crc_kunit.c

  1// SPDX-License-Identifier: GPL-2.0-or-later
  2/*
  3 * Unit tests and benchmarks for the CRC library functions
  4 *
  5 * Copyright 2024 Google LLC
  6 *
  7 * Author: Eric Biggers <ebiggers@google.com>
  8 */
  9#include <kunit/run-in-irq-context.h>
 10#include <kunit/test.h>
 11#include <linux/crc7.h>
 12#include <linux/crc16.h>
 13#include <linux/crc-t10dif.h>
 14#include <linux/crc32.h>
 15#include <linux/crc32c.h>
 16#include <linux/crc64.h>
 17#include <linux/prandom.h>
 18#include <linux/vmalloc.h>
 19
 20#define CRC_KUNIT_SEED			42
 21#define CRC_KUNIT_MAX_LEN		16384
 22#define CRC_KUNIT_NUM_TEST_ITERS	1000
 23
 24static struct rnd_state rng;
 25static u8 *test_buffer;
 26static size_t test_buflen;
 27
 28/**
 29 * struct crc_variant - describes a CRC variant
 30 * @bits: Number of bits in the CRC, 1 <= @bits <= 64.
 31 * @le: true if it's a "little endian" CRC (reversed mapping between bits and
 32 *	polynomial coefficients in each byte), false if it's a "big endian" CRC
 33 *	(natural mapping between bits and polynomial coefficients in each byte)
 34 * @poly: The generator polynomial with the highest-order term omitted.
 35 *	  Bit-reversed if @le is true.
 36 * @func: The function to compute a CRC.  The type signature uses u64 so that it
 37 *	  can fit any CRC up to CRC-64.  The CRC is passed in, and is expected
 38 *	  to be returned in, the least significant bits of the u64.  The
 39 *	  function is expected to *not* invert the CRC at the beginning and end.
 40 */
 41struct crc_variant {
 42	int bits;
 43	bool le;
 44	u64 poly;
 45	u64 (*func)(u64 crc, const u8 *p, size_t len);
 46};
 47
 48static u32 rand32(void)
 49{
 50	return prandom_u32_state(&rng);
 51}
 52
 53static u64 rand64(void)
 54{
 55	u32 n = rand32();
 56
 57	return ((u64)n << 32) | rand32();
 58}
 59
 60static u64 crc_mask(const struct crc_variant *v)
 61{
 62	return (u64)-1 >> (64 - v->bits);
 63}
 64
 65/* Reference implementation of any CRC variant */
 66static u64 crc_ref(const struct crc_variant *v,
 67		   u64 crc, const u8 *p, size_t len)
 68{
 69	size_t i, j;
 70
 71	for (i = 0; i < len; i++) {
 72		for (j = 0; j < 8; j++) {
 73			if (v->le) {
 74				crc ^= (p[i] >> j) & 1;
 75				crc = (crc >> 1) ^ ((crc & 1) ? v->poly : 0);
 76			} else {
 77				crc ^= (u64)((p[i] >> (7 - j)) & 1) <<
 78				       (v->bits - 1);
 79				if (crc & (1ULL << (v->bits - 1)))
 80					crc = ((crc << 1) ^ v->poly) &
 81					      crc_mask(v);
 82				else
 83					crc <<= 1;
 84			}
 85		}
 86	}
 87	return crc;
 88}
 89
 90static int crc_suite_init(struct kunit_suite *suite)
 91{
 92	/*
 93	 * Allocate the test buffer using vmalloc() with a page-aligned length
 94	 * so that it is immediately followed by a guard page.  This allows
 95	 * buffer overreads to be detected, even in assembly code.
 96	 */
 97	test_buflen = round_up(CRC_KUNIT_MAX_LEN, PAGE_SIZE);
 98	test_buffer = vmalloc(test_buflen);
 99	if (!test_buffer)
100		return -ENOMEM;
101
102	prandom_seed_state(&rng, CRC_KUNIT_SEED);
103	prandom_bytes_state(&rng, test_buffer, test_buflen);
104	return 0;
105}
106
107static void crc_suite_exit(struct kunit_suite *suite)
108{
109	vfree(test_buffer);
110	test_buffer = NULL;
111}
112
113/* Generate a random initial CRC. */
114static u64 generate_random_initial_crc(const struct crc_variant *v)
115{
116	switch (rand32() % 4) {
117	case 0:
118		return 0;
119	case 1:
120		return crc_mask(v); /* All 1 bits */
121	default:
122		return rand64() & crc_mask(v);
123	}
124}
125
126/* Generate a random length, preferring small lengths. */
127static size_t generate_random_length(size_t max_length)
128{
129	size_t len;
130
131	switch (rand32() % 3) {
132	case 0:
133		len = rand32() % 128;
134		break;
135	case 1:
136		len = rand32() % 3072;
137		break;
138	default:
139		len = rand32();
140		break;
141	}
142	return len % (max_length + 1);
143}
144
145#define IRQ_TEST_DATA_LEN 512
146#define IRQ_TEST_NUM_BUFFERS 3 /* matches max concurrency level */
147
148struct crc_irq_test_state {
149	const struct crc_variant *v;
150	u64 initial_crc;
151	u64 expected_crcs[IRQ_TEST_NUM_BUFFERS];
152	atomic_t seqno;
153};
154
155/*
156 * Compute the CRC of one of the test messages and verify that it matches the
157 * expected CRC from @state->expected_crcs.  To increase the chance of detecting
158 * problems, cycle through multiple messages.
159 */
160static bool crc_irq_test_func(void *state_)
161{
162	struct crc_irq_test_state *state = state_;
163	const struct crc_variant *v = state->v;
164	u32 i = (u32)atomic_inc_return(&state->seqno) % IRQ_TEST_NUM_BUFFERS;
165	u64 actual_crc = v->func(state->initial_crc,
166				 &test_buffer[i * IRQ_TEST_DATA_LEN],
167				 IRQ_TEST_DATA_LEN);
168
169	return actual_crc == state->expected_crcs[i];
170}
171
172/*
173 * Test that if CRCs are computed in task, softirq, and hardirq context
174 * concurrently, then all results are as expected.
175 */
176static void crc_interrupt_context_test(struct kunit *test,
177				       const struct crc_variant *v)
178{
179	struct crc_irq_test_state state = {
180		.v = v,
181		.initial_crc = generate_random_initial_crc(v),
182	};
183
184	for (int i = 0; i < IRQ_TEST_NUM_BUFFERS; i++) {
185		state.expected_crcs[i] = crc_ref(
186			v, state.initial_crc,
187			&test_buffer[i * IRQ_TEST_DATA_LEN], IRQ_TEST_DATA_LEN);
188	}
189
190	kunit_run_irq_test(test, crc_irq_test_func, 100000, &state);
191}
192
193/* Test that v->func gives the same CRCs as a reference implementation. */
194static void crc_test(struct kunit *test, const struct crc_variant *v)
195{
196	size_t i;
197
198	for (i = 0; i < CRC_KUNIT_NUM_TEST_ITERS; i++) {
199		u64 init_crc, expected_crc, actual_crc;
200		size_t len, offset;
201
202		init_crc = generate_random_initial_crc(v);
203		len = generate_random_length(CRC_KUNIT_MAX_LEN);
204
205		/* Generate a random offset. */
206		if (rand32() % 2 == 0) {
207			/* Use a random alignment mod 64 */
208			offset = rand32() % 64;
209			offset = min(offset, CRC_KUNIT_MAX_LEN - len);
210		} else {
211			/* Go up to the guard page, to catch buffer overreads */
212			offset = test_buflen - len;
213		}
214
215		if (rand32() % 8 == 0)
216			/* Refresh the data occasionally. */
217			prandom_bytes_state(&rng, &test_buffer[offset], len);
218
219		/*
220		 * Compute the CRC, and verify that it equals the CRC computed
221		 * by a simple bit-at-a-time reference implementation.
222		 */
223		expected_crc = crc_ref(v, init_crc, &test_buffer[offset], len);
224		actual_crc = v->func(init_crc, &test_buffer[offset], len);
225		KUNIT_EXPECT_EQ_MSG(test, expected_crc, actual_crc,
226				    "Wrong result with len=%zu offset=%zu",
227				    len, offset);
228	}
229
230	crc_interrupt_context_test(test, v);
231}
232
233static __always_inline void
234crc_benchmark(struct kunit *test,
235	      u64 (*crc_func)(u64 crc, const u8 *p, size_t len))
236{
237	static const size_t lens_to_test[] = {
238		1, 16, 64, 127, 128, 200, 256, 511, 512, 1024, 3173, 4096, 16384,
239	};
240	size_t len, i, j, num_iters;
241	/*
242	 * The CRC value that this function computes in a series of calls to
243	 * crc_func is never actually used, so use volatile to ensure that the
244	 * computations are done as intended and don't all get optimized out.
245	 */
246	volatile u64 crc = 0;
247	u64 t;
248
249	if (!IS_ENABLED(CONFIG_CRC_BENCHMARK))
250		kunit_skip(test, "not enabled");
251
252	/* warm-up */
253	for (i = 0; i < 10000000; i += CRC_KUNIT_MAX_LEN)
254		crc = crc_func(crc, test_buffer, CRC_KUNIT_MAX_LEN);
255
256	for (i = 0; i < ARRAY_SIZE(lens_to_test); i++) {
257		len = lens_to_test[i];
258		KUNIT_ASSERT_LE(test, len, CRC_KUNIT_MAX_LEN);
259		num_iters = 10000000 / (len + 128);
260		preempt_disable();
261		t = ktime_get_ns();
262		for (j = 0; j < num_iters; j++)
263			crc = crc_func(crc, test_buffer, len);
264		t = ktime_get_ns() - t;
265		preempt_enable();
266		kunit_info(test, "len=%zu: %llu MB/s\n",
267			   len, div64_u64((u64)len * num_iters * 1000, t));
268	}
269}
270
271/* crc7_be */
272
273static u64 crc7_be_wrapper(u64 crc, const u8 *p, size_t len)
274{
275	/*
276	 * crc7_be() left-aligns the 7-bit CRC in a u8, whereas the test wants a
277	 * right-aligned CRC (in a u64).  Convert between the conventions.
278	 */
279	return crc7_be(crc << 1, p, len) >> 1;
280}
281
282static const struct crc_variant crc_variant_crc7_be = {
283	.bits = 7,
284	.poly = 0x9,
285	.func = crc7_be_wrapper,
286};
287
288static void crc7_be_test(struct kunit *test)
289{
290	crc_test(test, &crc_variant_crc7_be);
291}
292
293static void crc7_be_benchmark(struct kunit *test)
294{
295	crc_benchmark(test, crc7_be_wrapper);
296}
297
298/* crc16 */
299
300static u64 crc16_wrapper(u64 crc, const u8 *p, size_t len)
301{
302	return crc16(crc, p, len);
303}
304
305static const struct crc_variant crc_variant_crc16 = {
306	.bits = 16,
307	.le = true,
308	.poly = 0xa001,
309	.func = crc16_wrapper,
310};
311
312static void crc16_test(struct kunit *test)
313{
314	crc_test(test, &crc_variant_crc16);
315}
316
317static void crc16_benchmark(struct kunit *test)
318{
319	crc_benchmark(test, crc16_wrapper);
320}
321
322/* crc_t10dif */
323
324static u64 crc_t10dif_wrapper(u64 crc, const u8 *p, size_t len)
325{
326	return crc_t10dif_update(crc, p, len);
327}
328
329static const struct crc_variant crc_variant_crc_t10dif = {
330	.bits = 16,
331	.le = false,
332	.poly = 0x8bb7,
333	.func = crc_t10dif_wrapper,
334};
335
336static void crc_t10dif_test(struct kunit *test)
337{
338	crc_test(test, &crc_variant_crc_t10dif);
339}
340
341static void crc_t10dif_benchmark(struct kunit *test)
342{
343	crc_benchmark(test, crc_t10dif_wrapper);
344}
345
346/* crc32_le */
347
348static u64 crc32_le_wrapper(u64 crc, const u8 *p, size_t len)
349{
350	return crc32_le(crc, p, len);
351}
352
353static const struct crc_variant crc_variant_crc32_le = {
354	.bits = 32,
355	.le = true,
356	.poly = 0xedb88320,
357	.func = crc32_le_wrapper,
358};
359
360static void crc32_le_test(struct kunit *test)
361{
362	crc_test(test, &crc_variant_crc32_le);
363}
364
365static void crc32_le_benchmark(struct kunit *test)
366{
367	crc_benchmark(test, crc32_le_wrapper);
368}
369
370/* crc32_be */
371
372static u64 crc32_be_wrapper(u64 crc, const u8 *p, size_t len)
373{
374	return crc32_be(crc, p, len);
375}
376
377static const struct crc_variant crc_variant_crc32_be = {
378	.bits = 32,
379	.le = false,
380	.poly = 0x04c11db7,
381	.func = crc32_be_wrapper,
382};
383
384static void crc32_be_test(struct kunit *test)
385{
386	crc_test(test, &crc_variant_crc32_be);
387}
388
389static void crc32_be_benchmark(struct kunit *test)
390{
391	crc_benchmark(test, crc32_be_wrapper);
392}
393
394/* crc32c */
395
396static u64 crc32c_wrapper(u64 crc, const u8 *p, size_t len)
397{
398	return crc32c(crc, p, len);
399}
400
401static const struct crc_variant crc_variant_crc32c = {
402	.bits = 32,
403	.le = true,
404	.poly = 0x82f63b78,
405	.func = crc32c_wrapper,
406};
407
408static void crc32c_test(struct kunit *test)
409{
410	crc_test(test, &crc_variant_crc32c);
411}
412
413static void crc32c_benchmark(struct kunit *test)
414{
415	crc_benchmark(test, crc32c_wrapper);
416}
417
418/* crc64_be */
419
420static u64 crc64_be_wrapper(u64 crc, const u8 *p, size_t len)
421{
422	return crc64_be(crc, p, len);
423}
424
425static const struct crc_variant crc_variant_crc64_be = {
426	.bits = 64,
427	.le = false,
428	.poly = 0x42f0e1eba9ea3693,
429	.func = crc64_be_wrapper,
430};
431
432static void crc64_be_test(struct kunit *test)
433{
434	crc_test(test, &crc_variant_crc64_be);
435}
436
437static void crc64_be_benchmark(struct kunit *test)
438{
439	crc_benchmark(test, crc64_be_wrapper);
440}
441
442/* crc64_nvme */
443
444static u64 crc64_nvme_wrapper(u64 crc, const u8 *p, size_t len)
445{
446	/* The inversions that crc64_nvme() does have to be undone here. */
447	return ~crc64_nvme(~crc, p, len);
448}
449
450static const struct crc_variant crc_variant_crc64_nvme = {
451	.bits = 64,
452	.le = true,
453	.poly = 0x9a6c9329ac4bc9b5,
454	.func = crc64_nvme_wrapper,
455};
456
457static void crc64_nvme_test(struct kunit *test)
458{
459	crc_test(test, &crc_variant_crc64_nvme);
460}
461
462static void crc64_nvme_benchmark(struct kunit *test)
463{
464	crc_benchmark(test, crc64_nvme_wrapper);
465}
466
467static struct kunit_case crc_test_cases[] = {
468	KUNIT_CASE(crc7_be_test),
469	KUNIT_CASE(crc7_be_benchmark),
470	KUNIT_CASE(crc16_test),
471	KUNIT_CASE(crc16_benchmark),
472	KUNIT_CASE(crc_t10dif_test),
473	KUNIT_CASE(crc_t10dif_benchmark),
474	KUNIT_CASE(crc32_le_test),
475	KUNIT_CASE(crc32_le_benchmark),
476	KUNIT_CASE(crc32_be_test),
477	KUNIT_CASE(crc32_be_benchmark),
478	KUNIT_CASE(crc32c_test),
479	KUNIT_CASE(crc32c_benchmark),
480	KUNIT_CASE(crc64_be_test),
481	KUNIT_CASE(crc64_be_benchmark),
482	KUNIT_CASE(crc64_nvme_test),
483	KUNIT_CASE(crc64_nvme_benchmark),
484	{},
485};
486
487static struct kunit_suite crc_test_suite = {
488	.name = "crc",
489	.test_cases = crc_test_cases,
490	.suite_init = crc_suite_init,
491	.suite_exit = crc_suite_exit,
492};
493kunit_test_suite(crc_test_suite);
494
495MODULE_DESCRIPTION("Unit tests and benchmarks for the CRC library functions");
496MODULE_LICENSE("GPL");