linux-kernel - Re: [PATCH 1/2] 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] [day] [month] [year] [list]

Message-ID: <87cy9vuoos.ffs@tglx>
Date: Sun, 20 Jul 2025 12:44:19 +0200
From: Thomas Gleixner <tglx@...utronix.de>
To: Yury Norov <yury.norov@...il.com>, Ingo Molnar <mingo@...hat.com>,
 Borislav Petkov <bp@...en8.de>, Dave Hansen <dave.hansen@...ux.intel.com>,
 "H. Peter Anvin" <hpa@...or.com>, Rasmus Villemoes
 <linux@...musvillemoes.dk>, Andrew Morton <akpm@...ux-foundation.org>,
 "Peter Zijlstra (Intel)" <peterz@...radead.org>, Ilpo Järvinen
 <ilpo.jarvinen@...ux.intel.com>, Fernando Fernandez Mancera
 <ffmancera@...eup.net>, "Xin Li (Intel)" <xin@...or.com>, x86@...nel.org,
 linux-kernel@...r.kernel.org
Cc: Yury Norov <yury.norov@...il.com>
Subject: Re: [PATCH 1/2] bitmap: add bitmap_weight_from()

On Sat, Jul 19 2025 at 21:41, Yury Norov wrote:
>  
> +#define BITMAP_WEIGHT_FROM(FETCH, start, bits)				\
> +({										\
> +	unsigned long __start = (start), __bits = (bits);			\
> +	unsigned int idx, w = 0;						\
> +										\
> +	if (unlikely(__start >= bits))						\
> +		goto out;							\
> +										\
> +	idx = __start / BITS_PER_LONG;						\
> +	w = (FETCH) & BITMAP_FIRST_WORD_MASK(__start);				\

So this expands to

        w = bitmap[idx] & (~0UL << ((start) & (BITS_PER_LONG - 1)));

Which means @w contains the content of the first bitmap word except for
the masked off bits. Let's assume @start is 0 and @bits is 32. Therefore
@idx is 0.

Assume further bitmap[idx] is all ones, which means 64bits set on a
64bit system. That results in

      w = bitmap[0] & (~0UL << ((0) & (BITS_PER_LONG - 1)));
-->   w = 0xFFFFFFFFFFFFFFFF & (0xFFFFFFFFFFFFFFFF << (0 & 0x3F));
-->   w = 0xFFFFFFFFFFFFFFFF;

which is obviously bogus.

> +	for (++idx; idx < __bits / BITS_PER_LONG; idx++)			\
> +		w += hweight_long(FETCH);					\

Evaluates to false

> +	if (__bits % BITS_PER_LONG)						\

Evaluates to true.

> +		w += hweight_long((FETCH) & BITMAP_LAST_WORD_MASK(__bits));	\

So this is executed and evaluates to:

      w += hweight_long(bitmap[1] & (~0UL >> (-(32UL) & (BITS_PER_LONG - 1))));

Let's assume the second word contains all ones as well.

-->   w += hweight_long(0xFFFFFFFFFFFFFFFF & (0xFFFFFFFFFFFFFFFF >> (0xFFFFFFFFFFFFFFE0 & 0x3F)));
-->   w += hweight_long(0xFFFFFFFFFFFFFFFF & (0xFFFFFFFFFFFFFFFF >> (0x20)));
-->   w += hweight_long(0xFFFFFFFFFFFFFFFF & 0xFFFFFFFF);

-->   w += 32;

Due to the wraparound of the addition it results in

      w = 31

which is not making the bogosity above more correct. And no, you can't
just fix up the initial assignment to @w:

	w = hweight_long((FETCH) & BITMAP_FIRST_WORD_MASK(__start);

because then the result is 32 + 32 == 64 as the final clause is
unconditionally executed.

Something like this should work:

        unsigned int idx, maxidx, w = 0;

	idx = start / BITS_PER_LONG;
	w = hweight_long((FETCH) & BITMAP_FIRST_WORD_MASK((unsigned long)start));

        maxidx = bits / BITS_PER_LONG;
        for (idx++; idx < maxidx; idx++)
        	w += hweight_long((FETCH));

        if (maxidx * BITS_PER_LONG < bits)
        	w += hweight_long((FETCH) & BITMAP_LAST_WORD_MASK((unsigned long)bits));

No?

Thanks,

        tglx