Blame view
lib/find_bit_benchmark.c
4.31 KB
4441fca0a lib: test module ... |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 |
/* * Test for find_*_bit functions. * * Copyright (c) 2017 Cavium. * * This program is free software; you can redistribute it and/or * modify it under the terms of version 2 of the GNU General Public * License as published by the Free Software Foundation. * * This program is distributed in the hope that it will be useful, but * WITHOUT ANY WARRANTY; without even the implied warranty of * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU * General Public License for more details. */ /* * 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... |
38 |
static DECLARE_BITMAP(bitmap2, BITMAP_LEN) __initdata; |
4441fca0a lib: test module ... |
39 40 41 42 43 44 45 46 |
/* * 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... |
47 |
ktime_t time; |
4441fca0a lib: test module ... |
48 |
|
15ff67bf8 lib/find_bit_benc... |
49 |
time = ktime_get(); |
4441fca0a lib: test module ... |
50 51 52 53 |
for (cnt = i = 0; i < len; cnt++) { i = find_first_bit(bitmap, len); __clear_bit(i, bitmap); } |
15ff67bf8 lib/find_bit_benc... |
54 55 56 |
time = ktime_get() - time; pr_err("find_first_bit: %18llu ns, %6ld iterations ", time, cnt); |
4441fca0a lib: test module ... |
57 58 59 60 61 62 63 |
return 0; } static int __init test_find_next_bit(const void *bitmap, unsigned long len) { unsigned long i, cnt; |
15ff67bf8 lib/find_bit_benc... |
64 |
ktime_t time; |
4441fca0a lib: test module ... |
65 |
|
15ff67bf8 lib/find_bit_benc... |
66 |
time = ktime_get(); |
4441fca0a lib: test module ... |
67 68 |
for (cnt = i = 0; i < BITMAP_LEN; cnt++) i = find_next_bit(bitmap, BITMAP_LEN, i) + 1; |
15ff67bf8 lib/find_bit_benc... |
69 70 71 |
time = ktime_get() - time; pr_err("find_next_bit: %18llu ns, %6ld iterations ", time, cnt); |
4441fca0a lib: test module ... |
72 73 74 75 76 77 78 |
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... |
79 |
ktime_t time; |
4441fca0a lib: test module ... |
80 |
|
15ff67bf8 lib/find_bit_benc... |
81 |
time = ktime_get(); |
4441fca0a lib: test module ... |
82 83 |
for (cnt = i = 0; i < BITMAP_LEN; cnt++) i = find_next_zero_bit(bitmap, len, i) + 1; |
15ff67bf8 lib/find_bit_benc... |
84 85 86 |
time = ktime_get() - time; pr_err("find_next_zero_bit: %18llu ns, %6ld iterations ", time, cnt); |
4441fca0a lib: test module ... |
87 88 89 90 91 92 93 |
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... |
94 |
ktime_t time; |
4441fca0a lib: test module ... |
95 |
|
15ff67bf8 lib/find_bit_benc... |
96 |
time = ktime_get(); |
4441fca0a lib: test module ... |
97 98 99 100 101 102 103 |
do { cnt++; l = find_last_bit(bitmap, len); if (l >= len) break; len = l; } while (len); |
15ff67bf8 lib/find_bit_benc... |
104 105 106 |
time = ktime_get() - time; pr_err("find_last_bit: %18llu ns, %6ld iterations ", time, cnt); |
4441fca0a lib: test module ... |
107 108 109 |
return 0; } |
0ade34c37 lib: optimize cpu... |
110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 |
static int __init test_find_next_and_bit(const void *bitmap, const void *bitmap2, unsigned long len) { unsigned long i, cnt; cycles_t cycles; cycles = get_cycles(); for (cnt = i = 0; i < BITMAP_LEN; cnt++) i = find_next_and_bit(bitmap, bitmap2, BITMAP_LEN, i+1); cycles = get_cycles() - cycles; pr_err("find_next_and_bit:\t\t%llu cycles, %ld iterations ", (u64)cycles, cnt); return 0; } |
4441fca0a lib: test module ... |
126 127 128 129 130 131 132 133 134 |
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... |
135 |
get_random_bytes(bitmap2, sizeof(bitmap2)); |
4441fca0a lib: test module ... |
136 137 138 139 |
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... |
140 141 142 143 144 145 |
/* * 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... |
146 |
test_find_next_and_bit(bitmap, bitmap2, BITMAP_LEN); |
4441fca0a lib: test module ... |
147 148 149 150 151 152 |
pr_err(" Start testing find_bit() with sparse bitmap "); bitmap_zero(bitmap, BITMAP_LEN); |
0ade34c37 lib: optimize cpu... |
153 |
bitmap_zero(bitmap2, BITMAP_LEN); |
4441fca0a lib: test module ... |
154 |
|
0ade34c37 lib: optimize cpu... |
155 |
while (nbits--) { |
4441fca0a lib: test module ... |
156 |
__set_bit(prandom_u32() % BITMAP_LEN, bitmap); |
0ade34c37 lib: optimize cpu... |
157 158 |
__set_bit(prandom_u32() % BITMAP_LEN, bitmap2); } |
4441fca0a lib: test module ... |
159 160 161 162 163 |
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... |
164 |
test_find_next_and_bit(bitmap, bitmap2, BITMAP_LEN); |
4441fca0a lib: test module ... |
165 |
|
15ff67bf8 lib/find_bit_benc... |
166 167 168 169 170 |
/* * Everything is OK. Return error just to let user run benchmark * again without annoying rmmod. */ return -EINVAL; |
4441fca0a lib: test module ... |
171 172 |
} module_init(find_bit_test); |
4441fca0a lib: test module ... |
173 |
MODULE_LICENSE("GPL"); |