Skip to contentSkip to conversation

lib: crc32: Greatly shrink CRC combining code

PATCH In review George Spelvin 2 participants 7 messages May 30, 2014 – Jun 4, 2014

Subsystems (2)
lore
Share & tools
lore
#0 lore raw

PATCH 1/3 lib: crc32: Greatly shrink CRC combining code

There's no need for a full 32x32 matrix, when rows before the last are just shifted copies of the rows after them.

There's still room for improvement (especially on X86 processors with CRC32 and PCLMUL instructions), but this is a large step in the right direction.

The internal primitive is now called crc32_generic_shift and takes one less argument; the XOR with crc2 is done in inline wrappers.

---
This is the significant patch; there other two patches are minor cleanups that I did while in the area.

Tested extensively in user-space (the "power" variable is identical to the last row of the current even/odd matrix in the previous code) and with CONFIG_CRC32_SELFTEST:

[    0.587152] crc32: CRC_LE_BITS = 64, CRC_BE BITS = 64
[    0.587186] crc32: self tests passed, processed 225944 bytes in 115727 nsec
[    0.587341] crc32c: CRC_LE_BITS = 64
[    0.587373] crc32c: self tests passed, processed 225944 bytes in 59505 nsec
[    0.596827] crc32_combine: 8373 self tests passed
[    0.606259] crc32c_combine: 8373 self tests passed

Code shrunk; comments increased to match.
Pulling 2x32x32 bits = 256 bytes off the stack is a nice bonus.

 include/linux/crc32.h |  12 ++++-
 lib/crc32.c           | 142 +++++++++++++++++++++++---------------------------
 2 files changed, 76 insertions(+), 78 deletions(-)
include/linux/crc32.h +10 -2
index 7d275c4f..bcb8e9d3 100644
@@ -29,7 +29,11 @@ extern u32  crc32_be(u32 crc, unsigned char const *p, size_t len);
  * 	   with the same initializer as crc1, and crc2 seed was 0. See
  * 	   also crc32_combine_test().
  */
-extern u32  crc32_le_combine(u32 crc1, u32 crc2, size_t len2);
+u32  crc32_le_shift(u32 crc, size_t len) __attribute_const__;
+static inline u32  crc32_le_combine(u32 crc1, u32 crc2, size_t len2)
+{
+	return crc32_le_shift(crc1, len2) ^ crc2;
+}
 
 extern u32  __crc32c_le(u32 crc, unsigned char const *p, size_t len);
 
@@ -51,7 +55,11 @@ extern u32  __crc32c_le(u32 crc, unsigned char const *p, size_t len);
  * 	   seeded with the same initializer as crc1, and crc2 seed
  * 	   was 0. See also crc32c_combine_test().
  */
-extern u32  __crc32c_le_combine(u32 crc1, u32 crc2, size_t len2);
+u32  __crc32c_le_shift(u32 crc, size_t len) __attribute_const__;
+static inline u32  __crc32c_le_combine(u32 crc1, u32 crc2, size_t len2)
+{
+	return __crc32c_le_shift(crc1, len2) ^ crc2;
+}
 
 #define crc32(seed, data, length)  crc32_le(seed, (unsigned char const *)(data), length)
 
lib/crc32.c +66 -76

165 lines not on this page · raw message

Signature · 1 line
1.9.2
#1 lore raw

PATCH 2/3 lib: crc32: mark test data __initconst

Quoted 1 line

From 1ecab5281e3cfc8c2a61648410c8b25ba2654fcb Mon Sep 17 00:00:00 2001

From: George Spelvin <[email protected]>
Date: Thu, 29 May 2014 00:08:03 -0400
Subject: [PATCH 2/3] lib: crc32: mark test data __initconst

So it gets discarded after the selftest.

---
This is the patch I started with, when I was looking for lib/ self-test code to emulate for my still-pending glob.c code. But curiosity about the combine code led me notice problems with it, and to study the arch/x86/crypto code, where I also have a proposed patch.

Aren't tangents fun?

 lib/crc32.c | 4 ++--
 1 file changed, 2 insertions(+), 2 deletions(-)
lib/crc32.c +2 -2
index a4a576f3..977167d6 100644
@@ -341,7 +341,7 @@ EXPORT_SYMBOL(crc32_be);
 #ifdef CONFIG_CRC32_SELFTEST
 
 /* 4096 random bytes */
-static u8 __attribute__((__aligned__(8))) test_buf[] =
+static u8 const __aligned(8) test_buf[] __initconst =
 {
 	0x5b, 0x85, 0x21, 0xcb, 0x09, 0x68, 0x7d, 0x30,
 	0xc7, 0x69, 0xd7, 0x30, 0x92, 0xde, 0x59, 0xe4,
@@ -865,7 +865,7 @@ static struct crc_test {
 	u32 crc_le;	/* expected crc32_le result */
 	u32 crc_be;	/* expected crc32_be result */
 	u32 crc32c_le;	/* expected crc32c_le result */
-} test[] =
+} const test[] __initconst =
 {
 	{0x674bf11d, 0x00000038, 0x00000542, 0x0af6d466, 0xd8b6e4c1, 0xf6e93d6c},
 	{0x35c672c6, 0x0000003a, 0x000001aa, 0xc6d3dfba, 0x28aaf3ad, 0x0fe92aca},
Signature · 1 line
1.9.2
#2 lore raw

PATCH 3/3 lib: crc32: Add some additional __pure annotations

In reply to George Spelvin

In case they help the compiler.

---
As long as I'm messing with it. I also have a large patch to do this to a number of lib/ headers if anyone wants.

Redundant "extern" removed to keep things within 80 columns.

 include/linux/crc32.h | 6 +++---
 lib/crc32.c           | 2 +-
 2 files changed, 4 insertions(+), 4 deletions(-)
include/linux/crc32.h +3 -3
index bcb8e9d3..25e57f3a 100644
@@ -8,8 +8,8 @@
 #include <linux/types.h>
 #include <linux/bitrev.h>
 
-extern u32  crc32_le(u32 crc, unsigned char const *p, size_t len);
-extern u32  crc32_be(u32 crc, unsigned char const *p, size_t len);
+u32  crc32_le(u32 crc, unsigned char const *p, size_t len) __pure;
+u32  crc32_be(u32 crc, unsigned char const *p, size_t len) __pure;
 
 /**
  * crc32_le_combine - Combine two crc32 check values into one. For two
@@ -35,7 +35,7 @@ static inline u32  crc32_le_combine(u32 crc1, u32 crc2, size_t len2)
 	return crc32_le_shift(crc1, len2) ^ crc2;
 }
 
-extern u32  __crc32c_le(u32 crc, unsigned char const *p, size_t len);
+u32  __crc32c_le(u32 crc, unsigned char const *p, size_t len) __pure;
 
 /**
  * __crc32c_le_combine - Combine two crc32c check values into one. For two
lib/crc32.c +1 -1
index 977167d6..cf0c8e08 100644
@@ -54,7 +54,7 @@ MODULE_LICENSE("GPL");
 #if CRC_LE_BITS > 8 || CRC_BE_BITS > 8
 
 /* implements slicing-by-4 or slicing-by-8 algorithm */
-static inline u32
+static inline u32 __pure
 crc32_body(u32 crc, unsigned char const *buf, size_t len, const u32 (*tab)[256])
 {
 # ifdef __LITTLE_ENDIAN
Signature · 1 line
1.9.2
#3 lore raw
In reply to George Spelvin

Sorry for the late answer, this slipped somehow through ...

I think you might want to cc Andrew Morton <[email protected]> to let this go via akpm's tree for misc changes, perhaps?

The work from my side went via Dave's net-next tree as it had some follow-up SCTP work that depended on these below bits.

No objections from my side if you really want this to go through <[email protected]>, though.

Anyway, some more comments inline:

Quoted 26 lines · George Spelvin

There's no need for a full 32x32 matrix, when rows before the last are just shifted copies of the rows after them.

There's still room for improvement (especially on X86 processors with CRC32 and PCLMUL instructions), but this is a large step in the right direction.

The internal primitive is now called crc32_generic_shift and takes one less argument; the XOR with crc2 is done in inline wrappers.

---
This is the significant patch; there other two patches are minor cleanups that I did while in the area.

Tested extensively in user-space (the "power" variable is identical to the last row of the current even/odd matrix in the previous code) and with CONFIG_CRC32_SELFTEST:

[    0.587152] crc32: CRC_LE_BITS = 64, CRC_BE BITS = 64
[    0.587186] crc32: self tests passed, processed 225944 bytes in 115727 nsec
[    0.587341] crc32c: CRC_LE_BITS = 64
[    0.587373] crc32c: self tests passed, processed 225944 bytes in 59505 nsec
[    0.596827] crc32_combine: 8373 self tests passed
[    0.606259] crc32c_combine: 8373 self tests passed
Quoted 2 lines

Code shrunk; comments increased to match.
Pulling 2x32x32 bits = 256 bytes off the stack is a nice bonus.

Looks good to me! Do you have any performance numbers to share?

Some very minor nit-picking:

Quoted 9 lines
  include/linux/crc32.h |  12 ++++-
  lib/crc32.c           | 142 +++++++++++++++++++++++---------------------------
  2 files changed, 76 insertions(+), 78 deletions(-)
include/linux/crc32.h +0 -0
index 7d275c4f..bcb8e9d3 100644

include/linux/crc32.h extern u32 crc32_be(u32 crc, unsigned char const *p, size_t len); · line 32

Quoted 5 lines
include/linux/crc32.h +1 -1
@@ -29,7 +29,11 @@ extern u32  crc32_be(u32 crc, unsigned char const *p, size_t len);
   * 	   with the same initializer as crc1, and crc2 seed was 0. See
   * 	   also crc32_combine_test().
   */
-extern u32  crc32_le_combine(u32 crc1, u32 crc2, size_t len2);
+u32  crc32_le_shift(u32 crc, size_t len) __attribute_const__;

Perhaps a newline here.

include/linux/crc32.h extern u32 __crc32c_le(u32 crc, unsigned char const *p, size_t len); · line 58

Quoted 13 lines
include/linux/crc32.h +5 -1
+static inline u32  crc32_le_combine(u32 crc1, u32 crc2, size_t len2)
+{
+	return crc32_le_shift(crc1, len2) ^ crc2;
+}
 
  extern u32  __crc32c_le(u32 crc, unsigned char const *p, size_t len);
 
@@ -51,7 +55,11 @@ extern u32  __crc32c_le(u32 crc, unsigned char const *p, size_t len);
   * 	   seeded with the same initializer as crc1, and crc2 seed
   * 	   was 0. See also crc32c_combine_test().
   */
-extern u32  __crc32c_le_combine(u32 crc1, u32 crc2, size_t len2);
+u32  __crc32c_le_shift(u32 crc, size_t len) __attribute_const__;

Ditto. Or, put both *_shift() helper signatures before the crc32_le_combine kdoc comment.

Quoted 9 lines
include/linux/crc32.h +4 -0
+static inline u32  __crc32c_le_combine(u32 crc1, u32 crc2, size_t len2)
+{
+	return __crc32c_le_shift(crc1, len2) ^ crc2;
+}
 
  #define crc32(seed, data, length)  crc32_le(seed, (unsigned char const *)(data), length)
 
lib/crc32.c +0 -0
index 70f00ca5..a4a576f3 100644

...

lib/crc32.c u32 __pure __crc32c_le(u32 crc, unsigned char const *p, size_t len) · line 231

Quoted 7 lines
lib/crc32.c +5 -1
-u32 __pure __crc32c_le_combine(u32 crc1, u32 crc2, size_t len2)
+/**
+ * crc32_generic_shift - Append len 0 bytes to crc, in logarithmic time
+ * @crc: The original little-endian CRC (i.e. lsbit is x^31 coefficient)
+ * @len: The number of bytes.  @crc is multiplied by x^(8*@len)
+ # @polynomial: The modulus used to reduce the result to 32 bits.

^^ seems this should have been a '*'

lib/crc32.c u32 __pure __crc32c_le(u32 crc, unsigned char const *p, size_t len) · line 240

Quoted 9 lines

+ *
+ * It's possible to parallelize CRC computations by computing a CRC
+ * over separate ranges of a buffer, then summing them.
+ * This shifts the given CRC by 8*len bits (i.e. produces the same effect
+ * as appending len bytes of zero to the data), in time proportional
+ * to log(len).
+ */

lib/crc32.c +2 -0
+static u32 __attribute_const__ crc32_generic_shift(u32 crc, size_t len,
+				 u32 polynomial)

u32 polynomial is not correctly aligned to the opening '(' from the previous line.

lib/crc32.c u32 __pure __crc32c_le(u32 crc, unsigned char const *p, size_t len) · line 245

Quoted 6 lines
  {
lib/crc32.c +4 -1
-	return crc32_generic_combine(crc1, crc2, len2, CRC32C_POLY_LE);
+	u32 power = polynomial;	/* CRC of x^32 */
+	int i;
+
+	/* Shift up to 32 bits in the simple linear way */

...

The other two patches are fine, imho. Thanks George! :)

#4 lore raw

Thanks for the nitpicks!

Quoted 2 lines

I think you might want to cc Andrew Morton <[email protected]> to let this go via akpm's tree for misc changes, perhaps?

I don't care, but akpm is fine by me. I'll send out a v2 after I resolve one minor point with you; see below.

Once that's done, may I add a Reviewed-by: or Acked-by: line from you?

Quoted 1 line

Looks good to me! Do you have any performance numbers to share?

Actually, I didn't bother benchmarking it because the improvement was so obvious, but here's a quick test showing a 35.5x performance gain.

     Old       New      Delta
  0: 83005684  2314192 (-80691492)
  1: 82730196  2313836 (-80416360)
  2: 82805636  2312736 (-80492900)
  3: 82648160  2344304 (-80303856)
  4: 82531928  2314940 (-80216988)
  5: 82669440  2312976 (-80356464)
  6: 82528792  2313984 (-80214808)
  7: 82415116  2313796 (-80101320)
  8: 82451620  2314000 (-80137620)
  9: 82811052  2329708 (-80481344)
 10: 82903344  2311120 (-80592224)
 11: 82549032  2313540 (-80235492)
 12: 82564660  2330260 (-80234400)
 13: 82289788  2312972 (-79976816)
 14: 82535828  2312036 (-80223792)
 15: 82664040  2313284 (-80350756)
 16: 82629476  2309744 (-80319732)
 17: 82806812  2329628 (-80477184)
 18: 82379284  2312876 (-80066408)
 19: 82483400  2313004 (-80170396)
 20: 82651232  2314244 (-80336988)
 21: 82327508  2330456 (-79997052)
 22: 82641324  2330664 (-80310660)
 23: 82538192  2314024 (-80224168)
MIN: 82289788  2309744 (-79980044)

Here's the test loop. Although it's subject to compiler rearrangements, I tried to charge the loop overhead to the new code.

static void
do_test(uint64_t times[2])

{
	uint32_t crc0 = 1, crc1 = 1;
	uint64_t t0, t1, sum0 = 0, sum1 = 0;
	int i;

	t1 = t0 = rdtsc();
	for (i = 1024; i < 2048; i++) {
		sum0 += t1;
		crc0 = crc32_generic_shift(crc0, i, CRC32C_POLY_LE);
		sum1 += rdtsc();
		crc1 = crc32_generic_combine(crc1, 0, i, CRC32C_POLY_LE);
		t1 = rdtsc();
	}
	times[0] = sum0 + t1 - sum1 - t0;	// Old code
	times[1] = sum1 - sum0;			// New code
	if (crc0 != crc1)
		printf("Mismatch!  %08x != %08x\n", crc0, crc1);
}

It's possible to do a bit better with more effort (exploiting the precomputed CRC tables for modular reduction) but this fruit was hanging *so* low I couldn't resist grabbing it.

Quoted 4 lines

include/linux/crc32.h extern u32 crc32_be(u32 crc, unsigned char const *p, size_t len); · line 32

Quoted 2 lines
include/linux/crc32.h +1 -1
-extern u32  crc32_le_combine(u32 crc1, u32 crc2, size_t len2);
+u32  crc32_le_shift(u32 crc, size_t len) __attribute_const__;

Perhaps a newline here.

Question: where do you think a newline should go? It's not obvious to me. My style has been to keep as much of a declaration on one line as possible so "git grep <function> include" is as informative as possible.

Quoted 5 lines

include/linux/crc32.h extern u32 __crc32c_le(u32 crc, unsigned char const *p, size_t len); · line 58

Quoted 2 lines
include/linux/crc32.h +1 -1
-extern u32  __crc32c_le_combine(u32 crc1, u32 crc2, size_t len2);
+u32  __crc32c_le_shift(u32 crc, size_t len) __attribute_const__;

Ditto. Or, put both *_shift() helper signatures before the crc32_le_combine kdoc comment.

Um, same basic question. I agree that putting a declaration between the kdoc and the function is strange, but that doesn't seem to be what you're commenting in...

Now that I've gotten an ack, I'm happy to be more aggressive about tweaking comments. I just wanted to focus the diff on the code changes.

Quoted 7 lines
Quoted 5 lines

+/**
+ * crc32_generic_shift - Append len 0 bytes to crc, in logarithmic time
+ * @crc: The original little-endian CRC (i.e. lsbit is x^31 coefficient)
+ * @len: The number of bytes. @crc is multiplied by x^(8*@len)
+ # @polynomial: The modulus used to reduce the result to 32 bits.

^^ seems this should have been a '*'

Yes, obviously. Thanks for catching that.

Quoted 4 lines

lib/crc32.c u32 __pure __crc32c_le(u32 crc, unsigned char const *p, size_t len) · line 240

Quoted 2 lines
lib/crc32.c +2 -0
+static u32 __attribute_const__ crc32_generic_shift(u32 crc, size_t len,
+				 u32 polynomial)

u32 polynomial is not correctly aligned to the opening '(' from the previous line.

Thanks again.

#5 lore raw
Quoted 9 lines · George Spelvin

Thanks for the nitpicks!

Quoted 2 lines

I think you might want to cc Andrew Morton <[email protected]> to let this go via akpm's tree for misc changes, perhaps?

I don't care, but akpm is fine by me. I'll send out a v2 after I resolve one minor point with you; see below.

Once that's done, may I add a Reviewed-by: or Acked-by: line from you?

Yes, feel free to add my Reviewed-by tag and keep me in Cc.

Quoted 4 lines
Quoted 1 line

Looks good to me! Do you have any performance numbers to share?

Actually, I didn't bother benchmarking it because the improvement was so obvious, but here's a quick test showing a 35.5x performance gain.

That's great!

...

Quoted 8 lines
Quoted 4 lines

include/linux/crc32.h extern u32 crc32_be(u32 crc, unsigned char const *p, size_t len); · line 32

Quoted 2 lines
include/linux/crc32.h +1 -1
-extern u32  crc32_le_combine(u32 crc1, u32 crc2, size_t len2);
+u32  crc32_le_shift(u32 crc, size_t len) __attribute_const__;

Perhaps a newline here.

Question: where do you think a newline should go? It's not obvious to me. My style has been to keep as much of a declaration on one line as possible so "git grep <function> include" is as informative as possible.

It's just nit, but since you've asked, end result like this:

--snip--
u32 crc32_le_shift(u32 crc, size_t len) __attribute_const__;

static inline u32 crc32_le_combine(u32 crc1, u32 crc2, size_t len2)

{
	return crc32_le_shift(crc1, len2) ^ crc2;
}

--snap--

Quoted 2 lines

Now that I've gotten an ack, I'm happy to be more aggressive about tweaking comments. I just wanted to focus the diff on the code changes.

Sounds good, thanks!

Quoted 16 lines
Quoted 7 lines
Quoted 5 lines

+/**
+ * crc32_generic_shift - Append len 0 bytes to crc, in logarithmic time
+ * @crc: The original little-endian CRC (i.e. lsbit is x^31 coefficient)
+ * @len: The number of bytes. @crc is multiplied by x^(8*@len)
+ # @polynomial: The modulus used to reduce the result to 32 bits.

^^ seems this should have been a '*'

Yes, obviously. Thanks for catching that.

Quoted 4 lines

lib/crc32.c u32 __pure __crc32c_le(u32 crc, unsigned char const *p, size_t len) · line 240

Quoted 2 lines
lib/crc32.c +2 -0
+static u32 __attribute_const__ crc32_generic_shift(u32 crc, size_t len,
+				 u32 polynomial)

u32 polynomial is not correctly aligned to the opening '(' from the previous line.

Thanks again.

#6 lore raw
Quoted 8 lines
Quoted 5 lines
Quoted 1 line

Perhaps a newline here.

Question: where do you think a newline should go? It's not obvious to me. My style has been to keep as much of a declaration on one line as possible so "git grep <function> include" is as informative as possible.

It's just nit, but since you've asked, end result like this:

Quoted 8 lines

--snip--
u32 crc32_le_shift(u32 crc, size_t len) __attribute_const__;

static inline u32 crc32_le_combine(u32 crc1, u32 crc2, size_t len2)

{
	return crc32_le_shift(crc1, len2) ^ crc2;
}

--snap--

Ah, got it! I couldn't figure out where it would make sense to insert a newline into the middle of one line, breaking it into two. Adding a blank line makes sense, and makes your other comment make sense.

Good suggestion; I'll do it.