1 // SPDX-License-Identifier: GPL-2.0
3 * Scheduler topology setup/handling methods
6 #include <linux/bsearch.h>
8 DEFINE_MUTEX(sched_domains_mutex
);
10 /* Protected by sched_domains_mutex: */
11 static cpumask_var_t sched_domains_tmpmask
;
12 static cpumask_var_t sched_domains_tmpmask2
;
14 #ifdef CONFIG_SCHED_DEBUG
16 static int __init
sched_debug_setup(char *str
)
18 sched_debug_verbose
= true;
22 early_param("sched_verbose", sched_debug_setup
);
24 static inline bool sched_debug(void)
26 return sched_debug_verbose
;
29 #define SD_FLAG(_name, mflags) [__##_name] = { .meta_flags = mflags, .name = #_name },
30 const struct sd_flag_debug sd_flag_debug
[] = {
31 #include <linux/sched/sd_flags.h>
35 static int sched_domain_debug_one(struct sched_domain
*sd
, int cpu
, int level
,
36 struct cpumask
*groupmask
)
38 struct sched_group
*group
= sd
->groups
;
39 unsigned long flags
= sd
->flags
;
42 cpumask_clear(groupmask
);
44 printk(KERN_DEBUG
"%*s domain-%d: ", level
, "", level
);
45 printk(KERN_CONT
"span=%*pbl level=%s\n",
46 cpumask_pr_args(sched_domain_span(sd
)), sd
->name
);
48 if (!cpumask_test_cpu(cpu
, sched_domain_span(sd
))) {
49 printk(KERN_ERR
"ERROR: domain->span does not contain CPU%d\n", cpu
);
51 if (group
&& !cpumask_test_cpu(cpu
, sched_group_span(group
))) {
52 printk(KERN_ERR
"ERROR: domain->groups does not contain CPU%d\n", cpu
);
55 for_each_set_bit(idx
, &flags
, __SD_FLAG_CNT
) {
56 unsigned int flag
= BIT(idx
);
57 unsigned int meta_flags
= sd_flag_debug
[idx
].meta_flags
;
59 if ((meta_flags
& SDF_SHARED_CHILD
) && sd
->child
&&
60 !(sd
->child
->flags
& flag
))
61 printk(KERN_ERR
"ERROR: flag %s set here but not in child\n",
62 sd_flag_debug
[idx
].name
);
64 if ((meta_flags
& SDF_SHARED_PARENT
) && sd
->parent
&&
65 !(sd
->parent
->flags
& flag
))
66 printk(KERN_ERR
"ERROR: flag %s set here but not in parent\n",
67 sd_flag_debug
[idx
].name
);
70 printk(KERN_DEBUG
"%*s groups:", level
+ 1, "");
74 printk(KERN_ERR
"ERROR: group is NULL\n");
78 if (cpumask_empty(sched_group_span(group
))) {
79 printk(KERN_CONT
"\n");
80 printk(KERN_ERR
"ERROR: empty group\n");
84 if (!(sd
->flags
& SD_OVERLAP
) &&
85 cpumask_intersects(groupmask
, sched_group_span(group
))) {
86 printk(KERN_CONT
"\n");
87 printk(KERN_ERR
"ERROR: repeated CPUs\n");
91 cpumask_or(groupmask
, groupmask
, sched_group_span(group
));
93 printk(KERN_CONT
" %d:{ span=%*pbl",
95 cpumask_pr_args(sched_group_span(group
)));
97 if ((sd
->flags
& SD_OVERLAP
) &&
98 !cpumask_equal(group_balance_mask(group
), sched_group_span(group
))) {
99 printk(KERN_CONT
" mask=%*pbl",
100 cpumask_pr_args(group_balance_mask(group
)));
103 if (group
->sgc
->capacity
!= SCHED_CAPACITY_SCALE
)
104 printk(KERN_CONT
" cap=%lu", group
->sgc
->capacity
);
106 if (group
== sd
->groups
&& sd
->child
&&
107 !cpumask_equal(sched_domain_span(sd
->child
),
108 sched_group_span(group
))) {
109 printk(KERN_ERR
"ERROR: domain->groups does not match domain->child\n");
112 printk(KERN_CONT
" }");
116 if (group
!= sd
->groups
)
117 printk(KERN_CONT
",");
119 } while (group
!= sd
->groups
);
120 printk(KERN_CONT
"\n");
122 if (!cpumask_equal(sched_domain_span(sd
), groupmask
))
123 printk(KERN_ERR
"ERROR: groups don't span domain->span\n");
126 !cpumask_subset(groupmask
, sched_domain_span(sd
->parent
)))
127 printk(KERN_ERR
"ERROR: parent span is not a superset of domain->span\n");
131 static void sched_domain_debug(struct sched_domain
*sd
, int cpu
)
135 if (!sched_debug_verbose
)
139 printk(KERN_DEBUG
"CPU%d attaching NULL sched-domain.\n", cpu
);
143 printk(KERN_DEBUG
"CPU%d attaching sched-domain(s):\n", cpu
);
146 if (sched_domain_debug_one(sd
, cpu
, level
, sched_domains_tmpmask
))
154 #else /* !CONFIG_SCHED_DEBUG */
156 # define sched_debug_verbose 0
157 # define sched_domain_debug(sd, cpu) do { } while (0)
158 static inline bool sched_debug(void)
162 #endif /* CONFIG_SCHED_DEBUG */
164 /* Generate a mask of SD flags with the SDF_NEEDS_GROUPS metaflag */
165 #define SD_FLAG(name, mflags) (name * !!((mflags) & SDF_NEEDS_GROUPS)) |
166 static const unsigned int SD_DEGENERATE_GROUPS_MASK
=
167 #include <linux/sched/sd_flags.h>
171 static int sd_degenerate(struct sched_domain
*sd
)
173 if (cpumask_weight(sched_domain_span(sd
)) == 1)
176 /* Following flags need at least 2 groups */
177 if ((sd
->flags
& SD_DEGENERATE_GROUPS_MASK
) &&
178 (sd
->groups
!= sd
->groups
->next
))
181 /* Following flags don't use groups */
182 if (sd
->flags
& (SD_WAKE_AFFINE
))
189 sd_parent_degenerate(struct sched_domain
*sd
, struct sched_domain
*parent
)
191 unsigned long cflags
= sd
->flags
, pflags
= parent
->flags
;
193 if (sd_degenerate(parent
))
196 if (!cpumask_equal(sched_domain_span(sd
), sched_domain_span(parent
)))
199 /* Flags needing groups don't count if only 1 group in parent */
200 if (parent
->groups
== parent
->groups
->next
)
201 pflags
&= ~SD_DEGENERATE_GROUPS_MASK
;
203 if (~cflags
& pflags
)
209 #if defined(CONFIG_ENERGY_MODEL) && defined(CONFIG_CPU_FREQ_GOV_SCHEDUTIL)
210 DEFINE_STATIC_KEY_FALSE(sched_energy_present
);
211 static unsigned int sysctl_sched_energy_aware
= 1;
212 static DEFINE_MUTEX(sched_energy_mutex
);
213 static bool sched_energy_update
;
215 static bool sched_is_eas_possible(const struct cpumask
*cpu_mask
)
217 bool any_asym_capacity
= false;
218 struct cpufreq_policy
*policy
;
219 struct cpufreq_governor
*gov
;
222 /* EAS is enabled for asymmetric CPU capacity topologies. */
223 for_each_cpu(i
, cpu_mask
) {
224 if (rcu_access_pointer(per_cpu(sd_asym_cpucapacity
, i
))) {
225 any_asym_capacity
= true;
229 if (!any_asym_capacity
) {
231 pr_info("rd %*pbl: Checking EAS, CPUs do not have asymmetric capacities\n",
232 cpumask_pr_args(cpu_mask
));
237 /* EAS definitely does *not* handle SMT */
238 if (sched_smt_active()) {
240 pr_info("rd %*pbl: Checking EAS, SMT is not supported\n",
241 cpumask_pr_args(cpu_mask
));
246 if (!arch_scale_freq_invariant()) {
248 pr_info("rd %*pbl: Checking EAS: frequency-invariant load tracking not yet supported",
249 cpumask_pr_args(cpu_mask
));
254 /* Do not attempt EAS if schedutil is not being used. */
255 for_each_cpu(i
, cpu_mask
) {
256 policy
= cpufreq_cpu_get(i
);
259 pr_info("rd %*pbl: Checking EAS, cpufreq policy not set for CPU: %d",
260 cpumask_pr_args(cpu_mask
), i
);
264 gov
= policy
->governor
;
265 cpufreq_cpu_put(policy
);
266 if (gov
!= &schedutil_gov
) {
268 pr_info("rd %*pbl: Checking EAS, schedutil is mandatory\n",
269 cpumask_pr_args(cpu_mask
));
278 void rebuild_sched_domains_energy(void)
280 mutex_lock(&sched_energy_mutex
);
281 sched_energy_update
= true;
282 rebuild_sched_domains();
283 sched_energy_update
= false;
284 mutex_unlock(&sched_energy_mutex
);
287 #ifdef CONFIG_PROC_SYSCTL
288 static int sched_energy_aware_handler(const struct ctl_table
*table
, int write
,
289 void *buffer
, size_t *lenp
, loff_t
*ppos
)
293 if (write
&& !capable(CAP_SYS_ADMIN
))
296 if (!sched_is_eas_possible(cpu_active_mask
)) {
305 ret
= proc_dointvec_minmax(table
, write
, buffer
, lenp
, ppos
);
307 state
= static_branch_unlikely(&sched_energy_present
);
308 if (state
!= sysctl_sched_energy_aware
)
309 rebuild_sched_domains_energy();
315 static struct ctl_table sched_energy_aware_sysctls
[] = {
317 .procname
= "sched_energy_aware",
318 .data
= &sysctl_sched_energy_aware
,
319 .maxlen
= sizeof(unsigned int),
321 .proc_handler
= sched_energy_aware_handler
,
322 .extra1
= SYSCTL_ZERO
,
323 .extra2
= SYSCTL_ONE
,
327 static int __init
sched_energy_aware_sysctl_init(void)
329 register_sysctl_init("kernel", sched_energy_aware_sysctls
);
333 late_initcall(sched_energy_aware_sysctl_init
);
336 static void free_pd(struct perf_domain
*pd
)
338 struct perf_domain
*tmp
;
347 static struct perf_domain
*find_pd(struct perf_domain
*pd
, int cpu
)
350 if (cpumask_test_cpu(cpu
, perf_domain_span(pd
)))
358 static struct perf_domain
*pd_init(int cpu
)
360 struct em_perf_domain
*obj
= em_cpu_get(cpu
);
361 struct perf_domain
*pd
;
365 pr_info("%s: no EM found for CPU%d\n", __func__
, cpu
);
369 pd
= kzalloc(sizeof(*pd
), GFP_KERNEL
);
377 static void perf_domain_debug(const struct cpumask
*cpu_map
,
378 struct perf_domain
*pd
)
380 if (!sched_debug() || !pd
)
383 printk(KERN_DEBUG
"root_domain %*pbl:", cpumask_pr_args(cpu_map
));
386 printk(KERN_CONT
" pd%d:{ cpus=%*pbl nr_pstate=%d }",
387 cpumask_first(perf_domain_span(pd
)),
388 cpumask_pr_args(perf_domain_span(pd
)),
389 em_pd_nr_perf_states(pd
->em_pd
));
393 printk(KERN_CONT
"\n");
396 static void destroy_perf_domain_rcu(struct rcu_head
*rp
)
398 struct perf_domain
*pd
;
400 pd
= container_of(rp
, struct perf_domain
, rcu
);
404 static void sched_energy_set(bool has_eas
)
406 if (!has_eas
&& static_branch_unlikely(&sched_energy_present
)) {
408 pr_info("%s: stopping EAS\n", __func__
);
409 static_branch_disable_cpuslocked(&sched_energy_present
);
410 } else if (has_eas
&& !static_branch_unlikely(&sched_energy_present
)) {
412 pr_info("%s: starting EAS\n", __func__
);
413 static_branch_enable_cpuslocked(&sched_energy_present
);
418 * EAS can be used on a root domain if it meets all the following conditions:
419 * 1. an Energy Model (EM) is available;
420 * 2. the SD_ASYM_CPUCAPACITY flag is set in the sched_domain hierarchy.
421 * 3. no SMT is detected.
422 * 4. schedutil is driving the frequency of all CPUs of the rd;
423 * 5. frequency invariance support is present;
425 static bool build_perf_domains(const struct cpumask
*cpu_map
)
428 struct perf_domain
*pd
= NULL
, *tmp
;
429 int cpu
= cpumask_first(cpu_map
);
430 struct root_domain
*rd
= cpu_rq(cpu
)->rd
;
432 if (!sysctl_sched_energy_aware
)
435 if (!sched_is_eas_possible(cpu_map
))
438 for_each_cpu(i
, cpu_map
) {
439 /* Skip already covered CPUs. */
443 /* Create the new pd and add it to the local list. */
451 perf_domain_debug(cpu_map
, pd
);
453 /* Attach the new list of performance domains to the root domain. */
455 rcu_assign_pointer(rd
->pd
, pd
);
457 call_rcu(&tmp
->rcu
, destroy_perf_domain_rcu
);
464 rcu_assign_pointer(rd
->pd
, NULL
);
466 call_rcu(&tmp
->rcu
, destroy_perf_domain_rcu
);
471 static void free_pd(struct perf_domain
*pd
) { }
472 #endif /* CONFIG_ENERGY_MODEL && CONFIG_CPU_FREQ_GOV_SCHEDUTIL*/
474 static void free_rootdomain(struct rcu_head
*rcu
)
476 struct root_domain
*rd
= container_of(rcu
, struct root_domain
, rcu
);
478 cpupri_cleanup(&rd
->cpupri
);
479 cpudl_cleanup(&rd
->cpudl
);
480 free_cpumask_var(rd
->dlo_mask
);
481 free_cpumask_var(rd
->rto_mask
);
482 free_cpumask_var(rd
->online
);
483 free_cpumask_var(rd
->span
);
488 void rq_attach_root(struct rq
*rq
, struct root_domain
*rd
)
490 struct root_domain
*old_rd
= NULL
;
493 rq_lock_irqsave(rq
, &rf
);
498 if (cpumask_test_cpu(rq
->cpu
, old_rd
->online
))
501 cpumask_clear_cpu(rq
->cpu
, old_rd
->span
);
504 * If we don't want to free the old_rd yet then
505 * set old_rd to NULL to skip the freeing later
508 if (!atomic_dec_and_test(&old_rd
->refcount
))
512 atomic_inc(&rd
->refcount
);
515 cpumask_set_cpu(rq
->cpu
, rd
->span
);
516 if (cpumask_test_cpu(rq
->cpu
, cpu_active_mask
))
520 * Because the rq is not a task, dl_add_task_root_domain() did not
521 * move the fair server bw to the rd if it already started.
524 if (rq
->fair_server
.dl_server
)
525 __dl_server_attach_root(&rq
->fair_server
, rq
);
527 rq_unlock_irqrestore(rq
, &rf
);
530 call_rcu(&old_rd
->rcu
, free_rootdomain
);
533 void sched_get_rd(struct root_domain
*rd
)
535 atomic_inc(&rd
->refcount
);
538 void sched_put_rd(struct root_domain
*rd
)
540 if (!atomic_dec_and_test(&rd
->refcount
))
543 call_rcu(&rd
->rcu
, free_rootdomain
);
546 static int init_rootdomain(struct root_domain
*rd
)
548 if (!zalloc_cpumask_var(&rd
->span
, GFP_KERNEL
))
550 if (!zalloc_cpumask_var(&rd
->online
, GFP_KERNEL
))
552 if (!zalloc_cpumask_var(&rd
->dlo_mask
, GFP_KERNEL
))
554 if (!zalloc_cpumask_var(&rd
->rto_mask
, GFP_KERNEL
))
557 #ifdef HAVE_RT_PUSH_IPI
559 raw_spin_lock_init(&rd
->rto_lock
);
560 rd
->rto_push_work
= IRQ_WORK_INIT_HARD(rto_push_irq_work_func
);
564 init_dl_bw(&rd
->dl_bw
);
565 if (cpudl_init(&rd
->cpudl
) != 0)
568 if (cpupri_init(&rd
->cpupri
) != 0)
573 cpudl_cleanup(&rd
->cpudl
);
575 free_cpumask_var(rd
->rto_mask
);
577 free_cpumask_var(rd
->dlo_mask
);
579 free_cpumask_var(rd
->online
);
581 free_cpumask_var(rd
->span
);
587 * By default the system creates a single root-domain with all CPUs as
588 * members (mimicking the global state we have today).
590 struct root_domain def_root_domain
;
592 void __init
init_defrootdomain(void)
594 init_rootdomain(&def_root_domain
);
596 atomic_set(&def_root_domain
.refcount
, 1);
599 static struct root_domain
*alloc_rootdomain(void)
601 struct root_domain
*rd
;
603 rd
= kzalloc(sizeof(*rd
), GFP_KERNEL
);
607 if (init_rootdomain(rd
) != 0) {
615 static void free_sched_groups(struct sched_group
*sg
, int free_sgc
)
617 struct sched_group
*tmp
, *first
;
626 if (free_sgc
&& atomic_dec_and_test(&sg
->sgc
->ref
))
629 if (atomic_dec_and_test(&sg
->ref
))
632 } while (sg
!= first
);
635 static void destroy_sched_domain(struct sched_domain
*sd
)
638 * A normal sched domain may have multiple group references, an
639 * overlapping domain, having private groups, only one. Iterate,
640 * dropping group/capacity references, freeing where none remain.
642 free_sched_groups(sd
->groups
, 1);
644 if (sd
->shared
&& atomic_dec_and_test(&sd
->shared
->ref
))
649 static void destroy_sched_domains_rcu(struct rcu_head
*rcu
)
651 struct sched_domain
*sd
= container_of(rcu
, struct sched_domain
, rcu
);
654 struct sched_domain
*parent
= sd
->parent
;
655 destroy_sched_domain(sd
);
660 static void destroy_sched_domains(struct sched_domain
*sd
)
663 call_rcu(&sd
->rcu
, destroy_sched_domains_rcu
);
667 * Keep a special pointer to the highest sched_domain that has SD_SHARE_LLC set
668 * (Last Level Cache Domain) for this allows us to avoid some pointer chasing
669 * select_idle_sibling().
671 * Also keep a unique ID per domain (we use the first CPU number in the cpumask
672 * of the domain), this allows us to quickly tell if two CPUs are in the same
673 * cache domain, see cpus_share_cache().
675 DEFINE_PER_CPU(struct sched_domain __rcu
*, sd_llc
);
676 DEFINE_PER_CPU(int, sd_llc_size
);
677 DEFINE_PER_CPU(int, sd_llc_id
);
678 DEFINE_PER_CPU(int, sd_share_id
);
679 DEFINE_PER_CPU(struct sched_domain_shared __rcu
*, sd_llc_shared
);
680 DEFINE_PER_CPU(struct sched_domain __rcu
*, sd_numa
);
681 DEFINE_PER_CPU(struct sched_domain __rcu
*, sd_asym_packing
);
682 DEFINE_PER_CPU(struct sched_domain __rcu
*, sd_asym_cpucapacity
);
684 DEFINE_STATIC_KEY_FALSE(sched_asym_cpucapacity
);
685 DEFINE_STATIC_KEY_FALSE(sched_cluster_active
);
687 static void update_top_cache_domain(int cpu
)
689 struct sched_domain_shared
*sds
= NULL
;
690 struct sched_domain
*sd
;
694 sd
= highest_flag_domain(cpu
, SD_SHARE_LLC
);
696 id
= cpumask_first(sched_domain_span(sd
));
697 size
= cpumask_weight(sched_domain_span(sd
));
701 rcu_assign_pointer(per_cpu(sd_llc
, cpu
), sd
);
702 per_cpu(sd_llc_size
, cpu
) = size
;
703 per_cpu(sd_llc_id
, cpu
) = id
;
704 rcu_assign_pointer(per_cpu(sd_llc_shared
, cpu
), sds
);
706 sd
= lowest_flag_domain(cpu
, SD_CLUSTER
);
708 id
= cpumask_first(sched_domain_span(sd
));
711 * This assignment should be placed after the sd_llc_id as
712 * we want this id equals to cluster id on cluster machines
713 * but equals to LLC id on non-Cluster machines.
715 per_cpu(sd_share_id
, cpu
) = id
;
717 sd
= lowest_flag_domain(cpu
, SD_NUMA
);
718 rcu_assign_pointer(per_cpu(sd_numa
, cpu
), sd
);
720 sd
= highest_flag_domain(cpu
, SD_ASYM_PACKING
);
721 rcu_assign_pointer(per_cpu(sd_asym_packing
, cpu
), sd
);
723 sd
= lowest_flag_domain(cpu
, SD_ASYM_CPUCAPACITY_FULL
);
724 rcu_assign_pointer(per_cpu(sd_asym_cpucapacity
, cpu
), sd
);
728 * Attach the domain 'sd' to 'cpu' as its base domain. Callers must
729 * hold the hotplug lock.
732 cpu_attach_domain(struct sched_domain
*sd
, struct root_domain
*rd
, int cpu
)
734 struct rq
*rq
= cpu_rq(cpu
);
735 struct sched_domain
*tmp
;
737 /* Remove the sched domains which do not contribute to scheduling. */
738 for (tmp
= sd
; tmp
; ) {
739 struct sched_domain
*parent
= tmp
->parent
;
743 if (sd_parent_degenerate(tmp
, parent
)) {
744 tmp
->parent
= parent
->parent
;
746 if (parent
->parent
) {
747 parent
->parent
->child
= tmp
;
748 parent
->parent
->groups
->flags
= tmp
->flags
;
752 * Transfer SD_PREFER_SIBLING down in case of a
753 * degenerate parent; the spans match for this
754 * so the property transfers.
756 if (parent
->flags
& SD_PREFER_SIBLING
)
757 tmp
->flags
|= SD_PREFER_SIBLING
;
758 destroy_sched_domain(parent
);
763 if (sd
&& sd_degenerate(sd
)) {
766 destroy_sched_domain(tmp
);
768 struct sched_group
*sg
= sd
->groups
;
771 * sched groups hold the flags of the child sched
772 * domain for convenience. Clear such flags since
773 * the child is being destroyed.
777 } while (sg
!= sd
->groups
);
783 sched_domain_debug(sd
, cpu
);
785 rq_attach_root(rq
, rd
);
787 rcu_assign_pointer(rq
->sd
, sd
);
788 dirty_sched_domain_sysctl(cpu
);
789 destroy_sched_domains(tmp
);
791 update_top_cache_domain(cpu
);
795 struct sched_domain
* __percpu
*sd
;
796 struct root_domain
*rd
;
807 * Return the canonical balance CPU for this group, this is the first CPU
808 * of this group that's also in the balance mask.
810 * The balance mask are all those CPUs that could actually end up at this
811 * group. See build_balance_mask().
813 * Also see should_we_balance().
815 int group_balance_cpu(struct sched_group
*sg
)
817 return cpumask_first(group_balance_mask(sg
));
822 * NUMA topology (first read the regular topology blurb below)
824 * Given a node-distance table, for example:
832 * which represents a 4 node ring topology like:
840 * We want to construct domains and groups to represent this. The way we go
841 * about doing this is to build the domains on 'hops'. For each NUMA level we
842 * construct the mask of all nodes reachable in @level hops.
844 * For the above NUMA topology that gives 3 levels:
846 * NUMA-2 0-3 0-3 0-3 0-3
847 * groups: {0-1,3},{1-3} {0-2},{0,2-3} {1-3},{0-1,3} {0,2-3},{0-2}
849 * NUMA-1 0-1,3 0-2 1-3 0,2-3
850 * groups: {0},{1},{3} {0},{1},{2} {1},{2},{3} {0},{2},{3}
855 * As can be seen; things don't nicely line up as with the regular topology.
856 * When we iterate a domain in child domain chunks some nodes can be
857 * represented multiple times -- hence the "overlap" naming for this part of
860 * In order to minimize this overlap, we only build enough groups to cover the
861 * domain. For instance Node-0 NUMA-2 would only get groups: 0-1,3 and 1-3.
865 * - the first group of each domain is its child domain; this
866 * gets us the first 0-1,3
867 * - the only uncovered node is 2, who's child domain is 1-3.
869 * However, because of the overlap, computing a unique CPU for each group is
870 * more complicated. Consider for instance the groups of NODE-1 NUMA-2, both
871 * groups include the CPUs of Node-0, while those CPUs would not in fact ever
872 * end up at those groups (they would end up in group: 0-1,3).
874 * To correct this we have to introduce the group balance mask. This mask
875 * will contain those CPUs in the group that can reach this group given the
876 * (child) domain tree.
878 * With this we can once again compute balance_cpu and sched_group_capacity
881 * XXX include words on how balance_cpu is unique and therefore can be
882 * used for sched_group_capacity links.
885 * Another 'interesting' topology is:
893 * Which looks a little like:
901 * This topology is asymmetric, nodes 1,2 are fully connected, but nodes 0,3
904 * This leads to a few particularly weird cases where the sched_domain's are
905 * not of the same number for each CPU. Consider:
908 * groups: {0-2},{1-3} {1-3},{0-2}
910 * NUMA-1 0-2 0-3 0-3 1-3
918 * Build the balance mask; it contains only those CPUs that can arrive at this
919 * group and should be considered to continue balancing.
921 * We do this during the group creation pass, therefore the group information
922 * isn't complete yet, however since each group represents a (child) domain we
923 * can fully construct this using the sched_domain bits (which are already
927 build_balance_mask(struct sched_domain
*sd
, struct sched_group
*sg
, struct cpumask
*mask
)
929 const struct cpumask
*sg_span
= sched_group_span(sg
);
930 struct sd_data
*sdd
= sd
->private;
931 struct sched_domain
*sibling
;
936 for_each_cpu(i
, sg_span
) {
937 sibling
= *per_cpu_ptr(sdd
->sd
, i
);
940 * Can happen in the asymmetric case, where these siblings are
941 * unused. The mask will not be empty because those CPUs that
942 * do have the top domain _should_ span the domain.
947 /* If we would not end up here, we can't continue from here */
948 if (!cpumask_equal(sg_span
, sched_domain_span(sibling
->child
)))
951 cpumask_set_cpu(i
, mask
);
954 /* We must not have empty masks here */
955 WARN_ON_ONCE(cpumask_empty(mask
));
959 * XXX: This creates per-node group entries; since the load-balancer will
960 * immediately access remote memory to construct this group's load-balance
961 * statistics having the groups node local is of dubious benefit.
963 static struct sched_group
*
964 build_group_from_child_sched_domain(struct sched_domain
*sd
, int cpu
)
966 struct sched_group
*sg
;
967 struct cpumask
*sg_span
;
969 sg
= kzalloc_node(sizeof(struct sched_group
) + cpumask_size(),
970 GFP_KERNEL
, cpu_to_node(cpu
));
975 sg_span
= sched_group_span(sg
);
977 cpumask_copy(sg_span
, sched_domain_span(sd
->child
));
978 sg
->flags
= sd
->child
->flags
;
980 cpumask_copy(sg_span
, sched_domain_span(sd
));
983 atomic_inc(&sg
->ref
);
987 static void init_overlap_sched_group(struct sched_domain
*sd
,
988 struct sched_group
*sg
)
990 struct cpumask
*mask
= sched_domains_tmpmask2
;
991 struct sd_data
*sdd
= sd
->private;
992 struct cpumask
*sg_span
;
995 build_balance_mask(sd
, sg
, mask
);
996 cpu
= cpumask_first(mask
);
998 sg
->sgc
= *per_cpu_ptr(sdd
->sgc
, cpu
);
999 if (atomic_inc_return(&sg
->sgc
->ref
) == 1)
1000 cpumask_copy(group_balance_mask(sg
), mask
);
1002 WARN_ON_ONCE(!cpumask_equal(group_balance_mask(sg
), mask
));
1005 * Initialize sgc->capacity such that even if we mess up the
1006 * domains and no possible iteration will get us here, we won't
1009 sg_span
= sched_group_span(sg
);
1010 sg
->sgc
->capacity
= SCHED_CAPACITY_SCALE
* cpumask_weight(sg_span
);
1011 sg
->sgc
->min_capacity
= SCHED_CAPACITY_SCALE
;
1012 sg
->sgc
->max_capacity
= SCHED_CAPACITY_SCALE
;
1015 static struct sched_domain
*
1016 find_descended_sibling(struct sched_domain
*sd
, struct sched_domain
*sibling
)
1019 * The proper descendant would be the one whose child won't span out
1022 while (sibling
->child
&&
1023 !cpumask_subset(sched_domain_span(sibling
->child
),
1024 sched_domain_span(sd
)))
1025 sibling
= sibling
->child
;
1028 * As we are referencing sgc across different topology level, we need
1029 * to go down to skip those sched_domains which don't contribute to
1030 * scheduling because they will be degenerated in cpu_attach_domain
1032 while (sibling
->child
&&
1033 cpumask_equal(sched_domain_span(sibling
->child
),
1034 sched_domain_span(sibling
)))
1035 sibling
= sibling
->child
;
1041 build_overlap_sched_groups(struct sched_domain
*sd
, int cpu
)
1043 struct sched_group
*first
= NULL
, *last
= NULL
, *sg
;
1044 const struct cpumask
*span
= sched_domain_span(sd
);
1045 struct cpumask
*covered
= sched_domains_tmpmask
;
1046 struct sd_data
*sdd
= sd
->private;
1047 struct sched_domain
*sibling
;
1050 cpumask_clear(covered
);
1052 for_each_cpu_wrap(i
, span
, cpu
) {
1053 struct cpumask
*sg_span
;
1055 if (cpumask_test_cpu(i
, covered
))
1058 sibling
= *per_cpu_ptr(sdd
->sd
, i
);
1061 * Asymmetric node setups can result in situations where the
1062 * domain tree is of unequal depth, make sure to skip domains
1063 * that already cover the entire range.
1065 * In that case build_sched_domains() will have terminated the
1066 * iteration early and our sibling sd spans will be empty.
1067 * Domains should always include the CPU they're built on, so
1070 if (!cpumask_test_cpu(i
, sched_domain_span(sibling
)))
1074 * Usually we build sched_group by sibling's child sched_domain
1075 * But for machines whose NUMA diameter are 3 or above, we move
1076 * to build sched_group by sibling's proper descendant's child
1077 * domain because sibling's child sched_domain will span out of
1078 * the sched_domain being built as below.
1080 * Smallest diameter=3 topology is:
1088 * 0 --- 1 --- 2 --- 3
1090 * NUMA-3 0-3 N/A N/A 0-3
1091 * groups: {0-2},{1-3} {1-3},{0-2}
1093 * NUMA-2 0-2 0-3 0-3 1-3
1094 * groups: {0-1},{1-3} {0-2},{2-3} {1-3},{0-1} {2-3},{0-2}
1096 * NUMA-1 0-1 0-2 1-3 2-3
1097 * groups: {0},{1} {1},{2},{0} {2},{3},{1} {3},{2}
1101 * The NUMA-2 groups for nodes 0 and 3 are obviously buggered, as the
1102 * group span isn't a subset of the domain span.
1104 if (sibling
->child
&&
1105 !cpumask_subset(sched_domain_span(sibling
->child
), span
))
1106 sibling
= find_descended_sibling(sd
, sibling
);
1108 sg
= build_group_from_child_sched_domain(sibling
, cpu
);
1112 sg_span
= sched_group_span(sg
);
1113 cpumask_or(covered
, covered
, sg_span
);
1115 init_overlap_sched_group(sibling
, sg
);
1129 free_sched_groups(first
, 0);
1136 * Package topology (also see the load-balance blurb in fair.c)
1138 * The scheduler builds a tree structure to represent a number of important
1139 * topology features. By default (default_topology[]) these include:
1141 * - Simultaneous multithreading (SMT)
1142 * - Multi-Core Cache (MC)
1145 * Where the last one more or less denotes everything up to a NUMA node.
1147 * The tree consists of 3 primary data structures:
1149 * sched_domain -> sched_group -> sched_group_capacity
1153 * The sched_domains are per-CPU and have a two way link (parent & child) and
1154 * denote the ever growing mask of CPUs belonging to that level of topology.
1156 * Each sched_domain has a circular (double) linked list of sched_group's, each
1157 * denoting the domains of the level below (or individual CPUs in case of the
1158 * first domain level). The sched_group linked by a sched_domain includes the
1159 * CPU of that sched_domain [*].
1161 * Take for instance a 2 threaded, 2 core, 2 cache cluster part:
1163 * CPU 0 1 2 3 4 5 6 7
1167 * SMT [ ] [ ] [ ] [ ]
1171 * PKG 0-7 0-7 0-7 0-7 0-7 0-7 0-7 0-7
1172 * MC 0-3 0-3 0-3 0-3 4-7 4-7 4-7 4-7
1173 * SMT 0-1 0-1 2-3 2-3 4-5 4-5 6-7 6-7
1175 * CPU 0 1 2 3 4 5 6 7
1177 * One way to think about it is: sched_domain moves you up and down among these
1178 * topology levels, while sched_group moves you sideways through it, at child
1179 * domain granularity.
1181 * sched_group_capacity ensures each unique sched_group has shared storage.
1183 * There are two related construction problems, both require a CPU that
1184 * uniquely identify each group (for a given domain):
1186 * - The first is the balance_cpu (see should_we_balance() and the
1187 * load-balance blurb in fair.c); for each group we only want 1 CPU to
1188 * continue balancing at a higher domain.
1190 * - The second is the sched_group_capacity; we want all identical groups
1191 * to share a single sched_group_capacity.
1193 * Since these topologies are exclusive by construction. That is, its
1194 * impossible for an SMT thread to belong to multiple cores, and cores to
1195 * be part of multiple caches. There is a very clear and unique location
1196 * for each CPU in the hierarchy.
1198 * Therefore computing a unique CPU for each group is trivial (the iteration
1199 * mask is redundant and set all 1s; all CPUs in a group will end up at _that_
1200 * group), we can simply pick the first CPU in each group.
1203 * [*] in other words, the first group of each domain is its child domain.
1206 static struct sched_group
*get_group(int cpu
, struct sd_data
*sdd
)
1208 struct sched_domain
*sd
= *per_cpu_ptr(sdd
->sd
, cpu
);
1209 struct sched_domain
*child
= sd
->child
;
1210 struct sched_group
*sg
;
1211 bool already_visited
;
1214 cpu
= cpumask_first(sched_domain_span(child
));
1216 sg
= *per_cpu_ptr(sdd
->sg
, cpu
);
1217 sg
->sgc
= *per_cpu_ptr(sdd
->sgc
, cpu
);
1219 /* Increase refcounts for claim_allocations: */
1220 already_visited
= atomic_inc_return(&sg
->ref
) > 1;
1221 /* sgc visits should follow a similar trend as sg */
1222 WARN_ON(already_visited
!= (atomic_inc_return(&sg
->sgc
->ref
) > 1));
1224 /* If we have already visited that group, it's already initialized. */
1225 if (already_visited
)
1229 cpumask_copy(sched_group_span(sg
), sched_domain_span(child
));
1230 cpumask_copy(group_balance_mask(sg
), sched_group_span(sg
));
1231 sg
->flags
= child
->flags
;
1233 cpumask_set_cpu(cpu
, sched_group_span(sg
));
1234 cpumask_set_cpu(cpu
, group_balance_mask(sg
));
1237 sg
->sgc
->capacity
= SCHED_CAPACITY_SCALE
* cpumask_weight(sched_group_span(sg
));
1238 sg
->sgc
->min_capacity
= SCHED_CAPACITY_SCALE
;
1239 sg
->sgc
->max_capacity
= SCHED_CAPACITY_SCALE
;
1245 * build_sched_groups will build a circular linked list of the groups
1246 * covered by the given span, will set each group's ->cpumask correctly,
1247 * and will initialize their ->sgc.
1249 * Assumes the sched_domain tree is fully constructed
1252 build_sched_groups(struct sched_domain
*sd
, int cpu
)
1254 struct sched_group
*first
= NULL
, *last
= NULL
;
1255 struct sd_data
*sdd
= sd
->private;
1256 const struct cpumask
*span
= sched_domain_span(sd
);
1257 struct cpumask
*covered
;
1260 lockdep_assert_held(&sched_domains_mutex
);
1261 covered
= sched_domains_tmpmask
;
1263 cpumask_clear(covered
);
1265 for_each_cpu_wrap(i
, span
, cpu
) {
1266 struct sched_group
*sg
;
1268 if (cpumask_test_cpu(i
, covered
))
1271 sg
= get_group(i
, sdd
);
1273 cpumask_or(covered
, covered
, sched_group_span(sg
));
1288 * Initialize sched groups cpu_capacity.
1290 * cpu_capacity indicates the capacity of sched group, which is used while
1291 * distributing the load between different sched groups in a sched domain.
1292 * Typically cpu_capacity for all the groups in a sched domain will be same
1293 * unless there are asymmetries in the topology. If there are asymmetries,
1294 * group having more cpu_capacity will pickup more load compared to the
1295 * group having less cpu_capacity.
1297 static void init_sched_groups_capacity(int cpu
, struct sched_domain
*sd
)
1299 struct sched_group
*sg
= sd
->groups
;
1300 struct cpumask
*mask
= sched_domains_tmpmask2
;
1305 int cpu
, cores
= 0, max_cpu
= -1;
1307 sg
->group_weight
= cpumask_weight(sched_group_span(sg
));
1309 cpumask_copy(mask
, sched_group_span(sg
));
1310 for_each_cpu(cpu
, mask
) {
1312 #ifdef CONFIG_SCHED_SMT
1313 cpumask_andnot(mask
, mask
, cpu_smt_mask(cpu
));
1318 if (!(sd
->flags
& SD_ASYM_PACKING
))
1321 for_each_cpu(cpu
, sched_group_span(sg
)) {
1324 else if (sched_asym_prefer(cpu
, max_cpu
))
1327 sg
->asym_prefer_cpu
= max_cpu
;
1331 } while (sg
!= sd
->groups
);
1333 if (cpu
!= group_balance_cpu(sg
))
1336 update_group_capacity(sd
, cpu
);
1340 * Set of available CPUs grouped by their corresponding capacities
1341 * Each list entry contains a CPU mask reflecting CPUs that share the same
1343 * The lifespan of data is unlimited.
1345 LIST_HEAD(asym_cap_list
);
1348 * Verify whether there is any CPU capacity asymmetry in a given sched domain.
1349 * Provides sd_flags reflecting the asymmetry scope.
1352 asym_cpu_capacity_classify(const struct cpumask
*sd_span
,
1353 const struct cpumask
*cpu_map
)
1355 struct asym_cap_data
*entry
;
1356 int count
= 0, miss
= 0;
1359 * Count how many unique CPU capacities this domain spans across
1360 * (compare sched_domain CPUs mask with ones representing available
1361 * CPUs capacities). Take into account CPUs that might be offline:
1364 list_for_each_entry(entry
, &asym_cap_list
, link
) {
1365 if (cpumask_intersects(sd_span
, cpu_capacity_span(entry
)))
1367 else if (cpumask_intersects(cpu_map
, cpu_capacity_span(entry
)))
1371 WARN_ON_ONCE(!count
&& !list_empty(&asym_cap_list
));
1373 /* No asymmetry detected */
1376 /* Some of the available CPU capacity values have not been detected */
1378 return SD_ASYM_CPUCAPACITY
;
1380 /* Full asymmetry */
1381 return SD_ASYM_CPUCAPACITY
| SD_ASYM_CPUCAPACITY_FULL
;
1385 static void free_asym_cap_entry(struct rcu_head
*head
)
1387 struct asym_cap_data
*entry
= container_of(head
, struct asym_cap_data
, rcu
);
1391 static inline void asym_cpu_capacity_update_data(int cpu
)
1393 unsigned long capacity
= arch_scale_cpu_capacity(cpu
);
1394 struct asym_cap_data
*insert_entry
= NULL
;
1395 struct asym_cap_data
*entry
;
1398 * Search if capacity already exits. If not, track which the entry
1399 * where we should insert to keep the list ordered descending.
1401 list_for_each_entry(entry
, &asym_cap_list
, link
) {
1402 if (capacity
== entry
->capacity
)
1404 else if (!insert_entry
&& capacity
> entry
->capacity
)
1405 insert_entry
= list_prev_entry(entry
, link
);
1408 entry
= kzalloc(sizeof(*entry
) + cpumask_size(), GFP_KERNEL
);
1409 if (WARN_ONCE(!entry
, "Failed to allocate memory for asymmetry data\n"))
1411 entry
->capacity
= capacity
;
1413 /* If NULL then the new capacity is the smallest, add last. */
1415 list_add_tail_rcu(&entry
->link
, &asym_cap_list
);
1417 list_add_rcu(&entry
->link
, &insert_entry
->link
);
1419 __cpumask_set_cpu(cpu
, cpu_capacity_span(entry
));
1423 * Build-up/update list of CPUs grouped by their capacities
1424 * An update requires explicit request to rebuild sched domains
1425 * with state indicating CPU topology changes.
1427 static void asym_cpu_capacity_scan(void)
1429 struct asym_cap_data
*entry
, *next
;
1432 list_for_each_entry(entry
, &asym_cap_list
, link
)
1433 cpumask_clear(cpu_capacity_span(entry
));
1435 for_each_cpu_and(cpu
, cpu_possible_mask
, housekeeping_cpumask(HK_TYPE_DOMAIN
))
1436 asym_cpu_capacity_update_data(cpu
);
1438 list_for_each_entry_safe(entry
, next
, &asym_cap_list
, link
) {
1439 if (cpumask_empty(cpu_capacity_span(entry
))) {
1440 list_del_rcu(&entry
->link
);
1441 call_rcu(&entry
->rcu
, free_asym_cap_entry
);
1446 * Only one capacity value has been detected i.e. this system is symmetric.
1447 * No need to keep this data around.
1449 if (list_is_singular(&asym_cap_list
)) {
1450 entry
= list_first_entry(&asym_cap_list
, typeof(*entry
), link
);
1451 list_del_rcu(&entry
->link
);
1452 call_rcu(&entry
->rcu
, free_asym_cap_entry
);
1457 * Initializers for schedule domains
1458 * Non-inlined to reduce accumulated stack pressure in build_sched_domains()
1461 static int default_relax_domain_level
= -1;
1462 int sched_domain_level_max
;
1464 static int __init
setup_relax_domain_level(char *str
)
1466 if (kstrtoint(str
, 0, &default_relax_domain_level
))
1467 pr_warn("Unable to set relax_domain_level\n");
1471 __setup("relax_domain_level=", setup_relax_domain_level
);
1473 static void set_domain_attribute(struct sched_domain
*sd
,
1474 struct sched_domain_attr
*attr
)
1478 if (!attr
|| attr
->relax_domain_level
< 0) {
1479 if (default_relax_domain_level
< 0)
1481 request
= default_relax_domain_level
;
1483 request
= attr
->relax_domain_level
;
1485 if (sd
->level
>= request
) {
1486 /* Turn off idle balance on this domain: */
1487 sd
->flags
&= ~(SD_BALANCE_WAKE
|SD_BALANCE_NEWIDLE
);
1491 static void __sdt_free(const struct cpumask
*cpu_map
);
1492 static int __sdt_alloc(const struct cpumask
*cpu_map
);
1494 static void __free_domain_allocs(struct s_data
*d
, enum s_alloc what
,
1495 const struct cpumask
*cpu_map
)
1499 if (!atomic_read(&d
->rd
->refcount
))
1500 free_rootdomain(&d
->rd
->rcu
);
1506 __sdt_free(cpu_map
);
1514 __visit_domain_allocation_hell(struct s_data
*d
, const struct cpumask
*cpu_map
)
1516 memset(d
, 0, sizeof(*d
));
1518 if (__sdt_alloc(cpu_map
))
1519 return sa_sd_storage
;
1520 d
->sd
= alloc_percpu(struct sched_domain
*);
1522 return sa_sd_storage
;
1523 d
->rd
= alloc_rootdomain();
1527 return sa_rootdomain
;
1531 * NULL the sd_data elements we've used to build the sched_domain and
1532 * sched_group structure so that the subsequent __free_domain_allocs()
1533 * will not free the data we're using.
1535 static void claim_allocations(int cpu
, struct sched_domain
*sd
)
1537 struct sd_data
*sdd
= sd
->private;
1539 WARN_ON_ONCE(*per_cpu_ptr(sdd
->sd
, cpu
) != sd
);
1540 *per_cpu_ptr(sdd
->sd
, cpu
) = NULL
;
1542 if (atomic_read(&(*per_cpu_ptr(sdd
->sds
, cpu
))->ref
))
1543 *per_cpu_ptr(sdd
->sds
, cpu
) = NULL
;
1545 if (atomic_read(&(*per_cpu_ptr(sdd
->sg
, cpu
))->ref
))
1546 *per_cpu_ptr(sdd
->sg
, cpu
) = NULL
;
1548 if (atomic_read(&(*per_cpu_ptr(sdd
->sgc
, cpu
))->ref
))
1549 *per_cpu_ptr(sdd
->sgc
, cpu
) = NULL
;
1553 enum numa_topology_type sched_numa_topology_type
;
1555 static int sched_domains_numa_levels
;
1556 static int sched_domains_curr_level
;
1558 int sched_max_numa_distance
;
1559 static int *sched_domains_numa_distance
;
1560 static struct cpumask
***sched_domains_numa_masks
;
1564 * SD_flags allowed in topology descriptions.
1566 * These flags are purely descriptive of the topology and do not prescribe
1567 * behaviour. Behaviour is artificial and mapped in the below sd_init()
1568 * function. For details, see include/linux/sched/sd_flags.h.
1570 * SD_SHARE_CPUCAPACITY
1575 * Odd one out, which beside describing the topology has a quirk also
1576 * prescribes the desired behaviour that goes along with it:
1578 * SD_ASYM_PACKING - describes SMT quirks
1580 #define TOPOLOGY_SD_FLAGS \
1581 (SD_SHARE_CPUCAPACITY | \
1587 static struct sched_domain
*
1588 sd_init(struct sched_domain_topology_level
*tl
,
1589 const struct cpumask
*cpu_map
,
1590 struct sched_domain
*child
, int cpu
)
1592 struct sd_data
*sdd
= &tl
->data
;
1593 struct sched_domain
*sd
= *per_cpu_ptr(sdd
->sd
, cpu
);
1594 int sd_id
, sd_weight
, sd_flags
= 0;
1595 struct cpumask
*sd_span
;
1599 * Ugly hack to pass state to sd_numa_mask()...
1601 sched_domains_curr_level
= tl
->numa_level
;
1604 sd_weight
= cpumask_weight(tl
->mask(cpu
));
1607 sd_flags
= (*tl
->sd_flags
)();
1608 if (WARN_ONCE(sd_flags
& ~TOPOLOGY_SD_FLAGS
,
1609 "wrong sd_flags in topology description\n"))
1610 sd_flags
&= TOPOLOGY_SD_FLAGS
;
1612 *sd
= (struct sched_domain
){
1613 .min_interval
= sd_weight
,
1614 .max_interval
= 2*sd_weight
,
1616 .imbalance_pct
= 117,
1618 .cache_nice_tries
= 0,
1620 .flags
= 1*SD_BALANCE_NEWIDLE
1625 | 0*SD_SHARE_CPUCAPACITY
1628 | 1*SD_PREFER_SIBLING
1633 .last_balance
= jiffies
,
1634 .balance_interval
= sd_weight
,
1635 .max_newidle_lb_cost
= 0,
1636 .last_decay_max_lb_cost
= jiffies
,
1638 #ifdef CONFIG_SCHED_DEBUG
1643 sd_span
= sched_domain_span(sd
);
1644 cpumask_and(sd_span
, cpu_map
, tl
->mask(cpu
));
1645 sd_id
= cpumask_first(sd_span
);
1647 sd
->flags
|= asym_cpu_capacity_classify(sd_span
, cpu_map
);
1649 WARN_ONCE((sd
->flags
& (SD_SHARE_CPUCAPACITY
| SD_ASYM_CPUCAPACITY
)) ==
1650 (SD_SHARE_CPUCAPACITY
| SD_ASYM_CPUCAPACITY
),
1651 "CPU capacity asymmetry not supported on SMT\n");
1654 * Convert topological properties into behaviour.
1656 /* Don't attempt to spread across CPUs of different capacities. */
1657 if ((sd
->flags
& SD_ASYM_CPUCAPACITY
) && sd
->child
)
1658 sd
->child
->flags
&= ~SD_PREFER_SIBLING
;
1660 if (sd
->flags
& SD_SHARE_CPUCAPACITY
) {
1661 sd
->imbalance_pct
= 110;
1663 } else if (sd
->flags
& SD_SHARE_LLC
) {
1664 sd
->imbalance_pct
= 117;
1665 sd
->cache_nice_tries
= 1;
1668 } else if (sd
->flags
& SD_NUMA
) {
1669 sd
->cache_nice_tries
= 2;
1671 sd
->flags
&= ~SD_PREFER_SIBLING
;
1672 sd
->flags
|= SD_SERIALIZE
;
1673 if (sched_domains_numa_distance
[tl
->numa_level
] > node_reclaim_distance
) {
1674 sd
->flags
&= ~(SD_BALANCE_EXEC
|
1681 sd
->cache_nice_tries
= 1;
1685 * For all levels sharing cache; connect a sched_domain_shared
1688 if (sd
->flags
& SD_SHARE_LLC
) {
1689 sd
->shared
= *per_cpu_ptr(sdd
->sds
, sd_id
);
1690 atomic_inc(&sd
->shared
->ref
);
1691 atomic_set(&sd
->shared
->nr_busy_cpus
, sd_weight
);
1700 * Topology list, bottom-up.
1702 static struct sched_domain_topology_level default_topology
[] = {
1703 #ifdef CONFIG_SCHED_SMT
1704 { cpu_smt_mask
, cpu_smt_flags
, SD_INIT_NAME(SMT
) },
1707 #ifdef CONFIG_SCHED_CLUSTER
1708 { cpu_clustergroup_mask
, cpu_cluster_flags
, SD_INIT_NAME(CLS
) },
1711 #ifdef CONFIG_SCHED_MC
1712 { cpu_coregroup_mask
, cpu_core_flags
, SD_INIT_NAME(MC
) },
1714 { cpu_cpu_mask
, SD_INIT_NAME(PKG
) },
1718 static struct sched_domain_topology_level
*sched_domain_topology
=
1720 static struct sched_domain_topology_level
*sched_domain_topology_saved
;
1722 #define for_each_sd_topology(tl) \
1723 for (tl = sched_domain_topology; tl->mask; tl++)
1725 void __init
set_sched_topology(struct sched_domain_topology_level
*tl
)
1727 if (WARN_ON_ONCE(sched_smp_initialized
))
1730 sched_domain_topology
= tl
;
1731 sched_domain_topology_saved
= NULL
;
1736 static const struct cpumask
*sd_numa_mask(int cpu
)
1738 return sched_domains_numa_masks
[sched_domains_curr_level
][cpu_to_node(cpu
)];
1741 static void sched_numa_warn(const char *str
)
1743 static int done
= false;
1751 printk(KERN_WARNING
"ERROR: %s\n\n", str
);
1753 for (i
= 0; i
< nr_node_ids
; i
++) {
1754 printk(KERN_WARNING
" ");
1755 for (j
= 0; j
< nr_node_ids
; j
++) {
1756 if (!node_state(i
, N_CPU
) || !node_state(j
, N_CPU
))
1757 printk(KERN_CONT
"(%02d) ", node_distance(i
,j
));
1759 printk(KERN_CONT
" %02d ", node_distance(i
,j
));
1761 printk(KERN_CONT
"\n");
1763 printk(KERN_WARNING
"\n");
1766 bool find_numa_distance(int distance
)
1771 if (distance
== node_distance(0, 0))
1775 distances
= rcu_dereference(sched_domains_numa_distance
);
1778 for (i
= 0; i
< sched_domains_numa_levels
; i
++) {
1779 if (distances
[i
] == distance
) {
1790 #define for_each_cpu_node_but(n, nbut) \
1791 for_each_node_state(n, N_CPU) \
1797 * A system can have three types of NUMA topology:
1798 * NUMA_DIRECT: all nodes are directly connected, or not a NUMA system
1799 * NUMA_GLUELESS_MESH: some nodes reachable through intermediary nodes
1800 * NUMA_BACKPLANE: nodes can reach other nodes through a backplane
1802 * The difference between a glueless mesh topology and a backplane
1803 * topology lies in whether communication between not directly
1804 * connected nodes goes through intermediary nodes (where programs
1805 * could run), or through backplane controllers. This affects
1806 * placement of programs.
1808 * The type of topology can be discerned with the following tests:
1809 * - If the maximum distance between any nodes is 1 hop, the system
1810 * is directly connected.
1811 * - If for two nodes A and B, located N > 1 hops away from each other,
1812 * there is an intermediary node C, which is < N hops away from both
1813 * nodes A and B, the system is a glueless mesh.
1815 static void init_numa_topology_type(int offline_node
)
1819 n
= sched_max_numa_distance
;
1821 if (sched_domains_numa_levels
<= 2) {
1822 sched_numa_topology_type
= NUMA_DIRECT
;
1826 for_each_cpu_node_but(a
, offline_node
) {
1827 for_each_cpu_node_but(b
, offline_node
) {
1828 /* Find two nodes furthest removed from each other. */
1829 if (node_distance(a
, b
) < n
)
1832 /* Is there an intermediary node between a and b? */
1833 for_each_cpu_node_but(c
, offline_node
) {
1834 if (node_distance(a
, c
) < n
&&
1835 node_distance(b
, c
) < n
) {
1836 sched_numa_topology_type
=
1842 sched_numa_topology_type
= NUMA_BACKPLANE
;
1847 pr_err("Failed to find a NUMA topology type, defaulting to DIRECT\n");
1848 sched_numa_topology_type
= NUMA_DIRECT
;
1852 #define NR_DISTANCE_VALUES (1 << DISTANCE_BITS)
1854 void sched_init_numa(int offline_node
)
1856 struct sched_domain_topology_level
*tl
;
1857 unsigned long *distance_map
;
1861 struct cpumask
***masks
;
1864 * O(nr_nodes^2) de-duplicating selection sort -- in order to find the
1865 * unique distances in the node_distance() table.
1867 distance_map
= bitmap_alloc(NR_DISTANCE_VALUES
, GFP_KERNEL
);
1871 bitmap_zero(distance_map
, NR_DISTANCE_VALUES
);
1872 for_each_cpu_node_but(i
, offline_node
) {
1873 for_each_cpu_node_but(j
, offline_node
) {
1874 int distance
= node_distance(i
, j
);
1876 if (distance
< LOCAL_DISTANCE
|| distance
>= NR_DISTANCE_VALUES
) {
1877 sched_numa_warn("Invalid distance value range");
1878 bitmap_free(distance_map
);
1882 bitmap_set(distance_map
, distance
, 1);
1886 * We can now figure out how many unique distance values there are and
1887 * allocate memory accordingly.
1889 nr_levels
= bitmap_weight(distance_map
, NR_DISTANCE_VALUES
);
1891 distances
= kcalloc(nr_levels
, sizeof(int), GFP_KERNEL
);
1893 bitmap_free(distance_map
);
1897 for (i
= 0, j
= 0; i
< nr_levels
; i
++, j
++) {
1898 j
= find_next_bit(distance_map
, NR_DISTANCE_VALUES
, j
);
1901 rcu_assign_pointer(sched_domains_numa_distance
, distances
);
1903 bitmap_free(distance_map
);
1906 * 'nr_levels' contains the number of unique distances
1908 * The sched_domains_numa_distance[] array includes the actual distance
1913 * Here, we should temporarily reset sched_domains_numa_levels to 0.
1914 * If it fails to allocate memory for array sched_domains_numa_masks[][],
1915 * the array will contain less then 'nr_levels' members. This could be
1916 * dangerous when we use it to iterate array sched_domains_numa_masks[][]
1917 * in other functions.
1919 * We reset it to 'nr_levels' at the end of this function.
1921 sched_domains_numa_levels
= 0;
1923 masks
= kzalloc(sizeof(void *) * nr_levels
, GFP_KERNEL
);
1928 * Now for each level, construct a mask per node which contains all
1929 * CPUs of nodes that are that many hops away from us.
1931 for (i
= 0; i
< nr_levels
; i
++) {
1932 masks
[i
] = kzalloc(nr_node_ids
* sizeof(void *), GFP_KERNEL
);
1936 for_each_cpu_node_but(j
, offline_node
) {
1937 struct cpumask
*mask
= kzalloc(cpumask_size(), GFP_KERNEL
);
1945 for_each_cpu_node_but(k
, offline_node
) {
1946 if (sched_debug() && (node_distance(j
, k
) != node_distance(k
, j
)))
1947 sched_numa_warn("Node-distance not symmetric");
1949 if (node_distance(j
, k
) > sched_domains_numa_distance
[i
])
1952 cpumask_or(mask
, mask
, cpumask_of_node(k
));
1956 rcu_assign_pointer(sched_domains_numa_masks
, masks
);
1958 /* Compute default topology size */
1959 for (i
= 0; sched_domain_topology
[i
].mask
; i
++);
1961 tl
= kzalloc((i
+ nr_levels
+ 1) *
1962 sizeof(struct sched_domain_topology_level
), GFP_KERNEL
);
1967 * Copy the default topology bits..
1969 for (i
= 0; sched_domain_topology
[i
].mask
; i
++)
1970 tl
[i
] = sched_domain_topology
[i
];
1973 * Add the NUMA identity distance, aka single NODE.
1975 tl
[i
++] = (struct sched_domain_topology_level
){
1976 .mask
= sd_numa_mask
,
1982 * .. and append 'j' levels of NUMA goodness.
1984 for (j
= 1; j
< nr_levels
; i
++, j
++) {
1985 tl
[i
] = (struct sched_domain_topology_level
){
1986 .mask
= sd_numa_mask
,
1987 .sd_flags
= cpu_numa_flags
,
1988 .flags
= SDTL_OVERLAP
,
1994 sched_domain_topology_saved
= sched_domain_topology
;
1995 sched_domain_topology
= tl
;
1997 sched_domains_numa_levels
= nr_levels
;
1998 WRITE_ONCE(sched_max_numa_distance
, sched_domains_numa_distance
[nr_levels
- 1]);
2000 init_numa_topology_type(offline_node
);
2004 static void sched_reset_numa(void)
2006 int nr_levels
, *distances
;
2007 struct cpumask
***masks
;
2009 nr_levels
= sched_domains_numa_levels
;
2010 sched_domains_numa_levels
= 0;
2011 sched_max_numa_distance
= 0;
2012 sched_numa_topology_type
= NUMA_DIRECT
;
2013 distances
= sched_domains_numa_distance
;
2014 rcu_assign_pointer(sched_domains_numa_distance
, NULL
);
2015 masks
= sched_domains_numa_masks
;
2016 rcu_assign_pointer(sched_domains_numa_masks
, NULL
);
2017 if (distances
|| masks
) {
2022 for (i
= 0; i
< nr_levels
&& masks
; i
++) {
2031 if (sched_domain_topology_saved
) {
2032 kfree(sched_domain_topology
);
2033 sched_domain_topology
= sched_domain_topology_saved
;
2034 sched_domain_topology_saved
= NULL
;
2039 * Call with hotplug lock held
2041 void sched_update_numa(int cpu
, bool online
)
2045 node
= cpu_to_node(cpu
);
2047 * Scheduler NUMA topology is updated when the first CPU of a
2048 * node is onlined or the last CPU of a node is offlined.
2050 if (cpumask_weight(cpumask_of_node(node
)) != 1)
2054 sched_init_numa(online
? NUMA_NO_NODE
: node
);
2057 void sched_domains_numa_masks_set(unsigned int cpu
)
2059 int node
= cpu_to_node(cpu
);
2062 for (i
= 0; i
< sched_domains_numa_levels
; i
++) {
2063 for (j
= 0; j
< nr_node_ids
; j
++) {
2064 if (!node_state(j
, N_CPU
))
2067 /* Set ourselves in the remote node's masks */
2068 if (node_distance(j
, node
) <= sched_domains_numa_distance
[i
])
2069 cpumask_set_cpu(cpu
, sched_domains_numa_masks
[i
][j
]);
2074 void sched_domains_numa_masks_clear(unsigned int cpu
)
2078 for (i
= 0; i
< sched_domains_numa_levels
; i
++) {
2079 for (j
= 0; j
< nr_node_ids
; j
++) {
2080 if (sched_domains_numa_masks
[i
][j
])
2081 cpumask_clear_cpu(cpu
, sched_domains_numa_masks
[i
][j
]);
2087 * sched_numa_find_closest() - given the NUMA topology, find the cpu
2088 * closest to @cpu from @cpumask.
2089 * cpumask: cpumask to find a cpu from
2090 * cpu: cpu to be close to
2092 * returns: cpu, or nr_cpu_ids when nothing found.
2094 int sched_numa_find_closest(const struct cpumask
*cpus
, int cpu
)
2096 int i
, j
= cpu_to_node(cpu
), found
= nr_cpu_ids
;
2097 struct cpumask
***masks
;
2100 masks
= rcu_dereference(sched_domains_numa_masks
);
2103 for (i
= 0; i
< sched_domains_numa_levels
; i
++) {
2106 cpu
= cpumask_any_and(cpus
, masks
[i
][j
]);
2107 if (cpu
< nr_cpu_ids
) {
2119 const struct cpumask
*cpus
;
2120 struct cpumask
***masks
;
2126 static int hop_cmp(const void *a
, const void *b
)
2128 struct cpumask
**prev_hop
, **cur_hop
= *(struct cpumask
***)b
;
2129 struct __cmp_key
*k
= (struct __cmp_key
*)a
;
2131 if (cpumask_weight_and(k
->cpus
, cur_hop
[k
->node
]) <= k
->cpu
)
2134 if (b
== k
->masks
) {
2139 prev_hop
= *((struct cpumask
***)b
- 1);
2140 k
->w
= cpumask_weight_and(k
->cpus
, prev_hop
[k
->node
]);
2148 * sched_numa_find_nth_cpu() - given the NUMA topology, find the Nth closest CPU
2149 * from @cpus to @cpu, taking into account distance
2150 * from a given @node.
2151 * @cpus: cpumask to find a cpu from
2152 * @cpu: CPU to start searching
2153 * @node: NUMA node to order CPUs by distance
2155 * Return: cpu, or nr_cpu_ids when nothing found.
2157 int sched_numa_find_nth_cpu(const struct cpumask
*cpus
, int cpu
, int node
)
2159 struct __cmp_key k
= { .cpus
= cpus
, .cpu
= cpu
};
2160 struct cpumask
***hop_masks
;
2161 int hop
, ret
= nr_cpu_ids
;
2163 if (node
== NUMA_NO_NODE
)
2164 return cpumask_nth_and(cpu
, cpus
, cpu_online_mask
);
2168 /* CPU-less node entries are uninitialized in sched_domains_numa_masks */
2169 node
= numa_nearest_node(node
, N_CPU
);
2172 k
.masks
= rcu_dereference(sched_domains_numa_masks
);
2176 hop_masks
= bsearch(&k
, k
.masks
, sched_domains_numa_levels
, sizeof(k
.masks
[0]), hop_cmp
);
2177 hop
= hop_masks
- k
.masks
;
2180 cpumask_nth_and_andnot(cpu
- k
.w
, cpus
, k
.masks
[hop
][node
], k
.masks
[hop
-1][node
]) :
2181 cpumask_nth_and(cpu
, cpus
, k
.masks
[0][node
]);
2186 EXPORT_SYMBOL_GPL(sched_numa_find_nth_cpu
);
2189 * sched_numa_hop_mask() - Get the cpumask of CPUs at most @hops hops away from
2191 * @node: The node to count hops from.
2192 * @hops: Include CPUs up to that many hops away. 0 means local node.
2194 * Return: On success, a pointer to a cpumask of CPUs at most @hops away from
2195 * @node, an error value otherwise.
2197 * Requires rcu_lock to be held. Returned cpumask is only valid within that
2198 * read-side section, copy it if required beyond that.
2200 * Note that not all hops are equal in distance; see sched_init_numa() for how
2201 * distances and masks are handled.
2202 * Also note that this is a reflection of sched_domains_numa_masks, which may change
2203 * during the lifetime of the system (offline nodes are taken out of the masks).
2205 const struct cpumask
*sched_numa_hop_mask(unsigned int node
, unsigned int hops
)
2207 struct cpumask
***masks
;
2209 if (node
>= nr_node_ids
|| hops
>= sched_domains_numa_levels
)
2210 return ERR_PTR(-EINVAL
);
2212 masks
= rcu_dereference(sched_domains_numa_masks
);
2214 return ERR_PTR(-EBUSY
);
2216 return masks
[hops
][node
];
2218 EXPORT_SYMBOL_GPL(sched_numa_hop_mask
);
2220 #endif /* CONFIG_NUMA */
2222 static int __sdt_alloc(const struct cpumask
*cpu_map
)
2224 struct sched_domain_topology_level
*tl
;
2227 for_each_sd_topology(tl
) {
2228 struct sd_data
*sdd
= &tl
->data
;
2230 sdd
->sd
= alloc_percpu(struct sched_domain
*);
2234 sdd
->sds
= alloc_percpu(struct sched_domain_shared
*);
2238 sdd
->sg
= alloc_percpu(struct sched_group
*);
2242 sdd
->sgc
= alloc_percpu(struct sched_group_capacity
*);
2246 for_each_cpu(j
, cpu_map
) {
2247 struct sched_domain
*sd
;
2248 struct sched_domain_shared
*sds
;
2249 struct sched_group
*sg
;
2250 struct sched_group_capacity
*sgc
;
2252 sd
= kzalloc_node(sizeof(struct sched_domain
) + cpumask_size(),
2253 GFP_KERNEL
, cpu_to_node(j
));
2257 *per_cpu_ptr(sdd
->sd
, j
) = sd
;
2259 sds
= kzalloc_node(sizeof(struct sched_domain_shared
),
2260 GFP_KERNEL
, cpu_to_node(j
));
2264 *per_cpu_ptr(sdd
->sds
, j
) = sds
;
2266 sg
= kzalloc_node(sizeof(struct sched_group
) + cpumask_size(),
2267 GFP_KERNEL
, cpu_to_node(j
));
2273 *per_cpu_ptr(sdd
->sg
, j
) = sg
;
2275 sgc
= kzalloc_node(sizeof(struct sched_group_capacity
) + cpumask_size(),
2276 GFP_KERNEL
, cpu_to_node(j
));
2280 #ifdef CONFIG_SCHED_DEBUG
2284 *per_cpu_ptr(sdd
->sgc
, j
) = sgc
;
2291 static void __sdt_free(const struct cpumask
*cpu_map
)
2293 struct sched_domain_topology_level
*tl
;
2296 for_each_sd_topology(tl
) {
2297 struct sd_data
*sdd
= &tl
->data
;
2299 for_each_cpu(j
, cpu_map
) {
2300 struct sched_domain
*sd
;
2303 sd
= *per_cpu_ptr(sdd
->sd
, j
);
2304 if (sd
&& (sd
->flags
& SD_OVERLAP
))
2305 free_sched_groups(sd
->groups
, 0);
2306 kfree(*per_cpu_ptr(sdd
->sd
, j
));
2310 kfree(*per_cpu_ptr(sdd
->sds
, j
));
2312 kfree(*per_cpu_ptr(sdd
->sg
, j
));
2314 kfree(*per_cpu_ptr(sdd
->sgc
, j
));
2316 free_percpu(sdd
->sd
);
2318 free_percpu(sdd
->sds
);
2320 free_percpu(sdd
->sg
);
2322 free_percpu(sdd
->sgc
);
2327 static struct sched_domain
*build_sched_domain(struct sched_domain_topology_level
*tl
,
2328 const struct cpumask
*cpu_map
, struct sched_domain_attr
*attr
,
2329 struct sched_domain
*child
, int cpu
)
2331 struct sched_domain
*sd
= sd_init(tl
, cpu_map
, child
, cpu
);
2334 sd
->level
= child
->level
+ 1;
2335 sched_domain_level_max
= max(sched_domain_level_max
, sd
->level
);
2338 if (!cpumask_subset(sched_domain_span(child
),
2339 sched_domain_span(sd
))) {
2340 pr_err("BUG: arch topology borken\n");
2341 #ifdef CONFIG_SCHED_DEBUG
2342 pr_err(" the %s domain not a subset of the %s domain\n",
2343 child
->name
, sd
->name
);
2345 /* Fixup, ensure @sd has at least @child CPUs. */
2346 cpumask_or(sched_domain_span(sd
),
2347 sched_domain_span(sd
),
2348 sched_domain_span(child
));
2352 set_domain_attribute(sd
, attr
);
2358 * Ensure topology masks are sane, i.e. there are no conflicts (overlaps) for
2359 * any two given CPUs at this (non-NUMA) topology level.
2361 static bool topology_span_sane(struct sched_domain_topology_level
*tl
,
2362 const struct cpumask
*cpu_map
, int cpu
)
2366 /* NUMA levels are allowed to overlap */
2367 if (tl
->flags
& SDTL_OVERLAP
)
2371 * Non-NUMA levels cannot partially overlap - they must be either
2372 * completely equal or completely disjoint. Otherwise we can end up
2373 * breaking the sched_group lists - i.e. a later get_group() pass
2374 * breaks the linking done for an earlier span.
2376 for_each_cpu_from(i
, cpu_map
) {
2378 * We should 'and' all those masks with 'cpu_map' to exactly
2379 * match the topology we're about to build, but that can only
2380 * remove CPUs, which only lessens our ability to detect
2383 if (!cpumask_equal(tl
->mask(cpu
), tl
->mask(i
)) &&
2384 cpumask_intersects(tl
->mask(cpu
), tl
->mask(i
)))
2392 * Build sched domains for a given set of CPUs and attach the sched domains
2393 * to the individual CPUs
2396 build_sched_domains(const struct cpumask
*cpu_map
, struct sched_domain_attr
*attr
)
2398 enum s_alloc alloc_state
= sa_none
;
2399 struct sched_domain
*sd
;
2401 struct rq
*rq
= NULL
;
2402 int i
, ret
= -ENOMEM
;
2403 bool has_asym
= false;
2404 bool has_cluster
= false;
2406 if (WARN_ON(cpumask_empty(cpu_map
)))
2409 alloc_state
= __visit_domain_allocation_hell(&d
, cpu_map
);
2410 if (alloc_state
!= sa_rootdomain
)
2413 /* Set up domains for CPUs specified by the cpu_map: */
2414 for_each_cpu(i
, cpu_map
) {
2415 struct sched_domain_topology_level
*tl
;
2418 for_each_sd_topology(tl
) {
2420 if (WARN_ON(!topology_span_sane(tl
, cpu_map
, i
)))
2423 sd
= build_sched_domain(tl
, cpu_map
, attr
, sd
, i
);
2425 has_asym
|= sd
->flags
& SD_ASYM_CPUCAPACITY
;
2427 if (tl
== sched_domain_topology
)
2428 *per_cpu_ptr(d
.sd
, i
) = sd
;
2429 if (tl
->flags
& SDTL_OVERLAP
)
2430 sd
->flags
|= SD_OVERLAP
;
2431 if (cpumask_equal(cpu_map
, sched_domain_span(sd
)))
2436 /* Build the groups for the domains */
2437 for_each_cpu(i
, cpu_map
) {
2438 for (sd
= *per_cpu_ptr(d
.sd
, i
); sd
; sd
= sd
->parent
) {
2439 sd
->span_weight
= cpumask_weight(sched_domain_span(sd
));
2440 if (sd
->flags
& SD_OVERLAP
) {
2441 if (build_overlap_sched_groups(sd
, i
))
2444 if (build_sched_groups(sd
, i
))
2451 * Calculate an allowed NUMA imbalance such that LLCs do not get
2454 for_each_cpu(i
, cpu_map
) {
2455 unsigned int imb
= 0;
2456 unsigned int imb_span
= 1;
2458 for (sd
= *per_cpu_ptr(d
.sd
, i
); sd
; sd
= sd
->parent
) {
2459 struct sched_domain
*child
= sd
->child
;
2461 if (!(sd
->flags
& SD_SHARE_LLC
) && child
&&
2462 (child
->flags
& SD_SHARE_LLC
)) {
2463 struct sched_domain __rcu
*top_p
;
2464 unsigned int nr_llcs
;
2467 * For a single LLC per node, allow an
2468 * imbalance up to 12.5% of the node. This is
2469 * arbitrary cutoff based two factors -- SMT and
2470 * memory channels. For SMT-2, the intent is to
2471 * avoid premature sharing of HT resources but
2472 * SMT-4 or SMT-8 *may* benefit from a different
2473 * cutoff. For memory channels, this is a very
2474 * rough estimate of how many channels may be
2475 * active and is based on recent CPUs with
2478 * For multiple LLCs, allow an imbalance
2479 * until multiple tasks would share an LLC
2480 * on one node while LLCs on another node
2481 * remain idle. This assumes that there are
2482 * enough logical CPUs per LLC to avoid SMT
2483 * factors and that there is a correlation
2484 * between LLCs and memory channels.
2486 nr_llcs
= sd
->span_weight
/ child
->span_weight
;
2488 imb
= sd
->span_weight
>> 3;
2492 sd
->imb_numa_nr
= imb
;
2494 /* Set span based on the first NUMA domain. */
2496 while (top_p
&& !(top_p
->flags
& SD_NUMA
)) {
2497 top_p
= top_p
->parent
;
2499 imb_span
= top_p
? top_p
->span_weight
: sd
->span_weight
;
2501 int factor
= max(1U, (sd
->span_weight
/ imb_span
));
2503 sd
->imb_numa_nr
= imb
* factor
;
2508 /* Calculate CPU capacity for physical packages and nodes */
2509 for (i
= nr_cpumask_bits
-1; i
>= 0; i
--) {
2510 if (!cpumask_test_cpu(i
, cpu_map
))
2513 for (sd
= *per_cpu_ptr(d
.sd
, i
); sd
; sd
= sd
->parent
) {
2514 claim_allocations(i
, sd
);
2515 init_sched_groups_capacity(i
, sd
);
2519 /* Attach the domains */
2521 for_each_cpu(i
, cpu_map
) {
2523 sd
= *per_cpu_ptr(d
.sd
, i
);
2525 cpu_attach_domain(sd
, d
.rd
, i
);
2527 if (lowest_flag_domain(i
, SD_CLUSTER
))
2533 static_branch_inc_cpuslocked(&sched_asym_cpucapacity
);
2536 static_branch_inc_cpuslocked(&sched_cluster_active
);
2538 if (rq
&& sched_debug_verbose
)
2539 pr_info("root domain span: %*pbl\n", cpumask_pr_args(cpu_map
));
2543 __free_domain_allocs(&d
, alloc_state
, cpu_map
);
2548 /* Current sched domains: */
2549 static cpumask_var_t
*doms_cur
;
2551 /* Number of sched domains in 'doms_cur': */
2552 static int ndoms_cur
;
2554 /* Attributes of custom domains in 'doms_cur' */
2555 static struct sched_domain_attr
*dattr_cur
;
2558 * Special case: If a kmalloc() of a doms_cur partition (array of
2559 * cpumask) fails, then fallback to a single sched domain,
2560 * as determined by the single cpumask fallback_doms.
2562 static cpumask_var_t fallback_doms
;
2565 * arch_update_cpu_topology lets virtualized architectures update the
2566 * CPU core maps. It is supposed to return 1 if the topology changed
2567 * or 0 if it stayed the same.
2569 int __weak
arch_update_cpu_topology(void)
2574 cpumask_var_t
*alloc_sched_domains(unsigned int ndoms
)
2577 cpumask_var_t
*doms
;
2579 doms
= kmalloc_array(ndoms
, sizeof(*doms
), GFP_KERNEL
);
2582 for (i
= 0; i
< ndoms
; i
++) {
2583 if (!alloc_cpumask_var(&doms
[i
], GFP_KERNEL
)) {
2584 free_sched_domains(doms
, i
);
2591 void free_sched_domains(cpumask_var_t doms
[], unsigned int ndoms
)
2594 for (i
= 0; i
< ndoms
; i
++)
2595 free_cpumask_var(doms
[i
]);
2600 * Set up scheduler domains and groups. For now this just excludes isolated
2601 * CPUs, but could be used to exclude other special cases in the future.
2603 int __init
sched_init_domains(const struct cpumask
*cpu_map
)
2607 zalloc_cpumask_var(&sched_domains_tmpmask
, GFP_KERNEL
);
2608 zalloc_cpumask_var(&sched_domains_tmpmask2
, GFP_KERNEL
);
2609 zalloc_cpumask_var(&fallback_doms
, GFP_KERNEL
);
2611 arch_update_cpu_topology();
2612 asym_cpu_capacity_scan();
2614 doms_cur
= alloc_sched_domains(ndoms_cur
);
2616 doms_cur
= &fallback_doms
;
2617 cpumask_and(doms_cur
[0], cpu_map
, housekeeping_cpumask(HK_TYPE_DOMAIN
));
2618 err
= build_sched_domains(doms_cur
[0], NULL
);
2624 * Detach sched domains from a group of CPUs specified in cpu_map
2625 * These CPUs will now be attached to the NULL domain
2627 static void detach_destroy_domains(const struct cpumask
*cpu_map
)
2629 unsigned int cpu
= cpumask_any(cpu_map
);
2632 if (rcu_access_pointer(per_cpu(sd_asym_cpucapacity
, cpu
)))
2633 static_branch_dec_cpuslocked(&sched_asym_cpucapacity
);
2635 if (static_branch_unlikely(&sched_cluster_active
))
2636 static_branch_dec_cpuslocked(&sched_cluster_active
);
2639 for_each_cpu(i
, cpu_map
)
2640 cpu_attach_domain(NULL
, &def_root_domain
, i
);
2644 /* handle null as "default" */
2645 static int dattrs_equal(struct sched_domain_attr
*cur
, int idx_cur
,
2646 struct sched_domain_attr
*new, int idx_new
)
2648 struct sched_domain_attr tmp
;
2656 return !memcmp(cur
? (cur
+ idx_cur
) : &tmp
,
2657 new ? (new + idx_new
) : &tmp
,
2658 sizeof(struct sched_domain_attr
));
2662 * Partition sched domains as specified by the 'ndoms_new'
2663 * cpumasks in the array doms_new[] of cpumasks. This compares
2664 * doms_new[] to the current sched domain partitioning, doms_cur[].
2665 * It destroys each deleted domain and builds each new domain.
2667 * 'doms_new' is an array of cpumask_var_t's of length 'ndoms_new'.
2668 * The masks don't intersect (don't overlap.) We should setup one
2669 * sched domain for each mask. CPUs not in any of the cpumasks will
2670 * not be load balanced. If the same cpumask appears both in the
2671 * current 'doms_cur' domains and in the new 'doms_new', we can leave
2674 * The passed in 'doms_new' should be allocated using
2675 * alloc_sched_domains. This routine takes ownership of it and will
2676 * free_sched_domains it when done with it. If the caller failed the
2677 * alloc call, then it can pass in doms_new == NULL && ndoms_new == 1,
2678 * and partition_sched_domains() will fallback to the single partition
2679 * 'fallback_doms', it also forces the domains to be rebuilt.
2681 * If doms_new == NULL it will be replaced with cpu_online_mask.
2682 * ndoms_new == 0 is a special case for destroying existing domains,
2683 * and it will not create the default domain.
2685 * Call with hotplug lock and sched_domains_mutex held
2687 void partition_sched_domains_locked(int ndoms_new
, cpumask_var_t doms_new
[],
2688 struct sched_domain_attr
*dattr_new
)
2690 bool __maybe_unused has_eas
= false;
2694 lockdep_assert_held(&sched_domains_mutex
);
2696 /* Let the architecture update CPU core mappings: */
2697 new_topology
= arch_update_cpu_topology();
2698 /* Trigger rebuilding CPU capacity asymmetry data */
2700 asym_cpu_capacity_scan();
2703 WARN_ON_ONCE(dattr_new
);
2705 doms_new
= alloc_sched_domains(1);
2708 cpumask_and(doms_new
[0], cpu_active_mask
,
2709 housekeeping_cpumask(HK_TYPE_DOMAIN
));
2715 /* Destroy deleted domains: */
2716 for (i
= 0; i
< ndoms_cur
; i
++) {
2717 for (j
= 0; j
< n
&& !new_topology
; j
++) {
2718 if (cpumask_equal(doms_cur
[i
], doms_new
[j
]) &&
2719 dattrs_equal(dattr_cur
, i
, dattr_new
, j
)) {
2720 struct root_domain
*rd
;
2723 * This domain won't be destroyed and as such
2724 * its dl_bw->total_bw needs to be cleared. It
2725 * will be recomputed in function
2726 * update_tasks_root_domain().
2728 rd
= cpu_rq(cpumask_any(doms_cur
[i
]))->rd
;
2729 dl_clear_root_domain(rd
);
2733 /* No match - a current sched domain not in new doms_new[] */
2734 detach_destroy_domains(doms_cur
[i
]);
2742 doms_new
= &fallback_doms
;
2743 cpumask_and(doms_new
[0], cpu_active_mask
,
2744 housekeeping_cpumask(HK_TYPE_DOMAIN
));
2747 /* Build new domains: */
2748 for (i
= 0; i
< ndoms_new
; i
++) {
2749 for (j
= 0; j
< n
&& !new_topology
; j
++) {
2750 if (cpumask_equal(doms_new
[i
], doms_cur
[j
]) &&
2751 dattrs_equal(dattr_new
, i
, dattr_cur
, j
))
2754 /* No match - add a new doms_new */
2755 build_sched_domains(doms_new
[i
], dattr_new
? dattr_new
+ i
: NULL
);
2760 #if defined(CONFIG_ENERGY_MODEL) && defined(CONFIG_CPU_FREQ_GOV_SCHEDUTIL)
2761 /* Build perf domains: */
2762 for (i
= 0; i
< ndoms_new
; i
++) {
2763 for (j
= 0; j
< n
&& !sched_energy_update
; j
++) {
2764 if (cpumask_equal(doms_new
[i
], doms_cur
[j
]) &&
2765 cpu_rq(cpumask_first(doms_cur
[j
]))->rd
->pd
) {
2770 /* No match - add perf domains for a new rd */
2771 has_eas
|= build_perf_domains(doms_new
[i
]);
2775 sched_energy_set(has_eas
);
2778 /* Remember the new sched domains: */
2779 if (doms_cur
!= &fallback_doms
)
2780 free_sched_domains(doms_cur
, ndoms_cur
);
2783 doms_cur
= doms_new
;
2784 dattr_cur
= dattr_new
;
2785 ndoms_cur
= ndoms_new
;
2787 update_sched_domain_debugfs();
2791 * Call with hotplug lock held
2793 void partition_sched_domains(int ndoms_new
, cpumask_var_t doms_new
[],
2794 struct sched_domain_attr
*dattr_new
)
2796 mutex_lock(&sched_domains_mutex
);
2797 partition_sched_domains_locked(ndoms_new
, doms_new
, dattr_new
);
2798 mutex_unlock(&sched_domains_mutex
);