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