[PATCH 0/4] add crc64 calculation as kernel library

[PATCH 0/4] add crc64 calculation as kernel library

[Coly Li]

This patch set adds basic implementation of crc64 calculation as Linux
kernel library. Since bcache already does crc64 by itself, this patch
set also modifies bcache code to use the new crc64 library routine.

bcache uses crc64 as storage checksum, if a change of crc lib routines
results an inconsistent result, the unmatched checksum may make bcache
'think' the on-disk is corrupted, such change should be avoided or
detected as early as possible. Therefore the last patch in this series
adds a crc test framework, to check consistency of different calculations.

Coly Li

Cc: Andy Shevchenko <andriy.shevchenko@linux.intel.com>
Cc: Greg Kroah-Hartman <gregkh@linuxfoundation.org>
Cc: Luis R. Rodriguez <mcgrof@suse.com>
Cc: Linus Torvalds <torvalds@linux-foundation.org>
Cc: Thomas Gleixner <tglx@linutronix.de>
Cc: Michael Lyle <mlyle@lyle.org>
Cc: Kent Overstreet <kent.overstreet@gmail.com>
Cc: Kate Stewart <kstewart@linuxfoundation.org>
---
Andy Shevchenko (1):
  lib/crc64: add crc64 option to lib/Kconfig

Coly Li (3):
  lib: add crc64 calculation routines
  bcache: use routines from lib/crc64.c for CRC64 calculation
  lib/test_crc: Add test cases for crc calculation

 drivers/md/bcache/bcache.h  |   7 +-
 drivers/md/bcache/btree.c   |   2 +-
 drivers/md/bcache/request.c |   2 +-
 drivers/md/bcache/super.c   |   5 +-
 drivers/md/bcache/util.c    | 131 ----------------------------------
 drivers/md/bcache/util.h    |   5 +-
 include/linux/crc64.h       |  15 ++++
 lib/.gitignore              |   2 +
 lib/Kconfig                 |   8 +++
 lib/Kconfig.debug           |  11 +++
 lib/Makefile                |  12 ++++
 lib/crc64.c                 |  71 +++++++++++++++++++
 lib/gen_crc64table.c        |  76 ++++++++++++++++++++
 lib/test_crc.c              | 136 ++++++++++++++++++++++++++++++++++++
 14 files changed, 341 insertions(+), 142 deletions(-)
 create mode 100644 include/linux/crc64.h
 create mode 100644 lib/crc64.c
 create mode 100644 lib/gen_crc64table.c
 create mode 100644 lib/test_crc.c

-- 
2.17.1

[PATCH 1/4] lib/crc64: add crc64 option to lib/Kconfig

[Coly Li]

From: Andy Shevchenko <andriy.shevchenko@linux.intel.com>

This patch adds crc64 option entry in lib/Kconfig. This patch is part of
a patch originally written by Andy Shevchenko, Coly Li cherry-picks it
and compose the commit log for a re-written crc64 source code.

Signed-off-by: Andy Shevchenko <andriy.shevchenko@linux.intel.com>
Signed-off-by: Coly Li <colyli@suse.de>
Cc: Greg Kroah-Hartman <gregkh@linuxfoundation.org>
Cc: Luis R. Rodriguez <mcgrof@suse.com>
Cc: Linus Torvalds <torvalds@linux-foundation.org>
Cc: Thomas Gleixner <tglx@linutronix.de>
Cc: Kate Stewart <kstewart@linuxfoundation.org>
---
 lib/Kconfig | 8 ++++++++
 1 file changed, 8 insertions(+)

diff --git a/lib/Kconfig b/lib/Kconfig
index 706836ec314d..4059df9ec4c7 100644
--- a/lib/Kconfig
+++ b/lib/Kconfig
@@ -170,6 +170,14 @@ config CRC32_BIT
 
 endchoice
 
+config CRC64
+	tristate "CRC64 functions"
+	help
+	  This option is provided for the case where no in-kernel-tree
+	  modules require CRC64 functions, but a module built outside
+	  the kernel tree does. Such modules that use library CRC64
+	  functions require M he
+
 config CRC4
 	tristate "CRC4 functions"
 	help
-- 
2.17.1

Re: [PATCH 1/4] lib/crc64: add crc64 option to lib/Kconfig

[Randy Dunlap]

On 07/16/2018 09:55 AM, Coly Li wrote:
> From: Andy Shevchenko <andriy.shevchenko@linux.intel.com>
> 
> This patch adds crc64 option entry in lib/Kconfig. This patch is part of
> a patch originally written by Andy Shevchenko, Coly Li cherry-picks it
> and compose the commit log for a re-written crc64 source code.
> 
> Signed-off-by: Andy Shevchenko <andriy.shevchenko@linux.intel.com>
> Signed-off-by: Coly Li <colyli@suse.de>
> Cc: Greg Kroah-Hartman <gregkh@linuxfoundation.org>
> Cc: Luis R. Rodriguez <mcgrof@suse.com>
> Cc: Linus Torvalds <torvalds@linux-foundation.org>
> Cc: Thomas Gleixner <tglx@linutronix.de>
> Cc: Kate Stewart <kstewart@linuxfoundation.org>
> ---
>  lib/Kconfig | 8 ++++++++
>  1 file changed, 8 insertions(+)
> 
> diff --git a/lib/Kconfig b/lib/Kconfig
> index 706836ec314d..4059df9ec4c7 100644
> --- a/lib/Kconfig
> +++ b/lib/Kconfig
> @@ -170,6 +170,14 @@ config CRC32_BIT
>  
>  endchoice
>  
> +config CRC64
> +	tristate "CRC64 functions"
> +	help
> +	  This option is provided for the case where no in-kernel-tree
> +	  modules require CRC64 functions, but a module built outside
> +	  the kernel tree does. Such modules that use library CRC64
> +	  functions require M he

eh?  missing something here.

> +
>  config CRC4
>  	tristate "CRC4 functions"
>  	help
> 


-- 
~Randy

Re: [PATCH 1/4] lib/crc64: add crc64 option to lib/Kconfig

[Coly Li]

On 2018/7/17 1:48 AM, Randy Dunlap wrote:
> On 07/16/2018 09:55 AM, Coly Li wrote:
>> From: Andy Shevchenko <andriy.shevchenko@linux.intel.com>
>>
>> This patch adds crc64 option entry in lib/Kconfig. This patch is part of
>> a patch originally written by Andy Shevchenko, Coly Li cherry-picks it
>> and compose the commit log for a re-written crc64 source code.
>>
>> Signed-off-by: Andy Shevchenko <andriy.shevchenko@linux.intel.com>
>> Signed-off-by: Coly Li <colyli@suse.de>
>> Cc: Greg Kroah-Hartman <gregkh@linuxfoundation.org>
>> Cc: Luis R. Rodriguez <mcgrof@suse.com>
>> Cc: Linus Torvalds <torvalds@linux-foundation.org>
>> Cc: Thomas Gleixner <tglx@linutronix.de>
>> Cc: Kate Stewart <kstewart@linuxfoundation.org>
>> ---
>>  lib/Kconfig | 8 ++++++++
>>  1 file changed, 8 insertions(+)
>>
>> diff --git a/lib/Kconfig b/lib/Kconfig
>> index 706836ec314d..4059df9ec4c7 100644
>> --- a/lib/Kconfig
>> +++ b/lib/Kconfig
>> @@ -170,6 +170,14 @@ config CRC32_BIT
>>  
>>  endchoice
>>  
>> +config CRC64
>> +	tristate "CRC64 functions"
>> +	help
>> +	  This option is provided for the case where no in-kernel-tree
>> +	  modules require CRC64 functions, but a module built outside
>> +	  the kernel tree does. Such modules that use library CRC64
>> +	  functions require M he
> 

Hi Randy,

> eh?  missing something here.
> 

Fix it in v2 series. Thanks.

Coly Li

[PATCH 2/4] lib: add crc64 calculation routines

[Coly Li]

This patch adds the re-write crc64 calculation routines for Linux kernel.
The CRC64 polynomical arithmetic follows ECMA-182 specification, inspired
by CRC paper of Dr. Ross N. Williams
(see http://www.ross.net/crc/download/crc_v3.txt) and other public domain
implementations.

All the changes work in this way,
- When Linux kernel is built, host program lib/gen_crc64table.c will be
  compiled to lib/gen_crc64table and executed.
- The output of gen_crc64table execution is an array called as lookup
  table (a.k.a POLY 0x42f0e1eba9ea369) which contain 256 64bits-long
  numbers, this talbe is dumped into header file lib/crc64table.h.
- Then the header file is included by lib/crc64.c for normal 64bit crc
  calculation.
- Function declaration of the crc64 calculation routines is placed in
  include/linux/crc64.h

Signed-off-by: Coly Li <colyli@suse.de>
Cc: Greg Kroah-Hartman <gregkh@linuxfoundation.org>
Cc: Andy Shevchenko <andriy.shevchenko@linux.intel.com>
Cc: Michael Lyle <mlyle@lyle.org>
Cc: Kent Overstreet <kent.overstreet@gmail.com>
Cc: Luis R. Rodriguez <mcgrof@suse.com>
Cc: Linus Torvalds <torvalds@linux-foundation.org>
Cc: Thomas Gleixner <tglx@linutronix.de>
Cc: Kate Stewart <kstewart@linuxfoundation.org>
---
 include/linux/crc64.h | 15 +++++++++
 lib/.gitignore        |  2 ++
 lib/Makefile          | 11 +++++++
 lib/crc64.c           | 71 +++++++++++++++++++++++++++++++++++++++
 lib/gen_crc64table.c  | 77 +++++++++++++++++++++++++++++++++++++++++++
 5 files changed, 176 insertions(+)
 create mode 100644 include/linux/crc64.h
 create mode 100644 lib/crc64.c
 create mode 100644 lib/gen_crc64table.c

diff --git a/include/linux/crc64.h b/include/linux/crc64.h
new file mode 100644
index 000000000000..cbd10a47d861
--- /dev/null
+++ b/include/linux/crc64.h
@@ -0,0 +1,15 @@
+/* SPDX-License-Identifier: GPL-2.0 */
+/*
+ * crc64.h
+ *
+ * See lib/crc64.c for the related specification and polynomical arithmetic.
+ */
+#ifndef _LINUX_CRC64_H
+#define _LINUX_CRC64_H
+
+#include <linux/types.h>
+
+__le64 crc64_le_update(__le64 crc, const void *_p, size_t len);
+__le64 crc64_le(const void *p, size_t len);
+__le64 crc64_le_bch(const void *p, size_t len);
+#endif /* _LINUX_CRC64_H */
diff --git a/lib/.gitignore b/lib/.gitignore
index 09aae85418ab..f2a39c9e5485 100644
--- a/lib/.gitignore
+++ b/lib/.gitignore
@@ -2,5 +2,7 @@
 # Generated files
 #
 gen_crc32table
+gen_crc64table
 crc32table.h
+crc64table.h
 oid_registry_data.c
diff --git a/lib/Makefile b/lib/Makefile
index 90dc5520b784..40c215181687 100644
--- a/lib/Makefile
+++ b/lib/Makefile
@@ -102,6 +102,7 @@ obj-$(CONFIG_CRC16)	+= crc16.o
 obj-$(CONFIG_CRC_T10DIF)+= crc-t10dif.o
 obj-$(CONFIG_CRC_ITU_T)	+= crc-itu-t.o
 obj-$(CONFIG_CRC32)	+= crc32.o
+obj-$(CONFIG_CRC64)     += crc64.o
 obj-$(CONFIG_CRC32_SELFTEST)	+= crc32test.o
 obj-$(CONFIG_CRC4)	+= crc4.o
 obj-$(CONFIG_CRC7)	+= crc7.o
@@ -215,7 +216,9 @@ obj-$(CONFIG_FONT_SUPPORT) += fonts/
 obj-$(CONFIG_PRIME_NUMBERS) += prime_numbers.o
 
 hostprogs-y	:= gen_crc32table
+hostprogs-y	+= gen_crc64table
 clean-files	:= crc32table.h
+clean-files	+= crc64table.h
 
 $(obj)/crc32.o: $(obj)/crc32table.h
 
@@ -225,6 +228,14 @@ quiet_cmd_crc32 = GEN     $@
 $(obj)/crc32table.h: $(obj)/gen_crc32table
 	$(call cmd,crc32)
 
+$(obj)/crc64.o: $(obj)/crc64table.h
+
+quiet_cmd_crc64 = GEN     $@
+      cmd_crc64 = $< > $@
+
+$(obj)/crc64table.h: $(obj)/gen_crc64table
+	$(call cmd,crc64)
+
 #
 # Build a fast OID lookip registry from include/linux/oid_registry.h
 #
diff --git a/lib/crc64.c b/lib/crc64.c
new file mode 100644
index 000000000000..03f078303bd3
--- /dev/null
+++ b/lib/crc64.c
@@ -0,0 +1,71 @@
+// SPDX-License-Identifier: GPL-2.0
+/*
+ * Normal 64bit CRC calculation.
+ *
+ * This is a basic crc64 implementation following ECMA-182 specification,
+ * which can be found from,
+ * http://www.ecma-international.org/publications/standards/Ecma-182.htm
+ *
+ * Dr. Ross N. Williams has a great document to introduce the idea of CRC
+ * algorithm, here the CRC64 code is also inspired by the table-driven
+ * algorithm and detail example from this paper. This paper can be found
+ * from,
+ * http://www.ross.net/crc/download/crc_v3.txt
+ *
+ * crc64table_le[256] is the lookup table of a table-driver 64bit CRC
+ * calculation, which is generated by gen_crc64table.c in kernel build
+ * time. The polynomial of crc64 arithmetic is from ECMA-182 specification
+ * as well, which is defined as,
+ *
+ * x^64 + x^62 + x^57 + x^55 + x^54 + x^53 + x^52 + x^47 + x^46 + x^45 +
+ * x^40 + x^39 + x^38 + x^37 + x^35 + x^33 + x^32 + x^31 + x^29 + x^27 +
+ * x^24 + x^23 + x^22 + x^21 + x^19 + x^17 + x^13 + x^12 + x^10 + x^9 +
+ * x^7 + x^4 + x + 1
+ *
+ * Copyright 2018 SUSE Linux.
+ *   Author: Coly Li <colyli@suse.de>
+ *
+ */
+
+#include <linux/module.h>
+#include <uapi/linux/types.h>
+#include "crc64table.h"
+
+MODULE_DESCRIPTION("CRC64 calculations");
+MODULE_LICENSE("GPL");
+
+__le64 crc64_le_update(__le64 crc, const void *_p, size_t len)
+{
+	size_t i, t;
+
+	const unsigned char *p = _p;
+
+	for (i = 0; i < len; i++) {
+		t = ((crc >> 56) ^ (__le64)(*p++)) & 0xFF;
+		crc = crc64table_le[t] ^ (crc << 8);
+	}
+
+	return crc;
+}
+EXPORT_SYMBOL_GPL(crc64_le_update);
+
+__le64 crc64_le(const void *p, size_t len)
+{
+	__le64 crc = 0x0000000000000000ULL;
+
+	crc = crc64_le_update(crc, p, len);
+
+	return crc;
+}
+EXPORT_SYMBOL_GPL(crc64_le);
+
+/* For checksum calculation in drivers/md/bcache/ */
+__le64 crc64_le_bch(const void *p, size_t len)
+{
+	__le64 crc = 0xFFFFFFFFFFFFFFFFULL;
+
+	crc = crc64_le_update(crc, p, len);
+
+	return (crc ^ 0xFFFFFFFFFFFFFFFFULL);
+}
+EXPORT_SYMBOL_GPL(crc64_le_bch);
diff --git a/lib/gen_crc64table.c b/lib/gen_crc64table.c
new file mode 100644
index 000000000000..5f292f287498
--- /dev/null
+++ b/lib/gen_crc64table.c
@@ -0,0 +1,77 @@
+// SPDX-License-Identifier: GPL-2.0
+/*
+ * Generate lookup table for the talbe-driven CRC64 calculation.
+ *
+ * gen_crc64table is executed in kernel build time and generates
+ * lib/crc64table.h. This header is included by lib/crc64.c for
+ * the table-driver CRC64 calculation.
+ *
+ * See lib/crc64.c for more information about which specification
+ * and polynomical arithmetic that gen_crc64table.c follows to
+ * generate the lookup table.
+ *
+ * Copyright 2018 SUSE Linux.
+ *   Author: Coly Li <colyli@suse.de>
+ *
+ */
+
+#include <inttypes.h>
+#include <linux/swab.h>
+#include <stdio.h>
+#include "../usr/include/asm/byteorder.h"
+
+#define CRC64_ECMA182_POLY 0x42F0E1EBA9EA3693ULL
+
+#ifdef __LITTLE_ENDIAN
+#  define cpu_to_le64(x) ((__le64)(x))
+#else
+#  define cpu_to_le64(x) ((__le64)__swab64(x))
+#endif
+
+static int64_t crc64_table[256] = {0,};
+
+static void generate_crc64_table(void)
+{
+	uint64_t i, j, c, crc;
+
+	for (i = 0; i < 256; i++) {
+		crc = 0;
+		c = i << 56;
+
+		for (j = 0; j < 8; j++) {
+			if ((crc ^ c) & 0x8000000000000000ULL)
+				crc = (crc << 1) ^ CRC64_ECMA182_POLY;
+			else
+				crc <<= 1;
+			c <<= 1;
+		}
+
+		crc64_table[i] = crc;
+	}
+
+}
+
+static void print_crc64le_table(void)
+{
+	int i;
+
+	printf("/* this file is generated - do not edit */\n\n");
+	printf("#include <uapi/linux/types.h>\n");
+	printf("#include <linux/cache.h>\n\n");
+	printf("static const __le64 ____cacheline_aligned crc64table_le[256] = {\n");
+	for (i = 0; i < 256; i++) {
+		printf("\t0x%016" PRIx64 "ULL", cpu_to_le64(crc64_table[i]));
+		if (i & 0x1)
+			printf(",\n");
+		else
+			printf(", ");
+	}
+	printf("};\n");
+}
+
+int main(int argc, char *argv[])
+{
+	generate_crc64_table();
+	print_crc64le_table();
+	return 0;
+}
-- 
2.17.1

Re: [PATCH 2/4] lib: add crc64 calculation routines

[Randy Dunlap]

On 07/16/2018 09:55 AM, Coly Li wrote:
> 
> diff --git a/lib/crc64.c b/lib/crc64.c
> new file mode 100644
> index 000000000000..03f078303bd3
> --- /dev/null
> +++ b/lib/crc64.c
> @@ -0,0 +1,71 @@
> +// SPDX-License-Identifier: GPL-2.0
> +/*
> + * Normal 64bit CRC calculation.
> + *
> + * This is a basic crc64 implementation following ECMA-182 specification,
> + * which can be found from,
> + * http://www.ecma-international.org/publications/standards/Ecma-182.htm
> + *
> + * Dr. Ross N. Williams has a great document to introduce the idea of CRC
> + * algorithm, here the CRC64 code is also inspired by the table-driven
> + * algorithm and detail example from this paper. This paper can be found
> + * from,
> + * http://www.ross.net/crc/download/crc_v3.txt
> + *
> + * crc64table_le[256] is the lookup table of a table-driver 64bit CRC
> + * calculation, which is generated by gen_crc64table.c in kernel build
> + * time. The polynomial of crc64 arithmetic is from ECMA-182 specification
> + * as well, which is defined as,
> + *
> + * x^64 + x^62 + x^57 + x^55 + x^54 + x^53 + x^52 + x^47 + x^46 + x^45 +
> + * x^40 + x^39 + x^38 + x^37 + x^35 + x^33 + x^32 + x^31 + x^29 + x^27 +
> + * x^24 + x^23 + x^22 + x^21 + x^19 + x^17 + x^13 + x^12 + x^10 + x^9 +
> + * x^7 + x^4 + x + 1
> + *
> + * Copyright 2018 SUSE Linux.
> + *   Author: Coly Li <colyli@suse.de>
> + *
> + */
> +
> +#include <linux/module.h>
> +#include <uapi/linux/types.h>
> +#include "crc64table.h"
> +
> +MODULE_DESCRIPTION("CRC64 calculations");
> +MODULE_LICENSE("GPL");
> +
> +__le64 crc64_le_update(__le64 crc, const void *_p, size_t len)
> +{
> +	size_t i, t;
> +
> +	const unsigned char *p = _p;
> +
> +	for (i = 0; i < len; i++) {
> +		t = ((crc >> 56) ^ (__le64)(*p++)) & 0xFF;
> +		crc = crc64table_le[t] ^ (crc << 8);
> +	}
> +
> +	return crc;
> +}
> +EXPORT_SYMBOL_GPL(crc64_le_update);
> +
> +__le64 crc64_le(const void *p, size_t len)
> +{
> +	__le64 crc = 0x0000000000000000ULL;

Hi,
What's wrong with just using 0ULL ?

thanks.

> +
> +	crc = crc64_le_update(crc, p, len);
> +
> +	return crc;
> +}


-- 
~Randy

Re: [PATCH 2/4] lib: add crc64 calculation routines

[Coly Li]

On 2018/7/17 1:57 AM, Randy Dunlap wrote:
> On 07/16/2018 09:55 AM, Coly Li wrote:
>>
>> diff --git a/lib/crc64.c b/lib/crc64.c
>> new file mode 100644
>> index 000000000000..03f078303bd3
>> --- /dev/null
>> +++ b/lib/crc64.c
>> @@ -0,0 +1,71 @@
>> +// SPDX-License-Identifier: GPL-2.0
>> +/*
>> + * Normal 64bit CRC calculation.
>> + *
>> + * This is a basic crc64 implementation following ECMA-182 specification,
>> + * which can be found from,
>> + * http://www.ecma-international.org/publications/standards/Ecma-182.htm
>> + *
>> + * Dr. Ross N. Williams has a great document to introduce the idea of CRC
>> + * algorithm, here the CRC64 code is also inspired by the table-driven
>> + * algorithm and detail example from this paper. This paper can be found
>> + * from,
>> + * http://www.ross.net/crc/download/crc_v3.txt
>> + *
>> + * crc64table_le[256] is the lookup table of a table-driver 64bit CRC
>> + * calculation, which is generated by gen_crc64table.c in kernel build
>> + * time. The polynomial of crc64 arithmetic is from ECMA-182 specification
>> + * as well, which is defined as,
>> + *
>> + * x^64 + x^62 + x^57 + x^55 + x^54 + x^53 + x^52 + x^47 + x^46 + x^45 +
>> + * x^40 + x^39 + x^38 + x^37 + x^35 + x^33 + x^32 + x^31 + x^29 + x^27 +
>> + * x^24 + x^23 + x^22 + x^21 + x^19 + x^17 + x^13 + x^12 + x^10 + x^9 +
>> + * x^7 + x^4 + x + 1
>> + *
>> + * Copyright 2018 SUSE Linux.
>> + *   Author: Coly Li <colyli@suse.de>
>> + *
>> + */
>> +
>> +#include <linux/module.h>
>> +#include <uapi/linux/types.h>
>> +#include "crc64table.h"
>> +
>> +MODULE_DESCRIPTION("CRC64 calculations");
>> +MODULE_LICENSE("GPL");
>> +
>> +__le64 crc64_le_update(__le64 crc, const void *_p, size_t len)
>> +{
>> +	size_t i, t;
>> +
>> +	const unsigned char *p = _p;
>> +
>> +	for (i = 0; i < len; i++) {
>> +		t = ((crc >> 56) ^ (__le64)(*p++)) & 0xFF;
>> +		crc = crc64table_le[t] ^ (crc << 8);
>> +	}
>> +
>> +	return crc;
>> +}
>> +EXPORT_SYMBOL_GPL(crc64_le_update);
>> +
>> +__le64 crc64_le(const void *p, size_t len)
>> +{
>> +	__le64 crc = 0x0000000000000000ULL;
> 

Hi Randy,

> Hi,
> What's wrong with just using 0ULL ?

In v2 series it will be 0x0ULL :-)

Thanks.

Coly Li

Re: [PATCH 2/4] lib: add crc64 calculation routines

[kbuild test robot]

[-- Attachment #1: Type: text/plain, Size: 1049 bytes --]

Hi Coly,

I love your patch! Yet something to improve:

[auto build test ERROR on linus/master]
[also build test ERROR on v4.18-rc5 next-20180716]
[if your patch is applied to the wrong git tree, please drop us a note to help improve the system]

url:    https://github.com/0day-ci/linux/commits/Coly-Li/add-crc64-calculation-as-kernel-library/20180717-025930
config: i386-allyesconfig (attached as .config)
compiler: gcc-7 (Debian 7.3.0-16) 7.3.0
reproduce:
        # save the attached .config to linux build tree
        make ARCH=i386 

All errors (new ones prefixed by >>):

>> lib/gen_crc64table.c:21:10: fatal error: ../usr/include/asm/byteorder.h: No such file or directory
    #include "../usr/include/asm/byteorder.h"
             ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
   compilation terminated.

vim +21 lib/gen_crc64table.c

  > 21	#include "../usr/include/asm/byteorder.h"
    22	

---
0-DAY kernel test infrastructure                Open Source Technology Center
https://lists.01.org/pipermail/kbuild-all                   Intel Corporation

[-- Attachment #2: .config.gz --]
[-- Type: application/gzip, Size: 63476 bytes --]

Re: [PATCH 2/4] lib: add crc64 calculation routines

[Eric Biggers]

Hi Coly,

On Tue, Jul 17, 2018 at 12:55:05AM +0800, Coly Li wrote:
> This patch adds the re-write crc64 calculation routines for Linux kernel.
> The CRC64 polynomical arithmetic follows ECMA-182 specification, inspired
> by CRC paper of Dr. Ross N. Williams
> (see http://www.ross.net/crc/download/crc_v3.txt) and other public domain
> implementations.
> 
> All the changes work in this way,
> - When Linux kernel is built, host program lib/gen_crc64table.c will be
>   compiled to lib/gen_crc64table and executed.
> - The output of gen_crc64table execution is an array called as lookup
>   table (a.k.a POLY 0x42f0e1eba9ea369) which contain 256 64bits-long
>   numbers, this talbe is dumped into header file lib/crc64table.h.
> - Then the header file is included by lib/crc64.c for normal 64bit crc
>   calculation.
> - Function declaration of the crc64 calculation routines is placed in
>   include/linux/crc64.h
> 
[...]
> diff --git a/lib/crc64.c b/lib/crc64.c
> new file mode 100644
> index 000000000000..03f078303bd3
> --- /dev/null
> +++ b/lib/crc64.c
> @@ -0,0 +1,71 @@
> +// SPDX-License-Identifier: GPL-2.0
> +/*
> + * Normal 64bit CRC calculation.
> + *
> + * This is a basic crc64 implementation following ECMA-182 specification,
> + * which can be found from,
> + * http://www.ecma-international.org/publications/standards/Ecma-182.htm
> + *
> + * Dr. Ross N. Williams has a great document to introduce the idea of CRC
> + * algorithm, here the CRC64 code is also inspired by the table-driven
> + * algorithm and detail example from this paper. This paper can be found
> + * from,
> + * http://www.ross.net/crc/download/crc_v3.txt
> + *
> + * crc64table_le[256] is the lookup table of a table-driver 64bit CRC
> + * calculation, which is generated by gen_crc64table.c in kernel build
> + * time. The polynomial of crc64 arithmetic is from ECMA-182 specification
> + * as well, which is defined as,
> + *
> + * x^64 + x^62 + x^57 + x^55 + x^54 + x^53 + x^52 + x^47 + x^46 + x^45 +
> + * x^40 + x^39 + x^38 + x^37 + x^35 + x^33 + x^32 + x^31 + x^29 + x^27 +
> + * x^24 + x^23 + x^22 + x^21 + x^19 + x^17 + x^13 + x^12 + x^10 + x^9 +
> + * x^7 + x^4 + x + 1
> + *
> + * Copyright 2018 SUSE Linux.
> + *   Author: Coly Li <colyli@suse.de>
> + *
> + */
> +
> +#include <linux/module.h>
> +#include <uapi/linux/types.h>
> +#include "crc64table.h"
> +
> +MODULE_DESCRIPTION("CRC64 calculations");
> +MODULE_LICENSE("GPL");
> +
> +__le64 crc64_le_update(__le64 crc, const void *_p, size_t len)
> +{
> +	size_t i, t;
> +
> +	const unsigned char *p = _p;
> +
> +	for (i = 0; i < len; i++) {
> +		t = ((crc >> 56) ^ (__le64)(*p++)) & 0xFF;
> +		crc = crc64table_le[t] ^ (crc << 8);
> +	}
> +
> +	return crc;
> +}
> +EXPORT_SYMBOL_GPL(crc64_le_update);
> +
> +__le64 crc64_le(const void *p, size_t len)
> +{
> +	__le64 crc = 0x0000000000000000ULL;
> +
> +	crc = crc64_le_update(crc, p, len);
> +
> +	return crc;
> +}
> +EXPORT_SYMBOL_GPL(crc64_le);
> +
> +/* For checksum calculation in drivers/md/bcache/ */
> +__le64 crc64_le_bch(const void *p, size_t len)
> +{
> +	__le64 crc = 0xFFFFFFFFFFFFFFFFULL;
> +
> +	crc = crc64_le_update(crc, p, len);
> +
> +	return (crc ^ 0xFFFFFFFFFFFFFFFFULL);
> +}
> +EXPORT_SYMBOL_GPL(crc64_le_bch);

Using __le64 here makes no sense, because that type indicates the endianness of
the *bytes*, whereas with CRC's "little endian" and "big endian" refer to the
order in which the *bits* are mapped to the polynomial coefficients.

Also as you can see for lib/crc32.c you really only need to provide a function

	u64 __pure crc64_le(u64 crc, unsigned char const *p, size_t len);

and the callers can invert at the beginning and/or end if needed.

Also your function names make it sound like inverting the bits is the exception
or not recommended, since you called the function which does the inversions
"crc32_le_bch()" so it sounds like a bcache-specific hack, while the one that
doesn't do the inversions is simply called "crc32_le()".  But actually it's
normally recommended to do CRC's with the inversions, so that leading and
trailing zeroes affect the resulting CRC.

> diff --git a/lib/gen_crc64table.c b/lib/gen_crc64table.c
> new file mode 100644
> index 000000000000..5f292f287498
> --- /dev/null
> +++ b/lib/gen_crc64table.c
> @@ -0,0 +1,77 @@
> +// SPDX-License-Identifier: GPL-2.0
> +/*
> + * Generate lookup table for the talbe-driven CRC64 calculation.
> + *
> + * gen_crc64table is executed in kernel build time and generates
> + * lib/crc64table.h. This header is included by lib/crc64.c for
> + * the table-driver CRC64 calculation.
> + *
> + * See lib/crc64.c for more information about which specification
> + * and polynomical arithmetic that gen_crc64table.c follows to
> + * generate the lookup table.
> + *
> + * Copyright 2018 SUSE Linux.
> + *   Author: Coly Li <colyli@suse.de>
> + *
> + */
> +
> +#include <inttypes.h>
> +#include <linux/swab.h>
> +#include <stdio.h>
> +#include "../usr/include/asm/byteorder.h"
> +
> +#define CRC64_ECMA182_POLY 0x42F0E1EBA9EA3693ULL

Okay, that's actually the ECMA-182 polynomial in "big endian" form (highest
order bit is the coefficient of x^63, lowest order bit is the coefficient of
x^0), so you're actually doing a "big endian" CRC.  So everything in your patch
series that claims it's a little endian or "le" CRC is incorrect.

> +
> +#ifdef __LITTLE_ENDIAN
> +#  define cpu_to_le64(x) ((__le64)(x))
> +#else
> +#  define cpu_to_le64(x) ((__le64)__swab64(x))
> +#endif
> +
> +static int64_t crc64_table[256] = {0,};
> +
> +static void generate_crc64_table(void)
> +{
> +	uint64_t i, j, c, crc;
> +
> +	for (i = 0; i < 256; i++) {
> +		crc = 0;
> +		c = i << 56;
> +
> +		for (j = 0; j < 8; j++) {
> +			if ((crc ^ c) & 0x8000000000000000ULL)
> +				crc = (crc << 1) ^ CRC64_ECMA182_POLY;
> +			else
> +				crc <<= 1;
> +			c <<= 1;

See here, it's shifting out the most significant bit, which means it's the
coefficient of the x^63 term ("big endian" or "normal" convention), not the x^0
term ("little endian" or "reversed" convention).

Eric

Re: [PATCH 2/4] lib: add crc64 calculation routines

[Coly Li]

On 2018/7/17 11:34 AM, Eric Biggers wrote:
> Hi Coly,
> 
> On Tue, Jul 17, 2018 at 12:55:05AM +0800, Coly Li wrote:
>> This patch adds the re-write crc64 calculation routines for Linux kernel.
>> The CRC64 polynomical arithmetic follows ECMA-182 specification, inspired
>> by CRC paper of Dr. Ross N. Williams
>> (see http://www.ross.net/crc/download/crc_v3.txt) and other public domain
>> implementations.
>>
>> All the changes work in this way,
>> - When Linux kernel is built, host program lib/gen_crc64table.c will be
>>   compiled to lib/gen_crc64table and executed.
>> - The output of gen_crc64table execution is an array called as lookup
>>   table (a.k.a POLY 0x42f0e1eba9ea369) which contain 256 64bits-long
>>   numbers, this talbe is dumped into header file lib/crc64table.h.
>> - Then the header file is included by lib/crc64.c for normal 64bit crc
>>   calculation.
>> - Function declaration of the crc64 calculation routines is placed in
>>   include/linux/crc64.h
>>
> [...]
>> diff --git a/lib/crc64.c b/lib/crc64.c
>> new file mode 100644
>> index 000000000000..03f078303bd3
>> --- /dev/null
>> +++ b/lib/crc64.c
>> @@ -0,0 +1,71 @@
>> +// SPDX-License-Identifier: GPL-2.0
>> +/*
>> + * Normal 64bit CRC calculation.
>> + *
>> + * This is a basic crc64 implementation following ECMA-182 specification,
>> + * which can be found from,
>> + * http://www.ecma-international.org/publications/standards/Ecma-182.htm
>> + *
>> + * Dr. Ross N. Williams has a great document to introduce the idea of CRC
>> + * algorithm, here the CRC64 code is also inspired by the table-driven
>> + * algorithm and detail example from this paper. This paper can be found
>> + * from,
>> + * http://www.ross.net/crc/download/crc_v3.txt
>> + *
>> + * crc64table_le[256] is the lookup table of a table-driver 64bit CRC
>> + * calculation, which is generated by gen_crc64table.c in kernel build
>> + * time. The polynomial of crc64 arithmetic is from ECMA-182 specification
>> + * as well, which is defined as,
>> + *
>> + * x^64 + x^62 + x^57 + x^55 + x^54 + x^53 + x^52 + x^47 + x^46 + x^45 +
>> + * x^40 + x^39 + x^38 + x^37 + x^35 + x^33 + x^32 + x^31 + x^29 + x^27 +
>> + * x^24 + x^23 + x^22 + x^21 + x^19 + x^17 + x^13 + x^12 + x^10 + x^9 +
>> + * x^7 + x^4 + x + 1
>> + *
>> + * Copyright 2018 SUSE Linux.
>> + *   Author: Coly Li <colyli@suse.de>
>> + *
>> + */
>> +
>> +#include <linux/module.h>
>> +#include <uapi/linux/types.h>
>> +#include "crc64table.h"
>> +
>> +MODULE_DESCRIPTION("CRC64 calculations");
>> +MODULE_LICENSE("GPL");
>> +
>> +__le64 crc64_le_update(__le64 crc, const void *_p, size_t len)
>> +{
>> +	size_t i, t;
>> +
>> +	const unsigned char *p = _p;
>> +
>> +	for (i = 0; i < len; i++) {
>> +		t = ((crc >> 56) ^ (__le64)(*p++)) & 0xFF;
>> +		crc = crc64table_le[t] ^ (crc << 8);
>> +	}
>> +
>> +	return crc;
>> +}
>> +EXPORT_SYMBOL_GPL(crc64_le_update);
>> +
>> +__le64 crc64_le(const void *p, size_t len)
>> +{
>> +	__le64 crc = 0x0000000000000000ULL;
>> +
>> +	crc = crc64_le_update(crc, p, len);
>> +
>> +	return crc;
>> +}
>> +EXPORT_SYMBOL_GPL(crc64_le);
>> +
>> +/* For checksum calculation in drivers/md/bcache/ */
>> +__le64 crc64_le_bch(const void *p, size_t len)
>> +{
>> +	__le64 crc = 0xFFFFFFFFFFFFFFFFULL;
>> +
>> +	crc = crc64_le_update(crc, p, len);
>> +
>> +	return (crc ^ 0xFFFFFFFFFFFFFFFFULL);
>> +}
>> +EXPORT_SYMBOL_GPL(crc64_le_bch);
> 

Hi Eric,

> Using __le64 here makes no sense, because that type indicates the endianness of
> the *bytes*, whereas with CRC's "little endian" and "big endian" refer to the
> order in which the *bits* are mapped to the polynomial coefficients.
> 
> Also as you can see for lib/crc32.c you really only need to provide a function
> 
> 	u64 __pure crc64_le(u64 crc, unsigned char const *p, size_t len);
> 
> and the callers can invert at the beginning and/or end if needed.

Let me explain why I explicit use __le64 here. When crc64 is used as
on-disk checksum, the input of crc64 calculation should be in a explicit
specific byte order. Currently check sum in bcache code assumes the CPU
is in little endian and just feeds in-memory data into crc64
calculation, then the code does not work on big endian machine like s390x.

To solve such problem, before calculating CRC the in-memory data should
be swapped into a specific byte order (in bcache case it should be
little endian). For data storage or transfer, CRC calculation without
explicit endian is more easy to introduce bugs.

When I declare the type of input and output value as __le64, on big
endian machine, I expect a type mismatch warning if the input memory
buffer is not swapped into little endian. For u64, there is no such type
checking warning.

This is the initial version of lib/crc64.c, people may add their crc64
calculation routines when necessary, e.g. crc64_be() or crc64(). I only
add crc64_le_update() and crc64_le_bch() because bcache code needs them.

Indeed there is no user of crc64_le() for now, but the file is name as
lib/crc64.c, I think there should be a crc64 calculation at least, so I
add crc64_le().

> 
> Also your function names make it sound like inverting the bits is the exception
> or not recommended, since you called the function which does the inversions
> "crc32_le_bch()" so it sounds like a bcache-specific hack, while the one that
> doesn't do the inversions is simply called "crc32_le()".  But actually it's
> normally recommended to do CRC's with the inversions, so that leading and
> trailing zeroes affect the resulting CRC.
> 

I notice this, normally there are two crc routines provided, with and
without inversion. The reason that there is no inversion version is
no-user in Linux kernel. Indeed there is no user of crc64_le() in Linnux
kernel so far. For performance reason, I doubt whether there will be
more user to do 64bit crc in kernel.

I prefer two crc32 calculation for a 64bit value, but meta data checksum
by crc64 calculation is used in bcache for years, the consistency has to
be kept.


>> diff --git a/lib/gen_crc64table.c b/lib/gen_crc64table.c
>> new file mode 100644
>> index 000000000000..5f292f287498
>> --- /dev/null
>> +++ b/lib/gen_crc64table.c
>> @@ -0,0 +1,77 @@
>> +// SPDX-License-Identifier: GPL-2.0
>> +/*
>> + * Generate lookup table for the talbe-driven CRC64 calculation.
>> + *
>> + * gen_crc64table is executed in kernel build time and generates
>> + * lib/crc64table.h. This header is included by lib/crc64.c for
>> + * the table-driver CRC64 calculation.
>> + *
>> + * See lib/crc64.c for more information about which specification
>> + * and polynomical arithmetic that gen_crc64table.c follows to
>> + * generate the lookup table.
>> + *
>> + * Copyright 2018 SUSE Linux.
>> + *   Author: Coly Li <colyli@suse.de>
>> + *
>> + */
>> +
>> +#include <inttypes.h>
>> +#include <linux/swab.h>
>> +#include <stdio.h>
>> +#include "../usr/include/asm/byteorder.h"
>> +
>> +#define CRC64_ECMA182_POLY 0x42F0E1EBA9EA3693ULL
> 
> Okay, that's actually the ECMA-182 polynomial in "big endian" form (highest
> order bit is the coefficient of x^63, lowest order bit is the coefficient of
> x^0), so you're actually doing a "big endian" CRC.  So everything in your patch
> series that claims it's a little endian or "le" CRC is incorrect.
> 
>> +
>> +#ifdef __LITTLE_ENDIAN
>> +#  define cpu_to_le64(x) ((__le64)(x))
>> +#else
>> +#  define cpu_to_le64(x) ((__le64)__swab64(x))
>> +#endif
>> +
>> +static int64_t crc64_table[256] = {0,};
>> +
>> +static void generate_crc64_table(void)
>> +{
>> +	uint64_t i, j, c, crc;
>> +
>> +	for (i = 0; i < 256; i++) {
>> +		crc = 0;
>> +		c = i << 56;
>> +
>> +		for (j = 0; j < 8; j++) {
>> +			if ((crc ^ c) & 0x8000000000000000ULL)
>> +				crc = (crc << 1) ^ CRC64_ECMA182_POLY;
>> +			else
>> +				crc <<= 1;
>> +			c <<= 1;
> 
> See here, it's shifting out the most significant bit, which means it's the
> coefficient of the x^63 term ("big endian" or "normal" convention), not the x^0
> term ("little endian" or "reversed" convention).

I see your point here. I am not expert in coding theory, the knowledge I
have is from wikipedia, ECMA-182 and the document from Dr. Ross
Williams. From ECMA-182 document, I don't see any word with 'big
endian', so I take it as a standard poly and regardless the byte order.

And on wikepedia page
https://en.wikipedia.org/wiki/Cyclic_redundancy_check , CRC-64-ECMA
references the same poly and call "0x42F0E1EBA9EA3693" as normal poly,
which one links to polynomial
	"x^64 + x^62 + x^57 + x^55 + x^54 + ....x^7 + x^4 + x + 1"
if I understand correctly. But from your information, it seems the
polynomial in generate_crc64_table() is x^64 + x^61 ..... Maybe I
misunderstand you, could you please give me more hint ?

Thanks.

Coly Li

Re: [PATCH 2/4] lib: add crc64 calculation routines

[Eric Biggers]

On Tue, Jul 17, 2018 at 02:25:24PM +0800, Coly Li wrote:
> On 2018/7/17 11:34 AM, Eric Biggers wrote:
> > Hi Coly,
> > 
> > On Tue, Jul 17, 2018 at 12:55:05AM +0800, Coly Li wrote:
> >> This patch adds the re-write crc64 calculation routines for Linux kernel.
> >> The CRC64 polynomical arithmetic follows ECMA-182 specification, inspired
> >> by CRC paper of Dr. Ross N. Williams
> >> (see http://www.ross.net/crc/download/crc_v3.txt) and other public domain
> >> implementations.
> >>
> >> All the changes work in this way,
> >> - When Linux kernel is built, host program lib/gen_crc64table.c will be
> >>   compiled to lib/gen_crc64table and executed.
> >> - The output of gen_crc64table execution is an array called as lookup
> >>   table (a.k.a POLY 0x42f0e1eba9ea369) which contain 256 64bits-long
> >>   numbers, this talbe is dumped into header file lib/crc64table.h.
> >> - Then the header file is included by lib/crc64.c for normal 64bit crc
> >>   calculation.
> >> - Function declaration of the crc64 calculation routines is placed in
> >>   include/linux/crc64.h
> >>
> > [...]
> >> diff --git a/lib/crc64.c b/lib/crc64.c
> >> new file mode 100644
> >> index 000000000000..03f078303bd3
> >> --- /dev/null
> >> +++ b/lib/crc64.c
> >> @@ -0,0 +1,71 @@
> >> +// SPDX-License-Identifier: GPL-2.0
> >> +/*
> >> + * Normal 64bit CRC calculation.
> >> + *
> >> + * This is a basic crc64 implementation following ECMA-182 specification,
> >> + * which can be found from,
> >> + * http://www.ecma-international.org/publications/standards/Ecma-182.htm
> >> + *
> >> + * Dr. Ross N. Williams has a great document to introduce the idea of CRC
> >> + * algorithm, here the CRC64 code is also inspired by the table-driven
> >> + * algorithm and detail example from this paper. This paper can be found
> >> + * from,
> >> + * http://www.ross.net/crc/download/crc_v3.txt
> >> + *
> >> + * crc64table_le[256] is the lookup table of a table-driver 64bit CRC
> >> + * calculation, which is generated by gen_crc64table.c in kernel build
> >> + * time. The polynomial of crc64 arithmetic is from ECMA-182 specification
> >> + * as well, which is defined as,
> >> + *
> >> + * x^64 + x^62 + x^57 + x^55 + x^54 + x^53 + x^52 + x^47 + x^46 + x^45 +
> >> + * x^40 + x^39 + x^38 + x^37 + x^35 + x^33 + x^32 + x^31 + x^29 + x^27 +
> >> + * x^24 + x^23 + x^22 + x^21 + x^19 + x^17 + x^13 + x^12 + x^10 + x^9 +
> >> + * x^7 + x^4 + x + 1
> >> + *
> >> + * Copyright 2018 SUSE Linux.
> >> + *   Author: Coly Li <colyli@suse.de>
> >> + *
> >> + */
> >> +
> >> +#include <linux/module.h>
> >> +#include <uapi/linux/types.h>
> >> +#include "crc64table.h"
> >> +
> >> +MODULE_DESCRIPTION("CRC64 calculations");
> >> +MODULE_LICENSE("GPL");
> >> +
> >> +__le64 crc64_le_update(__le64 crc, const void *_p, size_t len)
> >> +{
> >> +	size_t i, t;
> >> +
> >> +	const unsigned char *p = _p;
> >> +
> >> +	for (i = 0; i < len; i++) {
> >> +		t = ((crc >> 56) ^ (__le64)(*p++)) & 0xFF;
> >> +		crc = crc64table_le[t] ^ (crc << 8);
> >> +	}
> >> +
> >> +	return crc;
> >> +}
> >> +EXPORT_SYMBOL_GPL(crc64_le_update);
> >> +
> >> +__le64 crc64_le(const void *p, size_t len)
> >> +{
> >> +	__le64 crc = 0x0000000000000000ULL;
> >> +
> >> +	crc = crc64_le_update(crc, p, len);
> >> +
> >> +	return crc;
> >> +}
> >> +EXPORT_SYMBOL_GPL(crc64_le);
> >> +
> >> +/* For checksum calculation in drivers/md/bcache/ */
> >> +__le64 crc64_le_bch(const void *p, size_t len)
> >> +{
> >> +	__le64 crc = 0xFFFFFFFFFFFFFFFFULL;
> >> +
> >> +	crc = crc64_le_update(crc, p, len);
> >> +
> >> +	return (crc ^ 0xFFFFFFFFFFFFFFFFULL);
> >> +}
> >> +EXPORT_SYMBOL_GPL(crc64_le_bch);
> > 
> 
> Hi Eric,
> 
> > Using __le64 here makes no sense, because that type indicates the endianness of
> > the *bytes*, whereas with CRC's "little endian" and "big endian" refer to the
> > order in which the *bits* are mapped to the polynomial coefficients.
> > 
> > Also as you can see for lib/crc32.c you really only need to provide a function
> > 
> > 	u64 __pure crc64_le(u64 crc, unsigned char const *p, size_t len);
> > 
> > and the callers can invert at the beginning and/or end if needed.
> 
> Let me explain why I explicit use __le64 here. When crc64 is used as
> on-disk checksum, the input of crc64 calculation should be in a explicit
> specific byte order. Currently check sum in bcache code assumes the CPU
> is in little endian and just feeds in-memory data into crc64
> calculation, then the code does not work on big endian machine like s390x.
> 
> To solve such problem, before calculating CRC the in-memory data should
> be swapped into a specific byte order (in bcache case it should be
> little endian). For data storage or transfer, CRC calculation without
> explicit endian is more easy to introduce bugs.

No, the implementation never loads multi-byte values, so CPU endianness doesn't
matter for the input.  CPU endianness *does* matter when serializing the final
calculated CRC into a byte array for storing on-disk, so maybe bcache gets that
part wrong, I don't know.  Either way, that has nothing to do with how the
polynomial coefficients (bits) are ordered *within bytes*, which is what the
"_be" and "_le" refer to in the CRC-32 implementation.  Yes, the naming is
unfortunate as it can easily be confused with the usual "bytewise" endianness,
but you need to understand it.

Again, using __le64 makes absolutely no sense.  You're even doing operations
like shifts directly on a "__le64" which sparse will (correctly) complain about.

> 
> When I declare the type of input and output value as __le64, on big
> endian machine, I expect a type mismatch warning if the input memory
> buffer is not swapped into little endian. For u64, there is no such type
> checking warning.
> 
> This is the initial version of lib/crc64.c, people may add their crc64
> calculation routines when necessary, e.g. crc64_be() or crc64(). I only
> add crc64_le_update() and crc64_le_bch() because bcache code needs them.
> 
> Indeed there is no user of crc64_le() for now, but the file is name as
> lib/crc64.c, I think there should be a crc64 calculation at least, so I
> add crc64_le().
> 
> > 
> > Also your function names make it sound like inverting the bits is the exception
> > or not recommended, since you called the function which does the inversions
> > "crc32_le_bch()" so it sounds like a bcache-specific hack, while the one that
> > doesn't do the inversions is simply called "crc32_le()".  But actually it's
> > normally recommended to do CRC's with the inversions, so that leading and
> > trailing zeroes affect the resulting CRC.
> > 
> 
> I notice this, normally there are two crc routines provided, with and
> without inversion. The reason that there is no inversion version is
> no-user in Linux kernel. Indeed there is no user of crc64_le() in Linnux
> kernel so far. For performance reason, I doubt whether there will be
> more user to do 64bit crc in kernel.
> 
> I prefer two crc32 calculation for a 64bit value, but meta data checksum
> by crc64 calculation is used in bcache for years, the consistency has to
> be kept.

Well, your response didn't actually address my points.  But it raises the
question: if there won't be any other users, then why move CRC-64 to lib/ at
all?

> 
> 
> >> diff --git a/lib/gen_crc64table.c b/lib/gen_crc64table.c
> >> new file mode 100644
> >> index 000000000000..5f292f287498
> >> --- /dev/null
> >> +++ b/lib/gen_crc64table.c
> >> @@ -0,0 +1,77 @@
> >> +// SPDX-License-Identifier: GPL-2.0
> >> +/*
> >> + * Generate lookup table for the talbe-driven CRC64 calculation.
> >> + *
> >> + * gen_crc64table is executed in kernel build time and generates
> >> + * lib/crc64table.h. This header is included by lib/crc64.c for
> >> + * the table-driver CRC64 calculation.
> >> + *
> >> + * See lib/crc64.c for more information about which specification
> >> + * and polynomical arithmetic that gen_crc64table.c follows to
> >> + * generate the lookup table.
> >> + *
> >> + * Copyright 2018 SUSE Linux.
> >> + *   Author: Coly Li <colyli@suse.de>
> >> + *
> >> + */
> >> +
> >> +#include <inttypes.h>
> >> +#include <linux/swab.h>
> >> +#include <stdio.h>
> >> +#include "../usr/include/asm/byteorder.h"
> >> +
> >> +#define CRC64_ECMA182_POLY 0x42F0E1EBA9EA3693ULL
> > 
> > Okay, that's actually the ECMA-182 polynomial in "big endian" form (highest
> > order bit is the coefficient of x^63, lowest order bit is the coefficient of
> > x^0), so you're actually doing a "big endian" CRC.  So everything in your patch
> > series that claims it's a little endian or "le" CRC is incorrect.
> > 
> >> +
> >> +#ifdef __LITTLE_ENDIAN
> >> +#  define cpu_to_le64(x) ((__le64)(x))
> >> +#else
> >> +#  define cpu_to_le64(x) ((__le64)__swab64(x))
> >> +#endif
> >> +
> >> +static int64_t crc64_table[256] = {0,};
> >> +
> >> +static void generate_crc64_table(void)
> >> +{
> >> +	uint64_t i, j, c, crc;
> >> +
> >> +	for (i = 0; i < 256; i++) {
> >> +		crc = 0;
> >> +		c = i << 56;
> >> +
> >> +		for (j = 0; j < 8; j++) {
> >> +			if ((crc ^ c) & 0x8000000000000000ULL)
> >> +				crc = (crc << 1) ^ CRC64_ECMA182_POLY;
> >> +			else
> >> +				crc <<= 1;
> >> +			c <<= 1;
> > 
> > See here, it's shifting out the most significant bit, which means it's the
> > coefficient of the x^63 term ("big endian" or "normal" convention), not the x^0
> > term ("little endian" or "reversed" convention).
> 
> I see your point here. I am not expert in coding theory, the knowledge I
> have is from wikipedia, ECMA-182 and the document from Dr. Ross
> Williams. From ECMA-182 document, I don't see any word with 'big
> endian', so I take it as a standard poly and regardless the byte order.
> 
> And on wikepedia page
> https://en.wikipedia.org/wiki/Cyclic_redundancy_check , CRC-64-ECMA
> references the same poly and call "0x42F0E1EBA9EA3693" as normal poly,
> which one links to polynomial
> 	"x^64 + x^62 + x^57 + x^55 + x^54 + ....x^7 + x^4 + x + 1"
> if I understand correctly. But from your information, it seems the
> polynomial in generate_crc64_table() is x^64 + x^61 ..... Maybe I
> misunderstand you, could you please give me more hint ?

As I said, the "normal" convention is the same as "big endian", and the
"reversed" convention is the same as "little endian" (again, meaning "bitwise"
endianness, not the usual "bytewise" endianness).  The polynomial is correct but
you are claiming the polynomial coefficients are mapped to bits in a different
order than they actually are.

- Eric

Re: [PATCH 2/4] lib: add crc64 calculation routines

[Coly Li]

On 2018/7/17 3:13 PM, Eric Biggers wrote:
> On Tue, Jul 17, 2018 at 02:25:24PM +0800, Coly Li wrote:
>> On 2018/7/17 11:34 AM, Eric Biggers wrote:
>>> Hi Coly,
>>>
>>> On Tue, Jul 17, 2018 at 12:55:05AM +0800, Coly Li wrote:
>>>> This patch adds the re-write crc64 calculation routines for Linux kernel.
>>>> The CRC64 polynomical arithmetic follows ECMA-182 specification, inspired
>>>> by CRC paper of Dr. Ross N. Williams
>>>> (see http://www.ross.net/crc/download/crc_v3.txt) and other public domain
>>>> implementations.
>>>>
>>>> All the changes work in this way,
>>>> - When Linux kernel is built, host program lib/gen_crc64table.c will be
>>>>   compiled to lib/gen_crc64table and executed.
>>>> - The output of gen_crc64table execution is an array called as lookup
>>>>   table (a.k.a POLY 0x42f0e1eba9ea369) which contain 256 64bits-long
>>>>   numbers, this talbe is dumped into header file lib/crc64table.h.
>>>> - Then the header file is included by lib/crc64.c for normal 64bit crc
>>>>   calculation.
>>>> - Function declaration of the crc64 calculation routines is placed in
>>>>   include/linux/crc64.h
>>>>
>>> [...]
>>>> diff --git a/lib/crc64.c b/lib/crc64.c
>>>> new file mode 100644
>>>> index 000000000000..03f078303bd3
>>>> --- /dev/null
>>>> +++ b/lib/crc64.c
>>>> @@ -0,0 +1,71 @@
>>>> +// SPDX-License-Identifier: GPL-2.0
>>>> +/*
>>>> + * Normal 64bit CRC calculation.
>>>> + *
>>>> + * This is a basic crc64 implementation following ECMA-182 specification,
>>>> + * which can be found from,
>>>> + * http://www.ecma-international.org/publications/standards/Ecma-182.htm
>>>> + *
>>>> + * Dr. Ross N. Williams has a great document to introduce the idea of CRC
>>>> + * algorithm, here the CRC64 code is also inspired by the table-driven
>>>> + * algorithm and detail example from this paper. This paper can be found
>>>> + * from,
>>>> + * http://www.ross.net/crc/download/crc_v3.txt
>>>> + *
>>>> + * crc64table_le[256] is the lookup table of a table-driver 64bit CRC
>>>> + * calculation, which is generated by gen_crc64table.c in kernel build
>>>> + * time. The polynomial of crc64 arithmetic is from ECMA-182 specification
>>>> + * as well, which is defined as,
>>>> + *
>>>> + * x^64 + x^62 + x^57 + x^55 + x^54 + x^53 + x^52 + x^47 + x^46 + x^45 +
>>>> + * x^40 + x^39 + x^38 + x^37 + x^35 + x^33 + x^32 + x^31 + x^29 + x^27 +
>>>> + * x^24 + x^23 + x^22 + x^21 + x^19 + x^17 + x^13 + x^12 + x^10 + x^9 +
>>>> + * x^7 + x^4 + x + 1
>>>> + *
>>>> + * Copyright 2018 SUSE Linux.
>>>> + *   Author: Coly Li <colyli@suse.de>
>>>> + *
>>>> + */
>>>> +
>>>> +#include <linux/module.h>
>>>> +#include <uapi/linux/types.h>
>>>> +#include "crc64table.h"
>>>> +
>>>> +MODULE_DESCRIPTION("CRC64 calculations");
>>>> +MODULE_LICENSE("GPL");
>>>> +
>>>> +__le64 crc64_le_update(__le64 crc, const void *_p, size_t len)
>>>> +{
>>>> +	size_t i, t;
>>>> +
>>>> +	const unsigned char *p = _p;
>>>> +
>>>> +	for (i = 0; i < len; i++) {
>>>> +		t = ((crc >> 56) ^ (__le64)(*p++)) & 0xFF;
>>>> +		crc = crc64table_le[t] ^ (crc << 8);
>>>> +	}
>>>> +
>>>> +	return crc;
>>>> +}
>>>> +EXPORT_SYMBOL_GPL(crc64_le_update);
>>>> +
>>>> +__le64 crc64_le(const void *p, size_t len)
>>>> +{
>>>> +	__le64 crc = 0x0000000000000000ULL;
>>>> +
>>>> +	crc = crc64_le_update(crc, p, len);
>>>> +
>>>> +	return crc;
>>>> +}
>>>> +EXPORT_SYMBOL_GPL(crc64_le);
>>>> +
>>>> +/* For checksum calculation in drivers/md/bcache/ */
>>>> +__le64 crc64_le_bch(const void *p, size_t len)
>>>> +{
>>>> +	__le64 crc = 0xFFFFFFFFFFFFFFFFULL;
>>>> +
>>>> +	crc = crc64_le_update(crc, p, len);
>>>> +
>>>> +	return (crc ^ 0xFFFFFFFFFFFFFFFFULL);
>>>> +}
>>>> +EXPORT_SYMBOL_GPL(crc64_le_bch);
>>>
>>
>> Hi Eric,
>>
>>> Using __le64 here makes no sense, because that type indicates the endianness of
>>> the *bytes*, whereas with CRC's "little endian" and "big endian" refer to the
>>> order in which the *bits* are mapped to the polynomial coefficients.
>>>
>>> Also as you can see for lib/crc32.c you really only need to provide a function
>>>
>>> 	u64 __pure crc64_le(u64 crc, unsigned char const *p, size_t len);
>>>
>>> and the callers can invert at the beginning and/or end if needed.
>>
>> Let me explain why I explicit use __le64 here. When crc64 is used as
>> on-disk checksum, the input of crc64 calculation should be in a explicit
>> specific byte order. Currently check sum in bcache code assumes the CPU
>> is in little endian and just feeds in-memory data into crc64
>> calculation, then the code does not work on big endian machine like s390x.
>>
>> To solve such problem, before calculating CRC the in-memory data should
>> be swapped into a specific byte order (in bcache case it should be
>> little endian). For data storage or transfer, CRC calculation without
>> explicit endian is more easy to introduce bugs.
> 
> No, the implementation never loads multi-byte values, so CPU endianness doesn't
> matter for the input.  CPU endianness *does* matter when serializing the final

If the checksum is generated on big endian machine and checked on little
endian machine, non-specific endianness will be problematic.

> calculated CRC into a byte array for storing on-disk, so maybe bcache gets that
> part wrong, I don't know.  Either way, that has nothing to do with how the
> polynomial coefficients (bits) are ordered *within bytes*, which is what the
> "_be" and "_le" refer to in the CRC-32 implementation.  Yes, the naming is
> unfortunate as it can easily be confused with the usual "bytewise" endianness,
> but you need to understand it.
> 

I see, it seems I misunderstand _le and _be in CRC-32 implementation.
OK, I will find a way to fix the naming and data type issues in v3 series.

> Again, using __le64 makes absolutely no sense.  You're even doing operations
> like shifts directly on a "__le64" which sparse will (correctly) complain about.
> 

Sure, you are correct here :-)

>>
>> When I declare the type of input and output value as __le64, on big
>> endian machine, I expect a type mismatch warning if the input memory
>> buffer is not swapped into little endian. For u64, there is no such type
>> checking warning.
>>
>> This is the initial version of lib/crc64.c, people may add their crc64
>> calculation routines when necessary, e.g. crc64_be() or crc64(). I only
>> add crc64_le_update() and crc64_le_bch() because bcache code needs them.
>>
>> Indeed there is no user of crc64_le() for now, but the file is name as
>> lib/crc64.c, I think there should be a crc64 calculation at least, so I
>> add crc64_le().
>>
>>>
>>> Also your function names make it sound like inverting the bits is the exception
>>> or not recommended, since you called the function which does the inversions
>>> "crc32_le_bch()" so it sounds like a bcache-specific hack, while the one that
>>> doesn't do the inversions is simply called "crc32_le()".  But actually it's
>>> normally recommended to do CRC's with the inversions, so that leading and
>>> trailing zeroes affect the resulting CRC.
>>>
>>
>> I notice this, normally there are two crc routines provided, with and
>> without inversion. The reason that there is no inversion version is
>> no-user in Linux kernel. Indeed there is no user of crc64_le() in Linnux
>> kernel so far. For performance reason, I doubt whether there will be
>> more user to do 64bit crc in kernel.
>>
>> I prefer two crc32 calculation for a 64bit value, but meta data checksum
>> by crc64 calculation is used in bcache for years, the consistency has to
>> be kept.
> 
> Well, your response didn't actually address my points.  But it raises the
> question: if there won't be any other users, then why move CRC-64 to lib/ at
> all?
> 

The only motivation I can see is becachefs, which share part of the code
base with bcache, including crc64 calculation.

And before CPU supports build-in instructors for CRC64, I don't see the
reason why people should use 64bit CRC other than 32bit ones.

>>
>>
>>>> diff --git a/lib/gen_crc64table.c b/lib/gen_crc64table.c
>>>> new file mode 100644
>>>> index 000000000000..5f292f287498
>>>> --- /dev/null
>>>> +++ b/lib/gen_crc64table.c
>>>> @@ -0,0 +1,77 @@
>>>> +// SPDX-License-Identifier: GPL-2.0
>>>> +/*
>>>> + * Generate lookup table for the talbe-driven CRC64 calculation.
>>>> + *
>>>> + * gen_crc64table is executed in kernel build time and generates
>>>> + * lib/crc64table.h. This header is included by lib/crc64.c for
>>>> + * the table-driver CRC64 calculation.
>>>> + *
>>>> + * See lib/crc64.c for more information about which specification
>>>> + * and polynomical arithmetic that gen_crc64table.c follows to
>>>> + * generate the lookup table.
>>>> + *
>>>> + * Copyright 2018 SUSE Linux.
>>>> + *   Author: Coly Li <colyli@suse.de>
>>>> + *
>>>> + */
>>>> +
>>>> +#include <inttypes.h>
>>>> +#include <linux/swab.h>
>>>> +#include <stdio.h>
>>>> +#include "../usr/include/asm/byteorder.h"
>>>> +
>>>> +#define CRC64_ECMA182_POLY 0x42F0E1EBA9EA3693ULL
>>>
>>> Okay, that's actually the ECMA-182 polynomial in "big endian" form (highest
>>> order bit is the coefficient of x^63, lowest order bit is the coefficient of
>>> x^0), so you're actually doing a "big endian" CRC.  So everything in your patch
>>> series that claims it's a little endian or "le" CRC is incorrect.
>>>
>>>> +
>>>> +#ifdef __LITTLE_ENDIAN
>>>> +#  define cpu_to_le64(x) ((__le64)(x))
>>>> +#else
>>>> +#  define cpu_to_le64(x) ((__le64)__swab64(x))
>>>> +#endif
>>>> +
>>>> +static int64_t crc64_table[256] = {0,};
>>>> +
>>>> +static void generate_crc64_table(void)
>>>> +{
>>>> +	uint64_t i, j, c, crc;
>>>> +
>>>> +	for (i = 0; i < 256; i++) {
>>>> +		crc = 0;
>>>> +		c = i << 56;
>>>> +
>>>> +		for (j = 0; j < 8; j++) {
>>>> +			if ((crc ^ c) & 0x8000000000000000ULL)
>>>> +				crc = (crc << 1) ^ CRC64_ECMA182_POLY;
>>>> +			else
>>>> +				crc <<= 1;
>>>> +			c <<= 1;
>>>
>>> See here, it's shifting out the most significant bit, which means it's the
>>> coefficient of the x^63 term ("big endian" or "normal" convention), not the x^0
>>> term ("little endian" or "reversed" convention).
>>
>> I see your point here. I am not expert in coding theory, the knowledge I
>> have is from wikipedia, ECMA-182 and the document from Dr. Ross
>> Williams. From ECMA-182 document, I don't see any word with 'big
>> endian', so I take it as a standard poly and regardless the byte order.
>>
>> And on wikepedia page
>> https://en.wikipedia.org/wiki/Cyclic_redundancy_check , CRC-64-ECMA
>> references the same poly and call "0x42F0E1EBA9EA3693" as normal poly,
>> which one links to polynomial
>> 	"x^64 + x^62 + x^57 + x^55 + x^54 + ....x^7 + x^4 + x + 1"
>> if I understand correctly. But from your information, it seems the
>> polynomial in generate_crc64_table() is x^64 + x^61 ..... Maybe I
>> misunderstand you, could you please give me more hint ?
> 
> As I said, the "normal" convention is the same as "big endian", and the
> "reversed" convention is the same as "little endian" (again, meaning "bitwise"
> endianness, not the usual "bytewise" endianness).  The polynomial is correct but
> you are claiming the polynomial coefficients are mapped to bits in a different
> order than they actually are.

Copied, thanks for the hint :-)

Coly Li

Re: [PATCH 2/4] lib: add crc64 calculation routines

[Coly Li]

On 2018/7/17 3:34 PM, Coly Li wrote:
> On 2018/7/17 3:13 PM, Eric Biggers wrote:
>> On Tue, Jul 17, 2018 at 02:25:24PM +0800, Coly Li wrote:
>>> On 2018/7/17 11:34 AM, Eric Biggers wrote:
>>>> Hi Coly,
>>>>
>>>> On Tue, Jul 17, 2018 at 12:55:05AM +0800, Coly Li wrote:
>>>>> This patch adds the re-write crc64 calculation routines for Linux kernel.
>>>>> The CRC64 polynomical arithmetic follows ECMA-182 specification, inspired
>>>>> by CRC paper of Dr. Ross N. Williams
>>>>> (see http://www.ross.net/crc/download/crc_v3.txt) and other public domain
>>>>> implementations.
>>>>>
>>>>> All the changes work in this way,
>>>>> - When Linux kernel is built, host program lib/gen_crc64table.c will be
>>>>>   compiled to lib/gen_crc64table and executed.
>>>>> - The output of gen_crc64table execution is an array called as lookup
>>>>>   table (a.k.a POLY 0x42f0e1eba9ea369) which contain 256 64bits-long
>>>>>   numbers, this talbe is dumped into header file lib/crc64table.h.
>>>>> - Then the header file is included by lib/crc64.c for normal 64bit crc
>>>>>   calculation.
>>>>> - Function declaration of the crc64 calculation routines is placed in
>>>>>   include/linux/crc64.h
>>>>>
>>>> [...]
>>>>> diff --git a/lib/crc64.c b/lib/crc64.c
>>>>> new file mode 100644
>>>>> index 000000000000..03f078303bd3
>>>>> --- /dev/null
>>>>> +++ b/lib/crc64.c
>>>>> @@ -0,0 +1,71 @@
>>>>> +// SPDX-License-Identifier: GPL-2.0
>>>>> +/*
>>>>> + * Normal 64bit CRC calculation.
>>>>> + *
>>>>> + * This is a basic crc64 implementation following ECMA-182 specification,
>>>>> + * which can be found from,
>>>>> + * http://www.ecma-international.org/publications/standards/Ecma-182.htm
>>>>> + *
>>>>> + * Dr. Ross N. Williams has a great document to introduce the idea of CRC
>>>>> + * algorithm, here the CRC64 code is also inspired by the table-driven
>>>>> + * algorithm and detail example from this paper. This paper can be found
>>>>> + * from,
>>>>> + * http://www.ross.net/crc/download/crc_v3.txt
>>>>> + *
>>>>> + * crc64table_le[256] is the lookup table of a table-driver 64bit CRC
>>>>> + * calculation, which is generated by gen_crc64table.c in kernel build
>>>>> + * time. The polynomial of crc64 arithmetic is from ECMA-182 specification
>>>>> + * as well, which is defined as,
>>>>> + *
>>>>> + * x^64 + x^62 + x^57 + x^55 + x^54 + x^53 + x^52 + x^47 + x^46 + x^45 +
>>>>> + * x^40 + x^39 + x^38 + x^37 + x^35 + x^33 + x^32 + x^31 + x^29 + x^27 +
>>>>> + * x^24 + x^23 + x^22 + x^21 + x^19 + x^17 + x^13 + x^12 + x^10 + x^9 +
>>>>> + * x^7 + x^4 + x + 1
>>>>> + *
>>>>> + * Copyright 2018 SUSE Linux.
>>>>> + *   Author: Coly Li <colyli@suse.de>
>>>>> + *
>>>>> + */
>>>>> +
>>>>> +#include <linux/module.h>
>>>>> +#include <uapi/linux/types.h>
>>>>> +#include "crc64table.h"
>>>>> +
>>>>> +MODULE_DESCRIPTION("CRC64 calculations");
>>>>> +MODULE_LICENSE("GPL");
>>>>> +
>>>>> +__le64 crc64_le_update(__le64 crc, const void *_p, size_t len)
>>>>> +{
>>>>> +	size_t i, t;
>>>>> +
>>>>> +	const unsigned char *p = _p;
>>>>> +
>>>>> +	for (i = 0; i < len; i++) {
>>>>> +		t = ((crc >> 56) ^ (__le64)(*p++)) & 0xFF;
>>>>> +		crc = crc64table_le[t] ^ (crc << 8);
>>>>> +	}
>>>>> +
>>>>> +	return crc;
>>>>> +}
>>>>> +EXPORT_SYMBOL_GPL(crc64_le_update);
>>>>> +
>>>>> +__le64 crc64_le(const void *p, size_t len)
>>>>> +{
>>>>> +	__le64 crc = 0x0000000000000000ULL;
>>>>> +
>>>>> +	crc = crc64_le_update(crc, p, len);
>>>>> +
>>>>> +	return crc;
>>>>> +}
>>>>> +EXPORT_SYMBOL_GPL(crc64_le);
>>>>> +
>>>>> +/* For checksum calculation in drivers/md/bcache/ */
>>>>> +__le64 crc64_le_bch(const void *p, size_t len)
>>>>> +{
>>>>> +	__le64 crc = 0xFFFFFFFFFFFFFFFFULL;
>>>>> +
>>>>> +	crc = crc64_le_update(crc, p, len);
>>>>> +
>>>>> +	return (crc ^ 0xFFFFFFFFFFFFFFFFULL);
>>>>> +}
>>>>> +EXPORT_SYMBOL_GPL(crc64_le_bch);

[snipped]

>>> I see your point here. I am not expert in coding theory, the knowledge I
>>> have is from wikipedia, ECMA-182 and the document from Dr. Ross
>>> Williams. From ECMA-182 document, I don't see any word with 'big
>>> endian', so I take it as a standard poly and regardless the byte order.
>>>
>>> And on wikepedia page
>>> https://en.wikipedia.org/wiki/Cyclic_redundancy_check , CRC-64-ECMA
>>> references the same poly and call "0x42F0E1EBA9EA3693" as normal poly,
>>> which one links to polynomial
>>> 	"x^64 + x^62 + x^57 + x^55 + x^54 + ....x^7 + x^4 + x + 1"
>>> if I understand correctly. But from your information, it seems the
>>> polynomial in generate_crc64_table() is x^64 + x^61 ..... Maybe I
>>> misunderstand you, could you please give me more hint ?
>>
>> As I said, the "normal" convention is the same as "big endian", and the
>> "reversed" convention is the same as "little endian" (again, meaning "bitwise"
>> endianness, not the usual "bytewise" endianness).  The polynomial is correct but
>> you are claiming the polynomial coefficients are mapped to bits in a different
>> order than they actually are.

In v3 series, I remove _le and __le64 from the patch, that means the
calculation is not explicit resitricted to little endian, and the caller
should make sure the data in a proper byte order. The result is, there
is no misleading naming issue. Since so far the only user is bcache, and
potential user is bcachefs, the developers should know how to use
crc64_update() and crc64_bch() properly.

So now the routines are named as crc64(), crc64_update(), crc64_bch(),
and return value is u64.

I hope now the misleading can be avoided.

Thanks.

Coly Li

[PATCH 3/4] bcache: use routines from lib/crc64.c for CRC64 calculation

[Coly Li]

Now we have crc64 calculation in lib/crc64.c, it is unnecessary for
bcache to use it own version. This patch changes bcache code to use
crc64 routines in lib/crc64.c.

Signed-off-by: Coly Li <colyli@suse.de>
Cc: Andy Shevchenko <andriy.shevchenko@linux.intel.com>
Cc: Michael Lyle <mlyle@lyle.org>
Cc: Kent Overstreet <kent.overstreet@gmail.com>
Cc: Linus Torvalds <torvalds@linux-foundation.org>
Cc: Thomas Gleixner <tglx@linutronix.de>
Cc: Kate Stewart <kstewart@linuxfoundation.org>
---
 drivers/md/bcache/Kconfig   |   1 +
 drivers/md/bcache/bcache.h  |   7 +-
 drivers/md/bcache/btree.c   |   2 +-
 drivers/md/bcache/request.c |   2 +-
 drivers/md/bcache/super.c   |   5 +-
 drivers/md/bcache/util.c    | 131 ------------------------------------
 drivers/md/bcache/util.h    |   5 +-
 7 files changed, 11 insertions(+), 142 deletions(-)

diff --git a/drivers/md/bcache/Kconfig b/drivers/md/bcache/Kconfig
index 17bf109c58e9..af247298409a 100644
--- a/drivers/md/bcache/Kconfig
+++ b/drivers/md/bcache/Kconfig
@@ -1,6 +1,7 @@
 
 config BCACHE
 	tristate "Block device as cache"
+	select CRC64
 	---help---
 	Allows a block device to be used as cache for other devices; uses
 	a btree for indexing and the layout is optimized for SSDs.
diff --git a/drivers/md/bcache/bcache.h b/drivers/md/bcache/bcache.h
index d6bf294f3907..3f7934f56648 100644
--- a/drivers/md/bcache/bcache.h
+++ b/drivers/md/bcache/bcache.h
@@ -189,6 +189,7 @@
 #include <linux/types.h>
 #include <linux/workqueue.h>
 #include <linux/kthread.h>
+#include <linux/crc64.h>
 
 #include "bset.h"
 #include "util.h"
@@ -803,9 +804,9 @@ static inline bool ptr_available(struct cache_set *c, const struct bkey *k,
  * jset: The checksum is _always_ the first 8 bytes of these structs
  */
 #define csum_set(i)							\
-	bch_crc64(((void *) (i)) + sizeof(uint64_t),			\
-		  ((void *) bset_bkey_last(i)) -			\
-		  (((void *) (i)) + sizeof(uint64_t)))
+	crc64_le_bch(((void *) (i)) + sizeof(uint64_t),			\
+		   ((void *) bset_bkey_last(i)) -			\
+		   (((void *) (i)) + sizeof(uint64_t)))
 
 /* Error handling macros */
 
diff --git a/drivers/md/bcache/btree.c b/drivers/md/bcache/btree.c
index 547c9eedc2f4..378dd6688d26 100644
--- a/drivers/md/bcache/btree.c
+++ b/drivers/md/bcache/btree.c
@@ -194,7 +194,7 @@ static uint64_t btree_csum_set(struct btree *b, struct bset *i)
 	uint64_t crc = b->key.ptr[0];
 	void *data = (void *) i + 8, *end = bset_bkey_last(i);
 
-	crc = bch_crc64_update(crc, data, end - data);
+	crc = crc64_le_update(crc, data, end - data);
 	return crc ^ 0xffffffffffffffffULL;
 }
 
diff --git a/drivers/md/bcache/request.c b/drivers/md/bcache/request.c
index ae67f5fa8047..4efe6550df94 100644
--- a/drivers/md/bcache/request.c
+++ b/drivers/md/bcache/request.c
@@ -45,7 +45,7 @@ static void bio_csum(struct bio *bio, struct bkey *k)
 
 	bio_for_each_segment(bv, bio, iter) {
 		void *d = kmap(bv.bv_page) + bv.bv_offset;
-		csum = bch_crc64_update(csum, d, bv.bv_len);
+		csum = crc64_le_update(csum, d, bv.bv_len);
 		kunmap(bv.bv_page);
 	}
 
diff --git a/drivers/md/bcache/super.c b/drivers/md/bcache/super.c
index fa4058e43202..61beb68b9048 100644
--- a/drivers/md/bcache/super.c
+++ b/drivers/md/bcache/super.c
@@ -549,7 +549,7 @@ void bch_prio_write(struct cache *ca)
 
 		p->next_bucket	= ca->prio_buckets[i + 1];
 		p->magic	= pset_magic(&ca->sb);
-		p->csum		= bch_crc64(&p->magic, bucket_bytes(ca) - 8);
+		p->csum		= crc64_le_bch(&p->magic, bucket_bytes(ca) - 8);
 
 		bucket = bch_bucket_alloc(ca, RESERVE_PRIO, true);
 		BUG_ON(bucket == -1);
@@ -599,7 +599,8 @@ static void prio_read(struct cache *ca, uint64_t bucket)
 
 			prio_io(ca, bucket, REQ_OP_READ, 0);
 
-			if (p->csum != bch_crc64(&p->magic, bucket_bytes(ca) - 8))
+			if (p->csum != crc64_le_bch(&p->magic,
+						   bucket_bytes(ca) - 8))
 				pr_warn("bad csum reading priorities");
 
 			if (p->magic != pset_magic(&ca->sb))
diff --git a/drivers/md/bcache/util.c b/drivers/md/bcache/util.c
index fc479b026d6d..f912c372978c 100644
--- a/drivers/md/bcache/util.c
+++ b/drivers/md/bcache/util.c
@@ -279,134 +279,3 @@ int bch_bio_alloc_pages(struct bio *bio, gfp_t gfp_mask)
 
 	return 0;
 }
-
-/*
- * Portions Copyright (c) 1996-2001, PostgreSQL Global Development Group (Any
- * use permitted, subject to terms of PostgreSQL license; see.)
-
- * If we have a 64-bit integer type, then a 64-bit CRC looks just like the
- * usual sort of implementation. (See Ross Williams' excellent introduction
- * A PAINLESS GUIDE TO CRC ERROR DETECTION ALGORITHMS, available from
- * ftp://ftp.rocksoft.com/papers/crc_v3.txt or several other net sites.)
- * If we have no working 64-bit type, then fake it with two 32-bit registers.
- *
- * The present implementation is a normal (not "reflected", in Williams'
- * terms) 64-bit CRC, using initial all-ones register contents and a final
- * bit inversion. The chosen polynomial is borrowed from the DLT1 spec
- * (ECMA-182, available from http://www.ecma.ch/ecma1/STAND/ECMA-182.HTM):
- *
- * x^64 + x^62 + x^57 + x^55 + x^54 + x^53 + x^52 + x^47 + x^46 + x^45 +
- * x^40 + x^39 + x^38 + x^37 + x^35 + x^33 + x^32 + x^31 + x^29 + x^27 +
- * x^24 + x^23 + x^22 + x^21 + x^19 + x^17 + x^13 + x^12 + x^10 + x^9 +
- * x^7 + x^4 + x + 1
-*/
-
-static const uint64_t crc_table[256] = {
-	0x0000000000000000ULL, 0x42F0E1EBA9EA3693ULL, 0x85E1C3D753D46D26ULL,
-	0xC711223CFA3E5BB5ULL, 0x493366450E42ECDFULL, 0x0BC387AEA7A8DA4CULL,
-	0xCCD2A5925D9681F9ULL, 0x8E224479F47CB76AULL, 0x9266CC8A1C85D9BEULL,
-	0xD0962D61B56FEF2DULL, 0x17870F5D4F51B498ULL, 0x5577EEB6E6BB820BULL,
-	0xDB55AACF12C73561ULL, 0x99A54B24BB2D03F2ULL, 0x5EB4691841135847ULL,
-	0x1C4488F3E8F96ED4ULL, 0x663D78FF90E185EFULL, 0x24CD9914390BB37CULL,
-	0xE3DCBB28C335E8C9ULL, 0xA12C5AC36ADFDE5AULL, 0x2F0E1EBA9EA36930ULL,
-	0x6DFEFF5137495FA3ULL, 0xAAEFDD6DCD770416ULL, 0xE81F3C86649D3285ULL,
-	0xF45BB4758C645C51ULL, 0xB6AB559E258E6AC2ULL, 0x71BA77A2DFB03177ULL,
-	0x334A9649765A07E4ULL, 0xBD68D2308226B08EULL, 0xFF9833DB2BCC861DULL,
-	0x388911E7D1F2DDA8ULL, 0x7A79F00C7818EB3BULL, 0xCC7AF1FF21C30BDEULL,
-	0x8E8A101488293D4DULL, 0x499B3228721766F8ULL, 0x0B6BD3C3DBFD506BULL,
-	0x854997BA2F81E701ULL, 0xC7B97651866BD192ULL, 0x00A8546D7C558A27ULL,
-	0x4258B586D5BFBCB4ULL, 0x5E1C3D753D46D260ULL, 0x1CECDC9E94ACE4F3ULL,
-	0xDBFDFEA26E92BF46ULL, 0x990D1F49C77889D5ULL, 0x172F5B3033043EBFULL,
-	0x55DFBADB9AEE082CULL, 0x92CE98E760D05399ULL, 0xD03E790CC93A650AULL,
-	0xAA478900B1228E31ULL, 0xE8B768EB18C8B8A2ULL, 0x2FA64AD7E2F6E317ULL,
-	0x6D56AB3C4B1CD584ULL, 0xE374EF45BF6062EEULL, 0xA1840EAE168A547DULL,
-	0x66952C92ECB40FC8ULL, 0x2465CD79455E395BULL, 0x3821458AADA7578FULL,
-	0x7AD1A461044D611CULL, 0xBDC0865DFE733AA9ULL, 0xFF3067B657990C3AULL,
-	0x711223CFA3E5BB50ULL, 0x33E2C2240A0F8DC3ULL, 0xF4F3E018F031D676ULL,
-	0xB60301F359DBE0E5ULL, 0xDA050215EA6C212FULL, 0x98F5E3FE438617BCULL,
-	0x5FE4C1C2B9B84C09ULL, 0x1D14202910527A9AULL, 0x93366450E42ECDF0ULL,
-	0xD1C685BB4DC4FB63ULL, 0x16D7A787B7FAA0D6ULL, 0x5427466C1E109645ULL,
-	0x4863CE9FF6E9F891ULL, 0x0A932F745F03CE02ULL, 0xCD820D48A53D95B7ULL,
-	0x8F72ECA30CD7A324ULL, 0x0150A8DAF8AB144EULL, 0x43A04931514122DDULL,
-	0x84B16B0DAB7F7968ULL, 0xC6418AE602954FFBULL, 0xBC387AEA7A8DA4C0ULL,
-	0xFEC89B01D3679253ULL, 0x39D9B93D2959C9E6ULL, 0x7B2958D680B3FF75ULL,
-	0xF50B1CAF74CF481FULL, 0xB7FBFD44DD257E8CULL, 0x70EADF78271B2539ULL,
-	0x321A3E938EF113AAULL, 0x2E5EB66066087D7EULL, 0x6CAE578BCFE24BEDULL,
-	0xABBF75B735DC1058ULL, 0xE94F945C9C3626CBULL, 0x676DD025684A91A1ULL,
-	0x259D31CEC1A0A732ULL, 0xE28C13F23B9EFC87ULL, 0xA07CF2199274CA14ULL,
-	0x167FF3EACBAF2AF1ULL, 0x548F120162451C62ULL, 0x939E303D987B47D7ULL,
-	0xD16ED1D631917144ULL, 0x5F4C95AFC5EDC62EULL, 0x1DBC74446C07F0BDULL,
-	0xDAAD56789639AB08ULL, 0x985DB7933FD39D9BULL, 0x84193F60D72AF34FULL,
-	0xC6E9DE8B7EC0C5DCULL, 0x01F8FCB784FE9E69ULL, 0x43081D5C2D14A8FAULL,
-	0xCD2A5925D9681F90ULL, 0x8FDAB8CE70822903ULL, 0x48CB9AF28ABC72B6ULL,
-	0x0A3B7B1923564425ULL, 0x70428B155B4EAF1EULL, 0x32B26AFEF2A4998DULL,
-	0xF5A348C2089AC238ULL, 0xB753A929A170F4ABULL, 0x3971ED50550C43C1ULL,
-	0x7B810CBBFCE67552ULL, 0xBC902E8706D82EE7ULL, 0xFE60CF6CAF321874ULL,
-	0xE224479F47CB76A0ULL, 0xA0D4A674EE214033ULL, 0x67C58448141F1B86ULL,
-	0x253565A3BDF52D15ULL, 0xAB1721DA49899A7FULL, 0xE9E7C031E063ACECULL,
-	0x2EF6E20D1A5DF759ULL, 0x6C0603E6B3B7C1CAULL, 0xF6FAE5C07D3274CDULL,
-	0xB40A042BD4D8425EULL, 0x731B26172EE619EBULL, 0x31EBC7FC870C2F78ULL,
-	0xBFC9838573709812ULL, 0xFD39626EDA9AAE81ULL, 0x3A28405220A4F534ULL,
-	0x78D8A1B9894EC3A7ULL, 0x649C294A61B7AD73ULL, 0x266CC8A1C85D9BE0ULL,
-	0xE17DEA9D3263C055ULL, 0xA38D0B769B89F6C6ULL, 0x2DAF4F0F6FF541ACULL,
-	0x6F5FAEE4C61F773FULL, 0xA84E8CD83C212C8AULL, 0xEABE6D3395CB1A19ULL,
-	0x90C79D3FEDD3F122ULL, 0xD2377CD44439C7B1ULL, 0x15265EE8BE079C04ULL,
-	0x57D6BF0317EDAA97ULL, 0xD9F4FB7AE3911DFDULL, 0x9B041A914A7B2B6EULL,
-	0x5C1538ADB04570DBULL, 0x1EE5D94619AF4648ULL, 0x02A151B5F156289CULL,
-	0x4051B05E58BC1E0FULL, 0x87409262A28245BAULL, 0xC5B073890B687329ULL,
-	0x4B9237F0FF14C443ULL, 0x0962D61B56FEF2D0ULL, 0xCE73F427ACC0A965ULL,
-	0x8C8315CC052A9FF6ULL, 0x3A80143F5CF17F13ULL, 0x7870F5D4F51B4980ULL,
-	0xBF61D7E80F251235ULL, 0xFD913603A6CF24A6ULL, 0x73B3727A52B393CCULL,
-	0x31439391FB59A55FULL, 0xF652B1AD0167FEEAULL, 0xB4A25046A88DC879ULL,
-	0xA8E6D8B54074A6ADULL, 0xEA16395EE99E903EULL, 0x2D071B6213A0CB8BULL,
-	0x6FF7FA89BA4AFD18ULL, 0xE1D5BEF04E364A72ULL, 0xA3255F1BE7DC7CE1ULL,
-	0x64347D271DE22754ULL, 0x26C49CCCB40811C7ULL, 0x5CBD6CC0CC10FAFCULL,
-	0x1E4D8D2B65FACC6FULL, 0xD95CAF179FC497DAULL, 0x9BAC4EFC362EA149ULL,
-	0x158E0A85C2521623ULL, 0x577EEB6E6BB820B0ULL, 0x906FC95291867B05ULL,
-	0xD29F28B9386C4D96ULL, 0xCEDBA04AD0952342ULL, 0x8C2B41A1797F15D1ULL,
-	0x4B3A639D83414E64ULL, 0x09CA82762AAB78F7ULL, 0x87E8C60FDED7CF9DULL,
-	0xC51827E4773DF90EULL, 0x020905D88D03A2BBULL, 0x40F9E43324E99428ULL,
-	0x2CFFE7D5975E55E2ULL, 0x6E0F063E3EB46371ULL, 0xA91E2402C48A38C4ULL,
-	0xEBEEC5E96D600E57ULL, 0x65CC8190991CB93DULL, 0x273C607B30F68FAEULL,
-	0xE02D4247CAC8D41BULL, 0xA2DDA3AC6322E288ULL, 0xBE992B5F8BDB8C5CULL,
-	0xFC69CAB42231BACFULL, 0x3B78E888D80FE17AULL, 0x7988096371E5D7E9ULL,
-	0xF7AA4D1A85996083ULL, 0xB55AACF12C735610ULL, 0x724B8ECDD64D0DA5ULL,
-	0x30BB6F267FA73B36ULL, 0x4AC29F2A07BFD00DULL, 0x08327EC1AE55E69EULL,
-	0xCF235CFD546BBD2BULL, 0x8DD3BD16FD818BB8ULL, 0x03F1F96F09FD3CD2ULL,
-	0x41011884A0170A41ULL, 0x86103AB85A2951F4ULL, 0xC4E0DB53F3C36767ULL,
-	0xD8A453A01B3A09B3ULL, 0x9A54B24BB2D03F20ULL, 0x5D45907748EE6495ULL,
-	0x1FB5719CE1045206ULL, 0x919735E51578E56CULL, 0xD367D40EBC92D3FFULL,
-	0x1476F63246AC884AULL, 0x568617D9EF46BED9ULL, 0xE085162AB69D5E3CULL,
-	0xA275F7C11F7768AFULL, 0x6564D5FDE549331AULL, 0x279434164CA30589ULL,
-	0xA9B6706FB8DFB2E3ULL, 0xEB46918411358470ULL, 0x2C57B3B8EB0BDFC5ULL,
-	0x6EA7525342E1E956ULL, 0x72E3DAA0AA188782ULL, 0x30133B4B03F2B111ULL,
-	0xF7021977F9CCEAA4ULL, 0xB5F2F89C5026DC37ULL, 0x3BD0BCE5A45A6B5DULL,
-	0x79205D0E0DB05DCEULL, 0xBE317F32F78E067BULL, 0xFCC19ED95E6430E8ULL,
-	0x86B86ED5267CDBD3ULL, 0xC4488F3E8F96ED40ULL, 0x0359AD0275A8B6F5ULL,
-	0x41A94CE9DC428066ULL, 0xCF8B0890283E370CULL, 0x8D7BE97B81D4019FULL,
-	0x4A6ACB477BEA5A2AULL, 0x089A2AACD2006CB9ULL, 0x14DEA25F3AF9026DULL,
-	0x562E43B4931334FEULL, 0x913F6188692D6F4BULL, 0xD3CF8063C0C759D8ULL,
-	0x5DEDC41A34BBEEB2ULL, 0x1F1D25F19D51D821ULL, 0xD80C07CD676F8394ULL,
-	0x9AFCE626CE85B507ULL,
-};
-
-uint64_t bch_crc64_update(uint64_t crc, const void *_data, size_t len)
-{
-	const unsigned char *data = _data;
-
-	while (len--) {
-		int i = ((int) (crc >> 56) ^ *data++) & 0xFF;
-		crc = crc_table[i] ^ (crc << 8);
-	}
-
-	return crc;
-}
-
-uint64_t bch_crc64(const void *data, size_t len)
-{
-	uint64_t crc = 0xffffffffffffffffULL;
-
-	crc = bch_crc64_update(crc, data, len);
-
-	return crc ^ 0xffffffffffffffffULL;
-}
diff --git a/drivers/md/bcache/util.h b/drivers/md/bcache/util.h
index cced87f8eb27..b1deec0dc958 100644
--- a/drivers/md/bcache/util.h
+++ b/drivers/md/bcache/util.h
@@ -11,6 +11,7 @@
 #include <linux/ratelimit.h>
 #include <linux/vmalloc.h>
 #include <linux/workqueue.h>
+#include <linux/crc64.h>
 
 #include "closure.h"
 
@@ -561,8 +562,4 @@ static inline sector_t bdev_sectors(struct block_device *bdev)
 {
 	return bdev->bd_inode->i_size >> 9;
 }
-
-uint64_t bch_crc64_update(uint64_t, const void *, size_t);
-uint64_t bch_crc64(const void *, size_t);
-
 #endif /* _BCACHE_UTIL_H */
-- 
2.17.1

[PATCH 4/4] lib/test_crc: Add test cases for crc calculation

[Coly Li]

This patch adds a kernel module to test the consistency of multiple crc
calculation in Linux kernel. It is enabled with CONFIG_TEST_CRC enabled.

The test results are printed into kernel message, which look like,

test_crc: crc64_le: PASSED (0x4e6b1ff972fa8c55, expval 0x4e6b1ff972fa8c55)
test_crc: crc64_le_bch: PASSED (0x0e4f1391d7a4a62e, expval 0x0e4f1391d7a4a62e)
test_crc: crc64_le_update: FAILED (0x03d4d0d85685d9a1, expval 0x3d4d0d85685d9a1f)

kernel 0day system has framework to check kernel message, then the above
result can be handled by 0day system. If crc calculation inconsistency
happens, it can be detected quite soon.

lib/test_crc.c can is a testing frame work for all crc consistency
testings. For now, there are only test caes for 3 crc routines,
- crc64_le()
- crc64_le_bch()
- crc64_le_update()

Signed-off-by: Coly Li <colyli@suse.de>
Cc: Greg Kroah-Hartman <gregkh@linuxfoundation.org>
Cc: Luis R. Rodriguez <mcgrof@suse.com>
Cc: Linus Torvalds <torvalds@linux-foundation.org>
Cc: Thomas Gleixner <tglx@linutronix.de>
Cc: Kate Stewart <kstewart@linuxfoundation.org>
---
 lib/Kconfig.debug |  11 ++++
 lib/Makefile      |   1 +
 lib/test_crc.c    | 136 ++++++++++++++++++++++++++++++++++++++++++++++
 3 files changed, 148 insertions(+)
 create mode 100644 lib/test_crc.c

diff --git a/lib/Kconfig.debug b/lib/Kconfig.debug
index 8838d1158d19..c7deb4e2e4eb 100644
--- a/lib/Kconfig.debug
+++ b/lib/Kconfig.debug
@@ -1911,6 +1911,17 @@ config TEST_SYSCTL
 
 	  If unsure, say N.
 
+config TEST_CRC
+	tristate "CRC calculation test driver"
+	default n
+	depends on CRC64
+	help
+	  This builds the "test_crc" module. This driver enables to test the
+	  CRC calculation consistency to make sure new modification does not
+	  break existing checksum calculation.
+
+	  if unsure, say N.
+
 config TEST_UDELAY
 	tristate "udelay test driver"
 	default n
diff --git a/lib/Makefile b/lib/Makefile
index 40c215181687..224d047d026a 100644
--- a/lib/Makefile
+++ b/lib/Makefile
@@ -49,6 +49,7 @@ obj-$(CONFIG_FIND_BIT_BENCHMARK) += find_bit_benchmark.o
 obj-$(CONFIG_TEST_BPF) += test_bpf.o
 obj-$(CONFIG_TEST_FIRMWARE) += test_firmware.o
 obj-$(CONFIG_TEST_SYSCTL) += test_sysctl.o
+obj-$(CONFIG_TEST_CRC) += test_crc.o
 obj-$(CONFIG_TEST_HASH) += test_hash.o test_siphash.o
 obj-$(CONFIG_TEST_KASAN) += test_kasan.o
 CFLAGS_test_kasan.o += -fno-builtin
diff --git a/lib/test_crc.c b/lib/test_crc.c
new file mode 100644
index 000000000000..3a9442252de5
--- /dev/null
+++ b/lib/test_crc.c
@@ -0,0 +1,136 @@
+// SPDX-License-Identifier: GPL-2.0
+/*
+ * CRC test driver
+ *
+ * Copyright (C) 2018 Coly Li <colyli@suse.de>
+ *
+ * This module provides an simple framework to check the consistency of
+ * Linux kernel crc calculation routines in lib/crc*.c. This driver
+ * requires CONFIG_CRC* items to be enabled if the associated routines are
+ * tested here. The test results will be printed to kernel message
+ * when this test driver is loaded.
+ *
+ * Current test routines are,
+ * - crc64_le()
+ * - crc64_le_bch()
+ * - crc64_le_update()
+ *
+ */
+
+#include <linux/init.h>
+#include <linux/list.h>
+#include <linux/module.h>
+#include <linux/printk.h>
+#include <linux/fs.h>
+#include <linux/miscdevice.h>
+#include <linux/slab.h>
+#include <linux/uaccess.h>
+#include <linux/async.h>
+#include <linux/delay.h>
+#include <linux/vmalloc.h>
+#include <linux/crc64.h>
+
+struct crc_test_record {
+
+	char	*name;
+	__le64	data[4];
+	__le64	initval;
+	__le64	expval;
+	int	(*handler)(struct crc_test_record *rec);
+};
+
+static int chk_and_msg(const char *name, __le64 crc, __le64 expval)
+{
+	int ret = 0;
+
+	if (crc == expval) {
+		pr_info("test_crc: %s: PASSED:(0x%016llx, expval 0x%016llx)",
+			name, crc, expval);
+	} else {
+		pr_err("test_crc: %s: FAILED:(0x%016llx, expval 0x%016llx)",
+			name, crc, expval);
+		ret = -EINVAL;
+	}
+
+	return ret;
+}
+
+/* Add your crc test caese here */
+static int test_crc64_le(struct crc_test_record *rec)
+{
+	__le64 crc;
+
+	crc = crc64_le(rec->data, sizeof(rec->data));
+	return chk_and_msg(rec->name, crc, rec->expval);
+
+}
+
+static int test_crc64_le_bch(struct crc_test_record *rec)
+{
+	__le64 crc;
+
+	crc = crc64_le_bch(rec->data, sizeof(rec->data));
+	return chk_and_msg(rec->name, crc, rec->expval);
+}
+
+static int test_crc64_le_update(struct crc_test_record *rec)
+{
+	__le64 crc = rec->initval;
+
+	crc = crc64_le_update(crc, rec->data, sizeof(rec->data));
+	return chk_and_msg(rec->name, crc, rec->expval);
+}
+
+/*
+ * Set up your crc test initial data here.
+ * Do not change the existing items, they are hard coded with
+ * pre-calculated values.
+ */
+static struct crc_test_record test_data[] = {
+	{ .name		= "crc64_le",
+	  .data		= { 0x42F0E1EBA9EA3693, 0x85E1C3D753D46D26,
+			    0xC711223CFA3E5BB5, 0x493366450E42ECDF },
+	  .initval	= 0,
+	  .expval	= 0xe2b9911e7b997201,
+	  .handler	= test_crc64_le,
+	},
+	{ .name		= "crc64_le_bch",
+	  .data		= { 0x42F0E1EBA9EA3693, 0x85E1C3D753D46D26,
+			    0xC711223CFA3E5BB5, 0x493366450E42ECDF },
+	  .initval	= 0,
+	  .expval	= 0xd2753a20fd862892,
+	  .handler	= test_crc64_le_bch,
+	},
+	{ .name		= "crc64_le_update",
+	  .data		= { 0x42F0E1EBA9EA3693, 0x85E1C3D753D46D26,
+			    0xC711223CFA3E5BB5, 0x493366450E42ECDF },
+	  .initval	= 0x61C8864680B583EB,
+	  .expval	= 0xb2c863673f4292bf,
+	  .handler	= test_crc64_le_update,
+	},
+	{ .name = NULL, }
+};
+
+
+static int __init test_crc_init(void)
+{
+	int i;
+	int v, ret = 0;
+
+	pr_info("Kernel crc consitency testing:");
+	for (i = 0; test_data[i].name; i++) {
+		v = test_data[i].handler(&test_data[i]);
+		if (v < 0 && ret == 0)
+			ret = -EINVAL;
+	}
+
+	return ret;
+}
+late_initcall(test_crc_init);
+
+static void __exit test_crc_exit(void) { }
+module_exit(test_crc_exit);
+
+MODULE_DESCRIPTION("CRC consistency testing driver");
+MODULE_AUTHOR("Coly Li <colyli@suse.de>");
+MODULE_LICENSE("GPL");
-- 
2.17.1

Re: [PATCH 4/4] lib/test_crc: Add test cases for crc calculation

[Randy Dunlap]

On 07/16/2018 09:55 AM, Coly Li wrote:
> This patch adds a kernel module to test the consistency of multiple crc
> calculation in Linux kernel. It is enabled with CONFIG_TEST_CRC enabled.
> 
> The test results are printed into kernel message, which look like,
> 
> test_crc: crc64_le: PASSED (0x4e6b1ff972fa8c55, expval 0x4e6b1ff972fa8c55)
> test_crc: crc64_le_bch: PASSED (0x0e4f1391d7a4a62e, expval 0x0e4f1391d7a4a62e)
> test_crc: crc64_le_update: FAILED (0x03d4d0d85685d9a1, expval 0x3d4d0d85685d9a1f)
> 
> kernel 0day system has framework to check kernel message, then the above
> result can be handled by 0day system. If crc calculation inconsistency
> happens, it can be detected quite soon.
> 
> lib/test_crc.c can is a testing frame work for all crc consistency

            drop ^^^ "can"

Well, we already have (from lib/Makefile):
obj-$(CONFIG_CRC32_SELFTEST)	+= crc32test.o

so lib/test_crc.c isn't exactly "for all crc".


> testings. For now, there are only test caes for 3 crc routines,
> - crc64_le()
> - crc64_le_bch()
> - crc64_le_update()
> 
> Signed-off-by: Coly Li <colyli@suse.de>
> Cc: Greg Kroah-Hartman <gregkh@linuxfoundation.org>
> Cc: Luis R. Rodriguez <mcgrof@suse.com>
> Cc: Linus Torvalds <torvalds@linux-foundation.org>
> Cc: Thomas Gleixner <tglx@linutronix.de>
> Cc: Kate Stewart <kstewart@linuxfoundation.org>
> ---
>  lib/Kconfig.debug |  11 ++++
>  lib/Makefile      |   1 +
>  lib/test_crc.c    | 136 ++++++++++++++++++++++++++++++++++++++++++++++
>  3 files changed, 148 insertions(+)
>  create mode 100644 lib/test_crc.c


> diff --git a/lib/test_crc.c b/lib/test_crc.c
> new file mode 100644
> index 000000000000..3a9442252de5
> --- /dev/null
> +++ b/lib/test_crc.c
> @@ -0,0 +1,136 @@
> +// SPDX-License-Identifier: GPL-2.0
> +/*
> + * CRC test driver
> + *
> + * Copyright (C) 2018 Coly Li <colyli@suse.de>
> + *
> + * This module provides an simple framework to check the consistency of
> + * Linux kernel crc calculation routines in lib/crc*.c. This driver

                   CRC

> + * requires CONFIG_CRC* items to be enabled if the associated routines are
> + * tested here. The test results will be printed to kernel message
> + * when this test driver is loaded.
> + *
> + * Current test routines are,
> + * - crc64_le()
> + * - crc64_le_bch()
> + * - crc64_le_update()
> + *
> + */
> +
> +#include <linux/init.h>
> +#include <linux/list.h>
> +#include <linux/module.h>
> +#include <linux/printk.h>
> +#include <linux/fs.h>
> +#include <linux/miscdevice.h>
> +#include <linux/slab.h>
> +#include <linux/uaccess.h>
> +#include <linux/async.h>
> +#include <linux/delay.h>
> +#include <linux/vmalloc.h>
> +#include <linux/crc64.h>
> +
> +struct crc_test_record {
> +
> +	char	*name;
> +	__le64	data[4];
> +	__le64	initval;
> +	__le64	expval;
> +	int	(*handler)(struct crc_test_record *rec);
> +};
> +
> +static int chk_and_msg(const char *name, __le64 crc, __le64 expval)
> +{
> +	int ret = 0;
> +
> +	if (crc == expval) {
> +		pr_info("test_crc: %s: PASSED:(0x%016llx, expval 0x%016llx)",
> +			name, crc, expval);
> +	} else {
> +		pr_err("test_crc: %s: FAILED:(0x%016llx, expval 0x%016llx)",
> +			name, crc, expval);

For both pr_err() lines, please print "expected" instead of "expval".

> +		ret = -EINVAL;
> +	}
> +
> +	return ret;
> +}
> +
> +/* Add your crc test caese here */

               CRC test cases

> +static int test_crc64_le(struct crc_test_record *rec)
> +{
> +	__le64 crc;
> +
> +	crc = crc64_le(rec->data, sizeof(rec->data));
> +	return chk_and_msg(rec->name, crc, rec->expval);
> +
> +}
> +
> +static int test_crc64_le_bch(struct crc_test_record *rec)
> +{
> +	__le64 crc;
> +
> +	crc = crc64_le_bch(rec->data, sizeof(rec->data));
> +	return chk_and_msg(rec->name, crc, rec->expval);
> +}
> +
> +static int test_crc64_le_update(struct crc_test_record *rec)
> +{
> +	__le64 crc = rec->initval;
> +
> +	crc = crc64_le_update(crc, rec->data, sizeof(rec->data));
> +	return chk_and_msg(rec->name, crc, rec->expval);
> +}
> +
> +/*
> + * Set up your crc test initial data here.
> + * Do not change the existing items, they are hard coded with
> + * pre-calculated values.
> + */
> +static struct crc_test_record test_data[] = {
> +	{ .name		= "crc64_le",
> +	  .data		= { 0x42F0E1EBA9EA3693, 0x85E1C3D753D46D26,
> +			    0xC711223CFA3E5BB5, 0x493366450E42ECDF },
> +	  .initval	= 0,
> +	  .expval	= 0xe2b9911e7b997201,
> +	  .handler	= test_crc64_le,
> +	},
> +	{ .name		= "crc64_le_bch",
> +	  .data		= { 0x42F0E1EBA9EA3693, 0x85E1C3D753D46D26,
> +			    0xC711223CFA3E5BB5, 0x493366450E42ECDF },
> +	  .initval	= 0,
> +	  .expval	= 0xd2753a20fd862892,
> +	  .handler	= test_crc64_le_bch,
> +	},
> +	{ .name		= "crc64_le_update",
> +	  .data		= { 0x42F0E1EBA9EA3693, 0x85E1C3D753D46D26,
> +			    0xC711223CFA3E5BB5, 0x493366450E42ECDF },
> +	  .initval	= 0x61C8864680B583EB,
> +	  .expval	= 0xb2c863673f4292bf,
> +	  .handler	= test_crc64_le_update,
> +	},
> +	{ .name = NULL, }
> +};
> +
> +
> +static int __init test_crc_init(void)
> +{
> +	int i;
> +	int v, ret = 0;
> +
> +	pr_info("Kernel crc consitency testing:");

	                CRC consistency

> +	for (i = 0; test_data[i].name; i++) {
> +		v = test_data[i].handler(&test_data[i]);
> +		if (v < 0 && ret == 0)
> +			ret = -EINVAL;
> +	}
> +
> +	return ret;
> +}
> +late_initcall(test_crc_init);
> +
> +static void __exit test_crc_exit(void) { }
> +module_exit(test_crc_exit);
> +
> +MODULE_DESCRIPTION("CRC consistency testing driver");
> +MODULE_AUTHOR("Coly Li <colyli@suse.de>");
> +MODULE_LICENSE("GPL");
> 


thanks,
-- 
~Randy

Re: [PATCH 4/4] lib/test_crc: Add test cases for crc calculation

[Coly Li]

On 2018/7/17 2:05 AM, Randy Dunlap wrote:
> On 07/16/2018 09:55 AM, Coly Li wrote:
>> This patch adds a kernel module to test the consistency of multiple crc
>> calculation in Linux kernel. It is enabled with CONFIG_TEST_CRC enabled.
>>
>> The test results are printed into kernel message, which look like,
>>
>> test_crc: crc64_le: PASSED (0x4e6b1ff972fa8c55, expval 0x4e6b1ff972fa8c55)
>> test_crc: crc64_le_bch: PASSED (0x0e4f1391d7a4a62e, expval 0x0e4f1391d7a4a62e)
>> test_crc: crc64_le_update: FAILED (0x03d4d0d85685d9a1, expval 0x3d4d0d85685d9a1f)
>>
>> kernel 0day system has framework to check kernel message, then the above
>> result can be handled by 0day system. If crc calculation inconsistency
>> happens, it can be detected quite soon.
>>

Hi Randy,

>> lib/test_crc.c can is a testing frame work for all crc consistency
> 
>             drop ^^^ "can"
> 

All the following issues are fixed in v2 series, thank you for the review.

> Well, we already have (from lib/Makefile):
> obj-$(CONFIG_CRC32_SELFTEST)	+= crc32test.o
> 
> so lib/test_crc.c isn't exactly "for all crc".
> 

My plan is to add extra consistency test cases for crc32/crc32c for
consistency testing. Consistency testing case is much simpler than the
code in crc32test.c, the results of test_crc.c are in unified format so
0day testing can handle them in a simple way.

I agree with you that 'for all crc' is inaccurate before the
crc32/crc32c test cases added into test_crc. So in v2 series, it will be
modified to 'for many crc consistency testings'.

Thanks.

Coly Li

> 
>> testings. For now, there are only test caes for 3 crc routines,
>> - crc64_le()
>> - crc64_le_bch()
>> - crc64_le_update()
>>
>> Signed-off-by: Coly Li <colyli@suse.de>
>> Cc: Greg Kroah-Hartman <gregkh@linuxfoundation.org>
>> Cc: Luis R. Rodriguez <mcgrof@suse.com>
>> Cc: Linus Torvalds <torvalds@linux-foundation.org>
>> Cc: Thomas Gleixner <tglx@linutronix.de>
>> Cc: Kate Stewart <kstewart@linuxfoundation.org>
>> ---
>>  lib/Kconfig.debug |  11 ++++
>>  lib/Makefile      |   1 +
>>  lib/test_crc.c    | 136 ++++++++++++++++++++++++++++++++++++++++++++++
>>  3 files changed, 148 insertions(+)
>>  create mode 100644 lib/test_crc.c
> 
> 
>> diff --git a/lib/test_crc.c b/lib/test_crc.c
>> new file mode 100644
>> index 000000000000..3a9442252de5
>> --- /dev/null
>> +++ b/lib/test_crc.c
>> @@ -0,0 +1,136 @@
>> +// SPDX-License-Identifier: GPL-2.0
>> +/*
>> + * CRC test driver
>> + *
>> + * Copyright (C) 2018 Coly Li <colyli@suse.de>
>> + *
>> + * This module provides an simple framework to check the consistency of
>> + * Linux kernel crc calculation routines in lib/crc*.c. This driver
> 
>                    CRC
> 
>> + * requires CONFIG_CRC* items to be enabled if the associated routines are
>> + * tested here. The test results will be printed to kernel message
>> + * when this test driver is loaded.
>> + *
>> + * Current test routines are,
>> + * - crc64_le()
>> + * - crc64_le_bch()
>> + * - crc64_le_update()
>> + *
>> + */
>> +
>> +#include <linux/init.h>
>> +#include <linux/list.h>
>> +#include <linux/module.h>
>> +#include <linux/printk.h>
>> +#include <linux/fs.h>
>> +#include <linux/miscdevice.h>
>> +#include <linux/slab.h>
>> +#include <linux/uaccess.h>
>> +#include <linux/async.h>
>> +#include <linux/delay.h>
>> +#include <linux/vmalloc.h>
>> +#include <linux/crc64.h>
>> +
>> +struct crc_test_record {
>> +
>> +	char	*name;
>> +	__le64	data[4];
>> +	__le64	initval;
>> +	__le64	expval;
>> +	int	(*handler)(struct crc_test_record *rec);
>> +};
>> +
>> +static int chk_and_msg(const char *name, __le64 crc, __le64 expval)
>> +{
>> +	int ret = 0;
>> +
>> +	if (crc == expval) {
>> +		pr_info("test_crc: %s: PASSED:(0x%016llx, expval 0x%016llx)",
>> +			name, crc, expval);
>> +	} else {
>> +		pr_err("test_crc: %s: FAILED:(0x%016llx, expval 0x%016llx)",
>> +			name, crc, expval);
> 
> For both pr_err() lines, please print "expected" instead of "expval".
> 
>> +		ret = -EINVAL;
>> +	}
>> +
>> +	return ret;
>> +}
>> +
>> +/* Add your crc test caese here */
> 
>                CRC test cases
> 
>> +static int test_crc64_le(struct crc_test_record *rec)
>> +{
>> +	__le64 crc;
>> +
>> +	crc = crc64_le(rec->data, sizeof(rec->data));
>> +	return chk_and_msg(rec->name, crc, rec->expval);
>> +
>> +}
>> +
>> +static int test_crc64_le_bch(struct crc_test_record *rec)
>> +{
>> +	__le64 crc;
>> +
>> +	crc = crc64_le_bch(rec->data, sizeof(rec->data));
>> +	return chk_and_msg(rec->name, crc, rec->expval);
>> +}
>> +
>> +static int test_crc64_le_update(struct crc_test_record *rec)
>> +{
>> +	__le64 crc = rec->initval;
>> +
>> +	crc = crc64_le_update(crc, rec->data, sizeof(rec->data));
>> +	return chk_and_msg(rec->name, crc, rec->expval);
>> +}
>> +
>> +/*
>> + * Set up your crc test initial data here.
>> + * Do not change the existing items, they are hard coded with
>> + * pre-calculated values.
>> + */
>> +static struct crc_test_record test_data[] = {
>> +	{ .name		= "crc64_le",
>> +	  .data		= { 0x42F0E1EBA9EA3693, 0x85E1C3D753D46D26,
>> +			    0xC711223CFA3E5BB5, 0x493366450E42ECDF },
>> +	  .initval	= 0,
>> +	  .expval	= 0xe2b9911e7b997201,
>> +	  .handler	= test_crc64_le,
>> +	},
>> +	{ .name		= "crc64_le_bch",
>> +	  .data		= { 0x42F0E1EBA9EA3693, 0x85E1C3D753D46D26,
>> +			    0xC711223CFA3E5BB5, 0x493366450E42ECDF },
>> +	  .initval	= 0,
>> +	  .expval	= 0xd2753a20fd862892,
>> +	  .handler	= test_crc64_le_bch,
>> +	},
>> +	{ .name		= "crc64_le_update",
>> +	  .data		= { 0x42F0E1EBA9EA3693, 0x85E1C3D753D46D26,
>> +			    0xC711223CFA3E5BB5, 0x493366450E42ECDF },
>> +	  .initval	= 0x61C8864680B583EB,
>> +	  .expval	= 0xb2c863673f4292bf,
>> +	  .handler	= test_crc64_le_update,
>> +	},
>> +	{ .name = NULL, }
>> +};
>> +
>> +
>> +static int __init test_crc_init(void)
>> +{
>> +	int i;
>> +	int v, ret = 0;
>> +
>> +	pr_info("Kernel crc consitency testing:");
> 
> 	                CRC consistency
> 
>> +	for (i = 0; test_data[i].name; i++) {
>> +		v = test_data[i].handler(&test_data[i]);
>> +		if (v < 0 && ret == 0)
>> +			ret = -EINVAL;
>> +	}
>> +
>> +	return ret;
>> +}
>> +late_initcall(test_crc_init);
>> +
>> +static void __exit test_crc_exit(void) { }
>> +module_exit(test_crc_exit);
>> +
>> +MODULE_DESCRIPTION("CRC consistency testing driver");
>> +MODULE_AUTHOR("Coly Li <colyli@suse.de>");
>> +MODULE_LICENSE("GPL");
>>
> 
> 
> thanks,
> 

Re: [PATCH 4/4] lib/test_crc: Add test cases for crc calculation

[Andy Shevchenko]

On Mon, Jul 16, 2018 at 7:55 PM, Coly Li <colyli@suse.de> wrote:
> This patch adds a kernel module to test the consistency of multiple crc
> calculation in Linux kernel. It is enabled with CONFIG_TEST_CRC enabled.
>
> The test results are printed into kernel message, which look like,
>
> test_crc: crc64_le: PASSED (0x4e6b> +
1ff972fa8c55, expval 0x4e6b1ff972fa8c55)
> test_crc: crc64_le_bch: PASSED (0x0e4f1391d7a4a62e, expval 0x0e4f1391d7a4a62e)
> test_crc: crc64_le_update: FAILED (0x03d4d0d85685d9a1, expval 0x3d4d0d85685d9a1f)
>
> kernel 0day system has framework to check kernel message, then the above
> result can be handled by 0day system. If crc calculation inconsistency
> happens, it can be detected quite soon.
>
> lib/test_crc.c can is a testing frame work for all crc consistency
> testings. For now, there are only test caes for 3 crc routines,
> - crc64_le()
> - crc64_le_bch()
> - crc64_le_update()

> +config TEST_CRC
> +       tristate "CRC calculation test driver"

> +       default n

Default default is n.

> +       depends on CRC64

> +#include <linux/init.h>
> +#include <linux/list.h>
> +#include <linux/module.h>
> +#include <linux/printk.h>
> +#include <linux/fs.h>
> +#include <linux/miscdevice.h>
> +#include <linux/slab.h>
> +#include <linux/uaccess.h>
> +#include <linux/async.h>
> +#include <linux/delay.h>
> +#include <linux/vmalloc.h>
> +#include <linux/crc64.h>

Perhaps in order?

Moreover, either init.h or module.h depending on the Kconfig (here
seems module.h is a right choice).

> +struct crc_test_record {

> +

Redundant.

> +       char    *name;
> +       __le64  data[4];
> +       __le64  initval;
> +       __le64  expval;
> +       int     (*handler)(struct crc_test_record *rec);
> +};
> +
> +static int chk_and_msg(const char *name, __le64 crc, __le64 expval)
> +{
> +       int ret = 0;
> +
> +       if (crc == expval) {
> +               pr_info("test_crc: %s: PASSED:(0x%016llx, expval 0x%016llx)",
> +                       name, crc, expval);
> +       } else {
> +               pr_err("test_crc: %s: FAILED:(0x%016llx, expval 0x%016llx)",
> +                       name, crc, expval);
> +               ret = -EINVAL;
> +       }
> +
> +       return ret;

Perhaps collect statistics instead how it's done in many other tests?

> +}
> +
> +/* Add your crc test caese here */

caese ?

> +static int test_crc64_le(struct crc_test_record *rec)
> +{
> +       __le64 crc;
> +
> +       crc = crc64_le(rec->data, sizeof(rec->data));
> +       return chk_and_msg(rec->name, crc, rec->expval);

> +

Redundant.

> +}

> +       { .name = NULL, }

Simple {} would work.

> +static int __init test_crc_init(void)
> +{
> +       int i;
> +       int v, ret = 0;
> +
> +       pr_info("Kernel crc consitency testing:");
> +       for (i = 0; test_data[i].name; i++) {

> +               v = test_data[i].handler(&test_data[i]);
> +               if (v < 0 && ret == 0)
> +                       ret = -EINVAL;

A bit strange. Anyway, better to collect statistics and print it at
the end with corresponding return code.

> +       }
> +
> +       return ret;
> +}

> +late_initcall(test_crc_init);

Why?

> +static void __exit test_crc_exit(void) { }
> +module_exit(test_crc_exit);

> +MODULE_LICENSE("GPL");

It's not the same as in SPDX.

-- 
With Best Regards,
Andy Shevchenko

Re: [PATCH 4/4] lib/test_crc: Add test cases for crc calculation

[Coly Li]

On 2018/7/17 4:47 AM, Andy Shevchenko wrote:
> On Mon, Jul 16, 2018 at 7:55 PM, Coly Li <colyli@suse.de> wrote:
>> This patch adds a kernel module to test the consistency of multiple crc
>> calculation in Linux kernel. It is enabled with CONFIG_TEST_CRC enabled.
>>
>> The test results are printed into kernel message, which look like,
>>
>> test_crc: crc64_le: PASSED (0x4e6b> +
> 1ff972fa8c55, expval 0x4e6b1ff972fa8c55)
>> test_crc: crc64_le_bch: PASSED (0x0e4f1391d7a4a62e, expval 0x0e4f1391d7a4a62e)
>> test_crc: crc64_le_update: FAILED (0x03d4d0d85685d9a1, expval 0x3d4d0d85685d9a1f)
>>
>> kernel 0day system has framework to check kernel message, then the above
>> result can be handled by 0day system. If crc calculation inconsistency
>> happens, it can be detected quite soon.
>>
>> lib/test_crc.c can is a testing frame work for all crc consistency
>> testings. For now, there are only test caes for 3 crc routines,
>> - crc64_le()
>> - crc64_le_bch()
>> - crc64_le_update()
> 
>> +config TEST_CRC
>> +       tristate "CRC calculation test driver"
> 

Hi Andy,

>> +       default n
> 
> Default default is n.
> 

I see TEST_FIRMWARE, TEST_SYSCTL, TEST_UDELAY, TEST_STATIC_KEYS arround
TEST_CRC all have 'default n', then I think to follow the style it might
be better to have 'default n' here too.


>> +       depends on CRC64
> 
>> +#include <linux/init.h>
>> +#include <linux/list.h>
>> +#include <linux/module.h>
>> +#include <linux/printk.h>
>> +#include <linux/fs.h>
>> +#include <linux/miscdevice.h>
>> +#include <linux/slab.h>
>> +#include <linux/uaccess.h>
>> +#include <linux/async.h>
>> +#include <linux/delay.h>
>> +#include <linux/vmalloc.h>
>> +#include <linux/crc64.h>
> 
> Perhaps in order?

Do you mean in alphabet order of header file names ? I will do it in v2
series.

> 
> Moreover, either init.h or module.h depending on the Kconfig (here
> seems module.h is a right choice).
> 

Sure I will keep module.h in v2 series.

>> +struct crc_test_record {
> 
>> +
> 
> Redundant.

Removed.

> 
>> +       char    *name;
>> +       __le64  data[4];
>> +       __le64  initval;
>> +       __le64  expval;
>> +       int     (*handler)(struct crc_test_record *rec);
>> +};
>> +
>> +static int chk_and_msg(const char *name, __le64 crc, __le64 expval)
>> +{
>> +       int ret = 0;
>> +
>> +       if (crc == expval) {
>> +               pr_info("test_crc: %s: PASSED:(0x%016llx, expval 0x%016llx)",
>> +                       name, crc, expval);
>> +       } else {
>> +               pr_err("test_crc: %s: FAILED:(0x%016llx, expval 0x%016llx)",
>> +                       name, crc, expval);
>> +               ret = -EINVAL;
>> +       }
>> +
>> +       return ret;
> 
> Perhaps collect statistics instead how it's done in many other tests?
> 

Good idea. I will add this in v2 series.

>> +}
>> +
>> +/* Add your crc test caese here */
> 
> caese ?

Fixed.

> 
>> +static int test_crc64_le(struct crc_test_record *rec)
>> +{
>> +       __le64 crc;
>> +
>> +       crc = crc64_le(rec->data, sizeof(rec->data));
>> +       return chk_and_msg(rec->name, crc, rec->expval);
> 
>> +
> 
> Redundant.
> 

Fixed.

>> +}
> 
>> +       { .name = NULL, }
> 
> Simple {} would work.
> 

Fixed.

>> +static int __init test_crc_init(void)
>> +{
>> +       int i;
>> +       int v, ret = 0;
>> +
>> +       pr_info("Kernel crc consitency testing:");
>> +       for (i = 0; test_data[i].name; i++) {
> 
>> +               v = test_data[i].handler(&test_data[i]);
>> +               if (v < 0 && ret == 0)
>> +                       ret = -EINVAL;
> 
> A bit strange. Anyway, better to collect statistics and print it at
> the end with corresponding return code.
> 

Sure, I will add this :-)

>> +       }
>> +
>> +       return ret;
>> +}
> 
>> +late_initcall(test_crc_init);
> 
> Why?

Oh, IMHO this is a test module, we don't need to occupy boot time and it
should be good to invoke it after other modules loaded. As I see many
other test modules do this.

> 
>> +static void __exit test_crc_exit(void) { }
>> +module_exit(test_crc_exit);
> 
>> +MODULE_LICENSE("GPL");
> 
> It's not the same as in SPDX.
> 

Nice catch, I will change it to MODULE_LICENSE("GPL v2").

Thanks for all your review !

Coly Li

Re: [PATCH 0/4] add crc64 calculation as kernel library

[Hannes Reinecke]

On 07/16/2018 06:55 PM, Coly Li wrote:
> This patch set adds basic implementation of crc64 calculation as Linux
> kernel library. Since bcache already does crc64 by itself, this patch
> set also modifies bcache code to use the new crc64 library routine.
> 
> bcache uses crc64 as storage checksum, if a change of crc lib routines
> results an inconsistent result, the unmatched checksum may make bcache
> 'think' the on-disk is corrupted, such change should be avoided or
> detected as early as possible. Therefore the last patch in this series
> adds a crc test framework, to check consistency of different calculations.
> 
> Coly Li
> 
> Cc: Andy Shevchenko <andriy.shevchenko@linux.intel.com>
> Cc: Greg Kroah-Hartman <gregkh@linuxfoundation.org>
> Cc: Luis R. Rodriguez <mcgrof@suse.com>
> Cc: Linus Torvalds <torvalds@linux-foundation.org>
> Cc: Thomas Gleixner <tglx@linutronix.de>
> Cc: Michael Lyle <mlyle@lyle.org>
> Cc: Kent Overstreet <kent.overstreet@gmail.com>
> Cc: Kate Stewart <kstewart@linuxfoundation.org>
> ---
> Andy Shevchenko (1):
>   lib/crc64: add crc64 option to lib/Kconfig
> 
> Coly Li (3):
>   lib: add crc64 calculation routines
>   bcache: use routines from lib/crc64.c for CRC64 calculation
>   lib/test_crc: Add test cases for crc calculation
> 
>  drivers/md/bcache/bcache.h  |   7 +-
>  drivers/md/bcache/btree.c   |   2 +-
>  drivers/md/bcache/request.c |   2 +-
>  drivers/md/bcache/super.c   |   5 +-
>  drivers/md/bcache/util.c    | 131 ----------------------------------
>  drivers/md/bcache/util.h    |   5 +-
>  include/linux/crc64.h       |  15 ++++
>  lib/.gitignore              |   2 +
>  lib/Kconfig                 |   8 +++
>  lib/Kconfig.debug           |  11 +++
>  lib/Makefile                |  12 ++++
>  lib/crc64.c                 |  71 +++++++++++++++++++
>  lib/gen_crc64table.c        |  76 ++++++++++++++++++++
>  lib/test_crc.c              | 136 ++++++++++++++++++++++++++++++++++++
>  14 files changed, 341 insertions(+), 142 deletions(-)
>  create mode 100644 include/linux/crc64.h
>  create mode 100644 lib/crc64.c
>  create mode 100644 lib/gen_crc64table.c
>  create mode 100644 lib/test_crc.c
> 
Actually, I would merge patch 1 & 2 together (pointless to introduce an
option for which no code exists).
Otherwise for the whole series:

Reviewed-by: Hannes Reinecke <hare@suse.com>

Cheers,

Hannes
-- 
Dr. Hannes Reinecke		   Teamlead Storage & Networking
hare@suse.de			               +49 911 74053 688
SUSE LINUX GmbH, Maxfeldstr. 5, 90409 Nürnberg
GF: F. Imendörffer, J. Smithard, J. Guild, D. Upmanyu, G. Norton
HRB 21284 (AG Nürnberg)

Re: [PATCH 0/4] add crc64 calculation as kernel library

[Coly Li]

On 2018/7/17 1:46 PM, Hannes Reinecke wrote:
> On 07/16/2018 06:55 PM, Coly Li wrote:
>> This patch set adds basic implementation of crc64 calculation as Linux
>> kernel library. Since bcache already does crc64 by itself, this patch
>> set also modifies bcache code to use the new crc64 library routine.
>>
>> bcache uses crc64 as storage checksum, if a change of crc lib routines
>> results an inconsistent result, the unmatched checksum may make bcache
>> 'think' the on-disk is corrupted, such change should be avoided or
>> detected as early as possible. Therefore the last patch in this series
>> adds a crc test framework, to check consistency of different calculations.
>>
>> Coly Li
>>
>> Cc: Andy Shevchenko <andriy.shevchenko@linux.intel.com>
>> Cc: Greg Kroah-Hartman <gregkh@linuxfoundation.org>
>> Cc: Luis R. Rodriguez <mcgrof@suse.com>
>> Cc: Linus Torvalds <torvalds@linux-foundation.org>
>> Cc: Thomas Gleixner <tglx@linutronix.de>
>> Cc: Michael Lyle <mlyle@lyle.org>
>> Cc: Kent Overstreet <kent.overstreet@gmail.com>
>> Cc: Kate Stewart <kstewart@linuxfoundation.org>
>> ---
>> Andy Shevchenko (1):
>>   lib/crc64: add crc64 option to lib/Kconfig
>>
>> Coly Li (3):
>>   lib: add crc64 calculation routines
>>   bcache: use routines from lib/crc64.c for CRC64 calculation
>>   lib/test_crc: Add test cases for crc calculation
>>
>>  drivers/md/bcache/bcache.h  |   7 +-
>>  drivers/md/bcache/btree.c   |   2 +-
>>  drivers/md/bcache/request.c |   2 +-
>>  drivers/md/bcache/super.c   |   5 +-
>>  drivers/md/bcache/util.c    | 131 ----------------------------------
>>  drivers/md/bcache/util.h    |   5 +-
>>  include/linux/crc64.h       |  15 ++++
>>  lib/.gitignore              |   2 +
>>  lib/Kconfig                 |   8 +++
>>  lib/Kconfig.debug           |  11 +++
>>  lib/Makefile                |  12 ++++
>>  lib/crc64.c                 |  71 +++++++++++++++++++
>>  lib/gen_crc64table.c        |  76 ++++++++++++++++++++
>>  lib/test_crc.c              | 136 ++++++++++++++++++++++++++++++++++++
>>  14 files changed, 341 insertions(+), 142 deletions(-)
>>  create mode 100644 include/linux/crc64.h
>>  create mode 100644 lib/crc64.c
>>  create mode 100644 lib/gen_crc64table.c
>>  create mode 100644 lib/test_crc.c
>>

Hi Hannes,

> Actually, I would merge patch 1 & 2 together (pointless to introduce an
> option for which no code exists).

The patch 1 was originally from Andy Shevchenko, and I want to keep his
contribute. If it seems not a good idea from me, I will merge them into
1 patch in v2 series.

> Otherwise for the whole series:
> 
> Reviewed-by: Hannes Reinecke <hare@suse.com>

Thanks.

Coly Li

Re: [PATCH 0/4] add crc64 calculation as kernel library

[Andy Shevchenko]

On Tue, 2018-07-17 at 14:19 +0800, Coly Li wrote:
> On 2018/7/17 1:46 PM, Hannes Reinecke wrote:

> > Actually, I would merge patch 1 & 2 together (pointless to introduce
> > an
> > option for which no code exists).
> 

I was just about to say the same.

> The patch 1 was originally from Andy Shevchenko, and I want to keep
> his
> contribute. If it seems not a good idea from me, I will merge them
> into
> 1 patch in v2 series.

We have Co-developed-by tag, for example, which you may use here (if you
choose this way, leave my SoB as well).

-- 
Andy Shevchenko <andriy.shevchenko@linux.intel.com>
Intel Finland Oy

Re: [PATCH 0/4] add crc64 calculation as kernel library

[Coly Li]

On 2018/7/17 4:37 PM, Andy Shevchenko wrote:
> On Tue, 2018-07-17 at 14:19 +0800, Coly Li wrote:
>> On 2018/7/17 1:46 PM, Hannes Reinecke wrote:
> 
>>> Actually, I would merge patch 1 & 2 together (pointless to introduce
>>> an
>>> option for which no code exists).
>>
> 
> I was just about to say the same.
> 
>> The patch 1 was originally from Andy Shevchenko, and I want to keep
>> his
>> contribute. If it seems not a good idea from me, I will merge them
>> into
>> 1 patch in v2 series.
> 
> We have Co-developed-by tag, for example, which you may use here (if you
> choose this way, leave my SoB as well).
> 
Thanks for the hint. I add a Co-developed-by tag for you :-)

Coly Li