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 static DECLARE_BITMAP(bitmap2, BITMAP_LEN) __initdata; 39 40 /* 41 * This is Schlemiel the Painter's algorithm. It should be called after 42 * all other tests for the same bitmap because it sets all bits of bitmap to 1. 43 */ 44 static int __init test_find_first_bit(void *bitmap, unsigned long len) 45 { 46 unsigned long i, cnt; 47 ktime_t time; 48 49 time = ktime_get(); 50 for (cnt = i = 0; i < len; cnt++) { 51 i = find_first_bit(bitmap, len); 52 __clear_bit(i, bitmap); 53 } 54 time = ktime_get() - time; 55 pr_err("find_first_bit: %18llu ns, %6ld iterations\n", time, 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 ktime_t time; 64 65 time = ktime_get(); 66 for (cnt = i = 0; i < BITMAP_LEN; cnt++) 67 i = find_next_bit(bitmap, BITMAP_LEN, i) + 1; 68 time = ktime_get() - time; 69 pr_err("find_next_bit: %18llu ns, %6ld iterations\n", time, cnt); 70 71 return 0; 72 } 73 74 static int __init test_find_next_zero_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_zero_bit(bitmap, len, i) + 1; 82 time = ktime_get() - time; 83 pr_err("find_next_zero_bit: %18llu ns, %6ld iterations\n", time, cnt); 84 85 return 0; 86 } 87 88 static int __init test_find_last_bit(const void *bitmap, unsigned long len) 89 { 90 unsigned long l, cnt = 0; 91 ktime_t time; 92 93 time = ktime_get(); 94 do { 95 cnt++; 96 l = find_last_bit(bitmap, len); 97 if (l >= len) 98 break; 99 len = l; 100 } while (len); 101 time = ktime_get() - time; 102 pr_err("find_last_bit: %18llu ns, %6ld iterations\n", time, cnt); 103 104 return 0; 105 } 106 107 static int __init test_find_next_and_bit(const void *bitmap, 108 const void *bitmap2, unsigned long len) 109 { 110 unsigned long i, cnt; 111 ktime_t time; 112 113 time = ktime_get(); 114 for (cnt = i = 0; i < BITMAP_LEN; cnt++) 115 i = find_next_and_bit(bitmap, bitmap2, BITMAP_LEN, i + 1); 116 time = ktime_get() - time; 117 pr_err("find_next_and_bit: %18llu ns, %6ld iterations\n", time, cnt); 118 119 return 0; 120 } 121 122 static int __init find_bit_test(void) 123 { 124 unsigned long nbits = BITMAP_LEN / SPARSE; 125 126 pr_err("\nStart testing find_bit() with random-filled bitmap\n"); 127 128 get_random_bytes(bitmap, sizeof(bitmap)); 129 get_random_bytes(bitmap2, sizeof(bitmap2)); 130 131 test_find_next_bit(bitmap, BITMAP_LEN); 132 test_find_next_zero_bit(bitmap, BITMAP_LEN); 133 test_find_last_bit(bitmap, BITMAP_LEN); 134 135 /* 136 * test_find_first_bit() may take some time, so 137 * traverse only part of bitmap to avoid soft lockup. 138 */ 139 test_find_first_bit(bitmap, BITMAP_LEN / 10); 140 test_find_next_and_bit(bitmap, bitmap2, BITMAP_LEN); 141 142 pr_err("\nStart testing find_bit() with sparse bitmap\n"); 143 144 bitmap_zero(bitmap, BITMAP_LEN); 145 bitmap_zero(bitmap2, BITMAP_LEN); 146 147 while (nbits--) { 148 __set_bit(prandom_u32() % BITMAP_LEN, bitmap); 149 __set_bit(prandom_u32() % BITMAP_LEN, bitmap2); 150 } 151 152 test_find_next_bit(bitmap, BITMAP_LEN); 153 test_find_next_zero_bit(bitmap, BITMAP_LEN); 154 test_find_last_bit(bitmap, BITMAP_LEN); 155 test_find_first_bit(bitmap, BITMAP_LEN); 156 test_find_next_and_bit(bitmap, bitmap2, BITMAP_LEN); 157 158 /* 159 * Everything is OK. Return error just to let user run benchmark 160 * again without annoying rmmod. 161 */ 162 return -EINVAL; 163 } 164 module_init(find_bit_test); 165 166 MODULE_LICENSE("GPL"); 167