// SPDX-License-Identifier: GPL-2.0/* * BPF extensible scheduler class: Documentation/scheduler/sched-ext.rst * * Built-in idle CPU tracking policy. * * Copyright (c) 2022 Meta Platforms, Inc. and affiliates. * Copyright (c) 2022 Tejun Heo <tj@kernel.org> * Copyright (c) 2022 David Vernet <dvernet@meta.com> * Copyright (c) 2024 Andrea Righi <arighi@nvidia.com> */#include "internal.h"#include "cid.h"#include "idle.h"#include "sub.h" /* Enable/disable built-in idle CPU selection policy */static DEFINE_STATIC_KEY_FALSE(scx_builtin_idle_enabled); /* Enable/disable per-node idle cpumasks */static DEFINE_STATIC_KEY_FALSE(scx_builtin_idle_per_node); /* Enable/disable LLC aware optimizations */static DEFINE_STATIC_KEY_FALSE(scx_selcpu_topo_llc); /* Enable/disable NUMA aware optimizations */static DEFINE_STATIC_KEY_FALSE(scx_selcpu_topo_numa); /* * cpumasks to track idle CPUs within each NUMA node. * * If SCX_OPS_BUILTIN_IDLE_PER_NODE is not enabled, a single global cpumask * from is used to track all the idle CPUs in the system. */struct scx_idle_cpus {	cpumask_var_t cpu;	cpumask_var_t smt;}; /* * Global host-wide idle cpumasks (used when SCX_OPS_BUILTIN_IDLE_PER_NODE * is not enabled). */static struct scx_idle_cpus scx_idle_global_masks; /* * Per-node idle cpumasks. */static struct scx_idle_cpus **scx_idle_node_masks; /* * Local per-CPU cpumasks (used to generate temporary idle cpumasks). */static DEFINE_PER_CPU(cpumask_var_t, local_idle_cpumask);static DEFINE_PER_CPU(cpumask_var_t, local_llc_idle_cpumask);static DEFINE_PER_CPU(cpumask_var_t, local_numa_idle_cpumask); /* * Return the idle masks associated to a target @node. * * NUMA_NO_NODE identifies the global idle cpumask. */static struct scx_idle_cpus *idle_cpumask(int node){	return node == NUMA_NO_NODE ? &scx_idle_global_masks : scx_idle_node_masks[node];} /* * Returns the NUMA node ID associated with a @cpu, or NUMA_NO_NODE if * per-node idle cpumasks are disabled. */static int scx_cpu_node_if_enabled(int cpu){	if (!static_branch_maybe(CONFIG_NUMA, &scx_builtin_idle_per_node))		return NUMA_NO_NODE; 	return cpu_to_node(cpu);} static bool scx_idle_test_and_clear_cpu(int cpu){	int node = scx_cpu_node_if_enabled(cpu);	struct cpumask *idle_cpus = idle_cpumask(node)->cpu; 	/*	 * SMT mask should be cleared whether we can claim @cpu or not. The SMT	 * cluster is not wholly idle either way. This also prevents	 * scx_pick_idle_cpu() from getting caught in an infinite loop.	 */	if (sched_smt_active()) {		const struct cpumask *smt = cpu_smt_mask(cpu);		struct cpumask *idle_smts = idle_cpumask(node)->smt; 		/*		 * If offline, @cpu is not its own sibling and		 * scx_pick_idle_cpu() can get caught in an infinite loop as		 * @cpu is never cleared from the idle SMT mask. Ensure that		 * @cpu is eventually cleared.		 *		 * NOTE: Use cpumask_intersects() and cpumask_test_cpu() to		 * reduce memory writes, which may help alleviate cache		 * coherence pressure.		 */		if (cpumask_intersects(smt, idle_smts))			cpumask_andnot(idle_smts, idle_smts, smt);		else if (cpumask_test_cpu(cpu, idle_smts))			__cpumask_clear_cpu(cpu, idle_smts);	} 	return cpumask_test_and_clear_cpu(cpu, idle_cpus);} /* * Pick an idle CPU in a specific NUMA node. */static s32 pick_idle_cpu_in_node(const struct cpumask *cpus_allowed, int node, u64 flags){	int cpu; retry:	if (sched_smt_active()) {		cpu = cpumask_any_and_distribute(idle_cpumask(node)->smt, cpus_allowed);		if (cpu < nr_cpu_ids)			goto found; 		if (flags & SCX_PICK_IDLE_CORE)			return -EBUSY;	} 	cpu = cpumask_any_and_distribute(idle_cpumask(node)->cpu, cpus_allowed);	if (cpu >= nr_cpu_ids)		return -EBUSY; found:	if (scx_idle_test_and_clear_cpu(cpu))		return cpu;	else		goto retry;} #ifdef CONFIG_NUMA/* * Tracks nodes that have not yet been visited when searching for an idle * CPU across all available nodes. */static DEFINE_PER_CPU(nodemask_t, per_cpu_unvisited); /* * Search for an idle CPU across all nodes, excluding @node. */static s32 pick_idle_cpu_from_online_nodes(const struct cpumask *cpus_allowed, int node, u64 flags){	nodemask_t *unvisited;	s32 cpu = -EBUSY; 	preempt_disable();	unvisited = this_cpu_ptr(&per_cpu_unvisited); 	/*	 * Restrict the search to the online nodes (excluding the current	 * node that has been visited already).	 */	nodes_copy(*unvisited, node_states[N_ONLINE]);	node_clear(node, *unvisited); 	/*	 * Traverse all nodes in order of increasing distance, starting	 * from @node.	 *	 * This loop is O(N^2), with N being the amount of NUMA nodes,	 * which might be quite expensive in large NUMA systems. However,	 * this complexity comes into play only when a scheduler enables	 * SCX_OPS_BUILTIN_IDLE_PER_NODE and it's requesting an idle CPU	 * without specifying a target NUMA node, so it shouldn't be a	 * bottleneck is most cases.	 *	 * As a future optimization we may want to cache the list of nodes	 * in a per-node array, instead of actually traversing them every	 * time.	 */	for_each_node_numadist(node, *unvisited) {		cpu = pick_idle_cpu_in_node(cpus_allowed, node, flags);		if (cpu >= 0)			break;	}	preempt_enable(); 	return cpu;}#elsestatic inline s32pick_idle_cpu_from_online_nodes(const struct cpumask *cpus_allowed, int node, u64 flags){	return -EBUSY;}#endif /* * Find an idle CPU in the system, starting from @node. */static s32 scx_pick_idle_cpu(const struct cpumask *cpus_allowed, int node, u64 flags){	s32 cpu; 	/*	 * Always search in the starting node first (this is an	 * optimization that can save some cycles even when the search is	 * not limited to a single node).	 */	cpu = pick_idle_cpu_in_node(cpus_allowed, node, flags);	if (cpu >= 0)		return cpu; 	/*	 * Stop the search if we are using only a single global cpumask	 * (NUMA_NO_NODE) or if the search is restricted to the first node	 * only.	 */	if (node == NUMA_NO_NODE || flags & SCX_PICK_IDLE_IN_NODE)		return -EBUSY; 	/*	 * Extend the search to the other online nodes.	 */	return pick_idle_cpu_from_online_nodes(cpus_allowed, node, flags);} /* * Return the amount of CPUs in the same LLC domain of @cpu (or zero if the LLC * domain is not defined). */static unsigned int llc_weight(s32 cpu){	struct sched_domain *sd; 	sd = rcu_dereference(per_cpu(sd_llc, cpu));	if (!sd)		return 0; 	return sd->span_weight;} /* * Return the cpumask representing the LLC domain of @cpu (or NULL if the LLC * domain is not defined). */static struct cpumask *llc_span(s32 cpu){	struct sched_domain *sd; 	sd = rcu_dereference(per_cpu(sd_llc, cpu));	if (!sd)		return NULL; 	return sched_domain_span(sd);} /* * Return the amount of CPUs in the same NUMA domain of @cpu (or zero if the * NUMA domain is not defined). */static unsigned int numa_weight(s32 cpu){	struct sched_domain *sd;	struct sched_group *sg; 	sd = rcu_dereference(per_cpu(sd_numa, cpu));	if (!sd)		return 0;	sg = sd->groups;	if (!sg)		return 0; 	return sg->group_weight;} /* * Return the cpumask representing the NUMA domain of @cpu (or NULL if the NUMA * domain is not defined). */static struct cpumask *numa_span(s32 cpu){	struct sched_domain *sd;	struct sched_group *sg; 	sd = rcu_dereference(per_cpu(sd_numa, cpu));	if (!sd)		return NULL;	sg = sd->groups;	if (!sg)		return NULL; 	return sched_group_span(sg);} /* * Return true if the LLC domains do not perfectly overlap with the NUMA * domains, false otherwise. */static bool llc_numa_mismatch(void){	int cpu; 	/*	 * We need to scan all online CPUs to verify whether their scheduling	 * domains overlap.	 *	 * While it is rare to encounter architectures with asymmetric NUMA	 * topologies, CPU hotplugging or virtualized environments can result	 * in asymmetric configurations.	 *	 * For example:	 *	 *  NUMA 0:	 *    - LLC 0: cpu0..cpu7	 *    - LLC 1: cpu8..cpu15 [offline]	 *	 *  NUMA 1:	 *    - LLC 0: cpu16..cpu23	 *    - LLC 1: cpu24..cpu31	 *	 * In this case, if we only check the first online CPU (cpu0), we might	 * incorrectly assume that the LLC and NUMA domains are fully	 * overlapping, which is incorrect (as NUMA 1 has two distinct LLC	 * domains).	 */	for_each_online_cpu(cpu)		if (llc_weight(cpu) != numa_weight(cpu))			return true; 	return false;} /* * Initialize topology-aware scheduling. * * Detect if the system has multiple LLC or multiple NUMA domains and enable * cache-aware / NUMA-aware scheduling optimizations in the default CPU idle * selection policy. * * Assumption: the kernel's internal topology representation assumes that each * CPU belongs to a single LLC domain, and that each LLC domain is entirely * contained within a single NUMA node. */void scx_idle_update_selcpu_topology(struct sched_ext_ops *ops){	bool enable_llc = false, enable_numa = false;	unsigned int nr_cpus;	s32 cpu = cpumask_first(cpu_online_mask); 	/*	 * Enable LLC domain optimization only when there are multiple LLC	 * domains among the online CPUs. If all online CPUs are part of a	 * single LLC domain, the idle CPU selection logic can choose any	 * online CPU without bias.	 *	 * Note that it is sufficient to check the LLC domain of the first	 * online CPU to determine whether a single LLC domain includes all	 * CPUs.	 */	rcu_read_lock();	nr_cpus = llc_weight(cpu);	if (nr_cpus > 0) {		if (nr_cpus < num_online_cpus())			enable_llc = true;		pr_debug("sched_ext: LLC=%*pb weight=%u\n",			 cpumask_pr_args(llc_span(cpu)), llc_weight(cpu));	} 	/*	 * Enable NUMA optimization only when there are multiple NUMA domains	 * among the online CPUs and the NUMA domains don't perfectly overlap	 * with the LLC domains.	 *	 * If all CPUs belong to the same NUMA node and the same LLC domain,	 * enabling both NUMA and LLC optimizations is unnecessary, as checking	 * for an idle CPU in the same domain twice is redundant.	 *	 * If SCX_OPS_BUILTIN_IDLE_PER_NODE is enabled ignore the NUMA	 * optimization, as we would naturally select idle CPUs within	 * specific NUMA nodes querying the corresponding per-node cpumask.	 */	if (!(ops->flags & SCX_OPS_BUILTIN_IDLE_PER_NODE)) {		nr_cpus = numa_weight(cpu);		if (nr_cpus > 0) {			if (nr_cpus < num_online_cpus() && llc_numa_mismatch())				enable_numa = true;			pr_debug("sched_ext: NUMA=%*pb weight=%u\n",				 cpumask_pr_args(numa_span(cpu)), nr_cpus);		}	}	rcu_read_unlock(); 	pr_debug("sched_ext: LLC idle selection %s\n",		 str_enabled_disabled(enable_llc));	pr_debug("sched_ext: NUMA idle selection %s\n",		 str_enabled_disabled(enable_numa)); 	if (enable_llc)		static_branch_enable_cpuslocked(&scx_selcpu_topo_llc);	else		static_branch_disable_cpuslocked(&scx_selcpu_topo_llc);	if (enable_numa)		static_branch_enable_cpuslocked(&scx_selcpu_topo_numa);	else		static_branch_disable_cpuslocked(&scx_selcpu_topo_numa);} /* * Return true if @p can run on all possible CPUs, false otherwise. */static inline bool task_affinity_all(const struct task_struct *p){	return p->nr_cpus_allowed >= num_possible_cpus();} /* * Built-in CPU idle selection policy: * * 1. Prioritize full-idle cores: *   - always prioritize CPUs from fully idle cores (both logical CPUs are *     idle) to avoid interference caused by SMT. * * 2. Reuse the same CPU: *   - prefer the last used CPU to take advantage of cached data (L1, L2) and *     branch prediction optimizations. * * 3. Prefer @prev_cpu's SMT sibling: *   - if @prev_cpu is busy and no fully idle core is available, try to *     place the task on an idle SMT sibling of @prev_cpu; keeping the *     task on the same core makes migration cheaper, preserves L1 cache *     locality and reduces wakeup latency. * * 4. Pick a CPU within the same LLC (Last-Level Cache): *   - if the above conditions aren't met, pick a CPU that shares the same *     LLC, if the LLC domain is a subset of @cpus_allowed, to maintain *     cache locality. * * 5. Pick a CPU within the same NUMA node, if enabled: *   - choose a CPU from the same NUMA node, if the node cpumask is a *     subset of @cpus_allowed, to reduce memory access latency. * * 6. Pick any idle CPU within the @cpus_allowed domain. * * Step 4 and 5 are performed only if the system has, respectively, * multiple LLCs / multiple NUMA nodes (see scx_selcpu_topo_llc and * scx_selcpu_topo_numa) and they don't contain the same subset of CPUs. * * If %SCX_OPS_BUILTIN_IDLE_PER_NODE is enabled, the search will always * begin in @prev_cpu's node and proceed to other nodes in order of * increasing distance. * * Return the picked CPU if idle, or a negative value otherwise. * * NOTE: tasks that can only run on 1 CPU are excluded by this logic, because * we never call ops.select_cpu() for them, see select_task_rq(). */s32 scx_select_cpu_dfl(struct task_struct *p, s32 prev_cpu, u64 wake_flags,		       const struct cpumask *cpus_allowed, u64 flags){	const struct cpumask *llc_cpus = NULL, *numa_cpus = NULL;	const struct cpumask *allowed = cpus_allowed ?: p->cpus_ptr;	int node = scx_cpu_node_if_enabled(prev_cpu);	bool is_prev_allowed;	s32 cpu; 	preempt_disable(); 	/*	 * Determine the subset of CPUs usable by @p within @cpus_allowed.	 */	if (allowed != p->cpus_ptr) {		struct cpumask *local_cpus = this_cpu_cpumask_var_ptr(local_idle_cpumask); 		if (task_affinity_all(p)) {			allowed = cpus_allowed;		} else if (cpumask_and(local_cpus, cpus_allowed, p->cpus_ptr)) {			allowed = local_cpus;		} else {			cpu = -EBUSY;			goto out_enable;		}	} 	/*	 * Check whether @prev_cpu is still within the allowed set. If not,	 * we can still try selecting a nearby CPU.	 */	is_prev_allowed = cpumask_test_cpu(prev_cpu, allowed); 	/*	 * This is necessary to protect llc_cpus.	 */	rcu_read_lock(); 	/*	 * Determine the subset of CPUs that the task can use in its	 * current LLC and node.	 *	 * If the task can run on all CPUs, use the node and LLC cpumasks

Lines 1–500 of 1561. Load more