lib/find_bit_benchmark.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 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");