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