1 // SPDX-License-Identifier: GPL-2.0-only 2 /* 3 * Test for find_*_bit functions. 4 * 5 * Copyright (c) 2017 Cavium. 6 */ 7 8 /* 9 * find_bit functions are widely used in kernel, so the successful boot 10 * is good enough test for correctness. 11 * 12 * This test is focused on performance of traversing bitmaps. Two typical 13 * scenarios are reproduced: 14 * - randomly filled bitmap with approximately equal number of set and 15 * cleared bits; 16 * - sparse bitmap with few set bits at random positions. 17 */ 18 19 #include <linux/bitops.h> 20 #include <linux/kernel.h> 21 #include <linux/list.h> 22 #include <linux/module.h> 23 #include <linux/printk.h> 24 #include <linux/random.h> 25 26 #define BITMAP_LEN (4096UL * 8 * 10) 27 #define SPARSE 500 28 29 static DECLARE_BITMAP(bitmap, BITMAP_LEN) __initdata; 30 static DECLARE_BITMAP(bitmap2, BITMAP_LEN) __initdata; 31 32 /* 33 * This is Schlemiel the Painter's algorithm. 34 */ 35 static int __init test_find_first_bit(const void *bitmap, unsigned long len) 36 { 37 static DECLARE_BITMAP(cp, BITMAP_LEN) __initdata; 38 unsigned long i, cnt; 39 ktime_t time; 40 41 bitmap_copy(cp, bitmap, BITMAP_LEN); 42 43 time = ktime_get(); 44 for (cnt = i = 0; i < len; cnt++) { 45 i = find_first_bit(cp, len); 46 __clear_bit(i, cp); 47 } 48 time = ktime_get() - time; 49 pr_err("find_first_bit: %18llu ns, %6ld iterations\n", time, cnt); 50 51 return 0; 52 } 53 54 static int __init test_find_first_and_bit(const void *bitmap, const void *bitmap2, 55 unsigned long len) 56 { 57 static DECLARE_BITMAP(cp, BITMAP_LEN) __initdata; 58 unsigned long i, cnt; 59 ktime_t time; 60 61 bitmap_copy(cp, bitmap, BITMAP_LEN); 62 63 time = ktime_get(); 64 for (cnt = i = 0; i < len; cnt++) { 65 i = find_first_and_bit(cp, bitmap2, len); 66 __clear_bit(i, cp); 67 } 68 time = ktime_get() - time; 69 pr_err("find_first_and_bit: %18llu ns, %6ld iterations\n", time, cnt); 70 71 return 0; 72 } 73 74 static int __init test_find_next_bit(const void *bitmap, unsigned long len) 75 { 76 unsigned long i, cnt; 77 ktime_t time; 78 79 time = ktime_get(); 80 for (cnt = i = 0; i < BITMAP_LEN; cnt++) 81 i = find_next_bit(bitmap, BITMAP_LEN, i) + 1; 82 time = ktime_get() - time; 83 pr_err("find_next_bit: %18llu ns, %6ld iterations\n", time, cnt); 84 85 return 0; 86 } 87 88 static int __init test_find_next_zero_bit(const void *bitmap, unsigned long len) 89 { 90 unsigned long i, cnt; 91 ktime_t time; 92 93 time = ktime_get(); 94 for (cnt = i = 0; i < BITMAP_LEN; cnt++) 95 i = find_next_zero_bit(bitmap, len, i) + 1; 96 time = ktime_get() - time; 97 pr_err("find_next_zero_bit: %18llu ns, %6ld iterations\n", time, cnt); 98 99 return 0; 100 } 101 102 static int __init test_find_last_bit(const void *bitmap, unsigned long len) 103 { 104 unsigned long l, cnt = 0; 105 ktime_t time; 106 107 time = ktime_get(); 108 do { 109 cnt++; 110 l = find_last_bit(bitmap, len); 111 if (l >= len) 112 break; 113 len = l; 114 } while (len); 115 time = ktime_get() - time; 116 pr_err("find_last_bit: %18llu ns, %6ld iterations\n", time, cnt); 117 118 return 0; 119 } 120 121 static int __init test_find_nth_bit(const unsigned long *bitmap, unsigned long len) 122 { 123 unsigned long l, n, w = bitmap_weight(bitmap, len); 124 ktime_t time; 125 126 time = ktime_get(); 127 for (n = 0; n < w; n++) { 128 l = find_nth_bit(bitmap, len, n); 129 WARN_ON(l >= len); 130 } 131 time = ktime_get() - time; 132 pr_err("find_nth_bit: %18llu ns, %6ld iterations\n", time, w); 133 134 return 0; 135 } 136 137 static int __init test_find_next_and_bit(const void *bitmap, 138 const void *bitmap2, unsigned long len) 139 { 140 unsigned long i, cnt; 141 ktime_t time; 142 143 time = ktime_get(); 144 for (cnt = i = 0; i < BITMAP_LEN; cnt++) 145 i = find_next_and_bit(bitmap, bitmap2, BITMAP_LEN, i + 1); 146 time = ktime_get() - time; 147 pr_err("find_next_and_bit: %18llu ns, %6ld iterations\n", time, cnt); 148 149 return 0; 150 } 151 152 static int __init 153 test_bitmap_find_next_zero_area_off(unsigned long *bitmap, unsigned long len) 154 { 155 unsigned long i, cnt; 156 ktime_t time; 157 158 time = ktime_get(); 159 for (cnt = i = 0; i < BITMAP_LEN; cnt++) 160 i = bitmap_find_next_zero_area_off(bitmap, BITMAP_LEN, i, 8, 0, 0) + 1; 161 time = ktime_get() - time; 162 pr_err("bitmap_find_next_zero_area_off:%7llu ns, %6ld iterations\n", time, cnt); 163 164 return 0; 165 } 166 167 static int __init find_bit_test(void) 168 { 169 unsigned long nbits = BITMAP_LEN / SPARSE; 170 171 pr_err("\nStart testing find_bit() with random-filled bitmap\n"); 172 173 get_random_bytes(bitmap, sizeof(bitmap)); 174 get_random_bytes(bitmap2, sizeof(bitmap2)); 175 176 test_bitmap_find_next_zero_area_off(bitmap, BITMAP_LEN); 177 test_find_next_bit(bitmap, BITMAP_LEN); 178 test_find_next_zero_bit(bitmap, BITMAP_LEN); 179 test_find_last_bit(bitmap, BITMAP_LEN); 180 test_find_nth_bit(bitmap, BITMAP_LEN / 10); 181 182 /* 183 * test_find_first_bit() may take some time, so 184 * traverse only part of bitmap to avoid soft lockup. 185 */ 186 test_find_first_bit(bitmap, BITMAP_LEN / 10); 187 test_find_first_and_bit(bitmap, bitmap2, BITMAP_LEN / 2); 188 test_find_next_and_bit(bitmap, bitmap2, BITMAP_LEN); 189 190 pr_err("\nStart testing find_bit() with sparse bitmap\n"); 191 192 bitmap_zero(bitmap, BITMAP_LEN); 193 bitmap_zero(bitmap2, BITMAP_LEN); 194 195 while (nbits--) { 196 __set_bit(get_random_u32_below(BITMAP_LEN), bitmap); 197 __set_bit(get_random_u32_below(BITMAP_LEN), bitmap2); 198 } 199 200 test_bitmap_find_next_zero_area_off(bitmap, BITMAP_LEN); 201 test_find_next_bit(bitmap, BITMAP_LEN); 202 test_find_next_zero_bit(bitmap, BITMAP_LEN); 203 test_find_last_bit(bitmap, BITMAP_LEN); 204 test_find_nth_bit(bitmap, BITMAP_LEN); 205 test_find_first_bit(bitmap, BITMAP_LEN); 206 test_find_first_and_bit(bitmap, bitmap2, BITMAP_LEN); 207 test_find_next_and_bit(bitmap, bitmap2, BITMAP_LEN); 208 209 /* 210 * Everything is OK. Return error just to let user run benchmark 211 * again without annoying rmmod. 212 */ 213 return -EINVAL; 214 } 215 module_init(find_bit_test); 216 217 MODULE_DESCRIPTION("Test for find_*_bit functions"); 218 MODULE_LICENSE("GPL"); 219