1 // SPDX-License-Identifier: GPL-2.0
2 /*
3 * Scheduler topology setup/handling methods
4 */
5
6 #include <linux/bsearch.h>
7 #include <trace/hooks/sched.h>
8
9 DEFINE_MUTEX(sched_domains_mutex);
10 #ifdef CONFIG_LOCKDEP
11 EXPORT_SYMBOL_GPL(sched_domains_mutex);
12 #endif
13
14 /* Protected by sched_domains_mutex: */
15 static cpumask_var_t sched_domains_tmpmask;
16 static cpumask_var_t sched_domains_tmpmask2;
17
18 #ifdef CONFIG_SCHED_DEBUG
19
sched_debug_setup(char * str)20 static int __init sched_debug_setup(char *str)
21 {
22 sched_debug_verbose = true;
23
24 return 0;
25 }
26 early_param("sched_verbose", sched_debug_setup);
27
sched_debug(void)28 static inline bool sched_debug(void)
29 {
30 return sched_debug_verbose;
31 }
32
33 #define SD_FLAG(_name, mflags) [__##_name] = { .meta_flags = mflags, .name = #_name },
34 const struct sd_flag_debug sd_flag_debug[] = {
35 #include <linux/sched/sd_flags.h>
36 };
37 #undef SD_FLAG
38
sched_domain_debug_one(struct sched_domain * sd,int cpu,int level,struct cpumask * groupmask)39 static int sched_domain_debug_one(struct sched_domain *sd, int cpu, int level,
40 struct cpumask *groupmask)
41 {
42 struct sched_group *group = sd->groups;
43 unsigned long flags = sd->flags;
44 unsigned int idx;
45
46 cpumask_clear(groupmask);
47
48 printk(KERN_DEBUG "%*s domain-%d: ", level, "", level);
49 printk(KERN_CONT "span=%*pbl level=%s\n",
50 cpumask_pr_args(sched_domain_span(sd)), sd->name);
51
52 if (!cpumask_test_cpu(cpu, sched_domain_span(sd))) {
53 printk(KERN_ERR "ERROR: domain->span does not contain CPU%d\n", cpu);
54 }
55 if (group && !cpumask_test_cpu(cpu, sched_group_span(group))) {
56 printk(KERN_ERR "ERROR: domain->groups does not contain CPU%d\n", cpu);
57 }
58
59 for_each_set_bit(idx, &flags, __SD_FLAG_CNT) {
60 unsigned int flag = BIT(idx);
61 unsigned int meta_flags = sd_flag_debug[idx].meta_flags;
62
63 if ((meta_flags & SDF_SHARED_CHILD) && sd->child &&
64 !(sd->child->flags & flag))
65 printk(KERN_ERR "ERROR: flag %s set here but not in child\n",
66 sd_flag_debug[idx].name);
67
68 if ((meta_flags & SDF_SHARED_PARENT) && sd->parent &&
69 !(sd->parent->flags & flag))
70 printk(KERN_ERR "ERROR: flag %s set here but not in parent\n",
71 sd_flag_debug[idx].name);
72 }
73
74 printk(KERN_DEBUG "%*s groups:", level + 1, "");
75 do {
76 if (!group) {
77 printk("\n");
78 printk(KERN_ERR "ERROR: group is NULL\n");
79 break;
80 }
81
82 if (cpumask_empty(sched_group_span(group))) {
83 printk(KERN_CONT "\n");
84 printk(KERN_ERR "ERROR: empty group\n");
85 break;
86 }
87
88 if (!(sd->flags & SD_OVERLAP) &&
89 cpumask_intersects(groupmask, sched_group_span(group))) {
90 printk(KERN_CONT "\n");
91 printk(KERN_ERR "ERROR: repeated CPUs\n");
92 break;
93 }
94
95 cpumask_or(groupmask, groupmask, sched_group_span(group));
96
97 printk(KERN_CONT " %d:{ span=%*pbl",
98 group->sgc->id,
99 cpumask_pr_args(sched_group_span(group)));
100
101 if ((sd->flags & SD_OVERLAP) &&
102 !cpumask_equal(group_balance_mask(group), sched_group_span(group))) {
103 printk(KERN_CONT " mask=%*pbl",
104 cpumask_pr_args(group_balance_mask(group)));
105 }
106
107 if (group->sgc->capacity != SCHED_CAPACITY_SCALE)
108 printk(KERN_CONT " cap=%lu", group->sgc->capacity);
109
110 if (group == sd->groups && sd->child &&
111 !cpumask_equal(sched_domain_span(sd->child),
112 sched_group_span(group))) {
113 printk(KERN_ERR "ERROR: domain->groups does not match domain->child\n");
114 }
115
116 printk(KERN_CONT " }");
117
118 group = group->next;
119
120 if (group != sd->groups)
121 printk(KERN_CONT ",");
122
123 } while (group != sd->groups);
124 printk(KERN_CONT "\n");
125
126 if (!cpumask_equal(sched_domain_span(sd), groupmask))
127 printk(KERN_ERR "ERROR: groups don't span domain->span\n");
128
129 if (sd->parent &&
130 !cpumask_subset(groupmask, sched_domain_span(sd->parent)))
131 printk(KERN_ERR "ERROR: parent span is not a superset of domain->span\n");
132 return 0;
133 }
134
sched_domain_debug(struct sched_domain * sd,int cpu)135 static void sched_domain_debug(struct sched_domain *sd, int cpu)
136 {
137 int level = 0;
138
139 if (!sched_debug_verbose)
140 return;
141
142 if (!sd) {
143 printk(KERN_DEBUG "CPU%d attaching NULL sched-domain.\n", cpu);
144 return;
145 }
146
147 printk(KERN_DEBUG "CPU%d attaching sched-domain(s):\n", cpu);
148
149 for (;;) {
150 if (sched_domain_debug_one(sd, cpu, level, sched_domains_tmpmask))
151 break;
152 level++;
153 sd = sd->parent;
154 if (!sd)
155 break;
156 }
157 }
158 #else /* !CONFIG_SCHED_DEBUG */
159
160 # define sched_debug_verbose 0
161 # define sched_domain_debug(sd, cpu) do { } while (0)
sched_debug(void)162 static inline bool sched_debug(void)
163 {
164 return false;
165 }
166 #endif /* CONFIG_SCHED_DEBUG */
167
168 /* Generate a mask of SD flags with the SDF_NEEDS_GROUPS metaflag */
169 #define SD_FLAG(name, mflags) (name * !!((mflags) & SDF_NEEDS_GROUPS)) |
170 static const unsigned int SD_DEGENERATE_GROUPS_MASK =
171 #include <linux/sched/sd_flags.h>
172 0;
173 #undef SD_FLAG
174
sd_degenerate(struct sched_domain * sd)175 static int sd_degenerate(struct sched_domain *sd)
176 {
177 if (cpumask_weight(sched_domain_span(sd)) == 1)
178 return 1;
179
180 /* Following flags need at least 2 groups */
181 if ((sd->flags & SD_DEGENERATE_GROUPS_MASK) &&
182 (sd->groups != sd->groups->next))
183 return 0;
184
185 /* Following flags don't use groups */
186 if (sd->flags & (SD_WAKE_AFFINE))
187 return 0;
188
189 return 1;
190 }
191
192 static int
sd_parent_degenerate(struct sched_domain * sd,struct sched_domain * parent)193 sd_parent_degenerate(struct sched_domain *sd, struct sched_domain *parent)
194 {
195 unsigned long cflags = sd->flags, pflags = parent->flags;
196
197 if (sd_degenerate(parent))
198 return 1;
199
200 if (!cpumask_equal(sched_domain_span(sd), sched_domain_span(parent)))
201 return 0;
202
203 /* Flags needing groups don't count if only 1 group in parent */
204 if (parent->groups == parent->groups->next)
205 pflags &= ~SD_DEGENERATE_GROUPS_MASK;
206
207 if (~cflags & pflags)
208 return 0;
209
210 return 1;
211 }
212
213 #if defined(CONFIG_ENERGY_MODEL) && defined(CONFIG_CPU_FREQ_GOV_SCHEDUTIL)
214 DEFINE_STATIC_KEY_FALSE(sched_energy_present);
215 static unsigned int sysctl_sched_energy_aware = 1;
216 static DEFINE_MUTEX(sched_energy_mutex);
217 static bool sched_energy_update;
218
sched_is_eas_possible(const struct cpumask * cpu_mask)219 static bool sched_is_eas_possible(const struct cpumask *cpu_mask)
220 {
221 bool any_asym_capacity = false;
222 struct cpufreq_policy *policy;
223 struct cpufreq_governor *gov;
224 int i;
225 bool eas_check = false;
226
227 trace_android_rvh_build_perf_domains(&eas_check);
228 if (eas_check)
229 return true;
230
231 /* EAS is enabled for asymmetric CPU capacity topologies. */
232 for_each_cpu(i, cpu_mask) {
233 if (rcu_access_pointer(per_cpu(sd_asym_cpucapacity, i))) {
234 any_asym_capacity = true;
235 break;
236 }
237 }
238 if (!any_asym_capacity) {
239 if (sched_debug()) {
240 pr_info("rd %*pbl: Checking EAS, CPUs do not have asymmetric capacities\n",
241 cpumask_pr_args(cpu_mask));
242 }
243 return false;
244 }
245
246 /* EAS definitely does *not* handle SMT */
247 if (sched_smt_active()) {
248 if (sched_debug()) {
249 pr_info("rd %*pbl: Checking EAS, SMT is not supported\n",
250 cpumask_pr_args(cpu_mask));
251 }
252 return false;
253 }
254
255 if (!arch_scale_freq_invariant()) {
256 if (sched_debug()) {
257 pr_info("rd %*pbl: Checking EAS: frequency-invariant load tracking not yet supported",
258 cpumask_pr_args(cpu_mask));
259 }
260 return false;
261 }
262
263 /* Do not attempt EAS if schedutil is not being used. */
264 for_each_cpu(i, cpu_mask) {
265 policy = cpufreq_cpu_get(i);
266 if (!policy) {
267 if (sched_debug()) {
268 pr_info("rd %*pbl: Checking EAS, cpufreq policy not set for CPU: %d",
269 cpumask_pr_args(cpu_mask), i);
270 }
271 return false;
272 }
273 gov = policy->governor;
274 cpufreq_cpu_put(policy);
275 if (gov != &schedutil_gov) {
276 if (sched_debug()) {
277 pr_info("rd %*pbl: Checking EAS, schedutil is mandatory\n",
278 cpumask_pr_args(cpu_mask));
279 }
280 return false;
281 }
282 }
283
284 return true;
285 }
286
rebuild_sched_domains_energy(void)287 void rebuild_sched_domains_energy(void)
288 {
289 mutex_lock(&sched_energy_mutex);
290 sched_energy_update = true;
291 rebuild_sched_domains();
292 sched_energy_update = false;
293 mutex_unlock(&sched_energy_mutex);
294 }
295
296 #ifdef CONFIG_PROC_SYSCTL
sched_energy_aware_handler(const struct ctl_table * table,int write,void * buffer,size_t * lenp,loff_t * ppos)297 static int sched_energy_aware_handler(const struct ctl_table *table, int write,
298 void *buffer, size_t *lenp, loff_t *ppos)
299 {
300 int ret, state;
301
302 if (write && !capable(CAP_SYS_ADMIN))
303 return -EPERM;
304
305 if (!sched_is_eas_possible(cpu_active_mask)) {
306 if (write) {
307 return -EOPNOTSUPP;
308 } else {
309 *lenp = 0;
310 return 0;
311 }
312 }
313
314 ret = proc_dointvec_minmax(table, write, buffer, lenp, ppos);
315 if (!ret && write) {
316 state = static_branch_unlikely(&sched_energy_present);
317 if (state != sysctl_sched_energy_aware)
318 rebuild_sched_domains_energy();
319 }
320
321 return ret;
322 }
323
324 static struct ctl_table sched_energy_aware_sysctls[] = {
325 {
326 .procname = "sched_energy_aware",
327 .data = &sysctl_sched_energy_aware,
328 .maxlen = sizeof(unsigned int),
329 .mode = 0644,
330 .proc_handler = sched_energy_aware_handler,
331 .extra1 = SYSCTL_ZERO,
332 .extra2 = SYSCTL_ONE,
333 },
334 };
335
sched_energy_aware_sysctl_init(void)336 static int __init sched_energy_aware_sysctl_init(void)
337 {
338 register_sysctl_init("kernel", sched_energy_aware_sysctls);
339 return 0;
340 }
341
342 late_initcall(sched_energy_aware_sysctl_init);
343 #endif
344
free_pd(struct perf_domain * pd)345 static void free_pd(struct perf_domain *pd)
346 {
347 struct perf_domain *tmp;
348
349 while (pd) {
350 tmp = pd->next;
351 kfree(pd);
352 pd = tmp;
353 }
354 }
355
find_pd(struct perf_domain * pd,int cpu)356 static struct perf_domain *find_pd(struct perf_domain *pd, int cpu)
357 {
358 while (pd) {
359 if (cpumask_test_cpu(cpu, perf_domain_span(pd)))
360 return pd;
361 pd = pd->next;
362 }
363
364 return NULL;
365 }
366
pd_init(int cpu)367 static struct perf_domain *pd_init(int cpu)
368 {
369 struct em_perf_domain *obj = em_cpu_get(cpu);
370 struct perf_domain *pd;
371
372 if (!obj) {
373 if (sched_debug())
374 pr_info("%s: no EM found for CPU%d\n", __func__, cpu);
375 return NULL;
376 }
377
378 pd = kzalloc(sizeof(*pd), GFP_KERNEL);
379 if (!pd)
380 return NULL;
381 pd->em_pd = obj;
382
383 return pd;
384 }
385
perf_domain_debug(const struct cpumask * cpu_map,struct perf_domain * pd)386 static void perf_domain_debug(const struct cpumask *cpu_map,
387 struct perf_domain *pd)
388 {
389 if (!sched_debug() || !pd)
390 return;
391
392 printk(KERN_DEBUG "root_domain %*pbl:", cpumask_pr_args(cpu_map));
393
394 while (pd) {
395 printk(KERN_CONT " pd%d:{ cpus=%*pbl nr_pstate=%d }",
396 cpumask_first(perf_domain_span(pd)),
397 cpumask_pr_args(perf_domain_span(pd)),
398 em_pd_nr_perf_states(pd->em_pd));
399 pd = pd->next;
400 }
401
402 printk(KERN_CONT "\n");
403 }
404
destroy_perf_domain_rcu(struct rcu_head * rp)405 static void destroy_perf_domain_rcu(struct rcu_head *rp)
406 {
407 struct perf_domain *pd;
408
409 pd = container_of(rp, struct perf_domain, rcu);
410 free_pd(pd);
411 }
412
sched_energy_set(bool has_eas)413 static void sched_energy_set(bool has_eas)
414 {
415 if (!has_eas && static_branch_unlikely(&sched_energy_present)) {
416 if (sched_debug())
417 pr_info("%s: stopping EAS\n", __func__);
418 static_branch_disable_cpuslocked(&sched_energy_present);
419 } else if (has_eas && !static_branch_unlikely(&sched_energy_present)) {
420 if (sched_debug())
421 pr_info("%s: starting EAS\n", __func__);
422 static_branch_enable_cpuslocked(&sched_energy_present);
423 }
424 }
425
426 /*
427 * EAS can be used on a root domain if it meets all the following conditions:
428 * 1. an Energy Model (EM) is available;
429 * 2. the SD_ASYM_CPUCAPACITY flag is set in the sched_domain hierarchy.
430 * 3. no SMT is detected.
431 * 4. schedutil is driving the frequency of all CPUs of the rd;
432 * 5. frequency invariance support is present;
433 */
build_perf_domains(const struct cpumask * cpu_map)434 static bool build_perf_domains(const struct cpumask *cpu_map)
435 {
436 int i;
437 struct perf_domain *pd = NULL, *tmp;
438 int cpu = cpumask_first(cpu_map);
439 struct root_domain *rd = cpu_rq(cpu)->rd;
440
441 if (!sysctl_sched_energy_aware)
442 goto free;
443
444 if (!sched_is_eas_possible(cpu_map))
445 goto free;
446
447 for_each_cpu(i, cpu_map) {
448 /* Skip already covered CPUs. */
449 if (find_pd(pd, i))
450 continue;
451
452 /* Create the new pd and add it to the local list. */
453 tmp = pd_init(i);
454 if (!tmp)
455 goto free;
456 tmp->next = pd;
457 pd = tmp;
458 }
459
460 perf_domain_debug(cpu_map, pd);
461
462 /* Attach the new list of performance domains to the root domain. */
463 tmp = rd->pd;
464 rcu_assign_pointer(rd->pd, pd);
465 if (tmp)
466 call_rcu(&tmp->rcu, destroy_perf_domain_rcu);
467
468 return !!pd;
469
470 free:
471 free_pd(pd);
472 tmp = rd->pd;
473 rcu_assign_pointer(rd->pd, NULL);
474 if (tmp)
475 call_rcu(&tmp->rcu, destroy_perf_domain_rcu);
476
477 return false;
478 }
479 #else
free_pd(struct perf_domain * pd)480 static void free_pd(struct perf_domain *pd) { }
481 #endif /* CONFIG_ENERGY_MODEL && CONFIG_CPU_FREQ_GOV_SCHEDUTIL*/
482
free_rootdomain(struct rcu_head * rcu)483 static void free_rootdomain(struct rcu_head *rcu)
484 {
485 struct root_domain *rd = container_of(rcu, struct root_domain, rcu);
486
487 cpupri_cleanup(&rd->cpupri);
488 cpudl_cleanup(&rd->cpudl);
489 free_cpumask_var(rd->dlo_mask);
490 free_cpumask_var(rd->rto_mask);
491 free_cpumask_var(rd->online);
492 free_cpumask_var(rd->span);
493 free_pd(rd->pd);
494 kfree(rd);
495 }
496
rq_attach_root(struct rq * rq,struct root_domain * rd)497 void rq_attach_root(struct rq *rq, struct root_domain *rd)
498 {
499 struct root_domain *old_rd = NULL;
500 struct rq_flags rf;
501
502 rq_lock_irqsave(rq, &rf);
503
504 if (rq->rd) {
505 old_rd = rq->rd;
506
507 if (cpumask_test_cpu(rq->cpu, old_rd->online))
508 set_rq_offline(rq);
509
510 cpumask_clear_cpu(rq->cpu, old_rd->span);
511
512 /*
513 * If we don't want to free the old_rd yet then
514 * set old_rd to NULL to skip the freeing later
515 * in this function:
516 */
517 if (!atomic_dec_and_test(&old_rd->refcount))
518 old_rd = NULL;
519 }
520
521 atomic_inc(&rd->refcount);
522 rq->rd = rd;
523
524 cpumask_set_cpu(rq->cpu, rd->span);
525 if (cpumask_test_cpu(rq->cpu, cpu_active_mask))
526 set_rq_online(rq);
527
528 /*
529 * Because the rq is not a task, dl_add_task_root_domain() did not
530 * move the fair server bw to the rd if it already started.
531 * Add it now.
532 */
533 if (rq->fair_server.dl_server)
534 __dl_server_attach_root(&rq->fair_server, rq);
535
536 rq_unlock_irqrestore(rq, &rf);
537
538 if (old_rd)
539 call_rcu(&old_rd->rcu, free_rootdomain);
540 }
541
sched_get_rd(struct root_domain * rd)542 void sched_get_rd(struct root_domain *rd)
543 {
544 atomic_inc(&rd->refcount);
545 }
546
sched_put_rd(struct root_domain * rd)547 void sched_put_rd(struct root_domain *rd)
548 {
549 if (!atomic_dec_and_test(&rd->refcount))
550 return;
551
552 call_rcu(&rd->rcu, free_rootdomain);
553 }
554
init_rootdomain(struct root_domain * rd)555 static int init_rootdomain(struct root_domain *rd)
556 {
557 if (!zalloc_cpumask_var(&rd->span, GFP_KERNEL))
558 goto out;
559 if (!zalloc_cpumask_var(&rd->online, GFP_KERNEL))
560 goto free_span;
561 if (!zalloc_cpumask_var(&rd->dlo_mask, GFP_KERNEL))
562 goto free_online;
563 if (!zalloc_cpumask_var(&rd->rto_mask, GFP_KERNEL))
564 goto free_dlo_mask;
565
566 #ifdef HAVE_RT_PUSH_IPI
567 rd->rto_cpu = -1;
568 raw_spin_lock_init(&rd->rto_lock);
569 rd->rto_push_work = IRQ_WORK_INIT_HARD(rto_push_irq_work_func);
570 #endif
571
572 rd->visit_gen = 0;
573 init_dl_bw(&rd->dl_bw);
574 if (cpudl_init(&rd->cpudl) != 0)
575 goto free_rto_mask;
576
577 if (cpupri_init(&rd->cpupri) != 0)
578 goto free_cpudl;
579 return 0;
580
581 free_cpudl:
582 cpudl_cleanup(&rd->cpudl);
583 free_rto_mask:
584 free_cpumask_var(rd->rto_mask);
585 free_dlo_mask:
586 free_cpumask_var(rd->dlo_mask);
587 free_online:
588 free_cpumask_var(rd->online);
589 free_span:
590 free_cpumask_var(rd->span);
591 out:
592 return -ENOMEM;
593 }
594
595 /*
596 * By default the system creates a single root-domain with all CPUs as
597 * members (mimicking the global state we have today).
598 */
599 struct root_domain def_root_domain;
600
init_defrootdomain(void)601 void __init init_defrootdomain(void)
602 {
603 init_rootdomain(&def_root_domain);
604
605 atomic_set(&def_root_domain.refcount, 1);
606 }
607
alloc_rootdomain(void)608 static struct root_domain *alloc_rootdomain(void)
609 {
610 struct root_domain *rd;
611
612 rd = kzalloc(sizeof(*rd), GFP_KERNEL);
613 if (!rd)
614 return NULL;
615
616 if (init_rootdomain(rd) != 0) {
617 kfree(rd);
618 return NULL;
619 }
620
621 return rd;
622 }
623
free_sched_groups(struct sched_group * sg,int free_sgc)624 static void free_sched_groups(struct sched_group *sg, int free_sgc)
625 {
626 struct sched_group *tmp, *first;
627
628 if (!sg)
629 return;
630
631 first = sg;
632 do {
633 tmp = sg->next;
634
635 if (free_sgc && atomic_dec_and_test(&sg->sgc->ref))
636 kfree(sg->sgc);
637
638 if (atomic_dec_and_test(&sg->ref))
639 kfree(sg);
640 sg = tmp;
641 } while (sg != first);
642 }
643
destroy_sched_domain(struct sched_domain * sd)644 static void destroy_sched_domain(struct sched_domain *sd)
645 {
646 /*
647 * A normal sched domain may have multiple group references, an
648 * overlapping domain, having private groups, only one. Iterate,
649 * dropping group/capacity references, freeing where none remain.
650 */
651 free_sched_groups(sd->groups, 1);
652
653 if (sd->shared && atomic_dec_and_test(&sd->shared->ref))
654 kfree(sd->shared);
655 kfree(sd);
656 }
657
destroy_sched_domains_rcu(struct rcu_head * rcu)658 static void destroy_sched_domains_rcu(struct rcu_head *rcu)
659 {
660 struct sched_domain *sd = container_of(rcu, struct sched_domain, rcu);
661
662 while (sd) {
663 struct sched_domain *parent = sd->parent;
664 destroy_sched_domain(sd);
665 sd = parent;
666 }
667 }
668
destroy_sched_domains(struct sched_domain * sd)669 static void destroy_sched_domains(struct sched_domain *sd)
670 {
671 if (sd)
672 call_rcu(&sd->rcu, destroy_sched_domains_rcu);
673 }
674
675 /*
676 * Keep a special pointer to the highest sched_domain that has SD_SHARE_LLC set
677 * (Last Level Cache Domain) for this allows us to avoid some pointer chasing
678 * select_idle_sibling().
679 *
680 * Also keep a unique ID per domain (we use the first CPU number in the cpumask
681 * of the domain), this allows us to quickly tell if two CPUs are in the same
682 * cache domain, see cpus_share_cache().
683 */
684 DEFINE_PER_CPU(struct sched_domain __rcu *, sd_llc);
685 DEFINE_PER_CPU(int, sd_llc_size);
686 DEFINE_PER_CPU(int, sd_llc_id);
687 DEFINE_PER_CPU(int, sd_share_id);
688 DEFINE_PER_CPU(struct sched_domain_shared __rcu *, sd_llc_shared);
689 DEFINE_PER_CPU(struct sched_domain __rcu *, sd_numa);
690 DEFINE_PER_CPU(struct sched_domain __rcu *, sd_asym_packing);
691 DEFINE_PER_CPU(struct sched_domain __rcu *, sd_asym_cpucapacity);
692
693 DEFINE_STATIC_KEY_FALSE(sched_asym_cpucapacity);
694 DEFINE_STATIC_KEY_FALSE(sched_cluster_active);
695
update_top_cache_domain(int cpu)696 static void update_top_cache_domain(int cpu)
697 {
698 struct sched_domain_shared *sds = NULL;
699 struct sched_domain *sd;
700 int id = cpu;
701 int size = 1;
702
703 sd = highest_flag_domain(cpu, SD_SHARE_LLC);
704 if (sd) {
705 id = cpumask_first(sched_domain_span(sd));
706 size = cpumask_weight(sched_domain_span(sd));
707 sds = sd->shared;
708 }
709
710 rcu_assign_pointer(per_cpu(sd_llc, cpu), sd);
711 per_cpu(sd_llc_size, cpu) = size;
712 per_cpu(sd_llc_id, cpu) = id;
713 rcu_assign_pointer(per_cpu(sd_llc_shared, cpu), sds);
714
715 sd = lowest_flag_domain(cpu, SD_CLUSTER);
716 if (sd)
717 id = cpumask_first(sched_domain_span(sd));
718
719 /*
720 * This assignment should be placed after the sd_llc_id as
721 * we want this id equals to cluster id on cluster machines
722 * but equals to LLC id on non-Cluster machines.
723 */
724 per_cpu(sd_share_id, cpu) = id;
725
726 sd = lowest_flag_domain(cpu, SD_NUMA);
727 rcu_assign_pointer(per_cpu(sd_numa, cpu), sd);
728
729 sd = highest_flag_domain(cpu, SD_ASYM_PACKING);
730 rcu_assign_pointer(per_cpu(sd_asym_packing, cpu), sd);
731
732 sd = lowest_flag_domain(cpu, SD_ASYM_CPUCAPACITY_FULL);
733 rcu_assign_pointer(per_cpu(sd_asym_cpucapacity, cpu), sd);
734 }
735
736 /*
737 * Attach the domain 'sd' to 'cpu' as its base domain. Callers must
738 * hold the hotplug lock.
739 */
740 static void
cpu_attach_domain(struct sched_domain * sd,struct root_domain * rd,int cpu)741 cpu_attach_domain(struct sched_domain *sd, struct root_domain *rd, int cpu)
742 {
743 struct rq *rq = cpu_rq(cpu);
744 struct sched_domain *tmp;
745
746 /* Remove the sched domains which do not contribute to scheduling. */
747 for (tmp = sd; tmp; ) {
748 struct sched_domain *parent = tmp->parent;
749 if (!parent)
750 break;
751
752 if (sd_parent_degenerate(tmp, parent)) {
753 tmp->parent = parent->parent;
754
755 if (parent->parent) {
756 parent->parent->child = tmp;
757 parent->parent->groups->flags = tmp->flags;
758 }
759
760 /*
761 * Transfer SD_PREFER_SIBLING down in case of a
762 * degenerate parent; the spans match for this
763 * so the property transfers.
764 */
765 if (parent->flags & SD_PREFER_SIBLING)
766 tmp->flags |= SD_PREFER_SIBLING;
767 destroy_sched_domain(parent);
768 } else
769 tmp = tmp->parent;
770 }
771
772 if (sd && sd_degenerate(sd)) {
773 tmp = sd;
774 sd = sd->parent;
775 destroy_sched_domain(tmp);
776 if (sd) {
777 struct sched_group *sg = sd->groups;
778
779 /*
780 * sched groups hold the flags of the child sched
781 * domain for convenience. Clear such flags since
782 * the child is being destroyed.
783 */
784 do {
785 sg->flags = 0;
786 } while (sg != sd->groups);
787
788 sd->child = NULL;
789 }
790 }
791
792 sched_domain_debug(sd, cpu);
793
794 rq_attach_root(rq, rd);
795 tmp = rq->sd;
796 rcu_assign_pointer(rq->sd, sd);
797 dirty_sched_domain_sysctl(cpu);
798 destroy_sched_domains(tmp);
799
800 update_top_cache_domain(cpu);
801 }
802
803 struct s_data {
804 struct sched_domain * __percpu *sd;
805 struct root_domain *rd;
806 };
807
808 enum s_alloc {
809 sa_rootdomain,
810 sa_sd,
811 sa_sd_storage,
812 sa_none,
813 };
814
815 /*
816 * Return the canonical balance CPU for this group, this is the first CPU
817 * of this group that's also in the balance mask.
818 *
819 * The balance mask are all those CPUs that could actually end up at this
820 * group. See build_balance_mask().
821 *
822 * Also see should_we_balance().
823 */
group_balance_cpu(struct sched_group * sg)824 int group_balance_cpu(struct sched_group *sg)
825 {
826 return cpumask_first(group_balance_mask(sg));
827 }
828
829
830 /*
831 * NUMA topology (first read the regular topology blurb below)
832 *
833 * Given a node-distance table, for example:
834 *
835 * node 0 1 2 3
836 * 0: 10 20 30 20
837 * 1: 20 10 20 30
838 * 2: 30 20 10 20
839 * 3: 20 30 20 10
840 *
841 * which represents a 4 node ring topology like:
842 *
843 * 0 ----- 1
844 * | |
845 * | |
846 * | |
847 * 3 ----- 2
848 *
849 * We want to construct domains and groups to represent this. The way we go
850 * about doing this is to build the domains on 'hops'. For each NUMA level we
851 * construct the mask of all nodes reachable in @level hops.
852 *
853 * For the above NUMA topology that gives 3 levels:
854 *
855 * NUMA-2 0-3 0-3 0-3 0-3
856 * groups: {0-1,3},{1-3} {0-2},{0,2-3} {1-3},{0-1,3} {0,2-3},{0-2}
857 *
858 * NUMA-1 0-1,3 0-2 1-3 0,2-3
859 * groups: {0},{1},{3} {0},{1},{2} {1},{2},{3} {0},{2},{3}
860 *
861 * NUMA-0 0 1 2 3
862 *
863 *
864 * As can be seen; things don't nicely line up as with the regular topology.
865 * When we iterate a domain in child domain chunks some nodes can be
866 * represented multiple times -- hence the "overlap" naming for this part of
867 * the topology.
868 *
869 * In order to minimize this overlap, we only build enough groups to cover the
870 * domain. For instance Node-0 NUMA-2 would only get groups: 0-1,3 and 1-3.
871 *
872 * Because:
873 *
874 * - the first group of each domain is its child domain; this
875 * gets us the first 0-1,3
876 * - the only uncovered node is 2, who's child domain is 1-3.
877 *
878 * However, because of the overlap, computing a unique CPU for each group is
879 * more complicated. Consider for instance the groups of NODE-1 NUMA-2, both
880 * groups include the CPUs of Node-0, while those CPUs would not in fact ever
881 * end up at those groups (they would end up in group: 0-1,3).
882 *
883 * To correct this we have to introduce the group balance mask. This mask
884 * will contain those CPUs in the group that can reach this group given the
885 * (child) domain tree.
886 *
887 * With this we can once again compute balance_cpu and sched_group_capacity
888 * relations.
889 *
890 * XXX include words on how balance_cpu is unique and therefore can be
891 * used for sched_group_capacity links.
892 *
893 *
894 * Another 'interesting' topology is:
895 *
896 * node 0 1 2 3
897 * 0: 10 20 20 30
898 * 1: 20 10 20 20
899 * 2: 20 20 10 20
900 * 3: 30 20 20 10
901 *
902 * Which looks a little like:
903 *
904 * 0 ----- 1
905 * | / |
906 * | / |
907 * | / |
908 * 2 ----- 3
909 *
910 * This topology is asymmetric, nodes 1,2 are fully connected, but nodes 0,3
911 * are not.
912 *
913 * This leads to a few particularly weird cases where the sched_domain's are
914 * not of the same number for each CPU. Consider:
915 *
916 * NUMA-2 0-3 0-3
917 * groups: {0-2},{1-3} {1-3},{0-2}
918 *
919 * NUMA-1 0-2 0-3 0-3 1-3
920 *
921 * NUMA-0 0 1 2 3
922 *
923 */
924
925
926 /*
927 * Build the balance mask; it contains only those CPUs that can arrive at this
928 * group and should be considered to continue balancing.
929 *
930 * We do this during the group creation pass, therefore the group information
931 * isn't complete yet, however since each group represents a (child) domain we
932 * can fully construct this using the sched_domain bits (which are already
933 * complete).
934 */
935 static void
build_balance_mask(struct sched_domain * sd,struct sched_group * sg,struct cpumask * mask)936 build_balance_mask(struct sched_domain *sd, struct sched_group *sg, struct cpumask *mask)
937 {
938 const struct cpumask *sg_span = sched_group_span(sg);
939 struct sd_data *sdd = sd->private;
940 struct sched_domain *sibling;
941 int i;
942
943 cpumask_clear(mask);
944
945 for_each_cpu(i, sg_span) {
946 sibling = *per_cpu_ptr(sdd->sd, i);
947
948 /*
949 * Can happen in the asymmetric case, where these siblings are
950 * unused. The mask will not be empty because those CPUs that
951 * do have the top domain _should_ span the domain.
952 */
953 if (!sibling->child)
954 continue;
955
956 /* If we would not end up here, we can't continue from here */
957 if (!cpumask_equal(sg_span, sched_domain_span(sibling->child)))
958 continue;
959
960 cpumask_set_cpu(i, mask);
961 }
962
963 /* We must not have empty masks here */
964 WARN_ON_ONCE(cpumask_empty(mask));
965 }
966
967 /*
968 * XXX: This creates per-node group entries; since the load-balancer will
969 * immediately access remote memory to construct this group's load-balance
970 * statistics having the groups node local is of dubious benefit.
971 */
972 static struct sched_group *
build_group_from_child_sched_domain(struct sched_domain * sd,int cpu)973 build_group_from_child_sched_domain(struct sched_domain *sd, int cpu)
974 {
975 struct sched_group *sg;
976 struct cpumask *sg_span;
977
978 sg = kzalloc_node(sizeof(struct sched_group) + cpumask_size(),
979 GFP_KERNEL, cpu_to_node(cpu));
980
981 if (!sg)
982 return NULL;
983
984 sg_span = sched_group_span(sg);
985 if (sd->child) {
986 cpumask_copy(sg_span, sched_domain_span(sd->child));
987 sg->flags = sd->child->flags;
988 } else {
989 cpumask_copy(sg_span, sched_domain_span(sd));
990 }
991
992 atomic_inc(&sg->ref);
993 return sg;
994 }
995
init_overlap_sched_group(struct sched_domain * sd,struct sched_group * sg)996 static void init_overlap_sched_group(struct sched_domain *sd,
997 struct sched_group *sg)
998 {
999 struct cpumask *mask = sched_domains_tmpmask2;
1000 struct sd_data *sdd = sd->private;
1001 struct cpumask *sg_span;
1002 int cpu;
1003
1004 build_balance_mask(sd, sg, mask);
1005 cpu = cpumask_first(mask);
1006
1007 sg->sgc = *per_cpu_ptr(sdd->sgc, cpu);
1008 if (atomic_inc_return(&sg->sgc->ref) == 1)
1009 cpumask_copy(group_balance_mask(sg), mask);
1010 else
1011 WARN_ON_ONCE(!cpumask_equal(group_balance_mask(sg), mask));
1012
1013 /*
1014 * Initialize sgc->capacity such that even if we mess up the
1015 * domains and no possible iteration will get us here, we won't
1016 * die on a /0 trap.
1017 */
1018 sg_span = sched_group_span(sg);
1019 sg->sgc->capacity = SCHED_CAPACITY_SCALE * cpumask_weight(sg_span);
1020 sg->sgc->min_capacity = SCHED_CAPACITY_SCALE;
1021 sg->sgc->max_capacity = SCHED_CAPACITY_SCALE;
1022 }
1023
1024 static struct sched_domain *
find_descended_sibling(struct sched_domain * sd,struct sched_domain * sibling)1025 find_descended_sibling(struct sched_domain *sd, struct sched_domain *sibling)
1026 {
1027 /*
1028 * The proper descendant would be the one whose child won't span out
1029 * of sd
1030 */
1031 while (sibling->child &&
1032 !cpumask_subset(sched_domain_span(sibling->child),
1033 sched_domain_span(sd)))
1034 sibling = sibling->child;
1035
1036 /*
1037 * As we are referencing sgc across different topology level, we need
1038 * to go down to skip those sched_domains which don't contribute to
1039 * scheduling because they will be degenerated in cpu_attach_domain
1040 */
1041 while (sibling->child &&
1042 cpumask_equal(sched_domain_span(sibling->child),
1043 sched_domain_span(sibling)))
1044 sibling = sibling->child;
1045
1046 return sibling;
1047 }
1048
1049 static int
build_overlap_sched_groups(struct sched_domain * sd,int cpu)1050 build_overlap_sched_groups(struct sched_domain *sd, int cpu)
1051 {
1052 struct sched_group *first = NULL, *last = NULL, *sg;
1053 const struct cpumask *span = sched_domain_span(sd);
1054 struct cpumask *covered = sched_domains_tmpmask;
1055 struct sd_data *sdd = sd->private;
1056 struct sched_domain *sibling;
1057 int i;
1058
1059 cpumask_clear(covered);
1060
1061 for_each_cpu_wrap(i, span, cpu) {
1062 struct cpumask *sg_span;
1063
1064 if (cpumask_test_cpu(i, covered))
1065 continue;
1066
1067 sibling = *per_cpu_ptr(sdd->sd, i);
1068
1069 /*
1070 * Asymmetric node setups can result in situations where the
1071 * domain tree is of unequal depth, make sure to skip domains
1072 * that already cover the entire range.
1073 *
1074 * In that case build_sched_domains() will have terminated the
1075 * iteration early and our sibling sd spans will be empty.
1076 * Domains should always include the CPU they're built on, so
1077 * check that.
1078 */
1079 if (!cpumask_test_cpu(i, sched_domain_span(sibling)))
1080 continue;
1081
1082 /*
1083 * Usually we build sched_group by sibling's child sched_domain
1084 * But for machines whose NUMA diameter are 3 or above, we move
1085 * to build sched_group by sibling's proper descendant's child
1086 * domain because sibling's child sched_domain will span out of
1087 * the sched_domain being built as below.
1088 *
1089 * Smallest diameter=3 topology is:
1090 *
1091 * node 0 1 2 3
1092 * 0: 10 20 30 40
1093 * 1: 20 10 20 30
1094 * 2: 30 20 10 20
1095 * 3: 40 30 20 10
1096 *
1097 * 0 --- 1 --- 2 --- 3
1098 *
1099 * NUMA-3 0-3 N/A N/A 0-3
1100 * groups: {0-2},{1-3} {1-3},{0-2}
1101 *
1102 * NUMA-2 0-2 0-3 0-3 1-3
1103 * groups: {0-1},{1-3} {0-2},{2-3} {1-3},{0-1} {2-3},{0-2}
1104 *
1105 * NUMA-1 0-1 0-2 1-3 2-3
1106 * groups: {0},{1} {1},{2},{0} {2},{3},{1} {3},{2}
1107 *
1108 * NUMA-0 0 1 2 3
1109 *
1110 * The NUMA-2 groups for nodes 0 and 3 are obviously buggered, as the
1111 * group span isn't a subset of the domain span.
1112 */
1113 if (sibling->child &&
1114 !cpumask_subset(sched_domain_span(sibling->child), span))
1115 sibling = find_descended_sibling(sd, sibling);
1116
1117 sg = build_group_from_child_sched_domain(sibling, cpu);
1118 if (!sg)
1119 goto fail;
1120
1121 sg_span = sched_group_span(sg);
1122 cpumask_or(covered, covered, sg_span);
1123
1124 init_overlap_sched_group(sibling, sg);
1125
1126 if (!first)
1127 first = sg;
1128 if (last)
1129 last->next = sg;
1130 last = sg;
1131 last->next = first;
1132 }
1133 sd->groups = first;
1134
1135 return 0;
1136
1137 fail:
1138 free_sched_groups(first, 0);
1139
1140 return -ENOMEM;
1141 }
1142
1143
1144 /*
1145 * Package topology (also see the load-balance blurb in fair.c)
1146 *
1147 * The scheduler builds a tree structure to represent a number of important
1148 * topology features. By default (default_topology[]) these include:
1149 *
1150 * - Simultaneous multithreading (SMT)
1151 * - Multi-Core Cache (MC)
1152 * - Package (PKG)
1153 *
1154 * Where the last one more or less denotes everything up to a NUMA node.
1155 *
1156 * The tree consists of 3 primary data structures:
1157 *
1158 * sched_domain -> sched_group -> sched_group_capacity
1159 * ^ ^ ^ ^
1160 * `-' `-'
1161 *
1162 * The sched_domains are per-CPU and have a two way link (parent & child) and
1163 * denote the ever growing mask of CPUs belonging to that level of topology.
1164 *
1165 * Each sched_domain has a circular (double) linked list of sched_group's, each
1166 * denoting the domains of the level below (or individual CPUs in case of the
1167 * first domain level). The sched_group linked by a sched_domain includes the
1168 * CPU of that sched_domain [*].
1169 *
1170 * Take for instance a 2 threaded, 2 core, 2 cache cluster part:
1171 *
1172 * CPU 0 1 2 3 4 5 6 7
1173 *
1174 * PKG [ ]
1175 * MC [ ] [ ]
1176 * SMT [ ] [ ] [ ] [ ]
1177 *
1178 * - or -
1179 *
1180 * PKG 0-7 0-7 0-7 0-7 0-7 0-7 0-7 0-7
1181 * MC 0-3 0-3 0-3 0-3 4-7 4-7 4-7 4-7
1182 * SMT 0-1 0-1 2-3 2-3 4-5 4-5 6-7 6-7
1183 *
1184 * CPU 0 1 2 3 4 5 6 7
1185 *
1186 * One way to think about it is: sched_domain moves you up and down among these
1187 * topology levels, while sched_group moves you sideways through it, at child
1188 * domain granularity.
1189 *
1190 * sched_group_capacity ensures each unique sched_group has shared storage.
1191 *
1192 * There are two related construction problems, both require a CPU that
1193 * uniquely identify each group (for a given domain):
1194 *
1195 * - The first is the balance_cpu (see should_we_balance() and the
1196 * load-balance blurb in fair.c); for each group we only want 1 CPU to
1197 * continue balancing at a higher domain.
1198 *
1199 * - The second is the sched_group_capacity; we want all identical groups
1200 * to share a single sched_group_capacity.
1201 *
1202 * Since these topologies are exclusive by construction. That is, its
1203 * impossible for an SMT thread to belong to multiple cores, and cores to
1204 * be part of multiple caches. There is a very clear and unique location
1205 * for each CPU in the hierarchy.
1206 *
1207 * Therefore computing a unique CPU for each group is trivial (the iteration
1208 * mask is redundant and set all 1s; all CPUs in a group will end up at _that_
1209 * group), we can simply pick the first CPU in each group.
1210 *
1211 *
1212 * [*] in other words, the first group of each domain is its child domain.
1213 */
1214
get_group(int cpu,struct sd_data * sdd)1215 static struct sched_group *get_group(int cpu, struct sd_data *sdd)
1216 {
1217 struct sched_domain *sd = *per_cpu_ptr(sdd->sd, cpu);
1218 struct sched_domain *child = sd->child;
1219 struct sched_group *sg;
1220 bool already_visited;
1221
1222 if (child)
1223 cpu = cpumask_first(sched_domain_span(child));
1224
1225 sg = *per_cpu_ptr(sdd->sg, cpu);
1226 sg->sgc = *per_cpu_ptr(sdd->sgc, cpu);
1227
1228 /* Increase refcounts for claim_allocations: */
1229 already_visited = atomic_inc_return(&sg->ref) > 1;
1230 /* sgc visits should follow a similar trend as sg */
1231 WARN_ON(already_visited != (atomic_inc_return(&sg->sgc->ref) > 1));
1232
1233 /* If we have already visited that group, it's already initialized. */
1234 if (already_visited)
1235 return sg;
1236
1237 if (child) {
1238 cpumask_copy(sched_group_span(sg), sched_domain_span(child));
1239 cpumask_copy(group_balance_mask(sg), sched_group_span(sg));
1240 sg->flags = child->flags;
1241 } else {
1242 cpumask_set_cpu(cpu, sched_group_span(sg));
1243 cpumask_set_cpu(cpu, group_balance_mask(sg));
1244 }
1245
1246 sg->sgc->capacity = SCHED_CAPACITY_SCALE * cpumask_weight(sched_group_span(sg));
1247 sg->sgc->min_capacity = SCHED_CAPACITY_SCALE;
1248 sg->sgc->max_capacity = SCHED_CAPACITY_SCALE;
1249
1250 return sg;
1251 }
1252
1253 /*
1254 * build_sched_groups will build a circular linked list of the groups
1255 * covered by the given span, will set each group's ->cpumask correctly,
1256 * and will initialize their ->sgc.
1257 *
1258 * Assumes the sched_domain tree is fully constructed
1259 */
1260 static int
build_sched_groups(struct sched_domain * sd,int cpu)1261 build_sched_groups(struct sched_domain *sd, int cpu)
1262 {
1263 struct sched_group *first = NULL, *last = NULL;
1264 struct sd_data *sdd = sd->private;
1265 const struct cpumask *span = sched_domain_span(sd);
1266 struct cpumask *covered;
1267 int i;
1268
1269 lockdep_assert_held(&sched_domains_mutex);
1270 covered = sched_domains_tmpmask;
1271
1272 cpumask_clear(covered);
1273
1274 for_each_cpu_wrap(i, span, cpu) {
1275 struct sched_group *sg;
1276
1277 if (cpumask_test_cpu(i, covered))
1278 continue;
1279
1280 sg = get_group(i, sdd);
1281
1282 cpumask_or(covered, covered, sched_group_span(sg));
1283
1284 if (!first)
1285 first = sg;
1286 if (last)
1287 last->next = sg;
1288 last = sg;
1289 }
1290 last->next = first;
1291 sd->groups = first;
1292
1293 return 0;
1294 }
1295
1296 /*
1297 * Initialize sched groups cpu_capacity.
1298 *
1299 * cpu_capacity indicates the capacity of sched group, which is used while
1300 * distributing the load between different sched groups in a sched domain.
1301 * Typically cpu_capacity for all the groups in a sched domain will be same
1302 * unless there are asymmetries in the topology. If there are asymmetries,
1303 * group having more cpu_capacity will pickup more load compared to the
1304 * group having less cpu_capacity.
1305 */
init_sched_groups_capacity(int cpu,struct sched_domain * sd)1306 static void init_sched_groups_capacity(int cpu, struct sched_domain *sd)
1307 {
1308 struct sched_group *sg = sd->groups;
1309 struct cpumask *mask = sched_domains_tmpmask2;
1310
1311 WARN_ON(!sg);
1312
1313 do {
1314 int cpu, cores = 0, max_cpu = -1;
1315
1316 sg->group_weight = cpumask_weight(sched_group_span(sg));
1317
1318 cpumask_copy(mask, sched_group_span(sg));
1319 for_each_cpu(cpu, mask) {
1320 cores++;
1321 #ifdef CONFIG_SCHED_SMT
1322 cpumask_andnot(mask, mask, cpu_smt_mask(cpu));
1323 #endif
1324 }
1325 sg->cores = cores;
1326
1327 if (!(sd->flags & SD_ASYM_PACKING))
1328 goto next;
1329
1330 for_each_cpu(cpu, sched_group_span(sg)) {
1331 if (max_cpu < 0)
1332 max_cpu = cpu;
1333 else if (sched_asym_prefer(cpu, max_cpu))
1334 max_cpu = cpu;
1335 }
1336 sg->asym_prefer_cpu = max_cpu;
1337
1338 next:
1339 sg = sg->next;
1340 } while (sg != sd->groups);
1341
1342 if (cpu != group_balance_cpu(sg))
1343 return;
1344
1345 update_group_capacity(sd, cpu);
1346 }
1347
1348 /*
1349 * Set of available CPUs grouped by their corresponding capacities
1350 * Each list entry contains a CPU mask reflecting CPUs that share the same
1351 * capacity.
1352 * The lifespan of data is unlimited.
1353 */
1354 LIST_HEAD(asym_cap_list);
1355
1356 /*
1357 * Verify whether there is any CPU capacity asymmetry in a given sched domain.
1358 * Provides sd_flags reflecting the asymmetry scope.
1359 */
1360 static inline int
asym_cpu_capacity_classify(const struct cpumask * sd_span,const struct cpumask * cpu_map)1361 asym_cpu_capacity_classify(const struct cpumask *sd_span,
1362 const struct cpumask *cpu_map)
1363 {
1364 struct asym_cap_data *entry;
1365 int count = 0, miss = 0;
1366
1367 /*
1368 * Count how many unique CPU capacities this domain spans across
1369 * (compare sched_domain CPUs mask with ones representing available
1370 * CPUs capacities). Take into account CPUs that might be offline:
1371 * skip those.
1372 */
1373 list_for_each_entry(entry, &asym_cap_list, link) {
1374 if (cpumask_intersects(sd_span, cpu_capacity_span(entry)))
1375 ++count;
1376 else if (cpumask_intersects(cpu_map, cpu_capacity_span(entry)))
1377 ++miss;
1378 }
1379
1380 WARN_ON_ONCE(!count && !list_empty(&asym_cap_list));
1381
1382 /* No asymmetry detected */
1383 if (count < 2)
1384 return 0;
1385 /* Some of the available CPU capacity values have not been detected */
1386 if (miss)
1387 return SD_ASYM_CPUCAPACITY;
1388
1389 /* Full asymmetry */
1390 return SD_ASYM_CPUCAPACITY | SD_ASYM_CPUCAPACITY_FULL;
1391
1392 }
1393
free_asym_cap_entry(struct rcu_head * head)1394 static void free_asym_cap_entry(struct rcu_head *head)
1395 {
1396 struct asym_cap_data *entry = container_of(head, struct asym_cap_data, rcu);
1397 kfree(entry);
1398 }
1399
asym_cpu_capacity_update_data(int cpu)1400 static inline void asym_cpu_capacity_update_data(int cpu)
1401 {
1402 unsigned long capacity = arch_scale_cpu_capacity(cpu);
1403 struct asym_cap_data *insert_entry = NULL;
1404 struct asym_cap_data *entry;
1405
1406 /*
1407 * Search if capacity already exits. If not, track which the entry
1408 * where we should insert to keep the list ordered descending.
1409 */
1410 list_for_each_entry(entry, &asym_cap_list, link) {
1411 if (capacity == entry->capacity)
1412 goto done;
1413 else if (!insert_entry && capacity > entry->capacity)
1414 insert_entry = list_prev_entry(entry, link);
1415 }
1416
1417 entry = kzalloc(sizeof(*entry) + cpumask_size(), GFP_KERNEL);
1418 if (WARN_ONCE(!entry, "Failed to allocate memory for asymmetry data\n"))
1419 return;
1420 entry->capacity = capacity;
1421
1422 /* If NULL then the new capacity is the smallest, add last. */
1423 if (!insert_entry)
1424 list_add_tail_rcu(&entry->link, &asym_cap_list);
1425 else
1426 list_add_rcu(&entry->link, &insert_entry->link);
1427 done:
1428 __cpumask_set_cpu(cpu, cpu_capacity_span(entry));
1429 }
1430
1431 /*
1432 * Build-up/update list of CPUs grouped by their capacities
1433 * An update requires explicit request to rebuild sched domains
1434 * with state indicating CPU topology changes.
1435 */
asym_cpu_capacity_scan(void)1436 static void asym_cpu_capacity_scan(void)
1437 {
1438 struct asym_cap_data *entry, *next;
1439 int cpu;
1440
1441 list_for_each_entry(entry, &asym_cap_list, link)
1442 cpumask_clear(cpu_capacity_span(entry));
1443
1444 for_each_cpu_and(cpu, cpu_possible_mask, housekeeping_cpumask(HK_TYPE_DOMAIN))
1445 asym_cpu_capacity_update_data(cpu);
1446
1447 list_for_each_entry_safe(entry, next, &asym_cap_list, link) {
1448 if (cpumask_empty(cpu_capacity_span(entry))) {
1449 list_del_rcu(&entry->link);
1450 call_rcu(&entry->rcu, free_asym_cap_entry);
1451 }
1452 }
1453
1454 /*
1455 * Only one capacity value has been detected i.e. this system is symmetric.
1456 * No need to keep this data around.
1457 */
1458 if (list_is_singular(&asym_cap_list)) {
1459 entry = list_first_entry(&asym_cap_list, typeof(*entry), link);
1460 list_del_rcu(&entry->link);
1461 call_rcu(&entry->rcu, free_asym_cap_entry);
1462 }
1463 }
1464
1465 /*
1466 * Initializers for schedule domains
1467 * Non-inlined to reduce accumulated stack pressure in build_sched_domains()
1468 */
1469
1470 static int default_relax_domain_level = -1;
1471 int sched_domain_level_max;
1472
setup_relax_domain_level(char * str)1473 static int __init setup_relax_domain_level(char *str)
1474 {
1475 if (kstrtoint(str, 0, &default_relax_domain_level))
1476 pr_warn("Unable to set relax_domain_level\n");
1477
1478 return 1;
1479 }
1480 __setup("relax_domain_level=", setup_relax_domain_level);
1481
set_domain_attribute(struct sched_domain * sd,struct sched_domain_attr * attr)1482 static void set_domain_attribute(struct sched_domain *sd,
1483 struct sched_domain_attr *attr)
1484 {
1485 int request;
1486
1487 if (!attr || attr->relax_domain_level < 0) {
1488 if (default_relax_domain_level < 0)
1489 return;
1490 request = default_relax_domain_level;
1491 } else
1492 request = attr->relax_domain_level;
1493
1494 if (sd->level >= request) {
1495 /* Turn off idle balance on this domain: */
1496 sd->flags &= ~(SD_BALANCE_WAKE|SD_BALANCE_NEWIDLE);
1497 }
1498 }
1499
1500 static void __sdt_free(const struct cpumask *cpu_map);
1501 static int __sdt_alloc(const struct cpumask *cpu_map);
1502
__free_domain_allocs(struct s_data * d,enum s_alloc what,const struct cpumask * cpu_map)1503 static void __free_domain_allocs(struct s_data *d, enum s_alloc what,
1504 const struct cpumask *cpu_map)
1505 {
1506 switch (what) {
1507 case sa_rootdomain:
1508 if (!atomic_read(&d->rd->refcount))
1509 free_rootdomain(&d->rd->rcu);
1510 fallthrough;
1511 case sa_sd:
1512 free_percpu(d->sd);
1513 fallthrough;
1514 case sa_sd_storage:
1515 __sdt_free(cpu_map);
1516 fallthrough;
1517 case sa_none:
1518 break;
1519 }
1520 }
1521
1522 static enum s_alloc
__visit_domain_allocation_hell(struct s_data * d,const struct cpumask * cpu_map)1523 __visit_domain_allocation_hell(struct s_data *d, const struct cpumask *cpu_map)
1524 {
1525 memset(d, 0, sizeof(*d));
1526
1527 if (__sdt_alloc(cpu_map))
1528 return sa_sd_storage;
1529 d->sd = alloc_percpu(struct sched_domain *);
1530 if (!d->sd)
1531 return sa_sd_storage;
1532 d->rd = alloc_rootdomain();
1533 if (!d->rd)
1534 return sa_sd;
1535
1536 return sa_rootdomain;
1537 }
1538
1539 /*
1540 * NULL the sd_data elements we've used to build the sched_domain and
1541 * sched_group structure so that the subsequent __free_domain_allocs()
1542 * will not free the data we're using.
1543 */
claim_allocations(int cpu,struct sched_domain * sd)1544 static void claim_allocations(int cpu, struct sched_domain *sd)
1545 {
1546 struct sd_data *sdd = sd->private;
1547
1548 WARN_ON_ONCE(*per_cpu_ptr(sdd->sd, cpu) != sd);
1549 *per_cpu_ptr(sdd->sd, cpu) = NULL;
1550
1551 if (atomic_read(&(*per_cpu_ptr(sdd->sds, cpu))->ref))
1552 *per_cpu_ptr(sdd->sds, cpu) = NULL;
1553
1554 if (atomic_read(&(*per_cpu_ptr(sdd->sg, cpu))->ref))
1555 *per_cpu_ptr(sdd->sg, cpu) = NULL;
1556
1557 if (atomic_read(&(*per_cpu_ptr(sdd->sgc, cpu))->ref))
1558 *per_cpu_ptr(sdd->sgc, cpu) = NULL;
1559 }
1560
1561 #ifdef CONFIG_NUMA
1562 enum numa_topology_type sched_numa_topology_type;
1563
1564 static int sched_domains_numa_levels;
1565 static int sched_domains_curr_level;
1566
1567 int sched_max_numa_distance;
1568 static int *sched_domains_numa_distance;
1569 static struct cpumask ***sched_domains_numa_masks;
1570 #endif
1571
1572 /*
1573 * SD_flags allowed in topology descriptions.
1574 *
1575 * These flags are purely descriptive of the topology and do not prescribe
1576 * behaviour. Behaviour is artificial and mapped in the below sd_init()
1577 * function. For details, see include/linux/sched/sd_flags.h.
1578 *
1579 * SD_SHARE_CPUCAPACITY
1580 * SD_SHARE_LLC
1581 * SD_CLUSTER
1582 * SD_NUMA
1583 *
1584 * Odd one out, which beside describing the topology has a quirk also
1585 * prescribes the desired behaviour that goes along with it:
1586 *
1587 * SD_ASYM_PACKING - describes SMT quirks
1588 */
1589 #define TOPOLOGY_SD_FLAGS \
1590 (SD_SHARE_CPUCAPACITY | \
1591 SD_CLUSTER | \
1592 SD_SHARE_LLC | \
1593 SD_NUMA | \
1594 SD_ASYM_PACKING)
1595
1596 static struct sched_domain *
sd_init(struct sched_domain_topology_level * tl,const struct cpumask * cpu_map,struct sched_domain * child,int cpu)1597 sd_init(struct sched_domain_topology_level *tl,
1598 const struct cpumask *cpu_map,
1599 struct sched_domain *child, int cpu)
1600 {
1601 struct sd_data *sdd = &tl->data;
1602 struct sched_domain *sd = *per_cpu_ptr(sdd->sd, cpu);
1603 int sd_id, sd_weight, sd_flags = 0;
1604 struct cpumask *sd_span;
1605
1606 #ifdef CONFIG_NUMA
1607 /*
1608 * Ugly hack to pass state to sd_numa_mask()...
1609 */
1610 sched_domains_curr_level = tl->numa_level;
1611 #endif
1612
1613 sd_weight = cpumask_weight(tl->mask(cpu));
1614
1615 if (tl->sd_flags)
1616 sd_flags = (*tl->sd_flags)();
1617 if (WARN_ONCE(sd_flags & ~TOPOLOGY_SD_FLAGS,
1618 "wrong sd_flags in topology description\n"))
1619 sd_flags &= TOPOLOGY_SD_FLAGS;
1620
1621 *sd = (struct sched_domain){
1622 .min_interval = sd_weight,
1623 .max_interval = 2*sd_weight,
1624 .busy_factor = 16,
1625 .imbalance_pct = 117,
1626
1627 .cache_nice_tries = 0,
1628
1629 .flags = 1*SD_BALANCE_NEWIDLE
1630 | 1*SD_BALANCE_EXEC
1631 | 1*SD_BALANCE_FORK
1632 | 0*SD_BALANCE_WAKE
1633 | 1*SD_WAKE_AFFINE
1634 | 0*SD_SHARE_CPUCAPACITY
1635 | 0*SD_SHARE_LLC
1636 | 0*SD_SERIALIZE
1637 | 1*SD_PREFER_SIBLING
1638 | 0*SD_NUMA
1639 | sd_flags
1640 ,
1641
1642 .last_balance = jiffies,
1643 .balance_interval = sd_weight,
1644 .max_newidle_lb_cost = 0,
1645 .last_decay_max_lb_cost = jiffies,
1646 .child = child,
1647 #ifdef CONFIG_SCHED_DEBUG
1648 .name = tl->name,
1649 #endif
1650 };
1651
1652 sd_span = sched_domain_span(sd);
1653 cpumask_and(sd_span, cpu_map, tl->mask(cpu));
1654 sd_id = cpumask_first(sd_span);
1655
1656 sd->flags |= asym_cpu_capacity_classify(sd_span, cpu_map);
1657
1658 WARN_ONCE((sd->flags & (SD_SHARE_CPUCAPACITY | SD_ASYM_CPUCAPACITY)) ==
1659 (SD_SHARE_CPUCAPACITY | SD_ASYM_CPUCAPACITY),
1660 "CPU capacity asymmetry not supported on SMT\n");
1661
1662 /*
1663 * Convert topological properties into behaviour.
1664 */
1665 /* Don't attempt to spread across CPUs of different capacities. */
1666 if ((sd->flags & SD_ASYM_CPUCAPACITY) && sd->child)
1667 sd->child->flags &= ~SD_PREFER_SIBLING;
1668
1669 if (sd->flags & SD_SHARE_CPUCAPACITY) {
1670 sd->imbalance_pct = 110;
1671
1672 } else if (sd->flags & SD_SHARE_LLC) {
1673 sd->imbalance_pct = 117;
1674 sd->cache_nice_tries = 1;
1675
1676 #ifdef CONFIG_NUMA
1677 } else if (sd->flags & SD_NUMA) {
1678 sd->cache_nice_tries = 2;
1679
1680 sd->flags &= ~SD_PREFER_SIBLING;
1681 sd->flags |= SD_SERIALIZE;
1682 if (sched_domains_numa_distance[tl->numa_level] > node_reclaim_distance) {
1683 sd->flags &= ~(SD_BALANCE_EXEC |
1684 SD_BALANCE_FORK |
1685 SD_WAKE_AFFINE);
1686 }
1687
1688 #endif
1689 } else {
1690 sd->cache_nice_tries = 1;
1691 }
1692
1693 /*
1694 * For all levels sharing cache; connect a sched_domain_shared
1695 * instance.
1696 */
1697 if (sd->flags & SD_SHARE_LLC) {
1698 sd->shared = *per_cpu_ptr(sdd->sds, sd_id);
1699 atomic_inc(&sd->shared->ref);
1700 atomic_set(&sd->shared->nr_busy_cpus, sd_weight);
1701 }
1702
1703 sd->private = sdd;
1704
1705 return sd;
1706 }
1707
1708 /*
1709 * Topology list, bottom-up.
1710 */
1711 static struct sched_domain_topology_level default_topology[] = {
1712 #ifdef CONFIG_SCHED_SMT
1713 { cpu_smt_mask, cpu_smt_flags, SD_INIT_NAME(SMT) },
1714 #endif
1715
1716 #ifdef CONFIG_SCHED_CLUSTER
1717 { cpu_clustergroup_mask, cpu_cluster_flags, SD_INIT_NAME(CLS) },
1718 #endif
1719
1720 #ifdef CONFIG_SCHED_MC
1721 { cpu_coregroup_mask, cpu_core_flags, SD_INIT_NAME(MC) },
1722 #endif
1723 { cpu_cpu_mask, SD_INIT_NAME(PKG) },
1724 { NULL, },
1725 };
1726
1727 static struct sched_domain_topology_level *sched_domain_topology =
1728 default_topology;
1729 static struct sched_domain_topology_level *sched_domain_topology_saved;
1730
1731 #define for_each_sd_topology(tl) \
1732 for (tl = sched_domain_topology; tl->mask; tl++)
1733
set_sched_topology(struct sched_domain_topology_level * tl)1734 void __init set_sched_topology(struct sched_domain_topology_level *tl)
1735 {
1736 if (WARN_ON_ONCE(sched_smp_initialized))
1737 return;
1738
1739 sched_domain_topology = tl;
1740 sched_domain_topology_saved = NULL;
1741 }
1742
1743 #ifdef CONFIG_NUMA
1744
sd_numa_mask(int cpu)1745 static const struct cpumask *sd_numa_mask(int cpu)
1746 {
1747 return sched_domains_numa_masks[sched_domains_curr_level][cpu_to_node(cpu)];
1748 }
1749
sched_numa_warn(const char * str)1750 static void sched_numa_warn(const char *str)
1751 {
1752 static int done = false;
1753 int i,j;
1754
1755 if (done)
1756 return;
1757
1758 done = true;
1759
1760 printk(KERN_WARNING "ERROR: %s\n\n", str);
1761
1762 for (i = 0; i < nr_node_ids; i++) {
1763 printk(KERN_WARNING " ");
1764 for (j = 0; j < nr_node_ids; j++) {
1765 if (!node_state(i, N_CPU) || !node_state(j, N_CPU))
1766 printk(KERN_CONT "(%02d) ", node_distance(i,j));
1767 else
1768 printk(KERN_CONT " %02d ", node_distance(i,j));
1769 }
1770 printk(KERN_CONT "\n");
1771 }
1772 printk(KERN_WARNING "\n");
1773 }
1774
find_numa_distance(int distance)1775 bool find_numa_distance(int distance)
1776 {
1777 bool found = false;
1778 int i, *distances;
1779
1780 if (distance == node_distance(0, 0))
1781 return true;
1782
1783 rcu_read_lock();
1784 distances = rcu_dereference(sched_domains_numa_distance);
1785 if (!distances)
1786 goto unlock;
1787 for (i = 0; i < sched_domains_numa_levels; i++) {
1788 if (distances[i] == distance) {
1789 found = true;
1790 break;
1791 }
1792 }
1793 unlock:
1794 rcu_read_unlock();
1795
1796 return found;
1797 }
1798
1799 #define for_each_cpu_node_but(n, nbut) \
1800 for_each_node_state(n, N_CPU) \
1801 if (n == nbut) \
1802 continue; \
1803 else
1804
1805 /*
1806 * A system can have three types of NUMA topology:
1807 * NUMA_DIRECT: all nodes are directly connected, or not a NUMA system
1808 * NUMA_GLUELESS_MESH: some nodes reachable through intermediary nodes
1809 * NUMA_BACKPLANE: nodes can reach other nodes through a backplane
1810 *
1811 * The difference between a glueless mesh topology and a backplane
1812 * topology lies in whether communication between not directly
1813 * connected nodes goes through intermediary nodes (where programs
1814 * could run), or through backplane controllers. This affects
1815 * placement of programs.
1816 *
1817 * The type of topology can be discerned with the following tests:
1818 * - If the maximum distance between any nodes is 1 hop, the system
1819 * is directly connected.
1820 * - If for two nodes A and B, located N > 1 hops away from each other,
1821 * there is an intermediary node C, which is < N hops away from both
1822 * nodes A and B, the system is a glueless mesh.
1823 */
init_numa_topology_type(int offline_node)1824 static void init_numa_topology_type(int offline_node)
1825 {
1826 int a, b, c, n;
1827
1828 n = sched_max_numa_distance;
1829
1830 if (sched_domains_numa_levels <= 2) {
1831 sched_numa_topology_type = NUMA_DIRECT;
1832 return;
1833 }
1834
1835 for_each_cpu_node_but(a, offline_node) {
1836 for_each_cpu_node_but(b, offline_node) {
1837 /* Find two nodes furthest removed from each other. */
1838 if (node_distance(a, b) < n)
1839 continue;
1840
1841 /* Is there an intermediary node between a and b? */
1842 for_each_cpu_node_but(c, offline_node) {
1843 if (node_distance(a, c) < n &&
1844 node_distance(b, c) < n) {
1845 sched_numa_topology_type =
1846 NUMA_GLUELESS_MESH;
1847 return;
1848 }
1849 }
1850
1851 sched_numa_topology_type = NUMA_BACKPLANE;
1852 return;
1853 }
1854 }
1855
1856 pr_err("Failed to find a NUMA topology type, defaulting to DIRECT\n");
1857 sched_numa_topology_type = NUMA_DIRECT;
1858 }
1859
1860
1861 #define NR_DISTANCE_VALUES (1 << DISTANCE_BITS)
1862
sched_init_numa(int offline_node)1863 void sched_init_numa(int offline_node)
1864 {
1865 struct sched_domain_topology_level *tl;
1866 unsigned long *distance_map;
1867 int nr_levels = 0;
1868 int i, j;
1869 int *distances;
1870 struct cpumask ***masks;
1871
1872 /*
1873 * O(nr_nodes^2) de-duplicating selection sort -- in order to find the
1874 * unique distances in the node_distance() table.
1875 */
1876 distance_map = bitmap_alloc(NR_DISTANCE_VALUES, GFP_KERNEL);
1877 if (!distance_map)
1878 return;
1879
1880 bitmap_zero(distance_map, NR_DISTANCE_VALUES);
1881 for_each_cpu_node_but(i, offline_node) {
1882 for_each_cpu_node_but(j, offline_node) {
1883 int distance = node_distance(i, j);
1884
1885 if (distance < LOCAL_DISTANCE || distance >= NR_DISTANCE_VALUES) {
1886 sched_numa_warn("Invalid distance value range");
1887 bitmap_free(distance_map);
1888 return;
1889 }
1890
1891 bitmap_set(distance_map, distance, 1);
1892 }
1893 }
1894 /*
1895 * We can now figure out how many unique distance values there are and
1896 * allocate memory accordingly.
1897 */
1898 nr_levels = bitmap_weight(distance_map, NR_DISTANCE_VALUES);
1899
1900 distances = kcalloc(nr_levels, sizeof(int), GFP_KERNEL);
1901 if (!distances) {
1902 bitmap_free(distance_map);
1903 return;
1904 }
1905
1906 for (i = 0, j = 0; i < nr_levels; i++, j++) {
1907 j = find_next_bit(distance_map, NR_DISTANCE_VALUES, j);
1908 distances[i] = j;
1909 }
1910 rcu_assign_pointer(sched_domains_numa_distance, distances);
1911
1912 bitmap_free(distance_map);
1913
1914 /*
1915 * 'nr_levels' contains the number of unique distances
1916 *
1917 * The sched_domains_numa_distance[] array includes the actual distance
1918 * numbers.
1919 */
1920
1921 /*
1922 * Here, we should temporarily reset sched_domains_numa_levels to 0.
1923 * If it fails to allocate memory for array sched_domains_numa_masks[][],
1924 * the array will contain less then 'nr_levels' members. This could be
1925 * dangerous when we use it to iterate array sched_domains_numa_masks[][]
1926 * in other functions.
1927 *
1928 * We reset it to 'nr_levels' at the end of this function.
1929 */
1930 sched_domains_numa_levels = 0;
1931
1932 masks = kzalloc(sizeof(void *) * nr_levels, GFP_KERNEL);
1933 if (!masks)
1934 return;
1935
1936 /*
1937 * Now for each level, construct a mask per node which contains all
1938 * CPUs of nodes that are that many hops away from us.
1939 */
1940 for (i = 0; i < nr_levels; i++) {
1941 masks[i] = kzalloc(nr_node_ids * sizeof(void *), GFP_KERNEL);
1942 if (!masks[i])
1943 return;
1944
1945 for_each_cpu_node_but(j, offline_node) {
1946 struct cpumask *mask = kzalloc(cpumask_size(), GFP_KERNEL);
1947 int k;
1948
1949 if (!mask)
1950 return;
1951
1952 masks[i][j] = mask;
1953
1954 for_each_cpu_node_but(k, offline_node) {
1955 if (sched_debug() && (node_distance(j, k) != node_distance(k, j)))
1956 sched_numa_warn("Node-distance not symmetric");
1957
1958 if (node_distance(j, k) > sched_domains_numa_distance[i])
1959 continue;
1960
1961 cpumask_or(mask, mask, cpumask_of_node(k));
1962 }
1963 }
1964 }
1965 rcu_assign_pointer(sched_domains_numa_masks, masks);
1966
1967 /* Compute default topology size */
1968 for (i = 0; sched_domain_topology[i].mask; i++);
1969
1970 tl = kzalloc((i + nr_levels + 1) *
1971 sizeof(struct sched_domain_topology_level), GFP_KERNEL);
1972 if (!tl)
1973 return;
1974
1975 /*
1976 * Copy the default topology bits..
1977 */
1978 for (i = 0; sched_domain_topology[i].mask; i++)
1979 tl[i] = sched_domain_topology[i];
1980
1981 /*
1982 * Add the NUMA identity distance, aka single NODE.
1983 */
1984 tl[i++] = (struct sched_domain_topology_level){
1985 .mask = sd_numa_mask,
1986 .numa_level = 0,
1987 SD_INIT_NAME(NODE)
1988 };
1989
1990 /*
1991 * .. and append 'j' levels of NUMA goodness.
1992 */
1993 for (j = 1; j < nr_levels; i++, j++) {
1994 tl[i] = (struct sched_domain_topology_level){
1995 .mask = sd_numa_mask,
1996 .sd_flags = cpu_numa_flags,
1997 .flags = SDTL_OVERLAP,
1998 .numa_level = j,
1999 SD_INIT_NAME(NUMA)
2000 };
2001 }
2002
2003 sched_domain_topology_saved = sched_domain_topology;
2004 sched_domain_topology = tl;
2005
2006 sched_domains_numa_levels = nr_levels;
2007 WRITE_ONCE(sched_max_numa_distance, sched_domains_numa_distance[nr_levels - 1]);
2008
2009 init_numa_topology_type(offline_node);
2010 }
2011
2012
sched_reset_numa(void)2013 static void sched_reset_numa(void)
2014 {
2015 int nr_levels, *distances;
2016 struct cpumask ***masks;
2017
2018 nr_levels = sched_domains_numa_levels;
2019 sched_domains_numa_levels = 0;
2020 sched_max_numa_distance = 0;
2021 sched_numa_topology_type = NUMA_DIRECT;
2022 distances = sched_domains_numa_distance;
2023 rcu_assign_pointer(sched_domains_numa_distance, NULL);
2024 masks = sched_domains_numa_masks;
2025 rcu_assign_pointer(sched_domains_numa_masks, NULL);
2026 if (distances || masks) {
2027 int i, j;
2028
2029 synchronize_rcu();
2030 kfree(distances);
2031 for (i = 0; i < nr_levels && masks; i++) {
2032 if (!masks[i])
2033 continue;
2034 for_each_node(j)
2035 kfree(masks[i][j]);
2036 kfree(masks[i]);
2037 }
2038 kfree(masks);
2039 }
2040 if (sched_domain_topology_saved) {
2041 kfree(sched_domain_topology);
2042 sched_domain_topology = sched_domain_topology_saved;
2043 sched_domain_topology_saved = NULL;
2044 }
2045 }
2046
2047 /*
2048 * Call with hotplug lock held
2049 */
sched_update_numa(int cpu,bool online)2050 void sched_update_numa(int cpu, bool online)
2051 {
2052 int node;
2053
2054 node = cpu_to_node(cpu);
2055 /*
2056 * Scheduler NUMA topology is updated when the first CPU of a
2057 * node is onlined or the last CPU of a node is offlined.
2058 */
2059 if (cpumask_weight(cpumask_of_node(node)) != 1)
2060 return;
2061
2062 sched_reset_numa();
2063 sched_init_numa(online ? NUMA_NO_NODE : node);
2064 }
2065
sched_domains_numa_masks_set(unsigned int cpu)2066 void sched_domains_numa_masks_set(unsigned int cpu)
2067 {
2068 int node = cpu_to_node(cpu);
2069 int i, j;
2070
2071 for (i = 0; i < sched_domains_numa_levels; i++) {
2072 for (j = 0; j < nr_node_ids; j++) {
2073 if (!node_state(j, N_CPU))
2074 continue;
2075
2076 /* Set ourselves in the remote node's masks */
2077 if (node_distance(j, node) <= sched_domains_numa_distance[i])
2078 cpumask_set_cpu(cpu, sched_domains_numa_masks[i][j]);
2079 }
2080 }
2081 }
2082
sched_domains_numa_masks_clear(unsigned int cpu)2083 void sched_domains_numa_masks_clear(unsigned int cpu)
2084 {
2085 int i, j;
2086
2087 for (i = 0; i < sched_domains_numa_levels; i++) {
2088 for (j = 0; j < nr_node_ids; j++) {
2089 if (sched_domains_numa_masks[i][j])
2090 cpumask_clear_cpu(cpu, sched_domains_numa_masks[i][j]);
2091 }
2092 }
2093 }
2094
2095 /*
2096 * sched_numa_find_closest() - given the NUMA topology, find the cpu
2097 * closest to @cpu from @cpumask.
2098 * cpumask: cpumask to find a cpu from
2099 * cpu: cpu to be close to
2100 *
2101 * returns: cpu, or nr_cpu_ids when nothing found.
2102 */
sched_numa_find_closest(const struct cpumask * cpus,int cpu)2103 int sched_numa_find_closest(const struct cpumask *cpus, int cpu)
2104 {
2105 int i, j = cpu_to_node(cpu), found = nr_cpu_ids;
2106 struct cpumask ***masks;
2107
2108 rcu_read_lock();
2109 masks = rcu_dereference(sched_domains_numa_masks);
2110 if (!masks)
2111 goto unlock;
2112 for (i = 0; i < sched_domains_numa_levels; i++) {
2113 if (!masks[i][j])
2114 break;
2115 cpu = cpumask_any_and(cpus, masks[i][j]);
2116 if (cpu < nr_cpu_ids) {
2117 found = cpu;
2118 break;
2119 }
2120 }
2121 unlock:
2122 rcu_read_unlock();
2123
2124 return found;
2125 }
2126
2127 struct __cmp_key {
2128 const struct cpumask *cpus;
2129 struct cpumask ***masks;
2130 int node;
2131 int cpu;
2132 int w;
2133 };
2134
hop_cmp(const void * a,const void * b)2135 static int hop_cmp(const void *a, const void *b)
2136 {
2137 struct cpumask **prev_hop, **cur_hop = *(struct cpumask ***)b;
2138 struct __cmp_key *k = (struct __cmp_key *)a;
2139
2140 if (cpumask_weight_and(k->cpus, cur_hop[k->node]) <= k->cpu)
2141 return 1;
2142
2143 if (b == k->masks) {
2144 k->w = 0;
2145 return 0;
2146 }
2147
2148 prev_hop = *((struct cpumask ***)b - 1);
2149 k->w = cpumask_weight_and(k->cpus, prev_hop[k->node]);
2150 if (k->w <= k->cpu)
2151 return 0;
2152
2153 return -1;
2154 }
2155
2156 /**
2157 * sched_numa_find_nth_cpu() - given the NUMA topology, find the Nth closest CPU
2158 * from @cpus to @cpu, taking into account distance
2159 * from a given @node.
2160 * @cpus: cpumask to find a cpu from
2161 * @cpu: CPU to start searching
2162 * @node: NUMA node to order CPUs by distance
2163 *
2164 * Return: cpu, or nr_cpu_ids when nothing found.
2165 */
sched_numa_find_nth_cpu(const struct cpumask * cpus,int cpu,int node)2166 int sched_numa_find_nth_cpu(const struct cpumask *cpus, int cpu, int node)
2167 {
2168 struct __cmp_key k = { .cpus = cpus, .cpu = cpu };
2169 struct cpumask ***hop_masks;
2170 int hop, ret = nr_cpu_ids;
2171
2172 if (node == NUMA_NO_NODE)
2173 return cpumask_nth_and(cpu, cpus, cpu_online_mask);
2174
2175 rcu_read_lock();
2176
2177 /* CPU-less node entries are uninitialized in sched_domains_numa_masks */
2178 node = numa_nearest_node(node, N_CPU);
2179 k.node = node;
2180
2181 k.masks = rcu_dereference(sched_domains_numa_masks);
2182 if (!k.masks)
2183 goto unlock;
2184
2185 hop_masks = bsearch(&k, k.masks, sched_domains_numa_levels, sizeof(k.masks[0]), hop_cmp);
2186 if (!hop_masks)
2187 goto unlock;
2188 hop = hop_masks - k.masks;
2189
2190 ret = hop ?
2191 cpumask_nth_and_andnot(cpu - k.w, cpus, k.masks[hop][node], k.masks[hop-1][node]) :
2192 cpumask_nth_and(cpu, cpus, k.masks[0][node]);
2193 unlock:
2194 rcu_read_unlock();
2195 return ret;
2196 }
2197 EXPORT_SYMBOL_GPL(sched_numa_find_nth_cpu);
2198
2199 /**
2200 * sched_numa_hop_mask() - Get the cpumask of CPUs at most @hops hops away from
2201 * @node
2202 * @node: The node to count hops from.
2203 * @hops: Include CPUs up to that many hops away. 0 means local node.
2204 *
2205 * Return: On success, a pointer to a cpumask of CPUs at most @hops away from
2206 * @node, an error value otherwise.
2207 *
2208 * Requires rcu_lock to be held. Returned cpumask is only valid within that
2209 * read-side section, copy it if required beyond that.
2210 *
2211 * Note that not all hops are equal in distance; see sched_init_numa() for how
2212 * distances and masks are handled.
2213 * Also note that this is a reflection of sched_domains_numa_masks, which may change
2214 * during the lifetime of the system (offline nodes are taken out of the masks).
2215 */
sched_numa_hop_mask(unsigned int node,unsigned int hops)2216 const struct cpumask *sched_numa_hop_mask(unsigned int node, unsigned int hops)
2217 {
2218 struct cpumask ***masks;
2219
2220 if (node >= nr_node_ids || hops >= sched_domains_numa_levels)
2221 return ERR_PTR(-EINVAL);
2222
2223 masks = rcu_dereference(sched_domains_numa_masks);
2224 if (!masks)
2225 return ERR_PTR(-EBUSY);
2226
2227 return masks[hops][node];
2228 }
2229 EXPORT_SYMBOL_GPL(sched_numa_hop_mask);
2230
2231 #endif /* CONFIG_NUMA */
2232
__sdt_alloc(const struct cpumask * cpu_map)2233 static int __sdt_alloc(const struct cpumask *cpu_map)
2234 {
2235 struct sched_domain_topology_level *tl;
2236 int j;
2237
2238 for_each_sd_topology(tl) {
2239 struct sd_data *sdd = &tl->data;
2240
2241 sdd->sd = alloc_percpu(struct sched_domain *);
2242 if (!sdd->sd)
2243 return -ENOMEM;
2244
2245 sdd->sds = alloc_percpu(struct sched_domain_shared *);
2246 if (!sdd->sds)
2247 return -ENOMEM;
2248
2249 sdd->sg = alloc_percpu(struct sched_group *);
2250 if (!sdd->sg)
2251 return -ENOMEM;
2252
2253 sdd->sgc = alloc_percpu(struct sched_group_capacity *);
2254 if (!sdd->sgc)
2255 return -ENOMEM;
2256
2257 for_each_cpu(j, cpu_map) {
2258 struct sched_domain *sd;
2259 struct sched_domain_shared *sds;
2260 struct sched_group *sg;
2261 struct sched_group_capacity *sgc;
2262
2263 sd = kzalloc_node(sizeof(struct sched_domain) + cpumask_size(),
2264 GFP_KERNEL, cpu_to_node(j));
2265 if (!sd)
2266 return -ENOMEM;
2267
2268 *per_cpu_ptr(sdd->sd, j) = sd;
2269
2270 sds = kzalloc_node(sizeof(struct sched_domain_shared),
2271 GFP_KERNEL, cpu_to_node(j));
2272 if (!sds)
2273 return -ENOMEM;
2274
2275 *per_cpu_ptr(sdd->sds, j) = sds;
2276
2277 sg = kzalloc_node(sizeof(struct sched_group) + cpumask_size(),
2278 GFP_KERNEL, cpu_to_node(j));
2279 if (!sg)
2280 return -ENOMEM;
2281
2282 sg->next = sg;
2283
2284 *per_cpu_ptr(sdd->sg, j) = sg;
2285
2286 sgc = kzalloc_node(sizeof(struct sched_group_capacity) + cpumask_size(),
2287 GFP_KERNEL, cpu_to_node(j));
2288 if (!sgc)
2289 return -ENOMEM;
2290
2291 #ifdef CONFIG_SCHED_DEBUG
2292 sgc->id = j;
2293 #endif
2294
2295 *per_cpu_ptr(sdd->sgc, j) = sgc;
2296 }
2297 }
2298
2299 return 0;
2300 }
2301
__sdt_free(const struct cpumask * cpu_map)2302 static void __sdt_free(const struct cpumask *cpu_map)
2303 {
2304 struct sched_domain_topology_level *tl;
2305 int j;
2306
2307 for_each_sd_topology(tl) {
2308 struct sd_data *sdd = &tl->data;
2309
2310 for_each_cpu(j, cpu_map) {
2311 struct sched_domain *sd;
2312
2313 if (sdd->sd) {
2314 sd = *per_cpu_ptr(sdd->sd, j);
2315 if (sd && (sd->flags & SD_OVERLAP))
2316 free_sched_groups(sd->groups, 0);
2317 kfree(*per_cpu_ptr(sdd->sd, j));
2318 }
2319
2320 if (sdd->sds)
2321 kfree(*per_cpu_ptr(sdd->sds, j));
2322 if (sdd->sg)
2323 kfree(*per_cpu_ptr(sdd->sg, j));
2324 if (sdd->sgc)
2325 kfree(*per_cpu_ptr(sdd->sgc, j));
2326 }
2327 free_percpu(sdd->sd);
2328 sdd->sd = NULL;
2329 free_percpu(sdd->sds);
2330 sdd->sds = NULL;
2331 free_percpu(sdd->sg);
2332 sdd->sg = NULL;
2333 free_percpu(sdd->sgc);
2334 sdd->sgc = NULL;
2335 }
2336 }
2337
build_sched_domain(struct sched_domain_topology_level * tl,const struct cpumask * cpu_map,struct sched_domain_attr * attr,struct sched_domain * child,int cpu)2338 static struct sched_domain *build_sched_domain(struct sched_domain_topology_level *tl,
2339 const struct cpumask *cpu_map, struct sched_domain_attr *attr,
2340 struct sched_domain *child, int cpu)
2341 {
2342 struct sched_domain *sd = sd_init(tl, cpu_map, child, cpu);
2343
2344 if (child) {
2345 sd->level = child->level + 1;
2346 sched_domain_level_max = max(sched_domain_level_max, sd->level);
2347 child->parent = sd;
2348
2349 if (!cpumask_subset(sched_domain_span(child),
2350 sched_domain_span(sd))) {
2351 pr_err("BUG: arch topology borken\n");
2352 #ifdef CONFIG_SCHED_DEBUG
2353 pr_err(" the %s domain not a subset of the %s domain\n",
2354 child->name, sd->name);
2355 #endif
2356 /* Fixup, ensure @sd has at least @child CPUs. */
2357 cpumask_or(sched_domain_span(sd),
2358 sched_domain_span(sd),
2359 sched_domain_span(child));
2360 }
2361
2362 }
2363 set_domain_attribute(sd, attr);
2364
2365 return sd;
2366 }
2367
2368 /*
2369 * Ensure topology masks are sane, i.e. there are no conflicts (overlaps) for
2370 * any two given CPUs at this (non-NUMA) topology level.
2371 */
topology_span_sane(struct sched_domain_topology_level * tl,const struct cpumask * cpu_map,int cpu)2372 static bool topology_span_sane(struct sched_domain_topology_level *tl,
2373 const struct cpumask *cpu_map, int cpu)
2374 {
2375 int i = cpu + 1;
2376
2377 /* NUMA levels are allowed to overlap */
2378 if (tl->flags & SDTL_OVERLAP)
2379 return true;
2380
2381 /*
2382 * Non-NUMA levels cannot partially overlap - they must be either
2383 * completely equal or completely disjoint. Otherwise we can end up
2384 * breaking the sched_group lists - i.e. a later get_group() pass
2385 * breaks the linking done for an earlier span.
2386 */
2387 for_each_cpu_from(i, cpu_map) {
2388 /*
2389 * We should 'and' all those masks with 'cpu_map' to exactly
2390 * match the topology we're about to build, but that can only
2391 * remove CPUs, which only lessens our ability to detect
2392 * overlaps
2393 */
2394 if (!cpumask_equal(tl->mask(cpu), tl->mask(i)) &&
2395 cpumask_intersects(tl->mask(cpu), tl->mask(i)))
2396 return false;
2397 }
2398
2399 return true;
2400 }
2401
2402 /*
2403 * Build sched domains for a given set of CPUs and attach the sched domains
2404 * to the individual CPUs
2405 */
2406 static int
build_sched_domains(const struct cpumask * cpu_map,struct sched_domain_attr * attr)2407 build_sched_domains(const struct cpumask *cpu_map, struct sched_domain_attr *attr)
2408 {
2409 enum s_alloc alloc_state = sa_none;
2410 struct sched_domain *sd;
2411 struct s_data d;
2412 struct rq *rq = NULL;
2413 int i, ret = -ENOMEM;
2414 bool has_asym = false;
2415 bool has_cluster = false;
2416
2417 if (WARN_ON(cpumask_empty(cpu_map)))
2418 goto error;
2419
2420 alloc_state = __visit_domain_allocation_hell(&d, cpu_map);
2421 if (alloc_state != sa_rootdomain)
2422 goto error;
2423
2424 /* Set up domains for CPUs specified by the cpu_map: */
2425 for_each_cpu(i, cpu_map) {
2426 struct sched_domain_topology_level *tl;
2427
2428 sd = NULL;
2429 for_each_sd_topology(tl) {
2430
2431 if (WARN_ON(!topology_span_sane(tl, cpu_map, i)))
2432 goto error;
2433
2434 sd = build_sched_domain(tl, cpu_map, attr, sd, i);
2435
2436 has_asym |= sd->flags & SD_ASYM_CPUCAPACITY;
2437
2438 if (tl == sched_domain_topology)
2439 *per_cpu_ptr(d.sd, i) = sd;
2440 if (tl->flags & SDTL_OVERLAP)
2441 sd->flags |= SD_OVERLAP;
2442 if (cpumask_equal(cpu_map, sched_domain_span(sd)))
2443 break;
2444 }
2445 }
2446
2447 /* Build the groups for the domains */
2448 for_each_cpu(i, cpu_map) {
2449 for (sd = *per_cpu_ptr(d.sd, i); sd; sd = sd->parent) {
2450 sd->span_weight = cpumask_weight(sched_domain_span(sd));
2451 if (sd->flags & SD_OVERLAP) {
2452 if (build_overlap_sched_groups(sd, i))
2453 goto error;
2454 } else {
2455 if (build_sched_groups(sd, i))
2456 goto error;
2457 }
2458 }
2459 }
2460
2461 /*
2462 * Calculate an allowed NUMA imbalance such that LLCs do not get
2463 * imbalanced.
2464 */
2465 for_each_cpu(i, cpu_map) {
2466 unsigned int imb = 0;
2467 unsigned int imb_span = 1;
2468
2469 for (sd = *per_cpu_ptr(d.sd, i); sd; sd = sd->parent) {
2470 struct sched_domain *child = sd->child;
2471
2472 if (!(sd->flags & SD_SHARE_LLC) && child &&
2473 (child->flags & SD_SHARE_LLC)) {
2474 struct sched_domain __rcu *top_p;
2475 unsigned int nr_llcs;
2476
2477 /*
2478 * For a single LLC per node, allow an
2479 * imbalance up to 12.5% of the node. This is
2480 * arbitrary cutoff based two factors -- SMT and
2481 * memory channels. For SMT-2, the intent is to
2482 * avoid premature sharing of HT resources but
2483 * SMT-4 or SMT-8 *may* benefit from a different
2484 * cutoff. For memory channels, this is a very
2485 * rough estimate of how many channels may be
2486 * active and is based on recent CPUs with
2487 * many cores.
2488 *
2489 * For multiple LLCs, allow an imbalance
2490 * until multiple tasks would share an LLC
2491 * on one node while LLCs on another node
2492 * remain idle. This assumes that there are
2493 * enough logical CPUs per LLC to avoid SMT
2494 * factors and that there is a correlation
2495 * between LLCs and memory channels.
2496 */
2497 nr_llcs = sd->span_weight / child->span_weight;
2498 if (nr_llcs == 1)
2499 imb = sd->span_weight >> 3;
2500 else
2501 imb = nr_llcs;
2502 imb = max(1U, imb);
2503 sd->imb_numa_nr = imb;
2504
2505 /* Set span based on the first NUMA domain. */
2506 top_p = sd->parent;
2507 while (top_p && !(top_p->flags & SD_NUMA)) {
2508 top_p = top_p->parent;
2509 }
2510 imb_span = top_p ? top_p->span_weight : sd->span_weight;
2511 } else {
2512 int factor = max(1U, (sd->span_weight / imb_span));
2513
2514 sd->imb_numa_nr = imb * factor;
2515 }
2516 }
2517 }
2518
2519 /* Calculate CPU capacity for physical packages and nodes */
2520 for (i = nr_cpumask_bits-1; i >= 0; i--) {
2521 if (!cpumask_test_cpu(i, cpu_map))
2522 continue;
2523
2524 for (sd = *per_cpu_ptr(d.sd, i); sd; sd = sd->parent) {
2525 claim_allocations(i, sd);
2526 init_sched_groups_capacity(i, sd);
2527 }
2528 }
2529
2530 /* Attach the domains */
2531 rcu_read_lock();
2532 for_each_cpu(i, cpu_map) {
2533 rq = cpu_rq(i);
2534 sd = *per_cpu_ptr(d.sd, i);
2535
2536 cpu_attach_domain(sd, d.rd, i);
2537
2538 if (lowest_flag_domain(i, SD_CLUSTER))
2539 has_cluster = true;
2540 }
2541 rcu_read_unlock();
2542
2543 if (has_asym)
2544 static_branch_inc_cpuslocked(&sched_asym_cpucapacity);
2545
2546 if (has_cluster)
2547 static_branch_inc_cpuslocked(&sched_cluster_active);
2548
2549 if (rq && sched_debug_verbose)
2550 pr_info("root domain span: %*pbl\n", cpumask_pr_args(cpu_map));
2551 trace_android_vh_build_sched_domains(has_asym);
2552
2553 ret = 0;
2554 error:
2555 __free_domain_allocs(&d, alloc_state, cpu_map);
2556
2557 return ret;
2558 }
2559
2560 /* Current sched domains: */
2561 static cpumask_var_t *doms_cur;
2562
2563 /* Number of sched domains in 'doms_cur': */
2564 static int ndoms_cur;
2565
2566 /* Attributes of custom domains in 'doms_cur' */
2567 static struct sched_domain_attr *dattr_cur;
2568
2569 /*
2570 * Special case: If a kmalloc() of a doms_cur partition (array of
2571 * cpumask) fails, then fallback to a single sched domain,
2572 * as determined by the single cpumask fallback_doms.
2573 */
2574 static cpumask_var_t fallback_doms;
2575
2576 /*
2577 * arch_update_cpu_topology lets virtualized architectures update the
2578 * CPU core maps. It is supposed to return 1 if the topology changed
2579 * or 0 if it stayed the same.
2580 */
arch_update_cpu_topology(void)2581 int __weak arch_update_cpu_topology(void)
2582 {
2583 return 0;
2584 }
2585
alloc_sched_domains(unsigned int ndoms)2586 cpumask_var_t *alloc_sched_domains(unsigned int ndoms)
2587 {
2588 int i;
2589 cpumask_var_t *doms;
2590
2591 doms = kmalloc_array(ndoms, sizeof(*doms), GFP_KERNEL);
2592 if (!doms)
2593 return NULL;
2594 for (i = 0; i < ndoms; i++) {
2595 if (!alloc_cpumask_var(&doms[i], GFP_KERNEL)) {
2596 free_sched_domains(doms, i);
2597 return NULL;
2598 }
2599 }
2600 return doms;
2601 }
2602
free_sched_domains(cpumask_var_t doms[],unsigned int ndoms)2603 void free_sched_domains(cpumask_var_t doms[], unsigned int ndoms)
2604 {
2605 unsigned int i;
2606 for (i = 0; i < ndoms; i++)
2607 free_cpumask_var(doms[i]);
2608 kfree(doms);
2609 }
2610
2611 /*
2612 * Set up scheduler domains and groups. For now this just excludes isolated
2613 * CPUs, but could be used to exclude other special cases in the future.
2614 */
sched_init_domains(const struct cpumask * cpu_map)2615 int __init sched_init_domains(const struct cpumask *cpu_map)
2616 {
2617 int err;
2618
2619 zalloc_cpumask_var(&sched_domains_tmpmask, GFP_KERNEL);
2620 zalloc_cpumask_var(&sched_domains_tmpmask2, GFP_KERNEL);
2621 zalloc_cpumask_var(&fallback_doms, GFP_KERNEL);
2622
2623 arch_update_cpu_topology();
2624 asym_cpu_capacity_scan();
2625 ndoms_cur = 1;
2626 doms_cur = alloc_sched_domains(ndoms_cur);
2627 if (!doms_cur)
2628 doms_cur = &fallback_doms;
2629 cpumask_and(doms_cur[0], cpu_map, housekeeping_cpumask(HK_TYPE_DOMAIN));
2630 err = build_sched_domains(doms_cur[0], NULL);
2631
2632 return err;
2633 }
2634
2635 /*
2636 * Detach sched domains from a group of CPUs specified in cpu_map
2637 * These CPUs will now be attached to the NULL domain
2638 */
detach_destroy_domains(const struct cpumask * cpu_map)2639 static void detach_destroy_domains(const struct cpumask *cpu_map)
2640 {
2641 unsigned int cpu = cpumask_any(cpu_map);
2642 int i;
2643
2644 if (rcu_access_pointer(per_cpu(sd_asym_cpucapacity, cpu)))
2645 static_branch_dec_cpuslocked(&sched_asym_cpucapacity);
2646
2647 if (static_branch_unlikely(&sched_cluster_active))
2648 static_branch_dec_cpuslocked(&sched_cluster_active);
2649
2650 rcu_read_lock();
2651 for_each_cpu(i, cpu_map)
2652 cpu_attach_domain(NULL, &def_root_domain, i);
2653 rcu_read_unlock();
2654 }
2655
2656 /* handle null as "default" */
dattrs_equal(struct sched_domain_attr * cur,int idx_cur,struct sched_domain_attr * new,int idx_new)2657 static int dattrs_equal(struct sched_domain_attr *cur, int idx_cur,
2658 struct sched_domain_attr *new, int idx_new)
2659 {
2660 struct sched_domain_attr tmp;
2661
2662 /* Fast path: */
2663 if (!new && !cur)
2664 return 1;
2665
2666 tmp = SD_ATTR_INIT;
2667
2668 return !memcmp(cur ? (cur + idx_cur) : &tmp,
2669 new ? (new + idx_new) : &tmp,
2670 sizeof(struct sched_domain_attr));
2671 }
2672
2673 /*
2674 * Partition sched domains as specified by the 'ndoms_new'
2675 * cpumasks in the array doms_new[] of cpumasks. This compares
2676 * doms_new[] to the current sched domain partitioning, doms_cur[].
2677 * It destroys each deleted domain and builds each new domain.
2678 *
2679 * 'doms_new' is an array of cpumask_var_t's of length 'ndoms_new'.
2680 * The masks don't intersect (don't overlap.) We should setup one
2681 * sched domain for each mask. CPUs not in any of the cpumasks will
2682 * not be load balanced. If the same cpumask appears both in the
2683 * current 'doms_cur' domains and in the new 'doms_new', we can leave
2684 * it as it is.
2685 *
2686 * The passed in 'doms_new' should be allocated using
2687 * alloc_sched_domains. This routine takes ownership of it and will
2688 * free_sched_domains it when done with it. If the caller failed the
2689 * alloc call, then it can pass in doms_new == NULL && ndoms_new == 1,
2690 * and partition_sched_domains() will fallback to the single partition
2691 * 'fallback_doms', it also forces the domains to be rebuilt.
2692 *
2693 * If doms_new == NULL it will be replaced with cpu_online_mask.
2694 * ndoms_new == 0 is a special case for destroying existing domains,
2695 * and it will not create the default domain.
2696 *
2697 * Call with hotplug lock and sched_domains_mutex held
2698 */
partition_sched_domains_locked(int ndoms_new,cpumask_var_t doms_new[],struct sched_domain_attr * dattr_new)2699 void partition_sched_domains_locked(int ndoms_new, cpumask_var_t doms_new[],
2700 struct sched_domain_attr *dattr_new)
2701 {
2702 bool __maybe_unused has_eas = false;
2703 int i, j, n;
2704 int new_topology;
2705
2706 lockdep_assert_held(&sched_domains_mutex);
2707
2708 /* Let the architecture update CPU core mappings: */
2709 new_topology = arch_update_cpu_topology();
2710 /* Trigger rebuilding CPU capacity asymmetry data */
2711 if (new_topology)
2712 asym_cpu_capacity_scan();
2713
2714 if (!doms_new) {
2715 WARN_ON_ONCE(dattr_new);
2716 n = 0;
2717 doms_new = alloc_sched_domains(1);
2718 if (doms_new) {
2719 n = 1;
2720 cpumask_and(doms_new[0], cpu_active_mask,
2721 housekeeping_cpumask(HK_TYPE_DOMAIN));
2722 }
2723 } else {
2724 n = ndoms_new;
2725 }
2726
2727 /* Destroy deleted domains: */
2728 for (i = 0; i < ndoms_cur; i++) {
2729 for (j = 0; j < n && !new_topology; j++) {
2730 if (cpumask_equal(doms_cur[i], doms_new[j]) &&
2731 dattrs_equal(dattr_cur, i, dattr_new, j)) {
2732 struct root_domain *rd;
2733
2734 /*
2735 * This domain won't be destroyed and as such
2736 * its dl_bw->total_bw needs to be cleared. It
2737 * will be recomputed in function
2738 * update_tasks_root_domain().
2739 */
2740 rd = cpu_rq(cpumask_any(doms_cur[i]))->rd;
2741 dl_clear_root_domain(rd);
2742 goto match1;
2743 }
2744 }
2745 /* No match - a current sched domain not in new doms_new[] */
2746 detach_destroy_domains(doms_cur[i]);
2747 match1:
2748 ;
2749 }
2750
2751 n = ndoms_cur;
2752 if (!doms_new) {
2753 n = 0;
2754 doms_new = &fallback_doms;
2755 cpumask_and(doms_new[0], cpu_active_mask,
2756 housekeeping_cpumask(HK_TYPE_DOMAIN));
2757 }
2758
2759 /* Build new domains: */
2760 for (i = 0; i < ndoms_new; i++) {
2761 for (j = 0; j < n && !new_topology; j++) {
2762 if (cpumask_equal(doms_new[i], doms_cur[j]) &&
2763 dattrs_equal(dattr_new, i, dattr_cur, j))
2764 goto match2;
2765 }
2766 /* No match - add a new doms_new */
2767 build_sched_domains(doms_new[i], dattr_new ? dattr_new + i : NULL);
2768 match2:
2769 ;
2770 }
2771
2772 #if defined(CONFIG_ENERGY_MODEL) && defined(CONFIG_CPU_FREQ_GOV_SCHEDUTIL)
2773 /* Build perf domains: */
2774 for (i = 0; i < ndoms_new; i++) {
2775 for (j = 0; j < n && !sched_energy_update; j++) {
2776 if (cpumask_equal(doms_new[i], doms_cur[j]) &&
2777 cpu_rq(cpumask_first(doms_cur[j]))->rd->pd) {
2778 has_eas = true;
2779 goto match3;
2780 }
2781 }
2782 /* No match - add perf domains for a new rd */
2783 has_eas |= build_perf_domains(doms_new[i]);
2784 match3:
2785 ;
2786 }
2787 sched_energy_set(has_eas);
2788 #endif
2789
2790 /* Remember the new sched domains: */
2791 if (doms_cur != &fallback_doms)
2792 free_sched_domains(doms_cur, ndoms_cur);
2793
2794 kfree(dattr_cur);
2795 doms_cur = doms_new;
2796 dattr_cur = dattr_new;
2797 ndoms_cur = ndoms_new;
2798
2799 update_sched_domain_debugfs();
2800 }
2801
2802 /*
2803 * Call with hotplug lock held
2804 */
partition_sched_domains(int ndoms_new,cpumask_var_t doms_new[],struct sched_domain_attr * dattr_new)2805 void partition_sched_domains(int ndoms_new, cpumask_var_t doms_new[],
2806 struct sched_domain_attr *dattr_new)
2807 {
2808 mutex_lock(&sched_domains_mutex);
2809 partition_sched_domains_locked(ndoms_new, doms_new, dattr_new);
2810 mutex_unlock(&sched_domains_mutex);
2811 }
2812