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