~lkcamp/patches

lib/crc16_kunit.c: add KUnit tests for crc16 v2 PROPOSED

Vinicius Peixoto: 1
 lib/crc16_kunit.c: add KUnit tests for crc16

 3 files changed, 175 insertions(+), 0 deletions(-)
Export patchset (mbox)
How do I use this?

Copy & paste the following snippet into your terminal to import this patchset into git:

curl -s https://lists.sr.ht/~lkcamp/patches/patches/55298/mbox | git am -3
Learn more about email & git

[PATCH v2] lib/crc16_kunit.c: add KUnit tests for crc16 Export this patch

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@lkcamp.dev>
Co-developed-by: Enzo Bertoloti <ebertoloti@lkcamp.dev>
Signed-off-by: Enzo Bertoloti <ebertoloti@lkcamp.dev>
Co-developed-by: Fabricio Gasperin <fgasperin@lkcamp.dev>
Signed-off-by: Fabricio Gasperin <fgasperin@lkcamp.dev>
Suggested-by: David Laight <David.Laight@ACULAB.COM>
---
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@lkcamp.dev/

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@lkcamp.dev>
 * Author: Fabricio Gasperin <fgasperin@lkcamp.dev>
 * Author: Enzo Bertoloti <ebertoloti@lkcamp.dev>
 */
#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@lkcamp.dev>");
MODULE_AUTHOR("Vinicius Peixoto <vpeixoto@lkcamp.dev>");
MODULE_AUTHOR("Enzo Bertoloti <ebertoloti@lkcamp.dev>");
MODULE_DESCRIPTION("Unit tests for crc16");
MODULE_LICENSE("GPL");

---
base-commit: 9852d85ec9d492ebef56dc5f229416c925758edc
change-id: 20241003-crc16-kunit-127a4dc2b72c

Best regards,
-- 
Vinicius Peixoto <vpeixoto@lkcamp.dev>
kernel test robot <lkp@intel.com>
Hi Vinicius,

kernel test robot noticed the following build warnings:

[auto build test WARNING on 9852d85ec9d492ebef56dc5f229416c925758edc]

url:    https://github.com/intel-lab-lkp/linux/commits/Vinicius-Peixoto/lib-crc16_kunit-c-add-KUnit-tests-for-crc16/20241004-050248
base:   9852d85ec9d492ebef56dc5f229416c925758edc
patch link:    https://lore.kernel.org/r/20241003-crc16-kunit-v2-1-5fe74b113e1e%40lkcamp.dev
patch subject: [PATCH v2] lib/crc16_kunit.c: add KUnit tests for crc16
config: parisc-randconfig-r071-20241005 (https://download.01.org/0day-ci/archive/20241005/202410050215.eU9509xy-lkp@intel.com/config)
compiler: hppa-linux-gcc (GCC) 14.1.0
reproduce (this is a W=1 build): (https://download.01.org/0day-ci/archive/20241005/202410050215.eU9509xy-lkp@intel.com/reproduce)

If you fix the issue in a separate patch/commit (i.e. not just a new version of
the same patch/commit), kindly add following tags
| Reported-by: kernel test robot <lkp@intel.com>
| Closes: https://lore.kernel.org/oe-kbuild-all/202410050215.eU9509xy-lkp@intel.com/

All warnings (new ones prefixed by >>):
kernel test robot <lkp@intel.com>
lib/crc16_kunit.c:96: warning: Function parameter or struct member 'test' not described in 'crc16_test_empty'
   lib/crc16_kunit.c:111: warning: Function parameter or struct member 'test' not described in 'crc16_test_correctness'
   lib/crc16_kunit.c:132: warning: Function parameter or struct member 'test' not described in 'crc16_test_combine'

Kconfig warnings: (for reference only)
   WARNING: unmet direct dependencies detected for GET_FREE_REGION
   Depends on [n]: SPARSEMEM [=n]
   Selected by [m]:
   - RESOURCE_KUNIT_TEST [=m] && RUNTIME_TESTING_MENU [=y] && KUNIT [=m]


vim +29 lib/crc16_kunit.c

    17	
    18	/**
    19	 * struct crc16_test - CRC16 test data
    20	 * @crc: initial input value to CRC16
    21	 * @start: Start index within the data buffer
    22	 * @length: Length of the data
    23	 * @crc16: Expected CRC16 value for the test
    24	 */
    25	static struct crc16_test {
    26		u16 crc;
    27		u16 start;
    28		u16 length;
  > 29	} tests[CRC16_KUNIT_TEST_SIZE];
    30