[PATCH v3 0/3] bitmap: introduce find_random_bit() and use in clocksource

[PATCH v3 0/3] bitmap: introduce find_random_bit() and use in clocksource

[Yury Norov]

From: Yury Norov [NVIDIA] <yury.norov@gmail.com>

nodemasks implement node_random(), which may also be useful for other
subsystems. Generalize the function, and propagate to cpumask API.

This v3 reverts v2 change that removes inclusion of random.h in
nodemasks header. The nodemasks indeed don't need random.h anymore,
but quite a few units include random.h via nodemask.h indirectly.

Resolving this is out of scope of the series, so I'll do it separately.

v1: https://lore.kernel.org/all/20250604212125.25656-1-yury.norov@gmail.com/
v2: https://lore.kernel.org/all/20250608194536.28130-1-yury.norov@gmail.com/
v3: keep random.h included in linux/nodemasks.h

Yury Norov [NVIDIA] (3):
  bitmap: generalize node_random()
  cpumask: introduce cpumask_random()
  clocksource: Improve randomness in clocksource_verify_choose_cpus()

 include/linux/cpumask.h   | 12 ++++++++++++
 include/linux/find.h      |  2 ++
 include/linux/nodemask.h  | 16 +---------------
 kernel/time/clocksource.c |  5 +----
 lib/find_bit.c            | 24 ++++++++++++++++++++++++
 5 files changed, 40 insertions(+), 19 deletions(-)

-- 
2.43.0

[PATCH v3 1/3] bitmap: generalize node_random()

[Yury Norov]

From: "Yury Norov [NVIDIA]" <yury.norov@gmail.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").

Signed-off-by: Yury Norov [NVIDIA] <yury.norov@gmail.com>
---
 include/linux/find.h     |  2 ++
 include/linux/nodemask.h | 16 +---------------
 lib/find_bit.c           | 24 ++++++++++++++++++++++++
 3 files changed, 27 insertions(+), 15 deletions(-)

diff --git a/include/linux/find.h b/include/linux/find.h
index 5a2c267ea7f9..98c61838002c 100644
--- a/include/linux/find.h
+++ b/include/linux/find.h
@@ -44,6 +44,8 @@ unsigned long _find_next_bit_le(const unsigned long *addr, unsigned
 				long size, unsigned long offset);
 #endif
 
+unsigned long find_random_bit(const unsigned long *addr, unsigned long size);
+
 #ifndef find_next_bit
 /**
  * find_next_bit - find the next set bit in a memory region
diff --git a/include/linux/nodemask.h b/include/linux/nodemask.h
index f08ae71585fa..1cedc7132b76 100644
--- 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;
-		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);
 #else
 	return 0;
 #endif
diff --git a/lib/find_bit.c b/lib/find_bit.c
index 06b6342aa3ae..d4b5a29e3e72 100644
--- a/lib/find_bit.c
+++ b/lib/find_bit.c
@@ -18,6 +18,7 @@
 #include <linux/math.h>
 #include <linux/minmax.h>
 #include <linux/swab.h>
+#include <linux/random.h>
 
 /*
  * Common helper for find_bit() function family
@@ -291,3 +292,26 @@ EXPORT_SYMBOL(_find_next_bit_le);
 #endif
 
 #endif /* __BIG_ENDIAN */
+
+/**
+ * find_random_bit - find a set bit at random position
+ * @addr: The address to base the search on
+ * @size: The bitmap size in bits
+ *
+ * Returns: a position of a random set bit; >= @size otherwise
+ */
+unsigned long find_random_bit(const unsigned long *addr, unsigned long size)
+{
+	int w = bitmap_weight(addr, size);
+
+	switch (w) {
+	case 0:
+		return 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));
+	}
+}
+EXPORT_SYMBOL(find_random_bit);
-- 
2.43.0

[PATCH v3 2/3] cpumask: introduce cpumask_random()

[Yury Norov]

From: "Yury Norov [NVIDIA]" <yury.norov@gmail.com>

Propagate find_random_bit() to cpumask API.

Signed-off-by: Yury Norov [NVIDIA] <yury.norov@gmail.com>
---
 include/linux/cpumask.h | 12 ++++++++++++
 1 file changed, 12 insertions(+)

diff --git a/include/linux/cpumask.h b/include/linux/cpumask.h
index 7ae80a7ca81e..39b71b662da3 100644
--- a/include/linux/cpumask.h
+++ b/include/linux/cpumask.h
@@ -354,6 +354,18 @@ unsigned int cpumask_next_wrap(int n, const struct cpumask *src)
 	return find_next_bit_wrap(cpumask_bits(src), small_cpumask_bits, n + 1);
 }
 
+/**
+ * cpumask_random - get random cpu in *src.
+ * @src: cpumask pointer
+ *
+ * Return: random set bit, or >= nr_cpu_ids if @src is empty.
+ */
+static __always_inline
+unsigned int cpumask_random(const struct cpumask *src)
+{
+	return find_random_bit(cpumask_bits(src), nr_cpu_ids);
+}
+
 /**
  * for_each_cpu - iterate over every cpu in a mask
  * @cpu: the (optionally unsigned) integer iterator
-- 
2.43.0

[PATCH v3 3/3] clocksource: Improve randomness in clocksource_verify_choose_cpus()

[Yury Norov]

From: "Yury Norov [NVIDIA]" <yury.norov@gmail.com>

The current algorithm of picking a random CPU works OK for dense online
cpumask, but if cpumask is non-dense, the distribution of selected CPUs
is skewed.

For example, on 8-CPU board with CPUs 4-7 offlined, the probability of
selecting CPU 0 is 5/8. Accordingly, CPUs 1, 2 and 3 are chosen with
probability 1/8 each. The proper algorithm should pick each online CPU
with probability 1/4.

Switch it to cpumask_random(), which has better statistical
characteristics.

Acked-by: John Stultz <jstultz@google.com>
Signed-off-by: Yury Norov [NVIDIA] <yury.norov@gmail.com>
---
 kernel/time/clocksource.c | 5 +----
 1 file changed, 1 insertion(+), 4 deletions(-)

diff --git a/kernel/time/clocksource.c b/kernel/time/clocksource.c
index 6a8bc7da9062..4b005b2f3ef5 100644
--- a/kernel/time/clocksource.c
+++ b/kernel/time/clocksource.c
@@ -342,10 +342,7 @@ static void clocksource_verify_choose_cpus(void)
 	 * CPUs that are currently online.
 	 */
 	for (i = 1; i < n; i++) {
-		cpu = get_random_u32_below(nr_cpu_ids);
-		cpu = cpumask_next(cpu - 1, cpu_online_mask);
-		if (cpu >= nr_cpu_ids)
-			cpu = cpumask_first(cpu_online_mask);
+		cpu = cpumask_random(cpu_online_mask);
 		if (!WARN_ON_ONCE(cpu >= nr_cpu_ids))
 			cpumask_set_cpu(cpu, &cpus_chosen);
 	}
-- 
2.43.0

Re: [PATCH v3 1/3] bitmap: generalize node_random()

[Andrew Morton]

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

> From: "Yury Norov [NVIDIA]" <yury.norov@gmail.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?

Re: [PATCH v3 1/3] bitmap: generalize node_random()

[Yury Norov]

On Tue, Jun 17, 2025 at 03:50:56PM -0700, Andrew Morton wrote:
> On Tue, 17 Jun 2025 16:08:51 -0400 Yury Norov <yury.norov@gmail.com> wrote:
> 
> > From: "Yury Norov [NVIDIA]" <yury.norov@gmail.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.

...

> 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?

Ahh... Indeed you're right.

Thanks, Andrew, I'll send v4