* [RFC PATCH v3 01/17] sched/topology: Add llc_to_node() to translate LLC ID to NUMA node
2026-10-29 2:20 [RFC PATCH v3 00/17] sched: Scale cache-aware aggregation at LLC granularity Jianyong Wu
@ 2026-10-29 2:20 ` Jianyong Wu
2026-10-29 2:20 ` [RFC PATCH v3 02/17] sched/topology: Build NUMA node affinity sequences Jianyong Wu
` (15 subsequent siblings)
16 siblings, 0 replies; 25+ messages in thread
From: Jianyong Wu @ 2026-10-29 2:20 UTC (permalink / raw)
To: Ingo Molnar, Peter Zijlstra, Juri Lelli, Vincent Guittot, Chen Yu,
Tim Chen
Cc: Dietmar Eggemann, Steven Rostedt, Ben Segall, Mel Gorman,
Valentin Schneider, K Prateek Nayak, Shrikanth Hegde, Phil Auld,
Andrew Morton, David Hildenbrand, maddy, Michael Ellerman, ljs,
linux-kernel, linux-mm, wujianyong, jianyong.wu, zhongyuan,
huangsj, wangfengyu, yingzhiwei
Building LLC affinity sequences requires knowing which NUMA node each
LLC belongs to. Add a per-LLC-ID NUMA-node map derived from possible
CPUs that currently hold an LLC ID, and expose it to the scheduler
through llc_to_node(). Unassigned IDs return NUMA_NO_NODE.
Signed-off-by: Jianyong Wu <wujianyong@hygon.cn>
---
kernel/sched/sched.h | 1 +
kernel/sched/topology.c | 93 +++++++++++++++++++++++++++++++++++++++--
2 files changed, 91 insertions(+), 3 deletions(-)
diff --git a/kernel/sched/sched.h b/kernel/sched/sched.h
index 56acf502ba26..4ee223416012 100644
--- a/kernel/sched/sched.h
+++ b/kernel/sched/sched.h
@@ -4107,6 +4107,7 @@ static inline bool sched_cache_enabled(void)
}
extern void sched_cache_active_set(void);
+extern int llc_to_node(int llc);
#endif
diff --git a/kernel/sched/topology.c b/kernel/sched/topology.c
index 622e2e01974c..18171d2338fe 100644
--- a/kernel/sched/topology.c
+++ b/kernel/sched/topology.c
@@ -685,6 +685,24 @@ DEFINE_PER_CPU(struct sched_domain __rcu *, sd_asym_cpucapacity);
DEFINE_STATIC_KEY_FALSE(sched_asym_cpucapacity);
DEFINE_STATIC_KEY_FALSE(sched_cluster_active);
+#ifdef CONFIG_SCHED_CACHE
+/*
+ * LLC id to NUMA node map. The number of entries lives inside the
+ * RCU-protected allocation so that a reader bound-checks against the
+ * length of the very map it dereferenced. max_lid is updated by
+ * __sched_domains_alloc_llc_id() well before rebuild_llc_node_map()
+ * installs the matching map, so it must not be used as the bound.
+ */
+struct llc_node_map {
+ int nr_llc;
+ int node[];
+};
+
+static struct llc_node_map __rcu *llc_to_node_map;
+static void rebuild_llc_node_map(int size);
+
+#endif
+
static void update_top_cache_domain(int cpu)
{
struct sched_domain_shared *sds = NULL;
@@ -856,6 +874,64 @@ DEFINE_STATIC_KEY_FALSE(sched_cache_active);
/* user wants cache aware scheduling [0 or 1] */
int sysctl_sched_cache_user = 1;
+int llc_to_node(int llc)
+{
+ struct llc_node_map *map;
+ int node = -1;
+
+ rcu_read_lock();
+ map = rcu_dereference(llc_to_node_map);
+ if (map && llc >= 0 && llc < map->nr_llc)
+ node = map->node[llc];
+ rcu_read_unlock();
+
+ return node;
+}
+
+static void rebuild_llc_node_map(int size)
+{
+ struct llc_node_map *new_map, *old_map;
+ int cpu, llc, node;
+
+ lockdep_assert_held(&sched_domains_mutex);
+ if (size <= 0)
+ goto fail;
+
+ new_map = kzalloc(struct_size(new_map, node, size), GFP_KERNEL);
+ if (!new_map)
+ goto fail;
+
+ new_map->nr_llc = size;
+ for (llc = 0; llc < size; llc++)
+ new_map->node[llc] = NUMA_NO_NODE;
+
+ /*
+ * for_each_possible_cpu() revisits the same LLC non-consecutively
+ * under SMT (each node's LLCs are walked once per thread), so
+ * dedup by populated node entries, not by comparing against the
+ * immediately preceding CPU's llc.
+ */
+ for_each_possible_cpu(cpu) {
+ llc = per_cpu(sd_llc_id, cpu);
+ if (llc < 0 || llc >= size || new_map->node[llc] >= 0)
+ continue;
+ node = cpu_to_node(cpu);
+ if (node >= 0 && node < nr_node_ids && node_possible(node))
+ new_map->node[llc] = node;
+ }
+
+publish:
+ old_map = rcu_dereference_protected(llc_to_node_map,
+ lockdep_is_held(&sched_domains_mutex));
+ rcu_assign_pointer(llc_to_node_map, new_map);
+ kfree_rcu_mightsleep(old_map);
+ return;
+
+fail:
+ new_map = NULL;
+ goto publish;
+}
+
/*
* Get the effective LLC size in bytes that @cpu's bottom sched_domain
* can use. A CPU within a cpuset partition can only use a proportion
@@ -3040,7 +3116,8 @@ static int __sched_domains_alloc_llc_id(void)
return lid;
}
-static void __sched_domains_free_llc_id(int cpu)
+/* Return true only when the last CPU releases the LLC ID. */
+static bool __sched_domains_free_llc_id(int cpu)
{
int i, lid, max;
@@ -3048,14 +3125,14 @@ static void __sched_domains_free_llc_id(int cpu)
lid = per_cpu(sd_llc_id, cpu);
if (lid == -1 || lid >= nr_cpu_ids)
- return;
+ return false;
per_cpu(sd_llc_id, cpu) = -1;
for_each_cpu(i, llc_mask(cpu)) {
/* An online CPU owns the llc_id. */
if (per_cpu(sd_llc_id, i) == lid)
- return;
+ return false;
}
__cpumask_clear_cpu(lid, sched_domains_llc_id_allocmask);
@@ -3064,12 +3141,18 @@ static void __sched_domains_free_llc_id(int cpu)
/* shrink max lid to save memory */
if (max < max_lid)
max_lid = max;
+ return true;
}
void sched_domains_free_llc_id(int cpu)
{
sched_domains_mutex_lock();
+#ifdef CONFIG_SCHED_CACHE
+ if (__sched_domains_free_llc_id(cpu))
+ rebuild_llc_node_map(max_lid + 1);
+#else
__sched_domains_free_llc_id(cpu);
+#endif
sched_domains_mutex_unlock();
}
@@ -3139,6 +3222,10 @@ build_sched_domains(const struct cpumask *cpu_map, struct sched_domain_attr *att
}
}
+#ifdef CONFIG_SCHED_CACHE
+ /* The map depends on assigned LLC IDs, not on sd_llc allocations. */
+ rebuild_llc_node_map(max_lid + 1);
+#endif
if (WARN_ON(!topology_span_sane(cpu_map)))
goto error;
--
2.34.1
^ permalink raw reply related [flat|nested] 25+ messages in thread* [RFC PATCH v3 02/17] sched/topology: Build NUMA node affinity sequences
2026-10-29 2:20 [RFC PATCH v3 00/17] sched: Scale cache-aware aggregation at LLC granularity Jianyong Wu
2026-10-29 2:20 ` [RFC PATCH v3 01/17] sched/topology: Add llc_to_node() to translate LLC ID to NUMA node Jianyong Wu
@ 2026-10-29 2:20 ` Jianyong Wu
2026-10-29 2:20 ` [RFC PATCH v3 03/17] sched/topology: Add an iterator for cached NUMA node affinity rows Jianyong Wu
` (14 subsequent siblings)
16 siblings, 0 replies; 25+ messages in thread
From: Jianyong Wu @ 2026-10-29 2:20 UTC (permalink / raw)
To: Ingo Molnar, Peter Zijlstra, Juri Lelli, Vincent Guittot, Chen Yu,
Tim Chen
Cc: Dietmar Eggemann, Steven Rostedt, Ben Segall, Mel Gorman,
Valentin Schneider, K Prateek Nayak, Shrikanth Hegde, Phil Auld,
Andrew Morton, David Hildenbrand, maddy, Michael Ellerman, ljs,
linux-kernel, linux-mm, wujianyong, jianyong.wu, zhongyuan,
huangsj, wangfengyu, yingzhiwei
Cache-aware scheduling currently aggregates a workload into its preferred
LLC. To accommodate workloads that need more than one LLC, establish an
LLC affinity sequence for each preferred LLC. This sequence will guide
aggregation as the workload expands beyond that LLC.
Since LLCs belong to NUMA nodes, construct the ordering in two levels:
order the NUMA nodes first, then order the LLCs within each node. Build
the NUMA node affinity sequences here; subsequent patches handle the
intra-node LLC ordering.
Call the node containing the preferred LLC the cache-preferred node, to
distinguish it from the preferred node selected by NUMA balancing.
Raw NUMA distance provides the primary ordering, but multiple nodes may
have the same distance from the cache-preferred node. Breaking these ties
by ascending node ID creates a systematic preference for low-ID nodes.
For example, consider four nodes with the following distance matrix:
N0 N1 N2 N3
N0 10 20 20 20
N1 20 10 20 20
N2 20 20 10 20
N3 20 20 20 10
Using node IDs to break ties gives these sequences:
N0: N0 -> N1 -> N2 -> N3
N1: N1 -> N0 -> N2 -> N3
N2: N2 -> N0 -> N1 -> N3
N3: N3 -> N0 -> N1 -> N2
Suppose processes A and B have cache-preferred nodes N2 and N3,
respectively. When both nodes are full and the workloads need to expand,
both processes first prefer N0. They may therefore compete for resources
on N0 while N1 remains idle.
Use a triangular-number permutation to distribute tie-breaking positions
across nodes instead. Let N be the number of possible nodes. Assign them
consecutive ordinals in ascending node ID order, excluding ID holes, and
let p be the cache-preferred node's ordinal. Construct the offsets as:
M = 2^ceil(log2(N))
T(i) = i * (i + 1) / 2, i = 0, ..., M - 1
R(i) = T(i) % M
offset = [R(i) for i = 0, ..., M - 1 if R(i) < N]
sequence[p][j] = (p + offset[j]) % N, j = 0, ..., N - 1
Filtering preserves the original order. The first M triangular numbers
modulo M form a permutation when M is a power of two, so each retained
offset appears exactly once. Convert the resulting ordinals back to node
IDs. Across these cyclically shifted sequences, each node occupies each
position exactly once.
This sequence defines the tie-breaking order, not the final NUMA
ordering. Keep the cache-preferred node first, then sort remote nodes by
raw NUMA distance, using their positions in this sequence to break ties.
The raw distances are not modified. With unequal remote distances, the
final sequences need not retain the positional balance of the underlying
tie-breaking sequences.
For the example above, the offsets are [0, 1, 3, 2], giving:
N0: N0 -> N1 -> N3 -> N2
N1: N1 -> N2 -> N0 -> N3
N2: N2 -> N3 -> N1 -> N0
N3: N3 -> N0 -> N2 -> N1
If N2 and N3 are full, A skips N3 and expands to N1, while B expands to
N0. This avoids both processes choosing N0 while N1 remains idle. The
construction is a deterministic ordering heuristic, not a guarantee of
minimum contention for every topology or workload.
Build the sequences in sched_init_smp(). powerpc can update its NUMA
distance table at runtime in update_numa_distance(), so bracket that
update with sched_cache_numa_distance_update_begin() and
sched_cache_numa_distance_update_end(), which rebuild the cached
sequences under a mutex to keep them consistent with the raw distances.
Signed-off-by: Jianyong Wu <wujianyong@hygon.cn>
---
arch/powerpc/mm/numa.c | 4 +
include/linux/topology.h | 11 +++
kernel/sched/core.c | 1 +
kernel/sched/sched.h | 34 +++++++
kernel/sched/topology.c | 190 +++++++++++++++++++++++++++++++++++++++
5 files changed, 240 insertions(+)
diff --git a/arch/powerpc/mm/numa.c b/arch/powerpc/mm/numa.c
index f4cf3ae036de..b2befd6ec448 100644
--- a/arch/powerpc/mm/numa.c
+++ b/arch/powerpc/mm/numa.c
@@ -25,6 +25,7 @@
#include <linux/seq_file.h>
#include <linux/uaccess.h>
#include <linux/slab.h>
+#include <linux/topology.h>
#include <asm/cputhreads.h>
#include <asm/sparsemem.h>
#include <asm/smp.h>
@@ -350,7 +351,10 @@ void update_numa_distance(struct device_node *node)
if (!associativity)
return;
+ /* Keep cached node orders consistent with raw distance updates. */
+ sched_cache_numa_distance_update_begin();
initialize_form1_numa_distance(associativity);
+ sched_cache_numa_distance_update_end(true);
return;
}
diff --git a/include/linux/topology.h b/include/linux/topology.h
index 709a2dcf4c73..22bf14aaa543 100644
--- a/include/linux/topology.h
+++ b/include/linux/topology.h
@@ -177,6 +177,17 @@ static inline int cpu_to_mem(int cpu)
#endif /* [!]CONFIG_HAVE_MEMORYLESS_NODES */
+#ifdef CONFIG_SCHED_CACHE
+void sched_cache_init_node_order(void);
+/* Sleepable pair bracketing runtime changes to raw node_distance() data. */
+void sched_cache_numa_distance_update_begin(void);
+void sched_cache_numa_distance_update_end(bool changed);
+#else
+static inline void sched_cache_init_node_order(void) { }
+static inline void sched_cache_numa_distance_update_begin(void) { }
+static inline void sched_cache_numa_distance_update_end(bool changed) { }
+#endif
+
#if defined(topology_die_id) && defined(topology_die_cpumask)
#define TOPOLOGY_DIE_SYSFS
#endif
diff --git a/kernel/sched/core.c b/kernel/sched/core.c
index 96226707c2f6..bcf4026e5bd6 100644
--- a/kernel/sched/core.c
+++ b/kernel/sched/core.c
@@ -8860,6 +8860,7 @@ int sched_cpu_dying(unsigned int cpu)
void __init sched_init_smp(void)
{
sched_init_numa(NUMA_NO_NODE);
+ sched_cache_init_node_order();
prandom_init_once(&sched_rnd_state);
diff --git a/kernel/sched/sched.h b/kernel/sched/sched.h
index 4ee223416012..4dba127f1d4f 100644
--- a/kernel/sched/sched.h
+++ b/kernel/sched/sched.h
@@ -4109,6 +4109,40 @@ static inline bool sched_cache_enabled(void)
extern void sched_cache_active_set(void);
extern int llc_to_node(int llc);
+/*
+ * Lexicographic node affinity key. Keep the raw NUMA distance as the first
+ * component: it identifies the distance level without changing its order.
+ * tie_rank is used for tie-break if level equals.
+ */
+struct sched_cache_numa_key {
+ int level;
+ int tie_rank;
+};
+
+/* Both nodes must be valid */
+static inline struct sched_cache_numa_key
+sched_cache_numa_key(int node0, int node1, int tie_rank)
+{
+ return (struct sched_cache_numa_key) {
+ .level = node_distance(node0, node1),
+ .tie_rank = tie_rank,
+ };
+}
+
+static inline int
+sched_cache_numa_key_cmp(struct sched_cache_numa_key a,
+ struct sched_cache_numa_key b)
+{
+ if (a.level != b.level)
+ return a.level < b.level ? -1 : 1;
+ if (a.tie_rank != b.tie_rank)
+ return a.tie_rank < b.tie_rank ? -1 : 1;
+ return 0;
+}
+
+/* Node IDs in, zero-based rank out; -1 if unavailable or invalid. */
+extern int affi_node_rank_of(int prefer_node, int node);
+
#endif
void sched_domains_free_llc_id(int cpu);
diff --git a/kernel/sched/topology.c b/kernel/sched/topology.c
index 18171d2338fe..6b7b38eb7cd3 100644
--- a/kernel/sched/topology.c
+++ b/kernel/sched/topology.c
@@ -6,6 +6,7 @@
#include <linux/sched/isolation.h>
#include <linux/sched/clock.h>
#include <linux/bsearch.h>
+#include <linux/sort.h>
#include "sched.h"
DEFINE_MUTEX(sched_domains_mutex);
@@ -701,6 +702,18 @@ struct llc_node_map {
static struct llc_node_map __rcu *llc_to_node_map;
static void rebuild_llc_node_map(int size);
+struct affi_node_order_topology {
+ struct rcu_head rcu;
+ int size;
+ int nr_nodes;
+ int *rank;
+ int order[];
+};
+
+static struct affi_node_order_topology __rcu *affi_node_order;
+static DEFINE_MUTEX(affi_node_order_mutex);
+static bool affi_node_order_ready;
+
#endif
static void update_top_cache_domain(int cpu)
@@ -932,6 +945,183 @@ static void rebuild_llc_node_map(int size)
goto publish;
}
+struct affi_node_candidate {
+ struct sched_cache_numa_key key;
+ int node;
+};
+
+static int affi_node_candidate_cmp(const void *a, const void *b)
+{
+ const struct affi_node_candidate *ca = a, *cb = b;
+
+ return sched_cache_numa_key_cmp(ca->key, cb->key);
+}
+
+/*
+ * Build a root-relative tie-breaking order for equal-distance NUMA nodes.
+ * Sorting ties by node ID would make different roots consistently prefer
+ * low-ID nodes. Instead, use a permutation of cyclic offsets, shifted by
+ * each root's ordinal among possible nodes.
+ *
+ * Let N = nr_nodes and M be the smallest power of two >= N. Generate:
+ *
+ * T(i) = i * (i + 1) / 2, i = 0, ..., M - 1
+ * offset = T(i) % M
+ *
+ * These M residues form a permutation of [0, M). Keep only offsets < N,
+ * preserving their order, to obtain a permutation of [0, N). Using M
+ * rather than N avoids repeated or missing offsets when N is not a
+ * power of two.
+ *
+ * Store the inverse permutation: inverse[offset] is the position of
+ * that offset in the order. For root ordinal p and candidate ordinal q,
+ * the caller uses inverse[(q - p + N) % N] as the tie-breaking rank.
+ * Ordinals are consecutive and exclude holes in the node ID space.
+ *
+ * For N = 4, offsets are [0, 1, 3, 2], giving:
+ *
+ * root 0: 0, 1, 3, 2
+ * root 1: 1, 2, 0, 3
+ * root 2: 2, 3, 1, 0
+ * root 3: 3, 0, 2, 1
+ *
+ * Each ordinal occupies each position once across these shifted orders.
+ * Raw NUMA distance remains the primary sort key; this rank only breaks
+ * ties. Thus the final distance-sorted rows need not retain that balance.
+ */
+static void build_numa_tie_ranks(int *inverse, unsigned int nr_nodes)
+{
+ unsigned int mod = 1, pos = 0, i, rank = 0;
+
+ while (mod < nr_nodes)
+ mod <<= 1;
+ for (i = 0; i < mod; i++) {
+ if (pos < nr_nodes)
+ inverse[pos] = rank++;
+ pos = (pos + i + 1) & (mod - 1);
+ }
+}
+
+/* Possible nodes include CPU-less nodes and exclude node ID holes. */
+static void rebuild_node_order(void)
+{
+ struct affi_node_order_topology *topo = NULL, *old;
+ struct affi_node_candidate *cand;
+ int *tie_rank;
+ int size = nr_node_ids, nr_nodes = num_possible_nodes();
+ int root, node, i, k, root_ord = 0, node_ord, delta;
+ size_t order_entries = size_mul(size, nr_nodes);
+ size_t rank_entries = size_mul(size, size);
+ size_t entries = size_add(order_entries, rank_entries);
+
+ lockdep_assert_held(&affi_node_order_mutex);
+ if (!nr_nodes)
+ goto publish;
+
+ cand = kmalloc_array(nr_nodes, sizeof(*cand), GFP_KERNEL);
+ if (!cand)
+ goto publish;
+ tie_rank = kmalloc_array(nr_nodes, sizeof(*tie_rank), GFP_KERNEL);
+ if (!tie_rank) {
+ kfree(cand);
+ goto publish;
+ }
+ topo = kvzalloc(struct_size(topo, order, entries), GFP_KERNEL);
+ if (!topo) {
+ kfree(tie_rank);
+ kfree(cand);
+ goto publish;
+ }
+ build_numa_tie_ranks(tie_rank, nr_nodes);
+ topo->size = size;
+ topo->nr_nodes = nr_nodes;
+ /* Store both directions in one allocation and publish them together. */
+ topo->rank = topo->order + order_entries;
+ memset(topo->rank, -1, rank_entries * sizeof(*topo->rank));
+ for_each_node(root) {
+ int *row = topo->order + (size_t)root * nr_nodes;
+ int *rank = topo->rank + (size_t)root * size;
+
+ k = 0;
+ node_ord = 0;
+ for_each_node(node) {
+ /* Ordinals, rather than IDs, keep holes out of the cycle. */
+ delta = node_ord++ - root_ord;
+ if (delta < 0)
+ delta += nr_nodes;
+ if (node == root)
+ continue;
+ cand[k].node = node;
+ cand[k++].key = sched_cache_numa_key(root, node,
+ tie_rank[delta]);
+ }
+ sort(cand, k, sizeof(*cand), affi_node_candidate_cmp, NULL);
+ /* Keep the local node first regardless of firmware distances. */
+ row[0] = root;
+ rank[root] = 0;
+ for (i = 0; i < k; i++) {
+ row[i + 1] = cand[i].node;
+ rank[row[i + 1]] = i + 1;
+ }
+ root_ord++;
+ }
+ kfree(tie_rank);
+ kfree(cand);
+
+publish:
+ /* On failure, new readers fall back to the local node, not stale rows. */
+ old = rcu_replace_pointer(affi_node_order, topo,
+ lockdep_is_held(&affi_node_order_mutex));
+ kvfree_rcu(old, rcu);
+}
+
+/*
+ * Serialize runtime distance writes with construction of the cached rows.
+ * Architectures must hold this sleepable pair across their raw update.
+ * Readers continue to use an immutable old row until publication completes.
+ */
+void sched_cache_numa_distance_update_begin(void)
+{
+ mutex_lock(&affi_node_order_mutex);
+}
+
+void sched_cache_numa_distance_update_end(bool changed)
+{
+ lockdep_assert_held(&affi_node_order_mutex);
+ if (changed && affi_node_order_ready)
+ rebuild_node_order();
+ mutex_unlock(&affi_node_order_mutex);
+}
+
+void __init sched_cache_init_node_order(void)
+{
+ sched_cache_numa_distance_update_begin();
+ /* Include firmware updates made before scheduler initialization. */
+ affi_node_order_ready = true;
+ sched_cache_numa_distance_update_end(true);
+}
+
+/*
+ * Return @node's zero-based rank in @prefer_node's affinity order, with
+ * @prefer_node itself ranked first. Both arguments are node IDs, not CPUs.
+ * Return -1 for an unknown node or an unavailable ordering. Each query
+ * uses one RCU snapshot; separate queries may observe different versions.
+ */
+int affi_node_rank_of(int prefer_node, int node)
+{
+ struct affi_node_order_topology *topo;
+
+ if (prefer_node < 0 || node < 0)
+ return -1;
+
+ guard(rcu)();
+ topo = rcu_dereference(affi_node_order);
+ if (!topo || prefer_node >= topo->size || node >= topo->size)
+ return -1;
+
+ return topo->rank[(size_t)prefer_node * topo->size + node];
+}
+
/*
* Get the effective LLC size in bytes that @cpu's bottom sched_domain
* can use. A CPU within a cpuset partition can only use a proportion
--
2.34.1
^ permalink raw reply related [flat|nested] 25+ messages in thread* [RFC PATCH v3 03/17] sched/topology: Add an iterator for cached NUMA node affinity rows
2026-10-29 2:20 [RFC PATCH v3 00/17] sched: Scale cache-aware aggregation at LLC granularity Jianyong Wu
2026-10-29 2:20 ` [RFC PATCH v3 01/17] sched/topology: Add llc_to_node() to translate LLC ID to NUMA node Jianyong Wu
2026-10-29 2:20 ` [RFC PATCH v3 02/17] sched/topology: Build NUMA node affinity sequences Jianyong Wu
@ 2026-10-29 2:20 ` Jianyong Wu
2026-10-29 2:20 ` [RFC PATCH v3 04/17] sched/topology: Build triangular affinity orders for LLCs in a node Jianyong Wu
` (13 subsequent siblings)
16 siblings, 0 replies; 25+ messages in thread
From: Jianyong Wu @ 2026-10-29 2:20 UTC (permalink / raw)
To: Ingo Molnar, Peter Zijlstra, Juri Lelli, Vincent Guittot, Chen Yu,
Tim Chen
Cc: Dietmar Eggemann, Steven Rostedt, Ben Segall, Mel Gorman,
Valentin Schneider, K Prateek Nayak, Shrikanth Hegde, Phil Auld,
Andrew Morton, David Hildenbrand, maddy, Michael Ellerman, ljs,
linux-kernel, linux-mm, wujianyong, jianyong.wu, zhongyuan,
huangsj, wangfengyu, yingzhiwei
Provide for_each_affi_node() to walk the cached node affinity sequence.
Visit the local node first, then remote nodes by raw NUMA distance and
triangular tie rank. Include possible nodes without CPUs and skip holes
in the node ID space.
Pin one immutable row under RCU for the entire walk so rebuilding the
table cannot change the ordering midway through a migration decision.
If the table is unavailable, visit only the local node.
Signed-off-by: Jianyong Wu <wujianyong@hygon.cn>
---
kernel/sched/sched.h | 24 ++++++++++++++++++++++++
kernel/sched/topology.c | 32 ++++++++++++++++++++++++++++++++
2 files changed, 56 insertions(+)
diff --git a/kernel/sched/sched.h b/kernel/sched/sched.h
index 4dba127f1d4f..5d3fa5d70d16 100644
--- a/kernel/sched/sched.h
+++ b/kernel/sched/sched.h
@@ -4140,6 +4140,30 @@ sched_cache_numa_key_cmp(struct sched_cache_numa_key a,
return 0;
}
+struct affi_node_order_iter {
+ const int *order;
+ int root;
+ int nr_nodes;
+ int index;
+};
+
+/* Hold RCU continuously from begin() through the last next() call. */
+extern struct affi_node_order_iter affi_node_order_begin(int cpu);
+extern int affi_node_order_next(struct affi_node_order_iter *iter);
+
+/*
+ * Walk possible nodes, local first, then by raw NUMA distance and triangular
+ * tie rank. Pin one immutable row under RCU for the entire walk. The body
+ * must not sleep; break and return release the scoped lock. If the cached
+ * order is unavailable, visit only the local node.
+ */
+#define for_each_affi_node(cpu, node) \
+ scoped_guard(rcu) \
+ for (struct affi_node_order_iter __sn_iter = \
+ affi_node_order_begin((cpu)); \
+ ({ int __sn_node = affi_node_order_next(&__sn_iter); \
+ __sn_node >= 0 && ((node) = __sn_node, true); });)
+
/* Node IDs in, zero-based rank out; -1 if unavailable or invalid. */
extern int affi_node_rank_of(int prefer_node, int node);
diff --git a/kernel/sched/topology.c b/kernel/sched/topology.c
index 6b7b38eb7cd3..8d0fd0f8a67a 100644
--- a/kernel/sched/topology.c
+++ b/kernel/sched/topology.c
@@ -1101,6 +1101,38 @@ void __init sched_cache_init_node_order(void)
sched_cache_numa_distance_update_end(true);
}
+struct affi_node_order_iter affi_node_order_begin(int cpu)
+{
+ struct affi_node_order_topology *topo;
+ struct affi_node_order_iter iter = { };
+
+ RCU_LOCKDEP_WARN(!rcu_read_lock_any_held(), "node order read without RCU");
+ if (cpu < 0 || cpu >= nr_cpu_ids || !cpu_possible(cpu))
+ return iter;
+
+ iter.root = cpu_to_node(cpu);
+ if (iter.root < 0 || iter.root >= nr_node_ids || !node_possible(iter.root))
+ return iter;
+
+ iter.nr_nodes = 1;
+ topo = rcu_dereference_all(affi_node_order);
+ if (topo && iter.root < topo->size) {
+ iter.nr_nodes = topo->nr_nodes;
+ iter.order = topo->order + (size_t)iter.root * iter.nr_nodes;
+ }
+ return iter;
+}
+
+int affi_node_order_next(struct affi_node_order_iter *iter)
+{
+ int idx = iter->index;
+
+ if (idx >= iter->nr_nodes)
+ return -1;
+ iter->index++;
+ return iter->order ? iter->order[idx] : iter->root;
+}
+
/*
* Return @node's zero-based rank in @prefer_node's affinity order, with
* @prefer_node itself ranked first. Both arguments are node IDs, not CPUs.
--
2.34.1
^ permalink raw reply related [flat|nested] 25+ messages in thread* [RFC PATCH v3 04/17] sched/topology: Build triangular affinity orders for LLCs in a node
2026-10-29 2:20 [RFC PATCH v3 00/17] sched: Scale cache-aware aggregation at LLC granularity Jianyong Wu
` (2 preceding siblings ...)
2026-10-29 2:20 ` [RFC PATCH v3 03/17] sched/topology: Add an iterator for cached NUMA node affinity rows Jianyong Wu
@ 2026-10-29 2:20 ` Jianyong Wu
2026-10-29 2:20 ` [RFC PATCH v3 05/17] sched/topology: Walk LLCs in NUMA node Jianyong Wu
` (12 subsequent siblings)
16 siblings, 0 replies; 25+ messages in thread
From: Jianyong Wu @ 2026-10-29 2:20 UTC (permalink / raw)
To: Ingo Molnar, Peter Zijlstra, Juri Lelli, Vincent Guittot, Chen Yu,
Tim Chen
Cc: Dietmar Eggemann, Steven Rostedt, Ben Segall, Mel Gorman,
Valentin Schneider, K Prateek Nayak, Shrikanth Hegde, Phil Auld,
Andrew Morton, David Hildenbrand, maddy, Michael Ellerman, ljs,
linux-kernel, linux-mm, wujianyong, jianyong.wu, zhongyuan,
huangsj, wangfengyu, yingzhiwei
An earlier patch builds NUMA node affinity sequences. Build the LLC
order within each node here. Ordering the remaining LLCs by ID would
systematically favor low-ID LLCs, so use a triangular offset permutation.
Assign each LLC a node-local rank in ascending LLC ID order. For a node
with N LLCs, let M be the smallest power of two not less than N. Generate
the triangular offsets T(i) = i * (i + 1) / 2 modulo M for i in [0, M),
and discard offsets greater than or equal to N. Store the resulting
permutation and its inverse for each node.
For a preferred LLC with rank p, add p to each offset modulo N. For
example, with four LLCs, the order starting at LLC0 is:
LLC0, LLC1, LLC3, LLC2
Shifting the same offsets by the node-local rank of LLC1 gives:
LLC1, LLC2, LLC0, LLC3
In the system-wide affinity order used by subsequent patches, the
triangular LLC order applies only within the node containing the
preferred LLC. Other nodes follow the NUMA affinity sequence rooted at
that node, with LLCs within each remote node ordered by ascending LLC ID.
Signed-off-by: Jianyong Wu <wujianyong@hygon.cn>
---
kernel/sched/sched.h | 1 +
kernel/sched/topology.c | 96 +++++++++++++++++++++++++++++++++++++++--
2 files changed, 93 insertions(+), 4 deletions(-)
diff --git a/kernel/sched/sched.h b/kernel/sched/sched.h
index 5d3fa5d70d16..b114b7cc813f 100644
--- a/kernel/sched/sched.h
+++ b/kernel/sched/sched.h
@@ -4108,6 +4108,7 @@ static inline bool sched_cache_enabled(void)
extern void sched_cache_active_set(void);
extern int llc_to_node(int llc);
+extern int affi_llc_rank_of(int prefer_llc, int llc, int node);
/*
* Lexicographic node affinity key. Keep the raw NUMA distance as the first
diff --git a/kernel/sched/topology.c b/kernel/sched/topology.c
index 8d0fd0f8a67a..512a9762b9a2 100644
--- a/kernel/sched/topology.c
+++ b/kernel/sched/topology.c
@@ -696,6 +696,13 @@ DEFINE_STATIC_KEY_FALSE(sched_cluster_active);
*/
struct llc_node_map {
int nr_llc;
+ int nr_node;
+ int *rank; /* [nr_llc]: ascending LLC ID rank within its node */
+ int *offset; /* [nr_llc]: triangular offsets, grouped by node */
+ int *inverse; /* [nr_llc]: position of each offset */
+ int *node_count; /* [nr_node]: number of LLCs in each node */
+ int *node_offset; /* [nr_node]: start of each node's offset slice */
+ /* One allocation contains node[] and all the arrays above. */
int node[];
};
@@ -901,22 +908,56 @@ int llc_to_node(int llc)
return node;
}
+/* Build one triangular permutation and its inverse for each node's LLCs. */
+static void build_llc_offsets(struct llc_node_map *map)
+{
+ int node;
+
+ for (node = 0; node < map->nr_node; node++) {
+ unsigned int mod = 1, pos = 0, i, index = 0;
+ int nr = map->node_count[node];
+ int base = map->node_offset[node];
+
+ if (!nr)
+ continue;
+ while (mod < nr)
+ mod <<= 1;
+ for (i = 0; i < mod; i++) {
+ if (pos < nr) {
+ map->offset[base + index] = pos;
+ map->inverse[base + pos] = index++;
+ }
+ pos = (pos + i + 1) & (mod - 1);
+ }
+ }
+}
+
static void rebuild_llc_node_map(int size)
{
struct llc_node_map *new_map, *old_map;
+ size_t entries;
int cpu, llc, node;
lockdep_assert_held(&sched_domains_mutex);
if (size <= 0)
goto fail;
- new_map = kzalloc(struct_size(new_map, node, size), GFP_KERNEL);
+ entries = size_add(size_mul(size, 4), size_mul(nr_node_ids, 2));
+ new_map = kzalloc(struct_size(new_map, node, entries), GFP_KERNEL);
if (!new_map)
goto fail;
new_map->nr_llc = size;
- for (llc = 0; llc < size; llc++)
+ new_map->nr_node = nr_node_ids;
+ new_map->rank = new_map->node + size;
+ new_map->offset = new_map->rank + size;
+ new_map->inverse = new_map->offset + size;
+ new_map->node_count = new_map->inverse + size;
+ new_map->node_offset = new_map->node_count + nr_node_ids;
+ for (llc = 0; llc < size; llc++) {
new_map->node[llc] = NUMA_NO_NODE;
+ new_map->rank[llc] = -1;
+ }
/*
* for_each_possible_cpu() revisits the same LLC non-consecutively
@@ -929,10 +970,22 @@ static void rebuild_llc_node_map(int size)
if (llc < 0 || llc >= size || new_map->node[llc] >= 0)
continue;
node = cpu_to_node(cpu);
- if (node >= 0 && node < nr_node_ids && node_possible(node))
- new_map->node[llc] = node;
+ if (node < 0 || node >= new_map->nr_node || !node_possible(node))
+ continue;
+ new_map->node[llc] = node;
}
+ /* Rank LLCs by ascending ID, independently of CPU enumeration order. */
+ for (llc = 0; llc < size; llc++) {
+ node = new_map->node[llc];
+ if (node >= 0)
+ new_map->rank[llc] = new_map->node_count[node]++;
+ }
+ for (node = 1; node < new_map->nr_node; node++)
+ new_map->node_offset[node] = new_map->node_offset[node - 1] +
+ new_map->node_count[node - 1];
+ build_llc_offsets(new_map);
+
publish:
old_map = rcu_dereference_protected(llc_to_node_map,
lockdep_is_held(&sched_domains_mutex));
@@ -1154,6 +1207,41 @@ int affi_node_rank_of(int prefer_node, int node)
return topo->rank[(size_t)prefer_node * topo->size + node];
}
+/*
+ * Return @llc's position in @prefer_llc's intra-node affinity order.
+ * The preferred LLC is first; the other positions follow the triangular
+ * offset permutation of the node-local LLC ranks.
+ *
+ * Mapping, ranks and counts come from the same RCU snapshot. Return -1
+ * if the topology is unavailable or either LLC does not belong to @node.
+ */
+int affi_llc_rank_of(int prefer_llc, int llc, int node)
+{
+ struct llc_node_map *map;
+ int delta, nr, base;
+
+ if (prefer_llc < 0 || llc < 0 || node < 0)
+ return -1;
+
+ guard(rcu)();
+ map = rcu_dereference(llc_to_node_map);
+ if (!map || prefer_llc >= map->nr_llc || llc >= map->nr_llc ||
+ node >= map->nr_node || map->node[prefer_llc] != node ||
+ map->node[llc] != node)
+ return -1;
+
+ nr = map->node_count[node];
+ if (!nr || map->rank[prefer_llc] < 0 || map->rank[llc] < 0 ||
+ map->rank[prefer_llc] >= nr || map->rank[llc] >= nr)
+ return -1;
+
+ delta = map->rank[llc] - map->rank[prefer_llc];
+ if (delta < 0)
+ delta += nr;
+ base = map->node_offset[node];
+ return map->inverse[base + delta];
+}
+
/*
* Get the effective LLC size in bytes that @cpu's bottom sched_domain
* can use. A CPU within a cpuset partition can only use a proportion
--
2.34.1
^ permalink raw reply related [flat|nested] 25+ messages in thread* [RFC PATCH v3 05/17] sched/topology: Walk LLCs in NUMA node
2026-10-29 2:20 [RFC PATCH v3 00/17] sched: Scale cache-aware aggregation at LLC granularity Jianyong Wu
` (3 preceding siblings ...)
2026-10-29 2:20 ` [RFC PATCH v3 04/17] sched/topology: Build triangular affinity orders for LLCs in a node Jianyong Wu
@ 2026-10-29 2:20 ` Jianyong Wu
2026-10-29 2:20 ` [RFC PATCH v3 06/17] sched/cache: Prioritize cache-preferred node selection over LLC selection Jianyong Wu
` (11 subsequent siblings)
16 siblings, 0 replies; 25+ messages in thread
From: Jianyong Wu @ 2026-10-29 2:20 UTC (permalink / raw)
To: Ingo Molnar, Peter Zijlstra, Juri Lelli, Vincent Guittot, Chen Yu,
Tim Chen
Cc: Dietmar Eggemann, Steven Rostedt, Ben Segall, Mel Gorman,
Valentin Schneider, K Prateek Nayak, Shrikanth Hegde, Phil Auld,
Andrew Morton, David Hildenbrand, maddy, Michael Ellerman, ljs,
linux-kernel, linux-mm, wujianyong, jianyong.wu, zhongyuan,
huangsj, wangfengyu, yingzhiwei
Cache-aware scheduling needs to walk the LLCs of a NUMA node, either by
LLC ID or by their CPU spans. The existing LLC-to-node map records each
LLC's node and rank, but does not provide a direct per-node walk.
Store LLC IDs grouped by node in ascending ID order and cache each LLC's
CPU span in the RCU-published map. Add iterators for both forms of
traversal; the span iterator skips empty spans, and both keep the map
alive throughout the walk.
Refresh the map after CPUs are attached to or detached from root domains.
Also refresh it when a CPU gives up an LLC ID even if another CPU still
holds that ID, so the cached spans reflect the current load-balanced CPUs.
Signed-off-by: Jianyong Wu <wujianyong@hygon.cn>
---
kernel/sched/sched.h | 37 +++++++++++
kernel/sched/topology.c | 134 ++++++++++++++++++++++++++++++++++------
2 files changed, 153 insertions(+), 18 deletions(-)
diff --git a/kernel/sched/sched.h b/kernel/sched/sched.h
index b114b7cc813f..dec697c6a283 100644
--- a/kernel/sched/sched.h
+++ b/kernel/sched/sched.h
@@ -4141,6 +4141,43 @@ sched_cache_numa_key_cmp(struct sched_cache_numa_key a,
return 0;
}
+struct llc_node_iter {
+ const int *llc;
+ int nr;
+ int index;
+};
+
+/* Walk the LLC IDs of a node in ascending order under one RCU snapshot. */
+extern struct llc_node_iter llc_node_iter_begin(int node);
+extern int llc_node_iter_next(struct llc_node_iter *iter);
+
+#define for_each_llc_of_node(llc, node) \
+ scoped_guard(rcu) \
+ for (struct llc_node_iter __ln_iter = \
+ llc_node_iter_begin(node); \
+ ((llc) = llc_node_iter_next(&__ln_iter)) >= 0;)
+
+struct llc_node_span_iter {
+ const int *llc;
+ const void *span;
+ int nr;
+ int index;
+};
+
+/* Hold RCU continuously from begin() through the final next() call. */
+extern struct llc_node_span_iter llc_node_span_begin(int node);
+extern const struct cpumask *llc_node_span_next(struct llc_node_span_iter *iter);
+
+/*
+ * Visit @node's LLC spans in ascending LLC ID order. Empty spans are skipped.
+ * The body must not sleep.
+ */
+#define for_each_llc_node_span(node, span) \
+ scoped_guard(rcu) \
+ for (struct llc_node_span_iter __ls_iter = \
+ llc_node_span_begin(node); \
+ ((span) = llc_node_span_next(&__ls_iter)) != NULL;)
+
struct affi_node_order_iter {
const int *order;
int root;
diff --git a/kernel/sched/topology.c b/kernel/sched/topology.c
index 512a9762b9a2..37f1eeae9b7b 100644
--- a/kernel/sched/topology.c
+++ b/kernel/sched/topology.c
@@ -698,14 +698,22 @@ struct llc_node_map {
int nr_llc;
int nr_node;
int *rank; /* [nr_llc]: ascending LLC ID rank within its node */
+ int *node_llc; /* [nr_llc]: IDs grouped by node, in rank order */
int *offset; /* [nr_llc]: triangular offsets, grouped by node */
int *inverse; /* [nr_llc]: position of each offset */
int *node_count; /* [nr_node]: number of LLCs in each node */
- int *node_offset; /* [nr_node]: start of each node's offset slice */
+ int *node_offset; /* [nr_node]: start of each node's LLC/offset slice */
+ void *span; /* cpumask_size() bytes per LLC ID */
/* One allocation contains node[] and all the arrays above. */
int node[];
};
+/* The span array holds cpumask_size() bytes per LLC; never index it with []. */
+static inline struct cpumask *llc_span_at(const void *span, int llc)
+{
+ return (void *)span + (size_t)llc * cpumask_size();
+}
+
static struct llc_node_map __rcu *llc_to_node_map;
static void rebuild_llc_node_map(int size);
@@ -935,25 +943,33 @@ static void build_llc_offsets(struct llc_node_map *map)
static void rebuild_llc_node_map(int size)
{
struct llc_node_map *new_map, *old_map;
- size_t entries;
+ size_t entries, span_off;
int cpu, llc, node;
lockdep_assert_held(&sched_domains_mutex);
if (size <= 0)
goto fail;
- entries = size_add(size_mul(size, 4), size_mul(nr_node_ids, 2));
- new_map = kzalloc(struct_size(new_map, node, entries), GFP_KERNEL);
+ entries = size_add(size_mul(size, 5), size_mul(nr_node_ids, 2));
+ span_off = struct_size(new_map, node, entries);
+ if (span_off == SIZE_MAX)
+ goto fail;
+ span_off = ALIGN(span_off, sizeof(unsigned long));
+ /* The spans grow with nr_llc * nr_cpu_ids; avoid high-order kmalloc. */
+ new_map = kvzalloc(size_add(span_off, size_mul(size, cpumask_size())),
+ GFP_KERNEL);
if (!new_map)
goto fail;
new_map->nr_llc = size;
new_map->nr_node = nr_node_ids;
new_map->rank = new_map->node + size;
- new_map->offset = new_map->rank + size;
+ new_map->node_llc = new_map->rank + size;
+ new_map->offset = new_map->node_llc + size;
new_map->inverse = new_map->offset + size;
new_map->node_count = new_map->inverse + size;
new_map->node_offset = new_map->node_count + nr_node_ids;
+ new_map->span = (void *)new_map + span_off;
for (llc = 0; llc < size; llc++) {
new_map->node[llc] = NUMA_NO_NODE;
new_map->rank[llc] = -1;
@@ -962,17 +978,23 @@ static void rebuild_llc_node_map(int size)
/*
* for_each_possible_cpu() revisits the same LLC non-consecutively
* under SMT (each node's LLCs are walked once per thread), so
- * dedup by populated node entries, not by comparing against the
- * immediately preceding CPU's llc.
+ * assign the node once by checking populated node entries, not by
+ * comparing against the immediately preceding CPU's llc.
*/
for_each_possible_cpu(cpu) {
llc = per_cpu(sd_llc_id, cpu);
- if (llc < 0 || llc >= size || new_map->node[llc] >= 0)
+ if (llc < 0 || llc >= size)
continue;
- node = cpu_to_node(cpu);
- if (node < 0 || node >= new_map->nr_node || !node_possible(node))
- continue;
- new_map->node[llc] = node;
+ if (new_map->node[llc] < 0) {
+ node = cpu_to_node(cpu);
+ if (node < 0 || node >= new_map->nr_node ||
+ !node_possible(node))
+ continue;
+ new_map->node[llc] = node;
+ }
+ /* CPUs detached from load-balanced domains keep their LLC IDs. */
+ if (cpu_rq(cpu)->rd != &def_root_domain)
+ cpumask_set_cpu(cpu, llc_span_at(new_map->span, llc));
}
/* Rank LLCs by ascending ID, independently of CPU enumeration order. */
@@ -984,6 +1006,12 @@ static void rebuild_llc_node_map(int size)
for (node = 1; node < new_map->nr_node; node++)
new_map->node_offset[node] = new_map->node_offset[node - 1] +
new_map->node_count[node - 1];
+ for (llc = 0; llc < size; llc++) {
+ node = new_map->node[llc];
+ if (node >= 0)
+ new_map->node_llc[new_map->node_offset[node] +
+ new_map->rank[llc]] = llc;
+ }
build_llc_offsets(new_map);
publish:
@@ -2464,6 +2492,69 @@ const struct cpumask *tl_mc_mask(struct sched_domain_topology_level *tl, int cpu
#define llc_mask(cpu) arch_llc_mask(cpu)
+#ifdef CONFIG_SCHED_CACHE
+/* The iterator's LLC slice remains valid throughout the caller's RCU scope. */
+struct llc_node_iter llc_node_iter_begin(int node)
+{
+ struct llc_node_iter iter = {};
+ struct llc_node_map *map;
+
+ RCU_LOCKDEP_WARN(!rcu_read_lock_any_held(), "LLC walk without RCU");
+ map = rcu_dereference_all(llc_to_node_map);
+ if (!map || node < 0 || node >= map->nr_node)
+ return iter;
+
+ iter.nr = map->node_count[node];
+ iter.llc = map->node_llc + map->node_offset[node];
+ return iter;
+}
+
+int llc_node_iter_next(struct llc_node_iter *iter)
+{
+ if (iter->index >= iter->nr)
+ return -1;
+
+ return iter->llc[iter->index++];
+}
+
+/* The iterator's arrays remain valid throughout the caller's RCU scope. */
+struct llc_node_span_iter llc_node_span_begin(int node)
+{
+ struct llc_node_span_iter iter = {};
+ struct llc_node_map *map;
+ int base;
+
+ RCU_LOCKDEP_WARN(!rcu_read_lock_any_held(), "LLC span read without RCU");
+ map = rcu_dereference_all(llc_to_node_map);
+ if (!map || node < 0 || node >= map->nr_node)
+ return iter;
+
+ base = map->node_offset[node];
+ iter.nr = map->node_count[node];
+ iter.llc = map->node_llc + base;
+ iter.span = map->span;
+
+ return iter;
+}
+
+const struct cpumask *llc_node_span_next(struct llc_node_span_iter *iter)
+{
+ const struct cpumask *span;
+ int llc;
+
+ while (iter->index < iter->nr) {
+ llc = iter->llc[iter->index++];
+ span = llc_span_at(iter->span, llc);
+ if (cpumask_empty(span))
+ continue;
+
+ return span;
+ }
+
+ return NULL;
+}
+#endif /* CONFIG_SCHED_CACHE */
+
const struct cpumask *tl_pkg_mask(struct sched_domain_topology_level *tl, int cpu)
{
return cpu_node_mask(cpu);
@@ -3426,7 +3517,7 @@ static int __sched_domains_alloc_llc_id(void)
return lid;
}
-/* Return true only when the last CPU releases the LLC ID. */
+/* Return true if @cpu held an LLC ID, whether or not the ID is released. */
static bool __sched_domains_free_llc_id(int cpu)
{
int i, lid, max;
@@ -3442,7 +3533,7 @@ static bool __sched_domains_free_llc_id(int cpu)
for_each_cpu(i, llc_mask(cpu)) {
/* An online CPU owns the llc_id. */
if (per_cpu(sd_llc_id, i) == lid)
- return false;
+ return true;
}
__cpumask_clear_cpu(lid, sched_domains_llc_id_allocmask);
@@ -3458,6 +3549,7 @@ void sched_domains_free_llc_id(int cpu)
{
sched_domains_mutex_lock();
#ifdef CONFIG_SCHED_CACHE
+ /* Drop @cpu from the LLC span even if another CPU still holds the ID. */
if (__sched_domains_free_llc_id(cpu))
rebuild_llc_node_map(max_lid + 1);
#else
@@ -3532,10 +3624,6 @@ build_sched_domains(const struct cpumask *cpu_map, struct sched_domain_attr *att
}
}
-#ifdef CONFIG_SCHED_CACHE
- /* The map depends on assigned LLC IDs, not on sd_llc allocations. */
- rebuild_llc_node_map(max_lid + 1);
-#endif
if (WARN_ON(!topology_span_sane(cpu_map)))
goto error;
@@ -3608,6 +3696,11 @@ build_sched_domains(const struct cpumask *cpu_map, struct sched_domain_attr *att
}
rcu_read_unlock();
+#ifdef CONFIG_SCHED_CACHE
+ /* LLC spans depend on the root domains just attached. */
+ rebuild_llc_node_map(max_lid + 1);
+#endif
+
if (has_asym)
static_branch_inc_cpuslocked(&sched_asym_cpucapacity);
@@ -3723,6 +3816,11 @@ static void detach_destroy_domains(const struct cpumask *cpu_map)
for_each_cpu(i, cpu_map)
cpu_attach_domain(NULL, &def_root_domain, i);
rcu_read_unlock();
+
+#ifdef CONFIG_SCHED_CACHE
+ /* Detaching CPUs must also remove them from the published LLC spans. */
+ rebuild_llc_node_map(max_lid + 1);
+#endif
}
/* handle null as "default" */
--
2.34.1
^ permalink raw reply related [flat|nested] 25+ messages in thread* [RFC PATCH v3 06/17] sched/cache: Prioritize cache-preferred node selection over LLC selection
2026-10-29 2:20 [RFC PATCH v3 00/17] sched: Scale cache-aware aggregation at LLC granularity Jianyong Wu
` (4 preceding siblings ...)
2026-10-29 2:20 ` [RFC PATCH v3 05/17] sched/topology: Walk LLCs in NUMA node Jianyong Wu
@ 2026-10-29 2:20 ` Jianyong Wu
2026-10-29 2:20 ` [RFC PATCH v3 07/17] sched/topology: Add per-sd scratch for cache-aware load balancing Jianyong Wu
` (10 subsequent siblings)
16 siblings, 0 replies; 25+ messages in thread
From: Jianyong Wu @ 2026-10-29 2:20 UTC (permalink / raw)
To: Ingo Molnar, Peter Zijlstra, Juri Lelli, Vincent Guittot, Chen Yu,
Tim Chen
Cc: Dietmar Eggemann, Steven Rostedt, Ben Segall, Mel Gorman,
Valentin Schneider, K Prateek Nayak, Shrikanth Hegde, Phil Auld,
Andrew Morton, David Hildenbrand, maddy, Michael Ellerman, ljs,
linux-kernel, linux-mm, wujianyong, jianyong.wu, zhongyuan,
huangsj, wangfengyu, yingzhiwei
The LLC affinity sequence is rooted at the preferred LLC, and its node
order is rooted at the node containing that LLC. task_cache_work()
currently selects the preferred LLC by per-LLC occupancy alone. For a
workload spanning multiple nodes, small occupancy shifts between LLCs
can move the preferred LLC to another node and reorder the entire
sequence.
Occupancy aggregated over a larger set of CPUs is more stable: shifts
between LLCs of the same node cancel out in the node's sum. Make the
node-level decision on this sum first, then choose the LLC within the
selected node:
1. Sum the thread group's occupancy over the LLCs of each node. If
the busiest node exceeds twice the current cache-preferred node,
switch to it and select its busiest LLC.
2. Otherwise, stay on the current cache-preferred node and switch to
its busiest LLC only if that exceeds twice the current preferred
LLC.
This keeps the LLC affinity sequence stable. The node order changes
only when the workload's occupancy really moves to another node, and
switching LLCs within a node changes only the intra-node LLC order.
Signed-off-by: Jianyong Wu <wujianyong@hygon.cn>
---
kernel/sched/fair.c | 162 +++++++++++++++++++++++++++++---------------
1 file changed, 109 insertions(+), 53 deletions(-)
diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
index f15f5764818e..fe357d79b6e0 100644
--- a/kernel/sched/fair.c
+++ b/kernel/sched/fair.c
@@ -1824,14 +1824,47 @@ static inline void update_avg_scale(u64 *avg, u64 sample)
*avg += div64_s64(diff, divisor);
}
+/*
+ * Accumulate the mm's occupancy over one LLC. Returns the sum over @span,
+ * stores the busiest CPU in @max_cpu and adds the CPUs running a thread of
+ * @mm to @nr_running.
+ */
+static unsigned long scan_llc_occ(struct mm_struct *mm, const struct cpumask *span,
+ int *max_cpu, int *nr_running)
+{
+ unsigned long occ, m_occ = 0, a_occ = 0;
+ struct task_struct *cur;
+ int i, m_cpu = -1;
+
+ for_each_cpu(i, span) {
+ occ = fraction_mm_sched(cpu_rq(i),
+ per_cpu_ptr(mm->sc_stat.pcpu_sched, i));
+ a_occ += occ;
+ if (occ > m_occ) {
+ m_occ = occ;
+ m_cpu = i;
+ }
+
+ cur = rcu_dereference_all(cpu_rq(i)->curr);
+ if (cur && !(cur->flags & (PF_EXITING | PF_KTHREAD)) &&
+ cur->mm == mm)
+ (*nr_running)++;
+ }
+
+ *max_cpu = m_cpu;
+
+ return a_occ;
+}
+
static void task_cache_work(struct callback_head *work)
{
- int cpu, m_a_cpu = -1, nr_running = 0, curr_cpu;
unsigned long next_scan, now = jiffies;
- struct task_struct *p = current, *cur;
- unsigned long curr_m_a_occ = 0;
+ struct task_struct *p = current;
struct mm_struct *mm = p->mm;
- unsigned long m_a_occ = 0;
+ unsigned long m_a_n_occ = 0, curr_m_a_n_occ = 0, curr_m_a_occ = 0;
+ unsigned long pref_node_llc_occ = 0;
+ int cpu, m_a_n_cpu = -1, nr_running = 0, curr_cpu;
+ int pref_cpu, pref_node_llc_cpu = -1, new_cpu = -1;
cpumask_var_t cpus;
WARN_ON_ONCE(work != &p->cache_work);
@@ -1863,75 +1896,98 @@ static void task_cache_work(struct callback_head *work)
if (!zalloc_cpumask_var(&cpus, GFP_KERNEL))
return;
+ pref_cpu = READ_ONCE(mm->sc_stat.cpu);
+
scoped_guard (cpus_read_lock) {
guard(rcu)();
get_scan_cpumasks(cpus, p);
for_each_cpu(cpu, cpus) {
- /* XXX sched_cluster_active */
- struct sched_domain *sd = rcu_dereference_all(per_cpu(sd_llc, cpu));
- unsigned long occ, m_occ = 0, a_occ = 0;
- int m_cpu = -1, i;
+ const struct cpumask *node_span =
+ cpumask_of_node(cpu_to_node(cpu));
+ unsigned long a_occ, a_n_occ = 0, m_llc_occ = 0;
+ int m_llc_cpu = -1, m_cpu, k, nr_llc = 0;
- if (!sd)
- continue;
+ for_each_cpu_and(k, node_span, cpus) {
+ /* XXX sched_cluster_active */
+ struct sched_domain *sd =
+ rcu_dereference_all(per_cpu(sd_llc, k));
- for_each_cpu(i, sched_domain_span(sd)) {
- occ = fraction_mm_sched(cpu_rq(i),
- per_cpu_ptr(mm->sc_stat.pcpu_sched, i));
- a_occ += occ;
- if (occ > m_occ) {
- m_occ = occ;
- m_cpu = i;
+ /*
+ * No sched domain, e.g. an isolated CPU: retire
+ * the bit so the node is not walked again for it.
+ */
+ if (!sd) {
+ __cpumask_clear_cpu(k, cpus);
+ continue;
}
- cur = rcu_dereference_all(cpu_rq(i)->curr);
- if (cur && !(cur->flags & (PF_EXITING | PF_KTHREAD)) &&
- cur->mm == mm)
- nr_running++;
+ a_occ = scan_llc_occ(mm, sched_domain_span(sd),
+ &m_cpu, &nr_running);
+
+ cpumask_andnot(cpus, cpus, sched_domain_span(sd));
+ nr_llc++;
+ if (a_occ > m_llc_occ) {
+ m_llc_occ = a_occ;
+ m_llc_cpu = m_cpu;
+ }
+ if (pref_cpu >= 0 && llc_id(pref_cpu) == llc_id(k))
+ curr_m_a_occ = a_occ;
+ /* record for numa node */
+ a_n_occ += a_occ;
}
/*
- * Compare the accumulated occupancy of each LLC. The
- * reason for using accumulated occupancy rather than average
- * per CPU occupancy is that it works better in asymmetric LLC
- * scenarios.
- * For example, if there are 2 threads in a 4CPU LLC and 3
- * threads in an 8CPU LLC, it might be better to choose the one
- * with 3 threads. However, this would not be the case if the
- * occupancy is divided by the number of CPUs in an LLC (i.e.,
- * if average per CPU occupancy is used).
- * Besides, NUMA balancing fault statistics behave similarly:
- * the total number of faults per node is compared rather than
- * the average number of faults per CPU. This strategy is also
- * followed here.
+ * Nothing scanned for this node, none of its CPUs in the
+ * mask is attached to a sched domain.
+ */
+ if (!nr_llc)
+ continue;
+
+ /*
+ * Remember the busiest LLC of the node the preference
+ * currently points at, as opposed to the LLC the
+ * preference itself points at, so that the LLC level
+ * decision can be taken once, after the whole scan.
*/
- if (a_occ > m_a_occ) {
- m_a_occ = a_occ;
- m_a_cpu = m_cpu;
+ if (pref_cpu >= 0 && m_llc_cpu >= 0 &&
+ cpu_to_node(pref_cpu) == cpu_to_node(m_llc_cpu)) {
+ pref_node_llc_occ = m_llc_occ;
+ pref_node_llc_cpu = m_llc_cpu;
}
- if (llc_id(cpu) == llc_id(READ_ONCE(mm->sc_stat.cpu)))
- curr_m_a_occ = a_occ;
+ if (a_n_occ > m_a_n_occ) {
+ m_a_n_occ = a_n_occ;
+ m_a_n_cpu = m_llc_cpu;
+ }
- cpumask_andnot(cpus, cpus, sched_domain_span(sd));
+ if (pref_cpu >= 0 &&
+ cpu_to_node(cpu) == cpu_to_node(pref_cpu))
+ curr_m_a_n_occ = a_n_occ;
}
}
- if (m_a_occ > (2 * curr_m_a_occ)) {
- /*
- * Avoid switching sc_stat.cpu too fast.
- * The reason to choose 2X is because:
- * 1. It is better to keep the preferred LLC stable,
- * rather than changing it frequently and cause migrations
- * 2. 2X means the new preferred LLC has at least 1 more
- * busy CPU than the old one(200% vs 100%, eg)
- * 3. 2X is chosen based on test results, as it delivers
- * the optimal performance gain so far.
- */
- WRITE_ONCE(mm->sc_stat.cpu, m_a_cpu);
- }
+ /*
+ * Avoid switching sc_stat.cpu too fast. The reason to choose 2X is
+ * because:
+ * 1. It is better to keep the preferred LLC stable, rather than
+ * changing it frequently and cause migrations
+ * 2. 2X means the new preferred LLC has at least 1 more busy CPU than
+ * the old one(200% vs 100%, eg)
+ * 3. 2X is chosen based on test results, as it delivers the optimal
+ * performance gain so far.
+ *
+ * Moving the preference to another node takes precedence over moving
+ * it to another LLC of the node it already points at.
+ */
+ if (m_a_n_occ > 2 * curr_m_a_n_occ)
+ new_cpu = m_a_n_cpu;
+ else if (pref_node_llc_cpu >= 0 && pref_node_llc_occ > 2 * curr_m_a_occ)
+ new_cpu = pref_node_llc_cpu;
+
+ if (new_cpu >= 0)
+ WRITE_ONCE(mm->sc_stat.cpu, new_cpu);
update_avg_scale(&mm->sc_stat.nr_running_avg, nr_running);
free_cpumask_var(cpus);
--
2.34.1
^ permalink raw reply related [flat|nested] 25+ messages in thread* [RFC PATCH v3 07/17] sched/topology: Add per-sd scratch for cache-aware load balancing
2026-10-29 2:20 [RFC PATCH v3 00/17] sched: Scale cache-aware aggregation at LLC granularity Jianyong Wu
` (5 preceding siblings ...)
2026-10-29 2:20 ` [RFC PATCH v3 06/17] sched/cache: Prioritize cache-preferred node selection over LLC selection Jianyong Wu
@ 2026-10-29 2:20 ` Jianyong Wu
2026-10-29 2:20 ` [RFC PATCH v3 08/17] sched/cache: Introduce helpers for task migration decisions Jianyong Wu
` (9 subsequent siblings)
16 siblings, 0 replies; 25+ messages in thread
From: Jianyong Wu @ 2026-10-29 2:20 UTC (permalink / raw)
To: Ingo Molnar, Peter Zijlstra, Juri Lelli, Vincent Guittot, Chen Yu,
Tim Chen
Cc: Dietmar Eggemann, Steven Rostedt, Ben Segall, Mel Gorman,
Valentin Schneider, K Prateek Nayak, Shrikanth Hegde, Phil Auld,
Andrew Morton, David Hildenbrand, maddy, Michael Ellerman, ljs,
linux-kernel, linux-mm, wujianyong, jianyong.wu, zhongyuan,
huangsj, wangfengyu, yingzhiwei
Cache-aware load balancing needs arrays of eligible LLC/node IDs and
affinity weights when scoring candidate runqueues. Selecting a source
runqueue by LLC load also needs a temporary CPU mask to avoid sampling
the same LLC more than once.
Allocate these buffers on the bottom sched domain of each CPU, next to
llc_counts, rather than allocating memory in the load balance path.
Size both affinity arrays by llc_max and the independent statistics mask
by cpumask_size().
Signed-off-by: Jianyong Wu <wujianyong@hygon.cn>
---
include/linux/sched/topology.h | 7 +++++++
kernel/sched/topology.c | 37 +++++++++++++++++++++++++++++++++-
2 files changed, 43 insertions(+), 1 deletion(-)
diff --git a/include/linux/sched/topology.h b/include/linux/sched/topology.h
index b5d9d7c2b8ad..e41fc64391c3 100644
--- a/include/linux/sched/topology.h
+++ b/include/linux/sched/topology.h
@@ -121,6 +121,13 @@ struct sched_domain {
unsigned int llc_max;
unsigned int *llc_counts __counted_by_ptr(llc_max);
unsigned long llc_bytes;
+ /*
+ * Scratch for the load balance affinity score, llc_max entries each.
+ * Only the bottom sd owns them, like llc_counts above.
+ */
+ int *affi_ids __counted_by_ptr(llc_max);
+ int *affi_weights __counted_by_ptr(llc_max);
+ struct cpumask *llc_stats_mask;
#endif
#ifdef CONFIG_SCHEDSTATS
diff --git a/kernel/sched/topology.c b/kernel/sched/topology.c
index 37f1eeae9b7b..7d65a4d7b0dd 100644
--- a/kernel/sched/topology.c
+++ b/kernel/sched/topology.c
@@ -643,6 +643,9 @@ static void destroy_sched_domain(struct sched_domain *sd)
#ifdef CONFIG_SCHED_CACHE
/* only the bottom sd has llc_counts array */
kfree(sd->llc_counts);
+ kfree(sd->affi_ids);
+ kfree(sd->affi_weights);
+ kfree(sd->llc_stats_mask);
#endif
kfree(sd);
}
@@ -846,10 +849,16 @@ cpu_attach_domain(struct sched_domain *sd, struct root_domain *rd, int cpu)
sd->llc_counts = tmp->llc_counts;
sd->llc_max = tmp->llc_max;
sd->llc_bytes = tmp->llc_bytes;
+ sd->affi_ids = tmp->affi_ids;
+ sd->affi_weights = tmp->affi_weights;
+ sd->llc_stats_mask = tmp->llc_stats_mask;
/* make sure destroy_sched_domain() does not free it */
tmp->llc_counts = NULL;
tmp->llc_max = 0;
tmp->llc_bytes = 0;
+ tmp->affi_ids = NULL;
+ tmp->affi_weights = NULL;
+ tmp->llc_stats_mask = NULL;
#endif
/*
* sched groups hold the flags of the child sched
@@ -1307,6 +1316,8 @@ static bool alloc_sd_llc(const struct cpumask *cpu_map,
{
struct sched_domain *sd, *top_llc, *parent;
unsigned int *p;
+ int *p_ids, *p_w;
+ struct cpumask *stats_mask;
int i;
for_each_cpu(i, cpu_map) {
@@ -1316,8 +1327,20 @@ static bool alloc_sd_llc(const struct cpumask *cpu_map,
p = kcalloc_node(max_lid + 1, sizeof(unsigned int),
GFP_KERNEL, cpu_to_node(i));
- if (!p)
+ /* Scratch for the load balance affinity score. */
+ p_ids = kcalloc_node(max_lid + 1, sizeof(int),
+ GFP_KERNEL, cpu_to_node(i));
+ p_w = kcalloc_node(max_lid + 1, sizeof(int),
+ GFP_KERNEL, cpu_to_node(i));
+ stats_mask = kmalloc_node(cpumask_size(), GFP_KERNEL,
+ cpu_to_node(i));
+ if (!p || !p_ids || !p_w || !stats_mask) {
+ kfree(p);
+ kfree(p_ids);
+ kfree(p_w);
+ kfree(stats_mask);
goto err;
+ }
top_llc = sd;
/*
@@ -1333,9 +1356,15 @@ static bool alloc_sd_llc(const struct cpumask *cpu_map,
sd->llc_max = max_lid + 1;
sd->llc_counts = p;
sd->llc_bytes = get_effective_llc_bytes(i, top_llc);
+ sd->affi_ids = p_ids;
+ sd->affi_weights = p_w;
+ sd->llc_stats_mask = stats_mask;
} else {
/* avoid memory leak */
kfree(p);
+ kfree(p_ids);
+ kfree(p_w);
+ kfree(stats_mask);
}
}
@@ -1345,9 +1374,15 @@ static bool alloc_sd_llc(const struct cpumask *cpu_map,
sd = *per_cpu_ptr(d->sd, i);
if (sd) {
kfree(sd->llc_counts);
+ kfree(sd->affi_ids);
+ kfree(sd->affi_weights);
+ kfree(sd->llc_stats_mask);
sd->llc_counts = NULL;
sd->llc_max = 0;
sd->llc_bytes = 0;
+ sd->affi_ids = NULL;
+ sd->affi_weights = NULL;
+ sd->llc_stats_mask = NULL;
}
}
--
2.34.1
^ permalink raw reply related [flat|nested] 25+ messages in thread* [RFC PATCH v3 08/17] sched/cache: Introduce helpers for task migration decisions
2026-10-29 2:20 [RFC PATCH v3 00/17] sched: Scale cache-aware aggregation at LLC granularity Jianyong Wu
` (6 preceding siblings ...)
2026-10-29 2:20 ` [RFC PATCH v3 07/17] sched/topology: Add per-sd scratch for cache-aware load balancing Jianyong Wu
@ 2026-10-29 2:20 ` Jianyong Wu
2026-10-30 3:04 ` sashiko-bot
2026-10-29 2:20 ` [RFC PATCH v3 09/17] sched/cache: Introduce rq affinity gain calculation Jianyong Wu
` (8 subsequent siblings)
16 siblings, 1 reply; 25+ messages in thread
From: Jianyong Wu @ 2026-10-29 2:20 UTC (permalink / raw)
To: Ingo Molnar, Peter Zijlstra, Juri Lelli, Vincent Guittot, Chen Yu,
Tim Chen
Cc: Dietmar Eggemann, Steven Rostedt, Ben Segall, Mel Gorman,
Valentin Schneider, K Prateek Nayak, Shrikanth Hegde, Phil Auld,
Andrew Morton, David Hildenbrand, maddy, Michael Ellerman, ljs,
linux-kernel, linux-mm, wujianyong, jianyong.wu, zhongyuan,
huangsj, wangfengyu, yingzhiwei
Cache-aware aggregation must accommodate workloads that need more than
one LLC. Use the node and intra-node LLC affinity sequences established
by earlier patches to distinguish moves toward the preferred region
from moves away from it, and consult utilization to permit expansion.
Add get_node_stats() to accumulate a node's utilization, capacity and LLC
count without allocating memory in the load balance path.
Extend fits_llc_capacity() to support both <= and < comparisons against
the aggregation threshold. Reaching the threshold after arrival is
allowed; departure checks reject a move if the remaining utilization
falls below the threshold.
For moves toward the preferred region, permit a move if the destination
LLC fits the task, or if the source is noticeably busier and remains no
lighter than the destination after the move.
For moves away, walk the cached affinity sequence from the source node
to the destination. Within one node, leave the source LLC at or above
the threshold, and permit moves that reduce LLC imbalance without
reversing the source and destination utilization ordering.
Across nodes, require the source node to remain at or above the
threshold after departure. An intervening node vetoes expansion if its
aggregate utilization still fits after charging one task per LLC, or
per pair of LLCs when its raw distance to the cache-preferred node is
less than the destination's. This estimates average LLC headroom rather
than guaranteeing room in an individual LLC.
At the destination, permit a fitting or balancing move; otherwise leave
the decision to generic load balancing. Nodes preceding the source or
following the destination do not participate in the decision.
Signed-off-by: Jianyong Wu <wujianyong@hygon.cn>
---
kernel/sched/fair.c | 185 ++++++++++++++++++++++++++++++++++++++++++--
1 file changed, 180 insertions(+), 5 deletions(-)
diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
index fe357d79b6e0..4eb7cede9080 100644
--- a/kernel/sched/fair.c
+++ b/kernel/sched/fair.c
@@ -10478,7 +10478,7 @@ static inline int task_is_ineligible_on_dst_cpu(struct task_struct *p, int dest_
*
* (default: ~50%, tunable via debugfs)
*/
-static bool fits_llc_capacity(unsigned long util, unsigned long max)
+static bool fits_llc_capacity(unsigned long util, unsigned long max, bool inclusive)
{
u32 aggr_pct = llc_overaggr_pct;
@@ -10489,6 +10489,9 @@ static bool fits_llc_capacity(unsigned long util, unsigned long max)
if (cpu_smt_num_threads == 1)
aggr_pct = (aggr_pct * 3 / 2);
+ if (inclusive)
+ return util * 100 <= max * aggr_pct;
+
return util * 100 < max * aggr_pct;
}
@@ -10592,8 +10595,8 @@ static enum llc_mig can_migrate_llc(int src_cpu, int dst_cpu,
src_util = src_util < tsk_util ? 0 : src_util - tsk_util;
dst_util = dst_util + tsk_util;
- if (!fits_llc_capacity(dst_util, dst_cap) &&
- !fits_llc_capacity(src_util, src_cap))
+ if (!fits_llc_capacity(dst_util, dst_cap, false) &&
+ !fits_llc_capacity(src_util, src_cap, false))
return mig_unrestricted;
if (to_pref) {
@@ -10603,7 +10606,7 @@ static enum llc_mig can_migrate_llc(int src_cpu, int dst_cpu,
* than the src, in which case migration will
* increase the imbalance too much.
*/
- if (!fits_llc_capacity(dst_util, dst_cap) &&
+ if (!fits_llc_capacity(dst_util, dst_cap, false) &&
util_greater(dst_util, src_util))
return mig_forbid;
} else {
@@ -10614,13 +10617,185 @@ static enum llc_mig can_migrate_llc(int src_cpu, int dst_cpu,
* of preferred LLC, leading to migration again
* back to preferred LLC.
*/
- if (fits_llc_capacity(src_util, src_cap) ||
+ if (fits_llc_capacity(src_util, src_cap, false) ||
!util_greater(src_util, dst_util))
return mig_forbid;
}
return mig_llc;
}
+/* Accumulate a NUMA node's utilization and capacity at LLC granularity. */
+static bool get_node_stats(int node, unsigned long *util_out,
+ unsigned long *cap_out, int *nr_llcs)
+{
+ unsigned long util = 0, cap = 0;
+ const struct cpumask *span;
+ int nr = 0;
+
+ if (!util_out || !cap_out || !nr_llcs)
+ return false;
+
+ for_each_llc_node_span(node, span) {
+ unsigned long util_tmp, cap_tmp;
+
+ if (!get_llc_stats(cpumask_first(span), &util_tmp, &cap_tmp))
+ return false;
+
+ util += util_tmp;
+ cap += cap_tmp;
+ nr++;
+ }
+
+ *util_out = util;
+ *cap_out = cap;
+ *nr_llcs = nr;
+
+ return true;
+}
+
+static enum llc_mig __maybe_unused can_migrate_llcs(int src_cpu, int dst_cpu,
+ struct task_struct *p, bool to_pref)
+{
+ unsigned long src_util, src_pre, src_cap, dst_util, dst_cap, dst_pre;
+ int target_node, src_node, dst_node, dst_distance;
+ int node, target_cpu = src_cpu, n_llc;
+ unsigned long tsk_util = 0;
+ bool got_src = false;
+
+ if (!get_llc_stats(src_cpu, &src_util, &src_cap) ||
+ !get_llc_stats(dst_cpu, &dst_util, &dst_cap))
+ return mig_unrestricted;
+
+ if (p) {
+ struct mm_struct *mm = p->mm;
+
+ if (mm)
+ target_cpu = READ_ONCE(mm->sc_stat.cpu);
+ target_cpu = target_cpu >= 0 ? target_cpu : src_cpu;
+
+ tsk_util = task_util(p);
+ }
+
+ /* Utilization of the destination LLC before the task moves in. */
+ dst_pre = dst_util;
+ src_pre = src_util;
+ src_util = src_util < tsk_util ? 0 : src_util - tsk_util;
+ dst_util = dst_util + tsk_util;
+
+ if (to_pref) {
+ if (fits_llc_capacity(dst_util, dst_cap, true))
+ return mig_llc;
+
+ if (util_greater(src_pre, dst_pre) &&
+ src_util >= dst_util)
+ return mig_llc;
+
+ return mig_forbid;
+ }
+
+ src_node = cpu_to_node(src_cpu);
+ dst_node = cpu_to_node(dst_cpu);
+ target_node = cpu_to_node(target_cpu);
+ dst_distance = node_distance(target_node, dst_node);
+
+ /*
+ * For moves away from the cache preferred node, examine the source,
+ * intervening nodes and destination in the cached affinity order.
+ */
+ for_each_affi_node(target_cpu, node) {
+ unsigned long nu = 0, nc = 0;
+
+ if (!got_src) {
+ if (node != src_node)
+ continue;
+ got_src = true;
+
+ if (src_node == dst_node) {
+ /* Leave the source LLC at or above the threshold. */
+ if (fits_llc_capacity(src_util, src_cap, false))
+ return mig_forbid;
+
+ if (util_greater(src_pre, dst_pre) &&
+ src_util >= dst_util)
+ return mig_llc;
+
+ /* Nodes beyond the destination cannot veto this move. */
+ break;
+ }
+
+ /* Cross-node moves must leave the source node filled. */
+ if (get_node_stats(src_node, &nu, &nc, &n_llc) && n_llc) {
+ nu = nu < tsk_util ? 0 : nu - tsk_util;
+ if (fits_llc_capacity(nu, nc, false))
+ return mig_forbid;
+ }
+ continue;
+ }
+
+ if (node != dst_node) {
+ if (!get_node_stats(node, &nu, &nc, &n_llc) || !n_llc)
+ continue;
+
+ /*
+ * Estimate average LLC headroom in intervening nodes.
+ * Charge one task per LLC, or per pair of LLCs when
+ * this node is closer to the target than the destination.
+ */
+ if (node_distance(target_node, node) < dst_distance)
+ nu += DIV_ROUND_UP(n_llc, 2) * tsk_util;
+ else
+ nu += n_llc * tsk_util;
+
+ if (fits_llc_capacity(nu, nc, true))
+ return mig_forbid;
+ continue;
+ }
+
+ if (fits_llc_capacity(dst_util, dst_cap, true))
+ return mig_llc;
+
+ if (util_greater(src_pre, dst_pre) && src_util >= dst_util)
+ return mig_llc;
+
+ break;
+ }
+
+ return mig_unrestricted;
+}
+
+/* Decide whether the destination precedes the source in the affinity order. */
+static bool __maybe_unused if_to_prefer(int src_cpu, int dst_cpu, int pref_llc)
+{
+ int src_rank, dst_rank, src_node, dst_node, pref_node;
+
+ if (pref_llc < 0)
+ return false;
+
+ src_node = cpu_to_node(src_cpu);
+ dst_node = cpu_to_node(dst_cpu);
+ pref_node = llc_to_node(pref_llc);
+ if (pref_node < 0)
+ return false;
+
+ if (src_node == dst_node) {
+ if (src_node == pref_node) {
+ src_rank = affi_llc_rank_of(pref_llc, llc_id(src_cpu),
+ pref_node);
+ dst_rank = affi_llc_rank_of(pref_llc, llc_id(dst_cpu),
+ pref_node);
+ if (src_rank < 0 || dst_rank < 0)
+ return false;
+ return src_rank > dst_rank;
+ }
+ /* Outside the cache preferred node, use ascending LLC IDs. */
+ return llc_id(src_cpu) > llc_id(dst_cpu);
+ }
+
+ src_rank = affi_node_rank_of(pref_node, src_node);
+ dst_rank = affi_node_rank_of(pref_node, dst_node);
+ return src_rank >= 0 && dst_rank >= 0 && src_rank > dst_rank;
+}
+
/*
* Check if task p can migrate from source LLC to
* destination LLC in terms of cache aware load balance.
--
2.34.1
^ permalink raw reply related [flat|nested] 25+ messages in thread* Re: [RFC PATCH v3 08/17] sched/cache: Introduce helpers for task migration decisions
2026-10-29 2:20 ` [RFC PATCH v3 08/17] sched/cache: Introduce helpers for task migration decisions Jianyong Wu
@ 2026-10-30 3:04 ` sashiko-bot
0 siblings, 0 replies; 25+ messages in thread
From: sashiko-bot @ 2026-10-30 3:04 UTC (permalink / raw)
To: Jianyong Wu, Ingo Molnar, Peter Zijlstra, Juri Lelli,
Vincent Guittot, Chen Yu, Tim Chen
Cc: Dietmar Eggemann, Steven Rostedt, Ben Segall, Mel Gorman,
Valentin Schneider, K Prateek Nayak, Shrikanth Hegde, Phil Auld,
Andrew Morton, David Hildenbrand, maddy, Michael Ellerman, ljs,
linux-mm, jianyong.wu, zhongyuan, huangsj, wangfengyu, yingzhiwei
Thank you for your contribution! Sashiko AI review found 1 potential issue(s) to consider:
- [Medium] sched/cache: can_migrate_llcs() misapplies node walk when dst precedes src
--
commit c7cd924467c2448429791ac003c69c23764da05a
Author: Jianyong Wu <wujianyong@hygon.cn>
sched/cache: Introduce helpers for task migration decisions
This commit introduces get_node_stats(), can_migrate_llcs(), and
if_to_prefer(), and extends fits_llc_capacity() to support cache-aware task
migration decisions across multiple LLCs and NUMA nodes.
> diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
> index fe357d79b6e06..4eb7cede9080f 100644
> --- a/kernel/sched/fair.c
> +++ b/kernel/sched/fair.c
[ ... ]
> @@ -10614,13 +10617,185 @@ static enum llc_mig can_migrate_llc(int src_cpu, int dst_cpu,
[ ... ]
> +static enum llc_mig __maybe_unused can_migrate_llcs(int src_cpu, int dst_cpu,
> + struct task_struct *p, bool to_pref)
> +{
> + unsigned long src_util, src_pre, src_cap, dst_util, dst_cap, dst_pre;
> + int target_node, src_node, dst_node, dst_distance;
> + int node, target_cpu = src_cpu, n_llc;
> + unsigned long tsk_util = 0;
> + bool got_src = false;
> +
> + if (!get_llc_stats(src_cpu, &src_util, &src_cap) ||
> + !get_llc_stats(dst_cpu, &dst_util, &dst_cap))
> + return mig_unrestricted;
> +
> + if (p) {
> + struct mm_struct *mm = p->mm;
> +
> + if (mm)
> + target_cpu = READ_ONCE(mm->sc_stat.cpu);
> + target_cpu = target_cpu >= 0 ? target_cpu : src_cpu;
> +
> + tsk_util = task_util(p);
> + }
[ ... ]
> + src_node = cpu_to_node(src_cpu);
> + dst_node = cpu_to_node(dst_cpu);
> + target_node = cpu_to_node(target_cpu);
> + dst_distance = node_distance(target_node, dst_node);
> +
> + /*
> + * For moves away from the cache preferred node, examine the source,
> + * intervening nodes and destination in the cached affinity order.
> + */
> + for_each_affi_node(target_cpu, node) {
> + unsigned long nu = 0, nc = 0;
> +
> + if (!got_src) {
> + if (node != src_node)
> + continue;
> + got_src = true;
[ ... ]
> + /* Cross-node moves must leave the source node filled. */
> + if (get_node_stats(src_node, &nu, &nc, &n_llc) && n_llc) {
> + nu = nu < tsk_util ? 0 : nu - tsk_util;
> + if (fits_llc_capacity(nu, nc, false))
> + return mig_forbid;
> + }
> + continue;
> + }
> +
> + if (node != dst_node) {
> + if (!get_node_stats(node, &nu, &nc, &n_llc) || !n_llc)
> + continue;
> +
> + /*
> + * Estimate average LLC headroom in intervening nodes.
> + * Charge one task per LLC, or per pair of LLCs when
> + * this node is closer to the target than the destination.
> + */
> + if (node_distance(target_node, node) < dst_distance)
> + nu += DIV_ROUND_UP(n_llc, 2) * tsk_util;
> + else
> + nu += n_llc * tsk_util;
> +
> + if (fits_llc_capacity(nu, nc, true))
> + return mig_forbid;
> + continue;
> + }
> +
> + if (fits_llc_capacity(dst_util, dst_cap, true))
> + return mig_llc;
> +
> + if (util_greater(src_pre, dst_pre) && src_util >= dst_util)
> + return mig_llc;
> +
> + break;
> + }
[Severity: Medium]
In kernel/sched/fair.c, what happens in can_migrate_llcs() when to_pref is
false and src_node != dst_node, yet dst_node precedes src_node in the
for_each_affi_node(target_cpu, node) walk?
The loop skips every node before src_node while got_src is false, so
dst_node is passed before got_src becomes true. Once node == src_node sets
got_src = true, every subsequent node in the affinity sequence satisfies
node != dst_node. Those trailing nodes are then evaluated as intervening
nodes and can veto the move with mig_forbid, while the destination checks at
node == dst_node are never reached, contrary to the commit message guarantee
that nodes following the destination do not participate in the decision.
When wired up to can_migrate_llc_task() and alb_break_llc() in the
subsequent commit ("sched/cache: Apply multi-LLC aggregation policy to task
migration"), dst_node can precede src_node in target_cpu's affinity order
even when to_pref is false in several cases:
1. Both can_migrate_llc_task() and alb_break_llc() read mm->sc_stat.cpu once
to compute pref_llc for if_to_prefer(), and can_migrate_llcs() reads
mm->sc_stat.cpu a second time via READ_ONCE(mm->sc_stat.cpu). A
concurrent update in task_cache_work() or account_mm_sched() can cause
if_to_prefer() to return false for the old CPU while can_migrate_llcs()
reads a new target_cpu whose target_node ranks dst_node before src_node.
2. In alb_break_llc(), pref_llc is only derived from mm->sc_stat.cpu when
cur->sched_class == &fair_sched_class (otherwise remaining -1 so
if_to_prefer() returns false), whereas can_migrate_llcs() unconditionally
reads target_cpu = READ_ONCE(p->mm->sc_stat.cpu).
3. In if_to_prefer(), llc_to_node(pref_llc) can return -1 (for example, if
rebuild_llc_node_map() failed allocation), causing if_to_prefer() to
return false while can_migrate_llcs() resolves target_node via
cpu_to_node(target_cpu) and walks for_each_affi_node(target_cpu, node).
Should the caller pass a single consistent target_cpu or preferred node to
both helpers, or should can_migrate_llcs() handle encountering dst_node
before src_node during the affinity walk?
--
Sashiko AI review · https://sashiko.dev/#/patchset/20261029022036.4002331-1-wujianyong@hygon.cn?part=8
^ permalink raw reply [flat|nested] 25+ messages in thread
* [RFC PATCH v3 09/17] sched/cache: Introduce rq affinity gain calculation
2026-10-29 2:20 [RFC PATCH v3 00/17] sched: Scale cache-aware aggregation at LLC granularity Jianyong Wu
` (7 preceding siblings ...)
2026-10-29 2:20 ` [RFC PATCH v3 08/17] sched/cache: Introduce helpers for task migration decisions Jianyong Wu
@ 2026-10-29 2:20 ` Jianyong Wu
2026-10-30 3:05 ` sashiko-bot
2026-10-29 2:20 ` [RFC PATCH v3 10/17] sched/cache: Pick the source rq/group with the highest affinity gain Jianyong Wu
` (7 subsequent siblings)
16 siblings, 1 reply; 25+ messages in thread
From: Jianyong Wu @ 2026-10-29 2:20 UTC (permalink / raw)
To: Ingo Molnar, Peter Zijlstra, Juri Lelli, Vincent Guittot, Chen Yu,
Tim Chen
Cc: Dietmar Eggemann, Steven Rostedt, Ben Segall, Mel Gorman,
Valentin Schneider, K Prateek Nayak, Shrikanth Hegde, Phil Auld,
Andrew Morton, David Hildenbrand, maddy, Michael Ellerman, ljs,
linux-kernel, linux-mm, wujianyong, jianyong.wu, zhongyuan,
huangsj, wangfengyu, yingzhiwei
The current cache-aware source selection counts tasks whose preferred LLC
is the destination LLC. This misses opportunities to aggregate a workload
across multiple LLCs when moving toward the preferred LLC improves
affinity even without reaching that LLC.
For example, suppose thread group A prefers LLC0 and its LLC affinity
sequence is {LLC0, LLC1, LLC2}. A task of A moving from LLC2 to LLC1
improves affinity because LLC1 precedes LLC2 in that sequence. However,
that task does not contribute to the existing count of tasks preferring
LLC1. A source rq containing such tasks should receive credit for this
potential improvement.
Introduce helpers to calculate an affinity-gain score for a candidate
source rq and a fixed destination CPU. The calculation has two steps:
1. Identify the preferred LLCs or cache-preferred nodes for which moving
from source to destination improves affinity.
2. Iterate only those selected LLCs or nodes and sum the counts of tasks
on the source rq with those preferences, applying the corresponding
affinity weights.
For NUMA-domain balancing, define the raw distance difference to each
cache-preferred node i as:
D(i) = node_distance(src_node, i) - node_distance(dst_node, i)
Step 1 selects node i if D(i) > 0, or if D(i) == 0 and destination
precedes source in the affinity sequence rooted at i. Let E be this set
of eligible nodes.
Step 2 iterates only the nodes in E. For each node, sum the source rq's
counts for preferred LLCs belonging to that node, then apply its weight:
W(i) = clamp(D(i), 1, 1024), for i in E
S = sum_{i in E}(W(i) * task_count_for_cache_preferred_node(i))
For eligible equal-distance moves, the weight is 1. The fixed node order
determines eligibility, while its rank difference does not affect the
weight.
For LLC-level balancing, source and destination are in the same node.
When a task's preferred LLC is in that node, use the affinity sequence
rooted at that LLC to determine whether destination precedes source.
For preferred LLCs on other nodes, use ascending LLC ID order within the
source/destination node. Each eligible task contributes a unit weight:
S = sum_i(task_count_for_preferred_llc(i))
Here, i ranges over the preferred LLCs selected in the first step. Thus,
the LLC order determines eligibility without weighting the score by the
rank difference.
Subsequent patches use these helpers for source rq and group selection.
Signed-off-by: Jianyong Wu <wujianyong@hygon.cn>
---
kernel/sched/fair.c | 213 ++++++++++++++++++++++++++++++++++++++++++++
1 file changed, 213 insertions(+)
diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
index 4eb7cede9080..eb08ae66f465 100644
--- a/kernel/sched/fair.c
+++ b/kernel/sched/fair.c
@@ -11999,6 +11999,219 @@ static bool update_llc_busiest(struct lb_env *env,
*/
return sgs->nr_pref_dst_llc > busiest->nr_pref_dst_llc;
}
+
+/*
+ * Get preferred LLCs for which the destination precedes the source in
+ * that LLC's intra-node affinity order. For preferred LLCs outside the
+ * source/destination node, include them only when src_llc > dst_llc,
+ * following ascending LLC ID order within that node.
+ */
+static int get_affi_llcs(int src_llc, int dst_llc,
+ int *affi_llcs, int llc_max)
+{
+ int j = 0, src_rank, dst_rank, cur_node, node, llc;
+
+ if (src_llc == dst_llc)
+ return 0;
+
+ cur_node = llc_to_node(src_llc);
+ if (cur_node != llc_to_node(dst_llc))
+ return 0;
+
+ for_each_node(node) {
+ for_each_llc_of_node(llc, node) {
+ if (llc >= llc_max)
+ continue;
+ if (node == cur_node) {
+ src_rank = affi_llc_rank_of(llc, src_llc, cur_node);
+ dst_rank = affi_llc_rank_of(llc, dst_llc, cur_node);
+ if (src_rank < 0 || dst_rank < 0)
+ continue;
+ if (src_rank > dst_rank)
+ affi_llcs[j++] = llc;
+ } else {
+ if (src_llc > dst_llc)
+ affi_llcs[j++] = llc;
+ }
+ }
+ }
+
+ return j;
+}
+
+static int get_affi_numas(int src_node, int dst_node, int *affi_nodes, int *affi, int max)
+{
+ int j = 0, src_dist, dst_dist, node;
+
+ for_each_node(node) {
+ if (j >= max)
+ break;
+ src_dist = node_distance(src_node, node);
+ dst_dist = node_distance(dst_node, node);
+ if (src_dist < 0 || dst_dist < 0)
+ continue;
+ if (src_dist == dst_dist) {
+ src_dist = affi_node_rank_of(node, src_node);
+ dst_dist = affi_node_rank_of(node, dst_node);
+ if (src_dist > dst_dist) {
+ affi[j] = 1;
+ affi_nodes[j++] = node;
+ }
+ continue;
+ }
+
+ if (src_dist > dst_dist) {
+ affi[j] = clamp(src_dist - dst_dist, 0, 1024);
+ affi_nodes[j++] = node;
+ }
+ }
+
+ return j;
+}
+
+static int calc_affinity_numa_score(struct sched_domain *sd, int src_cpu, int dst_cpu,
+ int *affi_node, int *affi, int *last_node, int *num, int llc_max)
+{
+ int llc, src_node, dst_node, tmp_node, score = 0, numa_count, node_max;
+
+ src_node = cpu_to_node(src_cpu);
+ dst_node = cpu_to_node(dst_cpu);
+ node_max = min_t(int, nr_node_ids, llc_max);
+ /*
+ * The destination stays fixed during this source-rq scan. Reuse the
+ * eligible node list and weights for consecutive source CPUs in the
+ * same node; each rq's task counts are applied below.
+ */
+ if (src_node != *last_node) {
+ *last_node = src_node;
+ *num = get_affi_numas(src_node, dst_node, affi_node,
+ affi, node_max);
+ }
+
+ for (int i = 0; i < *num; i++) {
+ if ((unsigned int)affi_node[i] < nr_node_ids) {
+ tmp_node = affi_node[i];
+ numa_count = 0;
+ for_each_llc_of_node(llc, tmp_node) {
+ if (llc >= sd->llc_max)
+ continue;
+ numa_count += sd->llc_counts[llc];
+ }
+ score += numa_count * affi[i];
+ }
+ }
+
+ return score;
+}
+
+static int calc_affinity_llc_score(struct sched_domain *sd, struct sched_domain *sd_rq,
+ int src_cpu, int dst_cpu, int *affi_llc,
+ int *last_llc, int *num, int llc_max)
+{
+ int src_llc, dst_llc, score = 0;
+
+ if (sd->flags & (SD_NUMA | SD_SHARE_LLC))
+ return 0;
+
+ src_llc = llc_id(src_cpu);
+ dst_llc = llc_id(dst_cpu);
+
+ /*
+ * The destination stays fixed during this source-rq scan. Reuse the
+ * eligible LLC list for consecutive source CPUs in the same LLC;
+ * each rq's task counts are applied below.
+ */
+ if (src_llc != *last_llc) {
+ *last_llc = src_llc;
+ *num = get_affi_llcs(src_llc, dst_llc, affi_llc, llc_max);
+ }
+
+ for (int i = 0; i < *num; i++) {
+ if ((unsigned int)affi_llc[i] < llc_max)
+ score += sd_rq->llc_counts[affi_llc[i]];
+ }
+
+ return score;
+}
+
+/*
+ * Scratch arrays used while scoring rqs during load balancing. They live on
+ * the bottom sched_domain of the CPU running the balance, so they share the
+ * sched_domain lifetime and need neither a separate allocation nor any RCU
+ * handling of their own. Load balancing runs with preemption disabled, so
+ * this_rq() stays stable for a whole pass, and two CPUs balancing at the same
+ * time each get their own arrays.
+ */
+static void __maybe_unused lb_affi_scratch(int **ids, int **weights, int *llc_max)
+{
+ struct sched_domain *sd = rcu_dereference_all(this_rq()->sd);
+
+ *ids = sd ? sd->affi_ids : NULL;
+ *weights = sd ? sd->affi_weights : NULL;
+ *llc_max = sd ? sd->llc_max : 0;
+}
+
+/*
+ * To locate a source sched group/rq during load balancing, we require
+ * a metric to evaluate the migration benefit of each rq. For cache-aware
+ * scheduling, the primary optimization target is affinity improvement.
+ *
+ * This implementation quantifies affinity gains for candidate group/rq by
+ * computing an affinity score for each rq.
+ *
+ * The score is calculated for a given source and destination. Domains
+ * with SD_NUMA use NUMA-node granularity. Non-NUMA domains spanning
+ * multiple LLCs within one node use LLC granularity. This includes a
+ * package domain on a single-node system with multiple LLCs, as well as
+ * a NODE domain on a multi-node system.
+ *
+ * A task's cache preferred node is the node containing its preferred LLC.
+ * At NUMA level, score the cache preferred nodes for which moving from
+ * source to destination improves affinity. If the raw distances differ,
+ * use the positive distance difference as the weight. If they tie, use
+ * the cache preferred node's fixed affinity order to decide whether the
+ * move is eligible, with a unit weight:
+ *
+ * Di = node_distance(src_node, NUMAi)
+ * - node_distance(dst_node, NUMAi)
+ * Ai = clamp(Di, 0, 1024) if Di > 0
+ * = 1 if Di == 0 and dst ranks
+ * before src for NUMAi
+ * = 0 otherwise
+ * Rt_i = sum_j(rq->sd->llc_counts[j]), LLCj belongs to NUMAi
+ * Wi = Rt_i * Ai
+ * p = sum_i(Wi)
+ *
+ * At LLC level, the source and destination LLCs are in the same node.
+ * For each preferred LLC in that node, add the source rq's task count if the
+ * destination precedes the source in its fixed LLC affinity order.
+ * For preferred LLCs outside that node, include their task counts only
+ * when src_llc > dst_llc, following ascending LLC ID order within the
+ * source/destination node. Each eligible task contributes a unit weight.
+ *
+ * @last_node and @num cache the affinity vector while candidate runqueues
+ * are scanned for one load-balance destination. The destination CPU must
+ * remain unchanged for the lifetime of the cache. The caller must
+ * initialize *@last_node to -1 and *@num to 0.
+ */
+static int __maybe_unused
+calc_affinity_score(struct sched_domain *sd, struct rq *rq, int src_cpu,
+ int dst_cpu, int *affi_nodes, int *affi, int *last_node,
+ int *num, int llc_max)
+{
+ struct sched_domain *sd_rq = rcu_dereference_all(rq->sd);
+
+ if (!affi_nodes || !affi || !last_node ||
+ !num || !sd || !sd_rq || !llc_max)
+ return 0;
+
+ if (sd->flags & SD_NUMA)
+ return calc_affinity_numa_score(sd_rq, src_cpu, dst_cpu, affi_nodes,
+ affi, last_node, num, llc_max);
+
+ return calc_affinity_llc_score(sd, sd_rq, src_cpu, dst_cpu, affi_nodes,
+ last_node, num, llc_max);
+}
#else
static inline void record_sg_llc_stats(struct lb_env *env, struct sg_lb_stats *sgs,
struct sched_group *group)
--
2.34.1
^ permalink raw reply related [flat|nested] 25+ messages in thread* Re: [RFC PATCH v3 09/17] sched/cache: Introduce rq affinity gain calculation
2026-10-29 2:20 ` [RFC PATCH v3 09/17] sched/cache: Introduce rq affinity gain calculation Jianyong Wu
@ 2026-10-30 3:05 ` sashiko-bot
0 siblings, 0 replies; 25+ messages in thread
From: sashiko-bot @ 2026-10-30 3:05 UTC (permalink / raw)
To: Jianyong Wu, Ingo Molnar, Peter Zijlstra, Juri Lelli,
Vincent Guittot, Chen Yu, Tim Chen
Cc: Dietmar Eggemann, Steven Rostedt, Ben Segall, Mel Gorman,
Valentin Schneider, K Prateek Nayak, Shrikanth Hegde, Phil Auld,
Andrew Morton, David Hildenbrand, maddy, Michael Ellerman, ljs,
linux-mm, jianyong.wu, zhongyuan, huangsj, wangfengyu, yingzhiwei
Thank you for your contribution! Sashiko AI review found 5 potential issue(s) to consider:
- [Critical] sched/fair: unbounded affi_llcs write in get_affi_llcs()
- [High] sched/fair: wrong llc_max bound in calc_affinity_llc_score()
- [Medium] sched/fair: missing negative node check in get_affi_llcs()
- [Medium] sched/fair: missing negative rank check in get_affi_numas()
- [Medium] sched/fair: LLC-less nodes truncate NUMA list in get_affi_numas()
--
commit c22c2cf580aaca6a95248753109bc427527a2a88
Author: Jianyong Wu <wujianyong@hygon.cn>
sched/cache: Introduce rq affinity gain calculation
This commit introduces helper functions to compute NUMA and LLC affinity
gain scores for candidate source runqueues during cache-aware load
balancing.
> diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
> index 4eb7cede9080f..eb08ae66f4650 100644
> --- a/kernel/sched/fair.c
> +++ b/kernel/sched/fair.c
> @@ -11999,6 +11999,219 @@ static bool update_llc_busiest(struct lb_env *env,
> */
> return sgs->nr_pref_dst_llc > busiest->nr_pref_dst_llc;
> }
> +
> +/*
> + * Get preferred LLCs for which the destination precedes the source in
> + * that LLC's intra-node affinity order. For preferred LLCs outside the
> + * source/destination node, include them only when src_llc > dst_llc,
> + * following ascending LLC ID order within that node.
> + */
> +static int get_affi_llcs(int src_llc, int dst_llc,
> + int *affi_llcs, int llc_max)
> +{
> + int j = 0, src_rank, dst_rank, cur_node, node, llc;
> +
> + if (src_llc == dst_llc)
> + return 0;
> +
> + cur_node = llc_to_node(src_llc);
> + if (cur_node != llc_to_node(dst_llc))
> + return 0;
[Severity: Medium]
What happens in get_affi_llcs() when llc_to_node(src_llc) and
llc_to_node(dst_llc) both return -1 (NUMA_NO_NODE) while src_llc != dst_llc?
In kernel/sched/topology.c, llc_to_node() returns -1 if llc < 0, if
llc_to_node_map is NULL, or if llc >= map->nr_llc (for instance during
build_sched_domains() between cpu_attach_domain() attaching newly allocated
sd_llc_id values and rebuild_llc_node_map() publishing the updated map, or
when sched_domains_free_llc_id() resets sd_llc_id to -1).
If both calls return -1, cur_node != llc_to_node(dst_llc) is false, and in
the loop below node == cur_node is false for every valid node, so every LLC
across all nodes takes the remote-node else branch and is added whenever
src_llc > dst_llc. Should get_affi_llcs() return 0 when cur_node < 0?
> +
> + for_each_node(node) {
> + for_each_llc_of_node(llc, node) {
> + if (llc >= llc_max)
> + continue;
> + if (node == cur_node) {
> + src_rank = affi_llc_rank_of(llc, src_llc, cur_node);
> + dst_rank = affi_llc_rank_of(llc, dst_llc, cur_node);
> + if (src_rank < 0 || dst_rank < 0)
> + continue;
> + if (src_rank > dst_rank)
> + affi_llcs[j++] = llc;
> + } else {
> + if (src_llc > dst_llc)
> + affi_llcs[j++] = llc;
> + }
> + }
> + }
[Severity: Critical]
Can get_affi_llcs() overflow affi_llcs[] (which points to sd->affi_ids,
allocated with llc_max entries in alloc_sd_llc()) if llc_to_node_map is
updated concurrently?
Unlike get_affi_numas(), which checks if (j >= max) break, get_affi_llcs()
only checks if (llc >= llc_max) continue and does not bound j against
llc_max. However, for_each_llc_of_node() in kernel/sched/sched.h enters a
separate RCU read-side section on each node iteration:
#define for_each_llc_of_node(llc, node) \
scoped_guard(rcu) \
for (struct llc_node_iter __ln_iter = \
llc_node_iter_begin(node); \
((llc) = llc_node_iter_next(&__ln_iter)) >= 0;)
If rebuild_llc_node_map() publishes a new llc_to_node_map during CPU hotplug
or sched_domain rebuilds where an LLC ID freed on a lower-numbered node is
reallocated to a higher-numbered node, get_affi_llcs() can observe the same
LLC ID (< llc_max) in multiple node iterations and increment j past llc_max,
writing past the end of sd->affi_ids and causing calc_affinity_llc_score() to
read out of bounds as well. Should get_affi_llcs() check j >= llc_max (or
hold a single RCU read lock across the entire node scan)?
> +
> + return j;
> +}
> +
> +static int get_affi_numas(int src_node, int dst_node, int *affi_nodes, int *affi, int max)
> +{
> + int j = 0, src_dist, dst_dist, node;
> +
> + for_each_node(node) {
> + if (j >= max)
> + break;
> + src_dist = node_distance(src_node, node);
> + dst_dist = node_distance(dst_node, node);
> + if (src_dist < 0 || dst_dist < 0)
> + continue;
> + if (src_dist == dst_dist) {
> + src_dist = affi_node_rank_of(node, src_node);
> + dst_dist = affi_node_rank_of(node, dst_node);
> + if (src_dist > dst_dist) {
> + affi[j] = 1;
> + affi_nodes[j++] = node;
> + }
> + continue;
> + }
[Severity: Medium]
Should get_affi_numas() verify that src_dist and dst_dist are non-negative
after calling affi_node_rank_of(), and bail out early when
src_node == dst_node?
In kernel/sched/topology.c, affi_node_rank_of() takes its own RCU lock per
call and returns -1 if affi_node_order is NULL (for example if
rebuild_node_order() fails allocation and publishes NULL) or if a node ID is
out of bounds.
If affi_node_rank_of(node, src_node) returns a valid rank (>= 0) and a
concurrent update causes affi_node_rank_of(node, dst_node) to return -1,
src_dist > dst_dist evaluates to true (even when src_node == dst_node) and
adds the node with weight 1. By comparison, get_affi_llcs() checks
if (src_rank < 0 || dst_rank < 0) continue before comparing ranks.
[ ... ]
> +static int calc_affinity_numa_score(struct sched_domain *sd, int src_cpu, int dst_cpu,
> + int *affi_node, int *affi, int *last_node, int *num, int llc_max)
> +{
> + int llc, src_node, dst_node, tmp_node, score = 0, numa_count, node_max;
> +
> + src_node = cpu_to_node(src_cpu);
> + dst_node = cpu_to_node(dst_cpu);
> + node_max = min_t(int, nr_node_ids, llc_max);
> + /*
> + * The destination stays fixed during this source-rq scan. Reuse the
> + * eligible node list and weights for consecutive source CPUs in the
> + * same node; each rq's task counts are applied below.
> + */
> + if (src_node != *last_node) {
> + *last_node = src_node;
> + *num = get_affi_numas(src_node, dst_node, affi_node,
> + affi, node_max);
> + }
[Severity: Medium]
Can CPU-less or offline NUMA nodes cause get_affi_numas() to drop active
cache-preferred nodes when nr_node_ids > llc_max?
In alloc_sd_llc(), sd->affi_ids and sd->affi_weights are sized to llc_max
(the number of LLC IDs for online CPUs), so calc_affinity_numa_score() caps
node_max at min_t(int, nr_node_ids, llc_max).
However, get_affi_numas() iterates over for_each_node(node) (all possible
nodes in node_possible_map, including CPU-less HBM/CXL memory nodes or
offline nodes that have no LLCs) and stops once j >= max. Any lower-numbered
node without LLCs takes a slot in affi_node[] while always producing
numa_count == 0 in the for_each_llc_of_node(llc, tmp_node) loop below, which
can truncate higher-numbered NUMA nodes that actually have LLCs and tasks.
[ ... ]
> +static int calc_affinity_llc_score(struct sched_domain *sd, struct sched_domain *sd_rq,
> + int src_cpu, int dst_cpu, int *affi_llc,
> + int *last_llc, int *num, int llc_max)
> +{
> + int src_llc, dst_llc, score = 0;
> +
> + if (sd->flags & (SD_NUMA | SD_SHARE_LLC))
> + return 0;
> +
> + src_llc = llc_id(src_cpu);
> + dst_llc = llc_id(dst_cpu);
> +
> + /*
> + * The destination stays fixed during this source-rq scan. Reuse the
> + * eligible LLC list for consecutive source CPUs in the same LLC;
> + * each rq's task counts are applied below.
> + */
> + if (src_llc != *last_llc) {
> + *last_llc = src_llc;
> + *num = get_affi_llcs(src_llc, dst_llc, affi_llc, llc_max);
> + }
> +
> + for (int i = 0; i < *num; i++) {
> + if ((unsigned int)affi_llc[i] < llc_max)
> + score += sd_rq->llc_counts[affi_llc[i]];
> + }
[Severity: High]
Does calc_affinity_llc_score() check the wrong llc_max bound before indexing
sd_rq->llc_counts[]?
In lb_affi_scratch(), llc_max is read from this_rq()->sd->llc_max (the
balancing CPU's bottom sched_domain), whereas sd_rq is
rcu_dereference_all(rq->sd) for the candidate source runqueue, whose
sd_rq->llc_counts array is sized by sd_rq->llc_max (and annotated with
__counted_by_ptr(llc_max) in struct sched_domain).
While calc_affinity_numa_score() checks if (llc >= sd->llc_max) against
sd_rq->llc_max, calc_affinity_llc_score() checks
if ((unsigned int)affi_llc[i] < llc_max) against the balancing CPU's llc_max.
If sd_rq->llc_max < llc_max (for example while build_sched_domains() attaches
updated domains one CPU at a time under RCU, across reused vs. rebuilt cpuset
partitions during NOHZ balance, or if alloc_sd_llc() failed on sd_rq leaving
sd_rq->llc_max == 0 and sd_rq->llc_counts == NULL), indexing
sd_rq->llc_counts[affi_llc[i]] can read out of bounds or dereference NULL.
Should this check against sd_rq->llc_max as well?
--
Sashiko AI review · https://sashiko.dev/#/patchset/20261029022036.4002331-1-wujianyong@hygon.cn?part=9
^ permalink raw reply [flat|nested] 25+ messages in thread
* [RFC PATCH v3 10/17] sched/cache: Pick the source rq/group with the highest affinity gain
2026-10-29 2:20 [RFC PATCH v3 00/17] sched: Scale cache-aware aggregation at LLC granularity Jianyong Wu
` (8 preceding siblings ...)
2026-10-29 2:20 ` [RFC PATCH v3 09/17] sched/cache: Introduce rq affinity gain calculation Jianyong Wu
@ 2026-10-29 2:20 ` Jianyong Wu
2026-10-30 3:05 ` sashiko-bot
2026-10-29 2:20 ` [RFC PATCH v3 11/17] sched/cache: Drop prefer_sibling restriction for llc_balance Jianyong Wu
` (6 subsequent siblings)
16 siblings, 1 reply; 25+ messages in thread
From: Jianyong Wu @ 2026-10-29 2:20 UTC (permalink / raw)
To: Ingo Molnar, Peter Zijlstra, Juri Lelli, Vincent Guittot, Chen Yu,
Tim Chen
Cc: Dietmar Eggemann, Steven Rostedt, Ben Segall, Mel Gorman,
Valentin Schneider, K Prateek Nayak, Shrikanth Hegde, Phil Auld,
Andrew Morton, David Hildenbrand, maddy, Michael Ellerman, ljs,
linux-kernel, linux-mm, wujianyong, jianyong.wu, zhongyuan,
huangsj, wangfengyu, yingzhiwei
Current cache-aware source group/rq selection only counts tasks whose
preferred LLC is the destination LLC. It cannot identify aggregation
opportunities where the destination LLC is not a task's preferred LLC,
but moving there would improve affinity according to the LLC or NUMA
node affinity order.
Use the affinity gain calculation introduced in the previous commit
to select the source group and runqueue with the highest affinity
gain for the given destination.
Enable this calculation only when llc_aggr_tolerance is greater than 1,
allowing aggregation across multiple LLCs. When the tolerance is 1,
aggregation is limited to workloads that fit in a single LLC. In that
case, retain the original selection metric: count tasks whose preferred
LLC is the destination LLC. This targets aggregation directly toward
the preferred LLC without encouraging intermediate moves to other LLCs,
and avoids the additional affinity calculation overhead.
Signed-off-by: Jianyong Wu <wujianyong@hygon.cn>
---
kernel/sched/fair.c | 82 +++++++++++++++++++++++++++++++++------------
1 file changed, 61 insertions(+), 21 deletions(-)
diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
index eb08ae66f465..e9a803433b16 100644
--- a/kernel/sched/fair.c
+++ b/kernel/sched/fair.c
@@ -10339,6 +10339,10 @@ struct lb_env {
enum fbq_type fbq_type;
enum migration_type migration_type;
struct list_head tasks;
+#ifdef CONFIG_SCHED_CACHE
+ /* Aggregation tolerance sampled once per balance pass. */
+ unsigned int tol;
+#endif
};
/*
@@ -10653,7 +10657,7 @@ static bool get_node_stats(int node, unsigned long *util_out,
return true;
}
-static enum llc_mig __maybe_unused can_migrate_llcs(int src_cpu, int dst_cpu,
+static enum llc_mig can_migrate_llcs(int src_cpu, int dst_cpu,
struct task_struct *p, bool to_pref)
{
unsigned long src_util, src_pre, src_cap, dst_util, dst_cap, dst_pre;
@@ -11504,7 +11508,7 @@ struct sg_lb_stats {
unsigned int nr_preferred_running;
#endif
#ifdef CONFIG_SCHED_CACHE
- unsigned int nr_pref_dst_llc;
+ unsigned int affinity_score; /* Affinity gain toward the destination */
#endif
};
@@ -11962,8 +11966,8 @@ static void record_sg_llc_stats(struct lb_env *env,
}
/*
- * Do LLC balance on sched group that contains LLC, and have tasks preferring
- * to run on LLC in idle dst_cpu.
+ * Consider cache-aware balancing for a group whose tasks would gain
+ * affinity by moving to the destination.
*/
static inline bool llc_balance(struct lb_env *env, struct sg_lb_stats *sgs,
struct sched_group *group)
@@ -11982,9 +11986,9 @@ static inline bool llc_balance(struct lb_env *env, struct sg_lb_stats *sgs,
if (env->sd->nr_balance_failed >= env->sd->cache_nice_tries + 1)
return false;
- if (sgs->nr_pref_dst_llc &&
- can_migrate_llc(cpumask_first(sched_group_span(group)),
- env->dst_cpu, 0, true) == mig_llc)
+ if (sgs->affinity_score &&
+ can_migrate_llcs(cpumask_first(sched_group_span(group)),
+ env->dst_cpu, NULL, true) == mig_llc)
return true;
return false;
@@ -11994,10 +11998,8 @@ static bool update_llc_busiest(struct lb_env *env,
struct sg_lb_stats *busiest,
struct sg_lb_stats *sgs)
{
- /*
- * There are more tasks that want to run on dst_cpu's LLC.
- */
- return sgs->nr_pref_dst_llc > busiest->nr_pref_dst_llc;
+ /* Prefer the group with the greater affinity gain toward dst_cpu. */
+ return sgs->affinity_score > busiest->affinity_score;
}
/*
@@ -12142,7 +12144,7 @@ static int calc_affinity_llc_score(struct sched_domain *sd, struct sched_domain
* this_rq() stays stable for a whole pass, and two CPUs balancing at the same
* time each get their own arrays.
*/
-static void __maybe_unused lb_affi_scratch(int **ids, int **weights, int *llc_max)
+static void lb_affi_scratch(int **ids, int **weights, int *llc_max)
{
struct sched_domain *sd = rcu_dereference_all(this_rq()->sd);
@@ -12194,7 +12196,7 @@ static void __maybe_unused lb_affi_scratch(int **ids, int **weights, int *llc_ma
* remain unchanged for the lifetime of the cache. The caller must
* initialize *@last_node to -1 and *@num to 0.
*/
-static int __maybe_unused
+static int
calc_affinity_score(struct sched_domain *sd, struct rq *rq, int src_cpu,
int dst_cpu, int *affi_nodes, int *affi, int *last_node,
int *num, int llc_max)
@@ -12248,6 +12250,12 @@ static inline void update_sg_lb_stats(struct lb_env *env,
{
int i, nr_running, local_group, sd_flags = env->sd->flags;
bool balancing_at_rd = !env->sd->parent;
+#ifdef CONFIG_SCHED_CACHE
+ int last_node = -1, node_num = 0, llc_max;
+ int *cache_data, *affi;
+
+ lb_affi_scratch(&cache_data, &affi, &llc_max);
+#endif
memset(sgs, 0, sizeof(*sgs));
@@ -12276,8 +12284,22 @@ static inline void update_sg_lb_stats(struct lb_env *env,
dst_llc = llc_id(env->dst_cpu);
if (llc_id(i) != dst_llc) {
sd_tmp = rcu_dereference_all(rq->sd);
- if (sd_tmp && (unsigned int)dst_llc < sd_tmp->llc_max)
- sgs->nr_pref_dst_llc += sd_tmp->llc_counts[dst_llc];
+ if (sd_tmp && (unsigned int)dst_llc < sd_tmp->llc_max) {
+ /*
+ * At tolerance 1, aggregation is limited to
+ * workloads that fit in one LLC. Only count
+ * tasks preferring dst_llc, rather than scoring
+ * intermediate moves along the affinity order.
+ * Migration checks still enforce LLC headroom.
+ */
+ if (env->tol > 1)
+ sgs->affinity_score +=
+ calc_affinity_score(env->sd, rq, i, env->dst_cpu,
+ cache_data, affi, &last_node,
+ &node_num, llc_max);
+ else
+ sgs->affinity_score += sd_tmp->llc_counts[dst_llc];
+ }
}
}
#endif
@@ -13373,12 +13395,19 @@ static struct rq *sched_balance_find_src_rq(struct lb_env *env,
{
struct rq *busiest = NULL, *rq;
unsigned long busiest_util = 0, busiest_load = 0, busiest_capacity = 1;
- unsigned int __maybe_unused busiest_pref_llc = 0;
+ unsigned int __maybe_unused busiest_affinity_score = 0;
struct sched_domain __maybe_unused *sd_tmp;
unsigned int busiest_nr = 0;
int __maybe_unused dst_llc;
int i;
+#ifdef CONFIG_SCHED_CACHE
+ int last_node = -1, node_num = 0, llc_max;
+ int *cache_data, *affi;
+
+ lb_affi_scratch(&cache_data, &affi, &llc_max);
+#endif
+
for_each_cpu_and(i, sched_group_span(group), env->cpus) {
unsigned long capacity, load, util;
unsigned int nr_running;
@@ -13510,11 +13539,19 @@ static struct rq *sched_balance_find_src_rq(struct lb_env *env,
dst_llc = llc_id(env->dst_cpu);
if (sd_tmp && (unsigned)dst_llc < sd_tmp->llc_max) {
- unsigned int this_pref_llc =
- sd_tmp->llc_counts[dst_llc];
-
- if (busiest_pref_llc < this_pref_llc) {
- busiest_pref_llc = this_pref_llc;
+ unsigned int affinity_score;
+
+ /* Use the same scoring policy as group selection. */
+ if (env->tol > 1)
+ affinity_score = calc_affinity_score(env->sd, rq,
+ i, env->dst_cpu, cache_data,
+ affi, &last_node,
+ &node_num, llc_max);
+ else
+ affinity_score = sd_tmp->llc_counts[dst_llc];
+
+ if (busiest_affinity_score < affinity_score) {
+ busiest_affinity_score = affinity_score;
busiest = rq;
}
}
@@ -13732,6 +13769,9 @@ static int sched_balance_rq(int this_cpu, struct rq *this_rq,
.cpus = cpus,
.fbq_type = all,
.tasks = LIST_HEAD_INIT(env.tasks),
+#ifdef CONFIG_SCHED_CACHE
+ .tol = READ_ONCE(llc_aggr_tolerance),
+#endif
};
bool need_unlock = false;
--
2.34.1
^ permalink raw reply related [flat|nested] 25+ messages in thread* Re: [RFC PATCH v3 10/17] sched/cache: Pick the source rq/group with the highest affinity gain
2026-10-29 2:20 ` [RFC PATCH v3 10/17] sched/cache: Pick the source rq/group with the highest affinity gain Jianyong Wu
@ 2026-10-30 3:05 ` sashiko-bot
0 siblings, 0 replies; 25+ messages in thread
From: sashiko-bot @ 2026-10-30 3:05 UTC (permalink / raw)
To: Jianyong Wu, Ingo Molnar, Peter Zijlstra, Juri Lelli,
Vincent Guittot, Chen Yu, Tim Chen
Cc: Dietmar Eggemann, Steven Rostedt, Ben Segall, Mel Gorman,
Valentin Schneider, K Prateek Nayak, Shrikanth Hegde, Phil Auld,
Andrew Morton, David Hildenbrand, maddy, Michael Ellerman, ljs,
linux-mm, jianyong.wu, zhongyuan, huangsj, wangfengyu, yingzhiwei
Thank you for your contribution! Sashiko AI review found 1 potential issue(s) to consider:
- [High] sched/fair: unchecked sd_rq->llc_max in calc_affinity_llc_score()
--
commit 706d6b3fdde74f4bc3582ab9ff3b3880647fbae9
Author: Jianyong Wu <wujianyong@hygon.cn>
sched/cache: Pick the source rq/group with the highest affinity gain
This commit updates cache-aware source group and runqueue selection to score
candidates using the affinity gain calculation when llc_aggr_tolerance is
greater than 1, while retaining the destination LLC task count metric when
the tolerance is 1.
> diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
> index eb08ae66f4650..e9a803433b161 100644
> --- a/kernel/sched/fair.c
> +++ b/kernel/sched/fair.c
[ ... ]
> @@ -12248,6 +12250,12 @@ static inline void update_sg_lb_stats(struct lb_env *env,
> {
> int i, nr_running, local_group, sd_flags = env->sd->flags;
> bool balancing_at_rd = !env->sd->parent;
> +#ifdef CONFIG_SCHED_CACHE
> + int last_node = -1, node_num = 0, llc_max;
> + int *cache_data, *affi;
> +
> + lb_affi_scratch(&cache_data, &affi, &llc_max);
> +#endif
>
> memset(sgs, 0, sizeof(*sgs));
>
> @@ -12276,8 +12284,22 @@ static inline void update_sg_lb_stats(struct lb_env *env,
> dst_llc = llc_id(env->dst_cpu);
> if (llc_id(i) != dst_llc) {
> sd_tmp = rcu_dereference_all(rq->sd);
> - if (sd_tmp && (unsigned int)dst_llc < sd_tmp->llc_max)
> - sgs->nr_pref_dst_llc += sd_tmp->llc_counts[dst_llc];
> + if (sd_tmp && (unsigned int)dst_llc < sd_tmp->llc_max) {
> + /*
> + * At tolerance 1, aggregation is limited to
> + * workloads that fit in one LLC. Only count
> + * tasks preferring dst_llc, rather than scoring
> + * intermediate moves along the affinity order.
> + * Migration checks still enforce LLC headroom.
> + */
> + if (env->tol > 1)
> + sgs->affinity_score +=
> + calc_affinity_score(env->sd, rq, i, env->dst_cpu,
> + cache_data, affi, &last_node,
> + &node_num, llc_max);
> + else
> + sgs->affinity_score += sd_tmp->llc_counts[dst_llc];
> + }
> }
> }
> #endif
[Severity: High]
Can this cause an out-of-bounds read or NULL pointer dereference on
sd_rq->llc_counts[] in calc_affinity_llc_score() (and similarly at the call
site in sched_balance_find_src_rq())?
In update_sg_lb_stats() and sched_balance_find_src_rq(), lb_affi_scratch()
sets llc_max from this_rq()->sd->llc_max:
kernel/sched/fair.c:lb_affi_scratch() {
struct sched_domain *sd = rcu_dereference_all(this_rq()->sd);
*ids = sd ? sd->affi_ids : NULL;
*weights = sd ? sd->affi_weights : NULL;
*llc_max = sd ? sd->llc_max : 0;
}
When env->tol > 1, the callers check dst_llc < sd_tmp->llc_max and pass
llc_max into calc_affinity_score(). That function then re-reads rq->sd into
sd_rq and, for non-NUMA domains, calls calc_affinity_llc_score():
kernel/sched/fair.c:calc_affinity_llc_score() {
...
if (src_llc != *last_llc) {
*last_llc = src_llc;
*num = get_affi_llcs(src_llc, dst_llc, affi_llc, llc_max);
}
for (int i = 0; i < *num; i++) {
if ((unsigned int)affi_llc[i] < llc_max)
score += sd_rq->llc_counts[affi_llc[i]];
}
...
}
Unlike calc_affinity_numa_score(), which checks if (llc >= sd->llc_max)
before indexing sd->llc_counts[llc], calc_affinity_llc_score() only checks
affi_llc[i] < llc_max (the scratch capacity from this_rq()->sd->llc_max)
without checking against sd_rq->llc_max.
Since sd_rq->llc_counts is allocated with sd_rq->llc_max elements in
alloc_sd_llc() (and annotated with __counted_by_ptr(llc_max)),
this_rq()->sd->llc_max can exceed sd_rq->llc_max:
1. During _nohz_idle_balance(), the ILB CPU (this_rq()) in a cpuset partition
rebuilt after hotplugging a new LLC (larger max_lid) can balance an idle
CPU in an unchanged cpuset partition whose CPUs retained their older
rq->sd (smaller sd_rq->llc_max), after rebuild_llc_node_map() has already
published the new LLC ID in llc_to_node_map.
2. During concurrent build_sched_domains(), cpu_attach_domain() attaches new
domains with a larger max_lid + 1 one CPU at a time while load balancing
can already run on an updated CPU.
3. Because calc_affinity_score() performs a second rcu_dereference_all(rq->sd)
without re-checking sd_rq->llc_max, a concurrent domain update where
alloc_sd_llc() failed or SD_SHARE_LLC is absent leaves sd_rq->llc_max == 0
and sd_rq->llc_counts == NULL.
Should calc_affinity_llc_score() check (unsigned int)affi_llc[i] <
sd_rq->llc_max (or pass sd_tmp directly instead of re-reading rq->sd and
bound against min(llc_max, sd_rq->llc_max)) before indexing
sd_rq->llc_counts[]?
--
Sashiko AI review · https://sashiko.dev/#/patchset/20261029022036.4002331-1-wujianyong@hygon.cn?part=10
^ permalink raw reply [flat|nested] 25+ messages in thread
* [RFC PATCH v3 11/17] sched/cache: Drop prefer_sibling restriction for llc_balance
2026-10-29 2:20 [RFC PATCH v3 00/17] sched: Scale cache-aware aggregation at LLC granularity Jianyong Wu
` (9 preceding siblings ...)
2026-10-29 2:20 ` [RFC PATCH v3 10/17] sched/cache: Pick the source rq/group with the highest affinity gain Jianyong Wu
@ 2026-10-29 2:20 ` Jianyong Wu
2026-10-29 2:20 ` [RFC PATCH v3 12/17] sched/cache: Apply multi-LLC aggregation policy to task migration Jianyong Wu
` (5 subsequent siblings)
16 siblings, 0 replies; 25+ messages in thread
From: Jianyong Wu @ 2026-10-29 2:20 UTC (permalink / raw)
To: Ingo Molnar, Peter Zijlstra, Juri Lelli, Vincent Guittot, Chen Yu,
Tim Chen
Cc: Dietmar Eggemann, Steven Rostedt, Ben Segall, Mel Gorman,
Valentin Schneider, K Prateek Nayak, Shrikanth Hegde, Phil Auld,
Andrew Morton, David Hildenbrand, maddy, Michael Ellerman, ljs,
linux-kernel, linux-mm, wujianyong, jianyong.wu, zhongyuan,
huangsj, wangfengyu, yingzhiwei
group_llc_balance performs balancing across LLC and NUMA domains.
sched_balance_find_src_group() forces balancing for it only when the
busiest group's child domain prefers siblings. However, sd_init() clears
SD_PREFER_SIBLING on NUMA domains. On systems with multiple NUMA levels,
prefer_sibling is therefore false at the upper NUMA levels, whose groups
are NUMA domains themselves, and cache-aware aggregation cannot force
tasks across those groups, e.g. between sockets.
Force balancing for group_llc_balance whenever the local group has spare
capacity, regardless of prefer_sibling. Keep the prefer_sibling
requirement for the sibling_imbalance() path.
Signed-off-by: Jianyong Wu <wujianyong@hygon.cn>
---
kernel/sched/fair.c | 6 +++---
1 file changed, 3 insertions(+), 3 deletions(-)
diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
index e9a803433b16..03bb5c85a8b7 100644
--- a/kernel/sched/fair.c
+++ b/kernel/sched/fair.c
@@ -13334,9 +13334,9 @@ static struct sched_group *sched_balance_find_src_group(struct lb_env *env)
* Try to move all excess tasks to a sibling domain of the busiest
* group's child domain.
*/
- if (sds.prefer_sibling && local->group_type == group_has_spare &&
- (busiest->group_type == group_llc_balance ||
- sibling_imbalance(env, &sds, busiest, local) > 1))
+ if (local->group_type == group_has_spare &&
+ ((busiest->group_type == group_llc_balance) || (sds.prefer_sibling &&
+ sibling_imbalance(env, &sds, busiest, local) > 1)))
goto force_balance;
if (busiest->group_type != group_overloaded) {
--
2.34.1
^ permalink raw reply related [flat|nested] 25+ messages in thread* [RFC PATCH v3 12/17] sched/cache: Apply multi-LLC aggregation policy to task migration
2026-10-29 2:20 [RFC PATCH v3 00/17] sched: Scale cache-aware aggregation at LLC granularity Jianyong Wu
` (10 preceding siblings ...)
2026-10-29 2:20 ` [RFC PATCH v3 11/17] sched/cache: Drop prefer_sibling restriction for llc_balance Jianyong Wu
@ 2026-10-29 2:20 ` Jianyong Wu
2026-10-30 3:05 ` sashiko-bot
2026-10-29 2:45 ` [RFC PATCH v3 13/17] sched/cache: Allow active balance to spread load from a full LLC Jianyong Wu
` (4 subsequent siblings)
16 siblings, 1 reply; 25+ messages in thread
From: Jianyong Wu @ 2026-10-29 2:20 UTC (permalink / raw)
To: Ingo Molnar, Peter Zijlstra, Juri Lelli, Vincent Guittot, Chen Yu,
Tim Chen
Cc: Dietmar Eggemann, Steven Rostedt, Ben Segall, Mel Gorman,
Valentin Schneider, K Prateek Nayak, Shrikanth Hegde, Phil Auld,
Andrew Morton, David Hildenbrand, maddy, Michael Ellerman, ljs,
linux-kernel, linux-mm, wujianyong, jianyong.wu, zhongyuan,
huangsj, wangfengyu, yingzhiwei
The existing task migration checks only apply the cache-aware policy
when either endpoint is the task's preferred LLC. Moves between other
LLCs are left unrestricted by that policy.
Apply the multi-LLC aggregation policy to these moves as well:
if_to_prefer() decides whether the move raises the task's affinity,
and can_migrate_llcs() decides whether to block it, based on that
direction and the load of the LLCs involved. Remove the obsolete
can_migrate_llc() helper.
Active balance has the same limitation. alb_break_llc() assumes
aggregation into a single LLC: only a task on its preferred LLC counts
as aggregated, so it restricts active balance only when every runnable
task on the source runqueue is on its preferred LLC. Once aggregation
spans multiple LLCs, a task outside its preferred LLC may still be
within the aggregation range, and pulling it to an LLC later in the
affinity sequence lowers its affinity.
When the source runqueue has exactly one task, check that task with
if_to_prefer() and can_migrate_llcs() wherever its preferred LLC is.
With more than one task, the task to be moved is not known here, so
leave the decision to can_migrate_task(). Move its active-balance fast
path after the cache-aware check so that active balance cannot bypass
a cache-aware veto when NUMA locality is neutral.
Signed-off-by: Jianyong Wu <wujianyong@hygon.cn>
---
kernel/sched/fair.c | 111 +++++++++++++-------------------------------
1 file changed, 32 insertions(+), 79 deletions(-)
diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
index 03bb5c85a8b7..c3f9ef8798d6 100644
--- a/kernel/sched/fair.c
+++ b/kernel/sched/fair.c
@@ -10580,54 +10580,6 @@ enum llc_mig {
mig_unrestricted /* G: Don't restrict generic load balance migration */
};
-/*
- * Check if task can be moved from the source LLC to the
- * destination LLC without breaking cache aware preferrence.
- * src_cpu and dst_cpu are arbitrary CPUs within the source
- * and destination LLCs, respectively.
- */
-static enum llc_mig can_migrate_llc(int src_cpu, int dst_cpu,
- unsigned long tsk_util,
- bool to_pref)
-{
- unsigned long src_util, dst_util, src_cap, dst_cap;
-
- if (!get_llc_stats(src_cpu, &src_util, &src_cap) ||
- !get_llc_stats(dst_cpu, &dst_util, &dst_cap))
- return mig_unrestricted;
-
- src_util = src_util < tsk_util ? 0 : src_util - tsk_util;
- dst_util = dst_util + tsk_util;
-
- if (!fits_llc_capacity(dst_util, dst_cap, false) &&
- !fits_llc_capacity(src_util, src_cap, false))
- return mig_unrestricted;
-
- if (to_pref) {
- /*
- * Don't migrate if we will get preferred LLC too
- * heavily loaded and if the dest is much busier
- * than the src, in which case migration will
- * increase the imbalance too much.
- */
- if (!fits_llc_capacity(dst_util, dst_cap, false) &&
- util_greater(dst_util, src_util))
- return mig_forbid;
- } else {
- /*
- * Don't migrate if we will leave preferred LLC
- * too idle, or if this migration leads to the
- * non-preferred LLC falls within sysctl_aggr_imb percent
- * of preferred LLC, leading to migration again
- * back to preferred LLC.
- */
- if (fits_llc_capacity(src_util, src_cap, false) ||
- !util_greater(src_util, dst_util))
- return mig_forbid;
- }
- return mig_llc;
-}
-
/* Accumulate a NUMA node's utilization and capacity at LLC granularity. */
static bool get_node_stats(int node, unsigned long *util_out,
unsigned long *cap_out, int *nr_llcs)
@@ -10768,7 +10720,7 @@ static enum llc_mig can_migrate_llcs(int src_cpu, int dst_cpu,
}
/* Decide whether the destination precedes the source in the affinity order. */
-static bool __maybe_unused if_to_prefer(int src_cpu, int dst_cpu, int pref_llc)
+static bool if_to_prefer(int src_cpu, int dst_cpu, int pref_llc)
{
int src_rank, dst_rank, src_node, dst_node, pref_node;
@@ -10827,55 +10779,52 @@ static enum llc_mig can_migrate_llc_task(int src_cpu, int dst_cpu,
return mig_unrestricted;
}
- if (cpus_share_cache(dst_cpu, cpu))
- to_pref = true;
- else if (cpus_share_cache(src_cpu, cpu))
- to_pref = false;
- else
- return mig_unrestricted;
+ to_pref = if_to_prefer(src_cpu, dst_cpu, llc_id(cpu));
- return can_migrate_llc(src_cpu, dst_cpu,
- task_util(p), to_pref);
+ return can_migrate_llcs(src_cpu, dst_cpu,
+ p, to_pref);
}
/*
* Check if active load balance breaks LLC locality in
* terms of cache aware load balance. The load level and
* imbalance do not warrant breaking LLC preference per
- * the can_migrate_llc() policy. Here, the benefit of
+ * the can_migrate_llcs() policy. Here, the benefit of
* LLC locality outweighs the power efficiency gained from
* migrating the only runnable task away.
*/
static inline bool
alb_break_llc(struct lb_env *env)
{
+ int pref_llc = -1;
+ bool to_pref = false;
+
if (!sched_cache_enabled())
return false;
if (cpus_share_cache(env->src_cpu, env->dst_cpu))
return false;
/*
- * All tasks prefer to stay on their current CPU.
- * Do not pull a task from its preferred CPU if:
- * 1. It is the only task running and does not exceed
- * imbalance allowance; OR
- * 2. Migrating it away from its preferred LLC would violate
- * the cache-aware scheduling policy.
+ * We need the preferred LLC to decide whether we can perform migration.
+ * Therefore, we need to obtain task_struct, which is only meaningful
+ * in the case that only one task on the rq.
+ * For cases with more than one task on the rq, we need to check
+ * this in can_migrate_task().
*/
- if (env->src_rq->nr_pref_llc_running &&
- env->src_rq->nr_pref_llc_running == env->src_rq->cfs.h_nr_runnable) {
- unsigned long util = 0;
+ if (env->src_rq->nr_running == 1) {
struct task_struct *cur;
- if (env->src_rq->nr_running <= 1)
- return true;
-
cur = rcu_dereference_all(env->src_rq->curr);
- if (cur && cur->sched_class == &fair_sched_class)
- util = task_util(cur);
+ if (!cur || !cur->mm)
+ return false;
+
+ if (cur->sched_class == &fair_sched_class)
+ pref_llc = llc_id(cur->mm->sc_stat.cpu);
- if (can_migrate_llc(env->src_cpu, env->dst_cpu,
- util, false) == mig_forbid)
+ to_pref = if_to_prefer(env->src_cpu, env->dst_cpu, pref_llc);
+
+ if (can_migrate_llcs(env->src_cpu, env->dst_cpu,
+ cur, to_pref) == mig_forbid)
return true;
}
@@ -11027,14 +10976,11 @@ int can_migrate_task(struct task_struct *p, struct lb_env *env)
/*
* Aggressive migration if:
- * 1) active balance
- * 2) destination numa is preferred
+ * 1) destination numa is preferred
+ * 2) active balance
* 3) task is cache cold, or
* 4) too many balance attempts have failed.
*/
- if (env->flags & LBF_ACTIVE_LB)
- return 1;
-
degrades = migrate_degrades_locality(p, env);
if (!degrades) {
/*
@@ -11060,6 +11006,13 @@ int can_migrate_task(struct task_struct *p, struct lb_env *env)
hot = degrades > 0;
}
+ /*
+ * Keep this after the cache-aware check so active balance respects its
+ * migration veto when NUMA locality is neutral.
+ */
+ if (env->flags & LBF_ACTIVE_LB)
+ return 1;
+
if (!hot || env->sd->nr_balance_failed > env->sd->cache_nice_tries) {
if (hot)
p->sched_task_hot = 1;
--
2.34.1
^ permalink raw reply related [flat|nested] 25+ messages in thread* Re: [RFC PATCH v3 12/17] sched/cache: Apply multi-LLC aggregation policy to task migration
2026-10-29 2:20 ` [RFC PATCH v3 12/17] sched/cache: Apply multi-LLC aggregation policy to task migration Jianyong Wu
@ 2026-10-30 3:05 ` sashiko-bot
0 siblings, 0 replies; 25+ messages in thread
From: sashiko-bot @ 2026-10-30 3:05 UTC (permalink / raw)
To: Jianyong Wu, Ingo Molnar, Peter Zijlstra, Juri Lelli,
Vincent Guittot, Chen Yu, Tim Chen
Cc: Dietmar Eggemann, Steven Rostedt, Ben Segall, Mel Gorman,
Valentin Schneider, K Prateek Nayak, Shrikanth Hegde, Phil Auld,
Andrew Morton, David Hildenbrand, maddy, Michael Ellerman, ljs,
linux-mm, jianyong.wu, zhongyuan, huangsj, wangfengyu, yingzhiwei
Thank you for your contribution! Sashiko AI review found 3 potential issue(s) to consider:
- [Critical] sched/fair: NULL deref and mm_struct UAF in alb_break_llc()
- [High] sched/fair: alb_break_llc() blocks active balance when pref_llc < 0
- [Medium] sched/fair: active balance bypasses migrate_degrades_llc() when degrades > 0
--
commit 7bd76e4bf626d210dfac7f3c5332cbe2a77e81f9
Author: Jianyong Wu <wujianyong@hygon.cn>
sched/cache: Apply multi-LLC aggregation policy to task migration
This commit updates cache-aware task migration and active load balancing to
use if_to_prefer() and can_migrate_llcs() across all LLC pairs, removes the
can_migrate_llc() helper, and moves the LBF_ACTIVE_LB check in
can_migrate_task() after the locality check.
> diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
> index 03bb5c85a8b7b..c3f9ef8798d6c 100644
> --- a/kernel/sched/fair.c
> +++ b/kernel/sched/fair.c
[ ... ]
> @@ -10827,55 +10779,52 @@ static enum llc_mig can_migrate_llc_task(int src_cpu, int dst_cpu,
[ ... ]
> static inline bool
> alb_break_llc(struct lb_env *env)
> {
> + int pref_llc = -1;
> + bool to_pref = false;
> +
> if (!sched_cache_enabled())
> return false;
>
> if (cpus_share_cache(env->src_cpu, env->dst_cpu))
> return false;
> /*
> - * All tasks prefer to stay on their current CPU.
> - * Do not pull a task from its preferred CPU if:
> - * 1. It is the only task running and does not exceed
> - * imbalance allowance; OR
> - * 2. Migrating it away from its preferred LLC would violate
> - * the cache-aware scheduling policy.
> + * We need the preferred LLC to decide whether we can perform migration.
> + * Therefore, we need to obtain task_struct, which is only meaningful
> + * in the case that only one task on the rq.
> + * For cases with more than one task on the rq, we need to check
> + * this in can_migrate_task().
> */
> - if (env->src_rq->nr_pref_llc_running &&
> - env->src_rq->nr_pref_llc_running == env->src_rq->cfs.h_nr_runnable) {
> - unsigned long util = 0;
> + if (env->src_rq->nr_running == 1) {
> struct task_struct *cur;
>
> - if (env->src_rq->nr_running <= 1)
> - return true;
> -
> cur = rcu_dereference_all(env->src_rq->curr);
> - if (cur && cur->sched_class == &fair_sched_class)
> - util = task_util(cur);
> + if (!cur || !cur->mm)
> + return false;
> +
> + if (cur->sched_class == &fair_sched_class)
> + pref_llc = llc_id(cur->mm->sc_stat.cpu);
[Severity: Critical]
Can this dereference of cur->mm cause a NULL pointer dereference or a
use-after-free on struct mm_struct?
In sched_balance_rq(), need_active_balance() -> alb_break_llc() is called
before locking busiest (env->src_rq) and again after unlocking it, holding
only rcu_read_lock():
kernel/sched/fair.c:sched_balance_rq() {
...
if (need_active_balance(&env)) {
unsigned long flags;
raw_spin_rq_lock_irqsave(busiest, flags);
...
}
Because cur is actively running on env->src_cpu and neither the runqueue lock
nor task_lock(cur) is held, cur can concurrently execute exit_mm() or
kthread_unuse_mm() and clear current->mm = NULL between the cur->mm check and
the reload in cur->mm->sc_stat.cpu:
kernel/exit.c:exit_mm() {
...
local_irq_disable();
current->mm = NULL;
membarrier_update_current_mm(NULL);
enter_lazy_tlb(mm, current);
local_irq_enable();
task_unlock(current);
mmap_read_unlock(mm);
mm_update_next_owner(mm);
mmput(mm);
}
Even if the mm pointer is loaded only once, rcu_read_lock() only protects
struct task_struct, whereas mm_cachep does not use SLAB_TYPESAFE_BY_RCU and
__mmdrop() frees struct mm_struct immediately via free_mm(). If cur replaces
its mm in exec_mmap() or exits and switches out on the unlocked remote
runqueue, can alb_break_llc() and can_migrate_llcs() end up reading from a
freed struct mm_struct?
>
> - if (can_migrate_llc(env->src_cpu, env->dst_cpu,
> - util, false) == mig_forbid)
> + to_pref = if_to_prefer(env->src_cpu, env->dst_cpu, pref_llc);
> +
> + if (can_migrate_llcs(env->src_cpu, env->dst_cpu,
> + cur, to_pref) == mig_forbid)
> return true;
> }
[Severity: High]
When pref_llc is negative (for instance, when cur->mm->sc_stat.cpu is -1 on
single-threaded tasks, or when cur is not in fair_sched_class), shouldn't
alb_break_llc() return false instead of calling can_migrate_llcs()?
When pref_llc < 0, if_to_prefer() returns false, and can_migrate_llcs() falls
back to using src_cpu as target_cpu:
kernel/sched/fair.c:can_migrate_llcs() {
...
if (p) {
struct mm_struct *mm = p->mm;
if (mm)
target_cpu = READ_ONCE(mm->sc_stat.cpu);
target_cpu = target_cpu >= 0 ? target_cpu : src_cpu;
tsk_util = task_util(p);
}
...
}
With to_pref == false and target_cpu == src_cpu, can_migrate_llcs() treats
src_cpu as the task's preferred cache location and returns mig_forbid whenever
fits_llc_capacity() is true on the source LLC or node:
kernel/sched/fair.c:can_migrate_llcs() {
...
if (src_node == dst_node) {
/* Leave the source LLC at or above the threshold. */
if (fits_llc_capacity(src_util, src_cap, false))
return mig_forbid;
...
}
Unlike can_migrate_llc_task(), which returns mig_unrestricted when cpu < 0,
won't this regression cause alb_break_llc() to block cross-LLC active balance
for tasks that have no preferred LLC?
[ ... ]
> @@ -11027,14 +10976,11 @@ int can_migrate_task(struct task_struct *p, struct lb_env *env)
>
> /*
> * Aggressive migration if:
> - * 1) active balance
> - * 2) destination numa is preferred
> + * 1) destination numa is preferred
> + * 2) active balance
> * 3) task is cache cold, or
> * 4) too many balance attempts have failed.
> */
> - if (env->flags & LBF_ACTIVE_LB)
> - return 1;
> -
> degrades = migrate_degrades_locality(p, env);
> if (!degrades) {
> /*
> @@ -11060,6 +11006,13 @@ int can_migrate_task(struct task_struct *p, struct lb_env *env)
> hot = degrades > 0;
> }
>
> + /*
> + * Keep this after the cache-aware check so active balance respects its
> + * migration veto when NUMA locality is neutral.
> + */
> + if (env->flags & LBF_ACTIVE_LB)
> + return 1;
[Severity: Medium]
What happens during cross-node active load balancing when
migrate_degrades_locality() returns a positive value (degrades > 0)?
In active_load_balance_cpu_stop(), the stopper task is queued on env->src_rq,
so env->src_rq->nr_running > env->src_rq->nr_preferred_running is true in
migrate_degrades_locality():
kernel/sched/fair.c:migrate_degrades_locality() {
...
/* Migrating away from the preferred node is always bad. */
if (src_nid == p->numa_preferred_nid) {
if (env->src_rq->nr_running > env->src_rq->nr_preferred_running)
return 1;
else
return 0;
}
...
}
When a task is on its preferred NUMA node, migrate_degrades_locality() returns
1, which skips the if (!degrades) block containing migrate_degrades_llc() and
sets hot = 1. Because the LBF_ACTIVE_LB check right after that block returns 1
unconditionally, won't active balance bypass migrate_degrades_llc() whenever
migrating the task also degrades NUMA locality?
--
Sashiko AI review · https://sashiko.dev/#/patchset/20261029022036.4002331-1-wujianyong@hygon.cn?part=12
^ permalink raw reply [flat|nested] 25+ messages in thread
* [RFC PATCH v3 13/17] sched/cache: Allow active balance to spread load from a full LLC
2026-10-29 2:20 [RFC PATCH v3 00/17] sched: Scale cache-aware aggregation at LLC granularity Jianyong Wu
` (11 preceding siblings ...)
2026-10-29 2:20 ` [RFC PATCH v3 12/17] sched/cache: Apply multi-LLC aggregation policy to task migration Jianyong Wu
@ 2026-10-29 2:45 ` Jianyong Wu
2026-10-30 3:05 ` sashiko-bot
2026-10-29 2:50 ` [RFC PATCH v3 14/17] sched/cache: Consider LLC load when selecting a single-task source rq Jianyong Wu
` (3 subsequent siblings)
16 siblings, 1 reply; 25+ messages in thread
From: Jianyong Wu @ 2026-10-29 2:45 UTC (permalink / raw)
To: Ingo Molnar, Peter Zijlstra, Juri Lelli, Vincent Guittot, Chen Yu,
Tim Chen
Cc: Dietmar Eggemann, Steven Rostedt, Ben Segall, Mel Gorman,
Valentin Schneider, K Prateek Nayak, Shrikanth Hegde, Phil Auld,
Andrew Morton, David Hildenbrand, maddy, Michael Ellerman, ljs,
linux-kernel, linux-mm, wujianyong, jianyong.wu, zhongyuan,
huangsj, wangfengyu, yingzhiwei
Cache-aware aggregation can trigger active balance for migrate_llc_task
without waiting for nr_balance_failed. Spreading load from an LLC via
migrate_task normally requires nr_balance_failed to exceed
cache_nice_tries + 2. This delay can leave an LLC above the aggregation
threshold while another LLC has room.
Allow migrate_task to trigger active balance without that wait when the
source LLC exceeds the aggregation threshold and the destination can
accommodate one full CPU of additional load. Require the source to lead
the destination by at least two CPUs worth of load, so moving up to one
CPU of load does not reverse their utilization ordering and immediately
invite a migration back. The existing task migration checks still decide
whether the selected task may move.
Signed-off-by: Jianyong Wu <wujianyong@hygon.cn>
---
kernel/sched/fair.c | 54 +++++++++++++++++++++++++++++++++++++++++++++
1 file changed, 54 insertions(+)
diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
index c3f9ef8798d6..1e286296cd65 100644
--- a/kernel/sched/fair.c
+++ b/kernel/sched/fair.c
@@ -13558,6 +13558,57 @@ imbalanced_active_balance(struct lb_env *env)
return 0;
}
+#ifdef CONFIG_SCHED_CACHE
+/*
+ * Cache-aware aggregation can trigger active balance via migrate_llc_task
+ * without waiting for nr_balance_failed. Spreading load via migrate_task
+ * normally waits for nr_balance_failed to exceed cache_nice_tries + 2.
+ * This can leave one LLC above the aggregation threshold while another
+ * LLC has room.
+ *
+ * Allow that spread when the source is above the aggregation threshold,
+ * the destination has room for one CPU's load, and the source leads by
+ * at least two CPUs' load. The gap prevents one migration from reversing
+ * their utilization ordering and immediately inviting a migration back.
+ * The task migration checks still decide whether the task may move.
+ */
+static inline bool llc_spread_active_balance(struct lb_env *env)
+{
+ unsigned long src_util, src_cap, dst_util, dst_cap;
+
+ if (!sched_cache_enabled())
+ return false;
+
+ if (env->migration_type != migrate_task)
+ return false;
+
+ if (cpus_share_cache(env->src_cpu, env->dst_cpu))
+ return false;
+
+ if (!get_llc_stats(env->src_cpu, &src_util, &src_cap) ||
+ !get_llc_stats(env->dst_cpu, &dst_util, &dst_cap))
+ return false;
+
+ if (fits_llc_capacity(src_util, src_cap, true))
+ return false;
+
+ /*
+ * Reserve room for one CPU's load at the destination. A two-CPU gap
+ * keeps one migration from reversing the utilization ordering and
+ * causing the task to ping-pong between LLCs.
+ */
+ if (!fits_llc_capacity(dst_util + SCHED_CAPACITY_SCALE, dst_cap, true))
+ return false;
+
+ return util_greater(src_util, dst_util);
+}
+#else
+static inline bool llc_spread_active_balance(struct lb_env *env)
+{
+ return false;
+}
+#endif
+
static int need_active_balance(struct lb_env *env)
{
struct sched_domain *sd = env->sd;
@@ -13571,6 +13622,9 @@ static int need_active_balance(struct lb_env *env)
if (imbalanced_active_balance(env))
return 1;
+ if (llc_spread_active_balance(env))
+ return 1;
+
/*
* The dst_cpu is idle and the src_cpu CPU has only 1 CFS task.
* It's worth migrating the task if the src_cpu's capacity is reduced
--
2.34.1
^ permalink raw reply related [flat|nested] 25+ messages in thread* Re: [RFC PATCH v3 13/17] sched/cache: Allow active balance to spread load from a full LLC
2026-10-29 2:45 ` [RFC PATCH v3 13/17] sched/cache: Allow active balance to spread load from a full LLC Jianyong Wu
@ 2026-10-30 3:05 ` sashiko-bot
0 siblings, 0 replies; 25+ messages in thread
From: sashiko-bot @ 2026-10-30 3:05 UTC (permalink / raw)
To: Jianyong Wu, Ingo Molnar, Peter Zijlstra, Juri Lelli,
Vincent Guittot, Chen Yu, Tim Chen
Cc: Dietmar Eggemann, Steven Rostedt, Ben Segall, Mel Gorman,
Valentin Schneider, K Prateek Nayak, Shrikanth Hegde, Phil Auld,
Andrew Morton, David Hildenbrand, maddy, Michael Ellerman, ljs,
linux-mm, jianyong.wu, zhongyuan, huangsj, wangfengyu, yingzhiwei
Thank you for your contribution! Sashiko AI review found 2 potential issue(s) to consider:
- [Medium] sched/fair: missing 2-CPU utilization gap check in llc_spread_active_balance()
- [Medium] sched/cache: futile active load balance in llc_spread_active_balance()
--
commit 0b23fd14c184de7459085104b19552a73905471e
Author: Jianyong Wu <wujianyong@hygon.cn>
sched/cache: Allow active balance to spread load from a full LLC
This commit introduces llc_spread_active_balance() so migrate_task can trigger
active load balancing across LLCs without waiting for nr_balance_failed to
exceed cache_nice_tries + 2 when the source LLC exceeds the aggregation
threshold and the destination LLC has spare capacity.
> diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
> index c3f9ef8798d6c..1e286296cd65c 100644
> --- a/kernel/sched/fair.c
> +++ b/kernel/sched/fair.c
> @@ -13558,6 +13558,57 @@ imbalanced_active_balance(struct lb_env *env)
> return 0;
> }
>
> +#ifdef CONFIG_SCHED_CACHE
> +/*
> + * Cache-aware aggregation can trigger active balance via migrate_llc_task
> + * without waiting for nr_balance_failed. Spreading load via migrate_task
> + * normally waits for nr_balance_failed to exceed cache_nice_tries + 2.
> + * This can leave one LLC above the aggregation threshold while another
> + * LLC has room.
> + *
> + * Allow that spread when the source is above the aggregation threshold,
> + * the destination has room for one CPU's load, and the source leads by
> + * at least two CPUs' load. The gap prevents one migration from reversing
> + * their utilization ordering and immediately inviting a migration back.
> + * The task migration checks still decide whether the task may move.
> + */
> +static inline bool llc_spread_active_balance(struct lb_env *env)
> +{
> + unsigned long src_util, src_cap, dst_util, dst_cap;
> +
> + if (!sched_cache_enabled())
> + return false;
> +
> + if (env->migration_type != migrate_task)
> + return false;
[Severity: Medium]
Can llc_spread_active_balance() trigger repeated futile active load balance
attempts when env->src_rq->nr_running > 1 and detach_tasks() was vetoed by
cache locality checks?
In sched_balance_rq(), when detach_tasks() fails to pull a task because
can_migrate_task() -> migrate_degrades_llc() -> can_migrate_llcs() returns
mig_forbid, can_migrate_task() sets LBF_LLC_PINNED in env.flags.
When ld_moved == 0, sched_balance_rq() skips incrementing
sd->nr_balance_failed if LBF_LLC_PINNED is set, and then calls
need_active_balance():
kernel/sched/fair.c:sched_balance_rq() {
...
if (idle != CPU_NEWLY_IDLE &&
env.migration_type != migrate_misfit &&
!(env.flags & LBF_LLC_PINNED))
sd->nr_balance_failed++;
if (need_active_balance(&env)) {
...
}
In need_active_balance(), alb_break_llc() only checks can_migrate_llcs() when
env->src_rq->nr_running == 1:
kernel/sched/fair.c:alb_break_llc() {
...
if (env->src_rq->nr_running == 1) {
...
if (can_migrate_llcs(env->src_cpu, env->dst_cpu,
cur, to_pref) == mig_forbid)
return true;
}
return false;
}
When env->src_rq->nr_running > 1, alb_break_llc() returns false, and
llc_spread_active_balance() does not check env->flags & LBF_LLC_PINNED,
env->src_rq->nr_running == 1, or the post-departure and NUMA node constraints
in can_migrate_llcs().
If llc_spread_active_balance() returns true here, sched_balance_rq() queues
active_load_balance_cpu_stop() via stop_one_cpu_nowait() and resets
sd->balance_interval to sd->min_interval. When the CPU stopper runs
detach_one_task() -> can_migrate_task(), sd->nr_balance_failed is still 0, so
migrate_degrades_llc() rejects the migration for the same reason.
Should llc_spread_active_balance() bail out when env->flags & LBF_LLC_PINNED
is set (or check the post-departure state) to avoid kicking the CPU stopper
for a move that can_migrate_task() will reject?
> +
> + if (cpus_share_cache(env->src_cpu, env->dst_cpu))
> + return false;
> +
> + if (!get_llc_stats(env->src_cpu, &src_util, &src_cap) ||
> + !get_llc_stats(env->dst_cpu, &dst_util, &dst_cap))
> + return false;
> +
> + if (fits_llc_capacity(src_util, src_cap, true))
> + return false;
> +
> + /*
> + * Reserve room for one CPU's load at the destination. A two-CPU gap
> + * keeps one migration from reversing the utilization ordering and
> + * causing the task to ping-pong between LLCs.
> + */
> + if (!fits_llc_capacity(dst_util + SCHED_CAPACITY_SCALE, dst_cap, true))
> + return false;
> +
> + return util_greater(src_util, dst_util);
> +}
[Severity: Medium]
Does llc_spread_active_balance() actually enforce the two-CPU utilization gap
described in the comment and commit message?
Moving a task with one full CPU of utilization (SCHED_CAPACITY_SCALE) reduces
src_util by SCHED_CAPACITY_SCALE and increases dst_util by
SCHED_CAPACITY_SCALE, narrowing the gap between src_util and dst_util by
2 * SCHED_CAPACITY_SCALE.
However, the checks here only verify:
1. !fits_llc_capacity(src_util, src_cap, true), meaning src_util > threshold
2. fits_llc_capacity(dst_util + SCHED_CAPACITY_SCALE, dst_cap, true), meaning
dst_util <= threshold - SCHED_CAPACITY_SCALE
3. util_greater(src_util, dst_util), meaning
src_util * 100 > dst_util * (100 + llc_imb_pct)
For equal-capacity LLCs, the two fits_llc_capacity() checks only ensure
src_util - dst_util > SCHED_CAPACITY_SCALE (one CPU of load), and
util_greater() only requires a 20% relative difference (which is smaller than
2 * SCHED_CAPACITY_SCALE whenever dst_util < 10 * SCHED_CAPACITY_SCALE).
For example, on a 4-CPU LLC (cap = 4096, 50% threshold = 2048) with
src_util = 2050 and dst_util = 1024, all three checks pass even though
src_util - dst_util is only 1026 (~1 CPU). Migrating a 1-CPU task (1024)
drops src_util to 1026 (below the aggregation threshold) and raises dst_util
to 2048, reversing the utilization ordering between the two LLCs.
Furthermore, in can_migrate_llcs(), src_util has tsk_util subtracted before
checking the threshold and post-migration ordering:
kernel/sched/fair.c:can_migrate_llcs() {
...
if (src_node == dst_node) {
/* Leave the source LLC at or above the threshold. */
if (fits_llc_capacity(src_util, src_cap, false))
return mig_forbid;
if (util_greater(src_pre, dst_pre) &&
src_util >= dst_util)
return mig_llc;
...
}
Should llc_spread_active_balance() check that src_util remains at or above the
threshold after subtracting SCHED_CAPACITY_SCALE (for example, checking
fits_llc_capacity(src_util - SCHED_CAPACITY_SCALE, src_cap, false) or
explicitly checking src_util >= dst_util + 2 * SCHED_CAPACITY_SCALE) so that
the two-CPU gap is enforced?
--
Sashiko AI review · https://sashiko.dev/#/patchset/20261029022036.4002331-1-wujianyong@hygon.cn?part=13
^ permalink raw reply [flat|nested] 25+ messages in thread
* [RFC PATCH v3 14/17] sched/cache: Consider LLC load when selecting a single-task source rq
2026-10-29 2:20 [RFC PATCH v3 00/17] sched: Scale cache-aware aggregation at LLC granularity Jianyong Wu
` (12 preceding siblings ...)
2026-10-29 2:45 ` [RFC PATCH v3 13/17] sched/cache: Allow active balance to spread load from a full LLC Jianyong Wu
@ 2026-10-29 2:50 ` Jianyong Wu
2026-10-29 2:56 ` [RFC PATCH v3 15/17] sched/cache: Include recently used preferred nodes in LLC scans Jianyong Wu
` (2 subsequent siblings)
16 siblings, 0 replies; 25+ messages in thread
From: Jianyong Wu @ 2026-10-29 2:50 UTC (permalink / raw)
To: Ingo Molnar, Peter Zijlstra, Juri Lelli, Vincent Guittot, Chen Yu,
Tim Chen
Cc: Dietmar Eggemann, Steven Rostedt, Ben Segall, Mel Gorman,
Valentin Schneider, K Prateek Nayak, Shrikanth Hegde, Phil Auld,
Andrew Morton, David Hildenbrand, maddy, Michael Ellerman, ljs,
linux-kernel, linux-mm, wujianyong, jianyong.wu, zhongyuan,
huangsj, wangfengyu, yingzhiwei
When a source sched group spans multiple LLCs and every eligible rq has
at most one runnable task, migrate_task selects the first eligible rq.
It cannot distinguish an LLC above the aggregation threshold from one
at the threshold. If the selected rq is in an LLC at the threshold, the
cache-aware migration checks can veto the pull, while the LLC above the
threshold is never selected. The excess then persists.
For example, consider a two-socket machine with this topology:
Socket 0: NUMA nodes 0-3
Socket 1: NUMA nodes 4-7
Each node: four LLCs
Each LLC: four cores with SMT2, exposing eight logical CPUs
With a 50% aggregation threshold, each LLC can hold four full-utilization
tasks at the threshold. Suppose a workload has its preferred LLC in
node 6, with the node affinity order starting with 6, 7, 4, 5, followed
by the nodes in socket 0. One LLC in node 7 holds five CPU-bound tasks,
while every other LLC in socket 1 holds four. Each task runs on its own
rq, and socket 0 has spare capacity.
When socket 0 balances against socket 1, rq-level task counts select
the first CPU in node 4. Moving its task would leave node 4 below the
threshold, so the migration checks forbid it and active balance is not
started. Every such pass fails the same way: the five-task LLC stays
above the threshold while socket 0 has room. Balancing within node 7
does not help either, since moving a task to a sibling LLC with four
tasks merely reverses their task counts.
With cache-aware scheduling enabled, at domains above the LLC, track a
candidate rq in the LLC with the highest utilization within the source
group. Use it when the maximum runnable task count is one. In the
example, socket 0 then pulls from the five-task LLC. Node 7 remains
filled, so the move is permitted and brings that LLC back to the
threshold.
Keep task-count priority when an eligible rq has more than one runnable
task. Use the per-CPU scratch mask added earlier to sample each LLC
once during the existing scan.
Signed-off-by: Jianyong Wu <wujianyong@hygon.cn>
---
kernel/sched/fair.c | 43 +++++++++++++++++++++++++++++++++++++++++++
1 file changed, 43 insertions(+)
diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
index 1e286296cd65..20a6a7f5c2f7 100644
--- a/kernel/sched/fair.c
+++ b/kernel/sched/fair.c
@@ -13357,8 +13357,18 @@ static struct rq *sched_balance_find_src_rq(struct lb_env *env,
#ifdef CONFIG_SCHED_CACHE
int last_node = -1, node_num = 0, llc_max;
int *cache_data, *affi;
+ unsigned long llc_util, llc_cap;
+ struct sched_domain *llc_sd, *sd_self;
+ struct rq *llc_busiest = NULL;
+ unsigned long llc_busiest_util = 0;
+ struct cpumask *llcs_cpumask = NULL;
lb_affi_scratch(&cache_data, &affi, &llc_max);
+ sd_self = rcu_dereference_all(this_rq()->sd);
+ if (sd_self)
+ llcs_cpumask = sd_self->llc_stats_mask;
+ if (llcs_cpumask)
+ cpumask_clear(llcs_cpumask);
#endif
for_each_cpu_and(i, sched_group_span(group), env->cpus) {
@@ -13472,6 +13482,34 @@ static struct rq *sched_balance_find_src_rq(struct lb_env *env,
busiest_nr = nr_running;
busiest = rq;
}
+#ifdef CONFIG_SCHED_CACHE
+ /*
+ * When every eligible rq has at most one runnable task,
+ * task-count comparisons select the first non-empty rq,
+ * favoring lower-numbered CPUs regardless of LLC load.
+ * This can leave LLC load uneven even when individual
+ * runqueues have the same number of runnable tasks.
+ *
+ * Track an rq in the LLC with the highest utilization
+ * during the same scan. Use it only if no eligible rq
+ * has more than one runnable task, preserving task-count
+ * priority while helping resolve LLC imbalance.
+ */
+ if (busiest_nr < 2 &&
+ !(env->sd->flags & SD_SHARE_LLC) &&
+ nr_running == 1 && sched_cache_enabled() &&
+ llcs_cpumask && !cpumask_test_cpu(i, llcs_cpumask) &&
+ get_llc_stats(i, &llc_util, &llc_cap)) {
+ if (!llc_busiest || llc_util > llc_busiest_util) {
+ llc_busiest_util = llc_util;
+ llc_busiest = rq;
+ }
+ llc_sd = rcu_dereference_all(per_cpu(sd_llc, i));
+ if (llc_sd)
+ cpumask_or(llcs_cpumask, llcs_cpumask,
+ sched_domain_span(llc_sd));
+ }
+#endif
break;
case migrate_misfit:
@@ -13514,6 +13552,11 @@ static struct rq *sched_balance_find_src_rq(struct lb_env *env,
}
}
+#ifdef CONFIG_SCHED_CACHE
+ if (busiest_nr == 1 && llc_busiest)
+ return llc_busiest;
+#endif
+
return busiest;
}
--
2.34.1
^ permalink raw reply related [flat|nested] 25+ messages in thread* [RFC PATCH v3 15/17] sched/cache: Include recently used preferred nodes in LLC scans
2026-10-29 2:20 [RFC PATCH v3 00/17] sched: Scale cache-aware aggregation at LLC granularity Jianyong Wu
` (13 preceding siblings ...)
2026-10-29 2:50 ` [RFC PATCH v3 14/17] sched/cache: Consider LLC load when selecting a single-task source rq Jianyong Wu
@ 2026-10-29 2:56 ` Jianyong Wu
2026-10-30 3:05 ` sashiko-bot
2026-10-29 2:58 ` [RFC PATCH v3 16/17] sched/cache: Drop stale preferred LLC checks Jianyong Wu
2026-10-29 2:59 ` [RFC PATCH v3 17/17] sched/debug: Show cache placement and preferred LLC in /proc/<pid>/sched Jianyong Wu
16 siblings, 1 reply; 25+ messages in thread
From: Jianyong Wu @ 2026-10-29 2:56 UTC (permalink / raw)
To: Ingo Molnar, Peter Zijlstra, Juri Lelli, Vincent Guittot, Chen Yu,
Tim Chen
Cc: Dietmar Eggemann, Steven Rostedt, Ben Segall, Mel Gorman,
Valentin Schneider, K Prateek Nayak, Shrikanth Hegde, Phil Auld,
Andrew Morton, David Hildenbrand, maddy, Michael Ellerman, ljs,
linux-kernel, linux-mm, wujianyong, jianyong.wu, zhongyuan,
huangsj, wangfengyu, yingzhiwei
get_scan_cpumasks() includes the current task's preferred NUMA node,
but other tasks sharing the mm may prefer different nodes. This makes
the LLC scan scope depend on which task performs the scan.
Record preferred nodes observed while accounting tasks that share the
mm, and include recently observed nodes in the scan mask. Expire stale
records using the LLC affinity timeout and clear them when the mm's
preferred cache state is invalidated.
Signed-off-by: Jianyong Wu <wujianyong@hygon.cn>
---
include/linux/mm_types.h | 6 +-----
include/linux/sched.h | 1 +
kernel/sched/fair.c | 44 ++++++++++++++++++++++++++++++++++++++++
3 files changed, 46 insertions(+), 5 deletions(-)
diff --git a/include/linux/mm_types.h b/include/linux/mm_types.h
index b18c2b2e7d2c..7fef34c6f33a 100644
--- a/include/linux/mm_types.h
+++ b/include/linux/mm_types.h
@@ -1626,11 +1626,7 @@ static inline int mm_alloc_sched_noprof(struct mm_struct *mm)
#define mm_alloc_sched(...) alloc_hooks(mm_alloc_sched_noprof(__VA_ARGS__))
-static inline void mm_destroy_sched(struct mm_struct *mm)
-{
- free_percpu(mm->sc_stat.pcpu_sched);
- mm->sc_stat.pcpu_sched = NULL;
-}
+void mm_destroy_sched(struct mm_struct *mm);
#else /* !CONFIG_SCHED_CACHE */
static inline int mm_alloc_sched(struct mm_struct *mm) { return 0; }
diff --git a/include/linux/sched.h b/include/linux/sched.h
index 1e4136c2b2a3..7fd4ea8c9037 100644
--- a/include/linux/sched.h
+++ b/include/linux/sched.h
@@ -2393,6 +2393,7 @@ struct sched_cache_time {
struct sched_cache_stat {
struct sched_cache_time __percpu *pcpu_sched;
+ unsigned long *node_epoch;
raw_spinlock_t lock;
unsigned long epoch;
u64 nr_running_avg;
diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
index 20a6a7f5c2f7..b93b6e6c9dea 100644
--- a/kernel/sched/fair.c
+++ b/kernel/sched/fair.c
@@ -1594,6 +1594,9 @@ void mm_init_sched(struct mm_struct *mm,
mm->sc_stat.next_scan = jiffies;
mm->sc_stat.nr_running_avg = 0;
mm->sc_stat.footprint = 0;
+ mm->sc_stat.node_epoch = kcalloc(num_possible_nodes(),
+ sizeof(*mm->sc_stat.node_epoch),
+ GFP_KERNEL);
/*
* The update to mm->sc_stat should not be reordered
* before initialization to mm's other fields, in case
@@ -1602,6 +1605,14 @@ void mm_init_sched(struct mm_struct *mm,
smp_store_release(&mm->sc_stat.pcpu_sched, _pcpu_sched);
}
+void mm_destroy_sched(struct mm_struct *mm)
+{
+ free_percpu(mm->sc_stat.pcpu_sched);
+ mm->sc_stat.pcpu_sched = NULL;
+ kfree(mm->sc_stat.node_epoch);
+ mm->sc_stat.node_epoch = NULL;
+}
+
/* because why would C be fully specified */
static __always_inline void __shr_u64(u64 *val, unsigned int n)
{
@@ -1689,7 +1700,9 @@ void account_mm_sched(struct rq *rq, struct task_struct *p, s64 delta_exec)
{
struct sched_cache_time *pcpu_sched;
struct mm_struct *mm = p->mm;
+ unsigned long *node_epoch;
int mm_sched_llc = -1;
+ int node, pref_nid = NUMA_NO_NODE;
unsigned long epoch;
if (!sched_cache_enabled())
@@ -1713,6 +1726,13 @@ void account_mm_sched(struct rq *rq, struct task_struct *p, s64 delta_exec)
epoch = rq->cpu_epoch;
}
+ node_epoch = mm->sc_stat.node_epoch;
+#ifdef CONFIG_NUMA_BALANCING
+ pref_nid = READ_ONCE(p->numa_preferred_nid);
+#endif
+ if (pref_nid != NUMA_NO_NODE && mm->sc_stat.node_epoch)
+ mm->sc_stat.node_epoch[pref_nid] = epoch;
+
/*
* If this process hasn't hit task_cache_work() for a while invalidate
* its preferred state.
@@ -1722,6 +1742,16 @@ void account_mm_sched(struct rq *rq, struct task_struct *p, s64 delta_exec)
exceed_llc_capacity(mm, cpu_of(rq))) {
if (READ_ONCE(mm->sc_stat.cpu) != -1)
WRITE_ONCE(mm->sc_stat.cpu, -1);
+
+ if (node_epoch)
+ memset(mm->sc_stat.node_epoch, 0,
+ sizeof(*node_epoch) * num_possible_nodes());
+ } else if (node_epoch) {
+ for_each_node(node) {
+ if ((long)(epoch - READ_ONCE(node_epoch[node])) >
+ llc_epoch_affinity_timeout)
+ WRITE_ONCE(node_epoch[node], 0);
+ }
}
mm_sched_llc = get_pref_llc(p, mm);
@@ -1765,10 +1795,12 @@ static void get_scan_cpumasks(cpumask_var_t cpus, struct task_struct *p)
{
#ifdef CONFIG_NUMA_BALANCING
int cpu, curr_cpu, nid, pref_nid;
+ unsigned long *node_epoch;
if (!static_branch_likely(&sched_numa_balancing))
goto out;
+ node_epoch = p->mm->sc_stat.node_epoch;
cpu = READ_ONCE(p->mm->sc_stat.cpu);
if (cpu != -1)
nid = cpu_to_node(cpu);
@@ -1789,6 +1821,18 @@ static void get_scan_cpumasks(cpumask_var_t cpus, struct task_struct *p)
if (pref_nid == NUMA_NO_NODE)
goto out;
+ if (node_epoch) {
+ int node;
+
+ for_each_node(node) {
+ if (node == pref_nid)
+ continue;
+
+ if (node_epoch[node] > 0)
+ cpumask_or(cpus, cpus, cpumask_of_node(node));
+ }
+ }
+
cpumask_or(cpus, cpus, cpumask_of_node(pref_nid));
/* honor the task's preferred LLC CPU */
--
2.34.1
^ permalink raw reply related [flat|nested] 25+ messages in thread* Re: [RFC PATCH v3 15/17] sched/cache: Include recently used preferred nodes in LLC scans
2026-10-29 2:56 ` [RFC PATCH v3 15/17] sched/cache: Include recently used preferred nodes in LLC scans Jianyong Wu
@ 2026-10-30 3:05 ` sashiko-bot
0 siblings, 0 replies; 25+ messages in thread
From: sashiko-bot @ 2026-10-30 3:05 UTC (permalink / raw)
To: Jianyong Wu, Ingo Molnar, Peter Zijlstra, Juri Lelli,
Vincent Guittot, Chen Yu, Tim Chen
Cc: Dietmar Eggemann, Steven Rostedt, Ben Segall, Mel Gorman,
Valentin Schneider, K Prateek Nayak, Shrikanth Hegde, Phil Auld,
Andrew Morton, David Hildenbrand, maddy, Michael Ellerman, ljs,
linux-mm, jianyong.wu, zhongyuan, huangsj, wangfengyu, yingzhiwei
Thank you for your contribution! Sashiko AI review found 2 potential issue(s) to consider:
- [Critical] sched/fair: out-of-bounds access on node_epoch due to num_possible_nodes()
- [Medium] sched/cache: premature invalidation and repeated stores on node_epoch in account_mm_sched()
--
commit 75dca431c1e296ff78c3df14b7869d56e2b49b4e
Author: Jianyong Wu <wujianyong@hygon.cn>
sched/cache: Include recently used preferred nodes in LLC scans
This commit records preferred NUMA nodes observed while accounting tasks
that share an mm in a per-mm node_epoch array and includes recently
observed nodes in the LLC scan mask in get_scan_cpumasks(). Stale node
records are expired using the LLC affinity timeout or cleared when the
preferred cache state of the mm is invalidated.
> diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
> index 20a6a7f5c2f74..b93b6e6c9deae 100644
> --- a/kernel/sched/fair.c
> +++ b/kernel/sched/fair.c
> @@ -1594,6 +1594,9 @@ void mm_init_sched(struct mm_struct *mm,
> mm->sc_stat.next_scan = jiffies;
> mm->sc_stat.nr_running_avg = 0;
> mm->sc_stat.footprint = 0;
> + mm->sc_stat.node_epoch = kcalloc(num_possible_nodes(),
> + sizeof(*mm->sc_stat.node_epoch),
> + GFP_KERNEL);
[Severity: Critical]
Can this overflow mm->sc_stat.node_epoch[] on systems with sparse NUMA node
IDs?
In mm_init_sched(), mm->sc_stat.node_epoch is allocated with
num_possible_nodes() elements, which expands to num_node_state(N_POSSIBLE)
and returns the population count of possible nodes rather than the maximum
possible node ID plus one (nr_node_ids).
Later, account_mm_sched() and get_scan_cpumasks() index node_epoch[]
directly by raw node ID via pref_nid and for_each_node(node), which can
yield node IDs up to nr_node_ids - 1:
if (pref_nid != NUMA_NO_NODE && mm->sc_stat.node_epoch)
mm->sc_stat.node_epoch[pref_nid] = epoch;
...
for_each_node(node) {
if ((long)(epoch - READ_ONCE(node_epoch[node])) >
llc_epoch_affinity_timeout)
WRITE_ONCE(node_epoch[node], 0);
}
and in get_scan_cpumasks():
for_each_node(node) {
if (node == pref_nid)
continue;
if (node_epoch[node] > 0)
cpumask_or(cpus, cpus, cpumask_of_node(node));
}
When possible NUMA node IDs are discontiguous (for example, nodes 0 and 2
are possible while node 1 is not, giving num_possible_nodes() == 2 and
nr_node_ids == 3), any node ID >= num_possible_nodes() reads or writes past
the end of the slab buffer, and the memset() in account_mm_sched() only
clears num_possible_nodes() entries.
Should the kcalloc() in mm_init_sched() and the memset() in
account_mm_sched() use nr_node_ids instead of num_possible_nodes()?
[ ... ]
> @@ -1713,6 +1726,13 @@ void account_mm_sched(struct rq *rq, struct task_struct *p, s64 delta_exec)
> epoch = rq->cpu_epoch;
> }
>
> + node_epoch = mm->sc_stat.node_epoch;
> +#ifdef CONFIG_NUMA_BALANCING
> + pref_nid = READ_ONCE(p->numa_preferred_nid);
> +#endif
> + if (pref_nid != NUMA_NO_NODE && mm->sc_stat.node_epoch)
> + mm->sc_stat.node_epoch[pref_nid] = epoch;
> +
> /*
> * If this process hasn't hit task_cache_work() for a while invalidate
> * its preferred state.
> @@ -1722,6 +1742,16 @@ void account_mm_sched(struct rq *rq, struct task_struct *p, s64 delta_exec)
> exceed_llc_capacity(mm, cpu_of(rq))) {
> if (READ_ONCE(mm->sc_stat.cpu) != -1)
> WRITE_ONCE(mm->sc_stat.cpu, -1);
> +
> + if (node_epoch)
> + memset(mm->sc_stat.node_epoch, 0,
> + sizeof(*node_epoch) * num_possible_nodes());
> + } else if (node_epoch) {
> + for_each_node(node) {
> + if ((long)(epoch - READ_ONCE(node_epoch[node])) >
> + llc_epoch_affinity_timeout)
> + WRITE_ONCE(node_epoch[node], 0);
> + }
> }
[Severity: Medium]
Does updating and expiring mm->sc_stat.node_epoch[] here in
account_mm_sched() prematurely wipe out recorded preferred nodes and cause
repeated stores to the shared array on every update_se() call?
First, in task_tick_fair(), entity_tick() runs before task_tick_cache():
task_tick_fair()
entity_tick()
update_curr()
update_se()
account_mm_sched()
task_tick_cache()
When a process has not run task_tick_cache() for more than
llc_epoch_affinity_timeout epochs, account_mm_sched() writes
mm->sc_stat.node_epoch[pref_nid] = epoch and immediately hits
(long)(epoch - READ_ONCE(mm->sc_stat.epoch)) > llc_epoch_affinity_timeout,
zeroing the entire node_epoch[] array with memset() right before
task_tick_cache() updates mm->sc_stat.epoch and queues task_cache_work() ->
get_scan_cpumasks().
Second, when invalid_llc_nr() or exceed_llc_capacity() holds (such as for
single-threaded tasks or processes exceeding LLC capacity),
account_mm_sched() writes node_epoch[pref_nid] = epoch and then
unconditionally zeroes the array via memset() on every update_se() call
(ticks, wakeups, and context switches), unlike mm->sc_stat.cpu which checks
READ_ONCE(mm->sc_stat.cpu) != -1 before writing.
Third, in the else branch:
for_each_node(node) {
if ((long)(epoch - READ_ONCE(node_epoch[node])) >
llc_epoch_affinity_timeout)
WRITE_ONCE(node_epoch[node], 0);
}
when node_epoch[node] is already 0, (long)(epoch - 0) >
llc_epoch_affinity_timeout is always true once rq->cpu_epoch exceeds
llc_epoch_affinity_timeout, so every CPU running a thread of the mm
repeatedly executes WRITE_ONCE(node_epoch[node], 0) for every unused node on
every update_se() call.
Should node_epoch[pref_nid] only be updated after the invalidation check
when the value actually changes, and should the expiration loop check that
node_epoch[node] is non-zero before writing 0?
--
Sashiko AI review · https://sashiko.dev/#/patchset/20261029022036.4002331-1-wujianyong@hygon.cn?part=15
^ permalink raw reply [flat|nested] 25+ messages in thread
* [RFC PATCH v3 16/17] sched/cache: Drop stale preferred LLC checks
2026-10-29 2:20 [RFC PATCH v3 00/17] sched: Scale cache-aware aggregation at LLC granularity Jianyong Wu
` (14 preceding siblings ...)
2026-10-29 2:56 ` [RFC PATCH v3 15/17] sched/cache: Include recently used preferred nodes in LLC scans Jianyong Wu
@ 2026-10-29 2:58 ` Jianyong Wu
2026-10-30 3:05 ` sashiko-bot
2026-10-29 2:59 ` [RFC PATCH v3 17/17] sched/debug: Show cache placement and preferred LLC in /proc/<pid>/sched Jianyong Wu
16 siblings, 1 reply; 25+ messages in thread
From: Jianyong Wu @ 2026-10-29 2:58 UTC (permalink / raw)
To: Ingo Molnar, Peter Zijlstra, Juri Lelli, Vincent Guittot, Chen Yu,
Tim Chen
Cc: Dietmar Eggemann, Steven Rostedt, Ben Segall, Mel Gorman,
Valentin Schneider, K Prateek Nayak, Shrikanth Hegde, Phil Auld,
Andrew Morton, David Hildenbrand, maddy, Michael Ellerman, ljs,
linux-kernel, linux-mm, wujianyong, jianyong.wu, zhongyuan,
huangsj, wangfengyu, yingzhiwei
With multi-LLC aggregation, an mm's preferred LLC can be
outside a task's preferred NUMA node. Do not discard that LLC when
calculating the task's preference.
Likewise, an LLC migration may select a destination other than the
task's preferred LLC. Let can_migrate_llc_task() decide whether the
migration is allowed instead of rejecting the task based on an exact
preferred-LLC match.
Signed-off-by: Jianyong Wu <wujianyong@hygon.cn>
---
kernel/sched/fair.c | 29 +----------------------------
1 file changed, 1 insertion(+), 28 deletions(-)
diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
index b93b6e6c9dea..5d11f9b7f685 100644
--- a/kernel/sched/fair.c
+++ b/kernel/sched/fair.c
@@ -1669,27 +1669,9 @@ static int get_pref_llc(struct task_struct *p, struct mm_struct *mm)
return -1;
mm_sched_cpu = READ_ONCE(mm->sc_stat.cpu);
- if (mm_sched_cpu != -1) {
+ if (mm_sched_cpu != -1)
mm_sched_llc = llc_id(mm_sched_cpu);
-#ifdef CONFIG_NUMA_BALANCING
- /*
- * Don't assign preferred LLC if it
- * conflicts with NUMA balancing.
- * This can happen when sched_setnuma() gets
- * called, however it is not much of an issue
- * because we expect account_mm_sched() to get
- * called fairly regularly -- at a higher rate
- * than sched_setnuma() at least -- and thus the
- * conflict only exists for a short period of time.
- */
- if (static_branch_likely(&sched_numa_balancing) &&
- p->numa_preferred_nid >= 0 &&
- cpu_to_node(mm_sched_cpu) != p->numa_preferred_nid)
- mm_sched_llc = -1;
-#endif
- }
-
return mm_sched_llc;
}
@@ -10898,15 +10880,6 @@ static bool migrate_degrades_llc(struct task_struct *p, struct lb_env *env)
if (env->sd->nr_balance_failed >= env->sd->cache_nice_tries + 1)
return false;
- /*
- * We know the env->src_cpu has some tasks prefer to
- * run on env->dst_cpu, skip the tasks do not prefer
- * env->dst_cpu, and find the one that prefers.
- */
- if (env->migration_type == migrate_llc_task &&
- READ_ONCE(p->preferred_llc) != llc_id(env->dst_cpu))
- return true;
-
if (can_migrate_llc_task(env->src_cpu,
env->dst_cpu, p) != mig_forbid)
return false;
--
2.34.1
^ permalink raw reply related [flat|nested] 25+ messages in thread* Re: [RFC PATCH v3 16/17] sched/cache: Drop stale preferred LLC checks
2026-10-29 2:58 ` [RFC PATCH v3 16/17] sched/cache: Drop stale preferred LLC checks Jianyong Wu
@ 2026-10-30 3:05 ` sashiko-bot
0 siblings, 0 replies; 25+ messages in thread
From: sashiko-bot @ 2026-10-30 3:05 UTC (permalink / raw)
To: Jianyong Wu, Ingo Molnar, Peter Zijlstra, Juri Lelli,
Vincent Guittot, Chen Yu, Tim Chen
Cc: Dietmar Eggemann, Steven Rostedt, Ben Segall, Mel Gorman,
Valentin Schneider, K Prateek Nayak, Shrikanth Hegde, Phil Auld,
Andrew Morton, David Hildenbrand, maddy, Michael Ellerman, ljs,
linux-mm, jianyong.wu, zhongyuan, huangsj, wangfengyu, yingzhiwei
Thank you for your contribution! Sashiko AI review found 1 potential issue(s) to consider:
- [Medium] sched/fair: migrate_degrades_llc() allows unrelated tasks in migrate_llc_task
--
commit a6df5e882c3ba89fef18f6405775608279e27938
Author: Jianyong Wu <wujianyong@hygon.cn>
sched/cache: Drop stale preferred LLC checks
This commit removes the NUMA preference check in get_pref_llc() and drops
the exact preferred_llc check in migrate_degrades_llc() so that
can_migrate_llc_task() determines whether an LLC migration is allowed.
> diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
> index b93b6e6c9deae..5d11f9b7f685f 100644
> --- a/kernel/sched/fair.c
> +++ b/kernel/sched/fair.c
[ ... ]
> @@ -10898,15 +10880,6 @@ static bool migrate_degrades_llc(struct task_struct *p, struct lb_env *env)
> if (env->sd->nr_balance_failed >= env->sd->cache_nice_tries + 1)
> return false;
>
> - /*
> - * We know the env->src_cpu has some tasks prefer to
> - * run on env->dst_cpu, skip the tasks do not prefer
> - * env->dst_cpu, and find the one that prefers.
> - */
> - if (env->migration_type == migrate_llc_task &&
> - READ_ONCE(p->preferred_llc) != llc_id(env->dst_cpu))
> - return true;
> -
> if (can_migrate_llc_task(env->src_cpu,
> env->dst_cpu, p) != mig_forbid)
> return false;
[Severity: Medium]
Does removing this check in migrate_degrades_llc() allow detach_tasks() to
pull unrelated tasks during a migrate_llc_task balance pass instead of the
task that actually prefers moving toward env->dst_cpu?
When a source group is classified as group_llc_balance, calculate_imbalance()
sets up a single-task migration pass:
kernel/sched/fair.c:calculate_imbalance() {
if (busiest->group_type == group_llc_balance) {
/* Move a task that prefer local LLC */
env->migration_type = migrate_llc_task;
env->imbalance = 1;
return;
}
}
And detach_tasks() stops as soon as a single task passes can_migrate_task():
kernel/sched/fair.c:detach_tasks() {
case migrate_llc_task:
env->imbalance--;
break;
}
Without a check restricting migrate_llc_task to tasks that gain LLC affinity
by moving to env->dst_cpu, migrate_degrades_llc() relies solely on
can_migrate_llc_task(env->src_cpu, env->dst_cpu, p) != mig_forbid.
However, can_migrate_llc_task() returns mig_unrestricted for kernel threads
(!p->mm), tasks with mm->sc_stat.cpu < 0, single-threaded tasks matching
invalid_llc_nr(), and tasks matching exceed_llc_capacity():
kernel/sched/fair.c:can_migrate_llc_task() {
mm = p->mm;
if (!mm)
return mig_unrestricted;
cpu = READ_ONCE(mm->sc_stat.cpu);
if (cpu < 0 || cpus_share_cache(src_cpu, dst_cpu))
return mig_unrestricted;
/* skip cache aware load balance for too many threads */
if (invalid_llc_nr(mm, p, dst_cpu) ||
exceed_llc_capacity(mm, dst_cpu)) {
if (READ_ONCE(mm->sc_stat.cpu) != -1)
WRITE_ONCE(mm->sc_stat.cpu, -1);
return mig_unrestricted;
}
to_pref = if_to_prefer(src_cpu, dst_cpu, llc_id(cpu));
return can_migrate_llcs(src_cpu, dst_cpu,
p, to_pref);
}
In addition, when to_pref is false, can_migrate_llcs() can still return
mig_unrestricted or mig_llc. And when env->tol <= 1, update_sg_lb_stats()
and sched_balance_find_src_rq() only count affinity_score for tasks with
p->preferred_llc == llc_id(env->dst_cpu), whereas can_migrate_llc_task()
calls if_to_prefer() unconditionally.
If any such unrelated task precedes the target task on env->src_rq->cfs_tasks
(or if the target task is currently running on env->src_rq), won't
detach_tasks() detach the wrong task, decrement env->imbalance to 0, exit the
loop early, and also prevent need_active_balance() from migrating the running
LLC-preferring task?
--
Sashiko AI review · https://sashiko.dev/#/patchset/20261029022036.4002331-1-wujianyong@hygon.cn?part=16
^ permalink raw reply [flat|nested] 25+ messages in thread
* [RFC PATCH v3 17/17] sched/debug: Show cache placement and preferred LLC in /proc/<pid>/sched
2026-10-29 2:20 [RFC PATCH v3 00/17] sched: Scale cache-aware aggregation at LLC granularity Jianyong Wu
` (15 preceding siblings ...)
2026-10-29 2:58 ` [RFC PATCH v3 16/17] sched/cache: Drop stale preferred LLC checks Jianyong Wu
@ 2026-10-29 2:59 ` Jianyong Wu
16 siblings, 0 replies; 25+ messages in thread
From: Jianyong Wu @ 2026-10-29 2:59 UTC (permalink / raw)
To: Ingo Molnar, Peter Zijlstra, Juri Lelli, Vincent Guittot, Chen Yu,
Tim Chen
Cc: Dietmar Eggemann, Steven Rostedt, Ben Segall, Mel Gorman,
Valentin Schneider, K Prateek Nayak, Shrikanth Hegde, Phil Auld,
Andrew Morton, David Hildenbrand, maddy, Michael Ellerman, ljs,
linux-kernel, linux-mm, wujianyong, jianyong.wu, zhongyuan,
huangsj, wangfengyu, yingzhiwei, XIAO WU
Print the mm's selected CPU and its LLC and NUMA node, alongside the
task's preferred LLC and its NUMA node. This helps diagnose cache-aware
scheduling and task placement decisions.
Suggested-by: XIAO WU <xiaowu.417@qq.com>
Signed-off-by: Jianyong Wu <wujianyong@hygon.cn>
---
kernel/sched/debug.c | 28 +++++++++++++++++++++++++++-
1 file changed, 27 insertions(+), 1 deletion(-)
diff --git a/kernel/sched/debug.c b/kernel/sched/debug.c
index 40584b27ea0c..d18dbc1da67c 100644
--- a/kernel/sched/debug.c
+++ b/kernel/sched/debug.c
@@ -9,7 +9,9 @@
#include <linux/debugfs.h>
#include <linux/nmi.h>
#include <linux/log2.h>
+#include <linux/sched/clock.h>
#include "sched.h"
+#include <linux/sched/debug.h>
/*
* This allows printing both to /sys/kernel/debug/sched/debug and
@@ -1304,7 +1306,6 @@ void print_numa_stats(struct seq_file *m, int node, unsigned long tsf,
}
#endif
-
static void sched_show_numa(struct task_struct *p, struct seq_file *m)
{
#ifdef CONFIG_NUMA_BALANCING
@@ -1320,6 +1321,30 @@ static void sched_show_numa(struct task_struct *p, struct seq_file *m)
#endif /* CONFIG_NUMA_BALANCING */
}
+static void sched_show_cache(struct task_struct *p, struct seq_file *m)
+{
+#ifdef CONFIG_SCHED_CACHE
+ struct mm_struct *mm = NULL;
+ int sc_cpu, sc_llc, sc_node, pref_llc, pref_node;
+
+ mm = get_task_mm(p);
+
+ if (mm) {
+ sc_cpu = READ_ONCE(mm->sc_stat.cpu);
+ sc_llc = (sc_cpu >= 0) ? per_cpu(sd_llc_id, sc_cpu) : -1;
+ sc_node = (sc_cpu >= 0) ? cpu_to_node(sc_cpu) : -1;
+ pref_llc = READ_ONCE(p->preferred_llc);
+ pref_node = (pref_llc >= 0) ? llc_to_node(pref_llc) : -1;
+
+ SEQ_printf(m, "sc_stat_cpu=%d, sc_llc=%d, sc_node=%d\n",
+ sc_cpu, sc_llc, sc_node);
+ SEQ_printf(m, "preferred_llc=%d, preferred_llc_node=%d\n",
+ pref_llc, pref_node);
+ mmput(mm);
+ }
+#endif /* CONFIG_SCHED_CACHE */
+}
+
void proc_sched_show_task(struct task_struct *p, struct pid_namespace *ns,
struct seq_file *m)
{
@@ -1439,6 +1464,7 @@ void proc_sched_show_task(struct task_struct *p, struct pid_namespace *ns,
}
sched_show_numa(p, m);
+ sched_show_cache(p, m);
}
void proc_sched_set_task(struct task_struct *p)
--
2.34.1
^ permalink raw reply related [flat|nested] 25+ messages in thread