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 --- 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