From mboxrd@z Thu Jan 1 00:00:00 1970 Received: from foss.arm.com (foss.arm.com [217.140.110.172]) by smtp.subspace.kernel.org (Postfix) with ESMTP id 0336A22F154 for ; Mon, 13 Jan 2025 11:05:30 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=217.140.110.172 ARC-Seal:i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1736766333; cv=none; b=AAbR5uOiXHH7BzijOUQTMOhwEC9G+c2k/GTJhDeNpezmGZkZx8mAotjgV/PsjkoHhK7j9HxemsmsT/3dwAYiPuE9rwHw9h1tsFmS+l09sufPEhr7MMlmfjepU5Cp/3vtX1YK+c2J4QOR9ynTbj6ZCS/Xd5hRdY5Hw125nzwegU4= ARC-Message-Signature:i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1736766333; c=relaxed/simple; bh=cyOUzc37b6++eE1kxVY9bQcMpiLdFj8AtQdUUf5PoRM=; h=Date:From:To:Cc:Subject:Message-ID:References:MIME-Version: Content-Type:Content-Disposition:In-Reply-To; b=axdzyzwX3V0JHhUjzrf3ZrjrKWge8mofVSobQLADb+JJVpqkqS2wsb6txpq/xABdj3v0ILdvJUd+lhrCUK4N5nlvLN5237IFvEGp4AxgQ1x1QBluP9ueK8tjYm87q6Sf4en3nyHAVFTQjhQsGxNro++lnRjw6PPmquG9qG5Ai3M= ARC-Authentication-Results:i=1; smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=arm.com; spf=pass smtp.mailfrom=arm.com; arc=none smtp.client-ip=217.140.110.172 Authentication-Results: smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=arm.com Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=arm.com Received: from usa-sjc-imap-foss1.foss.arm.com (unknown [10.121.207.14]) by usa-sjc-mx-foss1.foss.arm.com (Postfix) with ESMTP id 744FE1424; Mon, 13 Jan 2025 03:05:58 -0800 (PST) Received: from J2N7QTR9R3 (usa-sjc-imap-foss1.foss.arm.com [10.121.207.14]) by usa-sjc-imap-foss1.foss.arm.com (Postfix) with ESMTPSA id 11B4B3F66E; Mon, 13 Jan 2025 03:05:28 -0800 (PST) Date: Mon, 13 Jan 2025 11:05:19 +0000 From: Mark Rutland To: I Hsin Cheng Cc: yury.norov@gmail.com, linux@rasmusvillemoes.dk, jserv@ccns.ncku.edu.tw, linux-kernel@vger.kernel.org Subject: Re: [RFC PATCH] cpumask: Implement "random" version of cpumask_any_but() Message-ID: References: <20250113061839.22131-1-richard120310@gmail.com> Precedence: bulk X-Mailing-List: linux-kernel@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: <20250113061839.22131-1-richard120310@gmail.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 > --- > 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 > >