5  * Built-in idle CPU tracking policy.
14 #include "idle.h"
17 /* Enable/disable built-in idle CPU selection policy */
20 /* Enable/disable per-node idle cpumasks */
30  * cpumasks to track idle CPUs within each NUMA node.
33  * from is used to track all the idle CPUs in the system.
41  * Global host-wide idle cpumasks (used when SCX_OPS_BUILTIN_IDLE_PER_NODE
47  * Per-node idle cpumasks.
52  * Local per-CPU cpumasks (used to generate temporary idle cpumasks).
59  * Return the idle masks associated to a target @node.
61  * NUMA_NO_NODE identifies the global idle cpumask.
70  * per-node idle cpumasks are disabled.
87 	 * cluster is not wholly idle either way. This also prevents  in scx_idle_test_and_clear_cpu()
97 		 * @cpu is never cleared from the idle SMT mask. Ensure that  in scx_idle_test_and_clear_cpu()
114  * Pick an idle CPU in a specific NUMA node.
143  * Tracks nodes that have not yet been visited when searching for an idle
149  * Search for an idle CPU across all nodes, excluding @node.
173 	 * SCX_OPS_BUILTIN_IDLE_PER_NODE and it's requesting an idle CPU  in pick_idle_cpu_from_online_nodes()
199  * Find an idle CPU in the system, starting from @node.
338  * cache-aware / NUMA-aware scheduling optimizations in the default CPU idle
354 	 * single LLC domain, the idle CPU selection logic can choose any  in scx_idle_update_selcpu_topology()
377 	 * for an idle CPU in the same domain twice is redundant.  in scx_idle_update_selcpu_topology()
380 	 * optimization, as we would naturally select idle CPUs within  in scx_idle_update_selcpu_topology()
394 	pr_debug("sched_ext: LLC idle selection %s\n",  in scx_idle_update_selcpu_topology()
396 	pr_debug("sched_ext: NUMA idle selection %s\n",  in scx_idle_update_selcpu_topology()
418  * Built-in CPU idle selection policy:
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.
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
443  * 6. Pick any idle CPU within the @cpus_allowed domain.
453  * Return the picked CPU if idle, or a negative value otherwise.
530 		 * If the waker's CPU is cache affine and prev_cpu is idle,  in scx_select_cpu_dfl()
548 		 * Checking only for the presence of idle CPUs is also  in scx_select_cpu_dfl()
550 		 * piled up on it even if there is an idle core elsewhere on  in scx_select_cpu_dfl()
566 	 * If CPU has SMT, any wholly idle CPU is likely a better pick than  in scx_select_cpu_dfl()
567 	 * partially idle @prev_cpu.  in scx_select_cpu_dfl()
571 		 * Keep using @prev_cpu if it's part of a fully idle core.  in scx_select_cpu_dfl()
581 		 * Search for any fully idle core in the same LLC domain.  in scx_select_cpu_dfl()
590 		 * Search for any fully idle core in the same NUMA node.  in scx_select_cpu_dfl()
599 		 * Search for any full-idle core usable by the task.  in scx_select_cpu_dfl()
601 		 * If the node-aware idle CPU selection policy is enabled  in scx_select_cpu_dfl()
611 		 * Give up if we're strictly looking for a full-idle SMT  in scx_select_cpu_dfl()
621 	 * Use @prev_cpu if it's idle.  in scx_select_cpu_dfl()
629 	 * Use @prev_cpu's sibling if it's idle.  in scx_select_cpu_dfl()
641 	 * Search for any idle CPU in the same LLC domain.  in scx_select_cpu_dfl()
650 	 * Search for any idle CPU in the same NUMA node.  in scx_select_cpu_dfl()
659 	 * Search for any idle CPU usable by the task.  in scx_select_cpu_dfl()
661 	 * If the node-aware idle CPU selection policy is enabled  in scx_select_cpu_dfl()
677  * Initialize global and per-node idle cpumasks.
683 	/* Allocate global idle cpumasks */  in scx_idle_init_masks()
687 	/* Allocate per-node idle cpumasks (use nr_node_ids for non-contiguous NUMA nodes) */  in scx_idle_init_masks()
700 	/* Allocate local per-cpu idle cpumasks */  in scx_idle_init_masks()
711 static void update_builtin_idle(int cpu, bool idle)  in update_builtin_idle()  argument
716 	assign_cpu(cpu, idle_cpus, idle);  in update_builtin_idle()
722 		if (idle) {  in update_builtin_idle()
737  * Notify schedulers of an idle transition on @cpu's cid, delivering to every
743 static void scx_idle_notify(struct rq *rq, bool idle, bool do_notify, bool root_renotify)  in scx_idle_notify()  argument
756 			SCX_CALL_OP(root, update_idle, rq, cid, idle);  in scx_idle_notify()
780 			SCX_CALL_OP(pos, update_idle, rq, cid, idle);  in scx_idle_notify()
786  * Update the idle state of a CPU to @idle.
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
793  * This distinction is necessary, because an idle CPU can be "reserved" and
796  * to idle without a true state transition. Refreshing the idle masks
797  * without invoking ops.update_idle() ensures accurate idle state tracking
801 void __scx_update_idle(struct rq *rq, bool idle, bool do_notify)  in __scx_update_idle()  argument
808 	 * pick_task_idle() calls here only on an idle-to-idle re-pick and the  in __scx_update_idle()
813 		update_builtin_idle(cpu, idle);  in __scx_update_idle()
816 	 * ops.update_idle() fires on real idle transitions, indicated by  in __scx_update_idle()
818 	 * An idle pick also fires it to flush a forced notify owed to a sched  in __scx_update_idle()
823 	 * This must come after the builtin idle update so that BPF schedulers  in __scx_update_idle()
825 	 * either enqueue() sees the idle bit or update_idle() sees the task  in __scx_update_idle()
829 	    (idle && (rq->scx.flags &  in __scx_update_idle()
834 		scx_idle_notify(rq, idle, do_notify, root_renotify);  in __scx_update_idle()
843 	 * Start with all CPUs marked busy. The idle masks are populated when  in reset_idle_masks()
844 	 * bypass is lifted and each idle CPU is forced through an idle re-pick.  in reset_idle_masks()
845 	 * This may temporarily omit idle CPUs but never advertises a busy CPU as  in reset_idle_masks()
846 	 * idle.  in reset_idle_masks()
888 		scx_error(sch, "per-node idle tracking is disabled");  in validate_node()
918 	scx_error(sch, "built-in idle tracking is disabled");  in check_builtin_idle_enabled()
997 	 * per-CPU tasks as well. For these tasks, we can skip all idle CPU  in select_cpu_from_kfunc()
999 	 * used CPU is idle and within the allowed cpumask.  in select_cpu_from_kfunc()
1046  * @is_idle: out parameter indicating whether the returned CPU is idle
1055  * currently idle and thus a good candidate for direct dispatching.
1107  * Returns the selected idle CPU, which will be automatically awakened upon
1109  * a negative value if no idle CPU is available.
1159  * idle-tracking per-CPU cpumask of a target NUMA node.
1163  * Returns an empty cpumask if idle tracking is not enabled, if @node is
1186  * scx_bpf_get_idle_cpumask - Get a referenced kptr to the idle-tracking
1190  * Returns an empty mask if idle tracking is not enabled, or running on a
1216  * idle-tracking, per-physical-core cpumask of a target NUMA node. Can be
1221  * Returns an empty cpumask if idle tracking is not enabled, if @node is
1247  * scx_bpf_get_idle_smtmask - Get a referenced kptr to the idle-tracking,
1252  * Returns an empty mask if idle tracking is not enabled, or running on a
1281  * either the percpu, or SMT idle-tracking cpumask.
1288 	 * a reference to a global idle cpumask, which is read-only in the  in scx_bpf_put_idle_cpumask()
1295  * scx_bpf_test_and_clear_cpu_idle - Test and clear @cpu's idle state
1296  * @cpu: cpu to test and clear idle for
1299  * Returns %true if @cpu was idle and its idle state was successfully cleared.
1325  * scx_bpf_pick_idle_cpu_node - Pick and claim an idle cpu from @node
1331  * Pick and claim an idle cpu in @cpus_allowed from the NUMA node @node.
1333  * Returns the picked idle cpu number on success, or -%EBUSY if no matching
1364  * scx_bpf_pick_idle_cpu - Pick and claim an idle cpu
1369  * Pick and claim an idle cpu in @cpus_allowed. Returns the picked idle cpu
1372  * Idle CPU tracking may race against CPU scheduling state transitions. For
1374  * idle state. If the caller then assumes that there will be dispatch events on
1398 		scx_error(sch, "per-node idle tracking is enabled");  in scx_bpf_pick_idle_cpu()
1409  * scx_bpf_pick_any_cpu_node - Pick and claim an idle cpu if available
1416  * Pick and claim an idle cpu in @cpus_allowed. If none is available, pick any
1417  * CPU in @cpus_allowed. Guaranteed to succeed and returns the picked idle cpu
1424  * the CPU idle state).
1427  * set, this function can't tell which CPUs are idle and will always pick any
1462  * scx_bpf_pick_any_cpu - Pick and claim an idle cpu if available or pick any CPU
1467  * Pick and claim an idle cpu in @cpus_allowed. If none is available, pick any
1468  * CPU in @cpus_allowed. Guaranteed to succeed and returns the picked idle cpu
1473  * set, this function can't tell which CPUs are idle and will always pick any
1492 		scx_error(sch, "per-node idle tracking is enabled");  in scx_bpf_pick_any_cpu()