linux-kernel - [PATCH v2 1/3] lib/find_bit: introduce FIND_FIRST

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]

Date:   Tue, 23 Aug 2022 18:26:22 -0700
From:   Yury Norov <yury.norov@...il.com>
To:     Linus Torvalds <torvalds@...ux-foundation.org>,
        linux-kernel@...r.kernel.org
Cc:     Yury Norov <yury.norov@...il.com>,
        Guenter Roeck <linux@...ck-us.net>,
        Dennis Zhou <dennis@...nel.org>,
        Russell King <linux@...linux.org.uk>,
        Catalin Marinas <catalin.marinas@....com>,
        Andy Shevchenko <andriy.shevchenko@...ux.intel.com>,
        Rasmus Villemoes <linux@...musvillemoes.dk>,
        Alexey Klimov <aklimov@...hat.com>,
        Kees Cook <keescook@...omium.org>,
        Andy Whitcroft <apw@...onical.com>
Subject: [PATCH v2 1/3] lib/find_bit: introduce FIND_FIRST_BIT() macro

Now that we have many flavors of find_first_bit(), and expect even more,
it's better to have one macro that generates optimal code for all and makes
maintaining of slightly different functions simpler.

The logic common to all versions is moved to the new macro, and all the
flavors are generated by providing an EXPRESSION macro-parameter, like
in this example:

  #define FIND_FIRST_BIT(EXPRESSION, size) ...
  
  find_first_ornot_and_bit(addr1, addr2, addr3, size)
  {
  	return FIND_NEXT_BIT(addr1[idx] | ~addr2[idx] & addr3[idx], size);
  }

The EXPRESSION may be of any complexity, as soon as it only refers
the bitmap(s) and an iterator idx.

The 'word_op' is here to allow the macro to generate code for _le
versions on big-endian machines; used in the following patches.

Suggested-by: Linus Torvalds <torvalds@...ux-foundation.org>
Signed-off-by: Yury Norov <yury.norov@...il.com>
---
 MAINTAINERS    |  1 +
 lib/find_bit.c | 30 +++++-------------------------
 lib/find_bit.h | 24 ++++++++++++++++++++++++
 3 files changed, 30 insertions(+), 25 deletions(-)
 create mode 100644 lib/find_bit.h

diff --git a/MAINTAINERS b/MAINTAINERS
index 96f47a7865d6..02e11f2dbafe 100644
--- a/MAINTAINERS
+++ b/MAINTAINERS
@@ -3612,6 +3612,7 @@ F:	include/linux/find.h
 F:	include/linux/nodemask.h
 F:	lib/bitmap.c
 F:	lib/cpumask.c
+F:	lib/find_bit.h
 F:	lib/find_bit.c
 F:	lib/find_bit_benchmark.c
 F:	lib/test_bitmap.c
diff --git a/lib/find_bit.c b/lib/find_bit.c
index 1b8e4b2a9cba..ccc4fb1dfc71 100644
--- a/lib/find_bit.c
+++ b/lib/find_bit.c
@@ -19,6 +19,8 @@
 #include <linux/minmax.h>
 #include <linux/swab.h>
 
+#include "find_bit.h"
+
 #if !defined(find_next_bit) || !defined(find_next_zero_bit) ||			\
 	!defined(find_next_bit_le) || !defined(find_next_zero_bit_le) ||	\
 	!defined(find_next_and_bit)
@@ -77,14 +79,7 @@ EXPORT_SYMBOL(_find_next_bit);
  */
 unsigned long _find_first_bit(const unsigned long *addr, unsigned long size)
 {
-	unsigned long idx;
-
-	for (idx = 0; idx * BITS_PER_LONG < size; idx++) {
-		if (addr[idx])
-			return min(idx * BITS_PER_LONG + __ffs(addr[idx]), size);
-	}
-
-	return size;
+	return FIND_FIRST_BIT(addr[idx], size);
 }
 EXPORT_SYMBOL(_find_first_bit);
 #endif
@@ -97,15 +92,7 @@ unsigned long _find_first_and_bit(const unsigned long *addr1,
 				  const unsigned long *addr2,
 				  unsigned long size)
 {
-	unsigned long idx, val;
-
-	for (idx = 0; idx * BITS_PER_LONG < size; idx++) {
-		val = addr1[idx] & addr2[idx];
-		if (val)
-			return min(idx * BITS_PER_LONG + __ffs(val), size);
-	}
-
-	return size;
+	return FIND_FIRST_BIT(addr1[idx] & addr2[idx], size);
 }
 EXPORT_SYMBOL(_find_first_and_bit);
 #endif
@@ -116,14 +103,7 @@ EXPORT_SYMBOL(_find_first_and_bit);
  */
 unsigned long _find_first_zero_bit(const unsigned long *addr, unsigned long size)
 {
-	unsigned long idx;
-
-	for (idx = 0; idx * BITS_PER_LONG < size; idx++) {
-		if (addr[idx] != ~0UL)
-			return min(idx * BITS_PER_LONG + ffz(addr[idx]), size);
-	}
-
-	return size;
+	return FIND_FIRST_BIT(~addr[idx], size);
 }
 EXPORT_SYMBOL(_find_first_zero_bit);
 #endif
diff --git a/lib/find_bit.h b/lib/find_bit.h
new file mode 100644
index 000000000000..b4b6245ddbf6
--- /dev/null
+++ b/lib/find_bit.h
@@ -0,0 +1,24 @@
+/* SPDX-License-Identifier: GPL-2.0-or-later */
+#ifndef _LIB_FIND_BIT_H
+#define _LIB_FIND_BIT_H
+
+#ifndef word_op
+#define word_op
+#endif
+
+#define FIND_FIRST_BIT(EXPRESSION, size)					\
+({										\
+	unsigned long idx, val, sz = (size);					\
+										\
+	for (idx = 0; idx * BITS_PER_LONG < sz; idx++) {			\
+		val = (EXPRESSION);						\
+		if (val) {							\
+			sz = min(idx * BITS_PER_LONG + __ffs(word_op(val)), sz);\
+			break;							\
+		}								\
+	}									\
+										\
+	sz;									\
+})
+
+#endif /* _LIB_FIND_BIT_H */
-- 
2.34.1