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. It should be called after 34 * all other tests for the same bitmap because it sets all bits of bitmap to 1. 35 */ 36 static int __init test_find_first_bit(void *bitmap, unsigned long len) 37 { 38 unsigned long i, cnt; 39 ktime_t time; 40 41 time = ktime_get(); 42 for (cnt = i = 0; i < len; cnt++) { 43 i = find_first_bit(bitmap, len); 44 __clear_bit(i, bitmap); 45 } 46 time = ktime_get() - time; 47 pr_err("find_first_bit: %18llu ns, %6ld iterations\n", time, cnt); 48 49 return 0; 50 } 51 52 static int __init test_find_first_and_bit(void *bitmap, const void *bitmap2, unsigned long len) 53 { 54 static DECLARE_BITMAP(cp, BITMAP_LEN) __initdata; 55 unsigned long i, cnt; 56 ktime_t time; 57 58 bitmap_copy(cp, bitmap, BITMAP_LEN); 59 60 time = ktime_get(); 61 for (cnt = i = 0; i < len; cnt++) { 62 i = find_first_and_bit(cp, bitmap2, len); 63 __clear_bit(i, cp); 64 } 65 time = ktime_get() - time; 66 pr_err("find_first_and_bit: %18llu ns, %6ld iterations\n", time, cnt); 67 68 return 0; 69 } 70 71 static int __init test_find_next_bit(const void *bitmap, unsigned long len) 72 { 73 unsigned long i, cnt; 74 ktime_t time; 75 76 time = ktime_get(); 77 for (cnt = i = 0; i < BITMAP_LEN; cnt++) 78 i = find_next_bit(bitmap, BITMAP_LEN, i) + 1; 79 time = ktime_get() - time; 80 pr_err("find_next_bit: %18llu ns, %6ld iterations\n", time, cnt); 81 82 return 0; 83 } 84 85 static int __init test_find_next_zero_bit(const void *bitmap, unsigned long len) 86 { 87 unsigned long i, cnt; 88 ktime_t time; 89 90 time = ktime_get(); 91 for (cnt = i = 0; i < BITMAP_LEN; cnt++) 92 i = find_next_zero_bit(bitmap, len, i) + 1; 93 time = ktime_get() - time; 94 pr_err("find_next_zero_bit: %18llu ns, %6ld iterations\n", time, cnt); 95 96 return 0; 97 } 98 99 static int __init test_find_last_bit(const void *bitmap, unsigned long len) 100 { 101 unsigned long l, cnt = 0; 102 ktime_t time; 103 104 time = ktime_get(); 105 do { 106 cnt++; 107 l = find_last_bit(bitmap, len); 108 if (l >= len) 109 break; 110 len = l; 111 } while (len); 112 time = ktime_get() - time; 113 pr_err("find_last_bit: %18llu ns, %6ld iterations\n", time, cnt); 114 115 return 0; 116 } 117 118 static int __init test_find_nth_bit(const unsigned long *bitmap, unsigned long len) 119 { 120 unsigned long l, n, w = bitmap_weight(bitmap, len); 121 ktime_t time; 122 123 time = ktime_get(); 124 for (n = 0; n < w; n++) { 125 l = find_nth_bit(bitmap, len, n); 126 WARN_ON(l >= len); 127 } 128 time = ktime_get() - time; 129 pr_err("find_nth_bit: %18llu ns, %6ld iterations\n", time, w); 130 131 return 0; 132 } 133 134 static int __init test_find_next_and_bit(const void *bitmap, 135 const void *bitmap2, unsigned long len) 136 { 137 unsigned long i, cnt; 138 ktime_t time; 139 140 time = ktime_get(); 141 for (cnt = i = 0; i < BITMAP_LEN; cnt++) 142 i = find_next_and_bit(bitmap, bitmap2, BITMAP_LEN, i + 1); 143 time = ktime_get() - time; 144 pr_err("find_next_and_bit: %18llu ns, %6ld iterations\n", time, cnt); 145 146 return 0; 147 } 148 149 static int __init find_bit_test(void) 150 { 151 unsigned long nbits = BITMAP_LEN / SPARSE; 152 153 pr_err("\nStart testing find_bit() with random-filled bitmap\n"); 154 155 get_random_bytes(bitmap, sizeof(bitmap)); 156 get_random_bytes(bitmap2, sizeof(bitmap2)); 157 158 test_find_next_bit(bitmap, BITMAP_LEN); 159 test_find_next_zero_bit(bitmap, BITMAP_LEN); 160 test_find_last_bit(bitmap, BITMAP_LEN); 161 test_find_nth_bit(bitmap, BITMAP_LEN / 10); 162 163 /* 164 * test_find_first_bit() may take some time, so 165 * traverse only part of bitmap to avoid soft lockup. 166 */ 167 test_find_first_bit(bitmap, BITMAP_LEN / 10); 168 test_find_first_and_bit(bitmap, bitmap2, BITMAP_LEN / 2); 169 test_find_next_and_bit(bitmap, bitmap2, BITMAP_LEN); 170 171 pr_err("\nStart testing find_bit() with sparse bitmap\n"); 172 173 bitmap_zero(bitmap, BITMAP_LEN); 174 bitmap_zero(bitmap2, BITMAP_LEN); 175 176 while (nbits--) { 177 __set_bit(prandom_u32_max(BITMAP_LEN), bitmap); 178 __set_bit(prandom_u32_max(BITMAP_LEN), bitmap2); 179 } 180 181 test_find_next_bit(bitmap, BITMAP_LEN); 182 test_find_next_zero_bit(bitmap, BITMAP_LEN); 183 test_find_last_bit(bitmap, BITMAP_LEN); 184 test_find_nth_bit(bitmap, BITMAP_LEN); 185 test_find_first_bit(bitmap, BITMAP_LEN); 186 test_find_first_and_bit(bitmap, bitmap2, BITMAP_LEN); 187 test_find_next_and_bit(bitmap, bitmap2, BITMAP_LEN); 188 189 /* 190 * Everything is OK. Return error just to let user run benchmark 191 * again without annoying rmmod. 192 */ 193 return -EINVAL; 194 } 195 module_init(find_bit_test); 196 197 MODULE_LICENSE("GPL"); 198