]>
Commit | Line | Data |
---|---|---|
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(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 | ||
52 | static int __init test_find_next_bit(const void *bitmap, unsigned long len) | |
53 | { | |
54 | unsigned long i, cnt; | |
55 | ktime_t time; | |
56 | ||
57 | time = ktime_get(); | |
58 | for (cnt = i = 0; i < BITMAP_LEN; cnt++) | |
59 | i = find_next_bit(bitmap, BITMAP_LEN, i) + 1; | |
60 | time = ktime_get() - time; | |
61 | pr_err("find_next_bit: %18llu ns, %6ld iterations\n", time, cnt); | |
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; | |
69 | ktime_t time; | |
70 | ||
71 | time = ktime_get(); | |
72 | for (cnt = i = 0; i < BITMAP_LEN; cnt++) | |
73 | i = find_next_zero_bit(bitmap, len, i) + 1; | |
74 | time = ktime_get() - time; | |
75 | pr_err("find_next_zero_bit: %18llu ns, %6ld iterations\n", time, cnt); | |
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; | |
83 | ktime_t time; | |
84 | ||
85 | time = ktime_get(); | |
86 | do { | |
87 | cnt++; | |
88 | l = find_last_bit(bitmap, len); | |
89 | if (l >= len) | |
90 | break; | |
91 | len = l; | |
92 | } while (len); | |
93 | time = ktime_get() - time; | |
94 | pr_err("find_last_bit: %18llu ns, %6ld iterations\n", time, cnt); | |
95 | ||
96 | return 0; | |
97 | } | |
98 | ||
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; | |
103 | ktime_t time; | |
104 | ||
105 | time = ktime_get(); | |
106 | for (cnt = i = 0; i < BITMAP_LEN; cnt++) | |
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); | |
110 | ||
111 | return 0; | |
112 | } | |
113 | ||
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)); | |
121 | get_random_bytes(bitmap2, sizeof(bitmap2)); | |
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); | |
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); | |
132 | test_find_next_and_bit(bitmap, bitmap2, BITMAP_LEN); | |
133 | ||
134 | pr_err("\nStart testing find_bit() with sparse bitmap\n"); | |
135 | ||
136 | bitmap_zero(bitmap, BITMAP_LEN); | |
137 | bitmap_zero(bitmap2, BITMAP_LEN); | |
138 | ||
139 | while (nbits--) { | |
140 | __set_bit(prandom_u32() % BITMAP_LEN, bitmap); | |
141 | __set_bit(prandom_u32() % BITMAP_LEN, bitmap2); | |
142 | } | |
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); | |
148 | test_find_next_and_bit(bitmap, bitmap2, BITMAP_LEN); | |
149 | ||
150 | /* | |
151 | * Everything is OK. Return error just to let user run benchmark | |
152 | * again without annoying rmmod. | |
153 | */ | |
154 | return -EINVAL; | |
155 | } | |
156 | module_init(find_bit_test); | |
157 | ||
158 | MODULE_LICENSE("GPL"); |