On Tue, Jul 17, 2018 at 02:25:24PM +0800, Coly Li wrote:

On 2018/7/17 11:34 AM, Eric Biggers wrote:

quoted

Hi Coly,

On Tue, Jul 17, 2018 at 12:55:05AM +0800, Coly Li wrote:

quoted

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

[...]

quoted

diff --git a/lib/crc64.c b/lib/crc64.c
new file mode 100644
index 000000000000..03f078303bd3
--- /dev/null
+++ b/lib/crc64.c

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

Hi Eric,

quoted

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

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

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

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

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

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

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

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

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

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

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

quoted

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

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

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

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

quoted

quoted

diff --git a/lib/gen_crc64table.c b/lib/gen_crc64table.c
new file mode 100644
index 000000000000..5f292f287498
--- /dev/null
+++ b/lib/gen_crc64table.c

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

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

quoted

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

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

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

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

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

- Eric