This patch set adds basic implementation of crc64 calculation as Linux
kernel library. Since bcache already does crc64 by itself, this patch
set also modifies bcache code to use the new crc64 library routine.
bcache uses crc64 as storage checksum, if a change of crc lib routines
results an inconsistent result, the unmatched checksum may make bcache
'think' the on-disk is corrupted, such change should be avoided or
detected as early as possible. Therefore the last patch in this series
adds a crc test framework, to check consistency of different calculations.
Changelog:
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
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]>
---
Andy Shevchenko (1):
lib/crc64: add crc64 option to lib/Kconfig
Coly Li (3):
lib: add crc64 calculation routines
bcache: use routines from lib/crc64.c for CRC64 calculation
lib/test_crc: Add test cases for crc calculation
drivers/md/bcache/bcache.h | 7 +-
drivers/md/bcache/btree.c | 2 +-
drivers/md/bcache/request.c | 2 +-
drivers/md/bcache/super.c | 5 +-
drivers/md/bcache/util.c | 131 ----------------------------------
drivers/md/bcache/util.h | 5 +-
include/linux/crc64.h | 15 ++++
lib/.gitignore | 2 +
lib/Kconfig | 8 +++
lib/Kconfig.debug | 11 +++
lib/Makefile | 12 ++++
lib/crc64.c | 71 +++++++++++++++++++
lib/gen_crc64table.c | 76 ++++++++++++++++++++
lib/test_crc.c | 136 ++++++++++++++++++++++++++++++++++++
14 files changed, 341 insertions(+), 142 deletions(-)
create mode 100644 include/linux/crc64.h
create mode 100644 lib/crc64.c
create mode 100644 lib/gen_crc64table.c
create mode 100644 lib/test_crc.c
--
2.17.1
This patch adds the re-write crc64 calculation routines for Linux kernel.
The CRC64 polynomical arithmetic follows ECMA-182 specification, inspired
by CRC paper of Dr. Ross N. Williams
(see http://www.ross.net/crc/download/crc_v3.txt) and other public domain
implementations.
All the changes work in this way,
- When Linux kernel is built, host program lib/gen_crc64table.c will be
compiled to lib/gen_crc64table and executed.
- The output of gen_crc64table execution is an array called as lookup
table (a.k.a POLY 0x42f0e1eba9ea369) which contain 256 64bits-long
numbers, this talbe is dumped into header file lib/crc64table.h.
- Then the header file is included by lib/crc64.c for normal 64bit crc
calculation.
- Function declaration of the crc64 calculation routines is placed in
include/linux/crc64.h
Changelog:
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.
Signed-off-by: Coly Li <[email protected]>
Co-developed-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]>
---
include/linux/crc64.h | 13 ++++++++
lib/.gitignore | 2 ++
lib/Kconfig | 8 +++++
lib/Makefile | 11 +++++++
lib/crc64.c | 71 +++++++++++++++++++++++++++++++++++++++++++
lib/gen_crc64table.c | 69 +++++++++++++++++++++++++++++++++++++++++
6 files changed, 174 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..3e87b61cd54f
--- /dev/null
+++ b/include/linux/crc64.h
@@ -0,0 +1,13 @@
+/* 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_update(u64 crc, const void *_p, size_t len);
+u64 __pure crc64(const void *p, size_t len);
+u64 __pure crc64_bch(const void *p, size_t len);
+#endif /* _LINUX_CRC64_H */
diff --git a/lib/.gitignore b/lib/.gitignore
index 09aae85418ab..f2a39c9e5485 100644
--- a/lib/.gitignore
+++ b/lib/.gitignore
@@ -2,5 +2,7 @@
# Generated files
#
gen_crc32table
+gen_crc64table
crc32table.h
+crc64table.h
oid_registry_data.c
diff --git a/lib/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..64b5f1ec3016
--- /dev/null
+++ b/lib/crc64.c
@@ -0,0 +1,71 @@
+// SPDX-License-Identifier: GPL-2.0
+/*
+ * Normal 64bit CRC calculation.
+ *
+ * This is a basic crc64 implementation following ECMA-182 specification,
+ * which can be found from,
+ * http://www.ecma-international.org/publications/standards/Ecma-182.htm
+ *
+ * Dr. Ross N. Williams has a great document to introduce the idea of CRC
+ * algorithm, here the CRC64 code is also inspired by the table-driven
+ * algorithm and detail example from this paper. This paper can be found
+ * from,
+ * http://www.ross.net/crc/download/crc_v3.txt
+ *
+ * crc64table[256] is the lookup table of a table-driver 64bit CRC
+ * calculation, which is generated by gen_crc64table.c in kernel build
+ * time. The polynomial of crc64 arithmetic is from ECMA-182 specification
+ * as well, which is defined as,
+ *
+ * x^64 + x^62 + x^57 + x^55 + x^54 + x^53 + x^52 + x^47 + x^46 + x^45 +
+ * x^40 + x^39 + x^38 + x^37 + x^35 + x^33 + x^32 + x^31 + x^29 + x^27 +
+ * x^24 + x^23 + x^22 + x^21 + x^19 + x^17 + x^13 + x^12 + x^10 + x^9 +
+ * x^7 + x^4 + x + 1
+ *
+ * Copyright 2018 SUSE Linux.
+ * Author: Coly Li <[email protected]>
+ *
+ */
+
+#include <linux/module.h>
+#include <linux/types.h>
+#include "crc64table.h"
+
+MODULE_DESCRIPTION("CRC64 calculations");
+MODULE_LICENSE("GPL v2");
+
+u64 __pure crc64_update(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_update);
+
+u64 __pure crc64(const void *p, size_t len)
+{
+ u64 crc = 0x0ULL;
+
+ crc = crc64_update(crc, p, len);
+
+ return crc;
+}
+EXPORT_SYMBOL_GPL(crc64);
+
+/* For checksum calculation in drivers/md/bcache/ */
+u64 __pure crc64_bch(const void *p, size_t len)
+{
+ u64 crc = 0xFFFFFFFFFFFFFFFFULL;
+
+ crc = crc64_update(crc, p, len);
+
+ return (crc ^ 0xFFFFFFFFFFFFFFFFULL);
+}
+EXPORT_SYMBOL_GPL(crc64_bch);
diff --git a/lib/gen_crc64table.c b/lib/gen_crc64table.c
new file mode 100644
index 000000000000..af9c4d12c0a1
--- /dev/null
+++ b/lib/gen_crc64table.c
@@ -0,0 +1,69 @@
+// 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 <uapi/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]>
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]>
---
drivers/md/bcache/Kconfig | 1 +
drivers/md/bcache/bcache.h | 7 +-
drivers/md/bcache/btree.c | 2 +-
drivers/md/bcache/request.c | 2 +-
drivers/md/bcache/super.c | 5 +-
drivers/md/bcache/util.c | 131 ------------------------------------
drivers/md/bcache/util.h | 5 +-
7 files changed, 11 insertions(+), 142 deletions(-)
diff --git a/drivers/md/bcache/Kconfig b/drivers/md/bcache/Kconfig
index 17bf109c58e9..af247298409a 100644
--- a/drivers/md/bcache/Kconfig
+++ b/drivers/md/bcache/Kconfig
@@ -1,6 +1,7 @@
config BCACHE
tristate "Block device as cache"
+ select CRC64
---help---
Allows a block device to be used as cache for other devices; uses
a btree for indexing and the layout is optimized for SSDs.
diff --git a/drivers/md/bcache/bcache.h b/drivers/md/bcache/bcache.h
index d6bf294f3907..6d4d2356c3cc 100644
--- a/drivers/md/bcache/bcache.h
+++ b/drivers/md/bcache/bcache.h
@@ -189,6 +189,7 @@
#include <linux/types.h>
#include <linux/workqueue.h>
#include <linux/kthread.h>
+#include <linux/crc64.h>
#include "bset.h"
#include "util.h"
@@ -803,9 +804,9 @@ static inline bool ptr_available(struct cache_set *c, const struct bkey *k,
* jset: The checksum is _always_ the first 8 bytes of these structs
*/
#define csum_set(i) \
- bch_crc64(((void *) (i)) + sizeof(uint64_t), \
- ((void *) bset_bkey_last(i)) - \
- (((void *) (i)) + sizeof(uint64_t)))
+ crc64_bch(((void *) (i)) + sizeof(uint64_t), \
+ ((void *) bset_bkey_last(i)) - \
+ (((void *) (i)) + sizeof(uint64_t)))
/* Error handling macros */
diff --git a/drivers/md/bcache/btree.c b/drivers/md/bcache/btree.c
index 547c9eedc2f4..72619508c928 100644
--- a/drivers/md/bcache/btree.c
+++ b/drivers/md/bcache/btree.c
@@ -194,7 +194,7 @@ static uint64_t btree_csum_set(struct btree *b, struct bset *i)
uint64_t crc = b->key.ptr[0];
void *data = (void *) i + 8, *end = bset_bkey_last(i);
- crc = bch_crc64_update(crc, data, end - data);
+ crc = crc64_update(crc, data, end - data);
return crc ^ 0xffffffffffffffffULL;
}
diff --git a/drivers/md/bcache/request.c b/drivers/md/bcache/request.c
index ae67f5fa8047..28b2fb11a3d5 100644
--- a/drivers/md/bcache/request.c
+++ b/drivers/md/bcache/request.c
@@ -45,7 +45,7 @@ static void bio_csum(struct bio *bio, struct bkey *k)
bio_for_each_segment(bv, bio, iter) {
void *d = kmap(bv.bv_page) + bv.bv_offset;
- csum = bch_crc64_update(csum, d, bv.bv_len);
+ csum = crc64_update(csum, d, bv.bv_len);
kunmap(bv.bv_page);
}
diff --git a/drivers/md/bcache/super.c b/drivers/md/bcache/super.c
index fa4058e43202..c425c52f0c42 100644
--- a/drivers/md/bcache/super.c
+++ b/drivers/md/bcache/super.c
@@ -549,7 +549,7 @@ void bch_prio_write(struct cache *ca)
p->next_bucket = ca->prio_buckets[i + 1];
p->magic = pset_magic(&ca->sb);
- p->csum = bch_crc64(&p->magic, bucket_bytes(ca) - 8);
+ p->csum = crc64_bch(&p->magic, bucket_bytes(ca) - 8);
bucket = bch_bucket_alloc(ca, RESERVE_PRIO, true);
BUG_ON(bucket == -1);
@@ -599,7 +599,8 @@ static void prio_read(struct cache *ca, uint64_t bucket)
prio_io(ca, bucket, REQ_OP_READ, 0);
- if (p->csum != bch_crc64(&p->magic, bucket_bytes(ca) - 8))
+ if (p->csum != crc64_bch(&p->magic,
+ bucket_bytes(ca) - 8))
pr_warn("bad csum reading priorities");
if (p->magic != pset_magic(&ca->sb))
diff --git a/drivers/md/bcache/util.c b/drivers/md/bcache/util.c
index fc479b026d6d..f912c372978c 100644
--- a/drivers/md/bcache/util.c
+++ b/drivers/md/bcache/util.c
@@ -279,134 +279,3 @@ int bch_bio_alloc_pages(struct bio *bio, gfp_t gfp_mask)
return 0;
}
-
-/*
- * Portions Copyright (c) 1996-2001, PostgreSQL Global Development Group (Any
- * use permitted, subject to terms of PostgreSQL license; see.)
-
- * If we have a 64-bit integer type, then a 64-bit CRC looks just like the
- * usual sort of implementation. (See Ross Williams' excellent introduction
- * A PAINLESS GUIDE TO CRC ERROR DETECTION ALGORITHMS, available from
- * ftp://ftp.rocksoft.com/papers/crc_v3.txt or several other net sites.)
- * If we have no working 64-bit type, then fake it with two 32-bit registers.
- *
- * The present implementation is a normal (not "reflected", in Williams'
- * terms) 64-bit CRC, using initial all-ones register contents and a final
- * bit inversion. The chosen polynomial is borrowed from the DLT1 spec
- * (ECMA-182, available from http://www.ecma.ch/ecma1/STAND/ECMA-182.HTM):
- *
- * x^64 + x^62 + x^57 + x^55 + x^54 + x^53 + x^52 + x^47 + x^46 + x^45 +
- * x^40 + x^39 + x^38 + x^37 + x^35 + x^33 + x^32 + x^31 + x^29 + x^27 +
- * x^24 + x^23 + x^22 + x^21 + x^19 + x^17 + x^13 + x^12 + x^10 + x^9 +
- * x^7 + x^4 + x + 1
-*/
-
-static const uint64_t crc_table[256] = {
- 0x0000000000000000ULL, 0x42F0E1EBA9EA3693ULL, 0x85E1C3D753D46D26ULL,
- 0xC711223CFA3E5BB5ULL, 0x493366450E42ECDFULL, 0x0BC387AEA7A8DA4CULL,
- 0xCCD2A5925D9681F9ULL, 0x8E224479F47CB76AULL, 0x9266CC8A1C85D9BEULL,
- 0xD0962D61B56FEF2DULL, 0x17870F5D4F51B498ULL, 0x5577EEB6E6BB820BULL,
- 0xDB55AACF12C73561ULL, 0x99A54B24BB2D03F2ULL, 0x5EB4691841135847ULL,
- 0x1C4488F3E8F96ED4ULL, 0x663D78FF90E185EFULL, 0x24CD9914390BB37CULL,
- 0xE3DCBB28C335E8C9ULL, 0xA12C5AC36ADFDE5AULL, 0x2F0E1EBA9EA36930ULL,
- 0x6DFEFF5137495FA3ULL, 0xAAEFDD6DCD770416ULL, 0xE81F3C86649D3285ULL,
- 0xF45BB4758C645C51ULL, 0xB6AB559E258E6AC2ULL, 0x71BA77A2DFB03177ULL,
- 0x334A9649765A07E4ULL, 0xBD68D2308226B08EULL, 0xFF9833DB2BCC861DULL,
- 0x388911E7D1F2DDA8ULL, 0x7A79F00C7818EB3BULL, 0xCC7AF1FF21C30BDEULL,
- 0x8E8A101488293D4DULL, 0x499B3228721766F8ULL, 0x0B6BD3C3DBFD506BULL,
- 0x854997BA2F81E701ULL, 0xC7B97651866BD192ULL, 0x00A8546D7C558A27ULL,
- 0x4258B586D5BFBCB4ULL, 0x5E1C3D753D46D260ULL, 0x1CECDC9E94ACE4F3ULL,
- 0xDBFDFEA26E92BF46ULL, 0x990D1F49C77889D5ULL, 0x172F5B3033043EBFULL,
- 0x55DFBADB9AEE082CULL, 0x92CE98E760D05399ULL, 0xD03E790CC93A650AULL,
- 0xAA478900B1228E31ULL, 0xE8B768EB18C8B8A2ULL, 0x2FA64AD7E2F6E317ULL,
- 0x6D56AB3C4B1CD584ULL, 0xE374EF45BF6062EEULL, 0xA1840EAE168A547DULL,
- 0x66952C92ECB40FC8ULL, 0x2465CD79455E395BULL, 0x3821458AADA7578FULL,
- 0x7AD1A461044D611CULL, 0xBDC0865DFE733AA9ULL, 0xFF3067B657990C3AULL,
- 0x711223CFA3E5BB50ULL, 0x33E2C2240A0F8DC3ULL, 0xF4F3E018F031D676ULL,
- 0xB60301F359DBE0E5ULL, 0xDA050215EA6C212FULL, 0x98F5E3FE438617BCULL,
- 0x5FE4C1C2B9B84C09ULL, 0x1D14202910527A9AULL, 0x93366450E42ECDF0ULL,
- 0xD1C685BB4DC4FB63ULL, 0x16D7A787B7FAA0D6ULL, 0x5427466C1E109645ULL,
- 0x4863CE9FF6E9F891ULL, 0x0A932F745F03CE02ULL, 0xCD820D48A53D95B7ULL,
- 0x8F72ECA30CD7A324ULL, 0x0150A8DAF8AB144EULL, 0x43A04931514122DDULL,
- 0x84B16B0DAB7F7968ULL, 0xC6418AE602954FFBULL, 0xBC387AEA7A8DA4C0ULL,
- 0xFEC89B01D3679253ULL, 0x39D9B93D2959C9E6ULL, 0x7B2958D680B3FF75ULL,
- 0xF50B1CAF74CF481FULL, 0xB7FBFD44DD257E8CULL, 0x70EADF78271B2539ULL,
- 0x321A3E938EF113AAULL, 0x2E5EB66066087D7EULL, 0x6CAE578BCFE24BEDULL,
- 0xABBF75B735DC1058ULL, 0xE94F945C9C3626CBULL, 0x676DD025684A91A1ULL,
- 0x259D31CEC1A0A732ULL, 0xE28C13F23B9EFC87ULL, 0xA07CF2199274CA14ULL,
- 0x167FF3EACBAF2AF1ULL, 0x548F120162451C62ULL, 0x939E303D987B47D7ULL,
- 0xD16ED1D631917144ULL, 0x5F4C95AFC5EDC62EULL, 0x1DBC74446C07F0BDULL,
- 0xDAAD56789639AB08ULL, 0x985DB7933FD39D9BULL, 0x84193F60D72AF34FULL,
- 0xC6E9DE8B7EC0C5DCULL, 0x01F8FCB784FE9E69ULL, 0x43081D5C2D14A8FAULL,
- 0xCD2A5925D9681F90ULL, 0x8FDAB8CE70822903ULL, 0x48CB9AF28ABC72B6ULL,
- 0x0A3B7B1923564425ULL, 0x70428B155B4EAF1EULL, 0x32B26AFEF2A4998DULL,
- 0xF5A348C2089AC238ULL, 0xB753A929A170F4ABULL, 0x3971ED50550C43C1ULL,
- 0x7B810CBBFCE67552ULL, 0xBC902E8706D82EE7ULL, 0xFE60CF6CAF321874ULL,
- 0xE224479F47CB76A0ULL, 0xA0D4A674EE214033ULL, 0x67C58448141F1B86ULL,
- 0x253565A3BDF52D15ULL, 0xAB1721DA49899A7FULL, 0xE9E7C031E063ACECULL,
- 0x2EF6E20D1A5DF759ULL, 0x6C0603E6B3B7C1CAULL, 0xF6FAE5C07D3274CDULL,
- 0xB40A042BD4D8425EULL, 0x731B26172EE619EBULL, 0x31EBC7FC870C2F78ULL,
- 0xBFC9838573709812ULL, 0xFD39626EDA9AAE81ULL, 0x3A28405220A4F534ULL,
- 0x78D8A1B9894EC3A7ULL, 0x649C294A61B7AD73ULL, 0x266CC8A1C85D9BE0ULL,
- 0xE17DEA9D3263C055ULL, 0xA38D0B769B89F6C6ULL, 0x2DAF4F0F6FF541ACULL,
- 0x6F5FAEE4C61F773FULL, 0xA84E8CD83C212C8AULL, 0xEABE6D3395CB1A19ULL,
- 0x90C79D3FEDD3F122ULL, 0xD2377CD44439C7B1ULL, 0x15265EE8BE079C04ULL,
- 0x57D6BF0317EDAA97ULL, 0xD9F4FB7AE3911DFDULL, 0x9B041A914A7B2B6EULL,
- 0x5C1538ADB04570DBULL, 0x1EE5D94619AF4648ULL, 0x02A151B5F156289CULL,
- 0x4051B05E58BC1E0FULL, 0x87409262A28245BAULL, 0xC5B073890B687329ULL,
- 0x4B9237F0FF14C443ULL, 0x0962D61B56FEF2D0ULL, 0xCE73F427ACC0A965ULL,
- 0x8C8315CC052A9FF6ULL, 0x3A80143F5CF17F13ULL, 0x7870F5D4F51B4980ULL,
- 0xBF61D7E80F251235ULL, 0xFD913603A6CF24A6ULL, 0x73B3727A52B393CCULL,
- 0x31439391FB59A55FULL, 0xF652B1AD0167FEEAULL, 0xB4A25046A88DC879ULL,
- 0xA8E6D8B54074A6ADULL, 0xEA16395EE99E903EULL, 0x2D071B6213A0CB8BULL,
- 0x6FF7FA89BA4AFD18ULL, 0xE1D5BEF04E364A72ULL, 0xA3255F1BE7DC7CE1ULL,
- 0x64347D271DE22754ULL, 0x26C49CCCB40811C7ULL, 0x5CBD6CC0CC10FAFCULL,
- 0x1E4D8D2B65FACC6FULL, 0xD95CAF179FC497DAULL, 0x9BAC4EFC362EA149ULL,
- 0x158E0A85C2521623ULL, 0x577EEB6E6BB820B0ULL, 0x906FC95291867B05ULL,
- 0xD29F28B9386C4D96ULL, 0xCEDBA04AD0952342ULL, 0x8C2B41A1797F15D1ULL,
- 0x4B3A639D83414E64ULL, 0x09CA82762AAB78F7ULL, 0x87E8C60FDED7CF9DULL,
- 0xC51827E4773DF90EULL, 0x020905D88D03A2BBULL, 0x40F9E43324E99428ULL,
- 0x2CFFE7D5975E55E2ULL, 0x6E0F063E3EB46371ULL, 0xA91E2402C48A38C4ULL,
- 0xEBEEC5E96D600E57ULL, 0x65CC8190991CB93DULL, 0x273C607B30F68FAEULL,
- 0xE02D4247CAC8D41BULL, 0xA2DDA3AC6322E288ULL, 0xBE992B5F8BDB8C5CULL,
- 0xFC69CAB42231BACFULL, 0x3B78E888D80FE17AULL, 0x7988096371E5D7E9ULL,
- 0xF7AA4D1A85996083ULL, 0xB55AACF12C735610ULL, 0x724B8ECDD64D0DA5ULL,
- 0x30BB6F267FA73B36ULL, 0x4AC29F2A07BFD00DULL, 0x08327EC1AE55E69EULL,
- 0xCF235CFD546BBD2BULL, 0x8DD3BD16FD818BB8ULL, 0x03F1F96F09FD3CD2ULL,
- 0x41011884A0170A41ULL, 0x86103AB85A2951F4ULL, 0xC4E0DB53F3C36767ULL,
- 0xD8A453A01B3A09B3ULL, 0x9A54B24BB2D03F20ULL, 0x5D45907748EE6495ULL,
- 0x1FB5719CE1045206ULL, 0x919735E51578E56CULL, 0xD367D40EBC92D3FFULL,
- 0x1476F63246AC884AULL, 0x568617D9EF46BED9ULL, 0xE085162AB69D5E3CULL,
- 0xA275F7C11F7768AFULL, 0x6564D5FDE549331AULL, 0x279434164CA30589ULL,
- 0xA9B6706FB8DFB2E3ULL, 0xEB46918411358470ULL, 0x2C57B3B8EB0BDFC5ULL,
- 0x6EA7525342E1E956ULL, 0x72E3DAA0AA188782ULL, 0x30133B4B03F2B111ULL,
- 0xF7021977F9CCEAA4ULL, 0xB5F2F89C5026DC37ULL, 0x3BD0BCE5A45A6B5DULL,
- 0x79205D0E0DB05DCEULL, 0xBE317F32F78E067BULL, 0xFCC19ED95E6430E8ULL,
- 0x86B86ED5267CDBD3ULL, 0xC4488F3E8F96ED40ULL, 0x0359AD0275A8B6F5ULL,
- 0x41A94CE9DC428066ULL, 0xCF8B0890283E370CULL, 0x8D7BE97B81D4019FULL,
- 0x4A6ACB477BEA5A2AULL, 0x089A2AACD2006CB9ULL, 0x14DEA25F3AF9026DULL,
- 0x562E43B4931334FEULL, 0x913F6188692D6F4BULL, 0xD3CF8063C0C759D8ULL,
- 0x5DEDC41A34BBEEB2ULL, 0x1F1D25F19D51D821ULL, 0xD80C07CD676F8394ULL,
- 0x9AFCE626CE85B507ULL,
-};
-
-uint64_t bch_crc64_update(uint64_t crc, const void *_data, size_t len)
-{
- const unsigned char *data = _data;
-
- while (len--) {
- int i = ((int) (crc >> 56) ^ *data++) & 0xFF;
- crc = crc_table[i] ^ (crc << 8);
- }
-
- return crc;
-}
-
-uint64_t bch_crc64(const void *data, size_t len)
-{
- uint64_t crc = 0xffffffffffffffffULL;
-
- crc = bch_crc64_update(crc, data, len);
-
- return crc ^ 0xffffffffffffffffULL;
-}
diff --git a/drivers/md/bcache/util.h b/drivers/md/bcache/util.h
index cced87f8eb27..b1deec0dc958 100644
--- a/drivers/md/bcache/util.h
+++ b/drivers/md/bcache/util.h
@@ -11,6 +11,7 @@
#include <linux/ratelimit.h>
#include <linux/vmalloc.h>
#include <linux/workqueue.h>
+#include <linux/crc64.h>
#include "closure.h"
@@ -561,8 +562,4 @@ static inline sector_t bdev_sectors(struct block_device *bdev)
{
return bdev->bd_inode->i_size >> 9;
}
-
-uint64_t bch_crc64_update(uint64_t, const void *, size_t);
-uint64_t bch_crc64(const void *, size_t);
-
#endif /* _BCACHE_UTIL_H */
--
2.17.1
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: PASSED (0x4e6b1ff972fa8c55, expected 0x4e6b1ff972fa8c55)
test_crc: crc64_bch: PASSED (0x0e4f1391d7a4a62e, expected 0x0e4f1391d7a4a62e)
test_crc: crc64_update: 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 are only test caes for 3 crc routines,
- crc64()
- crc64_bch()
- crc64_update()
Changelog:
v3: Add test cases passed/failed statistic
More fixes for review comments of v2
v2: Fixes for review comments of v1
v1: Initial version.
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]>
---
lib/Kconfig.debug | 10 ++++
lib/Makefile | 1 +
lib/test_crc.c | 138 ++++++++++++++++++++++++++++++++++++++++++++++
3 files changed, 149 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..441bf835fbd3
--- /dev/null
+++ b/lib/test_crc.c
@@ -0,0 +1,138 @@
+// 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()
+ * - crc64_bch()
+ * - crc64_update()
+ *
+ */
+
+#include <linux/async.h>
+#include <linux/delay.h>
+#include <linux/fs.h>
+#include <linux/list.h>
+#include <linux/module.h>
+#include <linux/printk.h>
+#include <linux/miscdevice.h>
+#include <linux/slab.h>
+#include <linux/uaccess.h>
+#include <linux/vmalloc.h>
+#include <linux/crc64.h>
+
+struct crc_test_record {
+ char *name;
+ u64 data[4];
+ u64 initval;
+ u64 expval;
+ int (*handler)(struct crc_test_record *rec);
+};
+
+static int chk_and_msg(const char *name, u64 crc, u64 expval)
+{
+ int ret = 0;
+
+ if (crc == expval) {
+ pr_info("test_crc: %s: PASSED:(0x%016llx, expected 0x%016llx)\n",
+ name, crc, expval);
+ } else {
+ pr_err("test_crc: %s: FAILED:(0x%016llx, expected 0x%016llx)\n",
+ name, crc, expval);
+ ret = -EINVAL;
+ }
+
+ return ret;
+}
+
+/* Add your crc test cases here */
+static int test_crc64(struct crc_test_record *rec)
+{
+ u64 crc;
+
+ crc = crc64(rec->data, sizeof(rec->data));
+ return chk_and_msg(rec->name, crc, rec->expval);
+}
+
+static int test_crc64_bch(struct crc_test_record *rec)
+{
+ u64 crc;
+
+ crc = crc64_bch(rec->data, sizeof(rec->data));
+ return chk_and_msg(rec->name, crc, rec->expval);
+}
+
+static int test_crc64_update(struct crc_test_record *rec)
+{
+ u64 crc = rec->initval;
+
+ crc = crc64_update(crc, rec->data, sizeof(rec->data));
+ return chk_and_msg(rec->name, crc, rec->expval);
+}
+
+/*
+ * Set up your crc test initial data here.
+ * Do not change the existing items, they are hard coded with
+ * pre-calculated values.
+ */
+static struct crc_test_record test_data[] = {
+ { .name = "crc64",
+ .data = { 0x42F0E1EBA9EA3693, 0x85E1C3D753D46D26,
+ 0xC711223CFA3E5BB5, 0x493366450E42ECDF },
+ .initval = 0,
+ .expval = 0xe2b9911e7b997201,
+ .handler = test_crc64,
+ },
+ { .name = "crc64_bch",
+ .data = { 0x42F0E1EBA9EA3693, 0x85E1C3D753D46D26,
+ 0xC711223CFA3E5BB5, 0x493366450E42ECDF },
+ .initval = 0,
+ .expval = 0xd2753a20fd862892,
+ .handler = test_crc64_bch,
+ },
+ { .name = "crc64_update",
+ .data = { 0x42F0E1EBA9EA3693, 0x85E1C3D753D46D26,
+ 0xC711223CFA3E5BB5, 0x493366450E42ECDF },
+ .initval = 0x61C8864680B583EB,
+ .expval = 0xb2c863673f4292bf,
+ .handler = test_crc64_update,
+ },
+ {}
+};
+
+static int __init test_crc_init(void)
+{
+ int i;
+ int v, err = 0;
+
+ pr_info("Kernel CRC consitency testing:\n");
+ for (i = 0; test_data[i].name; i++) {
+ v = test_data[i].handler(&test_data[i]);
+ if (v < 0)
+ err++;
+ }
+
+ if (err == 0)
+ pr_info("test_crc: all %d tests passed\n", i);
+ else
+ pr_err("test_crc: %d cases tested, %d passed, %d failed\n",
+ i, i - err, err);
+
+ return (err == 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 Tue, 2018-07-17 at 22:55 +0800, Coly Li wrote:
> This patch adds the re-write crc64 calculation routines for Linux
> kernel.
> The CRC64 polynomical arithmetic follows ECMA-182 specification,
> inspired
> by CRC paper of Dr. Ross N. Williams
> (see http://www.ross.net/crc/download/crc_v3.txt) and other public
> domain
> implementations.
>
> All the changes work in this way,
> - When Linux kernel is built, host program lib/gen_crc64table.c will
> be
> compiled to lib/gen_crc64table and executed.
> - The output of gen_crc64table execution is an array called as lookup
> table (a.k.a POLY 0x42f0e1eba9ea369) which contain 256 64bits-long
> numbers, this talbe is dumped into header file lib/crc64table.h.
> - Then the header file is included by lib/crc64.c for normal 64bit crc
> calculation.
> - Function declaration of the crc64 calculation routines is placed in
> include/linux/crc64.h
Thanks for an update! My comments below.
> Co-developed-by: Andy Shevchenko <[email protected]>
As required by coding style this tag should be accompanied with SoB of
co-developer(s).
> +u64 __pure crc64_update(u64 crc, const void *_p, size_t len);
For sake of consistency I would name _len as well.
> + * Normal 64bit CRC calculation.
I think 64-bit form is slightly better and more often
$ git grep -n -w 64bit | wc -l
809
$ git grep -n -w 64-bit | wc -l
2957
> + * crc64table[256] is the lookup table of a table-driver 64bit CRC
Ditto.
> + * Copyright 2018 SUSE Linux.
> + * Author: Coly Li <[email protected]>
> + *
This (blank comment) line is not needed.
> +u64 __pure crc64_update(u64 crc, const void *_p, size_t len)
_len ?
> + * Copyright 2018 SUSE Linux.
> + * Author: Coly Li <[email protected]>
> + *
Not needed line.
> +#include <inttypes.h>
> +#include <stdio.h>
+ blank line? Would separate groups of headers logically.
> +#include <linux/swab.h>
> +static int64_t crc64_table[256] = {0,};
I guess {0} would work as well (no comma).
> + printf("#include <uapi/linux/types.h>\n");
> + printf("#include <linux/cache.h>\n\n");
Do wee need these? CRC32 case seems fine without.
--
Andy Shevchenko <[email protected]>
Intel Finland Oy
On Tue, 2018-07-17 at 22:55 +0800, Coly Li wrote:
> 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.
>
Yes, no more PostgreSQL code in kernel!
Reviewed-by: Andy Shevchenko <[email protected]>
> Signed-off-by: Coly Li <[email protected]>
> Reviewed-by: Hannes Reinecke <[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]>
> ---
> drivers/md/bcache/Kconfig | 1 +
> drivers/md/bcache/bcache.h | 7 +-
> drivers/md/bcache/btree.c | 2 +-
> drivers/md/bcache/request.c | 2 +-
> drivers/md/bcache/super.c | 5 +-
> drivers/md/bcache/util.c | 131 ---------------------------------
> ---
> drivers/md/bcache/util.h | 5 +-
> 7 files changed, 11 insertions(+), 142 deletions(-)
>
> diff --git a/drivers/md/bcache/Kconfig b/drivers/md/bcache/Kconfig
> index 17bf109c58e9..af247298409a 100644
> --- a/drivers/md/bcache/Kconfig
> +++ b/drivers/md/bcache/Kconfig
> @@ -1,6 +1,7 @@
>
> config BCACHE
> tristate "Block device as cache"
> + select CRC64
> ---help---
> Allows a block device to be used as cache for other devices;
> uses
> a btree for indexing and the layout is optimized for SSDs.
> diff --git a/drivers/md/bcache/bcache.h b/drivers/md/bcache/bcache.h
> index d6bf294f3907..6d4d2356c3cc 100644
> --- a/drivers/md/bcache/bcache.h
> +++ b/drivers/md/bcache/bcache.h
> @@ -189,6 +189,7 @@
> #include <linux/types.h>
> #include <linux/workqueue.h>
> #include <linux/kthread.h>
> +#include <linux/crc64.h>
>
> #include "bset.h"
> #include "util.h"
> @@ -803,9 +804,9 @@ static inline bool ptr_available(struct cache_set
> *c, const struct bkey *k,
> * jset: The checksum is _always_ the first 8 bytes of these structs
> */
> #define csum_set(i)
> \
> - bch_crc64(((void *) (i)) + sizeof(uint64_t),
> \
> - ((void *) bset_bkey_last(i)) -
> \
> - (((void *) (i)) + sizeof(uint64_t)))
> + crc64_bch(((void *) (i)) + sizeof(uint64_t),
> \
> + ((void *) bset_bkey_last(i)) -
> \
> + (((void *) (i)) + sizeof(uint64_t)))
>
> /* Error handling macros */
>
> diff --git a/drivers/md/bcache/btree.c b/drivers/md/bcache/btree.c
> index 547c9eedc2f4..72619508c928 100644
> --- a/drivers/md/bcache/btree.c
> +++ b/drivers/md/bcache/btree.c
> @@ -194,7 +194,7 @@ static uint64_t btree_csum_set(struct btree *b,
> struct bset *i)
> uint64_t crc = b->key.ptr[0];
> void *data = (void *) i + 8, *end = bset_bkey_last(i);
>
> - crc = bch_crc64_update(crc, data, end - data);
> + crc = crc64_update(crc, data, end - data);
> return crc ^ 0xffffffffffffffffULL;
> }
>
> diff --git a/drivers/md/bcache/request.c b/drivers/md/bcache/request.c
> index ae67f5fa8047..28b2fb11a3d5 100644
> --- a/drivers/md/bcache/request.c
> +++ b/drivers/md/bcache/request.c
> @@ -45,7 +45,7 @@ static void bio_csum(struct bio *bio, struct bkey
> *k)
>
> bio_for_each_segment(bv, bio, iter) {
> void *d = kmap(bv.bv_page) + bv.bv_offset;
> - csum = bch_crc64_update(csum, d, bv.bv_len);
> + csum = crc64_update(csum, d, bv.bv_len);
> kunmap(bv.bv_page);
> }
>
> diff --git a/drivers/md/bcache/super.c b/drivers/md/bcache/super.c
> index fa4058e43202..c425c52f0c42 100644
> --- a/drivers/md/bcache/super.c
> +++ b/drivers/md/bcache/super.c
> @@ -549,7 +549,7 @@ void bch_prio_write(struct cache *ca)
>
> p->next_bucket = ca->prio_buckets[i + 1];
> p->magic = pset_magic(&ca->sb);
> - p->csum = bch_crc64(&p->magic,
> bucket_bytes(ca) - 8);
> + p->csum = crc64_bch(&p->magic,
> bucket_bytes(ca) - 8);
>
> bucket = bch_bucket_alloc(ca, RESERVE_PRIO, true);
> BUG_ON(bucket == -1);
> @@ -599,7 +599,8 @@ static void prio_read(struct cache *ca, uint64_t
> bucket)
>
> prio_io(ca, bucket, REQ_OP_READ, 0);
>
> - if (p->csum != bch_crc64(&p->magic,
> bucket_bytes(ca) - 8))
> + if (p->csum != crc64_bch(&p->magic,
> + bucket_bytes(ca) -
> 8))
> pr_warn("bad csum reading
> priorities");
>
> if (p->magic != pset_magic(&ca->sb))
> diff --git a/drivers/md/bcache/util.c b/drivers/md/bcache/util.c
> index fc479b026d6d..f912c372978c 100644
> --- a/drivers/md/bcache/util.c
> +++ b/drivers/md/bcache/util.c
> @@ -279,134 +279,3 @@ int bch_bio_alloc_pages(struct bio *bio, gfp_t
> gfp_mask)
>
> return 0;
> }
> -
> -/*
> - * Portions Copyright (c) 1996-2001, PostgreSQL Global Development
> Group (Any
> - * use permitted, subject to terms of PostgreSQL license; see.)
> -
> - * If we have a 64-bit integer type, then a 64-bit CRC looks just
> like the
> - * usual sort of implementation. (See Ross Williams' excellent
> introduction
> - * A PAINLESS GUIDE TO CRC ERROR DETECTION ALGORITHMS, available from
> - * ftp://ftp.rocksoft.com/papers/crc_v3.txt or several other net
> sites.)
> - * If we have no working 64-bit type, then fake it with two 32-bit
> registers.
> - *
> - * The present implementation is a normal (not "reflected", in
> Williams'
> - * terms) 64-bit CRC, using initial all-ones register contents and a
> final
> - * bit inversion. The chosen polynomial is borrowed from the DLT1
> spec
> - * (ECMA-182, available from http://www.ecma.ch/ecma1/STAND/ECMA-182.
> HTM):
> - *
> - * x^64 + x^62 + x^57 + x^55 + x^54 + x^53 + x^52 + x^47 + x^46 +
> x^45 +
> - * x^40 + x^39 + x^38 + x^37 + x^35 + x^33 + x^32 + x^31 + x^29 +
> x^27 +
> - * x^24 + x^23 + x^22 + x^21 + x^19 + x^17 + x^13 + x^12 + x^10 + x^9
> +
> - * x^7 + x^4 + x + 1
> -*/
> -
> -static const uint64_t crc_table[256] = {
> - 0x0000000000000000ULL, 0x42F0E1EBA9EA3693ULL,
> 0x85E1C3D753D46D26ULL,
> - 0xC711223CFA3E5BB5ULL, 0x493366450E42ECDFULL,
> 0x0BC387AEA7A8DA4CULL,
> - 0xCCD2A5925D9681F9ULL, 0x8E224479F47CB76AULL,
> 0x9266CC8A1C85D9BEULL,
> - 0xD0962D61B56FEF2DULL, 0x17870F5D4F51B498ULL,
> 0x5577EEB6E6BB820BULL,
> - 0xDB55AACF12C73561ULL, 0x99A54B24BB2D03F2ULL,
> 0x5EB4691841135847ULL,
> - 0x1C4488F3E8F96ED4ULL, 0x663D78FF90E185EFULL,
> 0x24CD9914390BB37CULL,
> - 0xE3DCBB28C335E8C9ULL, 0xA12C5AC36ADFDE5AULL,
> 0x2F0E1EBA9EA36930ULL,
> - 0x6DFEFF5137495FA3ULL, 0xAAEFDD6DCD770416ULL,
> 0xE81F3C86649D3285ULL,
> - 0xF45BB4758C645C51ULL, 0xB6AB559E258E6AC2ULL,
> 0x71BA77A2DFB03177ULL,
> - 0x334A9649765A07E4ULL, 0xBD68D2308226B08EULL,
> 0xFF9833DB2BCC861DULL,
> - 0x388911E7D1F2DDA8ULL, 0x7A79F00C7818EB3BULL,
> 0xCC7AF1FF21C30BDEULL,
> - 0x8E8A101488293D4DULL, 0x499B3228721766F8ULL,
> 0x0B6BD3C3DBFD506BULL,
> - 0x854997BA2F81E701ULL, 0xC7B97651866BD192ULL,
> 0x00A8546D7C558A27ULL,
> - 0x4258B586D5BFBCB4ULL, 0x5E1C3D753D46D260ULL,
> 0x1CECDC9E94ACE4F3ULL,
> - 0xDBFDFEA26E92BF46ULL, 0x990D1F49C77889D5ULL,
> 0x172F5B3033043EBFULL,
> - 0x55DFBADB9AEE082CULL, 0x92CE98E760D05399ULL,
> 0xD03E790CC93A650AULL,
> - 0xAA478900B1228E31ULL, 0xE8B768EB18C8B8A2ULL,
> 0x2FA64AD7E2F6E317ULL,
> - 0x6D56AB3C4B1CD584ULL, 0xE374EF45BF6062EEULL,
> 0xA1840EAE168A547DULL,
> - 0x66952C92ECB40FC8ULL, 0x2465CD79455E395BULL,
> 0x3821458AADA7578FULL,
> - 0x7AD1A461044D611CULL, 0xBDC0865DFE733AA9ULL,
> 0xFF3067B657990C3AULL,
> - 0x711223CFA3E5BB50ULL, 0x33E2C2240A0F8DC3ULL,
> 0xF4F3E018F031D676ULL,
> - 0xB60301F359DBE0E5ULL, 0xDA050215EA6C212FULL,
> 0x98F5E3FE438617BCULL,
> - 0x5FE4C1C2B9B84C09ULL, 0x1D14202910527A9AULL,
> 0x93366450E42ECDF0ULL,
> - 0xD1C685BB4DC4FB63ULL, 0x16D7A787B7FAA0D6ULL,
> 0x5427466C1E109645ULL,
> - 0x4863CE9FF6E9F891ULL, 0x0A932F745F03CE02ULL,
> 0xCD820D48A53D95B7ULL,
> - 0x8F72ECA30CD7A324ULL, 0x0150A8DAF8AB144EULL,
> 0x43A04931514122DDULL,
> - 0x84B16B0DAB7F7968ULL, 0xC6418AE602954FFBULL,
> 0xBC387AEA7A8DA4C0ULL,
> - 0xFEC89B01D3679253ULL, 0x39D9B93D2959C9E6ULL,
> 0x7B2958D680B3FF75ULL,
> - 0xF50B1CAF74CF481FULL, 0xB7FBFD44DD257E8CULL,
> 0x70EADF78271B2539ULL,
> - 0x321A3E938EF113AAULL, 0x2E5EB66066087D7EULL,
> 0x6CAE578BCFE24BEDULL,
> - 0xABBF75B735DC1058ULL, 0xE94F945C9C3626CBULL,
> 0x676DD025684A91A1ULL,
> - 0x259D31CEC1A0A732ULL, 0xE28C13F23B9EFC87ULL,
> 0xA07CF2199274CA14ULL,
> - 0x167FF3EACBAF2AF1ULL, 0x548F120162451C62ULL,
> 0x939E303D987B47D7ULL,
> - 0xD16ED1D631917144ULL, 0x5F4C95AFC5EDC62EULL,
> 0x1DBC74446C07F0BDULL,
> - 0xDAAD56789639AB08ULL, 0x985DB7933FD39D9BULL,
> 0x84193F60D72AF34FULL,
> - 0xC6E9DE8B7EC0C5DCULL, 0x01F8FCB784FE9E69ULL,
> 0x43081D5C2D14A8FAULL,
> - 0xCD2A5925D9681F90ULL, 0x8FDAB8CE70822903ULL,
> 0x48CB9AF28ABC72B6ULL,
> - 0x0A3B7B1923564425ULL, 0x70428B155B4EAF1EULL,
> 0x32B26AFEF2A4998DULL,
> - 0xF5A348C2089AC238ULL, 0xB753A929A170F4ABULL,
> 0x3971ED50550C43C1ULL,
> - 0x7B810CBBFCE67552ULL, 0xBC902E8706D82EE7ULL,
> 0xFE60CF6CAF321874ULL,
> - 0xE224479F47CB76A0ULL, 0xA0D4A674EE214033ULL,
> 0x67C58448141F1B86ULL,
> - 0x253565A3BDF52D15ULL, 0xAB1721DA49899A7FULL,
> 0xE9E7C031E063ACECULL,
> - 0x2EF6E20D1A5DF759ULL, 0x6C0603E6B3B7C1CAULL,
> 0xF6FAE5C07D3274CDULL,
> - 0xB40A042BD4D8425EULL, 0x731B26172EE619EBULL,
> 0x31EBC7FC870C2F78ULL,
> - 0xBFC9838573709812ULL, 0xFD39626EDA9AAE81ULL,
> 0x3A28405220A4F534ULL,
> - 0x78D8A1B9894EC3A7ULL, 0x649C294A61B7AD73ULL,
> 0x266CC8A1C85D9BE0ULL,
> - 0xE17DEA9D3263C055ULL, 0xA38D0B769B89F6C6ULL,
> 0x2DAF4F0F6FF541ACULL,
> - 0x6F5FAEE4C61F773FULL, 0xA84E8CD83C212C8AULL,
> 0xEABE6D3395CB1A19ULL,
> - 0x90C79D3FEDD3F122ULL, 0xD2377CD44439C7B1ULL,
> 0x15265EE8BE079C04ULL,
> - 0x57D6BF0317EDAA97ULL, 0xD9F4FB7AE3911DFDULL,
> 0x9B041A914A7B2B6EULL,
> - 0x5C1538ADB04570DBULL, 0x1EE5D94619AF4648ULL,
> 0x02A151B5F156289CULL,
> - 0x4051B05E58BC1E0FULL, 0x87409262A28245BAULL,
> 0xC5B073890B687329ULL,
> - 0x4B9237F0FF14C443ULL, 0x0962D61B56FEF2D0ULL,
> 0xCE73F427ACC0A965ULL,
> - 0x8C8315CC052A9FF6ULL, 0x3A80143F5CF17F13ULL,
> 0x7870F5D4F51B4980ULL,
> - 0xBF61D7E80F251235ULL, 0xFD913603A6CF24A6ULL,
> 0x73B3727A52B393CCULL,
> - 0x31439391FB59A55FULL, 0xF652B1AD0167FEEAULL,
> 0xB4A25046A88DC879ULL,
> - 0xA8E6D8B54074A6ADULL, 0xEA16395EE99E903EULL,
> 0x2D071B6213A0CB8BULL,
> - 0x6FF7FA89BA4AFD18ULL, 0xE1D5BEF04E364A72ULL,
> 0xA3255F1BE7DC7CE1ULL,
> - 0x64347D271DE22754ULL, 0x26C49CCCB40811C7ULL,
> 0x5CBD6CC0CC10FAFCULL,
> - 0x1E4D8D2B65FACC6FULL, 0xD95CAF179FC497DAULL,
> 0x9BAC4EFC362EA149ULL,
> - 0x158E0A85C2521623ULL, 0x577EEB6E6BB820B0ULL,
> 0x906FC95291867B05ULL,
> - 0xD29F28B9386C4D96ULL, 0xCEDBA04AD0952342ULL,
> 0x8C2B41A1797F15D1ULL,
> - 0x4B3A639D83414E64ULL, 0x09CA82762AAB78F7ULL,
> 0x87E8C60FDED7CF9DULL,
> - 0xC51827E4773DF90EULL, 0x020905D88D03A2BBULL,
> 0x40F9E43324E99428ULL,
> - 0x2CFFE7D5975E55E2ULL, 0x6E0F063E3EB46371ULL,
> 0xA91E2402C48A38C4ULL,
> - 0xEBEEC5E96D600E57ULL, 0x65CC8190991CB93DULL,
> 0x273C607B30F68FAEULL,
> - 0xE02D4247CAC8D41BULL, 0xA2DDA3AC6322E288ULL,
> 0xBE992B5F8BDB8C5CULL,
> - 0xFC69CAB42231BACFULL, 0x3B78E888D80FE17AULL,
> 0x7988096371E5D7E9ULL,
> - 0xF7AA4D1A85996083ULL, 0xB55AACF12C735610ULL,
> 0x724B8ECDD64D0DA5ULL,
> - 0x30BB6F267FA73B36ULL, 0x4AC29F2A07BFD00DULL,
> 0x08327EC1AE55E69EULL,
> - 0xCF235CFD546BBD2BULL, 0x8DD3BD16FD818BB8ULL,
> 0x03F1F96F09FD3CD2ULL,
> - 0x41011884A0170A41ULL, 0x86103AB85A2951F4ULL,
> 0xC4E0DB53F3C36767ULL,
> - 0xD8A453A01B3A09B3ULL, 0x9A54B24BB2D03F20ULL,
> 0x5D45907748EE6495ULL,
> - 0x1FB5719CE1045206ULL, 0x919735E51578E56CULL,
> 0xD367D40EBC92D3FFULL,
> - 0x1476F63246AC884AULL, 0x568617D9EF46BED9ULL,
> 0xE085162AB69D5E3CULL,
> - 0xA275F7C11F7768AFULL, 0x6564D5FDE549331AULL,
> 0x279434164CA30589ULL,
> - 0xA9B6706FB8DFB2E3ULL, 0xEB46918411358470ULL,
> 0x2C57B3B8EB0BDFC5ULL,
> - 0x6EA7525342E1E956ULL, 0x72E3DAA0AA188782ULL,
> 0x30133B4B03F2B111ULL,
> - 0xF7021977F9CCEAA4ULL, 0xB5F2F89C5026DC37ULL,
> 0x3BD0BCE5A45A6B5DULL,
> - 0x79205D0E0DB05DCEULL, 0xBE317F32F78E067BULL,
> 0xFCC19ED95E6430E8ULL,
> - 0x86B86ED5267CDBD3ULL, 0xC4488F3E8F96ED40ULL,
> 0x0359AD0275A8B6F5ULL,
> - 0x41A94CE9DC428066ULL, 0xCF8B0890283E370CULL,
> 0x8D7BE97B81D4019FULL,
> - 0x4A6ACB477BEA5A2AULL, 0x089A2AACD2006CB9ULL,
> 0x14DEA25F3AF9026DULL,
> - 0x562E43B4931334FEULL, 0x913F6188692D6F4BULL,
> 0xD3CF8063C0C759D8ULL,
> - 0x5DEDC41A34BBEEB2ULL, 0x1F1D25F19D51D821ULL,
> 0xD80C07CD676F8394ULL,
> - 0x9AFCE626CE85B507ULL,
> -};
> -
> -uint64_t bch_crc64_update(uint64_t crc, const void *_data, size_t
> len)
> -{
> - const unsigned char *data = _data;
> -
> - while (len--) {
> - int i = ((int) (crc >> 56) ^ *data++) & 0xFF;
> - crc = crc_table[i] ^ (crc << 8);
> - }
> -
> - return crc;
> -}
> -
> -uint64_t bch_crc64(const void *data, size_t len)
> -{
> - uint64_t crc = 0xffffffffffffffffULL;
> -
> - crc = bch_crc64_update(crc, data, len);
> -
> - return crc ^ 0xffffffffffffffffULL;
> -}
> diff --git a/drivers/md/bcache/util.h b/drivers/md/bcache/util.h
> index cced87f8eb27..b1deec0dc958 100644
> --- a/drivers/md/bcache/util.h
> +++ b/drivers/md/bcache/util.h
> @@ -11,6 +11,7 @@
> #include <linux/ratelimit.h>
> #include <linux/vmalloc.h>
> #include <linux/workqueue.h>
> +#include <linux/crc64.h>
>
> #include "closure.h"
>
> @@ -561,8 +562,4 @@ static inline sector_t bdev_sectors(struct
> block_device *bdev)
> {
> return bdev->bd_inode->i_size >> 9;
> }
> -
> -uint64_t bch_crc64_update(uint64_t, const void *, size_t);
> -uint64_t bch_crc64(const void *, size_t);
> -
> #endif /* _BCACHE_UTIL_H */
--
Andy Shevchenko <[email protected]>
Intel Finland Oy
On Tue, 2018-07-17 at 22:55 +0800, Coly Li wrote:
> This patch set adds basic implementation of crc64 calculation as Linux
> kernel library. Since bcache already does crc64 by itself, this patch
> set also modifies bcache code to use the new crc64 library routine.
>
> bcache uses crc64 as storage checksum, if a change of crc lib routines
> results an inconsistent result, the unmatched checksum may make bcache
> 'think' the on-disk is corrupted, such change should be avoided or
> detected as early as possible. Therefore the last patch in this series
> adds a crc test framework, to check consistency of different
> calculations.
>
Thanks, I have commented individual patches, though I didn't see patch
3/3 and...
> Andy Shevchenko (1):
> lib/crc64: add crc64 option to lib/Kconfig
>
> Coly Li (3):
> lib: add crc64 calculation routines
> bcache: use routines from lib/crc64.c for CRC64 calculation
> lib/test_crc: Add test cases for crc calculation
...this part looks weird.
Do you use `git format-patch --cover-letter`?
--
Andy Shevchenko <[email protected]>
Intel Finland Oy
Hi Coly,
On Tue, Jul 17, 2018 at 10:55:23PM +0800, Coly Li wrote:
> This patch adds the re-write crc64 calculation routines for Linux kernel.
> The CRC64 polynomical arithmetic follows ECMA-182 specification, inspired
> by CRC paper of Dr. Ross N. Williams
> (see http://www.ross.net/crc/download/crc_v3.txt) and other public domain
> implementations.
Please also mention who is planned to use this CRC-64 code. Again, if it's just
one user then there's no need for this patchset yet. If bcachefs is planned to
be another user (separate from bcache) then you need to say so.
>
> All the changes work in this way,
> - When Linux kernel is built, host program lib/gen_crc64table.c will be
> compiled to lib/gen_crc64table and executed.
> - The output of gen_crc64table execution is an array called as lookup
> table (a.k.a POLY 0x42f0e1eba9ea369) which contain 256 64bits-long
> numbers, this talbe is dumped into header file lib/crc64table.h.
> - Then the header file is included by lib/crc64.c for normal 64bit crc
> calculation.
> - Function declaration of the crc64 calculation routines is placed in
> include/linux/crc64.h
>
> Changelog:
> 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.
>
> Signed-off-by: Coly Li <[email protected]>
> Co-developed-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]>
> ---
> include/linux/crc64.h | 13 ++++++++
> lib/.gitignore | 2 ++
> lib/Kconfig | 8 +++++
> lib/Makefile | 11 +++++++
> lib/crc64.c | 71 +++++++++++++++++++++++++++++++++++++++++++
> lib/gen_crc64table.c | 69 +++++++++++++++++++++++++++++++++++++++++
> 6 files changed, 174 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..3e87b61cd54f
> --- /dev/null
> +++ b/include/linux/crc64.h
> @@ -0,0 +1,13 @@
> +/* 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_update(u64 crc, const void *_p, size_t len);
> +u64 __pure crc64(const void *p, size_t len);
> +u64 __pure crc64_bch(const void *p, size_t len);
> +#endif /* _LINUX_CRC64_H */
I still think you should make the API consistent with lib/crc32.c by replacing
the three functions with just:
u64 __pure crc64_be(u64 crc, const void *p, size_t len);
Your API maps to it as follows:
crc64_update(crc, p, len) == crc64_be(crc, p, len)
crc64(p, len) == crc64_be(0, p, len)
crc64_bch(p, len) == ~crc64_be(~0, p, len)
The "_be" suffix clarifies that it's not using the bit-reversed convention. We
don't want to have to rename everything when someone needs to do CRC-64 using
the other convention. The CRC-64 in the .xz file format, for example, uses the
bit-reversed convention.
The other problem with your API (besides it being inconsistent with lib/crc32.c)
is that as soon as the caller needs to do something nontrivial, like passing the
data in multiple chunks or using different conventions for the initial and final
values, then they actually have to use only "crc64_update()" anyway, which is
confusing as it makes it sound like there should be a "crc64_init()" and
"crc64_final()" to go along with "crc64_update()".
Also, naming CRC conventions after a specific user ("bch") isn't appropriate.
Thanks,
- Eric
Hi,
On 07/17/2018 07:55 AM, Coly Li wrote:
> diff --git a/lib/test_crc.c b/lib/test_crc.c
> new file mode 100644
> index 000000000000..441bf835fbd3
> --- /dev/null
> +++ b/lib/test_crc.c
> @@ -0,0 +1,138 @@
> +// SPDX-License-Identifier: GPL-2.0
> +/*
> + * CRC test driver
> + *
> + * Copyright (C) 2018 Coly Li <[email protected]>
> + *
> +
> +static int __init test_crc_init(void)
> +{
> + int i;
> + int v, err = 0;
> +
> + pr_info("Kernel CRC consitency testing:\n");
consistency
> + for (i = 0; test_data[i].name; i++) {
> + v = test_data[i].handler(&test_data[i]);
> + if (v < 0)
> + err++;
> + }
> +
> + if (err == 0)
> + pr_info("test_crc: all %d tests passed\n", i);
> + else
> + pr_err("test_crc: %d cases tested, %d passed, %d failed\n",
> + i, i - err, err);
> +
> + return (err == 0) ? 0 : -EINVAL;
> +}
--
~Randy
On Tue, Jul 17, 2018 at 5:55 PM, 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: PASSED (0x4e6b1ff972fa8c55, expected 0x4e6b1ff972fa8c55)
> test_crc: crc64_bch: PASSED (0x0e4f1391d7a4a62e, expected 0x0e4f1391d7a4a62e)
> test_crc: crc64_update: 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 are only test caes for 3 crc routines,
> - crc64()
> - crc64_bch()
> - crc64_update()
Thanks for an update. My comments below.
> Changelog:
> v3: Add test cases passed/failed statistic
> More fixes for review comments of v2
> v2: Fixes for review comments of v1
> v1: Initial version.
Usually this part goes after --- line below.
> 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]>
Please, Cc me as well this one in next version (use my Intel address).
> +#include <linux/async.h>
> +#include <linux/delay.h>
> +#include <linux/fs.h>
> +#include <linux/list.h>
> +#include <linux/module.h>
> +#include <linux/printk.h>
> +#include <linux/miscdevice.h>
> +#include <linux/slab.h>
> +#include <linux/uaccess.h>
> +#include <linux/vmalloc.h>
> +#include <linux/crc64.h>
Do we need all of them?
> +static int chk_and_msg(const char *name, u64 crc, u64 expval)
> +{
> + int ret = 0;
> +
> + if (crc == expval) {
> + pr_info("test_crc: %s: PASSED:(0x%016llx, expected 0x%016llx)\n",
> + name, crc, expval);
This doesn't bring anything useful.
> + } else {
> + pr_err("test_crc: %s: FAILED:(0x%016llx, expected 0x%016llx)\n",
> + name, crc, expval);
> + ret = -EINVAL;
> + }
> +
> + return ret;
I would rewrite entire function as follows:
static void ...(...)
{
total_tests++;
if (crc == expval)
return;
pr_err(...);
failed_tests++;
}
> +}
> +static int __init test_crc_init(void)
> +{
> + int i;
> + int v, err = 0;
> +
> + pr_info("Kernel CRC consitency testing:\n");
> + for (i = 0; test_data[i].name; i++) {
> + v = test_data[i].handler(&test_data[i]);
> + if (v < 0)
> + err++;
> + }
...and correct this to simple
for (...)
test_data[i].handler(...);
> + if (err == 0)
> + pr_info("test_crc: all %d tests passed\n", i);
> + else
> + pr_err("test_crc: %d cases tested, %d passed, %d failed\n",
> + i, i - err, err);
...and this accordingly.
Note, that in the future someone can add more test cases one or more
of which could not map 1:1 to i here.
That's why the rationale to have two global variables for test statistics.
Also it allows (as you see above) to get rid of return code from all
of those test. We don't interested in them I believe.
> +
> + return (err == 0) ? 0 : -EINVAL;
> +}
--
With Best Regards,
Andy Shevchenko
On Tue, Jul 17, 2018 at 10:56 AM 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: PASSED (0x4e6b1ff972fa8c55, expected 0x4e6b1ff972fa8c55)
> test_crc: crc64_bch: PASSED (0x0e4f1391d7a4a62e, expected 0x0e4f1391d7a4a62e)
> test_crc: crc64_update: 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 are only test caes for 3 crc routines,
> - crc64()
> - crc64_bch()
> - crc64_update()
>
> Changelog:
> v3: Add test cases passed/failed statistic
> More fixes for review comments of v2
> v2: Fixes for review comments of v1
> v1: Initial version.
>
> 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]>
> ---
> lib/Kconfig.debug | 10 ++++
> lib/Makefile | 1 +
> lib/test_crc.c | 138 ++++++++++++++++++++++++++++++++++++++++++++++
> 3 files changed, 149 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..441bf835fbd3
> --- /dev/null
> +++ b/lib/test_crc.c
> @@ -0,0 +1,138 @@
> +// 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()
> + * - crc64_bch()
> + * - crc64_update()
> + *
> + */
> +
> +#include <linux/async.h>
> +#include <linux/delay.h>
> +#include <linux/fs.h>
> +#include <linux/list.h>
> +#include <linux/module.h>
> +#include <linux/printk.h>
> +#include <linux/miscdevice.h>
> +#include <linux/slab.h>
> +#include <linux/uaccess.h>
> +#include <linux/vmalloc.h>
> +#include <linux/crc64.h>
> +
> +struct crc_test_record {
> + char *name;
> + u64 data[4];
> + u64 initval;
> + u64 expval;
> + int (*handler)(struct crc_test_record *rec);
> +};
> +
> +static int chk_and_msg(const char *name, u64 crc, u64 expval)
> +{
> + int ret = 0;
> +
> + if (crc == expval) {
> + pr_info("test_crc: %s: PASSED:(0x%016llx, expected 0x%016llx)\n",
> + name, crc, expval);
I don't think we should have specific kernel output for passed tests.
If a new test is added which follows this pattern, the 0-day will fail
because the kernel output would change. Along the lines of "silence is
golden", if no test hit the error output, we're good.
> + } else {
> + pr_err("test_crc: %s: FAILED:(0x%016llx, expected 0x%016llx)\n",
> + name, crc, expval);
> + ret = -EINVAL;
> + }
> +
> + return ret;
> +}
> +
> +/* Add your crc test cases here */
> +static int test_crc64(struct crc_test_record *rec)
> +{
> + u64 crc;
> +
> + crc = crc64(rec->data, sizeof(rec->data));
> + return chk_and_msg(rec->name, crc, rec->expval);
> +}
> +
> +static int test_crc64_bch(struct crc_test_record *rec)
> +{
> + u64 crc;
> +
> + crc = crc64_bch(rec->data, sizeof(rec->data));
> + return chk_and_msg(rec->name, crc, rec->expval);
> +}
> +
> +static int test_crc64_update(struct crc_test_record *rec)
> +{
> + u64 crc = rec->initval;
> +
> + crc = crc64_update(crc, rec->data, sizeof(rec->data));
> + return chk_and_msg(rec->name, crc, rec->expval);
> +}
> +
> +/*
> + * Set up your crc test initial data here.
> + * Do not change the existing items, they are hard coded with
> + * pre-calculated values.
> + */
> +static struct crc_test_record test_data[] = {
> + { .name = "crc64",
> + .data = { 0x42F0E1EBA9EA3693, 0x85E1C3D753D46D26,
> + 0xC711223CFA3E5BB5, 0x493366450E42ECDF },
> + .initval = 0,
> + .expval = 0xe2b9911e7b997201,
> + .handler = test_crc64,
> + },
> + { .name = "crc64_bch",
> + .data = { 0x42F0E1EBA9EA3693, 0x85E1C3D753D46D26,
> + 0xC711223CFA3E5BB5, 0x493366450E42ECDF },
> + .initval = 0,
> + .expval = 0xd2753a20fd862892,
> + .handler = test_crc64_bch,
> + },
> + { .name = "crc64_update",
> + .data = { 0x42F0E1EBA9EA3693, 0x85E1C3D753D46D26,
> + 0xC711223CFA3E5BB5, 0x493366450E42ECDF },
> + .initval = 0x61C8864680B583EB,
> + .expval = 0xb2c863673f4292bf,
> + .handler = test_crc64_update,
> + },
> + {}
> +};
> +
> +static int __init test_crc_init(void)
> +{
> + int i;
> + int v, err = 0;
> +
> + pr_info("Kernel CRC consitency testing:\n");
> + for (i = 0; test_data[i].name; i++) {
> + v = test_data[i].handler(&test_data[i]);
> + if (v < 0)
> + err++;
> + }
> +
> + if (err == 0)
> + pr_info("test_crc: all %d tests passed\n", i);
Similar to previous comment: we should not report the number of passed
tests, since adding a test would invalidate previous golden output.
Also, consider the situation where some tests are conditionally
executed depending on kconfig.
> + else
> + pr_err("test_crc: %d cases tested, %d passed, %d failed\n",
> + i, i - err, err);
> +
> + return (err == 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
>
> --
> To unsubscribe from this list: send the line "unsubscribe linux-bcache" in
> the body of a message to [email protected]
> More majordomo info at http://vger.kernel.org/majordomo-info.html
On Tue, Jul 17, 2018 at 9:51 PM, Noah Massey <[email protected]> wrote:
> On Tue, Jul 17, 2018 at 10:56 AM Coly Li <[email protected]> wrote:
>> + pr_info("test_crc: %s: PASSED:(0x%016llx, expected 0x%016llx)\n",
>> + name, crc, expval);
>
> I don't think we should have specific kernel output for passed tests.
> If a new test is added which follows this pattern, the 0-day will fail
> because the kernel output would change. Along the lines of "silence is
> golden", if no test hit the error output, we're good.
Agree.
>> + if (err == 0)
>> + pr_info("test_crc: all %d tests passed\n", i);
>
> Similar to previous comment: we should not report the number of passed
> tests, since adding a test would invalidate previous golden output.
> Also, consider the situation where some tests are conditionally
> executed depending on kconfig.
We do similar in many test modules and I know at least two that had
been changed in order to get new test cases.
Are you proposing to change 'em all?
--
With Best Regards,
Andy Shevchenko
On 2018/7/17 11:43 PM, Andy Shevchenko wrote:
> On Tue, 2018-07-17 at 22:55 +0800, Coly Li wrote:
>> This patch adds the re-write crc64 calculation routines for Linux
>> kernel.
>> The CRC64 polynomical arithmetic follows ECMA-182 specification,
>> inspired
>> by CRC paper of Dr. Ross N. Williams
>> (see http://www.ross.net/crc/download/crc_v3.txt) and other public
>> domain
>> implementations.
>>
>> All the changes work in this way,
>> - When Linux kernel is built, host program lib/gen_crc64table.c will
>> be
>> compiled to lib/gen_crc64table and executed.
>> - The output of gen_crc64table execution is an array called as lookup
>> table (a.k.a POLY 0x42f0e1eba9ea369) which contain 256 64bits-long
>> numbers, this talbe is dumped into header file lib/crc64table.h.
>> - Then the header file is included by lib/crc64.c for normal 64bit crc
>> calculation.
>> - Function declaration of the crc64 calculation routines is placed in
>> include/linux/crc64.h
>
> Thanks for an update! My comments below.
>
>> Co-developed-by: Andy Shevchenko <[email protected]>
>
> As required by coding style this tag should be accompanied with SoB of
> co-developer(s).
>
Now I change the lines as following in commit log,
Co-developed-by: Andy Shevchenko <[email protected]>
Signed-off-by: Andy Shevchenko <[email protected]>
>> +u64 __pure crc64_update(u64 crc, const void *_p, size_t len);
>
> For sake of consistency I would name _len as well.
>
Hmm, I will use 'p', and use '_p' for internal argument.
>> + * Normal 64bit CRC calculation.
>
> I think 64-bit form is slightly better and more often
>
> $ git grep -n -w 64bit | wc -l
> 809
>
> $ git grep -n -w 64-bit | wc -l
> 2957
>
>> + * crc64table[256] is the lookup table of a table-driver 64bit CRC
>
> Ditto.
>
Sure, I will change them to 64-bit.
>> + * Copyright 2018 SUSE Linux.
>> + * Author: Coly Li <[email protected]>
>
>> + *
>
> This (blank comment) line is not needed.
>
>> +u64 __pure crc64_update(u64 crc, const void *_p, size_t len)
>
> _len ?
>
I will rename '_p' to 'p' here too.
>> + * Copyright 2018 SUSE Linux.
>> + * Author: Coly Li <[email protected]>
>
>> + *
>
> Not needed line.
>
Fixed in v4.
>> +#include <inttypes.h>
>> +#include <stdio.h>
>
> + blank line? Would separate groups of headers logically.
>
>> +#include <linux/swab.h>
>
>> +static int64_t crc64_table[256] = {0,};
>
> I guess {0} would work as well (no comma).
Fixed them in v4.
>
>> + printf("#include <uapi/linux/types.h>\n");
>> + printf("#include <linux/cache.h>\n\n");
>
> Do wee need these? CRC32 case seems fine without.
>
I renamed uapi/linux/types.h to linux/types.h, this header is for 'u64'.
Another header linux/cache.h is for '____cacheline_aligned'. They should
be necessary if these two headers are not included before
lib/crc64table.h is included.
Thanks for your review :-)
Coly Li
On 2018/7/18 12:31 AM, Eric Biggers wrote:
> Hi Coly,
>
> On Tue, Jul 17, 2018 at 10:55:23PM +0800, Coly Li wrote:
>> This patch adds the re-write crc64 calculation routines for Linux kernel.
>> The CRC64 polynomical arithmetic follows ECMA-182 specification, inspired
>> by CRC paper of Dr. Ross N. Williams
>> (see http://www.ross.net/crc/download/crc_v3.txt) and other public domain
>> implementations.
>
> Please also mention who is planned to use this CRC-64 code. Again, if it's just
> one user then there's no need for this patchset yet. If bcachefs is planned to
> be another user (separate from bcache) then you need to say so.
>
>>
>> All the changes work in this way,
>> - When Linux kernel is built, host program lib/gen_crc64table.c will be
>> compiled to lib/gen_crc64table and executed.
>> - The output of gen_crc64table execution is an array called as lookup
>> table (a.k.a POLY 0x42f0e1eba9ea369) which contain 256 64bits-long
>> numbers, this talbe is dumped into header file lib/crc64table.h.
>> - Then the header file is included by lib/crc64.c for normal 64bit crc
>> calculation.
>> - Function declaration of the crc64 calculation routines is placed in
>> include/linux/crc64.h
>>
>> Changelog:
>> 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.
>>
>> Signed-off-by: Coly Li <[email protected]>
>> Co-developed-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]>
>> ---
>> include/linux/crc64.h | 13 ++++++++
>> lib/.gitignore | 2 ++
>> lib/Kconfig | 8 +++++
>> lib/Makefile | 11 +++++++
>> lib/crc64.c | 71 +++++++++++++++++++++++++++++++++++++++++++
>> lib/gen_crc64table.c | 69 +++++++++++++++++++++++++++++++++++++++++
>> 6 files changed, 174 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..3e87b61cd54f
>> --- /dev/null
>> +++ b/include/linux/crc64.h
>> @@ -0,0 +1,13 @@
>> +/* 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_update(u64 crc, const void *_p, size_t len);
>> +u64 __pure crc64(const void *p, size_t len);
>> +u64 __pure crc64_bch(const void *p, size_t len);
>> +#endif /* _LINUX_CRC64_H */
>
> I still think you should make the API consistent with lib/crc32.c by replacing
> the three functions with just:
>
> u64 __pure crc64_be(u64 crc, const void *p, size_t len);
>
> Your API maps to it as follows:
>
> crc64_update(crc, p, len) == crc64_be(crc, p, len)
> crc64(p, len) == crc64_be(0, p, len)
> crc64_bch(p, len) == ~crc64_be(~0, p, len)
>
> The "_be" suffix clarifies that it's not using the bit-reversed convention. We
> don't want to have to rename everything when someone needs to do CRC-64 using
> the other convention. The CRC-64 in the .xz file format, for example, uses the
> bit-reversed convention.
>
> The other problem with your API (besides it being inconsistent with lib/crc32.c)
> is that as soon as the caller needs to do something nontrivial, like passing the
> data in multiple chunks or using different conventions for the initial and final
> values, then they actually have to use only "crc64_update()" anyway, which is
> confusing as it makes it sound like there should be a "crc64_init()" and
> "crc64_final()" to go along with "crc64_update()".
>
> Also, naming CRC conventions after a specific user ("bch") isn't appropriate.
Agree. I will only keep crc64_be() in lib/crc64.c, and move the rested
back to bcache code with proper names. The change will be in v4 series.
Thanks.
Coly Li
On 2018/7/18 12:57 AM, Randy Dunlap wrote:
> Hi,
>
> On 07/17/2018 07:55 AM, Coly Li wrote:
>
>> diff --git a/lib/test_crc.c b/lib/test_crc.c
>> new file mode 100644
>> index 000000000000..441bf835fbd3
>> --- /dev/null
>> +++ b/lib/test_crc.c
>> @@ -0,0 +1,138 @@
>> +// SPDX-License-Identifier: GPL-2.0
>> +/*
>> + * CRC test driver
>> + *
>> + * Copyright (C) 2018 Coly Li <[email protected]>
>> + *
>
>> +
>> +static int __init test_crc_init(void)
>> +{
>> + int i;
>> + int v, err = 0;
>> +
>> + pr_info("Kernel CRC consitency testing:\n");
>
> consistency
>
Fixed in v4 series. Thanks.
Coly Li
[snipped]
On 2018/7/18 2:51 AM, Noah Massey wrote:
> On Tue, Jul 17, 2018 at 10:56 AM 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: PASSED (0x4e6b1ff972fa8c55, expected 0x4e6b1ff972fa8c55)
>> test_crc: crc64_bch: PASSED (0x0e4f1391d7a4a62e, expected 0x0e4f1391d7a4a62e)
>> test_crc: crc64_update: 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 are only test caes for 3 crc routines,
>> - crc64()
>> - crc64_bch()
>> - crc64_update()
>>
>> Changelog:
>> v3: Add test cases passed/failed statistic
>> More fixes for review comments of v2
>> v2: Fixes for review comments of v1
>> v1: Initial version.
>>
>> 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]>
>> ---
>> lib/Kconfig.debug | 10 ++++
>> lib/Makefile | 1 +
>> lib/test_crc.c | 138 ++++++++++++++++++++++++++++++++++++++++++++++
>> 3 files changed, 149 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..441bf835fbd3
>> --- /dev/null
>> +++ b/lib/test_crc.c
>> @@ -0,0 +1,138 @@
>> +// 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()
>> + * - crc64_bch()
>> + * - crc64_update()
>> + *
>> + */
>> +
>> +#include <linux/async.h>
>> +#include <linux/delay.h>
>> +#include <linux/fs.h>
>> +#include <linux/list.h>
>> +#include <linux/module.h>
>> +#include <linux/printk.h>
>> +#include <linux/miscdevice.h>
>> +#include <linux/slab.h>
>> +#include <linux/uaccess.h>
>> +#include <linux/vmalloc.h>
>> +#include <linux/crc64.h>
>> +
>> +struct crc_test_record {
>> + char *name;
>> + u64 data[4];
>> + u64 initval;
>> + u64 expval;
>> + int (*handler)(struct crc_test_record *rec);
>> +};
>> +
>> +static int chk_and_msg(const char *name, u64 crc, u64 expval)
>> +{
>> + int ret = 0;
>> +
>> + if (crc == expval) {
>> + pr_info("test_crc: %s: PASSED:(0x%016llx, expected 0x%016llx)\n",
>> + name, crc, expval);
>
> I don't think we should have specific kernel output for passed tests.
> If a new test is added which follows this pattern, the 0-day will fail
> because the kernel output would change. Along the lines of "silence is
> golden", if no test hit the error output, we're good.
>
>> + } else {
>> + pr_err("test_crc: %s: FAILED:(0x%016llx, expected 0x%016llx)\n",
>> + name, crc, expval);
>> + ret = -EINVAL;
>> + }
>> +
>> + return ret;
>> +}
>> +
>> +/* Add your crc test cases here */
>> +static int test_crc64(struct crc_test_record *rec)
>> +{
>> + u64 crc;
>> +
>> + crc = crc64(rec->data, sizeof(rec->data));
>> + return chk_and_msg(rec->name, crc, rec->expval);
>> +}
>> +
>> +static int test_crc64_bch(struct crc_test_record *rec)
>> +{
>> + u64 crc;
>> +
>> + crc = crc64_bch(rec->data, sizeof(rec->data));
>> + return chk_and_msg(rec->name, crc, rec->expval);
>> +}
>> +
>> +static int test_crc64_update(struct crc_test_record *rec)
>> +{
>> + u64 crc = rec->initval;
>> +
>> + crc = crc64_update(crc, rec->data, sizeof(rec->data));
>> + return chk_and_msg(rec->name, crc, rec->expval);
>> +}
>> +
>> +/*
>> + * Set up your crc test initial data here.
>> + * Do not change the existing items, they are hard coded with
>> + * pre-calculated values.
>> + */
>> +static struct crc_test_record test_data[] = {
>> + { .name = "crc64",
>> + .data = { 0x42F0E1EBA9EA3693, 0x85E1C3D753D46D26,
>> + 0xC711223CFA3E5BB5, 0x493366450E42ECDF },
>> + .initval = 0,
>> + .expval = 0xe2b9911e7b997201,
>> + .handler = test_crc64,
>> + },
>> + { .name = "crc64_bch",
>> + .data = { 0x42F0E1EBA9EA3693, 0x85E1C3D753D46D26,
>> + 0xC711223CFA3E5BB5, 0x493366450E42ECDF },
>> + .initval = 0,
>> + .expval = 0xd2753a20fd862892,
>> + .handler = test_crc64_bch,
>> + },
>> + { .name = "crc64_update",
>> + .data = { 0x42F0E1EBA9EA3693, 0x85E1C3D753D46D26,
>> + 0xC711223CFA3E5BB5, 0x493366450E42ECDF },
>> + .initval = 0x61C8864680B583EB,
>> + .expval = 0xb2c863673f4292bf,
>> + .handler = test_crc64_update,
>> + },
>> + {}
>> +};
>> +
>> +static int __init test_crc_init(void)
>> +{
>> + int i;
>> + int v, err = 0;
>> +
>> + pr_info("Kernel CRC consitency testing:\n");
>> + for (i = 0; test_data[i].name; i++) {
>> + v = test_data[i].handler(&test_data[i]);
>> + if (v < 0)
>> + err++;
>> + }
>> +
>> + if (err == 0)
>> + pr_info("test_crc: all %d tests passed\n", i);
>
> Similar to previous comment: we should not report the number of passed
> tests, since adding a test would invalidate previous golden output.
> Also, consider the situation where some tests are conditionally
> executed depending on kconfig.
Sure, I fix this in v4 series. Thanks.
Coly Li
[snipped]
On 2018/7/18 1:11 AM, Andy Shevchenko wrote:
> On Tue, Jul 17, 2018 at 5:55 PM, 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: PASSED (0x4e6b1ff972fa8c55, expected 0x4e6b1ff972fa8c55)
>> test_crc: crc64_bch: PASSED (0x0e4f1391d7a4a62e, expected 0x0e4f1391d7a4a62e)
>> test_crc: crc64_update: 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 are only test caes for 3 crc routines,
>> - crc64()
>> - crc64_bch()
>> - crc64_update()
>
> Thanks for an update. My comments below.
>
>> Changelog:
>> v3: Add test cases passed/failed statistic
>> More fixes for review comments of v2
>> v2: Fixes for review comments of v1
>> v1: Initial version.
>
> Usually this part goes after --- line below.
>
OK, I change all the patches in this way.
>> 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]>
>
> Please, Cc me as well this one in next version (use my Intel address).
>
Added :-)
>> +#include <linux/async.h>
>> +#include <linux/delay.h>
>> +#include <linux/fs.h>
>> +#include <linux/list.h>
>> +#include <linux/module.h>
>> +#include <linux/printk.h>
>> +#include <linux/miscdevice.h>
>> +#include <linux/slab.h>
>> +#include <linux/uaccess.h>
>> +#include <linux/vmalloc.h>
>> +#include <linux/crc64.h>
>
> Do we need all of them?
>
I remove most of them, only keep linux/module.h and linux/crc64.h in v4
series.
>> +static int chk_and_msg(const char *name, u64 crc, u64 expval)
>> +{
>
>> + int ret = 0;
>> +
>> + if (crc == expval) {
>
>> + pr_info("test_crc: %s: PASSED:(0x%016llx, expected 0x%016llx)\n",
>> + name, crc, expval);
>
> This doesn't bring anything useful.
>
>> + } else {
>> + pr_err("test_crc: %s: FAILED:(0x%016llx, expected 0x%016llx)\n",
>> + name, crc, expval);
>> + ret = -EINVAL;
>> + }
>> +
>> + return ret;
>
> I would rewrite entire function as follows:
>
> static void ...(...)
> {
> total_tests++;
> if (crc == expval)
> return;
>
> pr_err(...);
> failed_tests++;
> }
>
>
>> +}
>
>> +static int __init test_crc_init(void)
>> +{
>> + int i;
>> + int v, err = 0;
>> +
>> + pr_info("Kernel CRC consitency testing:\n");
>
>> + for (i = 0; test_data[i].name; i++) {
>> + v = test_data[i].handler(&test_data[i]);
>> + if (v < 0)
>> + err++;
>> + }
>
> ...and correct this to simple
> for (...)
> test_data[i].handler(...);
>
>> + if (err == 0)
>> + pr_info("test_crc: all %d tests passed\n", i);
>> + else
>> + pr_err("test_crc: %d cases tested, %d passed, %d failed\n",
>> + i, i - err, err);
>
> ...and this accordingly.
>
> Note, that in the future someone can add more test cases one or more
> of which could not map 1:1 to i here.
> That's why the rationale to have two global variables for test statistics.
> Also it allows (as you see above) to get rid of return code from all
> of those test. We don't interested in them I believe.
Yes, your code is simpler and more elegant IMHO. I change the code as
you suggested in v4 series.
Thanks.
Coly Li
On Tue, Jul 17, 2018 at 4:59 PM Andy Shevchenko
<[email protected]> wrote:
> On Tue, Jul 17, 2018 at 9:51 PM, Noah Massey <[email protected]> wrote:
> > On Tue, Jul 17, 2018 at 10:56 AM Coly Li <[email protected]> wrote:
>
> >> + if (err == 0)
> >> + pr_info("test_crc: all %d tests passed\n", i);
> >
> > Similar to previous comment: we should not report the number of passed
> > tests, since adding a test would invalidate previous golden output.
> > Also, consider the situation where some tests are conditionally
> > executed depending on kconfig.
>
> We do similar in many test modules and I know at least two that had
> been changed in order to get new test cases.
> Are you proposing to change 'em all?
>
I was proposing that the message should be "test_crc: all tests
passed\n", since that would maintain a static expected output. Upon
further review, parsing minor variations in the messages is simple
enough so if the automated test tools already handle it keeping the
test count in the output is better.
Sorry for the noise,
~ Noah
On 2018/7/17 10:55 PM, Coly Li wrote:
> This patch set adds basic implementation of crc64 calculation as Linux
> kernel library. Since bcache already does crc64 by itself, this patch
> set also modifies bcache code to use the new crc64 library routine.
>
> bcache uses crc64 as storage checksum, if a change of crc lib routines
> results an inconsistent result, the unmatched checksum may make bcache
> 'think' the on-disk is corrupted, such change should be avoided or
> detected as early as possible. Therefore the last patch in this series
> adds a crc test framework, to check consistency of different calculations.
>
> Changelog:
> 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
Hi folks,
Many thanks for your review and comments, I do appreciate for your help.
Also thank Andrew to pick up the patches.
Coly Li
From: Coly Li
> Sent: 17 July 2018 15:55
>
> 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.
That seems excessive for a fixed table.
No real point doing more than putting a commented out copy of the code
with the initialisation data.
> - The output of gen_crc64table execution is an array called as lookup
> table (a.k.a POLY 0x42f0e1eba9ea369) which contain 256 64bits-long
> numbers, this talbe is dumped into header file lib/crc64table.h.
> - Then the header file is included by lib/crc64.c for normal 64bit crc
> calculation.
How long are the buffers being processed?
For short buffers a lot of bytes will suffer cache line misses.
For longer buffers you'll be displacing 2k of data from the L1 data cache.
That could easily have a knock on effect on the surrounding code.
You might find that a nibble based loop and lookup table is faster.
Or, relying on the linearity of CRCs, separate lookup tables
for the high and low nibbles of each byte.
So replacing:
crc = crc64table[t] ^ (crc << 8);
with:
crc = crc64table_hi[t >> 4] ^ crc64table_lo[t & 15] ^ (crc << 8);
David
-
Registered Address Lakeside, Bramley Road, Mount Farm, Milton Keynes, MK1 1PT, UK
Registration No: 1397386 (Wales)