RE: [RFC PATCH v2 11/23] sched/cache: Introduce helpers for task migration decisions

[Jianyong Wu]

Hi Tim,

> -----Original Message-----
> From: Tim Chen <tim.c.chen@xxxxxxxxxxxxxxx>
> Sent: Thursday, September 3, 2026 5:11 AM
> To: Jianyong Wu <wujianyong@xxxxxxxx>; Ingo Molnar
> <mingo@xxxxxxxxxx>; Peter Zijlstra <peterz@xxxxxxxxxxxxx>; Juri Lelli
> <juri.lelli@xxxxxxxxxx>; Vincent Guittot <vincent.guittot@xxxxxxxxxx>;
> Chen Yu <yu.c.chen@xxxxxxxxx>
> Cc: Dietmar Eggemann <dietmar.eggemann@xxxxxxx>; Steven Rostedt
> <rostedt@xxxxxxxxxxx>; Ben Segall <bsegall@xxxxxxxxxx>; Mel Gorman
> <mgorman@xxxxxxx>; Valentin Schneider <vschneid@xxxxxxxxxx>; K
> Prateek Nayak <kprateek.nayak@xxxxxxx>; Shrikanth Hegde
> <sshegde@xxxxxxxxxxxxx>; Phil Auld <pauld@xxxxxxxxxx>; Andrew
> Morton <akpm@xxxxxxxxxxxxxxxxxxxx>; David Hildenbrand
> <david@xxxxxxxxxx>; linux-kernel@xxxxxxxxxxxxxxx; linux-mm@xxxxxxxxx;
> jianyong.wu@xxxxxxxxxxx; Yuan Zhong <zhongyuan@xxxxxxxx>; Huangsj
> <huangsj@xxxxxxxx>; Fengyu Wang <wangfengyu@xxxxxxxx>; Zhiwei Ying
> <yingzhiwei@xxxxxxxx>; justin.he@xxxxxxx
> Subject: Re: [RFC PATCH v2 11/23] sched/cache: Introduce helpers for task
> migration decisions
> 
> On Thu, 2026-08-27 at 20:28 +0800, Jianyong Wu wrote:
> > Cache-aware scheduling makes migration decisions purely based on LLC
> > affinity, allowing moves only toward a task's preferred LLC. This rigid
> > policy cannot handle workloads that do not fit within a single LLC.
> > A better approach is on-demand thread aggregation across LLCs: as the
> > thread count increases, additional LLCs are recruited to host threads,
> > enabling workload scaling at LLC granularity.
> >
> > To realize this behaviour, we need to pick the next eligible LLC once
> > currently selected LLCs become saturated.
> >
> > Earlier patches have built node-level and LLC-level distance matrices.
> > From these matrices we obtain a node-affinity sequence, and within each
> > node an intra-node LLC-affinity sequence. These sequences provide the
> > priority order used to pick subsequent LLC candidates.
> >
> > This patch adds a helper routine to determine whether task migration
> > is permitted. It checks whether the destination CPU resides within the
> > first eligible LLC. Migration is permitted if this condition holds,
> > and vice versa.
> >
> > The first eligible LLC is resolved via a two-stage policy. The first
> > stage operates at NUMA-node granularity: we iterate over the
> > node-affinity sequence to find the first node that can accommodate
> > the task. Once such a node is found, the second stage selects the
> > first capacity-available LLC within this node by walking the
> > intra-node LLC-affinity sequence.
> >
> > Signed-off-by: Jianyong Wu <wujianyong@xxxxxxxx>
> > ---
> >  kernel/sched/fair.c | 185
> ++++++++++++++++++++++++++++++++++++++++++++
> >  1 file changed, 185 insertions(+)
> >
> > diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
> > index dc7bbdb1ab98..cfbd596992ab 100644
> > --- a/kernel/sched/fair.c
> > +++ b/kernel/sched/fair.c
> > @@ -10610,6 +10610,191 @@ static enum llc_mig can_migrate_llc(int
> src_cpu, int dst_cpu,
> >  	return mig_llc;
> >  }
> >
> > +/*
> > + * Like get_llc_stats but for sched domain that above LLC level.
> > + * Based on get_llc_stats, we can accumulate utilization and cap for
> > + * sched domain in the granularity of LLC.
> > + */
> > +static bool get_span_stats(const struct cpumask *span, unsigned long
> *util_out,
> > +					unsigned long *cap_out)
> > +{
> > +	cpumask_var_t mask;
> > +	int cpu;
> > +	unsigned long util_tmp, cap_tmp, util = 0, cap = 0;
> > +	struct sched_domain *sd_tmp;
> > +
> > +	if (!span || !util_out || !cap_out)
> > +		return false;
> > +
> > +	if (!alloc_cpumask_var(&mask, GFP_ATOMIC))
> > +		return false;
> > +
> > +	cpumask_copy(mask, span);
> > +	for_each_cpu(cpu, mask) {
> > +		if (!get_llc_stats(cpu, &util_tmp, &cap_tmp)) {
> > +			free_cpumask_var(mask);
> > +			return false;
> > +		}
> > +
> > +		sd_tmp = rcu_dereference(per_cpu(sd_llc, cpu));
> > +		cpumask_andnot(mask, mask, sched_domain_span(sd_tmp));
> > +		util += util_tmp;
> > +		cap += cap_tmp;
> > +	}
> > +
> > +	*util_out = util;
> > +	*cap_out = cap;
> > +
> > +	free_cpumask_var(mask);
> > +	return true;
> > +}
> > +
> > +/*
> > + * Decide if migration should happen on a specific node.
> > + * The node here is an LLC or a NUMA.
> > + */
> > +static enum llc_mig __maybe_unused can_migrate_node(int src_cpu, int
> dst_cpu,
> > +			struct task_struct *p, bool to_pref)
> > +{
> > +	const struct cpumask *span;
> > +	struct mm_struct *mm;
> > +	unsigned long dst_util, dst_cap, tsk_util = 0;
> > +	unsigned long src_util = 0, src_cap = 0;
> > +	unsigned long acc_util = 0, acc_cap = 0;
> > +	int node, target_cpu = src_cpu;
> > +	int get_src = 0;
> > +
> > +	if (!get_llc_stats(dst_cpu, &dst_util, &dst_cap))
> > +		return mig_unrestricted;
> > +
> > +	if (!get_llc_stats(src_cpu, &src_util, &src_cap))
> > +		src_cap = 0;
> > +
> > +	if (p) {
> > +		mm = p->mm;
> > +		if (mm) {
> > +			if (mm->sc_stat.cpu >= 0)
> > +				target_cpu = mm->sc_stat.cpu;
> > +		}
> > +		tsk_util = task_util(p);
> > +	}
> > +
> > +	dst_util = dst_util + tsk_util;
> > +
> > +	if (to_pref) {
> > +		unsigned long dst_pre = dst_util - tsk_util;
> 
> dst_pre was limited to this scope but was used later in a different
> scope.  Should move the declaration to parent scope.
>
> > +
> > +		if (fits_llc_capacity(dst_util, dst_cap))
> > +			return mig_llc;
> > +
> > +		/*
> > +		 * The destination is over the margin. That is a reason to
> > +		 * refuse a task while the margin can still be met, but not
> > +		 * while every LLC of the node is over it: no placement
> > +		 * satisfies the margin then, and refusing every migration
> > +		 * leaves the imbalance in place.
> > +		 *
> > +		 * Let the task through when the move still lowers the peak,
> > +		 * that is when the source is noticeably heavier than the
> > +		 * destination and carries at least two more tasks worth of
> > +		 * utilization. The second condition keeps the destination
> > +		 * from becoming the heavier side, which would bounce the
> > +		 * task straight back.
> > +		 */
> > +		if (src_cap && util_greater(src_util, dst_pre) &&
> > +		    src_util >= dst_pre + 2 * tsk_util)
> > +			return mig_llc;
> > +
> > +		return mig_forbid;
> > +	}
> > +
> > +	for_each_sched_node(target_cpu, node) {
> > +		unsigned long u = 0, c = 0, nu, nc;
> > +
> > +		/*
> > +		 * The walk starts at the anchor, so the nodes it crosses before
> > +		 * reaching the source say nothing about this migration: the task
> > +		 * does not live there and is not going there. Judging them only
> > +		 * lets an unrelated node with room refuse the move. Start at
> the
> > +		 * node the task actually sits on.
> > +		 */
> > +		if (!get_src) {
> > +			if (!cpumask_test_cpu(src_cpu, cpumask_of_node(node)))
> > +				continue;
> > +			else
> > +				get_src = 1;
> > +		}
> > +
> > +		if (cpumask_test_cpu(dst_cpu, cpumask_of_node(node))) {
> > +			nu = 0;
> > +			nc = 0;
> > +			for_each_llc_node_span(node, span) {
> > +				get_span_stats(span, &u, &c);
> > +				nu += u;
> > +				nc += c;
> > +				if (cpumask_test_cpu(dst_cpu, span)) {
> > +					if (fits_llc_capacity(u + tsk_util, c))
> > +						return mig_llc;
> > +
> > +					/*
> > +					 * The destination is over the margin,
> > +					 * but so may be the source. Refusing
> > +					 * then leaves the peak where it is:
> > +					 * a LLC at seven tasks stays at seven
> > +					 * while a neighbour in the same node
> > +					 * sits at four, because taking one
> > +					 * more would put that neighbour over
> > +					 * the margin as well.
> > +					 *
> > +					 * Let the task through when the move
> > +					 * still lowers the peak, guarded the
> > +					 * same way as the aggregation path:
> > +					 * the source must be noticeably
> > +					 * heavier and carry at least two more
> > +					 * tasks worth of utilization, so the
> > +					 * destination cannot end up the
> > +					 * heavier side and bounce it back.
> > +					 */
> > +					if (src_cap &&
> > +					    util_greater(src_util, u + tsk_util) &&
> > +					    src_util >= u + 2 * tsk_util)
> > +						return mig_llc;
> > +
> > +					return mig_forbid;
> > +				/*
> > +				 * A nearer LLC only justifies vetoing this
> > +				 * migration if the task would actually fit
> > +				 * there, so account for its utilization the
> > +				 * same way the destination branch above does.
> > +				 * Without it a LLC already holding one task
> > +				 * per core still reads as having room and
> > +				 * vetoes every migration towards a farther,
> > +				 * genuinely idle LLC.
> > +				 */
> > +				} else if (fits_llc_capacity(acc_util + nu + tsk_util,
> > +						acc_cap + nc)
> > +						&& fits_llc_capacity(u + tsk_util, c)
> > +						&& !util_greater(u, dst_pre))
> 
> Got a compile error here when I try to build the code.  Seems like dst_pre
> was declared in previous scope above.
> Likely the posted version is slightly different from the tested version.
>

Right, the dst_pre fix landed in patch 20 but wasn't folded back into this
patch, so patch 11 alone doesn't build -- the full series builds because
patch 20 fixes it. I'll squash the fix into this patch in the next version.

I will also compile-test each individual commit before posting the next version.

Thanks
Jianyong
 
> $ make
>   DESCEND objtool
>   CC      kernel/sched/fair.o
> kernel/sched/fair.c: In function ‘can_migrate_node’:
> kernel/sched/fair.c:10855:69: error: ‘dst_pre’ undeclared (first use in this
> function)
> 10855 |
> && !util_greater(u, dst_pre))
>       |
> ^~~~~~~
> kernel/sched/fair.c:10618:27: note: in definition of macro ‘util_greater’
> 10618 |         ((util1) * 100 > (util2) * (100 + llc_imb_pct))
>       |                           ^~~~~
> kernel/sched/fair.c:10855:69: note: each undeclared identifier is reported
> only once for each function it appears in
> 10855 |
> && !util_greater(u, dst_pre))
>       |
> ^~~~~~~
> kernel/sched/fair.c:10618:27: note: in definition of macro ‘util_greater’
> 10618 |         ((util1) * 100 > (util2) * (100 + llc_imb_pct))
>       |                           ^~~~~
> make[4]: *** [scripts/Makefile.build:290: kernel/sched/fair.o] Error 1
> make[3]: *** [scripts/Makefile.build:551: kernel/sched] Error 2
> make[2]: *** [scripts/Makefile.build:551: kernel] Error 2
> make[1]: *** [/home/tim/linux/Makefile:2229: .] Error 2
> make: *** [Makefile:248: __sub-make] Error 2
> 
> Tim
> 
> > +					return mig_forbid;
> > +			}
> > +		}
> > +
> > +		/* Don't migrate if this is a good place to live. */
> > +		for_each_llc_node_span(node, span) {
> > +			get_span_stats(span, &u, &c);
> > +			if (cpumask_test_cpu(src_cpu, span)) {
> > +				if (fits_llc_capacity(u, c))
> > +					return mig_forbid;
> > +			} else {
> > +				if (fits_llc_capacity(u + tsk_util, c))
> > +					return mig_forbid;
> > +			}
> > +		}
> > +	}
> > +
> > +	return mig_unrestricted;
> > +}
> > +
> >  /*
> >   * Check if task p can migrate from source LLC to
> >   * destination LLC in terms of cache aware load balance.