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