linux-kernel - RE: [PATCH 3/3] crypto: x86/crc32c - eliminate jump table and excessive unrolling

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Message-ID: <a6c0c04a0486404ca4db3fd57a809d5b@AcuMS.aculab.com>
Date: Mon, 14 Oct 2024 16:30:05 +0000
From: David Laight <David.Laight@...LAB.COM>
To: 'Eric Biggers' <ebiggers@...nel.org>, "linux-crypto@...r.kernel.org"
	<linux-crypto@...r.kernel.org>
CC: "x86@...nel.org" <x86@...nel.org>, "linux-kernel@...r.kernel.org"
	<linux-kernel@...r.kernel.org>, Ard Biesheuvel <ardb@...nel.org>, "Josh
 Poimboeuf" <jpoimboe@...nel.org>, Peter Zijlstra <peterz@...radead.org>
Subject: RE: [PATCH 3/3] crypto: x86/crc32c - eliminate jump table and
 excessive unrolling

From: Eric Biggers
> Sent: 14 October 2024 05:25
> 
> crc32c-pcl-intel-asm_64.S has a loop with 1 to 127 iterations fully
> unrolled and uses a jump table to jump into the correct location.  This
> optimization is misguided, as it bloats the binary code size and
> introduces an indirect call.  x86_64 CPUs can predict loops well, so it
> is fine to just use a loop instead.  Loop bookkeeping instructions can
> compete with the crc instructions for the ALUs, but this is easily
> mitigated by unrolling the loop by a smaller amount, such as 4 times.

Do you need to unroll it at all?

...
> +	# Unroll the loop by a factor of 4 to reduce the overhead of the loop
> +	# bookkeeping instructions, which can compete with crc32q for the ALUs.
> +.Lcrc_3lanes_4x_loop:
> +	crc32q	(bufp), crc_init_q
> +	crc32q	(bufp,chunk_bytes_q), crc1
> +	crc32q	(bufp,chunk_bytes_q,2), crc2
> +	crc32q	8(bufp), crc_init_q
> +	crc32q	8(bufp,chunk_bytes_q), crc1
> +	crc32q	8(bufp,chunk_bytes_q,2), crc2
> +	crc32q	16(bufp), crc_init_q
> +	crc32q	16(bufp,chunk_bytes_q), crc1
> +	crc32q	16(bufp,chunk_bytes_q,2), crc2
> +	crc32q	24(bufp), crc_init_q
> +	crc32q	24(bufp,chunk_bytes_q), crc1
> +	crc32q	24(bufp,chunk_bytes_q,2), crc2
> +	add	$32, bufp
> +	sub	$4, %eax
> +	jge	.Lcrc_3lanes_4x_loop

If you are really lucky you'll get two memory reads/clock.
So you won't ever to do than two crc32/clock.
Looking at Agner's instruction latency tables I don't think
any cpu can do more that one per clock, or pipeline them.
I think that means you don't even need two (never mind 3)
buffers.

Most modern x86 can do 4 or 5 (or even more) ALU operations
per clock - depending on the combination of instructions.

Replace the loop termination with a comparison of 'bufp'
against a pre-calculated limit and you get two instructions
(that might get merged into one u-op) for the loop overhead.
They'll run in parallel with the crc32q instructions.

I've never managed to get a 1-clock loop, but two is easy.
You might find that just:
10:
	crc32q	(bufp), crc
	crc32q	8(bufp), crc
	add		$16, bufp
	cmp		bufp, buf_lim
	jne		10b
will run at 8 bytes/clock on modern intel cpu.
You can write that in C with a simple asm function for the crc32
instruction itself.

You might need the more complex to setup loop:
	offset = -length;
	bufend = buf + length;
10:
	crc32q	(offset, bufend), crc
	crc32q	8(offset, bufend), crc
	add		&16, offset
	jne		10b
which uses negative offsets from the end of the buffer.

	David

-
Registered Address Lakeside, Bramley Road, Mount Farm, Milton Keynes, MK1 1PT, UK
Registration No: 1397386 (Wales)