[PATCH sched_ext/for-7.4] sched_ext: cid: Represent clusters explicitly

[PATCH sched_ext/for-7.4] sched_ext: cid: Represent clusters explicitly

[Andrea Righi]

The sched_ext CID topology is meant to represent each topology level as
a contiguous range of CIDs. This works for cores, LLCs, and NUMA nodes,
but not for clusters: group of CPU cores that share a cache or other
CPU-local resources more closely with each other than with the rest of
the CPUs in the same LLC. Moreover, struct scx_cid_topo does not
identify the cluster a CPU belongs to.

Represent clusters explicitly in the CID topology:
 - enumerate the cores of each cluster before moving to the next
   cluster,
 - report the cluster in struct scx_cid_topo,
 - set @cluster_cid to the LLC's own CID when no cluster level exists,
 - set @cluster_idx to -1 when no cluster level exists,
 - treat a CPU without a cluster level as a cluster containing only its
   core, preserving the existing walk order.

Tested on a 13th Gen Intel Core i7-13800H with CONFIG_SCHED_CLUSTER=y:
six P-cores with SMT on CPUs 0-11, eight E-cores in two L2 modules on
CPUs 12-15 and 16-19 and one LLC spanning all 20 CPUs. The P-core
cluster domains degenerate to their SMT pairs, while each E-core module
has its own cluster domain; scx_bpf_cid_topo() reports the LLC's CID for
the P-cores and contiguous four-CID ranges for the two E-core clusters.

Signed-off-by: Andrea Righi <arighi@nvidia.com>
---
 kernel/sched/ext/cid.c   | 71 ++++++++++++++++++++++++++++++++++++----
 kernel/sched/ext/cid.h   | 12 ++++---
 kernel/sched/ext/types.h | 22 ++++++++++---
 3 files changed, 88 insertions(+), 17 deletions(-)

diff --git a/kernel/sched/ext/cid.c b/kernel/sched/ext/cid.c
index 39f88deb94bc4..680eef9bd924e 100644
--- a/kernel/sched/ext/cid.c
+++ b/kernel/sched/ext/cid.c
@@ -31,6 +31,7 @@ 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,	\
+	.cluster_cid = -1, .cluster_idx = -1,					\
 }
 
 /*
@@ -49,6 +50,28 @@ static const struct cpumask *cpu_llc_mask(int cpu, struct cpumask *fallbacks)
 	return &ci->info_list[ci->num_leaves - 1].shared_cpu_map;
 }
 
+/*
+ * Return the mask of cpus @cpu shares cache resources with below its LLC, the
+ * cpus an SD_CLUSTER domain would span, or NULL when that is not a level of its
+ * own here.
+ *
+ * The level is dropped in the same cases the sched domain is: a cluster that is
+ * no wider than the core, or that covers the whole LLC, adds nothing.
+ */
+static const struct cpumask *cpu_cluster_mask(int cpu, const struct cpumask *llc_cpus)
+{
+	const struct cpumask *cluster = topology_cluster_cpumask(cpu);
+
+	if (!cluster || cpumask_empty(cluster))
+		return NULL;
+	if (cpumask_subset(cluster, topology_sibling_cpumask(cpu)))
+		return NULL;
+	if (cpumask_subset(llc_cpus, cluster))
+		return NULL;
+
+	return cluster;
+}
+
 /*
  * 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
@@ -182,12 +205,14 @@ 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 cluster_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_cluster_idx = 0;
 	s32 next_shard_idx = 0;
 	u32 shard_size, max_cids;
 	u32 notopo_in_shard;
@@ -215,6 +240,7 @@ s32 scx_cid_init(struct scx_sched *sch)
 	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(&cluster_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))
@@ -256,27 +282,55 @@ s32 scx_cid_init(struct scx_sched *sch)
 			u32 cores_per_shard, nr_large;
 			u32 shard_local = 0, cores_in_shard = 0, cids_in_shard = 0;
 			s32 shard_cid, shard_idx;
+			s32 cluster_cid = llc_cid, cluster_idx = -1;
 
 			/* 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;
 
+			cpumask_clear(cluster_scratch);
 			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;
+				const struct cpumask *sib;
+				s32 core_cid, core_idx, lcpu, ccpu;
 				u32 max_cores, cids_in_core;
 
-				/* core_scratch = llc_scratch & this core */
-				cpumask_and(core_scratch, llc_scratch, sib);
+				/*
+				 * Take the cores of one cluster before moving
+				 * on, so that a cluster is a contiguous cid
+				 * range like the core, LLC and node levels.
+				 */
+				if (cpumask_empty(cluster_scratch)) {
+					s32 xcpu = cpumask_first(llc_scratch);
+					const struct cpumask *cluster =
+							cpu_cluster_mask(xcpu, llc_mask);
+
+					if (cluster) {
+						cpumask_and(cluster_scratch, llc_scratch, cluster);
+						cluster_cid = next_cid;
+						cluster_idx = next_cluster_idx++;
+					} else {
+						cpumask_and(cluster_scratch, llc_scratch,
+							    topology_sibling_cpumask(xcpu));
+						cluster_cid = llc_cid;
+						cluster_idx = -1;
+					}
+					if (WARN_ON_ONCE(!cpumask_test_cpu(xcpu, cluster_scratch)))
+						return -EINVAL;
+				}
+
+				lcpu = cpumask_first(cluster_scratch);
+				sib = topology_sibling_cpumask(lcpu);
+				core_cid = next_cid;
+				core_idx = next_core_idx++;
+
+				/* core_scratch = cluster_scratch & this core */
+				cpumask_and(core_scratch, cluster_scratch, sib);
 				if (WARN_ON_ONCE(!cpumask_test_cpu(lcpu, core_scratch)))
 					return -EINVAL;
 
@@ -316,8 +370,11 @@ s32 scx_cid_init(struct scx_sched *sch)
 						.node_idx = node_idx,
 						.shard_cid = shard_cid,
 						.shard_idx = shard_idx,
+						.cluster_cid = cluster_cid,
+						.cluster_idx = cluster_idx,
 					};
 
+					cpumask_clear_cpu(ccpu, cluster_scratch);
 					cpumask_clear_cpu(ccpu, llc_scratch);
 					cpumask_clear_cpu(ccpu, node_scratch);
 					cpumask_clear_cpu(ccpu, to_walk);
diff --git a/kernel/sched/ext/cid.h b/kernel/sched/ext/cid.h
index 2fe2311a0f995..cfe1e3890373d 100644
--- a/kernel/sched/ext/cid.h
+++ b/kernel/sched/ext/cid.h
@@ -13,11 +13,13 @@
  * kernel type sized for the maximum NR_CPUS (4k), with verbose helper sequences
  * for every op.
  *
- * cids give every cpu a dense, topology-ordered id. CPUs sharing a core, LLC or
- * NUMA node get contiguous cid ranges, so a topology unit becomes a (start,
- * length) slice of cid space. Communication can pass a slice instead of a
- * cpumask, and BPF code can process, for example, a u64 word's worth of cids at
- * a time.
+ * cids give every cpu a dense, topology-ordered id. CPUs in each core,
+ * distinct cluster, LLC or NUMA node get contiguous cid ranges, so a topology
+ * unit becomes a (start, length) slice of cid space. A cpu without a distinct
+ * cluster level uses its LLC's first cid as cluster_cid; cpus with this
+ * fallback value need not form a contiguous range. Communication can pass a
+ * slice instead of a cpumask, and BPF code can process, for example, a u64
+ * word's worth of cids at a time.
  *
  * The mapping is built once at root scheduler enable time by walking the
  * topology of online cpus only. Going by online cpus is out of necessity:
diff --git a/kernel/sched/ext/types.h b/kernel/sched/ext/types.h
index 943d8d429a2c9..9280e9cbdd6c3 100644
--- a/kernel/sched/ext/types.h
+++ b/kernel/sched/ext/types.h
@@ -59,11 +59,19 @@ enum scx_consts {
 };
 
 /*
- * Per-cid topology info. For each topology level (core, LLC, node) and shard,
- * 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 core/LLC/node fields
- * set to -1 but always have valid shard assignments.
+ * Per-cid topology info. For each topology level (core, cluster, LLC, node) and
+ * shard, 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 core/cluster/LLC/
+ * node fields set to -1 but always have valid shard assignments.
+ *
+ * A cluster is the cache-sharing level below an LLC used by SD_CLUSTER and
+ * identified by per_cpu(sd_share_id). Where this level is absent, including on
+ * individual CPUs of hybrid machines, cluster_cid is the LLC's first cid and
+ * cluster_idx is -1. Comparing cluster_cid then matches cpus_share_resources().
+ * Entries with the same nonnegative cluster_idx form a contiguous cid range.
+ * Fallback entries may be interleaved with clusters and may share cluster_cid
+ * with a real cluster, so cluster_cid alone does not delimit a cluster range.
  *
  * Shards are contiguous CID ranges used as scalable locking/work domains for
  * sub-scheduler operations. By default each LLC becomes one shard, split into
@@ -78,6 +86,8 @@ enum scx_consts {
  * @node_idx: global index of that node, in [0, nr_nodes_at_init)
  * @shard_cid: first cid of this cid's shard
  * @shard_idx: global index of that shard, in [0, scx_nr_cid_shards)
+ * @cluster_cid: first cid of this cid's cluster, or LLC if no cluster level
+ * @cluster_idx: global index of that cluster, or -1 if no cluster level
  */
 struct scx_cid_topo {
 	s32 core_cid;
@@ -88,6 +98,8 @@ struct scx_cid_topo {
 	s32 node_idx;
 	s32 shard_cid;
 	s32 shard_idx;
+	s32 cluster_cid;
+	s32 cluster_idx;
 };
 
 enum scx_cid_consts {
-- 
2.55.0

Re: [PATCH sched_ext/for-7.4] sched_ext: cid: Represent clusters explicitly

[Tejun Heo]

Hello, Andrea.

On Sat, Sep 26, 2026 at 05:23:06PM +0200, Andrea Righi wrote:
>  - set @cluster_cid to the LLC's own CID when no cluster level exists,
>  - set @cluster_idx to -1 when no cluster level exists,

The other levels are inclusive: a level that doesn't exist for a cpu is
represented by the level below it, the way a core on a non-SMT machine is
just the cpu. Can we do the same here? A core without a cluster level is
its own cluster, cluster_cid = core_cid with a dense cluster_idx. Then
every cluster is a contiguous cid range, cluster_idx indexes per-cluster
arrays without a -1 special case, and cluster_cid can't alias between a
real cluster and the fallback cpus in the same LLC.

> +	s32 cluster_cid;
> +	s32 cluster_idx;

Growing struct scx_cid_topo breaks existing binaries: scx_bpf_cid_topo()
copies out the kernel's sizeof into a buffer the program sized from its
own vmlinux.h. I'm changing the kfunc to take the buffer size and copy the
smaller of the two, filling the rest with -1, and routing that through
for-7.3-fixes so that it lands before any growth. Can you base the next
version on top of it and append the new fields at the end of the struct?

Thanks.

-- 
tejun

Re: [PATCH sched_ext/for-7.4] sched_ext: cid: Represent clusters explicitly

[Andrea Righi]

Hi Tejun,

On Sat, Sep 26, 2026 at 09:23:15AM -1000, Tejun Heo wrote:
> Hello, Andrea.
> 
> On Sat, Sep 26, 2026 at 05:23:06PM +0200, Andrea Righi wrote:
> >  - set @cluster_cid to the LLC's own CID when no cluster level exists,
> >  - set @cluster_idx to -1 when no cluster level exists,
> 
> The other levels are inclusive: a level that doesn't exist for a cpu is
> represented by the level below it, the way a core on a non-SMT machine is
> just the cpu. Can we do the same here? A core without a cluster level is
> its own cluster, cluster_cid = core_cid with a dense cluster_idx. Then
> every cluster is a contiguous cid range, cluster_idx indexes per-cluster
> arrays without a -1 special case, and cluster_cid can't alias between a
> real cluster and the fallback cpus in the same LLC.

Makes sense, I'll change the fallback so each such core is its own cluster with
cluster_cid = core_cid and a dense cluster_idx.

> 
> > +	s32 cluster_cid;
> > +	s32 cluster_idx;
> 
> Growing struct scx_cid_topo breaks existing binaries: scx_bpf_cid_topo()
> copies out the kernel's sizeof into a buffer the program sized from its
> own vmlinux.h. I'm changing the kfunc to take the buffer size and copy the
> smaller of the two, filling the rest with -1, and routing that through
> for-7.3-fixes so that it lands before any growth. Can you base the next
> version on top of it and append the new fields at the end of the struct?

Yes, I'll send a new version on top of your fix (already reviewed) and keep the
new fields at the end.

There's also a comment from Sashiko about dropping __uninit, but it looks like a
false positive to me, the current verifier checks the out buffer for read access
even with that suffix, so restoring it would not change whether an uninitialized
stack buffer is accepted.

Thanks,
-Andrea