mirror of https://lore.kernel.org/lkml/
 help / color / mirror / Atom feed
From: K Prateek Nayak <kprateek.nayak@amd.com>
To: Ingo Molnar <mingo@redhat.com>,
	Peter Zijlstra <peterz@infradead.org>,
	Juri Lelli <juri.lelli@redhat.com>,
	Vincent Guittot <vincent.guittot@linaro.org>,
	Anna-Maria Behnsen <anna-maria@linutronix.de>,
	Frederic Weisbecker <frederic@kernel.org>,
	Thomas Gleixner <tglx@linutronix.de>
Cc: <linux-kernel@vger.kernel.org>,
	Dietmar Eggemann <dietmar.eggemann@arm.com>,
	Steven Rostedt <rostedt@goodmis.org>,
	Ben Segall <bsegall@google.com>, Mel Gorman <mgorman@suse.de>,
	Valentin Schneider <vschneid@redhat.com>,
	K Prateek Nayak <kprateek.nayak@amd.com>,
	"Gautham R. Shenoy" <gautham.shenoy@amd.com>,
	Swapnil Sapkal <swapnil.sapkal@amd.com>,
	Shrikanth Hegde <sshegde@linux.ibm.com>,
	Chen Yu <yu.c.chen@intel.com>
Subject: [RESEND RFC PATCH v2 27/29] [EXPERIMENTAL] sched/fair: Proactive idle balance using push mechanism
Date: Mon, 8 Dec 2025 09:27:13 +0000	[thread overview]
Message-ID: <20251208092744.32737-27-kprateek.nayak@amd.com> (raw)
In-Reply-To: <20251208083602.31898-1-kprateek.nayak@amd.com>

Proactively try to push tasks to one of the CPUs in the sd_nohz domain
if "nr_idle_cpus" indicator indicates the presence of idle CPUs.

pick_next_pushable_fair_task() is taken from Vincent's series [1] as is
but the locking rules in push_fair_task() has been replaced with an IPI
based __ttwu_queue_wakelist(). Few additional checks have been added to
catch any corner cases with proxy execution where neither the current,
not the donor is pushable.

For the sake of this PoC, the __ttwu_queue_wakelist() based mechanism is
being used as is. If folks are in agreement with wider use of the
wakelist based migration, we can work on making this wakelist based
activation path more generic to be used for migrations too.

Although it is logical to traverse the "sd_nohz->shared->nohz_idle_cpus"
only, in testing, traversing the entire span was found to be more
beneficial.

Link: https://lore.kernel.org/all/20250302210539.1563190-6-vincent.guittot@linaro.org/ [1]
Signed-off-by: K Prateek Nayak <kprateek.nayak@amd.com>
---
 kernel/sched/core.c  |  2 +-
 kernel/sched/fair.c  | 93 +++++++++++++++++++++++++++++++++++++++++++-
 kernel/sched/sched.h |  1 +
 3 files changed, 94 insertions(+), 2 deletions(-)

diff --git a/kernel/sched/core.c b/kernel/sched/core.c
index 35cb640b7266..388805c4436c 100644
--- a/kernel/sched/core.c
+++ b/kernel/sched/core.c
@@ -3769,7 +3769,7 @@ bool call_function_single_prep_ipi(int cpu)
  * via sched_ttwu_wakeup() for activation so the wakee incurs the cost
  * of the wakeup instead of the waker.
  */
-static void __ttwu_queue_wakelist(struct task_struct *p, int cpu, int wake_flags)
+void __ttwu_queue_wakelist(struct task_struct *p, int cpu, int wake_flags)
 {
 	struct rq *rq = cpu_rq(cpu);
 
diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
index e6ba7bb09a61..34aeb8e58e0b 100644
--- a/kernel/sched/fair.c
+++ b/kernel/sched/fair.c
@@ -13079,12 +13079,103 @@ static inline int has_pushable_tasks(struct rq *rq)
 	return !plist_head_empty(&rq->cfs.pushable_tasks);
 }
 
+static struct task_struct *pick_next_pushable_fair_task(struct rq *rq)
+{
+	struct task_struct *p;
+
+	if (!has_pushable_tasks(rq))
+		return NULL;
+
+	p = plist_first_entry(&rq->cfs.pushable_tasks,
+			      struct task_struct, pushable_tasks);
+
+	WARN_ON_ONCE(rq->cpu != task_cpu(p));
+	WARN_ON_ONCE(task_current(rq, p));
+	WARN_ON_ONCE(task_current_donor(rq, p));
+	WARN_ON_ONCE(p->nr_cpus_allowed <= 1);
+	WARN_ON_ONCE(!task_on_rq_queued(p));
+
+	/*
+	 * Remove task from the pushable list as we try only once after that
+	 * the task has been put back in enqueued list.
+	 */
+	plist_del(&p->pushable_tasks, &rq->cfs.pushable_tasks);
+
+	return p;
+}
+
+static inline bool should_push_tasks(struct rq *rq)
+{
+	struct sched_domain_shared *sds;
+	struct sched_domain *sd;
+	int cpu = cpu_of(rq);
+
+	/* TODO: Add a CPU local failure counter. */
+
+	/* CPU doesn't have any fair task to push. */
+	if (!has_pushable_tasks(rq))
+		return false;
+
+	/* CPU is overloaded! Do not waste cycles pushing tasks. */
+	if (!fits_capacity(cpu_util_cfs(cpu), capacity_of(cpu)))
+		return false;
+
+	guard(rcu)();
+
+	sd = rcu_dereference(per_cpu(sd_nohz, cpu));
+	if (!sd)
+		return false;
+
+	/*
+	 * We may not be able to find a push target.
+	 * Skip for this tick and depend on the periodic
+	 * balance to pull the queued tasks.
+	 */
+	sds = sd->shared;
+	if (!sds || !atomic_read(&sds->nr_idle_cpus))
+		return false;
+
+	return true;
+}
+
 /*
  * See if the non running fair tasks on this rq can be sent on other CPUs
  * that fits better with their profile.
  */
 static bool push_fair_task(struct rq *rq)
 {
+	struct task_struct *p = pick_next_pushable_fair_task(rq);
+	struct sched_domain_shared *sds;
+	int cpu, this_cpu = cpu_of(rq);
+	struct sched_domain *sd;
+
+	if (!p)
+		return false;
+
+	guard(rcu)();
+
+	sd = rcu_dereference(per_cpu(sd_nohz, cpu));
+	if (!sd)
+		return false;
+
+	/*
+	 * It is possble to have idle CPUs with ticks enabled. To maximize the chance
+	 * of pulling a task, traverse the entire sched_domain_span() instead of just
+	 * the sd->shared->nohz_idle_cpus.
+	 */
+	for_each_cpu_and_wrap(cpu, p->cpus_ptr, sched_domain_span(sd), this_cpu + 1) {
+		struct rq *target_rq;
+
+		if (!idle_cpu(cpu))
+			continue;
+
+		target_rq = cpu_rq(cpu);
+		deactivate_task(rq, p, 0);
+		set_task_cpu(p, cpu);
+		__ttwu_queue_wakelist(p, cpu, 0);
+		return true;
+	}
+
 	return false;
 }
 
@@ -13099,7 +13190,7 @@ static DEFINE_PER_CPU(struct balance_callback, fair_push_head);
 
 static inline void fair_queue_pushable_tasks(struct rq *rq)
 {
-	if (!has_pushable_tasks(rq))
+	if (should_push_tasks(rq))
 		return;
 
 	queue_balance_callback(rq, &per_cpu(fair_push_head, rq->cpu), push_fair_tasks);
diff --git a/kernel/sched/sched.h b/kernel/sched/sched.h
index 91928a371588..451666753c2a 100644
--- a/kernel/sched/sched.h
+++ b/kernel/sched/sched.h
@@ -2939,6 +2939,7 @@ static inline void __block_task(struct rq *rq, struct task_struct *p)
 
 extern void activate_task(struct rq *rq, struct task_struct *p, int flags);
 extern void deactivate_task(struct rq *rq, struct task_struct *p, int flags);
+void __ttwu_queue_wakelist(struct task_struct *p, int cpu, int wake_flags);
 
 extern void wakeup_preempt(struct rq *rq, struct task_struct *p, int flags);
 
-- 
2.43.0


  parent reply	other threads:[~2025-12-08  9:35 UTC|newest]

Thread overview: 35+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2025-12-08  9:26 [RESEND RFC PATCH v2 00/29] sched/fair: Push-based load balancing K Prateek Nayak
2025-12-08  9:26 ` [RESEND RFC PATCH v2 01/29] sched/fair: Simplify set_cpu_sd_state_*() with guards K Prateek Nayak
2025-12-08  9:26 ` [RESEND RFC PATCH v2 02/29] sched/fair: Use rq->nohz_tick_stopped in update_nohz_stats() K Prateek Nayak
2025-12-08  9:26 ` [RESEND RFC PATCH v2 03/29] sched/topology: Optimize sd->shared allocation and assignment K Prateek Nayak
2025-12-08  9:26 ` [RESEND RFC PATCH v2 04/29] sched/fair: Simplify the entry condition for update_idle_cpu_scan() K Prateek Nayak
2025-12-08  9:26 ` [RESEND RFC PATCH v2 05/29] sched/fair: Simplity SIS_UTIL handling in select_idle_cpu() K Prateek Nayak
2025-12-08  9:26 ` [RESEND RFC PATCH v2 06/29] cpumask: Introduce for_each_cpu_and_wrap() and bitfield helpers K Prateek Nayak
2025-12-12 21:03   ` Yury Norov
2025-12-08  9:26 ` [RESEND RFC PATCH v2 07/29] sched/fair: Use for_each_cpu_and_wrap() in select_idle_capacity() K Prateek Nayak
2025-12-08  9:26 ` [RESEND RFC PATCH v2 08/29] sched/fair: Use for_each_cpu_and_wrap() in select_idle_cpu() K Prateek Nayak
2025-12-08  9:26 ` [RESEND RFC PATCH v2 09/29] sched/fair: Rotate the CPU resposible for busy load balancing K Prateek Nayak
2025-12-08  9:26 ` [RESEND RFC PATCH v2 10/29] sched/fair: Use xchg() to set sd->nohz_idle state K Prateek Nayak
2025-12-08  9:26 ` [RESEND RFC PATCH v2 11/29] sched/topology: Attach new hierarchy in rq_attach_root() K Prateek Nayak
2025-12-08  9:26 ` [RESEND RFC PATCH v2 12/29] sched/fair: Fixup sd->nohz_idle state during hotplug / cpuset K Prateek Nayak
2025-12-08  9:26 ` [RESEND RFC PATCH v2 13/29] sched/fair: Account idle cpus instead of busy cpus in sd->shared K Prateek Nayak
2025-12-08  9:27 ` [RESEND RFC PATCH v2 14/29] sched/topology: Introduce fallback sd->shared assignment K Prateek Nayak
2025-12-08  9:27 ` [RESEND RFC PATCH v2 15/29] sched/topology: Introduce percpu sd_nohz for nohz state tracking K Prateek Nayak
2025-12-08  9:27 ` [RESEND RFC PATCH v2 16/29] sched/topology: Introduce "nohz_idle_cpus_mask" in sd->shared K Prateek Nayak
2025-12-08  9:27 ` [RESEND RFC PATCH v2 17/29] sched/topology: Introduce "nohz_shared_list" to keep track of sd->shared K Prateek Nayak
2025-12-08  9:27 ` [RESEND RFC PATCH v2 18/29] sched/fair: Reorder the barrier in nohz_balance_enter_idle() K Prateek Nayak
2025-12-08  9:27 ` [RESEND RFC PATCH v2 19/29] sched/fair: Extract the main _nohz_idle_balance() loop into a helper K Prateek Nayak
2025-12-08  9:27 ` [RESEND RFC PATCH v2 20/29] sched/fair: Convert find_new_ilb() to use nohz_shared_list K Prateek Nayak
2025-12-08  9:27 ` [RESEND RFC PATCH v2 21/29] sched/fair: Introduce sched_asym_prefer_idle() for ILB kick K Prateek Nayak
2025-12-08  9:27 ` [RESEND RFC PATCH v2 22/29] sched/fair: Convert sched_balance_nohz_idle() to use nohz_shared_list K Prateek Nayak
2025-12-08  9:27 ` [RESEND RFC PATCH v2 23/29] sched/fair: Remove "nohz.idle_cpus_mask" K Prateek Nayak
2025-12-08  9:27 ` [RESEND RFC PATCH v2 24/29] sched/fair: Optimize global "nohz.nr_cpus" tracking K Prateek Nayak
2025-12-08  9:27 ` [RESEND RFC PATCH v2 25/29] sched/topology: Add basic debug information for "nohz_shared_list" K Prateek Nayak
2025-12-08  9:27 ` [RESEND RFC PATCH v2 26/29] [EXPERIMENTAL] sched/fair: Add push task framework K Prateek Nayak
2025-12-08  9:27 ` K Prateek Nayak [this message]
2025-12-08  9:27 ` [RESEND RFC PATCH v2 28/29] [EXPERIMENTAL] sched/fair: Add a local counter to rate limit task push K Prateek Nayak
2025-12-08 12:33   ` Christian Loehle
2025-12-08 17:35     ` K Prateek Nayak
2025-12-08  9:27 ` [RESEND RFC PATCH v2 29/29] [EXPERIMENTAL] sched/fair: Faster alternate for intra-NUMA newidle balance K Prateek Nayak
2025-12-08 14:04 ` [RESEND RFC PATCH v2 00/29] sched/fair: Push-based load balancing Shrikanth Hegde
2025-12-08 17:36   ` K Prateek Nayak

Reply instructions:

You may reply publicly to this message via plain-text email
using any one of the following methods:

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

  Avoid top-posting and favor interleaved quoting:
  https://en.wikipedia.org/wiki/Posting_style#Interleaved_style

* Reply using the --to, --cc, and --in-reply-to
  switches of git-send-email(1):

  git send-email \
    --in-reply-to=20251208092744.32737-27-kprateek.nayak@amd.com \
    --to=kprateek.nayak@amd.com \
    --cc=anna-maria@linutronix.de \
    --cc=bsegall@google.com \
    --cc=dietmar.eggemann@arm.com \
    --cc=frederic@kernel.org \
    --cc=gautham.shenoy@amd.com \
    --cc=juri.lelli@redhat.com \
    --cc=linux-kernel@vger.kernel.org \
    --cc=mgorman@suse.de \
    --cc=mingo@redhat.com \
    --cc=peterz@infradead.org \
    --cc=rostedt@goodmis.org \
    --cc=sshegde@linux.ibm.com \
    --cc=swapnil.sapkal@amd.com \
    --cc=tglx@linutronix.de \
    --cc=vincent.guittot@linaro.org \
    --cc=vschneid@redhat.com \
    --cc=yu.c.chen@intel.com \
    /path/to/YOUR_REPLY

  https://kernel.org/pub/software/scm/git/docs/git-send-email.html

* If your mail client supports setting the In-Reply-To header
  via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox

all inboxes | Powered by JetHome®