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