[PATCH v2 6/8] sched/deadline, topology: Avoid O(N^2) dl_server bandwidth walks during root_domain rebuilds

[sashiko-bot at kernel.org]

Thank you for your contribution! Sashiko AI review found 2 potential issue(s) to consider:
- [High] sched/deadline: dl_rebuild_rd_accounting() drops TASK_DEAD inactive_timer bw
- [High] sched/deadline: unskipped zero-dl_bw tasks in dl_add_task_root_domain()
--

commit e4cc8155c8ec900e6f7e52f8baebd0b6ab370fff
Author: Pasha Tatashin <pasha.tatashin at soleen.com>

sched/deadline, topology: Avoid O(N^2) dl_server bandwidth walks during root_domain rebuilds

This commit removes redundant __dl_server_attach_root() calls from
rq_attach_root() and replaces the nested O(N^2) loop in dl_clear_root_domain()
with an O(N) accumulation and update pass. It also adds a !CONFIG_CPUSETS
implementation of dl_rebuild_rd_accounting() and skips TASK_DEAD tasks on
inactive CPUs in dl_add_task_root_domain().

> diff --git a/kernel/sched/deadline.c b/kernel/sched/deadline.c
> index c0ebdcde5fe5d..c8847e1ea55a0 100644
> --- a/kernel/sched/deadline.c
> +++ b/kernel/sched/deadline.c
[ ... ]
> @@ -3433,7 +3415,8 @@ void dl_add_task_root_domain(struct task_struct *p)
>  	struct cpumask *msk;
>  
>  	raw_spin_lock_irqsave(&p->pi_lock, rf.flags);
> -	if (!dl_task(p) || dl_entity_is_special(&p->dl)) {
> +	if (!dl_task(p) || dl_entity_is_special(&p->dl) ||
> +	    (READ_ONCE(p->__state) == TASK_DEAD && !cpu_active(task_cpu(p)))) {
>  		raw_spin_unlock_irqrestore(&p->pi_lock, rf.flags);
>  		return;
>  	}

[Severity: High]
Can this trigger the BUG_ON(cpu >= nr_cpu_ids) just below in
dl_add_task_root_domain() for tasks where dl_task(p) is true, but
p->dl.dl_bw == 0?

During CPU hotplug or sched domain rebuilds, partition_sched_domains_locked()
calls dl_rebuild_rd_accounting() -> dl_add_task_root_domain(p) on tasks where
dl_prio(p->prio) / dl_task(p) is true:

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);
}

In dl_get_task_effective_cpus(), if p->cpus_ptr only intersects with
isolcpus=domain CPUs, it returns the active isolated CPUs:

kernel/sched/deadline.c: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;
		}
	}
	...
}

Normally, dl_bw_deactivate() blocks deactivating the last CPU in that domain
while reserved task bandwidth (total_bw - dl_server_bw) is non-zero. However,
dl_task(p) can be true while p->dl.dl_bw == 0 in two situations:

1. A non-deadline task (!task_has_dl_policy(p)) is PI-boosted by a
   SCHED_DEADLINE waiter via rt_mutex_setprio(), which sets
   p->prio = MAX_DL_PRIO - 1 while p->dl.dl_bw remains 0.

2. An exiting SCHED_DEADLINE task (p->__state == TASK_DEAD) has already had
   its bandwidth subtracted and cleared to p->dl.dl_bw = 0 by
   __dl_clear_params(&p->dl) in task_non_contending() or
   inactive_task_timer(), leaving p->prio as MAX_DL_PRIO - 1 while the
   unreaped zombie remains on the process/thread list.

Because p->dl.dl_bw == 0, dl_bw_deactivate() sees total_bw - dl_server_bw == 0
and permits all isolcpus=domain CPUs to be taken offline.

The new check only skips TASK_DEAD tasks when !cpu_active(task_cpu(p)). It
does not filter out PI-boosted non-DL tasks (where p->__state != TASK_DEAD,
such as a task blocked on a PI futex while affine to an isolated CPU) or
TASK_DEAD zombies whose task_cpu(p) is still active while p->cpus_ptr is
restricted to now-offline isolcpus=domain CPUs. For those tasks,
dl_get_task_effective_cpus() returns an empty mask and cpumask_first_and()
returns nr_cpu_ids, hitting BUG_ON(cpu >= nr_cpu_ids) just to add
p->dl.dl_bw == 0.

Should dl_add_task_root_domain() check !p->dl.dl_bw (or !task_has_dl_policy(p))
before computing the effective CPU mask?

[ ... ]
> @@ -3510,6 +3504,33 @@ void dl_clear_root_domain_cpu(int cpu)
>  	dl_clear_root_domain(cpu_rq(cpu)->rd);
>  }
>  
> +#ifndef CONFIG_CPUSETS
> +void dl_rebuild_rd_accounting(void)
> +{
> +	struct task_struct *g, *p;
> +	u64 cookie = ++dl_cookie;
> +	int cpu;
> +
> +	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_domain_cpu(cpu);
> +	}
> +	for_each_process_thread(g, p) {
> +		/* Racy pre-check; dl_add_task_root_domain() rechecks under pi_lock. */
> +		if (!dl_prio(READ_ONCE(p->prio)))
> +			continue;
> +		dl_add_task_root_domain(p);
> +	}
> +	rcu_read_unlock();
> +}
> +#endif

[Severity: High]
Can dl_rebuild_rd_accounting() drop the bandwidth of a TASK_DEAD
SCHED_DEADLINE task whose p->dl.inactive_timer is still armed, leading to an
underflow of rd->dl_bw.total_bw or a divide-by-zero in inactive_task_timer()?

When a running SCHED_DEADLINE task p exits via do_exit() -> do_task_dead() ->
__schedule() -> dequeue_task_dl() -> dequeue_dl_entity() ->
task_non_contending(&p->dl, true), if its 0-lag time is in the future,
task_non_contending() does not subtract p->dl.dl_bw immediately. Instead, it
sets p->dl.dl_non_contending = 1, takes a reference with get_task_struct(p),
and arms p->dl.inactive_timer.

When p->dl.inactive_timer later fires, inactive_task_timer() unconditionally
subtracts p->dl.dl_bw:

kernel/sched/deadline.c:inactive_task_timer() {
	...
	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_clear_params(dl_se);

		goto unlock;
	}
}

There appear to be two ways a root domain rebuild loses p->dl.dl_bw while
p->dl.inactive_timer is still pending:

1. In the new !CONFIG_CPUSETS dl_rebuild_rd_accounting(),
   dl_clear_root_domain() resets rd->dl_bw.total_bw to only the dl_server
   bandwidth and rebuilds task bandwidth via for_each_process_thread(g, p).
   If p was a sub-thread, autoreaped, or already reaped by wait(),
   release_task() -> __exit_signal() -> __unhash_process() has already removed
   p from the process/thread lists before p->dl.inactive_timer expires.
   for_each_process_thread(g, p) will not visit p, so p->dl.dl_bw is omitted
   from rd->dl_bw.total_bw, and when inactive_task_timer() later calls
   __dl_sub(), it underflows rd->dl_bw.total_bw and inflates rq->dl.extra_bw.

2. Even if p is still an unwaited zombie in for_each_process_thread(g, p),
   the new (READ_ONCE(p->__state) == TASK_DEAD && !cpu_active(task_cpu(p)))
   check in dl_add_task_root_domain() skips p when task_cpu(p) is deactivated
   during CPU offline while p->dl.inactive_timer is armed. That drops
   p->dl.dl_bw from the active root domain on rebuild, and if
   inactive_task_timer() fires after task_cpu(p) is attached to
   def_root_domain, __dl_sub() underflows def_root_domain.dl_bw.total_bw and
   divides by dl_bw_cpus(task_cpu(p)) == 0 when no isolated CPUs are active in
   def_root_domain.

_________________
_________________
_________________

-- 
Sashiko AI review · https://sashiko.dev/#/patchset/20261019011446.834487-1-pasha.tatashin@soleen.com?part=6