Re: [PATCH -v4 00/10] FUTEX_UNLOCK_PI wobbles

[Peter Zijlstra <peterz@infradead.org>]

On Tue, Dec 13, 2016 at 09:36:38AM +0100, Peter Zijlstra wrote:

> The basic idea is to, like requeue PI, break the rt_mutex_lock() function into
> pieces, such that we can enqueue the waiter while holding hb->lock, wait for
> acquisition without hb->lock and can remove the waiter, on failure, while
> holding hb->lock again.
> 
> That way, when we drop hb->lock to wait, futex and rt_mutex wait state is
> consistent.

And of course, there's a hole in...

There is a point in futex_unlock_pi() where we hold neither hb->lock nor
wait_lock, at that point a futex_lock_pi() that had failed its
rt_mutex_wait_proxy_lock() can sneak in and remove itself, even though
we saw its waiter, recreating a vraiant of the initial problem.

The below plugs the hole, but its rather fragile in that it relies on
overlapping critical sections and the specific detail that we call
rt_mutex_cleanup_proxy_lock() immediately after (re)acquiring hb->lock.

There is another solution, but that's more involved and uglier still.

I'll give it a bit more thought.


---
 kernel/futex.c                  |   36 +++++++++++++++++++++++++-----------
 kernel/locking/rtmutex.c        |   21 ++++++++++++++++++---
 kernel/locking/rtmutex_common.h |    2 +-
 3 files changed, 44 insertions(+), 15 deletions(-)

--- a/kernel/futex.c
+++ b/kernel/futex.c
@@ -1384,6 +1384,7 @@ static void mark_wake_futex(struct wake_
 }
 
 static int wake_futex_pi(u32 __user *uaddr, u32 uval, struct futex_pi_state *pi_state)
+	__releases(&pi_state->pi_mutex.wait_lock)
 {
 	u32 uninitialized_var(curval), newval;
 	struct task_struct *new_owner;
@@ -1391,7 +1392,8 @@ static int wake_futex_pi(u32 __user *uad
 	DEFINE_WAKE_Q(wake_q);
 	int ret = 0;
 
-	raw_spin_lock_irq(&pi_state->pi_mutex.wait_lock);
+	lockdep_assert_held(&pi_state->pi_mutex.wait_lock);
+
 	new_owner = rt_mutex_next_owner(&pi_state->pi_mutex);
 	BUG_ON(!new_owner);
 
@@ -2655,8 +2657,8 @@ static int futex_lock_pi(u32 __user *uad
 	 * rt_mutex waitqueue, such that we can keep the hb and rt_mutex
 	 * wait lists consistent.
 	 */
-	if (ret)
-		rt_mutex_cleanup_proxy_lock(&q.pi_state->pi_mutex, &rt_waiter);
+	if (ret && !rt_mutex_cleanup_proxy_lock(&q.pi_state->pi_mutex, &rt_waiter))
+		ret = 0;
 
 did_trylock:
 	/*
@@ -2763,15 +2765,26 @@ static int futex_unlock_pi(u32 __user *u
 		if (pi_state->owner != current)
 			goto out_unlock;
 
+		get_pi_state(pi_state);
+
 		/*
-		 * Grab a reference on the pi_state and drop hb->lock.
+		 * We must grab wait_lock _before_ dropping hb->lock, such that
+		 * the critical sections overlap. Without this there is a hole
+		 * in which futex_lock_pi()'s rt_mutex_wait_proxy_lock() can
+		 * fail, re-acquire the hb->lock and wait_lock and have our
+		 * top_waiter dissapear.
+		 */
+		raw_spin_lock_irq(&pi_state->pi_mutex.wait_lock);
+		/*
+		 * Now that we have a reference on pi_state and hole wait_lock
+		 * we can drop hb->lock without risk of a waiter dissapearing
+		 * on us.
 		 *
-		 * The reference ensures pi_state lives, dropping the hb->lock
-		 * is tricky.. wake_futex_pi() will take rt_mutex::wait_lock to
-		 * close the races against futex_lock_pi(), but in case of
-		 * _any_ fail we'll abort and retry the whole deal.
+		 * Even if rt_mutex_wait_proxy_lock() fails, us holding
+		 * wait_lock ensures it cannot be removed and the
+		 * rt_mutex_cleanup_proxy_lock() call will find it owns the
+		 * lock anyway.
 		 */
-		get_pi_state(pi_state);
 		spin_unlock(&hb->lock);
 
 		ret = wake_futex_pi(uaddr, uval, pi_state);
@@ -3041,8 +3054,9 @@ static int futex_wait_requeue_pi(u32 __u
 		debug_rt_mutex_free_waiter(&rt_waiter);
 
 		spin_lock(q.lock_ptr);
-		if (ret)
-			rt_mutex_cleanup_proxy_lock(pi_mutex, &rt_waiter);
+		if (ret && !rt_mutex_cleanup_proxy_lock(pi_mutex, &rt_waiter))
+			ret = 0;
+
 		/*
 		 * Fixup the pi_state owner and possibly acquire the lock if we
 		 * haven't already.
--- a/kernel/locking/rtmutex.c
+++ b/kernel/locking/rtmutex.c
@@ -1779,16 +1779,31 @@ int rt_mutex_wait_proxy_lock(struct rt_m
  *
  * Clean up the failed lock acquisition as per rt_mutex_wait_proxy_lock().
  *
+ * Returns:
+ *  true - did cleanup, we done.
+ *  false - we acquired the lock anyway, after rt_mutex_wait_proxy_lock(),
+ *          caller should disregard its return value.
+ *
  * Special API call for PI-futex support
  */
-void rt_mutex_cleanup_proxy_lock(struct rt_mutex *lock,
+bool rt_mutex_cleanup_proxy_lock(struct rt_mutex *lock,
 				 struct rt_mutex_waiter *waiter)
 {
+	bool cleanup = false;
+
 	raw_spin_lock_irq(&lock->wait_lock);
 
-	remove_waiter(lock, waiter);
-	fixup_rt_mutex_waiters(lock);
+	/*
+	 * Check if we got the lock anyway...
+	 */
+	if (rt_mutex_owner(lock) != current) {
+		remove_waiter(lock, waiter);
+		fixup_rt_mutex_waiters(lock);
+		cleanup = true;
+	}
 
 	raw_spin_unlock_irq(&lock->wait_lock);
+
+	return cleanup;
 }
 
--- a/kernel/locking/rtmutex_common.h
+++ b/kernel/locking/rtmutex_common.h
@@ -109,7 +109,7 @@ extern int rt_mutex_start_proxy_lock(str
 extern int rt_mutex_wait_proxy_lock(struct rt_mutex *lock,
 			       struct hrtimer_sleeper *to,
 			       struct rt_mutex_waiter *waiter);
-extern void rt_mutex_cleanup_proxy_lock(struct rt_mutex *lock,
+extern bool rt_mutex_cleanup_proxy_lock(struct rt_mutex *lock,
 				 struct rt_mutex_waiter *waiter);
 
 extern int rt_mutex_futex_trylock(struct rt_mutex *l);