linux-kernel - Re: [PATCH 0/1] Add KUnit tests for lib/crc16.c

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]

Message-ID: <1ca713fc-2675-4154-ad46-a3fe11839148@lkcamp.dev>
Date: Sun, 29 Sep 2024 22:18:26 -0300
From: Vinicius Peixoto <vpeixoto@...amp.dev>
To: David Laight <David.Laight@...LAB.COM>,
 Brendan Higgins <brendan.higgins@...ux.dev>, David Gow
 <davidgow@...gle.com>, Rae Moar <rmoar@...gle.com>,
 "linux-kselftest@...r.kernel.org" <linux-kselftest@...r.kernel.org>,
 "kunit-dev@...glegroups.com" <kunit-dev@...glegroups.com>,
 "linux-kernel@...r.kernel.org" <linux-kernel@...r.kernel.org>,
 Andrew Morton <akpm@...ux-foundation.org>,
 "~lkcamp/patches@...ts.sr.ht" <~lkcamp/patches@...ts.sr.ht>
Subject: Re: [PATCH 0/1] Add KUnit tests for lib/crc16.c

Hi David,

On 9/25/24 08:26, David Laight wrote:
> From: Vinicius Peixoto
>> Sent: 23 September 2024 00:27
>>
>> Hi all,
>>
>> This patch was developed during a hackathon organized by LKCAMP [1],
>> with the objective of writing KUnit tests, both to introduce people to
>> the kernel development process and to learn about different subsystems
>> (with the positive side effect of improving the kernel test coverage, of
>> course).
>>
>> We noticed there were tests for CRC32 in lib/crc32test.c and thought it
>> would be nice to have something similar for CRC16, since it seems to be
>> widely used in network drivers (as well as in some ext4 code).
>>
>> Although this patch turned out quite big, most of the LOCs come from
>> tables containing randomly-generated test data that we use to validate
>> the kernel's implementation of CRC-16.
>>
>> We would really appreciate any feedback/suggestions on how to improve
>> this. Thanks! :-)
> 
> Would is be better to use a trivial PRNG to generate repeatable 'random enough'
> data, rather than having a large static array?

That's fair, the big static arrays are indeed very unwieldy. I reworked 
it to use next_pseudo_random32 (from include/linux/prandom.h) to fill 
the tables with pseudorandom data before running the tests, and will 
send a v2 soon.

The LOC count is a lot smaller, although it is still using static tables 
to store the data and the tests (I thought it would be simpler than 
allocating them at runtime). Do you think this is acceptable?

> As a matter of interest, how in crc16 implemented (I know I could look).
> The code version:
> 
> uint32_t
> crc_step(uint32_t crc, uint32_t byte_val)
> {
>      uint32_t t = crc ^ (byte_val & 0xff);
>      t = (t ^ t << 4) & 0xff;
>      return crc >> 8 ^ t << 8 ^ t << 3 ^ t >> 4;
> }
> 
> may well be faster than a lookup table version.
> Especially on modern multi-issue cpu and/or for small buffers where the lookup
> table won't necessarily be resident in the D-cache.

lib/crc16.c does use a lookup table. I haven't had the time to run 
benchmarks testing whether this version is faster, but I'm curious as 
well, so I'll look into it.

Thanks,
Vinicius

> 
> It is slightly slower than the table lookup on the simple Nios-II cpu.
> But we use a custom instruction to do it in one clock.
> 
> 	David
> 
>>
>> Vinicius Peixoto (1):
>>    lib/crc16_kunit.c: add KUnit tests for crc16
>>
>>   lib/Kconfig.debug |   8 +
>>   lib/Makefile      |   1 +
>>   lib/crc16_kunit.c | 715 ++++++++++++++++++++++++++++++++++++++++++++++
>>   3 files changed, 724 insertions(+)
>>   create mode 100644 lib/crc16_kunit.c
>>
>> --
>> 2.43.0
>>
> 
> -
> Registered Address Lakeside, Bramley Road, Mount Farm, Milton Keynes, MK1 1PT, UK
> Registration No: 1397386 (Wales)