[PATCH 3/5] locking/rtmutex: Clone a waiter's sort keys as it enters pi_waiters

[Mathieu Desnoyers <mathieu.desnoyers@efficios.com>]

An rt_mutex owner can inherit the priority of the wrong waiter. A waiter
has two copies of its sort keys: the lock tree's, updated when its
priority changes, and the pi_tree's, which orders its owner's
pi_waiters, cloned from the first when the waiter blocks and by the
chain walk while it is the top waiter of its lock. A waiter whose
priority changes while another is ahead of it, and that becomes the top
waiter later, as the one ahead times out (remove_waiter()) or the lock
changes hands (try_to_take_rt_mutex()), enters pi_waiters with keys it
no longer has. On v7.4-rc1, an owner with a SCHED_FIFO 50 waiter on one
mutex, and on another a SCHED_FIFO 70 waiter set to SCHED_FIFO 10 behind
one of 80 that times out, runs at SCHED_FIFO 10 while the SCHED_FIFO 50
task waits on it, in 3 runs of 3.

Clone the keys in rt_mutex_enqueue_pi(), under the wait_lock that the
lock tree copy is updated under and the owner's pi_lock that the
pi_tree copy is read under, and drop the clones its callers did. The
owner then runs at SCHED_FIFO 50, in 3 runs of 3. The
futex_lock_pi_inherit selftest added later in this series has the case,
promoted_waiter.

Found reviewing "sched/deadline: Take a deadline boost from the
waiter's rt_mutex node", posted in a series on top of this one, which
takes a deadline boost from these keys.

Fixes: f7853c342418 ("locking/rtmutex: Fix task->pi_waiters integrity")
Cc: stable@vger.kernel.org
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
---
 kernel/locking/rtmutex.c | 11 ++++++++---
 1 file changed, 8 insertions(+), 3 deletions(-)

diff --git a/kernel/locking/rtmutex.c b/kernel/locking/rtmutex.c
index 323973be2074..e89f0f0e604b 100644
--- a/kernel/locking/rtmutex.c
+++ b/kernel/locking/rtmutex.c
@@ -512,11 +512,19 @@ static __always_inline bool __pi_waiter_less(struct rb_node *a, const struct rb_
 	return rt_waiter_node_less(__node_2_rt_node(a), __node_2_rt_node(b));
 }
 
+/*
+ * Enqueue @waiter in the pi_waiters of @task, its lock's owner, with the
+ * sort keys of its lock tree copy, current under the wait_lock held here:
+ * the chain walk updates the tree copy of a waiter that is not the top
+ * waiter of its lock, and does not clone it, so a copy cloned before would
+ * enter @task's pi_waiters with the keys of a priority it no longer has.
+ */
 static __always_inline void
 rt_mutex_enqueue_pi(struct task_struct *task, struct rt_mutex_waiter *waiter)
 {
 	lockdep_assert_held(&task->pi_lock);
 
+	waiter_clone_prio(waiter, task);
 	rb_add_cached(&waiter->pi_tree.entry, &task->pi_waiters, __pi_waiter_less);
 }
 
@@ -1005,7 +1013,6 @@ static int __sched rt_mutex_adjust_prio_chain(struct task_struct *task,
 		 * and adjust the priority of the owner.
 		 */
 		rt_mutex_dequeue_pi(task, prerequeue_top_waiter);
-		waiter_clone_prio(waiter, task);
 		rt_mutex_enqueue_pi(task, waiter);
 		rt_mutex_adjust_prio(lock, task);
 
@@ -1022,7 +1029,6 @@ static int __sched rt_mutex_adjust_prio_chain(struct task_struct *task,
 		 */
 		rt_mutex_dequeue_pi(task, waiter);
 		waiter = rt_mutex_top_waiter(lock);
-		waiter_clone_prio(waiter, task);
 		rt_mutex_enqueue_pi(task, waiter);
 		rt_mutex_adjust_prio(lock, task);
 	} else {
@@ -1243,7 +1249,6 @@ static int __sched task_blocks_on_rt_mutex(struct rt_mutex_base *lock,
 	waiter->task = task;
 	waiter->lock = lock;
 	waiter_update_prio(waiter, task);
-	waiter_clone_prio(waiter, task);
 
 	/* Get the top priority waiter on the lock */
 	if (rt_mutex_has_waiters(lock))
-- 
2.47.3