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 __init test_bitmap_arr64(void)
 589 {
 590         unsigned int nbits, next_bit;
 591         u64 arr[EXP1_IN_BITS / 64];
 592         DECLARE_BITMAP(bmap2, EXP1_IN_BITS);
 593
 594         memset(arr, 0xa5, sizeof(arr));
 595
 596         for (nbits = 0; nbits < EXP1_IN_BITS; ++nbits) {
 597                 memset(bmap2, 0xff, sizeof(arr));
 598                 bitmap_to_arr64(arr, exp1, nbits);
 599                 bitmap_from_arr64(bmap2, arr, nbits);
 600                 expect_eq_bitmap(bmap2, exp1, nbits);
 601
 602                 next_bit = find_next_bit(bmap2, round_up(nbits, BITS_PER_LONG), nbits);
 603                 if (next_bit < round_up(nbits, BITS_PER_LONG))
 604                         pr_err("bitmap_copy_arr64(nbits == %d:"
 605                                 " tail is not safely cleared: %d\n", nbits, next_bit);
 606
 607                 if (nbits < EXP1_IN_BITS - 64)
 608                         expect_eq_uint(arr[DIV_ROUND_UP(nbits, 64)], 0xa5a5a5a5);
 609         }
 610 }
 611
 612 static void noinline __init test_mem_optimisations(void)
 613 {
 614         DECLARE_BITMAP(bmap1, 1024);
 615         DECLARE_BITMAP(bmap2, 1024);
 616         unsigned int start, nbits;
 617
 618         for (start = 0; start < 1024; start += 8) {
 619                 for (nbits = 0; nbits < 1024 - start; nbits += 8) {
 620                         memset(bmap1, 0x5a, sizeof(bmap1));
 621                         memset(bmap2, 0x5a, sizeof(bmap2));
 622
 623                         bitmap_set(bmap1, start, nbits);
 624                         __bitmap_set(bmap2, start, nbits);
 625                         if (!bitmap_equal(bmap1, bmap2, 1024)) {
 626                                 printk("set not equal %d %d\n", start, nbits);
 627                                 failed_tests++;
 628                         }
 629                         if (!__bitmap_equal(bmap1, bmap2, 1024)) {
 630                                 printk("set not __equal %d %d\n", start, nbits);
 631                                 failed_tests++;
 632                         }
 633
 634                         bitmap_clear(bmap1, start, nbits);
 635                         __bitmap_clear(bmap2, start, nbits);
 636                         if (!bitmap_equal(bmap1, bmap2, 1024)) {
 637                                 printk("clear not equal %d %d\n", start, nbits);
 638                                 failed_tests++;
 639                         }
 640                         if (!__bitmap_equal(bmap1, bmap2, 1024)) {
 641                                 printk("clear not __equal %d %d\n", start,
 642                                                                         nbits);
 643                                 failed_tests++;
 644                         }
 645                 }
 646         }
 647 }
 648
 649 static const unsigned char clump_exp[] __initconst = {
 650         0x01,   /* 1 bit set */
 651         0x02,   /* non-edge 1 bit set */
 652         0x00,   /* zero bits set */
 653         0x38,   /* 3 bits set across 4-bit boundary */
 654         0x38,   /* Repeated clump */
 655         0x0F,   /* 4 bits set */
 656         0xFF,   /* all bits set */
 657         0x05,   /* non-adjacent 2 bits set */
 658 };
 659
 660 static void __init test_for_each_set_clump8(void)
 661 {
 662 #define CLUMP_EXP_NUMBITS 64
 663         DECLARE_BITMAP(bits, CLUMP_EXP_NUMBITS);
 664         unsigned int start;
 665         unsigned long clump;
 666
 667         /* set bitmap to test case */
 668         bitmap_zero(bits, CLUMP_EXP_NUMBITS);
 669         bitmap_set(bits, 0, 1);         /* 0x01 */
 670         bitmap_set(bits, 9, 1);         /* 0x02 */
 671         bitmap_set(bits, 27, 3);        /* 0x28 */
 672         bitmap_set(bits, 35, 3);        /* 0x28 */
 673         bitmap_set(bits, 40, 4);        /* 0x0F */
 674         bitmap_set(bits, 48, 8);        /* 0xFF */
 675         bitmap_set(bits, 56, 1);        /* 0x05 - part 1 */
 676         bitmap_set(bits, 58, 1);        /* 0x05 - part 2 */
 677
 678         for_each_set_clump8(start, clump, bits, CLUMP_EXP_NUMBITS)
 679                 expect_eq_clump8(start, CLUMP_EXP_NUMBITS, clump_exp, &clump);
 680 }
 681
 682 struct test_bitmap_cut {
 683         unsigned int first;
 684         unsigned int cut;
 685         unsigned int nbits;
 686         unsigned long in[4];
 687         unsigned long expected[4];
 688 };
 689
 690 static struct test_bitmap_cut test_cut[] = {
 691         {  0,  0,  8, { 0x0000000aUL, }, { 0x0000000aUL, }, },
 692         {  0,  0, 32, { 0xdadadeadUL, }, { 0xdadadeadUL, }, },
 693         {  0,  3,  8, { 0x000000aaUL, }, { 0x00000015UL, }, },
 694         {  3,  3,  8, { 0x000000aaUL, }, { 0x00000012UL, }, },
 695         {  0,  1, 32, { 0xa5a5a5a5UL, }, { 0x52d2d2d2UL, }, },
 696         {  0,  8, 32, { 0xdeadc0deUL, }, { 0x00deadc0UL, }, },
 697         {  1,  1, 32, { 0x5a5a5a5aUL, }, { 0x2d2d2d2cUL, }, },
 698         {  0, 15, 32, { 0xa5a5a5a5UL, }, { 0x00014b4bUL, }, },
 699         {  0, 16, 32, { 0xa5a5a5a5UL, }, { 0x0000a5a5UL, }, },
 700         { 15, 15, 32, { 0xa5a5a5a5UL, }, { 0x000125a5UL, }, },
 701         { 15, 16, 32, { 0xa5a5a5a5UL, }, { 0x0000a5a5UL, }, },
 702         { 16, 15, 32, { 0xa5a5a5a5UL, }, { 0x0001a5a5UL, }, },
 703
 704         { BITS_PER_LONG, BITS_PER_LONG, BITS_PER_LONG,
 705                 { 0xa5a5a5a5UL, 0xa5a5a5a5UL, },
 706                 { 0xa5a5a5a5UL, 0xa5a5a5a5UL, },
 707         },
 708         { 1, BITS_PER_LONG - 1, BITS_PER_LONG,
 709                 { 0xa5a5a5a5UL, 0xa5a5a5a5UL, },
 710                 { 0x00000001UL, 0x00000001UL, },
 711         },
 712
 713         { 0, BITS_PER_LONG * 2, BITS_PER_LONG * 2 + 1,
 714                 { 0xa5a5a5a5UL, 0x00000001UL, 0x00000001UL, 0x00000001UL },
 715                 { 0x00000001UL, },
 716         },
 717         { 16, BITS_PER_LONG * 2 + 1, BITS_PER_LONG * 2 + 1 + 16,
 718                 { 0x0000ffffUL, 0x5a5a5a5aUL, 0x5a5a5a5aUL, 0x5a5a5a5aUL },
 719                 { 0x2d2dffffUL, },
 720         },
 721 };
 722
 723 static void __init test_bitmap_cut(void)
 724 {
 725         unsigned long b[5], *in = &b[1], *out = &b[0];  /* Partial overlap */
 726         int i;
 727
 728         for (i = 0; i < ARRAY_SIZE(test_cut); i++) {
 729                 struct test_bitmap_cut *t = &test_cut[i];
 730
 731                 memcpy(in, t->in, sizeof(t->in));
 732
 733                 bitmap_cut(out, in, t->first, t->cut, t->nbits);
 734
 735                 expect_eq_bitmap(t->expected, out, t->nbits);
 736         }
 737 }
 738
 739 struct test_bitmap_print {
 740         const unsigned long *bitmap;
 741         unsigned long nbits;
 742         const char *mask;
 743         const char *list;
 744 };
 745
 746 static const unsigned long small_bitmap[] __initconst = {
 747         BITMAP_FROM_U64(0x3333333311111111ULL),
 748 };
 749
 750 static const char small_mask[] __initconst = "33333333,11111111\n";
 751 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";
 752
 753 static const unsigned long large_bitmap[] __initconst = {
 754         BITMAP_FROM_U64(0x3333333311111111ULL), BITMAP_FROM_U64(0x3333333311111111ULL),
 755         BITMAP_FROM_U64(0x3333333311111111ULL), BITMAP_FROM_U64(0x3333333311111111ULL),
 756         BITMAP_FROM_U64(0x3333333311111111ULL), BITMAP_FROM_U64(0x3333333311111111ULL),
 757         BITMAP_FROM_U64(0x3333333311111111ULL), BITMAP_FROM_U64(0x3333333311111111ULL),
 758         BITMAP_FROM_U64(0x3333333311111111ULL), BITMAP_FROM_U64(0x3333333311111111ULL),
 759         BITMAP_FROM_U64(0x3333333311111111ULL), BITMAP_FROM_U64(0x3333333311111111ULL),
 760         BITMAP_FROM_U64(0x3333333311111111ULL), BITMAP_FROM_U64(0x3333333311111111ULL),
 761         BITMAP_FROM_U64(0x3333333311111111ULL), BITMAP_FROM_U64(0x3333333311111111ULL),
 762         BITMAP_FROM_U64(0x3333333311111111ULL), BITMAP_FROM_U64(0x3333333311111111ULL),
 763         BITMAP_FROM_U64(0x3333333311111111ULL), BITMAP_FROM_U64(0x3333333311111111ULL),
 764         BITMAP_FROM_U64(0x3333333311111111ULL), BITMAP_FROM_U64(0x3333333311111111ULL),
 765         BITMAP_FROM_U64(0x3333333311111111ULL), BITMAP_FROM_U64(0x3333333311111111ULL),
 766         BITMAP_FROM_U64(0x3333333311111111ULL), BITMAP_FROM_U64(0x3333333311111111ULL),
 767         BITMAP_FROM_U64(0x3333333311111111ULL), BITMAP_FROM_U64(0x3333333311111111ULL),
 768         BITMAP_FROM_U64(0x3333333311111111ULL), BITMAP_FROM_U64(0x3333333311111111ULL),
 769         BITMAP_FROM_U64(0x3333333311111111ULL), BITMAP_FROM_U64(0x3333333311111111ULL),
 770         BITMAP_FROM_U64(0x3333333311111111ULL), BITMAP_FROM_U64(0x3333333311111111ULL),
 771         BITMAP_FROM_U64(0x3333333311111111ULL), BITMAP_FROM_U64(0x3333333311111111ULL),
 772         BITMAP_FROM_U64(0x3333333311111111ULL), BITMAP_FROM_U64(0x3333333311111111ULL),
 773         BITMAP_FROM_U64(0x3333333311111111ULL), BITMAP_FROM_U64(0x3333333311111111ULL),
 774 };
 775
 776 static const char large_mask[] __initconst = "33333333,11111111,33333333,11111111,"
 777                                         "33333333,11111111,33333333,11111111,"
 778                                         "33333333,11111111,33333333,11111111,"
 779                                         "33333333,11111111,33333333,11111111,"
 780                                         "33333333,11111111,33333333,11111111,"
 781                                         "33333333,11111111,33333333,11111111,"
 782                                         "33333333,11111111,33333333,11111111,"
 783                                         "33333333,11111111,33333333,11111111,"
 784                                         "33333333,11111111,33333333,11111111,"
 785                                         "33333333,11111111,33333333,11111111,"
 786                                         "33333333,11111111,33333333,11111111,"
 787                                         "33333333,11111111,33333333,11111111,"
 788                                         "33333333,11111111,33333333,11111111,"
 789                                         "33333333,11111111,33333333,11111111,"
 790                                         "33333333,11111111,33333333,11111111,"
 791                                         "33333333,11111111,33333333,11111111,"
 792                                         "33333333,11111111,33333333,11111111,"
 793                                         "33333333,11111111,33333333,11111111,"
 794                                         "33333333,11111111,33333333,11111111,"
 795                                         "33333333,11111111,33333333,11111111\n";
 796
 797 static const char large_list[] __initconst = /* more than 4KB */
 798         "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"
 799         "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"
 800         "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"
 801         "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"
 802         "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"
 803         "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"
 804         "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"
 805         "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"
 806         "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"
 807         "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"
 808         "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"
 809         "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"
 810         "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-"
 811         "1001,1004-1005,1008-1009,1012-1013,1016-1017,1020-1021,1024,1028,1032,1036,1040,1044,1048,1052,1056-1057,1060-10"
 812         "61,1064-1065,1068-1069,1072-1073,1076-1077,1080-1081,1084-1085,1088,1092,1096,1100,1104,1108,1112,1116,1120-1121"
 813         ",1124-1125,1128-1129,1132-1133,1136-1137,1140-1141,1144-1145,1148-1149,1152,1156,1160,1164,1168,1172,1176,1180,1"
 814         "184-1185,1188-1189,1192-1193,1196-1197,1200-1201,1204-1205,1208-1209,1212-1213,1216,1220,1224,1228,1232,1236,124"
 815         "0,1244,1248-1249,1252-1253,1256-1257,1260-1261,1264-1265,1268-1269,1272-1273,1276-1277,1280,1284,1288,1292,1296,"
 816         "1300,1304,1308,1312-1313,1316-1317,1320-1321,1324-1325,1328-1329,1332-1333,1336-1337,1340-1341,1344,1348,1352,13"
 817         "56,1360,1364,1368,1372,1376-1377,1380-1381,1384-1385,1388-1389,1392-1393,1396-1397,1400-1401,1404-1405,1408,1412"
 818         ",1416,1420,1424,1428,1432,1436,1440-1441,1444-1445,1448-1449,1452-1453,1456-1457,1460-1461,1464-1465,1468-1469,1"
 819         "472,1476,1480,1484,1488,1492,1496,1500,1504-1505,1508-1509,1512-1513,1516-1517,1520-1521,1524-1525,1528-1529,153"
 820         "2-1533,1536,1540,1544,1548,1552,1556,1560,1564,1568-1569,1572-1573,1576-1577,1580-1581,1584-1585,1588-1589,1592-"
 821         "1593,1596-1597,1600,1604,1608,1612,1616,1620,1624,1628,1632-1633,1636-1637,1640-1641,1644-1645,1648-1649,1652-16"
 822         "53,1656-1657,1660-1661,1664,1668,1672,1676,1680,1684,1688,1692,1696-1697,1700-1701,1704-1705,1708-1709,1712-1713"
 823         ",1716-1717,1720-1721,1724-1725,1728,1732,1736,1740,1744,1748,1752,1756,1760-1761,1764-1765,1768-1769,1772-1773,1"
 824         "776-1777,1780-1781,1784-1785,1788-1789,1792,1796,1800,1804,1808,1812,1816,1820,1824-1825,1828-1829,1832-1833,183"
 825         "6-1837,1840-1841,1844-1845,1848-1849,1852-1853,1856,1860,1864,1868,1872,1876,1880,1884,1888-1889,1892-1893,1896-"
 826         "1897,1900-1901,1904-1905,1908-1909,1912-1913,1916-1917,1920,1924,1928,1932,1936,1940,1944,1948,1952-1953,1956-19"
 827         "57,1960-1961,1964-1965,1968-1969,1972-1973,1976-1977,1980-1981,1984,1988,1992,1996,2000,2004,2008,2012,2016-2017"
 828         ",2020-2021,2024-2025,2028-2029,2032-2033,2036-2037,2040-2041,2044-2045,2048,2052,2056,2060,2064,2068,2072,2076,2"
 829         "080-2081,2084-2085,2088-2089,2092-2093,2096-2097,2100-2101,2104-2105,2108-2109,2112,2116,2120,2124,2128,2132,213"
 830         "6,2140,2144-2145,2148-2149,2152-2153,2156-2157,2160-2161,2164-2165,2168-2169,2172-2173,2176,2180,2184,2188,2192,"
 831         "2196,2200,2204,2208-2209,2212-2213,2216-2217,2220-2221,2224-2225,2228-2229,2232-2233,2236-2237,2240,2244,2248,22"
 832         "52,2256,2260,2264,2268,2272-2273,2276-2277,2280-2281,2284-2285,2288-2289,2292-2293,2296-2297,2300-2301,2304,2308"
 833         ",2312,2316,2320,2324,2328,2332,2336-2337,2340-2341,2344-2345,2348-2349,2352-2353,2356-2357,2360-2361,2364-2365,2"
 834         "368,2372,2376,2380,2384,2388,2392,2396,2400-2401,2404-2405,2408-2409,2412-2413,2416-2417,2420-2421,2424-2425,242"
 835         "8-2429,2432,2436,2440,2444,2448,2452,2456,2460,2464-2465,2468-2469,2472-2473,2476-2477,2480-2481,2484-2485,2488-"
 836         "2489,2492-2493,2496,2500,2504,2508,2512,2516,2520,2524,2528-2529,2532-2533,2536-2537,2540-2541,2544-2545,2548-25"
 837         "49,2552-2553,2556-2557\n";
 838
 839 static const struct test_bitmap_print test_print[] __initconst = {
 840         { small_bitmap, sizeof(small_bitmap) * BITS_PER_BYTE, small_mask, small_list },
 841         { large_bitmap, sizeof(large_bitmap) * BITS_PER_BYTE, large_mask, large_list },
 842 };
 843
 844 static void __init test_bitmap_print_buf(void)
 845 {
 846         int i;
 847
 848         for (i = 0; i < ARRAY_SIZE(test_print); i++) {
 849                 const struct test_bitmap_print *t = &test_print[i];
 850                 int n;
 851
 852                 n = bitmap_print_bitmask_to_buf(print_buf, t->bitmap, t->nbits,
 853                                                 0, 2 * PAGE_SIZE);
 854                 expect_eq_uint(strlen(t->mask) + 1, n);
 855                 expect_eq_str(t->mask, print_buf, n);
 856
 857                 n = bitmap_print_list_to_buf(print_buf, t->bitmap, t->nbits,
 858                                              0, 2 * PAGE_SIZE);
 859                 expect_eq_uint(strlen(t->list) + 1, n);
 860                 expect_eq_str(t->list, print_buf, n);
 861
 862                 /* test by non-zero offset */
 863                 if (strlen(t->list) > PAGE_SIZE) {
 864                         n = bitmap_print_list_to_buf(print_buf, t->bitmap, t->nbits,
 865                                                      PAGE_SIZE, PAGE_SIZE);
 866                         expect_eq_uint(strlen(t->list) + 1 - PAGE_SIZE, n);
 867                         expect_eq_str(t->list + PAGE_SIZE, print_buf, n);
 868                 }
 869         }
 870 }
 871
 872 static void __init selftest(void)
 873 {
 874         test_zero_clear();
 875         test_fill_set();
 876         test_copy();
 877         test_replace();
 878         test_bitmap_arr32();
 879         test_bitmap_arr64();
 880         test_bitmap_parse();
 881         test_bitmap_parselist();
 882         test_bitmap_printlist();
 883         test_mem_optimisations();
 884         test_for_each_set_clump8();
 885         test_bitmap_cut();
 886         test_bitmap_print_buf();
 887 }
 888
 889 KSTM_MODULE_LOADERS(test_bitmap);
 890 MODULE_AUTHOR("david decotigny <david.decotigny@googlers.com>");
 891 MODULE_LICENSE("GPL");