LXR linux/lib/find_bit

   1// SPDX-License-Identifier: GPL-2.0-only
   2/*
   3 * Test for find_*_bit functions.
   4 *
   5 * Copyright (c) 2017 Cavium.
   6 */
   7
   8/*
   9 * find_bit functions are widely used in kernel, so the successful boot
  10 * is good enough test for correctness.
  11 *
  12 * This test is focused on performance of traversing bitmaps. Two typical
  13 * scenarios are reproduced:
  14 * - randomly filled bitmap with approximately equal number of set and
  15 *   cleared bits;
  16 * - sparse bitmap with few set bits at random positions.
  17 */
  18
  19#include <linux/bitops.h>
  20#include <linux/kernel.h>
  21#include <linux/list.h>
  22#include <linux/module.h>
  23#include <linux/printk.h>
  24#include <linux/random.h>
  25
  26#define BITMAP_LEN      (4096UL * 8 * 10)
  27#define SPARSE          500
  28
  29static DECLARE_BITMAP(bitmap, BITMAP_LEN) __initdata;
  30static DECLARE_BITMAP(bitmap2, BITMAP_LEN) __initdata;
  31
  32/*
  33 * This is Schlemiel the Painter's algorithm. It should be called after
  34 * all other tests for the same bitmap because it sets all bits of bitmap to 1.
  35 */
  36static int __init test_find_first_bit(void *bitmap, unsigned long len)
  37{
  38        unsigned long i, cnt;
  39        ktime_t time;
  40
  41        time = ktime_get();
  42        for (cnt = i = 0; i < len; cnt++) {
  43                i = find_first_bit(bitmap, len);
  44                __clear_bit(i, bitmap);
  45        }
  46        time = ktime_get() - time;
  47        pr_err("find_first_bit:     %18llu ns, %6ld iterations\n", time, cnt);
  48
  49        return 0;
  50}
  51
  52static int __init test_find_next_bit(const void *bitmap, unsigned long len)
  53{
  54        unsigned long i, cnt;
  55        ktime_t time;
  56
  57        time = ktime_get();
  58        for (cnt = i = 0; i < BITMAP_LEN; cnt++)
  59                i = find_next_bit(bitmap, BITMAP_LEN, i) + 1;
  60        time = ktime_get() - time;
  61        pr_err("find_next_bit:      %18llu ns, %6ld iterations\n", time, cnt);
  62
  63        return 0;
  64}
  65
  66static int __init test_find_next_zero_bit(const void *bitmap, unsigned long len)
  67{
  68        unsigned long i, cnt;
  69        ktime_t time;
  70
  71        time = ktime_get();
  72        for (cnt = i = 0; i < BITMAP_LEN; cnt++)
  73                i = find_next_zero_bit(bitmap, len, i) + 1;
  74        time = ktime_get() - time;
  75        pr_err("find_next_zero_bit: %18llu ns, %6ld iterations\n", time, cnt);
  76
  77        return 0;
  78}
  79
  80static int __init test_find_last_bit(const void *bitmap, unsigned long len)
  81{
  82        unsigned long l, cnt = 0;
  83        ktime_t time;
  84
  85        time = ktime_get();
  86        do {
  87                cnt++;
  88                l = find_last_bit(bitmap, len);
  89                if (l >= len)
  90                        break;
  91                len = l;
  92        } while (len);
  93        time = ktime_get() - time;
  94        pr_err("find_last_bit:      %18llu ns, %6ld iterations\n", time, cnt);
  95
  96        return 0;
  97}
  98
  99static int __init test_find_next_and_bit(const void *bitmap,
 100                const void *bitmap2, unsigned long len)
 101{
 102        unsigned long i, cnt;
 103        ktime_t time;
 104
 105        time = ktime_get();
 106        for (cnt = i = 0; i < BITMAP_LEN; cnt++)
 107                i = find_next_and_bit(bitmap, bitmap2, BITMAP_LEN, i + 1);
 108        time = ktime_get() - time;
 109        pr_err("find_next_and_bit:  %18llu ns, %6ld iterations\n", time, cnt);
 110
 111        return 0;
 112}
 113
 114static int __init find_bit_test(void)
 115{
 116        unsigned long nbits = BITMAP_LEN / SPARSE;
 117
 118        pr_err("\nStart testing find_bit() with random-filled bitmap\n");
 119
 120        get_random_bytes(bitmap, sizeof(bitmap));
 121        get_random_bytes(bitmap2, sizeof(bitmap2));
 122
 123        test_find_next_bit(bitmap, BITMAP_LEN);
 124        test_find_next_zero_bit(bitmap, BITMAP_LEN);
 125        test_find_last_bit(bitmap, BITMAP_LEN);
 126
 127        /*
 128         * test_find_first_bit() may take some time, so
 129         * traverse only part of bitmap to avoid soft lockup.
 130         */
 131        test_find_first_bit(bitmap, BITMAP_LEN / 10);
 132        test_find_next_and_bit(bitmap, bitmap2, BITMAP_LEN);
 133
 134        pr_err("\nStart testing find_bit() with sparse bitmap\n");
 135
 136        bitmap_zero(bitmap, BITMAP_LEN);
 137        bitmap_zero(bitmap2, BITMAP_LEN);
 138
 139        while (nbits--) {
 140                __set_bit(prandom_u32() % BITMAP_LEN, bitmap);
 141                __set_bit(prandom_u32() % BITMAP_LEN, bitmap2);
 142        }
 143
 144        test_find_next_bit(bitmap, BITMAP_LEN);
 145        test_find_next_zero_bit(bitmap, BITMAP_LEN);
 146        test_find_last_bit(bitmap, BITMAP_LEN);
 147        test_find_first_bit(bitmap, BITMAP_LEN);
 148        test_find_next_and_bit(bitmap, bitmap2, BITMAP_LEN);
 149
 150        /*
 151         * Everything is OK. Return error just to let user run benchmark
 152         * again without annoying rmmod.
 153         */
 154        return -EINVAL;
 155}
 156module_init(find_bit_test);
 157
 158MODULE_LICENSE("GPL");
 159