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