[PATCH v3 0/6] lib: Extend bitmap find binary operations

[PATCH v3 0/6] lib: Extend bitmap find binary operations

[Mathieu Desnoyers]

Extend bitmap find.h and cpumask.h with additional binary operations
such as "nor".

Also extend the testing and benchmark coverage of those bitmap find with
binary operations.

This is useful for NUMA-aware rseq concurrency IDs which depend on this
series. The series can be found at:

https://lore.kernel.org/lkml/20240823185946.418340-1-mathieu.desnoyers@efficios.com/


Mathieu Desnoyers (6):
  lib: Clarify comment on top of find_next_andnot_bit
  lib: Implement find_{first,next,nth}_nor_bit, for_each_nor_bit,
    find_first_andnot_bit
  lib: test bitmap sets binary operation iterators
  lib: Fix test_find_first_and_bit and test_find_next_and_bit benchmark
  lib: benchmark bitmap sets binary operation find
  cpumask: Implement cpumask_{first,next}_{nor,andnot}

 include/linux/cpumask.h  |  60 ++++++++++++++++
 include/linux/find.h     | 124 +++++++++++++++++++++++++++++++--
 lib/find_bit.c           |  36 ++++++++++
 lib/find_bit_benchmark.c | 143 +++++++++++++++++++++++++++++++++------
 lib/test_bitmap.c        |  81 ++++++++++++++++++++++
 5 files changed, 418 insertions(+), 26 deletions(-)

-- 
2.39.2

[PATCH v3 1/6] lib: Clarify comment on top of find_next_andnot_bit

[Mathieu Desnoyers]

Make the comment on top of find_next_andnot_bit clearer by discussing in
terms of "cleared bits" rather than "excluding bits".

Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
Acked-by: Yury Norov <yury.norov@gmail.com>
Cc: Yury Norov <yury.norov@gmail.com>
Cc: Rasmus Villemoes <linux@rasmusvillemoes.dk>
---
 include/linux/find.h | 7 +++----
 1 file changed, 3 insertions(+), 4 deletions(-)

diff --git a/include/linux/find.h b/include/linux/find.h
index 5dfca4225fef..8a170aa55634 100644
--- a/include/linux/find.h
+++ b/include/linux/find.h
@@ -102,15 +102,14 @@ unsigned long find_next_and_bit(const unsigned long *addr1,
 
 #ifndef find_next_andnot_bit
 /**
- * find_next_andnot_bit - find the next set bit in *addr1 excluding all the bits
- *                        in *addr2
+ * find_next_andnot_bit - find the next set bit in *addr1, cleared in *addr2
  * @addr1: The first address to base the search on
  * @addr2: The second address to base the search on
  * @size: The bitmap size in bits
  * @offset: The bitnumber to start searching at
  *
- * Returns the bit number for the next set bit
- * If no bits are set, returns @size.
+ * Returns the bit number for the next bit set in *addr1, cleared in *addr2.
+ * If no such bits are found, returns @size.
  */
 static inline
 unsigned long find_next_andnot_bit(const unsigned long *addr1,
-- 
2.39.2

[PATCH v3 2/6] lib: Implement find_{first,next,nth}_nor_bit, for_each_nor_bit, find_first_andnot_bit

[Mathieu Desnoyers]

Allow finding the first, next, or nth bit within two input bitmasks
which is zero in both masks.

Allow fiding the first bit within two input bitmasks which is set in
first mask and cleared in the second mask. find_next_andnot_bit and
find_nth_andnot_bit already exist, so find the first bit appears to be
missing.

Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
Acked-by: Yury Norov <yury.norov@gmail.com>
Cc: Yury Norov <yury.norov@gmail.com>
Cc: Rasmus Villemoes <linux@rasmusvillemoes.dk>
---
Changes since v0:
- Rename "notandnot" to "nor", document equivalence.
- Move comment cleanups to a separate patch.
- Use __always_inline.
Changes since v1:
- Introduce for_each_nor_bit.
Changes since v2:
- Remove extern.
---
 include/linux/find.h | 117 +++++++++++++++++++++++++++++++++++++++++++
 lib/find_bit.c       |  36 +++++++++++++
 2 files changed, 153 insertions(+)

diff --git a/include/linux/find.h b/include/linux/find.h
index 8a170aa55634..d47591e6c999 100644
--- a/include/linux/find.h
+++ b/include/linux/find.h
@@ -14,6 +14,8 @@ unsigned long _find_next_and_bit(const unsigned long *addr1, const unsigned long
 					unsigned long nbits, unsigned long start);
 unsigned long _find_next_andnot_bit(const unsigned long *addr1, const unsigned long *addr2,
 					unsigned long nbits, unsigned long start);
+unsigned long _find_next_nor_bit(const unsigned long *addr1, const unsigned long *addr2,
+					unsigned long nbits, unsigned long start);
 unsigned long _find_next_or_bit(const unsigned long *addr1, const unsigned long *addr2,
 					unsigned long nbits, unsigned long start);
 unsigned long _find_next_zero_bit(const unsigned long *addr, unsigned long nbits,
@@ -24,11 +26,17 @@ unsigned long __find_nth_and_bit(const unsigned long *addr1, const unsigned long
 				unsigned long size, unsigned long n);
 unsigned long __find_nth_andnot_bit(const unsigned long *addr1, const unsigned long *addr2,
 					unsigned long size, unsigned long n);
+unsigned long __find_nth_nor_bit(const unsigned long *addr1, const unsigned long *addr2,
+					unsigned long size, unsigned long n);
 unsigned long __find_nth_and_andnot_bit(const unsigned long *addr1, const unsigned long *addr2,
 					const unsigned long *addr3, unsigned long size,
 					unsigned long n);
 extern unsigned long _find_first_and_bit(const unsigned long *addr1,
 					 const unsigned long *addr2, unsigned long size);
+unsigned long _find_first_andnot_bit(const unsigned long *addr1,
+					 const unsigned long *addr2, unsigned long size);
+unsigned long _find_first_nor_bit(const unsigned long *addr1,
+					 const unsigned long *addr2, unsigned long size);
 unsigned long _find_first_and_and_bit(const unsigned long *addr1, const unsigned long *addr2,
 				      const unsigned long *addr3, unsigned long size);
 extern unsigned long _find_first_zero_bit(const unsigned long *addr, unsigned long size);
@@ -130,6 +138,35 @@ unsigned long find_next_andnot_bit(const unsigned long *addr1,
 }
 #endif
 
+/**
+ * find_next_nor_bit - find the next bit cleared in both *addr1 and *addr2
+ * @addr1: The first address to base the search on
+ * @addr2: The second address to base the search on
+ * @size: The bitmap size in bits
+ * @offset: The bitnumber to start searching at
+ *
+ * Returns the bit number for the next bit cleared in both *addr1 and *addr2.
+ * If no such bits are found, returns @size.
+ * The bitwise operation nor ~(A | B) is equivalent to (~A & ~B).
+ */
+static __always_inline
+unsigned long find_next_nor_bit(const unsigned long *addr1,
+		const unsigned long *addr2, unsigned long size,
+		unsigned long offset)
+{
+	if (small_const_nbits(size)) {
+		unsigned long val;
+
+		if (unlikely(offset >= size))
+			return size;
+
+		val = ~(*addr1 | *addr2) & GENMASK(size - 1, offset);
+		return val ? __ffs(val) : size;
+	}
+
+	return _find_next_nor_bit(addr1, addr2, size, offset);
+}
+
 #ifndef find_next_or_bit
 /**
  * find_next_or_bit - find the next set bit in either memory regions
@@ -291,6 +328,33 @@ unsigned long find_nth_andnot_bit(const unsigned long *addr1, const unsigned lon
 	return __find_nth_andnot_bit(addr1, addr2, size, n);
 }
 
+/**
+ * find_nth_nor_bit - find N'th cleared bit in 2 memory regions.
+ * @addr1: The 1st address to start the search at
+ * @addr2: The 2nd address to start the search at
+ * @size: The maximum number of bits to search
+ * @n: The number of set bit, which position is needed, counting from 0
+ *
+ * Returns the bit number of the N'th bit cleared in the two regions.
+ * If no such, returns @size.
+ * The bitwise operation nor ~(A | B) is equivalent to (~A & ~B).
+ */
+static __always_inline
+unsigned long find_nth_nor_bit(const unsigned long *addr1, const unsigned long *addr2,
+				unsigned long size, unsigned long n)
+{
+	if (n >= size)
+		return size;
+
+	if (small_const_nbits(size)) {
+		unsigned long val = ~(*addr1 | *addr2) & GENMASK(size - 1, 0);
+
+		return val ? fns(val, n) : size;
+	}
+
+	return __find_nth_nor_bit(addr1, addr2, size, n);
+}
+
 /**
  * find_nth_and_andnot_bit - find N'th set bit in 2 memory regions,
  *			     excluding those set in 3rd region
@@ -346,6 +410,54 @@ unsigned long find_first_and_bit(const unsigned long *addr1,
 }
 #endif
 
+/**
+ * find_first_andnot_bit - find the first set bit in 2 memory regions,
+ *                         flipping bits in 2nd region.
+ * @addr1: The first address to base the search on
+ * @addr2: The second address to base the search on
+ * @size: The bitmap size in bits
+ *
+ * Returns the bit number for the next set bit.
+ * If no bits are set, returns @size.
+ */
+static __always_inline
+unsigned long find_first_andnot_bit(const unsigned long *addr1,
+				 const unsigned long *addr2,
+				 unsigned long size)
+{
+	if (small_const_nbits(size)) {
+		unsigned long val = *addr1 & (~*addr2) & GENMASK(size - 1, 0);
+
+		return val ? __ffs(val) : size;
+	}
+
+	return _find_first_andnot_bit(addr1, addr2, size);
+}
+
+/**
+ * find_first_nor_bit - find the first cleared bit in 2 memory regions
+ * @addr1: The first address to base the search on
+ * @addr2: The second address to base the search on
+ * @size: The bitmap size in bits
+ *
+ * Returns the bit number for the next cleared bit.
+ * If no bits are set, returns @size.
+ * The bitwise operation nor ~(A | B) is equivalent to (~A & ~B).
+ */
+static __always_inline
+unsigned long find_first_nor_bit(const unsigned long *addr1,
+				 const unsigned long *addr2,
+				 unsigned long size)
+{
+	if (small_const_nbits(size)) {
+		unsigned long val = ~(*addr1 | *addr2) & GENMASK(size - 1, 0);
+
+		return val ? __ffs(val) : size;
+	}
+
+	return _find_first_nor_bit(addr1, addr2, size);
+}
+
 /**
  * find_first_and_and_bit - find the first set bit in 3 memory regions
  * @addr1: The first address to base the search on
@@ -594,6 +706,11 @@ unsigned long find_next_bit_le(const void *addr, unsigned
 	     (bit) = find_next_andnot_bit((addr1), (addr2), (size), (bit)), (bit) < (size);\
 	     (bit)++)
 
+#define for_each_nor_bit(bit, addr1, addr2, size) \
+	for ((bit) = 0;									\
+	     (bit) = find_next_nor_bit((addr1), (addr2), (size), (bit)), (bit) < (size);\
+	     (bit)++)
+
 #define for_each_or_bit(bit, addr1, addr2, size) \
 	for ((bit) = 0;									\
 	     (bit) = find_next_or_bit((addr1), (addr2), (size), (bit)), (bit) < (size);\
diff --git a/lib/find_bit.c b/lib/find_bit.c
index 0836bb3d76c5..8050bc7c7ede 100644
--- a/lib/find_bit.c
+++ b/lib/find_bit.c
@@ -116,6 +116,28 @@ unsigned long _find_first_and_bit(const unsigned long *addr1,
 EXPORT_SYMBOL(_find_first_and_bit);
 #endif
 
+/*
+ * Find the first set bit in two memory regions, flipping bits in 2nd region.
+ */
+unsigned long _find_first_andnot_bit(const unsigned long *addr1,
+				  const unsigned long *addr2,
+				  unsigned long size)
+{
+	return FIND_FIRST_BIT(addr1[idx] & ~addr2[idx], /* nop */, size);
+}
+EXPORT_SYMBOL(_find_first_andnot_bit);
+
+/*
+ * Find the first cleared bit in two memory regions.
+ */
+unsigned long _find_first_nor_bit(const unsigned long *addr1,
+				  const unsigned long *addr2,
+				  unsigned long size)
+{
+	return FIND_FIRST_BIT(~(addr1[idx] | addr2[idx]), /* nop */, size);
+}
+EXPORT_SYMBOL(_find_first_nor_bit);
+
 /*
  * Find the first set bit in three memory regions.
  */
@@ -167,6 +189,13 @@ unsigned long __find_nth_andnot_bit(const unsigned long *addr1, const unsigned l
 }
 EXPORT_SYMBOL(__find_nth_andnot_bit);
 
+unsigned long __find_nth_nor_bit(const unsigned long *addr1, const unsigned long *addr2,
+				 unsigned long size, unsigned long n)
+{
+	return FIND_NTH_BIT(~(addr1[idx] | addr2[idx]), size, n);
+}
+EXPORT_SYMBOL(__find_nth_nor_bit);
+
 unsigned long __find_nth_and_andnot_bit(const unsigned long *addr1,
 					const unsigned long *addr2,
 					const unsigned long *addr3,
@@ -194,6 +223,13 @@ unsigned long _find_next_andnot_bit(const unsigned long *addr1, const unsigned l
 EXPORT_SYMBOL(_find_next_andnot_bit);
 #endif
 
+unsigned long _find_next_nor_bit(const unsigned long *addr1, const unsigned long *addr2,
+					unsigned long nbits, unsigned long start)
+{
+	return FIND_NEXT_BIT(~(addr1[idx] | addr2[idx]), /* nop */, nbits, start);
+}
+EXPORT_SYMBOL(_find_next_nor_bit);
+
 #ifndef find_next_or_bit
 unsigned long _find_next_or_bit(const unsigned long *addr1, const unsigned long *addr2,
 					unsigned long nbits, unsigned long start)
-- 
2.39.2

[PATCH v3 3/6] lib: test bitmap sets binary operation iterators

[Mathieu Desnoyers]

Test the following bitmap iterators applying binary operations on sets
of two bitmaps:

- for_each_and_bit,
- for_each_andnot_bit,
- for_each_nor_bit,
- for_each_or_bit.

Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
Cc: Yury Norov <yury.norov@gmail.com>
Cc: Rasmus Villemoes <linux@rasmusvillemoes.dk>
---
 lib/test_bitmap.c | 81 +++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 81 insertions(+)

diff --git a/lib/test_bitmap.c b/lib/test_bitmap.c
index 6dfb8d46a4ff..96ce3c78c7fa 100644
--- a/lib/test_bitmap.c
+++ b/lib/test_bitmap.c
@@ -184,6 +184,32 @@ __check_eq_str(const char *srcfile, unsigned int line,
 		result;							\
 	})
 
+static bool __init
+__check_neq_range_ulong(const char *srcfile, unsigned int line,
+		 const unsigned long exp_ulong_begin,
+		 const unsigned long exp_ulong_end,
+		 unsigned long x)
+{
+	if (exp_ulong_begin <= x && exp_ulong_end >= x) {
+		pr_err("[%s:%u] did not value %lu within range [%lu,%lu]\n",
+			srcfile, line, x, exp_ulong_begin, exp_ulong_end);
+		return false;
+	}
+	return true;
+}
+
+#define __expect_neq_range(suffix, ...)					\
+	({								\
+		int result = 0;						\
+		total_tests++;						\
+		if (!__check_neq_range_ ## suffix(__FILE__, __LINE__,	\
+					   ##__VA_ARGS__)) {		\
+			failed_tests++;					\
+			result = 1;					\
+		}							\
+		result;							\
+	})
+
 #define expect_eq_ulong(...)		__expect_eq(ulong, ##__VA_ARGS__)
 #define expect_eq_uint(x, y)		expect_eq_ulong((unsigned int)(x), (unsigned int)(y))
 #define expect_eq_bitmap(...)		__expect_eq(bitmap, ##__VA_ARGS__)
@@ -192,6 +218,9 @@ __check_eq_str(const char *srcfile, unsigned int line,
 #define expect_eq_clump8(...)		__expect_eq(clump8, ##__VA_ARGS__)
 #define expect_eq_str(...)		__expect_eq(str, ##__VA_ARGS__)
 
+#define expect_neq_range_ulong(...)		__expect_neq_range(ulong, ##__VA_ARGS__)
+#define expect_neq_range_uint(begin, end, y)	expect_neq_range_ulong((unsigned int)(begin), (unsigned int) end, (unsigned int)(y))
+
 static void __init test_zero_clear(void)
 {
 	DECLARE_BITMAP(bmap, 1024);
@@ -849,6 +878,57 @@ static void __init test_for_each_set_bit(void)
 	expect_eq_bitmap(orig, copy, 500);
 }
 
+static void __init test_for_each_binaryops_bit(void)
+{
+	DECLARE_BITMAP(orig1, 500);
+	DECLARE_BITMAP(orig2, 500);
+	unsigned int bit, count;
+
+	bitmap_zero(orig1, 500);
+	bitmap_zero(orig2, 500);
+
+	/* Set individual bits in orig1 and orig2 with stride 10 (expected in both orig1 & orig2) */
+	for (bit = 0; bit < 500; bit += 10) {
+		bitmap_set(orig1, bit, 1);
+		bitmap_set(orig2, bit, 1);
+	}
+	/* Set individual bits in orig1 with offset 1, stride 10 (expected in orig1 only) */
+	for (bit = 1; bit < 500; bit += 10)
+		bitmap_set(orig1, bit, 1);
+	/* Set individual bits in orig2 with offset 2, stride 10 (expected in orig2 only). */
+	for (bit = 2; bit < 500; bit += 10)
+		bitmap_set(orig2, bit, 1);
+
+	count = 0;
+	for_each_and_bit(bit, orig1, orig2, 500) {	/* orig1 & orig2 */
+		expect_neq_range_uint(1, 9, bit % 10);
+		count++;
+	}
+	expect_eq_uint(50, count);
+
+	count = 0;
+	for_each_andnot_bit(bit, orig1, orig2, 500) {	/* orig1 & ~orig2 */
+		expect_neq_range_uint(0, 0, bit % 10);
+		expect_neq_range_uint(2, 9, bit % 10);
+		count++;
+	}
+	expect_eq_uint(50, count);
+
+	count = 0;
+	for_each_nor_bit(bit, orig1, orig2, 500) {	/* ~(orig1 | orig2) */
+		expect_neq_range_uint(0, 2, bit % 10);
+		count++;
+	}
+	expect_eq_uint(7 * 50, count);
+
+	count = 0;
+	for_each_or_bit(bit, orig1, orig2, 500) {	/* orig1 | orig2 */
+		expect_neq_range_uint(3, 9, bit % 10);
+		count++;
+	}
+	expect_eq_uint(3 * 50, count);
+}
+
 static void __init test_for_each_set_bit_from(void)
 {
 	DECLARE_BITMAP(orig, 500);
@@ -1482,6 +1562,7 @@ static void __init selftest(void)
 	test_for_each_clear_bitrange_from();
 	test_for_each_set_clump8();
 	test_for_each_set_bit_wrap();
+	test_for_each_binaryops_bit();
 }
 
 KSTM_MODULE_LOADERS(test_bitmap);
-- 
2.39.2

[PATCH v3 4/6] lib: Fix test_find_first_and_bit and test_find_next_and_bit benchmark

[Mathieu Desnoyers]

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@efficios.com>
Cc: Yury Norov <yury.norov@gmail.com>
Cc: Rasmus Villemoes <linux@rasmusvillemoes.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

[PATCH v3 5/6] lib: benchmark bitmap sets binary operation find

[Mathieu Desnoyers]

Benchmark the following bitmap find functions applying binary operations
on sets of two bitmaps:

- find_first_andnot_bit,
- find_first_nor_bit,
- find_next_andnot_bit,
- find_next_nor_bit,
- find_next_or_bit.

Note that find_first_or_bit is not part of the current API, so it is not
covered.

Use "len" parameters rather than BITMAP_LEN within all benchmark
functions (changed across the whole file).

Example output:

(AMD EPYC 9654 96-Core Processor)

Start testing find_bit() with random-filled bitmap
find_next_bit:                     595816 ns, 163603 iterations
find_next_zero_bit:                613227 ns, 164078 iterations
find_last_bit:                     464619 ns, 163602 iterations
find_nth_bit:                     2647830 ns,  16413 iterations
find_first_bit:                   1240485 ns,  16414 iterations
find_first_and_bit:                623258 ns,   8136 iterations
find_next_and_bit:                 321039 ns,  81576 iterations
find_first_andnot_bit:             929316 ns,   8279 iterations
find_next_andnot_bit:              324820 ns,  82027 iterations
find_first_nor_bit:                971359 ns,   8241 iterations
find_next_nor_bit:                 346981 ns,  82058 iterations
find_next_or_bit:                  882343 ns, 245623 iterations

Start testing find_bit() with sparse bitmap
find_next_bit:                       8751 ns,    656 iterations
find_next_zero_bit:               1184552 ns, 327025 iterations
find_last_bit:                       8820 ns,    656 iterations
find_nth_bit:                     1111597 ns,    655 iterations
find_first_bit:                      4980 ns,     59 iterations
find_first_and_bit:                   550 ns,      1 iterations
find_next_and_bit:                   3110 ns,      1 iterations
find_first_andnot_bit:               7420 ns,     59 iterations
find_next_andnot_bit:                9500 ns,    656 iterations
find_first_nor_bit:               3889256 ns,  32647 iterations
find_next_nor_bit:                1254026 ns, 326370 iterations
find_next_or_bit:                   14341 ns,   1311 iterations

Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
Cc: Yury Norov <yury.norov@gmail.com>
Cc: Rasmus Villemoes <linux@rasmusvillemoes.dk>
---
Changes since v2:
- Use bitmap_alloc rather than a local static variable for bitmaps.
- Divide BITMAP_LEN by 10 for all find_first tests to ensure the test
  runs fast enough (a few ms per test).
- Fix alignment of text output.
- Clear/set bits only within range, fixing an out-of-bound access.
- Use "len" parameters rather than BITMAP_LEN within all benchmark
  functions (changed across the whole file).
---
 lib/find_bit_benchmark.c | 119 +++++++++++++++++++++++++++++++++++----
 1 file changed, 107 insertions(+), 12 deletions(-)

diff --git a/lib/find_bit_benchmark.c b/lib/find_bit_benchmark.c
index 81d358fb459b..5ab72829e7ee 100644
--- a/lib/find_bit_benchmark.c
+++ b/lib/find_bit_benchmark.c
@@ -47,7 +47,7 @@ static int __init test_find_first_bit(void *bitmap, unsigned long len)
 			__clear_bit(i, cp);
 	}
 	time = ktime_get() - time;
-	pr_err("find_first_bit:     %18llu ns, %6ld iterations\n", time, cnt);
+	pr_err("find_first_bit:        %18llu ns, %6ld iterations\n", time, cnt);
 
 	return 0;
 }
@@ -67,7 +67,47 @@ static int __init test_find_first_and_bit(void *bitmap, const void *bitmap2, uns
 			__clear_bit(i, cp);
 	}
 	time = ktime_get() - time;
-	pr_err("find_first_and_bit: %18llu ns, %6ld iterations\n", time, cnt);
+	pr_err("find_first_and_bit:    %18llu ns, %6ld iterations\n", time, cnt);
+
+	return 0;
+}
+
+static int __init test_find_first_andnot_bit(void *bitmap, const void *bitmap2, 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_andnot_bit(cp, bitmap2, len);
+		if (i < len)
+			__clear_bit(i, cp);
+	}
+	time = ktime_get() - time;
+	pr_err("find_first_andnot_bit: %18llu ns, %6ld iterations\n", time, cnt);
+
+	return 0;
+}
+
+static int __init test_find_first_nor_bit(void *bitmap, const void *bitmap2, 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_nor_bit(cp, bitmap2, len);
+		if (i < len)
+			__set_bit(i, cp);
+	}
+	time = ktime_get() - time;
+	pr_err("find_first_nor_bit:    %18llu ns, %6ld iterations\n", time, cnt);
 
 	return 0;
 }
@@ -78,10 +118,10 @@ static int __init test_find_next_bit(const void *bitmap, unsigned long len)
 	ktime_t time;
 
 	time = ktime_get();
-	for (cnt = i = 0; i < BITMAP_LEN; cnt++)
-		i = find_next_bit(bitmap, BITMAP_LEN, i) + 1;
+	for (cnt = i = 0; i < len; cnt++)
+		i = find_next_bit(bitmap, len, i) + 1;
 	time = ktime_get() - time;
-	pr_err("find_next_bit:      %18llu ns, %6ld iterations\n", time, cnt);
+	pr_err("find_next_bit:         %18llu ns, %6ld iterations\n", time, cnt);
 
 	return 0;
 }
@@ -92,10 +132,10 @@ static int __init test_find_next_zero_bit(const void *bitmap, unsigned long len)
 	ktime_t time;
 
 	time = ktime_get();
-	for (cnt = i = 0; i < BITMAP_LEN; cnt++)
+	for (cnt = i = 0; i < len; cnt++)
 		i = find_next_zero_bit(bitmap, len, i) + 1;
 	time = ktime_get() - time;
-	pr_err("find_next_zero_bit: %18llu ns, %6ld iterations\n", time, cnt);
+	pr_err("find_next_zero_bit:    %18llu ns, %6ld iterations\n", time, cnt);
 
 	return 0;
 }
@@ -114,7 +154,7 @@ static int __init test_find_last_bit(const void *bitmap, unsigned long len)
 		len = l;
 	} while (len);
 	time = ktime_get() - time;
-	pr_err("find_last_bit:      %18llu ns, %6ld iterations\n", time, cnt);
+	pr_err("find_last_bit:         %18llu ns, %6ld iterations\n", time, cnt);
 
 	return 0;
 }
@@ -130,7 +170,7 @@ static int __init test_find_nth_bit(const unsigned long *bitmap, unsigned long l
 		WARN_ON(l >= len);
 	}
 	time = ktime_get() - time;
-	pr_err("find_nth_bit:       %18llu ns, %6ld iterations\n", time, w);
+	pr_err("find_nth_bit:          %18llu ns, %6ld iterations\n", time, w);
 
 	return 0;
 }
@@ -142,10 +182,55 @@ static int __init test_find_next_and_bit(const void *bitmap,
 	ktime_t time;
 
 	time = ktime_get();
-	for (cnt = i = 0; i < BITMAP_LEN; cnt++)
-		i = find_next_and_bit(bitmap, bitmap2, BITMAP_LEN, i + 1);
+	for (cnt = i = 0; i < len; cnt++)
+		i = find_next_and_bit(bitmap, bitmap2, len, i + 1);
+	time = ktime_get() - time;
+	pr_err("find_next_and_bit:     %18llu ns, %6ld iterations\n", time, cnt);
+
+	return 0;
+}
+
+static int __init test_find_next_andnot_bit(const void *bitmap,
+		const void *bitmap2, unsigned long len)
+{
+	unsigned long i, cnt;
+	ktime_t time;
+
+	time = ktime_get();
+	for (cnt = i = 0; i < len; cnt++)
+		i = find_next_andnot_bit(bitmap, bitmap2, len, i + 1);
+	time = ktime_get() - time;
+	pr_err("find_next_andnot_bit:  %18llu ns, %6ld iterations\n", time, cnt);
+
+	return 0;
+}
+
+static int __init test_find_next_nor_bit(const void *bitmap,
+		const void *bitmap2, unsigned long len)
+{
+	unsigned long i, cnt;
+	ktime_t time;
+
+	time = ktime_get();
+	for (cnt = i = 0; i < len; cnt++)
+		i = find_next_nor_bit(bitmap, bitmap2, len, i + 1);
+	time = ktime_get() - time;
+	pr_err("find_next_nor_bit:     %18llu ns, %6ld iterations\n", time, cnt);
+
+	return 0;
+}
+
+static int __init test_find_next_or_bit(const void *bitmap,
+		const void *bitmap2, unsigned long len)
+{
+	unsigned long i, cnt;
+	ktime_t time;
+
+	time = ktime_get();
+	for (cnt = i = 0; i < len; cnt++)
+		i = find_next_or_bit(bitmap, bitmap2, len, i + 1);
 	time = ktime_get() - time;
-	pr_err("find_next_and_bit:  %18llu ns, %6ld iterations\n", time, cnt);
+	pr_err("find_next_or_bit:      %18llu ns, %6ld iterations\n", time, cnt);
 
 	return 0;
 }
@@ -171,6 +256,11 @@ static int __init find_bit_test(void)
 	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);
+	test_find_first_andnot_bit(bitmap, bitmap2, BITMAP_LEN / 10);
+	test_find_next_andnot_bit(bitmap, bitmap2, BITMAP_LEN);
+	test_find_first_nor_bit(bitmap, bitmap2, BITMAP_LEN / 10);
+	test_find_next_nor_bit(bitmap, bitmap2, BITMAP_LEN);
+	test_find_next_or_bit(bitmap, bitmap2, BITMAP_LEN);
 
 	pr_err("\nStart testing find_bit() with sparse bitmap\n");
 
@@ -189,6 +279,11 @@ static int __init find_bit_test(void)
 	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);
+	test_find_first_andnot_bit(bitmap, bitmap2, BITMAP_LEN / 10);
+	test_find_next_andnot_bit(bitmap, bitmap2, BITMAP_LEN);
+	test_find_first_nor_bit(bitmap, bitmap2, BITMAP_LEN / 10);
+	test_find_next_nor_bit(bitmap, bitmap2, BITMAP_LEN);
+	test_find_next_or_bit(bitmap, bitmap2, BITMAP_LEN);
 
 	/*
 	 * Everything is OK. Return error just to let user run benchmark
-- 
2.39.2

[PATCH v3 6/6] cpumask: Implement cpumask_{first,next}_{nor,andnot}

[Mathieu Desnoyers]

Allow finding the first or next bit within two input cpumasks which is
either:

- both zero and zero,
- respectively one and zero.

Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
Cc: Yury Norov <yury.norov@gmail.com>
Cc: Rasmus Villemoes <linux@rasmusvillemoes.dk>
---
Changes since v0:
- Rename "notandnot" to "nor".
- Use __always_inline.
Changes since v1:
- Use small_cpumask_bits instead of nr_cpumask_bits, which is better
  optimized for NR_CPUS < BITS_PER_LONG.
---
 include/linux/cpumask.h | 60 +++++++++++++++++++++++++++++++++++++++++
 1 file changed, 60 insertions(+)

diff --git a/include/linux/cpumask.h b/include/linux/cpumask.h
index 23686bed441d..0bf6aabae62c 100644
--- a/include/linux/cpumask.h
+++ b/include/linux/cpumask.h
@@ -204,6 +204,32 @@ unsigned int cpumask_first_and_and(const struct cpumask *srcp1,
 				      cpumask_bits(srcp3), small_cpumask_bits);
 }
 
+/**
+ * cpumask_first_andnot - return the first cpu from *srcp1 & ~*srcp2
+ * @src1p: the first input
+ * @src2p: the second input
+ *
+ * Returns >= nr_cpu_ids if no cpus match in both.
+ */
+static __always_inline
+unsigned int cpumask_first_andnot(const struct cpumask *srcp1, const struct cpumask *srcp2)
+{
+	return find_first_andnot_bit(cpumask_bits(srcp1), cpumask_bits(srcp2), small_cpumask_bits);
+}
+
+/**
+ * cpumask_first_nor - return the first cpu from ~(*srcp1 | *srcp2)
+ * @src1p: the first input
+ * @src2p: the second input
+ *
+ * Returns >= nr_cpu_ids if no cpus match in both.
+ */
+static __always_inline
+unsigned int cpumask_first_nor(const struct cpumask *srcp1, const struct cpumask *srcp2)
+{
+	return find_first_nor_bit(cpumask_bits(srcp1), cpumask_bits(srcp2), small_cpumask_bits);
+}
+
 /**
  * cpumask_last - get the last CPU in a cpumask
  * @srcp:	- the cpumask pointer
@@ -246,6 +272,40 @@ static inline unsigned int cpumask_next_zero(int n, const struct cpumask *srcp)
 	return find_next_zero_bit(cpumask_bits(srcp), small_cpumask_bits, n+1);
 }
 
+/**
+ * cpumask_next_andnot - return the next cpu from *srcp1 & ~*srcp2
+ * @n: the cpu prior to the place to search (ie. return will be > @n)
+ * @src1p: the first input
+ * @src2p: the second input
+ *
+ * Returns >= nr_cpu_ids if no cpus match in both.
+ */
+static __always_inline
+unsigned int cpumask_next_andnot(int n, const struct cpumask *srcp1, const struct cpumask *srcp2)
+{
+	/* -1 is a legal arg here. */
+	if (n != -1)
+		cpumask_check(n);
+	return find_next_andnot_bit(cpumask_bits(srcp1), cpumask_bits(srcp2), small_cpumask_bits, n+1);
+}
+
+/**
+ * cpumask_next_nor - return the next cpu from ~(*srcp1 | *srcp2)
+ * @n: the cpu prior to the place to search (ie. return will be > @n)
+ * @src1p: the first input
+ * @src2p: the second input
+ *
+ * Returns >= nr_cpu_ids if no cpus match in both.
+ */
+static __always_inline
+unsigned int cpumask_next_nor(int n, const struct cpumask *srcp1, const struct cpumask *srcp2)
+{
+	/* -1 is a legal arg here. */
+	if (n != -1)
+		cpumask_check(n);
+	return find_next_nor_bit(cpumask_bits(srcp1), cpumask_bits(srcp2), small_cpumask_bits, n+1);
+}
+
 #if NR_CPUS == 1
 /* Uniprocessor: there is only one valid CPU */
 static inline unsigned int cpumask_local_spread(unsigned int i, int node)
-- 
2.39.2

Re: [PATCH v3 0/6] lib: Extend bitmap find binary operations

[Yury Norov]

On Fri, Aug 30, 2024 at 03:10:37PM -0400, Mathieu Desnoyers wrote:
> Extend bitmap find.h and cpumask.h with additional binary operations
> such as "nor".
> 
> Also extend the testing and benchmark coverage of those bitmap find with
> binary operations.
> 
> This is useful for NUMA-aware rseq concurrency IDs which depend on this
> series. The series can be found at:
> 
> https://lore.kernel.org/lkml/20240823185946.418340-1-mathieu.desnoyers@efficios.com/
> 

Added in bitmap-for-next for testing.

Thanks,
Yury

> 
> Mathieu Desnoyers (6):
>   lib: Clarify comment on top of find_next_andnot_bit
>   lib: Implement find_{first,next,nth}_nor_bit, for_each_nor_bit,
>     find_first_andnot_bit
>   lib: test bitmap sets binary operation iterators
>   lib: Fix test_find_first_and_bit and test_find_next_and_bit benchmark
>   lib: benchmark bitmap sets binary operation find
>   cpumask: Implement cpumask_{first,next}_{nor,andnot}
> 
>  include/linux/cpumask.h  |  60 ++++++++++++++++
>  include/linux/find.h     | 124 +++++++++++++++++++++++++++++++--
>  lib/find_bit.c           |  36 ++++++++++
>  lib/find_bit_benchmark.c | 143 +++++++++++++++++++++++++++++++++------
>  lib/test_bitmap.c        |  81 ++++++++++++++++++++++
>  5 files changed, 418 insertions(+), 26 deletions(-)
> 
> -- 
> 2.39.2

Re: [PATCH v3 0/6] lib: Extend bitmap find binary operations

[Mathieu Desnoyers]

On 2024-08-30 19:02, Yury Norov wrote:
> On Fri, Aug 30, 2024 at 03:10:37PM -0400, Mathieu Desnoyers wrote:
>> Extend bitmap find.h and cpumask.h with additional binary operations
>> such as "nor".
>>
>> Also extend the testing and benchmark coverage of those bitmap find with
>> binary operations.
>>
>> This is useful for NUMA-aware rseq concurrency IDs which depend on this
>> series. The series can be found at:
>>
>> https://lore.kernel.org/lkml/20240823185946.418340-1-mathieu.desnoyers@efficios.com/
>>
> 
> Added in bitmap-for-next for testing.

Hi Yuri,

FYI, after a lot of performance results analysis on variations over
the NUMA-aware rseq patch, I figured I need to take a drastically
different (and much simpler) approach to solve this in order to improve
cache locality as well, and it turns out I likely won't need the new
bitwise ops added by this series.

So feel free to keep it as a general improvement, or to drop it for
now.

Thanks,

Mathieu

> 
> Thanks,
> Yury
> 
>>
>> Mathieu Desnoyers (6):
>>    lib: Clarify comment on top of find_next_andnot_bit
>>    lib: Implement find_{first,next,nth}_nor_bit, for_each_nor_bit,
>>      find_first_andnot_bit
>>    lib: test bitmap sets binary operation iterators
>>    lib: Fix test_find_first_and_bit and test_find_next_and_bit benchmark
>>    lib: benchmark bitmap sets binary operation find
>>    cpumask: Implement cpumask_{first,next}_{nor,andnot}
>>
>>   include/linux/cpumask.h  |  60 ++++++++++++++++
>>   include/linux/find.h     | 124 +++++++++++++++++++++++++++++++--
>>   lib/find_bit.c           |  36 ++++++++++
>>   lib/find_bit_benchmark.c | 143 +++++++++++++++++++++++++++++++++------
>>   lib/test_bitmap.c        |  81 ++++++++++++++++++++++
>>   5 files changed, 418 insertions(+), 26 deletions(-)
>>
>> -- 
>> 2.39.2

-- 
Mathieu Desnoyers
EfficiOS Inc.
https://www.efficios.com