Add Kunit tests for the kernel's implementation of the standard CRC-16 algorithm (<linux/crc16.h>). The test data consists of 100 randomly-generated test cases, validated against a naive CRC-16 implementation. This test follows roughly the same logic as lib/crc32test.c, but without the performance measurements. Signed-off-by: Vinicius Peixoto <vpeixoto@xxxxxxxxxx> Co-developed-by: Enzo Bertoloti <ebertoloti@xxxxxxxxxx> Signed-off-by: Enzo Bertoloti <ebertoloti@xxxxxxxxxx> Co-developed-by: Fabricio Gasperin <fgasperin@xxxxxxxxxx> Signed-off-by: Fabricio Gasperin <fgasperin@xxxxxxxxxx> Suggested-by: David Laight <David.Laight@xxxxxxxxxx> --- 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). We would really appreciate any feedback/suggestions on how to improve this. Thanks! :-) Link to v1: https://lore.kernel.org/linux-kselftest/20240922232643.535329-1-vpeixoto@xxxxxxxxxx/ Changes in v2 (suggested by David Laight): - Use the PRNG from include/linux/prandom.h to generate pseudorandom data/test cases instead of having them hardcoded as large static arrays - Add a naive CRC16 implementation used to validate the kernel's implementation (instead of having the test case results be hard-coded) [1] https://lkcamp.dev/about --- lib/Kconfig.debug | 9 +++ lib/Makefile | 1 + lib/crc16_kunit.c | 165 ++++++++++++++++++++++++++++++++++++++++++++++++++++++ 3 files changed, 175 insertions(+) diff --git a/lib/Kconfig.debug b/lib/Kconfig.debug index 7315f643817ae1021f1e4b3dd27b424f49e3f761..f9617e3054948ce43090f524dc67650e9549cee8 100644 --- a/lib/Kconfig.debug +++ b/lib/Kconfig.debug @@ -2850,6 +2850,15 @@ config USERCOPY_KUNIT_TEST on the copy_to/from_user infrastructure, making sure basic user/kernel boundary testing is working. +config CRC16_KUNIT_TEST + tristate "KUnit tests for CRC16" + depends on KUNIT + default KUNIT_ALL_TESTS + select CRC16 + help + Enable this option to run unit tests for the kernel's CRC16 + implementation (<linux/crc16.h>). + config TEST_UDELAY tristate "udelay test driver" help diff --git a/lib/Makefile b/lib/Makefile index 773adf88af41665b2419202e5427e0513c6becae..1faed6414a85fd366b4966a00e8ba231d7546e14 100644 --- a/lib/Makefile +++ b/lib/Makefile @@ -389,6 +389,7 @@ CFLAGS_fortify_kunit.o += $(DISABLE_STRUCTLEAK_PLUGIN) obj-$(CONFIG_FORTIFY_KUNIT_TEST) += fortify_kunit.o obj-$(CONFIG_SIPHASH_KUNIT_TEST) += siphash_kunit.o obj-$(CONFIG_USERCOPY_KUNIT_TEST) += usercopy_kunit.o +obj-$(CONFIG_CRC16_KUNIT_TEST) += crc16_kunit.o obj-$(CONFIG_GENERIC_LIB_DEVMEM_IS_ALLOWED) += devmem_is_allowed.o diff --git a/lib/crc16_kunit.c b/lib/crc16_kunit.c new file mode 100644 index 0000000000000000000000000000000000000000..7a79989815c451a21210d463729436fcc620d6b3 --- /dev/null +++ b/lib/crc16_kunit.c @@ -0,0 +1,165 @@ +// SPDX-License-Identifier: GPL-2.0 +/* + * KUnits tests for CRC16. + * + * Copyright (C) 2024, LKCAMP + * Author: Vinicius Peixoto <vpeixoto@xxxxxxxxxx> + * Author: Fabricio Gasperin <fgasperin@xxxxxxxxxx> + * Author: Enzo Bertoloti <ebertoloti@xxxxxxxxxx> + */ +#include <kunit/test.h> +#include <linux/crc16.h> +#include <linux/prandom.h> + +#define CRC16_KUNIT_DATA_SIZE 4096 +#define CRC16_KUNIT_TEST_SIZE 100 +#define CRC16_KUNIT_SEED 0x12345678 + +/** + * struct crc16_test - CRC16 test data + * @crc: initial input value to CRC16 + * @start: Start index within the data buffer + * @length: Length of the data + * @crc16: Expected CRC16 value for the test + */ +static struct crc16_test { + u16 crc; + u16 start; + u16 length; +} tests[CRC16_KUNIT_TEST_SIZE]; + +u8 data[CRC16_KUNIT_DATA_SIZE]; + + +/* Naive implementation of CRC16 for validation purposes */ +static inline u16 _crc16_naive_byte(u16 crc, u8 data) +{ + u8 i = 0; + + crc ^= (u16) data; + for (i = 0; i < 8; i++) { + if (crc & 0x01) + crc = (crc >> 1) ^ 0xa001; + else + crc = crc >> 1; + } + + return crc; +} + + +static inline u16 _crc16_naive(u16 crc, u8 *buffer, size_t len) +{ + while (len--) + crc = _crc16_naive_byte(crc, *buffer++); + return crc; +} + + +/* Small helper for generating pseudorandom 16-bit data */ +static inline u16 _rand16(void) +{ + static u32 rand = CRC16_KUNIT_SEED; + + rand = next_pseudo_random32(rand); + return rand & 0xFFFF; +} + + +static int crc16_init_test_data(struct kunit_suite *suite) +{ + size_t i; + + /* Fill the data buffer with random bytes */ + for (i = 0; i < CRC16_KUNIT_DATA_SIZE; i++) + data[i] = _rand16() & 0xFF; + + /* Generate random test data while ensuring the random + * start + length values won't overflow the 4096-byte + * buffer (0x7FF * 2 = 0xFFE < 0x1000) + */ + for (size_t i = 0; i < CRC16_KUNIT_TEST_SIZE; i++) { + tests[i].crc = _rand16(); + tests[i].start = _rand16() & 0x7FF; + tests[i].length = _rand16() & 0x7FF; + } + + return 0; +} + +/** + * crc16_test_empty - Test crc16 with empty data + * + * Test crc16 with empty data, the result should be the same as the initial crc + */ +static void crc16_test_empty(struct kunit *test) +{ + u16 crc; + + crc = crc16(0x00, data, 0); + KUNIT_EXPECT_EQ(test, crc, 0); + crc = crc16(0xFF, data, 0); + KUNIT_EXPECT_EQ(test, crc, 0xFF); +} + +/** + * crc16_test_correctness - Test crc16 + * + * Test crc16 against a naive implementation + */ +static void crc16_test_correctness(struct kunit *test) +{ + size_t i; + u16 crc, crc_naive; + + for (i = 0; i < CRC16_KUNIT_TEST_SIZE; i++) { + crc = crc16(tests[i].crc, data + tests[i].start, + tests[i].length); + crc_naive = _crc16_naive(tests[i].crc, data + tests[i].start, + tests[i].length); + KUNIT_EXPECT_EQ(test, crc, crc_naive); + } +} + + +/** + * crc16_test_combine - Test split crc16 calculations + * + * Test crc16 with data split in two parts, the result should be the same as + * crc16 with the data combined + */ +static void crc16_test_combine(struct kunit *test) +{ + size_t i, j; + u16 crc, crc_naive; + + for (i = 0; i < CRC16_KUNIT_TEST_SIZE; i++) { + crc_naive = crc16(tests[i].crc, data + tests[i].start, tests[i].length); + for (j = 0; j < tests[i].length; j++) { + crc = crc16(tests[i].crc, data + tests[i].start, j); + crc = crc16(crc, data + tests[i].start + j, tests[i].length - j); + KUNIT_EXPECT_EQ(test, crc, crc_naive); + } + } +} + + +static struct kunit_case crc16_test_cases[] = { + KUNIT_CASE(crc16_test_empty), + KUNIT_CASE(crc16_test_combine), + KUNIT_CASE(crc16_test_correctness), + {}, +}; + +static struct kunit_suite crc16_test_suite = { + .name = "crc16", + .test_cases = crc16_test_cases, + .suite_init = crc16_init_test_data, +}; +kunit_test_suite(crc16_test_suite); + +MODULE_AUTHOR("Fabricio Gasperin <fgasperin@xxxxxxxxxx>"); +MODULE_AUTHOR("Vinicius Peixoto <vpeixoto@xxxxxxxxxx>"); +MODULE_AUTHOR("Enzo Bertoloti <ebertoloti@xxxxxxxxxx>"); +MODULE_DESCRIPTION("Unit tests for crc16"); +MODULE_LICENSE("GPL"); --- base-commit: 9852d85ec9d492ebef56dc5f229416c925758edc change-id: 20241003-crc16-kunit-127a4dc2b72c Best regards, -- Vinicius Peixoto <vpeixoto@xxxxxxxxxx>
