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

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

[Yury Norov]

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

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: https://lore.kernel.org/all/20250617200854.60753-1-yury.norov@gmail.com/
v4: return NUMA_NO_NODES instead of MAX_NUMNODES in node_random() (Andrew)

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  | 18 +++---------------
 kernel/time/clocksource.c |  5 +----
 lib/find_bit.c            | 24 ++++++++++++++++++++++++
 5 files changed, 42 insertions(+), 19 deletions(-)

-- 
2.43.0

[PATCH v4 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 | 18 +++---------------
 lib/find_bit.c           | 24 ++++++++++++++++++++++++
 3 files changed, 29 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 81586d24d248..325e1dd3540b 100644
--- a/include/linux/nodemask.h
+++ b/include/linux/nodemask.h
@@ -488,21 +488,9 @@ 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;
+	int node = find_random_bit(maskp->bits, MAX_NUMNODES);
+
+	return node < MAX_NUMNODES ? node : NUMA_NO_NODE;
 #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 v4 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 v4 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 picked 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 v4 0/3] bitmap: introduce find_random_bit() and use in clocksource

[Thomas Gleixner]

On Thu, Jun 19 2025 at 14:26, Yury Norov wrote:
> nodemasks implement node_random(), which may also be useful for other
> subsystems. Generalize the function, and propagate to cpumask API.
>
> 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: https://lore.kernel.org/all/20250617200854.60753-1-yury.norov@gmail.com/
> v4: return NUMA_NO_NODES instead of MAX_NUMNODES in node_random() (Andrew)
>
> Yury Norov [NVIDIA] (3):
>   bitmap: generalize node_random()
>   cpumask: introduce cpumask_random()
>   clocksource: Improve randomness in clocksource_verify_choose_cpus()

Assuming this goes through the bitmap tree, for the clocksource change:

Reviewed-by: Thomas Gleixner <tglx@linutronix.de>

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

[Yury Norov]

On Fri, Jun 20, 2025 at 11:37:07PM +0200, Thomas Gleixner wrote:
> On Thu, Jun 19 2025 at 14:26, Yury Norov wrote:
> > nodemasks implement node_random(), which may also be useful for other
> > subsystems. Generalize the function, and propagate to cpumask API.
> >
> > 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: https://lore.kernel.org/all/20250617200854.60753-1-yury.norov@gmail.com/
> > v4: return NUMA_NO_NODES instead of MAX_NUMNODES in node_random() (Andrew)
> >
> > Yury Norov [NVIDIA] (3):
> >   bitmap: generalize node_random()
> >   cpumask: introduce cpumask_random()
> >   clocksource: Improve randomness in clocksource_verify_choose_cpus()
> 
> Assuming this goes through the bitmap tree, for the clocksource change:
> 
> Reviewed-by: Thomas Gleixner <tglx@linutronix.de>

Thanks, applying in bitmap-for-next for testing.