15b497af4SThomas Gleixner // SPDX-License-Identifier: GPL-2.0-only 2dceeb3e7SYury Norov /* 3dceeb3e7SYury Norov * Test for find_*_bit functions. 4dceeb3e7SYury Norov * 5dceeb3e7SYury Norov * Copyright (c) 2017 Cavium. 6dceeb3e7SYury Norov */ 7dceeb3e7SYury Norov 8dceeb3e7SYury Norov /* 9dceeb3e7SYury Norov * find_bit functions are widely used in kernel, so the successful boot 10dceeb3e7SYury Norov * is good enough test for correctness. 11dceeb3e7SYury Norov * 12dceeb3e7SYury Norov * This test is focused on performance of traversing bitmaps. Two typical 13dceeb3e7SYury Norov * scenarios are reproduced: 14dceeb3e7SYury Norov * - randomly filled bitmap with approximately equal number of set and 15dceeb3e7SYury Norov * cleared bits; 16dceeb3e7SYury Norov * - sparse bitmap with few set bits at random positions. 17dceeb3e7SYury Norov */ 18dceeb3e7SYury Norov 19dceeb3e7SYury Norov #include <linux/bitops.h> 20dceeb3e7SYury Norov #include <linux/kernel.h> 21dceeb3e7SYury Norov #include <linux/list.h> 22dceeb3e7SYury Norov #include <linux/module.h> 23dceeb3e7SYury Norov #include <linux/printk.h> 24dceeb3e7SYury Norov #include <linux/random.h> 25dceeb3e7SYury Norov 26dceeb3e7SYury Norov #define BITMAP_LEN (4096UL * 8 * 10) 27dceeb3e7SYury Norov #define SPARSE 500 28dceeb3e7SYury Norov 29dceeb3e7SYury Norov static DECLARE_BITMAP(bitmap, BITMAP_LEN) __initdata; 300ade34c3SClement Courbet static DECLARE_BITMAP(bitmap2, BITMAP_LEN) __initdata; 31dceeb3e7SYury Norov 32dceeb3e7SYury Norov /* 33dceeb3e7SYury Norov * This is Schlemiel the Painter's algorithm. It should be called after 34dceeb3e7SYury Norov * all other tests for the same bitmap because it sets all bits of bitmap to 1. 35dceeb3e7SYury Norov */ 36dceeb3e7SYury Norov static int __init test_find_first_bit(void *bitmap, unsigned long len) 37dceeb3e7SYury Norov { 38dceeb3e7SYury Norov unsigned long i, cnt; 3915ff67bfSYury Norov ktime_t time; 40dceeb3e7SYury Norov 4115ff67bfSYury Norov time = ktime_get(); 42dceeb3e7SYury Norov for (cnt = i = 0; i < len; cnt++) { 43dceeb3e7SYury Norov i = find_first_bit(bitmap, len); 44dceeb3e7SYury Norov __clear_bit(i, bitmap); 45dceeb3e7SYury Norov } 4615ff67bfSYury Norov time = ktime_get() - time; 4715ff67bfSYury Norov pr_err("find_first_bit: %18llu ns, %6ld iterations\n", time, cnt); 48dceeb3e7SYury Norov 49dceeb3e7SYury Norov return 0; 50dceeb3e7SYury Norov } 51dceeb3e7SYury Norov 52*f68edc92SYury Norov static int __init test_find_first_and_bit(void *bitmap, const void *bitmap2, unsigned long len) 53*f68edc92SYury Norov { 54*f68edc92SYury Norov static DECLARE_BITMAP(cp, BITMAP_LEN) __initdata; 55*f68edc92SYury Norov unsigned long i, cnt; 56*f68edc92SYury Norov ktime_t time; 57*f68edc92SYury Norov 58*f68edc92SYury Norov bitmap_copy(cp, bitmap, BITMAP_LEN); 59*f68edc92SYury Norov 60*f68edc92SYury Norov time = ktime_get(); 61*f68edc92SYury Norov for (cnt = i = 0; i < len; cnt++) { 62*f68edc92SYury Norov i = find_first_and_bit(cp, bitmap2, len); 63*f68edc92SYury Norov __clear_bit(i, cp); 64*f68edc92SYury Norov } 65*f68edc92SYury Norov time = ktime_get() - time; 66*f68edc92SYury Norov pr_err("find_first_and_bit: %18llu ns, %6ld iterations\n", time, cnt); 67*f68edc92SYury Norov 68*f68edc92SYury Norov return 0; 69*f68edc92SYury Norov } 70*f68edc92SYury Norov 71dceeb3e7SYury Norov static int __init test_find_next_bit(const void *bitmap, unsigned long len) 72dceeb3e7SYury Norov { 73dceeb3e7SYury Norov unsigned long i, cnt; 7415ff67bfSYury Norov ktime_t time; 75dceeb3e7SYury Norov 7615ff67bfSYury Norov time = ktime_get(); 77dceeb3e7SYury Norov for (cnt = i = 0; i < BITMAP_LEN; cnt++) 78dceeb3e7SYury Norov i = find_next_bit(bitmap, BITMAP_LEN, i) + 1; 7915ff67bfSYury Norov time = ktime_get() - time; 8015ff67bfSYury Norov pr_err("find_next_bit: %18llu ns, %6ld iterations\n", time, cnt); 81dceeb3e7SYury Norov 82dceeb3e7SYury Norov return 0; 83dceeb3e7SYury Norov } 84dceeb3e7SYury Norov 85dceeb3e7SYury Norov static int __init test_find_next_zero_bit(const void *bitmap, unsigned long len) 86dceeb3e7SYury Norov { 87dceeb3e7SYury Norov unsigned long i, cnt; 8815ff67bfSYury Norov ktime_t time; 89dceeb3e7SYury Norov 9015ff67bfSYury Norov time = ktime_get(); 91dceeb3e7SYury Norov for (cnt = i = 0; i < BITMAP_LEN; cnt++) 92dceeb3e7SYury Norov i = find_next_zero_bit(bitmap, len, i) + 1; 9315ff67bfSYury Norov time = ktime_get() - time; 9415ff67bfSYury Norov pr_err("find_next_zero_bit: %18llu ns, %6ld iterations\n", time, cnt); 95dceeb3e7SYury Norov 96dceeb3e7SYury Norov return 0; 97dceeb3e7SYury Norov } 98dceeb3e7SYury Norov 99dceeb3e7SYury Norov static int __init test_find_last_bit(const void *bitmap, unsigned long len) 100dceeb3e7SYury Norov { 101dceeb3e7SYury Norov unsigned long l, cnt = 0; 10215ff67bfSYury Norov ktime_t time; 103dceeb3e7SYury Norov 10415ff67bfSYury Norov time = ktime_get(); 105dceeb3e7SYury Norov do { 106dceeb3e7SYury Norov cnt++; 107dceeb3e7SYury Norov l = find_last_bit(bitmap, len); 108dceeb3e7SYury Norov if (l >= len) 109dceeb3e7SYury Norov break; 110dceeb3e7SYury Norov len = l; 111dceeb3e7SYury Norov } while (len); 11215ff67bfSYury Norov time = ktime_get() - time; 11315ff67bfSYury Norov pr_err("find_last_bit: %18llu ns, %6ld iterations\n", time, cnt); 114dceeb3e7SYury Norov 115dceeb3e7SYury Norov return 0; 116dceeb3e7SYury Norov } 117dceeb3e7SYury Norov 1180ade34c3SClement Courbet static int __init test_find_next_and_bit(const void *bitmap, 1190ade34c3SClement Courbet const void *bitmap2, unsigned long len) 1200ade34c3SClement Courbet { 1210ade34c3SClement Courbet unsigned long i, cnt; 122439e00b7SYury Norov ktime_t time; 1230ade34c3SClement Courbet 124439e00b7SYury Norov time = ktime_get(); 1250ade34c3SClement Courbet for (cnt = i = 0; i < BITMAP_LEN; cnt++) 1260ade34c3SClement Courbet i = find_next_and_bit(bitmap, bitmap2, BITMAP_LEN, i + 1); 127439e00b7SYury Norov time = ktime_get() - time; 128439e00b7SYury Norov pr_err("find_next_and_bit: %18llu ns, %6ld iterations\n", time, cnt); 1290ade34c3SClement Courbet 1300ade34c3SClement Courbet return 0; 1310ade34c3SClement Courbet } 1320ade34c3SClement Courbet 133dceeb3e7SYury Norov static int __init find_bit_test(void) 134dceeb3e7SYury Norov { 135dceeb3e7SYury Norov unsigned long nbits = BITMAP_LEN / SPARSE; 136dceeb3e7SYury Norov 137dceeb3e7SYury Norov pr_err("\nStart testing find_bit() with random-filled bitmap\n"); 138dceeb3e7SYury Norov 139dceeb3e7SYury Norov get_random_bytes(bitmap, sizeof(bitmap)); 1400ade34c3SClement Courbet get_random_bytes(bitmap2, sizeof(bitmap2)); 141dceeb3e7SYury Norov 142dceeb3e7SYury Norov test_find_next_bit(bitmap, BITMAP_LEN); 143dceeb3e7SYury Norov test_find_next_zero_bit(bitmap, BITMAP_LEN); 144dceeb3e7SYury Norov test_find_last_bit(bitmap, BITMAP_LEN); 1454ba281d5SYury Norov 1464ba281d5SYury Norov /* 1474ba281d5SYury Norov * test_find_first_bit() may take some time, so 1484ba281d5SYury Norov * traverse only part of bitmap to avoid soft lockup. 1494ba281d5SYury Norov */ 1504ba281d5SYury Norov test_find_first_bit(bitmap, BITMAP_LEN / 10); 151*f68edc92SYury Norov test_find_first_and_bit(bitmap, bitmap2, BITMAP_LEN / 2); 1520ade34c3SClement Courbet test_find_next_and_bit(bitmap, bitmap2, BITMAP_LEN); 153dceeb3e7SYury Norov 154dceeb3e7SYury Norov pr_err("\nStart testing find_bit() with sparse bitmap\n"); 155dceeb3e7SYury Norov 156dceeb3e7SYury Norov bitmap_zero(bitmap, BITMAP_LEN); 1570ade34c3SClement Courbet bitmap_zero(bitmap2, BITMAP_LEN); 158dceeb3e7SYury Norov 1590ade34c3SClement Courbet while (nbits--) { 160dceeb3e7SYury Norov __set_bit(prandom_u32() % BITMAP_LEN, bitmap); 1610ade34c3SClement Courbet __set_bit(prandom_u32() % BITMAP_LEN, bitmap2); 1620ade34c3SClement Courbet } 163dceeb3e7SYury Norov 164dceeb3e7SYury Norov test_find_next_bit(bitmap, BITMAP_LEN); 165dceeb3e7SYury Norov test_find_next_zero_bit(bitmap, BITMAP_LEN); 166dceeb3e7SYury Norov test_find_last_bit(bitmap, BITMAP_LEN); 167dceeb3e7SYury Norov test_find_first_bit(bitmap, BITMAP_LEN); 168*f68edc92SYury Norov test_find_first_and_bit(bitmap, bitmap2, BITMAP_LEN); 1690ade34c3SClement Courbet test_find_next_and_bit(bitmap, bitmap2, BITMAP_LEN); 170dceeb3e7SYury Norov 17115ff67bfSYury Norov /* 17215ff67bfSYury Norov * Everything is OK. Return error just to let user run benchmark 17315ff67bfSYury Norov * again without annoying rmmod. 17415ff67bfSYury Norov */ 17515ff67bfSYury Norov return -EINVAL; 176dceeb3e7SYury Norov } 177dceeb3e7SYury Norov module_init(find_bit_test); 178dceeb3e7SYury Norov 179dceeb3e7SYury Norov MODULE_LICENSE("GPL"); 180