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