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
__check_eq_uint(const char * srcfile,unsigned int line,const unsigned int exp_uint,unsigned int x)63 __check_eq_uint(const char *srcfile, unsigned int line,
64 const unsigned int exp_uint, unsigned int x)
65 {
66 if (exp_uint != x) {
67 pr_err("[%s:%u] expected %u, got %u\n",
68 srcfile, line, exp_uint, x);
69 return false;
70 }
71 return true;
72 }
73
74
75 static bool __init
__check_eq_bitmap(const char * srcfile,unsigned int line,const unsigned long * exp_bmap,const unsigned long * bmap,unsigned int nbits)76 __check_eq_bitmap(const char *srcfile, unsigned int line,
77 const unsigned long *exp_bmap, const unsigned long *bmap,
78 unsigned int nbits)
79 {
80 if (!bitmap_equal(exp_bmap, bmap, nbits)) {
81 pr_warn("[%s:%u] bitmaps contents differ: expected \"%*pbl\", got \"%*pbl\"\n",
82 srcfile, line,
83 nbits, exp_bmap, nbits, bmap);
84 return false;
85 }
86 return true;
87 }
88
89 static bool __init
__check_eq_pbl(const char * srcfile,unsigned int line,const char * expected_pbl,const unsigned long * bitmap,unsigned int nbits)90 __check_eq_pbl(const char *srcfile, unsigned int line,
91 const char *expected_pbl,
92 const unsigned long *bitmap, unsigned int nbits)
93 {
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",
97 srcfile, line,
98 expected_pbl, pbl_buffer);
99 return false;
100 }
101 return true;
102 }
103
104 static bool __init
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;
108 static bool __init
__check_eq_u32_array(const char * srcfile,unsigned int line,const u32 * exp_arr,unsigned int exp_len,const u32 * arr,unsigned int len)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)
112 {
113 if (exp_len != len) {
114 pr_warn("[%s:%u] array length differ: expected %u, got %u\n",
115 srcfile, line,
116 exp_len, len);
117 return false;
118 }
119
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);
126 return false;
127 }
128
129 return true;
130 }
131
__check_eq_clump8(const char * srcfile,unsigned int line,const unsigned int offset,const unsigned int size,const unsigned char * const clump_exp,const unsigned long * const clump)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)
137 {
138 unsigned long exp;
139
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);
143 return false;
144 }
145
146 exp = clump_exp[offset / 8];
147 if (!exp) {
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);
150 return false;
151 }
152
153 if (*clump != exp) {
154 pr_warn("[%s:%u] expected clump value of 0x%lX, got clump value of 0x%lX",
155 srcfile, line, exp, *clump);
156 return false;
157 }
158
159 return true;
160 }
161
162 static bool __init
__check_eq_str(const char * srcfile,unsigned int line,const char * exp_str,const char * str,unsigned int len)163 __check_eq_str(const char *srcfile, unsigned int line,
164 const char *exp_str, const char *str,
165 unsigned int len)
166 {
167 bool eq;
168
169 eq = strncmp(exp_str, str, len) == 0;
170 if (!eq)
171 pr_err("[%s:%u] expected %s, got %s\n", srcfile, line, exp_str, str);
172
173 return eq;
174 }
175
176 #define __expect_eq(suffix, ...) \
177 ({ \
178 int result = 0; \
179 total_tests++; \
180 if (!__check_eq_ ## suffix(__FILE__, __LINE__, \
181 ##__VA_ARGS__)) { \
182 failed_tests++; \
183 result = 1; \
184 } \
185 result; \
186 })
187
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__)
194
test_zero_clear(void)195 static void __init test_zero_clear(void)
196 {
197 DECLARE_BITMAP(bmap, 1024);
198
199 /* Known way to set all bits */
200 memset(bmap, 0xff, 128);
201
202 expect_eq_pbl("0-22", bmap, 23);
203 expect_eq_pbl("0-1023", bmap, 1024);
204
205 /* single-word bitmaps */
206 bitmap_clear(bmap, 0, 9);
207 expect_eq_pbl("9-1023", bmap, 1024);
208
209 bitmap_zero(bmap, 35);
210 expect_eq_pbl("64-1023", bmap, 1024);
211
212 /* cross boundaries operations */
213 bitmap_clear(bmap, 79, 19);
214 expect_eq_pbl("64-78,98-1023", bmap, 1024);
215
216 bitmap_zero(bmap, 115);
217 expect_eq_pbl("128-1023", bmap, 1024);
218
219 /* Zeroing entire area */
220 bitmap_zero(bmap, 1024);
221 expect_eq_pbl("", bmap, 1024);
222 }
223
test_find_nth_bit(void)224 static void __init test_find_nth_bit(void)
225 {
226 unsigned long b, bit, cnt = 0;
227 DECLARE_BITMAP(bmap, 64 * 3);
228
229 bitmap_zero(bmap, 64 * 3);
230 __set_bit(10, bmap);
231 __set_bit(20, bmap);
232 __set_bit(30, bmap);
233 __set_bit(40, bmap);
234 __set_bit(50, bmap);
235 __set_bit(60, bmap);
236 __set_bit(80, bmap);
237 __set_bit(123, bmap);
238
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));
248
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));
258
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);
262 }
263 }
264
test_fill_set(void)265 static void __init test_fill_set(void)
266 {
267 DECLARE_BITMAP(bmap, 1024);
268
269 /* Known way to clear all bits */
270 memset(bmap, 0x00, 128);
271
272 expect_eq_pbl("", bmap, 23);
273 expect_eq_pbl("", bmap, 1024);
274
275 /* single-word bitmaps */
276 bitmap_set(bmap, 0, 9);
277 expect_eq_pbl("0-8", bmap, 1024);
278
279 bitmap_fill(bmap, 35);
280 expect_eq_pbl("0-63", bmap, 1024);
281
282 /* cross boundaries operations */
283 bitmap_set(bmap, 79, 19);
284 expect_eq_pbl("0-63,79-97", bmap, 1024);
285
286 bitmap_fill(bmap, 115);
287 expect_eq_pbl("0-127", bmap, 1024);
288
289 /* Zeroing entire area */
290 bitmap_fill(bmap, 1024);
291 expect_eq_pbl("0-1023", bmap, 1024);
292 }
293
test_copy(void)294 static void __init test_copy(void)
295 {
296 DECLARE_BITMAP(bmap1, 1024);
297 DECLARE_BITMAP(bmap2, 1024);
298
299 bitmap_zero(bmap1, 1024);
300 bitmap_zero(bmap2, 1024);
301
302 /* single-word bitmaps */
303 bitmap_set(bmap1, 0, 19);
304 bitmap_copy(bmap2, bmap1, 23);
305 expect_eq_pbl("0-18", bmap2, 1024);
306
307 bitmap_set(bmap2, 0, 23);
308 bitmap_copy(bmap2, bmap1, 23);
309 expect_eq_pbl("0-18", bmap2, 1024);
310
311 /* multi-word bitmaps */
312 bitmap_set(bmap1, 0, 109);
313 bitmap_copy(bmap2, bmap1, 1024);
314 expect_eq_pbl("0-108", bmap2, 1024);
315
316 bitmap_fill(bmap2, 1024);
317 bitmap_copy(bmap2, bmap1, 1024);
318 expect_eq_pbl("0-108", bmap2, 1024);
319
320 /* the following tests assume a 32- or 64-bit arch (even 128b
321 * if we care)
322 */
323
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);
327
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);
331 }
332
333 #define EXP2_IN_BITS (sizeof(exp2) * 8)
334
test_replace(void)335 static void __init test_replace(void)
336 {
337 unsigned int nbits = 64;
338 unsigned int nlongs = DIV_ROUND_UP(nbits, BITS_PER_LONG);
339 DECLARE_BITMAP(bmap, 1024);
340
341 BUILD_BUG_ON(EXP2_IN_BITS < nbits * 2);
342
343 bitmap_zero(bmap, 1024);
344 bitmap_replace(bmap, &exp2[0 * nlongs], &exp2[1 * nlongs], exp2_to_exp3_mask, nbits);
345 expect_eq_bitmap(bmap, exp3_0_1, nbits);
346
347 bitmap_zero(bmap, 1024);
348 bitmap_replace(bmap, &exp2[1 * nlongs], &exp2[0 * nlongs], exp2_to_exp3_mask, nbits);
349 expect_eq_bitmap(bmap, exp3_1_0, nbits);
350
351 bitmap_fill(bmap, 1024);
352 bitmap_replace(bmap, &exp2[0 * nlongs], &exp2[1 * nlongs], exp2_to_exp3_mask, nbits);
353 expect_eq_bitmap(bmap, exp3_0_1, nbits);
354
355 bitmap_fill(bmap, 1024);
356 bitmap_replace(bmap, &exp2[1 * nlongs], &exp2[0 * nlongs], exp2_to_exp3_mask, nbits);
357 expect_eq_bitmap(bmap, exp3_1_0, nbits);
358 }
359
360 #define PARSE_TIME 0x1
361 #define NO_LEN 0x2
362
363 struct test_bitmap_parselist{
364 const int errno;
365 const char *in;
366 const unsigned long *expected;
367 const int nbits;
368 const int flags;
369 };
370
371 static const struct test_bitmap_parselist parselist_tests[] __initconst = {
372 #define step (sizeof(u64) / sizeof(unsigned long))
373
374 {0, "0", &exp1[0], 8, 0},
375 {0, "1", &exp1[1 * step], 8, 0},
376 {0, "0-15", &exp1[2 * step], 32, 0},
377 {0, "16-31", &exp1[3 * step], 32, 0},
378 {0, "0-31:1/2", &exp1[4 * step], 32, 0},
379 {0, "1-31:1/2", &exp1[5 * step], 32, 0},
380 {0, "0-31:1/4", &exp1[6 * step], 32, 0},
381 {0, "1-31:1/4", &exp1[7 * step], 32, 0},
382 {0, "0-31:4/4", &exp1[8 * step], 32, 0},
383 {0, "1-31:4/4", &exp1[9 * step], 32, 0},
384 {0, "0-31:1/4,32-63:2/4", &exp1[10 * step], 64, 0},
385 {0, "0-31:3/4,32-63:4/4", &exp1[11 * step], 64, 0},
386 {0, " ,, 0-31:3/4 ,, 32-63:4/4 ,, ", &exp1[11 * step], 64, 0},
387
388 {0, "0-31:1/4,32-63:2/4,64-95:3/4,96-127:4/4", exp2, 128, 0},
389
390 {0, "0-2047:128/256", NULL, 2048, PARSE_TIME},
391
392 {0, "", &exp1[12 * step], 8, 0},
393 {0, "\n", &exp1[12 * step], 8, 0},
394 {0, ",, ,, , , ,", &exp1[12 * step], 8, 0},
395 {0, " , ,, , , ", &exp1[12 * step], 8, 0},
396 {0, " , ,, , , \n", &exp1[12 * step], 8, 0},
397
398 {0, "0-0", &exp1[0], 32, 0},
399 {0, "1-1", &exp1[1 * step], 32, 0},
400 {0, "15-15", &exp1[13 * step], 32, 0},
401 {0, "31-31", &exp1[14 * step], 32, 0},
402
403 {0, "0-0:0/1", &exp1[12 * step], 32, 0},
404 {0, "0-0:1/1", &exp1[0], 32, 0},
405 {0, "0-0:1/31", &exp1[0], 32, 0},
406 {0, "0-0:31/31", &exp1[0], 32, 0},
407 {0, "1-1:1/1", &exp1[1 * step], 32, 0},
408 {0, "0-15:16/31", &exp1[2 * step], 32, 0},
409 {0, "15-15:1/2", &exp1[13 * step], 32, 0},
410 {0, "15-15:31/31", &exp1[13 * step], 32, 0},
411 {0, "15-31:1/31", &exp1[13 * step], 32, 0},
412 {0, "16-31:16/31", &exp1[3 * step], 32, 0},
413 {0, "31-31:31/31", &exp1[14 * step], 32, 0},
414
415 {0, "N-N", &exp1[14 * step], 32, 0},
416 {0, "0-0:1/N", &exp1[0], 32, 0},
417 {0, "0-0:N/N", &exp1[0], 32, 0},
418 {0, "0-15:16/N", &exp1[2 * step], 32, 0},
419 {0, "15-15:N/N", &exp1[13 * step], 32, 0},
420 {0, "15-N:1/N", &exp1[13 * step], 32, 0},
421 {0, "16-N:16/N", &exp1[3 * step], 32, 0},
422 {0, "N-N:N/N", &exp1[14 * step], 32, 0},
423
424 {0, "0-N:1/3,1-N:1/3,2-N:1/3", &exp1[8 * step], 32, 0},
425 {0, "0-31:1/3,1-31:1/3,2-31:1/3", &exp1[8 * step], 32, 0},
426 {0, "1-10:8/12,8-31:24/29,0-31:0/3", &exp1[9 * step], 32, 0},
427
428 {0, "all", &exp1[8 * step], 32, 0},
429 {0, "0, 1, all, ", &exp1[8 * step], 32, 0},
430 {0, "all:1/2", &exp1[4 * step], 32, 0},
431 {0, "ALL:1/2", &exp1[4 * step], 32, 0},
432 {-EINVAL, "al", NULL, 8, 0},
433 {-EINVAL, "alll", NULL, 8, 0},
434
435 {-EINVAL, "-1", NULL, 8, 0},
436 {-EINVAL, "-0", NULL, 8, 0},
437 {-EINVAL, "10-1", NULL, 8, 0},
438 {-ERANGE, "8-8", NULL, 8, 0},
439 {-ERANGE, "0-31", NULL, 8, 0},
440 {-EINVAL, "0-31:", NULL, 32, 0},
441 {-EINVAL, "0-31:0", NULL, 32, 0},
442 {-EINVAL, "0-31:0/", NULL, 32, 0},
443 {-EINVAL, "0-31:0/0", NULL, 32, 0},
444 {-EINVAL, "0-31:1/0", NULL, 32, 0},
445 {-EINVAL, "0-31:10/1", NULL, 32, 0},
446 {-EOVERFLOW, "0-98765432123456789:10/1", NULL, 8, 0},
447
448 {-EINVAL, "a-31", NULL, 8, 0},
449 {-EINVAL, "0-a1", NULL, 8, 0},
450 {-EINVAL, "a-31:10/1", NULL, 8, 0},
451 {-EINVAL, "0-31:a/1", NULL, 8, 0},
452 {-EINVAL, "0-\n", NULL, 8, 0},
453
454 };
455
test_bitmap_parselist(void)456 static void __init test_bitmap_parselist(void)
457 {
458 int i;
459 int err;
460 ktime_t time;
461 DECLARE_BITMAP(bmap, 2048);
462
463 for (i = 0; i < ARRAY_SIZE(parselist_tests); i++) {
464 #define ptest parselist_tests[i]
465
466 time = ktime_get();
467 err = bitmap_parselist(ptest.in, bmap, ptest.nbits);
468 time = ktime_get() - time;
469
470 if (err != ptest.errno) {
471 pr_err("parselist: %d: input is %s, errno is %d, expected %d\n",
472 i, ptest.in, err, ptest.errno);
473 failed_tests++;
474 continue;
475 }
476
477 if (!err && ptest.expected
478 && !__bitmap_equal(bmap, ptest.expected, ptest.nbits)) {
479 pr_err("parselist: %d: input is %s, result is 0x%lx, expected 0x%lx\n",
480 i, ptest.in, bmap[0],
481 *ptest.expected);
482 failed_tests++;
483 continue;
484 }
485
486 if (ptest.flags & PARSE_TIME)
487 pr_err("parselist: %d: input is '%s' OK, Time: %llu\n",
488 i, ptest.in, time);
489
490 #undef ptest
491 }
492 }
493
test_bitmap_printlist(void)494 static void __init test_bitmap_printlist(void)
495 {
496 unsigned long *bmap = kmalloc(PAGE_SIZE, GFP_KERNEL);
497 char *buf = kmalloc(PAGE_SIZE, GFP_KERNEL);
498 char expected[256];
499 int ret, slen;
500 ktime_t time;
501
502 if (!buf || !bmap)
503 goto out;
504
505 memset(bmap, -1, PAGE_SIZE);
506 slen = snprintf(expected, 256, "0-%ld", PAGE_SIZE * 8 - 1);
507 if (slen < 0)
508 goto out;
509
510 time = ktime_get();
511 ret = bitmap_print_to_pagebuf(true, buf, bmap, PAGE_SIZE * 8);
512 time = ktime_get() - time;
513
514 if (ret != slen + 1) {
515 pr_err("bitmap_print_to_pagebuf: result is %d, expected %d\n", ret, slen);
516 failed_tests++;
517 goto out;
518 }
519
520 if (strncmp(buf, expected, slen)) {
521 pr_err("bitmap_print_to_pagebuf: result is %s, expected %s\n", buf, expected);
522 failed_tests++;
523 goto out;
524 }
525
526 pr_err("bitmap_print_to_pagebuf: input is '%s', Time: %llu\n", buf, time);
527 out:
528 kfree(buf);
529 kfree(bmap);
530 }
531
532 static const unsigned long parse_test[] __initconst = {
533 BITMAP_FROM_U64(0),
534 BITMAP_FROM_U64(1),
535 BITMAP_FROM_U64(0xdeadbeef),
536 BITMAP_FROM_U64(0x100000000ULL),
537 };
538
539 static const unsigned long parse_test2[] __initconst = {
540 BITMAP_FROM_U64(0x100000000ULL), BITMAP_FROM_U64(0xdeadbeef),
541 BITMAP_FROM_U64(0x100000000ULL), BITMAP_FROM_U64(0xbaadf00ddeadbeef),
542 BITMAP_FROM_U64(0x100000000ULL), BITMAP_FROM_U64(0x0badf00ddeadbeef),
543 };
544
545 static const struct test_bitmap_parselist parse_tests[] __initconst = {
546 {0, "", &parse_test[0 * step], 32, 0},
547 {0, " ", &parse_test[0 * step], 32, 0},
548 {0, "0", &parse_test[0 * step], 32, 0},
549 {0, "0\n", &parse_test[0 * step], 32, 0},
550 {0, "1", &parse_test[1 * step], 32, 0},
551 {0, "deadbeef", &parse_test[2 * step], 32, 0},
552 {0, "1,0", &parse_test[3 * step], 33, 0},
553 {0, "deadbeef,\n,0,1", &parse_test[2 * step], 96, 0},
554
555 {0, "deadbeef,1,0", &parse_test2[0 * 2 * step], 96, 0},
556 {0, "baadf00d,deadbeef,1,0", &parse_test2[1 * 2 * step], 128, 0},
557 {0, "badf00d,deadbeef,1,0", &parse_test2[2 * 2 * step], 124, 0},
558 {0, "badf00d,deadbeef,1,0", &parse_test2[2 * 2 * step], 124, NO_LEN},
559 {0, " badf00d,deadbeef,1,0 ", &parse_test2[2 * 2 * step], 124, 0},
560 {0, " , badf00d,deadbeef,1,0 , ", &parse_test2[2 * 2 * step], 124, 0},
561 {0, " , badf00d, ,, ,,deadbeef,1,0 , ", &parse_test2[2 * 2 * step], 124, 0},
562
563 {-EINVAL, "goodfood,deadbeef,1,0", NULL, 128, 0},
564 {-EOVERFLOW, "3,0", NULL, 33, 0},
565 {-EOVERFLOW, "123badf00d,deadbeef,1,0", NULL, 128, 0},
566 {-EOVERFLOW, "badf00d,deadbeef,1,0", NULL, 90, 0},
567 {-EOVERFLOW, "fbadf00d,deadbeef,1,0", NULL, 95, 0},
568 {-EOVERFLOW, "badf00d,deadbeef,1,0", NULL, 100, 0},
569 #undef step
570 };
571
test_bitmap_parse(void)572 static void __init test_bitmap_parse(void)
573 {
574 int i;
575 int err;
576 ktime_t time;
577 DECLARE_BITMAP(bmap, 2048);
578
579 for (i = 0; i < ARRAY_SIZE(parse_tests); i++) {
580 struct test_bitmap_parselist test = parse_tests[i];
581 size_t len = test.flags & NO_LEN ? UINT_MAX : strlen(test.in);
582
583 time = ktime_get();
584 err = bitmap_parse(test.in, len, bmap, test.nbits);
585 time = ktime_get() - time;
586
587 if (err != test.errno) {
588 pr_err("parse: %d: input is %s, errno is %d, expected %d\n",
589 i, test.in, err, test.errno);
590 failed_tests++;
591 continue;
592 }
593
594 if (!err && test.expected
595 && !__bitmap_equal(bmap, test.expected, test.nbits)) {
596 pr_err("parse: %d: input is %s, result is 0x%lx, expected 0x%lx\n",
597 i, test.in, bmap[0],
598 *test.expected);
599 failed_tests++;
600 continue;
601 }
602
603 if (test.flags & PARSE_TIME)
604 pr_err("parse: %d: input is '%s' OK, Time: %llu\n",
605 i, test.in, time);
606 }
607 }
608
test_bitmap_arr32(void)609 static void __init test_bitmap_arr32(void)
610 {
611 unsigned int nbits, next_bit;
612 u32 arr[EXP1_IN_BITS / 32];
613 DECLARE_BITMAP(bmap2, EXP1_IN_BITS);
614
615 memset(arr, 0xa5, sizeof(arr));
616
617 for (nbits = 0; nbits < EXP1_IN_BITS; ++nbits) {
618 bitmap_to_arr32(arr, exp1, nbits);
619 bitmap_from_arr32(bmap2, arr, nbits);
620 expect_eq_bitmap(bmap2, exp1, nbits);
621
622 next_bit = find_next_bit(bmap2,
623 round_up(nbits, BITS_PER_LONG), nbits);
624 if (next_bit < round_up(nbits, BITS_PER_LONG)) {
625 pr_err("bitmap_copy_arr32(nbits == %d:"
626 " tail is not safely cleared: %d\n",
627 nbits, next_bit);
628 failed_tests++;
629 }
630
631 if (nbits < EXP1_IN_BITS - 32)
632 expect_eq_uint(arr[DIV_ROUND_UP(nbits, 32)],
633 0xa5a5a5a5);
634 }
635 }
636
test_bitmap_arr64(void)637 static void __init test_bitmap_arr64(void)
638 {
639 unsigned int nbits, next_bit;
640 u64 arr[EXP1_IN_BITS / 64];
641 DECLARE_BITMAP(bmap2, EXP1_IN_BITS);
642
643 memset(arr, 0xa5, sizeof(arr));
644
645 for (nbits = 0; nbits < EXP1_IN_BITS; ++nbits) {
646 memset(bmap2, 0xff, sizeof(arr));
647 bitmap_to_arr64(arr, exp1, nbits);
648 bitmap_from_arr64(bmap2, arr, nbits);
649 expect_eq_bitmap(bmap2, exp1, nbits);
650
651 next_bit = find_next_bit(bmap2, round_up(nbits, BITS_PER_LONG), nbits);
652 if (next_bit < round_up(nbits, BITS_PER_LONG)) {
653 pr_err("bitmap_copy_arr64(nbits == %d:"
654 " tail is not safely cleared: %d\n", nbits, next_bit);
655 failed_tests++;
656 }
657
658 if ((nbits % 64) &&
659 (arr[(nbits - 1) / 64] & ~GENMASK_ULL((nbits - 1) % 64, 0))) {
660 pr_err("bitmap_to_arr64(nbits == %d): tail is not safely cleared: 0x%016llx (must be 0x%016llx)\n",
661 nbits, arr[(nbits - 1) / 64],
662 GENMASK_ULL((nbits - 1) % 64, 0));
663 failed_tests++;
664 }
665
666 if (nbits < EXP1_IN_BITS - 64)
667 expect_eq_uint(arr[DIV_ROUND_UP(nbits, 64)], 0xa5a5a5a5);
668 }
669 }
670
test_mem_optimisations(void)671 static void noinline __init test_mem_optimisations(void)
672 {
673 DECLARE_BITMAP(bmap1, 1024);
674 DECLARE_BITMAP(bmap2, 1024);
675 unsigned int start, nbits;
676
677 for (start = 0; start < 1024; start += 8) {
678 for (nbits = 0; nbits < 1024 - start; nbits += 8) {
679 memset(bmap1, 0x5a, sizeof(bmap1));
680 memset(bmap2, 0x5a, sizeof(bmap2));
681
682 bitmap_set(bmap1, start, nbits);
683 __bitmap_set(bmap2, start, nbits);
684 if (!bitmap_equal(bmap1, bmap2, 1024)) {
685 printk("set not equal %d %d\n", start, nbits);
686 failed_tests++;
687 }
688 if (!__bitmap_equal(bmap1, bmap2, 1024)) {
689 printk("set not __equal %d %d\n", start, nbits);
690 failed_tests++;
691 }
692
693 bitmap_clear(bmap1, start, nbits);
694 __bitmap_clear(bmap2, start, nbits);
695 if (!bitmap_equal(bmap1, bmap2, 1024)) {
696 printk("clear not equal %d %d\n", start, nbits);
697 failed_tests++;
698 }
699 if (!__bitmap_equal(bmap1, bmap2, 1024)) {
700 printk("clear not __equal %d %d\n", start,
701 nbits);
702 failed_tests++;
703 }
704 }
705 }
706 }
707
708 static const unsigned char clump_exp[] __initconst = {
709 0x01, /* 1 bit set */
710 0x02, /* non-edge 1 bit set */
711 0x00, /* zero bits set */
712 0x38, /* 3 bits set across 4-bit boundary */
713 0x38, /* Repeated clump */
714 0x0F, /* 4 bits set */
715 0xFF, /* all bits set */
716 0x05, /* non-adjacent 2 bits set */
717 };
718
test_for_each_set_clump8(void)719 static void __init test_for_each_set_clump8(void)
720 {
721 #define CLUMP_EXP_NUMBITS 64
722 DECLARE_BITMAP(bits, CLUMP_EXP_NUMBITS);
723 unsigned int start;
724 unsigned long clump;
725
726 /* set bitmap to test case */
727 bitmap_zero(bits, CLUMP_EXP_NUMBITS);
728 bitmap_set(bits, 0, 1); /* 0x01 */
729 bitmap_set(bits, 9, 1); /* 0x02 */
730 bitmap_set(bits, 27, 3); /* 0x28 */
731 bitmap_set(bits, 35, 3); /* 0x28 */
732 bitmap_set(bits, 40, 4); /* 0x0F */
733 bitmap_set(bits, 48, 8); /* 0xFF */
734 bitmap_set(bits, 56, 1); /* 0x05 - part 1 */
735 bitmap_set(bits, 58, 1); /* 0x05 - part 2 */
736
737 for_each_set_clump8(start, clump, bits, CLUMP_EXP_NUMBITS)
738 expect_eq_clump8(start, CLUMP_EXP_NUMBITS, clump_exp, &clump);
739 }
740
test_for_each_set_bit_wrap(void)741 static void __init test_for_each_set_bit_wrap(void)
742 {
743 DECLARE_BITMAP(orig, 500);
744 DECLARE_BITMAP(copy, 500);
745 unsigned int wr, bit;
746
747 bitmap_zero(orig, 500);
748
749 /* Set individual bits */
750 for (bit = 0; bit < 500; bit += 10)
751 bitmap_set(orig, bit, 1);
752
753 /* Set range of bits */
754 bitmap_set(orig, 100, 50);
755
756 for (wr = 0; wr < 500; wr++) {
757 bitmap_zero(copy, 500);
758
759 for_each_set_bit_wrap(bit, orig, 500, wr)
760 bitmap_set(copy, bit, 1);
761
762 expect_eq_bitmap(orig, copy, 500);
763 }
764 }
765
test_for_each_set_bit(void)766 static void __init test_for_each_set_bit(void)
767 {
768 DECLARE_BITMAP(orig, 500);
769 DECLARE_BITMAP(copy, 500);
770 unsigned int bit;
771
772 bitmap_zero(orig, 500);
773 bitmap_zero(copy, 500);
774
775 /* Set individual bits */
776 for (bit = 0; bit < 500; bit += 10)
777 bitmap_set(orig, bit, 1);
778
779 /* Set range of bits */
780 bitmap_set(orig, 100, 50);
781
782 for_each_set_bit(bit, orig, 500)
783 bitmap_set(copy, bit, 1);
784
785 expect_eq_bitmap(orig, copy, 500);
786 }
787
test_for_each_set_bit_from(void)788 static void __init test_for_each_set_bit_from(void)
789 {
790 DECLARE_BITMAP(orig, 500);
791 DECLARE_BITMAP(copy, 500);
792 unsigned int wr, bit;
793
794 bitmap_zero(orig, 500);
795
796 /* Set individual bits */
797 for (bit = 0; bit < 500; bit += 10)
798 bitmap_set(orig, bit, 1);
799
800 /* Set range of bits */
801 bitmap_set(orig, 100, 50);
802
803 for (wr = 0; wr < 500; wr++) {
804 DECLARE_BITMAP(tmp, 500);
805
806 bitmap_zero(copy, 500);
807 bit = wr;
808
809 for_each_set_bit_from(bit, orig, 500)
810 bitmap_set(copy, bit, 1);
811
812 bitmap_copy(tmp, orig, 500);
813 bitmap_clear(tmp, 0, wr);
814 expect_eq_bitmap(tmp, copy, 500);
815 }
816 }
817
test_for_each_clear_bit(void)818 static void __init test_for_each_clear_bit(void)
819 {
820 DECLARE_BITMAP(orig, 500);
821 DECLARE_BITMAP(copy, 500);
822 unsigned int bit;
823
824 bitmap_fill(orig, 500);
825 bitmap_fill(copy, 500);
826
827 /* Set individual bits */
828 for (bit = 0; bit < 500; bit += 10)
829 bitmap_clear(orig, bit, 1);
830
831 /* Set range of bits */
832 bitmap_clear(orig, 100, 50);
833
834 for_each_clear_bit(bit, orig, 500)
835 bitmap_clear(copy, bit, 1);
836
837 expect_eq_bitmap(orig, copy, 500);
838 }
839
test_for_each_clear_bit_from(void)840 static void __init test_for_each_clear_bit_from(void)
841 {
842 DECLARE_BITMAP(orig, 500);
843 DECLARE_BITMAP(copy, 500);
844 unsigned int wr, bit;
845
846 bitmap_fill(orig, 500);
847
848 /* Set individual bits */
849 for (bit = 0; bit < 500; bit += 10)
850 bitmap_clear(orig, bit, 1);
851
852 /* Set range of bits */
853 bitmap_clear(orig, 100, 50);
854
855 for (wr = 0; wr < 500; wr++) {
856 DECLARE_BITMAP(tmp, 500);
857
858 bitmap_fill(copy, 500);
859 bit = wr;
860
861 for_each_clear_bit_from(bit, orig, 500)
862 bitmap_clear(copy, bit, 1);
863
864 bitmap_copy(tmp, orig, 500);
865 bitmap_set(tmp, 0, wr);
866 expect_eq_bitmap(tmp, copy, 500);
867 }
868 }
869
test_for_each_set_bitrange(void)870 static void __init test_for_each_set_bitrange(void)
871 {
872 DECLARE_BITMAP(orig, 500);
873 DECLARE_BITMAP(copy, 500);
874 unsigned int s, e;
875
876 bitmap_zero(orig, 500);
877 bitmap_zero(copy, 500);
878
879 /* Set individual bits */
880 for (s = 0; s < 500; s += 10)
881 bitmap_set(orig, s, 1);
882
883 /* Set range of bits */
884 bitmap_set(orig, 100, 50);
885
886 for_each_set_bitrange(s, e, orig, 500)
887 bitmap_set(copy, s, e-s);
888
889 expect_eq_bitmap(orig, copy, 500);
890 }
891
test_for_each_clear_bitrange(void)892 static void __init test_for_each_clear_bitrange(void)
893 {
894 DECLARE_BITMAP(orig, 500);
895 DECLARE_BITMAP(copy, 500);
896 unsigned int s, e;
897
898 bitmap_fill(orig, 500);
899 bitmap_fill(copy, 500);
900
901 /* Set individual bits */
902 for (s = 0; s < 500; s += 10)
903 bitmap_clear(orig, s, 1);
904
905 /* Set range of bits */
906 bitmap_clear(orig, 100, 50);
907
908 for_each_clear_bitrange(s, e, orig, 500)
909 bitmap_clear(copy, s, e-s);
910
911 expect_eq_bitmap(orig, copy, 500);
912 }
913
test_for_each_set_bitrange_from(void)914 static void __init test_for_each_set_bitrange_from(void)
915 {
916 DECLARE_BITMAP(orig, 500);
917 DECLARE_BITMAP(copy, 500);
918 unsigned int wr, s, e;
919
920 bitmap_zero(orig, 500);
921
922 /* Set individual bits */
923 for (s = 0; s < 500; s += 10)
924 bitmap_set(orig, s, 1);
925
926 /* Set range of bits */
927 bitmap_set(orig, 100, 50);
928
929 for (wr = 0; wr < 500; wr++) {
930 DECLARE_BITMAP(tmp, 500);
931
932 bitmap_zero(copy, 500);
933 s = wr;
934
935 for_each_set_bitrange_from(s, e, orig, 500)
936 bitmap_set(copy, s, e - s);
937
938 bitmap_copy(tmp, orig, 500);
939 bitmap_clear(tmp, 0, wr);
940 expect_eq_bitmap(tmp, copy, 500);
941 }
942 }
943
test_for_each_clear_bitrange_from(void)944 static void __init test_for_each_clear_bitrange_from(void)
945 {
946 DECLARE_BITMAP(orig, 500);
947 DECLARE_BITMAP(copy, 500);
948 unsigned int wr, s, e;
949
950 bitmap_fill(orig, 500);
951
952 /* Set individual bits */
953 for (s = 0; s < 500; s += 10)
954 bitmap_clear(orig, s, 1);
955
956 /* Set range of bits */
957 bitmap_set(orig, 100, 50);
958
959 for (wr = 0; wr < 500; wr++) {
960 DECLARE_BITMAP(tmp, 500);
961
962 bitmap_fill(copy, 500);
963 s = wr;
964
965 for_each_clear_bitrange_from(s, e, orig, 500)
966 bitmap_clear(copy, s, e - s);
967
968 bitmap_copy(tmp, orig, 500);
969 bitmap_set(tmp, 0, wr);
970 expect_eq_bitmap(tmp, copy, 500);
971 }
972 }
973
974 struct test_bitmap_cut {
975 unsigned int first;
976 unsigned int cut;
977 unsigned int nbits;
978 unsigned long in[4];
979 unsigned long expected[4];
980 };
981
982 static struct test_bitmap_cut test_cut[] = {
983 { 0, 0, 8, { 0x0000000aUL, }, { 0x0000000aUL, }, },
984 { 0, 0, 32, { 0xdadadeadUL, }, { 0xdadadeadUL, }, },
985 { 0, 3, 8, { 0x000000aaUL, }, { 0x00000015UL, }, },
986 { 3, 3, 8, { 0x000000aaUL, }, { 0x00000012UL, }, },
987 { 0, 1, 32, { 0xa5a5a5a5UL, }, { 0x52d2d2d2UL, }, },
988 { 0, 8, 32, { 0xdeadc0deUL, }, { 0x00deadc0UL, }, },
989 { 1, 1, 32, { 0x5a5a5a5aUL, }, { 0x2d2d2d2cUL, }, },
990 { 0, 15, 32, { 0xa5a5a5a5UL, }, { 0x00014b4bUL, }, },
991 { 0, 16, 32, { 0xa5a5a5a5UL, }, { 0x0000a5a5UL, }, },
992 { 15, 15, 32, { 0xa5a5a5a5UL, }, { 0x000125a5UL, }, },
993 { 15, 16, 32, { 0xa5a5a5a5UL, }, { 0x0000a5a5UL, }, },
994 { 16, 15, 32, { 0xa5a5a5a5UL, }, { 0x0001a5a5UL, }, },
995
996 { BITS_PER_LONG, BITS_PER_LONG, BITS_PER_LONG,
997 { 0xa5a5a5a5UL, 0xa5a5a5a5UL, },
998 { 0xa5a5a5a5UL, 0xa5a5a5a5UL, },
999 },
1000 { 1, BITS_PER_LONG - 1, BITS_PER_LONG,
1001 { 0xa5a5a5a5UL, 0xa5a5a5a5UL, },
1002 { 0x00000001UL, 0x00000001UL, },
1003 },
1004
1005 { 0, BITS_PER_LONG * 2, BITS_PER_LONG * 2 + 1,
1006 { 0xa5a5a5a5UL, 0x00000001UL, 0x00000001UL, 0x00000001UL },
1007 { 0x00000001UL, },
1008 },
1009 { 16, BITS_PER_LONG * 2 + 1, BITS_PER_LONG * 2 + 1 + 16,
1010 { 0x0000ffffUL, 0x5a5a5a5aUL, 0x5a5a5a5aUL, 0x5a5a5a5aUL },
1011 { 0x2d2dffffUL, },
1012 },
1013 };
1014
test_bitmap_cut(void)1015 static void __init test_bitmap_cut(void)
1016 {
1017 unsigned long b[5], *in = &b[1], *out = &b[0]; /* Partial overlap */
1018 int i;
1019
1020 for (i = 0; i < ARRAY_SIZE(test_cut); i++) {
1021 struct test_bitmap_cut *t = &test_cut[i];
1022
1023 memcpy(in, t->in, sizeof(t->in));
1024
1025 bitmap_cut(out, in, t->first, t->cut, t->nbits);
1026
1027 expect_eq_bitmap(t->expected, out, t->nbits);
1028 }
1029 }
1030
1031 struct test_bitmap_print {
1032 const unsigned long *bitmap;
1033 unsigned long nbits;
1034 const char *mask;
1035 const char *list;
1036 };
1037
1038 static const unsigned long small_bitmap[] __initconst = {
1039 BITMAP_FROM_U64(0x3333333311111111ULL),
1040 };
1041
1042 static const char small_mask[] __initconst = "33333333,11111111\n";
1043 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";
1044
1045 static const unsigned long large_bitmap[] __initconst = {
1046 BITMAP_FROM_U64(0x3333333311111111ULL), BITMAP_FROM_U64(0x3333333311111111ULL),
1047 BITMAP_FROM_U64(0x3333333311111111ULL), BITMAP_FROM_U64(0x3333333311111111ULL),
1048 BITMAP_FROM_U64(0x3333333311111111ULL), BITMAP_FROM_U64(0x3333333311111111ULL),
1049 BITMAP_FROM_U64(0x3333333311111111ULL), BITMAP_FROM_U64(0x3333333311111111ULL),
1050 BITMAP_FROM_U64(0x3333333311111111ULL), BITMAP_FROM_U64(0x3333333311111111ULL),
1051 BITMAP_FROM_U64(0x3333333311111111ULL), BITMAP_FROM_U64(0x3333333311111111ULL),
1052 BITMAP_FROM_U64(0x3333333311111111ULL), BITMAP_FROM_U64(0x3333333311111111ULL),
1053 BITMAP_FROM_U64(0x3333333311111111ULL), BITMAP_FROM_U64(0x3333333311111111ULL),
1054 BITMAP_FROM_U64(0x3333333311111111ULL), BITMAP_FROM_U64(0x3333333311111111ULL),
1055 BITMAP_FROM_U64(0x3333333311111111ULL), BITMAP_FROM_U64(0x3333333311111111ULL),
1056 BITMAP_FROM_U64(0x3333333311111111ULL), BITMAP_FROM_U64(0x3333333311111111ULL),
1057 BITMAP_FROM_U64(0x3333333311111111ULL), BITMAP_FROM_U64(0x3333333311111111ULL),
1058 BITMAP_FROM_U64(0x3333333311111111ULL), BITMAP_FROM_U64(0x3333333311111111ULL),
1059 BITMAP_FROM_U64(0x3333333311111111ULL), BITMAP_FROM_U64(0x3333333311111111ULL),
1060 BITMAP_FROM_U64(0x3333333311111111ULL), BITMAP_FROM_U64(0x3333333311111111ULL),
1061 BITMAP_FROM_U64(0x3333333311111111ULL), BITMAP_FROM_U64(0x3333333311111111ULL),
1062 BITMAP_FROM_U64(0x3333333311111111ULL), BITMAP_FROM_U64(0x3333333311111111ULL),
1063 BITMAP_FROM_U64(0x3333333311111111ULL), BITMAP_FROM_U64(0x3333333311111111ULL),
1064 BITMAP_FROM_U64(0x3333333311111111ULL), BITMAP_FROM_U64(0x3333333311111111ULL),
1065 BITMAP_FROM_U64(0x3333333311111111ULL), BITMAP_FROM_U64(0x3333333311111111ULL),
1066 };
1067
1068 static const char large_mask[] __initconst = "33333333,11111111,33333333,11111111,"
1069 "33333333,11111111,33333333,11111111,"
1070 "33333333,11111111,33333333,11111111,"
1071 "33333333,11111111,33333333,11111111,"
1072 "33333333,11111111,33333333,11111111,"
1073 "33333333,11111111,33333333,11111111,"
1074 "33333333,11111111,33333333,11111111,"
1075 "33333333,11111111,33333333,11111111,"
1076 "33333333,11111111,33333333,11111111,"
1077 "33333333,11111111,33333333,11111111,"
1078 "33333333,11111111,33333333,11111111,"
1079 "33333333,11111111,33333333,11111111,"
1080 "33333333,11111111,33333333,11111111,"
1081 "33333333,11111111,33333333,11111111,"
1082 "33333333,11111111,33333333,11111111,"
1083 "33333333,11111111,33333333,11111111,"
1084 "33333333,11111111,33333333,11111111,"
1085 "33333333,11111111,33333333,11111111,"
1086 "33333333,11111111,33333333,11111111,"
1087 "33333333,11111111,33333333,11111111\n";
1088
1089 static const char large_list[] __initconst = /* more than 4KB */
1090 "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"
1091 "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"
1092 "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"
1093 "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"
1094 "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"
1095 "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"
1096 "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"
1097 "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"
1098 "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"
1099 "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"
1100 "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"
1101 "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"
1102 "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-"
1103 "1001,1004-1005,1008-1009,1012-1013,1016-1017,1020-1021,1024,1028,1032,1036,1040,1044,1048,1052,1056-1057,1060-10"
1104 "61,1064-1065,1068-1069,1072-1073,1076-1077,1080-1081,1084-1085,1088,1092,1096,1100,1104,1108,1112,1116,1120-1121"
1105 ",1124-1125,1128-1129,1132-1133,1136-1137,1140-1141,1144-1145,1148-1149,1152,1156,1160,1164,1168,1172,1176,1180,1"
1106 "184-1185,1188-1189,1192-1193,1196-1197,1200-1201,1204-1205,1208-1209,1212-1213,1216,1220,1224,1228,1232,1236,124"
1107 "0,1244,1248-1249,1252-1253,1256-1257,1260-1261,1264-1265,1268-1269,1272-1273,1276-1277,1280,1284,1288,1292,1296,"
1108 "1300,1304,1308,1312-1313,1316-1317,1320-1321,1324-1325,1328-1329,1332-1333,1336-1337,1340-1341,1344,1348,1352,13"
1109 "56,1360,1364,1368,1372,1376-1377,1380-1381,1384-1385,1388-1389,1392-1393,1396-1397,1400-1401,1404-1405,1408,1412"
1110 ",1416,1420,1424,1428,1432,1436,1440-1441,1444-1445,1448-1449,1452-1453,1456-1457,1460-1461,1464-1465,1468-1469,1"
1111 "472,1476,1480,1484,1488,1492,1496,1500,1504-1505,1508-1509,1512-1513,1516-1517,1520-1521,1524-1525,1528-1529,153"
1112 "2-1533,1536,1540,1544,1548,1552,1556,1560,1564,1568-1569,1572-1573,1576-1577,1580-1581,1584-1585,1588-1589,1592-"
1113 "1593,1596-1597,1600,1604,1608,1612,1616,1620,1624,1628,1632-1633,1636-1637,1640-1641,1644-1645,1648-1649,1652-16"
1114 "53,1656-1657,1660-1661,1664,1668,1672,1676,1680,1684,1688,1692,1696-1697,1700-1701,1704-1705,1708-1709,1712-1713"
1115 ",1716-1717,1720-1721,1724-1725,1728,1732,1736,1740,1744,1748,1752,1756,1760-1761,1764-1765,1768-1769,1772-1773,1"
1116 "776-1777,1780-1781,1784-1785,1788-1789,1792,1796,1800,1804,1808,1812,1816,1820,1824-1825,1828-1829,1832-1833,183"
1117 "6-1837,1840-1841,1844-1845,1848-1849,1852-1853,1856,1860,1864,1868,1872,1876,1880,1884,1888-1889,1892-1893,1896-"
1118 "1897,1900-1901,1904-1905,1908-1909,1912-1913,1916-1917,1920,1924,1928,1932,1936,1940,1944,1948,1952-1953,1956-19"
1119 "57,1960-1961,1964-1965,1968-1969,1972-1973,1976-1977,1980-1981,1984,1988,1992,1996,2000,2004,2008,2012,2016-2017"
1120 ",2020-2021,2024-2025,2028-2029,2032-2033,2036-2037,2040-2041,2044-2045,2048,2052,2056,2060,2064,2068,2072,2076,2"
1121 "080-2081,2084-2085,2088-2089,2092-2093,2096-2097,2100-2101,2104-2105,2108-2109,2112,2116,2120,2124,2128,2132,213"
1122 "6,2140,2144-2145,2148-2149,2152-2153,2156-2157,2160-2161,2164-2165,2168-2169,2172-2173,2176,2180,2184,2188,2192,"
1123 "2196,2200,2204,2208-2209,2212-2213,2216-2217,2220-2221,2224-2225,2228-2229,2232-2233,2236-2237,2240,2244,2248,22"
1124 "52,2256,2260,2264,2268,2272-2273,2276-2277,2280-2281,2284-2285,2288-2289,2292-2293,2296-2297,2300-2301,2304,2308"
1125 ",2312,2316,2320,2324,2328,2332,2336-2337,2340-2341,2344-2345,2348-2349,2352-2353,2356-2357,2360-2361,2364-2365,2"
1126 "368,2372,2376,2380,2384,2388,2392,2396,2400-2401,2404-2405,2408-2409,2412-2413,2416-2417,2420-2421,2424-2425,242"
1127 "8-2429,2432,2436,2440,2444,2448,2452,2456,2460,2464-2465,2468-2469,2472-2473,2476-2477,2480-2481,2484-2485,2488-"
1128 "2489,2492-2493,2496,2500,2504,2508,2512,2516,2520,2524,2528-2529,2532-2533,2536-2537,2540-2541,2544-2545,2548-25"
1129 "49,2552-2553,2556-2557\n";
1130
1131 static const struct test_bitmap_print test_print[] __initconst = {
1132 { small_bitmap, sizeof(small_bitmap) * BITS_PER_BYTE, small_mask, small_list },
1133 { large_bitmap, sizeof(large_bitmap) * BITS_PER_BYTE, large_mask, large_list },
1134 };
1135
test_bitmap_print_buf(void)1136 static void __init test_bitmap_print_buf(void)
1137 {
1138 int i;
1139
1140 for (i = 0; i < ARRAY_SIZE(test_print); i++) {
1141 const struct test_bitmap_print *t = &test_print[i];
1142 int n;
1143
1144 n = bitmap_print_bitmask_to_buf(print_buf, t->bitmap, t->nbits,
1145 0, 2 * PAGE_SIZE);
1146 expect_eq_uint(strlen(t->mask) + 1, n);
1147 expect_eq_str(t->mask, print_buf, n);
1148
1149 n = bitmap_print_list_to_buf(print_buf, t->bitmap, t->nbits,
1150 0, 2 * PAGE_SIZE);
1151 expect_eq_uint(strlen(t->list) + 1, n);
1152 expect_eq_str(t->list, print_buf, n);
1153
1154 /* test by non-zero offset */
1155 if (strlen(t->list) > PAGE_SIZE) {
1156 n = bitmap_print_list_to_buf(print_buf, t->bitmap, t->nbits,
1157 PAGE_SIZE, PAGE_SIZE);
1158 expect_eq_uint(strlen(t->list) + 1 - PAGE_SIZE, n);
1159 expect_eq_str(t->list + PAGE_SIZE, print_buf, n);
1160 }
1161 }
1162 }
1163
1164 /*
1165 * FIXME: Clang breaks compile-time evaluations when KASAN and GCOV are enabled.
1166 * To workaround it, GCOV is force-disabled in Makefile for this configuration.
1167 */
test_bitmap_const_eval(void)1168 static void __init test_bitmap_const_eval(void)
1169 {
1170 DECLARE_BITMAP(bitmap, BITS_PER_LONG);
1171 unsigned long initvar = BIT(2);
1172 unsigned long bitopvar = 0;
1173 unsigned long var = 0;
1174 int res;
1175
1176 /*
1177 * Compilers must be able to optimize all of those to compile-time
1178 * constants on any supported optimization level (-O2, -Os) and any
1179 * architecture. Otherwise, trigger a build bug.
1180 * The whole function gets optimized out then, there's nothing to do
1181 * in runtime.
1182 */
1183
1184 /*
1185 * Equals to `unsigned long bitmap[1] = { GENMASK(6, 5), }`.
1186 * Clang on s390 optimizes bitops at compile-time as intended, but at
1187 * the same time stops treating @bitmap and @bitopvar as compile-time
1188 * constants after regular test_bit() is executed, thus triggering the
1189 * build bugs below. So, call const_test_bit() there directly until
1190 * the compiler is fixed.
1191 */
1192 bitmap_clear(bitmap, 0, BITS_PER_LONG);
1193 if (!test_bit(7, bitmap))
1194 bitmap_set(bitmap, 5, 2);
1195
1196 /* Equals to `unsigned long bitopvar = BIT(20)` */
1197 __change_bit(31, &bitopvar);
1198 bitmap_shift_right(&bitopvar, &bitopvar, 11, BITS_PER_LONG);
1199
1200 /* Equals to `unsigned long var = BIT(25)` */
1201 var |= BIT(25);
1202 if (var & BIT(0))
1203 var ^= GENMASK(9, 6);
1204
1205 /* __const_hweight<32|64>(GENMASK(6, 5)) == 2 */
1206 res = bitmap_weight(bitmap, 20);
1207 BUILD_BUG_ON(!__builtin_constant_p(res));
1208 BUILD_BUG_ON(res != 2);
1209
1210 /* !(BIT(31) & BIT(18)) == 1 */
1211 res = !test_bit(18, &bitopvar);
1212 BUILD_BUG_ON(!__builtin_constant_p(res));
1213 BUILD_BUG_ON(!res);
1214
1215 /* BIT(2) & GENMASK(14, 8) == 0 */
1216 res = initvar & GENMASK(14, 8);
1217 BUILD_BUG_ON(!__builtin_constant_p(res));
1218 BUILD_BUG_ON(res);
1219
1220 /* ~BIT(25) */
1221 BUILD_BUG_ON(!__builtin_constant_p(~var));
1222 BUILD_BUG_ON(~var != ~BIT(25));
1223 }
1224
selftest(void)1225 static void __init selftest(void)
1226 {
1227 test_zero_clear();
1228 test_fill_set();
1229 test_copy();
1230 test_replace();
1231 test_bitmap_arr32();
1232 test_bitmap_arr64();
1233 test_bitmap_parse();
1234 test_bitmap_parselist();
1235 test_bitmap_printlist();
1236 test_mem_optimisations();
1237 test_bitmap_cut();
1238 test_bitmap_print_buf();
1239 test_bitmap_const_eval();
1240
1241 test_find_nth_bit();
1242 test_for_each_set_bit();
1243 test_for_each_set_bit_from();
1244 test_for_each_clear_bit();
1245 test_for_each_clear_bit_from();
1246 test_for_each_set_bitrange();
1247 test_for_each_clear_bitrange();
1248 test_for_each_set_bitrange_from();
1249 test_for_each_clear_bitrange_from();
1250 test_for_each_set_clump8();
1251 test_for_each_set_bit_wrap();
1252 }
1253
1254 KSTM_MODULE_LOADERS(test_bitmap);
1255 MODULE_AUTHOR("david decotigny <david.decotigny@googlers.com>");
1256 MODULE_LICENSE("GPL");
1257