linux-kernel - [PATCH 2/5] lib/bitmap: add tests for find_nth

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite for Android: free password hash cracker in your pocket

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Message-Id: <20220706182300.70862-3-yury.norov@gmail.com>
Date:   Wed,  6 Jul 2022 11:22:57 -0700
From:   Yury Norov <yury.norov@...il.com>
To:     linux-kernel@...r.kernel.org,
        Alexander Lobakin <alexandr.lobakin@...el.com>,
        Andy Shevchenko <andriy.shevchenko@...ux.intel.com>,
        Arnd Bergmann <arnd@...db.de>, David Gow <davidgow@...gle.com>,
        Eric Dumazet <edumazet@...gle.com>,
        Isabella Basso <isabbasso@...eup.net>,
        Kees Cook <keescook@...omium.org>,
        Keith Busch <kbusch@...nel.org>,
        Kumar Kartikeya Dwivedi <memxor@...il.com>,
        Marco Elver <elver@...gle.com>,
        Mark Rutland <mark.rutland@....com>,
        Rasmus Villemoes <linux@...musvillemoes.dk>,
        Steven Rostedt <rostedt@...dmis.org>,
        Toke Høiland-Jørgensen <toke@...hat.com>
Cc:     Yury Norov <yury.norov@...il.com>
Subject: [PATCH 2/5] lib/bitmap: add tests for find_nth_bit()

Add functional and performance tests for find_nth_bit().

Signed-off-by: Yury Norov <yury.norov@...il.com>
---
 lib/find_bit_benchmark.c | 17 +++++++++++++++++
 lib/test_bitmap.c        | 36 ++++++++++++++++++++++++++++++++++--
 2 files changed, 51 insertions(+), 2 deletions(-)

diff --git a/lib/find_bit_benchmark.c b/lib/find_bit_benchmark.c
index db904b57d4b8..aad769c6ca84 100644
--- a/lib/find_bit_benchmark.c
+++ b/lib/find_bit_benchmark.c
@@ -115,6 +115,22 @@ static int __init test_find_last_bit(const void *bitmap, unsigned long len)
 	return 0;
 }
 
+static int __init test_find_nth_bit(const unsigned long *bitmap, unsigned long len)
+{
+	unsigned long l, n, w = bitmap_weight(bitmap, len);
+	ktime_t time;
+
+	time = ktime_get();
+	for (n = 1; n <= w; n++) {
+		l = find_nth_bit(bitmap, len, n);
+		WARN_ON(l >= len);
+	}
+	time = ktime_get() - time;
+	pr_err("find_nth_bit:       %18llu ns, %6ld iterations\n", time, w);
+
+	return 0;
+}
+
 static int __init test_find_next_and_bit(const void *bitmap,
 		const void *bitmap2, unsigned long len)
 {
@@ -142,6 +158,7 @@ static int __init find_bit_test(void)
 	test_find_next_bit(bitmap, BITMAP_LEN);
 	test_find_next_zero_bit(bitmap, BITMAP_LEN);
 	test_find_last_bit(bitmap, BITMAP_LEN);
+	test_find_nth_bit(bitmap, BITMAP_LEN/10);
 
 	/*
 	 * test_find_first_bit() may take some time, so
diff --git a/lib/test_bitmap.c b/lib/test_bitmap.c
index d5923a640457..b4b53d8c66ae 100644
--- a/lib/test_bitmap.c
+++ b/lib/test_bitmap.c
@@ -16,6 +16,8 @@
 
 #include "../tools/testing/selftests/kselftest_module.h"
 
+#define EXP1_IN_BITS	(sizeof(exp1) * 8)
+
 KSTM_MODULE_GLOBALS();
 
 static char pbl_buffer[PAGE_SIZE] __initdata;
@@ -219,6 +221,36 @@ static void __init test_zero_clear(void)
 	expect_eq_pbl("", bmap, 1024);
 }
 
+static void __init test_find_nth_bit(void)
+{
+	unsigned long b, bit, cnt = 0;
+	DECLARE_BITMAP(bmap, 64 * 3);
+
+	bitmap_zero(bmap, 64 * 3);
+	__set_bit(10, bmap);
+	__set_bit(20, bmap);
+	__set_bit(30, bmap);
+	__set_bit(40, bmap);
+	__set_bit(50, bmap);
+	__set_bit(60, bmap);
+	__set_bit(80, bmap);
+	__set_bit(123, bmap);
+
+	expect_eq_uint(10,  find_nth_bit(bmap, 64 * 3, 1));
+	expect_eq_uint(20,  find_nth_bit(bmap, 64 * 3, 2));
+	expect_eq_uint(30,  find_nth_bit(bmap, 64 * 3, 3));
+	expect_eq_uint(40,  find_nth_bit(bmap, 64 * 3, 4));
+	expect_eq_uint(50,  find_nth_bit(bmap, 64 * 3, 5));
+	expect_eq_uint(60,  find_nth_bit(bmap, 64 * 3, 6));
+	expect_eq_uint(80,  find_nth_bit(bmap, 64 * 3, 7));
+	expect_eq_uint(123, find_nth_bit(bmap, 64 * 3, 8));
+
+	for_each_set_bit(bit, exp1, EXP1_IN_BITS) {
+		b = find_nth_bit(exp1, EXP1_IN_BITS, ++cnt);
+		expect_eq_uint(b, bit);
+	}
+}
+
 static void __init test_fill_set(void)
 {
 	DECLARE_BITMAP(bmap, 1024);
@@ -557,8 +589,6 @@ static void __init test_bitmap_parse(void)
 	}
 }
 
-#define EXP1_IN_BITS	(sizeof(exp1) * 8)
-
 static void __init test_bitmap_arr32(void)
 {
 	unsigned int nbits, next_bit;
@@ -884,6 +914,8 @@ static void __init selftest(void)
 	test_for_each_set_clump8();
 	test_bitmap_cut();
 	test_bitmap_print_buf();
+
+	test_find_nth_bit();
 }
 
 KSTM_MODULE_LOADERS(test_bitmap);
-- 
2.34.1