linux-kernel - Re: [RFC PATCH] cpumask: Implement "random" version of cpumask_any

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Message-ID: <Z4VU2MfOSq9VJvBN@thinkpad>
Date: Mon, 13 Jan 2025 13:00:56 -0500
From: Yury Norov <yury.norov@...il.com>
To: Mark Rutland <mark.rutland@....com>
Cc: I Hsin Cheng <richard120310@...il.com>, linux@...musvillemoes.dk,
	jserv@...s.ncku.edu.tw, linux-kernel@...r.kernel.org
Subject: Re: [RFC PATCH] cpumask: Implement "random" version of
 cpumask_any_but()

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@...il.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
> > 
> >