[PATCH] sched/proxy_exec: Limit find_proxy_task() chain depth to prevent CPU hang

[PATCH] sched/proxy_exec: Limit find_proxy_task() chain depth to prevent CPU hang

[soolaugust]

From: zhidao su <suzhidao@xiaomi.com>

find_proxy_task() follows the blocked_on chain with:

  for (p = donor; task_is_blocked(p); p = owner)

The existing WARN_ON(owner == p) only detects immediate self-loops
(a task waiting on a mutex it already owns). It does not detect
multi-task cycles: if tasks A and B form a cycle where A waits on
B's mutex and B waits on A's mutex, the chain traversal loops forever
between A and B, hanging the CPU indefinitely while holding rq->lock.

The scenario is real under PE: mutex-blocked tasks are kept on the
runqueue (try_to_block_task() with should_block=false), so both A and
B remain selectable by pick_next_task(). When A is selected as donor,
find_proxy_task() follows A->mutex_B->owner=B->mutex_A->owner=A->...
with no termination condition for cycles.

rt-mutex handles this identically with max_lock_depth (default 1024),
printing a warning and returning -EDEADLK when the chain is too deep.

Add a chain_depth counter with MAX_PROXY_CHAIN_DEPTH=64. When exceeded,
emit WARN_ONCE and call proxy_resched_idle() to schedule idle briefly,
consistent with how other unresolvable states are handled in the
function (e.g., owner migrating, curr_in_chain bailouts). This keeps
the kernel healthy without spinning; the deadlock resolution is the
caller's problem.

Tested with a built-in boot-param test (pe_cycle_test) that creates two
kthreads on CPU 0 each holding one kernel mutex while trying to acquire
the other, forming an A->B->A deadlock cycle.

With this fix:

  [  111.758150] sched/pe: proxy chain depth exceeded 64, possible deadlock cycle involving pid 120
  [  111.758150] WARNING: CPU: 0 PID: 119 at kernel/sched/core.c:7339 __schedule+0x1e6e/0x1e80
  ...
  [  112.694277] pe_cycle_test: still alive after 1s (CPU not hung)

Without this fix, an NMI watchdog (nmi_watchdog=1, watchdog_thresh=15)
fires a hard LOCKUP on CPU 0 with RIP in do_raw_spin_lock, called from
__schedule, confirming the CPU spins inside find_proxy_task() holding
rq->lock with no forward progress:

  [  109.951781] watchdog: CPU0: Watchdog detected hard LOCKUP on cpu 0
  [  109.951781] RIP: 0010:do_raw_spin_lock+0x3e/0xb0
  [  109.951781] Call Trace:
  [  109.951781]  __schedule+0x11e7/0x1e10
  [  109.951781]  schedule_preempt_disabled+0x18/0x30
  [  109.951781]  __mutex_lock+0x6f0/0xac0
  [  109.951781]  pe_test_thread_a+0x9c/0xe0

Fixes: 7de9d4f94638 ("sched: Start blocked_on chain processing in find_proxy_task()")
Signed-off-by: zhidao su <suzhidao@xiaomi.com>
---
 kernel/sched/core.c | 17 +++++++++++++++++
 1 file changed, 17 insertions(+)

diff --git a/kernel/sched/core.c b/kernel/sched/core.c
index 3f3425c6b2f2..bafb59432f7f 100644
--- a/kernel/sched/core.c
+++ b/kernel/sched/core.c
@@ -7310,6 +7310,17 @@ DEFINE_LOCK_GUARD_1(blocked_on_lock, struct blocked_on_lock,
  * Returns the task that is going to be used as execution context (the one
  * that is actually going to be run on cpu_of(rq)).
  */
+/*
+ * Limit proxy chain traversal depth to avoid infinite loops in pathological
+ * cases (e.g., A waits for B's mutex while B waits for A's mutex). The
+ * existing WARN_ON(owner == p) only catches immediate self-loops; multi-task
+ * cycles like A->B->A are not detected without a depth counter.
+ *
+ * rt-mutex uses a similar guard (max_lock_depth = 1024). We use a smaller
+ * limit since proxy chains are expected to be short in practice.
+ */
+#define MAX_PROXY_CHAIN_DEPTH	64
+
 static struct task_struct *
 find_proxy_task(struct rq *rq, struct task_struct *donor, struct rq_flags *rf)
 	__must_hold(__rq_lockp(rq))
@@ -7318,11 +7329,17 @@ find_proxy_task(struct rq *rq, struct task_struct *donor, struct rq_flags *rf)
 	struct task_struct *owner = NULL;
 	bool curr_in_chain = false;
 	int this_cpu = cpu_of(rq);
+	int chain_depth = 0;
 	struct task_struct *p;
 	int owner_cpu;
 
 	/* Follow blocked_on chain. */
 	for (p = donor; task_is_blocked(p); p = owner) {
+		if (++chain_depth > MAX_PROXY_CHAIN_DEPTH) {
+			WARN_ONCE(1, "sched/pe: proxy chain depth exceeded %d, possible deadlock cycle involving pid %d\n",
+				  MAX_PROXY_CHAIN_DEPTH, p->pid);
+			return proxy_resched_idle(rq);
+		}
 		/* copy the entire blocked_on structure */
 		raw_spin_lock(&p->blocked_lock);
 		bo = p->blocked_on;
-- 
2.43.0

Re: [PATCH] sched/proxy_exec: Limit find_proxy_task() chain depth to prevent CPU hang

[John Stultz]

On Mon, Apr 13, 2026 at 10:36 PM <soolaugust@gmail.com> wrote:
>
> From: zhidao su <suzhidao@xiaomi.com>
>
> find_proxy_task() follows the blocked_on chain with:
>
>   for (p = donor; task_is_blocked(p); p = owner)
>
> The existing WARN_ON(owner == p) only detects immediate self-loops
> (a task waiting on a mutex it already owns). It does not detect
> multi-task cycles: if tasks A and B form a cycle where A waits on
> B's mutex and B waits on A's mutex, the chain traversal loops forever
> between A and B, hanging the CPU indefinitely while holding rq->lock.
>
> The scenario is real under PE: mutex-blocked tasks are kept on the
> runqueue (try_to_block_task() with should_block=false), so both A and
> B remain selectable by pick_next_task(). When A is selected as donor,
> find_proxy_task() follows A->mutex_B->owner=B->mutex_A->owner=A->...
> with no termination condition for cycles.
>
> rt-mutex handles this identically with max_lock_depth (default 1024),
> printing a warning and returning -EDEADLK when the chain is too deep.
>
> Add a chain_depth counter with MAX_PROXY_CHAIN_DEPTH=64. When exceeded,
> emit WARN_ONCE and call proxy_resched_idle() to schedule idle briefly,
> consistent with how other unresolvable states are handled in the
> function (e.g., owner migrating, curr_in_chain bailouts). This keeps
> the kernel healthy without spinning; the deadlock resolution is the
> caller's problem.


Nice. I used a very similar change myself when debugging proxy-exec
issues in the early days of getting ww_mutexes working properly. :)


> Tested with a built-in boot-param test (pe_cycle_test) that creates two
> kthreads on CPU 0 each holding one kernel mutex while trying to acquire
> the other, forming an A->B->A deadlock cycle.
>
> With this fix:
>
>   [  111.758150] sched/pe: proxy chain depth exceeded 64, possible deadlock cycle involving pid 120
>   [  111.758150] WARNING: CPU: 0 PID: 119 at kernel/sched/core.c:7339 __schedule+0x1e6e/0x1e80
>   ...
>   [  112.694277] pe_cycle_test: still alive after 1s (CPU not hung)
>
> Without this fix, an NMI watchdog (nmi_watchdog=1, watchdog_thresh=15)
> fires a hard LOCKUP on CPU 0 with RIP in do_raw_spin_lock, called from
> __schedule, confirming the CPU spins inside find_proxy_task() holding
> rq->lock with no forward progress:
>
>   [  109.951781] watchdog: CPU0: Watchdog detected hard LOCKUP on cpu 0
>   [  109.951781] RIP: 0010:do_raw_spin_lock+0x3e/0xb0
>   [  109.951781] Call Trace:
>   [  109.951781]  __schedule+0x11e7/0x1e10
>   [  109.951781]  schedule_preempt_disabled+0x18/0x30
>   [  109.951781]  __mutex_lock+0x6f0/0xac0
>   [  109.951781]  pe_test_thread_a+0x9c/0xe0


So, I guess I'd be curious what happens without proxy-exec.

My sense if if you have a mutex lock cycle today without proxy
execution you'll just deadlock and get a similar hard LOCKUP warning.
I assume you'd get a LOCKDEP splat as well if that was enabled in
either case, no?

So I'm not sure if I see a whole lot of benefit to rescheduling idle
over and over to keep the system sort of alive when that cpu is not
going to make any progress.

A few more thoughts below...

> Fixes: 7de9d4f94638 ("sched: Start blocked_on chain processing in find_proxy_task()")
> Signed-off-by: zhidao su <suzhidao@xiaomi.com>
> ---
>  kernel/sched/core.c | 17 +++++++++++++++++
>  1 file changed, 17 insertions(+)
>
> diff --git a/kernel/sched/core.c b/kernel/sched/core.c
> index 3f3425c6b2f2..bafb59432f7f 100644
> --- a/kernel/sched/core.c
> +++ b/kernel/sched/core.c
> @@ -7310,6 +7310,17 @@ DEFINE_LOCK_GUARD_1(blocked_on_lock, struct blocked_on_lock,
>   * Returns the task that is going to be used as execution context (the one
>   * that is actually going to be run on cpu_of(rq)).
>   */
> +/*
> + * Limit proxy chain traversal depth to avoid infinite loops in pathological
> + * cases (e.g., A waits for B's mutex while B waits for A's mutex). The
> + * existing WARN_ON(owner == p) only catches immediate self-loops; multi-task
> + * cycles like A->B->A are not detected without a depth counter.
> + *
> + * rt-mutex uses a similar guard (max_lock_depth = 1024). We use a smaller
> + * limit since proxy chains are expected to be short in practice.
> + */
> +#define MAX_PROXY_CHAIN_DEPTH  64

So while we'd hope proxy chains are short in most cases, there's no
guarantee they would be different from rt-mutexes.
In fact, with rwsem support, the chains could interleave across lock
types, so I'd probably at least match the rt-mutex value.

>  static struct task_struct *
>  find_proxy_task(struct rq *rq, struct task_struct *donor, struct rq_flags *rf)
>         __must_hold(__rq_lockp(rq))
> @@ -7318,11 +7329,17 @@ find_proxy_task(struct rq *rq, struct task_struct *donor, struct rq_flags *rf)
>         struct task_struct *owner = NULL;
>         bool curr_in_chain = false;
>         int this_cpu = cpu_of(rq);
> +       int chain_depth = 0;
>         struct task_struct *p;
>         int owner_cpu;
>
>         /* Follow blocked_on chain. */
>         for (p = donor; task_is_blocked(p); p = owner) {
> +               if (++chain_depth > MAX_PROXY_CHAIN_DEPTH) {
> +                       WARN_ONCE(1, "sched/pe: proxy chain depth exceeded %d, possible deadlock cycle involving pid %d\n",
> +                                 MAX_PROXY_CHAIN_DEPTH, p->pid);
> +                       return proxy_resched_idle(rq);

So at this point the cpu is going to be stuck, as as soon as it
switches to idle, it will call back into __schedule(), select the same
donor task and and traverse the same chain, and then reschedule idle
and start again.

So it seems to me like BUG() would be more appropriate here as the cpu
is effectively deadlocked.

I guess one could deactivate the selected blocked donor task, which
would let the cpu continue to run other tasks, but the entire lock
chain would eventually get deactivated and would never be woken up, so
it would likely trip hung task warnings. So I of would lean towards
BUG() since lock cycles are a big no no (for non-ww_mutexes) and I'd
fret if you don't stop the system folks will just ignore warnings and
not really understand why things aren't working properly.

But that's just my instinct.

Anyway, thanks for the submission here! I'm excited to see more folks
working and testing with proxy-exec!

thanks
-john

Re: [PATCH] sched/proxy_exec: Limit find_proxy_task() chain depth to prevent CPU hang

[K Prateek Nayak]

Hello John, Zhidao,

On 4/21/2026 7:57 AM, John Stultz wrote:
>> With this fix:
>>
>>   [  111.758150] sched/pe: proxy chain depth exceeded 64, possible deadlock cycle involving pid 120
>>   [  111.758150] WARNING: CPU: 0 PID: 119 at kernel/sched/core.c:7339 __schedule+0x1e6e/0x1e80
>>   ...
>>   [  112.694277] pe_cycle_test: still alive after 1s (CPU not hung)
>>
>> Without this fix, an NMI watchdog (nmi_watchdog=1, watchdog_thresh=15)
>> fires a hard LOCKUP on CPU 0 with RIP in do_raw_spin_lock, called from
>> __schedule, confirming the CPU spins inside find_proxy_task() holding
>> rq->lock with no forward progress:
>>
>>   [  109.951781] watchdog: CPU0: Watchdog detected hard LOCKUP on cpu 0
>>   [  109.951781] RIP: 0010:do_raw_spin_lock+0x3e/0xb0
>>   [  109.951781] Call Trace:
>>   [  109.951781]  __schedule+0x11e7/0x1e10
>>   [  109.951781]  schedule_preempt_disabled+0x18/0x30
>>   [  109.951781]  __mutex_lock+0x6f0/0xac0
>>   [  109.951781]  pe_test_thread_a+0x9c/0xe0
> 
> 
> So, I guess I'd be curious what happens without proxy-exec.

I think you hit the hung task detector in that case since the
interruptible sleep has lingered for too long.

> 
> My sense if if you have a mutex lock cycle today without proxy
> execution you'll just deadlock and get a similar hard LOCKUP warning.
> I assume you'd get a LOCKDEP splat as well if that was enabled in
> either case, no?
> 
> So I'm not sure if I see a whole lot of benefit to rescheduling idle
> over and over to keep the system sort of alive when that cpu is not
> going to make any progress.
> 
> A few more thoughts below...
> 
>> Fixes: 7de9d4f94638 ("sched: Start blocked_on chain processing in find_proxy_task()")
>> Signed-off-by: zhidao su <suzhidao@xiaomi.com>
>> ---
>>  kernel/sched/core.c | 17 +++++++++++++++++
>>  1 file changed, 17 insertions(+)
>>
>> diff --git a/kernel/sched/core.c b/kernel/sched/core.c
>> index 3f3425c6b2f2..bafb59432f7f 100644
>> --- a/kernel/sched/core.c
>> +++ b/kernel/sched/core.c
>> @@ -7310,6 +7310,17 @@ DEFINE_LOCK_GUARD_1(blocked_on_lock, struct blocked_on_lock,
>>   * Returns the task that is going to be used as execution context (the one
>>   * that is actually going to be run on cpu_of(rq)).
>>   */
>> +/*
>> + * Limit proxy chain traversal depth to avoid infinite loops in pathological
>> + * cases (e.g., A waits for B's mutex while B waits for A's mutex). The
>> + * existing WARN_ON(owner == p) only catches immediate self-loops; multi-task
>> + * cycles like A->B->A are not detected without a depth counter.
>> + *
>> + * rt-mutex uses a similar guard (max_lock_depth = 1024). We use a smaller
>> + * limit since proxy chains are expected to be short in practice.
>> + */
>> +#define MAX_PROXY_CHAIN_DEPTH  64
> 
> So while we'd hope proxy chains are short in most cases, there's no
> guarantee they would be different from rt-mutexes.
> In fact, with rwsem support, the chains could interleave across lock
> types, so I'd probably at least match the rt-mutex value.
> 
>>  static struct task_struct *
>>  find_proxy_task(struct rq *rq, struct task_struct *donor, struct rq_flags *rf)
>>         __must_hold(__rq_lockp(rq))
>> @@ -7318,11 +7329,17 @@ find_proxy_task(struct rq *rq, struct task_struct *donor, struct rq_flags *rf)
>>         struct task_struct *owner = NULL;
>>         bool curr_in_chain = false;
>>         int this_cpu = cpu_of(rq);
>> +       int chain_depth = 0;
>>         struct task_struct *p;
>>         int owner_cpu;
>>
>>         /* Follow blocked_on chain. */
>>         for (p = donor; task_is_blocked(p); p = owner) {
>> +               if (++chain_depth > MAX_PROXY_CHAIN_DEPTH) {
>> +                       WARN_ONCE(1, "sched/pe: proxy chain depth exceeded %d, possible deadlock cycle involving pid %d\n",
>> +                                 MAX_PROXY_CHAIN_DEPTH, p->pid);
>> +                       return proxy_resched_idle(rq);
> 
> So at this point the cpu is going to be stuck, as as soon as it
> switches to idle, it will call back into __schedule(), select the same
> donor task and and traverse the same chain, and then reschedule idle
> and start again.
> 
> So it seems to me like BUG() would be more appropriate here as the cpu
> is effectively deadlocked.
> 
> I guess one could deactivate the selected blocked donor task, which
> would let the cpu continue to run other tasks, but the entire lock
> chain would eventually get deactivated and would never be woken up, so
> it would likely trip hung task warnings. So I of would lean towards
> BUG() since lock cycles are a big no no (for non-ww_mutexes) and I'd
> fret if you don't stop the system folks will just ignore warnings and
> not really understand why things aren't working properly.
> 
> But that's just my instinct.

I would second that but I can see someone having a "creative"
mutex_lock_interruptible() pattern that relies on the hung task splat
to then trigger something from userspace to selectively kill tasks.
(Insane? Yes! Possible? Also yes!)

As an alternate approach, when traversing blocked_on links, can we
start deactivating the chain if we encounter rq->donor again as owner
in find_proxy_task() loop?

That way we go back to triggering the hung task detector and if someone
has a stack that depends on it, it'll continue to work fine while also
avoiding this lockup.

Thoughts?

> 
> Anyway, thanks for the submission here! I'm excited to see more folks
> working and testing with proxy-exec!

+1. With the next batch of changes, when we hopefully drop the EXPERT
dependency, we'll probably see even wider usage and development ;-)

-- 
Thanks and Regards,
Prateek

Re: [PATCH] sched/proxy_exec: Limit find_proxy_task() chain depth to prevent CPU hang

[zhidao su]

Hello John, Prateek,

On Tue, Apr 21, 2026 at 08:43 AM +0530, K Prateek Nayak wrote:
> As an alternate approach, when traversing blocked_on links, can we
> start deactivating the chain if we encounter rq->donor again as owner
> in find_proxy_task() loop?
>
> That way we go back to triggering the hung task detector and if someone
> has a stack that depends on it, it'll continue to work fine while also
> avoiding this lockup.

Thanks for the suggestion. I've implemented and tested this approach.

On John's point about BUG(): I agree lock cycles are a serious bug,
but deactivating the donor preserves mutex_lock_interruptible()
recovery paths and avoids a hard system stop for what could be an
application-level bug. The WARN_ONCE + hung-task splat provides
sufficient visibility.

Changes from v1:
 - Replace proxy_resched_idle() with proxy_deactivate() on both the
   depth-exceeded path and the new cycle-detected path.
   proxy_resched_idle() returns rq->idle, causing __schedule() to
   immediately re-select the same donor and re-enter find_proxy_task(),
   creating a soft loop with no forward progress. (John Stultz)
 - Add owner == donor cycle detection immediately after resolving
   owner from blocked_on. This catches A->B->...->A at the first chain
   closure; no visited set needed. (Prateek Sood)
 - Raise MAX_PROXY_CHAIN_DEPTH from 64 to 1024 to match rt-mutex's
   max_lock_depth. (John Stultz)

Tested with pe_cycle_kmod (two kthreads pinned to CPU 0, each holding
one mutex and trying to acquire the other, virtme-ng, CONFIG_LOCKDEP=n):

  [  109.057659] sched/pe: deadlock cycle detected, pid 154
  [  109.057687] WARNING: CPU: 0 PID: 155 at kernel/sched/core.c:7392
                 find_proxy_task+0x.../...
  ...
  [  246.820220] INFO: task pe_cycle_A:154 blocked for more than 122 seconds.
  [  246.820238] "echo 0 > /proc/sys/kernel/hung_task_timeout_secs" disables this message.
  [  246.820358] INFO: task pe_cycle_A:154 is blocked on a mutex likely owned by task pe_cycle_B:155.
  [  246.820360] INFO: task pe_cycle_B:155 blocked for more than 122 seconds.
  [  246.820433] INFO: task pe_cycle_B:155 is blocked on a mutex likely owned by task pe_cycle_A:154.
  EXEC_DONE  (VM continued normally throughout)

cycle detection fires immediately (~1ms after deadlock forms), donor
is deactivated, hung-task detector fires after 122s as expected.

Will send v2 once this direction is confirmed.

Thanks,
zhidao su

Re: [PATCH] sched/proxy_exec: Limit find_proxy_task() chain depth to prevent CPU hang

[zhidao su]

Hello John, Prateek,

On Tue, Apr 21, 2026 at 08:43 AM +0530, K Prateek Nayak wrote:
> As an alternate approach, when traversing blocked_on links, can we
> start deactivating the chain if we encounter rq->donor again as owner
> in find_proxy_task() loop?
>
> That way we go back to triggering the hung task detector and if someone
> has a stack that depends on it, it'll continue to work fine while also
> avoiding this lockup.

Thanks for the suggestion. I've implemented and tested this approach.

On John's point about BUG(): I agree lock cycles are a serious bug,
but deactivating the donor preserves mutex_lock_interruptible()
recovery paths and avoids a hard system stop for what could be an
application-level bug. The WARN_ONCE + hung-task splat provides
sufficient visibility.

Changes from v1:
 - Replace proxy_resched_idle() with proxy_deactivate() on both the
   depth-exceeded path and the new cycle-detected path.
   proxy_resched_idle() returns rq->idle, causing __schedule() to
   immediately re-select the same donor and re-enter find_proxy_task(),
   creating a soft loop with no forward progress. (John Stultz)
 - Add owner == donor cycle detection immediately after resolving
   owner from blocked_on. This catches A->B->...->A at the first chain
   closure; no visited set needed. (K Prateek Nayak)
 - Raise MAX_PROXY_CHAIN_DEPTH from 64 to 1024 to match rt-mutex's
   max_lock_depth. (John Stultz)

Tested with pe_cycle_kmod (two kthreads pinned to CPU 0, each holding
one mutex and trying to acquire the other, virtme-ng, CONFIG_LOCKDEP=n):

  [  109.057659] sched/pe: deadlock cycle detected, pid 154
  [  109.057687] WARNING: CPU: 0 PID: 155 at kernel/sched/core.c:7392
                 find_proxy_task+0x.../...
  ...
  [  246.820220] INFO: task pe_cycle_A:154 blocked for more than 122 seconds.
  [  246.820238] "echo 0 > /proc/sys/kernel/hung_task_timeout_secs" disables this message.
  [  246.820358] INFO: task pe_cycle_A:154 is blocked on a mutex likely owned by task pe_cycle_B:155.
  [  246.820360] INFO: task pe_cycle_B:155 blocked for more than 122 seconds.
  [  246.820433] INFO: task pe_cycle_B:155 is blocked on a mutex likely owned by task pe_cycle_A:154.
  EXEC_DONE  (VM continued normally throughout)

cycle detection fires immediately (~1ms after deadlock forms), donor
is deactivated, hung-task detector fires after 122s as expected.

Will send v2 once this direction is confirmed.

Thanks,
zhidao su

[PATCH v2] sched/proxy_exec: Break cyclic proxy chains by deactivating blocked tasks

[soolaugust]

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.

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>
---

Changes from v1:
- Deactivate the blocked task instead of rescheduling idle.
- Add direct owner == donor cycle detection.
- Raise MAX_PROXY_CHAIN_DEPTH from 64 to 1024.

 kernel/sched/core.c | 17 +++++++++++++++++
 1 file changed, 17 insertions(+)

diff --git a/kernel/sched/core.c b/kernel/sched/core.c
index 2e7cde033a319..cff1a3b58660b 100644
--- a/kernel/sched/core.c
+++ b/kernel/sched/core.c
@@ -6724,6 +6724,8 @@ static bool try_to_block_task(struct rq *rq, struct task_struct *p,
 }
 
 #ifdef CONFIG_SCHED_PROXY_EXEC
+#define MAX_PROXY_CHAIN_DEPTH	1024
+
 static inline void proxy_set_task_cpu(struct task_struct *p, int cpu)
 {
 	unsigned int wake_cpu;
@@ -6873,6 +6875,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) {
@@ -6905,6 +6908,13 @@ find_proxy_task(struct rq *rq, struct task_struct *donor, struct rq_flags *rf)
 			return NULL;
 		}
 
+		if (++chain_depth > MAX_PROXY_CHAIN_DEPTH) {
+			WARN_ONCE(1, "sched/pe: proxy chain depth exceeded %d, pid %d\n",
+				  MAX_PROXY_CHAIN_DEPTH, p->pid);
+			__clear_task_blocked_on(p, NULL);
+			goto deactivate;
+		}
+
 		if (task_current(rq, p))
 			curr_in_chain = true;
 
@@ -6923,6 +6933,13 @@ find_proxy_task(struct rq *rq, struct task_struct *donor, struct rq_flags *rf)
 			goto deactivate;
 		}
 
+		if (owner == donor) {
+			WARN_ONCE(1, "sched/pe: deadlock cycle detected, pid %d\n",
+				  p->pid);
+			__clear_task_blocked_on(p, NULL);
+			goto deactivate;
+		}
+
 		if (!READ_ONCE(owner->on_rq) || owner->se.sched_delayed) {
 			/* XXX Don't handle blocked owners/delayed dequeue yet */
 			if (curr_in_chain)
-- 
2.43.0

Re: [PATCH v2] sched/proxy_exec: Break cyclic proxy chains by deactivating blocked tasks

[K Prateek Nayak]

Hello Zhidao,

On 7/14/2026 8:51 PM, soolaugust@gmail.com wrote:
> diff --git a/kernel/sched/core.c b/kernel/sched/core.c
> index 2e7cde033a319..cff1a3b58660b 100644
> --- a/kernel/sched/core.c
> +++ b/kernel/sched/core.c
> @@ -6724,6 +6724,8 @@ static bool try_to_block_task(struct rq *rq, struct task_struct *p,
>  }
>  
>  #ifdef CONFIG_SCHED_PROXY_EXEC
> +#define MAX_PROXY_CHAIN_DEPTH	1024

I'm not really a fan of the arbitrary MAX_PROXY_CHAIN_DEPTH.

> +
>  static inline void proxy_set_task_cpu(struct task_struct *p, int cpu)
>  {
>  	unsigned int wake_cpu;
> @@ -6873,6 +6875,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) {
> @@ -6905,6 +6908,13 @@ find_proxy_task(struct rq *rq, struct task_struct *donor, struct rq_flags *rf)
>  			return NULL;
>  		}
>  
> +		if (++chain_depth > MAX_PROXY_CHAIN_DEPTH) {
> +			WARN_ONCE(1, "sched/pe: proxy chain depth exceeded %d, pid %d\n",
> +				  MAX_PROXY_CHAIN_DEPTH, p->pid);
> +			__clear_task_blocked_on(p, NULL);
> +			goto deactivate;
> +		}
> +
>  		if (task_current(rq, p))
>  			curr_in_chain = true;
>  
> @@ -6923,6 +6933,13 @@ find_proxy_task(struct rq *rq, struct task_struct *donor, struct rq_flags *rf)
>  			goto deactivate;
>  		}
>  
> +		if (owner == donor) {

So let us take a step back. Say you have a genuine case of:

  A -> B -> C -> D
       ^         |
       |         |
       +---------+

  donor = A
  Cycle is somewhere in-between the chain

Now, we have a "p->blocked_donor" back link that we can probably
leverage to detect this cycle except we don't clear a
p->blocked_donor link when find_proxy_task() returns idle or NULL
so we can have stale p->blocked_donor links for queued tasks but
they are so far harmless.

Me goes and thinks ...

Since p->blocked_donor isn't used for chain migration yet, does
something like below help your deadlock case?

  (Prepared on top of tip:sched/core; Lightly tested)

diff --git a/kernel/sched/core.c b/kernel/sched/core.c
index 2e7cde033a31..fa1d9443f744 100644
--- a/kernel/sched/core.c
+++ b/kernel/sched/core.c
@@ -6874,6 +6874,9 @@ find_proxy_task(struct rq *rq, struct task_struct *donor, struct rq_flags *rf)
 	struct task_struct *p;
 	int owner_cpu;
 
+	/* Increment proxy_pick_seq such that last 4 bits are always set. */
+	rq->proxy_pick_seq += 0x10;
+
 	/* Follow blocked_on chain. */
 	for (p = donor; p->is_blocked; p = owner) {
 		/* if its PROXY_WAKING, do return migration or run if current */
@@ -6990,12 +6993,28 @@ find_proxy_task(struct rq *rq, struct task_struct *donor, struct rq_flags *rf)
 			 */
 			return proxy_resched_idle(rq);
 		}
+
+		/* Cyclic deadlock detection. */
+		if (((u64)owner->blocked_donor) & 0xF) {
+			u64 pick_seq = (u64)owner->blocked_donor;
+
+			/*
+			 * Owner was already seen during this find_proxy_task() loop.
+			 * Deactivate the task since there is a loop in proxy-chain.
+			 */
+			if (rq->proxy_pick_seq == pick_seq) {
+				__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
 		 * guarantee its existence, as per ttwu_remote().
 		 */
 		owner->blocked_donor = p;
+		p->blocked_donor = (void *)rq->proxy_pick_seq;
 	}
 	WARN_ON_ONCE(owner && !owner->on_rq);
 	return owner;
@@ -9057,6 +9076,9 @@ void __init sched_init(void)
 		raw_spin_lock_init(&rq->cpu_epoch_lock);
 		rq->cpu_epoch_next = jiffies;
 #endif
+#ifdef CONFIG_SCHED_PROXY_EXEC
+		rq->proxy_pick_seq = 0xf;
+#endif
 
 		zalloc_cpumask_var_node(&rq->scratch_mask, GFP_KERNEL, cpu_to_node(i));
 	}
diff --git a/kernel/sched/sched.h b/kernel/sched/sched.h
index 26ae13c86b69..452cbcd3a8c5 100644
--- a/kernel/sched/sched.h
+++ b/kernel/sched/sched.h
@@ -1154,6 +1154,7 @@ struct rq {
 #ifdef CONFIG_SCHED_PROXY_EXEC
 	struct task_struct __rcu	*donor;  /* Scheduling context */
 	struct task_struct __rcu	*curr;   /* Execution context */
+	u64			proxy_pick_seq;  /* find_proxy_task() seq */
 #else
 	union {
 		struct task_struct __rcu *donor; /* Scheduler context */
---
base-commit: 04998aa54848f15332202d0bea008d2ca1ed1713

This assumes task_struct pointers are 4-bytes aligned.

Only rq->curr->blocked_donor matters currently so it should be okay
to clobber the rest of the chain. If this is okay, perhaps we can
just stash the pick_seq copy in task_struct.

Thoughts?

> +			WARN_ONCE(1, "sched/pe: deadlock cycle detected, pid %d\n",
> +				  p->pid);
> +			__clear_task_blocked_on(p, NULL);
> +			goto deactivate;
> +		}
> +
>  		if (!READ_ONCE(owner->on_rq) || owner->se.sched_delayed) {
>  			/* XXX Don't handle blocked owners/delayed dequeue yet */
>  			if (curr_in_chain)

-- 
Thanks and Regards,
Prateek

Re: [PATCH v2] sched/proxy_exec: Break cyclic proxy chains by deactivating blocked tasks

[soolaugust]

Thanks Prateek.

> I'm not really a fan of the arbitrary MAX_PROXY_CHAIN_DEPTH.

Agreed. It was only a guard rail, not a real fix. I'll drop it in v3
and switch to a proper cycle check.

> This only catches cycles that come back to the original donor.

Right. The owner == donor check only catches cycles that include the
original donor, so it misses loops in the middle of the chain, like
your A -> B -> C -> D -> B example.

> Maybe we can use the blocked_donor backlink as a visited marker?

The basic idea makes sense, but I'd rather not overload blocked_donor.
That field is already the donor-stack backlink, and keeping it as a
plain task pointer seems easier to reason about as the proxy-exec model
grows to more primitives.

So for v3 I'll likely use an explicit per-pick seq marker instead.

> We should probably think about other lock types too.

Yes, agreed. That's another reason to keep this at the proxy
wait-for-chain level rather than make it mutex-specific. The current
tree still only has mutex-backed blocked_on, but the design is meant to
cover other blocking primitives as well.

Thanks for the review. I'll rework v3 accordingly.

Re: [PATCH v2] sched/proxy_exec: Break cyclic proxy chains by deactivating blocked tasks

[K Prateek Nayak]

Hello Zhidao,

On 7/15/2026 8:07 AM, soolaugust@gmail.com wrote:
> Thanks Prateek.
> 
>> I'm not really a fan of the arbitrary MAX_PROXY_CHAIN_DEPTH.
> 
> Agreed. It was only a guard rail, not a real fix. I'll drop it in v3
> and switch to a proper cycle check.
> 
>> This only catches cycles that come back to the original donor.
> 
> Right. The owner == donor check only catches cycles that include the
> original donor, so it misses loops in the middle of the chain, like
> your A -> B -> C -> D -> B example.
> 
>> Maybe we can use the blocked_donor backlink as a visited marker?
> 
> The basic idea makes sense, but I'd rather not overload blocked_donor.
> That field is already the donor-stack backlink, and keeping it as a
> plain task pointer seems easier to reason about as the proxy-exec model
> grows to more primitives.
> 
> So for v3 I'll likely use an explicit per-pick seq marker instead.

Ack! Sample code was just a PoC to see if it is good enough to solve the
hard lockup problem :-)

Btw, I realized you'll need to reset this marker on migration, else
there is a rare chance of a stale p->blocked_donor pick_seq from an old
pick CPU colliding with the pick_seq after migration.

For my PoC, this was a good enough solution:

diff --git a/kernel/sched/sched.h b/kernel/sched/sched.h
index 452cbcd3a8c5..f5180913c038 100644
--- a/kernel/sched/sched.h
+++ b/kernel/sched/sched.h
@@ -2400,6 +2400,7 @@ static inline void __set_task_cpu(struct task_struct *p, unsigned int cpu)
 	smp_wmb();
 	WRITE_ONCE(task_thread_info(p)->cpu, cpu);
 	p->wake_cpu = cpu;
+	p->blocked_donor = NULL;
 	rseq_sched_set_ids_changed(p);
 #endif /* CONFIG_SMP */
 }
---

You can make this fit as per your v3 scheme.

>> We should probably think about other lock types too.
> 
> Yes, agreed. That's another reason to keep this at the proxy
> wait-for-chain level rather than make it mutex-specific. The current
> tree still only has mutex-backed blocked_on, but the design is meant to
> cover other blocking primitives as well.

Ack! I think eventually, blocked_on becomes a struct with a lock_type
enum + void* pointer which allows for interpreting the pointer based
on the lock_type.

I agree p->blocked_donor has other uses with the extended series so it
is best to use a separate variable to track the seq_count if we go down
that route.

I'll let John comment if it is a good idea or not.

> 
> Thanks for the review. I'll rework v3 accordingly.

Thanks a ton.

-- 
Thanks and Regards,
Prateek

Re: [PATCH v2] sched/proxy_exec: Break cyclic proxy chains by deactivating blocked tasks

[zhidao su]

> Btw, I realized you'll need to reset this marker on migration, else
> there is a rare chance of a stale p->blocked_donor pick_seq from an old
> pick CPU colliding with the pick_seq after migration.

Good catch. I think v3 should clear the marker when we migrate the task,
so the pick state is only meaningful for a single walk on a single CPU.
That avoids stale state from an old CPU colliding with a later walk.

> You can make this fit as per your v3 scheme.

I’m leaning toward keeping this proxy-local instead of putting it in a
generic CPU switch helper.

> Ack! I think eventually, blocked_on becomes a struct with a lock_type
> enum + void* pointer which allows for interpreting the pointer based
> on the lock_type.

Makes sense, and that’s another reason I’d keep the walk marker separate
from the blocked_on / blocked_donor representation itself.

> I agree p->blocked_donor has other uses with the extended series so it
> is best to use a separate variable to track the seq_count if we go down
> that route.

Right, that was my thinking as well.

[PATCH v3] sched/proxy_exec: Detect cycles in proxy walks

[zhidao su (Xiaomi)]

find_proxy_task() can keep walking the same blocked_on chain if the chain
contains a cycle. This happens with a simple A->B->A mutex deadlock under
proxy execution, and can leave the CPU spinning in __schedule() with the rq
lock held.

Mark each task visited during one proxy walk with the rq's pick sequence.
If the walk sees the same task again in the same pick, break the cycle by
clearing the blocked_on state at the detection point and deactivating that
task.

Clear the marker when proxy execution migrates a blocked task, so a later
walk on another CPU cannot match stale state.

Tested with a PE cycle reproducer in virtme-ng:

  buggy kernel: vng timed out without returning
  fixed kernel: WARN_ONCE "sched/pe: deadlock cycle detected"

Signed-off-by: zhidao su (Xiaomi) <soolaugust@gmail.com>
---
Changes since v2:
- Drop the proxy-chain depth limit.
- Detect cycles anywhere in the proxy walk, not only cycles back to the
  original donor.
- Use a separate per-pick marker instead of overloading blocked_donor.
- Clear the marker on proxy-exec blocked-task migration.

 include/linux/sched.h |  4 ++++
 kernel/fork.c         |  4 ++++
 kernel/sched/core.c   | 34 ++++++++++++++++++++++++++++++++--
 kernel/sched/sched.h  |  1 +
 4 files changed, 41 insertions(+), 2 deletions(-)

diff --git a/include/linux/sched.h b/include/linux/sched.h
index 968b18a7f4702..b83a4e775d736 100644
--- a/include/linux/sched.h
+++ b/include/linux/sched.h
@@ -1256,6 +1256,10 @@ struct task_struct {
 	 * under preempt_disable().
 	 */
 	struct task_struct		*blocked_donor;
+#ifdef CONFIG_SCHED_PROXY_EXEC
+	int				proxy_pick_cpu;
+	u64				proxy_pick_seq; /* find_proxy_task() seq */
+#endif
 
 #ifdef CONFIG_DETECT_HUNG_TASK_BLOCKER
 	/*
diff --git a/kernel/fork.c b/kernel/fork.c
index 13e38e89a1f30..2219cce602c62 100644
--- a/kernel/fork.c
+++ b/kernel/fork.c
@@ -2242,6 +2242,10 @@ __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
+	p->proxy_pick_cpu = -1;
+	p->proxy_pick_seq = 0;
+#endif
 
 #ifdef CONFIG_BCACHE
 	p->sequential_io	= 0;
diff --git a/kernel/sched/core.c b/kernel/sched/core.c
index 2e7cde033a319..3db4e6c2b786a 100644
--- a/kernel/sched/core.c
+++ b/kernel/sched/core.c
@@ -6724,6 +6724,7 @@ 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;
@@ -6830,6 +6831,10 @@ static void proxy_migrate_task(struct rq *rq, struct rq_flags *rf,
 
 	deactivate_task(rq, p, DEQUEUE_NOCLOCK);
 	proxy_set_task_cpu(p, target_cpu);
+#ifdef CONFIG_SCHED_PROXY_EXEC
+	WRITE_ONCE(p->proxy_pick_cpu, -1);
+	WRITE_ONCE(p->proxy_pick_seq, 0);
+#endif
 
 	proxy_release_rq_lock(rq, rf);
 
@@ -6839,14 +6844,14 @@ static void proxy_migrate_task(struct rq *rq, struct rq_flags *rf,
 }
 
 /*
- * Find runnable lock owner to proxy for mutex blocked donor
+ * Find runnable lock owner to proxy for a blocked donor
  *
  * Follow the blocked-on relation:
  *
  *                ,-> task
  *                |     | blocked-on
  *                |     v
- *  blocked_donor |   mutex
+ *  blocked_donor | blocking primitive
  *                |     | owner
  *                |     v
  *                `-- task
@@ -6874,6 +6879,10 @@ find_proxy_task(struct rq *rq, struct task_struct *donor, struct rq_flags *rf)
 	struct task_struct *p;
 	int owner_cpu;
 
+	rq->proxy_pick_seq++;
+	if (unlikely(!rq->proxy_pick_seq))
+		rq->proxy_pick_seq++;
+
 	/* Follow blocked_on chain. */
 	for (p = donor; p->is_blocked; p = owner) {
 		/* if its PROXY_WAKING, do return migration or run if current */
@@ -6905,6 +6914,16 @@ find_proxy_task(struct rq *rq, struct task_struct *donor, struct rq_flags *rf)
 			return NULL;
 		}
 
+		if (READ_ONCE(p->proxy_pick_cpu) == this_cpu &&
+		    READ_ONCE(p->proxy_pick_seq) == rq->proxy_pick_seq) {
+			WARN_ONCE(1, "sched/pe: deadlock cycle detected, pid %d\n",
+				  p->pid);
+			__clear_task_blocked_on(p, NULL);
+			goto deactivate;
+		}
+		WRITE_ONCE(p->proxy_pick_cpu, this_cpu);
+		WRITE_ONCE(p->proxy_pick_seq, rq->proxy_pick_seq);
+
 		if (task_current(rq, p))
 			curr_in_chain = true;
 
@@ -6990,6 +7009,14 @@ find_proxy_task(struct rq *rq, struct task_struct *donor, struct rq_flags *rf)
 			 */
 			return proxy_resched_idle(rq);
 		}
+
+		if (READ_ONCE(owner->proxy_pick_cpu) == this_cpu &&
+		    READ_ONCE(owner->proxy_pick_seq) == rq->proxy_pick_seq) {
+			WARN_ONCE(1, "sched/pe: deadlock cycle detected, pid %d\n",
+				  p->pid);
+			__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
@@ -9057,6 +9084,9 @@ void __init sched_init(void)
 		raw_spin_lock_init(&rq->cpu_epoch_lock);
 		rq->cpu_epoch_next = jiffies;
 #endif
+#ifdef CONFIG_SCHED_PROXY_EXEC
+		rq->proxy_pick_seq = 0;
+#endif
 
 		zalloc_cpumask_var_node(&rq->scratch_mask, GFP_KERNEL, cpu_to_node(i));
 	}
diff --git a/kernel/sched/sched.h b/kernel/sched/sched.h
index 26ae13c86b699..f63c024d160e8 100644
--- a/kernel/sched/sched.h
+++ b/kernel/sched/sched.h
@@ -1154,6 +1154,7 @@ struct rq {
 #ifdef CONFIG_SCHED_PROXY_EXEC
 	struct task_struct __rcu	*donor;  /* Scheduling context */
 	struct task_struct __rcu	*curr;   /* Execution context */
+	u64				proxy_pick_seq;  /* find_proxy_task() seq */
 #else
 	union {
 		struct task_struct __rcu *donor; /* Scheduler context */

base-commit: 04998aa54848f15332202d0bea008d2ca1ed1713
-- 
2.43.0

Re: [PATCH v3] sched/proxy_exec: Detect cycles in proxy walks

[K Prateek Nayak]

Hello Zhidao,

On 7/17/2026 4:22 PM, zhidao su (Xiaomi) wrote:
> find_proxy_task() can keep walking the same blocked_on chain if the chain
> contains a cycle. This happens with a simple A->B->A mutex deadlock under
> proxy execution, and can leave the CPU spinning in __schedule() with the rq
> lock held.
> 
> Mark each task visited during one proxy walk with the rq's pick sequence.
> If the walk sees the same task again in the same pick, break the cycle by
> clearing the blocked_on state at the detection point and deactivating that
> task.
> 
> Clear the marker when proxy execution migrates a blocked task, so a later
> walk on another CPU cannot match stale state.
> 
> Tested with a PE cycle reproducer in virtme-ng:
> 
>   buggy kernel: vng timed out without returning
>   fixed kernel: WARN_ONCE "sched/pe: deadlock cycle detected"
> 
> Signed-off-by: zhidao su (Xiaomi) <soolaugust@gmail.com>
> ---
> Changes since v2:
> - Drop the proxy-chain depth limit.
> - Detect cycles anywhere in the proxy walk, not only cycles back to the
>   original donor.
> - Use a separate per-pick marker instead of overloading blocked_donor.
> - Clear the marker on proxy-exec blocked-task migration.
> 
>  include/linux/sched.h |  4 ++++
>  kernel/fork.c         |  4 ++++
>  kernel/sched/core.c   | 34 ++++++++++++++++++++++++++++++++--
>  kernel/sched/sched.h  |  1 +
>  4 files changed, 41 insertions(+), 2 deletions(-)
> 
> diff --git a/include/linux/sched.h b/include/linux/sched.h
> index 968b18a7f4702..b83a4e775d736 100644
> --- a/include/linux/sched.h
> +++ b/include/linux/sched.h
> @@ -1256,6 +1256,10 @@ struct task_struct {
>  	 * under preempt_disable().
>  	 */
>  	struct task_struct		*blocked_donor;
> +#ifdef CONFIG_SCHED_PROXY_EXEC
> +	int				proxy_pick_cpu;

This adds 8-bytes to task_struct for not much benefit.

I think resetting proxy_pick_seq on migration / enqueue is much
simpler than tracking 2 things. Not to mention you need to write to
"proxy_pick_cpu" at every iteration and compare it too.

> +	u64				proxy_pick_seq; /* find_proxy_task() seq */
> +#endif
>  
>  #ifdef CONFIG_DETECT_HUNG_TASK_BLOCKER
>  	/*
> diff --git a/kernel/fork.c b/kernel/fork.c
> index 13e38e89a1f30..2219cce602c62 100644
> --- a/kernel/fork.c
> +++ b/kernel/fork.c
> @@ -2242,6 +2242,10 @@ __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
> +	p->proxy_pick_cpu = -1;
> +	p->proxy_pick_seq = 0;

It should be okay to inherit these values from parent. The task
still needs to be placed after the fork which grabs the rq_lock
and next pick would increment the seq number anyways.

> +#endif
>  
>  #ifdef CONFIG_BCACHE
>  	p->sequential_io	= 0;
> diff --git a/kernel/sched/core.c b/kernel/sched/core.c
> index 2e7cde033a319..3db4e6c2b786a 100644
> --- a/kernel/sched/core.c
> +++ b/kernel/sched/core.c
> @@ -6724,6 +6724,7 @@ 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;
> @@ -6830,6 +6831,10 @@ static void proxy_migrate_task(struct rq *rq, struct rq_flags *rf,
>  
>  	deactivate_task(rq, p, DEQUEUE_NOCLOCK);
>  	proxy_set_task_cpu(p, target_cpu);
> +#ifdef CONFIG_SCHED_PROXY_EXEC
> +	WRITE_ONCE(p->proxy_pick_cpu, -1);
> +	WRITE_ONCE(p->proxy_pick_seq, 0);
> +#endif
>  
>  	proxy_release_rq_lock(rq, rf);
>  
> @@ -6839,14 +6844,14 @@ static void proxy_migrate_task(struct rq *rq, struct rq_flags *rf,
>  }
>  
>  /*
> - * Find runnable lock owner to proxy for mutex blocked donor
> + * Find runnable lock owner to proxy for a blocked donor
>   *
>   * Follow the blocked-on relation:
>   *
>   *                ,-> task
>   *                |     | blocked-on
>   *                |     v
> - *  blocked_donor |   mutex
> + *  blocked_donor | blocking primitive
>   *                |     | owner
>   *                |     v
>   *                `-- task
> @@ -6874,6 +6879,10 @@ find_proxy_task(struct rq *rq, struct task_struct *donor, struct rq_flags *rf)
>  	struct task_struct *p;
>  	int owner_cpu;
>  
> +	rq->proxy_pick_seq++;
> +	if (unlikely(!rq->proxy_pick_seq))
> +		rq->proxy_pick_seq++;

Can't we simply initialize "rq->proxy_pick_seq" to 1 in sched_init()?
I don't think we need to worry about a u64 wraparound.

> +
>  	/* Follow blocked_on chain. */
>  	for (p = donor; p->is_blocked; p = owner) {
>  		/* if its PROXY_WAKING, do return migration or run if current */
> @@ -6905,6 +6914,16 @@ find_proxy_task(struct rq *rq, struct task_struct *donor, struct rq_flags *rf)
>  			return NULL;
>  		}
>  
> +		if (READ_ONCE(p->proxy_pick_cpu) == this_cpu &&
> +		    READ_ONCE(p->proxy_pick_seq) == rq->proxy_pick_seq) {
> +			WARN_ONCE(1, "sched/pe: deadlock cycle detected, pid %d\n",
> +				  p->pid);
> +			__clear_task_blocked_on(p, NULL);
> +			goto deactivate;
> +		}
> +		WRITE_ONCE(p->proxy_pick_cpu, this_cpu);
> +		WRITE_ONCE(p->proxy_pick_seq, rq->proxy_pick_seq);
> +

Why do we need READ_ONCE() / WRITE_ONCE()?

All the checks happen on the same CPU under rq_lock. There is no chance
of a concurrent update here. Any time we drop the lock, we do a re-pick
and that should be sufficient to prevent any collision.

>  		if (task_current(rq, p))
>  			curr_in_chain = true;
>  
> @@ -6990,6 +7009,14 @@ find_proxy_task(struct rq *rq, struct task_struct *donor, struct rq_flags *rf)
>  			 */
>  			return proxy_resched_idle(rq);
>  		}
> +
> +		if (READ_ONCE(owner->proxy_pick_cpu) == this_cpu &&
> +		    READ_ONCE(owner->proxy_pick_seq) == rq->proxy_pick_seq) {
> +			WARN_ONCE(1, "sched/pe: deadlock cycle detected, pid %d\n",
> +				  p->pid);
> +			__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
> @@ -9057,6 +9084,9 @@ void __init sched_init(void)
>  		raw_spin_lock_init(&rq->cpu_epoch_lock);
>  		rq->cpu_epoch_next = jiffies;
>  #endif
> +#ifdef CONFIG_SCHED_PROXY_EXEC
> +		rq->proxy_pick_seq = 0;
> +#endif
>  
>  		zalloc_cpumask_var_node(&rq->scratch_mask, GFP_KERNEL, cpu_to_node(i));
>  	}
> diff --git a/kernel/sched/sched.h b/kernel/sched/sched.h
> index 26ae13c86b699..f63c024d160e8 100644
> --- a/kernel/sched/sched.h
> +++ b/kernel/sched/sched.h
> @@ -1154,6 +1154,7 @@ struct rq {
>  #ifdef CONFIG_SCHED_PROXY_EXEC
>  	struct task_struct __rcu	*donor;  /* Scheduling context */
>  	struct task_struct __rcu	*curr;   /* Execution context */
> +	u64				proxy_pick_seq;  /* find_proxy_task() seq */
>  #else
>  	union {
>  		struct task_struct __rcu *donor; /* Scheduler context */
> 
> base-commit: 04998aa54848f15332202d0bea008d2ca1ed1713

-- 
Thanks and Regards,
Prateek

[PATCH v4] sched/proxy_exec: Detect cycles in proxy walks

[zhidao su (Xiaomi)]

find_proxy_task() can keep walking the same blocked_on chain if the chain
contains a cycle. This happens with a simple A->B->A mutex deadlock under
proxy execution, and can leave the CPU spinning in __schedule() with the rq
lock held.

Use the rq pick sequence as a per-walk marker. Mark each task visited by
the current proxy walk. If the walk sees the same marker again, break the
cycle by clearing the blocked_on state at the detection point and
deactivating that task.

The marker is only consumed while holding the rq lock. Clear it when a task
is activated, so stale state from an earlier pick or another rq is not
carried into the next queued lifetime.

Tested with a PE cycle reproducer in virtme-ng:

  buggy kernel: vng timed out without returning
  fixed kernel: WARN_ONCE "sched/pe: deadlock cycle detected"

Signed-off-by: zhidao su (Xiaomi) <soolaugust@gmail.com>
---
Changes since v3:
- Use a single per-task proxy_pick_seq marker instead of storing both CPU
  and sequence.
- Clear stale proxy-walk state from activate_task() rather than from the
  proxy migration path only.
- Drop fork-time marker initialization.
- Drop READ_ONCE()/WRITE_ONCE() around marker accesses; the walk is under
  rq lock.
- Drop the u64 wraparound guard.

 include/linux/sched.h |  3 +++
 kernel/sched/core.c   | 28 ++++++++++++++++++++++++++--
 kernel/sched/sched.h  |  1 +
 3 files changed, 30 insertions(+), 2 deletions(-)

diff --git a/include/linux/sched.h b/include/linux/sched.h
index 968b18a7f4702..b1c46e21bc268 100644
--- a/include/linux/sched.h
+++ b/include/linux/sched.h
@@ -1256,6 +1256,9 @@ struct task_struct {
 	 * under preempt_disable().
 	 */
 	struct task_struct		*blocked_donor;
+#ifdef CONFIG_SCHED_PROXY_EXEC
+	u64				proxy_pick_seq;
+#endif
 
 #ifdef CONFIG_DETECT_HUNG_TASK_BLOCKER
 	/*
diff --git a/kernel/sched/core.c b/kernel/sched/core.c
index 2e7cde033a319..1a9d3decd66e0 100644
--- a/kernel/sched/core.c
+++ b/kernel/sched/core.c
@@ -2221,6 +2221,9 @@ void activate_task(struct rq *rq, struct task_struct *p, int flags)
 	if (task_on_rq_migrating(p))
 		flags |= ENQUEUE_MIGRATED;
 
+#ifdef CONFIG_SCHED_PROXY_EXEC
+	p->proxy_pick_seq = 0;
+#endif
 	enqueue_task(rq, p, flags);
 
 	WRITE_ONCE(p->on_rq, TASK_ON_RQ_QUEUED);
@@ -6724,6 +6727,7 @@ 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;
@@ -6839,14 +6843,14 @@ static void proxy_migrate_task(struct rq *rq, struct rq_flags *rf,
 }
 
 /*
- * Find runnable lock owner to proxy for mutex blocked donor
+ * Find runnable lock owner to proxy for a blocked donor
  *
  * Follow the blocked-on relation:
  *
  *                ,-> task
  *                |     | blocked-on
  *                |     v
- *  blocked_donor |   mutex
+ *  blocked_donor | blocking primitive
  *                |     | owner
  *                |     v
  *                `-- task
@@ -6874,6 +6878,8 @@ find_proxy_task(struct rq *rq, struct task_struct *donor, struct rq_flags *rf)
 	struct task_struct *p;
 	int owner_cpu;
 
+	rq->proxy_pick_seq++;
+
 	/* Follow blocked_on chain. */
 	for (p = donor; p->is_blocked; p = owner) {
 		/* if its PROXY_WAKING, do return migration or run if current */
@@ -6905,6 +6911,14 @@ find_proxy_task(struct rq *rq, struct task_struct *donor, struct rq_flags *rf)
 			return NULL;
 		}
 
+		if (p->proxy_pick_seq == rq->proxy_pick_seq) {
+			WARN_ONCE(1, "sched/pe: deadlock cycle detected, pid %d\n",
+				  p->pid);
+			__clear_task_blocked_on(p, NULL);
+			goto deactivate;
+		}
+		p->proxy_pick_seq = rq->proxy_pick_seq;
+
 		if (task_current(rq, p))
 			curr_in_chain = true;
 
@@ -6990,6 +7004,13 @@ find_proxy_task(struct rq *rq, struct task_struct *donor, struct rq_flags *rf)
 			 */
 			return proxy_resched_idle(rq);
 		}
+
+		if (owner->proxy_pick_seq == rq->proxy_pick_seq) {
+			WARN_ONCE(1, "sched/pe: deadlock cycle detected, pid %d\n",
+				  p->pid);
+			__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
@@ -9057,6 +9078,9 @@ void __init sched_init(void)
 		raw_spin_lock_init(&rq->cpu_epoch_lock);
 		rq->cpu_epoch_next = jiffies;
 #endif
+#ifdef CONFIG_SCHED_PROXY_EXEC
+		rq->proxy_pick_seq = 1;
+#endif
 
 		zalloc_cpumask_var_node(&rq->scratch_mask, GFP_KERNEL, cpu_to_node(i));
 	}
diff --git a/kernel/sched/sched.h b/kernel/sched/sched.h
index 26ae13c86b699..26d8d2788e0cd 100644
--- a/kernel/sched/sched.h
+++ b/kernel/sched/sched.h
@@ -1154,6 +1154,7 @@ struct rq {
 #ifdef CONFIG_SCHED_PROXY_EXEC
 	struct task_struct __rcu	*donor;  /* Scheduling context */
 	struct task_struct __rcu	*curr;   /* Execution context */
+	u64				proxy_pick_seq;
 #else
 	union {
 		struct task_struct __rcu *donor; /* Scheduler context */

base-commit: 04998aa54848f15332202d0bea008d2ca1ed1713
-- 
2.43.0