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