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