Re: [PATCH v5 10/17] sched/deadline: Fix an overflow of the 0-lag time with long periods

From: Juri Lelli

Date: Fri Nov 20 2026 - 08:02:29 EST


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@xxxxxxxxxx>

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