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