linux-kernel - [PATCH v3 4/6] lib: Fix test_find_first_and_bit and test_find_next_and

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: Windows password security audit tool. GUI, reports in PDF.

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

Message-Id: <20240830191043.1028827-5-mathieu.desnoyers@efficios.com>
Date: Fri, 30 Aug 2024 15:10:41 -0400
From: Mathieu Desnoyers <mathieu.desnoyers@...icios.com>
To: Yury Norov <yury.norov@...il.com>,
	Rasmus Villemoes <linux@...musvillemoes.dk>
Cc: linux-kernel@...r.kernel.org,
	Mathieu Desnoyers <mathieu.desnoyers@...icios.com>
Subject: [PATCH v3 4/6] lib: Fix test_find_first_and_bit and test_find_next_and_bit benchmark

Modify test_find_first_bit so it modifies a local copy of bitmap rather
than modifying the input bitmap, which removes the requirement of
placing it last in the tests.

Calls to test_find_first_and_bit and test_find_next_and_bit are placed
after test_find_first_bit, which makes them use a bitmap entirely filled
rather than the expected bitmap (random-filled or sparse).

Use bitmap_alloc rather than a local static variable in test_find_first_bit
and test_find_first_and_bit. Only clear bits when find bit returns a
value within range, which causes an out-of-bound access otherwise.

Use BITMAP_LEN / 10 for all find_first tests to ensure they run within a
few ms each.

Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@...icios.com>
Cc: Yury Norov <yury.norov@...il.com>
Cc: Rasmus Villemoes <linux@...musvillemoes.dk>
---
Changes since v2:
- Use bitmap_alloc rather than a local static variable in test_find_first_bit
  and test_find_first_and_bit.
- Use BITMAP_LEN / 10 for all find_first tests.
- Use len parameter rather than BITMAP_LEN.
- Only clear bits when find bit returns a value within range.
---
 lib/find_bit_benchmark.c | 24 ++++++++++++++----------
 1 file changed, 14 insertions(+), 10 deletions(-)

diff --git a/lib/find_bit_benchmark.c b/lib/find_bit_benchmark.c
index d3fb09e6eff1..81d358fb459b 100644
--- a/lib/find_bit_benchmark.c
+++ b/lib/find_bit_benchmark.c
@@ -30,18 +30,21 @@ static DECLARE_BITMAP(bitmap, BITMAP_LEN) __initdata;
 static DECLARE_BITMAP(bitmap2, BITMAP_LEN) __initdata;
 
 /*
- * This is Schlemiel the Painter's algorithm. It should be called after
- * all other tests for the same bitmap because it sets all bits of bitmap to 1.
+ * This is Schlemiel the Painter's algorithm.
  */
 static int __init test_find_first_bit(void *bitmap, unsigned long len)
 {
+	unsigned long *cp __free(bitmap) = bitmap_alloc(len, GFP_KERNEL);
 	unsigned long i, cnt;
 	ktime_t time;
 
+	bitmap_copy(cp, bitmap, len);
+
 	time = ktime_get();
 	for (cnt = i = 0; i < len; cnt++) {
-		i = find_first_bit(bitmap, len);
-		__clear_bit(i, bitmap);
+		i = find_first_bit(cp, len);
+		if (i < len)
+			__clear_bit(i, cp);
 	}
 	time = ktime_get() - time;
 	pr_err("find_first_bit:     %18llu ns, %6ld iterations\n", time, cnt);
@@ -51,16 +54,17 @@ static int __init test_find_first_bit(void *bitmap, unsigned long len)
 
 static int __init test_find_first_and_bit(void *bitmap, const void *bitmap2, unsigned long len)
 {
-	static DECLARE_BITMAP(cp, BITMAP_LEN) __initdata;
+	unsigned long *cp __free(bitmap) = bitmap_alloc(len, GFP_KERNEL);
 	unsigned long i, cnt;
 	ktime_t time;
 
-	bitmap_copy(cp, bitmap, BITMAP_LEN);
+	bitmap_copy(cp, bitmap, len);
 
 	time = ktime_get();
 	for (cnt = i = 0; i < len; cnt++) {
 		i = find_first_and_bit(cp, bitmap2, len);
-		__clear_bit(i, cp);
+		if (i < len)
+			__clear_bit(i, cp);
 	}
 	time = ktime_get() - time;
 	pr_err("find_first_and_bit: %18llu ns, %6ld iterations\n", time, cnt);
@@ -165,7 +169,7 @@ static int __init find_bit_test(void)
 	 * traverse only part of bitmap to avoid soft lockup.
 	 */
 	test_find_first_bit(bitmap, BITMAP_LEN / 10);
-	test_find_first_and_bit(bitmap, bitmap2, BITMAP_LEN / 2);
+	test_find_first_and_bit(bitmap, bitmap2, BITMAP_LEN / 10);
 	test_find_next_and_bit(bitmap, bitmap2, BITMAP_LEN);
 
 	pr_err("\nStart testing find_bit() with sparse bitmap\n");
@@ -182,8 +186,8 @@ static int __init find_bit_test(void)
 	test_find_next_zero_bit(bitmap, BITMAP_LEN);
 	test_find_last_bit(bitmap, BITMAP_LEN);
 	test_find_nth_bit(bitmap, BITMAP_LEN);
-	test_find_first_bit(bitmap, BITMAP_LEN);
-	test_find_first_and_bit(bitmap, bitmap2, BITMAP_LEN);
+	test_find_first_bit(bitmap, BITMAP_LEN / 10);
+	test_find_first_and_bit(bitmap, bitmap2, BITMAP_LEN / 10);
 	test_find_next_and_bit(bitmap, bitmap2, BITMAP_LEN);
 
 	/*
-- 
2.39.2