Re: [RFC PATCH] cpumask: Implement "random" version of cpumask_any_but()

[Mark Rutland <mark.rutland@arm.com>]

On Mon, Jan 13, 2025 at 02:18:39PM +0800, I Hsin Cheng wrote:
> Original implementation of "cpumask_any_but()" isn't actually random as
> the comment claims itself to be. It's behavior is in fact to select the
> first cpu in "mask" which isn't equal to "cpu".

What it says specifically is:

  cpumask_any_but - return a "random" in a cpumask, but not this one.

... and by "random", it really means "arbitrary".

The idea here is that the caller is specifying that it doesn't care
which specific CPU is chosen, but this is not required to be a random
selection.

> Re-implement the function so we can choose a random cpu by randomly
> select the value of "n" and choose the nth cpu in "mask"
> 
> Experiments[1] are done below to verify it generate more random result than
> orginal implementation which tends to select the same cpu over and over
> again.

I think what you're after here is similar to
cpumask_any_and_distribute(), and you should look at building
cpumask_any_but_distribute() in the same way, rather than changing
cpumask_any_but().

Mark.

> Signed-off-by: I Hsin Cheng <richard120310@gmail.com>
> ---
> The test is done on x86_64 architecture with 6.8.0-48-generic kernel
> version on Intel(R) Core(TM) i7-2600 CPU @ 3.40GHz
> 
> [1]:
> Test script:
> 
> int init_module(void)
> {
>     const struct cpumask *cur_mask = cpu_online_mask;
>     unsigned int cpu = 5, result;
>     int times = 50;
> 
>     pr_info("Old cpumask_any_but(): ");
>     for (int i = 0; i < times; i++) {
>         result = cpumask_any_but(cur_mask, cpu);
>         pr_cont("%u ", result);
>     }
>     pr_info("\n");
> 
>     pr_info("New cpumask_any_but(): ");
>     for (int i = 0; i < times; i++) {
>         result = cpumask_any_but_v2(cur_mask, cpu);
>         pr_cont("%u ", result);
>     }
>     pr_info("\n");
> 
>     return 0;
> }
> 
> Experiment result showned as below display in dmesg:
> [ 8036.558152] Old cpumask_any_but(): 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
> 
> [ 8036.558193] New cpumask_any_but(): 7 1 1 2 2 2 3 4 0 2 7 4 6 3 3 2 2 4 2 7 6 6 6 4 6 6 6 4 4 7 6 2 2 6 7 6 6 3 0 6 2 1 0 4 4 6 4 6 6 3
> ---
>  include/linux/cpumask.h | 14 ++++++++++----
>  1 file changed, 10 insertions(+), 4 deletions(-)
> 
> diff --git a/include/linux/cpumask.h b/include/linux/cpumask.h
> index 9278a50d5..336297960 100644
> --- a/include/linux/cpumask.h
> +++ b/include/linux/cpumask.h
> @@ -401,12 +401,18 @@ unsigned int __pure cpumask_next_wrap(int n, const struct cpumask *mask, int sta
>  static __always_inline
>  unsigned int cpumask_any_but(const struct cpumask *mask, unsigned int cpu)
>  {
> -	unsigned int i;
> +	unsigned int i, n, weight;
>  
>  	cpumask_check(cpu);
> -	for_each_cpu(i, mask)
> -		if (i != cpu)
> -			break;
> +	weight = cpumask_weight(mask);
> +	n = get_random_u32() % weight;
> +
> +	/* If we accidentally pick "n" equal to "cpu",
> +	 * then simply choose "n + 1"th cpu.
> +	 */
> +	if (n == cpu)
> +		n = (n + 1) % weight;
> +	i = cpumask_nth(n, mask);
>  	return i;
>  }
>  
> -- 
> 2.43.0
> 
>