* [PATCH v5 0/2] add crc64 calculation as kernel library
@ 2018-07-26 5:33 Coly Li
2018-07-26 5:33 ` [PATCH v5 1/2] lib: add crc64 calculation routines Coly Li
2018-07-26 5:33 ` [PATCH v5 2/2] bcache: use routines from lib/crc64.c for CRC64 calculation Coly Li
0 siblings, 2 replies; 6+ messages in thread
From: Coly Li @ 2018-07-26 5:33 UTC (permalink / raw)
To: colyli, akpm, linux-kernel
Cc: linux-bcache, linux-block, Andy Shevchenko, Greg Kroah-Hartman,
Linus Torvalds, Thomas Gleixner, Michael Lyle, Kent Overstreet,
Kate Stewart, Randy Dunlap, Eric Biggers
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.
CRC calculation consistency testing is not trvial, it will be another
separated patch set and not in this series any more.
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>
Cc: Eric Biggers <ebiggers3@gmail.com>
---
Changelog:
v5: Remove test_crc patch from this series, it will be another separated
patch set. Fixes review comments from v4.
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 (2):
lib: add crc64 calculation routines
bcache: use routines from lib/crc64.c for CRC64 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/Makefile | 11 ++++
lib/crc64.c | 56 ++++++++++++++++
lib/gen_crc64table.c | 68 ++++++++++++++++++++
9 files changed, 174 insertions(+), 135 deletions(-)
create mode 100644 include/linux/crc64.h
create mode 100644 lib/crc64.c
create mode 100644 lib/gen_crc64table.c
--
2.17.1
^ permalink raw reply [flat|nested] 6+ messages in thread* [PATCH v5 1/2] lib: add crc64 calculation routines 2018-07-26 5:33 [PATCH v5 0/2] add crc64 calculation as kernel library Coly Li @ 2018-07-26 5:33 ` Coly Li 2018-07-26 20:02 ` Andrew Morton 2018-07-26 5:33 ` [PATCH v5 2/2] bcache: use routines from lib/crc64.c for CRC64 calculation Coly Li 1 sibling, 1 reply; 6+ messages in thread From: Coly Li @ 2018-07-26 5:33 UTC (permalink / raw) To: colyli, akpm, linux-kernel Cc: linux-bcache, linux-block, Andy Shevchenko, Greg Kroah-Hartman, Michael Lyle, Kent Overstreet, Linus Torvalds, Thomas Gleixner, Kate Stewart, Eric Biggers, Randy Dunlap This patch adds the re-write crc64 calculation routines for Linux kernel. The CRC64 polynomial 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: v5: Fixes review comments of v4 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 polynomial 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..0ef8ae6ac047 --- /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-driven 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 or (u64)~0 for a new CRC calculation, + 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..9011926e4162 --- /dev/null +++ b/lib/gen_crc64table.c @@ -0,0 +1,68 @@ +// SPDX-License-Identifier: GPL-2.0 +/* + * Generate lookup table for the table-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-driven CRC64 calculation. + * + * See lib/crc64.c for more information about which specification + * and polynomial 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 uint64_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] 6+ messages in thread
* Re: [PATCH v5 1/2] lib: add crc64 calculation routines 2018-07-26 5:33 ` [PATCH v5 1/2] lib: add crc64 calculation routines Coly Li @ 2018-07-26 20:02 ` Andrew Morton 2018-12-29 2:58 ` NeilBrown 0 siblings, 1 reply; 6+ messages in thread From: Andrew Morton @ 2018-07-26 20:02 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, Eric Biggers, Randy Dunlap On Thu, 26 Jul 2018 13:33:51 +0800 Coly Li <colyli@suse.de> wrote: > This patch adds the re-write crc64 calculation routines for Linux kernel. > The CRC64 polynomial 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. delta from v4: --- a/include/linux/crc64.h~lib-add-crc64-calculation-routines-v5 +++ a/include/linux/crc64.h @@ -1,6 +1,6 @@ /* SPDX-License-Identifier: GPL-2.0 */ /* - * See lib/crc64.c for the related specification and polynomical arithmetic. + * See lib/crc64.c for the related specification and polynomial arithmetic. */ #ifndef _LINUX_CRC64_H #define _LINUX_CRC64_H --- a/lib/crc64.c~lib-add-crc64-calculation-routines-v5 +++ a/lib/crc64.c @@ -12,7 +12,7 @@ * from, * http://www.ross.net/crc/download/crc_v3.txt * - * crc64table[256] is the lookup table of a table-driver 64-bit CRC + * crc64table[256] is the lookup table of a table-driven 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, @@ -35,8 +35,8 @@ 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. + * @crc: seed value for computation. 0 or (u64)~0 for a new CRC calculation, + or the previous crc64 value if computing incrementally. * @p: pointer to buffer over which CRC64 is run * @len: length of buffer @p */ --- a/lib/gen_crc64table.c~lib-add-crc64-calculation-routines-v5 +++ a/lib/gen_crc64table.c @@ -1,13 +1,13 @@ // SPDX-License-Identifier: GPL-2.0 /* - * Generate lookup table for the talbe-driven CRC64 calculation. + * Generate lookup table for the table-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. + * the table-driven CRC64 calculation. * * See lib/crc64.c for more information about which specification - * and polynomical arithmetic that gen_crc64table.c follows to + * and polynomial arithmetic that gen_crc64table.c follows to * generate the lookup table. * * Copyright 2018 SUSE Linux. @@ -20,7 +20,7 @@ #define CRC64_ECMA182_POLY 0x42F0E1EBA9EA3693ULL -static int64_t crc64_table[256] = {0}; +static uint64_t crc64_table[256] = {0}; static void generate_crc64_table(void) { ^ permalink raw reply [flat|nested] 6+ messages in thread
* Re: [PATCH v5 1/2] lib: add crc64 calculation routines 2018-07-26 20:02 ` Andrew Morton @ 2018-12-29 2:58 ` NeilBrown 2018-12-29 3:57 ` Coly Li 0 siblings, 1 reply; 6+ messages in thread From: NeilBrown @ 2018-12-29 2:58 UTC (permalink / raw) To: Andrew Morton, Coly Li Cc: linux-kernel, linux-bcache, linux-block, Andy Shevchenko, Greg Kroah-Hartman, Michael Lyle, Kent Overstreet, Linus Torvalds, Thomas Gleixner, Kate Stewart, Eric Biggers, Randy Dunlap [-- Attachment #1: Type: text/plain, Size: 1656 bytes --] On Thu, Jul 26 2018, Andrew Morton wrote: > On Thu, 26 Jul 2018 13:33:51 +0800 Coly Li <colyli@suse.de> wrote: > >> This patch adds the re-write crc64 calculation routines for Linux kernel. >> The CRC64 polynomial 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. Hi Coly and Andrew, This patch breaks compilation if linux headers files are not installed (reported at https://github.com/gnubee-git/GnuBee_Docs/issues/75). Following fixes it. Thanks, NeilBrown From: NeilBrown <neil@brown.name> Subject: [PATCH] lib: don't depend on linux headers being installed. gen_crc64table requires linux include files to be installed in /usr/include/linux. This is a new requrement so hosts that could previously build the kernel, now cannot. gen_crc64table makes this requirement by including <linux/swab.h>, but nothing from that header is actaully used. So remove the #include, so that the linux headers no longer need to be installed. Fixes: feba04fd2cf8 ("lib: add crc64 calculation routines") Signed-off-by: NeilBrown <neil@brown.name> --- lib/gen_crc64table.c | 2 -- 1 file changed, 2 deletions(-) diff --git a/lib/gen_crc64table.c b/lib/gen_crc64table.c index 9011926e4162..094b43aef8db 100644 --- a/lib/gen_crc64table.c +++ b/lib/gen_crc64table.c @@ -16,8 +16,6 @@ #include <inttypes.h> #include <stdio.h> -#include <linux/swab.h> - #define CRC64_ECMA182_POLY 0x42F0E1EBA9EA3693ULL static uint64_t crc64_table[256] = {0}; -- 2.14.0.rc0.dirty [-- Attachment #2: signature.asc --] [-- Type: application/pgp-signature, Size: 832 bytes --] ^ permalink raw reply related [flat|nested] 6+ messages in thread
* Re: [PATCH v5 1/2] lib: add crc64 calculation routines 2018-12-29 2:58 ` NeilBrown @ 2018-12-29 3:57 ` Coly Li 0 siblings, 0 replies; 6+ messages in thread From: Coly Li @ 2018-12-29 3:57 UTC (permalink / raw) To: NeilBrown Cc: Andrew Morton, linux-kernel, linux-bcache, linux-block, Andy Shevchenko, Greg Kroah-Hartman, Michael Lyle, Kent Overstreet, Linus Torvalds, Thomas Gleixner, Kate Stewart, Eric Biggers, Randy Dunlap -----BEGIN PGP SIGNED MESSAGE----- Hash: SHA256 On 12/29/18 10:58 上午, NeilBrown wrote: > On Thu, Jul 26 2018, Andrew Morton wrote: > >> On Thu, 26 Jul 2018 13:33:51 +0800 Coly Li <colyli@suse.de> >> wrote: >> >>> This patch adds the re-write crc64 calculation routines for >>> Linux kernel. The CRC64 polynomial 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. > > Hi Coly and Andrew, > > This patch breaks compilation if linux headers files are not > installed (reported at > https://github.com/gnubee-git/GnuBee_Docs/issues/75). Following > fixes it. > > Thanks, NeilBrown > Hi Neil, Thanks for the fix. I add by Acked-by. Coly Li > From: NeilBrown <neil@brown.name> Subject: [PATCH] lib: don't > depend on linux headers being installed. > > gen_crc64table requires linux include files to be installed in > /usr/include/linux. This is a new requrement so hosts that could > previously build the kernel, now cannot. > > gen_crc64table makes this requirement by including <linux/swab.h>, > but nothing from that header is actaully used. > > So remove the #include, so that the linux headers no longer need to > be installed. > > Fixes: feba04fd2cf8 ("lib: add crc64 calculation routines") > Signed-off-by: NeilBrown <neil@brown.name> Acked-by: Coly Li <colyli@suse.de> > --- lib/gen_crc64table.c | 2 -- 1 file changed, 2 deletions(-) > > diff --git a/lib/gen_crc64table.c b/lib/gen_crc64table.c index > 9011926e4162..094b43aef8db 100644 --- a/lib/gen_crc64table.c +++ > b/lib/gen_crc64table.c @@ -16,8 +16,6 @@ #include <inttypes.h> > #include <stdio.h> > > -#include <linux/swab.h> - #define CRC64_ECMA182_POLY > 0x42F0E1EBA9EA3693ULL > > static uint64_t crc64_table[256] = {0}; > -----BEGIN PGP SIGNATURE----- Comment: GPGTools - http://gpgtools.org iQIzBAEBCAAdFiEE6j5FL/T5SGCN6PrQxzkHk2t9+PwFAlwm8JsACgkQxzkHk2t9 +PxELA//U8FohU56Xty9Yfe/5IX0WXHzpLk8efz34xNodo1bavy9yIlpzG8l9cX5 c2vaM4hYvc2rrYokgkxHcANSpFkRzD9TjkwNbij7wd37lEJYzPWr0Qk1Ttuojs7b iJYLis0pbu6WTeUpM4NwdkKzylqWXg0dRrf3tNpF5ttN+LZOSEzbIiP8P2rnQUmD a9WCM6Ka/E9dP5H2CIvR6gAJL/BwsVyFgd6PiYy8ElMVYBpIu2uG34eO0tx6ebSE TPxWrSXY92jWCggJUBNr5zDXyBQADBQfy0YIv36zsplcolF/4mN4LWF2WCC4jp0c XLBrvSslzombjxq3h+zE4GNXsDNiKtaNQy1N30b1+N3ilXa4uav1wVvaBQBMwf4I QQDM8ZZ2alS5zAyzgtnbIr0AhlNEya+GO+42+rY0yrWG2Ffg3ONHSgylQ7hANVdk 2qAWugdXZLw/pqustIodIR3hjsWLc4zZDF+d6BywdB5WqSiS54u7ENSPkbGInKRR 8zprb2tjjjgwxL1MXF+6J1HG+GoTvEjjwjh26XDSiFbWCIX3hRjej+EjltKDARIo RWfX6/hTVnljkNUEpBfsi7DaiDVwkgo1OLQ3OSXgG9rZxs50ASMb4dBuN8wGdRrX jK3PF5m3ddVxCW2I5CFltd3qHlUFn+fmQojXtU6VSACgw0roQhw= =qnbZ -----END PGP SIGNATURE----- ^ permalink raw reply [flat|nested] 6+ messages in thread
* [PATCH v5 2/2] bcache: use routines from lib/crc64.c for CRC64 calculation 2018-07-26 5:33 [PATCH v5 0/2] add crc64 calculation as kernel library Coly Li 2018-07-26 5:33 ` [PATCH v5 1/2] lib: add crc64 calculation routines Coly Li @ 2018-07-26 5:33 ` Coly Li 1 sibling, 0 replies; 6+ messages in thread From: Coly Li @ 2018-07-26 5:33 UTC (permalink / raw) To: colyli, akpm, linux-kernel Cc: linux-bcache, linux-block, Michael Lyle, Kent Overstreet, Linus Torvalds, Thomas Gleixner, Kate Stewart, 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] 6+ messages in thread
end of thread, other threads:[~2018-12-29 4:13 UTC | newest] Thread overview: 6+ messages (download: mbox.gz / follow: Atom feed) -- links below jump to the message on this page -- 2018-07-26 5:33 [PATCH v5 0/2] add crc64 calculation as kernel library Coly Li 2018-07-26 5:33 ` [PATCH v5 1/2] lib: add crc64 calculation routines Coly Li 2018-07-26 20:02 ` Andrew Morton 2018-12-29 2:58 ` NeilBrown 2018-12-29 3:57 ` Coly Li 2018-07-26 5:33 ` [PATCH v5 2/2] bcache: use routines from lib/crc64.c for CRC64 calculation 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).