the-tree/lib/find_bit_benchmark.c

0001 // SPDX-License-Identifier: GPL-2.0-only
0002 /*
0003  * Test for find_*_bit functions.
0004  *
0005  * Copyright (c) 2017 Cavium.
0006  */
0007
0008 /*
0009  * find_bit functions are widely used in kernel, so the successful boot
0010  * is good enough test for correctness.
0011  *
0012  * This test is focused on performance of traversing bitmaps. Two typical
0013  * scenarios are reproduced:
0014  * - randomly filled bitmap with approximately equal number of set and
0015  *   cleared bits;
0016  * - sparse bitmap with few set bits at random positions.
0017  */
0018
0019 #include <linux/bitops.h>
0020 #include <linux/kernel.h>
0021 #include <linux/list.h>
0022 #include <linux/module.h>
0023 #include <linux/printk.h>
0024 #include <linux/random.h>
0025
0026 #define BITMAP_LEN  (4096UL * 8 * 10)
0027 #define SPARSE      500
0028
0029 static DECLARE_BITMAP(bitmap, BITMAP_LEN) __initdata;
0030 static DECLARE_BITMAP(bitmap2, BITMAP_LEN) __initdata;
0031
0032 /*
0033  * This is Schlemiel the Painter's algorithm. It should be called after
0034  * all other tests for the same bitmap because it sets all bits of bitmap to 1.
0035  */
0036 static int __init test_find_first_bit(void *bitmap, unsigned long len)
0037 {
0038     unsigned long i, cnt;
0039     ktime_t time;
0040
0041     time = ktime_get();
0042     for (cnt = i = 0; i < len; cnt++) {
0043         i = find_first_bit(bitmap, len);
0044         __clear_bit(i, bitmap);
0045     }
0046     time = ktime_get() - time;
0047     pr_err("find_first_bit:     %18llu ns, %6ld iterations\n", time, cnt);
0048
0049     return 0;
0050 }
0051
0052 static int __init test_find_first_and_bit(void *bitmap, const void *bitmap2, unsigned long len)
0053 {
0054     static DECLARE_BITMAP(cp, BITMAP_LEN) __initdata;
0055     unsigned long i, cnt;
0056     ktime_t time;
0057
0058     bitmap_copy(cp, bitmap, BITMAP_LEN);
0059
0060     time = ktime_get();
0061     for (cnt = i = 0; i < len; cnt++) {
0062         i = find_first_and_bit(cp, bitmap2, len);
0063         __clear_bit(i, cp);
0064     }
0065     time = ktime_get() - time;
0066     pr_err("find_first_and_bit: %18llu ns, %6ld iterations\n", time, cnt);
0067
0068     return 0;
0069 }
0070
0071 static int __init test_find_next_bit(const void *bitmap, unsigned long len)
0072 {
0073     unsigned long i, cnt;
0074     ktime_t time;
0075
0076     time = ktime_get();
0077     for (cnt = i = 0; i < BITMAP_LEN; cnt++)
0078         i = find_next_bit(bitmap, BITMAP_LEN, i) + 1;
0079     time = ktime_get() - time;
0080     pr_err("find_next_bit:      %18llu ns, %6ld iterations\n", time, cnt);
0081
0082     return 0;
0083 }
0084
0085 static int __init test_find_next_zero_bit(const void *bitmap, unsigned long len)
0086 {
0087     unsigned long i, cnt;
0088     ktime_t time;
0089
0090     time = ktime_get();
0091     for (cnt = i = 0; i < BITMAP_LEN; cnt++)
0092         i = find_next_zero_bit(bitmap, len, i) + 1;
0093     time = ktime_get() - time;
0094     pr_err("find_next_zero_bit: %18llu ns, %6ld iterations\n", time, cnt);
0095
0096     return 0;
0097 }
0098
0099 static int __init test_find_last_bit(const void *bitmap, unsigned long len)
0100 {
0101     unsigned long l, cnt = 0;
0102     ktime_t time;
0103
0104     time = ktime_get();
0105     do {
0106         cnt++;
0107         l = find_last_bit(bitmap, len);
0108         if (l >= len)
0109             break;
0110         len = l;
0111     } while (len);
0112     time = ktime_get() - time;
0113     pr_err("find_last_bit:      %18llu ns, %6ld iterations\n", time, cnt);
0114
0115     return 0;
0116 }
0117
0118 static int __init test_find_next_and_bit(const void *bitmap,
0119         const void *bitmap2, unsigned long len)
0120 {
0121     unsigned long i, cnt;
0122     ktime_t time;
0123
0124     time = ktime_get();
0125     for (cnt = i = 0; i < BITMAP_LEN; cnt++)
0126         i = find_next_and_bit(bitmap, bitmap2, BITMAP_LEN, i + 1);
0127     time = ktime_get() - time;
0128     pr_err("find_next_and_bit:  %18llu ns, %6ld iterations\n", time, cnt);
0129
0130     return 0;
0131 }
0132
0133 static int __init find_bit_test(void)
0134 {
0135     unsigned long nbits = BITMAP_LEN / SPARSE;
0136
0137     pr_err("\nStart testing find_bit() with random-filled bitmap\n");
0138
0139     get_random_bytes(bitmap, sizeof(bitmap));
0140     get_random_bytes(bitmap2, sizeof(bitmap2));
0141
0142     test_find_next_bit(bitmap, BITMAP_LEN);
0143     test_find_next_zero_bit(bitmap, BITMAP_LEN);
0144     test_find_last_bit(bitmap, BITMAP_LEN);
0145
0146     /*
0147      * test_find_first_bit() may take some time, so
0148      * traverse only part of bitmap to avoid soft lockup.
0149      */
0150     test_find_first_bit(bitmap, BITMAP_LEN / 10);
0151     test_find_first_and_bit(bitmap, bitmap2, BITMAP_LEN / 2);
0152     test_find_next_and_bit(bitmap, bitmap2, BITMAP_LEN);
0153
0154     pr_err("\nStart testing find_bit() with sparse bitmap\n");
0155
0156     bitmap_zero(bitmap, BITMAP_LEN);
0157     bitmap_zero(bitmap2, BITMAP_LEN);
0158
0159     while (nbits--) {
0160         __set_bit(prandom_u32() % BITMAP_LEN, bitmap);
0161         __set_bit(prandom_u32() % BITMAP_LEN, bitmap2);
0162     }
0163
0164     test_find_next_bit(bitmap, BITMAP_LEN);
0165     test_find_next_zero_bit(bitmap, BITMAP_LEN);
0166     test_find_last_bit(bitmap, BITMAP_LEN);
0167     test_find_first_bit(bitmap, BITMAP_LEN);
0168     test_find_first_and_bit(bitmap, bitmap2, BITMAP_LEN);
0169     test_find_next_and_bit(bitmap, bitmap2, BITMAP_LEN);
0170
0171     /*
0172      * Everything is OK. Return error just to let user run benchmark
0173      * again without annoying rmmod.
0174      */
0175     return -EINVAL;
0176 }
0177 module_init(find_bit_test);
0178
0179 MODULE_LICENSE("GPL");