Re: [PATCH 2/4] lib: add crc64 calculation routines

[Eric Biggers]

On Tue, Jul 17, 2018 at 02:25:24PM +0800, Coly Li wrote:
> On 2018/7/17 11:34 AM, Eric Biggers wrote:
> > Hi Coly,
> > 
> > On Tue, Jul 17, 2018 at 12:55:05AM +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
> >>
> > [...]
> >> 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@xxxxxxx>
> >> + *
> >> + */
> >> +
> >> +#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,
> 
> > 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().
> 
> > 
> > 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?

> 
> 
> >> 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@xxxxxxx>
> >> + *
> >> + */
> >> +
> >> +#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.
> > 
> >> +
> >> +#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