[PATCH v2 6/8] sched/deadline, topology: Avoid O(N^2) dl_server bandwidth walks during root_domain rebuilds
From: Pasha Tatashin
Date: Sun Oct 18 2026 - 21:18:09 EST
Every CPU runqueue has a fair_server (and optionally an ext_server)
deadline entity enabled by default. Whenever a root_domain is rebuilt on
CPU hotplug or cpuset changes, partition_sched_domains_locked() currently
performs three O(N^2) remote runqueue bandwidth updates across all N
active CPUs (O(N^3) across sequential hotplug of N CPUs):
1. detach_destroy_domains() calls
cpu_attach_domain(NULL, &def_root_domain, i) -> rq_attach_root() ->
__dl_server_attach_root() for each of the N CPUs. Each call recomputes
cpumask_weight_and(rd->span, cpu_active_mask) twice and calls
__dl_add() -> __dl_update(), walking all active CPUs attached to
def_root_domain so far to update rq->dl.extra_bw, only for
def_root_domain to be detached milliseconds later.
2. build_sched_domains() calls cpu_attach_domain(sd, d.rd, i) ->
rq_attach_root() -> __dl_server_attach_root() for each of the N CPUs,
performing another N*(N+1)/2 remote rq->dl.extra_bw updates using
intermediate partial span weights (1..N) that are immediately
discarded at the end of partition_sched_domains_locked().
3. dl_rebuild_rd_accounting() -> dl_clear_root_domain() resets
rd->dl_bw.total_bw = 0 and cpu_rq(i)->dl.extra_bw = max_bw, and then
calls dl_server_add_bw(rd, i) -> __dl_add() -> __dl_update() in a
nested O(N^2) loop over rd->span with interrupts disabled.
Remove the redundant __dl_server_attach_root() calls from rq_attach_root()
(since partition_sched_domains_locked() always rebuilds root_domain
accounting via dl_rebuild_rd_accounting() once domain attachment is
complete), and replace the nested O(N^2) loop in dl_clear_root_domain()
with a single O(N) accumulation pass and a single O(N) extra_bw update
pass.
Also provide a !CONFIG_CPUSETS implementation of
dl_rebuild_rd_accounting() (using a lockless dl_prio(READ_ONCE(p->prio))
pre-check before dl_add_task_root_domain(p)). Previously,
dl_rebuild_rd_accounting() was a no-op stub when CONFIG_CPUSETS=n, which
left root_domain rebuilds without SCHED_DEADLINE task bandwidth
accounting and left inconsistent per-CPU extra_bw values computed from
partial active CPU counts in rq_attach_root().
2-socket, 480-CPU Intel Xeon 6985P-C (N=479, mean of 10 runs):
Offline: 5.15 s -> 3.88 s (-24.7%)
Online: 4.05 s -> 2.51 s (-38.0%)
Total: 9.20 s -> 6.39 s (-30.5%)
dl_clear_root_domain() / dl_rebuild_rd_accounting() (cpu479):
5,537.0 us -> 58.1 us (-99.0%) / 5,176.2 us -> 61.9 us (-98.8%)
2-socket, 512-CPU AMD EPYC 9B45 (N=511, mean of 10 runs):
Offline: 3.26 s -> 2.77 s (-15.0%)
Online: 2.03 s -> 1.53 s (-24.6%)
Total: 5.29 s -> 4.30 s (-18.7%)
dl_clear_root_domain() / dl_rebuild_rd_accounting() (cpu511):
1,880.5 us -> 27.5 us (-98.5%) / 1,762.3 us -> 22.6 us (-98.7%)
Signed-off-by: Pasha Tatashin <pasha.tatashin@xxxxxxxxxx>
---
include/linux/cpuset.h | 23 ++++++---
include/linux/sched/deadline.h | 1 -
kernel/sched/deadline.c | 93 +++++++++++++++++++++-------------
kernel/sched/sched.h | 1 -
kernel/sched/topology.c | 13 -----
5 files changed, 73 insertions(+), 58 deletions(-)
diff --git a/include/linux/cpuset.h b/include/linux/cpuset.h
index 914983387e95..b99f329551fa 100644
--- a/include/linux/cpuset.h
+++ b/include/linux/cpuset.h
@@ -129,7 +129,7 @@ static inline int cpuset_do_page_mem_spread(void)
extern bool current_cpuset_is_being_rebound(void);
-extern void dl_rebuild_rd_accounting(void);
+void dl_rebuild_rd_accounting(void);
extern void rebuild_sched_domains(void);
extern void cpuset_print_current_mems_allowed(void);
@@ -196,9 +196,20 @@ static inline void cpuset_update_active_cpus(void)
static inline void inc_dl_tasks_cs(struct task_struct *task) { }
static inline void dec_dl_tasks_cs(struct task_struct *task) { }
-static inline void cpuset_lock(void) { }
-static inline void cpuset_unlock(void) { }
-static inline void lockdep_assert_cpuset_lock_held(void) { }
+static inline void cpuset_lock(void)
+{
+ sched_domains_mutex_lock();
+}
+
+static inline void cpuset_unlock(void)
+{
+ sched_domains_mutex_unlock();
+}
+
+static inline void lockdep_assert_cpuset_lock_held(void)
+{
+ lockdep_assert_held(&sched_domains_mutex);
+}
static inline void cpuset_cpus_allowed_locked(struct task_struct *p,
struct cpumask *mask)
@@ -273,9 +284,7 @@ static inline bool current_cpuset_is_being_rebound(void)
return false;
}
-static inline void dl_rebuild_rd_accounting(void)
-{
-}
+void dl_rebuild_rd_accounting(void);
static inline void rebuild_sched_domains(void)
{
diff --git a/include/linux/sched/deadline.h b/include/linux/sched/deadline.h
index 273538200a44..6f03357f05c7 100644
--- a/include/linux/sched/deadline.h
+++ b/include/linux/sched/deadline.h
@@ -31,7 +31,6 @@ 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);
/*
* Return whether moving DL task @p to @new_mask requires moving DL
diff --git a/kernel/sched/deadline.c b/kernel/sched/deadline.c
index c0ebdcde5fe5..c8847e1ea55a 100644
--- a/kernel/sched/deadline.c
+++ b/kernel/sched/deadline.c
@@ -1885,24 +1885,6 @@ void sched_init_dl_servers(void)
}
}
-void __dl_server_attach_root(struct sched_dl_entity *dl_se, struct rq *rq)
-{
- u64 new_bw = dl_se->dl_bw;
- int cpu = cpu_of(rq);
- struct dl_bw *dl_b;
-
- if (!dl_se->dl_bw_attached)
- return;
-
- dl_b = dl_bw_of(cpu_of(rq));
- guard(raw_spinlock)(&dl_b->lock);
-
- if (!dl_bw_cpus(cpu))
- return;
-
- __dl_add(dl_b, new_bw, dl_bw_cpus(cpu));
-}
-
int dl_server_apply_params(struct sched_dl_entity *dl_se, u64 runtime, u64 period, bool init)
{
u64 old_bw = (init || !dl_se->dl_bw_attached) ? 0 :
@@ -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;
}
@@ -3451,18 +3434,22 @@ void dl_add_task_root_domain(struct task_struct *p)
raw_spin_unlock_irqrestore(&p->pi_lock, rf.flags);
}
-static void dl_server_add_bw(struct root_domain *rd, int cpu)
+static void dl_server_sum_bw(int cpu, int cpus, u64 *total_bw, s64 *extra_bw)
{
struct sched_dl_entity *dl_se;
dl_se = &cpu_rq(cpu)->fair_server;
- if (dl_server(dl_se) && dl_se->dl_bw_attached && cpu_active(cpu))
- __dl_add(&rd->dl_bw, dl_se->dl_bw, dl_bw_cpus(cpu));
+ if (dl_server(dl_se) && dl_se->dl_bw_attached) {
+ *total_bw += dl_se->dl_bw;
+ *extra_bw -= (s32)dl_se->dl_bw / cpus;
+ }
#ifdef CONFIG_SCHED_CLASS_EXT
dl_se = &cpu_rq(cpu)->ext_server;
- if (dl_server(dl_se) && dl_se->dl_bw_attached && cpu_active(cpu))
- __dl_add(&rd->dl_bw, dl_se->dl_bw, dl_bw_cpus(cpu));
+ if (dl_server(dl_se) && dl_se->dl_bw_attached) {
+ *total_bw += dl_se->dl_bw;
+ *extra_bw -= (s32)dl_se->dl_bw / cpus;
+ }
#endif
}
@@ -3483,26 +3470,33 @@ 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);
- /*
- * Reset total_bw to zero and extra_bw to max_bw so that next
- * loop will add dl-servers contributions back properly,
- */
- rd->dl_bw.total_bw = 0;
- for_each_cpu(i, rd->span)
- cpu_rq(i)->dl.extra_bw = cpu_rq(i)->dl.max_bw;
-
/*
* dl_servers are not tasks. Since dl_add_task_root_domain ignores
* them, we need to account for them here explicitly.
*/
- for_each_cpu(i, rd->span)
- dl_server_add_bw(rd, i);
+ cpus = cpumask_weight_and(rd->span, cpu_active_mask);
+ if (cpus) {
+ for_each_cpu_and(i, rd->span, cpu_active_mask)
+ dl_server_sum_bw(i, cpus, &total_bw, &extra_bw);
+ }
+
+ rd->dl_bw.total_bw = total_bw;
+ for_each_cpu(i, rd->span) {
+ struct rq *rq = cpu_rq(i);
+ u64 bw = rq->dl.max_bw;
+
+ if (cpu_active(i))
+ bw += extra_bw;
+ WRITE_ONCE(rq->dl.extra_bw, bw);
+ }
}
void dl_clear_root_domain_cpu(int cpu)
@@ -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
+
static void switched_from_dl(struct rq *rq, struct task_struct *p)
{
/*
diff --git a/kernel/sched/sched.h b/kernel/sched/sched.h
index 314fcad94668..3225cda0f9f6 100644
--- a/kernel/sched/sched.h
+++ b/kernel/sched/sched.h
@@ -418,7 +418,6 @@ extern void sched_init_dl_servers(void);
extern void fair_server_init(struct rq *rq);
extern void ext_server_init(struct rq *rq);
-extern void __dl_server_attach_root(struct sched_dl_entity *dl_se, struct rq *rq);
extern int dl_server_apply_params(struct sched_dl_entity *dl_se,
u64 runtime, u64 period, bool init);
extern int dl_server_attach_bw(struct sched_dl_entity *dl_se);
diff --git a/kernel/sched/topology.c b/kernel/sched/topology.c
index a5a5d1378ce2..b5dec7f486b5 100644
--- a/kernel/sched/topology.c
+++ b/kernel/sched/topology.c
@@ -516,19 +516,6 @@ void rq_attach_root(struct rq *rq, struct root_domain *rd)
if (cpumask_test_cpu(rq->cpu, cpu_active_mask))
set_rq_online(rq);
- /*
- * Because the rq is not a task, dl_add_task_root_domain() did not
- * move the fair server bw to the rd if it already started.
- * Add it now.
- */
- if (rq->fair_server.dl_server)
- __dl_server_attach_root(&rq->fair_server, rq);
-
-#ifdef CONFIG_SCHED_CLASS_EXT
- if (rq->ext_server.dl_server)
- __dl_server_attach_root(&rq->ext_server, rq);
-#endif
-
rq_unlock_irqrestore(rq, &rf);
if (old_rd)
--
2.56.0.176.g3575e65682-goog