Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > linux.kernel > #1540917 > unrolled thread

[PATCH -v4 00/10] FUTEX_UNLOCK_PI wobbles

Back to article view | Back to linux.kernel

Contents

  [PATCH -v4 00/10] FUTEX_UNLOCK_PI wobbles Peter Zijlstra <peterz@infradead.org> - 2016-12-13 10:10 +0100
    [PATCH -v4 08/10] futex: Rework futex_lock_pi() vs rt_mutex_timed_futex_lock() Peter Zijlstra <peterz@infradead.org> - 2016-12-13 10:10 +0100
    [PATCH -v4 06/10] futex,rt_mutex: Provide futex specific rt_mutex API Peter Zijlstra <peterz@infradead.org> - 2016-12-13 10:10 +0100
    [PATCH -v4 03/10] futex: Cleanup variable names for futex_top_waiter() Peter Zijlstra <peterz@infradead.org> - 2016-12-13 10:10 +0100
      Re: [PATCH -v4 03/10] futex: Cleanup variable names for  futex_top_waiter() Darren Hart <dvhart@infradead.org> - 2016-12-17 01:20 +0100
    Re: [PATCH -v4 00/10] FUTEX_UNLOCK_PI wobbles Peter Zijlstra <peterz@infradead.org> - 2016-12-13 17:10 +0100
    Re: [PATCH -v4 00/10] FUTEX_UNLOCK_PI wobbles Darren Hart <dvhart@infradead.org> - 2016-12-17 00:40 +0100
      Re: [PATCH -v4 00/10] FUTEX_UNLOCK_PI wobbles Peter Zijlstra <peterz@infradead.org> - 2016-12-17 15:00 +0100
        Re: [PATCH -v4 00/10] FUTEX_UNLOCK_PI wobbles Darren Hart <dvhart@infradead.org> - 2016-12-18 23:40 +0100

#1540917 — [PATCH -v4 00/10] FUTEX_UNLOCK_PI wobbles

Hi all,

This is (I think) the 4th attempt at fixing this tiny pesky issue with
FUTEX_UNLOCK_PI, where we would really like to drop (and unboost) the rt_mutex
without holding hb->lock.

While going through the requeue PI code and thinking about how all that worked
I realized we can avoid the entire problem I've been trying to solve. That is,
the 'problem' is that futex state and rt_mutex state can end up disagreeing on
who is waiting for the lock and we muddle around that with intricate state.

This series, well patch 8, avoids the entire problem by making sure this
inconsistent state does not occur. Which then simplifies everything -- assuming
I got it right of course :-)

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.


In any case, it passes our inadequate testing.

[toc] | [next] | [standalone]

#1540918 — [PATCH -v4 08/10] futex: Rework futex_lock_pi() vs rt_mutex_timed_futex_lock()

Currently we must drop hb->lock in order to call
rt_mutex_timed_futex_lock(), such that it can block and wait for lock
acquisition.

The problem with this is that at this point (and after a failed
acquire but before re-acquiring hb->lock) the hb queue and rt_mutex
wait list disagree on who is waiting to acquire the futex. This leads
to a 'funny' state in wake_futex_pi() which we then need to deal with
in fixup_owner().

This inconsistent state would become even more of a problem when we
move rt_mutex_unlock() out from under hb->lock, which we want to do
because of PI inversion issues.

Avoid the funny state by reusing the
rt_mutex_{start,finish}_proxy_lock() primitives that were created for
requeue-pi.

The idea is to enqueue the rt_mutex_waiter on the rt_mutex wait list
before dropping the hb->lock, this is what rt_mutex_start_proxy_lock()
allows.

We must then wait for the lock with hb->lock dropped, _however_ we
must not do remove_waiter() in case the lock acquire fails, this means
we need to split rt_mutex_finish_proxy_lock() into two parts: wait and
cleanup.

With this done we can do something along the lines of:

	__queue_me();
	rt_mutex_start_proxy_lock();
	spin_unlock(q.lock_ptr);

	ret = rt_mutex_wait_proxy_lock();

	spin_lock(q.lock_ptr);
	if (ret)
		rt_mutex_cleanup_proxy_lock();

And the hb queue and rt_mutex wait lists are always in sync, with the
one except of rt_mutex_futex_unlock(), which removes the new owner
from the rt_mutex wait list which will remain on the hb queue until it
returns from rt_mutex_wait_proxy_lock().

This one case is fine, since unlock has no concurrency with itself.
That is, the new owner must finish and return from futex_lock_pi()
before it can do another unlock (through futex_unlock_pi()), at which
point its state is coherent again.

Signed-off-by: Peter Zijlstra (Intel) <peterz@infradead.org>
---
 kernel/futex.c                  |   78 ++++++++++++++++++++++++++++------------
 kernel/locking/rtmutex.c        |   47 +++++++++++++-----------
 kernel/locking/rtmutex_common.h |   10 +++--
 3 files changed, 88 insertions(+), 47 deletions(-)

--- a/kernel/futex.c
+++ b/kernel/futex.c
@@ -2088,20 +2088,7 @@ queue_unlock(struct futex_hash_bucket *h
 	hb_waiters_dec(hb);
 }
 
-/**
- * queue_me() - Enqueue the futex_q on the futex_hash_bucket
- * @q:	The futex_q to enqueue
- * @hb:	The destination hash bucket
- *
- * The hb->lock must be held by the caller, and is released here. A call to
- * queue_me() is typically paired with exactly one call to unqueue_me().  The
- * exceptions involve the PI related operations, which may use unqueue_me_pi()
- * or nothing if the unqueue is done as part of the wake process and the unqueue
- * state is implicit in the state of woken task (see futex_wait_requeue_pi() for
- * an example).
- */
-static inline void queue_me(struct futex_q *q, struct futex_hash_bucket *hb)
-	__releases(&hb->lock)
+static inline void __queue_me(struct futex_q *q, struct futex_hash_bucket *hb)
 {
 	int prio;
 
@@ -2118,6 +2105,24 @@ static inline void queue_me(struct futex
 	plist_node_init(&q->list, prio);
 	plist_add(&q->list, &hb->chain);
 	q->task = current;
+}
+
+/**
+ * queue_me() - Enqueue the futex_q on the futex_hash_bucket
+ * @q:	The futex_q to enqueue
+ * @hb:	The destination hash bucket
+ *
+ * The hb->lock must be held by the caller, and is released here. A call to
+ * queue_me() is typically paired with exactly one call to unqueue_me().  The
+ * exceptions involve the PI related operations, which may use unqueue_me_pi()
+ * or nothing if the unqueue is done as part of the wake process and the unqueue
+ * state is implicit in the state of woken task (see futex_wait_requeue_pi() for
+ * an example).
+ */
+static inline void queue_me(struct futex_q *q, struct futex_hash_bucket *hb)
+	__releases(&hb->lock)
+{
+	__queue_me(q, hb);
 	spin_unlock(&hb->lock);
 }
 
@@ -2593,6 +2598,7 @@ static int futex_lock_pi(u32 __user *uad
 			 ktime_t *time, int trylock)
 {
 	struct hrtimer_sleeper timeout, *to = NULL;
+	struct rt_mutex_waiter rt_waiter;
 	struct futex_hash_bucket *hb;
 	struct futex_q q = futex_q_init;
 	int res, ret;
@@ -2645,25 +2651,49 @@ static int futex_lock_pi(u32 __user *uad
 		}
 	}
 
+	WARN_ON(!q.pi_state);
+
 	/*
 	 * Only actually queue now that the atomic ops are done:
 	 */
-	queue_me(&q, hb);
+	__queue_me(&q, hb);
 
-	WARN_ON(!q.pi_state);
-	/*
-	 * Block on the PI mutex:
-	 */
-	if (!trylock) {
-		ret = rt_mutex_timed_futex_lock(&q.pi_state->pi_mutex, to);
-	} else {
+	debug_rt_mutex_init_waiter(&rt_waiter);
+	RB_CLEAR_NODE(&rt_waiter.pi_tree_entry);
+	RB_CLEAR_NODE(&rt_waiter.tree_entry);
+	rt_waiter.task = NULL;
+
+	if (trylock) {
 		ret = rt_mutex_futex_trylock(&q.pi_state->pi_mutex);
 		/* Fixup the trylock return value: */
 		ret = ret ? 0 : -EWOULDBLOCK;
+		goto did_trylock;
 	}
 
+	/*
+	 * We must add ourselves to the rt_mutex waitlist while holding hb->lock
+	 * such that the hb and rt_mutex wait lists match.
+	 */
+	rt_mutex_start_proxy_lock(&q.pi_state->pi_mutex, &rt_waiter, current);
+	spin_unlock(q.lock_ptr);
+
+	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);
+
 	spin_lock(q.lock_ptr);
 	/*
+	 * If we failed to acquire the lock (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.
+	 */
+	if (ret)
+		rt_mutex_cleanup_proxy_lock(&q.pi_state->pi_mutex, &rt_waiter);
+
+did_trylock:
+	/*
 	 * Fixup the pi_state owner and possibly acquire the lock if we
 	 * haven't already.
 	 */
@@ -3005,10 +3035,12 @@ static int futex_wait_requeue_pi(u32 __u
 		 */
 		WARN_ON(!q.pi_state);
 		pi_mutex = &q.pi_state->pi_mutex;
-		ret = rt_mutex_finish_proxy_lock(pi_mutex, to, &rt_waiter);
+		ret = rt_mutex_wait_proxy_lock(pi_mutex, to, &rt_waiter);
 		debug_rt_mutex_free_waiter(&rt_waiter);
 
 		spin_lock(q.lock_ptr);
+		if (ret)
+			rt_mutex_cleanup_proxy_lock(pi_mutex, &rt_waiter);
 		/*
 		 * 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
@@ -1485,19 +1485,6 @@ int __sched rt_mutex_lock_interruptible(
 EXPORT_SYMBOL_GPL(rt_mutex_lock_interruptible);
 
 /*
- * Futex variant with full deadlock detection.
- * Futex variants must not use the fast-path, see __rt_mutex_futex_unlock().
- */
-int __sched rt_mutex_timed_futex_lock(struct rt_mutex *lock,
-			      struct hrtimer_sleeper *timeout)
-{
-	might_sleep();
-
-	return rt_mutex_slowlock(lock, TASK_INTERRUPTIBLE,
-				 timeout, RT_MUTEX_FULL_CHAINWALK);
-}
-
-/*
  * Futex variant, must not use fastpath.
  */
 int __sched rt_mutex_futex_trylock(struct rt_mutex *lock)
@@ -1745,21 +1732,23 @@ struct task_struct *rt_mutex_next_owner(
 }
 
 /**
- * rt_mutex_finish_proxy_lock() - Complete lock acquisition
+ * rt_mutex_wait_proxy_lock() - Wait for lock acquisition
  * @lock:		the rt_mutex we were woken on
  * @to:			the timeout, null if none. hrtimer should already have
  *			been started.
  * @waiter:		the pre-initialized rt_mutex_waiter
  *
- * Complete the lock acquisition started our behalf by another thread.
+ * Wait for the the lock acquisition started on our behalf by
+ * rt_mutex_start_proxy_lock(). Upon failure, the caller must call
+ * rt_mutex_cleanup_proxy_lock().
  *
  * Returns:
  *  0 - success
  * <0 - error, one of -EINTR, -ETIMEDOUT
  *
- * Special API call for PI-futex requeue support
+ * Special API call for PI-futex support
  */
-int rt_mutex_finish_proxy_lock(struct rt_mutex *lock,
+int rt_mutex_wait_proxy_lock(struct rt_mutex *lock,
 			       struct hrtimer_sleeper *to,
 			       struct rt_mutex_waiter *waiter)
 {
@@ -1772,9 +1761,6 @@ int rt_mutex_finish_proxy_lock(struct rt
 	/* sleep on the mutex */
 	ret = __rt_mutex_slowlock(lock, TASK_INTERRUPTIBLE, to, waiter);
 
-	if (unlikely(ret))
-		remove_waiter(lock, waiter);
-
 	/*
 	 * try_to_take_rt_mutex() sets the waiter bit unconditionally. We might
 	 * have to fix that up.
@@ -1785,3 +1771,24 @@ int rt_mutex_finish_proxy_lock(struct rt
 
 	return ret;
 }
+
+/**
+ * rt_mutex_cleanup_proxy_lock() - Cleanup failed lock acquisition
+ * @lock:		the rt_mutex we were woken on
+ * @waiter:		the pre-initialized rt_mutex_waiter
+ *
+ * Clean up the failed lock acquisition as per rt_mutex_wait_proxy_lock().
+ *
+ * Special API call for PI-futex support
+ */
+void rt_mutex_cleanup_proxy_lock(struct rt_mutex *lock,
+				 struct rt_mutex_waiter *waiter)
+{
+	raw_spin_lock_irq(&lock->wait_lock);
+
+	remove_waiter(lock, waiter);
+	fixup_rt_mutex_waiters(lock);
+
+	raw_spin_unlock_irq(&lock->wait_lock);
+}
+
--- a/kernel/locking/rtmutex_common.h
+++ b/kernel/locking/rtmutex_common.h
@@ -105,11 +105,13 @@ extern void rt_mutex_proxy_unlock(struct
 extern int rt_mutex_start_proxy_lock(struct rt_mutex *lock,
 				     struct rt_mutex_waiter *waiter,
 				     struct task_struct *task);
-extern int rt_mutex_finish_proxy_lock(struct rt_mutex *lock,
-				      struct hrtimer_sleeper *to,
-				      struct rt_mutex_waiter *waiter);
 
-extern int rt_mutex_timed_futex_lock(struct rt_mutex *l, struct hrtimer_sleeper *to);
+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,
+				 struct rt_mutex_waiter *waiter);
+
 extern int rt_mutex_futex_trylock(struct rt_mutex *l);
 
 extern void rt_mutex_futex_unlock(struct rt_mutex *lock);

[toc] | [prev] | [next] | [standalone]

#1540919 — [PATCH -v4 06/10] futex,rt_mutex: Provide futex specific rt_mutex API

Part of what makes futex_unlock_pi() intricate is that
rt_mutex_futex_unlock() -> rt_mutex_slowunlock() can drop
rt_mutex::wait_lock.

This means we cannot rely on the atomicy of wait_lock, which we would
like to do in order to not rely on hb->lock so much.

The reason rt_mutex_slowunlock() needs to drop wait_lock is because it
can race with the rt_mutex fastpath, however futexes have their own
fast path.

Since futexes already have a bunch of separate rt_mutex accessors,
complete that set and implement a rt_mutex variant without fastpath
for them.

Signed-off-by: Peter Zijlstra (Intel) <peterz@infradead.org>
---
 kernel/futex.c                  |   30 ++++++++++-----------
 kernel/locking/rtmutex.c        |   55 +++++++++++++++++++++++++++++-----------
 kernel/locking/rtmutex_common.h |    9 +++++-
 3 files changed, 62 insertions(+), 32 deletions(-)

--- a/kernel/futex.c
+++ b/kernel/futex.c
@@ -914,7 +914,7 @@ void exit_pi_state_list(struct task_stru
 		pi_state->owner = NULL;
 		raw_spin_unlock_irq(&curr->pi_lock);
 
-		rt_mutex_unlock(&pi_state->pi_mutex);
+		rt_mutex_futex_unlock(&pi_state->pi_mutex);
 
 		spin_unlock(&hb->lock);
 
@@ -1362,20 +1362,18 @@ static int wake_futex_pi(u32 __user *uad
 	pi_state->owner = new_owner;
 	raw_spin_unlock(&new_owner->pi_lock);
 
-	raw_spin_unlock_irq(&pi_state->pi_mutex.wait_lock);
-
-	deboost = 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
-	 * deboost first (and lose our higher priority), then the task might get
-	 * scheduled away before the wake up can take place.
+	 * We've updated the uservalue, this unlock cannot fail.
 	 */
+	deboost = __rt_mutex_futex_unlock(&pi_state->pi_mutex, &wake_q);
+
+	raw_spin_unlock_irq(&pi_state->pi_mutex.wait_lock);
 	spin_unlock(&hb->lock);
-	wake_up_q(&wake_q);
-	if (deboost)
+
+	if (deboost) {
+		wake_up_q(&wake_q);
 		rt_mutex_adjust_prio(current);
+	}
 
 	return 0;
 }
@@ -2251,7 +2249,7 @@ static int fixup_owner(u32 __user *uaddr
 		 * task acquired the rt_mutex after we removed ourself from the
 		 * rt_mutex waiters list.
 		 */
-		if (rt_mutex_trylock(&q->pi_state->pi_mutex)) {
+		if (rt_mutex_futex_trylock(&q->pi_state->pi_mutex)) {
 			locked = 1;
 			goto out;
 		}
@@ -2566,7 +2564,7 @@ static int futex_lock_pi(u32 __user *uad
 	if (!trylock) {
 		ret = rt_mutex_timed_futex_lock(&q.pi_state->pi_mutex, to);
 	} else {
-		ret = rt_mutex_trylock(&q.pi_state->pi_mutex);
+		ret = rt_mutex_futex_trylock(&q.pi_state->pi_mutex);
 		/* Fixup the trylock return value: */
 		ret = ret ? 0 : -EWOULDBLOCK;
 	}
@@ -2589,7 +2587,7 @@ static int futex_lock_pi(u32 __user *uad
 	 * it and return the fault to userspace.
 	 */
 	if (ret && (rt_mutex_owner(&q.pi_state->pi_mutex) == current))
-		rt_mutex_unlock(&q.pi_state->pi_mutex);
+		rt_mutex_futex_unlock(&q.pi_state->pi_mutex);
 
 	/* Unqueue and drop the lock */
 	unqueue_me_pi(&q);
@@ -2896,7 +2894,7 @@ static int futex_wait_requeue_pi(u32 __u
 			spin_lock(q.lock_ptr);
 			ret = fixup_pi_state_owner(uaddr2, &q, current);
 			if (ret && rt_mutex_owner(&q.pi_state->pi_mutex) == current)
-				rt_mutex_unlock(&q.pi_state->pi_mutex);
+				rt_mutex_futex_unlock(&q.pi_state->pi_mutex);
 			/*
 			 * Drop the reference to the pi state which
 			 * the requeue_pi() code acquired for us.
@@ -2936,7 +2934,7 @@ static int futex_wait_requeue_pi(u32 __u
 		 * userspace.
 		 */
 		if (ret && rt_mutex_owner(pi_mutex) == current)
-			rt_mutex_unlock(pi_mutex);
+			rt_mutex_futex_unlock(pi_mutex);
 
 		/* Unqueue and drop the lock. */
 		unqueue_me_pi(&q);
--- a/kernel/locking/rtmutex.c
+++ b/kernel/locking/rtmutex.c
@@ -1486,15 +1486,23 @@ EXPORT_SYMBOL_GPL(rt_mutex_lock_interrup
 
 /*
  * Futex variant with full deadlock detection.
+ * Futex variants must not use the fast-path, see __rt_mutex_futex_unlock().
  */
-int rt_mutex_timed_futex_lock(struct rt_mutex *lock,
+int __sched rt_mutex_timed_futex_lock(struct rt_mutex *lock,
 			      struct hrtimer_sleeper *timeout)
 {
 	might_sleep();
 
-	return rt_mutex_timed_fastlock(lock, TASK_INTERRUPTIBLE, timeout,
-				       RT_MUTEX_FULL_CHAINWALK,
-				       rt_mutex_slowlock);
+	return rt_mutex_slowlock(lock, TASK_INTERRUPTIBLE,
+				 timeout, RT_MUTEX_FULL_CHAINWALK);
+}
+
+/*
+ * Futex variant, must not use fastpath.
+ */
+int __sched rt_mutex_futex_trylock(struct rt_mutex *lock)
+{
+	return rt_mutex_slowtrylock(lock);
 }
 
 /**
@@ -1553,19 +1561,38 @@ void __sched rt_mutex_unlock(struct rt_m
 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.
+ * Futex variant, that since futex variants do not use the fast-path, can be
+ * simple and will not need to retry.
  */
-bool __sched rt_mutex_futex_unlock(struct rt_mutex *lock,
-				   struct wake_q_head *wqh)
+bool __sched __rt_mutex_futex_unlock(struct rt_mutex *lock,
+				    struct wake_q_head *wake_q)
+{
+	lockdep_assert_held(&lock->wait_lock);
+
+	debug_rt_mutex_unlock(lock);
+
+	if (!rt_mutex_has_waiters(lock)) {
+		lock->owner = NULL;
+		return false; /* done */
+	}
+
+	mark_wakeup_next_waiter(wake_q, lock);
+	return true; /* deboost and wakeups */
+}
+
+void __sched rt_mutex_futex_unlock(struct rt_mutex *lock)
 {
-	if (likely(rt_mutex_cmpxchg_release(lock, current, NULL)))
-		return false;
+	DEFINE_WAKE_Q(wake_q);
+	bool deboost;
 
-	return rt_mutex_slowunlock(lock, wqh);
+	raw_spin_lock_irq(&lock->wait_lock);
+	deboost = __rt_mutex_futex_unlock(lock, &wake_q);
+	raw_spin_unlock_irq(&lock->wait_lock);
+
+	if (deboost) {
+		wake_up_q(&wake_q);
+		rt_mutex_adjust_prio(current);
+	}
 }
 
 /**
--- a/kernel/locking/rtmutex_common.h
+++ b/kernel/locking/rtmutex_common.h
@@ -108,9 +108,14 @@ extern int rt_mutex_start_proxy_lock(str
 extern int rt_mutex_finish_proxy_lock(struct rt_mutex *lock,
 				      struct hrtimer_sleeper *to,
 				      struct rt_mutex_waiter *waiter);
+
 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 int rt_mutex_futex_trylock(struct rt_mutex *l);
+
+extern void rt_mutex_futex_unlock(struct rt_mutex *lock);
+extern bool __rt_mutex_futex_unlock(struct rt_mutex *lock,
+				 struct wake_q_head *wqh);
+
 extern void rt_mutex_adjust_prio(struct task_struct *task);
 
 #ifdef CONFIG_DEBUG_RT_MUTEXES

[toc] | [prev] | [next] | [standalone]

#1540920 — [PATCH -v4 03/10] futex: Cleanup variable names for futex_top_waiter()

futex_top_waiter() returns the top-waiter on the pi_mutex. Assinging
this to a variable 'match' totally obscures the code.

Signed-off-by: Peter Zijlstra (Intel) <peterz@infradead.org>
---
 kernel/futex.c |   30 +++++++++++++++---------------
 1 file changed, 15 insertions(+), 15 deletions(-)

--- a/kernel/futex.c
+++ b/kernel/futex.c
@@ -1120,14 +1120,14 @@ static int attach_to_pi_owner(u32 uval,
 static int lookup_pi_state(u32 uval, struct futex_hash_bucket *hb,
 			   union futex_key *key, struct futex_pi_state **ps)
 {
-	struct futex_q *match = futex_top_waiter(hb, key);
+	struct futex_q *top_waiter = futex_top_waiter(hb, key);
 
 	/*
 	 * If there is a waiter on that futex, validate it and
 	 * attach to the pi_state when the validation succeeds.
 	 */
-	if (match)
-		return attach_to_pi_state(uval, match->pi_state, ps);
+	if (top_waiter)
+		return attach_to_pi_state(uval, top_waiter->pi_state, ps);
 
 	/*
 	 * We are the first waiter - try to look up the owner based on
@@ -1174,7 +1174,7 @@ static int futex_lock_pi_atomic(u32 __us
 				struct task_struct *task, int set_waiters)
 {
 	u32 uval, newval, vpid = task_pid_vnr(task);
-	struct futex_q *match;
+	struct futex_q *top_waiter;
 	int ret;
 
 	/*
@@ -1200,9 +1200,9 @@ static int futex_lock_pi_atomic(u32 __us
 	 * Lookup existing state first. If it exists, try to attach to
 	 * its pi_state.
 	 */
-	match = futex_top_waiter(hb, key);
-	if (match)
-		return attach_to_pi_state(uval, match->pi_state, ps);
+	top_waiter = futex_top_waiter(hb, key);
+	if (top_waiter)
+		return attach_to_pi_state(uval, top_waiter->pi_state, ps);
 
 	/*
 	 * No waiter and user TID is 0. We are here because the
@@ -1292,11 +1292,11 @@ static void mark_wake_futex(struct wake_
 	q->lock_ptr = NULL;
 }
 
-static int wake_futex_pi(u32 __user *uaddr, u32 uval, struct futex_q *this,
+static int wake_futex_pi(u32 __user *uaddr, u32 uval, struct futex_q *top_waiter,
 			 struct futex_hash_bucket *hb)
 {
 	struct task_struct *new_owner;
-	struct futex_pi_state *pi_state = this->pi_state;
+	struct futex_pi_state *pi_state = top_waiter->pi_state;
 	u32 uninitialized_var(curval), newval;
 	DEFINE_WAKE_Q(wake_q);
 	bool deboost;
@@ -1317,11 +1317,11 @@ static int wake_futex_pi(u32 __user *uad
 
 	/*
 	 * It is possible that the next waiter (the one that brought
-	 * this owner to the kernel) timed out and is no longer
+	 * top_waiter owner to the kernel) timed out and is no longer
 	 * waiting on the lock.
 	 */
 	if (!new_owner)
-		new_owner = this->task;
+		new_owner = top_waiter->task;
 
 	/*
 	 * We pass it to the next owner. The WAITERS bit is always
@@ -2631,7 +2631,7 @@ static int futex_unlock_pi(u32 __user *u
 	u32 uninitialized_var(curval), uval, vpid = task_pid_vnr(current);
 	union futex_key key = FUTEX_KEY_INIT;
 	struct futex_hash_bucket *hb;
-	struct futex_q *match;
+	struct futex_q *top_waiter;
 	int ret;
 
 retry:
@@ -2655,9 +2655,9 @@ static int futex_unlock_pi(u32 __user *u
 	 * all and we at least want to know if user space fiddled
 	 * with the futex value instead of blindly unlocking.
 	 */
-	match = futex_top_waiter(hb, &key);
-	if (match) {
-		ret = wake_futex_pi(uaddr, uval, match, hb);
+	top_waiter = futex_top_waiter(hb, &key);
+	if (top_waiter) {
+		ret = wake_futex_pi(uaddr, uval, top_waiter, hb);
 		/*
 		 * In case of success wake_futex_pi dropped the hash
 		 * bucket lock.

[toc] | [prev] | [next] | [standalone]

#1543857 — Re: [PATCH -v4 03/10] futex: Cleanup variable names for futex_top_waiter()

On Tue, Dec 13, 2016 at 09:36:41AM +0100, Peter Zijlstra wrote:
> futex_top_waiter() returns the top-waiter on the pi_mutex. Assinging
> this to a variable 'match' totally obscures the code.
> 

Yes please.

One wording nit...

> Signed-off-by: Peter Zijlstra (Intel) <peterz@infradead.org>
> ---
>  kernel/futex.c |   30 +++++++++++++++---------------
>  1 file changed, 15 insertions(+), 15 deletions(-)
> 
> --- a/kernel/futex.c
> +++ b/kernel/futex.c

> @@ -1317,11 +1317,11 @@ static int wake_futex_pi(u32 __user *uad
>  
>  	/*
>  	 * It is possible that the next waiter (the one that brought
> -	 * this owner to the kernel) timed out and is no longer
> +	 * top_waiter owner to the kernel) timed out and is no longer
>  	 * waiting on the lock.
>  	 */

This breaks my parser (and did before too).

Consider:

/*
 * It is possible that the next waiter (that caused top_waiter to call
 * into the kernel) has since timed out and is no longer waiting on the
 * lock.
 */

Is that clearer?

-- 
Darren Hart
Intel Open Source Technology Center

[toc] | [prev] | [next] | [standalone]

#1541215

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);

[toc] | [prev] | [next] | [standalone]

#1543850

On Tue, Dec 13, 2016 at 09:36:38AM +0100, Peter Zijlstra wrote:
> 
> Hi all,
> 
> This is (I think) the 4th attempt at fixing this tiny pesky issue with
> FUTEX_UNLOCK_PI, where we would really like to drop (and unboost) the rt_mutex
> without holding hb->lock.
> 
> While going through the requeue PI code and thinking about how all that worked
> I realized we can avoid the entire problem I've been trying to solve. That is,
> the 'problem' is that futex state and rt_mutex state can end up disagreeing on
> who is waiting for the lock and we muddle around that with intricate state.
> 
> This series, well patch 8, avoids the entire problem by making sure this
> inconsistent state does not occur. Which then simplifies everything -- assuming
> I got it right of course :-)
> 
> 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.

Oh boy, this is going to take some brain space/time. I'll comment as I work
through them and ask questions - to keep the dialog going.

> 
> That way, when we drop hb->lock to wait, futex and rt_mutex wait state is
> consistent.
> 
> 
> In any case, it passes our inadequate testing.

It passed my CI tools/testing/selftests/futex/functional/run.sh. Did you also
happen to run a fuzz tester?

-- 
Darren Hart
Intel Open Source Technology Center

[toc] | [prev] | [next] | [standalone]

#1543972

On Fri, Dec 16, 2016 at 03:31:40PM -0800, Darren Hart wrote:
> On Tue, Dec 13, 2016 at 09:36:38AM +0100, Peter Zijlstra wrote:
> > That way, when we drop hb->lock to wait, futex and rt_mutex wait state is
> > consistent.
> > 
> > 
> > In any case, it passes our inadequate testing.
> 
> It passed my CI tools/testing/selftests/futex/functional/run.sh. Did you also
> happen to run a fuzz tester?

I did not. I'm not sure how good trinity is at poking holes in futexes.
I would love a domain specific fuzzer for futex, but I suspect it would
end up being me writing it :-(

[toc] | [prev] | [next] | [standalone]

#1544215

On Sat, Dec 17, 2016 at 02:52:14PM +0100, Peter Zijlstra wrote:
> On Fri, Dec 16, 2016 at 03:31:40PM -0800, Darren Hart wrote:
> > On Tue, Dec 13, 2016 at 09:36:38AM +0100, Peter Zijlstra wrote:
> > > That way, when we drop hb->lock to wait, futex and rt_mutex wait state is
> > > consistent.
> > > 
> > > 
> > > In any case, it passes our inadequate testing.
> > 
> > It passed my CI tools/testing/selftests/futex/functional/run.sh. Did you also
> > happen to run a fuzz tester?
> 
> I did not. I'm not sure how good trinity is at poking holes in futexes.
> I would love a domain specific fuzzer for futex, but I suspect it would
> end up being me writing it :-(
> 

Trinity had some futex awareness and found several issues in the past, I can't
say how likely it is to find more. I haven't tried ... syzcaller? yet.

I had set out to do this in the futextest suite, which I later merged into
kselftests, but I scrapped the fuzz testing, deferring to trinity. Perhaps that
is a project we should resurrect.

-- 
Darren Hart
Intel Open Source Technology Center

[toc] | [prev] | [standalone]

Back to top | Article view | linux.kernel

csiph-web