[linux-2.6-block.git] / lib / find_bit_benchmark.c

// SPDX-License-Identifier: GPL-2.0-only
/*
 * Test for find_*_bit functions.
 *
 * Copyright (c) 2017 Cavium.
 */

/*
 * find_bit functions are widely used in kernel, so the successful boot
 * is good enough test for correctness.
 *
 * This test is focused on performance of traversing bitmaps. Two typical
 * scenarios are reproduced:
 * - randomly filled bitmap with approximately equal number of set and
 *   cleared bits;
 * - sparse bitmap with few set bits at random positions.
 */

#include <linux/bitops.h>
#include <linux/kernel.h>
#include <linux/list.h>
#include <linux/module.h>
#include <linux/printk.h>
#include <linux/random.h>

#define BITMAP_LEN	(4096UL * 8 * 10)
#define SPARSE		500

static DECLARE_BITMAP(bitmap, BITMAP_LEN) __initdata;
static DECLARE_BITMAP(bitmap2, BITMAP_LEN) __initdata;

/*
 * This is Schlemiel the Painter's algorithm. It should be called after
 * all other tests for the same bitmap because it sets all bits of bitmap to 1.
 */
static int __init test_find_first_bit(void *bitmap, unsigned long len)
{
	unsigned long i, cnt;
	ktime_t time;

	time = ktime_get();
	for (cnt = i = 0; i < len; cnt++) {
		i = find_first_bit(bitmap, len);
		__clear_bit(i, bitmap);
	}
	time = ktime_get() - time;
	pr_err("find_first_bit:     %18llu ns, %6ld iterations\n", time, cnt);

	return 0;
}

static int __init test_find_next_bit(const void *bitmap, unsigned long len)
{
	unsigned long i, cnt;
	ktime_t time;

	time = ktime_get();
	for (cnt = i = 0; i < BITMAP_LEN; cnt++)
		i = find_next_bit(bitmap, BITMAP_LEN, i) + 1;
	time = ktime_get() - time;
	pr_err("find_next_bit:      %18llu ns, %6ld iterations\n", time, cnt);

	return 0;
}

static int __init test_find_next_zero_bit(const void *bitmap, unsigned long len)
{
	unsigned long i, cnt;
	ktime_t time;

	time = ktime_get();
	for (cnt = i = 0; i < BITMAP_LEN; cnt++)
		i = find_next_zero_bit(bitmap, len, i) + 1;
	time = ktime_get() - time;
	pr_err("find_next_zero_bit: %18llu ns, %6ld iterations\n", time, cnt);

	return 0;
}

static int __init test_find_last_bit(const void *bitmap, unsigned long len)
{
	unsigned long l, cnt = 0;
	ktime_t time;

	time = ktime_get();
	do {
		cnt++;
		l = find_last_bit(bitmap, len);
		if (l >= len)
			break;
		len = l;
	} while (len);
	time = ktime_get() - time;
	pr_err("find_last_bit:      %18llu ns, %6ld iterations\n", time, cnt);

	return 0;
}

static int __init test_find_next_and_bit(const void *bitmap,
		const void *bitmap2, unsigned long len)
{
	unsigned long i, cnt;
	ktime_t time;

	time = ktime_get();
	for (cnt = i = 0; i < BITMAP_LEN; cnt++)
		i = find_next_and_bit(bitmap, bitmap2, BITMAP_LEN, i + 1);
	time = ktime_get() - time;
	pr_err("find_next_and_bit:  %18llu ns, %6ld iterations\n", time, cnt);

	return 0;
}

static int __init find_bit_test(void)
{
	unsigned long nbits = BITMAP_LEN / SPARSE;

	pr_err("\nStart testing find_bit() with random-filled bitmap\n");

	get_random_bytes(bitmap, sizeof(bitmap));
	get_random_bytes(bitmap2, sizeof(bitmap2));

	test_find_next_bit(bitmap, BITMAP_LEN);
	test_find_next_zero_bit(bitmap, BITMAP_LEN);
	test_find_last_bit(bitmap, BITMAP_LEN);

	/*
	 * test_find_first_bit() may take some time, so
	 * traverse only part of bitmap to avoid soft lockup.
	 */
	test_find_first_bit(bitmap, BITMAP_LEN / 10);
	test_find_next_and_bit(bitmap, bitmap2, BITMAP_LEN);

	pr_err("\nStart testing find_bit() with sparse bitmap\n");

	bitmap_zero(bitmap, BITMAP_LEN);
	bitmap_zero(bitmap2, BITMAP_LEN);

	while (nbits--) {
		__set_bit(prandom_u32() % BITMAP_LEN, bitmap);
		__set_bit(prandom_u32() % BITMAP_LEN, bitmap2);
	}

	test_find_next_bit(bitmap, BITMAP_LEN);
	test_find_next_zero_bit(bitmap, BITMAP_LEN);
	test_find_last_bit(bitmap, BITMAP_LEN);
	test_find_first_bit(bitmap, BITMAP_LEN);
	test_find_next_and_bit(bitmap, bitmap2, BITMAP_LEN);

	/*
	 * Everything is OK. Return error just to let user run benchmark
	 * again without annoying rmmod.
	 */
	return -EINVAL;
}
module_init(find_bit_test);

MODULE_LICENSE("GPL");
Commit	Line	Data
5b497af4	1	// SPDX-License-Identifier: GPL-2.0-only
4441fca0 YN	2	/*
	3	* Test for find_*_bit functions.
	4	*
	5	* Copyright (c) 2017 Cavium.
4441fca0 YN	6	*/
	7
	8	/*
	9	* find_bit functions are widely used in kernel, so the successful boot
	10	* is good enough test for correctness.
	11	*
	12	* This test is focused on performance of traversing bitmaps. Two typical
	13	* scenarios are reproduced:
	14	* - randomly filled bitmap with approximately equal number of set and
	15	* cleared bits;
	16	* - sparse bitmap with few set bits at random positions.
	17	*/
	18
	19	#include <linux/bitops.h>
	20	#include <linux/kernel.h>
	21	#include <linux/list.h>
	22	#include <linux/module.h>
	23	#include <linux/printk.h>
	24	#include <linux/random.h>
	25
	26	#define BITMAP_LEN (4096UL * 8 * 10)
	27	#define SPARSE 500
	28
	29	static DECLARE_BITMAP(bitmap, BITMAP_LEN) __initdata;
0ade34c3	30	static DECLARE_BITMAP(bitmap2, BITMAP_LEN) __initdata;
4441fca0 YN	31
	32	/*
	33	* This is Schlemiel the Painter's algorithm. It should be called after
	34	* all other tests for the same bitmap because it sets all bits of bitmap to 1.
	35	*/
	36	static int __init test_find_first_bit(void *bitmap, unsigned long len)
	37	{
	38	unsigned long i, cnt;
15ff67bf	39	ktime_t time;
4441fca0	40
15ff67bf	41	time = ktime_get();
4441fca0 YN	42	for (cnt = i = 0; i < len; cnt++) {
	43	i = find_first_bit(bitmap, len);
	44	__clear_bit(i, bitmap);
	45	}
15ff67bf YN	46	time = ktime_get() - time;
15ff67bf YN	47	pr_err("find_first_bit: %18llu ns, %6ld iterations\n", time, cnt);
4441fca0 YN	48
	49	return 0;
	50	}
	51
	52	static int __init test_find_next_bit(const void *bitmap, unsigned long len)
	53	{
	54	unsigned long i, cnt;
15ff67bf	55	ktime_t time;
4441fca0	56
15ff67bf	57	time = ktime_get();
4441fca0 YN	58	for (cnt = i = 0; i < BITMAP_LEN; cnt++)
4441fca0 YN	59	i = find_next_bit(bitmap, BITMAP_LEN, i) + 1;
15ff67bf YN	60	time = ktime_get() - time;
15ff67bf YN	61	pr_err("find_next_bit: %18llu ns, %6ld iterations\n", time, cnt);
4441fca0 YN	62
	63	return 0;
	64	}
	65
	66	static int __init test_find_next_zero_bit(const void *bitmap, unsigned long len)
	67	{
	68	unsigned long i, cnt;
15ff67bf	69	ktime_t time;
4441fca0	70
15ff67bf	71	time = ktime_get();
4441fca0 YN	72	for (cnt = i = 0; i < BITMAP_LEN; cnt++)
4441fca0 YN	73	i = find_next_zero_bit(bitmap, len, i) + 1;
15ff67bf YN	74	time = ktime_get() - time;
15ff67bf YN	75	pr_err("find_next_zero_bit: %18llu ns, %6ld iterations\n", time, cnt);
4441fca0 YN	76
	77	return 0;
	78	}
	79
	80	static int __init test_find_last_bit(const void *bitmap, unsigned long len)
	81	{
	82	unsigned long l, cnt = 0;
15ff67bf	83	ktime_t time;
4441fca0	84
15ff67bf	85	time = ktime_get();
4441fca0 YN	86	do {
	87	cnt++;
	88	l = find_last_bit(bitmap, len);
	89	if (l >= len)
	90	break;
	91	len = l;
	92	} while (len);
15ff67bf YN	93	time = ktime_get() - time;
15ff67bf YN	94	pr_err("find_last_bit: %18llu ns, %6ld iterations\n", time, cnt);
4441fca0 YN	95
	96	return 0;
	97	}
	98
0ade34c3 CC	99	static int __init test_find_next_and_bit(const void *bitmap,
	100	const void *bitmap2, unsigned long len)
	101	{
	102	unsigned long i, cnt;
439e00b7	103	ktime_t time;
0ade34c3	104
439e00b7	105	time = ktime_get();
0ade34c3	106	for (cnt = i = 0; i < BITMAP_LEN; cnt++)
439e00b7 YN	107	i = find_next_and_bit(bitmap, bitmap2, BITMAP_LEN, i + 1);
	108	time = ktime_get() - time;
	109	pr_err("find_next_and_bit: %18llu ns, %6ld iterations\n", time, cnt);
0ade34c3 CC	110
	111	return 0;
	112	}
	113
4441fca0 YN	114	static int __init find_bit_test(void)
	115	{
	116	unsigned long nbits = BITMAP_LEN / SPARSE;
	117
	118	pr_err("\nStart testing find_bit() with random-filled bitmap\n");
	119
	120	get_random_bytes(bitmap, sizeof(bitmap));
0ade34c3	121	get_random_bytes(bitmap2, sizeof(bitmap2));
4441fca0 YN	122
	123	test_find_next_bit(bitmap, BITMAP_LEN);
	124	test_find_next_zero_bit(bitmap, BITMAP_LEN);
	125	test_find_last_bit(bitmap, BITMAP_LEN);
4ba281d5 YN	126
	127	/*
	128	* test_find_first_bit() may take some time, so
	129	* traverse only part of bitmap to avoid soft lockup.
	130	*/
	131	test_find_first_bit(bitmap, BITMAP_LEN / 10);
0ade34c3	132	test_find_next_and_bit(bitmap, bitmap2, BITMAP_LEN);
4441fca0 YN	133
	134	pr_err("\nStart testing find_bit() with sparse bitmap\n");
	135
	136	bitmap_zero(bitmap, BITMAP_LEN);
0ade34c3	137	bitmap_zero(bitmap2, BITMAP_LEN);
4441fca0	138
0ade34c3	139	while (nbits--) {
4441fca0	140	__set_bit(prandom_u32() % BITMAP_LEN, bitmap);
0ade34c3 CC	141	__set_bit(prandom_u32() % BITMAP_LEN, bitmap2);
0ade34c3 CC	142	}
4441fca0 YN	143
	144	test_find_next_bit(bitmap, BITMAP_LEN);
	145	test_find_next_zero_bit(bitmap, BITMAP_LEN);
	146	test_find_last_bit(bitmap, BITMAP_LEN);
	147	test_find_first_bit(bitmap, BITMAP_LEN);
0ade34c3	148	test_find_next_and_bit(bitmap, bitmap2, BITMAP_LEN);
4441fca0	149
15ff67bf YN	150	/*
	151	* Everything is OK. Return error just to let user run benchmark
	152	* again without annoying rmmod.
	153	*/
	154	return -EINVAL;
4441fca0 YN	155	}
	156	module_init(find_bit_test);
	157
4441fca0	158	MODULE_LICENSE("GPL");