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 static unsigned total_tests __initdata;
20 static unsigned failed_tests __initdata;
22 static char pbl_buffer[PAGE_SIZE] __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),
40 static const unsigned long exp2[] __initconst = {
41 BITMAP_FROM_U64(0x3333333311111111ULL),
42 BITMAP_FROM_U64(0xffffffff77777777ULL),
46 __check_eq_uint(const char *srcfile, unsigned int line,
47 const unsigned int exp_uint, unsigned int x)
50 pr_err("[%s:%u] expected %u, got %u\n",
51 srcfile, line, exp_uint, x);
59 __check_eq_bitmap(const char *srcfile, unsigned int line,
60 const unsigned long *exp_bmap, const unsigned long *bmap,
63 if (!bitmap_equal(exp_bmap, bmap, nbits)) {
64 pr_warn("[%s:%u] bitmaps contents differ: expected \"%*pbl\", got \"%*pbl\"\n",
66 nbits, exp_bmap, nbits, bmap);
73 __check_eq_pbl(const char *srcfile, unsigned int line,
74 const char *expected_pbl,
75 const unsigned long *bitmap, unsigned int nbits)
77 snprintf(pbl_buffer, sizeof(pbl_buffer), "%*pbl", nbits, bitmap);
78 if (strcmp(expected_pbl, pbl_buffer)) {
79 pr_warn("[%s:%u] expected \"%s\", got \"%s\"\n",
81 expected_pbl, pbl_buffer);
88 __check_eq_u32_array(const char *srcfile, unsigned int line,
89 const u32 *exp_arr, unsigned int exp_len,
90 const u32 *arr, unsigned int len) __used;
92 __check_eq_u32_array(const char *srcfile, unsigned int line,
93 const u32 *exp_arr, unsigned int exp_len,
94 const u32 *arr, unsigned int len)
97 pr_warn("[%s:%u] array length differ: expected %u, got %u\n",
103 if (memcmp(exp_arr, arr, len*sizeof(*arr))) {
104 pr_warn("[%s:%u] array contents differ\n", srcfile, line);
105 print_hex_dump(KERN_WARNING, " exp: ", DUMP_PREFIX_OFFSET,
106 32, 4, exp_arr, exp_len*sizeof(*exp_arr), false);
107 print_hex_dump(KERN_WARNING, " got: ", DUMP_PREFIX_OFFSET,
108 32, 4, arr, len*sizeof(*arr), false);
115 static bool __init __check_eq_clump8(const char *srcfile, unsigned int line,
116 const unsigned int offset,
117 const unsigned int size,
118 const unsigned char *const clump_exp,
119 const unsigned long *const clump)
123 if (offset >= size) {
124 pr_warn("[%s:%u] bit offset for clump out-of-bounds: expected less than %u, got %u\n",
125 srcfile, line, size, offset);
129 exp = clump_exp[offset / 8];
131 pr_warn("[%s:%u] bit offset for zero clump: expected nonzero clump, got bit offset %u with clump value 0",
132 srcfile, line, offset);
137 pr_warn("[%s:%u] expected clump value of 0x%lX, got clump value of 0x%lX",
138 srcfile, line, exp, *clump);
145 #define __expect_eq(suffix, ...) \
149 if (!__check_eq_ ## suffix(__FILE__, __LINE__, \
157 #define expect_eq_uint(...) __expect_eq(uint, ##__VA_ARGS__)
158 #define expect_eq_bitmap(...) __expect_eq(bitmap, ##__VA_ARGS__)
159 #define expect_eq_pbl(...) __expect_eq(pbl, ##__VA_ARGS__)
160 #define expect_eq_u32_array(...) __expect_eq(u32_array, ##__VA_ARGS__)
161 #define expect_eq_clump8(...) __expect_eq(clump8, ##__VA_ARGS__)
163 static void __init test_zero_clear(void)
165 DECLARE_BITMAP(bmap, 1024);
167 /* Known way to set all bits */
168 memset(bmap, 0xff, 128);
170 expect_eq_pbl("0-22", bmap, 23);
171 expect_eq_pbl("0-1023", bmap, 1024);
173 /* single-word bitmaps */
174 bitmap_clear(bmap, 0, 9);
175 expect_eq_pbl("9-1023", bmap, 1024);
177 bitmap_zero(bmap, 35);
178 expect_eq_pbl("64-1023", bmap, 1024);
180 /* cross boundaries operations */
181 bitmap_clear(bmap, 79, 19);
182 expect_eq_pbl("64-78,98-1023", bmap, 1024);
184 bitmap_zero(bmap, 115);
185 expect_eq_pbl("128-1023", bmap, 1024);
187 /* Zeroing entire area */
188 bitmap_zero(bmap, 1024);
189 expect_eq_pbl("", bmap, 1024);
192 static void __init test_fill_set(void)
194 DECLARE_BITMAP(bmap, 1024);
196 /* Known way to clear all bits */
197 memset(bmap, 0x00, 128);
199 expect_eq_pbl("", bmap, 23);
200 expect_eq_pbl("", bmap, 1024);
202 /* single-word bitmaps */
203 bitmap_set(bmap, 0, 9);
204 expect_eq_pbl("0-8", bmap, 1024);
206 bitmap_fill(bmap, 35);
207 expect_eq_pbl("0-63", bmap, 1024);
209 /* cross boundaries operations */
210 bitmap_set(bmap, 79, 19);
211 expect_eq_pbl("0-63,79-97", bmap, 1024);
213 bitmap_fill(bmap, 115);
214 expect_eq_pbl("0-127", bmap, 1024);
216 /* Zeroing entire area */
217 bitmap_fill(bmap, 1024);
218 expect_eq_pbl("0-1023", bmap, 1024);
221 static void __init test_copy(void)
223 DECLARE_BITMAP(bmap1, 1024);
224 DECLARE_BITMAP(bmap2, 1024);
226 bitmap_zero(bmap1, 1024);
227 bitmap_zero(bmap2, 1024);
229 /* single-word bitmaps */
230 bitmap_set(bmap1, 0, 19);
231 bitmap_copy(bmap2, bmap1, 23);
232 expect_eq_pbl("0-18", bmap2, 1024);
234 bitmap_set(bmap2, 0, 23);
235 bitmap_copy(bmap2, bmap1, 23);
236 expect_eq_pbl("0-18", bmap2, 1024);
238 /* multi-word bitmaps */
239 bitmap_set(bmap1, 0, 109);
240 bitmap_copy(bmap2, bmap1, 1024);
241 expect_eq_pbl("0-108", bmap2, 1024);
243 bitmap_fill(bmap2, 1024);
244 bitmap_copy(bmap2, bmap1, 1024);
245 expect_eq_pbl("0-108", bmap2, 1024);
247 /* the following tests assume a 32- or 64-bit arch (even 128b
251 bitmap_fill(bmap2, 1024);
252 bitmap_copy(bmap2, bmap1, 109); /* ... but 0-padded til word length */
253 expect_eq_pbl("0-108,128-1023", bmap2, 1024);
255 bitmap_fill(bmap2, 1024);
256 bitmap_copy(bmap2, bmap1, 97); /* ... but aligned on word length */
257 expect_eq_pbl("0-108,128-1023", bmap2, 1024);
260 #define PARSE_TIME 0x1
262 struct test_bitmap_parselist{
265 const unsigned long *expected;
270 static const struct test_bitmap_parselist parselist_tests[] __initconst = {
271 #define step (sizeof(u64) / sizeof(unsigned long))
273 {0, "0", &exp1[0], 8, 0},
274 {0, "1", &exp1[1 * step], 8, 0},
275 {0, "0-15", &exp1[2 * step], 32, 0},
276 {0, "16-31", &exp1[3 * step], 32, 0},
277 {0, "0-31:1/2", &exp1[4 * step], 32, 0},
278 {0, "1-31:1/2", &exp1[5 * step], 32, 0},
279 {0, "0-31:1/4", &exp1[6 * step], 32, 0},
280 {0, "1-31:1/4", &exp1[7 * step], 32, 0},
281 {0, "0-31:4/4", &exp1[8 * step], 32, 0},
282 {0, "1-31:4/4", &exp1[9 * step], 32, 0},
283 {0, "0-31:1/4,32-63:2/4", &exp1[10 * step], 64, 0},
284 {0, "0-31:3/4,32-63:4/4", &exp1[11 * step], 64, 0},
285 {0, " ,, 0-31:3/4 ,, 32-63:4/4 ,, ", &exp1[11 * step], 64, 0},
287 {0, "0-31:1/4,32-63:2/4,64-95:3/4,96-127:4/4", exp2, 128, 0},
289 {0, "0-2047:128/256", NULL, 2048, PARSE_TIME},
291 {0, "", &exp1[12 * step], 8, 0},
292 {0, "\n", &exp1[12 * step], 8, 0},
293 {0, ",, ,, , , ,", &exp1[12 * step], 8, 0},
294 {0, " , ,, , , ", &exp1[12 * step], 8, 0},
295 {0, " , ,, , , \n", &exp1[12 * step], 8, 0},
297 {-EINVAL, "-1", NULL, 8, 0},
298 {-EINVAL, "-0", NULL, 8, 0},
299 {-EINVAL, "10-1", NULL, 8, 0},
300 {-EINVAL, "0-31:", NULL, 8, 0},
301 {-EINVAL, "0-31:0", NULL, 8, 0},
302 {-EINVAL, "0-31:0/", NULL, 8, 0},
303 {-EINVAL, "0-31:0/0", NULL, 8, 0},
304 {-EINVAL, "0-31:1/0", NULL, 8, 0},
305 {-EINVAL, "0-31:10/1", NULL, 8, 0},
306 {-EOVERFLOW, "0-98765432123456789:10/1", NULL, 8, 0},
308 {-EINVAL, "a-31", NULL, 8, 0},
309 {-EINVAL, "0-a1", NULL, 8, 0},
310 {-EINVAL, "a-31:10/1", NULL, 8, 0},
311 {-EINVAL, "0-31:a/1", NULL, 8, 0},
312 {-EINVAL, "0-\n", NULL, 8, 0},
317 static void __init __test_bitmap_parselist(int is_user)
322 DECLARE_BITMAP(bmap, 2048);
323 char *mode = is_user ? "_user" : "";
325 for (i = 0; i < ARRAY_SIZE(parselist_tests); i++) {
326 #define ptest parselist_tests[i]
329 mm_segment_t orig_fs = get_fs();
330 size_t len = strlen(ptest.in);
334 err = bitmap_parselist_user((__force const char __user *)ptest.in, len,
336 time = ktime_get() - time;
340 err = bitmap_parselist(ptest.in, bmap, ptest.nbits);
341 time = ktime_get() - time;
344 if (err != ptest.errno) {
345 pr_err("parselist%s: %d: input is %s, errno is %d, expected %d\n",
346 mode, i, ptest.in, err, ptest.errno);
350 if (!err && ptest.expected
351 && !__bitmap_equal(bmap, ptest.expected, ptest.nbits)) {
352 pr_err("parselist%s: %d: input is %s, result is 0x%lx, expected 0x%lx\n",
353 mode, i, ptest.in, bmap[0],
358 if (ptest.flags & PARSE_TIME)
359 pr_err("parselist%s: %d: input is '%s' OK, Time: %llu\n",
360 mode, i, ptest.in, time);
366 static void __init test_bitmap_parselist(void)
368 __test_bitmap_parselist(0);
371 static void __init test_bitmap_parselist_user(void)
373 __test_bitmap_parselist(1);
376 #define EXP1_IN_BITS (sizeof(exp1) * 8)
378 static void __init test_bitmap_arr32(void)
380 unsigned int nbits, next_bit;
381 u32 arr[EXP1_IN_BITS / 32];
382 DECLARE_BITMAP(bmap2, EXP1_IN_BITS);
384 memset(arr, 0xa5, sizeof(arr));
386 for (nbits = 0; nbits < EXP1_IN_BITS; ++nbits) {
387 bitmap_to_arr32(arr, exp1, nbits);
388 bitmap_from_arr32(bmap2, arr, nbits);
389 expect_eq_bitmap(bmap2, exp1, nbits);
391 next_bit = find_next_bit(bmap2,
392 round_up(nbits, BITS_PER_LONG), nbits);
393 if (next_bit < round_up(nbits, BITS_PER_LONG))
394 pr_err("bitmap_copy_arr32(nbits == %d:"
395 " tail is not safely cleared: %d\n",
398 if (nbits < EXP1_IN_BITS - 32)
399 expect_eq_uint(arr[DIV_ROUND_UP(nbits, 32)],
404 static void noinline __init test_mem_optimisations(void)
406 DECLARE_BITMAP(bmap1, 1024);
407 DECLARE_BITMAP(bmap2, 1024);
408 unsigned int start, nbits;
410 for (start = 0; start < 1024; start += 8) {
411 for (nbits = 0; nbits < 1024 - start; nbits += 8) {
412 memset(bmap1, 0x5a, sizeof(bmap1));
413 memset(bmap2, 0x5a, sizeof(bmap2));
415 bitmap_set(bmap1, start, nbits);
416 __bitmap_set(bmap2, start, nbits);
417 if (!bitmap_equal(bmap1, bmap2, 1024)) {
418 printk("set not equal %d %d\n", start, nbits);
421 if (!__bitmap_equal(bmap1, bmap2, 1024)) {
422 printk("set not __equal %d %d\n", start, nbits);
426 bitmap_clear(bmap1, start, nbits);
427 __bitmap_clear(bmap2, start, nbits);
428 if (!bitmap_equal(bmap1, bmap2, 1024)) {
429 printk("clear not equal %d %d\n", start, nbits);
432 if (!__bitmap_equal(bmap1, bmap2, 1024)) {
433 printk("clear not __equal %d %d\n", start,
441 static const unsigned char clump_exp[] __initconst = {
442 0x01, /* 1 bit set */
443 0x02, /* non-edge 1 bit set */
444 0x00, /* zero bits set */
445 0x38, /* 3 bits set across 4-bit boundary */
446 0x38, /* Repeated clump */
447 0x0F, /* 4 bits set */
448 0xFF, /* all bits set */
449 0x05, /* non-adjacent 2 bits set */
452 static void __init test_for_each_set_clump8(void)
454 #define CLUMP_EXP_NUMBITS 64
455 DECLARE_BITMAP(bits, CLUMP_EXP_NUMBITS);
459 /* set bitmap to test case */
460 bitmap_zero(bits, CLUMP_EXP_NUMBITS);
461 bitmap_set(bits, 0, 1); /* 0x01 */
462 bitmap_set(bits, 9, 1); /* 0x02 */
463 bitmap_set(bits, 27, 3); /* 0x28 */
464 bitmap_set(bits, 35, 3); /* 0x28 */
465 bitmap_set(bits, 40, 4); /* 0x0F */
466 bitmap_set(bits, 48, 8); /* 0xFF */
467 bitmap_set(bits, 56, 1); /* 0x05 - part 1 */
468 bitmap_set(bits, 58, 1); /* 0x05 - part 2 */
470 for_each_set_clump8(start, clump, bits, CLUMP_EXP_NUMBITS)
471 expect_eq_clump8(start, CLUMP_EXP_NUMBITS, clump_exp, &clump);
474 static void __init selftest(void)
480 test_bitmap_parselist();
481 test_bitmap_parselist_user();
482 test_mem_optimisations();
483 test_for_each_set_clump8();
486 KSTM_MODULE_LOADERS(test_bitmap);
487 MODULE_AUTHOR("david decotigny <david.decotigny@googlers.com>");
488 MODULE_LICENSE("GPL");