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; |
47 | pr_err("find_first_bit: %18llu ns, %6ld iterations\n", time, cnt); | |
4441fca0 YN |
48 | |
49 | return 0; | |
50 | } | |
51 | ||
f68edc92 YN |
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 | ||
4441fca0 YN |
71 | static int __init test_find_next_bit(const void *bitmap, unsigned long len) |
72 | { | |
73 | unsigned long i, cnt; | |
15ff67bf | 74 | ktime_t time; |
4441fca0 | 75 | |
15ff67bf | 76 | time = ktime_get(); |
4441fca0 YN |
77 | for (cnt = i = 0; i < BITMAP_LEN; cnt++) |
78 | i = find_next_bit(bitmap, BITMAP_LEN, i) + 1; | |
15ff67bf YN |
79 | time = ktime_get() - time; |
80 | pr_err("find_next_bit: %18llu ns, %6ld iterations\n", time, cnt); | |
4441fca0 YN |
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; | |
15ff67bf | 88 | ktime_t time; |
4441fca0 | 89 | |
15ff67bf | 90 | time = ktime_get(); |
4441fca0 YN |
91 | for (cnt = i = 0; i < BITMAP_LEN; cnt++) |
92 | i = find_next_zero_bit(bitmap, len, i) + 1; | |
15ff67bf YN |
93 | time = ktime_get() - time; |
94 | pr_err("find_next_zero_bit: %18llu ns, %6ld iterations\n", time, cnt); | |
4441fca0 YN |
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; | |
15ff67bf | 102 | ktime_t time; |
4441fca0 | 103 | |
15ff67bf | 104 | time = ktime_get(); |
4441fca0 YN |
105 | do { |
106 | cnt++; | |
107 | l = find_last_bit(bitmap, len); | |
108 | if (l >= len) | |
109 | break; | |
110 | len = l; | |
111 | } while (len); | |
15ff67bf YN |
112 | time = ktime_get() - time; |
113 | pr_err("find_last_bit: %18llu ns, %6ld iterations\n", time, cnt); | |
4441fca0 YN |
114 | |
115 | return 0; | |
116 | } | |
117 | ||
0ade34c3 CC |
118 | static int __init test_find_next_and_bit(const void *bitmap, |
119 | const void *bitmap2, unsigned long len) | |
120 | { | |
121 | unsigned long i, cnt; | |
439e00b7 | 122 | ktime_t time; |
0ade34c3 | 123 | |
439e00b7 | 124 | time = ktime_get(); |
0ade34c3 | 125 | for (cnt = i = 0; i < BITMAP_LEN; cnt++) |
439e00b7 YN |
126 | i = find_next_and_bit(bitmap, bitmap2, BITMAP_LEN, i + 1); |
127 | time = ktime_get() - time; | |
128 | pr_err("find_next_and_bit: %18llu ns, %6ld iterations\n", time, cnt); | |
0ade34c3 CC |
129 | |
130 | return 0; | |
131 | } | |
132 | ||
4441fca0 YN |
133 | static int __init find_bit_test(void) |
134 | { | |
135 | unsigned long nbits = BITMAP_LEN / SPARSE; | |
136 | ||
137 | pr_err("\nStart testing find_bit() with random-filled bitmap\n"); | |
138 | ||
139 | get_random_bytes(bitmap, sizeof(bitmap)); | |
0ade34c3 | 140 | get_random_bytes(bitmap2, sizeof(bitmap2)); |
4441fca0 YN |
141 | |
142 | test_find_next_bit(bitmap, BITMAP_LEN); | |
143 | test_find_next_zero_bit(bitmap, BITMAP_LEN); | |
144 | test_find_last_bit(bitmap, BITMAP_LEN); | |
4ba281d5 YN |
145 | |
146 | /* | |
147 | * test_find_first_bit() may take some time, so | |
148 | * traverse only part of bitmap to avoid soft lockup. | |
149 | */ | |
150 | test_find_first_bit(bitmap, BITMAP_LEN / 10); | |
f68edc92 | 151 | test_find_first_and_bit(bitmap, bitmap2, BITMAP_LEN / 2); |
0ade34c3 | 152 | test_find_next_and_bit(bitmap, bitmap2, BITMAP_LEN); |
4441fca0 YN |
153 | |
154 | pr_err("\nStart testing find_bit() with sparse bitmap\n"); | |
155 | ||
156 | bitmap_zero(bitmap, BITMAP_LEN); | |
0ade34c3 | 157 | bitmap_zero(bitmap2, BITMAP_LEN); |
4441fca0 | 158 | |
0ade34c3 | 159 | while (nbits--) { |
4441fca0 | 160 | __set_bit(prandom_u32() % BITMAP_LEN, bitmap); |
0ade34c3 CC |
161 | __set_bit(prandom_u32() % BITMAP_LEN, bitmap2); |
162 | } | |
4441fca0 YN |
163 | |
164 | test_find_next_bit(bitmap, BITMAP_LEN); | |
165 | test_find_next_zero_bit(bitmap, BITMAP_LEN); | |
166 | test_find_last_bit(bitmap, BITMAP_LEN); | |
167 | test_find_first_bit(bitmap, BITMAP_LEN); | |
f68edc92 | 168 | test_find_first_and_bit(bitmap, bitmap2, BITMAP_LEN); |
0ade34c3 | 169 | test_find_next_and_bit(bitmap, bitmap2, BITMAP_LEN); |
4441fca0 | 170 | |
15ff67bf YN |
171 | /* |
172 | * Everything is OK. Return error just to let user run benchmark | |
173 | * again without annoying rmmod. | |
174 | */ | |
175 | return -EINVAL; | |
4441fca0 YN |
176 | } |
177 | module_init(find_bit_test); | |
178 | ||
4441fca0 | 179 | MODULE_LICENSE("GPL"); |