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