mirror of https://lore.kernel.org/lkml/
 help / color / mirror / Atom feed
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


  reply	other threads:[~2026-11-20 13:02 UTC|newest]

Thread overview: 22+ 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:48   ` sashiko-bot
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-20 13:33     ` [PATCH v5.1 " Mathieu Desnoyers
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

all inboxes | Powered by JetHome®