1 // SPDX-License-Identifier: GPL-2.0-only
3 * Test cases for bitmap API.
6 #define pr_fmt(fmt) KBUILD_MODNAME ": " fmt
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>
17 #include "../tools/testing/selftests/kselftest_module.h"
19 #define EXP1_IN_BITS (sizeof(exp1) * 8)
21 KSTM_MODULE_GLOBALS();
23 static char pbl_buffer[PAGE_SIZE] __initdata;
24 static char print_buf[PAGE_SIZE * 2] __initdata;
26 static const unsigned long exp1[] __initconst = {
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),
40 BITMAP_FROM_U64(0x00008000),
41 BITMAP_FROM_U64(0x80000000),
44 static const unsigned long exp2[] __initconst = {
45 BITMAP_FROM_U64(0x3333333311111111ULL),
46 BITMAP_FROM_U64(0xffffffff77777777ULL),
49 /* Fibonacci sequence */
50 static const unsigned long exp2_to_exp3_mask[] __initconst = {
51 BITMAP_FROM_U64(0x008000020020212eULL),
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),
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),
63 __check_eq_uint(const char *srcfile, unsigned int line,
64 const unsigned int exp_uint, unsigned int x)
67 pr_err("[%s:%u] expected %u, got %u\n",
68 srcfile, line, exp_uint, x);
76 __check_eq_bitmap(const char *srcfile, unsigned int line,
77 const unsigned long *exp_bmap, const unsigned long *bmap,
80 if (!bitmap_equal(exp_bmap, bmap, nbits)) {
81 pr_warn("[%s:%u] bitmaps contents differ: expected \"%*pbl\", got \"%*pbl\"\n",
83 nbits, exp_bmap, nbits, bmap);
90 __check_eq_pbl(const char *srcfile, unsigned int line,
91 const char *expected_pbl,
92 const unsigned long *bitmap, unsigned int nbits)
94 snprintf(pbl_buffer, sizeof(pbl_buffer), "%*pbl", nbits, bitmap);
95 if (strcmp(expected_pbl, pbl_buffer)) {
96 pr_warn("[%s:%u] expected \"%s\", got \"%s\"\n",
98 expected_pbl, pbl_buffer);
105 __check_eq_u32_array(const char *srcfile, unsigned int line,
106 const u32 *exp_arr, unsigned int exp_len,
107 const u32 *arr, unsigned int len) __used;
109 __check_eq_u32_array(const char *srcfile, unsigned int line,
110 const u32 *exp_arr, unsigned int exp_len,
111 const u32 *arr, unsigned int len)
113 if (exp_len != len) {
114 pr_warn("[%s:%u] array length differ: expected %u, got %u\n",
120 if (memcmp(exp_arr, arr, len*sizeof(*arr))) {
121 pr_warn("[%s:%u] array contents differ\n", srcfile, line);
122 print_hex_dump(KERN_WARNING, " exp: ", DUMP_PREFIX_OFFSET,
123 32, 4, exp_arr, exp_len*sizeof(*exp_arr), false);
124 print_hex_dump(KERN_WARNING, " got: ", DUMP_PREFIX_OFFSET,
125 32, 4, arr, len*sizeof(*arr), false);
132 static bool __init __check_eq_clump8(const char *srcfile, unsigned int line,
133 const unsigned int offset,
134 const unsigned int size,
135 const unsigned char *const clump_exp,
136 const unsigned long *const clump)
140 if (offset >= size) {
141 pr_warn("[%s:%u] bit offset for clump out-of-bounds: expected less than %u, got %u\n",
142 srcfile, line, size, offset);
146 exp = clump_exp[offset / 8];
148 pr_warn("[%s:%u] bit offset for zero clump: expected nonzero clump, got bit offset %u with clump value 0",
149 srcfile, line, offset);
154 pr_warn("[%s:%u] expected clump value of 0x%lX, got clump value of 0x%lX",
155 srcfile, line, exp, *clump);
163 __check_eq_str(const char *srcfile, unsigned int line,
164 const char *exp_str, const char *str,
169 eq = strncmp(exp_str, str, len) == 0;
171 pr_err("[%s:%u] expected %s, got %s\n", srcfile, line, exp_str, str);
176 #define __expect_eq(suffix, ...) \
180 if (!__check_eq_ ## suffix(__FILE__, __LINE__, \
188 #define expect_eq_uint(...) __expect_eq(uint, ##__VA_ARGS__)
189 #define expect_eq_bitmap(...) __expect_eq(bitmap, ##__VA_ARGS__)
190 #define expect_eq_pbl(...) __expect_eq(pbl, ##__VA_ARGS__)
191 #define expect_eq_u32_array(...) __expect_eq(u32_array, ##__VA_ARGS__)
192 #define expect_eq_clump8(...) __expect_eq(clump8, ##__VA_ARGS__)
193 #define expect_eq_str(...) __expect_eq(str, ##__VA_ARGS__)
195 static void __init test_zero_clear(void)
197 DECLARE_BITMAP(bmap, 1024);
199 /* Known way to set all bits */
200 memset(bmap, 0xff, 128);
202 expect_eq_pbl("0-22", bmap, 23);
203 expect_eq_pbl("0-1023", bmap, 1024);
205 /* single-word bitmaps */
206 bitmap_clear(bmap, 0, 9);
207 expect_eq_pbl("9-1023", bmap, 1024);
209 bitmap_zero(bmap, 35);
210 expect_eq_pbl("64-1023", bmap, 1024);
212 /* cross boundaries operations */
213 bitmap_clear(bmap, 79, 19);
214 expect_eq_pbl("64-78,98-1023", bmap, 1024);
216 bitmap_zero(bmap, 115);
217 expect_eq_pbl("128-1023", bmap, 1024);
219 /* Zeroing entire area */
220 bitmap_zero(bmap, 1024);
221 expect_eq_pbl("", bmap, 1024);
224 static void __init test_find_nth_bit(void)
226 unsigned long b, bit, cnt = 0;
227 DECLARE_BITMAP(bmap, 64 * 3);
229 bitmap_zero(bmap, 64 * 3);
237 __set_bit(123, bmap);
239 expect_eq_uint(10, find_nth_bit(bmap, 64 * 3, 0));
240 expect_eq_uint(20, find_nth_bit(bmap, 64 * 3, 1));
241 expect_eq_uint(30, find_nth_bit(bmap, 64 * 3, 2));
242 expect_eq_uint(40, find_nth_bit(bmap, 64 * 3, 3));
243 expect_eq_uint(50, find_nth_bit(bmap, 64 * 3, 4));
244 expect_eq_uint(60, find_nth_bit(bmap, 64 * 3, 5));
245 expect_eq_uint(80, find_nth_bit(bmap, 64 * 3, 6));
246 expect_eq_uint(123, find_nth_bit(bmap, 64 * 3, 7));
247 expect_eq_uint(64 * 3, find_nth_bit(bmap, 64 * 3, 8));
249 expect_eq_uint(10, find_nth_bit(bmap, 64 * 3 - 1, 0));
250 expect_eq_uint(20, find_nth_bit(bmap, 64 * 3 - 1, 1));
251 expect_eq_uint(30, find_nth_bit(bmap, 64 * 3 - 1, 2));
252 expect_eq_uint(40, find_nth_bit(bmap, 64 * 3 - 1, 3));
253 expect_eq_uint(50, find_nth_bit(bmap, 64 * 3 - 1, 4));
254 expect_eq_uint(60, find_nth_bit(bmap, 64 * 3 - 1, 5));
255 expect_eq_uint(80, find_nth_bit(bmap, 64 * 3 - 1, 6));
256 expect_eq_uint(123, find_nth_bit(bmap, 64 * 3 - 1, 7));
257 expect_eq_uint(64 * 3 - 1, find_nth_bit(bmap, 64 * 3 - 1, 8));
259 for_each_set_bit(bit, exp1, EXP1_IN_BITS) {
260 b = find_nth_bit(exp1, EXP1_IN_BITS, cnt++);
261 expect_eq_uint(b, bit);
265 static void __init test_fill_set(void)
267 DECLARE_BITMAP(bmap, 1024);
269 /* Known way to clear all bits */
270 memset(bmap, 0x00, 128);
272 expect_eq_pbl("", bmap, 23);
273 expect_eq_pbl("", bmap, 1024);
275 /* single-word bitmaps */
276 bitmap_set(bmap, 0, 9);
277 expect_eq_pbl("0-8", bmap, 1024);
279 bitmap_fill(bmap, 35);
280 expect_eq_pbl("0-63", bmap, 1024);
282 /* cross boundaries operations */
283 bitmap_set(bmap, 79, 19);
284 expect_eq_pbl("0-63,79-97", bmap, 1024);
286 bitmap_fill(bmap, 115);
287 expect_eq_pbl("0-127", bmap, 1024);
289 /* Zeroing entire area */
290 bitmap_fill(bmap, 1024);
291 expect_eq_pbl("0-1023", bmap, 1024);
294 static void __init test_copy(void)
296 DECLARE_BITMAP(bmap1, 1024);
297 DECLARE_BITMAP(bmap2, 1024);
299 bitmap_zero(bmap1, 1024);
300 bitmap_zero(bmap2, 1024);
302 /* single-word bitmaps */
303 bitmap_set(bmap1, 0, 19);
304 bitmap_copy(bmap2, bmap1, 23);
305 expect_eq_pbl("0-18", bmap2, 1024);
307 bitmap_set(bmap2, 0, 23);
308 bitmap_copy(bmap2, bmap1, 23);
309 expect_eq_pbl("0-18", bmap2, 1024);
311 /* multi-word bitmaps */
312 bitmap_set(bmap1, 0, 109);
313 bitmap_copy(bmap2, bmap1, 1024);
314 expect_eq_pbl("0-108", bmap2, 1024);
316 bitmap_fill(bmap2, 1024);
317 bitmap_copy(bmap2, bmap1, 1024);
318 expect_eq_pbl("0-108", bmap2, 1024);
320 /* the following tests assume a 32- or 64-bit arch (even 128b
324 bitmap_fill(bmap2, 1024);
325 bitmap_copy(bmap2, bmap1, 109); /* ... but 0-padded til word length */
326 expect_eq_pbl("0-108,128-1023", bmap2, 1024);
328 bitmap_fill(bmap2, 1024);
329 bitmap_copy(bmap2, bmap1, 97); /* ... but aligned on word length */
330 expect_eq_pbl("0-108,128-1023", bmap2, 1024);
333 static void __init test_bitmap_region(void)
337 DECLARE_BITMAP(bmap, 1000);
339 bitmap_zero(bmap, 1000);
341 for (order = 0; order < 10; order++) {
342 pos = bitmap_find_free_region(bmap, 1000, order);
344 expect_eq_uint(pos, 0);
346 expect_eq_uint(pos, order < 9 ? BIT(order) : -ENOMEM);
349 bitmap_release_region(bmap, 0, 0);
350 for (order = 1; order < 9; order++)
351 bitmap_release_region(bmap, BIT(order), order);
353 expect_eq_uint(bitmap_weight(bmap, 1000), 0);
356 #define EXP2_IN_BITS (sizeof(exp2) * 8)
358 static void __init test_replace(void)
360 unsigned int nbits = 64;
361 unsigned int nlongs = DIV_ROUND_UP(nbits, BITS_PER_LONG);
362 DECLARE_BITMAP(bmap, 1024);
364 BUILD_BUG_ON(EXP2_IN_BITS < nbits * 2);
366 bitmap_zero(bmap, 1024);
367 bitmap_replace(bmap, &exp2[0 * nlongs], &exp2[1 * nlongs], exp2_to_exp3_mask, nbits);
368 expect_eq_bitmap(bmap, exp3_0_1, nbits);
370 bitmap_zero(bmap, 1024);
371 bitmap_replace(bmap, &exp2[1 * nlongs], &exp2[0 * nlongs], exp2_to_exp3_mask, nbits);
372 expect_eq_bitmap(bmap, exp3_1_0, nbits);
374 bitmap_fill(bmap, 1024);
375 bitmap_replace(bmap, &exp2[0 * nlongs], &exp2[1 * nlongs], exp2_to_exp3_mask, nbits);
376 expect_eq_bitmap(bmap, exp3_0_1, nbits);
378 bitmap_fill(bmap, 1024);
379 bitmap_replace(bmap, &exp2[1 * nlongs], &exp2[0 * nlongs], exp2_to_exp3_mask, nbits);
380 expect_eq_bitmap(bmap, exp3_1_0, nbits);
383 static const unsigned long sg_mask[] __initconst = {
384 BITMAP_FROM_U64(0x000000000000035aULL),
387 static const unsigned long sg_src[] __initconst = {
388 BITMAP_FROM_U64(0x0000000000000667ULL),
391 static const unsigned long sg_gather_exp[] __initconst = {
392 BITMAP_FROM_U64(0x0000000000000029ULL),
395 static const unsigned long sg_scatter_exp[] __initconst = {
396 BITMAP_FROM_U64(0x000000000000021aULL),
399 static void __init test_bitmap_sg(void)
401 unsigned int nbits = 64;
402 DECLARE_BITMAP(bmap_gather, 100);
403 DECLARE_BITMAP(bmap_scatter, 100);
404 DECLARE_BITMAP(bmap_tmp, 100);
405 DECLARE_BITMAP(bmap_res, 100);
407 /* Simple gather call */
408 bitmap_zero(bmap_gather, 100);
409 bitmap_gather(bmap_gather, sg_src, sg_mask, nbits);
410 expect_eq_bitmap(sg_gather_exp, bmap_gather, nbits);
412 /* Simple scatter call */
413 bitmap_zero(bmap_scatter, 100);
414 bitmap_scatter(bmap_scatter, sg_src, sg_mask, nbits);
415 expect_eq_bitmap(sg_scatter_exp, bmap_scatter, nbits);
417 /* Scatter/gather relationship */
418 bitmap_zero(bmap_tmp, 100);
419 bitmap_gather(bmap_tmp, bmap_scatter, sg_mask, nbits);
420 bitmap_scatter(bmap_res, bmap_tmp, sg_mask, nbits);
421 expect_eq_bitmap(bmap_scatter, bmap_res, nbits);
424 #define PARSE_TIME 0x1
427 struct test_bitmap_parselist{
430 const unsigned long *expected;
435 static const struct test_bitmap_parselist parselist_tests[] __initconst = {
436 #define step (sizeof(u64) / sizeof(unsigned long))
438 {0, "0", &exp1[0], 8, 0},
439 {0, "1", &exp1[1 * step], 8, 0},
440 {0, "0-15", &exp1[2 * step], 32, 0},
441 {0, "16-31", &exp1[3 * step], 32, 0},
442 {0, "0-31:1/2", &exp1[4 * step], 32, 0},
443 {0, "1-31:1/2", &exp1[5 * step], 32, 0},
444 {0, "0-31:1/4", &exp1[6 * step], 32, 0},
445 {0, "1-31:1/4", &exp1[7 * step], 32, 0},
446 {0, "0-31:4/4", &exp1[8 * step], 32, 0},
447 {0, "1-31:4/4", &exp1[9 * step], 32, 0},
448 {0, "0-31:1/4,32-63:2/4", &exp1[10 * step], 64, 0},
449 {0, "0-31:3/4,32-63:4/4", &exp1[11 * step], 64, 0},
450 {0, " ,, 0-31:3/4 ,, 32-63:4/4 ,, ", &exp1[11 * step], 64, 0},
452 {0, "0-31:1/4,32-63:2/4,64-95:3/4,96-127:4/4", exp2, 128, 0},
454 {0, "0-2047:128/256", NULL, 2048, PARSE_TIME},
456 {0, "", &exp1[12 * step], 8, 0},
457 {0, "\n", &exp1[12 * step], 8, 0},
458 {0, ",, ,, , , ,", &exp1[12 * step], 8, 0},
459 {0, " , ,, , , ", &exp1[12 * step], 8, 0},
460 {0, " , ,, , , \n", &exp1[12 * step], 8, 0},
462 {0, "0-0", &exp1[0], 32, 0},
463 {0, "1-1", &exp1[1 * step], 32, 0},
464 {0, "15-15", &exp1[13 * step], 32, 0},
465 {0, "31-31", &exp1[14 * step], 32, 0},
467 {0, "0-0:0/1", &exp1[12 * step], 32, 0},
468 {0, "0-0:1/1", &exp1[0], 32, 0},
469 {0, "0-0:1/31", &exp1[0], 32, 0},
470 {0, "0-0:31/31", &exp1[0], 32, 0},
471 {0, "1-1:1/1", &exp1[1 * step], 32, 0},
472 {0, "0-15:16/31", &exp1[2 * step], 32, 0},
473 {0, "15-15:1/2", &exp1[13 * step], 32, 0},
474 {0, "15-15:31/31", &exp1[13 * step], 32, 0},
475 {0, "15-31:1/31", &exp1[13 * step], 32, 0},
476 {0, "16-31:16/31", &exp1[3 * step], 32, 0},
477 {0, "31-31:31/31", &exp1[14 * step], 32, 0},
479 {0, "N-N", &exp1[14 * step], 32, 0},
480 {0, "0-0:1/N", &exp1[0], 32, 0},
481 {0, "0-0:N/N", &exp1[0], 32, 0},
482 {0, "0-15:16/N", &exp1[2 * step], 32, 0},
483 {0, "15-15:N/N", &exp1[13 * step], 32, 0},
484 {0, "15-N:1/N", &exp1[13 * step], 32, 0},
485 {0, "16-N:16/N", &exp1[3 * step], 32, 0},
486 {0, "N-N:N/N", &exp1[14 * step], 32, 0},
488 {0, "0-N:1/3,1-N:1/3,2-N:1/3", &exp1[8 * step], 32, 0},
489 {0, "0-31:1/3,1-31:1/3,2-31:1/3", &exp1[8 * step], 32, 0},
490 {0, "1-10:8/12,8-31:24/29,0-31:0/3", &exp1[9 * step], 32, 0},
492 {0, "all", &exp1[8 * step], 32, 0},
493 {0, "0, 1, all, ", &exp1[8 * step], 32, 0},
494 {0, "all:1/2", &exp1[4 * step], 32, 0},
495 {0, "ALL:1/2", &exp1[4 * step], 32, 0},
496 {-EINVAL, "al", NULL, 8, 0},
497 {-EINVAL, "alll", NULL, 8, 0},
499 {-EINVAL, "-1", NULL, 8, 0},
500 {-EINVAL, "-0", NULL, 8, 0},
501 {-EINVAL, "10-1", NULL, 8, 0},
502 {-ERANGE, "8-8", NULL, 8, 0},
503 {-ERANGE, "0-31", NULL, 8, 0},
504 {-EINVAL, "0-31:", NULL, 32, 0},
505 {-EINVAL, "0-31:0", NULL, 32, 0},
506 {-EINVAL, "0-31:0/", NULL, 32, 0},
507 {-EINVAL, "0-31:0/0", NULL, 32, 0},
508 {-EINVAL, "0-31:1/0", NULL, 32, 0},
509 {-EINVAL, "0-31:10/1", NULL, 32, 0},
510 {-EOVERFLOW, "0-98765432123456789:10/1", NULL, 8, 0},
512 {-EINVAL, "a-31", NULL, 8, 0},
513 {-EINVAL, "0-a1", NULL, 8, 0},
514 {-EINVAL, "a-31:10/1", NULL, 8, 0},
515 {-EINVAL, "0-31:a/1", NULL, 8, 0},
516 {-EINVAL, "0-\n", NULL, 8, 0},
520 static void __init test_bitmap_parselist(void)
525 DECLARE_BITMAP(bmap, 2048);
527 for (i = 0; i < ARRAY_SIZE(parselist_tests); i++) {
528 #define ptest parselist_tests[i]
531 err = bitmap_parselist(ptest.in, bmap, ptest.nbits);
532 time = ktime_get() - time;
534 if (err != ptest.errno) {
535 pr_err("parselist: %d: input is %s, errno is %d, expected %d\n",
536 i, ptest.in, err, ptest.errno);
541 if (!err && ptest.expected
542 && !__bitmap_equal(bmap, ptest.expected, ptest.nbits)) {
543 pr_err("parselist: %d: input is %s, result is 0x%lx, expected 0x%lx\n",
544 i, ptest.in, bmap[0],
550 if (ptest.flags & PARSE_TIME)
551 pr_err("parselist: %d: input is '%s' OK, Time: %llu\n",
558 static void __init test_bitmap_printlist(void)
560 unsigned long *bmap = kmalloc(PAGE_SIZE, GFP_KERNEL);
561 char *buf = kmalloc(PAGE_SIZE, GFP_KERNEL);
569 memset(bmap, -1, PAGE_SIZE);
570 slen = snprintf(expected, 256, "0-%ld", PAGE_SIZE * 8 - 1);
575 ret = bitmap_print_to_pagebuf(true, buf, bmap, PAGE_SIZE * 8);
576 time = ktime_get() - time;
578 if (ret != slen + 1) {
579 pr_err("bitmap_print_to_pagebuf: result is %d, expected %d\n", ret, slen);
584 if (strncmp(buf, expected, slen)) {
585 pr_err("bitmap_print_to_pagebuf: result is %s, expected %s\n", buf, expected);
590 pr_err("bitmap_print_to_pagebuf: input is '%s', Time: %llu\n", buf, time);
596 static const unsigned long parse_test[] __initconst = {
599 BITMAP_FROM_U64(0xdeadbeef),
600 BITMAP_FROM_U64(0x100000000ULL),
603 static const unsigned long parse_test2[] __initconst = {
604 BITMAP_FROM_U64(0x100000000ULL), BITMAP_FROM_U64(0xdeadbeef),
605 BITMAP_FROM_U64(0x100000000ULL), BITMAP_FROM_U64(0xbaadf00ddeadbeef),
606 BITMAP_FROM_U64(0x100000000ULL), BITMAP_FROM_U64(0x0badf00ddeadbeef),
609 static const struct test_bitmap_parselist parse_tests[] __initconst = {
610 {0, "", &parse_test[0 * step], 32, 0},
611 {0, " ", &parse_test[0 * step], 32, 0},
612 {0, "0", &parse_test[0 * step], 32, 0},
613 {0, "0\n", &parse_test[0 * step], 32, 0},
614 {0, "1", &parse_test[1 * step], 32, 0},
615 {0, "deadbeef", &parse_test[2 * step], 32, 0},
616 {0, "1,0", &parse_test[3 * step], 33, 0},
617 {0, "deadbeef,\n,0,1", &parse_test[2 * step], 96, 0},
619 {0, "deadbeef,1,0", &parse_test2[0 * 2 * step], 96, 0},
620 {0, "baadf00d,deadbeef,1,0", &parse_test2[1 * 2 * step], 128, 0},
621 {0, "badf00d,deadbeef,1,0", &parse_test2[2 * 2 * step], 124, 0},
622 {0, "badf00d,deadbeef,1,0", &parse_test2[2 * 2 * step], 124, NO_LEN},
623 {0, " badf00d,deadbeef,1,0 ", &parse_test2[2 * 2 * step], 124, 0},
624 {0, " , badf00d,deadbeef,1,0 , ", &parse_test2[2 * 2 * step], 124, 0},
625 {0, " , badf00d, ,, ,,deadbeef,1,0 , ", &parse_test2[2 * 2 * step], 124, 0},
627 {-EINVAL, "goodfood,deadbeef,1,0", NULL, 128, 0},
628 {-EOVERFLOW, "3,0", NULL, 33, 0},
629 {-EOVERFLOW, "123badf00d,deadbeef,1,0", NULL, 128, 0},
630 {-EOVERFLOW, "badf00d,deadbeef,1,0", NULL, 90, 0},
631 {-EOVERFLOW, "fbadf00d,deadbeef,1,0", NULL, 95, 0},
632 {-EOVERFLOW, "badf00d,deadbeef,1,0", NULL, 100, 0},
636 static void __init test_bitmap_parse(void)
641 DECLARE_BITMAP(bmap, 2048);
643 for (i = 0; i < ARRAY_SIZE(parse_tests); i++) {
644 struct test_bitmap_parselist test = parse_tests[i];
645 size_t len = test.flags & NO_LEN ? UINT_MAX : strlen(test.in);
648 err = bitmap_parse(test.in, len, bmap, test.nbits);
649 time = ktime_get() - time;
651 if (err != test.errno) {
652 pr_err("parse: %d: input is %s, errno is %d, expected %d\n",
653 i, test.in, err, test.errno);
658 if (!err && test.expected
659 && !__bitmap_equal(bmap, test.expected, test.nbits)) {
660 pr_err("parse: %d: input is %s, result is 0x%lx, expected 0x%lx\n",
667 if (test.flags & PARSE_TIME)
668 pr_err("parse: %d: input is '%s' OK, Time: %llu\n",
673 static void __init test_bitmap_arr32(void)
675 unsigned int nbits, next_bit;
676 u32 arr[EXP1_IN_BITS / 32];
677 DECLARE_BITMAP(bmap2, EXP1_IN_BITS);
679 memset(arr, 0xa5, sizeof(arr));
681 for (nbits = 0; nbits < EXP1_IN_BITS; ++nbits) {
682 bitmap_to_arr32(arr, exp1, nbits);
683 bitmap_from_arr32(bmap2, arr, nbits);
684 expect_eq_bitmap(bmap2, exp1, nbits);
686 next_bit = find_next_bit(bmap2,
687 round_up(nbits, BITS_PER_LONG), nbits);
688 if (next_bit < round_up(nbits, BITS_PER_LONG)) {
689 pr_err("bitmap_copy_arr32(nbits == %d:"
690 " tail is not safely cleared: %d\n",
695 if (nbits < EXP1_IN_BITS - 32)
696 expect_eq_uint(arr[DIV_ROUND_UP(nbits, 32)],
701 static void __init test_bitmap_arr64(void)
703 unsigned int nbits, next_bit;
704 u64 arr[EXP1_IN_BITS / 64];
705 DECLARE_BITMAP(bmap2, EXP1_IN_BITS);
707 memset(arr, 0xa5, sizeof(arr));
709 for (nbits = 0; nbits < EXP1_IN_BITS; ++nbits) {
710 memset(bmap2, 0xff, sizeof(arr));
711 bitmap_to_arr64(arr, exp1, nbits);
712 bitmap_from_arr64(bmap2, arr, nbits);
713 expect_eq_bitmap(bmap2, exp1, nbits);
715 next_bit = find_next_bit(bmap2, round_up(nbits, BITS_PER_LONG), nbits);
716 if (next_bit < round_up(nbits, BITS_PER_LONG)) {
717 pr_err("bitmap_copy_arr64(nbits == %d:"
718 " tail is not safely cleared: %d\n", nbits, next_bit);
723 (arr[(nbits - 1) / 64] & ~GENMASK_ULL((nbits - 1) % 64, 0))) {
724 pr_err("bitmap_to_arr64(nbits == %d): tail is not safely cleared: 0x%016llx (must be 0x%016llx)\n",
725 nbits, arr[(nbits - 1) / 64],
726 GENMASK_ULL((nbits - 1) % 64, 0));
730 if (nbits < EXP1_IN_BITS - 64)
731 expect_eq_uint(arr[DIV_ROUND_UP(nbits, 64)], 0xa5a5a5a5);
735 static void noinline __init test_mem_optimisations(void)
737 DECLARE_BITMAP(bmap1, 1024);
738 DECLARE_BITMAP(bmap2, 1024);
739 unsigned int start, nbits;
741 for (start = 0; start < 1024; start += 8) {
742 for (nbits = 0; nbits < 1024 - start; nbits += 8) {
743 memset(bmap1, 0x5a, sizeof(bmap1));
744 memset(bmap2, 0x5a, sizeof(bmap2));
746 bitmap_set(bmap1, start, nbits);
747 __bitmap_set(bmap2, start, nbits);
748 if (!bitmap_equal(bmap1, bmap2, 1024)) {
749 printk("set not equal %d %d\n", start, nbits);
752 if (!__bitmap_equal(bmap1, bmap2, 1024)) {
753 printk("set not __equal %d %d\n", start, nbits);
757 bitmap_clear(bmap1, start, nbits);
758 __bitmap_clear(bmap2, start, nbits);
759 if (!bitmap_equal(bmap1, bmap2, 1024)) {
760 printk("clear not equal %d %d\n", start, nbits);
763 if (!__bitmap_equal(bmap1, bmap2, 1024)) {
764 printk("clear not __equal %d %d\n", start,
772 static const unsigned char clump_exp[] __initconst = {
773 0x01, /* 1 bit set */
774 0x02, /* non-edge 1 bit set */
775 0x00, /* zero bits set */
776 0x38, /* 3 bits set across 4-bit boundary */
777 0x38, /* Repeated clump */
778 0x0F, /* 4 bits set */
779 0xFF, /* all bits set */
780 0x05, /* non-adjacent 2 bits set */
783 static void __init test_for_each_set_clump8(void)
785 #define CLUMP_EXP_NUMBITS 64
786 DECLARE_BITMAP(bits, CLUMP_EXP_NUMBITS);
790 /* set bitmap to test case */
791 bitmap_zero(bits, CLUMP_EXP_NUMBITS);
792 bitmap_set(bits, 0, 1); /* 0x01 */
793 bitmap_set(bits, 9, 1); /* 0x02 */
794 bitmap_set(bits, 27, 3); /* 0x28 */
795 bitmap_set(bits, 35, 3); /* 0x28 */
796 bitmap_set(bits, 40, 4); /* 0x0F */
797 bitmap_set(bits, 48, 8); /* 0xFF */
798 bitmap_set(bits, 56, 1); /* 0x05 - part 1 */
799 bitmap_set(bits, 58, 1); /* 0x05 - part 2 */
801 for_each_set_clump8(start, clump, bits, CLUMP_EXP_NUMBITS)
802 expect_eq_clump8(start, CLUMP_EXP_NUMBITS, clump_exp, &clump);
805 static void __init test_for_each_set_bit_wrap(void)
807 DECLARE_BITMAP(orig, 500);
808 DECLARE_BITMAP(copy, 500);
809 unsigned int wr, bit;
811 bitmap_zero(orig, 500);
813 /* Set individual bits */
814 for (bit = 0; bit < 500; bit += 10)
815 bitmap_set(orig, bit, 1);
817 /* Set range of bits */
818 bitmap_set(orig, 100, 50);
820 for (wr = 0; wr < 500; wr++) {
821 bitmap_zero(copy, 500);
823 for_each_set_bit_wrap(bit, orig, 500, wr)
824 bitmap_set(copy, bit, 1);
826 expect_eq_bitmap(orig, copy, 500);
830 static void __init test_for_each_set_bit(void)
832 DECLARE_BITMAP(orig, 500);
833 DECLARE_BITMAP(copy, 500);
836 bitmap_zero(orig, 500);
837 bitmap_zero(copy, 500);
839 /* Set individual bits */
840 for (bit = 0; bit < 500; bit += 10)
841 bitmap_set(orig, bit, 1);
843 /* Set range of bits */
844 bitmap_set(orig, 100, 50);
846 for_each_set_bit(bit, orig, 500)
847 bitmap_set(copy, bit, 1);
849 expect_eq_bitmap(orig, copy, 500);
852 static void __init test_for_each_set_bit_from(void)
854 DECLARE_BITMAP(orig, 500);
855 DECLARE_BITMAP(copy, 500);
856 unsigned int wr, bit;
858 bitmap_zero(orig, 500);
860 /* Set individual bits */
861 for (bit = 0; bit < 500; bit += 10)
862 bitmap_set(orig, bit, 1);
864 /* Set range of bits */
865 bitmap_set(orig, 100, 50);
867 for (wr = 0; wr < 500; wr++) {
868 DECLARE_BITMAP(tmp, 500);
870 bitmap_zero(copy, 500);
873 for_each_set_bit_from(bit, orig, 500)
874 bitmap_set(copy, bit, 1);
876 bitmap_copy(tmp, orig, 500);
877 bitmap_clear(tmp, 0, wr);
878 expect_eq_bitmap(tmp, copy, 500);
882 static void __init test_for_each_clear_bit(void)
884 DECLARE_BITMAP(orig, 500);
885 DECLARE_BITMAP(copy, 500);
888 bitmap_fill(orig, 500);
889 bitmap_fill(copy, 500);
891 /* Set individual bits */
892 for (bit = 0; bit < 500; bit += 10)
893 bitmap_clear(orig, bit, 1);
895 /* Set range of bits */
896 bitmap_clear(orig, 100, 50);
898 for_each_clear_bit(bit, orig, 500)
899 bitmap_clear(copy, bit, 1);
901 expect_eq_bitmap(orig, copy, 500);
904 static void __init test_for_each_clear_bit_from(void)
906 DECLARE_BITMAP(orig, 500);
907 DECLARE_BITMAP(copy, 500);
908 unsigned int wr, bit;
910 bitmap_fill(orig, 500);
912 /* Set individual bits */
913 for (bit = 0; bit < 500; bit += 10)
914 bitmap_clear(orig, bit, 1);
916 /* Set range of bits */
917 bitmap_clear(orig, 100, 50);
919 for (wr = 0; wr < 500; wr++) {
920 DECLARE_BITMAP(tmp, 500);
922 bitmap_fill(copy, 500);
925 for_each_clear_bit_from(bit, orig, 500)
926 bitmap_clear(copy, bit, 1);
928 bitmap_copy(tmp, orig, 500);
929 bitmap_set(tmp, 0, wr);
930 expect_eq_bitmap(tmp, copy, 500);
934 static void __init test_for_each_set_bitrange(void)
936 DECLARE_BITMAP(orig, 500);
937 DECLARE_BITMAP(copy, 500);
940 bitmap_zero(orig, 500);
941 bitmap_zero(copy, 500);
943 /* Set individual bits */
944 for (s = 0; s < 500; s += 10)
945 bitmap_set(orig, s, 1);
947 /* Set range of bits */
948 bitmap_set(orig, 100, 50);
950 for_each_set_bitrange(s, e, orig, 500)
951 bitmap_set(copy, s, e-s);
953 expect_eq_bitmap(orig, copy, 500);
956 static void __init test_for_each_clear_bitrange(void)
958 DECLARE_BITMAP(orig, 500);
959 DECLARE_BITMAP(copy, 500);
962 bitmap_fill(orig, 500);
963 bitmap_fill(copy, 500);
965 /* Set individual bits */
966 for (s = 0; s < 500; s += 10)
967 bitmap_clear(orig, s, 1);
969 /* Set range of bits */
970 bitmap_clear(orig, 100, 50);
972 for_each_clear_bitrange(s, e, orig, 500)
973 bitmap_clear(copy, s, e-s);
975 expect_eq_bitmap(orig, copy, 500);
978 static void __init test_for_each_set_bitrange_from(void)
980 DECLARE_BITMAP(orig, 500);
981 DECLARE_BITMAP(copy, 500);
982 unsigned int wr, s, e;
984 bitmap_zero(orig, 500);
986 /* Set individual bits */
987 for (s = 0; s < 500; s += 10)
988 bitmap_set(orig, s, 1);
990 /* Set range of bits */
991 bitmap_set(orig, 100, 50);
993 for (wr = 0; wr < 500; wr++) {
994 DECLARE_BITMAP(tmp, 500);
996 bitmap_zero(copy, 500);
999 for_each_set_bitrange_from(s, e, orig, 500)
1000 bitmap_set(copy, s, e - s);
1002 bitmap_copy(tmp, orig, 500);
1003 bitmap_clear(tmp, 0, wr);
1004 expect_eq_bitmap(tmp, copy, 500);
1008 static void __init test_for_each_clear_bitrange_from(void)
1010 DECLARE_BITMAP(orig, 500);
1011 DECLARE_BITMAP(copy, 500);
1012 unsigned int wr, s, e;
1014 bitmap_fill(orig, 500);
1016 /* Set individual bits */
1017 for (s = 0; s < 500; s += 10)
1018 bitmap_clear(orig, s, 1);
1020 /* Set range of bits */
1021 bitmap_set(orig, 100, 50);
1023 for (wr = 0; wr < 500; wr++) {
1024 DECLARE_BITMAP(tmp, 500);
1026 bitmap_fill(copy, 500);
1029 for_each_clear_bitrange_from(s, e, orig, 500)
1030 bitmap_clear(copy, s, e - s);
1032 bitmap_copy(tmp, orig, 500);
1033 bitmap_set(tmp, 0, wr);
1034 expect_eq_bitmap(tmp, copy, 500);
1038 struct test_bitmap_cut {
1042 unsigned long in[4];
1043 unsigned long expected[4];
1046 static struct test_bitmap_cut test_cut[] = {
1047 { 0, 0, 8, { 0x0000000aUL, }, { 0x0000000aUL, }, },
1048 { 0, 0, 32, { 0xdadadeadUL, }, { 0xdadadeadUL, }, },
1049 { 0, 3, 8, { 0x000000aaUL, }, { 0x00000015UL, }, },
1050 { 3, 3, 8, { 0x000000aaUL, }, { 0x00000012UL, }, },
1051 { 0, 1, 32, { 0xa5a5a5a5UL, }, { 0x52d2d2d2UL, }, },
1052 { 0, 8, 32, { 0xdeadc0deUL, }, { 0x00deadc0UL, }, },
1053 { 1, 1, 32, { 0x5a5a5a5aUL, }, { 0x2d2d2d2cUL, }, },
1054 { 0, 15, 32, { 0xa5a5a5a5UL, }, { 0x00014b4bUL, }, },
1055 { 0, 16, 32, { 0xa5a5a5a5UL, }, { 0x0000a5a5UL, }, },
1056 { 15, 15, 32, { 0xa5a5a5a5UL, }, { 0x000125a5UL, }, },
1057 { 15, 16, 32, { 0xa5a5a5a5UL, }, { 0x0000a5a5UL, }, },
1058 { 16, 15, 32, { 0xa5a5a5a5UL, }, { 0x0001a5a5UL, }, },
1060 { BITS_PER_LONG, BITS_PER_LONG, BITS_PER_LONG,
1061 { 0xa5a5a5a5UL, 0xa5a5a5a5UL, },
1062 { 0xa5a5a5a5UL, 0xa5a5a5a5UL, },
1064 { 1, BITS_PER_LONG - 1, BITS_PER_LONG,
1065 { 0xa5a5a5a5UL, 0xa5a5a5a5UL, },
1066 { 0x00000001UL, 0x00000001UL, },
1069 { 0, BITS_PER_LONG * 2, BITS_PER_LONG * 2 + 1,
1070 { 0xa5a5a5a5UL, 0x00000001UL, 0x00000001UL, 0x00000001UL },
1073 { 16, BITS_PER_LONG * 2 + 1, BITS_PER_LONG * 2 + 1 + 16,
1074 { 0x0000ffffUL, 0x5a5a5a5aUL, 0x5a5a5a5aUL, 0x5a5a5a5aUL },
1079 static void __init test_bitmap_cut(void)
1081 unsigned long b[5], *in = &b[1], *out = &b[0]; /* Partial overlap */
1084 for (i = 0; i < ARRAY_SIZE(test_cut); i++) {
1085 struct test_bitmap_cut *t = &test_cut[i];
1087 memcpy(in, t->in, sizeof(t->in));
1089 bitmap_cut(out, in, t->first, t->cut, t->nbits);
1091 expect_eq_bitmap(t->expected, out, t->nbits);
1095 struct test_bitmap_print {
1096 const unsigned long *bitmap;
1097 unsigned long nbits;
1102 static const unsigned long small_bitmap[] __initconst = {
1103 BITMAP_FROM_U64(0x3333333311111111ULL),
1106 static const char small_mask[] __initconst = "33333333,11111111\n";
1107 static const char small_list[] __initconst = "0,4,8,12,16,20,24,28,32-33,36-37,40-41,44-45,48-49,52-53,56-57,60-61\n";
1109 static const unsigned long large_bitmap[] __initconst = {
1110 BITMAP_FROM_U64(0x3333333311111111ULL), BITMAP_FROM_U64(0x3333333311111111ULL),
1111 BITMAP_FROM_U64(0x3333333311111111ULL), BITMAP_FROM_U64(0x3333333311111111ULL),
1112 BITMAP_FROM_U64(0x3333333311111111ULL), BITMAP_FROM_U64(0x3333333311111111ULL),
1113 BITMAP_FROM_U64(0x3333333311111111ULL), BITMAP_FROM_U64(0x3333333311111111ULL),
1114 BITMAP_FROM_U64(0x3333333311111111ULL), BITMAP_FROM_U64(0x3333333311111111ULL),
1115 BITMAP_FROM_U64(0x3333333311111111ULL), BITMAP_FROM_U64(0x3333333311111111ULL),
1116 BITMAP_FROM_U64(0x3333333311111111ULL), BITMAP_FROM_U64(0x3333333311111111ULL),
1117 BITMAP_FROM_U64(0x3333333311111111ULL), BITMAP_FROM_U64(0x3333333311111111ULL),
1118 BITMAP_FROM_U64(0x3333333311111111ULL), BITMAP_FROM_U64(0x3333333311111111ULL),
1119 BITMAP_FROM_U64(0x3333333311111111ULL), BITMAP_FROM_U64(0x3333333311111111ULL),
1120 BITMAP_FROM_U64(0x3333333311111111ULL), BITMAP_FROM_U64(0x3333333311111111ULL),
1121 BITMAP_FROM_U64(0x3333333311111111ULL), BITMAP_FROM_U64(0x3333333311111111ULL),
1122 BITMAP_FROM_U64(0x3333333311111111ULL), BITMAP_FROM_U64(0x3333333311111111ULL),
1123 BITMAP_FROM_U64(0x3333333311111111ULL), BITMAP_FROM_U64(0x3333333311111111ULL),
1124 BITMAP_FROM_U64(0x3333333311111111ULL), BITMAP_FROM_U64(0x3333333311111111ULL),
1125 BITMAP_FROM_U64(0x3333333311111111ULL), BITMAP_FROM_U64(0x3333333311111111ULL),
1126 BITMAP_FROM_U64(0x3333333311111111ULL), BITMAP_FROM_U64(0x3333333311111111ULL),
1127 BITMAP_FROM_U64(0x3333333311111111ULL), BITMAP_FROM_U64(0x3333333311111111ULL),
1128 BITMAP_FROM_U64(0x3333333311111111ULL), BITMAP_FROM_U64(0x3333333311111111ULL),
1129 BITMAP_FROM_U64(0x3333333311111111ULL), BITMAP_FROM_U64(0x3333333311111111ULL),
1132 static const char large_mask[] __initconst = "33333333,11111111,33333333,11111111,"
1133 "33333333,11111111,33333333,11111111,"
1134 "33333333,11111111,33333333,11111111,"
1135 "33333333,11111111,33333333,11111111,"
1136 "33333333,11111111,33333333,11111111,"
1137 "33333333,11111111,33333333,11111111,"
1138 "33333333,11111111,33333333,11111111,"
1139 "33333333,11111111,33333333,11111111,"
1140 "33333333,11111111,33333333,11111111,"
1141 "33333333,11111111,33333333,11111111,"
1142 "33333333,11111111,33333333,11111111,"
1143 "33333333,11111111,33333333,11111111,"
1144 "33333333,11111111,33333333,11111111,"
1145 "33333333,11111111,33333333,11111111,"
1146 "33333333,11111111,33333333,11111111,"
1147 "33333333,11111111,33333333,11111111,"
1148 "33333333,11111111,33333333,11111111,"
1149 "33333333,11111111,33333333,11111111,"
1150 "33333333,11111111,33333333,11111111,"
1151 "33333333,11111111,33333333,11111111\n";
1153 static const char large_list[] __initconst = /* more than 4KB */
1154 "0,4,8,12,16,20,24,28,32-33,36-37,40-41,44-45,48-49,52-53,56-57,60-61,64,68,72,76,80,84,88,92,96-97,100-101,104-1"
1155 "05,108-109,112-113,116-117,120-121,124-125,128,132,136,140,144,148,152,156,160-161,164-165,168-169,172-173,176-1"
1156 "77,180-181,184-185,188-189,192,196,200,204,208,212,216,220,224-225,228-229,232-233,236-237,240-241,244-245,248-2"
1157 "49,252-253,256,260,264,268,272,276,280,284,288-289,292-293,296-297,300-301,304-305,308-309,312-313,316-317,320,3"
1158 "24,328,332,336,340,344,348,352-353,356-357,360-361,364-365,368-369,372-373,376-377,380-381,384,388,392,396,400,4"
1159 "04,408,412,416-417,420-421,424-425,428-429,432-433,436-437,440-441,444-445,448,452,456,460,464,468,472,476,480-4"
1160 "81,484-485,488-489,492-493,496-497,500-501,504-505,508-509,512,516,520,524,528,532,536,540,544-545,548-549,552-5"
1161 "53,556-557,560-561,564-565,568-569,572-573,576,580,584,588,592,596,600,604,608-609,612-613,616-617,620-621,624-6"
1162 "25,628-629,632-633,636-637,640,644,648,652,656,660,664,668,672-673,676-677,680-681,684-685,688-689,692-693,696-6"
1163 "97,700-701,704,708,712,716,720,724,728,732,736-737,740-741,744-745,748-749,752-753,756-757,760-761,764-765,768,7"
1164 "72,776,780,784,788,792,796,800-801,804-805,808-809,812-813,816-817,820-821,824-825,828-829,832,836,840,844,848,8"
1165 "52,856,860,864-865,868-869,872-873,876-877,880-881,884-885,888-889,892-893,896,900,904,908,912,916,920,924,928-9"
1166 "29,932-933,936-937,940-941,944-945,948-949,952-953,956-957,960,964,968,972,976,980,984,988,992-993,996-997,1000-"
1167 "1001,1004-1005,1008-1009,1012-1013,1016-1017,1020-1021,1024,1028,1032,1036,1040,1044,1048,1052,1056-1057,1060-10"
1168 "61,1064-1065,1068-1069,1072-1073,1076-1077,1080-1081,1084-1085,1088,1092,1096,1100,1104,1108,1112,1116,1120-1121"
1169 ",1124-1125,1128-1129,1132-1133,1136-1137,1140-1141,1144-1145,1148-1149,1152,1156,1160,1164,1168,1172,1176,1180,1"
1170 "184-1185,1188-1189,1192-1193,1196-1197,1200-1201,1204-1205,1208-1209,1212-1213,1216,1220,1224,1228,1232,1236,124"
1171 "0,1244,1248-1249,1252-1253,1256-1257,1260-1261,1264-1265,1268-1269,1272-1273,1276-1277,1280,1284,1288,1292,1296,"
1172 "1300,1304,1308,1312-1313,1316-1317,1320-1321,1324-1325,1328-1329,1332-1333,1336-1337,1340-1341,1344,1348,1352,13"
1173 "56,1360,1364,1368,1372,1376-1377,1380-1381,1384-1385,1388-1389,1392-1393,1396-1397,1400-1401,1404-1405,1408,1412"
1174 ",1416,1420,1424,1428,1432,1436,1440-1441,1444-1445,1448-1449,1452-1453,1456-1457,1460-1461,1464-1465,1468-1469,1"
1175 "472,1476,1480,1484,1488,1492,1496,1500,1504-1505,1508-1509,1512-1513,1516-1517,1520-1521,1524-1525,1528-1529,153"
1176 "2-1533,1536,1540,1544,1548,1552,1556,1560,1564,1568-1569,1572-1573,1576-1577,1580-1581,1584-1585,1588-1589,1592-"
1177 "1593,1596-1597,1600,1604,1608,1612,1616,1620,1624,1628,1632-1633,1636-1637,1640-1641,1644-1645,1648-1649,1652-16"
1178 "53,1656-1657,1660-1661,1664,1668,1672,1676,1680,1684,1688,1692,1696-1697,1700-1701,1704-1705,1708-1709,1712-1713"
1179 ",1716-1717,1720-1721,1724-1725,1728,1732,1736,1740,1744,1748,1752,1756,1760-1761,1764-1765,1768-1769,1772-1773,1"
1180 "776-1777,1780-1781,1784-1785,1788-1789,1792,1796,1800,1804,1808,1812,1816,1820,1824-1825,1828-1829,1832-1833,183"
1181 "6-1837,1840-1841,1844-1845,1848-1849,1852-1853,1856,1860,1864,1868,1872,1876,1880,1884,1888-1889,1892-1893,1896-"
1182 "1897,1900-1901,1904-1905,1908-1909,1912-1913,1916-1917,1920,1924,1928,1932,1936,1940,1944,1948,1952-1953,1956-19"
1183 "57,1960-1961,1964-1965,1968-1969,1972-1973,1976-1977,1980-1981,1984,1988,1992,1996,2000,2004,2008,2012,2016-2017"
1184 ",2020-2021,2024-2025,2028-2029,2032-2033,2036-2037,2040-2041,2044-2045,2048,2052,2056,2060,2064,2068,2072,2076,2"
1185 "080-2081,2084-2085,2088-2089,2092-2093,2096-2097,2100-2101,2104-2105,2108-2109,2112,2116,2120,2124,2128,2132,213"
1186 "6,2140,2144-2145,2148-2149,2152-2153,2156-2157,2160-2161,2164-2165,2168-2169,2172-2173,2176,2180,2184,2188,2192,"
1187 "2196,2200,2204,2208-2209,2212-2213,2216-2217,2220-2221,2224-2225,2228-2229,2232-2233,2236-2237,2240,2244,2248,22"
1188 "52,2256,2260,2264,2268,2272-2273,2276-2277,2280-2281,2284-2285,2288-2289,2292-2293,2296-2297,2300-2301,2304,2308"
1189 ",2312,2316,2320,2324,2328,2332,2336-2337,2340-2341,2344-2345,2348-2349,2352-2353,2356-2357,2360-2361,2364-2365,2"
1190 "368,2372,2376,2380,2384,2388,2392,2396,2400-2401,2404-2405,2408-2409,2412-2413,2416-2417,2420-2421,2424-2425,242"
1191 "8-2429,2432,2436,2440,2444,2448,2452,2456,2460,2464-2465,2468-2469,2472-2473,2476-2477,2480-2481,2484-2485,2488-"
1192 "2489,2492-2493,2496,2500,2504,2508,2512,2516,2520,2524,2528-2529,2532-2533,2536-2537,2540-2541,2544-2545,2548-25"
1193 "49,2552-2553,2556-2557\n";
1195 static const struct test_bitmap_print test_print[] __initconst = {
1196 { small_bitmap, sizeof(small_bitmap) * BITS_PER_BYTE, small_mask, small_list },
1197 { large_bitmap, sizeof(large_bitmap) * BITS_PER_BYTE, large_mask, large_list },
1200 static void __init test_bitmap_print_buf(void)
1204 for (i = 0; i < ARRAY_SIZE(test_print); i++) {
1205 const struct test_bitmap_print *t = &test_print[i];
1208 n = bitmap_print_bitmask_to_buf(print_buf, t->bitmap, t->nbits,
1210 expect_eq_uint(strlen(t->mask) + 1, n);
1211 expect_eq_str(t->mask, print_buf, n);
1213 n = bitmap_print_list_to_buf(print_buf, t->bitmap, t->nbits,
1215 expect_eq_uint(strlen(t->list) + 1, n);
1216 expect_eq_str(t->list, print_buf, n);
1218 /* test by non-zero offset */
1219 if (strlen(t->list) > PAGE_SIZE) {
1220 n = bitmap_print_list_to_buf(print_buf, t->bitmap, t->nbits,
1221 PAGE_SIZE, PAGE_SIZE);
1222 expect_eq_uint(strlen(t->list) + 1 - PAGE_SIZE, n);
1223 expect_eq_str(t->list + PAGE_SIZE, print_buf, n);
1229 * FIXME: Clang breaks compile-time evaluations when KASAN and GCOV are enabled.
1230 * To workaround it, GCOV is force-disabled in Makefile for this configuration.
1232 static void __init test_bitmap_const_eval(void)
1234 DECLARE_BITMAP(bitmap, BITS_PER_LONG);
1235 unsigned long initvar = BIT(2);
1236 unsigned long bitopvar = 0;
1237 unsigned long var = 0;
1241 * Compilers must be able to optimize all of those to compile-time
1242 * constants on any supported optimization level (-O2, -Os) and any
1243 * architecture. Otherwise, trigger a build bug.
1244 * The whole function gets optimized out then, there's nothing to do
1249 * Equals to `unsigned long bitmap[1] = { GENMASK(6, 5), }`.
1250 * Clang on s390 optimizes bitops at compile-time as intended, but at
1251 * the same time stops treating @bitmap and @bitopvar as compile-time
1252 * constants after regular test_bit() is executed, thus triggering the
1253 * build bugs below. So, call const_test_bit() there directly until
1254 * the compiler is fixed.
1256 bitmap_clear(bitmap, 0, BITS_PER_LONG);
1257 if (!test_bit(7, bitmap))
1258 bitmap_set(bitmap, 5, 2);
1260 /* Equals to `unsigned long bitopvar = BIT(20)` */
1261 __change_bit(31, &bitopvar);
1262 bitmap_shift_right(&bitopvar, &bitopvar, 11, BITS_PER_LONG);
1264 /* Equals to `unsigned long var = BIT(25)` */
1267 var ^= GENMASK(9, 6);
1269 /* __const_hweight<32|64>(GENMASK(6, 5)) == 2 */
1270 res = bitmap_weight(bitmap, 20);
1271 BUILD_BUG_ON(!__builtin_constant_p(res));
1272 BUILD_BUG_ON(res != 2);
1274 /* !(BIT(31) & BIT(18)) == 1 */
1275 res = !test_bit(18, &bitopvar);
1276 BUILD_BUG_ON(!__builtin_constant_p(res));
1279 /* BIT(2) & GENMASK(14, 8) == 0 */
1280 res = initvar & GENMASK(14, 8);
1281 BUILD_BUG_ON(!__builtin_constant_p(res));
1285 BUILD_BUG_ON(!__builtin_constant_p(~var));
1286 BUILD_BUG_ON(~var != ~BIT(25));
1289 static void __init selftest(void)
1294 test_bitmap_region();
1297 test_bitmap_arr32();
1298 test_bitmap_arr64();
1299 test_bitmap_parse();
1300 test_bitmap_parselist();
1301 test_bitmap_printlist();
1302 test_mem_optimisations();
1304 test_bitmap_print_buf();
1305 test_bitmap_const_eval();
1307 test_find_nth_bit();
1308 test_for_each_set_bit();
1309 test_for_each_set_bit_from();
1310 test_for_each_clear_bit();
1311 test_for_each_clear_bit_from();
1312 test_for_each_set_bitrange();
1313 test_for_each_clear_bitrange();
1314 test_for_each_set_bitrange_from();
1315 test_for_each_clear_bitrange_from();
1316 test_for_each_set_clump8();
1317 test_for_each_set_bit_wrap();
1320 KSTM_MODULE_LOADERS(test_bitmap);
1321 MODULE_AUTHOR("david decotigny <david.decotigny@googlers.com>");
1322 MODULE_LICENSE("GPL");