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

[Pasha Tatashin]

On 10-15 15:57, sashiko-bot at kernel.org wrote:
> Thank you for your contribution! Sashiko AI review found 3 potential issue(s) to consider:
> - [High] sched/deadline: Concurrent sched_setattr() during dl_rebuild_rd_accounting() corrupts bandwidth (!CONFIG_CPUSETS)
> - [Medium] sched/deadline: root domain bandwidth leak for DEAD tasks on offline CPUs
> - [Medium] sched/deadline: lockless u64 write to extra_bw causes data race and torn reads
> --
> 
> commit 2fcbfb40fdf44ef2a7ddc6709657336b0c7fb178
> 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 reduces the O(N^2) complexity of dl_server bandwidth walks during
> root_domain rebuilds by accumulating the total bandwidth in a single pass. It
> also introduces a !CONFIG_CPUSETS implementation of dl_rebuild_rd_accounting()
> to fix an issue where SCHED_DEADLINE task bandwidth was not accounted for on
> rebuilds.
> 
> > diff --git a/kernel/sched/deadline.c b/kernel/sched/deadline.c
> > index 857dbe3519a86..01f2f24e3b814 100644
> > --- a/kernel/sched/deadline.c
> > +++ b/kernel/sched/deadline.c
> [ ... ]
> > @@ -3480,26 +3466,32 @@ static u64 dl_server_read_bw(int cpu)
> >  	return dl_bw;
> >  }
> >  
> > -void dl_clear_root_domain(struct root_domain *rd)
> > +static void dl_clear_root_domain(struct root_domain *rd)
> >  {
> > -	int i;
> > +	u64 total_bw = 0;
> > +	s64 extra_bw = 0;
> > +	int i, cpus;
> >  
> >  	guard(raw_spinlock_irqsave)(&rd->dl_bw.lock);
> >  
> [ ... ]
> > +	rd->dl_bw.total_bw = total_bw;
> > +	for_each_cpu(i, rd->span) {
> > +		struct rq *rq = cpu_rq(i);
> > +
> > +		rq->dl.extra_bw = rq->dl.max_bw;
> > +		if (cpu_active(i))
> > +			rq->dl.extra_bw += extra_bw;
> 
> [Severity: Medium]
> Can this lockless u64 write to extra_bw cause a data race and torn reads with
> grub_reclaim()?
> 
> This updates rq->dl.extra_bw remotely holding only rd->dl_bw.lock. Concurrently,
> grub_reclaim() reads rq->dl.extra_bw while holding only the local rq->lock.
> 
> Because extra_bw is a u64 and can be a negative delta, 32-bit architectures
> process the write as two 32-bit stores. A torn read by grub_reclaim() could
> observe mismatched upper and lower halves, producing an incorrect bandwidth
> value that miscalculates DL task runtime.
> 
> Additionally, splitting the update into two distinct non-atomic assignments
> widens the race window.
> 
> > +	}
> >  }
> >  
> >  void dl_clear_root_domain_cpu(int cpu)
> [ ... ]
> > @@ -3507,6 +3499,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);
> 
> [Severity: High]
> Does this allow a race with concurrent __sched_setscheduler()?
> 
> In a kernel without CONFIG_CPUSETS, cpuset_lock() is an empty no-op stub,
> leaving __sched_setscheduler() completely unsynchronized against this loop.
> 
> If sched_setattr() transitions a task to SCHED_DEADLINE concurrently,
> __sched_setscheduler() calls sched_dl_overflow() which acquires dl_b->lock
> and adds the task's bandwidth. Then this iteration loop could observe the new
> priority, call dl_add_task_root_domain(), and add the bandwidth a second time,
> corrupting rd->dl_bw.total_bw.
> 
> Similarly, a task transitioning from SCHED_DEADLINE to SCHED_OTHER could result
> in a bandwidth underflow because the rebuild clears the bandwidth, skips the
> task, and later inactive_task_timer() subtracts the bandwidth.
> 
> [Severity: Medium]
> Does this leak SCHED_DEADLINE bandwidth in the active root domain for DEAD tasks
> on offline CPUs?
> 
> This loop blindly iterates over all tasks, including TASK_DEAD zombies, without
> checking the task state. If a SCHED_DEADLINE task exits and enters TASK_DEAD
> state, its bandwidth is preserved until its 0-lag inactive timer fires.

Both bugs, are real, and I am going to address them in the next itiration, after
waiting for feedback on the series.