lib/test_bitmap.c

   1 // SPDX-License-Identifier: GPL-2.0-only
   2 /*
   3  * Test cases for bitmap API.
   4  */
   5
   6 #define pr_fmt(fmt) KBUILD_MODNAME ": " fmt
   7
   8 #include <linux/bitmap.h>
   9 #include <linux/init.h>
  10 #include <linux/kernel.h>
  11 #include <linux/module.h>
  12 #include <linux/printk.h>
  13 #include <linux/slab.h>
  14 #include <linux/string.h>
  15 #include <linux/uaccess.h>
  16
  17 #include "../tools/testing/selftests/kselftest_module.h"
  18
  19 KSTM_MODULE_GLOBALS();
  20
  21 static char pbl_buffer[PAGE_SIZE] __initdata;
  22 static char print_buf[PAGE_SIZE * 2] __initdata;
  23
  24 static const unsigned long exp1[] __initconst = {
  25         BITMAP_FROM_U64(1),
  26         BITMAP_FROM_U64(2),
  27         BITMAP_FROM_U64(0x0000ffff),
  28         BITMAP_FROM_U64(0xffff0000),
  29         BITMAP_FROM_U64(0x55555555),
  30         BITMAP_FROM_U64(0xaaaaaaaa),
  31         BITMAP_FROM_U64(0x11111111),
  32         BITMAP_FROM_U64(0x22222222),
  33         BITMAP_FROM_U64(0xffffffff),
  34         BITMAP_FROM_U64(0xfffffffe),
  35         BITMAP_FROM_U64(0x3333333311111111ULL),
  36         BITMAP_FROM_U64(0xffffffff77777777ULL),
  37         BITMAP_FROM_U64(0),
  38         BITMAP_FROM_U64(0x00008000),
  39         BITMAP_FROM_U64(0x80000000),
  40 };
  41
  42 static const unsigned long exp2[] __initconst = {
  43         BITMAP_FROM_U64(0x3333333311111111ULL),
  44         BITMAP_FROM_U64(0xffffffff77777777ULL),
  45 };
  46
  47 /* Fibonacci sequence */
  48 static const unsigned long exp2_to_exp3_mask[] __initconst = {
  49         BITMAP_FROM_U64(0x008000020020212eULL),
  50 };
  51 /* exp3_0_1 = (exp2[0] & ~exp2_to_exp3_mask) | (exp2[1] & exp2_to_exp3_mask) */
  52 static const unsigned long exp3_0_1[] __initconst = {
  53         BITMAP_FROM_U64(0x33b3333311313137ULL),
  54 };
  55 /* exp3_1_0 = (exp2[1] & ~exp2_to_exp3_mask) | (exp2[0] & exp2_to_exp3_mask) */
  56 static const unsigned long exp3_1_0[] __initconst = {
  57         BITMAP_FROM_U64(0xff7fffff77575751ULL),
  58 };
  59
  60 static bool __init
  61 __check_eq_uint(const char *srcfile, unsigned int line,
  62                 const unsigned int exp_uint, unsigned int x)
  63 {
  64         if (exp_uint != x) {
  65                 pr_err("[%s:%u] expected %u, got %u\n",
  66                         srcfile, line, exp_uint, x);
  67                 return false;
  68         }
  69         return true;
  70 }
  71
  72
  73 static bool __init
  74 __check_eq_bitmap(const char *srcfile, unsigned int line,
  75                   const unsigned long *exp_bmap, const unsigned long *bmap,
  76                   unsigned int nbits)
  77 {
  78         if (!bitmap_equal(exp_bmap, bmap, nbits)) {
  79                 pr_warn("[%s:%u] bitmaps contents differ: expected \"%*pbl\", got \"%*pbl\"\n",
  80                         srcfile, line,
  81                         nbits, exp_bmap, nbits, bmap);
  82                 return false;
  83         }
  84         return true;
  85 }
  86
  87 static bool __init
  88 __check_eq_pbl(const char *srcfile, unsigned int line,
  89                const char *expected_pbl,
  90                const unsigned long *bitmap, unsigned int nbits)
  91 {
  92         snprintf(pbl_buffer, sizeof(pbl_buffer), "%*pbl", nbits, bitmap);
  93         if (strcmp(expected_pbl, pbl_buffer)) {
  94                 pr_warn("[%s:%u] expected \"%s\", got \"%s\"\n",
  95                         srcfile, line,
  96                         expected_pbl, pbl_buffer);
  97                 return false;
  98         }
  99         return true;
 100 }
 101
 102 static bool __init
 103 __check_eq_u32_array(const char *srcfile, unsigned int line,
 104                      const u32 *exp_arr, unsigned int exp_len,
 105                      const u32 *arr, unsigned int len) __used;
 106 static bool __init
 107 __check_eq_u32_array(const char *srcfile, unsigned int line,
 108                      const u32 *exp_arr, unsigned int exp_len,
 109                      const u32 *arr, unsigned int len)
 110 {
 111         if (exp_len != len) {
 112                 pr_warn("[%s:%u] array length differ: expected %u, got %u\n",
 113                         srcfile, line,
 114                         exp_len, len);
 115                 return false;
 116         }
 117
 118         if (memcmp(exp_arr, arr, len*sizeof(*arr))) {
 119                 pr_warn("[%s:%u] array contents differ\n", srcfile, line);
 120                 print_hex_dump(KERN_WARNING, "  exp:  ", DUMP_PREFIX_OFFSET,
 121                                32, 4, exp_arr, exp_len*sizeof(*exp_arr), false);
 122                 print_hex_dump(KERN_WARNING, "  got:  ", DUMP_PREFIX_OFFSET,
 123                                32, 4, arr, len*sizeof(*arr), false);
 124                 return false;
 125         }
 126
 127         return true;
 128 }
 129
 130 static bool __init __check_eq_clump8(const char *srcfile, unsigned int line,
 131                                     const unsigned int offset,
 132                                     const unsigned int size,
 133                                     const unsigned char *const clump_exp,
 134                                     const unsigned long *const clump)
 135 {
 136         unsigned long exp;
 137
 138         if (offset >= size) {
 139                 pr_warn("[%s:%u] bit offset for clump out-of-bounds: expected less than %u, got %u\n",
 140                         srcfile, line, size, offset);
 141                 return false;
 142         }
 143
 144         exp = clump_exp[offset / 8];
 145         if (!exp) {
 146                 pr_warn("[%s:%u] bit offset for zero clump: expected nonzero clump, got bit offset %u with clump value 0",
 147                         srcfile, line, offset);
 148                 return false;
 149         }
 150
 151         if (*clump != exp) {
 152                 pr_warn("[%s:%u] expected clump value of 0x%lX, got clump value of 0x%lX",
 153                         srcfile, line, exp, *clump);
 154                 return false;
 155         }
 156
 157         return true;
 158 }
 159
 160 static bool __init
 161 __check_eq_str(const char *srcfile, unsigned int line,
 162                 const char *exp_str, const char *str,
 163                 unsigned int len)
 164 {
 165         bool eq;
 166
 167         eq = strncmp(exp_str, str, len) == 0;
 168         if (!eq)
 169                 pr_err("[%s:%u] expected %s, got %s\n", srcfile, line, exp_str, str);
 170
 171         return eq;
 172 }
 173
 174 #define __expect_eq(suffix, ...)                                        \
 175         ({                                                              \
 176                 int result = 0;                                         \
 177                 total_tests++;                                          \
 178                 if (!__check_eq_ ## suffix(__FILE__, __LINE__,          \
 179                                            ##__VA_ARGS__)) {            \
 180                         failed_tests++;                                 \
 181                         result = 1;                                     \
 182                 }                                                       \
 183                 result;                                                 \
 184         })
 185
 186 #define expect_eq_uint(...)             __expect_eq(uint, ##__VA_ARGS__)
 187 #define expect_eq_bitmap(...)           __expect_eq(bitmap, ##__VA_ARGS__)
 188 #define expect_eq_pbl(...)              __expect_eq(pbl, ##__VA_ARGS__)
 189 #define expect_eq_u32_array(...)        __expect_eq(u32_array, ##__VA_ARGS__)
 190 #define expect_eq_clump8(...)           __expect_eq(clump8, ##__VA_ARGS__)
 191 #define expect_eq_str(...)              __expect_eq(str, ##__VA_ARGS__)
 192
 193 static void __init test_zero_clear(void)
 194 {
 195         DECLARE_BITMAP(bmap, 1024);
 196
 197         /* Known way to set all bits */
 198         memset(bmap, 0xff, 128);
 199
 200         expect_eq_pbl("0-22", bmap, 23);
 201         expect_eq_pbl("0-1023", bmap, 1024);
 202
 203         /* single-word bitmaps */
 204         bitmap_clear(bmap, 0, 9);
 205         expect_eq_pbl("9-1023", bmap, 1024);
 206
 207         bitmap_zero(bmap, 35);
 208         expect_eq_pbl("64-1023", bmap, 1024);
 209
 210         /* cross boundaries operations */
 211         bitmap_clear(bmap, 79, 19);
 212         expect_eq_pbl("64-78,98-1023", bmap, 1024);
 213
 214         bitmap_zero(bmap, 115);
 215         expect_eq_pbl("128-1023", bmap, 1024);
 216
 217         /* Zeroing entire area */
 218         bitmap_zero(bmap, 1024);
 219         expect_eq_pbl("", bmap, 1024);
 220 }
 221
 222 static void __init test_fill_set(void)
 223 {
 224         DECLARE_BITMAP(bmap, 1024);
 225
 226         /* Known way to clear all bits */
 227         memset(bmap, 0x00, 128);
 228
 229         expect_eq_pbl("", bmap, 23);
 230         expect_eq_pbl("", bmap, 1024);
 231
 232         /* single-word bitmaps */
 233         bitmap_set(bmap, 0, 9);
 234         expect_eq_pbl("0-8", bmap, 1024);
 235
 236         bitmap_fill(bmap, 35);
 237         expect_eq_pbl("0-63", bmap, 1024);
 238
 239         /* cross boundaries operations */
 240         bitmap_set(bmap, 79, 19);
 241         expect_eq_pbl("0-63,79-97", bmap, 1024);
 242
 243         bitmap_fill(bmap, 115);
 244         expect_eq_pbl("0-127", bmap, 1024);
 245
 246         /* Zeroing entire area */
 247         bitmap_fill(bmap, 1024);
 248         expect_eq_pbl("0-1023", bmap, 1024);
 249 }
 250
 251 static void __init test_copy(void)
 252 {
 253         DECLARE_BITMAP(bmap1, 1024);
 254         DECLARE_BITMAP(bmap2, 1024);
 255
 256         bitmap_zero(bmap1, 1024);
 257         bitmap_zero(bmap2, 1024);
 258
 259         /* single-word bitmaps */
 260         bitmap_set(bmap1, 0, 19);
 261         bitmap_copy(bmap2, bmap1, 23);
 262         expect_eq_pbl("0-18", bmap2, 1024);
 263
 264         bitmap_set(bmap2, 0, 23);
 265         bitmap_copy(bmap2, bmap1, 23);
 266         expect_eq_pbl("0-18", bmap2, 1024);
 267
 268         /* multi-word bitmaps */
 269         bitmap_set(bmap1, 0, 109);
 270         bitmap_copy(bmap2, bmap1, 1024);
 271         expect_eq_pbl("0-108", bmap2, 1024);
 272
 273         bitmap_fill(bmap2, 1024);
 274         bitmap_copy(bmap2, bmap1, 1024);
 275         expect_eq_pbl("0-108", bmap2, 1024);
 276
 277         /* the following tests assume a 32- or 64-bit arch (even 128b
 278          * if we care)
 279          */
 280
 281         bitmap_fill(bmap2, 1024);
 282         bitmap_copy(bmap2, bmap1, 109);  /* ... but 0-padded til word length */
 283         expect_eq_pbl("0-108,128-1023", bmap2, 1024);
 284
 285         bitmap_fill(bmap2, 1024);
 286         bitmap_copy(bmap2, bmap1, 97);  /* ... but aligned on word length */
 287         expect_eq_pbl("0-108,128-1023", bmap2, 1024);
 288 }
 289
 290 #define EXP2_IN_BITS    (sizeof(exp2) * 8)
 291
 292 static void __init test_replace(void)
 293 {
 294         unsigned int nbits = 64;
 295         unsigned int nlongs = DIV_ROUND_UP(nbits, BITS_PER_LONG);
 296         DECLARE_BITMAP(bmap, 1024);
 297
 298         BUILD_BUG_ON(EXP2_IN_BITS < nbits * 2);
 299
 300         bitmap_zero(bmap, 1024);
 301         bitmap_replace(bmap, &exp2[0 * nlongs], &exp2[1 * nlongs], exp2_to_exp3_mask, nbits);
 302         expect_eq_bitmap(bmap, exp3_0_1, nbits);
 303
 304         bitmap_zero(bmap, 1024);
 305         bitmap_replace(bmap, &exp2[1 * nlongs], &exp2[0 * nlongs], exp2_to_exp3_mask, nbits);
 306         expect_eq_bitmap(bmap, exp3_1_0, nbits);
 307
 308         bitmap_fill(bmap, 1024);
 309         bitmap_replace(bmap, &exp2[0 * nlongs], &exp2[1 * nlongs], exp2_to_exp3_mask, nbits);
 310         expect_eq_bitmap(bmap, exp3_0_1, nbits);
 311
 312         bitmap_fill(bmap, 1024);
 313         bitmap_replace(bmap, &exp2[1 * nlongs], &exp2[0 * nlongs], exp2_to_exp3_mask, nbits);
 314         expect_eq_bitmap(bmap, exp3_1_0, nbits);
 315 }
 316
 317 #define PARSE_TIME      0x1
 318 #define NO_LEN          0x2
 319
 320 struct test_bitmap_parselist{
 321         const int errno;
 322         const char *in;
 323         const unsigned long *expected;
 324         const int nbits;
 325         const int flags;
 326 };
 327
 328 static const struct test_bitmap_parselist parselist_tests[] __initconst = {
 329 #define step (sizeof(u64) / sizeof(unsigned long))
 330
 331         {0, "0",                        &exp1[0], 8, 0},
 332         {0, "1",                        &exp1[1 * step], 8, 0},
 333         {0, "0-15",                     &exp1[2 * step], 32, 0},
 334         {0, "16-31",                    &exp1[3 * step], 32, 0},
 335         {0, "0-31:1/2",                 &exp1[4 * step], 32, 0},
 336         {0, "1-31:1/2",                 &exp1[5 * step], 32, 0},
 337         {0, "0-31:1/4",                 &exp1[6 * step], 32, 0},
 338         {0, "1-31:1/4",                 &exp1[7 * step], 32, 0},
 339         {0, "0-31:4/4",                 &exp1[8 * step], 32, 0},
 340         {0, "1-31:4/4",                 &exp1[9 * step], 32, 0},
 341         {0, "0-31:1/4,32-63:2/4",       &exp1[10 * step], 64, 0},
 342         {0, "0-31:3/4,32-63:4/4",       &exp1[11 * step], 64, 0},
 343         {0, "  ,,  0-31:3/4  ,, 32-63:4/4  ,,  ",       &exp1[11 * step], 64, 0},
 344
 345         {0, "0-31:1/4,32-63:2/4,64-95:3/4,96-127:4/4",  exp2, 128, 0},
 346
 347         {0, "0-2047:128/256", NULL, 2048, PARSE_TIME},
 348
 349         {0, "",                         &exp1[12 * step], 8, 0},
 350         {0, "\n",                       &exp1[12 * step], 8, 0},
 351         {0, ",,  ,,  , ,  ,",           &exp1[12 * step], 8, 0},
 352         {0, " ,  ,,  , ,   ",           &exp1[12 * step], 8, 0},
 353         {0, " ,  ,,  , ,   \n",         &exp1[12 * step], 8, 0},
 354
 355         {0, "0-0",                      &exp1[0], 32, 0},
 356         {0, "1-1",                      &exp1[1 * step], 32, 0},
 357         {0, "15-15",                    &exp1[13 * step], 32, 0},
 358         {0, "31-31",                    &exp1[14 * step], 32, 0},
 359
 360         {0, "0-0:0/1",                  &exp1[12 * step], 32, 0},
 361         {0, "0-0:1/1",                  &exp1[0], 32, 0},
 362         {0, "0-0:1/31",                 &exp1[0], 32, 0},
 363         {0, "0-0:31/31",                &exp1[0], 32, 0},
 364         {0, "1-1:1/1",                  &exp1[1 * step], 32, 0},
 365         {0, "0-15:16/31",               &exp1[2 * step], 32, 0},
 366         {0, "15-15:1/2",                &exp1[13 * step], 32, 0},
 367         {0, "15-15:31/31",              &exp1[13 * step], 32, 0},
 368         {0, "15-31:1/31",               &exp1[13 * step], 32, 0},
 369         {0, "16-31:16/31",              &exp1[3 * step], 32, 0},
 370         {0, "31-31:31/31",              &exp1[14 * step], 32, 0},
 371
 372         {0, "N-N",                      &exp1[14 * step], 32, 0},
 373         {0, "0-0:1/N",                  &exp1[0], 32, 0},
 374         {0, "0-0:N/N",                  &exp1[0], 32, 0},
 375         {0, "0-15:16/N",                &exp1[2 * step], 32, 0},
 376         {0, "15-15:N/N",                &exp1[13 * step], 32, 0},
 377         {0, "15-N:1/N",                 &exp1[13 * step], 32, 0},
 378         {0, "16-N:16/N",                &exp1[3 * step], 32, 0},
 379         {0, "N-N:N/N",                  &exp1[14 * step], 32, 0},
 380
 381         {0, "0-N:1/3,1-N:1/3,2-N:1/3",          &exp1[8 * step], 32, 0},
 382         {0, "0-31:1/3,1-31:1/3,2-31:1/3",       &exp1[8 * step], 32, 0},
 383         {0, "1-10:8/12,8-31:24/29,0-31:0/3",    &exp1[9 * step], 32, 0},
 384
 385         {0,       "all",                &exp1[8 * step], 32, 0},
 386         {0,       "0, 1, all,  ",       &exp1[8 * step], 32, 0},
 387         {0,       "all:1/2",            &exp1[4 * step], 32, 0},
 388         {0,       "ALL:1/2",            &exp1[4 * step], 32, 0},
 389         {-EINVAL, "al", NULL, 8, 0},
 390         {-EINVAL, "alll", NULL, 8, 0},
 391
 392         {-EINVAL, "-1", NULL, 8, 0},
 393         {-EINVAL, "-0", NULL, 8, 0},
 394         {-EINVAL, "10-1", NULL, 8, 0},
 395         {-ERANGE, "8-8", NULL, 8, 0},
 396         {-ERANGE, "0-31", NULL, 8, 0},
 397         {-EINVAL, "0-31:", NULL, 32, 0},
 398         {-EINVAL, "0-31:0", NULL, 32, 0},
 399         {-EINVAL, "0-31:0/", NULL, 32, 0},
 400         {-EINVAL, "0-31:0/0", NULL, 32, 0},
 401         {-EINVAL, "0-31:1/0", NULL, 32, 0},
 402         {-EINVAL, "0-31:10/1", NULL, 32, 0},
 403         {-EOVERFLOW, "0-98765432123456789:10/1", NULL, 8, 0},
 404
 405         {-EINVAL, "a-31", NULL, 8, 0},
 406         {-EINVAL, "0-a1", NULL, 8, 0},
 407         {-EINVAL, "a-31:10/1", NULL, 8, 0},
 408         {-EINVAL, "0-31:a/1", NULL, 8, 0},
 409         {-EINVAL, "0-\n", NULL, 8, 0},
 410
 411 };
 412
 413 static void __init test_bitmap_parselist(void)
 414 {
 415         int i;
 416         int err;
 417         ktime_t time;
 418         DECLARE_BITMAP(bmap, 2048);
 419
 420         for (i = 0; i < ARRAY_SIZE(parselist_tests); i++) {
 421 #define ptest parselist_tests[i]
 422
 423                 time = ktime_get();
 424                 err = bitmap_parselist(ptest.in, bmap, ptest.nbits);
 425                 time = ktime_get() - time;
 426
 427                 if (err != ptest.errno) {
 428                         pr_err("parselist: %d: input is %s, errno is %d, expected %d\n",
 429                                         i, ptest.in, err, ptest.errno);
 430                         continue;
 431                 }
 432
 433                 if (!err && ptest.expected
 434                          && !__bitmap_equal(bmap, ptest.expected, ptest.nbits)) {
 435                         pr_err("parselist: %d: input is %s, result is 0x%lx, expected 0x%lx\n",
 436                                         i, ptest.in, bmap[0],
 437                                         *ptest.expected);
 438                         continue;
 439                 }
 440
 441                 if (ptest.flags & PARSE_TIME)
 442                         pr_err("parselist: %d: input is '%s' OK, Time: %llu\n",
 443                                         i, ptest.in, time);
 444
 445 #undef ptest
 446         }
 447 }
 448
 449 static void __init test_bitmap_printlist(void)
 450 {
 451         unsigned long *bmap = kmalloc(PAGE_SIZE, GFP_KERNEL);
 452         char *buf = kmalloc(PAGE_SIZE, GFP_KERNEL);
 453         char expected[256];
 454         int ret, slen;
 455         ktime_t time;
 456
 457         if (!buf || !bmap)
 458                 goto out;
 459
 460         memset(bmap, -1, PAGE_SIZE);
 461         slen = snprintf(expected, 256, "0-%ld", PAGE_SIZE * 8 - 1);
 462         if (slen < 0)
 463                 goto out;
 464
 465         time = ktime_get();
 466         ret = bitmap_print_to_pagebuf(true, buf, bmap, PAGE_SIZE * 8);
 467         time = ktime_get() - time;
 468
 469         if (ret != slen + 1) {
 470                 pr_err("bitmap_print_to_pagebuf: result is %d, expected %d\n", ret, slen);
 471                 goto out;
 472         }
 473
 474         if (strncmp(buf, expected, slen)) {
 475                 pr_err("bitmap_print_to_pagebuf: result is %s, expected %s\n", buf, expected);
 476                 goto out;
 477         }
 478
 479         pr_err("bitmap_print_to_pagebuf: input is '%s', Time: %llu\n", buf, time);
 480 out:
 481         kfree(buf);
 482         kfree(bmap);
 483 }
 484
 485 static const unsigned long parse_test[] __initconst = {
 486         BITMAP_FROM_U64(0),
 487         BITMAP_FROM_U64(1),
 488         BITMAP_FROM_U64(0xdeadbeef),
 489         BITMAP_FROM_U64(0x100000000ULL),
 490 };
 491
 492 static const unsigned long parse_test2[] __initconst = {
 493         BITMAP_FROM_U64(0x100000000ULL), BITMAP_FROM_U64(0xdeadbeef),
 494         BITMAP_FROM_U64(0x100000000ULL), BITMAP_FROM_U64(0xbaadf00ddeadbeef),
 495         BITMAP_FROM_U64(0x100000000ULL), BITMAP_FROM_U64(0x0badf00ddeadbeef),
 496 };
 497
 498 static const struct test_bitmap_parselist parse_tests[] __initconst = {
 499         {0, "",                         &parse_test[0 * step], 32, 0},
 500         {0, " ",                        &parse_test[0 * step], 32, 0},
 501         {0, "0",                        &parse_test[0 * step], 32, 0},
 502         {0, "0\n",                      &parse_test[0 * step], 32, 0},
 503         {0, "1",                        &parse_test[1 * step], 32, 0},
 504         {0, "deadbeef",                 &parse_test[2 * step], 32, 0},
 505         {0, "1,0",                      &parse_test[3 * step], 33, 0},
 506         {0, "deadbeef,\n,0,1",          &parse_test[2 * step], 96, 0},
 507
 508         {0, "deadbeef,1,0",             &parse_test2[0 * 2 * step], 96, 0},
 509         {0, "baadf00d,deadbeef,1,0",    &parse_test2[1 * 2 * step], 128, 0},
 510         {0, "badf00d,deadbeef,1,0",     &parse_test2[2 * 2 * step], 124, 0},
 511         {0, "badf00d,deadbeef,1,0",     &parse_test2[2 * 2 * step], 124, NO_LEN},
 512         {0, "  badf00d,deadbeef,1,0  ", &parse_test2[2 * 2 * step], 124, 0},
 513         {0, " , badf00d,deadbeef,1,0 , ",       &parse_test2[2 * 2 * step], 124, 0},
 514         {0, " , badf00d, ,, ,,deadbeef,1,0 , ", &parse_test2[2 * 2 * step], 124, 0},
 515
 516         {-EINVAL,    "goodfood,deadbeef,1,0",   NULL, 128, 0},
 517         {-EOVERFLOW, "3,0",                     NULL, 33, 0},
 518         {-EOVERFLOW, "123badf00d,deadbeef,1,0", NULL, 128, 0},
 519         {-EOVERFLOW, "badf00d,deadbeef,1,0",    NULL, 90, 0},
 520         {-EOVERFLOW, "fbadf00d,deadbeef,1,0",   NULL, 95, 0},
 521         {-EOVERFLOW, "badf00d,deadbeef,1,0",    NULL, 100, 0},
 522 #undef step
 523 };
 524
 525 static void __init test_bitmap_parse(void)
 526 {
 527         int i;
 528         int err;
 529         ktime_t time;
 530         DECLARE_BITMAP(bmap, 2048);
 531
 532         for (i = 0; i < ARRAY_SIZE(parse_tests); i++) {
 533                 struct test_bitmap_parselist test = parse_tests[i];
 534                 size_t len = test.flags & NO_LEN ? UINT_MAX : strlen(test.in);
 535
 536                 time = ktime_get();
 537                 err = bitmap_parse(test.in, len, bmap, test.nbits);
 538                 time = ktime_get() - time;
 539
 540                 if (err != test.errno) {
 541                         pr_err("parse: %d: input is %s, errno is %d, expected %d\n",
 542                                         i, test.in, err, test.errno);
 543                         continue;
 544                 }
 545
 546                 if (!err && test.expected
 547                          && !__bitmap_equal(bmap, test.expected, test.nbits)) {
 548                         pr_err("parse: %d: input is %s, result is 0x%lx, expected 0x%lx\n",
 549                                         i, test.in, bmap[0],
 550                                         *test.expected);
 551                         continue;
 552                 }
 553
 554                 if (test.flags & PARSE_TIME)
 555                         pr_err("parse: %d: input is '%s' OK, Time: %llu\n",
 556                                         i, test.in, time);
 557         }
 558 }
 559
 560 #define EXP1_IN_BITS    (sizeof(exp1) * 8)
 561
 562 static void __init test_bitmap_arr32(void)
 563 {
 564         unsigned int nbits, next_bit;
 565         u32 arr[EXP1_IN_BITS / 32];
 566         DECLARE_BITMAP(bmap2, EXP1_IN_BITS);
 567
 568         memset(arr, 0xa5, sizeof(arr));
 569
 570         for (nbits = 0; nbits < EXP1_IN_BITS; ++nbits) {
 571                 bitmap_to_arr32(arr, exp1, nbits);
 572                 bitmap_from_arr32(bmap2, arr, nbits);
 573                 expect_eq_bitmap(bmap2, exp1, nbits);
 574
 575                 next_bit = find_next_bit(bmap2,
 576                                 round_up(nbits, BITS_PER_LONG), nbits);
 577                 if (next_bit < round_up(nbits, BITS_PER_LONG))
 578                         pr_err("bitmap_copy_arr32(nbits == %d:"
 579                                 " tail is not safely cleared: %d\n",
 580                                 nbits, next_bit);
 581
 582                 if (nbits < EXP1_IN_BITS - 32)
 583                         expect_eq_uint(arr[DIV_ROUND_UP(nbits, 32)],
 584                                                                 0xa5a5a5a5);
 585         }
 586 }
 587
 588 static void noinline __init test_mem_optimisations(void)
 589 {
 590         DECLARE_BITMAP(bmap1, 1024);
 591         DECLARE_BITMAP(bmap2, 1024);
 592         unsigned int start, nbits;
 593
 594         for (start = 0; start < 1024; start += 8) {
 595                 for (nbits = 0; nbits < 1024 - start; nbits += 8) {
 596                         memset(bmap1, 0x5a, sizeof(bmap1));
 597                         memset(bmap2, 0x5a, sizeof(bmap2));
 598
 599                         bitmap_set(bmap1, start, nbits);
 600                         __bitmap_set(bmap2, start, nbits);
 601                         if (!bitmap_equal(bmap1, bmap2, 1024)) {
 602                                 printk("set not equal %d %d\n", start, nbits);
 603                                 failed_tests++;
 604                         }
 605                         if (!__bitmap_equal(bmap1, bmap2, 1024)) {
 606                                 printk("set not __equal %d %d\n", start, nbits);
 607                                 failed_tests++;
 608                         }
 609
 610                         bitmap_clear(bmap1, start, nbits);
 611                         __bitmap_clear(bmap2, start, nbits);
 612                         if (!bitmap_equal(bmap1, bmap2, 1024)) {
 613                                 printk("clear not equal %d %d\n", start, nbits);
 614                                 failed_tests++;
 615                         }
 616                         if (!__bitmap_equal(bmap1, bmap2, 1024)) {
 617                                 printk("clear not __equal %d %d\n", start,
 618                                                                         nbits);
 619                                 failed_tests++;
 620                         }
 621                 }
 622         }
 623 }
 624
 625 static const unsigned char clump_exp[] __initconst = {
 626         0x01,   /* 1 bit set */
 627         0x02,   /* non-edge 1 bit set */
 628         0x00,   /* zero bits set */
 629         0x38,   /* 3 bits set across 4-bit boundary */
 630         0x38,   /* Repeated clump */
 631         0x0F,   /* 4 bits set */
 632         0xFF,   /* all bits set */
 633         0x05,   /* non-adjacent 2 bits set */
 634 };
 635
 636 static void __init test_for_each_set_clump8(void)
 637 {
 638 #define CLUMP_EXP_NUMBITS 64
 639         DECLARE_BITMAP(bits, CLUMP_EXP_NUMBITS);
 640         unsigned int start;
 641         unsigned long clump;
 642
 643         /* set bitmap to test case */
 644         bitmap_zero(bits, CLUMP_EXP_NUMBITS);
 645         bitmap_set(bits, 0, 1);         /* 0x01 */
 646         bitmap_set(bits, 9, 1);         /* 0x02 */
 647         bitmap_set(bits, 27, 3);        /* 0x28 */
 648         bitmap_set(bits, 35, 3);        /* 0x28 */
 649         bitmap_set(bits, 40, 4);        /* 0x0F */
 650         bitmap_set(bits, 48, 8);        /* 0xFF */
 651         bitmap_set(bits, 56, 1);        /* 0x05 - part 1 */
 652         bitmap_set(bits, 58, 1);        /* 0x05 - part 2 */
 653
 654         for_each_set_clump8(start, clump, bits, CLUMP_EXP_NUMBITS)
 655                 expect_eq_clump8(start, CLUMP_EXP_NUMBITS, clump_exp, &clump);
 656 }
 657
 658 struct test_bitmap_cut {
 659         unsigned int first;
 660         unsigned int cut;
 661         unsigned int nbits;
 662         unsigned long in[4];
 663         unsigned long expected[4];
 664 };
 665
 666 static struct test_bitmap_cut test_cut[] = {
 667         {  0,  0,  8, { 0x0000000aUL, }, { 0x0000000aUL, }, },
 668         {  0,  0, 32, { 0xdadadeadUL, }, { 0xdadadeadUL, }, },
 669         {  0,  3,  8, { 0x000000aaUL, }, { 0x00000015UL, }, },
 670         {  3,  3,  8, { 0x000000aaUL, }, { 0x00000012UL, }, },
 671         {  0,  1, 32, { 0xa5a5a5a5UL, }, { 0x52d2d2d2UL, }, },
 672         {  0,  8, 32, { 0xdeadc0deUL, }, { 0x00deadc0UL, }, },
 673         {  1,  1, 32, { 0x5a5a5a5aUL, }, { 0x2d2d2d2cUL, }, },
 674         {  0, 15, 32, { 0xa5a5a5a5UL, }, { 0x00014b4bUL, }, },
 675         {  0, 16, 32, { 0xa5a5a5a5UL, }, { 0x0000a5a5UL, }, },
 676         { 15, 15, 32, { 0xa5a5a5a5UL, }, { 0x000125a5UL, }, },
 677         { 15, 16, 32, { 0xa5a5a5a5UL, }, { 0x0000a5a5UL, }, },
 678         { 16, 15, 32, { 0xa5a5a5a5UL, }, { 0x0001a5a5UL, }, },
 679
 680         { BITS_PER_LONG, BITS_PER_LONG, BITS_PER_LONG,
 681                 { 0xa5a5a5a5UL, 0xa5a5a5a5UL, },
 682                 { 0xa5a5a5a5UL, 0xa5a5a5a5UL, },
 683         },
 684         { 1, BITS_PER_LONG - 1, BITS_PER_LONG,
 685                 { 0xa5a5a5a5UL, 0xa5a5a5a5UL, },
 686                 { 0x00000001UL, 0x00000001UL, },
 687         },
 688
 689         { 0, BITS_PER_LONG * 2, BITS_PER_LONG * 2 + 1,
 690                 { 0xa5a5a5a5UL, 0x00000001UL, 0x00000001UL, 0x00000001UL },
 691                 { 0x00000001UL, },
 692         },
 693         { 16, BITS_PER_LONG * 2 + 1, BITS_PER_LONG * 2 + 1 + 16,
 694                 { 0x0000ffffUL, 0x5a5a5a5aUL, 0x5a5a5a5aUL, 0x5a5a5a5aUL },
 695                 { 0x2d2dffffUL, },
 696         },
 697 };
 698
 699 static void __init test_bitmap_cut(void)
 700 {
 701         unsigned long b[5], *in = &b[1], *out = &b[0];  /* Partial overlap */
 702         int i;
 703
 704         for (i = 0; i < ARRAY_SIZE(test_cut); i++) {
 705                 struct test_bitmap_cut *t = &test_cut[i];
 706
 707                 memcpy(in, t->in, sizeof(t->in));
 708
 709                 bitmap_cut(out, in, t->first, t->cut, t->nbits);
 710
 711                 expect_eq_bitmap(t->expected, out, t->nbits);
 712         }
 713 }
 714
 715 struct test_bitmap_print {
 716         const unsigned long *bitmap;
 717         unsigned long nbits;
 718         const char *mask;
 719         const char *list;
 720 };
 721
 722 static const unsigned long small_bitmap[] __initconst = {
 723         BITMAP_FROM_U64(0x3333333311111111ULL),
 724 };
 725
 726 static const char small_mask[] __initconst = "33333333,11111111\n";
 727 static const char small_list[] __initconst = "0,4,8,12,16,20,24,28,32-33,36-37,40-41,44-45,48-49,52-53,56-57,60-61\n";
 728
 729 static const unsigned long large_bitmap[] __initconst = {
 730         BITMAP_FROM_U64(0x3333333311111111ULL), BITMAP_FROM_U64(0x3333333311111111ULL),
 731         BITMAP_FROM_U64(0x3333333311111111ULL), BITMAP_FROM_U64(0x3333333311111111ULL),
 732         BITMAP_FROM_U64(0x3333333311111111ULL), BITMAP_FROM_U64(0x3333333311111111ULL),
 733         BITMAP_FROM_U64(0x3333333311111111ULL), BITMAP_FROM_U64(0x3333333311111111ULL),
 734         BITMAP_FROM_U64(0x3333333311111111ULL), BITMAP_FROM_U64(0x3333333311111111ULL),
 735         BITMAP_FROM_U64(0x3333333311111111ULL), BITMAP_FROM_U64(0x3333333311111111ULL),
 736         BITMAP_FROM_U64(0x3333333311111111ULL), BITMAP_FROM_U64(0x3333333311111111ULL),
 737         BITMAP_FROM_U64(0x3333333311111111ULL), BITMAP_FROM_U64(0x3333333311111111ULL),
 738         BITMAP_FROM_U64(0x3333333311111111ULL), BITMAP_FROM_U64(0x3333333311111111ULL),
 739         BITMAP_FROM_U64(0x3333333311111111ULL), BITMAP_FROM_U64(0x3333333311111111ULL),
 740         BITMAP_FROM_U64(0x3333333311111111ULL), BITMAP_FROM_U64(0x3333333311111111ULL),
 741         BITMAP_FROM_U64(0x3333333311111111ULL), BITMAP_FROM_U64(0x3333333311111111ULL),
 742         BITMAP_FROM_U64(0x3333333311111111ULL), BITMAP_FROM_U64(0x3333333311111111ULL),
 743         BITMAP_FROM_U64(0x3333333311111111ULL), BITMAP_FROM_U64(0x3333333311111111ULL),
 744         BITMAP_FROM_U64(0x3333333311111111ULL), BITMAP_FROM_U64(0x3333333311111111ULL),
 745         BITMAP_FROM_U64(0x3333333311111111ULL), BITMAP_FROM_U64(0x3333333311111111ULL),
 746         BITMAP_FROM_U64(0x3333333311111111ULL), BITMAP_FROM_U64(0x3333333311111111ULL),
 747         BITMAP_FROM_U64(0x3333333311111111ULL), BITMAP_FROM_U64(0x3333333311111111ULL),
 748         BITMAP_FROM_U64(0x3333333311111111ULL), BITMAP_FROM_U64(0x3333333311111111ULL),
 749         BITMAP_FROM_U64(0x3333333311111111ULL), BITMAP_FROM_U64(0x3333333311111111ULL),
 750 };
 751
 752 static const char large_mask[] __initconst = "33333333,11111111,33333333,11111111,"
 753                                         "33333333,11111111,33333333,11111111,"
 754                                         "33333333,11111111,33333333,11111111,"
 755                                         "33333333,11111111,33333333,11111111,"
 756                                         "33333333,11111111,33333333,11111111,"
 757                                         "33333333,11111111,33333333,11111111,"
 758                                         "33333333,11111111,33333333,11111111,"
 759                                         "33333333,11111111,33333333,11111111,"
 760                                         "33333333,11111111,33333333,11111111,"
 761                                         "33333333,11111111,33333333,11111111,"
 762                                         "33333333,11111111,33333333,11111111,"
 763                                         "33333333,11111111,33333333,11111111,"
 764                                         "33333333,11111111,33333333,11111111,"
 765                                         "33333333,11111111,33333333,11111111,"
 766                                         "33333333,11111111,33333333,11111111,"
 767                                         "33333333,11111111,33333333,11111111,"
 768                                         "33333333,11111111,33333333,11111111,"
 769                                         "33333333,11111111,33333333,11111111,"
 770                                         "33333333,11111111,33333333,11111111,"
 771                                         "33333333,11111111,33333333,11111111\n";
 772
 773 static const char large_list[] __initconst = /* more than 4KB */
 774         "0,4,8,12,16,20,24,28,32-33,36-37,40-41,44-45,48-49,52-53,56-57,60-61,64,68,72,76,80,84,88,92,96-97,100-101,104-1"
 775         "05,108-109,112-113,116-117,120-121,124-125,128,132,136,140,144,148,152,156,160-161,164-165,168-169,172-173,176-1"
 776         "77,180-181,184-185,188-189,192,196,200,204,208,212,216,220,224-225,228-229,232-233,236-237,240-241,244-245,248-2"
 777         "49,252-253,256,260,264,268,272,276,280,284,288-289,292-293,296-297,300-301,304-305,308-309,312-313,316-317,320,3"
 778         "24,328,332,336,340,344,348,352-353,356-357,360-361,364-365,368-369,372-373,376-377,380-381,384,388,392,396,400,4"
 779         "04,408,412,416-417,420-421,424-425,428-429,432-433,436-437,440-441,444-445,448,452,456,460,464,468,472,476,480-4"
 780         "81,484-485,488-489,492-493,496-497,500-501,504-505,508-509,512,516,520,524,528,532,536,540,544-545,548-549,552-5"
 781         "53,556-557,560-561,564-565,568-569,572-573,576,580,584,588,592,596,600,604,608-609,612-613,616-617,620-621,624-6"
 782         "25,628-629,632-633,636-637,640,644,648,652,656,660,664,668,672-673,676-677,680-681,684-685,688-689,692-693,696-6"
 783         "97,700-701,704,708,712,716,720,724,728,732,736-737,740-741,744-745,748-749,752-753,756-757,760-761,764-765,768,7"
 784         "72,776,780,784,788,792,796,800-801,804-805,808-809,812-813,816-817,820-821,824-825,828-829,832,836,840,844,848,8"
 785         "52,856,860,864-865,868-869,872-873,876-877,880-881,884-885,888-889,892-893,896,900,904,908,912,916,920,924,928-9"
 786         "29,932-933,936-937,940-941,944-945,948-949,952-953,956-957,960,964,968,972,976,980,984,988,992-993,996-997,1000-"
 787         "1001,1004-1005,1008-1009,1012-1013,1016-1017,1020-1021,1024,1028,1032,1036,1040,1044,1048,1052,1056-1057,1060-10"
 788         "61,1064-1065,1068-1069,1072-1073,1076-1077,1080-1081,1084-1085,1088,1092,1096,1100,1104,1108,1112,1116,1120-1121"
 789         ",1124-1125,1128-1129,1132-1133,1136-1137,1140-1141,1144-1145,1148-1149,1152,1156,1160,1164,1168,1172,1176,1180,1"
 790         "184-1185,1188-1189,1192-1193,1196-1197,1200-1201,1204-1205,1208-1209,1212-1213,1216,1220,1224,1228,1232,1236,124"
 791         "0,1244,1248-1249,1252-1253,1256-1257,1260-1261,1264-1265,1268-1269,1272-1273,1276-1277,1280,1284,1288,1292,1296,"
 792         "1300,1304,1308,1312-1313,1316-1317,1320-1321,1324-1325,1328-1329,1332-1333,1336-1337,1340-1341,1344,1348,1352,13"
 793         "56,1360,1364,1368,1372,1376-1377,1380-1381,1384-1385,1388-1389,1392-1393,1396-1397,1400-1401,1404-1405,1408,1412"
 794         ",1416,1420,1424,1428,1432,1436,1440-1441,1444-1445,1448-1449,1452-1453,1456-1457,1460-1461,1464-1465,1468-1469,1"
 795         "472,1476,1480,1484,1488,1492,1496,1500,1504-1505,1508-1509,1512-1513,1516-1517,1520-1521,1524-1525,1528-1529,153"
 796         "2-1533,1536,1540,1544,1548,1552,1556,1560,1564,1568-1569,1572-1573,1576-1577,1580-1581,1584-1585,1588-1589,1592-"
 797         "1593,1596-1597,1600,1604,1608,1612,1616,1620,1624,1628,1632-1633,1636-1637,1640-1641,1644-1645,1648-1649,1652-16"
 798         "53,1656-1657,1660-1661,1664,1668,1672,1676,1680,1684,1688,1692,1696-1697,1700-1701,1704-1705,1708-1709,1712-1713"
 799         ",1716-1717,1720-1721,1724-1725,1728,1732,1736,1740,1744,1748,1752,1756,1760-1761,1764-1765,1768-1769,1772-1773,1"
 800         "776-1777,1780-1781,1784-1785,1788-1789,1792,1796,1800,1804,1808,1812,1816,1820,1824-1825,1828-1829,1832-1833,183"
 801         "6-1837,1840-1841,1844-1845,1848-1849,1852-1853,1856,1860,1864,1868,1872,1876,1880,1884,1888-1889,1892-1893,1896-"
 802         "1897,1900-1901,1904-1905,1908-1909,1912-1913,1916-1917,1920,1924,1928,1932,1936,1940,1944,1948,1952-1953,1956-19"
 803         "57,1960-1961,1964-1965,1968-1969,1972-1973,1976-1977,1980-1981,1984,1988,1992,1996,2000,2004,2008,2012,2016-2017"
 804         ",2020-2021,2024-2025,2028-2029,2032-2033,2036-2037,2040-2041,2044-2045,2048,2052,2056,2060,2064,2068,2072,2076,2"
 805         "080-2081,2084-2085,2088-2089,2092-2093,2096-2097,2100-2101,2104-2105,2108-2109,2112,2116,2120,2124,2128,2132,213"
 806         "6,2140,2144-2145,2148-2149,2152-2153,2156-2157,2160-2161,2164-2165,2168-2169,2172-2173,2176,2180,2184,2188,2192,"
 807         "2196,2200,2204,2208-2209,2212-2213,2216-2217,2220-2221,2224-2225,2228-2229,2232-2233,2236-2237,2240,2244,2248,22"
 808         "52,2256,2260,2264,2268,2272-2273,2276-2277,2280-2281,2284-2285,2288-2289,2292-2293,2296-2297,2300-2301,2304,2308"
 809         ",2312,2316,2320,2324,2328,2332,2336-2337,2340-2341,2344-2345,2348-2349,2352-2353,2356-2357,2360-2361,2364-2365,2"
 810         "368,2372,2376,2380,2384,2388,2392,2396,2400-2401,2404-2405,2408-2409,2412-2413,2416-2417,2420-2421,2424-2425,242"
 811         "8-2429,2432,2436,2440,2444,2448,2452,2456,2460,2464-2465,2468-2469,2472-2473,2476-2477,2480-2481,2484-2485,2488-"
 812         "2489,2492-2493,2496,2500,2504,2508,2512,2516,2520,2524,2528-2529,2532-2533,2536-2537,2540-2541,2544-2545,2548-25"
 813         "49,2552-2553,2556-2557\n";
 814
 815 static const struct test_bitmap_print test_print[] __initconst = {
 816         { small_bitmap, sizeof(small_bitmap) * BITS_PER_BYTE, small_mask, small_list },
 817         { large_bitmap, sizeof(large_bitmap) * BITS_PER_BYTE, large_mask, large_list },
 818 };
 819
 820 static void __init test_bitmap_print_buf(void)
 821 {
 822         int i;
 823
 824         for (i = 0; i < ARRAY_SIZE(test_print); i++) {
 825                 const struct test_bitmap_print *t = &test_print[i];
 826                 int n;
 827
 828                 n = bitmap_print_bitmask_to_buf(print_buf, t->bitmap, t->nbits,
 829                                                 0, 2 * PAGE_SIZE);
 830                 expect_eq_uint(strlen(t->mask) + 1, n);
 831                 expect_eq_str(t->mask, print_buf, n);
 832
 833                 n = bitmap_print_list_to_buf(print_buf, t->bitmap, t->nbits,
 834                                              0, 2 * PAGE_SIZE);
 835                 expect_eq_uint(strlen(t->list) + 1, n);
 836                 expect_eq_str(t->list, print_buf, n);
 837
 838                 /* test by non-zero offset */
 839                 if (strlen(t->list) > PAGE_SIZE) {
 840                         n = bitmap_print_list_to_buf(print_buf, t->bitmap, t->nbits,
 841                                                      PAGE_SIZE, PAGE_SIZE);
 842                         expect_eq_uint(strlen(t->list) + 1 - PAGE_SIZE, n);
 843                         expect_eq_str(t->list + PAGE_SIZE, print_buf, n);
 844                 }
 845         }
 846 }
 847
 848 static void __init selftest(void)
 849 {
 850         test_zero_clear();
 851         test_fill_set();
 852         test_copy();
 853         test_replace();
 854         test_bitmap_arr32();
 855         test_bitmap_parse();
 856         test_bitmap_parselist();
 857         test_bitmap_printlist();
 858         test_mem_optimisations();
 859         test_for_each_set_clump8();
 860         test_bitmap_cut();
 861         test_bitmap_print_buf();
 862 }
 863
 864 KSTM_MODULE_LOADERS(test_bitmap);
 865 MODULE_AUTHOR("david decotigny <david.decotigny@googlers.com>");
 866 MODULE_LICENSE("GPL");