Skip to contentSkip to conversation

arm64: Speed up CRC-32 using PMULL instructions

PATCH Superseded Ard Biesheuvel 3 participants 6 messages Oct 17, 2024

Subsystems (2)

v3 of 4 Superseded Latest is v4 →

lore
Share & tools
lore
#0 lore raw

v3 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 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.

Cc Eric Biggers <[email protected]>
Cc Kees Cook <[email protected]>

Ard Biesheuvel (2):
arm64/lib: Handle CRC-32 alternative in C code arm64/crc32: Implement 4-way interleave using PMULL

 arch/arm64/lib/Makefile     |   2 +-
 arch/arm64/lib/crc32-4way.S | 242 ++++++++++++++++++++
 arch/arm64/lib/crc32-glue.c |  82 +++++++
 arch/arm64/lib/crc32.S      |  22 +-
 4 files changed, 331 insertions(+), 17 deletions(-)
 create mode 100644 arch/arm64/lib/crc32-4way.S
 create mode 100644 arch/arm64/lib/crc32-glue.c
Signature · 1 line
2.47.0.rc1.288.g06298d1525-goog
#1 lore raw

PATCH v3 1/2 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
index 13e6a2829116..8e882f479d98 100644
@@ -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
new file mode 100644
index 000000000000..0b51761d4b75
@@ -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
index 8340dccff46f..22139691c7ae 100644
@@ -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
#2 lore raw

PATCH v3 2/2 arm64/crc32: Implement 4-way interleave using PMULL

In reply to 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]

[0] https://github.com/ebiggers/libdeflate/blob/master/scripts/gen_crc32_multipliers.c

---
 arch/arm64/lib/Makefile     |   2 +-
 arch/arm64/lib/crc32-4way.S | 242 ++++++++++++++++++++
 arch/arm64/lib/crc32-glue.c |  48 ++++
 3 files changed, 291 insertions(+), 1 deletion(-)
arch/arm64/lib/Makefile +1 -1
index 8e882f479d98..52f3d3e302f7 100644
@@ -13,7 +13,7 @@ endif
 
 lib-$(CONFIG_ARCH_HAS_UACCESS_FLUSHCACHE) += uaccess_flushcache.o
 
-obj-$(CONFIG_CRC32) += crc32.o crc32-glue.o
+obj-$(CONFIG_CRC32) += crc32.o crc32-glue.o crc32-4way.o
 
 obj-$(CONFIG_FUNCTION_ERROR_INJECTION) += error-inject.o
 
arch/arm64/lib/crc32-4way.S new file +242 -0

242 lines not on this page · raw message

arch/arm64/lib/crc32-glue.c +48 -0

75 lines not on this page · raw message

Signature · 1 line
2.47.0.rc1.288.g06298d1525-goog
#3 lore raw
In reply to Ard Biesheuvel
Quoted 32 lines · Ard Biesheuvel

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 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.

Quoted 7 lines
Cc Eric Biggers <[email protected]>
Cc Kees Cook <[email protected]>

Ard Biesheuvel (2):
arm64/lib: Handle CRC-32 alternative in C code arm64/crc32: Implement 4-way interleave using PMULL

I'll need to respin this - the crc32_be code doesn't actually work correctly.

#4 lore raw
Quoted 6 lines · Ard Biesheuvel
Quoted 4 lines

Ard Biesheuvel (2):
arm64/lib: Handle CRC-32 alternative in C code arm64/crc32: Implement 4-way interleave using PMULL

I'll need to respin this - the crc32_be code doesn't actually work correctly.

Right, good catch. It looks like it needs an rbit of the crc value at the beginning and end. lib/crc32test.c doesn't actually test crc32_be_arm64_4way() because it runs the tests with IRQs disabled; it probably shouldn't do that.

On a slightly related topic, since any crc32_le() and __crc32c_le() functions in arch/*/lib/ are automatically exposed as shash algorithms via the crypto API (this was already the case, but your other patch makes this more explicit by properly separating them from the generic implementation), I wonder if all the remaining arch/*/crypto/crc32*.c should be migrated to arch/*/lib/, and then users of crc32 and crc32c like ext4 and f2fs should just use the library functions instead of shash. That would simply things greatly. See e.g. the horrible hacks used in ext4_chksum() and __f2fs_crc32()...

The only crc32 and crc32c implementations that *aren't* software based are those in drivers/crypto/stm32/stm32-crc32.c and drivers/crypto/inside-secure/safexcel_hash.c. Access to those would be lost by going through lib. But I strongly suspect they exist just because the hardware supported it and not because they are actually useful.

- Eric

#5 lore raw
Quoted 7 lines · Eric Biggers
Quoted 5 lines · Ard Biesheuvel
Quoted 4 lines

Ard Biesheuvel (2):
arm64/lib: Handle CRC-32 alternative in C code arm64/crc32: Implement 4-way interleave using PMULL

Quoted 6 lines
Quoted 1 line

I'll need to respin this - the crc32_be code doesn't actually work correctly.

Right, good catch. It looks like it needs an rbit of the crc value at the beginning and end. lib/crc32test.c doesn't actually test crc32_be_arm64_4way() because it runs the tests with IRQs disabled; it probably shouldn't do that.

Yeah, we should probably fix that.

Quoted 9 lines

On a slightly related topic, since any crc32_le() and __crc32c_le() functions in arch/*/lib/ are automatically exposed as shash algorithms via the crypto API (this was already the case, but your other patch makes this more explicit by properly separating them from the generic implementation), I wonder if all the remaining arch/*/crypto/crc32*.c should be migrated to arch/*/lib/, and then users of crc32 and crc32c like ext4 and f2fs should just use the library functions instead of shash. That would simply things greatly. See e.g. the horrible hacks used in ext4_chksum() and __f2fs_crc32()...

Quoted 6 lines

The only crc32 and crc32c implementations that *aren't* software based are those in drivers/crypto/stm32/stm32-crc32.c and drivers/crypto/inside-secure/safexcel_hash.c. Access to those would be lost by going through lib. But I strongly suspect they exist just because the hardware supported it and not because they are actually useful.

Indeed. Another case where the flexibility of the shash interface doesn't buy us anything but overhead and complexity.