[PATCH 00/12] sched/deadline: bandwidth accounting fixes and selftests

[PATCH 00/12] sched/deadline: bandwidth accounting fixes and selftests

[Mathieu Desnoyers]

Hi Juri,

Please find in this series eight fixes to SCHED_DEADLINE bandwidth
accounting, on top of your four in sched/urgent, with the selftests that
catch them.

One word before the details: I am at home with the concepts behind
SCHED_DEADLINE, but not with its implementation, and these patches were
written with an LLM assistant under my review ("How this was developed"
below). So I am asking those who know this code for a careful reading of
the fixes themselves. Each of them has a reproducer and was measured in
VMs, which says that the symptom goes away, not that the fix is the one
you would have written.

Two take the kernel down: a divide by zero in __dl_sub(), reachable from
a debugfs write to a fair server while its CPU goes offline or comes
online, and a BUG() when a deadline task's affinity has no active CPU
left, which priority inheritance and CPU hotplug reach on a default
kernel. The other six leave a root domain's total_bw, or a runqueue's
this_bw, holding what its tasks do not: the root domain then admits
deadline tasks beyond the capacity of its CPUs, or refuses every one of
them and refuses to offline its last CPU, and on the runqueue side the
kernel warns of the underflow.

They came out of a cgroup feature under development whose selftests hung
and flaked where the accounting drifts. Each fix has a reproducer: five
fail a case of the selftests here, one needs a kernel built without
cpusets, and the two that crash have standalone reproducers I can post.

The fixes
=========

 1  sched_setattr() with SCHED_FLAG_KEEP_PARAMS from SCHED_OTHER to
    SCHED_DEADLINE fails after reserving bandwidth that nothing gives
    back.
 2  __dl_sub() and __dl_add() divide a change of total_bw by the number
    of active CPUs of the root domain, which is 0 while a CPU passes
    through the default one.
 3  dl_task_root_domain_cpu() BUG()s when a deadline task's mask has no
    active CPU, as a boosted mutex owner's does when its CPU goes
    offline.
 4  a throttled task switched out of SCHED_DEADLINE and back before its
    0-lag time is left throttled with nothing to replenish it: it never
    runs again, and a fatal signal cannot make it run.
 5  a sleeper leaving the class releases bandwidth the root domain no
    longer holds, or never held.
 7  a rebuild of the root domains' accounting (any cpuset partition
    change, CPU hotplug) forgets the bandwidth of the tasks that left
    the class, or died, before their 0-lag time: the inactive timer then
    removes it a second time, or from a root domain that never had it.
 9  a task whose wakeup is left to the target CPU has its bandwidth on
    no runqueue while task_cpu() already names the destination: a
    parameter change meanwhile takes it off a runqueue that never held
    it, and this_bw underflows there for good.
 11 dl_rebuild_rd_accounting() is a stub without CONFIG_CPUSETS, so such
    a kernel loses the bandwidth of every deadline task at the first
    hotplug.

Patch 10 is not a fix: sched_debug gains each runqueue's this_bw and
running_bw, which is what makes patch 9's bug visible from userspace.
Patches 6, 8 and 12 are the selftests, 48 cases in three programs.

Testing
=======

In 8 QEMU guests of 8 vCPUs, the 48 cases pass on the series, every
time. No case fails on 4 vCPUs either, with PREEMPT_RT, with
CONFIG_SCHED_PROXY_EXEC on and off, or on a kernel built without
CONFIG_CPUSETS, where the cases that want a cpuset partition root skip.
No kernel warning in any run.

A bisect over the series, one kernel per patch that changes kernel code,
2 guests each and the same test binaries throughout, says what each
patch is worth in the suite:

    base  params_keep_class_change, throttled_round_trip,
          pi_former_owner_asleep, dies_before_rebuild,
          switched_out_before_rebuild, moved_after_switch_out and
          random_mix fail
    +1    params_keep_class_change passes
    +4    throttled_round_trip passes
    +5    pi_former_owner_asleep passes
    +7    the three rebuild cases and random_mix pass

params_waking needs patch 10's sched_debug sums to run at all: on a
kernel with patch 10 and without patch 9 it fails in 6 guests of 6, and
random_mix catches that bug too, in 1 of 3. Patch 11 shows in the five
hotplug cases of a kernel built without cpusets: three fail and two skip
for want of room without it, and the five pass with it. Patches 2 and 3
move nothing in the suite, by design: an unfixed kernel dies, so their
reproducers stand apart.

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

These patches, their messages and the tests were written by an LLM
coding assistant under my direction and review.

It started from the cgroup selftests of a feature I am developing, which
the assistant also wrote: one of them hung about once in 1350 runs, and
another failed about once in ten. Asking it to root-cause those two
flakes, rather than work around them, gave patches 4 and 7. Reviewing
your four fixes in sched/urgent with it gave patches 1 and 5. I then
asked for a selftest of the bandwidth accounting in its own right, and
for one area of coverage at a time: priority inheritance, parameter
changes, cpuset moves, deaths, sched_yield(), runtime overruns, GRUB
reclaiming, the fair servers, CPU hotplug, proxy execution, and a
randomized mix of all of them. That is deadline_bw_test, and building it
turned up patch 9, through the kernel's own this_bw underflow warning
under a parameter-change load, and patch 11, on a build without
cpusets. Patches 2 and 3 came from reading the code instead; their
reproducers were written afterwards, and each takes an unfixed kernel
down on the first round.

A second model reviewed the series, and its findings are folded in. The
assistant got things wrong on the way as well: one diagnosis of patch
9's bug was wrong twice over and was settled only by instrumenting a
kernel, and one assertion it had put in a test was itself racy and had
to go. The per-patch bisect above exists because I asked whether every
fix had a reproducer of its own.

Based on tip sched/urgent, at commit a2b67e904401 ("sched/deadline:
Reject SCHED_DEADLINE on exited tasks"); patch 5 builds on
commit 41a7968022ca ("sched/deadline: Fix total_bw leak when switching
away from SCHED_DEADLINE while !queued") there.

Mathieu Desnoyers (12):
  sched: Reject SCHED_FLAG_KEEP_PARAMS before reserving deadline
    bandwidth
  sched/deadline: Do not divide by zero active CPUs of a root domain
  sched/deadline: Do not BUG() on a deadline task with no active CPU
    allowed
  sched/deadline: Do not lose a throttled task switched out and back
  sched/deadline: Do not release a departing sleeper's bandwidth twice
  selftests/sched: Add a test of SCHED_DEADLINE policy round trips
  sched/deadline: Keep departing bandwidth across a root domain rebuild
  selftests/sched: Test SCHED_DEADLINE bandwidth across a root domain
    rebuild
  sched/deadline: Do not take a waking task's bandwidth off a runqueue
    it left
  sched/debug: Show the deadline bandwidth of each runqueue
  sched/deadline: Rebuild the root domains' accounting without cpusets
    too
  selftests/sched: Add a test of SCHED_DEADLINE bandwidth accounting

 include/linux/cpuset.h                        |    5 -
 include/linux/sched.h                         |   15 +
 include/linux/sched/deadline.h                |    6 +-
 kernel/cgroup/cpuset.c                        |   11 +-
 kernel/sched/deadline.c                       |  316 +-
 kernel/sched/debug.c                          |    2 +
 kernel/sched/syscalls.c                       |   24 +-
 tools/testing/selftests/sched/.gitignore      |    3 +
 tools/testing/selftests/sched/Makefile        |    1 +
 .../selftests/sched/deadline_bw_test.c        | 3182 +++++++++++++++++
 .../selftests/sched/deadline_rebuild_test.c   |  462 +++
 .../selftests/sched/deadline_switch_test.c    |  332 ++
 12 files changed, 4292 insertions(+), 67 deletions(-)
 create mode 100644 tools/testing/selftests/sched/deadline_bw_test.c
 create mode 100644 tools/testing/selftests/sched/deadline_rebuild_test.c
 create mode 100644 tools/testing/selftests/sched/deadline_switch_test.c

-- 
2.47.3

[PATCH 01/12] sched: Reject SCHED_FLAG_KEEP_PARAMS before reserving deadline bandwidth

[Mathieu Desnoyers]

__sched_setscheduler() returns -EINVAL for a SCHED_FLAG_KEEP_PARAMS
request that would change scheduling class, after sched_dl_overflow()
has reserved the bandwidth of the request, and nothing gives it back.
Switching a SCHED_OTHER task to SCHED_DEADLINE that way fails and leaks
the runtime that sched_setattr() filled in from the task's slice, up to
100ms with a custom one, into the root domain's total_bw. Repeated, it
makes the root domain refuse every deadline task, and refuse to offline
its last CPU.

Reserve the bandwidth after that check, last of the checks. A refused
request also leaves sched_reset_on_fork as it was again.

Fixes: 8a70415351ba ("sched: Reject SCHED_FLAG_KEEP_PARAMS when it would change scheduling class")
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
---
 kernel/sched/syscalls.c | 24 +++++++++++++-----------
 1 file changed, 13 insertions(+), 11 deletions(-)

diff --git a/kernel/sched/syscalls.c b/kernel/sched/syscalls.c
index 3fa447aabe7f..f0b7b2d52614 100644
--- a/kernel/sched/syscalls.c
+++ b/kernel/sched/syscalls.c
@@ -655,17 +655,6 @@ int __sched_setscheduler(struct task_struct *p,
 		goto recheck;
 	}
 
-	/*
-	 * If setscheduling to SCHED_DEADLINE (or changing the parameters
-	 * of a SCHED_DEADLINE task) we need to check if enough bandwidth
-	 * is available.
-	 */
-	if ((dl_policy(policy) || dl_task(p)) && sched_dl_overflow(p, policy, attr)) {
-		retval = -EBUSY;
-		goto unlock;
-	}
-
-	p->sched_reset_on_fork = reset_on_fork;
 	oldprio = p->prio;
 
 	newprio = __normal_prio(policy, attr->sched_priority, attr->sched_nice);
@@ -699,6 +688,19 @@ int __sched_setscheduler(struct task_struct *p,
 		queue_flags |= DEQUEUE_CLASS;
 	}
 
+	/*
+	 * If setscheduling to SCHED_DEADLINE (or changing the parameters
+	 * of a SCHED_DEADLINE task) we need to check if enough bandwidth
+	 * is available. Last of the checks: nothing gives back the
+	 * bandwidth it reserves.
+	 */
+	if ((dl_policy(policy) || dl_task(p)) && sched_dl_overflow(p, policy, attr)) {
+		retval = -EBUSY;
+		goto unlock;
+	}
+
+	p->sched_reset_on_fork = reset_on_fork;
+
 	scx_prepare_setscheduler(p, policy);
 
 	scoped_guard (sched_change, p, queue_flags) {
-- 
2.47.3

[PATCH 02/12] sched/deadline: Do not divide by zero active CPUs of a root domain

[Mathieu Desnoyers]

__dl_sub() and __dl_add() spread a change of a root domain's total_bw
over the extra_bw of its active CPUs, dividing it by their number, which
their callers take from dl_bw_cpus(). That number is 0 for a root domain
whose CPUs all went offline, such as the default root domain, which
holds the offline CPUs: the division then traps.

A debugfs write of a fair server's runtime or period reaches it while
its CPU goes offline or comes online. From the rebuild of the root
domains in sched_cpu_deactivate() until the CPU is offline, and from the
CPU online until sched_cpu_activate(), the CPU sits in the default root
domain, with no active CPU. A write that leaves the server's bandwidth
as it is passes admission there, __dl_overflow() comparing that root
domain's capacity, 0, with total_bw less the old bandwidth plus the new,
0 as well, and dl_server_apply_params() divides. Any other value is
refused with EBUSY, higher directly, lower through the unsigned
subtraction. Once the CPU is offline the write is refused, since
commit 4043f5498416 ("sched/deadline: Reject debugfs dl_server writes
for offline CPUs").

Writing a fair server's own runtime back in a loop while its CPU goes
offline and online oopses on the first round, in 8-CPU VMs of v7.4-rc1
with the four deadline fixes of sched/urgent:

  Oops: divide error: 0000 [#1] SMP NOPTI
  CPU: 6 UID: 0 PID: 110 Comm: dl_server_div0
  RIP: 0010:dl_server_apply_params+0x335/0x380
  Call Trace:
   <TASK>
   sched_server_write_common.isra.0+0x1c0/0x260
   full_proxy_write+0x58/0x90
   vfs_write+0xcb/0x550
   ksys_write+0x6c/0xe0
   do_syscall_64+0x109/0x5d0
   entry_SYSCALL_64_after_hwframe+0x77/0x7f

inactive_task_timer() can reach it too, found by reading: it releases
the bandwidth of a task that left SCHED_DEADLINE, or died, before its
0-lag time from the root domain of the CPU the task is on, and that CPU
may go offline before the timer fires. With admission control off, so
may sched_setattr() to SCHED_DEADLINE of a task asleep on an offline
CPU.

With no active CPU there is no extra_bw to update: change total_bw
alone. 20 rounds of the reproducer leave no warning then.

Fixes: daec57983670 ("sched/deadline: Reclaim bandwidth not used by dl tasks")
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
---
 kernel/sched/deadline.c | 11 +++++++++--
 1 file changed, 9 insertions(+), 2 deletions(-)

diff --git a/kernel/sched/deadline.c b/kernel/sched/deadline.c
index 963fda6ddb7f..dadda1a528ec 100644
--- a/kernel/sched/deadline.c
+++ b/kernel/sched/deadline.c
@@ -189,18 +189,25 @@ void __dl_update(struct dl_bw *dl_b, s64 bw)
 	}
 }
 
+/*
+ * @cpus is the number of active CPUs of the root domain, whose extra_bw
+ * shares the change: none once they all went offline, and total_bw alone
+ * changes then.
+ */
 static inline
 void __dl_sub(struct dl_bw *dl_b, u64 tsk_bw, int cpus)
 {
 	dl_b->total_bw -= tsk_bw;
-	__dl_update(dl_b, (s32)tsk_bw / cpus);
+	if (cpus)
+		__dl_update(dl_b, (s32)tsk_bw / cpus);
 }
 
 static inline
 void __dl_add(struct dl_bw *dl_b, u64 tsk_bw, int cpus)
 {
 	dl_b->total_bw += tsk_bw;
-	__dl_update(dl_b, -((s32)tsk_bw / cpus));
+	if (cpus)
+		__dl_update(dl_b, -((s32)tsk_bw / cpus));
 }
 
 static inline bool
-- 
2.47.3

[PATCH 03/12] sched/deadline: Do not BUG() on a deadline task with no active CPU allowed

[Mathieu Desnoyers]

dl_task_root_domain_cpu() finds the root domain that holds a deadline
task's bandwidth from the first active CPU of the task's mask, and
BUG()s when the mask has none. A mask can have none:

 - a task boosted into the deadline class by priority inheritance keeps
   the affinity of its own policy, which may allow one CPU alone, or a
   cpuset of one. dl_task_needs_bw_move() and set_cpus_allowed_dl()
   take it for a deadline task, dl_task(p) being true, and look the root
   domain up from the mask they are replacing, which allows that CPU,
   inactive by then: the cpuset code updates the masks of a cpuset's
   tasks once the CPU is inactive, and select_fallback_rq() widens the
   mask of a task it pushes off that CPU;
 - with admission control off (sched_rt_runtime_us at -1), a deadline
   task may be pinned to fewer CPUs than its root domain spans, and
   those may all go offline.

Both take the kernel down on the first try, in 8-CPU VMs of v7.4-rc1
with the four deadline fixes of sched/urgent. The priority inheritance
one, which asks for no unusual configuration, through the wakeup of the
boosted owner:

  kernel BUG at kernel/sched/deadline.c:3340!
  CPU: 7 UID: 0 PID: 0 Comm: swapper/7
  RIP: 0010:set_cpus_allowed_dl+0xf0/0x100
  Call Trace:
   <IRQ>
   set_cpus_allowed_force+0x9f/0xf0
   cpuset_cpus_allowed_fallback+0x12b/0x1d0
   select_fallback_rq+0x238/0x340
   try_to_wake_up+0x2a0/0xb70

Fall back to the CPU the task last ran on, which these callers used
before the commit this one fixes. Its root domain may have no active CPU
left: the previous patch has __dl_sub() and __dl_add() take that. Ten
rounds of each case leave no warning with it.

Fixes: b4a61fdc19c5 ("sched/deadline: Fix stale root domain in cpuset bandwidth transfer")
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
---
 kernel/sched/deadline.c | 8 +++++++-
 1 file changed, 7 insertions(+), 1 deletion(-)

diff --git a/kernel/sched/deadline.c b/kernel/sched/deadline.c
index dadda1a528ec..30a52e42c26d 100644
--- a/kernel/sched/deadline.c
+++ b/kernel/sched/deadline.c
@@ -3338,13 +3338,19 @@ static void task_woken_dl(struct rq *rq, struct task_struct *p)
  * current cpus_mask (not yet updated to the new mask) to find the
  * actual root domain. Use cpus_mask rather than cpus_ptr, which
  * may be temporarily narrowed by migrate_disable().
+ *
+ * The mask has no active CPU left when the CPUs it allows went offline,
+ * which the affinity of a deadline task allows with admission control
+ * off, and that of a task boosted into the deadline class by priority
+ * inheritance always: fall back to the CPU the task last ran on.
  */
 static unsigned int dl_task_root_domain_cpu(struct task_struct *p)
 {
 	unsigned int cpu;
 
 	cpu = cpumask_first_and(&p->cpus_mask, cpu_active_mask);
-	BUG_ON(cpu >= nr_cpu_ids);
+	if (cpu >= nr_cpu_ids)
+		cpu = task_cpu(p);
 	return cpu;
 }
 
-- 
2.47.3

[PATCH 04/12] sched/deadline: Do not lose a throttled task switched out and back

[Mathieu Desnoyers]

A SCHED_DEADLINE task that is throttled, switched to another policy and
switched back before its 0-lag time can be left throttled with nothing
to replenish it: runnable, queued as far as the core is concerned, but
on no dl_rq and with no timer pending. It never runs again, and a fatal
signal cannot make it run; only another switch out of SCHED_DEADLINE
requeues it.

 1. the task exhausts its runtime: dl_throttled is set, and the
    replenishment timer armed for the start of its next period;
 2. sched_setscheduler() switches it to SCHED_OTHER: switched_from_dl()
    calls task_non_contending(), which arms the inactive timer for the
    0-lag time; the parameters are kept until then, so that leaving and
    reentering SCHED_DEADLINE gains no bandwidth;
 3. the replenishment timer fires: dl_task_timer() finds a task that is
    not a deadline task and returns, dl_throttled still set;
 4. sched_setattr() switches it back before the 0-lag time:
    switched_to_dl() cancels the inactive timer, and enqueue_dl_entity()
    leaves a throttled task to its replenishment timer, which has fired
    already.

The window between the deadline and the 0-lag time is the overrun
scaled by period/runtime: about 100us for an overrun of 20us at 20%
bandwidth. The replenishment timer cleared the parameters, dl_throttled
included, of a task it found out of SCHED_DEADLINE until
commit 209a0cbda7a0 ("sched/deadline: Improve the tracking of active
utilization") moved that reset to the inactive timer, at the 0-lag
time.

Clear dl_throttled there again. The deadline has passed by then, so a
return before the 0-lag time starts a new period when the task is
enqueued (ENQUEUE_MOVE, or the wakeup of a sleeper), as the
replenishment would have; a return after it finds the parameters reset
by the inactive timer, as before.

The selftest added two patches later fails its throttled_round_trip
case 8 times out of 8, on v7.3 as on v7.4-rc1 with the four deadline
fixes of sched/urgent, and passes it 8 times out of 8 with this change.
It was found by a cgroup selftest under development,
test_concurrency_deadline, which hung about once in 1350 runs.

Fixes: 209a0cbda7a0 ("sched/deadline: Improve the tracking of active utilization")
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
---
 kernel/sched/deadline.c | 11 +++++++++--
 1 file changed, 9 insertions(+), 2 deletions(-)

diff --git a/kernel/sched/deadline.c b/kernel/sched/deadline.c
index 30a52e42c26d..d474fbfd9be6 100644
--- a/kernel/sched/deadline.c
+++ b/kernel/sched/deadline.c
@@ -1232,10 +1232,17 @@ static enum hrtimer_restart dl_task_timer(struct hrtimer *timer)
 
 	/*
 	 * The task might have changed its scheduling policy to something
-	 * different than SCHED_DEADLINE (through switched_from_dl()).
+	 * different than SCHED_DEADLINE (through switched_from_dl()). It
+	 * keeps its parameters until its 0-lag time and may come back to
+	 * SCHED_DEADLINE before then, switched_to_dl() cancelling the
+	 * inactive timer: it must not come back throttled, since this was
+	 * its replenishment. Its deadline has passed: the enqueue starts a
+	 * new period.
 	 */
-	if (!dl_task(p))
+	if (!dl_task(p)) {
+		dl_se->dl_throttled = 0;
 		goto unlock;
+	}
 
 	/*
 	 * The task might have been boosted by someone else and might be in the
-- 
2.47.3

[PATCH 05/12] sched/deadline: Do not release a departing sleeper's bandwidth twice

[Mathieu Desnoyers]

Commit 41a7968022ca ("sched/deadline: Fix total_bw leak when switching
away from SCHED_DEADLINE while !queued") releases the bandwidth of a
task that leaves SCHED_DEADLINE asleep with no inactive timer pending.
Three cases release what the root domain no longer holds, or never held:

 - the task keeps its parameters. inactive_task_timer() resets them
   once it has released the bandwidth (__dl_clear_params()); left in
   place, task_contending() and task_non_contending() take the task,
   now of another policy, for one with bandwidth when priority
   inheritance boosts it into the deadline class, and a deboost while
   it sleeps releases that bandwidth from total_bw a second time. The
   root domain then admits deadline tasks beyond its capacity;
 - a task deboosted from priority inheritance with no parameters of its
   own, and a special one (SCHED_FLAG_SUGOV), have no bandwidth in
   total_bw. Releasing 0 changes nothing, and the root domain that
   dl_task_root_domain_cpu() finds from the task's mask means nothing
   either: a sleeping task of another policy may have no active CPU in
   its mask, a CPU it is pinned to having gone offline, until its next
   wakeup widens it;
 - migrate_task_rq_dl() clears dl_non_contending when it cannot cancel
   the inactive timer because its handler runs. That handler, once it
   takes the task's locks, finds it out of SCHED_DEADLINE and releases
   total_bw itself.

Release for a task with parameters of its own, not special, and reset
its parameters afterwards, once sub_rq_bw(), which reads its dl_bw, is
done: a handler that runs late then finds no bandwidth to release. A
test of hrtimer_active() would not tell that handler apart: it stays
true after the handler returns, until the hrtimer code clears its
running state, and the bandwidth of a task switched out meanwhile would
never be released.

The deadline_bw_test selftest, added later in this series, reproduces
the first case as pi_former_owner_asleep: in a one-CPU partition with
room, the waiter of its second round is refused as a deadline task,
total_bw having wrapped. The other two were found by reading.

Fixes: 41a7968022ca ("sched/deadline: Fix total_bw leak when switching away from SCHED_DEADLINE while !queued")
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
---
 kernel/sched/deadline.c | 22 +++++++++++++++++++++-
 1 file changed, 21 insertions(+), 1 deletion(-)

diff --git a/kernel/sched/deadline.c b/kernel/sched/deadline.c
index d474fbfd9be6..3c57e5f5fc05 100644
--- a/kernel/sched/deadline.c
+++ b/kernel/sched/deadline.c
@@ -3567,6 +3567,8 @@ static void switched_from_dl(struct rq *rq, struct task_struct *p)
 	dec_dl_tasks_cs(p);
 
 	if (!task_on_rq_queued(p)) {
+		bool released = false;
+
 		if (p->dl.dl_non_contending) {
 			/*
 			 * Inactive timer is armed. However, p is leaving
@@ -3579,12 +3581,18 @@ static void switched_from_dl(struct rq *rq, struct task_struct *p)
 			 * release total_bw via __dl_sub().
 			 */
 			sub_running_bw(&p->dl, &rq->dl);
-		} else {
+		} else if (p->dl.dl_runtime && !dl_entity_is_special(&p->dl)) {
 			/*
 			 * No pending inactive timer: the task never ran as
 			 * DEADLINE or the timer already fired while still
 			 * DEADLINE (only dropping running_bw at that time).
 			 * Nobody else will release total_bw, do it now.
+			 *
+			 * Not for a task without parameters of its own, one
+			 * deboosted from priority inheritance, whose mask may
+			 * have no active CPU for dl_task_root_domain_cpu(),
+			 * nor for a special one: neither has bandwidth in
+			 * total_bw.
 			 */
 			unsigned int cpu = dl_task_root_domain_cpu(p);
 			struct dl_bw *dl_b = &cpu_rq(cpu)->rd->dl_bw;
@@ -3592,8 +3600,20 @@ static void switched_from_dl(struct rq *rq, struct task_struct *p)
 			raw_spin_lock(&dl_b->lock);
 			__dl_sub(dl_b, p->dl.dl_bw, dl_bw_cpus(cpu));
 			raw_spin_unlock(&dl_b->lock);
+			released = true;
 		}
 		sub_rq_bw(&p->dl, &rq->dl);
+		/*
+		 * Released: reset the parameters, as inactive_task_timer()
+		 * does. Kept, they would make the task one with bandwidth to
+		 * task_contending() and task_non_contending() once priority
+		 * inheritance boosts it, and a deboost while it sleeps would
+		 * release that bandwidth again. So would the inactive timer's
+		 * handler when it runs late, dl_non_contending cleared under
+		 * it by migrate_task_rq_dl(): it finds !dl_task(p).
+		 */
+		if (released)
+			__dl_clear_params(&p->dl);
 	}
 
 	/*
-- 
2.47.3

[PATCH 06/12] selftests/sched: Add a test of SCHED_DEADLINE policy round trips

[Mathieu Desnoyers]

Add deadline_switch_test, with a case for the fix two patches back and
one for commit 41a7968022ca ("sched/deadline: Fix total_bw leak when
switching away from SCHED_DEADLINE while !queued"):

 - throttled_round_trip: a task with a runtime of 10ms per 2s period
   spins, so that each replenishment throttles it again at once. Right
   after a throttle it is switched to SCHED_OTHER, and back 200us after
   its deadline: past its replenishment timer, and before its 0-lag
   time, which the overrun scaled by 200 puts later. It must run again
   within a period and a half. Three attempts;
 - asleep_round_trip: a task of 9ms every 10ms, running 0.2ms and
   sleeping 50ms, is switched to SCHED_OTHER and back while it sleeps
   past its 0-lag time, enough times that a leak of its bandwidth at
   each round trip fills the root domain: sched_setattr() then fails
   with EBUSY. Skipped without admission control (sched_rt_runtime_us
   at -1). A kernel that leaks is left without SCHED_DEADLINE bandwidth
   until a reboot, so this case runs last.

In 8 VMs of 8 vCPUs each, v7.3 fails both cases, and v7.4-rc1 with the
four deadline fixes of sched/urgent fails the first; with the two
previous patches as well both pass; every time.

Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
---
 tools/testing/selftests/sched/.gitignore      |   1 +
 tools/testing/selftests/sched/Makefile        |   1 +
 .../selftests/sched/deadline_switch_test.c    | 332 ++++++++++++++++++
 3 files changed, 334 insertions(+)
 create mode 100644 tools/testing/selftests/sched/deadline_switch_test.c

diff --git a/tools/testing/selftests/sched/.gitignore b/tools/testing/selftests/sched/.gitignore
index 6996d4654d92..d97f40c21ab5 100644
--- a/tools/testing/selftests/sched/.gitignore
+++ b/tools/testing/selftests/sched/.gitignore
@@ -1 +1,2 @@
 cs_prctl_test
+deadline_switch_test
diff --git a/tools/testing/selftests/sched/Makefile b/tools/testing/selftests/sched/Makefile
index 099ee9213557..ae9421eabf15 100644
--- a/tools/testing/selftests/sched/Makefile
+++ b/tools/testing/selftests/sched/Makefile
@@ -10,5 +10,6 @@ LDLIBS += -lpthread
 
 TEST_GEN_FILES := cs_prctl_test
 TEST_PROGS := cs_prctl_test
+TEST_GEN_PROGS := deadline_switch_test
 
 include ../lib.mk
diff --git a/tools/testing/selftests/sched/deadline_switch_test.c b/tools/testing/selftests/sched/deadline_switch_test.c
new file mode 100644
index 000000000000..81125d81b618
--- /dev/null
+++ b/tools/testing/selftests/sched/deadline_switch_test.c
@@ -0,0 +1,332 @@
+// SPDX-License-Identifier: GPL-2.0
+/*
+ * A SCHED_DEADLINE task switched to SCHED_OTHER and back:
+ *
+ *  - throttled: switched out after its runtime ran out, and back after
+ *    its deadline but before its 0-lag time, it must run again, the
+ *    replenishment it missed while out of SCHED_DEADLINE or not;
+ *  - asleep past its 0-lag time: its bandwidth must leave the root domain
+ *    when it leaves SCHED_DEADLINE, or the switch back adds it again and
+ *    sched_setattr() soon refuses SCHED_DEADLINE with EBUSY.
+ *
+ * On a kernel that leaks, the second case leaves the root domain without
+ * bandwidth for new SCHED_DEADLINE tasks until a reboot.
+ */
+#define _GNU_SOURCE
+#include <errno.h>
+#include <sched.h>
+#include <signal.h>
+#include <stdint.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+#include <sys/mman.h>
+#include <sys/syscall.h>
+#include <sys/sysinfo.h>
+#include <sys/wait.h>
+#include <time.h>
+#include <unistd.h>
+
+#include "../kselftest.h"
+
+#ifndef SCHED_DEADLINE
+#define SCHED_DEADLINE	6
+#endif
+
+#define NSEC_PER_USEC	1000ULL
+#define NSEC_PER_MSEC	1000000ULL
+#define NSEC_PER_SEC	1000000000ULL
+
+struct dl_attr {
+	uint32_t size;
+	uint32_t sched_policy;
+	uint64_t sched_flags;
+	int32_t sched_nice;
+	uint32_t sched_priority;
+	uint64_t sched_runtime;
+	uint64_t sched_deadline;
+	uint64_t sched_period;
+};
+
+/* Written by the child, read by the parent. */
+struct shared {
+	uint64_t stamp;		/* last time the child ran */
+	uint64_t run_start;	/* when it last resumed after a gap */
+	uint64_t runs;		/* resumptions after a gap */
+	uint64_t sleeps;	/* sleeps begun */
+};
+
+static uint64_t now_ns(void)
+{
+	struct timespec ts;
+
+	clock_gettime(CLOCK_MONOTONIC, &ts);
+	return ts.tv_sec * NSEC_PER_SEC + ts.tv_nsec;
+}
+
+static void sleep_ns(uint64_t ns)
+{
+	struct timespec ts = { .tv_sec = ns / NSEC_PER_SEC, .tv_nsec = ns % NSEC_PER_SEC };
+
+	while (nanosleep(&ts, &ts) && errno == EINTR)
+		;
+}
+
+static void sleep_until(uint64_t t)
+{
+	struct timespec ts = { .tv_sec = t / NSEC_PER_SEC, .tv_nsec = t % NSEC_PER_SEC };
+
+	while (clock_nanosleep(CLOCK_MONOTONIC, TIMER_ABSTIME, &ts, NULL) == EINTR)
+		;
+}
+
+static int set_deadline(pid_t pid, uint64_t runtime, uint64_t period)
+{
+	struct dl_attr attr = {
+		.size = sizeof(attr),
+		.sched_policy = SCHED_DEADLINE,
+		.sched_runtime = runtime,
+		.sched_deadline = period,
+		.sched_period = period,
+	};
+
+	return syscall(__NR_sched_setattr, pid, &attr, 0) ? -errno : 0;
+}
+
+static int set_other(pid_t pid)
+{
+	struct sched_param sp = { .sched_priority = 0 };
+
+	return sched_setscheduler(pid, SCHED_OTHER, &sp) ? -errno : 0;
+}
+
+static struct shared *sh;
+
+static void reap(pid_t pid)
+{
+	int status;
+
+	if (pid <= 0)
+		return;
+	if (kill(pid, SIGKILL) && errno != ESRCH)
+		ksft_print_msg("kill %d: %s\n", pid, strerror(errno));
+	/* A task lost in SCHED_DEADLINE runs again, and dies, once out of it. */
+	set_other(pid);			/* gone already: nothing to switch */
+	while (waitpid(pid, &status, 0) != pid) {
+		if (errno == EINTR)
+			continue;
+		ksft_print_msg("waitpid %d: %s\n", pid, strerror(errno));
+		break;
+	}
+}
+
+/* The child died before the case was done: @status says whether it skips. */
+static int gone(int status)
+{
+	if (WIFEXITED(status) && WEXITSTATUS(status) == KSFT_SKIP) {
+		ksft_print_msg("SCHED_DEADLINE refused\n");
+		return KSFT_SKIP;
+	}
+	if (WIFSIGNALED(status))
+		ksft_print_msg("the task died of signal %d\n", WTERMSIG(status));
+	else
+		ksft_print_msg("the task exited with %d\n", WEXITSTATUS(status));
+	return KSFT_FAIL;
+}
+
+/* Spins: runs out of its runtime at once, and is throttled. */
+static void spinner(void)
+{
+	uint64_t last = now_ns();
+
+	for (;;) {
+		uint64_t t = now_ns();
+
+		if (t - last > 2 * NSEC_PER_MSEC) {
+			__atomic_store_n(&sh->run_start, t, __ATOMIC_RELAXED);
+			__atomic_fetch_add(&sh->runs, 1, __ATOMIC_RELEASE);
+		}
+		__atomic_store_n(&sh->stamp, t, __ATOMIC_RELEASE);
+		last = t;
+	}
+}
+
+#define LOST_RUNTIME	(10 * NSEC_PER_MSEC)
+#define LOST_PERIOD	(2 * NSEC_PER_SEC)
+#define LOST_MARGIN	(200 * NSEC_PER_USEC)
+
+/*
+ * The window between the deadline and the 0-lag time is the overrun
+ * scaled by period/runtime: 200 here, so that an overrun of 2us leaves
+ * 400us. A runtime longer than a tick keeps an overrun caught at the tick
+ * from carrying past the next replenishment, which comes a period after
+ * the last. The switch back comes LOST_MARGIN after the deadline, once
+ * the replenishment timer has fired on a task out of SCHED_DEADLINE.
+ */
+static int test_throttled_round_trip(void)
+{
+	int attempt, ret = KSFT_PASS, err;
+	pid_t pid;
+
+	memset(sh, 0, sizeof(*sh));
+	pid = fork();
+	if (pid < 0) {
+		ksft_print_msg("fork: %s\n", strerror(errno));
+		return KSFT_FAIL;
+	}
+	if (!pid) {
+		if (set_deadline(0, LOST_RUNTIME, LOST_PERIOD))
+			_exit(KSFT_SKIP);
+		spinner();
+	}
+	for (attempt = 0; attempt < 3 && ret == KSFT_PASS; attempt++) {
+		uint64_t runs, r, s, t;
+
+		/* A resumption at a replenishment, D, then its throttle. */
+		runs = __atomic_load_n(&sh->runs, __ATOMIC_ACQUIRE);
+		t = now_ns();
+		while (__atomic_load_n(&sh->runs, __ATOMIC_ACQUIRE) == runs) {
+			if (now_ns() - t > 3 * LOST_PERIOD) {
+				int status;
+
+				if (waitpid(pid, &status, WNOHANG) == pid)
+					return gone(status);
+				ksft_print_msg("the task did not resume within 3 periods\n");
+				reap(pid);
+				return KSFT_FAIL;
+			}
+			sleep_ns(NSEC_PER_MSEC);
+		}
+		r = __atomic_load_n(&sh->run_start, __ATOMIC_RELAXED);
+		do {
+			s = __atomic_load_n(&sh->stamp, __ATOMIC_ACQUIRE);
+			sleep_ns(2 * NSEC_PER_MSEC);
+		} while (__atomic_load_n(&sh->stamp, __ATOMIC_ACQUIRE) != s);
+		/* Throttled until D + period: out, and back after that. */
+		err = set_other(pid);
+		if (!err) {
+			sleep_until(r + LOST_PERIOD + LOST_MARGIN);
+			err = set_deadline(pid, LOST_RUNTIME, LOST_PERIOD);
+		}
+		if (err) {
+			ksft_print_msg("policy switch: %s\n", strerror(-err));
+			ret = KSFT_FAIL;
+			break;
+		}
+		sleep_ns(10 * NSEC_PER_MSEC);
+		s = __atomic_load_n(&sh->stamp, __ATOMIC_ACQUIRE);
+		t = now_ns();
+		while (__atomic_load_n(&sh->stamp, __ATOMIC_ACQUIRE) == s &&
+		       now_ns() - t < LOST_PERIOD + LOST_PERIOD / 2)
+			sleep_ns(NSEC_PER_MSEC);
+		if (__atomic_load_n(&sh->stamp, __ATOMIC_ACQUIRE) == s) {
+			ksft_print_msg("throttled, switched out and back: never ran again\n");
+			ret = KSFT_FAIL;
+		}
+	}
+	reap(pid);
+	return ret;
+}
+
+#define LEAK_RUNTIME	(9 * NSEC_PER_MSEC)
+#define LEAK_PERIOD	(10 * NSEC_PER_MSEC)
+
+/* Runs 0.2ms, sleeps 50ms. */
+static void sleeper(void)
+{
+	for (;;) {
+		uint64_t end = now_ns() + 200 * NSEC_PER_USEC;
+
+		while (now_ns() < end)
+			;
+		__atomic_fetch_add(&sh->sleeps, 1, __ATOMIC_RELEASE);
+		sleep_ns(50 * NSEC_PER_MSEC);
+	}
+}
+
+/*
+ * 90% of a CPU per round trip: a leak fills the root domain within about
+ * as many round trips as it has CPUs.
+ */
+static int test_asleep_round_trip(void)
+{
+	int i, trips = get_nprocs() * 10 / 9 + 3, ret = KSFT_PASS, err;
+	pid_t pid;
+	FILE *f;
+
+	f = fopen("/proc/sys/kernel/sched_rt_runtime_us", "r");
+	if (f) {
+		long rt = 0;
+
+		if (fscanf(f, "%ld", &rt) == 1 && rt < 0) {
+			fclose(f);
+			ksft_print_msg("no admission control: a leak cannot be seen\n");
+			return KSFT_SKIP;
+		}
+		fclose(f);
+	}
+	memset(sh, 0, sizeof(*sh));
+	pid = fork();
+	if (pid < 0) {
+		ksft_print_msg("fork: %s\n", strerror(errno));
+		return KSFT_FAIL;
+	}
+	if (!pid) {
+		if (set_deadline(0, LEAK_RUNTIME, LEAK_PERIOD))
+			_exit(KSFT_SKIP);
+		sleeper();
+	}
+	for (i = 0; i < trips; i++) {
+		uint64_t sleeps = __atomic_load_n(&sh->sleeps, __ATOMIC_ACQUIRE);
+		uint64_t t = now_ns();
+
+		while (__atomic_load_n(&sh->sleeps, __ATOMIC_ACQUIRE) == sleeps) {
+			if (now_ns() - t > NSEC_PER_SEC) {
+				int status;
+
+				if (waitpid(pid, &status, WNOHANG) == pid)
+					return gone(status);
+				ksft_print_msg("the task did not run within 1s\n");
+				reap(pid);
+				return KSFT_FAIL;
+			}
+			sleep_ns(NSEC_PER_MSEC);
+		}
+		/* Asleep, well past its 0-lag time. */
+		sleep_ns(5 * NSEC_PER_MSEC);
+		err = set_other(pid);
+		if (!err)
+			err = set_deadline(pid, LEAK_RUNTIME, LEAK_PERIOD);
+		if (err) {
+			ksft_print_msg("switch back refused after %d of %d round trips: %s\n",
+				       i, trips, strerror(-err));
+			ret = KSFT_FAIL;
+			break;
+		}
+	}
+	reap(pid);
+	return ret;
+}
+
+static void report(const char *name, int ret)
+{
+	if (ret == KSFT_PASS)
+		ksft_test_result_pass("%s\n", name);
+	else if (ret == KSFT_SKIP)
+		ksft_test_result_skip("%s\n", name);
+	else
+		ksft_test_result_fail("%s\n", name);
+}
+
+int main(void)
+{
+	sh = mmap(NULL, sizeof(*sh), PROT_READ | PROT_WRITE, MAP_SHARED | MAP_ANONYMOUS, -1, 0);
+	if (sh == MAP_FAILED)
+		ksft_exit_fail_msg("mmap: %s\n", strerror(errno));
+	ksft_print_header();
+	ksft_set_plan(2);
+	/* The first one first: the second fills the root domain where it leaks. */
+	report("throttled_round_trip", test_throttled_round_trip());
+	report("asleep_round_trip", test_asleep_round_trip());
+	ksft_finished();
+}
-- 
2.47.3

[PATCH 07/12] sched/deadline: Keep departing bandwidth across a root domain rebuild

[Mathieu Desnoyers]

A task that leaves SCHED_DEADLINE, or dies, before its 0-lag time keeps
its bandwidth in the total_bw of its root domain until that time, when
inactive_task_timer() removes it from the root domain of the CPU the
task is on (commit 387e31300b57 ("sched/deadline: Fix the update of the
total -deadline utilization")). Two things break that:

 1. a rebuild of the root domains' accounting,
    dl_rebuild_rd_accounting() on any change of the cpuset partitions
    and on CPU hotplug, clears every root domain and adds back the
    bandwidth of the deadline tasks it finds in the cpusets. A task out
    of the policy is not one, and a dead one is in no cpuset any more:
    its bandwidth is dropped, and the timer then removes it again, from
    whichever root domain its CPU is in by then. total_bw wraps around,
    and that root domain admits deadline tasks beyond its capacity
    until the next rebuild;
 2. a task out of the policy may move meanwhile, as any other task, to
    a CPU of another root domain, moved to another cpuset partition:
    the timer then removes the bandwidth from that root domain, which
    never had it, and leaves it for good in the one that has it.

Keep each departing task on a list, from its departure to its timer,
with a CPU of the root domain that holds its bandwidth: the CPU a dying
task runs on, and for one that leaves the policy, a CPU of its mask
(dl_task_root_domain_cpu()), since the CPU it last ran on may be of
another root domain, when it was moved asleep. A rebuild puts that
bandwidth back in the root domain of that CPU, and the timer removes it
from there.

dl_non_contending tells a task departed, its inactive timer armed and
that timer's handler yet to run; hrtimer_active() stays true for a
while after the handler returns, and would leave the task on the list
with nothing to take it off. A count of the rebuilds, which each task
records when its bandwidth is counted, settles the races with a death
and with a CPU going inactive: a rebuild that dropped the bandwidth
since leaves nothing to remove, as for a task that exits while a
rebuild runs, which neither the cpuset walk, skipping exiting tasks,
nor the list, if it is not dead yet when the list is put back, finds. A
switch back to SCHED_DEADLINE before the timer has sched_dl_overflow()
release the old bandwidth from the root domain that keeps it, the new
one reserved in the task's current root domain; a boost into
the deadline class by priority inheritance in that window, whose
switched_to_dl() cancels the timer, takes the task off the list, its
bandwidth removed when it leaves the class again, from the root domain
of its mask by then, as before. The list's lock nests inside the rq and
pi locks, and outside the root domains' dl_bw locks.

dl_cookie and dl_bw_visited() have no user outside deadline.c left:
make them static.

The selftest added by the next patch fails its three cases every time
without this change, and passes them with it. A standalone reproducer,
a task of 400ms every second that runs 380ms and then exits, switches
to SCHED_OTHER or moves, a partition root made or unmade before its
0-lag time, has a one-CPU partition root admit two tasks of 600ms every
second on v7.3, every time, and refuse the second with this change, in
36 runs out of 36. It was found by a cgroup selftest under development,
test_concurrency_deadline_domain, which failed about once in ten runs
when it followed a test whose deadline task had died just before.

Fixes: 387e31300b57 ("sched/deadline: Fix the update of the total -deadline utilization")
Fixes: f9a25f776d78 ("cpusets: Rebuild root domain deadline accounting information")
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
---
 include/linux/sched.h          |  14 +++
 include/linux/sched/deadline.h |   5 +-
 kernel/cgroup/cpuset.c         |  11 +-
 kernel/sched/deadline.c        | 222 ++++++++++++++++++++++++++++-----
 4 files changed, 208 insertions(+), 44 deletions(-)

diff --git a/include/linux/sched.h b/include/linux/sched.h
index 1c93da75226e..0633a73579db 100644
--- a/include/linux/sched.h
+++ b/include/linux/sched.h
@@ -734,6 +734,20 @@ struct sched_dl_entity {
 	 */
 	struct hrtimer			inactive_timer;
 
+	/*
+	 * A task that leaves SCHED_DEADLINE, or dies, before its "0-lag
+	 * time" keeps its bandwidth in its root domain until the inactive
+	 * timer removes it. @dl_departed_cpu is then a CPU of the root domain
+	 * that counts that bandwidth, and @dl_departed_node links it on the
+	 * list that a rebuild of the root domains' accounting puts that
+	 * bandwidth back from; -1 otherwise. @dl_bw_gen is the
+	 * rebuild that last counted the task's bandwidth: one since then
+	 * dropped it, and nothing is to be removed.
+	 */
+	struct list_head		dl_departed_node;
+	int				dl_departed_cpu;
+	unsigned int			dl_bw_gen;
+
 	/*
 	 * Bits for DL-server functionality. Also see the comment near
 	 * dl_server_update().
diff --git a/include/linux/sched/deadline.h b/include/linux/sched/deadline.h
index 273538200a44..bdf39ac1d43d 100644
--- a/include/linux/sched/deadline.h
+++ b/include/linux/sched/deadline.h
@@ -32,7 +32,7 @@ static inline bool dl_time_before(u64 a, u64 b)
 struct root_domain;
 extern void dl_add_task_root_domain(struct task_struct *p);
 extern void dl_clear_root_domain(struct root_domain *rd);
-extern void dl_clear_root_domain_cpu(int cpu);
+extern void dl_clear_root_domains(void);
 /*
  * Return whether moving DL task @p to @new_mask requires moving DL
  * bandwidth accounting between root domains. This helper is specific to
@@ -43,9 +43,6 @@ extern void dl_clear_root_domain_cpu(int cpu);
 extern bool dl_task_needs_bw_move(struct task_struct *p,
 				  const struct cpumask *new_mask);
 
-extern u64 dl_cookie;
-extern bool dl_bw_visited(int cpu, u64 cookie);
-
 static inline bool dl_server(struct sched_dl_entity *dl_se)
 {
 	return dl_se->dl_server;
diff --git a/kernel/cgroup/cpuset.c b/kernel/cgroup/cpuset.c
index 3219f927c35e..4159abfbbbb5 100644
--- a/kernel/cgroup/cpuset.c
+++ b/kernel/cgroup/cpuset.c
@@ -985,21 +985,14 @@ void dl_rebuild_rd_accounting(void)
 {
 	struct cpuset *cs = NULL;
 	struct cgroup_subsys_state *pos_css;
-	int cpu;
-	u64 cookie = ++dl_cookie;
 
 	lockdep_assert_cpuset_lock_held();
 	lockdep_assert_cpus_held();
 	lockdep_assert_held(&sched_domains_mutex);
 
-	rcu_read_lock();
-
-	for_each_possible_cpu(cpu) {
-		if (dl_bw_visited(cpu, cookie))
-			continue;
+	dl_clear_root_domains();
 
-		dl_clear_root_domain_cpu(cpu);
-	}
+	rcu_read_lock();
 
 	cpuset_for_each_descendant_pre(cs, pos_css, &top_cpuset) {
 
diff --git a/kernel/sched/deadline.c b/kernel/sched/deadline.c
index 3c57e5f5fc05..8ead9b050dfc 100644
--- a/kernel/sched/deadline.c
+++ b/kernel/sched/deadline.c
@@ -163,7 +163,13 @@ static inline unsigned long dl_bw_capacity(int i)
 	}
 }
 
-bool dl_bw_visited(int cpu, u64 cookie)
+/*
+ * Used for dl_bw check and update, used under sched_rt_handler()::mutex and
+ * sched_domains_mutex.
+ */
+static u64 dl_cookie;
+
+static bool dl_bw_visited(int cpu, u64 cookie)
 {
 	struct root_domain *rd = cpu_rq(cpu)->rd;
 
@@ -217,6 +223,88 @@ __dl_overflow(struct dl_bw *dl_b, unsigned long cap, u64 old_bw, u64 new_bw)
 	       cap_scale(dl_b->bw, cap) < dl_b->total_bw - old_bw + new_bw;
 }
 
+/*
+ * A task that leaves SCHED_DEADLINE, or dies, before its 0-lag time keeps
+ * its bandwidth in total_bw until then: the inactive timer removes it. A
+ * rebuild of the root domains' accounting meanwhile (dl_clear_root_domains()
+ * and dl_add_task_root_domain(), on any change of the partitions or CPU
+ * hotplug) finds no such task among the deadline tasks of the cpusets: it
+ * puts that bandwidth back from dl_departed_list, which holds them from
+ * their departure to their timer, in the root domain each left, found by
+ * its mask then (dl_task_root_domain_cpu()), or by the CPU it dies on: the
+ * CPU it last ran on may be of another one, when it was moved asleep. The
+ * task may run anywhere meanwhile, as another policy; its timer holds a
+ * reference to it.
+ *
+ * dl_bw_gen counts the rebuilds, and each task records the one that last
+ * counted its bandwidth. A rebuild that dropped it since then leaves
+ * nothing to remove: the CPU recorded was no longer active, or the task
+ * exited while the rebuild ran, which the cpuset walk skips, and was not
+ * dead yet when the list was put back. Both counts, and the list, are under
+ * dl_departed_lock, taken with interrupts disabled (under the task's rq
+ * lock or pi_lock, or by the rebuild) and before any dl_bw lock.
+ */
+static LIST_HEAD(dl_departed_list);
+static DEFINE_RAW_SPINLOCK(dl_departed_lock);
+static unsigned int dl_bw_gen;
+
+/*
+ * @p leaves SCHED_DEADLINE, or dies, its bandwidth kept for now in the root
+ * domain of @cpu. Under its rq lock.
+ */
+static void dl_task_depart(struct task_struct *p, int cpu)
+{
+	struct sched_dl_entity *dl_se = &p->dl;
+
+	lockdep_assert_irqs_disabled();
+	if (dl_se->dl_departed_cpu >= 0)
+		return;
+	guard(raw_spinlock)(&dl_departed_lock);
+	dl_se->dl_departed_cpu = cpu;
+	list_add(&dl_se->dl_departed_node, &dl_departed_list);
+}
+
+/*
+ * @p comes back to the deadline class, its bandwidth kept as a deadline
+ * task's again. Under its rq lock.
+ */
+static void dl_task_undepart(struct task_struct *p)
+{
+	struct sched_dl_entity *dl_se = &p->dl;
+
+	lockdep_assert_irqs_disabled();
+	guard(raw_spinlock)(&dl_departed_lock);
+	dl_se->dl_departed_cpu = -1;
+	list_del(&dl_se->dl_departed_node);
+}
+
+/*
+ * Remove @p's bandwidth from the root domain that counts it: that of the
+ * CPU recorded when it departed, else that of @cpu. Nothing to remove
+ * when a rebuild of the accounting has dropped it; and no rebuild running
+ * counts it again. Under @p's rq lock.
+ */
+static void dl_task_release_bw(struct task_struct *p, int cpu)
+{
+	struct sched_dl_entity *dl_se = &p->dl;
+	struct dl_bw *dl_b;
+
+	lockdep_assert_irqs_disabled();
+	guard(raw_spinlock)(&dl_departed_lock);
+	if (dl_se->dl_departed_cpu >= 0) {
+		cpu = dl_se->dl_departed_cpu;
+		dl_se->dl_departed_cpu = -1;
+		list_del(&dl_se->dl_departed_node);
+	}
+	if (dl_se->dl_bw_gen == dl_bw_gen) {
+		dl_b = dl_bw_of(cpu);
+		raw_spin_lock(&dl_b->lock);
+		__dl_sub(dl_b, dl_se->dl_bw, dl_bw_cpus(cpu));
+		raw_spin_unlock(&dl_b->lock);
+	}
+	dl_se->dl_bw_gen = dl_bw_gen;
+}
+
 static inline
 void __add_running_bw(u64 dl_bw, struct dl_rq *dl_rq)
 {
@@ -449,13 +537,9 @@ static void task_non_contending(struct sched_dl_entity *dl_se, bool dl_task)
 				sub_running_bw(dl_se, dl_rq);
 
 			if (!dl_task || READ_ONCE(p->__state) == TASK_DEAD) {
-				struct dl_bw *dl_b = dl_bw_of(task_cpu(p));
-
 				if (READ_ONCE(p->__state) == TASK_DEAD)
 					sub_rq_bw(dl_se, &rq->dl);
-				raw_spin_lock(&dl_b->lock);
-				__dl_sub(dl_b, dl_se->dl_bw, dl_bw_cpus(task_cpu(p)));
-				raw_spin_unlock(&dl_b->lock);
+				dl_task_release_bw(p, task_cpu(p));
 				__dl_clear_params(dl_se);
 			}
 		}
@@ -464,8 +548,18 @@ static void task_non_contending(struct sched_dl_entity *dl_se, bool dl_task)
 	}
 
 	dl_se->dl_non_contending = 1;
-	if (!dl_server(dl_se))
-		get_task_struct(dl_task_of(dl_se));
+	if (!dl_server(dl_se)) {
+		struct task_struct *p = dl_task_of(dl_se);
+
+		get_task_struct(p);
+		/*
+		 * Dying: its bandwidth is in the root domain of the CPU it
+		 * runs on. switched_from_dl() records one that leaves
+		 * SCHED_DEADLINE.
+		 */
+		if (READ_ONCE(p->__state) == TASK_DEAD)
+			dl_task_depart(p, task_cpu(p));
+	}
 
 	hrtimer_start(timer, ns_to_ktime(zerolag_time), HRTIMER_MODE_REL_HARD);
 }
@@ -2185,17 +2279,13 @@ static enum hrtimer_restart inactive_task_timer(struct hrtimer *timer)
 		goto no_task;
 
 	if (!dl_task(p) || READ_ONCE(p->__state) == TASK_DEAD) {
-		struct dl_bw *dl_b = dl_bw_of(task_cpu(p));
-
 		if (READ_ONCE(p->__state) == TASK_DEAD && dl_se->dl_non_contending) {
 			sub_running_bw(&p->dl, dl_rq_of_se(&p->dl));
 			sub_rq_bw(&p->dl, dl_rq_of_se(&p->dl));
 			dl_se->dl_non_contending = 0;
 		}
 
-		raw_spin_lock(&dl_b->lock);
-		__dl_sub(dl_b, p->dl.dl_bw, dl_bw_cpus(task_cpu(p)));
-		raw_spin_unlock(&dl_b->lock);
+		dl_task_release_bw(p, task_cpu(p));
 		__dl_clear_params(dl_se);
 
 		goto unlock;
@@ -3479,12 +3569,33 @@ void dl_add_task_root_domain(struct task_struct *p)
 	dl_get_task_effective_cpus(p, msk);
 	cpu = cpumask_first_and(cpu_active_mask, msk);
 	BUG_ON(cpu >= nr_cpu_ids);
+
+	raw_spin_lock(&dl_departed_lock);
+	/*
+	 * Counted already by this rebuild: put back by
+	 * dl_clear_root_domains() as a departed task, which priority
+	 * inheritance boosted into the class since, or its bandwidth
+	 * gone since (dl_task_release_bw()), as that of one that died
+	 * after the walk found it. One that died since with its 0-lag
+	 * time ahead goes back to the root domain of the CPU recorded
+	 * (dl_task_depart()), if active.
+	 */
+	if (p->dl.dl_bw_gen == dl_bw_gen)
+		goto unlock;
+	if (p->dl.dl_departed_cpu >= 0) {
+		cpu = p->dl.dl_departed_cpu;
+		if (!cpu_active(cpu))
+			goto unlock;
+	}
 	rq = cpu_rq(cpu);
 	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));
 	raw_spin_unlock(&dl_b->lock);
+	p->dl.dl_bw_gen = dl_bw_gen;
+unlock:
+	raw_spin_unlock(&dl_departed_lock);
 	raw_spin_unlock_irqrestore(&p->pi_lock, rf.flags);
 }
 
@@ -3542,9 +3653,37 @@ void dl_clear_root_domain(struct root_domain *rd)
 		dl_server_add_bw(rd, i);
 }
 
-void dl_clear_root_domain_cpu(int cpu)
+/*
+ * Clear every root domain ahead of a rebuild of their accounting, which
+ * dl_add_task_root_domain() then fills with the deadline tasks of the
+ * cpusets: put back their servers, and the bandwidth of the tasks that
+ * left SCHED_DEADLINE, or died, before their 0-lag time, which no cpuset
+ * holds as a deadline task, in the root domain of the CPU recorded for
+ * each; dropped if it is no longer active.
+ */
+void dl_clear_root_domains(void)
 {
-	dl_clear_root_domain(cpu_rq(cpu)->rd);
+	struct sched_dl_entity *dl_se;
+	u64 cookie = ++dl_cookie;
+	struct dl_bw *dl_b;
+	int cpu;
+
+	guard(raw_spinlock_irqsave)(&dl_departed_lock);
+	dl_bw_gen++;
+	for_each_possible_cpu(cpu) {
+		if (!dl_bw_visited(cpu, cookie))
+			dl_clear_root_domain(cpu_rq(cpu)->rd);
+	}
+	list_for_each_entry(dl_se, &dl_departed_list, dl_departed_node) {
+		cpu = dl_se->dl_departed_cpu;
+		if (!cpu_active(cpu))
+			continue;
+		dl_b = dl_bw_of(cpu);
+		raw_spin_lock(&dl_b->lock);
+		__dl_add(dl_b, dl_se->dl_bw, dl_bw_cpus(cpu));
+		raw_spin_unlock(&dl_b->lock);
+		dl_se->dl_bw_gen = dl_bw_gen;
+	}
 }
 
 static void switched_from_dl(struct rq *rq, struct task_struct *p)
@@ -3578,7 +3717,7 @@ static void switched_from_dl(struct rq *rq, struct task_struct *p)
 			 * or sub_rq_bw (below) will complain.
 			 *
 			 * inactive_task_timer() will find !dl_task(p) and
-			 * release total_bw via __dl_sub().
+			 * release total_bw (dl_task_release_bw()).
 			 */
 			sub_running_bw(&p->dl, &rq->dl);
 		} else if (p->dl.dl_runtime && !dl_entity_is_special(&p->dl)) {
@@ -3594,12 +3733,7 @@ static void switched_from_dl(struct rq *rq, struct task_struct *p)
 			 * nor for a special one: neither has bandwidth in
 			 * total_bw.
 			 */
-			unsigned int cpu = dl_task_root_domain_cpu(p);
-			struct dl_bw *dl_b = &cpu_rq(cpu)->rd->dl_bw;
-
-			raw_spin_lock(&dl_b->lock);
-			__dl_sub(dl_b, p->dl.dl_bw, dl_bw_cpus(cpu));
-			raw_spin_unlock(&dl_b->lock);
+			dl_task_release_bw(p, dl_task_root_domain_cpu(p));
 			released = true;
 		}
 		sub_rq_bw(&p->dl, &rq->dl);
@@ -3620,9 +3754,19 @@ static void switched_from_dl(struct rq *rq, struct task_struct *p)
 	 * We cannot use inactive_task_timer() to invoke sub_running_bw()
 	 * at the 0-lag time, because the task could have been migrated
 	 * while SCHED_OTHER in the meanwhile.
+	 *
+	 * Nor can it take the task's bandwidth from the root domain of the
+	 * CPU the task is on by then, and a rebuild of the root domains
+	 * meanwhile would not find it among the deadline tasks: record a
+	 * CPU of the root domain that keeps that bandwidth until the
+	 * inactive timer removes it (dl_task_depart()). dl_non_contending
+	 * tells that timer armed, its handler yet to run; hrtimer_active()
+	 * stays true for a while after that handler returns.
 	 */
-	if (p->dl.dl_non_contending)
+	if (p->dl.dl_non_contending) {
 		p->dl.dl_non_contending = 0;
+		dl_task_depart(p, dl_task_root_domain_cpu(p));
+	}
 
 	/*
 	 * Since this might be the only -deadline task on the rq,
@@ -3642,6 +3786,16 @@ static void switched_from_dl(struct rq *rq, struct task_struct *p)
 static void switched_to_dl(struct rq *rq, struct task_struct *p)
 {
 	cancel_inactive_timer(&p->dl);
+	/*
+	 * Boosted back into the class before its 0-lag time (a policy change
+	 * released that bandwidth in sched_dl_overflow()): the inactive
+	 * timer will not remove it, but its leaving the class again. That
+	 * forgets the CPU recorded: moved to another root domain meanwhile,
+	 * the task then removes the bandwidth from that one, as it did
+	 * before departures were recorded.
+	 */
+	if (p->dl.dl_departed_cpu >= 0)
+		dl_task_undepart(p);
 
 	/*
 	 * In case a task is setscheduled to SCHED_DEADLINE we need to keep
@@ -3756,12 +3910,6 @@ DEFINE_SCHED_CLASS(dl) = {
 #endif
 };
 
-/*
- * Used for dl_bw check and update, used under sched_rt_handler()::mutex and
- * sched_domains_mutex.
- */
-u64 dl_cookie;
-
 int sched_dl_global_validate(void)
 {
 	u64 runtime = global_rt_runtime();
@@ -3882,8 +4030,6 @@ int sched_dl_overflow(struct task_struct *p, int policy,
 
 	if (dl_policy(policy) && !task_has_dl_policy(p) &&
 	    !__dl_overflow(dl_b, cap, 0, new_bw)) {
-		if (hrtimer_active(&p->dl.inactive_timer))
-			__dl_sub(dl_b, p->dl.dl_bw, cpus);
 		__dl_add(dl_b, new_bw, cpus);
 		err = 0;
 	} else if (dl_policy(policy) && task_has_dl_policy(p) &&
@@ -3909,6 +4055,19 @@ int sched_dl_overflow(struct task_struct *p, int policy,
 	}
 	raw_spin_unlock(&dl_b->lock);
 
+	/*
+	 * Back before its 0-lag time, the task still has the bandwidth it
+	 * left with, which the new one replaces: removed from the root
+	 * domain that keeps it (dl_task_release_bw()). A rebuild cannot
+	 * run meanwhile: the caller holds cpuset_mutex.
+	 */
+	if (!err && dl_policy(policy) && !task_has_dl_policy(p)) {
+		lockdep_assert_cpuset_lock_held();
+		if (p->dl.dl_departed_cpu >= 0)
+			dl_task_release_bw(p, -1);
+		p->dl.dl_bw_gen = dl_bw_gen;
+	}
+
 	return err;
 }
 
@@ -4044,6 +4203,7 @@ void init_dl_entity(struct sched_dl_entity *dl_se)
 	init_dl_task_timer(dl_se);
 	init_dl_inactive_task_timer(dl_se);
 	__dl_clear_params(dl_se);
+	dl_se->dl_departed_cpu = -1;
 }
 
 bool dl_param_changed(struct task_struct *p, const struct sched_attr *attr)
-- 
2.47.3

[PATCH 08/12] selftests/sched: Test SCHED_DEADLINE bandwidth across a root domain rebuild

[Mathieu Desnoyers]

Add deadline_rebuild_test, for the previous patch. In each case a task
of 400ms every second runs 380ms, then leaves SCHED_DEADLINE, its 0-lag
time some 570ms ahead; past that time, the one-CPU partition root P must
admit one task of 600ms every second and refuse a second with EBUSY:

 - dies_before_rebuild: the task, in P, exits, and a second partition
   root is made meanwhile, which rebuilds the accounting of every root
   domain;
 - switched_out_before_rebuild: the same, the task switched to
   SCHED_OTHER and asleep in P;
 - moved_after_switch_out: the task, outside P, switches to SCHED_OTHER,
   moves into P and dies there.

A kernel that removes the bandwidth from P's root domain when a rebuild
dropped it, or when P never had it, admits both. Skipped without root,
the cgroup v2 cpuset controller, deadline admission control (that is,
with sched_rt_runtime_us at -1) or 3 CPUs.

In 8 VMs of 8 vCPUs each, three runs in each, v7.4-rc1 with the four
deadline fixes of sched/urgent fails the three cases, and so does it
with the previous patches but the last; with it, the three pass; every
time. v7.3 fails them as well (2 VMs, three runs in each).

Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
---
 tools/testing/selftests/sched/.gitignore      |   1 +
 tools/testing/selftests/sched/Makefile        |   2 +-
 .../selftests/sched/deadline_rebuild_test.c   | 462 ++++++++++++++++++
 3 files changed, 464 insertions(+), 1 deletion(-)
 create mode 100644 tools/testing/selftests/sched/deadline_rebuild_test.c

diff --git a/tools/testing/selftests/sched/.gitignore b/tools/testing/selftests/sched/.gitignore
index d97f40c21ab5..fc7ab1ddbbe7 100644
--- a/tools/testing/selftests/sched/.gitignore
+++ b/tools/testing/selftests/sched/.gitignore
@@ -1,2 +1,3 @@
 cs_prctl_test
 deadline_switch_test
+deadline_rebuild_test
diff --git a/tools/testing/selftests/sched/Makefile b/tools/testing/selftests/sched/Makefile
index ae9421eabf15..728e046b463c 100644
--- a/tools/testing/selftests/sched/Makefile
+++ b/tools/testing/selftests/sched/Makefile
@@ -10,6 +10,6 @@ LDLIBS += -lpthread
 
 TEST_GEN_FILES := cs_prctl_test
 TEST_PROGS := cs_prctl_test
-TEST_GEN_PROGS := deadline_switch_test
+TEST_GEN_PROGS := deadline_switch_test deadline_rebuild_test
 
 include ../lib.mk
diff --git a/tools/testing/selftests/sched/deadline_rebuild_test.c b/tools/testing/selftests/sched/deadline_rebuild_test.c
new file mode 100644
index 000000000000..d1f948f5de77
--- /dev/null
+++ b/tools/testing/selftests/sched/deadline_rebuild_test.c
@@ -0,0 +1,462 @@
+// SPDX-License-Identifier: GPL-2.0
+/*
+ * The bandwidth of a SCHED_DEADLINE task that leaves the policy, or dies,
+ * before its 0-lag time stays allocated in its root domain until the
+ * inactive timer removes it. It must be removed once, from the root
+ * domain that keeps it:
+ *
+ *  - dies: a task of a one-CPU partition root P dies, and a second
+ *    partition root Q is made meanwhile, which rebuilds the accounting
+ *    of every root domain;
+ *  - switched out: the same, the task switched to SCHED_OTHER;
+ *  - moved: a task outside P switched to SCHED_OTHER, then moved into P
+ *    before its 0-lag time.
+ *
+ * Then P, past the timer, must admit one task of 600ms every second and
+ * refuse a second one (EBUSY). A kernel that removes the bandwidth from
+ * P's root domain when the rebuild dropped it, or when P never held it,
+ * leaves it negative: it admits both.
+ *
+ * Needs root, the cgroup v2 cpuset controller, deadline admission
+ * control and 3 CPUs.
+ */
+#define _GNU_SOURCE
+#include <errno.h>
+#include <fcntl.h>
+#include <limits.h>
+#include <sched.h>
+#include <signal.h>
+#include <stdint.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+#include <sys/stat.h>
+#include <sys/syscall.h>
+#include <sys/sysinfo.h>
+#include <sys/wait.h>
+#include <time.h>
+#include <unistd.h>
+
+#include "../kselftest.h"
+
+#ifndef SCHED_DEADLINE
+#define SCHED_DEADLINE	6
+#endif
+
+#define NSEC_PER_MSEC	1000000ULL
+#define NSEC_PER_SEC	1000000000ULL
+
+struct dl_attr {
+	uint32_t size;
+	uint32_t sched_policy;
+	uint64_t sched_flags;
+	int32_t sched_nice;
+	uint32_t sched_priority;
+	uint64_t sched_runtime;
+	uint64_t sched_deadline;
+	uint64_t sched_period;
+};
+
+static char root[PATH_MAX], cg_p[PATH_MAX], cg_q[PATH_MAX];
+static int ncpus;
+
+static int set_deadline(pid_t pid, uint64_t runtime)
+{
+	struct dl_attr attr = {
+		.size = sizeof(attr),
+		.sched_policy = SCHED_DEADLINE,
+		.sched_runtime = runtime,
+		.sched_deadline = NSEC_PER_SEC,
+		.sched_period = NSEC_PER_SEC,
+	};
+
+	return syscall(__NR_sched_setattr, pid, &attr, 0) ? -errno : 0;
+}
+
+static int set_other(pid_t pid)
+{
+	struct sched_param sp = { .sched_priority = 0 };
+
+	return sched_setscheduler(pid, SCHED_OTHER, &sp) ? -errno : 0;
+}
+
+/* These clocks cannot fail: both are always supported, the pointer is valid. */
+static uint64_t now_ns(void)
+{
+	struct timespec ts;
+
+	clock_gettime(CLOCK_MONOTONIC, &ts);
+	return ts.tv_sec * NSEC_PER_SEC + ts.tv_nsec;
+}
+
+static void sleep_ns(uint64_t ns)
+{
+	struct timespec ts = { .tv_sec = ns / NSEC_PER_SEC, .tv_nsec = ns % NSEC_PER_SEC };
+
+	while (nanosleep(&ts, &ts) && errno == EINTR)
+		;
+}
+
+static void reap(pid_t pid)
+{
+	int status;
+
+	if (pid <= 0)
+		return;
+	if (kill(pid, SIGKILL) && errno != ESRCH)
+		ksft_print_msg("kill %d: %s\n", pid, strerror(errno));
+	set_other(pid);			/* gone already: nothing to switch */
+	while (waitpid(pid, &status, 0) != pid) {
+		if (errno == EINTR)
+			continue;
+		ksft_print_msg("waitpid %d: %s\n", pid, strerror(errno));
+		break;
+	}
+}
+
+static int write_file(const char *dir, const char *name, const char *val)
+{
+	char path[PATH_MAX];
+	int fd, err = 0;
+	ssize_t n;
+
+	if (snprintf(path, sizeof(path), "%s/%s", dir, name) >= (int)sizeof(path))
+		return -ENAMETOOLONG;
+	fd = open(path, O_WRONLY);
+	if (fd < 0)
+		return -errno;
+	n = write(fd, val, strlen(val));
+	if (n < 0)
+		err = -errno;
+	else if (n != (ssize_t)strlen(val))
+		err = -EIO;
+	if (close(fd) && !err)
+		err = -errno;
+	return err;
+}
+
+static int read_file(const char *path, char *buf, size_t len)
+{
+	int fd = open(path, O_RDONLY);
+	ssize_t n;
+
+	if (fd < 0)
+		return -1;
+	do {
+		n = read(fd, buf, len - 1);
+	} while (n < 0 && errno == EINTR);
+	close(fd);
+	if (n < 0)
+		return -1;
+	buf[n] = 0;
+	return 0;
+}
+
+static int enter(const char *cg, pid_t pid)
+{
+	char buf[16];
+
+	snprintf(buf, sizeof(buf), "%d", pid);
+	return write_file(cg, "cgroup.procs", buf);
+}
+
+/* A partition root of the one CPU @cpu, or -1. */
+static int make_partition(const char *cg, int cpu)
+{
+	char path[PATH_MAX], buf[32];
+
+	if (mkdir(cg, 0755) && errno != EEXIST)
+		return -1;
+	snprintf(buf, sizeof(buf), "%d", cpu);
+	if (write_file(cg, "cpuset.cpus", buf) || write_file(cg, "cpuset.cpus.partition", "root"))
+		return -1;
+	snprintf(path, sizeof(path), "%s/cpuset.cpus.partition", cg);
+	if (read_file(path, buf, sizeof(buf)) || strcmp(buf, "root\n"))
+		return -1;
+	return 0;
+}
+
+static void remove_partition(const char *cg)
+{
+	int err = write_file(cg, "cpuset.cpus.partition", "member");
+	uint64_t end;
+
+	if (err && err != -ENOENT)
+		ksft_print_msg("%s back to a member: %s\n", cg, strerror(-err));
+	/* A cgroup whose last task just died takes a moment to empty. */
+	end = now_ns() + NSEC_PER_SEC;
+	while (rmdir(cg)) {
+		if (errno == ENOENT)
+			return;
+		if (errno != EBUSY || now_ns() > end) {
+			ksft_print_msg("rmdir %s: %s\n", cg, strerror(errno));
+			return;
+		}
+		sleep_ns(10 * NSEC_PER_MSEC);
+	}
+}
+
+/* Both clocks are always supported and the pointer is valid: no error. */
+static uint64_t cpu_time_ns(void)
+{
+	struct timespec ts;
+
+	clock_gettime(CLOCK_THREAD_CPUTIME_ID, &ts);
+	return ts.tv_sec * NSEC_PER_SEC + ts.tv_nsec;
+}
+
+enum depart { DIES, SWITCHED_OUT };
+
+/*
+ * In @cg if given, made SCHED_DEADLINE at 400ms every second, the child
+ * runs 380ms of it, then dies or switches to SCHED_OTHER and sleeps:
+ * its 0-lag time is then some 570ms ahead. The pipe @fd gets a byte once
+ * it is out of the policy; for one that dies, its exit status tells. The
+ * caller keeps the read end alone.
+ */
+static pid_t departing(const char *cg, enum depart how, int fd[2])
+{
+	pid_t pid = fork();
+
+	if (pid < 0)
+		ksft_print_msg("fork: %s\n", strerror(errno));
+	if (!pid) {
+		uint64_t t0;
+
+		close(fd[0]);
+		if (cg && enter(cg, getpid()))
+			_exit(2);
+		if (set_deadline(0, 400 * NSEC_PER_MSEC))
+			_exit(3);
+		t0 = cpu_time_ns();
+		while (cpu_time_ns() - t0 < 380 * NSEC_PER_MSEC)
+			;
+		if (how == DIES)
+			_exit(0);
+		if (set_other(0) || write(fd[1], "x", 1) != 1)
+			_exit(4);
+		for (;;)
+			pause();
+	}
+	close(fd[1]);
+	fd[1] = -1;
+	return pid;
+}
+
+/* Wait until the child is out of SCHED_DEADLINE, dead or switched out. */
+static int departed(pid_t *pid, enum depart how, int fd)
+{
+	int status;
+	char c;
+
+	if (*pid < 0)
+		return -1;
+	/* No byte: the child failed, and its exit status tells. */
+	if (how == SWITCHED_OUT) {
+		ssize_t n;
+
+		do {
+			n = read(fd, &c, 1);
+		} while (n < 0 && errno == EINTR);
+		if (n == 1)
+			return 0;
+	}
+	if (waitpid(*pid, &status, 0) != *pid)
+		return -1;
+	*pid = -1;
+	return WIFEXITED(status) ? WEXITSTATUS(status) : -1;
+}
+
+/*
+ * A child that enters @cg and sleeps there, or -1. It moves itself, so
+ * that it last ran on a CPU of @cg, and says so once it is there.
+ */
+static pid_t sleeper(const char *cg)
+{
+	int fd[2];
+	pid_t pid;
+	char c;
+
+	if (pipe(fd))
+		return -1;
+	pid = fork();
+	if (pid < 0)
+		ksft_print_msg("fork: %s\n", strerror(errno));
+	if (!pid) {
+		close(fd[0]);
+		if (enter(cg, getpid()) || write(fd[1], "x", 1) != 1)
+			_exit(1);
+		for (;;)
+			pause();
+	}
+	close(fd[1]);
+	if (pid > 0 && read(fd[0], &c, 1) != 1) {
+		reap(pid);
+		pid = -1;
+	}
+	close(fd[0]);
+	return pid;
+}
+
+/* P, past every timer, admits one task of 600ms every second, not two. */
+static int check_p(void)
+{
+	pid_t a = sleeper(cg_p), b = sleeper(cg_p);
+	int ret = KSFT_FAIL, e1, e2;
+
+	if (a < 0 || b < 0) {
+		ksft_print_msg("no task could enter P\n");
+		goto out;
+	}
+	e1 = set_deadline(a, 600 * NSEC_PER_MSEC);
+	e2 = set_deadline(b, 600 * NSEC_PER_MSEC);
+	if (e1)
+		ksft_print_msg("a first task refused in P: %s\n", strerror(-e1));
+	else if (!e2)
+		ksft_print_msg("1.2 CPUs of deadline tasks admitted in a partition of one CPU\n");
+	else if (e2 != -EBUSY)
+		ksft_print_msg("the second task refused with %s, not EBUSY\n", strerror(-e2));
+	else
+		ret = KSFT_PASS;
+out:
+	reap(a);
+	reap(b);
+	return ret;
+}
+
+/* A task of P leaves, and Q is made before its 0-lag time. */
+static int test_rebuild(enum depart how)
+{
+	int ret = KSFT_FAIL, fd[2], err;
+	pid_t pid = -1;
+
+	if (pipe(fd))
+		return KSFT_FAIL;
+	if (make_partition(cg_p, ncpus - 1)) {
+		ksft_print_msg("no partition root on CPU %d\n", ncpus - 1);
+		ret = KSFT_SKIP;
+		goto out;
+	}
+	pid = departing(cg_p, how, fd);
+	err = departed(&pid, how, fd[0]);
+	if (err) {
+		ksft_print_msg("the deadline task failed (%d)\n", err);
+		goto out;
+	}
+	if (make_partition(cg_q, ncpus - 2)) {
+		ksft_print_msg("no partition root on CPU %d\n", ncpus - 2);
+		ret = KSFT_SKIP;
+		goto out;
+	}
+	/* Past the 0-lag time; one switched out sleeps on in P. */
+	sleep_ns(1500 * NSEC_PER_MSEC);
+	ret = check_p();
+out:
+	reap(pid);
+	remove_partition(cg_q);
+	remove_partition(cg_p);
+	close(fd[0]);
+	if (fd[1] >= 0)
+		close(fd[1]);
+	return ret;
+}
+
+/* A task outside P switches out, then moves into P before its 0-lag time. */
+static int test_move(void)
+{
+	int ret = KSFT_FAIL, fd[2], err;
+	pid_t pid = -1;
+
+	if (pipe(fd))
+		return KSFT_FAIL;
+	if (make_partition(cg_p, ncpus - 1)) {
+		ksft_print_msg("no partition root on CPU %d\n", ncpus - 1);
+		ret = KSFT_SKIP;
+		goto out;
+	}
+	pid = departing(NULL, SWITCHED_OUT, fd);
+	err = departed(&pid, SWITCHED_OUT, fd[0]);
+	if (err) {
+		ksft_print_msg("the deadline task failed (%d)\n", err);
+		goto out;
+	}
+	if (enter(cg_p, pid)) {
+		ksft_print_msg("the task cannot move into P\n");
+		goto out;
+	}
+	/* It wakes up, and dies, on P's CPU, before its 0-lag time. */
+	reap(pid);
+	pid = -1;
+	sleep_ns(1500 * NSEC_PER_MSEC);
+	ret = check_p();
+out:
+	reap(pid);
+	remove_partition(cg_p);
+	close(fd[0]);
+	if (fd[1] >= 0)
+		close(fd[1]);
+	return ret;
+}
+
+static int find_cgroup2(void)
+{
+	char line[PATH_MAX + 64], dev[64], dir[PATH_MAX], type[64];
+	FILE *f = fopen("/proc/self/mounts", "r");
+	int found = 0;
+
+	while (f && !found && fgets(line, sizeof(line), f)) {
+		if (sscanf(line, "%63s %4095s %63s", dev, dir, type) == 3 &&
+		    !strcmp(type, "cgroup2")) {
+			snprintf(root, sizeof(root), "%s", dir);
+			found = 1;
+		}
+	}
+	if (f)
+		fclose(f);
+	return found ? 0 : -1;
+}
+
+static void report(const char *name, int ret)
+{
+	if (ret == KSFT_PASS)
+		ksft_test_result_pass("%s\n", name);
+	else if (ret == KSFT_SKIP)
+		ksft_test_result_skip("%s\n", name);
+	else
+		ksft_test_result_fail("%s\n", name);
+}
+
+int main(void)
+{
+	char buf[256], path[PATH_MAX + 32];
+	int added;
+
+	ksft_print_header();
+	if (geteuid())
+		ksft_exit_skip("needs root\n");
+	ncpus = get_nprocs();
+	if (ncpus < 3)
+		ksft_exit_skip("needs 3 CPUs\n");
+	if (read_file("/proc/sys/kernel/sched_rt_runtime_us", buf, sizeof(buf)) || atol(buf) < 0)
+		ksft_exit_skip("no deadline admission control\n");
+	if (find_cgroup2())
+		ksft_exit_skip("cgroup v2 is not mounted\n");
+	/* The cpuset controller for the root's children while the test runs. */
+	snprintf(path, sizeof(path), "%s/cgroup.subtree_control", root);
+	if (read_file(path, buf, sizeof(buf)))
+		ksft_exit_skip("no cgroup.subtree_control\n");
+	added = !strstr(buf, "cpuset");
+	if (added && write_file(root, "cgroup.subtree_control", "+cpuset"))
+		ksft_exit_skip("no cpuset controller\n");
+	if (snprintf(cg_p, sizeof(cg_p), "%s/deadline_rebuild_p", root) >= (int)sizeof(cg_p) ||
+	    snprintf(cg_q, sizeof(cg_q), "%s/deadline_rebuild_q", root) >= (int)sizeof(cg_q))
+		ksft_exit_skip("cgroup v2 mount path too long\n");
+
+	ksft_set_plan(3);
+	report("dies_before_rebuild", test_rebuild(DIES));
+	report("switched_out_before_rebuild", test_rebuild(SWITCHED_OUT));
+	report("moved_after_switch_out", test_move());
+	if (added && write_file(root, "cgroup.subtree_control", "-cpuset"))
+		ksft_print_msg("the cpuset controller stays enabled\n");
+	ksft_finished();
+}
-- 
2.47.3

[PATCH 09/12] sched/deadline: Do not take a waking task's bandwidth off a runqueue it left

[Mathieu Desnoyers]

A deadline task that wakes on another CPU has its bandwidth taken off
the runqueue it slept on by migrate_task_rq_dl(), from set_task_cpu(),
and charged to the one it wakes on by the enqueue that follows. That
enqueue can be left to the target CPU through the wake list, and
try_to_wake_up() returns before it runs: the task's task_cpu() is then
the CPU it wakes on while its bandwidth is on no runqueue at all.

sched_setattr() of that task meanwhile finds it off the runqueues, and
dl_change_utilization() takes its old bandwidth off the runqueue of
task_cpu(), which never held it. this_bw of that CPU underflows, which
costs every other task and the fair server there their own, for good.
switched_from_dl() leaves the class through the same hole.

Reaching it needs a deadline task whose wakeup migrates, which asks for
more than one CPU in its root domain and for them to be taken. It is
easier to reach with CONFIG_SCHED_PROXY_EXEC=y, where a task blocked on
a mutex is migrated to the CPU of its owner and wakes back on its own.

In 8 VMs of 8 vCPUs, a task of 10ms every 100ms that sleeps and wakes in
a partition root of two CPUs, both taken by deadline tasks of an earlier
deadline, its runtime changed between 10ms and 20ms from a CPU outside,
warns in all 8 within a second, and the warnings spread to the idle
task's accounting of both CPUs:

  WARNING: kernel/sched/deadline.c:352 at dl_rq_change_utilization+0x71/0x2e0, CPU#0: wake_race/109
   __sub_rq_bw(): this_bw underflow
  WARNING: kernel/sched/deadline.c:316 at task_contending+0x244/0x260, CPU#6: swapper/6/0
   __add_running_bw(): running_bw overflow

Record that window in the entity, as dl_bw_offrq, and leave the
runqueue alone while it is set: the enqueue to come charges the CPU the
task wakes on, with the new bandwidth, which __setparam_dl() sets right
after sched_dl_overflow(). add_rq_bw() clears it, so every path that
charges a runqueue does. The 8 VMs above warn no more. deadline_bw_test,
added later in this series, has params_waking for this: without this
change it fails on every one of those VMs, and random_mix on one of
three.

Fixes: 8fd27231c330 ("sched/deadline: Track the "total rq utilization" too")
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
---
 include/linux/sched.h   |  1 +
 kernel/sched/deadline.c | 20 +++++++++++++++++++-
 2 files changed, 20 insertions(+), 1 deletion(-)

diff --git a/include/linux/sched.h b/include/linux/sched.h
index 0633a73579db..8ffc076a485f 100644
--- a/include/linux/sched.h
+++ b/include/linux/sched.h
@@ -718,6 +718,7 @@ struct sched_dl_entity {
 	unsigned int			dl_defer_running  : 1;
 	unsigned int			dl_defer_idle     : 1;
 	unsigned int			dl_bw_attached    : 1;
+	unsigned int			dl_bw_offrq       : 1;
 
 	/*
 	 * Bandwidth enforcement timer. Each -deadline task has its
diff --git a/kernel/sched/deadline.c b/kernel/sched/deadline.c
index 8ead9b050dfc..a8906cf96640 100644
--- a/kernel/sched/deadline.c
+++ b/kernel/sched/deadline.c
@@ -358,6 +358,7 @@ void __sub_rq_bw(u64 dl_bw, struct dl_rq *dl_rq)
 static inline
 void add_rq_bw(struct sched_dl_entity *dl_se, struct dl_rq *dl_rq)
 {
+	dl_se->dl_bw_offrq = 0;
 	if (!dl_entity_is_special(dl_se))
 		__add_rq_bw(dl_se->dl_bw, dl_rq);
 }
@@ -435,6 +436,14 @@ static void dl_change_utilization(struct task_struct *p, u64 new_bw)
 	if (task_on_rq_queued(p))
 		return;
 
+	/*
+	 * Waking up on another CPU, the task has its bandwidth on no
+	 * runqueue: the enqueue to come charges the new one, with the new
+	 * parameters, which __setparam_dl() sets right after this.
+	 */
+	if (p->dl.dl_bw_offrq)
+		return;
+
 	dl_rq_change_utilization(task_rq(p), &p->dl, new_bw);
 }
 
@@ -2785,6 +2794,12 @@ static void migrate_task_rq_dl(struct task_struct *p, int new_cpu __maybe_unused
 		cancel_inactive_timer(&p->dl);
 	}
 	sub_rq_bw(&p->dl, &rq->dl);
+	/*
+	 * Until the enqueue on the CPU it wakes on charges it there, which
+	 * add_rq_bw() tells of, this bandwidth is on no runqueue: the rq of
+	 * task_cpu() is not the one it was taken from.
+	 */
+	p->dl.dl_bw_offrq = 1;
 	rq_unlock(rq, &rf);
 }
 
@@ -3736,7 +3751,9 @@ static void switched_from_dl(struct rq *rq, struct task_struct *p)
 			dl_task_release_bw(p, dl_task_root_domain_cpu(p));
 			released = true;
 		}
-		sub_rq_bw(&p->dl, &rq->dl);
+		if (!p->dl.dl_bw_offrq)
+			sub_rq_bw(&p->dl, &rq->dl);
+		p->dl.dl_bw_offrq = 0;
 		/*
 		 * Released: reset the parameters, as inactive_task_timer()
 		 * does. Kept, they would make the task one with bandwidth to
@@ -4191,6 +4208,7 @@ static void __dl_clear_params(struct sched_dl_entity *dl_se)
 	dl_se->dl_defer			= 0;
 	dl_se->dl_defer_running		= 0;
 	dl_se->dl_defer_armed		= 0;
+	dl_se->dl_bw_offrq		= 0;
 
 #ifdef CONFIG_RT_MUTEXES
 	dl_se->pi_se			= dl_se;
-- 
2.47.3

[PATCH 10/12] sched/debug: Show the deadline bandwidth of each runqueue

[Mathieu Desnoyers]

sched_debug prints the bandwidth each root domain has handed out
(dl_bw->total_bw), and nothing of the two sums each runqueue keeps:
this_bw, the bandwidth of every deadline task of that CPU, and
running_bw, the part of it whose tasks are active. GRUB drains the
runtime of a reclaiming task at the rate the two give, the bandwidth of
its CPU that is reserved and active (grub_reclaim(): max_bw - (this_bw -
running_bw) - extra_bw): the less of its CPU is active, the slower its
runtime drains, and the longer it runs on.

Both sums have invariants a test can check, which the kernel itself
warns about when they break: neither may wrap, and running_bw never
exceeds this_bw. Print them.

Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
---
 kernel/sched/debug.c | 2 ++
 1 file changed, 2 insertions(+)

diff --git a/kernel/sched/debug.c b/kernel/sched/debug.c
index e6a3b516c703..8a726817baa0 100644
--- a/kernel/sched/debug.c
+++ b/kernel/sched/debug.c
@@ -1166,6 +1166,8 @@ void print_dl_rq(struct seq_file *m, int cpu, struct dl_rq *dl_rq)
 	SEQ_printf(m, "  .%-30s: %lu\n", #x, (unsigned long)(dl_rq->x))
 
 	PU(dl_nr_running);
+	PU(running_bw);
+	PU(this_bw);
 	dl_bw = &cpu_rq(cpu)->rd->dl_bw;
 	SEQ_printf(m, "  .%-30s: %lld\n", "dl_bw->bw", dl_bw->bw);
 	SEQ_printf(m, "  .%-30s: %lld\n", "dl_bw->total_bw", dl_bw->total_bw);
-- 
2.47.3

[PATCH 11/12] sched/deadline: Rebuild the root domains' accounting without cpusets too

[Mathieu Desnoyers]

A change of the root domains, which CPU hotplug and suspend and resume
make, clears their deadline bandwidth accounting and fills it back: the
servers of each CPU, and the bandwidth of the deadline tasks of each
cpuset. The walk that puts the tasks back lives in the cpuset code,
dl_rebuild_rd_accounting(), and is a stub without CONFIG_CPUSETS: such
a kernel loses the bandwidth of every deadline task at the first
hotplug, total_bw of the new root domain holding its servers alone.

The tasks are never told. Each still takes its bandwidth out of
total_bw once it leaves SCHED_DEADLINE, or dies: it underflows, and
admission afterwards refuses every deadline task of the root domain.

Walk the tasks instead of the cpusets, which is all there is without
them, and keep one declaration beside dl_clear_root_domains() for both.

In 8-CPU VMs built without CONFIG_CPUSETS, the hotplug_sleepers case of
the selftest added later in this series admits 9 tasks of 10ms every
100ms before taking a CPU offline and back, and 0 after, on v7.4-rc1 as
with the patches before this one; hotplug_departed and
hotplug_server_refused fail after it, and two more hotplug cases skip
for want of room. The five pass with this change, in 4 VMs, with no
warning.

Fixes: f9a25f776d78 ("cpusets: Rebuild root domain deadline accounting information")
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
---
 include/linux/cpuset.h         |  5 -----
 include/linux/sched/deadline.h |  1 +
 kernel/sched/deadline.c        | 22 ++++++++++++++++++++++
 3 files changed, 23 insertions(+), 5 deletions(-)

diff --git a/include/linux/cpuset.h b/include/linux/cpuset.h
index 914983387e95..608c3c5a9535 100644
--- a/include/linux/cpuset.h
+++ b/include/linux/cpuset.h
@@ -129,7 +129,6 @@ static inline int cpuset_do_page_mem_spread(void)
 
 extern bool current_cpuset_is_being_rebound(void);
 
-extern void dl_rebuild_rd_accounting(void);
 extern void rebuild_sched_domains(void);
 
 extern void cpuset_print_current_mems_allowed(void);
@@ -273,10 +272,6 @@ static inline bool current_cpuset_is_being_rebound(void)
 	return false;
 }
 
-static inline void dl_rebuild_rd_accounting(void)
-{
-}
-
 static inline void rebuild_sched_domains(void)
 {
 	guard(cpus_read_lock)();
diff --git a/include/linux/sched/deadline.h b/include/linux/sched/deadline.h
index bdf39ac1d43d..e30b6ac2b050 100644
--- a/include/linux/sched/deadline.h
+++ b/include/linux/sched/deadline.h
@@ -33,6 +33,7 @@ struct root_domain;
 extern void dl_add_task_root_domain(struct task_struct *p);
 extern void dl_clear_root_domain(struct root_domain *rd);
 extern void dl_clear_root_domains(void);
+extern void dl_rebuild_rd_accounting(void);
 /*
  * Return whether moving DL task @p to @new_mask requires moving DL
  * bandwidth accounting between root domains. This helper is specific to
diff --git a/kernel/sched/deadline.c b/kernel/sched/deadline.c
index a8906cf96640..0ea902b9e5d0 100644
--- a/kernel/sched/deadline.c
+++ b/kernel/sched/deadline.c
@@ -3668,6 +3668,28 @@ void dl_clear_root_domain(struct root_domain *rd)
 		dl_server_add_bw(rd, i);
 }
 
+#ifndef CONFIG_CPUSETS
+/*
+ * Rebuild the root domains' accounting, where no cpuset holds the
+ * deadline tasks of each: they are found by walking them all, which
+ * dl_rebuild_rd_accounting() of the cpusets does per cpuset instead.
+ */
+void dl_rebuild_rd_accounting(void)
+{
+	struct task_struct *g, *p;
+
+	lockdep_assert_cpus_held();
+	lockdep_assert_held(&sched_domains_mutex);
+
+	dl_clear_root_domains();
+
+	read_lock(&tasklist_lock);
+	for_each_process_thread(g, p)
+		dl_add_task_root_domain(p);
+	read_unlock(&tasklist_lock);
+}
+#endif /* !CONFIG_CPUSETS */
+
 /*
  * Clear every root domain ahead of a rebuild of their accounting, which
  * dl_add_task_root_domain() then fills with the deadline tasks of the
-- 
2.47.3

[PATCH 12/12] selftests/sched: Add a test of SCHED_DEADLINE bandwidth accounting

[Mathieu Desnoyers]

Add deadline_bw_test, 43 cases that take deadline tasks through priority
inheritance, parameter changes, cpuset moves, deaths, sched_yield(),
runtime overruns, bandwidth reclaiming, changes to the fair servers, a
randomized mix of all of those, and CPU hotplug.

Each case measures the free bandwidth of a root domain before and after
it runs, as the number of tasks of 10ms every 100ms the root domain
admits, and wants the two equal once the case's tasks are gone and their
0-lag time is past: fewer is bandwidth leaked, more is bandwidth
released twice. A deadline task that a case keeps running must also make
progress.

The reclaiming and server cases measure instead the share of a CPU a
deadline task with SCHED_FLAG_RECLAIM gets, which tells of the bandwidth
its CPU keeps as reclaimable (extra_bw) where the admission of probe()
tells of the root domain's own (total_bw): of a CPU of its own, a task
of 10ms every 100ms got 66% of it, where one without the flag got 9%,
and it follows the fair server of that CPU, 49% with a server of 10% and
24% with one of 30%, as GRUB has it.

params_waking and random_mix check the two sums each runqueue keeps,
this_bw and running_bw, which "sched/debug: Show the deadline bandwidth
of each runqueue" prints: parameter changes of a deadline task whose
wakeups move it between the two CPUs of a partition root, and six tasks
taking random transitions of their own while the case moves, kills and
reparameterizes them and changes the fair servers, three thousand
transitions in three seconds. Both want this_bw of each CPU back where
it started. random_mix's seed is fixed, so a failure can be replayed.

The cases in the partition root each get a new one, the accounting
rebuilt in between, so that a case that breaks it does not fail the next
ones. The server cases put the fair servers back as they found them.
Skipped without root or deadline admission control, and the cases that
need them without a cpuset partition root, debugfs, CPU hotplug or
enough CPUs.

Kprobes confirmed the states the cases mean to reach: the inactive timer
pending at a kill, the replenishment, the boost, and the fair server
stopped, deferred and serving at the debugfs writes. A write cannot find
a server in two of its states: throttled after serving, which the last
of the served task's runtime, charged as background running, turns at
once into deferred anew; and its idle wait, which on a CPU with no tick
in idle begins and ends in one timer callback.

In 8 VMs of 8 vCPUs, v7.4-rc1 with the four deadline fixes of
sched/urgent fails three cases, every time:

 - pi_former_owner_asleep: the waiter of its second round is refused
   with EBUSY in a partition with room, total_bw having wrapped when the
   deboost of the first round released the owner's bandwidth a second
   time;
 - params_keep_class_change: the refused request leaves 40% of the
   partition reserved;
 - random_mix: the partition root admits 5, 8 or 10 tasks of 10% where
   it admitted 9 before, bandwidth leaked and bandwidth released twice
   both.

params_waking fails on every VM of 8 vCPUs and of 4 without
"sched/deadline: Do not take a waking task's bandwidth off a runqueue it
left": this_bw of one of the two CPUs ends elsewhere than it started,
having lost or gained the bandwidth of a task or of a fair server, and
the kernel warns of the underflow that got it there. random_mix catches
that one on 1 VM of 3, a race being what it is.

With this series, all 43 cases pass every time, with PREEMPT_RT as well,
and with no warning. Built without cpusets they need the previous patch:
without it hotplug_sleepers fails, and the hotplug cases after it fail
or skip for want of room, every time, the root domain that a CPU hotplug
makes getting back the bandwidth of its servers alone.

Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
---
 tools/testing/selftests/sched/.gitignore      |    1 +
 tools/testing/selftests/sched/Makefile        |    2 +-
 .../selftests/sched/deadline_bw_test.c        | 3182 +++++++++++++++++
 3 files changed, 3184 insertions(+), 1 deletion(-)
 create mode 100644 tools/testing/selftests/sched/deadline_bw_test.c

diff --git a/tools/testing/selftests/sched/.gitignore b/tools/testing/selftests/sched/.gitignore
index fc7ab1ddbbe7..27018878c063 100644
--- a/tools/testing/selftests/sched/.gitignore
+++ b/tools/testing/selftests/sched/.gitignore
@@ -1,3 +1,4 @@
 cs_prctl_test
 deadline_switch_test
 deadline_rebuild_test
+deadline_bw_test
diff --git a/tools/testing/selftests/sched/Makefile b/tools/testing/selftests/sched/Makefile
index 728e046b463c..a32a0f7aa76b 100644
--- a/tools/testing/selftests/sched/Makefile
+++ b/tools/testing/selftests/sched/Makefile
@@ -10,6 +10,6 @@ LDLIBS += -lpthread
 
 TEST_GEN_FILES := cs_prctl_test
 TEST_PROGS := cs_prctl_test
-TEST_GEN_PROGS := deadline_switch_test deadline_rebuild_test
+TEST_GEN_PROGS := deadline_switch_test deadline_rebuild_test deadline_bw_test
 
 include ../lib.mk
diff --git a/tools/testing/selftests/sched/deadline_bw_test.c b/tools/testing/selftests/sched/deadline_bw_test.c
new file mode 100644
index 000000000000..d16aee10155b
--- /dev/null
+++ b/tools/testing/selftests/sched/deadline_bw_test.c
@@ -0,0 +1,3182 @@
+// SPDX-License-Identifier: GPL-2.0
+/*
+ * SCHED_DEADLINE bandwidth through priority inheritance, parameter changes,
+ * cpuset moves, deaths, yields, runtime overruns, bandwidth reclaiming,
+ * changes to the fair servers and CPU hotplug.
+ *
+ * Each case measures the free bandwidth of a root domain before and after
+ * it runs: the number of tasks of 10ms every 100ms that root domain admits
+ * (probe()). Once every task of the case is gone and its 0-lag time is
+ * past, the two must be equal: fewer is bandwidth leaked, more is
+ * bandwidth released twice, which lets the root domain admit deadline
+ * tasks beyond its capacity. A deadline task a case keeps running must
+ * also make progress.
+ *
+ * The reclaiming cases measure instead the share of a CPU a deadline task
+ * with SCHED_FLAG_RECLAIM gets, which tells of the free bandwidth its CPU
+ * keeps of the root domain (extra_bw), where probe() tells of the root
+ * domain's own (total_bw).
+ *
+ * Every case but the hotplug ones uses P, a partition root of one CPU,
+ * the last one, made anew for each case: the rebuild of the accounting
+ * that makes it clears what an earlier case left. The hotplug cases run in
+ * the root domain of all CPUs. The server cases change the fair server of a
+ * CPU through debugfs, and the test puts it back as it found it. Needs
+ * root, deadline admission control, and for the cases that use them, the
+ * cgroup v2 cpuset controller, debugfs and CPU hotplug.
+ */
+#define _GNU_SOURCE
+#include <errno.h>
+#include <fcntl.h>
+#include <limits.h>
+#include <pthread.h>
+#include <sched.h>
+#include <semaphore.h>
+#include <signal.h>
+#include <stdatomic.h>
+#include <stdint.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+#include <sys/mman.h>
+#include <sys/stat.h>
+#include <sys/syscall.h>
+#include <sys/sysinfo.h>
+#include <sys/wait.h>
+#include <time.h>
+#include <unistd.h>
+#include <linux/futex.h>
+
+#include "../kselftest.h"
+
+#ifndef SCHED_DEADLINE
+#define SCHED_DEADLINE	6
+#endif
+#ifndef SCHED_FLAG_RECLAIM
+#define SCHED_FLAG_RECLAIM	0x02
+#endif
+#ifndef SCHED_FLAG_DL_OVERRUN
+#define SCHED_FLAG_DL_OVERRUN	0x04
+#endif
+#ifndef SCHED_FLAG_KEEP_PARAMS
+#define SCHED_FLAG_KEEP_PARAMS	0x10
+#endif
+
+#define NSEC_PER_USEC	1000ULL
+#define NSEC_PER_MSEC	1000000ULL
+#define NSEC_PER_SEC	1000000000ULL
+
+#define PROBE_RUNTIME	(10 * NSEC_PER_MSEC)
+#define PROBE_PERIOD	(100 * NSEC_PER_MSEC)
+#define PERIOD		(100 * NSEC_PER_MSEC)
+
+struct dl_attr {
+	uint32_t size;
+	uint32_t sched_policy;
+	uint64_t sched_flags;
+	int32_t sched_nice;
+	uint32_t sched_priority;
+	uint64_t sched_runtime;
+	uint64_t sched_deadline;
+	uint64_t sched_period;
+};
+
+static char root[PATH_MAX], cg_p[PATH_MAX], cg_q[PATH_MAX];
+static int ncpus;
+
+/* Both clocks are always supported and the pointer is valid: no error. */
+static uint64_t now_ns(void)
+{
+	struct timespec ts;
+
+	clock_gettime(CLOCK_MONOTONIC, &ts);
+	return ts.tv_sec * NSEC_PER_SEC + ts.tv_nsec;
+}
+
+static uint64_t thread_time_ns(void)
+{
+	struct timespec ts;
+
+	clock_gettime(CLOCK_THREAD_CPUTIME_ID, &ts);
+	return ts.tv_sec * NSEC_PER_SEC + ts.tv_nsec;
+}
+
+static void sleep_ns(uint64_t ns)
+{
+	struct timespec ts = { .tv_sec = ns / NSEC_PER_SEC, .tv_nsec = ns % NSEC_PER_SEC };
+
+	while (nanosleep(&ts, &ts) && errno == EINTR)
+		;
+}
+
+static void spin_ns(uint64_t ns)
+{
+	uint64_t end = thread_time_ns() + ns;
+
+	while (thread_time_ns() < end)
+		;
+}
+
+/*
+ * Polls @cond every @step, at most @ms: 0 once it holds, -1 on a timeout.
+ * Every wait here is bounded, so that a child that never started, or was
+ * refused SCHED_DEADLINE, fails its case instead of hanging it.
+ */
+#define wait_for_step(ms, step, cond)					\
+({									\
+	uint64_t wait_end = now_ns() + (uint64_t)(ms) * NSEC_PER_MSEC;	\
+	int wait_ret = -1;						\
+									\
+	while (1) {							\
+		if (cond) {						\
+			wait_ret = 0;					\
+			break;						\
+		}							\
+		if (now_ns() >= wait_end)				\
+			break;						\
+		sleep_ns(step);						\
+	}								\
+	wait_ret;							\
+})
+
+#define wait_for(ms, cond)	wait_for_step(ms, NSEC_PER_MSEC, cond)
+
+/* sem_wait(), retrying the signals that interrupt it. */
+static void sem_wait_sig(sem_t *s)
+{
+	while (sem_wait(s)) {
+		if (errno == EINTR)
+			continue;
+		ksft_print_msg("sem_wait: %s\n", strerror(errno));
+		return;
+	}
+}
+
+/* The same, at most @ms: 0, or -1. For what a thread or a child must post. */
+static int sem_wait_for(sem_t *s, int ms)
+{
+	struct timespec ts;
+
+	clock_gettime(CLOCK_REALTIME, &ts);
+	ts.tv_nsec += (long)(ms % 1000) * 1000000L;
+	ts.tv_sec += ms / 1000 + ts.tv_nsec / 1000000000L;
+	ts.tv_nsec %= 1000000000L;
+	while (sem_timedwait(s, &ts)) {
+		if (errno == EINTR)
+			continue;
+		if (errno != ETIMEDOUT)
+			ksft_print_msg("sem_timedwait: %s\n", strerror(errno));
+		return -1;
+	}
+	return 0;
+}
+
+/* fork(), which tells of its own failure: the caller handles -1. */
+static pid_t fork_child(const char *what)
+{
+	pid_t pid = fork();
+
+	if (pid < 0)
+		ksft_print_msg("fork for %s: %s\n", what, strerror(errno));
+	return pid;
+}
+
+static void reap(pid_t pid)
+{
+	int status;
+
+	if (pid <= 0)
+		return;
+	if (kill(pid, SIGKILL) && errno != ESRCH)
+		ksft_print_msg("kill %d: %s\n", pid, strerror(errno));
+	while (waitpid(pid, &status, 0) != pid) {
+		if (errno == EINTR)
+			continue;
+		ksft_print_msg("waitpid %d: %s\n", pid, strerror(errno));
+		break;
+	}
+}
+
+static void join(pthread_t t)
+{
+	int err = pthread_join(t, NULL);
+
+	if (err)
+		ksft_print_msg("pthread_join: %s\n", strerror(err));
+}
+
+static pid_t gettid_(void)
+{
+	return syscall(SYS_gettid);
+}
+
+static int set_deadline_flags(pid_t tid, uint64_t runtime, uint64_t period,
+			      uint64_t flags)
+{
+	struct dl_attr attr = {
+		.size = sizeof(attr),
+		.sched_policy = SCHED_DEADLINE,
+		.sched_flags = flags,
+		.sched_runtime = runtime,
+		.sched_deadline = period,
+		.sched_period = period,
+	};
+
+	return syscall(SYS_sched_setattr, tid, &attr, 0) ? -errno : 0;
+}
+
+static int set_deadline(pid_t tid, uint64_t runtime, uint64_t period)
+{
+	return set_deadline_flags(tid, runtime, period, 0);
+}
+
+static int set_other(pid_t tid)
+{
+	struct dl_attr attr = { .size = sizeof(attr), .sched_policy = SCHED_OTHER };
+
+	return syscall(SYS_sched_setattr, tid, &attr, 0) ? -errno : 0;
+}
+
+static int write_file(const char *dir, const char *name, const char *val)
+{
+	char path[PATH_MAX];
+	int fd, err = 0;
+	ssize_t n;
+
+	if (snprintf(path, sizeof(path), "%s/%s", dir, name) >= (int)sizeof(path))
+		return -ENAMETOOLONG;
+	fd = open(path, O_WRONLY);
+	if (fd < 0)
+		return -errno;
+	n = write(fd, val, strlen(val));
+	if (n < 0)
+		err = -errno;
+	else if (n != (ssize_t)strlen(val))
+		err = -EIO;
+	if (close(fd) && !err)
+		err = -errno;
+	return err;
+}
+
+static int read_file(const char *path, char *buf, size_t len)
+{
+	int fd = open(path, O_RDONLY);
+	ssize_t n;
+
+	if (fd < 0)
+		return -1;
+	do {
+		n = read(fd, buf, len - 1);
+	} while (n < 0 && errno == EINTR);
+	close(fd);
+	if (n < 0)
+		return -1;
+	buf[n] = 0;
+	return 0;
+}
+
+static int enter(const char *cg, pid_t pid)
+{
+	char buf[16];
+
+	snprintf(buf, sizeof(buf), "%d", pid);
+	return write_file(cg, "cgroup.procs", buf);
+}
+
+/* @cg, a partition root of the CPUs @cpus names: 0, or -1. */
+static int make_partition_cpus(const char *cg, const char *cpus)
+{
+	char path[PATH_MAX + 32], buf[32];
+
+	if (mkdir(cg, 0755) && errno != EEXIST)
+		return -1;
+	if (write_file(cg, "cpuset.cpus", cpus) ||
+	    write_file(cg, "cpuset.cpus.partition", "root"))
+		return -1;
+	snprintf(path, sizeof(path), "%s/cpuset.cpus.partition", cg);
+	if (read_file(path, buf, sizeof(buf)) || strcmp(buf, "root\n"))
+		return -1;
+	return 0;
+}
+
+/* @cg, a partition root of CPU @cpu: 0, or -1. */
+static int make_partition(const char *cg, int cpu)
+{
+	char buf[32];
+
+	snprintf(buf, sizeof(buf), "%d", cpu);
+	return make_partition_cpus(cg, buf);
+}
+
+static void remove_partition(const char *cg)
+{
+	int err = write_file(cg, "cpuset.cpus.partition", "member");
+
+	if (err && err != -ENOENT)
+		ksft_print_msg("%s back to a member: %s\n", cg, strerror(-err));
+	/* A cgroup whose last task just died takes a moment to empty. */
+	if (wait_for(1000, !rmdir(cg) || errno == ENOENT))
+		ksft_print_msg("rmdir %s: %s\n", cg, strerror(errno));
+}
+
+/* P, a partition root of the last CPU: 0, or -1. */
+static int make_p(void)
+{
+	return make_partition(cg_p, ncpus - 1);
+}
+
+static void remove_p(void)
+{
+	remove_partition(cg_p);
+}
+
+/* The CPU @pid last ran on, from /proc. */
+static int task_cpu_of(pid_t pid)
+{
+	char path[64], buf[1024], *p;
+	int i;
+
+	snprintf(path, sizeof(path), "/proc/%d/stat", pid);
+	if (read_file(path, buf, sizeof(buf)))
+		return -1;
+	p = strrchr(buf, ')');
+	for (i = 0; p && i < 37; i++)
+		p = strchr(p + 1, ' ');
+	return p ? atoi(p + 1) : -1;
+}
+
+/* The CPU time @tid has used. */
+static uint64_t cpu_time_of(pthread_t t)
+{
+	static int told;
+	struct timespec ts;
+	clockid_t c;
+
+	if (pthread_getcpuclockid(t, &c) || clock_gettime(c, &ts)) {
+		if (!told++)
+			ksft_print_msg("the CPU time of a thread cannot be read: %s\n",
+				       strerror(errno));
+		return 0;
+	}
+	return ts.tv_sec * NSEC_PER_SEC + ts.tv_nsec;
+}
+
+/* The share of a CPU, in percent, that @t uses over @ns, a period later. */
+static int share_of(pthread_t t, uint64_t ns)
+{
+	uint64_t cpu, wall;
+
+	sleep_ns(PERIOD);		/* a period of its own to settle in */
+	cpu = cpu_time_of(t);
+	wall = now_ns();
+	sleep_ns(ns);
+	cpu = cpu_time_of(t) - cpu;
+	wall = now_ns() - wall;
+	return wall ? (int)(100 * cpu / wall) : -1;
+}
+
+/*
+ * The probe: from a process that joins @cg (the root domain of its CPUs),
+ * threads each make themselves a deadline task of PROBE_RUNTIME every
+ * PROBE_PERIOD, one at a time, until one is refused; then they all exit.
+ * Returns how many were admitted, or -1. The threads never run past their
+ * first instants, so their bandwidth goes at their death; probe() waits for
+ * their 0-lag times all the same.
+ */
+struct probe_slot {
+	pthread_t t;
+	int err;
+};
+
+static sem_t probe_done;
+static int probe_hold[2];
+
+static void *probe_thread(void *arg)
+{
+	struct probe_slot *s = arg;
+	char c;
+
+	s->err = set_deadline(0, PROBE_RUNTIME, PROBE_PERIOD);
+	if (sem_post(&probe_done))
+		ksft_print_msg("sem_post: %s\n", strerror(errno));
+	/* Asleep until the probe is over: the write end closes. */
+	while (!s->err) {
+		ssize_t r = read(probe_hold[0], &c, 1);
+
+		if (r >= 0)
+			break;
+		if (errno != EINTR) {
+			s->err = -errno;
+			break;
+		}
+	}
+	return NULL;
+}
+
+static int probe(const char *cg)
+{
+	int fd[2], n = -1, max = 16 * ncpus + 16;
+	pid_t pid;
+
+	if (pipe(fd)) {
+		ksft_print_msg("pipe: %s\n", strerror(errno));
+		return -1;
+	}
+	pid = fork_child("the admission check");
+	if (!pid) {
+		struct probe_slot *s = calloc(max, sizeof(*s));
+		pthread_attr_t a;
+		int i, k = 0;
+
+		close(fd[0]);
+		if (!s || sem_init(&probe_done, 0, 0) || pipe(probe_hold) ||
+		    (cg && enter(cg, getpid())))
+			_exit(1);
+		if (pthread_attr_init(&a) || pthread_attr_setstacksize(&a, 64 * 1024))
+			_exit(1);
+		for (i = 0; i < max; i++) {
+			if (pthread_create(&s[i].t, &a, probe_thread, &s[i]))
+				break;
+			if (sem_wait_for(&probe_done, 10000)) {
+				k = -1;
+				i++;	/* that thread is to be joined as well */
+				break;
+			}
+			if (s[i].err) {
+				if (s[i].err != -EBUSY)
+					k = -1;
+				join(s[i].t);
+				break;
+			}
+			if (k >= 0)
+				k++;
+		}
+		if (i == max)
+			k = -1;
+		close(probe_hold[1]);
+		while (--i >= 0)
+			join(s[i].t);
+		if (write(fd[1], &k, sizeof(k)) != sizeof(k))
+			_exit(1);
+		_exit(0);
+	}
+	close(fd[1]);
+	if (pid < 0 || read(fd[0], &n, sizeof(n)) != sizeof(n))
+		n = -1;
+	close(fd[0]);
+	reap(pid);
+	sleep_ns(3 * PROBE_PERIOD);
+	return n;
+}
+
+/*
+ * A case runs in a child process, in @cg, so that all its threads go with
+ * it: @fn returns KSFT_PASS or KSFT_FAIL, or KSFT_SKIP.
+ */
+static int run_in(const char *cg, int (*fn)(void))
+{
+	pid_t pid = fork_child("a case");
+	int status;
+
+	if (!pid) {
+		if (cg && enter(cg, getpid()))
+			_exit(KSFT_SKIP);
+		_exit(fn());
+	}
+	if (pid < 0)
+		return KSFT_FAIL;
+	while (waitpid(pid, &status, 0) != pid) {
+		if (errno == EINTR)
+			continue;
+		ksft_print_msg("waitpid %d: %s\n", pid, strerror(errno));
+		return KSFT_FAIL;
+	}
+	if (!WIFEXITED(status)) {
+		ksft_print_msg("the case died of signal %d\n",
+			       WIFSIGNALED(status) ? WTERMSIG(status) : 0);
+		return KSFT_FAIL;
+	}
+	return WEXITSTATUS(status);
+}
+
+/* @fn in @cg, with the free bandwidth of @cg's root domain the same after. */
+static int measured(const char *name, const char *cg, int (*fn)(void))
+{
+	int before, after, ret;
+
+	before = probe(cg);
+	if (before <= 0) {
+		ksft_print_msg("%s: no room to probe (%d)\n", name, before);
+		return KSFT_SKIP;
+	}
+	ret = run_in(cg, fn);
+	sleep_ns(3 * PERIOD);
+	after = probe(cg);
+	if (ret == KSFT_PASS && after != before) {
+		ksft_print_msg("%s: %d probe tasks admitted before, %d after: %s\n",
+			       name, before, after,
+			       after < before ? "bandwidth leaked" : "bandwidth released twice");
+		ret = KSFT_FAIL;
+	}
+	return ret;
+}
+
+/* Priority inheritance */
+
+static pthread_mutex_t pi_lock;
+static sem_t owner_ready, owner_go;
+static atomic_int owner_holds, owner_tid;
+
+/* 0, or -1 where a priority inheritance mutex is not to be had. */
+static int pi_init(void)
+{
+	pthread_mutexattr_t a;
+	int err;
+
+	err = pthread_mutexattr_init(&a);
+	if (!err)
+		err = pthread_mutexattr_setprotocol(&a, PTHREAD_PRIO_INHERIT);
+	if (!err)
+		err = pthread_mutex_init(&pi_lock, &a);
+	if (err) {
+		ksft_print_msg("no priority inheritance mutex: %s\n", strerror(err));
+		return -1;
+	}
+	if (sem_init(&owner_ready, 0, 0) || sem_init(&owner_go, 0, 0)) {
+		ksft_print_msg("sem_init: %s\n", strerror(errno));
+		return -1;
+	}
+	owner_holds = 0;
+	return 0;
+}
+
+/*
+ * The calling thread, a deadline task meanwhile, waits for the lock up to
+ * @ms: 0 when it times out, or gets the lock, as @timeout expects.
+ */
+static int wait_lock_for(int ms, int timeout)
+{
+	struct timespec ts;
+	int err;
+
+	err = set_deadline(0, 5 * NSEC_PER_MSEC, 50 * NSEC_PER_MSEC);
+	if (err) {
+		ksft_print_msg("a waiter refused as a deadline task: %s\n", strerror(-err));
+		return -1;
+	}
+	clock_gettime(CLOCK_REALTIME, &ts);
+	ts.tv_nsec += (long)ms * 1000000L;
+	ts.tv_sec += ts.tv_nsec / 1000000000L;
+	ts.tv_nsec %= 1000000000L;
+	err = pthread_mutex_timedlock(&pi_lock, &ts);
+	if (!err) {
+		int e = pthread_mutex_unlock(&pi_lock);
+
+		if (e)
+			ksft_print_msg("a waiter cannot unlock: %s\n", strerror(e));
+	}
+	if (set_other(0)) {
+		ksft_print_msg("a waiter cannot leave SCHED_DEADLINE\n");
+		return -1;
+	}
+	if (err != (timeout ? ETIMEDOUT : 0)) {
+		ksft_print_msg("a waiter of the lock: %s, not %s\n", err ? strerror(err) : "got it",
+			       timeout ? "a timeout" : "the lock");
+		return -1;
+	}
+	return 0;
+}
+
+/* The lock of an owner: -1 told of, and owner_holds says so. */
+static int take_pi_lock(void)
+{
+	int err = pthread_mutex_lock(&pi_lock);
+
+	if (err) {
+		ksft_print_msg("an owner cannot take the lock: %s\n", strerror(err));
+		owner_holds = -1;
+	}
+	return err ? -1 : 0;
+}
+
+static void drop_pi_lock(void)
+{
+	int err = pthread_mutex_unlock(&pi_lock);
+
+	if (err)
+		ksft_print_msg("an owner cannot unlock: %s\n", strerror(err));
+}
+
+/* Owner: was a deadline task (@was_dl), takes the lock and sleeps with it. */
+static void *sleeping_owner(void *arg)
+{
+	int was_dl = (long)arg;
+
+	owner_tid = gettid_();
+	if (was_dl) {
+		if (set_deadline(0, 30 * NSEC_PER_MSEC, PERIOD)) {
+			owner_holds = -1;
+			sem_post(&owner_ready);
+			return (void *)1;
+		}
+		spin_ns(NSEC_PER_MSEC);
+		/* Asleep past its 0-lag time, switched out by the main thread. */
+		sem_post(&owner_ready);
+		sem_wait_sig(&owner_go);
+	}
+	if (take_pi_lock())
+		return (void *)1;
+	owner_holds = 2;
+	sleep_ns(400 * NSEC_PER_MSEC);
+	drop_pi_lock();
+	return NULL;
+}
+
+static int pi_asleep(int was_dl, int rounds)
+{
+	pthread_t o;
+	int r, ret = KSFT_PASS;
+
+	if (pi_init())
+		return KSFT_SKIP;
+	if (pthread_create(&o, NULL, sleeping_owner, (void *)(long)was_dl)) {
+		ksft_print_msg("the owner thread could not start\n");
+		return KSFT_FAIL;
+	}
+	if (was_dl) {
+		if (sem_wait_for(&owner_ready, 5000)) {
+			ksft_print_msg("the owner did not become a deadline task\n");
+			ret = KSFT_FAIL;
+		} else {
+			sleep_ns(200 * NSEC_PER_MSEC);
+			if (set_other(owner_tid)) {
+				ksft_print_msg("the owner cannot leave SCHED_DEADLINE\n");
+				ret = KSFT_FAIL;
+			}
+		}
+		sem_post(&owner_go);
+	}
+	if (ret == KSFT_PASS && (wait_for(5000, owner_holds) || owner_holds != 2)) {
+		ksft_print_msg("the owner never took the lock\n");
+		ret = KSFT_FAIL;
+	}
+	if (ret == KSFT_PASS)
+		sleep_ns(20 * NSEC_PER_MSEC);
+	/* Each attempt boosts the sleeping owner, its timeout deboosts it asleep. */
+	for (r = 0; r < rounds && ret == KSFT_PASS; r++) {
+		if (wait_lock_for(20, 1)) {
+			ksft_print_msg("round %d of %d failed\n", r + 1, rounds);
+			ret = KSFT_FAIL;
+		}
+	}
+	join(o);
+	return ret;
+}
+
+static int pi_other_owner_asleep(void)
+{
+	return pi_asleep(0, 5);
+}
+
+static int pi_former_owner_asleep(void)
+{
+	return pi_asleep(1, 5);
+}
+
+/* A deadline owner boosted by a deadline waiter of an earlier deadline. */
+static void *dl_owner(void *arg)
+{
+	uint64_t end;
+
+	if (set_deadline(0, 30 * NSEC_PER_MSEC, PERIOD)) {
+		owner_holds = -1;
+		return (void *)1;
+	}
+	if (take_pi_lock())
+		return (void *)1;
+	owner_holds = 2;
+	end = now_ns() + 300 * NSEC_PER_MSEC;
+	while (now_ns() < end) {
+		spin_ns(2 * NSEC_PER_MSEC);
+		sleep_ns(5 * NSEC_PER_MSEC);
+	}
+	drop_pi_lock();
+	return NULL;
+}
+
+static int pi_deadline_owner(void)
+{
+	int r, ret = KSFT_PASS, err;
+	pthread_t o;
+	void *res;
+
+	if (pi_init())
+		return KSFT_SKIP;
+	if (pthread_create(&o, NULL, dl_owner, NULL)) {
+		ksft_print_msg("the owner thread could not start\n");
+		return KSFT_FAIL;
+	}
+	if (wait_for(5000, owner_holds) || owner_holds != 2) {
+		ksft_print_msg("the deadline owner never took the lock\n");
+		ret = KSFT_FAIL;
+	}
+	for (r = 0; r < 5 && ret == KSFT_PASS; r++)
+		if (wait_lock_for(20, 1))
+			ret = KSFT_FAIL;
+	err = pthread_join(o, &res);
+	if (err)
+		ksft_print_msg("pthread_join: %s\n", strerror(err));
+	return res || err ? KSFT_FAIL : ret;
+}
+
+/* The owner runs when boosted, and its unlock deboosts it. */
+static void *running_owner(void *arg)
+{
+	if (take_pi_lock())
+		return (void *)1;
+	owner_holds = 2;
+	spin_ns(50 * NSEC_PER_MSEC);
+	drop_pi_lock();
+	return NULL;
+}
+
+static int pi_unlock_running(void)
+{
+	pthread_t o;
+	int r, ret = KSFT_PASS;
+
+	for (r = 0; r < 5 && ret == KSFT_PASS; r++) {
+		if (pi_init())
+			return KSFT_SKIP;
+		if (pthread_create(&o, NULL, running_owner, NULL)) {
+			ksft_print_msg("the owner thread could not start\n");
+			return KSFT_FAIL;
+		}
+		if (wait_for_step(5000, 100 * NSEC_PER_USEC, owner_holds) ||
+		    owner_holds != 2) {
+			ksft_print_msg("the owner never took the lock\n");
+			ret = KSFT_FAIL;
+		} else if (wait_lock_for(1000, 0)) {
+			ret = KSFT_FAIL;
+		}
+		join(o);
+	}
+	return ret;
+}
+
+/* Parameter changes */
+
+static atomic_int t_state;	/* 1: about to sleep, or spinning */
+static _Atomic pid_t t_tid;
+static sem_t t_exit;
+
+/* A deadline task that runs @run_ns of its runtime, then sleeps. */
+static void *runs_then_sleeps(void *arg)
+{
+	uint64_t run = (uint64_t)(long)arg;
+
+	t_tid = gettid_();
+	if (set_deadline(0, 20 * NSEC_PER_MSEC, PERIOD)) {
+		t_state = -1;
+		return (void *)1;
+	}
+	sleep_ns(PERIOD);	/* a fresh period */
+	spin_ns(run);
+	t_state = 1;
+	sem_wait_sig(&t_exit);
+	return NULL;
+}
+
+/* Starts runs_then_sleeps(): 0 once it is about to sleep, or -1. */
+static int start_sleeper(pthread_t *t, uint64_t run)
+{
+	t_state = 0;
+	if (sem_init(&t_exit, 0, 0)) {
+		ksft_print_msg("sem_init: %s\n", strerror(errno));
+		return -1;
+	}
+	if (pthread_create(t, NULL, runs_then_sleeps, (void *)(long)run)) {
+		ksft_print_msg("the sleeper thread could not start\n");
+		return -1;
+	}
+	if (wait_for_step(5000, 100 * NSEC_PER_USEC, t_state) || t_state != 1) {
+		ksft_print_msg("the sleeper was refused SCHED_DEADLINE\n");
+		join(*t);
+		return -1;
+	}
+	return 0;
+}
+
+static void stop_sleeper(pthread_t t)
+{
+	if (sem_post(&t_exit))
+		ksft_print_msg("sem_post: %s\n", strerror(errno));
+	join(t);
+}
+
+/* The root domain of @cg admits @want probe tasks now. */
+static int admits_in(const char *cg, int want, const char *what)
+{
+	int n = probe(cg);
+
+	if (n != want) {
+		ksft_print_msg("%s: %d probe tasks admitted, %d expected\n", what, n, want);
+		return -1;
+	}
+	return 0;
+}
+
+/* The root domain of the caller's cgroup admits @want probe tasks now. */
+static int admits(int want, const char *what)
+{
+	return admits_in(NULL, want, what);
+}
+
+static int params_asleep(void)
+{
+	static const uint64_t rt[] = { 40, 10, 30, 20 };
+	int base, i, ret = KSFT_PASS;
+	pthread_t t;
+
+	if (start_sleeper(&t, NSEC_PER_MSEC))
+		return KSFT_FAIL;
+	sleep_ns(2 * PERIOD);
+	/* Probed from here, in P: this process is P's. */
+	base = probe(NULL) + 2;		/* the task's 20% back */
+	for (i = 0; i < 4 && ret == KSFT_PASS; i++) {
+		char what[64];
+
+		if (set_deadline(t_tid, rt[i] * NSEC_PER_MSEC, PERIOD)) {
+			ret = KSFT_FAIL;
+			break;
+		}
+		snprintf(what, sizeof(what), "asleep, changed to %llums every 100ms",
+			 (unsigned long long)rt[i]);
+		if (admits(base - (int)(rt[i] / 10), what))
+			ret = KSFT_FAIL;
+	}
+	stop_sleeper(t);
+	return ret;
+}
+
+static int params_non_contending(void)
+{
+	pthread_t t;
+	int ret = KSFT_PASS;
+
+	/* 5ms of 20ms run: its 0-lag time some 20ms after it sleeps. */
+	if (start_sleeper(&t, 5 * NSEC_PER_MSEC))
+		return KSFT_FAIL;
+	sleep_ns(NSEC_PER_MSEC);
+	if (set_deadline(t_tid, 40 * NSEC_PER_MSEC, PERIOD) ||
+	    set_deadline(t_tid, 10 * NSEC_PER_MSEC, PERIOD))
+		ret = KSFT_FAIL;
+	stop_sleeper(t);
+	return ret;
+}
+
+static atomic_int spin_stop;
+static uint64_t spin_runtime, spin_flags;	/* set before the thread starts */
+
+static void *dl_spinner(void *arg)
+{
+	t_tid = gettid_();
+	if (set_deadline_flags(0, spin_runtime, PERIOD, spin_flags)) {
+		t_state = -1;
+		return (void *)1;
+	}
+	t_state = 1;
+	while (!spin_stop)
+		;
+	return NULL;
+}
+
+/* Starts dl_spinner() of @runtime every 100ms with @flags: 0, or -1. */
+static int start_spinner(pthread_t *t, uint64_t runtime, uint64_t flags)
+{
+	t_state = 0;
+	spin_stop = 0;
+	spin_runtime = runtime;
+	spin_flags = flags;
+	if (pthread_create(t, NULL, dl_spinner, NULL)) {
+		ksft_print_msg("the spinner thread could not start\n");
+		return -1;
+	}
+	if (!wait_for(5000, t_state) && t_state == 1)
+		return 0;
+	join(*t);
+	return -1;
+}
+
+static void stop_spinner(pthread_t t)
+{
+	spin_stop = 1;
+	set_other(t_tid);	/* out of the class already: no matter */
+	join(t);
+}
+
+/* Waits until @t stops using CPU time: throttled. 0, or -1 after 1s. */
+static int wait_throttled(pthread_t t)
+{
+	uint64_t end = now_ns() + NSEC_PER_SEC, last = cpu_time_of(t);
+
+	while (now_ns() < end) {
+		uint64_t cur;
+
+		sleep_ns(3 * NSEC_PER_MSEC);
+		cur = cpu_time_of(t);
+		if (cur == last)
+			return 0;
+		last = cur;
+	}
+	return -1;
+}
+
+/* @t runs again within @ns. */
+static int progresses(pthread_t t, uint64_t ns)
+{
+	uint64_t start = cpu_time_of(t), end = now_ns() + ns;
+
+	while (now_ns() < end) {
+		if (cpu_time_of(t) > start + NSEC_PER_MSEC)
+			return 0;
+		sleep_ns(2 * NSEC_PER_MSEC);
+	}
+	return -1;
+}
+
+static int params_throttled(void)
+{
+	int r, ret = KSFT_PASS;
+	pthread_t t;
+
+	if (start_spinner(&t, 10 * NSEC_PER_MSEC, 0))
+		return KSFT_FAIL;
+	for (r = 0; r < 5 && ret == KSFT_PASS; r++) {
+		if (wait_throttled(t) ||
+		    set_deadline(t_tid, (r & 1 ? 10 : 20) * NSEC_PER_MSEC, PERIOD)) {
+			ret = KSFT_FAIL;
+			break;
+		}
+		if (progresses(t, 3 * PERIOD)) {
+			ksft_print_msg("throttled, parameters changed: never ran again\n");
+			ret = KSFT_FAIL;
+		}
+	}
+	stop_spinner(t);
+	return ret;
+}
+
+static int params_refused(void)
+{
+	pthread_t t;
+	int ret = KSFT_PASS, base, err;
+
+	if (start_sleeper(&t, NSEC_PER_MSEC))
+		return KSFT_FAIL;
+	sleep_ns(2 * PERIOD);
+	base = probe(NULL);
+	/*
+	 * P's free bandwidth is at least @base probe tasks of 10%, and less
+	 * than one more: growing the task by one more than that is refused,
+	 * whatever the admission limit.
+	 */
+	if (20 + 10 * (base + 1) > 100) {
+		stop_sleeper(t);
+		return KSFT_SKIP;	/* more room than a task of P can take */
+	}
+	err = set_deadline(t_tid, (20 + 10 * (uint64_t)(base + 1)) * NSEC_PER_MSEC, PERIOD);
+	if (err != -EBUSY) {
+		ksft_print_msg("an increase beyond P's room: %s, not EBUSY\n",
+			       err ? strerror(-err) : "accepted");
+		ret = KSFT_FAIL;
+	} else if (admits(base, "after a refused increase")) {
+		ret = KSFT_FAIL;
+	}
+	stop_sleeper(t);
+	return ret;
+}
+
+/*
+ * SCHED_FLAG_KEEP_PARAMS with a change of class is refused, with nothing
+ * reserved for the deadline parameters it would keep: the task's own,
+ * its slice the runtime.
+ */
+static int params_keep_class_change(void)
+{
+	struct dl_attr attr = {
+		.size = sizeof(attr),
+		.sched_policy = SCHED_OTHER,
+		.sched_runtime = 40 * NSEC_PER_MSEC,
+	};
+	int err;
+
+	if (syscall(SYS_sched_setattr, 0, &attr, 0))
+		return KSFT_SKIP;	/* no slice of its own */
+	attr.sched_policy = SCHED_DEADLINE;
+	attr.sched_flags = SCHED_FLAG_KEEP_PARAMS;
+	attr.sched_deadline = PERIOD;
+	attr.sched_period = PERIOD;
+	err = syscall(SYS_sched_setattr, 0, &attr, 0) ? -errno : 0;
+	if (err != -EINVAL) {
+		ksft_print_msg("to SCHED_DEADLINE with SCHED_FLAG_KEEP_PARAMS: %s, not EINVAL\n",
+			       err ? strerror(-err) : "accepted");
+		return KSFT_FAIL;
+	}
+	return KSFT_PASS;
+}
+
+/* cpuset moves, from the main process, outside P */
+
+/* Shared with the processes of a case: atomic in shared memory. */
+static atomic_int *mv_state;
+
+/* mv_state[0] says a child is up (1) or was refused SCHED_DEADLINE (-1). */
+static int child_up(const char *what, int fast)
+{
+	if (wait_for_step(5000, fast ? 100 * NSEC_PER_USEC : NSEC_PER_MSEC, mv_state[0])) {
+		ksft_print_msg("%s: the task never started\n", what);
+		return -1;
+	}
+	if (mv_state[0] != 1) {
+		ksft_print_msg("%s: the task was refused SCHED_DEADLINE\n", what);
+		return -1;
+	}
+	return 0;
+}
+
+/* A process whose one deadline thread does what @mode says, in the root cgroup. */
+enum mv_mode { MV_ASLEEP, MV_THROTTLED, MV_YIELDED, MV_NON_CONTENDING };
+
+static pid_t mover(enum mv_mode mode, uint64_t runtime)
+{
+	pid_t pid = fork_child("a deadline task");
+
+	if (!pid) {
+		if (set_deadline(0, runtime, PERIOD)) {
+			mv_state[0] = -1;
+			_exit(1);
+		}
+		if (mode == MV_ASLEEP) {
+			spin_ns(NSEC_PER_MSEC);
+			*mv_state = 1;
+			for (;;)
+				pause();
+		}
+		if (mode == MV_NON_CONTENDING) {
+			sleep_ns(PERIOD);
+			spin_ns(runtime / 4);
+			*mv_state = 1;
+			for (;;)
+				pause();
+		}
+		if (mode == MV_YIELDED) {
+			*mv_state = 1;
+			for (;;) {
+				spin_ns(NSEC_PER_MSEC / 2);
+				mv_state[1]++;
+				sched_yield();
+			}
+		}
+		*mv_state = 1;
+		for (;;)
+			mv_state[1]++;
+	}
+	return pid;
+}
+
+static int moves(enum mv_mode mode, const char *name)
+{
+	int base_p, base_r, after_p, after_r, ret = KSFT_PASS;
+	pid_t pid;
+
+	base_p = probe(cg_p);
+	base_r = probe(root);
+	mv_state[0] = 0;
+	mv_state[1] = 0;
+	pid = mover(mode, 30 * NSEC_PER_MSEC);
+	if (pid < 0 || child_up(name, mode == MV_NON_CONTENDING)) {
+		reap(pid);
+		return KSFT_FAIL;
+	}
+	if (mode == MV_NON_CONTENDING)
+		sleep_ns(NSEC_PER_MSEC);
+	else
+		sleep_ns(2 * PERIOD);
+	if (enter(cg_p, pid) || enter(root, pid)) {
+		ksft_print_msg("%s: a move refused\n", name);
+		ret = KSFT_FAIL;
+	}
+	if (mode == MV_THROTTLED || mode == MV_YIELDED) {
+		int last = mv_state[1];
+
+		sleep_ns(3 * PERIOD);
+		if (mv_state[1] == last) {
+			ksft_print_msg("%s: moved, never ran again\n", name);
+			ret = KSFT_FAIL;
+		}
+	}
+	reap(pid);
+	sleep_ns(3 * PERIOD);
+	after_p = probe(cg_p);
+	after_r = probe(root);
+	if (ret == KSFT_PASS && (after_p != base_p || after_r != base_r)) {
+		ksft_print_msg("%s: probe tasks admitted, P %d -> %d, the other CPUs %d -> %d\n",
+			       name, base_p, after_p, base_r, after_r);
+		ret = KSFT_FAIL;
+	}
+	return ret;
+}
+
+static int move_refused(void)
+{
+	int base_p, base_r, ret = KSFT_PASS, err;
+	pid_t in_p, pid;
+
+	base_p = probe(cg_p);
+	base_r = probe(root);
+	mv_state[0] = 0;
+	/* 60% in P, then a task of 60% moved in: refused. */
+	in_p = fork_child("a deadline task of P");
+	if (!in_p) {
+		if (enter(cg_p, getpid()) || set_deadline(0, 60 * NSEC_PER_MSEC, PERIOD))
+			_exit(1);
+		mv_state[0] = 1;
+		for (;;)
+			pause();
+	}
+	if (in_p < 0 || child_up("a task of 60% in P", 0)) {
+		reap(in_p);
+		return KSFT_FAIL;
+	}
+	mv_state[0] = 0;
+	pid = mover(MV_ASLEEP, 60 * NSEC_PER_MSEC);
+	if (pid < 0 || child_up("a task of 60% to move into P", 0)) {
+		reap(pid);
+		reap(in_p);
+		return KSFT_FAIL;
+	}
+	err = enter(cg_p, pid);
+	if (err != -EBUSY) {
+		ksft_print_msg("a move beyond P's room: %s, not EBUSY\n",
+			       err ? strerror(-err) : "accepted");
+		ret = KSFT_FAIL;
+	}
+	reap(pid);
+	reap(in_p);
+	sleep_ns(3 * PERIOD);
+	if (ret == KSFT_PASS && (probe(cg_p) != base_p || probe(root) != base_r)) {
+		ksft_print_msg("a refused move changed the free bandwidth\n");
+		ret = KSFT_FAIL;
+	}
+	return ret;
+}
+
+static int move_asleep(void)
+{
+	return moves(MV_ASLEEP, "move_asleep");
+}
+
+static int move_throttled(void)
+{
+	return moves(MV_THROTTLED, "move_throttled");
+}
+
+static int move_non_contending(void)
+{
+	return moves(MV_NON_CONTENDING, "move_non_contending");
+}
+
+/* Deaths, in P */
+
+enum die_mode { DIE_RUNNING, DIE_SWITCHED_OUT, DIE_SHRUNK };
+
+/*
+ * A deadline task of 30% that runs 5ms of a fresh period, its 0-lag time
+ * ahead, and dies there: as it is, or switched to SCHED_OTHER, its
+ * bandwidth then going at that time; or shrunk to 10%, which puts that
+ * time behind it, and the bandwidth goes at its death.
+ */
+static int die_case(enum die_mode mode, const char *what)
+{
+	pid_t pid = fork_child("a task that dies");
+	int status;
+
+	if (!pid) {
+		if (set_deadline(0, 30 * NSEC_PER_MSEC, PERIOD))
+			_exit(1);
+		sleep_ns(PERIOD);
+		spin_ns(5 * NSEC_PER_MSEC);
+		if (mode == DIE_SWITCHED_OUT && set_other(0))
+			_exit(2);
+		if (mode == DIE_SHRUNK && set_deadline(0, 10 * NSEC_PER_MSEC, PERIOD))
+			_exit(3);
+		_exit(0);
+	}
+	if (pid < 0 || waitpid(pid, &status, 0) != pid || !WIFEXITED(status) ||
+	    WEXITSTATUS(status)) {
+		ksft_print_msg("a task that dies %s failed\n", what);
+		return KSFT_FAIL;
+	}
+	return KSFT_PASS;
+}
+
+static int death_running(void)
+{
+	return die_case(DIE_RUNNING, "running");
+}
+
+static int death_switched_out(void)
+{
+	return die_case(DIE_SWITCHED_OUT, "switched out");
+}
+
+static int death_shrunk(void)
+{
+	return die_case(DIE_SHRUNK, "shrunk");
+}
+
+/*
+ * Waits until the spinner's mv_state[1] moves (@moving): it runs; or stops
+ * for 5ms: it is throttled. 0, or -1 after 1s.
+ */
+static int wait_spinner(int moving)
+{
+	uint64_t end = now_ns() + NSEC_PER_SEC;
+	int last = mv_state[1];
+
+	while (now_ns() < end) {
+		sleep_ns(moving ? NSEC_PER_MSEC : 5 * NSEC_PER_MSEC);
+		if (moving ? mv_state[1] != last : mv_state[1] == last)
+			return 0;
+		last = mv_state[1];
+	}
+	return -1;
+}
+
+enum kill_when { KILL_AFTER, KILL_THROTTLED, KILL_RUNNING };
+
+/*
+ * A deadline task of 30% (mover()) killed in the state @mode leaves it in,
+ * @after that, or once it is throttled, or while it runs. The killer
+ * leaves P first, to watch and kill from another CPU without taking the
+ * task's.
+ */
+static int kill_case(enum mv_mode mode, enum kill_when when, uint64_t after, const char *what)
+{
+	int ret = KSFT_PASS;
+	pid_t pid;
+
+	mv_state[0] = 0;
+	mv_state[1] = 0;
+	pid = mover(mode, 30 * NSEC_PER_MSEC);
+	if (pid < 0) {
+		ret = KSFT_FAIL;
+		goto out;
+	}
+	if (enter(root, getpid())) {
+		ksft_print_msg("killed %s: the killer cannot leave P\n", what);
+		ret = KSFT_FAIL;
+		goto out;
+	}
+	if (child_up(what, 1)) {
+		ret = KSFT_FAIL;
+	} else if (when != KILL_AFTER && wait_spinner(when == KILL_RUNNING)) {
+		ksft_print_msg("killed %s: never %s\n", what,
+			       when == KILL_RUNNING ? "ran" : "throttled");
+		ret = KSFT_FAIL;
+	} else {
+		sleep_ns(after);
+	}
+out:
+	reap(pid);
+	return ret;
+}
+
+static int death_killed_asleep(void)
+{
+	return kill_case(MV_ASLEEP, KILL_AFTER, 2 * PERIOD, "asleep");
+}
+
+static int death_killed_non_contending(void)
+{
+	return kill_case(MV_NON_CONTENDING, KILL_AFTER, 0, "before its 0-lag time");
+}
+
+static int death_killed_throttled(void)
+{
+	return kill_case(MV_THROTTLED, KILL_THROTTLED, 0, "throttled");
+}
+
+static int death_killed_running(void)
+{
+	return kill_case(MV_THROTTLED, KILL_RUNNING, 0, "running");
+}
+
+/*
+ * A robust priority inheritance lock that processes share: mv_state[0]
+ * tells its owner's state, mv_state[2] its waiter's.
+ */
+static pthread_mutex_t *shm_lock;
+
+/* 0, or -1 where such a mutex is not to be had. */
+static int shm_lock_init(void)
+{
+	pthread_mutexattr_t a;
+	int err;
+
+	err = pthread_mutexattr_init(&a);
+	if (!err)
+		err = pthread_mutexattr_setpshared(&a, PTHREAD_PROCESS_SHARED);
+	if (!err)
+		err = pthread_mutexattr_setprotocol(&a, PTHREAD_PRIO_INHERIT);
+	if (!err)
+		err = pthread_mutexattr_setrobust(&a, PTHREAD_MUTEX_ROBUST);
+	if (!err)
+		err = pthread_mutex_init(shm_lock, &a);
+	if (err) {
+		ksft_print_msg("no shared priority inheritance mutex: %s\n", strerror(err));
+		return -1;
+	}
+	mv_state[0] = 0;
+	mv_state[2] = 0;
+	return 0;
+}
+
+/* Takes the lock, as a deadline task of 30% if @dl, and sleeps with it. */
+static pid_t lock_owner(int dl)
+{
+	pid_t pid = fork_child("the owner of the lock");
+
+	if (!pid) {
+		if ((dl && set_deadline(0, 30 * NSEC_PER_MSEC, PERIOD)) ||
+		    pthread_mutex_lock(shm_lock)) {
+			mv_state[0] = -1;
+			_exit(1);
+		}
+		mv_state[0] = 1;
+		for (;;)
+			pause();
+	}
+	return pid;
+}
+
+/* A deadline task of 5ms every 50ms that waits for the lock: 2 once it got it. */
+static pid_t lock_waiter(void)
+{
+	pid_t pid = fork_child("a waiter of the lock");
+
+	if (!pid) {
+		int err;
+
+		if (set_deadline(0, 5 * NSEC_PER_MSEC, 50 * NSEC_PER_MSEC)) {
+			mv_state[2] = -1;
+			_exit(1);
+		}
+		mv_state[2] = 1;
+		err = pthread_mutex_lock(shm_lock);
+		if (err == EOWNERDEAD)
+			err = pthread_mutex_consistent(shm_lock);
+		if (!err)
+			pthread_mutex_unlock(shm_lock);
+		mv_state[2] = err ? -2 : 2;
+		for (;;)
+			pause();
+	}
+	return pid;
+}
+
+/* @var reaches @want within 1s: 0, or -1. */
+static int wait_state(atomic_int *var, int want)
+{
+	uint64_t end = now_ns() + NSEC_PER_SEC;
+
+	while (now_ns() < end) {
+		if (*var == want)
+			return 0;
+		sleep_ns(NSEC_PER_MSEC);
+	}
+	return -1;
+}
+
+/*
+ * The owner sleeps with the lock, a deadline task if @dl_owner, and the
+ * waiter boosts it; then @kill_owner, or the waiter, dies. A killed owner
+ * does not die boosted: its exit releases its priority inheritance
+ * futexes first (futex_exit_release()), which deboosts it.
+ */
+static int pi_death(int dl_owner, int kill_owner, const char *what)
+{
+	int ret = KSFT_PASS;
+	pid_t owner, waiter = -1;
+
+	if (shm_lock_init())
+		return KSFT_SKIP;
+	owner = lock_owner(dl_owner);
+	if (owner < 0)
+		return KSFT_FAIL;
+	if (wait_state(&mv_state[0], 1)) {
+		ksft_print_msg("%s: no owner\n", what);
+		ret = KSFT_FAIL;
+		goto out;
+	}
+	waiter = lock_waiter();
+	if (waiter < 0) {
+		ret = KSFT_FAIL;
+		goto out;
+	}
+	if (wait_state(&mv_state[2], 1)) {
+		ksft_print_msg("%s: no waiter\n", what);
+		ret = KSFT_FAIL;
+		goto out;
+	}
+	sleep_ns(50 * NSEC_PER_MSEC);	/* blocked, boosting the owner */
+	if (kill_owner) {
+		reap(owner);
+		owner = -1;
+		if (wait_state(&mv_state[2], 2)) {
+			ksft_print_msg("%s: the waiter did not get the lock\n", what);
+			ret = KSFT_FAIL;
+		}
+	} else {
+		reap(waiter);
+		waiter = -1;
+		sleep_ns(50 * NSEC_PER_MSEC);	/* the owner deboosted asleep */
+	}
+out:
+	reap(waiter);
+	reap(owner);
+	return ret;
+}
+
+static int death_pi_waiter(void)
+{
+	return pi_death(0, 0, "a waiter killed");
+}
+
+static int death_pi_owner(void)
+{
+	return pi_death(0, 1, "a boosted owner killed");
+}
+
+static int death_pi_deadline_owner(void)
+{
+	return pi_death(1, 1, "a boosted deadline owner killed");
+}
+
+/* Deadline threads of one process, asleep, throttled and running, killed at once. */
+static void *group_thread(void *arg)
+{
+	long kind = (long)arg;
+
+	if (set_deadline(0, 10 * NSEC_PER_MSEC, PERIOD)) {
+		mv_state[0] = -1000;
+		return NULL;
+	}
+	spin_ns(NSEC_PER_MSEC);
+	mv_state[0]++;
+	if (!kind)
+		for (;;)
+			pause();
+	for (;;)
+		;
+	return NULL;
+}
+
+static int death_group(void)
+{
+	pid_t pid;
+
+	mv_state[0] = 0;
+	pid = fork_child("a group of deadline threads");
+	if (pid < 0)
+		return KSFT_FAIL;
+	if (!pid) {
+		pthread_t t;
+		long i;
+
+		for (i = 0; i < 3; i++)
+			if (pthread_create(&t, NULL, group_thread, (void *)i))
+				mv_state[0] = -1000;
+		for (;;)
+			pause();
+	}
+	if (wait_for(5000, mv_state[0] < 0 || mv_state[0] == 3))
+		ksft_print_msg("only %d threads of the group started\n", (int)mv_state[0]);
+	sleep_ns(PERIOD / 2);
+	reap(pid);
+	if (mv_state[0] != 3) {
+		ksft_print_msg("a thread of the group refused SCHED_DEADLINE\n");
+		return KSFT_FAIL;
+	}
+	return KSFT_PASS;
+}
+
+/* sched_yield() */
+
+static atomic_int y_rounds;	/* the yields of the yielder */
+
+/*
+ * A deadline task of 30% that yields half a millisecond into every
+ * period: it spends nearly all of its time throttled by sched_yield(),
+ * with runtime left, so its 0-lag time is a few milliseconds away and the
+ * inactive timer that releases its bandwidth is armed for that long.
+ * @t_state is 2 while it is in the yield.
+ */
+static void *yielder(void *arg)
+{
+	t_tid = gettid_();
+	if (set_deadline(0, 30 * NSEC_PER_MSEC, PERIOD)) {
+		t_state = -1;
+		return (void *)1;
+	}
+	t_state = 1;
+	while (!spin_stop) {
+		spin_ns(NSEC_PER_MSEC / 2);
+		y_rounds++;
+		t_state = 2;
+		sched_yield();
+		t_state = 1;
+	}
+	return NULL;
+}
+
+static int start_yielder(pthread_t *t)
+{
+	t_state = 0;
+	spin_stop = 0;
+	y_rounds = 0;
+	if (pthread_create(t, NULL, yielder, NULL)) {
+		ksft_print_msg("the yielder thread could not start\n");
+		return -1;
+	}
+	if (!wait_for(5000, t_state) && t_state > 0)
+		return 0;
+	join(*t);
+	return -1;
+}
+
+/*
+ * A task switched to SCHED_OTHER while it is throttled by sched_yield():
+ * its bandwidth comes back, and it runs again.
+ */
+static int yield_switched_out(void)
+{
+	int base, ret = KSFT_PASS;
+	pthread_t t;
+
+	base = probe(NULL);
+	if (base < 3)
+		return KSFT_SKIP;	/* no room for a task of 30% */
+	if (start_yielder(&t))
+		return KSFT_FAIL;
+	if (wait_throttled(t) || t_state != 2) {
+		ksft_print_msg("the task never yielded\n");
+		ret = KSFT_FAIL;
+	} else if (set_other(t_tid)) {
+		ret = KSFT_FAIL;
+	} else {
+		int last = y_rounds;
+
+		sleep_ns(2 * PERIOD);
+		if (y_rounds == last) {
+			ksft_print_msg("yielded, then switched out: never ran again\n");
+			ret = KSFT_FAIL;
+		}
+	}
+	stop_spinner(t);
+	sleep_ns(3 * PERIOD);		/* its 0-lag time */
+	if (ret == KSFT_PASS && admits(base, "yielded, then switched out"))
+		ret = KSFT_FAIL;
+	return ret;
+}
+
+static int yield_moved(void)
+{
+	return moves(MV_YIELDED, "yield_moved");
+}
+
+/* A task killed while it is throttled by sched_yield(). */
+static int yield_killed(void)
+{
+	pid_t pid;
+
+	mv_state[0] = 0;
+	pid = fork_child("a task that yields");
+	if (!pid) {
+		if (set_deadline(0, 30 * NSEC_PER_MSEC, PERIOD)) {
+			mv_state[0] = -1;
+			_exit(1);
+		}
+		mv_state[0] = 1;
+		for (;;) {
+			spin_ns(NSEC_PER_MSEC / 2);
+			sched_yield();
+		}
+	}
+	if (pid < 0)
+		return KSFT_FAIL;
+	if (child_up("a task that yields", 0)) {
+		reap(pid);
+		return KSFT_FAIL;
+	}
+	sleep_ns(2 * PERIOD);
+	reap(pid);
+	return KSFT_PASS;
+}
+
+/* SCHED_FLAG_DL_OVERRUN */
+
+static atomic_int got_xcpu;
+
+static void catch_xcpu(int sig)
+{
+	got_xcpu = 1;
+}
+
+/* A deadline task of 10% with SCHED_FLAG_DL_OVERRUN that runs past it. */
+static void *overruns(void *arg)
+{
+	t_tid = gettid_();
+	if (set_deadline_flags(0, 10 * NSEC_PER_MSEC, PERIOD, SCHED_FLAG_DL_OVERRUN)) {
+		t_state = -1;
+		return (void *)1;
+	}
+	t_state = 1;
+	spin_ns(15 * NSEC_PER_MSEC);
+	while (!spin_stop)
+		sleep_ns(10 * NSEC_PER_MSEC);
+	return NULL;
+}
+
+/*
+ * The thread group of a task with SCHED_FLAG_DL_OVERRUN that overruns its
+ * runtime gets SIGXCPU. Caught here: the overrun leaves the task's
+ * bandwidth reserved, and it comes back when the task leaves
+ * SCHED_DEADLINE.
+ */
+static int overrun_caught(void)
+{
+	int base, ret = KSFT_PASS;
+	uint64_t end;
+	pthread_t t;
+
+	if (signal(SIGXCPU, catch_xcpu) == SIG_ERR)
+		return KSFT_FAIL;
+	base = probe(NULL);
+	if (base < 1)
+		return KSFT_SKIP;
+	got_xcpu = 0;
+	t_state = 0;
+	spin_stop = 0;
+	if (pthread_create(&t, NULL, overruns, NULL))
+		return KSFT_FAIL;
+	while (!t_state)
+		sleep_ns(NSEC_PER_MSEC);
+	end = now_ns() + 2 * NSEC_PER_SEC;
+	while (!got_xcpu && now_ns() < end)
+		sleep_ns(5 * NSEC_PER_MSEC);
+	if (t_state != 1) {
+		ret = KSFT_FAIL;
+	} else if (!got_xcpu) {
+		ksft_print_msg("it overran its runtime, no SIGXCPU in 2s\n");
+		ret = KSFT_FAIL;
+	} else if (admits(base - 1, "an overrun told")) {
+		ret = KSFT_FAIL;	/* the overrun gave its 10% back */
+	}
+	stop_spinner(t);
+	sleep_ns(3 * PERIOD);		/* its 0-lag time */
+	if (ret == KSFT_PASS && admits(base, "after an overrun was told"))
+		ret = KSFT_FAIL;
+	return ret;
+}
+
+/* The deadline threads of overrun_group_death(). */
+static void *og_thread(void *arg)
+{
+	switch ((int)(long)arg) {
+	case 0:		/* overruns its runtime: SIGXCPU to the group */
+		if (set_deadline_flags(0, 10 * NSEC_PER_MSEC, PERIOD,
+				       SCHED_FLAG_DL_OVERRUN))
+			_exit(1);
+		spin_ns(30 * NSEC_PER_MSEC);
+		break;
+	case 1:		/* asleep, its 0-lag time past */
+		if (set_deadline(0, 20 * NSEC_PER_MSEC, PERIOD))
+			_exit(1);
+		spin_ns(NSEC_PER_MSEC);
+		break;
+	case 2:		/* asleep, mostly before its 0-lag time */
+		if (set_deadline(0, 15 * NSEC_PER_MSEC, PERIOD))
+			_exit(1);
+		for (;;) {
+			spin_ns(3 * NSEC_PER_MSEC);
+			sleep_ns(22 * NSEC_PER_MSEC);
+		}
+	}
+	for (;;)
+		pause();
+}
+
+/*
+ * The SIGXCPU of an overrun kills the whole thread group: the bandwidth
+ * of its three deadline threads comes back.
+ */
+static int overrun_group_death(void)
+{
+	pid_t pid = fork_child("a group of deadline threads");
+	int i, status;
+
+	if (!pid) {
+		pthread_t t;
+
+		for (i = 0; i < 3; i++)
+			if (pthread_create(&t, NULL, og_thread, (void *)(long)i))
+				_exit(1);
+		for (;;)
+			pause();
+	}
+	if (pid < 0)
+		return KSFT_FAIL;
+	for (i = 0; i < 300; i++) {
+		if (waitpid(pid, &status, WNOHANG) == pid)
+			break;
+		sleep_ns(10 * NSEC_PER_MSEC);
+	}
+	if (i == 300) {
+		reap(pid);
+		ksft_print_msg("an overrun of 10ms every 100ms: no SIGXCPU in 3s\n");
+		return KSFT_FAIL;
+	}
+	if (WIFEXITED(status)) {
+		ksft_print_msg("a thread of the group was refused SCHED_DEADLINE\n");
+		return KSFT_SKIP;
+	}
+	if (!WIFSIGNALED(status) || WTERMSIG(status) != SIGXCPU) {
+		ksft_print_msg("the group of an overrun died of signal %d, not SIGXCPU\n",
+			       WIFSIGNALED(status) ? WTERMSIG(status) : 0);
+		return KSFT_FAIL;
+	}
+	return KSFT_PASS;
+}
+
+/* SCHED_FLAG_RECLAIM */
+
+#define RECLAIM_MIN	40	/* % of a CPU a reclaiming task of 10% gets */
+#define PLAIN_MAX	25	/* % one without the flag gets */
+#define SHARE_SLACK	15	/* % two measures of the same may differ by */
+#define SHARE_NS	(400 * NSEC_PER_MSEC)
+
+/*
+ * A deadline task with SCHED_FLAG_RECLAIM runs past its runtime, taking
+ * the bandwidth of its root domain that no deadline task uses: of a CPU
+ * of its own, a task of 10% every 100ms gets most of it, where one
+ * without the flag gets its 10%.
+ */
+static int reclaim_runs(void)
+{
+	int plain, grub, ret = KSFT_PASS;
+	pthread_t t;
+
+	if (start_spinner(&t, 10 * NSEC_PER_MSEC, 0))
+		return KSFT_SKIP;	/* no room for a task of 10% */
+	plain = share_of(t, SHARE_NS);
+	stop_spinner(t);
+	if (start_spinner(&t, 10 * NSEC_PER_MSEC, SCHED_FLAG_RECLAIM))
+		return KSFT_FAIL;
+	grub = share_of(t, SHARE_NS);
+	stop_spinner(t);
+	if (plain > PLAIN_MAX || grub < RECLAIM_MIN) {
+		ksft_print_msg("of a CPU, a task of 10%% got %d%%, with SCHED_FLAG_RECLAIM %d%%\n",
+			       plain, grub);
+		ret = KSFT_FAIL;
+	}
+	return ret;
+}
+
+/*
+ * A reclaiming task switched out of SCHED_DEADLINE before its 0-lag time
+ * and back, which leaves its bandwidth standing until the inactive timer
+ * releases it: what it reclaims afterwards is what it reclaimed before.
+ */
+static int reclaim_switched(void)
+{
+	int before, after = 0, r, ret = KSFT_PASS;
+	pthread_t t;
+
+	if (start_spinner(&t, 10 * NSEC_PER_MSEC, SCHED_FLAG_RECLAIM))
+		return KSFT_SKIP;	/* no room for a task of 10% */
+	before = share_of(t, SHARE_NS);
+	for (r = 0; r < 4; r++) {
+		if (set_other(t_tid)) {
+			ret = KSFT_FAIL;
+			break;
+		}
+		if (r & 1)
+			sleep_ns(5 * NSEC_PER_MSEC);
+		if (set_deadline_flags(t_tid, 10 * NSEC_PER_MSEC, PERIOD,
+				       SCHED_FLAG_RECLAIM)) {
+			ksft_print_msg("round %d of 4: back to SCHED_DEADLINE refused\n",
+				       r + 1);
+			ret = KSFT_FAIL;
+			break;
+		}
+		sleep_ns(PERIOD);
+	}
+	if (ret == KSFT_PASS)
+		after = share_of(t, SHARE_NS);
+	stop_spinner(t);
+	if (ret == KSFT_PASS &&
+	    (after < before - SHARE_SLACK || after > before + SHARE_SLACK)) {
+		ksft_print_msg("reclaiming: %d%% of a CPU, %d%% after 4 round trips\n",
+			       before, after);
+		ret = KSFT_FAIL;
+	}
+	return ret;
+}
+
+/*
+ * A reclaiming deadline task of 10% that spins, publishing the CPU time
+ * it has used in milliseconds, and idles while mv_state[2] is set. The
+ * moves happen then: a cpuset move waits for an RCU grace period, which
+ * a task that reclaims a whole CPU of its own keeps from ending where
+ * RCU runs in kthreads of its own (PREEMPT_RT).
+ */
+static pid_t reclaim_mover(void)
+{
+	pid_t pid = fork_child("a reclaiming task");
+
+	if (!pid) {
+		if (set_deadline_flags(0, 10 * NSEC_PER_MSEC, PERIOD,
+				       SCHED_FLAG_RECLAIM)) {
+			mv_state[0] = -1;
+			_exit(1);
+		}
+		mv_state[0] = 1;
+		for (;;) {
+			if (mv_state[2]) {
+				sleep_ns(10 * NSEC_PER_MSEC);
+				continue;
+			}
+			spin_ns(NSEC_PER_MSEC);
+			mv_state[1] = (int)(thread_time_ns() / NSEC_PER_MSEC);
+		}
+	}
+	return pid;
+}
+
+/* Moves the mover to @cg, idle: 0, or -1. */
+static int move_idle(const char *cg, pid_t pid)
+{
+	int err;
+
+	mv_state[2] = 1;
+	sleep_ns(20 * NSEC_PER_MSEC);	/* it stops spinning */
+	err = enter(cg, pid);
+	mv_state[2] = 0;
+	return err;
+}
+
+/* The share of a CPU, in percent, the mover uses over the next @ns. */
+static int mover_share(uint64_t ns)
+{
+	uint64_t wall = now_ns();
+	int cpu = mv_state[1];
+
+	sleep_ns(ns);
+	cpu = mv_state[1] - cpu;
+	wall = now_ns() - wall;
+	return (int)(100 * (uint64_t)cpu * NSEC_PER_MSEC / wall);
+}
+
+/*
+ * A reclaiming task moved into P and back, then into P again: what it
+ * reclaims of P's CPU is what it reclaimed there before, and the free
+ * bandwidth of both root domains is the one it found.
+ */
+static int reclaim_moved(void)
+{
+	int base_p, base_r, in_p, again = 0, ret = KSFT_PASS;
+	pid_t pid;
+
+	base_p = probe(cg_p);
+	base_r = probe(root);
+	mv_state[0] = 0;
+	mv_state[1] = 0;
+	mv_state[2] = 1;		/* idle until it is in P */
+	pid = reclaim_mover();
+	if (pid < 0)
+		return KSFT_FAIL;
+	if (child_up("a reclaiming task", 0) || move_idle(cg_p, pid)) {
+		mv_state[2] = 1;
+		reap(pid);
+		return KSFT_FAIL;
+	}
+	sleep_ns(2 * PERIOD);
+	in_p = mover_share(SHARE_NS);
+	if (move_idle(root, pid) || move_idle(cg_p, pid)) {
+		ksft_print_msg("a move of a reclaiming task refused\n");
+		ret = KSFT_FAIL;
+	} else {
+		sleep_ns(2 * PERIOD);
+		again = mover_share(SHARE_NS);
+		if (in_p < RECLAIM_MIN || again < in_p - SHARE_SLACK ||
+		    again > in_p + SHARE_SLACK) {
+			ksft_print_msg("reclaiming: %d%% of P's CPU, %d%% after a move\n",
+				       in_p, again);
+			ret = KSFT_FAIL;
+		}
+	}
+	mv_state[2] = 1;
+	reap(pid);
+	sleep_ns(3 * PERIOD);
+	if (ret == KSFT_PASS && (probe(cg_p) != base_p || probe(root) != base_r)) {
+		ksft_print_msg("a reclaiming task moved: the free bandwidth changed\n");
+		ret = KSFT_FAIL;
+	}
+	return ret;
+}
+
+/* Deadline servers */
+
+#define SERVER_RUNTIME	(100 * NSEC_PER_MSEC)	/* 10%, where the cases start from */
+#define SERVER_PERIOD	(1000 * NSEC_PER_MSEC)
+
+static const char server_dir[] = "/sys/kernel/debug/sched/fair_server";
+static uint64_t *server_found;	/* runtime and period of each CPU's fair server */
+
+static int server_get(int cpu, const char *name, uint64_t *val)
+{
+	char path[96], buf[32];
+
+	snprintf(path, sizeof(path), "%s/cpu%d/%s", server_dir, cpu, name);
+	if (read_file(path, buf, sizeof(buf)))
+		return -1;
+	*val = strtoull(buf, NULL, 10);
+	return 0;
+}
+
+static int server_put(int cpu, const char *name, uint64_t val)
+{
+	char dir[96], buf[32];
+
+	snprintf(dir, sizeof(dir), "%s/cpu%d", server_dir, cpu);
+	snprintf(buf, sizeof(buf), "%llu", (unsigned long long)val);
+	return write_file(dir, name, buf);
+}
+
+/* The fair server of @cpu runs @runtime every @period: 0, or -errno. */
+static int server_set(int cpu, uint64_t runtime, uint64_t period)
+{
+	uint64_t cur;
+	int err;
+
+	if (!server_found || server_get(cpu, "period", &cur))
+		return -ENOENT;
+	/* Each write keeps the runtime within the period. */
+	if (runtime <= cur) {
+		err = server_put(cpu, "runtime", runtime);
+		return err ? err : server_put(cpu, "period", period);
+	}
+	err = server_put(cpu, "period", period);
+	return err ? err : server_put(cpu, "runtime", runtime);
+}
+
+/* The fair servers as the test finds them, or none without debugfs. */
+static void server_init(void)
+{
+	int cpu;
+
+	server_found = calloc(2 * ncpus, sizeof(*server_found));
+	for (cpu = 0; server_found && cpu < ncpus; cpu++) {
+		if (server_get(cpu, "runtime", &server_found[2 * cpu]) ||
+		    server_get(cpu, "period", &server_found[2 * cpu + 1])) {
+			free(server_found);
+			server_found = NULL;
+			ksft_print_msg("no fair server in debugfs: server cases skipped\n");
+		}
+	}
+}
+
+/* Puts the fair servers back as the test found them. */
+static void server_restore(void)
+{
+	uint64_t runtime, period;
+	int cpu;
+
+	for (cpu = 0; server_found && cpu < ncpus; cpu++) {
+		int err;
+
+		if (server_get(cpu, "runtime", &runtime) || server_get(cpu, "period", &period))
+			continue;
+		if (runtime == server_found[2 * cpu] && period == server_found[2 * cpu + 1])
+			continue;
+		err = server_set(cpu, server_found[2 * cpu], server_found[2 * cpu + 1]);
+		if (err)
+			ksft_print_msg("the fair server of CPU %d stays changed: %s\n",
+				       cpu, strerror(-err));
+	}
+}
+
+/* Deadline threads of 10% every 100ms that sleep until released. */
+static pthread_t *held;
+static int nheld, held_err;
+static sem_t held_up, held_go;
+
+static void *holder(void *arg)
+{
+	int err = set_deadline(0, PROBE_RUNTIME, PROBE_PERIOD);
+
+	held_err = err;
+	if (sem_post(&held_up))
+		ksft_print_msg("sem_post: %s\n", strerror(errno));
+	if (!err)
+		sem_wait_sig(&held_go);
+	return NULL;
+}
+
+/* Starts @n more holders: 0 once they are all admitted, or -1. */
+static int hold(int n)
+{
+	int max = 16 * ncpus + 16;
+	pthread_attr_t a;
+
+	if (!held) {
+		held = calloc(max, sizeof(*held));
+		if (!held || sem_init(&held_up, 0, 0) || sem_init(&held_go, 0, 0)) {
+			ksft_print_msg("the holders cannot be set up\n");
+			return -1;
+		}
+	}
+	if (pthread_attr_init(&a) || pthread_attr_setstacksize(&a, 64 * 1024)) {
+		ksft_print_msg("pthread_attr: %s\n", strerror(errno));
+		return -1;
+	}
+	for (; n > 0; n--) {
+		if (nheld == max || pthread_create(&held[nheld], &a, holder, NULL)) {
+			ksft_print_msg("a holder thread could not start\n");
+			return -1;
+		}
+		if (sem_wait_for(&held_up, 10000)) {
+			ksft_print_msg("a holder did not answer\n");
+			return -1;
+		}
+		if (held_err) {
+			join(held[nheld]);
+			return -1;
+		}
+		nheld++;
+	}
+	return 0;
+}
+
+static void release_held(void)
+{
+	int i;
+
+	for (i = 0; i < nheld; i++)
+		if (sem_post(&held_go))
+			ksft_print_msg("sem_post: %s\n", strerror(errno));
+	for (i = 0; i < nheld; i++)
+		join(held[i]);
+	nheld = 0;
+	sleep_ns(3 * PERIOD);	/* their 0-lag times */
+}
+
+/*
+ * The fair server of P's CPU, changed at runtime, takes from P's root
+ * domain what deadline tasks then cannot: from 10% every second, P admits
+ * two probe tasks fewer with 30%, one fewer with 100ms every 500ms, one
+ * more with the server off. A change P has no room for is refused.
+ */
+static int server_params(void)
+{
+	static const struct {
+		uint64_t runtime, period;
+		int more;
+		const char *what;
+	} step[] = {
+		{ 3 * SERVER_RUNTIME, SERVER_PERIOD, -2, "a fair server of 30%" },
+		{ SERVER_RUNTIME, SERVER_PERIOD / 2, -1, "a fair server of 100ms every 500ms" },
+		{ 0, SERVER_PERIOD, 1, "the fair server off" },
+		{ SERVER_RUNTIME, SERVER_PERIOD, 0, "the fair server back to 10%" },
+	};
+	int cpu = ncpus - 1, base, err, i, ret = KSFT_PASS;
+	uint64_t runtime;
+
+	if (server_set(cpu, SERVER_RUNTIME, SERVER_PERIOD))
+		return KSFT_SKIP;
+	base = probe(NULL);
+	if (base < 2)
+		return KSFT_SKIP;
+	for (i = 0; i < (int)ARRAY_SIZE(step); i++) {
+		err = server_set(cpu, step[i].runtime, step[i].period);
+		if (err) {
+			ksft_print_msg("%s: %s\n", step[i].what, strerror(-err));
+			return KSFT_FAIL;
+		}
+		if (admits(base + step[i].more, step[i].what))
+			return KSFT_FAIL;
+	}
+	/*
+	 * With base - 1 probe tasks held, P has room for 10% more and less
+	 * than 20%: the server may grow to 20%, not to 30%.
+	 */
+	if (hold(base - 1)) {
+		release_held();
+		return KSFT_FAIL;
+	}
+	err = server_put(cpu, "runtime", 2 * SERVER_RUNTIME);
+	if (err) {
+		ksft_print_msg("a fair server of 20%% with room for it: %s\n", strerror(-err));
+		ret = KSFT_FAIL;
+	} else {
+		err = server_put(cpu, "runtime", 3 * SERVER_RUNTIME);
+		if (err != -EBUSY) {
+			ksft_print_msg("a fair server of 30%% with no room for it: %s, not EBUSY\n",
+				       err ? strerror(-err) : "accepted");
+			ret = KSFT_FAIL;
+		} else if (server_get(cpu, "runtime", &runtime) ||
+			   runtime != 2 * SERVER_RUNTIME) {
+			ksft_print_msg("a refused change changed the fair server\n");
+			ret = KSFT_FAIL;
+		}
+	}
+	if (server_set(cpu, SERVER_RUNTIME, SERVER_PERIOD))
+		ret = KSFT_FAIL;
+	release_held();
+	if (ret == KSFT_PASS && admits(base, "after a refused change of the fair server"))
+		ret = KSFT_FAIL;
+	return ret;
+}
+
+/*
+ * The rebuilds of the root domains' accounting put the fair servers'
+ * bandwidth back as it is set, not as it was at boot: P's own, when a
+ * partition root Q is made and unmade beside it; that of the other CPUs,
+ * when P is unmade and its CPU joins them with its server; P's again,
+ * when it is made anew.
+ */
+static int server_rebuilds(void)
+{
+	int cpu = ncpus - 1, base, n10, n30;
+
+	if (server_set(cpu, SERVER_RUNTIME, SERVER_PERIOD))
+		return KSFT_SKIP;
+	base = probe(cg_p);
+	if (base < 2)
+		return KSFT_SKIP;
+	if (server_set(cpu, 3 * SERVER_RUNTIME, SERVER_PERIOD) ||
+	    admits_in(cg_p, base - 2, "P, a fair server of 30%"))
+		return KSFT_FAIL;
+	if (make_partition(cg_q, ncpus - 2)) {
+		remove_partition(cg_q);
+		ksft_print_msg("no partition root Q beside P\n");
+		return KSFT_FAIL;
+	}
+	if (admits_in(cg_p, base - 2, "P, Q made beside it")) {
+		remove_partition(cg_q);
+		return KSFT_FAIL;
+	}
+	remove_partition(cg_q);
+	if (admits_in(cg_p, base - 2, "P, Q unmade beside it"))
+		return KSFT_FAIL;
+	/* P unmade: its CPU and its server join the root domain of the others. */
+	remove_p();
+	n30 = probe(root);
+	if (server_set(cpu, SERVER_RUNTIME, SERVER_PERIOD))
+		return KSFT_FAIL;
+	n10 = probe(root);
+	if (n10 != n30 + 2) {
+		ksft_print_msg("P unmade: %d probe tasks, its CPU's server at 30%%, %d at 10%%\n",
+			       n30, n10);
+		return KSFT_FAIL;
+	}
+	if (server_set(cpu, 3 * SERVER_RUNTIME, SERVER_PERIOD) || make_p()) {
+		ksft_print_msg("P made anew, a fair server of 30%%: failed\n");
+		return KSFT_FAIL;
+	}
+	if (admits_in(cg_p, base - 2, "P made anew, a fair server of 30%") ||
+	    server_set(cpu, SERVER_RUNTIME, SERVER_PERIOD) ||
+	    admits_in(cg_p, base, "P, the fair server back to 10%"))
+		return KSFT_FAIL;
+	return KSFT_PASS;
+}
+
+/* Waits for @f to be set: a futex in shared memory. */
+static void wait_set(atomic_int *f)
+{
+	while (!*f)
+		syscall(SYS_futex, f, FUTEX_WAIT, 0, NULL, NULL, 0);
+}
+
+static void set_flag(atomic_int *f, int val)
+{
+	*f = val;
+	syscall(SYS_futex, f, FUTEX_WAKE, INT_MAX, NULL, NULL, 0);
+}
+
+/*
+ * A process of P that spins while mv_state[4 + @rt] is set, and sleeps
+ * otherwise: a fair task, or a real-time one (@rt) that leaves P's CPU
+ * for a millisecond every 50ms to the real-time kthreads of that CPU
+ * (PREEMPT_RT runs RCU and the timers there).
+ */
+static pid_t server_client(int rt)
+{
+	pid_t pid = fork_child(rt ? "a real-time task of P" : "a fair task of P");
+
+	if (!pid) {
+		struct sched_param sp = { .sched_priority = 1 };
+
+		if (enter(cg_p, getpid()) ||
+		    (rt && sched_setscheduler(0, SCHED_FIFO, &sp)))
+			_exit(1);
+		mv_state[0]++;
+		for (;;) {
+			wait_set(&mv_state[4 + rt]);
+			spin_ns(rt ? 50 * NSEC_PER_MSEC : NSEC_PER_MSEC);
+			if (rt)
+				sleep_ns(NSEC_PER_MSEC);
+		}
+	}
+	return pid;
+}
+
+/* The share of a CPU, in percent, that process @pid uses over @ns. */
+static int proc_share(pid_t pid, uint64_t ns)
+{
+	struct timespec t0, t1;
+	uint64_t wall = now_ns();
+	clockid_t c;
+
+	if (clock_getcpuclockid(pid, &c) || clock_gettime(c, &t0))
+		return -1;
+	sleep_ns(ns);
+	if (clock_gettime(c, &t1))
+		return -1;
+	wall = now_ns() - wall;
+	return (int)(100 * ((t1.tv_sec - t0.tv_sec) * NSEC_PER_SEC +
+			    t1.tv_nsec - t0.tv_nsec) / wall);
+}
+
+#define STARVED_SLACK	8	/* % a starved fair task's share may be off its server's */
+
+/*
+ * The fair server of P's CPU changed from outside P in the states a change
+ * can find it in: stopped, deferred while a fair task of P runs, deferred
+ * while a real-time task starves it, serving it, deferred again after
+ * serving it, and deferred while the CPU idles. Each change starts a
+ * period of the server, which defers serving a starved task to its
+ * zero-laxity time, 0.7s in at 30% and 0.9s in at 10%. Afterwards, the
+ * starved task gets the server's bandwidth as set last, and P's free
+ * bandwidth is as it was. (Throttled after serving, the server is
+ * deferred anew at once: the last of the served task's runtime is charged
+ * to it as running in the background. Its idle wait ends in the timer
+ * callback that starts it, on a CPU with no tick in idle.)
+ */
+static int server_states(void)
+{
+	static const struct {
+		int fair, rt, ms;
+	} step[] = {
+		{ 0, 0, 1500 },	/* stopped: nothing of P ran for a period of the server */
+		{ 1, 0, 300 },	/* deferred while the fair task runs */
+		{ 1, 1, 300 },	/* deferred, the fair task starved: before 0.9s */
+		{ 1, 1, 800 },	/* serving it: after 0.7s */
+		{ 1, 1, 1500 },	/* deferred again: served from 0.9s to 1s */
+		{ 0, 0, 600 },	/* deferred while the CPU idles */
+	};
+	int cpu = ncpus - 1, base, i, s30 = -1, s10 = -1, ret = KSFT_PASS;
+	pid_t fair, rt;
+
+	if (server_set(cpu, SERVER_RUNTIME, SERVER_PERIOD))
+		return KSFT_SKIP;
+	base = probe(cg_p);
+	if (base <= 0)
+		return KSFT_SKIP;
+	mv_state[0] = 0;
+	set_flag(&mv_state[4], 0);
+	set_flag(&mv_state[5], 0);
+	fair = server_client(0);
+	rt = server_client(1);
+	if (fair < 0 || rt < 0 || wait_for(5000, mv_state[0] >= 2)) {
+		if (fair >= 0 && rt >= 0)
+			ksft_print_msg("a fair or real-time task of P could not start\n");
+		ret = KSFT_FAIL;
+	}
+	/* Even steps set the server to 30%, odd ones back to 10%: its runtime alone. */
+	for (i = 0; i < (int)ARRAY_SIZE(step) && ret == KSFT_PASS; i++) {
+		set_flag(&mv_state[4], step[i].fair);
+		set_flag(&mv_state[5], step[i].rt);
+		sleep_ns(step[i].ms * NSEC_PER_MSEC);
+		if (server_put(cpu, "runtime", (i & 1 ? 1 : 3) * SERVER_RUNTIME)) {
+			ksft_print_msg("change %d of the fair server refused\n", i + 1);
+			ret = KSFT_FAIL;
+		}
+	}
+	if (ret == KSFT_PASS) {
+		set_flag(&mv_state[4], 1);
+		set_flag(&mv_state[5], 1);
+		if (server_put(cpu, "runtime", 3 * SERVER_RUNTIME))
+			ret = KSFT_FAIL;
+		s30 = proc_share(fair, 2 * SERVER_PERIOD);
+		if (server_put(cpu, "runtime", SERVER_RUNTIME))
+			ret = KSFT_FAIL;
+		s10 = proc_share(fair, 2 * SERVER_PERIOD);
+	}
+	set_flag(&mv_state[5], 0);
+	set_flag(&mv_state[4], 0);
+	reap(rt);
+	reap(fair);
+	if (ret == KSFT_PASS &&
+	    (s30 < 30 - STARVED_SLACK || s30 > 30 + STARVED_SLACK ||
+	     s10 < 10 - STARVED_SLACK || s10 > 10 + STARVED_SLACK)) {
+		ksft_print_msg("a starved fair task got %d%% of a server of 30%%, %d%% of 10%%\n",
+			       s30, s10);
+		ret = KSFT_FAIL;
+	}
+	sleep_ns(3 * PERIOD);
+	if (ret == KSFT_PASS && admits_in(cg_p, base, "after the fair server's changes"))
+		ret = KSFT_FAIL;
+	return ret;
+}
+
+/*
+ * A reclaiming deadline task of P gets the share of P's CPU its root
+ * domain leaves free, which P's fair server takes from: less once the
+ * server grows, as much after a rebuild of the accounting (Q made and
+ * unmade), and what it had once the server is back. The server is then
+ * put back as the test found it, as P's free bandwidth must be.
+ */
+static int server_reclaim(void)
+{
+	int cpu = ncpus - 1, s10, s30, rebuilt, back, ret = KSFT_PASS;
+	pthread_t t;
+
+	if (server_set(cpu, SERVER_RUNTIME, SERVER_PERIOD))
+		return KSFT_SKIP;
+	if (start_spinner(&t, 10 * NSEC_PER_MSEC, SCHED_FLAG_RECLAIM))
+		return KSFT_SKIP;	/* no room for a task of 10% */
+	s10 = share_of(t, SHARE_NS);
+	if (server_set(cpu, 3 * SERVER_RUNTIME, SERVER_PERIOD))
+		ret = KSFT_FAIL;
+	s30 = share_of(t, SHARE_NS);
+	if (make_partition(cg_q, ncpus - 2))
+		ret = KSFT_FAIL;
+	remove_partition(cg_q);
+	rebuilt = share_of(t, SHARE_NS);
+	if (server_set(cpu, SERVER_RUNTIME, SERVER_PERIOD))
+		ret = KSFT_FAIL;
+	back = share_of(t, SHARE_NS);
+	stop_spinner(t);
+	server_restore();
+	if (ret == KSFT_PASS &&
+	    (s30 > s10 - SHARE_SLACK ||
+	     rebuilt < s30 - SHARE_SLACK || rebuilt > s30 + SHARE_SLACK ||
+	     back < s10 - SHARE_SLACK || back > s10 + SHARE_SLACK)) {
+		ksft_print_msg("reclaiming: %d%%, %d%% at 30%%, %d%% rebuilt, %d%% back at 10%%\n",
+			       s10, s30, rebuilt, back);
+		ret = KSFT_FAIL;
+	}
+	return ret;
+}
+
+/* Parameter changes while a task wakes on another CPU */
+
+#define WAKE_NS		(5 * NSEC_PER_SEC)	/* how long the changes go on */
+#define WAKE_BURST	2000			/* changes between two clock readings */
+
+/* this_bw and running_bw of @cpu, from sched_debug: 0, or -1. */
+static int rq_bw_of(int cpu, long *this_bw, long *running_bw)
+{
+	char line[256], want[32];
+	FILE *f = fopen("/sys/kernel/debug/sched/debug", "r");
+	int in = 0, got = 0;
+
+	if (!f)
+		return -1;
+	snprintf(want, sizeof(want), "dl_rq[%d]:", cpu);
+	while (got < 2 && fgets(line, sizeof(line), f)) {
+		char *val = strchr(line, ':');
+
+		if (!strncmp(line, want, strlen(want)))
+			in = 1;
+		else if (!in || !val)
+			continue;
+		else if (strstr(line, ".running_bw") && sscanf(val + 1, "%ld", running_bw) == 1)
+			got++;
+		else if (strstr(line, ".this_bw") && sscanf(val + 1, "%ld", this_bw) == 1)
+			got++;
+	}
+	fclose(f);
+	return got == 2 ? 0 : -1;
+}
+
+/*
+ * A deadline task of Q, a partition root of two CPUs taken by two
+ * deadline tasks of an earlier deadline, that sleeps and wakes: it wakes
+ * on whichever of the two has the later deadline to run, which moves it.
+ * Its parameters change meanwhile, from a CPU outside Q.
+ *
+ * A wakeup that moves a task takes its bandwidth off the runqueue it
+ * slept on, and the enqueue on the one it wakes on, which that CPU may
+ * be left to do, charges it there. A change in between must not take it
+ * off the runqueue of either: once every task of the case is gone,
+ * this_bw of both CPUs is what it was before.
+ *
+ * Only then, with nothing left to change: sched_debug prints running_bw
+ * and this_bw of a CPU one after the other, holding no lock in between,
+ * and every parameter change takes a task's bandwidth off its runqueue
+ * and puts it back, so a reading of the two while the changes go on
+ * straddles one of those and tells nothing.
+ */
+static atomic_int *wk_state;		/* 0: tasks up, 1: wakeups, 2: stop */
+
+static pid_t waking_task(uint64_t runtime, uint64_t period, int sleeps)
+{
+	pid_t pid = fork_child("a waking deadline task");
+
+	if (!pid) {
+		if (enter(cg_q, getpid()) || set_deadline(0, runtime, period)) {
+			wk_state[0] = -1;
+			_exit(1);
+		}
+		wk_state[0]++;
+		for (;;) {
+			if (wk_state[2])
+				_exit(0);
+			spin_ns(sleeps ? 20 * NSEC_PER_USEC : NSEC_PER_MSEC);
+			if (sleeps) {
+				sleep_ns(80 * NSEC_PER_USEC);
+				wk_state[1]++;
+			}
+		}
+	}
+	return pid;
+}
+
+/* Changes the parameters of @pid over and over, until told to stop. */
+static pid_t changer_proc(pid_t pid)
+{
+	pid_t self = fork_child("a changer of the parameters");
+
+	if (!self) {
+		while (!wk_state[2]) {
+			if (set_deadline(pid, 20 * NSEC_PER_MSEC, PERIOD) ||
+			    set_deadline(pid, 10 * NSEC_PER_MSEC, PERIOD))
+				break;
+		}
+		_exit(0);
+	}
+	return self;
+}
+
+static int params_waking(void)
+{
+	int cpu_a = ncpus - 3, cpu_b = ncpus - 2, i, ret = KSFT_PASS, changes = 0;
+	long ta, ra, tb, rb, ta2, ra2, tb2, rb2;
+	pid_t pid[3] = { -1, -1, -1 }, changer = -1;
+	uint64_t end;
+	char cpus[32];
+
+	if (ncpus < 4)
+		return KSFT_SKIP;
+	snprintf(cpus, sizeof(cpus), "%d-%d", cpu_a, cpu_b);
+	if (make_partition_cpus(cg_q, cpus)) {
+		remove_partition(cg_q);
+		return KSFT_SKIP;	/* no partition root of two CPUs */
+	}
+	if (rq_bw_of(cpu_a, &ta, &ra) || rq_bw_of(cpu_b, &tb, &rb)) {
+		remove_partition(cg_q);
+		return KSFT_SKIP;	/* sched_debug tells of neither */
+	}
+	wk_state = mv_state + 8;
+	wk_state[0] = wk_state[1] = wk_state[2] = 0;
+	/* Two of 40% hold both CPUs with an earlier deadline than the third. */
+	pid[0] = waking_task(20 * NSEC_PER_MSEC, 50 * NSEC_PER_MSEC, 0);
+	pid[1] = waking_task(20 * NSEC_PER_MSEC, 50 * NSEC_PER_MSEC, 0);
+	pid[2] = waking_task(10 * NSEC_PER_MSEC, PERIOD, 1);
+	if (pid[0] < 0 || pid[1] < 0 || pid[2] < 0) {
+		ret = KSFT_FAIL;
+		goto out;
+	}
+	wait_for(5000, wk_state[0] >= 3 || wk_state[0] < 0);
+	if (wk_state[0] != 3) {
+		ksft_print_msg("no room for the deadline tasks of a partition of two CPUs\n");
+		ret = KSFT_SKIP;
+		goto out;
+	}
+	changer = changer_proc(pid[2]);
+	if (changer < 0) {
+		ret = KSFT_FAIL;
+		goto out;
+	}
+	end = now_ns() + WAKE_NS;
+	while (now_ns() < end) {
+		for (i = 0; i < WAKE_BURST; i++, changes += 2) {
+			if (set_deadline(pid[2], 20 * NSEC_PER_MSEC, PERIOD) ||
+			    set_deadline(pid[2], 10 * NSEC_PER_MSEC, PERIOD)) {
+				ksft_print_msg("a change of the waking task refused\n");
+				ret = KSFT_FAIL;
+				goto out;
+			}
+		}
+	}
+	if (!wk_state[1]) {
+		ksft_print_msg("the waking task never woke\n");
+		ret = KSFT_FAIL;
+	}
+out:
+	wk_state[2] = 1;
+	reap(changer);
+	for (i = 0; i < 3; i++)
+		reap(pid[i]);
+	sleep_ns(3 * PERIOD);
+	if (ret == KSFT_PASS) {
+		if (rq_bw_of(cpu_a, &ta2, &ra2) || rq_bw_of(cpu_b, &tb2, &rb2)) {
+			ret = KSFT_FAIL;
+		} else if (ta2 != ta || tb2 != tb) {
+			ksft_print_msg("%d changes: this_bw %ld and %ld, was %ld and %ld\n",
+				       changes, ta2, tb2, ta, tb);
+			ret = KSFT_FAIL;
+		}
+	}
+	remove_partition(cg_q);
+	return ret;
+}
+
+/* A random mix of the transitions above */
+
+#define MIX_WORKERS	6
+#define MIX_NS		(3 * NSEC_PER_SEC)
+#define MIX_SEED	20261103	/* fixed, so that a failure can be replayed */
+
+/*
+ * Each worker takes a random transition of its own over and over: into
+ * SCHED_DEADLINE with random parameters and flags, out of it, asleep,
+ * spinning past its runtime, through sched_yield(), through the shared
+ * mutex of the priority inheritance cases, and out of life. The case
+ * takes the ones only another task can: new parameters, a move between
+ * the cgroups, a kill, and the fair server of a CPU. Every worker it
+ * finds dead it starts anew, so the mix keeps its tasks.
+ *
+ * Nothing here looks at what a single transition does, which the cases
+ * above do one at a time. What it wants is the accounting whole
+ * afterwards: once every worker is gone and its 0-lag time is past, each
+ * of the three root domains admits what it admitted before, and this_bw
+ * of the three CPUs is what it was. The kernel's own warnings of
+ * running_bw and this_bw over- and underflow count as well, which the
+ * suite's dmesg tells of.
+ */
+static atomic_int *mix_state;		/* 0: stop, 1 + i: worker i's rounds */
+
+static pid_t mix_worker(int idx, unsigned int seed)
+{
+	static const uint64_t runtime[] = { 5, 10, 20, 30 };
+	static const uint64_t period[] = { 50, 100 };
+	static const uint64_t flag[] = { 0, SCHED_FLAG_RECLAIM, SCHED_FLAG_DL_OVERRUN };
+	pid_t pid = fork_child("a worker of the mix");
+
+	if (!pid) {
+		struct sigaction sa = { .sa_handler = catch_xcpu };
+		int err;
+
+		if (sigaction(SIGXCPU, &sa, NULL))
+			_exit(1);
+		seed += idx;
+		/*
+		 * A refusal is part of the mix: each call below is made in
+		 * whatever state the worker is in, and an error is what the
+		 * kernel is entitled to answer.
+		 */
+		while (!mix_state[0]) {
+			unsigned int r = rand_r(&seed);
+
+			switch (r % 8) {
+			case 0:
+				set_deadline_flags(0, runtime[r % 4] * NSEC_PER_MSEC,
+						   period[r % 2] * NSEC_PER_MSEC,
+						   flag[r % 3]);
+				break;
+			case 1:
+				set_other(0);
+				break;
+			case 2:
+				sleep_ns((r % 20 + 1) * NSEC_PER_MSEC);
+				break;
+			case 3:
+				spin_ns((r % 15 + 1) * NSEC_PER_MSEC);
+				break;
+			case 4:
+				sched_yield();
+				break;
+			case 5:
+				err = pthread_mutex_trylock(shm_lock);
+				if (err == EOWNERDEAD)	/* its owner died holding it */
+					err = pthread_mutex_consistent(shm_lock);
+				if (!err) {
+					spin_ns(NSEC_PER_MSEC);
+					if (pthread_mutex_unlock(shm_lock))
+						_exit(1);
+				}
+				break;
+			case 6:
+				_exit(0);	/* the case starts another */
+			default:
+				sleep_ns(NSEC_PER_MSEC / 2);
+				break;
+			}
+			mix_state[1 + idx]++;
+		}
+		_exit(0);
+	}
+	return pid;
+}
+
+static int random_mix(void)
+{
+	static const uint64_t runtime[] = { 5, 10, 20, 30 };
+	int cpu_a = ncpus - 3, cpu_b = ncpus - 2, cpu_p = ncpus - 1;
+	int base_p, base_q, base_r, i, ret = KSFT_PASS, rounds = 0, sums;
+	long ta = 0, ra, tb = 0, rb, tp = 0, rp, ta2, ra2, tb2, rb2, tp2, rp2;
+	pid_t pid[MIX_WORKERS] = { -1, -1, -1, -1, -1, -1 };
+	unsigned int seed = MIX_SEED;
+	uint64_t end;
+	char cpus[32];
+
+	if (ncpus < 4)
+		return KSFT_SKIP;
+	snprintf(cpus, sizeof(cpus), "%d-%d", cpu_a, cpu_b);
+	if (make_partition_cpus(cg_q, cpus)) {
+		remove_partition(cg_q);
+		return KSFT_SKIP;	/* no partition root of two CPUs */
+	}
+	/* Without the two sums of sched_debug, the admissions alone tell. */
+	sums = !rq_bw_of(cpu_a, &ta, &ra) && !rq_bw_of(cpu_b, &tb, &rb) &&
+	       !rq_bw_of(cpu_p, &tp, &rp);
+	base_p = probe(cg_p);
+	base_q = probe(cg_q);
+	base_r = probe(root);
+	if (base_p <= 0 || base_q <= 0 || base_r <= 0) {
+		remove_partition(cg_q);
+		return KSFT_SKIP;
+	}
+	mix_state = mv_state + 16;
+	for (i = 0; i <= MIX_WORKERS; i++)
+		mix_state[i] = 0;
+	for (i = 0; i < MIX_WORKERS; i++) {
+		pid[i] = mix_worker(i, seed);
+		if (pid[i] < 0) {
+			ret = KSFT_FAIL;
+			goto out;
+		}
+	}
+
+	end = now_ns() + MIX_NS;
+	while (now_ns() < end) {
+		unsigned int r = rand_r(&seed);
+		int w = r % MIX_WORKERS;
+
+		switch ((r / MIX_WORKERS) % 7) {
+		case 0:
+			set_deadline(pid[w], runtime[r % 4] * NSEC_PER_MSEC, PERIOD);
+			break;
+		case 1:
+			set_other(pid[w]);
+			break;
+		case 2:
+			enter(cg_p, pid[w]);
+			break;
+		case 3:
+			enter(cg_q, pid[w]);
+			break;
+		case 4:
+			enter(root, pid[w]);
+			break;
+		case 5:
+			/* Dead and reaped already: ESRCH, and it starts anew below. */
+			if (kill(pid[w], SIGKILL) && errno != ESRCH)
+				ksft_print_msg("kill %d: %s\n", pid[w], strerror(errno));
+			break;
+		default:
+			server_set(r % 2 ? cpu_p : cpu_a,
+				   (r % 3 + 1) * SERVER_RUNTIME, SERVER_PERIOD);
+			break;
+		}
+		sleep_ns((r % 2000 + 100) * NSEC_PER_USEC);
+		/* Whoever died, of its own or killed, runs again. */
+		for (i = 0; i < MIX_WORKERS; i++) {
+			pid_t done = waitpid(pid[i], NULL, WNOHANG);
+
+			if (done < 0 && errno != EINTR) {
+				ksft_print_msg("waitpid %d: %s\n", pid[i], strerror(errno));
+				ret = KSFT_FAIL;
+				goto out;
+			}
+			if (done == pid[i]) {
+				pid[i] = mix_worker(i, seed + rounds);
+				if (pid[i] < 0) {
+					ret = KSFT_FAIL;
+					goto out;
+				}
+				rounds++;
+			}
+		}
+	}
+out:
+	mix_state[0] = 1;
+	for (i = 0; i < MIX_WORKERS; i++)
+		reap(pid[i]);
+	server_restore();
+	if (ret != KSFT_PASS) {
+		remove_partition(cg_q);
+		return ret;
+	}
+	for (i = 0, rounds = 0; i < MIX_WORKERS; i++)
+		rounds += mix_state[1 + i];
+	if (!rounds) {
+		ksft_print_msg("the workers of the mix took no transition\n");
+		ret = KSFT_FAIL;
+	}
+	sleep_ns(5 * PERIOD);		/* their 0-lag times */
+	if (ret == KSFT_PASS && sums) {
+		if (rq_bw_of(cpu_a, &ta2, &ra2) || rq_bw_of(cpu_b, &tb2, &rb2) ||
+		    rq_bw_of(cpu_p, &tp2, &rp2)) {
+			ret = KSFT_FAIL;
+		} else if (ta2 != ta || tb2 != tb || tp2 != tp) {
+			ksft_print_msg("this_bw %ld %ld %ld, was %ld %ld %ld\n",
+				       ta2, tb2, tp2, ta, tb, tp);
+			ret = KSFT_FAIL;
+		}
+	}
+	if (ret == KSFT_PASS &&
+	    (admits_in(cg_p, base_p, "P after the mix") ||
+	     admits_in(cg_q, base_q, "Q after the mix") ||
+	     admits_in(root, base_r, "the root domain of the rest after the mix"))) {
+		ksft_print_msg("seed %u, %d transitions\n", MIX_SEED, rounds);
+		ret = KSFT_FAIL;
+	}
+	remove_partition(cg_q);
+	return ret;
+}
+
+/* CPU hotplug, from the main process, with no P */
+
+static int hp_cpu = -1;
+
+static int cpu_online(int cpu, int on)
+{
+	char dir[64];
+
+	snprintf(dir, sizeof(dir), "/sys/devices/system/cpu/cpu%d", cpu);
+	return write_file(dir, "online", on ? "1" : "0");
+}
+
+/* Back online: every case that follows needs that CPU. */
+static void cpu_up(int cpu)
+{
+	int err = cpu_online(cpu, 1);
+
+	if (err)
+		ksft_print_msg("CPU %d cannot come back online: %s\n", cpu, strerror(-err));
+}
+
+/* Deadline sleepers of 30% each: offline and online a CPU meanwhile. */
+static int hotplug_sleepers(void)
+{
+	int base = probe(NULL), after, i, ret = KSFT_PASS;
+	pid_t pid[4];
+
+	for (i = 0; i < 4; i++) {
+		mv_state[0] = 0;
+		pid[i] = mover(MV_ASLEEP, 30 * NSEC_PER_MSEC);
+		if (pid[i] < 0 || child_up("a deadline sleeper", 0)) {
+			while (i >= 0)
+				reap(pid[i--]);
+			return KSFT_FAIL;
+		}
+	}
+	if (cpu_online(hp_cpu, 0) || cpu_online(hp_cpu, 1)) {
+		ksft_print_msg("offline and online of CPU %d with deadline sleepers failed\n",
+			       hp_cpu);
+		ret = KSFT_FAIL;
+		cpu_up(hp_cpu);
+	}
+	for (i = 0; i < 4; i++)
+		reap(pid[i]);
+	sleep_ns(3 * PERIOD);
+	after = probe(NULL);
+	if (ret == KSFT_PASS && after != base) {
+		ksft_print_msg("hotplug with sleepers: %d probe tasks admitted before, %d after\n",
+			       base, after);
+		ret = KSFT_FAIL;
+	}
+	return ret;
+}
+
+/* The deadline tasks fill the CPUs: going offline must be refused. */
+static int hotplug_refused(void)
+{
+	int base = probe(NULL), n, i, ret = KSFT_PASS, err;
+	pid_t *pid;
+
+	if (base < 12)
+		return KSFT_SKIP;
+	/* 30% each, up to the free bandwidth but 30% to 60%: less than a CPU's. */
+	n = base / 3 - 1;
+	pid = calloc(n, sizeof(*pid));
+	if (!pid) {
+		ksft_print_msg("calloc: %s\n", strerror(errno));
+		return KSFT_FAIL;
+	}
+	for (i = 0; i < n; i++) {
+		mv_state[0] = 0;
+		pid[i] = mover(MV_ASLEEP, 30 * NSEC_PER_MSEC);
+		if (pid[i] < 0 || child_up("a deadline sleeper", 0)) {
+			while (i >= 0)
+				reap(pid[i--]);
+			free(pid);
+			return KSFT_FAIL;
+		}
+	}
+	err = cpu_online(hp_cpu, 0);
+	if (!err) {
+		ksft_print_msg("CPU %d went offline with its deadline bandwidth in use\n", hp_cpu);
+		cpu_up(hp_cpu);
+		ret = KSFT_FAIL;
+	} else if (err != -EBUSY) {
+		ksft_print_msg("offline refused with %s, not EBUSY\n", strerror(-err));
+		ret = KSFT_FAIL;
+	}
+	for (i = 0; i < n; i++)
+		reap(pid[i]);
+	free(pid);
+	sleep_ns(3 * PERIOD);
+	if (ret == KSFT_PASS && probe(NULL) != base) {
+		ksft_print_msg("a refused offline changed the free bandwidth\n");
+		ret = KSFT_FAIL;
+	}
+	return ret;
+}
+
+/*
+ * A deadline task leaves the class while it runs, its 0-lag time ahead,
+ * and the CPU it is on goes offline before that time.
+ */
+static int hotplug_departed(void)
+{
+	int base = probe(NULL), after, cpu, ret = KSFT_PASS;
+	pid_t pid;
+
+	mv_state[0] = 0;
+	mv_state[1] = 0;
+	pid = mover(MV_THROTTLED, 40 * NSEC_PER_MSEC);
+	if (pid < 0 || child_up("a departing deadline task", 0)) {
+		reap(pid);
+		return KSFT_FAIL;
+	}
+	sleep_ns(PERIOD / 2);
+	/* Running and queued: its bandwidth stays until its 0-lag time. */
+	if (set_other(pid))
+		ret = KSFT_FAIL;
+	cpu = task_cpu_of(pid);
+	if (cpu <= 0) {
+		cpu_set_t set;
+
+		/* Out of the class now: it may be moved to the CPU we offline. */
+		cpu = hp_cpu;
+		CPU_ZERO(&set);
+		CPU_SET(cpu, &set);
+		if (sched_setaffinity(pid, sizeof(set), &set))
+			ret = KSFT_FAIL;
+	}
+	if (ret == KSFT_PASS && cpu_online(cpu, 0)) {
+		ksft_print_msg("offline of CPU %d refused\n", cpu);
+		ret = KSFT_FAIL;
+	}
+	sleep_ns(2 * PERIOD);
+	cpu_up(cpu);
+	reap(pid);
+	sleep_ns(3 * PERIOD);
+	after = probe(NULL);
+	if (ret == KSFT_PASS && after != base) {
+		ksft_print_msg("departed, CPU offlined: %d probe tasks admitted before, %d after\n",
+			       base, after);
+		ret = KSFT_FAIL;
+	}
+	return ret;
+}
+
+/*
+ * The fair server of the CPU set to 30%: its bandwidth leaves the root
+ * domain with the CPU, as it does at 10%, and comes back with the CPU as
+ * it was set.
+ */
+static int hotplug_server(void)
+{
+	int base, off10, off30;
+
+	if (server_set(hp_cpu, SERVER_RUNTIME, SERVER_PERIOD))
+		return KSFT_SKIP;
+	base = probe(NULL);
+	if (cpu_online(hp_cpu, 0)) {
+		ksft_print_msg("offline of CPU %d refused\n", hp_cpu);
+		return KSFT_FAIL;
+	}
+	off10 = probe(NULL);
+	cpu_up(hp_cpu);
+	if (server_set(hp_cpu, 3 * SERVER_RUNTIME, SERVER_PERIOD) ||
+	    admits(base - 2, "a fair server of 30%"))
+		return KSFT_FAIL;
+	if (cpu_online(hp_cpu, 0)) {
+		ksft_print_msg("offline of CPU %d refused, its fair server at 30%%\n", hp_cpu);
+		return KSFT_FAIL;
+	}
+	off30 = probe(NULL);
+	cpu_up(hp_cpu);
+	if (off30 != off10) {
+		ksft_print_msg("CPU %d offline: %d probe tasks, its server at 10%%, %d at 30%%\n",
+			       hp_cpu, off10, off30);
+		return KSFT_FAIL;
+	}
+	if (admits(base - 2, "a fair server of 30%, its CPU back online") ||
+	    server_set(hp_cpu, SERVER_RUNTIME, SERVER_PERIOD) ||
+	    admits(base, "the fair server back to 10%"))
+		return KSFT_FAIL;
+	return KSFT_PASS;
+}
+
+/*
+ * Going offline, a CPU takes its fair server's bandwidth along with its
+ * capacity. With the server at the admission limit less 10%, the CPU goes
+ * offline with as many probe tasks held as the root domain admits but
+ * one, and no longer with one more.
+ */
+static int hotplug_server_refused(void)
+{
+	uint64_t rt_runtime, rt_period, runtime;
+	int n, err, ret = KSFT_PASS;
+	char buf[32];
+
+	if (read_file("/proc/sys/kernel/sched_rt_runtime_us", buf, sizeof(buf)))
+		return KSFT_SKIP;
+	rt_runtime = atoll(buf);
+	if (read_file("/proc/sys/kernel/sched_rt_period_us", buf, sizeof(buf)))
+		return KSFT_SKIP;
+	rt_period = atoll(buf);
+	if (!rt_period || 5 * rt_runtime < rt_period)
+		return KSFT_SKIP;
+	runtime = SERVER_PERIOD * rt_runtime / rt_period - SERVER_PERIOD / 10;
+	if (server_set(hp_cpu, runtime, SERVER_PERIOD))
+		return KSFT_SKIP;
+	n = probe(NULL);
+	if (n < 2 || hold(n - 1)) {
+		release_held();
+		return KSFT_FAIL;
+	}
+	err = cpu_online(hp_cpu, 0);
+	if (err) {
+		ksft_print_msg("CPU %d, room for one probe task left: offline refused (%s)\n",
+			       hp_cpu, strerror(-err));
+		ret = KSFT_FAIL;
+	} else if (cpu_online(hp_cpu, 1) || hold(1)) {
+		cpu_up(hp_cpu);
+		ret = KSFT_FAIL;
+	} else {
+		err = cpu_online(hp_cpu, 0);
+		if (err != -EBUSY) {
+			ksft_print_msg("CPU %d, no room left: offline %s, not EBUSY\n",
+				       hp_cpu, err ? strerror(-err) : "accepted");
+			if (!err)
+				cpu_up(hp_cpu);
+			ret = KSFT_FAIL;
+		}
+	}
+	release_held();
+	return ret;
+}
+
+/* Setup */
+
+static int find_cgroup2(void)
+{
+	char line[PATH_MAX + 64], dev[64], dir[PATH_MAX], type[64];
+	FILE *f = fopen("/proc/self/mounts", "r");
+	int found = 0;
+
+	while (f && !found && fgets(line, sizeof(line), f)) {
+		if (sscanf(line, "%63s %4095s %63s", dev, dir, type) == 3 &&
+		    !strcmp(type, "cgroup2")) {
+			snprintf(root, sizeof(root), "%s", dir);
+			found = 1;
+		}
+	}
+	if (f)
+		fclose(f);
+	return found ? 0 : -1;
+}
+
+static void report(const char *name, int ret)
+{
+	if (ret == KSFT_PASS)
+		ksft_test_result_pass("%s\n", name);
+	else if (ret == KSFT_SKIP)
+		ksft_test_result_skip("%s\n", name);
+	else
+		ksft_test_result_fail("%s\n", name);
+}
+
+enum where {
+	MEASURED_IN_P,	/* in P, measured before and after */
+	IN_P,		/* in P, measuring itself */
+	FROM_OUTSIDE,	/* from the main process */
+};
+
+static const struct p_case {
+	const char *name;
+	int (*fn)(void);
+	enum where where;
+} p_cases[] = {
+	{ "pi_deadline_owner", pi_deadline_owner, MEASURED_IN_P },
+	{ "pi_other_owner_asleep", pi_other_owner_asleep, MEASURED_IN_P },
+	{ "pi_former_owner_asleep", pi_former_owner_asleep, MEASURED_IN_P },
+	{ "pi_unlock_running", pi_unlock_running, MEASURED_IN_P },
+	{ "params_asleep", params_asleep, IN_P },
+	{ "params_non_contending", params_non_contending, MEASURED_IN_P },
+	{ "params_throttled", params_throttled, MEASURED_IN_P },
+	{ "params_refused", params_refused, IN_P },
+	{ "params_keep_class_change", params_keep_class_change, MEASURED_IN_P },
+	{ "move_asleep", move_asleep, FROM_OUTSIDE },
+	{ "move_throttled", move_throttled, FROM_OUTSIDE },
+	{ "move_non_contending", move_non_contending, FROM_OUTSIDE },
+	{ "move_refused", move_refused, FROM_OUTSIDE },
+	{ "death_running", death_running, MEASURED_IN_P },
+	{ "death_switched_out", death_switched_out, MEASURED_IN_P },
+	{ "death_shrunk", death_shrunk, MEASURED_IN_P },
+	{ "death_killed_asleep", death_killed_asleep, MEASURED_IN_P },
+	{ "death_killed_non_contending", death_killed_non_contending, MEASURED_IN_P },
+	{ "death_killed_throttled", death_killed_throttled, MEASURED_IN_P },
+	{ "death_killed_running", death_killed_running, MEASURED_IN_P },
+	{ "death_pi_waiter", death_pi_waiter, MEASURED_IN_P },
+	{ "death_pi_owner", death_pi_owner, MEASURED_IN_P },
+	{ "death_pi_deadline_owner", death_pi_deadline_owner, MEASURED_IN_P },
+	{ "death_group", death_group, MEASURED_IN_P },
+	{ "yield_switched_out", yield_switched_out, IN_P },
+	{ "yield_moved", yield_moved, FROM_OUTSIDE },
+	{ "yield_killed", yield_killed, MEASURED_IN_P },
+	{ "overrun_caught", overrun_caught, IN_P },
+	{ "overrun_group_death", overrun_group_death, MEASURED_IN_P },
+	{ "reclaim_runs", reclaim_runs, MEASURED_IN_P },
+	{ "reclaim_switched", reclaim_switched, MEASURED_IN_P },
+	{ "reclaim_moved", reclaim_moved, FROM_OUTSIDE },
+	{ "server_params", server_params, IN_P },
+	{ "server_rebuilds", server_rebuilds, FROM_OUTSIDE },
+	{ "server_states", server_states, FROM_OUTSIDE },
+	{ "server_reclaim", server_reclaim, MEASURED_IN_P },
+	{ "params_waking", params_waking, FROM_OUTSIDE },
+	{ "random_mix", random_mix, FROM_OUTSIDE },
+};
+
+#define N_P_CASES	((int)ARRAY_SIZE(p_cases))
+
+static const struct hp_case {
+	const char *name;
+	int (*fn)(void);
+} hp_cases[] = {
+	{ "hotplug_sleepers", hotplug_sleepers },
+	{ "hotplug_refused", hotplug_refused },
+	{ "hotplug_departed", hotplug_departed },
+	{ "hotplug_server", hotplug_server },
+	{ "hotplug_server_refused", hotplug_server_refused },
+};
+
+#define N_HP_CASES	((int)ARRAY_SIZE(hp_cases))
+
+/* The cases in P, each in a P of its own. */
+static void run_p_cases(void)
+{
+	char path[PATH_MAX + 32], buf[256];
+	int i, ret, added = 0, told = 0, ok;
+
+	ok = !find_cgroup2() &&
+	     snprintf(cg_p, sizeof(cg_p), "%s/deadline_bw_p", root) < (int)sizeof(cg_p) &&
+	     snprintf(cg_q, sizeof(cg_q), "%s/deadline_bw_q", root) < (int)sizeof(cg_q);
+	if (ok) {
+		/* The cpuset controller for the root's children while the cases run. */
+		snprintf(path, sizeof(path), "%s/cgroup.subtree_control", root);
+		ok = !read_file(path, buf, sizeof(buf));
+		added = ok && !strstr(buf, "cpuset");
+		if (added && write_file(root, "cgroup.subtree_control", "+cpuset")) {
+			ok = 0;
+			added = 0;
+		}
+	}
+	for (i = 0; i < N_P_CASES; i++) {
+		const struct p_case *c = &p_cases[i];
+
+		if (ok && make_p()) {
+			remove_p();
+			ok = 0;
+		}
+		if (!ok) {
+			if (!told++)
+				ksft_print_msg("no one-CPU partition root: cases in P skipped\n");
+			ksft_test_result_skip("%s\n", c->name);
+			continue;
+		}
+		if (c->where == MEASURED_IN_P)
+			ret = measured(c->name, cg_p, c->fn);
+		else if (c->where == IN_P)
+			ret = run_in(cg_p, c->fn);
+		else
+			ret = c->fn();
+		remove_p();
+		server_restore();
+		report(c->name, ret);
+	}
+	if (added && write_file(root, "cgroup.subtree_control", "-cpuset"))
+		ksft_print_msg("the cpuset controller stays enabled\n");
+}
+
+int main(void)
+{
+	char buf[64];
+	int i;
+
+	ksft_print_header();
+	if (geteuid())
+		ksft_exit_skip("needs root\n");
+	ncpus = get_nprocs();
+	if (ncpus < 3)
+		ksft_exit_skip("needs 3 CPUs\n");
+	if (read_file("/proc/sys/kernel/sched_rt_runtime_us", buf, sizeof(buf)) || atol(buf) < 0)
+		ksft_exit_skip("no deadline admission control\n");
+	mv_state = mmap(NULL, 4096, PROT_READ | PROT_WRITE, MAP_SHARED | MAP_ANONYMOUS, -1, 0);
+	if (mv_state == MAP_FAILED)
+		ksft_exit_fail_msg("mmap: %s\n", strerror(errno));
+	shm_lock = (pthread_mutex_t *)((char *)mv_state + 256);
+
+	ksft_set_plan(N_P_CASES + N_HP_CASES);
+	server_init();
+	run_p_cases();
+
+	for (i = ncpus - 1; i > 0 && hp_cpu < 0; i--) {
+		char dir[64];
+
+		snprintf(dir, sizeof(dir), "/sys/devices/system/cpu/cpu%d/online", i);
+		if (!access(dir, W_OK))
+			hp_cpu = i;
+	}
+	if (hp_cpu < 0)
+		ksft_print_msg("no CPU hotplug: hotplug cases skipped\n");
+	for (i = 0; i < N_HP_CASES; i++) {
+		if (hp_cpu < 0) {
+			ksft_test_result_skip("%s\n", hp_cases[i].name);
+			continue;
+		}
+		report(hp_cases[i].name, hp_cases[i].fn());
+		server_restore();
+	}
+	ksft_finished();
+}
-- 
2.47.3

Re: [PATCH 01/12] sched: Reject SCHED_FLAG_KEEP_PARAMS before reserving deadline bandwidth

[sashiko-bot]

Thank you for your contribution! Sashiko AI review found 1 potential issue(s) to consider:
- [High] sched: bandwidth leak in __sched_setscheduler() under SCHED_FLAG_KEEP_PARAMS
--

commit 7875cab1acc5b85b363d87da8587a9ad5e4642f8
Author: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>

sched: Reject SCHED_FLAG_KEEP_PARAMS before reserving deadline bandwidth

This commit moves the sched_dl_overflow() check and sched_reset_on_fork
update in __sched_setscheduler() after the SCHED_FLAG_KEEP_PARAMS class
change check so rejected requests do not leak deadline bandwidth.

> diff --git a/kernel/sched/syscalls.c b/kernel/sched/syscalls.c
> index 3fa447aabe7fb..f0b7b2d52614f 100644
> --- a/kernel/sched/syscalls.c
> +++ b/kernel/sched/syscalls.c
> @@ -655,17 +655,6 @@ int __sched_setscheduler(struct task_struct *p,
>  		goto recheck;
>  	}
>  
> -	/*
> -	 * If setscheduling to SCHED_DEADLINE (or changing the parameters
> -	 * of a SCHED_DEADLINE task) we need to check if enough bandwidth
> -	 * is available.
> -	 */
> -	if ((dl_policy(policy) || dl_task(p)) && sched_dl_overflow(p, policy, attr)) {
> -		retval = -EBUSY;
> -		goto unlock;
> -	}
> -
> -	p->sched_reset_on_fork = reset_on_fork;
>  	oldprio = p->prio;
>  
>  	newprio = __normal_prio(policy, attr->sched_priority, attr->sched_nice);
> @@ -699,6 +688,19 @@ int __sched_setscheduler(struct task_struct *p,
>  		queue_flags |= DEQUEUE_CLASS;
>  	}
>  
> +	/*
> +	 * If setscheduling to SCHED_DEADLINE (or changing the parameters
> +	 * of a SCHED_DEADLINE task) we need to check if enough bandwidth
> +	 * is available. Last of the checks: nothing gives back the
> +	 * bandwidth it reserves.
> +	 */
> +	if ((dl_policy(policy) || dl_task(p)) && sched_dl_overflow(p, policy, attr)) {
> +		retval = -EBUSY;
> +		goto unlock;
> +	}

[Severity: High]
Can __sched_setscheduler() in kernel/sched/syscalls.c still leak
dl_b->total_bw or corrupt rq->dl bandwidth accounting when
SCHED_FLAG_KEEP_PARAMS is set?

When attr->sched_flags & SCHED_FLAG_KEEP_PARAMS is set, the sched_change
block skips __setscheduler_params(p, attr):

kernel/sched/syscalls.c:__sched_setscheduler() {
	...
	scoped_guard (sched_change, p, queue_flags) {

		if (!(attr->sched_flags & SCHED_FLAG_KEEP_PARAMS)) {
			__setscheduler_params(p, attr);
			p->sched_class = next_class;
			p->prio = newprio;
			__setscheduler_dl_pi(newprio, policy, p, scope);
		}
		__setscheduler_uclamp(p, attr);
	...
}

Because __setscheduler_params() is skipped, neither p->policy nor
p->dl.dl_bw is updated. However, SCHED_FLAG_KEEP_PARAMS is only rejected
when prev_class != next_class, and sched_dl_overflow(p, policy, attr) is
still called even when SCHED_FLAG_KEEP_PARAMS is set.

This allows sched_dl_overflow() to modify deadline bandwidth without
updating p->dl.dl_bw or p->policy in two paths:

1. If a non-deadline task (e.g. p->policy == SCHED_NORMAL, so
!task_has_dl_policy(p) and p->dl.dl_bw == 0) is PI-boosted by a
SCHED_DEADLINE waiter via rt_mutex_setprio(), p->sched_class is
&dl_sched_class while p->policy remains SCHED_NORMAL. Calling
sys_sched_setattr() with sched_policy = SCHED_DEADLINE and
SCHED_FLAG_KEEP_PARAMS populates attr.sched_runtime = p->se.slice via
get_params(). In __sched_setscheduler(), both prev_class and next_class
are &dl_sched_class, so the prev_class != next_class check is bypassed.
sched_dl_overflow() then sees dl_policy(policy) && !task_has_dl_policy(p)
and adds new_bw to dl_b->total_bw via __dl_add(), while the
SCHED_FLAG_KEEP_PARAMS check skips __setscheduler_params(), leaving
p->policy as SCHED_NORMAL and p->dl.dl_bw as 0. When p deboosts, new_bw is
never subtracted from dl_b->total_bw.

2. In SYSCALL_DEFINE3(sched_setattr), get_params(p, &attr, 0) reads p's
deadline parameters without holding p->pi_lock or rq->__lock:

kernel/sched/syscalls.c:SYSCALL_DEFINE3(sched_setattr) {
	...
	if (attr.sched_flags & SCHED_FLAG_KEEP_PARAMS)
		get_params(p, &attr, 0);

	return sched_setattr(p, &attr);
}

If a concurrent sched_setattr() updates a SCHED_DEADLINE task's parameters
before __sched_setscheduler() acquires task_rq_lock(p, &rf), attr holds
stale parameters where new_bw != p->dl.dl_bw while prev_class ==
next_class == &dl_sched_class. sched_dl_overflow() then updates
dl_b->total_bw and calls dl_change_utilization(p, new_bw) to update
rq->dl.this_bw and rq->dl.running_bw to the stale new_bw, while
__setscheduler_params() is skipped, leaving p->dl.dl_bw out of sync with
dl_b->total_bw and rq->dl.

Should __sched_setscheduler() also reject SCHED_FLAG_KEEP_PARAMS when
policy != p->policy, and skip sched_dl_overflow() when
SCHED_FLAG_KEEP_PARAMS is set?

-- 
Sashiko AI review · https://sashiko.dev/#/patchset/cover.1793804635.git.mathieu.desnoyers@efficios.com?part=1

Re: [PATCH 05/12] sched/deadline: Do not release a departing sleeper's bandwidth twice

[sashiko-bot]

Thank you for your contribution! Sashiko AI review found 1 potential issue(s) to consider:
- [High] sched/deadline: infinite loop in replenish_dl_entity() on PI donor clear
--

commit 0ea45c3b24aa9d9591791893080fc323c30a9de8
Author: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>

sched/deadline: Do not release a departing sleeper's bandwidth twice

This commit prevents switched_from_dl() from releasing root domain bandwidth
for tasks without their own deadline parameters or special sugov entities, and
clears the deadline parameters after releasing a departing sleeper's bandwidth
so it cannot be released a second time.

> diff --git a/kernel/sched/deadline.c b/kernel/sched/deadline.c
> index d474fbfd9be6d..3c57e5f5fc056 100644
> --- a/kernel/sched/deadline.c
> +++ b/kernel/sched/deadline.c
> @@ -3567,6 +3567,8 @@ static void switched_from_dl(struct rq *rq, struct task_struct *p)
>  	dec_dl_tasks_cs(p);
>  
>  	if (!task_on_rq_queued(p)) {
> +		bool released = false;
> +
>  		if (p->dl.dl_non_contending) {
>  			/*
>  			 * Inactive timer is armed. However, p is leaving
> @@ -3579,12 +3581,18 @@ static void switched_from_dl(struct rq *rq, struct task_struct *p)
>  			 * release total_bw via __dl_sub().
>  			 */
>  			sub_running_bw(&p->dl, &rq->dl);
> -		} else {
> +		} else if (p->dl.dl_runtime && !dl_entity_is_special(&p->dl)) {
>  			/*
>  			 * No pending inactive timer: the task never ran as
>  			 * DEADLINE or the timer already fired while still
>  			 * DEADLINE (only dropping running_bw at that time).
>  			 * Nobody else will release total_bw, do it now.
> +			 *
> +			 * Not for a task without parameters of its own, one
> +			 * deboosted from priority inheritance, whose mask may
> +			 * have no active CPU for dl_task_root_domain_cpu(),
> +			 * nor for a special one: neither has bandwidth in
> +			 * total_bw.
>  			 */
>  			unsigned int cpu = dl_task_root_domain_cpu(p);
>  			struct dl_bw *dl_b = &cpu_rq(cpu)->rd->dl_bw;
> @@ -3592,8 +3600,20 @@ static void switched_from_dl(struct rq *rq, struct task_struct *p)
>  			raw_spin_lock(&dl_b->lock);
>  			__dl_sub(dl_b, p->dl.dl_bw, dl_bw_cpus(cpu));
>  			raw_spin_unlock(&dl_b->lock);
> +			released = true;
>  		}
>  		sub_rq_bw(&p->dl, &rq->dl);
> +		/*
> +		 * Released: reset the parameters, as inactive_task_timer()
> +		 * does. Kept, they would make the task one with bandwidth to
> +		 * task_contending() and task_non_contending() once priority
> +		 * inheritance boosts it, and a deboost while it sleeps would
> +		 * release that bandwidth again. So would the inactive timer's
> +		 * handler when it runs late, dl_non_contending cleared under
> +		 * it by migrate_task_rq_dl(): it finds !dl_task(p).
> +		 */
> +		if (released)
> +			__dl_clear_params(&p->dl);

[Severity: High]
Can calling __dl_clear_params(&p->dl) in switched_from_dl() cause an infinite
loop in replenish_dl_entity() when p is blocked on an rt_mutex and acting as
the priority inheritance donor for the lock owner?

If a non-deadline owner holds an rt_mutex and a SCHED_DEADLINE task p blocks
on it as the top waiter, task_blocks_on_rt_mutex() -> rt_mutex_setprio() sets
owner->dl.pi_se = &p->dl and places the owner into dl_sched_class.

If p's 0-lag time has already elapsed while p sleeps on the lock (so
p->dl.dl_non_contending == 0) and p is switched to another policy via
__sched_setscheduler() in kernel/sched/syscalls.c, switched_from_dl() runs
inside the sched_change guard before rt_mutex_adjust_pi(p) is called:

    scoped_guard (sched_change, p, queue_flags) {
        /* sched_change_begin() -> switched_from_dl() */
        ...
    }

    preempt_disable();
    head = splice_balance_callbacks(rq);
    task_rq_unlock(rq, p, &rf);

    if (pi) {
        if (cpuset_locked)
            cpuset_unlock();
        rt_mutex_adjust_pi(p);
    }

At that point __dl_clear_params(&p->dl) zeroes p->dl.dl_runtime,
p->dl.dl_deadline, and p->dl.dl_period while the lock owner still has
owner->dl.pi_se pointing to &p->dl.

Even once rt_mutex_adjust_pi(p) calls rt_mutex_setprio() in
kernel/sched/core.c to deboost the owner, sched_change_begin() dequeues and
updates the owner before resetting owner->dl.pi_se:

    scoped_guard (sched_change, p, queue_flag) {
        /* sched_change_begin() -> dequeue_task_dl() -> update_curr_dl() */
        ...
        } else {
            if (dl_prio(oldprio))
                p->dl.pi_se = &p->dl;

If the boosted owner exhausts its runtime (or yields) either concurrently on
another CPU before rt_mutex_adjust_pi(p) runs, or during the dequeue in
rt_mutex_setprio(), update_curr_dl_se() sees is_dl_boosted(&owner->dl) and
calls:

    enqueue_task_dl(rq, owner, ENQUEUE_REPLENISH)
      -> enqueue_dl_entity()
        -> replenish_dl_entity(&owner->dl)

In kernel/sched/deadline.c:replenish_dl_entity(), pi_of(dl_se) still resolves
to &p->dl where dl_runtime and dl_period are now 0:

    WARN_ON_ONCE(pi_of(dl_se)->dl_runtime <= 0);
    ...
    while (dl_se->runtime <= 0) {
        dl_se->deadline += pi_of(dl_se)->dl_period;
        dl_se->runtime += pi_of(dl_se)->dl_runtime;
    }

Wouldn't this trigger the warning and spin forever with the runqueue lock
held and interrupts disabled?

-- 
Sashiko AI review · https://sashiko.dev/#/patchset/cover.1793804635.git.mathieu.desnoyers@efficios.com?part=5

Re: [PATCH 03/12] sched/deadline: Do not BUG() on a deadline task with no active CPU allowed

[sashiko-bot]

Thank you for your contribution! Sashiko AI review found 1 potential issue(s) to consider:
- [High] sched/deadline: stale root domain in dl_task_root_domain_cpu() fallback
--

commit 1ac76c29bedf1013e2c606590748a52f51b1170b
Author: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>

sched/deadline: Do not BUG() on a deadline task with no active CPU allowed

This commit replaces the BUG_ON(cpu >= nr_cpu_ids) in
dl_task_root_domain_cpu() with a fallback to task_cpu(p) when a deadline
task's cpus_mask contains no active CPUs.

> diff --git a/kernel/sched/deadline.c b/kernel/sched/deadline.c
> index dadda1a528ec6..30a52e42c26d8 100644
> --- a/kernel/sched/deadline.c
> +++ b/kernel/sched/deadline.c
> @@ -3338,13 +3338,19 @@ static void task_woken_dl(struct rq *rq, struct task_struct *p)
>   * current cpus_mask (not yet updated to the new mask) to find the
>   * actual root domain. Use cpus_mask rather than cpus_ptr, which
>   * may be temporarily narrowed by migrate_disable().
> + *
> + * The mask has no active CPU left when the CPUs it allows went offline,
> + * which the affinity of a deadline task allows with admission control
> + * off, and that of a task boosted into the deadline class by priority
> + * inheritance always: fall back to the CPU the task last ran on.
>   */
>  static unsigned int dl_task_root_domain_cpu(struct task_struct *p)
>  {
>  	unsigned int cpu;
>  
>  	cpu = cpumask_first_and(&p->cpus_mask, cpu_active_mask);
> -	BUG_ON(cpu >= nr_cpu_ids);
> +	if (cpu >= nr_cpu_ids)
> +		cpu = task_cpu(p);
>  	return cpu;
>  }

[Severity: High]
When a deadline task's cpus_mask has no active CPUs left, can falling back
to task_cpu(p) in dl_task_root_domain_cpu() return an offline or stale CPU
whose root domain no longer holds p->dl.dl_bw?

For example, with admission control disabled (sched_rt_runtime_us == -1),
suppose a SCHED_DEADLINE task p in top_cpuset is pinned via
sched_setaffinity() to CPU 1 (so p->cpus_mask is {1}), runs on CPU 1
(task_cpu(p) == 1), and blocks.

When CPU 1 goes offline via sched_cpu_deactivate(), cpuset_handle_hotplug()
does not rewrite p->cpus_mask for tasks in top_cpuset, so p->cpus_mask
remains {1} and task_cpu(p) remains 1. During the domain rebuild:

  partition_sched_domains_locked()
    detach_destroy_domains() -> attaches offline CPU 1 to def_root_domain
    build_sched_domains() -> attaches remaining active CPUs to rd_active
    dl_rebuild_rd_accounting()
      dl_clear_root_domain() -> sets def_root_domain.dl_bw.total_bw = 0
      dl_add_task_root_domain(p)

In kernel/sched/deadline.c:dl_add_task_root_domain():

	msk = this_cpu_cpumask_var_ptr(local_cpu_mask_dl);
	dl_get_task_effective_cpus(p, msk);
	cpu = cpumask_first_and(cpu_active_mask, msk);
	BUG_ON(cpu >= nr_cpu_ids);
	rq = cpu_rq(cpu);
	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_get_task_effective_cpus() queries cpuset_cpus_allowed_locked(), so p's
bandwidth is accounted into rd_active->dl_bw.total_bw, whereas
cpu_rq(task_cpu(p))->rd is def_root_domain. (Similarly, if a sleeping
deadline task last ran on CPU A in partition A, was moved to a 1-CPU cpuset
on CPU B without waking up, and CPU B goes offline, task_cpu(p) still
points to CPU A in partition A.)

Because dl_task_root_domain_cpu(p) returns task_cpu(p) (CPU 1) while
p->cpus_mask has no active CPUs:

1. In switched_from_dl(), if p changes policy away from SCHED_DEADLINE
   while sleeping, __dl_sub() subtracts p->dl.dl_bw from
   def_root_domain.dl_bw.total_bw (underflowing it from 0) instead of
   rd_active->dl_bw.total_bw, leaking p->dl.dl_bw in rd_active.

2. In dl_task_needs_bw_move() and set_cpus_allowed_dl():

	cpu = dl_task_root_domain_cpu(p);
	return !cpumask_intersects(cpu_rq(cpu)->rd->span, new_mask);

   cpu_rq(1)->rd->span is def_root_domain.span, which contains only
   offline CPUs and does not intersect any new_mask of active CPUs.
   Updating p's affinity to active CPUs in rd_active via
   sched_setaffinity() or cpuset_cpus_allowed_fallback() causes
   dl_task_needs_bw_move() to return true and set_cpus_allowed_dl() to
   subtract p->dl.dl_bw from def_root_domain.dl_bw.total_bw. Moving p via
   cpuset_can_attach() and cpuset_attach_task() to a child cpuset in the
   same root domain rd_active causes cpuset_reserve_dl_bw() to add
   p->dl.dl_bw a second time to rd_active->dl_bw.total_bw while
   set_cpus_allowed_dl() subtracts from def_root_domain; moving p to a
   different partition subtracts from def_root_domain instead of rd_active,
   leaking p->dl.dl_bw in rd_active.

-- 
Sashiko AI review · https://sashiko.dev/#/patchset/cover.1793804635.git.mathieu.desnoyers@efficios.com?part=3

Re: [PATCH 04/12] sched/deadline: Do not lose a throttled task switched out and back

[sashiko-bot]

Thank you for your contribution! Sashiko AI review found 2 potential issue(s) to consider:
- [Medium] sched/deadline: incomplete replenishment when clearing dl_throttled
- [Medium] sched/deadline: stale dl_yielded left set by dl_task_timer()
--

commit b274aa4dbc0a2822908373f43a14a8b8436d20eb
Author: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>

sched/deadline: Do not lose a throttled task switched out and back

This commit clears dl_se->dl_throttled in dl_task_timer() when a throttled
SCHED_DEADLINE task has been switched to another scheduling policy before
its replenishment timer fires, so that switching back to SCHED_DEADLINE
before the 0-lag time does not leave the task permanently throttled.

> diff --git a/kernel/sched/deadline.c b/kernel/sched/deadline.c
> index 30a52e42c26d8..d474fbfd9be6d 100644
> --- a/kernel/sched/deadline.c
> +++ b/kernel/sched/deadline.c
> @@ -1232,10 +1232,17 @@ static enum hrtimer_restart dl_task_timer(struct hrtimer *timer)
>  
>  	/*
>  	 * The task might have changed its scheduling policy to something
> -	 * different than SCHED_DEADLINE (through switched_from_dl()).
> +	 * different than SCHED_DEADLINE (through switched_from_dl()). It
> +	 * keeps its parameters until its 0-lag time and may come back to
> +	 * SCHED_DEADLINE before then, switched_to_dl() cancelling the
> +	 * inactive timer: it must not come back throttled, since this was
> +	 * its replenishment. Its deadline has passed: the enqueue starts a
> +	 * new period.
>  	 */
> -	if (!dl_task(p))
> +	if (!dl_task(p)) {
> +		dl_se->dl_throttled = 0;
>  		goto unlock;
> +	}

[Severity: Medium]
Could clearing only dl_se->dl_throttled here without calling
replenish_dl_entity(dl_se) forgive negative runtime overruns and leave
dl_se->deadline stale when the task switches back to SCHED_DEADLINE before
its 0-lag time?

The window between the replenishment timer and the inactive timer exists
specifically when a task has overrun its runtime (dl_se->runtime < 0),
making the 0-lag time later than dl_next_period(dl_se). Normal replenishment
in replenish_dl_entity() deducts that overrun from subsequent periods:

kernel/sched/deadline.c:replenish_dl_entity() {
	...
	while (dl_se->runtime <= 0) {
		dl_se->deadline += pi_of(dl_se)->dl_period;
		dl_se->runtime += pi_of(dl_se)->dl_runtime;
	}
	...
}

By only clearing dl_se->dl_throttled and leaving dl_se->deadline in the past
and dl_se->runtime negative, a task returning to SCHED_DEADLINE before its
0-lag time enters enqueue_dl_entity(), where setup_new_dl_entity() (on
ENQUEUE_MOVE) or update_dl_entity() (on ENQUEUE_WAKEUP) calls
replenish_dl_new_period(dl_se, rq):

kernel/sched/deadline.c:enqueue_dl_entity() {
	...
	} else if ((flags & ENQUEUE_MOVE) &&
		   !is_dl_boosted(dl_se) &&
		   dl_time_before(dl_se->deadline, rq_clock(rq_of_dl_se(dl_se)))) {
		setup_new_dl_entity(dl_se);
	}
	...
}

replenish_dl_new_period() unconditionally resets dl_se->runtime to the full
pi_of(dl_se)->dl_runtime rather than deducting the prior negative runtime
overrun, allowing the task to bypass bandwidth enforcement by switching
policies across its replenishment point.

In addition, in enqueue_dl_entity(), dl_check_constrained_dl() runs before
the ENQUEUE_MOVE branch:

kernel/sched/deadline.c:enqueue_dl_entity() {
	...
	if (!dl_se->dl_throttled && !dl_is_implicit(dl_se))
		dl_check_constrained_dl(dl_se);
	...
}

If the task returns with constrained-deadline parameters (for example, with
a larger dl_period passed to sched_setattr() so that dl_se->deadline <
rq_clock(rq) < dl_next_period(dl_se)), dl_check_constrained_dl() sees the
un-advanced dl_se->deadline and re-throttles the task before
setup_new_dl_entity() is reached. And if the task migrated to another CPU
while in SCHED_OTHER whose rq_clock(rq) has not yet strictly passed
dl_se->deadline when it switches back, dl_time_before(dl_se->deadline,
rq_clock(rq)) evaluates to false and the task is enqueued onto dl_rq with
dl_se->runtime <= 0.

[Severity: Medium]
What happens if the task had also called sched_yield() in the period where
it was throttled, leaving dl_se->dl_yielded set to 1 when dl_task_timer()
fires?

In yield_task_dl(), rq->donor->dl.dl_yielded = 1 is set before calling
update_curr_dl(rq) -> update_curr_dl_se():

kernel/sched/deadline.c:yield_task_dl() {
	...
	rq->donor->dl.dl_yielded = 1;

	update_rq_clock(rq);
	update_curr_dl(rq);
	...
}

If the elapsed execution time in that slice also pushes dl_se->runtime < 0,
update_curr_dl_se() throttles the task with both dl_se->dl_throttled == 1
and dl_se->dl_yielded == 1, and arms the inactive timer for a 0-lag time
later than the deadline when the task switches out of SCHED_DEADLINE.

Unlike replenish_dl_entity() and __dl_clear_params(), which clear both
dl_se->dl_yielded and dl_se->dl_throttled:

kernel/sched/deadline.c:replenish_dl_entity() {
	...
	if (dl_se->dl_yielded)
		dl_se->dl_yielded = 0;
	if (dl_se->dl_throttled)
		dl_se->dl_throttled = 0;
	...
}

neither the !dl_task(p) path in dl_task_timer() nor replenish_dl_new_period()
clears dl_se->dl_yielded. When the task switches back to SCHED_DEADLINE
before its 0-lag time, wouldn't it be enqueued with a stale
dl_se->dl_yielded == 1 and immediately get throttled again for an entire
new period on the next call to update_curr_dl_se()?

-- 
Sashiko AI review · https://sashiko.dev/#/patchset/cover.1793804635.git.mathieu.desnoyers@efficios.com?part=4

Re: [PATCH 09/12] sched/deadline: Do not take a waking task's bandwidth off a runqueue it left

[sashiko-bot]

Thank you for your contribution! Sashiko AI review found 2 potential issue(s) to consider:
- [High] sched/deadline: double add_rq_bw() in task_contending() on wake_list switch
- [Medium] sched/deadline: migrate_task_rq_dl() leaves dl_bw_offrq set for dl_runtime == 0
--

commit 38f78e09a172accddd40a9e36af4e6c19f0febc1
Author: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>

sched/deadline: Do not take a waking task's bandwidth off a runqueue it left

This commit adds a dl_bw_offrq bit to struct sched_dl_entity to track when a
waking deadline task has had its bandwidth removed from its previous runqueue
by migrate_task_rq_dl() but has not yet been enqueued on its target CPU. While
dl_bw_offrq is set, dl_change_utilization() and switched_from_dl() avoid
subtracting the task's bandwidth from the target CPU's runqueue before the
wakeup enqueue charges it via add_rq_bw().

> diff --git a/kernel/sched/deadline.c b/kernel/sched/deadline.c
> index 8ead9b050dfcf..a8906cf966401 100644
> --- a/kernel/sched/deadline.c
> +++ b/kernel/sched/deadline.c

[ ... ]

> @@ -2785,6 +2794,12 @@ static void migrate_task_rq_dl(struct task_struct *p, int new_cpu __maybe_unused
>  		cancel_inactive_timer(&p->dl);
>  	}
>  	sub_rq_bw(&p->dl, &rq->dl);
> +	/*
> +	 * Until the enqueue on the CPU it wakes on charges it there, which
> +	 * add_rq_bw() tells of, this bandwidth is on no runqueue: the rq of
> +	 * task_cpu() is not the one it was taken from.
> +	 */
> +	p->dl.dl_bw_offrq = 1;
>  	rq_unlock(rq, &rf);
>  }

[Severity: Medium]
What happens if a non-deadline task boosted via priority inheritance (with
p->dl.dl_runtime == 0) blocks and migrates on wakeup through
try_to_wake_up() -> set_task_cpu() -> migrate_task_rq_dl()?

Here migrate_task_rq_dl() unconditionally sets p->dl.dl_bw_offrq = 1, but
when the wakeup enqueues the task via enqueue_task_dl() ->
enqueue_dl_entity() -> task_contending(), task_contending() returns early
before calling add_rq_bw():

kernel/sched/deadline.c:task_contending() {
	if (dl_se->dl_runtime == 0)
		return;

	if (flags & ENQUEUE_MIGRATED)
		add_rq_bw(dl_se, dl_rq);

Because switched_from_dl() only clears dl_bw_offrq when !task_on_rq_queued(p),
won't p->dl.dl_bw_offrq remain stuck at 1 after the wakeup completes?

If the task later blocks while still PI-boosted in dl_sched_class and
sched_setattr() assigns it SCHED_DEADLINE parameters, __sched_setscheduler()
sees prev_class == next_class == &dl_sched_class and does not call
switched_to_dl(). Wouldn't the stale p->dl.dl_bw_offrq == 1 then cause
dl_change_utilization() or a subsequent switched_from_dl() while blocked to
skip updating rq->dl.this_bw?

> @@ -3736,7 +3751,9 @@ static void switched_from_dl(struct rq *rq, struct task_struct *p)
>  			dl_task_release_bw(p, dl_task_root_domain_cpu(p));
>  			released = true;
>  		}
> -		sub_rq_bw(&p->dl, &rq->dl);
> +		if (!p->dl.dl_bw_offrq)
> +			sub_rq_bw(&p->dl, &rq->dl);
> +		p->dl.dl_bw_offrq = 0;

[Severity: High]
Can this leak p->dl.dl_bw into the target CPU's rq->dl.this_bw when a task
queued on the target CPU's wake_list switches out of SCHED_DEADLINE and back
into SCHED_DEADLINE before sched_ttwu_pending() runs?

When try_to_wake_up() migrates a waking deadline task and queues it via
ttwu_queue_wakelist(), p->sched_remote_wakeup is set to 1 while
!task_on_rq_queued(p) and migrate_task_rq_dl() sets p->dl.dl_bw_offrq = 1.

If the task then leaves SCHED_DEADLINE before sched_ttwu_pending() runs,
switched_from_dl() sees p->dl.dl_bw_offrq == 1, skips sub_rq_bw(), and clears
p->dl.dl_bw_offrq = 0. If the task is then switched back to SCHED_DEADLINE
(or if a non-deadline task on the wake_list with p->sched_remote_wakeup == 1
switches to SCHED_DEADLINE) while still waiting on the wake_list,
switched_to_dl() charges the target CPU's rq->dl.this_bw immediately:

kernel/sched/deadline.c:switched_to_dl() {
	...
	/* If p is not queued we will update its parameters at next wakeup. */
	if (!task_on_rq_queued(p)) {
		add_rq_bw(&p->dl, &rq->dl);

		return;
	}

When sched_ttwu_pending() subsequently runs on the target CPU, it sees
p->sched_remote_wakeup == 1 and calls ttwu_do_activate() with WF_MIGRATED,
which passes ENQUEUE_MIGRATED into enqueue_task_dl() -> enqueue_dl_entity() ->
task_contending():

kernel/sched/deadline.c:task_contending() {
	...
	if (flags & ENQUEUE_MIGRATED)
		add_rq_bw(dl_se, dl_rq);

Since task_contending() checks (flags & ENQUEUE_MIGRATED) rather than
dl_se->dl_bw_offrq, won't it call add_rq_bw() a second time on the target
CPU's dl_rq even though switched_to_dl() already added p->dl.dl_bw and cleared
dl_bw_offrq?

-- 
Sashiko AI review · https://sashiko.dev/#/patchset/cover.1793804635.git.mathieu.desnoyers@efficios.com?part=9

Re: [PATCH 11/12] sched/deadline: Rebuild the root domains' accounting without cpusets too

[sashiko-bot]

Thank you for your contribution! Sashiko AI review found 3 potential issue(s) to consider:
- [High] sched/deadline: race between dl_rebuild_rd_accounting() and sched_dl_overflow()
- [High] sched/deadline: BUG_ON() in dl_add_task_root_domain() when isolated CPUs offline
- [High] sched/deadline: dl_get_task_effective_cpus() picks isolated CPU for hk tasks
--

commit c1e57d1e06a701583f3de7582594314893352edf
Author: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>

sched/deadline: Rebuild the root domains' accounting without cpusets too

This commit implements dl_rebuild_rd_accounting() in kernel/sched/deadline.c
for kernels built without CONFIG_CPUSETS by clearing the root domains and
walking all threads under tasklist_lock to re-add their deadline bandwidth.
It also moves the declaration of dl_rebuild_rd_accounting() from
include/linux/cpuset.h to include/linux/sched/deadline.h.

> diff --git a/kernel/sched/deadline.c b/kernel/sched/deadline.c
> index a8906cf966401..0ea902b9e5d09 100644
> --- a/kernel/sched/deadline.c
> +++ b/kernel/sched/deadline.c
> @@ -3668,6 +3668,28 @@ void dl_clear_root_domain(struct root_domain *rd)
>  		dl_server_add_bw(rd, i);
>  }
>  
> +#ifndef CONFIG_CPUSETS
> +/*
> + * Rebuild the root domains' accounting, where no cpuset holds the
> + * deadline tasks of each: they are found by walking them all, which
> + * dl_rebuild_rd_accounting() of the cpusets does per cpuset instead.
> + */
> +void dl_rebuild_rd_accounting(void)
> +{
> +	struct task_struct *g, *p;
> +
> +	lockdep_assert_cpus_held();
> +	lockdep_assert_held(&sched_domains_mutex);
> +
> +	dl_clear_root_domains();

[Severity: High]
What serializes this rebuild against concurrent __sched_setscheduler() ->
sched_dl_overflow() calls when CONFIG_CPUSETS is disabled?

With CONFIG_CPUSETS enabled, __sched_setscheduler() in
kernel/sched/syscalls.c calls cpuset_lock() when entering, leaving, or
updating SCHED_DEADLINE:

	if (dl_policy(policy) || dl_policy(p->policy)) {
		cpuset_locked = true;
		cpuset_lock();
	}

and sched_dl_overflow() in kernel/sched/deadline.c relies on cpuset_mutex to
prevent a rebuild from running concurrently:

	/*
	 * Back before its 0-lag time, the task still has the bandwidth it
	 * left with, which the new one replaces: removed from the root
	 * domain that keeps it (dl_task_release_bw()). A rebuild cannot
	 * run meanwhile: the caller holds cpuset_mutex.
	 */
	if (!err && dl_policy(policy) && !task_has_dl_policy(p)) {
		lockdep_assert_cpuset_lock_held();
		if (p->dl.dl_departed_cpu >= 0)
			dl_task_release_bw(p, -1);
		p->dl.dl_bw_gen = dl_bw_gen;
	}

When !CONFIG_CPUSETS, cpuset_lock() and lockdep_assert_cpuset_lock_held() in
include/linux/cpuset.h are no-op stubs, while dl_rebuild_rd_accounting() only
holds cpu_hotplug_lock and sched_domains_mutex, neither of which is taken by
__sched_setscheduler().

Without mutual exclusion between dl_rebuild_rd_accounting() and
__sched_setscheduler(), can they interleave and corrupt rd->dl_bw.total_bw?
For example:

1. A task entering SCHED_DEADLINE calls sched_dl_overflow(), which adds
new_bw to dl_b->total_bw under dl_b->lock and drops dl_b->lock before setting
p->dl.dl_bw_gen = dl_bw_gen and before __setparam_dl() updates p->dl.dl_bw
and p->prio. If dl_clear_root_domains() runs in that window, it increments
dl_bw_gen and resets rd->dl_bw.total_bw to 0 (wiping out new_bw), after which
sched_dl_overflow() writes the new dl_bw_gen into p->dl.dl_bw_gen. When
dl_add_task_root_domain() later visits p, it sees p->dl.dl_bw_gen ==
dl_bw_gen and skips it, leaving new_bw uncounted until p exits and underflows
total_bw.

2. If an existing SCHED_DEADLINE task updates its parameters after
dl_clear_root_domains() zeroes total_bw and before for_each_process_thread()
reaches p, sched_dl_overflow() adjusts total_bw by new_bw - old_bw without
updating p->dl.dl_bw_gen, __setparam_dl() sets p->dl.dl_bw = new_bw, and
dl_add_task_root_domain() subsequently adds new_bw a second time.

3. If a task switches out of SCHED_DEADLINE after dl_clear_root_domains() has
walked dl_departed_list and before for_each_process_thread() visits p,
switched_from_dl() moves p to dl_departed_list and clears its deadline
priority, so dl_add_task_root_domain() sees !dl_task(p) and drops its
bandwidth before its 0-lag time.

4. Between dl_clear_root_domains() and the end of the tasklist walk,
concurrent sched_dl_overflow() admission checks evaluate __dl_overflow()
against a zeroed or partially rebuilt total_bw.

> +
> +	read_lock(&tasklist_lock);
> +	for_each_process_thread(g, p)
> +		dl_add_task_root_domain(p);

[Severity: High]
Can walking all tasks with for_each_process_thread() trigger the
BUG_ON(cpu >= nr_cpu_ids) in dl_add_task_root_domain() when CPUs isolated via
isolcpus=domain are taken offline?

In kernel/sched/deadline.c, dl_add_task_root_domain() computes the effective
CPU mask and checks BUG_ON(cpu >= nr_cpu_ids) before checking
p->dl.dl_bw_gen, p->dl.dl_departed_cpu, or p->dl.dl_bw:

	raw_spin_lock_irqsave(&p->pi_lock, rf.flags);
	if (!dl_task(p) || dl_entity_is_special(&p->dl)) {
		raw_spin_unlock_irqrestore(&p->pi_lock, rf.flags);
		return;
	}

	msk = this_cpu_cpumask_var_ptr(local_cpu_mask_dl);
	dl_get_task_effective_cpus(p, msk);
	cpu = cpumask_first_and(cpu_active_mask, msk);
	BUG_ON(cpu >= nr_cpu_ids);

And dl_get_task_effective_cpus() handles HK_TYPE_DOMAIN isolation as follows:

	if (housekeeping_enabled(HK_TYPE_DOMAIN)) {
		if (!cpumask_intersects(p->cpus_ptr, hk_msk)) {
			/*
			 * CPUs isolated by isolcpu="domain" always belong to
			 * def_root_domain.
			 */
			cpumask_andnot(cpus, cpu_active_mask, hk_msk);
			return;
		}
	}

Because for_each_process_thread() visits every task in the system, it visits
unreaped EXIT_ZOMBIE deadline tasks whose bandwidth has already been released
or moved to dl_departed_list (where p->prio is still < MAX_DL_PRIO, so
dl_task(p) is true), as well as PI-boosted tasks with p->dl.dl_bw == 0.
Since those tasks carry no active bandwidth in def_root_domain to block
dl_bw_deactivate(), all isolated CPUs outside hk_msk can be taken offline.
When that happens, cpumask_andnot(cpus, cpu_active_mask, hk_msk) is empty,
cpumask_first_and(cpu_active_mask, msk) returns nr_cpu_ids, and
dl_add_task_root_domain() hits BUG_ON(cpu >= nr_cpu_ids).

[Severity: High]
Also in the dl_add_task_root_domain() -> dl_get_task_effective_cpus() path on
!CONFIG_CPUSETS, could housekeeping deadline tasks have their bandwidth
added to def_root_domain instead of the housekeeping root domain when
isolcpus=domain is used?

In dl_get_task_effective_cpus():

	hk_msk = housekeeping_cpumask(HK_TYPE_DOMAIN);
	if (housekeeping_enabled(HK_TYPE_DOMAIN)) {
		if (!cpumask_intersects(p->cpus_ptr, hk_msk)) {
			cpumask_andnot(cpus, cpu_active_mask, hk_msk);
			return;
		}
	}

	cpuset_cpus_allowed_locked(p, cpus);

When !CONFIG_CPUSETS, cpuset_cpus_allowed_locked() in include/linux/cpuset.h
copies task_cpu_possible_mask(p) into cpus without masking out the CPUs
isolated by HK_TYPE_DOMAIN:

static inline void cpuset_cpus_allowed_locked(struct task_struct *p,
					struct cpumask *mask)
{
	cpumask_copy(mask, task_cpu_possible_mask(p));
}

For a housekeeping deadline task where p->cpus_ptr intersects hk_msk,
dl_add_task_root_domain() then picks:

	cpu = cpumask_first_and(cpu_active_mask, msk);

If an active isolated CPU has a lower CPU number than the active housekeeping
CPUs (for example with isolcpus=domain,0), cpu resolves to CPU 0, whose
cpu_rq(cpu)->rd is def_root_domain rather than the housekeeping root domain.
Wouldn't that account the housekeeping task's bandwidth into def_root_domain
during the rebuild, and later underflow the housekeeping root domain's
total_bw when the task leaves SCHED_DEADLINE or exits?

-- 
Sashiko AI review · https://sashiko.dev/#/patchset/cover.1793804635.git.mathieu.desnoyers@efficios.com?part=11

Re: [PATCH 07/12] sched/deadline: Keep departing bandwidth across a root domain rebuild

[sashiko-bot]

Thank you for your contribution! Sashiko AI review found 4 potential issue(s) to consider:
- [High] sched/deadline: bandwidth leak and underflow in switched_to_dl() on PI boost
- [High] sched/deadline: dl_clear_root_domains() drops and resurrects departed bw
- [High] sched/deadline: exiting tasks lose or corrupt bandwidth across rd rebuild
- [High] sched/deadline: task_non_contending() uses task_cpu() instead of mask CPU
--

commit e37776f3c05c45d876702021f65c587c9806cb26
Author: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>

sched/deadline: Keep departing bandwidth across a root domain rebuild

This commit tracks tasks that leave SCHED_DEADLINE or die before their
0-lag time on a departed list associated with a CPU of their root domain,
and uses a rebuild generation counter to preserve or release their
bandwidth across root domain accounting rebuilds.

> diff --git a/kernel/sched/deadline.c b/kernel/sched/deadline.c
> index 3c57e5f5fc056..8ead9b050dfcf 100644
> --- a/kernel/sched/deadline.c
> +++ b/kernel/sched/deadline.c

[ ... ]

> @@ -217,6 +223,88 @@ __dl_overflow(struct dl_bw *dl_b, unsigned long cap, u64 old_bw, u64 new_bw)
>  	       cap_scale(dl_b->bw, cap) < dl_b->total_bw - old_bw + new_bw;
>  }
>  
> +/*
> + * A task that leaves SCHED_DEADLINE, or dies, before its 0-lag time keeps
> + * its bandwidth in total_bw until then: the inactive timer removes it. A
> + * rebuild of the root domains' accounting meanwhile (dl_clear_root_domains()
> + * and dl_add_task_root_domain(), on any change of the partitions or CPU
> + * hotplug) finds no such task among the deadline tasks of the cpusets: it
> + * puts that bandwidth back from dl_departed_list, which holds them from
> + * their departure to their timer, in the root domain each left, found by
> + * its mask then (dl_task_root_domain_cpu()), or by the CPU it dies on: the
> + * CPU it last ran on may be of another one, when it was moved asleep. The
> + * task may run anywhere meanwhile, as another policy; its timer holds a
> + * reference to it.
> + *
> + * dl_bw_gen counts the rebuilds, and each task records the one that last
> + * counted its bandwidth. A rebuild that dropped it since then leaves
> + * nothing to remove: the CPU recorded was no longer active, or the task
> + * exited while the rebuild ran, which the cpuset walk skips, and was not
> + * dead yet when the list was put back. Both counts, and the list, are under
> + * dl_departed_lock, taken with interrupts disabled (under the task's rq
> + * lock or pi_lock, or by the rebuild) and before any dl_bw lock.
> + */
> +static LIST_HEAD(dl_departed_list);
> +static DEFINE_RAW_SPINLOCK(dl_departed_lock);
> +static unsigned int dl_bw_gen;

[ ... ]

> +static void dl_task_release_bw(struct task_struct *p, int cpu)
> +{
> +	struct sched_dl_entity *dl_se = &p->dl;
> +	struct dl_bw *dl_b;
> +
> +	lockdep_assert_irqs_disabled();
> +	guard(raw_spinlock)(&dl_departed_lock);
> +	if (dl_se->dl_departed_cpu >= 0) {
> +		cpu = dl_se->dl_departed_cpu;
> +		dl_se->dl_departed_cpu = -1;
> +		list_del(&dl_se->dl_departed_node);
> +	}
> +	if (dl_se->dl_bw_gen == dl_bw_gen) {
> +		dl_b = dl_bw_of(cpu);
> +		raw_spin_lock(&dl_b->lock);
> +		__dl_sub(dl_b, dl_se->dl_bw, dl_bw_cpus(cpu));
> +		raw_spin_unlock(&dl_b->lock);
> +	}
> +	dl_se->dl_bw_gen = dl_bw_gen;
> +}

[Severity: High]
What happens when dl_rebuild_rd_accounting() runs while a SCHED_DEADLINE
task is in the middle of do_exit()?

In do_exit(), exit_signals() sets PF_EXITING and decrements signal->live to
0 near the beginning of task teardown, before exit_mm(), exit_files(),
exit_notify(), and cgroup_exit(), whereas do_task_dead() -> __schedule() ->
deactivate_task() -> dequeue_task_dl() -> task_non_contending() ->
dl_task_depart() only runs at the very end of do_exit().

If dl_rebuild_rd_accounting() runs during that window (or if the task
reaches do_task_dead() after dl_clear_root_domains() has walked
dl_departed_list, and unlinks from its cset before
dl_update_tasks_root_domain() walks it), dl_clear_root_domains() increments
dl_bw_gen without finding the task on dl_departed_list, and
dl_update_tasks_root_domain() calls css_task_iter_start(&cs->css, 0, &it)
without CSS_TASK_ITER_WITH_DEAD, which skips the task because PF_EXITING is
set and signal->live is 0.

Doesn't that cause three problems for an exiting deadline task?

1. Its bandwidth is dropped from total_bw while the task is still running
in do_exit() and before its 0-lag time.

2. When the task finally reaches do_task_dead() -> task_non_contending()
with zerolag_time >= 0, task_non_contending() unconditionally calls
dl_task_depart(p, task_cpu(p)) without checking whether p->dl.dl_bw_gen
matches dl_bw_gen. If a second rebuild runs before inactive_task_timer()
fires, dl_clear_root_domains() will add p->dl.dl_bw back into total_bw on
top of any bandwidth admitted after the first rebuild.

3. If the task is migrated while in do_exit() after the first rebuild
dropped its bandwidth (for example via set_cpus_allowed_dl() or
dl_task_offline_migration()), those paths subtract p->dl.dl_bw from the
source root domain without checking p->dl.dl_bw_gen == dl_bw_gen
(underflowing total_bw), and dl_task_offline_migration() adds p->dl.dl_bw
to later_rq->rd->dl_bw without updating p->dl.dl_bw_gen, so
dl_task_release_bw() later skips subtracting it and leaks p->dl.dl_bw in
later_rq->rd.

[ ... ]

> @@ -449,13 +537,9 @@ static void task_non_contending(struct sched_dl_entity *dl_se, bool dl_task)
>  				sub_running_bw(dl_se, dl_rq);
>  
>  			if (!dl_task || READ_ONCE(p->__state) == TASK_DEAD) {
> -				struct dl_bw *dl_b = dl_bw_of(task_cpu(p));
> -
>  				if (READ_ONCE(p->__state) == TASK_DEAD)
>  					sub_rq_bw(dl_se, &rq->dl);
> -				raw_spin_lock(&dl_b->lock);
> -				__dl_sub(dl_b, dl_se->dl_bw, dl_bw_cpus(task_cpu(p)));
> -				raw_spin_unlock(&dl_b->lock);
> +				dl_task_release_bw(p, task_cpu(p));
>  				__dl_clear_params(dl_se);
>  			}
>  		}
> @@ -464,8 +548,18 @@ static void task_non_contending(struct sched_dl_entity *dl_se, bool dl_task)
>  	}
>  
>  	dl_se->dl_non_contending = 1;
> -	if (!dl_server(dl_se))
> -		get_task_struct(dl_task_of(dl_se));
> +	if (!dl_server(dl_se)) {
> +		struct task_struct *p = dl_task_of(dl_se);
> +
> +		get_task_struct(p);
> +		/*
> +		 * Dying: its bandwidth is in the root domain of the CPU it
> +		 * runs on. switched_from_dl() records one that leaves
> +		 * SCHED_DEADLINE.
> +		 */
> +		if (READ_ONCE(p->__state) == TASK_DEAD)
> +			dl_task_depart(p, task_cpu(p));
> +	}

[Severity: High]
Should task_non_contending() use dl_task_root_domain_cpu(p) instead of
task_cpu(p) when calling dl_task_release_bw() and dl_task_depart()?

Suppose a SCHED_DEADLINE task p is running on CPU 0 in RD_0 (or has
is_migration_disabled(p) true) while it is moved to a cpuset partition in
RD_1:

  cpuset_can_attach()
    -> reserves p->dl.dl_bw in RD_1->dl_bw.total_bw
  cpuset_attach_task()
    -> set_cpus_allowed_ptr()
      -> __set_cpus_allowed_ptr_locked()
        -> do_set_cpus_allowed()
          -> set_cpus_allowed_dl()
            -> subtracts p->dl.dl_bw from RD_0->dl_bw.total_bw
            -> updates p->cpus_mask to RD_1
        -> affine_move_task()
          -> task_on_cpu(rq0, p) or is_migration_disabled(p) is true
          -> unlocks rq0 and queues migration_cpu_stop (or waits for
             migrate_enable())

Before migration_cpu_stop runs on CPU 0 (or while migration remains
disabled), p's bandwidth is already accounted in RD_1 (matching
p->cpus_mask), but task_cpu(p) is still CPU 0 in RD_0.

If p then exits into do_task_dead() -> dequeue_task_dl() ->
task_non_contending(&p->dl, true), or switches policy via
switched_from_dl() -> task_non_contending(&p->dl, false) when zerolag_time
< 0 or hrtimer_active(&dl_se->inactive_timer) is true, passing task_cpu(p)
causes dl_task_release_bw() or dl_task_depart() to target RD_0 instead of
RD_1, underflowing RD_0->dl_bw.total_bw and leaking p->dl.dl_bw in
RD_1->dl_bw.total_bw.

[ ... ]

> @@ -3542,9 +3653,37 @@ void dl_clear_root_domain(struct root_domain *rd)
>  		dl_server_add_bw(rd, i);
>  }
>  
> -void dl_clear_root_domain_cpu(int cpu)
> +/*
> + * Clear every root domain ahead of a rebuild of their accounting, which
> + * dl_add_task_root_domain() then fills with the deadline tasks of the
> + * cpusets: put back their servers, and the bandwidth of the tasks that
> + * left SCHED_DEADLINE, or died, before their 0-lag time, which no cpuset
> + * holds as a deadline task, in the root domain of the CPU recorded for
> + * each; dropped if it is no longer active.
> + */
> +void dl_clear_root_domains(void)
>  {
> -	dl_clear_root_domain(cpu_rq(cpu)->rd);
> +	struct sched_dl_entity *dl_se;
> +	u64 cookie = ++dl_cookie;
> +	struct dl_bw *dl_b;
> +	int cpu;
> +
> +	guard(raw_spinlock_irqsave)(&dl_departed_lock);
> +	dl_bw_gen++;
> +	for_each_possible_cpu(cpu) {
> +		if (!dl_bw_visited(cpu, cookie))
> +			dl_clear_root_domain(cpu_rq(cpu)->rd);
> +	}
> +	list_for_each_entry(dl_se, &dl_departed_list, dl_departed_node) {
> +		cpu = dl_se->dl_departed_cpu;
> +		if (!cpu_active(cpu))
> +			continue;
> +		dl_b = dl_bw_of(cpu);
> +		raw_spin_lock(&dl_b->lock);
> +		__dl_add(dl_b, dl_se->dl_bw, dl_bw_cpus(cpu));
> +		raw_spin_unlock(&dl_b->lock);
> +		dl_se->dl_bw_gen = dl_bw_gen;
> +	}
>  }

[Severity: High]
Can dl_clear_root_domains() prematurely drop departed bandwidth in a
multi-CPU root domain and later resurrect it?

When a task departs or dies in a root domain spanning CPUs 0 and 1,
dl_task_depart() records only a single CPU in dl_se->dl_departed_cpu (for
example, CPU 1). If CPU 1 is then taken offline via sched_cpu_deactivate(1)
before the task's 0-lag time while CPU 0 remains active in the same root
domain, dl_bw_deactivate(1) succeeds if CPU 0 has enough capacity for the
root domain's total_bw. However, when cpuset_cpu_inactive() ->
dl_rebuild_rd_accounting() -> dl_clear_root_domains() runs, cpu_active(1)
is false, so dl_clear_root_domains() skips dl_se and drops its bandwidth
from the still-active root domain before its 0-lag time.

In addition, when dl_clear_root_domains() skips an entry because
!cpu_active(cpu), the entry stays on dl_departed_list with its old
dl_bw_gen. If CPU 1 becomes active again and another rebuild runs before
inactive_task_timer() fires, dl_clear_root_domains() does not check whether
dl_se->dl_bw_gen matched the previous generation before dl_bw_gen++, so it
adds dl_se->dl_bw back into dl_bw_of(cpu) and updates dl_se->dl_bw_gen =
dl_bw_gen after that bandwidth was already dropped.

[ ... ]

> @@ -3642,6 +3786,16 @@ static void switched_from_dl(struct rq *rq, struct task_struct *p)
>  static void switched_to_dl(struct rq *rq, struct task_struct *p)
>  {
>  	cancel_inactive_timer(&p->dl);
> +	/*
> +	 * Boosted back into the class before its 0-lag time (a policy change
> +	 * released that bandwidth in sched_dl_overflow()): the inactive
> +	 * timer will not remove it, but its leaving the class again. That
> +	 * forgets the CPU recorded: moved to another root domain meanwhile,
> +	 * the task then removes the bandwidth from that one, as it did
> +	 * before departures were recorded.
> +	 */
> +	if (p->dl.dl_departed_cpu >= 0)
> +		dl_task_undepart(p);

[ ... ]

> @@ -3909,6 +4055,19 @@ int sched_dl_overflow(struct task_struct *p, int policy,
>  	}
>  	raw_spin_unlock(&dl_b->lock);
>  
> +	/*
> +	 * Back before its 0-lag time, the task still has the bandwidth it
> +	 * left with, which the new one replaces: removed from the root
> +	 * domain that keeps it (dl_task_release_bw()). A rebuild cannot
> +	 * run meanwhile: the caller holds cpuset_mutex.
> +	 */
> +	if (!err && dl_policy(policy) && !task_has_dl_policy(p)) {
> +		lockdep_assert_cpuset_lock_held();
> +		if (p->dl.dl_departed_cpu >= 0)
> +			dl_task_release_bw(p, -1);
> +		p->dl.dl_bw_gen = dl_bw_gen;
> +	}
> +
>  	return err;
>  }

[Severity: High]
Does calling dl_task_undepart(p) in switched_to_dl() when a departed task
is PI-boosted cause bandwidth leaks and cross-root-domain underflows?

When a SCHED_DEADLINE task p switches to SCHED_OTHER before its 0-lag time,
switched_from_dl() arms inactive_timer, keeps p->dl.dl_runtime and
p->dl.dl_bw set, and records the origin root domain CPU in
p->dl.dl_departed_cpu via dl_task_depart(). If p is then boosted into
dl_sched_class via rt_mutex_setprio() before the timer fires,
switched_to_dl() cancels inactive_timer and calls dl_task_undepart(p),
which resets p->dl.dl_departed_cpu to -1 and removes p from
dl_departed_list without releasing p->dl.dl_bw from the origin root domain:

1. If p is switched back to SCHED_DEADLINE via sched_setattr() while still
PI-boosted (!task_has_dl_policy(p) is true), sched_dl_overflow() adds
new_bw to dl_b->total_bw and then checks:

	if (p->dl.dl_departed_cpu >= 0)
		dl_task_release_bw(p, -1);

Because switched_to_dl() already set p->dl.dl_departed_cpu = -1 (or if p
was already PI-boosted when it earlier switched from SCHED_DEADLINE to
SCHED_OTHER, so switched_from_dl() never ran), dl_task_release_bw() is
skipped and __setparam_dl() overwrites p->dl.dl_bw with new_bw, permanently
leaking the old p->dl.dl_bw in total_bw (and in rq->dl.this_bw if p was not
queued when boosted).

2. If p migrated to another root domain (RD_B) while in SCHED_OTHER and is
then PI-boosted, dl_task_undepart(p) forgets the origin root domain (RD_A)
recorded in dl_departed_cpu. When p is later deboosted in RD_B,
switched_from_dl() releases or re-departs p->dl.dl_bw from RD_B via
dl_task_root_domain_cpu(p), underflowing RD_B->dl_bw.total_bw and leaking
the bandwidth in RD_A->dl_bw.total_bw.

3. If p is sleeping when PI-boosted and the waiter times out or is
interrupted while p is still sleeping (!task_on_rq_queued(p)), deboosting p
calls switched_from_dl() with p->dl.dl_non_contending == 0, which enters:

	} else if (p->dl.dl_runtime && !dl_entity_is_special(&p->dl)) {
		dl_task_release_bw(p, dl_task_root_domain_cpu(p));
		released = true;
	}

and releases p->dl.dl_bw immediately before p's 0-lag time.

4. If dl_clear_root_domains() runs while p is PI-boosted (so p is not on
dl_departed_list) and p is deboosted before dl_add_task_root_domain(p)
visits it, dl_add_task_root_domain(p) sees !dl_task(p) and returns early,
dropping p's bandwidth before its 0-lag time.

-- 
Sashiko AI review · https://sashiko.dev/#/patchset/cover.1793804635.git.mathieu.desnoyers@efficios.com?part=7

Re: [PATCH 12/12] selftests/sched: Add a test of SCHED_DEADLINE bandwidth accounting

[sashiko-bot]

Thank you for your contribution! Sashiko AI review found 8 potential issue(s) to consider:
- [Medium] selftests/sched: deadline_bw_test exceeds default 45s kselftest timeout
- [Medium] selftests/sched: hardcoded 64 KiB thread stack in probe() and hold()
- [Medium] selftests/sched: mix_worker() reuses r % 8 making r % 4 and r % 2 always 0
- [Medium] selftests/sched: overrun_group_death() triggers SIGXCPU before sibling setup
- [Medium] selftests/sched: cpu_up() in hotplug_departed() masks bandwidth corruption
- [Medium] selftests/sched: missing shm_lock_init() call in random_mix()
- [Medium] selftests/sched: return -1 from probe() when pthread_create() fails
- [Low] selftests/sched: silent KSFT_SKIP returns without reason strings
--

commit e47dbb10f477e11f4985642a757e69830e31cc5f
Author: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>

selftests/sched: Add a test of SCHED_DEADLINE bandwidth accounting

This commit adds the deadline_bw_test selftest with 43 test cases exercising
SCHED_DEADLINE bandwidth accounting across priority inheritance, parameter
changes, cpuset moves, task deaths, sched_yield(), runtime overruns, GRUB
bandwidth reclaiming, fair server changes, a randomized mix, and CPU hotplug.

> diff --git a/tools/testing/selftests/sched/Makefile b/tools/testing/selftests/sched/Makefile
> index 728e046b463c9..a32a0f7aa76b8 100644
> --- a/tools/testing/selftests/sched/Makefile
> +++ b/tools/testing/selftests/sched/Makefile
> @@ -10,6 +10,6 @@ LDLIBS += -lpthread
>  
>  TEST_GEN_FILES := cs_prctl_test
>  TEST_PROGS := cs_prctl_test
> -TEST_GEN_PROGS := deadline_switch_test deadline_rebuild_test
> +TEST_GEN_PROGS := deadline_switch_test deadline_rebuild_test deadline_bw_test

[Severity: Medium]
When deadline_bw_test is added to TEST_GEN_PROGS in
tools/testing/selftests/sched/Makefile without a companion
tools/testing/selftests/sched/settings file, the kselftest runner applies the
default 45-second timeout (kselftest_default_timeout=45 in
tools/testing/selftests/kselftest/runner.sh).

In main() -> run_p_cases(), the 43 sequential test cases perform unconditional
sleeps totaling over 74 seconds when all features are enabled (including 25
MEASURED_IN_P cases sleeping at least 900ms each across two probe() calls and
measured(), server_states() sleeping 9.9s, params_waking() sleeping 5.3s, and
random_mix() sleeping 5.3s), and over 51 seconds even when the debugfs and
hotplug cases are skipped.

Because deadline_bw_test does not handle SIGTERM, when runner.sh kills the
test after 45 seconds it exits without running remove_p(),
remove_partition(cg_q), server_restore(), or restoring cgroup.subtree_control,
leaving active cpuset partitions and modified fair_server parameters on the
system.

Should tools/testing/selftests/sched/settings be added with a higher timeout
(and a signal handler installed to clean up cgroups and fair_server state on
termination)?

> diff --git a/tools/testing/selftests/sched/deadline_bw_test.c b/tools/testing/selftests/sched/deadline_bw_test.c
> new file mode 100644
> index 0000000000000..d16aee10155b3
> --- /dev/null
> +++ b/tools/testing/selftests/sched/deadline_bw_test.c
[ ... ]
> +static int probe(const char *cg)
> +{
> +	int fd[2], n = -1, max = 16 * ncpus + 16;
> +	pid_t pid;
> +
> +	if (pipe(fd)) {
> +		ksft_print_msg("pipe: %s\n", strerror(errno));
> +		return -1;
> +	}
> +	pid = fork_child("the admission check");
> +	if (!pid) {
> +		struct probe_slot *s = calloc(max, sizeof(*s));
> +		pthread_attr_t a;
> +		int i, k = 0;
> +
> +		close(fd[0]);
> +		if (!s || sem_init(&probe_done, 0, 0) || pipe(probe_hold) ||
> +		    (cg && enter(cg, getpid())))
> +			_exit(1);
> +		if (pthread_attr_init(&a) || pthread_attr_setstacksize(&a, 64 * 1024))
> +			_exit(1);

[Severity: Medium]
On architectures where PTHREAD_STACK_MIN is larger than 64 KiB (for example,
ppc64le where PTHREAD_STACK_MIN is 128 KiB, or kernels configured with 64 KiB
pages), will pthread_attr_setstacksize(&a, 64 * 1024) fail with EINVAL in both
probe() and hold()?

In probe(), that causes the child to exit with 1 and probe() to return -1,
which causes measured() to skip all 25 MEASURED_IN_P cases and fails the
remaining cases that call probe() directly.

In hold(), the same call also logs strerror(errno) even though
pthread_attr_init() and pthread_attr_setstacksize() return the error number
directly rather than setting errno:

	if (pthread_attr_init(&a) || pthread_attr_setstacksize(&a, 64 * 1024)) {
		ksft_print_msg("pthread_attr: %s\n", strerror(errno));
		return -1;
	}

Should the stack size in probe() and hold() be clamped to at least
PTHREAD_STACK_MIN, and hold() pass the returned error code to strerror()?

> +		for (i = 0; i < max; i++) {
> +			if (pthread_create(&s[i].t, &a, probe_thread, &s[i]))
> +				break;

[Severity: Medium]
If pthread_create() fails partway through the admission loop in probe() (for
example with EAGAIN due to RLIMIT_NPROC, cgroup pids.max, or memory pressure
when probing across many CPUs), breaking out of the loop leaves k at the
number of threads created so far rather than setting k = -1.

Won't probe() then write that partial count k to the pipe and return it as a
valid admission count, causing callers like measured(), admits_in(), and
moves() to misreport a bandwidth leak or double-release?

[ ... ]
> +/* The deadline threads of overrun_group_death(). */
> +static void *og_thread(void *arg)
> +{
> +	switch ((int)(long)arg) {
> +	case 0:		/* overruns its runtime: SIGXCPU to the group */
> +		if (set_deadline_flags(0, 10 * NSEC_PER_MSEC, PERIOD,
> +				       SCHED_FLAG_DL_OVERRUN))
> +			_exit(1);
> +		spin_ns(30 * NSEC_PER_MSEC);
> +		break;
> +	case 1:		/* asleep, its 0-lag time past */
> +		if (set_deadline(0, 20 * NSEC_PER_MSEC, PERIOD))
> +			_exit(1);
> +		spin_ns(NSEC_PER_MSEC);
> +		break;
> +	case 2:		/* asleep, mostly before its 0-lag time */
> +		if (set_deadline(0, 15 * NSEC_PER_MSEC, PERIOD))
> +			_exit(1);
> +		for (;;) {
> +			spin_ns(3 * NSEC_PER_MSEC);
> +			sleep_ns(22 * NSEC_PER_MSEC);
> +		}
> +	}
> +	for (;;)
> +		pause();
> +}
> +
> +/*
> + * The SIGXCPU of an overrun kills the whole thread group: the bandwidth
> + * of its three deadline threads comes back.
> + */
> +static int overrun_group_death(void)
> +{
> +	pid_t pid = fork_child("a group of deadline threads");
> +	int i, status;
> +
> +	if (!pid) {
> +		pthread_t t;
> +
> +		for (i = 0; i < 3; i++)
> +			if (pthread_create(&t, NULL, og_thread, (void *)(long)i))
> +				_exit(1);
> +		for (;;)
> +			pause();
> +	}

[Severity: Medium]
overrun_group_death() runs inside cg_p, which is a single-CPU cpuset partition
root, and creates thread 0 first without waiting for threads 1 and 2 to reach
their sleeping states.

In og_thread(), thread 0 immediately enters SCHED_DEADLINE with a 10ms runtime
and 100ms period and calls spin_ns(30 * NSEC_PER_MSEC) on P's single CPU. Even
if threads 1 and 2 also enter SCHED_DEADLINE before thread 0 starts spinning,
all three share the same 100ms relative deadline so thread 0 has the earliest
deadline and monopolizes the single CPU until it overruns at 10ms and delivers
SIGXCPU to the thread group.

Doesn't this kill the process before threads 1 and 2 can spin and go to sleep
in their intended states?

[ ... ]
> +static pid_t mix_worker(int idx, unsigned int seed)
> +{
> +	static const uint64_t runtime[] = { 5, 10, 20, 30 };
> +	static const uint64_t period[] = { 50, 100 };
> +	static const uint64_t flag[] = { 0, SCHED_FLAG_RECLAIM, SCHED_FLAG_DL_OVERRUN };
> +	pid_t pid = fork_child("a worker of the mix");
> +
> +	if (!pid) {
> +		struct sigaction sa = { .sa_handler = catch_xcpu };
> +		int err;
> +
> +		if (sigaction(SIGXCPU, &sa, NULL))
> +			_exit(1);
> +		seed += idx;
> +		/*
> +		 * A refusal is part of the mix: each call below is made in
> +		 * whatever state the worker is in, and an error is what the
> +		 * kernel is entitled to answer.
> +		 */
> +		while (!mix_state[0]) {
> +			unsigned int r = rand_r(&seed);
> +
> +			switch (r % 8) {
> +			case 0:
> +				set_deadline_flags(0, runtime[r % 4] * NSEC_PER_MSEC,
> +						   period[r % 2] * NSEC_PER_MSEC,
> +						   flag[r % 3]);
> +				break;

[Severity: Medium]
In mix_worker(), case 0 of switch (r % 8) is only entered when r is a multiple
of 8. Because runtime[r % 4] and period[r % 2] use r directly without dividing
by 8, aren't r % 4 and r % 2 always 0 here, causing mix_worker() to only ever
select runtime[0] (5ms) and period[0] (50ms)?

[ ... ]
> +			case 5:
> +				err = pthread_mutex_trylock(shm_lock);
> +				if (err == EOWNERDEAD)	/* its owner died holding it */
> +					err = pthread_mutex_consistent(shm_lock);
> +				if (!err) {
> +					spin_ns(NSEC_PER_MSEC);
> +					if (pthread_mutex_unlock(shm_lock))
> +						_exit(1);
> +				}
> +				break;
[ ... ]
> +static int random_mix(void)
> +{
[ ... ]
> +	mix_state = mv_state + 16;
> +	for (i = 0; i <= MIX_WORKERS; i++)
> +		mix_state[i] = 0;
> +	for (i = 0; i < MIX_WORKERS; i++) {
> +		pid[i] = mix_worker(i, seed);
> +		if (pid[i] < 0) {
> +			ret = KSFT_FAIL;
> +			goto out;
> +		}
> +	}

[Severity: Medium]
In random_mix(), the mix_worker() child processes lock and unlock shm_lock
across processes while random_mix() periodically kills workers with SIGKILL,
but random_mix() never calls shm_lock_init().

In main(), shm_lock is only pointed at zero-initialized MAP_SHARED memory:

	shm_lock = (pthread_mutex_t *)((char *)mv_state + 256);

shm_lock_init() (which configures PTHREAD_PROCESS_SHARED,
PTHREAD_PRIO_INHERIT, and PTHREAD_MUTEX_ROBUST) is only called inside
pi_death() for the earlier death_pi_* cases. If the death_pi_* cases were
skipped in measured(), or if shm_lock_init() failed there, shm_lock remains a
zero-initialized process-private non-robust mutex when random_mix() runs; and
if an earlier death_pi_* case failed before its waiter recovered and unlocked
shm_lock, shm_lock enters random_mix() in an inconsistent or unrecoverable
state.

Should random_mix() call shm_lock_init() (or skip case 5 in mix_worker() when
shm_lock_init() fails)?

[ ... ]
> +static int hotplug_departed(void)
> +{
> +	int base = probe(NULL), after, cpu, ret = KSFT_PASS;
> +	pid_t pid;
> +
> +	mv_state[0] = 0;
> +	mv_state[1] = 0;
> +	pid = mover(MV_THROTTLED, 40 * NSEC_PER_MSEC);
> +	if (pid < 0 || child_up("a departing deadline task", 0)) {
> +		reap(pid);
> +		return KSFT_FAIL;
> +	}
> +	sleep_ns(PERIOD / 2);
> +	/* Running and queued: its bandwidth stays until its 0-lag time. */
> +	if (set_other(pid))
> +		ret = KSFT_FAIL;
> +	cpu = task_cpu_of(pid);
> +	if (cpu <= 0) {
> +		cpu_set_t set;
> +
> +		/* Out of the class now: it may be moved to the CPU we offline. */
> +		cpu = hp_cpu;
> +		CPU_ZERO(&set);
> +		CPU_SET(cpu, &set);
> +		if (sched_setaffinity(pid, sizeof(set), &set))
> +			ret = KSFT_FAIL;
> +	}
> +	if (ret == KSFT_PASS && cpu_online(cpu, 0)) {
> +		ksft_print_msg("offline of CPU %d refused\n", cpu);
> +		ret = KSFT_FAIL;
> +	}
> +	sleep_ns(2 * PERIOD);
> +	cpu_up(cpu);
> +	reap(pid);
> +	sleep_ns(3 * PERIOD);
> +	after = probe(NULL);

[Severity: Medium]
In hotplug_departed(), after offlining cpu and sleeping 2 * PERIOD (so
inactive_task_timer() has already fired and cleared the departed task's
deadline parameters), the test calls cpu_up(cpu) before calling
after = probe(NULL).

Doesn't bringing cpu back online trigger dl_rebuild_rd_accounting() ->
dl_clear_root_domains(), resetting the root domain's total_bw to 0 and
recomputing it from scratch before probe(NULL) measures it, which masks any
total_bw leak or underflow that occurred when the inactive timer fired while
cpu was offline?

Also, since pid runs in the root cgroup with all online CPUs in its affinity
mask when set_other(pid) is called, switched_from_dl() ->
dl_task_root_domain_cpu() picks the first CPU in pid's cpus_mask (CPU 0) as
dl_departed_cpu rather than the CPU offlined here. Should probe(NULL) be
checked while cpu is still offline (or should pid's affinity be restricted to
include cpu and exclude CPU 0 before entering SCHED_DEADLINE)?

[ ... ]
> +static void report(const char *name, int ret)
> +{
> +	if (ret == KSFT_PASS)
> +		ksft_test_result_pass("%s\n", name);
> +	else if (ret == KSFT_SKIP)
> +		ksft_test_result_skip("%s\n", name);
> +	else
> +		ksft_test_result_fail("%s\n", name);
> +}

[Severity: Low]
In report(), ksft_test_result_skip("%s\n", name) only prints the test name,
and many of the KSFT_SKIP return paths (such as in run_in(), params_refused(),
params_keep_class_change(), yield_switched_out(), overrun_caught(),
reclaim_runs(), reclaim_switched(), server_params(), server_rebuilds(),
server_states(), server_reclaim(), params_waking(), random_mix(),
hotplug_refused(), hotplug_server(), and hotplug_server_refused()) return
KSFT_SKIP without printing why the test was skipped.

Could the skip paths pass or log a reason string explaining which prerequisite
was missing, per kselftest conventions?

-- 
Sashiko AI review · https://sashiko.dev/#/patchset/cover.1793804635.git.mathieu.desnoyers@efficios.com?part=12

Re: [PATCH 01/12] sched: Reject SCHED_FLAG_KEEP_PARAMS before reserving deadline bandwidth

[Mathieu Desnoyers]

On 2026-11-04 10:30, sashiko-bot@kernel.org wrote:
[...]
> 
> Should __sched_setscheduler() also reject SCHED_FLAG_KEEP_PARAMS when
> policy != p->policy, and skip sched_dl_overflow() when
> SCHED_FLAG_KEEP_PARAMS is set?
Both, and the first one is reproducible. Thank you, this is a real bug
and not the one patch 1 fixes.

The boosted case, confirmed: __normal_prio(SCHED_DEADLINE) gives
MAX_DL_PRIO - 1, so next_class is &dl_sched_class, and a task that
priority inheritance has boosted is of that class already. prev_class ==
next_class, so the check of commit 8a70415351ba ("sched: Reject
SCHED_FLAG_KEEP_PARAMS when it would change scheduling class") does not
fire, sched_dl_overflow() takes its first branch (p->policy is still
SCHED_NORMAL, so !task_has_dl_policy(p)) and adds the bandwidth of the
request, and the skipped __setscheduler_params() never gives it to the
task. Its dl_bw stays 0, so switched_from_dl() has nothing to release at
the deboost.

A SCHED_OTHER owner of a PTHREAD_PRIO_INHERIT mutex with a slice of
40ms, boosted by a deadline waiter blocked on it, with one
sched_setattr(SCHED_DEADLINE | SCHED_FLAG_KEEP_PARAMS) on the owner:

   total_bw 419424 -> 838854 (+419430, 0.4 of a CPU), and there to stay

in 8-CPU VMs, on v7.4-rc1 with the four deadline fixes of sched/urgent
as on this series, so it predates both.

The stale parameters: also real, by reading. sys_sched_setattr() fills
the request in from the task (get_params()) with no lock held, and
dl_param_changed() then takes the stale copy for a change, so
sched_dl_overflow() moves total_bw, and this_bw and running_bw through
dl_change_utilization(), to a bandwidth the task does not have; the
release at its 0-lag time takes the task's own dl_bw and leaves the
difference behind. I have not reproduced that one: it needs a parameter
change of the task to land inside the window.

v2 will carry both fixes as two patches after patch 1:

  - refuse SCHED_FLAG_KEEP_PARAMS that would change the policy, where
    only a class change was refused before. This also closes the boosted
    case, and it stops the kernel from answering 0 to a request it
    carries out by half: SCHED_OTHER to SCHED_BATCH with
    SCHED_FLAG_KEEP_PARAMS returns 0 today and leaves the policy alone.
    That is an ABI change, so say if you would rather keep accepting it;
  - skip sched_dl_overflow() when SCHED_FLAG_KEEP_PARAMS is set, since
    there is nothing to admit for parameters that are kept. This is what
    closes the stale-parameter window.

Both carry Fixes: a509a7cd7974 ("sched/uclamp: Extend sched_setattr() to
support utilization clamping"), which added the flag and the skip of
__setscheduler_params(), and the selftest of patch 12 gains a case for
the boosted one (params_keep_boosted).

Thanks,

Mathieu

-- 
Mathieu Desnoyers
EfficiOS Inc.
https://www.efficios.com

Re: [PATCH 00/12] sched/deadline: bandwidth accounting fixes and selftests

[Mathieu Desnoyers]

On 2026-11-04 10:10, Mathieu Desnoyers wrote:
> Hi Juri,
> 
> Please find in this series eight fixes to SCHED_DEADLINE bandwidth
> accounting, on top of your four in sched/urgent, with the selftests that
> catch them.
I'm taking care of issues found by Sashiko, including additional
preexisting bugs. I'm also taking care of yet more preexisting
sched deadline bugs identified by a round of Fable review
over my updated series.

v2 will include fixes for 17 sched deadline bugs, most of which have
reproducers.

Thanks,

Mathieu

-- 
Mathieu Desnoyers
EfficiOS Inc.
https://www.efficios.com