riscv: Optimize crc32 with Zbc extension
Subsystems (2)
PATCH 1/1 riscv: Optimize crc32 with Zbc extension
As suggested by the B-ext spec, the Zbc (carry-less multiplication) instructions can be used to accelerate CRC calculations. Currently, the crc32 is the most widely used crc function inside kernel, so this patch focuses on the optimization of just the crc32 APIs.
Compared with the current table-lookup based optimization, Zbc based optimization can also achieve large stride during CRC calculation loop, meantime, it avoids the memory access latency of the table-lookup based implementation and it reduces memory footprint.
If Zbc feature is not supported in a runtime environment, then the table-lookup based implementation would serve as fallback via alternative mechanism. To avoid the performance concern of unalignment access, we also use the fallback implementation to handle the head and tail bytes if any, the main body is accelerated by Zbc extension.
This patch is tested on QEMU VM with the kernel CRC32 selftest.
--- arch/riscv/Kconfig | 23 +++++ arch/riscv/lib/Makefile | 1 + arch/riscv/lib/crc32.c | 216 ++++++++++++++++++++++++++++++++++++++++ include/linux/crc32.h | 3 + 4 files changed, 243 insertions(+) create mode 100644 arch/riscv/lib/crc32.c
arch/riscv/Kconfig +23 -0
@@ -549,6 +549,29 @@ config RISCV_ISA_ZBB If you don't know what to do here, say Y. +config TOOLCHAIN_HAS_ZBC + bool + default y + depends on !64BIT || $(cc-option,-mabi=lp64 -march=rv64ima_zbc) + depends on !32BIT || $(cc-option,-mabi=ilp32 -march=rv32ima_zbc) + depends on LLD_VERSION >= 150000 || LD_VERSION >= 23900 + depends on AS_HAS_OPTION_ARCH + +config RISCV_ISA_ZBC + bool "Zbc extension support for carry-less multiplication instructions" + depends on TOOLCHAIN_HAS_ZBC + depends on MMU + depends on RISCV_ALTERNATIVE + default y + help + Adds support to dynamically detect the presence of the Zbc + extension (carry-less multiplication) and enable its usage. + + The Zbc extension could accelerate CRC (cyclic redundancy check) + calculations. + + If you don't know what to do here, say Y. + config RISCV_ISA_ZICBOM bool "Zicbom extension support for non-coherent DMA operation" depends on MMU
arch/riscv/lib/Makefile +1 -0
@@ -9,5 +9,6 @@ lib-y += strncmp.o lib-$(CONFIG_MMU) += uaccess.o lib-$(CONFIG_64BIT) += tishift.o lib-$(CONFIG_RISCV_ISA_ZICBOZ) += clear_page.o +lib-$(CONFIG_RISCV_ISA_ZBC) += crc32.o obj-$(CONFIG_FUNCTION_ERROR_INJECTION) += error-inject.o
arch/riscv/lib/crc32.c new file +216 -0
216 lines not on this page · raw message
include/linux/crc32.h +3 -0
@@ -9,7 +9,9 @@#include <linux/bitrev.h> u32 __pure crc32_le (u32 crc,unsigned char const *p,size_t len); +u32 __pure crc32_le_base (u32 crc,unsigned char const *p,size_t len);u32 __pure crc32_be (u32 crc,unsigned char const *p,size_t len); +u32 __pure crc32_be_base (u32 crc,unsigned char const *p,size_t len);/** * crc32_le_combine - Combine two crc32 check values into one. For two
@@ -37,6 +39,7 @@ static inline u32 crc32_le_combine(u32 crc1, u32 crc2, size_t len2) }u32 __pure __crc32c_le (u32 crc,unsigned char const *p,size_t len); +u32 __pure __crc32c_le_base (u32 crc,unsigned char const *p,size_t len);/** * __crc32c_le_combine - Combine two crc32c check values into one. For two
Signature · 1 line
2.25.1
kernel test robot
build botkernel test robot noticed the following build warnings:
Hi Xiao,
kernel test robot noticed the following build warnings:
[auto build test WARNING on linus/master]
[also build test WARNING on v6.7 next-20240108]
[If your patch is applied to the wrong git tree, kindly drop us a note. And when submitting patch, we suggest to use '--base' as documented in
https://git-scm.com/docs/git-format-patch#_base_tree_information]
url: https://github.com/intel-lab-lkp/linux/commits/Xiao-Wang/riscv-Optimize-crc32-with-Zbc-extension/20240105-161053 base: linus/master patch link: https://lore.kernel.org/r/20240105080830.3738117-1-xiao.w.wang%40intel.com patch subject: [PATCH] riscv: Optimize crc32 with Zbc extension config: riscv-randconfig-r121-20240106 (https://download.01.org/0day-ci/archive/20240108/[email protected]/config) compiler: riscv64-linux-gcc (GCC) 13.2.0 reproduce: (https://download.01.org/0day-ci/archive/20240108/[email protected]/reproduce)
If you fix the issue in a separate patch/commit (i.e. not just a new version of the same patch/commit), kindly add following tags
| Reported-by: kernel test robot <[email protected]>
| Closes: https://lore.kernel.org/oe-kbuild-all/[email protected]/
sparse warnings: (new ones prefixed by >>)
>> arch/riscv/lib/crc32.c:192:19: sparse: sparse: invalid assignment: ^= arch/riscv/lib/crc32.c:192:19: sparse: left side has type unsigned long arch/riscv/lib/crc32.c:192:19: sparse: right side has type restricted __be64 >> arch/riscv/lib/crc32.c:110:42: sparse: sparse: restricted __le64 degrades to integer >> arch/riscv/lib/crc32.c:110:42: sparse: sparse: restricted __le64 degrades to integer
vim +192 arch/riscv/lib/crc32.c
78
79 static inline u32 __pure crc32_le_generic(u32 crc, unsigned char const *p,
80 #if (BITS_PER_LONG == 64)
81 size_t len, u32 poly, u64 poly_qt,
82 #else
83 size_t len, u32 poly, u32 poly_qt,
84 #endif
85 fallback crc_fb)
86 {
87 size_t offset, head_len, tail_len;
88 const unsigned long *p_ul;
89 unsigned long s;
90
91 asm_volatile_goto(ALTERNATIVE("j %l[legacy]", "nop", 0,
92 RISCV_ISA_EXT_ZBC, 1)
93 : : : : legacy);
94
95 /* Handle the unalignment head. */
96 offset = (unsigned long)p & OFFSET_MASK;
97 if (offset) {
98 head_len = MIN(STEP - offset, len);
99 crc = crc_fb(crc, p, head_len);
100 len -= head_len;
101 p += head_len;
102 }
103
104 tail_len = len & OFFSET_MASK;
105 len = len >> STEP_ORDER;
106 p_ul = (unsigned long *)p;
107
108 for (int i = 0; i < len; i++) {
109 #if (BITS_PER_LONG == 64)
> 110 s = (unsigned long)crc ^ __cpu_to_le64(*p_ul++);
111 /* We don't have a "clmulrh" insn, so use clmul + slli instead.
112 */
113 asm volatile (".option push\n"
114 ".option arch,+zbc\n"
115 "clmul %0, %1, %2\n"
116 "slli %0, %0, 1\n"
117 "xor %0, %0, %1\n"
118 "clmulr %0, %0, %3\n"
119 "srli %0, %0, 32\n"
120 ".option pop\n"
121 : "=&r" (crc)
122 : "r" (s),
123 "r" (poly_qt),
124 "r" ((u64)poly << 32)
125 :);
126 #else
127 s = crc ^ __cpu_to_le32(*p_ul++);
128 /* We don't have a "clmulrh" insn, so use clmul + slli instead.
129 */
130 asm volatile (".option push\n"
131 ".option arch,+zbc\n"
132 "clmul %0, %1, %2\n"
133 "slli %0, %0, 1\n"
134 "xor %0, %0, %1\n"
135 "clmulr %0, %0, %3\n"
136 ".option pop\n"
137 : "=&r" (crc)
138 : "r" (s),
139 "r" (poly_qt),
140 "r" (poly)
141 :);
142 #endif
143 }
144
145 /* Handle the tail bytes. */
146 if (tail_len)
147 crc = crc_fb(crc, (unsigned char const *)p_ul, tail_len);
148 return crc;
149
150 legacy:
151 return crc_fb(crc, p, len);
152 }
153
154 u32 __pure crc32_le(u32 crc, unsigned char const *p, size_t len)
155 {
156 return crc32_le_generic(crc, p, len, CRC32_POLY_LE, CRC32_POLY_QT_LE,
157 crc32_le_base);
158 }
159
160 u32 __pure __crc32c_le(u32 crc, unsigned char const *p, size_t len)
161 {
162 return crc32_le_generic(crc, p, len, CRC32C_POLY_LE,
163 CRC32C_POLY_QT_LE, __crc32c_le_base);
164 }
165
166 u32 __pure crc32_be(u32 crc, unsigned char const *p, size_t len)
167 {
168 size_t offset, head_len, tail_len;
169 const unsigned long *p_ul;
170 unsigned long s;
171
172 asm_volatile_goto(ALTERNATIVE("j %l[legacy]", "nop", 0,
173 RISCV_ISA_EXT_ZBC, 1)
174 : : : : legacy);
175
176 /* Handle the unalignment head. */
177 offset = (unsigned long)p & OFFSET_MASK;
178 if (offset) {
179 head_len = MIN(STEP - offset, len);
180 crc = crc32_be_base(crc, p, head_len);
181 len -= head_len;
182 p += head_len;
183 }
184
185 tail_len = len & OFFSET_MASK;
186 len = len >> STEP_ORDER;
187 p_ul = (unsigned long *)p;
188
189 for (int i = 0; i < len; i++) {
190 #if (BITS_PER_LONG == 64)
191 s = (unsigned long)crc << 32;
> 192 s ^= __cpu_to_be64(*p_ul++);Signature · 2 lines
0-DAY CI Kernel Test Service https://github.com/intel/lkp-tests/wiki
Quoted 10 lines · Xiao Wang
As suggested by the B-ext spec, the Zbc (carry-less multiplication) instructions can be used to accelerate CRC calculations. Currently, the crc32 is the most widely used crc function inside kernel, so this patch focuses on the optimization of just the crc32 APIs.
Compared with the current table-lookup based optimization, Zbc based optimization can also achieve large stride during CRC calculation loop, meantime, it avoids the memory access latency of the table-lookup based implementation and it reduces memory footprint.
Quoted 7 lines
If Zbc feature is not supported in a runtime environment, then the table-lookup based implementation would serve as fallback via alternative mechanism. To avoid the performance concern of unalignment access, we also use the fallback implementation to handle the head and tail bytes if any, the main body is accelerated by Zbc extension.
This patch is tested on QEMU VM with the kernel CRC32 selftest.
Ideally we'd also have the results of some benchmarks, or at least a dynamic instruction count or something, but I don't suspect that the table-lookup would "win" over Zbc. The bigger question is whether we want three implementations, because I assume we want Zvbc, particularly since [1] says
"""
Zvbc is listed as a development option for use in other algorithms, and will become mandatory. Scalar Zbc is now listed as an expansion option, i.e., it will probably not become mandatory.
"""
[1] https://github.com/riscv/riscv-profiles/blob/main/rva23-profile.adoc
A few nits below.
Quoted 71 lines
Signed-off-by Xiao Wang <[email protected]>--- arch/riscv/Kconfig | 23 +++++ arch/riscv/lib/Makefile | 1 + arch/riscv/lib/crc32.c | 216 ++++++++++++++++++++++++++++++++++++++++ include/linux/crc32.h | 3 + 4 files changed, 243 insertions(+) create mode 100644 arch/riscv/lib/crc32.carch/riscv/Kconfig +23
-0@@ -549,6 +549,29 @@ config RISCV_ISA_ZBB If you don't know what to do here, say Y. +config TOOLCHAIN_HAS_ZBC + bool + default y + depends on !64BIT || $(cc-option,-mabi=lp64 -march=rv64ima_zbc) + depends on !32BIT || $(cc-option,-mabi=ilp32 -march=rv32ima_zbc) + depends on LLD_VERSION >= 150000 || LD_VERSION >= 23900 + depends on AS_HAS_OPTION_ARCH + +config RISCV_ISA_ZBC + bool "Zbc extension support for carry-less multiplication instructions" + depends on TOOLCHAIN_HAS_ZBC + depends on MMU + depends on RISCV_ALTERNATIVE + default y + help + Adds support to dynamically detect the presence of the Zbc + extension (carry-less multiplication) and enable its usage. + + The Zbc extension could accelerate CRC (cyclic redundancy check) + calculations. + + If you don't know what to do here, say Y. + config RISCV_ISA_ZICBOM bool "Zicbom extension support for non-coherent DMA operation" depends on MMUarch/riscv/lib/Makefile +1
-0@@ -9,5 +9,6 @@ lib-y += strncmp.o lib-$(CONFIG_MMU) += uaccess.o lib-$(CONFIG_64BIT) += tishift.o lib-$(CONFIG_RISCV_ISA_ZICBOZ) += clear_page.o +lib-$(CONFIG_RISCV_ISA_ZBC) += crc32.o obj-$(CONFIG_FUNCTION_ERROR_INJECTION) += error-inject.oarch/riscv/lib/crc32.c new file +10
-0@@ -0,0 +1,216 @@ +// SPDX-License-Identifier: GPL-2.0-only +/* +* Accelerated CRC32 implementation with Zbc extension. +* +* Copyright (C) 2024 Intel Corporation +* +* Authors: +* Xiao Wang <[email protected]> +*/ +
arch/riscv/lib/crc32.c line 20
Quoted 10 lines
arch/riscv/lib/crc32.c new file +10
-0+#include <asm/hwcap.h> +#include <asm/alternative-macros.h> +#include <asm/byteorder.h> + +#include <linux/types.h> +#include <linux/crc32poly.h> +#include <linux/crc32.h> +#include <linux/byteorder/generic.h> + +#define MIN (a, b) ((a) < (b) ? (a) : (b))
min() from linux/minmax.h?
arch/riscv/lib/crc32.c line 22
Quoted 2 lines
arch/riscv/lib/crc32.c new file +2
-0+ +#if (BITS_PER_LONG ==64 )
I think riscv prefers
#if __riscv_xlen == 64
In any case, the () are unnecessary.
Quoted 17 lines
arch/riscv/lib/crc32.c new file +17
-0+/* Slide by XLEN bits per iteration */ +# define STEP_ORDER 3 + +/* Each below polynomial quotient has an implicit bit for 2^XLEN */ + +/* Polynomial quotient of (2^(XLEN+32))/CRC32_POLY, in LE format */ +# define CRC32_POLY_QT_LE 0x5a72d812fb808b20 + +/* Polynomial quotient of (2^(XLEN+32))/CRC32C_POLY, in LE format */ +# define CRC32C_POLY_QT_LE 0xa434f61c6f5389f8 + +/* Polynomial quotient of (2^(XLEN+32))/CRC32_POLY, in BE format, it should be +* the same as the bit-reversed version of CRC32_POLY_QT_LE +*/ +# define CRC32_POLY_QT_BE 0x04d101df481b4e5a +#elif (BITS_PER_LONG ==32 ) +# define STEP_ORDER 2
arch/riscv/lib/crc32.c line 49
Quoted 10 lines
arch/riscv/lib/crc32.c new file +10
-0+/* Each quotient should match the upper half of its analog in RV64 */ +# define CRC32_POLY_QT_LE 0xfb808b20 +# define CRC32C_POLY_QT_LE 0x6f5389f8 +# define CRC32_POLY_QT_BE 0x04d101df +#else +# error "Unexpected BITS_PER_LONG" +#endif + +#define STEP (1 << STEP_ORDER) +#define OFFSET_MASK (STEP - 1)
Should tab out the values of these defines so they line up.
arch/riscv/lib/crc32.c line 53
Quoted 4 lines
arch/riscv/lib/crc32.c new file +4
-0+ +/* +* Refer to https://www.corsix.org/content/barrett-reduction-polynomials for +* better understanding of how this math works.
Thanks for this pointer. I read it, but I didn't digest it enough to understand it, which means my review isn't confirming the math is correct.
Quoted 21 lines
arch/riscv/lib/crc32.c new file +21
-0+* +* let "+" denotes polynomial add (XOR) +* let "-" denotes polynomial sub (XOR) +* let "*" denotes polynomial multiplication +* let "/" denotes polynomial floor division +* let "S" denotes source data, XLEN bit wide +* let "P" denotes CRC32 polynomial +* let "T" denotes 2^(XLEN+32) +* let "QT" denotes quotient of T/P, with the bit for 2^XLEN being implicit +* +* crc32(S, P) +* => S * (2^32) - S * (2^32) / P * P +* => lowest 32 bits of: S * (2^32) / P * P +* => lowest 32 bits of: S * (2^32) * (T / P) / T * P +* => lowest 32 bits of: S * (2^32) * quotient / T * P +* => lowest 32 bits of: S * quotient / 2^XLEN * P +* => lowest 32 bits of: (clmul_high_part(S, QT) + S) * P +* => clmul_low_part(clmul_high_part(S, QT) + S, P) +* +* In terms of below implementations, the BE case is more intuitive, since the +* higher order bit sits at more significant position.
arch/riscv/lib/crc32.c line 84
Quoted 10 lines
arch/riscv/lib/crc32.c new file +10
-0+*/ + +typedef u32 (*fallback )(u32 crc,unsigned char const *p,size_t len); + +static inline u32 __pure crc32_le_generic(u32 crc, unsigned char const *p, +#if (BITS_PER_LONG == 64) + size_t len, u32 poly, u64 poly_qt, +#else + size_t len, u32 poly, u32 poly_qt, +#endif
How about creating a new type for poly_qt, defined as u64 for xlen=64 and u32 for xlen=32 to avoid the #ifdef?
Quoted 18 lines
arch/riscv/lib/crc32.c new file +18
-0+ fallback crc_fb) +{ +size_t offset, head_len, tail_len; +const unsigned long *p_ul; +unsigned long s; + +asm_volatile_goto (ALTERNATIVE ("j %l[legacy]" ,"nop" ,0 , +RISCV_ISA_EXT_ZBC ,1 ) + : : : : legacy); + +/* Handle the unalignment head. */ + offset = (unsigned long )p &OFFSET_MASK ; +if (offset) { + head_len =MIN (STEP - offset, len); + crc =crc_fb (crc, p, head_len); + len -= head_len; + p += head_len; + }
arch/riscv/lib/crc32.c line 112
Quoted 10 lines
arch/riscv/lib/crc32.c new file +10
-0+ + tail_len = len &OFFSET_MASK ; + len = len >>STEP_ORDER ; + p_ul = (unsigned long *)p; + +for (int i =0 ; i < len; i++) { +#if (BITS_PER_LONG ==64 ) + s = (unsigned long )crc ^__cpu_to_le64 (*p_ul++); +/* We don't have a "clmulrh" insn, so use clmul + slli instead. +*/
need opening /* comment wing
Quoted 6 lines
arch/riscv/lib/crc32.c new file +6
-0+ asmvolatile (".option push\n" +".option arch,+zbc\n" +"clmul %0, %1, %2\n" +"slli %0, %0, 1\n" +"xor %0, %0, %1\n" + "clmulr %0, %0, %3\n"
arch/riscv/lib/crc32.c line 128
Quoted 10 lines
arch/riscv/lib/crc32.c new file +10
-0+"srli %0, %0, 32\n" +".option pop\n" + : "=&r" (crc) + : "r" (s), +" r" (poly_qt), + "r" ((u64)poly << 32) + :); +#else + s = crc ^__cpu_to_le32 (*p_ul++); +/* We don't have a "clmulrh" insn, so use clmul + slli instead.
also here
Quoted 4 lines
arch/riscv/lib/crc32.c new file +4
-0+*/ + asmvolatile (".option push\n" +".option arch,+zbc\n" + "clmul %0, %1, %2\n"
arch/riscv/lib/crc32.c line 142
Quoted 10 lines
arch/riscv/lib/crc32.c new file +10
-0+"slli %0, %0, 1\n" +"xor %0, %0, %1\n" +"clmulr %0, %0, %3\n" +".option pop\n" + : "=&r" (crc) + : "r" (s), +" r" (poly_qt), + "r" (poly) + :); +#endif
Instead of the #ifdef here, we could provide function wrappers for the asm which would be defined above in the first #ifdef ladder.
Quoted 43 lines
arch/riscv/lib/crc32.c new file +43
-0+ } + +/* Handle the tail bytes. */ +if (tail_len) + crc =crc_fb (crc, (unsigned char const *)p_ul, tail_len); +return crc; + +legacy: +return crc_fb (crc, p, len); +} + +u32 __pure crc32_le (u32 crc,unsigned char const *p,size_t len) +{ +return crc32_le_generic (crc, p, len,CRC32_POLY_LE ,CRC32_POLY_QT_LE , + crc32_le_base); +} + +u32 __pure __crc32c_le (u32 crc,unsigned char const *p,size_t len) +{ +return crc32_le_generic (crc, p, len,CRC32C_POLY_LE , +CRC32C_POLY_QT_LE , __crc32c_le_base); +} + +u32 __pure crc32_be (u32 crc,unsigned char const *p,size_t len) +{ +size_t offset, head_len, tail_len; +const unsigned long *p_ul; +unsigned long s; + +asm_volatile_goto (ALTERNATIVE ("j %l[legacy]" ,"nop" ,0 , +RISCV_ISA_EXT_ZBC ,1 ) + : : : : legacy); + +/* Handle the unalignment head. */ + offset = (unsigned long )p &OFFSET_MASK ; +if (offset) { + head_len =MIN (STEP - offset, len); + crc =crc32_be_base (crc, p, head_len); + len -= head_len; + p += head_len; + } + + tail_len = len &OFFSET_MASK ;
arch/riscv/lib/crc32.c line 195
Quoted 10 lines
arch/riscv/lib/crc32.c new file +10
-0+ len = len >>STEP_ORDER ; + p_ul = (unsigned long *)p; + +for (int i =0 ; i < len; i++) { +#if (BITS_PER_LONG ==64 ) + s = (unsigned long )crc <<32 ; + s ^=__cpu_to_be64 (*p_ul++); +#else + s = crc ^__cpu_to_be32 (*p_ul++); +#endif
Could write the above without #ifdef with
if (IS_ENABLED(CONFIG_64BIT)) {
...
} else {
...}
Quoted 46 lines
arch/riscv/lib/crc32.c new file +21
-0+ asmvolatile (".option push\n" +".option arch,+zbc\n" +"clmulh %0, %1, %2\n" +"xor %0, %0, %1\n" +"clmul %0, %0, %3\n" +".option pop\n" + :"=&r" (crc) + :"r" (s), +"r" (CRC32_POLY_QT_BE ), +"r" (CRC32_POLY_BE ) + :); + } + +/* Handle the tail bytes. */ +if (tail_len) + crc =crc32_be_base (crc, (unsigned char const *)p_ul, tail_len); +return crc; + +legacy: +return crc32_be_base (crc, p, len); +}include/linux/crc32.h +3
-0@@ -9,7 +9,9 @@#include <linux/bitrev.h> u32 __pure crc32_le (u32 crc,unsigned char const *p,size_t len); +u32 __pure crc32_le_base (u32 crc,unsigned char const *p,size_t len);u32 __pure crc32_be (u32 crc,unsigned char const *p,size_t len); +u32 __pure crc32_be_base (u32 crc,unsigned char const *p,size_t len);/** * crc32_le_combine - Combine two crc32 check values into one. For two @@ -37,6 +39,7 @@ static inline u32 crc32_le_combine(u32 crc1, u32 crc2, size_t len2) }u32 __pure __crc32c_le (u32 crc,unsigned char const *p,size_t len); +u32 __pure __crc32c_le_base (u32 crc,unsigned char const *p,size_t len);/** * __crc32c_le_combine - Combine two crc32c check values into one. For two Signature · 1 line
2.25.1
Thanks,
drew
...
Quoted 9 lines
arch/riscv/lib/crc32.c line 84
Quoted 6 lines
arch/riscv/lib/crc32.c new file +6
-0+static inline u32 __pure crc32_le_generic(u32 crc, unsigned char const *p, +#if (BITS_PER_LONG == 64) + size_t len, u32 poly, u64 poly_qt, +#else + size_t len, u32 poly, u32 poly_qt, +#endifHow about creating a new type for
poly_qt, defined as u64 for xlen=64 and u32 for xlen=32 to avoid the #ifdef?
unsigned long ?
...
Quoted 9 lines
arch/riscv/lib/crc32.c line 195
Quoted 7 lines
arch/riscv/lib/crc32.c new file +7
-0+for (int i =0 ; i < len; i++) { +#if (BITS_PER_LONG ==64 ) + s = (unsigned long )crc <<32 ; + s ^=__cpu_to_be64 (*p_ul++); +#else + s = crc ^__cpu_to_be32 (*p_ul++); +#endif Could write the above without #ifdef with
Haven't I seen a bpf patch that rather implies that byteswap is likely to be truly horrid?
I've not tried to parse the crc code (although I do understand how it should work). But I'm surprised you need a byteswap.
After all, the crc is basically a long division of the buffer by the crc constant.
The CRC I've done recently is the hdlc crc-16.
My nios version (also mips-like) has:
static __inline__ uint32_tcrc_step(uint32_t crc, uint32_t byte_val)
{
#if defined(crc_step_ci)
return crc_step_ci(byte_val, crc);
#else
uint32_t t = crc ^ (byte_val & 0xff);
t = (t ^ t << 4) & 0xff;
return crc >> 8 ^ t << 8 ^ t << 3 ^ t >> 4;#endif
}
I normally use a custom instruction for the logic - one clock. But the C code is only a couple of clocks slower that the best table lookup version.
On anything pipelined and multi-issue the C code is likely to be faster than a lookup table!
I don't know if any of the 32bit crc can be reduced the same way.
David
-
Registered Address Lakeside, Bramley Road, Mount Farm, Milton Keynes, MK1 1PT, UK Registration No: 1397386 (Wales)
Hi David,
Quoted 22 lines
-----Original Message-----
From: David Laight <[email protected]>
Sent: Wednesday, January 17, 2024 1:16 AM
To: 'Andrew Jones' <[email protected]>; Wang, Xiao W <[email protected]>
Cc: [email protected]; [email protected]; [email protected]; [email protected]; [email protected]; Li, Haicheng <[email protected]>; [email protected]; linux- [email protected]
Subject: RE: [PATCH] riscv: Optimize crc32 with Zbc extension...
Quoted 9 lines
arch/riscv/lib/crc32.c line 84
Quoted 6 lines
arch/riscv/lib/crc32.c new file +6
-0+static inline u32 __pure crc32_le_generic(u32 crc, unsigned char const *p, +#if (BITS_PER_LONG == 64) + size_t len, u32 poly, u64 poly_qt, +#else + size_t len, u32 poly, u32 poly_qt, +#endifHow about creating a new type for
poly_qt, defined as u64 for xlen=64 and u32 for xlen=32 to avoid the #ifdef?
Quoted 1 line
unsigned long ?
Yes, it's simpler. thanks.
Quoted 12 lines
...
Quoted 9 lines
arch/riscv/lib/crc32.c line 195
Quoted 7 lines
arch/riscv/lib/crc32.c new file +7
-0+for (int i =0 ; i < len; i++) { +#if (BITS_PER_LONG ==64 ) + s = (unsigned long )crc <<32 ; + s ^=__cpu_to_be64 (*p_ul++); +#else + s = crc ^__cpu_to_be32 (*p_ul++); +#endif Could write the above without #ifdef with
Quoted 8 lines
Haven't I seen a bpf patch that rather implies that byteswap is likely to be truly horrid?
I've not tried to parse the crc code (although I do understand how it should work). But I'm surprised you need a byteswap.
After all, the crc is basically a long division of the buffer by the crc constant.
For the *_be mode, the API expects that within each byte from the data stream,the higher order poly bit sits at more significant bit position, and within the parameter "u32 crc", the higher order poly bit sits at more significant bit position, regardless of CPU endianness.
After the unsigned long data loading from memory into a register, the "higher order poly bit sits at more significant bit position" is true for each byte, but not for the whole register on a little endian CPU. In order to do the XOR in s ^= __cpu_to_be64(*p_ul++), and in order to run the CLMUL insn at XLEN scale, we need to rearrange the whole register bits to get them rightly ordered.
Quoted 13 lines
The CRC I've done recently is the hdlc crc-16.
My nios version (also mips-like) has:static
__inline__uint32_tcrc_step(uint32_t crc, uint32_t byte_val)
{#if defined(crc_step_ci) return crc_step_ci(byte_val, crc); #else uint32_t t = crc ^ (byte_val & 0xff); t = (t ^ t << 4) & 0xff; return crc >> 8 ^ t << 8 ^ t << 3 ^ t >> 4;
Quoted 8 lines
#endif
}I normally use a custom instruction for the logic - one clock. But the C code is only a couple of clocks slower that the best table lookup version.
On anything pipelined and multi-issue the C code is likely to be faster than a lookup table!
I don't understand your code piece, but it looks only the least significant byte of "uint32_t byte_val" is involved in this crc16 calculation, I don't understand how it can work.
BRs,
Xiao
Quoted 8 lines
I don't know if any of the 32bit crc can be reduced the same way.
David
-
Registered Address Lakeside, Bramley Road, Mount Farm, Milton Keynes, MK1 1PT, UK
Registration No: 1397386 (Wales)
Hi Andrew,
Quoted 36 lines
-----Original Message-----
From: Andrew Jones <[email protected]>
Sent: Tuesday, January 16, 2024 11:04 PM
To: Wang, Xiao W <[email protected]>
Cc: [email protected]; [email protected]; [email protected]; [email protected]; [email protected]; Li, Haicheng <[email protected]>; [email protected]; linux- [email protected]
Subject: Re: [PATCH] riscv: Optimize crc32 with Zbc extensionQuoted 5 lines · Xiao Wang
As suggested by the B-ext spec, the Zbc (carry-less multiplication) instructions can be used to accelerate CRC calculations. Currently, the crc32 is the most widely used crc function inside kernel, so this patch focuses on the optimization of just the crc32 APIs.
Quoted 8 lines
Compared with the current table-lookup based optimization, Zbc based optimization can also achieve large stride during CRC calculation loop, meantime, it avoids the memory access latency of the table-lookup based implementation and it reduces memory footprint.
If Zbc feature is not supported in a runtime environment, then the table-lookup based implementation would serve as fallback via alternative mechanism. To avoid the performance concern of unalignment access, we
also
Quoted 4 lines
use the fallback implementation to handle the head and tail bytes if any, the main body is accelerated by Zbc extension.
This patch is tested on QEMU VM with the kernel CRC32 selftest.
Ideally we'd also have the results of some benchmarks, or at least a dynamic instruction count or something, but I don't suspect that the table-lookup would "win" over Zbc. The bigger question is whether we want three implementations, because I assume we want Zvbc, particularly since [1] says
Quoted 7 lines
"""
Zvbc is listed as a development option for use in other algorithms, and will become mandatory. Scalar Zbc is now listed as an expansion option, i.e., it will probably not become mandatory.
"""[1] https://github.com/riscv/riscv-profiles/blob/main/rva23-profile.adoc
I would collect instructions count change and include the info in the commit log. Regarding to the bigger question, I have some thoughts:
- It looks this question also stands for some other cases like lib/str*, which currently has been accelerated by Zbb-ext, but since the in-kernel RVV support has been enabled, we may also use RVV to accelerate the lib/str*.ALTERNATIVE_2 mechanism allows a second code patching on the same location. So two alternative versions for the same function can be supported.
- At this moment, I can't figure out how Zvbc can be used to better accelerate these crc32 APIs which take just one data stream as input. I have rough idea for a batched version API which takes multi data stream as input (a parallel implementation of below Zbc acceleration), but not for these 3 APIs here.
BTW, the vector "clmulr" insn is not listed in the Zvbc spec, but it's useful in below implementation.
https://github.com/riscv/riscv-crypto/blob/main/doc/vector/riscv-crypto-vector-zvbc.adoc
Anyway, if we come up with a Zvbc based optimization in future, then ALTERNATIVE_2 would help.
Quoted 3 lines
A few nits below.
Thanks for all the above & below comments. Will adopt most of the suggestions, except two, please check below.
Quoted 12 lines
Quoted 7 lines
Signed-off-by Xiao Wang <[email protected]>--- arch/riscv/Kconfig | 23 +++++ arch/riscv/lib/Makefile | 1 + arch/riscv/lib/crc32.c | 216++++++++++++++++++++++++++++++++++++++++
Quoted 4 lines
include/linux/crc32.h | 3 + 4 files changed, 243 insertions(+) create mode 100644 arch/riscv/lib/crc32.c
[...]
Quoted 8 lines
arch/riscv/lib/crc32.c line 84
Quoted 5 lines
arch/riscv/lib/crc32.c new file +5
-0+#if (BITS_PER_LONG ==64 ) + size_t len, u32 poly, u64 poly_qt, +#else + size_t len, u32 poly, u32 poly_qt, +#endifHow about creating a new type for
poly_qt, defined as u64 for xlen=64 and u32 for xlen=32 to avoid the #ifdef?
Would make it as "unsigned long", as David's comment.
Quoted 126 lines
Quoted 19 lines
arch/riscv/lib/crc32.c new file +18
-0+ fallback crc_fb) +{ +size_t offset, head_len, tail_len; +const unsigned long *p_ul; +unsigned long s; + +asm_volatile_goto (ALTERNATIVE ("j %l[legacy]" ,"nop" ,0 , +RISCV_ISA_EXT_ZBC ,1 ) + : : : : legacy); + +/* Handle the unalignment head. */ + offset = (unsigned long )p &OFFSET_MASK ; +if (offset) { + head_len =MIN (STEP - offset, len); + crc =crc_fb (crc, p, head_len); + len -= head_len; + p += head_len; + }arch/riscv/lib/crc32.c line 112
Quoted 10 lines
arch/riscv/lib/crc32.c new file +10
-0+ + tail_len = len &OFFSET_MASK ; + len = len >>STEP_ORDER ; + p_ul = (unsigned long *)p; + +for (int i =0 ; i < len; i++) { +#if (BITS_PER_LONG ==64 ) + s = (unsigned long )crc ^__cpu_to_le64 (*p_ul++); +/* We don't have a "clmulrh" insn, so use clmul + slli instead. +*/ need opening /* comment wing
Quoted 6 lines
arch/riscv/lib/crc32.c new file +6
-0+ asmvolatile (".option push\n" +".option arch,+zbc\n" +"clmul %0, %1, %2\n" +"slli %0, %0, 1\n" +"xor %0, %0, %1\n" + "clmulr %0, %0, %3\n"arch/riscv/lib/crc32.c line 128
Quoted 10 lines
arch/riscv/lib/crc32.c new file +10
-0+"srli %0, %0, 32\n" +".option pop\n" + : "=&r" (crc) + : "r" (s), +" r" (poly_qt), + "r" ((u64)poly << 32) + :); +#else + s = crc ^__cpu_to_le32 (*p_ul++); +/* We don't have a "clmulrh" insn, so use clmul + slli instead. also here
Quoted 4 lines
arch/riscv/lib/crc32.c new file +4
-0+*/ + asmvolatile (".option push\n" +".option arch,+zbc\n" + "clmul %0, %1, %2\n"arch/riscv/lib/crc32.c line 142
Quoted 10 lines
arch/riscv/lib/crc32.c new file +10
-0+"slli %0, %0, 1\n" +"xor %0, %0, %1\n" +"clmulr %0, %0, %3\n" +".option pop\n" + : "=&r" (crc) + : "r" (s), +" r" (poly_qt), + "r" (poly) + :); +#endif Instead of the #ifdef here, we could provide function wrappers for the asm which would be defined above in the first #ifdef ladder.
Quoted 4 lines
arch/riscv/lib/crc32.c new file +4
-0+ } + +/* Handle the tail bytes. */ +if (tail_len)arch/riscv/lib/crc32.c
Quoted 10 lines
arch/riscv/lib/crc32.c new file +10
-0+ crc =crc_fb (crc, (unsigned char const *)p_ul, tail_len); +return crc; + +legacy: +return crc_fb (crc, p, len); +} + +u32 __pure crc32_le (u32 crc,unsigned char const *p,size_t len) +{ + return crc32_le_generic(crc, p, len, CRC32_POLY_LE,
CRC32_POLY_QT_LE,Quoted 29 lines
arch/riscv/lib/crc32.c new file +29
-0+ crc32_le_base); +} + +u32 __pure __crc32c_le (u32 crc,unsigned char const *p,size_t len) +{ +return crc32_le_generic (crc, p, len,CRC32C_POLY_LE , +CRC32C_POLY_QT_LE , __crc32c_le_base); +} + +u32 __pure crc32_be (u32 crc,unsigned char const *p,size_t len) +{ +size_t offset, head_len, tail_len; +const unsigned long *p_ul; +unsigned long s; + +asm_volatile_goto (ALTERNATIVE ("j %l[legacy]" ,"nop" ,0 , +RISCV_ISA_EXT_ZBC ,1 ) + : : : : legacy); + +/* Handle the unalignment head. */ + offset = (unsigned long )p &OFFSET_MASK ; +if (offset) { + head_len =MIN (STEP - offset, len); + crc =crc32_be_base (crc, p, head_len); + len -= head_len; + p += head_len; + } + + tail_len = len &OFFSET_MASK ;arch/riscv/lib/crc32.c line 195
Quoted 10 lines
arch/riscv/lib/crc32.c new file +10
-0+ len = len >>STEP_ORDER ; + p_ul = (unsigned long *)p; + +for (int i =0 ; i < len; i++) { +#if (BITS_PER_LONG ==64 ) + s = (unsigned long )crc <<32 ; + s ^=__cpu_to_be64 (*p_ul++); +#else + s = crc ^__cpu_to_be32 (*p_ul++); +#endif Could write the above without #ifdef with
Quoted 5 lines
if (IS_ENABLED(CONFIG_64BIT)) { ... } else { ...}
I got a warning for riscv32 build with this change, gcc v12.2.0 ../arch/riscv/lib/crc32.c:191:40: warning: left shift count >= width of type [-Wshift-count-overflow] It looks compiler takes the always-impossible code branch into consideration.
BRs,
Xiao