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