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 <[email protected]>
Cc: Greg Kroah-Hartman <[email protected]>
Cc: Linus Torvalds <[email protected]>
Cc: Thomas Gleixner <[email protected]>
Cc: Michael Lyle <[email protected]>
Cc: Kent Overstreet <[email protected]>
Cc: Kate Stewart <[email protected]>
Cc: Andrew Morton <[email protected]>
Cc: Randy Dunlap <[email protected]>
---
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
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 <[email protected]>
Co-developed-by: Andy Shevchenko <[email protected]>
Signed-off-by: Andy Shevchenko <[email protected]>
Reviewed-by: Hannes Reinecke <[email protected]>
Cc: Greg Kroah-Hartman <[email protected]>
Cc: Andy Shevchenko <[email protected]>
Cc: Michael Lyle <[email protected]>
Cc: Kent Overstreet <[email protected]>
Cc: Linus Torvalds <[email protected]>
Cc: Thomas Gleixner <[email protected]>
Cc: Kate Stewart <[email protected]>
Cc: Eric Biggers <[email protected]>
Cc: Andrew Morton <[email protected]>
Cc: Randy Dunlap <[email protected]>
---
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 <[email protected]>
+ */
+
+#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 <[email protected]>
+ */
+#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
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 <[email protected]>
Reviewed-by: Hannes Reinecke <[email protected]>
Reviewed-by: Andy Shevchenko <[email protected]>
Cc: Michael Lyle <[email protected]>
Cc: Kent Overstreet <[email protected]>
Cc: Linus Torvalds <[email protected]>
Cc: Thomas Gleixner <[email protected]>
Cc: Kate Stewart <[email protected]>
Cc: Andrew Morton <[email protected]>
Cc: Randy Dunlap <[email protected]>
---
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
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 <[email protected]>
Reviewed-by: Hannes Reinecke <[email protected]>
Cc: Greg Kroah-Hartman <[email protected]>
Cc: Linus Torvalds <[email protected]>
Cc: Thomas Gleixner <[email protected]>
Cc: Kate Stewart <[email protected]>
Cc: Andrew Morton <[email protected]>
Cc: Randy Dunlap <[email protected]>
Cc: Andy Shevchenko <[email protected]>
Cc: Noah Massey <[email protected]>
---
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 <[email protected]>
+ *
+ * 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 <[email protected]>");
+MODULE_LICENSE("GPL v2");
--
2.17.1
On Thu, 19 Jul 2018 00:55:45 +0800 Coly Li <[email protected]> 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 <[email protected]>
Subject: lib-test_crc-add-test-cases-for-crc-calculation-fix
make two globals static, regularize code layout, remove unneeded initialization
Cc: Coly Li <[email protected]>
Signed-off-by: Andrew Morton <[email protected]>
---
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");
_
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 <[email protected]>
> + */
> +
> +#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 <[email protected]>
> + */
> +#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
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
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
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 <[email protected]>
>> + */
>> +
>> +#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 <[email protected]>
>> + */
>> +#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
>
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 <[email protected]>
Intel Finland Oy
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
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
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
On Wed, 25 Jul 2018 10:37:23 +0800 Coly Li <[email protected]> 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.
On 2018/7/26 5:22 AM, Andrew Morton wrote:
> On Wed, 25 Jul 2018 10:37:23 +0800 Coly Li <[email protected]> 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