blob: f4394a36f9aa2b60a05624308a60ba59897f1606 [file] [log] [blame]
Yury Norov4441fca2017-11-17 15:28:31 -08001/*
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
37static 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 */
43static 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
60static 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
75static 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
90static 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
110static 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}
137module_init(find_bit_test);
138
139static void __exit test_find_bit_cleanup(void)
140{
141}
142module_exit(test_find_bit_cleanup);
143
144MODULE_LICENSE("GPL");