Linux Audio

Check our new training course

Loading...
v5.14.15
  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
 
 
 19KSTM_MODULE_GLOBALS();
 20
 21static char pbl_buffer[PAGE_SIZE] __initdata;
 
 22
 23static const unsigned long exp1[] __initconst = {
 24	BITMAP_FROM_U64(1),
 25	BITMAP_FROM_U64(2),
 26	BITMAP_FROM_U64(0x0000ffff),
 27	BITMAP_FROM_U64(0xffff0000),
 28	BITMAP_FROM_U64(0x55555555),
 29	BITMAP_FROM_U64(0xaaaaaaaa),
 30	BITMAP_FROM_U64(0x11111111),
 31	BITMAP_FROM_U64(0x22222222),
 32	BITMAP_FROM_U64(0xffffffff),
 33	BITMAP_FROM_U64(0xfffffffe),
 34	BITMAP_FROM_U64(0x3333333311111111ULL),
 35	BITMAP_FROM_U64(0xffffffff77777777ULL),
 36	BITMAP_FROM_U64(0),
 37	BITMAP_FROM_U64(0x00008000),
 38	BITMAP_FROM_U64(0x80000000),
 39};
 40
 41static const unsigned long exp2[] __initconst = {
 42	BITMAP_FROM_U64(0x3333333311111111ULL),
 43	BITMAP_FROM_U64(0xffffffff77777777ULL),
 44};
 45
 46/* Fibonacci sequence */
 47static const unsigned long exp2_to_exp3_mask[] __initconst = {
 48	BITMAP_FROM_U64(0x008000020020212eULL),
 49};
 50/* exp3_0_1 = (exp2[0] & ~exp2_to_exp3_mask) | (exp2[1] & exp2_to_exp3_mask) */
 51static const unsigned long exp3_0_1[] __initconst = {
 52	BITMAP_FROM_U64(0x33b3333311313137ULL),
 53};
 54/* exp3_1_0 = (exp2[1] & ~exp2_to_exp3_mask) | (exp2[0] & exp2_to_exp3_mask) */
 55static const unsigned long exp3_1_0[] __initconst = {
 56	BITMAP_FROM_U64(0xff7fffff77575751ULL),
 57};
 58
 59static bool __init
 60__check_eq_uint(const char *srcfile, unsigned int line,
 61		const unsigned int exp_uint, unsigned int x)
 62{
 63	if (exp_uint != x) {
 64		pr_err("[%s:%u] expected %u, got %u\n",
 65			srcfile, line, exp_uint, x);
 66		return false;
 67	}
 68	return true;
 69}
 70
 71
 72static bool __init
 73__check_eq_bitmap(const char *srcfile, unsigned int line,
 74		  const unsigned long *exp_bmap, const unsigned long *bmap,
 75		  unsigned int nbits)
 76{
 77	if (!bitmap_equal(exp_bmap, bmap, nbits)) {
 78		pr_warn("[%s:%u] bitmaps contents differ: expected \"%*pbl\", got \"%*pbl\"\n",
 79			srcfile, line,
 80			nbits, exp_bmap, nbits, bmap);
 81		return false;
 82	}
 83	return true;
 84}
 85
 86static bool __init
 87__check_eq_pbl(const char *srcfile, unsigned int line,
 88	       const char *expected_pbl,
 89	       const unsigned long *bitmap, unsigned int nbits)
 90{
 91	snprintf(pbl_buffer, sizeof(pbl_buffer), "%*pbl", nbits, bitmap);
 92	if (strcmp(expected_pbl, pbl_buffer)) {
 93		pr_warn("[%s:%u] expected \"%s\", got \"%s\"\n",
 94			srcfile, line,
 95			expected_pbl, pbl_buffer);
 96		return false;
 97	}
 98	return true;
 99}
100
101static bool __init
102__check_eq_u32_array(const char *srcfile, unsigned int line,
103		     const u32 *exp_arr, unsigned int exp_len,
104		     const u32 *arr, unsigned int len) __used;
105static bool __init
106__check_eq_u32_array(const char *srcfile, unsigned int line,
107		     const u32 *exp_arr, unsigned int exp_len,
108		     const u32 *arr, unsigned int len)
109{
110	if (exp_len != len) {
111		pr_warn("[%s:%u] array length differ: expected %u, got %u\n",
112			srcfile, line,
113			exp_len, len);
114		return false;
115	}
116
117	if (memcmp(exp_arr, arr, len*sizeof(*arr))) {
118		pr_warn("[%s:%u] array contents differ\n", srcfile, line);
119		print_hex_dump(KERN_WARNING, "  exp:  ", DUMP_PREFIX_OFFSET,
120			       32, 4, exp_arr, exp_len*sizeof(*exp_arr), false);
121		print_hex_dump(KERN_WARNING, "  got:  ", DUMP_PREFIX_OFFSET,
122			       32, 4, arr, len*sizeof(*arr), false);
123		return false;
124	}
125
126	return true;
127}
128
129static bool __init __check_eq_clump8(const char *srcfile, unsigned int line,
130				    const unsigned int offset,
131				    const unsigned int size,
132				    const unsigned char *const clump_exp,
133				    const unsigned long *const clump)
134{
135	unsigned long exp;
136
137	if (offset >= size) {
138		pr_warn("[%s:%u] bit offset for clump out-of-bounds: expected less than %u, got %u\n",
139			srcfile, line, size, offset);
140		return false;
141	}
142
143	exp = clump_exp[offset / 8];
144	if (!exp) {
145		pr_warn("[%s:%u] bit offset for zero clump: expected nonzero clump, got bit offset %u with clump value 0",
146			srcfile, line, offset);
147		return false;
148	}
149
150	if (*clump != exp) {
151		pr_warn("[%s:%u] expected clump value of 0x%lX, got clump value of 0x%lX",
152			srcfile, line, exp, *clump);
153		return false;
154	}
155
156	return true;
157}
158
 
 
 
 
 
 
 
 
 
 
 
 
 
 
159#define __expect_eq(suffix, ...)					\
160	({								\
161		int result = 0;						\
162		total_tests++;						\
163		if (!__check_eq_ ## suffix(__FILE__, __LINE__,		\
164					   ##__VA_ARGS__)) {		\
165			failed_tests++;					\
166			result = 1;					\
167		}							\
168		result;							\
169	})
170
171#define expect_eq_uint(...)		__expect_eq(uint, ##__VA_ARGS__)
 
172#define expect_eq_bitmap(...)		__expect_eq(bitmap, ##__VA_ARGS__)
173#define expect_eq_pbl(...)		__expect_eq(pbl, ##__VA_ARGS__)
174#define expect_eq_u32_array(...)	__expect_eq(u32_array, ##__VA_ARGS__)
175#define expect_eq_clump8(...)		__expect_eq(clump8, ##__VA_ARGS__)
 
176
177static void __init test_zero_clear(void)
178{
179	DECLARE_BITMAP(bmap, 1024);
180
181	/* Known way to set all bits */
182	memset(bmap, 0xff, 128);
183
184	expect_eq_pbl("0-22", bmap, 23);
185	expect_eq_pbl("0-1023", bmap, 1024);
186
187	/* single-word bitmaps */
188	bitmap_clear(bmap, 0, 9);
189	expect_eq_pbl("9-1023", bmap, 1024);
190
191	bitmap_zero(bmap, 35);
192	expect_eq_pbl("64-1023", bmap, 1024);
193
194	/* cross boundaries operations */
195	bitmap_clear(bmap, 79, 19);
196	expect_eq_pbl("64-78,98-1023", bmap, 1024);
197
198	bitmap_zero(bmap, 115);
199	expect_eq_pbl("128-1023", bmap, 1024);
200
201	/* Zeroing entire area */
202	bitmap_zero(bmap, 1024);
203	expect_eq_pbl("", bmap, 1024);
204}
205
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
206static void __init test_fill_set(void)
207{
208	DECLARE_BITMAP(bmap, 1024);
209
210	/* Known way to clear all bits */
211	memset(bmap, 0x00, 128);
212
213	expect_eq_pbl("", bmap, 23);
214	expect_eq_pbl("", bmap, 1024);
215
216	/* single-word bitmaps */
217	bitmap_set(bmap, 0, 9);
218	expect_eq_pbl("0-8", bmap, 1024);
219
220	bitmap_fill(bmap, 35);
221	expect_eq_pbl("0-63", bmap, 1024);
222
223	/* cross boundaries operations */
224	bitmap_set(bmap, 79, 19);
225	expect_eq_pbl("0-63,79-97", bmap, 1024);
226
227	bitmap_fill(bmap, 115);
228	expect_eq_pbl("0-127", bmap, 1024);
229
230	/* Zeroing entire area */
231	bitmap_fill(bmap, 1024);
232	expect_eq_pbl("0-1023", bmap, 1024);
233}
234
235static void __init test_copy(void)
236{
237	DECLARE_BITMAP(bmap1, 1024);
238	DECLARE_BITMAP(bmap2, 1024);
239
240	bitmap_zero(bmap1, 1024);
241	bitmap_zero(bmap2, 1024);
242
243	/* single-word bitmaps */
244	bitmap_set(bmap1, 0, 19);
245	bitmap_copy(bmap2, bmap1, 23);
246	expect_eq_pbl("0-18", bmap2, 1024);
247
248	bitmap_set(bmap2, 0, 23);
249	bitmap_copy(bmap2, bmap1, 23);
250	expect_eq_pbl("0-18", bmap2, 1024);
251
252	/* multi-word bitmaps */
253	bitmap_set(bmap1, 0, 109);
254	bitmap_copy(bmap2, bmap1, 1024);
255	expect_eq_pbl("0-108", bmap2, 1024);
256
257	bitmap_fill(bmap2, 1024);
258	bitmap_copy(bmap2, bmap1, 1024);
259	expect_eq_pbl("0-108", bmap2, 1024);
260
261	/* the following tests assume a 32- or 64-bit arch (even 128b
262	 * if we care)
263	 */
264
265	bitmap_fill(bmap2, 1024);
266	bitmap_copy(bmap2, bmap1, 109);  /* ... but 0-padded til word length */
267	expect_eq_pbl("0-108,128-1023", bmap2, 1024);
268
269	bitmap_fill(bmap2, 1024);
270	bitmap_copy(bmap2, bmap1, 97);  /* ... but aligned on word length */
271	expect_eq_pbl("0-108,128-1023", bmap2, 1024);
272}
273
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
274#define EXP2_IN_BITS	(sizeof(exp2) * 8)
275
276static void __init test_replace(void)
277{
278	unsigned int nbits = 64;
279	unsigned int nlongs = DIV_ROUND_UP(nbits, BITS_PER_LONG);
280	DECLARE_BITMAP(bmap, 1024);
281
282	BUILD_BUG_ON(EXP2_IN_BITS < nbits * 2);
283
284	bitmap_zero(bmap, 1024);
285	bitmap_replace(bmap, &exp2[0 * nlongs], &exp2[1 * nlongs], exp2_to_exp3_mask, nbits);
286	expect_eq_bitmap(bmap, exp3_0_1, nbits);
287
288	bitmap_zero(bmap, 1024);
289	bitmap_replace(bmap, &exp2[1 * nlongs], &exp2[0 * nlongs], exp2_to_exp3_mask, nbits);
290	expect_eq_bitmap(bmap, exp3_1_0, nbits);
291
292	bitmap_fill(bmap, 1024);
293	bitmap_replace(bmap, &exp2[0 * nlongs], &exp2[1 * nlongs], exp2_to_exp3_mask, nbits);
294	expect_eq_bitmap(bmap, exp3_0_1, nbits);
295
296	bitmap_fill(bmap, 1024);
297	bitmap_replace(bmap, &exp2[1 * nlongs], &exp2[0 * nlongs], exp2_to_exp3_mask, nbits);
298	expect_eq_bitmap(bmap, exp3_1_0, nbits);
299}
300
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
301#define PARSE_TIME	0x1
302#define NO_LEN		0x2
303
304struct test_bitmap_parselist{
305	const int errno;
306	const char *in;
307	const unsigned long *expected;
308	const int nbits;
309	const int flags;
310};
311
312static const struct test_bitmap_parselist parselist_tests[] __initconst = {
313#define step (sizeof(u64) / sizeof(unsigned long))
314
315	{0, "0",			&exp1[0], 8, 0},
316	{0, "1",			&exp1[1 * step], 8, 0},
317	{0, "0-15",			&exp1[2 * step], 32, 0},
318	{0, "16-31",			&exp1[3 * step], 32, 0},
319	{0, "0-31:1/2",			&exp1[4 * step], 32, 0},
320	{0, "1-31:1/2",			&exp1[5 * step], 32, 0},
321	{0, "0-31:1/4",			&exp1[6 * step], 32, 0},
322	{0, "1-31:1/4",			&exp1[7 * step], 32, 0},
323	{0, "0-31:4/4",			&exp1[8 * step], 32, 0},
324	{0, "1-31:4/4",			&exp1[9 * step], 32, 0},
325	{0, "0-31:1/4,32-63:2/4",	&exp1[10 * step], 64, 0},
326	{0, "0-31:3/4,32-63:4/4",	&exp1[11 * step], 64, 0},
327	{0, "  ,,  0-31:3/4  ,, 32-63:4/4  ,,  ",	&exp1[11 * step], 64, 0},
328
329	{0, "0-31:1/4,32-63:2/4,64-95:3/4,96-127:4/4",	exp2, 128, 0},
330
331	{0, "0-2047:128/256", NULL, 2048, PARSE_TIME},
332
333	{0, "",				&exp1[12 * step], 8, 0},
334	{0, "\n",			&exp1[12 * step], 8, 0},
335	{0, ",,  ,,  , ,  ,",		&exp1[12 * step], 8, 0},
336	{0, " ,  ,,  , ,   ",		&exp1[12 * step], 8, 0},
337	{0, " ,  ,,  , ,   \n",		&exp1[12 * step], 8, 0},
338
339	{0, "0-0",			&exp1[0], 32, 0},
340	{0, "1-1",			&exp1[1 * step], 32, 0},
341	{0, "15-15",			&exp1[13 * step], 32, 0},
342	{0, "31-31",			&exp1[14 * step], 32, 0},
343
344	{0, "0-0:0/1",			&exp1[12 * step], 32, 0},
345	{0, "0-0:1/1",			&exp1[0], 32, 0},
346	{0, "0-0:1/31",			&exp1[0], 32, 0},
347	{0, "0-0:31/31",		&exp1[0], 32, 0},
348	{0, "1-1:1/1",			&exp1[1 * step], 32, 0},
349	{0, "0-15:16/31",		&exp1[2 * step], 32, 0},
350	{0, "15-15:1/2",		&exp1[13 * step], 32, 0},
351	{0, "15-15:31/31",		&exp1[13 * step], 32, 0},
352	{0, "15-31:1/31",		&exp1[13 * step], 32, 0},
353	{0, "16-31:16/31",		&exp1[3 * step], 32, 0},
354	{0, "31-31:31/31",		&exp1[14 * step], 32, 0},
355
356	{0, "N-N",			&exp1[14 * step], 32, 0},
357	{0, "0-0:1/N",			&exp1[0], 32, 0},
358	{0, "0-0:N/N",			&exp1[0], 32, 0},
359	{0, "0-15:16/N",		&exp1[2 * step], 32, 0},
360	{0, "15-15:N/N",		&exp1[13 * step], 32, 0},
361	{0, "15-N:1/N",			&exp1[13 * step], 32, 0},
362	{0, "16-N:16/N",		&exp1[3 * step], 32, 0},
363	{0, "N-N:N/N",			&exp1[14 * step], 32, 0},
364
365	{0, "0-N:1/3,1-N:1/3,2-N:1/3",		&exp1[8 * step], 32, 0},
366	{0, "0-31:1/3,1-31:1/3,2-31:1/3",	&exp1[8 * step], 32, 0},
367	{0, "1-10:8/12,8-31:24/29,0-31:0/3",	&exp1[9 * step], 32, 0},
368
369	{0,	  "all",		&exp1[8 * step], 32, 0},
370	{0,	  "0, 1, all,  ",	&exp1[8 * step], 32, 0},
371	{0,	  "all:1/2",		&exp1[4 * step], 32, 0},
372	{0,	  "ALL:1/2",		&exp1[4 * step], 32, 0},
373	{-EINVAL, "al", NULL, 8, 0},
374	{-EINVAL, "alll", NULL, 8, 0},
375
376	{-EINVAL, "-1",	NULL, 8, 0},
377	{-EINVAL, "-0",	NULL, 8, 0},
378	{-EINVAL, "10-1", NULL, 8, 0},
379	{-ERANGE, "8-8", NULL, 8, 0},
380	{-ERANGE, "0-31", NULL, 8, 0},
381	{-EINVAL, "0-31:", NULL, 32, 0},
382	{-EINVAL, "0-31:0", NULL, 32, 0},
383	{-EINVAL, "0-31:0/", NULL, 32, 0},
384	{-EINVAL, "0-31:0/0", NULL, 32, 0},
385	{-EINVAL, "0-31:1/0", NULL, 32, 0},
386	{-EINVAL, "0-31:10/1", NULL, 32, 0},
387	{-EOVERFLOW, "0-98765432123456789:10/1", NULL, 8, 0},
388
389	{-EINVAL, "a-31", NULL, 8, 0},
390	{-EINVAL, "0-a1", NULL, 8, 0},
391	{-EINVAL, "a-31:10/1", NULL, 8, 0},
392	{-EINVAL, "0-31:a/1", NULL, 8, 0},
393	{-EINVAL, "0-\n", NULL, 8, 0},
394
395};
396
397static void __init test_bitmap_parselist(void)
398{
399	int i;
400	int err;
401	ktime_t time;
402	DECLARE_BITMAP(bmap, 2048);
403
404	for (i = 0; i < ARRAY_SIZE(parselist_tests); i++) {
405#define ptest parselist_tests[i]
406
407		time = ktime_get();
408		err = bitmap_parselist(ptest.in, bmap, ptest.nbits);
409		time = ktime_get() - time;
410
411		if (err != ptest.errno) {
412			pr_err("parselist: %d: input is %s, errno is %d, expected %d\n",
413					i, ptest.in, err, ptest.errno);
 
414			continue;
415		}
416
417		if (!err && ptest.expected
418			 && !__bitmap_equal(bmap, ptest.expected, ptest.nbits)) {
419			pr_err("parselist: %d: input is %s, result is 0x%lx, expected 0x%lx\n",
420					i, ptest.in, bmap[0],
421					*ptest.expected);
 
422			continue;
423		}
424
425		if (ptest.flags & PARSE_TIME)
426			pr_err("parselist: %d: input is '%s' OK, Time: %llu\n",
427					i, ptest.in, time);
428
429#undef ptest
430	}
431}
432
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
433static const unsigned long parse_test[] __initconst = {
434	BITMAP_FROM_U64(0),
435	BITMAP_FROM_U64(1),
436	BITMAP_FROM_U64(0xdeadbeef),
437	BITMAP_FROM_U64(0x100000000ULL),
438};
439
440static const unsigned long parse_test2[] __initconst = {
441	BITMAP_FROM_U64(0x100000000ULL), BITMAP_FROM_U64(0xdeadbeef),
442	BITMAP_FROM_U64(0x100000000ULL), BITMAP_FROM_U64(0xbaadf00ddeadbeef),
443	BITMAP_FROM_U64(0x100000000ULL), BITMAP_FROM_U64(0x0badf00ddeadbeef),
444};
445
446static const struct test_bitmap_parselist parse_tests[] __initconst = {
447	{0, "",				&parse_test[0 * step], 32, 0},
448	{0, " ",			&parse_test[0 * step], 32, 0},
449	{0, "0",			&parse_test[0 * step], 32, 0},
450	{0, "0\n",			&parse_test[0 * step], 32, 0},
451	{0, "1",			&parse_test[1 * step], 32, 0},
452	{0, "deadbeef",			&parse_test[2 * step], 32, 0},
453	{0, "1,0",			&parse_test[3 * step], 33, 0},
454	{0, "deadbeef,\n,0,1",		&parse_test[2 * step], 96, 0},
455
456	{0, "deadbeef,1,0",		&parse_test2[0 * 2 * step], 96, 0},
457	{0, "baadf00d,deadbeef,1,0",	&parse_test2[1 * 2 * step], 128, 0},
458	{0, "badf00d,deadbeef,1,0",	&parse_test2[2 * 2 * step], 124, 0},
459	{0, "badf00d,deadbeef,1,0",	&parse_test2[2 * 2 * step], 124, NO_LEN},
460	{0, "  badf00d,deadbeef,1,0  ",	&parse_test2[2 * 2 * step], 124, 0},
461	{0, " , badf00d,deadbeef,1,0 , ",	&parse_test2[2 * 2 * step], 124, 0},
462	{0, " , badf00d, ,, ,,deadbeef,1,0 , ",	&parse_test2[2 * 2 * step], 124, 0},
463
464	{-EINVAL,    "goodfood,deadbeef,1,0",	NULL, 128, 0},
465	{-EOVERFLOW, "3,0",			NULL, 33, 0},
466	{-EOVERFLOW, "123badf00d,deadbeef,1,0",	NULL, 128, 0},
467	{-EOVERFLOW, "badf00d,deadbeef,1,0",	NULL, 90, 0},
468	{-EOVERFLOW, "fbadf00d,deadbeef,1,0",	NULL, 95, 0},
469	{-EOVERFLOW, "badf00d,deadbeef,1,0",	NULL, 100, 0},
470#undef step
471};
472
473static void __init test_bitmap_parse(void)
474{
475	int i;
476	int err;
477	ktime_t time;
478	DECLARE_BITMAP(bmap, 2048);
479
480	for (i = 0; i < ARRAY_SIZE(parse_tests); i++) {
481		struct test_bitmap_parselist test = parse_tests[i];
482		size_t len = test.flags & NO_LEN ? UINT_MAX : strlen(test.in);
483
484		time = ktime_get();
485		err = bitmap_parse(test.in, len, bmap, test.nbits);
486		time = ktime_get() - time;
487
488		if (err != test.errno) {
489			pr_err("parse: %d: input is %s, errno is %d, expected %d\n",
490					i, test.in, err, test.errno);
 
491			continue;
492		}
493
494		if (!err && test.expected
495			 && !__bitmap_equal(bmap, test.expected, test.nbits)) {
496			pr_err("parse: %d: input is %s, result is 0x%lx, expected 0x%lx\n",
497					i, test.in, bmap[0],
498					*test.expected);
 
499			continue;
500		}
501
502		if (test.flags & PARSE_TIME)
503			pr_err("parse: %d: input is '%s' OK, Time: %llu\n",
504					i, test.in, time);
505	}
506}
507
508#define EXP1_IN_BITS	(sizeof(exp1) * 8)
509
510static void __init test_bitmap_arr32(void)
511{
512	unsigned int nbits, next_bit;
513	u32 arr[EXP1_IN_BITS / 32];
514	DECLARE_BITMAP(bmap2, EXP1_IN_BITS);
515
516	memset(arr, 0xa5, sizeof(arr));
517
518	for (nbits = 0; nbits < EXP1_IN_BITS; ++nbits) {
519		bitmap_to_arr32(arr, exp1, nbits);
520		bitmap_from_arr32(bmap2, arr, nbits);
521		expect_eq_bitmap(bmap2, exp1, nbits);
522
523		next_bit = find_next_bit(bmap2,
524				round_up(nbits, BITS_PER_LONG), nbits);
525		if (next_bit < round_up(nbits, BITS_PER_LONG))
526			pr_err("bitmap_copy_arr32(nbits == %d:"
527				" tail is not safely cleared: %d\n",
528				nbits, next_bit);
 
 
529
530		if (nbits < EXP1_IN_BITS - 32)
531			expect_eq_uint(arr[DIV_ROUND_UP(nbits, 32)],
532								0xa5a5a5a5);
533	}
534}
535
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
536static void noinline __init test_mem_optimisations(void)
537{
538	DECLARE_BITMAP(bmap1, 1024);
539	DECLARE_BITMAP(bmap2, 1024);
540	unsigned int start, nbits;
541
542	for (start = 0; start < 1024; start += 8) {
543		for (nbits = 0; nbits < 1024 - start; nbits += 8) {
544			memset(bmap1, 0x5a, sizeof(bmap1));
545			memset(bmap2, 0x5a, sizeof(bmap2));
546
547			bitmap_set(bmap1, start, nbits);
548			__bitmap_set(bmap2, start, nbits);
549			if (!bitmap_equal(bmap1, bmap2, 1024)) {
550				printk("set not equal %d %d\n", start, nbits);
551				failed_tests++;
552			}
553			if (!__bitmap_equal(bmap1, bmap2, 1024)) {
554				printk("set not __equal %d %d\n", start, nbits);
555				failed_tests++;
556			}
557
558			bitmap_clear(bmap1, start, nbits);
559			__bitmap_clear(bmap2, start, nbits);
560			if (!bitmap_equal(bmap1, bmap2, 1024)) {
561				printk("clear not equal %d %d\n", start, nbits);
562				failed_tests++;
563			}
564			if (!__bitmap_equal(bmap1, bmap2, 1024)) {
565				printk("clear not __equal %d %d\n", start,
566									nbits);
567				failed_tests++;
568			}
569		}
570	}
571}
572
573static const unsigned char clump_exp[] __initconst = {
574	0x01,	/* 1 bit set */
575	0x02,	/* non-edge 1 bit set */
576	0x00,	/* zero bits set */
577	0x38,	/* 3 bits set across 4-bit boundary */
578	0x38,	/* Repeated clump */
579	0x0F,	/* 4 bits set */
580	0xFF,	/* all bits set */
581	0x05,	/* non-adjacent 2 bits set */
582};
583
584static void __init test_for_each_set_clump8(void)
585{
586#define CLUMP_EXP_NUMBITS 64
587	DECLARE_BITMAP(bits, CLUMP_EXP_NUMBITS);
588	unsigned int start;
589	unsigned long clump;
590
591	/* set bitmap to test case */
592	bitmap_zero(bits, CLUMP_EXP_NUMBITS);
593	bitmap_set(bits, 0, 1);		/* 0x01 */
594	bitmap_set(bits, 9, 1);		/* 0x02 */
595	bitmap_set(bits, 27, 3);	/* 0x28 */
596	bitmap_set(bits, 35, 3);	/* 0x28 */
597	bitmap_set(bits, 40, 4);	/* 0x0F */
598	bitmap_set(bits, 48, 8);	/* 0xFF */
599	bitmap_set(bits, 56, 1);	/* 0x05 - part 1 */
600	bitmap_set(bits, 58, 1);	/* 0x05 - part 2 */
601
602	for_each_set_clump8(start, clump, bits, CLUMP_EXP_NUMBITS)
603		expect_eq_clump8(start, CLUMP_EXP_NUMBITS, clump_exp, &clump);
604}
605
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
606struct test_bitmap_cut {
607	unsigned int first;
608	unsigned int cut;
609	unsigned int nbits;
610	unsigned long in[4];
611	unsigned long expected[4];
612};
613
614static struct test_bitmap_cut test_cut[] = {
615	{  0,  0,  8, { 0x0000000aUL, }, { 0x0000000aUL, }, },
616	{  0,  0, 32, { 0xdadadeadUL, }, { 0xdadadeadUL, }, },
617	{  0,  3,  8, { 0x000000aaUL, }, { 0x00000015UL, }, },
618	{  3,  3,  8, { 0x000000aaUL, }, { 0x00000012UL, }, },
619	{  0,  1, 32, { 0xa5a5a5a5UL, }, { 0x52d2d2d2UL, }, },
620	{  0,  8, 32, { 0xdeadc0deUL, }, { 0x00deadc0UL, }, },
621	{  1,  1, 32, { 0x5a5a5a5aUL, }, { 0x2d2d2d2cUL, }, },
622	{  0, 15, 32, { 0xa5a5a5a5UL, }, { 0x00014b4bUL, }, },
623	{  0, 16, 32, { 0xa5a5a5a5UL, }, { 0x0000a5a5UL, }, },
624	{ 15, 15, 32, { 0xa5a5a5a5UL, }, { 0x000125a5UL, }, },
625	{ 15, 16, 32, { 0xa5a5a5a5UL, }, { 0x0000a5a5UL, }, },
626	{ 16, 15, 32, { 0xa5a5a5a5UL, }, { 0x0001a5a5UL, }, },
627
628	{ BITS_PER_LONG, BITS_PER_LONG, BITS_PER_LONG,
629		{ 0xa5a5a5a5UL, 0xa5a5a5a5UL, },
630		{ 0xa5a5a5a5UL, 0xa5a5a5a5UL, },
631	},
632	{ 1, BITS_PER_LONG - 1, BITS_PER_LONG,
633		{ 0xa5a5a5a5UL, 0xa5a5a5a5UL, },
634		{ 0x00000001UL, 0x00000001UL, },
635	},
636
637	{ 0, BITS_PER_LONG * 2, BITS_PER_LONG * 2 + 1,
638		{ 0xa5a5a5a5UL, 0x00000001UL, 0x00000001UL, 0x00000001UL },
639		{ 0x00000001UL, },
640	},
641	{ 16, BITS_PER_LONG * 2 + 1, BITS_PER_LONG * 2 + 1 + 16,
642		{ 0x0000ffffUL, 0x5a5a5a5aUL, 0x5a5a5a5aUL, 0x5a5a5a5aUL },
643		{ 0x2d2dffffUL, },
644	},
645};
646
647static void __init test_bitmap_cut(void)
648{
649	unsigned long b[5], *in = &b[1], *out = &b[0];	/* Partial overlap */
650	int i;
651
652	for (i = 0; i < ARRAY_SIZE(test_cut); i++) {
653		struct test_bitmap_cut *t = &test_cut[i];
654
655		memcpy(in, t->in, sizeof(t->in));
656
657		bitmap_cut(out, in, t->first, t->cut, t->nbits);
658
659		expect_eq_bitmap(t->expected, out, t->nbits);
660	}
661}
662
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
663static void __init selftest(void)
664{
665	test_zero_clear();
666	test_fill_set();
667	test_copy();
 
668	test_replace();
 
669	test_bitmap_arr32();
 
670	test_bitmap_parse();
671	test_bitmap_parselist();
 
672	test_mem_optimisations();
673	test_for_each_set_clump8();
674	test_bitmap_cut();
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
675}
676
677KSTM_MODULE_LOADERS(test_bitmap);
678MODULE_AUTHOR("david decotigny <david.decotigny@googlers.com>");
 
679MODULE_LICENSE("GPL");
v6.13.7
   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
  21KSTM_MODULE_GLOBALS();
  22
  23static char pbl_buffer[PAGE_SIZE] __initdata;
  24static char print_buf[PAGE_SIZE * 2] __initdata;
  25
  26static 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
  44static const unsigned long exp2[] __initconst = {
  45	BITMAP_FROM_U64(0x3333333311111111ULL),
  46	BITMAP_FROM_U64(0xffffffff77777777ULL),
  47};
  48
  49/* Fibonacci sequence */
  50static 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) */
  54static 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) */
  58static const unsigned long exp3_1_0[] __initconst = {
  59	BITMAP_FROM_U64(0xff7fffff77575751ULL),
  60};
  61
  62static 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
 
  74static bool __init
  75__check_eq_bitmap(const char *srcfile, unsigned int line,
  76		  const unsigned long *exp_bmap, const unsigned long *bmap,
  77		  unsigned int nbits)
  78{
  79	if (!bitmap_equal(exp_bmap, bmap, nbits)) {
  80		pr_warn("[%s:%u] bitmaps contents differ: expected \"%*pbl\", got \"%*pbl\"\n",
  81			srcfile, line,
  82			nbits, exp_bmap, nbits, bmap);
  83		return false;
  84	}
  85	return true;
  86}
  87
  88static bool __init
  89__check_eq_pbl(const char *srcfile, unsigned int line,
  90	       const char *expected_pbl,
  91	       const unsigned long *bitmap, unsigned int nbits)
  92{
  93	snprintf(pbl_buffer, sizeof(pbl_buffer), "%*pbl", nbits, bitmap);
  94	if (strcmp(expected_pbl, pbl_buffer)) {
  95		pr_warn("[%s:%u] expected \"%s\", got \"%s\"\n",
  96			srcfile, line,
  97			expected_pbl, pbl_buffer);
  98		return false;
  99	}
 100	return true;
 101}
 102
 103static bool __init
 104__check_eq_u32_array(const char *srcfile, unsigned int line,
 105		     const u32 *exp_arr, unsigned int exp_len,
 106		     const u32 *arr, unsigned int len) __used;
 107static bool __init
 108__check_eq_u32_array(const char *srcfile, unsigned int line,
 109		     const u32 *exp_arr, unsigned int exp_len,
 110		     const u32 *arr, unsigned int len)
 111{
 112	if (exp_len != len) {
 113		pr_warn("[%s:%u] array length differ: expected %u, got %u\n",
 114			srcfile, line,
 115			exp_len, len);
 116		return false;
 117	}
 118
 119	if (memcmp(exp_arr, arr, len*sizeof(*arr))) {
 120		pr_warn("[%s:%u] array contents differ\n", srcfile, line);
 121		print_hex_dump(KERN_WARNING, "  exp:  ", DUMP_PREFIX_OFFSET,
 122			       32, 4, exp_arr, exp_len*sizeof(*exp_arr), false);
 123		print_hex_dump(KERN_WARNING, "  got:  ", DUMP_PREFIX_OFFSET,
 124			       32, 4, arr, len*sizeof(*arr), false);
 125		return false;
 126	}
 127
 128	return true;
 129}
 130
 131static bool __init __check_eq_clump8(const char *srcfile, unsigned int line,
 132				    const unsigned int offset,
 133				    const unsigned int size,
 134				    const unsigned char *const clump_exp,
 135				    const unsigned long *const clump)
 136{
 137	unsigned long exp;
 138
 139	if (offset >= size) {
 140		pr_warn("[%s:%u] bit offset for clump out-of-bounds: expected less than %u, got %u\n",
 141			srcfile, line, size, offset);
 142		return false;
 143	}
 144
 145	exp = clump_exp[offset / 8];
 146	if (!exp) {
 147		pr_warn("[%s:%u] bit offset for zero clump: expected nonzero clump, got bit offset %u with clump value 0",
 148			srcfile, line, offset);
 149		return false;
 150	}
 151
 152	if (*clump != exp) {
 153		pr_warn("[%s:%u] expected clump value of 0x%lX, got clump value of 0x%lX",
 154			srcfile, line, exp, *clump);
 155		return false;
 156	}
 157
 158	return true;
 159}
 160
 161static bool __init
 162__check_eq_str(const char *srcfile, unsigned int line,
 163		const char *exp_str, const char *str,
 164		unsigned int len)
 165{
 166	bool eq;
 167
 168	eq = strncmp(exp_str, str, len) == 0;
 169	if (!eq)
 170		pr_err("[%s:%u] expected %s, got %s\n", srcfile, line, exp_str, str);
 171
 172	return eq;
 173}
 174
 175#define __expect_eq(suffix, ...)					\
 176	({								\
 177		int result = 0;						\
 178		total_tests++;						\
 179		if (!__check_eq_ ## suffix(__FILE__, __LINE__,		\
 180					   ##__VA_ARGS__)) {		\
 181			failed_tests++;					\
 182			result = 1;					\
 183		}							\
 184		result;							\
 185	})
 186
 187#define expect_eq_ulong(...)		__expect_eq(ulong, ##__VA_ARGS__)
 188#define expect_eq_uint(x, y)		expect_eq_ulong((unsigned int)(x), (unsigned int)(y))
 189#define expect_eq_bitmap(...)		__expect_eq(bitmap, ##__VA_ARGS__)
 190#define expect_eq_pbl(...)		__expect_eq(pbl, ##__VA_ARGS__)
 191#define expect_eq_u32_array(...)	__expect_eq(u32_array, ##__VA_ARGS__)
 192#define expect_eq_clump8(...)		__expect_eq(clump8, ##__VA_ARGS__)
 193#define expect_eq_str(...)		__expect_eq(str, ##__VA_ARGS__)
 194
 195static void __init test_zero_clear(void)
 196{
 197	DECLARE_BITMAP(bmap, 1024);
 198
 199	/* Known way to set all bits */
 200	memset(bmap, 0xff, 128);
 201
 202	expect_eq_pbl("0-22", bmap, 23);
 203	expect_eq_pbl("0-1023", bmap, 1024);
 204
 205	/* single-word bitmaps */
 206	bitmap_clear(bmap, 0, 9);
 207	expect_eq_pbl("9-1023", bmap, 1024);
 208
 209	bitmap_zero(bmap, 35);
 210	expect_eq_pbl("64-1023", bmap, 1024);
 211
 212	/* cross boundaries operations */
 213	bitmap_clear(bmap, 79, 19);
 214	expect_eq_pbl("64-78,98-1023", bmap, 1024);
 215
 216	bitmap_zero(bmap, 115);
 217	expect_eq_pbl("128-1023", bmap, 1024);
 218
 219	/* Zeroing entire area */
 220	bitmap_zero(bmap, 1024);
 221	expect_eq_pbl("", bmap, 1024);
 222}
 223
 224static void __init test_find_nth_bit(void)
 225{
 226	unsigned long b, bit, cnt = 0;
 227	DECLARE_BITMAP(bmap, 64 * 3);
 228
 229	bitmap_zero(bmap, 64 * 3);
 230	__set_bit(10, bmap);
 231	__set_bit(20, bmap);
 232	__set_bit(30, bmap);
 233	__set_bit(40, bmap);
 234	__set_bit(50, bmap);
 235	__set_bit(60, bmap);
 236	__set_bit(80, bmap);
 237	__set_bit(123, bmap);
 238
 239	expect_eq_uint(10,  find_nth_bit(bmap, 64 * 3, 0));
 240	expect_eq_uint(20,  find_nth_bit(bmap, 64 * 3, 1));
 241	expect_eq_uint(30,  find_nth_bit(bmap, 64 * 3, 2));
 242	expect_eq_uint(40,  find_nth_bit(bmap, 64 * 3, 3));
 243	expect_eq_uint(50,  find_nth_bit(bmap, 64 * 3, 4));
 244	expect_eq_uint(60,  find_nth_bit(bmap, 64 * 3, 5));
 245	expect_eq_uint(80,  find_nth_bit(bmap, 64 * 3, 6));
 246	expect_eq_uint(123, find_nth_bit(bmap, 64 * 3, 7));
 247	expect_eq_uint(0,   !!(find_nth_bit(bmap, 64 * 3, 8) < 64 * 3));
 248
 249	expect_eq_uint(10,  find_nth_bit(bmap, 64 * 3 - 1, 0));
 250	expect_eq_uint(20,  find_nth_bit(bmap, 64 * 3 - 1, 1));
 251	expect_eq_uint(30,  find_nth_bit(bmap, 64 * 3 - 1, 2));
 252	expect_eq_uint(40,  find_nth_bit(bmap, 64 * 3 - 1, 3));
 253	expect_eq_uint(50,  find_nth_bit(bmap, 64 * 3 - 1, 4));
 254	expect_eq_uint(60,  find_nth_bit(bmap, 64 * 3 - 1, 5));
 255	expect_eq_uint(80,  find_nth_bit(bmap, 64 * 3 - 1, 6));
 256	expect_eq_uint(123, find_nth_bit(bmap, 64 * 3 - 1, 7));
 257	expect_eq_uint(0,   !!(find_nth_bit(bmap, 64 * 3 - 1, 8) < 64 * 3 - 1));
 258
 259	for_each_set_bit(bit, exp1, EXP1_IN_BITS) {
 260		b = find_nth_bit(exp1, EXP1_IN_BITS, cnt++);
 261		expect_eq_uint(b, bit);
 262	}
 263}
 264
 265static void __init test_fill_set(void)
 266{
 267	DECLARE_BITMAP(bmap, 1024);
 268
 269	/* Known way to clear all bits */
 270	memset(bmap, 0x00, 128);
 271
 272	expect_eq_pbl("", bmap, 23);
 273	expect_eq_pbl("", bmap, 1024);
 274
 275	/* single-word bitmaps */
 276	bitmap_set(bmap, 0, 9);
 277	expect_eq_pbl("0-8", bmap, 1024);
 278
 279	bitmap_fill(bmap, 35);
 280	expect_eq_pbl("0-63", bmap, 1024);
 281
 282	/* cross boundaries operations */
 283	bitmap_set(bmap, 79, 19);
 284	expect_eq_pbl("0-63,79-97", bmap, 1024);
 285
 286	bitmap_fill(bmap, 115);
 287	expect_eq_pbl("0-127", bmap, 1024);
 288
 289	/* Zeroing entire area */
 290	bitmap_fill(bmap, 1024);
 291	expect_eq_pbl("0-1023", bmap, 1024);
 292}
 293
 294static void __init test_copy(void)
 295{
 296	DECLARE_BITMAP(bmap1, 1024);
 297	DECLARE_BITMAP(bmap2, 1024);
 298
 299	bitmap_zero(bmap1, 1024);
 300	bitmap_zero(bmap2, 1024);
 301
 302	/* single-word bitmaps */
 303	bitmap_set(bmap1, 0, 19);
 304	bitmap_copy(bmap2, bmap1, 23);
 305	expect_eq_pbl("0-18", bmap2, 1024);
 306
 307	bitmap_set(bmap2, 0, 23);
 308	bitmap_copy(bmap2, bmap1, 23);
 309	expect_eq_pbl("0-18", bmap2, 1024);
 310
 311	/* multi-word bitmaps */
 312	bitmap_set(bmap1, 0, 109);
 313	bitmap_copy(bmap2, bmap1, 1024);
 314	expect_eq_pbl("0-108", bmap2, 1024);
 315
 316	bitmap_fill(bmap2, 1024);
 317	bitmap_copy(bmap2, bmap1, 1024);
 318	expect_eq_pbl("0-108", bmap2, 1024);
 319
 320	/* the following tests assume a 32- or 64-bit arch (even 128b
 321	 * if we care)
 322	 */
 323
 324	bitmap_fill(bmap2, 1024);
 325	bitmap_copy(bmap2, bmap1, 109);  /* ... but 0-padded til word length */
 326	expect_eq_pbl("0-108,128-1023", bmap2, 1024);
 327
 328	bitmap_fill(bmap2, 1024);
 329	bitmap_copy(bmap2, bmap1, 97);  /* ... but aligned on word length */
 330	expect_eq_pbl("0-108,128-1023", bmap2, 1024);
 331}
 332
 333static void __init test_bitmap_region(void)
 334{
 335	int pos, order;
 336
 337	DECLARE_BITMAP(bmap, 1000);
 338
 339	bitmap_zero(bmap, 1000);
 340
 341	for (order = 0; order < 10; order++) {
 342		pos = bitmap_find_free_region(bmap, 1000, order);
 343		if (order == 0)
 344			expect_eq_uint(pos, 0);
 345		else
 346			expect_eq_uint(pos, order < 9 ? BIT(order) : -ENOMEM);
 347	}
 348
 349	bitmap_release_region(bmap, 0, 0);
 350	for (order = 1; order < 9; order++)
 351		bitmap_release_region(bmap, BIT(order), order);
 352
 353	expect_eq_uint(bitmap_weight(bmap, 1000), 0);
 354}
 355
 356#define EXP2_IN_BITS	(sizeof(exp2) * 8)
 357
 358static void __init test_replace(void)
 359{
 360	unsigned int nbits = 64;
 361	unsigned int nlongs = DIV_ROUND_UP(nbits, BITS_PER_LONG);
 362	DECLARE_BITMAP(bmap, 1024);
 363
 364	BUILD_BUG_ON(EXP2_IN_BITS < nbits * 2);
 365
 366	bitmap_zero(bmap, 1024);
 367	bitmap_replace(bmap, &exp2[0 * nlongs], &exp2[1 * nlongs], exp2_to_exp3_mask, nbits);
 368	expect_eq_bitmap(bmap, exp3_0_1, nbits);
 369
 370	bitmap_zero(bmap, 1024);
 371	bitmap_replace(bmap, &exp2[1 * nlongs], &exp2[0 * nlongs], exp2_to_exp3_mask, nbits);
 372	expect_eq_bitmap(bmap, exp3_1_0, nbits);
 373
 374	bitmap_fill(bmap, 1024);
 375	bitmap_replace(bmap, &exp2[0 * nlongs], &exp2[1 * nlongs], exp2_to_exp3_mask, nbits);
 376	expect_eq_bitmap(bmap, exp3_0_1, nbits);
 377
 378	bitmap_fill(bmap, 1024);
 379	bitmap_replace(bmap, &exp2[1 * nlongs], &exp2[0 * nlongs], exp2_to_exp3_mask, nbits);
 380	expect_eq_bitmap(bmap, exp3_1_0, nbits);
 381}
 382
 383static const unsigned long sg_mask[] __initconst = {
 384	BITMAP_FROM_U64(0x000000000000035aULL),
 385};
 386
 387static const unsigned long sg_src[] __initconst = {
 388	BITMAP_FROM_U64(0x0000000000000667ULL),
 389};
 390
 391static const unsigned long sg_gather_exp[] __initconst = {
 392	BITMAP_FROM_U64(0x0000000000000029ULL),
 393};
 394
 395static const unsigned long sg_scatter_exp[] __initconst = {
 396	BITMAP_FROM_U64(0x000000000000021aULL),
 397};
 398
 399static void __init test_bitmap_sg(void)
 400{
 401	unsigned int nbits = 64;
 402	DECLARE_BITMAP(bmap_gather, 100);
 403	DECLARE_BITMAP(bmap_scatter, 100);
 404	DECLARE_BITMAP(bmap_tmp, 100);
 405	DECLARE_BITMAP(bmap_res, 100);
 406
 407	/* Simple gather call */
 408	bitmap_zero(bmap_gather, 100);
 409	bitmap_gather(bmap_gather, sg_src, sg_mask, nbits);
 410	expect_eq_bitmap(sg_gather_exp, bmap_gather, nbits);
 411
 412	/* Simple scatter call */
 413	bitmap_zero(bmap_scatter, 100);
 414	bitmap_scatter(bmap_scatter, sg_src, sg_mask, nbits);
 415	expect_eq_bitmap(sg_scatter_exp, bmap_scatter, nbits);
 416
 417	/* Scatter/gather relationship */
 418	bitmap_zero(bmap_tmp, 100);
 419	bitmap_gather(bmap_tmp, bmap_scatter, sg_mask, nbits);
 420	bitmap_scatter(bmap_res, bmap_tmp, sg_mask, nbits);
 421	expect_eq_bitmap(bmap_scatter, bmap_res, nbits);
 422}
 423
 424#define PARSE_TIME	0x1
 425#define NO_LEN		0x2
 426
 427struct 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
 435static 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
 520static void __init test_bitmap_parselist(void)
 521{
 522	int i;
 523	int err;
 524	ktime_t time;
 525	DECLARE_BITMAP(bmap, 2048);
 526
 527	for (i = 0; i < ARRAY_SIZE(parselist_tests); i++) {
 528#define ptest parselist_tests[i]
 529
 530		time = ktime_get();
 531		err = bitmap_parselist(ptest.in, bmap, ptest.nbits);
 532		time = ktime_get() - time;
 533
 534		if (err != ptest.errno) {
 535			pr_err("parselist: %d: input is %s, errno is %d, expected %d\n",
 536					i, ptest.in, err, ptest.errno);
 537			failed_tests++;
 538			continue;
 539		}
 540
 541		if (!err && ptest.expected
 542			 && !__bitmap_equal(bmap, ptest.expected, ptest.nbits)) {
 543			pr_err("parselist: %d: input is %s, result is 0x%lx, expected 0x%lx\n",
 544					i, ptest.in, bmap[0],
 545					*ptest.expected);
 546			failed_tests++;
 547			continue;
 548		}
 549
 550		if (ptest.flags & PARSE_TIME)
 551			pr_info("parselist: %d: input is '%s' OK, Time: %llu\n",
 552					i, ptest.in, time);
 553
 554#undef ptest
 555	}
 556}
 557
 558static void __init test_bitmap_printlist(void)
 559{
 560	unsigned long *bmap = kmalloc(PAGE_SIZE, GFP_KERNEL);
 561	char *buf = kmalloc(PAGE_SIZE, GFP_KERNEL);
 562	char expected[256];
 563	int ret, slen;
 564	ktime_t time;
 565
 566	if (!buf || !bmap)
 567		goto out;
 568
 569	memset(bmap, -1, PAGE_SIZE);
 570	slen = snprintf(expected, 256, "0-%ld", PAGE_SIZE * 8 - 1);
 571	if (slen < 0)
 572		goto out;
 573
 574	time = ktime_get();
 575	ret = bitmap_print_to_pagebuf(true, buf, bmap, PAGE_SIZE * 8);
 576	time = ktime_get() - time;
 577
 578	if (ret != slen + 1) {
 579		pr_err("bitmap_print_to_pagebuf: result is %d, expected %d\n", ret, slen);
 580		failed_tests++;
 581		goto out;
 582	}
 583
 584	if (strncmp(buf, expected, slen)) {
 585		pr_err("bitmap_print_to_pagebuf: result is %s, expected %s\n", buf, expected);
 586		failed_tests++;
 587		goto out;
 588	}
 589
 590	pr_info("bitmap_print_to_pagebuf: input is '%s', Time: %llu\n", buf, time);
 591out:
 592	kfree(buf);
 593	kfree(bmap);
 594}
 595
 596static 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
 603static 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
 609static 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
 636static void __init test_bitmap_parse(void)
 637{
 638	int i;
 639	int err;
 640	ktime_t time;
 641	DECLARE_BITMAP(bmap, 2048);
 642
 643	for (i = 0; i < ARRAY_SIZE(parse_tests); i++) {
 644		struct test_bitmap_parselist test = parse_tests[i];
 645		size_t len = test.flags & NO_LEN ? UINT_MAX : strlen(test.in);
 646
 647		time = ktime_get();
 648		err = bitmap_parse(test.in, len, bmap, test.nbits);
 649		time = ktime_get() - time;
 650
 651		if (err != test.errno) {
 652			pr_err("parse: %d: input is %s, errno is %d, expected %d\n",
 653					i, test.in, err, test.errno);
 654			failed_tests++;
 655			continue;
 656		}
 657
 658		if (!err && test.expected
 659			 && !__bitmap_equal(bmap, test.expected, test.nbits)) {
 660			pr_err("parse: %d: input is %s, result is 0x%lx, expected 0x%lx\n",
 661					i, test.in, bmap[0],
 662					*test.expected);
 663			failed_tests++;
 664			continue;
 665		}
 666
 667		if (test.flags & PARSE_TIME)
 668			pr_info("parse: %d: input is '%s' OK, Time: %llu\n",
 669					i, test.in, time);
 670	}
 671}
 672
 
 
 673static void __init test_bitmap_arr32(void)
 674{
 675	unsigned int nbits, next_bit;
 676	u32 arr[EXP1_IN_BITS / 32];
 677	DECLARE_BITMAP(bmap2, EXP1_IN_BITS);
 678
 679	memset(arr, 0xa5, sizeof(arr));
 680
 681	for (nbits = 0; nbits < EXP1_IN_BITS; ++nbits) {
 682		bitmap_to_arr32(arr, exp1, nbits);
 683		bitmap_from_arr32(bmap2, arr, nbits);
 684		expect_eq_bitmap(bmap2, exp1, nbits);
 685
 686		next_bit = find_next_bit(bmap2,
 687				round_up(nbits, BITS_PER_LONG), nbits);
 688		if (next_bit < round_up(nbits, BITS_PER_LONG)) {
 689			pr_err("bitmap_copy_arr32(nbits == %d:"
 690				" tail is not safely cleared: %d\n",
 691				nbits, next_bit);
 692			failed_tests++;
 693		}
 694
 695		if (nbits < EXP1_IN_BITS - 32)
 696			expect_eq_uint(arr[DIV_ROUND_UP(nbits, 32)],
 697								0xa5a5a5a5);
 698	}
 699}
 700
 701static void __init test_bitmap_arr64(void)
 702{
 703	unsigned int nbits, next_bit;
 704	u64 arr[EXP1_IN_BITS / 64];
 705	DECLARE_BITMAP(bmap2, EXP1_IN_BITS);
 706
 707	memset(arr, 0xa5, sizeof(arr));
 708
 709	for (nbits = 0; nbits < EXP1_IN_BITS; ++nbits) {
 710		memset(bmap2, 0xff, sizeof(arr));
 711		bitmap_to_arr64(arr, exp1, nbits);
 712		bitmap_from_arr64(bmap2, arr, nbits);
 713		expect_eq_bitmap(bmap2, exp1, nbits);
 714
 715		next_bit = find_next_bit(bmap2, round_up(nbits, BITS_PER_LONG), nbits);
 716		if (next_bit < round_up(nbits, BITS_PER_LONG)) {
 717			pr_err("bitmap_copy_arr64(nbits == %d:"
 718				" tail is not safely cleared: %d\n", nbits, next_bit);
 719			failed_tests++;
 720		}
 721
 722		if ((nbits % 64) &&
 723		    (arr[(nbits - 1) / 64] & ~GENMASK_ULL((nbits - 1) % 64, 0))) {
 724			pr_err("bitmap_to_arr64(nbits == %d): tail is not safely cleared: 0x%016llx (must be 0x%016llx)\n",
 725			       nbits, arr[(nbits - 1) / 64],
 726			       GENMASK_ULL((nbits - 1) % 64, 0));
 727			failed_tests++;
 728		}
 729
 730		if (nbits < EXP1_IN_BITS - 64)
 731			expect_eq_uint(arr[DIV_ROUND_UP(nbits, 64)], 0xa5a5a5a5);
 732	}
 733}
 734
 735static void noinline __init test_mem_optimisations(void)
 736{
 737	DECLARE_BITMAP(bmap1, 1024);
 738	DECLARE_BITMAP(bmap2, 1024);
 739	unsigned int start, nbits;
 740
 741	for (start = 0; start < 1024; start += 8) {
 742		for (nbits = 0; nbits < 1024 - start; nbits += 8) {
 743			memset(bmap1, 0x5a, sizeof(bmap1));
 744			memset(bmap2, 0x5a, sizeof(bmap2));
 745
 746			bitmap_set(bmap1, start, nbits);
 747			__bitmap_set(bmap2, start, nbits);
 748			if (!bitmap_equal(bmap1, bmap2, 1024)) {
 749				printk("set not equal %d %d\n", start, nbits);
 750				failed_tests++;
 751			}
 752			if (!__bitmap_equal(bmap1, bmap2, 1024)) {
 753				printk("set not __equal %d %d\n", start, nbits);
 754				failed_tests++;
 755			}
 756
 757			bitmap_clear(bmap1, start, nbits);
 758			__bitmap_clear(bmap2, start, nbits);
 759			if (!bitmap_equal(bmap1, bmap2, 1024)) {
 760				printk("clear not equal %d %d\n", start, nbits);
 761				failed_tests++;
 762			}
 763			if (!__bitmap_equal(bmap1, bmap2, 1024)) {
 764				printk("clear not __equal %d %d\n", start,
 765									nbits);
 766				failed_tests++;
 767			}
 768		}
 769	}
 770}
 771
 772static 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
 783static void __init test_for_each_set_clump8(void)
 784{
 785#define CLUMP_EXP_NUMBITS 64
 786	DECLARE_BITMAP(bits, CLUMP_EXP_NUMBITS);
 787	unsigned int start;
 788	unsigned long clump;
 789
 790	/* set bitmap to test case */
 791	bitmap_zero(bits, CLUMP_EXP_NUMBITS);
 792	bitmap_set(bits, 0, 1);		/* 0x01 */
 793	bitmap_set(bits, 9, 1);		/* 0x02 */
 794	bitmap_set(bits, 27, 3);	/* 0x28 */
 795	bitmap_set(bits, 35, 3);	/* 0x28 */
 796	bitmap_set(bits, 40, 4);	/* 0x0F */
 797	bitmap_set(bits, 48, 8);	/* 0xFF */
 798	bitmap_set(bits, 56, 1);	/* 0x05 - part 1 */
 799	bitmap_set(bits, 58, 1);	/* 0x05 - part 2 */
 800
 801	for_each_set_clump8(start, clump, bits, CLUMP_EXP_NUMBITS)
 802		expect_eq_clump8(start, CLUMP_EXP_NUMBITS, clump_exp, &clump);
 803}
 804
 805static void __init test_for_each_set_bit_wrap(void)
 806{
 807	DECLARE_BITMAP(orig, 500);
 808	DECLARE_BITMAP(copy, 500);
 809	unsigned int wr, bit;
 810
 811	bitmap_zero(orig, 500);
 812
 813	/* Set individual bits */
 814	for (bit = 0; bit < 500; bit += 10)
 815		bitmap_set(orig, bit, 1);
 816
 817	/* Set range of bits */
 818	bitmap_set(orig, 100, 50);
 819
 820	for (wr = 0; wr < 500; wr++) {
 821		bitmap_zero(copy, 500);
 822
 823		for_each_set_bit_wrap(bit, orig, 500, wr)
 824			bitmap_set(copy, bit, 1);
 825
 826		expect_eq_bitmap(orig, copy, 500);
 827	}
 828}
 829
 830static void __init test_for_each_set_bit(void)
 831{
 832	DECLARE_BITMAP(orig, 500);
 833	DECLARE_BITMAP(copy, 500);
 834	unsigned int bit;
 835
 836	bitmap_zero(orig, 500);
 837	bitmap_zero(copy, 500);
 838
 839	/* Set individual bits */
 840	for (bit = 0; bit < 500; bit += 10)
 841		bitmap_set(orig, bit, 1);
 842
 843	/* Set range of bits */
 844	bitmap_set(orig, 100, 50);
 845
 846	for_each_set_bit(bit, orig, 500)
 847		bitmap_set(copy, bit, 1);
 848
 849	expect_eq_bitmap(orig, copy, 500);
 850}
 851
 852static void __init test_for_each_set_bit_from(void)
 853{
 854	DECLARE_BITMAP(orig, 500);
 855	DECLARE_BITMAP(copy, 500);
 856	unsigned int wr, bit;
 857
 858	bitmap_zero(orig, 500);
 859
 860	/* Set individual bits */
 861	for (bit = 0; bit < 500; bit += 10)
 862		bitmap_set(orig, bit, 1);
 863
 864	/* Set range of bits */
 865	bitmap_set(orig, 100, 50);
 866
 867	for (wr = 0; wr < 500; wr++) {
 868		DECLARE_BITMAP(tmp, 500);
 869
 870		bitmap_zero(copy, 500);
 871		bit = wr;
 872
 873		for_each_set_bit_from(bit, orig, 500)
 874			bitmap_set(copy, bit, 1);
 875
 876		bitmap_copy(tmp, orig, 500);
 877		bitmap_clear(tmp, 0, wr);
 878		expect_eq_bitmap(tmp, copy, 500);
 879	}
 880}
 881
 882static void __init test_for_each_clear_bit(void)
 883{
 884	DECLARE_BITMAP(orig, 500);
 885	DECLARE_BITMAP(copy, 500);
 886	unsigned int bit;
 887
 888	bitmap_fill(orig, 500);
 889	bitmap_fill(copy, 500);
 890
 891	/* Set individual bits */
 892	for (bit = 0; bit < 500; bit += 10)
 893		bitmap_clear(orig, bit, 1);
 894
 895	/* Set range of bits */
 896	bitmap_clear(orig, 100, 50);
 897
 898	for_each_clear_bit(bit, orig, 500)
 899		bitmap_clear(copy, bit, 1);
 900
 901	expect_eq_bitmap(orig, copy, 500);
 902}
 903
 904static void __init test_for_each_clear_bit_from(void)
 905{
 906	DECLARE_BITMAP(orig, 500);
 907	DECLARE_BITMAP(copy, 500);
 908	unsigned int wr, bit;
 909
 910	bitmap_fill(orig, 500);
 911
 912	/* Set individual bits */
 913	for (bit = 0; bit < 500; bit += 10)
 914		bitmap_clear(orig, bit, 1);
 915
 916	/* Set range of bits */
 917	bitmap_clear(orig, 100, 50);
 918
 919	for (wr = 0; wr < 500; wr++) {
 920		DECLARE_BITMAP(tmp, 500);
 921
 922		bitmap_fill(copy, 500);
 923		bit = wr;
 924
 925		for_each_clear_bit_from(bit, orig, 500)
 926			bitmap_clear(copy, bit, 1);
 927
 928		bitmap_copy(tmp, orig, 500);
 929		bitmap_set(tmp, 0, wr);
 930		expect_eq_bitmap(tmp, copy, 500);
 931	}
 932}
 933
 934static void __init test_for_each_set_bitrange(void)
 935{
 936	DECLARE_BITMAP(orig, 500);
 937	DECLARE_BITMAP(copy, 500);
 938	unsigned int s, e;
 939
 940	bitmap_zero(orig, 500);
 941	bitmap_zero(copy, 500);
 942
 943	/* Set individual bits */
 944	for (s = 0; s < 500; s += 10)
 945		bitmap_set(orig, s, 1);
 946
 947	/* Set range of bits */
 948	bitmap_set(orig, 100, 50);
 949
 950	for_each_set_bitrange(s, e, orig, 500)
 951		bitmap_set(copy, s, e-s);
 952
 953	expect_eq_bitmap(orig, copy, 500);
 954}
 955
 956static void __init test_for_each_clear_bitrange(void)
 957{
 958	DECLARE_BITMAP(orig, 500);
 959	DECLARE_BITMAP(copy, 500);
 960	unsigned int s, e;
 961
 962	bitmap_fill(orig, 500);
 963	bitmap_fill(copy, 500);
 964
 965	/* Set individual bits */
 966	for (s = 0; s < 500; s += 10)
 967		bitmap_clear(orig, s, 1);
 968
 969	/* Set range of bits */
 970	bitmap_clear(orig, 100, 50);
 971
 972	for_each_clear_bitrange(s, e, orig, 500)
 973		bitmap_clear(copy, s, e-s);
 974
 975	expect_eq_bitmap(orig, copy, 500);
 976}
 977
 978static void __init test_for_each_set_bitrange_from(void)
 979{
 980	DECLARE_BITMAP(orig, 500);
 981	DECLARE_BITMAP(copy, 500);
 982	unsigned int wr, s, e;
 983
 984	bitmap_zero(orig, 500);
 985
 986	/* Set individual bits */
 987	for (s = 0; s < 500; s += 10)
 988		bitmap_set(orig, s, 1);
 989
 990	/* Set range of bits */
 991	bitmap_set(orig, 100, 50);
 992
 993	for (wr = 0; wr < 500; wr++) {
 994		DECLARE_BITMAP(tmp, 500);
 995
 996		bitmap_zero(copy, 500);
 997		s = wr;
 998
 999		for_each_set_bitrange_from(s, e, orig, 500)
1000			bitmap_set(copy, s, e - s);
1001
1002		bitmap_copy(tmp, orig, 500);
1003		bitmap_clear(tmp, 0, wr);
1004		expect_eq_bitmap(tmp, copy, 500);
1005	}
1006}
1007
1008static void __init test_for_each_clear_bitrange_from(void)
1009{
1010	DECLARE_BITMAP(orig, 500);
1011	DECLARE_BITMAP(copy, 500);
1012	unsigned int wr, s, e;
1013
1014	bitmap_fill(orig, 500);
1015
1016	/* Set individual bits */
1017	for (s = 0; s < 500; s += 10)
1018		bitmap_clear(orig, s, 1);
1019
1020	/* Set range of bits */
1021	bitmap_set(orig, 100, 50);
1022
1023	for (wr = 0; wr < 500; wr++) {
1024		DECLARE_BITMAP(tmp, 500);
1025
1026		bitmap_fill(copy, 500);
1027		s = wr;
1028
1029		for_each_clear_bitrange_from(s, e, orig, 500)
1030			bitmap_clear(copy, s, e - s);
1031
1032		bitmap_copy(tmp, orig, 500);
1033		bitmap_set(tmp, 0, wr);
1034		expect_eq_bitmap(tmp, copy, 500);
1035	}
1036}
1037
1038struct 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
1046static 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
1079static void __init test_bitmap_cut(void)
1080{
1081	unsigned long b[5], *in = &b[1], *out = &b[0];	/* Partial overlap */
1082	int i;
1083
1084	for (i = 0; i < ARRAY_SIZE(test_cut); i++) {
1085		struct test_bitmap_cut *t = &test_cut[i];
1086
1087		memcpy(in, t->in, sizeof(t->in));
1088
1089		bitmap_cut(out, in, t->first, t->cut, t->nbits);
1090
1091		expect_eq_bitmap(t->expected, out, t->nbits);
1092	}
1093}
1094
1095struct test_bitmap_print {
1096	const unsigned long *bitmap;
1097	unsigned long nbits;
1098	const char *mask;
1099	const char *list;
1100};
1101
1102static const unsigned long small_bitmap[] __initconst = {
1103	BITMAP_FROM_U64(0x3333333311111111ULL),
1104};
1105
1106static const char small_mask[] __initconst = "33333333,11111111\n";
1107static 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
1109static 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
1132static 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
1153static 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
1195static 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
1200static void __init test_bitmap_print_buf(void)
1201{
1202	int i;
1203
1204	for (i = 0; i < ARRAY_SIZE(test_print); i++) {
1205		const struct test_bitmap_print *t = &test_print[i];
1206		int n;
1207
1208		n = bitmap_print_bitmask_to_buf(print_buf, t->bitmap, t->nbits,
1209						0, 2 * PAGE_SIZE);
1210		expect_eq_uint(strlen(t->mask) + 1, n);
1211		expect_eq_str(t->mask, print_buf, n);
1212
1213		n = bitmap_print_list_to_buf(print_buf, t->bitmap, t->nbits,
1214					     0, 2 * PAGE_SIZE);
1215		expect_eq_uint(strlen(t->list) + 1, n);
1216		expect_eq_str(t->list, print_buf, n);
1217
1218		/* test by non-zero offset */
1219		if (strlen(t->list) > PAGE_SIZE) {
1220			n = bitmap_print_list_to_buf(print_buf, t->bitmap, t->nbits,
1221						     PAGE_SIZE, PAGE_SIZE);
1222			expect_eq_uint(strlen(t->list) + 1 - PAGE_SIZE, n);
1223			expect_eq_str(t->list + PAGE_SIZE, print_buf, n);
1224		}
1225	}
1226}
1227
1228/*
1229 * FIXME: Clang breaks compile-time evaluations when KASAN and GCOV are enabled.
1230 * To workaround it, GCOV is force-disabled in Makefile for this configuration.
1231 */
1232static void __init test_bitmap_const_eval(void)
1233{
1234	DECLARE_BITMAP(bitmap, BITS_PER_LONG);
1235	unsigned long initvar = BIT(2);
1236	unsigned long bitopvar = 0;
1237	unsigned long var = 0;
1238	int res;
1239
1240	/*
1241	 * Compilers must be able to optimize all of those to compile-time
1242	 * constants on any supported optimization level (-O2, -Os) and any
1243	 * architecture. Otherwise, trigger a build bug.
1244	 * The whole function gets optimized out then, there's nothing to do
1245	 * in runtime.
1246	 */
1247
1248	/* Equals to `unsigned long bitmap[1] = { GENMASK(6, 5), }` */
1249	bitmap_clear(bitmap, 0, BITS_PER_LONG);
1250	if (!test_bit(7, bitmap))
1251		bitmap_set(bitmap, 5, 2);
1252
1253	/* Equals to `unsigned long bitopvar = BIT(20)` */
1254	__change_bit(31, &bitopvar);
1255	bitmap_shift_right(&bitopvar, &bitopvar, 11, BITS_PER_LONG);
1256
1257	/* Equals to `unsigned long var = BIT(25)` */
1258	var |= BIT(25);
1259	if (var & BIT(0))
1260		var ^= GENMASK(9, 6);
1261
1262	/* __const_hweight<32|64>(GENMASK(6, 5)) == 2 */
1263	res = bitmap_weight(bitmap, 20);
1264	BUILD_BUG_ON(!__builtin_constant_p(res));
1265	BUILD_BUG_ON(res != 2);
1266
1267	/* !(BIT(31) & BIT(18)) == 1 */
1268	res = !test_bit(18, &bitopvar);
1269	BUILD_BUG_ON(!__builtin_constant_p(res));
1270	BUILD_BUG_ON(!res);
1271
1272	/* BIT(2) & GENMASK(14, 8) == 0 */
1273	res = initvar & GENMASK(14, 8);
1274	BUILD_BUG_ON(!__builtin_constant_p(res));
1275	BUILD_BUG_ON(res);
1276
1277	/* ~BIT(25) */
1278	BUILD_BUG_ON(!__builtin_constant_p(~var));
1279	BUILD_BUG_ON(~var != ~BIT(25));
1280
1281	/* ~BIT(25) | BIT(25) == ~0UL */
1282	bitmap_complement(&var, &var, BITS_PER_LONG);
1283	__assign_bit(25, &var, true);
1284
1285	/* !(~(~0UL)) == 1 */
1286	res = bitmap_full(&var, BITS_PER_LONG);
1287	BUILD_BUG_ON(!__builtin_constant_p(res));
1288	BUILD_BUG_ON(!res);
1289}
1290
1291/*
1292 * Test bitmap should be big enough to include the cases when start is not in
1293 * the first word, and start+nbits lands in the following word.
1294 */
1295#define TEST_BIT_LEN (1000)
1296
1297/*
1298 * Helper function to test bitmap_write() overwriting the chosen byte pattern.
1299 */
1300static void __init test_bitmap_write_helper(const char *pattern)
1301{
1302	DECLARE_BITMAP(bitmap, TEST_BIT_LEN);
1303	DECLARE_BITMAP(exp_bitmap, TEST_BIT_LEN);
1304	DECLARE_BITMAP(pat_bitmap, TEST_BIT_LEN);
1305	unsigned long w, r, bit;
1306	int i, n, nbits;
1307
1308	/*
1309	 * Only parse the pattern once and store the result in the intermediate
1310	 * bitmap.
1311	 */
1312	bitmap_parselist(pattern, pat_bitmap, TEST_BIT_LEN);
1313
1314	/*
1315	 * Check that writing a single bit does not accidentally touch the
1316	 * adjacent bits.
1317	 */
1318	for (i = 0; i < TEST_BIT_LEN; i++) {
1319		bitmap_copy(bitmap, pat_bitmap, TEST_BIT_LEN);
1320		bitmap_copy(exp_bitmap, pat_bitmap, TEST_BIT_LEN);
1321		for (bit = 0; bit <= 1; bit++) {
1322			bitmap_write(bitmap, bit, i, 1);
1323			__assign_bit(i, exp_bitmap, bit);
1324			expect_eq_bitmap(exp_bitmap, bitmap,
1325					 TEST_BIT_LEN);
1326		}
1327	}
1328
1329	/* Ensure writing 0 bits does not change anything. */
1330	bitmap_copy(bitmap, pat_bitmap, TEST_BIT_LEN);
1331	bitmap_copy(exp_bitmap, pat_bitmap, TEST_BIT_LEN);
1332	for (i = 0; i < TEST_BIT_LEN; i++) {
1333		bitmap_write(bitmap, ~0UL, i, 0);
1334		expect_eq_bitmap(exp_bitmap, bitmap, TEST_BIT_LEN);
1335	}
1336
1337	for (nbits = BITS_PER_LONG; nbits >= 1; nbits--) {
1338		w = IS_ENABLED(CONFIG_64BIT) ? 0xdeadbeefdeadbeefUL
1339					     : 0xdeadbeefUL;
1340		w >>= (BITS_PER_LONG - nbits);
1341		for (i = 0; i <= TEST_BIT_LEN - nbits; i++) {
1342			bitmap_copy(bitmap, pat_bitmap, TEST_BIT_LEN);
1343			bitmap_copy(exp_bitmap, pat_bitmap, TEST_BIT_LEN);
1344			for (n = 0; n < nbits; n++)
1345				__assign_bit(i + n, exp_bitmap, w & BIT(n));
1346			bitmap_write(bitmap, w, i, nbits);
1347			expect_eq_bitmap(exp_bitmap, bitmap, TEST_BIT_LEN);
1348			r = bitmap_read(bitmap, i, nbits);
1349			expect_eq_ulong(r, w);
1350		}
1351	}
1352}
1353
1354static void __init test_bitmap_read_write(void)
1355{
1356	unsigned char *pattern[3] = {"", "all:1/2", "all"};
1357	DECLARE_BITMAP(bitmap, TEST_BIT_LEN);
1358	unsigned long zero_bits = 0, bits_per_long = BITS_PER_LONG;
1359	unsigned long val;
1360	int i, pi;
1361
1362	/*
1363	 * Reading/writing zero bits should not crash the kernel.
1364	 * READ_ONCE() prevents constant folding.
1365	 */
1366	bitmap_write(NULL, 0, 0, READ_ONCE(zero_bits));
1367	/* Return value of bitmap_read() is undefined here. */
1368	bitmap_read(NULL, 0, READ_ONCE(zero_bits));
1369
1370	/*
1371	 * Reading/writing more than BITS_PER_LONG bits should not crash the
1372	 * kernel. READ_ONCE() prevents constant folding.
1373	 */
1374	bitmap_write(NULL, 0, 0, READ_ONCE(bits_per_long) + 1);
1375	/* Return value of bitmap_read() is undefined here. */
1376	bitmap_read(NULL, 0, READ_ONCE(bits_per_long) + 1);
1377
1378	/*
1379	 * Ensure that bitmap_read() reads the same value that was previously
1380	 * written, and two consequent values are correctly merged.
1381	 * The resulting bit pattern is asymmetric to rule out possible issues
1382	 * with bit numeration order.
1383	 */
1384	for (i = 0; i < TEST_BIT_LEN - 7; i++) {
1385		bitmap_zero(bitmap, TEST_BIT_LEN);
1386
1387		bitmap_write(bitmap, 0b10101UL, i, 5);
1388		val = bitmap_read(bitmap, i, 5);
1389		expect_eq_ulong(0b10101UL, val);
1390
1391		bitmap_write(bitmap, 0b101UL, i + 5, 3);
1392		val = bitmap_read(bitmap, i + 5, 3);
1393		expect_eq_ulong(0b101UL, val);
1394
1395		val = bitmap_read(bitmap, i, 8);
1396		expect_eq_ulong(0b10110101UL, val);
1397	}
1398
1399	for (pi = 0; pi < ARRAY_SIZE(pattern); pi++)
1400		test_bitmap_write_helper(pattern[pi]);
1401}
1402
1403static void __init test_bitmap_read_perf(void)
1404{
1405	DECLARE_BITMAP(bitmap, TEST_BIT_LEN);
1406	unsigned int cnt, nbits, i;
1407	unsigned long val;
1408	ktime_t time;
1409
1410	bitmap_fill(bitmap, TEST_BIT_LEN);
1411	time = ktime_get();
1412	for (cnt = 0; cnt < 5; cnt++) {
1413		for (nbits = 1; nbits <= BITS_PER_LONG; nbits++) {
1414			for (i = 0; i < TEST_BIT_LEN; i++) {
1415				if (i + nbits > TEST_BIT_LEN)
1416					break;
1417				/*
1418				 * Prevent the compiler from optimizing away the
1419				 * bitmap_read() by using its value.
1420				 */
1421				WRITE_ONCE(val, bitmap_read(bitmap, i, nbits));
1422			}
1423		}
1424	}
1425	time = ktime_get() - time;
1426	pr_info("Time spent in %s:\t%llu\n", __func__, time);
1427}
1428
1429static void __init test_bitmap_write_perf(void)
1430{
1431	DECLARE_BITMAP(bitmap, TEST_BIT_LEN);
1432	unsigned int cnt, nbits, i;
1433	unsigned long val = 0xfeedface;
1434	ktime_t time;
1435
1436	bitmap_zero(bitmap, TEST_BIT_LEN);
1437	time = ktime_get();
1438	for (cnt = 0; cnt < 5; cnt++) {
1439		for (nbits = 1; nbits <= BITS_PER_LONG; nbits++) {
1440			for (i = 0; i < TEST_BIT_LEN; i++) {
1441				if (i + nbits > TEST_BIT_LEN)
1442					break;
1443				bitmap_write(bitmap, val, i, nbits);
1444			}
1445		}
1446	}
1447	time = ktime_get() - time;
1448	pr_info("Time spent in %s:\t%llu\n", __func__, time);
1449}
1450
1451#undef TEST_BIT_LEN
1452
1453static void __init selftest(void)
1454{
1455	test_zero_clear();
1456	test_fill_set();
1457	test_copy();
1458	test_bitmap_region();
1459	test_replace();
1460	test_bitmap_sg();
1461	test_bitmap_arr32();
1462	test_bitmap_arr64();
1463	test_bitmap_parse();
1464	test_bitmap_parselist();
1465	test_bitmap_printlist();
1466	test_mem_optimisations();
 
1467	test_bitmap_cut();
1468	test_bitmap_print_buf();
1469	test_bitmap_const_eval();
1470	test_bitmap_read_write();
1471	test_bitmap_read_perf();
1472	test_bitmap_write_perf();
1473
1474	test_find_nth_bit();
1475	test_for_each_set_bit();
1476	test_for_each_set_bit_from();
1477	test_for_each_clear_bit();
1478	test_for_each_clear_bit_from();
1479	test_for_each_set_bitrange();
1480	test_for_each_clear_bitrange();
1481	test_for_each_set_bitrange_from();
1482	test_for_each_clear_bitrange_from();
1483	test_for_each_set_clump8();
1484	test_for_each_set_bit_wrap();
1485}
1486
1487KSTM_MODULE_LOADERS(test_bitmap);
1488MODULE_AUTHOR("david decotigny <david.decotigny@googlers.com>");
1489MODULE_DESCRIPTION("Test cases for bitmap API");
1490MODULE_LICENSE("GPL");