linux-kernel - Re: [PATCH v3 1/3] bitmap: generalize node

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]

Message-Id: <20250617155056.5c1d292d8831e7c7a27c8e5f@linux-foundation.org>
Date: Tue, 17 Jun 2025 15:50:56 -0700
From: Andrew Morton <akpm@...ux-foundation.org>
To: Yury Norov <yury.norov@...il.com>
Cc: linux-kernel@...r.kernel.org, Rasmus Villemoes
 <linux@...musvillemoes.dk>, John Stultz <jstultz@...gle.com>, Thomas
 Gleixner <tglx@...utronix.de>, Stephen Boyd <sboyd@...nel.org>
Subject: Re: [PATCH v3 1/3] bitmap: generalize node_random()

On Tue, 17 Jun 2025 16:08:51 -0400 Yury Norov <yury.norov@...il.com> wrote:

> From: "Yury Norov [NVIDIA]" <yury.norov@...il.com>
> 
> Generalize node_random() and make it available to general bitmaps and
> cpumasks users.
> 
> Notice, find_first_bit() is generally faster than find_nth_bit(), and we
> employ it when there's a single set bit in the bitmap.
> 
> See commit 3e061d924fe9c7b4 ("lib/nodemask: optimize node_random for
> nodemask with single NUMA node").
> 
> ...
>
> --- a/include/linux/nodemask.h
> +++ b/include/linux/nodemask.h
> @@ -492,21 +492,7 @@ static __always_inline int num_node_state(enum node_states state)
>  static __always_inline int node_random(const nodemask_t *maskp)
>  {
>  #if defined(CONFIG_NUMA) && (MAX_NUMNODES > 1)
> -	int w, bit;
> -
> -	w = nodes_weight(*maskp);
> -	switch (w) {
> -	case 0:
> -		bit = NUMA_NO_NODE;

If the mask has no bits set, return -1.

> -		break;
> -	case 1:
> -		bit = first_node(*maskp);
> -		break;
> -	default:
> -		bit = find_nth_bit(maskp->bits, MAX_NUMNODES, get_random_u32_below(w));
> -		break;
> -	}
> -	return bit;
> +	return find_random_bit(maskp->bits, MAX_NUMNODES);
>
> ...
>
> +unsigned long find_random_bit(const unsigned long *addr, unsigned long size)
> +{
> +	int w = bitmap_weight(addr, size);
> +
> +	switch (w) {
> +	case 0:
> +		return size;

If the mask has no bits set, return the mask's size.

> +	case 1:
> +		/* Performance trick for single-bit bitmaps */
> +		return find_first_bit(addr, size);
> +	default:
> +		return find_nth_bit(addr, size, get_random_u32_below(w));
> +	}
> +}

I'm not seeing how this is correct?