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