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