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