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>,
        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>,
        Linux Kernel Mailing List <linux-kernel@vger.kernel.org>
Cc:     Yury Norov <yury.norov@gmail.com>
Subject: [PATCH 3/5] lib/find_bit: unify _find_first_{,and,zero}_bit implementations
Date:   Thu, 28 Jul 2022 09:12:06 -0700
Message-Id: <20220728161208.865420-4-yury.norov@gmail.com>
In-Reply-To: <20220728161208.865420-1-yury.norov@gmail.com>
References: <20220728161208.865420-1-yury.norov@gmail.com>
MIME-Version: 1.0
Content-Transfer-Encoding: 8bit
Precedence: bulk

The functions are almost identical, so create a common helper for them so
that compiler will be able to either inline the helper and optimize-out
parameters known at compile-time, or save some space by keeping it as a
real function.

On kvm/x86_64, bloat-o-meter reports +9 bytes. Find_bit_benchmark 5 times
before and after doesn't show significant (i.e. delta is greater than 3
sigma) difference, except find_next_bit, which is most likely an outlier
(although, lucky for the patch):
                     v5.19-rc8    Optimized   Difference (more - better)
Random dense bitmap	    ns	         ns             %       sigmas
find_next_bit:          721209       594936            18         3.19
find_next_zero_bit:     738138       638182            14         1.40
find_last_bit:          802393       940846           -17        -0.31
find_first_bit:        3560900      3379983             5         0.65
find_first_and_bit:   38601442     37683449             2         1.00
find_next_and_bit:      335574       300373            10         2.82
                                                       
Random sparse bitmap                                   
find_next_bit:           15868        13856            13         0.82
find_next_zero_bit:    1311843      1227418             6         0.72
find_last_bit:           13633        14080            -3        -0.74
find_first_bit:        1273625      1253343             2         0.52
find_first_and_bit:       8548         8157             5         0.32
find_next_and_bit:        8828         8437             4         0.52

Signed-off-by: Yury Norov <yury.norov@gmail.com>
---
 lib/find_bit.c | 62 +++++++++++++++++++++++++++-----------------------
 1 file changed, 33 insertions(+), 29 deletions(-)

diff --git a/lib/find_bit.c b/lib/find_bit.c
index 4ef3151b3109..d207d1699834 100644
--- a/lib/find_bit.c
+++ b/lib/find_bit.c
@@ -20,12 +20,38 @@
 #include <linux/swab.h>
 
 /*
- * This is a common helper function for find_next_bit, find_next_zero_bit, and
- * find_next_and_bit. The differences are:
+ * This is a common helper functions for find_{first,next}_bit{,_le}.
+ * Internal parameters are:
  *  - The "invert" argument, which is XORed with each fetched word before
- *    searching it for one bits.
- *  - The optional "addr2", which is anded with "addr1" if present.
+ *    searching it for set bits; to implement find_*_zero_bit().
+ *  - The optional "addr2", which is ANDed with "addr1" if present; to
+ *    implement find_*_and_bit().
+ *  - The "need_swab" that converts words to BE format; to implement
+ *    find_*_le() on big-endian machines.
  */
+static inline
+unsigned long __find_first_bit(const unsigned long *addr1, const unsigned long *addr2,
+				unsigned long size, unsigned long invert, bool need_swab)
+{
+	unsigned long idx, val;
+
+	for (idx = 0; idx * BITS_PER_LONG < size; idx++) {
+		val = addr1[idx];
+		if (addr2)
+			val &= addr2[idx];
+
+		val ^= invert;
+
+		if (val) {
+			if (need_swab)
+				val = swab(val);
+			return min(idx * BITS_PER_LONG + __ffs(val), size);
+		}
+	}
+
+	return size;
+}
+
 static inline unsigned long __find_next_bit(const unsigned long *addr1,
 		const unsigned long *addr2, unsigned long nbits,
 		unsigned long start, unsigned long invert, bool need_swab)
@@ -118,14 +144,7 @@ EXPORT_SYMBOL(_find_next_bit_le);
  */
 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, NULL, size, 0UL, false);
 }
 EXPORT_SYMBOL(_find_first_bit);
 #endif
@@ -138,15 +157,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, addr2, size, 0UL, false);
 }
 EXPORT_SYMBOL(_find_first_and_bit);
 #endif
@@ -157,14 +168,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, NULL, size, ~0UL, false);
 }
 EXPORT_SYMBOL(_find_first_zero_bit);
 #endif
-- 
2.34.1