mirror of https://lore.kernel.org/lkml/
 help / color / mirror / Atom feed
* [PATCH 0/2] sched/deadline: fix the 0-lag time and extra_bw accounting
@ 2026-11-17 14:49 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 ` [PATCH 2/2] sched/deadline: Count only active CPUs when spreading extra_bw Mathieu Desnoyers
  0 siblings, 2 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

Hi Juri, Peter,

These two fixes are the ones that v7 of "sched/deadline: bandwidth
accounting fixes and selftests" announced under "Found, left for
separate patches" [1]. Both bugs are in upstream code. The Sashiko
review of v6 found them.

The fixes:

 1  Compute the 0-lag time on 128 bits. A task with a period of a few
    seconds then no longer keeps its bandwidth seconds too long.
 2  Spread extra_bw over the active CPUs only, in the two places that
    still count the whole span. SCHED_FLAG_RECLAIM tasks then reclaim
    their share.

Patch 1 applies on tip sched/urgent alone, and is marked for stable.
Patch 2 needs patch 4 of v7, which makes __dl_add() and __dl_sub()
accept 0 CPUs: dl_bw_cpus() can return 0. So this series is based on
v7.

Testing
=======

Patch 1 has a reproducer, which its message describes. It fails on tip
in 6 tries of 6, and passes with the patch in 6 of 6. Patch 2 was found
by reading. extra_bw is not visible from user space, so I have no
reproducer for it.

The 112 cases of the v7 selftests pass with both patches, in the 19
QEMU guests that the v7 cover letter lists. No kernel warning is
logged. Each patch builds alone, and checkpatch is clean.

How this was developed
======================

An LLM coding assistant wrote these patches and their messages, under
my direction and review. A reproducer that stops failing shows that the
symptom goes away. It does not show that the fix is the one you would
have written.

[1] https://lore.kernel.org/all/cover.1794922146.git.mathieu.desnoyers@efficios.com/

Mathieu Desnoyers (2):
  sched/deadline: Fix an overflow of the 0-lag time with long periods
  sched/deadline: Count only active CPUs when spreading extra_bw

 kernel/sched/deadline.c | 23 +++++++++++++++++------
 1 file changed, 17 insertions(+), 6 deletions(-)


base-commit: ec6f6731538e0d45872eb279fdeb477bed152d6f
prerequisite-patch-id: 5e2478ffdfb7583751bf44bdf87fb930bc23551b
prerequisite-patch-id: d5e5ef986ff2d9bc39a87b56e96a2acbd3158687
prerequisite-patch-id: 99e47f80396008ee2b2576157d37842481ce52d2
prerequisite-patch-id: a10824f98c11a4c902dad55cab3ec03b3dbe2c8a
prerequisite-patch-id: 6a944081caf562b37b617f6a763fb9c5e93b7671
prerequisite-patch-id: 16acf1d18f01d20310d6db767dfbec2f072e0372
prerequisite-patch-id: e1946bb015a7b14ed4e2cd0421e5e30b0c7afdda
prerequisite-patch-id: 4daf48a89779fbd8c8bc5fc1d7a7d6df9bca2d9d
prerequisite-patch-id: 069eafdf81a30c046a1a54638a2716d3f7d5b15c
prerequisite-patch-id: f8b34127a06e7503c069fb08e275574569aa1663
prerequisite-patch-id: 867205dd61f1097dba3faa6648243622e0a57112
prerequisite-patch-id: 00e953bbec4bd21e5d5ff6e218ca02ec3d77189f
prerequisite-patch-id: fb69a0665dc38ca9022cc2bd75234a90e2035b7f
prerequisite-patch-id: e5b851fc06511b47520dbbd96a7823cb28e83904
prerequisite-patch-id: 6e7ce0551aae3d1e5cdffcb79a9dfad9572d171e
prerequisite-patch-id: 8574b50d81a09ec6091e42d65338adcab2986d71
prerequisite-patch-id: cf098d7617ec51026a60140b231640a73a67be83
prerequisite-patch-id: b4ace4d6fbffab1d45765c86650ca535c4bade7e
prerequisite-patch-id: f6b9bef6e53a08be446fd431a8d6790470c74234
prerequisite-patch-id: 1aa25df96d60d30f549c71fdfba5589cb239928f
prerequisite-patch-id: 3f22a07ea1846d81570daafd00db92f077a6703e
prerequisite-patch-id: e1dd6913718da692992ed4c0304e56b93195327e
prerequisite-patch-id: 42ce74717bea531db1419582c647401d4edd497a
prerequisite-patch-id: a005df845d96a168895545d1ee2e003b353fbf98
prerequisite-patch-id: 7db308c051f710d98bdd1f661be5b9fa33120760
prerequisite-patch-id: ecd0fc0d0327f8eef27f504a92696c0e38622ce6
prerequisite-patch-id: 0b15882cde9c46c6a8bdd6f9d66b00b1b9669749
prerequisite-patch-id: 90bd9e96aa9b038296989ea3ceb3588b98c4dc8a
prerequisite-patch-id: 28aa2285131a249c03ec360b8ee95f427314c9ba
prerequisite-patch-id: 3d3525d4572c00db7586a2b863c9e918a0eb0c15
prerequisite-patch-id: 73b7bf5a66a4b43ebc393b7a77ec59cf92c6f944
prerequisite-patch-id: 9b860d340021441081e605651f409c46769501f2
prerequisite-patch-id: ab0784c824416be573685aac9c771dd4da6b15ca
prerequisite-patch-id: 2349b9f4fe6ec67608d52fb4ce3ae8b42d4e7471
prerequisite-patch-id: 1c864890d70c38372dc4ae9326e41b794e163ab8
prerequisite-patch-id: 3ba4159520b960e8059ccec735876cfeceaad5f4
prerequisite-patch-id: d38384e0b7d043a3556ee02fb09316a6227038da
prerequisite-patch-id: 72c83e4083d683436569565488149534319d065a
prerequisite-patch-id: 727a8041cecc638f8051ad069b7606515c1739c4
prerequisite-patch-id: d5fa12141d48e70e41d8fe3637facdb25f97d698
-- 
2.47.3


^ permalink raw reply	[flat|nested] 3+ messages in thread

* [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	[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	[flat|nested] 3+ messages in thread

end of thread, other threads:[~2026-11-17 14:49 UTC | newest]

Thread overview: 3+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
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 ` [PATCH 2/2] sched/deadline: Count only active CPUs when spreading extra_bw Mathieu Desnoyers

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®