[RFC PATCH v2 22/23] sched/cache: Walk the preferred node from the preferred LLC

[Jianyong Wu]

for_each_llc_node_span() hands out a node's LLCs ordered by
llc_intra_node_distance() from that node's first LLC. That anchor is the
right one for every LLC outside the node, which all see the same order,
but not for the node the mm's preferred LLC lives in.

llc_intra_node_distance(a, b) is (rank_a + rank_b) % k + 1, so the order
seen from a rank-r anchor is a rotation of the order seen from rank 0.
With four LLCs per node and the anchor at rank 2, the canonical walk
yields distances 3, 4, 0, 2 instead of 0, 2, 3, 4. Callers that accumulate
while walking therefore treat farther LLCs as nearer ones.

Add llc_node_span_from() and for_each_llc_node_span_from(), which take the
anchor as an argument and undo the rotation, and use them wherever a
preferred LLC is already known. Nodes the anchor does not belong to keep
the canonical order, so only the preferred node's walk changes.

Signed-off-by: Jianyong Wu <wujianyong@xxxxxxxx>
---
 kernel/sched/fair.c     |  8 ++---
 kernel/sched/sched.h    | 17 +++++++++++
 kernel/sched/topology.c | 68 +++++++++++++++++++++++++++++++++++++----
 3 files changed, 83 insertions(+), 10 deletions(-)

diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
index def42490fa2a..21513e3dd65a 100644
--- a/kernel/sched/fair.c
+++ b/kernel/sched/fair.c
@@ -10866,7 +10866,7 @@ static int mm_estimated_range_dist(int pref_cpu, u64 group_util,
 		int next_dist = INT_MAX;
 
 		for_each_sched_node(pref_cpu, node) {
-			for_each_llc_node_span(node, span) {
+			for_each_llc_node_span_from(node, llc_id(pref_cpu), span) {
 				int cpu = cpumask_first(span);
 				int dist = mm_cache_distance(pref_cpu, cpu);
 
@@ -10881,7 +10881,7 @@ static int mm_estimated_range_dist(int pref_cpu, u64 group_util,
 			break;
 
 		for_each_sched_node(pref_cpu, node) {
-			for_each_llc_node_span(node, span) {
+			for_each_llc_node_span_from(node, llc_id(pref_cpu), span) {
 				int cpu = cpumask_first(span);
 
 				if (mm_cache_distance(pref_cpu, cpu) != next_dist)
@@ -11030,7 +11030,7 @@ static enum llc_mig can_migrate_node(int src_cpu, int dst_cpu,
 		if (cpumask_test_cpu(dst_cpu, cpumask_of_node(node))) {
 			nu = 0;
 			nc = 0;
-			for_each_llc_node_span(node, span) {
+			for_each_llc_node_span_from(node, llc_id(target_cpu), span) {
 				get_span_stats(span, &u, &c);
 				nu += u;
 				nc += c;
@@ -11082,7 +11082,7 @@ static enum llc_mig can_migrate_node(int src_cpu, int dst_cpu,
 		}
 
 		/* Don't migrate if this is a good place to live. */
-		for_each_llc_node_span(node, span) {
+		for_each_llc_node_span_from(node, llc_id(target_cpu), span) {
 			get_span_stats(span, &u, &c);
 			if (cpumask_test_cpu(src_cpu, span)) {
 				if (fits_llc_capacity(u, c))
diff --git a/kernel/sched/sched.h b/kernel/sched/sched.h
index e13775e9b177..409e889d660f 100644
--- a/kernel/sched/sched.h
+++ b/kernel/sched/sched.h
@@ -4128,6 +4128,8 @@ extern int sched_node_order_at(int cpu, int idx);
 extern int llc_node_stride;
 extern int llc_node_count(int node);
 extern const struct cpumask *llc_node_span_by_dist(int node, int index, int *llc_out);
+extern const struct cpumask *llc_node_span_from(int node, int anchor_llc,
+						int index, int *llc_out);
 
 /*
  * Walk each individual LLC belonging to NUMA node @node, nearest-first
@@ -4140,6 +4142,21 @@ extern const struct cpumask *llc_node_span_by_dist(int node, int index, int *llc
 	     ((span) = llc_node_span_by_dist((node), __lns_idx, NULL)) != NULL; \
 	     __lns_idx++)
 
+/*
+ * Same walk as for_each_llc_node_span(), but ordered from @anchor_llc when
+ * that LLC lives in @node. Callers that already have a preferred LLC should
+ * use this so the walk starts at the anchor instead of the node's first LLC;
+ * the two orders differ because llc_intra_node_distance() wraps modulo the
+ * node's LLC count. For any node the anchor does not belong to, this falls
+ * back to the canonical order.
+ */
+#define for_each_llc_node_span_from(node, anchor_llc, span)			\
+	for (int __lns_idx = 0, __lns_nr = llc_node_count((node));		\
+	     __lns_idx < __lns_nr &&						\
+	     ((span) = llc_node_span_from((node), (anchor_llc), __lns_idx,	\
+					  NULL)) != NULL;			\
+	     __lns_idx++)
+
 #endif
 
 void sched_domains_free_llc_id(int cpu);
diff --git a/kernel/sched/topology.c b/kernel/sched/topology.c
index 13d360070679..a0c3ec1278a6 100644
--- a/kernel/sched/topology.c
+++ b/kernel/sched/topology.c
@@ -1022,6 +1022,25 @@ static int llc_local_rank_node_count(int node)
 	return count;
 }
 
+/*
+ * 0-based rank of @llc within its own NUMA node, -1 when unknown.
+ * Ranks are handed out in ascending LLC id order, so the node's first
+ * LLC always has rank 0.
+ */
+static int llc_local_rank(int llc)
+{
+	struct llc_local_rank_topology *topo;
+	int rank = -1;
+
+	rcu_read_lock();
+	topo = rcu_dereference(llc_local_rank_topo);
+	if (topo && llc >= 0 && llc < topo->nr_llc)
+		rank = topo->rank[llc];
+	rcu_read_unlock();
+
+	return rank;
+}
+
 static void rebuild_llc_node_map(int size)
 {
 	int *new_map, *old_map;
@@ -2854,25 +2873,62 @@ int llc_node_count(int node)
 
 /*
  * Return a pointer to the cached cpumask of the LLC at position @index
- * within NUMA node @node, ordered ascending by
- * llc_intra_node_distance() from that node's lowest-id LLC.
+ * within NUMA node @node, ordered ascending by llc_intra_node_distance()
+ * from @anchor_llc.
+ *
+ * @anchor_llc is only honoured when it belongs to @node. Pass -1, or an LLC
+ * from any other node, to get the canonical order anchored at the node's own
+ * first LLC - the order every LLC outside the node agrees on.
  */
-const struct cpumask *llc_node_span_by_dist(int node, int index, int *llc_out)
+const struct cpumask *llc_node_span_from(int node, int anchor_llc, int index,
+					 int *llc_out)
 {
 	struct llc_aggr_topology *topo = rcu_dereference_all(llc_aggr_topo);
-	int llc;
+	int base, cnt, rank, self_slot, slot, llc;
 
 	if (!topo || node < 0 || node >= topo->nr_node)
 		return NULL;
-	if (index < 0 || index >= llc_local_rank_node_count(node))
+
+	cnt = llc_local_rank_node_count(node);
+	if (index < 0 || index >= cnt)
 		return NULL;
 
-	llc = topo->node_llc_by_dist[topo->node_offset[node] + index];
+	base = topo->node_offset[node];
+
+	if (anchor_llc < 0 || llc_to_node(anchor_llc) != node) {
+		llc = topo->node_llc_by_dist[base + index];
+	} else if (!index) {
+		llc = anchor_llc;		/* distance 0 */
+	} else {
+		rank = llc_local_rank(anchor_llc);
+		if (rank < 0)
+			return NULL;
+
+		/*
+		 * llc_intra_node_distance(anchor, x) is
+		 * (rank + rank_x) % cnt + 1, so walking that modular sum
+		 * ascending walks the distances ascending. The anchor itself
+		 * owns slot (2 * rank) % cnt and was already returned at
+		 * index 0, so step over it.
+		 */
+		self_slot = (2 * rank) % cnt;
+		slot = index - 1;
+		if (slot >= self_slot)
+			slot++;
+
+		llc = topo->node_llc[base + (slot - rank + cnt) % cnt];
+	}
+
 	if (llc_out)
 		*llc_out = llc;
 
 	return topo->llc_span[llc];
 }
+
+const struct cpumask *llc_node_span_by_dist(int node, int index, int *llc_out)
+{
+	return llc_node_span_from(node, -1, index, llc_out);
+}
 #endif /* CONFIG_SCHED_CACHE */
 
 const struct cpumask *tl_pkg_mask(struct sched_domain_topology_level *tl, int cpu)
-- 
2.34.1