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