lib/test_find_bit.c

   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
  39 /*
  40  * This is Schlemiel the Painter's algorithm. It should be called after
  41  * all other tests for the same bitmap because it sets all bits of bitmap to 1.
  42  */
  43 static int __init test_find_first_bit(void *bitmap, unsigned long len)
  44 {
  45         unsigned long i, cnt;
  46         cycles_t cycles;
  47
  48         cycles = get_cycles();
  49         for (cnt = i = 0; i < len; cnt++) {
  50                 i = find_first_bit(bitmap, len);
  51                 __clear_bit(i, bitmap);
  52         }
  53         cycles = get_cycles() - cycles;
  54         pr_err("find_first_bit:\t\t%llu cycles,\t%ld iterations\n",
  55                (u64)cycles, 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         cycles_t cycles;
  64
  65         cycles = get_cycles();
  66         for (cnt = i = 0; i < BITMAP_LEN; cnt++)
  67                 i = find_next_bit(bitmap, BITMAP_LEN, i) + 1;
  68         cycles = get_cycles() - cycles;
  69         pr_err("find_next_bit:\t\t%llu cycles,\t%ld iterations\n",
  70                (u64)cycles, cnt);
  71
  72         return 0;
  73 }
  74
  75 static int __init test_find_next_zero_bit(const void *bitmap, unsigned long len)
  76 {
  77         unsigned long i, cnt;
  78         cycles_t cycles;
  79
  80         cycles = get_cycles();
  81         for (cnt = i = 0; i < BITMAP_LEN; cnt++)
  82                 i = find_next_zero_bit(bitmap, len, i) + 1;
  83         cycles = get_cycles() - cycles;
  84         pr_err("find_next_zero_bit:\t%llu cycles,\t%ld iterations\n",
  85                (u64)cycles, cnt);
  86
  87         return 0;
  88 }
  89
  90 static int __init test_find_last_bit(const void *bitmap, unsigned long len)
  91 {
  92         unsigned long l, cnt = 0;
  93         cycles_t cycles;
  94
  95         cycles = get_cycles();
  96         do {
  97                 cnt++;
  98                 l = find_last_bit(bitmap, len);
  99                 if (l >= len)
 100                         break;
 101                 len = l;
 102         } while (len);
 103         cycles = get_cycles() - cycles;
 104         pr_err("find_last_bit:\t\t%llu cycles,\t%ld iterations\n",
 105                (u64)cycles, cnt);
 106
 107         return 0;
 108 }
 109
 110 static int __init find_bit_test(void)
 111 {
 112         unsigned long nbits = BITMAP_LEN / SPARSE;
 113
 114         pr_err("\nStart testing find_bit() with random-filled bitmap\n");
 115
 116         get_random_bytes(bitmap, sizeof(bitmap));
 117
 118         test_find_next_bit(bitmap, BITMAP_LEN);
 119         test_find_next_zero_bit(bitmap, BITMAP_LEN);
 120         test_find_last_bit(bitmap, BITMAP_LEN);
 121         test_find_first_bit(bitmap, BITMAP_LEN);
 122
 123         pr_err("\nStart testing find_bit() with sparse bitmap\n");
 124
 125         bitmap_zero(bitmap, BITMAP_LEN);
 126
 127         while (nbits--)
 128                 __set_bit(prandom_u32() % BITMAP_LEN, bitmap);
 129
 130         test_find_next_bit(bitmap, BITMAP_LEN);
 131         test_find_next_zero_bit(bitmap, BITMAP_LEN);
 132         test_find_last_bit(bitmap, BITMAP_LEN);
 133         test_find_first_bit(bitmap, BITMAP_LEN);
 134
 135         return 0;
 136 }
 137 module_init(find_bit_test);
 138
 139 static void __exit test_find_bit_cleanup(void)
 140 {
 141 }
 142 module_exit(test_find_bit_cleanup);
 143
 144 MODULE_LICENSE("GPL");