linux-kernel - Re: [PATCH] bitmap: optimize bitmap

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:   Fri, 18 Aug 2023 19:03:44 -0700
From:   Yury Norov <yury.norov@...il.com>
To:     Andy Shevchenko <andriy.shevchenko@...ux.intel.com>
Cc:     linux-kernel@...r.kernel.org,
        Rasmus Villemoes <linux@...musvillemoes.dk>
Subject: Re: [PATCH] bitmap: optimize bitmap_remap()

On Thu, Aug 17, 2023 at 06:37:01PM +0300, Andy Shevchenko wrote:
> On Thu, Aug 17, 2023 at 07:21:59AM -0700, Yury Norov wrote:
> > On Thu, Aug 17, 2023 at 12:38:28PM +0300, Andy Shevchenko wrote:
> > > On Thu, Aug 17, 2023 at 12:37:05PM +0300, Andy Shevchenko wrote:
> > > > On Tue, Aug 15, 2023 at 04:59:34PM -0700, Yury Norov wrote:
> 
> ...
> 
> > > > >  		int n = bitmap_pos_to_ord(old, oldbit, nbits);
> > > > >  
> > > > > +		bit = (n < 0) ? oldbit :	/* identity map */
> > > > 
> > > > Can't you also optimize this case?
> > > > 
> > > > Something like
> > > > 
> > > >   bitmap_xor(tmp, old, new) // maybe even better approach, dunno
> > > 
> > > >   bitmap_empty(tmp) // can be replaced by find first bit
> > > 
> > > Or reuse bitmap_weight()...
> > 
> > That way it wouldn't work,
> 
> Why not? AFAIU there are two cases when we may copy:
> 1) the new mapping is empty;
> 2) the old == new.
> 
> The other cases we need to remap.
> 
> The case 2) is easy with xor and weight.
> 
> diff --git a/lib/bitmap.c b/lib/bitmap.c
> index 24284caadbcc..917eea5219ac 100644
> --- a/lib/bitmap.c
> +++ b/lib/bitmap.c
> @@ -958,7 +958,7 @@ EXPORT_SYMBOL(bitmap_parse);
>   * gets mapped to (returns) @ord value 3 in this example, that means
>   * that bit 7 is the 3rd (starting with 0th) set bit in @buf.
>   *
> - * The bit positions 0 through @bits are valid positions in @buf.
> + * The bit positions 0 through @nbits are valid positions in @buf.
>   */
>  static int bitmap_pos_to_ord(const unsigned long *buf, unsigned int pos, unsigned int nbits)
>  {
> @@ -1008,17 +1008,30 @@ void bitmap_remap(unsigned long *dst, const unsigned long *src,
>  
>  	if (dst == src)		/* following doesn't handle inplace remaps */
>  		return;
> -	bitmap_zero(dst, nbits);
> +
> +	bitmap_xor(dst, old, new, nbits);
> +	if (bitmap_empty(dst, nbits))
> +		goto identity_map;

Now you see? The complexity of this test is 2*O(N). Assuming that people
know better than us when they can optimize their trivial cases with just
copying, this will slow those conscientious users because for them, of
course, old == new is highly unlikely.

Of course, we can do 'if (bitmap_equal(old, new, nbits))', but it's
still O(N), and the above is applicable just as well.
  
>  	w = bitmap_weight(new, nbits);
> +	if (w == 0)
> +		goto identity_map;

In contrast, this test is O(1), because we need the weight of new
bitmap anyways.

> +
> +	bitmap_zero(dst, nbits);
> +
>  	for_each_set_bit(oldbit, src, nbits) {
>  		int n = bitmap_pos_to_ord(old, oldbit, nbits);
>  
> -		if (n < 0 || w == 0)
> +		if (n < 0)
>  			set_bit(oldbit, dst);	/* identity map */
>  		else
>  			set_bit(find_nth_bit(new, nbits, n % w), dst);
>  	}
> +
> +	return;
> +
> +identity_map:
> +	bitmap_copy(dst, src, nbits);
>  }
>  EXPORT_SYMBOL(bitmap_remap);
> 
> But this gives +89 bytes on x86_64... :-(

Who cares if it gives a boost of performance for regular users?

> Inside the loop we can also break when n gets equal to w, but it seems
> a special case (we don't need bitmap_weight_from() for that, do we?).

No, we can't. Instead, we should wrap around 0, exactly what the existing
code does. See the comment:

  * Let @old and @new define a mapping of bit positions, such that
  * whatever position is held by the n-th set bit in @old is mapped
  * to the n-th set bit in @new.  In the more general case, allowing
  * for the possibility that the weight 'w' of @new is less than the
  * weight of @old, map the position of the n-th set bit in @old to
  * the position of the m-th set bit in @new, where m == n % w.

This is written 18 years ago, and it seems it needs to get illustrated.
I didn't find anything else describing bitmap_remap() for more except
my own comment in a random discussion more than a year ago:

https://lkml.org/lkml/2022/6/13/3126

Thanks,
Yury