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