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