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