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 26/29] [EXPERIMENTAL] sched/fair: Add push task framework
Date: Mon, 8 Dec 2025 09:27:12 +0000 [thread overview]
Message-ID: <20251208092744.32737-26-kprateek.nayak@amd.com> (raw)
In-Reply-To: <20251208083602.31898-1-kprateek.nayak@amd.com>
From: Vincent Guittot <vincent.guittot@linaro.org>
Add the skeleton for push task infrastructure. The empty
push_fair_task() prototype will be used to implement proactive idle
balancing in subsequent commits.
[ prateek: Broke off relevant bits from [1] ]
Link: https://lore.kernel.org/all/20250302210539.1563190-6-vincent.guittot@linaro.org/ [1]
Signed-off-by: Vincent Guittot <vincent.guittot@linaro.org>
Signed-off-by: K Prateek Nayak <kprateek.nayak@amd.com>
---
Peter, the plist is still being used since a plist node already exists
in the task_struct which can be reused. Depending on the collective push
effort, we can either settle on the reuse of the plist_node or add a new
list_head for fair tasks.
---
kernel/sched/fair.c | 102 +++++++++++++++++++++++++++++++++++++++++++
kernel/sched/sched.h | 2 +
2 files changed, 104 insertions(+)
diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
index f622104d54d7..e6ba7bb09a61 100644
--- a/kernel/sched/fair.c
+++ b/kernel/sched/fair.c
@@ -6865,6 +6865,9 @@ requeue_delayed_entity(struct sched_entity *se)
clear_delayed(se);
}
+static void fair_remove_pushable_task(struct rq *rq, struct task_struct *p);
+static void fair_add_pushable_task(struct rq *rq, struct task_struct *p);
+
/*
* The enqueue_task method is called before nr_running is
* increased. Here we update the fair scheduling stats and
@@ -7015,6 +7018,7 @@ static int dequeue_entities(struct rq *rq, struct sched_entity *se, int flags)
h_nr_idle = task_has_idle_policy(p);
if (task_sleep || task_delayed || !se->sched_delayed)
h_nr_runnable = 1;
+ fair_remove_pushable_task(rq, p);
}
for_each_sched_entity(se) {
@@ -8954,6 +8958,12 @@ pick_next_task_fair(struct rq *rq, struct task_struct *prev, struct rq_flags *rf
put_prev_entity(cfs_rq, pse);
set_next_entity(cfs_rq, se);
+ /*
+ * The previous task might be eligible for being pushed on
+ * another cpu if it is still active.
+ */
+ fair_add_pushable_task(rq, prev);
+
__set_next_task_fair(rq, p, true);
}
@@ -9017,6 +9027,13 @@ static void put_prev_task_fair(struct rq *rq, struct task_struct *prev, struct t
cfs_rq = cfs_rq_of(se);
put_prev_entity(cfs_rq, se);
}
+
+ /*
+ * The previous task might be eligible for being pushed on another cpu
+ * if it is still active.
+ */
+ fair_add_pushable_task(rq, prev);
+
}
/*
@@ -13028,6 +13045,79 @@ static void nohz_newidle_balance(struct rq *this_rq)
atomic_or(NOHZ_NEWILB_KICK, nohz_flags(this_cpu));
}
+/*
+ * Push based load balancing: It may take several ticks before a nohz idle CPU
+ * is selected for load balancing which is less than ideal for latency
+ * sensitive tasks stuck on overloaded CPUs.
+ *
+ * If a fair task is preempted, opportunistically try pushing to an idle CPU if
+ * the indicators say it is favourable. Since a busy CPU is handling the push,
+ * this is a time sensitive operation.
+ */
+static inline bool fair_push_task(struct rq *rq, struct task_struct *p)
+{
+ if (!task_on_rq_queued(p))
+ return false;
+
+ if (p->se.sched_delayed)
+ return false;
+
+ if (p->nr_cpus_allowed == 1)
+ return false;
+
+ if (task_current_donor(rq, p))
+ return false;
+
+ if (task_current(rq, p))
+ return false;
+
+ return true;
+}
+
+static inline int has_pushable_tasks(struct rq *rq)
+{
+ return !plist_head_empty(&rq->cfs.pushable_tasks);
+}
+
+/*
+ * 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)
+{
+ return false;
+}
+
+static void push_fair_tasks(struct rq *rq)
+{
+ /* push_fair_task() will return true if it moved a fair task */
+ while (push_fair_task(rq))
+ ;
+}
+
+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))
+ return;
+
+ queue_balance_callback(rq, &per_cpu(fair_push_head, rq->cpu), push_fair_tasks);
+}
+static void fair_remove_pushable_task(struct rq *rq, struct task_struct *p)
+{
+ plist_del(&p->pushable_tasks, &rq->cfs.pushable_tasks);
+}
+
+static void fair_add_pushable_task(struct rq *rq, struct task_struct *p)
+{
+ if (fair_push_task(rq, p)) {
+ plist_del(&p->pushable_tasks, &rq->cfs.pushable_tasks);
+ /* Place the task with greates chance to be pushed first. */
+ plist_node_init(&p->pushable_tasks, p->prio);
+ plist_add(&p->pushable_tasks, &rq->cfs.pushable_tasks);
+ }
+}
#else /* !CONFIG_NO_HZ_COMMON: */
static inline void cpu_sd_exit_nohz_balance(struct rq *rq) { }
static inline void cpu_sd_reenter_nohz_balance(struct rq *rq) { }
@@ -13039,6 +13129,10 @@ static inline bool nohz_idle_balance(struct rq *this_rq, enum cpu_idle_type idle
}
static inline void nohz_newidle_balance(struct rq *this_rq) { }
+
+static inline void fair_remove_pushable_task(struct rq *rq, struct task_struct *p) { }
+static inline void fair_add_pushable_task(struct rq *rq, struct task_struct *p) { }
+static inline void fair_queue_pushable_tasks(struct rq *rq) { }
#endif /* !CONFIG_NO_HZ_COMMON */
/*
@@ -13738,6 +13832,8 @@ static void __set_next_task_fair(struct rq *rq, struct task_struct *p, bool firs
{
struct sched_entity *se = &p->se;
+ fair_remove_pushable_task(rq, p);
+
if (task_on_rq_queued(p)) {
/*
* Move the next running task to the front of the list, so our
@@ -13753,6 +13849,11 @@ static void __set_next_task_fair(struct rq *rq, struct task_struct *p, bool firs
if (hrtick_enabled_fair(rq))
hrtick_start_fair(rq, p);
+ /*
+ * Try to push prev task before checking misfit for next task as
+ * the migration of prev can make next fitting the CPU
+ */
+ fair_queue_pushable_tasks(rq);
update_misfit_status(p, rq);
sched_fair_update_stop_tick(rq, p);
}
@@ -13782,6 +13883,7 @@ void init_cfs_rq(struct cfs_rq *cfs_rq)
{
cfs_rq->tasks_timeline = RB_ROOT_CACHED;
cfs_rq->zero_vruntime = (u64)(-(1LL << 20));
+ plist_head_init(&cfs_rq->pushable_tasks);
raw_spin_lock_init(&cfs_rq->removed.lock);
}
diff --git a/kernel/sched/sched.h b/kernel/sched/sched.h
index 3433de20a249..91928a371588 100644
--- a/kernel/sched/sched.h
+++ b/kernel/sched/sched.h
@@ -743,6 +743,8 @@ struct cfs_rq {
struct list_head leaf_cfs_rq_list;
struct task_group *tg; /* group that "owns" this runqueue */
+ struct plist_head pushable_tasks;
+
/* Locally cached copy of our task_group's idle value */
int idle;
--
2.43.0
next prev 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 ` K Prateek Nayak [this message]
2025-12-08 9:27 ` [RESEND RFC PATCH v2 27/29] [EXPERIMENTAL] sched/fair: Proactive idle balance using push mechanism K Prateek Nayak
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-26-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®