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 | ||
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++) |
59 | i = find_next_bit(bitmap, BITMAP_LEN, i) + 1; | |
15ff67bf YN |
60 | time = ktime_get() - time; |
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++) |
73 | i = find_next_zero_bit(bitmap, len, i) + 1; | |
15ff67bf YN |
74 | time = ktime_get() - time; |
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; |
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); |
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"); |