1 // SPDX-License-Identifier: GPL-2.0 2 /* 3 * BPF extensible scheduler class: Documentation/scheduler/sched-ext.rst 4 * 5 * Built-in idle CPU tracking policy. 6 * 7 * Copyright (c) 2022 Meta Platforms, Inc. and affiliates. 8 * Copyright (c) 2022 Tejun Heo <tj@kernel.org> 9 * Copyright (c) 2022 David Vernet <dvernet@meta.com> 10 * Copyright (c) 2024 Andrea Righi <arighi@nvidia.com> 11 */ 12 #include "ext_idle.h" 13 14 /* Enable/disable built-in idle CPU selection policy */ 15 static DEFINE_STATIC_KEY_FALSE(scx_builtin_idle_enabled); 16 17 /* Enable/disable per-node idle cpumasks */ 18 static DEFINE_STATIC_KEY_FALSE(scx_builtin_idle_per_node); 19 20 #ifdef CONFIG_SMP 21 /* Enable/disable LLC aware optimizations */ 22 static DEFINE_STATIC_KEY_FALSE(scx_selcpu_topo_llc); 23 24 /* Enable/disable NUMA aware optimizations */ 25 static DEFINE_STATIC_KEY_FALSE(scx_selcpu_topo_numa); 26 27 /* 28 * cpumasks to track idle CPUs within each NUMA node. 29 * 30 * If SCX_OPS_BUILTIN_IDLE_PER_NODE is not enabled, a single global cpumask 31 * from is used to track all the idle CPUs in the system. 32 */ 33 struct scx_idle_cpus { 34 cpumask_var_t cpu; 35 cpumask_var_t smt; 36 }; 37 38 /* 39 * Global host-wide idle cpumasks (used when SCX_OPS_BUILTIN_IDLE_PER_NODE 40 * is not enabled). 41 */ 42 static struct scx_idle_cpus scx_idle_global_masks; 43 44 /* 45 * Per-node idle cpumasks. 46 */ 47 static struct scx_idle_cpus **scx_idle_node_masks; 48 49 /* 50 * Return the idle masks associated to a target @node. 51 * 52 * NUMA_NO_NODE identifies the global idle cpumask. 53 */ 54 static struct scx_idle_cpus *idle_cpumask(int node) 55 { 56 return node == NUMA_NO_NODE ? &scx_idle_global_masks : scx_idle_node_masks[node]; 57 } 58 59 /* 60 * Returns the NUMA node ID associated with a @cpu, or NUMA_NO_NODE if 61 * per-node idle cpumasks are disabled. 62 */ 63 static int scx_cpu_node_if_enabled(int cpu) 64 { 65 if (!static_branch_maybe(CONFIG_NUMA, &scx_builtin_idle_per_node)) 66 return NUMA_NO_NODE; 67 68 return cpu_to_node(cpu); 69 } 70 71 bool scx_idle_test_and_clear_cpu(int cpu) 72 { 73 int node = scx_cpu_node_if_enabled(cpu); 74 struct cpumask *idle_cpus = idle_cpumask(node)->cpu; 75 76 #ifdef CONFIG_SCHED_SMT 77 /* 78 * SMT mask should be cleared whether we can claim @cpu or not. The SMT 79 * cluster is not wholly idle either way. This also prevents 80 * scx_pick_idle_cpu() from getting caught in an infinite loop. 81 */ 82 if (sched_smt_active()) { 83 const struct cpumask *smt = cpu_smt_mask(cpu); 84 struct cpumask *idle_smts = idle_cpumask(node)->smt; 85 86 /* 87 * If offline, @cpu is not its own sibling and 88 * scx_pick_idle_cpu() can get caught in an infinite loop as 89 * @cpu is never cleared from the idle SMT mask. Ensure that 90 * @cpu is eventually cleared. 91 * 92 * NOTE: Use cpumask_intersects() and cpumask_test_cpu() to 93 * reduce memory writes, which may help alleviate cache 94 * coherence pressure. 95 */ 96 if (cpumask_intersects(smt, idle_smts)) 97 cpumask_andnot(idle_smts, idle_smts, smt); 98 else if (cpumask_test_cpu(cpu, idle_smts)) 99 __cpumask_clear_cpu(cpu, idle_smts); 100 } 101 #endif 102 103 return cpumask_test_and_clear_cpu(cpu, idle_cpus); 104 } 105 106 /* 107 * Pick an idle CPU in a specific NUMA node. 108 */ 109 static s32 pick_idle_cpu_in_node(const struct cpumask *cpus_allowed, int node, u64 flags) 110 { 111 int cpu; 112 113 retry: 114 if (sched_smt_active()) { 115 cpu = cpumask_any_and_distribute(idle_cpumask(node)->smt, cpus_allowed); 116 if (cpu < nr_cpu_ids) 117 goto found; 118 119 if (flags & SCX_PICK_IDLE_CORE) 120 return -EBUSY; 121 } 122 123 cpu = cpumask_any_and_distribute(idle_cpumask(node)->cpu, cpus_allowed); 124 if (cpu >= nr_cpu_ids) 125 return -EBUSY; 126 127 found: 128 if (scx_idle_test_and_clear_cpu(cpu)) 129 return cpu; 130 else 131 goto retry; 132 } 133 134 /* 135 * Tracks nodes that have not yet been visited when searching for an idle 136 * CPU across all available nodes. 137 */ 138 static DEFINE_PER_CPU(nodemask_t, per_cpu_unvisited); 139 140 /* 141 * Search for an idle CPU across all nodes, excluding @node. 142 */ 143 static s32 pick_idle_cpu_from_online_nodes(const struct cpumask *cpus_allowed, int node, u64 flags) 144 { 145 nodemask_t *unvisited; 146 s32 cpu = -EBUSY; 147 148 preempt_disable(); 149 unvisited = this_cpu_ptr(&per_cpu_unvisited); 150 151 /* 152 * Restrict the search to the online nodes (excluding the current 153 * node that has been visited already). 154 */ 155 nodes_copy(*unvisited, node_states[N_ONLINE]); 156 node_clear(node, *unvisited); 157 158 /* 159 * Traverse all nodes in order of increasing distance, starting 160 * from @node. 161 * 162 * This loop is O(N^2), with N being the amount of NUMA nodes, 163 * which might be quite expensive in large NUMA systems. However, 164 * this complexity comes into play only when a scheduler enables 165 * SCX_OPS_BUILTIN_IDLE_PER_NODE and it's requesting an idle CPU 166 * without specifying a target NUMA node, so it shouldn't be a 167 * bottleneck is most cases. 168 * 169 * As a future optimization we may want to cache the list of nodes 170 * in a per-node array, instead of actually traversing them every 171 * time. 172 */ 173 for_each_node_numadist(node, *unvisited) { 174 cpu = pick_idle_cpu_in_node(cpus_allowed, node, flags); 175 if (cpu >= 0) 176 break; 177 } 178 preempt_enable(); 179 180 return cpu; 181 } 182 183 /* 184 * Find an idle CPU in the system, starting from @node. 185 */ 186 s32 scx_pick_idle_cpu(const struct cpumask *cpus_allowed, int node, u64 flags) 187 { 188 s32 cpu; 189 190 /* 191 * Always search in the starting node first (this is an 192 * optimization that can save some cycles even when the search is 193 * not limited to a single node). 194 */ 195 cpu = pick_idle_cpu_in_node(cpus_allowed, node, flags); 196 if (cpu >= 0) 197 return cpu; 198 199 /* 200 * Stop the search if we are using only a single global cpumask 201 * (NUMA_NO_NODE) or if the search is restricted to the first node 202 * only. 203 */ 204 if (node == NUMA_NO_NODE || flags & SCX_PICK_IDLE_IN_NODE) 205 return -EBUSY; 206 207 /* 208 * Extend the search to the other online nodes. 209 */ 210 return pick_idle_cpu_from_online_nodes(cpus_allowed, node, flags); 211 } 212 213 /* 214 * Return the amount of CPUs in the same LLC domain of @cpu (or zero if the LLC 215 * domain is not defined). 216 */ 217 static unsigned int llc_weight(s32 cpu) 218 { 219 struct sched_domain *sd; 220 221 sd = rcu_dereference(per_cpu(sd_llc, cpu)); 222 if (!sd) 223 return 0; 224 225 return sd->span_weight; 226 } 227 228 /* 229 * Return the cpumask representing the LLC domain of @cpu (or NULL if the LLC 230 * domain is not defined). 231 */ 232 static struct cpumask *llc_span(s32 cpu) 233 { 234 struct sched_domain *sd; 235 236 sd = rcu_dereference(per_cpu(sd_llc, cpu)); 237 if (!sd) 238 return 0; 239 240 return sched_domain_span(sd); 241 } 242 243 /* 244 * Return the amount of CPUs in the same NUMA domain of @cpu (or zero if the 245 * NUMA domain is not defined). 246 */ 247 static unsigned int numa_weight(s32 cpu) 248 { 249 struct sched_domain *sd; 250 struct sched_group *sg; 251 252 sd = rcu_dereference(per_cpu(sd_numa, cpu)); 253 if (!sd) 254 return 0; 255 sg = sd->groups; 256 if (!sg) 257 return 0; 258 259 return sg->group_weight; 260 } 261 262 /* 263 * Return the cpumask representing the NUMA domain of @cpu (or NULL if the NUMA 264 * domain is not defined). 265 */ 266 static struct cpumask *numa_span(s32 cpu) 267 { 268 struct sched_domain *sd; 269 struct sched_group *sg; 270 271 sd = rcu_dereference(per_cpu(sd_numa, cpu)); 272 if (!sd) 273 return NULL; 274 sg = sd->groups; 275 if (!sg) 276 return NULL; 277 278 return sched_group_span(sg); 279 } 280 281 /* 282 * Return true if the LLC domains do not perfectly overlap with the NUMA 283 * domains, false otherwise. 284 */ 285 static bool llc_numa_mismatch(void) 286 { 287 int cpu; 288 289 /* 290 * We need to scan all online CPUs to verify whether their scheduling 291 * domains overlap. 292 * 293 * While it is rare to encounter architectures with asymmetric NUMA 294 * topologies, CPU hotplugging or virtualized environments can result 295 * in asymmetric configurations. 296 * 297 * For example: 298 * 299 * NUMA 0: 300 * - LLC 0: cpu0..cpu7 301 * - LLC 1: cpu8..cpu15 [offline] 302 * 303 * NUMA 1: 304 * - LLC 0: cpu16..cpu23 305 * - LLC 1: cpu24..cpu31 306 * 307 * In this case, if we only check the first online CPU (cpu0), we might 308 * incorrectly assume that the LLC and NUMA domains are fully 309 * overlapping, which is incorrect (as NUMA 1 has two distinct LLC 310 * domains). 311 */ 312 for_each_online_cpu(cpu) 313 if (llc_weight(cpu) != numa_weight(cpu)) 314 return true; 315 316 return false; 317 } 318 319 /* 320 * Initialize topology-aware scheduling. 321 * 322 * Detect if the system has multiple LLC or multiple NUMA domains and enable 323 * cache-aware / NUMA-aware scheduling optimizations in the default CPU idle 324 * selection policy. 325 * 326 * Assumption: the kernel's internal topology representation assumes that each 327 * CPU belongs to a single LLC domain, and that each LLC domain is entirely 328 * contained within a single NUMA node. 329 */ 330 void scx_idle_update_selcpu_topology(struct sched_ext_ops *ops) 331 { 332 bool enable_llc = false, enable_numa = false; 333 unsigned int nr_cpus; 334 s32 cpu = cpumask_first(cpu_online_mask); 335 336 /* 337 * Enable LLC domain optimization only when there are multiple LLC 338 * domains among the online CPUs. If all online CPUs are part of a 339 * single LLC domain, the idle CPU selection logic can choose any 340 * online CPU without bias. 341 * 342 * Note that it is sufficient to check the LLC domain of the first 343 * online CPU to determine whether a single LLC domain includes all 344 * CPUs. 345 */ 346 rcu_read_lock(); 347 nr_cpus = llc_weight(cpu); 348 if (nr_cpus > 0) { 349 if (nr_cpus < num_online_cpus()) 350 enable_llc = true; 351 pr_debug("sched_ext: LLC=%*pb weight=%u\n", 352 cpumask_pr_args(llc_span(cpu)), llc_weight(cpu)); 353 } 354 355 /* 356 * Enable NUMA optimization only when there are multiple NUMA domains 357 * among the online CPUs and the NUMA domains don't perfectly overlaps 358 * with the LLC domains. 359 * 360 * If all CPUs belong to the same NUMA node and the same LLC domain, 361 * enabling both NUMA and LLC optimizations is unnecessary, as checking 362 * for an idle CPU in the same domain twice is redundant. 363 * 364 * If SCX_OPS_BUILTIN_IDLE_PER_NODE is enabled ignore the NUMA 365 * optimization, as we would naturally select idle CPUs within 366 * specific NUMA nodes querying the corresponding per-node cpumask. 367 */ 368 if (!(ops->flags & SCX_OPS_BUILTIN_IDLE_PER_NODE)) { 369 nr_cpus = numa_weight(cpu); 370 if (nr_cpus > 0) { 371 if (nr_cpus < num_online_cpus() && llc_numa_mismatch()) 372 enable_numa = true; 373 pr_debug("sched_ext: NUMA=%*pb weight=%u\n", 374 cpumask_pr_args(numa_span(cpu)), nr_cpus); 375 } 376 } 377 rcu_read_unlock(); 378 379 pr_debug("sched_ext: LLC idle selection %s\n", 380 str_enabled_disabled(enable_llc)); 381 pr_debug("sched_ext: NUMA idle selection %s\n", 382 str_enabled_disabled(enable_numa)); 383 384 if (enable_llc) 385 static_branch_enable_cpuslocked(&scx_selcpu_topo_llc); 386 else 387 static_branch_disable_cpuslocked(&scx_selcpu_topo_llc); 388 if (enable_numa) 389 static_branch_enable_cpuslocked(&scx_selcpu_topo_numa); 390 else 391 static_branch_disable_cpuslocked(&scx_selcpu_topo_numa); 392 } 393 394 /* 395 * Built-in CPU idle selection policy: 396 * 397 * 1. Prioritize full-idle cores: 398 * - always prioritize CPUs from fully idle cores (both logical CPUs are 399 * idle) to avoid interference caused by SMT. 400 * 401 * 2. Reuse the same CPU: 402 * - prefer the last used CPU to take advantage of cached data (L1, L2) and 403 * branch prediction optimizations. 404 * 405 * 3. Pick a CPU within the same LLC (Last-Level Cache): 406 * - if the above conditions aren't met, pick a CPU that shares the same LLC 407 * to maintain cache locality. 408 * 409 * 4. Pick a CPU within the same NUMA node, if enabled: 410 * - choose a CPU from the same NUMA node to reduce memory access latency. 411 * 412 * 5. Pick any idle CPU usable by the task. 413 * 414 * Step 3 and 4 are performed only if the system has, respectively, 415 * multiple LLCs / multiple NUMA nodes (see scx_selcpu_topo_llc and 416 * scx_selcpu_topo_numa) and they don't contain the same subset of CPUs. 417 * 418 * If %SCX_OPS_BUILTIN_IDLE_PER_NODE is enabled, the search will always 419 * begin in @prev_cpu's node and proceed to other nodes in order of 420 * increasing distance. 421 * 422 * Return the picked CPU if idle, or a negative value otherwise. 423 * 424 * NOTE: tasks that can only run on 1 CPU are excluded by this logic, because 425 * we never call ops.select_cpu() for them, see select_task_rq(). 426 */ 427 s32 scx_select_cpu_dfl(struct task_struct *p, s32 prev_cpu, u64 wake_flags, u64 flags) 428 { 429 const struct cpumask *llc_cpus = NULL; 430 const struct cpumask *numa_cpus = NULL; 431 int node = scx_cpu_node_if_enabled(prev_cpu); 432 s32 cpu; 433 434 /* 435 * This is necessary to protect llc_cpus. 436 */ 437 rcu_read_lock(); 438 439 /* 440 * Determine the scheduling domain only if the task is allowed to run 441 * on all CPUs. 442 * 443 * This is done primarily for efficiency, as it avoids the overhead of 444 * updating a cpumask every time we need to select an idle CPU (which 445 * can be costly in large SMP systems), but it also aligns logically: 446 * if a task's scheduling domain is restricted by user-space (through 447 * CPU affinity), the task will simply use the flat scheduling domain 448 * defined by user-space. 449 */ 450 if (p->nr_cpus_allowed >= num_possible_cpus()) { 451 if (static_branch_maybe(CONFIG_NUMA, &scx_selcpu_topo_numa)) 452 numa_cpus = numa_span(prev_cpu); 453 454 if (static_branch_maybe(CONFIG_SCHED_MC, &scx_selcpu_topo_llc)) 455 llc_cpus = llc_span(prev_cpu); 456 } 457 458 /* 459 * If WAKE_SYNC, try to migrate the wakee to the waker's CPU. 460 */ 461 if (wake_flags & SCX_WAKE_SYNC) { 462 int waker_node; 463 464 /* 465 * If the waker's CPU is cache affine and prev_cpu is idle, 466 * then avoid a migration. 467 */ 468 cpu = smp_processor_id(); 469 if (cpus_share_cache(cpu, prev_cpu) && 470 scx_idle_test_and_clear_cpu(prev_cpu)) { 471 cpu = prev_cpu; 472 goto out_unlock; 473 } 474 475 /* 476 * If the waker's local DSQ is empty, and the system is under 477 * utilized, try to wake up @p to the local DSQ of the waker. 478 * 479 * Checking only for an empty local DSQ is insufficient as it 480 * could give the wakee an unfair advantage when the system is 481 * oversaturated. 482 * 483 * Checking only for the presence of idle CPUs is also 484 * insufficient as the local DSQ of the waker could have tasks 485 * piled up on it even if there is an idle core elsewhere on 486 * the system. 487 */ 488 waker_node = cpu_to_node(cpu); 489 if (!(current->flags & PF_EXITING) && 490 cpu_rq(cpu)->scx.local_dsq.nr == 0 && 491 (!(flags & SCX_PICK_IDLE_IN_NODE) || (waker_node == node)) && 492 !cpumask_empty(idle_cpumask(waker_node)->cpu)) { 493 if (cpumask_test_cpu(cpu, p->cpus_ptr)) 494 goto out_unlock; 495 } 496 } 497 498 /* 499 * If CPU has SMT, any wholly idle CPU is likely a better pick than 500 * partially idle @prev_cpu. 501 */ 502 if (sched_smt_active()) { 503 /* 504 * Keep using @prev_cpu if it's part of a fully idle core. 505 */ 506 if (cpumask_test_cpu(prev_cpu, idle_cpumask(node)->smt) && 507 scx_idle_test_and_clear_cpu(prev_cpu)) { 508 cpu = prev_cpu; 509 goto out_unlock; 510 } 511 512 /* 513 * Search for any fully idle core in the same LLC domain. 514 */ 515 if (llc_cpus) { 516 cpu = pick_idle_cpu_in_node(llc_cpus, node, SCX_PICK_IDLE_CORE); 517 if (cpu >= 0) 518 goto out_unlock; 519 } 520 521 /* 522 * Search for any fully idle core in the same NUMA node. 523 */ 524 if (numa_cpus) { 525 cpu = pick_idle_cpu_in_node(numa_cpus, node, SCX_PICK_IDLE_CORE); 526 if (cpu >= 0) 527 goto out_unlock; 528 } 529 530 /* 531 * Search for any full-idle core usable by the task. 532 * 533 * If the node-aware idle CPU selection policy is enabled 534 * (%SCX_OPS_BUILTIN_IDLE_PER_NODE), the search will always 535 * begin in prev_cpu's node and proceed to other nodes in 536 * order of increasing distance. 537 */ 538 cpu = scx_pick_idle_cpu(p->cpus_ptr, node, flags | SCX_PICK_IDLE_CORE); 539 if (cpu >= 0) 540 goto out_unlock; 541 542 /* 543 * Give up if we're strictly looking for a full-idle SMT 544 * core. 545 */ 546 if (flags & SCX_PICK_IDLE_CORE) { 547 cpu = -EBUSY; 548 goto out_unlock; 549 } 550 } 551 552 /* 553 * Use @prev_cpu if it's idle. 554 */ 555 if (scx_idle_test_and_clear_cpu(prev_cpu)) { 556 cpu = prev_cpu; 557 goto out_unlock; 558 } 559 560 /* 561 * Search for any idle CPU in the same LLC domain. 562 */ 563 if (llc_cpus) { 564 cpu = pick_idle_cpu_in_node(llc_cpus, node, 0); 565 if (cpu >= 0) 566 goto out_unlock; 567 } 568 569 /* 570 * Search for any idle CPU in the same NUMA node. 571 */ 572 if (numa_cpus) { 573 cpu = pick_idle_cpu_in_node(numa_cpus, node, 0); 574 if (cpu >= 0) 575 goto out_unlock; 576 } 577 578 /* 579 * Search for any idle CPU usable by the task. 580 * 581 * If the node-aware idle CPU selection policy is enabled 582 * (%SCX_OPS_BUILTIN_IDLE_PER_NODE), the search will always begin 583 * in prev_cpu's node and proceed to other nodes in order of 584 * increasing distance. 585 */ 586 cpu = scx_pick_idle_cpu(p->cpus_ptr, node, flags); 587 588 out_unlock: 589 rcu_read_unlock(); 590 591 return cpu; 592 } 593 594 /* 595 * Initialize global and per-node idle cpumasks. 596 */ 597 void scx_idle_init_masks(void) 598 { 599 int node; 600 601 /* Allocate global idle cpumasks */ 602 BUG_ON(!alloc_cpumask_var(&scx_idle_global_masks.cpu, GFP_KERNEL)); 603 BUG_ON(!alloc_cpumask_var(&scx_idle_global_masks.smt, GFP_KERNEL)); 604 605 /* Allocate per-node idle cpumasks */ 606 scx_idle_node_masks = kcalloc(num_possible_nodes(), 607 sizeof(*scx_idle_node_masks), GFP_KERNEL); 608 BUG_ON(!scx_idle_node_masks); 609 610 for_each_node(node) { 611 scx_idle_node_masks[node] = kzalloc_node(sizeof(**scx_idle_node_masks), 612 GFP_KERNEL, node); 613 BUG_ON(!scx_idle_node_masks[node]); 614 615 BUG_ON(!alloc_cpumask_var_node(&scx_idle_node_masks[node]->cpu, GFP_KERNEL, node)); 616 BUG_ON(!alloc_cpumask_var_node(&scx_idle_node_masks[node]->smt, GFP_KERNEL, node)); 617 } 618 } 619 620 static void update_builtin_idle(int cpu, bool idle) 621 { 622 int node = scx_cpu_node_if_enabled(cpu); 623 struct cpumask *idle_cpus = idle_cpumask(node)->cpu; 624 625 assign_cpu(cpu, idle_cpus, idle); 626 627 #ifdef CONFIG_SCHED_SMT 628 if (sched_smt_active()) { 629 const struct cpumask *smt = cpu_smt_mask(cpu); 630 struct cpumask *idle_smts = idle_cpumask(node)->smt; 631 632 if (idle) { 633 /* 634 * idle_smt handling is racy but that's fine as it's 635 * only for optimization and self-correcting. 636 */ 637 if (!cpumask_subset(smt, idle_cpus)) 638 return; 639 cpumask_or(idle_smts, idle_smts, smt); 640 } else { 641 cpumask_andnot(idle_smts, idle_smts, smt); 642 } 643 } 644 #endif 645 } 646 647 /* 648 * Update the idle state of a CPU to @idle. 649 * 650 * If @do_notify is true, ops.update_idle() is invoked to notify the scx 651 * scheduler of an actual idle state transition (idle to busy or vice 652 * versa). If @do_notify is false, only the idle state in the idle masks is 653 * refreshed without invoking ops.update_idle(). 654 * 655 * This distinction is necessary, because an idle CPU can be "reserved" and 656 * awakened via scx_bpf_pick_idle_cpu() + scx_bpf_kick_cpu(), marking it as 657 * busy even if no tasks are dispatched. In this case, the CPU may return 658 * to idle without a true state transition. Refreshing the idle masks 659 * without invoking ops.update_idle() ensures accurate idle state tracking 660 * while avoiding unnecessary updates and maintaining balanced state 661 * transitions. 662 */ 663 void __scx_update_idle(struct rq *rq, bool idle, bool do_notify) 664 { 665 int cpu = cpu_of(rq); 666 667 lockdep_assert_rq_held(rq); 668 669 /* 670 * Trigger ops.update_idle() only when transitioning from a task to 671 * the idle thread and vice versa. 672 * 673 * Idle transitions are indicated by do_notify being set to true, 674 * managed by put_prev_task_idle()/set_next_task_idle(). 675 */ 676 if (SCX_HAS_OP(update_idle) && do_notify && !scx_rq_bypassing(rq)) 677 SCX_CALL_OP(SCX_KF_REST, update_idle, cpu_of(rq), idle); 678 679 /* 680 * Update the idle masks: 681 * - for real idle transitions (do_notify == true) 682 * - for idle-to-idle transitions (indicated by the previous task 683 * being the idle thread, managed by pick_task_idle()) 684 * 685 * Skip updating idle masks if the previous task is not the idle 686 * thread, since set_next_task_idle() has already handled it when 687 * transitioning from a task to the idle thread (calling this 688 * function with do_notify == true). 689 * 690 * In this way we can avoid updating the idle masks twice, 691 * unnecessarily. 692 */ 693 if (static_branch_likely(&scx_builtin_idle_enabled)) 694 if (do_notify || is_idle_task(rq->curr)) 695 update_builtin_idle(cpu, idle); 696 } 697 698 static void reset_idle_masks(struct sched_ext_ops *ops) 699 { 700 int node; 701 702 /* 703 * Consider all online cpus idle. Should converge to the actual state 704 * quickly. 705 */ 706 if (!(ops->flags & SCX_OPS_BUILTIN_IDLE_PER_NODE)) { 707 cpumask_copy(idle_cpumask(NUMA_NO_NODE)->cpu, cpu_online_mask); 708 cpumask_copy(idle_cpumask(NUMA_NO_NODE)->smt, cpu_online_mask); 709 return; 710 } 711 712 for_each_node(node) { 713 const struct cpumask *node_mask = cpumask_of_node(node); 714 715 cpumask_and(idle_cpumask(node)->cpu, cpu_online_mask, node_mask); 716 cpumask_and(idle_cpumask(node)->smt, cpu_online_mask, node_mask); 717 } 718 } 719 #endif /* CONFIG_SMP */ 720 721 void scx_idle_enable(struct sched_ext_ops *ops) 722 { 723 if (!ops->update_idle || (ops->flags & SCX_OPS_KEEP_BUILTIN_IDLE)) 724 static_branch_enable_cpuslocked(&scx_builtin_idle_enabled); 725 else 726 static_branch_disable_cpuslocked(&scx_builtin_idle_enabled); 727 728 if (ops->flags & SCX_OPS_BUILTIN_IDLE_PER_NODE) 729 static_branch_enable_cpuslocked(&scx_builtin_idle_per_node); 730 else 731 static_branch_disable_cpuslocked(&scx_builtin_idle_per_node); 732 733 #ifdef CONFIG_SMP 734 reset_idle_masks(ops); 735 #endif 736 } 737 738 void scx_idle_disable(void) 739 { 740 static_branch_disable(&scx_builtin_idle_enabled); 741 static_branch_disable(&scx_builtin_idle_per_node); 742 } 743 744 /******************************************************************************** 745 * Helpers that can be called from the BPF scheduler. 746 */ 747 748 static int validate_node(int node) 749 { 750 if (!static_branch_likely(&scx_builtin_idle_per_node)) { 751 scx_ops_error("per-node idle tracking is disabled"); 752 return -EOPNOTSUPP; 753 } 754 755 /* Return no entry for NUMA_NO_NODE (not a critical scx error) */ 756 if (node == NUMA_NO_NODE) 757 return -ENOENT; 758 759 /* Make sure node is in a valid range */ 760 if (node < 0 || node >= nr_node_ids) { 761 scx_ops_error("invalid node %d", node); 762 return -EINVAL; 763 } 764 765 /* Make sure the node is part of the set of possible nodes */ 766 if (!node_possible(node)) { 767 scx_ops_error("unavailable node %d", node); 768 return -EINVAL; 769 } 770 771 return node; 772 } 773 774 __bpf_kfunc_start_defs(); 775 776 static bool check_builtin_idle_enabled(void) 777 { 778 if (static_branch_likely(&scx_builtin_idle_enabled)) 779 return true; 780 781 scx_ops_error("built-in idle tracking is disabled"); 782 return false; 783 } 784 785 /** 786 * scx_bpf_cpu_node - Return the NUMA node the given @cpu belongs to, or 787 * trigger an error if @cpu is invalid 788 * @cpu: target CPU 789 */ 790 __bpf_kfunc int scx_bpf_cpu_node(s32 cpu) 791 { 792 #ifdef CONFIG_NUMA 793 if (!ops_cpu_valid(cpu, NULL)) 794 return NUMA_NO_NODE; 795 796 return cpu_to_node(cpu); 797 #else 798 return 0; 799 #endif 800 } 801 802 /** 803 * scx_bpf_select_cpu_dfl - The default implementation of ops.select_cpu() 804 * @p: task_struct to select a CPU for 805 * @prev_cpu: CPU @p was on previously 806 * @wake_flags: %SCX_WAKE_* flags 807 * @is_idle: out parameter indicating whether the returned CPU is idle 808 * 809 * Can only be called from ops.select_cpu() if the built-in CPU selection is 810 * enabled - ops.update_idle() is missing or %SCX_OPS_KEEP_BUILTIN_IDLE is set. 811 * @p, @prev_cpu and @wake_flags match ops.select_cpu(). 812 * 813 * Returns the picked CPU with *@is_idle indicating whether the picked CPU is 814 * currently idle and thus a good candidate for direct dispatching. 815 */ 816 __bpf_kfunc s32 scx_bpf_select_cpu_dfl(struct task_struct *p, s32 prev_cpu, 817 u64 wake_flags, bool *is_idle) 818 { 819 #ifdef CONFIG_SMP 820 s32 cpu; 821 #endif 822 if (!ops_cpu_valid(prev_cpu, NULL)) 823 goto prev_cpu; 824 825 if (!check_builtin_idle_enabled()) 826 goto prev_cpu; 827 828 if (!scx_kf_allowed(SCX_KF_SELECT_CPU)) 829 goto prev_cpu; 830 831 #ifdef CONFIG_SMP 832 cpu = scx_select_cpu_dfl(p, prev_cpu, wake_flags, 0); 833 if (cpu >= 0) { 834 *is_idle = true; 835 return cpu; 836 } 837 #endif 838 839 prev_cpu: 840 *is_idle = false; 841 return prev_cpu; 842 } 843 844 /** 845 * scx_bpf_get_idle_cpumask_node - Get a referenced kptr to the 846 * idle-tracking per-CPU cpumask of a target NUMA node. 847 * @node: target NUMA node 848 * 849 * Returns an empty cpumask if idle tracking is not enabled, if @node is 850 * not valid, or running on a UP kernel. In this case the actual error will 851 * be reported to the BPF scheduler via scx_ops_error(). 852 */ 853 __bpf_kfunc const struct cpumask *scx_bpf_get_idle_cpumask_node(int node) 854 { 855 node = validate_node(node); 856 if (node < 0) 857 return cpu_none_mask; 858 859 #ifdef CONFIG_SMP 860 return idle_cpumask(node)->cpu; 861 #else 862 return cpu_none_mask; 863 #endif 864 } 865 866 /** 867 * scx_bpf_get_idle_cpumask - Get a referenced kptr to the idle-tracking 868 * per-CPU cpumask. 869 * 870 * Returns an empty mask if idle tracking is not enabled, or running on a 871 * UP kernel. 872 */ 873 __bpf_kfunc const struct cpumask *scx_bpf_get_idle_cpumask(void) 874 { 875 if (static_branch_unlikely(&scx_builtin_idle_per_node)) { 876 scx_ops_error("SCX_OPS_BUILTIN_IDLE_PER_NODE enabled"); 877 return cpu_none_mask; 878 } 879 880 if (!check_builtin_idle_enabled()) 881 return cpu_none_mask; 882 883 #ifdef CONFIG_SMP 884 return idle_cpumask(NUMA_NO_NODE)->cpu; 885 #else 886 return cpu_none_mask; 887 #endif 888 } 889 890 /** 891 * scx_bpf_get_idle_smtmask_node - Get a referenced kptr to the 892 * idle-tracking, per-physical-core cpumask of a target NUMA node. Can be 893 * used to determine if an entire physical core is free. 894 * @node: target NUMA node 895 * 896 * Returns an empty cpumask if idle tracking is not enabled, if @node is 897 * not valid, or running on a UP kernel. In this case the actual error will 898 * be reported to the BPF scheduler via scx_ops_error(). 899 */ 900 __bpf_kfunc const struct cpumask *scx_bpf_get_idle_smtmask_node(int node) 901 { 902 node = validate_node(node); 903 if (node < 0) 904 return cpu_none_mask; 905 906 #ifdef CONFIG_SMP 907 if (sched_smt_active()) 908 return idle_cpumask(node)->smt; 909 else 910 return idle_cpumask(node)->cpu; 911 #else 912 return cpu_none_mask; 913 #endif 914 } 915 916 /** 917 * scx_bpf_get_idle_smtmask - Get a referenced kptr to the idle-tracking, 918 * per-physical-core cpumask. Can be used to determine if an entire physical 919 * core is free. 920 * 921 * Returns an empty mask if idle tracking is not enabled, or running on a 922 * UP kernel. 923 */ 924 __bpf_kfunc const struct cpumask *scx_bpf_get_idle_smtmask(void) 925 { 926 if (static_branch_unlikely(&scx_builtin_idle_per_node)) { 927 scx_ops_error("SCX_OPS_BUILTIN_IDLE_PER_NODE enabled"); 928 return cpu_none_mask; 929 } 930 931 if (!check_builtin_idle_enabled()) 932 return cpu_none_mask; 933 934 #ifdef CONFIG_SMP 935 if (sched_smt_active()) 936 return idle_cpumask(NUMA_NO_NODE)->smt; 937 else 938 return idle_cpumask(NUMA_NO_NODE)->cpu; 939 #else 940 return cpu_none_mask; 941 #endif 942 } 943 944 /** 945 * scx_bpf_put_idle_cpumask - Release a previously acquired referenced kptr to 946 * either the percpu, or SMT idle-tracking cpumask. 947 * @idle_mask: &cpumask to use 948 */ 949 __bpf_kfunc void scx_bpf_put_idle_cpumask(const struct cpumask *idle_mask) 950 { 951 /* 952 * Empty function body because we aren't actually acquiring or releasing 953 * a reference to a global idle cpumask, which is read-only in the 954 * caller and is never released. The acquire / release semantics here 955 * are just used to make the cpumask a trusted pointer in the caller. 956 */ 957 } 958 959 /** 960 * scx_bpf_test_and_clear_cpu_idle - Test and clear @cpu's idle state 961 * @cpu: cpu to test and clear idle for 962 * 963 * Returns %true if @cpu was idle and its idle state was successfully cleared. 964 * %false otherwise. 965 * 966 * Unavailable if ops.update_idle() is implemented and 967 * %SCX_OPS_KEEP_BUILTIN_IDLE is not set. 968 */ 969 __bpf_kfunc bool scx_bpf_test_and_clear_cpu_idle(s32 cpu) 970 { 971 if (!check_builtin_idle_enabled()) 972 return false; 973 974 if (ops_cpu_valid(cpu, NULL)) 975 return scx_idle_test_and_clear_cpu(cpu); 976 else 977 return false; 978 } 979 980 /** 981 * scx_bpf_pick_idle_cpu_node - Pick and claim an idle cpu from @node 982 * @cpus_allowed: Allowed cpumask 983 * @node: target NUMA node 984 * @flags: %SCX_PICK_IDLE_* flags 985 * 986 * Pick and claim an idle cpu in @cpus_allowed from the NUMA node @node. 987 * 988 * Returns the picked idle cpu number on success, or -%EBUSY if no matching 989 * cpu was found. 990 * 991 * The search starts from @node and proceeds to other online NUMA nodes in 992 * order of increasing distance (unless SCX_PICK_IDLE_IN_NODE is specified, 993 * in which case the search is limited to the target @node). 994 * 995 * Always returns an error if ops.update_idle() is implemented and 996 * %SCX_OPS_KEEP_BUILTIN_IDLE is not set, or if 997 * %SCX_OPS_BUILTIN_IDLE_PER_NODE is not set. 998 */ 999 __bpf_kfunc s32 scx_bpf_pick_idle_cpu_node(const struct cpumask *cpus_allowed, 1000 int node, u64 flags) 1001 { 1002 node = validate_node(node); 1003 if (node < 0) 1004 return node; 1005 1006 return scx_pick_idle_cpu(cpus_allowed, node, flags); 1007 } 1008 1009 /** 1010 * scx_bpf_pick_idle_cpu - Pick and claim an idle cpu 1011 * @cpus_allowed: Allowed cpumask 1012 * @flags: %SCX_PICK_IDLE_CPU_* flags 1013 * 1014 * Pick and claim an idle cpu in @cpus_allowed. Returns the picked idle cpu 1015 * number on success. -%EBUSY if no matching cpu was found. 1016 * 1017 * Idle CPU tracking may race against CPU scheduling state transitions. For 1018 * example, this function may return -%EBUSY as CPUs are transitioning into the 1019 * idle state. If the caller then assumes that there will be dispatch events on 1020 * the CPUs as they were all busy, the scheduler may end up stalling with CPUs 1021 * idling while there are pending tasks. Use scx_bpf_pick_any_cpu() and 1022 * scx_bpf_kick_cpu() to guarantee that there will be at least one dispatch 1023 * event in the near future. 1024 * 1025 * Unavailable if ops.update_idle() is implemented and 1026 * %SCX_OPS_KEEP_BUILTIN_IDLE is not set. 1027 * 1028 * Always returns an error if %SCX_OPS_BUILTIN_IDLE_PER_NODE is set, use 1029 * scx_bpf_pick_idle_cpu_node() instead. 1030 */ 1031 __bpf_kfunc s32 scx_bpf_pick_idle_cpu(const struct cpumask *cpus_allowed, 1032 u64 flags) 1033 { 1034 if (static_branch_maybe(CONFIG_NUMA, &scx_builtin_idle_per_node)) { 1035 scx_ops_error("per-node idle tracking is enabled"); 1036 return -EBUSY; 1037 } 1038 1039 if (!check_builtin_idle_enabled()) 1040 return -EBUSY; 1041 1042 return scx_pick_idle_cpu(cpus_allowed, NUMA_NO_NODE, flags); 1043 } 1044 1045 /** 1046 * scx_bpf_pick_any_cpu_node - Pick and claim an idle cpu if available 1047 * or pick any CPU from @node 1048 * @cpus_allowed: Allowed cpumask 1049 * @node: target NUMA node 1050 * @flags: %SCX_PICK_IDLE_CPU_* flags 1051 * 1052 * Pick and claim an idle cpu in @cpus_allowed. If none is available, pick any 1053 * CPU in @cpus_allowed. Guaranteed to succeed and returns the picked idle cpu 1054 * number if @cpus_allowed is not empty. -%EBUSY is returned if @cpus_allowed is 1055 * empty. 1056 * 1057 * The search starts from @node and proceeds to other online NUMA nodes in 1058 * order of increasing distance (unless %SCX_PICK_IDLE_IN_NODE is specified, 1059 * in which case the search is limited to the target @node, regardless of 1060 * the CPU idle state). 1061 * 1062 * If ops.update_idle() is implemented and %SCX_OPS_KEEP_BUILTIN_IDLE is not 1063 * set, this function can't tell which CPUs are idle and will always pick any 1064 * CPU. 1065 */ 1066 __bpf_kfunc s32 scx_bpf_pick_any_cpu_node(const struct cpumask *cpus_allowed, 1067 int node, u64 flags) 1068 { 1069 s32 cpu; 1070 1071 node = validate_node(node); 1072 if (node < 0) 1073 return node; 1074 1075 cpu = scx_pick_idle_cpu(cpus_allowed, node, flags); 1076 if (cpu >= 0) 1077 return cpu; 1078 1079 if (flags & SCX_PICK_IDLE_IN_NODE) 1080 cpu = cpumask_any_and_distribute(cpumask_of_node(node), cpus_allowed); 1081 else 1082 cpu = cpumask_any_distribute(cpus_allowed); 1083 if (cpu < nr_cpu_ids) 1084 return cpu; 1085 else 1086 return -EBUSY; 1087 } 1088 1089 /** 1090 * scx_bpf_pick_any_cpu - Pick and claim an idle cpu if available or pick any CPU 1091 * @cpus_allowed: Allowed cpumask 1092 * @flags: %SCX_PICK_IDLE_CPU_* flags 1093 * 1094 * Pick and claim an idle cpu in @cpus_allowed. If none is available, pick any 1095 * CPU in @cpus_allowed. Guaranteed to succeed and returns the picked idle cpu 1096 * number if @cpus_allowed is not empty. -%EBUSY is returned if @cpus_allowed is 1097 * empty. 1098 * 1099 * If ops.update_idle() is implemented and %SCX_OPS_KEEP_BUILTIN_IDLE is not 1100 * set, this function can't tell which CPUs are idle and will always pick any 1101 * CPU. 1102 * 1103 * Always returns an error if %SCX_OPS_BUILTIN_IDLE_PER_NODE is set, use 1104 * scx_bpf_pick_any_cpu_node() instead. 1105 */ 1106 __bpf_kfunc s32 scx_bpf_pick_any_cpu(const struct cpumask *cpus_allowed, 1107 u64 flags) 1108 { 1109 s32 cpu; 1110 1111 if (static_branch_maybe(CONFIG_NUMA, &scx_builtin_idle_per_node)) { 1112 scx_ops_error("per-node idle tracking is enabled"); 1113 return -EBUSY; 1114 } 1115 1116 if (static_branch_likely(&scx_builtin_idle_enabled)) { 1117 cpu = scx_pick_idle_cpu(cpus_allowed, NUMA_NO_NODE, flags); 1118 if (cpu >= 0) 1119 return cpu; 1120 } 1121 1122 cpu = cpumask_any_distribute(cpus_allowed); 1123 if (cpu < nr_cpu_ids) 1124 return cpu; 1125 else 1126 return -EBUSY; 1127 } 1128 1129 __bpf_kfunc_end_defs(); 1130 1131 BTF_KFUNCS_START(scx_kfunc_ids_idle) 1132 BTF_ID_FLAGS(func, scx_bpf_cpu_node) 1133 BTF_ID_FLAGS(func, scx_bpf_get_idle_cpumask_node, KF_ACQUIRE) 1134 BTF_ID_FLAGS(func, scx_bpf_get_idle_cpumask, KF_ACQUIRE) 1135 BTF_ID_FLAGS(func, scx_bpf_get_idle_smtmask_node, KF_ACQUIRE) 1136 BTF_ID_FLAGS(func, scx_bpf_get_idle_smtmask, KF_ACQUIRE) 1137 BTF_ID_FLAGS(func, scx_bpf_put_idle_cpumask, KF_RELEASE) 1138 BTF_ID_FLAGS(func, scx_bpf_test_and_clear_cpu_idle) 1139 BTF_ID_FLAGS(func, scx_bpf_pick_idle_cpu_node, KF_RCU) 1140 BTF_ID_FLAGS(func, scx_bpf_pick_idle_cpu, KF_RCU) 1141 BTF_ID_FLAGS(func, scx_bpf_pick_any_cpu_node, KF_RCU) 1142 BTF_ID_FLAGS(func, scx_bpf_pick_any_cpu, KF_RCU) 1143 BTF_KFUNCS_END(scx_kfunc_ids_idle) 1144 1145 static const struct btf_kfunc_id_set scx_kfunc_set_idle = { 1146 .owner = THIS_MODULE, 1147 .set = &scx_kfunc_ids_idle, 1148 }; 1149 1150 BTF_KFUNCS_START(scx_kfunc_ids_select_cpu) 1151 BTF_ID_FLAGS(func, scx_bpf_select_cpu_dfl, KF_RCU) 1152 BTF_KFUNCS_END(scx_kfunc_ids_select_cpu) 1153 1154 static const struct btf_kfunc_id_set scx_kfunc_set_select_cpu = { 1155 .owner = THIS_MODULE, 1156 .set = &scx_kfunc_ids_select_cpu, 1157 }; 1158 1159 int scx_idle_init(void) 1160 { 1161 int ret; 1162 1163 ret = register_btf_kfunc_id_set(BPF_PROG_TYPE_STRUCT_OPS, &scx_kfunc_set_select_cpu) || 1164 register_btf_kfunc_id_set(BPF_PROG_TYPE_STRUCT_OPS, &scx_kfunc_set_idle) || 1165 register_btf_kfunc_id_set(BPF_PROG_TYPE_TRACING, &scx_kfunc_set_idle) || 1166 register_btf_kfunc_id_set(BPF_PROG_TYPE_SYSCALL, &scx_kfunc_set_idle); 1167 1168 return ret; 1169 } 1170