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