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

[PATCH v2 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.


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 | 103 ++++++++++++++++++++++++++++++--
 lib/test_bitmap.c        |  81 +++++++++++++++++++++++++
 5 files changed, 396 insertions(+), 8 deletions(-)

-- 
2.39.2

[PATCH v2 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 v2 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.
---
 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..cf3a49d18c1f 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);
+extern unsigned long _find_first_andnot_bit(const unsigned long *addr1,
+					 const unsigned long *addr2, unsigned long size);
+extern 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 v2 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 v2 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).

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

diff --git a/lib/find_bit_benchmark.c b/lib/find_bit_benchmark.c
index d3fb09e6eff1..aee2ebb6b3cd 100644
--- a/lib/find_bit_benchmark.c
+++ b/lib/find_bit_benchmark.c
@@ -30,18 +30,20 @@ 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)
 {
+	static DECLARE_BITMAP(cp, BITMAP_LEN) __initdata;
 	unsigned long i, cnt;
 	ktime_t time;
 
+	bitmap_copy(cp, bitmap, 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);
+		__clear_bit(i, cp);
 	}
 	time = ktime_get() - time;
 	pr_err("find_first_bit:     %18llu ns, %6ld iterations\n", time, cnt);
-- 
2.39.2

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

[Yury Norov]

On Thu, Aug 29, 2024 at 09:59:24AM -0400, Mathieu Desnoyers wrote:
> 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).
> 
> Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
> Cc: Yury Norov <yury.norov@gmail.com>
> Cc: Rasmus Villemoes <linux@rasmusvillemoes.dk>
> ---
>  lib/find_bit_benchmark.c | 10 ++++++----
>  1 file changed, 6 insertions(+), 4 deletions(-)
> 
> diff --git a/lib/find_bit_benchmark.c b/lib/find_bit_benchmark.c
> index d3fb09e6eff1..aee2ebb6b3cd 100644
> --- a/lib/find_bit_benchmark.c
> +++ b/lib/find_bit_benchmark.c
> @@ -30,18 +30,20 @@ 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.
>   */

Good to drop it, moreover, the comment is incorrect - we set all bits
to 0, not 1.

>  static int __init test_find_first_bit(void *bitmap, unsigned long len)
>  {
> +	static DECLARE_BITMAP(cp, BITMAP_LEN) __initdata;

This days we can allocate automatic variables, which is better than
statics:

   unsigned long *cp __free(bitmap) = bitmap_alloc(len, GFP_KERNEL);

If no objections, I can fix it inplace. The rest of the series looks
good. I'll add it in bitmap-for-next for testing shortly.

Thanks,
Yury

>  	unsigned long i, cnt;
>  	ktime_t time;
>  
> +	bitmap_copy(cp, bitmap, 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);
> +		__clear_bit(i, cp);
>  	}
>  	time = ktime_get() - time;
>  	pr_err("find_first_bit:     %18llu ns, %6ld iterations\n", time, cnt);
> -- 
> 2.39.2

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

[Mathieu Desnoyers]

On 2024-08-30 17:46, Yury Norov wrote:
> On Thu, Aug 29, 2024 at 09:59:24AM -0400, Mathieu Desnoyers wrote:
>> 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).
>>
>> Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
>> Cc: Yury Norov <yury.norov@gmail.com>
>> Cc: Rasmus Villemoes <linux@rasmusvillemoes.dk>
>> ---
>>   lib/find_bit_benchmark.c | 10 ++++++----
>>   1 file changed, 6 insertions(+), 4 deletions(-)
>>
>> diff --git a/lib/find_bit_benchmark.c b/lib/find_bit_benchmark.c
>> index d3fb09e6eff1..aee2ebb6b3cd 100644
>> --- a/lib/find_bit_benchmark.c
>> +++ b/lib/find_bit_benchmark.c
>> @@ -30,18 +30,20 @@ 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.
>>    */
> 
> Good to drop it, moreover, the comment is incorrect - we set all bits
> to 0, not 1.
> 
>>   static int __init test_find_first_bit(void *bitmap, unsigned long len)
>>   {
>> +	static DECLARE_BITMAP(cp, BITMAP_LEN) __initdata;
> 
> This days we can allocate automatic variables, which is better than
> statics:
> 
>     unsigned long *cp __free(bitmap) = bitmap_alloc(len, GFP_KERNEL);
> 
> If no objections, I can fix it inplace. The rest of the series looks
> good. I'll add it in bitmap-for-next for testing shortly.

I'm ok with the in-place fix, thanks!

Mathieu

> 
> Thanks,
> Yury
> 
>>   	unsigned long i, cnt;
>>   	ktime_t time;
>>   
>> +	bitmap_copy(cp, bitmap, 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);
>> +		__clear_bit(i, cp);
>>   	}
>>   	time = ktime_get() - time;
>>   	pr_err("find_first_bit:     %18llu ns, %6ld iterations\n", time, cnt);
>> -- 
>> 2.39.2

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

[PATCH v2 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.

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

diff --git a/lib/find_bit_benchmark.c b/lib/find_bit_benchmark.c
index aee2ebb6b3cd..3b16254dec23 100644
--- a/lib/find_bit_benchmark.c
+++ b/lib/find_bit_benchmark.c
@@ -70,6 +70,44 @@ static int __init test_find_first_and_bit(void *bitmap, const void *bitmap2, uns
 	return 0;
 }
 
+static int __init test_find_first_andnot_bit(void *bitmap, const void *bitmap2, unsigned long len)
+{
+	static DECLARE_BITMAP(cp, BITMAP_LEN) __initdata;
+	unsigned long i, cnt;
+	ktime_t time;
+
+	bitmap_copy(cp, bitmap, BITMAP_LEN);
+
+	time = ktime_get();
+	for (cnt = i = 0; i < len; cnt++) {
+		i = find_first_andnot_bit(cp, bitmap2, 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)
+{
+	static DECLARE_BITMAP(cp, BITMAP_LEN) __initdata;
+	unsigned long i, cnt;
+	ktime_t time;
+
+	bitmap_copy(cp, bitmap, BITMAP_LEN);
+
+	time = ktime_get();
+	for (cnt = i = 0; i < len; cnt++) {
+		i = find_first_nor_bit(cp, bitmap2, len);
+		__set_bit(i, cp);
+	}
+	time = ktime_get() - time;
+	pr_err("find_first_nor_bit: %18llu ns, %6ld iterations\n", time, cnt);
+
+	return 0;
+}
+
 static int __init test_find_next_bit(const void *bitmap, unsigned long len)
 {
 	unsigned long i, cnt;
@@ -148,6 +186,51 @@ static int __init test_find_next_and_bit(const void *bitmap,
 	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 < BITMAP_LEN; cnt++)
+		i = find_next_andnot_bit(bitmap, bitmap2, BITMAP_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 < BITMAP_LEN; cnt++)
+		i = find_next_nor_bit(bitmap, bitmap2, BITMAP_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 < BITMAP_LEN; cnt++)
+		i = find_next_or_bit(bitmap, bitmap2, BITMAP_LEN, i + 1);
+	time = ktime_get() - time;
+	pr_err("find_next_or_bit:  %18llu ns, %6ld iterations\n", time, cnt);
+
+	return 0;
+}
+
 static int __init find_bit_test(void)
 {
 	unsigned long nbits = BITMAP_LEN / SPARSE;
@@ -169,6 +252,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 / 2);
 	test_find_next_and_bit(bitmap, bitmap2, BITMAP_LEN);
+	test_find_first_andnot_bit(bitmap, bitmap2, BITMAP_LEN / 2);
+	test_find_next_andnot_bit(bitmap, bitmap2, BITMAP_LEN);
+	test_find_first_nor_bit(bitmap, bitmap2, BITMAP_LEN / 2);
+	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");
 
@@ -187,6 +275,11 @@ static int __init find_bit_test(void)
 	test_find_first_bit(bitmap, BITMAP_LEN);
 	test_find_first_and_bit(bitmap, bitmap2, BITMAP_LEN);
 	test_find_next_and_bit(bitmap, bitmap2, BITMAP_LEN);
+	test_find_first_andnot_bit(bitmap, bitmap2, BITMAP_LEN);
+	test_find_next_andnot_bit(bitmap, bitmap2, BITMAP_LEN);
+	test_find_first_nor_bit(bitmap, bitmap2, BITMAP_LEN);
+	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

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

[Yury Norov]

On Thu, Aug 29, 2024 at 09:59:25AM -0400, Mathieu Desnoyers wrote:
> 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.

Can you please show how the test output looks on your system now? I'll
add that in commit message.

> 
> Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
> Cc: Yury Norov <yury.norov@gmail.com>
> Cc: Rasmus Villemoes <linux@rasmusvillemoes.dk>
> ---
>  lib/find_bit_benchmark.c | 93 ++++++++++++++++++++++++++++++++++++++++
>  1 file changed, 93 insertions(+)
> 
> diff --git a/lib/find_bit_benchmark.c b/lib/find_bit_benchmark.c
> index aee2ebb6b3cd..3b16254dec23 100644
> --- a/lib/find_bit_benchmark.c
> +++ b/lib/find_bit_benchmark.c
> @@ -70,6 +70,44 @@ static int __init test_find_first_and_bit(void *bitmap, const void *bitmap2, uns
>  	return 0;
>  }
>  
> +static int __init test_find_first_andnot_bit(void *bitmap, const void *bitmap2, unsigned long len)
> +{
> +	static DECLARE_BITMAP(cp, BITMAP_LEN) __initdata;
> +	unsigned long i, cnt;
> +	ktime_t time;
> +
> +	bitmap_copy(cp, bitmap, BITMAP_LEN);
> +
> +	time = ktime_get();
> +	for (cnt = i = 0; i < len; cnt++) {
> +		i = find_first_andnot_bit(cp, bitmap2, 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)
> +{
> +	static DECLARE_BITMAP(cp, BITMAP_LEN) __initdata;
> +	unsigned long i, cnt;
> +	ktime_t time;
> +
> +	bitmap_copy(cp, bitmap, BITMAP_LEN);
> +
> +	time = ktime_get();
> +	for (cnt = i = 0; i < len; cnt++) {
> +		i = find_first_nor_bit(cp, bitmap2, len);
> +		__set_bit(i, cp);
> +	}
> +	time = ktime_get() - time;
> +	pr_err("find_first_nor_bit: %18llu ns, %6ld iterations\n", time, cnt);
> +
> +	return 0;
> +}
> +
>  static int __init test_find_next_bit(const void *bitmap, unsigned long len)
>  {
>  	unsigned long i, cnt;
> @@ -148,6 +186,51 @@ static int __init test_find_next_and_bit(const void *bitmap,
>  	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 < BITMAP_LEN; cnt++)
> +		i = find_next_andnot_bit(bitmap, bitmap2, BITMAP_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 < BITMAP_LEN; cnt++)
> +		i = find_next_nor_bit(bitmap, bitmap2, BITMAP_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 < BITMAP_LEN; cnt++)
> +		i = find_next_or_bit(bitmap, bitmap2, BITMAP_LEN, i + 1);
> +	time = ktime_get() - time;
> +	pr_err("find_next_or_bit:  %18llu ns, %6ld iterations\n", time, cnt);
> +
> +	return 0;
> +}
> +
>  static int __init find_bit_test(void)
>  {
>  	unsigned long nbits = BITMAP_LEN / SPARSE;
> @@ -169,6 +252,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 / 2);
>  	test_find_next_and_bit(bitmap, bitmap2, BITMAP_LEN);
> +	test_find_first_andnot_bit(bitmap, bitmap2, BITMAP_LEN / 2);
> +	test_find_next_andnot_bit(bitmap, bitmap2, BITMAP_LEN);
> +	test_find_first_nor_bit(bitmap, bitmap2, BITMAP_LEN / 2);
> +	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");
>  
> @@ -187,6 +275,11 @@ static int __init find_bit_test(void)
>  	test_find_first_bit(bitmap, BITMAP_LEN);
>  	test_find_first_and_bit(bitmap, bitmap2, BITMAP_LEN);
>  	test_find_next_and_bit(bitmap, bitmap2, BITMAP_LEN);
> +	test_find_first_andnot_bit(bitmap, bitmap2, BITMAP_LEN);
> +	test_find_next_andnot_bit(bitmap, bitmap2, BITMAP_LEN);
> +	test_find_first_nor_bit(bitmap, bitmap2, BITMAP_LEN);
> +	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

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

[Mathieu Desnoyers]

On 2024-08-30 17:48, Yury Norov wrote:
> On Thu, Aug 29, 2024 at 09:59:25AM -0400, Mathieu Desnoyers wrote:
>> 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.
> 
> Can you please show how the test output looks on your system now? I'll
> add that in commit message.

Start testing find_bit() with random-filled bitmap
find_next_bit:                  576314 ns, 163810 iterations
find_next_zero_bit:             626847 ns, 163871 iterations
find_last_bit:                  465050 ns, 163810 iterations
find_nth_bit:                  2720718 ns,  16329 iterations
find_first_bit:                1409431 ns,  16330 iterations
find_first_and_bit:           15216406 ns,  40975 iterations
find_next_and_bit:              324624 ns,  81708 iterations
find_first_andnot_bit:           23856039 ns,  40955 iterations
find_next_andnot_bit:              327734 ns,  82103 iterations
find_first_nor_bit:           21911075 ns,  40956 iterations
find_next_nor_bit:              345315 ns,  81919 iterations
find_next_or_bit:              886338 ns, 245762 iterations

Start testing find_bit() with sparse bitmap
find_next_bit:                    8870 ns,    656 iterations
find_next_zero_bit:            1188951 ns, 327025 iterations
find_last_bit:                    8380 ns,    656 iterations
find_nth_bit:                  1110068 ns,    655 iterations
find_first_bit:                 455799 ns,    656 iterations
find_first_and_bit:               6521 ns,      2 iterations
find_next_and_bit:                3540 ns,      2 iterations
find_first_andnot_bit:             785844 ns,    655 iterations
find_next_andnot_bit:                8950 ns,    655 iterations
find_first_nor_bit:          338646832 ns, 326373 iterations
find_next_nor_bit:             1264144 ns, 326372 iterations
find_next_or_bit:               14020 ns,   1309 iterations

Relevant lscpu output:

Architecture:             x86_64
   CPU op-mode(s):         32-bit, 64-bit
   Address sizes:          52 bits physical, 57 bits virtual
   Byte Order:             Little Endian
CPU(s):                   384
   On-line CPU(s) list:    0-383
Vendor ID:                AuthenticAMD
   Model name:             AMD EPYC 9654 96-Core Processor
     CPU family:           25
     Model:                17
     Thread(s) per core:   2
     Core(s) per socket:   96
     Socket(s):            2
     Stepping:             1
     Frequency boost:      enabled
     CPU(s) scaling MHz:   100%
     CPU max MHz:          3709.0000
     CPU min MHz:          400.0000
     BogoMIPS:             4799.80
     Flags:                fpu vme de pse tsc msr pae mce cx8 apic sep mtrr pge mca cmov pat pse36 clflush mmx fxsr sse sse2 ht syscall nx mmxext
                           fxsr_opt pdpe1gb rdtscp lm constant_tsc rep_good amd_lbr_v2 nopl xtopology nonstop_tsc cpuid extd_apicid aperfmperf rap
                           l pni pclmulqdq monitor ssse3 fma cx16 pcid sse4_1 sse4_2 x2apic movbe popcnt aes xsave avx f16c rdrand lahf_lm cmp_leg
                           acy svm extapic cr8_legacy abm sse4a misalignsse 3dnowprefetch osvw ibs skinit wdt tce topoext perfctr_core perfctr_nb
                           bpext perfctr_llc mwaitx cpb cat_l3 cdp_l3 hw_pstate ssbd mba perfmon_v2 ibrs ibpb stibp ibrs_enhanced vmmcall fsgsbase
                            bmi1 avx2 smep bmi2 erms invpcid cqm rdt_a avx512f avx512dq rdseed adx smap avx512ifma clflushopt clwb avx512cd sha_ni
                            avx512bw avx512vl xsaveopt xsavec xgetbv1 xsaves cqm_llc cqm_occup_llc cqm_mbm_total cqm_mbm_local user_shstk avx512_b
                           f16 clzero irperf xsaveerptr rdpru wbnoinvd amd_ppin cppc arat npt lbrv svm_lock nrip_save tsc_scale vmcb_clean flushby
                           asid decodeassists pausefilter pfthreshold avic v_vmsave_vmload vgif x2avic v_spec_ctrl vnmi avx512vbmi umip pku ospke
                           avx512_vbmi2 gfni vaes vpclmulqdq avx512_vnni avx512_bitalg avx512_vpopcntdq la57 rdpid overflow_recov succor smca fsrm
                            flush_l1d debug_swap
Virtualization features:
   Virtualization:         AMD-V
Caches (sum of all):
   L1d:                    6 MiB (192 instances)
   L1i:                    6 MiB (192 instances)
   L2:                     192 MiB (192 instances)
   L3:                     768 MiB (24 instances)
NUMA:
   NUMA node(s):           24
   NUMA node0 CPU(s):      0-7,192-199
   NUMA node1 CPU(s):      8-15,200-207
   NUMA node2 CPU(s):      16-23,208-215
   NUMA node3 CPU(s):      24-31,216-223
   NUMA node4 CPU(s):      32-39,224-231
   NUMA node5 CPU(s):      40-47,232-239
   NUMA node6 CPU(s):      48-55,240-247
   NUMA node7 CPU(s):      56-63,248-255
   NUMA node8 CPU(s):      64-71,256-263
   NUMA node9 CPU(s):      72-79,264-271
   NUMA node10 CPU(s):     80-87,272-279
   NUMA node11 CPU(s):     88-95,280-287
   NUMA node12 CPU(s):     96-103,288-295
   NUMA node13 CPU(s):     104-111,296-303
   NUMA node14 CPU(s):     112-119,304-311
   NUMA node15 CPU(s):     120-127,312-319
   NUMA node16 CPU(s):     128-135,320-327
   NUMA node17 CPU(s):     136-143,328-335
   NUMA node18 CPU(s):     144-151,336-343
   NUMA node19 CPU(s):     152-159,344-351
   NUMA node20 CPU(s):     160-167,352-359
   NUMA node21 CPU(s):     168-175,360-367
   NUMA node22 CPU(s):     176-183,368-375
   NUMA node23 CPU(s):     184-191,376-383
Vulnerabilities:
   Gather data sampling:   Not affected
   Itlb multihit:          Not affected
   L1tf:                   Not affected
   Mds:                    Not affected
   Meltdown:               Not affected
   Mmio stale data:        Not affected
   Reg file data sampling: Not affected
   Retbleed:               Not affected
   Spec rstack overflow:   Vulnerable
   Spec store bypass:      Vulnerable
   Spectre v1:             Vulnerable: __user pointer sanitization and usercopy barriers only; no swapgs barriers
   Spectre v2:             Vulnerable; IBPB: disabled; STIBP: disabled; PBRSB-eIBRS: Not affected; BHI: Not affected
   Srbds:                  Not affected
   Tsx async abort:        Not affected



> 
>>
>> Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
>> Cc: Yury Norov <yury.norov@gmail.com>
>> Cc: Rasmus Villemoes <linux@rasmusvillemoes.dk>
>> ---
>>   lib/find_bit_benchmark.c | 93 ++++++++++++++++++++++++++++++++++++++++
>>   1 file changed, 93 insertions(+)
>>
>> diff --git a/lib/find_bit_benchmark.c b/lib/find_bit_benchmark.c
>> index aee2ebb6b3cd..3b16254dec23 100644
>> --- a/lib/find_bit_benchmark.c
>> +++ b/lib/find_bit_benchmark.c
>> @@ -70,6 +70,44 @@ static int __init test_find_first_and_bit(void *bitmap, const void *bitmap2, uns
>>   	return 0;
>>   }
>>   
>> +static int __init test_find_first_andnot_bit(void *bitmap, const void *bitmap2, unsigned long len)
>> +{
>> +	static DECLARE_BITMAP(cp, BITMAP_LEN) __initdata;
>> +	unsigned long i, cnt;
>> +	ktime_t time;
>> +
>> +	bitmap_copy(cp, bitmap, BITMAP_LEN);
>> +
>> +	time = ktime_get();
>> +	for (cnt = i = 0; i < len; cnt++) {
>> +		i = find_first_andnot_bit(cp, bitmap2, 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)
>> +{
>> +	static DECLARE_BITMAP(cp, BITMAP_LEN) __initdata;
>> +	unsigned long i, cnt;
>> +	ktime_t time;
>> +
>> +	bitmap_copy(cp, bitmap, BITMAP_LEN);
>> +
>> +	time = ktime_get();
>> +	for (cnt = i = 0; i < len; cnt++) {
>> +		i = find_first_nor_bit(cp, bitmap2, len);
>> +		__set_bit(i, cp);
>> +	}
>> +	time = ktime_get() - time;
>> +	pr_err("find_first_nor_bit: %18llu ns, %6ld iterations\n", time, cnt);
>> +
>> +	return 0;
>> +}
>> +
>>   static int __init test_find_next_bit(const void *bitmap, unsigned long len)
>>   {
>>   	unsigned long i, cnt;
>> @@ -148,6 +186,51 @@ static int __init test_find_next_and_bit(const void *bitmap,
>>   	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 < BITMAP_LEN; cnt++)
>> +		i = find_next_andnot_bit(bitmap, bitmap2, BITMAP_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 < BITMAP_LEN; cnt++)
>> +		i = find_next_nor_bit(bitmap, bitmap2, BITMAP_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 < BITMAP_LEN; cnt++)
>> +		i = find_next_or_bit(bitmap, bitmap2, BITMAP_LEN, i + 1);
>> +	time = ktime_get() - time;
>> +	pr_err("find_next_or_bit:  %18llu ns, %6ld iterations\n", time, cnt);
>> +
>> +	return 0;
>> +}
>> +
>>   static int __init find_bit_test(void)
>>   {
>>   	unsigned long nbits = BITMAP_LEN / SPARSE;
>> @@ -169,6 +252,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 / 2);
>>   	test_find_next_and_bit(bitmap, bitmap2, BITMAP_LEN);
>> +	test_find_first_andnot_bit(bitmap, bitmap2, BITMAP_LEN / 2);
>> +	test_find_next_andnot_bit(bitmap, bitmap2, BITMAP_LEN);
>> +	test_find_first_nor_bit(bitmap, bitmap2, BITMAP_LEN / 2);
>> +	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");
>>   
>> @@ -187,6 +275,11 @@ static int __init find_bit_test(void)
>>   	test_find_first_bit(bitmap, BITMAP_LEN);
>>   	test_find_first_and_bit(bitmap, bitmap2, BITMAP_LEN);
>>   	test_find_next_and_bit(bitmap, bitmap2, BITMAP_LEN);
>> +	test_find_first_andnot_bit(bitmap, bitmap2, BITMAP_LEN);
>> +	test_find_next_andnot_bit(bitmap, bitmap2, BITMAP_LEN);
>> +	test_find_first_nor_bit(bitmap, bitmap2, BITMAP_LEN);
>> +	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

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

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

[Yury Norov]

On Fri, Aug 30, 2024 at 12:07:53PM -0400, Mathieu Desnoyers wrote:
> On 2024-08-30 17:48, Yury Norov wrote:
> > On Thu, Aug 29, 2024 at 09:59:25AM -0400, Mathieu Desnoyers wrote:
> > > 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.
> > 
> > Can you please show how the test output looks on your system now? I'll
> > add that in commit message.
> 
> Start testing find_bit() with random-filled bitmap
> find_next_bit:                  576314 ns, 163810 iterations
> find_next_zero_bit:             626847 ns, 163871 iterations
> find_last_bit:                  465050 ns, 163810 iterations
> find_nth_bit:                  2720718 ns,  16329 iterations
> find_first_bit:                1409431 ns,  16330 iterations
> find_first_and_bit:           15216406 ns,  40975 iterations
> find_next_and_bit:              324624 ns,  81708 iterations
> find_first_andnot_bit:           23856039 ns,  40955 iterations
> find_next_andnot_bit:              327734 ns,  82103 iterations
> find_first_nor_bit:           21911075 ns,  40956 iterations
> find_next_nor_bit:              345315 ns,  81919 iterations
> find_next_or_bit:              886338 ns, 245762 iterations
> 
> Start testing find_bit() with sparse bitmap
> find_next_bit:                    8870 ns,    656 iterations
> find_next_zero_bit:            1188951 ns, 327025 iterations
> find_last_bit:                    8380 ns,    656 iterations
> find_nth_bit:                  1110068 ns,    655 iterations
> find_first_bit:                 455799 ns,    656 iterations
> find_first_and_bit:               6521 ns,      2 iterations
> find_next_and_bit:                3540 ns,      2 iterations
> find_first_andnot_bit:             785844 ns,    655 iterations
> find_next_andnot_bit:                8950 ns,    655 iterations
> find_first_nor_bit:          338646832 ns, 326373 iterations

0.3 sec is too much. Consider a slower CPU where it may be 10
times slower... Can you keep that in a range of few milliseconds?
It's more than enough to grab stable perf results.

> find_next_nor_bit:             1264144 ns, 326372 iterations
> find_next_or_bit:               14020 ns,   1309 iterations

Before the columns were all aligned. Can you please send a v3
with this fixed, and address the other comments?

Thanks,
Yury

> 
> Relevant lscpu output:
> 
> Architecture:             x86_64
>   CPU op-mode(s):         32-bit, 64-bit
>   Address sizes:          52 bits physical, 57 bits virtual
>   Byte Order:             Little Endian
> CPU(s):                   384
>   On-line CPU(s) list:    0-383
> Vendor ID:                AuthenticAMD
>   Model name:             AMD EPYC 9654 96-Core Processor
>     CPU family:           25
>     Model:                17
>     Thread(s) per core:   2
>     Core(s) per socket:   96
>     Socket(s):            2
>     Stepping:             1
>     Frequency boost:      enabled
>     CPU(s) scaling MHz:   100%
>     CPU max MHz:          3709.0000
>     CPU min MHz:          400.0000
>     BogoMIPS:             4799.80
>     Flags:                fpu vme de pse tsc msr pae mce cx8 apic sep mtrr pge mca cmov pat pse36 clflush mmx fxsr sse sse2 ht syscall nx mmxext
>                           fxsr_opt pdpe1gb rdtscp lm constant_tsc rep_good amd_lbr_v2 nopl xtopology nonstop_tsc cpuid extd_apicid aperfmperf rap
>                           l pni pclmulqdq monitor ssse3 fma cx16 pcid sse4_1 sse4_2 x2apic movbe popcnt aes xsave avx f16c rdrand lahf_lm cmp_leg
>                           acy svm extapic cr8_legacy abm sse4a misalignsse 3dnowprefetch osvw ibs skinit wdt tce topoext perfctr_core perfctr_nb
>                           bpext perfctr_llc mwaitx cpb cat_l3 cdp_l3 hw_pstate ssbd mba perfmon_v2 ibrs ibpb stibp ibrs_enhanced vmmcall fsgsbase
>                            bmi1 avx2 smep bmi2 erms invpcid cqm rdt_a avx512f avx512dq rdseed adx smap avx512ifma clflushopt clwb avx512cd sha_ni
>                            avx512bw avx512vl xsaveopt xsavec xgetbv1 xsaves cqm_llc cqm_occup_llc cqm_mbm_total cqm_mbm_local user_shstk avx512_b
>                           f16 clzero irperf xsaveerptr rdpru wbnoinvd amd_ppin cppc arat npt lbrv svm_lock nrip_save tsc_scale vmcb_clean flushby
>                           asid decodeassists pausefilter pfthreshold avic v_vmsave_vmload vgif x2avic v_spec_ctrl vnmi avx512vbmi umip pku ospke
>                           avx512_vbmi2 gfni vaes vpclmulqdq avx512_vnni avx512_bitalg avx512_vpopcntdq la57 rdpid overflow_recov succor smca fsrm
>                            flush_l1d debug_swap
> Virtualization features:
>   Virtualization:         AMD-V
> Caches (sum of all):
>   L1d:                    6 MiB (192 instances)
>   L1i:                    6 MiB (192 instances)
>   L2:                     192 MiB (192 instances)
>   L3:                     768 MiB (24 instances)
> NUMA:
>   NUMA node(s):           24
>   NUMA node0 CPU(s):      0-7,192-199
>   NUMA node1 CPU(s):      8-15,200-207
>   NUMA node2 CPU(s):      16-23,208-215
>   NUMA node3 CPU(s):      24-31,216-223
>   NUMA node4 CPU(s):      32-39,224-231
>   NUMA node5 CPU(s):      40-47,232-239
>   NUMA node6 CPU(s):      48-55,240-247
>   NUMA node7 CPU(s):      56-63,248-255
>   NUMA node8 CPU(s):      64-71,256-263
>   NUMA node9 CPU(s):      72-79,264-271
>   NUMA node10 CPU(s):     80-87,272-279
>   NUMA node11 CPU(s):     88-95,280-287
>   NUMA node12 CPU(s):     96-103,288-295
>   NUMA node13 CPU(s):     104-111,296-303
>   NUMA node14 CPU(s):     112-119,304-311
>   NUMA node15 CPU(s):     120-127,312-319
>   NUMA node16 CPU(s):     128-135,320-327
>   NUMA node17 CPU(s):     136-143,328-335
>   NUMA node18 CPU(s):     144-151,336-343
>   NUMA node19 CPU(s):     152-159,344-351
>   NUMA node20 CPU(s):     160-167,352-359
>   NUMA node21 CPU(s):     168-175,360-367
>   NUMA node22 CPU(s):     176-183,368-375
>   NUMA node23 CPU(s):     184-191,376-383
> Vulnerabilities:
>   Gather data sampling:   Not affected
>   Itlb multihit:          Not affected
>   L1tf:                   Not affected
>   Mds:                    Not affected
>   Meltdown:               Not affected
>   Mmio stale data:        Not affected
>   Reg file data sampling: Not affected
>   Retbleed:               Not affected
>   Spec rstack overflow:   Vulnerable
>   Spec store bypass:      Vulnerable
>   Spectre v1:             Vulnerable: __user pointer sanitization and usercopy barriers only; no swapgs barriers
>   Spectre v2:             Vulnerable; IBPB: disabled; STIBP: disabled; PBRSB-eIBRS: Not affected; BHI: Not affected
>   Srbds:                  Not affected
>   Tsx async abort:        Not affected
> 
> 
> 
> > 
> > > 
> > > Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
> > > Cc: Yury Norov <yury.norov@gmail.com>
> > > Cc: Rasmus Villemoes <linux@rasmusvillemoes.dk>
> > > ---
> > >   lib/find_bit_benchmark.c | 93 ++++++++++++++++++++++++++++++++++++++++
> > >   1 file changed, 93 insertions(+)
> > > 
> > > diff --git a/lib/find_bit_benchmark.c b/lib/find_bit_benchmark.c
> > > index aee2ebb6b3cd..3b16254dec23 100644
> > > --- a/lib/find_bit_benchmark.c
> > > +++ b/lib/find_bit_benchmark.c
> > > @@ -70,6 +70,44 @@ static int __init test_find_first_and_bit(void *bitmap, const void *bitmap2, uns
> > >   	return 0;
> > >   }
> > > +static int __init test_find_first_andnot_bit(void *bitmap, const void *bitmap2, unsigned long len)
> > > +{
> > > +	static DECLARE_BITMAP(cp, BITMAP_LEN) __initdata;
> > > +	unsigned long i, cnt;
> > > +	ktime_t time;
> > > +
> > > +	bitmap_copy(cp, bitmap, BITMAP_LEN);
> > > +
> > > +	time = ktime_get();
> > > +	for (cnt = i = 0; i < len; cnt++) {
> > > +		i = find_first_andnot_bit(cp, bitmap2, 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)
> > > +{
> > > +	static DECLARE_BITMAP(cp, BITMAP_LEN) __initdata;
> > > +	unsigned long i, cnt;
> > > +	ktime_t time;
> > > +
> > > +	bitmap_copy(cp, bitmap, BITMAP_LEN);
> > > +
> > > +	time = ktime_get();
> > > +	for (cnt = i = 0; i < len; cnt++) {
> > > +		i = find_first_nor_bit(cp, bitmap2, len);
> > > +		__set_bit(i, cp);
> > > +	}
> > > +	time = ktime_get() - time;
> > > +	pr_err("find_first_nor_bit: %18llu ns, %6ld iterations\n", time, cnt);
> > > +
> > > +	return 0;
> > > +}
> > > +
> > >   static int __init test_find_next_bit(const void *bitmap, unsigned long len)
> > >   {
> > >   	unsigned long i, cnt;
> > > @@ -148,6 +186,51 @@ static int __init test_find_next_and_bit(const void *bitmap,
> > >   	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 < BITMAP_LEN; cnt++)
> > > +		i = find_next_andnot_bit(bitmap, bitmap2, BITMAP_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 < BITMAP_LEN; cnt++)
> > > +		i = find_next_nor_bit(bitmap, bitmap2, BITMAP_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 < BITMAP_LEN; cnt++)
> > > +		i = find_next_or_bit(bitmap, bitmap2, BITMAP_LEN, i + 1);
> > > +	time = ktime_get() - time;
> > > +	pr_err("find_next_or_bit:  %18llu ns, %6ld iterations\n", time, cnt);
> > > +
> > > +	return 0;
> > > +}
> > > +
> > >   static int __init find_bit_test(void)
> > >   {
> > >   	unsigned long nbits = BITMAP_LEN / SPARSE;
> > > @@ -169,6 +252,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 / 2);
> > >   	test_find_next_and_bit(bitmap, bitmap2, BITMAP_LEN);
> > > +	test_find_first_andnot_bit(bitmap, bitmap2, BITMAP_LEN / 2);
> > > +	test_find_next_andnot_bit(bitmap, bitmap2, BITMAP_LEN);
> > > +	test_find_first_nor_bit(bitmap, bitmap2, BITMAP_LEN / 2);
> > > +	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");
> > > @@ -187,6 +275,11 @@ static int __init find_bit_test(void)
> > >   	test_find_first_bit(bitmap, BITMAP_LEN);
> > >   	test_find_first_and_bit(bitmap, bitmap2, BITMAP_LEN);
> > >   	test_find_next_and_bit(bitmap, bitmap2, BITMAP_LEN);
> > > +	test_find_first_andnot_bit(bitmap, bitmap2, BITMAP_LEN);
> > > +	test_find_next_andnot_bit(bitmap, bitmap2, BITMAP_LEN);
> > > +	test_find_first_nor_bit(bitmap, bitmap2, BITMAP_LEN);
> > > +	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
> 
> -- 
> Mathieu Desnoyers
> EfficiOS Inc.
> https://www.efficios.com

[PATCH v2 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 v2 0/6] lib: Extend bitmap find binary operations

[Yury Norov]

On Thu, Aug 29, 2024 at 09:59:20AM -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.
 
Hi Mathieu,

Thanks for the series! I appreciate your time nailing it down, and
especially the tests provided. A couple nits is that we don't need
an 'extern' specifier,  and would better avoid local statics, even
in tests.

I'll fix that inplace and apply in bitmap-for-next. Can you share
a link for your work that requires the new API? I need to point it
when sending a merge request.

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 | 103 ++++++++++++++++++++++++++++++--
>  lib/test_bitmap.c        |  81 +++++++++++++++++++++++++
>  5 files changed, 396 insertions(+), 8 deletions(-)
> 
> -- 
> 2.39.2

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

[Mathieu Desnoyers]

On 2024-08-30 17:56, Yury Norov wrote:
> On Thu, Aug 29, 2024 at 09:59:20AM -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.
>   
> Hi Mathieu,
> 
> Thanks for the series! I appreciate your time nailing it down, and
> especially the tests provided. A couple nits is that we don't need
> an 'extern' specifier,  and would better avoid local statics, even
> in tests.

OK. I've mostly followed the style present in the files I modified.
I'm OK if you change that in place.

> 
> I'll fix that inplace and apply in bitmap-for-next. Can you share
> a link for your work that requires the new API? I need to point it
> when sending a merge request.

Here is the latest version posted, before I split the bitmap patches
into a serparate series:

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

Please note that I am currently doing additional tests/benchmarks/schedstat
instrumentation and bug fixes on the RSEQ numa-aware patch.

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 | 103 ++++++++++++++++++++++++++++++--
>>   lib/test_bitmap.c        |  81 +++++++++++++++++++++++++
>>   5 files changed, 396 insertions(+), 8 deletions(-)
>>
>> -- 
>> 2.39.2

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