Received-SPF: pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 2620:137:e000::1:20 as permitted sender) client-ip=2620:137:e000::1:20;
From:   Yury Norov <yury.norov@gmail.com>
To:     Linus Torvalds <torvalds@linux-foundation.org>,
        linux-kernel@vger.kernel.org
Cc:     Yury Norov <yury.norov@gmail.com>,
        Guenter Roeck <linux@roeck-us.net>,
        Dennis Zhou <dennis@kernel.org>,
        Russell King <linux@armlinux.org.uk>,
        Catalin Marinas <catalin.marinas@arm.com>,
        Andy Shevchenko <andriy.shevchenko@linux.intel.com>,
        Rasmus Villemoes <linux@rasmusvillemoes.dk>,
        Alexey Klimov <aklimov@redhat.com>,
        Kees Cook <keescook@chromium.org>,
        Andy Whitcroft <apw@canonical.com>
Subject: [PATCH v2 1/3] lib/find_bit: introduce FIND_FIRST_BIT() macro
Date:   Tue, 23 Aug 2022 18:26:22 -0700
Message-Id: <20220824012624.2826445-2-yury.norov@gmail.com>
In-Reply-To: <20220824012624.2826445-1-yury.norov@gmail.com>
References: <20220824012624.2826445-1-yury.norov@gmail.com>
MIME-Version: 1.0
Content-Transfer-Encoding: 8bit
Precedence: bulk

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@linux-foundation.org>
Signed-off-by: Yury Norov <yury.norov@gmail.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