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/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
rand32(void)46 static u32 rand32(void)
47 {
48 return prandom_u32_state(&rng);
49 }
50
rand64(void)51 static u64 rand64(void)
52 {
53 u32 n = rand32();
54
55 return ((u64)n << 32) | rand32();
56 }
57
crc_mask(const struct crc_variant * v)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 */
crc_ref(const struct crc_variant * v,u64 crc,const u8 * p,size_t len)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
crc_suite_init(struct kunit_suite * suite)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
crc_suite_exit(struct kunit_suite * suite)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. */
generate_random_initial_crc(const struct crc_variant * v)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. */
generate_random_length(size_t max_length)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. */
crc_main_test(struct kunit * test,const struct crc_variant * v)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)). */
crc_combine_test(struct kunit * test,const struct crc_variant * v)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
crc_test(struct kunit * test,const struct crc_variant * v)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
crc_benchmark(struct kunit * test,u64 (* crc_func)(u64 crc,const u8 * p,size_t len))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
crc16_wrapper(u64 crc,const u8 * p,size_t len)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
crc16_test(struct kunit * test)268 static void crc16_test(struct kunit *test)
269 {
270 crc_test(test, &crc_variant_crc16);
271 }
272
crc16_benchmark(struct kunit * test)273 static void crc16_benchmark(struct kunit *test)
274 {
275 crc_benchmark(test, crc16_wrapper);
276 }
277
278 /* crc_t10dif */
279
crc_t10dif_wrapper(u64 crc,const u8 * p,size_t len)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
crc_t10dif_test(struct kunit * test)292 static void crc_t10dif_test(struct kunit *test)
293 {
294 crc_test(test, &crc_variant_crc_t10dif);
295 }
296
crc_t10dif_benchmark(struct kunit * test)297 static void crc_t10dif_benchmark(struct kunit *test)
298 {
299 crc_benchmark(test, crc_t10dif_wrapper);
300 }
301
302 /* crc32_le */
303
crc32_le_wrapper(u64 crc,const u8 * p,size_t len)304 static u64 crc32_le_wrapper(u64 crc, const u8 *p, size_t len)
305 {
306 return crc32_le(crc, p, len);
307 }
308
crc32_le_combine_wrapper(u64 crc1,u64 crc2,size_t len2)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
crc32_le_test(struct kunit * test)322 static void crc32_le_test(struct kunit *test)
323 {
324 crc_test(test, &crc_variant_crc32_le);
325 }
326
crc32_le_benchmark(struct kunit * test)327 static void crc32_le_benchmark(struct kunit *test)
328 {
329 crc_benchmark(test, crc32_le_wrapper);
330 }
331
332 /* crc32_be */
333
crc32_be_wrapper(u64 crc,const u8 * p,size_t len)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
crc32_be_test(struct kunit * test)346 static void crc32_be_test(struct kunit *test)
347 {
348 crc_test(test, &crc_variant_crc32_be);
349 }
350
crc32_be_benchmark(struct kunit * test)351 static void crc32_be_benchmark(struct kunit *test)
352 {
353 crc_benchmark(test, crc32_be_wrapper);
354 }
355
356 /* crc32c */
357
crc32c_wrapper(u64 crc,const u8 * p,size_t len)358 static u64 crc32c_wrapper(u64 crc, const u8 *p, size_t len)
359 {
360 return crc32c(crc, p, len);
361 }
362
crc32c_combine_wrapper(u64 crc1,u64 crc2,size_t len2)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
crc32c_test(struct kunit * test)376 static void crc32c_test(struct kunit *test)
377 {
378 crc_test(test, &crc_variant_crc32c);
379 }
380
crc32c_benchmark(struct kunit * test)381 static void crc32c_benchmark(struct kunit *test)
382 {
383 crc_benchmark(test, crc32c_wrapper);
384 }
385
386 /* crc64_be */
387
crc64_be_wrapper(u64 crc,const u8 * p,size_t len)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
crc64_be_test(struct kunit * test)400 static void crc64_be_test(struct kunit *test)
401 {
402 crc_test(test, &crc_variant_crc64_be);
403 }
404
crc64_be_benchmark(struct kunit * test)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