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                         failed_tests++;
 474                         continue;
 475                 }
 476
 477                 if (!err && ptest.expected
 478                          && !__bitmap_equal(bmap, ptest.expected, ptest.nbits)) {
 479                         pr_err("parselist: %d: input is %s, result is 0x%lx, expected 0x%lx\n",
 480                                         i, ptest.in, bmap[0],
 481                                         *ptest.expected);
 482                         failed_tests++;
 483                         continue;
 484                 }
 485
 486                 if (ptest.flags & PARSE_TIME)
 487                         pr_err("parselist: %d: input is '%s' OK, Time: %llu\n",
 488                                         i, ptest.in, time);
 489
 490 #undef ptest
 491         }
 492 }
 493
 494 static void __init test_bitmap_printlist(void)
 495 {
 496         unsigned long *bmap = kmalloc(PAGE_SIZE, GFP_KERNEL);
 497         char *buf = kmalloc(PAGE_SIZE, GFP_KERNEL);
 498         char expected[256];
 499         int ret, slen;
 500         ktime_t time;
 501
 502         if (!buf || !bmap)
 503                 goto out;
 504
 505         memset(bmap, -1, PAGE_SIZE);
 506         slen = snprintf(expected, 256, "0-%ld", PAGE_SIZE * 8 - 1);
 507         if (slen < 0)
 508                 goto out;
 509
 510         time = ktime_get();
 511         ret = bitmap_print_to_pagebuf(true, buf, bmap, PAGE_SIZE * 8);
 512         time = ktime_get() - time;
 513
 514         if (ret != slen + 1) {
 515                 pr_err("bitmap_print_to_pagebuf: result is %d, expected %d\n", ret, slen);
 516                 failed_tests++;
 517                 goto out;
 518         }
 519
 520         if (strncmp(buf, expected, slen)) {
 521                 pr_err("bitmap_print_to_pagebuf: result is %s, expected %s\n", buf, expected);
 522                 failed_tests++;
 523                 goto out;
 524         }
 525
 526         pr_err("bitmap_print_to_pagebuf: input is '%s', Time: %llu\n", buf, time);
 527 out:
 528         kfree(buf);
 529         kfree(bmap);
 530 }
 531
 532 static const unsigned long parse_test[] __initconst = {
 533         BITMAP_FROM_U64(0),
 534         BITMAP_FROM_U64(1),
 535         BITMAP_FROM_U64(0xdeadbeef),
 536         BITMAP_FROM_U64(0x100000000ULL),
 537 };
 538
 539 static const unsigned long parse_test2[] __initconst = {
 540         BITMAP_FROM_U64(0x100000000ULL), BITMAP_FROM_U64(0xdeadbeef),
 541         BITMAP_FROM_U64(0x100000000ULL), BITMAP_FROM_U64(0xbaadf00ddeadbeef),
 542         BITMAP_FROM_U64(0x100000000ULL), BITMAP_FROM_U64(0x0badf00ddeadbeef),
 543 };
 544
 545 static const struct test_bitmap_parselist parse_tests[] __initconst = {
 546         {0, "",                         &parse_test[0 * step], 32, 0},
 547         {0, " ",                        &parse_test[0 * step], 32, 0},
 548         {0, "0",                        &parse_test[0 * step], 32, 0},
 549         {0, "0\n",                      &parse_test[0 * step], 32, 0},
 550         {0, "1",                        &parse_test[1 * step], 32, 0},
 551         {0, "deadbeef",                 &parse_test[2 * step], 32, 0},
 552         {0, "1,0",                      &parse_test[3 * step], 33, 0},
 553         {0, "deadbeef,\n,0,1",          &parse_test[2 * step], 96, 0},
 554
 555         {0, "deadbeef,1,0",             &parse_test2[0 * 2 * step], 96, 0},
 556         {0, "baadf00d,deadbeef,1,0",    &parse_test2[1 * 2 * step], 128, 0},
 557         {0, "badf00d,deadbeef,1,0",     &parse_test2[2 * 2 * step], 124, 0},
 558         {0, "badf00d,deadbeef,1,0",     &parse_test2[2 * 2 * step], 124, NO_LEN},
 559         {0, "  badf00d,deadbeef,1,0  ", &parse_test2[2 * 2 * step], 124, 0},
 560         {0, " , badf00d,deadbeef,1,0 , ",       &parse_test2[2 * 2 * step], 124, 0},
 561         {0, " , badf00d, ,, ,,deadbeef,1,0 , ", &parse_test2[2 * 2 * step], 124, 0},
 562
 563         {-EINVAL,    "goodfood,deadbeef,1,0",   NULL, 128, 0},
 564         {-EOVERFLOW, "3,0",                     NULL, 33, 0},
 565         {-EOVERFLOW, "123badf00d,deadbeef,1,0", NULL, 128, 0},
 566         {-EOVERFLOW, "badf00d,deadbeef,1,0",    NULL, 90, 0},
 567         {-EOVERFLOW, "fbadf00d,deadbeef,1,0",   NULL, 95, 0},
 568         {-EOVERFLOW, "badf00d,deadbeef,1,0",    NULL, 100, 0},
 569 #undef step
 570 };
 571
 572 static void __init test_bitmap_parse(void)
 573 {
 574         int i;
 575         int err;
 576         ktime_t time;
 577         DECLARE_BITMAP(bmap, 2048);
 578
 579         for (i = 0; i < ARRAY_SIZE(parse_tests); i++) {
 580                 struct test_bitmap_parselist test = parse_tests[i];
 581                 size_t len = test.flags & NO_LEN ? UINT_MAX : strlen(test.in);
 582
 583                 time = ktime_get();
 584                 err = bitmap_parse(test.in, len, bmap, test.nbits);
 585                 time = ktime_get() - time;
 586
 587                 if (err != test.errno) {
 588                         pr_err("parse: %d: input is %s, errno is %d, expected %d\n",
 589                                         i, test.in, err, test.errno);
 590                         failed_tests++;
 591                         continue;
 592                 }
 593
 594                 if (!err && test.expected
 595                          && !__bitmap_equal(bmap, test.expected, test.nbits)) {
 596                         pr_err("parse: %d: input is %s, result is 0x%lx, expected 0x%lx\n",
 597                                         i, test.in, bmap[0],
 598                                         *test.expected);
 599                         failed_tests++;
 600                         continue;
 601                 }
 602
 603                 if (test.flags & PARSE_TIME)
 604                         pr_err("parse: %d: input is '%s' OK, Time: %llu\n",
 605                                         i, test.in, time);
 606         }
 607 }
 608
 609 static void __init test_bitmap_arr32(void)
 610 {
 611         unsigned int nbits, next_bit;
 612         u32 arr[EXP1_IN_BITS / 32];
 613         DECLARE_BITMAP(bmap2, EXP1_IN_BITS);
 614
 615         memset(arr, 0xa5, sizeof(arr));
 616
 617         for (nbits = 0; nbits < EXP1_IN_BITS; ++nbits) {
 618                 bitmap_to_arr32(arr, exp1, nbits);
 619                 bitmap_from_arr32(bmap2, arr, nbits);
 620                 expect_eq_bitmap(bmap2, exp1, nbits);
 621
 622                 next_bit = find_next_bit(bmap2,
 623                                 round_up(nbits, BITS_PER_LONG), nbits);
 624                 if (next_bit < round_up(nbits, BITS_PER_LONG)) {
 625                         pr_err("bitmap_copy_arr32(nbits == %d:"
 626                                 " tail is not safely cleared: %d\n",
 627                                 nbits, next_bit);
 628                         failed_tests++;
 629                 }
 630
 631                 if (nbits < EXP1_IN_BITS - 32)
 632                         expect_eq_uint(arr[DIV_ROUND_UP(nbits, 32)],
 633                                                                 0xa5a5a5a5);
 634         }
 635 }
 636
 637 static void __init test_bitmap_arr64(void)
 638 {
 639         unsigned int nbits, next_bit;
 640         u64 arr[EXP1_IN_BITS / 64];
 641         DECLARE_BITMAP(bmap2, EXP1_IN_BITS);
 642
 643         memset(arr, 0xa5, sizeof(arr));
 644
 645         for (nbits = 0; nbits < EXP1_IN_BITS; ++nbits) {
 646                 memset(bmap2, 0xff, sizeof(arr));
 647                 bitmap_to_arr64(arr, exp1, nbits);
 648                 bitmap_from_arr64(bmap2, arr, nbits);
 649                 expect_eq_bitmap(bmap2, exp1, nbits);
 650
 651                 next_bit = find_next_bit(bmap2, round_up(nbits, BITS_PER_LONG), nbits);
 652                 if (next_bit < round_up(nbits, BITS_PER_LONG)) {
 653                         pr_err("bitmap_copy_arr64(nbits == %d:"
 654                                 " tail is not safely cleared: %d\n", nbits, next_bit);
 655                         failed_tests++;
 656                 }
 657
 658                 if ((nbits % 64) &&
 659                     (arr[(nbits - 1) / 64] & ~GENMASK_ULL((nbits - 1) % 64, 0))) {
 660                         pr_err("bitmap_to_arr64(nbits == %d): tail is not safely cleared: 0x%016llx (must be 0x%016llx)\n",
 661                                nbits, arr[(nbits - 1) / 64],
 662                                GENMASK_ULL((nbits - 1) % 64, 0));
 663                         failed_tests++;
 664                 }
 665
 666                 if (nbits < EXP1_IN_BITS - 64)
 667                         expect_eq_uint(arr[DIV_ROUND_UP(nbits, 64)], 0xa5a5a5a5);
 668         }
 669 }
 670
 671 static void noinline __init test_mem_optimisations(void)
 672 {
 673         DECLARE_BITMAP(bmap1, 1024);
 674         DECLARE_BITMAP(bmap2, 1024);
 675         unsigned int start, nbits;
 676
 677         for (start = 0; start < 1024; start += 8) {
 678                 for (nbits = 0; nbits < 1024 - start; nbits += 8) {
 679                         memset(bmap1, 0x5a, sizeof(bmap1));
 680                         memset(bmap2, 0x5a, sizeof(bmap2));
 681
 682                         bitmap_set(bmap1, start, nbits);
 683                         __bitmap_set(bmap2, start, nbits);
 684                         if (!bitmap_equal(bmap1, bmap2, 1024)) {
 685                                 printk("set not equal %d %d\n", start, nbits);
 686                                 failed_tests++;
 687                         }
 688                         if (!__bitmap_equal(bmap1, bmap2, 1024)) {
 689                                 printk("set not __equal %d %d\n", start, nbits);
 690                                 failed_tests++;
 691                         }
 692
 693                         bitmap_clear(bmap1, start, nbits);
 694                         __bitmap_clear(bmap2, start, nbits);
 695                         if (!bitmap_equal(bmap1, bmap2, 1024)) {
 696                                 printk("clear not equal %d %d\n", start, nbits);
 697                                 failed_tests++;
 698                         }
 699                         if (!__bitmap_equal(bmap1, bmap2, 1024)) {
 700                                 printk("clear not __equal %d %d\n", start,
 701                                                                         nbits);
 702                                 failed_tests++;
 703                         }
 704                 }
 705         }
 706 }
 707
 708 static const unsigned char clump_exp[] __initconst = {
 709         0x01,   /* 1 bit set */
 710         0x02,   /* non-edge 1 bit set */
 711         0x00,   /* zero bits set */
 712         0x38,   /* 3 bits set across 4-bit boundary */
 713         0x38,   /* Repeated clump */
 714         0x0F,   /* 4 bits set */
 715         0xFF,   /* all bits set */
 716         0x05,   /* non-adjacent 2 bits set */
 717 };
 718
 719 static void __init test_for_each_set_clump8(void)
 720 {
 721 #define CLUMP_EXP_NUMBITS 64
 722         DECLARE_BITMAP(bits, CLUMP_EXP_NUMBITS);
 723         unsigned int start;
 724         unsigned long clump;
 725
 726         /* set bitmap to test case */
 727         bitmap_zero(bits, CLUMP_EXP_NUMBITS);
 728         bitmap_set(bits, 0, 1);         /* 0x01 */
 729         bitmap_set(bits, 9, 1);         /* 0x02 */
 730         bitmap_set(bits, 27, 3);        /* 0x28 */
 731         bitmap_set(bits, 35, 3);        /* 0x28 */
 732         bitmap_set(bits, 40, 4);        /* 0x0F */
 733         bitmap_set(bits, 48, 8);        /* 0xFF */
 734         bitmap_set(bits, 56, 1);        /* 0x05 - part 1 */
 735         bitmap_set(bits, 58, 1);        /* 0x05 - part 2 */
 736
 737         for_each_set_clump8(start, clump, bits, CLUMP_EXP_NUMBITS)
 738                 expect_eq_clump8(start, CLUMP_EXP_NUMBITS, clump_exp, &clump);
 739 }
 740
 741 static void __init test_for_each_set_bit_wrap(void)
 742 {
 743         DECLARE_BITMAP(orig, 500);
 744         DECLARE_BITMAP(copy, 500);
 745         unsigned int wr, bit;
 746
 747         bitmap_zero(orig, 500);
 748
 749         /* Set individual bits */
 750         for (bit = 0; bit < 500; bit += 10)
 751                 bitmap_set(orig, bit, 1);
 752
 753         /* Set range of bits */
 754         bitmap_set(orig, 100, 50);
 755
 756         for (wr = 0; wr < 500; wr++) {
 757                 bitmap_zero(copy, 500);
 758
 759                 for_each_set_bit_wrap(bit, orig, 500, wr)
 760                         bitmap_set(copy, bit, 1);
 761
 762                 expect_eq_bitmap(orig, copy, 500);
 763         }
 764 }
 765
 766 static void __init test_for_each_set_bit(void)
 767 {
 768         DECLARE_BITMAP(orig, 500);
 769         DECLARE_BITMAP(copy, 500);
 770         unsigned int bit;
 771
 772         bitmap_zero(orig, 500);
 773         bitmap_zero(copy, 500);
 774
 775         /* Set individual bits */
 776         for (bit = 0; bit < 500; bit += 10)
 777                 bitmap_set(orig, bit, 1);
 778
 779         /* Set range of bits */
 780         bitmap_set(orig, 100, 50);
 781
 782         for_each_set_bit(bit, orig, 500)
 783                 bitmap_set(copy, bit, 1);
 784
 785         expect_eq_bitmap(orig, copy, 500);
 786 }
 787
 788 static void __init test_for_each_set_bit_from(void)
 789 {
 790         DECLARE_BITMAP(orig, 500);
 791         DECLARE_BITMAP(copy, 500);
 792         unsigned int wr, bit;
 793
 794         bitmap_zero(orig, 500);
 795
 796         /* Set individual bits */
 797         for (bit = 0; bit < 500; bit += 10)
 798                 bitmap_set(orig, bit, 1);
 799
 800         /* Set range of bits */
 801         bitmap_set(orig, 100, 50);
 802
 803         for (wr = 0; wr < 500; wr++) {
 804                 DECLARE_BITMAP(tmp, 500);
 805
 806                 bitmap_zero(copy, 500);
 807                 bit = wr;
 808
 809                 for_each_set_bit_from(bit, orig, 500)
 810                         bitmap_set(copy, bit, 1);
 811
 812                 bitmap_copy(tmp, orig, 500);
 813                 bitmap_clear(tmp, 0, wr);
 814                 expect_eq_bitmap(tmp, copy, 500);
 815         }
 816 }
 817
 818 static void __init test_for_each_clear_bit(void)
 819 {
 820         DECLARE_BITMAP(orig, 500);
 821         DECLARE_BITMAP(copy, 500);
 822         unsigned int bit;
 823
 824         bitmap_fill(orig, 500);
 825         bitmap_fill(copy, 500);
 826
 827         /* Set individual bits */
 828         for (bit = 0; bit < 500; bit += 10)
 829                 bitmap_clear(orig, bit, 1);
 830
 831         /* Set range of bits */
 832         bitmap_clear(orig, 100, 50);
 833
 834         for_each_clear_bit(bit, orig, 500)
 835                 bitmap_clear(copy, bit, 1);
 836
 837         expect_eq_bitmap(orig, copy, 500);
 838 }
 839
 840 static void __init test_for_each_clear_bit_from(void)
 841 {
 842         DECLARE_BITMAP(orig, 500);
 843         DECLARE_BITMAP(copy, 500);
 844         unsigned int wr, bit;
 845
 846         bitmap_fill(orig, 500);
 847
 848         /* Set individual bits */
 849         for (bit = 0; bit < 500; bit += 10)
 850                 bitmap_clear(orig, bit, 1);
 851
 852         /* Set range of bits */
 853         bitmap_clear(orig, 100, 50);
 854
 855         for (wr = 0; wr < 500; wr++) {
 856                 DECLARE_BITMAP(tmp, 500);
 857
 858                 bitmap_fill(copy, 500);
 859                 bit = wr;
 860
 861                 for_each_clear_bit_from(bit, orig, 500)
 862                         bitmap_clear(copy, bit, 1);
 863
 864                 bitmap_copy(tmp, orig, 500);
 865                 bitmap_set(tmp, 0, wr);
 866                 expect_eq_bitmap(tmp, copy, 500);
 867         }
 868 }
 869
 870 static void __init test_for_each_set_bitrange(void)
 871 {
 872         DECLARE_BITMAP(orig, 500);
 873         DECLARE_BITMAP(copy, 500);
 874         unsigned int s, e;
 875
 876         bitmap_zero(orig, 500);
 877         bitmap_zero(copy, 500);
 878
 879         /* Set individual bits */
 880         for (s = 0; s < 500; s += 10)
 881                 bitmap_set(orig, s, 1);
 882
 883         /* Set range of bits */
 884         bitmap_set(orig, 100, 50);
 885
 886         for_each_set_bitrange(s, e, orig, 500)
 887                 bitmap_set(copy, s, e-s);
 888
 889         expect_eq_bitmap(orig, copy, 500);
 890 }
 891
 892 static void __init test_for_each_clear_bitrange(void)
 893 {
 894         DECLARE_BITMAP(orig, 500);
 895         DECLARE_BITMAP(copy, 500);
 896         unsigned int s, e;
 897
 898         bitmap_fill(orig, 500);
 899         bitmap_fill(copy, 500);
 900
 901         /* Set individual bits */
 902         for (s = 0; s < 500; s += 10)
 903                 bitmap_clear(orig, s, 1);
 904
 905         /* Set range of bits */
 906         bitmap_clear(orig, 100, 50);
 907
 908         for_each_clear_bitrange(s, e, orig, 500)
 909                 bitmap_clear(copy, s, e-s);
 910
 911         expect_eq_bitmap(orig, copy, 500);
 912 }
 913
 914 static void __init test_for_each_set_bitrange_from(void)
 915 {
 916         DECLARE_BITMAP(orig, 500);
 917         DECLARE_BITMAP(copy, 500);
 918         unsigned int wr, s, e;
 919
 920         bitmap_zero(orig, 500);
 921
 922         /* Set individual bits */
 923         for (s = 0; s < 500; s += 10)
 924                 bitmap_set(orig, s, 1);
 925
 926         /* Set range of bits */
 927         bitmap_set(orig, 100, 50);
 928
 929         for (wr = 0; wr < 500; wr++) {
 930                 DECLARE_BITMAP(tmp, 500);
 931
 932                 bitmap_zero(copy, 500);
 933                 s = wr;
 934
 935                 for_each_set_bitrange_from(s, e, orig, 500)
 936                         bitmap_set(copy, s, e - s);
 937
 938                 bitmap_copy(tmp, orig, 500);
 939                 bitmap_clear(tmp, 0, wr);
 940                 expect_eq_bitmap(tmp, copy, 500);
 941         }
 942 }
 943
 944 static void __init test_for_each_clear_bitrange_from(void)
 945 {
 946         DECLARE_BITMAP(orig, 500);
 947         DECLARE_BITMAP(copy, 500);
 948         unsigned int wr, s, e;
 949
 950         bitmap_fill(orig, 500);
 951
 952         /* Set individual bits */
 953         for (s = 0; s < 500; s += 10)
 954                 bitmap_clear(orig, s, 1);
 955
 956         /* Set range of bits */
 957         bitmap_set(orig, 100, 50);
 958
 959         for (wr = 0; wr < 500; wr++) {
 960                 DECLARE_BITMAP(tmp, 500);
 961
 962                 bitmap_fill(copy, 500);
 963                 s = wr;
 964
 965                 for_each_clear_bitrange_from(s, e, orig, 500)
 966                         bitmap_clear(copy, s, e - s);
 967
 968                 bitmap_copy(tmp, orig, 500);
 969                 bitmap_set(tmp, 0, wr);
 970                 expect_eq_bitmap(tmp, copy, 500);
 971         }
 972 }
 973
 974 struct test_bitmap_cut {
 975         unsigned int first;
 976         unsigned int cut;
 977         unsigned int nbits;
 978         unsigned long in[4];
 979         unsigned long expected[4];
 980 };
 981
 982 static struct test_bitmap_cut test_cut[] = {
 983         {  0,  0,  8, { 0x0000000aUL, }, { 0x0000000aUL, }, },
 984         {  0,  0, 32, { 0xdadadeadUL, }, { 0xdadadeadUL, }, },
 985         {  0,  3,  8, { 0x000000aaUL, }, { 0x00000015UL, }, },
 986         {  3,  3,  8, { 0x000000aaUL, }, { 0x00000012UL, }, },
 987         {  0,  1, 32, { 0xa5a5a5a5UL, }, { 0x52d2d2d2UL, }, },
 988         {  0,  8, 32, { 0xdeadc0deUL, }, { 0x00deadc0UL, }, },
 989         {  1,  1, 32, { 0x5a5a5a5aUL, }, { 0x2d2d2d2cUL, }, },
 990         {  0, 15, 32, { 0xa5a5a5a5UL, }, { 0x00014b4bUL, }, },
 991         {  0, 16, 32, { 0xa5a5a5a5UL, }, { 0x0000a5a5UL, }, },
 992         { 15, 15, 32, { 0xa5a5a5a5UL, }, { 0x000125a5UL, }, },
 993         { 15, 16, 32, { 0xa5a5a5a5UL, }, { 0x0000a5a5UL, }, },
 994         { 16, 15, 32, { 0xa5a5a5a5UL, }, { 0x0001a5a5UL, }, },
 995
 996         { BITS_PER_LONG, BITS_PER_LONG, BITS_PER_LONG,
 997                 { 0xa5a5a5a5UL, 0xa5a5a5a5UL, },
 998                 { 0xa5a5a5a5UL, 0xa5a5a5a5UL, },
 999         },
1000         { 1, BITS_PER_LONG - 1, BITS_PER_LONG,
1001                 { 0xa5a5a5a5UL, 0xa5a5a5a5UL, },
1002                 { 0x00000001UL, 0x00000001UL, },
1003         },
1004
1005         { 0, BITS_PER_LONG * 2, BITS_PER_LONG * 2 + 1,
1006                 { 0xa5a5a5a5UL, 0x00000001UL, 0x00000001UL, 0x00000001UL },
1007                 { 0x00000001UL, },
1008         },
1009         { 16, BITS_PER_LONG * 2 + 1, BITS_PER_LONG * 2 + 1 + 16,
1010                 { 0x0000ffffUL, 0x5a5a5a5aUL, 0x5a5a5a5aUL, 0x5a5a5a5aUL },
1011                 { 0x2d2dffffUL, },
1012         },
1013 };
1014
1015 static void __init test_bitmap_cut(void)
1016 {
1017         unsigned long b[5], *in = &b[1], *out = &b[0];  /* Partial overlap */
1018         int i;
1019
1020         for (i = 0; i < ARRAY_SIZE(test_cut); i++) {
1021                 struct test_bitmap_cut *t = &test_cut[i];
1022
1023                 memcpy(in, t->in, sizeof(t->in));
1024
1025                 bitmap_cut(out, in, t->first, t->cut, t->nbits);
1026
1027                 expect_eq_bitmap(t->expected, out, t->nbits);
1028         }
1029 }
1030
1031 struct test_bitmap_print {
1032         const unsigned long *bitmap;
1033         unsigned long nbits;
1034         const char *mask;
1035         const char *list;
1036 };
1037
1038 static const unsigned long small_bitmap[] __initconst = {
1039         BITMAP_FROM_U64(0x3333333311111111ULL),
1040 };
1041
1042 static const char small_mask[] __initconst = "33333333,11111111\n";
1043 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";
1044
1045 static const unsigned long large_bitmap[] __initconst = {
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         BITMAP_FROM_U64(0x3333333311111111ULL), BITMAP_FROM_U64(0x3333333311111111ULL),
1055         BITMAP_FROM_U64(0x3333333311111111ULL), BITMAP_FROM_U64(0x3333333311111111ULL),
1056         BITMAP_FROM_U64(0x3333333311111111ULL), BITMAP_FROM_U64(0x3333333311111111ULL),
1057         BITMAP_FROM_U64(0x3333333311111111ULL), BITMAP_FROM_U64(0x3333333311111111ULL),
1058         BITMAP_FROM_U64(0x3333333311111111ULL), BITMAP_FROM_U64(0x3333333311111111ULL),
1059         BITMAP_FROM_U64(0x3333333311111111ULL), BITMAP_FROM_U64(0x3333333311111111ULL),
1060         BITMAP_FROM_U64(0x3333333311111111ULL), BITMAP_FROM_U64(0x3333333311111111ULL),
1061         BITMAP_FROM_U64(0x3333333311111111ULL), BITMAP_FROM_U64(0x3333333311111111ULL),
1062         BITMAP_FROM_U64(0x3333333311111111ULL), BITMAP_FROM_U64(0x3333333311111111ULL),
1063         BITMAP_FROM_U64(0x3333333311111111ULL), BITMAP_FROM_U64(0x3333333311111111ULL),
1064         BITMAP_FROM_U64(0x3333333311111111ULL), BITMAP_FROM_U64(0x3333333311111111ULL),
1065         BITMAP_FROM_U64(0x3333333311111111ULL), BITMAP_FROM_U64(0x3333333311111111ULL),
1066 };
1067
1068 static const char large_mask[] __initconst = "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,"
1076                                         "33333333,11111111,33333333,11111111,"
1077                                         "33333333,11111111,33333333,11111111,"
1078                                         "33333333,11111111,33333333,11111111,"
1079                                         "33333333,11111111,33333333,11111111,"
1080                                         "33333333,11111111,33333333,11111111,"
1081                                         "33333333,11111111,33333333,11111111,"
1082                                         "33333333,11111111,33333333,11111111,"
1083                                         "33333333,11111111,33333333,11111111,"
1084                                         "33333333,11111111,33333333,11111111,"
1085                                         "33333333,11111111,33333333,11111111,"
1086                                         "33333333,11111111,33333333,11111111,"
1087                                         "33333333,11111111,33333333,11111111\n";
1088
1089 static const char large_list[] __initconst = /* more than 4KB */
1090         "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"
1091         "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"
1092         "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"
1093         "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"
1094         "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"
1095         "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"
1096         "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"
1097         "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"
1098         "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"
1099         "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"
1100         "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"
1101         "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"
1102         "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-"
1103         "1001,1004-1005,1008-1009,1012-1013,1016-1017,1020-1021,1024,1028,1032,1036,1040,1044,1048,1052,1056-1057,1060-10"
1104         "61,1064-1065,1068-1069,1072-1073,1076-1077,1080-1081,1084-1085,1088,1092,1096,1100,1104,1108,1112,1116,1120-1121"
1105         ",1124-1125,1128-1129,1132-1133,1136-1137,1140-1141,1144-1145,1148-1149,1152,1156,1160,1164,1168,1172,1176,1180,1"
1106         "184-1185,1188-1189,1192-1193,1196-1197,1200-1201,1204-1205,1208-1209,1212-1213,1216,1220,1224,1228,1232,1236,124"
1107         "0,1244,1248-1249,1252-1253,1256-1257,1260-1261,1264-1265,1268-1269,1272-1273,1276-1277,1280,1284,1288,1292,1296,"
1108         "1300,1304,1308,1312-1313,1316-1317,1320-1321,1324-1325,1328-1329,1332-1333,1336-1337,1340-1341,1344,1348,1352,13"
1109         "56,1360,1364,1368,1372,1376-1377,1380-1381,1384-1385,1388-1389,1392-1393,1396-1397,1400-1401,1404-1405,1408,1412"
1110         ",1416,1420,1424,1428,1432,1436,1440-1441,1444-1445,1448-1449,1452-1453,1456-1457,1460-1461,1464-1465,1468-1469,1"
1111         "472,1476,1480,1484,1488,1492,1496,1500,1504-1505,1508-1509,1512-1513,1516-1517,1520-1521,1524-1525,1528-1529,153"
1112         "2-1533,1536,1540,1544,1548,1552,1556,1560,1564,1568-1569,1572-1573,1576-1577,1580-1581,1584-1585,1588-1589,1592-"
1113         "1593,1596-1597,1600,1604,1608,1612,1616,1620,1624,1628,1632-1633,1636-1637,1640-1641,1644-1645,1648-1649,1652-16"
1114         "53,1656-1657,1660-1661,1664,1668,1672,1676,1680,1684,1688,1692,1696-1697,1700-1701,1704-1705,1708-1709,1712-1713"
1115         ",1716-1717,1720-1721,1724-1725,1728,1732,1736,1740,1744,1748,1752,1756,1760-1761,1764-1765,1768-1769,1772-1773,1"
1116         "776-1777,1780-1781,1784-1785,1788-1789,1792,1796,1800,1804,1808,1812,1816,1820,1824-1825,1828-1829,1832-1833,183"
1117         "6-1837,1840-1841,1844-1845,1848-1849,1852-1853,1856,1860,1864,1868,1872,1876,1880,1884,1888-1889,1892-1893,1896-"
1118         "1897,1900-1901,1904-1905,1908-1909,1912-1913,1916-1917,1920,1924,1928,1932,1936,1940,1944,1948,1952-1953,1956-19"
1119         "57,1960-1961,1964-1965,1968-1969,1972-1973,1976-1977,1980-1981,1984,1988,1992,1996,2000,2004,2008,2012,2016-2017"
1120         ",2020-2021,2024-2025,2028-2029,2032-2033,2036-2037,2040-2041,2044-2045,2048,2052,2056,2060,2064,2068,2072,2076,2"
1121         "080-2081,2084-2085,2088-2089,2092-2093,2096-2097,2100-2101,2104-2105,2108-2109,2112,2116,2120,2124,2128,2132,213"
1122         "6,2140,2144-2145,2148-2149,2152-2153,2156-2157,2160-2161,2164-2165,2168-2169,2172-2173,2176,2180,2184,2188,2192,"
1123         "2196,2200,2204,2208-2209,2212-2213,2216-2217,2220-2221,2224-2225,2228-2229,2232-2233,2236-2237,2240,2244,2248,22"
1124         "52,2256,2260,2264,2268,2272-2273,2276-2277,2280-2281,2284-2285,2288-2289,2292-2293,2296-2297,2300-2301,2304,2308"
1125         ",2312,2316,2320,2324,2328,2332,2336-2337,2340-2341,2344-2345,2348-2349,2352-2353,2356-2357,2360-2361,2364-2365,2"
1126         "368,2372,2376,2380,2384,2388,2392,2396,2400-2401,2404-2405,2408-2409,2412-2413,2416-2417,2420-2421,2424-2425,242"
1127         "8-2429,2432,2436,2440,2444,2448,2452,2456,2460,2464-2465,2468-2469,2472-2473,2476-2477,2480-2481,2484-2485,2488-"
1128         "2489,2492-2493,2496,2500,2504,2508,2512,2516,2520,2524,2528-2529,2532-2533,2536-2537,2540-2541,2544-2545,2548-25"
1129         "49,2552-2553,2556-2557\n";
1130
1131 static const struct test_bitmap_print test_print[] __initconst = {
1132         { small_bitmap, sizeof(small_bitmap) * BITS_PER_BYTE, small_mask, small_list },
1133         { large_bitmap, sizeof(large_bitmap) * BITS_PER_BYTE, large_mask, large_list },
1134 };
1135
1136 static void __init test_bitmap_print_buf(void)
1137 {
1138         int i;
1139
1140         for (i = 0; i < ARRAY_SIZE(test_print); i++) {
1141                 const struct test_bitmap_print *t = &test_print[i];
1142                 int n;
1143
1144                 n = bitmap_print_bitmask_to_buf(print_buf, t->bitmap, t->nbits,
1145                                                 0, 2 * PAGE_SIZE);
1146                 expect_eq_uint(strlen(t->mask) + 1, n);
1147                 expect_eq_str(t->mask, print_buf, n);
1148
1149                 n = bitmap_print_list_to_buf(print_buf, t->bitmap, t->nbits,
1150                                              0, 2 * PAGE_SIZE);
1151                 expect_eq_uint(strlen(t->list) + 1, n);
1152                 expect_eq_str(t->list, print_buf, n);
1153
1154                 /* test by non-zero offset */
1155                 if (strlen(t->list) > PAGE_SIZE) {
1156                         n = bitmap_print_list_to_buf(print_buf, t->bitmap, t->nbits,
1157                                                      PAGE_SIZE, PAGE_SIZE);
1158                         expect_eq_uint(strlen(t->list) + 1 - PAGE_SIZE, n);
1159                         expect_eq_str(t->list + PAGE_SIZE, print_buf, n);
1160                 }
1161         }
1162 }
1163
1164 /*
1165  * FIXME: Clang breaks compile-time evaluations when KASAN and GCOV are enabled.
1166  * To workaround it, GCOV is force-disabled in Makefile for this configuration.
1167  */
1168 static void __init test_bitmap_const_eval(void)
1169 {
1170         DECLARE_BITMAP(bitmap, BITS_PER_LONG);
1171         unsigned long initvar = BIT(2);
1172         unsigned long bitopvar = 0;
1173         unsigned long var = 0;
1174         int res;
1175
1176         /*
1177          * Compilers must be able to optimize all of those to compile-time
1178          * constants on any supported optimization level (-O2, -Os) and any
1179          * architecture. Otherwise, trigger a build bug.
1180          * The whole function gets optimized out then, there's nothing to do
1181          * in runtime.
1182          */
1183
1184         /*
1185          * Equals to `unsigned long bitmap[1] = { GENMASK(6, 5), }`.
1186          * Clang on s390 optimizes bitops at compile-time as intended, but at
1187          * the same time stops treating @bitmap and @bitopvar as compile-time
1188          * constants after regular test_bit() is executed, thus triggering the
1189          * build bugs below. So, call const_test_bit() there directly until
1190          * the compiler is fixed.
1191          */
1192         bitmap_clear(bitmap, 0, BITS_PER_LONG);
1193         if (!test_bit(7, bitmap))
1194                 bitmap_set(bitmap, 5, 2);
1195
1196         /* Equals to `unsigned long bitopvar = BIT(20)` */
1197         __change_bit(31, &bitopvar);
1198         bitmap_shift_right(&bitopvar, &bitopvar, 11, BITS_PER_LONG);
1199
1200         /* Equals to `unsigned long var = BIT(25)` */
1201         var |= BIT(25);
1202         if (var & BIT(0))
1203                 var ^= GENMASK(9, 6);
1204
1205         /* __const_hweight<32|64>(GENMASK(6, 5)) == 2 */
1206         res = bitmap_weight(bitmap, 20);
1207         BUILD_BUG_ON(!__builtin_constant_p(res));
1208         BUILD_BUG_ON(res != 2);
1209
1210         /* !(BIT(31) & BIT(18)) == 1 */
1211         res = !test_bit(18, &bitopvar);
1212         BUILD_BUG_ON(!__builtin_constant_p(res));
1213         BUILD_BUG_ON(!res);
1214
1215         /* BIT(2) & GENMASK(14, 8) == 0 */
1216         res = initvar & GENMASK(14, 8);
1217         BUILD_BUG_ON(!__builtin_constant_p(res));
1218         BUILD_BUG_ON(res);
1219
1220         /* ~BIT(25) */
1221         BUILD_BUG_ON(!__builtin_constant_p(~var));
1222         BUILD_BUG_ON(~var != ~BIT(25));
1223 }
1224
1225 static void __init selftest(void)
1226 {
1227         test_zero_clear();
1228         test_fill_set();
1229         test_copy();
1230         test_replace();
1231         test_bitmap_arr32();
1232         test_bitmap_arr64();
1233         test_bitmap_parse();
1234         test_bitmap_parselist();
1235         test_bitmap_printlist();
1236         test_mem_optimisations();
1237         test_bitmap_cut();
1238         test_bitmap_print_buf();
1239         test_bitmap_const_eval();
1240
1241         test_find_nth_bit();
1242         test_for_each_set_bit();
1243         test_for_each_set_bit_from();
1244         test_for_each_clear_bit();
1245         test_for_each_clear_bit_from();
1246         test_for_each_set_bitrange();
1247         test_for_each_clear_bitrange();
1248         test_for_each_set_bitrange_from();
1249         test_for_each_clear_bitrange_from();
1250         test_for_each_set_clump8();
1251         test_for_each_set_bit_wrap();
1252 }
1253
1254 KSTM_MODULE_LOADERS(test_bitmap);
1255 MODULE_AUTHOR("david decotigny <david.decotigny@googlers.com>");
1256 MODULE_LICENSE("GPL");