xref: /linux-6.15/lib/tests/crc_kunit.c (revision 7a79e7da) 
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 <[email protected]>
8  */
9 #include <kunit/test.h>
10 #include <linux/crc16.h>
11 #include <linux/crc-t10dif.h>
12 #include <linux/crc32.h>
13 #include <linux/crc32c.h>
14 #include <linux/crc64.h>
15 #include <linux/prandom.h>
16 #include <linux/vmalloc.h>
17 
18 #define CRC_KUNIT_SEED			42
19 #define CRC_KUNIT_MAX_LEN		16384
20 #define CRC_KUNIT_NUM_TEST_ITERS	1000
21 
22 static struct rnd_state rng;
23 static u8 *test_buffer;
24 static size_t test_buflen;
25 
26 /**
27  * struct crc_variant - describes a CRC variant
28  * @bits: Number of bits in the CRC, 1 <= @bits <= 64.
29  * @le: true if it's a "little endian" CRC (reversed mapping between bits and
30  *	polynomial coefficients in each byte), false if it's a "big endian" CRC
31  *	(natural mapping between bits and polynomial coefficients in each byte)
32  * @poly: The generator polynomial with the highest-order term omitted.
33  *	  Bit-reversed if @le is true.
34  * @func: The function to compute a CRC.  The type signature uses u64 so that it
35  *	  can fit any CRC up to CRC-64.
36  * @combine_func: Optional function to combine two CRCs.
37  */
38 struct crc_variant {
39 	int bits;
40 	bool le;
41 	u64 poly;
42 	u64 (*func)(u64 crc, const u8 *p, size_t len);
43 	u64 (*combine_func)(u64 crc1, u64 crc2, size_t len2);
44 };
45 
46 static u32 rand32(void)
47 {
48 	return prandom_u32_state(&rng);
49 }
50 
51 static u64 rand64(void)
52 {
53 	u32 n = rand32();
54 
55 	return ((u64)n << 32) | rand32();
56 }
57 
58 static u64 crc_mask(const struct crc_variant *v)
59 {
60 	return (u64)-1 >> (64 - v->bits);
61 }
62 
63 /* Reference implementation of any CRC variant */
64 static u64 crc_ref(const struct crc_variant *v,
65 		   u64 crc, const u8 *p, size_t len)
66 {
67 	size_t i, j;
68 
69 	for (i = 0; i < len; i++) {
70 		for (j = 0; j < 8; j++) {
71 			if (v->le) {
72 				crc ^= (p[i] >> j) & 1;
73 				crc = (crc >> 1) ^ ((crc & 1) ? v->poly : 0);
74 			} else {
75 				crc ^= (u64)((p[i] >> (7 - j)) & 1) <<
76 				       (v->bits - 1);
77 				if (crc & (1ULL << (v->bits - 1)))
78 					crc = ((crc << 1) ^ v->poly) &
79 					      crc_mask(v);
80 				else
81 					crc <<= 1;
82 			}
83 		}
84 	}
85 	return crc;
86 }
87 
88 static int crc_suite_init(struct kunit_suite *suite)
89 {
90 	/*
91 	 * Allocate the test buffer using vmalloc() with a page-aligned length
92 	 * so that it is immediately followed by a guard page.  This allows
93 	 * buffer overreads to be detected, even in assembly code.
94 	 */
95 	test_buflen = round_up(CRC_KUNIT_MAX_LEN, PAGE_SIZE);
96 	test_buffer = vmalloc(test_buflen);
97 	if (!test_buffer)
98 		return -ENOMEM;
99 
100 	prandom_seed_state(&rng, CRC_KUNIT_SEED);
101 	prandom_bytes_state(&rng, test_buffer, test_buflen);
102 	return 0;
103 }
104 
105 static void crc_suite_exit(struct kunit_suite *suite)
106 {
107 	vfree(test_buffer);
108 	test_buffer = NULL;
109 }
110 
111 /* Generate a random initial CRC. */
112 static u64 generate_random_initial_crc(const struct crc_variant *v)
113 {
114 	switch (rand32() % 4) {
115 	case 0:
116 		return 0;
117 	case 1:
118 		return crc_mask(v); /* All 1 bits */
119 	default:
120 		return rand64() & crc_mask(v);
121 	}
122 }
123 
124 /* Generate a random length, preferring small lengths. */
125 static size_t generate_random_length(size_t max_length)
126 {
127 	size_t len;
128 
129 	switch (rand32() % 3) {
130 	case 0:
131 		len = rand32() % 128;
132 		break;
133 	case 1:
134 		len = rand32() % 3072;
135 		break;
136 	default:
137 		len = rand32();
138 		break;
139 	}
140 	return len % (max_length + 1);
141 }
142 
143 /* Test that v->func gives the same CRCs as a reference implementation. */
144 static void crc_main_test(struct kunit *test, const struct crc_variant *v)
145 {
146 	size_t i;
147 
148 	for (i = 0; i < CRC_KUNIT_NUM_TEST_ITERS; i++) {
149 		u64 init_crc, expected_crc, actual_crc;
150 		size_t len, offset;
151 		bool nosimd;
152 
153 		init_crc = generate_random_initial_crc(v);
154 		len = generate_random_length(CRC_KUNIT_MAX_LEN);
155 
156 		/* Generate a random offset. */
157 		if (rand32() % 2 == 0) {
158 			/* Use a random alignment mod 64 */
159 			offset = rand32() % 64;
160 			offset = min(offset, CRC_KUNIT_MAX_LEN - len);
161 		} else {
162 			/* Go up to the guard page, to catch buffer overreads */
163 			offset = test_buflen - len;
164 		}
165 
166 		if (rand32() % 8 == 0)
167 			/* Refresh the data occasionally. */
168 			prandom_bytes_state(&rng, &test_buffer[offset], len);
169 
170 		nosimd = rand32() % 8 == 0;
171 
172 		/*
173 		 * Compute the CRC, and verify that it equals the CRC computed
174 		 * by a simple bit-at-a-time reference implementation.
175 		 */
176 		expected_crc = crc_ref(v, init_crc, &test_buffer[offset], len);
177 		if (nosimd)
178 			local_irq_disable();
179 		actual_crc = v->func(init_crc, &test_buffer[offset], len);
180 		if (nosimd)
181 			local_irq_enable();
182 		KUNIT_EXPECT_EQ_MSG(test, expected_crc, actual_crc,
183 				    "Wrong result with len=%zu offset=%zu nosimd=%d",
184 				    len, offset, nosimd);
185 	}
186 }
187 
188 /* Test that CRC(concat(A, B)) == combine_CRCs(CRC(A), CRC(B), len(B)). */
189 static void crc_combine_test(struct kunit *test, const struct crc_variant *v)
190 {
191 	int i;
192 
193 	for (i = 0; i < 100; i++) {
194 		u64 init_crc = generate_random_initial_crc(v);
195 		size_t len1 = generate_random_length(CRC_KUNIT_MAX_LEN);
196 		size_t len2 = generate_random_length(CRC_KUNIT_MAX_LEN - len1);
197 		u64 crc1, crc2, expected_crc, actual_crc;
198 
199 		prandom_bytes_state(&rng, test_buffer, len1 + len2);
200 		crc1 = v->func(init_crc, test_buffer, len1);
201 		crc2 = v->func(0, &test_buffer[len1], len2);
202 		expected_crc = v->func(init_crc, test_buffer, len1 + len2);
203 		actual_crc = v->combine_func(crc1, crc2, len2);
204 		KUNIT_EXPECT_EQ_MSG(test, expected_crc, actual_crc,
205 				    "CRC combination gave wrong result with len1=%zu len2=%zu\n",
206 				    len1, len2);
207 	}
208 }
209 
210 static void crc_test(struct kunit *test, const struct crc_variant *v)
211 {
212 	crc_main_test(test, v);
213 	if (v->combine_func)
214 		crc_combine_test(test, v);
215 }
216 
217 static __always_inline void
218 crc_benchmark(struct kunit *test,
219 	      u64 (*crc_func)(u64 crc, const u8 *p, size_t len))
220 {
221 	static const size_t lens_to_test[] = {
222 		1, 16, 64, 127, 128, 200, 256, 511, 512, 1024, 3173, 4096, 16384,
223 	};
224 	size_t len, i, j, num_iters;
225 	/*
226 	 * Some of the CRC library functions are marked as __pure, so use
227 	 * volatile to ensure that all calls are really made as intended.
228 	 */
229 	volatile u64 crc = 0;
230 	u64 t;
231 
232 	if (!IS_ENABLED(CONFIG_CRC_BENCHMARK))
233 		kunit_skip(test, "not enabled");
234 
235 	/* warm-up */
236 	for (i = 0; i < 10000000; i += CRC_KUNIT_MAX_LEN)
237 		crc = crc_func(crc, test_buffer, CRC_KUNIT_MAX_LEN);
238 
239 	for (i = 0; i < ARRAY_SIZE(lens_to_test); i++) {
240 		len = lens_to_test[i];
241 		KUNIT_ASSERT_LE(test, len, CRC_KUNIT_MAX_LEN);
242 		num_iters = 10000000 / (len + 128);
243 		preempt_disable();
244 		t = ktime_get_ns();
245 		for (j = 0; j < num_iters; j++)
246 			crc = crc_func(crc, test_buffer, len);
247 		t = ktime_get_ns() - t;
248 		preempt_enable();
249 		kunit_info(test, "len=%zu: %llu MB/s\n",
250 			   len, div64_u64((u64)len * num_iters * 1000, t));
251 	}
252 }
253 
254 /* crc16 */
255 
256 static u64 crc16_wrapper(u64 crc, const u8 *p, size_t len)
257 {
258 	return crc16(crc, p, len);
259 }
260 
261 static const struct crc_variant crc_variant_crc16 = {
262 	.bits = 16,
263 	.le = true,
264 	.poly = 0xa001,
265 	.func = crc16_wrapper,
266 };
267 
268 static void crc16_test(struct kunit *test)
269 {
270 	crc_test(test, &crc_variant_crc16);
271 }
272 
273 static void crc16_benchmark(struct kunit *test)
274 {
275 	crc_benchmark(test, crc16_wrapper);
276 }
277 
278 /* crc_t10dif */
279 
280 static u64 crc_t10dif_wrapper(u64 crc, const u8 *p, size_t len)
281 {
282 	return crc_t10dif_update(crc, p, len);
283 }
284 
285 static const struct crc_variant crc_variant_crc_t10dif = {
286 	.bits = 16,
287 	.le = false,
288 	.poly = 0x8bb7,
289 	.func = crc_t10dif_wrapper,
290 };
291 
292 static void crc_t10dif_test(struct kunit *test)
293 {
294 	crc_test(test, &crc_variant_crc_t10dif);
295 }
296 
297 static void crc_t10dif_benchmark(struct kunit *test)
298 {
299 	crc_benchmark(test, crc_t10dif_wrapper);
300 }
301 
302 /* crc32_le */
303 
304 static u64 crc32_le_wrapper(u64 crc, const u8 *p, size_t len)
305 {
306 	return crc32_le(crc, p, len);
307 }
308 
309 static u64 crc32_le_combine_wrapper(u64 crc1, u64 crc2, size_t len2)
310 {
311 	return crc32_le_combine(crc1, crc2, len2);
312 }
313 
314 static const struct crc_variant crc_variant_crc32_le = {
315 	.bits = 32,
316 	.le = true,
317 	.poly = 0xedb88320,
318 	.func = crc32_le_wrapper,
319 	.combine_func = crc32_le_combine_wrapper,
320 };
321 
322 static void crc32_le_test(struct kunit *test)
323 {
324 	crc_test(test, &crc_variant_crc32_le);
325 }
326 
327 static void crc32_le_benchmark(struct kunit *test)
328 {
329 	crc_benchmark(test, crc32_le_wrapper);
330 }
331 
332 /* crc32_be */
333 
334 static u64 crc32_be_wrapper(u64 crc, const u8 *p, size_t len)
335 {
336 	return crc32_be(crc, p, len);
337 }
338 
339 static const struct crc_variant crc_variant_crc32_be = {
340 	.bits = 32,
341 	.le = false,
342 	.poly = 0x04c11db7,
343 	.func = crc32_be_wrapper,
344 };
345 
346 static void crc32_be_test(struct kunit *test)
347 {
348 	crc_test(test, &crc_variant_crc32_be);
349 }
350 
351 static void crc32_be_benchmark(struct kunit *test)
352 {
353 	crc_benchmark(test, crc32_be_wrapper);
354 }
355 
356 /* crc32c */
357 
358 static u64 crc32c_wrapper(u64 crc, const u8 *p, size_t len)
359 {
360 	return crc32c(crc, p, len);
361 }
362 
363 static u64 crc32c_combine_wrapper(u64 crc1, u64 crc2, size_t len2)
364 {
365 	return __crc32c_le_combine(crc1, crc2, len2);
366 }
367 
368 static const struct crc_variant crc_variant_crc32c = {
369 	.bits = 32,
370 	.le = true,
371 	.poly = 0x82f63b78,
372 	.func = crc32c_wrapper,
373 	.combine_func = crc32c_combine_wrapper,
374 };
375 
376 static void crc32c_test(struct kunit *test)
377 {
378 	crc_test(test, &crc_variant_crc32c);
379 }
380 
381 static void crc32c_benchmark(struct kunit *test)
382 {
383 	crc_benchmark(test, crc32c_wrapper);
384 }
385 
386 /* crc64_be */
387 
388 static u64 crc64_be_wrapper(u64 crc, const u8 *p, size_t len)
389 {
390 	return crc64_be(crc, p, len);
391 }
392 
393 static const struct crc_variant crc_variant_crc64_be = {
394 	.bits = 64,
395 	.le = false,
396 	.poly = 0x42f0e1eba9ea3693,
397 	.func = crc64_be_wrapper,
398 };
399 
400 static void crc64_be_test(struct kunit *test)
401 {
402 	crc_test(test, &crc_variant_crc64_be);
403 }
404 
405 static void crc64_be_benchmark(struct kunit *test)
406 {
407 	crc_benchmark(test, crc64_be_wrapper);
408 }
409 
410 static struct kunit_case crc_test_cases[] = {
411 	KUNIT_CASE(crc16_test),
412 	KUNIT_CASE(crc16_benchmark),
413 	KUNIT_CASE(crc_t10dif_test),
414 	KUNIT_CASE(crc_t10dif_benchmark),
415 	KUNIT_CASE(crc32_le_test),
416 	KUNIT_CASE(crc32_le_benchmark),
417 	KUNIT_CASE(crc32_be_test),
418 	KUNIT_CASE(crc32_be_benchmark),
419 	KUNIT_CASE(crc32c_test),
420 	KUNIT_CASE(crc32c_benchmark),
421 	KUNIT_CASE(crc64_be_test),
422 	KUNIT_CASE(crc64_be_benchmark),
423 	{},
424 };
425 
426 static struct kunit_suite crc_test_suite = {
427 	.name = "crc",
428 	.test_cases = crc_test_cases,
429 	.suite_init = crc_suite_init,
430 	.suite_exit = crc_suite_exit,
431 };
432 kunit_test_suite(crc_test_suite);
433 
434 MODULE_DESCRIPTION("Unit tests and benchmarks for the CRC library functions");
435 MODULE_LICENSE("GPL");
436