Blame view
lib/find_bit_benchmark.c
3.9 KB
5b497af42
|
1 |
// SPDX-License-Identifier: GPL-2.0-only |
4441fca0a
|
2 3 4 5 |
/* * Test for find_*_bit functions. * * Copyright (c) 2017 Cavium. |
4441fca0a
|
6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 |
*/ /* * find_bit functions are widely used in kernel, so the successful boot * is good enough test for correctness. * * This test is focused on performance of traversing bitmaps. Two typical * scenarios are reproduced: * - randomly filled bitmap with approximately equal number of set and * cleared bits; * - sparse bitmap with few set bits at random positions. */ #include <linux/bitops.h> #include <linux/kernel.h> #include <linux/list.h> #include <linux/module.h> #include <linux/printk.h> #include <linux/random.h> #define BITMAP_LEN (4096UL * 8 * 10) #define SPARSE 500 static DECLARE_BITMAP(bitmap, BITMAP_LEN) __initdata; |
0ade34c37
|
30 |
static DECLARE_BITMAP(bitmap2, BITMAP_LEN) __initdata; |
4441fca0a
|
31 32 33 34 35 36 37 38 |
/* * This is Schlemiel the Painter's algorithm. It should be called after * all other tests for the same bitmap because it sets all bits of bitmap to 1. */ static int __init test_find_first_bit(void *bitmap, unsigned long len) { unsigned long i, cnt; |
15ff67bf8
|
39 |
ktime_t time; |
4441fca0a
|
40 |
|
15ff67bf8
|
41 |
time = ktime_get(); |
4441fca0a
|
42 43 44 45 |
for (cnt = i = 0; i < len; cnt++) { i = find_first_bit(bitmap, len); __clear_bit(i, bitmap); } |
15ff67bf8
|
46 47 48 |
time = ktime_get() - time; pr_err("find_first_bit: %18llu ns, %6ld iterations ", time, cnt); |
4441fca0a
|
49 50 51 52 53 54 55 |
return 0; } static int __init test_find_next_bit(const void *bitmap, unsigned long len) { unsigned long i, cnt; |
15ff67bf8
|
56 |
ktime_t time; |
4441fca0a
|
57 |
|
15ff67bf8
|
58 |
time = ktime_get(); |
4441fca0a
|
59 60 |
for (cnt = i = 0; i < BITMAP_LEN; cnt++) i = find_next_bit(bitmap, BITMAP_LEN, i) + 1; |
15ff67bf8
|
61 62 63 |
time = ktime_get() - time; pr_err("find_next_bit: %18llu ns, %6ld iterations ", time, cnt); |
4441fca0a
|
64 65 66 67 68 69 70 |
return 0; } static int __init test_find_next_zero_bit(const void *bitmap, unsigned long len) { unsigned long i, cnt; |
15ff67bf8
|
71 |
ktime_t time; |
4441fca0a
|
72 |
|
15ff67bf8
|
73 |
time = ktime_get(); |
4441fca0a
|
74 75 |
for (cnt = i = 0; i < BITMAP_LEN; cnt++) i = find_next_zero_bit(bitmap, len, i) + 1; |
15ff67bf8
|
76 77 78 |
time = ktime_get() - time; pr_err("find_next_zero_bit: %18llu ns, %6ld iterations ", time, cnt); |
4441fca0a
|
79 80 81 82 83 84 85 |
return 0; } static int __init test_find_last_bit(const void *bitmap, unsigned long len) { unsigned long l, cnt = 0; |
15ff67bf8
|
86 |
ktime_t time; |
4441fca0a
|
87 |
|
15ff67bf8
|
88 |
time = ktime_get(); |
4441fca0a
|
89 90 91 92 93 94 95 |
do { cnt++; l = find_last_bit(bitmap, len); if (l >= len) break; len = l; } while (len); |
15ff67bf8
|
96 97 98 |
time = ktime_get() - time; pr_err("find_last_bit: %18llu ns, %6ld iterations ", time, cnt); |
4441fca0a
|
99 100 101 |
return 0; } |
0ade34c37
|
102 103 104 105 |
static int __init test_find_next_and_bit(const void *bitmap, const void *bitmap2, unsigned long len) { unsigned long i, cnt; |
439e00b76
|
106 |
ktime_t time; |
0ade34c37
|
107 |
|
439e00b76
|
108 |
time = ktime_get(); |
0ade34c37
|
109 |
for (cnt = i = 0; i < BITMAP_LEN; cnt++) |
439e00b76
|
110 111 112 113 |
i = find_next_and_bit(bitmap, bitmap2, BITMAP_LEN, i + 1); time = ktime_get() - time; pr_err("find_next_and_bit: %18llu ns, %6ld iterations ", time, cnt); |
0ade34c37
|
114 115 116 |
return 0; } |
4441fca0a
|
117 118 119 120 121 122 123 124 125 |
static int __init find_bit_test(void) { unsigned long nbits = BITMAP_LEN / SPARSE; pr_err(" Start testing find_bit() with random-filled bitmap "); get_random_bytes(bitmap, sizeof(bitmap)); |
0ade34c37
|
126 |
get_random_bytes(bitmap2, sizeof(bitmap2)); |
4441fca0a
|
127 128 129 130 |
test_find_next_bit(bitmap, BITMAP_LEN); test_find_next_zero_bit(bitmap, BITMAP_LEN); test_find_last_bit(bitmap, BITMAP_LEN); |
4ba281d5b
|
131 132 133 134 135 136 |
/* * test_find_first_bit() may take some time, so * traverse only part of bitmap to avoid soft lockup. */ test_find_first_bit(bitmap, BITMAP_LEN / 10); |
0ade34c37
|
137 |
test_find_next_and_bit(bitmap, bitmap2, BITMAP_LEN); |
4441fca0a
|
138 139 140 141 142 143 |
pr_err(" Start testing find_bit() with sparse bitmap "); bitmap_zero(bitmap, BITMAP_LEN); |
0ade34c37
|
144 |
bitmap_zero(bitmap2, BITMAP_LEN); |
4441fca0a
|
145 |
|
0ade34c37
|
146 |
while (nbits--) { |
4441fca0a
|
147 |
__set_bit(prandom_u32() % BITMAP_LEN, bitmap); |
0ade34c37
|
148 149 |
__set_bit(prandom_u32() % BITMAP_LEN, bitmap2); } |
4441fca0a
|
150 151 152 153 154 |
test_find_next_bit(bitmap, BITMAP_LEN); test_find_next_zero_bit(bitmap, BITMAP_LEN); test_find_last_bit(bitmap, BITMAP_LEN); test_find_first_bit(bitmap, BITMAP_LEN); |
0ade34c37
|
155 |
test_find_next_and_bit(bitmap, bitmap2, BITMAP_LEN); |
4441fca0a
|
156 |
|
15ff67bf8
|
157 158 159 160 161 |
/* * Everything is OK. Return error just to let user run benchmark * again without annoying rmmod. */ return -EINVAL; |
4441fca0a
|
162 163 |
} module_init(find_bit_test); |
4441fca0a
|
164 |
MODULE_LICENSE("GPL"); |