FUTEX_UNLOCK_PI wobbles
Peter Zijlstra
maintainercover 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?
Peter Zijlstra
maintainerRFC PATCH 1/4 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.
--- kernel/futex.c | 30 +++++++++++++++--------------- 1 file changed, 15 insertions(+), 15 deletions(-)
kernel/futex.c +15 -15
@@ -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;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 *uu32 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.
Re: [RFC][PATCH 1/4] futex: Cleanup variable names for futex_top_waiter()
Quoted 4 lines · On Mon, 03 Oct 2016 11:12:35 +0200 Peter Zijlstra <[email protected]> wrote:
futex_top_waiter()returns the top-waiter on thepi_mutex. Assinging this to a variable 'match' totally obscures the code.Signed-off-by Peter Zijlstra (Intel) <[email protected]>
Nice!
-- Steve
Re: [RFC][PATCH 1/4] futex: Cleanup variable names for futex_top_waiter()
In reply to Peter ZijlstraQuoted 4 lines · Peter Zijlstra
futex_top_waiter()returns the top-waiter on thepi_mutex. Assinging this to a variable 'match' totally obscures the code.Signed-off-by Peter Zijlstra (Intel) <[email protected]>
Peter Zijlstra
maintainerRFC PATCH 2/4 futex: Use smp_store_release() in mark_wake_futex()
In reply to Peter ZijlstraSince the futex_q can dissapear the instruction after assigning NULL, this really should be a RELEASE barrier. That stops loads from hitting dead memory too.
--- kernel/futex.c | 3 +-- 1 file changed, 1 insertion(+), 2 deletions(-)
kernel/futex.c +1 -2
@@ -1288,8 +1288,7 @@ static void mark_wake_futex(struct wake_* memory barrier is required here to prevent the following * store to lock_ptr from getting ahead of the plist_del. */ -smp_wmb (); - q->lock_ptr =NULL ; +smp_store_release (&q->lock_ptr,NULL ); } static int wake_futex_pi(u32 __user *uaddr, u32 uval, struct futex_q *top_waiter,
Re: [RFC][PATCH 2/4] futex: Use smp_store_release() in mark_wake_futex()
Quoted 13 lines · On Mon, 03 Oct 2016 11:12:36 +0200 Peter Zijlstra <[email protected]> wrote:
Since the
futex_qcan dissapear the instruction after assigning NULL, this really should be a RELEASE barrier. That stops loads from hitting dead memory too.Signed-off-by Peter Zijlstra (Intel) <[email protected]>--- kernel/futex.c | 3 +-- 1 file changed, 1 insertion(+), 2 deletions(-)
kernel/futex.c static void mark_wake_futex(struct wake_ · line 1294
Quoted 9 lines
kernel/futex.c +1
-2@@ -1288,8 +1288,7 @@ static void mark_wake_futex(struct wake_* memory barrier is required here to prevent the following * store to lock_ptr from getting ahead of the plist_del. */ -smp_wmb (); - q->lock_ptr =NULL ; +smp_store_release (&q->lock_ptr,NULL ); } static int wake_futex_pi(u32 __user *uaddr, u32 uval, struct futex_q *top_waiter,
-- Steve
Re: [RFC][PATCH 2/4] futex: Use smp_store_release() in mark_wake_futex()
In reply to Peter ZijlstraQuoted 12 lines · Peter Zijlstra
Since the
futex_qcan dissapear the instruction after assigning NULL, this really should be a RELEASE barrier. That stops loads from hitting dead memory too.Signed-off-by Peter Zijlstra (Intel) <[email protected]>---
kernel/futex.c| 3 +--1 file changed, 1 insertion(+), 2 deletions(-)
kernel/futex.c static void mark_wake_futex(struct wake_ · line 1292
Quoted 7 lines
kernel/futex.c +1
-2@@ -1288,8 +1288,7 @@ static void mark_wake_futex(struct wake_* memory barrier is required here to prevent the following * store to lock_ptr from getting ahead of the plist_del. */ -smp_wmb (); - q->lock_ptr =NULL ; +smp_store_release (&q->lock_ptr,NULL ); }
Hmm, what if we relied on the implicit barrier in the wake_q_add() above and got rid of the smp_wmb altogether? We'd obviously have to move up __unqueue_futex(), but all we care about is the publishing store to lock_ptr being the last operation, or at least the plist_del, such that the wakeup order is respected; ie:
__unqueue_futex(q); wake_q_add(wake_q, p); q->lock_ptr = NULL;
Thanks,
Davidlohr
Peter Zijlstra
maintainerRe: [RFC][PATCH 2/4] futex: Use smp_store_release() in mark_wake_futex()
Quoted 28 lines · Davidlohr Bueso
Quoted 12 lines · Peter Zijlstra
Since the
futex_qcan dissapear the instruction after assigning NULL, this really should be a RELEASE barrier. That stops loads from hitting dead memory too.Signed-off-by Peter Zijlstra (Intel) <[email protected]>---
kernel/futex.c| 3 +--1 file changed, 1 insertion(+), 2 deletions(-)kernel/futex.c static void mark_wake_futex(struct wake_ · line 1292
Quoted 7 lines
kernel/futex.c +1
-2@@ -1288,8 +1288,7 @@ static void mark_wake_futex(struct wake_* memory barrier is required here to prevent the following * store to lock_ptr from getting ahead of the plist_del. */ -smp_wmb (); - q->lock_ptr =NULL ; +smp_store_release (&q->lock_ptr,NULL ); }Hmm, what if we relied on the implicit barrier in the
wake_q_add()above and got rid of thesmp_wmbaltogether? We'd obviously have to move up__unqueue_futex(), but all we care about is the publishing store tolock_ptrbeing the last operation, or at least theplist_del, such that the wakeup order is respected; ie:
Quoted 3 lines
__unqueue_futex(q); wake_q_add(wake_q, p); q->lock_ptr = NULL;
Less obvious but would work I suppose, I didn't look too hard at the ordering requirements on __unqueue_futex(), but an early morning glance (without tea) doesn't show any obvious problems with that.
Peter Zijlstra
maintainerRFC PATCH 3/4 futex: Remove rt_mutex_deadlock_account_*()
In reply to Peter ZijlstraThese are unused and clutter up the code.
--- kernel/locking/rtmutex-debug.c | 9 ------- kernel/locking/rtmutex-debug.h | 3 -- kernel/locking/rtmutex.c | 47 +++++++++++++++-------------------------- kernel/locking/rtmutex.h | 2 - 4 files changed, 18 insertions(+), 43 deletions(-)
kernel/locking/rtmutex-debug.c +0 -9
@@ -173,12 +173,3 @@ void debug_rt_mutex_init(struct rt_mutex lock->name = name; } -void -rt_mutex_deadlock_account_lock (struct rt_mutex *lock,struct task_struct *task) -{ -} - -void rt_mutex_deadlock_account_unlock (struct task_struct *task) -{ -} -
kernel/locking/rtmutex-debug.h +0 -3
@@ -9,9 +9,6 @@* This file contains macros used solely by rtmutex.c. Debug version. */ -extern void -rt_mutex_deadlock_account_lock (struct rt_mutex *lock,struct task_struct *task); -extern void rt_mutex_deadlock_account_unlock (struct task_struct *task);extern void debug_rt_mutex_init_waiter (struct rt_mutex_waiter *waiter);extern void debug_rt_mutex_free_waiter (struct rt_mutex_waiter *waiter);extern void debug_rt_mutex_init (struct rt_mutex *lock,const char *name);
kernel/locking/rtmutex.c +18 -29
109 lines not on this page · raw message
kernel/locking/rtmutex.h +0 -2
@@ -11,8 +11,6 @@*/ #define rt_mutex_deadlock_check (l) (0) -#define rt_mutex_deadlock_account_lock (m, t) do { } while (0) -#define rt_mutex_deadlock_account_unlock (l) do { } while (0)#define debug_rt_mutex_init_waiter (w) do { } while (0)#define debug_rt_mutex_free_waiter (w) do { } while (0)#define debug_rt_mutex_lock (l) do { } while (0)
Peter Zijlstra
maintainerRe: [RFC][PATCH 3/4] futex: Remove rt_mutex_deadlock_account_*()
^Subject should've had rtmutex: on.. -ENOTENOUGHTEA
Re: [RFC][PATCH 3/4] futex: Remove rt_mutex_deadlock_account_*()
In reply to Peter ZijlstraQuoted 3 lines · On Mon, 03 Oct 2016 11:12:37 +0200 Peter Zijlstra <[email protected]> wrote:
These are unused and clutter up the code.
Signed-off-by Peter Zijlstra (Intel) <[email protected]>
-- Steve
Re: [RFC][PATCH 3/4] futex: Remove rt_mutex_deadlock_account_*()
In reply to Peter ZijlstraQuoted 3 lines · Peter Zijlstra
These are unused and clutter up the code.
Signed-off-by Peter Zijlstra (Intel) <[email protected]>
Re: [RFC][PATCH 3/4] futex: Remove rt_mutex_deadlock_account_*()
In reply to Peter ZijlstraQuoted 1 line · Peter Zijlstra
These are unused and clutter up the code.
it seems that it has been like that since day one (Ingo's patches from 2006 [0] are like that). I assume we never had real code behind this functions, right? Not even in -RT?
[0] http://people.redhat.com/mingo/PI-futex-patches/patches/
Sebastian
Peter Zijlstra
maintainerRFC PATCH 4/4 futex: Rewrite FUTEX_UNLOCK_PI
In reply to Peter ZijlstraThere'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.
--- kernel/futex.c | 63 +++++++++++++++++-------------- kernel/locking/rtmutex.c | 81 ++++++++++++++++++++++++++++++++++++---- kernel/locking/rtmutex_common.h | 4 - 3 files changed, 110 insertions(+), 38 deletions(-)
kernel/futex.c +35 -28
@@ -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 *uadif (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 *uadelse 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 *ureturn ret; pi_faulted: -spin_unlock (&hb->lock);put_futex_key (&key); ret =fault_in_user_writeable (uaddr);
kernel/locking/rtmutex.c +73 -8
92 lines not on this page · raw message
kernel/locking/rtmutex_common.h +2 -2
@@ -109,8 +109,8 @@ extern int rt_mutex_finish_proxy_lock(ststruct 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
Re: [RFC][PATCH 4/4] futex: Rewrite FUTEX_UNLOCK_PI
Quoted 43 lines · On Mon, 03 Oct 2016 11:12:38 +0200 Peter Zijlstra <[email protected]> wrote:
There's a number of 'interesting' problems with
FUTEX_UNLOCK_PI, all caused by holdinghb->lockwhile doing thert_mutex_unlock()equivalient.This patch doesn't attempt to fix any of the actual problems, but instead reworks the code to not hold
hb->lockacross the unlock, paving the way to actually fix the problems later.The current reason we hold
hb->lockover unlock is that it serializes againstFUTEX_LOCK_PIand avoids new waiters from coming in, this then ensures thert_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 atnew_owner.This patch recognises that holding
rt_mutex::wait_lockresults 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_lockheld.This (of course) is not entirely straight forward either, see the comment in
rt_mutex_slowunlock(), doing the unlock itself might dropwait_lock, letting new waiters in. To cure thisrt_mutex_futex_unlock()becomes a variant ofrt_mutex_slowunlock()that return-EAGAINinstead. This ensures theFUTEX_UNLOCK_PIcode aborts and restarts the entire operation.Signed-off-by Peter Zijlstra (Intel) <[email protected]>--- kernel/futex.c | 63 +++++++++++++++++-------------- kernel/locking/rtmutex.c | 81 ++++++++++++++++++++++++++++++++++++---- kernel/locking/rtmutex_common.h | 4 - 3 files changed, 110 insertions(+), 38 deletions(-)kernel/futex.c +0
-1@@ -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;
kernel/futex.c static void mark_wake_futex(struct wake_ · line 1305
Quoted 10 lines
kernel/futex.c +3
-3+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);
kernel/futex.c static void mark_wake_futex(struct wake_ · line 1311
Quoted 10 lines
kernel/futex.c +3
-4/* -* 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
Quoted 4 lines
kernel/futex.c +0
-1-raw_spin_lock_irq (&pi_state->pi_mutex.wait_lock); new_owner =rt_mutex_next_owner (&pi_state->pi_mutex);/*
Peter Zijlstra
maintainerRe: [RFC][PATCH 4/4] futex: Rewrite FUTEX_UNLOCK_PI
Quoted 8 lines · Steven Rostedt
Quoted 8 lines
(quoted diff) +2
-4/* - * 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;
Quoted 8 lines
Review
Quoted 2 lines
(quoted diff) +1
-0+ spin_unlock(&hb->lock);Also, as Sebastian has said before, I believe this breaks rt's migrate disable code. As migrate disable and
migrate_enableare a nop if preemption is disabled, thus if you hold araw_spin_lockacross aspin_unlock()when the migrate enable will be a nop, and themigrate_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.
kernel/futex.c +3 -4
@@ -1300,15 +1300,14 @@ static int wake_futex_pi(u32 __user *uadWAKE_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);/*
Peter Zijlstra
maintainerRe: [RFC][PATCH 4/4] futex: Rewrite FUTEX_UNLOCK_PI
In reply to Steven RostedtQuoted 5 lines · Steven Rostedt
kernel/futex.c static void mark_wake_futex(struct wake_ · line 1305
Quoted 1 line
kernel/futex.c +1
-0+WARN_ON_ONCE (!atomic_inc_not_zero (&pi_state->refcount));Don't we have a rule where
WARN_ON()andBUG_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.
Re: [RFC][PATCH 4/4] futex: Rewrite FUTEX_UNLOCK_PI
Quoted 10 lines · On Mon, 3 Oct 2016 17:45:14 +0200 Peter Zijlstra <[email protected]> wrote:
Quoted 5 lines · Steven Rostedt
kernel/futex.c static void mark_wake_futex(struct wake_ · line 1305
Quoted 1 line
kernel/futex.c +1
-0+WARN_ON_ONCE (!atomic_inc_not_zero (&pi_state->refcount));Don't we have a rule where
WARN_ON()andBUG_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
Re: [RFC][PATCH 4/4] futex: Rewrite FUTEX_UNLOCK_PI
In reply to Peter ZijlstraQuoted 3 lines · Peter Zijlstra
There's a number of 'interesting' problems with
FUTEX_UNLOCK_PI, all caused by holdinghb->lockwhile doing thert_mutex_unlock()equivalient.
are those problems DL related?
Sebastian
Peter Zijlstra
maintainerRe: [RFC][PATCH 4/4] futex: Rewrite FUTEX_UNLOCK_PI
Quoted 6 lines · Sebastian Andrzej Siewior
Quoted 3 lines · Peter Zijlstra
There's a number of 'interesting' problems with
FUTEX_UNLOCK_PI, all caused by holdinghb->lockwhile doing thert_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?
Re: [RFC][PATCH 4/4] futex: Rewrite FUTEX_UNLOCK_PI
Quoted 5 lines · Peter Zijlstra
Quoted 1 line · Sebastian Andrzej Siewior
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
Peter Zijlstra
maintainerRe: [RFC][PATCH 4/4] futex: Rewrite FUTEX_UNLOCK_PI
Quoted 4 lines · Sebastian Andrzej Siewior
Quoted 3 lines · Peter Zijlstra
Quoted 1 line · Sebastian Andrzej Siewior
are those problems DL related?
Quoted 8 lines
Quoted 2 lines
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.
Peter Zijlstra
maintainerRe: [RFC][PATCH 4/4] futex: Rewrite FUTEX_UNLOCK_PI
In reply to Peter ZijlstraQuoted 18 lines · Peter Zijlstra
There's a number of 'interesting' problems with
FUTEX_UNLOCK_PI, all caused by holdinghb->lockwhile doing thert_mutex_unlock()equivalient.This patch doesn't attempt to fix any of the actual problems, but instead reworks the code to not hold
hb->lockacross the unlock, paving the way to actually fix the problems later.The current reason we hold
hb->lockover unlock is that it serializes againstFUTEX_LOCK_PIand avoids new waiters from coming in, this then ensures thert_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 atnew_owner.This patch recognises that holding
rt_mutex::wait_lockresults 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.
Quoted 8 lines
It therefore restructures the code to keep
rt_mutex::wait_lockheld.This (of course) is not entirely straight forward either, see the comment in
rt_mutex_slowunlock(), doing the unlock itself might dropwait_lock, letting new waiters in. To cure thisrt_mutex_futex_unlock()becomes a variant ofrt_mutex_slowunlock()that return-EAGAINinstead. This ensures theFUTEX_UNLOCK_PIcode 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..
Peter Zijlstra
maintainerRe: [RFC][PATCH 4/4] futex: Rewrite FUTEX_UNLOCK_PI
In reply to Peter ZijlstraNew 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 <[email protected]>
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.
--- kernel/futex.c | 178 ++++++++++++++++++++-------------------- kernel/locking/rtmutex.c | 55 +++++++++--- kernel/locking/rtmutex_common.h | 9 +- 3 files changed, 139 insertions(+), 103 deletions(-)
kernel/futex.c +91 -87
@@ -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 __uif (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 *uadelse 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 *uadif (!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 *ureturn 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
kernel/locking/rtmutex.c +41 -14
75 lines not on this page · raw message
kernel/locking/rtmutex_common.h +7 -2
@@ -108,9 +108,14 @@ extern int rt_mutex_start_proxy_lock(strextern 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
Re: [RFC][PATCH 4/4] futex: Rewrite FUTEX_UNLOCK_PI
Quoted 7 lines · Peter Zijlstra
Solve all that by:
- using futex specific
rt_mutexcalls that lack the fastpath, futexes have their own fastpath anyway. This makes thatrt_mutex_futex_unlock()doesn't need to droprt_mutex::wait_lockand the unlock is guaranteed if we manage to update user state.
Quoted 8 lines
- make
futex_unlock_pi()drophb->lockearly and only usert_mutex::wait_lockto serialize againstrt_mutexwaiters update the futex value and unlock.- in case futex and
rt_mutexdisagree on waiters, side withrt_mutexand simply clear the user value. This works because either there really are no waiters left, orfutex_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
Peter Zijlstra
maintainerRe: [RFC][PATCH 4/4] futex: Rewrite FUTEX_UNLOCK_PI
Quoted 35 lines · Thomas Gleixner
Quoted 7 lines · Peter Zijlstra
Solve all that by:
- using futex specific
rt_mutexcalls that lack the fastpath, futexes have their own fastpath anyway. This makes thatrt_mutex_futex_unlock()doesn't need to droprt_mutex::wait_lockand the unlock is guaranteed if we manage to update user state.Quoted 8 lines
- make
futex_unlock_pi()drophb->lockearly and only usert_mutex::wait_lockto serialize againstrt_mutexwaiters update the futex value and unlock.- in case futex and
rt_mutexdisagree on waiters, side withrt_mutexand simply clear the user value. This works because either there really are no waiters left, orfutex_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;
Quoted 8 lines
....
pistate->owner= newowner;So in this case we tell the caller on CPU 1 that the futex is in inconsistent state, because
pistate->ownerstill 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 aboveattach_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.
Quoted 2 lines
I suspect that there are more issues like this, especially since I did not look at
requeue_piyet, 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.
Re: [RFC][PATCH 4/4] futex: Rewrite FUTEX_UNLOCK_PI
Quoted 9 lines · Peter Zijlstra
Quoted 5 lines
So in this case we tell the caller on CPU 1 that the futex is in inconsistent state, because
pistate->ownerstill 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 aboveattach_to_pi_state().Urgh, yes. I think I can cure that, by taking
pi_state->pi_mutex.wait_lockinattach_to_pi_state(), but blergh.
Quoted 7 lines
Quoted 2 lines
I suspect that there are more issues like this, especially since I did not look at
requeue_piyet, 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
Re: [RFC][PATCH 4/4] futex: Rewrite FUTEX_UNLOCK_PI
In reply to Peter ZijlstraQuoted 39 lines · Peter Zijlstra
Quoted 38 lines · Thomas Gleixner
Quoted 7 lines · Peter Zijlstra
Solve all that by:
- using futex specific
rt_mutexcalls that lack the fastpath, futexes have their own fastpath anyway. This makes thatrt_mutex_futex_unlock()doesn't need to droprt_mutex::wait_lockand the unlock is guaranteed if we manage to update user state.Quoted 8 lines
- make
futex_unlock_pi()drophb->lockearly and only usert_mutex::wait_lockto serialize againstrt_mutexwaiters update the futex value and unlock.- in case futex and
rt_mutexdisagree on waiters, side withrt_mutexand simply clear the user value. This works because either there really are no waiters left, orfutex_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;
Quoted 8 lines
Quoted 5 lines
So in this case we tell the caller on CPU 1 that the futex is in inconsistent state, because
pistate->ownerstill 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 aboveattach_to_pi_state().Urgh, yes. I think I can cure that, by taking
pi_state->pi_mutex.wait_lockinattach_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
Peter Zijlstra
maintainerRe: [RFC][PATCH 4/4] futex: Rewrite FUTEX_UNLOCK_PI
Quoted 5 lines · Thomas Gleixner
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..
Peter Zijlstra
maintainerRe: [RFC][PATCH 4/4] futex: Rewrite FUTEX_UNLOCK_PI
In reply to Thomas GleixnerQuoted 2 lines · Thomas Gleixner
I fear, we need to rethink this whole locking/protection scheme from scratch.
Here goes... as discussed at ELCE this serializes the {uval, pi_state} state using pi_mutex->wait_lock.
I did my best to reason about requeue_pi, but I did suffer some stack overflows. That said, I audited all places pi_state is used/modified and applied consistent locking and/or comments.
The patch could possibly be broken up in 3 parts, namely:
- introduce the futex specific rt_mutex wrappers that avoid the regular rt_mutex fast path (and isolate futex from the normal rt_mutex interface).
- add the pi_mutex->wait_lock locking, which at that point will be entirely redundant.
- rework the unlock_pi path to drop hb->lock.
Let me know if you would prefer to see that. For review I think having all that in a single patch is easier to reason about.
The only thing I didn't do is update the Changelog. I would like to leave that until later, when I've managed to convince you this approach is indeed viable.
Please have a look.
---
Subject: futex: Rewrite FUTEX_UNLOCK_PI
From: Peter Zijlstra <[email protected]>
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.
XXX update changelog..
--- futex.c | 340 ++++++++++++++++++++++++++++++----------------- locking/rtmutex.c | 55 +++++-- locking/rtmutex_common.h | 9 - 3 files changed, 270 insertions(+), 134 deletions(-)
kernel/futex.c +222 -118
@@ -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);
@@ -963,7 +963,9 @@ void exit_pi_state_list(struct task_stru* * [7] pi_state->owner can only be NULL when the OWNER_DIED bit is set. * -* [8] Owner and user space value match +* [8] Owner and user space value match; there is a special case in +* wake_futex_pi() where we use pi_state->owner = &init_task to +* make this true for TID 0 and avoid rules 9 and 10. * * [9] There is no transient state which sets the user space TID to 0 * except exit_robust_list(), but this is indicated by the
@@ -971,6 +973,39 @@ void exit_pi_state_list(struct task_stru* * [10] There is no transient state which leaves owner and user space * TID out of sync. +* +* +* Serialization and lifetime rules: +* +* hb->lock: +* +* hb -> futex_q, relation +* futex_q -> pi_state, relation +* +* (cannot be raw because hb can contain arbitrary amount +* of futex_q's) +* +* pi_mutex->wait_lock: +* +* {uval, pi_state} +* +* (and pi_mutex 'obviously') +* +* p->pi_lock: +* +* p->pi_state_list -> pi_state->list, relation +* +* pi_state->refcount: +* +* pi_state lifetime +* +* +* Lock order: +* +* hb->lock +* pi_mutex->wait_lock +* p->pi_lock +* */ /*
@@ -978,10 +1013,12 @@ void exit_pi_state_list(struct task_stru* the pi_state against the user space value. If correct, attach to * it. */ -static int attach_to_pi_state (u32 uval,struct futex_pi_state *pi_state, +static int attach_to_pi_state (u32 __user *uaddr,u32 uval, +struct futex_pi_state *pi_state,struct futex_pi_state **ps) {pid_t pid = uval &FUTEX_TID_MASK ; +int ret, uval2;/* * Userspace might have messed up non-PI and PI futexes [3]
@@ -989,9 +1026,37 @@ static int attach_to_pi_state(u32 uval,if (unlikely (!pi_state))return -EINVAL ; +/* +* We get here with hb->lock held, and having found a +* futex_top_waiter(). This means that futex_lock_pi() of said futex_q +* has dropped the hb->lock in between queue_me() and unqueue_me_pi(), +* which in turn means that futex_lock_pi() still has a reference on +* our pi_state. +* +* IOW, we cannot race against the unlocked put_pi_state() in +* futex_unlock_pi(). +*/ WARN_ON (!atomic_read (&pi_state->refcount));/* +* Now that we have a pi_state, we can acquire wait_lock +* and do the state validation. +*/ +raw_spin_lock_irq (&pi_state->pi_mutex.wait_lock); + +/* +* Since {uval, pi_state} is serialized by wait_lock, and our current +* uval was read without holding it, it can have changed. Verify it +* still is what we expect it to be, otherwise retry the entire +* operation. +*/ +if (get_futex_value_locked (&uval2, uaddr)) + goto out_efault; + +if (uval != uval2) + goto out_eagain; + +/* * Handle the owner died case: */ if (uval &FUTEX_OWNER_DIED ) {
@@ -1006,11 +1071,11 @@ static int attach_to_pi_state(u32 uval,* is not 0. Inconsistent state. [5] */ if (pid) -return -EINVAL ; + goto out_einval;/* * Take a ref on the state and return success. [4] */ - goto out_state; + goto out_attach; }/*
@@ -1022,14 +1087,14 @@ static int attach_to_pi_state(u32 uval,* Take a ref on the state and return success. [6] */ if (!pid) - goto out_state; + goto out_attach; }else {/* * If the owner died bit is not set, then the pi_state * must have an owner. [7] */ if (!pi_state->owner) -return -EINVAL ; + goto out_einval; }/*
@@ -1038,11 +1103,29 @@ static int attach_to_pi_state(u32 uval,* user space TID. [9/10] */ if (pid !=task_pid_vnr (pi_state->owner)) -return -EINVAL ; -out_state: + goto out_einval; + +out_attach:atomic_inc (&pi_state->refcount); +raw_spin_unlock_irq (&pi_state->pi_mutex.wait_lock); *ps = pi_state;return 0 ; + +out_einval: + ret = -EINVAL ; + goto out_error; + +out_eagain: + ret = -EAGAIN ; + goto out_error; + +out_efault: + ret = -EFAULT ; + goto out_error; + +out_error: +raw_spin_unlock_irq (&pi_state->pi_mutex.wait_lock); +return ret; }/*
@@ -1093,6 +1176,9 @@ static int attach_to_pi_owner(u32 uval,/* * No existing pi state. First waiter. [2] +* +* This creates pi_state, we have hb->lock held, this means nothing can +* observe this state, wait_lock is irrelevant. */ pi_state =alloc_pi_state ();
@@ -1117,7 +1203,8 @@ static int attach_to_pi_owner(u32 uval,return 0 ; } -static int lookup_pi_state (u32 uval,struct futex_hash_bucket *hb, +static int lookup_pi_state (u32 __user *uaddr,u32 uval, +struct futex_hash_bucket *hb,union futex_key *key,struct futex_pi_state **ps) {struct futex_q *top_waiter =futex_top_waiter (hb, key);
@@ -1127,7 +1214,7 @@ static int lookup_pi_state(u32 uval, str* attach to the pi_state when the validation succeeds. */ if (top_waiter) -return attach_to_pi_state (uval, top_waiter->pi_state, ps); +return attach_to_pi_state (uaddr, uval, top_waiter->pi_state, ps);/* * We are the first waiter - try to look up the owner based on
@@ -1146,7 +1233,7 @@ static int lock_pi_update_atomic(u32 __uif (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 ; }
@@ -1202,7 +1289,7 @@ static int futex_lock_pi_atomic(u32 __us*/ top_waiter =futex_top_waiter (hb, key);if (top_waiter) -return attach_to_pi_state (uval, top_waiter->pi_state, ps); +return attach_to_pi_state (uaddr, uval, top_waiter->pi_state, ps);/* * No waiter and user TID is 0. We are here because the
@@ -1291,49 +1378,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 +1442,9 @@ static int wake_futex_pi(u32 __user *uadelse 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 +1457,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; }/*
@@ -1823,7 +1916,7 @@ static int futex_requeue(u32 __user *uad* If that call succeeds then we have pi_state and an * initial refcount on it. */ - ret =lookup_pi_state (ret, hb2, &key2, &pi_state); + ret =lookup_pi_state (uaddr2, ret, hb2, &key2, &pi_state); }switch (ret) {
@@ -2122,10 +2215,13 @@ static int fixup_pi_state_owner(u32 __us {u32 newtid =task_pid_vnr (newowner) |FUTEX_WAITERS ;struct futex_pi_state *pi_state = q->pi_state; -struct task_struct *oldowner = pi_state->owner;u32 uval,uninitialized_var (curval ), newval; +struct task_struct *oldowner;int ret; +raw_spin_lock_irq (&pi_state->pi_mutex.wait_lock); + + oldowner = pi_state->owner;/* Owner died? */ if (!pi_state->owner) newtid |=FUTEX_OWNER_DIED ;
@@ -2141,11 +2237,10 @@ static int fixup_pi_state_owner(u32 __us* because we can fault here. Imagine swapped out pages or a fork * that marked all the anonymous memory readonly for cow. * -* Modifying pi_state _before_ the user space value would -* leave the pi_state in an inconsistent state when we fault -* here, because we need to drop the hash bucket lock to -* handle the fault. This might be observed in the PID check -* in lookup_pi_state. +* Modifying pi_state _before_ the user space value would leave the +* pi_state in an inconsistent state when we fault here, because we +* need to drop the locks to handle the fault. This might be observed +* in the PID check in lookup_pi_state. */ retry:if (get_futex_value_locked (&uval, uaddr))
@@ -2166,36 +2261,43 @@ static int fixup_pi_state_owner(u32 __us* itself. */ if (pi_state->owner !=NULL ) { -raw_spin_lock_irq (&pi_state->owner->pi_lock); +raw_spin_lock (&pi_state->owner->pi_lock);WARN_ON (list_empty (&pi_state->list));list_del_init (&pi_state->list); -raw_spin_unlock_irq (&pi_state->owner->pi_lock); +raw_spin_unlock (&pi_state->owner->pi_lock); } pi_state->owner = newowner; -raw_spin_lock_irq (&newowner->pi_lock); +raw_spin_lock (&newowner->pi_lock);WARN_ON (!list_empty (&pi_state->list));list_add (&pi_state->list, &newowner->pi_state_list); -raw_spin_unlock_irq (&newowner->pi_lock); +raw_spin_unlock (&newowner->pi_lock); +raw_spin_unlock_irq (&pi_state->pi_mutex.wait_lock); +return 0 ;/* -* To handle the page fault we need to drop the hash bucket -* lock here. That gives the other task (either the highest priority -* waiter itself or the task which stole the rtmutex) the -* chance to try the fixup of the pi_state. So once we are -* back from handling the fault we need to check the pi_state -* after reacquiring the hash bucket lock and before trying to -* do another fixup. When the fixup has been done already we -* simply return. +* To handle the page fault we need to drop the locks here. That gives +* the other task (either the highest priority waiter itself or the +* task which stole the rtmutex) the chance to try the fixup of the +* pi_state. So once we are back from handling the fault we need to +* check the pi_state after reacquiring the locks and before trying to +* do another fixup. When the fixup has been done already we simply +* return. +* +* Note: we hold both hb->lock and pi_mutex->wait_lock. We can safely +* drop hb->lock since the caller owns the hb -> futex_q relation. +* Dropping the pi_mutex->wait_lock requires the state revalidate. */ handle_fault: +raw_spin_unlock_irq (&pi_state->pi_mutex.wait_lock);spin_unlock (q->lock_ptr); ret =fault_in_user_writeable (uaddr);spin_lock (q->lock_ptr); +raw_spin_lock_irq (&pi_state->pi_mutex.wait_lock);/* * Check if someone else fixed it for us:
@@ -2228,45 +2330,20 @@ 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) {/* * Got the lock. We might not be the anticipated owner if we * did a lock-steal - fix up the PI-state in that case: +* +* We can safely read pi_state->owner without holding wait_lock +* because we now own the rt_mutex, only the owner will attempt +* to change it. */ if (q->pi_state->owner != current) ret =fixup_pi_state_owner (uaddr, q, current); - goto out; - } -/* -* 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; }
@@ -2274,11 +2351,12 @@ static int fixup_owner(u32 __user *uaddr* 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 +2644,7 @@ static int futex_lock_pi(u32 __user *uadif (!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 +2667,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,10 +2734,36 @@ 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; +/* -* In case of success wake_futex_pi dropped the hash -* bucket lock. +* 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); + +/* +* Success, we're done! No tricky corner cases. */ if (!ret) goto out_putkey;
@@ -2674,7 +2778,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 +2785,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 +2795,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 +2812,6 @@ static int futex_unlock_pi(u32 __user *ureturn ret; pi_faulted: -spin_unlock (&hb->lock);put_futex_key (&key); ret =fault_in_user_writeable (uaddr);
@@ -2937,7 +3041,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
kernel/locking/rtmutex.c +41 -14
75 lines not on this page · raw message
kernel/locking/rtmutex_common.h +7 -2
@@ -108,9 +108,14 @@ extern int rt_mutex_start_proxy_lock(strextern 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
Re: [RFC][PATCH 4/4] futex: Rewrite FUTEX_UNLOCK_PI
Quoted 17 lines · Peter Zijlstra
Quoted 2 lines · Thomas Gleixner
I fear, we need to rethink this whole locking/protection scheme from scratch.
Here goes... as discussed at ELCE this serializes the {uval,
pi_state} state usingpi_mutex->wait_lock.I did my best to reason about
requeue_pi, but I did suffer some stack overflows. That said, I audited all placespi_stateis used/modified and applied consistent locking and/or comments.The patch could possibly be broken up in 3 parts, namely:
- introduce the futex specific
rt_mutexwrappers that avoid the regularrt_mutexfast path (and isolate futex from the normalrt_mutexinterface).
Quoted 7 lines
- add the
pi_mutex->wait_locklocking, which at that point will be entirely redundant.- rework the
unlock_pipath to drophb->lock.Let me know if you would prefer to see that. For review I think having all that in a single patch is easier to reason about.
For merging and final review, yes please.
Quoted 12 lines
kernel/futex.c +1
-1@@ -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);
kernel/futex.c void exit_pi_state_list(struct task_stru · line 968
Quoted 7 lines
kernel/futex.c +3
-1@@ -963,7 +963,9 @@ void exit_pi_state_list(struct task_stru* * [7] pi_state->owner can only be NULL when the OWNER_DIED bit is set. * -* [8] Owner and user space value match +* [8] Owner and user space value match; there is a special case in +* wake_futex_pi() where we use pi_state->owner = &init_task to +* make this true for TID 0 and avoid rules 9 and 10.
So you create a transient state with TID 0, but without setting the waiter bit, right? I'll comment on that in the code below.
Quoted 60 lines
kernel/futex.c +20
-30* * [9] There is no transient state which sets the user space TID to 0 * except exit_robust_list(), but this is indicated by the -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, +*
kernel/futex.c void exit_pi_state_list(struct task_stru
Quoted 10 lines
kernel/futex.c +10
-0+* - 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;
So that waiter which is now spinning on pi_mutex->lock has already set the waiters bit, which you undo. So you created the following scenario:
CPU0 CPU1 CPU2
TID 0x1001 TID 0x1000 TID 0x1002
Acquires futex in user space
futex value = 0x1000;futex_lock_pi()
lock_hb() set_waiter_bit() --> futex value = 0x40001000;
futex_unlock_pi()
lock_hb()
attach_to_pi_owner()
rt_mutex_init_proxy_locked()
queue_me()
unlock_hb()
unlock_hb()
rt_mutex_lock() wake_futex_pi()
lock(pi_mutex->lock);
lock(pi_mutex->lock) new_owner is NULL;
--> futex value = 0;
rt_mutex_futex_unlock(pi_mutex);
unlock(pi_mutex->lock);
acquire_rt_mutex() return to user space
Acquires futex in user space
--> futex value = 0x1002
fixup_owner()
fixup_pi_state_owner()
uval = 0x1002;
newval = 0x40001001;
cmpxchg(uval, newval) succeeds
--> futex value = 0x40001001Voila. Inconsistent state .... TID 0x1002 is borked now.
There is no check in fixup_pi_state_owner() for this case as we until now rightfully forced consistent state.
So with this new transient state we really need to check whether uval is what we expect it to be, i.e. 0. The completely untested and probably incorrect patch below might cure the issue in futex_lock_pi(), but does not handle any of the requeue_pi mess.
The other option we have is to set the futex value to FUTEX_WAITERS instead of 0. Have not looked at that variant yet, but it might be simpler as it forces the other task into the kernel instead of giving it the oportunity to steal the futex in user space. Just assumptions as brain melt has already set in.
In any case we must carefully document this new transient state with all its extra bells and whistels.
That transient state 0 made me nervous from the very beginning and I should have seen the hole earlier...
Sorry for spoiling the party once again!
Thanks,
tglx
8<------------------------
kernel/futex.c +23 -8
@@ -2246,16 +2246,27 @@ static int fixup_pi_state_owner(u32 __usif (get_futex_value_locked (&uval, uaddr)) goto handle_fault; -while (1 ) { - newval = (uval &FUTEX_OWNER_DIED ) | newtid; - -if (cmpxchg_futex_value_locked (&curval, uaddr, uval, newval)) - goto handle_fault; -if (curval == uval) -break ; - uval = curval; +/* +* If wake_futex_pi() set the futex to 0 and made init_task the +* transient owner another task might have acquired the futex +* in user space. +*/ +if (oldowner == &init_task && uval !=0 ) { +raw_spin_lock (&pi_state->owner->pi_lock); +list_del_init (&pi_state->list); +raw_spin_unlock (&pi_state->owner->pi_lock); + pi_state->owner =NULL ; +return -EAGAIN ; } + newval = (uval &FUTEX_OWNER_DIED ) | newtid; + +if (cmpxchg_futex_value_locked (&curval, uaddr, uval, newval)) + goto handle_fault; + +if (curval != uval) + goto retry; +/* * We fixed up user space. Now we need to fix the pi_state * itself.
@@ -2679,6 +2690,10 @@ static int futex_lock_pi(u32 __user *uad out_put_key:put_futex_key (&q.key); + +if (ret == -EAGAIN ) + goto retry; + out:if (to)destroy_hrtimer_on_stack (&to->timer);
Peter Zijlstra
maintainerRe: [RFC][PATCH 4/4] futex: Rewrite FUTEX_UNLOCK_PI
Quoted 67 lines · Thomas Gleixner
Quoted 17 lines
(quoted diff) +17
-0+ 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, + *Review
Quoted 10 lines
(quoted diff) +10
-0+ * - 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;So that waiter which is now spinning on
pi_mutex->lockhas already set the waiters bit, which you undo. So you created the following scenario:CPU0 CPU1 CPU2
TID
0x1001TID0x1000TID0x1002Acquires futex in user space futex value = 0x1000;
futex_lock_pi()lock_hb() set_waiter_bit() --> futex value = 0x40001000;futex_unlock_pi() lock_hb() attach_to_pi_owner() rt_mutex_init_proxy_locked() queue_me() unlock_hb() unlock_hb() rt_mutex_lock() wake_futex_pi() lock(pi_mutex->lock); lock(pi_mutex->lock) new_owner is NULL; --> futex value = 0; rt_mutex_futex_unlock(pi_mutex); unlock(pi_mutex->lock); acquire_rt_mutex() return to user space Acquires futex in user space --> futex value = 0x1002 fixup_owner() fixup_pi_state_owner() uval = 0x1002; newval = 0x40001001; cmpxchg(uval, newval) succeeds --> futex value = 0x40001001
Quoted 1 line
Voila. Inconsistent state .... TID
0x1002is borked now.
Urgh, right.
Quoted 2 lines
The other option we have is to set the futex value to
FUTEX_WAITERSinstead of 0.
Yeah, I initially did that but didn't really like it, I then went on to convince myself setting it to 0 was good, silly me. Leaking the WAITERS bit is _by_far_ the simplest option though.
Ok, I went and implemented various broken and discarded alternatives while re-learning all about futexes that I forgot the past few weeks, while trying to figure out wtf the below does.
I also tried to create some 4+ CPU races that would hit holes in the below, no luck so far.
kernel/futex.c static int fixup_pi_state_owner(u32 __us · line 2253
Quoted 11 lines
kernel/futex.c +5
-0@@ -2246,16 +2246,27 @@ static int fixup_pi_state_owner(u32 __usif (get_futex_value_locked (&uval, uaddr)) goto handle_fault; +/* +* If wake_futex_pi() set the futex to 0 and made init_task the +* transient owner another task might have acquired the futex +* in user space. +*/
True, but that doesn't explain why we do this. Naively leaving pi_state->owner set while returning EAGAIN shouldn't be a problem because put_pi_state() should clean that up.
_However_, that does rt_mutex_proxy_unlock() on it as well, and _that_ is a problem, because it's not the rt_mutex owner.
Then again, we can hit this very problem through any of the other put_pi_state() calls after setting ->owner = &init_task I think. Which would argue to special case this in put_pi_state() instead.
Quoted 5 lines
kernel/futex.c +5
-0+if (oldowner == &init_task && uval !=0 ) { +raw_spin_lock (&pi_state->owner->pi_lock); +list_del_init (&pi_state->list); +raw_spin_unlock (&pi_state->owner->pi_lock); + pi_state->owner =NULL ;
kernel/futex.c static int fixup_pi_state_owner(u32 __us · line 2268
Quoted 10 lines
kernel/futex.c +8
-0+return -EAGAIN ; } + newval = (uval &FUTEX_OWNER_DIED ) | newtid; + +if (cmpxchg_futex_value_locked (&curval, uaddr, uval, newval)) + goto handle_fault; + +if (curval != uval) + goto retry;
This is slightly weird in that we loose the obvious cmpxchg loop construct. So I'd write it differently, also that get_futex_value_locked() call is entirely superfluous the second time around, we got curval after all.
kernel/futex.c static int futex_lock_pi(u32 __user *uad · line 2696
Quoted 12 lines
kernel/futex.c +5
-0+/* * We fixed up user space. Now we need to fix the pi_state * itself. @@ -2679,6 +2690,10 @@ static int futex_lock_pi(u32 __user *uad out_put_key:put_futex_key (&q.key); + +if (ret == -EAGAIN ) + goto retry; +
And this is far too clever and really needs a comment. So the crucial point is that this is after unqueue_me_pi(), which drops the pi_state and loops back to lookup the pi_state again, which, hopefully, has now been completely destroyed -- and therefore we hit the regular attach_to_pi_owner() path, fixing up our 'funny' state.
This is where I was playing with 4+ CPU scenarios, to see if we could somehow keep the pi_state alive and not make progress.
I think we can do the retry slightly earlier, right after unqueue_me_pi() and then add retry_queue: right before futex_lock_pi_atomic(), that would avoid dropping the hb->lock (and avoids put/get_futex_key).
kernel/futex.c static int futex_lock_pi(u32 __user *uad · line 2699
Quoted 3 lines
kernel/futex.c +0
-0out:if (to)destroy_hrtimer_on_stack (&to->timer);
Also, since fixup_pi_state_owner() can now return -EAGAIN, all users need handling for that.
I'll try and do a patch that does all that and attempt to write coherent comments on our fancy new state.
Peter Zijlstra
maintainerRe: [RFC][PATCH 4/4] futex: Rewrite FUTEX_UNLOCK_PI
Quoted 9 lines · Peter Zijlstra
Quoted 9 lines
kernel/futex.c +6
-0+if (oldowner == &init_task && uval !=0 ) { +raw_spin_lock (&pi_state->owner->pi_lock); +list_del_init (&pi_state->list); +raw_spin_unlock (&pi_state->owner->pi_lock); + pi_state->owner =NULL ; +return -EAGAIN ;@@ -2679,6 +2690,10 @@ static int futex_lock_pi(u32 __user *uad
Quoted 13 lines
kernel/futex.c static int futex_lock_pi(u32 __user *uad · line 2696
Quoted 6 lines
kernel/futex.c +4
-0out_put_key:put_futex_key (&q.key); + +if (ret == -EAGAIN ) + goto retry; +And this is far too clever and really needs a comment. So the crucial point is that this is after
unqueue_me_pi(), which drops thepi_stateand loops back to lookup thepi_stateagain, which, hopefully, has now been completely destroyed -- and therefore we hit the regularattach_to_pi_owner()path, fixing up our 'funny' state.
I'm stumped on REQUEUE_PI.. this relies on attach_to_pi_owner() and fixup_owner() being in the same function. But this is not the case for requeue. WAIT_REQUEUE has the fixup, as its return path finds it has acquired the outer pi-futex (uaddr2), but the lookup_pi_state() stuff is done by CMP_REQUEUE, which does the actual transfer of the waiters from inner futex (uaddr1) to outer futex (uaddr2).
Maybe I can restructure things a bit, I think CMP_REQUEUE would also know who actually acquired the outer-futex, but I have to think more on this and the brain is pretty fried...
Re: [RFC][PATCH 4/4] futex: Rewrite FUTEX_UNLOCK_PI
Quoted 24 lines · Peter Zijlstra
Quoted 9 lines · Peter Zijlstra
Quoted 9 lines
kernel/futex.c +6
-0+if (oldowner == &init_task && uval !=0 ) { +raw_spin_lock (&pi_state->owner->pi_lock); +list_del_init (&pi_state->list); +raw_spin_unlock (&pi_state->owner->pi_lock); + pi_state->owner =NULL ; +return -EAGAIN ;@@ -2679,6 +2690,10 @@ static int futex_lock_pi(u32 __user *uadQuoted 13 lines
kernel/futex.c static int futex_lock_pi(u32 __user *uad · line 2696
Quoted 6 lines
kernel/futex.c +4
-0out_put_key:put_futex_key (&q.key); + +if (ret == -EAGAIN ) + goto retry; +And this is far too clever and really needs a comment. So the crucial point is that this is after
unqueue_me_pi(), which drops thepi_stateand loops back to lookup thepi_stateagain, which, hopefully, has now been completely destroyed -- and therefore we hit the regularattach_to_pi_owner()path, fixing up our 'funny' state.
Quoted 1 line
I'm stumped on
REQUEUE_PI.. this relies onattach_to_pi_owner()and
You mean LOCK_PI, right?
Quoted 5 lines
fixup_owner()being in the same function. But this is not the case for requeue.WAIT_REQUEUEhas the fixup, as its return path finds it has acquired the outer pi-futex (uaddr2), but thelookup_pi_state()stuff is done byCMP_REQUEUE, which does the actual transfer of the waiters from inner futex (uaddr1) to outer futex (uaddr2).
Correct. WAIT_REQUEUE puts the futex on the inner (uaddr1) and then gets moved to the outer. From there it's the same thing as LOCK_PI.
Quoted 3 lines
Maybe I can restructure things a bit, I think
CMP_REQUEUEwould also know who actually acquired the outer-futex, but I have to think more on this and the brain is pretty fried...
That is irrelevant at requeue time and the owner can change up to the point where the waiter is really woken by a UNLOCK_PI.
Thanks,
tglx
Peter Zijlstra
maintainerRe: [RFC][PATCH 4/4] futex: Rewrite FUTEX_UNLOCK_PI
Quoted 13 lines · Thomas Gleixner
Quoted 1 line
I'm stumped on
REQUEUE_PI.. this relies onattach_to_pi_owner()andYou mean
LOCK_PI, right?Quoted 5 lines
fixup_owner()being in the same function. But this is not the case for requeue.WAIT_REQUEUEhas the fixup, as its return path finds it has acquired the outer pi-futex (uaddr2), but thelookup_pi_state()stuff is done byCMP_REQUEUE, which does the actual transfer of the waiters from inner futex (uaddr1) to outer futex (uaddr2).Correct.
WAIT_REQUEUEputs the futex on the inner (uaddr1) and then gets moved to the outer. From there it's the same thing asLOCK_PI.
Quoted 6 lines
Quoted 3 lines
Maybe I can restructure things a bit, I think
CMP_REQUEUEwould also know who actually acquired the outer-futex, but I have to think more on this and the brain is pretty fried...That is irrelevant at requeue time and the owner can change up to the point where the waiter is really woken by a
UNLOCK_PI.
OK, so clearly I'm confused. So let me try again.
LOCK_PI, does in one function: lookup_pi_state, and fixup_owner. If fixup_owner fails with -EAGAIN, we can redo the pi_state lookup.
The requeue stuff, otoh, has one each. REQUEUE_WAIT has fixup_owner(), CMP_REQUEUE has lookup_pi_state. Therefore, fixup_owner failing with -EAGAIN leaves us dead in the water. There's nothing to go back to to retry.
So far, so 'good', right?
Now, as far as I understand this requeue stuff, we have 2 futexes, an inner futex and an outer futex. The inner futex is always 'locked' and serves as a collection pool for waiting threads.
The requeue crap picks one (or more) waiters from the inner futex and sticks them on the outer futex, which gives them a chance to run.
So WAIT_REQUEUE blocks on the inner futex, but knows that if it ever gets woken, it will be on the outer futex, and hence needs to fixup_owner if the futex and rt_mutex state got out of sync.
CMP_REQUEUEUEUE picks the one (or more) waiters of the inner futex and sticks them on the outer futex.
So far, so 'good' ?
The thing I'm not entire sure on is what happens with the outer futex, do we first LOCK_PI it before doing CMP_REQUEUE, giving us waiters, and then UNLOCK_PI to let them rip? Or do we just CMP_REQUEUE and then let whoever wins finish with UNLOCK_PI?
In any case, I don't think it matters much, either way we can race betwen the 'last' UNLOCK_PI and getting rt_mutex waiters and then hit the &init_task funny state, such that WAIT_REQUEUE waking hits EAGAIN and we're 'stuck'.
Now, if we always CMP_REQUEUE to a locked outer futex, then we cannot know, at CMP_REQUEUE time, who will win and cannot fix up.
The only solution I've come up with so far involves that rt_mutex_proxy_swizzle() muck which you didn't really fancy much.
Peter Zijlstra
maintainerRe: [RFC][PATCH 4/4] futex: Rewrite FUTEX_UNLOCK_PI
Quoted 34 lines · Peter Zijlstra
OK, so clearly I'm confused. So let me try again.
LOCK_PI, does in one function:lookup_pi_state, andfixup_owner. Iffixup_ownerfails with-EAGAIN, we can redo thepi_statelookup.The requeue stuff, otoh, has one each.
REQUEUE_WAIThasfixup_owner(),CMP_REQUEUEhaslookup_pi_state. Therefore,fixup_ownerfailing with-EAGAINleaves us dead in the water. There's nothing to go back to to retry.So far, so 'good', right?
Now, as far as I understand this requeue stuff, we have 2 futexes, an inner futex and an outer futex. The inner futex is always 'locked' and serves as a collection pool for waiting threads.
The requeue crap picks one (or more) waiters from the inner futex and sticks them on the outer futex, which gives them a chance to run.
So
WAIT_REQUEUEblocks on the inner futex, but knows that if it ever gets woken, it will be on the outer futex, and hence needs tofixup_ownerif the futex andrt_mutexstate got out of sync.
CMP_REQUEUEUEUEpicks the one (or more) waiters of the inner futex and sticks them on the outer futex.So far, so 'good' ?
The thing I'm not entire sure on is what happens with the outer futex, do we first
LOCK_PIit before doingCMP_REQUEUE, giving us waiters, and thenUNLOCK_PIto let them rip? Or do we justCMP_REQUEUEand then let whoever wins finish withUNLOCK_PI?
Quoted 7 lines
In any case, I don't think it matters much, either way we can race betwen the 'last'
UNLOCK_PIand gettingrt_mutexwaiters and then hit the&init_taskfunny state, such thatWAIT_REQUEUEwaking hits EAGAIN and we're 'stuck'.Now, if we always
CMP_REQUEUEto a locked outer futex, then we cannot know, atCMP_REQUEUEtime, who will win and cannot fix up.
OTOH, if we always first LOCK_PI before doing CMP_REQUEUE, I don't think we can hit the funny state, LOCK_PI will have fixed it up for us.
So the question is, do we mandate LOCK_PI before CMP_REQUEUE?
Peter Zijlstra
maintainerRe: [RFC][PATCH 4/4] futex: Rewrite FUTEX_UNLOCK_PI
Quoted 41 lines · Peter Zijlstra
Quoted 39 lines · Peter Zijlstra
OK, so clearly I'm confused. So let me try again.
LOCK_PI, does in one function:lookup_pi_state, andfixup_owner. Iffixup_ownerfails with-EAGAIN, we can redo thepi_statelookup.The requeue stuff, otoh, has one each.
REQUEUE_WAIThasfixup_owner(),CMP_REQUEUEhaslookup_pi_state. Therefore,fixup_ownerfailing with-EAGAINleaves us dead in the water. There's nothing to go back to to retry.So far, so 'good', right?
Now, as far as I understand this requeue stuff, we have 2 futexes, an inner futex and an outer futex. The inner futex is always 'locked' and serves as a collection pool for waiting threads.
The requeue crap picks one (or more) waiters from the inner futex and sticks them on the outer futex, which gives them a chance to run.
So
WAIT_REQUEUEblocks on the inner futex, but knows that if it ever gets woken, it will be on the outer futex, and hence needs tofixup_ownerif the futex andrt_mutexstate got out of sync.
CMP_REQUEUEUEUEpicks the one (or more) waiters of the inner futex and sticks them on the outer futex.So far, so 'good' ?
The thing I'm not entire sure on is what happens with the outer futex, do we first
LOCK_PIit before doingCMP_REQUEUE, giving us waiters, and thenUNLOCK_PIto let them rip? Or do we justCMP_REQUEUEand then let whoever wins finish withUNLOCK_PI?In any case, I don't think it matters much, either way we can race betwen the 'last'
UNLOCK_PIand gettingrt_mutexwaiters and then hit the&init_taskfunny state, such thatWAIT_REQUEUEwaking hits EAGAIN and we're 'stuck'.
Quoted 7 lines
Quoted 2 lines
Now, if we always
CMP_REQUEUEto a locked outer futex, then we cannot know, atCMP_REQUEUEtime, who will win and cannot fix up.OTOH, if we always first
LOCK_PIbefore doingCMP_REQUEUE, I don't think we can hit the funny state,LOCK_PIwill have fixed it up for us.So the question is, do we mandate
LOCK_PIbeforeCMP_REQUEUE?
Going by futex_requeue(), the first thing it does; after validation and getting hbs locked, is futex_proxy_trylock_atomic(), which per the comment above it will attempt to acquire uaddr2.
So no such mandate, otherwise that op would not exist and we'd only need to validate that uaddr2 was 'current'.
A well, back to reading more..
Re: [RFC][PATCH 4/4] futex: Rewrite FUTEX_UNLOCK_PI
Quoted 13 lines · Peter Zijlstra
Quoted 12 lines · Peter Zijlstra
Quoted 10 lines · Peter Zijlstra
OK, so clearly I'm confused. So let me try again.
LOCK_PI, does in one function:lookup_pi_state, andfixup_owner. Iffixup_ownerfails with-EAGAIN, we can redo thepi_statelookup.The requeue stuff, otoh, has one each.
REQUEUE_WAIThasfixup_owner(),CMP_REQUEUEhaslookup_pi_state. Therefore,fixup_ownerfailing with-EAGAINleaves us dead in the water. There's nothing to go back to to retry.
Quoted 5 lines
Quoted 5 lines
Quoted 5 lines
So far, so 'good', right?
Now, as far as I understand this requeue stuff, we have 2 futexes, an inner futex and an outer futex. The inner futex is always 'locked' and serves as a collection pool for waiting threads.
Yes.
Quoted 2 lines
Quoted 2 lines
Quoted 2 lines
The requeue crap picks one (or more) waiters from the inner futex and sticks them on the outer futex, which gives them a chance to run.
No. The chance to ran can get only one, if it can acquire the futex in user space directly. If the futex is locked, it is queued on the outer futex/rtmutex and gets to run when the outer futex is unlocked by the owner.
Quoted 3 lines
Quoted 3 lines
Quoted 3 lines
So
WAIT_REQUEUEblocks on the inner futex, but knows that if it ever gets woken, it will be on the outer futex, and hence needs tofixup_ownerif the futex andrt_mutexstate got out of sync.
It can be woken on the inner one as well (signal/timeout), but that does not affect the outer futex, so it's not interesting.
Quoted 11 lines
Quoted 11 lines
Quoted 11 lines
CMP_REQUEUEUEUEpicks the one (or more) waiters of the inner futex and sticks them on the outer futex.So far, so 'good' ?
The thing I'm not entire sure on is what happens with the outer futex, do we first
LOCK_PIit before doingCMP_REQUEUE, giving us waiters, and thenUNLOCK_PIto let them rip? Or do we justCMP_REQUEUEand then let whoever wins finish withUNLOCK_PI?
Quoted 4 lines
Quoted 4 lines
Quoted 4 lines
In any case, I don't think it matters much, either way we can race betwen the 'last'
UNLOCK_PIand gettingrt_mutexwaiters and then hit the&init_taskfunny state, such thatWAIT_REQUEUEwaking hits EAGAIN and we're 'stuck'.
Right, that would be exceptionally bad.
Quoted 6 lines
Quoted 6 lines
Quoted 2 lines
Now, if we always
CMP_REQUEUEto a locked outer futex, then we cannot know, atCMP_REQUEUEtime, who will win and cannot fix up.OTOH, if we always first
LOCK_PIbefore doingCMP_REQUEUE, I don't think we can hit the funny state,LOCK_PIwill have fixed it up for us.
Quoted 8 lines
Quoted 1 line
So the question is, do we mandate
LOCK_PIbeforeCMP_REQUEUE?Going by
futex_requeue(), the first thing it does; after validation and getting hbs locked, isfutex_proxy_trylock_atomic(), which per the comment above it will attempt to acquire uaddr2.So no such mandate, otherwise that op would not exist and we'd only need to validate that uaddr2 was 'current'.
Correct. It can be done with uaddr2 locked or not. That's why we try to take it directly first.
Thanks,
tglx
Peter Zijlstra
maintainerRe: [RFC][PATCH 4/4] futex: Rewrite FUTEX_UNLOCK_PI
In reply to Thomas GleixnerQuoted 39 lines · Thomas Gleixner
So that waiter which is now spinning on
pi_mutex->lockhas already set the waiters bit, which you undo. So you created the following scenario:CPU0 CPU1 CPU2
TID
0x1001TID0x1000TID0x1002Acquires futex in user space futex value = 0x1000;
futex_lock_pi()lock_hb() set_waiter_bit() --> futex value = 0x40001000;futex_unlock_pi() lock_hb() attach_to_pi_owner() rt_mutex_init_proxy_locked() queue_me() unlock_hb() unlock_hb() rt_mutex_lock() wake_futex_pi() lock(pi_mutex->lock); lock(pi_mutex->lock) new_owner is NULL; --> futex value = 0; rt_mutex_futex_unlock(pi_mutex); unlock(pi_mutex->lock); acquire_rt_mutex() return to user space Acquires futex in user space --> futex value = 0x1002 fixup_owner() fixup_pi_state_owner() uval = 0x1002; newval = 0x40001001; cmpxchg(uval, newval) succeeds --> futex value = 0x40001001
Quoted 1 line
Voila. Inconsistent state .... TID
0x1002is borked now.
OK, I think its much worse...
Consider:
CPU0 (tid=0x1000) CPU1 (tid=0x1001) CPU2 (tid=0x1002)
acquire in userspace
*uaddr = 0x1000
futex_lock_pi() acq hb->lock attach_to_pi_owner pi_state->refcount == 1 queue_me rel hb->lock futex_lock_pi() acq hb->lock attach_to_pi_state pi_state->refcount == 2 queue_me rel hb->lock
futex_unlock_pi()
acq pi_mutex->lock
top_waiter == (CPU1 | CPU2)
wake_futex_pi()
new_owner == NULL
pi_state->owner = &init_task
*uaddr = 0
rt_mutex_futex_unlock()ret-to-user
acquire in userspace
*uaddr = 0x1000
Quoted 1 line
From here there's multiple ways to trainwreck the thing, the way you
list above, lets call this A):
rt_mutex_lock() acq hb->lock fixup_owner() cmpxchg(uaddr, 0x1000, 0x40001002) *BORKED CPU0*
alternatively we can do; B):
CPU3 (or CPU0 with a different tid) futex_lock_pi() acq hb->lock attach_to_pi_state() -EINVAL : *uaddr != task_pid_vnr(&init_task)
Now, since CPU1 is pinning the hb->waiter relation, the proposed fixup_owner() -EAGAIN change cannot work either, since, A1):
rt_mutex_lock() acq hb->lock fixup_owner() : -EAGAIN unqueue_me_pi() put_pi_state pi_state->refcount == 1 rel hb->lock goto retry_private retry_private: acq hb->lock attach_to_pi_state() : -EINVAL
Similar things happen with CMP_REQUEUE doing a lookup_pi_state() around this point.
I'm sorely tempted to do the 'simple' thing and leak FUTEX_WAITERS, forcing things into the slow path.
Re: [RFC][PATCH 4/4] futex: Rewrite FUTEX_UNLOCK_PI
In reply to Peter ZijlstraQuoted 8 lines · Peter Zijlstra
kernel/futex.c +8
-0+/* +* 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. +*/
kernel/futex.c static int futex_unlock_pi(u32 __user *u · line 2666
Quoted 10 lines
kernel/futex.c +7
-0+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
Re: [RFC][PATCH 4/4] futex: Rewrite FUTEX_UNLOCK_PI
In reply to Peter ZijlstraQuoted 20 lines · Peter Zijlstra
kernel/futex.c +17
-1top_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
kernel/futex.c static int futex_unlock_pi(u32 __user *u · line 2662
Quoted 10 lines
kernel/futex.c +10
-0+* 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
Peter Zijlstra
maintainerRe: [RFC][PATCH 4/4] futex: Rewrite FUTEX_UNLOCK_PI
Quoted 43 lines · Thomas Gleixner
Quoted 20 lines · Peter Zijlstra
kernel/futex.c +17
-1top_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 kernel/futex.c static int futex_unlock_pi(u32 __user *u · line 2662
Quoted 10 lines
kernel/futex.c +10
-0+* 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()requireshb->lockprotection AFAICT.CPU0 CPU1
wake_futex_pi() attach_to_pi_state() put_pi_state() refcount--; if (!refcount) free_state(); WARN_ON(!pi_state->refcount);
Quoted 2 lines
we might not see the warning, but in any case the following access to
pi_stateon 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).
Quoted 12 lines · Peter Zijlstra
Hi,
During my last PI failing patch set it became obvious there's a number of related fail in
FUTEX_UNLOCK_PIthat 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:
Quoted 7 lines
- perf bench futex lock-pi
- selftests/futexbut 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?
pi_stress.
Peter Zijlstra
maintainerQuoted 5 lines · Davidlohr Bueso
Quoted 1 line · Peter Zijlstra
Do people have more/better futex-pi test cases?
pi_stress.
Where does one find that? Link?
Quoted 3 lines · Peter Zijlstra
Quoted 1 line
pi_stress.Where does one find that? Link?
https://git.kernel.org/cgit/utils/rt-tests/rt-tests.git/tree/src/pi_tests/pi_stress.c
Take the whole package :)
Sebastian
Quoted 8 lines · Peter Zijlstra
Quoted 5 lines · Davidlohr Bueso
Quoted 1 line · Peter Zijlstra
Do people have more/better futex-pi test cases?
pi_stress.Where does one find that? Link?
Sorry, git://git.kernel.org/pub/scm/linux/kernel/git/clrkwllms/rt-tests.git