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

[Kayra Cizmeci]

On Fri, Oct 23, 2026 at 10:04:17PM +0000, John Stultz wrote:
> From: Hui Su <sh_def@xxxxxxx>
> 
> 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.

Wouldn't it be better to add the results here or remove this sentence
completely? "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>
> [jstultz: Minor tweaks to work with hard MAX_PROXY_CHAIN_DEPTH limit]
> Signed-off-by: John Stultz <jstultz@xxxxxxxxxx>
> ---
> ---
>  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. */

I think we don't need the comment above, no? Or atleast maybe changing it would
be better to tell what the algorithm does.

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

So on a loop like this (Circle but a square):

TA->X
|   |
Y<-TB

Where TA holds X, wants Y and TB wants X, holds Y. And the donor is TA.

At the first run, we get the mutex of TA and then find it's owner (that
is TB), and we increase cycle_span by one. The next run is with TB, now
power is 2, and span is 0. Owner is TA, so again owner ==
cycle_checkpoint is false. span is 1 now. The next run, owner is TB,
and now we leave.

AFAICT this works correct.

Reviewed-by: Kayra Cizmeci <kayracizmeci@xxxxxxxxx>