1
2
3
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
48static const unsigned long exp2_to_exp3_mask[] __initconst = {
49 BITMAP_FROM_U64(0x008000020020212eULL),
50};
51
52static const unsigned long exp3_0_1[] __initconst = {
53 BITMAP_FROM_U64(0x33b3333311313137ULL),
54};
55
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
198 memset(bmap, 0xff, 128);
199
200 expect_eq_pbl("0-22", bmap, 23);
201 expect_eq_pbl("0-1023", bmap, 1024);
202
203
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
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
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
227 memset(bmap, 0x00, 128);
228
229 expect_eq_pbl("", bmap, 23);
230 expect_eq_pbl("", bmap, 1024);
231
232
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
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
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
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
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
278
279
280
281 bitmap_fill(bmap2, 1024);
282 bitmap_copy(bmap2, bmap1, 109);
283 expect_eq_pbl("0-108,128-1023", bmap2, 1024);
284
285 bitmap_fill(bmap2, 1024);
286 bitmap_copy(bmap2, bmap1, 97);
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 const unsigned long parse_test[] __initconst = {
450 BITMAP_FROM_U64(0),
451 BITMAP_FROM_U64(1),
452 BITMAP_FROM_U64(0xdeadbeef),
453 BITMAP_FROM_U64(0x100000000ULL),
454};
455
456static const unsigned long parse_test2[] __initconst = {
457 BITMAP_FROM_U64(0x100000000ULL), BITMAP_FROM_U64(0xdeadbeef),
458 BITMAP_FROM_U64(0x100000000ULL), BITMAP_FROM_U64(0xbaadf00ddeadbeef),
459 BITMAP_FROM_U64(0x100000000ULL), BITMAP_FROM_U64(0x0badf00ddeadbeef),
460};
461
462static const struct test_bitmap_parselist parse_tests[] __initconst = {
463 {0, "", &parse_test[0 * step], 32, 0},
464 {0, " ", &parse_test[0 * step], 32, 0},
465 {0, "0", &parse_test[0 * step], 32, 0},
466 {0, "0\n", &parse_test[0 * step], 32, 0},
467 {0, "1", &parse_test[1 * step], 32, 0},
468 {0, "deadbeef", &parse_test[2 * step], 32, 0},
469 {0, "1,0", &parse_test[3 * step], 33, 0},
470 {0, "deadbeef,\n,0,1", &parse_test[2 * step], 96, 0},
471
472 {0, "deadbeef,1,0", &parse_test2[0 * 2 * step], 96, 0},
473 {0, "baadf00d,deadbeef,1,0", &parse_test2[1 * 2 * step], 128, 0},
474 {0, "badf00d,deadbeef,1,0", &parse_test2[2 * 2 * step], 124, 0},
475 {0, "badf00d,deadbeef,1,0", &parse_test2[2 * 2 * step], 124, NO_LEN},
476 {0, " badf00d,deadbeef,1,0 ", &parse_test2[2 * 2 * step], 124, 0},
477 {0, " , badf00d,deadbeef,1,0 , ", &parse_test2[2 * 2 * step], 124, 0},
478 {0, " , badf00d, ,, ,,deadbeef,1,0 , ", &parse_test2[2 * 2 * step], 124, 0},
479
480 {-EINVAL, "goodfood,deadbeef,1,0", NULL, 128, 0},
481 {-EOVERFLOW, "3,0", NULL, 33, 0},
482 {-EOVERFLOW, "123badf00d,deadbeef,1,0", NULL, 128, 0},
483 {-EOVERFLOW, "badf00d,deadbeef,1,0", NULL, 90, 0},
484 {-EOVERFLOW, "fbadf00d,deadbeef,1,0", NULL, 95, 0},
485 {-EOVERFLOW, "badf00d,deadbeef,1,0", NULL, 100, 0},
486#undef step
487};
488
489static void __init test_bitmap_parse(void)
490{
491 int i;
492 int err;
493 ktime_t time;
494 DECLARE_BITMAP(bmap, 2048);
495
496 for (i = 0; i < ARRAY_SIZE(parse_tests); i++) {
497 struct test_bitmap_parselist test = parse_tests[i];
498 size_t len = test.flags & NO_LEN ? UINT_MAX : strlen(test.in);
499
500 time = ktime_get();
501 err = bitmap_parse(test.in, len, bmap, test.nbits);
502 time = ktime_get() - time;
503
504 if (err != test.errno) {
505 pr_err("parse: %d: input is %s, errno is %d, expected %d\n",
506 i, test.in, err, test.errno);
507 continue;
508 }
509
510 if (!err && test.expected
511 && !__bitmap_equal(bmap, test.expected, test.nbits)) {
512 pr_err("parse: %d: input is %s, result is 0x%lx, expected 0x%lx\n",
513 i, test.in, bmap[0],
514 *test.expected);
515 continue;
516 }
517
518 if (test.flags & PARSE_TIME)
519 pr_err("parse: %d: input is '%s' OK, Time: %llu\n",
520 i, test.in, time);
521 }
522}
523
524#define EXP1_IN_BITS (sizeof(exp1) * 8)
525
526static void __init test_bitmap_arr32(void)
527{
528 unsigned int nbits, next_bit;
529 u32 arr[EXP1_IN_BITS / 32];
530 DECLARE_BITMAP(bmap2, EXP1_IN_BITS);
531
532 memset(arr, 0xa5, sizeof(arr));
533
534 for (nbits = 0; nbits < EXP1_IN_BITS; ++nbits) {
535 bitmap_to_arr32(arr, exp1, nbits);
536 bitmap_from_arr32(bmap2, arr, nbits);
537 expect_eq_bitmap(bmap2, exp1, nbits);
538
539 next_bit = find_next_bit(bmap2,
540 round_up(nbits, BITS_PER_LONG), nbits);
541 if (next_bit < round_up(nbits, BITS_PER_LONG))
542 pr_err("bitmap_copy_arr32(nbits == %d:"
543 " tail is not safely cleared: %d\n",
544 nbits, next_bit);
545
546 if (nbits < EXP1_IN_BITS - 32)
547 expect_eq_uint(arr[DIV_ROUND_UP(nbits, 32)],
548 0xa5a5a5a5);
549 }
550}
551
552static void noinline __init test_mem_optimisations(void)
553{
554 DECLARE_BITMAP(bmap1, 1024);
555 DECLARE_BITMAP(bmap2, 1024);
556 unsigned int start, nbits;
557
558 for (start = 0; start < 1024; start += 8) {
559 for (nbits = 0; nbits < 1024 - start; nbits += 8) {
560 memset(bmap1, 0x5a, sizeof(bmap1));
561 memset(bmap2, 0x5a, sizeof(bmap2));
562
563 bitmap_set(bmap1, start, nbits);
564 __bitmap_set(bmap2, start, nbits);
565 if (!bitmap_equal(bmap1, bmap2, 1024)) {
566 printk("set not equal %d %d\n", start, nbits);
567 failed_tests++;
568 }
569 if (!__bitmap_equal(bmap1, bmap2, 1024)) {
570 printk("set not __equal %d %d\n", start, nbits);
571 failed_tests++;
572 }
573
574 bitmap_clear(bmap1, start, nbits);
575 __bitmap_clear(bmap2, start, nbits);
576 if (!bitmap_equal(bmap1, bmap2, 1024)) {
577 printk("clear not equal %d %d\n", start, nbits);
578 failed_tests++;
579 }
580 if (!__bitmap_equal(bmap1, bmap2, 1024)) {
581 printk("clear not __equal %d %d\n", start,
582 nbits);
583 failed_tests++;
584 }
585 }
586 }
587}
588
589static const unsigned char clump_exp[] __initconst = {
590 0x01,
591 0x02,
592 0x00,
593 0x38,
594 0x38,
595 0x0F,
596 0xFF,
597 0x05,
598};
599
600static void __init test_for_each_set_clump8(void)
601{
602#define CLUMP_EXP_NUMBITS 64
603 DECLARE_BITMAP(bits, CLUMP_EXP_NUMBITS);
604 unsigned int start;
605 unsigned long clump;
606
607
608 bitmap_zero(bits, CLUMP_EXP_NUMBITS);
609 bitmap_set(bits, 0, 1);
610 bitmap_set(bits, 9, 1);
611 bitmap_set(bits, 27, 3);
612 bitmap_set(bits, 35, 3);
613 bitmap_set(bits, 40, 4);
614 bitmap_set(bits, 48, 8);
615 bitmap_set(bits, 56, 1);
616 bitmap_set(bits, 58, 1);
617
618 for_each_set_clump8(start, clump, bits, CLUMP_EXP_NUMBITS)
619 expect_eq_clump8(start, CLUMP_EXP_NUMBITS, clump_exp, &clump);
620}
621
622struct test_bitmap_cut {
623 unsigned int first;
624 unsigned int cut;
625 unsigned int nbits;
626 unsigned long in[4];
627 unsigned long expected[4];
628};
629
630static struct test_bitmap_cut test_cut[] = {
631 { 0, 0, 8, { 0x0000000aUL, }, { 0x0000000aUL, }, },
632 { 0, 0, 32, { 0xdadadeadUL, }, { 0xdadadeadUL, }, },
633 { 0, 3, 8, { 0x000000aaUL, }, { 0x00000015UL, }, },
634 { 3, 3, 8, { 0x000000aaUL, }, { 0x00000012UL, }, },
635 { 0, 1, 32, { 0xa5a5a5a5UL, }, { 0x52d2d2d2UL, }, },
636 { 0, 8, 32, { 0xdeadc0deUL, }, { 0x00deadc0UL, }, },
637 { 1, 1, 32, { 0x5a5a5a5aUL, }, { 0x2d2d2d2cUL, }, },
638 { 0, 15, 32, { 0xa5a5a5a5UL, }, { 0x00014b4bUL, }, },
639 { 0, 16, 32, { 0xa5a5a5a5UL, }, { 0x0000a5a5UL, }, },
640 { 15, 15, 32, { 0xa5a5a5a5UL, }, { 0x000125a5UL, }, },
641 { 15, 16, 32, { 0xa5a5a5a5UL, }, { 0x0000a5a5UL, }, },
642 { 16, 15, 32, { 0xa5a5a5a5UL, }, { 0x0001a5a5UL, }, },
643
644 { BITS_PER_LONG, BITS_PER_LONG, BITS_PER_LONG,
645 { 0xa5a5a5a5UL, 0xa5a5a5a5UL, },
646 { 0xa5a5a5a5UL, 0xa5a5a5a5UL, },
647 },
648 { 1, BITS_PER_LONG - 1, BITS_PER_LONG,
649 { 0xa5a5a5a5UL, 0xa5a5a5a5UL, },
650 { 0x00000001UL, 0x00000001UL, },
651 },
652
653 { 0, BITS_PER_LONG * 2, BITS_PER_LONG * 2 + 1,
654 { 0xa5a5a5a5UL, 0x00000001UL, 0x00000001UL, 0x00000001UL },
655 { 0x00000001UL, },
656 },
657 { 16, BITS_PER_LONG * 2 + 1, BITS_PER_LONG * 2 + 1 + 16,
658 { 0x0000ffffUL, 0x5a5a5a5aUL, 0x5a5a5a5aUL, 0x5a5a5a5aUL },
659 { 0x2d2dffffUL, },
660 },
661};
662
663static void __init test_bitmap_cut(void)
664{
665 unsigned long b[5], *in = &b[1], *out = &b[0];
666 int i;
667
668 for (i = 0; i < ARRAY_SIZE(test_cut); i++) {
669 struct test_bitmap_cut *t = &test_cut[i];
670
671 memcpy(in, t->in, sizeof(t->in));
672
673 bitmap_cut(out, in, t->first, t->cut, t->nbits);
674
675 expect_eq_bitmap(t->expected, out, t->nbits);
676 }
677}
678
679struct test_bitmap_print {
680 const unsigned long *bitmap;
681 unsigned long nbits;
682 const char *mask;
683 const char *list;
684};
685
686static const unsigned long small_bitmap[] __initconst = {
687 BITMAP_FROM_U64(0x3333333311111111ULL),
688};
689
690static const char small_mask[] __initconst = "33333333,11111111\n";
691static 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";
692
693static const unsigned long large_bitmap[] __initconst = {
694 BITMAP_FROM_U64(0x3333333311111111ULL), BITMAP_FROM_U64(0x3333333311111111ULL),
695 BITMAP_FROM_U64(0x3333333311111111ULL), BITMAP_FROM_U64(0x3333333311111111ULL),
696 BITMAP_FROM_U64(0x3333333311111111ULL), BITMAP_FROM_U64(0x3333333311111111ULL),
697 BITMAP_FROM_U64(0x3333333311111111ULL), BITMAP_FROM_U64(0x3333333311111111ULL),
698 BITMAP_FROM_U64(0x3333333311111111ULL), BITMAP_FROM_U64(0x3333333311111111ULL),
699 BITMAP_FROM_U64(0x3333333311111111ULL), BITMAP_FROM_U64(0x3333333311111111ULL),
700 BITMAP_FROM_U64(0x3333333311111111ULL), BITMAP_FROM_U64(0x3333333311111111ULL),
701 BITMAP_FROM_U64(0x3333333311111111ULL), BITMAP_FROM_U64(0x3333333311111111ULL),
702 BITMAP_FROM_U64(0x3333333311111111ULL), BITMAP_FROM_U64(0x3333333311111111ULL),
703 BITMAP_FROM_U64(0x3333333311111111ULL), BITMAP_FROM_U64(0x3333333311111111ULL),
704 BITMAP_FROM_U64(0x3333333311111111ULL), BITMAP_FROM_U64(0x3333333311111111ULL),
705 BITMAP_FROM_U64(0x3333333311111111ULL), BITMAP_FROM_U64(0x3333333311111111ULL),
706 BITMAP_FROM_U64(0x3333333311111111ULL), BITMAP_FROM_U64(0x3333333311111111ULL),
707 BITMAP_FROM_U64(0x3333333311111111ULL), BITMAP_FROM_U64(0x3333333311111111ULL),
708 BITMAP_FROM_U64(0x3333333311111111ULL), BITMAP_FROM_U64(0x3333333311111111ULL),
709 BITMAP_FROM_U64(0x3333333311111111ULL), BITMAP_FROM_U64(0x3333333311111111ULL),
710 BITMAP_FROM_U64(0x3333333311111111ULL), BITMAP_FROM_U64(0x3333333311111111ULL),
711 BITMAP_FROM_U64(0x3333333311111111ULL), BITMAP_FROM_U64(0x3333333311111111ULL),
712 BITMAP_FROM_U64(0x3333333311111111ULL), BITMAP_FROM_U64(0x3333333311111111ULL),
713 BITMAP_FROM_U64(0x3333333311111111ULL), BITMAP_FROM_U64(0x3333333311111111ULL),
714};
715
716static const char large_mask[] __initconst = "33333333,11111111,33333333,11111111,"
717 "33333333,11111111,33333333,11111111,"
718 "33333333,11111111,33333333,11111111,"
719 "33333333,11111111,33333333,11111111,"
720 "33333333,11111111,33333333,11111111,"
721 "33333333,11111111,33333333,11111111,"
722 "33333333,11111111,33333333,11111111,"
723 "33333333,11111111,33333333,11111111,"
724 "33333333,11111111,33333333,11111111,"
725 "33333333,11111111,33333333,11111111,"
726 "33333333,11111111,33333333,11111111,"
727 "33333333,11111111,33333333,11111111,"
728 "33333333,11111111,33333333,11111111,"
729 "33333333,11111111,33333333,11111111,"
730 "33333333,11111111,33333333,11111111,"
731 "33333333,11111111,33333333,11111111,"
732 "33333333,11111111,33333333,11111111,"
733 "33333333,11111111,33333333,11111111,"
734 "33333333,11111111,33333333,11111111,"
735 "33333333,11111111,33333333,11111111\n";
736
737static const char large_list[] __initconst =
738 "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"
739 "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"
740 "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"
741 "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"
742 "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"
743 "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"
744 "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"
745 "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"
746 "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"
747 "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"
748 "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"
749 "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"
750 "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-"
751 "1001,1004-1005,1008-1009,1012-1013,1016-1017,1020-1021,1024,1028,1032,1036,1040,1044,1048,1052,1056-1057,1060-10"
752 "61,1064-1065,1068-1069,1072-1073,1076-1077,1080-1081,1084-1085,1088,1092,1096,1100,1104,1108,1112,1116,1120-1121"
753 ",1124-1125,1128-1129,1132-1133,1136-1137,1140-1141,1144-1145,1148-1149,1152,1156,1160,1164,1168,1172,1176,1180,1"
754 "184-1185,1188-1189,1192-1193,1196-1197,1200-1201,1204-1205,1208-1209,1212-1213,1216,1220,1224,1228,1232,1236,124"
755 "0,1244,1248-1249,1252-1253,1256-1257,1260-1261,1264-1265,1268-1269,1272-1273,1276-1277,1280,1284,1288,1292,1296,"
756 "1300,1304,1308,1312-1313,1316-1317,1320-1321,1324-1325,1328-1329,1332-1333,1336-1337,1340-1341,1344,1348,1352,13"
757 "56,1360,1364,1368,1372,1376-1377,1380-1381,1384-1385,1388-1389,1392-1393,1396-1397,1400-1401,1404-1405,1408,1412"
758 ",1416,1420,1424,1428,1432,1436,1440-1441,1444-1445,1448-1449,1452-1453,1456-1457,1460-1461,1464-1465,1468-1469,1"
759 "472,1476,1480,1484,1488,1492,1496,1500,1504-1505,1508-1509,1512-1513,1516-1517,1520-1521,1524-1525,1528-1529,153"
760 "2-1533,1536,1540,1544,1548,1552,1556,1560,1564,1568-1569,1572-1573,1576-1577,1580-1581,1584-1585,1588-1589,1592-"
761 "1593,1596-1597,1600,1604,1608,1612,1616,1620,1624,1628,1632-1633,1636-1637,1640-1641,1644-1645,1648-1649,1652-16"
762 "53,1656-1657,1660-1661,1664,1668,1672,1676,1680,1684,1688,1692,1696-1697,1700-1701,1704-1705,1708-1709,1712-1713"
763 ",1716-1717,1720-1721,1724-1725,1728,1732,1736,1740,1744,1748,1752,1756,1760-1761,1764-1765,1768-1769,1772-1773,1"
764 "776-1777,1780-1781,1784-1785,1788-1789,1792,1796,1800,1804,1808,1812,1816,1820,1824-1825,1828-1829,1832-1833,183"
765 "6-1837,1840-1841,1844-1845,1848-1849,1852-1853,1856,1860,1864,1868,1872,1876,1880,1884,1888-1889,1892-1893,1896-"
766 "1897,1900-1901,1904-1905,1908-1909,1912-1913,1916-1917,1920,1924,1928,1932,1936,1940,1944,1948,1952-1953,1956-19"
767 "57,1960-1961,1964-1965,1968-1969,1972-1973,1976-1977,1980-1981,1984,1988,1992,1996,2000,2004,2008,2012,2016-2017"
768 ",2020-2021,2024-2025,2028-2029,2032-2033,2036-2037,2040-2041,2044-2045,2048,2052,2056,2060,2064,2068,2072,2076,2"
769 "080-2081,2084-2085,2088-2089,2092-2093,2096-2097,2100-2101,2104-2105,2108-2109,2112,2116,2120,2124,2128,2132,213"
770 "6,2140,2144-2145,2148-2149,2152-2153,2156-2157,2160-2161,2164-2165,2168-2169,2172-2173,2176,2180,2184,2188,2192,"
771 "2196,2200,2204,2208-2209,2212-2213,2216-2217,2220-2221,2224-2225,2228-2229,2232-2233,2236-2237,2240,2244,2248,22"
772 "52,2256,2260,2264,2268,2272-2273,2276-2277,2280-2281,2284-2285,2288-2289,2292-2293,2296-2297,2300-2301,2304,2308"
773 ",2312,2316,2320,2324,2328,2332,2336-2337,2340-2341,2344-2345,2348-2349,2352-2353,2356-2357,2360-2361,2364-2365,2"
774 "368,2372,2376,2380,2384,2388,2392,2396,2400-2401,2404-2405,2408-2409,2412-2413,2416-2417,2420-2421,2424-2425,242"
775 "8-2429,2432,2436,2440,2444,2448,2452,2456,2460,2464-2465,2468-2469,2472-2473,2476-2477,2480-2481,2484-2485,2488-"
776 "2489,2492-2493,2496,2500,2504,2508,2512,2516,2520,2524,2528-2529,2532-2533,2536-2537,2540-2541,2544-2545,2548-25"
777 "49,2552-2553,2556-2557\n";
778
779static const struct test_bitmap_print test_print[] __initconst = {
780 { small_bitmap, sizeof(small_bitmap) * BITS_PER_BYTE, small_mask, small_list },
781 { large_bitmap, sizeof(large_bitmap) * BITS_PER_BYTE, large_mask, large_list },
782};
783
784static void __init test_bitmap_print_buf(void)
785{
786 int i;
787
788 for (i = 0; i < ARRAY_SIZE(test_print); i++) {
789 const struct test_bitmap_print *t = &test_print[i];
790 int n;
791
792 n = bitmap_print_bitmask_to_buf(print_buf, t->bitmap, t->nbits,
793 0, 2 * PAGE_SIZE);
794 expect_eq_uint(strlen(t->mask) + 1, n);
795 expect_eq_str(t->mask, print_buf, n);
796
797 n = bitmap_print_list_to_buf(print_buf, t->bitmap, t->nbits,
798 0, 2 * PAGE_SIZE);
799 expect_eq_uint(strlen(t->list) + 1, n);
800 expect_eq_str(t->list, print_buf, n);
801
802
803 if (strlen(t->list) > PAGE_SIZE) {
804 n = bitmap_print_list_to_buf(print_buf, t->bitmap, t->nbits,
805 PAGE_SIZE, PAGE_SIZE);
806 expect_eq_uint(strlen(t->list) + 1 - PAGE_SIZE, n);
807 expect_eq_str(t->list + PAGE_SIZE, print_buf, n);
808 }
809 }
810}
811
812static void __init selftest(void)
813{
814 test_zero_clear();
815 test_fill_set();
816 test_copy();
817 test_replace();
818 test_bitmap_arr32();
819 test_bitmap_parse();
820 test_bitmap_parselist();
821 test_mem_optimisations();
822 test_for_each_set_clump8();
823 test_bitmap_cut();
824 test_bitmap_print_buf();
825}
826
827KSTM_MODULE_LOADERS(test_bitmap);
828MODULE_AUTHOR("david decotigny <david.decotigny@googlers.com>");
829MODULE_LICENSE("GPL");
830
