sched: Various reweight_entity() fixes
Subsystems (2)
Peter Zijlstra
maintainerv2 cover sched: Various reweight_entity() fixes
Hi,
So what started out as a few reweight fixies, turned into a a few more patches, but it looks to be solid now.
Thanks for all the testing!
The plan is to stick the first 4 patches (those with a Fixes tag) into tip/sched/urgent and the rest into tip/sched/core right after -rc1.
These patches have been in queue/sched/core for about a week now, but I'll wipe that tree to start staging stuff for the post -rc1 tip trees.
Peter Zijlstra
maintainerPATCH v2 1/7 sched/fair: Fix zero_vruntime tracking
It turns out that zero_vruntime tracking is broken when there is but a single task running. Current update paths are through __{en,de}queue_entity(), and when there is but a single task, pick_next_task() will always return that one task, and put_prev_set_next_task() will end up in neither function.
This can cause entity_key() to grow indefinitely large and cause overflows, leading to much pain and suffering.
Furtermore, doing update_zero_vruntime() from __{de,en}queue_entity(), which are called from {set_next,put_prev}_entity() has problems because:
- set_next_entity() calls __dequeue_entity() before it does cfs_rq->curr = se. This means the avg_vruntime() will see the removal but not current, missing the entity for accounting.
- put_prev_entity() calls __enqueue_entity() before it does cfs_rq->curr = NULL. This means the avg_vruntime() will see the addition *and* current, leading to double accounting.
Both cases are incorrect/inconsistent.
Noting that avg_vruntime is already called on each {en,de}queue, remove the explicit avg_vruntime() calls (which removes an extra 64bit division for each {en,de}queue) and have avg_vruntime() update zero_vruntime itself.
Additionally, have the tick call avg_vruntime() -- discarding the result, but for the side-effect of updating zero_vruntime.
While there, optimize avg_vruntime() by noting that the average of one value is rather trivial to compute.
Test case:
# taskset -c -p 1 $$
# taskset -c 2 bash -c 'while :; do :; done&'
# cat /sys/kernel/debug/sched/debug | awk '/^cpu#/ {P=0} /^cpu#2,/ {P=1} {if (P) print $0}' | grep -e zero_vruntime -e "^>"PRE:
.zero_vruntime : 31316.407903
Quoted 1 line
R bash 487 50787.345112 E 50789.145972 2.800000 50780.298364 16 120 0.000000 0.000000 0.000000 /
.zero_vruntime : 382548.253179
Quoted 1 line
R bash 487 427275.204288 E 427276.003584 2.800000 427268.157540 23 120 0.000000 0.000000 0.000000 /
POST:
.zero_vruntime : 17259.709467
Quoted 1 line
R bash 526 17259.709467 E 17262.509467 2.800000 16915.031624 9 120 0.000000 0.000000 0.000000 /
.zero_vruntime : 18702.723356
Quoted 1 line
R bash 526 18702.723356 E 18705.523356 2.800000 18358.045513 9 120 0.000000 0.000000 0.000000 /
--- kernel/sched/fair.c | 84 +++++++++++++++++++++++++++++++++++----------------- 1 file changed, 57 insertions(+), 27 deletions(-)
kernel/sched/fair.c +57 -27
@@ -589,6 +589,21 @@ static inline bool entity_before(const sreturn vruntime_cmp (a->deadline,"<" , b->deadline); } +/* +* Per avg_vruntime() below, cfs_rq::zero_vruntime is only slightly stale +* and this value should be no more than two lag bounds. Which puts it in the +* general order of: +* +* (slice + TICK_NSEC) << NICE_0_LOAD_SHIFT +* +* which is around 44 bits in size (on 64bit); that is 20 for +* NICE_0_LOAD_SHIFT, another 20 for NSEC_PER_MSEC and then a handful for +* however many msec the actual slice+tick ends up begin. +* +* (disregarding the actual divide-by-weight part makes for the worst case +* weight of 2, which nicely cancels vs the fuzz in zero_vruntime not actually +* being the zero-lag point). +*/ static inline s64 entity_key (struct cfs_rq *cfs_rq,struct sched_entity *se) {return vruntime_op (se->vruntime,"-" , cfs_rq->zero_vruntime);
@@ -676,39 +691,61 @@ sum_w_vruntime_sub(struct cfs_rq *cfs_rq }static inline -void sum_w_vruntime_update (struct cfs_rq *cfs_rq,s64 delta) +void update_zero_vruntime (struct cfs_rq *cfs_rq,s64 delta) {/* -* v' = v + d ==> sum_w_vruntime' = sum_runtime - d*sum_weight +* v' = v + d ==> sum_w_vruntime' = sum_w_vruntime - d*sum_weight */ cfs_rq->sum_w_vruntime -= cfs_rq->sum_weight * delta; + cfs_rq->zero_vruntime += delta; }/* -* Specifically: avg_runtime() + 0 must result in entity_eligible() := true +* Specifically: avg_vruntime() + 0 must result in entity_eligible() := true * For this to be so, the result of this function must have a left bias. +* +* Called in: +* - place_entity() -- before enqueue +* - update_entity_lag() -- before dequeue +* - entity_tick() +* +* This means it is one entry 'behind' but that puts it close enough to where +* the bound on entity_key() is at most two lag bounds. */ u64 avg_vruntime (struct cfs_rq *cfs_rq) {struct sched_entity *curr = cfs_rq->curr; -s64 avg = cfs_rq->sum_w_vruntime; -long load = cfs_rq->sum_weight; +long weight = cfs_rq->sum_weight; +s64 delta =0 ; -if (curr && curr->on_rq) { -unsigned long weight =scale_load_down (curr->load.weight); +if (curr && !curr->on_rq) + curr =NULL ; - avg +=entity_key (cfs_rq, curr) * weight; - load += weight; - } +if (weight) { +s64 runtime = cfs_rq->sum_w_vruntime; + +if (curr) { +unsigned long w =scale_load_down (curr->load.weight); + + runtime +=entity_key (cfs_rq, curr) * w; + weight += w; + } -if (load) {/* sign flips effective floor / ceiling */ -if (avg <0 ) - avg -= (load -1 ); - avg =div_s64 (avg, load); +if (runtime <0 ) + runtime -= (weight -1 ); + + delta =div_s64 (runtime, weight); + }else if (curr) { +/* +* When there is but one element, it is the average. +*/ + delta = curr->vruntime - cfs_rq->zero_vruntime; } -return cfs_rq->zero_vruntime + avg; +update_zero_vruntime (cfs_rq, delta); + +return cfs_rq->zero_vruntime; }/*
@@ -777,16 +814,6 @@ int entity_eligible(struct cfs_rq *cfs_rreturn vruntime_eligible (cfs_rq, se->vruntime); } -static void update_zero_vruntime (struct cfs_rq *cfs_rq) -{ -u64 vruntime =avg_vruntime (cfs_rq); -s64 delta =vruntime_op (vruntime,"-" , cfs_rq->zero_vruntime); - -sum_w_vruntime_update (cfs_rq, delta); - - cfs_rq->zero_vruntime = vruntime; -} -static inline u64 cfs_rq_min_slice (struct cfs_rq *cfs_rq) {struct sched_entity *root =__pick_root_entity (cfs_rq);
@@ -856,7 +883,6 @@ RB_DECLARE_CALLBACKS(static, min_vruntimstatic void __enqueue_entity (struct cfs_rq *cfs_rq,struct sched_entity *se) {sum_w_vruntime_add (cfs_rq, se); -update_zero_vruntime (cfs_rq); se->min_vruntime = se->vruntime; se->min_slice = se->slice; rb_add_augmented_cached(&se->run_node, &cfs_rq->tasks_timeline,
@@ -868,7 +894,6 @@ static void __dequeue_entity(struct cfs_rb_erase_augmented_cached (&se->run_node, &cfs_rq->tasks_timeline, &min_vruntime_cb);sum_w_vruntime_sub (cfs_rq, se); -update_zero_vruntime (cfs_rq); }struct sched_entity *__pick_root_entity (struct cfs_rq *cfs_rq)
@@ -5524,6 +5549,11 @@ entity_tick(struct cfs_rq *cfs_rq, strucupdate_load_avg (cfs_rq, curr,UPDATE_TG );update_cfs_group (curr); +/* +* Pulls along cfs_rq::zero_vruntime. +*/ +avg_vruntime (cfs_rq); +#ifdef CONFIG_SCHED_HRTICK /* * queued ticks are scheduled to match the slice, so don't bother
Re: [PATCH v2 1/7] sched/fair: Fix zero_vruntime tracking
Quoted 46 lines · Peter Zijlstra
It turns out that
zero_vruntimetracking is broken when there is but a single task running. Current update paths are through __{en,de}queue_entity(), and when there is but a single task,pick_next_task()will always return that one task, andput_prev_set_next_task()will end up in neither function.This can cause
entity_key()to grow indefinitely large and cause overflows, leading to much pain and suffering.Furtermore, doing
update_zero_vruntime()from __{de,en}queue_entity(), which are called from {set_next,put_prev}_entity() has problems because:-
set_next_entity()calls__dequeue_entity()before it doescfs_rq->curr= se. This means theavg_vruntime()will see the removal but not current, missing the entity for accounting.-
put_prev_entity()calls__enqueue_entity()before it doescfs_rq->curr= NULL. This means theavg_vruntime()will see the addition *and* current, leading to double accounting.Both cases are incorrect/inconsistent.
Noting that
avg_vruntimeis already called on each {en,de}queue, remove the explicitavg_vruntime()calls (which removes an extra 64bit division for each {en,de}queue) and haveavg_vruntime()updatezero_vruntimeitself.Additionally, have the tick call
avg_vruntime()-- discarding the result, but for the side-effect of updatingzero_vruntime.While there, optimize
avg_vruntime()by noting that the average of one value is rather trivial to compute.Test case:
# taskset -c -p 1 $$ # taskset -c 2 bash -c 'while :; do :; done&' # cat /sys/kernel/debug/sched/debug | awk '/^cpu#/ {P=0} /^cpu#2,/ {P=1} {if (P) print $0}' | grep -e zero_vruntime -e "^>"PRE:
.zero_vruntime : 31316.407903Quoted 1 line
R bash 487 50787.345112 E 50789.145972 2.800000 50780.298364 16 120 0.000000 0.000000 0.000000 /
.zero_vruntime : 382548.253179Quoted 1 line
R bash 487 427275.204288 E 427276.003584 2.800000 427268.157540 23 120 0.000000 0.000000 0.000000 /
POST:
.zero_vruntime : 17259.709467Quoted 1 line
R bash 526 17259.709467 E 17262.509467 2.800000 16915.031624 9 120 0.000000 0.000000 0.000000 /
Quoted 8 lines
.zero_vruntime : 18702.723356Quoted 1 line
R bash 526 18702.723356 E 18705.523356 2.800000 18358.045513 9 120 0.000000 0.000000 0.000000 /
Fixes 79f3f9bedd14 ("sched/eevdf: Fix min_vruntime vs avg_vruntime")Reported-by K Prateek Nayak <[email protected]>Signed-off-by Peter Zijlstra (Intel) <[email protected]>Tested-by K Prateek Nayak <[email protected]>Tested-by Shubhang Kaushik <[email protected]>
Quoted 152 lines
--- kernel/sched/fair.c | 84 +++++++++++++++++++++++++++++++++++----------------- 1 file changed, 57 insertions(+), 27 deletions(-)kernel/sched/fair.c +57
-27@@ -589,6 +589,21 @@ static inline bool entity_before(const sreturn vruntime_cmp (a->deadline,"<" , b->deadline); } +/* +* Per avg_vruntime() below, cfs_rq::zero_vruntime is only slightly stale +* and this value should be no more than two lag bounds. Which puts it in the +* general order of: +* +* (slice + TICK_NSEC) << NICE_0_LOAD_SHIFT +* +* which is around 44 bits in size (on 64bit); that is 20 for +* NICE_0_LOAD_SHIFT, another 20 for NSEC_PER_MSEC and then a handful for +* however many msec the actual slice+tick ends up begin. +* +* (disregarding the actual divide-by-weight part makes for the worst case +* weight of 2, which nicely cancels vs the fuzz in zero_vruntime not actually +* being the zero-lag point). +*/ static inline s64 entity_key (struct cfs_rq *cfs_rq,struct sched_entity *se) {return vruntime_op (se->vruntime,"-" , cfs_rq->zero_vruntime);@@ -676,39 +691,61 @@ sum_w_vruntime_sub(struct cfs_rq *cfs_rq }static inline -void sum_w_vruntime_update (struct cfs_rq *cfs_rq,s64 delta) +void update_zero_vruntime (struct cfs_rq *cfs_rq,s64 delta) {/* -* v' = v + d ==> sum_w_vruntime' = sum_runtime - d*sum_weight +* v' = v + d ==> sum_w_vruntime' = sum_w_vruntime - d*sum_weight */ cfs_rq->sum_w_vruntime -= cfs_rq->sum_weight * delta; + cfs_rq->zero_vruntime += delta; }/* -* Specifically: avg_runtime() + 0 must result in entity_eligible() := true +* Specifically: avg_vruntime() + 0 must result in entity_eligible() := true * For this to be so, the result of this function must have a left bias. +* +* Called in: +* - place_entity() -- before enqueue +* - update_entity_lag() -- before dequeue +* - entity_tick() +* +* This means it is one entry 'behind' but that puts it close enough to where +* the bound on entity_key() is at most two lag bounds. */ u64 avg_vruntime (struct cfs_rq *cfs_rq) {struct sched_entity *curr = cfs_rq->curr; -s64 avg = cfs_rq->sum_w_vruntime; -long load = cfs_rq->sum_weight; +long weight = cfs_rq->sum_weight; +s64 delta =0 ; -if (curr && curr->on_rq) { -unsigned long weight =scale_load_down (curr->load.weight); +if (curr && !curr->on_rq) + curr =NULL ; - avg +=entity_key (cfs_rq, curr) * weight; - load += weight; - } +if (weight) { +s64 runtime = cfs_rq->sum_w_vruntime; + +if (curr) { +unsigned long w =scale_load_down (curr->load.weight); + + runtime +=entity_key (cfs_rq, curr) * w; + weight += w; + } -if (load) {/* sign flips effective floor / ceiling */ -if (avg <0 ) - avg -= (load -1 ); - avg =div_s64 (avg, load); +if (runtime <0 ) + runtime -= (weight -1 ); + + delta =div_s64 (runtime, weight); + }else if (curr) { +/* +* When there is but one element, it is the average. +*/ + delta = curr->vruntime - cfs_rq->zero_vruntime; } -return cfs_rq->zero_vruntime + avg; +update_zero_vruntime (cfs_rq, delta); + +return cfs_rq->zero_vruntime; }/* @@ -777,16 +814,6 @@ int entity_eligible(struct cfs_rq *cfs_rreturn vruntime_eligible (cfs_rq, se->vruntime); } -static void update_zero_vruntime (struct cfs_rq *cfs_rq) -{ -u64 vruntime =avg_vruntime (cfs_rq); -s64 delta =vruntime_op (vruntime,"-" , cfs_rq->zero_vruntime); - -sum_w_vruntime_update (cfs_rq, delta); - - cfs_rq->zero_vruntime = vruntime; -} -static inline u64 cfs_rq_min_slice (struct cfs_rq *cfs_rq) {struct sched_entity *root =__pick_root_entity (cfs_rq);@@ -856,7 +883,6 @@ RB_DECLARE_CALLBACKS(static, min_vruntimstatic void __enqueue_entity (struct cfs_rq *cfs_rq,struct sched_entity *se) {sum_w_vruntime_add (cfs_rq, se); -update_zero_vruntime (cfs_rq); se->min_vruntime = se->vruntime; se->min_slice = se->slice; rb_add_augmented_cached(&se->run_node, &cfs_rq->tasks_timeline,@@ -868,7 +894,6 @@ static void __dequeue_entity(struct cfs_rb_erase_augmented_cached (&se->run_node, &cfs_rq->tasks_timeline, &min_vruntime_cb);sum_w_vruntime_sub (cfs_rq, se); -update_zero_vruntime (cfs_rq); }struct sched_entity *__pick_root_entity (struct cfs_rq *cfs_rq)@@ -5524,6 +5549,11 @@ entity_tick(struct cfs_rq *cfs_rq, strucupdate_load_avg (cfs_rq, curr,UPDATE_TG );update_cfs_group (curr); +/* +* Pulls along cfs_rq::zero_vruntime. +*/ +avg_vruntime (cfs_rq); +#ifdef CONFIG_SCHED_HRTICK /* * queued ticks are scheduled to match the slice, so don't bother
Dietmar Eggemann
reviewerRe: [PATCH v2 1/7] sched/fair: Fix zero_vruntime tracking
In reply to Peter ZijlstraQuoted 4 lines · Peter Zijlstra
It turns out that
zero_vruntimetracking is broken when there is but a single task running. Current update paths are through __{en,de}queue_entity(), and when there is but a single task,pick_next_task()will always return that one task, andput_prev_set_next_task()will end up in neither function.
Tried hard but I don't get the last clause.
[...]
Quoted 3 lines
While there, optimize
avg_vruntime()by noting that the average of one value is rather trivial to compute.
nitpick:
Quoted 4 lines
Test case:
# taskset -c -p 1 $$ # taskset -c 2 bash -c 'while :; do :; done&' # cat /sys/kernel/debug/sched/debug | awk '/^cpu#/ {P=0} /^cpu#2,/ {P=1} {if (P) print $0}' | grep -e zero_vruntime -e "^>"
^
|
Worksonly w/o this comma for me.
[...]
Peter Zijlstra
maintainerRe: [PATCH v2 1/7] sched/fair: Fix zero_vruntime tracking
Quoted 7 lines · Dietmar Eggemann
Quoted 4 lines · Peter Zijlstra
It turns out that
zero_vruntimetracking is broken when there is but a single task running. Current update paths are through __{en,de}queue_entity(), and when there is but a single task,pick_next_task()will always return that one task, andput_prev_set_next_task()will end up in neither function.Tried hard but I don't get the last clause.
When prev==next, then put_prev_set_next_task() bails out and we'll never hit __enqueue_entity()/__dequeue_entity().
Quoted 8 lines
[...]
Quoted 3 lines
While there, optimize
avg_vruntime()by noting that the average of one value is rather trivial to compute.nitpick:
Quoted 8 lines
Quoted 4 lines
Test case:
# taskset -c -p 1 $$ # taskset -c 2 bash -c 'while :; do :; done&' # cat /sys/kernel/debug/sched/debug | awk '/^cpu#/ {P=0} /^cpu#2,/ {P=1} {if (P) print $0}' | grep -e zero_vruntime -e "^>"^ | Worksonly w/o this comma for me.
Hmm, weird, for me:
cat /sys/kernel/debug/sched/debug | grep ^cpu#2
cpu#2, 2500.000 MHz
cpu#20, 2500.000 MHz
cpu#21, 2500.000 MHz
cpu#22, 2500.000 MHz
cpu#23, 2500.000 MHz
cpu#24, 2500.000 MHz
cpu#25, 2500.000 MHz
cpu#26, 2500.000 MHz
cpu#27, 2500.000 MHz
cpu#28, 2500.000 MHz
cpu#29, 2500.000 MHz
And that ',' was added because otherwise it would match the full 20 range of CPUs too, which was not intended ;-)
Dietmar Eggemann
reviewerRe: [PATCH v2 1/7] sched/fair: Fix zero_vruntime tracking
Quoted 11 lines · Peter Zijlstra
Quoted 7 lines · Dietmar Eggemann
Quoted 4 lines · Peter Zijlstra
It turns out that
zero_vruntimetracking is broken when there is but a single task running. Current update paths are through __{en,de}queue_entity(), and when there is but a single task,pick_next_task()will always return that one task, andput_prev_set_next_task()will end up in neither function.Tried hard but I don't get the last clause.
When prev==next, then
put_prev_set_next_task()bails out and we'll never hit __enqueue_entity()/__dequeue_entity().
Ah, I see. But IMHO put_prev_set_next_task() is never called for the testcase below (CPU hog is prev and next in put_prev_set_next_task())
But (prev != p) in pick_next_task_fair() is avoided ?
pick_next_task_fair()
if (prev != p) {
while (!is_same_group())
put_prev_entity()
set_next_entity()
put_prev_entity()
set_next_entity()
}[...]
Quoted 24 lines
Quoted 8 lines
Quoted 4 lines
Test case:
# taskset -c -p 1 $$ # taskset -c 2 bash -c 'while :; do :; done&' # cat /sys/kernel/debug/sched/debug | awk '/^cpu#/ {P=0} /^cpu#2,/ {P=1} {if (P) print $0}' | grep -e zero_vruntime -e "^>"^ | Worksonly w/o this comma for me.
Hmm, weird, for me:
cat
/sys/kernel/debug/sched/debug| grep ^cpu#2
cpu#2, 2500.000 MHz
cpu#20, 2500.000 MHz
cpu#21, 2500.000 MHz
cpu#22, 2500.000 MHz
cpu#23, 2500.000 MHz
cpu#24, 2500.000 MHz
cpu#25, 2500.000 MHz
cpu#26, 2500.000 MHz
cpu#27, 2500.000 MHz
cpu#28, 2500.000 MHz
cpu#29, 2500.000 MHz
Quoted 2 lines
And that ',' was added because otherwise it would match the full 20 range of CPUs too, which was not intended ;-)
Ah, the ', X Mhz' thing is X86 specific.
awk '/^cpu#/ {P=0} /^cpu#2(,|$)/ {P=1} {if (P) print $0}'
works on Arm64 as well.
Peter Zijlstra
maintainerRe: [PATCH v2 1/7] sched/fair: Fix zero_vruntime tracking
Quoted 20 lines · Dietmar Eggemann
Quoted 11 lines · Peter Zijlstra
Quoted 7 lines · Dietmar Eggemann
Quoted 4 lines · Peter Zijlstra
It turns out that
zero_vruntimetracking is broken when there is but a single task running. Current update paths are through __{en,de}queue_entity(), and when there is but a single task,pick_next_task()will always return that one task, andput_prev_set_next_task()will end up in neither function.Tried hard but I don't get the last clause.
When prev==next, then
put_prev_set_next_task()bails out and we'll never hit __enqueue_entity()/__dequeue_entity().Ah, I see. But IMHO
put_prev_set_next_task()is never called for the testcase below (CPU hog is prev and next input_prev_set_next_task())But (prev != p) in
pick_next_task_fair()is avoided ?
pick_next_task_fair()
Quoted 10 lines
if (prev != p) {
while (!is_same_group())
put_prev_entity()
set_next_entity()
put_prev_entity()
set_next_entity()
}Ah yes, pick_next_task_fair() open codes that. Also, I might have a patch to 'fix' all that, but I've not goten around to posting that. There's still a few wobblies in that part of the pile :/
Look at the top 3 patches in queue/sched/flat if you're up for it :-)
Re: [PATCH v2 1/7] sched/fair: Fix zero_vruntime tracking
In reply to Peter ZijlstraQuoted 20 lines · Peter Zijlstra
It turns out that
zero_vruntimetracking is broken when there is but a single task running. Current update paths are through __{en,de}queue_entity(), and when there is but a single task,pick_next_task()will always return that one task, andput_prev_set_next_task()will end up in neither function.This can cause
entity_key()to grow indefinitely large and cause overflows, leading to much pain and suffering.Furtermore, doing
update_zero_vruntime()from __{de,en}queue_entity(), which are called from {set_next,put_prev}_entity() has problems because:-
set_next_entity()calls__dequeue_entity()before it doescfs_rq->curr= se. This means theavg_vruntime()will see the removal but not current, missing the entity for accounting.-
put_prev_entity()calls__enqueue_entity()before it doescfs_rq->curr= NULL. This means theavg_vruntime()will see the addition *and* current, leading to double accounting.
Quoted 8 lines
Both cases are incorrect/inconsistent.
Noting that
avg_vruntimeis already called on each {en,de}queue, remove the explicitavg_vruntime()calls (which removes an extra 64bit division for each {en,de}queue) and haveavg_vruntime()updatezero_vruntimeitself.Additionally, have the tick call
avg_vruntime()-- discarding the result, but for the side-effect of updatingzero_vruntime.
Hey all,
So in stress testing with my full proxy-exec series, I was occasionally tripping over the situation where __pick_eevdf() returns null which quickly crashes.
Initially I was thinking the bug was in my out of tree patches, but I later found I could trip it with upstream as well, and I believe I have bisected it down to this patch. Though reproduction often takes 3-4 hours, and I usually quit testing after 5 hours, so it's possible I have some false negatives on the problem and it could have arisen earlier.
From a little bit of debugging (done with the full proxy exec series, I need to re-debug with vanilla), usual symptom is that we run into a situation where !entity_eligible(cfs_rq, curr), so curr gets set to null (though in one case, I saw cfs_rq->curr start as null), and then we never set best, and thus the if (!best || ...) best = curr; assignment doesn't save us and we return null, and crash.
I still need to dig more into the eligibility values and also to dump the rq to see why nothing is being found. I am running with CONFIG_SCHED_PROXY_EXEC enabled, so there may yet be some collision here between this change and the already upstream portions of Proxy Exec (I'll have to do more testing to see if it reproduces without that option enabled).
The backtrace is usually due to stress-ng stress-ng-yield test:
[ 3775.898617] BUG: kernel NULL pointer dereference, address: 0000000000000059 [ 3775.903089] #PF: supervisor read access in kernel mode [ 3775.906068] #PF: error_code(0x0000) - not-present page [ 3775.909102] PGD 0 P4D 0 [ 3775.910656] Oops: Oops: 0000 [#1] SMP NOPTI [ 3775.913371] CPU: 36 UID: 0 PID: 269131 Comm: stress-ng-yield Tainted: G W 7.0.0-rc5-00001-g42a93b71138f #5 PREEMPT(full) [ 3775.920304] Tainted: [W]=WARN [ 3775.922100] Hardware name: QEMU Standard PC (i440FX + PIIX, 1996), BIOS 1.17.0-debian-1.17.0-1 04/01/2014 [ 3775.927852] RIP: 0010:pick_task_fair+0x6f/0xb0 [ 3775.930466] Code: 85 ff 74 52 48 8b 47 48 48 85 c0 74 d6 80 78 58 00 74 d0 48 89 3c 24 e8 8f 9b ff ff 48 8b 3c 24 be 01 00 00 00 e8 51 74 ff ff <80> 78 59 00 74 c3 ba 21 00 00 00 48 89 c6 48 89 df e8 5b f1 ff ff [ 3775.941027] RSP: 0018:ffffc9003827fde0 EFLAGS: 00010086 [ 3775.943949] RAX: 0000000000000000 RBX: ffff8881b972bc40 RCX: 0000000000000803 [ 3775.948179] RDX: 00000041acc1002a RSI: 000000b0cef5382a RDI: 000040138cc6cd49 [ 3775.952149] RBP: ffffc9003827fef8 R08: 0000000000000400 R09: 0000000000000002 [ 3775.956548] R10: 0000000000000024 R11: ffff8881b04a4d40 R12: ffff8881b04a4280 [ 3775.960480] R13: ffff8881b04a4280 R14: ffffffff82ce70a8 R15: ffff8881b972bc40 [ 3775.964713] FS: 00007f6ecb7a6b00(0000) GS:ffff888235beb000(0000) knlGS:0000000000000000 [ 3775.969468] CS: 0010 DS: 0000 ES: 0000 CR0: 0000000080050033 [ 3775.972960] CR2: 0000000000000059 CR3: 000000019c32a003 CR4: 0000000000370ef0 [ 3775.977008] Call Trace: [ 3775.978581] <TASK> [ 3775.979841] pick_next_task_fair+0x3c/0x8e0 [ 3775.982408] ? lock_is_held_type+0xcd/0x130 [ 3775.984833] __schedule+0x20f/0x14d0 [ 3775.987287] ? do_sched_yield+0xa2/0xe0 [ 3775.989365] schedule+0x3d/0x130 [ 3775.991376] __do_sys_sched_yield+0xe/0x20 [ 3775.993889] do_syscall_64+0xf3/0x680 [ 3775.996229] entry_SYSCALL_64_after_hwframe+0x77/0x7f [ 3776.000459] RIP: 0033:0x7f6ecc0e18c7 [ 3776.002757] Code: 73 01 c3 48 8b 0d 49 d5 0e 00 f7 d8 64 89 01 48
83 c8 ff c3 66 2e 0f 1f 84 00 00 00 00 00 0f 1f 44 00 00 b8 18 00 00 00 0f 05 <48> 3d 01 f0 ff
ff 73 01 c3 48 8b 0d 19 d5 0e 00 f7 d8 64 89 01 48
I'll continue digging next week on this, but wanted to share in case anyone else sees something obvious first.
thanks
-john
Steven Rostedt
reviewerRe: [PATCH v2 1/7] sched/fair: Fix zero_vruntime tracking
Quoted 2 lines · On Fri, 27 Mar 2026 22:44:28 -0700 John Stultz <[email protected]> wrote:
I'll continue digging next week on this, but wanted to share in case anyone else sees something obvious first.
FYI, you can add a trace_printk() around all the areas that assign cfs_rq->curr, and if you use the persistent ring buffer you can retrieve the output of all the events that lead up to the crash.
Add to the kernel command line:
reserve_mem=100M:12M:trace trace_instance=boot_mapped^traceprintk^traceoff@trace
And before starting your testing:
echo 1 > /sys/kernel/tracing/instances/boot_mapped/tracing_on
If all goes well, after the crash you should see the output in:
cat /sys/kernel/tracing/instances/boot_mapped/trace
-- Steve
Re: [PATCH v2 1/7] sched/fair: Fix zero_vruntime tracking
Quoted 15 lines · Steven Rostedt
Quoted 2 lines · On Fri, 27 Mar 2026 22:44:28 -0700 John Stultz <[email protected]> wrote:
I'll continue digging next week on this, but wanted to share in case anyone else sees something obvious first.
FYI, you can add a
trace_printk()around all the areas that assigncfs_rq->curr, and if you use the persistent ring buffer you can retrieve the output of all the events that lead up to the crash.Add to the kernel command line:
reserve_mem=100M:12M:trace trace_instance=boot_mapped^traceprintk^traceoff@trace
Quoted 7 lines
And before starting your testing:
echo 1 >
/sys/kernel/tracing/instances/boot_mapped/tracing_onIf all goes well, after the crash you should see the output in:
cat
/sys/kernel/tracing/instances/boot_mapped/trace
Nice. I've actually been using ftrace_dump_on_oops as I log the VM serial console to a file and don't have to remember to go fetch it out the next time. But this is helpful when its on real hardware (dumping the trace over serial console can take awhile and I've had cases where the hardware watchdogs reboot the device midway when the trace is too large).
thanks
-john
Steven Rostedt
reviewerRe: [PATCH v2 1/7] sched/fair: Fix zero_vruntime tracking
Quoted 7 lines · On Mon, 30 Mar 2026 10:58:54 -0700 John Stultz <[email protected]> wrote:
Nice. I've actually been using
ftrace_dump_on_oopsas I log the VM serial console to a file and don't have to remember to go fetch it out the next time. But this is helpful when its on real hardware (dumping the trace over serial console can take awhile and I've had cases where the hardware watchdogs reboot the device midway when the trace is too large).
I use it on VMs all the time. It works nicely with qemu.
In the near future we will have a backup buffer implementation too, where you don't need to remember to start it!
reserve_mem=100M:12M:trace trace_instance=boot_mapped^traceprintk^@trace trace_instance=backup=boot_mapped
Where on early boot up, a "backup" instance is created and copies the persistent ring buffer to a read-only temporary buffer that doesn't get overwritten.
Then you can keep the persistent ring buffer always on, and if there's a crash, just look at the "backup" instance to see what happened.
-- Steve
Peter Zijlstra
maintainerRe: [PATCH v2 1/7] sched/fair: Fix zero_vruntime tracking
In reply to John StultzQuoted 1 line · John Stultz
The backtrace is usually due to stress-ng stress-ng-yield test:
What actual stress-ng parameters are that, and what kind of VM are you running?
Re: [PATCH v2 1/7] sched/fair: Fix zero_vruntime tracking
Quoted 7 lines · Peter Zijlstra
Quoted 1 line · John Stultz
The backtrace is usually due to stress-ng stress-ng-yield test:
What actual stress-ng parameters are that, and what kind of VM are you running?
Just running in a loop:
stress-ng --class scheduler --all 1 --timeout 300
I usually also run with locktorture using the following boot args:
torture.random_shuffle=1 locktorture.writer_fifo=1 locktorture.torture_type=mutex_lock locktorture.nested_locks=8 locktorture.rt_boost=1 locktorture.rt_boost_factor=50 locktorture.stutter=0
As well as cyclictest -t -p99 and my prio-inversion-demo in a loop in the background, but I suspect they aren't necessary here.
This all on a nested VM w/ 64 vCPUs (host has 96 vCPUs).
Over the weekend I did run with CONFIG_SCHED_PROXY_EXEC disabled, and still tripped the problem. I've added some trace_printks back in and am working to get more details.
thanks
-john
Peter Zijlstra
maintainerRe: [PATCH v2 1/7] sched/fair: Fix zero_vruntime tracking
In reply to John StultzQuoted 30 lines · John Stultz
Quoted 20 lines · Peter Zijlstra
It turns out that
zero_vruntimetracking is broken when there is but a single task running. Current update paths are through __{en,de}queue_entity(), and when there is but a single task,pick_next_task()will always return that one task, andput_prev_set_next_task()will end up in neither function.This can cause
entity_key()to grow indefinitely large and cause overflows, leading to much pain and suffering.Furtermore, doing
update_zero_vruntime()from __{de,en}queue_entity(), which are called from {set_next,put_prev}_entity() has problems because:-
set_next_entity()calls__dequeue_entity()before it doescfs_rq->curr= se. This means theavg_vruntime()will see the removal but not current, missing the entity for accounting.-
put_prev_entity()calls__enqueue_entity()before it doescfs_rq->curr= NULL. This means theavg_vruntime()will see the addition *and* current, leading to double accounting.Quoted 8 lines
Both cases are incorrect/inconsistent.
Noting that
avg_vruntimeis already called on each {en,de}queue, remove the explicitavg_vruntime()calls (which removes an extra 64bit division for each {en,de}queue) and haveavg_vruntime()updatezero_vruntimeitself.Additionally, have the tick call
avg_vruntime()-- discarding the result, but for the side-effect of updatingzero_vruntime.
Quoted 7 lines
Hey all,
So in stress testing with my full proxy-exec series, I was occasionally tripping over the situation where
__pick_eevdf()returns null which quickly crashes.The backtrace is usually due to stress-ng stress-ng-yield test:
Suppose we have 2 runnable tasks, both doing yield. Then one will be eligible and one will not be, because the average position must be in between these two entities.
Therefore, the runnable task will be eligible, and be promoted a full slice (all the tasks do is yield after all). This causes it to jump over the other task and now the other task is eligible and it is no longer. So we schedule.
Since we are runnable, there is no dequeue or enqueue. All we have is the __enqueue_entity() and __dequeue_entity() from put_prev_task() / set_next_task(). But per the fingered commit, those two no longer move zero_vruntime head.
All that moves zero_vruntime is tick and full dequeue or enqueue.
This means, that if the two tasks playing leapfrog can reach the critical speed to reach the overflow point inside one tick's worth of time, we're up a creek.
If this is indeed the case, then the below should cure things.
This also means that running a HZ=100 config will increase the chances of hitting this vs HZ=1000.
kernel/sched/fair.c +1 -0
@@ -9307,6 +9307,7 @@ static void yield_task_fair(struct rq *rq)if (entity_eligible (cfs_rq, se)) { se->vruntime = se->deadline; se->deadline +=calc_delta_fair (se->slice, se); +avg_vruntime (cfs_rq); } }
Re: [PATCH v2 1/7] sched/fair: Fix zero_vruntime tracking
Hello Peter,
Quoted 5 lines · Peter Zijlstra
This means, that if the two tasks playing leapfrog can reach the critical speed to reach the overflow point inside one tick's worth of time, we're up a creek.
If this is indeed the case, then the below should cure things.
I have been running with this for four hours now and haven't seen any splats or crashes on my setup. I could reliably trigger the warning from __sum_w_vruntime_add() within an hour previously so it is safe to say I was hitting exactly this.
Feel free to include:
Signature · 2 lines
Thanks and Regards, Prateek
Peter Zijlstra
maintainerRe: [PATCH v2 1/7] sched/fair: Fix zero_vruntime tracking
Quoted 9 lines · K Prateek Nayak
Hello Peter,
Quoted 5 lines · Peter Zijlstra
This means, that if the two tasks playing leapfrog can reach the critical speed to reach the overflow point inside one tick's worth of time, we're up a creek.
If this is indeed the case, then the below should cure things.
Quoted 8 lines
I have been running with this for four hours now and haven't seen any splats or crashes on my setup. I could reliably trigger the warning from
__sum_w_vruntime_add()within an hour previously so it is safe to say I was hitting exactly this.Feel free to include:
Tested-by K Prateek Nayak <[email protected]>
Ha!, excellent. Thanks!
K Prateek Nayak
reviewerRe: [PATCH v2 1/7] sched/fair: Fix zero_vruntime tracking
Hello Peter,
Quoted 15 lines · Peter Zijlstra
Quoted 14 lines · K Prateek Nayak
Hello Peter,
Quoted 5 lines · Peter Zijlstra
This means, that if the two tasks playing leapfrog can reach the critical speed to reach the overflow point inside one tick's worth of time, we're up a creek.
If this is indeed the case, then the below should cure things.
I have been running with this for four hours now and haven't seen any splats or crashes on my setup. I could reliably trigger the warning from
__sum_w_vruntime_add()within an hour previously so it is safe to say I was hitting exactly this.
Quoted 5 lines
Quoted 3 lines
Feel free to include:
Tested-by K Prateek Nayak <[email protected]>Ha!, excellent. Thanks!
Turns out I spoke too soon and it did eventually run into that problem again and then eventually crashed in pick_task_fair() later so there is definitely something amiss still :-(
I'll throw in some debug traces and get back tomorrow.
Signature · 2 lines
Thanks and Regards, Prateek
Peter Zijlstra
maintainerRe: [PATCH v2 1/7] sched/fair: Fix zero_vruntime tracking
Quoted 22 lines · K Prateek Nayak
Hello Peter,
Quoted 19 lines · Peter Zijlstra
Quoted 17 lines · K Prateek Nayak
Hello Peter,
Quoted 5 lines · Peter Zijlstra
This means, that if the two tasks playing leapfrog can reach the critical speed to reach the overflow point inside one tick's worth of time, we're up a creek.
If this is indeed the case, then the below should cure things.
I have been running with this for four hours now and haven't seen any splats or crashes on my setup. I could reliably trigger the warning from
__sum_w_vruntime_add()within an hour previously so it is safe to say I was hitting exactly this.Feel free to include:
Tested-by K Prateek Nayak <[email protected]>
Quoted 7 lines
Quoted 1 line
Ha!, excellent. Thanks!
Turns out I spoke too soon and it did eventually run into that problem again and then eventually crashed in
pick_task_fair()later so there is definitely something amiss still :-(I'll throw in some debug traces and get back tomorrow.
Are there cgroups involved?
I'm thinking that if you have two groups, and the tick always hits the one group, the other group can go a while without ever getting updated.
But if there's no cgroups, this can't be it.
Anyway, something like the below would rule this out I suppose.
kernel/sched/fair.c +2 -5
@@ -1304,6 +1304,8 @@ static void update_curr(struct cfs_rq *cfs_rq) curr->vruntime +=calc_delta_fair (delta_exec, curr); resched =update_deadline (cfs_rq, curr); +if (resched) +avg_vruntime (cfs_rq);if (entity_is_task (curr)) {/*
@@ -5593,11 +5595,6 @@ entity_tick(struct cfs_rq *cfs_rq, struct sched_entity *curr, int queued)update_load_avg (cfs_rq, curr,UPDATE_TG );update_cfs_group (curr); -/* -* Pulls along cfs_rq::zero_vruntime. -*/ -avg_vruntime (cfs_rq); -#ifdef CONFIG_SCHED_HRTICK /* * queued ticks are scheduled to match the slice, so don't bother
K Prateek Nayak
reviewerRe: [PATCH v2 1/7] sched/fair: Fix zero_vruntime tracking
Hello Peter,
Quoted 7 lines · Peter Zijlstra
Quoted 5 lines
Turns out I spoke too soon and it did eventually run into that problem again and then eventually crashed in
pick_task_fair()later so there is definitely something amiss still :-(I'll throw in some debug traces and get back tomorrow.
Are there cgroups involved?
Indeed there are.
Quoted 3 lines
I'm thinking that if you have two groups, and the tick always hits the one group, the other group can go a while without ever getting updated.
Ack! That could be but I only have once cgroup on top of root cgroup as far as cpu controllers are concerned so the sched_yield() catching up the avg_vruntime() should have worked. Either ways, I have more data:
When I hit the overflow warning, I have:
se: entity_key(-83106064385) weight(90891264) overflow(-7553615238018032640)
cfs_rq: zero_vruntime(138430453113448575) sum_w_vruntime(0) sum_weight(0)
cfs_rq->curr: entity_key(0) vruntime(138430453113448575) deadline(138430500540426854)
Post avg_vruntime():
se: entity_key(-83106064385) weight(90891264) overflow(-7553615238018032640)
cfs_rq: zero_vruntime(138430453113448575) sum_w_vruntime(0) sum_weight(0)
cfs_rq->curr: entity_key(0) vruntime(138430453113448575) deadline(138430500540426854)so running avg_vruntime() doesn't make a difference and it seems to be a genuine case of place_entity() putting the newly woken entity pretty far back in the timeline. (I forgot to print weights!)
Now, the funny part is, if I leave the system undisturbed, I get a few of the above warning and nothing interesting but as soon as I do a:
grep bits /sys/kernel/debug/sched/debug
Boom! Pick fails very consistently (Because of copy-pasta this too doesn't contain weights):
NULL Pick!
cfs_rq: zero_vruntime(89029406877992895) sum_w_vruntime(-135049248768) sum_weight(1048576)
cfs_rq->curr: entity_key(149162) vruntime(89029406878142057) deadline(89029406976268435)
queued se: entity_key(-123294) vruntime(89029406877869601) deadline(89029406880669601)
after avg_vruntime()!
cfs_rq: zero_vruntime(89029406877868114) sum_w_vruntime(-4206886912) sum_weight(1048576)
cfs_rq->curr: entity_key(273943) vruntime(89029406878142057) deadline(89029406976268435)
queued se: entity_key(1487) vruntime(89029406877869601) deadline(89029406880669601)
NULL Pick!The above doesn't recover after a avg_vruntime(). Btw I'm running:
nice -n 19 stress-ng --yield 32 -t 1000000s&
while true; do perf bench sched messaging -p -t -l 100000 -g 16; done
Nice 19 is to get a large deadline and keep catching up to that deadline at every yield to see if that makes any difference.
Quoted 4 lines
But if there's no cgroups, this can't be it.
Anyway, something like the below would rule this out I suppose.
I'll add that in and see if it makes a difference. I'll add in weights and look at place_entity() to see if we have anything interesting going on there.
Thank you for taking a look.
Signature · 2 lines
Thanks and Regards, Prateek
K Prateek Nayak
reviewerRe: [PATCH v2 1/7] sched/fair: Fix zero_vruntime tracking
Quoted 50 lines · K Prateek Nayak
Quoted 2 lines
I'm thinking that if you have two groups, and the tick always hits the one group, the other group can go a while without ever getting updated.
Ack! That could be but I only have once cgroup on top of root cgroup as far as cpu controllers are concerned so the
sched_yield()catching up theavg_vruntime()should have worked. Either ways, I have more data:When I hit the overflow warning, I have:
se: entity_key(-83106064385) weight(90891264) overflow(-7553615238018032640) cfs_rq: zero_vruntime(138430453113448575) sum_w_vruntime(0) sum_weight(0) cfs_rq->curr: entity_key(0) vruntime(138430453113448575) deadline(138430500540426854) Post avg_vruntime(): se: entity_key(-83106064385) weight(90891264) overflow(-7553615238018032640) cfs_rq: zero_vruntime(138430453113448575) sum_w_vruntime(0) sum_weight(0) cfs_rq->curr: entity_key(0) vruntime(138430453113448575) deadline(138430500540426854)so running
avg_vruntime()doesn't make a difference and it seems to be a genuine case ofplace_entity()putting the newly woken entity pretty far back in the timeline. (I forgot to print weights!)Now, the funny part is, if I leave the system undisturbed, I get a few of the above warning and nothing interesting but as soon as I do a:
grep bits
/sys/kernel/debug/sched/debugBoom! Pick fails very consistently (Because of copy-pasta this too doesn't contain weights):
NULL Pick! cfs_rq: zero_vruntime(89029406877992895) sum_w_vruntime(-135049248768) sum_weight(1048576) cfs_rq->curr: entity_key(149162) vruntime(89029406878142057) deadline(89029406976268435) queued se: entity_key(-123294) vruntime(89029406877869601) deadline(89029406880669601) after avg_vruntime()! cfs_rq: zero_vruntime(89029406877868114) sum_w_vruntime(-4206886912) sum_weight(1048576) cfs_rq->curr: entity_key(273943) vruntime(89029406878142057) deadline(89029406976268435) queued se: entity_key(1487) vruntime(89029406877869601) deadline(89029406880669601) NULL Pick!The above doesn't recover after a
avg_vruntime(). Btw I'm running:nice -n 19 stress-ng --yield 32 -t 1000000s&
while true; do perf bench sched messaging -p -t -l 100000 -g 16; doneNice 19 is to get a large deadline and keep catching up to that deadline at every yield to see if that makes any difference.
Quoted 1 line
Quoted 7 lines
Quoted 3 lines
But if there's no cgroups, this can't be it.
Anyway, something like the below would rule this out I suppose.
I'll add that in and see if it makes a difference. I'll add in weights and look at
place_entity()to see if we have anything interesting going on there.
Still trips the issue :-( This time I have logs with weights.
For the warning:
se: entity_key(-72358759771) weight(90891264) warning_mul(-6576779137058540544) vlag(39009) delayed?(0)
cfs_rq: zero_vruntime(18695504496613622) sum_w_vruntime(0) sum_weight(0)
cfs_rq->curr: entity_key(0) vruntime(18695504496613622) deadline(18695540588878716) weight(49)
Post avg_vruntime():
se: entity_key(-72358759771) weight(90891264) overflow?(-6576779137058540544)
cfs_rq: zero_vruntime(18695504496613622) sum_w_vruntime(0) sum_weight(0)
cfs_rq->curr: entity_key(0) vruntime(18695504496613622) deadline(18695540588878716) weight(49)And the NULL pick while reading debugfs (probably something in the initial task wakeup path that trips it?):
NULL Pick!
cfs_rq: zero_vruntime(21126236598445952) sum_w_vruntime(-1074569456640) sum_weight(15360)
cfs_rq->curr: entity_key(69958950) vruntime(21126236668404902) deadline(21126236859551568) weight(15360)
queued se: entity_key(32498584) vruntime(21126236630944536) deadline(21126236822091202) weight(15360)
After avg_vruntime():
cfs_rq: zero_vruntime(21126236598445952) sum_w_vruntime(-1074569456640) sum_weight(15360)
cfs_rq->curr: entity_key(69958950) vruntime(21126236668404902) deadline(21126236859551568) weight(15360)
queued se: entity_key(32498584) vruntime(21126236630944536) deadline(21126236822091202) weight(15360)
NULL Pick!Updated zero_vruntime is behind that of either of the queued entities. Now that I have a reliable trigger for the crash, I'll just start tracing everything before I run grep (although I suspect something may have gone bad a long time ago but we can be hopeful)
Signature · 2 lines
Thanks and Regards, Prateek
Peter Zijlstra
maintainerRe: [PATCH v2 1/7] sched/fair: Fix zero_vruntime tracking
In reply to K Prateek NayakQuoted 4 lines · K Prateek Nayak
The above doesn't recover after a
avg_vruntime(). Btw I'm running:nice -n 19 stress-ng --yield 32 -t 1000000s&
while true; do perf bench sched messaging -p -t -l 100000 -g 16; done
And you're running that on a 16 cpu machine / vm ?
Peter Zijlstra
maintainerRe: [PATCH v2 1/7] sched/fair: Fix zero_vruntime tracking
Quoted 8 lines · Peter Zijlstra
Quoted 4 lines · K Prateek Nayak
The above doesn't recover after a
avg_vruntime(). Btw I'm running:nice -n 19 stress-ng --yield 32 -t 1000000s&
while true; do perf bench sched messaging -p -t -l 100000 -g 16; doneAnd you're running that on a 16 cpu machine / vm ?
W00t, it went b00m. Ok, let me go add some tracing.
K Prateek Nayak
reviewerRe: [PATCH v2 1/7] sched/fair: Fix zero_vruntime tracking
Quoted 11 lines · Peter Zijlstra
Quoted 8 lines · Peter Zijlstra
Quoted 4 lines · K Prateek Nayak
The above doesn't recover after a
avg_vruntime(). Btw I'm running:nice -n 19 stress-ng --yield 32 -t 1000000s&
while true; do perf bench sched messaging -p -t -l 100000 -g 16; doneAnd you're running that on a 16 cpu machine / vm ?
W00t, it went b00m. Ok, let me go add some tracing.
I could only repro it on baremetal after few hours but good to know it exploded effortlessly on your end! Was this a 16vCPU VM with the same recipe?
Signature · 2 lines
Thanks and Regards, Prateek
Peter Zijlstra
maintainerRe: [PATCH v2 1/7] sched/fair: Fix zero_vruntime tracking
Quoted 9 lines · K Prateek Nayak
Quoted 8 lines · Peter Zijlstra
Quoted 7 lines · Peter Zijlstra
Quoted 4 lines · K Prateek Nayak
The above doesn't recover after a
avg_vruntime(). Btw I'm running:nice -n 19 stress-ng --yield 32 -t 1000000s&
while true; do perf bench sched messaging -p -t -l 100000 -g 16; done
Quoted 7 lines
Quoted 3 lines
Quoted 1 line
And you're running that on a 16 cpu machine / vm ?
W00t, it went b00m. Ok, let me go add some tracing.
I could only repro it on baremetal after few hours but good to know it exploded effortlessly on your end! Was this a 16vCPU VM with the same recipe?
Yep. It almost insta triggers. Trying to make sense of the traces now.
Peter Zijlstra
maintainerRe: [PATCH v2 1/7] sched/fair: Fix zero_vruntime tracking
Quoted 12 lines · Peter Zijlstra
Quoted 11 lines · K Prateek Nayak
Quoted 10 lines · Peter Zijlstra
Quoted 8 lines · Peter Zijlstra
Quoted 4 lines · K Prateek Nayak
The above doesn't recover after a
avg_vruntime(). Btw I'm running:nice -n 19 stress-ng --yield 32 -t 1000000s&
while true; do perf bench sched messaging -p -t -l 100000 -g 16; doneAnd you're running that on a 16 cpu machine / vm ?
Quoted 7 lines
Quoted 5 lines
Quoted 1 line
W00t, it went b00m. Ok, let me go add some tracing.
I could only repro it on baremetal after few hours but good to know it exploded effortlessly on your end! Was this a 16vCPU VM with the same recipe?
Yep. It almost insta triggers. Trying to make sense of the traces now.
So the thing I'm seeing is that avg_vruntime() is behind of where it should be, not much, but every time it goes *boom* it is just far enough behind that no entity is eligible.
sched-messaging-2192 [039] d..2. 77.136100: pick_task_fair: cfs_rq(39:ff4a5bc7bebeb680): sum_w_vruntime(194325882) sum_weight(5120) zero_vruntime(105210161141318) avg_vruntime(105210161179272) sched-messaging-2192 [039] d..2. 77.136100: pick_task_fair: T se(ff4a5bc79040c940): vruntime(105210161556539) deadline(105210164099443) weight(1048576) -- sched-messaging:2340 sched-messaging-2192 [039] d..2. 77.136101: pick_task_fair: T se(ff4a5bc794ce98c0): vruntime(105210161435669) deadline(105210164235669) weight(1048576) -- sched-messaging:2212 sched-messaging-2192 [039] d..2. 77.136101: pick_task_fair: T se(ff4a5bc7952d3100): vruntime(105210161580240) deadline(105210164380240) weight(1048576) -- sched-messaging:2381 sched-messaging-2192 [039] d..2. 77.136102: pick_task_fair: T se(ff4a5bc794c318c0): vruntime(105210161818264) deadline(105210164518004) weight(1048576) -- sched-messaging:2306 sched-messaging-2192 [039] d..2. 77.136103: pick_task_fair: T se(ff4a5bc796b4b100): vruntime(105210161831546) deadline(105210164631546) weight(1048576) -- sched-messaging:2551 sched-messaging-2192 [039] d..2. 77.136104: pick_task_fair: min_lag(-652274) max_lag(0) limit(38000000) sched-messaging-2192 [039] d..2. 77.136104: pick_task_fair: picked NULL!!
If we compute the avg_vruntime() manually, then we get a sum_w_vruntime contribution for each task:
(105210161556539-105210161141318)*1024
425186304
(105210161435669-105210161141318)*1024
301415424
(105210161580240-105210161141318)*1024
449456128
(105210161818264-105210161141318)*1024
693192704
(105210161831546-105210161141318)*1024
706793472
Which combined is:
425186304+301415424+449456128+693192704+706793472
2576044032
NOTE: this is different (more) from sum_w_vruntime(194325882).
So divided, and added to zero gives:
2576044032/5120
503133.60000000000000000000
105210161141318+503133.60000000000000000000
105210161644451.60000000000000000000
Which is where avg_vruntime() *should* be, except it ends up being at:
avg_vruntime(105210161179272), which then results in no eligible entities.
Note that with the computed avg, the first 3 entities would be eligible.
This suggests I go build a parallel infrastructure to double check when and where this goes sizeways.
... various attempts later ....
sched-messaging-1021 [009] d..2. 34.483159: update_curr: T<=> se(ff37d0bcd52718c0): vruntime(56921690782736, E) deadline(56921693563331) weight(1048576) -- sched-messaging:1021 sched-messaging-1021 [009] d..2. 34.483160: __avg_vruntime: cfs_rq(9:ff37d0bcfe46b680): delta(-48327) sum_w_vruntime(811471242) zero_vruntime(56921691575188)
sched-messaging-1021 [009] d..2. 34.483160: pick_task_fair: cfs_rq(9:ff37d0bcfe46b680): sum_w_vruntime(811471242) sum_weight(6159) zero_vruntime(56921691575188) avg_vruntime(56921691706941) sched-messaging-1021 [009] d..2. 34.483160: pick_task_fair: T< se(ff37d0bcd5c6c940): vruntime(56921691276707, E) deadline(56921694076707) weight(1048576) -- sched-messaging:1276 sched-messaging-1021 [009] d..2. 34.483161: pick_task_fair: T se(ff37d0bcd56f98c0): vruntime(56921691917863) deadline(56921694079320) weight(1048576) -- sched-messaging:1201 sched-messaging-1021 [009] d..2. 34.483162: pick_task_fair: T se(ff37d0bcd5344940): vruntime(56921691340323, E) deadline(56921694140323) weight(1048576) -- sched-messaging:1036 sched-messaging-1021 [009] d..2. 34.483163: pick_task_fair: T se(ff37d0bcd56dc940): vruntime(56921691637185, E) deadline(56921694403038) weight(1048576) -- sched-messaging:1179 sched-messaging-1021 [009] d..2. 34.483164: pick_task_fair: T se(ff37d0bcd43eb100): vruntime(56921691629067, E) deadline(56921694429067) weight(1048576) -- sched-messaging:786 sched-messaging-1021 [009] d..2. 34.483164: pick_task_fair: T se(ff37d0bcd5d80080): vruntime(56921691810771) deadline(56921694610771) weight(1048576) -- sched-messaging:1291 sched-messaging-1021 [009] d..2. 34.483165: pick_task_fair: T se(ff37d0bcd027b100): vruntime(56921734696810) deadline(56921917287562) weight(15360) -- stress-ng-yield:693 sched-messaging-1021 [009] d..2. 34.483165: pick_task_fair: min_lag(-42989869) max_lag(430234) limit(38000000) sched-messaging-1021 [009] d..2. 34.483166: pick_task_fair: swv(811471242) sched-messaging-1021 [009] d..2. 34.483167: __dequeue_entity: cfs_rq(9:ff37d0bcfe46b680): sum_w_vruntime(1117115786) zero_vruntime(56921691575188)
set_next_task(1276):
swv -= key * weight
811471242 - (56921691276707-56921691575188)*1024
1117115786
OK
sched-messaging-1276 [009] d.h2. 34.483168: update_curr: T<=> se(ff37d0bcd5c6c940): vruntime(56921691285759, E) deadline(56921694076707) weight(1048576) -- sched-messaging:1276 sched-messaging-1276 [009] d.h2. 34.483169: __avg_vruntime: cfs_rq(9:ff37d0bcfe46b680): delta(22156) sum_w_vruntime(319064896) zero_vruntime(56921691597344)
swv -= sw * delta
1117115786 - 5135 * 22156
1003344726
WTF!?!
zv += delta
56921691575188 + 22156
56921691597344
OK
sched-messaging-1276 [009] d.h2. 34.483169: place_entity: T< se(ff37d0bcd52718c0): vruntime(56921690673139, E) deadline(56921693473139) weight(1048576) -- sched-messaging:1021 sched-messaging-1276 [009] d.h2. 34.483170: __enqueue_entity: cfs_rq(9:ff37d0bcfe46b680): sum_w_vruntime(-627321024) zero_vruntime(56921691597344)
swv += key * weight
Should be:
1003344726 + (56921690673139 - 56921691597344) * 1024 56958806 [*]
But is:
319064896 + (56921690673139 - 56921691597344) * 1024 -627321024
Consistent, but wrong
sched-messaging-1276 [009] d..2. 34.483173: update_curr: T<=> se(ff37d0bcd5c6c940): vruntime(56921691289762, E) deadline(56921694076707) weight(1048576) -- sched-messaging:1276 sched-messaging-1276 [009] d..2. 34.483173: __avg_vruntime: cfs_rq(9:ff37d0bcfe46b680): delta(571) sum_w_vruntime(180635073) zero_vruntime(56921691466161)
This would be dequeue(1276) update_entity_lag(), but the numbers make no sense...
swv -= sw * delta
-627321024 - 6159 * 571
-630837813 != 180635073
zv += delta
56921691597344 + 571
56921691597915 != 56921691466161
Also, the actual delta would be (zero_vruntime - prev zero_vruntime):
56921691466161-56921691597344
-131183
At which point we can construct the swv value from where we left of [*]
56958806 - -131183 * 6159
864914903
But the actual state makes no frigging sense....
sched-messaging-1276 [009] d..2. 34.483174: pick_task_fair: cfs_rq(9:ff37d0bcfe46b680): sum_w_vruntime(180635073) sum_weight(6159) zero_vruntime(56921691466161) avg_vruntime(56921691495489) sched-messaging-1276 [009] d..2. 34.483174: pick_task_fair: T< se(ff37d0bcd52718c0): vruntime(56921690673139, E) deadline(56921693473139) weight(1048576) -- sched-messaging:1021 sched-messaging-1276 [009] d..2. 34.483175: pick_task_fair: T se(ff37d0bcd56f98c0): vruntime(56921691917863) deadline(56921694079320) weight(1048576) -- sched-messaging:1201 sched-messaging-1276 [009] d..2. 34.483175: pick_task_fair: T se(ff37d0bcd5344940): vruntime(56921691340323, E) deadline(56921694140323) weight(1048576) -- sched-messaging:1036 sched-messaging-1276 [009] d..2. 34.483176: pick_task_fair: T se(ff37d0bcd56dc940): vruntime(56921691637185) deadline(56921694403038) weight(1048576) -- sched-messaging:1179 sched-messaging-1276 [009] d..2. 34.483177: pick_task_fair: T se(ff37d0bcd43eb100): vruntime(56921691629067) deadline(56921694429067) weight(1048576) -- sched-messaging:786 sched-messaging-1276 [009] d..2. 34.483177: pick_task_fair: T se(ff37d0bcd5d80080): vruntime(56921691810771) deadline(56921694610771) weight(1048576) -- sched-messaging:1291 sched-messaging-1276 [009] d..2. 34.483178: pick_task_fair: T se(ff37d0bcd027b100): vruntime(56921734696810) deadline(56921917287562) weight(15360) -- stress-ng-yield:693 sched-messaging-1276 [009] d..2. 34.483178: pick_task_fair: min_lag(-43201321) max_lag(822350) limit(38000000) sched-messaging-1276 [009] d..2. 34.483178: pick_task_fair: swv(864914903) sched-messaging-1276 [009] d..2. 34.483179: pick_task_fair: FAIL
Generated with the below patch on top of -rc6.
---
kernel/sched/fair.c +157 -33
@@ -678,6 +678,11 @@ sum_w_vruntime_add(struct cfs_rq *cfs_rq, struct sched_entity *se) cfs_rq->sum_w_vruntime += key * weight; cfs_rq->sum_weight += weight; + +trace_printk ("cfs_rq(%d:%px): sum_w_vruntime(%Ld) zero_vruntime(%Ld)\n" , +rq_of (cfs_rq)->cpu, cfs_rq, + cfs_rq->sum_w_vruntime, + cfs_rq->zero_vruntime); } static void
@@ -688,6 +693,11 @@ sum_w_vruntime_sub(struct cfs_rq *cfs_rq, struct sched_entity *se) cfs_rq->sum_w_vruntime -= key * weight; cfs_rq->sum_weight -= weight; + +trace_printk ("cfs_rq(%d:%px): sum_w_vruntime(%Ld) zero_vruntime(%Ld)\n" , +rq_of (cfs_rq)->cpu, cfs_rq, + cfs_rq->sum_w_vruntime, + cfs_rq->zero_vruntime); } static inline
@@ -698,6 +708,12 @@ void update_zero_vruntime(struct cfs_rq *cfs_rq, s64 delta)*/ cfs_rq->sum_w_vruntime -= cfs_rq->sum_weight * delta; cfs_rq->zero_vruntime += delta; + +trace_printk ("cfs_rq(%d:%px): delta(%Ld) sum_w_vruntime(%Ld) zero_vruntime(%Ld)\n" , +rq_of (cfs_rq)->cpu, cfs_rq, + delta, + cfs_rq->sum_w_vruntime, + cfs_rq->zero_vruntime); }/*
@@ -712,7 +728,7 @@ void update_zero_vruntime(struct cfs_rq *cfs_rq, s64 delta)* This means it is one entry 'behind' but that puts it close enough to where * the bound on entity_key() is at most two lag bounds. */ -u64 avg_vruntime (struct cfs_rq *cfs_rq) +static u64 __avg_vruntime (struct cfs_rq *cfs_rq,bool update) {struct sched_entity *curr = cfs_rq->curr;long weight = cfs_rq->sum_weight;
@@ -743,9 +759,17 @@ u64 avg_vruntime(struct cfs_rq *cfs_rq) delta = curr->vruntime - cfs_rq->zero_vruntime; } -update_zero_vruntime (cfs_rq, delta); +if (update) { +update_zero_vruntime (cfs_rq, delta); +return cfs_rq->zero_vruntime; + } -return cfs_rq->zero_vruntime; +return cfs_rq->zero_vruntime + delta; +} + +u64 avg_vruntime (struct cfs_rq *cfs_rq) +{ +return __avg_vruntime (cfs_rq, true); }static inline u64 cfs_rq_max_slice (struct cfs_rq *cfs_rq);
@@ -1078,11 +1102,6 @@ static struct sched_entity *__pick_eevdf(struct cfs_rq *cfs_rq, bool protect)return best; } -static struct sched_entity *pick_eevdf (struct cfs_rq *cfs_rq) -{ -return __pick_eevdf (cfs_rq, true); -} -struct sched_entity *__pick_last_entity (struct cfs_rq *cfs_rq) {struct rb_node *last =rb_last (&cfs_rq->tasks_timeline.rb_root);
@@ -1279,6 +1298,8 @@ s64 update_curr_common(struct rq *rq)return update_se (rq, &rq->donor->se); } +static void print_se (struct cfs_rq *cfs_rq,struct sched_entity *se,bool pick); +/* * Update the current task's runtime statistics. */
@@ -1304,6 +1325,10 @@ static void update_curr(struct cfs_rq *cfs_rq) curr->vruntime +=calc_delta_fair (delta_exec, curr); resched =update_deadline (cfs_rq, curr); +if (resched) +avg_vruntime (cfs_rq); + +print_se (cfs_rq, curr, true);if (entity_is_task (curr)) {/*
@@ -3849,6 +3874,8 @@ static void reweight_entity(struct cfs_rq *cfs_rq, struct sched_entity *se,bool rel_vprot = false;u64 vprot; +print_se (cfs_rq, se, true); +if (se->on_rq) {/* commit outstanding execution time */ update_curr (cfs_rq);
@@ -3896,6 +3923,8 @@ static void reweight_entity(struct cfs_rq *cfs_rq, struct sched_entity *se,__enqueue_entity (cfs_rq, se); cfs_rq->nr_queued++; } + +print_se (cfs_rq, se, true); } static void reweight_task_fair(struct rq *rq, struct task_struct *p,
@@ -5251,6 +5280,7 @@ place_entity(struct cfs_rq *cfs_rq, struct sched_entity *se, int flags)if (se->rel_deadline) { se->deadline += se->vruntime; se->rel_deadline =0 ; +print_se (cfs_rq, se, true);return ; }
@@ -5266,6 +5296,7 @@ place_entity(struct cfs_rq *cfs_rq, struct sched_entity *se, int flags)* EEVDF: vd_i = ve_i + r_i/w_i */ se->deadline = se->vruntime + vslice; +print_se (cfs_rq, se, true); }static void check_enqueue_throttle (struct cfs_rq *cfs_rq);
@@ -5529,31 +5560,6 @@ set_next_entity(struct cfs_rq *cfs_rq, struct sched_entity *se, bool first) se->prev_sum_exec_runtime = se->sum_exec_runtime; } -static int dequeue_entities (struct rq *rq,struct sched_entity *se,int flags); - -/* -* Pick the next process, keeping these things in mind, in this order: -* 1) keep things fair between processes/task groups -* 2) pick the "next" process, since someone really wants that to run -* 3) pick the "last" process, for cache locality -* 4) do not run the "skip" process, if something else is available -*/ -static struct sched_entity * -pick_next_entity (struct rq *rq,struct cfs_rq *cfs_rq) -{ -struct sched_entity *se; - - se =pick_eevdf (cfs_rq); -if (se->sched_delayed) { -dequeue_entities (rq, se,DEQUEUE_SLEEP |DEQUEUE_DELAYED ); -/* -* Must not reference @se again, see __block_task(). -*/ -return NULL ; - } -return se; -} -static bool check_cfs_rq_runtime (struct cfs_rq *cfs_rq);static void put_prev_entity (struct cfs_rq *cfs_rq,struct sched_entity *prev)
@@ -8942,6 +8948,123 @@ static void wakeup_preempt_fair(struct rq *rq, struct task_struct *p, int wake_fresched_curr_lazy (rq); } +static __always_inline +void print_se(struct cfs_rq *cfs_rq, struct sched_entity *se, bool pick) +{ +bool curr = (se == cfs_rq->curr); +bool el =entity_eligible (cfs_rq, se); +bool prot =protect_slice (se); +bool task = false; +char *comm =NULL ; +int pid =-1 ; + +if (entity_is_task (se)) { +struct task_struct *p =task_of (se); + task = true; + comm = p->comm; + pid = p->pid; + } + +trace_printk ("%c%c%c%c se(%px): vruntime(%Ld%s) deadline(%Ld) weight(%ld) -- %s:%d\n" , + task ?'T' :'@' , + pick ?'<' :' ' , + curr && prot ?'=' :' ' , + curr ?'>' :' ' , + se, se->vruntime, el ?", E" :"" , + se->deadline, se->load.weight, + comm, pid); +} + +static struct sched_entity *pick_debug (struct cfs_rq *cfs_rq) +{ +struct sched_entity *pick =__pick_eevdf (cfs_rq, true); +struct sched_entity *curr = cfs_rq->curr; +s64 min_lag =0 , max_lag =0 ; +u64 runtime, weight, z_vruntime, avg; +u64 swv =0 ; + +s64 limit =10 *(sysctl_sched_base_slice +TICK_NSEC ); + +if (curr && !curr->on_rq) + curr =NULL ; + + runtime = cfs_rq->sum_w_vruntime; + weight = cfs_rq->sum_weight; + z_vruntime = cfs_rq->zero_vruntime; +barrier (); + avg =__avg_vruntime (cfs_rq, false); + +trace_printk ("cfs_rq(%d:%px): sum_w_vruntime(%Ld) sum_weight(%Ld) zero_vruntime(%Ld) avg_vruntime(%Ld)\n" , +rq_of (cfs_rq)->cpu, cfs_rq, + runtime, weight, + z_vruntime, avg); + +for (struct rb_node *node = cfs_rq->tasks_timeline.rb_leftmost; + node; node =rb_next (node)) { +struct sched_entity *se =__node_2_se (node); +if (se == curr) + curr =NULL ; +print_se (cfs_rq, se, pick == se); + + swv += (se->vruntime - z_vruntime) *scale_load_down (se->load.weight); + +s64 vlag = avg - se->vruntime; + min_lag =min (min_lag, vlag); + max_lag =max (max_lag, vlag); + } + +if (curr) { +print_se (cfs_rq, curr, pick == curr); + +s64 vlag = avg - curr->vruntime; + min_lag =min (min_lag, vlag); + max_lag =max (max_lag, vlag); + } + +trace_printk (" min_lag(%Ld) max_lag(%Ld) limit(%Ld)\n" , min_lag, max_lag, limit); +trace_printk (" swv(%Ld)\n" , swv); + +if (swv != runtime) { +trace_printk ("FAIL\n" ); +tracing_off (); +printk ("FAIL FAIL FAIL!!!\n" ); + } + +// WARN_ON_ONCE(min_lag < -limit || max_lag > limit); + +if (!pick) { +trace_printk ("picked NULL!!\n" ); +tracing_off (); +printk ("FAIL FAIL FAIL!!!\n" ); +return __pick_first_entity (cfs_rq); + } + +return pick; +} + +/* +* Pick the next process, keeping these things in mind, in this order: +* 1) keep things fair between processes/task groups +* 2) pick the "next" process, since someone really wants that to run +* 3) pick the "last" process, for cache locality +* 4) do not run the "skip" process, if something else is available +*/ +static struct sched_entity * +pick_next_entity (struct rq *rq,struct cfs_rq *cfs_rq) +{ +struct sched_entity *se; + + se =pick_debug (cfs_rq); +if (se->sched_delayed) { +dequeue_entities (rq, se,DEQUEUE_SLEEP |DEQUEUE_DELAYED ); +/* +* Must not reference @se again, see __block_task(). +*/ +return NULL ; + } +return se; +} +static struct task_struct *pick_task_fair (struct rq *rq,struct rq_flags *rf) {struct sched_entity *se;
@@ -9129,6 +9252,7 @@ static void yield_task_fair(struct rq *rq)if (entity_eligible (cfs_rq, se)) { se->vruntime = se->deadline; se->deadline +=calc_delta_fair (se->slice, se); +avg_vruntime (cfs_rq); } }
Peter Zijlstra
maintainerRe: [PATCH v2 1/7] sched/fair: Fix zero_vruntime tracking
Quoted 1 line · Peter Zijlstra
WTF!?!
I'm thinking this might help... I'll try once I'm back home again.
kernel/sched/debug.c +3 -1
@@ -902,6 +902,7 @@ static void print_rq(struct seq_file *m, struct rq *rq, int rq_cpu)void print_cfs_rq (struct seq_file *m,int cpu,struct cfs_rq *cfs_rq) {s64 left_vruntime =-1 , zero_vruntime, right_vruntime =-1 , left_deadline =-1 , spread; +u64 avruntime;struct sched_entity *last, *first, *root;struct rq *rq =cpu_rq (cpu);unsigned long flags;
@@ -925,6 +926,7 @@ void print_cfs_rq(struct seq_file *m, int cpu, struct cfs_rq *cfs_rq)if (last) right_vruntime = last->vruntime; zero_vruntime = cfs_rq->zero_vruntime; + avruntime =avg_vruntime (cfs_rq);raw_spin_rq_unlock_irqrestore (rq, flags); SEQ_printf(m, " .%-30s: %Ld.%06ld\n", "left_deadline",
@@ -934,7 +936,7 @@ void print_cfs_rq(struct seq_file *m, int cpu, struct cfs_rq *cfs_rq)SEQ_printf (m," .%-30s: %Ld.%06ld\n" ,"zero_vruntime" ,SPLIT_NS (zero_vruntime));SEQ_printf (m," .%-30s: %Ld.%06ld\n" ,"avg_vruntime" , -SPLIT_NS (avg_vruntime (cfs_rq))); +SPLIT_NS (avruntime));SEQ_printf (m," .%-30s: %Ld.%06ld\n" ,"right_vruntime" ,SPLIT_NS (right_vruntime)); spread = right_vruntime - left_vruntime;
Re: [PATCH v2 1/7] sched/fair: Fix zero_vruntime tracking
kernel/sched/debug.c void print_cfs_rq(struct seq_file *m, int cpu, struct cfs_rq *cfs_rq) · line 930
Quoted 6 lines · Peter Zijlstra
kernel/sched/debug.c +1
-0@@ -925,6 +926,7 @@ void print_cfs_rq(struct seq_file *m, int cpu, struct cfs_rq *cfs_rq)if (last) right_vruntime = last->vruntime; zero_vruntime = cfs_rq->zero_vruntime; + avruntime =avg_vruntime (cfs_rq);raw_spin_rq_unlock_irqrestore (rq, flags);
Ah! Didn't notice we dropped the lock as soon as we are done reading the necessary values. Makes sense why reading the debugfs under heavy load crashed.
Ran 100 loops of reading the debug file while running stress-ng
+ sched-messaging and I haven't see any crashes yet so feel free to include:
Quoted 2 lines
kernel/sched/debug.c +0
-0SEQ_printf(m, " .%-30s: %Ld.%06ld\n", "left_deadline",
Signature · 2 lines
Thanks and Regards, Prateek
John Stultz
Tested-byRe: [PATCH v2 1/7] sched/fair: Fix zero_vruntime tracking
In reply to Peter ZijlstraQuoted 27 lines · Peter Zijlstra
On Tue, Mar 31, 2026 at 02:20:35PM +0200, Peter Zijlstra wrote:
I'm thinking this might help... I'll try once I'm back home again.
kernel/sched/debug.c +2
-0@@ -902,6 +902,7 @@ static void print_rq(struct seq_file *m, struct rq *rq, int rq_cpu)void print_cfs_rq (struct seq_file *m,int cpu,struct cfs_rq *cfs_rq) {s64 left_vruntime =-1 , zero_vruntime, right_vruntime =-1 , left_deadline =-1 , spread; +u64 avruntime;struct sched_entity *last, *first, *root;struct rq *rq =cpu_rq (cpu);unsigned long flags;@@ -925,6 +926,7 @@ void print_cfs_rq(struct seq_file *m, int cpu, struct cfs_rq *cfs_rq)if (last) right_vruntime = last->vruntime; zero_vruntime = cfs_rq->zero_vruntime; + avruntime =avg_vruntime (cfs_rq);raw_spin_rq_unlock_irqrestore (rq, flags); SEQ_printf(m, " .%-30s: %Ld.%06ld\n", "left_deadline",
kernel/sched/debug.c void print_cfs_rq(struct seq_file *m, int cpu, struct cfs_rq *cfs_rq) · line 942
Quoted 8 lines
kernel/sched/debug.c +1
-1@@ -934,7 +936,7 @@ void print_cfs_rq(struct seq_file *m, int cpu, struct cfs_rq *cfs_rq)SEQ_printf (m," .%-30s: %Ld.%06ld\n" ,"zero_vruntime" ,SPLIT_NS (zero_vruntime));SEQ_printf (m," .%-30s: %Ld.%06ld\n" ,"avg_vruntime" , -SPLIT_NS (avg_vruntime (cfs_rq))); +SPLIT_NS (avruntime));SEQ_printf (m," .%-30s: %Ld.%06ld\n" ,"right_vruntime" ,SPLIT_NS (right_vruntime)); spread = right_vruntime - left_vruntime;
This on top of your two previous changes has run for 5 hours for me now, which is usually where I'd call things "good" when bisecting.
I'm going to leave it overnight, but tentatively:
thanks
-john
Re: [PATCH v2 1/7] sched/fair: Fix zero_vruntime tracking
In reply to Peter ZijlstraQuoted 14 lines · Peter Zijlstra
This means, that if the two tasks playing leapfrog can reach the critical speed to reach the overflow point inside one tick's worth of time, we're up a creek.
If this is indeed the case, then the below should cure things.
This also means that running a HZ=100 config will increase the chances of hitting this vs HZ=1000.
kernel/sched/fair.c +0
-0
kernel/sched/fair.c static void yield_task_fair(struct rq *rq) · line 9312
Quoted 6 lines
kernel/sched/fair.c +1
-0@@ -9307,6 +9307,7 @@ static void yield_task_fair(struct rq *rq)if (entity_eligible (cfs_rq, se)) { se->vruntime = se->deadline; se->deadline +=calc_delta_fair (se->slice, se); +avg_vruntime (cfs_rq); } }
I just tested with this and similar to Prateek, I also still tripped the issue.
I'll give your new patch a spin here in a second.
thanks
-john
Peter Zijlstra
maintainerRe: [PATCH v2 1/7] sched/fair: Fix zero_vruntime tracking
Quoted 24 lines · John Stultz
Quoted 14 lines · Peter Zijlstra
This means, that if the two tasks playing leapfrog can reach the critical speed to reach the overflow point inside one tick's worth of time, we're up a creek.
If this is indeed the case, then the below should cure things.
This also means that running a HZ=100 config will increase the chances of hitting this vs HZ=1000.
kernel/sched/fair.c +0
-0kernel/sched/fair.c static void yield_task_fair(struct rq *rq) · line 9312
Quoted 6 lines
kernel/sched/fair.c +1
-0@@ -9307,6 +9307,7 @@ static void yield_task_fair(struct rq *rq)if (entity_eligible (cfs_rq, se)) { se->vruntime = se->deadline; se->deadline +=calc_delta_fair (se->slice, se); +avg_vruntime (cfs_rq); } }I just tested with this and similar to Prateek, I also still tripped the issue.
Quoted 1 line
I'll give your new patch a spin here in a second.
Stick both on please :-) AFAICT they're both real, just not convinced they're what you're hitting.
Re: [PATCH v2 1/7] sched/fair: Fix zero_vruntime tracking
Quoted 25 lines · Peter Zijlstra
Quoted 24 lines · John Stultz
Quoted 14 lines · Peter Zijlstra
This means, that if the two tasks playing leapfrog can reach the critical speed to reach the overflow point inside one tick's worth of time, we're up a creek.
If this is indeed the case, then the below should cure things.
This also means that running a HZ=100 config will increase the chances of hitting this vs HZ=1000.
kernel/sched/fair.c +0
-0kernel/sched/fair.c static void yield_task_fair(struct rq *rq) · line 9312
Quoted 6 lines
kernel/sched/fair.c +1
-0@@ -9307,6 +9307,7 @@ static void yield_task_fair(struct rq *rq)if (entity_eligible (cfs_rq, se)) { se->vruntime = se->deadline; se->deadline +=calc_delta_fair (se->slice, se); +avg_vruntime (cfs_rq); } }I just tested with this and similar to Prateek, I also still tripped the issue.
Quoted 4 lines
Quoted 1 line
I'll give your new patch a spin here in a second.
Stick both on please :-) AFAICT they're both real, just not convinced they're what you're hitting.
Sadly I'm still hitting it with both. This time the stack trace was different, and it came up through do_nanosleep() from stress-ng-exit instead of yield.
I'll re-add my debug trace_printks (I dropped them while testing your patches in case they changed the timing of things) and work to understand more here.
thanks
-john
[ 6777.071789] BUG: kernel NULL pointer dereference, address: 0000000000000051 [ 6777.076712] #PF: supervisor read access in kernel mode [ 6777.079767] #PF: error_code(0x0000) - not-present page [ 6777.082787] PGD 0 P4D 0 [ 6777.084361] Oops: Oops: 0000 [#1] SMP NOPTI [ 6777.086812] CPU: 37 UID: 0 PID: 531349 Comm: stress-ng-exit- Tainted: G W 7.0.0-rc1-00001-gb3d99f43c72b-dirty #18 PREEMPT(full) [ 6777.094026] Tainted: [W]=WARN [ 6777.095771] Hardware name: QEMU Standard PC (i440FX + PIIX, 1996), BIOS 1.17.0-debian-1.17.0-1 04/01/2014 [ 6777.100689] RIP: 0010:pick_task_fair+0x6f/0xb0 [ 6777.103239] Code: 85 ff 74 52 48 8b 47 48 48 85 c0 74 d6 80 78 50 00 74 d0 48 89 3c 24 e8 8f e0 ff ff 48 8b 3c 24 be 01 00 00 00 e8 31 77 ff ff <80> 78 51 00 74 c3 ba 2 1 00 00 00 48 89 c6 48 89 df e8 db f1 ff ff [ 6777.113447] RSP: 0018:ffffc9000f7dbcf0 EFLAGS: 00010082 [ 6777.116283] RAX: 0000000000000000 RBX: ffff8881b976bbc0 RCX: 0000000000000800 [ 6777.119791] RDX: 000000000a071800 RSI: 000000000b719000 RDI: 00004fc5ab7864c9 [ 6777.123608] RBP: ffffc9000f7dbdf0 R08: 0000000000000400 R09: 0000000000000002 [ 6777.127785] R10: 0000000000000025 R11: 0000000000000000 R12: ffff88810adc4200 [ 6777.131937] R13: ffff88810adc4200 R14: ffffffff82ce5b28 R15: ffff8881b976bbc0 [ 6777.135994] FS: 00007fc1c37866c0(0000) GS:ffff888235c2b000(0000) knlGS:0000000000000000 [ 6777.140449] CS: 0010 DS: 0000 ES: 0000 CR0: 0000000080050033 [ 6777.143756] CR2: 0000000000000051 CR3: 000000014160f005 CR4: 0000000000370ef0 [ 6777.147819] Call Trace: [ 6777.149379] <TASK> [ 6777.150653] pick_next_task_fair+0x3c/0x8c0 [ 6777.153115] __schedule+0x1e8/0x1200 [ 6777.155241] ? do_nanosleep+0x1a/0x170 [ 6777.157336] schedule+0x3d/0x130 [ 6777.159150] do_nanosleep+0x88/0x170 [ 6777.161161] ? find_held_lock+0x2b/0x80 [ 6777.163201] hrtimer_nanosleep+0xba/0x1f0 [ 6777.165481] ? __pfx_hrtimer_wakeup+0x10/0x10 [ 6777.167990] common_nsleep+0x34/0x60 [ 6777.169957] __x64_sys_clock_nanosleep+0xde/0x150 [ 6777.172443] do_syscall_64+0xf3/0x680 [ 6777.174409] entry_SYSCALL_64_after_hwframe+0x77/0x7f [ 6777.177176] RIP: 0033:0x7fc1cc92d9ee [ 6777.179009] Code: 08 0f 85 f5 4b ff ff 49 89 fb 48 89 f0 48 89 d7
48 89 ce 4c 89 c2 4d 89 ca 4c 8b 44 24 08 4c 8b 4c 24 10 4c 89 5c 24 08 0f 05 <c3> 66 2e 0f 1f 84 00 00 00 00 00 0f 1f 80 00 00 00 00 48 83 ec 08
Peter Zijlstra
maintainerPATCH v2 2/7 sched/fair: Only set slice protection at pick time
In reply to Peter ZijlstraWe should not (re)set slice protection in the sched_change pattern which calls put_prev_task() / set_next_task().
--- kernel/sched/fair.c | 11 ++++++----- 1 file changed, 6 insertions(+), 5 deletions(-)
kernel/sched/fair.c +6 -5
@@ -5444,7 +5444,7 @@ dequeue_entity(struct cfs_rq *cfs_rq, st }static void -set_next_entity (struct cfs_rq *cfs_rq,struct sched_entity *se) +set_next_entity (struct cfs_rq *cfs_rq,struct sched_entity *se,bool first) {clear_buddies (cfs_rq, se);
@@ -5459,7 +5459,8 @@ set_next_entity(struct cfs_rq *cfs_rq, s__dequeue_entity (cfs_rq, se);update_load_avg (cfs_rq, se,UPDATE_TG ); -set_protect_slice (cfs_rq, se); +if (first) +set_protect_slice (cfs_rq, se); }update_stats_curr_start (cfs_rq, se);
@@ -8977,13 +8978,13 @@ pick_next_task_fair(struct rq *rq, struc pse =parent_entity (pse); }if (se_depth >= pse_depth) { -set_next_entity (cfs_rq_of (se), se); +set_next_entity (cfs_rq_of (se), se, true); se =parent_entity (se); } }put_prev_entity (cfs_rq, pse); -set_next_entity (cfs_rq, se); +set_next_entity (cfs_rq, se, true);__set_next_task_fair (rq, p, true); }
@@ -13597,7 +13598,7 @@ static void set_next_task_fair(struct rqfor_each_sched_entity (se) {struct cfs_rq *cfs_rq =cfs_rq_of (se); -set_next_entity (cfs_rq, se); +set_next_entity (cfs_rq, se, first);/* ensure bandwidth has been allocated on our new cfs_rq */ account_cfs_rq_runtime (cfs_rq,0 ); }
Peter Zijlstra
maintainerPATCH v2 3/7 sched/eevdf: Update se->vprot in reweight_entity()
In reply to Peter ZijlstraFrom: Wang Tao <[email protected]>
In the EEVDF framework with Run-to-Parity protection, se->vprot is an independent variable defining the virtual protection timestamp.
When reweight_entity() is called (e.g., via nice/renice), it performs the following actions to preserve Lag consistency:
1. Scales se->vlag based on the new weight.
2. Calls place_entity(), which recalculates se->vruntime based on the new weight and scaled lag.
However, the current implementation fails to update se->vprot, leading to mismatches between the task's actual runtime and its expected duration.
--- kernel/sched/fair.c | 12 ++++++++++++ 1 file changed, 12 insertions(+)
kernel/sched/fair.c +12 -0
@@ -3814,6 +3814,8 @@ static void reweight_entity(struct cfs_r unsigned long weight) {bool curr = cfs_rq->curr == se; +bool rel_vprot = false; +u64 vprot;if (se->on_rq) {/* commit outstanding execution time */
@@ -3821,6 +3823,11 @@ static void reweight_entity(struct cfs_rupdate_entity_lag (cfs_rq, se); se->deadline -= se->vruntime; se->rel_deadline =1 ; +if (curr &&protect_slice (se)) { + vprot = se->vprot - se->vruntime; + rel_vprot = true; + } + cfs_rq->nr_queued--;if (!curr)__dequeue_entity (cfs_rq, se);
@@ -3836,6 +3843,9 @@ static void reweight_entity(struct cfs_rif (se->rel_deadline) se->deadline =div_s64 (se->deadline * se->load.weight, weight); +if (rel_vprot) + vprot =div_s64 (vprot * se->load.weight, weight); +update_load_set (&se->load, weight); do {
@@ -3847,6 +3857,8 @@ static void reweight_entity(struct cfs_renqueue_load_avg (cfs_rq, se);if (se->on_rq) {place_entity (cfs_rq, se,0 ); +if (rel_vprot) + se->vprot = se->vruntime + vprot;update_load_add (&cfs_rq->load, se->load.weight);if (!curr)__enqueue_entity (cfs_rq, se);
Peter Zijlstra
maintainerPATCH v2 4/7 sched/fair: Fix lag clamp
In reply to Peter ZijlstraVincent reported that he was seeing undue lag clamping in a mixed slice workload. Implement the max_slice tracking as per the todo comment.
--- include/linux/sched.h | 1 + kernel/sched/fair.c | 39 +++++++++++++++++++++++++++++++++++---- 2 files changed, 36 insertions(+), 4 deletions(-)
include/linux/sched.h +1 -0
@@ -574,6 +574,7 @@ struct sched_entity {u64 deadline;u64 min_vruntime;u64 min_slice; +u64 max_slice;struct list_head group_node;unsigned char on_rq;
kernel/sched/fair.c +35 -4
@@ -748,6 +748,8 @@ u64 avg_vruntime(struct cfs_rq *cfs_rq)return cfs_rq->zero_vruntime; } +static inline u64 cfs_rq_max_slice (struct cfs_rq *cfs_rq); +/* * lag_i = S - s_i = w_i * (V - v_i) *
@@ -761,17 +763,16 @@ u64 avg_vruntime(struct cfs_rq *cfs_rq)* EEVDF gives the following limit for a steady state system: * * -r_max < lag < max(r_max, q) -* -* XXX could add max_slice to the augmented data to track this. */ static void update_entity_lag (struct cfs_rq *cfs_rq,struct sched_entity *se) { +u64 max_slice =cfs_rq_max_slice (cfs_rq) +TICK_NSEC ;s64 vlag, limit;WARN_ON_ONCE (!se->on_rq); vlag =avg_vruntime (cfs_rq) - se->vruntime; - limit =calc_delta_fair (max_t (u64,2 *se->slice,TICK_NSEC ), se); + limit =calc_delta_fair (max_slice, se); se->vlag =clamp (vlag, -limit, limit); }
@@ -829,6 +830,21 @@ static inline u64 cfs_rq_min_slice(strucreturn min_slice; } +static inline u64 cfs_rq_max_slice (struct cfs_rq *cfs_rq) +{ +struct sched_entity *root =__pick_root_entity (cfs_rq); +struct sched_entity *curr = cfs_rq->curr; +u64 max_slice =0ULL ; + +if (curr && curr->on_rq) + max_slice = curr->slice; + +if (root) + max_slice =max (max_slice, root->max_slice); + +return max_slice; +} +static inline bool __entity_less (struct rb_node *a,const struct rb_node *b) {return entity_before (__node_2_se (a),__node_2_se (b));
@@ -853,6 +869,15 @@ static inline void __min_slice_update(st } } +static inline void __max_slice_update (struct sched_entity *se,struct rb_node *node) +{ +if (node) { +struct sched_entity *rse =__node_2_se (node); +if (rse->max_slice > se->max_slice) + se->max_slice = rse->max_slice; + } +} +/* * se->min_vruntime = min(se->vruntime, {left,right}->min_vruntime) */
@@ -860,6 +885,7 @@ static inline bool min_vruntime_update(s {u64 old_min_vruntime = se->min_vruntime;u64 old_min_slice = se->min_slice; +u64 old_max_slice = se->max_slice;struct rb_node *node = &se->run_node; se->min_vruntime = se->vruntime;
@@ -870,8 +896,13 @@ static inline bool min_vruntime_update(s__min_slice_update (se, node->rb_right);__min_slice_update (se, node->rb_left); + se->max_slice = se->slice; +__max_slice_update (se, node->rb_right); +__max_slice_update (se, node->rb_left); +return se->min_vruntime == old_min_vruntime && - se->min_slice == old_min_slice; + se->min_slice == old_min_slice && + se->max_slice == old_max_slice; } RB_DECLARE_CALLBACKS(static, min_vruntime_cb, struct sched_entity,
Dietmar Eggemann
reviewerRe: [PATCH v2 4/7] sched/fair: Fix lag clamp
On 19.02.26 08:58, Peter Zijlstra wrote:
[...]
Quoted 10 lines
kernel/sched/fair.c +1
-2@@ -761,17 +763,16 @@ u64 avg_vruntime(struct cfs_rq *cfs_rq)* EEVDF gives the following limit for a steady state system: * * -r_max < lag < max(r_max, q) -* -* XXX could add max_slice to the augmented data to track this. */ static void update_entity_lag (struct cfs_rq *cfs_rq,struct sched_entity *se) { +u64 max_slice =cfs_rq_max_slice (cfs_rq) +TICK_NSEC ;
kernel/sched/fair.c u64 avg_vruntime(struct cfs_rq *cfs_rq) · line 778
Quoted 10 lines
kernel/sched/fair.c +1
-1s64 vlag, limit;WARN_ON_ONCE (!se->on_rq); vlag =avg_vruntime (cfs_rq) - se->vruntime; - limit =calc_delta_fair (max_t (u64,2 *se->slice,TICK_NSEC ), se); + limit =calc_delta_fair (max_slice, se); se->vlag =clamp (vlag, -limit, limit); }
nitpick:
The "Limit this to either double the slice length with a minimum of TICK_NSEC ..." in the function comment header doesn't match anymore.
Re: [PATCH v2 4/7] sched/fair: Fix lag clamp
In reply to Peter ZijlstraQuoted 5 lines · Peter Zijlstra
Vincent reported that he was seeing undue lag clamping in a mixed slice workload. Implement the
max_slicetracking as per the todo comment.
Quoted 7 lines
Fixes 147f3efaa241 ("sched/fair: Implement an EEVDF-like scheduling policy")Reported-off-by Vincent Guittot <[email protected]>Signed-off-by Peter Zijlstra (Intel) <[email protected]>Tested-by Vincent Guittot <[email protected]>Tested-by K Prateek Nayak <[email protected]>Tested-by Shubhang Kaushik <[email protected]>
Quoted 109 lines
--- include/linux/sched.h | 1 + kernel/sched/fair.c | 39 +++++++++++++++++++++++++++++++++++---- 2 files changed, 36 insertions(+), 4 deletions(-)include/linux/sched.h +1
-0@@ -574,6 +574,7 @@ struct sched_entity {u64 deadline;u64 min_vruntime;u64 min_slice; +u64 max_slice;struct list_head group_node;unsigned char on_rq;kernel/sched/fair.c +35
-4@@ -748,6 +748,8 @@ u64 avg_vruntime(struct cfs_rq *cfs_rq)return cfs_rq->zero_vruntime; } +static inline u64 cfs_rq_max_slice (struct cfs_rq *cfs_rq); +/* * lag_i = S - s_i = w_i * (V - v_i) * @@ -761,17 +763,16 @@ u64 avg_vruntime(struct cfs_rq *cfs_rq)* EEVDF gives the following limit for a steady state system: * * -r_max < lag < max(r_max, q) -* -* XXX could add max_slice to the augmented data to track this. */ static void update_entity_lag (struct cfs_rq *cfs_rq,struct sched_entity *se) { +u64 max_slice =cfs_rq_max_slice (cfs_rq) +TICK_NSEC ;s64 vlag, limit;WARN_ON_ONCE (!se->on_rq); vlag =avg_vruntime (cfs_rq) - se->vruntime; - limit =calc_delta_fair (max_t (u64,2 *se->slice,TICK_NSEC ), se); + limit =calc_delta_fair (max_slice, se); se->vlag =clamp (vlag, -limit, limit); }@@ -829,6 +830,21 @@ static inline u64 cfs_rq_min_slice(strucreturn min_slice; } +static inline u64 cfs_rq_max_slice (struct cfs_rq *cfs_rq) +{ +struct sched_entity *root =__pick_root_entity (cfs_rq); +struct sched_entity *curr = cfs_rq->curr; +u64 max_slice =0ULL ; + +if (curr && curr->on_rq) + max_slice = curr->slice; + +if (root) + max_slice =max (max_slice, root->max_slice); + +return max_slice; +} +static inline bool __entity_less (struct rb_node *a,const struct rb_node *b) {return entity_before (__node_2_se (a),__node_2_se (b));@@ -853,6 +869,15 @@ static inline void __min_slice_update(st } } +static inline void __max_slice_update (struct sched_entity *se,struct rb_node *node) +{ +if (node) { +struct sched_entity *rse =__node_2_se (node); +if (rse->max_slice > se->max_slice) + se->max_slice = rse->max_slice; + } +} +/* * se->min_vruntime = min(se->vruntime, {left,right}->min_vruntime) */ @@ -860,6 +885,7 @@ static inline bool min_vruntime_update(s {u64 old_min_vruntime = se->min_vruntime;u64 old_min_slice = se->min_slice; +u64 old_max_slice = se->max_slice;struct rb_node *node = &se->run_node; se->min_vruntime = se->vruntime;@@ -870,8 +896,13 @@ static inline bool min_vruntime_update(s__min_slice_update (se, node->rb_right);__min_slice_update (se, node->rb_left); + se->max_slice = se->slice; +__max_slice_update (se, node->rb_right); +__max_slice_update (se, node->rb_left); +return se->min_vruntime == old_min_vruntime && - se->min_slice == old_min_slice; + se->min_slice == old_min_slice && + se->max_slice == old_max_slice; } RB_DECLARE_CALLBACKS(static, min_vruntime_cb, struct sched_entity,
Peter Zijlstra
maintainerPATCH v2 5/7 sched/fair: Increase weight bits for avg_vruntime
In reply to Peter ZijlstraDue to the zero_vruntime patch, the deltas are now a lot smaller and measurement with kernel-build and hackbench runs show about 45 bits used.
This ensures avg_vruntime() tracks the full weight range, reducing numerical artifacts in reweight and the like.
Also, lets keep the paranoid debug code around fow now.
--- kernel/sched/debug.c | 14 ++++++- kernel/sched/fair.c | 91 ++++++++++++++++++++++++++++++++++++++---------- kernel/sched/features.h | 2 + kernel/sched/sched.h | 3 + 4 files changed, 90 insertions(+), 20 deletions(-)
kernel/sched/debug.c +13 -1
@@ -8,6 +8,7 @@*/ #include <linux/debugfs.h> #include <linux/nmi.h> +#include <linux/log2.h> #include "sched.h" /*
@@ -901,10 +902,13 @@ static void print_rq(struct seq_file *m,void print_cfs_rq (struct seq_file *m,int cpu,struct cfs_rq *cfs_rq) { -s64 left_vruntime =-1 , zero_vruntime, right_vruntime =-1 , left_deadline =-1 , spread; +s64 left_vruntime =-1 , right_vruntime =-1 , left_deadline =-1 , spread; +s64 zero_vruntime =-1 , sum_w_vruntime =-1 ;struct sched_entity *last, *first, *root;struct rq *rq =cpu_rq (cpu); +unsigned int sum_shift;unsigned long flags; +u64 sum_weight;#ifdef CONFIG_FAIR_GROUP_SCHED SEQ_printf (m,"\n" );
@@ -925,6 +929,9 @@ void print_cfs_rq(struct seq_file *m, inif (last) right_vruntime = last->vruntime; zero_vruntime = cfs_rq->zero_vruntime; + sum_w_vruntime = cfs_rq->sum_w_vruntime; + sum_weight = cfs_rq->sum_weight; + sum_shift = cfs_rq->sum_shift;raw_spin_rq_unlock_irqrestore (rq, flags); SEQ_printf(m, " .%-30s: %Ld.%06ld\n", "left_deadline",
@@ -933,6 +940,11 @@ void print_cfs_rq(struct seq_file *m, in SPLIT_NS(left_vruntime));SEQ_printf (m," .%-30s: %Ld.%06ld\n" ,"zero_vruntime" ,SPLIT_NS (zero_vruntime)); +SEQ_printf (m," .%-30s: %Ld (%d bits)\n" ,"sum_w_vruntime" , + sum_w_vruntime,ilog2 (abs (sum_w_vruntime))); +SEQ_printf (m," .%-30s: %Lu\n" ,"sum_weight" , + sum_weight); +SEQ_printf (m," .%-30s: %u\n" ,"sum_shift" , sum_shift);SEQ_printf (m," .%-30s: %Ld.%06ld\n" ,"avg_vruntime" ,SPLIT_NS (avg_vruntime (cfs_rq))); SEQ_printf(m, " .%-30s: %Ld.%06ld\n", "right_vruntime",
kernel/sched/fair.c +73 -18
149 lines not on this page · raw message
kernel/sched/features.h +2 -0
@@ -58,6 +58,8 @@ SCHED_FEAT(CACHE_HOT_BUDDY, true) SCHED_FEAT(DELAY_DEQUEUE, true) SCHED_FEAT(DELAY_ZERO, true) +SCHED_FEAT (PARANOID_AVG , false) +/* * Allow wakeup-time preemption of the current task: */
kernel/sched/sched.h +2 -1
@@ -684,8 +684,9 @@ struct cfs_rq {s64 sum_w_vruntime;u64 sum_weight; -u64 zero_vruntime; +unsigned int sum_shift; +#ifdef CONFIG_SCHED_CORE unsigned int forceidle_seq;u64 zero_vruntime_fi;
Vincent Guittot
maintainerRe: [PATCH v2 5/7] sched/fair: Increase weight bits for avg_vruntime
Quoted 7 lines · Peter Zijlstra
Due to the
zero_vruntimepatch, the deltas are now a lot smaller and measurement with kernel-build and hackbench runs show about 45 bits used.This ensures
avg_vruntime()tracks the full weight range, reducing numerical artifacts in reweight and the like.
Instead of paranoid, would it be better to add WARN_ONCE ?
I'm afraid that we will not notice any potential overflow without a long study of the regression with SCHED_FEAT(PARANOID_AVG, false)
Couldn't we add a cheaper WARN_ONCE (key > 2^50) in __sum_w_vruntime_add ?
We should always have
key < 110ms (max slice+max tick) * nice_0 (2^20) / weight (2) key < 2^46
We can use 50 bits to get margin
Weight is always less than 27bits and key*weight gives us 110ms (max slice+max tick) * nice_0 (2^20) so we should never add more than 2^47 to ->sum_weight
so a WARN_ONCE (cfs_rq->sum_weight > 2^63) should be enough
Quoted 245 lines
Also, lets keep the paranoid debug code around fow now.
Signed-off-by Peter Zijlstra (Intel) <[email protected]>Tested-by K Prateek Nayak <[email protected]>Tested-by Shubhang Kaushik <[email protected]>--- kernel/sched/debug.c | 14 ++++++- kernel/sched/fair.c | 91 ++++++++++++++++++++++++++++++++++++++---------- kernel/sched/features.h | 2 + kernel/sched/sched.h | 3 + 4 files changed, 90 insertions(+), 20 deletions(-)kernel/sched/debug.c +13
-1@@ -8,6 +8,7 @@*/ #include <linux/debugfs.h> #include <linux/nmi.h> +#include <linux/log2.h> #include "sched.h" /* @@ -901,10 +902,13 @@ static void print_rq(struct seq_file *m,void print_cfs_rq (struct seq_file *m,int cpu,struct cfs_rq *cfs_rq) { -s64 left_vruntime =-1 , zero_vruntime, right_vruntime =-1 , left_deadline =-1 , spread; +s64 left_vruntime =-1 , right_vruntime =-1 , left_deadline =-1 , spread; +s64 zero_vruntime =-1 , sum_w_vruntime =-1 ;struct sched_entity *last, *first, *root;struct rq *rq =cpu_rq (cpu); +unsigned int sum_shift;unsigned long flags; +u64 sum_weight;#ifdef CONFIG_FAIR_GROUP_SCHED SEQ_printf (m,"\n" );@@ -925,6 +929,9 @@ void print_cfs_rq(struct seq_file *m, inif (last) right_vruntime = last->vruntime; zero_vruntime = cfs_rq->zero_vruntime; + sum_w_vruntime = cfs_rq->sum_w_vruntime; + sum_weight = cfs_rq->sum_weight; + sum_shift = cfs_rq->sum_shift;raw_spin_rq_unlock_irqrestore (rq, flags); SEQ_printf(m, " .%-30s: %Ld.%06ld\n", "left_deadline",@@ -933,6 +940,11 @@ void print_cfs_rq(struct seq_file *m, in SPLIT_NS(left_vruntime));SEQ_printf (m," .%-30s: %Ld.%06ld\n" ,"zero_vruntime" ,SPLIT_NS (zero_vruntime)); +SEQ_printf (m," .%-30s: %Ld (%d bits)\n" ,"sum_w_vruntime" , + sum_w_vruntime,ilog2 (abs (sum_w_vruntime))); +SEQ_printf (m," .%-30s: %Lu\n" ,"sum_weight" , + sum_weight); +SEQ_printf (m," .%-30s: %u\n" ,"sum_shift" , sum_shift);SEQ_printf (m," .%-30s: %Ld.%06ld\n" ,"avg_vruntime" ,SPLIT_NS (avg_vruntime (cfs_rq))); SEQ_printf(m, " .%-30s: %Ld.%06ld\n", "right_vruntime",kernel/sched/fair.c +73
-18@@ -665,15 +665,20 @@ static inline s64 entity_key(struct cfs_* Since zero_vruntime closely tracks the per-task service, these * deltas: (v_i - v0), will be in the order of the maximal (virtual) lag * induced in the system due to quantisation. -* -* Also, we use scale_load_down() to reduce the size. -* -* As measured, the max (key * weight) value was ~44 bits for a kernel build. */ -static void -sum_w_vruntime_add (struct cfs_rq *cfs_rq,struct sched_entity *se) +static inline unsigned long avg_vruntime_weight (struct cfs_rq *cfs_rq,unsigned long w) +{ +#ifdef CONFIG_64BIT +if (cfs_rq->sum_shift) + w =max (2UL , w >> cfs_rq->sum_shift); +#endif +return w; +} + +static inline void +__sum_w_vruntime_add (struct cfs_rq *cfs_rq,struct sched_entity *se) { -unsigned long weight =scale_load_down (se->load.weight); +unsigned long weight =avg_vruntime_weight (cfs_rq, se->load.weight);s64 key =entity_key (cfs_rq, se); cfs_rq->sum_w_vruntime += key * weight;@@ -681,9 +686,59 @@ sum_w_vruntime_add(struct cfs_rq *cfs_rq }static void +sum_w_vruntime_add_paranoid (struct cfs_rq *cfs_rq,struct sched_entity *se) +{ +unsigned long weight; +s64 key, tmp; + +again: + weight =avg_vruntime_weight (cfs_rq, se->load.weight); + key =entity_key (cfs_rq, se); + +if (check_mul_overflow (key, weight, &key)) + goto overflow; + +if (check_add_overflow (cfs_rq->sum_w_vruntime, key, &tmp)) + goto overflow; + + cfs_rq->sum_w_vruntime = tmp; + cfs_rq->sum_weight += weight; +return ; + +overflow: +/* +* There's gotta be a limit -- if we're still failing at this point +* there's really nothing much to be done about things. +*/ +BUG_ON (cfs_rq->sum_shift >=10 ); + cfs_rq->sum_shift++; + +/* +* Note: \Sum (k_i * (w_i >> 1)) != (\Sum (k_i * w_i)) >> 1 +*/ + cfs_rq->sum_w_vruntime =0 ; + cfs_rq->sum_weight =0 ; + +for (struct rb_node *node = cfs_rq->tasks_timeline.rb_leftmost; + node; node =rb_next (node)) +__sum_w_vruntime_add (cfs_rq,__node_2_se (node)); + + goto again; +} + +static void +sum_w_vruntime_add (struct cfs_rq *cfs_rq,struct sched_entity *se) +{ +if (sched_feat (PARANOID_AVG )) +return sum_w_vruntime_add_paranoid (cfs_rq, se); + +__sum_w_vruntime_add (cfs_rq, se); +} + +static void sum_w_vruntime_sub (struct cfs_rq *cfs_rq,struct sched_entity *se) { -unsigned long weight =scale_load_down (se->load.weight); +unsigned long weight =avg_vruntime_weight (cfs_rq, se->load.weight);s64 key =entity_key (cfs_rq, se); cfs_rq->sum_w_vruntime -= key * weight;@@ -725,7 +780,7 @@ u64 avg_vruntime(struct cfs_rq *cfs_rq)s64 runtime = cfs_rq->sum_w_vruntime;if (curr) { -unsigned long w =scale_load_down (curr->load.weight); +unsigned long w =avg_vruntime_weight (cfs_rq, curr->load.weight); runtime +=entity_key (cfs_rq, curr) * w; weight += w;@@ -735,7 +790,7 @@ u64 avg_vruntime(struct cfs_rq *cfs_rq)if (runtime <0 ) runtime -= (weight -1 ); - delta =div_s64 (runtime, weight); + delta =div64_long (runtime, weight); }else if (curr) {/* * When there is but one element, it is the average. @@ -801,7 +856,7 @@ static int vruntime_eligible(struct cfs_long load = cfs_rq->sum_weight;if (curr && curr->on_rq) { -unsigned long weight =scale_load_down (curr->load.weight); +unsigned long weight =avg_vruntime_weight (cfs_rq, curr->load.weight); avg +=entity_key (cfs_rq, curr) * weight; load += weight;@@ -3871,12 +3926,12 @@ static void reweight_entity(struct cfs_r* Because we keep se->vlag = V - v_i, while: lag_i = w_i*(V - v_i), * we need to scale se->vlag when w_i changes. */ - se->vlag =div_s64 (se->vlag * se->load.weight, weight); + se->vlag =div64_long (se->vlag * se->load.weight, weight);if (se->rel_deadline) - se->deadline =div_s64 (se->deadline * se->load.weight, weight); + se->deadline =div64_long (se->deadline * se->load.weight, weight);if (rel_vprot) - vprot =div_s64 (vprot * se->load.weight, weight); + vprot =div64_long (vprot * se->load.weight, weight);update_load_set (&se->load, weight);@@ -5180,7 +5235,7 @@ place_entity(struct cfs_rq *cfs_rq, stru*/ if (sched_feat (PLACE_LAG ) && cfs_rq->nr_queued && se->vlag) {struct sched_entity *curr = cfs_rq->curr; -unsigned long load; +long load; lag = se->vlag;@@ -5238,12 +5293,12 @@ place_entity(struct cfs_rq *cfs_rq, stru*/ load = cfs_rq->sum_weight;if (curr && curr->on_rq) - load +=scale_load_down (curr->load.weight); + load +=avg_vruntime_weight (cfs_rq, curr->load.weight); - lag *= load +scale_load_down (se->load.weight); + lag *= load +avg_vruntime_weight (cfs_rq, se->load.weight);if (WARN_ON_ONCE (!load)) load =1 ; - lag =div_s64 (lag, load); + lag =div64_long (lag, load); } se->vruntime = vruntime - lag;kernel/sched/features.h +2
-0@@ -58,6 +58,8 @@ SCHED_FEAT(CACHE_HOT_BUDDY, true) SCHED_FEAT(DELAY_DEQUEUE, true) SCHED_FEAT(DELAY_ZERO, true) +SCHED_FEAT (PARANOID_AVG , false) +/* * Allow wakeup-time preemption of the current task: */ kernel/sched/sched.h +2
-1@@ -684,8 +684,9 @@ struct cfs_rq {s64 sum_w_vruntime;u64 sum_weight; -u64 zero_vruntime; +unsigned int sum_shift; +#ifdef CONFIG_SCHED_CORE unsigned int forceidle_seq;u64 zero_vruntime_fi;
Peter Zijlstra
maintainerRe: [PATCH v2 5/7] sched/fair: Increase weight bits for avg_vruntime
Quoted 20 lines · Vincent Guittot
Quoted 7 lines · Peter Zijlstra
Due to the
zero_vruntimepatch, the deltas are now a lot smaller and measurement with kernel-build and hackbench runs show about 45 bits used.This ensures
avg_vruntime()tracks the full weight range, reducing numerical artifacts in reweight and the like.Instead of paranoid, would it be better to add
WARN_ONCE?I'm afraid that we will not notice any potential overflow without a long study of the regression with
SCHED_FEAT(PARANOID_AVG, false)Couldn't we add a cheaper
WARN_ONCE(key > 2^50) in__sum_w_vruntime_add?We should always have
key < 110ms (max slice+max tick) *nice_0(2^20) / weight (2) key < 2^46
Quoted 7 lines
We can use 50 bits to get margin
Weight is always less than 27bits and key*weight gives us 110ms (max slice+max tick) *
nice_0(2^20) so we should never add more than 2^47 to ->sum_weightso a
WARN_ONCE(cfs_rq->sum_weight> 2^63) should be enough
Ha, I was >< close to pushing out these patches when I saw this.
The thing is signed, so bit 63 is the sign bit, but I suppose we can test bit 62 like so:
Let me go build and boot that.
kernel/sched/fair.c +6 -2
@@ -679,9 +679,13 @@ static inline void __sum_w_vruntime_add(struct cfs_rq *cfs_rq, struct sched_entity *se) { unsigned long weight = avg_vruntime_weight(cfs_rq, se->load.weight); -s64 key =entity_key (cfs_rq, se); +s64 w_vruntime, key =entity_key (cfs_rq, se); - cfs_rq->sum_w_vruntime += key * weight; + w_vruntime = key * weight; + +WARN_ON_ONCE ((w_vruntime >>63 ) != (w_vruntime >>62 )); + + cfs_rq->sum_w_vruntime += w_vruntime; cfs_rq->sum_weight += weight; }
Peter Zijlstra
maintainerRe: [PATCH v2 5/7] sched/fair: Increase weight bits for avg_vruntime
Quoted 1 line · Peter Zijlstra
Let me go build and boot that.
Seems to not explode; had it run a few things and such. Must be good.
Quoted 18 lines
kernel/sched/fair.c +6
-2@@ -679,9 +679,13 @@ static inline void __sum_w_vruntime_add(struct cfs_rq *cfs_rq, struct sched_entity *se) { unsigned long weight = avg_vruntime_weight(cfs_rq, se->load.weight); -s64 key =entity_key (cfs_rq, se); +s64 w_vruntime, key =entity_key (cfs_rq, se); - cfs_rq->sum_w_vruntime += key * weight; + w_vruntime = key * weight; + +WARN_ON_ONCE ((w_vruntime >>63 ) != (w_vruntime >>62 )); + + cfs_rq->sum_w_vruntime += w_vruntime; cfs_rq->sum_weight += weight; }
Vincent Guittot
maintainerRe: [PATCH v2 5/7] sched/fair: Increase weight bits for avg_vruntime
In reply to Peter ZijlstraQuoted 28 lines · Peter Zijlstra
Quoted 26 lines · Vincent Guittot
Quoted 7 lines · Peter Zijlstra
Due to the
zero_vruntimepatch, the deltas are now a lot smaller and measurement with kernel-build and hackbench runs show about 45 bits used.This ensures
avg_vruntime()tracks the full weight range, reducing numerical artifacts in reweight and the like.Instead of paranoid, would it be better to add
WARN_ONCE?I'm afraid that we will not notice any potential overflow without a long study of the regression with
SCHED_FEAT(PARANOID_AVG, false)Couldn't we add a cheaper
WARN_ONCE(key > 2^50) in__sum_w_vruntime_add?We should always have
key < 110ms (max slice+max tick) *nice_0(2^20) / weight (2) key < 2^46We can use 50 bits to get margin
Weight is always less than 27bits and key*weight gives us 110ms (max slice+max tick) *
nice_0(2^20) so we should never add more than 2^47 to ->sum_weight
Quoted 6 lines
Quoted 1 line
so a
WARN_ONCE(cfs_rq->sum_weight> 2^63) should be enoughHa, I was >< close to pushing out these patches when I saw this.
The thing is signed, so bit 63 is the sign bit, but I suppose we can test bit 62 like so:
Ah yes, I forgot that it's a signed value
Quoted 6 lines
Let me go build and boot that.
kernel/sched/fair.c static inline void · line 686
Quoted 10 lines
kernel/sched/fair.c +4
-2@@ -679,9 +679,13 @@ static inline void __sum_w_vruntime_add(struct cfs_rq *cfs_rq, struct sched_entity *se) { unsigned long weight = avg_vruntime_weight(cfs_rq, se->load.weight); -s64 key =entity_key (cfs_rq, se); +s64 w_vruntime, key =entity_key (cfs_rq, se); - cfs_rq->sum_w_vruntime += key * weight; + w_vruntime = key * weight; + +WARN_ON_ONCE ((w_vruntime >>63 ) != (w_vruntime >>62 ));
yes looks good
Quoted 5 lines
kernel/sched/fair.c +2
-0+ + cfs_rq->sum_w_vruntime += w_vruntime; cfs_rq->sum_weight += weight; }
K Prateek Nayak
reviewerRe: [PATCH v2 5/7] sched/fair: Increase weight bits for avg_vruntime
In reply to Peter ZijlstraQuoted 22 lines · Peter Zijlstra
Quoted 11 lines
We should always have
key < 110ms (max slice+max tick) *nice_0(2^20) / weight (2) key < 2^46We can use 50 bits to get margin
Weight is always less than 27bits and key*weight gives us 110ms (max slice+max tick) *
nice_0(2^20) so we should never add more than 2^47 to ->sum_weightso a
WARN_ONCE(cfs_rq->sum_weight> 2^63) should be enoughHa, I was >< close to pushing out these patches when I saw this.
The thing is signed, so bit 63 is the sign bit, but I suppose we can test bit 62 like so:
Let me go build and boot that.
kernel/sched/fair.c static inline void · line 686
Quoted 10 lines
kernel/sched/fair.c +4
-2@@ -679,9 +679,13 @@ static inline void __sum_w_vruntime_add(struct cfs_rq *cfs_rq, struct sched_entity *se) { unsigned long weight = avg_vruntime_weight(cfs_rq, se->load.weight); -s64 key =entity_key (cfs_rq, se); +s64 w_vruntime, key =entity_key (cfs_rq, se); - cfs_rq->sum_w_vruntime += key * weight; + w_vruntime = key * weight; + +WARN_ON_ONCE ((w_vruntime >>63 ) != (w_vruntime >>62 ));
I was trying to reproduce the crash that John mentioned on the Patch 1 and although I couldn't reproduce that crash (yet), I tripped this when running stress-ng yield test (32 copies x 256 children + sched messaging 16 groups) on my dual socket system (2 x 64C/128T):
------------[ cut here ]------------
(w_vruntime >> 63) != (w_vruntime >> 62)
WARNING: kernel/sched/fair.c:692 at __enqueue_entity+0x382/0x3a0, CPU#5: stress-ng/5062
Modules linked in: ...
CPU: 5 UID: 1000 PID: 5062 Comm: stress-ng Not tainted 7.0.0-rc5-topo-test+ #40 PREEMPT(full)
Hardware name: Dell Inc. PowerEdge R6525/024PW1, BIOS 2.7.3 03/30/2022
RIP: 0010:__enqueue_entity+0x382/0x3a0
Code: 4c 89 4b 48 4c 89 4b 50 e9 61 fe ff ff 83 f9 3f 0f 87 b8 27 e5 ff 49 d3 ec b8 02 00 00 00 49 39 c4 4c 0f 42 e0 e9 16 ff ff ff <0f> 0b e9 d8 fc ff ff 0f 0b e9 e1 fe ff ff 0f 0b 66 66 2e 0f 1f 84
RSP: 0018:ffffcf6b8ea88c18 EFLAGS: 00010002
RAX: bf38ba3b09dc2400 RBX: ffff8d546f832680 RCX: ffffffffffffffff
RDX: fffffffffffffffe RSI: ffff8d1587818080 RDI: ffff8d546f832680
RBP: ffff8d1587818080 R08: 000000000000002d R09: 00000000ffffffff
R10: 0000000000000001 R11: ffffcf6b8ea88ff8 R12: 00000000056ae400
R13: ffff8d1587818080 R14: 0000000000000001 R15: ffff8d546f832680
FS: 00007f8c742c9740(0000) GS:ffff8d54b0c82000(0000) knlGS:0000000000000000
CS: 0010 DS: 0000 ES: 0000 CR0: 0000000080050033
CR2: 00007f2e09381358 CR3: 00000040db039002 CR4: 0000000000f70ef0
PKRU: 55555554
Call Trace:
<IRQ>
enqueue_task_fair+0x1a3/0xe50
? srso_alias_return_thunk+0x5/0xfbef5
? place_entity+0x21/0x160
enqueue_task+0x88/0x1b0
ttwu_do_activate+0x74/0x1c0
try_to_wake_up+0x277/0x840
...
asm_sysvec_call_function_single+0x1a/0x20
RIP: 0010:do_sched_yield+0x73/0xa0
Code: 89 df 48 8b 80 e8 02 00 00 48 8b 40 18 e8 75 a9 fd 00 65 ff 05 9e 94 fc 02 66 90 48 8d 7b 48 e8 d3 96 fd 00 fb 0f 1f 44 00 00 <65> ff 0d 86 94 fc 02 5b e9 10 12 fd 00 83 83 70 0d 00 00 01 eb bb
RSP: 0018:ffffcf6b9b7bbd78 EFLAGS: 00000282
RAX: ffffffffbbbb4560 RBX: ffff8d546f832580 RCX: 0000000000000000
RDX: 0000000000000001 RSI: 0000000000000000 RDI: ffff8d546f8325c8
RBP: ffffcf6b9b7bbf38 R08: 0000000000000000 R09: 0000000000000000
R10: 0000000000000000 R11: 0000000000000000 R12: ffff8d15d1070000
R13: 0000000000000018 R14: 0000000000000000 R15: 0000000000000018
? __pfx_yield_task_fair+0x10/0x10
? do_sched_yield+0x6d/0xa0
__do_sys_sched_yield+0xe/0x20
...Since this wasn't suppose to trip, I'm assuming we are somehow in the wrap around territory again :-(
I don't see anything particularly interesting in the sched/debug entry after the fact:
cfs_rq[5]:/user.slice
.left_deadline : 26249498461.397509 .left_vruntime : 26249498270.250843 .zero_vruntime : 26249456859.395628 .sum_w_vruntime : 2547538312135680 (51 bits) .sum_weight : 61440 .sum_shift : 0 .avg_vruntime : 26249498338.158417 .right_vruntime : 26249498381.633124 .spread : 111.382281 .nr_queued : 5 .h_nr_runnable : 5 .h_nr_queued : 5 .h_nr_idle : 0
...
I still haven't figured out how this happens I'll start running with some debug prints next.
On a tangential note, now that we only yield on eligibility, would something like below make sense?
kernel/sched/fair.c +3 -2
@@ -9265,9 +9265,10 @@ static void yield_task_fair(struct rq *rq)struct sched_entity *se = &curr->se;/* -* Are we the only task in the tree? +* Single task is always eligible on the cfs_rq. +* Don't pull the vruntime needlessly. */ -if (unlikely (rq->nr_running ==1 )) +if (unlikely (cfs_rq->nr_queued ==1 ))return ;clear_buddies (cfs_rq, se);
Signature · 2 lines
Thanks and Regards, Prateek
Peter Zijlstra
maintainerRe: [PATCH v2 5/7] sched/fair: Increase weight bits for avg_vruntime
Quoted 10 lines · K Prateek Nayak
On a tangential note, now that we only yield on eligibility, would something like below make sense?
kernel/sched/fair.c +0
-0@@ -9265,9 +9265,10 @@ static void yield_task_fair(struct rq *rq)struct sched_entity *se = &curr->se;
kernel/sched/fair.c static void yield_task_fair(struct rq *rq) · line 9274
Quoted 10 lines
kernel/sched/fair.c +3
-2/* -* Are we the only task in the tree? +* Single task is always eligible on the cfs_rq. +* Don't pull the vruntime needlessly. */ -if (unlikely (rq->nr_running ==1 )) +if (unlikely (cfs_rq->nr_queued ==1 ))return ;clear_buddies (cfs_rq, se);
Right, with the addition of sched_ext this could actually make a difference.
K Prateek Nayak
reviewerRe: [PATCH v2 5/7] sched/fair: Increase weight bits for avg_vruntime
In reply to K Prateek NayakQuoted 3 lines · K Prateek Nayak
------------[ cut here ]------------
(w_vruntime >> 63) != (w_vruntime >> 62)
WARNING: kernel/sched/fair.c:692 at __enqueue_entity+0x382/0x3a0, CPU#5: stress-ng/5062Back to this: I still see this with latest set of changes on queue:sched/urgent but it doesn't go kaboom. Nonetheless, it suggests we are closing in on the s64 limitations of "sum_w_vruntime" which isn't very comforting.
Here is one scenario where it was triggered when running:
stress-ng --yield=32 -t 10000000s&
while true; do perf bench sched messaging -p -t -l 100000 -g 16; done
on a 256CPUs machine after about an hour into the run:
__enqeue_entity: entity_key(-141245081754) weight(90891264) overflow_mul(5608800059305154560) vlag(57498) delayed?(0)
cfs_rq: zero_vruntime(3809707759657809) sum_w_vruntime(0) sum_weight(0) nr_queued(1)
cfs_rq->curr: entity_key(0) vruntime(3809707759657809) deadline(3809723966988476) weight(37)The above comes from __enqueue_entity() after a place_entity(). Breaking this down:
vlag_initial = 57498
vlag = (57498 * (37 + 90891264)) / 37 = 141,245,081,754
vruntime = 3809707759657809 - 141245081754 = 3,809,566,514,576,055
entity_key(se, cfs_rq) = -141,245,081,754Now, multiplying the entity_key with its own weight results to 5,608,800,059,305,154,560 (same as what overflow_mul() suggests) but in Python, without overflow, this would be: -1,2837,944,014,404,397,056
Now, the fact that it doesn't crash suggests to me the later avg_vruntime() calculation would restore normality and the sum_w_vruntime turns to -57498 (vlag_initial) * 90891264 (weight) = -5,226,065,897,472 (assuming curr's vruntime is still the same) which only requires 43 bits.
I also added the following at the bottom of dequeue_entity():
WARN_ON_ONCE(!cfs_rq->nr_queued && cfs_rq->sum_w_vruntime)
which was never triggered when the cfs_rq goes idle so it isn't like we didn't account sum_w_vruntime properly. There was just a momentary overflow so we are fine but will it always be that way?
One way to avoid the warning entirely would be to pull the zero_vruntime close to avg_vruntime is we are enqueuing a very heavy entity.
The correct way to do this would be to compute the actual avg_vruntime() and move the zero_vruntime to that point (but that requires at least one multiply + divide + update_zero_vruntime()).
One seemingly cheap way by which I've been able to avoid the warning is with:
kernel/sched/fair.c +15 -0
@@ -5329,6 +5329,7 @@ static void place_entity(struct cfs_rq *cfs_rq, struct sched_entity *se, int flags) { u64 vslice, vruntime = avg_vruntime(cfs_rq); +bool update_zero = false;s64 lag =0 ;if (!se->custom_slice)
@@ -5406,6 +5407,17 @@ place_entity(struct cfs_rq *cfs_rq, struct sched_entity *se, int flags) load +=avg_vruntime_weight (cfs_rq, curr->load.weight); lag *= load +avg_vruntime_weight (cfs_rq, se->load.weight); +/* +* If the entity_key() * sum_weight of all the enqueued entities +* is more than the sum_w_vruntime, move the zero_vruntime +* point to the vruntime of the entity which prevents using +* more bits than necessary for sum_w_vruntime until the +* next avg_vruntime(). +* +* XXX: Cheap enough check? +*/ +if (abs (lag) >abs (cfs_rq->sum_w_vruntime)) + update_zero = true;if (WARN_ON_ONCE (!load)) load =1 ; lag =div64_long (lag, load);
@@ -5413,6 +5425,9 @@ place_entity(struct cfs_rq *cfs_rq, struct sched_entity *se, int flags) se->vruntime = vruntime - lag; +if (update_zero) +update_zero_vruntime (cfs_rq, -lag); +if (sched_feat (PLACE_REL_DEADLINE ) && se->rel_deadline) { se->deadline += se->vruntime; se->rel_deadline =0 ;
---
But I'm sure it'll make people nervous since we basically move the zero_vruntime to se->vruntime. It isn't too bad if:
abs(sum_w_vuntime - (lag * load)) < abs(lag * se->load.weight)
but we already know that the latter overflows so is there any other cheaper indicator that we can use to detect the necessity to adjust the avg_vruntime beforehand at place_entity()?
Signature · 2 lines
Thanks and Regards, Prateek
Peter Zijlstra
maintainerRe: [PATCH v2 5/7] sched/fair: Increase weight bits for avg_vruntime
Quoted 9 lines · K Prateek Nayak
Quoted 3 lines · K Prateek Nayak
------------[ cut here ]------------ (w_vruntime >> 63) != (w_vruntime >> 62) WARNING: kernel/sched/fair.c:692 at __enqueue_entity+0x382/0x3a0, CPU#5: stress-ng/5062Back to this: I still see this with latest set of changes on queue:sched/urgent but it doesn't go kaboom. Nonetheless, it suggests we are closing in on the s64 limitations of "
sum_w_vruntime" which isn't very comforting.
Yeah, we are pushing 64bit pretty hard :/ And if all we would care about was x86_64 I'd have long since used the fact that imul has a 128bit result and idiv actually divides 128bit. But even among 64bit architectures that is somewhat rare :/
Quoted 20 lines
Here is one scenario where it was triggered when running:
stress-ng --yield=32 -t 10000000s&
while true; do perf bench sched messaging -p -t -l 100000 -g 16; doneon a 256CPUs machine after about an hour into the run:
__enqeue_entity: entity_key(-141245081754) weight(90891264) overflow_mul(5608800059305154560) vlag(57498) delayed?(0) cfs_rq: zero_vruntime(3809707759657809) sum_w_vruntime(0) sum_weight(0) nr_queued(1) cfs_rq->curr: entity_key(0) vruntime(3809707759657809) deadline(3809723966988476) weight(37)The above comes from
__enqueue_entity()after aplace_entity(). Breaking this down:vlag_initial = 57498 vlag = (57498 * (37 + 90891264)) / 37 = 141,245,081,754 vruntime = 3809707759657809 - 141245081754 = 3,809,566,514,576,055 entity_key(se, cfs_rq) = -141,245,081,754
Quoted 3 lines
Now, multiplying the
entity_keywith its own weight results to 5,608,800,059,305,154,560 (same as whatoverflow_mul()suggests) but in Python, without overflow, this would be: -1,2837,944,014,404,397,056
Oh gawd, this is a 'fun' case.
Quoted 52 lines
One way to avoid the warning entirely would be to pull the
zero_vruntimeclose toavg_vruntimeis we are enqueuing a very heavy entity.The correct way to do this would be to compute the actual
avg_vruntime()and move thezero_vruntimeto that point (but that requires at least one multiply + divide +update_zero_vruntime()).One seemingly cheap way by which I've been able to avoid the warning is with:
kernel/sched/fair.c +15
-1@@ -5329,6 +5329,7 @@ static void place_entity(struct cfs_rq *cfs_rq, struct sched_entity *se, int flags) { u64 vslice, vruntime = avg_vruntime(cfs_rq); +bool update_zero = false;s64 lag =0 ;if (!se->custom_slice)@@ -5406,6 +5407,17 @@ place_entity(struct cfs_rq *cfs_rq, struct sched_entity *se, int flags) load +=avg_vruntime_weight (cfs_rq, curr->load.weight); lag *= load +avg_vruntime_weight (cfs_rq, se->load.weight); +/* +* If the entity_key() * sum_weight of all the enqueued entities +* is more than the sum_w_vruntime, move the zero_vruntime +* point to the vruntime of the entity which prevents using +* more bits than necessary for sum_w_vruntime until the +* next avg_vruntime(). +* +* XXX: Cheap enough check? +*/ +if (abs (lag) >abs (cfs_rq->sum_w_vruntime)) + update_zero = true;if (WARN_ON_ONCE (!load)) load =1 ; lag =div64_long (lag, load);@@ -5413,6 +5425,9 @@ place_entity(struct cfs_rq *cfs_rq, struct sched_entity *se, int flags) se->vruntime = vruntime - lag; +if (update_zero) +update_zero_vruntime (cfs_rq, -lag); +if (sched_feat (PLACE_REL_DEADLINE ) && se->rel_deadline) { se->deadline += se->vruntime; se->rel_deadline =0 ; ---
Quoted 8 lines
But I'm sure it'll make people nervous since we basically move the
zero_vruntimetose->vruntime. It isn't too bad if:abs(sum_w_vuntime - (lag * load)) < abs(lag * se->load.weight)but we already know that the latter overflows so is there any other cheaper indicator that we can use to detect the necessity to adjust the
avg_vruntimebeforehand atplace_entity()?
So in general I think it would be fine to move zero_vruntime to the heaviest entity in the tree. And if there are multiple equal heaviest weights, any one of them should be fine.
Per necessity heavy entities are more tightly clustered -- the lag is inversely proportional to weight, and the spread is proportional to the lag bound.
I suspect something simple like comparing the entity weight against the sum_weight might be enough. If the pre-existing tree is, in aggregate, heavier than the new element, the avg will not move very drastically. However, if the new element is (significantly) heavier than the tree, the avg will move significantly (as demonstrated here).
That is, something like the below... But with a comment ofc :-)
Does that make sense?
kernel/sched/fair.c +10 -2
@@ -5329,6 +5329,7 @@ static void place_entity(struct cfs_rq *cfs_rq, struct sched_entity *se, int flags) { u64 vslice, vruntime = avg_vruntime(cfs_rq); +bool update_zero = false;s64 lag =0 ;if (!se->custom_slice)
@@ -5345,7 +5346,7 @@ place_entity(struct cfs_rq *cfs_rq, struct sched_entity *se, int flags)*/ if (sched_feat (PLACE_LAG ) && cfs_rq->nr_queued && se->vlag) {struct sched_entity *curr = cfs_rq->curr; -long load; +long load, weight; lag = se->vlag;
@@ -5405,14 +5406,21 @@ place_entity(struct cfs_rq *cfs_rq, struct sched_entity *se, int flags)if (curr && curr->on_rq) load +=avg_vruntime_weight (cfs_rq, curr->load.weight); - lag *= load +avg_vruntime_weight (cfs_rq, se->load.weight); + weight =avg_vruntime_weight (cfs_rq, se->load.weight); + lag *= load + weight;if (WARN_ON_ONCE (!load)) load =1 ; lag =div64_long (lag, load); + +if (weight > load) + update_zero = true; } se->vruntime = vruntime - lag; +if (update_zero) +update_zero_vruntime (cfs_rq, -lag); +if (sched_feat (PLACE_REL_DEADLINE ) && se->rel_deadline) { se->deadline += se->vruntime; se->rel_deadline =0 ;
K Prateek Nayak
reviewerRe: [PATCH v2 5/7] sched/fair: Increase weight bits for avg_vruntime
Hello Peter,
Quoted 11 lines · Peter Zijlstra
Quoted 9 lines · K Prateek Nayak
Quoted 3 lines · K Prateek Nayak
------------[ cut here ]------------ (w_vruntime >> 63) != (w_vruntime >> 62) WARNING: kernel/sched/fair.c:692 at __enqueue_entity+0x382/0x3a0, CPU#5: stress-ng/5062Back to this: I still see this with latest set of changes on queue:sched/urgent but it doesn't go kaboom. Nonetheless, it suggests we are closing in on the s64 limitations of "
sum_w_vruntime" which isn't very comforting.
Quoted 4 lines
Yeah, we are pushing 64bit pretty hard :/ And if all we would care about was
x86_64I'd have long since used the fact that imul has a 128bit result and idiv actually divides 128bit. But even among 64bit architectures that is somewhat rare :/
Guess we have to make do with what is more abundant. We haven't crashed and burnt yet so it should be a fun debug for future us when we get there :-)
Quoted 102 lines
Quoted 21 lines
Here is one scenario where it was triggered when running:
stress-ng --yield=32 -t 10000000s&
while true; do perf bench sched messaging -p -t -l 100000 -g 16; doneon a 256CPUs machine after about an hour into the run:
__enqeue_entity: entity_key(-141245081754) weight(90891264) overflow_mul(5608800059305154560) vlag(57498) delayed?(0) cfs_rq: zero_vruntime(3809707759657809) sum_w_vruntime(0) sum_weight(0) nr_queued(1) cfs_rq->curr: entity_key(0) vruntime(3809707759657809) deadline(3809723966988476) weight(37)The above comes from
__enqueue_entity()after aplace_entity(). Breaking this down:vlag_initial = 57498 vlag = (57498 * (37 + 90891264)) / 37 = 141,245,081,754 vruntime = 3809707759657809 - 141245081754 = 3,809,566,514,576,055 entity_key(se, cfs_rq) = -141,245,081,754Quoted 3 lines
Now, multiplying the
entity_keywith its own weight results to 5,608,800,059,305,154,560 (same as whatoverflow_mul()suggests) but in Python, without overflow, this would be: -1,2837,944,014,404,397,056Oh gawd, this is a 'fun' case.
Quoted 52 lines
One way to avoid the warning entirely would be to pull the
zero_vruntimeclose toavg_vruntimeis we are enqueuing a very heavy entity.The correct way to do this would be to compute the actual
avg_vruntime()and move thezero_vruntimeto that point (but that requires at least one multiply + divide +update_zero_vruntime()).One seemingly cheap way by which I've been able to avoid the warning is with:
kernel/sched/fair.c +15
-1@@ -5329,6 +5329,7 @@ static void place_entity(struct cfs_rq *cfs_rq, struct sched_entity *se, int flags) { u64 vslice, vruntime = avg_vruntime(cfs_rq); +bool update_zero = false;s64 lag =0 ;if (!se->custom_slice)@@ -5406,6 +5407,17 @@ place_entity(struct cfs_rq *cfs_rq, struct sched_entity *se, int flags) load +=avg_vruntime_weight (cfs_rq, curr->load.weight); lag *= load +avg_vruntime_weight (cfs_rq, se->load.weight); +/* +* If the entity_key() * sum_weight of all the enqueued entities +* is more than the sum_w_vruntime, move the zero_vruntime +* point to the vruntime of the entity which prevents using +* more bits than necessary for sum_w_vruntime until the +* next avg_vruntime(). +* +* XXX: Cheap enough check? +*/ +if (abs (lag) >abs (cfs_rq->sum_w_vruntime)) + update_zero = true;if (WARN_ON_ONCE (!load)) load =1 ; lag =div64_long (lag, load);@@ -5413,6 +5425,9 @@ place_entity(struct cfs_rq *cfs_rq, struct sched_entity *se, int flags) se->vruntime = vruntime - lag; +if (update_zero) +update_zero_vruntime (cfs_rq, -lag); +if (sched_feat (PLACE_REL_DEADLINE ) && se->rel_deadline) { se->deadline += se->vruntime; se->rel_deadline =0 ; ---Quoted 8 lines
But I'm sure it'll make people nervous since we basically move the
zero_vruntimetose->vruntime. It isn't too bad if:abs(sum_w_vuntime - (lag * load)) < abs(lag * se->load.weight)but we already know that the latter overflows so is there any other cheaper indicator that we can use to detect the necessity to adjust the
avg_vruntimebeforehand atplace_entity()?So in general I think it would be fine to move
zero_vruntimeto the heaviest entity in the tree. And if there are multiple equal heaviest weights, any one of them should be fine.Per necessity heavy entities are more tightly clustered -- the lag is inversely proportional to weight, and the spread is proportional to the lag bound.
I suspect something simple like comparing the entity weight against the
sum_weightmight be enough. If the pre-existing tree is, in aggregate, heavier than the new element, the avg will not move very drastically. However, if the new element is (significantly) heavier than the tree, the avg will move significantly (as demonstrated here).
Quoted 3 lines
That is, something like the below... But with a comment ofc :-)
Does that make sense?
Let me go queue an overnight test to see if I trip that warning or not. I initially did think this might work but then convinced myself that testing the spread with "sum_w_vruntime" might prove to be better but we'll know for sure tomorrow ;-)
Signature · 2 lines
Thanks and Regards, Prateek
Re: [PATCH v2 5/7] sched/fair: Increase weight bits for avg_vruntime
Quoted 6 lines · K Prateek Nayak
Quoted 3 lines
That is, something like the below... But with a comment ofc :-)
Does that make sense?
Let me go queue an overnight test to see if I trip that warning or not.
Didn't trip any warning and the machine is still up and running after 15 Hours so feel free to include:
Perhaps the comment can read something like:
/*
* A heavy entity can pull the avg_vruntime close to its
* vruntime post enqueue but the zero_vruntime point is
* only updated at the next update_deadline() / enqueue
* / dequeue.
*
* Until then, the sum_w_vruntime grow quadratically,
* proportional to the entity's weight (w_i) as:
*
* sum_w_vruntime -= (lag_i * (W + w_i) / W) * w_i
*
* If w_i > W, it is beneficial to pull the
* zero_vruntime towards the entity's vruntime (V_i)
* since the sum_w_vruntime would only grow by
* (lag_i * W) which consumes lesser bits than leaving
* the zero_vruntime at the pre-enqueue avg_vruntime. */
if (weight > load)
update_zero = true;
Feel free to reword as you see fit :-)
Signature · 2 lines
Thanks and Regards, Prateek
Peter Zijlstra
maintainerRe: [PATCH v2 5/7] sched/fair: Increase weight bits for avg_vruntime
Quoted 35 lines · K Prateek Nayak
Quoted 6 lines · K Prateek Nayak
Quoted 3 lines
That is, something like the below... But with a comment ofc :-)
Does that make sense?
Let me go queue an overnight test to see if I trip that warning or not.
Didn't trip any warning and the machine is still up and running after 15 Hours so feel free to include:
Tested-by K Prateek Nayak <[email protected]>Perhaps the comment can read something like:
/*
* A heavy entity can pull theavg_vruntimeclose to its
* vruntime post enqueue but thezero_vruntimepoint is
* only updated at the nextupdate_deadline()/ enqueue
* / dequeue.
*
* Until then, thesum_w_vruntimegrow quadratically,
* proportional to the entity's weight (w_i) as:
*
*sum_w_vruntime-= (lag_i* (W +w_i) / W) *w_i
*
* Ifw_i> W, it is beneficial to pull the
*zero_vruntimetowards the entity's vruntime (V_i)
* since thesum_w_vruntimewould only grow by
* (lag_i* W) which consumes lesser bits than leaving
* thezero_vruntimeat the pre-enqueueavg_vruntime. */
if (weight > load)
update_zero= true;
Quoted 1 line
Feel free to reword as you see fit :-)
I've made it like so. You did all the hard work after all. Thanks!
---
Subject: sched/fair: Avoid overflow in enqueue_entity()
From: K Prateek Nayak <[email protected]>
Date: Tue Apr 7 13:36:17 CEST 2026
Here is one scenario which was triggered when running:
stress-ng --yield=32 -t 10000000s&
while true; do perf bench sched messaging -p -t -l 100000 -g 16; done
on a 256CPUs machine after about an hour into the run:
__enqeue_entity: entity_key(-141245081754) weight(90891264) overflow_mul(5608800059305154560) vlag(57498) delayed?(0)
cfs_rq: zero_vruntime(3809707759657809) sum_w_vruntime(0) sum_weight(0) nr_queued(1)
cfs_rq->curr: entity_key(0) vruntime(3809707759657809) deadline(3809723966988476) weight(37)The above comes from __enqueue_entity() after a place_entity(). Breaking this down:
vlag_initial = 57498
vlag = (57498 * (37 + 90891264)) / 37 = 141,245,081,754
vruntime = 3809707759657809 - 141245081754 = 3,809,566,514,576,055
entity_key(se, cfs_rq) = -141,245,081,754Now, multiplying the entity_key with its own weight results to 5,608,800,059,305,154,560 (same as what overflow_mul() suggests) but in Python, without overflow, this would be: -1,2837,944,014,404,397,056
Avoid the overflow (without doing the division for avg_vruntime()), by moving zero_vruntime to the new entity when it is heavier.
--- kernel/sched/fair.c | 32 ++++++++++++++++++++++++++++++-- 1 file changed, 30 insertions(+), 2 deletions(-)
kernel/sched/fair.c +30 -2
@@ -5352,6 +5352,7 @@ static void place_entity(struct cfs_rq *cfs_rq, struct sched_entity *se, int flags) { u64 vslice, vruntime = avg_vruntime(cfs_rq); +bool update_zero = false;s64 lag =0 ;if (!se->custom_slice)
@@ -5368,7 +5369,7 @@ place_entity(struct cfs_rq *cfs_rq, stru*/ if (sched_feat (PLACE_LAG ) && cfs_rq->nr_queued && se->vlag) {struct sched_entity *curr = cfs_rq->curr; -long load; +long load, weight; lag = se->vlag;
@@ -5428,14 +5429,41 @@ place_entity(struct cfs_rq *cfs_rq, struif (curr && curr->on_rq) load +=avg_vruntime_weight (cfs_rq, curr->load.weight); - lag *= load +avg_vruntime_weight (cfs_rq, se->load.weight); + weight =avg_vruntime_weight (cfs_rq, se->load.weight); + lag *= load + weight;if (WARN_ON_ONCE (!load)) load =1 ; lag =div64_long (lag, load); + +/* +* A heavy entity (relative to the tree) will pull the +* avg_vruntime close to its vruntime position on enqueue. But +* the zero_vruntime point is only updated at the next +* update_deadline()/place_entity()/update_entity_lag(). +* +* Specifically (see the comment near avg_vruntime_weight()): +* +* sum_w_vruntime = \Sum (v_i - v0) * w_i +* +* Note that if v0 is near a light entity, both terms will be +* small for the light entity, while in that case both terms +* are large for the heavy entity, leading to risk of +* overflow. +* +* OTOH if v0 is near the heavy entity, then the difference is +* larger for the light entity, but the factor is small, while +* for the heavy entity the difference is small but the factor +* is large. Avoiding the multiplication overflow. +*/ +if (weight > load) + update_zero = true; } se->vruntime = vruntime - lag; +if (update_zero) +update_zero_vruntime (cfs_rq, -lag); +if (sched_feat (PLACE_REL_DEADLINE ) && se->rel_deadline) { se->deadline += se->vruntime; se->rel_deadline =0 ;
[tip: sched/core] sched/fair: Avoid overflow in enqueue_entity()
The following commit has been merged into the sched/core branch of tip:
The following commit has been merged into the sched/core branch of tip:
Commit-ID: 556146ce5e9476db234134c46ddf0e154ca17028 Gitweb: https://git.kernel.org/tip/556146ce5e9476db234134c46ddf0e154ca17028 Author: K Prateek Nayak <[email protected]> AuthorDate: Tue, 07 Apr 2026 13:36:17 +02:00 Committer: Peter Zijlstra <[email protected]> CommitterDate: Tue, 07 Apr 2026 14:02:00 +02:00
sched/fair: Avoid overflow in enqueue_entity()
Here is one scenario which was triggered when running:
stress-ng --yield=32 -t 10000000s&
while true; do perf bench sched messaging -p -t -l 100000 -g 16; done
on a 256CPUs machine after about an hour into the run:
__enqeue_entity: entity_key(-141245081754) weight(90891264) overflow_mul(5608800059305154560) vlag(57498) delayed?(0)
cfs_rq: zero_vruntime(3809707759657809) sum_w_vruntime(0) sum_weight(0) nr_queued(1)
cfs_rq->curr: entity_key(0) vruntime(3809707759657809) deadline(3809723966988476) weight(37)The above comes from __enqueue_entity() after a place_entity(). Breaking this down:
vlag_initial = 57498
vlag = (57498 * (37 + 90891264)) / 37 = 141,245,081,754
vruntime = 3809707759657809 - 141245081754 = 3,809,566,514,576,055
entity_key(se, cfs_rq) = -141,245,081,754Now, multiplying the entity_key with its own weight results to 5,608,800,059,305,154,560 (same as what overflow_mul() suggests) but in Python, without overflow, this would be: -1,2837,944,014,404,397,056
Avoid the overflow (without doing the division for avg_vruntime()), by moving zero_vruntime to the new entity when it is heavier.
--- kernel/sched/fair.c | 32 ++++++++++++++++++++++++++++++-- 1 file changed, 30 insertions(+), 2 deletions(-)
kernel/sched/fair.c +30 -2
@@ -5352,6 +5352,7 @@ static void place_entity(struct cfs_rq *cfs_rq, struct sched_entity *se, int flags) { u64 vslice, vruntime = avg_vruntime(cfs_rq); +bool update_zero = false;s64 lag =0 ;if (!se->custom_slice)
@@ -5368,7 +5369,7 @@ place_entity(struct cfs_rq *cfs_rq, struct sched_entity *se, int flags)*/ if (sched_feat (PLACE_LAG ) && cfs_rq->nr_queued && se->vlag) {struct sched_entity *curr = cfs_rq->curr; -long load; +long load, weight; lag = se->vlag;
@@ -5428,14 +5429,41 @@ place_entity(struct cfs_rq *cfs_rq, struct sched_entity *se, int flags)if (curr && curr->on_rq) load +=avg_vruntime_weight (cfs_rq, curr->load.weight); - lag *= load +avg_vruntime_weight (cfs_rq, se->load.weight); + weight =avg_vruntime_weight (cfs_rq, se->load.weight); + lag *= load + weight;if (WARN_ON_ONCE (!load)) load =1 ; lag =div64_long (lag, load); + +/* +* A heavy entity (relative to the tree) will pull the +* avg_vruntime close to its vruntime position on enqueue. But +* the zero_vruntime point is only updated at the next +* update_deadline()/place_entity()/update_entity_lag(). +* +* Specifically (see the comment near avg_vruntime_weight()): +* +* sum_w_vruntime = \Sum (v_i - v0) * w_i +* +* Note that if v0 is near a light entity, both terms will be +* small for the light entity, while in that case both terms +* are large for the heavy entity, leading to risk of +* overflow. +* +* OTOH if v0 is near the heavy entity, then the difference is +* larger for the light entity, but the factor is small, while +* for the heavy entity the difference is small but the factor +* is large. Avoiding the multiplication overflow. +*/ +if (weight > load) + update_zero = true; } se->vruntime = vruntime - lag; +if (update_zero) +update_zero_vruntime (cfs_rq, -lag); +if (sched_feat (PLACE_REL_DEADLINE ) && se->rel_deadline) { se->deadline += se->vruntime; se->rel_deadline =0 ;
Peter Zijlstra
maintainerPATCH v2 6/7 sched/fair: Revert 6d71a9c61604 ("sched/fair: Fix EEVDF entity placement bug causing scheduling lag")
In reply to Peter ZijlstraZicheng Qu reported that, because avg_vruntime() always includes cfs_rq->curr, when ->on_rq, place_entity() doesn't work right.
Specifically, the lag scaling in place_entity() relies on avg_vruntime() being the state *before* placement of the new entity. However in this case avg_vruntime() will actually already include the entity, which breaks things.
Also, Zicheng Qu argues that avg_vruntime should be invariant under reweight. IOW commit 6d71a9c61604 ("sched/fair: Fix EEVDF entity placement bug causing scheduling lag") was wrong!
The issue reported in 6d71a9c61604 could possibly be explained by rounding artifacts -- notably the extreme weight '2' is outside of the range of avg_vruntime/sum_w_vruntime, since that uses scale_load_down(). By scaling vruntime by the real weight, but accounting it in vruntime with a factor 1024 more, the average moves significantly. However, that is now cured.
Tested by reverting 66951e4860d3 ("sched/fair: Fix update_cfs_group() vs DELAY_DEQUEUE") and tracing vruntime and vlag figures again.
--- kernel/sched/fair.c | 148 +++++++++++++++++++++++++++++++++++++++++++--------- 1 file changed, 124 insertions(+), 24 deletions(-)
kernel/sched/fair.c +124 -24
@@ -819,17 +819,22 @@ static inline u64 cfs_rq_max_slice(struc* * -r_max < lag < max(r_max, q) */ -static void update_entity_lag (struct cfs_rq *cfs_rq,struct sched_entity *se) +static s64 entity_lag (struct cfs_rq *cfs_rq,struct sched_entity *se,u64 avruntime) {u64 max_slice =cfs_rq_max_slice (cfs_rq) +TICK_NSEC ;s64 vlag, limit; -WARN_ON_ONCE (!se->on_rq); - - vlag =avg_vruntime (cfs_rq) - se->vruntime; + vlag = avruntime - se->vruntime; limit =calc_delta_fair (max_slice, se); - se->vlag =clamp (vlag, -limit, limit); +return clamp (vlag, -limit, limit); +} + +static void update_entity_lag (struct cfs_rq *cfs_rq,struct sched_entity *se) +{ +WARN_ON_ONCE (!se->on_rq); + + se->vlag =entity_lag (cfs_rq, se,avg_vruntime (cfs_rq)); }/*
@@ -3895,23 +3900,125 @@ dequeue_load_avg(struct cfs_rq *cfs_rq, se_weight(se) * -se->avg.load_sum); } -static void place_entity (struct cfs_rq *cfs_rq,struct sched_entity *se,int flags); +static void +rescale_entity (struct sched_entity *se,unsigned long weight,bool rel_vprot) +{ +unsigned long old_weight = se->load.weight; + +/* +* VRUNTIME +* -------- +* +* COROLLARY #1: The virtual runtime of the entity needs to be +* adjusted if re-weight at !0-lag point. +* +* Proof: For contradiction assume this is not true, so we can +* re-weight without changing vruntime at !0-lag point. +* +* Weight VRuntime Avg-VRuntime +* before w v V +* after w' v' V' +* +* Since lag needs to be preserved through re-weight: +* +* lag = (V - v)*w = (V'- v')*w', where v = v' +* ==> V' = (V - v)*w/w' + v (1) +* +* Let W be the total weight of the entities before reweight, +* since V' is the new weighted average of entities: +* +* V' = (WV + w'v - wv) / (W + w' - w) (2) +* +* by using (1) & (2) we obtain: +* +* (WV + w'v - wv) / (W + w' - w) = (V - v)*w/w' + v +* ==> (WV-Wv+Wv+w'v-wv)/(W+w'-w) = (V - v)*w/w' + v +* ==> (WV - Wv)/(W + w' - w) + v = (V - v)*w/w' + v +* ==> (V - v)*W/(W + w' - w) = (V - v)*w/w' (3) +* +* Since we are doing at !0-lag point which means V != v, we +* can simplify (3): +* +* ==> W / (W + w' - w) = w / w' +* ==> Ww' = Ww + ww' - ww +* ==> W * (w' - w) = w * (w' - w) +* ==> W = w (re-weight indicates w' != w) +* +* So the cfs_rq contains only one entity, hence vruntime of +* the entity @v should always equal to the cfs_rq's weighted +* average vruntime @V, which means we will always re-weight +* at 0-lag point, thus breach assumption. Proof completed. +* +* +* COROLLARY #2: Re-weight does NOT affect weighted average +* vruntime of all the entities. +* +* Proof: According to corollary #1, Eq. (1) should be: +* +* (V - v)*w = (V' - v')*w' +* ==> v' = V' - (V - v)*w/w' (4) +* +* According to the weighted average formula, we have: +* +* V' = (WV - wv + w'v') / (W - w + w') +* = (WV - wv + w'(V' - (V - v)w/w')) / (W - w + w') +* = (WV - wv + w'V' - Vw + wv) / (W - w + w') +* = (WV + w'V' - Vw) / (W - w + w') +* +* ==> V'*(W - w + w') = WV + w'V' - Vw +* ==> V' * (W - w) = (W - w) * V (5) +* +* If the entity is the only one in the cfs_rq, then reweight +* always occurs at 0-lag point, so V won't change. Or else +* there are other entities, hence W != w, then Eq. (5) turns +* into V' = V. So V won't change in either case, proof done. +* +* +* So according to corollary #1 & #2, the effect of re-weight +* on vruntime should be: +* +* v' = V' - (V - v) * w / w' (4) +* = V - (V - v) * w / w' +* = V - vl * w / w' +* = V - vl' +*/ + se->vlag =div64_long (se->vlag * old_weight, weight); + +/* +* DEADLINE +* -------- +* +* When the weight changes, the virtual time slope changes and +* we should adjust the relative virtual deadline accordingly. +* +* d' = v' + (d - v)*w/w' +* = V' - (V - v)*w/w' + (d - v)*w/w' +* = V - (V - v)*w/w' + (d - v)*w/w' +* = V + (d - V)*w/w' +*/ +if (se->rel_deadline) + se->deadline =div64_long (se->deadline * old_weight, weight); + +if (rel_vprot) + se->vprot =div64_long (se->vprot * old_weight, weight); +}static void reweight_entity (struct cfs_rq *cfs_rq,struct sched_entity *se,unsigned long weight) {bool curr = cfs_rq->curr == se;bool rel_vprot = false; -u64 vprot; +u64 avruntime =0 ;if (se->on_rq) {/* commit outstanding execution time */ update_curr (cfs_rq); -update_entity_lag (cfs_rq, se); - se->deadline -= se->vruntime; + avruntime =avg_vruntime (cfs_rq); + se->vlag =entity_lag (cfs_rq, se, avruntime); + se->deadline -= avruntime; se->rel_deadline =1 ;if (curr &&protect_slice (se)) { - vprot = se->vprot - se->vruntime; + se->vprot -= avruntime; rel_vprot = true; }
@@ -3922,30 +4029,23 @@ static void reweight_entity(struct cfs_r }dequeue_load_avg (cfs_rq, se); -/* -* Because we keep se->vlag = V - v_i, while: lag_i = w_i*(V - v_i), -* we need to scale se->vlag when w_i changes. -*/ - se->vlag =div64_long (se->vlag * se->load.weight, weight); -if (se->rel_deadline) - se->deadline =div64_long (se->deadline * se->load.weight, weight); - -if (rel_vprot) - vprot =div64_long (vprot * se->load.weight, weight); +rescale_entity (se, weight, rel_vprot);update_load_set (&se->load, weight);do {u32 divider =get_pelt_divider (&se->avg); - se->avg.load_avg =div_u64 (se_weight (se) * se->avg.load_sum, divider); }while (0 );enqueue_load_avg (cfs_rq, se);if (se->on_rq) { -place_entity (cfs_rq, se,0 );if (rel_vprot) - se->vprot = se->vruntime + vprot; + se->vprot += avruntime; + se->deadline += avruntime; + se->rel_deadline =0 ; + se->vruntime = avruntime - se->vlag; +update_load_add (&cfs_rq->load, se->load.weight);if (!curr)__enqueue_entity (cfs_rq, se);
@@ -5303,7 +5403,7 @@ place_entity(struct cfs_rq *cfs_rq, stru se->vruntime = vruntime - lag; -if (se->rel_deadline) { +if (sched_feat (PLACE_REL_DEADLINE ) && se->rel_deadline) { se->deadline += se->vruntime; se->rel_deadline =0 ;return ;
Re: [PATCH v2 6/7] sched/fair: Revert 6d71a9c61604 ("sched/fair: Fix EEVDF entity placement bug causing scheduling lag")
Quoted 20 lines · Peter Zijlstra
Zicheng Qu reported that, because
avg_vruntime()always includescfs_rq->curr, when ->on_rq,place_entity()doesn't work right.Specifically, the lag scaling in
place_entity()relies onavg_vruntime()being the state *before* placement of the new entity. However in this caseavg_vruntime()will actually already include the entity, which breaks things.Also, Zicheng Qu argues that
avg_vruntimeshould be invariant under reweight. IOW commit6d71a9c61604("sched/fair: Fix EEVDF entity placement bug causing scheduling lag") was wrong!The issue reported in
6d71a9c61604could possibly be explained by rounding artifacts -- notably the extreme weight '2' is outside of the range of avg_vruntime/sum_w_vruntime, since that usesscale_load_down(). By scaling vruntime by the real weight, but accounting it in vruntime with a factor 1024 more, the average moves significantly. However, that is now cured.
Quoted 7 lines
Tested by reverting
66951e4860d3("sched/fair: Fixupdate_cfs_group()vsDELAY_DEQUEUE") and tracing vruntime and vlag figures again.Reported-by Zicheng Qu <[email protected]>Signed-off-by Peter Zijlstra (Intel) <[email protected]>Tested-by K Prateek Nayak <[email protected]>Tested-by Shubhang Kaushik <[email protected]>
Quoted 213 lines
--- kernel/sched/fair.c | 148 +++++++++++++++++++++++++++++++++++++++++++--------- 1 file changed, 124 insertions(+), 24 deletions(-)kernel/sched/fair.c +124
-24@@ -819,17 +819,22 @@ static inline u64 cfs_rq_max_slice(struc* * -r_max < lag < max(r_max, q) */ -static void update_entity_lag (struct cfs_rq *cfs_rq,struct sched_entity *se) +static s64 entity_lag (struct cfs_rq *cfs_rq,struct sched_entity *se,u64 avruntime) {u64 max_slice =cfs_rq_max_slice (cfs_rq) +TICK_NSEC ;s64 vlag, limit; -WARN_ON_ONCE (!se->on_rq); - - vlag =avg_vruntime (cfs_rq) - se->vruntime; + vlag = avruntime - se->vruntime; limit =calc_delta_fair (max_slice, se); - se->vlag =clamp (vlag, -limit, limit); +return clamp (vlag, -limit, limit); +} + +static void update_entity_lag (struct cfs_rq *cfs_rq,struct sched_entity *se) +{ +WARN_ON_ONCE (!se->on_rq); + + se->vlag =entity_lag (cfs_rq, se,avg_vruntime (cfs_rq)); }/* @@ -3895,23 +3900,125 @@ dequeue_load_avg(struct cfs_rq *cfs_rq, se_weight(se) * -se->avg.load_sum); } -static void place_entity (struct cfs_rq *cfs_rq,struct sched_entity *se,int flags); +static void +rescale_entity (struct sched_entity *se,unsigned long weight,bool rel_vprot) +{ +unsigned long old_weight = se->load.weight; + +/* +* VRUNTIME +* -------- +* +* COROLLARY #1: The virtual runtime of the entity needs to be +* adjusted if re-weight at !0-lag point. +* +* Proof: For contradiction assume this is not true, so we can +* re-weight without changing vruntime at !0-lag point. +* +* Weight VRuntime Avg-VRuntime +* before w v V +* after w' v' V' +* +* Since lag needs to be preserved through re-weight: +* +* lag = (V - v)*w = (V'- v')*w', where v = v' +* ==> V' = (V - v)*w/w' + v (1) +* +* Let W be the total weight of the entities before reweight, +* since V' is the new weighted average of entities: +* +* V' = (WV + w'v - wv) / (W + w' - w) (2) +* +* by using (1) & (2) we obtain: +* +* (WV + w'v - wv) / (W + w' - w) = (V - v)*w/w' + v +* ==> (WV-Wv+Wv+w'v-wv)/(W+w'-w) = (V - v)*w/w' + v +* ==> (WV - Wv)/(W + w' - w) + v = (V - v)*w/w' + v +* ==> (V - v)*W/(W + w' - w) = (V - v)*w/w' (3) +* +* Since we are doing at !0-lag point which means V != v, we +* can simplify (3): +* +* ==> W / (W + w' - w) = w / w' +* ==> Ww' = Ww + ww' - ww +* ==> W * (w' - w) = w * (w' - w) +* ==> W = w (re-weight indicates w' != w) +* +* So the cfs_rq contains only one entity, hence vruntime of +* the entity @v should always equal to the cfs_rq's weighted +* average vruntime @V, which means we will always re-weight +* at 0-lag point, thus breach assumption. Proof completed. +* +* +* COROLLARY #2: Re-weight does NOT affect weighted average +* vruntime of all the entities. +* +* Proof: According to corollary #1, Eq. (1) should be: +* +* (V - v)*w = (V' - v')*w' +* ==> v' = V' - (V - v)*w/w' (4) +* +* According to the weighted average formula, we have: +* +* V' = (WV - wv + w'v') / (W - w + w') +* = (WV - wv + w'(V' - (V - v)w/w')) / (W - w + w') +* = (WV - wv + w'V' - Vw + wv) / (W - w + w') +* = (WV + w'V' - Vw) / (W - w + w') +* +* ==> V'*(W - w + w') = WV + w'V' - Vw +* ==> V' * (W - w) = (W - w) * V (5) +* +* If the entity is the only one in the cfs_rq, then reweight +* always occurs at 0-lag point, so V won't change. Or else +* there are other entities, hence W != w, then Eq. (5) turns +* into V' = V. So V won't change in either case, proof done. +* +* +* So according to corollary #1 & #2, the effect of re-weight +* on vruntime should be: +* +* v' = V' - (V - v) * w / w' (4) +* = V - (V - v) * w / w' +* = V - vl * w / w' +* = V - vl' +*/ + se->vlag =div64_long (se->vlag * old_weight, weight); + +/* +* DEADLINE +* -------- +* +* When the weight changes, the virtual time slope changes and +* we should adjust the relative virtual deadline accordingly. +* +* d' = v' + (d - v)*w/w' +* = V' - (V - v)*w/w' + (d - v)*w/w' +* = V - (V - v)*w/w' + (d - v)*w/w' +* = V + (d - V)*w/w' +*/ +if (se->rel_deadline) + se->deadline =div64_long (se->deadline * old_weight, weight); + +if (rel_vprot) + se->vprot =div64_long (se->vprot * old_weight, weight); +}static void reweight_entity (struct cfs_rq *cfs_rq,struct sched_entity *se,unsigned long weight) {bool curr = cfs_rq->curr == se;bool rel_vprot = false; -u64 vprot; +u64 avruntime =0 ;if (se->on_rq) {/* commit outstanding execution time */ update_curr (cfs_rq); -update_entity_lag (cfs_rq, se); - se->deadline -= se->vruntime; + avruntime =avg_vruntime (cfs_rq); + se->vlag =entity_lag (cfs_rq, se, avruntime); + se->deadline -= avruntime; se->rel_deadline =1 ;if (curr &&protect_slice (se)) { - vprot = se->vprot - se->vruntime; + se->vprot -= avruntime; rel_vprot = true; }@@ -3922,30 +4029,23 @@ static void reweight_entity(struct cfs_r }dequeue_load_avg (cfs_rq, se); -/* -* Because we keep se->vlag = V - v_i, while: lag_i = w_i*(V - v_i), -* we need to scale se->vlag when w_i changes. -*/ - se->vlag =div64_long (se->vlag * se->load.weight, weight); -if (se->rel_deadline) - se->deadline =div64_long (se->deadline * se->load.weight, weight); - -if (rel_vprot) - vprot =div64_long (vprot * se->load.weight, weight); +rescale_entity (se, weight, rel_vprot);update_load_set (&se->load, weight);do {u32 divider =get_pelt_divider (&se->avg); - se->avg.load_avg =div_u64 (se_weight (se) * se->avg.load_sum, divider); }while (0 );enqueue_load_avg (cfs_rq, se);if (se->on_rq) { -place_entity (cfs_rq, se,0 );if (rel_vprot) - se->vprot = se->vruntime + vprot; + se->vprot += avruntime; + se->deadline += avruntime; + se->rel_deadline =0 ; + se->vruntime = avruntime - se->vlag; +update_load_add (&cfs_rq->load, se->load.weight);if (!curr)__enqueue_entity (cfs_rq, se);@@ -5303,7 +5403,7 @@ place_entity(struct cfs_rq *cfs_rq, stru se->vruntime = vruntime - lag; -if (se->rel_deadline) { +if (sched_feat (PLACE_REL_DEADLINE ) && se->rel_deadline) { se->deadline += se->vruntime; se->rel_deadline =0 ;return ;
Re: [PATCH v2 6/7] sched/fair: Revert 6d71a9c61604 ("sched/fair: Fix EEVDF entity placement bug causing scheduling lag")
Hi,
Quoted 7 lines
Zicheng Qu reported that, because
avg_vruntime()always includescfs_rq->curr, when ->on_rq,place_entity()doesn't work right.Specifically, the lag scaling in
place_entity()relies onavg_vruntime()being the state *before* placement of the new entity. However in this caseavg_vruntime()will actually already include the entity, which breaks things.
This has proven to be harmful on our production cluster using kernel version 6.18.19
We witness a parent cgroup entity (/kubepods.slice in our case) changing very frequently load_avg figures, which leads to calling entity_pick->update_cfs_group->reweight_entity very often (pretty much at all entity_tick call).
If a cpu hogging task is member of this cgroup and bound to a CPU,
we observe starvation of processes bound to that same CPU but not being members of this cgroup (kworkers for ceph rbd in our production case).
Looking at /sys/kernel/debug/sched/debug, we can indeed see that cfs_rq[0]:/ .avg_vruntime and .zero_vruntime continuously move back in time while .left_deadline and .left_vruntime are stuck.
This is likely due to the wrong lag calculation of the cgroup entity within the root cgroup.
We can reproduce that in a sandboxed manner doing the following:
* create a cgroup 'CG'
* run a cpu intensive task 'offender', bound to a CPU
* move the task to cgroup 'CG'
* run a cpu intensive task 'victim' bound to the same CPU
* To reproduce the frequent call to reweight_entity, we change rapidly CG/cpu.weight from 99, 100, 101 and loop
* 'victim' will stop running
I use the following script to reproduce:
---
#!/bin/bash
TARGET_CPU=0
CG_PATH="/sys/fs/cgroup/test_reweight"
cat << 'EOF' > heartbeat.c
#include <stdio.h>
#include <time.h>
#include <stdint.h>
int main() {
struct timespec last, now;
uint64_t count = 0;
clock_gettime(CLOCK_MONOTONIC, &last);
while (1) {
count++;
clock_gettime(CLOCK_MONOTONIC, &now);
long delta_ms = (now.tv_sec - last.tv_sec) * 1000 + (now.tv_nsec - last.tv_nsec) / 1000000;
if (delta_ms >= 500) {
printf("Tick: %lu iterations (delta %ld ms)\n", count, delta_ms);
fflush(stdout);
count = 0;
last = now;
}
}
return 0;
}EOF
gcc -O2 heartbeat.c -o heartbeat
mkdir -p "$CG_PATH"
echo "+cpu" > /sys/fs/cgroup/cgroup.subtree_control
taskset -c $TARGET_CPU yes > /dev/null &
PID_YES=$!
echo $PID_YES > "$CG_PATH/cgroup.procs"
taskset -c $TARGET_CPU ./heartbeat &
PID_HEARTBEAT=$!
echo "5 seconds observation..."
sleep 5
echo "Jittering on $CG_PATH/cpu.weight..."
trap "kill $PID_YES $PID_HEARTBEAT; rmdir $CG_PATH; rm heartbeat.c; rm heartbeat; exit" SIGINT SIGTERM while true; do
echo 99 > "$CG_PATH/cpu.weight"
echo 100 > "$CG_PATH/cpu.weight"
echo 101 > "$CG_PATH/cpu.weight"done
---
I tested the following versions:
* LTS 5.10.252, 5.15.202, 6.1.166, 6.6.129, 6.12.77 --> no issue
* LTS 6.18.19 has the issue
* Stable 6.19.9 has the issue
* Mainline 7.0-rc5 has the issue
* Tip 7.0.0-rc5+ no issue
Finally, I applied the patch to 6.18.19 LTS which solves the issue. However, we do not benefit from previous patches such as [PATCH v2 5/7] sched/fair: Increase weight bits for avg_vruntime.
Thus I would prefer to let you decide how you want to adress backport on 6.18
If you want I can share my patch file, let me know.
Best regards
Peter Zijlstra
maintainerRe: [PATCH v2 6/7] sched/fair: Revert 6d71a9c61604 ("sched/fair: Fix EEVDF entity placement bug causing scheduling lag")
Quoted 19 lines · William Montaz
Hi,
Quoted 7 lines
Zicheng Qu reported that, because
avg_vruntime()always includescfs_rq->curr, when ->on_rq,place_entity()doesn't work right.Specifically, the lag scaling in
place_entity()relies onavg_vruntime()being the state *before* placement of the new entity. However in this caseavg_vruntime()will actually already include the entity, which breaks things.This has proven to be harmful on our production cluster using kernel version 6.18.19
I tested the following versions:
* LTS 5.10.252, 5.15.202, 6.1.166, 6.6.129, 6.12.77 --> no issue
* LTS 6.18.19 has the issue
* Stable 6.19.9 has the issue
* Mainline 7.0-rc5 has the issue
* Tip 7.0.0-rc5+ no issue
Quoted 6 lines
Finally, I applied the patch to 6.18.19 LTS which solves the issue. However, we do not benefit from previous patches such as [PATCH v2 5/7] sched/fair: Increase weight bits for
avg_vruntime.Thus I would prefer to let you decide how you want to adress backport on 6.18
If you want I can share my patch file, let me know.
I've (finally!) had a look at stable-6.18.y and yes, I think this can be backported without too much issue.
Feel free to submit a backport to stable for this.
PATCH 1/1 sched/fair: Revert 6d71a9c61604 ("sched/fair: Fix EEVDF entity placement bug causing scheduling lag")
In reply to William MontazFrom: Peter Zijlstra <[email protected]>
[ Upstream commit 101f3498b4bdfef97152a444847948de1543f692 ]
Zicheng Qu reported that, because avg_vruntime() always includes cfs_rq->curr, when ->on_rq, place_entity() doesn't work right.
Specifically, the lag scaling in place_entity() relies on avg_vruntime() being the state *before* placement of the new entity. However in this case avg_vruntime() will actually already include the entity, which breaks things.
Also, Zicheng Qu argues that avg_vruntime should be invariant under reweight. IOW commit 6d71a9c61604 ("sched/fair: Fix EEVDF entity placement bug causing scheduling lag") was wrong!
The issue reported in 6d71a9c61604 could possibly be explained by rounding artifacts -- notably the extreme weight '2' is outside of the range of avg_vruntime/sum_w_vruntime, since that uses scale_load_down(). By scaling vruntime by the real weight, but accounting it in vruntime with a factor 1024 more, the average moves significantly. However, that is now cured.
Tested by reverting 66951e4860d3 ("sched/fair: Fix update_cfs_group() vs DELAY_DEQUEUE") and tracing vruntime and vlag figures again.
---
Cc: Dietmar Eggemann <[email protected]>
Cc: "Xuewen Yan" <[email protected]>
Cc: William Montaz <[email protected]>
--- kernel/sched/fair.c | 148 +++++++++++++++++++++++++++++++++++++------- 1 file changed, 124 insertions(+), 24 deletions(-)
kernel/sched/fair.c +124 -24
@@ -764,17 +764,22 @@ static inline u64 cfs_rq_max_slice(struct cfs_rq *cfs_rq);* * -r_max < lag < max(r_max, q) */ -static void update_entity_lag (struct cfs_rq *cfs_rq,struct sched_entity *se) +static s64 entity_lag (struct cfs_rq *cfs_rq,struct sched_entity *se,u64 avruntime) {u64 max_slice =cfs_rq_max_slice (cfs_rq) +TICK_NSEC ;s64 vlag, limit; -WARN_ON_ONCE (!se->on_rq); - - vlag =avg_vruntime (cfs_rq) - se->vruntime; + vlag = avruntime - se->vruntime; limit =calc_delta_fair (max_slice, se); - se->vlag =clamp (vlag, -limit, limit); +return clamp (vlag, -limit, limit); +} + +static void update_entity_lag (struct cfs_rq *cfs_rq,struct sched_entity *se) +{ +WARN_ON_ONCE (!se->on_rq); + + se->vlag =entity_lag (cfs_rq, se,avg_vruntime (cfs_rq)); }/*
@@ -3831,23 +3836,125 @@ dequeue_load_avg(struct cfs_rq *cfs_rq, struct sched_entity *se) cfs_rq->avg.load_avg * PELT_MIN_DIVIDER); } -static void place_entity (struct cfs_rq *cfs_rq,struct sched_entity *se,int flags); +static void +rescale_entity (struct sched_entity *se,unsigned long weight,bool rel_vprot) +{ +unsigned long old_weight = se->load.weight; + +/* +* VRUNTIME +* -------- +* +* COROLLARY #1: The virtual runtime of the entity needs to be +* adjusted if re-weight at !0-lag point. +* +* Proof: For contradiction assume this is not true, so we can +* re-weight without changing vruntime at !0-lag point. +* +* Weight VRuntime Avg-VRuntime +* before w v V +* after w' v' V' +* +* Since lag needs to be preserved through re-weight: +* +* lag = (V - v)*w = (V'- v')*w', where v = v' +* ==> V' = (V - v)*w/w' + v (1) +* +* Let W be the total weight of the entities before reweight, +* since V' is the new weighted average of entities: +* +* V' = (WV + w'v - wv) / (W + w' - w) (2) +* +* by using (1) & (2) we obtain: +* +* (WV + w'v - wv) / (W + w' - w) = (V - v)*w/w' + v +* ==> (WV-Wv+Wv+w'v-wv)/(W+w'-w) = (V - v)*w/w' + v +* ==> (WV - Wv)/(W + w' - w) + v = (V - v)*w/w' + v +* ==> (V - v)*W/(W + w' - w) = (V - v)*w/w' (3) +* +* Since we are doing at !0-lag point which means V != v, we +* can simplify (3): +* +* ==> W / (W + w' - w) = w / w' +* ==> Ww' = Ww + ww' - ww +* ==> W * (w' - w) = w * (w' - w) +* ==> W = w (re-weight indicates w' != w) +* +* So the cfs_rq contains only one entity, hence vruntime of +* the entity @v should always equal to the cfs_rq's weighted +* average vruntime @V, which means we will always re-weight +* at 0-lag point, thus breach assumption. Proof completed. +* +* +* COROLLARY #2: Re-weight does NOT affect weighted average +* vruntime of all the entities. +* +* Proof: According to corollary #1, Eq. (1) should be: +* +* (V - v)*w = (V' - v')*w' +* ==> v' = V' - (V - v)*w/w' (4) +* +* According to the weighted average formula, we have: +* +* V' = (WV - wv + w'v') / (W - w + w') +* = (WV - wv + w'(V' - (V - v)w/w')) / (W - w + w') +* = (WV - wv + w'V' - Vw + wv) / (W - w + w') +* = (WV + w'V' - Vw) / (W - w + w') +* +* ==> V'*(W - w + w') = WV + w'V' - Vw +* ==> V' * (W - w) = (W - w) * V (5) +* +* If the entity is the only one in the cfs_rq, then reweight +* always occurs at 0-lag point, so V won't change. Or else +* there are other entities, hence W != w, then Eq. (5) turns +* into V' = V. So V won't change in either case, proof done. +* +* +* So according to corollary #1 & #2, the effect of re-weight +* on vruntime should be: +* +* v' = V' - (V - v) * w / w' (4) +* = V - (V - v) * w / w' +* = V - vl * w / w' +* = V - vl' +*/ + se->vlag =div64_long (se->vlag * old_weight, weight); + +/* +* DEADLINE +* -------- +* +* When the weight changes, the virtual time slope changes and +* we should adjust the relative virtual deadline accordingly. +* +* d' = v' + (d - v)*w/w' +* = V' - (V - v)*w/w' + (d - v)*w/w' +* = V - (V - v)*w/w' + (d - v)*w/w' +* = V + (d - V)*w/w' +*/ +if (se->rel_deadline) + se->deadline =div64_long (se->deadline * old_weight, weight); + +if (rel_vprot) + se->vprot =div64_long (se->vprot * old_weight, weight); +}static void reweight_entity (struct cfs_rq *cfs_rq,struct sched_entity *se,unsigned long weight) {bool curr = cfs_rq->curr == se;bool rel_vprot = false; -u64 vprot; +u64 avruntime =0 ;if (se->on_rq) {/* commit outstanding execution time */ update_curr (cfs_rq); -update_entity_lag (cfs_rq, se); - se->deadline -= se->vruntime; + avruntime =avg_vruntime (cfs_rq); + se->vlag =entity_lag (cfs_rq, se, avruntime); + se->deadline -= avruntime; se->rel_deadline =1 ;if (curr &&protect_slice (se)) { - vprot = se->vprot - se->vruntime; + se->vprot -= avruntime; rel_vprot = true; }
@@ -3858,30 +3965,23 @@ static void reweight_entity(struct cfs_rq *cfs_rq, struct sched_entity *se, }dequeue_load_avg (cfs_rq, se); -/* -* Because we keep se->vlag = V - v_i, while: lag_i = w_i*(V - v_i), -* we need to scale se->vlag when w_i changes. -*/ - se->vlag =div_s64 (se->vlag * se->load.weight, weight); -if (se->rel_deadline) - se->deadline =div_s64 (se->deadline * se->load.weight, weight); - -if (rel_vprot) - vprot =div_s64 (vprot * se->load.weight, weight); +rescale_entity (se, weight, rel_vprot);update_load_set (&se->load, weight);do {u32 divider =get_pelt_divider (&se->avg); - se->avg.load_avg =div_u64 (se_weight (se) * se->avg.load_sum, divider); }while (0 );enqueue_load_avg (cfs_rq, se);if (se->on_rq) { -place_entity (cfs_rq, se,0 );if (rel_vprot) - se->vprot = se->vruntime + vprot; + se->vprot += avruntime; + se->deadline += avruntime; + se->rel_deadline =0 ; + se->vruntime = avruntime - se->vlag; +update_load_add (&cfs_rq->load, se->load.weight);if (!curr)__enqueue_entity (cfs_rq, se);
@@ -5281,7 +5381,7 @@ place_entity(struct cfs_rq *cfs_rq, struct sched_entity *se, int flags) se->vruntime = vruntime - lag; -if (se->rel_deadline) { +if (sched_feat (PLACE_REL_DEADLINE ) && se->rel_deadline) { se->deadline += se->vruntime; se->rel_deadline =0 ;return ;
Signature · 1 line
2.54.0.rc1.513.gad8abe7a5a-goog
Re: [PATCH 6.18] sched/fair: Revert 6d71a9c61604 ("sched/fair: Fix EEVDF entity placement bug causing scheduling lag")
Quoted 4 lines · John Stultz
From: Peter Zijlstra <[email protected]>
[ Upstream commit
101f3498b4bdfef97152a444847948de1543f692]
[...]
Quoted 3 lines
(cherry picked from commit 101f3498b4bdfef97152a444847948de1543f692)[jstultz: Resolved minor collision in the revert against 6.18-stable]Signed-off-by John Stultz <[email protected]>
We have been hitting this on 6.18.y in production. The setup is a thread spinning on one CPU inside a cgroup that holds nearly all the weight on that CPU. That cgroup's weight gets recalculated on almost every tick, and the per-cpu kworker on the same CPU ends up runnable but never picked for minutes to hours. We see it as workqueue lockup reports and hung tasks stuck behind lru_add_drain_all().
I tested this patch on 6.18.44 in a 4 vCPU KVM guest with a reproducer along the lines of William's script. Three spinners are pinned to three CPUs inside a nested cgroup with a high cpu.weight, and some extra load in the group keeps its weight changing. On plain 6.18.44 the kworkers on those CPUs get stuck runnable but never picked, and their vruntime stops moving. With this patch they run normally. Running the same load with no cgroup does not starve anything on either kernel.
Peter said in April that this could go to 6.18 [1]. Janne Huttunen posted the same backport last month [2] and Sasha is holding it for Peter's ack on taking the revert without 4823725d9d1d [3]. This patch and [2] differ only in div64_long() against div_s64().
[1] https://lore.kernel.org/all/[email protected]/
[2] https://lore.kernel.org/stable/PAWPR07MB100712177EB29A65F4385E4C29ACF2@PAWPR07MB10071.eurprd07.prod.outlook.com/
[3] https://lore.kernel.org/stable/[email protected]/
Peter Zijlstra
maintainerRe: [PATCH 6.18] sched/fair: Revert 6d71a9c61604 ("sched/fair: Fix EEVDF entity placement bug causing scheduling lag")
Quoted 30 lines · Jose Fernandez
Quoted 4 lines · John Stultz
From: Peter Zijlstra <[email protected]>
[ Upstream commit
101f3498b4bdfef97152a444847948de1543f692][...]
Quoted 3 lines
(cherry picked from commit 101f3498b4bdfef97152a444847948de1543f692)[jstultz: Resolved minor collision in the revert against 6.18-stable]Signed-off-by John Stultz <[email protected]>We have been hitting this on 6.18.y in production. The setup is a thread spinning on one CPU inside a cgroup that holds nearly all the weight on that CPU. That cgroup's weight gets recalculated on almost every tick, and the per-cpu kworker on the same CPU ends up runnable but never picked for minutes to hours. We see it as workqueue lockup reports and hung tasks stuck behind
lru_add_drain_all().I tested this patch on 6.18.44 in a 4 vCPU KVM guest with a reproducer along the lines of William's script. Three spinners are pinned to three CPUs inside a nested cgroup with a high cpu.weight, and some extra load in the group keeps its weight changing. On plain 6.18.44 the kworkers on those CPUs get stuck runnable but never picked, and their vruntime stops moving. With this patch they run normally. Running the same load with no cgroup does not starve anything on either kernel.
Peter said in April that this could go to 6.18 [1]. Janne Huttunen posted the same backport last month [2] and Sasha is holding it for Peter's ack on taking the revert without
4823725d9d1d[3]. This patch and [2] differ only indiv64_long()againstdiv_s64().
Quoted 5 lines
[1] https://lore.kernel.org/all/[email protected]/
[2] https://lore.kernel.org/stable/PAWPR07MB100712177EB29A65F4385E4C29ACF2@PAWPR07MB10071.eurprd07.prod.outlook.com/
[3] https://lore.kernel.org/stable/[email protected]/
Yeah, this should be fine without 4823725d9d1d.
Re: [PATCH 6.18] sched/fair: Revert 6d71a9c61604 ("sched/fair: Fix EEVDF entity placement bug causing scheduling lag")
Quoted 1 line · Peter Zijlstra
Yeah, this should be fine without
4823725d9d1d.
One heads up, our review tooling caught this after I sent the Tested-by. The revert was written after commit 80390ead2080 ("sched/fair: Separate se->vlag from se->vprot") took vlag and vprot out of their union, and 6.18 still has the union. Without that split first, the rel_vprot path in the new reweight_entity() scales vlag twice and curr's vruntime comes out wrong.
Re: [PATCH 6.18] sched/fair: Revert 6d71a9c61604 ("sched/fair: Fix EEVDF entity placement bug causing scheduling lag")
Quoted 10 lines · Jose Fernandez (Anthropic)
Quoted 1 line · Peter Zijlstra
Yeah, this should be fine without
4823725d9d1d.One heads up, our review tooling caught this after I sent the Tested-by. The revert was written after commit
80390ead2080("sched/fair: Separatese->vlagfromse->vprot") took vlag and vprot out of their union, and 6.18 still has the union. Without that split first, therel_vprotpath in the newreweight_entity()scales vlag twice and curr's vruntime comes out wrong.
Indeed! I was looking earlier today as I had some foggy memory of an issue the backport caused in our android17-6.18 tree, but couldn't find it right off!
Since we were KABI frozen in the android tree, we used the following patch to work around it: https://r.android.com/4103883
But then reverted that and cherry-picked 80390ead2080 ("UPSTREAM:
sched/fair: Separate se->vlag from se->vprot") for the KABI thaw.
Thanks for noticing and reminding me of this!
thanks
-john
Sasha Levin
maintainerRe: [PATCH 6.18] sched/fair: Revert 6d71a9c61604 ("sched/fair: Fix EEVDF entity placement bug causing scheduling lag")
In reply to Peter ZijlstraQuoted 5 lines
Quoted 3 lines
Peter said in April that this could go to 6.18 [1]. Janne Huttunen posted the same backport last month [2] and Sasha is holding it for Peter's ack on taking the revert without
4823725d9d1d[3].Yeah, this should be fine without
4823725d9d1d.
Thanks, that was what I was waiting on. Queued John's version for 6.18.
Signature · 2 lines
Thanks, Sasha
Re: [PATCH 6.18] sched/fair: Revert 6d71a9c61604 ("sched/fair: Fix EEVDF entity placement bug causing scheduling lag")
Quoted 8 lines · Sasha Levin
Quoted 6 lines
Quoted 4 lines
Peter said in April that this could go to 6.18 [1]. Janne Huttunen posted the same backport last month [2] and Sasha is holding it for Peter's ack on taking the revert without
4823725d9d1d[3].Yeah, this should be fine without
4823725d9d1d.Thanks, that was what I was waiting on. Queued John's version for 6.18.
Do note, as Jose pointed out you should probably take: 80390ead2080 ("UPSTREAM: sched/fair: Separate se->vlag from se->vprot") as well then (ideally prior to).
thanks
-john
Re: [PATCH 6.18] sched/fair: Revert 6d71a9c61604 ("sched/fair: Fix EEVDF entity placement bug causing scheduling lag")
Quoted 3 lines
Do note, as Jose pointed out you should probably take:
80390ead2080("UPSTREAM: sched/fair: Separatese->vlagfromse->vprot") as well then (ideally prior to).
Queued for 6.18, thanks - and thanks to Jose for catching it.
Signature · 2 lines
Thanks, Sasha
Peter Zijlstra
maintainerPATCH v2 7/7 sched/fair: Use full weight to __calc_delta()
In reply to Peter ZijlstraSince we now use the full weight for avg_vruntime(), also make __calc_delta() use the full value.
Since weight is effectively NICE_0_LOAD, this is 20 bits on 64bit. This leaves 44 bits for delta_exec, which is ~16k seconds, way longer than any one tick would ever be, so no worry about overflow.
--- kernel/sched/fair.c | 7 +++++++ 1 file changed, 7 insertions(+)
kernel/sched/fair.c +7 -0
@@ -225,6 +225,7 @@ void __init sched_init_granularity(void)update_sysctl (); } +#ifndef CONFIG_64BIT #define WMULT_CONST (~0U)#define WMULT_SHIFT 32
@@ -283,6 +284,12 @@ static u64 __calc_delta(u64 delta_exec, return mul_u64_u32_shr(delta_exec, fact, shift); } +#else +static u64 __calc_delta (u64 delta_exec,unsigned long weight,struct load_weight *lw) +{ +return (delta_exec * weight) / lw->weight; +} +#endif /* * delta /= w
Re: [PATCH v2 7/7] sched/fair: Use full weight to __calc_delta()
Quoted 11 lines · Peter Zijlstra
Since we now use the full weight for
avg_vruntime(), also make__calc_delta()use the full value.Since weight is effectively
NICE_0_LOAD, this is 20 bits on 64bit. This leaves 44 bits fordelta_exec, which is ~16k seconds, way longer than any one tick would ever be, so no worry about overflow.Signed-off-by Peter Zijlstra (Intel) <[email protected]>Tested-by K Prateek Nayak <[email protected]>Tested-by Shubhang Kaushik <[email protected]>
Quoted 29 lines
--- kernel/sched/fair.c | 7 +++++++ 1 file changed, 7 insertions(+)kernel/sched/fair.c +7
-0@@ -225,6 +225,7 @@ void __init sched_init_granularity(void)update_sysctl (); } +#ifndef CONFIG_64BIT #define WMULT_CONST (~0U)#define WMULT_SHIFT 32@@ -283,6 +284,12 @@ static u64 __calc_delta(u64 delta_exec, return mul_u64_u32_shr(delta_exec, fact, shift); } +#else +static u64 __calc_delta (u64 delta_exec,unsigned long weight,struct load_weight *lw) +{ +return (delta_exec * weight) / lw->weight; +} +#endif /* * delta /= w