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