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

[Andrea Righi <arighi@nvidia.com>]

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