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

Provided by KDAB

Privacy Policy
Improve your Profiling and Debugging skills
Find out more

source code of linux/kernel/sched/topology.c