* [PATCH 1/2] sched/deadline: Fix an overflow of the 0-lag time with long periods
2026-11-17 14:49 [PATCH 0/2] sched/deadline: fix the 0-lag time and extra_bw accounting Mathieu Desnoyers
@ 2026-11-17 14:49 ` Mathieu Desnoyers
2026-11-17 14:49 ` [PATCH 2/2] sched/deadline: Count only active CPUs when spreading extra_bw Mathieu Desnoyers
1 sibling, 0 replies; 3+ messages in thread
From: Mathieu Desnoyers @ 2026-11-17 14:49 UTC (permalink / raw)
To: juri.lelli, peterz, mingo, vincent.guittot
Cc: linux-kernel, Mathieu Desnoyers, dietmar.eggemann, rostedt,
bsegall, mgorman, vschneid, kprateek.nayak, luca.abeni, stable
When a deadline task blocks, task_non_contending() computes its 0-lag
time:
zerolag_time = deadline - runtime * dl_period / dl_runtime
A task that ran at its reserved bandwidth would use up its runtime left
at that time. Until then, the task still counts in running_bw. A task
that leaves SCHED_DEADLINE also keeps its bandwidth in total_bw until
then. This comes from commit 209a0cbda7a0 ("sched/deadline: Improve the
tracking of active utilization"), which adds the inactive timer of the
GRUB algorithm.
The product runtime * dl_period is computed on 64 bits, then divided as
an s64 by div64_long(). With a period of 4s, it passes S64_MAX once the
runtime left is above 2.3s. The default limit on the period is about
4.2s, so this needs no sysctl change. The quotient is then negative, and
the 0-lag time lands after the deadline.
On 32-bit, div64_long() also truncates dl_runtime to an s32. A
dl_runtime above about 2.1s then gives a wrong 0-lag time too. If root
raises the period limit, a dl_runtime that is a multiple of 2^32 ns
would divide by zero. This was found by reading.
The bandwidth is then released seconds late. Until then, the root domain
refuses deadline tasks that would fit. I tested this in an x86-64 guest
with one CPU. A task took a reservation of 3.1s every 4s, then went back
to SCHED_OTHER at once. A second task that asked for the same
reservation got EBUSY for 5.95s, in 6 tries of 6. That is the deadline
at 4s, plus the 1.95s that the wrapped product adds.
Fix this by multiplying on 128 bits with mul_u64_u64_div_u64().
cputime_adjust() uses the same helper. Its operands are unsigned. So
take the magnitude of the runtime, which is negative after an overrun,
and add or subtract the result. With the fix, the second task got its
reservation at once.
Fixes: 209a0cbda7a0 ("sched/deadline: Improve the tracking of active utilization")
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
Cc: stable@vger.kernel.org
---
kernel/sched/deadline.c | 17 ++++++++++++++---
1 file changed, 14 insertions(+), 3 deletions(-)
diff --git a/kernel/sched/deadline.c b/kernel/sched/deadline.c
index f1d259df8f2a..8c0c982810c1 100644
--- a/kernel/sched/deadline.c
+++ b/kernel/sched/deadline.c
@@ -693,9 +693,20 @@ static void task_non_contending(struct sched_dl_entity *dl_se, bool dl_task)
WARN_ON(dl_se->dl_non_contending);
- zerolag_time = dl_se->deadline -
- div64_long((dl_se->runtime * dl_se->dl_period),
- dl_se->dl_runtime);
+ /*
+ * The 0-lag time is the deadline minus the runtime left, scaled by
+ * dl_period / dl_runtime. The product of the runtime and dl_period
+ * can overflow s64 with periods of a few seconds, so multiply on 128
+ * bits. The runtime is negative after an overrun.
+ */
+ if (dl_se->runtime >= 0)
+ zerolag_time = dl_se->deadline -
+ mul_u64_u64_div_u64(dl_se->runtime, dl_se->dl_period,
+ dl_se->dl_runtime);
+ else
+ zerolag_time = dl_se->deadline +
+ mul_u64_u64_div_u64(-dl_se->runtime, dl_se->dl_period,
+ dl_se->dl_runtime);
/*
* Using relative times instead of the absolute "0-lag time"
--
2.47.3
^ permalink raw reply related [flat|nested] 3+ messages in thread* [PATCH 2/2] sched/deadline: Count only active CPUs when spreading extra_bw
2026-11-17 14:49 [PATCH 0/2] sched/deadline: fix the 0-lag time and extra_bw accounting Mathieu Desnoyers
2026-11-17 14:49 ` [PATCH 1/2] sched/deadline: Fix an overflow of the 0-lag time with long periods Mathieu Desnoyers
@ 2026-11-17 14:49 ` Mathieu Desnoyers
1 sibling, 0 replies; 3+ messages in thread
From: Mathieu Desnoyers @ 2026-11-17 14:49 UTC (permalink / raw)
To: juri.lelli, peterz, mingo, vincent.guittot
Cc: linux-kernel, Mathieu Desnoyers, dietmar.eggemann, rostedt,
bsegall, mgorman, vschneid, kprateek.nayak, luca.abeni
__dl_add() and __dl_sub() change the total_bw of a root domain. They
also spread the change over the extra_bw of its CPUs, which GRUB uses
for SCHED_FLAG_RECLAIM tasks. __dl_update() changes only the active
CPUs, so the cpus argument must count those. Most callers pass
dl_bw_cpus(), which does.
dl_task_offline_migration() and dl_add_task_root_domain() pass
cpumask_weight(rd->span) instead. That also counts the inactive CPUs of
the span. A span holds one while that CPU goes offline, which is when
dl_task_offline_migration() runs. Each active CPU then gets a smaller
share of the change than it should. A later change made with
dl_bw_cpus() does not undo it exactly. extra_bw stays off until the
next rebuild of the root domains resets it. SCHED_FLAG_RECLAIM tasks
would reclaim a little more or less than their share meanwhile. This
was found by reading.
Fix this by passing dl_bw_cpus() of the CPU whose root domain changes.
Fixes: 59d06cea1198 ("sched/deadline: Fix bandwidth accounting at all levels after offline migration")
Fixes: f9a25f776d78 ("cpusets: Rebuild root domain deadline accounting information")
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
---
kernel/sched/deadline.c | 6 +++---
1 file changed, 3 insertions(+), 3 deletions(-)
diff --git a/kernel/sched/deadline.c b/kernel/sched/deadline.c
index 8c0c982810c1..d80f3f6bdf3a 100644
--- a/kernel/sched/deadline.c
+++ b/kernel/sched/deadline.c
@@ -1021,7 +1021,7 @@ static struct rq *dl_task_offline_migration(struct rq *rq, struct task_struct *p
dl_b = &src_rq->rd->dl_bw;
raw_spin_lock(&dl_b->lock);
__dl_sub(dl_b, p->dl.dl_bw,
- cpumask_weight(src_rq->rd->span));
+ dl_bw_cpus(cpu_of(src_rq)));
raw_spin_unlock(&dl_b->lock);
}
/*
@@ -1033,7 +1033,7 @@ static struct rq *dl_task_offline_migration(struct rq *rq, struct task_struct *p
dl_b = &later_rq->rd->dl_bw;
raw_spin_lock(&dl_b->lock);
__dl_add(dl_b, p->dl.dl_bw,
- cpumask_weight(later_rq->rd->span));
+ dl_bw_cpus(cpu_of(later_rq)));
raw_spin_unlock(&dl_b->lock);
p->dl.dl_bw_cpu = later_rq->cpu;
p->dl.dl_bw_gen = dl_bw_gen;
@@ -4283,7 +4283,7 @@ void dl_add_task_root_domain(struct task_struct *p)
dl_b = &rq->rd->dl_bw;
raw_spin_lock(&dl_b->lock);
- __dl_add(dl_b, p->dl.dl_bw, cpumask_weight(rq->rd->span));
+ __dl_add(dl_b, p->dl.dl_bw, dl_bw_cpus(cpu));
raw_spin_unlock(&dl_b->lock);
p->dl.dl_bw_cpu = cpu;
p->dl.dl_bw_gen = dl_bw_gen;
--
2.47.3
^ permalink raw reply related [flat|nested] 3+ messages in thread