* [PATCH v4 0/3] add crc64 calculation as kernel library
@ 2018-07-18 16:55 Coly Li
2018-07-18 16:55 ` [PATCH v4 1/3] lib: add crc64 calculation routines Coly Li
` (2 more replies)
0 siblings, 3 replies; 15+ messages in thread
From: Coly Li @ 2018-07-18 16:55 UTC (permalink / raw)
To: linux-kernel
Cc: linux-bcache, linux-block, Coly Li, Andy Shevchenko,
Greg Kroah-Hartman, Linus Torvalds, Thomas Gleixner,
Michael Lyle, Kent Overstreet, Kate Stewart, Andrew Morton,
Randy Dunlap
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.
Currently bcache is the only user of crc64 calculation, another potential
user is bcachefs which is on the way to be in mainline kernel. Therefore
it makes sense to make crc64 calculation to be a public library.
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: 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>
Cc: Andrew Morton <akpm@linux-foundation.org>
Cc: Randy Dunlap <rdunlap@infradead.org>
---
Changelog:
v4: Only keep crc64_be() in lib/crc64.c, tested bcache specific stuffs
moved back to bcache code.
Fixes all review comments of v3.
v3: Remove little endian restriction and remove 'le' from function names.
Fixes all review comments of v2
v2: Combine first two patches into one
Fixes all review comments of v1
v1: Initial version.
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/Kconfig | 1 +
drivers/md/bcache/util.c | 131 --------------------------------------
drivers/md/bcache/util.h | 21 ++++--
include/linux/crc64.h | 11 ++++
lib/.gitignore | 2 +
lib/Kconfig | 8 +++
lib/Kconfig.debug | 10 +++
lib/Makefile | 12 ++++
lib/crc64.c | 56 ++++++++++++++++
lib/gen_crc64table.c | 68 ++++++++++++++++++++
lib/test_crc.c | 93 +++++++++++++++++++++++++++
11 files changed, 278 insertions(+), 135 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
^ permalink raw reply [flat|nested] 15+ messages in thread* [PATCH v4 1/3] lib: add crc64 calculation routines 2018-07-18 16:55 [PATCH v4 0/3] add crc64 calculation as kernel library Coly Li @ 2018-07-18 16:55 ` Coly Li 2018-07-24 4:26 ` Eric Biggers 2018-07-18 16:55 ` [PATCH v4 2/3] bcache: use routines from lib/crc64.c for CRC64 calculation Coly Li 2018-07-18 16:55 ` [PATCH v4 3/3] lib/test_crc: Add test cases for crc calculation Coly Li 2 siblings, 1 reply; 15+ messages in thread From: Coly Li @ 2018-07-18 16:55 UTC (permalink / raw) To: linux-kernel Cc: linux-bcache, linux-block, Coly Li, Andy Shevchenko, Greg Kroah-Hartman, Michael Lyle, Kent Overstreet, Linus Torvalds, Thomas Gleixner, Kate Stewart, Eric Biggers, Andrew Morton, Randy Dunlap 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 64-bit 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 Currently bcache is the only user of crc64_be(), another potential user is bcachefs which is on the way to be in mainline kernel. Therefore it makes sense to move crc64 calculation into lib/crc64.c as public code. Signed-off-by: Coly Li <colyli@suse.de> Co-developed-by: Andy Shevchenko <andriy.shevchenko@linux.intel.com> Signed-off-by: Andy Shevchenko <andriy.shevchenko@linux.intel.com> Reviewed-by: Hannes Reinecke <hare@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: Linus Torvalds <torvalds@linux-foundation.org> Cc: Thomas Gleixner <tglx@linutronix.de> Cc: Kate Stewart <kstewart@linuxfoundation.org> Cc: Eric Biggers <ebiggers3@gmail.com> Cc: Andrew Morton <akpm@linux-foundation.org> Cc: Randy Dunlap <rdunlap@infradead.org> --- Changelog: v4: Only keep crc64_be() in lib/crc64.c, move rested bcache specific stuffs back to bcache code. Other fixes from the review comments of v3 v3: More fixes for review comments of v2 By review comments from Eric Biggers, current functions naming with 'le' is misleading. Remove 'le' from the crc function names, and use u64 to replace __le64 in parameters and return values. v2: Fix reivew comments of v1 v1: Initial version. include/linux/crc64.h | 11 +++++++ lib/.gitignore | 2 ++ lib/Kconfig | 8 +++++ lib/Makefile | 11 +++++++ lib/crc64.c | 56 +++++++++++++++++++++++++++++++++++ lib/gen_crc64table.c | 68 +++++++++++++++++++++++++++++++++++++++++++ 6 files changed, 156 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..1fc9f0710c10 --- /dev/null +++ b/include/linux/crc64.h @@ -0,0 +1,11 @@ +/* SPDX-License-Identifier: GPL-2.0 */ +/* + * See lib/crc64.c for the related specification and polynomical arithmetic. + */ +#ifndef _LINUX_CRC64_H +#define _LINUX_CRC64_H + +#include <linux/types.h> + +u64 __pure crc64_be(u64 crc, 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/Kconfig b/lib/Kconfig index 706836ec314d..9c10b9852563 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 here. + config CRC4 tristate "CRC4 functions" help 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..d093298ba2c6 --- /dev/null +++ b/lib/crc64.c @@ -0,0 +1,56 @@ +// SPDX-License-Identifier: GPL-2.0 +/* + * Normal 64-bit 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[256] is the lookup table of a table-driver 64-bit 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 <linux/types.h> +#include "crc64table.h" + +MODULE_DESCRIPTION("CRC64 calculations"); +MODULE_LICENSE("GPL v2"); + +/** + * crc64_be - Calculate bitwise big-endian ECMA-182 CRC64 + * @crc: seed value for computation. 0 for a new CRC computing, or the + * previous crc64 value if computing incrementally. + * @p: pointer to buffer over which CRC64 is run + * @len: length of buffer @p + */ +u64 __pure crc64_be(u64 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) ^ (*_p++)) & 0xFF; + crc = crc64table[t] ^ (crc << 8); + } + + return crc; +} +EXPORT_SYMBOL_GPL(crc64_be); diff --git a/lib/gen_crc64table.c b/lib/gen_crc64table.c new file mode 100644 index 000000000000..8296b0c3ea30 --- /dev/null +++ b/lib/gen_crc64table.c @@ -0,0 +1,68 @@ +// 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 <stdio.h> + +#include <linux/swab.h> + +#define CRC64_ECMA182_POLY 0x42F0E1EBA9EA3693ULL + +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_crc64_table(void) +{ + int i; + + printf("/* this file is generated - do not edit */\n\n"); + printf("#include <linux/types.h>\n"); + printf("#include <linux/cache.h>\n\n"); + printf("static const u64 ____cacheline_aligned crc64table[256] = {\n"); + for (i = 0; i < 256; i++) { + printf("\t0x%016" PRIx64 "ULL", crc64_table[i]); + if (i & 0x1) + printf(",\n"); + else + printf(", "); + } + printf("};\n"); +} + +int main(int argc, char *argv[]) +{ + generate_crc64_table(); + print_crc64_table(); + return 0; +} -- 2.17.1 ^ permalink raw reply related [flat|nested] 15+ messages in thread
* Re: [PATCH v4 1/3] lib: add crc64 calculation routines 2018-07-18 16:55 ` [PATCH v4 1/3] lib: add crc64 calculation routines Coly Li @ 2018-07-24 4:26 ` Eric Biggers 2018-07-24 16:29 ` Coly Li 0 siblings, 1 reply; 15+ messages in thread From: Eric Biggers @ 2018-07-24 4:26 UTC (permalink / raw) To: Coly Li Cc: linux-kernel, linux-bcache, linux-block, Andy Shevchenko, Greg Kroah-Hartman, Michael Lyle, Kent Overstreet, Linus Torvalds, Thomas Gleixner, Kate Stewart, Andrew Morton, Randy Dunlap On Thu, Jul 19, 2018 at 12:55:43AM +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 "polynomical" => "polynomial". Same everywhere else in the patches. > + * crc64table[256] is the lookup table of a table-driver 64-bit CRC "table-driver" => "table-driven" > + * 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 <linux/types.h> > +#include "crc64table.h" > + > +MODULE_DESCRIPTION("CRC64 calculations"); > +MODULE_LICENSE("GPL v2"); > + > +/** > + * crc64_be - Calculate bitwise big-endian ECMA-182 CRC64 > + * @crc: seed value for computation. 0 for a new CRC computing, or the > + * previous crc64 value if computing incrementally. "0 or (u64)~0 for a new CRC calculation". Both conventions are common in CRCs. In fact the all-ones convention is generally considered better, because it causes leading zeroes in the data to affect the checksum. > + * @p: pointer to buffer over which CRC64 is run > + * @len: length of buffer @p > + */ > +u64 __pure crc64_be(u64 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) ^ (*_p++)) & 0xFF; > + crc = crc64table[t] ^ (crc << 8); > + } > + > + return crc; > +} > +EXPORT_SYMBOL_GPL(crc64_be); > diff --git a/lib/gen_crc64table.c b/lib/gen_crc64table.c > new file mode 100644 > index 000000000000..8296b0c3ea30 > --- /dev/null > +++ b/lib/gen_crc64table.c > @@ -0,0 +1,68 @@ > +// SPDX-License-Identifier: GPL-2.0 > +/* > + * Generate lookup table for the talbe-driven CRC64 calculation. "talbe-driven" => "table-driven" > + * > + * 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. "table-driver" => "table-driven" > + * > + * 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 <stdio.h> > + > +#include <linux/swab.h> > + > +#define CRC64_ECMA182_POLY 0x42F0E1EBA9EA3693ULL > + > +static int64_t crc64_table[256] = {0}; This really should be uint64_t, not int64_t. > + > +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_crc64_table(void) > +{ > + int i; > + > + printf("/* this file is generated - do not edit */\n\n"); > + printf("#include <linux/types.h>\n"); > + printf("#include <linux/cache.h>\n\n"); > + printf("static const u64 ____cacheline_aligned crc64table[256] = {\n"); > + for (i = 0; i < 256; i++) { > + printf("\t0x%016" PRIx64 "ULL", crc64_table[i]); > + if (i & 0x1) > + printf(",\n"); > + else > + printf(", "); > + } > + printf("};\n"); > +} > + > +int main(int argc, char *argv[]) > +{ > + generate_crc64_table(); > + print_crc64_table(); > + return 0; > +} > -- > 2.17.1 > - Eric ^ permalink raw reply [flat|nested] 15+ messages in thread
* Re: [PATCH v4 1/3] lib: add crc64 calculation routines 2018-07-24 4:26 ` Eric Biggers @ 2018-07-24 16:29 ` Coly Li 2018-07-24 17:06 ` Andy Shevchenko 0 siblings, 1 reply; 15+ messages in thread From: Coly Li @ 2018-07-24 16:29 UTC (permalink / raw) To: Eric Biggers Cc: linux-kernel, linux-bcache, linux-block, Andy Shevchenko, Greg Kroah-Hartman, Michael Lyle, Kent Overstreet, Linus Torvalds, Thomas Gleixner, Kate Stewart, Andrew Morton, Randy Dunlap On 2018/7/24 12:26 PM, Eric Biggers wrote: > On Thu, Jul 19, 2018 at 12:55:43AM +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 > > "polynomical" => "polynomial". Same everywhere else in the patches. > Hi Eric, Thanks for your careful review. I will post a fixing patch to fix all these issues. Coly Li >> + * crc64table[256] is the lookup table of a table-driver 64-bit CRC > > "table-driver" => "table-driven" > >> + * 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 <linux/types.h> >> +#include "crc64table.h" >> + >> +MODULE_DESCRIPTION("CRC64 calculations"); >> +MODULE_LICENSE("GPL v2"); >> + >> +/** >> + * crc64_be - Calculate bitwise big-endian ECMA-182 CRC64 >> + * @crc: seed value for computation. 0 for a new CRC computing, or the >> + * previous crc64 value if computing incrementally. > > "0 or (u64)~0 for a new CRC calculation". Both conventions are common in CRCs. > In fact the all-ones convention is generally considered better, because it > causes leading zeroes in the data to affect the checksum. > >> + * @p: pointer to buffer over which CRC64 is run >> + * @len: length of buffer @p >> + */ >> +u64 __pure crc64_be(u64 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) ^ (*_p++)) & 0xFF; >> + crc = crc64table[t] ^ (crc << 8); >> + } >> + >> + return crc; >> +} >> +EXPORT_SYMBOL_GPL(crc64_be); >> diff --git a/lib/gen_crc64table.c b/lib/gen_crc64table.c >> new file mode 100644 >> index 000000000000..8296b0c3ea30 >> --- /dev/null >> +++ b/lib/gen_crc64table.c >> @@ -0,0 +1,68 @@ >> +// SPDX-License-Identifier: GPL-2.0 >> +/* >> + * Generate lookup table for the talbe-driven CRC64 calculation. > > "talbe-driven" => "table-driven" > >> + * >> + * 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. > > "table-driver" => "table-driven" > >> + * >> + * 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 <stdio.h> >> + >> +#include <linux/swab.h> >> + >> +#define CRC64_ECMA182_POLY 0x42F0E1EBA9EA3693ULL >> + >> +static int64_t crc64_table[256] = {0}; > > This really should be uint64_t, not int64_t. > >> + >> +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_crc64_table(void) >> +{ >> + int i; >> + >> + printf("/* this file is generated - do not edit */\n\n"); >> + printf("#include <linux/types.h>\n"); >> + printf("#include <linux/cache.h>\n\n"); >> + printf("static const u64 ____cacheline_aligned crc64table[256] = {\n"); >> + for (i = 0; i < 256; i++) { >> + printf("\t0x%016" PRIx64 "ULL", crc64_table[i]); >> + if (i & 0x1) >> + printf(",\n"); >> + else >> + printf(", "); >> + } >> + printf("};\n"); >> +} >> + >> +int main(int argc, char *argv[]) >> +{ >> + generate_crc64_table(); >> + print_crc64_table(); >> + return 0; >> +} >> -- >> 2.17.1 >> > > - Eric > ^ permalink raw reply [flat|nested] 15+ messages in thread
* Re: [PATCH v4 1/3] lib: add crc64 calculation routines 2018-07-24 16:29 ` Coly Li @ 2018-07-24 17:06 ` Andy Shevchenko 2018-07-25 2:37 ` Coly Li 0 siblings, 1 reply; 15+ messages in thread From: Andy Shevchenko @ 2018-07-24 17:06 UTC (permalink / raw) To: Coly Li, Eric Biggers Cc: linux-kernel, linux-bcache, linux-block, Greg Kroah-Hartman, Michael Lyle, Kent Overstreet, Linus Torvalds, Thomas Gleixner, Kate Stewart, Andrew Morton, Randy Dunlap On Wed, 2018-07-25 at 00:29 +0800, Coly Li wrote: > On 2018/7/24 12:26 PM, Eric Biggers wrote: > > On Thu, Jul 19, 2018 at 12:55:43AM +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 > > > > "polynomical" => "polynomial". Same everywhere else in the patches. > > > > Hi Eric, > > Thanks for your careful review. I will post a fixing patch to fix all > these issues. IIUC this series in Andrew's quilt. So, it's still possible to replace it with better one, I suppose. Ask Andrew (at least I remember recent case where he just replaced series by fixed one). -- Andy Shevchenko <andriy.shevchenko@linux.intel.com> Intel Finland Oy ^ permalink raw reply [flat|nested] 15+ messages in thread
* Re: [PATCH v4 1/3] lib: add crc64 calculation routines 2018-07-24 17:06 ` Andy Shevchenko @ 2018-07-25 2:37 ` Coly Li 2018-07-25 21:22 ` Andrew Morton 0 siblings, 1 reply; 15+ messages in thread From: Coly Li @ 2018-07-25 2:37 UTC (permalink / raw) To: Andrew Morton Cc: Andy Shevchenko, Eric Biggers, linux-kernel, linux-bcache, linux-block, Greg Kroah-Hartman, Michael Lyle, Kent Overstreet, Linus Torvalds, Thomas Gleixner, Kate Stewart, Randy Dunlap On 2018/7/25 1:06 AM, Andy Shevchenko wrote: > On Wed, 2018-07-25 at 00:29 +0800, Coly Li wrote: >> On 2018/7/24 12:26 PM, Eric Biggers wrote: >>> On Thu, Jul 19, 2018 at 12:55:43AM +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 >>> >>> "polynomical" => "polynomial". Same everywhere else in the patches. >>> >> >> Hi Eric, >> >> Thanks for your careful review. I will post a fixing patch to fix all >> these issues. > > IIUC this series in Andrew's quilt. So, it's still possible to replace > it with better one, I suppose. Ask Andrew (at least I remember recent > case where he just replaced series by fixed one). Hi Andrew, It seems there should be some fix/update for this series. I see current series is in linux-next for now. If I want to add the fix, should I post a new version of the series, or the incremental patches to fix current series ? Thanks in advance for your advice. Coly Li ^ permalink raw reply [flat|nested] 15+ messages in thread
* Re: [PATCH v4 1/3] lib: add crc64 calculation routines 2018-07-25 2:37 ` Coly Li @ 2018-07-25 21:22 ` Andrew Morton 2018-07-26 3:28 ` Coly Li 0 siblings, 1 reply; 15+ messages in thread From: Andrew Morton @ 2018-07-25 21:22 UTC (permalink / raw) To: Coly Li Cc: Andy Shevchenko, Eric Biggers, linux-kernel, linux-bcache, linux-block, Greg Kroah-Hartman, Michael Lyle, Kent Overstreet, Linus Torvalds, Thomas Gleixner, Kate Stewart, Randy Dunlap On Wed, 25 Jul 2018 10:37:23 +0800 Coly Li <colyli@suse.de> wrote: > > IIUC this series in Andrew's quilt. So, it's still possible to replace > > it with better one, I suppose. Ask Andrew (at least I remember recent > > case where he just replaced series by fixed one). > > Hi Andrew, > > It seems there should be some fix/update for this series. I see current > series is in linux-next for now. If I want to add the fix, should I post > a new version of the series, or the incremental patches to fix current > series ? mm... it sounds like the changes will be large, so probably a new series would be better at this early stage. If the changes are small then little fixup patches would be nicer to the people who have already reviewed v1. ^ permalink raw reply [flat|nested] 15+ messages in thread
* Re: [PATCH v4 1/3] lib: add crc64 calculation routines 2018-07-25 21:22 ` Andrew Morton @ 2018-07-26 3:28 ` Coly Li 0 siblings, 0 replies; 15+ messages in thread From: Coly Li @ 2018-07-26 3:28 UTC (permalink / raw) To: Andrew Morton Cc: Andy Shevchenko, Eric Biggers, linux-kernel, linux-bcache, linux-block, Greg Kroah-Hartman, Michael Lyle, Kent Overstreet, Linus Torvalds, Thomas Gleixner, Kate Stewart, Randy Dunlap On 2018/7/26 5:22 AM, Andrew Morton wrote: > On Wed, 25 Jul 2018 10:37:23 +0800 Coly Li <colyli@suse.de> wrote: > >>> IIUC this series in Andrew's quilt. So, it's still possible to replace >>> it with better one, I suppose. Ask Andrew (at least I remember recent >>> case where he just replaced series by fixed one). >> >> Hi Andrew, >> >> It seems there should be some fix/update for this series. I see current >> series is in linux-next for now. If I want to add the fix, should I post >> a new version of the series, or the incremental patches to fix current >> series ? > > mm... it sounds like the changes will be large, so probably a new > series would be better at this early stage. If the changes are small > then little fixup patches would be nicer to the people who have already > reviewed v1. > Yes, it is large (patch 3/3 will be removed). So I will post a new series to replace current series. Thanks for the hint. Coly Li ^ permalink raw reply [flat|nested] 15+ messages in thread
* [PATCH v4 2/3] bcache: use routines from lib/crc64.c for CRC64 calculation 2018-07-18 16:55 [PATCH v4 0/3] add crc64 calculation as kernel library Coly Li 2018-07-18 16:55 ` [PATCH v4 1/3] lib: add crc64 calculation routines Coly Li @ 2018-07-18 16:55 ` Coly Li 2018-07-18 16:55 ` [PATCH v4 3/3] lib/test_crc: Add test cases for crc calculation Coly Li 2 siblings, 0 replies; 15+ messages in thread From: Coly Li @ 2018-07-18 16:55 UTC (permalink / raw) To: linux-kernel Cc: linux-bcache, linux-block, Coly Li, Michael Lyle, Kent Overstreet, Linus Torvalds, Thomas Gleixner, Kate Stewart, Andrew Morton, Randy Dunlap 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> Reviewed-by: Hannes Reinecke <hare@suse.de> Reviewed-by: 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> Cc: Andrew Morton <akpm@linux-foundation.org> Cc: Randy Dunlap <rdunlap@infradead.org> --- Changelog: v3: Only call crc64_be() from lib/crc64.c, and implemennt bch_crc64() and bch_crc64_update() based on crc64_be(). v2: Call crc64_le_bch(), crc64_le_update() from lib/crc64.c v1: Initial version drivers/md/bcache/Kconfig | 1 + drivers/md/bcache/util.c | 131 -------------------------------------- drivers/md/bcache/util.h | 21 ++++-- 3 files changed, 18 insertions(+), 135 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/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..a1579e28049f 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" @@ -542,6 +543,22 @@ dup: \ #define RB_PREV(ptr, member) \ container_of_or_null(rb_prev(&(ptr)->member), typeof(*ptr), member) +static inline uint64_t bch_crc64(const void *p, size_t len) +{ + uint64_t crc = 0xffffffffffffffffULL; + + crc = crc64_be(crc, p, len); + return crc ^ 0xffffffffffffffffULL; +} + +static inline uint64_t bch_crc64_update(uint64_t crc, + const void *p, + size_t len) +{ + crc = crc64_be(crc, p, len); + return crc; +} + /* Does linear interpolation between powers of two */ static inline unsigned fract_exp_two(unsigned x, unsigned fract_bits) { @@ -561,8 +578,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 ^ permalink raw reply related [flat|nested] 15+ messages in thread
* [PATCH v4 3/3] lib/test_crc: Add test cases for crc calculation 2018-07-18 16:55 [PATCH v4 0/3] add crc64 calculation as kernel library Coly Li 2018-07-18 16:55 ` [PATCH v4 1/3] lib: add crc64 calculation routines Coly Li 2018-07-18 16:55 ` [PATCH v4 2/3] bcache: use routines from lib/crc64.c for CRC64 calculation Coly Li @ 2018-07-18 16:55 ` Coly Li 2018-07-18 21:24 ` Andrew Morton 2018-07-24 4:44 ` Eric Biggers 2 siblings, 2 replies; 15+ messages in thread From: Coly Li @ 2018-07-18 16:55 UTC (permalink / raw) To: linux-kernel Cc: linux-bcache, linux-block, Coly Li, Greg Kroah-Hartman, Linus Torvalds, Thomas Gleixner, Kate Stewart, Andrew Morton, Randy Dunlap, Andy Shevchenko, Noah Massey 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_be: FAILED (0x03d4d0d85685d9a1, expected 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 is a testing frame work for many crc consistency testings. For now, there is only one test caes for crc64_be(). Signed-off-by: Coly Li <colyli@suse.de> Reviewed-by: Hannes Reinecke <hare@suse.de> Cc: Greg Kroah-Hartman <gregkh@linuxfoundation.org> Cc: Linus Torvalds <torvalds@linux-foundation.org> Cc: Thomas Gleixner <tglx@linutronix.de> Cc: Kate Stewart <kstewart@linuxfoundation.org> Cc: Andrew Morton <akpm@linux-foundation.org> Cc: Randy Dunlap <rdunlap@infradead.org> Cc: Andy Shevchenko <andriy.shevchenko@linux.intel.com> Cc: Noah Massey <noah.massey@gmail.com> --- Changelog: v4: Improve error statistic and failure message display by suggestion from Andy Shevchenko and Noah Massey. Fixes for review commennts of v3 v3: Add test cases passed/failed statistic More fixes for review comments of v2 v2: Fixes for review comments of v1 v1: Initial version. lib/Kconfig.debug | 10 +++++ lib/Makefile | 1 + lib/test_crc.c | 93 +++++++++++++++++++++++++++++++++++++++++++++++ 3 files changed, 104 insertions(+) create mode 100644 lib/test_crc.c diff --git a/lib/Kconfig.debug b/lib/Kconfig.debug index 8838d1158d19..a9c1de0c2a7d 100644 --- a/lib/Kconfig.debug +++ b/lib/Kconfig.debug @@ -1911,6 +1911,16 @@ config TEST_SYSCTL If unsure, say N. +config TEST_CRC + tristate "CRC calculation test driver" + 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..324e8ad419d7 --- /dev/null +++ b/lib/test_crc.c @@ -0,0 +1,93 @@ +// 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_be() + */ + +#include <linux/module.h> +#include <linux/crc64.h> + +struct crc_test_record { + char *name; + u64 data[4]; + u64 initval; + u64 expval; + void (*handler)(struct crc_test_record *rec); +}; + +int failed_tests; +int total_tests; + +static void chk_and_msg(const char *name, u64 crc, u64 expval) +{ + total_tests++; + if (crc == expval) + return; + + pr_err("test_crc: %s: FAILED:(0x%016llx, expected 0x%016llx)\n", + name, crc, expval); + failed_tests++; +} + +/* Add your crc test cases here */ +static void test_crc64_be(struct crc_test_record *rec) +{ + u64 crc; + + crc = crc64_be(rec->initval, rec->data, sizeof(rec->data)); + 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_be", + .data = { 0x42F0E1EBA9EA3693, 0x85E1C3D753D46D26, + 0xC711223CFA3E5BB5, 0x493366450E42ECDF }, + .initval = 0x61C8864680B583EB, + .expval = 0xb2c863673f4292bf, + .handler = test_crc64_be, + }, + {} +}; + +static int __init test_crc_init(void) +{ + int i; + + failed_tests = 0; + total_tests = 0; + + pr_info("Kernel CRC consistency testing:\n"); + for (i = 0; test_data[i].name; i++) + test_data[i].handler(&test_data[i]); + + if (failed_tests == 0) + pr_info("test_crc: all %d tests passed\n", i); + else + pr_err("test_crc: %d cases tested, %d passed, %d failed\n", + total_tests, total_tests - failed_tests, failed_tests); + + return (failed_tests == 0) ? 0 : -EINVAL; +} +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 v2"); -- 2.17.1 ^ permalink raw reply related [flat|nested] 15+ messages in thread
* Re: [PATCH v4 3/3] lib/test_crc: Add test cases for crc calculation 2018-07-18 16:55 ` [PATCH v4 3/3] lib/test_crc: Add test cases for crc calculation Coly Li @ 2018-07-18 21:24 ` Andrew Morton 2018-07-24 4:44 ` Eric Biggers 1 sibling, 0 replies; 15+ messages in thread From: Andrew Morton @ 2018-07-18 21:24 UTC (permalink / raw) To: Coly Li Cc: linux-kernel, linux-bcache, linux-block, Greg Kroah-Hartman, Linus Torvalds, Thomas Gleixner, Kate Stewart, Randy Dunlap, Andy Shevchenko, Noah Massey On Thu, 19 Jul 2018 00:55:45 +0800 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_be: FAILED (0x03d4d0d85685d9a1, expected 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 is a testing frame work for many crc consistency > testings. For now, there is only one test caes for crc64_be(). Some tweaks. From: Andrew Morton <akpm@linux-foundation.org> Subject: lib-test_crc-add-test-cases-for-crc-calculation-fix make two globals static, regularize code layout, remove unneeded initialization Cc: Coly Li <colyli@suse.de> Signed-off-by: Andrew Morton <akpm@linux-foundation.org> --- lib/test_crc.c | 11 +++++------ 1 file changed, 5 insertions(+), 6 deletions(-) diff -puN lib/test_crc.c~lib-test_crc-add-test-cases-for-crc-calculation-fix lib/test_crc.c --- a/lib/test_crc.c~lib-test_crc-add-test-cases-for-crc-calculation-fix +++ a/lib/test_crc.c @@ -25,8 +25,8 @@ struct crc_test_record { void (*handler)(struct crc_test_record *rec); }; -int failed_tests; -int total_tests; +static int failed_tests; +static int total_tests; static void chk_and_msg(const char *name, u64 crc, u64 expval) { @@ -68,9 +68,6 @@ static int __init test_crc_init(void) { int i; - failed_tests = 0; - total_tests = 0; - pr_info("Kernel CRC consistency testing:\n"); for (i = 0; test_data[i].name; i++) test_data[i].handler(&test_data[i]); @@ -85,7 +82,9 @@ static int __init test_crc_init(void) } late_initcall(test_crc_init); -static void __exit test_crc_exit(void) { } +static void __exit test_crc_exit(void) +{ +} module_exit(test_crc_exit); MODULE_DESCRIPTION("CRC consistency testing driver"); _ ^ permalink raw reply [flat|nested] 15+ messages in thread
* Re: [PATCH v4 3/3] lib/test_crc: Add test cases for crc calculation 2018-07-18 16:55 ` [PATCH v4 3/3] lib/test_crc: Add test cases for crc calculation Coly Li 2018-07-18 21:24 ` Andrew Morton @ 2018-07-24 4:44 ` Eric Biggers 2018-07-24 16:28 ` Coly Li 1 sibling, 1 reply; 15+ messages in thread From: Eric Biggers @ 2018-07-24 4:44 UTC (permalink / raw) To: Coly Li Cc: linux-kernel, linux-bcache, linux-block, Greg Kroah-Hartman, Linus Torvalds, Thomas Gleixner, Kate Stewart, Andrew Morton, Randy Dunlap, Andy Shevchenko, Noah Massey On Thu, Jul 19, 2018 at 12:55:45AM +0800, 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_be: FAILED (0x03d4d0d85685d9a1, expected 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 is a testing frame work for many crc consistency > testings. For now, there is only one test caes for crc64_be(). Are you aware there's already a CRC-32 test module: CONFIG_CRC32_SELFTEST and lib/crc32test.c? Confusingly, your patch uses a different naming convention for the new CRC-64 one, and puts the Kconfig option in a different place, and makes it sound like it's a generic test for all CRC implementations rather than just the CRC-64 one. Please use the existing convention (i.e. add CONFIG_CRC64_SELFTEST and lib/crc64test.c) unless you have a strong argument for why it should be done differently. (And I don't think it makes sense to combine all CRC tests into one module, since you should be able to e.g. enable just CRC32 and CRC32_SELFTEST without also pulling in a dependency on all the other CRC variants.) > +/* Add your crc test cases here */ > +static void test_crc64_be(struct crc_test_record *rec) > +{ > + u64 crc; > + > + crc = crc64_be(rec->initval, rec->data, sizeof(rec->data)); > + 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_be", > + .data = { 0x42F0E1EBA9EA3693, 0x85E1C3D753D46D26, > + 0xC711223CFA3E5BB5, 0x493366450E42ECDF }, > + .initval = 0x61C8864680B583EB, > + .expval = 0xb2c863673f4292bf, > + .handler = test_crc64_be, > + }, > + {} > +}; This is incorrect; the test is checksumming data that has a CPU-specific endianness. So, it will fail on big-endian systems. The data needs to be declared as a byte or char array instead. See e.g. what crypto/testmgr.h does for crypto API algorithms. Also please mark the test data structures 'const'. - Eric ^ permalink raw reply [flat|nested] 15+ messages in thread
* Re: [PATCH v4 3/3] lib/test_crc: Add test cases for crc calculation 2018-07-24 4:44 ` Eric Biggers @ 2018-07-24 16:28 ` Coly Li 2018-07-24 17:39 ` Eric Biggers 0 siblings, 1 reply; 15+ messages in thread From: Coly Li @ 2018-07-24 16:28 UTC (permalink / raw) To: Eric Biggers Cc: linux-kernel, linux-bcache, linux-block, Greg Kroah-Hartman, Linus Torvalds, Thomas Gleixner, Kate Stewart, Andrew Morton, Randy Dunlap, Andy Shevchenko, Noah Massey On 2018/7/24 12:44 PM, Eric Biggers wrote: > On Thu, Jul 19, 2018 at 12:55:45AM +0800, 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_be: FAILED (0x03d4d0d85685d9a1, expected 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 is a testing frame work for many crc consistency >> testings. For now, there is only one test caes for crc64_be(). > > Are you aware there's already a CRC-32 test module: CONFIG_CRC32_SELFTEST and > lib/crc32test.c? Confusingly, your patch uses a different naming convention for > the new CRC-64 one, and puts the Kconfig option in a different place, and makes > it sound like it's a generic test for all CRC implementations rather than just > the CRC-64 one. Please use the existing convention (i.e. add > CONFIG_CRC64_SELFTEST and lib/crc64test.c) unless you have a strong argument for > why it should be done differently. > > (And I don't think it makes sense to combine all CRC tests into one module, > since you should be able to e.g. enable just CRC32 and CRC32_SELFTEST without > also pulling in a dependency on all the other CRC variants.) > Hi Eric, The purpose of test_crc is to provide a unified crc calculation consistency testing for 0day. So far it is only crc64, and I will add more test cases later. I see there is crc-32 test module, which does more testing then consistency check, and no unified format for 0day system to detect. This is why people suggested me to add this test framework. >> +/* Add your crc test cases here */ >> +static void test_crc64_be(struct crc_test_record *rec) >> +{ >> + u64 crc; >> + >> + crc = crc64_be(rec->initval, rec->data, sizeof(rec->data)); >> + 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_be", >> + .data = { 0x42F0E1EBA9EA3693, 0x85E1C3D753D46D26, >> + 0xC711223CFA3E5BB5, 0x493366450E42ECDF }, >> + .initval = 0x61C8864680B583EB, >> + .expval = 0xb2c863673f4292bf, >> + .handler = test_crc64_be, >> + }, >> + {} >> +}; > > This is incorrect; the test is checksumming data that has a CPU-specific > endianness. So, it will fail on big-endian systems. The data needs to be > declared as a byte or char array instead. See e.g. what crypto/testmgr.h does > for crypto API algorithms. > > Also please mark the test data structures 'const'. Sure, I will send fix patches (not rebase the posted patches because they are in linux-next for now) soon. Thanks for your comments. Coly Li ^ permalink raw reply [flat|nested] 15+ messages in thread
* Re: [PATCH v4 3/3] lib/test_crc: Add test cases for crc calculation 2018-07-24 16:28 ` Coly Li @ 2018-07-24 17:39 ` Eric Biggers 2018-07-25 4:07 ` Coly Li 0 siblings, 1 reply; 15+ messages in thread From: Eric Biggers @ 2018-07-24 17:39 UTC (permalink / raw) To: Coly Li Cc: linux-kernel, linux-bcache, linux-block, Greg Kroah-Hartman, Linus Torvalds, Thomas Gleixner, Kate Stewart, Andrew Morton, Randy Dunlap, Andy Shevchenko, Noah Massey On Wed, Jul 25, 2018 at 12:28:15AM +0800, Coly Li wrote: > On 2018/7/24 12:44 PM, Eric Biggers wrote: > > On Thu, Jul 19, 2018 at 12:55:45AM +0800, 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_be: FAILED (0x03d4d0d85685d9a1, expected 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 is a testing frame work for many crc consistency > >> testings. For now, there is only one test caes for crc64_be(). > > > > Are you aware there's already a CRC-32 test module: CONFIG_CRC32_SELFTEST and > > lib/crc32test.c? Confusingly, your patch uses a different naming convention for > > the new CRC-64 one, and puts the Kconfig option in a different place, and makes > > it sound like it's a generic test for all CRC implementations rather than just > > the CRC-64 one. Please use the existing convention (i.e. add > > CONFIG_CRC64_SELFTEST and lib/crc64test.c) unless you have a strong argument for > > why it should be done differently. > > > > (And I don't think it makes sense to combine all CRC tests into one module, > > since you should be able to e.g. enable just CRC32 and CRC32_SELFTEST without > > also pulling in a dependency on all the other CRC variants.) > > > > Hi Eric, > > The purpose of test_crc is to provide a unified crc calculation > consistency testing for 0day. So far it is only crc64, and I will add > more test cases later. I see there is crc-32 test module, which does > more testing then consistency check, and no unified format for 0day > system to detect. This is why people suggested me to add this test > framework. > Actually the code in crc32test is nearly the same as what you're adding for CRC-64. The CRC-32 test is longer because it's testing two different polynomials "crc32" and "crc32c" as well as combining CRC's; neither of those is relevant for CRC-64 yet, as you've implemented just one polynomial and there is no function provided to combine CRC64's yet. The CRC-32 test also tests performance, but if you don't believe CRC performance should be tested, then you should remove the performance test from the existing module rather than implementing a brand new test module just to remove the performance test... I still don't understand why you decided to do things differently for CRC-64, when there were already CRC-32 tests that used a certain convention for the Kconfig option, filename, etc. It's inconsistent and confusing. Again, please use the existing convention unless you have a strong argument for why it should be done differently. (And if you do want to do things differently, the existing test should be converted first.) - Eric ^ permalink raw reply [flat|nested] 15+ messages in thread
* Re: [PATCH v4 3/3] lib/test_crc: Add test cases for crc calculation 2018-07-24 17:39 ` Eric Biggers @ 2018-07-25 4:07 ` Coly Li 0 siblings, 0 replies; 15+ messages in thread From: Coly Li @ 2018-07-25 4:07 UTC (permalink / raw) To: Eric Biggers Cc: linux-kernel, linux-bcache, linux-block, Greg Kroah-Hartman, Linus Torvalds, Thomas Gleixner, Kate Stewart, Andrew Morton, Randy Dunlap, Andy Shevchenko, Noah Massey On 2018/7/25 1:39 AM, Eric Biggers wrote: > On Wed, Jul 25, 2018 at 12:28:15AM +0800, Coly Li wrote: >> On 2018/7/24 12:44 PM, Eric Biggers wrote: >>> On Thu, Jul 19, 2018 at 12:55:45AM +0800, 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_be: FAILED (0x03d4d0d85685d9a1, expected 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 is a testing frame work for many crc consistency >>>> testings. For now, there is only one test caes for crc64_be(). >>> >>> Are you aware there's already a CRC-32 test module: CONFIG_CRC32_SELFTEST and >>> lib/crc32test.c? Confusingly, your patch uses a different naming convention for >>> the new CRC-64 one, and puts the Kconfig option in a different place, and makes >>> it sound like it's a generic test for all CRC implementations rather than just >>> the CRC-64 one. Please use the existing convention (i.e. add >>> CONFIG_CRC64_SELFTEST and lib/crc64test.c) unless you have a strong argument for >>> why it should be done differently. >>> >>> (And I don't think it makes sense to combine all CRC tests into one module, >>> since you should be able to e.g. enable just CRC32 and CRC32_SELFTEST without >>> also pulling in a dependency on all the other CRC variants.) >>> >> >> Hi Eric, >> >> The purpose of test_crc is to provide a unified crc calculation >> consistency testing for 0day. So far it is only crc64, and I will add >> more test cases later. I see there is crc-32 test module, which does >> more testing then consistency check, and no unified format for 0day >> system to detect. This is why people suggested me to add this test >> framework. >> > > Actually the code in crc32test is nearly the same as what you're adding for > CRC-64. The CRC-32 test is longer because it's testing two different > polynomials "crc32" and "crc32c" as well as combining CRC's; neither of those is > relevant for CRC-64 yet, as you've implemented just one polynomial and there is > no function provided to combine CRC64's yet. The CRC-32 test also tests > performance, but if you don't believe CRC performance should be tested, then you > should remove the performance test from the existing module rather than > implementing a brand new test module just to remove the performance test... > > I still don't understand why you decided to do things differently for CRC-64, > when there were already CRC-32 tests that used a certain convention for the > Kconfig option, filename, etc. It's inconsistent and confusing. Again, please > use the existing convention unless you have a strong argument for why it should > be done differently. (And if you do want to do things differently, the existing > test should be converted first.) Hi Eric, So far only crc32 has selftesting code, it is hardly to be a convention IMHO. Anyway, considerate your comments and suggestion, I feel crc_test can be a separate patch from this series. Later I will post another series, which unify all crc test together into test_crc, including other crc calculations which don't have their testing code. Thanks. Coly Li ^ permalink raw reply [flat|nested] 15+ messages in thread
end of thread, other threads:[~2018-07-26 3:29 UTC | newest] Thread overview: 15+ messages (download: mbox.gz / follow: Atom feed) -- links below jump to the message on this page -- 2018-07-18 16:55 [PATCH v4 0/3] add crc64 calculation as kernel library Coly Li 2018-07-18 16:55 ` [PATCH v4 1/3] lib: add crc64 calculation routines Coly Li 2018-07-24 4:26 ` Eric Biggers 2018-07-24 16:29 ` Coly Li 2018-07-24 17:06 ` Andy Shevchenko 2018-07-25 2:37 ` Coly Li 2018-07-25 21:22 ` Andrew Morton 2018-07-26 3:28 ` Coly Li 2018-07-18 16:55 ` [PATCH v4 2/3] bcache: use routines from lib/crc64.c for CRC64 calculation Coly Li 2018-07-18 16:55 ` [PATCH v4 3/3] lib/test_crc: Add test cases for crc calculation Coly Li 2018-07-18 21:24 ` Andrew Morton 2018-07-24 4:44 ` Eric Biggers 2018-07-24 16:28 ` Coly Li 2018-07-24 17:39 ` Eric Biggers 2018-07-25 4:07 ` Coly Li
This is a public inbox, see mirroring instructions for how to clone and mirror all data and code used for this inbox; as well as URLs for NNTP newsgroup(s).