Re: [PATCH v11 1/2] sched/cache: Reduce the overhead of task_cache_work by only scan the visisted cpus
From: Tim Chen
Date: Mon Nov 16 2026 - 18:38:55 EST
On Wed, 2026-11-11 at 11:04 +0000, Luo Gengkun wrote:
Nit:
subject would read better as
Reduce the overhead of task_cache_work() by scanning only the visited cpuswh
> The overhead of task_cache_work() is high, especially in multi-NUMA systems.
> Currently, task_cache_work() tries to find the prewf_llc by scanning all CPUs
> in the system. However, most of these scans are meaningless, such as those
> for CPUs that have never been visited or were accessed a long time ago.
>
> To address this problem, introduce visited_cpus to track the visited CPUs
> and evict them once they have not been accessed for a duration exceeding
> llc_epoch_affinity_timeout.
>
> Now that we know exactly which CPUs to scan from visited_cpus, we can remove
> get_scan_cpumasks().
>
> Below are the Redis test results conducted on AMD server.
>
> When NUMA balancing is disabled:
>
> valkey-benchmark rps | baseline | schedcache | schedcache_visit
> | (no cache aware) | (without this series) | (with this series)
> ----------------------+---------------------+---------------------+-----------+-------------------+--------
> | p99 latency(ms) | p99 latency(ms) | DIFF(%) | p99 latency(ms) | DIFF(%)
> 400000 | 0.436 | 0.554 | -25.68% | 0.441 | -1.14%
>
> Additionally, the output of perf top -e cycles:k highlights the overhead
> incurred by task_cache_work():
>
> valkey-benchmark rps | schedcache | schedcache_visit
> | (without this series) | (with this series)
> ----------------------+-------------------------------------------+---------------------------------------
> 400000 | 0.81% [kernel] [k] task_cache_work | 0.02% [kernel] [k] task_cache_work
>
> The trace data is shown below:
>
> echo NO_SC_VISIT > /sys/kernel/debug/sched/features
> redis-server-24660 [195] ..... 2916.005989: sched_cache_scan: comm=redis-server pid=24660 scan=384
> valkey-benchmar-48836 [317] ..... 2916.005993: sched_cache_scan: comm=valkey-benchmar pid=48836 scan=384
> valkey-benchmar-48487 [310] ..... 2916.006002: sched_cache_scan: comm=valkey-benchmar pid=48487 scan=384
>
> echo SC_VISIT > /sys/kernel/debug/sched/features
> redis-server-29080 [225] ..... 2876.257909: sched_cache_scan: comm=redis-server pid=29080 scan=14
> redis-server-26694 [018] ..... 2876.257909: sched_cache_scan: comm=redis-server pid=26694 scan=13
> valkey-benchmar-48198 [103] ..... 2876.257909: sched_cache_scan: comm=valkey-benchmar pid=48198 scan=16
>
> The above results show that this series significantly reduces the overhead
> of task_cache_work() by decreasing the number of CPUs that need to be
> scanned, from 384 to 16, when NUMA balancing is disabled.
>
> Even with NUMA balancing enabled, this patch provides better performance
> benefits. The following tests were conducted with NUMA balancing enabled:
>
> valkey-benchmark rps | baseline | schedcache | schedcache_visit
> | (no cache aware) | (without this series) | (with this series)
> ----------------------+---------------------+---------------------+-----------+-------------------+--------
> | p99 latency(ms) | p99 latency(ms) | DIFF(%) | p99 latency(ms) | DIFF(%)
> 400000 | 0.437 | 0.454 | -3.89% | 0.442 | -1.14%
>
> The overhead of task_cache_work() is as follows:
>
> valkey-benchmark rps | schedcache | schedcache_visit
> | (without this series) | (with this series)
> ----------------------+-------------------------------------------+---------------------------------------
> 400000 | 0.13% [kernel] [k] task_cache_work | 0.03% [kernel] [k] task_cache_work
>
> Hackbench testing was also conducted. The results below show that this
> series does not affect the accuracy of cache-aware scheduling.
>
> =========================================
> Hackbench Comparison: baseline vs schedcache
> =========================================
> MODE GROUPS FDS | baseline(std) | schedcache(std) | DIFF(%) | VERDICT
> ---------- ------ -----+--------------------+--------------------+------------+-----------
> threads 1 10 | 113.200 (4.22%) | 67.300 (1.32%) | 40.55% | IMPROVED
> threads 1 2 | 16.555 (4.11%) | 11.020 (1.66%) | 33.43% | IMPROVED
> threads 1 20 | 250.774 (1.26%) | 265.026 (5.44%) | -5.68% | REGRESSED
> threads 1 4 | 42.117 (1.44%) | 27.758 (1.64%) | 34.09% | IMPROVED
> threads 1 6 | 65.140 (4.31%) | 39.182 (1.38%) | 39.85% | IMPROVED
> threads 1 8 | 84.286 (1.29%) | 53.721 (1.58%) | 36.26% | IMPROVED
> threads 2 10 | 122.592 (0.44%) | 113.365 (4.93%) | 7.53% | IMPROVED
> threads 2 2 | 17.702 (4.09%) | 10.473 (0.42%) | 40.84% | IMPROVED
> threads 2 20 | 336.457 (1.77%) | 314.108 (1.51%) | 6.64% | IMPROVED
> threads 2 4 | 43.989 (0.88%) | 27.067 (3.38%) | 38.47% | IMPROVED
> threads 2 6 | 69.322 (0.85%) | 41.707 (4.19%) | 39.84% | IMPROVED
> threads 2 8 | 103.767 (1.81%) | 58.518 (3.00%) | 43.61% | IMPROVED
> threads 4 10 | 148.882 (3.56%) | 149.449 (1.06%) | -0.38% | REGRESSED
> threads 4 2 | 18.909 (2.96%) | 11.063 (2.08%) | 41.49% | IMPROVED
> threads 4 20 | 724.943 (2.14%) | 631.222 (3.92%) | 12.93% | IMPROVED
> threads 4 4 | 48.191 (1.91%) | 27.352 (5.35%) | 43.24% | IMPROVED
> threads 4 6 | 79.725 (3.84%) | 78.732 (4.10%) | 1.25% | IMPROVED
> threads 4 8 | 108.768 (1.36%) | 105.928 (1.65%) | 2.61% | IMPROVED
>
> Hackbench Comparison: schedcache vs schedcache_visit
> =========================================
> MODE GROUPS FDS | schedcache(std) |schedcache_visit(std) | DIFF(%) | VERDICT
> ---------- ------ -----+--------------------+----------------------+---------+-----------
> threads 1 10 | 67.300 (1.32%) | 67.014 (0.96%) | 0.42% | IMPROVED
> threads 1 2 | 11.020 (1.66%) | 10.557 (1.46%) | 4.20% | IMPROVED
> threads 1 20 | 265.026 (5.44%) | 212.366 (16.32%) | 19.87% | IMPROVED
> threads 1 4 | 27.758 (1.64%) | 25.711 (1.32%) | 7.37% | IMPROVED
> threads 1 6 | 39.182 (1.38%) | 38.914 (0.34%) | 0.68% | IMPROVED
> threads 1 8 | 53.721 (1.58%) | 52.889 (0.27%) | 1.55% | IMPROVED
> threads 2 10 | 121.203 (6.99%) | 124.254 (1.38%) | -2.52% | REGRESSED
> threads 2 2 | 10.473 (0.42%) | 11.206 (5.91%) | -7.00% | REGRESSED
> threads 2 20 | 314.108 (1.51%) | 301.754 (1.95%) | 3.93% | IMPROVED
> threads 2 4 | 27.067 (3.38%) | 28.028 (2.01%) | -3.55% | REGRESSED
> threads 2 6 | 41.707 (4.19%) | 42.149 (3.35%) | -1.06% | REGRESSED
> threads 2 8 | 58.518 (3.00%) | 57.133 (4.39%) | 2.37% | IMPROVED
> threads 4 10 | 149.449 (1.06%) | 141.407 (0.08%) | 5.38% | IMPROVED
> threads 4 2 | 11.063 (2.08%) | 11.360 (5.85%) | -2.68% | REGRESSED
> threads 4 20 | 631.222 (3.92%) | 622.780 (2.49%) | 1.34% | IMPROVED
> threads 4 4 | 27.352 (5.35%) | 27.947 (5.37%) | -2.18% | REGRESSED
> threads 4 6 | 78.732 (4.10%) | 73.911 (0.70%) | 6.12% | IMPROVED
> threads 4 8 | 105.928 (1.65%) | 107.535 (3.29%) | -1.52% | REGRESSED
>
> Tested-by: K Prateek Nayak <kprateek.nayak@xxxxxxx>
> Tested-by: Chen Yu <yu.c.chen@xxxxxxxxx>
> Reviewed-by: Chen Yu <yu.c.chen@xxxxxxxxx>
> Signed-off-by: Luo Gengkun <luogengkun@xxxxxxxxxxxxxxx>
> ---
> include/linux/sched.h | 2 +
> kernel/sched/fair.c | 99 ++++++++++++++++++-------------------------
> 2 files changed, 43 insertions(+), 58 deletions(-)
>
> diff --git a/include/linux/sched.h b/include/linux/sched.h
> index e4f6323d7855..1b08925c6358 100644
> --- a/include/linux/sched.h
> +++ b/include/linux/sched.h
> @@ -2385,6 +2385,7 @@ static __always_inline int task_mm_cid(struct task_struct *t)
> struct sched_cache_time {
> u64 runtime;
> unsigned long epoch;
> + unsigned long epoch_last_visit;
> };
>
> struct sched_cache_group {
> @@ -2397,6 +2398,7 @@ struct sched_cache_group {
> int cpu;
> refcount_t refcnt;
> struct rcu_head rcu;
> + cpumask_var_t visited_cpus;
> } ____cacheline_aligned_in_smp;
>
> struct sched_cache_group *sched_cache_group_get(struct sched_cache_group *grp);
> diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
> index 79f6b3a4fd7f..c97f08eaa9e5 100644
> --- a/kernel/sched/fair.c
> +++ b/kernel/sched/fair.c
> @@ -1599,11 +1599,11 @@ int mm_init_sched(struct mm_struct *mm,
> int i;
>
> grp = kzalloc_obj(*grp);
> - if (!grp) {
> - free_percpu(_pcpu_sched);
> - mm->sched_cache_grp = NULL;
> - return -ENOMEM;
> - }
> + if (!grp)
> + goto err_free_pcpu;
> +
> + if (!zalloc_cpumask_var(&grp->visited_cpus, GFP_KERNEL))
> + goto err_free_grp;
>
> for_each_possible_cpu(i) {
> struct sched_cache_time *pcpu_sched = per_cpu_ptr(_pcpu_sched, i);
> @@ -1612,6 +1612,7 @@ int mm_init_sched(struct mm_struct *mm,
> pcpu_sched->runtime = 0;
> /* a slightly stale cpu epoch is acceptible */
> pcpu_sched->epoch = rq->cpu_epoch;
> + pcpu_sched->epoch_last_visit = rq->cpu_epoch;
> epoch = rq->cpu_epoch;
> }
>
> @@ -1637,6 +1638,14 @@ int mm_init_sched(struct mm_struct *mm,
> */
> smp_store_release(&mm->sched_cache_grp, grp);
> return 0;
> +
> +err_free_grp:
> + kfree(grp);
> +
> +err_free_pcpu:
> + free_percpu(_pcpu_sched);
> + mm->sched_cache_grp = NULL;
> + return -ENOMEM;
> }
>
> static void sched_cache_group_free_rcu(struct rcu_head *rcu)
> @@ -1645,6 +1654,7 @@ static void sched_cache_group_free_rcu(struct rcu_head *rcu)
> container_of(rcu, struct sched_cache_group, rcu);
>
> free_percpu(grp->pcpu_sched);
> + free_cpumask_var(grp->visited_cpus);
> kfree(grp);
> }
>
> @@ -1785,13 +1795,24 @@ static inline void __update_mm_sched(struct rq *rq,
> }
> }
>
> -static unsigned long fraction_mm_sched(struct rq *rq,
> - struct sched_cache_time *pcpu_sched)
> +static unsigned long fraction_mm_sched(int cpu,
> + struct sched_cache_group *grp)
> {
> + struct sched_cache_time *pcpu_sched =
> + per_cpu_ptr(grp->pcpu_sched, cpu);
> + struct rq *rq = cpu_rq(cpu);
> +
> guard(raw_spinlock_irqsave)(&rq->cpu_epoch_lock);
>
> __update_mm_sched(rq, pcpu_sched);
>
> + /* Evict the CPU if this sched group has not run on it for a while */
> + if ((rq->cpu_epoch - pcpu_sched->epoch_last_visit) >
> + llc_epoch_affinity_timeout) {
> + cpumask_clear_cpu(cpu, grp->visited_cpus);
> + return 0;
> + }
> +
> /*
> * Runtime is a geometric series (r=0.5) and as such will sum to twice
> * the accumulation period, this means the multiplcation here should
> @@ -1867,6 +1888,9 @@ void account_mm_sched(struct rq *rq, struct task_struct *p, s64 delta_exec)
> pcpu_sched->runtime += delta_exec;
> rq->cpu_runtime += delta_exec;
> epoch = rq->cpu_epoch;
> + pcpu_sched->epoch_last_visit = epoch;
> + if (!cpumask_test_cpu(cpu_of(rq), grp->visited_cpus))
> + cpumask_set_cpu(cpu_of(rq), grp->visited_cpus);
> }
>
> /*
> @@ -1917,52 +1941,6 @@ static void task_tick_cache(struct rq *rq, struct task_struct *p)
> }
> }
>
> -static void get_scan_cpumasks(cpumask_var_t cpus, struct task_struct *p,
> - struct sched_cache_group *grp)
> -{
> -#ifdef CONFIG_NUMA_BALANCING
> - int cpu, curr_cpu, nid, pref_nid;
> -
> - if (!static_branch_likely(&sched_numa_balancing))
> - goto out;
> -
> - cpu = READ_ONCE(grp->cpu);
> - if (cpu != -1)
> - nid = cpu_to_node(cpu);
> - curr_cpu = task_cpu(p);
> -
> - /*
> - * Scanning in the preferred NUMA node is ideal. However, the NUMA
> - * preferred node is per-task rather than per-process. It is possible
> - * for different threads of the process to have distinct preferred
> - * nodes; consequently, the process-wide preferred LLC may bounce
> - * between different nodes. As a workaround, maintain the scan
> - * CPU mask to also cover the process's current preferred LLC and the
> - * current running node to mitigate the bouncing risk.
> - * TBD: numa_group should be considered during task aggregation.
> - */
> - pref_nid = p->numa_preferred_nid;
> - /* honor the task's preferred node */
> - if (pref_nid == NUMA_NO_NODE)
> - goto out;
> -
> - cpumask_or(cpus, cpus, cpumask_of_node(pref_nid));
> -
> - /* honor the task's preferred LLC CPU */
> - if (cpu != -1 && !cpumask_test_cpu(cpu, cpus) && nid != NUMA_NO_NODE)
> - cpumask_or(cpus, cpus, cpumask_of_node(nid));
> -
> - /* make sure the task's current running node is included */
> - if (!cpumask_test_cpu(curr_cpu, cpus))
> - cpumask_or(cpus, cpus, cpumask_of_node(cpu_to_node(curr_cpu)));
> -
> - return;
> -
> -out:
> -#endif
> - cpumask_copy(cpus, cpu_online_mask);
> -}
> -
> static inline void update_avg_scale(u64 *avg, u64 sample)
> {
> int factor = per_cpu(sd_llc_size, raw_smp_processor_id());
> @@ -2011,7 +1989,7 @@ static void task_cache_work(struct callback_head *work)
> if (time_before(now, next_scan))
> return;
>
> - /* only 1 thread is allowed to scan */
> + /* elect a single scanner per epoch */
> if (!try_cmpxchg(&grp->next_scan, &next_scan,
> now + max_t(unsigned long,
> READ_ONCE(llc_epoch_period), 1)))
> @@ -2032,7 +2010,13 @@ static void task_cache_work(struct callback_head *work)
> scoped_guard (cpus_read_lock) {
> guard(rcu)();
>
> - get_scan_cpumasks(cpus, p, grp);
> + /*
> + * account_mm_sched() can set a bit in visited_cpus while
> + * it is read here locklessly for efficiency. A CPU missed
> + * this way has only just been used by this sched group,
> + * so its share small, and the next scan will include it.
Nit: so its share is small,
> + */
> + cpumask_and(cpus, cpu_online_mask, grp->visited_cpus);
>
> for_each_cpu(cpu, cpus) {
> /* XXX sched_cluster_active */
> @@ -2043,9 +2027,8 @@ static void task_cache_work(struct callback_head *work)
> if (!sd)
> continue;
>
> - for_each_cpu(i, sched_domain_span(sd)) {
> - occ = fraction_mm_sched(cpu_rq(i),
> - per_cpu_ptr(grp->pcpu_sched, i));
> + for_each_cpu_and(i, sched_domain_span(sd), cpus) {
> + occ = fraction_mm_sched(i, grp);
> a_occ += occ;
> if (occ > m_occ) {
> m_occ = occ;
Otherwise patch looks good to me.
Reviewed-by: Tim Chen <tim.c.chen@xxxxxxxxxxxxxxx>
Tim