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