1	// SPDX-License-Identifier: GPL-2.0-only
2	/*
3	* Test cases for bitmap API.
4	*/
5
6	#define pr_fmt(fmt) KBUILD_MODNAME ": " fmt
7
8	#include <linux/bitmap.h>
9	#include <linux/init.h>
10	#include <linux/kernel.h>
11	#include <linux/module.h>
12	#include <linux/printk.h>
13	#include <linux/slab.h>
14	#include <linux/string.h>
15	#include <linux/uaccess.h>
16
17	#include "../tools/testing/selftests/kselftest_module.h"
18
19	#define EXP1_IN_BITS (sizeof(exp1) * 8)
20
21	KSTM_MODULE_GLOBALS();
22
23	static char pbl_buffer[PAGE_SIZE] __initdata;
24	static char print_buf[PAGE_SIZE * 2] __initdata;
25
26	static const unsigned long exp1[] __initconst = {
27	BITMAP_FROM_U64(1),
28	BITMAP_FROM_U64(2),
29	BITMAP_FROM_U64(0x0000ffff),
30	BITMAP_FROM_U64(0xffff0000),
31	BITMAP_FROM_U64(0x55555555),
32	BITMAP_FROM_U64(0xaaaaaaaa),
33	BITMAP_FROM_U64(0x11111111),
34	BITMAP_FROM_U64(0x22222222),
35	BITMAP_FROM_U64(0xffffffff),
36	BITMAP_FROM_U64(0xfffffffe),
37	BITMAP_FROM_U64(0x3333333311111111ULL),
38	BITMAP_FROM_U64(0xffffffff77777777ULL),
39	BITMAP_FROM_U64(0),
40	BITMAP_FROM_U64(0x00008000),
41	BITMAP_FROM_U64(0x80000000),
42	};
43
44	static const unsigned long exp2[] __initconst = {
45	BITMAP_FROM_U64(0x3333333311111111ULL),
46	BITMAP_FROM_U64(0xffffffff77777777ULL),
47	};
48
49	/* Fibonacci sequence */
50	static const unsigned long exp2_to_exp3_mask[] __initconst = {
51	BITMAP_FROM_U64(0x008000020020212eULL),
52	};
53	/* exp3_0_1 = (exp2[0] & ~exp2_to_exp3_mask) | (exp2[1] & exp2_to_exp3_mask) */
54	static const unsigned long exp3_0_1[] __initconst = {
55	BITMAP_FROM_U64(0x33b3333311313137ULL),
56	};
57	/* exp3_1_0 = (exp2[1] & ~exp2_to_exp3_mask) | (exp2[0] & exp2_to_exp3_mask) */
58	static const unsigned long exp3_1_0[] __initconst = {
59	BITMAP_FROM_U64(0xff7fffff77575751ULL),
60	};
61
62	static bool __init
63	__check_eq_uint(const char *srcfile, unsigned int line,
64	const unsigned int exp_uint, unsigned int x)
65	{
66	if (exp_uint != x) {
67	pr_err("[%s:%u] expected %u, got %u\n",
68	srcfile, line, exp_uint, x);
69	return false;
70	}
71	return true;
72	}
73
74
75	static bool __init
76	__check_eq_bitmap(const char *srcfile, unsigned int line,
77	const unsigned long *exp_bmap, const unsigned long *bmap,
78	unsigned int nbits)
79	{
80	if (!bitmap_equal(src1: exp_bmap, src2: bmap, nbits)) {
81	pr_warn("[%s:%u] bitmaps contents differ: expected \"%*pbl\", got \"%*pbl\"\n",
82	srcfile, line,
83	nbits, exp_bmap, nbits, bmap);
84	return false;
85	}
86	return true;
87	}
88
89	static bool __init
90	__check_eq_pbl(const char *srcfile, unsigned int line,
91	const char *expected_pbl,
92	const unsigned long *bitmap, unsigned int nbits)
93	{
94	snprintf(buf: pbl_buffer, size: sizeof(pbl_buffer), fmt: "%*pbl", nbits, bitmap);
95	if (strcmp(expected_pbl, pbl_buffer)) {
96	pr_warn("[%s:%u] expected \"%s\", got \"%s\"\n",
97	srcfile, line,
98	expected_pbl, pbl_buffer);
99	return false;
100	}
101	return true;
102	}
103
104	static bool __init
105	__check_eq_u32_array(const char *srcfile, unsigned int line,
106	const u32 *exp_arr, unsigned int exp_len,
107	const u32 *arr, unsigned int len) __used;
108	static bool __init
109	__check_eq_u32_array(const char *srcfile, unsigned int line,
110	const u32 *exp_arr, unsigned int exp_len,
111	const u32 *arr, unsigned int len)
112	{
113	if (exp_len != len) {
114	pr_warn("[%s:%u] array length differ: expected %u, got %u\n",
115	srcfile, line,
116	exp_len, len);
117	return false;
118	}
119
120	if (memcmp(p: exp_arr, q: arr, size: len*sizeof(*arr))) {
121	pr_warn("[%s:%u] array contents differ\n", srcfile, line);
122	print_hex_dump(KERN_WARNING, prefix_str: " exp: ", prefix_type: DUMP_PREFIX_OFFSET,
123	rowsize: 32, groupsize: 4, buf: exp_arr, len: exp_len*sizeof(*exp_arr), ascii: false);
124	print_hex_dump(KERN_WARNING, prefix_str: " got: ", prefix_type: DUMP_PREFIX_OFFSET,
125	rowsize: 32, groupsize: 4, buf: arr, len: len*sizeof(*arr), ascii: false);
126	return false;
127	}
128
129	return true;
130	}
131
132	static bool __init __check_eq_clump8(const char *srcfile, unsigned int line,
133	const unsigned int offset,
134	const unsigned int size,
135	const unsigned char *const clump_exp,
136	const unsigned long *const clump)
137	{
138	unsigned long exp;
139
140	if (offset >= size) {
141	pr_warn("[%s:%u] bit offset for clump out-of-bounds: expected less than %u, got %u\n",
142	srcfile, line, size, offset);
143	return false;
144	}
145
146	exp = clump_exp[offset / 8];
147	if (!exp) {
148	pr_warn("[%s:%u] bit offset for zero clump: expected nonzero clump, got bit offset %u with clump value 0",
149	srcfile, line, offset);
150	return false;
151	}
152
153	if (*clump != exp) {
154	pr_warn("[%s:%u] expected clump value of 0x%lX, got clump value of 0x%lX",
155	srcfile, line, exp, *clump);
156	return false;
157	}
158
159	return true;
160	}
161
162	static bool __init
163	__check_eq_str(const char *srcfile, unsigned int line,
164	const char *exp_str, const char *str,
165	unsigned int len)
166	{
167	bool eq;
168
169	eq = strncmp(exp_str, str, len) == 0;
170	if (!eq)
171	pr_err("[%s:%u] expected %s, got %s\n", srcfile, line, exp_str, str);
172
173	return eq;
174	}
175
176	#define __expect_eq(suffix, ...) \
177	({ \
178	int result = 0; \
179	total_tests++; \
180	if (!__check_eq_ ## suffix(__FILE__, __LINE__, \
181	##__VA_ARGS__)) { \
182	failed_tests++; \
183	result = 1; \
184	} \
185	result; \
186	})
187
188	#define expect_eq_uint(...) __expect_eq(uint, ##__VA_ARGS__)
189	#define expect_eq_bitmap(...) __expect_eq(bitmap, ##__VA_ARGS__)
190	#define expect_eq_pbl(...) __expect_eq(pbl, ##__VA_ARGS__)
191	#define expect_eq_u32_array(...) __expect_eq(u32_array, ##__VA_ARGS__)
192	#define expect_eq_clump8(...) __expect_eq(clump8, ##__VA_ARGS__)
193	#define expect_eq_str(...) __expect_eq(str, ##__VA_ARGS__)
194
195	static void __init test_zero_clear(void)
196	{
197	DECLARE_BITMAP(bmap, 1024);
198
199	/* Known way to set all bits */
200	memset(bmap, 0xff, 128);
201
202	expect_eq_pbl("0-22", bmap, 23);
203	expect_eq_pbl("0-1023", bmap, 1024);
204
205	/* single-word bitmaps */
206	bitmap_clear(map: bmap, start: 0, nbits: 9);
207	expect_eq_pbl("9-1023", bmap, 1024);
208
209	bitmap_zero(dst: bmap, nbits: 35);
210	expect_eq_pbl("64-1023", bmap, 1024);
211
212	/* cross boundaries operations */
213	bitmap_clear(map: bmap, start: 79, nbits: 19);
214	expect_eq_pbl("64-78,98-1023", bmap, 1024);
215
216	bitmap_zero(dst: bmap, nbits: 115);
217	expect_eq_pbl("128-1023", bmap, 1024);
218
219	/* Zeroing entire area */
220	bitmap_zero(dst: bmap, nbits: 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(dst: bmap, nbits: 64 * 3);
230	__set_bit(10, bmap);
231	__set_bit(20, bmap);
232	__set_bit(30, bmap);
233	__set_bit(40, bmap);
234	__set_bit(50, bmap);
235	__set_bit(60, bmap);
236	__set_bit(80, bmap);
237	__set_bit(123, bmap);
238
239	expect_eq_uint(10, find_nth_bit(bmap, 64 * 3, 0));
240	expect_eq_uint(20, find_nth_bit(bmap, 64 * 3, 1));
241	expect_eq_uint(30, find_nth_bit(bmap, 64 * 3, 2));
242	expect_eq_uint(40, find_nth_bit(bmap, 64 * 3, 3));
243	expect_eq_uint(50, find_nth_bit(bmap, 64 * 3, 4));
244	expect_eq_uint(60, find_nth_bit(bmap, 64 * 3, 5));
245	expect_eq_uint(80, find_nth_bit(bmap, 64 * 3, 6));
246	expect_eq_uint(123, find_nth_bit(bmap, 64 * 3, 7));
247	expect_eq_uint(64 * 3, find_nth_bit(bmap, 64 * 3, 8));
248
249	expect_eq_uint(10, find_nth_bit(bmap, 64 * 3 - 1, 0));
250	expect_eq_uint(20, find_nth_bit(bmap, 64 * 3 - 1, 1));
251	expect_eq_uint(30, find_nth_bit(bmap, 64 * 3 - 1, 2));
252	expect_eq_uint(40, find_nth_bit(bmap, 64 * 3 - 1, 3));
253	expect_eq_uint(50, find_nth_bit(bmap, 64 * 3 - 1, 4));
254	expect_eq_uint(60, find_nth_bit(bmap, 64 * 3 - 1, 5));
255	expect_eq_uint(80, find_nth_bit(bmap, 64 * 3 - 1, 6));
256	expect_eq_uint(123, find_nth_bit(bmap, 64 * 3 - 1, 7));
257	expect_eq_uint(64 * 3 - 1, find_nth_bit(bmap, 64 * 3 - 1, 8));
258
259	for_each_set_bit(bit, exp1, EXP1_IN_BITS) {
260	b = find_nth_bit(addr: exp1, EXP1_IN_BITS, n: 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(map: bmap, start: 0, nbits: 9);
277	expect_eq_pbl("0-8", bmap, 1024);
278
279	bitmap_fill(dst: bmap, nbits: 35);
280	expect_eq_pbl("0-63", bmap, 1024);
281
282	/* cross boundaries operations */
283	bitmap_set(map: bmap, start: 79, nbits: 19);
284	expect_eq_pbl("0-63,79-97", bmap, 1024);
285
286	bitmap_fill(dst: bmap, nbits: 115);
287	expect_eq_pbl("0-127", bmap, 1024);
288
289	/* Zeroing entire area */
290	bitmap_fill(dst: bmap, nbits: 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(dst: bmap1, nbits: 1024);
300	bitmap_zero(dst: bmap2, nbits: 1024);
301
302	/* single-word bitmaps */
303	bitmap_set(map: bmap1, start: 0, nbits: 19);
304	bitmap_copy(dst: bmap2, src: bmap1, nbits: 23);
305	expect_eq_pbl("0-18", bmap2, 1024);
306
307	bitmap_set(map: bmap2, start: 0, nbits: 23);
308	bitmap_copy(dst: bmap2, src: bmap1, nbits: 23);
309	expect_eq_pbl("0-18", bmap2, 1024);
310
311	/* multi-word bitmaps */
312	bitmap_set(map: bmap1, start: 0, nbits: 109);
313	bitmap_copy(dst: bmap2, src: bmap1, nbits: 1024);
314	expect_eq_pbl("0-108", bmap2, 1024);
315
316	bitmap_fill(dst: bmap2, nbits: 1024);
317	bitmap_copy(dst: bmap2, src: bmap1, nbits: 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(dst: bmap2, nbits: 1024);
325	bitmap_copy(dst: bmap2, src: bmap1, nbits: 109); /* ... but 0-padded til word length */
326	expect_eq_pbl("0-108,128-1023", bmap2, 1024);
327
328	bitmap_fill(dst: bmap2, nbits: 1024);
329	bitmap_copy(dst: bmap2, src: bmap1, nbits: 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(dst: bmap, nbits: 1000);
340
341	for (order = 0; order < 10; order++) {
342	pos = bitmap_find_free_region(bitmap: bmap, bits: 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(bitmap: bmap, pos: 0, order: 0);
350	for (order = 1; order < 9; order++)
351	bitmap_release_region(bitmap: 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(dst: bmap, nbits: 1024);
367	bitmap_replace(dst: bmap, old: &exp2[0 * nlongs], new: &exp2[1 * nlongs], mask: exp2_to_exp3_mask, nbits);
368	expect_eq_bitmap(bmap, exp3_0_1, nbits);
369
370	bitmap_zero(dst: bmap, nbits: 1024);
371	bitmap_replace(dst: bmap, old: &exp2[1 * nlongs], new: &exp2[0 * nlongs], mask: exp2_to_exp3_mask, nbits);
372	expect_eq_bitmap(bmap, exp3_1_0, nbits);
373
374	bitmap_fill(dst: bmap, nbits: 1024);
375	bitmap_replace(dst: bmap, old: &exp2[0 * nlongs], new: &exp2[1 * nlongs], mask: exp2_to_exp3_mask, nbits);
376	expect_eq_bitmap(bmap, exp3_0_1, nbits);
377
378	bitmap_fill(dst: bmap, nbits: 1024);
379	bitmap_replace(dst: bmap, old: &exp2[1 * nlongs], new: &exp2[0 * nlongs], mask: 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(dst: bmap_gather, nbits: 100);
409	bitmap_gather(dst: bmap_gather, src: sg_src, mask: sg_mask, nbits);
410	expect_eq_bitmap(sg_gather_exp, bmap_gather, nbits);
411
412	/* Simple scatter call */
413	bitmap_zero(dst: bmap_scatter, nbits: 100);
414	bitmap_scatter(dst: bmap_scatter, src: sg_src, mask: sg_mask, nbits);
415	expect_eq_bitmap(sg_scatter_exp, bmap_scatter, nbits);
416
417	/* Scatter/gather relationship */
418	bitmap_zero(dst: bmap_tmp, nbits: 100);
419	bitmap_gather(dst: bmap_tmp, src: bmap_scatter, mask: sg_mask, nbits);
420	bitmap_scatter(dst: bmap_res, src: bmap_tmp, mask: 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, maskp: 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(bitmap1: 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_err("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(buf: expected, size: 256, fmt: "0-%ld", PAGE_SIZE * 8 - 1);
571	if (slen < 0)
572	goto out;
573
574	time = ktime_get();
575	ret = bitmap_print_to_pagebuf(list: true, buf, maskp: 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_err("bitmap_print_to_pagebuf: input is '%s', Time: %llu\n", buf, time);
591	out:
592	kfree(objp: buf);
593	kfree(objp: 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(buf: test.in, buflen: len, dst: bmap, nbits: 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(bitmap1: bmap, bitmap2: test.expected, nbits: 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_err("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(buf: arr, bitmap: exp1, nbits);
683	bitmap_from_arr32(bitmap: bmap2, buf: arr, nbits);
684	expect_eq_bitmap(bmap2, exp1, nbits);
685
686	next_bit = find_next_bit(addr: bmap2,
687	round_up(nbits, BITS_PER_LONG), offset: 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(addr: bmap2, round_up(nbits, BITS_PER_LONG), offset: 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(map: bmap1, start, nbits);
747	__bitmap_set(map: bmap2, start, len: nbits);
748	if (!bitmap_equal(src1: bmap1, src2: bmap2, nbits: 1024)) {
749	printk("set not equal %d %d\n", start, nbits);
750	failed_tests++;
751	}
752	if (!__bitmap_equal(bitmap1: bmap1, bitmap2: bmap2, nbits: 1024)) {
753	printk("set not __equal %d %d\n", start, nbits);
754	failed_tests++;
755	}
756
757	bitmap_clear(map: bmap1, start, nbits);
758	__bitmap_clear(map: bmap2, start, len: nbits);
759	if (!bitmap_equal(src1: bmap1, src2: bmap2, nbits: 1024)) {
760	printk("clear not equal %d %d\n", start, nbits);
761	failed_tests++;
762	}
763	if (!__bitmap_equal(bitmap1: bmap1, bitmap2: bmap2, nbits: 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(dst: bits, CLUMP_EXP_NUMBITS);
792	bitmap_set(map: bits, start: 0, nbits: 1); /* 0x01 */
793	bitmap_set(map: bits, start: 9, nbits: 1); /* 0x02 */
794	bitmap_set(map: bits, start: 27, nbits: 3); /* 0x28 */
795	bitmap_set(map: bits, start: 35, nbits: 3); /* 0x28 */
796	bitmap_set(map: bits, start: 40, nbits: 4); /* 0x0F */
797	bitmap_set(map: bits, start: 48, nbits: 8); /* 0xFF */
798	bitmap_set(map: bits, start: 56, nbits: 1); /* 0x05 - part 1 */
799	bitmap_set(map: bits, start: 58, nbits: 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(dst: orig, nbits: 500);
812
813	/* Set individual bits */
814	for (bit = 0; bit < 500; bit += 10)
815	bitmap_set(map: orig, start: bit, nbits: 1);
816
817	/* Set range of bits */
818	bitmap_set(map: orig, start: 100, nbits: 50);
819
820	for (wr = 0; wr < 500; wr++) {
821	bitmap_zero(dst: copy, nbits: 500);
822
823	for_each_set_bit_wrap(bit, orig, 500, wr)
824	bitmap_set(map: copy, start: bit, nbits: 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(dst: orig, nbits: 500);
837	bitmap_zero(dst: copy, nbits: 500);
838
839	/* Set individual bits */
840	for (bit = 0; bit < 500; bit += 10)
841	bitmap_set(map: orig, start: bit, nbits: 1);
842
843	/* Set range of bits */
844	bitmap_set(map: orig, start: 100, nbits: 50);
845
846	for_each_set_bit(bit, orig, 500)
847	bitmap_set(map: copy, start: bit, nbits: 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(dst: orig, nbits: 500);
859
860	/* Set individual bits */
861	for (bit = 0; bit < 500; bit += 10)
862	bitmap_set(map: orig, start: bit, nbits: 1);
863
864	/* Set range of bits */
865	bitmap_set(map: orig, start: 100, nbits: 50);
866
867	for (wr = 0; wr < 500; wr++) {
868	DECLARE_BITMAP(tmp, 500);
869
870	bitmap_zero(dst: copy, nbits: 500);
871	bit = wr;
872
873	for_each_set_bit_from(bit, orig, 500)
874	bitmap_set(map: copy, start: bit, nbits: 1);
875
876	bitmap_copy(dst: tmp, src: orig, nbits: 500);
877	bitmap_clear(map: tmp, start: 0, nbits: 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(dst: orig, nbits: 500);
889	bitmap_fill(dst: copy, nbits: 500);
890
891	/* Set individual bits */
892	for (bit = 0; bit < 500; bit += 10)
893	bitmap_clear(map: orig, start: bit, nbits: 1);
894
895	/* Set range of bits */
896	bitmap_clear(map: orig, start: 100, nbits: 50);
897
898	for_each_clear_bit(bit, orig, 500)
899	bitmap_clear(map: copy, start: bit, nbits: 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(dst: orig, nbits: 500);
911
912	/* Set individual bits */
913	for (bit = 0; bit < 500; bit += 10)
914	bitmap_clear(map: orig, start: bit, nbits: 1);
915
916	/* Set range of bits */
917	bitmap_clear(map: orig, start: 100, nbits: 50);
918
919	for (wr = 0; wr < 500; wr++) {
920	DECLARE_BITMAP(tmp, 500);
921
922	bitmap_fill(dst: copy, nbits: 500);
923	bit = wr;
924
925	for_each_clear_bit_from(bit, orig, 500)
926	bitmap_clear(map: copy, start: bit, nbits: 1);
927
928	bitmap_copy(dst: tmp, src: orig, nbits: 500);
929	bitmap_set(map: tmp, start: 0, nbits: 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(dst: orig, nbits: 500);
941	bitmap_zero(dst: copy, nbits: 500);
942
943	/* Set individual bits */
944	for (s = 0; s < 500; s += 10)
945	bitmap_set(map: orig, start: s, nbits: 1);
946
947	/* Set range of bits */
948	bitmap_set(map: orig, start: 100, nbits: 50);
949
950	for_each_set_bitrange(s, e, orig, 500)
951	bitmap_set(map: copy, start: s, nbits: 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(dst: orig, nbits: 500);
963	bitmap_fill(dst: copy, nbits: 500);
964
965	/* Set individual bits */
966	for (s = 0; s < 500; s += 10)
967	bitmap_clear(map: orig, start: s, nbits: 1);
968
969	/* Set range of bits */
970	bitmap_clear(map: orig, start: 100, nbits: 50);
971
972	for_each_clear_bitrange(s, e, orig, 500)
973	bitmap_clear(map: copy, start: s, nbits: 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(dst: orig, nbits: 500);
985
986	/* Set individual bits */
987	for (s = 0; s < 500; s += 10)
988	bitmap_set(map: orig, start: s, nbits: 1);
989
990	/* Set range of bits */
991	bitmap_set(map: orig, start: 100, nbits: 50);
992
993	for (wr = 0; wr < 500; wr++) {
994	DECLARE_BITMAP(tmp, 500);
995
996	bitmap_zero(dst: copy, nbits: 500);
997	s = wr;
998
999	for_each_set_bitrange_from(s, e, orig, 500)
1000	bitmap_set(map: copy, start: s, nbits: e - s);
1001
1002	bitmap_copy(dst: tmp, src: orig, nbits: 500);
1003	bitmap_clear(map: tmp, start: 0, nbits: 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(dst: orig, nbits: 500);
1015
1016	/* Set individual bits */
1017	for (s = 0; s < 500; s += 10)
1018	bitmap_clear(map: orig, start: s, nbits: 1);
1019
1020	/* Set range of bits */
1021	bitmap_set(map: orig, start: 100, nbits: 50);
1022
1023	for (wr = 0; wr < 500; wr++) {
1024	DECLARE_BITMAP(tmp, 500);
1025
1026	bitmap_fill(dst: copy, nbits: 500);
1027	s = wr;
1028
1029	for_each_clear_bitrange_from(s, e, orig, 500)
1030	bitmap_clear(map: copy, start: s, nbits: e - s);
1031
1032	bitmap_copy(dst: tmp, src: orig, nbits: 500);
1033	bitmap_set(map: tmp, start: 0, nbits: 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(dst: out, src: in, first: t->first, cut: t->cut, nbits: 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(buf: print_buf, maskp: t->bitmap, nmaskbits: t->nbits,
1209	off: 0, count: 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(buf: print_buf, maskp: t->bitmap, nmaskbits: t->nbits,
1214	off: 0, count: 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(buf: print_buf, maskp: t->bitmap, nmaskbits: 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	/*
1249	* Equals to `unsigned long bitmap[1] = { GENMASK(6, 5), }`.
1250	* Clang on s390 optimizes bitops at compile-time as intended, but at
1251	* the same time stops treating @bitmap and @bitopvar as compile-time
1252	* constants after regular test_bit() is executed, thus triggering the
1253	* build bugs below. So, call const_test_bit() there directly until
1254	* the compiler is fixed.
1255	*/
1256	bitmap_clear(map: bitmap, start: 0, BITS_PER_LONG);
1257	if (!test_bit(7, bitmap))
1258	bitmap_set(map: bitmap, start: 5, nbits: 2);
1259
1260	/* Equals to `unsigned long bitopvar = BIT(20)` */
1261	__change_bit(31, &bitopvar);
1262	bitmap_shift_right(dst: &bitopvar, src: &bitopvar, shift: 11, BITS_PER_LONG);
1263
1264	/* Equals to `unsigned long var = BIT(25)` */
1265	var |= BIT(25);
1266	if (var & BIT(0))
1267	var ^= GENMASK(9, 6);
1268
1269	/* __const_hweight<32|64>(GENMASK(6, 5)) == 2 */
1270	res = bitmap_weight(src: bitmap, nbits: 20);
1271	BUILD_BUG_ON(!__builtin_constant_p(res));
1272	BUILD_BUG_ON(res != 2);
1273
1274	/* !(BIT(31) & BIT(18)) == 1 */
1275	res = !test_bit(18, &bitopvar);
1276	BUILD_BUG_ON(!__builtin_constant_p(res));
1277	BUILD_BUG_ON(!res);
1278
1279	/* BIT(2) & GENMASK(14, 8) == 0 */
1280	res = initvar & GENMASK(14, 8);
1281	BUILD_BUG_ON(!__builtin_constant_p(res));
1282	BUILD_BUG_ON(res);
1283
1284	/* ~BIT(25) */
1285	BUILD_BUG_ON(!__builtin_constant_p(~var));
1286	BUILD_BUG_ON(~var != ~BIT(25));
1287	}
1288
1289	static void __init selftest(void)
1290	{
1291	test_zero_clear();
1292	test_fill_set();
1293	test_copy();
1294	test_bitmap_region();
1295	test_replace();
1296	test_bitmap_sg();
1297	test_bitmap_arr32();
1298	test_bitmap_arr64();
1299	test_bitmap_parse();
1300	test_bitmap_parselist();
1301	test_bitmap_printlist();
1302	test_mem_optimisations();
1303	test_bitmap_cut();
1304	test_bitmap_print_buf();
1305	test_bitmap_const_eval();
1306
1307	test_find_nth_bit();
1308	test_for_each_set_bit();
1309	test_for_each_set_bit_from();
1310	test_for_each_clear_bit();
1311	test_for_each_clear_bit_from();
1312	test_for_each_set_bitrange();
1313	test_for_each_clear_bitrange();
1314	test_for_each_set_bitrange_from();
1315	test_for_each_clear_bitrange_from();
1316	test_for_each_set_clump8();
1317	test_for_each_set_bit_wrap();
1318	}
1319
1320	KSTM_MODULE_LOADERS(test_bitmap);
1321	MODULE_AUTHOR("david decotigny <david.decotigny@googlers.com>");
1322	MODULE_LICENSE("GPL");
1323