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