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

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

[Andrea Righi]

The sched_ext CID topology gives each core, LLC and NUMA node a
contiguous CID range. Clusters lack explicit entries, so schedulers
cannot obtain their CID range or global index.

Walk cores by cluster and add cluster_cid and cluster_idx to
scx_cid_topo. When a core has no distinct cluster level, make that
core its own cluster. This gives every cluster a contiguous CID range
and a dense index, including on hybrid machines where only some cores
have a cluster domain.

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. Each P-core's SMT
pair forms a two-CID fallback cluster with cluster_cid = core_cid; each
E-core L2 module forms a four-CID cluster; scx_bpf_cid_topo() reports
dense cluster_idx values across all eight clusters.

Signed-off-by: Andrea Righi <arighi@nvidia.com>
---
Changes in v2:
 - Give each core without a distinct cluster level its own cluster,
   with cluster_cid = core_cid and a dense cluster_idx (Tejun Heo).
 - Based on the size-aware scx_bpf_cid_topo() fix
   (https://lore.kernel.org/r/fa6479d36b528573565ca22914451317@kernel.org)
 - Link to v1: https://lore.kernel.org/r/20260926152306.3190774-1-arighi@nvidia.com

 kernel/sched/ext/cid.c   | 69 ++++++++++++++++++++++++++++++++++++----
 kernel/sched/ext/cid.h   | 11 ++++---
 kernel/sched/ext/types.h | 19 ++++++++---
 3 files changed, 82 insertions(+), 17 deletions(-)

diff --git a/kernel/sched/ext/cid.c b/kernel/sched/ext/cid.c
index dc670975c5bfd..0addbcd103472 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,53 @@ 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 = next_cid, cluster_idx = next_cluster_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;
 
+			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);
+					} else {
+						cpumask_and(cluster_scratch, llc_scratch,
+							    topology_sibling_cpumask(xcpu));
+					}
+					if (WARN_ON_ONCE(!cpumask_test_cpu(xcpu, cluster_scratch)))
+						return -EINVAL;
+					cluster_cid = next_cid;
+					cluster_idx = next_cluster_idx++;
+				}
+
+				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 +368,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..6377b76db9c6f 100644
--- a/kernel/sched/ext/cid.h
+++ b/kernel/sched/ext/cid.h
@@ -13,11 +13,12 @@
  * 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 core without a distinct
+ * cluster level forms a cluster of its own. 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 139176cf9fc6e..da1be66cd8c3c 100644
--- a/kernel/sched/ext/types.h
+++ b/kernel/sched/ext/types.h
@@ -59,11 +59,16 @@ 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. Where
+ * this level is absent, including on individual CPUs of hybrid machines, each
+ * core forms a cluster of its own. Each cluster has a unique cluster_cid and a
+ * dense cluster_idx, and its cids form a contiguous 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
@@ -82,6 +87,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
+ * @cluster_idx: global index of that cluster, in [0, nr_clusters_at_init)
  */
 struct scx_cid_topo {
 	s32 core_cid;
@@ -92,6 +99,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 v2 sched_ext/for-7.4] sched_ext: cid: Represent clusters explicitly

[Tejun Heo]

Hello, Andrea.

The following is a Claude-generated review.

On Sat, Sep 26, 2026 at 11:20:17PM +0200, Andrea Righi wrote:
> +	if (cpumask_subset(cluster, topology_sibling_cpumask(cpu)))
> +		return NULL;
> +	if (cpumask_subset(llc_cpus, cluster))
> +		return NULL;

The second drop inverts the hardware on a part whose cores all share one
L2, such as a single E-core module or a DSU whose L2 is the LLC: each core
becomes its own cluster and a scheduler looking for L2 sharers through
cluster_cid finds none. The sched domain doesn't drop the cluster there
either, it drops MC and keeps CLS. Can we make the level inclusive instead
and skip the conditions altogether?

	cpumask_or(cluster_scratch, topology_cluster_cpumask(xcpu),
		   topology_sibling_cpumask(xcpu));
	cpumask_and(cluster_scratch, cluster_scratch, llc_scratch);

Private-L2 cores yield the core, modules yield the module and an LLC-wide
L2 yields one cluster per LLC, with the walk order unchanged. That also
drops the helper with its NULL and empty checks, which no arch can
produce, and the lines past 94 columns.

> +			s32 cluster_cid = next_cid, cluster_idx = next_cluster_idx;

cluster_scratch is always empty when an LLC starts, so the refill block
assigns both before any use. Plain declarations, and the per-LLC
cpumask_clear() is redundant for the same reason.

A few smaller things:

- The comments in cid.c and types.h describe SD_CLUSTER and when the sched
  domain drops the level. This layer's contract is enough: the
  cache-sharing level between the core and the LLC, and a core without one
  is its own cluster. The sched domain also doesn't exist with
  CONFIG_SCHED_CLUSTER=n while the L2 masks do.
- scx_bpf_cid_override()'s kerneldoc still says core/LLC/node is cleared.
- The test paragraph can be one sentence, and the Based on note under the
  separator is moot now that the fix is in for-7.4. Maybe "sched_ext: Add
  the cluster level to the cid topology" for the subject; nothing in the
  tree uses a cid: prefix.

Thanks.

-- 
tejun

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

[Andrea Righi]

Hi Tejun,

On Sat, Sep 26, 2026 at 01:27:37PM -1000, Tejun Heo wrote:
> Hello, Andrea.
> 
> The following is a Claude-generated review.
> 
> On Sat, Sep 26, 2026 at 11:20:17PM +0200, Andrea Righi wrote:
> > +	if (cpumask_subset(cluster, topology_sibling_cpumask(cpu)))
> > +		return NULL;
> > +	if (cpumask_subset(llc_cpus, cluster))
> > +		return NULL;
> 
> The second drop inverts the hardware on a part whose cores all share one
> L2, such as a single E-core module or a DSU whose L2 is the LLC: each core
> becomes its own cluster and a scheduler looking for L2 sharers through
> cluster_cid finds none. The sched domain doesn't drop the cluster there
> either, it drops MC and keeps CLS. Can we make the level inclusive instead
> and skip the conditions altogether?
> 
> 	cpumask_or(cluster_scratch, topology_cluster_cpumask(xcpu),
> 		   topology_sibling_cpumask(xcpu));
> 	cpumask_and(cluster_scratch, cluster_scratch, llc_scratch);

Agreed. I'll use the inclusive cluster mask you suggested, so an LLC-wide L2
remains one cluster.

> 
> Private-L2 cores yield the core, modules yield the module and an LLC-wide
> L2 yields one cluster per LLC, with the walk order unchanged. That also
> drops the helper with its NULL and empty checks, which no arch can
> produce, and the lines past 94 columns.
> 
> > +			s32 cluster_cid = next_cid, cluster_idx = next_cluster_idx;
> 
> cluster_scratch is always empty when an LLC starts, so the refill block
> assigns both before any use. Plain declarations, and the per-LLC
> cpumask_clear() is redundant for the same reason.

Right. I'll remove the redundant clear an changed both variables to plain
declarations.

> 
> A few smaller things:
> 
> - The comments in cid.c and types.h describe SD_CLUSTER and when the sched
>   domain drops the level. This layer's contract is enough: the
>   cache-sharing level between the core and the LLC, and a core without one
>   is its own cluster. The sched domain also doesn't exist with
>   CONFIG_SCHED_CLUSTER=n while the L2 masks do.
> - scx_bpf_cid_override()'s kerneldoc still says core/LLC/node is cleared.
> - The test paragraph can be one sentence, and the Based on note under the
>   separator is moot now that the fix is in for-7.4. Maybe "sched_ext: Add
>   the cluster level to the cid topology" for the subject; nothing in the
>   tree uses a cid: prefix.

Ack to all of the above, I'll send a v3.

Thanks,
-Andrea