arm64: Speed up CRC-32 using PMULL instructions
Subsystems (2)
v4 cover arm64: Speed up CRC-32 using PMULL instructions
From: Ard Biesheuvel <[email protected]>
The CRC-32 code is library code, and is not part of the crypto subsystem. This means that callers may not generally be aware of the kind of implementation that backs it, and so we've refrained from using FP/SIMD code in the past, as it disables preemption, and this may incur scheduling latencies that the caller did not anticipate.
This was solved a while ago, and on arm64, kernel mode FP/SIMD no longer disables preemption.
This means we can happily use PMULL instructions in the CRC-32 library code, which permits an optimization to be implemented that results in a speedup of 2 - 2.8x for inputs >1k in size (on Apple M2)
Patch #1 implements some prepwork to handle the scalar CRC-32 alternatives patching in C code.
Changes since v3:
- fix broken crc32be version
- add patch to tidy up existing code for reuse
- add 4-way code to existing .S file
Changes since v2:
- drop alternatives.h #include (#1)
- drop unneeded branch (#2)
- fix comment max -> min (#2)
- add Eric's Rb
Changes since v1:
- rename crc32-pmull.S to crc32-4way.S and avoid pmull in the function names to avoid confusion about the nature of the implementation;
- polish the asm a bit, and add some comments
- don't return via the scalar code if len dropped to 0 after calling the 4-way code.
Ard Biesheuvel (3):
arm64/lib: Handle CRC-32 alternative in C code arm64/crc32: Reorganize bit/byte ordering macros arm64/crc32: Implement 4-way interleave using PMULL
arch/arm64/lib/Makefile | 2 +- arch/arm64/lib/crc32-glue.c | 82 +++++ arch/arm64/lib/crc32.S | 344 ++++++++++++++++---- 3 files changed, 356 insertions(+), 72 deletions(-) create mode 100644 arch/arm64/lib/crc32-glue.c
Signature · 1 line
2.47.0.rc1.288.g06298d1525-goog
PATCH v4 1/3 arm64/lib: Handle CRC-32 alternative in C code
From: Ard Biesheuvel <[email protected]>
In preparation for adding another code path for performing CRC-32, move the alternative patching for ARM64_HAS_CRC32 into C code. The logic for deciding whether to use this new code path will be implemented in C too.
--- arch/arm64/lib/Makefile | 2 +- arch/arm64/lib/crc32-glue.c | 34 ++++++++++++++++++++ arch/arm64/lib/crc32.S | 22 ++++--------- 3 files changed, 41 insertions(+), 17 deletions(-)
arch/arm64/lib/Makefile +1 -1
@@ -13,7 +13,7 @@ endif lib-$(CONFIG_ARCH_HAS_UACCESS_FLUSHCACHE) += uaccess_flushcache.o -obj-$(CONFIG_CRC32) += crc32.o +obj-$(CONFIG_CRC32) += crc32.o crc32-glue.o obj-$(CONFIG_FUNCTION_ERROR_INJECTION) += error-inject.o
arch/arm64/lib/crc32-glue.c new file +34 -0
@@ -0,0 +1,34 @@ +// SPDX-License-Identifier: GPL-2.0-only + +#include <linux/crc32.h> +#include <linux/linkage.h> + +#include <asm/alternative.h> + +asmlinkage u32 crc32_le_arm64(u32 crc, unsigned char const *p, size_t len); +asmlinkage u32 crc32c_le_arm64(u32 crc, unsigned char const *p, size_t len); +asmlinkage u32 crc32_be_arm64(u32 crc, unsigned char const *p, size_t len); + +u32 __pure crc32_le (u32 crc,unsigned char const *p,size_t len) +{ +if (!alternative_has_cap_likely (ARM64_HAS_CRC32 )) +return crc32_le_base (crc, p, len); + +return crc32_le_arm64 (crc, p, len); +} + +u32 __pure __crc32c_le (u32 crc,unsigned char const *p,size_t len) +{ +if (!alternative_has_cap_likely (ARM64_HAS_CRC32 )) +return __crc32c_le_base (crc, p, len); + +return crc32c_le_arm64 (crc, p, len); +} + +u32 __pure crc32_be (u32 crc,unsigned char const *p,size_t len) +{ +if (!alternative_has_cap_likely (ARM64_HAS_CRC32 )) +return crc32_be_base (crc, p, len); + +return crc32_be_arm64 (crc, p, len); +}
arch/arm64/lib/crc32.S +6 -16
@@ -6,7 +6,6 @@ */ #include <linux/linkage.h> -#include <asm/alternative.h> #include <asm/assembler.h> .arch armv8-a+crc
@@ -136,25 +135,16 @@ CPU_BE( rev16 \reg, \reg ) .endm .align 5 -SYM_FUNC_START(crc32_le) -alternative_if_not ARM64_HAS_CRC32 - b crc32_le_base -alternative_else_nop_endif +SYM_FUNC_START(crc32_le_arm64) __crc32 -SYM_FUNC_END(crc32_le) +SYM_FUNC_END(crc32_le_arm64) .align 5 -SYM_FUNC_START(__crc32c_le) -alternative_if_not ARM64_HAS_CRC32 - b __crc32c_le_base -alternative_else_nop_endif +SYM_FUNC_START(crc32c_le_arm64) __crc32 c -SYM_FUNC_END(__crc32c_le) +SYM_FUNC_END(crc32c_le_arm64) .align 5 -SYM_FUNC_START(crc32_be) -alternative_if_not ARM64_HAS_CRC32 - b crc32_be_base -alternative_else_nop_endif +SYM_FUNC_START(crc32_be_arm64) __crc32 be=1 -SYM_FUNC_END(crc32_be) +SYM_FUNC_END(crc32_be_arm64)
Signature · 1 line
2.47.0.rc1.288.g06298d1525-goog
PATCH v4 2/3 arm64/crc32: Reorganize bit/byte ordering macros
In reply to Ard BiesheuvelFrom: Ard Biesheuvel <[email protected]>
In preparation for a new user, reorganize the bit/byte ordering macros that are used to parameterize the crc32 template code and instantiate CRC-32, CRC-32c and 'big endian' CRC-32.
--- arch/arm64/lib/crc32.S | 91 +++++++++----------- 1 file changed, 39 insertions(+), 52 deletions(-)
arch/arm64/lib/crc32.S +39 -52
@@ -10,44 +10,48 @@ .arch armv8-a+crc - .macro byteorder, reg, be - .if \be -CPU_LE( rev \reg, \reg ) - .else -CPU_BE( rev \reg, \reg ) - .endif + .macro bitle, reg .endm - .macro byteorder16, reg, be - .if \be -CPU_LE( rev16 \reg, \reg ) - .else -CPU_BE( rev16 \reg, \reg ) - .endif + .macro bitbe, reg + rbit \reg, \reg .endm - .macro bitorder, reg, be - .if \be - rbit \reg, \reg - .endif + .macro bytele, reg .endm - .macro bitorder16, reg, be - .if \be + .macro bytebe, reg rbit \reg, \reg - lsr \reg, \reg, #16 - .endif + lsr \reg, \reg, #24 + .endm + + .macro hwordle, reg +CPU_BE( rev16 \reg, \reg ) .endm - .macro bitorder8, reg, be - .if \be + .macro hwordbe, reg +CPU_LE( rev \reg, \reg ) rbit \reg, \reg - lsr \reg, \reg, #24 - .endif +CPU_BE( lsr \reg, \reg, #16 ) + .endm + + .macro le, regs:vararg + .irp r, \regs +CPU_BE( rev \r, \r ) + .endr + .endm + + .macro be, regs:vararg + .irp r, \regs +CPU_LE( rev \r, \r ) + .endr + .irp r, \regs + rbit \r, \r + .endr .endm - .macro __crc32, c, be=0 - bitorder w0, \be + .macro __crc32, c, order=le + bit\order w0 cmp x2, #16 b.lt 8f // less than 16 bytes
@@ -60,14 +64,7 @@ CPU_BE( rev16 \reg, \reg ) add x8, x8, x1 add x1, x1, x7 ldp x5, x6, [x8] - byteorder x3, \be - byteorder x4, \be - byteorder x5, \be - byteorder x6, \be - bitorder x3, \be - bitorder x4, \be - bitorder x5, \be - bitorder x6, \be + \order x3, x4, x5, x6 tst x7, #8 crc32\c\()x w8, w0, x3
@@ -95,42 +92,32 @@ CPU_BE( rev16 \reg, \reg ) 32: ldp x3, x4, [x1], #32 sub x2, x2, #32 ldp x5, x6, [x1, #-16] - byteorder x3, \be - byteorder x4, \be - byteorder x5, \be - byteorder x6, \be - bitorder x3, \be - bitorder x4, \be - bitorder x5, \be - bitorder x6, \be + \order x3, x4, x5, x6 crc32\c\()x w0, w0, x3 crc32\c\()x w0, w0, x4 crc32\c\()x w0, w0, x5 crc32\c\()x w0, w0, x6 cbnz x2, 32b -0: bitorder w0, \be +0: bit\order w0 ret 8: tbz x2, #3, 4f ldr x3, [x1], #8 - byteorder x3, \be - bitorder x3, \be + \order x3 crc32\c\()x w0, w0, x3 4: tbz x2, #2, 2f ldr w3, [x1], #4 - byteorder w3, \be - bitorder w3, \be + \order w3 crc32\c\()w w0, w0, w3 2: tbz x2, #1, 1f ldrh w3, [x1], #2 - byteorder16 w3, \be - bitorder16 w3, \be + hword\order w3 crc32\c\()h w0, w0, w3 1: tbz x2, #0, 0f ldrb w3, [x1] - bitorder8 w3, \be + byte\order w3 crc32\c\()b w0, w0, w3 -0: bitorder w0, \be +0: bit\order w0 ret .endm
@@ -146,5 +133,5 @@ SYM_FUNC_END(crc32c_le_arm64) .align 5 SYM_FUNC_START(crc32_be_arm64) - __crc32 be=1 + __crc32 order=be SYM_FUNC_END(crc32_be_arm64)
Signature · 1 line
2.47.0.rc1.288.g06298d1525-goog
Re: [PATCH v4 2/3] arm64/crc32: Reorganize bit/byte ordering macros
Quoted 10 lines · Ard Biesheuvel
From: Ard Biesheuvel <[email protected]>
In preparation for a new user, reorganize the bit/byte ordering macros that are used to parameterize the crc32 template code and instantiate CRC-32, CRC-32c and 'big endian' CRC-32.
Signed-off-by Ard Biesheuvel <[email protected]>--- arch/arm64/lib/crc32.S | 91 +++++++++----------- 1 file changed, 39 insertions(+), 52 deletions(-)
- Eric
PATCH v4 3/3 arm64/crc32: Implement 4-way interleave using PMULL
In reply to Ard BiesheuvelFrom: Ard Biesheuvel <[email protected]>
Now that kernel mode NEON no longer disables preemption, using FP/SIMD in library code which is not obviously part of the crypto subsystem is no longer problematic, as it will no longer incur unexpected latencies.
So accelerate the CRC-32 library code on arm64 to use a 4-way interleave, using PMULL instructions to implement the folding.
On Apple M2, this results in a speedup of 2 - 2.8x when using input sizes of 1k - 8k. For smaller sizes, the overhead of preserving and restoring the FP/SIMD register file may not be worth it, so 1k is used as a threshold for choosing this code path.
The coefficient tables were generated using code provided by Eric. [0]
[0] https://github.com/ebiggers/libdeflate/blob/master/scripts/gen_crc32_multipliers.c
--- arch/arm64/lib/crc32-glue.c | 48 ++++ arch/arm64/lib/crc32.S | 231 +++++++++++++++++++- 2 files changed, 276 insertions(+), 3 deletions(-)
arch/arm64/lib/crc32-glue.c +48 -0
@@ -4,16 +4,40 @@#include <linux/linkage.h> #include <asm/alternative.h> +#include <asm/cpufeature.h> +#include <asm/neon.h> +#include <asm/simd.h> + +#include <crypto/internal/simd.h> + +// The minimum input length to consider the 4-way interleaved code path +static const size_t min_len =1024 ; asmlinkage u32 crc32_le_arm64(u32 crc, unsigned char const *p, size_t len); asmlinkage u32 crc32c_le_arm64(u32 crc, unsigned char const *p, size_t len); asmlinkage u32 crc32_be_arm64(u32 crc, unsigned char const *p, size_t len); +asmlinkage u32 crc32_le_arm64_4way(u32 crc, unsigned char const *p, size_t len); +asmlinkage u32 crc32c_le_arm64_4way(u32 crc, unsigned char const *p, size_t len); +asmlinkage u32 crc32_be_arm64_4way(u32 crc, unsigned char const *p, size_t len); +u32 __pure crc32_le (u32 crc,unsigned char const *p,size_t len) {if (!alternative_has_cap_likely (ARM64_HAS_CRC32 ))return crc32_le_base (crc, p, len); +if (len >= min_len &&cpu_have_named_feature (PMULL ) &&crypto_simd_usable ()) { +kernel_neon_begin (); + crc =crc32_le_arm64_4way (crc, p, len); +kernel_neon_end (); + + p +=round_down (len,64 ); + len %=64 ; + +if (!len) +return crc; + } +return crc32_le_arm64 (crc, p, len); }
@@ -22,6 +46,18 @@ u32 __pure __crc32c_le(u32 crc, unsigned char const *p, size_t len)if (!alternative_has_cap_likely (ARM64_HAS_CRC32 ))return __crc32c_le_base (crc, p, len); +if (len >= min_len &&cpu_have_named_feature (PMULL ) &&crypto_simd_usable ()) { +kernel_neon_begin (); + crc =crc32c_le_arm64_4way (crc, p, len); +kernel_neon_end (); + + p +=round_down (len,64 ); + len %=64 ; + +if (!len) +return crc; + } +return crc32c_le_arm64 (crc, p, len); }
@@ -30,5 +66,17 @@ u32 __pure crc32_be(u32 crc, unsigned char const *p, size_t len)if (!alternative_has_cap_likely (ARM64_HAS_CRC32 ))return crc32_be_base (crc, p, len); +if (len >= min_len &&cpu_have_named_feature (PMULL ) &&crypto_simd_usable ()) { +kernel_neon_begin (); + crc =crc32_be_arm64_4way (crc, p, len); +kernel_neon_end (); + + p +=round_down (len,64 ); + len %=64 ; + +if (!len) +return crc; + } +return crc32_be_arm64 (crc, p, len); }
arch/arm64/lib/crc32.S +228 -3
245 lines not on this page · raw message
Signature · 1 line
2.47.0.rc1.288.g06298d1525-goog
Re: [PATCH v4 3/3] arm64/crc32: Implement 4-way interleave using PMULL
Quoted 16 lines · Ard Biesheuvel
From: Ard Biesheuvel <[email protected]>
Now that kernel mode NEON no longer disables preemption, using FP/SIMD in library code which is not obviously part of the crypto subsystem is no longer problematic, as it will no longer incur unexpected latencies.
So accelerate the CRC-32 library code on arm64 to use a 4-way interleave, using PMULL instructions to implement the folding.
On Apple M2, this results in a speedup of 2 - 2.8x when using input sizes of 1k - 8k. For smaller sizes, the overhead of preserving and restoring the FP/SIMD register file may not be worth it, so 1k is used as a threshold for choosing this code path.
The coefficient tables were generated using code provided by Eric. [0]
Quoted 8 lines
[0] https://github.com/ebiggers/libdeflate/blob/master/scripts/gen_crc32_multipliers.c
Cc Eric Biggers <[email protected]>Signed-off-by Ard Biesheuvel <[email protected]>--- arch/arm64/lib/crc32-glue.c | 48 ++++ arch/arm64/lib/crc32.S | 231 +++++++++++++++++++- 2 files changed, 276 insertions(+), 3 deletions(-)
Review
Quoted 1 line
(quoted diff) +1
-0+ if (len >= min_len && cpu_have_named_feature(PMULL) && crypto_simd_usable()) {
Using crypto_simd_usable() here causes a build error when CRYPTO_ALGAPI2=m.
https://lore.kernel.org/linux-crypto/[email protected]
will fix that.
- Eric
Quoted 10 lines · Ard Biesheuvel
The CRC-32 code is library code, and is not part of the crypto subsystem. This means that callers may not generally be aware of the kind of implementation that backs it, and so we've refrained from using FP/SIMD code in the past, as it disables preemption, and this may incur scheduling latencies that the caller did not anticipate.
This was solved a while ago, and on arm64, kernel mode FP/SIMD no longer disables preemption.
[...]
Applied to arm64 (for-next/crc32), thanks!
[1/3] arm64/lib: Handle CRC-32 alternative in C code
https://git.kernel.org/arm64/c/fc7454107d1b [2/3] arm64/crc32: Reorganize bit/byte ordering macros https://git.kernel.org/arm64/c/b98b23e19492 [3/3] arm64/crc32: Implement 4-way interleave using PMULL https://git.kernel.org/arm64/c/a6478d69cf56
Signature · 1 line
Catalin