[PATCH v33 0/7] Sleeping Owner Handling for Proxy Execution (v33)

[PATCH v33 0/7] Sleeping Owner Handling for Proxy Execution (v33)

[John Stultz]

Hey All,
  Just wanted to send out this next iteration of Proxy
Execution: Sleeping Owner Handling.

As always, I’m trying to submit this larger work in smallish
digestible pieces. A quick overview of the journey so far:
 1) Prep patches
 2) Single rq proxying
 3) Simple donor migration
 4) Optimized donor migration
 5) Sleeping owner handling  <---- We are here!
 6) K Prateek’s core-sched fixes
 7) Connor's chain level balancing
 8) Suleiman’s proxy rwsems
 9) Suleiman’s proxy futexes
10) ...

The main feature in this series is the sleeping owner handling
patch, which addresses what to do when a task is blocked on a
mutex whose owner is sleeping. Since there is nothing we can do
to boost the sleeping owner at that point, we instead deactivate
and queue the waiter on a list attached to the owner. Then when
the owner wakes up, we will activate the waiters on the same
runqueue, so they can then boost the owner to run.

But since the simple sounding things hide subtlety, this ends up
being a pretty complex bit of logic. You can effectively get
trees of waiters, and it's possible to have tasks in the middle
of the tree be woken up. Then handling wakeups as they cascade
down the tree properly is also a bit complex, as there are extra
lists to manage the recursive style work without actually
recursing.

K Prateek sent an interesting alternative approach:
  https://lore.kernel.org/lkml/20260826062901.2137-1-kprateek.nayak@amd.com/

But after talking with Peter on this at LPC, we agreed to start
with the “relatively simpler”(ha!) approach first, and then take
a later swing at using K Prateek’s approach to optimize it.

In this series (against linus' HEAD) I’ve also aggregated fixes
from K Prateek, Shubhang Kaushik, as well as included some
initial proxy-chain cycle detection logic combining parallel
efforts from Zhidao Su and Hui Su. Additionally there have been
issues fixed in the sleeping-owner-enqueuing change, reported
by David Stevens as well as other partners.

Thank you to everyone for contributing bug reports, fixes and
improvements! I really appreciate it!

New in v32 of this set:
 * Fixes to PSI flag handling logic that proxy-exec could break.

 * Fix from Shubhang to use rq->donor for sched_tick_remote().

 * Extended K Prateek’s optimization to activate on NULL owner
   to do the same for null mutex/blocked_on.

 * Fix to set TASK_RUNNING when we shortcut return-migration to
   immediately run a task.

 * Fixed chain depth limit for find_proxy_task() to avoid
   deadlocks if there were a lock cycle, from Zhidao Su.

 * Further chain cycle-detection logic, using Brent’s algorithm
   to catch cycles faster from Hui Su.

 * Additional fixes to activate_blocked_waiters() to avoid PSI
   state problems

 * Fix for a potential crasher caused when the call to
   do_activate_blocked_waiter() is significantly delayed, which
   could cause proxy activations to the previous owner’s cpu,
   even if the task had been otherwise woken and then went back
   to sleep - potentially allowing execution outside of the smp
   affinity mask.

Additionally I’d appreciate any testing or comments that folks
have with the full Proxy Execution series! You can find the full
Proxy Exec series here:
  https://github.com/johnstultz-work/linux-dev/commits/proxy-exec-v33-7.4-pre-rc1/
  https://github.com/johnstultz-work/linux-dev.git proxy-exec-v33-7.4-pre-rc1

New changes to the full patch series in this revision include:
 * Small fix for Suleiman’s FUTEX_LOCK_PING logic

Issues still to address with the full series:
 * Address and integrate feedback from v1 RFC of Proxy enabled
   futexes

 * Maria Yu raised a subtle difference in how the nr_iowait
   counting might be attributed with proxy-exec: potentially
   proxy-migrated donors that become blocked on sleeping owners
   could increment/decrement the value on the owners cpu rq,
   instead of on the donor’s original cpu rq. It’s unclear to
   me what the impact of this would be, if at all, but it is
   potentially an observable difference with proxy-exec, so
   I’m going to take a swing at addressing it.

 * Reevaluate performance regression K Prateek Nayak found with
   the full series earlier.

 * The chain migration functionality needs further iterations
   and better validation to ensure it truly maintains the RT/DL
   load balancing invariants (despite this being broken in
   vanilla upstream with RT_PUSH_IPI currently)

Future work:
 * Expand to more locking primitives: Binder PI is something
   else we’re exploring.

 * Eventually: Work to replace rt_mutexes and get things happy
   with PREEMPT_RT


Credit/Disclaimer:
—--------------------
As always, this Proxy Execution series has a long history with
lots of developers that deserve credit: 

First described in a paper[1] by Watkins, Straub, Niehaus, then
from patches from Peter Zijlstra, extended with lots of work by
Juri Lelli, Valentin Schneider, and Connor O'Brien. (and thank
you to Steven Rostedt for providing additional details here!).
Thanks also to Joel Fernandes, Dietmar Eggemann, Metin Kaya,
K Prateek Nayak, Suleiman Souhlal, Christian Loehle, and
Andrea Righi for their substantial review, suggestion, and patch
contributions.

So again, many thanks to those above, as all the credit for this
series really is due to them - while the mistakes are surely mine.

Thanks so much!
-john

[1] https://static.lwn.net/images/conf/rtlws11/papers/proc/p38.pdf

Cc: Peter Zijlstra <peterz@infradead.org>
Cc: Ingo Molnar <mingo@redhat.com>
Cc: K Prateek Nayak <kprateek.nayak@amd.com>
Cc: Thomas Gleixner <tglx@linutronix.de>
Cc: Juri Lelli <juri.lelli@redhat.com>
Cc: Vincent Guittot <vincent.guittot@linaro.org>
Cc: Valentin Schneider <vschneid@redhat.com>
Cc: Suleiman Souhlal <suleiman@google.com>
Cc: Andrea Righi <arighi@nvidia.com>
Cc: Metin Kaya <Metin.Kaya@arm.com>
Cc: Dietmar Eggemann <dietmar.eggemann@arm.com>
Cc: Steven Rostedt <rostedt@goodmis.org>
Cc: Zimuzo Ezeozue <zezeozue@google.com>
Cc: Waiman Long <longman@redhat.com>
Cc: Boqun Feng <boqun.feng@gmail.com>
Cc: "Paul E. McKenney" <paulmck@kernel.org>
Cc: Joel Fernandes <joelagnelf@nvidia.com>
Cc: Qais Yousef <qyousef@layalina.io>
Cc: Xuewen Yan <xuewen.yan94@gmail.com>
Cc: kuyo chang <kuyo.chang@mediatek.com>
Cc: hupu <hupu.gm@gmail.com>
Cc: Zhan Xusheng <zhanxusheng@xiaomi.com>
Cc: zhidao su (Xiaomi) <soolaugust@gmail.com>
Cc: Hui Su <sh_def@163.com>
Cc: Shubhang Kaushik (Ampere) <sh@gentwo.org>
Cc: kernel-team@android.com


Hui Su (1):
  sched/proxy: Detect cycles in proxy walks earlier

John Stultz (2):
  sched/psi: Preserve sleep-persistent PSI flags on off-CPU sleeping
    dequeues
  sched/proxy: Set TASK_RUNNING when shortcuting return migration

K Prateek Nayak (1):
  sched/core: Activate blocked donor when no owner is found

Peter Zijlstra (1):
  sched/proxy: Add deactivated (sleeping) owner handling to
    find_proxy_task()

Shubhang Kaushik (Ampere) (1):
  sched/core: Use the scheduling context for remote ticks

zhidao su (Xiaomi) (1):
  sched/proxy: Break cyclic proxy chains by deactivating blocked tasks

 include/linux/sched.h      |   7 +
 include/linux/sched/task.h |   1 +
 init/init_task.c           |   6 +
 kernel/fork.c              |   6 +
 kernel/sched/core.c        | 404 +++++++++++++++++++++++++++++++++----
 kernel/sched/stats.h       |  24 ++-
 6 files changed, 407 insertions(+), 41 deletions(-)

-- 
2.56.0.257.gf7497c7d27-goog

[PATCH v33 1/7] sched/psi: Preserve sleep-persistent PSI flags on off-CPU sleeping dequeues

[John Stultz]

Normally, when a task goes to sleep (DEQUEUE_SLEEP),
psi_dequeue() does nothing because psi_sched_switch() ->
psi_task_switch() immediately follows and handles the
runnable-to-sleeping PSI transition (clearing TSK_ONCPU,
TSK_RUNNING, and TSK_MEMSTALL_RUNNING, setting TSK_IOWAIT, and
leaving sleep-persistent TSK_MEMSTALL set).

With Proxy Execution, mutex-blocked tasks stay on the runqueue
across context switches, so psi_sched_switch() runs with
sleep=false and only clears TSK_ONCPU. If the blocked donor task
is later deactivated via block_task(), psi_dequeue() is called
with DEQUEUE_SLEEP while TSK_ONCPU is already cleared.

Commit c2ae8b0df2d1 ("sched/core: Fix psi_dequeue() for Proxy
Execution") checked for (flags & DEQUEUE_SLEEP) && (p->psi_flags
& TSK_ONCPU), falling through to
psi_task_change(p, p->psi_flags, 0) when TSK_ONCPU was not set.
However, clearing all of p->psi_flags treats the sleeping
dequeue as a migration and wipes sleep-persistent flags like
TSK_MEMSTALL (and fails to set TSK_IOWAIT).

When the task later wakes up on the same cpu without
ENQUEUE_MIGRATED, psi_enqueue() assumes TSK_MEMSTALL is still
set from when the task went to sleep and only sets TSK_RUNNING |
TSK_MEMSTALL_RUNNING. This leaves things in an inconsistent
state (TSK_MEMSTALL_RUNNING set without TSK_MEMSTALL), causing
psi.mem.full to exceed psi.mem.some, delta underflows in
get_recent_times(), and spurious psi.mem.full events.

So fix psi_dequeue() such that when DEQUEUE_SLEEP is set and
TSK_ONCPU is not set, we do the same runnable-to-sleeping flag
transition as psi_task_switch() (clearing TSK_RUNNING and
TSK_MEMSTALL_RUNNING, setting TSK_IOWAIT, and preserving
TSK_MEMSTALL).

Fixes: c2ae8b0df2d1 ("sched/core: Fix psi_dequeue() for Proxy Execution")
Reported-by: David Stevens <stevensd@google.com>
Signed-off-by: John Stultz <jstultz@google.com>
---
Cc: Peter Zijlstra <peterz@infradead.org>
Cc: Ingo Molnar <mingo@redhat.com>
Cc: K Prateek Nayak <kprateek.nayak@amd.com>
Cc: Thomas Gleixner <tglx@linutronix.de>
Cc: Juri Lelli <juri.lelli@redhat.com>
Cc: Vincent Guittot <vincent.guittot@linaro.org>
Cc: Valentin Schneider <vschneid@redhat.com>
Cc: Suleiman Souhlal <suleiman@google.com>
Cc: Andrea Righi <arighi@nvidia.com>
Cc: Metin Kaya <Metin.Kaya@arm.com>
Cc: Dietmar Eggemann <dietmar.eggemann@arm.com>
Cc: Steven Rostedt <rostedt@goodmis.org>
Cc: Zimuzo Ezeozue <zezeozue@google.com>
Cc: Waiman Long <longman@redhat.com>
Cc: Boqun Feng <boqun.feng@gmail.com>
Cc: "Paul E. McKenney" <paulmck@kernel.org>
Cc: Joel Fernandes <joelagnelf@nvidia.com>
Cc: Qais Yousef <qyousef@layalina.io>
Cc: Xuewen Yan <xuewen.yan94@gmail.com>
Cc: kuyo chang <kuyo.chang@mediatek.com>
Cc: hupu <hupu.gm@gmail.com>
Cc: Zhan Xusheng <zhanxusheng@xiaomi.com>
Cc: zhidao su (Xiaomi) <soolaugust@gmail.com>
Cc: Hui Su <sh_def@163.com>
Cc: Shubhang Kaushik (Ampere) <sh@gentwo.org>
Cc: kernel-team@android.com
---
 kernel/sched/stats.h | 24 ++++++++++++++++++++----
 1 file changed, 20 insertions(+), 4 deletions(-)

diff --git a/kernel/sched/stats.h b/kernel/sched/stats.h
index ebe0a7765f98e..20820fe1021a1 100644
--- a/kernel/sched/stats.h
+++ b/kernel/sched/stats.h
@@ -175,12 +175,28 @@ static inline void psi_dequeue(struct task_struct *p, int flags)
 	 * Do nothing here.
 	 *
 	 * In the SCHED_PROXY_EXECUTION case we may do sleeping
-	 * dequeues that are not followed by a task switch, so check
-	 * TSK_ONCPU is set to ensure the task switch is imminent.
-	 * Otherwise clear the flags as usual.
+	 * dequeues that are not followed by a task switch. If TSK_ONCPU
+	 * is not set (meaning we already switched away while the task
+	 * stayed on the rq as a blocked donor), handle the sleeping
+	 * state transition here so sleep-persistent states (TSK_MEMSTALL,
+	 * TSK_IOWAIT) are preserved.
 	 */
-	if ((flags & DEQUEUE_SLEEP) && (p->psi_flags & TSK_ONCPU))
+	if (flags & DEQUEUE_SLEEP) {
+		int clear = TSK_RUNNING, set = 0;
+
+		if (p->psi_flags & TSK_ONCPU)
+			return;
+		if (p->se.sched_delayed)
+			return;
+
+		if (p->in_memstall)
+			clear |= TSK_MEMSTALL_RUNNING;
+		if (p->in_iowait)
+			set |= TSK_IOWAIT;
+
+		psi_task_change(p, clear, set);
 		return;
+	}
 
 	/*
 	 * When migrating a task to another CPU, clear all psi
-- 
2.56.0.257.gf7497c7d27-goog

[PATCH v33 2/7] sched/core: Use the scheduling context for remote ticks

[John Stultz]

From: "Shubhang Kaushik (Ampere)" <sh@gentwo.org>

sched_tick_remote() assumes that a CPU in full dynticks mode has only
one running task. It therefore assumes that proxy execution cannot be
active and that rq->curr == rq->donor.

However, sched_can_stop_tick() can stop the tick with multiple tasks on
the runqueue. With exactly one SCHED_RR task, the tick is not needed for
round-robin timeslice rotation. When there are no SCHED_RR tasks,
SCHED_FIFO tasks do not require the tick because they have no forced
tick preemption. Lower scheduling-class tasks can still be queued in
both cases.

Consequently, a SCHED_FIFO task blocked on a SCHED_NORMAL mutex owner
can remain rq->donor while find_proxy_task() selects the owner to
execute as rq->curr. sched_tick_remote() can therefore run with
rq->curr != rq->donor.

The full-nohz state check in sched_tick_remote() is intentionally racy
and can allow an extra or missed remote tick. This issue does not rely
on that race: the tick can be legitimately stopped in the cases above.

Use rq->donor for the remote class tick and its full-nohz tick-interval
sanity check, matching sched_tick() and hrtick().

Fixes: 7de9d4f94638 ("sched: Start blocked_on chain processing in find_proxy_task()")
Signed-off-by: Shubhang Kaushik (Ampere) <sh@gentwo.org>
Signed-off-by: John Stultz <jstultz@google.com>
---
Cc: Peter Zijlstra <peterz@infradead.org>
Cc: Ingo Molnar <mingo@redhat.com>
Cc: K Prateek Nayak <kprateek.nayak@amd.com>
Cc: Thomas Gleixner <tglx@linutronix.de>
Cc: Juri Lelli <juri.lelli@redhat.com>
Cc: Vincent Guittot <vincent.guittot@linaro.org>
Cc: Valentin Schneider <vschneid@redhat.com>
Cc: Suleiman Souhlal <suleiman@google.com>
Cc: Andrea Righi <arighi@nvidia.com>
Cc: Metin Kaya <Metin.Kaya@arm.com>
Cc: Dietmar Eggemann <dietmar.eggemann@arm.com>
Cc: Steven Rostedt <rostedt@goodmis.org>
Cc: Zimuzo Ezeozue <zezeozue@google.com>
Cc: Waiman Long <longman@redhat.com>
Cc: Boqun Feng <boqun.feng@gmail.com>
Cc: "Paul E. McKenney" <paulmck@kernel.org>
Cc: Joel Fernandes <joelagnelf@nvidia.com>
Cc: Qais Yousef <qyousef@layalina.io>
Cc: Xuewen Yan <xuewen.yan94@gmail.com>
Cc: kuyo chang <kuyo.chang@mediatek.com>
Cc: hupu <hupu.gm@gmail.com>
Cc: Zhan Xusheng <zhanxusheng@xiaomi.com>
Cc: zhidao su (Xiaomi) <soolaugust@gmail.com>
Cc: Hui Su <sh_def@163.com>
Cc: Shubhang Kaushik (Ampere) <sh@gentwo.org>
Cc: kernel-team@android.com
---
 kernel/sched/core.c | 14 ++++----------
 1 file changed, 4 insertions(+), 10 deletions(-)

diff --git a/kernel/sched/core.c b/kernel/sched/core.c
index 0ab15f03cb947..729ebaca35e1a 100644
--- a/kernel/sched/core.c
+++ b/kernel/sched/core.c
@@ -5934,26 +5934,20 @@ static void sched_tick_remote(struct work_struct *work)
 	 */
 	if (tick_nohz_tick_stopped_cpu(cpu)) {
 		guard(rq_lock_irq)(rq);
-		struct task_struct *curr = rq->curr;
+		struct task_struct *donor = rq->donor;
 
 		if (cpu_online(cpu)) {
-			/*
-			 * Since this is a remote tick for full dynticks mode,
-			 * we are always sure that there is no proxy (only a
-			 * single task is running).
-			 */
-			WARN_ON_ONCE(rq->curr != rq->donor);
 			update_rq_clock(rq);
 
-			if (!is_idle_task(curr)) {
+			if (!is_idle_task(donor)) {
 				/*
 				 * Make sure the next tick runs within a
 				 * reasonable amount of time.
 				 */
-				u64 delta = rq_clock_task(rq) - curr->se.exec_start;
+				u64 delta = rq_clock_task(rq) - donor->se.exec_start;
 				WARN_ON_ONCE(delta > (u64)NSEC_PER_SEC * 30);
 			}
-			curr->sched_class->task_tick(rq, curr, 0);
+			donor->sched_class->task_tick(rq, donor, 0);
 
 			calc_load_nohz_remote(rq);
 		}
-- 
2.56.0.257.gf7497c7d27-goog

[PATCH v33 3/7] sched/core: Activate blocked donor when no owner is found

[John Stultz]

From: K Prateek Nayak <kprateek.nayak@amd.com>

mutex_unlock_slowpath() follows:

    if (owner & MUTEX_FLAG_HANDOFF)
        break /* ... and do __mutex_handoff() */

    if (atomic_long_try_cmpxchg_release(&lock->owner, &owner, __owner_flags(owner))) {
        if (owner & MUTEX_FLAG_WAITERS)
            break; /* ... and wake up the forst waiter. */

MUTEX_FLAG_HANDOFF is only set by first-waiter after it has been woken
up and in absence of MUTEX_FLAG_HANDOFF, the owner clears itself from
the lock_word and wakes up the first waiter to try a
__mutex_trylock_or_handoff().

MUTEX_FLAG_HANDOFF exists to prevent new optimistic spinners from
trying to hijack the lock from waiter all the time and potentially
starving them but it is not necessary for MUTEX_FLAG_HANDOFF to be
always set in presence of a waiter.

If a blocked donor is deactivated when no owner is observed, it may not
be woken up until it becomes the first waiter and is naturally woken up
which breaks proxy in the interim.

Wake up the blocked donor and allow it to grab the lock when no owner is
observed. If the task manages to grab the lock, the block chain will
follow at the next proxy migration. If the task fails to grab the lock,
same situation is restored and everyone migrated to the CPU of new
owner.

Similarly, do the same for the NULL blocked_on/mutex pointer for
consistency.

Fixes: f13beb010e4a ("sched: Have try_to_wake_up() handle return-migration for PROXY_WAKING case")
Signed-off-by: K Prateek Nayak <kprateek.nayak@amd.com>
Signed-off-by: John Stultz <jstultz@google.com>
---
v33:
* Added similar logic for the null mutex/blocked_on case

Cc: Peter Zijlstra <peterz@infradead.org>
Cc: Ingo Molnar <mingo@redhat.com>
Cc: K Prateek Nayak <kprateek.nayak@amd.com>
Cc: Thomas Gleixner <tglx@linutronix.de>
Cc: Juri Lelli <juri.lelli@redhat.com>
Cc: Vincent Guittot <vincent.guittot@linaro.org>
Cc: Valentin Schneider <vschneid@redhat.com>
Cc: Suleiman Souhlal <suleiman@google.com>
Cc: Andrea Righi <arighi@nvidia.com>
Cc: Metin Kaya <Metin.Kaya@arm.com>
Cc: Dietmar Eggemann <dietmar.eggemann@arm.com>
Cc: Steven Rostedt <rostedt@goodmis.org>
Cc: Zimuzo Ezeozue <zezeozue@google.com>
Cc: Waiman Long <longman@redhat.com>
Cc: Boqun Feng <boqun.feng@gmail.com>
Cc: "Paul E. McKenney" <paulmck@kernel.org>
Cc: Joel Fernandes <joelagnelf@nvidia.com>
Cc: Qais Yousef <qyousef@layalina.io>
Cc: Xuewen Yan <xuewen.yan94@gmail.com>
Cc: kuyo chang <kuyo.chang@mediatek.com>
Cc: hupu <hupu.gm@gmail.com>
Cc: Zhan Xusheng <zhanxusheng@xiaomi.com>
Cc: zhidao su (Xiaomi) <soolaugust@gmail.com>
Cc: Hui Su <sh_def@163.com>
Cc: Shubhang Kaushik (Ampere) <sh@gentwo.org>
Cc: kernel-team@android.com
---
 kernel/sched/core.c | 27 ++++++++++++++++++++++-----
 1 file changed, 22 insertions(+), 5 deletions(-)

diff --git a/kernel/sched/core.c b/kernel/sched/core.c
index 729ebaca35e1a..2cb42de255f7a 100644
--- a/kernel/sched/core.c
+++ b/kernel/sched/core.c
@@ -6921,6 +6921,19 @@ static inline void proxy_reacquire_rq_lock(struct rq *rq, struct rq_flags *rf)
 	update_rq_clock(rq);
 }
 
+static void
+proxy_activate(struct rq *rq, struct rq_flags *rf, struct task_struct *p)
+	__must_hold(__rq_lockp(rq))
+{
+	lockdep_assert_rq_held(rq);
+	proxy_resched_idle(rq);
+	proxy_release_rq_lock(rq, rf);
+
+	wake_up_process(p);
+
+	proxy_reacquire_rq_lock(rq, rf);
+}
+
 /*
  * If the blocked-on relationship crosses CPUs, migrate @p to the
  * owner's CPU.
@@ -7013,11 +7026,11 @@ find_proxy_task(struct rq *rq, struct task_struct *donor, struct rq_flags *rf)
 		struct mutex *mutex = p->blocked_on;
 		if (!mutex) {
 			clear_task_blocked_on(p, mutex);
-			if (task_current(rq, p)) {
+			if (task_current(rq, p) || p->wake_cpu == task_cpu(p)) {
 				p->is_blocked = 0;
 				return p;
 			}
-			goto deactivate;
+			goto activate;
 		}
 
 		/*
@@ -7046,14 +7059,15 @@ find_proxy_task(struct rq *rq, struct task_struct *donor, struct rq_flags *rf)
 			/*
 			 * If there is no owner, either clear blocked_on
 			 * and return p (if it is current and safe to
-			 * just run on this rq), or return-migrate the task.
+			 * just run on this rq), or wake the task to try
+			 * and grab the lock it is blocked on.
 			 */
 			__clear_task_blocked_on(p, NULL);
-			if (task_current(rq, p)) {
+			if (task_current(rq, p) || p->wake_cpu == task_cpu(p)) {
 				p->is_blocked = 0;
 				return p;
 			}
-			goto deactivate;
+			goto activate;
 		}
 
 		if (!READ_ONCE(owner->on_rq) || owner->se.sched_delayed) {
@@ -7143,6 +7157,9 @@ find_proxy_task(struct rq *rq, struct task_struct *donor, struct rq_flags *rf)
 
 resched_idle:
 	return proxy_resched_idle(rq);
+activate:
+	proxy_activate(rq, rf, p);
+	return NULL;
 deactivate:
 	proxy_deactivate(rq, p);
 	return NULL;
-- 
2.56.0.257.gf7497c7d27-goog

[PATCH v33 4/7] sched/proxy: Set TASK_RUNNING when shortcuting return migration

[John Stultz]

K Prateek's prior patch optimizing find_proxy_tasks() logic to
shortcut and run previously blocked tasks on the current cpu
made me realize while we are clearing the blocked_on and
is_blocked, we are not setting the task state as TASK_RUNNING
before returning the task to run.

So set the tasks to TASK_RUNNING prior to returning them to run.

Fixes: b049b81bdff6 ("sched: Handle blocked-waiter migration (and return migration)")
Signed-off-by: John Stultz <jstultz@google.com>
---
Cc: Peter Zijlstra <peterz@infradead.org>
Cc: Ingo Molnar <mingo@redhat.com>
Cc: K Prateek Nayak <kprateek.nayak@amd.com>
Cc: Thomas Gleixner <tglx@linutronix.de>
Cc: Juri Lelli <juri.lelli@redhat.com>
Cc: Vincent Guittot <vincent.guittot@linaro.org>
Cc: Valentin Schneider <vschneid@redhat.com>
Cc: Suleiman Souhlal <suleiman@google.com>
Cc: Andrea Righi <arighi@nvidia.com>
Cc: Metin Kaya <Metin.Kaya@arm.com>
Cc: Dietmar Eggemann <dietmar.eggemann@arm.com>
Cc: Steven Rostedt <rostedt@goodmis.org>
Cc: Zimuzo Ezeozue <zezeozue@google.com>
Cc: Waiman Long <longman@redhat.com>
Cc: Boqun Feng <boqun.feng@gmail.com>
Cc: "Paul E. McKenney" <paulmck@kernel.org>
Cc: Joel Fernandes <joelagnelf@nvidia.com>
Cc: Qais Yousef <qyousef@layalina.io>
Cc: Xuewen Yan <xuewen.yan94@gmail.com>
Cc: kuyo chang <kuyo.chang@mediatek.com>
Cc: hupu <hupu.gm@gmail.com>
Cc: Zhan Xusheng <zhanxusheng@xiaomi.com>
Cc: zhidao su (Xiaomi) <soolaugust@gmail.com>
Cc: Hui Su <sh_def@163.com>
Cc: Shubhang Kaushik (Ampere) <sh@gentwo.org>
Cc: kernel-team@android.com
---
 kernel/sched/core.c | 2 ++
 1 file changed, 2 insertions(+)

diff --git a/kernel/sched/core.c b/kernel/sched/core.c
index 2cb42de255f7a..43ba76b5a3464 100644
--- a/kernel/sched/core.c
+++ b/kernel/sched/core.c
@@ -7028,6 +7028,7 @@ find_proxy_task(struct rq *rq, struct task_struct *donor, struct rq_flags *rf)
 			clear_task_blocked_on(p, mutex);
 			if (task_current(rq, p) || p->wake_cpu == task_cpu(p)) {
 				p->is_blocked = 0;
+				WRITE_ONCE(p->__state, TASK_RUNNING);
 				return p;
 			}
 			goto activate;
@@ -7065,6 +7066,7 @@ find_proxy_task(struct rq *rq, struct task_struct *donor, struct rq_flags *rf)
 			__clear_task_blocked_on(p, NULL);
 			if (task_current(rq, p) || p->wake_cpu == task_cpu(p)) {
 				p->is_blocked = 0;
+				WRITE_ONCE(p->__state, TASK_RUNNING);
 				return p;
 			}
 			goto activate;
-- 
2.56.0.257.gf7497c7d27-goog

[PATCH v33 5/7] sched/proxy: Break cyclic proxy chains by deactivating blocked tasks

[John Stultz]

From: "zhidao su (Xiaomi)" <soolaugust@gmail.com>

find_proxy_task() follows the blocked_on/owner chain for a
blocked donor. If the chain forms a cycle, __schedule() can keep
walking the same chain while holding rq->lock.

Kernel locks are not allowed to have cycles (except ww_mutexes,
which we handle properly), so this logic isn't likely to trip
unless a bad driver has incorrect locking (which lockdep should
detect). However, eventually we want to have proxy-enabled
futexes, where we can't control userland's locking, and will
need to avoid wasting cpu time iterating around a cycle.

A PE cycle reproducer creates two tasks blocked on each other's
mutexes. Without a guard, the guest does not complete within a
90s vng timeout. With this change, loading the reproducer
reports:

  sched/pe: deadlock cycle detected, pid 128

and a heartbeat kthread pinned to the same CPU continues to run:

  pe_cycle_kmod: heartbeat 3 pid 129

Rescheduling idle is not enough here: the same blocked_on
relation remains, so the next scheduling pass can select the
same donor and re-enter the same cycle.

When the walk reaches the original donor again, clear the
current blocked_on relation and deactivate that blocked task. Do
the same for excessive chain depth after revalidating blocked_on
under p->blocked_lock. This removes the task from the proxy-exec
runnable-chain selection path and lets the scheduler make
progress.

Use 1024 as the depth limit to match rtmutex's default
max_lock_depth.

Signed-off-by: zhidao su (Xiaomi) <soolaugust@gmail.com>
[jstultz: Simplified slightly, dropping WARN_ON and owner == donor
 check, slightly reworked commit message]
Signed-off-by: John Stultz <jstultz@google.com>
---
Cc: Peter Zijlstra <peterz@infradead.org>
Cc: Ingo Molnar <mingo@redhat.com>
Cc: K Prateek Nayak <kprateek.nayak@amd.com>
Cc: Thomas Gleixner <tglx@linutronix.de>
Cc: Juri Lelli <juri.lelli@redhat.com>
Cc: Vincent Guittot <vincent.guittot@linaro.org>
Cc: Valentin Schneider <vschneid@redhat.com>
Cc: Suleiman Souhlal <suleiman@google.com>
Cc: Andrea Righi <arighi@nvidia.com>
Cc: Metin Kaya <Metin.Kaya@arm.com>
Cc: Dietmar Eggemann <dietmar.eggemann@arm.com>
Cc: Steven Rostedt <rostedt@goodmis.org>
Cc: Zimuzo Ezeozue <zezeozue@google.com>
Cc: Waiman Long <longman@redhat.com>
Cc: Boqun Feng <boqun.feng@gmail.com>
Cc: "Paul E. McKenney" <paulmck@kernel.org>
Cc: Joel Fernandes <joelagnelf@nvidia.com>
Cc: Qais Yousef <qyousef@layalina.io>
Cc: Xuewen Yan <xuewen.yan94@gmail.com>
Cc: kuyo chang <kuyo.chang@mediatek.com>
Cc: hupu <hupu.gm@gmail.com>
Cc: Zhan Xusheng <zhanxusheng@xiaomi.com>
Cc: zhidao su (Xiaomi) <soolaugust@gmail.com>
Cc: Hui Su <sh_def@163.com>
Cc: Shubhang Kaushik (Ampere) <sh@gentwo.org>
Cc: kernel-team@android.com
---
 kernel/sched/core.c | 10 ++++++++++
 1 file changed, 10 insertions(+)

diff --git a/kernel/sched/core.c b/kernel/sched/core.c
index 43ba76b5a3464..12a42252bf474 100644
--- a/kernel/sched/core.c
+++ b/kernel/sched/core.c
@@ -6984,6 +6984,8 @@ static void proxy_migrate_task(struct rq *rq, struct rq_flags *rf,
 	proxy_reacquire_rq_lock(rq, rf);
 }
 
+#define MAX_PROXY_CHAIN_DEPTH 1024
+
 /*
  * Find runnable lock owner to proxy for mutex blocked donor
  *
@@ -7019,6 +7021,7 @@ find_proxy_task(struct rq *rq, struct task_struct *donor, struct rq_flags *rf)
 	int this_cpu = cpu_of(rq);
 	struct task_struct *p;
 	int owner_cpu;
+	int chain_depth = 0;
 
 	/* Follow blocked_on chain. */
 	for (p = donor; p->is_blocked; p = owner) {
@@ -7139,6 +7142,13 @@ find_proxy_task(struct rq *rq, struct task_struct *donor, struct rq_flags *rf)
 			 */
 			goto resched_idle;
 		}
+
+		/* Limit the depth we'll proxy to avoid cyclic deadlocks */
+		if (++chain_depth > MAX_PROXY_CHAIN_DEPTH) {
+			__clear_task_blocked_on(p, NULL);
+			goto deactivate;
+		}
+
 		/*
 		 * OK, now we're absolutely sure @owner is on this
 		 * rq, therefore holding @rq->lock is sufficient to
-- 
2.56.0.257.gf7497c7d27-goog

[PATCH v33 6/7] sched/proxy: Detect cycles in proxy walks earlier

[John Stultz]

From: Hui Su <sh_def@163.com>

Proxy execution follows blocked_on relationships to find a runnable lock
owner. A cycle in that chain can make find_proxy_task() loop indefinitely
while holding rq->lock.

Use Brent checkpoint state directly in the real owner walk. Cycle detection
reuses the owner resolution already performed by that walk and requires no
separate preflight traversal. The checkpoint, power, and span state are all
invocation-local.

Keep the existing owner == p wakeup-race handling ahead of cycle detection.
Unlike a sequence-marker approach, this adds no task_struct or runqueue
state and requires no activation-time reset.

The online walk can temporarily install a blocked_donor cycle before the
delayed Brent detection point. In the tested recovery path, the selected
task's blocked_donor was cleared before it resumed. A forced-stale control
also confirmed that mutex handoff revalidates the donor's blocked_on
relationship before consuming a backlink. Validation of this trade-off and
comparative measurements against the sequence-marker approach are included
in the cover letter.

Signed-off-by: Hui Su <sh_def@163.com>
[jstultz: Minor tweaks to work with hard MAX_PROXY_CHAIN_DEPTH limit]
Signed-off-by: John Stultz <jstultz@google.com>
---
Cc: Peter Zijlstra <peterz@infradead.org>
Cc: Ingo Molnar <mingo@redhat.com>
Cc: K Prateek Nayak <kprateek.nayak@amd.com>
Cc: Thomas Gleixner <tglx@linutronix.de>
Cc: Juri Lelli <juri.lelli@redhat.com>
Cc: Vincent Guittot <vincent.guittot@linaro.org>
Cc: Valentin Schneider <vschneid@redhat.com>
Cc: Suleiman Souhlal <suleiman@google.com>
Cc: Andrea Righi <arighi@nvidia.com>
Cc: Metin Kaya <Metin.Kaya@arm.com>
Cc: Dietmar Eggemann <dietmar.eggemann@arm.com>
Cc: Steven Rostedt <rostedt@goodmis.org>
Cc: Zimuzo Ezeozue <zezeozue@google.com>
Cc: Waiman Long <longman@redhat.com>
Cc: Boqun Feng <boqun.feng@gmail.com>
Cc: "Paul E. McKenney" <paulmck@kernel.org>
Cc: Joel Fernandes <joelagnelf@nvidia.com>
Cc: Qais Yousef <qyousef@layalina.io>
Cc: Xuewen Yan <xuewen.yan94@gmail.com>
Cc: kuyo chang <kuyo.chang@mediatek.com>
Cc: hupu <hupu.gm@gmail.com>
Cc: Zhan Xusheng <zhanxusheng@xiaomi.com>
Cc: zhidao su (Xiaomi) <soolaugust@gmail.com>
Cc: Hui Su <sh_def@163.com>
Cc: Shubhang Kaushik (Ampere) <sh@gentwo.org>
Cc: kernel-team@android.com
---
 kernel/sched/core.c | 22 +++++++++++++++++++---
 1 file changed, 19 insertions(+), 3 deletions(-)

diff --git a/kernel/sched/core.c b/kernel/sched/core.c
index 12a42252bf474..0cb41a884ea70 100644
--- a/kernel/sched/core.c
+++ b/kernel/sched/core.c
@@ -7017,6 +7017,9 @@ find_proxy_task(struct rq *rq, struct task_struct *donor, struct rq_flags *rf)
 	__must_hold(__rq_lockp(rq))
 {
 	struct task_struct *owner = NULL;
+	struct task_struct *cycle_checkpoint = donor;
+	unsigned int cycle_power = 1;
+	unsigned int cycle_span = 0;
 	bool curr_in_chain = false;
 	int this_cpu = cpu_of(rq);
 	struct task_struct *p;
@@ -7025,8 +7028,16 @@ find_proxy_task(struct rq *rq, struct task_struct *donor, struct rq_flags *rf)
 
 	/* Follow blocked_on chain. */
 	for (p = donor; p->is_blocked; p = owner) {
-		/* if its PROXY_WAKING, do return migration or run if current */
 		struct mutex *mutex = p->blocked_on;
+
+		/* Keep Brent's checkpoint state local to this owner walk. */
+		if (cycle_span == cycle_power) {
+			cycle_checkpoint = p;
+			cycle_power <<= 1;
+			cycle_span = 0;
+		}
+
+		/* if its PROXY_WAKING, do return migration or run if current */
 		if (!mutex) {
 			clear_task_blocked_on(p, mutex);
 			if (task_current(rq, p) || p->wake_cpu == task_cpu(p)) {
@@ -7143,8 +7154,13 @@ find_proxy_task(struct rq *rq, struct task_struct *donor, struct rq_flags *rf)
 			goto resched_idle;
 		}
 
-		/* Limit the depth we'll proxy to avoid cyclic deadlocks */
-		if (++chain_depth > MAX_PROXY_CHAIN_DEPTH) {
+		/*
+		 * Check for cycles, and worst case limit the depth
+		 * we'll proxy to avoid cyclic deadlocks
+		 */
+		cycle_span++;
+		if ((owner == cycle_checkpoint) ||
+		    (++chain_depth > MAX_PROXY_CHAIN_DEPTH)) {
 			__clear_task_blocked_on(p, NULL);
 			goto deactivate;
 		}
-- 
2.56.0.257.gf7497c7d27-goog

[PATCH v33 7/7] sched/proxy: Add deactivated (sleeping) owner handling to find_proxy_task()

[John Stultz]

From: Peter Zijlstra <peterz@infradead.org>

If the blocked_on chain resolves to a sleeping owner, deactivate
the donor task, and enqueue it on the sleeping owner task.
Then re-activate it later when the owner is woken up.

NOTE: This has been particularly challenging to get working
properly, and some of the locking is particularly awkward. I'd
very much appreciate review and feedback for ways to simplify
this.

Signed-off-by: Peter Zijlstra (Intel) <peterz@infradead.org>
Signed-off-by: Juri Lelli <juri.lelli@redhat.com>
Signed-off-by: Valentin Schneider <valentin.schneider@arm.com>
Signed-off-by: Connor O'Brien <connoro@google.com>
[jstultz: This was broken out from the larger proxy() patch]
Signed-off-by: John Stultz <jstultz@google.com>
---
v5:
* Split out from larger proxy patch
v6:
* Major rework, replacing the single list head per task with
  per-task list head and nodes, creating a tree structure so
  we only wake up descendants of the task woken.
* Reworked the locking to take the task->pi_lock, so we can
  avoid mid-chain wakeup races from try_to_wake_up() called by
  the ww_mutex logic.
v7:
* Drop unnecessary __nested lock annotation, as we already drop
  the lock prior.
* Add comments on #else & #endif lines, and clearer function
  names, and commit message tweaks as suggested by Metin Kaya
* Move activate_blocked_entities() call from ttwu_queue to
  try_to_wake_up() to simplify locking. Thanks to questions from
  Metin Kaya
* Fix irqsave/irqrestore usage now we call this outside where
  the pi_lock is held
* Fix activate_blocked_entitites not preserving wake_cpu
* Fix for UP builds
v8:
* Minor checkpatch fixup
* Drop proxy_deactivate and cleanups suggested by Metin
v9:
* Fix bug causing possibly uninitialized cpu value to be used with
  activate_blocked_entities()
* Improved comment around preserving wake_cpu suggested by Metin
* Add additional lockdep asserts, suggested by Metin
* Tweaked placement of lockdep assert, suggested by Metin
* Fixed comment referring to structure entry name
* Fix to call proxy_resched_idle() _prior_ to calling
  proxy_enqueue_on_owner() where we deactivate the task, this
  avoids stale references to rq_selected() when the task may
  have been migrated to another rq.
* Fix to remove the blocked_head list at the start of
  activate_blocked_entities() so we only do a finite amount
  of work, avoiding a potential livelock of two cpus removing
  and adding tasks to the list at the same time if the owner
  went back to sleep while blocked entities were being woken.
v11:
* Big rework to get rid of recursion. Had to add another list
  item to the task_stuct to do this as we are in atomic context
  and cannot allocate memory while activating blocked entities.
  Will need to watch carefully for bugs, as switching to a
  list_head in the task_struct instead of a pointer on the
  stack opens up the potential for races on the shared state,
  but I think I've got the locking sorted.
* Moved proxy_set_task_cpu helper to earlier in the series
* Minor rework for try_to_deactivate_task changes
* Minor variable name cleanups suggested by Metin
v13:
* Switch to use donor from next for proxy_enqueue_on_owner
* Switch to using block_task instead of deactivate_task
v14:
* Ensure we call block_task() last in proxy_enqueue_on_owner
  and not touch it again to avoid races where it might be
  activated on another cpu
* Make sure we activate blocked_entities when we exit from ttwu
* Fix to enqueue the last task in the chain (p) on the blocked
  owner instead of donor, so that we preserve the chain
  structure so mid-chain wakeups propagate properly
* Rework of sleeping_owner handling so that we properly deal
  with delayed-dequeued (sched_delayed) tasks (also removes
  now unused proxy_deactivate() logic)
v15:
* Rework do_activate_task to be activate_task() and have it
  call __activate_task(), suggested by Carlos Llamas
* Put task_struct additions under CONFIG_SCHED_PROXY_EXEC
v16:
* Rework do_activate_blocked_waiter locking to use scoped_guard
* Rework find_proxy_task() logic to use guard
v18:
* Integrate Suleiman's suggested optimization to check sleeping
  owner status before task_cpu, to avoid unnecssarily
  proxy-migrating tasks to then just dequeue them.
* Add on_cpu check to fix for a very hard to reproduce race where
  a late blocked_task_activation() happens while the task is already
  on_cpu elsewhere. When we get to  __schedule() we block the task
  (!on_rq) but haven't yet switched away. blocked_task_activation()
  would then incorrectly activate on a different runqueue.
* Add init_task initialization for sleeping owner lists, as
  suggested by Suleiman
v19:
* Build fixup for !CONFIG_SMP
v22:
* Rework to avoid gotos in guard() scopes, using break and
  switch() on action values. Suggested by K Prateek.
v25:
* Fix elevated nr_uninterruptible and nr_iowait counts,
  which were causing bad loadavg values. Reported and
  fixed by David Stevens <stevensd@google.com>
v28:
* In __proxy_remove_from_sleeping_owner() we call
  put_task(), which might free the owner while we are
  still holing the owners->blocked_lock. So be sure
  to get_task()/put_task() around the owner usage to
  ensure we don't prematurely free the task.
* Also reorder the put_task/unlock lines in
  activate_blocked_waiters(), to avoid a similar issue
v30:
* Optimize activate_blocked_waiters() so we don't do so much
  unnecessary work when proxy-exec is enabled. If there are
  no blocked waiters, we can return early.
v31:
* K Prateek's noticed a potential race where if a sleeping owner
  is woken in paralell with the waiter enquing itself on the
  sleeping owner, the waiting task could get stuck on that owner
  until it sleeps and is woken up again. So double check after
  we grab the blocked_lock to avoid this.
* Maria Yu and Tengfei Fan reported an issue with rq->nr_iowait
  values getting out of balance, and provided a helpful
  reproducer. To fix this, make sure we do the atomic_dec() in
  do_activate_blocked_waiter() before we call
  proxy_set_task_cpu() so we always dec on the same rq we
  inc'ed.
v32:
* Atul Kumar Pant noticed a task could wakeup and then sleep
  before we call into do_activate_blocked_waiter() and in
  that case we would activate the task on the target_rq.
  As the target_rq is where the owner is being woken on, if
  the waiter already woke and ran the activation could move
  it to a cpu outside its affinity mask. So add an extra
  is_blocked check to ensure the task is still blocked on
  the owner.
* PeterZ shared a number of cleanups utilizing guard to make
  the code simpler.
* PeterZ pointed out we could see owner races in
  proxy_remove_from_sleeping_owner(), so re-sample owner after
  we take the lock to ensure we're consistent, and add a BUG_ON
  in __proxy_remove_from_sleeping_owner() to enforce
  p->sleeping_owner  == owner.
* PeterZ noted we're calling activate_blocked_waiters()
  extraniously in sched_ttwu_pending(), so drop that.
v33:
* David Stevens <stevensd@google.com> reported seeing
  "psi: inconsistent task state!" warnings, which was caused
  when we activate the blocked waiter list, proxy-migrating the
  tasks to the owners' rq. Since we currently don't signal to
  the PSI layer, the TSK_MEMSTALL flag persists when the
  following activation happens, throwing the error. This results
  in the source CPU's count of TSK_MEMSTALL becoming permanently
  non-zero, leading to very exaggerated memory PSI.
  To avoid this, check if the target_cpu is the task_cpu(p) and
  if not call psi_ttwu_dequeue() to clear the flags before the
  activation.
* David also noted that when activating blocked tasks, the
  enqueue flag was being set to ENQUEUE_MIGRATED if the owner's
  wake_flags had WF_MIGRATED set, but the waiters task_cpu may
  already be the target_cpu during the activation, so we
  shouldn't activate the waiters with ENQUEUE_MIGRATED in this
  case. So change the logic that sets ENQUEUE_MIGRATED to be
  where we check if the waiter's task_cpu == target_cpu
* It was reported that in some cases unblocked tasks were being
  placed outside of their CPU affinity mask. If the call to
  do_activate_blocked_waiter() was delayed, its possible the
  task has already been woken. We already have checks for task
  state == TASK_WAKING, p->on_rq, task_on_cpu(), but its still
  possible the task woke and then blocked again (sleeping or
  re-waiting on the same or different mutex). So before
  activating on the prior sleeping owner's rq, ensure the
  task_is_blocked() to make sure we don't migrate a
  sleeping task outside of its affinity mask.

Cc: Peter Zijlstra <peterz@infradead.org>
Cc: Ingo Molnar <mingo@redhat.com>
Cc: K Prateek Nayak <kprateek.nayak@amd.com>
Cc: Thomas Gleixner <tglx@linutronix.de>
Cc: Juri Lelli <juri.lelli@redhat.com>
Cc: Vincent Guittot <vincent.guittot@linaro.org>
Cc: Valentin Schneider <vschneid@redhat.com>
Cc: Suleiman Souhlal <suleiman@google.com>
Cc: Andrea Righi <arighi@nvidia.com>
Cc: Metin Kaya <Metin.Kaya@arm.com>
Cc: Dietmar Eggemann <dietmar.eggemann@arm.com>
Cc: Steven Rostedt <rostedt@goodmis.org>
Cc: Zimuzo Ezeozue <zezeozue@google.com>
Cc: Waiman Long <longman@redhat.com>
Cc: Boqun Feng <boqun.feng@gmail.com>
Cc: "Paul E. McKenney" <paulmck@kernel.org>
Cc: Joel Fernandes <joelagnelf@nvidia.com>
Cc: Qais Yousef <qyousef@layalina.io>
Cc: Xuewen Yan <xuewen.yan94@gmail.com>
Cc: kuyo chang <kuyo.chang@mediatek.com>
Cc: hupu <hupu.gm@gmail.com>
Cc: Zhan Xusheng <zhanxusheng@xiaomi.com>
Cc: zhidao su (Xiaomi) <soolaugust@gmail.com>
Cc: Hui Su <sh_def@163.com>
Cc: Shubhang Kaushik (Ampere) <sh@gentwo.org>
Cc: kernel-team@android.com
---
 include/linux/sched.h      |   7 +
 include/linux/sched/task.h |   1 +
 init/init_task.c           |   6 +
 kernel/fork.c              |   6 +
 kernel/sched/core.c        | 333 ++++++++++++++++++++++++++++++++++---
 5 files changed, 332 insertions(+), 21 deletions(-)

diff --git a/include/linux/sched.h b/include/linux/sched.h
index 12a7e094a3e6b..3fae2f1438583 100644
--- a/include/linux/sched.h
+++ b/include/linux/sched.h
@@ -1266,6 +1266,13 @@ struct task_struct {
 
 	struct mutex			*blocked_on;	/* lock we're blocked on */
 	raw_spinlock_t			blocked_lock;
+#ifdef CONFIG_SCHED_PROXY_EXEC
+	struct list_head		blocked_head;  /* tasks blocked on this task */
+	struct list_head		blocked_node;  /* our entry on someone elses blocked_head */
+	/* Node for list of tasks to process blocked_head list for blocked entitiy activations */
+	struct list_head		blocked_activation_node;
+	struct task_struct		*sleeping_owner; /* task our blocked_node is enqueued on */
+#endif
 
 	/*
 	 * The task that is boosting this task; a back link for the current
diff --git a/include/linux/sched/task.h b/include/linux/sched/task.h
index 90ed5bc3c7afe..26c19ee980456 100644
--- a/include/linux/sched/task.h
+++ b/include/linux/sched/task.h
@@ -160,6 +160,7 @@ static inline void put_task_struct(struct task_struct *t)
 }
 
 DEFINE_FREE(put_task, struct task_struct *, if (_T) put_task_struct(_T))
+DEFINE_GUARD(get_task, struct task_struct *, get_task_struct(_T), put_task_struct(_T))
 
 static inline void put_task_struct_many(struct task_struct *t, int nr)
 {
diff --git a/init/init_task.c b/init/init_task.c
index ce7c2b07d855d..aed3f7d8a5cc3 100644
--- a/init/init_task.c
+++ b/init/init_task.c
@@ -213,6 +213,12 @@ struct task_struct init_task __aligned(L1_CACHE_BYTES) = {
 						 &init_task.alloc_lock),
 #endif
 	.blocked_donor = NULL,
+#ifdef CONFIG_SCHED_PROXY_EXEC
+	.blocked_head = LIST_HEAD_INIT(init_task.blocked_head),
+	.blocked_node = LIST_HEAD_INIT(init_task.blocked_node),
+	.blocked_activation_node = LIST_HEAD_INIT(init_task.blocked_activation_node),
+	.sleeping_owner = NULL,
+#endif
 #ifdef CONFIG_RT_MUTEXES
 	.pi_waiters	= RB_ROOT_CACHED,
 	.pi_top_task	= NULL,
diff --git a/kernel/fork.c b/kernel/fork.c
index 394906afafd30..f87f806c2958b 100644
--- a/kernel/fork.c
+++ b/kernel/fork.c
@@ -2277,6 +2277,12 @@ __latent_entropy struct task_struct *copy_process(
 
 	p->blocked_on = NULL; /* not blocked yet */
 	p->blocked_donor = NULL; /* nobody is boosting p yet */
+#ifdef CONFIG_SCHED_PROXY_EXEC
+	INIT_LIST_HEAD(&p->blocked_head);
+	INIT_LIST_HEAD(&p->blocked_node);
+	INIT_LIST_HEAD(&p->blocked_activation_node);
+	p->sleeping_owner = NULL;
+#endif
 
 #ifdef CONFIG_BCACHE
 	p->sequential_io	= 0;
diff --git a/kernel/sched/core.c b/kernel/sched/core.c
index 0cb41a884ea70..be3ce8b554fed 100644
--- a/kernel/sched/core.c
+++ b/kernel/sched/core.c
@@ -2229,7 +2229,7 @@ inline bool dequeue_task(struct rq *rq, struct task_struct *p, int flags)
 	return p->sched_class->dequeue_task(rq, p, flags);
 }
 
-void activate_task(struct rq *rq, struct task_struct *p, int flags)
+static inline void __activate_task(struct rq *rq, struct task_struct *p, int flags)
 {
 	if (task_on_rq_migrating(p))
 		flags |= ENQUEUE_MIGRATED;
@@ -2240,6 +2240,76 @@ void activate_task(struct rq *rq, struct task_struct *p, int flags)
 	ASSERT_EXCLUSIVE_WRITER(p->on_rq);
 }
 
+#ifdef CONFIG_SCHED_PROXY_EXEC
+static inline
+void __proxy_remove_from_sleeping_owner(struct task_struct *owner, struct task_struct *p)
+{
+	lockdep_assert_held(&owner->blocked_lock);
+
+	BUG_ON(p->sleeping_owner != owner);
+
+	list_del_init(&p->blocked_node);
+	WRITE_ONCE(p->sleeping_owner, NULL);
+	put_task_struct(owner); // matches get in proxy_enqueue_on_owner
+}
+
+static inline void proxy_remove_from_sleeping_owner(struct task_struct *p)
+{
+	struct task_struct *owner;
+
+retry:
+	owner = data_race(READ_ONCE(p->sleeping_owner));
+	if (!owner)
+		return;
+
+	/*
+	 * __proxy_remove_from_sleeping_owner() does a
+	 * put on owner to match the get done in
+	 * proxy_enqueue_on_owner(). If that put is the
+	 * last one and it frees owner, we'd be freeing
+	 * a lock we held. So get/put owner around its
+	 * usage her to ensure that doesn't happen.
+	 */
+	scoped_guard(get_task, owner) {
+		guard(raw_spinlock)(&owner->blocked_lock);
+
+		if (owner != READ_ONCE(p->sleeping_owner))
+			goto retry;
+		__proxy_remove_from_sleeping_owner(owner, p);
+	}
+}
+
+void activate_task(struct rq *rq, struct task_struct *p, int en_flags)
+{
+	lockdep_assert_rq_held(rq);
+
+	if (!sched_proxy_exec()) {
+		__activate_task(rq, p, en_flags);
+		return;
+	}
+
+	proxy_remove_from_sleeping_owner(p);
+	/*
+	 * By calling __activate_task() with blocked_lock held, we
+	 * order against the find_proxy_task() blocked_task case
+	 * such that no more blocked tasks will be enqueued on p
+	 * once we release p->blocked_lock.
+	 */
+	guard(raw_spinlock)(&p->blocked_lock);
+	WARN_ON(task_cpu(p) != cpu_of(rq));
+	__activate_task(rq, p, en_flags);
+}
+#else
+static inline void proxy_remove_from_sleeping_owner(struct task_struct *p)
+{
+}
+
+void activate_task(struct rq *rq, struct task_struct *p, int en_flags)
+{
+	__activate_task(rq, p, en_flags);
+}
+#endif
+
 void deactivate_task(struct rq *rq, struct task_struct *p, int flags)
 {
 	WARN_ON_ONCE(flags & DEQUEUE_SLEEP);
@@ -3815,6 +3885,184 @@ static inline void proxy_reset_donor(struct rq *rq)
 	resched_curr(rq);
 }
 
+static inline void proxy_set_task_cpu(struct task_struct *p, int cpu)
+{
+	unsigned int wake_cpu;
+
+	/*
+	 * Since we are enqueuing a blocked task on a cpu it may
+	 * not be able to run on, preserve wake_cpu when we
+	 * __set_task_cpu so we can return the task to where it
+	 * was previously runnable.
+	 */
+	wake_cpu = p->wake_cpu;
+	__set_task_cpu(p, cpu);
+	p->wake_cpu = wake_cpu;
+}
+
+static void do_activate_blocked_waiter(struct rq *target_rq, struct task_struct *p, int en_flags)
+{
+	struct rq_flags rf;
+	int target_cpu = cpu_of(target_rq);
+
+	scoped_guard (raw_spinlock_irqsave, &p->pi_lock) {
+		/* If task is no longer blocked, don't activate */
+		if (!p->is_blocked)
+			return;
+
+		/* Avoid racing with ttwu */
+		if (READ_ONCE(p->__state) == TASK_WAKING)
+			return;
+
+		if (READ_ONCE(p->on_rq)) {
+			/*
+			 * We raced with a non mutex handoff activation of p.
+			 * That activation will also take care of activating
+			 * all of the tasks after p in the blocked_head list,
+			 * so we're done here.
+			 */
+			return;
+		}
+		if (task_on_cpu(task_rq(p), p)) {
+			/*
+			 * Its possible this activation is very late, and
+			 * we already were woken up and are running on a
+			 * different cpu. If that task blocked, it could be
+			 * dequeued (so on_rq == 0), but still on_cpu.
+			 * Bail in this case, as we definitely don't want to
+			 * activate a task when its on_cpu elsewhere.
+			 */
+			return;
+		}
+
+		scoped_guard (raw_spinlock, &p->blocked_lock) {
+			/*
+			 * Again, if activation is delayed, it's possible the
+			 * task has been woken and is no longer blocked_on,
+			 * but went back to sleep, so double check blocked_on
+			 * before activating onto the owner's rq
+			 */
+			if (!task_is_blocked(p))
+				return;
+		}
+
+		/*
+		 * Have to make sure we handle nr_iowait adjustment before
+		 * we call proxy_set_task_cpu() to ensure we are adjusting
+		 * the same runqueue we left (where block_task()
+		 * incremented nr_iowait).
+		 */
+		if (p->in_iowait) {
+			delayacct_blkio_end(p);
+			atomic_dec(&task_rq(p)->nr_iowait);
+		}
+
+		if (task_cpu(p) != target_cpu) {
+			en_flags |= ENQUEUE_MIGRATED;
+			psi_ttwu_dequeue(p);
+			proxy_set_task_cpu(p, target_cpu);
+		}
+		rq_lock_irqsave(target_rq, &rf);
+		/*
+		 * proxy_enqueue_on_owner() called block_task() which
+		 * increments nr_uninterruptible, so we need to reverse
+		 * that when we activate the blocked waiter
+		 */
+		if (p->sched_contributes_to_load)
+			target_rq->nr_uninterruptible--;
+		update_rq_clock(target_rq);
+		activate_task(target_rq, p, en_flags);
+		resched_curr(target_rq);
+		rq_unlock_irqrestore(target_rq, &rf);
+	}
+}
+
+static void activate_blocked_waiters(struct rq *target_rq,
+				     struct task_struct *owner,
+				     int wake_flags)
+{
+	struct list_head bal_head;
+	unsigned long flags;
+	int en_flags = ENQUEUE_WAKEUP | ENQUEUE_NOCLOCK;
+
+	if (!sched_proxy_exec())
+		return;
+
+	/*
+	 * A whole bunch of waiting donor tasks back this blocked
+	 * lock owner task, wake them all up to give this task its
+	 * 'fair' share.
+	 *
+	 * This is a little unique here and the locking is messy.
+	 * At this point we only hold the blocked_lock, so the
+	 * owner task may be able to run and do all sorts of
+	 * things while we are processing the blocked_head list,
+	 * including going back to sleep, which can cause tasks
+	 * to be added to the owners->blocked_head while we are
+	 * processing it!
+	 * Thus, we pull the entire list off the owner->blocked_head
+	 * here so that we will only process a finite amount of
+	 * tasks. Tasks added after this will be processed by the
+	 * future wake events.
+	 * Even though we have pulled the list off the blocked_head
+	 * the removed list is *still* "owned" and serialized by
+	 * the owner->blocked_lock! As we have to serialize against
+	 * mid-chain wakeups, who may try to remove themselves from
+	 * the list.
+	 */
+	raw_spin_lock_irqsave(&owner->blocked_lock, flags);
+	if (!list_empty(&owner->blocked_activation_node)) {
+		raw_spin_unlock_irqrestore(&owner->blocked_lock, flags);
+		return;
+	}
+
+	if (list_empty(&owner->blocked_head)) {
+		raw_spin_unlock_irqrestore(&owner->blocked_lock, flags);
+		return;
+	}
+
+	get_task_struct(owner);
+	INIT_LIST_HEAD(&bal_head);
+	list_add_tail(&owner->blocked_activation_node, &bal_head);
+	raw_spin_unlock_irqrestore(&owner->blocked_lock, flags);
+
+	while (!list_empty(&bal_head)) {
+		struct list_head tmp_head;
+
+		INIT_LIST_HEAD(&tmp_head);
+		owner = list_first_entry(&bal_head, struct task_struct, blocked_activation_node);
+
+		raw_spin_lock_irqsave(&owner->blocked_lock, flags);
+		list_replace_init(&owner->blocked_head, &tmp_head);
+		list_del_init(&owner->blocked_activation_node);
+		while (!list_empty(&tmp_head)) {
+			struct task_struct *p;
+
+			p = list_first_entry(&tmp_head,
+					     struct task_struct,
+					     blocked_node);
+			WARN_ON(p == owner);
+			__proxy_remove_from_sleeping_owner(owner, p);
+			raw_spin_unlock_irqrestore(&owner->blocked_lock, flags);
+
+			do_activate_blocked_waiter(target_rq, p, en_flags);
+
+			raw_spin_lock_irqsave(&p->blocked_lock, flags);
+			if (list_empty(&p->blocked_activation_node)) {
+				get_task_struct(p);
+				list_add_tail(&p->blocked_activation_node, &bal_head);
+			}
+			raw_spin_unlock_irqrestore(&p->blocked_lock, flags);
+
+			raw_spin_lock_irqsave(&owner->blocked_lock, flags);
+		}
+		raw_spin_unlock_irqrestore(&owner->blocked_lock, flags);
+		put_task_struct(owner); // put matches get prior to adding to local bal_head
+	}
+}
+
+static inline struct task_struct *proxy_resched_idle(struct rq *rq);
+
 /*
  * Checks to see if task p has been proxy-migrated to another rq
  * and needs to be returned. If so, we deactivate the task here
@@ -3872,6 +4120,10 @@ static inline bool proxy_needs_return(struct rq *rq, struct task_struct *p)
 {
 	return false;
 }
+
+static inline void activate_blocked_waiters(struct rq *target_rq,
+					    struct task_struct *owner,
+					    int wake_flags) {}
 #endif /* CONFIG_SCHED_PROXY_EXEC */
 
 static void
@@ -3945,8 +4197,10 @@ static int ttwu_runnable(struct task_struct *p, int wake_flags)
 
 	update_rq_clock(rq);
 	if (p->is_blocked) {
-		if (p->se.sched_delayed)
+		if (p->se.sched_delayed) {
+			proxy_remove_from_sleeping_owner(p);
 			enqueue_task(rq, p, ENQUEUE_NOCLOCK | ENQUEUE_DELAYED);
+		}
 		if (proxy_needs_return(rq, p))
 			return 0;
 	}
@@ -3975,13 +4229,15 @@ void sched_ttwu_pending(void *arg)
 	update_rq_clock(rq);
 
 	llist_for_each_entry_safe(p, t, llist, wake_entry.llist) {
+		int wake_flags;
 		if (WARN_ON_ONCE(p->on_cpu))
 			smp_cond_load_acquire(&p->on_cpu, !VAL);
 
 		if (WARN_ON_ONCE(task_cpu(p) != cpu_of(rq)))
 			set_task_cpu(p, cpu_of(rq));
 
-		ttwu_do_activate(rq, p, p->sched_remote_wakeup ? WF_MIGRATED : 0, &rf);
+		wake_flags = p->sched_remote_wakeup ? WF_MIGRATED : 0;
+		ttwu_do_activate(rq, p, wake_flags, &rf);
 	}
 
 	/*
@@ -4488,6 +4744,7 @@ int try_to_wake_up(struct task_struct *p, unsigned int state, int wake_flags)
 		ttwu_queue(p, cpu, wake_flags);
 	}
 out:
+	activate_blocked_waiters(cpu_rq(task_cpu(p)), p, wake_flags);
 	if (success)
 		ttwu_stat(p, task_cpu(p), wake_flags);
 
@@ -6822,21 +7079,6 @@ static bool try_to_block_task(struct rq *rq, struct task_struct *p,
 }
 
 #ifdef CONFIG_SCHED_PROXY_EXEC
-static inline void proxy_set_task_cpu(struct task_struct *p, int cpu)
-{
-	unsigned int wake_cpu;
-
-	/*
-	 * Since we are enqueuing a blocked task on a cpu it may
-	 * not be able to run on, preserve wake_cpu when we
-	 * __set_task_cpu so we can return the task to where it
-	 * was previously runnable.
-	 */
-	wake_cpu = p->wake_cpu;
-	__set_task_cpu(p, cpu);
-	p->wake_cpu = wake_cpu;
-}
-
 static inline struct task_struct *proxy_resched_idle(struct rq *rq)
 {
 	put_prev_set_next_task(rq, rq->donor, rq->idle);
@@ -6984,6 +7226,29 @@ static void proxy_migrate_task(struct rq *rq, struct rq_flags *rf,
 	proxy_reacquire_rq_lock(rq, rf);
 }
 
+static void proxy_enqueue_on_owner(struct rq *rq, struct task_struct *owner,
+				   struct task_struct *p)
+{
+	lockdep_assert_rq_held(rq);
+	lockdep_assert_held(&owner->blocked_lock);
+	/*
+	 * ttwu_activate() will pick them up and place them on whatever rq
+	 * @owner will run next.
+	 */
+	WARN_ON(p == owner);
+	WARN_ON(!p->on_rq);
+	WARN_ON(p->sleeping_owner);
+	get_task_struct(owner);
+	WRITE_ONCE(p->sleeping_owner, owner);
+	/*
+	 * ttwu_do_activate must not have a chance to activate p
+	 * elsewhere before it's fully extricated from its old rq.
+	 */
+	list_add(&p->blocked_node, &owner->blocked_head);
+	proxy_resched_idle(rq);
+	block_task(rq, p, READ_ONCE(p->__state));
+}
+
 #define MAX_PROXY_CHAIN_DEPTH 1024
 
 /*
@@ -7087,11 +7352,37 @@ find_proxy_task(struct rq *rq, struct task_struct *donor, struct rq_flags *rf)
 		}
 
 		if (!READ_ONCE(owner->on_rq) || owner->se.sched_delayed) {
-			/* XXX Don't handle blocked owners/delayed dequeue yet */
+			/*
+			 * rq->curr must not be added to the blocked_head list or else
+			 * ttwu_do_activate could enqueue it elsewhere before it switches
+			 * out here. The approach to avoid this is the same as in the
+			 * migrate_task case.
+			 */
 			if (curr_in_chain)
 				goto resched_idle;
-			__clear_task_blocked_on(p, NULL);
-			goto deactivate;
+			/*
+			 * If !@owner->on_rq, holding @rq->lock will not pin the task,
+			 * so we cannot drop @mutex->wait_lock until we're sure its a blocked
+			 * task on this rq.
+			 *
+			 * We use @owner->blocked_lock to serialize against ttwu_activate().
+			 * Either we see its new owner->on_rq or it will see our list_add().
+			 */
+			WARN_ON(owner == p);
+			raw_spin_unlock(&p->blocked_lock);
+			raw_spin_lock(&owner->blocked_lock);
+			/*
+			 * Before actually adding to the sleeping owner, double check
+			 * we didn't race with an owner wakeup before grabbing the
+			 * owner's blocked_lock.
+			 */
+			if (!READ_ONCE(owner->on_rq) || owner->se.sched_delayed)
+				proxy_enqueue_on_owner(rq, owner, p);
+
+			raw_spin_unlock(&owner->blocked_lock);
+			raw_spin_lock(&p->blocked_lock);
+
+			return NULL; /* retry task selection */
 		}
 
 		owner_cpu = task_cpu(owner);
-- 
2.56.0.257.gf7497c7d27-goog

Re: [PATCH v33 3/7] sched/core: Activate blocked donor when no owner is found

[Andrea Righi]

Hi John and Prateek,

On Fri, Oct 23, 2026 at 10:04:14PM +0000, John Stultz wrote:
> From: K Prateek Nayak <kprateek.nayak@amd.com>
> 
> mutex_unlock_slowpath() follows:
> 
>     if (owner & MUTEX_FLAG_HANDOFF)
>         break /* ... and do __mutex_handoff() */
> 
>     if (atomic_long_try_cmpxchg_release(&lock->owner, &owner, __owner_flags(owner))) {
>         if (owner & MUTEX_FLAG_WAITERS)
>             break; /* ... and wake up the forst waiter. */
> 
> MUTEX_FLAG_HANDOFF is only set by first-waiter after it has been woken
> up and in absence of MUTEX_FLAG_HANDOFF, the owner clears itself from
> the lock_word and wakes up the first waiter to try a
> __mutex_trylock_or_handoff().
> 
> MUTEX_FLAG_HANDOFF exists to prevent new optimistic spinners from
> trying to hijack the lock from waiter all the time and potentially
> starving them but it is not necessary for MUTEX_FLAG_HANDOFF to be
> always set in presence of a waiter.
> 
> If a blocked donor is deactivated when no owner is observed, it may not
> be woken up until it becomes the first waiter and is naturally woken up
> which breaks proxy in the interim.
> 
> Wake up the blocked donor and allow it to grab the lock when no owner is
> observed. If the task manages to grab the lock, the block chain will
> follow at the next proxy migration. If the task fails to grab the lock,
> same situation is restored and everyone migrated to the CPU of new
> owner.
> 
> Similarly, do the same for the NULL blocked_on/mutex pointer for
> consistency.
> 
> Fixes: f13beb010e4a ("sched: Have try_to_wake_up() handle return-migration for PROXY_WAKING case")
> Signed-off-by: K Prateek Nayak <kprateek.nayak@amd.com>
> Signed-off-by: John Stultz <jstultz@google.com>
> ---

...

> @@ -7013,11 +7026,11 @@ find_proxy_task(struct rq *rq, struct task_struct *donor, struct rq_flags *rf)
>  		struct mutex *mutex = p->blocked_on;
>  		if (!mutex) {
>  			clear_task_blocked_on(p, mutex);
> -			if (task_current(rq, p)) {
> +			if (task_current(rq, p) || p->wake_cpu == task_cpu(p)) {
>  				p->is_blocked = 0;
>  				return p;
>  			}
> -			goto deactivate;
> +			goto activate;
>  		}

IIUC, p here isn't necessarily the donor, after the first iteration it
can be an intermediate owner that is queued on this rq and blocked
itself. If its blocked_on was cleared by a handoff (or its mutex has no
owner, below), we now return it when p->wake_cpu == task_cpu(p),
skipping the sched_cpu_cookie_match() check at the end of the function.

So with CONFIG_SCHED_CORE enabled, are we running a task that was never
cookie-checked by the core-wide pick?

>  
>  		/*
> @@ -7046,14 +7059,15 @@ find_proxy_task(struct rq *rq, struct task_struct *donor, struct rq_flags *rf)
>  			/*
>  			 * If there is no owner, either clear blocked_on
>  			 * and return p (if it is current and safe to
> -			 * just run on this rq), or return-migrate the task.
> +			 * just run on this rq), or wake the task to try
> +			 * and grab the lock it is blocked on.
>  			 */
>  			__clear_task_blocked_on(p, NULL);
> -			if (task_current(rq, p)) {
> +			if (task_current(rq, p) || p->wake_cpu == task_cpu(p)) {
>  				p->is_blocked = 0;
>  				return p;
>  			}
> -			goto deactivate;
> +			goto activate;
>  		}

Same here.

Thanks,
-Andrea

Re: [PATCH v33 4/7] sched/proxy: Set TASK_RUNNING when shortcuting return migration

[Andrea Righi]

Hi John,

On Fri, Oct 23, 2026 at 10:04:15PM +0000, John Stultz wrote:
> K Prateek's prior patch optimizing find_proxy_tasks() logic to
> shortcut and run previously blocked tasks on the current cpu
> made me realize while we are clearing the blocked_on and
> is_blocked, we are not setting the task state as TASK_RUNNING
> before returning the task to run.
> 
> So set the tasks to TASK_RUNNING prior to returning them to run.
> 
> Fixes: b049b81bdff6 ("sched: Handle blocked-waiter migration (and return migration)")
> Signed-off-by: John Stultz <jstultz@google.com>
> ---
> Cc: Peter Zijlstra <peterz@infradead.org>
> Cc: Ingo Molnar <mingo@redhat.com>
> Cc: K Prateek Nayak <kprateek.nayak@amd.com>
> Cc: Thomas Gleixner <tglx@linutronix.de>
> Cc: Juri Lelli <juri.lelli@redhat.com>
> Cc: Vincent Guittot <vincent.guittot@linaro.org>
> Cc: Valentin Schneider <vschneid@redhat.com>
> Cc: Suleiman Souhlal <suleiman@google.com>
> Cc: Andrea Righi <arighi@nvidia.com>
> Cc: Metin Kaya <Metin.Kaya@arm.com>
> Cc: Dietmar Eggemann <dietmar.eggemann@arm.com>
> Cc: Steven Rostedt <rostedt@goodmis.org>
> Cc: Zimuzo Ezeozue <zezeozue@google.com>
> Cc: Waiman Long <longman@redhat.com>
> Cc: Boqun Feng <boqun.feng@gmail.com>
> Cc: "Paul E. McKenney" <paulmck@kernel.org>
> Cc: Joel Fernandes <joelagnelf@nvidia.com>
> Cc: Qais Yousef <qyousef@layalina.io>
> Cc: Xuewen Yan <xuewen.yan94@gmail.com>
> Cc: kuyo chang <kuyo.chang@mediatek.com>
> Cc: hupu <hupu.gm@gmail.com>
> Cc: Zhan Xusheng <zhanxusheng@xiaomi.com>
> Cc: zhidao su (Xiaomi) <soolaugust@gmail.com>
> Cc: Hui Su <sh_def@163.com>
> Cc: Shubhang Kaushik (Ampere) <sh@gentwo.org>
> Cc: kernel-team@android.com
> ---
>  kernel/sched/core.c | 2 ++
>  1 file changed, 2 insertions(+)
> 
> diff --git a/kernel/sched/core.c b/kernel/sched/core.c
> index 2cb42de255f7a..43ba76b5a3464 100644
> --- a/kernel/sched/core.c
> +++ b/kernel/sched/core.c
> @@ -7028,6 +7028,7 @@ find_proxy_task(struct rq *rq, struct task_struct *donor, struct rq_flags *rf)
>  			clear_task_blocked_on(p, mutex);
>  			if (task_current(rq, p) || p->wake_cpu == task_cpu(p)) {
>  				p->is_blocked = 0;
> +				WRITE_ONCE(p->__state, TASK_RUNNING);
>  				return p;
>  			}
>  			goto activate;

This is basically an inlined ttwu_do_wakeup() without
trace_sched_wakeup().

> @@ -7065,6 +7066,7 @@ find_proxy_task(struct rq *rq, struct task_struct *donor, struct rq_flags *rf)
>  			__clear_task_blocked_on(p, NULL);
>  			if (task_current(rq, p) || p->wake_cpu == task_cpu(p)) {
>  				p->is_blocked = 0;
> +				WRITE_ONCE(p->__state, TASK_RUNNING);
>  				return p;
>  			}
>  			goto activate;

Ditto.

Can we just call ttwu_do_wakeup(p)? It'd also avoid having two copies of
the same state transition that can diverge.

Thanks,
-Andrea

Re: [PATCH v33 7/7] sched/proxy: Add deactivated (sleeping) owner handling to find_proxy_task()

[Andrea Righi]

Hi John and Peter,

On Fri, Oct 23, 2026 at 10:04:18PM +0000, John Stultz wrote:
> From: Peter Zijlstra <peterz@infradead.org>
> 
> If the blocked_on chain resolves to a sleeping owner, deactivate
> the donor task, and enqueue it on the sleeping owner task.
> Then re-activate it later when the owner is woken up.
> 
> NOTE: This has been particularly challenging to get working
> properly, and some of the locking is particularly awkward. I'd
> very much appreciate review and feedback for ways to simplify
> this.
> 
> Signed-off-by: Peter Zijlstra (Intel) <peterz@infradead.org>
> Signed-off-by: Juri Lelli <juri.lelli@redhat.com>
> Signed-off-by: Valentin Schneider <valentin.schneider@arm.com>
> Signed-off-by: Connor O'Brien <connoro@google.com>
> [jstultz: This was broken out from the larger proxy() patch]
> Signed-off-by: John Stultz <jstultz@google.com>
> ---

...

> diff --git a/include/linux/sched.h b/include/linux/sched.h
> index 12a7e094a3e6b..3fae2f1438583 100644
> --- a/include/linux/sched.h
> +++ b/include/linux/sched.h
> @@ -1266,6 +1266,13 @@ struct task_struct {
>  
>  	struct mutex			*blocked_on;	/* lock we're blocked on */
>  	raw_spinlock_t			blocked_lock;
> +#ifdef CONFIG_SCHED_PROXY_EXEC
> +	struct list_head		blocked_head;  /* tasks blocked on this task */
> +	struct list_head		blocked_node;  /* our entry on someone elses blocked_head */
> +	/* Node for list of tasks to process blocked_head list for blocked entitiy activations */

nit: s/entitiy/entity/

> +	struct list_head		blocked_activation_node;
> +	struct task_struct		*sleeping_owner; /* task our blocked_node is enqueued on */
> +#endif
>  
>  	/*
>  	 * The task that is boosting this task; a back link for the current
> diff --git a/include/linux/sched/task.h b/include/linux/sched/task.h
> index 90ed5bc3c7afe..26c19ee980456 100644
> --- a/include/linux/sched/task.h
> +++ b/include/linux/sched/task.h
> @@ -160,6 +160,7 @@ static inline void put_task_struct(struct task_struct *t)
>  }
>  
>  DEFINE_FREE(put_task, struct task_struct *, if (_T) put_task_struct(_T))
> +DEFINE_GUARD(get_task, struct task_struct *, get_task_struct(_T), put_task_struct(_T))
>  
>  static inline void put_task_struct_many(struct task_struct *t, int nr)
>  {
> diff --git a/init/init_task.c b/init/init_task.c
> index ce7c2b07d855d..aed3f7d8a5cc3 100644
> --- a/init/init_task.c
> +++ b/init/init_task.c
> @@ -213,6 +213,12 @@ struct task_struct init_task __aligned(L1_CACHE_BYTES) = {
>  						 &init_task.alloc_lock),
>  #endif
>  	.blocked_donor = NULL,
> +#ifdef CONFIG_SCHED_PROXY_EXEC
> +	.blocked_head = LIST_HEAD_INIT(init_task.blocked_head),
> +	.blocked_node = LIST_HEAD_INIT(init_task.blocked_node),
> +	.blocked_activation_node = LIST_HEAD_INIT(init_task.blocked_activation_node),
> +	.sleeping_owner = NULL,
> +#endif
>  #ifdef CONFIG_RT_MUTEXES
>  	.pi_waiters	= RB_ROOT_CACHED,
>  	.pi_top_task	= NULL,
> diff --git a/kernel/fork.c b/kernel/fork.c
> index 394906afafd30..f87f806c2958b 100644
> --- a/kernel/fork.c
> +++ b/kernel/fork.c
> @@ -2277,6 +2277,12 @@ __latent_entropy struct task_struct *copy_process(
>  
>  	p->blocked_on = NULL; /* not blocked yet */
>  	p->blocked_donor = NULL; /* nobody is boosting p yet */
> +#ifdef CONFIG_SCHED_PROXY_EXEC
> +	INIT_LIST_HEAD(&p->blocked_head);
> +	INIT_LIST_HEAD(&p->blocked_node);
> +	INIT_LIST_HEAD(&p->blocked_activation_node);
> +	p->sleeping_owner = NULL;
> +#endif
>  
>  #ifdef CONFIG_BCACHE
>  	p->sequential_io	= 0;
> diff --git a/kernel/sched/core.c b/kernel/sched/core.c
> index 0cb41a884ea70..be3ce8b554fed 100644
> --- a/kernel/sched/core.c
> +++ b/kernel/sched/core.c
> @@ -2229,7 +2229,7 @@ inline bool dequeue_task(struct rq *rq, struct task_struct *p, int flags)
>  	return p->sched_class->dequeue_task(rq, p, flags);
>  }
>  
> -void activate_task(struct rq *rq, struct task_struct *p, int flags)
> +static inline void __activate_task(struct rq *rq, struct task_struct *p, int flags)
>  {
>  	if (task_on_rq_migrating(p))
>  		flags |= ENQUEUE_MIGRATED;
> @@ -2240,6 +2240,76 @@ void activate_task(struct rq *rq, struct task_struct *p, int flags)
>  	ASSERT_EXCLUSIVE_WRITER(p->on_rq);
>  }
>  
> +#ifdef CONFIG_SCHED_PROXY_EXEC
> +static inline
> +void __proxy_remove_from_sleeping_owner(struct task_struct *owner, struct task_struct *p)
> +{
> +	lockdep_assert_held(&owner->blocked_lock);
> +
> +	BUG_ON(p->sleeping_owner != owner);
> +
> +	list_del_init(&p->blocked_node);
> +	WRITE_ONCE(p->sleeping_owner, NULL);
> +	put_task_struct(owner); // matches get in proxy_enqueue_on_owner
> +}
> +
> +static inline void proxy_remove_from_sleeping_owner(struct task_struct *p)
> +{
> +	struct task_struct *owner;
> +
> +retry:
> +	owner = data_race(READ_ONCE(p->sleeping_owner));
> +	if (!owner)
> +		return;
> +
> +	/*
> +	 * __proxy_remove_from_sleeping_owner() does a
> +	 * put on owner to match the get done in
> +	 * proxy_enqueue_on_owner(). If that put is the
> +	 * last one and it frees owner, we'd be freeing
> +	 * a lock we held. So get/put owner around its
> +	 * usage her to ensure that doesn't happen.

nit: s/usage her/usage here/

> +	 */
> +	scoped_guard(get_task, owner) {
> +		guard(raw_spinlock)(&owner->blocked_lock);
> +
> +		if (owner != READ_ONCE(p->sleeping_owner))
> +			goto retry;
> +		__proxy_remove_from_sleeping_owner(owner, p);
> +	}
> +}
> +
> +void activate_task(struct rq *rq, struct task_struct *p, int en_flags)
> +{
> +	lockdep_assert_rq_held(rq);
> +
> +	if (!sched_proxy_exec()) {
> +		__activate_task(rq, p, en_flags);
> +		return;
> +	}
> +
> +	proxy_remove_from_sleeping_owner(p);
> +	/*
> +	 * By calling __activate_task() with blocked_lock held, we
> +	 * order against the find_proxy_task() blocked_task case
> +	 * such that no more blocked tasks will be enqueued on p
> +	 * once we release p->blocked_lock.
> +	 */
> +	guard(raw_spinlock)(&p->blocked_lock);
> +	WARN_ON(task_cpu(p) != cpu_of(rq));
> +	__activate_task(rq, p, en_flags);
> +}
> +#else
> +static inline void proxy_remove_from_sleeping_owner(struct task_struct *p)
> +{
> +}
> +
> +void activate_task(struct rq *rq, struct task_struct *p, int en_flags)
> +{
> +	__activate_task(rq, p, en_flags);
> +}
> +#endif
> +
>  void deactivate_task(struct rq *rq, struct task_struct *p, int flags)
>  {
>  	WARN_ON_ONCE(flags & DEQUEUE_SLEEP);
> @@ -3815,6 +3885,184 @@ static inline void proxy_reset_donor(struct rq *rq)
>  	resched_curr(rq);
>  }
>  
> +static inline void proxy_set_task_cpu(struct task_struct *p, int cpu)
> +{
> +	unsigned int wake_cpu;
> +
> +	/*
> +	 * Since we are enqueuing a blocked task on a cpu it may
> +	 * not be able to run on, preserve wake_cpu when we
> +	 * __set_task_cpu so we can return the task to where it
> +	 * was previously runnable.
> +	 */
> +	wake_cpu = p->wake_cpu;
> +	__set_task_cpu(p, cpu);
> +	p->wake_cpu = wake_cpu;
> +}
> +
> +static void do_activate_blocked_waiter(struct rq *target_rq, struct task_struct *p, int en_flags)
> +{
> +	struct rq_flags rf;
> +	int target_cpu = cpu_of(target_rq);
> +
> +	scoped_guard (raw_spinlock_irqsave, &p->pi_lock) {
> +		/* If task is no longer blocked, don't activate */
> +		if (!p->is_blocked)
> +			return;
> +
> +		/* Avoid racing with ttwu */
> +		if (READ_ONCE(p->__state) == TASK_WAKING)
> +			return;
> +
> +		if (READ_ONCE(p->on_rq)) {
> +			/*
> +			 * We raced with a non mutex handoff activation of p.
> +			 * That activation will also take care of activating
> +			 * all of the tasks after p in the blocked_head list,
> +			 * so we're done here.
> +			 */
> +			return;
> +		}

Is a racing activation the only possible case here? When
proxy_enqueue_on_owner() calls block_task() on a fair task that isn't
eligible, DELAY_DEQUEUE keeps it on_rq with se.sched_delayed set. In
that case p simply won't donate until it's woken by the mutex, so
nothing nasty shoudl happen, but maybe it's worth updating the comment
to describe this case as well?

> +		if (task_on_cpu(task_rq(p), p)) {
> +			/*
> +			 * Its possible this activation is very late, and
> +			 * we already were woken up and are running on a
> +			 * different cpu. If that task blocked, it could be
> +			 * dequeued (so on_rq == 0), but still on_cpu.
> +			 * Bail in this case, as we definitely don't want to
> +			 * activate a task when its on_cpu elsewhere.
> +			 */
> +			return;
> +		}
> +
> +		scoped_guard (raw_spinlock, &p->blocked_lock) {
> +			/*
> +			 * Again, if activation is delayed, it's possible the
> +			 * task has been woken and is no longer blocked_on,
> +			 * but went back to sleep, so double check blocked_on
> +			 * before activating onto the owner's rq
> +			 */
> +			if (!task_is_blocked(p))
> +				return;
> +		}
> +
> +		/*
> +		 * Have to make sure we handle nr_iowait adjustment before
> +		 * we call proxy_set_task_cpu() to ensure we are adjusting
> +		 * the same runqueue we left (where block_task()
> +		 * incremented nr_iowait).
> +		 */
> +		if (p->in_iowait) {
> +			delayacct_blkio_end(p);
> +			atomic_dec(&task_rq(p)->nr_iowait);
> +		}
> +
> +		if (task_cpu(p) != target_cpu) {
> +			en_flags |= ENQUEUE_MIGRATED;
> +			psi_ttwu_dequeue(p);
> +			proxy_set_task_cpu(p, target_cpu);
> +		}

Can this break SCHED_DEADLINE bw accounting?

p is sleeping here (not TASK_WAKING, not TASK_ON_RQ_MIGRATING), so
__set_task_cpu() skips migrate_task_rq_dl(): the old rq never does
sub_rq_bw(), while ENQUEUE_MIGRATED makes the new rq do add_rq_bw(), so
this_bw is leaked on the old rq. And if p is still dl_non_contending,
task_contending() on the new rq just cancels the inactive timer, leaving
running_bw on the old rq forever and making it underflow on the new rq
the next time p blocks.

set_task_cpu() doesn't help, because migrate_task_rq_dl() bails out
unless TASK_WAKING, so I'm not sure how to fix this case...

> +		rq_lock_irqsave(target_rq, &rf);
> +		/*
> +		 * proxy_enqueue_on_owner() called block_task() which
> +		 * increments nr_uninterruptible, so we need to reverse
> +		 * that when we activate the blocked waiter
> +		 */
> +		if (p->sched_contributes_to_load)
> +			target_rq->nr_uninterruptible--;
> +		update_rq_clock(target_rq);
> +		activate_task(target_rq, p, en_flags);
> +		resched_curr(target_rq);
> +		rq_unlock_irqrestore(target_rq, &rf);
> +	}
> +}
> +
> +static void activate_blocked_waiters(struct rq *target_rq,
> +				     struct task_struct *owner,
> +				     int wake_flags)
> +{
> +	struct list_head bal_head;
> +	unsigned long flags;
> +	int en_flags = ENQUEUE_WAKEUP | ENQUEUE_NOCLOCK;
> +
> +	if (!sched_proxy_exec())
> +		return;
> +
> +	/*
> +	 * A whole bunch of waiting donor tasks back this blocked
> +	 * lock owner task, wake them all up to give this task its
> +	 * 'fair' share.
> +	 *
> +	 * This is a little unique here and the locking is messy.
> +	 * At this point we only hold the blocked_lock, so the
> +	 * owner task may be able to run and do all sorts of
> +	 * things while we are processing the blocked_head list,
> +	 * including going back to sleep, which can cause tasks
> +	 * to be added to the owners->blocked_head while we are
> +	 * processing it!
> +	 * Thus, we pull the entire list off the owner->blocked_head
> +	 * here so that we will only process a finite amount of
> +	 * tasks. Tasks added after this will be processed by the
> +	 * future wake events.
> +	 * Even though we have pulled the list off the blocked_head
> +	 * the removed list is *still* "owned" and serialized by
> +	 * the owner->blocked_lock! As we have to serialize against
> +	 * mid-chain wakeups, who may try to remove themselves from
> +	 * the list.
> +	 */
> +	raw_spin_lock_irqsave(&owner->blocked_lock, flags);
> +	if (!list_empty(&owner->blocked_activation_node)) {
> +		raw_spin_unlock_irqrestore(&owner->blocked_lock, flags);
> +		return;
> +	}
> +
> +	if (list_empty(&owner->blocked_head)) {
> +		raw_spin_unlock_irqrestore(&owner->blocked_lock, flags);
> +		return;
> +	}
> +
> +	get_task_struct(owner);
> +	INIT_LIST_HEAD(&bal_head);
> +	list_add_tail(&owner->blocked_activation_node, &bal_head);
> +	raw_spin_unlock_irqrestore(&owner->blocked_lock, flags);
> +
> +	while (!list_empty(&bal_head)) {
> +		struct list_head tmp_head;
> +
> +		INIT_LIST_HEAD(&tmp_head);
> +		owner = list_first_entry(&bal_head, struct task_struct, blocked_activation_node);
> +
> +		raw_spin_lock_irqsave(&owner->blocked_lock, flags);
> +		list_replace_init(&owner->blocked_head, &tmp_head);
> +		list_del_init(&owner->blocked_activation_node);
> +		while (!list_empty(&tmp_head)) {
> +			struct task_struct *p;
> +
> +			p = list_first_entry(&tmp_head,
> +					     struct task_struct,
> +					     blocked_node);
> +			WARN_ON(p == owner);
> +			__proxy_remove_from_sleeping_owner(owner, p);
> +			raw_spin_unlock_irqrestore(&owner->blocked_lock, flags);
> +
> +			do_activate_blocked_waiter(target_rq, p, en_flags);
> +
> +			raw_spin_lock_irqsave(&p->blocked_lock, flags);
> +			if (list_empty(&p->blocked_activation_node)) {
> +				get_task_struct(p);
> +				list_add_tail(&p->blocked_activation_node, &bal_head);
> +			}
> +			raw_spin_unlock_irqrestore(&p->blocked_lock, flags);
> +
> +			raw_spin_lock_irqsave(&owner->blocked_lock, flags);
> +		}
> +		raw_spin_unlock_irqrestore(&owner->blocked_lock, flags);
> +		put_task_struct(owner); // put matches get prior to adding to local bal_head
> +	}
> +}
> +
> +static inline struct task_struct *proxy_resched_idle(struct rq *rq);
> +
>  /*
>   * Checks to see if task p has been proxy-migrated to another rq
>   * and needs to be returned. If so, we deactivate the task here
> @@ -3872,6 +4120,10 @@ static inline bool proxy_needs_return(struct rq *rq, struct task_struct *p)
>  {
>  	return false;
>  }
> +
> +static inline void activate_blocked_waiters(struct rq *target_rq,
> +					    struct task_struct *owner,
> +					    int wake_flags) {}
>  #endif /* CONFIG_SCHED_PROXY_EXEC */
>  
>  static void
> @@ -3945,8 +4197,10 @@ static int ttwu_runnable(struct task_struct *p, int wake_flags)
>  
>  	update_rq_clock(rq);
>  	if (p->is_blocked) {
> -		if (p->se.sched_delayed)
> +		if (p->se.sched_delayed) {
> +			proxy_remove_from_sleeping_owner(p);
>  			enqueue_task(rq, p, ENQUEUE_NOCLOCK | ENQUEUE_DELAYED);
> +		}
>  		if (proxy_needs_return(rq, p))
>  			return 0;
>  	}
> @@ -3975,13 +4229,15 @@ void sched_ttwu_pending(void *arg)
>  	update_rq_clock(rq);
>  
>  	llist_for_each_entry_safe(p, t, llist, wake_entry.llist) {
> +		int wake_flags;
>  		if (WARN_ON_ONCE(p->on_cpu))
>  			smp_cond_load_acquire(&p->on_cpu, !VAL);
>  
>  		if (WARN_ON_ONCE(task_cpu(p) != cpu_of(rq)))
>  			set_task_cpu(p, cpu_of(rq));
>  
> -		ttwu_do_activate(rq, p, p->sched_remote_wakeup ? WF_MIGRATED : 0, &rf);
> +		wake_flags = p->sched_remote_wakeup ? WF_MIGRATED : 0;
> +		ttwu_do_activate(rq, p, wake_flags, &rf);
>  	}
>  
>  	/*
> @@ -4488,6 +4744,7 @@ int try_to_wake_up(struct task_struct *p, unsigned int state, int wake_flags)
>  		ttwu_queue(p, cpu, wake_flags);
>  	}
>  out:
> +	activate_blocked_waiters(cpu_rq(task_cpu(p)), p, wake_flags);

We can get here also when ttwu_state_match() fails, e.g., a signal sent
to an owner sleeping in TASK_UNINTERRUPTIBLE. In that case the owner
never goes through select_task_rq() and task_cpu(owner) is the CPU where
it last slept, which may have gone offline in the meantime (hotplug
only migrates queued tasks I think).

Should this be done only if (success)?

Thanks,
-Andrea

Re: [PATCH v33 1/7] sched/psi: Preserve sleep-persistent PSI flags on off-CPU sleeping dequeues

[Peter Zijlstra]

On Fri, Oct 23, 2026 at 10:04:12PM +0000, John Stultz wrote:
> diff --git a/kernel/sched/stats.h b/kernel/sched/stats.h
> index ebe0a7765f98e..20820fe1021a1 100644
> --- a/kernel/sched/stats.h
> +++ b/kernel/sched/stats.h
> @@ -175,12 +175,28 @@ static inline void psi_dequeue(struct task_struct *p, int flags)
>  	 * Do nothing here.
>  	 *
>  	 * In the SCHED_PROXY_EXECUTION case we may do sleeping
> -	 * dequeues that are not followed by a task switch, so check
> -	 * TSK_ONCPU is set to ensure the task switch is imminent.
> -	 * Otherwise clear the flags as usual.
> +	 * dequeues that are not followed by a task switch. If TSK_ONCPU
> +	 * is not set (meaning we already switched away while the task
> +	 * stayed on the rq as a blocked donor), handle the sleeping
> +	 * state transition here so sleep-persistent states (TSK_MEMSTALL,
> +	 * TSK_IOWAIT) are preserved.
>  	 */
> -	if ((flags & DEQUEUE_SLEEP) && (p->psi_flags & TSK_ONCPU))
> +	if (flags & DEQUEUE_SLEEP) {
> +		int clear = TSK_RUNNING, set = 0;
> +
> +		if (p->psi_flags & TSK_ONCPU)
> +			return;
> +		if (p->se.sched_delayed)
> +			return;

Must this really be sched_delayed, that is, cannot p->is_blocked be used
here? I'm trying to push sched_delayed into fair.c if at all possible.

> +
> +		if (p->in_memstall)
> +			clear |= TSK_MEMSTALL_RUNNING;
> +		if (p->in_iowait)
> +			set |= TSK_IOWAIT;
> +
> +		psi_task_change(p, clear, set);
>  		return;
> +	}
>  
>  	/*
>  	 * When migrating a task to another CPU, clear all psi
> -- 
> 2.56.0.257.gf7497c7d27-goog
>