sched/fair: clamp rescaled vlag in reweight_entity() to bound entity_key()
PATCH 1/1 sched/fair: clamp rescaled vlag in reweight_entity() to bound entity_key()
A 252-CPU machine running an EEVDF kernel hard-locked up. The trigger was the s64 overflow guard in __sum_w_vruntime_add():
WARNING: CPU: 181 ... at kernel/sched/fair.c __enqueue_entity+0x1fc ... __enqueue_entity / put_prev_entity / put_prev_task_fair / __schedule
firing during a reschedule, resulting in the CPU trying to wake up the printk worker, while already holding the runqueue lock, resulting in a deadlock.
Root cause for this scheduler bug is in the reweight path, not the enqueue that tripped the WARN.
reweight_entity() preserves an entity's lag across a weight change by scaling vlag in rescale_entity():
se->vlag = vl' = vl * old_weight / new_weight;
and then, for an on_rq entity, recomputes:
se->vruntime = avruntime - se->vlag;
On a large weight decrease (w' << w) this inflates vlag without bound; nothing re-clamps it to the per-entity lag limit that entity_lag() and update_entity_lag() enforce everywhere else. The deadline is rescaled and re-based separately, so only vruntime drifts.
For a group entity reweighted via update_cfs_group() this lets se->vruntime drift arbitrarily far below cfs_rq->zero_vruntime. A later __enqueue_entity() then computes
key = entity_key(cfs_rq, se) = se->vruntime - cfs_rq->zero_vruntime weight = avg_vruntime_weight(cfs_rq, se->load.weight) w_vruntime = key * weight
and trips the s64 overflow guard in __sum_w_vruntime_add():
WARN_ON_ONCE((w_vruntime >> 63) != (w_vruntime >> 62));
leaving the avg-vruntime accounting and the rb-tree ordering corrupt, which in turn wedges the load balancer (every CPU spinning in sched_balance_rq()) into a hard lockup.
Observed on a 252-CPU machine on a depth-7 group sched_entity:
cfs_rq->zero_vruntime = -503694424797 se->vruntime = -15964975487901 key = -15461281063104 (~2^43.8) se->load.weight = 438118, sum_shift = 0 key * weight = -6773865536804998272 = -(2^62.55) -> WARN
Re-clamp vlag to the same bound entity_lag() uses, after the new weight is installed:
limit = calc_delta_fair(cfs_rq_max_slice(cfs_rq) + TICK_NSEC, se); se->vlag = clamp(se->vlag, -limit, limit);
Since calc_delta_fair(t, se) * se->load.weight <= t << NICE_0_LOAD_SHIFT (equality but for the floor in __calc_delta), this bounds key * weight by (max_slice + TICK_NSEC) << NICE_0_LOAD_SHIFT independent of the entity's weight. For the case above (max_slice = 3 ms, NICE_0_LOAD = 1 << 20):
limit = (4000000 << 20) / 438118 = 9573457 (~2^23.2) |key| clamped from 2^43.8 -> 2^23.2 (20.6 bits, ~1.6e6x) key * weight <= 9573457 * 438118 = 4194303833926 = 2^41.9
i.e. ~20 bits of headroom below the 2^62 guard, so the overflow and the resulting lockup cannot occur. For legitimate reweights the rescaled vlag is already within the bound, so the clamp is a no-op.
---
PS: do we want some LOGLEVEL_SCHED equivalent WARN_ON for inside
the scheduler, so we can warn without a deadlock?
kernel/sched/fair.c | 18 ++++++++++++++++++ 1 file changed, 18 insertions(+)
kernel/sched/fair.c +18 -0
@@ -4669,6 +4669,7 @@ static void reweight_entity(struct cfs_rq *cfs_rq, struct sched_entity *se,bool curr = cfs_rq->curr == se;bool rel_vprot = false;u64 avruntime =0 ; +s64 limit;if (se->on_rq) {/* commit outstanding execution time */
@@ -4693,6 +4694,23 @@ static void reweight_entity(struct cfs_rq *cfs_rq, struct sched_entity *se,update_load_set (&se->load, weight); +/* +* rescale_entity() scaled vlag by old_weight/new_weight to preserve +* lag across the reweight (vl' = vl * w/w'). On a large weight +* decrease this can inflate vlag well past the legal lag bound. Left +* unclamped, the resulting se->vruntime = avruntime - vlag (computed +* just below for an on_rq entity, or via place_entity() on the next +* enqueue for an off_rq one) drifts far from cfs_rq->zero_vruntime, and +* a subsequent __enqueue_entity() then overflows entity_key() * weight +* in __sum_w_vruntime_add(). Re-clamp to the per-entity lag limit for +* the new weight, exactly as entity_lag() does on every fresh lag. +* Note calc_delta_fair(t, se) * se->load.weight <= t << NICE_0_LOAD_SHIFT +* (equality but for the floor in __calc_delta), so this bounds +* key * weight regardless of the entity's weight. +*/ + limit =calc_delta_fair (cfs_rq_max_slice (cfs_rq) +TICK_NSEC , se); + se->vlag =clamp (se->vlag, -limit, limit); + do { u32 divider = get_pelt_divider(&se->avg); se->avg.load_avg = div_u64(se_weight(se) * se->avg.load_sum, divider);
Signature · 1 line
2.53.0-Meta
Peter Zijlstra
maintainerQuoted 5 lines · Rik van Riel
reweight_entity()preserves an entity's lag across a weight change by scaling vlag inrescale_entity():se->vlag = vl' = vl * old_weight / new_weight;
Quoted 8 lines
and then, for an
on_rqentity, recomputes:se->vruntime = avruntime - se->vlag;On a large weight decrease (w' << w) this inflates vlag without bound; nothing re-clamps it to the per-entity lag limit that
entity_lag()andupdate_entity_lag()enforce everywhere else. The deadline is rescaled and re-based separately, so only vruntime drifts.
So the vlag limit is:
limit = calc_delta_fair(max_slice, se)
Right? But that is in fact:
max_slice * NICE_0_LOAD
limit = -----------------------
se->weight
Now, rescale does:
vlag * old_weight
vlag = -----------------
new_weight
So then transform the limit using that same:
max_slice * NICE_0_LOAD old_weight max_slice * NICE_0_LOAD
limit = ----------------------- * ---------- = -----------------------
old_weight new_weight new_weight
IOW, the transform totally preserves the limit. If the vlag was bound before, it must be bound after.
What am I missing?
Quoted 5 lines · Peter Zijlstra
IOW, the transform totally preserves the limit. If the vlag was bound before, it must be bound after.
What am I missing?
You're not missing anything.
After looking at the code, and tracing through things for much of the afternoon, it turns out the culprit is the cgroup throttle path.
Specifically, this bug happened on a 6.16 based kernel, which has the new EEVDF zero_vruntime code, in order to prevent the EEVDF starvation that could happen with the old min_vruntime code, but also still has the old cgroup throttling code.
This leaves a code path where lazy dequeue code combined with the cgroup throttling code can result in entity_lag and entity_key reaching ludicrous values, resulting in the overflow.
This bug reproduces in about 5 minutes on that 6.16 based kernel, but not with current upstream.
Nothing to do upstream, and it looks like there are a few changesets upstream that may be able to fix the issue in the 6.16 based kernel without even needing the clamp from this patch.
Signature · 1 line
All Rights Reversed.