Skip to content

RFC lib/crc: x86: convert the CRC assembly to C intrinsics

Qu Wenruo linux-btrfs linux-crypto lkml 1 version In review

Get series with b4
b4 am [email protected]

Versions newest first

  1. v2 RFC Latest6 patches 4 repliesIn review

Changes in v2 from the cover letter

- Use compiler's intrinsics header directly
- Convert all x86 asm files to C

Patches in v2 No applies recorded yet

#Subject and filesSizeRepliesApplied
1/6x86: Add a wrapper header for the compiler's SIMD intrinsicsarch/x86/include/asm/x86-intrinsics.h+49 -00 replies
2/6lib/crc: x86: Convert crc32c_x86_3way() from assembly to C intrinsicslib/crc/Makefile lib/crc/x86/crc32.h lib/crc/x86/crc32c-3way.S +1 more+270 -3610 replies
3/6lib/crc: x86: Convert crc32_lsb_*() from assembly to Clib/crc/Makefile lib/crc/x86/crc-pclmul-helpers.h lib/crc/x86/crc-pclmul-impl.h +2 more+353 -60 replies
4/6lib/crc: x86: Convert crc64_msb_*() from assembly to Clib/crc/Makefile lib/crc/x86/crc-pclmul-helpers.h lib/crc/x86/crc-pclmul-impl.h +3 more+83 -150 replies
5/6lib/crc: x86: Convert crc64_lsb_*() from assembly to Clib/crc/Makefile lib/crc/x86/crc-pclmul-impl.h lib/crc/x86/crc64-lsb-pclmul.c +1 more+39 -70 replies
6/6lib/crc: x86: Convert crc16_msb_*() from assembly to Clib/crc/Makefile lib/crc/x86/crc-pclmul-impl.h lib/crc/x86/crc-pclmul-template.S +3 more+32 -5830 replies

Reviews trailers per patch

No Reviewed-by, Acked-by or Tested-by trailers for v2 yet.

Read the v2 thread

Cover letter [PATCH RFC v2 0/6] lib/crc: x86: convert the CRC assembly to C intrinsics

[CHANGELOG]
v2:
- Use compiler's intrinsics header directly
- Convert all x86 asm files to C

Currently the x86 CRC code is all assembly: the generic [V]PCLMULQDQ template (12 functions: crc16, crc32 and crc64, three vector lengths each) and crc32c-3way.S. arm and arm64 already use C intrinsics.

This series converts all of it to C with the compiler's intrinsics, and removes the assembly. No algorithm, constant or calling convention changes, so the glue is untouched.

The goal is maintainability and portability, not speed: C is easier to read, review and extend than the macro-heavy assembly.
And it is also easier to port to userspace tools like btrfs-progs and xfsprogs which will require optimized CRC for offline operations.

Tests on a Zen5 VM show no obvious change in performance, except for clang with the MSB-first SSE and AVX2 functions, see below.

Patches:

1: asm/x86-intrinsics.h, a wrapper around <immintrin.h>.
2: crc32c_x86_3way().
3-6: crc32_lsb, crc64_msb, crc64_lsb and crc16_msb, each with the SSE4.1,
AVX2 and AVX512BW/VL variants. The template crc-pclmul-impl.h grows with them, and the assembly is removed in the last one.

Design decisions and trade-offs
===============================

- ISA selection: target attribute instead of per-file flags

Each function and helper has __attribute__((target(...))), the code is not built with -msse4.1, -mavx2 or -mavx512*. Per-file flags would need one object per ISA level, or the SSE function could use AVX-512.

Pros: all vector lengths of a CRC are in one file, and the compiler can only use an extension in the functions that run after the CPU feature checks (checked in the objdump).

Cons: no precedent in the kernel for selecting x86 ISA levels this way, and this is completely compiler dependent. See the GCC 8.1/8.2 issue below.

- One template, included once per function

The 12 functions differ only in vector length, CRC width and bit order, so crc-pclmul-impl.h generates one per inclusion, after the includer defined VL, CRC_BITS, CRC_MSB and CRC_FUNC.

I tried two different solutions:

* Nine standalone functions
About 1400 lines against about 490 with the template. And any fututre fixes needs to be duplicated 9 times.

* A DEFINE_CRC_PCLMUL_FUNCS() style macro
It can work, but the body cannot have #if, so the wide-vector stages become constant if()s and GCC warns about the dead code (-Wpsabi).

That macro also makes checkpatch warn about flow control in a macro, and compiler errors, gdb and perf point at the invocation line.

The include-as-template is not a common practice, but would be the least-worst solution I can come up with.

- Generated code and performance

Against the assembly (kbuild objects, GCC 16.2, clang 23): clang has the same total size for the 12 pclmul functions (7453 against 7482 bytes) and the same instruction count in each main loop.

GCC is 18% bigger (SSE +12%, AVX2 +22%, AVX-512 +19%): stack realignment in every function and, for AVX-512, loads not folded into vpternlogq (19 instead of 16 instructions in the LSB-first main loop).

crc32c_x86_3way() grows from 400 bytes to 603 (GCC) and 783 (clang), mostly prologue and unrolling of the tail. The main loop is 15, 17 and 16 instructions (asm, GCC, clang).

Every C function also gets endbr64 and the ftrace call, which the assembly never had. The call is patched to a nop at boot.

Throughput comes from a userspace harness using the same sources, built with the kernel's -mno-sse flags, on a Zen5 VM (Ryzen AI 9 HX 370): one pinned CPU, median of 7 runs. No in-kernel benchmark yet.

Peak is about 7.7, 15.4 and 30.7 GB/s for SSE, AVX2 and AVX-512. GCC is within 2% of the assembly from 1 KiB, up to 4-6% slower at 64-200 bytes and 8% for AVX2 at 512 bytes.

clang is the same, except crc64_msb and crc16_msb: SSE is 5-8% slower from 512 bytes, AVX2 5-7% from 1 KiB, but 14% faster at 512 bytes. AVX-512 is equal.

The clang SSE loop is 175 bytes against 153 for the assembly, as it keeps data in xmm8-xmm11 (REX prefixes). That is likely the cause, changing the XOR order did not help.

crc32c_x86_3way() is within 3% of the assembly: 8.6 to 9.0 GB/s at 200 bytes, 14.8 to 14.9 GB/s at 64 KiB.

Known issue: GCC 8.1 and 8.2

GCC 8.1 and 8.2 cannot build the AVX2 functions. Their <vpclmulqdqintrin.h> declares _mm256_clmulepi64_epi128() with avx512vl in its target, which fold256() lacks, so it cannot be inlined.

GCC 8.3 and later only need avx. I reproduced it on Compiler Explorer, where 8.3 to 9.5 build the code cleanly.

Calling __builtin_ia32_vpclmulqdq_v4di() directly for GCC older than 9 fixes it, but it is not included. 8.1 is still the documented minimum,
so: add that workaround, raise the minimum, or ignore 8.1 and 8.2?

Qu Wenruo (6):
x86: Add a wrapper header for the compiler's SIMD intrinsics lib/crc: x86: Convert crc32c_x86_3way() from assembly to C intrinsics lib/crc: x86: Convert crc32_lsb_*() from assembly to C lib/crc: x86: Convert crc64_msb_*() from assembly to C lib/crc: x86: Convert crc64_lsb_*() from assembly to C lib/crc: x86: Convert crc16_msb_*() from assembly to C

 arch/x86/include/asm/x86-intrinsics.h |  49 +++
 lib/crc/Makefile                      |  11 +-
 lib/crc/x86/crc-pclmul-helpers.h      |  90 ++++
 lib/crc/x86/crc-pclmul-impl.h         | 304 ++++++++++++++
 lib/crc/x86/crc-pclmul-template.S     | 575 --------------------------
 lib/crc/x86/crc-pclmul-template.h     |   2 +-
 lib/crc/x86/crc16-msb-pclmul.S        |   6 -
 lib/crc/x86/crc16-msb-pclmul.c        |  23 ++
 lib/crc/x86/crc32-pclmul.S            |   6 -
 lib/crc/x86/crc32-pclmul.c            |  23 ++
 lib/crc/x86/crc32.h                   |   2 +-
 lib/crc/x86/crc32c-3way.S             | 360 ----------------
 lib/crc/x86/crc32c-3way.c             | 264 ++++++++++++
 lib/crc/x86/crc64-lsb-pclmul.c        |  23 ++
 lib/crc/x86/crc64-msb-pclmul.c        |  23 ++
 lib/crc/x86/crc64-pclmul.S            |   7 -
 16 files changed, 811 insertions(+), 957 deletions(-)
 create mode 100644 arch/x86/include/asm/x86-intrinsics.h
 create mode 100644 lib/crc/x86/crc-pclmul-helpers.h
 create mode 100644 lib/crc/x86/crc-pclmul-impl.h
 delete mode 100644 lib/crc/x86/crc-pclmul-template.S
 delete mode 100644 lib/crc/x86/crc16-msb-pclmul.S
 create mode 100644 lib/crc/x86/crc16-msb-pclmul.c
 delete mode 100644 lib/crc/x86/crc32-pclmul.S
 create mode 100644 lib/crc/x86/crc32-pclmul.c
 delete mode 100644 lib/crc/x86/crc32c-3way.S
 create mode 100644 lib/crc/x86/crc32c-3way.c
 create mode 100644 lib/crc/x86/crc64-lsb-pclmul.c
 create mode 100644 lib/crc/x86/crc64-msb-pclmul.c
 delete mode 100644 lib/crc/x86/crc64-pclmul.S
Signature · 1 line
2.56.0