lib/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 <[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");