From mboxrd@z Thu Jan 1 00:00:00 1970 Received: from mail-yb1-f176.google.com (mail-yb1-f176.google.com [209.85.219.176]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id D88AD1BD9FB for ; Mon, 13 Jan 2025 18:00:58 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.219.176 ARC-Seal:i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1736791261; cv=none; b=bvLeDtbEUedGNlJ8cOrvpG9BajhYGL5j1CKJgOFWmXBPqm/gDuOIsGMfSvrMdbiCYRituQTLuTqfe7jamf29W1MEYxeSEFaqWAvPEbaYgRRqbTPRAv5XLQvzWOFVOt+alZyTs3VPQiEG9B0vuGjjlcX1Thb7DYON2Z1S2WBwO0Y= ARC-Message-Signature:i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1736791261; c=relaxed/simple; bh=IwIiGV1524IionjsBgRlsEbuAQXIrsuExC9g771BFw4=; h=Date:From:To:Cc:Subject:Message-ID:References:MIME-Version: Content-Type:Content-Disposition:In-Reply-To; b=qsc+B4l/4NZRFF6Jif+VyXxMmnP8+7PglzKN2qsF+gnOZY6ZncZy95Y7Z6sA5s0nSfRosN37p63cDuUC3n7MCu+jRyQDMJqEifGWEcBjw66GQjazSKsZpcmub4dUf7NG3uAJLd++ech2Th+3ZUG+NXsXHPDdA9O5+KvrczjOV1A= ARC-Authentication-Results:i=1; smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=gmail.com; spf=pass smtp.mailfrom=gmail.com; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b=GNsgez+B; arc=none smtp.client-ip=209.85.219.176 Authentication-Results: smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=gmail.com Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=gmail.com Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b="GNsgez+B" Received: by mail-yb1-f176.google.com with SMTP id 3f1490d57ef6-e4a6b978283so9129943276.0 for ; Mon, 13 Jan 2025 10:00:58 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1736791258; x=1737396058; darn=vger.kernel.org; h=in-reply-to:content-disposition:mime-version:references:message-id :subject:cc:to:from:date:from:to:cc:subject:date:message-id:reply-to; bh=ouvlJO+pQh2Ha+xZnQTgKzpF8j/jcxIsFHvb/7k5OuA=; b=GNsgez+BIV5MtBMJ221fKa1EY4LBIda3ef1DhO2DQl90TbUpEmthcz2ew2Fkk3Tmuu xqgs4fur/HmSP+4RjMWAP+T0DwLx5gKZKXP7dFV6DUbW1IHZ3Un7Xa5F1OyaaCAgPVxO P1Xw0PX8fd/X3wFYTVRDsRosqEiKzlINf7ey0jOyFb+j69AJxytX3lKwH8oN3DwzQ+hm KrnbSTfAmIXseXOZYnsoZ41tqwIK8MpUdfgiUQfo0NEq0npTqAEmKxfNxSiuph71EKYi RHM69OjaVMpzlRHyatUzOqCnI90eLlp7zLYDO6NCdIFTdtagOuEifdQms33VjfPtddNd YHmw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1736791258; x=1737396058; h=in-reply-to:content-disposition:mime-version:references:message-id :subject:cc:to:from:date:x-gm-message-state:from:to:cc:subject:date :message-id:reply-to; bh=ouvlJO+pQh2Ha+xZnQTgKzpF8j/jcxIsFHvb/7k5OuA=; b=piRXYC8236CDIpMcR0kRpXP79jsJBIASrfOVsQy9c0G7FFObeTBd/pi9DMiXkELUGW whib2XaAuTHIXYKHDISpZImrh+iEssGm3ssL1q9JTROXuN6lpGunkKOUHMozckPnfnnI JdV4EZxdTHfrP/t4Hddi3ZKCpmEz+siBnC6d5Iu4N++DuBZWTGLBgN5cR//Dj6WWEMB5 98NEMueYl/elPJVDvnmAAWQ9Y1KujgxWlikgTAe7a7VrKIIdh9YRKrrpMPgR1RtpoKVy v5eJ9WK3ZrYIUDkKA+jCJwgj2EbgYnrY4AGn/LKznR6oI6uK/3gr6DYBuN+ygRgbGFo/ C3mw== X-Forwarded-Encrypted: i=1; AJvYcCV0IkB/4pmAgNwL4VcUYEVBgW1oO+buEKFZ0CVu1ZbJ99G30JhL2M1UPwlC1F7k4VOExNQdo+rvh2pALJU=@vger.kernel.org X-Gm-Message-State: AOJu0Yz/wXbGXVc59qoY7UWVMoPPMUT4M4l9Zc1rjcC5aFGNW3PRZJjJ uhCbm7vVQfb+bASyT2NIxL0APYFbFM2jTLzdA//JVDwYpRtYJ3AW X-Gm-Gg: ASbGncuEcevAVF+NOQ2wtujvmMSuQDdaG89+NDnTWw4n0XZOeZLiTQxQkrWqCgMQ+0/ 4aA7om9SMQiY7TJ1Exw5+lYPzAuaaW79jKQq5vK+WQcXVi27cn+oeGCC7julBxY+5SjH2n3NNiU 6g3sVuPqzsrGsiE1vJtg6FlFm1ku+fPp+ZtsIlsagxj5NamWe6pFXWDOrt0+yyovgb9hjkpiFjb h+sgDtLjkA5FbxrXEKOsLzY9nm77OOC1Y3vrIg1Md63+19AGFKvvUY= X-Google-Smtp-Source: AGHT+IGk209nWkW+fSUR9cR4QX5Hhw5aPBvUFP1fGoVyCQ6/GvddFRkAEtv1QrHPMxLIg0ZFmZ3j9Q== X-Received: by 2002:a05:690c:ec4:b0:6ee:7916:2fa3 with SMTP id 00721157ae682-6f543e45777mr131671417b3.2.1736791257700; Mon, 13 Jan 2025 10:00:57 -0800 (PST) Received: from localhost ([2601:347:100:5ea0:c05d:9d61:b5c:cc62]) by smtp.gmail.com with ESMTPSA id 00721157ae682-6f546e3416asm18237687b3.112.2025.01.13.10.00.56 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Mon, 13 Jan 2025 10:00:57 -0800 (PST) Date: Mon, 13 Jan 2025 13:00:56 -0500 From: Yury Norov To: Mark Rutland Cc: I Hsin Cheng , 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: 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 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 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 > > > >