From nobody Sat Feb 7 22:54:49 2026 Received: from mail-dy1-f177.google.com (mail-dy1-f177.google.com [74.125.82.177]) (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 ECFFC42EEB1 for ; Thu, 22 Jan 2026 15:20:37 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=74.125.82.177 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1769095240; cv=none; b=fgxVb2a3rY6OEspxeuUW7w93egF8mfxSLzZXWM7doYp2QFfyilN/mZkmbz0136GxPCTBeiugUIGpEPlsrsxlCuwxnv4lh54k/0fAGcJX1bVG/Jg0TKdTKNCxliMV0Ldyyg8aYlJGmfXknagyZPumMyPUZYD7AbpquVIPNmDvG/A= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1769095240; c=relaxed/simple; bh=i7iar9wfyMQIE1oP2WGjeafxCMjB8JGFk3fzyyv8W14=; h=From:To:Cc:Subject:Date:Message-ID:MIME-Version; b=HwWDFwx+y9SLr3lxGVIcuNYgxvfLQAYTF06IhP2OWsV8mr+oefTy3FQGZmIUCUSPUF9/9JQgIpiTtPLrK5WJBJPt8BKymVIgQnBoGMBnocbaiCVzMLVCKXhiQDzue5TuD/U0ayCa1u5BqR3F/En/xKYL+8kSuFW35fdcWzEedL4= 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=iSJUplVj; arc=none smtp.client-ip=74.125.82.177 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="iSJUplVj" Received: by mail-dy1-f177.google.com with SMTP id 5a478bee46e88-2b720e4dcb4so1074481eec.0 for ; Thu, 22 Jan 2026 07:20:37 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1769095237; x=1769700037; darn=vger.kernel.org; h=content-transfer-encoding:mime-version:message-id:date:subject:cc :to:from:from:to:cc:subject:date:message-id:reply-to; bh=IYPv//WdLvNCyuJGatdvuu36vlWrGWXXTXRcOTAssrA=; b=iSJUplVjfqMAPOpt1GuEk6P6L3Axtg+ieFSfqcSDp2kX5mcfzs4PHvwXG15nOiPUsF ozIQH2E6ZpOtzr7doVCXRTCD4UqKXAeg2bMMAZazuu6Ug8vvUr5uxX9O+QJStRh7c3da SMCfWHMKrfwe9gHLaegOAUjB3E0urLK+m+BPx5PtcIwNmXWDtt8ANDpqXEkUU7+9Bhw3 hFU0DKFqLYj/WAxu3ZGhlvpVSXtNNth1Glmzm8uoJXrHUJ3Z2SALY/+HwKNY5Zg/DHDu SCiC6sWOqc4CK5wxCaquES2QFrJ049EA1AG1p/zO7sZi/ONu7tnzK70yPERWCkQoJXPE HMsA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1769095237; x=1769700037; h=content-transfer-encoding:mime-version:message-id:date:subject:cc :to:from:x-gm-gg:x-gm-message-state:from:to:cc:subject:date :message-id:reply-to; bh=IYPv//WdLvNCyuJGatdvuu36vlWrGWXXTXRcOTAssrA=; b=q2AbAm0GX6QTtfNqBwJVcSgBSNb4ldVb3x0zxRD7dzeR7Wd5Lrjk0dKV85q7gEEG/4 5HZUr+bWZaHE6hp5A/WNsoL5vTnPMZhGLKAmxlyUW4inhaVzC5loFw89+9XFObngPMFg cm0LurH55wVU80x0vtj7ub0RVjeUDSg1G1I+Jtqc9IItHZotqxfQyOf3Nh2nbnZT6NeG HQ2LPgxqkXai2SrsOOIVj1hm39cj+VKVuHkE2ac9e+Q9uLZYEFLa0fzYRl3xAaBZG8vZ Yqo1cwgpO7E+o7NXVmsNpvkPuAp/qycxIEPld+4diwBZ1zYQQCKGUdf8m8CFXgbHy/Ue gQvA== X-Forwarded-Encrypted: i=1; AJvYcCVDorWe1ySw7FqX3MSIekawEb8WYkxMjjgRuq8E93ql3liYaSVo4njpBjq2aTNJwLKffhpHzoyoCcCVNE8=@vger.kernel.org X-Gm-Message-State: AOJu0YwU0LCeZYuZLm+vkj3A3jp0WbV+yHKC6SeQdVbw+r9+D7Ahpj9c 7bXp+jwrnmWBel1mn/i58HxU9yQrT7AeJh47W6zW+nrzdE/IZJy62JID X-Gm-Gg: AZuq6aI8g/wACDrSJxnDpF8vKjcOPcuPP/+2cIoacE1SVq5k8+lOb1VnV3zGzFxL/uc /HwqshQipmonaaNU52S2u7vybpjlGi7V/NogPbVCXbyCXCQHufgqSV0utR7LWJc+Inpcn1jLgtr Dwmd8wqhkmG1v2grjh5abAKKypS7FUimoCbZvM+KHwcjfpaVyGiIr4G2oZ49NQChRHX3B8cGH5Q c9K7V2G7MZ9JOevvSaHnjRW9+SfylKH6lY9OxjrAXULflQ0qR6voUqfNx+Mv64mb0vO52L6sPv8 gT3LX1rfcNaG8t4NsFbyhaGgsipL/LrnMrl4KRU5kxWldhQ+FOpDssidrxm/Bt8xbJ7C1whPcMx sBg4LbnjpZBbKe3Oy46zZG3jgBx4cjlkdOdF++ui8ksa8TrVDUEBErel7D8o7WonSDkDoPk1yHp CNxt4= X-Received: by 2002:a05:7300:b913:b0:2a4:3592:c5f0 with SMTP id 5a478bee46e88-2b6fd623eeamr4961197eec.1.1769095236800; Thu, 22 Jan 2026 07:20:36 -0800 (PST) Received: from debian ([74.48.213.230]) by smtp.gmail.com with ESMTPSA id 5a478bee46e88-2b6b34c0f7fsm25949836eec.3.2026.01.22.07.20.31 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Thu, 22 Jan 2026 07:20:36 -0800 (PST) From: Qiliang Yuan To: mingo@redhat.com, peterz@infradead.org, juri.lelli@redhat.com, vincent.guittot@linaro.org Cc: dietmar.eggemann@arm.com, rostedt@goodmis.org, bsegall@google.com, mgorman@suse.de, vschneid@redhat.com, linux-kernel@vger.kernel.org, Qiliang Yuan , Qiliang Yuan Subject: [PATCH] sched/fair: Optimize idle core discovery algorithm via LLC-wide bitmask Date: Thu, 22 Jan 2026 10:20:24 -0500 Message-ID: <20260122152024.124979-1-realwujing@gmail.com> X-Mailer: git-send-email 2.51.0 Precedence: bulk X-Mailing-List: linux-kernel@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 Content-Transfer-Encoding: quoted-printable Content-Type: text/plain; charset="utf-8" The current select_idle_cpu() employs a linear O(N) scan to find idle cores, which scales poorly on modern high-core-count systems. This patch optimizes the discovery algorithm by: 1. Adding a per-LLC 'idle_cores_mask' to sched_domain_shared for tracking core-level idle status. 2. Converting the linear search into an efficient bitmask iteration, reducing typical search complexity towards O(1) in sparse scenarios. 3. Implementing a lazy-clear mechanism during the scan to maintain efficiency without expensive global synchronization. This algorithmic refinement minimizes the search space in the critical wakeup path, effectively mitigating linear scaling overhead on large SMT machines. Signed-off-by: Qiliang Yuan Signed-off-by: Qiliang Yuan --- include/linux/sched/topology.h | 1 + kernel/sched/fair.c | 49 ++++++++++++++++++++++++---------- kernel/sched/topology.c | 2 +- 3 files changed, 37 insertions(+), 15 deletions(-) diff --git a/include/linux/sched/topology.h b/include/linux/sched/topology.h index 45c0022b91ce..4223f2cd7eb8 100644 --- a/include/linux/sched/topology.h +++ b/include/linux/sched/topology.h @@ -68,6 +68,7 @@ struct sched_domain_shared { atomic_t nr_busy_cpus; int has_idle_cores; int nr_idle_scan; + unsigned long idle_cores_mask[]; }; =20 struct sched_domain { diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c index e71302282671..458324d240e9 100644 --- a/kernel/sched/fair.c +++ b/kernel/sched/fair.c @@ -7507,8 +7507,13 @@ static inline void set_idle_cores(int cpu, int val) struct sched_domain_shared *sds; =20 sds =3D rcu_dereference(per_cpu(sd_llc_shared, cpu)); - if (sds) + if (sds) { WRITE_ONCE(sds->has_idle_cores, val); + if (val) + cpumask_set_cpu(cpu, (struct cpumask *)sds->idle_cores_mask); + else + cpumask_clear((struct cpumask *)sds->idle_cores_mask); + } } =20 static inline bool test_idle_cores(int cpu) @@ -7678,23 +7683,39 @@ static int select_idle_cpu(struct task_struct *p, s= truct sched_domain *sd, bool } } =20 - for_each_cpu_wrap(cpu, cpus, target + 1) { - if (has_idle_core) { - i =3D select_idle_core(p, cpu, cpus, &idle_cpu); - if ((unsigned int)i < nr_cpumask_bits) - return i; + if (has_idle_core) { + sd_share =3D rcu_dereference(per_cpu(sd_llc_shared, target)); + if (sd_share) { + for_each_cpu_wrap(cpu, (struct cpumask *)sd_share->idle_cores_mask, tar= get + 1) { + if (!cpumask_test_cpu(cpu, cpus)) + continue; =20 - } else { - if (--nr <=3D 0) - return -1; - idle_cpu =3D __select_idle_cpu(cpu, p); - if ((unsigned int)idle_cpu < nr_cpumask_bits) - break; + i =3D select_idle_core(p, cpu, cpus, &idle_cpu); + if ((unsigned int)i < nr_cpumask_bits) + return i; + + /* Core is no longer idle, clear the hint */ + cpumask_clear_cpu(cpu, (struct cpumask *)sd_share->idle_cores_mask); + } + + /* Searched all hinted cores and found none */ + set_idle_cores(target, false); } + /* If we found an idle CPU during core search, return it */ + if (idle_cpu !=3D -1) + return idle_cpu; + + /* Fall through to any-CPU search if needed */ + has_idle_core =3D false; } =20 - if (has_idle_core) - set_idle_cores(target, false); + for_each_cpu_wrap(cpu, cpus, target + 1) { + if (--nr <=3D 0) + return -1; + idle_cpu =3D __select_idle_cpu(cpu, p); + if ((unsigned int)idle_cpu < nr_cpumask_bits) + break; + } =20 return idle_cpu; } diff --git a/kernel/sched/topology.c b/kernel/sched/topology.c index cf643a5ddedd..5a3f29a26bdb 100644 --- a/kernel/sched/topology.c +++ b/kernel/sched/topology.c @@ -2392,7 +2392,7 @@ static int __sdt_alloc(const struct cpumask *cpu_map) =20 *per_cpu_ptr(sdd->sd, j) =3D sd; =20 - sds =3D kzalloc_node(sizeof(struct sched_domain_shared), + sds =3D kzalloc_node(sizeof(struct sched_domain_shared) + cpumask_size(= ), GFP_KERNEL, cpu_to_node(j)); if (!sds) return -ENOMEM; --=20 2.51.0