linux-kernel - Re: [PATCH 02/12] bitmap: add bitmap_weight

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:   Tue, 29 Aug 2023 09:22:52 +0200
From:   Rasmus Villemoes <linux@...musvillemoes.dk>
To:     Yury Norov <yury.norov@...il.com>, linux-kernel@...r.kernel.org
Cc:     Andy Shevchenko <andriy.shevchenko@...ux.intel.com>
Subject: Re: [PATCH 02/12] bitmap: add bitmap_weight_from()

On 28/08/2023 20.43, Yury Norov wrote:
> Add a _from flavor for bitmap_weight(). It's useful when traversing
> bitmaps in a loop to not count bits from the beginning every time.
> 
> The test for bitmap_weight{,_from}() is added as well.
> 
> Signed-off-by: Yury Norov <yury.norov@...il.com>
> ---
>  include/linux/bitmap.h | 14 ++++++++++++++
>  lib/bitmap.c           | 25 +++++++++++++++++++++++++
>  lib/test_bitmap.c      | 18 ++++++++++++++++++
>  3 files changed, 57 insertions(+)
> 
> diff --git a/include/linux/bitmap.h b/include/linux/bitmap.h
> index 692d0a1dbe92..6acbdd2abd0c 100644
> --- a/include/linux/bitmap.h
> +++ b/include/linux/bitmap.h
> @@ -168,6 +168,8 @@ bool __bitmap_subset(const unsigned long *bitmap1,
>  unsigned int __bitmap_weight(const unsigned long *bitmap, unsigned int nbits);
>  unsigned int __bitmap_weight_and(const unsigned long *bitmap1,
>  				 const unsigned long *bitmap2, unsigned int nbits);
> +unsigned int __bitmap_weight_from(const unsigned long *bitmap,
> +					unsigned int bits, unsigned int start);
>  void __bitmap_set(unsigned long *map, unsigned int start, int len);
>  void __bitmap_clear(unsigned long *map, unsigned int start, int len);
>  
> @@ -446,6 +448,18 @@ unsigned long bitmap_weight_and(const unsigned long *src1,
>  	return __bitmap_weight_and(src1, src2, nbits);
>  }
>  
> +static __always_inline
> +unsigned int bitmap_weight_from(const unsigned long *src, unsigned int nbits, unsigned int start)
> +{
> +	if (unlikely(start >= nbits))
> +		return 0;
> +
> +	if (small_const_nbits(nbits - start) && nbits / BITS_PER_LONG == start / BITS_PER_LONG)
> +		return hweight_long(*src & GENMASK(nbits-1, start));

This must be buggy. If I pass compile-time constants nbits==96 and
start==64, the whole if() is true, and we call GENMASK with total
garbage arguments, and access src[0] and not src[1] as that start-value
would suggest.

Don't optimize for irrelevant cases. The expected use of this function
must be that start is some runtime thing. So just make the whole if()
just test whether nbits is small_const, and if so, I think the
hweight_long() line is actually right as-is (though I can never remember
GENMASK argument order).
>  
> +#define BITMAP_WEIGHT_FROM(FETCH, bits, start)					\
> +({										\
> +	unsigned long __bits = (bits), val, idx, w = 0, __start = (start), mask;\
> +										\
> +	mask = BITMAP_FIRST_WORD_MASK(__start);					\
> +	idx = __start / BITS_PER_LONG;						\
> +										\
> +	for (val = (FETCH) & mask; idx < __bits / BITS_PER_LONG; val = (FETCH))	{\
> +		w += hweight_long(val);						\
> +		idx++;								\
> +	}									\
> +										\
> +	if (__bits % BITS_PER_LONG)						\
> +		w += hweight_long((val) & BITMAP_LAST_WORD_MASK(__bits));	\
> +										\
> +	w;									\
> +})
>

Why does the entire function body need to be an unholy statement expression?

Rasmus