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