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 | */ |
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(addr: bitmap, size: 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 | |
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(dst: cp, src: bitmap, BITMAP_LEN); |
59 | |
60 | time = ktime_get(); |
61 | for (cnt = i = 0; i < len; cnt++) { |
62 | i = find_first_and_bit(addr1: cp, addr2: bitmap2, size: 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 | |
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(addr: bitmap, BITMAP_LEN, offset: 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 | |
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(addr: bitmap, size: len, offset: 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 | |
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(addr: bitmap, size: 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 | |
118 | static int __init test_find_nth_bit(const unsigned long *bitmap, unsigned long len) |
119 | { |
120 | unsigned long l, n, w = bitmap_weight(src: bitmap, nbits: len); |
121 | ktime_t time; |
122 | |
123 | time = ktime_get(); |
124 | for (n = 0; n < w; n++) { |
125 | l = find_nth_bit(addr: bitmap, size: 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 | |
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(addr1: bitmap, addr2: bitmap2, BITMAP_LEN, offset: 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 | |
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(buf: bitmap, len: sizeof(bitmap)); |
156 | get_random_bytes(buf: bitmap2, len: 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(dst: bitmap, BITMAP_LEN); |
174 | bitmap_zero(dst: 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_LICENSE("GPL" ); |
198 | |