Blame view
lib/find_bit_benchmark.c
3.9 KB
5b497af42 treewide: Replace... |
1 |
// SPDX-License-Identifier: GPL-2.0-only |
4441fca0a lib: test module ... |
2 3 4 5 |
/* * Test for find_*_bit functions. * * Copyright (c) 2017 Cavium. |
4441fca0a lib: test module ... |
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 lib: optimize cpu... |
30 |
static DECLARE_BITMAP(bitmap2, BITMAP_LEN) __initdata; |
4441fca0a lib: test module ... |
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 lib/find_bit_benc... |
39 |
ktime_t time; |
4441fca0a lib: test module ... |
40 |
|
15ff67bf8 lib/find_bit_benc... |
41 |
time = ktime_get(); |
4441fca0a lib: test module ... |
42 43 44 45 |
for (cnt = i = 0; i < len; cnt++) { i = find_first_bit(bitmap, len); __clear_bit(i, bitmap); } |
15ff67bf8 lib/find_bit_benc... |
46 47 48 |
time = ktime_get() - time; pr_err("find_first_bit: %18llu ns, %6ld iterations ", time, cnt); |
4441fca0a lib: test module ... |
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 lib/find_bit_benc... |
56 |
ktime_t time; |
4441fca0a lib: test module ... |
57 |
|
15ff67bf8 lib/find_bit_benc... |
58 |
time = ktime_get(); |
4441fca0a lib: test module ... |
59 60 |
for (cnt = i = 0; i < BITMAP_LEN; cnt++) i = find_next_bit(bitmap, BITMAP_LEN, i) + 1; |
15ff67bf8 lib/find_bit_benc... |
61 62 63 |
time = ktime_get() - time; pr_err("find_next_bit: %18llu ns, %6ld iterations ", time, cnt); |
4441fca0a lib: test module ... |
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 lib/find_bit_benc... |
71 |
ktime_t time; |
4441fca0a lib: test module ... |
72 |
|
15ff67bf8 lib/find_bit_benc... |
73 |
time = ktime_get(); |
4441fca0a lib: test module ... |
74 75 |
for (cnt = i = 0; i < BITMAP_LEN; cnt++) i = find_next_zero_bit(bitmap, len, i) + 1; |
15ff67bf8 lib/find_bit_benc... |
76 77 78 |
time = ktime_get() - time; pr_err("find_next_zero_bit: %18llu ns, %6ld iterations ", time, cnt); |
4441fca0a lib: test module ... |
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 lib/find_bit_benc... |
86 |
ktime_t time; |
4441fca0a lib: test module ... |
87 |
|
15ff67bf8 lib/find_bit_benc... |
88 |
time = ktime_get(); |
4441fca0a lib: test module ... |
89 90 91 92 93 94 95 |
do { cnt++; l = find_last_bit(bitmap, len); if (l >= len) break; len = l; } while (len); |
15ff67bf8 lib/find_bit_benc... |
96 97 98 |
time = ktime_get() - time; pr_err("find_last_bit: %18llu ns, %6ld iterations ", time, cnt); |
4441fca0a lib: test module ... |
99 100 101 |
return 0; } |
0ade34c37 lib: optimize cpu... |
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 lib/find_bit_benc... |
106 |
ktime_t time; |
0ade34c37 lib: optimize cpu... |
107 |
|
439e00b76 lib/find_bit_benc... |
108 |
time = ktime_get(); |
0ade34c37 lib: optimize cpu... |
109 |
for (cnt = i = 0; i < BITMAP_LEN; cnt++) |
439e00b76 lib/find_bit_benc... |
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 lib: optimize cpu... |
114 115 116 |
return 0; } |
4441fca0a lib: test module ... |
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 lib: optimize cpu... |
126 |
get_random_bytes(bitmap2, sizeof(bitmap2)); |
4441fca0a lib: test module ... |
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 lib/find_bit_benc... |
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 lib: optimize cpu... |
137 |
test_find_next_and_bit(bitmap, bitmap2, BITMAP_LEN); |
4441fca0a lib: test module ... |
138 139 140 141 142 143 |
pr_err(" Start testing find_bit() with sparse bitmap "); bitmap_zero(bitmap, BITMAP_LEN); |
0ade34c37 lib: optimize cpu... |
144 |
bitmap_zero(bitmap2, BITMAP_LEN); |
4441fca0a lib: test module ... |
145 |
|
0ade34c37 lib: optimize cpu... |
146 |
while (nbits--) { |
4441fca0a lib: test module ... |
147 |
__set_bit(prandom_u32() % BITMAP_LEN, bitmap); |
0ade34c37 lib: optimize cpu... |
148 149 |
__set_bit(prandom_u32() % BITMAP_LEN, bitmap2); } |
4441fca0a lib: test module ... |
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 lib: optimize cpu... |
155 |
test_find_next_and_bit(bitmap, bitmap2, BITMAP_LEN); |
4441fca0a lib: test module ... |
156 |
|
15ff67bf8 lib/find_bit_benc... |
157 158 159 160 161 |
/* * Everything is OK. Return error just to let user run benchmark * again without annoying rmmod. */ return -EINVAL; |
4441fca0a lib: test module ... |
162 163 |
} module_init(find_bit_test); |
4441fca0a lib: test module ... |
164 |
MODULE_LICENSE("GPL"); |