Merge tag 'armsoc-fixes' of git://git.kernel.org/pub/scm/linux/kernel/git/arm/arm-soc
[platform/kernel/linux-rpi.git] / lib / test_bitmap.c
1 /*
2  * Test cases for printf facility.
3  */
4
5 #define pr_fmt(fmt) KBUILD_MODNAME ": " fmt
6
7 #include <linux/bitmap.h>
8 #include <linux/init.h>
9 #include <linux/kernel.h>
10 #include <linux/module.h>
11 #include <linux/printk.h>
12 #include <linux/slab.h>
13 #include <linux/string.h>
14
15 static unsigned total_tests __initdata;
16 static unsigned failed_tests __initdata;
17
18 static char pbl_buffer[PAGE_SIZE] __initdata;
19
20
21 static bool __init
22 __check_eq_uint(const char *srcfile, unsigned int line,
23                 const unsigned int exp_uint, unsigned int x)
24 {
25         if (exp_uint != x) {
26                 pr_warn("[%s:%u] expected %u, got %u\n",
27                         srcfile, line, exp_uint, x);
28                 return false;
29         }
30         return true;
31 }
32
33
34 static bool __init
35 __check_eq_bitmap(const char *srcfile, unsigned int line,
36                   const unsigned long *exp_bmap, unsigned int exp_nbits,
37                   const unsigned long *bmap, unsigned int nbits)
38 {
39         if (exp_nbits != nbits) {
40                 pr_warn("[%s:%u] bitmap length mismatch: expected %u, got %u\n",
41                         srcfile, line, exp_nbits, nbits);
42                 return false;
43         }
44
45         if (!bitmap_equal(exp_bmap, bmap, nbits)) {
46                 pr_warn("[%s:%u] bitmaps contents differ: expected \"%*pbl\", got \"%*pbl\"\n",
47                         srcfile, line,
48                         exp_nbits, exp_bmap, nbits, bmap);
49                 return false;
50         }
51         return true;
52 }
53
54 static bool __init
55 __check_eq_pbl(const char *srcfile, unsigned int line,
56                const char *expected_pbl,
57                const unsigned long *bitmap, unsigned int nbits)
58 {
59         snprintf(pbl_buffer, sizeof(pbl_buffer), "%*pbl", nbits, bitmap);
60         if (strcmp(expected_pbl, pbl_buffer)) {
61                 pr_warn("[%s:%u] expected \"%s\", got \"%s\"\n",
62                         srcfile, line,
63                         expected_pbl, pbl_buffer);
64                 return false;
65         }
66         return true;
67 }
68
69 static bool __init
70 __check_eq_u32_array(const char *srcfile, unsigned int line,
71                      const u32 *exp_arr, unsigned int exp_len,
72                      const u32 *arr, unsigned int len)
73 {
74         if (exp_len != len) {
75                 pr_warn("[%s:%u] array length differ: expected %u, got %u\n",
76                         srcfile, line,
77                         exp_len, len);
78                 return false;
79         }
80
81         if (memcmp(exp_arr, arr, len*sizeof(*arr))) {
82                 pr_warn("[%s:%u] array contents differ\n", srcfile, line);
83                 print_hex_dump(KERN_WARNING, "  exp:  ", DUMP_PREFIX_OFFSET,
84                                32, 4, exp_arr, exp_len*sizeof(*exp_arr), false);
85                 print_hex_dump(KERN_WARNING, "  got:  ", DUMP_PREFIX_OFFSET,
86                                32, 4, arr, len*sizeof(*arr), false);
87                 return false;
88         }
89
90         return true;
91 }
92
93 #define __expect_eq(suffix, ...)                                        \
94         ({                                                              \
95                 int result = 0;                                         \
96                 total_tests++;                                          \
97                 if (!__check_eq_ ## suffix(__FILE__, __LINE__,          \
98                                            ##__VA_ARGS__)) {            \
99                         failed_tests++;                                 \
100                         result = 1;                                     \
101                 }                                                       \
102                 result;                                                 \
103         })
104
105 #define expect_eq_uint(...)             __expect_eq(uint, ##__VA_ARGS__)
106 #define expect_eq_bitmap(...)           __expect_eq(bitmap, ##__VA_ARGS__)
107 #define expect_eq_pbl(...)              __expect_eq(pbl, ##__VA_ARGS__)
108 #define expect_eq_u32_array(...)        __expect_eq(u32_array, ##__VA_ARGS__)
109
110 static void __init test_zero_fill_copy(void)
111 {
112         DECLARE_BITMAP(bmap1, 1024);
113         DECLARE_BITMAP(bmap2, 1024);
114
115         bitmap_zero(bmap1, 1024);
116         bitmap_zero(bmap2, 1024);
117
118         /* single-word bitmaps */
119         expect_eq_pbl("", bmap1, 23);
120
121         bitmap_fill(bmap1, 19);
122         expect_eq_pbl("0-18", bmap1, 1024);
123
124         bitmap_copy(bmap2, bmap1, 23);
125         expect_eq_pbl("0-18", bmap2, 1024);
126
127         bitmap_fill(bmap2, 23);
128         expect_eq_pbl("0-22", bmap2, 1024);
129
130         bitmap_copy(bmap2, bmap1, 23);
131         expect_eq_pbl("0-18", bmap2, 1024);
132
133         bitmap_zero(bmap1, 23);
134         expect_eq_pbl("", bmap1, 1024);
135
136         /* multi-word bitmaps */
137         bitmap_zero(bmap1, 1024);
138         expect_eq_pbl("", bmap1, 1024);
139
140         bitmap_fill(bmap1, 109);
141         expect_eq_pbl("0-108", bmap1, 1024);
142
143         bitmap_copy(bmap2, bmap1, 1024);
144         expect_eq_pbl("0-108", bmap2, 1024);
145
146         bitmap_fill(bmap2, 1024);
147         expect_eq_pbl("0-1023", bmap2, 1024);
148
149         bitmap_copy(bmap2, bmap1, 1024);
150         expect_eq_pbl("0-108", bmap2, 1024);
151
152         /* the following tests assume a 32- or 64-bit arch (even 128b
153          * if we care)
154          */
155
156         bitmap_fill(bmap2, 1024);
157         bitmap_copy(bmap2, bmap1, 109);  /* ... but 0-padded til word length */
158         expect_eq_pbl("0-108,128-1023", bmap2, 1024);
159
160         bitmap_fill(bmap2, 1024);
161         bitmap_copy(bmap2, bmap1, 97);  /* ... but aligned on word length */
162         expect_eq_pbl("0-108,128-1023", bmap2, 1024);
163
164         bitmap_zero(bmap2, 97);  /* ... but 0-padded til word length */
165         expect_eq_pbl("128-1023", bmap2, 1024);
166 }
167
168 #define PARSE_TIME 0x1
169
170 struct test_bitmap_parselist{
171         const int errno;
172         const char *in;
173         const unsigned long *expected;
174         const int nbits;
175         const int flags;
176 };
177
178 static const unsigned long exp[] __initconst = {
179         BITMAP_FROM_U64(1),
180         BITMAP_FROM_U64(2),
181         BITMAP_FROM_U64(0x0000ffff),
182         BITMAP_FROM_U64(0xffff0000),
183         BITMAP_FROM_U64(0x55555555),
184         BITMAP_FROM_U64(0xaaaaaaaa),
185         BITMAP_FROM_U64(0x11111111),
186         BITMAP_FROM_U64(0x22222222),
187         BITMAP_FROM_U64(0xffffffff),
188         BITMAP_FROM_U64(0xfffffffe),
189         BITMAP_FROM_U64(0x3333333311111111ULL),
190         BITMAP_FROM_U64(0xffffffff77777777ULL)
191 };
192
193 static const unsigned long exp2[] __initconst = {
194         BITMAP_FROM_U64(0x3333333311111111ULL),
195         BITMAP_FROM_U64(0xffffffff77777777ULL)
196 };
197
198 static const struct test_bitmap_parselist parselist_tests[] __initconst = {
199 #define step (sizeof(u64) / sizeof(unsigned long))
200
201         {0, "0",                        &exp[0], 8, 0},
202         {0, "1",                        &exp[1 * step], 8, 0},
203         {0, "0-15",                     &exp[2 * step], 32, 0},
204         {0, "16-31",                    &exp[3 * step], 32, 0},
205         {0, "0-31:1/2",                 &exp[4 * step], 32, 0},
206         {0, "1-31:1/2",                 &exp[5 * step], 32, 0},
207         {0, "0-31:1/4",                 &exp[6 * step], 32, 0},
208         {0, "1-31:1/4",                 &exp[7 * step], 32, 0},
209         {0, "0-31:4/4",                 &exp[8 * step], 32, 0},
210         {0, "1-31:4/4",                 &exp[9 * step], 32, 0},
211         {0, "0-31:1/4,32-63:2/4",       &exp[10 * step], 64, 0},
212         {0, "0-31:3/4,32-63:4/4",       &exp[11 * step], 64, 0},
213
214         {0, "0-31:1/4,32-63:2/4,64-95:3/4,96-127:4/4",  exp2, 128, 0},
215
216         {0, "0-2047:128/256", NULL, 2048, PARSE_TIME},
217
218         {-EINVAL, "-1", NULL, 8, 0},
219         {-EINVAL, "-0", NULL, 8, 0},
220         {-EINVAL, "10-1", NULL, 8, 0},
221         {-EINVAL, "0-31:10/1", NULL, 8, 0},
222 };
223
224 static void __init test_bitmap_parselist(void)
225 {
226         int i;
227         int err;
228         cycles_t cycles;
229         DECLARE_BITMAP(bmap, 2048);
230
231         for (i = 0; i < ARRAY_SIZE(parselist_tests); i++) {
232 #define ptest parselist_tests[i]
233
234                 cycles = get_cycles();
235                 err = bitmap_parselist(ptest.in, bmap, ptest.nbits);
236                 cycles = get_cycles() - cycles;
237
238                 if (err != ptest.errno) {
239                         pr_err("test %d: input is %s, errno is %d, expected %d\n",
240                                         i, ptest.in, err, ptest.errno);
241                         continue;
242                 }
243
244                 if (!err && ptest.expected
245                          && !__bitmap_equal(bmap, ptest.expected, ptest.nbits)) {
246                         pr_err("test %d: input is %s, result is 0x%lx, expected 0x%lx\n",
247                                         i, ptest.in, bmap[0], *ptest.expected);
248                         continue;
249                 }
250
251                 if (ptest.flags & PARSE_TIME)
252                         pr_err("test %d: input is '%s' OK, Time: %llu\n",
253                                         i, ptest.in,
254                                         (unsigned long long)cycles);
255         }
256 }
257
258 static void __init test_bitmap_u32_array_conversions(void)
259 {
260         DECLARE_BITMAP(bmap1, 1024);
261         DECLARE_BITMAP(bmap2, 1024);
262         u32 exp_arr[32], arr[32];
263         unsigned nbits;
264
265         for (nbits = 0 ; nbits < 257 ; ++nbits) {
266                 const unsigned int used_u32s = DIV_ROUND_UP(nbits, 32);
267                 unsigned int i, rv;
268
269                 bitmap_zero(bmap1, nbits);
270                 bitmap_set(bmap1, nbits, 1024 - nbits);  /* garbage */
271
272                 memset(arr, 0xff, sizeof(arr));
273                 rv = bitmap_to_u32array(arr, used_u32s, bmap1, nbits);
274                 expect_eq_uint(nbits, rv);
275
276                 memset(exp_arr, 0xff, sizeof(exp_arr));
277                 memset(exp_arr, 0, used_u32s*sizeof(*exp_arr));
278                 expect_eq_u32_array(exp_arr, 32, arr, 32);
279
280                 bitmap_fill(bmap2, 1024);
281                 rv = bitmap_from_u32array(bmap2, nbits, arr, used_u32s);
282                 expect_eq_uint(nbits, rv);
283                 expect_eq_bitmap(bmap1, 1024, bmap2, 1024);
284
285                 for (i = 0 ; i < nbits ; ++i) {
286                         /*
287                          * test conversion bitmap -> u32[]
288                          */
289
290                         bitmap_zero(bmap1, 1024);
291                         __set_bit(i, bmap1);
292                         bitmap_set(bmap1, nbits, 1024 - nbits);  /* garbage */
293
294                         memset(arr, 0xff, sizeof(arr));
295                         rv = bitmap_to_u32array(arr, used_u32s, bmap1, nbits);
296                         expect_eq_uint(nbits, rv);
297
298                         /* 1st used u32 words contain expected bit set, the
299                          * remaining words are left unchanged (0xff)
300                          */
301                         memset(exp_arr, 0xff, sizeof(exp_arr));
302                         memset(exp_arr, 0, used_u32s*sizeof(*exp_arr));
303                         exp_arr[i/32] = (1U<<(i%32));
304                         expect_eq_u32_array(exp_arr, 32, arr, 32);
305
306
307                         /* same, with longer array to fill
308                          */
309                         memset(arr, 0xff, sizeof(arr));
310                         rv = bitmap_to_u32array(arr, 32, bmap1, nbits);
311                         expect_eq_uint(nbits, rv);
312
313                         /* 1st used u32 words contain expected bit set, the
314                          * remaining words are all 0s
315                          */
316                         memset(exp_arr, 0, sizeof(exp_arr));
317                         exp_arr[i/32] = (1U<<(i%32));
318                         expect_eq_u32_array(exp_arr, 32, arr, 32);
319
320                         /*
321                          * test conversion u32[] -> bitmap
322                          */
323
324                         /* the 1st nbits of bmap2 are identical to
325                          * bmap1, the remaining bits of bmap2 are left
326                          * unchanged (all 1s)
327                          */
328                         bitmap_fill(bmap2, 1024);
329                         rv = bitmap_from_u32array(bmap2, nbits,
330                                                   exp_arr, used_u32s);
331                         expect_eq_uint(nbits, rv);
332
333                         expect_eq_bitmap(bmap1, 1024, bmap2, 1024);
334
335                         /* same, with more bits to fill
336                          */
337                         memset(arr, 0xff, sizeof(arr));  /* garbage */
338                         memset(arr, 0, used_u32s*sizeof(u32));
339                         arr[i/32] = (1U<<(i%32));
340
341                         bitmap_fill(bmap2, 1024);
342                         rv = bitmap_from_u32array(bmap2, 1024, arr, used_u32s);
343                         expect_eq_uint(used_u32s*32, rv);
344
345                         /* the 1st nbits of bmap2 are identical to
346                          * bmap1, the remaining bits of bmap2 are cleared
347                          */
348                         bitmap_zero(bmap1, 1024);
349                         __set_bit(i, bmap1);
350                         expect_eq_bitmap(bmap1, 1024, bmap2, 1024);
351
352
353                         /*
354                          * test short conversion bitmap -> u32[] (1
355                          * word too short)
356                          */
357                         if (used_u32s > 1) {
358                                 bitmap_zero(bmap1, 1024);
359                                 __set_bit(i, bmap1);
360                                 bitmap_set(bmap1, nbits,
361                                            1024 - nbits);  /* garbage */
362                                 memset(arr, 0xff, sizeof(arr));
363
364                                 rv = bitmap_to_u32array(arr, used_u32s - 1,
365                                                         bmap1, nbits);
366                                 expect_eq_uint((used_u32s - 1)*32, rv);
367
368                                 /* 1st used u32 words contain expected
369                                  * bit set, the remaining words are
370                                  * left unchanged (0xff)
371                                  */
372                                 memset(exp_arr, 0xff, sizeof(exp_arr));
373                                 memset(exp_arr, 0,
374                                        (used_u32s-1)*sizeof(*exp_arr));
375                                 if ((i/32) < (used_u32s - 1))
376                                         exp_arr[i/32] = (1U<<(i%32));
377                                 expect_eq_u32_array(exp_arr, 32, arr, 32);
378                         }
379
380                         /*
381                          * test short conversion u32[] -> bitmap (3
382                          * bits too short)
383                          */
384                         if (nbits > 3) {
385                                 memset(arr, 0xff, sizeof(arr));  /* garbage */
386                                 memset(arr, 0, used_u32s*sizeof(*arr));
387                                 arr[i/32] = (1U<<(i%32));
388
389                                 bitmap_zero(bmap1, 1024);
390                                 rv = bitmap_from_u32array(bmap1, nbits - 3,
391                                                           arr, used_u32s);
392                                 expect_eq_uint(nbits - 3, rv);
393
394                                 /* we are expecting the bit < nbits -
395                                  * 3 (none otherwise), and the rest of
396                                  * bmap1 unchanged (0-filled)
397                                  */
398                                 bitmap_zero(bmap2, 1024);
399                                 if (i < nbits - 3)
400                                         __set_bit(i, bmap2);
401                                 expect_eq_bitmap(bmap2, 1024, bmap1, 1024);
402
403                                 /* do the same with bmap1 initially
404                                  * 1-filled
405                                  */
406
407                                 bitmap_fill(bmap1, 1024);
408                                 rv = bitmap_from_u32array(bmap1, nbits - 3,
409                                                          arr, used_u32s);
410                                 expect_eq_uint(nbits - 3, rv);
411
412                                 /* we are expecting the bit < nbits -
413                                  * 3 (none otherwise), and the rest of
414                                  * bmap1 unchanged (1-filled)
415                                  */
416                                 bitmap_zero(bmap2, 1024);
417                                 if (i < nbits - 3)
418                                         __set_bit(i, bmap2);
419                                 bitmap_set(bmap2, nbits-3, 1024 - nbits + 3);
420                                 expect_eq_bitmap(bmap2, 1024, bmap1, 1024);
421                         }
422                 }
423         }
424 }
425
426 static void noinline __init test_mem_optimisations(void)
427 {
428         DECLARE_BITMAP(bmap1, 1024);
429         DECLARE_BITMAP(bmap2, 1024);
430         unsigned int start, nbits;
431
432         for (start = 0; start < 1024; start += 8) {
433                 memset(bmap1, 0x5a, sizeof(bmap1));
434                 memset(bmap2, 0x5a, sizeof(bmap2));
435                 for (nbits = 0; nbits < 1024 - start; nbits += 8) {
436                         bitmap_set(bmap1, start, nbits);
437                         __bitmap_set(bmap2, start, nbits);
438                         if (!bitmap_equal(bmap1, bmap2, 1024))
439                                 printk("set not equal %d %d\n", start, nbits);
440                         if (!__bitmap_equal(bmap1, bmap2, 1024))
441                                 printk("set not __equal %d %d\n", start, nbits);
442
443                         bitmap_clear(bmap1, start, nbits);
444                         __bitmap_clear(bmap2, start, nbits);
445                         if (!bitmap_equal(bmap1, bmap2, 1024))
446                                 printk("clear not equal %d %d\n", start, nbits);
447                         if (!__bitmap_equal(bmap1, bmap2, 1024))
448                                 printk("clear not __equal %d %d\n", start,
449                                                                         nbits);
450                 }
451         }
452 }
453
454 static int __init test_bitmap_init(void)
455 {
456         test_zero_fill_copy();
457         test_bitmap_u32_array_conversions();
458         test_bitmap_parselist();
459         test_mem_optimisations();
460
461         if (failed_tests == 0)
462                 pr_info("all %u tests passed\n", total_tests);
463         else
464                 pr_warn("failed %u out of %u tests\n",
465                         failed_tests, total_tests);
466
467         return failed_tests ? -EINVAL : 0;
468 }
469
470 static void __exit test_bitmap_cleanup(void)
471 {
472 }
473
474 module_init(test_bitmap_init);
475 module_exit(test_bitmap_cleanup);
476
477 MODULE_AUTHOR("david decotigny <david.decotigny@googlers.com>");
478 MODULE_LICENSE("GPL");