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

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives
Hash Suite: Windows password security audit tool. GUI, reports in PDF.
[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]
Date:   Thu, 7 Jul 2022 14:03:45 -0700
From:   Yury Norov <yury.norov@...il.com>
To:     Rasmus Villemoes <linux@...musvillemoes.dk>
Cc:     linux-kernel@...r.kernel.org,
        Alexander Lobakin <alexandr.lobakin@...el.com>,
        Andy Shevchenko <andriy.shevchenko@...ux.intel.com>,
        Arnd Bergmann <arnd@...db.de>, David Gow <davidgow@...gle.com>,
        Eric Dumazet <edumazet@...gle.com>,
        Isabella Basso <isabbasso@...eup.net>,
        Kees Cook <keescook@...omium.org>,
        Keith Busch <kbusch@...nel.org>,
        Kumar Kartikeya Dwivedi <memxor@...il.com>,
        Marco Elver <elver@...gle.com>,
        Mark Rutland <mark.rutland@....com>,
        Steven Rostedt <rostedt@...dmis.org>,
        Toke Høiland-Jørgensen <toke@...hat.com>
Subject: Re: [PATCH 1/5] lib: add find_nth(,and,andnot)_bit()

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@...il.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