Commit | Line | Data |
---|---|---|
4441fca0 YN |
1 | /* |
2 | * Test for find_*_bit functions. | |
3 | * | |
4 | * Copyright (c) 2017 Cavium. | |
5 | * | |
6 | * This program is free software; you can redistribute it and/or | |
7 | * modify it under the terms of version 2 of the GNU General Public | |
8 | * License as published by the Free Software Foundation. | |
9 | * | |
10 | * This program is distributed in the hope that it will be useful, but | |
11 | * WITHOUT ANY WARRANTY; without even the implied warranty of | |
12 | * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU | |
13 | * General Public License for more details. | |
14 | */ | |
15 | ||
16 | /* | |
17 | * find_bit functions are widely used in kernel, so the successful boot | |
18 | * is good enough test for correctness. | |
19 | * | |
20 | * This test is focused on performance of traversing bitmaps. Two typical | |
21 | * scenarios are reproduced: | |
22 | * - randomly filled bitmap with approximately equal number of set and | |
23 | * cleared bits; | |
24 | * - sparse bitmap with few set bits at random positions. | |
25 | */ | |
26 | ||
27 | #include <linux/bitops.h> | |
28 | #include <linux/kernel.h> | |
29 | #include <linux/list.h> | |
30 | #include <linux/module.h> | |
31 | #include <linux/printk.h> | |
32 | #include <linux/random.h> | |
33 | ||
34 | #define BITMAP_LEN (4096UL * 8 * 10) | |
35 | #define SPARSE 500 | |
36 | ||
37 | static DECLARE_BITMAP(bitmap, BITMAP_LEN) __initdata; | |
38 | ||
39 | /* | |
40 | * This is Schlemiel the Painter's algorithm. It should be called after | |
41 | * all other tests for the same bitmap because it sets all bits of bitmap to 1. | |
42 | */ | |
43 | static int __init test_find_first_bit(void *bitmap, unsigned long len) | |
44 | { | |
45 | unsigned long i, cnt; | |
46 | cycles_t cycles; | |
47 | ||
48 | cycles = get_cycles(); | |
49 | for (cnt = i = 0; i < len; cnt++) { | |
50 | i = find_first_bit(bitmap, len); | |
51 | __clear_bit(i, bitmap); | |
52 | } | |
53 | cycles = get_cycles() - cycles; | |
54 | pr_err("find_first_bit:\t\t%llu cycles,\t%ld iterations\n", | |
55 | (u64)cycles, cnt); | |
56 | ||
57 | return 0; | |
58 | } | |
59 | ||
60 | static int __init test_find_next_bit(const void *bitmap, unsigned long len) | |
61 | { | |
62 | unsigned long i, cnt; | |
63 | cycles_t cycles; | |
64 | ||
65 | cycles = get_cycles(); | |
66 | for (cnt = i = 0; i < BITMAP_LEN; cnt++) | |
67 | i = find_next_bit(bitmap, BITMAP_LEN, i) + 1; | |
68 | cycles = get_cycles() - cycles; | |
69 | pr_err("find_next_bit:\t\t%llu cycles,\t%ld iterations\n", | |
70 | (u64)cycles, cnt); | |
71 | ||
72 | return 0; | |
73 | } | |
74 | ||
75 | static int __init test_find_next_zero_bit(const void *bitmap, unsigned long len) | |
76 | { | |
77 | unsigned long i, cnt; | |
78 | cycles_t cycles; | |
79 | ||
80 | cycles = get_cycles(); | |
81 | for (cnt = i = 0; i < BITMAP_LEN; cnt++) | |
82 | i = find_next_zero_bit(bitmap, len, i) + 1; | |
83 | cycles = get_cycles() - cycles; | |
84 | pr_err("find_next_zero_bit:\t%llu cycles,\t%ld iterations\n", | |
85 | (u64)cycles, cnt); | |
86 | ||
87 | return 0; | |
88 | } | |
89 | ||
90 | static int __init test_find_last_bit(const void *bitmap, unsigned long len) | |
91 | { | |
92 | unsigned long l, cnt = 0; | |
93 | cycles_t cycles; | |
94 | ||
95 | cycles = get_cycles(); | |
96 | do { | |
97 | cnt++; | |
98 | l = find_last_bit(bitmap, len); | |
99 | if (l >= len) | |
100 | break; | |
101 | len = l; | |
102 | } while (len); | |
103 | cycles = get_cycles() - cycles; | |
104 | pr_err("find_last_bit:\t\t%llu cycles,\t%ld iterations\n", | |
105 | (u64)cycles, cnt); | |
106 | ||
107 | return 0; | |
108 | } | |
109 | ||
110 | static int __init find_bit_test(void) | |
111 | { | |
112 | unsigned long nbits = BITMAP_LEN / SPARSE; | |
113 | ||
114 | pr_err("\nStart testing find_bit() with random-filled bitmap\n"); | |
115 | ||
116 | get_random_bytes(bitmap, sizeof(bitmap)); | |
117 | ||
118 | test_find_next_bit(bitmap, BITMAP_LEN); | |
119 | test_find_next_zero_bit(bitmap, BITMAP_LEN); | |
120 | test_find_last_bit(bitmap, BITMAP_LEN); | |
121 | test_find_first_bit(bitmap, BITMAP_LEN); | |
122 | ||
123 | pr_err("\nStart testing find_bit() with sparse bitmap\n"); | |
124 | ||
125 | bitmap_zero(bitmap, BITMAP_LEN); | |
126 | ||
127 | while (nbits--) | |
128 | __set_bit(prandom_u32() % BITMAP_LEN, bitmap); | |
129 | ||
130 | test_find_next_bit(bitmap, BITMAP_LEN); | |
131 | test_find_next_zero_bit(bitmap, BITMAP_LEN); | |
132 | test_find_last_bit(bitmap, BITMAP_LEN); | |
133 | test_find_first_bit(bitmap, BITMAP_LEN); | |
134 | ||
135 | return 0; | |
136 | } | |
137 | module_init(find_bit_test); | |
138 | ||
139 | static void __exit test_find_bit_cleanup(void) | |
140 | { | |
141 | } | |
142 | module_exit(test_find_bit_cleanup); | |
143 | ||
144 | MODULE_LICENSE("GPL"); |