lib/crc: x86: rewrite crc32c_x86_3way() in C with inline asm

Unlike user space, we can not use intrinsics, so some instructions must still use inlined ASM, but that is only limited to crc32_u*() helpers and the PCLMULQDQ based lanes combination.

Those wrappers are in the new crc32c-inst.h header, and are also utilized by crc32c_arch() and the new C based crc32c_x86_3way().

The hot loop is the same sequence of crc32 instructions as in the asm version, with the same lane addressing.
The differences in the generated code (x86_64, clang, function tracing enabled) are as follows.

The old 4x unrolled loop is 12 memory-operand crc32q plus 3 bookkeeping instructions per iteration:

    crc32q  (bufp), crc0_q
    crc32q  (bufp,chunk_bytes_q), crc1
    crc32q  (bufp,chunk_bytes_q,2), crc2

... same for offsets 8, 16 and 24 ...
add $32, bufp
sub $4, %eax
jge .Lcrc_3lanes_4x_loop

The new one has the same 12 crc32 and the same addressing, but clang can't fold the load into the instruction because ASM_INPUT_RM is "r" for clang, so every crc32 has a preceding mov:

    mov     (%rsi),%r14
    crc32   %r14,%r9
    mov     (%rsi,%rdx,8),%r14
    crc32   %r14,%r11
    mov     (%rsi,%r10,1),%r14
    crc32   %r14,%rax
    ... same for offsets 8, 16 and 24 ...
    add     $-4,%rbx
    add     $0x20,%rsi
    cmp     $3,%rbx
    ja      <loop>

Thus 12 extra loads per iteration. They don't matter in practice, as the loop is bound by the latency of the three crc32 dependency chains, not by uop throughput.
Forcing the memory form with "m" made no difference either in a userspace benchmark. gcc accepts "rm" and folds the loads into crc32q (checked on a userspace build of the same code).

The combination step is the same instructions, with the old code being

pmovzxdq (K_table-8)(%rax,chunk_bytes_q), %xmm0
movq crc0_q, %xmm1
pclmulqdq $0x00, %xmm0, %xmm1
movq crc1, %xmm2
pclmulqdq $0x10, %xmm0, %xmm2
pxor %xmm2, %xmm1
movq %xmm1, %rax
xor (bufp,chunk_bytes_q,2), %rax
mov crc2, crc0_q
crc32 %rax, crc0_q

and the new one

    mov     %r9d,%r9d
    mov     %r11d,%r11d
    pmovzxdq 0x0(%rdi,%rdx,8),%xmm0
    movq    %r9,%xmm1
    pclmulqdq $0x00,%xmm0,%xmm1
    movq    %r11,%xmm2
    pclmulqdq $0x10,%xmm0,%xmm2
    pxor    %xmm2,%xmm1
    movq    %xmm1,%rdx
    xor     (%rsi,%r10,1),%rdx
    crc32   %rdx,%rax

The two movs at the top are the (u64) zero extensions of the lane CRCs, which are redundant as crc32q already zeroes the upper half. The register copy of crc2 disappears as crc2 is just the accumulator for the final crc32.

The rest (prologue/epilogue, alignment head and sub-qword tail) is not performance critical. The only visible difference is the usual kernel function prologue with a few callee-saved register pushes.

Measured throughput matches the old implementation within noise, both in a userspace comparison (gcc and clang, 200 bytes to 1 MiB) and in the in-kernel CRC32C KUnit benchmark, using a Zen5 (HX 370) based system.

Assisted-by LLM (coding and testing)

Signed-off-by Qu Wenruo <[email protected]>

---
Reason for RFC:

The idea is inspired when I was cleaning up btrfs-progs, to prepare for new arm64 CRC32C implementation, as a preparation I want to remove all ASM file and inline ASM usages in userspace btrfs-progs. That works pretty well, so here I'm trying to cross-port this change to the kernel 3way acceleration path.

Although I would prefer a code base with less minimal ASM files, I'm not sure if everyone prefers this solution other than hand-written ASM code.

Furthermore all my tests are on a Zen5 based system (HX 370), with cpuid masking to test the 3way optimization code.

So no test on older platforms.

If this one is fine, I can continue converting the AVX512 version too. And hopefully can cross-port the C version of AVX512 back to btrfs-progs.

As much as I'd like to reduce the use of asm, I'm not sure this is super convincing. We get worse code generation and have to fall back to inline asm anyway, as the x86 intrinsics are still unusable in the kernel (which is different from userspace).

This patch also introduces a compiler error with gcc. It seems only clang was tested. (Showing again that this kind of code often has compiler-specific issues, and we have to be extra careful to test it with every supported compiler version.)

There's also a subtle bug where the inline asm blocks are missing the volatile qualifier, so technically they could be reordered after the kernel_fpu_end() and corrupt a userspace process's XMM registers. Without inline asm, this issue would not have been possible.

I'd be interested in seeing what you can come up with for crc-pclmul-template.S, though I think that one is going to be harder to replace.

Quoted 10 lines · Eric Biggers

As much as I'd like to reduce the use of asm, I'm not sure this is super convincing. We get worse code generation and have to fall back to inline asm anyway, as the x86 intrinsics are still unusable in the kernel (which is different from userspace).

This patch also introduces a compiler error with gcc. It seems only clang was tested. (Showing again that this kind of code often has compiler-specific issues, and we have to be extra careful to test it with every supported compiler version.)

Quoted 8 lines

There's also a subtle bug where the inline asm blocks are missing the volatile qualifier, so technically they could be reordered after the kernel_fpu_end() and corrupt a userspace process's XMM registers. Without inline asm, this issue would not have been possible.

I'd be interested in seeing what you can come up with for crc-pclmul-template.S, though I think that one is going to be harder to replace.

Also, just to emphasize: most "C" code using this strategy will be mostly inline asm blocks, since that's what is needed to access the vector registers in kernel code. See lib/raid/*/x86/ for some examples.

crc32c_x86_3way() is an exception because it mostly use scalar instructions, with only a few vector instructions. So it makes this strategy seem a bit more workable. But actually, as soon as this same strategy is adopted for crc-pclmul-template.S or any of the many crypto assembly files (AES, GHASH, ChaCha, Poly1305, BLAKE2, etc.) that use far more vector instructions, it will become mostly inline asm blocks, just like the RAID code.

So I feel it's kind of an odd path to go down. Perhaps as a prerequisite for reimplementing some of this code in C (or will it soon be Rust?), we should get the x86 intrinsics working in the kernel first?

- Eric

Quoted 32 lines · Eric Biggers

Quoted 10 lines · Eric Biggers

As much as I'd like to reduce the use of asm, I'm not sure this is super convincing. We get worse code generation and have to fall back to inline asm anyway, as the x86 intrinsics are still unusable in the kernel (which is different from userspace).

This patch also introduces a compiler error with gcc. It seems only clang was tested. (Showing again that this kind of code often has compiler-specific issues, and we have to be extra careful to test it with every supported compiler version.)

Quoted 8 lines

There's also a subtle bug where the inline asm blocks are missing the volatile qualifier, so technically they could be reordered after the kernel_fpu_end() and corrupt a userspace process's XMM registers. Without inline asm, this issue would not have been possible.

I'd be interested in seeing what you can come up with for crc-pclmul-template.S, though I think that one is going to be harder to replace.

Also, just to emphasize: most "C" code using this strategy will be mostly inline asm blocks, since that's what is needed to access the vector registers in kernel code. See lib/raid/*/x86/ for some examples.

crc32c_x86_3way() is an exception because it mostly use scalar instructions, with only a few vector instructions. So it makes this strategy seem a bit more workable. But actually, as soon as this same strategy is adopted for crc-pclmul-template.S or any of the many crypto assembly files (AES, GHASH, ChaCha, Poly1305, BLAKE2, etc.) that use far more vector instructions, it will become mostly inline asm blocks, just like the RAID code.

Quoted 3 lines

So I feel it's kind of an odd path to go down. Perhaps as a prerequisite for reimplementing some of this code in C (or will it soon be Rust?), we should get the x86 intrinsics working in the kernel first?

Indeed, it works almost flawlessly in user space just because there are already intrinsics available, and most of the code is just regular control flow, with mostly scalar code.

Thanks for the feedback, I'll just give up the idea in kernel, and enjoy the complete intrinsics in user space for now.

Thanks,
Qu

Quoted 44 lines · Qu Wenruo

Quoted 32 lines · Eric Biggers

Quoted 10 lines · Eric Biggers

As much as I'd like to reduce the use of asm, I'm not sure this is super convincing. We get worse code generation and have to fall back to inline asm anyway, as the x86 intrinsics are still unusable in the kernel (which is different from userspace).

This patch also introduces a compiler error with gcc. It seems only clang was tested. (Showing again that this kind of code often has compiler-specific issues, and we have to be extra careful to test it with every supported compiler version.)

Quoted 8 lines

There's also a subtle bug where the inline asm blocks are missing the volatile qualifier, so technically they could be reordered after the kernel_fpu_end() and corrupt a userspace process's XMM registers. Without inline asm, this issue would not have been possible.

I'd be interested in seeing what you can come up with for crc-pclmul-template.S, though I think that one is going to be harder to replace.

Also, just to emphasize: most "C" code using this strategy will be mostly inline asm blocks, since that's what is needed to access the vector registers in kernel code. See lib/raid/*/x86/ for some examples.

crc32c_x86_3way() is an exception because it mostly use scalar instructions, with only a few vector instructions. So it makes this strategy seem a bit more workable. But actually, as soon as this same strategy is adopted for crc-pclmul-template.S or any of the many crypto assembly files (AES, GHASH, ChaCha, Poly1305, BLAKE2, etc.) that use far more vector instructions, it will become mostly inline asm blocks, just like the RAID code.

Quoted 3 lines

So I feel it's kind of an odd path to go down. Perhaps as a prerequisite for reimplementing some of this code in C (or will it soon be Rust?), we should get the x86 intrinsics working in the kernel first?

Indeed, it works almost flawlessly in user space just because there are already intrinsics available, and most of the code is just regular control flow, with mostly scalar code.

Thanks for the feedback, I'll just give up the idea in kernel, and enjoy the complete intrinsics in user space for now.

Quoted 2 lines

Thanks,
Qu

Okay. I'd be interested in someone trying to get the x86 intrinsics working in the kernel, though. Just when I last tried it, it still wasn't possible to include <immintrin.h> without errors.

- Eric

Quoted 45 lines · Eric Biggers

Quoted 44 lines · Qu Wenruo

Quoted 32 lines · Eric Biggers

Quoted 10 lines · Eric Biggers

As much as I'd like to reduce the use of asm, I'm not sure this is super convincing.  We get worse code generation and have to fall back to inline asm anyway, as the x86 intrinsics are still unusable in the kernel (which is different from userspace).

This patch also introduces a compiler error with gcc. It seems only clang was tested.  (Showing again that this kind of code often has compiler-specific issues, and we have to be extra careful to test it with every supported compiler version.)

Quoted 8 lines

There's also a subtle bug where the inline asm blocks are missing the volatile qualifier, so technically they could be reordered after the kernel_fpu_end() and corrupt a userspace process's XMM registers. Without inline asm, this issue would not have been possible.

I'd be interested in seeing what you can come up with for crc-pclmul-template.S, though I think that one is going to be harder to replace.

Also, just to emphasize: most "C" code using this strategy will be mostly inline asm blocks, since that's what is needed to access the vector registers in kernel code.  See lib/raid/*/x86/ for some examples.

crc32c_x86_3way() is an exception because it mostly use scalar instructions, with only a few vector instructions.  So it makes this strategy seem a bit more workable.  But actually, as soon as this same strategy is adopted for crc-pclmul-template.S or any of the many crypto assembly files (AES, GHASH, ChaCha, Poly1305, BLAKE2, etc.) that use far more vector instructions, it will become mostly inline asm blocks, just like the RAID code.

Quoted 3 lines

So I feel it's kind of an odd path to go down.  Perhaps as a prerequisite for reimplementing some of this code in C (or will it soon be Rust?), we should get the x86 intrinsics working in the kernel first?

Indeed, it works almost flawlessly in user space just because there are already intrinsics available, and most of the code is just regular control flow, with mostly scalar code.

Thanks for the feedback, I'll just give up the idea in kernel, and enjoy the complete intrinsics in user space for now.

Quoted 6 lines

Quoted 2 lines

Thanks,
Qu

Okay.  I'd be interested in someone trying to get the x86 intrinsics working in the kernel, though.  Just when I last tried it, it still wasn't possible to include <immintrin.h> without errors.

I don't think we can use the compiler's wrappers directly, there are quite a lot of conflicts with kernel's library.

So a different, independent copy may be needed.

If we can get that part done, it will be much easier to do the conversion. Although introducing the intrinsics itself may be a much larger project.

Thanks,
Qu

Quoted 2 lines

- Eric