[PATCH v2 3/5] locking/rtmutex: Clone the sort keys in rt_mutex_enqueue_pi()

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

An rt_mutex waiter has two copies of its sort keys. waiter->tree sorts
the waiters of its lock. waiter->pi_tree sorts the pi_waiters of the
lock owner. Only the top waiter of each lock is in pi_waiters.

When the priority of a waiter changes, the chain walk updates
waiter->tree. It copies waiter->tree to waiter->pi_tree for the top
waiter only. A waiter that is not the top waiter keeps its old pi_tree
keys.

Such a waiter can become the top waiter later. remove_waiter() does this
when the top waiter leaves. try_to_take_rt_mutex() does it when the lock
changes owner. Both put the new top waiter in pi_waiters without a new
copy. So pi_waiters sorts it by a priority it no longer has. The owner
then inherits from the wrong waiter, at that waiter's current priority.

In this example, O is the owner, a SCHED_OTHER task. L1 and L2 are two
rt_mutexes. W1, W2 and W3 are waiters. Their SCHED_FIFO priority is
under their name. T is any other task. It changes the priority of W2:

  T                         O                W1                            W2           W3
                                             FIFO 80                       FIFO 70      FIFO 50

                            locks L1, L2
                                                                                        blocks on L2
                                             blocks on L1 (timed)
                                                                           blocks on L1
  sched_setscheduler(W2)
    W2 now at FIFO 10
    rt_mutex_adjust_pi(W2)
      W2->tree: FIFO 10
      W2 not top: no copy
      W2->pi_tree: FIFO 70
                                             <timeout>
                                             remove_waiter()
                                               rt_mutex_enqueue_pi(O, W2)
                                                 W2 sorted as FIFO 70,
                                                 ahead of W3
                                               rt_mutex_adjust_prio(O)
                                                 O inherits W2's FIFO 10
                            runs at FIFO 10                                             still waits

The owner runs at SCHED_FIFO 10 while a SCHED_FIFO 50 task waits for
it. This needs no race. Each step can come long after the one before.

Fix this by copying the keys in rt_mutex_enqueue_pi(). All callers hold
the wait_lock and the owner's pi_lock, as waiter_clone_prio() requires.
Remove the three copies the callers made.

With this patch, the owner runs at SCHED_FIFO 50. The
futex_lock_pi_inherit selftest added later in this series tests this
case (promoted_waiter).

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 | 5 ++---
 1 file changed, 2 insertions(+), 3 deletions(-)

diff --git a/kernel/locking/rtmutex.c b/kernel/locking/rtmutex.c
index 323973be2074..975efa1d864c 100644
--- a/kernel/locking/rtmutex.c
+++ b/kernel/locking/rtmutex.c
@@ -517,6 +517,8 @@ rt_mutex_enqueue_pi(struct task_struct *task, struct rt_mutex_waiter *waiter)
 {
 	lockdep_assert_held(&task->pi_lock);
 
+	/* The tree keys can change while @waiter is not in pi_waiters. */
+	waiter_clone_prio(waiter, task);
 	rb_add_cached(&waiter->pi_tree.entry, &task->pi_waiters, __pi_waiter_less);
 }
 
@@ -1005,7 +1007,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 +1023,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 +1243,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