lib/test_bitmap.c

   1 // SPDX-License-Identifier: GPL-2.0-only
   2 /*
   3  * Test cases for bitmap API.
   4  */
   5
   6 #define pr_fmt(fmt) KBUILD_MODNAME ": " fmt
   7
   8 #include <linux/bitmap.h>
   9 #include <linux/init.h>
  10 #include <linux/kernel.h>
  11 #include <linux/module.h>
  12 #include <linux/printk.h>
  13 #include <linux/slab.h>
  14 #include <linux/string.h>
  15 #include <linux/uaccess.h>
  16
  17 #include "../tools/testing/selftests/kselftest_module.h"
  18
  19 KSTM_MODULE_GLOBALS();
  20
  21 static char pbl_buffer[PAGE_SIZE] __initdata;
  22 static char print_buf[PAGE_SIZE * 2] __initdata;
  23
  24 static const unsigned long exp1[] __initconst = {
  25         BITMAP_FROM_U64(1),
  26         BITMAP_FROM_U64(2),
  27         BITMAP_FROM_U64(0x0000ffff),
  28         BITMAP_FROM_U64(0xffff0000),
  29         BITMAP_FROM_U64(0x55555555),
  30         BITMAP_FROM_U64(0xaaaaaaaa),
  31         BITMAP_FROM_U64(0x11111111),
  32         BITMAP_FROM_U64(0x22222222),
  33         BITMAP_FROM_U64(0xffffffff),
  34         BITMAP_FROM_U64(0xfffffffe),
  35         BITMAP_FROM_U64(0x3333333311111111ULL),
  36         BITMAP_FROM_U64(0xffffffff77777777ULL),
  37         BITMAP_FROM_U64(0),
  38         BITMAP_FROM_U64(0x00008000),
  39         BITMAP_FROM_U64(0x80000000),
  40 };
  41
  42 static const unsigned long exp2[] __initconst = {
  43         BITMAP_FROM_U64(0x3333333311111111ULL),
  44         BITMAP_FROM_U64(0xffffffff77777777ULL),
  45 };
  46
  47 /* Fibonacci sequence */
  48 static const unsigned long exp2_to_exp3_mask[] __initconst = {
  49         BITMAP_FROM_U64(0x008000020020212eULL),
  50 };
  51 /* exp3_0_1 = (exp2[0] & ~exp2_to_exp3_mask) | (exp2[1] & exp2_to_exp3_mask) */
  52 static const unsigned long exp3_0_1[] __initconst = {
  53         BITMAP_FROM_U64(0x33b3333311313137ULL),
  54 };
  55 /* exp3_1_0 = (exp2[1] & ~exp2_to_exp3_mask) | (exp2[0] & exp2_to_exp3_mask) */
  56 static const unsigned long exp3_1_0[] __initconst = {
  57         BITMAP_FROM_U64(0xff7fffff77575751ULL),
  58 };
  59
  60 static bool __init
  61 __check_eq_uint(const char *srcfile, unsigned int line,
  62                 const unsigned int exp_uint, unsigned int x)
  63 {
  64         if (exp_uint != x) {
  65                 pr_err("[%s:%u] expected %u, got %u\n",
  66                         srcfile, line, exp_uint, x);
  67                 return false;
  68         }
  69         return true;
  70 }
  71
  72
  73 static bool __init
  74 __check_eq_bitmap(const char *srcfile, unsigned int line,
  75                   const unsigned long *exp_bmap, const unsigned long *bmap,
  76                   unsigned int nbits)
  77 {
  78         if (!bitmap_equal(exp_bmap, bmap, nbits)) {
  79                 pr_warn("[%s:%u] bitmaps contents differ: expected \"%*pbl\", got \"%*pbl\"\n",
  80                         srcfile, line,
  81                         nbits, exp_bmap, nbits, bmap);
  82                 return false;
  83         }
  84         return true;
  85 }
  86
  87 static bool __init
  88 __check_eq_pbl(const char *srcfile, unsigned int line,
  89                const char *expected_pbl,
  90                const unsigned long *bitmap, unsigned int nbits)
  91 {
  92         snprintf(pbl_buffer, sizeof(pbl_buffer), "%*pbl", nbits, bitmap);
  93         if (strcmp(expected_pbl, pbl_buffer)) {
  94                 pr_warn("[%s:%u] expected \"%s\", got \"%s\"\n",
  95                         srcfile, line,
  96                         expected_pbl, pbl_buffer);
  97                 return false;
  98         }
  99         return true;
 100 }
 101
 102 static bool __init
 103 __check_eq_u32_array(const char *srcfile, unsigned int line,
 104                      const u32 *exp_arr, unsigned int exp_len,
 105                      const u32 *arr, unsigned int len) __used;
 106 static bool __init
 107 __check_eq_u32_array(const char *srcfile, unsigned int line,
 108                      const u32 *exp_arr, unsigned int exp_len,
 109                      const u32 *arr, unsigned int len)
 110 {
 111         if (exp_len != len) {
 112                 pr_warn("[%s:%u] array length differ: expected %u, got %u\n",
 113                         srcfile, line,
 114                         exp_len, len);
 115                 return false;
 116         }
 117
 118         if (memcmp(exp_arr, arr, len*sizeof(*arr))) {
 119                 pr_warn("[%s:%u] array contents differ\n", srcfile, line);
 120                 print_hex_dump(KERN_WARNING, "  exp:  ", DUMP_PREFIX_OFFSET,
 121                                32, 4, exp_arr, exp_len*sizeof(*exp_arr), false);
 122                 print_hex_dump(KERN_WARNING, "  got:  ", DUMP_PREFIX_OFFSET,
 123                                32, 4, arr, len*sizeof(*arr), false);
 124                 return false;
 125         }
 126
 127         return true;
 128 }
 129
 130 static bool __init __check_eq_clump8(const char *srcfile, unsigned int line,
 131                                     const unsigned int offset,
 132                                     const unsigned int size,
 133                                     const unsigned char *const clump_exp,
 134                                     const unsigned long *const clump)
 135 {
 136         unsigned long exp;
 137
 138         if (offset >= size) {
 139                 pr_warn("[%s:%u] bit offset for clump out-of-bounds: expected less than %u, got %u\n",
 140                         srcfile, line, size, offset);
 141                 return false;
 142         }
 143
 144         exp = clump_exp[offset / 8];
 145         if (!exp) {
 146                 pr_warn("[%s:%u] bit offset for zero clump: expected nonzero clump, got bit offset %u with clump value 0",
 147                         srcfile, line, offset);
 148                 return false;
 149         }
 150
 151         if (*clump != exp) {
 152                 pr_warn("[%s:%u] expected clump value of 0x%lX, got clump value of 0x%lX",
 153                         srcfile, line, exp, *clump);
 154                 return false;
 155         }
 156
 157         return true;
 158 }
 159
 160 static bool __init
 161 __check_eq_str(const char *srcfile, unsigned int line,
 162                 const char *exp_str, const char *str,
 163                 unsigned int len)
 164 {
 165         bool eq;
 166
 167         eq = strncmp(exp_str, str, len) == 0;
 168         if (!eq)
 169                 pr_err("[%s:%u] expected %s, got %s\n", srcfile, line, exp_str, str);
 170
 171         return eq;
 172 }
 173
 174 #define __expect_eq(suffix, ...)                                        \
 175         ({                                                              \
 176                 int result = 0;                                         \
 177                 total_tests++;                                          \
 178                 if (!__check_eq_ ## suffix(__FILE__, __LINE__,          \
 179                                            ##__VA_ARGS__)) {            \
 180                         failed_tests++;                                 \
 181                         result = 1;                                     \
 182                 }                                                       \
 183                 result;                                                 \
 184         })
 185
 186 #define expect_eq_uint(...)             __expect_eq(uint, ##__VA_ARGS__)
 187 #define expect_eq_bitmap(...)           __expect_eq(bitmap, ##__VA_ARGS__)
 188 #define expect_eq_pbl(...)              __expect_eq(pbl, ##__VA_ARGS__)
 189 #define expect_eq_u32_array(...)        __expect_eq(u32_array, ##__VA_ARGS__)
 190 #define expect_eq_clump8(...)           __expect_eq(clump8, ##__VA_ARGS__)
 191 #define expect_eq_str(...)              __expect_eq(str, ##__VA_ARGS__)
 192
 193 static void __init test_zero_clear(void)
 194 {
 195         DECLARE_BITMAP(bmap, 1024);
 196
 197         /* Known way to set all bits */
 198         memset(bmap, 0xff, 128);
 199
 200         expect_eq_pbl("0-22", bmap, 23);
 201         expect_eq_pbl("0-1023", bmap, 1024);
 202
 203         /* single-word bitmaps */
 204         bitmap_clear(bmap, 0, 9);
 205         expect_eq_pbl("9-1023", bmap, 1024);
 206
 207         bitmap_zero(bmap, 35);
 208         expect_eq_pbl("64-1023", bmap, 1024);
 209
 210         /* cross boundaries operations */
 211         bitmap_clear(bmap, 79, 19);
 212         expect_eq_pbl("64-78,98-1023", bmap, 1024);
 213
 214         bitmap_zero(bmap, 115);
 215         expect_eq_pbl("128-1023", bmap, 1024);
 216
 217         /* Zeroing entire area */
 218         bitmap_zero(bmap, 1024);
 219         expect_eq_pbl("", bmap, 1024);
 220 }
 221
 222 static void __init test_fill_set(void)
 223 {
 224         DECLARE_BITMAP(bmap, 1024);
 225
 226         /* Known way to clear all bits */
 227         memset(bmap, 0x00, 128);
 228
 229         expect_eq_pbl("", bmap, 23);
 230         expect_eq_pbl("", bmap, 1024);
 231
 232         /* single-word bitmaps */
 233         bitmap_set(bmap, 0, 9);
 234         expect_eq_pbl("0-8", bmap, 1024);
 235
 236         bitmap_fill(bmap, 35);
 237         expect_eq_pbl("0-63", bmap, 1024);
 238
 239         /* cross boundaries operations */
 240         bitmap_set(bmap, 79, 19);
 241         expect_eq_pbl("0-63,79-97", bmap, 1024);
 242
 243         bitmap_fill(bmap, 115);
 244         expect_eq_pbl("0-127", bmap, 1024);
 245
 246         /* Zeroing entire area */
 247         bitmap_fill(bmap, 1024);
 248         expect_eq_pbl("0-1023", bmap, 1024);
 249 }
 250
 251 static void __init test_copy(void)
 252 {
 253         DECLARE_BITMAP(bmap1, 1024);
 254         DECLARE_BITMAP(bmap2, 1024);
 255
 256         bitmap_zero(bmap1, 1024);
 257         bitmap_zero(bmap2, 1024);
 258
 259         /* single-word bitmaps */
 260         bitmap_set(bmap1, 0, 19);
 261         bitmap_copy(bmap2, bmap1, 23);
 262         expect_eq_pbl("0-18", bmap2, 1024);
 263
 264         bitmap_set(bmap2, 0, 23);
 265         bitmap_copy(bmap2, bmap1, 23);
 266         expect_eq_pbl("0-18", bmap2, 1024);
 267
 268         /* multi-word bitmaps */
 269         bitmap_set(bmap1, 0, 109);
 270         bitmap_copy(bmap2, bmap1, 1024);
 271         expect_eq_pbl("0-108", bmap2, 1024);
 272
 273         bitmap_fill(bmap2, 1024);
 274         bitmap_copy(bmap2, bmap1, 1024);
 275         expect_eq_pbl("0-108", bmap2, 1024);
 276
 277         /* the following tests assume a 32- or 64-bit arch (even 128b
 278          * if we care)
 279          */
 280
 281         bitmap_fill(bmap2, 1024);
 282         bitmap_copy(bmap2, bmap1, 109);  /* ... but 0-padded til word length */
 283         expect_eq_pbl("0-108,128-1023", bmap2, 1024);
 284
 285         bitmap_fill(bmap2, 1024);
 286         bitmap_copy(bmap2, bmap1, 97);  /* ... but aligned on word length */
 287         expect_eq_pbl("0-108,128-1023", bmap2, 1024);
 288 }
 289
 290 #define EXP2_IN_BITS    (sizeof(exp2) * 8)
 291
 292 static void __init test_replace(void)
 293 {
 294         unsigned int nbits = 64;
 295         unsigned int nlongs = DIV_ROUND_UP(nbits, BITS_PER_LONG);
 296         DECLARE_BITMAP(bmap, 1024);
 297
 298         BUILD_BUG_ON(EXP2_IN_BITS < nbits * 2);
 299
 300         bitmap_zero(bmap, 1024);
 301         bitmap_replace(bmap, &exp2[0 * nlongs], &exp2[1 * nlongs], exp2_to_exp3_mask, nbits);
 302         expect_eq_bitmap(bmap, exp3_0_1, nbits);
 303
 304         bitmap_zero(bmap, 1024);
 305         bitmap_replace(bmap, &exp2[1 * nlongs], &exp2[0 * nlongs], exp2_to_exp3_mask, nbits);
 306         expect_eq_bitmap(bmap, exp3_1_0, nbits);
 307
 308         bitmap_fill(bmap, 1024);
 309         bitmap_replace(bmap, &exp2[0 * nlongs], &exp2[1 * nlongs], exp2_to_exp3_mask, nbits);
 310         expect_eq_bitmap(bmap, exp3_0_1, nbits);
 311
 312         bitmap_fill(bmap, 1024);
 313         bitmap_replace(bmap, &exp2[1 * nlongs], &exp2[0 * nlongs], exp2_to_exp3_mask, nbits);
 314         expect_eq_bitmap(bmap, exp3_1_0, nbits);
 315 }
 316
 317 #define PARSE_TIME      0x1
 318 #define NO_LEN          0x2
 319
 320 struct test_bitmap_parselist{
 321         const int errno;
 322         const char *in;
 323         const unsigned long *expected;
 324         const int nbits;
 325         const int flags;
 326 };
 327
 328 static const struct test_bitmap_parselist parselist_tests[] __initconst = {
 329 #define step (sizeof(u64) / sizeof(unsigned long))
 330
 331         {0, "0",                        &exp1[0], 8, 0},
 332         {0, "1",                        &exp1[1 * step], 8, 0},
 333         {0, "0-15",                     &exp1[2 * step], 32, 0},
 334         {0, "16-31",                    &exp1[3 * step], 32, 0},
 335         {0, "0-31:1/2",                 &exp1[4 * step], 32, 0},
 336         {0, "1-31:1/2",                 &exp1[5 * step], 32, 0},
 337         {0, "0-31:1/4",                 &exp1[6 * step], 32, 0},
 338         {0, "1-31:1/4",                 &exp1[7 * step], 32, 0},
 339         {0, "0-31:4/4",                 &exp1[8 * step], 32, 0},
 340         {0, "1-31:4/4",                 &exp1[9 * step], 32, 0},
 341         {0, "0-31:1/4,32-63:2/4",       &exp1[10 * step], 64, 0},
 342         {0, "0-31:3/4,32-63:4/4",       &exp1[11 * step], 64, 0},
 343         {0, "  ,,  0-31:3/4  ,, 32-63:4/4  ,,  ",       &exp1[11 * step], 64, 0},
 344
 345         {0, "0-31:1/4,32-63:2/4,64-95:3/4,96-127:4/4",  exp2, 128, 0},
 346
 347         {0, "0-2047:128/256", NULL, 2048, PARSE_TIME},
 348
 349         {0, "",                         &exp1[12 * step], 8, 0},
 350         {0, "\n",                       &exp1[12 * step], 8, 0},
 351         {0, ",,  ,,  , ,  ,",           &exp1[12 * step], 8, 0},
 352         {0, " ,  ,,  , ,   ",           &exp1[12 * step], 8, 0},
 353         {0, " ,  ,,  , ,   \n",         &exp1[12 * step], 8, 0},
 354
 355         {0, "0-0",                      &exp1[0], 32, 0},
 356         {0, "1-1",                      &exp1[1 * step], 32, 0},
 357         {0, "15-15",                    &exp1[13 * step], 32, 0},
 358         {0, "31-31",                    &exp1[14 * step], 32, 0},
 359
 360         {0, "0-0:0/1",                  &exp1[12 * step], 32, 0},
 361         {0, "0-0:1/1",                  &exp1[0], 32, 0},
 362         {0, "0-0:1/31",                 &exp1[0], 32, 0},
 363         {0, "0-0:31/31",                &exp1[0], 32, 0},
 364         {0, "1-1:1/1",                  &exp1[1 * step], 32, 0},
 365         {0, "0-15:16/31",               &exp1[2 * step], 32, 0},
 366         {0, "15-15:1/2",                &exp1[13 * step], 32, 0},
 367         {0, "15-15:31/31",              &exp1[13 * step], 32, 0},
 368         {0, "15-31:1/31",               &exp1[13 * step], 32, 0},
 369         {0, "16-31:16/31",              &exp1[3 * step], 32, 0},
 370         {0, "31-31:31/31",              &exp1[14 * step], 32, 0},
 371
 372         {0, "N-N",                      &exp1[14 * step], 32, 0},
 373         {0, "0-0:1/N",                  &exp1[0], 32, 0},
 374         {0, "0-0:N/N",                  &exp1[0], 32, 0},
 375         {0, "0-15:16/N",                &exp1[2 * step], 32, 0},
 376         {0, "15-15:N/N",                &exp1[13 * step], 32, 0},
 377         {0, "15-N:1/N",                 &exp1[13 * step], 32, 0},
 378         {0, "16-N:16/N",                &exp1[3 * step], 32, 0},
 379         {0, "N-N:N/N",                  &exp1[14 * step], 32, 0},
 380
 381         {0, "0-N:1/3,1-N:1/3,2-N:1/3",          &exp1[8 * step], 32, 0},
 382         {0, "0-31:1/3,1-31:1/3,2-31:1/3",       &exp1[8 * step], 32, 0},
 383         {0, "1-10:8/12,8-31:24/29,0-31:0/3",    &exp1[9 * step], 32, 0},
 384
 385         {0,       "all",                &exp1[8 * step], 32, 0},
 386         {0,       "0, 1, all,  ",       &exp1[8 * step], 32, 0},
 387         {0,       "all:1/2",            &exp1[4 * step], 32, 0},
 388         {0,       "ALL:1/2",            &exp1[4 * step], 32, 0},
 389         {-EINVAL, "al", NULL, 8, 0},
 390         {-EINVAL, "alll", NULL, 8, 0},
 391
 392         {-EINVAL, "-1", NULL, 8, 0},
 393         {-EINVAL, "-0", NULL, 8, 0},
 394         {-EINVAL, "10-1", NULL, 8, 0},
 395         {-ERANGE, "8-8", NULL, 8, 0},
 396         {-ERANGE, "0-31", NULL, 8, 0},
 397         {-EINVAL, "0-31:", NULL, 32, 0},
 398         {-EINVAL, "0-31:0", NULL, 32, 0},
 399         {-EINVAL, "0-31:0/", NULL, 32, 0},
 400         {-EINVAL, "0-31:0/0", NULL, 32, 0},
 401         {-EINVAL, "0-31:1/0", NULL, 32, 0},
 402         {-EINVAL, "0-31:10/1", NULL, 32, 0},
 403         {-EOVERFLOW, "0-98765432123456789:10/1", NULL, 8, 0},
 404
 405         {-EINVAL, "a-31", NULL, 8, 0},
 406         {-EINVAL, "0-a1", NULL, 8, 0},
 407         {-EINVAL, "a-31:10/1", NULL, 8, 0},
 408         {-EINVAL, "0-31:a/1", NULL, 8, 0},
 409         {-EINVAL, "0-\n", NULL, 8, 0},
 410
 411 };
 412
 413 static void __init test_bitmap_parselist(void)
 414 {
 415         int i;
 416         int err;
 417         ktime_t time;
 418         DECLARE_BITMAP(bmap, 2048);
 419
 420         for (i = 0; i < ARRAY_SIZE(parselist_tests); i++) {
 421 #define ptest parselist_tests[i]
 422
 423                 time = ktime_get();
 424                 err = bitmap_parselist(ptest.in, bmap, ptest.nbits);
 425                 time = ktime_get() - time;
 426
 427                 if (err != ptest.errno) {
 428                         pr_err("parselist: %d: input is %s, errno is %d, expected %d\n",
 429                                         i, ptest.in, err, ptest.errno);
 430                         continue;
 431                 }
 432
 433                 if (!err && ptest.expected
 434                          && !__bitmap_equal(bmap, ptest.expected, ptest.nbits)) {
 435                         pr_err("parselist: %d: input is %s, result is 0x%lx, expected 0x%lx\n",
 436                                         i, ptest.in, bmap[0],
 437                                         *ptest.expected);
 438                         continue;
 439                 }
 440
 441                 if (ptest.flags & PARSE_TIME)
 442                         pr_err("parselist: %d: input is '%s' OK, Time: %llu\n",
 443                                         i, ptest.in, time);
 444
 445 #undef ptest
 446         }
 447 }
 448
 449 static const unsigned long parse_test[] __initconst = {
 450         BITMAP_FROM_U64(0),
 451         BITMAP_FROM_U64(1),
 452         BITMAP_FROM_U64(0xdeadbeef),
 453         BITMAP_FROM_U64(0x100000000ULL),
 454 };
 455
 456 static const unsigned long parse_test2[] __initconst = {
 457         BITMAP_FROM_U64(0x100000000ULL), BITMAP_FROM_U64(0xdeadbeef),
 458         BITMAP_FROM_U64(0x100000000ULL), BITMAP_FROM_U64(0xbaadf00ddeadbeef),
 459         BITMAP_FROM_U64(0x100000000ULL), BITMAP_FROM_U64(0x0badf00ddeadbeef),
 460 };
 461
 462 static const struct test_bitmap_parselist parse_tests[] __initconst = {
 463         {0, "",                         &parse_test[0 * step], 32, 0},
 464         {0, " ",                        &parse_test[0 * step], 32, 0},
 465         {0, "0",                        &parse_test[0 * step], 32, 0},
 466         {0, "0\n",                      &parse_test[0 * step], 32, 0},
 467         {0, "1",                        &parse_test[1 * step], 32, 0},
 468         {0, "deadbeef",                 &parse_test[2 * step], 32, 0},
 469         {0, "1,0",                      &parse_test[3 * step], 33, 0},
 470         {0, "deadbeef,\n,0,1",          &parse_test[2 * step], 96, 0},
 471
 472         {0, "deadbeef,1,0",             &parse_test2[0 * 2 * step], 96, 0},
 473         {0, "baadf00d,deadbeef,1,0",    &parse_test2[1 * 2 * step], 128, 0},
 474         {0, "badf00d,deadbeef,1,0",     &parse_test2[2 * 2 * step], 124, 0},
 475         {0, "badf00d,deadbeef,1,0",     &parse_test2[2 * 2 * step], 124, NO_LEN},
 476         {0, "  badf00d,deadbeef,1,0  ", &parse_test2[2 * 2 * step], 124, 0},
 477         {0, " , badf00d,deadbeef,1,0 , ",       &parse_test2[2 * 2 * step], 124, 0},
 478         {0, " , badf00d, ,, ,,deadbeef,1,0 , ", &parse_test2[2 * 2 * step], 124, 0},
 479
 480         {-EINVAL,    "goodfood,deadbeef,1,0",   NULL, 128, 0},
 481         {-EOVERFLOW, "3,0",                     NULL, 33, 0},
 482         {-EOVERFLOW, "123badf00d,deadbeef,1,0", NULL, 128, 0},
 483         {-EOVERFLOW, "badf00d,deadbeef,1,0",    NULL, 90, 0},
 484         {-EOVERFLOW, "fbadf00d,deadbeef,1,0",   NULL, 95, 0},
 485         {-EOVERFLOW, "badf00d,deadbeef,1,0",    NULL, 100, 0},
 486 #undef step
 487 };
 488
 489 static void __init test_bitmap_parse(void)
 490 {
 491         int i;
 492         int err;
 493         ktime_t time;
 494         DECLARE_BITMAP(bmap, 2048);
 495
 496         for (i = 0; i < ARRAY_SIZE(parse_tests); i++) {
 497                 struct test_bitmap_parselist test = parse_tests[i];
 498                 size_t len = test.flags & NO_LEN ? UINT_MAX : strlen(test.in);
 499
 500                 time = ktime_get();
 501                 err = bitmap_parse(test.in, len, bmap, test.nbits);
 502                 time = ktime_get() - time;
 503
 504                 if (err != test.errno) {
 505                         pr_err("parse: %d: input is %s, errno is %d, expected %d\n",
 506                                         i, test.in, err, test.errno);
 507                         continue;
 508                 }
 509
 510                 if (!err && test.expected
 511                          && !__bitmap_equal(bmap, test.expected, test.nbits)) {
 512                         pr_err("parse: %d: input is %s, result is 0x%lx, expected 0x%lx\n",
 513                                         i, test.in, bmap[0],
 514                                         *test.expected);
 515                         continue;
 516                 }
 517
 518                 if (test.flags & PARSE_TIME)
 519                         pr_err("parse: %d: input is '%s' OK, Time: %llu\n",
 520                                         i, test.in, time);
 521         }
 522 }
 523
 524 #define EXP1_IN_BITS    (sizeof(exp1) * 8)
 525
 526 static void __init test_bitmap_arr32(void)
 527 {
 528         unsigned int nbits, next_bit;
 529         u32 arr[EXP1_IN_BITS / 32];
 530         DECLARE_BITMAP(bmap2, EXP1_IN_BITS);
 531
 532         memset(arr, 0xa5, sizeof(arr));
 533
 534         for (nbits = 0; nbits < EXP1_IN_BITS; ++nbits) {
 535                 bitmap_to_arr32(arr, exp1, nbits);
 536                 bitmap_from_arr32(bmap2, arr, nbits);
 537                 expect_eq_bitmap(bmap2, exp1, nbits);
 538
 539                 next_bit = find_next_bit(bmap2,
 540                                 round_up(nbits, BITS_PER_LONG), nbits);
 541                 if (next_bit < round_up(nbits, BITS_PER_LONG))
 542                         pr_err("bitmap_copy_arr32(nbits == %d:"
 543                                 " tail is not safely cleared: %d\n",
 544                                 nbits, next_bit);
 545
 546                 if (nbits < EXP1_IN_BITS - 32)
 547                         expect_eq_uint(arr[DIV_ROUND_UP(nbits, 32)],
 548                                                                 0xa5a5a5a5);
 549         }
 550 }
 551
 552 static void noinline __init test_mem_optimisations(void)
 553 {
 554         DECLARE_BITMAP(bmap1, 1024);
 555         DECLARE_BITMAP(bmap2, 1024);
 556         unsigned int start, nbits;
 557
 558         for (start = 0; start < 1024; start += 8) {
 559                 for (nbits = 0; nbits < 1024 - start; nbits += 8) {
 560                         memset(bmap1, 0x5a, sizeof(bmap1));
 561                         memset(bmap2, 0x5a, sizeof(bmap2));
 562
 563                         bitmap_set(bmap1, start, nbits);
 564                         __bitmap_set(bmap2, start, nbits);
 565                         if (!bitmap_equal(bmap1, bmap2, 1024)) {
 566                                 printk("set not equal %d %d\n", start, nbits);
 567                                 failed_tests++;
 568                         }
 569                         if (!__bitmap_equal(bmap1, bmap2, 1024)) {
 570                                 printk("set not __equal %d %d\n", start, nbits);
 571                                 failed_tests++;
 572                         }
 573
 574                         bitmap_clear(bmap1, start, nbits);
 575                         __bitmap_clear(bmap2, start, nbits);
 576                         if (!bitmap_equal(bmap1, bmap2, 1024)) {
 577                                 printk("clear not equal %d %d\n", start, nbits);
 578                                 failed_tests++;
 579                         }
 580                         if (!__bitmap_equal(bmap1, bmap2, 1024)) {
 581                                 printk("clear not __equal %d %d\n", start,
 582                                                                         nbits);
 583                                 failed_tests++;
 584                         }
 585                 }
 586         }
 587 }
 588
 589 static const unsigned char clump_exp[] __initconst = {
 590         0x01,   /* 1 bit set */
 591         0x02,   /* non-edge 1 bit set */
 592         0x00,   /* zero bits set */
 593         0x38,   /* 3 bits set across 4-bit boundary */
 594         0x38,   /* Repeated clump */
 595         0x0F,   /* 4 bits set */
 596         0xFF,   /* all bits set */
 597         0x05,   /* non-adjacent 2 bits set */
 598 };
 599
 600 static void __init test_for_each_set_clump8(void)
 601 {
 602 #define CLUMP_EXP_NUMBITS 64
 603         DECLARE_BITMAP(bits, CLUMP_EXP_NUMBITS);
 604         unsigned int start;
 605         unsigned long clump;
 606
 607         /* set bitmap to test case */
 608         bitmap_zero(bits, CLUMP_EXP_NUMBITS);
 609         bitmap_set(bits, 0, 1);         /* 0x01 */
 610         bitmap_set(bits, 9, 1);         /* 0x02 */
 611         bitmap_set(bits, 27, 3);        /* 0x28 */
 612         bitmap_set(bits, 35, 3);        /* 0x28 */
 613         bitmap_set(bits, 40, 4);        /* 0x0F */
 614         bitmap_set(bits, 48, 8);        /* 0xFF */
 615         bitmap_set(bits, 56, 1);        /* 0x05 - part 1 */
 616         bitmap_set(bits, 58, 1);        /* 0x05 - part 2 */
 617
 618         for_each_set_clump8(start, clump, bits, CLUMP_EXP_NUMBITS)
 619                 expect_eq_clump8(start, CLUMP_EXP_NUMBITS, clump_exp, &clump);
 620 }
 621
 622 struct test_bitmap_cut {
 623         unsigned int first;
 624         unsigned int cut;
 625         unsigned int nbits;
 626         unsigned long in[4];
 627         unsigned long expected[4];
 628 };
 629
 630 static struct test_bitmap_cut test_cut[] = {
 631         {  0,  0,  8, { 0x0000000aUL, }, { 0x0000000aUL, }, },
 632         {  0,  0, 32, { 0xdadadeadUL, }, { 0xdadadeadUL, }, },
 633         {  0,  3,  8, { 0x000000aaUL, }, { 0x00000015UL, }, },
 634         {  3,  3,  8, { 0x000000aaUL, }, { 0x00000012UL, }, },
 635         {  0,  1, 32, { 0xa5a5a5a5UL, }, { 0x52d2d2d2UL, }, },
 636         {  0,  8, 32, { 0xdeadc0deUL, }, { 0x00deadc0UL, }, },
 637         {  1,  1, 32, { 0x5a5a5a5aUL, }, { 0x2d2d2d2cUL, }, },
 638         {  0, 15, 32, { 0xa5a5a5a5UL, }, { 0x00014b4bUL, }, },
 639         {  0, 16, 32, { 0xa5a5a5a5UL, }, { 0x0000a5a5UL, }, },
 640         { 15, 15, 32, { 0xa5a5a5a5UL, }, { 0x000125a5UL, }, },
 641         { 15, 16, 32, { 0xa5a5a5a5UL, }, { 0x0000a5a5UL, }, },
 642         { 16, 15, 32, { 0xa5a5a5a5UL, }, { 0x0001a5a5UL, }, },
 643
 644         { BITS_PER_LONG, BITS_PER_LONG, BITS_PER_LONG,
 645                 { 0xa5a5a5a5UL, 0xa5a5a5a5UL, },
 646                 { 0xa5a5a5a5UL, 0xa5a5a5a5UL, },
 647         },
 648         { 1, BITS_PER_LONG - 1, BITS_PER_LONG,
 649                 { 0xa5a5a5a5UL, 0xa5a5a5a5UL, },
 650                 { 0x00000001UL, 0x00000001UL, },
 651         },
 652
 653         { 0, BITS_PER_LONG * 2, BITS_PER_LONG * 2 + 1,
 654                 { 0xa5a5a5a5UL, 0x00000001UL, 0x00000001UL, 0x00000001UL },
 655                 { 0x00000001UL, },
 656         },
 657         { 16, BITS_PER_LONG * 2 + 1, BITS_PER_LONG * 2 + 1 + 16,
 658                 { 0x0000ffffUL, 0x5a5a5a5aUL, 0x5a5a5a5aUL, 0x5a5a5a5aUL },
 659                 { 0x2d2dffffUL, },
 660         },
 661 };
 662
 663 static void __init test_bitmap_cut(void)
 664 {
 665         unsigned long b[5], *in = &b[1], *out = &b[0];  /* Partial overlap */
 666         int i;
 667
 668         for (i = 0; i < ARRAY_SIZE(test_cut); i++) {
 669                 struct test_bitmap_cut *t = &test_cut[i];
 670
 671                 memcpy(in, t->in, sizeof(t->in));
 672
 673                 bitmap_cut(out, in, t->first, t->cut, t->nbits);
 674
 675                 expect_eq_bitmap(t->expected, out, t->nbits);
 676         }
 677 }
 678
 679 struct test_bitmap_print {
 680         const unsigned long *bitmap;
 681         unsigned long nbits;
 682         const char *mask;
 683         const char *list;
 684 };
 685
 686 static const unsigned long small_bitmap[] __initconst = {
 687         BITMAP_FROM_U64(0x3333333311111111ULL),
 688 };
 689
 690 static const char small_mask[] __initconst = "33333333,11111111\n";
 691 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";
 692
 693 static const unsigned long large_bitmap[] __initconst = {
 694         BITMAP_FROM_U64(0x3333333311111111ULL), BITMAP_FROM_U64(0x3333333311111111ULL),
 695         BITMAP_FROM_U64(0x3333333311111111ULL), BITMAP_FROM_U64(0x3333333311111111ULL),
 696         BITMAP_FROM_U64(0x3333333311111111ULL), BITMAP_FROM_U64(0x3333333311111111ULL),
 697         BITMAP_FROM_U64(0x3333333311111111ULL), BITMAP_FROM_U64(0x3333333311111111ULL),
 698         BITMAP_FROM_U64(0x3333333311111111ULL), BITMAP_FROM_U64(0x3333333311111111ULL),
 699         BITMAP_FROM_U64(0x3333333311111111ULL), BITMAP_FROM_U64(0x3333333311111111ULL),
 700         BITMAP_FROM_U64(0x3333333311111111ULL), BITMAP_FROM_U64(0x3333333311111111ULL),
 701         BITMAP_FROM_U64(0x3333333311111111ULL), BITMAP_FROM_U64(0x3333333311111111ULL),
 702         BITMAP_FROM_U64(0x3333333311111111ULL), BITMAP_FROM_U64(0x3333333311111111ULL),
 703         BITMAP_FROM_U64(0x3333333311111111ULL), BITMAP_FROM_U64(0x3333333311111111ULL),
 704         BITMAP_FROM_U64(0x3333333311111111ULL), BITMAP_FROM_U64(0x3333333311111111ULL),
 705         BITMAP_FROM_U64(0x3333333311111111ULL), BITMAP_FROM_U64(0x3333333311111111ULL),
 706         BITMAP_FROM_U64(0x3333333311111111ULL), BITMAP_FROM_U64(0x3333333311111111ULL),
 707         BITMAP_FROM_U64(0x3333333311111111ULL), BITMAP_FROM_U64(0x3333333311111111ULL),
 708         BITMAP_FROM_U64(0x3333333311111111ULL), BITMAP_FROM_U64(0x3333333311111111ULL),
 709         BITMAP_FROM_U64(0x3333333311111111ULL), BITMAP_FROM_U64(0x3333333311111111ULL),
 710         BITMAP_FROM_U64(0x3333333311111111ULL), BITMAP_FROM_U64(0x3333333311111111ULL),
 711         BITMAP_FROM_U64(0x3333333311111111ULL), BITMAP_FROM_U64(0x3333333311111111ULL),
 712         BITMAP_FROM_U64(0x3333333311111111ULL), BITMAP_FROM_U64(0x3333333311111111ULL),
 713         BITMAP_FROM_U64(0x3333333311111111ULL), BITMAP_FROM_U64(0x3333333311111111ULL),
 714 };
 715
 716 static const char large_mask[] __initconst = "33333333,11111111,33333333,11111111,"
 717                                         "33333333,11111111,33333333,11111111,"
 718                                         "33333333,11111111,33333333,11111111,"
 719                                         "33333333,11111111,33333333,11111111,"
 720                                         "33333333,11111111,33333333,11111111,"
 721                                         "33333333,11111111,33333333,11111111,"
 722                                         "33333333,11111111,33333333,11111111,"
 723                                         "33333333,11111111,33333333,11111111,"
 724                                         "33333333,11111111,33333333,11111111,"
 725                                         "33333333,11111111,33333333,11111111,"
 726                                         "33333333,11111111,33333333,11111111,"
 727                                         "33333333,11111111,33333333,11111111,"
 728                                         "33333333,11111111,33333333,11111111,"
 729                                         "33333333,11111111,33333333,11111111,"
 730                                         "33333333,11111111,33333333,11111111,"
 731                                         "33333333,11111111,33333333,11111111,"
 732                                         "33333333,11111111,33333333,11111111,"
 733                                         "33333333,11111111,33333333,11111111,"
 734                                         "33333333,11111111,33333333,11111111,"
 735                                         "33333333,11111111,33333333,11111111\n";
 736
 737 static const char large_list[] __initconst = /* more than 4KB */
 738         "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"
 739         "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"
 740         "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"
 741         "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"
 742         "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"
 743         "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"
 744         "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"
 745         "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"
 746         "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"
 747         "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"
 748         "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"
 749         "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"
 750         "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-"
 751         "1001,1004-1005,1008-1009,1012-1013,1016-1017,1020-1021,1024,1028,1032,1036,1040,1044,1048,1052,1056-1057,1060-10"
 752         "61,1064-1065,1068-1069,1072-1073,1076-1077,1080-1081,1084-1085,1088,1092,1096,1100,1104,1108,1112,1116,1120-1121"
 753         ",1124-1125,1128-1129,1132-1133,1136-1137,1140-1141,1144-1145,1148-1149,1152,1156,1160,1164,1168,1172,1176,1180,1"
 754         "184-1185,1188-1189,1192-1193,1196-1197,1200-1201,1204-1205,1208-1209,1212-1213,1216,1220,1224,1228,1232,1236,124"
 755         "0,1244,1248-1249,1252-1253,1256-1257,1260-1261,1264-1265,1268-1269,1272-1273,1276-1277,1280,1284,1288,1292,1296,"
 756         "1300,1304,1308,1312-1313,1316-1317,1320-1321,1324-1325,1328-1329,1332-1333,1336-1337,1340-1341,1344,1348,1352,13"
 757         "56,1360,1364,1368,1372,1376-1377,1380-1381,1384-1385,1388-1389,1392-1393,1396-1397,1400-1401,1404-1405,1408,1412"
 758         ",1416,1420,1424,1428,1432,1436,1440-1441,1444-1445,1448-1449,1452-1453,1456-1457,1460-1461,1464-1465,1468-1469,1"
 759         "472,1476,1480,1484,1488,1492,1496,1500,1504-1505,1508-1509,1512-1513,1516-1517,1520-1521,1524-1525,1528-1529,153"
 760         "2-1533,1536,1540,1544,1548,1552,1556,1560,1564,1568-1569,1572-1573,1576-1577,1580-1581,1584-1585,1588-1589,1592-"
 761         "1593,1596-1597,1600,1604,1608,1612,1616,1620,1624,1628,1632-1633,1636-1637,1640-1641,1644-1645,1648-1649,1652-16"
 762         "53,1656-1657,1660-1661,1664,1668,1672,1676,1680,1684,1688,1692,1696-1697,1700-1701,1704-1705,1708-1709,1712-1713"
 763         ",1716-1717,1720-1721,1724-1725,1728,1732,1736,1740,1744,1748,1752,1756,1760-1761,1764-1765,1768-1769,1772-1773,1"
 764         "776-1777,1780-1781,1784-1785,1788-1789,1792,1796,1800,1804,1808,1812,1816,1820,1824-1825,1828-1829,1832-1833,183"
 765         "6-1837,1840-1841,1844-1845,1848-1849,1852-1853,1856,1860,1864,1868,1872,1876,1880,1884,1888-1889,1892-1893,1896-"
 766         "1897,1900-1901,1904-1905,1908-1909,1912-1913,1916-1917,1920,1924,1928,1932,1936,1940,1944,1948,1952-1953,1956-19"
 767         "57,1960-1961,1964-1965,1968-1969,1972-1973,1976-1977,1980-1981,1984,1988,1992,1996,2000,2004,2008,2012,2016-2017"
 768         ",2020-2021,2024-2025,2028-2029,2032-2033,2036-2037,2040-2041,2044-2045,2048,2052,2056,2060,2064,2068,2072,2076,2"
 769         "080-2081,2084-2085,2088-2089,2092-2093,2096-2097,2100-2101,2104-2105,2108-2109,2112,2116,2120,2124,2128,2132,213"
 770         "6,2140,2144-2145,2148-2149,2152-2153,2156-2157,2160-2161,2164-2165,2168-2169,2172-2173,2176,2180,2184,2188,2192,"
 771         "2196,2200,2204,2208-2209,2212-2213,2216-2217,2220-2221,2224-2225,2228-2229,2232-2233,2236-2237,2240,2244,2248,22"
 772         "52,2256,2260,2264,2268,2272-2273,2276-2277,2280-2281,2284-2285,2288-2289,2292-2293,2296-2297,2300-2301,2304,2308"
 773         ",2312,2316,2320,2324,2328,2332,2336-2337,2340-2341,2344-2345,2348-2349,2352-2353,2356-2357,2360-2361,2364-2365,2"
 774         "368,2372,2376,2380,2384,2388,2392,2396,2400-2401,2404-2405,2408-2409,2412-2413,2416-2417,2420-2421,2424-2425,242"
 775         "8-2429,2432,2436,2440,2444,2448,2452,2456,2460,2464-2465,2468-2469,2472-2473,2476-2477,2480-2481,2484-2485,2488-"
 776         "2489,2492-2493,2496,2500,2504,2508,2512,2516,2520,2524,2528-2529,2532-2533,2536-2537,2540-2541,2544-2545,2548-25"
 777         "49,2552-2553,2556-2557\n";
 778
 779 static const struct test_bitmap_print test_print[] __initconst = {
 780         { small_bitmap, sizeof(small_bitmap) * BITS_PER_BYTE, small_mask, small_list },
 781         { large_bitmap, sizeof(large_bitmap) * BITS_PER_BYTE, large_mask, large_list },
 782 };
 783
 784 static void __init test_bitmap_print_buf(void)
 785 {
 786         int i;
 787
 788         for (i = 0; i < ARRAY_SIZE(test_print); i++) {
 789                 const struct test_bitmap_print *t = &test_print[i];
 790                 int n;
 791
 792                 n = bitmap_print_bitmask_to_buf(print_buf, t->bitmap, t->nbits,
 793                                                 0, 2 * PAGE_SIZE);
 794                 expect_eq_uint(strlen(t->mask) + 1, n);
 795                 expect_eq_str(t->mask, print_buf, n);
 796
 797                 n = bitmap_print_list_to_buf(print_buf, t->bitmap, t->nbits,
 798                                              0, 2 * PAGE_SIZE);
 799                 expect_eq_uint(strlen(t->list) + 1, n);
 800                 expect_eq_str(t->list, print_buf, n);
 801
 802                 /* test by non-zero offset */
 803                 if (strlen(t->list) > PAGE_SIZE) {
 804                         n = bitmap_print_list_to_buf(print_buf, t->bitmap, t->nbits,
 805                                                      PAGE_SIZE, PAGE_SIZE);
 806                         expect_eq_uint(strlen(t->list) + 1 - PAGE_SIZE, n);
 807                         expect_eq_str(t->list + PAGE_SIZE, print_buf, n);
 808                 }
 809         }
 810 }
 811
 812 static void __init selftest(void)
 813 {
 814         test_zero_clear();
 815         test_fill_set();
 816         test_copy();
 817         test_replace();
 818         test_bitmap_arr32();
 819         test_bitmap_parse();
 820         test_bitmap_parselist();
 821         test_mem_optimisations();
 822         test_for_each_set_clump8();
 823         test_bitmap_cut();
 824         test_bitmap_print_buf();
 825 }
 826
 827 KSTM_MODULE_LOADERS(test_bitmap);
 828 MODULE_AUTHOR("david decotigny <david.decotigny@googlers.com>");
 829 MODULE_LICENSE("GPL");