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