From: K Prateek Nayak <kprateek.nayak@amd.com>
To: Peter Zijlstra <peterz@infradead.org>,
Ingo Molnar <mingo@redhat.com>,
Juri Lelli <juri.lelli@redhat.com>,
Vincent Guittot <vincent.guittot@linaro.org>,
Valentin Schneider <vschneid@redhat.com>,
"Ben Segall" <bsegall@google.com>,
Thomas Gleixner <tglx@linutronix.de>,
"Andy Lutomirski" <luto@kernel.org>,
<linux-kernel@vger.kernel.org>
Cc: Dietmar Eggemann <dietmar.eggemann@arm.com>,
Steven Rostedt <rostedt@goodmis.org>,
Mel Gorman <mgorman@suse.de>,
"Sebastian Andrzej Siewior" <bigeasy@linutronix.de>,
Clark Williams <clrkwllms@kernel.org>,
<linux-rt-devel@lists.linux.dev>, Tejun Heo <tj@kernel.org>,
"Frederic Weisbecker" <frederic@kernel.org>,
Barret Rhoden <brho@google.com>, "Petr Mladek" <pmladek@suse.com>,
Josh Don <joshdon@google.com>, Qais Yousef <qyousef@layalina.io>,
"Paul E. McKenney" <paulmck@kernel.org>,
David Vernet <dvernet@meta.com>,
K Prateek Nayak <kprateek.nayak@amd.com>,
"Gautham R. Shenoy" <gautham.shenoy@amd.com>,
Swapnil Sapkal <swapnil.sapkal@amd.com>
Subject: [RFC PATCH 21/22] [MAYBE BUGFIX] sched/fair: Group all the se->min_* members together for propagation
Date: Thu, 20 Feb 2025 09:32:56 +0000 [thread overview]
Message-ID: <20250220093257.9380-22-kprateek.nayak@amd.com> (raw)
In-Reply-To: <20250220093257.9380-1-kprateek.nayak@amd.com>
When working on the prototype, at some point, min_kcs_vruntime heap
integrity issues were encountered. Since then many bugs were ironed out
but when auditing rb_{add,erase}_augmented_cached(), it was noticed that
only "min_vruntime" was considered as RBAUGMENTED for
RB_DECLARE_CALLBACKS().
The augment->copy() function generated only copies RBAUGMENTED member.
It is very likely that augment->propagate() is always called after
augment->copy() similar to the convention in augment->rotate() which
reconstructs all of min_{vruntime,slice,kcs_vruntime} before comparing
if the values have changed however this author was not sure if
augment->propagate() indeed reaches until the copied node for Case 2.
in __rb_erase_augmented().
Group all the min_* members together that need propagation to rb_root
and pass the new "min" struct as RBAUGMENTED to ease the author's
paranoia.
XXX: Reverting this bit reintroduces the heap integrity issue. It does
not happen immediately into the run and the amount of traces are
overwhelming to analyze which series of rbtree operations lead to this
but with this patch I haven't run into the heap integrity issue so far.
The cover letter should have more details.
Signed-off-by: K Prateek Nayak <kprateek.nayak@amd.com>
---
include/linux/sched.h | 20 +++++++++-------
kernel/sched/debug.c | 2 +-
kernel/sched/fair.c | 54 +++++++++++++++++++++----------------------
3 files changed, 40 insertions(+), 36 deletions(-)
diff --git a/include/linux/sched.h b/include/linux/sched.h
index 200cc086e121..6fd5cee3a0f5 100644
--- a/include/linux/sched.h
+++ b/include/linux/sched.h
@@ -549,8 +549,18 @@ struct sched_entity {
struct load_weight load;
struct rb_node run_node;
u64 deadline;
- u64 min_vruntime;
- u64 min_slice;
+ struct {
+ u64 vruntime;
+ u64 slice;
+
+#ifdef CONFIG_FAIR_GROUP_SCHED
+ /*
+ * min_vruntime of the kernel mode preempted
+ * entities in the subtree of this sched entity.
+ */
+ s64 kcs_vruntime;
+#endif
+ } min;
struct list_head group_node;
unsigned char on_rq;
@@ -601,12 +611,6 @@ struct sched_entity {
/* Entity picked on a throttled hierarchy */
unsigned char sched_throttled;
/* hole */
-
- /*
- * min_vruntime of the kernel mode preempted entities
- * in the subtree of this sched entity.
- */
- s64 min_kcs_vruntime;
#endif /* CONFIG_CFS_BANDWIDTH */
#endif /* CONFIG_FAIR_GROUP_SCHED */
diff --git a/kernel/sched/debug.c b/kernel/sched/debug.c
index ef047add7f9e..37bca53f109f 100644
--- a/kernel/sched/debug.c
+++ b/kernel/sched/debug.c
@@ -821,7 +821,7 @@ void print_cfs_rq(struct seq_file *m, int cpu, struct cfs_rq *cfs_rq)
raw_spin_rq_lock_irqsave(rq, flags);
root = __pick_root_entity(cfs_rq);
if (root)
- left_vruntime = root->min_vruntime;
+ left_vruntime = root->min.vruntime;
first = __pick_first_entity(cfs_rq);
if (first)
left_deadline = first->deadline;
diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
index 39c7e8f548ca..97566a043398 100644
--- a/kernel/sched/fair.c
+++ b/kernel/sched/fair.c
@@ -768,7 +768,7 @@ int pick_subtree(struct cfs_rq *cfs_rq, struct sched_entity *se, bool h_throttle
if (unlikely(h_throttled))
return pick_subtree_on_throttled(cfs_rq, se);
- return vruntime_eligible(cfs_rq, se->min_vruntime);
+ return vruntime_eligible(cfs_rq, se->min.vruntime);
}
static u64 __update_min_vruntime(struct cfs_rq *cfs_rq, u64 vruntime)
@@ -800,9 +800,9 @@ static void update_min_vruntime(struct cfs_rq *cfs_rq)
if (se) {
if (!curr)
- vruntime = se->min_vruntime;
+ vruntime = se->min.vruntime;
else
- vruntime = min_vruntime(vruntime, se->min_vruntime);
+ vruntime = min_vruntime(vruntime, se->min.vruntime);
}
/* ensure we never gain time by being placed backwards. */
@@ -819,7 +819,7 @@ static inline u64 cfs_rq_min_slice(struct cfs_rq *cfs_rq)
min_slice = curr->slice;
if (root)
- min_slice = min(min_slice, root->min_slice);
+ min_slice = min(min_slice, root->min.slice);
return min_slice;
}
@@ -835,8 +835,8 @@ static inline void __min_vruntime_update(struct sched_entity *se, struct rb_node
{
if (node) {
struct sched_entity *rse = __node_2_se(node);
- if (vruntime_gt(min_vruntime, se, rse))
- se->min_vruntime = rse->min_vruntime;
+ if (vruntime_gt(min.vruntime, se, rse))
+ se->min.vruntime = rse->min.vruntime;
}
}
@@ -844,8 +844,8 @@ static inline void __min_slice_update(struct sched_entity *se, struct rb_node *n
{
if (node) {
struct sched_entity *rse = __node_2_se(node);
- if (rse->min_slice < se->min_slice)
- se->min_slice = rse->min_slice;
+ if (rse->min.slice < se->min.slice)
+ se->min.slice = rse->min.slice;
}
}
@@ -853,30 +853,30 @@ static __always_inline void init_se_kcs_stats(struct sched_entity *se);
static inline bool min_kcs_vruntime_update(struct sched_entity *se);
/*
- * se->min_vruntime = min(se->vruntime, {left,right}->min_vruntime)
+ * se->min.vruntime = min(se->vruntime, {left,right}->min_vruntime)
*/
static inline bool min_vruntime_update(struct sched_entity *se, bool exit)
{
- u64 old_min_vruntime = se->min_vruntime;
- u64 old_min_slice = se->min_slice;
+ u64 old_min_vruntime = se->min.vruntime;
+ u64 old_min_slice = se->min.slice;
struct rb_node *node = &se->run_node;
bool kcs_stats_unchanged = min_kcs_vruntime_update(se);
- se->min_vruntime = se->vruntime;
+ se->min.vruntime = se->vruntime;
__min_vruntime_update(se, node->rb_right);
__min_vruntime_update(se, node->rb_left);
- se->min_slice = se->slice;
+ se->min.slice = se->slice;
__min_slice_update(se, node->rb_right);
__min_slice_update(se, node->rb_left);
- return se->min_vruntime == old_min_vruntime &&
- se->min_slice == old_min_slice &&
+ return se->min.vruntime == old_min_vruntime &&
+ se->min.slice == old_min_slice &&
kcs_stats_unchanged;
}
RB_DECLARE_CALLBACKS(static, min_vruntime_cb, struct sched_entity,
- run_node, min_vruntime, min_vruntime_update);
+ run_node, min, min_vruntime_update);
/*
* Enqueue an entity into the rb-tree:
@@ -885,8 +885,8 @@ static void __enqueue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se)
{
avg_vruntime_add(cfs_rq, se);
init_se_kcs_stats(se);
- se->min_vruntime = se->vruntime;
- se->min_slice = se->slice;
+ se->min.vruntime = se->vruntime;
+ se->min.slice = se->slice;
rb_add_augmented_cached(&se->run_node, &cfs_rq->tasks_timeline,
__entity_less, &min_vruntime_cb);
}
@@ -953,7 +953,7 @@ static inline void cancel_protect_slice(struct sched_entity *se)
* tree keeps the entries sorted on deadline, but also functions as a
* heap based on the vruntime by keeping:
*
- * se->min_vruntime = min(se->vruntime, se->{left,right}->min_vruntime)
+ * se->min.vruntime = min(se->vruntime, se->{left,right}->min_vruntime)
*
* Which allows tree pruning through eligibility.
*/
@@ -7018,7 +7018,7 @@ static __always_inline void init_se_kcs_stats(struct sched_entity *se)
* the upper bound to differentiate the case where no kernel mode preempted
* entities are queued on the subtree.
*/
- se->min_kcs_vruntime = (se_in_kernel(se)) ? se->vruntime : LLONG_MAX;
+ se->min.kcs_vruntime = (se_in_kernel(se)) ? se->vruntime : LLONG_MAX;
}
/*
@@ -7096,11 +7096,11 @@ static __always_inline
int pick_subtree_on_throttled(struct cfs_rq *cfs_rq, struct sched_entity *se)
{
/* There are no kernel mode preempted entities in the subtree. */
- if (se->min_kcs_vruntime == LLONG_MAX)
+ if (se->min.kcs_vruntime == LLONG_MAX)
return false;
return throttled_vruntime_eligible(cfs_rq,
- se->min_kcs_vruntime,
+ se->min.kcs_vruntime,
curr_h_is_throttled(cfs_rq));
}
@@ -7109,21 +7109,21 @@ static inline void __min_kcs_vruntime_update(struct sched_entity *se, struct rb_
if (node) {
struct sched_entity *rse = __node_2_se(node);
- if (rse->min_kcs_vruntime < se->min_kcs_vruntime)
- se->min_kcs_vruntime = rse->min_kcs_vruntime;
+ if (rse->min.kcs_vruntime < se->min.kcs_vruntime)
+ se->min.kcs_vruntime = rse->min.kcs_vruntime;
}
}
static inline bool min_kcs_vruntime_update(struct sched_entity *se)
{
- u64 old_min_kcs_vruntime = se->min_kcs_vruntime;
+ u64 old_min_kcs_vruntime = se->min.kcs_vruntime;
struct rb_node *node = &se->run_node;
init_se_kcs_stats(se);
__min_kcs_vruntime_update(se, node->rb_right);
__min_kcs_vruntime_update(se, node->rb_left);
- return se->min_kcs_vruntime == old_min_kcs_vruntime;
+ return se->min.kcs_vruntime == old_min_kcs_vruntime;
}
static inline void account_kcs_enqueue(struct cfs_rq *gcfs_rq, bool in_kernel)
@@ -7341,7 +7341,7 @@ static __always_inline int pick_se_on_throttled(struct cfs_rq *cfs_rq, struct sc
static __always_inline
int pick_subtree_on_throttled(struct cfs_rq *cfs_rq, struct sched_entity *se)
{
- return vruntime_eligible(cfs_rq, se->min_vruntime);
+ return vruntime_eligible(cfs_rq, se->min.vruntime);
}
static inline bool min_kcs_vruntime_update(struct sched_entity *se)
--
2.43.0
next prev parent reply other threads:[~2025-02-20 9:40 UTC|newest]
Thread overview: 36+ messages / expand[flat|nested] mbox.gz Atom feed top
2025-02-20 9:32 [RFC PATCH 00/22] sched/fair: Defer CFS throttling to exit to user mode K Prateek Nayak
2025-02-20 9:32 ` [RFC PATCH 01/22] kernel/entry/common: Move syscall_enter_from_user_mode_work() out of header K Prateek Nayak
2025-02-20 10:43 ` Peter Zijlstra
2025-02-20 10:56 ` K Prateek Nayak
2025-02-20 9:32 ` [RFC PATCH 02/22] sched/fair: Convert "se->runnable_weight" to unsigned int and pack the struct K Prateek Nayak
2025-02-20 9:32 ` [RFC PATCH 03/22] [PoC] kernel/entry/common: Mark syscall as a kernel critical section K Prateek Nayak
2025-02-20 9:32 ` [RFC PATCH 04/22] [PoC] kernel/sched: Inititalize "kernel_cs_count" for new tasks K Prateek Nayak
2025-02-20 9:32 ` [RFC PATCH 05/22] sched/fair: Track EEVDF stats for entities preempted in kernel mode K Prateek Nayak
2025-02-20 9:32 ` [RFC PATCH 06/22] sched/fair: Propagate the min_vruntime of kernel mode preempted entity K Prateek Nayak
2025-02-20 9:32 ` [RFC PATCH 07/22] sched/fair: Propagate preempted entity information up cgroup hierarchy K Prateek Nayak
2025-02-20 9:32 ` [RFC PATCH 08/22] sched/fair: Allow pick_eevdf() to pick in-kernel entities on throttled hierarchy K Prateek Nayak
2025-02-20 9:32 ` [RFC PATCH 09/22] sched/fair: Introduce cfs_rq throttled states in preparation for partial throttling K Prateek Nayak
2025-02-20 9:32 ` [RFC PATCH 10/22] sched/fair: Prepare throttle_cfs_rq() to allow " K Prateek Nayak
2025-02-20 9:32 ` [RFC PATCH 11/22] sched/fair: Prepare unthrottle_cfs_rq() to demote throttle status K Prateek Nayak
2025-02-20 9:32 ` [RFC PATCH 12/22] sched/fair: Prepare bandwidth distribution to unthrottle partial throttles right away K Prateek Nayak
2025-02-20 9:32 ` [RFC PATCH 13/22] sched/fair: Correct the throttle status supplied to pick_eevdf() K Prateek Nayak
2025-02-20 9:32 ` [RFC PATCH 14/22] sched/fair: Mark a task if it was picked on a partially throttled hierarchy K Prateek Nayak
2025-02-20 9:32 ` [RFC PATCH 15/22] sched/fair: Call resched_curr() from sched_notify_syscall_exit() K Prateek Nayak
2025-02-20 9:32 ` [RFC PATCH 16/22] sched/fair: Prepare enqueue to partially unthrottle cfs_rq K Prateek Nayak
2025-02-20 9:32 ` [RFC PATCH 17/22] sched/fair: Clear pick on throttled indicator when task leave fair class K Prateek Nayak
2025-02-20 9:32 ` [RFC PATCH 18/22] sched/fair: Prepare pick_next_task_fair() to unthrottle a throttled hierarchy K Prateek Nayak
2025-02-20 9:32 ` [RFC PATCH 19/22] sched/fair: Ignore in-kernel indicators for running task outside of schedule() K Prateek Nayak
2025-02-20 9:32 ` [RFC PATCH 20/22] sched/fair: Implement determine_throttle_state() for partial throttle K Prateek Nayak
2025-02-20 9:32 ` K Prateek Nayak [this message]
2025-02-20 9:32 ` [RFC PATCH 22/22] [DEBUG] sched/fair: Debug pick_eevdf() returning NULL! K Prateek Nayak
2025-02-20 10:55 ` [RFC PATCH 00/22] sched/fair: Defer CFS throttling to exit to user mode Peter Zijlstra
2025-02-20 11:18 ` K Prateek Nayak
2025-02-20 11:32 ` Peter Zijlstra
2025-02-20 12:04 ` K Prateek Nayak
2025-02-21 2:04 ` Josh Don
2025-02-21 3:37 ` K Prateek Nayak
2025-02-21 19:42 ` Josh Don
2025-02-20 15:40 ` Valentin Schneider
2025-02-20 16:58 ` K Prateek Nayak
2025-02-21 1:47 ` Josh Don
2025-02-25 21:13 ` Valentin Schneider
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=20250220093257.9380-22-kprateek.nayak@amd.com \
--to=kprateek.nayak@amd.com \
--cc=bigeasy@linutronix.de \
--cc=brho@google.com \
--cc=bsegall@google.com \
--cc=clrkwllms@kernel.org \
--cc=dietmar.eggemann@arm.com \
--cc=dvernet@meta.com \
--cc=frederic@kernel.org \
--cc=gautham.shenoy@amd.com \
--cc=joshdon@google.com \
--cc=juri.lelli@redhat.com \
--cc=linux-kernel@vger.kernel.org \
--cc=linux-rt-devel@lists.linux.dev \
--cc=luto@kernel.org \
--cc=mgorman@suse.de \
--cc=mingo@redhat.com \
--cc=paulmck@kernel.org \
--cc=peterz@infradead.org \
--cc=pmladek@suse.com \
--cc=qyousef@layalina.io \
--cc=rostedt@goodmis.org \
--cc=swapnil.sapkal@amd.com \
--cc=tglx@linutronix.de \
--cc=tj@kernel.org \
--cc=vincent.guittot@linaro.org \
--cc=vschneid@redhat.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®