Skip to contentSkip to conversation

sched_ext: Add topological CPU IDs (cids)

PATCH In review Tejun Heo 1 participant 1 message Apr 24

Subsystems (2)
lore
Share & tools
lore

Tejun Heo

author reviewer
#0 lore raw

PATCH 7/17 sched_ext: Add topological CPU IDs (cids)

Raw cpu numbers are clumsy for sharding and cross-sched communication, especially from BPF. The space is sparse, numerical closeness doesn't track topological closeness (x86 hyperthreading often scatters SMT siblings), and a range of cpu ids doesn't describe anything meaningful. Sub-sched support makes this acute: cpu allocation, revocation, and state constantly flow across sub-scheds. Passing whole cpumasks scales poorly (every op scans 4K bits) and cpumasks are awkward in BPF.

cids assign every cpu a dense, topology-ordered id. CPUs sharing a core, LLC, or NUMA node occupy contiguous cid ranges, so a topology unit becomes a (start, length) slice. Communication passes slices; BPF can process a u64 word of cids at a time.

Build the mapping once at root enable by walking online cpus node -> LLC -> core. Possible-but-not-online cpus tail the space with no-topo cids. Expose kfuncs to map cpu <-> cid in either direction and to query each cid's topology metadata.

v2: Use kzalloc_objs()/kmalloc_objs() for the three allocs in
scx_cid_arrays_alloc() (Cheng-Yang Chou).

---
 kernel/sched/build_policy.c              |   1 +
 kernel/sched/ext.c                       |  17 ++
 kernel/sched/ext_cid.c                   | 303 +++++++++++++++++++++++
 kernel/sched/ext_cid.h                   | 129 ++++++++++
 kernel/sched/ext_types.h                 |  23 ++
 tools/sched_ext/include/scx/common.bpf.h |   3 +
 6 files changed, 476 insertions(+)
 create mode 100644 kernel/sched/ext_cid.c
 create mode 100644 kernel/sched/ext_cid.h
kernel/sched/build_policy.c +1 -0
index 180ade38625e..cb9b16af09fd 100644
@@ -61,6 +61,7 @@
 # include "ext_types.h"
 # include "ext_internal.h"
 # include "ext.c"
+# include "ext_cid.c"
 # include "ext_idle.c"
 #endif
 
kernel/sched/ext.c +17 -0
index cd4c235e0c82..e05d35e8c261 100644
@@ -7,6 +7,7 @@
  * Copyright (c) 2022 David Vernet <[email protected]>
  */
 #include <linux/btf_ids.h>
+#include "ext_cid.h"
 #include "ext_idle.h"
 
 static DEFINE_RAW_SPINLOCK(scx_sched_lock);
@@ -6727,6 +6728,16 @@ static void scx_root_enable_workfn(struct kthread_work *work)
 	 */
 	cpus_read_lock();
 
+	/*
+	 * Build the cid mapping before publishing scx_root. The cid kfuncs
+	 * dereference the cid arrays unconditionally once scx_prog_sched()
+	 * returns non-NULL; the rcu_assign_pointer() below pairs with their
+	 * rcu_dereference() to make the populated arrays visible.
+	 */
+	ret = scx_cid_init(sch);
+	if (ret)
+		goto err_disable;
+
 	/*
 	 * Make the scheduler instance visible. Must be inside cpus_read_lock().
 	 * See handle_hotplug().
@@ -9775,6 +9786,12 @@ static int __init scx_init(void)
 		return ret;
 	}
 
+	ret = scx_cid_kfunc_init();
+	if (ret) {
+		pr_err("sched_ext: Failed to register cid kfuncs (%d)\n", ret);
+		return ret;
+	}
+
 	ret = register_bpf_struct_ops(&bpf_sched_ext_ops, sched_ext_ops);
 	if (ret) {
 		pr_err("sched_ext: Failed to register struct_ops (%d)\n", ret);
kernel/sched/ext_cid.c new file +303 -0

303 lines not on this page · raw message

kernel/sched/ext_cid.h new file +129 -0

129 lines not on this page · raw message

kernel/sched/ext_types.h +23 -0
index 19299ec3920e..be4d3565ae8d 100644
@@ -40,4 +40,27 @@ enum scx_consts {
 	SCX_SUB_MAX_DEPTH		= 4,
 };
 
+/*
+ * Per-cid topology info. For each topology level (core, LLC, node), records
+ * the first cid in the unit and its global index. Global indices are
+ * consecutive integers assigned in cid-walk order, so e.g. core_idx ranges
+ * over [0, nr_cores_at_init) with no gaps. No-topo cids have all fields set
+ * to -1.
+ *
+ * @core_cid: first cid of this cid's core (smt-sibling group)
+ * @core_idx: global index of that core, in [0, nr_cores_at_init)
+ * @llc_cid: first cid of this cid's LLC
+ * @llc_idx: global index of that LLC, in [0, nr_llcs_at_init)
+ * @node_cid: first cid of this cid's NUMA node
+ * @node_idx: global index of that node, in [0, nr_nodes_at_init)
+ */
+struct scx_cid_topo {
+	s32 core_cid;
+	s32 core_idx;
+	s32 llc_cid;
+	s32 llc_idx;
+	s32 node_cid;
+	s32 node_idx;
+};
+
 #endif /* _KERNEL_SCHED_EXT_TYPES_H */
tools/sched_ext/include/scx/common.bpf.h +3 -0
index 67b4b179b422..18f823d424cc 100644
@@ -102,6 +102,9 @@ struct task_struct *scx_bpf_cpu_curr(s32 cpu) __ksym __weak;
 struct task_struct *scx_bpf_tid_to_task(u64 tid) __ksym __weak;
 u64 scx_bpf_now(void) __ksym __weak;
 void scx_bpf_events(struct scx_event_stats *events, size_t events__sz) __ksym __weak;
+s32 scx_bpf_cpu_to_cid(s32 cpu) __ksym __weak;
+s32 scx_bpf_cid_to_cpu(s32 cid) __ksym __weak;
+void scx_bpf_cid_topo(s32 cid, struct scx_cid_topo *out) __ksym __weak;
 
 /*
  * Use the following as @it__iter when calling scx_bpf_dsq_move[_vtime]() from
Signature · 1 line
2.53.0