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