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