Merge tag 'drm-intel-gt-next-2022-06-29' of git://anongit.freedesktop.org/drm/drm...
[linux-2.6-microblaze.git] / lib / test_bitmap.c
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 KSTM_MODULE_GLOBALS();
20
21 static char pbl_buffer[PAGE_SIZE] __initdata;
22 static char print_buf[PAGE_SIZE * 2] __initdata;
23
24 static 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
42 static const unsigned long exp2[] __initconst = {
43         BITMAP_FROM_U64(0x3333333311111111ULL),
44         BITMAP_FROM_U64(0xffffffff77777777ULL),
45 };
46
47 /* Fibonacci sequence */
48 static 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) */
52 static 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) */
56 static const unsigned long exp3_1_0[] __initconst = {
57         BITMAP_FROM_U64(0xff7fffff77575751ULL),
58 };
59
60 static 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
73 static 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
87 static 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
102 static 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;
106 static 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
130 static 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
160 static 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
193 static 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
222 static 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
251 static 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
292 static 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
320 struct 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
328 static 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
413 static 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
449 static 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);
480 out:
481         kfree(buf);
482         kfree(bmap);
483 }
484
485 static 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
492 static 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
498 static 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
525 static 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
562 static 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
588 static 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 < EXP1_IN_BITS - 64)
608                         expect_eq_uint(arr[DIV_ROUND_UP(nbits, 64)], 0xa5a5a5a5);
609         }
610 }
611
612 static void noinline __init test_mem_optimisations(void)
613 {
614         DECLARE_BITMAP(bmap1, 1024);
615         DECLARE_BITMAP(bmap2, 1024);
616         unsigned int start, nbits;
617
618         for (start = 0; start < 1024; start += 8) {
619                 for (nbits = 0; nbits < 1024 - start; nbits += 8) {
620                         memset(bmap1, 0x5a, sizeof(bmap1));
621                         memset(bmap2, 0x5a, sizeof(bmap2));
622
623                         bitmap_set(bmap1, start, nbits);
624                         __bitmap_set(bmap2, start, nbits);
625                         if (!bitmap_equal(bmap1, bmap2, 1024)) {
626                                 printk("set not equal %d %d\n", start, nbits);
627                                 failed_tests++;
628                         }
629                         if (!__bitmap_equal(bmap1, bmap2, 1024)) {
630                                 printk("set not __equal %d %d\n", start, nbits);
631                                 failed_tests++;
632                         }
633
634                         bitmap_clear(bmap1, start, nbits);
635                         __bitmap_clear(bmap2, start, nbits);
636                         if (!bitmap_equal(bmap1, bmap2, 1024)) {
637                                 printk("clear not equal %d %d\n", start, nbits);
638                                 failed_tests++;
639                         }
640                         if (!__bitmap_equal(bmap1, bmap2, 1024)) {
641                                 printk("clear not __equal %d %d\n", start,
642                                                                         nbits);
643                                 failed_tests++;
644                         }
645                 }
646         }
647 }
648
649 static const unsigned char clump_exp[] __initconst = {
650         0x01,   /* 1 bit set */
651         0x02,   /* non-edge 1 bit set */
652         0x00,   /* zero bits set */
653         0x38,   /* 3 bits set across 4-bit boundary */
654         0x38,   /* Repeated clump */
655         0x0F,   /* 4 bits set */
656         0xFF,   /* all bits set */
657         0x05,   /* non-adjacent 2 bits set */
658 };
659
660 static void __init test_for_each_set_clump8(void)
661 {
662 #define CLUMP_EXP_NUMBITS 64
663         DECLARE_BITMAP(bits, CLUMP_EXP_NUMBITS);
664         unsigned int start;
665         unsigned long clump;
666
667         /* set bitmap to test case */
668         bitmap_zero(bits, CLUMP_EXP_NUMBITS);
669         bitmap_set(bits, 0, 1);         /* 0x01 */
670         bitmap_set(bits, 9, 1);         /* 0x02 */
671         bitmap_set(bits, 27, 3);        /* 0x28 */
672         bitmap_set(bits, 35, 3);        /* 0x28 */
673         bitmap_set(bits, 40, 4);        /* 0x0F */
674         bitmap_set(bits, 48, 8);        /* 0xFF */
675         bitmap_set(bits, 56, 1);        /* 0x05 - part 1 */
676         bitmap_set(bits, 58, 1);        /* 0x05 - part 2 */
677
678         for_each_set_clump8(start, clump, bits, CLUMP_EXP_NUMBITS)
679                 expect_eq_clump8(start, CLUMP_EXP_NUMBITS, clump_exp, &clump);
680 }
681
682 struct test_bitmap_cut {
683         unsigned int first;
684         unsigned int cut;
685         unsigned int nbits;
686         unsigned long in[4];
687         unsigned long expected[4];
688 };
689
690 static struct test_bitmap_cut test_cut[] = {
691         {  0,  0,  8, { 0x0000000aUL, }, { 0x0000000aUL, }, },
692         {  0,  0, 32, { 0xdadadeadUL, }, { 0xdadadeadUL, }, },
693         {  0,  3,  8, { 0x000000aaUL, }, { 0x00000015UL, }, },
694         {  3,  3,  8, { 0x000000aaUL, }, { 0x00000012UL, }, },
695         {  0,  1, 32, { 0xa5a5a5a5UL, }, { 0x52d2d2d2UL, }, },
696         {  0,  8, 32, { 0xdeadc0deUL, }, { 0x00deadc0UL, }, },
697         {  1,  1, 32, { 0x5a5a5a5aUL, }, { 0x2d2d2d2cUL, }, },
698         {  0, 15, 32, { 0xa5a5a5a5UL, }, { 0x00014b4bUL, }, },
699         {  0, 16, 32, { 0xa5a5a5a5UL, }, { 0x0000a5a5UL, }, },
700         { 15, 15, 32, { 0xa5a5a5a5UL, }, { 0x000125a5UL, }, },
701         { 15, 16, 32, { 0xa5a5a5a5UL, }, { 0x0000a5a5UL, }, },
702         { 16, 15, 32, { 0xa5a5a5a5UL, }, { 0x0001a5a5UL, }, },
703
704         { BITS_PER_LONG, BITS_PER_LONG, BITS_PER_LONG,
705                 { 0xa5a5a5a5UL, 0xa5a5a5a5UL, },
706                 { 0xa5a5a5a5UL, 0xa5a5a5a5UL, },
707         },
708         { 1, BITS_PER_LONG - 1, BITS_PER_LONG,
709                 { 0xa5a5a5a5UL, 0xa5a5a5a5UL, },
710                 { 0x00000001UL, 0x00000001UL, },
711         },
712
713         { 0, BITS_PER_LONG * 2, BITS_PER_LONG * 2 + 1,
714                 { 0xa5a5a5a5UL, 0x00000001UL, 0x00000001UL, 0x00000001UL },
715                 { 0x00000001UL, },
716         },
717         { 16, BITS_PER_LONG * 2 + 1, BITS_PER_LONG * 2 + 1 + 16,
718                 { 0x0000ffffUL, 0x5a5a5a5aUL, 0x5a5a5a5aUL, 0x5a5a5a5aUL },
719                 { 0x2d2dffffUL, },
720         },
721 };
722
723 static void __init test_bitmap_cut(void)
724 {
725         unsigned long b[5], *in = &b[1], *out = &b[0];  /* Partial overlap */
726         int i;
727
728         for (i = 0; i < ARRAY_SIZE(test_cut); i++) {
729                 struct test_bitmap_cut *t = &test_cut[i];
730
731                 memcpy(in, t->in, sizeof(t->in));
732
733                 bitmap_cut(out, in, t->first, t->cut, t->nbits);
734
735                 expect_eq_bitmap(t->expected, out, t->nbits);
736         }
737 }
738
739 struct test_bitmap_print {
740         const unsigned long *bitmap;
741         unsigned long nbits;
742         const char *mask;
743         const char *list;
744 };
745
746 static const unsigned long small_bitmap[] __initconst = {
747         BITMAP_FROM_U64(0x3333333311111111ULL),
748 };
749
750 static const char small_mask[] __initconst = "33333333,11111111\n";
751 static const char small_list[] __initconst = "0,4,8,12,16,20,24,28,32-33,36-37,40-41,44-45,48-49,52-53,56-57,60-61\n";
752
753 static const unsigned long large_bitmap[] __initconst = {
754         BITMAP_FROM_U64(0x3333333311111111ULL), BITMAP_FROM_U64(0x3333333311111111ULL),
755         BITMAP_FROM_U64(0x3333333311111111ULL), BITMAP_FROM_U64(0x3333333311111111ULL),
756         BITMAP_FROM_U64(0x3333333311111111ULL), BITMAP_FROM_U64(0x3333333311111111ULL),
757         BITMAP_FROM_U64(0x3333333311111111ULL), BITMAP_FROM_U64(0x3333333311111111ULL),
758         BITMAP_FROM_U64(0x3333333311111111ULL), BITMAP_FROM_U64(0x3333333311111111ULL),
759         BITMAP_FROM_U64(0x3333333311111111ULL), BITMAP_FROM_U64(0x3333333311111111ULL),
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 };
775
776 static const char large_mask[] __initconst = "33333333,11111111,33333333,11111111,"
777                                         "33333333,11111111,33333333,11111111,"
778                                         "33333333,11111111,33333333,11111111,"
779                                         "33333333,11111111,33333333,11111111,"
780                                         "33333333,11111111,33333333,11111111,"
781                                         "33333333,11111111,33333333,11111111,"
782                                         "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\n";
796
797 static const char large_list[] __initconst = /* more than 4KB */
798         "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"
799         "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"
800         "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"
801         "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"
802         "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"
803         "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"
804         "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"
805         "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"
806         "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"
807         "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"
808         "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"
809         "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"
810         "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-"
811         "1001,1004-1005,1008-1009,1012-1013,1016-1017,1020-1021,1024,1028,1032,1036,1040,1044,1048,1052,1056-1057,1060-10"
812         "61,1064-1065,1068-1069,1072-1073,1076-1077,1080-1081,1084-1085,1088,1092,1096,1100,1104,1108,1112,1116,1120-1121"
813         ",1124-1125,1128-1129,1132-1133,1136-1137,1140-1141,1144-1145,1148-1149,1152,1156,1160,1164,1168,1172,1176,1180,1"
814         "184-1185,1188-1189,1192-1193,1196-1197,1200-1201,1204-1205,1208-1209,1212-1213,1216,1220,1224,1228,1232,1236,124"
815         "0,1244,1248-1249,1252-1253,1256-1257,1260-1261,1264-1265,1268-1269,1272-1273,1276-1277,1280,1284,1288,1292,1296,"
816         "1300,1304,1308,1312-1313,1316-1317,1320-1321,1324-1325,1328-1329,1332-1333,1336-1337,1340-1341,1344,1348,1352,13"
817         "56,1360,1364,1368,1372,1376-1377,1380-1381,1384-1385,1388-1389,1392-1393,1396-1397,1400-1401,1404-1405,1408,1412"
818         ",1416,1420,1424,1428,1432,1436,1440-1441,1444-1445,1448-1449,1452-1453,1456-1457,1460-1461,1464-1465,1468-1469,1"
819         "472,1476,1480,1484,1488,1492,1496,1500,1504-1505,1508-1509,1512-1513,1516-1517,1520-1521,1524-1525,1528-1529,153"
820         "2-1533,1536,1540,1544,1548,1552,1556,1560,1564,1568-1569,1572-1573,1576-1577,1580-1581,1584-1585,1588-1589,1592-"
821         "1593,1596-1597,1600,1604,1608,1612,1616,1620,1624,1628,1632-1633,1636-1637,1640-1641,1644-1645,1648-1649,1652-16"
822         "53,1656-1657,1660-1661,1664,1668,1672,1676,1680,1684,1688,1692,1696-1697,1700-1701,1704-1705,1708-1709,1712-1713"
823         ",1716-1717,1720-1721,1724-1725,1728,1732,1736,1740,1744,1748,1752,1756,1760-1761,1764-1765,1768-1769,1772-1773,1"
824         "776-1777,1780-1781,1784-1785,1788-1789,1792,1796,1800,1804,1808,1812,1816,1820,1824-1825,1828-1829,1832-1833,183"
825         "6-1837,1840-1841,1844-1845,1848-1849,1852-1853,1856,1860,1864,1868,1872,1876,1880,1884,1888-1889,1892-1893,1896-"
826         "1897,1900-1901,1904-1905,1908-1909,1912-1913,1916-1917,1920,1924,1928,1932,1936,1940,1944,1948,1952-1953,1956-19"
827         "57,1960-1961,1964-1965,1968-1969,1972-1973,1976-1977,1980-1981,1984,1988,1992,1996,2000,2004,2008,2012,2016-2017"
828         ",2020-2021,2024-2025,2028-2029,2032-2033,2036-2037,2040-2041,2044-2045,2048,2052,2056,2060,2064,2068,2072,2076,2"
829         "080-2081,2084-2085,2088-2089,2092-2093,2096-2097,2100-2101,2104-2105,2108-2109,2112,2116,2120,2124,2128,2132,213"
830         "6,2140,2144-2145,2148-2149,2152-2153,2156-2157,2160-2161,2164-2165,2168-2169,2172-2173,2176,2180,2184,2188,2192,"
831         "2196,2200,2204,2208-2209,2212-2213,2216-2217,2220-2221,2224-2225,2228-2229,2232-2233,2236-2237,2240,2244,2248,22"
832         "52,2256,2260,2264,2268,2272-2273,2276-2277,2280-2281,2284-2285,2288-2289,2292-2293,2296-2297,2300-2301,2304,2308"
833         ",2312,2316,2320,2324,2328,2332,2336-2337,2340-2341,2344-2345,2348-2349,2352-2353,2356-2357,2360-2361,2364-2365,2"
834         "368,2372,2376,2380,2384,2388,2392,2396,2400-2401,2404-2405,2408-2409,2412-2413,2416-2417,2420-2421,2424-2425,242"
835         "8-2429,2432,2436,2440,2444,2448,2452,2456,2460,2464-2465,2468-2469,2472-2473,2476-2477,2480-2481,2484-2485,2488-"
836         "2489,2492-2493,2496,2500,2504,2508,2512,2516,2520,2524,2528-2529,2532-2533,2536-2537,2540-2541,2544-2545,2548-25"
837         "49,2552-2553,2556-2557\n";
838
839 static const struct test_bitmap_print test_print[] __initconst = {
840         { small_bitmap, sizeof(small_bitmap) * BITS_PER_BYTE, small_mask, small_list },
841         { large_bitmap, sizeof(large_bitmap) * BITS_PER_BYTE, large_mask, large_list },
842 };
843
844 static void __init test_bitmap_print_buf(void)
845 {
846         int i;
847
848         for (i = 0; i < ARRAY_SIZE(test_print); i++) {
849                 const struct test_bitmap_print *t = &test_print[i];
850                 int n;
851
852                 n = bitmap_print_bitmask_to_buf(print_buf, t->bitmap, t->nbits,
853                                                 0, 2 * PAGE_SIZE);
854                 expect_eq_uint(strlen(t->mask) + 1, n);
855                 expect_eq_str(t->mask, print_buf, n);
856
857                 n = bitmap_print_list_to_buf(print_buf, t->bitmap, t->nbits,
858                                              0, 2 * PAGE_SIZE);
859                 expect_eq_uint(strlen(t->list) + 1, n);
860                 expect_eq_str(t->list, print_buf, n);
861
862                 /* test by non-zero offset */
863                 if (strlen(t->list) > PAGE_SIZE) {
864                         n = bitmap_print_list_to_buf(print_buf, t->bitmap, t->nbits,
865                                                      PAGE_SIZE, PAGE_SIZE);
866                         expect_eq_uint(strlen(t->list) + 1 - PAGE_SIZE, n);
867                         expect_eq_str(t->list + PAGE_SIZE, print_buf, n);
868                 }
869         }
870 }
871
872 static void __init selftest(void)
873 {
874         test_zero_clear();
875         test_fill_set();
876         test_copy();
877         test_replace();
878         test_bitmap_arr32();
879         test_bitmap_arr64();
880         test_bitmap_parse();
881         test_bitmap_parselist();
882         test_bitmap_printlist();
883         test_mem_optimisations();
884         test_for_each_set_clump8();
885         test_bitmap_cut();
886         test_bitmap_print_buf();
887 }
888
889 KSTM_MODULE_LOADERS(test_bitmap);
890 MODULE_AUTHOR("david decotigny <david.decotigny@googlers.com>");
891 MODULE_LICENSE("GPL");