From: Juri Lelli <juri.lelli@redhat.com>
To: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
Cc: peterz@infradead.org, mingo@redhat.com,
vincent.guittot@linaro.org, tglx@kernel.org, will@kernel.org,
boqun@kernel.org, dietmar.eggemann@arm.com, rostedt@goodmis.org,
bsegall@google.com, mgorman@suse.de, vschneid@redhat.com,
kprateek.nayak@amd.com, luca.abeni@santannapisa.it,
mathieu.poirier@linaro.org, longman@redhat.com,
ridong.chen@linux.dev, tj@kernel.org, hannes@cmpxchg.org,
mkoutny@suse.com, shuah@kernel.org, bigeasy@linutronix.de,
clrkwllms@kernel.org, parri.andrea@gmail.com,
m.szyprowski@samsung.com, kayracizmeci@gmail.com,
weihengqiuu@gmail.com, linux-kernel@vger.kernel.org,
cgroups@vger.kernel.org, linux-kselftest@vger.kernel.org,
linux-rt-devel@lists.linux.dev, stable@vger.kernel.org
Subject: Re: [PATCH v5 10/17] sched/deadline: Fix an overflow of the 0-lag time with long periods
Date: Fri, 20 Nov 2026 14:01:55 +0100 [thread overview]
Message-ID: <awBEww33F6yn0MBO@jlelli-thinkpadt14gen4.remote.csb> (raw)
In-Reply-To: <2be3813af9e997f5f7d9d3161d0b65b8d4ab917c.1795115075.git.mathieu.desnoyers@efficios.com>
Hello,
On 19/11/26 14:07, Mathieu Desnoyers wrote:
> When a deadline task blocks, task_non_contending() computes its 0-lag
> time:
>
> zerolag_time = deadline - runtime * dl_period / 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. 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. An overrun lasts at most
> + * about a tick, unless the CPU stalls. After a stall of seconds, with
> + * a long period and a short dl_runtime, the 0-lag time can overflow
> + * s64. It would be centuries away. In that case, release the bandwidth
> + * now.
> */
> - zerolag_time -= rq_clock(rq);
> + left = dl_se->deadline - rq_clock(rq);
> + if (dl_se->runtime < 0) {
> + u64 room = S64_MAX - max(left, 0LL);
> +
> + if (-dl_se->runtime > mul_u64_u64_div_u64(room, 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);
> + } 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);
Nitpick-ish, feel free to ignore: the logic is right, but it took me a
while to see which inequality each check stands for, and I fear the next
person looking at it (future me included) will have the same problem.
The multi-line branches also miss the braces the tip bracket rules ask
for.
How about moving it into a helper with one early return per case, and a
comment in front of each check saying what it compares? Something like
the below, on top of this patch. I don't think you need to respin the
whole series in case it makes sense, maybe just an updated version of
this patch will do?
Either way, you can add my
Reviewed-by: Juri Lelli <juri.lelli@redhat.com>
Thanks,
Juri
---
kernel/sched/deadline.c | 117 ++++++++++++++++++++++++----------------
1 file changed, 72 insertions(+), 45 deletions(-)
diff --git a/kernel/sched/deadline.c b/kernel/sched/deadline.c
index 63890866dd0c7..eab354e15acbb 100644
--- a/kernel/sched/deadline.c
+++ b/kernel/sched/deadline.c
@@ -377,6 +377,76 @@ static void dl_change_utilization(struct task_struct *p, u64 new_bw)
static void __dl_clear_params(struct sched_dl_entity *dl_se);
+/*
+ * Return the time from now to the 0-lag time of @dl_se, or a negative
+ * value if the 0-lag time has passed.
+ *
+ * The 0-lag time is when a task running at its reserved bandwidth would
+ * use up the runtime it has left:
+ *
+ * 0-lag = deadline - runtime * dl_period / dl_runtime
+ *
+ * Example: 30ms every 100ms, blocking 10ms into its period with 20ms
+ * left. 0-lag = 100 - 20 * 100 / 30 = 33ms. From there to the deadline,
+ * 30% of the CPU is exactly the 20ms left.
+ *
+ * The product can overflow 64 bits, so mul_u64_u64_div_u64() multiplies
+ * on 128 bits. Its quotient must still fit: on x86-64 it traps
+ * otherwise. Usually |runtime| <= dl_runtime and the quotient is at most
+ * dl_period.
+ *
+ * Each check compares against the bound scaled by dl_runtime / dl_period,
+ * That quotient cannot overflow, as dl_runtime <= dl_period.
+ */
+static s64 dl_time_to_zerolag(struct sched_dl_entity *dl_se, struct rq *rq)
+{
+ /* Time to the deadline. Negative if the deadline has passed. */
+ s64 left = dl_se->deadline - rq_clock(rq);
+
+ if (dl_se->runtime < 0) {
+ /*
+ * Overrun: the 0-lag time is after the deadline, by the time
+ * needed to pay the overrun back at the reserved bandwidth.
+ */
+ u64 overrun = -dl_se->runtime;
+ u64 room = S64_MAX - max(left, 0LL);
+
+ /*
+ * overrun * dl_period / dl_runtime > room: the result would
+ * overflow s64. The 0-lag time is centuries away, for a
+ * negligible bandwidth. Release it now.
+ */
+ if (overrun > mul_u64_u64_div_u64(room, dl_se->dl_runtime,
+ dl_se->dl_period)) {
+ return -1;
+ }
+
+ return left + mul_u64_u64_div_u64(overrun, dl_se->dl_period,
+ dl_se->dl_runtime);
+ }
+
+ /*
+ * Runtime left: the 0-lag time is before the deadline. It has
+ * passed if the deadline has.
+ */
+ if (left < 0)
+ return -1;
+
+ /*
+ * runtime * dl_period / dl_runtime > left: the 0-lag time has
+ * passed. The runtime left is more than the bandwidth gives until
+ * the deadline, as a wakeup would find with dl_entity_overflow().
+ */
+ if (dl_se->runtime > mul_u64_u64_div_u64(left, dl_se->dl_runtime,
+ dl_se->dl_period)) {
+ return -1;
+ }
+
+ /* The quotient is at most @left here. */
+ return left - mul_u64_u64_div_u64(dl_se->runtime, dl_se->dl_period,
+ dl_se->dl_runtime);
+}
+
/*
* The utilization of a task cannot be immediately removed from
* the rq active utilization (running_bw) when the task blocks.
@@ -436,7 +506,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, left;
+ s64 zerolag_time;
/*
* If this is a non-deadline task that has been boosted,
@@ -450,50 +520,7 @@ static void task_non_contending(struct sched_dl_entity *dl_se, bool dl_task)
WARN_ON(dl_se->dl_non_contending);
- /*
- * 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. An overrun lasts at most
- * about a tick, unless the CPU stalls. After a stall of seconds, with
- * a long period and a short dl_runtime, the 0-lag time can overflow
- * s64. It would be centuries away. In that case, release the bandwidth
- * now.
- */
- left = dl_se->deadline - rq_clock(rq);
- if (dl_se->runtime < 0) {
- u64 room = S64_MAX - max(left, 0LL);
-
- if (-dl_se->runtime > mul_u64_u64_div_u64(room, 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);
- } 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);
+ zerolag_time = dl_time_to_zerolag(dl_se, rq);
/*
* If the "0-lag time" already passed, decrease the active
--
2.56.0
next prev parent reply other threads:[~2026-11-20 13:02 UTC|newest]
Thread overview: 20+ messages / expand[flat|nested] mbox.gz Atom feed top
2026-11-19 19:06 [PATCH v5 00/17] sched/deadline: first bandwidth accounting fixes and selftests Mathieu Desnoyers
2026-11-19 19:06 ` [PATCH v5 01/17] sched: Refuse SCHED_FLAG_KEEP_PARAMS that would change the policy or the class Mathieu Desnoyers
2026-11-19 19:06 ` [PATCH v5 02/17] sched/deadline: Do not admit bandwidth for parameters that are kept Mathieu Desnoyers
2026-11-19 19:07 ` [PATCH v5 03/17] sched: Let a task boosted by a deadline waiter change its policy Mathieu Desnoyers
2026-11-19 19:07 ` [PATCH v5 04/17] sched/deadline: Do not divide by zero active CPUs of a root domain Mathieu Desnoyers
2026-11-19 19:07 ` [PATCH v5 05/17] sched/deadline: Refuse dl_server debugfs writes while the rq is offline Mathieu Desnoyers
2026-11-19 19:07 ` [PATCH v5 06/17] sched: Take cpuset_mutex for a deadline policy change only with pi Mathieu Desnoyers
2026-11-19 19:07 ` [PATCH v5 07/17] sched/deadline: Do not lose a throttled task switched out and back Mathieu Desnoyers
2026-11-19 19:07 ` [PATCH v5 08/17] sched/deadline: Do not replenish a boost from cleared parameters Mathieu Desnoyers
2026-11-19 19:07 ` [PATCH v5 09/17] sched/deadline: Reset the deadline and the runtime with the parameters Mathieu Desnoyers
2026-11-19 19:07 ` [PATCH v5 10/17] sched/deadline: Fix an overflow of the 0-lag time with long periods Mathieu Desnoyers
2026-11-20 13:01 ` Juri Lelli [this message]
2026-11-19 19:07 ` [PATCH v5 11/17] sched/deadline: Release the bandwidth of a task that leaves the class asleep Mathieu Desnoyers
2026-11-19 19:07 ` [PATCH v5 12/17] sched/deadline: Reject SCHED_DEADLINE on exited tasks Mathieu Desnoyers
2026-11-19 19:07 ` [PATCH v5 13/17] sched/deadline: Fix this_bw when a task is changed during a remote wakeup Mathieu Desnoyers
2026-11-19 19:07 ` [PATCH v5 14/17] sched/deadline: Check SCHED_DEADLINE affinity under the rq lock Mathieu Desnoyers
2026-11-19 19:07 ` [PATCH v5 15/17] sched/debug: Show the deadline bandwidth of each runqueue Mathieu Desnoyers
2026-11-19 19:07 ` [PATCH v5 16/17] selftests/sched: Add a test of SCHED_DEADLINE policy round trips Mathieu Desnoyers
2026-11-19 19:07 ` [PATCH v5 17/17] selftests/sched: Add a test of SCHED_DEADLINE bandwidth accounting Mathieu Desnoyers
2026-11-20 13:05 ` [PATCH v5 00/17] sched/deadline: first bandwidth accounting fixes and selftests Juri Lelli
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=awBEww33F6yn0MBO@jlelli-thinkpadt14gen4.remote.csb \
--to=juri.lelli@redhat.com \
--cc=bigeasy@linutronix.de \
--cc=boqun@kernel.org \
--cc=bsegall@google.com \
--cc=cgroups@vger.kernel.org \
--cc=clrkwllms@kernel.org \
--cc=dietmar.eggemann@arm.com \
--cc=hannes@cmpxchg.org \
--cc=kayracizmeci@gmail.com \
--cc=kprateek.nayak@amd.com \
--cc=linux-kernel@vger.kernel.org \
--cc=linux-kselftest@vger.kernel.org \
--cc=linux-rt-devel@lists.linux.dev \
--cc=longman@redhat.com \
--cc=luca.abeni@santannapisa.it \
--cc=m.szyprowski@samsung.com \
--cc=mathieu.desnoyers@efficios.com \
--cc=mathieu.poirier@linaro.org \
--cc=mgorman@suse.de \
--cc=mingo@redhat.com \
--cc=mkoutny@suse.com \
--cc=parri.andrea@gmail.com \
--cc=peterz@infradead.org \
--cc=ridong.chen@linux.dev \
--cc=rostedt@goodmis.org \
--cc=shuah@kernel.org \
--cc=stable@vger.kernel.org \
--cc=tglx@kernel.org \
--cc=tj@kernel.org \
--cc=vincent.guittot@linaro.org \
--cc=vschneid@redhat.com \
--cc=weihengqiuu@gmail.com \
--cc=will@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