1  // SPDX-License-Identifier: GPL-2.0-only
2  /*
3   * Test for find_*_bit functions.
4   *
5   * Copyright (c) 2017 Cavium.
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;
30  static DECLARE_BITMAP(bitmap2, BITMAP_LEN) __initdata;
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   */
test_find_first_bit(void * bitmap,unsigned long len)36  static int __init test_find_first_bit(void *bitmap, unsigned long len)
37  {
38  	unsigned long i, cnt;
39  	ktime_t time;
40  
41  	time = ktime_get();
42  	for (cnt = i = 0; i < len; cnt++) {
43  		i = find_first_bit(bitmap, len);
44  		__clear_bit(i, bitmap);
45  	}
46  	time = ktime_get() - time;
47  	pr_err("find_first_bit:     %18llu ns, %6ld iterations\n", time, cnt);
48  
49  	return 0;
50  }
51  
test_find_first_and_bit(void * bitmap,const void * bitmap2,unsigned long len)52  static int __init test_find_first_and_bit(void *bitmap, const void *bitmap2, unsigned long len)
53  {
54  	static DECLARE_BITMAP(cp, BITMAP_LEN) __initdata;
55  	unsigned long i, cnt;
56  	ktime_t time;
57  
58  	bitmap_copy(cp, bitmap, BITMAP_LEN);
59  
60  	time = ktime_get();
61  	for (cnt = i = 0; i < len; cnt++) {
62  		i = find_first_and_bit(cp, bitmap2, len);
63  		__clear_bit(i, cp);
64  	}
65  	time = ktime_get() - time;
66  	pr_err("find_first_and_bit: %18llu ns, %6ld iterations\n", time, cnt);
67  
68  	return 0;
69  }
70  
test_find_next_bit(const void * bitmap,unsigned long len)71  static int __init test_find_next_bit(const void *bitmap, unsigned long len)
72  {
73  	unsigned long i, cnt;
74  	ktime_t time;
75  
76  	time = ktime_get();
77  	for (cnt = i = 0; i < BITMAP_LEN; cnt++)
78  		i = find_next_bit(bitmap, BITMAP_LEN, i) + 1;
79  	time = ktime_get() - time;
80  	pr_err("find_next_bit:      %18llu ns, %6ld iterations\n", time, cnt);
81  
82  	return 0;
83  }
84  
test_find_next_zero_bit(const void * bitmap,unsigned long len)85  static int __init test_find_next_zero_bit(const void *bitmap, unsigned long len)
86  {
87  	unsigned long i, cnt;
88  	ktime_t time;
89  
90  	time = ktime_get();
91  	for (cnt = i = 0; i < BITMAP_LEN; cnt++)
92  		i = find_next_zero_bit(bitmap, len, i) + 1;
93  	time = ktime_get() - time;
94  	pr_err("find_next_zero_bit: %18llu ns, %6ld iterations\n", time, cnt);
95  
96  	return 0;
97  }
98  
test_find_last_bit(const void * bitmap,unsigned long len)99  static int __init test_find_last_bit(const void *bitmap, unsigned long len)
100  {
101  	unsigned long l, cnt = 0;
102  	ktime_t time;
103  
104  	time = ktime_get();
105  	do {
106  		cnt++;
107  		l = find_last_bit(bitmap, len);
108  		if (l >= len)
109  			break;
110  		len = l;
111  	} while (len);
112  	time = ktime_get() - time;
113  	pr_err("find_last_bit:      %18llu ns, %6ld iterations\n", time, cnt);
114  
115  	return 0;
116  }
117  
test_find_nth_bit(const unsigned long * bitmap,unsigned long len)118  static int __init test_find_nth_bit(const unsigned long *bitmap, unsigned long len)
119  {
120  	unsigned long l, n, w = bitmap_weight(bitmap, len);
121  	ktime_t time;
122  
123  	time = ktime_get();
124  	for (n = 0; n < w; n++) {
125  		l = find_nth_bit(bitmap, len, n);
126  		WARN_ON(l >= len);
127  	}
128  	time = ktime_get() - time;
129  	pr_err("find_nth_bit:       %18llu ns, %6ld iterations\n", time, w);
130  
131  	return 0;
132  }
133  
test_find_next_and_bit(const void * bitmap,const void * bitmap2,unsigned long len)134  static int __init test_find_next_and_bit(const void *bitmap,
135  		const void *bitmap2, unsigned long len)
136  {
137  	unsigned long i, cnt;
138  	ktime_t time;
139  
140  	time = ktime_get();
141  	for (cnt = i = 0; i < BITMAP_LEN; cnt++)
142  		i = find_next_and_bit(bitmap, bitmap2, BITMAP_LEN, i + 1);
143  	time = ktime_get() - time;
144  	pr_err("find_next_and_bit:  %18llu ns, %6ld iterations\n", time, cnt);
145  
146  	return 0;
147  }
148  
find_bit_test(void)149  static int __init find_bit_test(void)
150  {
151  	unsigned long nbits = BITMAP_LEN / SPARSE;
152  
153  	pr_err("\nStart testing find_bit() with random-filled bitmap\n");
154  
155  	get_random_bytes(bitmap, sizeof(bitmap));
156  	get_random_bytes(bitmap2, sizeof(bitmap2));
157  
158  	test_find_next_bit(bitmap, BITMAP_LEN);
159  	test_find_next_zero_bit(bitmap, BITMAP_LEN);
160  	test_find_last_bit(bitmap, BITMAP_LEN);
161  	test_find_nth_bit(bitmap, BITMAP_LEN / 10);
162  
163  	/*
164  	 * test_find_first_bit() may take some time, so
165  	 * traverse only part of bitmap to avoid soft lockup.
166  	 */
167  	test_find_first_bit(bitmap, BITMAP_LEN / 10);
168  	test_find_first_and_bit(bitmap, bitmap2, BITMAP_LEN / 2);
169  	test_find_next_and_bit(bitmap, bitmap2, BITMAP_LEN);
170  
171  	pr_err("\nStart testing find_bit() with sparse bitmap\n");
172  
173  	bitmap_zero(bitmap, BITMAP_LEN);
174  	bitmap_zero(bitmap2, BITMAP_LEN);
175  
176  	while (nbits--) {
177  		__set_bit(get_random_u32_below(BITMAP_LEN), bitmap);
178  		__set_bit(get_random_u32_below(BITMAP_LEN), bitmap2);
179  	}
180  
181  	test_find_next_bit(bitmap, BITMAP_LEN);
182  	test_find_next_zero_bit(bitmap, BITMAP_LEN);
183  	test_find_last_bit(bitmap, BITMAP_LEN);
184  	test_find_nth_bit(bitmap, BITMAP_LEN);
185  	test_find_first_bit(bitmap, BITMAP_LEN);
186  	test_find_first_and_bit(bitmap, bitmap2, BITMAP_LEN);
187  	test_find_next_and_bit(bitmap, bitmap2, BITMAP_LEN);
188  
189  	/*
190  	 * Everything is OK. Return error just to let user run benchmark
191  	 * again without annoying rmmod.
192  	 */
193  	return -EINVAL;
194  }
195  module_init(find_bit_test);
196  
197  MODULE_DESCRIPTION("Test for find_*_bit functions");
198  MODULE_LICENSE("GPL");
199