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

On Mon, Jul 11, 2022 at 6:51 AM Yury Norov <yury.norov@gmail.com> 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;
>
> 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.

Two observations:
1) your patches are not versioned (hint: use `git format-patch
--thread -vX --cover-letter ...`, where X is a version you want to
give);
2) fns() is not good abbreviation, because among ffs (First) and fls
(Last), fns would be read as Next, which is misleading, I'm not sure
fnths(), which is correct, is good for readers.

-- 
With Best Regards,
Andy Shevchenko

On Mon, Jul 11, 2022 at 1:55 AM Andy Shevchenko
<andy.shevchenko@gmail.com> wrote:
>
> On Mon, Jul 11, 2022 at 6:51 AM Yury Norov <yury.norov@gmail.com> 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;
> >
> > 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.
>
> Two observations:
> 1) your patches are not versioned (hint: use `git format-patch
> --thread -vX --cover-letter ...`, where X is a version you want to
> give);

OK

> 2) fns() is not good abbreviation, because among ffs (First) and fls
> (Last), fns would be read as Next, which is misleading, I'm not sure
> fnths(), which is correct, is good for readers.

I agree that fns() may be confusing, but fnths() is even worse to me.
I expect that it will be mostly used indirectly via find_nth_bit(), and
will not create a lot of confusion for users.

Thanks,
Yury

On Tue, Jul 12, 2022 at 6:26 PM Yury Norov <yury.norov@gmail.com> wrote:
> On Mon, Jul 11, 2022 at 1:55 AM Andy Shevchenko
> <andy.shevchenko@gmail.com> wrote:
> > On Mon, Jul 11, 2022 at 6:51 AM Yury Norov <yury.norov@gmail.com> wrote:

...

> > 2) fns() is not good abbreviation, because among ffs (First) and fls
> > (Last), fns would be read as Next, which is misleading, I'm not sure
> > fnths(), which is correct, is good for readers.
>
> I agree that fns() may be confusing, but fnths() is even worse to me.

I also think it's not the best choice.

> I expect that it will be mostly used indirectly via find_nth_bit(), and
> will not create a lot of confusion for users.

Perhaps in that case we can survive with something else? Naming is hard...

-- 
With Best Regards,
Andy Shevchenko

On Tue, Jul 12, 2022 at 08:28:42PM +0200, Andy Shevchenko wrote:
> On Tue, Jul 12, 2022 at 6:26 PM Yury Norov <yury.norov@gmail.com> wrote:
> > On Mon, Jul 11, 2022 at 1:55 AM Andy Shevchenko
> > <andy.shevchenko@gmail.com> wrote:
> > > On Mon, Jul 11, 2022 at 6:51 AM Yury Norov <yury.norov@gmail.com> wrote:
> 
> ...
> 
> > > 2) fns() is not good abbreviation, because among ffs (First) and fls
> > > (Last), fns would be read as Next, which is misleading, I'm not sure
> > > fnths(), which is correct, is good for readers.
> >
> > I agree that fns() may be confusing, but fnths() is even worse to me.
> 
> I also think it's not the best choice.
> 
> > I expect that it will be mostly used indirectly via find_nth_bit(), and
> > will not create a lot of confusion for users.
> 
> Perhaps in that case we can survive with something else? Naming is hard...

OK, I'll move it to find.h and call __find_nth_bit().

Is this the only issue, or I'd wait for more comments?

Thanks,
Yury

On Tue, Jul 12, 2022 at 06:46:35PM -0700, Yury Norov wrote:
> On Tue, Jul 12, 2022 at 08:28:42PM +0200, Andy Shevchenko wrote:
> > On Tue, Jul 12, 2022 at 6:26 PM Yury Norov <yury.norov@gmail.com> wrote:
> > > On Mon, Jul 11, 2022 at 1:55 AM Andy Shevchenko
> > > <andy.shevchenko@gmail.com> wrote:
> > > > On Mon, Jul 11, 2022 at 6:51 AM Yury Norov <yury.norov@gmail.com> wrote:
> > 
> > ...
> > 
> > > > 2) fns() is not good abbreviation, because among ffs (First) and fls
> > > > (Last), fns would be read as Next, which is misleading, I'm not sure
> > > > fnths(), which is correct, is good for readers.
> > >
> > > I agree that fns() may be confusing, but fnths() is even worse to me.
> > 
> > I also think it's not the best choice.
> > 
> > > I expect that it will be mostly used indirectly via find_nth_bit(), and
> > > will not create a lot of confusion for users.
> > 
> > Perhaps in that case we can survive with something else? Naming is hard...
> 
> OK, I'll move it to find.h and call __find_nth_bit().
> 
> Is this the only issue, or I'd wait for more comments?

I looked again, and I think that the structure of the code requires
to have fns() in bitops.h

Just because we can't think out a good name doesn't mean that we
should break existing structure. Let's keep things as is, and if
one day we'll find a better name - we'll rename it.

Regarding this:

> > > I expect that it will be mostly used indirectly via find_nth_bit()

It's not too important what I expect. For available functionality it's
much easier to find a place to use, and breaking people from doing it 
is silly.
 
> Thanks,
> Yury

If no other comments, except that fns() name, moving it in -next.

On Sun, Jul 10, 2022 at 09:47:06PM -0700, 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;
> 
> 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