linux-kernel - [PATCH] bitmap: optimize bitmap

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-next>] [day] [month] [year] [list]

Message-Id: <20230815235934.47782-1-yury.norov@gmail.com>
Date:   Tue, 15 Aug 2023 16:59:34 -0700
From:   Yury Norov <yury.norov@...il.com>
To:     linux-kernel@...r.kernel.org
Cc:     Yury Norov <yury.norov@...il.com>,
        Andy Shevchenko <andriy.shevchenko@...ux.intel.com>,
        Rasmus Villemoes <linux@...musvillemoes.dk>
Subject: [PATCH] bitmap: optimize bitmap_remap()

When 'new' map is empty, i.e. identity mapping, we can simply copy
src to dst, which is significantly faster than setting bits one by
one in a for-loop.

While here, replace set_bit() with non-atomic __set_bit().

Signed-off-by: Yury Norov <yury.norov@...il.com>
---
 lib/bitmap.c | 16 ++++++++++------
 1 file changed, 10 insertions(+), 6 deletions(-)

diff --git a/lib/bitmap.c b/lib/bitmap.c
index 24284caadbcc..bf6b0eea1af8 100644
--- a/lib/bitmap.c
+++ b/lib/bitmap.c
@@ -1004,20 +1004,24 @@ void bitmap_remap(unsigned long *dst, const unsigned long *src,
 		const unsigned long *old, const unsigned long *new,
 		unsigned int nbits)
 {
-	unsigned int oldbit, w;
+	unsigned int bit, oldbit, w;
 
 	if (dst == src)		/* following doesn't handle inplace remaps */
 		return;
-	bitmap_zero(dst, nbits);
 
 	w = bitmap_weight(new, nbits);
+	if (w == 0) {
+		bitmap_copy(dst, src, nbits);
+		return;
+	}
+
+	bitmap_zero(dst, nbits);
 	for_each_set_bit(oldbit, src, nbits) {
 		int n = bitmap_pos_to_ord(old, oldbit, nbits);
 
-		if (n < 0 || w == 0)
-			set_bit(oldbit, dst);	/* identity map */
-		else
-			set_bit(find_nth_bit(new, nbits, n % w), dst);
+		bit = (n < 0) ? oldbit :	/* identity map */
+				find_nth_bit(new, nbits, n % w);
+		__set_bit(bit, dst);
 	}
 }
 EXPORT_SYMBOL(bitmap_remap);
-- 
2.39.2