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

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

[I Hsin Cheng]

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".

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.

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

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

[Kuan-Wei Chiu]

Hi I Hsin,

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".
> 
> 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"
> 
This patch may slow down the efficiency of cpumask_any_but(). Are there
any in-tree users of cpumask_any_but() that require it to return a
truly random id, or benefit from such behavior?

Regards,
Kuan-Wei

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

[I Hsin Cheng]

On Mon, Jan 13, 2025 at 06:13:07PM +0800, Kuan-Wei Chiu wrote:
> Hi I Hsin,
> 
> 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".
> > 
> > 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"
> > 
> This patch may slow down the efficiency of cpumask_any_but(). Are there
> any in-tree users of cpumask_any_but() that require it to return a
> truly random id, or benefit from such behavior?

Hi Kuan-Wei,

Thanks for your review ! Yes indeed it may slow down the efficiency
abit.

However there are some use cases I think randomness is important
such as "dl_task_offline_migration()" under kernel/sched/deadline.c ,
where the operation of cpu picking shouldn't favor certain cpu too much.

Also "select_task_rq()" utitlize "cpumask_any()" to pick cpu, it doesn't
need to be perfectly random, but neither should it only favor certain
cpu.

What do you think?

Best regards,
I Hsin

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

[Kuan-Wei Chiu]

On Mon, Jan 13, 2025 at 06:27:26PM +0800, I Hsin Cheng wrote:
> On Mon, Jan 13, 2025 at 06:13:07PM +0800, Kuan-Wei Chiu wrote:
> > Hi I Hsin,
> > 
> > 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".
> > > 
> > > 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"
> > > 
> > This patch may slow down the efficiency of cpumask_any_but(). Are there
> > any in-tree users of cpumask_any_but() that require it to return a
> > truly random id, or benefit from such behavior?
> 
> Hi Kuan-Wei,
> 
> Thanks for your review ! Yes indeed it may slow down the efficiency
> abit.
> 
> However there are some use cases I think randomness is important
> such as "dl_task_offline_migration()" under kernel/sched/deadline.c ,
> where the operation of cpu picking shouldn't favor certain cpu too much.
> 
> Also "select_task_rq()" utitlize "cpumask_any()" to pick cpu, it doesn't
> need to be perfectly random, but neither should it only favor certain
> cpu.
> 
> What do you think?
>

If a true random number isn't needed, could next_pseudo_random32() be
used instead for better efficiency?

I'm not familiar with the scheduler, but if there are only one or two
scheduler use cases, would you consider creating a new
cpumask_random_but() API and converting those specific cases to use it?
In this case, the patch should also be CC'd to scheduler developers.
Additionally, you should explain the benefits of this approach in the
patch description.

Regards,
Kuan-Wei

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

[Mark Rutland]

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

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

[Yury Norov]

On Mon, Jan 13, 2025 at 11:05:19AM +0000, Mark Rutland wrote:
> 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.

I agree with Mark. cpumask_any_but_distribute() is what you most
likely need. Anyways, whatever you end up please don't change existing
API, especially in a way that hurts performance so badly.

> 
> > Signed-off-by: I Hsin Cheng <richard120310@gmail.com>

This patch should go with a demonstration that some particular
system(s) benefits from it, and the others don't suffer.

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

 #include <linux/random.h>

Which would be really good to avoid.

> > @@ -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);

This is an entirely broken thing, and it works only because your CPU mask
is dense. Imagine cpumask: 0111 1111. Your new cpumask_any_but(mask, 5)
will return 5 exactly, if the get_random_u32() draws 4.

It looks broken even for a dense mask. By probability, your code returns:

P(0-4,7) == 1/8,
P(5) == 0,
P(6) == 1/4.

Assuming you are trying to implement a random uniform distribution drawing,
the correct probabilities should look like:

P(0-4,6-7) == 1/7,
P(5) == 0,

Thanks,
Yury

> >  	return i;
> >  }
> >  
> > -- 
> > 2.43.0
> > 
> > 

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

[I Hsin Cheng]

On Mon, Jan 13, 2025 at 01:00:56PM -0500, Yury Norov wrote:
> On Mon, Jan 13, 2025 at 11:05:19AM +0000, Mark Rutland wrote:
> > 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.
> 
> I agree with Mark. cpumask_any_but_distribute() is what you most
> likely need. Anyways, whatever you end up please don't change existing
> API, especially in a way that hurts performance so badly.

I see, I didn't noticed cpumask_any*_distribute() APIs, they're the
thing I was looking for, thanks!
> 
> > 
> > > Signed-off-by: I Hsin Cheng <richard120310@gmail.com>
> 
> This patch should go with a demonstration that some particular
> system(s) benefits from it, and the others don't suffer.

Thanks for the head up, I'll be aware of this in the future.

> 
> > > ---
> > > 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
> 
>  #include <linux/random.h>
> 
> Which would be really good to avoid.
> 
> > > @@ -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);
> 
> This is an entirely broken thing, and it works only because your CPU mask
> is dense. Imagine cpumask: 0111 1111. Your new cpumask_any_but(mask, 5)
> will return 5 exactly, if the get_random_u32() draws 4.
> 

Oh I'm sorry for this part, "cpumask_nth()" return value should be
checked instead of checking "get_random_u32()". May I ask why does it
only work for dense cpumask? I mean clearly original method will be
faster when cpumask isn't dense.

> It looks broken even for a dense mask. By probability, your code returns:
> 
> P(0-4,7) == 1/8,
> P(5) == 0,
> P(6) == 1/4.
> 
> Assuming you are trying to implement a random uniform distribution drawing,
> the correct probabilities should look like:
> 
> P(0-4,6-7) == 1/7,
> P(5) == 0,
> 
> Thanks,
> Yury
> 

I did noticed this part, I was thinking that we do not actually need to
make the prbability to be uniform distribution, just want to make it
scatters more then picking certain number.

Thanks for your detailed review and explanation, also thanks to Mark and
Kuan-Wei !

I now realize "random" here is more of a convention for the caller to
states that it doesn't matter which cpu it gets, maybe we should
rephrase the comment to make it less confusing? Because I think "random"
itself does stands for a particular meaning.

Best regards,
Richard Cheng.

> > >  	return i;
> > >  }
> > >  
> > > -- 
> > > 2.43.0
> > > 
> > > 

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

[Mark Rutland]

On Tue, Jan 14, 2025 at 03:15:43PM +0800, I Hsin Cheng wrote:
> On Mon, Jan 13, 2025 at 01:00:56PM -0500, Yury Norov wrote:
> > On Mon, Jan 13, 2025 at 11:05:19AM +0000, Mark Rutland wrote:
> > > 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.

> I now realize "random" here is more of a convention for the caller to
> states that it doesn't matter which cpu it gets, maybe we should
> rephrase the comment to make it less confusing? Because I think "random"
> itself does stands for a particular meaning.

FWIW, I agree. I reckon (as above), we could replace "random" with
arbitrary, i.e. replace

	return a "random" cpu in a cpumask ...
	
... with:

	return an arbitrary cpu in a cpumask ...

Looking again I see that the comment for cpumask_any_but() misses the
word "cpu" too, so it'd be nice to clean that up regardless.

Mark.

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

[Yury Norov]

> > > > @@ -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);
> > 
> > This is an entirely broken thing, and it works only because your CPU mask
> > is dense. Imagine cpumask: 0111 1111. Your new cpumask_any_but(mask, 5)
> > will return 5 exactly, if the get_random_u32() draws 4.
> > 
> 
> Oh I'm sorry for this part, "cpumask_nth()" return value should be
> checked instead of checking "get_random_u32()". May I ask why does it
> only work for dense cpumask?

Because for dense mask cpumask_nth(n) == n, and your
 	n = get_random_u32() % weight
is the same as 
 	n = cpumask_nth(get_random_u32() % weight)

> I mean clearly original method will be
> faster when cpumask isn't dense.
> 
> > It looks broken even for a dense mask. By probability, your code returns:
> > 
> > P(0-4,7) == 1/8,
> > P(5) == 0,
> > P(6) == 1/4.
> > 
> > Assuming you are trying to implement a random uniform distribution drawing,
> > the correct probabilities should look like:
> > 
> > P(0-4,6-7) == 1/7,
> > P(5) == 0,
> > 
> > Thanks,
> > Yury
> > 
> 
> I did noticed this part, I was thinking that we do not actually need to
> make the prbability to be uniform distribution, just want to make it
> scatters more then picking certain number.

On cpumask level you can't speculate whether users need true randomness
or not. That's why we pay so much attention to proper function naming.

See: 
 - cpumask_any() - 'any' requirement is much simpler than random;
 - cpumask_any_distribute() - not random at all, just a better (good
   enough) approximation;
 - cpumask_random() - a true random drawing. Must pass Chi^2, 
   Kolmogorov-Smirnov and other fancy statistical tests. As you can see,
   doesn't exist.

If in your function you use expensive true-random get_random_u32(),
one can expect that the output will not be worse than the original
uniform distribution, by the statistical properties means.

> Thanks for your detailed review and explanation, also thanks to Mark and
> Kuan-Wei !
> 
> I now realize "random" here is more of a convention for the caller to
> states that it doesn't matter which cpu it gets, maybe we should
> rephrase the comment to make it less confusing? Because I think "random"
> itself does stands for a particular meaning.

Feel free to send a patch.

Thanks,
Yury

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

[I Hsin Cheng]

On Tue, Jan 14, 2025 at 10:43:56AM -0500, Yury Norov wrote:
> > > > > @@ -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);
> > > 
> > > This is an entirely broken thing, and it works only because your CPU mask
> > > is dense. Imagine cpumask: 0111 1111. Your new cpumask_any_but(mask, 5)
> > > will return 5 exactly, if the get_random_u32() draws 4.
> > > 
> > 
> > Oh I'm sorry for this part, "cpumask_nth()" return value should be
> > checked instead of checking "get_random_u32()". May I ask why does it
> > only work for dense cpumask?
> 
> Because for dense mask cpumask_nth(n) == n, and your
>  	n = get_random_u32() % weight
> is the same as 
>  	n = cpumask_nth(get_random_u32() % weight)
> 
> > I mean clearly original method will be
> > faster when cpumask isn't dense.
> > 
> > > It looks broken even for a dense mask. By probability, your code returns:
> > > 
> > > P(0-4,7) == 1/8,
> > > P(5) == 0,
> > > P(6) == 1/4.
> > > 
> > > Assuming you are trying to implement a random uniform distribution drawing,
> > > the correct probabilities should look like:
> > > 
> > > P(0-4,6-7) == 1/7,
> > > P(5) == 0,
> > > 
> > > Thanks,
> > > Yury
> > > 
> > 
> > I did noticed this part, I was thinking that we do not actually need to
> > make the prbability to be uniform distribution, just want to make it
> > scatters more then picking certain number.
> 
> On cpumask level you can't speculate whether users need true randomness
> or not. That's why we pay so much attention to proper function naming.
> 
> See: 
>  - cpumask_any() - 'any' requirement is much simpler than random;
>  - cpumask_any_distribute() - not random at all, just a better (good
>    enough) approximation;
>  - cpumask_random() - a true random drawing. Must pass Chi^2, 
>    Kolmogorov-Smirnov and other fancy statistical tests. As you can see,
>    doesn't exist.
> 
> If in your function you use expensive true-random get_random_u32(),
> one can expect that the output will not be worse than the original
> uniform distribution, by the statistical properties means.
>

I see, thanks for the explanation, it really helps me learn alot!

> > Thanks for your detailed review and explanation, also thanks to Mark and
> > Kuan-Wei !
> > 
> > I now realize "random" here is more of a convention for the caller to
> > states that it doesn't matter which cpu it gets, maybe we should
> > rephrase the comment to make it less confusing? Because I think "random"
> > itself does stands for a particular meaning.
> 
> Feel free to send a patch.

No problem, I'll send it ASAP.

Regards,
I Hsin Cheng.