[RFC PATCH 0/1] sched/proxy_exec: detect cycles without persistent walk state

[RFC PATCH 0/1] sched/proxy_exec: detect cycles without persistent walk state

[Hui Su]

Proxy execution follows blocked_on relationships to find a runnable lock
owner. If that relationship contains a cycle, find_proxy_task() can loop
indefinitely while holding rq->lock.

Zhidao Su's v5 detects repetition with sequence state in task_struct and
struct rq, and resets the task marker on activation. This RFC explores a
different trade-off: keep cycle-detection state local to the real owner walk
without adding persistent task or runqueue state.

The patch applies Brent's checkpoint algorithm directly to the existing owner
walk. Cycle detection reuses the owner resolution already performed by the
real walk and does not add a separate preflight traversal. The existing
owner == p wakeup-race handling remains ahead of cycle detection because that
state does not by itself prove a deadlock cycle.

The Online Brent walk can temporarily install a blocked_donor cycle before
the delayed checkpoint detection point.

I also tested the lifetime of this transient state. In the natural recovery
path, a cycle member selected to run reached its subsequent mutex_unlock()
with blocked_donor already cleared. As a defense-in-depth check, a
validation-only forced-stale test restored a stale blocked_donor immediately
before mutex_unlock(); the existing blocked_on revalidation rejected that
handoff.

This does not prove every possible scheduling interleaving, but no
blocked_donor chain reader was found in the tested tree, and the tested
recovery path did not expose the transient backlink to normal mutex handoff.
Whether allowing that transient state while rq->lock is held is preferable
to persistent visitation state is the main design question for this RFC.

For comparison, Zhidao Su's v5 patch is available at:

https://lore.kernel.org/r/20260722120346.93000-1-soolaugust@gmail.com/

Both implementations were tested as one commit above the same base
revision, with the same x86_64 configuration, compiler, staged testcase
module, SSH initramfs, KVM setup, 2048 MiB guest memory, four vCPUs, and host
CPU affinity 8-11. The timing hook surrounds only find_proxy_task(),
accumulates per-CPU counters, and dumps once after each testcase. No
per-edge printk or atomic counter is used.

The following are medians from five fresh acyclic runs. ns/call is calculated
per run before selecting the median:

        depth   v5 ns/call   Online Brent ns/call   Online/v5
        -----   ----------   --------------------   ----------
        16      500          442                    0.884
        32      584          612                    1.048
        64      1314         988                    0.752
        128     2276         1942                   0.853
        256     4561         4815                   1.056
        512     9338         8396                   0.899
        1024    26551        25507                  0.961

The 16-64 entries are included for completeness; fixed per-call and guest
scheduling noise is more visible at those depths. Across these deeper
acyclic walks, Online Brent and the sequence-marker implementation show
comparable find_proxy_task() cost. These measurements are not intended to
claim a performance improvement for Online Brent; they show that keeping
Brent state in the real owner walk does not add a second owner traversal.

Cycle testing covered 33 topologies per implementation, including A -> B ->
A, A -> B -> C -> A, D -> A -> B -> C -> A, D0 -> D1 -> A -> B -> C -> A,
root cycle lengths through 513 with power-of-two boundaries, and tail lengths
1 and 5 with selected cycle lengths. Each topology was run in a fresh guest.
All 66 cases returned successfully and emitted exactly one cycle warning.
Saved dmesg logs include blocked_donor dumps. This build did not include a
per-edge cycle counter, so these results establish detection and progress,
not an exact first-closing-edge count.

Additional validation included Brent power-of-two boundaries, acyclic chains
through depth 1024, repeated task/mutex reuse, and a KCSAN + lockdep build.
The synthetic mutexes used to construct deliberate dependency cycles were
assigned no-validate lockdep classes so that those test dependencies did not
disable lockdep before the scheduler paths were exercised. No
Online-Brent-specific KCSAN report or scheduler lock-order failure was
observed.

The Online Brent patch changes one file with 19 implementation lines. Unlike
v5, it adds no task_struct or rq fields and needs no activation-time marker
reset.

A hard bound on proxy-walk length is intentionally left separate from this
cycle detector. In particular, should we also add an independent bound of
1024 owner transitions, matching the rt-mutex maximum lock depth, for
pathological acyclic or late-detected proxy-futex dependency graphs? Depth
exhaustion does not itself prove a cycle, so the recovery policy for such a
bound is orthogonal to cycle detection and is left for discussion.

The implementation diff in this message-only reroll is identical to the
Online Brent implementation used for the measurements; only commit-message
and cover-letter text changed after testing.

The open design question is whether avoiding persistent task/rq state and its
activation lifecycle is worth accepting the temporary blocked_donor cycle
window in the single-pass Online Brent walk.

Hui Su (1):
  sched/proxy_exec: detect cycles in proxy walks

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


base-commit: 2f0c1cf72f4682178506f513bbf015e591b1aa4a
-- 
2.55.0

[RFC PATCH 1/1] sched/proxy_exec: detect cycles in proxy walks

[Hui Su]

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>
---
 kernel/sched/core.c | 19 +++++++++++++++++++
 1 file changed, 19 insertions(+)

diff --git a/kernel/sched/core.c b/kernel/sched/core.c
index b998ef6b87af..debf313ed9fd 100644
--- a/kernel/sched/core.c
+++ b/kernel/sched/core.c
@@ -6914,6 +6914,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;
@@ -6921,6 +6924,13 @@ 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) {
+		/* 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 */
 		struct mutex *mutex = p->blocked_on;
 		if (!mutex) {
@@ -7035,6 +7045,15 @@ find_proxy_task(struct rq *rq, struct task_struct *donor, struct rq_flags *rf)
 			 */
 			return proxy_resched_idle(rq);
 		}
+
+		cycle_span++;
+		if (owner == cycle_checkpoint) {
+			pr_warn_once("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
-- 
2.55.0

Re: [RFC PATCH 0/1] sched/proxy_exec: detect cycles without persistent walk state

[Hui Su]

> The open design question is whether avoiding persistent task/rq state and its
> activation lifecycle is worth accepting the temporary blocked_donor cycle
> window in the single-pass Online Brent walk.

I did some follow-up validation of the unchanged Online Brent patch on
tip/sched/core at e81ee0630837.

One relevant change since the base used for the original measurements is:

	772d9ffbfd26 ("sched: Migrate whole chain in proxy_migrate_task()")

proxy_migrate_task() now walks p->blocked_donor directly, so this seemed
like the most important current consumer against which to test the temporary
backlink cycle mentioned in the RFC.

I added validation-only, read-only instrumentation at
proxy_migrate_task() entry.  It inspected the already-built backlink prefix
but did not repair, truncate, or otherwise change the production migration
path.

The validation on that tip revision included cross-CPU/multi-hop cycle cases, long
acyclic chains, repeated reuse of the same task/mutex objects, and KCSAN
runs.  Some representative results were:

  - an acyclic depth-1024 case completed 2921/2921 observed whole-chain
    migrations, reaching a maximum backlink prefix of 1016 tasks;

  - curr_in_chain/current-task protection was exercised 959 times in that
    run, with no current task entering the migration prefix;

  - the same task/mutex objects were reused for 100 rounds while affinity
    changes forced remote-owner placement; 226/226 observed proxy migrations
    completed;

  - across the observed migration entries I saw no backlink cycle, duplicate
    task, wrong-rq task, or off-rq task;

  - the clean RFC kernel, without the observer, also completed the
    representative cycle cases, and a clean KCSAN build completed a
    tail-plus-cycle case and 100 repeated cycle/recovery rounds without a KCSAN
    report or fatal scheduler diagnostic.

This does not prove every possible owner-change interleaving, but in the
tested paths I did not observe the temporary backlink cycle caused by delayed
Brent detection escaping into the current whole-chain blocked_donor
consumer.

The control-flow argument also looks consistent with those results: before a
remote-owner migration, find_proxy_task() has not installed the backlink for
that owner edge, so proxy_migrate_task() sees the finite prefix already
constructed from the current donor.  Once a local backlink cycle can close,
those owners have already passed the same-rq validation while rq->lock is
held.

There is also a state-lifetime property of this approach that I think is
worth considering as PE evolves.

The Brent state:

	checkpoint / power / span

belongs entirely to one find_proxy_task() invocation.  In other words, the
lifetime of the cycle-detection state matches the lifetime of the owner walk
that consumes it.  Task activation, migration, or later reactivation
therefore do not have to carry or reset detector state.

I have not tested this RFC on top of the sleeping-owner, rwsem, or futex
series; the point here is about the ownership and lifetime of the
cycle-detection state rather than a compatibility claim for those patches.

The same separation applies at the owner-resolution boundary.  As long as a
blocking primitive exposes or resolves one dependency step to at most one
task owner, e.g.

	mutex -----------\
	rwsem writer -----+--> task owner
	futex ------------/

the detector still only sees a task-to-task walk and does not need to know
which primitive supplied the edge.

So the useful property here is that lock-specific owner resolution,
task/rq lifecycle, and cycle-detection state remain separate.

There is also a clear limit to this abstraction: Brent assumes one successor
per step.  If PE eventually models and traverses multiple rwsem readers as
dependency owners, the walk becomes a branching graph and cycle detection
would need to be reconsidered together with that traversal model.

The cost remains the one described in the RFC: detection can occur later
than the first repeated owner, and the walk can temporarily close a
blocked_donor cycle.  The current-tip testing above was intended to exercise
that cost against the whole-chain blocked_donor consumer now present in
proxy_migrate_task().

The RFC implementation itself did not need any changes after this
validation, so I do not plan to respin it just for the additional test
results.

At this point, the main question I would appreciate feedback on is whether
this trade-off -- invocation-local detector state in exchange for delayed
detection and the transient backlink window -- is reasonable for this path.

Thanks,
Hui

Re: [RFC PATCH 1/1] sched/proxy_exec: detect cycles in proxy walks

[John Stultz]

On Mon, Sep 14, 2026 at 9:55 AM Hui Su <sh_def@163.com> wrote:
>
> 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>

Hey! Thanks for sending this out and apologies for my slow response to
your patches.

This looks interesting, and with Suleiman's futex work, it becomes
more critical to include.

I think similar to what Peter already mentioned, having a max depth
counter is probably still a good idea, but it does seem like this
would catch smaller cycles earlier without much overhead.

I've included an simplified version of Zhidao Su's earlier work (using
a fixed MAX_PROXY_CHAIN_DEPTH) in my tree, but will include this as
well as an potential optimization.

thanks
-john

Re: [RFC PATCH 1/1] sched/proxy_exec: detect cycles in proxy walks

[K Prateek Nayak]

On 9/22/2026 10:56 AM, John Stultz wrote:
> On Mon, Sep 14, 2026 at 9:55 AM Hui Su <sh_def@163.com> wrote:
>>
>> 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>
> 
> Hey! Thanks for sending this out and apologies for my slow response to
> your patches.
> 
> This looks interesting, and with Suleiman's futex work, it becomes
> more critical to include.
> 
> I think similar to what Peter already mentioned, having a max depth
> counter is probably still a good idea, but it does seem like this
> would catch smaller cycles earlier without much overhead.
> 
> I've included an simplified version of Zhidao Su's earlier work (using
> a fixed MAX_PROXY_CHAIN_DEPTH) in my tree, but will include this as
> well as an potential optimization.

So if we are eventually planning on returning -EDEADLK to userspace
(context: https://lore.kernel.org/lkml/20260917153649.GK4121339@noisy.programming.kicks-ass.net/)
do we care where the chain starts or can we return -EDEADLK anywhere
in the chain?

I think Brent checkpoint first converges to some point in the chain
and then requires additional traversal to find the beginning of the
chain. Is that fine?

-- 
Thanks and Regards,
Prateek

Re: [RFC PATCH 1/1] sched/proxy_exec: detect cycles in proxy walks

[John Stultz]

On Mon, Sep 21, 2026 at 10:48 PM K Prateek Nayak <kprateek.nayak@amd.com> wrote:
>
> On 9/22/2026 10:56 AM, John Stultz wrote:
> > On Mon, Sep 14, 2026 at 9:55 AM Hui Su <sh_def@163.com> wrote:
> >>
> >> 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>
> >
> > Hey! Thanks for sending this out and apologies for my slow response to
> > your patches.
> >
> > This looks interesting, and with Suleiman's futex work, it becomes
> > more critical to include.
> >
> > I think similar to what Peter already mentioned, having a max depth
> > counter is probably still a good idea, but it does seem like this
> > would catch smaller cycles earlier without much overhead.
> >
> > I've included an simplified version of Zhidao Su's earlier work (using
> > a fixed MAX_PROXY_CHAIN_DEPTH) in my tree, but will include this as
> > well as an potential optimization.
>
> So if we are eventually planning on returning -EDEADLK to userspace
> (context: https://lore.kernel.org/lkml/20260917153649.GK4121339@noisy.programming.kicks-ass.net/)
> do we care where the chain starts or can we return -EDEADLK anywhere
> in the chain?

So returning EDEADLK to userland seems like a new feature to me, as I
don't believe existing futexes (which can still have dependency cycles
or just ABA style usage) currently do this.

So I'm mostly focused on ensuring we have the same behavior first.
Where we deactivate the tasks in the cycle so we don't burn cputime on
the loop and the userland application will see the same behavior as
they do with normal futexes (get descheduled and just never come
back).

From there, my initial thinking is: we could change the logic so that
when we detect a cycle (or the max chain depth), we re-walk the chain
marking tasks with a deadlocked bit, and then wake the tasks. Then in
the futex lock loop, when we wake, we can check the deadlock bit and
return EDADLK to userland. While in-kernel locks are always deeper in
the lock order, and aren't allowed to have cycles, we shouldn't have
to worry about them in a cycle chain. However, if we did trip it due
to a driver with bad locking, we could still use the deactivation
approach based on the type.

That way we don't have to add overhead of walking the chain at block
time. But admittedly this is fairly handwavy right now.

thanks
-john

Re: [RFC PATCH 1/1] sched/proxy_exec: detect cycles in proxy walks

[Peter Zijlstra]

On Mon, Sep 21, 2026 at 11:06:52PM -0700, John Stultz wrote:

> > So if we are eventually planning on returning -EDEADLK to userspace
> > (context: https://lore.kernel.org/lkml/20260917153649.GK4121339@noisy.programming.kicks-ass.net/)
> > do we care where the chain starts or can we return -EDEADLK anywhere
> > in the chain?
> 
> So returning EDEADLK to userland seems like a new feature to me, as I
> don't believe existing futexes (which can still have dependency cycles
> or just ABA style usage) currently do this.

  git grep -e DEADLK -e DEADLOCK kernel/{futex,locking}

We definitely return -EDEADLK for PI futexes and rt_mutex. And given the
whole proxy thing hard relies on the block graph being acyclic, it
seems rather mandatory we enforce this before exposing it to userspace.