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! :-)

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

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?

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.

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)

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)

Hey!

On 9/23/24 01:26, Vinicius Peixoto wrote:
> 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.
Can you share how you created the tables? Given that is impossible to 
review the table itself, at least people will be able to see how they 
got created at least.
> We would really appreciate any feedback/suggestions on how to improve
> this. Thanks! :-)
>
> 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
>

Hi André,

On 9/24/24 6:33 PM, André Almeida wrote:
> Hey!
> 
> On 9/23/24 01:26, Vinicius Peixoto wrote:
>> 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.
> Can you share how you created the tables? Given that is impossible to 
> review the table itself, at least people will be able to see how they 
> got created at least.

Yes, of course, that was an oversight on my part. I'll make sure to add 
a more detailed explanation in the cover letter/commit message for the 
next revisions. Thanks for the suggestion!

This test follows lib/crc32test.c very closely; the data table is filled 
with 4096 random bytes, and the idea is to calculate several checksums 
within it by randomly choosing a i) start offset within the data buffer, 
ii) number of bytes after the start offset and iii) input CRC.

The checksums for the randomly-generated test cases were calculated 
using a reference implementation [1] and this test compares them against 
the values yielded by the kernel's implementation.

Thanks,
Vinicius

[1] https://github.com/lammertb/libcrc/blob/master/src/crc16.c

>> We would really appreciate any feedback/suggestions on how to improve
>> this. Thanks! :-)
>>
>> 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
>>

...
> The checksums for the randomly-generated test cases were calculated
> using a reference implementation [1] and this test compares them against
> the values yielded by the kernel's implementation.

I'd just use a naïve implementation - doesn't really matter
if it is a bit slow.

Slow is relative - this code only takes 35ms to crc-64 over 5MB of data.

{
    volatile const uint32_t *r = (const void *)buf;
    for (crc = 0; r < (const uint32_t *)buf_end; r++) {
        uint64_t val = le32toh(*r);
        crc ^= bswap64(val);
        for (i = 0; i < 32; i++) {
            if (crc & (1ull << 63))
                crc = (crc << 1) ^ 0x42f0e1eba9ea3693ull;
            else
                crc = crc << 1;
        }
    }
}

	David

-
Registered Address Lakeside, Bramley Road, Mount Farm, Milton Keynes, MK1 1PT, UK
Registration No: 1397386 (Wales)

Hi David,

On 9/26/24 13:21, David Laight wrote:
> ...
>> The checksums for the randomly-generated test cases were calculated
>> using a reference implementation [1] and this test compares them against
>> the values yielded by the kernel's implementation.
> 
> I'd just use a naïve implementation - doesn't really matter
> if it is a bit slow.

Thanks for the feedback. I agree that it makes more sense to use a naive 
implementation to validate the results from the kernel's crc16 instead 
of having a table of pre-computed results. I will include in v2 a 
bog-standard implementation of crc16 similar to yours (using a loop 
instead of a lookup table) to validate the results.

Thanks,
Vinicius

> 
> Slow is relative - this code only takes 35ms to crc-64 over 5MB of data.
> 
> {
>      volatile const uint32_t *r = (const void *)buf;
>      for (crc = 0; r < (const uint32_t *)buf_end; r++) {
>          uint64_t val = le32toh(*r);
>          crc ^= bswap64(val);
>          for (i = 0; i < 32; i++) {
>              if (crc & (1ull << 63))
>                  crc = (crc << 1) ^ 0x42f0e1eba9ea3693ull;
>              else
>                  crc = crc << 1;
>          }
>      }
> }
> 
> 	David
> 
> -
> Registered Address Lakeside, Bramley Road, Mount Farm, Milton Keynes, MK1 1PT, UK
> Registration No: 1397386 (Wales)