PI and assorted failings

From: Xunlei Pang <[email protected]>

We should deboost before waking the high-prio task, such that we don't run two tasks with the same "state"(priority, deadline,

sched_class, etc) during the period between the end of wake_up_q() and the end of rt_mutex_adjust_prio().

As "Peter Zijlstra" said:
Its semantically icky to have the two tasks running off the same

state and practically icky when you consider bandwidth inheritance -- where the boosted task wants to explicitly modify the state of the booster. In that latter case you really want to unboost before you let the booster run again.

But this however can lead to prio-inversion if current would get preempted after the deboost but before waking our high-prio task, hence we disable preemption before doing deboost, and enabling it

after the wake up is over.

The patch fixed the logic, and introduced rt_mutex_postunlock()

to do some code refactor.

Most importantly however; this change ensures pointer stability for the next patch, where we have rt_mutex_setprio() cache a pointer to the top-most waiter task. If we, as before this change, do the wakeup first and then deboost, this pointer might point into thin air.

Cc Steven Rostedt <[email protected]>

Cc Ingo Molnar <[email protected]>

Cc Juri Lelli <[email protected]>

Suggested-by Peter Zijlstra <[email protected]>

[peterz: Changelog]

Signed-off-by Xunlei Pang <[email protected]>

Signed-off-by Peter Zijlstra (Intel) <[email protected]>

Link http://lkml.kernel.org/r/[email protected] open here

---

 kernel/futex.c                  |    5 ++---
 kernel/locking/rtmutex.c        |   28 ++++++++++++++++++++++++----
 kernel/locking/rtmutex_common.h |    1 +
 3 files changed, 27 insertions(+), 7 deletions(-)

kernel/futex.c +2 -3

@@ -1336,9 +1336,8 @@ static int wake_futex_pi(u32 __user *uad
 	 * scheduled away before the wake up can take place.
 	 */
 	spin_unlock(&hb->lock);
-	wake_up_q(&wake_q);
-	if (deboost)
-		rt_mutex_adjust_prio(current);
+
+	rt_mutex_postunlock(&wake_q, deboost);
 
 	return 0;
 }

kernel/locking/rtmutex.c +24 -4

@@ -1390,12 +1390,32 @@ rt_mutex_fastunlock(struct rt_mutex *loc
 	} else {
 		bool deboost = slowfn(lock, &wake_q);
 
-		wake_up_q(&wake_q);
+		rt_mutex_postunlock(&wake_q, deboost);
+	}
+}
+
 
-		/* Undo pi boosting if necessary: */
-		if (deboost)
-			rt_mutex_adjust_prio(current);
+/*
+ * Undo pi boosting (if necessary) and wake top waiter.
+ */
+void rt_mutex_postunlock(struct wake_q_head *wake_q, bool deboost)
+{
+	/*
+	 * We should deboost before waking the top waiter task such that
+	 * we don't run two tasks with the 'same' priority. This however
+	 * can lead to prio-inversion if we would get preempted after
+	 * the deboost but before waking our high-prio task, hence the
+	 * preempt_disable.
+	 */
+	if (deboost) {
+		preempt_disable();
+		rt_mutex_adjust_prio(current);
 	}
+
+	wake_up_q(wake_q);
+
+	if (deboost)
+		preempt_enable();
 }
 
 /**

kernel/locking/rtmutex_common.h +1 -0

@@ -111,6 +111,7 @@ extern int rt_mutex_finish_proxy_lock(st
 extern int rt_mutex_timed_futex_lock(struct rt_mutex *l, struct hrtimer_sleeper *to);
 extern bool rt_mutex_futex_unlock(struct rt_mutex *lock,
 				  struct wake_q_head *wqh);
+extern void rt_mutex_postunlock(struct wake_q_head *wake_q, bool deboost);
 extern void rt_mutex_adjust_prio(struct task_struct *task);
 
 #ifdef CONFIG_DEBUG_RT_MUTEXES

I've got only nitpicks for the changelog. Otherwise the patch looks good to me (and yes, without it bw inheritance would be a problem).

Quoted 2 lines · Juri Lelli

I've got only nitpicks for the changelog. Otherwise the patch looks good to me (and yes, without it bw inheritance would be a problem).

So for bw inheritance I'm still not sure how to dead with the faxt that the top_pi_waiter, while blocked, can still be running, spin waiting.

Quoted 7 lines · Peter Zijlstra

Quoted 2 lines · Juri Lelli

I've got only nitpicks for the changelog. Otherwise the patch looks good to me (and yes, without it bw inheritance would be a problem).

So for bw inheritance I'm still not sure how to dead with the faxt that the top_pi_waiter, while blocked, can still be running, spin waiting.

You mean for M-BWI (multiprocessor), right? If that's the case, we were actually discussing this thing with Pisa/Trento folks yesterday. I'm not sure yet as well, but plan seems to be to get first things right with current DI code (Luca was saying that there is a BUG somewhere); then move to implement BWI; and then tackle the M- case (and see what we can do to work around the theoretical need for spin waiting). We actually got some ideas a while back, but I need to go there and refresh my mind.

If the plan sounds reasonable to you, it seems that we can start this discussion as soon as Luca has his DI fixes ready. What you think?

Do we have any specific tests for this set? I'm running mine.

Quoted 1 line · Juri Lelli

Do we have any specific tests for this set? I'm running mine.

pi_stress from rt-tests is a good workload to run for such changes.

(https://git.kernel.org/cgit/utils/rt-tests/rt-tests.git/)

From: Xunlei Pang <[email protected]>

We should deboost before waking the high-prio task, such that we don't run two tasks with the same "state"(priority, deadline, sched_class, etc) during the period between the end of wake_up_q() and the end of rt_mutex_adjust_prio().

As "Peter Zijlstra" said:
Its semantically icky to have the two tasks running off the same state and practically icky when you consider bandwidth inheritance -- where the boosted task wants to explicitly modify the state of the booster. In that latter case you really want to unboost before you let the booster run again.

But this however can lead to prio-inversion if current would get preempted after the deboost but before waking our high-prio task, hence we disable preemption before doing deboost, and enabling it after the wake up is over.

The patch fixed the logic, and introduced rt_mutex_postunlock() to do some code refactor.

Most importantly however; this change ensures pointer stability for the next patch, where we have rt_mutex_setprio() cache a pointer to the top-most waiter task. If we, as before this change, do the wakeup first and then deboost, this pointer might point into thin air.

Cc Steven Rostedt <[email protected]>

Cc Ingo Molnar <[email protected]>

Cc Juri Lelli <[email protected]>

Suggested-by Peter Zijlstra <[email protected]>

[peterz: Changelog]

Signed-off-by Xunlei Pang <[email protected]>

Signed-off-by Peter Zijlstra (Intel) <[email protected]>

Link http://lkml.kernel.org/r/[email protected] open here

---

From: Xunlei Pang <[email protected]>

A crash happened while I was playing with deadline PI rtmutex.

    BUG: unable to handle kernel NULL pointer dereference at 0000000000000018
    IP: [<ffffffff810eeb8f>] rt_mutex_get_top_task+0x1f/0x30
    PGD 232a75067 PUD 230947067 PMD 0
    Oops: 0000 [#1] SMP
    CPU: 1 PID: 10994 Comm: a.out Not tainted

    Call Trace:
    [<ffffffff810b658c>] enqueue_task+0x2c/0x80
    [<ffffffff810ba763>] activate_task+0x23/0x30
    [<ffffffff810d0ab5>] pull_dl_task+0x1d5/0x260
    [<ffffffff810d0be6>] pre_schedule_dl+0x16/0x20

    [<ffffffff8164e783>] __schedule+0xd3/0x900
    [<ffffffff8164efd9>] schedule+0x29/0x70
    [<ffffffff8165035b>] __rt_mutex_slowlock+0x4b/0xc0
    [<ffffffff81650501>] rt_mutex_slowlock+0xd1/0x190
    [<ffffffff810eeb33>] rt_mutex_timed_lock+0x53/0x60
    [<ffffffff810ecbfc>] futex_lock_pi.isra.18+0x28c/0x390
    [<ffffffff810ed8b0>] do_futex+0x190/0x5b0
    [<ffffffff810edd50>] SyS_futex+0x80/0x180

This is because rt_mutex_enqueue_pi() and rt_mutex_dequeue_pi() are only protected by pi_lock when operating pi waiters, while rt_mutex_get_top_task(), will access them with rq lock held but not holding pi_lock.

In order to tackle it, we introduce new "pi_top_task" pointer cached in task_struct, and add new rt_mutex_update_top_task() to update its value, it can be called by rt_mutex_setprio() which held both owner's pi_lock and rq lock. Thus "pi_top_task" can be safely accessed by enqueue_task_dl() under rq lock.

[XXX this next section is unparsable]

One problem is when rt_mutex_adjust_prio()->...->rt_mutex_setprio(), at that time rtmutex lock was released and owner was marked off, this can cause "pi_top_task" dereferenced to be a running one(as it can be falsely woken up by others before rt_mutex_setprio() is made to update "pi_top_task"). We solve this by directly calling __rt_mutex_adjust_prio() in mark_wakeup_next_waiter() which held pi_lock and rtmutex lock, and remove rt_mutex_adjust_prio(). Since now we moved the deboost point, in order to avoid current to be preempted due to deboost earlier before wake_up_q(), we also moved preempt_disable() before unlocking rtmutex.

Cc: Steven Rostedt <[email protected]>
Cc: Ingo Molnar <[email protected]>
Cc: Juri Lelli <[email protected]>
Originally-From: Peter Zijlstra <[email protected]>

Signed-off-by Xunlei Pang <[email protected]>

Signed-off-by Peter Zijlstra (Intel) <[email protected]>

Link http://lkml.kernel.org/r/[email protected] open here

---

 include/linux/init_task.h |    1 
 include/linux/sched.h     |    2 +
 include/linux/sched/rt.h  |    1 
 kernel/fork.c             |    1 
 kernel/locking/rtmutex.c  |   65 +++++++++++++++++++---------------------------
 kernel/sched/core.c       |    2 +
 6 files changed, 34 insertions(+), 38 deletions(-)

include/linux/init_task.h +1 -0

@@ -162,6 +162,7 @@ extern struct task_group root_task_group
 #ifdef CONFIG_RT_MUTEXES
 # define INIT_RT_MUTEXES(tsk)						\
 	.pi_waiters = RB_ROOT,						\
+	.pi_top_task = NULL,						\
 	.pi_waiters_leftmost = NULL,
 #else
 # define INIT_RT_MUTEXES(tsk)

include/linux/sched.h +2 -0

@@ -1681,6 +1681,8 @@ struct task_struct {
 	/* PI waiters blocked on a rt_mutex held by this task */
 	struct rb_root pi_waiters;
 	struct rb_node *pi_waiters_leftmost;
+	/* Updated under owner's pi_lock and rq lock */
+	struct task_struct *pi_top_task;
 	/* Deadlock detection and priority inheritance handling */
 	struct rt_mutex_waiter *pi_blocked_on;
 #endif

include/linux/sched/rt.h +1 -0

@@ -19,6 +19,7 @@ static inline int rt_task(struct task_st
 extern int rt_mutex_getprio(struct task_struct *p);
 extern void rt_mutex_setprio(struct task_struct *p, int prio);
 extern int rt_mutex_get_effective_prio(struct task_struct *task, int newprio);
+extern void rt_mutex_update_top_task(struct task_struct *p);
 extern struct task_struct *rt_mutex_get_top_task(struct task_struct *task);
 extern void rt_mutex_adjust_pi(struct task_struct *p);
 static inline bool tsk_is_pi_blocked(struct task_struct *tsk)

kernel/fork.c +1 -0

@@ -1219,6 +1219,7 @@ static void rt_mutex_init_task(struct ta
 #ifdef CONFIG_RT_MUTEXES
 	p->pi_waiters = RB_ROOT;
 	p->pi_waiters_leftmost = NULL;
+	p->pi_top_task = NULL;
 	p->pi_blocked_on = NULL;
 #endif
 }

kernel/locking/rtmutex.c +27 -38

@@ -256,6 +256,16 @@ rt_mutex_dequeue_pi(struct task_struct *
 	RB_CLEAR_NODE(&waiter->pi_tree_entry);
 }
 
+void rt_mutex_update_top_task(struct task_struct *p)
+{
+	if (!task_has_pi_waiters(p)) {
+		p->pi_top_task = NULL;
+		return;
+	}
+
+	p->pi_top_task = task_top_pi_waiter(p)->task;
+}
+
 /*
  * Calculate task priority from the waiter tree priority
  *

@@ -273,10 +283,7 @@ int rt_mutex_getprio(struct task_struct
 
 struct task_struct *rt_mutex_get_top_task(struct task_struct *task)
 {
-	if (likely(!task_has_pi_waiters(task)))
-		return NULL;
-
-	return task_top_pi_waiter(task)->task;
+	return task->pi_top_task;
 }
 
 /*

@@ -285,12 +292,12 @@ struct task_struct *rt_mutex_get_top_tas
  */
 int rt_mutex_get_effective_prio(struct task_struct *task, int newprio)
 {
-	if (!task_has_pi_waiters(task))
+	struct task_struct *top_task = rt_mutex_get_top_task(task);
+
+	if (!top_task)
 		return newprio;
 
-	if (task_top_pi_waiter(task)->task->prio <= newprio)
-		return task_top_pi_waiter(task)->task->prio;
-	return newprio;
+	return min(top_task->prio, newprio);
 }
 
 /*

@@ -307,24 +314,6 @@ static void __rt_mutex_adjust_prio(struc
 }
 
 /*
- * Adjust task priority (undo boosting). Called from the exit path of
- * rt_mutex_slowunlock() and rt_mutex_slowlock().
- *
- * (Note: We do this outside of the protection of lock->wait_lock to
- * allow the lock to be taken while or before we readjust the priority
- * of task. We do not use the spin_xx_mutex() variants here as we are
- * outside of the debug path.)
- */
-void rt_mutex_adjust_prio(struct task_struct *task)
-{
-	unsigned long flags;
-
-	raw_spin_lock_irqsave(&task->pi_lock, flags);
-	__rt_mutex_adjust_prio(task);
-	raw_spin_unlock_irqrestore(&task->pi_lock, flags);
-}
-
-/*
  * Deadlock detection is conditional:
  *
  * If CONFIG_DEBUG_RT_MUTEXES=n, deadlock detection is only conducted

@@ -987,6 +976,7 @@ static void mark_wakeup_next_waiter(stru
 	 * lock->wait_lock.
 	 */
 	rt_mutex_dequeue_pi(current, waiter);
+	__rt_mutex_adjust_prio(current);
 
 	/*
 	 * As we are waking up the top waiter, and the waiter stays

@@ -1325,6 +1315,16 @@ static bool __sched rt_mutex_slowunlock(
 	 */
 	mark_wakeup_next_waiter(wake_q, lock);
 
+	/*
+	 * We should deboost before waking the top waiter task such that
+	 * we don't run two tasks with the 'same' priority. This however
+	 * can lead to prio-inversion if we would get preempted after
+	 * the deboost but before waking our high-prio task, hence the
+	 * preempt_disable before unlock. Pairs with preempt_enable() in
+	 * rt_mutex_postunlock();
+	 */
+	preempt_disable();
+
 	raw_spin_unlock_irqrestore(&lock->wait_lock, flags);
 
 	/* check PI boosting */

@@ -1400,20 +1400,9 @@ rt_mutex_fastunlock(struct rt_mutex *loc
  */
 void rt_mutex_postunlock(struct wake_q_head *wake_q, bool deboost)
 {
-	/*
-	 * We should deboost before waking the top waiter task such that
-	 * we don't run two tasks with the 'same' priority. This however
-	 * can lead to prio-inversion if we would get preempted after
-	 * the deboost but before waking our high-prio task, hence the
-	 * preempt_disable.
-	 */
-	if (deboost) {
-		preempt_disable();
-		rt_mutex_adjust_prio(current);
-	}
-
 	wake_up_q(wake_q);
 
+	/* Pairs with preempt_disable() in rt_mutex_slowunlock() */
 	if (deboost)
 		preempt_enable();
 }

kernel/sched/core.c +2 -0

@@ -3568,6 +3568,8 @@ void rt_mutex_setprio(struct task_struct
 		goto out_unlock;
 	}
 
+	rt_mutex_update_top_task(p);
+
 	trace_sched_pi_setprio(p, prio);
 	oldprio = p->prio;
 

Quoted 1 line

[XXX this next section is unparsable]

Yes, a bit hard to understand. However, am I correct in assuming this patch and the previous one should fix this problem? Or are there still other races causing issues?

Hi,

Quoted 15 lines · Peter Zijlstra

From: Xunlei Pang <[email protected]>

A crash happened while I was playing with deadline PI rtmutex.

    BUG: unable to handle kernel NULL pointer dereference at 0000000000000018
    IP: [<ffffffff810eeb8f>] rt_mutex_get_top_task+0x1f/0x30
    PGD 232a75067 PUD 230947067 PMD 0
    Oops: 0000 [#1] SMP
    CPU: 1 PID: 10994 Comm: a.out Not tainted

    Call Trace:
    [<ffffffff810b658c>] enqueue_task+0x2c/0x80
    [<ffffffff810ba763>] activate_task+0x23/0x30
    [<ffffffff810d0ab5>] pull_dl_task+0x1d5/0x260
    [<ffffffff810d0be6>] pre_schedule_dl+0x16/0x20

Quoted 9 lines

    [<ffffffff8164e783>] __schedule+0xd3/0x900
    [<ffffffff8164efd9>] schedule+0x29/0x70
    [<ffffffff8165035b>] __rt_mutex_slowlock+0x4b/0xc0
    [<ffffffff81650501>] rt_mutex_slowlock+0xd1/0x190
    [<ffffffff810eeb33>] rt_mutex_timed_lock+0x53/0x60
    [<ffffffff810ecbfc>] futex_lock_pi.isra.18+0x28c/0x390
    [<ffffffff810ed8b0>] do_futex+0x190/0x5b0
    [<ffffffff810edd50>] SyS_futex+0x80/0x180

This seems to be caused by the race condition you detail below between load balancing and PI code. I tried to reproduce the BUG on my box, but it looks hard to get. Do you have a reproducer I can give a try?

Quoted 11 lines

This is because rt_mutex_enqueue_pi() and rt_mutex_dequeue_pi() are only protected by pi_lock when operating pi waiters, while rt_mutex_get_top_task(), will access them with rq lock held but not holding pi_lock.

In order to tackle it, we introduce new "pi_top_task" pointer cached in task_struct, and add new rt_mutex_update_top_task() to update its value, it can be called by rt_mutex_setprio() which held both owner's pi_lock and rq lock. Thus "pi_top_task" can be safely accessed by enqueue_task_dl() under rq lock.

Quoted 1 line

[XXX this next section is unparsable]

Yes, a bit hard to understand. However, am I correct in assuming this patch and the previous one should fix this problem? Or are there still other races causing issues?

Quoted 12 lines

One problem is when rt_mutex_adjust_prio()->...->rt_mutex_setprio(), at that time rtmutex lock was released and owner was marked off, this can cause "pi_top_task" dereferenced to be a running one(as it can be falsely woken up by others before rt_mutex_setprio() is made to update "pi_top_task"). We solve this by directly calling __rt_mutex_adjust_prio() in mark_wakeup_next_waiter() which held pi_lock and rtmutex lock, and remove rt_mutex_adjust_prio(). Since now we moved the deboost point, in order to avoid current to be preempted due to deboost earlier before wake_up_q(), we also moved preempt_disable() before unlocking rtmutex.

Quoted 7 lines

Cc: Steven Rostedt <[email protected]>
Cc: Ingo Molnar <[email protected]>
Cc: Juri Lelli <[email protected]>
Originally-From: Peter Zijlstra <[email protected]>

Signed-off-by Xunlei Pang <[email protected]>

Signed-off-by Peter Zijlstra (Intel) <[email protected]>

Link http://lkml.kernel.org/r/[email protected] open here

The idea of this fix makes sense to me. But, I would like to be able to see the BUG and test the fix. What I have is a test in which I create N DEADLINE workers that share a PI mutex. They get migrated around and seem to stress PI code. But I couldn't hit the BUG yet. Maybe I let it run for some more time.

Best,

- Juri

Quoted 177 lines

---

 include/linux/init_task.h |    1 
 include/linux/sched.h     |    2 +
 include/linux/sched/rt.h  |    1 
 kernel/fork.c             |    1 
 kernel/locking/rtmutex.c  |   65 +++++++++++++++++++---------------------------
 kernel/sched/core.c       |    2 +
 6 files changed, 34 insertions(+), 38 deletions(-)

include/linux/init_task.h +1 -0

@@ -162,6 +162,7 @@ extern struct task_group root_task_group
 #ifdef CONFIG_RT_MUTEXES
 # define INIT_RT_MUTEXES(tsk)						\
 	.pi_waiters = RB_ROOT,						\
+	.pi_top_task = NULL,						\
 	.pi_waiters_leftmost = NULL,
 #else
 # define INIT_RT_MUTEXES(tsk)

include/linux/sched.h +2 -0

@@ -1681,6 +1681,8 @@ struct task_struct {
 	/* PI waiters blocked on a rt_mutex held by this task */
 	struct rb_root pi_waiters;
 	struct rb_node *pi_waiters_leftmost;
+	/* Updated under owner's pi_lock and rq lock */
+	struct task_struct *pi_top_task;
 	/* Deadlock detection and priority inheritance handling */
 	struct rt_mutex_waiter *pi_blocked_on;
 #endif

include/linux/sched/rt.h +1 -0

@@ -19,6 +19,7 @@ static inline int rt_task(struct task_st
 extern int rt_mutex_getprio(struct task_struct *p);
 extern void rt_mutex_setprio(struct task_struct *p, int prio);
 extern int rt_mutex_get_effective_prio(struct task_struct *task, int newprio);
+extern void rt_mutex_update_top_task(struct task_struct *p);
 extern struct task_struct *rt_mutex_get_top_task(struct task_struct *task);
 extern void rt_mutex_adjust_pi(struct task_struct *p);
 static inline bool tsk_is_pi_blocked(struct task_struct *tsk)

kernel/fork.c +1 -0

@@ -1219,6 +1219,7 @@ static void rt_mutex_init_task(struct ta
 #ifdef CONFIG_RT_MUTEXES
 	p->pi_waiters = RB_ROOT;
 	p->pi_waiters_leftmost = NULL;
+	p->pi_top_task = NULL;
 	p->pi_blocked_on = NULL;
 #endif
 }

kernel/locking/rtmutex.c +27 -38

@@ -256,6 +256,16 @@ rt_mutex_dequeue_pi(struct task_struct *
 	RB_CLEAR_NODE(&waiter->pi_tree_entry);
 }
 
+void rt_mutex_update_top_task(struct task_struct *p)
+{
+	if (!task_has_pi_waiters(p)) {
+		p->pi_top_task = NULL;
+		return;
+	}
+
+	p->pi_top_task = task_top_pi_waiter(p)->task;
+}
+
 /*
  * Calculate task priority from the waiter tree priority
  *

@@ -273,10 +283,7 @@ int rt_mutex_getprio(struct task_struct
 
 struct task_struct *rt_mutex_get_top_task(struct task_struct *task)
 {
-	if (likely(!task_has_pi_waiters(task)))
-		return NULL;
-
-	return task_top_pi_waiter(task)->task;
+	return task->pi_top_task;
 }
 
 /*

@@ -285,12 +292,12 @@ struct task_struct *rt_mutex_get_top_tas
  */
 int rt_mutex_get_effective_prio(struct task_struct *task, int newprio)
 {
-	if (!task_has_pi_waiters(task))
+	struct task_struct *top_task = rt_mutex_get_top_task(task);
+
+	if (!top_task)
 		return newprio;
 
-	if (task_top_pi_waiter(task)->task->prio <= newprio)
-		return task_top_pi_waiter(task)->task->prio;
-	return newprio;
+	return min(top_task->prio, newprio);
 }
 
 /*

@@ -307,24 +314,6 @@ static void __rt_mutex_adjust_prio(struc
 }
 
 /*
- * Adjust task priority (undo boosting). Called from the exit path of
- * rt_mutex_slowunlock() and rt_mutex_slowlock().
- *
- * (Note: We do this outside of the protection of lock->wait_lock to
- * allow the lock to be taken while or before we readjust the priority
- * of task. We do not use the spin_xx_mutex() variants here as we are
- * outside of the debug path.)
- */
-void rt_mutex_adjust_prio(struct task_struct *task)
-{
-	unsigned long flags;
-
-	raw_spin_lock_irqsave(&task->pi_lock, flags);
-	__rt_mutex_adjust_prio(task);
-	raw_spin_unlock_irqrestore(&task->pi_lock, flags);
-}
-
-/*
  * Deadlock detection is conditional:
  *
  * If CONFIG_DEBUG_RT_MUTEXES=n, deadlock detection is only conducted

@@ -987,6 +976,7 @@ static void mark_wakeup_next_waiter(stru
 	 * lock->wait_lock.
 	 */
 	rt_mutex_dequeue_pi(current, waiter);
+	__rt_mutex_adjust_prio(current);
 
 	/*
 	 * As we are waking up the top waiter, and the waiter stays

@@ -1325,6 +1315,16 @@ static bool __sched rt_mutex_slowunlock(
 	 */
 	mark_wakeup_next_waiter(wake_q, lock);
 
+	/*
+	 * We should deboost before waking the top waiter task such that
+	 * we don't run two tasks with the 'same' priority. This however
+	 * can lead to prio-inversion if we would get preempted after
+	 * the deboost but before waking our high-prio task, hence the
+	 * preempt_disable before unlock. Pairs with preempt_enable() in
+	 * rt_mutex_postunlock();
+	 */
+	preempt_disable();
+
 	raw_spin_unlock_irqrestore(&lock->wait_lock, flags);
 
 	/* check PI boosting */

@@ -1400,20 +1400,9 @@ rt_mutex_fastunlock(struct rt_mutex *loc
  */
 void rt_mutex_postunlock(struct wake_q_head *wake_q, bool deboost)
 {
-	/*
-	 * We should deboost before waking the top waiter task such that
-	 * we don't run two tasks with the 'same' priority. This however
-	 * can lead to prio-inversion if we would get preempted after
-	 * the deboost but before waking our high-prio task, hence the
-	 * preempt_disable.
-	 */
-	if (deboost) {
-		preempt_disable();
-		rt_mutex_adjust_prio(current);
-	}
-
 	wake_up_q(wake_q);
 
+	/* Pairs with preempt_disable() in rt_mutex_slowunlock() */
 	if (deboost)
 		preempt_enable();
 }

kernel/sched/core.c +0 -0

@@ -3568,6 +3568,8 @@ void rt_mutex_setprio(struct task_struct
 		goto out_unlock;
 	}
 

kernel/sched/core.c void rt_mutex_setprio(struct task_struct · line 3575

Quoted 7 lines

kernel/sched/core.c +2 -0

+	rt_mutex_update_top_task(p);
+
 	trace_sched_pi_setprio(p, prio);
 	oldprio = p->prio;
 

Quoted 42 lines · Juri Lelli

Hi,

Quoted 15 lines · Peter Zijlstra

From: Xunlei Pang <[email protected]>

A crash happened while I was playing with deadline PI rtmutex.

    BUG: unable to handle kernel NULL pointer dereference at 0000000000000018
    IP: [<ffffffff810eeb8f>] rt_mutex_get_top_task+0x1f/0x30
    PGD 232a75067 PUD 230947067 PMD 0
    Oops: 0000 [#1] SMP
    CPU: 1 PID: 10994 Comm: a.out Not tainted

    Call Trace:
    [<ffffffff810b658c>] enqueue_task+0x2c/0x80
    [<ffffffff810ba763>] activate_task+0x23/0x30
    [<ffffffff810d0ab5>] pull_dl_task+0x1d5/0x260
    [<ffffffff810d0be6>] pre_schedule_dl+0x16/0x20

Quoted 9 lines

    [<ffffffff8164e783>] __schedule+0xd3/0x900
    [<ffffffff8164efd9>] schedule+0x29/0x70
    [<ffffffff8165035b>] __rt_mutex_slowlock+0x4b/0xc0
    [<ffffffff81650501>] rt_mutex_slowlock+0xd1/0x190
    [<ffffffff810eeb33>] rt_mutex_timed_lock+0x53/0x60
    [<ffffffff810ecbfc>] futex_lock_pi.isra.18+0x28c/0x390
    [<ffffffff810ed8b0>] do_futex+0x190/0x5b0
    [<ffffffff810edd50>] SyS_futex+0x80/0x180

This seems to be caused by the race condition you detail below between load balancing and PI code. I tried to reproduce the BUG on my box, but it looks hard to get. Do you have a reproducer I can give a try?

Quoted 11 lines

This is because rt_mutex_enqueue_pi() and rt_mutex_dequeue_pi() are only protected by pi_lock when operating pi waiters, while rt_mutex_get_top_task(), will access them with rq lock held but not holding pi_lock.

In order to tackle it, we introduce new "pi_top_task" pointer cached in task_struct, and add new rt_mutex_update_top_task() to update its value, it can be called by rt_mutex_setprio() which held both owner's pi_lock and rq lock. Thus "pi_top_task" can be safely accessed by enqueue_task_dl() under rq lock.

Quoted 4 lines

Quoted 1 line

[XXX this next section is unparsable]

Yes, a bit hard to understand. However, am I correct in assuming this patch and the previous one should fix this problem? Or are there still other races causing issues?

Yes, these two patches can fix the problem.

Quoted 19 lines

Quoted 19 lines

One problem is when rt_mutex_adjust_prio()->...->rt_mutex_setprio(), at that time rtmutex lock was released and owner was marked off, this can cause "pi_top_task" dereferenced to be a running one(as it can be falsely woken up by others before rt_mutex_setprio() is made to update "pi_top_task"). We solve this by directly calling __rt_mutex_adjust_prio() in mark_wakeup_next_waiter() which held pi_lock and rtmutex lock, and remove rt_mutex_adjust_prio(). Since now we moved the deboost point, in order to avoid current to be preempted due to deboost earlier before wake_up_q(), we also moved preempt_disable() before unlocking rtmutex.

Cc: Steven Rostedt <[email protected]>
Cc: Ingo Molnar <[email protected]>
Cc: Juri Lelli <[email protected]>
Originally-From: Peter Zijlstra <[email protected]>

Signed-off-by Xunlei Pang <[email protected]>

Signed-off-by Peter Zijlstra (Intel) <[email protected]>

Link http://lkml.kernel.org/r/[email protected] open here

Quoted 5 lines

The idea of this fix makes sense to me. But, I would like to be able to see the BUG and test the fix. What I have is a test in which I create N DEADLINE workers that share a PI mutex. They get migrated around and seem to stress PI code. But I couldn't hit the BUG yet. Maybe I let it run for some more time.

You can use this reproducer attached(gcc crash_deadline_pi.c -lpthread -lrt ). Start multiple instances, then it will hit the bug very soon.

Quoted 6 lines · Xunlei Pang

Quoted 5 lines · Juri Lelli

Hi,

Quoted 2 lines · Peter Zijlstra

From: Xunlei Pang <[email protected]>

Quoted 6 lines

Quoted 5 lines

The idea of this fix makes sense to me. But, I would like to be able to see the BUG and test the fix. What I have is a test in which I create N DEADLINE workers that share a PI mutex. They get migrated around and seem to stress PI code. But I couldn't hit the BUG yet. Maybe I let it run for some more time.

Quoted 3 lines

You can use this reproducer attached(gcc crash_deadline_pi.c -lpthread -lrt ). Start multiple instances, then it will hit the bug very soon.

Great, thanks! I'll use it.

include/linux/sched/rt.h +1 -0

@@ -19,6 +19,7 @@ static inline int rt_task(struct task_st
 extern int rt_mutex_getprio(struct task_struct *p);
 extern void rt_mutex_setprio(struct task_struct *p, int prio);
 extern int rt_mutex_get_effective_prio(struct task_struct *task, int newprio);
+extern void rt_mutex_update_top_task(struct task_struct *p);
 extern struct task_struct *rt_mutex_get_top_task(struct task_struct *task);
 extern void rt_mutex_adjust_pi(struct task_struct *p);
 static inline bool tsk_is_pi_blocked(struct task_struct *tsk)

kernel/fork.c +1 -0

@@ -1219,6 +1219,7 @@ static void rt_mutex_init_task(struct ta
 #ifdef CONFIG_RT_MUTEXES
 	p->pi_waiters = RB_ROOT;
 	p->pi_waiters_leftmost = NULL;
+	p->pi_top_task = NULL;
 	p->pi_blocked_on = NULL;
 #endif
 }

kernel/locking/rtmutex.c +16 -26

@@ -256,6 +256,16 @@ rt_mutex_dequeue_pi(struct task_struct *
 	RB_CLEAR_NODE(&waiter->pi_tree_entry);
 }
 
+void rt_mutex_update_top_task(struct task_struct *p)
+{
+	if (!task_has_pi_waiters(p)) {
+		p->pi_top_task = NULL;
+		return;
+	}
+
+	p->pi_top_task = task_top_pi_waiter(p)->task;
+}
+
 /*
  * Calculate task priority from the waiter tree priority
  *

@@ -273,10 +283,7 @@ int rt_mutex_getprio(struct task_struct
 
 struct task_struct *rt_mutex_get_top_task(struct task_struct *task)
 {
-	if (likely(!task_has_pi_waiters(task)))
-		return NULL;
-
-	return task_top_pi_waiter(task)->task;
+	return task->pi_top_task;
 }
 
 /*

@@ -285,12 +292,12 @@ struct task_struct *rt_mutex_get_top_tas
  */
 int rt_mutex_get_effective_prio(struct task_struct *task, int newprio)
 {
-	if (!task_has_pi_waiters(task))
+	struct task_struct *top_task = rt_mutex_get_top_task(task);
+
+	if (!top_task)
 		return newprio;
 
-	if (task_top_pi_waiter(task)->task->prio <= newprio)
-		return task_top_pi_waiter(task)->task->prio;
-	return newprio;
+	return min(top_task->prio, newprio);
 }
 
 /*

@@ -307,24 +314,6 @@ static void __rt_mutex_adjust_prio(struc
 }
 
 /*
- * Adjust task priority (undo boosting). Called from the exit path of
- * rt_mutex_slowunlock() and rt_mutex_slowlock().
- *
- * (Note: We do this outside of the protection of lock->wait_lock to
- * allow the lock to be taken while or before we readjust the priority
- * of task. We do not use the spin_xx_mutex() variants here as we are
- * outside of the debug path.)
- */
-void rt_mutex_adjust_prio(struct task_struct *task)
-{
-	unsigned long flags;
-
-	raw_spin_lock_irqsave(&task->pi_lock, flags);
-	__rt_mutex_adjust_prio(task);
-	raw_spin_unlock_irqrestore(&task->pi_lock, flags);
-}
-
-/*
  * Deadlock detection is conditional:
  *
  * If CONFIG_DEBUG_RT_MUTEXES=n, deadlock detection is only conducted

@@ -987,6 +976,7 @@ static void mark_wakeup_next_waiter(stru
 	 * lock->wait_lock.
 	 */
 	rt_mutex_dequeue_pi(current, waiter);
+	__rt_mutex_adjust_prio(current);
 
 	/*
 	 * As we are waking up the top waiter, and the waiter stays

@@ -1325,6 +1315,16 @@ static bool __sched rt_mutex_slowunlock(
 	 */
 	mark_wakeup_next_waiter(wake_q, lock);
 

kernel/locking/rtmutex.c +1 -12

 	raw_spin_unlock_irqrestore(&lock->wait_lock, flags);
 
 	/* check PI boosting */

@@ -1400,20 +1400,9 @@ rt_mutex_fastunlock(struct rt_mutex *loc
  */
 void rt_mutex_postunlock(struct wake_q_head *wake_q, bool deboost)
 {
-	/*
-	 * We should deboost before waking the top waiter task such that
-	 * we don't run two tasks with the 'same' priority. This however
-	 * can lead to prio-inversion if we would get preempted after
-	 * the deboost but before waking our high-prio task, hence the
-	 * preempt_disable.
-	 */
-	if (deboost) {
-		preempt_disable();
-		rt_mutex_adjust_prio(current);
-	}
-
 	wake_up_q(wake_q);
 
+	/* Pairs with preempt_disable() in rt_mutex_slowunlock() */
 	if (deboost)
 		preempt_enable();
 }

kernel/sched/core.c +2 -0

@@ -3568,6 +3568,8 @@ void rt_mutex_setprio(struct task_struct
 		goto out_unlock;
 	}
 
+	rt_mutex_update_top_task(p);
+
 	trace_sched_pi_setprio(p, prio);
 	oldprio = p->prio;
 

kernel/locking/rtmutex.c static bool __sched rt_mutex_slowunlock( · line 1327

Quoted 10 lines · On Tue, 07 Jun 2016 21:56:37 +0200 Peter Zijlstra <[email protected]> wrote:

kernel/locking/rtmutex.c +10 -0

+	/*
+	 * We should deboost before waking the top waiter task such that
+	 * we don't run two tasks with the 'same' priority. This however
+	 * can lead to prio-inversion if we would get preempted after
+	 * the deboost but before waking our high-prio task, hence the
+	 * preempt_disable before unlock. Pairs with preempt_enable() in
+	 * rt_mutex_postunlock();
+	 */
+	preempt_disable();
+

This looks like a possible maintenance nightmare. Can we add some more comments at the start of the functions that state that rt_mutex_slowunlock() calls must be paired with rt_mutex_postunlock()?

Please look at patches 4 and 5 that clean this up.

From: Xunlei Pang <[email protected]>

Currently dl tasks will actually return at the very beginning of rt_mutex_adjust_prio_chain() in !detect_deadlock cases:

    if (waiter->prio == task->prio) {
        if (!detect_deadlock)
            goto out_unlock_pi; // out here
        else
            requeue = false;
    }

As the deadline value of blocked deadline tasks(waiters) without changing their sched_class(thus prio doesn't change) never changes, this seems reasonable, but it actually misses the chance of updating rt_mutex_waiter's "dl_runtime(period)_copy" if a waiter updates its deadline parameters(dl_runtime, dl_period) or boosted waiter changes to !deadline class.

Thus, force deadline task not out by adding the !dl_prio() condition.

[peterz: I should introduce more task state comparators like rt_mutex_waiter_less, all PI prio comparisons already have this DL exception, except this one]

Cc Steven Rostedt <[email protected]>

Cc Ingo Molnar <[email protected]>

Cc Thomas Gleixner <[email protected]>

Cc Juri Lelli <[email protected]>

Signed-off-by Xunlei Pang <[email protected]>

Signed-off-by Peter Zijlstra (Intel) <[email protected]>

Link http://lkml.kernel.org/r/[email protected] open here

---
 kernel/locking/rtmutex.c |    2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

Quoted 3 lines

[peterz: I should introduce more task state comparators like rt_mutex_waiter_less, all PI prio comparisons already have this DL exception, except this one]

kernel/locking/rtmutex.c static int rt_mutex_adjust_prio_chain(st · line 491

Quoted 7 lines

+++ b/kernel/locking/rtmutex.c

kernel/locking/rtmutex.c +1 -1

@@ -488,7 +488,7 @@ static int rt_mutex_adjust_prio_chain(st
 	 * enabled we continue, but stop the requeueing in the chain
 	 * walk.
 	 */
-	if (waiter->prio == task->prio) {
+	if (waiter->prio == task->prio && !dl_task(task)) {

Right. Do we want a rt_mutex_waiter_equal() helper? As I think the comment in the changelog was also saying?

From: Xunlei Pang <[email protected]>

Currently dl tasks will actually return at the very beginning of rt_mutex_adjust_prio_chain() in !detect_deadlock cases:

    if (waiter->prio == task->prio) {
        if (!detect_deadlock)
            goto out_unlock_pi; // out here
        else
            requeue = false;
    }

As the deadline value of blocked deadline tasks(waiters) without changing their sched_class(thus prio doesn't change) never changes, this seems reasonable, but it actually misses the chance of updating rt_mutex_waiter's "dl_runtime(period)_copy" if a waiter updates its deadline parameters(dl_runtime, dl_period) or boosted waiter changes to !deadline class.

Thus, force deadline task not out by adding the !dl_prio() condition.

[peterz: I should introduce more task state comparators like rt_mutex_waiter_less, all PI prio comparisons already have this DL exception, except this one]

Cc Steven Rostedt <[email protected]>

Cc Ingo Molnar <[email protected]>

Cc Thomas Gleixner <[email protected]>

Cc Juri Lelli <[email protected]>

Signed-off-by Xunlei Pang <[email protected]>

Signed-off-by Peter Zijlstra (Intel) <[email protected]>

Link http://lkml.kernel.org/r/[email protected] open here

---
 kernel/locking/rtmutex.c |    2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

kernel/locking/rtmutex.c +0 -0

 		if (!detect_deadlock)
 			goto out_unlock_pi;
 		else

kernel/locking/rtmutex.c static int rt_mutex_adjust_prio_chain(st · line 491

Quoted 7 lines

+++ b/kernel/locking/rtmutex.c

kernel/locking/rtmutex.c +1 -1

@@ -488,7 +488,7 @@ static int rt_mutex_adjust_prio_chain(st
 	 * enabled we continue, but stop the requeueing in the chain
 	 * walk.
 	 */
-	if (waiter->prio == task->prio) {
+	if (waiter->prio == task->prio && !dl_task(task)) {

Isn't task the owner of the lock?

What happens if the waiter is a
deadline task?

There is but a single user and the previous patch mandates slowfn must be rt_mutex_slowunlock(), so fold the lot together and save a few lines.

Signed-off-by Peter Zijlstra (Intel) <[email protected]>

---
 kernel/locking/rtmutex.c |   29 ++++++++++-------------------
 1 file changed, 10 insertions(+), 19 deletions(-)

Previous patches changed the meaning of the return value of rt_mutex_slowunlock(); update comments and code to reflect this.

Signed-off-by Peter Zijlstra (Intel) <[email protected]>

---
 kernel/futex.c                  |   12 ++++++------
 kernel/locking/rtmutex.c        |   20 +++++++++-----------
 kernel/locking/rtmutex_common.h |    2 +-
 3 files changed, 16 insertions(+), 18 deletions(-)

kernel/futex.c +2 -3

@@ -1261,7 +1261,7 @@ static int wake_futex_pi(u32 __user *uad
 	struct futex_pi_state *pi_state = this->pi_state;
 	u32 uninitialized_var(curval), newval;
 	WAKE_Q(wake_q);
-	bool deboost;
+	bool postunlock;
 	int ret = 0;
 
 	if (!pi_state)

@@ -1327,17 +1327,17 @@ static int wake_futex_pi(u32 __user *uad
 
 	raw_spin_unlock_irq(&pi_state->pi_mutex.wait_lock);
 
-	deboost = rt_mutex_futex_unlock(&pi_state->pi_mutex, &wake_q);
+	postunlock = rt_mutex_futex_unlock(&pi_state->pi_mutex, &wake_q);
 
 	/*
 	 * First unlock HB so the waiter does not spin on it once he got woken
-	 * up. Second wake up the waiter before the priority is adjusted. If we

kernel/futex.c +0 -0

 	return 0;
 }

kernel/locking/rtmutex.c +9 -11

@@ -1254,7 +1254,8 @@ static inline int rt_mutex_slowtrylock(s
 
 /*
  * Slow path to release a rt-mutex.
- * Return whether the current task needs to undo a potential priority boosting.
+ *
+ * Return whether the current task needs to call rt_mutex_postunlock().
  */
 static bool __sched rt_mutex_slowunlock(struct rt_mutex *lock,
 					struct wake_q_head *wake_q)

@@ -1327,7 +1328,7 @@ static bool __sched rt_mutex_slowunlock(
 
 	raw_spin_unlock_irqrestore(&lock->wait_lock, flags);
 
-	/* check PI boosting */
+	/* call rt_mutex_postunlock() */
 	return true;
 }
 

@@ -1378,15 +1379,14 @@ rt_mutex_fasttrylock(struct rt_mutex *lo
 }
 
 /*
- * Undo pi boosting (if necessary) and wake top waiter.
+ * Performs the wakeup of the the top-waiter and re-enables preemption.
  */
-void rt_mutex_postunlock(struct wake_q_head *wake_q, bool deboost)
+void rt_mutex_postunlock(struct wake_q_head *wake_q)
 {
 	wake_up_q(wake_q);
 
 	/* Pairs with preempt_disable() in rt_mutex_slowunlock() */
-	if (deboost)
-		preempt_enable();
+	preempt_enable();
 }
 
 /**

@@ -1489,9 +1489,8 @@ void __sched rt_mutex_unlock(struct rt_m
 		rt_mutex_deadlock_account_unlock(current);
 
 	} else {
-		bool deboost = rt_mutex_slowunlock(lock, &wake_q);
-
-		rt_mutex_postunlock(&wake_q, deboost);
+		if (rt_mutex_slowunlock(lock, &wake_q))
+			rt_mutex_postunlock(&wake_q);
 	}
 }
 EXPORT_SYMBOL_GPL(rt_mutex_unlock);

@@ -1500,8 +1499,7 @@ EXPORT_SYMBOL_GPL(rt_mutex_unlock);
  * rt_mutex_futex_unlock - Futex variant of rt_mutex_unlock
  * @lock: the rt_mutex to be unlocked
  *
- * Returns: true/false indicating whether priority adjustment is
- * required or not.
+ * Returns: true/false indicating whether we should call rt_mutex_postunlock().
  */
 bool __sched rt_mutex_futex_unlock(struct rt_mutex *lock,
 				   struct wake_q_head *wqh)

kernel/locking/rtmutex_common.h +1 -1

@@ -111,7 +111,7 @@ extern int rt_mutex_finish_proxy_lock(st
 extern int rt_mutex_timed_futex_lock(struct rt_mutex *l, struct hrtimer_sleeper *to);
 extern bool rt_mutex_futex_unlock(struct rt_mutex *lock,
 				  struct wake_q_head *wqh);
-extern void rt_mutex_postunlock(struct wake_q_head *wake_q, bool deboost);
+extern void rt_mutex_postunlock(struct wake_q_head *wake_q);
 extern void rt_mutex_adjust_prio(struct task_struct *task);
 
 #ifdef CONFIG_DEBUG_RT_MUTEXES

Quoted 9 lines

kernel/futex.c +3 -0

+	postunlock = rt_mutex_futex_unlock(&pi_state->pi_mutex, &wake_q);
 
 	/*
 	 * First unlock HB so the waiter does not spin on it once he got woken
+	 * up. Then wakeup the waiter by calling rt_mutex_postunlock(). Priority
+	 * is already adjusted and preemption is disabled to avoid inversion.
 	 */
 	spin_unlock(&hb->lock);

kernel/futex.c static int wake_futex_pi(u32 __user *uad · line 1340

Quoted 2 lines

kernel/futex.c +2 -0

+	if (postunlock)
+		rt_mutex_postunlock(&wake_q);

I'm most probably missing something, but don't we still need to call wake_up_q() even when postunlock is false? IIUC, we were always doing that, rt_mutex_postunlock(), before this change (only calling preempt_enable() was conditional).

Quoted 9 lines · Juri Lelli

Quoted 9 lines

kernel/futex.c +3 -0

+	postunlock = rt_mutex_futex_unlock(&pi_state->pi_mutex, &wake_q);
 
 	/*
 	 * First unlock HB so the waiter does not spin on it once he got woken
+	 * up. Then wakeup the waiter by calling rt_mutex_postunlock(). Priority
+	 * is already adjusted and preemption is disabled to avoid inversion.
 	 */
 	spin_unlock(&hb->lock);

Quoted 7 lines

kernel/futex.c static int wake_futex_pi(u32 __user *uad · line 1340

Quoted 2 lines

kernel/futex.c +2 -0

+	if (postunlock)
+		rt_mutex_postunlock(&wake_q);

I'm most probably missing something, but don't we still need to call wake_up_q() even when postunlock is false? IIUC, we were always doing that, rt_mutex_postunlock(), before this change (only calling preempt_enable() was conditional).

Note that rt_mutex_slowunlock() only uses wake_q on the true path. When it returns false, it will not have placed a task to wake up.

With the introduction of SCHED_DEADLINE the whole notion that priority is a single number is gone, therefore the @prio argument to rt_mutex_setprio() doesn't make sense anymore.

So rework the code to pass a pi_task instead.

Note this also fixes a problem with pi_top_task caching; previously we would not set the pointer (call rt_mutex_update_top_task) if the priority didn't change, this could lead to a stale pointer.

As for the XXX, I think its fine to use pi_task->prio, because if it differs from waiter->prio, a PI chain update is immenent.

Signed-off-by Peter Zijlstra (Intel) <[email protected]>

---
 include/linux/sched/rt.h        |   21 +-------
 kernel/locking/rtmutex.c        |  105 +++++++++++-----------------------------
 kernel/locking/rtmutex_common.h |    1 
 kernel/sched/core.c             |   66 ++++++++++++++++++++-----
 4 files changed, 88 insertions(+), 105 deletions(-)

kernel/locking/rtmutex.c +2 -14

@@ -256,61 +256,16 @@ rt_mutex_dequeue_pi(struct task_struct *
 	RB_CLEAR_NODE(&waiter->pi_tree_entry);
 }
 
-void rt_mutex_update_top_task(struct task_struct *p)
+static void rt_mutex_adjust_prio(struct task_struct *p)
 {
-	if (!task_has_pi_waiters(p)) {
-		p->pi_top_task = NULL;
-		return;
-	}
+	struct task_struct *pi_task = NULL;
 
-	p->pi_top_task = task_top_pi_waiter(p)->task;
-}
-
-/*
- * Calculate task priority from the waiter tree priority
- *
- * Return task->normal_prio when the waiter tree is empty or when
- * the waiter is not allowed to do priority boosting
- */

Hi,

still digesting this change, but I'll point out below why I think you are hitting a NULL ptr dereference (discussed on IRC).

Quoted 10 lines · Peter Zijlstra

kernel/locking/rtmutex.c +2 -0

@@ -256,61 +256,16 @@ rt_mutex_dequeue_pi(struct task_struct *
 	RB_CLEAR_NODE(&waiter->pi_tree_entry);
 }
 
+static void rt_mutex_adjust_prio(struct task_struct *p)
 {
+	struct task_struct *pi_task = NULL;
 

kernel/locking/rtmutex.c rt_mutex_dequeue_pi(struct task_struct * · line 265

Quoted 3 lines

kernel/locking/rtmutex.c +2 -0

+	lockdep_assert_held(&p->pi_lock);
 
+	if (!task_has_pi_waiters(p))

Shouldn't this be the other way around?

if (task_has_pi_waiters(p))
pi_task = ...

rt_mutex_waiter::prio is a copy of task_struct::prio which is updated during the PI chain walk, such that the PI chain order isn't messed up by (asynchronous) task state updates.

Currently rt_mutex_waiter_less() uses task state for deadline tasks; this is broken, since the task state can, as said above, change asynchronously, causing the RB tree order to change without actual tree update -> FAIL.

Fix this by also copying the deadline into the rt_mutex_waiter state and updating it along with its prio field.

Ideally we would also force PI chain updates whenever DL tasks update their deadline parameter, but for first approximation this is less broken than it was.

Quoted 9 lines · Peter Zijlstra

rt_mutex_waiter::prio is a copy of task_struct::prio which is updated during the PI chain walk, such that the PI chain order isn't messed up by (asynchronous) task state updates.

Currently rt_mutex_waiter_less() uses task state for deadline tasks; this is broken, since the task state can, as said above, change asynchronously, causing the RB tree order to change without actual tree update -> FAIL.

Quoted 7 lines

Fix this by also copying the deadline into the rt_mutex_waiter state and updating it along with its prio field.

Ideally we would also force PI chain updates whenever DL tasks update their deadline parameter, but for first approximation this is less broken than it was.

The patch looks OK to me. However, I'm failing to see when we can update dl.deadline of a waiter asynchronously. Since a waiter is blocked, we can't really change his dl.deadline by calling setscheduler on him, as the update would operate on dl.dl_deadline. The new values will start to be used as soon as it gets unblocked. The situation seems different for RT tasks, for which priority change takes effect immediately.

What am I missing? :-)

Quoted 25 lines · Juri Lelli

Quoted 9 lines · Peter Zijlstra

rt_mutex_waiter::prio is a copy of task_struct::prio which is updated during the PI chain walk, such that the PI chain order isn't messed up by (asynchronous) task state updates.

Currently rt_mutex_waiter_less() uses task state for deadline tasks; this is broken, since the task state can, as said above, change asynchronously, causing the RB tree order to change without actual tree update -> FAIL.

Quoted 7 lines

Fix this by also copying the deadline into the rt_mutex_waiter state and updating it along with its prio field.

Ideally we would also force PI chain updates whenever DL tasks update their deadline parameter, but for first approximation this is less broken than it was.

The patch looks OK to me. However, I'm failing to see when we can update dl.deadline of a waiter asynchronously. Since a waiter is blocked, we can't really change his dl.deadline by calling setscheduler on him, as the update would operate on dl.dl_deadline. The new values will start to be used as soon as it gets unblocked. The situation seems different for RT tasks, for which priority change takes effect immediately.

Quoted 1 line

What am I missing? :-)

Ah, I missed the dl_deadline vs deadline thing. Still, with optimistic spinning the waiter could hit its throttle/refresh path, right? And then that would update deadline.

I guess it's not that likely, but yes it could potentially happen that a waiter is optimistically spinning, depletes its runtime, gets throttled and then replenished when still spinning. Maybe it doesn't really make sense continuing spinning in this situation, but I guess things get really complicated. :-/

Anyway, as said, I think this patch is OK. Maybe we want to add a comment just to remember what situation can cause an issue if we don't do this? Patch changelog would be OK as well for such a comment IMHO.

Quoted 9 lines · Juri Lelli

I guess it's not that likely, but yes it could potentially happen that a waiter is optimistically spinning, depletes its runtime, gets throttled and then replenished when still spinning. Maybe it doesn't really make sense continuing spinning in this situation, but I guess things get really complicated. :-/

Anyway, as said, I think this patch is OK. Maybe we want to add a comment just to remember what situation can cause an issue if we don't do this? Patch changelog would be OK as well for such a comment IMHO.

OK, so I went to write a simple comment and ended up with the below :/

While writing the comment I noticed two issues:

- we update the waiter order fields while the entry is still enqueued on the pi_waiters tree, which is also sorted by these exact fields.

- another one of these pure ->prio comparisons

Please double check, there be dragons here.

Quoted 9 lines · Juri Lelli

I guess it's not that likely, but yes it could potentially happen that a waiter is optimistically spinning, depletes its runtime, gets throttled and then replenished when still spinning. Maybe it doesn't really make sense continuing spinning in this situation, but I guess things get really complicated. :-/

Anyway, as said, I think this patch is OK. Maybe we want to add a comment just to remember what situation can cause an issue if we don't do this? Patch changelog would be OK as well for such a comment IMHO.

OK, so I went to write a simple comment and ended up with the below :/

While writing the comment I noticed two issues:

- we update the waiter order fields while the entry is still enqueued on the pi_waiters tree, which is also sorted by these exact fields.

- another one of these pure ->prio comparisons

Please double check, there be dragons here.