futex: Handle early deadlock return correctly

commit 56222b212e8e ("futex: Drop hb->lock before enqueueing on the
rtmutex") changed the locking rules in the futex code so that the hash
bucket lock is not longer held while the waiter is enqueued into the
rtmutex wait list. This made the lock and the unlock path symmetric, but
unfortunately the possible early exit from __rt_mutex_proxy_start() due to
a detected deadlock was not updated accordingly. That allows a concurrent
unlocker to observe inconsitent state which triggers the warning in the
unlock path.

futex_lock_pi()                         futex_unlock_pi()
  lock(hb->lock)
  queue(hb_waiter)				lock(hb->lock)
  lock(rtmutex->wait_lock)
  unlock(hb->lock)
                                        // acquired hb->lock
                                        hb_waiter = futex_top_waiter()
                                        lock(rtmutex->wait_lock)
  __rt_mutex_proxy_start()
     ---> fail
          remove(rtmutex_waiter);
     ---> returns -EDEADLOCK
  unlock(rtmutex->wait_lock)
                                        // acquired wait_lock
                                        wake_futex_pi()
                                        rt_mutex_next_owner()
					  --> returns NULL
                                          --> WARN

  lock(hb->lock)
  unqueue(hb_waiter)

The problem is caused by the remove(rtmutex_waiter) in the failure case of
__rt_mutex_proxy_start() as this lets the unlocker observe a waiter in the
hash bucket but no waiter on the rtmutex, i.e. inconsistent state.

The original commit handles this correctly for the other early return cases
(timeout, signal) by delaying the removal of the rtmutex waiter until the
returning task reacquired the hash bucket lock.

Treat the failure case of __rt_mutex_proxy_start() in the same way and let
the existing cleanup code handle the eventual handover of the rtmutex
gracefully. The regular rt_mutex_proxy_start() gains the rtmutex waiter
removal for the failure case, so that the other callsites are still
operating correctly.

Add proper comments to the code so all these details are fully documented.

Thanks to Peter for helping with the analysis and writing the really
valuable code comments.

Fixes: 56222b212e8e ("futex: Drop hb->lock before enqueueing on the rtmutex")
Reported-by: Heiko Carstens <heiko.carstens@de.ibm.com>
Co-developed-by: Peter Zijlstra <peterz@infradead.org>
Signed-off-by: Peter Zijlstra <peterz@infradead.org>
Signed-off-by: Thomas Gleixner <tglx@linutronix.de>
Tested-by: Heiko Carstens <heiko.carstens@de.ibm.com>
Cc: Martin Schwidefsky <schwidefsky@de.ibm.com>
Cc: linux-s390@vger.kernel.org
Cc: Stefan Liebler <stli@linux.ibm.com>
Cc: Sebastian Sewior <bigeasy@linutronix.de>
Cc: stable@vger.kernel.org
Link: https://lkml.kernel.org/r/alpine.DEB.2.21.1901292311410.1950@nanos.tec.linutronix.de

1 files changed, 18 insertions, 10 deletions

diff --git a/kernel/futex.c b/kernel/futex.c
index 5ec2473a3497..a0514e01c3eb 100644
--- a/kernel/futex.c
+++ b/kernel/futex.c
@@ -2861,35 +2861,39 @@ retry_private:
          * and BUG when futex_unlock_pi() interleaves with this.
          *
          * Therefore acquire wait_lock while holding hb->lock, but drop the
-         * latter before calling rt_mutex_start_proxy_lock(). This still fully
-         * serializes against futex_unlock_pi() as that does the exact same
-         * lock handoff sequence.
+         * latter before calling __rt_mutex_start_proxy_lock(). This
+         * interleaves with futex_unlock_pi() -- which does a similar lock
+         * handoff -- such that the latter can observe the futex_q::pi_state
+         * before __rt_mutex_start_proxy_lock() is done.
          */
         raw_spin_lock_irq(&q.pi_state->pi_mutex.wait_lock);
         spin_unlock(q.lock_ptr);
+        /*
+         * __rt_mutex_start_proxy_lock() unconditionally enqueues the @rt_waiter
+         * such that futex_unlock_pi() is guaranteed to observe the waiter when
+         * it sees the futex_q::pi_state.
+         */
         ret = __rt_mutex_start_proxy_lock(&q.pi_state->pi_mutex, &rt_waiter, current);
         raw_spin_unlock_irq(&q.pi_state->pi_mutex.wait_lock);
 
         if (ret) {
                 if (ret == 1)
                         ret = 0;
-
-                spin_lock(q.lock_ptr);
-                goto no_block;
+                goto cleanup;
         }
 
-
         if (unlikely(to))
                 hrtimer_start_expires(&to->timer, HRTIMER_MODE_ABS);
 
         ret = rt_mutex_wait_proxy_lock(&q.pi_state->pi_mutex, to, &rt_waiter);
 
+cleanup:
         spin_lock(q.lock_ptr);
         /*
-         * If we failed to acquire the lock (signal/timeout), we must
+         * If we failed to acquire the lock (deadlock/signal/timeout), we must
          * first acquire the hb->lock before removing the lock from the
-         * rt_mutex waitqueue, such that we can keep the hb and rt_mutex
-         * wait lists consistent.
+         * rt_mutex waitqueue, such that we can keep the hb and rt_mutex wait
+         * lists consistent.
          *
          * In particular; it is important that futex_unlock_pi() can not
          * observe this inconsistency.
@@ -3013,6 +3017,10 @@ retry:
                  * there is no point where we hold neither; and therefore
                  * wake_futex_pi() must observe a state consistent with what we
                  * observed.
+                 *
+                 * In particular; this forces __rt_mutex_start_proxy() to
+                 * complete such that we're guaranteed to observe the
+                 * rt_waiter. Also see the WARN in wake_futex_pi().
                  */
                 raw_spin_lock_irq(&pi_state->pi_mutex.wait_lock);
                 spin_unlock(&hb->lock);