[PATCH 0/5] lib/find: add find_nth_bit()

[PATCH 0/5] lib/find: add find_nth_bit()

[Yury Norov]

Kernel lacks for a function that searches for Nth bit in a bitmap.
Usually people do it like this:
	for_each_set_bit(bit, mask, size)
		if (--n == 0)
			return bit;

Which is not so elegant, and very slow.

This series adds fast routines for this task, and applies them where
appropriate.

While here, move thin wrappers around find_bit() in nodemask.c to a
corresponding header, and because nodemask.c is empty after that,
remove it.

On top of "lib: cleanup bitmap-related headers":
https://lkml.org/lkml/2022/7/6/1202

Yury Norov (5):
  lib: add find_nth(,and,andnot)_bit()
  lib/bitmap: add tests for find_nth_bit()
  remove bitmap_ord_to_pos
  cpumask: add cpumask_nth_{,and,andnot}
  lib/nodemask: inline next_node_in() and node_random()

 MAINTAINERS              |  1 -
 include/linux/bitmap.h   |  1 -
 include/linux/bitops.h   | 19 ++++++++++
 include/linux/cpumask.h  | 44 ++++++++++++++++++++++
 include/linux/find.h     | 79 ++++++++++++++++++++++++++++++++++++++++
 include/linux/nodemask.h | 27 +++++++++++---
 lib/Makefile             |  2 +-
 lib/bitmap.c             | 36 ++----------------
 lib/cpumask.c            | 26 ++++++-------
 lib/find_bit.c           | 20 ++++++++++
 lib/find_bit_benchmark.c | 17 +++++++++
 lib/nodemask.c           | 31 ----------------
 lib/test_bitmap.c        | 36 +++++++++++++++++-
 13 files changed, 250 insertions(+), 89 deletions(-)
 delete mode 100644 lib/nodemask.c

-- 
2.34.1

[PATCH 1/5] lib: add find_nth(,and,andnot)_bit()

[Yury Norov]

Kernel lacks for a function that searches for Nth bit in a bitmap.
Usually people do it like this:
	for_each_set_bit(bit, mask, size)
		if (--n == 0)
			return bit;

We can do it more efficiently, if we:
1. find a word containing Nth bit, using hweight(); and
2. find the bit, using a helper fns(), that works similarly to
   __ffs() and ffz().

fns() is implemented as a simple loop. For x86_64, there's PDEP instruction
to do that: ret = clz(pdep(1 << idx, num)). However, for large bitmaps the
most of improvement comes from using hweight(), so I kept fns() simple.

New find_nth_bit() is ~70 times faster on x86_64/kvm:
for_each_bit:                  7154190 ns,  16411 iterations
find_nth_bit:                505493126 ns,  16315 iterations

With all that, a family of 3 new functions is added, and used where
appropriate in the following patches.

Signed-off-by: Yury Norov <yury.norov@gmail.com>
---
 include/linux/bitops.h | 19 ++++++++++
 include/linux/find.h   | 79 ++++++++++++++++++++++++++++++++++++++++++
 lib/find_bit.c         | 20 +++++++++++
 3 files changed, 118 insertions(+)

diff --git a/include/linux/bitops.h b/include/linux/bitops.h
index 7aaed501f768..86072cfcbe17 100644
--- a/include/linux/bitops.h
+++ b/include/linux/bitops.h
@@ -196,6 +196,25 @@ static inline unsigned long __ffs64(u64 word)
 	return __ffs((unsigned long)word);
 }
 
+/**
+ * fns - find N'th set bit in a 64 bit word
+ * @word: The 64 bit word
+ * @n: Bit to find
+ */
+static inline unsigned long fns(unsigned long word, unsigned int n)
+{
+	unsigned int bit;
+
+	while (word) {
+		bit = __ffs(word);
+		if (--n == 0)
+			return bit;
+		__clear_bit(bit, &word);
+	}
+
+	return BITS_PER_LONG;
+}
+
 /**
  * assign_bit - Assign value to a bit in memory
  * @nr: the bit to set
diff --git a/include/linux/find.h b/include/linux/find.h
index 424ef67d4a42..00a24bc596d0 100644
--- a/include/linux/find.h
+++ b/include/linux/find.h
@@ -12,6 +12,8 @@ extern unsigned long _find_next_bit(const unsigned long *addr1,
 		const unsigned long *addr2, unsigned long nbits,
 		unsigned long start, unsigned long invert, unsigned long le);
 extern unsigned long _find_first_bit(const unsigned long *addr, unsigned long size);
+unsigned long _find_nth_bit(const unsigned long *addr1, const unsigned long *addr2,
+				unsigned long size, unsigned long n, bool not);
 extern unsigned long _find_first_and_bit(const unsigned long *addr1,
 					 const unsigned long *addr2, unsigned long size);
 extern unsigned long _find_first_zero_bit(const unsigned long *addr, unsigned long size);
@@ -125,6 +127,83 @@ unsigned long find_first_bit(const unsigned long *addr, unsigned long size)
 }
 #endif
 
+/**
+ * find_nth_bit - find N'th set bit in a memory region
+ * @addr: The address to start the search at
+ * @size: The maximum number of bits to search
+ * @n: The number of set bit, which position is needed
+ *
+ * Returns the bit number of the N'th set bit.
+ * If no such, returns @size.
+ */
+static inline
+unsigned long find_nth_bit(const unsigned long *addr, unsigned long size, unsigned long n)
+{
+	if (n == 0 || n > size)
+		return size;
+
+	if (small_const_nbits(size)) {
+		unsigned long val =  *addr & GENMASK(size - 1, 0);
+
+		return val ? fns(val, n) : size;
+	}
+
+	return _find_nth_bit(addr, NULL, size, n, false);
+}
+
+/**
+ * find_nth_and_bit - find N'th set 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
+ *
+ * Returns the bit number of the N'th set bit.
+ * If no such, returns @size.
+ */
+static inline
+unsigned long find_nth_and_bit(const unsigned long *addr1, const unsigned long *addr2,
+				unsigned long size, unsigned long n)
+{
+	if (n == 0 || 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_bit(addr1, addr2, size, n, false);
+}
+
+/**
+ * find_nth_andnot_bit - find N'th set bit in 2 memory regions,
+ *			 flipping bits in 2nd region
+ * @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
+ *
+ * Returns the bit number of the N'th set bit.
+ * If no such, returns @size.
+ */
+static inline
+unsigned long find_nth_andnot_bit(const unsigned long *addr1, const unsigned long *addr2,
+				unsigned long size, unsigned long n)
+{
+	if (n == 0 || 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_bit(addr1, addr2, size, n, true);
+}
+
 #ifndef find_first_and_bit
 /**
  * find_first_and_bit - find the first set bit in both memory regions
diff --git a/lib/find_bit.c b/lib/find_bit.c
index 1b8e4b2a9cba..7b8ad12c8cc7 100644
--- a/lib/find_bit.c
+++ b/lib/find_bit.c
@@ -89,6 +89,26 @@ unsigned long _find_first_bit(const unsigned long *addr, unsigned long size)
 EXPORT_SYMBOL(_find_first_bit);
 #endif
 
+unsigned long _find_nth_bit(const unsigned long *addr1, const unsigned long *addr2,
+				unsigned long size, unsigned long n, bool not)
+{
+	unsigned long val, idx, w;
+
+	for (idx = 0; idx * BITS_PER_LONG < size; idx++, n -= w) {
+		val = addr1[idx];
+		if (addr2)
+			val &= not ? ~addr2[idx] : addr2[idx];
+
+		w = hweight_long(val);
+		if (w >= n)
+			return min(idx * BITS_PER_LONG + fns(val, n), size);
+	}
+
+	return size;
+
+}
+EXPORT_SYMBOL(_find_nth_bit);
+
 #ifndef find_first_and_bit
 /*
  * Find the first set bit in two memory regions.
-- 
2.34.1

Re: [PATCH 1/5] lib: add find_nth(,and,andnot)_bit()

[Rasmus Villemoes]

On 06/07/2022 20.22, Yury Norov wrote:
> Kernel lacks for a function that searches for Nth bit in a bitmap.
> Usually people do it like this:
> 	for_each_set_bit(bit, mask, size)
> 		if (--n == 0)
> 			return bit;
> 
> We can do it more efficiently, if we:
> 1. find a word containing Nth bit, using hweight(); and
> 2. find the bit, using a helper fns(), that works similarly to
>    __ffs() and ffz().
> 
> fns() is implemented as a simple loop. For x86_64, there's PDEP instruction
> to do that: ret = clz(pdep(1 << idx, num)). However, for large bitmaps the
> most of improvement comes from using hweight(), so I kept fns() simple.
> 
> New find_nth_bit() is ~70 times faster on x86_64/kvm:
> for_each_bit:                  7154190 ns,  16411 iterations
> find_nth_bit:                505493126 ns,  16315 iterations

Eh, have you interchanged these somehow, otherwise this reads as
find_nth_bit being ~70 times _slower_?

> With all that, a family of 3 new functions is added, and used where
> appropriate in the following patches.
> 
> Signed-off-by: Yury Norov <yury.norov@gmail.com>
> ---
>  include/linux/bitops.h | 19 ++++++++++
>  include/linux/find.h   | 79 ++++++++++++++++++++++++++++++++++++++++++
>  lib/find_bit.c         | 20 +++++++++++
>  3 files changed, 118 insertions(+)
> 
> diff --git a/include/linux/bitops.h b/include/linux/bitops.h
> index 7aaed501f768..86072cfcbe17 100644
> --- a/include/linux/bitops.h
> +++ b/include/linux/bitops.h
> @@ -196,6 +196,25 @@ static inline unsigned long __ffs64(u64 word)
>  	return __ffs((unsigned long)word);
>  }
>  
> +/**
> + * fns - find N'th set bit in a 64 bit word
> + * @word: The 64 bit word
> + * @n: Bit to find
> + */
> +static inline unsigned long fns(unsigned long word, unsigned int n)
> +{
> +	unsigned int bit;
> +
> +	while (word) {
> +		bit = __ffs(word);
> +		if (--n == 0)
> +			return bit;
> +		__clear_bit(bit, &word);
> +	}
> +
> +	return BITS_PER_LONG;
> +}

Urgh.  "unsigned long" is not necessarily a 64 bit word. And I don't
like that the index is apparently 1-based (and that surprising API isn't
spelled out anywhere). This is also way too big to be inline IMO.

>  #ifndef find_first_and_bit
>  /**
>   * find_first_and_bit - find the first set bit in both memory regions
> diff --git a/lib/find_bit.c b/lib/find_bit.c
> index 1b8e4b2a9cba..7b8ad12c8cc7 100644
> --- a/lib/find_bit.c
> +++ b/lib/find_bit.c
> @@ -89,6 +89,26 @@ unsigned long _find_first_bit(const unsigned long *addr, unsigned long size)
>  EXPORT_SYMBOL(_find_first_bit);
>  #endif
>  
> +unsigned long _find_nth_bit(const unsigned long *addr1, const unsigned long *addr2,
> +				unsigned long size, unsigned long n, bool not)
> +{
> +	unsigned long val, idx, w;
> +
> +	for (idx = 0; idx * BITS_PER_LONG < size; idx++, n -= w) {
> +		val = addr1[idx];
> +		if (addr2)
> +			val &= not ? ~addr2[idx] : addr2[idx];

Maybe this could be microoptimized by doing

unsigned long addr2mask = not ? ~0UL : 0UL;
...

  val &= (addr2[idx] ^ addr2mask);

but I don't think it'll make a difference.

Rasmus

Re: [PATCH 1/5] lib: add find_nth(,and,andnot)_bit()

[Yury Norov]

On Thu, Jul 07, 2022 at 09:25:07AM +0200, Rasmus Villemoes wrote:
> On 06/07/2022 20.22, Yury Norov wrote:
> > Kernel lacks for a function that searches for Nth bit in a bitmap.
> > Usually people do it like this:
> > 	for_each_set_bit(bit, mask, size)
> > 		if (--n == 0)
> > 			return bit;
> > 
> > We can do it more efficiently, if we:
> > 1. find a word containing Nth bit, using hweight(); and
> > 2. find the bit, using a helper fns(), that works similarly to
> >    __ffs() and ffz().
> > 
> > fns() is implemented as a simple loop. For x86_64, there's PDEP instruction
> > to do that: ret = clz(pdep(1 << idx, num)). However, for large bitmaps the
> > most of improvement comes from using hweight(), so I kept fns() simple.
> > 
> > New find_nth_bit() is ~70 times faster on x86_64/kvm:
> > for_each_bit:                  7154190 ns,  16411 iterations
> > find_nth_bit:                505493126 ns,  16315 iterations
> 
> Eh, have you interchanged these somehow, otherwise this reads as
> find_nth_bit being ~70 times _slower_?

I didn't change the pr_err("find_nth_bit: ...") line in the test, and
had to edit manually when preparing the series. The numbers are fair,
it's just manual edit issue.
 
> > With all that, a family of 3 new functions is added, and used where
> > appropriate in the following patches.
> > 
> > Signed-off-by: Yury Norov <yury.norov@gmail.com>
> > ---
> >  include/linux/bitops.h | 19 ++++++++++
> >  include/linux/find.h   | 79 ++++++++++++++++++++++++++++++++++++++++++
> >  lib/find_bit.c         | 20 +++++++++++
> >  3 files changed, 118 insertions(+)
> > 
> > diff --git a/include/linux/bitops.h b/include/linux/bitops.h
> > index 7aaed501f768..86072cfcbe17 100644
> > --- a/include/linux/bitops.h
> > +++ b/include/linux/bitops.h
> > @@ -196,6 +196,25 @@ static inline unsigned long __ffs64(u64 word)
> >  	return __ffs((unsigned long)word);
> >  }
> >  
> > +/**
> > + * fns - find N'th set bit in a 64 bit word
> > + * @word: The 64 bit word
> > + * @n: Bit to find
> > + */
> > +static inline unsigned long fns(unsigned long word, unsigned int n)
> > +{
> > +	unsigned int bit;
> > +
> > +	while (word) {
> > +		bit = __ffs(word);
> > +		if (--n == 0)
> > +			return bit;
> > +		__clear_bit(bit, &word);
> > +	}
> > +
> > +	return BITS_PER_LONG;
> > +}
> 
> Urgh.  "unsigned long" is not necessarily a 64 bit word.

I'm not sure I understand your concern. The fns() returns an index
of Nth bit (0...31 or 0...63 correspondingly), or 32/64 if such bit
doesn't exit.

> And I don't
> like that the index is apparently 1-based (and that surprising API isn't
> spelled out anywhere).

Yeah... My motivation to start counting from 1 is to keep consistency
with ffs: __ffs(word) <=> fns(word, 1). So, the argument is not an
index - we are looking for the index; instead, it's an order - first,
second, third etc.

But the return value - is index, counting from 0. It looks weird, but
after some poking around, I think this is the most logical way to go.
I'll add a note in the comments for v2.

> This is also way too big to be inline IMO.

Maybe yes... I've got nothing against moving it into c-file. On the
other hand, arch/alpha/include/asm/bitops.h is full of 5-line inline
functions, just for example. Let's see what others say.

> >  #ifndef find_first_and_bit
> >  /**
> >   * find_first_and_bit - find the first set bit in both memory regions
> > diff --git a/lib/find_bit.c b/lib/find_bit.c
> > index 1b8e4b2a9cba..7b8ad12c8cc7 100644
> > --- a/lib/find_bit.c
> > +++ b/lib/find_bit.c
> > @@ -89,6 +89,26 @@ unsigned long _find_first_bit(const unsigned long *addr, unsigned long size)
> >  EXPORT_SYMBOL(_find_first_bit);
> >  #endif
> >  
> > +unsigned long _find_nth_bit(const unsigned long *addr1, const unsigned long *addr2,
> > +				unsigned long size, unsigned long n, bool not)
> > +{
> > +	unsigned long val, idx, w;
> > +
> > +	for (idx = 0; idx * BITS_PER_LONG < size; idx++, n -= w) {
> > +		val = addr1[idx];
> > +		if (addr2)
> > +			val &= not ? ~addr2[idx] : addr2[idx];
> 
> Maybe this could be microoptimized by doing
> 
> unsigned long addr2mask = not ? ~0UL : 0UL;
> ...
> 
>   val &= (addr2[idx] ^ addr2mask);
> 
> but I don't think it'll make a difference.

I'll try.

Thanks for review!

Thanks,
Yury

Re: [PATCH 1/5] lib: add find_nth(,and,andnot)_bit()

[Rasmus Villemoes]

On 07/07/2022 23.03, Yury Norov wrote:

>> And I don't
>> like that the index is apparently 1-based (and that surprising API isn't
>> spelled out anywhere).
> 
> Yeah... My motivation to start counting from 1 is to keep consistency
> with ffs: __ffs(word) <=> fns(word, 1). 

I understand that you're translating that second f in ffs (find First
set) to a 1. But I disagree that that's necessarily a logical thing to
do. Everybody understands that (given a C or python or... context) when
some prose talks about "the first element in an array", it's the one at
[0]. So I find it much more natural that the set bits in a word are
enumerated 0, 1, ..., popcount(w)-1.

Rasmus

Re: [PATCH 1/5] lib: add find_nth(,and,andnot)_bit()

[Andy Shevchenko]

On Fri, Jul 8, 2022 at 10:55 AM Rasmus Villemoes
<linux@rasmusvillemoes.dk> wrote:
> On 07/07/2022 23.03, Yury Norov wrote:
>
> >> And I don't
> >> like that the index is apparently 1-based (and that surprising API isn't
> >> spelled out anywhere).
> >
> > Yeah... My motivation to start counting from 1 is to keep consistency
> > with ffs: __ffs(word) <=> fns(word, 1).
>
> I understand that you're translating that second f in ffs (find First
> set) to a 1. But I disagree that that's necessarily a logical thing to
> do. Everybody understands that (given a C or python or... context) when
> some prose talks about "the first element in an array", it's the one at
> [0]. So I find it much more natural that the set bits in a word are
> enumerated 0, 1, ..., popcount(w)-1.

I agree that here we operate with an array of bits, which naturally
starts from bit 0.

-- 
With Best Regards,
Andy Shevchenko

Re: [PATCH 1/5] lib: add find_nth(,and,andnot)_bit()

[Yury Norov]

On Fri, Jul 8, 2022 at 2:13 AM Andy Shevchenko
<andy.shevchenko@gmail.com> wrote:
>
> On Fri, Jul 8, 2022 at 10:55 AM Rasmus Villemoes
> <linux@rasmusvillemoes.dk> wrote:
> > On 07/07/2022 23.03, Yury Norov wrote:
> >
> > >> And I don't
> > >> like that the index is apparently 1-based (and that surprising API isn't
> > >> spelled out anywhere).
> > >
> > > Yeah... My motivation to start counting from 1 is to keep consistency
> > > with ffs: __ffs(word) <=> fns(word, 1).
> >
> > I understand that you're translating that second f in ffs (find First
> > set) to a 1. But I disagree that that's necessarily a logical thing to
> > do. Everybody understands that (given a C or python or... context) when
> > some prose talks about "the first element in an array", it's the one at
> > [0]. So I find it much more natural that the set bits in a word are
> > enumerated 0, 1, ..., popcount(w)-1.
>
> I agree that here we operate with an array of bits, which naturally
> starts from bit 0.

OK, I'll send v2 shortly

[PATCH 2/5] lib/bitmap: add tests for find_nth_bit()

[Yury Norov]

Add functional and performance tests for find_nth_bit().

Signed-off-by: Yury Norov <yury.norov@gmail.com>
---
 lib/find_bit_benchmark.c | 17 +++++++++++++++++
 lib/test_bitmap.c        | 36 ++++++++++++++++++++++++++++++++++--
 2 files changed, 51 insertions(+), 2 deletions(-)

diff --git a/lib/find_bit_benchmark.c b/lib/find_bit_benchmark.c
index db904b57d4b8..aad769c6ca84 100644
--- a/lib/find_bit_benchmark.c
+++ b/lib/find_bit_benchmark.c
@@ -115,6 +115,22 @@ static int __init test_find_last_bit(const void *bitmap, unsigned long len)
 	return 0;
 }
 
+static int __init test_find_nth_bit(const unsigned long *bitmap, unsigned long len)
+{
+	unsigned long l, n, w = bitmap_weight(bitmap, len);
+	ktime_t time;
+
+	time = ktime_get();
+	for (n = 1; n <= w; n++) {
+		l = find_nth_bit(bitmap, len, n);
+		WARN_ON(l >= len);
+	}
+	time = ktime_get() - time;
+	pr_err("find_nth_bit:       %18llu ns, %6ld iterations\n", time, w);
+
+	return 0;
+}
+
 static int __init test_find_next_and_bit(const void *bitmap,
 		const void *bitmap2, unsigned long len)
 {
@@ -142,6 +158,7 @@ static int __init find_bit_test(void)
 	test_find_next_bit(bitmap, BITMAP_LEN);
 	test_find_next_zero_bit(bitmap, BITMAP_LEN);
 	test_find_last_bit(bitmap, BITMAP_LEN);
+	test_find_nth_bit(bitmap, BITMAP_LEN/10);
 
 	/*
 	 * test_find_first_bit() may take some time, so
diff --git a/lib/test_bitmap.c b/lib/test_bitmap.c
index d5923a640457..b4b53d8c66ae 100644
--- a/lib/test_bitmap.c
+++ b/lib/test_bitmap.c
@@ -16,6 +16,8 @@
 
 #include "../tools/testing/selftests/kselftest_module.h"
 
+#define EXP1_IN_BITS	(sizeof(exp1) * 8)
+
 KSTM_MODULE_GLOBALS();
 
 static char pbl_buffer[PAGE_SIZE] __initdata;
@@ -219,6 +221,36 @@ static void __init test_zero_clear(void)
 	expect_eq_pbl("", bmap, 1024);
 }
 
+static void __init test_find_nth_bit(void)
+{
+	unsigned long b, bit, cnt = 0;
+	DECLARE_BITMAP(bmap, 64 * 3);
+
+	bitmap_zero(bmap, 64 * 3);
+	__set_bit(10, bmap);
+	__set_bit(20, bmap);
+	__set_bit(30, bmap);
+	__set_bit(40, bmap);
+	__set_bit(50, bmap);
+	__set_bit(60, bmap);
+	__set_bit(80, bmap);
+	__set_bit(123, bmap);
+
+	expect_eq_uint(10,  find_nth_bit(bmap, 64 * 3, 1));
+	expect_eq_uint(20,  find_nth_bit(bmap, 64 * 3, 2));
+	expect_eq_uint(30,  find_nth_bit(bmap, 64 * 3, 3));
+	expect_eq_uint(40,  find_nth_bit(bmap, 64 * 3, 4));
+	expect_eq_uint(50,  find_nth_bit(bmap, 64 * 3, 5));
+	expect_eq_uint(60,  find_nth_bit(bmap, 64 * 3, 6));
+	expect_eq_uint(80,  find_nth_bit(bmap, 64 * 3, 7));
+	expect_eq_uint(123, find_nth_bit(bmap, 64 * 3, 8));
+
+	for_each_set_bit(bit, exp1, EXP1_IN_BITS) {
+		b = find_nth_bit(exp1, EXP1_IN_BITS, ++cnt);
+		expect_eq_uint(b, bit);
+	}
+}
+
 static void __init test_fill_set(void)
 {
 	DECLARE_BITMAP(bmap, 1024);
@@ -557,8 +589,6 @@ static void __init test_bitmap_parse(void)
 	}
 }
 
-#define EXP1_IN_BITS	(sizeof(exp1) * 8)
-
 static void __init test_bitmap_arr32(void)
 {
 	unsigned int nbits, next_bit;
@@ -884,6 +914,8 @@ static void __init selftest(void)
 	test_for_each_set_clump8();
 	test_bitmap_cut();
 	test_bitmap_print_buf();
+
+	test_find_nth_bit();
 }
 
 KSTM_MODULE_LOADERS(test_bitmap);
-- 
2.34.1

[PATCH 3/5] lib/bitmap: remove bitmap_ord_to_pos

[Yury Norov]

Now that we have find_nth_bit(), we can drop bitmap_ord_to_pos().

Signed-off-by: Yury Norov <yury.norov@gmail.com>
---
 include/linux/bitmap.h |  1 -
 lib/bitmap.c           | 36 +++---------------------------------
 lib/nodemask.c         |  3 +--
 3 files changed, 4 insertions(+), 36 deletions(-)

diff --git a/include/linux/bitmap.h b/include/linux/bitmap.h
index b2198665a064..91506057b240 100644
--- a/include/linux/bitmap.h
+++ b/include/linux/bitmap.h
@@ -222,7 +222,6 @@ void bitmap_copy_le(unsigned long *dst, const unsigned long *src, unsigned int n
 #else
 #define bitmap_copy_le bitmap_copy
 #endif
-unsigned int bitmap_ord_to_pos(const unsigned long *bitmap, unsigned int ord, unsigned int nbits);
 int bitmap_print_to_pagebuf(bool list, char *buf,
 				   const unsigned long *maskp, int nmaskbits);
 
diff --git a/lib/bitmap.c b/lib/bitmap.c
index b580b381eca1..0b1082aa0b2c 100644
--- a/lib/bitmap.c
+++ b/lib/bitmap.c
@@ -956,36 +956,6 @@ static int bitmap_pos_to_ord(const unsigned long *buf, unsigned int pos, unsigne
 	return __bitmap_weight(buf, pos);
 }
 
-/**
- * bitmap_ord_to_pos - find position of n-th set bit in bitmap
- *	@buf: pointer to bitmap
- *	@ord: ordinal bit position (n-th set bit, n >= 0)
- *	@nbits: number of valid bit positions in @buf
- *
- * Map the ordinal offset of bit @ord in @buf to its position in @buf.
- * Value of @ord should be in range 0 <= @ord < weight(buf). If @ord
- * >= weight(buf), returns @nbits.
- *
- * If for example, just bits 4 through 7 are set in @buf, then @ord
- * values 0 through 3 will get mapped to 4 through 7, respectively,
- * and all other @ord values returns @nbits.  When @ord value 3
- * gets mapped to (returns) @pos value 7 in this example, that means
- * that the 3rd set bit (starting with 0th) is at position 7 in @buf.
- *
- * The bit positions 0 through @nbits-1 are valid positions in @buf.
- */
-unsigned int bitmap_ord_to_pos(const unsigned long *buf, unsigned int ord, unsigned int nbits)
-{
-	unsigned int pos;
-
-	for (pos = find_first_bit(buf, nbits);
-	     pos < nbits && ord;
-	     pos = find_next_bit(buf, nbits, pos + 1))
-		ord--;
-
-	return pos;
-}
-
 /**
  * bitmap_remap - Apply map defined by a pair of bitmaps to another bitmap
  *	@dst: remapped result
@@ -1035,7 +1005,7 @@ void bitmap_remap(unsigned long *dst, const unsigned long *src,
 		if (n < 0 || w == 0)
 			set_bit(oldbit, dst);	/* identity map */
 		else
-			set_bit(bitmap_ord_to_pos(new, n % w, nbits), dst);
+			set_bit(find_nth_bit(new, nbits, n % w + 1), dst);
 	}
 }
 EXPORT_SYMBOL(bitmap_remap);
@@ -1074,7 +1044,7 @@ int bitmap_bitremap(int oldbit, const unsigned long *old,
 	if (n < 0 || w == 0)
 		return oldbit;
 	else
-		return bitmap_ord_to_pos(new, n % w, bits);
+		return find_nth_bit(new, bits, n % w + 1);
 }
 EXPORT_SYMBOL(bitmap_bitremap);
 
@@ -1198,7 +1168,7 @@ void bitmap_onto(unsigned long *dst, const unsigned long *orig,
 	 * The following code is a more efficient, but less
 	 * obvious, equivalent to the loop:
 	 *	for (m = 0; m < bitmap_weight(relmap, bits); m++) {
-	 *		n = bitmap_ord_to_pos(orig, m, bits);
+	 *		n = find_nth_bit(orig, bits, m + 1);
 	 *		if (test_bit(m, orig))
 	 *			set_bit(n, dst);
 	 *	}
diff --git a/lib/nodemask.c b/lib/nodemask.c
index e22647f5181b..7dad4ce8ff59 100644
--- a/lib/nodemask.c
+++ b/lib/nodemask.c
@@ -24,8 +24,7 @@ int node_random(const nodemask_t *maskp)
 
 	w = nodes_weight(*maskp);
 	if (w)
-		bit = bitmap_ord_to_pos(maskp->bits,
-			get_random_int() % w, MAX_NUMNODES);
+		bit = find_nth_bit(maskp->bits, MAX_NUMNODES, get_random_int() % w + 1);
 	return bit;
 }
 #endif
-- 
2.34.1

[PATCH 4/5] cpumask: add cpumask_nth_{,and,andnot}

[Yury Norov]

Add cpumask_nth_{,and,andnot} as wrappers around corresponding
find functions, and use it in cpumask_local_spread().

Signed-off-by: Yury Norov <yury.norov@gmail.com>
---
 include/linux/cpumask.h | 44 +++++++++++++++++++++++++++++++++++++++++
 lib/cpumask.c           | 26 +++++++++++-------------
 2 files changed, 55 insertions(+), 15 deletions(-)

diff --git a/include/linux/cpumask.h b/include/linux/cpumask.h
index 0738a6c9be40..8cf460368fca 100644
--- a/include/linux/cpumask.h
+++ b/include/linux/cpumask.h
@@ -379,6 +379,50 @@ unsigned int cpumask_any_but(const struct cpumask *mask, unsigned int cpu)
 }
 #endif /* SMP */
 
+/**
+ * cpumask_nth - get the first cpu in a cpumask
+ * @srcp: the cpumask pointer
+ * @cpu: the N'th cpu to find, starting from 1
+ *
+ * Returns >= nr_cpu_ids if such cpu doesn't exist.
+ */
+static inline unsigned int cpumask_nth(unsigned int cpu, const struct cpumask *srcp)
+{
+	return find_nth_bit(cpumask_bits(srcp), nr_cpumask_bits, cpumask_check(cpu));
+}
+
+/**
+ * cpumask_nth_and - get the first cpu in 2 cpumasks
+ * @srcp1: the cpumask pointer
+ * @srcp2: the cpumask pointer
+ * @cpu: the N'th cpu to find, starting from 1
+ *
+ * Returns >= nr_cpu_ids if such cpu doesn't exist.
+ */
+static inline
+unsigned int cpumask_nth_and(unsigned int cpu, const struct cpumask *srcp1,
+							const struct cpumask *srcp2)
+{
+	return find_nth_and_bit(cpumask_bits(srcp1), cpumask_bits(srcp2),
+				nr_cpumask_bits, cpumask_check(cpu));
+}
+
+/**
+ * cpumask_nth_andnot - get the first cpu set in 1st cpumask, and clear in 2nd.
+ * @srcp1: the cpumask pointer
+ * @srcp2: the cpumask pointer
+ * @cpu: the N'th cpu to find, starting from 1
+ *
+ * Returns >= nr_cpu_ids if such cpu doesn't exist.
+ */
+static inline
+unsigned int cpumask_nth_andnot(unsigned int cpu, const struct cpumask *srcp1,
+							const struct cpumask *srcp2)
+{
+	return find_nth_andnot_bit(cpumask_bits(srcp1), cpumask_bits(srcp2),
+				nr_cpumask_bits, cpumask_check(cpu));
+}
+
 #define CPU_BITS_NONE						\
 {								\
 	[0 ... BITS_TO_LONGS(NR_CPUS)-1] = 0UL			\
diff --git a/lib/cpumask.c b/lib/cpumask.c
index f0ae119be8c4..56aeb9c9d702 100644
--- a/lib/cpumask.c
+++ b/lib/cpumask.c
@@ -128,23 +128,19 @@ unsigned int cpumask_local_spread(unsigned int i, int node)
 	i %= num_online_cpus();
 
 	if (node == NUMA_NO_NODE) {
-		for_each_cpu(cpu, cpu_online_mask)
-			if (i-- == 0)
-				return cpu;
+		cpu = cpumask_nth(i + 1, cpu_online_mask);
+		if (cpu < nr_cpu_ids)
+			return cpu;
 	} else {
 		/* NUMA first. */
-		for_each_cpu_and(cpu, cpumask_of_node(node), cpu_online_mask)
-			if (i-- == 0)
-				return cpu;
-
-		for_each_cpu(cpu, cpu_online_mask) {
-			/* Skip NUMA nodes, done above. */
-			if (cpumask_test_cpu(cpu, cpumask_of_node(node)))
-				continue;
-
-			if (i-- == 0)
-				return cpu;
-		}
+		cpu = cpumask_nth_and(i + 1, cpu_online_mask, cpumask_of_node(node));
+		if (cpu < nr_cpu_ids)
+			return cpu;
+
+		/* Skip NUMA nodes, done above. */
+		cpu = cpumask_nth_andnot(i + 1, cpu_online_mask, cpumask_of_node(node));
+		if (cpu < nr_cpu_ids)
+			return cpu;
 	}
 	BUG();
 }
-- 
2.34.1

[PATCH 5/5] lib/nodemask: inline next_node_in() and node_random()

[Yury Norov]

The functions are pretty thin wrappers around find_bit engine, and
keeping them in c-file prevents compiler from small_const_nbits()
optimization, which must take place for all systems with MAX_NUMNODES
less than BITS_PER_LONG (default is 16 for me).

Moving them in header file doesn't blow up the kernel size:
add/remove: 1/2 grow/shrink: 9/5 up/down: 968/-88 (880)

Signed-off-by: Yury Norov <yury.norov@gmail.com>
---
 MAINTAINERS              |  1 -
 include/linux/nodemask.h | 27 ++++++++++++++++++++++-----
 lib/Makefile             |  2 +-
 lib/nodemask.c           | 30 ------------------------------
 4 files changed, 23 insertions(+), 37 deletions(-)
 delete mode 100644 lib/nodemask.c

diff --git a/MAINTAINERS b/MAINTAINERS
index f808826509e5..314dd1054246 100644
--- a/MAINTAINERS
+++ b/MAINTAINERS
@@ -3540,7 +3540,6 @@ F:	lib/bitmap.c
 F:	lib/cpumask.c
 F:	lib/find_bit.c
 F:	lib/find_bit_benchmark.c
-F:	lib/nodemask.c
 F:	lib/test_bitmap.c
 F:	tools/include/linux/bitmap.h
 F:	tools/include/linux/find.h
diff --git a/include/linux/nodemask.h b/include/linux/nodemask.h
index 0f233b76c9ce..48ebe4007955 100644
--- a/include/linux/nodemask.h
+++ b/include/linux/nodemask.h
@@ -94,6 +94,7 @@
 #include <linux/bitmap.h>
 #include <linux/minmax.h>
 #include <linux/numa.h>
+#include <linux/random.h>
 
 typedef struct { DECLARE_BITMAP(bits, MAX_NUMNODES); } nodemask_t;
 extern nodemask_t _unused_nodemask_arg_;
@@ -276,7 +277,14 @@ static inline unsigned int __next_node(int n, const nodemask_t *srcp)
  * the first node in src if needed.  Returns MAX_NUMNODES if src is empty.
  */
 #define next_node_in(n, src) __next_node_in((n), &(src))
-unsigned int __next_node_in(int node, const nodemask_t *srcp);
+static inline unsigned int __next_node_in(int node, const nodemask_t *srcp)
+{
+	unsigned int ret = __next_node(node, srcp);
+
+	if (ret == MAX_NUMNODES)
+		ret = __first_node(srcp);
+	return ret;
+}
 
 static inline void init_nodemask_of_node(nodemask_t *mask, int node)
 {
@@ -493,14 +501,23 @@ static inline int num_node_state(enum node_states state)
 
 #endif
 
+/*
+ * Return the bit number of a random bit set in the nodemask.
+ * (returns NUMA_NO_NODE if nodemask is empty)
+ */
+static inline int node_random(const nodemask_t *maskp)
+{
 #if defined(CONFIG_NUMA) && (MAX_NUMNODES > 1)
-extern int node_random(const nodemask_t *maskp);
+	int w, bit = NUMA_NO_NODE;
+
+	w = nodes_weight(*maskp);
+	if (w)
+		bit = find_nth_bit(maskp->bits, MAX_NUMNODES, get_random_int() % w + 1);
+	return bit;
 #else
-static inline int node_random(const nodemask_t *mask)
-{
 	return 0;
-}
 #endif
+}
 
 #define node_online_map 	node_states[N_ONLINE]
 #define node_possible_map 	node_states[N_POSSIBLE]
diff --git a/lib/Makefile b/lib/Makefile
index f99bf61f8bbc..731cea0342d1 100644
--- a/lib/Makefile
+++ b/lib/Makefile
@@ -33,7 +33,7 @@ lib-y := ctype.o string.o vsprintf.o cmdline.o \
 	 flex_proportions.o ratelimit.o show_mem.o \
 	 is_single_threaded.o plist.o decompress.o kobject_uevent.o \
 	 earlycpio.o seq_buf.o siphash.o dec_and_lock.o \
-	 nmi_backtrace.o nodemask.o win_minmax.o memcat_p.o \
+	 nmi_backtrace.o win_minmax.o memcat_p.o \
 	 buildid.o
 
 lib-$(CONFIG_PRINTK) += dump_stack.o
diff --git a/lib/nodemask.c b/lib/nodemask.c
deleted file mode 100644
index 7dad4ce8ff59..000000000000
--- a/lib/nodemask.c
+++ /dev/null
@@ -1,30 +0,0 @@
-// SPDX-License-Identifier: GPL-2.0
-#include <linux/nodemask.h>
-#include <linux/module.h>
-#include <linux/random.h>
-
-unsigned int __next_node_in(int node, const nodemask_t *srcp)
-{
-	unsigned int ret = __next_node(node, srcp);
-
-	if (ret == MAX_NUMNODES)
-		ret = __first_node(srcp);
-	return ret;
-}
-EXPORT_SYMBOL(__next_node_in);
-
-#ifdef CONFIG_NUMA
-/*
- * Return the bit number of a random bit set in the nodemask.
- * (returns NUMA_NO_NODE if nodemask is empty)
- */
-int node_random(const nodemask_t *maskp)
-{
-	int w, bit = NUMA_NO_NODE;
-
-	w = nodes_weight(*maskp);
-	if (w)
-		bit = find_nth_bit(maskp->bits, MAX_NUMNODES, get_random_int() % w + 1);
-	return bit;
-}
-#endif
-- 
2.34.1

[PATCH v2 0/5] lib/find: add find_nth_bit()

[Yury Norov]

Kernel lacks for a function that searches for Nth bit in a bitmap.
Usually people do it like this:
        for_each_set_bit(bit, mask, size)
                if (--n == 0)
                        return bit;

Which is not so elegant, and very slow.

This series adds fast routines for this task, and applies them where
appropriate.

While here, move thin wrappers around find_bit() in nodemask.c to a
corresponding header, and because nodemask.c is empty after that,
remove it.

v1: https://lore.kernel.org/lkml/20220706182300.70862-4-yury.norov@gmail.com/T/
v2: - count Nth bit from 0 (was 1);
    - use 'invert' trick in _find_nth_bit(), as in _find_next_bit();
    - cleanup comments;
    - fns() is kept inline - looking at __ffs() generic implementation,
      I decided to keep it untouched.

Yury Norov (5):
  lib: add find_nth(,and,andnot)_bit()
  lib/bitmap: add tests for find_nth_bit()
  lib/bitmap: remove bitmap_ord_to_pos
  cpumask: add cpumask_nth_{,and,andnot}
  lib/nodemask: inline next_node_in() and node_random()

 MAINTAINERS              |  1 -
 include/linux/bitmap.h   |  1 -
 include/linux/bitops.h   | 19 +++++++++
 include/linux/cpumask.h  | 44 +++++++++++++++++++++
 include/linux/find.h     | 83 ++++++++++++++++++++++++++++++++++++++++
 include/linux/nodemask.h | 27 ++++++++++---
 lib/Makefile             |  2 +-
 lib/bitmap.c             | 36 ++---------------
 lib/cpumask.c            | 26 ++++++-------
 lib/find_bit.c           | 20 ++++++++++
 lib/find_bit_benchmark.c | 17 ++++++++
 lib/nodemask.c           | 31 ---------------
 lib/test_bitmap.c        | 36 ++++++++++++++++-
 13 files changed, 254 insertions(+), 89 deletions(-)
 delete mode 100644 lib/nodemask.c

-- 
2.34.1

[PATCH 1/5] lib: add find_nth(,and,andnot)_bit()

[Yury Norov]

Kernel lacks for a function that searches for Nth bit in a bitmap.
Usually people do it like this:
	for_each_set_bit(bit, mask, size)
		if (--n == 0)
			return bit;

We can do it more efficiently, if we:
1. find a word containing Nth bit, using hweight(); and
2. find the bit, using a helper fns(), that works similarly to
   __ffs() and ffz().

fns() is implemented as a simple loop. For x86_64, there's PDEP instruction
to do that: ret = clz(pdep(1 << idx, num)). However, for large bitmaps the
most of improvement comes from using hweight(), so I kept fns() simple.

New find_nth_bit() is ~70 times faster on x86_64/kvm:
find_nth_bit:                  7154190 ns,  16411 iterations
for_each_bit:                505493126 ns,  16315 iterations

With all that, a family of 3 new functions is added, and used where
appropriate in the following patches.

Signed-off-by: Yury Norov <yury.norov@gmail.com>
---
 include/linux/bitops.h | 19 ++++++++++
 include/linux/find.h   | 83 ++++++++++++++++++++++++++++++++++++++++++
 lib/find_bit.c         | 20 ++++++++++
 3 files changed, 122 insertions(+)

diff --git a/include/linux/bitops.h b/include/linux/bitops.h
index cf9bf65039f2..8b2189878afa 100644
--- a/include/linux/bitops.h
+++ b/include/linux/bitops.h
@@ -246,6 +246,25 @@ static inline unsigned long __ffs64(u64 word)
 	return __ffs((unsigned long)word);
 }
 
+/**
+ * fns - find N'th set bit in a word
+ * @word: The word to search
+ * @n: Bit to find
+ */
+static inline unsigned long fns(unsigned long word, unsigned int n)
+{
+	unsigned int bit;
+
+	while (word) {
+		bit = __ffs(word);
+		if (n-- == 0)
+			return bit;
+		__clear_bit(bit, &word);
+	}
+
+	return BITS_PER_LONG;
+}
+
 /**
  * assign_bit - Assign value to a bit in memory
  * @nr: the bit to set
diff --git a/include/linux/find.h b/include/linux/find.h
index 424ef67d4a42..4c7f82dcc38a 100644
--- a/include/linux/find.h
+++ b/include/linux/find.h
@@ -12,6 +12,8 @@ extern unsigned long _find_next_bit(const unsigned long *addr1,
 		const unsigned long *addr2, unsigned long nbits,
 		unsigned long start, unsigned long invert, unsigned long le);
 extern unsigned long _find_first_bit(const unsigned long *addr, unsigned long size);
+unsigned long _find_nth_bit(const unsigned long *addr1, const unsigned long *addr2,
+				unsigned long size, unsigned long n, unsigned long invert);
 extern unsigned long _find_first_and_bit(const unsigned long *addr1,
 					 const unsigned long *addr2, unsigned long size);
 extern unsigned long _find_first_zero_bit(const unsigned long *addr, unsigned long size);
@@ -125,6 +127,87 @@ unsigned long find_first_bit(const unsigned long *addr, unsigned long size)
 }
 #endif
 
+/**
+ * find_nth_bit - find N'th set bit in a memory region
+ * @addr: The 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
+ *
+ * The following is semantically equivalent:
+ *	 idx = find_nth_bit(addr, size, 0);
+ *	 idx = find_first_bit(addr, size);
+ *
+ * Returns the bit number of the N'th set bit.
+ * If no such, returns @size.
+ */
+static inline
+unsigned long find_nth_bit(const unsigned long *addr, unsigned long size, unsigned long n)
+{
+	if (n >= size)
+		return size;
+
+	if (small_const_nbits(size)) {
+		unsigned long val =  *addr & GENMASK(size - 1, 0);
+
+		return val ? fns(val, n) : size;
+	}
+
+	return _find_nth_bit(addr, NULL, size, n, 0UL);
+}
+
+/**
+ * find_nth_and_bit - find N'th set 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 set bit.
+ * If no such, returns @size.
+ */
+static inline
+unsigned long find_nth_and_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_bit(addr1, addr2, size, n, 0UL);
+}
+
+/**
+ * find_nth_andnot_bit - find N'th set bit in 2 memory regions,
+ *			 flipping bits in 2nd region
+ * @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 set bit.
+ * If no such, returns @size.
+ */
+static inline
+unsigned long find_nth_andnot_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_bit(addr1, addr2, size, n, ~0UL);
+}
+
 #ifndef find_first_and_bit
 /**
  * find_first_and_bit - find the first set bit in both memory regions
diff --git a/lib/find_bit.c b/lib/find_bit.c
index 1b8e4b2a9cba..43cb1f781056 100644
--- a/lib/find_bit.c
+++ b/lib/find_bit.c
@@ -89,6 +89,26 @@ unsigned long _find_first_bit(const unsigned long *addr, unsigned long size)
 EXPORT_SYMBOL(_find_first_bit);
 #endif
 
+unsigned long _find_nth_bit(const unsigned long *addr1, const unsigned long *addr2,
+				unsigned long size, unsigned long n, unsigned long invert)
+{
+	unsigned long val, idx, w;
+
+	for (idx = 0; idx * BITS_PER_LONG < size; idx++, n -= w) {
+		val = addr1[idx];
+		if (addr2)
+			val &= addr2[idx] ^ invert;
+
+		w = hweight_long(val);
+		if (w > n)
+			return min(idx * BITS_PER_LONG + fns(val, n), size);
+	}
+
+	return size;
+
+}
+EXPORT_SYMBOL(_find_nth_bit);
+
 #ifndef find_first_and_bit
 /*
  * Find the first set bit in two memory regions.
-- 
2.34.1