From df0d98475954d655571979aa061ecb07d7e00392 Mon Sep 17 00:00:00 2001 From: "Peter Zijlstra (Intel)" Date: Wed, 1 Apr 2026 14:52:13 -0700 Subject: sched/cache: Introduce infrastructure for cache-aware load balancing Adds infrastructure to enable cache-aware load balancing, which improves cache locality by grouping tasks that share resources within the same cache domain. This reduces cache misses and improves overall data access efficiency. In this initial implementation, threads belonging to the same process are treated as entities that likely share working sets. The mechanism tracks per-process CPU occupancy across cache domains and attempts to migrate threads toward cache-hot domains where their process already has active threads, thereby enhancing locality. This provides a basic model for cache affinity. While the current code targets the last-level cache (LLC), the approach could be extended to other domain types such as clusters (L2) or node-internal groupings. At present, the mechanism selects the CPU within an LLC that has the highest recent runtime. Subsequent patches in this series will use this information in the load-balancing path to guide task placement toward preferred LLCs. In the future, more advanced policies could be integrated through NUMA balancing-for example, migrating a task to its preferred LLC when spare capacity exists, or swapping tasks across LLCs to improve cache affinity. Grouping of tasks could also be generalized from that of a process to be that of a NUMA group, or be user configurable. Signed-off-by: Peter Zijlstra (Intel) Signed-off-by: Chen Yu Signed-off-by: Tim Chen Signed-off-by: Peter Zijlstra (Intel) Link: https://patch.msgid.link/6269a53221b9439b9ca00d18a9d1946fb64d8cff.1775065312.git.tim.c.chen@linux.intel.com --- init/Kconfig | 11 +++++++++++ 1 file changed, 11 insertions(+) (limited to 'init') diff --git a/init/Kconfig b/init/Kconfig index 7484cd703bc1..2dfd4744d1d4 100644 --- a/init/Kconfig +++ b/init/Kconfig @@ -1005,6 +1005,17 @@ config NUMA_BALANCING This system will be inactive on UMA systems. +config SCHED_CACHE + bool "Cache aware load balance" + default y + depends on SMP + help + When enabled, the scheduler will attempt to aggregate tasks from + the same process onto a single Last Level Cache (LLC) domain when + possible. This improves cache locality by keeping tasks that share + resources within the same cache domain, reducing cache misses and + lowering data access latency. + config NUMA_BALANCING_DEFAULT_ENABLED bool "Automatically enable NUMA aware memory/task placement" default y -- cgit v1.2.3 From 47d8696b95f7397fe7cad2d194d550ffe82efc15 Mon Sep 17 00:00:00 2001 From: Tim Chen Date: Wed, 1 Apr 2026 14:52:18 -0700 Subject: sched/cache: Assign preferred LLC ID to processes With cache-aware scheduling enabled, each task is assigned a preferred LLC ID. This allows quick identification of the LLC domain where the task prefers to run, similar to numa_preferred_nid in NUMA balancing. Co-developed-by: Chen Yu Signed-off-by: Chen Yu Signed-off-by: Tim Chen Signed-off-by: Peter Zijlstra (Intel) Link: https://patch.msgid.link/f2ceecba5858680349ad4ce9303a2121f0bb7272.1775065312.git.tim.c.chen@linux.intel.com --- include/linux/sched.h | 1 + init/init_task.c | 3 +++ kernel/sched/fair.c | 43 +++++++++++++++++++++++++++++++++++++++++++ 3 files changed, 47 insertions(+) (limited to 'init') diff --git a/include/linux/sched.h b/include/linux/sched.h index 2bf261bcd7b6..d2010483cd77 100644 --- a/include/linux/sched.h +++ b/include/linux/sched.h @@ -1409,6 +1409,7 @@ struct task_struct { #ifdef CONFIG_SCHED_CACHE struct callback_head cache_work; + int preferred_llc; #endif struct rseq_data rseq; diff --git a/init/init_task.c b/init/init_task.c index b5f48ebdc2b6..5d90db4ff1f8 100644 --- a/init/init_task.c +++ b/init/init_task.c @@ -215,6 +215,9 @@ struct task_struct init_task __aligned(L1_CACHE_BYTES) = { .numa_group = NULL, .numa_faults = NULL, #endif +#ifdef CONFIG_SCHED_CACHE + .preferred_llc = -1, +#endif #if defined(CONFIG_KASAN_GENERIC) || defined(CONFIG_KASAN_SW_TAGS) .kasan_depth = 1, #endif diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c index 7860c5bc12d7..6e78ecfb560e 100644 --- a/kernel/sched/fair.c +++ b/kernel/sched/fair.c @@ -1459,11 +1459,43 @@ static unsigned long fraction_mm_sched(struct rq *rq, return div64_u64(NICE_0_LOAD * pcpu_sched->runtime, rq->cpu_runtime + 1); } +static int get_pref_llc(struct task_struct *p, struct mm_struct *mm) +{ + int mm_sched_llc = -1; + + if (!mm) + return -1; + + if (mm->sc_stat.cpu != -1) { + mm_sched_llc = llc_id(mm->sc_stat.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->sc_stat.cpu) != p->numa_preferred_nid) + mm_sched_llc = -1; +#endif + } + + return mm_sched_llc; +} + static inline 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; + int mm_sched_llc = -1; unsigned long epoch; if (!sched_cache_enabled()) @@ -1495,6 +1527,11 @@ void account_mm_sched(struct rq *rq, struct task_struct *p, s64 delta_exec) if (mm->sc_stat.cpu != -1) mm->sc_stat.cpu = -1; } + + mm_sched_llc = get_pref_llc(p, mm); + + if (READ_ONCE(p->preferred_llc) != mm_sched_llc) + WRITE_ONCE(p->preferred_llc, mm_sched_llc); } static void task_tick_cache(struct rq *rq, struct task_struct *p) @@ -1671,6 +1708,12 @@ void init_sched_mm(struct task_struct *p) { } static void task_tick_cache(struct rq *rq, struct task_struct *p) { } +static inline int get_pref_llc(struct task_struct *p, + struct mm_struct *mm) +{ + return -1; +} + #endif /* CONFIG_SCHED_CACHE */ /* -- cgit v1.2.3 From 03755348b8e74421f92ffed9da159175a698290b Mon Sep 17 00:00:00 2001 From: Chen Yu Date: Wed, 13 May 2026 13:39:21 -0700 Subject: sched/cache: Fix unpaired account_llc_enqueue/dequeue There is a race condition that, after a task is enqueued on a runqueue, task_llc(p) may change due to CPU hotplug, because the llc_id is dynamically allocated and adjusted at runtime. Therefore, checking task_llc(p) to determine whether the task is being dequeued from its preferred LLC is unreliable and can cause inconsistent values. To fix this problem, record whether p is enqueued on its preferred LLC, in order to pair with account_llc_dequeue() to maintain a consistent nr_pref_llc_running per runqueue. This bug was reported by sashiko, and the solution was once suggested by Prateek. Fixes: 46afe3af7ead ("sched/cache: Track LLC-preferred tasks per runqueue") Suggested-by: K Prateek Nayak Signed-off-by: Chen Yu Co-developed-by: Tim Chen Signed-off-by: Tim Chen Signed-off-by: Peter Zijlstra (Intel) Link: https://patch.msgid.link/0c8c6a1571d66792a4d2ff0103ba3cc13e059046.1778703694.git.tim.c.chen@linux.intel.com --- include/linux/sched.h | 2 ++ init/init_task.c | 1 + kernel/sched/fair.c | 31 ++++++++++++++++++++++++++++--- 3 files changed, 31 insertions(+), 3 deletions(-) (limited to 'init') diff --git a/include/linux/sched.h b/include/linux/sched.h index 95729670929c..2c9e8e2edde1 100644 --- a/include/linux/sched.h +++ b/include/linux/sched.h @@ -1410,6 +1410,8 @@ struct task_struct { #ifdef CONFIG_SCHED_CACHE struct callback_head cache_work; int preferred_llc; + /* 1: task was enqueued to its preferred LLC, 0 otherwise */ + int pref_llc_queued; #endif struct rseq_data rseq; diff --git a/init/init_task.c b/init/init_task.c index 5d90db4ff1f8..3ecd66fbd563 100644 --- a/init/init_task.c +++ b/init/init_task.c @@ -217,6 +217,7 @@ struct task_struct init_task __aligned(L1_CACHE_BYTES) = { #endif #ifdef CONFIG_SCHED_CACHE .preferred_llc = -1, + .pref_llc_queued = 0, #endif #if defined(CONFIG_KASAN_GENERIC) || defined(CONFIG_KASAN_SW_TAGS) .kasan_depth = 1, diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c index 087445ea6bc9..96c61ce366c2 100644 --- a/kernel/sched/fair.c +++ b/kernel/sched/fair.c @@ -1472,15 +1472,32 @@ static bool invalid_llc_nr(struct mm_struct *mm, struct task_struct *p, static void account_llc_enqueue(struct rq *rq, struct task_struct *p) { + int pref_llc, pref_llc_queued; struct sched_domain *sd; - int pref_llc; pref_llc = p->preferred_llc; if (pref_llc < 0) return; + pref_llc_queued = (pref_llc == task_llc(p)); rq->nr_llc_running++; - rq->nr_pref_llc_running += (pref_llc == task_llc(p)); + rq->nr_pref_llc_running += pref_llc_queued; + + /* + * Record whether p is enqueued on its preferred + * LLC, in order to pair with account_llc_dequeue() + * to maintain a consistent nr_pref_llc_running per + * runqueue. + * This is necessary because a race condition exists: + * after a task is enqueued on a runqueue, task_llc(p) + * may change due to CPU hotplug. Therefore, checking + * task_llc(p) to determine whether the task is being + * dequeued from its preferred LLC is unreliable and + * can cause inconsistent values - checking the + * p->pref_llc_queued in account_llc_dequeue() would + * be reliable. + */ + p->pref_llc_queued = pref_llc_queued; sd = rcu_dereference_all(rq->sd); if (sd && (unsigned int)pref_llc < sd->llc_max) @@ -1497,7 +1514,15 @@ static void account_llc_dequeue(struct rq *rq, struct task_struct *p) return; rq->nr_llc_running--; - rq->nr_pref_llc_running -= (pref_llc == task_llc(p)); + if (p->pref_llc_queued) { + rq->nr_pref_llc_running--; + /* + * Update the status in case + * other logic might query + * this. + */ + p->pref_llc_queued = 0; + } sd = rcu_dereference_all(rq->sd); if (sd && (unsigned int)pref_llc < sd->llc_max) { -- cgit v1.2.3 From 1628b25248d0742b2ce9c7cfa59cd183e35f37e1 Mon Sep 17 00:00:00 2001 From: Peter Zijlstra Date: Tue, 12 May 2026 02:56:17 +0000 Subject: sched: Add blocked_donor link to task for smarter mutex handoffs Add link to the task this task is proxying for, and use it so the mutex owner can do an intelligent hand-off of the mutex to the task that the owner is running on behalf. [jstultz: This patch was split out from larger proxy patch] Signed-off-by: Peter Zijlstra (Intel) Signed-off-by: Juri Lelli Signed-off-by: Valentin Schneider Signed-off-by: Connor O'Brien Signed-off-by: John Stultz Signed-off-by: Peter Zijlstra (Intel) Link: https://patch.msgid.link/20260512025635.2840817-8-jstultz@google.com --- include/linux/sched.h | 7 ++++++ init/init_task.c | 1 + kernel/fork.c | 1 + kernel/locking/mutex.c | 60 ++++++++++++++++++++++++++++++++++++++++++++------ kernel/sched/core.c | 14 +++++++++++- 5 files changed, 75 insertions(+), 8 deletions(-) (limited to 'init') diff --git a/include/linux/sched.h b/include/linux/sched.h index ec170663f99b..e2f127a7ca0d 100644 --- a/include/linux/sched.h +++ b/include/linux/sched.h @@ -1250,6 +1250,13 @@ struct task_struct { struct mutex *blocked_on; /* lock we're blocked on */ raw_spinlock_t blocked_lock; + /* + * The task that is boosting this task; a back link for the current + * donor stack. Set in schedule() -> find_proxy_task() and only stable + * under preempt_disable(). + */ + struct task_struct *blocked_donor; + #ifdef CONFIG_DETECT_HUNG_TASK_BLOCKER /* * Encoded lock address causing task block (lower 2 bits = type from diff --git a/init/init_task.c b/init/init_task.c index 3ecd66fbd563..674d174e2e6a 100644 --- a/init/init_task.c +++ b/init/init_task.c @@ -200,6 +200,7 @@ struct task_struct init_task __aligned(L1_CACHE_BYTES) = { .mems_allowed_seq = SEQCNT_SPINLOCK_ZERO(init_task.mems_allowed_seq, &init_task.alloc_lock), #endif + .blocked_donor = NULL, #ifdef CONFIG_RT_MUTEXES .pi_waiters = RB_ROOT_CACHED, .pi_top_task = NULL, diff --git a/kernel/fork.c b/kernel/fork.c index a679b2448234..6fcca1db0af3 100644 --- a/kernel/fork.c +++ b/kernel/fork.c @@ -2224,6 +2224,7 @@ __latent_entropy struct task_struct *copy_process( lockdep_init_task(p); p->blocked_on = NULL; /* not blocked yet */ + p->blocked_donor = NULL; /* nobody is boosting p yet */ #ifdef CONFIG_BCACHE p->sequential_io = 0; diff --git a/kernel/locking/mutex.c b/kernel/locking/mutex.c index a93d4c6bee1a..28677165785f 100644 --- a/kernel/locking/mutex.c +++ b/kernel/locking/mutex.c @@ -981,15 +981,22 @@ EXPORT_SYMBOL_GPL(ww_mutex_lock_interruptible); static noinline void __sched __mutex_unlock_slowpath(struct mutex *lock, unsigned long ip) __releases(lock) { - struct task_struct *next = NULL; + struct task_struct *donor, *next = NULL; struct mutex_waiter *waiter; - DEFINE_WAKE_Q(wake_q); unsigned long owner; unsigned long flags; mutex_release(&lock->dep_map, ip); __release(lock); + /* + * Ensures the proxy donor stack is stable across unlock and handoff. + * Specifically, it avoids the case where current->blocked_donor is + * NULL when it is inspected while doing the unlock, but a preemption + * before taking the wake_lock would make it set and a hand-off is + * missed. + */ + guard(preempt)(); /* * Release the lock before (potentially) taking the spinlock such that * other contenders can get on with things ASAP. @@ -1002,6 +1009,12 @@ static noinline void __sched __mutex_unlock_slowpath(struct mutex *lock, unsigne MUTEX_WARN_ON(__owner_task(owner) != current); MUTEX_WARN_ON(owner & MUTEX_FLAG_PICKUP); + if (sched_proxy_exec() && current->blocked_donor) { + /* force handoff if we have a blocked_donor */ + owner = MUTEX_FLAG_HANDOFF; + break; + } + if (owner & MUTEX_FLAG_HANDOFF) break; @@ -1014,20 +1027,53 @@ static noinline void __sched __mutex_unlock_slowpath(struct mutex *lock, unsigne } raw_spin_lock_irqsave(&lock->wait_lock, flags); + raw_spin_lock(¤t->blocked_lock); debug_mutex_unlock(lock); + + if (sched_proxy_exec()) { + /* + * If we have a task boosting current, and that task was boosting + * current through this lock, hand the lock to that task, as that + * is the highest waiter, as selected by the scheduling function. + */ + donor = current->blocked_donor; + if (donor) { + struct mutex *next_lock; + + raw_spin_lock_nested(&donor->blocked_lock, SINGLE_DEPTH_NESTING); + next_lock = __get_task_blocked_on(donor); + if (next_lock == lock) { + next = get_task_struct(donor); + __set_task_blocked_on_waking(donor, next_lock); + current->blocked_donor = NULL; + } + raw_spin_unlock(&donor->blocked_lock); + } + } + + /* + * Failing that, pick first on the wait list. + */ waiter = lock->first_waiter; - if (waiter) { - next = waiter->task; + if (!next && waiter) { + next = get_task_struct(waiter->task); + raw_spin_lock_nested(&next->blocked_lock, SINGLE_DEPTH_NESTING); debug_mutex_wake_waiter(lock, waiter); - set_task_blocked_on_waking(next, lock); - wake_q_add(&wake_q, next); + __set_task_blocked_on_waking(next, lock); + raw_spin_unlock(&next->blocked_lock); + } if (owner & MUTEX_FLAG_HANDOFF) __mutex_handoff(lock, next); - raw_spin_unlock_irqrestore_wake(&lock->wait_lock, flags, &wake_q); + raw_spin_unlock(¤t->blocked_lock); + raw_spin_unlock_irqrestore(&lock->wait_lock, flags); + if (next) { + wake_up_process(next); + put_task_struct(next); + } } #ifndef CONFIG_DEBUG_LOCK_ALLOC diff --git a/kernel/sched/core.c b/kernel/sched/core.c index c7552869d5c4..4c6ceff3855e 100644 --- a/kernel/sched/core.c +++ b/kernel/sched/core.c @@ -6827,7 +6827,17 @@ static void proxy_migrate_task(struct rq *rq, struct rq_flags *rf, * Find runnable lock owner to proxy for mutex blocked donor * * Follow the blocked-on relation: - * task->blocked_on -> mutex->owner -> task... + * + * ,-> task + * | | blocked-on + * | v + * blocked_donor | mutex + * | | owner + * | v + * `-- task + * + * and set the blocked_donor relation, this latter is used by the mutex + * code to find which (blocked) task to hand-off to. * * Lock order: * @@ -6969,6 +6979,7 @@ find_proxy_task(struct rq *rq, struct task_struct *donor, struct rq_flags *rf) * rq, therefore holding @rq->lock is sufficient to * guarantee its existence, as per ttwu_remote(). */ + owner->blocked_donor = p; } WARN_ON_ONCE(owner && !owner->on_rq); return owner; @@ -7125,6 +7136,7 @@ pick_again: clear_task_blocked_on(prev, NULL); rq_set_donor(rq, next); + next->blocked_donor = NULL; if (unlikely(next->is_blocked && next->blocked_on)) { next = find_proxy_task(rq, next, &rf); if (!next) { -- cgit v1.2.3