lib/crypto: x86/chacha: Eliminate more never-taken branches
Subsystems (2)
Eric Biggers
maintainerPATCH 1/1 lib/crypto: x86/chacha: Eliminate more never-taken branches
The x86_64 optimized ChaCha code has assembly functions that generate 1, 2, 4, 8, or 16 keystream blocks and XOR them with up to that number of data blocks.
However, to avoid unnecessary overhead, the 4, 8, and 16-block functions, and the AVX2 2-block function, are never called with a length that is supported by the next-smaller function (that is, <= N/2 blocks, or <= 1 block for the SSSE3 4-block function), since a smaller function is called to handle such cases instead.
As a result, all the branches in those assembly functions that handle XOR'ing fewer than that minimum number of data blocks are dead code.
Remove these branches to eliminate dead code and overhead. Also rename the assembly functions to make it clear which cases they handle.
Some register moves in chacha_1to4blocks_ssse3() are also eliminated, as they were needed only because of the support for less than 1 block.
Note: many of the functions could use exclusive rather than inclusive lower bounds. Inclusive is used for simplicity.
--- lib/crypto/x86/chacha-avx2-x86_64.S | 73 +++++++-------------- lib/crypto/x86/chacha-avx512-x86_64.S | 94 +++++++++------------------ lib/crypto/x86/chacha-ssse3-x86_64.S | 51 ++++++--------- lib/crypto/x86/chacha.h | 72 +++++++++++++------- 4 files changed, 119 insertions(+), 171 deletions(-)
lib/crypto/x86/chacha-avx2-x86_64.S +23 -50
@@ -34,11 +34,11 @@ CTR4BL: .octa 0x00000000000000000000000000000002 .text -SYM_FUNC_START(chacha_2block_xor_avx2) +SYM_FUNC_START(chacha_1to2blocks_avx2) # %rdi: Input state matrix, s - # %rsi: up to 2 data blocks output, o - # %rdx: up to 2 data blocks input, i - # %rcx: input/output length in bytes + # %rsi: output data, o + # %rdx: input data, i + # %rcx: input/output data length in bytes: 1 to 2 blocks inclusive # %r8d: nrounds # This function encrypts two ChaCha blocks by loading the state
@@ -141,20 +141,16 @@ SYM_FUNC_START(chacha_2block_xor_avx2) vpaddd %ymm10,%ymm2,%ymm2 vpaddd %ymm11,%ymm3,%ymm3 - # xor the data with the keystream - + # XOR the first data block with the generated keystream. vperm2i128 $0x20, %ymm1, %ymm0, %ymm4 - cmp $1*32,%rax - jl .Lxorpart2 vpxor 0*32(%rdx),%ymm4,%ymm4 vmovdqu %ymm4,0*32(%rsi) vperm2i128 $0x20, %ymm3, %ymm2, %ymm4 - cmp $2*32,%rax - jl .Lxorpart2 vpxor 1*32(%rdx),%ymm4,%ymm4 vmovdqu %ymm4,1*32(%rsi) + # XOR up to 1 additional data block with the generated keystream. vperm2i128 $0x31, %ymm1, %ymm0, %ymm4 cmp $3*32,%rax jl .Lxorpart2
@@ -200,13 +196,13 @@ SYM_FUNC_START(chacha_2block_xor_avx2) lea -8(%r10),%rsp jmp .Ldone2 -SYM_FUNC_END(chacha_2block_xor_avx2) +SYM_FUNC_END(chacha_1to2blocks_avx2) -SYM_FUNC_START(chacha_4block_xor_avx2) +SYM_FUNC_START(chacha_2to4blocks_avx2) # %rdi: Input state matrix, s - # %rsi: up to 4 data blocks output, o - # %rdx: up to 4 data blocks input, i - # %rcx: input/output length in bytes + # %rsi: output data, o + # %rdx: input data, i + # %rcx: input/output data length in bytes: 2 to 4 blocks inclusive # %r8d: nrounds # This function encrypts four ChaCha blocks by loading the state
@@ -372,32 +368,24 @@ SYM_FUNC_START(chacha_4block_xor_avx2) vpaddd %ymm13,%ymm6,%ymm6 vpaddd %ymm15,%ymm7,%ymm7 - # xor the data with the keystream - + # XOR the first 2 data blocks with the generated keystream. vperm2i128 $0x20, %ymm1, %ymm0, %ymm8 - cmp $1*32,%rax - jl .Lxorpart4 vpxor 0*32(%rdx),%ymm8,%ymm8 vmovdqu %ymm8,0*32(%rsi) vperm2i128 $0x20, %ymm3, %ymm2, %ymm8 - cmp $2*32,%rax - jl .Lxorpart4 vpxor 1*32(%rdx),%ymm8,%ymm8 vmovdqu %ymm8,1*32(%rsi) vperm2i128 $0x31, %ymm1, %ymm0, %ymm8 - cmp $3*32,%rax - jl .Lxorpart4 vpxor 2*32(%rdx),%ymm8,%ymm8 vmovdqu %ymm8,2*32(%rsi) vperm2i128 $0x31, %ymm3, %ymm2, %ymm8 - cmp $4*32,%rax - jl .Lxorpart4 vpxor 3*32(%rdx),%ymm8,%ymm8 vmovdqu %ymm8,3*32(%rsi) + # XOR up to 2 additional data blocks with the generated keystream. vperm2i128 $0x20, %ymm5, %ymm4, %ymm8 cmp $5*32,%rax jl .Lxorpart4
@@ -455,13 +443,13 @@ SYM_FUNC_START(chacha_4block_xor_avx2) lea -8(%r10),%rsp jmp .Ldone4 -SYM_FUNC_END(chacha_4block_xor_avx2) +SYM_FUNC_END(chacha_2to4blocks_avx2) -SYM_FUNC_START(chacha_8block_xor_avx2) +SYM_FUNC_START(chacha_4to8blocks_avx2) # %rdi: Input state matrix, s - # %rsi: up to 8 data blocks output, o - # %rdx: up to 8 data blocks input, i - # %rcx: input/output length in bytes + # %rsi: output data, o + # %rdx: input data, i + # %rcx: input/output data length in bytes: 4 to 8 blocks inclusive # %r8d: nrounds # This function encrypts eight consecutive ChaCha blocks by loading
@@ -803,69 +791,54 @@ SYM_FUNC_START(chacha_8block_xor_avx2) vpunpcklqdq %ymm15,%ymm0,%ymm13 vpunpckhqdq %ymm15,%ymm0,%ymm15 - # interleave 128-bit words in state n, n+4 - # xor/write first four blocks + # Do the final 128-bit interleave within the XOR sequence. + + # XOR the first 4 data blocks with the generated keystream. vmovdqa 0x00(%rsp),%ymm1 vperm2i128 $0x20,%ymm4,%ymm1,%ymm0 - cmp $0x0020,%rax - jl .Lxorpart8 vpxor 0x0000(%rdx),%ymm0,%ymm0 vmovdqu %ymm0,0x0000(%rsi) vperm2i128 $0x31,%ymm4,%ymm1,%ymm4 vperm2i128 $0x20,%ymm12,%ymm8,%ymm0 - cmp $0x0040,%rax - jl .Lxorpart8 vpxor 0x0020(%rdx),%ymm0,%ymm0 vmovdqu %ymm0,0x0020(%rsi) vperm2i128 $0x31,%ymm12,%ymm8,%ymm12 vmovdqa 0x40(%rsp),%ymm1 vperm2i128 $0x20,%ymm6,%ymm1,%ymm0 - cmp $0x0060,%rax - jl .Lxorpart8 vpxor 0x0040(%rdx),%ymm0,%ymm0 vmovdqu %ymm0,0x0040(%rsi) vperm2i128 $0x31,%ymm6,%ymm1,%ymm6 vperm2i128 $0x20,%ymm14,%ymm10,%ymm0 - cmp $0x0080,%rax - jl .Lxorpart8 vpxor 0x0060(%rdx),%ymm0,%ymm0 vmovdqu %ymm0,0x0060(%rsi) vperm2i128 $0x31,%ymm14,%ymm10,%ymm14 vmovdqa 0x20(%rsp),%ymm1 vperm2i128 $0x20,%ymm5,%ymm1,%ymm0 - cmp $0x00a0,%rax - jl .Lxorpart8 vpxor 0x0080(%rdx),%ymm0,%ymm0 vmovdqu %ymm0,0x0080(%rsi) vperm2i128 $0x31,%ymm5,%ymm1,%ymm5 vperm2i128 $0x20,%ymm13,%ymm9,%ymm0 - cmp $0x00c0,%rax - jl .Lxorpart8 vpxor 0x00a0(%rdx),%ymm0,%ymm0 vmovdqu %ymm0,0x00a0(%rsi) vperm2i128 $0x31,%ymm13,%ymm9,%ymm13 vmovdqa 0x60(%rsp),%ymm1 vperm2i128 $0x20,%ymm7,%ymm1,%ymm0 - cmp $0x00e0,%rax - jl .Lxorpart8 vpxor 0x00c0(%rdx),%ymm0,%ymm0 vmovdqu %ymm0,0x00c0(%rsi) vperm2i128 $0x31,%ymm7,%ymm1,%ymm7 vperm2i128 $0x20,%ymm15,%ymm11,%ymm0 - cmp $0x0100,%rax - jl .Lxorpart8 vpxor 0x00e0(%rdx),%ymm0,%ymm0 vmovdqu %ymm0,0x00e0(%rsi) vperm2i128 $0x31,%ymm15,%ymm11,%ymm15 - # xor remaining blocks, write to output + # XOR up to 4 additional data blocks with the generated keystream. vmovdqa %ymm4,%ymm0 cmp $0x0120,%rax jl .Lxorpart8
@@ -943,4 +916,4 @@ SYM_FUNC_START(chacha_8block_xor_avx2) jmp .Ldone8 -SYM_FUNC_END(chacha_8block_xor_avx2) +SYM_FUNC_END(chacha_4to8blocks_avx2)
lib/crypto/x86/chacha-avx512-x86_64.S +29 -65
231 lines not on this page · raw message
lib/crypto/x86/chacha-ssse3-x86_64.S +20 -31
88 lines not on this page · raw message
lib/crypto/x86/chacha.h +47 -25
155 lines not on this page · raw message
base-commit: 9fbbbaefd5f95551da18426c200cf41e1b4255a1
prerequisite-patch-id: 890b33260038bff2e3adfe7867af5919666677fc
prerequisite-patch-id: 36cadf8c358a9778d745637c00368df82a93ce0d
prerequisite-patch-id: b9ef92f4abcdfe8946d645db12187f6293a46381
prerequisite-patch-id: 85904a5ef5aa8a48c311b2e87ed4d2403bd9e351
prerequisite-patch-id: b2272c2d61bf0db8f678f393b3907a7bce7e99d6
Signature · 1 line
2.56.0
Tested on Zen 5 (Ryzen 9 9950X) in a KVM guest, on top of base 9fbbbaefd5f9 + the 5 prerequisite patches. KUnit chacha suite + benchmark (64..16384 B incl. 200/511/513, 3 runs each), compared with the tree without this patch:
path CPU setup KUnit perf ------------------- --------------------- ----- ------------ AVX-512, zmm native pass -1.0..-0.1% AVX-512VL, ymm only spoofed SKX (6/0x55) pass -0.3..+1.1% AVX2 clearcpuid=avx512f pass -0.6..+1.0% SSSE3 clearcpuid=avx2 pass -0.4..+0.0%
There is a little loss in the zmm case. I presume we can live with that, but was worth mentioning.
Signature · 5 lines
Antonio Quartulli CEO and Co-Founder Mandelbit Srl https://www.mandelbit.com
Eric Biggers
maintainerQuoted 3 lines · Antonio Quartulli
path CPU setup KUnit perf ------------------- --------------------- ----- ------------ AVX-512, zmm native pass -1.0..-0.1%
[...]
Quoted 2 lines
There is a little loss in the zmm case. I presume we can live with that, but was worth mentioning.
Probably just noise, or maybe instruction alignment which is best tweaked separately if needed rather than relying on chance.
Note that removing these branches will help mostly if the caches (instruction cache and branch predictor) are cold, which the benchmark doesn't measure. We maybe should start trying to measure the cold cache case in the lib/crypto/ benchmarks, as it is meaningful too.
- Eric
Quoted 10 lines · Eric Biggers
Quoted 3 lines · Antonio Quartulli
path CPU setup KUnit perf ------------------- --------------------- ----- ------------ AVX-512, zmm native pass -1.0..-0.1%[...]
Quoted 2 lines
There is a little loss in the zmm case. I presume we can live with that, but was worth mentioning.
Probably just noise, or maybe instruction alignment which is best tweaked separately if needed rather than relying on chance.
My guess is also with the alignment shift.
Signature · 5 lines
Antonio Quartulli CEO and Co-Founder Mandelbit Srl https://www.mandelbit.com
Quoted 22 lines · Eric Biggers
The
x86_64optimized ChaCha code has assembly functions that generate 1, 2, 4, 8, or 16 keystream blocks and XOR them with up to that number of data blocks.However, to avoid unnecessary overhead, the 4, 8, and 16-block functions, and the AVX2 2-block function, are never called with a length that is supported by the next-smaller function (that is, <= N/2 blocks, or <= 1 block for the SSSE3 4-block function), since a smaller function is called to handle such cases instead.
As a result, all the branches in those assembly functions that handle XOR'ing fewer than that minimum number of data blocks are dead code.
Remove these branches to eliminate dead code and overhead. Also rename the assembly functions to make it clear which cases they handle.
Some register moves in
chacha_1to4blocks_ssse3()are also eliminated, as they were needed only because of the support for less than 1 block.Note: many of the functions could use exclusive rather than inclusive lower bounds. Inclusive is used for simplicity.
Quoted 7 lines
Signed-off-by Eric Biggers <[email protected]>--- lib/crypto/x86/chacha-avx2-x86_64.S | 73 +++++++-------------- lib/crypto/x86/chacha-avx512-x86_64.S | 94 +++++++++------------------ lib/crypto/x86/chacha-ssse3-x86_64.S | 51 ++++++--------- lib/crypto/x86/chacha.h | 72 +++++++++++++------- 4 files changed, 119 insertions(+), 171 deletions(-)
Applied to https://git.kernel.org/pub/scm/linux/kernel/git/ebiggers/linux.git/log/?h=libcrypto-next
- Eric