linux-kernel - [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-next>] [day] [month] [year] [list]

Message-ID: <20250113061839.22131-1-richard120310@gmail.com>
Date: Mon, 13 Jan 2025 14:18:39 +0800
From: I Hsin Cheng <richard120310@...il.com>
To: yury.norov@...il.com
Cc: linux@...musvillemoes.dk,
	jserv@...s.ncku.edu.tw,
	linux-kernel@...r.kernel.org,
	I Hsin Cheng <richard120310@...il.com>
Subject: [RFC PATCH] cpumask: Implement "random" version of cpumask_any_but()

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