[thirdparty/linux.git] / lib / test_bitmap.c

// SPDX-License-Identifier: GPL-2.0-only
/*
 * Test cases for bitmap API.
 */

#define pr_fmt(fmt) KBUILD_MODNAME ": " fmt

#include <linux/bitmap.h>
#include <linux/init.h>
#include <linux/kernel.h>
#include <linux/module.h>
#include <linux/printk.h>
#include <linux/slab.h>
#include <linux/string.h>
#include <linux/uaccess.h>

#include "../tools/testing/selftests/kselftest_module.h"

KSTM_MODULE_GLOBALS();

static char pbl_buffer[PAGE_SIZE] __initdata;

static const unsigned long exp1[] __initconst = {
	BITMAP_FROM_U64(1),
	BITMAP_FROM_U64(2),
	BITMAP_FROM_U64(0x0000ffff),
	BITMAP_FROM_U64(0xffff0000),
	BITMAP_FROM_U64(0x55555555),
	BITMAP_FROM_U64(0xaaaaaaaa),
	BITMAP_FROM_U64(0x11111111),
	BITMAP_FROM_U64(0x22222222),
	BITMAP_FROM_U64(0xffffffff),
	BITMAP_FROM_U64(0xfffffffe),
	BITMAP_FROM_U64(0x3333333311111111ULL),
	BITMAP_FROM_U64(0xffffffff77777777ULL),
	BITMAP_FROM_U64(0),
};

static const unsigned long exp2[] __initconst = {
	BITMAP_FROM_U64(0x3333333311111111ULL),
	BITMAP_FROM_U64(0xffffffff77777777ULL),
};

/* Fibonacci sequence */
static const unsigned long exp2_to_exp3_mask[] __initconst = {
	BITMAP_FROM_U64(0x008000020020212eULL),
};
/* exp3_0_1 = (exp2[0] & ~exp2_to_exp3_mask) | (exp2[1] & exp2_to_exp3_mask) */
static const unsigned long exp3_0_1[] __initconst = {
	BITMAP_FROM_U64(0x33b3333311313137ULL),
};
/* exp3_1_0 = (exp2[1] & ~exp2_to_exp3_mask) | (exp2[0] & exp2_to_exp3_mask) */
static const unsigned long exp3_1_0[] __initconst = {
	BITMAP_FROM_U64(0xff7fffff77575751ULL),
};

static bool __init
__check_eq_uint(const char *srcfile, unsigned int line,
		const unsigned int exp_uint, unsigned int x)
{
	if (exp_uint != x) {
		pr_err("[%s:%u] expected %u, got %u\n",
			srcfile, line, exp_uint, x);
		return false;
	}
	return true;
}


static bool __init
__check_eq_bitmap(const char *srcfile, unsigned int line,
		  const unsigned long *exp_bmap, const unsigned long *bmap,
		  unsigned int nbits)
{
	if (!bitmap_equal(exp_bmap, bmap, nbits)) {
		pr_warn("[%s:%u] bitmaps contents differ: expected \"%*pbl\", got \"%*pbl\"\n",
			srcfile, line,
			nbits, exp_bmap, nbits, bmap);
		return false;
	}
	return true;
}

static bool __init
__check_eq_pbl(const char *srcfile, unsigned int line,
	       const char *expected_pbl,
	       const unsigned long *bitmap, unsigned int nbits)
{
	snprintf(pbl_buffer, sizeof(pbl_buffer), "%*pbl", nbits, bitmap);
	if (strcmp(expected_pbl, pbl_buffer)) {
		pr_warn("[%s:%u] expected \"%s\", got \"%s\"\n",
			srcfile, line,
			expected_pbl, pbl_buffer);
		return false;
	}
	return true;
}

static bool __init
__check_eq_u32_array(const char *srcfile, unsigned int line,
		     const u32 *exp_arr, unsigned int exp_len,
		     const u32 *arr, unsigned int len) __used;
static bool __init
__check_eq_u32_array(const char *srcfile, unsigned int line,
		     const u32 *exp_arr, unsigned int exp_len,
		     const u32 *arr, unsigned int len)
{
	if (exp_len != len) {
		pr_warn("[%s:%u] array length differ: expected %u, got %u\n",
			srcfile, line,
			exp_len, len);
		return false;
	}

	if (memcmp(exp_arr, arr, len*sizeof(*arr))) {
		pr_warn("[%s:%u] array contents differ\n", srcfile, line);
		print_hex_dump(KERN_WARNING, "  exp:  ", DUMP_PREFIX_OFFSET,
			       32, 4, exp_arr, exp_len*sizeof(*exp_arr), false);
		print_hex_dump(KERN_WARNING, "  got:  ", DUMP_PREFIX_OFFSET,
			       32, 4, arr, len*sizeof(*arr), false);
		return false;
	}

	return true;
}

static bool __init __check_eq_clump8(const char *srcfile, unsigned int line,
				    const unsigned int offset,
				    const unsigned int size,
				    const unsigned char *const clump_exp,
				    const unsigned long *const clump)
{
	unsigned long exp;

	if (offset >= size) {
		pr_warn("[%s:%u] bit offset for clump out-of-bounds: expected less than %u, got %u\n",
			srcfile, line, size, offset);
		return false;
	}

	exp = clump_exp[offset / 8];
	if (!exp) {
		pr_warn("[%s:%u] bit offset for zero clump: expected nonzero clump, got bit offset %u with clump value 0",
			srcfile, line, offset);
		return false;
	}

	if (*clump != exp) {
		pr_warn("[%s:%u] expected clump value of 0x%lX, got clump value of 0x%lX",
			srcfile, line, exp, *clump);
		return false;
	}

	return true;
}

#define __expect_eq(suffix, ...)					\
	({								\
		int result = 0;						\
		total_tests++;						\
		if (!__check_eq_ ## suffix(__FILE__, __LINE__,		\
					   ##__VA_ARGS__)) {		\
			failed_tests++;					\
			result = 1;					\
		}							\
		result;							\
	})

#define expect_eq_uint(...)		__expect_eq(uint, ##__VA_ARGS__)
#define expect_eq_bitmap(...)		__expect_eq(bitmap, ##__VA_ARGS__)
#define expect_eq_pbl(...)		__expect_eq(pbl, ##__VA_ARGS__)
#define expect_eq_u32_array(...)	__expect_eq(u32_array, ##__VA_ARGS__)
#define expect_eq_clump8(...)		__expect_eq(clump8, ##__VA_ARGS__)

static void __init test_zero_clear(void)
{
	DECLARE_BITMAP(bmap, 1024);

	/* Known way to set all bits */
	memset(bmap, 0xff, 128);

	expect_eq_pbl("0-22", bmap, 23);
	expect_eq_pbl("0-1023", bmap, 1024);

	/* single-word bitmaps */
	bitmap_clear(bmap, 0, 9);
	expect_eq_pbl("9-1023", bmap, 1024);

	bitmap_zero(bmap, 35);
	expect_eq_pbl("64-1023", bmap, 1024);

	/* cross boundaries operations */
	bitmap_clear(bmap, 79, 19);
	expect_eq_pbl("64-78,98-1023", bmap, 1024);

	bitmap_zero(bmap, 115);
	expect_eq_pbl("128-1023", bmap, 1024);

	/* Zeroing entire area */
	bitmap_zero(bmap, 1024);
	expect_eq_pbl("", bmap, 1024);
}

static void __init test_fill_set(void)
{
	DECLARE_BITMAP(bmap, 1024);

	/* Known way to clear all bits */
	memset(bmap, 0x00, 128);

	expect_eq_pbl("", bmap, 23);
	expect_eq_pbl("", bmap, 1024);

	/* single-word bitmaps */
	bitmap_set(bmap, 0, 9);
	expect_eq_pbl("0-8", bmap, 1024);

	bitmap_fill(bmap, 35);
	expect_eq_pbl("0-63", bmap, 1024);

	/* cross boundaries operations */
	bitmap_set(bmap, 79, 19);
	expect_eq_pbl("0-63,79-97", bmap, 1024);

	bitmap_fill(bmap, 115);
	expect_eq_pbl("0-127", bmap, 1024);

	/* Zeroing entire area */
	bitmap_fill(bmap, 1024);
	expect_eq_pbl("0-1023", bmap, 1024);
}

static void __init test_copy(void)
{
	DECLARE_BITMAP(bmap1, 1024);
	DECLARE_BITMAP(bmap2, 1024);

	bitmap_zero(bmap1, 1024);
	bitmap_zero(bmap2, 1024);

	/* single-word bitmaps */
	bitmap_set(bmap1, 0, 19);
	bitmap_copy(bmap2, bmap1, 23);
	expect_eq_pbl("0-18", bmap2, 1024);

	bitmap_set(bmap2, 0, 23);
	bitmap_copy(bmap2, bmap1, 23);
	expect_eq_pbl("0-18", bmap2, 1024);

	/* multi-word bitmaps */
	bitmap_set(bmap1, 0, 109);
	bitmap_copy(bmap2, bmap1, 1024);
	expect_eq_pbl("0-108", bmap2, 1024);

	bitmap_fill(bmap2, 1024);
	bitmap_copy(bmap2, bmap1, 1024);
	expect_eq_pbl("0-108", bmap2, 1024);

	/* the following tests assume a 32- or 64-bit arch (even 128b
	 * if we care)
	 */

	bitmap_fill(bmap2, 1024);
	bitmap_copy(bmap2, bmap1, 109);  /* ... but 0-padded til word length */
	expect_eq_pbl("0-108,128-1023", bmap2, 1024);

	bitmap_fill(bmap2, 1024);
	bitmap_copy(bmap2, bmap1, 97);  /* ... but aligned on word length */
	expect_eq_pbl("0-108,128-1023", bmap2, 1024);
}

#define EXP2_IN_BITS	(sizeof(exp2) * 8)

static void __init test_replace(void)
{
	unsigned int nbits = 64;
	unsigned int nlongs = DIV_ROUND_UP(nbits, BITS_PER_LONG);
	DECLARE_BITMAP(bmap, 1024);

	BUILD_BUG_ON(EXP2_IN_BITS < nbits * 2);

	bitmap_zero(bmap, 1024);
	bitmap_replace(bmap, &exp2[0 * nlongs], &exp2[1 * nlongs], exp2_to_exp3_mask, nbits);
	expect_eq_bitmap(bmap, exp3_0_1, nbits);

	bitmap_zero(bmap, 1024);
	bitmap_replace(bmap, &exp2[1 * nlongs], &exp2[0 * nlongs], exp2_to_exp3_mask, nbits);
	expect_eq_bitmap(bmap, exp3_1_0, nbits);

	bitmap_fill(bmap, 1024);
	bitmap_replace(bmap, &exp2[0 * nlongs], &exp2[1 * nlongs], exp2_to_exp3_mask, nbits);
	expect_eq_bitmap(bmap, exp3_0_1, nbits);

	bitmap_fill(bmap, 1024);
	bitmap_replace(bmap, &exp2[1 * nlongs], &exp2[0 * nlongs], exp2_to_exp3_mask, nbits);
	expect_eq_bitmap(bmap, exp3_1_0, nbits);
}

#define PARSE_TIME	0x1
#define NO_LEN		0x2

struct test_bitmap_parselist{
	const int errno;
	const char *in;
	const unsigned long *expected;
	const int nbits;
	const int flags;
};

static const struct test_bitmap_parselist parselist_tests[] __initconst = {
#define step (sizeof(u64) / sizeof(unsigned long))

	{0, "0",			&exp1[0], 8, 0},
	{0, "1",			&exp1[1 * step], 8, 0},
	{0, "0-15",			&exp1[2 * step], 32, 0},
	{0, "16-31",			&exp1[3 * step], 32, 0},
	{0, "0-31:1/2",			&exp1[4 * step], 32, 0},
	{0, "1-31:1/2",			&exp1[5 * step], 32, 0},
	{0, "0-31:1/4",			&exp1[6 * step], 32, 0},
	{0, "1-31:1/4",			&exp1[7 * step], 32, 0},
	{0, "0-31:4/4",			&exp1[8 * step], 32, 0},
	{0, "1-31:4/4",			&exp1[9 * step], 32, 0},
	{0, "0-31:1/4,32-63:2/4",	&exp1[10 * step], 64, 0},
	{0, "0-31:3/4,32-63:4/4",	&exp1[11 * step], 64, 0},
	{0, "  ,,  0-31:3/4  ,, 32-63:4/4  ,,  ",	&exp1[11 * step], 64, 0},

	{0, "0-31:1/4,32-63:2/4,64-95:3/4,96-127:4/4",	exp2, 128, 0},

	{0, "0-2047:128/256", NULL, 2048, PARSE_TIME},

	{0, "",				&exp1[12 * step], 8, 0},
	{0, "\n",			&exp1[12 * step], 8, 0},
	{0, ",,  ,,  , ,  ,",		&exp1[12 * step], 8, 0},
	{0, " ,  ,,  , ,   ",		&exp1[12 * step], 8, 0},
	{0, " ,  ,,  , ,   \n",		&exp1[12 * step], 8, 0},

	{-EINVAL, "-1",	NULL, 8, 0},
	{-EINVAL, "-0",	NULL, 8, 0},
	{-EINVAL, "10-1", NULL, 8, 0},
	{-ERANGE, "8-8", NULL, 8, 0},
	{-ERANGE, "0-31", NULL, 8, 0},
	{-EINVAL, "0-31:", NULL, 32, 0},
	{-EINVAL, "0-31:0", NULL, 32, 0},
	{-EINVAL, "0-31:0/", NULL, 32, 0},
	{-EINVAL, "0-31:0/0", NULL, 32, 0},
	{-EINVAL, "0-31:1/0", NULL, 32, 0},
	{-EINVAL, "0-31:10/1", NULL, 32, 0},
	{-EOVERFLOW, "0-98765432123456789:10/1", NULL, 8, 0},

	{-EINVAL, "a-31", NULL, 8, 0},
	{-EINVAL, "0-a1", NULL, 8, 0},
	{-EINVAL, "a-31:10/1", NULL, 8, 0},
	{-EINVAL, "0-31:a/1", NULL, 8, 0},
	{-EINVAL, "0-\n", NULL, 8, 0},

};

static void __init test_bitmap_parselist(void)
{
	int i;
	int err;
	ktime_t time;
	DECLARE_BITMAP(bmap, 2048);

	for (i = 0; i < ARRAY_SIZE(parselist_tests); i++) {
#define ptest parselist_tests[i]

		time = ktime_get();
		err = bitmap_parselist(ptest.in, bmap, ptest.nbits);
		time = ktime_get() - time;

		if (err != ptest.errno) {
			pr_err("parselist: %d: input is %s, errno is %d, expected %d\n",
					i, ptest.in, err, ptest.errno);
			continue;
		}

		if (!err && ptest.expected
			 && !__bitmap_equal(bmap, ptest.expected, ptest.nbits)) {
			pr_err("parselist: %d: input is %s, result is 0x%lx, expected 0x%lx\n",
					i, ptest.in, bmap[0],
					*ptest.expected);
			continue;
		}

		if (ptest.flags & PARSE_TIME)
			pr_err("parselist: %d: input is '%s' OK, Time: %llu\n",
					i, ptest.in, time);

#undef ptest
	}
}

static const unsigned long parse_test[] __initconst = {
	BITMAP_FROM_U64(0),
	BITMAP_FROM_U64(1),
	BITMAP_FROM_U64(0xdeadbeef),
	BITMAP_FROM_U64(0x100000000ULL),
};

static const unsigned long parse_test2[] __initconst = {
	BITMAP_FROM_U64(0x100000000ULL), BITMAP_FROM_U64(0xdeadbeef),
	BITMAP_FROM_U64(0x100000000ULL), BITMAP_FROM_U64(0xbaadf00ddeadbeef),
	BITMAP_FROM_U64(0x100000000ULL), BITMAP_FROM_U64(0x0badf00ddeadbeef),
};

static const struct test_bitmap_parselist parse_tests[] __initconst = {
	{0, "",				&parse_test[0 * step], 32, 0},
	{0, " ",			&parse_test[0 * step], 32, 0},
	{0, "0",			&parse_test[0 * step], 32, 0},
	{0, "0\n",			&parse_test[0 * step], 32, 0},
	{0, "1",			&parse_test[1 * step], 32, 0},
	{0, "deadbeef",			&parse_test[2 * step], 32, 0},
	{0, "1,0",			&parse_test[3 * step], 33, 0},
	{0, "deadbeef,\n,0,1",		&parse_test[2 * step], 96, 0},

	{0, "deadbeef,1,0",		&parse_test2[0 * 2 * step], 96, 0},
	{0, "baadf00d,deadbeef,1,0",	&parse_test2[1 * 2 * step], 128, 0},
	{0, "badf00d,deadbeef,1,0",	&parse_test2[2 * 2 * step], 124, 0},
	{0, "badf00d,deadbeef,1,0",	&parse_test2[2 * 2 * step], 124, NO_LEN},
	{0, "  badf00d,deadbeef,1,0  ",	&parse_test2[2 * 2 * step], 124, 0},
	{0, " , badf00d,deadbeef,1,0 , ",	&parse_test2[2 * 2 * step], 124, 0},
	{0, " , badf00d, ,, ,,deadbeef,1,0 , ",	&parse_test2[2 * 2 * step], 124, 0},

	{-EINVAL,    "goodfood,deadbeef,1,0",	NULL, 128, 0},
	{-EOVERFLOW, "3,0",			NULL, 33, 0},
	{-EOVERFLOW, "123badf00d,deadbeef,1,0",	NULL, 128, 0},
	{-EOVERFLOW, "badf00d,deadbeef,1,0",	NULL, 90, 0},
	{-EOVERFLOW, "fbadf00d,deadbeef,1,0",	NULL, 95, 0},
	{-EOVERFLOW, "badf00d,deadbeef,1,0",	NULL, 100, 0},
#undef step
};

static void __init test_bitmap_parse(void)
{
	int i;
	int err;
	ktime_t time;
	DECLARE_BITMAP(bmap, 2048);

	for (i = 0; i < ARRAY_SIZE(parse_tests); i++) {
		struct test_bitmap_parselist test = parse_tests[i];
		size_t len = test.flags & NO_LEN ? UINT_MAX : strlen(test.in);

		time = ktime_get();
		err = bitmap_parse(test.in, len, bmap, test.nbits);
		time = ktime_get() - time;

		if (err != test.errno) {
			pr_err("parse: %d: input is %s, errno is %d, expected %d\n",
					i, test.in, err, test.errno);
			continue;
		}

		if (!err && test.expected
			 && !__bitmap_equal(bmap, test.expected, test.nbits)) {
			pr_err("parse: %d: input is %s, result is 0x%lx, expected 0x%lx\n",
					i, test.in, bmap[0],
					*test.expected);
			continue;
		}

		if (test.flags & PARSE_TIME)
			pr_err("parse: %d: input is '%s' OK, Time: %llu\n",
					i, test.in, time);
	}
}

#define EXP1_IN_BITS	(sizeof(exp1) * 8)

static void __init test_bitmap_arr32(void)
{
	unsigned int nbits, next_bit;
	u32 arr[EXP1_IN_BITS / 32];
	DECLARE_BITMAP(bmap2, EXP1_IN_BITS);

	memset(arr, 0xa5, sizeof(arr));

	for (nbits = 0; nbits < EXP1_IN_BITS; ++nbits) {
		bitmap_to_arr32(arr, exp1, nbits);
		bitmap_from_arr32(bmap2, arr, nbits);
		expect_eq_bitmap(bmap2, exp1, nbits);

		next_bit = find_next_bit(bmap2,
				round_up(nbits, BITS_PER_LONG), nbits);
		if (next_bit < round_up(nbits, BITS_PER_LONG))
			pr_err("bitmap_copy_arr32(nbits == %d:"
				" tail is not safely cleared: %d\n",
				nbits, next_bit);

		if (nbits < EXP1_IN_BITS - 32)
			expect_eq_uint(arr[DIV_ROUND_UP(nbits, 32)],
								0xa5a5a5a5);
	}
}

static void noinline __init test_mem_optimisations(void)
{
	DECLARE_BITMAP(bmap1, 1024);
	DECLARE_BITMAP(bmap2, 1024);
	unsigned int start, nbits;

	for (start = 0; start < 1024; start += 8) {
		for (nbits = 0; nbits < 1024 - start; nbits += 8) {
			memset(bmap1, 0x5a, sizeof(bmap1));
			memset(bmap2, 0x5a, sizeof(bmap2));

			bitmap_set(bmap1, start, nbits);
			__bitmap_set(bmap2, start, nbits);
			if (!bitmap_equal(bmap1, bmap2, 1024)) {
				printk("set not equal %d %d\n", start, nbits);
				failed_tests++;
			}
			if (!__bitmap_equal(bmap1, bmap2, 1024)) {
				printk("set not __equal %d %d\n", start, nbits);
				failed_tests++;
			}

			bitmap_clear(bmap1, start, nbits);
			__bitmap_clear(bmap2, start, nbits);
			if (!bitmap_equal(bmap1, bmap2, 1024)) {
				printk("clear not equal %d %d\n", start, nbits);
				failed_tests++;
			}
			if (!__bitmap_equal(bmap1, bmap2, 1024)) {
				printk("clear not __equal %d %d\n", start,
									nbits);
				failed_tests++;
			}
		}
	}
}

static const unsigned char clump_exp[] __initconst = {
	0x01,	/* 1 bit set */
	0x02,	/* non-edge 1 bit set */
	0x00,	/* zero bits set */
	0x38,	/* 3 bits set across 4-bit boundary */
	0x38,	/* Repeated clump */
	0x0F,	/* 4 bits set */
	0xFF,	/* all bits set */
	0x05,	/* non-adjacent 2 bits set */
};

static void __init test_for_each_set_clump8(void)
{
#define CLUMP_EXP_NUMBITS 64
	DECLARE_BITMAP(bits, CLUMP_EXP_NUMBITS);
	unsigned int start;
	unsigned long clump;

	/* set bitmap to test case */
	bitmap_zero(bits, CLUMP_EXP_NUMBITS);
	bitmap_set(bits, 0, 1);		/* 0x01 */
	bitmap_set(bits, 9, 1);		/* 0x02 */
	bitmap_set(bits, 27, 3);	/* 0x28 */
	bitmap_set(bits, 35, 3);	/* 0x28 */
	bitmap_set(bits, 40, 4);	/* 0x0F */
	bitmap_set(bits, 48, 8);	/* 0xFF */
	bitmap_set(bits, 56, 1);	/* 0x05 - part 1 */
	bitmap_set(bits, 58, 1);	/* 0x05 - part 2 */

	for_each_set_clump8(start, clump, bits, CLUMP_EXP_NUMBITS)
		expect_eq_clump8(start, CLUMP_EXP_NUMBITS, clump_exp, &clump);
}

struct test_bitmap_cut {
	unsigned int first;
	unsigned int cut;
	unsigned int nbits;
	unsigned long in[4];
	unsigned long expected[4];
};

static struct test_bitmap_cut test_cut[] = {
	{  0,  0,  8, { 0x0000000aUL, }, { 0x0000000aUL, }, },
	{  0,  0, 32, { 0xdadadeadUL, }, { 0xdadadeadUL, }, },
	{  0,  3,  8, { 0x000000aaUL, }, { 0x00000015UL, }, },
	{  3,  3,  8, { 0x000000aaUL, }, { 0x00000012UL, }, },
	{  0,  1, 32, { 0xa5a5a5a5UL, }, { 0x52d2d2d2UL, }, },
	{  0,  8, 32, { 0xdeadc0deUL, }, { 0x00deadc0UL, }, },
	{  1,  1, 32, { 0x5a5a5a5aUL, }, { 0x2d2d2d2cUL, }, },
	{  0, 15, 32, { 0xa5a5a5a5UL, }, { 0x00014b4bUL, }, },
	{  0, 16, 32, { 0xa5a5a5a5UL, }, { 0x0000a5a5UL, }, },
	{ 15, 15, 32, { 0xa5a5a5a5UL, }, { 0x000125a5UL, }, },
	{ 15, 16, 32, { 0xa5a5a5a5UL, }, { 0x0000a5a5UL, }, },
	{ 16, 15, 32, { 0xa5a5a5a5UL, }, { 0x0001a5a5UL, }, },

	{ BITS_PER_LONG, BITS_PER_LONG, BITS_PER_LONG,
		{ 0xa5a5a5a5UL, 0xa5a5a5a5UL, },
		{ 0xa5a5a5a5UL, 0xa5a5a5a5UL, },
	},
	{ 1, BITS_PER_LONG - 1, BITS_PER_LONG,
		{ 0xa5a5a5a5UL, 0xa5a5a5a5UL, },
		{ 0x00000001UL, 0x00000001UL, },
	},

	{ 0, BITS_PER_LONG * 2, BITS_PER_LONG * 2 + 1,
		{ 0xa5a5a5a5UL, 0x00000001UL, 0x00000001UL, 0x00000001UL },
		{ 0x00000001UL, },
	},
	{ 16, BITS_PER_LONG * 2 + 1, BITS_PER_LONG * 2 + 1 + 16,
		{ 0x0000ffffUL, 0x5a5a5a5aUL, 0x5a5a5a5aUL, 0x5a5a5a5aUL },
		{ 0x2d2dffffUL, },
	},
};

static void __init test_bitmap_cut(void)
{
	unsigned long b[5], *in = &b[1], *out = &b[0];	/* Partial overlap */
	int i;

	for (i = 0; i < ARRAY_SIZE(test_cut); i++) {
		struct test_bitmap_cut *t = &test_cut[i];

		memcpy(in, t->in, sizeof(t->in));

		bitmap_cut(out, in, t->first, t->cut, t->nbits);

		expect_eq_bitmap(t->expected, out, t->nbits);
	}
}

static void __init selftest(void)
{
	test_zero_clear();
	test_fill_set();
	test_copy();
	test_replace();
	test_bitmap_arr32();
	test_bitmap_parse();
	test_bitmap_parselist();
	test_mem_optimisations();
	test_for_each_set_clump8();
	test_bitmap_cut();
}

KSTM_MODULE_LOADERS(test_bitmap);
MODULE_AUTHOR("david decotigny <david.decotigny@googlers.com>");
MODULE_LICENSE("GPL");
Commit	Line	Data
09c434b8	1	// SPDX-License-Identifier: GPL-2.0-only
5fd003f5	2	/*
780ff33b	3	* Test cases for bitmap API.
5fd003f5 DD	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>
6ea86bdf	15	#include <linux/uaccess.h>
5fd003f5	16
6b1a4d5b TH	17	#include "../tools/testing/selftests/kselftest_module.h"
6b1a4d5b TH	18
4e89a787	19	KSTM_MODULE_GLOBALS();
5fd003f5 DD	20
	21	static char pbl_buffer[PAGE_SIZE] __initdata;
	22
c21dd8a7 AS	23	static 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	};
	38
	39	static const unsigned long exp2[] __initconst = {
	40	BITMAP_FROM_U64(0x3333333311111111ULL),
	41	BITMAP_FROM_U64(0xffffffff77777777ULL),
	42	};
5fd003f5	43
30544ed5 AS	44	/* Fibonacci sequence */
	45	static const unsigned long exp2_to_exp3_mask[] __initconst = {
	46	BITMAP_FROM_U64(0x008000020020212eULL),
	47	};
	48	/* exp3_0_1 = (exp2[0] & ~exp2_to_exp3_mask) \| (exp2[1] & exp2_to_exp3_mask) */
	49	static const unsigned long exp3_0_1[] __initconst = {
	50	BITMAP_FROM_U64(0x33b3333311313137ULL),
	51	};
	52	/* exp3_1_0 = (exp2[1] & ~exp2_to_exp3_mask) \| (exp2[0] & exp2_to_exp3_mask) */
	53	static const unsigned long exp3_1_0[] __initconst = {
	54	BITMAP_FROM_U64(0xff7fffff77575751ULL),
	55	};
	56
5fd003f5 DD	57	static bool __init
	58	__check_eq_uint(const char *srcfile, unsigned int line,
	59	const unsigned int exp_uint, unsigned int x)
	60	{
	61	if (exp_uint != x) {
3aa56885	62	pr_err("[%s:%u] expected %u, got %u\n",
5fd003f5 DD	63	srcfile, line, exp_uint, x);
	64	return false;
	65	}
	66	return true;
	67	}
	68
	69
	70	static bool __init
	71	__check_eq_bitmap(const char *srcfile, unsigned int line,
3aa56885 YN	72	const unsigned long exp_bmap, const unsigned long bmap,
3aa56885 YN	73	unsigned int nbits)
5fd003f5	74	{
5fd003f5 DD	75	if (!bitmap_equal(exp_bmap, bmap, nbits)) {
	76	pr_warn("[%s:%u] bitmaps contents differ: expected \"%pbl\", got \"%pbl\"\n",
	77	srcfile, line,
3aa56885	78	nbits, exp_bmap, nbits, bmap);
5fd003f5 DD	79	return false;
	80	}
	81	return true;
	82	}
	83
	84	static bool __init
	85	__check_eq_pbl(const char *srcfile, unsigned int line,
	86	const char *expected_pbl,
	87	const unsigned long *bitmap, unsigned int nbits)
	88	{
	89	snprintf(pbl_buffer, sizeof(pbl_buffer), "%*pbl", nbits, bitmap);
	90	if (strcmp(expected_pbl, pbl_buffer)) {
	91	pr_warn("[%s:%u] expected \"%s\", got \"%s\"\n",
	92	srcfile, line,
	93	expected_pbl, pbl_buffer);
	94	return false;
	95	}
	96	return true;
	97	}
	98
3aa56885 YN	99	static bool __init
	100	__check_eq_u32_array(const char *srcfile, unsigned int line,
	101	const u32 *exp_arr, unsigned int exp_len,
	102	const u32 *arr, unsigned int len) __used;
5fd003f5 DD	103	static bool __init
	104	__check_eq_u32_array(const char *srcfile, unsigned int line,
	105	const u32 *exp_arr, unsigned int exp_len,
	106	const u32 *arr, unsigned int len)
	107	{
	108	if (exp_len != len) {
	109	pr_warn("[%s:%u] array length differ: expected %u, got %u\n",
	110	srcfile, line,
	111	exp_len, len);
	112	return false;
	113	}
	114
	115	if (memcmp(exp_arr, arr, lensizeof(arr))) {
	116	pr_warn("[%s:%u] array contents differ\n", srcfile, line);
	117	print_hex_dump(KERN_WARNING, " exp: ", DUMP_PREFIX_OFFSET,
	118	32, 4, exp_arr, exp_lensizeof(exp_arr), false);
	119	print_hex_dump(KERN_WARNING, " got: ", DUMP_PREFIX_OFFSET,
	120	32, 4, arr, lensizeof(arr), false);
	121	return false;
	122	}
	123
	124	return true;
	125	}
	126
e4aa168d WBG	127	static bool __init __check_eq_clump8(const char *srcfile, unsigned int line,
	128	const unsigned int offset,
	129	const unsigned int size,
	130	const unsigned char *const clump_exp,
	131	const unsigned long *const clump)
	132	{
	133	unsigned long exp;
	134
	135	if (offset >= size) {
	136	pr_warn("[%s:%u] bit offset for clump out-of-bounds: expected less than %u, got %u\n",
	137	srcfile, line, size, offset);
	138	return false;
	139	}
	140
	141	exp = clump_exp[offset / 8];
	142	if (!exp) {
	143	pr_warn("[%s:%u] bit offset for zero clump: expected nonzero clump, got bit offset %u with clump value 0",
	144	srcfile, line, offset);
	145	return false;
	146	}
	147
	148	if (*clump != exp) {
	149	pr_warn("[%s:%u] expected clump value of 0x%lX, got clump value of 0x%lX",
	150	srcfile, line, exp, *clump);
	151	return false;
	152	}
	153
	154	return true;
	155	}
	156
5fd003f5 DD	157	#define __expect_eq(suffix, ...) \
	158	({ \
	159	int result = 0; \
	160	total_tests++; \
	161	if (!__check_eq_ ## suffix(__FILE__, __LINE__, \
	162	##__VA_ARGS__)) { \
	163	failed_tests++; \
	164	result = 1; \
	165	} \
	166	result; \
	167	})
	168
	169	#define expect_eq_uint(...) __expect_eq(uint, ##__VA_ARGS__)
	170	#define expect_eq_bitmap(...) __expect_eq(bitmap, ##__VA_ARGS__)
	171	#define expect_eq_pbl(...) __expect_eq(pbl, ##__VA_ARGS__)
	172	#define expect_eq_u32_array(...) __expect_eq(u32_array, ##__VA_ARGS__)
e4aa168d	173	#define expect_eq_clump8(...) __expect_eq(clump8, ##__VA_ARGS__)
5fd003f5	174
ee3527bd AS	175	static void __init test_zero_clear(void)
	176	{
	177	DECLARE_BITMAP(bmap, 1024);
	178
	179	/* Known way to set all bits */
	180	memset(bmap, 0xff, 128);
	181
	182	expect_eq_pbl("0-22", bmap, 23);
	183	expect_eq_pbl("0-1023", bmap, 1024);
	184
	185	/* single-word bitmaps */
	186	bitmap_clear(bmap, 0, 9);
	187	expect_eq_pbl("9-1023", bmap, 1024);
	188
	189	bitmap_zero(bmap, 35);
	190	expect_eq_pbl("64-1023", bmap, 1024);
	191
	192	/* cross boundaries operations */
	193	bitmap_clear(bmap, 79, 19);
	194	expect_eq_pbl("64-78,98-1023", bmap, 1024);
	195
	196	bitmap_zero(bmap, 115);
	197	expect_eq_pbl("128-1023", bmap, 1024);
	198
	199	/* Zeroing entire area */
	200	bitmap_zero(bmap, 1024);
	201	expect_eq_pbl("", bmap, 1024);
	202	}
	203
978f369c AS	204	static void __init test_fill_set(void)
	205	{
	206	DECLARE_BITMAP(bmap, 1024);
	207
	208	/* Known way to clear all bits */
	209	memset(bmap, 0x00, 128);
	210
	211	expect_eq_pbl("", bmap, 23);
	212	expect_eq_pbl("", bmap, 1024);
	213
	214	/* single-word bitmaps */
	215	bitmap_set(bmap, 0, 9);
	216	expect_eq_pbl("0-8", bmap, 1024);
	217
	218	bitmap_fill(bmap, 35);
	219	expect_eq_pbl("0-63", bmap, 1024);
	220
	221	/* cross boundaries operations */
	222	bitmap_set(bmap, 79, 19);
	223	expect_eq_pbl("0-63,79-97", bmap, 1024);
	224
	225	bitmap_fill(bmap, 115);
	226	expect_eq_pbl("0-127", bmap, 1024);
	227
	228	/* Zeroing entire area */
	229	bitmap_fill(bmap, 1024);
	230	expect_eq_pbl("0-1023", bmap, 1024);
	231	}
	232
fe81814c	233	static void __init test_copy(void)
5fd003f5 DD	234	{
	235	DECLARE_BITMAP(bmap1, 1024);
	236	DECLARE_BITMAP(bmap2, 1024);
	237
	238	bitmap_zero(bmap1, 1024);
	239	bitmap_zero(bmap2, 1024);
	240
	241	/* single-word bitmaps */
fe81814c	242	bitmap_set(bmap1, 0, 19);
5fd003f5 DD	243	bitmap_copy(bmap2, bmap1, 23);
	244	expect_eq_pbl("0-18", bmap2, 1024);
	245
fe81814c	246	bitmap_set(bmap2, 0, 23);
5fd003f5 DD	247	bitmap_copy(bmap2, bmap1, 23);
	248	expect_eq_pbl("0-18", bmap2, 1024);
	249
5fd003f5	250	/* multi-word bitmaps */
fe81814c	251	bitmap_set(bmap1, 0, 109);
5fd003f5 DD	252	bitmap_copy(bmap2, bmap1, 1024);
	253	expect_eq_pbl("0-108", bmap2, 1024);
	254
	255	bitmap_fill(bmap2, 1024);
5fd003f5 DD	256	bitmap_copy(bmap2, bmap1, 1024);
	257	expect_eq_pbl("0-108", bmap2, 1024);
	258
	259	/* the following tests assume a 32- or 64-bit arch (even 128b
	260	* if we care)
	261	*/
	262
	263	bitmap_fill(bmap2, 1024);
	264	bitmap_copy(bmap2, bmap1, 109); /* ... but 0-padded til word length */
	265	expect_eq_pbl("0-108,128-1023", bmap2, 1024);
	266
	267	bitmap_fill(bmap2, 1024);
	268	bitmap_copy(bmap2, bmap1, 97); /* ... but aligned on word length */
	269	expect_eq_pbl("0-108,128-1023", bmap2, 1024);
5fd003f5 DD	270	}
5fd003f5 DD	271
30544ed5 AS	272	#define EXP2_IN_BITS (sizeof(exp2) * 8)
	273
	274	static void __init test_replace(void)
	275	{
	276	unsigned int nbits = 64;
69334ca5	277	unsigned int nlongs = DIV_ROUND_UP(nbits, BITS_PER_LONG);
30544ed5 AS	278	DECLARE_BITMAP(bmap, 1024);
30544ed5 AS	279
caa7f776 AS	280	BUILD_BUG_ON(EXP2_IN_BITS < nbits * 2);
caa7f776 AS	281
30544ed5	282	bitmap_zero(bmap, 1024);
69334ca5	283	bitmap_replace(bmap, &exp2[0 * nlongs], &exp2[1 * nlongs], exp2_to_exp3_mask, nbits);
30544ed5 AS	284	expect_eq_bitmap(bmap, exp3_0_1, nbits);
	285
	286	bitmap_zero(bmap, 1024);
69334ca5	287	bitmap_replace(bmap, &exp2[1 * nlongs], &exp2[0 * nlongs], exp2_to_exp3_mask, nbits);
30544ed5 AS	288	expect_eq_bitmap(bmap, exp3_1_0, nbits);
	289
	290	bitmap_fill(bmap, 1024);
69334ca5	291	bitmap_replace(bmap, &exp2[0 * nlongs], &exp2[1 * nlongs], exp2_to_exp3_mask, nbits);
30544ed5 AS	292	expect_eq_bitmap(bmap, exp3_0_1, nbits);
	293
	294	bitmap_fill(bmap, 1024);
69334ca5	295	bitmap_replace(bmap, &exp2[1 * nlongs], &exp2[0 * nlongs], exp2_to_exp3_mask, nbits);
30544ed5 AS	296	expect_eq_bitmap(bmap, exp3_1_0, nbits);
	297	}
	298
7eb2e94e YN	299	#define PARSE_TIME 0x1
7eb2e94e YN	300	#define NO_LEN 0x2
6df0d464 YN	301
	302	struct test_bitmap_parselist{
	303	const int errno;
	304	const char *in;
	305	const unsigned long *expected;
	306	const int nbits;
	307	const int flags;
	308	};
	309
6df0d464	310	static const struct test_bitmap_parselist parselist_tests[] __initconst = {
60ef6900 YN	311	#define step (sizeof(u64) / sizeof(unsigned long))
60ef6900 YN	312
0ee312e3 AS	313	{0, "0", &exp1[0], 8, 0},
	314	{0, "1", &exp1[1 * step], 8, 0},
	315	{0, "0-15", &exp1[2 * step], 32, 0},
	316	{0, "16-31", &exp1[3 * step], 32, 0},
	317	{0, "0-31:1/2", &exp1[4 * step], 32, 0},
	318	{0, "1-31:1/2", &exp1[5 * step], 32, 0},
	319	{0, "0-31:1/4", &exp1[6 * step], 32, 0},
	320	{0, "1-31:1/4", &exp1[7 * step], 32, 0},
	321	{0, "0-31:4/4", &exp1[8 * step], 32, 0},
	322	{0, "1-31:4/4", &exp1[9 * step], 32, 0},
	323	{0, "0-31:1/4,32-63:2/4", &exp1[10 * step], 64, 0},
	324	{0, "0-31:3/4,32-63:4/4", &exp1[11 * step], 64, 0},
	325	{0, " ,, 0-31:3/4 ,, 32-63:4/4 ,, ", &exp1[11 * step], 64, 0},
6df0d464 YN	326
	327	{0, "0-31:1/4,32-63:2/4,64-95:3/4,96-127:4/4", exp2, 128, 0},
	328
	329	{0, "0-2047:128/256", NULL, 2048, PARSE_TIME},
	330
0ee312e3 AS	331	{0, "", &exp1[12 * step], 8, 0},
	332	{0, "\n", &exp1[12 * step], 8, 0},
	333	{0, ",, ,, , , ,", &exp1[12 * step], 8, 0},
	334	{0, " , ,, , , ", &exp1[12 * step], 8, 0},
	335	{0, " , ,, , , \n", &exp1[12 * step], 8, 0},
a4ab5050	336
6df0d464 YN	337	{-EINVAL, "-1", NULL, 8, 0},
	338	{-EINVAL, "-0", NULL, 8, 0},
	339	{-EINVAL, "10-1", NULL, 8, 0},
6fef5905 PG	340	{-ERANGE, "8-8", NULL, 8, 0},
6fef5905 PG	341	{-ERANGE, "0-31", NULL, 8, 0},
494215fb PG	342	{-EINVAL, "0-31:", NULL, 32, 0},
	343	{-EINVAL, "0-31:0", NULL, 32, 0},
	344	{-EINVAL, "0-31:0/", NULL, 32, 0},
	345	{-EINVAL, "0-31:0/0", NULL, 32, 0},
	346	{-EINVAL, "0-31:1/0", NULL, 32, 0},
	347	{-EINVAL, "0-31:10/1", NULL, 32, 0},
a4ab5050 YN	348	{-EOVERFLOW, "0-98765432123456789:10/1", NULL, 8, 0},
	349
	350	{-EINVAL, "a-31", NULL, 8, 0},
	351	{-EINVAL, "0-a1", NULL, 8, 0},
	352	{-EINVAL, "a-31:10/1", NULL, 8, 0},
	353	{-EINVAL, "0-31:a/1", NULL, 8, 0},
	354	{-EINVAL, "0-\n", NULL, 8, 0},
54224044	355
6df0d464 YN	356	};
6df0d464 YN	357
81b1e242	358	static void __init test_bitmap_parselist(void)
6df0d464 YN	359	{
	360	int i;
	361	int err;
0c2111a5	362	ktime_t time;
6df0d464 YN	363	DECLARE_BITMAP(bmap, 2048);
	364
	365	for (i = 0; i < ARRAY_SIZE(parselist_tests); i++) {
	366	#define ptest parselist_tests[i]
	367
81b1e242 CH	368	time = ktime_get();
	369	err = bitmap_parselist(ptest.in, bmap, ptest.nbits);
	370	time = ktime_get() - time;
6df0d464 YN	371
6df0d464 YN	372	if (err != ptest.errno) {
81b1e242 CH	373	pr_err("parselist: %d: input is %s, errno is %d, expected %d\n",
81b1e242 CH	374	i, ptest.in, err, ptest.errno);
6df0d464 YN	375	continue;
	376	}
	377
	378	if (!err && ptest.expected
	379	&& !__bitmap_equal(bmap, ptest.expected, ptest.nbits)) {
81b1e242 CH	380	pr_err("parselist: %d: input is %s, result is 0x%lx, expected 0x%lx\n",
81b1e242 CH	381	i, ptest.in, bmap[0],
6ea86bdf	382	*ptest.expected);
6df0d464 YN	383	continue;
	384	}
	385
	386	if (ptest.flags & PARSE_TIME)
81b1e242 CH	387	pr_err("parselist: %d: input is '%s' OK, Time: %llu\n",
81b1e242 CH	388	i, ptest.in, time);
54224044 AS	389
54224044 AS	390	#undef ptest
6df0d464 YN	391	}
	392	}
	393
7eb2e94e YN	394	static const unsigned long parse_test[] __initconst = {
	395	BITMAP_FROM_U64(0),
	396	BITMAP_FROM_U64(1),
	397	BITMAP_FROM_U64(0xdeadbeef),
	398	BITMAP_FROM_U64(0x100000000ULL),
	399	};
	400
	401	static const unsigned long parse_test2[] __initconst = {
	402	BITMAP_FROM_U64(0x100000000ULL), BITMAP_FROM_U64(0xdeadbeef),
	403	BITMAP_FROM_U64(0x100000000ULL), BITMAP_FROM_U64(0xbaadf00ddeadbeef),
	404	BITMAP_FROM_U64(0x100000000ULL), BITMAP_FROM_U64(0x0badf00ddeadbeef),
	405	};
	406
	407	static const struct test_bitmap_parselist parse_tests[] __initconst = {
809e308f YN	408	{0, "", &parse_test[0 * step], 32, 0},
809e308f YN	409	{0, " ", &parse_test[0 * step], 32, 0},
7eb2e94e	410	{0, "0", &parse_test[0 * step], 32, 0},
809e308f	411	{0, "0\n", &parse_test[0 * step], 32, 0},
7eb2e94e YN	412	{0, "1", &parse_test[1 * step], 32, 0},
	413	{0, "deadbeef", &parse_test[2 * step], 32, 0},
	414	{0, "1,0", &parse_test[3 * step], 33, 0},
809e308f	415	{0, "deadbeef,\n,0,1", &parse_test[2 * step], 96, 0},
7eb2e94e YN	416
	417	{0, "deadbeef,1,0", &parse_test2[0 * 2 * step], 96, 0},
	418	{0, "baadf00d,deadbeef,1,0", &parse_test2[1 * 2 * step], 128, 0},
	419	{0, "badf00d,deadbeef,1,0", &parse_test2[2 * 2 * step], 124, 0},
809e308f YN	420	{0, "badf00d,deadbeef,1,0", &parse_test2[2 * 2 * step], 124, NO_LEN},
	421	{0, " badf00d,deadbeef,1,0 ", &parse_test2[2 * 2 * step], 124, 0},
	422	{0, " , badf00d,deadbeef,1,0 , ", &parse_test2[2 * 2 * step], 124, 0},
	423	{0, " , badf00d, ,, ,,deadbeef,1,0 , ", &parse_test2[2 * 2 * step], 124, 0},
7eb2e94e YN	424
	425	{-EINVAL, "goodfood,deadbeef,1,0", NULL, 128, 0},
	426	{-EOVERFLOW, "3,0", NULL, 33, 0},
	427	{-EOVERFLOW, "123badf00d,deadbeef,1,0", NULL, 128, 0},
	428	{-EOVERFLOW, "badf00d,deadbeef,1,0", NULL, 90, 0},
	429	{-EOVERFLOW, "fbadf00d,deadbeef,1,0", NULL, 95, 0},
	430	{-EOVERFLOW, "badf00d,deadbeef,1,0", NULL, 100, 0},
	431	#undef step
	432	};
	433
81b1e242	434	static void __init test_bitmap_parse(void)
7eb2e94e YN	435	{
	436	int i;
	437	int err;
	438	ktime_t time;
	439	DECLARE_BITMAP(bmap, 2048);
7eb2e94e YN	440
	441	for (i = 0; i < ARRAY_SIZE(parse_tests); i++) {
	442	struct test_bitmap_parselist test = parse_tests[i];
81b1e242	443	size_t len = test.flags & NO_LEN ? UINT_MAX : strlen(test.in);
7eb2e94e	444
81b1e242 CH	445	time = ktime_get();
	446	err = bitmap_parse(test.in, len, bmap, test.nbits);
	447	time = ktime_get() - time;
7eb2e94e YN	448
7eb2e94e YN	449	if (err != test.errno) {
81b1e242 CH	450	pr_err("parse: %d: input is %s, errno is %d, expected %d\n",
81b1e242 CH	451	i, test.in, err, test.errno);
7eb2e94e YN	452	continue;
	453	}
	454
	455	if (!err && test.expected
	456	&& !__bitmap_equal(bmap, test.expected, test.nbits)) {
81b1e242 CH	457	pr_err("parse: %d: input is %s, result is 0x%lx, expected 0x%lx\n",
81b1e242 CH	458	i, test.in, bmap[0],
7eb2e94e YN	459	*test.expected);
	460	continue;
	461	}
	462
	463	if (test.flags & PARSE_TIME)
81b1e242 CH	464	pr_err("parse: %d: input is '%s' OK, Time: %llu\n",
81b1e242 CH	465	i, test.in, time);
7eb2e94e YN	466	}
	467	}
	468
0ee312e3	469	#define EXP1_IN_BITS (sizeof(exp1) * 8)
f6f66c1b	470
3aa56885	471	static void __init test_bitmap_arr32(void)
5fd003f5	472	{
f6f66c1b	473	unsigned int nbits, next_bit;
a4881d1c AS	474	u32 arr[EXP1_IN_BITS / 32];
a4881d1c AS	475	DECLARE_BITMAP(bmap2, EXP1_IN_BITS);
3aa56885 YN	476
	477	memset(arr, 0xa5, sizeof(arr));
	478
a4881d1c	479	for (nbits = 0; nbits < EXP1_IN_BITS; ++nbits) {
0ee312e3	480	bitmap_to_arr32(arr, exp1, nbits);
3aa56885	481	bitmap_from_arr32(bmap2, arr, nbits);
0ee312e3	482	expect_eq_bitmap(bmap2, exp1, nbits);
3aa56885 YN	483
	484	next_bit = find_next_bit(bmap2,
	485	round_up(nbits, BITS_PER_LONG), nbits);
	486	if (next_bit < round_up(nbits, BITS_PER_LONG))
	487	pr_err("bitmap_copy_arr32(nbits == %d:"
	488	" tail is not safely cleared: %d\n",
	489	nbits, next_bit);
	490
a4881d1c	491	if (nbits < EXP1_IN_BITS - 32)
3aa56885 YN	492	expect_eq_uint(arr[DIV_ROUND_UP(nbits, 32)],
3aa56885 YN	493	0xa5a5a5a5);
5fd003f5 DD	494	}
	495	}
	496
3cc78125 MW	497	static void noinline __init test_mem_optimisations(void)
	498	{
	499	DECLARE_BITMAP(bmap1, 1024);
	500	DECLARE_BITMAP(bmap2, 1024);
	501	unsigned int start, nbits;
	502
	503	for (start = 0; start < 1024; start += 8) {
3cc78125	504	for (nbits = 0; nbits < 1024 - start; nbits += 8) {
1e3054b9 MW	505	memset(bmap1, 0x5a, sizeof(bmap1));
	506	memset(bmap2, 0x5a, sizeof(bmap2));
	507
3cc78125 MW	508	bitmap_set(bmap1, start, nbits);
3cc78125 MW	509	__bitmap_set(bmap2, start, nbits);
1e3054b9	510	if (!bitmap_equal(bmap1, bmap2, 1024)) {
3cc78125	511	printk("set not equal %d %d\n", start, nbits);
1e3054b9 MW	512	failed_tests++;
	513	}
	514	if (!__bitmap_equal(bmap1, bmap2, 1024)) {
3cc78125	515	printk("set not __equal %d %d\n", start, nbits);
1e3054b9 MW	516	failed_tests++;
1e3054b9 MW	517	}
3cc78125 MW	518
	519	bitmap_clear(bmap1, start, nbits);
	520	__bitmap_clear(bmap2, start, nbits);
1e3054b9	521	if (!bitmap_equal(bmap1, bmap2, 1024)) {
3cc78125	522	printk("clear not equal %d %d\n", start, nbits);
1e3054b9 MW	523	failed_tests++;
	524	}
	525	if (!__bitmap_equal(bmap1, bmap2, 1024)) {
3cc78125 MW	526	printk("clear not __equal %d %d\n", start,
3cc78125 MW	527	nbits);
1e3054b9 MW	528	failed_tests++;
1e3054b9 MW	529	}
3cc78125 MW	530	}
	531	}
	532	}
	533
e4aa168d WBG	534	static const unsigned char clump_exp[] __initconst = {
	535	0x01, /* 1 bit set */
	536	0x02, /* non-edge 1 bit set */
	537	0x00, /* zero bits set */
	538	0x38, /* 3 bits set across 4-bit boundary */
	539	0x38, /* Repeated clump */
	540	0x0F, /* 4 bits set */
	541	0xFF, /* all bits set */
	542	0x05, /* non-adjacent 2 bits set */
	543	};
	544
	545	static void __init test_for_each_set_clump8(void)
	546	{
	547	#define CLUMP_EXP_NUMBITS 64
	548	DECLARE_BITMAP(bits, CLUMP_EXP_NUMBITS);
	549	unsigned int start;
	550	unsigned long clump;
	551
	552	/* set bitmap to test case */
	553	bitmap_zero(bits, CLUMP_EXP_NUMBITS);
	554	bitmap_set(bits, 0, 1); /* 0x01 */
	555	bitmap_set(bits, 9, 1); /* 0x02 */
	556	bitmap_set(bits, 27, 3); /* 0x28 */
	557	bitmap_set(bits, 35, 3); /* 0x28 */
	558	bitmap_set(bits, 40, 4); /* 0x0F */
	559	bitmap_set(bits, 48, 8); /* 0xFF */
	560	bitmap_set(bits, 56, 1); /* 0x05 - part 1 */
	561	bitmap_set(bits, 58, 1); /* 0x05 - part 2 */
	562
	563	for_each_set_clump8(start, clump, bits, CLUMP_EXP_NUMBITS)
	564	expect_eq_clump8(start, CLUMP_EXP_NUMBITS, clump_exp, &clump);
	565	}
	566
bcb32a1d SB	567	struct test_bitmap_cut {
	568	unsigned int first;
	569	unsigned int cut;
	570	unsigned int nbits;
	571	unsigned long in[4];
	572	unsigned long expected[4];
	573	};
	574
	575	static struct test_bitmap_cut test_cut[] = {
	576	{ 0, 0, 8, { 0x0000000aUL, }, { 0x0000000aUL, }, },
	577	{ 0, 0, 32, { 0xdadadeadUL, }, { 0xdadadeadUL, }, },
	578	{ 0, 3, 8, { 0x000000aaUL, }, { 0x00000015UL, }, },
	579	{ 3, 3, 8, { 0x000000aaUL, }, { 0x00000012UL, }, },
	580	{ 0, 1, 32, { 0xa5a5a5a5UL, }, { 0x52d2d2d2UL, }, },
	581	{ 0, 8, 32, { 0xdeadc0deUL, }, { 0x00deadc0UL, }, },
	582	{ 1, 1, 32, { 0x5a5a5a5aUL, }, { 0x2d2d2d2cUL, }, },
	583	{ 0, 15, 32, { 0xa5a5a5a5UL, }, { 0x00014b4bUL, }, },
	584	{ 0, 16, 32, { 0xa5a5a5a5UL, }, { 0x0000a5a5UL, }, },
	585	{ 15, 15, 32, { 0xa5a5a5a5UL, }, { 0x000125a5UL, }, },
	586	{ 15, 16, 32, { 0xa5a5a5a5UL, }, { 0x0000a5a5UL, }, },
	587	{ 16, 15, 32, { 0xa5a5a5a5UL, }, { 0x0001a5a5UL, }, },
	588
	589	{ BITS_PER_LONG, BITS_PER_LONG, BITS_PER_LONG,
	590	{ 0xa5a5a5a5UL, 0xa5a5a5a5UL, },
	591	{ 0xa5a5a5a5UL, 0xa5a5a5a5UL, },
	592	},
	593	{ 1, BITS_PER_LONG - 1, BITS_PER_LONG,
	594	{ 0xa5a5a5a5UL, 0xa5a5a5a5UL, },
	595	{ 0x00000001UL, 0x00000001UL, },
	596	},
	597
	598	{ 0, BITS_PER_LONG * 2, BITS_PER_LONG * 2 + 1,
	599	{ 0xa5a5a5a5UL, 0x00000001UL, 0x00000001UL, 0x00000001UL },
	600	{ 0x00000001UL, },
	601	},
	602	{ 16, BITS_PER_LONG * 2 + 1, BITS_PER_LONG * 2 + 1 + 16,
	603	{ 0x0000ffffUL, 0x5a5a5a5aUL, 0x5a5a5a5aUL, 0x5a5a5a5aUL },
	604	{ 0x2d2dffffUL, },
	605	},
	606	};
	607
	608	static void __init test_bitmap_cut(void)
	609	{
	610	unsigned long b[5], in = &b[1], out = &b[0]; /* Partial overlap */
	611	int i;
	612
	613	for (i = 0; i < ARRAY_SIZE(test_cut); i++) {
	614	struct test_bitmap_cut *t = &test_cut[i];
	615
	616	memcpy(in, t->in, sizeof(t->in));
	617
	618	bitmap_cut(out, in, t->first, t->cut, t->nbits);
	619
	620	expect_eq_bitmap(t->expected, out, t->nbits);
	621	}
	622	}
	623
6b1a4d5b	624	static void __init selftest(void)
5fd003f5	625	{
ee3527bd	626	test_zero_clear();
978f369c	627	test_fill_set();
fe81814c	628	test_copy();
30544ed5	629	test_replace();
3aa56885	630	test_bitmap_arr32();
7eb2e94e	631	test_bitmap_parse();
6df0d464	632	test_bitmap_parselist();
3cc78125	633	test_mem_optimisations();
e4aa168d	634	test_for_each_set_clump8();
bcb32a1d	635	test_bitmap_cut();
5fd003f5 DD	636	}
5fd003f5 DD	637
6b1a4d5b	638	KSTM_MODULE_LOADERS(test_bitmap);
5fd003f5 DD	639	MODULE_AUTHOR("david decotigny <david.decotigny@googlers.com>");
5fd003f5 DD	640	MODULE_LICENSE("GPL");