From: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
Cc: linux-kernel@vger.kernel.org,
Mathieu Desnoyers <mathieu.desnoyers@efficios.com>,
stable@vger.kernel.org
Subject: [PATCH v4 10/17] sched/deadline: Fix an overflow of the 0-lag time with long periods
Date: Thu, 19 Nov 2026 11:21:31 -0500 [thread overview]
Message-ID: <abbad2aa0ec392b1b0ede00b66b2d177d2b7b2df.1795103339.git.mathieu.desnoyers@efficios.com> (raw)
In-Reply-To: <cover.1795103339.git.mathieu.desnoyers@efficios.com>
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 no sysctl change is needed. 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. In an x86-64 guest, a task took a
reservation of 3.1s every 4s, then went back to SCHED_OTHER at once.
Another task asking for the same reservation got EBUSY for 5.95s.
Fix this by multiplying on 128 bits with mul_u64_u64_div_u64(). 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.
The quotient must still fit in 64 bits. On x86-64, mul_u64_u64_div_u64()
traps with a divide error otherwise. After a change of parameters, the
runtime and the deadline stay those of the old parameters until the
next period. The 0-lag time uses the new dl_runtime and dl_period. So
the runtime left can be far above dl_runtime. For example, root can
raise the period limit and give a task 150s every 300s. The task can
then shrink its runtime to 1024ns. Before the division, compare the
runtime left with the runtime that the parameters give until the
deadline. If it is larger, the 0-lag time has passed, and the bandwidth
is released at once. Otherwise, the quotient is at most the time to the
deadline.
The params_switched_asleep and params_shrunk_long_period cases of
deadline_bw_test, added later in this series, test this second part.
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 | 41 +++++++++++++++++++++++++++++++++--------
1 file changed, 33 insertions(+), 8 deletions(-)
diff --git a/kernel/sched/deadline.c b/kernel/sched/deadline.c
index d6d2657dcddd..5e4aff28e9bc 100644
--- a/kernel/sched/deadline.c
+++ b/kernel/sched/deadline.c
@@ -411,7 +411,7 @@ static void task_non_contending(struct sched_dl_entity *dl_se, bool dl_task)
struct hrtimer *timer = &dl_se->inactive_timer;
struct rq *rq = rq_of_dl_se(dl_se);
struct dl_rq *dl_rq = &rq->dl;
- s64 zerolag_time;
+ s64 zerolag_time, left;
/*
* If this is a non-deadline task that has been boosted,
@@ -425,15 +425,40 @@ 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);
-
/*
- * Using relative times instead of the absolute "0-lag time"
- * allows to simplify the code
+ * 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. Compute the 0-lag time relative to now.
+ *
+ * After a change of parameters, the runtime and the deadline stay
+ * those of the old parameters until the next period. The 0-lag time
+ * uses the new dl_runtime and dl_period. The runtime left can then be
+ * far above dl_runtime, and the quotient too large for 64 bits. So
+ * first compare the runtime left with the runtime that the new
+ * parameters give until the deadline:
+ *
+ * (deadline - now) * dl_runtime / dl_period
+ *
+ * If it is larger, the 0-lag time has passed, and the bandwidth is
+ * released now.
+ *
+ * The runtime is negative after an overrun. The next tick throttles
+ * the task, so the overrun is short and its quotient fits.
*/
- zerolag_time -= rq_clock(rq);
+ left = dl_se->deadline - rq_clock(rq);
+ if (dl_se->runtime < 0)
+ zerolag_time = left +
+ mul_u64_u64_div_u64(-dl_se->runtime, dl_se->dl_period,
+ dl_se->dl_runtime);
+ else if (left < 0 ||
+ dl_se->runtime > mul_u64_u64_div_u64(left, dl_se->dl_runtime,
+ dl_se->dl_period))
+ zerolag_time = -1;
+ else
+ zerolag_time = left -
+ mul_u64_u64_div_u64(dl_se->runtime, dl_se->dl_period,
+ dl_se->dl_runtime);
/*
* If the "0-lag time" already passed, decrease the active
--
2.47.3
next prev parent reply other threads:[~2026-11-19 16:21 UTC|newest]
Thread overview: 19+ messages / expand[flat|nested] mbox.gz Atom feed top
2026-11-19 16:21 [PATCH v4 00/17] sched/deadline: first bandwidth accounting fixes and selftests Mathieu Desnoyers
2026-11-19 16:21 ` [PATCH v4 01/17] sched: Refuse SCHED_FLAG_KEEP_PARAMS that would change the policy or the class Mathieu Desnoyers
2026-11-19 16:21 ` [PATCH v4 02/17] sched/deadline: Do not admit bandwidth for parameters that are kept Mathieu Desnoyers
2026-11-19 16:21 ` [PATCH v4 03/17] sched: Let a task boosted by a deadline waiter change its policy Mathieu Desnoyers
2026-11-19 16:21 ` [PATCH v4 04/17] sched/deadline: Do not divide by zero active CPUs of a root domain Mathieu Desnoyers
2026-11-19 16:21 ` [PATCH v4 05/17] sched/deadline: Refuse dl_server debugfs writes while the rq is offline Mathieu Desnoyers
2026-11-19 16:21 ` [PATCH v4 06/17] sched: Take cpuset_mutex for a deadline policy change only with pi Mathieu Desnoyers
2026-11-19 16:21 ` [PATCH v4 07/17] sched/deadline: Do not lose a throttled task switched out and back Mathieu Desnoyers
2026-11-19 16:21 ` [PATCH v4 08/17] sched/deadline: Do not replenish a boost from cleared parameters Mathieu Desnoyers
2026-11-19 16:21 ` [PATCH v4 09/17] sched/deadline: Reset the deadline and the runtime with the parameters Mathieu Desnoyers
2026-11-19 16:21 ` Mathieu Desnoyers [this message]
2026-11-19 16:21 ` [PATCH v4 11/17] sched/deadline: Release the bandwidth of a task that leaves the class asleep Mathieu Desnoyers
2026-11-19 16:21 ` [PATCH v4 12/17] sched/deadline: Reject SCHED_DEADLINE on exited tasks Mathieu Desnoyers
2026-11-19 16:21 ` [PATCH v4 13/17] sched/deadline: Fix this_bw when a task is changed during a remote wakeup Mathieu Desnoyers
2026-11-19 16:21 ` [PATCH v4 14/17] sched/deadline: Check SCHED_DEADLINE affinity under the rq lock Mathieu Desnoyers
2026-11-19 16:21 ` [PATCH v4 15/17] sched/debug: Show the deadline bandwidth of each runqueue Mathieu Desnoyers
2026-11-19 16:21 ` [PATCH v4 16/17] selftests/sched: Add a test of SCHED_DEADLINE policy round trips Mathieu Desnoyers
2026-11-19 16:21 ` [PATCH v4 17/17] selftests/sched: Add a test of SCHED_DEADLINE bandwidth accounting Mathieu Desnoyers
2026-11-19 16:22 ` [PATCH v4 00/17] sched/deadline: first bandwidth accounting fixes and selftests Mathieu Desnoyers
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=abbad2aa0ec392b1b0ede00b66b2d177d2b7b2df.1795103339.git.mathieu.desnoyers@efficios.com \
--to=mathieu.desnoyers@efficios.com \
--cc=linux-kernel@vger.kernel.org \
--cc=stable@vger.kernel.org \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox
all inboxes | Powered by JetHome®