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

[John Stultz]

On Wed, Jul 22, 2026 at 5:03 AM zhidao su (Xiaomi) <soolaugust@xxxxxxxxx> wrote:
>
> find_proxy_task() can keep walking the same blocked_on chain if the chain
> contains a cycle. A simple A->B->A deadlock can leave the CPU spinning in
> __schedule() with rq->lock held.
>
> Use the rq pick sequence as a per-walk marker. Mark each task visited by
> the current walk. If the walk sees the same marker again, break the cycle
> by clearing blocked_on at the detection point and deactivating that task.
>
> The marker is only consumed while holding 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"
>
> Reviewed-by: K Prateek Nayak <kprateek.nayak@xxxxxxx>
> Signed-off-by: zhidao su (Xiaomi) <soolaugust@xxxxxxxxx>

Hey! Zhidao,
  Sorry for not having responded on this for awhile. In part its
because I'm still maybe partial to the simplicity of the
MAX_PROXY_CHAIN_DEPTH appraoch (no structure additions to task or rq
needed!).

But I also trust K Prateek's taste more then my own, so I've sort of
backed off to see what takes shape here.

I've not seen the cycle detection as super urgent, as mutex lock
cycles are not currently allowable in-kernel, and while the behavior
in this problematic case does shift with proxy (system hang vs task
stalls), it didn't seem like this was an actual problem except for
problematic out of tree drivers.   That said, now that Suleiman has a
first draft for proxy-enabled futexes, this definitely raises the
urgency, as userland would be controlling the locking, so cycle
detection would be critical.

So I'm definitely eager to see this move forward.  Though I still
think a simple (++count > MAX_PROXY_CHAIN_DEPTH) check would be
simpler and just as effective.

One small thought below..

> @@ -6990,6 +6994,14 @@ 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) {
> +                       pr_warn_once("sched/pe: deadlock cycle detected, pid %d\n",
> +                                    p->pid);
> +                       __clear_task_blocked_on(p, NULL);
> +                       goto deactivate;
> +               }

So, the only thought I have here is that the deactivate here will
deactivate p, not the donor.  This will cause the next cycle to follow
the same chain path, until it hits the deactivated task and then it
will call proxy_enqueue_on_owner() and pick_again. The downside is
since you're always acting effectively on a leaf (sort of an
inacturate term in the loop case), you have to basically
deactivate/enqueue_on_owner the whole chain before we migth pick
something runnable.

If instead the donor was first to be deactivated (working root to
leaf), the next pick_again cycle could potentially pick a task out of
the chain and run it.

This is maybe a little moot, since once you detect and deactivate a
task *in-the-loop*, the proxy_enqueue_on_owner() code will have to
work leaf->root. But if the loop is at the end of a chain it might
help allow non-chain tasks to be picked a little faster.

Bit of a tangent, but this does make me wonder if we should eventually
try to do the proxy_enqueue_on_owner() back down the entire chain
following the blocked_donor (similar to what we do for
proxy_migrate_task) to try to reduce the amount of pick_again work we
do.

thanks
-john