From mboxrd@z Thu Jan 1 00:00:00 1970 Received: from mx0a-001b2d01.pphosted.com (mx0a-001b2d01.pphosted.com [148.163.156.1]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id 0F2BD15B971 for ; Fri, 27 Mar 2026 13:39:08 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=148.163.156.1 ARC-Seal:i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1774618750; cv=none; b=C4Yai7Kc8wp3BUffgJRfl7MaNMoDRnqx+CqspbQbBkI6OKI2CHipygu11qC2zUaozYWv4m6z2bVIA3NNPv4V677PE+zSU12Vr1Aym17VbSlwhA1U0WSLNOkkzuZzQeQJm2lXej5hz/+YWH2xmW/Fg5GuDKC6Nr3q2TfP+PVtP2A= ARC-Message-Signature:i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1774618750; c=relaxed/simple; bh=CWvZn9XYHRt7IbPNB8NgK/FbiSNX3345RM2xdCGMvYE=; h=Message-ID:Date:MIME-Version:Subject:To:Cc:References:From: In-Reply-To:Content-Type; b=MG4d6636+Zp4e+kSuuQZOxdDPIX1emYPVH3AdNENoBJyOduoBdbUFopgbk42EqkKytEpI6sDot/rwS8ivwN4V274g9+KAGeMGqua338h+fsPrGN01YT8O4oZY4BhdnbelXGZOFLAawWMLmR2WfWxnvkIEByJWlHLH7xABE7g4CI= ARC-Authentication-Results:i=1; smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=linux.ibm.com; spf=pass smtp.mailfrom=linux.ibm.com; dkim=pass (2048-bit key) header.d=ibm.com header.i=@ibm.com header.b=tVhPZCz+; arc=none smtp.client-ip=148.163.156.1 Authentication-Results: smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=linux.ibm.com Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=linux.ibm.com Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=ibm.com header.i=@ibm.com header.b="tVhPZCz+" Received: from pps.filterd (m0356517.ppops.net [127.0.0.1]) by mx0a-001b2d01.pphosted.com (8.18.1.11/8.18.1.11) with ESMTP id 62R8UaBI510743; Fri, 27 Mar 2026 13:38:41 GMT DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=ibm.com; h=cc :content-transfer-encoding:content-type:date:from:in-reply-to :message-id:mime-version:references:subject:to; s=pp1; bh=X5qAaf JxLcxD8LRSxugnQ8pE5BWlU68D12sVh4aja1o=; b=tVhPZCz+qlH0ixDdSGwIMy njyoJKORwXZ/SuOlnDx1wBZK2+WF8DBNvwjBuPW0AFHOgum7Vw9tyVCD3R9IX7Il 6+7ni2v80QVPj7aSDy6bimtW0aqrwDCZ5gTaRDxza/1cNHuW2h4VYKsMYq4fpnrC 97KWpw9gDb6TETgcuVW1J1j6/dOEUn+N+oqQpb7QkaUMAtTIHQBNgPBvSh4qGl0u ogs/tR0n8F8pXbdle75Sy9fx56lSo37f17ioadMi73emE779sT3WiRF38Bxjgtdl hJz78y5QLVzjbiynjxA6bfLDg0TCHsVBOxUySVLcG5WjlB7iRvXksTdjQt6VcysA == Received: from ppma11.dal12v.mail.ibm.com (db.9e.1632.ip4.static.sl-reverse.com [50.22.158.219]) by mx0a-001b2d01.pphosted.com (PPS) with ESMTPS id 4d1kwaac4n-1 (version=TLSv1.2 cipher=ECDHE-RSA-AES256-GCM-SHA384 bits=256 verify=NOT); Fri, 27 Mar 2026 13:38:40 +0000 (GMT) Received: from pps.filterd (ppma11.dal12v.mail.ibm.com [127.0.0.1]) by ppma11.dal12v.mail.ibm.com (8.18.1.2/8.18.1.2) with ESMTP id 62RCBDxP004407; Fri, 27 Mar 2026 13:38:39 GMT Received: from smtprelay01.fra02v.mail.ibm.com ([9.218.2.227]) by ppma11.dal12v.mail.ibm.com (PPS) with ESMTPS id 4d28c2fdqu-1 (version=TLSv1.2 cipher=ECDHE-RSA-AES256-GCM-SHA384 bits=256 verify=NOT); Fri, 27 Mar 2026 13:38:39 +0000 Received: from smtpav02.fra02v.mail.ibm.com (smtpav02.fra02v.mail.ibm.com [10.20.54.101]) by smtprelay01.fra02v.mail.ibm.com (8.14.9/8.14.9/NCO v10.0) with ESMTP id 62RDccq559965794 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-GCM-SHA384 bits=256 verify=OK); Fri, 27 Mar 2026 13:38:38 GMT Received: from smtpav02.fra02v.mail.ibm.com (unknown [127.0.0.1]) by IMSVA (Postfix) with ESMTP id 1C2EF2004B; Fri, 27 Mar 2026 13:38:38 +0000 (GMT) Received: from smtpav02.fra02v.mail.ibm.com (unknown [127.0.0.1]) by IMSVA (Postfix) with ESMTP id E097720043; Fri, 27 Mar 2026 13:38:35 +0000 (GMT) Received: from [9.39.30.147] (unknown [9.39.30.147]) by smtpav02.fra02v.mail.ibm.com (Postfix) with ESMTP; Fri, 27 Mar 2026 13:38:35 +0000 (GMT) Message-ID: <65c0ce37-ca30-4b9a-9136-bd1236330eaf@linux.ibm.com> Date: Fri, 27 Mar 2026 19:08:35 +0530 Precedence: bulk X-Mailing-List: linux-kernel@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 User-Agent: Mozilla Thunderbird Subject: Re: [PATCH] sched/topology: optimize sched_numa_find_nth_cpu() To: Valentin Schneider Cc: Yury Norov , Yury Norov , Peter Zijlstra , Ingo Molnar , Juri Lelli , Vincent Guittot , Dietmar Eggemann , Steven Rostedt , Ben Segall , Mel Gorman , linux-kernel@vger.kernel.org References: <20260319172607.926280-1-ynorov@nvidia.com> Content-Language: en-US From: Shrikanth Hegde In-Reply-To: Content-Type: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: 7bit X-TM-AS-GCONF: 00 X-Proofpoint-Reinject: loops=2 maxloops=12 X-Proofpoint-ORIG-GUID: 8lsOs_AipyzYATNS9McV6kMlcMjIBWFf X-Proofpoint-Spam-Details-Enc: AW1haW4tMjYwMzI3MDA5MSBTYWx0ZWRfX4SPGg6C8Dcu9 GAiat4DfqH1hBxqEcj/xGQEfqMc5KQ/iwFp7zA7PmW3LyYqK+rvSFFHAvtWDah5CwwL5uwPPpQj hCy5OsPQp8qJJw6Av6o0TIs9TqluzaDE/TQ5n2MFpN53BrhXt4DamtxvtwivC59k0F+mWU4lOJ6 3j8/Mp0as0k2CmrlUOvlvtOE6u/O6yGrM7JyafH8H6pD+qY1+C9BMXoPPPpRMoG/lcFM4AsVojd 37ctkep0EvXh319qjnP5TqpZ+vs8BHI7MbjV8Dn0X2xHszh8SXFGJkrOQZXbFegwWrJ81CQ3Aiu f35zpyZ8Jhg+H2JuH2ov8Xm8/eyUZdPFiM9cg4wDpPbBvKyRNwzM0UovVgM7J3t9zZ1r5ZuVY3f F2WSHCJeBOQFUr/A706dQviAn/I1y+sALW3/vQZTZ67N1edLVaMDfGbWQokfWJRonrt7q0s8Rcu ZWqUUuTyFqSPcNo/log== X-Proofpoint-GUID: sN5reClRjjhSbyNLvtNme4pWK9bcgBul X-Authority-Analysis: v=2.4 cv=OsZCCi/t c=1 sm=1 tr=0 ts=69c68861 cx=c_pps a=aDMHemPKRhS1OARIsFnwRA==:117 a=aDMHemPKRhS1OARIsFnwRA==:17 a=IkcTkHD0fZMA:10 a=Yq5XynenixoA:10 a=VkNPw1HP01LnGYTKEx00:22 a=RnoormkPH1_aCDwRdu11:22 a=U7nrCbtTmkRpXpFmAIza:22 a=Ikd4Dj_1AAAA:8 a=jgI6WJQOdLY477NTblMA:9 a=QEXdDO2ut3YA:10 X-Proofpoint-Virus-Version: vendor=baseguard engine=ICAP:2.0.293,Aquarius:18.0.1143,Hydra:6.1.51,FMLib:17.12.100.49 definitions=2026-03-26_04,2026-03-26_01,2025-10-01_01 X-Proofpoint-Spam-Details: rule=outbound_notspam policy=outbound score=0 impostorscore=0 adultscore=0 clxscore=1015 phishscore=0 suspectscore=0 lowpriorityscore=0 priorityscore=1501 bulkscore=0 spamscore=0 malwarescore=0 classifier=typeunknown authscore=0 authtc= authcc= route=outbound adjust=0 reason=mlx scancount=1 engine=8.22.0-2603050001 definitions=main-2603270091 Hi Valentin. On 3/27/26 1:15 AM, Valentin Schneider wrote: > On 26/03/26 20:09, Valentin Schneider wrote: >> On 19/03/26 13:26, Yury Norov wrote: >>> The binary search callback hop_cmp() uses cpumask_weight_and() on each >>> iteration. Switch it to cpumask_nth_and() as it returns earlier, as >>> soon as the required number of CPUs is found. >>> >>> Signed-off-by: Yury Norov >> >> Woopsie, forget about the empty reply. >> >> Took me a little while to get back on track with how >> sched_numa_find_nth_cpu() works. Doesn't help that it and the >> cpumask_nth*() family have a @cpu parameter when it isn't a CPU but an >> offset from a search start (i.e. an index, as coined for cpumask_local_spread()). >> >> Comments would help, Yes. It is quite difficult to get at first glance. I'll try to come up with something tomorrow if I wake >> up from whatever's brewing in my lungs :( > > I figured I'd give it a try before the fever kicks in: Take care. > --- > diff --git a/kernel/sched/topology.c b/kernel/sched/topology.c > index 32dcddaead82d..7069179d5ee0c 100644 > --- a/kernel/sched/topology.c > +++ b/kernel/sched/topology.c > @@ -2267,6 +2267,7 @@ static int hop_cmp(const void *a, const void *b) > struct cpumask **prev_hop, **cur_hop = *(struct cpumask ***)b; > struct __cmp_key *k = (struct __cmp_key *)a; > > + /* Not enough CPUs reachable in that many hops */ > if (cpumask_weight_and(k->cpus, cur_hop[k->node]) <= k->cpu) > return 1; > > @@ -2275,6 +2276,10 @@ static int hop_cmp(const void *a, const void *b) > return 0; > } > > + /* > + * cur_hop spans enough CPUs to return an nth one, if the immediately > + * preceding hop doesn't then we're done. > + */ > prev_hop = *((struct cpumask ***)b - 1); > k->w = cpumask_weight_and(k->cpus, prev_hop[k->node]); > if (k->w <= k->cpu) > @@ -2284,16 +2289,16 @@ static int hop_cmp(const void *a, const void *b) > } > > /** > - * sched_numa_find_nth_cpu() - given the NUMA topology, find the Nth closest CPU > - * from @cpus to @cpu, taking into account distance > - * from a given @node. > + * sched_numa_find_nth_cpu() - given the NUMA topology, find the @nth_cpu in > + * @cpus reachable from @node in the least amount > + * of hops. > * @cpus: cpumask to find a cpu from > - * @cpu: CPU to start searching > - * @node: NUMA node to order CPUs by distance > + * @nth_cpu: CPU offset to search for > + * @node: NUMA node to start the search from > * > * Return: cpu, or nr_cpu_ids when nothing found. > */ > -int sched_numa_find_nth_cpu(const struct cpumask *cpus, int cpu, int node) > +int sched_numa_find_nth_cpu(const struct cpumask *cpus, int nth_cpu, int node) > { > struct __cmp_key k = { .cpus = cpus, .cpu = cpu }; nit: it should .cpu = nth_cpu? and one more place below should change to nth_cpu. > struct cpumask ***hop_masks; > @@ -2315,8 +2320,21 @@ int sched_numa_find_nth_cpu(const struct cpumask *cpus, int cpu, int node) > hop_masks = bsearch(&k, k.masks, sched_domains_numa_levels, sizeof(k.masks[0]), hop_cmp); > if (!hop_masks) > goto unlock; > + /* > + * bsearch returned sched_domains_numa_masks[hop], with @hop being the > + * smallest amount of hops it takes to reach an @nth_cpu from @node. > + */ > hop = hop_masks - k.masks; > > + /* > + * @hop is constructed by hop_cmp() such that sched_domains_numa_masks[hop][node] > + * spans enough CPUs to return an @nth_cpu, and sched_domains_numa_masks[hop-1][node] > + * doesn't. > + * > + * Get a cpumask without the CPUs from sched_domains_numa_masks[hop-1][node] > + * subtract how many CPUs that contains (@k.w), and fetch our @nth_cpu from > + * the resulting mask. > + */ > ret = hop ? > cpumask_nth_and_andnot(cpu - k.w, cpus, k.masks[hop][node], k.masks[hop-1][node]) : > cpumask_nth_and(cpu, cpus, k.masks[0][node]); >