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 "internal.h" 13 #include "cid.h" 14 #include "idle.h" 15 #include "sub.h" 16 17 /* Enable/disable built-in idle CPU selection policy */ 18 static DEFINE_STATIC_KEY_FALSE(scx_builtin_idle_enabled); 19 20 /* Enable/disable per-node idle cpumasks */ 21 static DEFINE_STATIC_KEY_FALSE(scx_builtin_idle_per_node); 22 23 /* Enable/disable LLC aware optimizations */ 24 static DEFINE_STATIC_KEY_FALSE(scx_selcpu_topo_llc); 25 26 /* Enable/disable NUMA aware optimizations */ 27 static DEFINE_STATIC_KEY_FALSE(scx_selcpu_topo_numa); 28 29 /* 30 * cpumasks to track idle CPUs within each NUMA node. 31 * 32 * If SCX_OPS_BUILTIN_IDLE_PER_NODE is not enabled, a single global cpumask 33 * from is used to track all the idle CPUs in the system. 34 */ 35 struct scx_idle_cpus { 36 cpumask_var_t cpu; 37 cpumask_var_t smt; 38 }; 39 40 /* 41 * Global host-wide idle cpumasks (used when SCX_OPS_BUILTIN_IDLE_PER_NODE 42 * is not enabled). 43 */ 44 static struct scx_idle_cpus scx_idle_global_masks; 45 46 /* 47 * Per-node idle cpumasks. 48 */ 49 static struct scx_idle_cpus **scx_idle_node_masks; 50 51 /* 52 * Local per-CPU cpumasks (used to generate temporary idle cpumasks). 53 */ 54 static DEFINE_PER_CPU(cpumask_var_t, local_idle_cpumask); 55 static DEFINE_PER_CPU(cpumask_var_t, local_llc_idle_cpumask); 56 static DEFINE_PER_CPU(cpumask_var_t, local_numa_idle_cpumask); 57 58 /* 59 * Return the idle masks associated to a target @node. 60 * 61 * NUMA_NO_NODE identifies the global idle cpumask. 62 */ 63 static struct scx_idle_cpus *idle_cpumask(int node) 64 { 65 return node == NUMA_NO_NODE ? &scx_idle_global_masks : scx_idle_node_masks[node]; 66 } 67 68 /* 69 * Returns the NUMA node ID associated with a @cpu, or NUMA_NO_NODE if 70 * per-node idle cpumasks are disabled. 71 */ 72 static int scx_cpu_node_if_enabled(int cpu) 73 { 74 if (!static_branch_maybe(CONFIG_NUMA, &scx_builtin_idle_per_node)) 75 return NUMA_NO_NODE; 76 77 return cpu_to_node(cpu); 78 } 79 80 static bool scx_idle_test_and_clear_cpu(int cpu) 81 { 82 int node = scx_cpu_node_if_enabled(cpu); 83 struct cpumask *idle_cpus = idle_cpumask(node)->cpu; 84 85 /* 86 * SMT mask should be cleared whether we can claim @cpu or not. The SMT 87 * cluster is not wholly idle either way. This also prevents 88 * scx_pick_idle_cpu() from getting caught in an infinite loop. 89 */ 90 if (sched_smt_active()) { 91 const struct cpumask *smt = cpu_smt_mask(cpu); 92 struct cpumask *idle_smts = idle_cpumask(node)->smt; 93 94 /* 95 * If offline, @cpu is not its own sibling and 96 * scx_pick_idle_cpu() can get caught in an infinite loop as 97 * @cpu is never cleared from the idle SMT mask. Ensure that 98 * @cpu is eventually cleared. 99 * 100 * NOTE: Use cpumask_intersects() and cpumask_test_cpu() to 101 * reduce memory writes, which may help alleviate cache 102 * coherence pressure. 103 */ 104 if (cpumask_intersects(smt, idle_smts)) 105 cpumask_andnot(idle_smts, idle_smts, smt); 106 else if (cpumask_test_cpu(cpu, idle_smts)) 107 __cpumask_clear_cpu(cpu, idle_smts); 108 } 109 110 return cpumask_test_and_clear_cpu(cpu, idle_cpus); 111 } 112 113 /* 114 * Pick an idle CPU in a specific NUMA node. 115 */ 116 static s32 pick_idle_cpu_in_node(const struct cpumask *cpus_allowed, int node, u64 flags) 117 { 118 int cpu; 119 120 retry: 121 if (sched_smt_active()) { 122 cpu = cpumask_any_and_distribute(idle_cpumask(node)->smt, cpus_allowed); 123 if (cpu < nr_cpu_ids) 124 goto found; 125 126 if (flags & SCX_PICK_IDLE_CORE) 127 return -EBUSY; 128 } 129 130 cpu = cpumask_any_and_distribute(idle_cpumask(node)->cpu, cpus_allowed); 131 if (cpu >= nr_cpu_ids) 132 return -EBUSY; 133 134 found: 135 if (scx_idle_test_and_clear_cpu(cpu)) 136 return cpu; 137 else 138 goto retry; 139 } 140 141 #ifdef CONFIG_NUMA 142 /* 143 * Tracks nodes that have not yet been visited when searching for an idle 144 * CPU across all available nodes. 145 */ 146 static DEFINE_PER_CPU(nodemask_t, per_cpu_unvisited); 147 148 /* 149 * Search for an idle CPU across all nodes, excluding @node. 150 */ 151 static s32 pick_idle_cpu_from_online_nodes(const struct cpumask *cpus_allowed, int node, u64 flags) 152 { 153 nodemask_t *unvisited; 154 s32 cpu = -EBUSY; 155 156 /* 157 * @per_cpu_unvisited is per-CPU scratch and the idle kfuncs can be 158 * called from IRQ-enabled contexts, so mask IRQs to keep a nested 159 * invocation from clobbering the mask an outer invocation is still 160 * iterating. 161 * 162 * NMI nesting is not handled: there is no legitimate reason to call 163 * pick_idle from NMI and doing so poses no crash risk, so such a 164 * caller is on its own. 165 */ 166 guard(irqsave)(); 167 168 unvisited = this_cpu_ptr(&per_cpu_unvisited); 169 170 /* 171 * Restrict the search to the online nodes (excluding the current 172 * node that has been visited already). 173 */ 174 nodes_copy(*unvisited, node_states[N_ONLINE]); 175 node_clear(node, *unvisited); 176 177 /* 178 * Traverse all nodes in order of increasing distance, starting 179 * from @node. 180 * 181 * This loop is O(N^2), with N being the amount of NUMA nodes, 182 * which might be quite expensive in large NUMA systems. However, 183 * this complexity comes into play only when a scheduler enables 184 * SCX_OPS_BUILTIN_IDLE_PER_NODE and it's requesting an idle CPU 185 * without specifying a target NUMA node, so it shouldn't be a 186 * bottleneck is most cases. 187 * 188 * As a future optimization we may want to cache the list of nodes 189 * in a per-node array, instead of actually traversing them every 190 * time. 191 */ 192 for_each_node_numadist(node, *unvisited) { 193 cpu = pick_idle_cpu_in_node(cpus_allowed, node, flags); 194 if (cpu >= 0) 195 break; 196 } 197 198 return cpu; 199 } 200 #else 201 static inline s32 202 pick_idle_cpu_from_online_nodes(const struct cpumask *cpus_allowed, int node, u64 flags) 203 { 204 return -EBUSY; 205 } 206 #endif 207 208 /* 209 * Find an idle CPU in the system, starting from @node. 210 */ 211 static s32 scx_pick_idle_cpu(const struct cpumask *cpus_allowed, int node, u64 flags) 212 { 213 s32 cpu; 214 215 /* 216 * Always search in the starting node first (this is an 217 * optimization that can save some cycles even when the search is 218 * not limited to a single node). 219 */ 220 cpu = pick_idle_cpu_in_node(cpus_allowed, node, flags); 221 if (cpu >= 0) 222 return cpu; 223 224 /* 225 * Stop the search if we are using only a single global cpumask 226 * (NUMA_NO_NODE) or if the search is restricted to the first node 227 * only. 228 */ 229 if (node == NUMA_NO_NODE || flags & SCX_PICK_IDLE_IN_NODE) 230 return -EBUSY; 231 232 /* 233 * Extend the search to the other online nodes. 234 */ 235 return pick_idle_cpu_from_online_nodes(cpus_allowed, node, flags); 236 } 237 238 /* 239 * Return the amount of CPUs in the same LLC domain of @cpu (or zero if the LLC 240 * domain is not defined). 241 */ 242 static unsigned int llc_weight(s32 cpu) 243 { 244 struct sched_domain *sd; 245 246 sd = rcu_dereference(per_cpu(sd_llc, cpu)); 247 if (!sd) 248 return 0; 249 250 return sd->span_weight; 251 } 252 253 /* 254 * Return the cpumask representing the LLC domain of @cpu (or NULL if the LLC 255 * domain is not defined). 256 */ 257 static struct cpumask *llc_span(s32 cpu) 258 { 259 struct sched_domain *sd; 260 261 sd = rcu_dereference(per_cpu(sd_llc, cpu)); 262 if (!sd) 263 return NULL; 264 265 return sched_domain_span(sd); 266 } 267 268 /* 269 * Return the amount of CPUs in the same NUMA domain of @cpu (or zero if the 270 * NUMA domain is not defined). 271 */ 272 static unsigned int numa_weight(s32 cpu) 273 { 274 struct sched_domain *sd; 275 struct sched_group *sg; 276 277 sd = rcu_dereference(per_cpu(sd_numa, cpu)); 278 if (!sd) 279 return 0; 280 sg = sd->groups; 281 if (!sg) 282 return 0; 283 284 return sg->group_weight; 285 } 286 287 /* 288 * Return the cpumask representing the NUMA domain of @cpu (or NULL if the NUMA 289 * domain is not defined). 290 */ 291 static struct cpumask *numa_span(s32 cpu) 292 { 293 struct sched_domain *sd; 294 struct sched_group *sg; 295 296 sd = rcu_dereference(per_cpu(sd_numa, cpu)); 297 if (!sd) 298 return NULL; 299 sg = sd->groups; 300 if (!sg) 301 return NULL; 302 303 return sched_group_span(sg); 304 } 305 306 /* 307 * Return true if the LLC domains do not perfectly overlap with the NUMA 308 * domains, false otherwise. 309 */ 310 static bool llc_numa_mismatch(void) 311 { 312 int cpu; 313 314 /* 315 * We need to scan all online CPUs to verify whether their scheduling 316 * domains overlap. 317 * 318 * While it is rare to encounter architectures with asymmetric NUMA 319 * topologies, CPU hotplugging or virtualized environments can result 320 * in asymmetric configurations. 321 * 322 * For example: 323 * 324 * NUMA 0: 325 * - LLC 0: cpu0..cpu7 326 * - LLC 1: cpu8..cpu15 [offline] 327 * 328 * NUMA 1: 329 * - LLC 0: cpu16..cpu23 330 * - LLC 1: cpu24..cpu31 331 * 332 * In this case, if we only check the first online CPU (cpu0), we might 333 * incorrectly assume that the LLC and NUMA domains are fully 334 * overlapping, which is incorrect (as NUMA 1 has two distinct LLC 335 * domains). 336 */ 337 for_each_online_cpu(cpu) 338 if (llc_weight(cpu) != numa_weight(cpu)) 339 return true; 340 341 return false; 342 } 343 344 /* 345 * Initialize topology-aware scheduling. 346 * 347 * Detect if the system has multiple LLC or multiple NUMA domains and enable 348 * cache-aware / NUMA-aware scheduling optimizations in the default CPU idle 349 * selection policy. 350 * 351 * Assumption: the kernel's internal topology representation assumes that each 352 * CPU belongs to a single LLC domain, and that each LLC domain is entirely 353 * contained within a single NUMA node. 354 */ 355 void scx_idle_update_selcpu_topology(struct sched_ext_ops *ops) 356 { 357 bool enable_llc = false, enable_numa = false; 358 unsigned int nr_cpus; 359 s32 cpu = cpumask_first(cpu_online_mask); 360 361 /* 362 * Enable LLC domain optimization only when there are multiple LLC 363 * domains among the online CPUs. If all online CPUs are part of a 364 * single LLC domain, the idle CPU selection logic can choose any 365 * online CPU without bias. 366 * 367 * Note that it is sufficient to check the LLC domain of the first 368 * online CPU to determine whether a single LLC domain includes all 369 * CPUs. 370 */ 371 rcu_read_lock(); 372 nr_cpus = llc_weight(cpu); 373 if (nr_cpus > 0) { 374 if (nr_cpus < num_online_cpus()) 375 enable_llc = true; 376 pr_debug("sched_ext: LLC=%*pb weight=%u\n", 377 cpumask_pr_args(llc_span(cpu)), llc_weight(cpu)); 378 } 379 380 /* 381 * Enable NUMA optimization only when there are multiple NUMA domains 382 * among the online CPUs and the NUMA domains don't perfectly overlap 383 * with the LLC domains. 384 * 385 * If all CPUs belong to the same NUMA node and the same LLC domain, 386 * enabling both NUMA and LLC optimizations is unnecessary, as checking 387 * for an idle CPU in the same domain twice is redundant. 388 * 389 * If SCX_OPS_BUILTIN_IDLE_PER_NODE is enabled ignore the NUMA 390 * optimization, as we would naturally select idle CPUs within 391 * specific NUMA nodes querying the corresponding per-node cpumask. 392 */ 393 if (!(ops->flags & SCX_OPS_BUILTIN_IDLE_PER_NODE)) { 394 nr_cpus = numa_weight(cpu); 395 if (nr_cpus > 0) { 396 if (nr_cpus < num_online_cpus() && llc_numa_mismatch()) 397 enable_numa = true; 398 pr_debug("sched_ext: NUMA=%*pb weight=%u\n", 399 cpumask_pr_args(numa_span(cpu)), nr_cpus); 400 } 401 } 402 rcu_read_unlock(); 403 404 pr_debug("sched_ext: LLC idle selection %s\n", 405 str_enabled_disabled(enable_llc)); 406 pr_debug("sched_ext: NUMA idle selection %s\n", 407 str_enabled_disabled(enable_numa)); 408 409 if (enable_llc) 410 static_branch_enable_cpuslocked(&scx_selcpu_topo_llc); 411 else 412 static_branch_disable_cpuslocked(&scx_selcpu_topo_llc); 413 if (enable_numa) 414 static_branch_enable_cpuslocked(&scx_selcpu_topo_numa); 415 else 416 static_branch_disable_cpuslocked(&scx_selcpu_topo_numa); 417 } 418 419 /* 420 * Return true if @p can run on all possible CPUs, false otherwise. 421 */ 422 static inline bool task_affinity_all(const struct task_struct *p) 423 { 424 return p->nr_cpus_allowed >= num_possible_cpus(); 425 } 426 427 /* 428 * Built-in CPU idle selection policy: 429 * 430 * 1. Prioritize full-idle cores: 431 * - always prioritize CPUs from fully idle cores (both logical CPUs are 432 * idle) to avoid interference caused by SMT. 433 * 434 * 2. Reuse the same CPU: 435 * - prefer the last used CPU to take advantage of cached data (L1, L2) and 436 * branch prediction optimizations. 437 * 438 * 3. Prefer @prev_cpu's SMT sibling: 439 * - if @prev_cpu is busy and no fully idle core is available, try to 440 * place the task on an idle SMT sibling of @prev_cpu; keeping the 441 * task on the same core makes migration cheaper, preserves L1 cache 442 * locality and reduces wakeup latency. 443 * 444 * 4. Pick a CPU within the same LLC (Last-Level Cache): 445 * - if the above conditions aren't met, pick a CPU that shares the same 446 * LLC, if the LLC domain is a subset of @cpus_allowed, to maintain 447 * cache locality. 448 * 449 * 5. Pick a CPU within the same NUMA node, if enabled: 450 * - choose a CPU from the same NUMA node, if the node cpumask is a 451 * subset of @cpus_allowed, to reduce memory access latency. 452 * 453 * 6. Pick any idle CPU within the @cpus_allowed domain. 454 * 455 * Step 4 and 5 are performed only if the system has, respectively, 456 * multiple LLCs / multiple NUMA nodes (see scx_selcpu_topo_llc and 457 * scx_selcpu_topo_numa) and they don't contain the same subset of CPUs. 458 * 459 * If %SCX_OPS_BUILTIN_IDLE_PER_NODE is enabled, the search will always 460 * begin in @prev_cpu's node and proceed to other nodes in order of 461 * increasing distance. 462 * 463 * Return the picked CPU if idle, or a negative value otherwise. 464 * 465 * NOTE: tasks that can only run on 1 CPU are excluded by this logic, because 466 * we never call ops.select_cpu() for them, see select_task_rq(). 467 */ 468 s32 scx_select_cpu_dfl(struct task_struct *p, s32 prev_cpu, u64 wake_flags, 469 const struct cpumask *cpus_allowed, u64 flags) 470 { 471 const struct cpumask *llc_cpus = NULL, *numa_cpus = NULL; 472 const struct cpumask *allowed = cpus_allowed ?: p->cpus_ptr; 473 int node = scx_cpu_node_if_enabled(prev_cpu); 474 bool is_prev_allowed; 475 s32 cpu; 476 477 preempt_disable(); 478 479 /* 480 * Determine the subset of CPUs usable by @p within @cpus_allowed. 481 */ 482 if (allowed != p->cpus_ptr) { 483 struct cpumask *local_cpus = this_cpu_cpumask_var_ptr(local_idle_cpumask); 484 485 if (task_affinity_all(p)) { 486 allowed = cpus_allowed; 487 } else if (cpumask_and(local_cpus, cpus_allowed, p->cpus_ptr)) { 488 allowed = local_cpus; 489 } else { 490 cpu = -EBUSY; 491 goto out_enable; 492 } 493 } 494 495 /* 496 * Check whether @prev_cpu is still within the allowed set. If not, 497 * we can still try selecting a nearby CPU. 498 */ 499 is_prev_allowed = cpumask_test_cpu(prev_cpu, allowed); 500 501 /* 502 * This is necessary to protect llc_cpus. 503 */ 504 rcu_read_lock(); 505 506 /* 507 * Determine the subset of CPUs that the task can use in its 508 * current LLC and node. 509 * 510 * If the task can run on all CPUs, use the node and LLC cpumasks 511 * directly. 512 */ 513 if (static_branch_maybe(CONFIG_NUMA, &scx_selcpu_topo_numa)) { 514 struct cpumask *local_cpus = this_cpu_cpumask_var_ptr(local_numa_idle_cpumask); 515 const struct cpumask *cpus = numa_span(prev_cpu); 516 517 if (allowed == p->cpus_ptr && task_affinity_all(p)) 518 numa_cpus = cpus; 519 else if (cpus && cpumask_and(local_cpus, allowed, cpus)) 520 numa_cpus = local_cpus; 521 } 522 523 if (static_branch_maybe(CONFIG_SCHED_MC, &scx_selcpu_topo_llc)) { 524 struct cpumask *local_cpus = this_cpu_cpumask_var_ptr(local_llc_idle_cpumask); 525 const struct cpumask *cpus = llc_span(prev_cpu); 526 527 if (allowed == p->cpus_ptr && task_affinity_all(p)) 528 llc_cpus = cpus; 529 else if (cpus && cpumask_and(local_cpus, allowed, cpus)) 530 llc_cpus = local_cpus; 531 } 532 533 /* 534 * If WAKE_SYNC, try to migrate the wakee to the waker's CPU. 535 */ 536 if (wake_flags & SCX_WAKE_SYNC) { 537 int waker_node; 538 539 /* 540 * If the waker's CPU is cache affine and prev_cpu is idle, 541 * then avoid a migration. 542 */ 543 cpu = smp_processor_id(); 544 if (is_prev_allowed && cpus_share_cache(cpu, prev_cpu) && 545 scx_idle_test_and_clear_cpu(prev_cpu)) { 546 cpu = prev_cpu; 547 goto out_unlock; 548 } 549 550 /* 551 * If the waker's local DSQ is empty, and the system is under 552 * utilized, try to wake up @p to the local DSQ of the waker. 553 * 554 * Checking only for an empty local DSQ is insufficient as it 555 * could give the wakee an unfair advantage when the system is 556 * oversaturated. 557 * 558 * Checking only for the presence of idle CPUs is also 559 * insufficient as the local DSQ of the waker could have tasks 560 * piled up on it even if there is an idle core elsewhere on 561 * the system. 562 */ 563 waker_node = scx_cpu_node_if_enabled(cpu); 564 if (!(current->flags & PF_EXITING) && 565 cpu_rq(cpu)->scx.local_dsq.nr == 0 && 566 (!(flags & SCX_PICK_IDLE_IN_NODE) || (waker_node == node)) && 567 !cpumask_empty(idle_cpumask(waker_node)->cpu)) { 568 if (cpumask_test_cpu(cpu, allowed)) { 569 scx_idle_test_and_clear_cpu(cpu); 570 goto out_unlock; 571 } 572 } 573 } 574 575 /* 576 * If CPU has SMT, any wholly idle CPU is likely a better pick than 577 * partially idle @prev_cpu. 578 */ 579 if (sched_smt_active()) { 580 /* 581 * Keep using @prev_cpu if it's part of a fully idle core. 582 */ 583 if (is_prev_allowed && 584 cpumask_test_cpu(prev_cpu, idle_cpumask(node)->smt) && 585 scx_idle_test_and_clear_cpu(prev_cpu)) { 586 cpu = prev_cpu; 587 goto out_unlock; 588 } 589 590 /* 591 * Search for any fully idle core in the same LLC domain. 592 */ 593 if (llc_cpus) { 594 cpu = pick_idle_cpu_in_node(llc_cpus, node, SCX_PICK_IDLE_CORE); 595 if (cpu >= 0) 596 goto out_unlock; 597 } 598 599 /* 600 * Search for any fully idle core in the same NUMA node. 601 */ 602 if (numa_cpus) { 603 cpu = pick_idle_cpu_in_node(numa_cpus, node, SCX_PICK_IDLE_CORE); 604 if (cpu >= 0) 605 goto out_unlock; 606 } 607 608 /* 609 * Search for any full-idle core usable by the task. 610 * 611 * If the node-aware idle CPU selection policy is enabled 612 * (%SCX_OPS_BUILTIN_IDLE_PER_NODE), the search will always 613 * begin in prev_cpu's node and proceed to other nodes in 614 * order of increasing distance. 615 */ 616 cpu = scx_pick_idle_cpu(allowed, node, flags | SCX_PICK_IDLE_CORE); 617 if (cpu >= 0) 618 goto out_unlock; 619 620 /* 621 * Give up if we're strictly looking for a full-idle SMT 622 * core. 623 */ 624 if (flags & SCX_PICK_IDLE_CORE) { 625 cpu = -EBUSY; 626 goto out_unlock; 627 } 628 } 629 630 /* 631 * Use @prev_cpu if it's idle. 632 */ 633 if (is_prev_allowed && scx_idle_test_and_clear_cpu(prev_cpu)) { 634 cpu = prev_cpu; 635 goto out_unlock; 636 } 637 638 /* 639 * Use @prev_cpu's sibling if it's idle. 640 */ 641 if (sched_smt_active()) { 642 for_each_cpu_and(cpu, cpu_smt_mask(prev_cpu), allowed) { 643 if (cpu == prev_cpu) 644 continue; 645 if (scx_idle_test_and_clear_cpu(cpu)) 646 goto out_unlock; 647 } 648 } 649 650 /* 651 * Search for any idle CPU in the same LLC domain. 652 */ 653 if (llc_cpus) { 654 cpu = pick_idle_cpu_in_node(llc_cpus, node, 0); 655 if (cpu >= 0) 656 goto out_unlock; 657 } 658 659 /* 660 * Search for any idle CPU in the same NUMA node. 661 */ 662 if (numa_cpus) { 663 cpu = pick_idle_cpu_in_node(numa_cpus, node, 0); 664 if (cpu >= 0) 665 goto out_unlock; 666 } 667 668 /* 669 * Search for any idle CPU usable by the task. 670 * 671 * If the node-aware idle CPU selection policy is enabled 672 * (%SCX_OPS_BUILTIN_IDLE_PER_NODE), the search will always begin 673 * in prev_cpu's node and proceed to other nodes in order of 674 * increasing distance. 675 */ 676 cpu = scx_pick_idle_cpu(allowed, node, flags); 677 678 out_unlock: 679 rcu_read_unlock(); 680 out_enable: 681 preempt_enable(); 682 683 return cpu; 684 } 685 686 /* 687 * Initialize global and per-node idle cpumasks. 688 */ 689 void scx_idle_init_masks(void) 690 { 691 int i; 692 693 /* Allocate global idle cpumasks */ 694 BUG_ON(!alloc_cpumask_var(&scx_idle_global_masks.cpu, GFP_KERNEL)); 695 BUG_ON(!alloc_cpumask_var(&scx_idle_global_masks.smt, GFP_KERNEL)); 696 697 /* Allocate per-node idle cpumasks (use nr_node_ids for non-contiguous NUMA nodes) */ 698 scx_idle_node_masks = kzalloc_objs(*scx_idle_node_masks, nr_node_ids); 699 BUG_ON(!scx_idle_node_masks); 700 701 for_each_node(i) { 702 scx_idle_node_masks[i] = kzalloc_node(sizeof(**scx_idle_node_masks), 703 GFP_KERNEL, i); 704 BUG_ON(!scx_idle_node_masks[i]); 705 706 BUG_ON(!alloc_cpumask_var_node(&scx_idle_node_masks[i]->cpu, GFP_KERNEL, i)); 707 BUG_ON(!alloc_cpumask_var_node(&scx_idle_node_masks[i]->smt, GFP_KERNEL, i)); 708 } 709 710 /* Allocate local per-cpu idle cpumasks */ 711 for_each_possible_cpu(i) { 712 BUG_ON(!alloc_cpumask_var_node(&per_cpu(local_idle_cpumask, i), 713 GFP_KERNEL, cpu_to_node(i))); 714 BUG_ON(!alloc_cpumask_var_node(&per_cpu(local_llc_idle_cpumask, i), 715 GFP_KERNEL, cpu_to_node(i))); 716 BUG_ON(!alloc_cpumask_var_node(&per_cpu(local_numa_idle_cpumask, i), 717 GFP_KERNEL, cpu_to_node(i))); 718 } 719 } 720 721 static void update_builtin_idle(int cpu, bool idle) 722 { 723 int node = scx_cpu_node_if_enabled(cpu); 724 struct cpumask *idle_cpus = idle_cpumask(node)->cpu; 725 726 assign_cpu(cpu, idle_cpus, idle); 727 728 if (sched_smt_active()) { 729 const struct cpumask *smt = cpu_smt_mask(cpu); 730 struct cpumask *idle_smts = idle_cpumask(node)->smt; 731 732 if (idle) { 733 /* 734 * idle_smt handling is racy but that's fine as it's 735 * only for optimization and self-correcting. 736 */ 737 if (!cpumask_subset(smt, idle_cpus)) 738 return; 739 cpumask_or(idle_smts, idle_smts, smt); 740 } else { 741 cpumask_andnot(idle_smts, idle_smts, smt); 742 } 743 } 744 } 745 746 /* 747 * Notify schedulers of an idle transition on @cpu's cid, delivering to every 748 * sched that holds %SCX_CAP_BASE on the cid (the root holds every cap). A real 749 * transition (@do_notify) reaches all holders. A forced one (@root_renotify for 750 * the root, a sub-sched's idle_renotify marker for a sub) reaches only the owed 751 * scheds. 752 */ 753 static void scx_idle_notify(struct rq *rq, bool idle, bool do_notify, bool root_renotify) 754 { 755 s32 cpu = cpu_of(rq); 756 s32 cid = scx_cpu_arg(cpu); 757 struct scx_sched *root = scx_root_protected_live(); 758 struct scx_sched *pos; 759 760 lockdep_assert_rq_held(rq); 761 762 /* with no sub-sched, only the root can be owed a notification */ 763 if (!scx_has_subs()) { 764 if ((do_notify || root_renotify) && 765 SCX_HAS_OP(root, update_idle) && !scx_bypassing(root, cpu)) 766 SCX_CALL_OP(root, update_idle, rq, cid, idle); 767 return; 768 } 769 770 pos = scx_next_descendant_pre(NULL, root); 771 while (pos) { 772 bool forced = false; 773 774 if (unlikely(scx_missing_caps(pos, cpu, SCX_CAP_BASE))) { 775 pos = scx_skip_subtree_pre(pos, root); 776 continue; 777 } 778 779 if (!pos->level) { 780 forced = root_renotify; 781 } 782 #ifdef CONFIG_EXT_SUB_SCHED 783 else if (per_cpu_ptr(pos->pcpu, cpu)->idle_renotify) { 784 per_cpu_ptr(pos->pcpu, cpu)->idle_renotify = false; 785 forced = true; 786 } 787 #endif 788 if ((do_notify || forced) && SCX_HAS_OP(pos, update_idle) && 789 !scx_bypassing(pos, cpu)) 790 SCX_CALL_OP(pos, update_idle, rq, cid, idle); 791 pos = scx_next_descendant_pre(pos, root); 792 } 793 } 794 795 /* 796 * Update the idle state of a CPU to @idle. 797 * 798 * If @do_notify is true, ops.update_idle() is invoked to notify the scx 799 * scheduler of an actual idle state transition (idle to busy or vice 800 * versa). If @do_notify is false, only the idle state in the idle masks is 801 * refreshed without invoking ops.update_idle(). 802 * 803 * This distinction is necessary, because an idle CPU can be "reserved" and 804 * awakened via scx_bpf_pick_idle_cpu() + scx_bpf_kick_cpu(), marking it as 805 * busy even if no tasks are dispatched. In this case, the CPU may return 806 * to idle without a true state transition. Refreshing the idle masks 807 * without invoking ops.update_idle() ensures accurate idle state tracking 808 * while avoiding unnecessary updates and maintaining balanced state 809 * transitions. 810 */ 811 void __scx_update_idle(struct rq *rq, bool idle, bool do_notify) 812 { 813 int cpu = cpu_of(rq); 814 815 lockdep_assert_rq_held(rq); 816 817 /* 818 * pick_task_idle() calls here only on an idle-to-idle re-pick and the 819 * transitions call with @do_notify, so every reaching call updates the 820 * masks. 821 */ 822 if (static_branch_likely(&scx_builtin_idle_enabled)) 823 update_builtin_idle(cpu, idle); 824 825 /* 826 * ops.update_idle() fires on real idle transitions, indicated by 827 * @do_notify and managed by put_prev_task_idle()/set_next_task_idle(). 828 * An idle pick also fires it to flush a forced notify owed to a sched 829 * that missed transitions while bypassed or on a cid it just gained. 830 * unbypass_renotify_idle() and scx_process_sync_ecaps() arm the per-rq 831 * gates, and scx_idle_notify() targets the owed scheds. 832 * 833 * This must come after the builtin idle update so that BPF schedulers 834 * can create interlocking between ops.update_idle() and ops.enqueue() - 835 * either enqueue() sees the idle bit or update_idle() sees the task 836 * that enqueue() queued. 837 */ 838 if (do_notify || 839 (idle && (rq->scx.flags & 840 (SCX_RQ_SUB_IDLE_RENOTIFY | SCX_RQ_ROOT_IDLE_RENOTIFY)))) { 841 bool root_renotify = rq->scx.flags & SCX_RQ_ROOT_IDLE_RENOTIFY; 842 843 rq->scx.flags &= ~(SCX_RQ_SUB_IDLE_RENOTIFY | SCX_RQ_ROOT_IDLE_RENOTIFY); 844 scx_idle_notify(rq, idle, do_notify, root_renotify); 845 } 846 } 847 848 static void reset_idle_masks(struct sched_ext_ops *ops) 849 { 850 int node; 851 852 /* 853 * Start with all CPUs marked busy. The idle masks are populated when 854 * bypass is lifted and each idle CPU is forced through an idle re-pick. 855 * This may temporarily omit idle CPUs but never advertises a busy CPU as 856 * idle. 857 */ 858 if (!(ops->flags & SCX_OPS_BUILTIN_IDLE_PER_NODE)) { 859 cpumask_clear(idle_cpumask(NUMA_NO_NODE)->cpu); 860 cpumask_clear(idle_cpumask(NUMA_NO_NODE)->smt); 861 return; 862 } 863 864 for_each_node(node) { 865 cpumask_clear(idle_cpumask(node)->cpu); 866 cpumask_clear(idle_cpumask(node)->smt); 867 } 868 } 869 870 void scx_idle_enable(struct sched_ext_ops *ops) 871 { 872 if (!ops->update_idle || (ops->flags & SCX_OPS_KEEP_BUILTIN_IDLE)) 873 static_branch_enable_cpuslocked(&scx_builtin_idle_enabled); 874 else 875 static_branch_disable_cpuslocked(&scx_builtin_idle_enabled); 876 877 if (ops->flags & SCX_OPS_BUILTIN_IDLE_PER_NODE) 878 static_branch_enable_cpuslocked(&scx_builtin_idle_per_node); 879 else 880 static_branch_disable_cpuslocked(&scx_builtin_idle_per_node); 881 882 reset_idle_masks(ops); 883 } 884 885 void scx_idle_disable(void) 886 { 887 static_branch_disable(&scx_builtin_idle_enabled); 888 static_branch_disable(&scx_builtin_idle_per_node); 889 } 890 891 /******************************************************************************** 892 * Helpers that can be called from the BPF scheduler. 893 */ 894 895 static int validate_node(struct scx_sched *sch, int node) 896 { 897 if (!static_branch_likely(&scx_builtin_idle_per_node)) { 898 scx_error(sch, "per-node idle tracking is disabled"); 899 return -EOPNOTSUPP; 900 } 901 902 /* Return no entry for NUMA_NO_NODE (not a critical scx error) */ 903 if (node == NUMA_NO_NODE) 904 return -ENOENT; 905 906 /* Make sure node is in a valid range */ 907 if (node < 0 || node >= nr_node_ids) { 908 scx_error(sch, "invalid node %d", node); 909 return -EINVAL; 910 } 911 912 /* Make sure the node is part of the set of possible nodes */ 913 if (!node_possible(node)) { 914 scx_error(sch, "unavailable node %d", node); 915 return -EINVAL; 916 } 917 918 return node; 919 } 920 921 __bpf_kfunc_start_defs(); 922 923 static bool check_builtin_idle_enabled(struct scx_sched *sch) 924 { 925 if (static_branch_likely(&scx_builtin_idle_enabled)) 926 return true; 927 928 scx_error(sch, "built-in idle tracking is disabled"); 929 return false; 930 } 931 932 /* 933 * Determine whether @p is a migration-disabled task in the context of BPF 934 * code. 935 * 936 * We can't simply check whether @p->migration_disabled is set in a 937 * sched_ext callback, because the BPF prolog (__bpf_prog_enter) may disable 938 * migration for the current task while running BPF code. 939 * 940 * Since the BPF prolog calls migrate_disable() only when CONFIG_PREEMPT_RCU 941 * is enabled (via rcu_read_lock_dont_migrate()), migration_disabled == 1 for 942 * the current task is ambiguous only in that case: it could be from the BPF 943 * prolog rather than a real migrate_disable() call. 944 * 945 * Without CONFIG_PREEMPT_RCU, the BPF prolog never calls migrate_disable(), 946 * so migration_disabled == 1 always means the task is truly 947 * migration-disabled. 948 * 949 * Therefore, when migration_disabled == 1 and CONFIG_PREEMPT_RCU is enabled, 950 * check whether @p is the current task or not: if it is, then migration was 951 * not disabled before entering the callback, otherwise migration was disabled. 952 * 953 * Returns true if @p is migration-disabled, false otherwise. 954 */ 955 static bool is_bpf_migration_disabled(const struct task_struct *p) 956 { 957 if (p->migration_disabled == 1) { 958 if (IS_ENABLED(CONFIG_PREEMPT_RCU)) 959 return p != current; 960 return true; 961 } 962 return p->migration_disabled; 963 } 964 965 static s32 select_cpu_restricted(struct task_struct *p, s32 prev_cpu, 966 const struct cpumask *allowed, u64 flags, 967 bool migration_disabled) 968 { 969 s32 cpu; 970 971 if (migration_disabled) 972 cpu = task_cpu(p); 973 else 974 cpu = cpumask_first(p->cpus_ptr); 975 976 if (!cpumask_test_cpu(cpu, p->cpus_ptr)) 977 return -EBUSY; 978 979 if (allowed && !cpumask_test_cpu(cpu, allowed)) 980 return -EBUSY; 981 982 if (flags & SCX_PICK_IDLE_IN_NODE) { 983 int node = scx_cpu_node_if_enabled(prev_cpu); 984 985 if (scx_cpu_node_if_enabled(cpu) != node) 986 return -EBUSY; 987 } 988 989 if (!scx_idle_test_and_clear_cpu(cpu)) 990 return -EBUSY; 991 992 return cpu; 993 } 994 995 static s32 select_cpu_from_kfunc(struct scx_sched *sch, struct task_struct *p, 996 s32 prev_cpu, u64 wake_flags, 997 const struct cpumask *allowed, u64 flags) 998 { 999 unsigned long irq_flags; 1000 bool we_locked = false; 1001 bool migration_disabled; 1002 s32 cpu; 1003 1004 if (!scx_cpu_valid(sch, prev_cpu, NULL)) 1005 return -EINVAL; 1006 1007 if (!check_builtin_idle_enabled(sch)) 1008 return -EBUSY; 1009 1010 /* 1011 * Accessing p->cpus_ptr / p->nr_cpus_allowed needs either @p's rq 1012 * lock or @p's pi_lock. Three cases: 1013 * 1014 * - inside ops.select_cpu(): try_to_wake_up() holds the wake-up 1015 * task's pi_lock; the wake-up task is recorded in kf_tasks[0] 1016 * by SCX_CALL_OP_TASK_RET(). 1017 * - other rq-locked SCX op: scx_locked_rq() points at the held rq. 1018 * - truly unlocked (UNLOCKED ops, SYSCALL, non-SCX struct_ops): 1019 * nothing held, take pi_lock ourselves. 1020 * 1021 * In the first two cases, BPF schedulers may pass an arbitrary task 1022 * that the held lock doesn't cover. Refuse those. 1023 */ 1024 if (this_rq()->scx.in_select_cpu) { 1025 if (!scx_kf_arg_task_ok(sch, p)) 1026 return -EINVAL; 1027 lockdep_assert_held(&p->pi_lock); 1028 } else if (scx_locked_rq()) { 1029 if (task_rq(p) != scx_locked_rq()) 1030 goto cross_task; 1031 } else { 1032 raw_spin_lock_irqsave(&p->pi_lock, irq_flags); 1033 we_locked = true; 1034 } 1035 1036 /* 1037 * This may also be called from ops.enqueue(), so we need to handle 1038 * per-CPU tasks as well. For these tasks, skip general idle CPU 1039 * selection and validate the task's only usable CPU directly. 1040 */ 1041 migration_disabled = is_bpf_migration_disabled(p); 1042 1043 if (p->nr_cpus_allowed == 1 || migration_disabled) 1044 cpu = select_cpu_restricted(p, prev_cpu, allowed, flags, 1045 migration_disabled); 1046 else 1047 cpu = scx_select_cpu_dfl(p, prev_cpu, wake_flags, 1048 allowed ?: p->cpus_ptr, flags); 1049 1050 if (we_locked) 1051 raw_spin_unlock_irqrestore(&p->pi_lock, irq_flags); 1052 1053 return cpu; 1054 1055 cross_task: 1056 scx_error(sch, "select_cpu kfunc called cross-task on %s[%d]", 1057 p->comm, p->pid); 1058 return -EINVAL; 1059 } 1060 1061 /** 1062 * scx_bpf_cpu_node - Return the NUMA node the given @cpu belongs to, or 1063 * trigger an error if @cpu is invalid 1064 * @cpu: target CPU 1065 * @aux: implicit BPF argument to access bpf_prog_aux hidden from BPF progs 1066 */ 1067 __bpf_kfunc s32 scx_bpf_cpu_node(s32 cpu, const struct bpf_prog_aux *aux) 1068 { 1069 struct scx_sched *sch; 1070 1071 guard(rcu)(); 1072 1073 sch = scx_prog_sched(aux); 1074 if (unlikely(!sch) || !scx_cpu_valid(sch, cpu, NULL)) 1075 return NUMA_NO_NODE; 1076 return cpu_to_node(cpu); 1077 } 1078 1079 /** 1080 * scx_bpf_select_cpu_dfl - The default implementation of ops.select_cpu() 1081 * @p: task_struct to select a CPU for 1082 * @prev_cpu: CPU @p was on previously 1083 * @wake_flags: %SCX_WAKE_* flags 1084 * @is_idle: out parameter indicating whether the returned CPU is idle 1085 * @aux: implicit BPF argument to access bpf_prog_aux hidden from BPF progs 1086 * 1087 * Can be called from ops.select_cpu(), ops.enqueue(), or from an unlocked 1088 * context such as a BPF test_run() call, as long as built-in CPU selection 1089 * is enabled: ops.update_idle() is missing or %SCX_OPS_KEEP_BUILTIN_IDLE 1090 * is set. 1091 * 1092 * Returns the picked CPU with *@is_idle indicating whether the picked CPU is 1093 * currently idle and thus a good candidate for direct dispatching. 1094 */ 1095 __bpf_kfunc s32 scx_bpf_select_cpu_dfl(struct task_struct *p, s32 prev_cpu, 1096 u64 wake_flags, bool *is_idle, 1097 const struct bpf_prog_aux *aux) 1098 { 1099 struct scx_sched *sch; 1100 s32 cpu; 1101 1102 guard(rcu)(); 1103 1104 sch = scx_prog_sched(aux); 1105 if (unlikely(!sch)) 1106 return -ENODEV; 1107 1108 cpu = select_cpu_from_kfunc(sch, p, prev_cpu, wake_flags, NULL, 0); 1109 if (cpu >= 0) { 1110 *is_idle = true; 1111 return cpu; 1112 } 1113 *is_idle = false; 1114 return prev_cpu; 1115 } 1116 1117 struct scx_bpf_select_cpu_and_args { 1118 /* @p and @cpus_allowed can't be packed together as KF_RCU is not transitive */ 1119 s32 prev_cpu; 1120 u64 wake_flags; 1121 u64 flags; 1122 }; 1123 1124 /** 1125 * __scx_bpf_select_cpu_and - Arg-wrapped CPU selection with cpumask 1126 * @p: task_struct to select a CPU for 1127 * @cpus_allowed: cpumask of allowed CPUs 1128 * @args: struct containing the rest of the arguments 1129 * @args->prev_cpu: CPU @p was on previously 1130 * @args->wake_flags: %SCX_WAKE_* flags 1131 * @args->flags: %SCX_PICK_IDLE* flags 1132 * @aux: implicit BPF argument to access bpf_prog_aux hidden from BPF progs 1133 * 1134 * Wrapper kfunc that takes arguments via struct to work around BPF's 5 argument 1135 * limit. BPF programs should use scx_bpf_select_cpu_and() which is provided 1136 * as an inline wrapper in common.bpf.h. 1137 * 1138 * Can be called from ops.select_cpu(), ops.enqueue(), or from an unlocked 1139 * context such as a BPF test_run() call, as long as built-in CPU selection 1140 * is enabled: ops.update_idle() is missing or %SCX_OPS_KEEP_BUILTIN_IDLE 1141 * is set. 1142 * 1143 * @p, @args->prev_cpu and @args->wake_flags match ops.select_cpu(). 1144 * 1145 * Returns the selected idle CPU, which will be automatically awakened upon 1146 * returning from ops.select_cpu() and can be used for direct dispatch, or 1147 * a negative value if no idle CPU is available. 1148 */ 1149 __bpf_kfunc s32 1150 __scx_bpf_select_cpu_and(struct task_struct *p, const struct cpumask *cpus_allowed, 1151 struct scx_bpf_select_cpu_and_args *args, 1152 const struct bpf_prog_aux *aux) 1153 { 1154 struct scx_sched *sch; 1155 1156 guard(rcu)(); 1157 1158 sch = scx_prog_sched(aux); 1159 if (unlikely(!sch)) 1160 return -ENODEV; 1161 1162 return select_cpu_from_kfunc(sch, p, args->prev_cpu, args->wake_flags, 1163 cpus_allowed, args->flags); 1164 } 1165 1166 /* 1167 * COMPAT: Will be removed in v6.22. 1168 */ 1169 __bpf_kfunc s32 scx_bpf_select_cpu_and(struct task_struct *p, s32 prev_cpu, u64 wake_flags, 1170 const struct cpumask *cpus_allowed, u64 flags) 1171 { 1172 struct scx_sched *sch; 1173 1174 guard(rcu)(); 1175 1176 sch = rcu_dereference(scx_root); 1177 if (unlikely(!sch)) 1178 return -ENODEV; 1179 1180 #ifdef CONFIG_EXT_SUB_SCHED 1181 /* 1182 * Disallow if any sub-scheds are attached. There is no way to tell 1183 * which scheduler called us, so error out @p's scheduler -- read it 1184 * under RCU as @p's locks aren't necessarily held here. @p may be a 1185 * task past sched_ext_dead() or an idle task, in which case its 1186 * scheduler can't be determined and there is nothing obviously wrong 1187 * to report; just refuse the call. 1188 */ 1189 if (unlikely(!list_empty(&sch->children))) { 1190 struct scx_sched *tsch = scx_task_sched_rcu(p); 1191 1192 if (tsch) 1193 scx_error(tsch, "__scx_bpf_select_cpu_and() must be used"); 1194 return -EINVAL; 1195 } 1196 #endif 1197 1198 return select_cpu_from_kfunc(sch, p, prev_cpu, wake_flags, 1199 cpus_allowed, flags); 1200 } 1201 1202 /** 1203 * scx_bpf_get_idle_cpumask_node - Get a referenced kptr to the 1204 * idle-tracking per-CPU cpumask of a target NUMA node. 1205 * @node: target NUMA node 1206 * @aux: implicit BPF argument to access bpf_prog_aux hidden from BPF progs 1207 * 1208 * Returns an empty cpumask if idle tracking is not enabled, if @node is 1209 * not valid, or running on a UP kernel. In this case the actual error will 1210 * be reported to the BPF scheduler via scx_error(). 1211 */ 1212 __bpf_kfunc const struct cpumask * 1213 scx_bpf_get_idle_cpumask_node(s32 node, const struct bpf_prog_aux *aux) 1214 { 1215 struct scx_sched *sch; 1216 1217 guard(rcu)(); 1218 1219 sch = scx_prog_sched(aux); 1220 if (unlikely(!sch)) 1221 return cpu_none_mask; 1222 1223 node = validate_node(sch, node); 1224 if (node < 0) 1225 return cpu_none_mask; 1226 1227 return idle_cpumask(node)->cpu; 1228 } 1229 1230 /** 1231 * scx_bpf_get_idle_cpumask - Get a referenced kptr to the idle-tracking 1232 * per-CPU cpumask. 1233 * @aux: implicit BPF argument to access bpf_prog_aux hidden from BPF progs 1234 * 1235 * Returns an empty mask if idle tracking is not enabled, or running on a 1236 * UP kernel. 1237 */ 1238 __bpf_kfunc const struct cpumask *scx_bpf_get_idle_cpumask(const struct bpf_prog_aux *aux) 1239 { 1240 struct scx_sched *sch; 1241 1242 guard(rcu)(); 1243 1244 sch = scx_prog_sched(aux); 1245 if (unlikely(!sch)) 1246 return cpu_none_mask; 1247 1248 if (static_branch_unlikely(&scx_builtin_idle_per_node)) { 1249 scx_error(sch, "SCX_OPS_BUILTIN_IDLE_PER_NODE enabled"); 1250 return cpu_none_mask; 1251 } 1252 1253 if (!check_builtin_idle_enabled(sch)) 1254 return cpu_none_mask; 1255 1256 return idle_cpumask(NUMA_NO_NODE)->cpu; 1257 } 1258 1259 /** 1260 * scx_bpf_get_idle_smtmask_node - Get a referenced kptr to the 1261 * idle-tracking, per-physical-core cpumask of a target NUMA node. Can be 1262 * used to determine if an entire physical core is free. 1263 * @node: target NUMA node 1264 * @aux: implicit BPF argument to access bpf_prog_aux hidden from BPF progs 1265 * 1266 * Returns an empty cpumask if idle tracking is not enabled, if @node is 1267 * not valid, or running on a UP kernel. In this case the actual error will 1268 * be reported to the BPF scheduler via scx_error(). 1269 */ 1270 __bpf_kfunc const struct cpumask * 1271 scx_bpf_get_idle_smtmask_node(s32 node, const struct bpf_prog_aux *aux) 1272 { 1273 struct scx_sched *sch; 1274 1275 guard(rcu)(); 1276 1277 sch = scx_prog_sched(aux); 1278 if (unlikely(!sch)) 1279 return cpu_none_mask; 1280 1281 node = validate_node(sch, node); 1282 if (node < 0) 1283 return cpu_none_mask; 1284 1285 if (sched_smt_active()) 1286 return idle_cpumask(node)->smt; 1287 else 1288 return idle_cpumask(node)->cpu; 1289 } 1290 1291 /** 1292 * scx_bpf_get_idle_smtmask - Get a referenced kptr to the idle-tracking, 1293 * per-physical-core cpumask. Can be used to determine if an entire physical 1294 * core is free. 1295 * @aux: implicit BPF argument to access bpf_prog_aux hidden from BPF progs 1296 * 1297 * Returns an empty mask if idle tracking is not enabled, or running on a 1298 * UP kernel. 1299 */ 1300 __bpf_kfunc const struct cpumask *scx_bpf_get_idle_smtmask(const struct bpf_prog_aux *aux) 1301 { 1302 struct scx_sched *sch; 1303 1304 guard(rcu)(); 1305 1306 sch = scx_prog_sched(aux); 1307 if (unlikely(!sch)) 1308 return cpu_none_mask; 1309 1310 if (static_branch_unlikely(&scx_builtin_idle_per_node)) { 1311 scx_error(sch, "SCX_OPS_BUILTIN_IDLE_PER_NODE enabled"); 1312 return cpu_none_mask; 1313 } 1314 1315 if (!check_builtin_idle_enabled(sch)) 1316 return cpu_none_mask; 1317 1318 if (sched_smt_active()) 1319 return idle_cpumask(NUMA_NO_NODE)->smt; 1320 else 1321 return idle_cpumask(NUMA_NO_NODE)->cpu; 1322 } 1323 1324 /** 1325 * scx_bpf_put_idle_cpumask - Release a previously acquired referenced kptr to 1326 * either the percpu, or SMT idle-tracking cpumask. 1327 * @idle_mask: &cpumask to use 1328 */ 1329 __bpf_kfunc void scx_bpf_put_idle_cpumask(const struct cpumask *idle_mask) 1330 { 1331 /* 1332 * Empty function body because we aren't actually acquiring or releasing 1333 * a reference to a global idle cpumask, which is read-only in the 1334 * caller and is never released. The acquire / release semantics here 1335 * are just used to make the cpumask a trusted pointer in the caller. 1336 */ 1337 } 1338 1339 /** 1340 * scx_bpf_test_and_clear_cpu_idle - Test and clear @cpu's idle state 1341 * @cpu: cpu to test and clear idle for 1342 * @aux: implicit BPF argument to access bpf_prog_aux hidden from BPF progs 1343 * 1344 * Returns %true if @cpu was idle and its idle state was successfully cleared. 1345 * %false otherwise. 1346 * 1347 * Unavailable if ops.update_idle() is implemented and 1348 * %SCX_OPS_KEEP_BUILTIN_IDLE is not set. 1349 */ 1350 __bpf_kfunc bool scx_bpf_test_and_clear_cpu_idle(s32 cpu, const struct bpf_prog_aux *aux) 1351 { 1352 struct scx_sched *sch; 1353 1354 guard(rcu)(); 1355 1356 sch = scx_prog_sched(aux); 1357 if (unlikely(!sch)) 1358 return false; 1359 1360 if (!check_builtin_idle_enabled(sch)) 1361 return false; 1362 1363 if (!scx_cpu_valid(sch, cpu, NULL)) 1364 return false; 1365 1366 return scx_idle_test_and_clear_cpu(cpu); 1367 } 1368 1369 /** 1370 * scx_bpf_pick_idle_cpu_node - Pick and claim an idle cpu from @node 1371 * @cpus_allowed: Allowed cpumask 1372 * @node: target NUMA node 1373 * @flags: %SCX_PICK_IDLE_* flags 1374 * @aux: implicit BPF argument to access bpf_prog_aux hidden from BPF progs 1375 * 1376 * Pick and claim an idle cpu in @cpus_allowed from the NUMA node @node. 1377 * 1378 * Returns the picked idle cpu number on success, or -%EBUSY if no matching 1379 * cpu was found. 1380 * 1381 * The search starts from @node and proceeds to other online NUMA nodes in 1382 * order of increasing distance (unless SCX_PICK_IDLE_IN_NODE is specified, 1383 * in which case the search is limited to the target @node). 1384 * 1385 * Always returns an error if ops.update_idle() is implemented and 1386 * %SCX_OPS_KEEP_BUILTIN_IDLE is not set, or if 1387 * %SCX_OPS_BUILTIN_IDLE_PER_NODE is not set. 1388 */ 1389 __bpf_kfunc s32 scx_bpf_pick_idle_cpu_node(const struct cpumask *cpus_allowed, 1390 s32 node, u64 flags, 1391 const struct bpf_prog_aux *aux) 1392 { 1393 struct scx_sched *sch; 1394 1395 guard(rcu)(); 1396 1397 sch = scx_prog_sched(aux); 1398 if (unlikely(!sch)) 1399 return -ENODEV; 1400 1401 node = validate_node(sch, node); 1402 if (node < 0) 1403 return node; 1404 1405 return scx_pick_idle_cpu(cpus_allowed, node, flags); 1406 } 1407 1408 /** 1409 * scx_bpf_pick_idle_cpu - Pick and claim an idle cpu 1410 * @cpus_allowed: Allowed cpumask 1411 * @flags: %SCX_PICK_IDLE_* flags 1412 * @aux: implicit BPF argument to access bpf_prog_aux hidden from BPF progs 1413 * 1414 * Pick and claim an idle cpu in @cpus_allowed. Returns the picked idle cpu 1415 * number on success. -%EBUSY if no matching cpu was found. 1416 * 1417 * Idle CPU tracking may race against CPU scheduling state transitions. For 1418 * example, this function may return -%EBUSY as CPUs are transitioning into the 1419 * idle state. If the caller then assumes that there will be dispatch events on 1420 * the CPUs as they were all busy, the scheduler may end up stalling with CPUs 1421 * idling while there are pending tasks. Use scx_bpf_pick_any_cpu() and 1422 * scx_bpf_kick_cpu() to guarantee that there will be at least one dispatch 1423 * event in the near future. 1424 * 1425 * Unavailable if ops.update_idle() is implemented and 1426 * %SCX_OPS_KEEP_BUILTIN_IDLE is not set. 1427 * 1428 * Always returns an error if %SCX_OPS_BUILTIN_IDLE_PER_NODE is set, use 1429 * scx_bpf_pick_idle_cpu_node() instead. 1430 */ 1431 __bpf_kfunc s32 scx_bpf_pick_idle_cpu(const struct cpumask *cpus_allowed, 1432 u64 flags, const struct bpf_prog_aux *aux) 1433 { 1434 struct scx_sched *sch; 1435 1436 guard(rcu)(); 1437 1438 sch = scx_prog_sched(aux); 1439 if (unlikely(!sch)) 1440 return -ENODEV; 1441 1442 if (static_branch_maybe(CONFIG_NUMA, &scx_builtin_idle_per_node)) { 1443 scx_error(sch, "per-node idle tracking is enabled"); 1444 return -EBUSY; 1445 } 1446 1447 if (!check_builtin_idle_enabled(sch)) 1448 return -EBUSY; 1449 1450 return scx_pick_idle_cpu(cpus_allowed, NUMA_NO_NODE, flags); 1451 } 1452 1453 /** 1454 * scx_bpf_pick_any_cpu_node - Pick and claim an idle cpu if available 1455 * or pick any CPU from @node 1456 * @cpus_allowed: Allowed cpumask 1457 * @node: target NUMA node 1458 * @flags: %SCX_PICK_IDLE_* flags 1459 * @aux: implicit BPF argument to access bpf_prog_aux hidden from BPF progs 1460 * 1461 * Pick and claim an idle cpu in @cpus_allowed. If none is available, pick any 1462 * CPU in @cpus_allowed. Guaranteed to succeed and returns the picked idle cpu 1463 * number if @cpus_allowed is not empty. -%EBUSY is returned if @cpus_allowed is 1464 * empty. 1465 * 1466 * The search starts from @node and proceeds to other online NUMA nodes in 1467 * order of increasing distance (unless %SCX_PICK_IDLE_IN_NODE is specified, 1468 * in which case the search is limited to the target @node, regardless of 1469 * the CPU idle state). 1470 * 1471 * If ops.update_idle() is implemented and %SCX_OPS_KEEP_BUILTIN_IDLE is not 1472 * set, this function can't tell which CPUs are idle and will always pick any 1473 * CPU. 1474 */ 1475 __bpf_kfunc s32 scx_bpf_pick_any_cpu_node(const struct cpumask *cpus_allowed, 1476 s32 node, u64 flags, 1477 const struct bpf_prog_aux *aux) 1478 { 1479 struct scx_sched *sch; 1480 s32 cpu; 1481 1482 guard(rcu)(); 1483 1484 sch = scx_prog_sched(aux); 1485 if (unlikely(!sch)) 1486 return -ENODEV; 1487 1488 node = validate_node(sch, node); 1489 if (node < 0) 1490 return node; 1491 1492 cpu = scx_pick_idle_cpu(cpus_allowed, node, flags); 1493 if (cpu >= 0) 1494 return cpu; 1495 1496 if (flags & SCX_PICK_IDLE_IN_NODE) 1497 cpu = cpumask_any_and_distribute(cpumask_of_node(node), cpus_allowed); 1498 else 1499 cpu = cpumask_any_distribute(cpus_allowed); 1500 if (cpu < nr_cpu_ids) 1501 return cpu; 1502 else 1503 return -EBUSY; 1504 } 1505 1506 /** 1507 * scx_bpf_pick_any_cpu - Pick and claim an idle cpu if available or pick any CPU 1508 * @cpus_allowed: Allowed cpumask 1509 * @flags: %SCX_PICK_IDLE_* flags 1510 * @aux: implicit BPF argument to access bpf_prog_aux hidden from BPF progs 1511 * 1512 * Pick and claim an idle cpu in @cpus_allowed. If none is available, pick any 1513 * CPU in @cpus_allowed. Guaranteed to succeed and returns the picked idle cpu 1514 * number if @cpus_allowed is not empty. -%EBUSY is returned if @cpus_allowed is 1515 * empty. 1516 * 1517 * If ops.update_idle() is implemented and %SCX_OPS_KEEP_BUILTIN_IDLE is not 1518 * set, this function can't tell which CPUs are idle and will always pick any 1519 * CPU. 1520 * 1521 * Always returns an error if %SCX_OPS_BUILTIN_IDLE_PER_NODE is set, use 1522 * scx_bpf_pick_any_cpu_node() instead. 1523 */ 1524 __bpf_kfunc s32 scx_bpf_pick_any_cpu(const struct cpumask *cpus_allowed, 1525 u64 flags, const struct bpf_prog_aux *aux) 1526 { 1527 struct scx_sched *sch; 1528 s32 cpu; 1529 1530 guard(rcu)(); 1531 1532 sch = scx_prog_sched(aux); 1533 if (unlikely(!sch)) 1534 return -ENODEV; 1535 1536 if (static_branch_maybe(CONFIG_NUMA, &scx_builtin_idle_per_node)) { 1537 scx_error(sch, "per-node idle tracking is enabled"); 1538 return -EBUSY; 1539 } 1540 1541 if (static_branch_likely(&scx_builtin_idle_enabled)) { 1542 cpu = scx_pick_idle_cpu(cpus_allowed, NUMA_NO_NODE, flags); 1543 if (cpu >= 0) 1544 return cpu; 1545 } 1546 1547 cpu = cpumask_any_distribute(cpus_allowed); 1548 if (cpu < nr_cpu_ids) 1549 return cpu; 1550 else 1551 return -EBUSY; 1552 } 1553 1554 __bpf_kfunc_end_defs(); 1555 1556 BTF_KFUNCS_START(scx_kfunc_ids_idle) 1557 BTF_ID_FLAGS(func, scx_bpf_cpu_node, KF_IMPLICIT_ARGS) 1558 BTF_ID_FLAGS(func, scx_bpf_get_idle_cpumask_node, KF_IMPLICIT_ARGS | KF_ACQUIRE) 1559 BTF_ID_FLAGS(func, scx_bpf_get_idle_cpumask, KF_IMPLICIT_ARGS | KF_ACQUIRE) 1560 BTF_ID_FLAGS(func, scx_bpf_get_idle_smtmask_node, KF_IMPLICIT_ARGS | KF_ACQUIRE) 1561 BTF_ID_FLAGS(func, scx_bpf_get_idle_smtmask, KF_IMPLICIT_ARGS | KF_ACQUIRE) 1562 BTF_ID_FLAGS(func, scx_bpf_put_idle_cpumask, KF_RELEASE) 1563 BTF_ID_FLAGS(func, scx_bpf_test_and_clear_cpu_idle, KF_IMPLICIT_ARGS) 1564 BTF_ID_FLAGS(func, scx_bpf_pick_idle_cpu_node, KF_IMPLICIT_ARGS | KF_RCU) 1565 BTF_ID_FLAGS(func, scx_bpf_pick_idle_cpu, KF_IMPLICIT_ARGS | KF_RCU) 1566 BTF_ID_FLAGS(func, scx_bpf_pick_any_cpu_node, KF_IMPLICIT_ARGS | KF_RCU) 1567 BTF_ID_FLAGS(func, scx_bpf_pick_any_cpu, KF_IMPLICIT_ARGS | KF_RCU) 1568 BTF_KFUNCS_END(scx_kfunc_ids_idle) 1569 1570 static const struct btf_kfunc_id_set scx_kfunc_set_idle = { 1571 .owner = THIS_MODULE, 1572 .set = &scx_kfunc_ids_idle, 1573 .filter = scx_kfunc_context_filter, 1574 }; 1575 1576 /* 1577 * The select_cpu kfuncs internally call task_rq_lock() when invoked from an 1578 * rq-unlocked context, and thus cannot be safely called from arbitrary tracing 1579 * contexts where @p's pi_lock state is unknown. Keep them out of 1580 * BPF_PROG_TYPE_TRACING by registering them in their own set which is exposed 1581 * only to STRUCT_OPS and SYSCALL programs. 1582 * 1583 * These kfuncs are also members of scx_kfunc_ids_unlocked (see ext.c) because 1584 * they're callable from unlocked contexts in addition to ops.select_cpu() and 1585 * ops.enqueue(). 1586 */ 1587 BTF_KFUNCS_START(scx_kfunc_ids_select_cpu) 1588 BTF_ID_FLAGS(func, __scx_bpf_select_cpu_and, KF_IMPLICIT_ARGS | KF_RCU) 1589 BTF_ID_FLAGS(func, scx_bpf_select_cpu_and, KF_RCU) 1590 BTF_ID_FLAGS(func, scx_bpf_select_cpu_dfl, KF_IMPLICIT_ARGS | KF_RCU) 1591 BTF_KFUNCS_END(scx_kfunc_ids_select_cpu) 1592 1593 static const struct btf_kfunc_id_set scx_kfunc_set_select_cpu = { 1594 .owner = THIS_MODULE, 1595 .set = &scx_kfunc_ids_select_cpu, 1596 .filter = scx_kfunc_context_filter, 1597 }; 1598 1599 int scx_idle_init(void) 1600 { 1601 return register_btf_kfunc_id_set(BPF_PROG_TYPE_STRUCT_OPS, &scx_kfunc_set_idle) ?: 1602 register_btf_kfunc_id_set(BPF_PROG_TYPE_TRACING, &scx_kfunc_set_idle) ?: 1603 register_btf_kfunc_id_set(BPF_PROG_TYPE_SYSCALL, &scx_kfunc_set_idle) ?: 1604 register_btf_kfunc_id_set(BPF_PROG_TYPE_STRUCT_OPS, &scx_kfunc_set_select_cpu) ?: 1605 register_btf_kfunc_id_set(BPF_PROG_TYPE_SYSCALL, &scx_kfunc_set_select_cpu); 1606 } 1607