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