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

Groups > linux.kernel > #1494775 > unrolled thread

[RFC][PATCH 0/4] FUTEX_UNLOCK_PI wobbles

Back to article view | Back to linux.kernel

Contents

  [RFC][PATCH 0/4] FUTEX_UNLOCK_PI wobbles Peter Zijlstra <peterz@infradead.org> - 2016-10-03 11:30 +0200
    [RFC][PATCH 4/4] futex: Rewrite FUTEX_UNLOCK_PI Peter Zijlstra <peterz@infradead.org> - 2016-10-03 11:30 +0200
      Re: [RFC][PATCH 4/4] futex: Rewrite FUTEX_UNLOCK_PI Steven Rostedt <rostedt@goodmis.org> - 2016-10-03 17:40 +0200
        Re: [RFC][PATCH 4/4] futex: Rewrite FUTEX_UNLOCK_PI Peter Zijlstra <peterz@infradead.org> - 2016-10-03 17:50 +0200
          Re: [RFC][PATCH 4/4] futex: Rewrite FUTEX_UNLOCK_PI Steven Rostedt <rostedt@goodmis.org> - 2016-10-03 18:30 +0200
        Re: [RFC][PATCH 4/4] futex: Rewrite FUTEX_UNLOCK_PI Peter Zijlstra <peterz@infradead.org> - 2016-10-03 17:50 +0200
      Re: [RFC][PATCH 4/4] futex: Rewrite FUTEX_UNLOCK_PI Sebastian Andrzej Siewior <bigeasy@linutronix.de> - 2016-10-05 09:50 +0200
        Re: [RFC][PATCH 4/4] futex: Rewrite FUTEX_UNLOCK_PI Peter Zijlstra <peterz@infradead.org> - 2016-10-05 10:10 +0200
          Re: [RFC][PATCH 4/4] futex: Rewrite FUTEX_UNLOCK_PI Sebastian Andrzej Siewior <bigeasy@linutronix.de> - 2016-10-05 10:30 +0200
            Re: [RFC][PATCH 4/4] futex: Rewrite FUTEX_UNLOCK_PI Peter Zijlstra <peterz@infradead.org> - 2016-10-05 10:40 +0200
      Re: [RFC][PATCH 4/4] futex: Rewrite FUTEX_UNLOCK_PI Peter Zijlstra <peterz@infradead.org> - 2016-10-06 12:30 +0200
      Re: [RFC][PATCH 4/4] futex: Rewrite FUTEX_UNLOCK_PI Peter Zijlstra <peterz@infradead.org> - 2016-10-07 13:30 +0200
        Re: [RFC][PATCH 4/4] futex: Rewrite FUTEX_UNLOCK_PI Thomas Gleixner <tglx@linutronix.de> - 2016-10-08 18:00 +0200
          Re: [RFC][PATCH 4/4] futex: Rewrite FUTEX_UNLOCK_PI Peter Zijlstra <peterz@infradead.org> - 2016-10-08 19:00 +0200
            Re: [RFC][PATCH 4/4] futex: Rewrite FUTEX_UNLOCK_PI Thomas Gleixner <tglx@linutronix.de> - 2016-10-08 19:10 +0200
            Re: [RFC][PATCH 4/4] futex: Rewrite FUTEX_UNLOCK_PI Thomas Gleixner <tglx@linutronix.de> - 2016-10-10 12:30 +0200
              Re: [RFC][PATCH 4/4] futex: Rewrite FUTEX_UNLOCK_PI Peter Zijlstra <peterz@infradead.org> - 2016-10-10 13:50 +0200
        Re: [RFC][PATCH 4/4] futex: Rewrite FUTEX_UNLOCK_PI Thomas Gleixner <tglx@linutronix.de> - 2016-10-08 20:30 +0200
        Re: [RFC][PATCH 4/4] futex: Rewrite FUTEX_UNLOCK_PI Thomas Gleixner <tglx@linutronix.de> - 2016-10-09 13:30 +0200
          Re: [RFC][PATCH 4/4] futex: Rewrite FUTEX_UNLOCK_PI Peter Zijlstra <peterz@infradead.org> - 2016-10-10 16:10 +0200
    [RFC][PATCH 1/4] futex: Cleanup variable names for futex_top_waiter() Peter Zijlstra <peterz@infradead.org> - 2016-10-03 11:30 +0200
      Re: [RFC][PATCH 1/4] futex: Cleanup variable names for  futex_top_waiter() Steven Rostedt <rostedt@goodmis.org> - 2016-10-03 16:20 +0200
      Re: [RFC][PATCH 1/4] futex: Cleanup variable names for  futex_top_waiter() Davidlohr Bueso <dave@stgolabs.net> - 2016-10-05 06:00 +0200
    [RFC][PATCH 3/4] futex: Remove rt_mutex_deadlock_account_*() Peter Zijlstra <peterz@infradead.org> - 2016-10-03 11:30 +0200
      Re: [RFC][PATCH 3/4] futex: Remove rt_mutex_deadlock_account_*() Peter Zijlstra <peterz@infradead.org> - 2016-10-03 11:40 +0200
      Re: [RFC][PATCH 3/4] futex: Remove rt_mutex_deadlock_account_*() Steven Rostedt <rostedt@goodmis.org> - 2016-10-03 16:30 +0200
      Re: [RFC][PATCH 3/4] futex: Remove rt_mutex_deadlock_account_*() Davidlohr Bueso <dave@stgolabs.net> - 2016-10-05 03:10 +0200
      Re: [RFC][PATCH 3/4] futex: Remove rt_mutex_deadlock_account_*() Sebastian Andrzej Siewior <bigeasy@linutronix.de> - 2016-10-05 09:40 +0200
    Re: [RFC][PATCH 0/4] FUTEX_UNLOCK_PI wobbles Davidlohr Bueso <dave@stgolabs.net> - 2016-10-05 03:10 +0200
      Re: [RFC][PATCH 0/4] FUTEX_UNLOCK_PI wobbles Peter Zijlstra <peterz@infradead.org> - 2016-10-05 08:30 +0200
        Re: [RFC][PATCH 0/4] FUTEX_UNLOCK_PI wobbles Sebastian Andrzej Siewior <bigeasy@linutronix.de> - 2016-10-05 09:30 +0200
        Re: [RFC][PATCH 0/4] FUTEX_UNLOCK_PI wobbles Davidlohr Bueso <dave@stgolabs.net> - 2016-10-05 18:10 +0200

Page 1 of 2  [1] 2  Next page →

#1494775 — [RFC][PATCH 0/4] FUTEX_UNLOCK_PI wobbles

Hi,

During my last PI failing patch set it became obvious there's a number of
related fail in FUTEX_UNLOCK_PI that needed sorting before we can move on
with that stuff.

These here patches are the result of staring at that code for a wee bit.

Please have a very _very_ careful look at the last patch, it appears to not
explode when running:

  - perf bench futex lock-pi
  - selftests/futex

but given the immense amount of tricky involved with both PI and futex there is
bound to be something I've overlooked.

Do people have more/better futex-pi test cases?

[toc] | [next] | [standalone]

#1494779 — [RFC][PATCH 4/4] futex: Rewrite FUTEX_UNLOCK_PI

There's a number of 'interesting' problems with FUTEX_UNLOCK_PI, all
caused by holding hb->lock while doing the rt_mutex_unlock()
equivalient.

This patch doesn't attempt to fix any of the actual problems, but
instead reworks the code to not hold hb->lock across the unlock,
paving the way to actually fix the problems later.

The current reason we hold hb->lock over unlock is that it serializes
against FUTEX_LOCK_PI and avoids new waiters from coming in, this then
ensures the rt_mutex_next_owner() value is stable and can be written
into the user-space futex value before doing the unlock. Such that the
unlock will indeed end up at new_owner.

This patch recognises that holding rt_mutex::wait_lock results in the
very same guarantee, no new waiters can come in while we hold that
lock -- after all, waiters would need this lock to queue themselves.

It therefore restructures the code to keep rt_mutex::wait_lock held.

This (of course) is not entirely straight forward either, see the
comment in rt_mutex_slowunlock(), doing the unlock itself might drop
wait_lock, letting new waiters in. To cure this
rt_mutex_futex_unlock() becomes a variant of rt_mutex_slowunlock()
that return -EAGAIN instead. This ensures the FUTEX_UNLOCK_PI code
aborts and restarts the entire operation.

Signed-off-by: Peter Zijlstra (Intel) <peterz@infradead.org>
---
 kernel/futex.c                  |   63 +++++++++++++++++--------------
 kernel/locking/rtmutex.c        |   81 ++++++++++++++++++++++++++++++++++++----
 kernel/locking/rtmutex_common.h |    4 -
 3 files changed, 110 insertions(+), 38 deletions(-)

--- a/kernel/futex.c
+++ b/kernel/futex.c
@@ -1294,24 +1294,21 @@ static void mark_wake_futex(struct wake_
 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 = top_waiter->pi_state;
 	u32 uninitialized_var(curval), newval;
+	struct task_struct *new_owner;
 	WAKE_Q(wake_q);
-	bool deboost;
 	int ret = 0;
 
-	if (!pi_state)
-		return -EINVAL;
+	raw_spin_lock_irq(&pi_state->pi_mutex.wait_lock);
 
+	WARN_ON_ONCE(!atomic_inc_not_zero(&pi_state->refcount));
 	/*
-	 * If current does not own the pi_state then the futex is
-	 * inconsistent and user space fiddled with the futex value.
+	 * Now that we hold wait_lock, no new waiters can happen on the
+	 * rt_mutex and new owner is stable. Drop hb->lock.
 	 */
-	if (pi_state->owner != current)
-		return -EINVAL;
+	spin_unlock(&hb->lock);
 
-	raw_spin_lock_irq(&pi_state->pi_mutex.wait_lock);
 	new_owner = rt_mutex_next_owner(&pi_state->pi_mutex);
 
 	/*
@@ -1334,6 +1331,7 @@ static int wake_futex_pi(u32 __user *uad
 
 	if (cmpxchg_futex_value_locked(&curval, uaddr, uval, newval)) {
 		ret = -EFAULT;
+
 	} else if (curval != uval) {
 		/*
 		 * If a unconditional UNLOCK_PI operation (user space did not
@@ -1346,10 +1344,9 @@ static int wake_futex_pi(u32 __user *uad
 		else
 			ret = -EINVAL;
 	}
-	if (ret) {
-		raw_spin_unlock_irq(&pi_state->pi_mutex.wait_lock);
-		return ret;
-	}
+
+	if (ret)
+		goto out_unlock;
 
 	raw_spin_lock(&pi_state->owner->pi_lock);
 	WARN_ON(list_empty(&pi_state->list));
@@ -1362,22 +1359,20 @@ 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);
+	ret = rt_mutex_futex_unlock(&pi_state->pi_mutex, &wake_q);
 
-	deboost = rt_mutex_futex_unlock(&pi_state->pi_mutex, &wake_q);
+out_unlock:
+	raw_spin_unlock_irq(&pi_state->pi_mutex.wait_lock);
 
-	/*
-	 * 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.
-	 */
-	spin_unlock(&hb->lock);
-	wake_up_q(&wake_q);
-	if (deboost)
+	if (ret > 0) {
+		wake_up_q(&wake_q);
 		rt_mutex_adjust_prio(current);
+		ret = 0;
+	}
 
-	return 0;
+	put_pi_state(pi_state);
+
+	return ret;
 }
 
 /*
@@ -2656,6 +2651,20 @@ static int futex_unlock_pi(u32 __user *u
 	 */
 	top_waiter = futex_top_waiter(hb, &key);
 	if (top_waiter) {
+
+		if (!top_waiter->pi_state)
+			goto out_unlock;
+
+		/*
+		 * If current does not own the pi_state then the futex is
+		 * inconsistent and user space fiddled with the futex value.
+		 */
+		if (top_waiter->pi_state->owner != current)
+			goto out_unlock;
+
+		/*
+		 * wait_futex_pi() _will_ drop hb->lock
+		 */
 		ret = wake_futex_pi(uaddr, uval, top_waiter, hb);
 		/*
 		 * In case of success wake_futex_pi dropped the hash
@@ -2674,7 +2683,6 @@ static int futex_unlock_pi(u32 __user *u
 		 * setting the FUTEX_WAITERS bit. Try again.
 		 */
 		if (ret == -EAGAIN) {
-			spin_unlock(&hb->lock);
 			put_futex_key(&key);
 			goto retry;
 		}
@@ -2682,7 +2690,7 @@ static int futex_unlock_pi(u32 __user *u
 		 * wake_futex_pi has detected invalid state. Tell user
 		 * space.
 		 */
-		goto out_unlock;
+		goto out_putkey;
 	}
 
 	/*
@@ -2707,7 +2715,6 @@ static int futex_unlock_pi(u32 __user *u
 	return ret;
 
 pi_faulted:
-	spin_unlock(&hb->lock);
 	put_futex_key(&key);
 
 	ret = fault_in_user_writeable(uaddr);
--- a/kernel/locking/rtmutex.c
+++ b/kernel/locking/rtmutex.c
@@ -1489,19 +1489,84 @@ void __sched rt_mutex_unlock(struct rt_m
 EXPORT_SYMBOL_GPL(rt_mutex_unlock);
 
 /**
- * rt_mutex_futex_unlock - Futex variant of rt_mutex_unlock
+ * rt_mutex_futex_unlock - Futex variant of rt_mutex_slowunlock
  * @lock: the rt_mutex to be unlocked
+ * @wqh: wake queue
  *
- * Returns: true/false indicating whether priority adjustment is
- * required or not.
+ * This cannot just be rt_mutex_slowunlock() since that does the wait_lock
+ * dance, and the futex code is tricky (ha!) and uses the wait_lock
+ * to hold off new waiters, so dropping this lock invalidates prior state
+ * and we need to redo all of it.
+ *
+ * Returns:
+ *  -EAGAIN: if we need to retry the whole operation;
+ *        1: if we need to wake and deboost;
+ *        0: if we're done.
  */
-bool __sched rt_mutex_futex_unlock(struct rt_mutex *lock,
-				   struct wake_q_head *wqh)
+int __sched rt_mutex_futex_unlock(struct rt_mutex *lock,
+				  struct wake_q_head *wake_q)
 {
-	if (likely(rt_mutex_cmpxchg_release(lock, current, NULL)))
-		return false;
+	lockdep_assert_held(&lock->wait_lock);
+
+	debug_rt_mutex_unlock(lock);
+
+	/*
+	 * We must be careful here if the fast path is enabled. If we
+	 * have no waiters queued we cannot set owner to NULL here
+	 * because of:
+	 *
+	 * foo->lock->owner = NULL;
+	 *			rtmutex_lock(foo->lock);   <- fast path
+	 *			free = atomic_dec_and_test(foo->refcnt);
+	 *			rtmutex_unlock(foo->lock); <- fast path
+	 *			if (free)
+	 *				kfree(foo);
+	 * raw_spin_unlock(foo->lock->wait_lock);
+	 *
+	 * So for the fastpath enabled kernel:
+	 *
+	 * Nothing can set the waiters bit as long as we hold
+	 * lock->wait_lock. So we do the following sequence:
+	 *
+	 *	owner = rt_mutex_owner(lock);
+	 *	clear_rt_mutex_waiters(lock);
+	 *	raw_spin_unlock(&lock->wait_lock);
+	 *	if (cmpxchg(&lock->owner, owner, 0) == owner)
+	 *		return;
+	 *	goto retry;
+	 *
+	 * The fastpath disabled variant is simple as all access to
+	 * lock->owner is serialized by lock->wait_lock:
+	 *
+	 *	lock->owner = NULL;
+	 *	raw_spin_unlock(&lock->wait_lock);
+	 */
+	if (!rt_mutex_has_waiters(lock)) {
+		unsigned long flags;
+		int ret = 0;
+
+		local_save_flags(flags);
+
+		/* Drops lock->wait_lock ! */
+		if (unlock_rt_mutex_safe(lock, flags))
+			ret = -EAGAIN;
+
+		/* Relock the rtmutex and try again */
+		raw_spin_lock_irq(&lock->wait_lock);
+
+		return ret;
+	}
+
+	/*
+	 * The wakeup next waiter path does not suffer from the above
+	 * race. See the comments there.
+	 *
+	 * Queue the next waiter for wakeup once we release the wait_lock.
+	 */
+	mark_wakeup_next_waiter(wake_q, lock);
 
-	return rt_mutex_slowunlock(lock, wqh);
+	/* Do wakeups and deboost. */
+	return 1;
 }
 
 /**
--- a/kernel/locking/rtmutex_common.h
+++ b/kernel/locking/rtmutex_common.h
@@ -109,8 +109,8 @@ extern int rt_mutex_finish_proxy_lock(st
 				      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_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]

#1494918 — Re: [RFC][PATCH 4/4] futex: Rewrite FUTEX_UNLOCK_PI

On Mon, 03 Oct 2016 11:12:38 +0200
Peter Zijlstra <peterz@infradead.org> wrote:

> There's a number of 'interesting' problems with FUTEX_UNLOCK_PI, all
> caused by holding hb->lock while doing the rt_mutex_unlock()
> equivalient.
> 
> This patch doesn't attempt to fix any of the actual problems, but
> instead reworks the code to not hold hb->lock across the unlock,
> paving the way to actually fix the problems later.
> 
> The current reason we hold hb->lock over unlock is that it serializes
> against FUTEX_LOCK_PI and avoids new waiters from coming in, this then
> ensures the rt_mutex_next_owner() value is stable and can be written
> into the user-space futex value before doing the unlock. Such that the
> unlock will indeed end up at new_owner.
> 
> This patch recognises that holding rt_mutex::wait_lock results in the
> very same guarantee, no new waiters can come in while we hold that
> lock -- after all, waiters would need this lock to queue themselves.
> 
> It therefore restructures the code to keep rt_mutex::wait_lock held.
> 
> This (of course) is not entirely straight forward either, see the
> comment in rt_mutex_slowunlock(), doing the unlock itself might drop
> wait_lock, letting new waiters in. To cure this
> rt_mutex_futex_unlock() becomes a variant of rt_mutex_slowunlock()
> that return -EAGAIN instead. This ensures the FUTEX_UNLOCK_PI code
> aborts and restarts the entire operation.
> 
> Signed-off-by: Peter Zijlstra (Intel) <peterz@infradead.org>
> ---
>  kernel/futex.c                  |   63 +++++++++++++++++--------------
>  kernel/locking/rtmutex.c        |   81 ++++++++++++++++++++++++++++++++++++----
>  kernel/locking/rtmutex_common.h |    4 -
>  3 files changed, 110 insertions(+), 38 deletions(-)
> 
> --- a/kernel/futex.c
> +++ b/kernel/futex.c
> @@ -1294,24 +1294,21 @@ static void mark_wake_futex(struct wake_
>  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 = top_waiter->pi_state;
>  	u32 uninitialized_var(curval), newval;
> +	struct task_struct *new_owner;
>  	WAKE_Q(wake_q);
> -	bool deboost;
>  	int ret = 0;
>  
> -	if (!pi_state)
> -		return -EINVAL;
> +	raw_spin_lock_irq(&pi_state->pi_mutex.wait_lock);
>  
> +	WARN_ON_ONCE(!atomic_inc_not_zero(&pi_state->refcount));

Don't we have a rule where WARN_ON() and BUG_ON() should never have
"side effects"? That is, they should only check values, but their
contents should not update values.

hence have:

	ret = atomic_inc_not_zero(&pi_state->refcount);
	WARN_ON_ONCE(!ret);

>  	/*
> -	 * If current does not own the pi_state then the futex is
> -	 * inconsistent and user space fiddled with the futex value.
> +	 * Now that we hold wait_lock, no new waiters can happen on the
> +	 * rt_mutex and new owner is stable. Drop hb->lock.
>  	 */
> -	if (pi_state->owner != current)
> -		return -EINVAL;
> +	spin_unlock(&hb->lock);
>  

Also, as Sebastian has said before, I believe this breaks rt's migrate
disable code. As migrate disable and migrate_enable are a nop if
preemption is disabled, thus if you hold a raw_spin_lock across a
spin_unlock() when the migrate enable will be a nop, and the
migrate_disable() will never stop.

-- Steve

> -	raw_spin_lock_irq(&pi_state->pi_mutex.wait_lock);
>  	new_owner = rt_mutex_next_owner(&pi_state->pi_mutex);
>  
>  	/*

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

#1494919 — Re: [RFC][PATCH 4/4] futex: Rewrite FUTEX_UNLOCK_PI

On Mon, Oct 03, 2016 at 11:36:24AM -0400, Steven Rostedt wrote:

> > +	WARN_ON_ONCE(!atomic_inc_not_zero(&pi_state->refcount));
> 
> Don't we have a rule where WARN_ON() and BUG_ON() should never have
> "side effects"? That is, they should only check values, but their
> contents should not update values.

not that I'm aware, there's various places in the kernel (including
kref.h) that relies on WARN_ON*() having side effects.

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

#1494960 — Re: [RFC][PATCH 4/4] futex: Rewrite FUTEX_UNLOCK_PI

On Mon, 3 Oct 2016 17:45:14 +0200
Peter Zijlstra <peterz@infradead.org> wrote:

> On Mon, Oct 03, 2016 at 11:36:24AM -0400, Steven Rostedt wrote:
> 
> > > +	WARN_ON_ONCE(!atomic_inc_not_zero(&pi_state->refcount));  
> > 
> > Don't we have a rule where WARN_ON() and BUG_ON() should never have
> > "side effects"? That is, they should only check values, but their
> > contents should not update values.  
> 
> not that I'm aware, there's various places in the kernel (including
> kref.h) that relies on WARN_ON*() having side effects.

Looking more into it, I believe the "no side effect" is only with
BUG_ON(), as WARN_ON() can be used within if statements.

-- Steve

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

#1494924 — Re: [RFC][PATCH 4/4] futex: Rewrite FUTEX_UNLOCK_PI

On Mon, Oct 03, 2016 at 11:36:24AM -0400, Steven Rostedt wrote:
> >  	/*
> > -	 * If current does not own the pi_state then the futex is
> > -	 * inconsistent and user space fiddled with the futex value.
> > +	 * Now that we hold wait_lock, no new waiters can happen on the
> > +	 * rt_mutex and new owner is stable. Drop hb->lock.
> >  	 */
> > -	if (pi_state->owner != current)
> > -		return -EINVAL;
> > +	spin_unlock(&hb->lock);
> >  
> 
> Also, as Sebastian has said before, I believe this breaks rt's migrate
> disable code. As migrate disable and migrate_enable are a nop if
> preemption is disabled, thus if you hold a raw_spin_lock across a
> spin_unlock() when the migrate enable will be a nop, and the
> migrate_disable() will never stop.

Its too long since I looked at that trainwreck, but yuck, that would
make lock unlock order important :-(

Now I think we could do something like so.. but I'm not entirely sure on
the various lifetime rules here, its not overly documented.

--- a/kernel/futex.c
+++ b/kernel/futex.c
@@ -1300,15 +1300,14 @@ static int wake_futex_pi(u32 __user *uad
 	WAKE_Q(wake_q);
 	int ret = 0;
 
-	raw_spin_lock_irq(&pi_state->pi_mutex.wait_lock);
-
 	WARN_ON_ONCE(!atomic_inc_not_zero(&pi_state->refcount));
 	/*
-	 * Now that we hold wait_lock, no new waiters can happen on the
-	 * rt_mutex and new owner is stable. Drop hb->lock.
+	 * XXX
 	 */
 	spin_unlock(&hb->lock);
 
+	raw_spin_lock_irq(&pi_state->pi_mutex.wait_lock);
+
 	new_owner = rt_mutex_next_owner(&pi_state->pi_mutex);
 
 	/*

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

#1495743 — Re: [RFC][PATCH 4/4] futex: Rewrite FUTEX_UNLOCK_PI

On 2016-10-03 11:12:38 [+0200], Peter Zijlstra wrote:
> There's a number of 'interesting' problems with FUTEX_UNLOCK_PI, all
> caused by holding hb->lock while doing the rt_mutex_unlock()
> equivalient.

are those problems DL related?

Sebastian

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

#1495748 — Re: [RFC][PATCH 4/4] futex: Rewrite FUTEX_UNLOCK_PI

On Wed, Oct 05, 2016 at 09:41:47AM +0200, Sebastian Andrzej Siewior wrote:
> On 2016-10-03 11:12:38 [+0200], Peter Zijlstra wrote:
> > There's a number of 'interesting' problems with FUTEX_UNLOCK_PI, all
> > caused by holding hb->lock while doing the rt_mutex_unlock()
> > equivalient.
> 
> are those problems DL related?

One of them, the other is that PI thing you did that ugly nodeboost
thing for, right?

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

#1495756 — Re: [RFC][PATCH 4/4] futex: Rewrite FUTEX_UNLOCK_PI

On 2016-10-05 10:09:12 [+0200], Peter Zijlstra wrote:
> On Wed, Oct 05, 2016 at 09:41:47AM +0200, Sebastian Andrzej Siewior wrote:
> > are those problems DL related?
> 
> One of them, the other is that PI thing you did that ugly nodeboost
> thing for, right?

this no-de-boost yes. This is probably a problem since we have this
"delayed" wake-up. I've been thinking about a marked in PI state to
ignore a de-boost so the spin_unlock() won't be a problem. But if I
understand it right, then this won't solve the DL problem since you
can't have two tasks at the same priority.

Sebastian

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

#1495758 — Re: [RFC][PATCH 4/4] futex: Rewrite FUTEX_UNLOCK_PI

On Wed, Oct 05, 2016 at 10:21:02AM +0200, Sebastian Andrzej Siewior wrote:
> On 2016-10-05 10:09:12 [+0200], Peter Zijlstra wrote:
> > On Wed, Oct 05, 2016 at 09:41:47AM +0200, Sebastian Andrzej Siewior wrote:
> > > are those problems DL related?
> > 
> > One of them, the other is that PI thing you did that ugly nodeboost
> > thing for, right?
> 
> this no-de-boost yes. This is probably a problem since we have this
> "delayed" wake-up. I've been thinking about a marked in PI state to
> ignore a de-boost so the spin_unlock() won't be a problem. But if I
> understand it right, then this won't solve the DL problem since you
> can't have two tasks at the same priority.

The primary concern for DL right now is being able to have a stable
pointer to the top waiter. We do this by having  rt_mutex_setprio()
update the pointer while holding both rq->lock and tsk->pi_lock.

This means the pointer is stable when holding either lock, which is
sufficient.

But this means, we need to deboost _before_ we wake. Otherwise the task
could've continued running and called do_exit() on us.


Secondary, once we start looking at BWI (bandwidth inheritance), where a
blocked DL task donates its runtime budget along with its deadline, we
also very much need this, since a task cannot be running of its own
budget while at the same time the boosted task is also running off that
same budget.

(having the 'blocked' DL task spin-waiting, as per optimistic spinning,
makes all that rather 'interesting').

In any case, this is two problems:

  - your inversion issue
  - my pointer stability (and eventually bandwidth issue)

that are caused by this hb->lock being in the way.

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

#1496579 — Re: [RFC][PATCH 4/4] futex: Rewrite FUTEX_UNLOCK_PI

On Mon, Oct 03, 2016 at 11:12:38AM +0200, Peter Zijlstra wrote:
> There's a number of 'interesting' problems with FUTEX_UNLOCK_PI, all
> caused by holding hb->lock while doing the rt_mutex_unlock()
> equivalient.
> 
> This patch doesn't attempt to fix any of the actual problems, but
> instead reworks the code to not hold hb->lock across the unlock,
> paving the way to actually fix the problems later.
> 
> The current reason we hold hb->lock over unlock is that it serializes
> against FUTEX_LOCK_PI and avoids new waiters from coming in, this then
> ensures the rt_mutex_next_owner() value is stable and can be written
> into the user-space futex value before doing the unlock. Such that the
> unlock will indeed end up at new_owner.
> 
> This patch recognises that holding rt_mutex::wait_lock results in the
> very same guarantee, no new waiters can come in while we hold that
> lock -- after all, waiters would need this lock to queue themselves.
> 
> It therefore restructures the code to keep rt_mutex::wait_lock held.
> 
> This (of course) is not entirely straight forward either, see the
> comment in rt_mutex_slowunlock(), doing the unlock itself might drop
> wait_lock, letting new waiters in. To cure this
> rt_mutex_futex_unlock() becomes a variant of rt_mutex_slowunlock()
> that return -EAGAIN instead. This ensures the FUTEX_UNLOCK_PI code
> aborts and restarts the entire operation.

Urgh, I missed a bunch :/

So there's the !new_owner case in wake_futex_pi() which can happen if
futex_lock_pi()'s rt_mutex_timed_futex_lock() failed but we still see
that task on the futex_q list (it hasn't yet done unqueue_me).

I wondered if we could sort this case by making fixup_owner() more
interesting, which got me looking at that.

And it turns out fixup_owner() relies on futex_pi_unlock() holding
hb->lock as well.. It does rt_mutex_owner() while holding wait_lock, but
then drops wait_lock to call fixup_pi_state_owner(), assuming the owner
it read remains valid.

ARGGH, what a mess.

Lemme stare at this more..

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

#1497130 — Re: [RFC][PATCH 4/4] futex: Rewrite FUTEX_UNLOCK_PI

New version..


This one seems to pass all the (pi) futex tests and survives many hours
of my modified pi_stress (I added MADV_UNMAP to punch holes in the
page-tables to trigger (minor) faults).

---
Subject: futex: Rewrite FUTEX_UNLOCK_PI
From: Peter Zijlstra <peterz@infradead.org>
Date: Sun Oct 2 18:42:33 CEST 2016

There's a number of 'interesting' problems with FUTEX_UNLOCK_PI, all
caused by holding hb->lock while doing the rt_mutex_unlock()
equivalient.

Notably:
 - a PI inversion on hb->lock
 - DL crash because of pointer instability.

This patch doesn't attempt to fix any of the actual problems, but
instead reworks the code to not hold hb->lock across the unlock,
paving the way to actually fix the problems later.

The current reason we hold hb->lock over unlock is that it serializes
against FUTEX_LOCK_PI and avoids new waiters from coming in, this then
ensures the rt_mutex_next_owner() value is stable and can be written
into the user-space futex value before doing the unlock. Such that the
unlock will indeed end up at new_owner.

This patch recognises that holding rt_mutex::wait_lock results in the
very same guarantee, no new waiters can come in while we hold that
lock -- after all, waiters would need this lock to queue themselves.

This (of course) is not entirely straight forward either, see the
comment in rt_mutex_slowunlock(), doing the unlock itself might drop
wait_lock, letting new waiters in.

Another problem is the case where futex_lock_pi() failed to acquire
the lock (ie. released rt_mutex::wait_lock) but hasn't yet re-acquired
hb->lock and called unqueue_me_pi(). In this case we're confused about
having waiters (the futex state says yes, the rt_mutex state says no).

The current solution is to assign the futex to the waiter from the
futex state, and have futex_lock_pi() detect this and try and fix it
up. This again, all relies on hb->lock serializing things.


Solve all that by:

 - using futex specific rt_mutex calls that lack the fastpath, futexes
   have their own fastpath anyway. This makes that
   rt_mutex_futex_unlock() doesn't need to drop rt_mutex::wait_lock
   and the unlock is guaranteed if we manage to update user state.

 - make futex_unlock_pi() drop hb->lock early and only use
   rt_mutex::wait_lock to serialize against rt_mutex waiters
   update the futex value and unlock.

 - in case futex and rt_mutex disagree on waiters, side with rt_mutex
   and simply clear the user value. This works because either there
   really are no waiters left, or futex_lock_pi() triggers the
   lock-steal path and fixes up the WAITERS flag.


Signed-off-by: Peter Zijlstra (Intel) <peterz@infradead.org>
---
 kernel/futex.c                  |  178 ++++++++++++++++++++--------------------
 kernel/locking/rtmutex.c        |   55 +++++++++---
 kernel/locking/rtmutex_common.h |    9 +-
 3 files changed, 139 insertions(+), 103 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);
 
@@ -1146,7 +1146,7 @@ static int lock_pi_update_atomic(u32 __u
 	if (unlikely(cmpxchg_futex_value_locked(&curval, uaddr, uval, newval)))
 		return -EFAULT;
 
-	/*If user space value changed, let the caller retry */
+	/* If user space value changed, let the caller retry */
 	return curval != uval ? -EAGAIN : 0;
 }
 
@@ -1291,49 +1291,58 @@ static void mark_wake_futex(struct wake_
 	smp_store_release(&q->lock_ptr, NULL);
 }
 
-static int wake_futex_pi(u32 __user *uaddr, u32 uval, struct futex_q *top_waiter,
-			 struct futex_hash_bucket *hb)
+static int wake_futex_pi(u32 __user *uaddr, u32 uval, struct futex_pi_state *pi_state)
 {
-	struct task_struct *new_owner;
-	struct futex_pi_state *pi_state = top_waiter->pi_state;
 	u32 uninitialized_var(curval), newval;
+	struct task_struct *new_owner;
+	bool deboost = false;
 	WAKE_Q(wake_q);
-	bool deboost;
 	int ret = 0;
 
-	if (!pi_state)
-		return -EINVAL;
-
-	/*
-	 * If current does not own the pi_state then the futex is
-	 * inconsistent and user space fiddled with the futex value.
-	 */
-	if (pi_state->owner != current)
-		return -EINVAL;
-
 	raw_spin_lock_irq(&pi_state->pi_mutex.wait_lock);
-	new_owner = rt_mutex_next_owner(&pi_state->pi_mutex);
-
-	/*
-	 * It is possible that the next waiter (the one that brought
-	 * top_waiter owner to the kernel) timed out and is no longer
-	 * waiting on the lock.
-	 */
-	if (!new_owner)
-		new_owner = top_waiter->task;
 
-	/*
-	 * We pass it to the next owner. The WAITERS bit is always
-	 * kept enabled while there is PI state around. We cleanup the
-	 * owner died bit, because we are the owner.
-	 */
-	newval = FUTEX_WAITERS | task_pid_vnr(new_owner);
+	new_owner = rt_mutex_next_owner(&pi_state->pi_mutex);
+	if (!new_owner) {
+		/*
+		 * This is the case where futex_lock_pi() has not yet or failed
+		 * to acquire the lock but still has the futex_q enqueued. So
+		 * the futex state has a 'waiter' while the rt_mutex state does
+		 * not.
+		 *
+		 * Even though there still is pi_state for this futex, we can
+		 * clear FUTEX_WAITERS. Either:
+		 *
+		 *  - we or futex_lock_pi() will drop the last reference and
+		 *    clean up this pi_state,
+		 *
+		 *  - userspace acquires the futex through its fastpath
+		 *    and the above pi_state cleanup still happens,
+		 *
+		 *  - or futex_lock_pi() will re-set the WAITERS bit in
+		 *    fixup_owner().
+		 */
+		newval = 0;
+		/*
+		 * Since pi_state->owner must point to a valid task, and
+		 * task_pid_vnr(pi_state->owner) must match TID_MASK, use
+		 * init_task.
+		 */
+		new_owner = &init_task;
+	} else {
+		/*
+		 * We pass it to the next owner. The WAITERS bit is always kept
+		 * enabled while there is PI state around. We cleanup the owner
+		 * died bit, because we are the owner.
+		 */
+		newval = FUTEX_WAITERS | task_pid_vnr(new_owner);
+	}
 
 	if (unlikely(should_fail_futex(true)))
 		ret = -EFAULT;
 
 	if (cmpxchg_futex_value_locked(&curval, uaddr, uval, newval)) {
 		ret = -EFAULT;
+
 	} else if (curval != uval) {
 		/*
 		 * If a unconditional UNLOCK_PI operation (user space did not
@@ -1346,10 +1355,9 @@ static int wake_futex_pi(u32 __user *uad
 		else
 			ret = -EINVAL;
 	}
-	if (ret) {
-		raw_spin_unlock_irq(&pi_state->pi_mutex.wait_lock);
-		return ret;
-	}
+
+	if (ret)
+		goto out_unlock;
 
 	raw_spin_lock(&pi_state->owner->pi_lock);
 	WARN_ON(list_empty(&pi_state->list));
@@ -1362,22 +1370,20 @@ 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.
 	 */
-	spin_unlock(&hb->lock);
-	wake_up_q(&wake_q);
-	if (deboost)
+	deboost = __rt_mutex_futex_unlock(&pi_state->pi_mutex, &wake_q);
+
+out_unlock:
+	raw_spin_unlock_irq(&pi_state->pi_mutex.wait_lock);
+
+	if (deboost) {
+		wake_up_q(&wake_q);
 		rt_mutex_adjust_prio(current);
+	}
 
-	return 0;
+	return ret;
 }
 
 /*
@@ -2228,7 +2234,6 @@ static long futex_wait_restart(struct re
  */
 static int fixup_owner(u32 __user *uaddr, struct futex_q *q, int locked)
 {
-	struct task_struct *owner;
 	int ret = 0;
 
 	if (locked) {
@@ -2242,43 +2247,15 @@ static int fixup_owner(u32 __user *uaddr
 	}
 
 	/*
-	 * Catch the rare case, where the lock was released when we were on the
-	 * way back before we locked the hash bucket.
-	 */
-	if (q->pi_state->owner == current) {
-		/*
-		 * Try to get the rt_mutex now. This might fail as some other
-		 * task acquired the rt_mutex after we removed ourself from the
-		 * rt_mutex waiters list.
-		 */
-		if (rt_mutex_trylock(&q->pi_state->pi_mutex)) {
-			locked = 1;
-			goto out;
-		}
-
-		/*
-		 * pi_state is incorrect, some other task did a lock steal and
-		 * we returned due to timeout or signal without taking the
-		 * rt_mutex. Too late.
-		 */
-		raw_spin_lock_irq(&q->pi_state->pi_mutex.wait_lock);
-		owner = rt_mutex_owner(&q->pi_state->pi_mutex);
-		if (!owner)
-			owner = rt_mutex_next_owner(&q->pi_state->pi_mutex);
-		raw_spin_unlock_irq(&q->pi_state->pi_mutex.wait_lock);
-		ret = fixup_pi_state_owner(uaddr, q, owner);
-		goto out;
-	}
-
-	/*
 	 * Paranoia check. If we did not take the lock, then we should not be
 	 * the owner of the rt_mutex.
 	 */
-	if (rt_mutex_owner(&q->pi_state->pi_mutex) == current)
+	if (rt_mutex_owner(&q->pi_state->pi_mutex) == current) {
 		printk(KERN_ERR "fixup_owner: ret = %d pi-mutex: %p "
 				"pi-state %p\n", ret,
 				q->pi_state->pi_mutex.owner,
 				q->pi_state->owner);
+	}
 
 out:
 	return ret ? ret : locked;
@@ -2566,7 +2543,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 +2566,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);
@@ -2656,7 +2633,34 @@ static int futex_unlock_pi(u32 __user *u
 	 */
 	top_waiter = futex_top_waiter(hb, &key);
 	if (top_waiter) {
-		ret = wake_futex_pi(uaddr, uval, top_waiter, hb);
+		struct futex_pi_state *pi_state = top_waiter->pi_state;
+
+		ret = -EINVAL;
+		if (!pi_state)
+			goto out_unlock;
+
+		/*
+		 * If current does not own the pi_state then the futex is
+		 * inconsistent and user space fiddled with the futex value.
+		 */
+		if (pi_state->owner != current)
+			goto out_unlock;
+
+		/*
+		 * Grab a reference on the pi_state and drop hb->lock.
+		 *
+		 * 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.
+		 */
+		WARN_ON_ONCE(!atomic_inc_not_zero(&pi_state->refcount));
+		spin_unlock(&hb->lock);
+
+		ret = wake_futex_pi(uaddr, uval, pi_state);
+
+		put_pi_state(pi_state);
+
 		/*
 		 * In case of success wake_futex_pi dropped the hash
 		 * bucket lock.
@@ -2674,7 +2678,6 @@ static int futex_unlock_pi(u32 __user *u
 		 * setting the FUTEX_WAITERS bit. Try again.
 		 */
 		if (ret == -EAGAIN) {
-			spin_unlock(&hb->lock);
 			put_futex_key(&key);
 			goto retry;
 		}
@@ -2682,7 +2685,7 @@ static int futex_unlock_pi(u32 __user *u
 		 * wake_futex_pi has detected invalid state. Tell user
 		 * space.
 		 */
-		goto out_unlock;
+		goto out_putkey;
 	}
 
 	/*
@@ -2692,8 +2695,10 @@ static int futex_unlock_pi(u32 __user *u
 	 * preserve the WAITERS bit not the OWNER_DIED one. We are the
 	 * owner.
 	 */
-	if (cmpxchg_futex_value_locked(&curval, uaddr, uval, 0))
+	if (cmpxchg_futex_value_locked(&curval, uaddr, uval, 0)) {
+		spin_unlock(&hb->lock);
 		goto pi_faulted;
+	}
 
 	/*
 	 * If uval has changed, let user space handle it.
@@ -2707,7 +2712,6 @@ static int futex_unlock_pi(u32 __user *u
 	return ret;
 
 pi_faulted:
-	spin_unlock(&hb->lock);
 	put_futex_key(&key);
 
 	ret = fault_in_user_writeable(uaddr);
@@ -2937,7 +2941,7 @@ static int futex_wait_requeue_pi(u32 __u
 	 */
 	if (ret == -EFAULT) {
 		if (pi_mutex && rt_mutex_owner(pi_mutex) == current)
-			rt_mutex_unlock(pi_mutex);
+			rt_mutex_futex_unlock(pi_mutex);
 	} else if (ret == -EINTR) {
 		/*
 		 * We've already been requeued, but cannot restart by calling
--- a/kernel/locking/rtmutex.c
+++ b/kernel/locking/rtmutex.c
@@ -1422,15 +1422,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);
 }
 
 /**
@@ -1489,19 +1497,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;
+	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]

#1497765 — Re: [RFC][PATCH 4/4] futex: Rewrite FUTEX_UNLOCK_PI

On Fri, 7 Oct 2016, Peter Zijlstra wrote:
> Solve all that by:
> 
>  - using futex specific rt_mutex calls that lack the fastpath, futexes
>    have their own fastpath anyway. This makes that
>    rt_mutex_futex_unlock() doesn't need to drop rt_mutex::wait_lock
>    and the unlock is guaranteed if we manage to update user state.
> 
>  - make futex_unlock_pi() drop hb->lock early and only use
>    rt_mutex::wait_lock to serialize against rt_mutex waiters
>    update the futex value and unlock.
> 
>  - in case futex and rt_mutex disagree on waiters, side with rt_mutex
>    and simply clear the user value. This works because either there
>    really are no waiters left, or futex_lock_pi() triggers the
>    lock-steal path and fixes up the WAITERS flag.

I stared at this for a few hours and while I'm not yet done analyzing all
possible combinations I found at least one thing which is broken:

CPU 0				CPU 1

unlock_pi(f)
  ....
  unlock(hb->lock)
  *f = new_owner_tid | WAITERS;

				lock_pi(f) 
				  lock(hb->lock)
				  uval = *f;
				  topwaiter = futex_top_waiter();
				    attach_to_pi_state(uval, topwaiter->pistate);
				      pid = uval & TID_MASK;
				      if (pid != task_pid_vnr(pistate->owner))
				      	 return -EINVAL;
  ....
  pistate->owner = newowner;

So in this case we tell the caller on CPU 1 that the futex is in
inconsistent state, because pistate->owner still points to the unlocking
task while the user space value alread shows the new owner. So this sanity
check triggers and we simply fail while we should not. It's [10] in the
state matrix above attach_to_pi_state().

I suspect that there are more issues like this, especially since I did not
look at requeue_pi yet, but by now my brain is completely fried.

Thanks,

	tglx

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

#1497782 — Re: [RFC][PATCH 4/4] futex: Rewrite FUTEX_UNLOCK_PI

On Sat, Oct 08, 2016 at 05:53:49PM +0200, Thomas Gleixner wrote:
> On Fri, 7 Oct 2016, Peter Zijlstra wrote:
> > Solve all that by:
> > 
> >  - using futex specific rt_mutex calls that lack the fastpath, futexes
> >    have their own fastpath anyway. This makes that
> >    rt_mutex_futex_unlock() doesn't need to drop rt_mutex::wait_lock
> >    and the unlock is guaranteed if we manage to update user state.
> > 
> >  - make futex_unlock_pi() drop hb->lock early and only use
> >    rt_mutex::wait_lock to serialize against rt_mutex waiters
> >    update the futex value and unlock.
> > 
> >  - in case futex and rt_mutex disagree on waiters, side with rt_mutex
> >    and simply clear the user value. This works because either there
> >    really are no waiters left, or futex_lock_pi() triggers the
> >    lock-steal path and fixes up the WAITERS flag.
> 
> I stared at this for a few hours and while I'm not yet done analyzing all
> possible combinations I found at least one thing which is broken:
> 
> CPU 0				CPU 1
> 
> unlock_pi(f)
>   ....
>   unlock(hb->lock)
>   *f = new_owner_tid | WAITERS;
> 
> 				lock_pi(f) 
> 				  lock(hb->lock)
> 				  uval = *f;
> 				  topwaiter = futex_top_waiter();
> 				    attach_to_pi_state(uval, topwaiter->pistate);
> 				      pid = uval & TID_MASK;
> 				      if (pid != task_pid_vnr(pistate->owner))
> 				      	 return -EINVAL;
>   ....
>   pistate->owner = newowner;
> 
> So in this case we tell the caller on CPU 1 that the futex is in
> inconsistent state, because pistate->owner still points to the unlocking
> task while the user space value alread shows the new owner. So this sanity
> check triggers and we simply fail while we should not. It's [10] in the
> state matrix above attach_to_pi_state().

Urgh, yes. I think I can cure that, by taking
pi_state->pi_mutex.wait_lock in attach_to_pi_state(), but blergh.

> I suspect that there are more issues like this, especially since I did not
> look at requeue_pi yet, but by now my brain is completely fried.

Yes, I know about fried brains :-( This stuff has far too many moving
parts. I've been staring at this stuff far too long.


Also, we need better tools to stress this stuff.

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

#1497786 — Re: [RFC][PATCH 4/4] futex: Rewrite FUTEX_UNLOCK_PI

On Sat, 8 Oct 2016, Peter Zijlstra wrote:
> > So in this case we tell the caller on CPU 1 that the futex is in
> > inconsistent state, because pistate->owner still points to the unlocking
> > task while the user space value alread shows the new owner. So this sanity
> > check triggers and we simply fail while we should not. It's [10] in the
> > state matrix above attach_to_pi_state().
> 
> Urgh, yes. I think I can cure that, by taking
> pi_state->pi_mutex.wait_lock in attach_to_pi_state(), but blergh.
> 
> > I suspect that there are more issues like this, especially since I did not
> > look at requeue_pi yet, but by now my brain is completely fried.
> 
> Yes, I know about fried brains :-( This stuff has far too many moving
> parts. I've been staring at this stuff far too long.
> 
> Also, we need better tools to stress this stuff.

I tried to come up with something which forces all corner cases of this
years ago and failed. The state space seems to be infinite.

Thanks,

	tglx

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

#1498219 — Re: [RFC][PATCH 4/4] futex: Rewrite FUTEX_UNLOCK_PI

On Sat, 8 Oct 2016, Peter Zijlstra wrote:
> On Sat, Oct 08, 2016 at 05:53:49PM +0200, Thomas Gleixner wrote:
> > On Fri, 7 Oct 2016, Peter Zijlstra wrote:
> > > Solve all that by:
> > > 
> > >  - using futex specific rt_mutex calls that lack the fastpath, futexes
> > >    have their own fastpath anyway. This makes that
> > >    rt_mutex_futex_unlock() doesn't need to drop rt_mutex::wait_lock
> > >    and the unlock is guaranteed if we manage to update user state.
> > > 
> > >  - make futex_unlock_pi() drop hb->lock early and only use
> > >    rt_mutex::wait_lock to serialize against rt_mutex waiters
> > >    update the futex value and unlock.
> > > 
> > >  - in case futex and rt_mutex disagree on waiters, side with rt_mutex
> > >    and simply clear the user value. This works because either there
> > >    really are no waiters left, or futex_lock_pi() triggers the
> > >    lock-steal path and fixes up the WAITERS flag.
> > 
> > I stared at this for a few hours and while I'm not yet done analyzing all
> > possible combinations I found at least one thing which is broken:
> > 
> > CPU 0				CPU 1
> > 
> > unlock_pi(f)
> >   ....
> >   unlock(hb->lock)
> >   *f = new_owner_tid | WAITERS;
> > 
> > 				lock_pi(f) 
> > 				  lock(hb->lock)
> > 				  uval = *f;
> > 				  topwaiter = futex_top_waiter();
> > 				    attach_to_pi_state(uval, topwaiter->pistate);
> > 				      pid = uval & TID_MASK;
> > 				      if (pid != task_pid_vnr(pistate->owner))
> > 				      	 return -EINVAL;
> >   ....
> >   pistate->owner = newowner;
> > 
> > So in this case we tell the caller on CPU 1 that the futex is in
> > inconsistent state, because pistate->owner still points to the unlocking
> > task while the user space value alread shows the new owner. So this sanity
> > check triggers and we simply fail while we should not. It's [10] in the
> > state matrix above attach_to_pi_state().
> 
> Urgh, yes. I think I can cure that, by taking
> pi_state->pi_mutex.wait_lock in attach_to_pi_state(), but blergh.

There is another problem with all that racing against fixup_owner()
resp. fixup_pi_state_owner().

I fear, we need to rethink this whole locking/protection scheme from
scratch.

Thanks,

	tglx

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

#1498247 — Re: [RFC][PATCH 4/4] futex: Rewrite FUTEX_UNLOCK_PI

On Mon, Oct 10, 2016 at 12:17:48PM +0200, Thomas Gleixner wrote:
> There is another problem with all that racing against fixup_owner()
> resp. fixup_pi_state_owner().
> 
> I fear, we need to rethink this whole locking/protection scheme from
> scratch.


So for pi_state (ie, the attach_to_pi_state() vs put_pi_state() race) I
can see two options, either we re-take hb->lock after we've completed
the futex_unlock_pi() in order to drop it, which is cringe worthy, or we
make pi_state RCU freed and replace that WARN_ON() in
attach_to_pi_state() with an atomic_inc_not_zero() and deal with the
fail case by going back to the caller and treating it like !top_waiter.


As to the rt_mutex vs futex state coherence, I think I can do all of
that with rt_mutex::wait_lock held, the alternative is doing part with
hb->lock and part with rt_mutex::wait_lock and parts with both, but
that's already hurting my head and I didn't even try yet.


Let me think a wee bit more on this..

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

#1497806 — Re: [RFC][PATCH 4/4] futex: Rewrite FUTEX_UNLOCK_PI

On Fri, 7 Oct 2016, Peter Zijlstra wrote:
> +		/*
> +		 * Grab a reference on the pi_state and drop hb->lock.
> +		 *
> +		 * 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.
> +		 */
> +		WARN_ON_ONCE(!atomic_inc_not_zero(&pi_state->refcount));
> +		spin_unlock(&hb->lock);
> +
> +		ret = wake_futex_pi(uaddr, uval, pi_state);
> +
> +		put_pi_state(pi_state);
> +
>  		/*
>  		 * In case of success wake_futex_pi dropped the hash
>  		 * bucket lock.

This comment has become stale.

Thanks,

	tglx

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

#1497900 — Re: [RFC][PATCH 4/4] futex: Rewrite FUTEX_UNLOCK_PI

On Fri, 7 Oct 2016, Peter Zijlstra wrote:
>  	top_waiter = futex_top_waiter(hb, &key);
>  	if (top_waiter) {
> -		ret = wake_futex_pi(uaddr, uval, top_waiter, hb);
> +		struct futex_pi_state *pi_state = top_waiter->pi_state;
> +
> +		ret = -EINVAL;
> +		if (!pi_state)
> +			goto out_unlock;
> +
> +		/*
> +		 * If current does not own the pi_state then the futex is
> +		 * inconsistent and user space fiddled with the futex value.
> +		 */
> +		if (pi_state->owner != current)
> +			goto out_unlock;
> +
> +		/*
> +		 * Grab a reference on the pi_state and drop hb->lock.
> +		 *
> +		 * 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.
> +		 */
> +		WARN_ON_ONCE(!atomic_inc_not_zero(&pi_state->refcount));
> +		spin_unlock(&hb->lock);
> +
> +		ret = wake_futex_pi(uaddr, uval, pi_state);
> +
> +		put_pi_state(pi_state);

put_pi_state() requires hb->lock protection AFAICT.

CPU0	       			 CPU1

    wake_futex_pi()		 attach_to_pi_state()
    put_pi_state()
	refcount--;	
	if (!refcount)		
	    free_state();	
	    			WARN_ON(!pi_state->refcount);

we might not see the warning, but in any case the following access to
pi_state on cpu1 is borked.

Thanks,

	tglx


   	     	     	      	

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

#1498337 — Re: [RFC][PATCH 4/4] futex: Rewrite FUTEX_UNLOCK_PI

On Sun, Oct 09, 2016 at 01:17:50PM +0200, Thomas Gleixner wrote:
> On Fri, 7 Oct 2016, Peter Zijlstra wrote:
> >  	top_waiter = futex_top_waiter(hb, &key);
> >  	if (top_waiter) {
> > -		ret = wake_futex_pi(uaddr, uval, top_waiter, hb);
> > +		struct futex_pi_state *pi_state = top_waiter->pi_state;
> > +
> > +		ret = -EINVAL;
> > +		if (!pi_state)
> > +			goto out_unlock;
> > +
> > +		/*
> > +		 * If current does not own the pi_state then the futex is
> > +		 * inconsistent and user space fiddled with the futex value.
> > +		 */
> > +		if (pi_state->owner != current)
> > +			goto out_unlock;
> > +
> > +		/*
> > +		 * Grab a reference on the pi_state and drop hb->lock.
> > +		 *
> > +		 * 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.
> > +		 */
> > +		WARN_ON_ONCE(!atomic_inc_not_zero(&pi_state->refcount));
> > +		spin_unlock(&hb->lock);
> > +
> > +		ret = wake_futex_pi(uaddr, uval, pi_state);
> > +
> > +		put_pi_state(pi_state);
> 
> put_pi_state() requires hb->lock protection AFAICT.
> 
> CPU0	       			 CPU1
> 
>     wake_futex_pi()		 attach_to_pi_state()
>     put_pi_state()
> 	refcount--;	
> 	if (!refcount)		
> 	    free_state();	
> 	    			WARN_ON(!pi_state->refcount);
> 
> we might not see the warning, but in any case the following access to
> pi_state on cpu1 is borked.

Not sure this can happen, we do all attach_to_pi_state() with hb->lock
held, and the only way to get there is through futex_q->pi_state. And as
long as that link is stable, pi_state is too.

That is, the only way for wake_futex_pi() to drop the last reference is
if there are no futex_q's referencing it anymore, but that also means
attach_to_pi_state() cannot happen (!top_waiter).

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

Page 1 of 2  [1] 2  Next page →

Back to top | Article view | linux.kernel

csiph-web