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 23 static const unsigned long exp1[] __initconst = { 24 BITMAP_FROM_U64(1), 25 BITMAP_FROM_U64(2), 26 BITMAP_FROM_U64(0x0000ffff), 27 BITMAP_FROM_U64(0xffff0000), 28 BITMAP_FROM_U64(0x55555555), 29 BITMAP_FROM_U64(0xaaaaaaaa), 30 BITMAP_FROM_U64(0x11111111), 31 BITMAP_FROM_U64(0x22222222), 32 BITMAP_FROM_U64(0xffffffff), 33 BITMAP_FROM_U64(0xfffffffe), 34 BITMAP_FROM_U64(0x3333333311111111ULL), 35 BITMAP_FROM_U64(0xffffffff77777777ULL), 36 BITMAP_FROM_U64(0), 37 BITMAP_FROM_U64(0x00008000), 38 BITMAP_FROM_U64(0x80000000), 39 }; 40 41 static const unsigned long exp2[] __initconst = { 42 BITMAP_FROM_U64(0x3333333311111111ULL), 43 BITMAP_FROM_U64(0xffffffff77777777ULL), 44 }; 45 46 /* Fibonacci sequence */ 47 static const unsigned long exp2_to_exp3_mask[] __initconst = { 48 BITMAP_FROM_U64(0x008000020020212eULL), 49 }; 50 /* exp3_0_1 = (exp2[0] & ~exp2_to_exp3_mask) | (exp2[1] & exp2_to_exp3_mask) */ 51 static const unsigned long exp3_0_1[] __initconst = { 52 BITMAP_FROM_U64(0x33b3333311313137ULL), 53 }; 54 /* exp3_1_0 = (exp2[1] & ~exp2_to_exp3_mask) | (exp2[0] & exp2_to_exp3_mask) */ 55 static const unsigned long exp3_1_0[] __initconst = { 56 BITMAP_FROM_U64(0xff7fffff77575751ULL), 57 }; 58 59 static bool __init 60 __check_eq_uint(const char *srcfile, unsigned int line, 61 const unsigned int exp_uint, unsigned int x) 62 { 63 if (exp_uint != x) { 64 pr_err("[%s:%u] expected %u, got %u\n", 65 srcfile, line, exp_uint, x); 66 return false; 67 } 68 return true; 69 } 70 71 72 static bool __init 73 __check_eq_bitmap(const char *srcfile, unsigned int line, 74 const unsigned long *exp_bmap, const unsigned long *bmap, 75 unsigned int nbits) 76 { 77 if (!bitmap_equal(exp_bmap, bmap, nbits)) { 78 pr_warn("[%s:%u] bitmaps contents differ: expected \"%*pbl\", got \"%*pbl\"\n", 79 srcfile, line, 80 nbits, exp_bmap, nbits, bmap); 81 return false; 82 } 83 return true; 84 } 85 86 static bool __init 87 __check_eq_pbl(const char *srcfile, unsigned int line, 88 const char *expected_pbl, 89 const unsigned long *bitmap, unsigned int nbits) 90 { 91 snprintf(pbl_buffer, sizeof(pbl_buffer), "%*pbl", nbits, bitmap); 92 if (strcmp(expected_pbl, pbl_buffer)) { 93 pr_warn("[%s:%u] expected \"%s\", got \"%s\"\n", 94 srcfile, line, 95 expected_pbl, pbl_buffer); 96 return false; 97 } 98 return true; 99 } 100 101 static bool __init 102 __check_eq_u32_array(const char *srcfile, unsigned int line, 103 const u32 *exp_arr, unsigned int exp_len, 104 const u32 *arr, unsigned int len) __used; 105 static bool __init 106 __check_eq_u32_array(const char *srcfile, unsigned int line, 107 const u32 *exp_arr, unsigned int exp_len, 108 const u32 *arr, unsigned int len) 109 { 110 if (exp_len != len) { 111 pr_warn("[%s:%u] array length differ: expected %u, got %u\n", 112 srcfile, line, 113 exp_len, len); 114 return false; 115 } 116 117 if (memcmp(exp_arr, arr, len*sizeof(*arr))) { 118 pr_warn("[%s:%u] array contents differ\n", srcfile, line); 119 print_hex_dump(KERN_WARNING, " exp: ", DUMP_PREFIX_OFFSET, 120 32, 4, exp_arr, exp_len*sizeof(*exp_arr), false); 121 print_hex_dump(KERN_WARNING, " got: ", DUMP_PREFIX_OFFSET, 122 32, 4, arr, len*sizeof(*arr), false); 123 return false; 124 } 125 126 return true; 127 } 128 129 static bool __init __check_eq_clump8(const char *srcfile, unsigned int line, 130 const unsigned int offset, 131 const unsigned int size, 132 const unsigned char *const clump_exp, 133 const unsigned long *const clump) 134 { 135 unsigned long exp; 136 137 if (offset >= size) { 138 pr_warn("[%s:%u] bit offset for clump out-of-bounds: expected less than %u, got %u\n", 139 srcfile, line, size, offset); 140 return false; 141 } 142 143 exp = clump_exp[offset / 8]; 144 if (!exp) { 145 pr_warn("[%s:%u] bit offset for zero clump: expected nonzero clump, got bit offset %u with clump value 0", 146 srcfile, line, offset); 147 return false; 148 } 149 150 if (*clump != exp) { 151 pr_warn("[%s:%u] expected clump value of 0x%lX, got clump value of 0x%lX", 152 srcfile, line, exp, *clump); 153 return false; 154 } 155 156 return true; 157 } 158 159 #define __expect_eq(suffix, ...) \ 160 ({ \ 161 int result = 0; \ 162 total_tests++; \ 163 if (!__check_eq_ ## suffix(__FILE__, __LINE__, \ 164 ##__VA_ARGS__)) { \ 165 failed_tests++; \ 166 result = 1; \ 167 } \ 168 result; \ 169 }) 170 171 #define expect_eq_uint(...) __expect_eq(uint, ##__VA_ARGS__) 172 #define expect_eq_bitmap(...) __expect_eq(bitmap, ##__VA_ARGS__) 173 #define expect_eq_pbl(...) __expect_eq(pbl, ##__VA_ARGS__) 174 #define expect_eq_u32_array(...) __expect_eq(u32_array, ##__VA_ARGS__) 175 #define expect_eq_clump8(...) __expect_eq(clump8, ##__VA_ARGS__) 176 177 static void __init test_zero_clear(void) 178 { 179 DECLARE_BITMAP(bmap, 1024); 180 181 /* Known way to set all bits */ 182 memset(bmap, 0xff, 128); 183 184 expect_eq_pbl("0-22", bmap, 23); 185 expect_eq_pbl("0-1023", bmap, 1024); 186 187 /* single-word bitmaps */ 188 bitmap_clear(bmap, 0, 9); 189 expect_eq_pbl("9-1023", bmap, 1024); 190 191 bitmap_zero(bmap, 35); 192 expect_eq_pbl("64-1023", bmap, 1024); 193 194 /* cross boundaries operations */ 195 bitmap_clear(bmap, 79, 19); 196 expect_eq_pbl("64-78,98-1023", bmap, 1024); 197 198 bitmap_zero(bmap, 115); 199 expect_eq_pbl("128-1023", bmap, 1024); 200 201 /* Zeroing entire area */ 202 bitmap_zero(bmap, 1024); 203 expect_eq_pbl("", bmap, 1024); 204 } 205 206 static void __init test_fill_set(void) 207 { 208 DECLARE_BITMAP(bmap, 1024); 209 210 /* Known way to clear all bits */ 211 memset(bmap, 0x00, 128); 212 213 expect_eq_pbl("", bmap, 23); 214 expect_eq_pbl("", bmap, 1024); 215 216 /* single-word bitmaps */ 217 bitmap_set(bmap, 0, 9); 218 expect_eq_pbl("0-8", bmap, 1024); 219 220 bitmap_fill(bmap, 35); 221 expect_eq_pbl("0-63", bmap, 1024); 222 223 /* cross boundaries operations */ 224 bitmap_set(bmap, 79, 19); 225 expect_eq_pbl("0-63,79-97", bmap, 1024); 226 227 bitmap_fill(bmap, 115); 228 expect_eq_pbl("0-127", bmap, 1024); 229 230 /* Zeroing entire area */ 231 bitmap_fill(bmap, 1024); 232 expect_eq_pbl("0-1023", bmap, 1024); 233 } 234 235 static void __init test_copy(void) 236 { 237 DECLARE_BITMAP(bmap1, 1024); 238 DECLARE_BITMAP(bmap2, 1024); 239 240 bitmap_zero(bmap1, 1024); 241 bitmap_zero(bmap2, 1024); 242 243 /* single-word bitmaps */ 244 bitmap_set(bmap1, 0, 19); 245 bitmap_copy(bmap2, bmap1, 23); 246 expect_eq_pbl("0-18", bmap2, 1024); 247 248 bitmap_set(bmap2, 0, 23); 249 bitmap_copy(bmap2, bmap1, 23); 250 expect_eq_pbl("0-18", bmap2, 1024); 251 252 /* multi-word bitmaps */ 253 bitmap_set(bmap1, 0, 109); 254 bitmap_copy(bmap2, bmap1, 1024); 255 expect_eq_pbl("0-108", bmap2, 1024); 256 257 bitmap_fill(bmap2, 1024); 258 bitmap_copy(bmap2, bmap1, 1024); 259 expect_eq_pbl("0-108", bmap2, 1024); 260 261 /* the following tests assume a 32- or 64-bit arch (even 128b 262 * if we care) 263 */ 264 265 bitmap_fill(bmap2, 1024); 266 bitmap_copy(bmap2, bmap1, 109); /* ... but 0-padded til word length */ 267 expect_eq_pbl("0-108,128-1023", bmap2, 1024); 268 269 bitmap_fill(bmap2, 1024); 270 bitmap_copy(bmap2, bmap1, 97); /* ... but aligned on word length */ 271 expect_eq_pbl("0-108,128-1023", bmap2, 1024); 272 } 273 274 #define EXP2_IN_BITS (sizeof(exp2) * 8) 275 276 static void __init test_replace(void) 277 { 278 unsigned int nbits = 64; 279 unsigned int nlongs = DIV_ROUND_UP(nbits, BITS_PER_LONG); 280 DECLARE_BITMAP(bmap, 1024); 281 282 BUILD_BUG_ON(EXP2_IN_BITS < nbits * 2); 283 284 bitmap_zero(bmap, 1024); 285 bitmap_replace(bmap, &exp2[0 * nlongs], &exp2[1 * nlongs], exp2_to_exp3_mask, nbits); 286 expect_eq_bitmap(bmap, exp3_0_1, nbits); 287 288 bitmap_zero(bmap, 1024); 289 bitmap_replace(bmap, &exp2[1 * nlongs], &exp2[0 * nlongs], exp2_to_exp3_mask, nbits); 290 expect_eq_bitmap(bmap, exp3_1_0, nbits); 291 292 bitmap_fill(bmap, 1024); 293 bitmap_replace(bmap, &exp2[0 * nlongs], &exp2[1 * nlongs], exp2_to_exp3_mask, nbits); 294 expect_eq_bitmap(bmap, exp3_0_1, nbits); 295 296 bitmap_fill(bmap, 1024); 297 bitmap_replace(bmap, &exp2[1 * nlongs], &exp2[0 * nlongs], exp2_to_exp3_mask, nbits); 298 expect_eq_bitmap(bmap, exp3_1_0, nbits); 299 } 300 301 #define PARSE_TIME 0x1 302 #define NO_LEN 0x2 303 304 struct test_bitmap_parselist{ 305 const int errno; 306 const char *in; 307 const unsigned long *expected; 308 const int nbits; 309 const int flags; 310 }; 311 312 static const struct test_bitmap_parselist parselist_tests[] __initconst = { 313 #define step (sizeof(u64) / sizeof(unsigned long)) 314 315 {0, "0", &exp1[0], 8, 0}, 316 {0, "1", &exp1[1 * step], 8, 0}, 317 {0, "0-15", &exp1[2 * step], 32, 0}, 318 {0, "16-31", &exp1[3 * step], 32, 0}, 319 {0, "0-31:1/2", &exp1[4 * step], 32, 0}, 320 {0, "1-31:1/2", &exp1[5 * step], 32, 0}, 321 {0, "0-31:1/4", &exp1[6 * step], 32, 0}, 322 {0, "1-31:1/4", &exp1[7 * step], 32, 0}, 323 {0, "0-31:4/4", &exp1[8 * step], 32, 0}, 324 {0, "1-31:4/4", &exp1[9 * step], 32, 0}, 325 {0, "0-31:1/4,32-63:2/4", &exp1[10 * step], 64, 0}, 326 {0, "0-31:3/4,32-63:4/4", &exp1[11 * step], 64, 0}, 327 {0, " ,, 0-31:3/4 ,, 32-63:4/4 ,, ", &exp1[11 * step], 64, 0}, 328 329 {0, "0-31:1/4,32-63:2/4,64-95:3/4,96-127:4/4", exp2, 128, 0}, 330 331 {0, "0-2047:128/256", NULL, 2048, PARSE_TIME}, 332 333 {0, "", &exp1[12 * step], 8, 0}, 334 {0, "\n", &exp1[12 * step], 8, 0}, 335 {0, ",, ,, , , ,", &exp1[12 * step], 8, 0}, 336 {0, " , ,, , , ", &exp1[12 * step], 8, 0}, 337 {0, " , ,, , , \n", &exp1[12 * step], 8, 0}, 338 339 {0, "0-0", &exp1[0], 32, 0}, 340 {0, "1-1", &exp1[1 * step], 32, 0}, 341 {0, "15-15", &exp1[13 * step], 32, 0}, 342 {0, "31-31", &exp1[14 * step], 32, 0}, 343 344 {0, "0-0:0/1", &exp1[12 * step], 32, 0}, 345 {0, "0-0:1/1", &exp1[0], 32, 0}, 346 {0, "0-0:1/31", &exp1[0], 32, 0}, 347 {0, "0-0:31/31", &exp1[0], 32, 0}, 348 {0, "1-1:1/1", &exp1[1 * step], 32, 0}, 349 {0, "0-15:16/31", &exp1[2 * step], 32, 0}, 350 {0, "15-15:1/2", &exp1[13 * step], 32, 0}, 351 {0, "15-15:31/31", &exp1[13 * step], 32, 0}, 352 {0, "15-31:1/31", &exp1[13 * step], 32, 0}, 353 {0, "16-31:16/31", &exp1[3 * step], 32, 0}, 354 {0, "31-31:31/31", &exp1[14 * step], 32, 0}, 355 356 {0, "N-N", &exp1[14 * step], 32, 0}, 357 {0, "0-0:1/N", &exp1[0], 32, 0}, 358 {0, "0-0:N/N", &exp1[0], 32, 0}, 359 {0, "0-15:16/N", &exp1[2 * step], 32, 0}, 360 {0, "15-15:N/N", &exp1[13 * step], 32, 0}, 361 {0, "15-N:1/N", &exp1[13 * step], 32, 0}, 362 {0, "16-N:16/N", &exp1[3 * step], 32, 0}, 363 {0, "N-N:N/N", &exp1[14 * step], 32, 0}, 364 365 {0, "0-N:1/3,1-N:1/3,2-N:1/3", &exp1[8 * step], 32, 0}, 366 {0, "0-31:1/3,1-31:1/3,2-31:1/3", &exp1[8 * step], 32, 0}, 367 {0, "1-10:8/12,8-31:24/29,0-31:0/3", &exp1[9 * step], 32, 0}, 368 369 {0, "all", &exp1[8 * step], 32, 0}, 370 {0, "0, 1, all, ", &exp1[8 * step], 32, 0}, 371 {0, "all:1/2", &exp1[4 * step], 32, 0}, 372 {0, "ALL:1/2", &exp1[4 * step], 32, 0}, 373 {-EINVAL, "al", NULL, 8, 0}, 374 {-EINVAL, "alll", NULL, 8, 0}, 375 376 {-EINVAL, "-1", NULL, 8, 0}, 377 {-EINVAL, "-0", NULL, 8, 0}, 378 {-EINVAL, "10-1", NULL, 8, 0}, 379 {-ERANGE, "8-8", NULL, 8, 0}, 380 {-ERANGE, "0-31", NULL, 8, 0}, 381 {-EINVAL, "0-31:", NULL, 32, 0}, 382 {-EINVAL, "0-31:0", NULL, 32, 0}, 383 {-EINVAL, "0-31:0/", NULL, 32, 0}, 384 {-EINVAL, "0-31:0/0", NULL, 32, 0}, 385 {-EINVAL, "0-31:1/0", NULL, 32, 0}, 386 {-EINVAL, "0-31:10/1", NULL, 32, 0}, 387 {-EOVERFLOW, "0-98765432123456789:10/1", NULL, 8, 0}, 388 389 {-EINVAL, "a-31", NULL, 8, 0}, 390 {-EINVAL, "0-a1", NULL, 8, 0}, 391 {-EINVAL, "a-31:10/1", NULL, 8, 0}, 392 {-EINVAL, "0-31:a/1", NULL, 8, 0}, 393 {-EINVAL, "0-\n", NULL, 8, 0}, 394 395 }; 396 397 static void __init test_bitmap_parselist(void) 398 { 399 int i; 400 int err; 401 ktime_t time; 402 DECLARE_BITMAP(bmap, 2048); 403 404 for (i = 0; i < ARRAY_SIZE(parselist_tests); i++) { 405 #define ptest parselist_tests[i] 406 407 time = ktime_get(); 408 err = bitmap_parselist(ptest.in, bmap, ptest.nbits); 409 time = ktime_get() - time; 410 411 if (err != ptest.errno) { 412 pr_err("parselist: %d: input is %s, errno is %d, expected %d\n", 413 i, ptest.in, err, ptest.errno); 414 continue; 415 } 416 417 if (!err && ptest.expected 418 && !__bitmap_equal(bmap, ptest.expected, ptest.nbits)) { 419 pr_err("parselist: %d: input is %s, result is 0x%lx, expected 0x%lx\n", 420 i, ptest.in, bmap[0], 421 *ptest.expected); 422 continue; 423 } 424 425 if (ptest.flags & PARSE_TIME) 426 pr_err("parselist: %d: input is '%s' OK, Time: %llu\n", 427 i, ptest.in, time); 428 429 #undef ptest 430 } 431 } 432 433 static const unsigned long parse_test[] __initconst = { 434 BITMAP_FROM_U64(0), 435 BITMAP_FROM_U64(1), 436 BITMAP_FROM_U64(0xdeadbeef), 437 BITMAP_FROM_U64(0x100000000ULL), 438 }; 439 440 static const unsigned long parse_test2[] __initconst = { 441 BITMAP_FROM_U64(0x100000000ULL), BITMAP_FROM_U64(0xdeadbeef), 442 BITMAP_FROM_U64(0x100000000ULL), BITMAP_FROM_U64(0xbaadf00ddeadbeef), 443 BITMAP_FROM_U64(0x100000000ULL), BITMAP_FROM_U64(0x0badf00ddeadbeef), 444 }; 445 446 static const struct test_bitmap_parselist parse_tests[] __initconst = { 447 {0, "", &parse_test[0 * step], 32, 0}, 448 {0, " ", &parse_test[0 * step], 32, 0}, 449 {0, "0", &parse_test[0 * step], 32, 0}, 450 {0, "0\n", &parse_test[0 * step], 32, 0}, 451 {0, "1", &parse_test[1 * step], 32, 0}, 452 {0, "deadbeef", &parse_test[2 * step], 32, 0}, 453 {0, "1,0", &parse_test[3 * step], 33, 0}, 454 {0, "deadbeef,\n,0,1", &parse_test[2 * step], 96, 0}, 455 456 {0, "deadbeef,1,0", &parse_test2[0 * 2 * step], 96, 0}, 457 {0, "baadf00d,deadbeef,1,0", &parse_test2[1 * 2 * step], 128, 0}, 458 {0, "badf00d,deadbeef,1,0", &parse_test2[2 * 2 * step], 124, 0}, 459 {0, "badf00d,deadbeef,1,0", &parse_test2[2 * 2 * step], 124, NO_LEN}, 460 {0, " badf00d,deadbeef,1,0 ", &parse_test2[2 * 2 * step], 124, 0}, 461 {0, " , badf00d,deadbeef,1,0 , ", &parse_test2[2 * 2 * step], 124, 0}, 462 {0, " , badf00d, ,, ,,deadbeef,1,0 , ", &parse_test2[2 * 2 * step], 124, 0}, 463 464 {-EINVAL, "goodfood,deadbeef,1,0", NULL, 128, 0}, 465 {-EOVERFLOW, "3,0", NULL, 33, 0}, 466 {-EOVERFLOW, "123badf00d,deadbeef,1,0", NULL, 128, 0}, 467 {-EOVERFLOW, "badf00d,deadbeef,1,0", NULL, 90, 0}, 468 {-EOVERFLOW, "fbadf00d,deadbeef,1,0", NULL, 95, 0}, 469 {-EOVERFLOW, "badf00d,deadbeef,1,0", NULL, 100, 0}, 470 #undef step 471 }; 472 473 static void __init test_bitmap_parse(void) 474 { 475 int i; 476 int err; 477 ktime_t time; 478 DECLARE_BITMAP(bmap, 2048); 479 480 for (i = 0; i < ARRAY_SIZE(parse_tests); i++) { 481 struct test_bitmap_parselist test = parse_tests[i]; 482 size_t len = test.flags & NO_LEN ? UINT_MAX : strlen(test.in); 483 484 time = ktime_get(); 485 err = bitmap_parse(test.in, len, bmap, test.nbits); 486 time = ktime_get() - time; 487 488 if (err != test.errno) { 489 pr_err("parse: %d: input is %s, errno is %d, expected %d\n", 490 i, test.in, err, test.errno); 491 continue; 492 } 493 494 if (!err && test.expected 495 && !__bitmap_equal(bmap, test.expected, test.nbits)) { 496 pr_err("parse: %d: input is %s, result is 0x%lx, expected 0x%lx\n", 497 i, test.in, bmap[0], 498 *test.expected); 499 continue; 500 } 501 502 if (test.flags & PARSE_TIME) 503 pr_err("parse: %d: input is '%s' OK, Time: %llu\n", 504 i, test.in, time); 505 } 506 } 507 508 #define EXP1_IN_BITS (sizeof(exp1) * 8) 509 510 static void __init test_bitmap_arr32(void) 511 { 512 unsigned int nbits, next_bit; 513 u32 arr[EXP1_IN_BITS / 32]; 514 DECLARE_BITMAP(bmap2, EXP1_IN_BITS); 515 516 memset(arr, 0xa5, sizeof(arr)); 517 518 for (nbits = 0; nbits < EXP1_IN_BITS; ++nbits) { 519 bitmap_to_arr32(arr, exp1, nbits); 520 bitmap_from_arr32(bmap2, arr, nbits); 521 expect_eq_bitmap(bmap2, exp1, nbits); 522 523 next_bit = find_next_bit(bmap2, 524 round_up(nbits, BITS_PER_LONG), nbits); 525 if (next_bit < round_up(nbits, BITS_PER_LONG)) 526 pr_err("bitmap_copy_arr32(nbits == %d:" 527 " tail is not safely cleared: %d\n", 528 nbits, next_bit); 529 530 if (nbits < EXP1_IN_BITS - 32) 531 expect_eq_uint(arr[DIV_ROUND_UP(nbits, 32)], 532 0xa5a5a5a5); 533 } 534 } 535 536 static void noinline __init test_mem_optimisations(void) 537 { 538 DECLARE_BITMAP(bmap1, 1024); 539 DECLARE_BITMAP(bmap2, 1024); 540 unsigned int start, nbits; 541 542 for (start = 0; start < 1024; start += 8) { 543 for (nbits = 0; nbits < 1024 - start; nbits += 8) { 544 memset(bmap1, 0x5a, sizeof(bmap1)); 545 memset(bmap2, 0x5a, sizeof(bmap2)); 546 547 bitmap_set(bmap1, start, nbits); 548 __bitmap_set(bmap2, start, nbits); 549 if (!bitmap_equal(bmap1, bmap2, 1024)) { 550 printk("set not equal %d %d\n", start, nbits); 551 failed_tests++; 552 } 553 if (!__bitmap_equal(bmap1, bmap2, 1024)) { 554 printk("set not __equal %d %d\n", start, nbits); 555 failed_tests++; 556 } 557 558 bitmap_clear(bmap1, start, nbits); 559 __bitmap_clear(bmap2, start, nbits); 560 if (!bitmap_equal(bmap1, bmap2, 1024)) { 561 printk("clear not equal %d %d\n", start, nbits); 562 failed_tests++; 563 } 564 if (!__bitmap_equal(bmap1, bmap2, 1024)) { 565 printk("clear not __equal %d %d\n", start, 566 nbits); 567 failed_tests++; 568 } 569 } 570 } 571 } 572 573 static const unsigned char clump_exp[] __initconst = { 574 0x01, /* 1 bit set */ 575 0x02, /* non-edge 1 bit set */ 576 0x00, /* zero bits set */ 577 0x38, /* 3 bits set across 4-bit boundary */ 578 0x38, /* Repeated clump */ 579 0x0F, /* 4 bits set */ 580 0xFF, /* all bits set */ 581 0x05, /* non-adjacent 2 bits set */ 582 }; 583 584 static void __init test_for_each_set_clump8(void) 585 { 586 #define CLUMP_EXP_NUMBITS 64 587 DECLARE_BITMAP(bits, CLUMP_EXP_NUMBITS); 588 unsigned int start; 589 unsigned long clump; 590 591 /* set bitmap to test case */ 592 bitmap_zero(bits, CLUMP_EXP_NUMBITS); 593 bitmap_set(bits, 0, 1); /* 0x01 */ 594 bitmap_set(bits, 9, 1); /* 0x02 */ 595 bitmap_set(bits, 27, 3); /* 0x28 */ 596 bitmap_set(bits, 35, 3); /* 0x28 */ 597 bitmap_set(bits, 40, 4); /* 0x0F */ 598 bitmap_set(bits, 48, 8); /* 0xFF */ 599 bitmap_set(bits, 56, 1); /* 0x05 - part 1 */ 600 bitmap_set(bits, 58, 1); /* 0x05 - part 2 */ 601 602 for_each_set_clump8(start, clump, bits, CLUMP_EXP_NUMBITS) 603 expect_eq_clump8(start, CLUMP_EXP_NUMBITS, clump_exp, &clump); 604 } 605 606 struct test_bitmap_cut { 607 unsigned int first; 608 unsigned int cut; 609 unsigned int nbits; 610 unsigned long in[4]; 611 unsigned long expected[4]; 612 }; 613 614 static struct test_bitmap_cut test_cut[] = { 615 { 0, 0, 8, { 0x0000000aUL, }, { 0x0000000aUL, }, }, 616 { 0, 0, 32, { 0xdadadeadUL, }, { 0xdadadeadUL, }, }, 617 { 0, 3, 8, { 0x000000aaUL, }, { 0x00000015UL, }, }, 618 { 3, 3, 8, { 0x000000aaUL, }, { 0x00000012UL, }, }, 619 { 0, 1, 32, { 0xa5a5a5a5UL, }, { 0x52d2d2d2UL, }, }, 620 { 0, 8, 32, { 0xdeadc0deUL, }, { 0x00deadc0UL, }, }, 621 { 1, 1, 32, { 0x5a5a5a5aUL, }, { 0x2d2d2d2cUL, }, }, 622 { 0, 15, 32, { 0xa5a5a5a5UL, }, { 0x00014b4bUL, }, }, 623 { 0, 16, 32, { 0xa5a5a5a5UL, }, { 0x0000a5a5UL, }, }, 624 { 15, 15, 32, { 0xa5a5a5a5UL, }, { 0x000125a5UL, }, }, 625 { 15, 16, 32, { 0xa5a5a5a5UL, }, { 0x0000a5a5UL, }, }, 626 { 16, 15, 32, { 0xa5a5a5a5UL, }, { 0x0001a5a5UL, }, }, 627 628 { BITS_PER_LONG, BITS_PER_LONG, BITS_PER_LONG, 629 { 0xa5a5a5a5UL, 0xa5a5a5a5UL, }, 630 { 0xa5a5a5a5UL, 0xa5a5a5a5UL, }, 631 }, 632 { 1, BITS_PER_LONG - 1, BITS_PER_LONG, 633 { 0xa5a5a5a5UL, 0xa5a5a5a5UL, }, 634 { 0x00000001UL, 0x00000001UL, }, 635 }, 636 637 { 0, BITS_PER_LONG * 2, BITS_PER_LONG * 2 + 1, 638 { 0xa5a5a5a5UL, 0x00000001UL, 0x00000001UL, 0x00000001UL }, 639 { 0x00000001UL, }, 640 }, 641 { 16, BITS_PER_LONG * 2 + 1, BITS_PER_LONG * 2 + 1 + 16, 642 { 0x0000ffffUL, 0x5a5a5a5aUL, 0x5a5a5a5aUL, 0x5a5a5a5aUL }, 643 { 0x2d2dffffUL, }, 644 }, 645 }; 646 647 static void __init test_bitmap_cut(void) 648 { 649 unsigned long b[5], *in = &b[1], *out = &b[0]; /* Partial overlap */ 650 int i; 651 652 for (i = 0; i < ARRAY_SIZE(test_cut); i++) { 653 struct test_bitmap_cut *t = &test_cut[i]; 654 655 memcpy(in, t->in, sizeof(t->in)); 656 657 bitmap_cut(out, in, t->first, t->cut, t->nbits); 658 659 expect_eq_bitmap(t->expected, out, t->nbits); 660 } 661 } 662 663 static void __init selftest(void) 664 { 665 test_zero_clear(); 666 test_fill_set(); 667 test_copy(); 668 test_replace(); 669 test_bitmap_arr32(); 670 test_bitmap_parse(); 671 test_bitmap_parselist(); 672 test_mem_optimisations(); 673 test_for_each_set_clump8(); 674 test_bitmap_cut(); 675 } 676 677 KSTM_MODULE_LOADERS(test_bitmap); 678 MODULE_AUTHOR("david decotigny <david.decotigny@googlers.com>"); 679 MODULE_LICENSE("GPL"); 680