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         cycles_t cycles;
 112
 113         cycles = get_cycles();
 114         for (cnt = i = 0; i < BITMAP_LEN; cnt++)
 115                 i = find_next_and_bit(bitmap, bitmap2, BITMAP_LEN, i+1);
 116         cycles = get_cycles() - cycles;
 117         pr_err("find_next_and_bit:\t\t%llu cycles, %ld iterations\n",
 118                 (u64)cycles, cnt);
 119
 120         return 0;
 121 }
 122
 123 static int __init find_bit_test(void)
 124 {
 125         unsigned long nbits = BITMAP_LEN / SPARSE;
 126
 127         pr_err("\nStart testing find_bit() with random-filled bitmap\n");
 128
 129         get_random_bytes(bitmap, sizeof(bitmap));
 130         get_random_bytes(bitmap2, sizeof(bitmap2));
 131
 132         test_find_next_bit(bitmap, BITMAP_LEN);
 133         test_find_next_zero_bit(bitmap, BITMAP_LEN);
 134         test_find_last_bit(bitmap, BITMAP_LEN);
 135
 136         /*
 137          * test_find_first_bit() may take some time, so
 138          * traverse only part of bitmap to avoid soft lockup.
 139          */
 140         test_find_first_bit(bitmap, BITMAP_LEN / 10);
 141         test_find_next_and_bit(bitmap, bitmap2, BITMAP_LEN);
 142
 143         pr_err("\nStart testing find_bit() with sparse bitmap\n");
 144
 145         bitmap_zero(bitmap, BITMAP_LEN);
 146         bitmap_zero(bitmap2, BITMAP_LEN);
 147
 148         while (nbits--) {
 149                 __set_bit(prandom_u32() % BITMAP_LEN, bitmap);
 150                 __set_bit(prandom_u32() % BITMAP_LEN, bitmap2);
 151         }
 152
 153         test_find_next_bit(bitmap, BITMAP_LEN);
 154         test_find_next_zero_bit(bitmap, BITMAP_LEN);
 155         test_find_last_bit(bitmap, BITMAP_LEN);
 156         test_find_first_bit(bitmap, BITMAP_LEN);
 157         test_find_next_and_bit(bitmap, bitmap2, BITMAP_LEN);
 158
 159         /*
 160          * Everything is OK. Return error just to let user run benchmark
 161          * again without annoying rmmod.
 162          */
 163         return -EINVAL;
 164 }
 165 module_init(find_bit_test);
 166
 167 MODULE_LICENSE("GPL");