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@xxxxxxx> wrote:
>
> On 9/22/2026 10:56 AM, John Stultz wrote:
> > On Mon, Sep 14, 2026 at 9:55 AM Hui Su <sh_def@xxxxxxx> 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@xxxxxxx>
> >
> > 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@xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx/)
> 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