linux-kernel - RE: [PATCH v3 1/3] lib: add crc64 calculation routines

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [<thread-prev] [day] [month] [year] [list]

Date:   Tue, 24 Jul 2018 13:33:52 +0000
From:   David Laight <David.Laight@...LAB.COM>
To:     'Coly Li' <colyli@...e.de>,
        "linux-kernel@...r.kernel.org" <linux-kernel@...r.kernel.org>
CC:     "linux-bcache@...r.kernel.org" <linux-bcache@...r.kernel.org>,
        "linux-block@...r.kernel.org" <linux-block@...r.kernel.org>,
        "Greg Kroah-Hartman" <gregkh@...uxfoundation.org>,
        Andy Shevchenko <andriy.shevchenko@...ux.intel.com>,
        Michael Lyle <mlyle@...e.org>,
        "Kent Overstreet" <kent.overstreet@...il.com>,
        Linus Torvalds <torvalds@...ux-foundation.org>,
        Thomas Gleixner <tglx@...utronix.de>,
        "Kate Stewart" <kstewart@...uxfoundation.org>,
        Eric Biggers <ebiggers3@...il.com>
Subject: RE: [PATCH v3 1/3] lib: add crc64 calculation routines

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)