Re: [PATCH v5 13/29] sched/deadline: Keep departing bandwidth across a root domain rebuild

[Juri Lelli]

Hello,

On 08/11/26 13:53, Mathieu Desnoyers wrote:
> A task that leaves SCHED_DEADLINE, or dies, keeps its bandwidth in
> total_bw until its 0-lag time. This keeps admission control on the safe
> side. Then inactive_task_timer() removes it from the root domain of the
> task's CPU. Two things break this:
> 
>  - A rebuild of the accounting clears every root domain, then adds back
>    the deadline tasks of the cpusets. It misses a task out of the
>    class, or a dead one. Their bandwidth is dropped, and the timer
>    removes it again.
>  - A task out of the class can also move to another root domain. The
>    timer then takes total_bw from that one, which never had it.
> 
> Either way, a root domain admits deadline tasks beyond its capacity
> until the next rebuild.
> 
> Fix this with dl_departed_list. A departing task goes on it with the
> CPU it is on. A rebuild puts its bandwidth back in that CPU's root
> domain. The timer removes it from there, and so does
> sched_dl_overflow() for a task back in the class.
> 
> A rebuild still drops the bandwidth of a task whose CPU is inactive, or
> that dies during the rebuild. Each task records a count of the
> rebuilds, dl_bw_gen, with its bandwidth. The timer removes nothing if a
> rebuild came since.
> 
> Make dl_cookie and dl_bw_visited() static: only deadline.c uses them.
> 
> deadline_rebuild_test, added later in this series, fails every time on
> v7.3 and v7.4-rc1 kernels. A one-CPU partition root admits two tasks of
> 600ms every second there, where it has room for one. It passes with
> this patch.
> 
> Fixes: 387e31300b57 ("sched/deadline: Fix the update of the total -deadline utilization")
> Fixes: f9a25f776d78 ("cpusets: Rebuild root domain deadline accounting information")
> Cc: stable@xxxxxxxxxxxxxxx
> Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@xxxxxxxxxxxx>
> ---

...

> +/*
> + * A task that leaves SCHED_DEADLINE, or dies, before its 0-lag time keeps
> + * its bandwidth in total_bw until that time. Then the inactive timer
> + * removes it. Meanwhile the task may run anywhere, under another policy.
> + * The timer holds a reference to it.
> + *
> + * A rebuild of the root domains' accounting (dl_clear_root_domains() and
> + * dl_add_task_root_domain()) does not find such a task among the deadline
> + * tasks of the cpusets. So dl_departed_list holds these tasks, from their
> + * departure to their timer. The rebuild puts their bandwidth back in the
> + * root domain of the CPU each one was on when it left.
> + *
> + * dl_bw_gen counts the rebuilds. Each task records its value when its
> + * bandwidth is counted. If a rebuild dropped the bandwidth since, there
> + * is nothing to remove. A rebuild drops it when the CPU recorded is no
> + * longer active. It also drops the bandwidth of a task that dies while
> + * the rebuild runs. The cpuset walk skips that task, and it was not dead
> + * yet when the list was put back.

It took me a bit of staring to (hopefully) understand better how
dl_bw_gen works, maybe the following can help others?

 /*
  * dl_bw_gen numbers the rebuilds of the accounting: how many times the
  * root domains were wiped and reconstructed (dl_clear_root_domain
  * increments it). A task records the number of its last definite
  * state, counted or settled. That number dates the state:
  *
  *  - Current: the bandwidth is counted, or a release settled it since
  *    the rebuild began. A release subtracts; the walk of the cpusets
  *    skips.
  *  - One behind: the clear that just ran wiped it. The rebuild puts
  *    it back.
  *  - Older: an earlier rebuild dropped it. Leave it out; its release
  *    removes nothing.
  *
  * Only equalities are compared, so the wrap of the counter is
  * harmless.
  */

> + *
> + * dl_departed_lock protects the list and both counts. Take it with
> + * interrupts disabled, under the task's rq lock or pi_lock or in 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;

...

> +/*
> + * Clear every root domain before a rebuild of their accounting, and count
> + * the rebuild in dl_bw_gen. Put back the bandwidth of their servers. Put
> + * back the bandwidth of the tasks on dl_departed_list, which no cpuset
> + * holds as deadline tasks. Put each in the root domain of the CPU
> + * recorded for it, or drop it if that CPU is not active.
> + * dl_add_task_root_domain() then adds the deadline tasks of the cpusets.
> + */
> +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;
> +		/*
> +		 * Skip bandwidth that an earlier rebuild dropped. It is not
> +		 * counted now, and its release removes nothing
> +		 * (dl_task_release_bw()).
> +		 */
> +		if (dl_se->dl_bw_gen != dl_bw_gen - 1)
> +			continue;
> +		if (!cpu_active(cpu))
> +			continue;

Maybe additional info can again help (before the above)?

 /*
  * Drop the bandwidth of a task whose CPU is inactive.
  * That CPU no longer identifies the root domain that
  * counts it: a CPU going offline sits in the default root
  * domain by then, and the old one cannot be found back
  * from the recorded number. The release then removes
  * nothing, and no later rebuild restores it.
  */

> +		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_to_dl(struct rq *rq, struct task_struct *p)
>  {
>  	cancel_inactive_timer(&p->dl);
> +	/*
> +	 * A task on the departed list gets here when priority inheritance
> +	 * boosts it back into the class before its 0-lag time. (A policy change
> +	 * took it off the list in sched_dl_overflow().) The inactive timer no
> +	 * longer removes its bandwidth: the task does when it leaves the class
> +	 * again. So take it off the list. If the task moved to another root
> +	 * domain meanwhile, it then takes the bandwidth from that root domain
> +	 * instead.
> +	 */
> +	if (p->dl.dl_departed_cpu >= 0)
> +		dl_task_undepart(p);

Can something like the following happen? And do we actually have a test
for it?

1. T departs. A SCHED_DEADLINE task with bandwidth X leaves the class
asleep, 0-lag still ahead. Per the design, X stays counted in rd(A)'s
total_bw; T goes on dl_departed_list with dl_departed_cpu = A, and the
inactive timer is armed as the designated releaser. So far so good — the
record says "rd( A) owes X on T's behalf."

2. T migrates. T is now a fair task; it wakes and gets placed on a CPU
in a different root domain, rd(B). task_cpu(T) = B.

3. T is PI-boosted back. A deadline waiter blocks on a mutex T holds ->
rt_mutex_setprio -> class change -> switched_to_dl():
   - cancel_inactive_timer() — the designated releaser is cancelled;
   - dl_task_undepart() — T is delisted and dl_departed_cpu is reset to −1.

   X is still sitting in rd(A)'s total_bw, but nothing anywhere
   remembers that. T runs in rd(B) on its donor's reservation.

4. The boost ends. T is deboosted out of the class -> switched_from_dl()
-> task_non_contending() -> dl_task_release_bw(p, task_cpu(p)). T is not on
the departed list, so the passed-in CPU is used: X is subtracted from
rd(B).

...

Apart from the above, the proposed approach looks alright. I now wonder,
though, if an overall different scheme might make more sense. The
half-baked solution we have today for rebuilding bandwidth information
after domain changes is based on cpusets keeping track of DEADLINE tasks
(with the indirect cpu <-> rd association complicating things further).
With dl_departed_list, we now have one half of a per-domain membership
structure; the accounted current tasks are the other half. Wouldn't it
be better to move to a single list of accounted tasks (current and
departed alike), keyed by their recorded home CPU, which turns the
rebuild from a reconstruction into a re-partition? The dl_bw_gen
machinery and the cpuset walk would both go away. I understand this
would require some major restructuring of a number of patches in this
set, so maybe we can think of doing it after this set lands (or the
majority of the patches in here). Unless you are open to trying the idea
(if it makes any sense) and see if it simplifies things?

Thanks,
Juri