1dceeb3e7SYury Norov /* 2dceeb3e7SYury Norov * Test for find_*_bit functions. 3dceeb3e7SYury Norov * 4dceeb3e7SYury Norov * Copyright (c) 2017 Cavium. 5dceeb3e7SYury Norov * 6dceeb3e7SYury Norov * This program is free software; you can redistribute it and/or 7dceeb3e7SYury Norov * modify it under the terms of version 2 of the GNU General Public 8dceeb3e7SYury Norov * License as published by the Free Software Foundation. 9dceeb3e7SYury Norov * 10dceeb3e7SYury Norov * This program is distributed in the hope that it will be useful, but 11dceeb3e7SYury Norov * WITHOUT ANY WARRANTY; without even the implied warranty of 12dceeb3e7SYury Norov * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 13dceeb3e7SYury Norov * General Public License for more details. 14dceeb3e7SYury Norov */ 15dceeb3e7SYury Norov 16dceeb3e7SYury Norov /* 17dceeb3e7SYury Norov * find_bit functions are widely used in kernel, so the successful boot 18dceeb3e7SYury Norov * is good enough test for correctness. 19dceeb3e7SYury Norov * 20dceeb3e7SYury Norov * This test is focused on performance of traversing bitmaps. Two typical 21dceeb3e7SYury Norov * scenarios are reproduced: 22dceeb3e7SYury Norov * - randomly filled bitmap with approximately equal number of set and 23dceeb3e7SYury Norov * cleared bits; 24dceeb3e7SYury Norov * - sparse bitmap with few set bits at random positions. 25dceeb3e7SYury Norov */ 26dceeb3e7SYury Norov 27dceeb3e7SYury Norov #include <linux/bitops.h> 28dceeb3e7SYury Norov #include <linux/kernel.h> 29dceeb3e7SYury Norov #include <linux/list.h> 30dceeb3e7SYury Norov #include <linux/module.h> 31dceeb3e7SYury Norov #include <linux/printk.h> 32dceeb3e7SYury Norov #include <linux/random.h> 33dceeb3e7SYury Norov 34dceeb3e7SYury Norov #define BITMAP_LEN (4096UL * 8 * 10) 35dceeb3e7SYury Norov #define SPARSE 500 36dceeb3e7SYury Norov 37dceeb3e7SYury Norov static DECLARE_BITMAP(bitmap, BITMAP_LEN) __initdata; 38dceeb3e7SYury Norov 39dceeb3e7SYury Norov /* 40dceeb3e7SYury Norov * This is Schlemiel the Painter's algorithm. It should be called after 41dceeb3e7SYury Norov * all other tests for the same bitmap because it sets all bits of bitmap to 1. 42dceeb3e7SYury Norov */ 43dceeb3e7SYury Norov static int __init test_find_first_bit(void *bitmap, unsigned long len) 44dceeb3e7SYury Norov { 45dceeb3e7SYury Norov unsigned long i, cnt; 4615ff67bfSYury Norov ktime_t time; 47dceeb3e7SYury Norov 4815ff67bfSYury Norov time = ktime_get(); 49dceeb3e7SYury Norov for (cnt = i = 0; i < len; cnt++) { 50dceeb3e7SYury Norov i = find_first_bit(bitmap, len); 51dceeb3e7SYury Norov __clear_bit(i, bitmap); 52dceeb3e7SYury Norov } 5315ff67bfSYury Norov time = ktime_get() - time; 5415ff67bfSYury Norov pr_err("find_first_bit: %18llu ns, %6ld iterations\n", time, cnt); 55dceeb3e7SYury Norov 56dceeb3e7SYury Norov return 0; 57dceeb3e7SYury Norov } 58dceeb3e7SYury Norov 59dceeb3e7SYury Norov static int __init test_find_next_bit(const void *bitmap, unsigned long len) 60dceeb3e7SYury Norov { 61dceeb3e7SYury Norov unsigned long i, cnt; 6215ff67bfSYury Norov ktime_t time; 63dceeb3e7SYury Norov 6415ff67bfSYury Norov time = ktime_get(); 65dceeb3e7SYury Norov for (cnt = i = 0; i < BITMAP_LEN; cnt++) 66dceeb3e7SYury Norov i = find_next_bit(bitmap, BITMAP_LEN, i) + 1; 6715ff67bfSYury Norov time = ktime_get() - time; 6815ff67bfSYury Norov pr_err("find_next_bit: %18llu ns, %6ld iterations\n", time, cnt); 69dceeb3e7SYury Norov 70dceeb3e7SYury Norov return 0; 71dceeb3e7SYury Norov } 72dceeb3e7SYury Norov 73dceeb3e7SYury Norov static int __init test_find_next_zero_bit(const void *bitmap, unsigned long len) 74dceeb3e7SYury Norov { 75dceeb3e7SYury Norov unsigned long i, cnt; 7615ff67bfSYury Norov ktime_t time; 77dceeb3e7SYury Norov 7815ff67bfSYury Norov time = ktime_get(); 79dceeb3e7SYury Norov for (cnt = i = 0; i < BITMAP_LEN; cnt++) 80dceeb3e7SYury Norov i = find_next_zero_bit(bitmap, len, i) + 1; 8115ff67bfSYury Norov time = ktime_get() - time; 8215ff67bfSYury Norov pr_err("find_next_zero_bit: %18llu ns, %6ld iterations\n", time, cnt); 83dceeb3e7SYury Norov 84dceeb3e7SYury Norov return 0; 85dceeb3e7SYury Norov } 86dceeb3e7SYury Norov 87dceeb3e7SYury Norov static int __init test_find_last_bit(const void *bitmap, unsigned long len) 88dceeb3e7SYury Norov { 89dceeb3e7SYury Norov unsigned long l, cnt = 0; 9015ff67bfSYury Norov ktime_t time; 91dceeb3e7SYury Norov 9215ff67bfSYury Norov time = ktime_get(); 93dceeb3e7SYury Norov do { 94dceeb3e7SYury Norov cnt++; 95dceeb3e7SYury Norov l = find_last_bit(bitmap, len); 96dceeb3e7SYury Norov if (l >= len) 97dceeb3e7SYury Norov break; 98dceeb3e7SYury Norov len = l; 99dceeb3e7SYury Norov } while (len); 10015ff67bfSYury Norov time = ktime_get() - time; 10115ff67bfSYury Norov pr_err("find_last_bit: %18llu ns, %6ld iterations\n", time, cnt); 102dceeb3e7SYury Norov 103dceeb3e7SYury Norov return 0; 104dceeb3e7SYury Norov } 105dceeb3e7SYury Norov 106dceeb3e7SYury Norov static int __init find_bit_test(void) 107dceeb3e7SYury Norov { 108dceeb3e7SYury Norov unsigned long nbits = BITMAP_LEN / SPARSE; 109dceeb3e7SYury Norov 110dceeb3e7SYury Norov pr_err("\nStart testing find_bit() with random-filled bitmap\n"); 111dceeb3e7SYury Norov 112dceeb3e7SYury Norov get_random_bytes(bitmap, sizeof(bitmap)); 113dceeb3e7SYury Norov 114dceeb3e7SYury Norov test_find_next_bit(bitmap, BITMAP_LEN); 115dceeb3e7SYury Norov test_find_next_zero_bit(bitmap, BITMAP_LEN); 116dceeb3e7SYury Norov test_find_last_bit(bitmap, BITMAP_LEN); 117dceeb3e7SYury Norov test_find_first_bit(bitmap, BITMAP_LEN); 118dceeb3e7SYury Norov 119dceeb3e7SYury Norov pr_err("\nStart testing find_bit() with sparse bitmap\n"); 120dceeb3e7SYury Norov 121dceeb3e7SYury Norov bitmap_zero(bitmap, BITMAP_LEN); 122dceeb3e7SYury Norov 123dceeb3e7SYury Norov while (nbits--) 124dceeb3e7SYury Norov __set_bit(prandom_u32() % BITMAP_LEN, bitmap); 125dceeb3e7SYury Norov 126dceeb3e7SYury Norov test_find_next_bit(bitmap, BITMAP_LEN); 127dceeb3e7SYury Norov test_find_next_zero_bit(bitmap, BITMAP_LEN); 128dceeb3e7SYury Norov test_find_last_bit(bitmap, BITMAP_LEN); 129dceeb3e7SYury Norov test_find_first_bit(bitmap, BITMAP_LEN); 130dceeb3e7SYury Norov 13115ff67bfSYury Norov /* 13215ff67bfSYury Norov * Everything is OK. Return error just to let user run benchmark 13315ff67bfSYury Norov * again without annoying rmmod. 13415ff67bfSYury Norov */ 13515ff67bfSYury Norov return -EINVAL; 136dceeb3e7SYury Norov } 137dceeb3e7SYury Norov module_init(find_bit_test); 138dceeb3e7SYury Norov 139dceeb3e7SYury Norov MODULE_LICENSE("GPL"); 140