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

[John Stultz]

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.

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>
---
Cc: Peter Zijlstra <peterz@xxxxxxxxxxxxx>
Cc: Ingo Molnar <mingo@xxxxxxxxxx>
Cc: K Prateek Nayak <kprateek.nayak@xxxxxxx>
Cc: Thomas Gleixner <tglx@xxxxxxxxxxxxx>
Cc: Juri Lelli <juri.lelli@xxxxxxxxxx>
Cc: Vincent Guittot <vincent.guittot@xxxxxxxxxx>
Cc: Valentin Schneider <vschneid@xxxxxxxxxx>
Cc: Suleiman Souhlal <suleiman@xxxxxxxxxx>
Cc: Andrea Righi <arighi@xxxxxxxxxx>
Cc: Metin Kaya <Metin.Kaya@xxxxxxx>
Cc: Dietmar Eggemann <dietmar.eggemann@xxxxxxx>
Cc: Steven Rostedt <rostedt@xxxxxxxxxxx>
Cc: Zimuzo Ezeozue <zezeozue@xxxxxxxxxx>
Cc: Waiman Long <longman@xxxxxxxxxx>
Cc: Boqun Feng <boqun.feng@xxxxxxxxx>
Cc: "Paul E. McKenney" <paulmck@xxxxxxxxxx>
Cc: Joel Fernandes <joelagnelf@xxxxxxxxxx>
Cc: Qais Yousef <qyousef@xxxxxxxxxxx>
Cc: Xuewen Yan <xuewen.yan94@xxxxxxxxx>
Cc: kuyo chang <kuyo.chang@xxxxxxxxxxxx>
Cc: hupu <hupu.gm@xxxxxxxxx>
Cc: Zhan Xusheng <zhanxusheng@xxxxxxxxxx>
Cc: zhidao su (Xiaomi) <soolaugust@xxxxxxxxx>
Cc: Hui Su <sh_def@xxxxxxx>
Cc: Shubhang Kaushik (Ampere) <sh@xxxxxxxxxx>
Cc: kernel-team@xxxxxxxxxxx
---
 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. */
+		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