/* SPDX-License-Identifier: GPL-2.0 *//* * BPF extensible scheduler class: Documentation/scheduler/sched-ext.rst * * Copyright (c) 2026 Meta Platforms, Inc. and affiliates. * Copyright (c) 2026 Tejun Heo <tj@kernel.org> */#include <linux/cacheinfo.h> #include "internal.h"#include "cid.h" /* * cid tables. The cid kfuncs are available whether the root scheduler is * cid-form or cpu-form, the latter to allow gradual migration to cids, so every * root builds a default mapping. Each root enable allocates a fresh set, builds * it privately and publishes the __rcu globals below once the layout is final. * Root disable unpublishes and RCU-frees the set. kfuncs may run before the * tables are published and must check for NULL. */u32 scx_nr_cid_shards;s16 __rcu *scx_cid_to_cpu_tbl;s16 __rcu *scx_cpu_to_cid_tbl;s32 __rcu *scx_cid_to_shard;s32 __rcu *scx_shard_node;struct scx_cid_shard __rcu *scx_cid_shard_ranges;struct scx_cid_topo __rcu *scx_cid_topo; static struct scx_cid_tables *scx_cid_tables; /* used only during alloc/free */ #define SCX_CID_TOPO_NEG (struct scx_cid_topo) { \ .core_cid = -1, .core_idx = -1, .llc_cid = -1, .llc_idx = -1, \ .node_cid = -1, .node_idx = -1, .shard_cid = -1, .shard_idx = -1, \} /* * Return @cpu's LLC shared_cpu_map. If cacheinfo isn't populated (offline or * !present), record @cpu in @fallbacks and return its node mask instead - the * worst that can happen is that the cpu's LLC becomes coarser than reality. */static const struct cpumask *cpu_llc_mask(int cpu, struct cpumask *fallbacks){ struct cpu_cacheinfo *ci = get_cpu_cacheinfo(cpu); if (!ci || !ci->info_list || !ci->num_leaves) { cpumask_set_cpu(cpu, fallbacks); return cpumask_of_node(cpu_to_node(cpu)); } return &ci->info_list[ci->num_leaves - 1].shared_cpu_map;} /* * Compute per-LLC shard layout. Each shard holds at most @shard_size cids, and * in any case no more than SCX_CID_SHARD_MAX_CPUS. Cores are spread as evenly * as possible across shards so cpu count is balanced: the first *@nr_large_p * shards get (*@cores_per_shard_p + 1) cores, the rest get *@cores_per_shard_p. */static void calc_shard_layout(const struct cpumask *llc_cpus, u32 shard_size, u32 *cores_per_shard_p, u32 *nr_large_p){ u32 nr_cores = 0, nr_cpus = 0, nr_shards; int cpu; for_each_cpu(cpu, llc_cpus) { nr_cpus++; if (cpumask_first(topology_sibling_cpumask(cpu)) == cpu) nr_cores++; } nr_shards = max_t(u32, 1, DIV_ROUND_UP(nr_cpus, shard_size)); nr_shards = max_t(u32, nr_shards, DIV_ROUND_UP(nr_cpus, SCX_CID_SHARD_MAX_CPUS)); *cores_per_shard_p = nr_cores / nr_shards; *nr_large_p = nr_cores % nr_shards;} static void scx_cid_tables_free(struct scx_cid_tables *tbls){ if (!tbls) return; kvfree(tbls->cid_to_cpu); kvfree(tbls->cpu_to_cid); kvfree(tbls->cid_to_shard); kvfree(tbls->shard_node); kvfree(tbls->shard_ranges); kvfree(tbls->topo); kfree(tbls);} static void scx_cid_tables_free_rcufn(struct rcu_head *rcu){ scx_cid_tables_free(container_of(rcu, struct scx_cid_tables, rcu));} static struct scx_cid_tables *scx_cid_alloc_tables(void){ u32 npossible = num_possible_cpus(); struct scx_cid_tables *tbls; tbls = kzalloc_obj(*tbls); if (!tbls) return NULL; tbls->cid_to_cpu = kvzalloc_objs(*tbls->cid_to_cpu, npossible); tbls->cpu_to_cid = kvzalloc_objs(*tbls->cpu_to_cid, nr_cpu_ids); tbls->cid_to_shard = kvzalloc_objs(*tbls->cid_to_shard, npossible); tbls->shard_node = kvzalloc_objs(*tbls->shard_node, npossible); tbls->shard_ranges = kvzalloc_objs(*tbls->shard_ranges, npossible); tbls->topo = kvzalloc_objs(*tbls->topo, npossible); if (!tbls->cid_to_cpu || !tbls->cpu_to_cid || !tbls->cid_to_shard || !tbls->shard_node || !tbls->shard_ranges || !tbls->topo) { scx_cid_tables_free(tbls); return NULL; } return tbls;} /** * scx_cid_publish_tables - Publish the tables scx_cid_init() built * * Called after ops.init_cids() where the layout is final. */void scx_cid_publish_tables(void){ struct scx_cid_tables *tbls = scx_cid_tables; lockdep_assert_held(&scx_enable_mutex); scx_nr_cid_shards = tbls->nr_shards; rcu_assign_pointer(scx_cid_to_cpu_tbl, tbls->cid_to_cpu); rcu_assign_pointer(scx_cpu_to_cid_tbl, tbls->cpu_to_cid); rcu_assign_pointer(scx_cid_to_shard, tbls->cid_to_shard); rcu_assign_pointer(scx_shard_node, tbls->shard_node); rcu_assign_pointer(scx_cid_shard_ranges, tbls->shard_ranges); rcu_assign_pointer(scx_cid_topo, tbls->topo);} /** * scx_cid_retire_tables - Unpublish and retire the cid tables * * Called by root disable after the readers which dereference without NULL * checks are drained, inside cpus_read_lock() to exclude the hotplug path. */void scx_cid_retire_tables(void){ struct scx_cid_tables *tbls = scx_cid_tables; lockdep_assert_held(&scx_enable_mutex); lockdep_assert_cpus_held(); if (!tbls) return; scx_cid_tables = NULL; RCU_INIT_POINTER(scx_cid_to_cpu_tbl, NULL); RCU_INIT_POINTER(scx_cpu_to_cid_tbl, NULL); RCU_INIT_POINTER(scx_cid_to_shard, NULL); RCU_INIT_POINTER(scx_shard_node, NULL); RCU_INIT_POINTER(scx_cid_shard_ranges, NULL); RCU_INIT_POINTER(scx_cid_topo, NULL); call_rcu(&tbls->rcu, scx_cid_tables_free_rcufn);} /** * scx_cid_init - build the cid mapping * @sch: the scx_sched being initialized; used as the scx_error() target * * Build a fresh table set. It becomes visible through scx_cid_publish_tables() * and is retired by scx_cid_retire_tables() at disable. * * See "Topological CPU IDs" in cid.h for the model. Walk online cpus by * intersection at each level (parent_scratch & this_level_mask), which keeps * containment correct by construction and naturally splits a physical LLC * straddling two NUMA nodes into two LLC units. The caller must hold * cpus_read_lock. */s32 scx_cid_init(struct scx_sched *sch){ cpumask_var_t to_walk __free(free_cpumask_var) = CPUMASK_VAR_NULL; cpumask_var_t node_scratch __free(free_cpumask_var) = CPUMASK_VAR_NULL; cpumask_var_t llc_scratch __free(free_cpumask_var) = CPUMASK_VAR_NULL; cpumask_var_t core_scratch __free(free_cpumask_var) = CPUMASK_VAR_NULL; cpumask_var_t llc_fallback __free(free_cpumask_var) = CPUMASK_VAR_NULL; cpumask_var_t online_no_topo __free(free_cpumask_var) = CPUMASK_VAR_NULL; struct scx_cid_tables *tbls; u32 next_cid = 0; s32 next_node_idx = 0, next_llc_idx = 0, next_core_idx = 0; s32 next_shard_idx = 0; u32 shard_size, max_cids; u32 notopo_in_shard; s32 notopo_shard_cid, notopo_shard_idx; s32 cpu, cid, si; /* CMASK_MAX_WORDS in cid.bpf.h covers NR_CPUS up to 8192 */ BUILD_BUG_ON(NR_CPUS > 8192); lockdep_assert_cpus_held(); lockdep_assert_held(&scx_enable_mutex); shard_size = sch->ops.cid_shard_size ?: SCX_CID_SHARD_SIZE_DFL; max_cids = min_t(u32, shard_size, SCX_CID_SHARD_MAX_CPUS); tbls = scx_cid_alloc_tables(); if (!tbls) return -ENOMEM; scx_cid_tables = tbls; for (si = 0; si < num_possible_cpus(); si++) tbls->shard_node[si] = NUMA_NO_NODE; if (!zalloc_cpumask_var(&to_walk, GFP_KERNEL) || !zalloc_cpumask_var(&node_scratch, GFP_KERNEL) || !zalloc_cpumask_var(&llc_scratch, GFP_KERNEL) || !zalloc_cpumask_var(&core_scratch, GFP_KERNEL) || !zalloc_cpumask_var(&llc_fallback, GFP_KERNEL) || !zalloc_cpumask_var(&online_no_topo, GFP_KERNEL)) return -ENOMEM; /* -1 sentinels for sparse-possible cpu id holes (0 is a valid cid) */ for (cpu = 0; cpu < nr_cpu_ids; cpu++) tbls->cpu_to_cid[cpu] = -1; cpumask_copy(to_walk, cpu_online_mask); while (!cpumask_empty(to_walk)) { s32 next_cpu = cpumask_first(to_walk); s32 nid = cpu_to_node(next_cpu); s32 node_cid = next_cid; s32 node_idx; /* * No NUMA info: skip and let the tail loop assign a no-topo * cid. cpumask_of_node(-1) is undefined. */ if (nid < 0) { cpumask_clear_cpu(next_cpu, to_walk); continue; } node_idx = next_node_idx++; /* node_scratch = to_walk & this node */ cpumask_and(node_scratch, to_walk, cpumask_of_node(nid)); if (WARN_ON_ONCE(!cpumask_test_cpu(next_cpu, node_scratch))) return -EINVAL; while (!cpumask_empty(node_scratch)) { s32 ncpu = cpumask_first(node_scratch); const struct cpumask *llc_mask = cpu_llc_mask(ncpu, llc_fallback); s32 llc_cid = next_cid; s32 llc_idx = next_llc_idx++; u32 cores_per_shard, nr_large; u32 shard_local = 0, cores_in_shard = 0, cids_in_shard = 0; s32 shard_cid, shard_idx; /* llc_scratch = node_scratch & this llc */ cpumask_and(llc_scratch, node_scratch, llc_mask); if (WARN_ON_ONCE(!cpumask_test_cpu(ncpu, llc_scratch))) return -EINVAL; calc_shard_layout(llc_scratch, shard_size, &cores_per_shard, &nr_large); shard_cid = next_cid; shard_idx = next_shard_idx++; tbls->shard_node[shard_idx] = nid; while (!cpumask_empty(llc_scratch)) { s32 lcpu = cpumask_first(llc_scratch); const struct cpumask *sib = topology_sibling_cpumask(lcpu); s32 core_cid = next_cid; s32 core_idx = next_core_idx++; s32 ccpu; u32 max_cores, cids_in_core; /* core_scratch = llc_scratch & this core */ cpumask_and(core_scratch, llc_scratch, sib); if (WARN_ON_ONCE(!cpumask_test_cpu(lcpu, core_scratch))) return -EINVAL; /* * Advance to a new shard when either core or * cid count reaches max. The latter bounds * shard sizes under uneven SMT. Never start an * empty shard. */ cids_in_core = cpumask_weight(core_scratch); max_cores = cores_per_shard + (shard_local < nr_large ? 1 : 0); if (cores_in_shard && (cores_in_shard >= max_cores || cids_in_shard + cids_in_core > max_cids)) { shard_local++; cores_in_shard = 0; cids_in_shard = 0; shard_cid = next_cid; shard_idx = next_shard_idx++; tbls->shard_node[shard_idx] = nid; } cores_in_shard++; cids_in_shard += cids_in_core; for_each_cpu(ccpu, core_scratch) { s32 cid = next_cid++; tbls->cid_to_cpu[cid] = ccpu; tbls->cpu_to_cid[ccpu] = cid; tbls->cid_to_shard[cid] = shard_idx; tbls->topo[cid] = (struct scx_cid_topo){ .core_cid = core_cid, .core_idx = core_idx, .llc_cid = llc_cid, .llc_idx = llc_idx, .node_cid = node_cid, .node_idx = node_idx, .shard_cid = shard_cid, .shard_idx = shard_idx, }; cpumask_clear_cpu(ccpu, llc_scratch); cpumask_clear_cpu(ccpu, node_scratch); cpumask_clear_cpu(ccpu, to_walk); } } } } /* * No-topo section: any possible cpu without a cid - normally just the * not-online ones. Pack into shards of up to min(@shard_size, * SCX_CID_SHARD_MAX_CPUS) cids so that every cid has a valid shard * assignment and the hard cap holds even with a large @shard_size. * Collect any currently-online cpus that land here in @online_no_topo * so we can warn about them at the end. */ notopo_in_shard = min_t(u32, shard_size, SCX_CID_SHARD_MAX_CPUS); notopo_shard_cid = -1; notopo_shard_idx = -1; for_each_cpu(cpu, cpu_possible_mask) { if (tbls->cpu_to_cid[cpu] != -1) continue; if (cpu_online(cpu)) cpumask_set_cpu(cpu, online_no_topo); cid = next_cid++; tbls->cid_to_cpu[cid] = cpu; tbls->cpu_to_cid[cpu] = cid; if (notopo_in_shard >= min_t(u32, shard_size, SCX_CID_SHARD_MAX_CPUS)) { notopo_shard_cid = cid; notopo_shard_idx = next_shard_idx++; notopo_in_shard = 0; } notopo_in_shard++; tbls->cid_to_shard[cid] = notopo_shard_idx; tbls->topo[cid] = SCX_CID_TOPO_NEG; tbls->topo[cid].shard_cid = notopo_shard_cid; tbls->topo[cid].shard_idx = notopo_shard_idx; } if (!cpumask_empty(llc_fallback)) pr_warn("scx_cid: cpus without cacheinfo, using node mask as llc: %*pbl\n", cpumask_pr_args(llc_fallback)); if (!cpumask_empty(online_no_topo)) pr_warn("scx_cid: online cpus with no usable topology: %*pbl\n", cpumask_pr_args(online_no_topo)); /* * Fill cid_shard_ranges[] from cid_to_shard[]. Shards are contiguous * cid ranges by construction: base_cid is the first cid landing in a * shard, nr_cids is the count. */ for (cid = 0; cid < next_cid; cid++) { s32 sidx = tbls->cid_to_shard[cid]; if (tbls->shard_ranges[sidx].nr_cids == 0) tbls->shard_ranges[sidx].base_cid = cid; tbls->shard_ranges[sidx].nr_cids++; } tbls->nr_shards = next_shard_idx; return 0;} /** * scx_cmask_clear - Zero every bit in @m's active range * @m: cmask to clear * * Storage past the active range is left as is. */void scx_cmask_clear(struct scx_cmask *m){ u32 nr_words; if (!m->nr_cids) return; nr_words = (m->base + m->nr_cids - 1) / 64 - m->base / 64 + 1; memset(m->bits, 0, nr_words * sizeof(u64));} /** * scx_cmask_fill - Set every bit in @m's active range * @m: cmask to fill * * Counterpart to scx_cmask_clear(). Storage past the active range is left as is. */void scx_cmask_fill(struct scx_cmask *m){ u32 nr_words, head_bits, tail_bits; if (!m->nr_cids) return; nr_words = (m->base + m->nr_cids - 1) / 64 - m->base / 64 + 1; memset(m->bits, 0xff, nr_words * sizeof(u64)); /* clear word-0 bits below base */ head_bits = m->base & 63; if (head_bits) m->bits[0] &= ~((1ULL << head_bits) - 1); /* clear last-word bits at or past base + nr_cids */ tail_bits = (m->base + m->nr_cids) & 63; if (tail_bits) m->bits[nr_words - 1] &= (1ULL << tail_bits) - 1;} /* * Return the index of the largest entry in @counts, or NUMA_NO_NODE if all * entries are zero. Ties resolve to the lowest index. */static s32 pick_max_node(const u32 *counts, u32 n){ s32 best = NUMA_NO_NODE; u32 best_count = 0, i; for (i = 0; i < n; i++) { if (counts[i] > best_count) { best_count = counts[i]; best = i; } } return best;} __bpf_kfunc_start_defs(); /** * scx_bpf_cid_override - Install an explicit cpu->cid mapping with shard info * @cpu_to_cid__arena: array of nr_cpu_ids s32 entries (cid for each cpu) * @cpu_to_cid_cnt: number of entries, must be nr_cpu_ids * @shard_start__arena: array of first-cid-of-each-shard, one entry per shard * @shard_start_cnt: number of shards * @aux: implicit BPF argument to access bpf_prog_aux hidden from BPF progs * * May only be called from ops.init_cids() of the root scheduler. Replace the * topology-probed cid mapping and shard layout with caller-provided ones. Each * possible cpu must map to a unique cid in [0, num_possible_cpus()). The shard * starts must be strictly increasing with the first entry 0 and all values < * num_possible_cpus(). The last shard extends to num_possible_cpus() and no * shard may span more than SCX_CID_SHARD_MAX_CPUS cids. Topo info * (core/LLC/node) is cleared and the shard layout is set from the input. On * invalid input, abort the scheduler. */__bpf_kfunc void scx_bpf_cid_override(const s32 *cpu_to_cid__arena, u32 cpu_to_cid_cnt, const s32 *shard_start__arena, u32 shard_start_cnt, const struct bpf_prog_aux *aux){ cpumask_var_t seen __free(free_cpumask_var) = CPUMASK_VAR_NULL; u32 *node_counts __free(kfree) = NULL; s32 *cpu_to_cid __free(kfree) = NULL; s32 *shard_start __free(kfree) = NULL; u32 npossible = num_possible_cpus(); struct scx_cid_tables *tbls; struct scx_sched *sch; u32 nr_shards = shard_start_cnt; bool alloced; s32 cpu, cid, si; /* * GFP_KERNEL allocs must happen before the rcu read section. Snapshot * the BPF-supplied arrays so a concurrent arena write can't change * them between validation and use. * * The BPF-supplied counts size the snapshots and thus the arena reads. * Gate the copies on the count bounds, reported below once @sch is * available. The bounded reads, at most 32KB, stay within the guard * region that arena fault recovery covers. */ alloced = zalloc_cpumask_var(&seen, GFP_KERNEL); node_counts = kzalloc_objs(*node_counts, nr_node_ids); if (cpu_to_cid_cnt == nr_cpu_ids) cpu_to_cid = kmemdup(cpu_to_cid__arena, cpu_to_cid_cnt * sizeof(s32), GFP_KERNEL); if (nr_shards && nr_shards <= npossible) shard_start = kmemdup(shard_start__arena, nr_shards * sizeof(s32), GFP_KERNEL); Lines 1–500 of 1166. Load more
/* SPDX-License-Identifier: GPL-2.0 */ /* * BPF extensible scheduler class: Documentation/scheduler/sched-ext.rst * * Copyright (c) 2026 Meta Platforms, Inc. and affiliates. * Copyright (c) 2026 Tejun Heo <tj@kernel.org> */ #include <linux/cacheinfo.h> #include "internal.h" #include "cid.h" /* * cid tables. The cid kfuncs are available whether the root scheduler is * cid-form or cpu-form, the latter to allow gradual migration to cids, so every * root builds a default mapping. Each root enable allocates a fresh set, builds * it privately and publishes the __rcu globals below once the layout is final. * Root disable unpublishes and RCU-frees the set. kfuncs may run before the * tables are published and must check for NULL. */ u32 scx_nr_cid_shards; s16 __rcu *scx_cid_to_cpu_tbl; s16 __rcu *scx_cpu_to_cid_tbl; s32 __rcu *scx_cid_to_shard; s32 __rcu *scx_shard_node; struct scx_cid_shard __rcu *scx_cid_shard_ranges; struct scx_cid_topo __rcu *scx_cid_topo; static struct scx_cid_tables *scx_cid_tables; /* used only during alloc/free */ #define SCX_CID_TOPO_NEG (struct scx_cid_topo) { \ .core_cid = -1, .core_idx = -1, .llc_cid = -1, .llc_idx = -1, \ .node_cid = -1, .node_idx = -1, .shard_cid = -1, .shard_idx = -1, \ } /* * Return @cpu's LLC shared_cpu_map. If cacheinfo isn't populated (offline or * !present), record @cpu in @fallbacks and return its node mask instead - the * worst that can happen is that the cpu's LLC becomes coarser than reality. */ static const struct cpumask *cpu_llc_mask(int cpu, struct cpumask *fallbacks) { struct cpu_cacheinfo *ci = get_cpu_cacheinfo(cpu); if (!ci || !ci->info_list || !ci->num_leaves) { cpumask_set_cpu(cpu, fallbacks); return cpumask_of_node(cpu_to_node(cpu)); } return &ci->info_list[ci->num_leaves - 1].shared_cpu_map; } /* * Compute per-LLC shard layout. Each shard holds at most @shard_size cids, and * in any case no more than SCX_CID_SHARD_MAX_CPUS. Cores are spread as evenly * as possible across shards so cpu count is balanced: the first *@nr_large_p * shards get (*@cores_per_shard_p + 1) cores, the rest get *@cores_per_shard_p. */ static void calc_shard_layout(const struct cpumask *llc_cpus, u32 shard_size, u32 *cores_per_shard_p, u32 *nr_large_p) { u32 nr_cores = 0, nr_cpus = 0, nr_shards; int cpu; for_each_cpu(cpu, llc_cpus) { nr_cpus++; if (cpumask_first(topology_sibling_cpumask(cpu)) == cpu) nr_cores++; } nr_shards = max_t(u32, 1, DIV_ROUND_UP(nr_cpus, shard_size)); nr_shards = max_t(u32, nr_shards, DIV_ROUND_UP(nr_cpus, SCX_CID_SHARD_MAX_CPUS)); *cores_per_shard_p = nr_cores / nr_shards; *nr_large_p = nr_cores % nr_shards; } static void scx_cid_tables_free(struct scx_cid_tables *tbls) { if (!tbls) return; kvfree(tbls->cid_to_cpu); kvfree(tbls->cpu_to_cid); kvfree(tbls->cid_to_shard); kvfree(tbls->shard_node); kvfree(tbls->shard_ranges); kvfree(tbls->topo); kfree(tbls); } static void scx_cid_tables_free_rcufn(struct rcu_head *rcu) { scx_cid_tables_free(container_of(rcu, struct scx_cid_tables, rcu)); } static struct scx_cid_tables *scx_cid_alloc_tables(void) { u32 npossible = num_possible_cpus(); struct scx_cid_tables *tbls; tbls = kzalloc_obj(*tbls); if (!tbls) return NULL; tbls->cid_to_cpu = kvzalloc_objs(*tbls->cid_to_cpu, npossible); tbls->cpu_to_cid = kvzalloc_objs(*tbls->cpu_to_cid, nr_cpu_ids); tbls->cid_to_shard = kvzalloc_objs(*tbls->cid_to_shard, npossible); tbls->shard_node = kvzalloc_objs(*tbls->shard_node, npossible); tbls->shard_ranges = kvzalloc_objs(*tbls->shard_ranges, npossible); tbls->topo = kvzalloc_objs(*tbls->topo, npossible); if (!tbls->cid_to_cpu || !tbls->cpu_to_cid || !tbls->cid_to_shard || !tbls->shard_node || !tbls->shard_ranges || !tbls->topo) { scx_cid_tables_free(tbls); return NULL; } return tbls; } /** * scx_cid_publish_tables - Publish the tables scx_cid_init() built * * Called after ops.init_cids() where the layout is final. */ void scx_cid_publish_tables(void) { struct scx_cid_tables *tbls = scx_cid_tables; lockdep_assert_held(&scx_enable_mutex); scx_nr_cid_shards = tbls->nr_shards; rcu_assign_pointer(scx_cid_to_cpu_tbl, tbls->cid_to_cpu); rcu_assign_pointer(scx_cpu_to_cid_tbl, tbls->cpu_to_cid); rcu_assign_pointer(scx_cid_to_shard, tbls->cid_to_shard); rcu_assign_pointer(scx_shard_node, tbls->shard_node); rcu_assign_pointer(scx_cid_shard_ranges, tbls->shard_ranges); rcu_assign_pointer(scx_cid_topo, tbls->topo); } /** * scx_cid_retire_tables - Unpublish and retire the cid tables * * Called by root disable after the readers which dereference without NULL * checks are drained, inside cpus_read_lock() to exclude the hotplug path. */ void scx_cid_retire_tables(void) { struct scx_cid_tables *tbls = scx_cid_tables; lockdep_assert_held(&scx_enable_mutex); lockdep_assert_cpus_held(); if (!tbls) return; scx_cid_tables = NULL; RCU_INIT_POINTER(scx_cid_to_cpu_tbl, NULL); RCU_INIT_POINTER(scx_cpu_to_cid_tbl, NULL); RCU_INIT_POINTER(scx_cid_to_shard, NULL); RCU_INIT_POINTER(scx_shard_node, NULL); RCU_INIT_POINTER(scx_cid_shard_ranges, NULL); RCU_INIT_POINTER(scx_cid_topo, NULL); call_rcu(&tbls->rcu, scx_cid_tables_free_rcufn); } /** * scx_cid_init - build the cid mapping * @sch: the scx_sched being initialized; used as the scx_error() target * * Build a fresh table set. It becomes visible through scx_cid_publish_tables() * and is retired by scx_cid_retire_tables() at disable. * * See "Topological CPU IDs" in cid.h for the model. Walk online cpus by * intersection at each level (parent_scratch & this_level_mask), which keeps * containment correct by construction and naturally splits a physical LLC * straddling two NUMA nodes into two LLC units. The caller must hold * cpus_read_lock. */ s32 scx_cid_init(struct scx_sched *sch) { cpumask_var_t to_walk __free(free_cpumask_var) = CPUMASK_VAR_NULL; cpumask_var_t node_scratch __free(free_cpumask_var) = CPUMASK_VAR_NULL; cpumask_var_t llc_scratch __free(free_cpumask_var) = CPUMASK_VAR_NULL; cpumask_var_t core_scratch __free(free_cpumask_var) = CPUMASK_VAR_NULL; cpumask_var_t llc_fallback __free(free_cpumask_var) = CPUMASK_VAR_NULL; cpumask_var_t online_no_topo __free(free_cpumask_var) = CPUMASK_VAR_NULL; struct scx_cid_tables *tbls; u32 next_cid = 0; s32 next_node_idx = 0, next_llc_idx = 0, next_core_idx = 0; s32 next_shard_idx = 0; u32 shard_size, max_cids; u32 notopo_in_shard; s32 notopo_shard_cid, notopo_shard_idx; s32 cpu, cid, si; /* CMASK_MAX_WORDS in cid.bpf.h covers NR_CPUS up to 8192 */ BUILD_BUG_ON(NR_CPUS > 8192); lockdep_assert_cpus_held(); lockdep_assert_held(&scx_enable_mutex); shard_size = sch->ops.cid_shard_size ?: SCX_CID_SHARD_SIZE_DFL; max_cids = min_t(u32, shard_size, SCX_CID_SHARD_MAX_CPUS); tbls = scx_cid_alloc_tables(); if (!tbls) return -ENOMEM; scx_cid_tables = tbls; for (si = 0; si < num_possible_cpus(); si++) tbls->shard_node[si] = NUMA_NO_NODE; if (!zalloc_cpumask_var(&to_walk, GFP_KERNEL) || !zalloc_cpumask_var(&node_scratch, GFP_KERNEL) || !zalloc_cpumask_var(&llc_scratch, GFP_KERNEL) || !zalloc_cpumask_var(&core_scratch, GFP_KERNEL) || !zalloc_cpumask_var(&llc_fallback, GFP_KERNEL) || !zalloc_cpumask_var(&online_no_topo, GFP_KERNEL)) return -ENOMEM; /* -1 sentinels for sparse-possible cpu id holes (0 is a valid cid) */ for (cpu = 0; cpu < nr_cpu_ids; cpu++) tbls->cpu_to_cid[cpu] = -1; cpumask_copy(to_walk, cpu_online_mask); while (!cpumask_empty(to_walk)) { s32 next_cpu = cpumask_first(to_walk); s32 nid = cpu_to_node(next_cpu); s32 node_cid = next_cid; s32 node_idx; /* * No NUMA info: skip and let the tail loop assign a no-topo * cid. cpumask_of_node(-1) is undefined. */ if (nid < 0) { cpumask_clear_cpu(next_cpu, to_walk); continue; } node_idx = next_node_idx++; /* node_scratch = to_walk & this node */ cpumask_and(node_scratch, to_walk, cpumask_of_node(nid)); if (WARN_ON_ONCE(!cpumask_test_cpu(next_cpu, node_scratch))) return -EINVAL; while (!cpumask_empty(node_scratch)) { s32 ncpu = cpumask_first(node_scratch); const struct cpumask *llc_mask = cpu_llc_mask(ncpu, llc_fallback); s32 llc_cid = next_cid; s32 llc_idx = next_llc_idx++; u32 cores_per_shard, nr_large; u32 shard_local = 0, cores_in_shard = 0, cids_in_shard = 0; s32 shard_cid, shard_idx; /* llc_scratch = node_scratch & this llc */ cpumask_and(llc_scratch, node_scratch, llc_mask); if (WARN_ON_ONCE(!cpumask_test_cpu(ncpu, llc_scratch))) return -EINVAL; calc_shard_layout(llc_scratch, shard_size, &cores_per_shard, &nr_large); shard_cid = next_cid; shard_idx = next_shard_idx++; tbls->shard_node[shard_idx] = nid; while (!cpumask_empty(llc_scratch)) { s32 lcpu = cpumask_first(llc_scratch); const struct cpumask *sib = topology_sibling_cpumask(lcpu); s32 core_cid = next_cid; s32 core_idx = next_core_idx++; s32 ccpu; u32 max_cores, cids_in_core; /* core_scratch = llc_scratch & this core */ cpumask_and(core_scratch, llc_scratch, sib); if (WARN_ON_ONCE(!cpumask_test_cpu(lcpu, core_scratch))) return -EINVAL; /* * Advance to a new shard when either core or * cid count reaches max. The latter bounds * shard sizes under uneven SMT. Never start an * empty shard. */ cids_in_core = cpumask_weight(core_scratch); max_cores = cores_per_shard + (shard_local < nr_large ? 1 : 0); if (cores_in_shard && (cores_in_shard >= max_cores || cids_in_shard + cids_in_core > max_cids)) { shard_local++; cores_in_shard = 0; cids_in_shard = 0; shard_cid = next_cid; shard_idx = next_shard_idx++; tbls->shard_node[shard_idx] = nid; } cores_in_shard++; cids_in_shard += cids_in_core; for_each_cpu(ccpu, core_scratch) { s32 cid = next_cid++; tbls->cid_to_cpu[cid] = ccpu; tbls->cpu_to_cid[ccpu] = cid; tbls->cid_to_shard[cid] = shard_idx; tbls->topo[cid] = (struct scx_cid_topo){ .core_cid = core_cid, .core_idx = core_idx, .llc_cid = llc_cid, .llc_idx = llc_idx, .node_cid = node_cid, .node_idx = node_idx, .shard_cid = shard_cid, .shard_idx = shard_idx, }; cpumask_clear_cpu(ccpu, llc_scratch); cpumask_clear_cpu(ccpu, node_scratch); cpumask_clear_cpu(ccpu, to_walk); } } } } /* * No-topo section: any possible cpu without a cid - normally just the * not-online ones. Pack into shards of up to min(@shard_size, * SCX_CID_SHARD_MAX_CPUS) cids so that every cid has a valid shard * assignment and the hard cap holds even with a large @shard_size. * Collect any currently-online cpus that land here in @online_no_topo * so we can warn about them at the end. */ notopo_in_shard = min_t(u32, shard_size, SCX_CID_SHARD_MAX_CPUS); notopo_shard_cid = -1; notopo_shard_idx = -1; for_each_cpu(cpu, cpu_possible_mask) { if (tbls->cpu_to_cid[cpu] != -1) continue; if (cpu_online(cpu)) cpumask_set_cpu(cpu, online_no_topo); cid = next_cid++; tbls->cid_to_cpu[cid] = cpu; tbls->cpu_to_cid[cpu] = cid; if (notopo_in_shard >= min_t(u32, shard_size, SCX_CID_SHARD_MAX_CPUS)) { notopo_shard_cid = cid; notopo_shard_idx = next_shard_idx++; notopo_in_shard = 0; } notopo_in_shard++; tbls->cid_to_shard[cid] = notopo_shard_idx; tbls->topo[cid] = SCX_CID_TOPO_NEG; tbls->topo[cid].shard_cid = notopo_shard_cid; tbls->topo[cid].shard_idx = notopo_shard_idx; } if (!cpumask_empty(llc_fallback)) pr_warn("scx_cid: cpus without cacheinfo, using node mask as llc: %*pbl\n", cpumask_pr_args(llc_fallback)); if (!cpumask_empty(online_no_topo)) pr_warn("scx_cid: online cpus with no usable topology: %*pbl\n", cpumask_pr_args(online_no_topo)); /* * Fill cid_shard_ranges[] from cid_to_shard[]. Shards are contiguous * cid ranges by construction: base_cid is the first cid landing in a * shard, nr_cids is the count. */ for (cid = 0; cid < next_cid; cid++) { s32 sidx = tbls->cid_to_shard[cid]; if (tbls->shard_ranges[sidx].nr_cids == 0) tbls->shard_ranges[sidx].base_cid = cid; tbls->shard_ranges[sidx].nr_cids++; } tbls->nr_shards = next_shard_idx; return 0; } /** * scx_cmask_clear - Zero every bit in @m's active range * @m: cmask to clear * * Storage past the active range is left as is. */ void scx_cmask_clear(struct scx_cmask *m) { u32 nr_words; if (!m->nr_cids) return; nr_words = (m->base + m->nr_cids - 1) / 64 - m->base / 64 + 1; memset(m->bits, 0, nr_words * sizeof(u64)); } /** * scx_cmask_fill - Set every bit in @m's active range * @m: cmask to fill * * Counterpart to scx_cmask_clear(). Storage past the active range is left as is. */ void scx_cmask_fill(struct scx_cmask *m) { u32 nr_words, head_bits, tail_bits; if (!m->nr_cids) return; nr_words = (m->base + m->nr_cids - 1) / 64 - m->base / 64 + 1; memset(m->bits, 0xff, nr_words * sizeof(u64)); /* clear word-0 bits below base */ head_bits = m->base & 63; if (head_bits) m->bits[0] &= ~((1ULL << head_bits) - 1); /* clear last-word bits at or past base + nr_cids */ tail_bits = (m->base + m->nr_cids) & 63; if (tail_bits) m->bits[nr_words - 1] &= (1ULL << tail_bits) - 1; } /* * Return the index of the largest entry in @counts, or NUMA_NO_NODE if all * entries are zero. Ties resolve to the lowest index. */ static s32 pick_max_node(const u32 *counts, u32 n) { s32 best = NUMA_NO_NODE; u32 best_count = 0, i; for (i = 0; i < n; i++) { if (counts[i] > best_count) { best_count = counts[i]; best = i; } } return best; } __bpf_kfunc_start_defs(); /** * scx_bpf_cid_override - Install an explicit cpu->cid mapping with shard info * @cpu_to_cid__arena: array of nr_cpu_ids s32 entries (cid for each cpu) * @cpu_to_cid_cnt: number of entries, must be nr_cpu_ids * @shard_start__arena: array of first-cid-of-each-shard, one entry per shard * @shard_start_cnt: number of shards * @aux: implicit BPF argument to access bpf_prog_aux hidden from BPF progs * * May only be called from ops.init_cids() of the root scheduler. Replace the * topology-probed cid mapping and shard layout with caller-provided ones. Each * possible cpu must map to a unique cid in [0, num_possible_cpus()). The shard * starts must be strictly increasing with the first entry 0 and all values < * num_possible_cpus(). The last shard extends to num_possible_cpus() and no * shard may span more than SCX_CID_SHARD_MAX_CPUS cids. Topo info * (core/LLC/node) is cleared and the shard layout is set from the input. On * invalid input, abort the scheduler. */ __bpf_kfunc void scx_bpf_cid_override(const s32 *cpu_to_cid__arena, u32 cpu_to_cid_cnt, const s32 *shard_start__arena, u32 shard_start_cnt, const struct bpf_prog_aux *aux) { cpumask_var_t seen __free(free_cpumask_var) = CPUMASK_VAR_NULL; u32 *node_counts __free(kfree) = NULL; s32 *cpu_to_cid __free(kfree) = NULL; s32 *shard_start __free(kfree) = NULL; u32 npossible = num_possible_cpus(); struct scx_cid_tables *tbls; struct scx_sched *sch; u32 nr_shards = shard_start_cnt; bool alloced; s32 cpu, cid, si; /* * GFP_KERNEL allocs must happen before the rcu read section. Snapshot * the BPF-supplied arrays so a concurrent arena write can't change * them between validation and use. * * The BPF-supplied counts size the snapshots and thus the arena reads. * Gate the copies on the count bounds, reported below once @sch is * available. The bounded reads, at most 32KB, stay within the guard * region that arena fault recovery covers. */ alloced = zalloc_cpumask_var(&seen, GFP_KERNEL); node_counts = kzalloc_objs(*node_counts, nr_node_ids); if (cpu_to_cid_cnt == nr_cpu_ids) cpu_to_cid = kmemdup(cpu_to_cid__arena, cpu_to_cid_cnt * sizeof(s32), GFP_KERNEL); if (nr_shards && nr_shards <= npossible) shard_start = kmemdup(shard_start__arena, nr_shards * sizeof(s32), GFP_KERNEL);