futex: More robustness tweaks

The kernel tries to atomically unlock the futex without checking whether there is kernel state associated to the futex.

So if user space manipulated the user space value, this will leave kernel internal state around associated to the owner task.

For robustness sake, lookup first whether there are waiters on the futex. If there are waiters, wake the top priority waiter with all the proper sanity checks applied.

If there are no waiters, do the atomic release. We do not have to preserve the waiters bit in this case, because a potentially incoming waiter is blocked on the hb->lock and will acquire the futex atomically. We neither have to preserve the owner died bit. The caller is the owner and it was supposed to cleanup the mess.

Signed-off-by Thomas Gleixner <[email protected]>

---
 kernel/futex.c |   78
+++++++++++++++++++--------------------------------------
 1 file changed, 26 insertions(+), 52 deletions(-)

Index: linux/kernel/futex.c
===================================================================

kernel/futex.c +0 -5

@@ -1186,22 +1186,6 @@ static int wake_futex_pi(u32 __user *uad
        return 0;
 }
 
-static int unlock_futex_pi(u32 __user *uaddr, u32 uval)
-{
-       u32 uninitialized_var(oldval);
-
-       /*

kernel/futex.c +3 -4

-
 /*
  * Express the locking dependencies for lockdep:
  */

@@ -2401,10 +2385,10 @@ uaddr_faulted:
  */
 static int futex_unlock_pi(u32 __user *uaddr, unsigned int flags)
 {
-       struct futex_hash_bucket *hb;
-       struct futex_q *this, *next;
+       u32 uninitialized_var(curval), uval, vpid =
 task_pid_vnr(current);
        union futex_key key = FUTEX_KEY_INIT;
-       u32 uval, vpid = task_pid_vnr(current);
+       struct futex_hash_bucket *hb;
+       struct futex_q *match;
        int ret;
 

retry:

kernel/futex.c +9 -26

        hb = hash_futex(&key);
        spin_lock(&hb->lock);
 
        /*
-        * To avoid races, try to do the TID -> 0 atomic transition
-        * again. If it succeeds then we can return without waking
-        * anyone else up. We only try this if neither the waiters nor
-        * the owner died bit are set.
-        */
-       if (!(uval & ~FUTEX_TID_MASK) &&
-           cmpxchg_futex_value_locked(&uval, uaddr, vpid, 0))
-               goto pi_faulted;
-       /*
-        * Rare case: we managed to release the lock atomically,
-        * no need to wake anyone else up:
-        */
-       if (unlikely(uval == vpid))
-               goto out_unlock;
-
-       /*
-        * Ok, other tasks may need to be woken up - check waiters
-        * and do the wakeup if necessary:
-        */
-       plist_for_each_entry_safe(this, next, &hb->chain, list) {
-               if (!match_futex (&this->key, &key))
-                       continue;
-               ret = wake_futex_pi(uaddr, uval, this);
+        * Check waiters first. We do not trust user space values at
+        * 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);
                /*
-                * The atomic access to the futex value
-                * generated a pagefault, so retry the
-                * user-access and the wakeup:
+                * The atomic access to the futex value generated a
+                * pagefault, so retry the user-access and the wakeup:

kernel/futex.c +0 -0

 pi_faulted:

Quoted 4 lines · Thomas Gleixner

static int futex_unlock_pi(u32 __user *uaddr, unsigned int flags)

kernel/futex.c +0 -0

@@ -2417,57 +2401,47 @@ retry:
                return -EPERM;
 

kernel/futex.c retry: · line 2405

Quoted 6 lines

kernel/futex.c +2 -2

        ret = get_futex_key(uaddr, flags & FLAGS_SHARED, &key,
 VERIFY_WRITE);
-       if (unlikely(ret != 0))
-               goto out;
+       if (ret)
+               return ret;

Looks like you're also trying to move away from a single exit point to multiple exit points. I prefer the single exit (which you've probably noticed :-), but it's a subjective thing, and so long as we are not duplicating cleanup logic, I guess it's fine either way. This change was not mentioned in the commit message though.

Quoted 13 lines

kernel/futex.c +9 -3

+        * Check waiters first. We do not trust user space values at
+        * 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);
                /*
-                * The atomic access to the futex value
-                * generated a pagefault, so retry the
-                * user-access and the wakeup:
+                * The atomic access to the futex value generated a
+                * pagefault, so retry the user-access and the wakeup:

kernel/futex.c retry: · line 2429

Quoted 10 lines

kernel/futex.c +3 -1

                 */
                if (ret == -EFAULT)
                        goto pi_faulted;
                goto out_unlock;
        }
+
        /*
-        * No waiters - kernel unlocks the futex:
+        * We have no kernel internal state, i.e. no waiters in the
+        * kernel. Waiters which are about to queue themself are stuck

themselves

kernel/futex.c retry: · line 2431

Quoted 2 lines

kernel/futex.c +2 -0

+        * on hb->lock. So we can safely ignore them. We do neither
+        * preserve the WAITERS bit not the OWNER_DIED one. We are the

We preserve neither the WAITERS bit nor the OWNER_DIED bit. (the above use of "do" and "not" is incorrect and could easily be misinterpreted).

kernel/futex.c retry: · line 2432

Quoted 1 line

kernel/futex.c +1 -0

+        * owner.

In wake_futex_pi we verify ownership by matching pi_state->owner == current, but here the only test is the TID value, which is set by userspace - which we don't trust...

I'm trying to determine if it matters in this case... if there are no waiters, is the pi_state still around? If so, it does indeed matter, and we should be verifying.

kernel/futex.c retry: · line 2436

Quoted 6 lines

kernel/futex.c +1 -2

         */
-       ret = unlock_futex_pi(uaddr, uval);
-       if (ret == -EFAULT)
+       if (cmpxchg_futex_value_locked(&curval, uaddr, uval, 0))
                goto pi_faulted;
 

This refactoring seems like it would be best done as a prequel patch so as not to confuse cleanup with functional change. At least that is what you and others have beaten into me over the years ;-)

Quoted 7 lines

kernel/futex.c +5 -0

+       /*
+        * If uval has changed, let user space handle it.
+        */
+       ret = (curval == uval) ? 0 : -EAGAIN;
+
 out_unlock:
        spin_unlock(&hb->lock);

kernel/futex.c retry: · line 2446

Quoted 5 lines

kernel/futex.c +0 -2

        put_futex_key(&key);
-
-out:
        return ret;
 

By dropping this you won't return ret, but rather fall through into pi_faulted... which certainly isn't what you wanted.

The need for better test coverage is very evident now :-)

Quoted 8 lines · Darren Hart

On Wed, 2014-06-11 at 20:45 +0000, Thomas Gleixner wrote:
In wake_futex_pi we verify ownership by matching pi_state->owner == current, but here the only test is the TID value, which is set by userspace - which we don't trust...

I'm trying to determine if it matters in this case... if there are no waiters, is the pi_state still around? If so, it does indeed matter, and we should be verifying.

Erm. The whole point of this patch is to do:

- Find existing state first and handle it.

- If no state exists and TID == current, take it

- Otherwise create state

Quoted 16 lines · Thomas Gleixner

Quoted 8 lines · Darren Hart

On Wed, 2014-06-11 at 20:45 +0000, Thomas Gleixner wrote:
In wake_futex_pi we verify ownership by matching pi_state->owner == current, but here the only test is the TID value, which is set by userspace - which we don't trust...

I'm trying to determine if it matters in this case... if there are no waiters, is the pi_state still around? If so, it does indeed matter, and we should be verifying.

Erm. The whole point of this patch is to do:

- Find existing state first and handle it.

- If no state exists and TID == current, take it

Quoted 1 line

- Otherwise create state

Duh, that was the lock path. But here the point is:

- Find existing state first and handle it.

- If no state exists and TID == current, release it

The retry is obvious, right?

Quoted 5 lines · Darren Hart

Quoted 4 lines · Thomas Gleixner

static int futex_unlock_pi(u32 __user *uaddr, unsigned int flags)

kernel/futex.c +0 -0

@@ -2417,57 +2401,47 @@ retry:
                return -EPERM;
 

Quoted 12 lines

kernel/futex.c retry: · line 2405

Quoted 6 lines

kernel/futex.c +2 -2

        ret = get_futex_key(uaddr, flags & FLAGS_SHARED, &key,
 VERIFY_WRITE);
-       if (unlikely(ret != 0))
-               goto out;
+       if (ret)
+               return ret;

Looks like you're also trying to move away from a single exit point to multiple exit points. I prefer the single exit (which you've probably noticed :-), but it's a subjective thing, and so long as we are not duplicating cleanup logic, I guess it's fine either way. This change was not mentioned in the commit message though.

I really did not think about mentioning that :)

Quoted 35 lines

Quoted 13 lines

kernel/futex.c +9 -3

+        * Check waiters first. We do not trust user space values at
+        * 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);
                /*
-                * The atomic access to the futex value
-                * generated a pagefault, so retry the
-                * user-access and the wakeup:
+                * The atomic access to the futex value generated a
+                * pagefault, so retry the user-access and the wakeup:

kernel/futex.c retry: · line 2429

Quoted 10 lines

kernel/futex.c +3 -1

                 */
                if (ret == -EFAULT)
                        goto pi_faulted;
                goto out_unlock;
        }
+
        /*
-        * No waiters - kernel unlocks the futex:
+        * We have no kernel internal state, i.e. no waiters in the
+        * kernel. Waiters which are about to queue themself are stuck

themselves

kernel/futex.c retry: · line 2431

Quoted 2 lines

kernel/futex.c +2 -0

+        * on hb->lock. So we can safely ignore them. We do neither
+        * preserve the WAITERS bit not the OWNER_DIED one. We are the

We preserve neither the WAITERS bit nor the OWNER_DIED bit. (the above use of "do" and "not" is incorrect and could easily be misinterpreted).

kernel/futex.c retry: · line 2432

Quoted 1 line

kernel/futex.c +1 -0

+        * owner.

Quoted 7 lines

In wake_futex_pi we verify ownership by matching pi_state->owner == current, but here the only test is the TID value, which is set by userspace - which we don't trust...

I'm trying to determine if it matters in this case... if there are no waiters, is the pi_state still around? If so, it does indeed matter, and we should be verifying.

Erm. The whole point of this patch is to do:

- Find existing state first and handle it.hehheh

- If no state exists and TID == current, take it

- Otherwise create state

This all happens under hb->lock. So how should something create new state after we looked up existing state?

Quoted 10 lines

kernel/futex.c retry: · line 2436

Quoted 6 lines

kernel/futex.c +1 -2

         */
-       ret = unlock_futex_pi(uaddr, uval);
-       if (ret == -EFAULT)
+       if (cmpxchg_futex_value_locked(&curval, uaddr, uval, 0))
                goto pi_faulted;
 

This refactoring seems like it would be best done as a prequel patch so as not to confuse cleanup with functional change. At least that is what you and others have beaten into me over the years ;-)

Well, yes and no. I'll hapilly discuss that without after clarifying the issue below.

Quoted 7 lines

Quoted 7 lines

kernel/futex.c +5 -0

+       /*
+        * If uval has changed, let user space handle it.
+        */
+       ret = (curval == uval) ? 0 : -EAGAIN;
+
 out_unlock:
        spin_unlock(&hb->lock);

Quoted 8 lines

kernel/futex.c retry: · line 2446

Quoted 5 lines

kernel/futex.c +0 -2

        put_futex_key(&key);
-
-out:
        return ret;
 

By dropping this you won't return ret, but rather fall through into pi_faulted... which certainly isn't what you wanted.

By dropping the now unused "out" label I'm not longer returning ret?

The resulting code is:

out_unlock:

	spin_unlock(&hb->lock);
	put_futex_key(&key);
	return ret;

If you can explain me how that "return ret" falls through to pi_faulted magically, then I'm definitely agreeing with you on this:

Quoted 1 line

The need for better test coverage is very evident now :-)

-ENOTENOUGHSLEEP or -ENOTENOUGHCOFFEE or -ENOGLASSES perhaps?

I'm omitting some other politicially incorrect speculations for now.

No point in open coding the same function again.

Signed-off-by Thomas Gleixner <[email protected]>

---
 kernel/futex.c |  128
++++++++++++++++++++++++++++-----------------------------
 1 file changed, 63 insertions(+), 65 deletions(-)

Index: linux/kernel/futex.c
===================================================================

kernel/futex.c +24 -21

@@ -796,87 +796,85 @@ 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_pi_state *pi_state = NULL;
-       struct futex_q *this, *next;
        struct task_struct *p;
        pid_t pid = uval & FUTEX_TID_MASK;
 
-       plist_for_each_entry_safe(this, next, &hb->chain, list) {
-               if (match_futex(&this->key, key)) {
+       if (match) {
+               /*
+                * Sanity check the waiter before increasing the
+                * refcount and attaching to it.
+                */
+               pi_state = match->pi_state;
+               /*
+                * Userspace might have messed up non-PI and PI
+                * futexes [3]
+                */
+               if (unlikely(!pi_state))
+                       return -EINVAL;
+
+               WARN_ON(!atomic_read(&pi_state->refcount));
+
+               /*
+                * Handle the owner died case:
+                */
+               if (uval & FUTEX_OWNER_DIED) {
                        /*
-                        * Sanity check the waiter before increasing
-                        * the refcount and attaching to it.
+                        * exit_pi_state_list sets owner to NULL and
+                        * wakes the topmost waiter. The task which
+                        * acquires the pi_state->rt_mutex will fixup
+                        * owner.
                         */
-                       pi_state = this->pi_state;
-                       /*
-                        * Userspace might have messed up non-PI and
-                        * PI futexes [3]
-                        */
-                       if (unlikely(!pi_state))
-                               return -EINVAL;
-
-                       WARN_ON(!atomic_read(&pi_state->refcount));
-
-                       /*
-                        * Handle the owner died case:
-                        */
-                       if (uval & FUTEX_OWNER_DIED) {
-                               /*
-                                * exit_pi_state_list sets owner to

NULL and
- * wakes the topmost waiter. The task
which
- * acquires the pi_state->rt_mutex
will fixup

kernel/futex.c +0 -5

-                                * owner.
-                                */
-                               if (!pi_state->owner) {
-                                       /*
-                                        * No pi state owner, but the

user
- * space TID is not 0.
Inconsistent

kernel/futex.c +1 -12

-                                        * state. [5]
-                                        */
-                                       if (pid)
-                                               return -EINVAL;
-                                       /*
-                                        * Take a ref on the state and
-                                        * return. [4]
-                                        */
-                                       goto out_state;
-                               }
-
+                       if (!pi_state->owner) {
                                /*
-                                * If TID is 0, then either the dying

owner
- * has not yet executed
exit_pi_state_list()
- * or some waiter acquired the rtmutex
in the
- * pi state, but did not yet fixup the
TID in

kernel/futex.c +0 -3

-                                * user space.
-                                *
-                                * Take a ref on the state and return.

[6]

kernel/futex.c +28 -18

+                                * No pi state owner, but the user
+                                * space TID is not 0. Inconsistent
+                                * state. [5]
                                 */
-                               if (!pid)
-                                       goto out_state;
-                       } else {
+                               if (pid)
+                                       return -EINVAL;
                                /*
-                                * If the owner died bit is not set,
-                                * then the pi_state must have an
-                                * owner. [7]
+                                * Take a ref on the state and
+                                * return. [4]
                                 */
-                               if (!pi_state->owner)
-                                       return -EINVAL;
+                               goto out_state;
                        }
 
                        /*
-                        * Bail out if user space manipulated the
-                        * futex value. If pi state exists then the
-                        * owner TID must be the same as the user
-                        * space TID. [9/10]
+                        * If TID is 0, then either the dying owner
+                        * has not yet executed exit_pi_state_list()
+                        * or some waiter acquired the rtmutex in the
+                        * pi state, but did not yet fixup the TID in
+                        * user space.
+                        *
+                        * Take a ref on the state and return. [6]
                         */
-                       if (pid != task_pid_vnr(pi_state->owner))
+                       if (!pid)
+                               goto out_state;
+               } else {
+                       /*
+                        * If the owner died bit is not set,
+                        * then the pi_state must have an
+                        * owner. [7]
+                        */
+                       if (!pi_state->owner)
                                return -EINVAL;
-
-               out_state:
-                       atomic_inc(&pi_state->refcount);
-                       *ps = pi_state;
-                       return 0;
                }
+
+               /*
+                * Bail out if user space manipulated the
+                * futex value. If pi state exists then the

We want to be a bit more clever in futex_lock_pi_atomic() and separate the possible states. Split out the waiter verification into a separate function. No functional change.

Signed-off-by Thomas Gleixner <[email protected]>

We want to be a bit more clever in futex_lock_pi_atomic() and separate the possible states. Split out the code which attaches the first waiter to the owner into a separate function. No functional change.

Signed-off-by Thomas Gleixner <[email protected]>

futex_lock_pi_atomic() is a maze of retry hoops and loops.

Reduce it to simple and understandable states:

First step is to lookup existing waiters (state) in the kernel.

If there is an existing waiter, validate it and attach to it.

If there is no existing waiter, check the user space value

If the TID encoded in the user space value is 0, take over the futex preserving the owner died bit.

If the TID encoded in the user space value is != 0, lookup the owner task, validate it and attach to it.

Reduces text size by 144 bytes on x8664.

Signed-off-by Thomas Gleixner <[email protected]>

---
 kernel/futex.c |  139 +++++++++++++++++++++------------------------------------
 1 file changed, 53 insertions(+), 86 deletions(-)

Index: linux/kernel/futex.c
===================================================================

kernel/futex.c +17 -13

@@ -956,6 +956,17 @@ static int lookup_pi_state(u32 uval, str
        return attach_to_pi_owner(uval, key, ps);
 }
 
+static int lock_pi_update_atomic(u32 __user *uaddr, u32 uval, u32 newval)
+{
+       u32 uninitialized_var(curval);
+
+       if (unlikely(cmpxchg_futex_value_locked(&curval, uaddr, uval, newval)))
+               return -EFAULT;
+
+       /* If user space value changed, let the caller retry */
+       return curval != uval ? -EAGAIN : 0;
+}
+
 /**
  * futex_lock_pi_atomic() - Atomic work required to acquire a pi aware futex
  * @uaddr:             the pi futex user address

@@ -979,113 +990,67 @@ static int futex_lock_pi_atomic(u32 __us
                                struct futex_pi_state **ps,
                                struct task_struct *task, int set_waiters)
 {
-       int lock_taken, ret, force_take = 0;
-       u32 uval, newval, curval, vpid = task_pid_vnr(task);
-
-retry:
-       ret = lock_taken = 0;
+       u32 uval, newval, vpid = task_pid_vnr(task);
+       struct futex_q *match;
+       int ret;
 
        /*
-        * To avoid races, we attempt to take the lock here again
-        * (by doing a 0 -> TID atomic cmpxchg), while holding all
-        * the locks. It will most likely not succeed.
+        * Read the user space value first so we can validate a few
+        * things before proceeding further.
         */
-       newval = vpid;
-       if (set_waiters)
-               newval |= FUTEX_WAITERS;
-
-       if (unlikely(cmpxchg_futex_value_locked(&curval, uaddr, 0, newval)))
+       if (get_futex_value_locked(&uval, uaddr))
                return -EFAULT;

kernel/futex.c +7 -8

-       }
-
-       uval = curval;
+       match = futex_top_waiter(hb, key);
+       if (match)
+               return attach_to_pi_state(uval, match->pi_state, ps);
 
        /*
-        * Set the FUTEX_WAITERS flag, so the owner will know it has someone
-        * to wake at the next unlock.
+        * No waiter and user TID is 0. We are here because the
+        * waiters or the owner died bit is set or called from
+        * requeue_cmp_pi or for whatever reason something took the
+        * syscall.
         */
-       newval = curval | FUTEX_WAITERS;
-
-       /*

kernel/futex.c +2 -4

-               newval = (curval & ~FUTEX_TID_MASK) | vpid;
-               force_take = 0;
-               lock_taken = 1;
-       }
+               newval = uval & FUTEX_OWNER_DIED;
+               newval |= vpid;

From 3eec2db2654a6cd8dcac3c60acda0f16a3243e29 Mon Sep 17 00:00:00 2001

kernel/futex.c +16 -41

+       }
 
        /*
-        * We took the lock due to forced take over.
+        * First waiter. Set the waiters bit before attaching ourself to
+        * the owner. If owner tries to unlock, it will be forced into
+        * the kernel and blocked on hb->lock.
         */
-       if (unlikely(lock_taken))
-               return 1;
-
+       newval = uval | FUTEX_WAITERS;
+       ret = lock_pi_update_atomic(uaddr, uval, newval);
+       if (ret)
+               return ret;
        /*
-        * We dont have the lock. Look up the PI state (or create it if
-        * we are the first waiter):
+        * If the update of the user space value succeeded, we try to
+        * attach to the owner. If that fails, no harm done, we only
+        * set the FUTEX_WAITERS bit in the user space variable.
         */
-       ret = lookup_pi_state(uval, hb, key, ps);
-
-       if (unlikely(ret)) {
-               switch (ret) {
-               case -ESRCH:
-                       /*
-                        * We failed to find an owner for this
-                        * futex. So we have no pi_state to block
-                        * on. This can happen in two cases:
-                        *
-                        * 1) The owner died
-                        * 2) A stale FUTEX_WAITERS bit
-                        *
-                        * Re-read the futex value.
-                        */
-                       if (get_futex_value_locked(&curval, uaddr))
-                               return -EFAULT;
-
-                       /*
-                        * If the owner died or we have a stale
-                        * WAITERS bit the owner TID in the user space
-                        * futex is 0.
-                        */
-                       if (!(curval & FUTEX_TID_MASK)) {
-                               force_take = 1;
-                               goto retry;
-                       }
-               default:
-                       break;
-               }
-       }
-
-       return ret;
+       return attach_to_pi_owner(uval, key, ps);
 }
 
 /**

@@ -2316,8 +2281,10 @@ retry_private:
                        goto uaddr_faulted;
                case -EAGAIN:
                        /*
-                        * Task is exiting and we just wait for the
-                        * exit to complete.
+                        * Two reasons for this:
+                        * - Task is exiting and we just wait for the
+                        *   exit to complete.
+                        * - The user space value changed.
                         */
                        queue_unlock(hb);
                        put_futex_key(&q.key);

Quoted 3 lines · Thomas Gleixner

futex_lock_pi_atomic() is a maze of retry hoops and loops.

Reduce it to simple and understandable states:

Heh... well...

With this patch applied (1-4 will not reproduce without 5), if userspace wrongly sets the uval to 0, the pi_state can end up being NULL for a subsequent requeue_pi operation:

[   10.426159] requeue: 00000000006022e0 to 00000000006022e4
[   10.427737]   this:ffff88013a637da8
[   10.428749]   waking:ffff88013a637da8
fut2 = 0
[   10.429994]   comparing requeue_pi_key
[   10.431034]   prepare waiter to take the rt_mutex
[   10.432344]   pi_state:          (null)
[   10.433414] BUG: unable to handle kernel NULL pointer dereference at

0000000000000038

This occurs in the requeue loop, in the requeue_pi block at:

	atomic_inc(&pi_state->refcount);

Quoted 21 lines · Darren Hart

Quoted 3 lines · Thomas Gleixner

futex_lock_pi_atomic() is a maze of retry hoops and loops.

Reduce it to simple and understandable states:

Heh... well...

With this patch applied (1-4 will not reproduce without 5), if userspace wrongly sets the uval to 0, the pi_state can end up being NULL for a subsequent requeue_pi operation:

[   10.426159] requeue: 00000000006022e0 to 00000000006022e4
[   10.427737]   this:ffff88013a637da8
[   10.428749]   waking:ffff88013a637da8
fut2 = 0
[   10.429994]   comparing requeue_pi_key
[   10.431034]   prepare waiter to take the rt_mutex
[   10.432344]   pi_state:          (null)
[   10.433414] BUG: unable to handle kernel NULL pointer dereference at

0000000000000038

Quoted 3 lines

This occurs in the requeue loop, in the requeue_pi block at:

	atomic_inc(&pi_state->refcount);

Hmm. Took me some time to reproduce. Digging into it now.

Subject: futex: Simplify futex_lock_pi_atomic() and make it more robust
From: Thomas Gleixner <[email protected]>
Date: Wed, 11 Jun 2014 20:45:41 -0000

futex_lock_pi_atomic() is a maze of retry hoops and loops.

Reduce it to simple and understandable states:

First step is to lookup existing waiters (state) in the kernel.

If there is an existing waiter, validate it and attach to it.

If there is no existing waiter, check the user space value

If the TID encoded in the user space value is 0, take over the futex preserving the owner died bit.

If the TID encoded in the user space value is != 0, lookup the owner task, validate it and attach to it.

Reduces text size by 128 bytes on x8664.

Signed-off-by Thomas Gleixner <[email protected]>

Cc Peter Zijlstra <[email protected]>

Cc Darren Hart <[email protected]>

Cc Davidlohr Bueso <[email protected]>

Cc Kees Cook <[email protected]>

Cc [email protected]

Link http://lkml.kernel.org/r/[email protected] open here

Signed-off-by Thomas Gleixner <[email protected]>

---

V2: Fixed the brown paperbag bug of V1

Subject: futex: Simplify futex_lock_pi_atomic() and make it more robust
From: Thomas Gleixner <[email protected]>
Date: Wed, 11 Jun 2014 20:45:41 -0000

futex_lock_pi_atomic() is a maze of retry hoops and loops.

Reduce it to simple and understandable states:

First step is to lookup existing waiters (state) in the kernel.

If there is an existing waiter, validate it and attach to it.

If there is no existing waiter, check the user space value

If the TID encoded in the user space value is 0, take over the futex preserving the owner died bit.

If the TID encoded in the user space value is != 0, lookup the owner task, validate it and attach to it.

Reduces text size by 128 bytes on x8664.

Signed-off-by Thomas Gleixner <[email protected]>

Cc Peter Zijlstra <[email protected]>

Cc Darren Hart <[email protected]>

Cc Davidlohr Bueso <[email protected]>

Cc Kees Cook <[email protected]>

Cc [email protected]

Link http://lkml.kernel.org/r/[email protected] open here

Signed-off-by Thomas Gleixner <[email protected]>

---

V2: Fixed the brown paperbag bug of V1

 kernel/futex.c |  141 ++++++++++++++++++++++-----------------------------------
 1 file changed, 55 insertions(+), 86 deletions(-)

Index: linux/kernel/futex.c
===================================================================

kernel/futex.c +0 -0

@@ -956,6 +956,17 @@ static int lookup_pi_state(u32 uval, str
 	return attach_to_pi_owner(uval, key, ps);
 }
 

From my analysis, this is a good cleanup and makes the code for

kernel/futex.c +45 -86

+
 /**
  * futex_lock_pi_atomic() - Atomic work required to acquire a pi aware futex
  * @uaddr:		the pi futex user address

@@ -979,113 +990,69 @@ static int futex_lock_pi_atomic(u32 __us
 				struct futex_pi_state **ps,
 				struct task_struct *task, int set_waiters)
 {
-	int lock_taken, ret, force_take = 0;
-	u32 uval, newval, curval, vpid = task_pid_vnr(task);
-
-retry:
-	ret = lock_taken = 0;
+	u32 uval, newval, vpid = task_pid_vnr(task);
+	struct futex_q *match;
+	int ret;
 
 	/*
-	 * To avoid races, we attempt to take the lock here again
-	 * (by doing a 0 -> TID atomic cmpxchg), while holding all
-	 * the locks. It will most likely not succeed.
+	 * Read the user space value first so we can validate a few
+	 * things before proceeding further.
 	 */
-	newval = vpid;
-	if (set_waiters)
-		newval |= FUTEX_WAITERS;
-
-	if (unlikely(cmpxchg_futex_value_locked(&curval, uaddr, 0, newval)))
+	if (get_futex_value_locked(&uval, uaddr))
 		return -EFAULT;
 
 	/*
 	 * Detect deadlocks.
 	 */
-	if ((unlikely((curval & FUTEX_TID_MASK) == vpid)))
+	if ((unlikely((uval & FUTEX_TID_MASK) == vpid)))
 		return -EDEADLK;
 
 	/*
-	 * Surprise - we got the lock, but we do not trust user space at all.
+	 * Lookup existing state first. If it exists, try to attach to
+	 * its pi_state.
 	 */
-	if (unlikely(!curval)) {
-		/*
-		 * We verify whether there is kernel state for this
-		 * futex. If not, we can safely assume, that the 0 ->
-		 * TID transition is correct. If state exists, we do
-		 * not bother to fixup the user space state as it was
-		 * corrupted already.
-		 */
-		return futex_top_waiter(hb, key) ? -EINVAL : 1;
-	}
-
-	uval = curval;
+	match = futex_top_waiter(hb, key);
+	if (match)
+		return attach_to_pi_state(uval, match->pi_state, ps);
 
 	/*
-	 * Set the FUTEX_WAITERS flag, so the owner will know it has someone
-	 * to wake at the next unlock.
+	 * No waiter and user TID is 0. We are here because the
+	 * waiters or the owner died bit is set or called from
+	 * requeue_cmp_pi or for whatever reason something took the
+	 * syscall.
 	 */
-	newval = curval | FUTEX_WAITERS;
-
-	/*
-	 * Should we force take the futex? See below.
-	 */
-	if (unlikely(force_take)) {
+	if (!(uval & FUTEX_TID_MASK)) {
 		/*
-		 * Keep the OWNER_DIED and the WAITERS bit and set the
-		 * new TID value.
+		 * We take over the futex. No other waiters and the user space
+		 * TID is 0. We preserve the owner died bit.
 		 */
-		newval = (curval & ~FUTEX_TID_MASK) | vpid;
-		force_take = 0;
-		lock_taken = 1;
-	}
+		newval = uval & FUTEX_OWNER_DIED;
+		newval |= vpid;
 
-	if (unlikely(cmpxchg_futex_value_locked(&curval, uaddr, uval, newval)))
-		return -EFAULT;
-	if (unlikely(curval != uval))
-		goto retry;
+		/* The futex requeue_pi code can enforce the waiters bit */
+		if (set_waiters)
+			newval |= FUTEX_WAITERS;
+
+		ret = lock_pi_update_atomic(uaddr, uval, newval);
+		/* If the take over worked, return 1 */
+		return ret < 0 ? ret : 1;
+	}
 
 	/*
-	 * We took the lock due to forced take over.
+	 * First waiter. Set the waiters bit before attaching ourself to
+	 * the owner. If owner tries to unlock, it will be forced into
+	 * the kernel and blocked on hb->lock.
 	 */
-	if (unlikely(lock_taken))
-		return 1;
-
+	newval = uval | FUTEX_WAITERS;
+	ret = lock_pi_update_atomic(uaddr, uval, newval);
+	if (ret)
+		return ret;
 	/*
-	 * We dont have the lock. Look up the PI state (or create it if
-	 * we are the first waiter):
+	 * If the update of the user space value succeeded, we try to
+	 * attach to the owner. If that fails, no harm done, we only
+	 * set the FUTEX_WAITERS bit in the user space variable.
 	 */
-	ret = lookup_pi_state(uval, hb, key, ps);
-
-	if (unlikely(ret)) {
-		switch (ret) {
-		case -ESRCH:
-			/*
-			 * We failed to find an owner for this
-			 * futex. So we have no pi_state to block
-			 * on. This can happen in two cases:
-			 *
-			 * 1) The owner died
-			 * 2) A stale FUTEX_WAITERS bit
-			 *
-			 * Re-read the futex value.
-			 */
-			if (get_futex_value_locked(&curval, uaddr))
-				return -EFAULT;
-
-			/*
-			 * If the owner died or we have a stale
-			 * WAITERS bit the owner TID in the user space
-			 * futex is 0.
-			 */
-			if (!(curval & FUTEX_TID_MASK)) {
-				force_take = 1;
-				goto retry;
-			}
-		default:
-			break;
-		}
-	}
-
-	return ret;
+	return attach_to_pi_owner(uval, key, ps);
 }
 
 /**

@@ -2316,8 +2283,10 @@ retry_private:
 			goto uaddr_faulted;
 		case -EAGAIN:
 			/*
-			 * Task is exiting and we just wait for the
-			 * exit to complete.
+			 * Two reasons for this:
+			 * - Task is exiting and we just wait for the
+			 *   exit to complete.
+			 * - The user space value changed.
 			 */
 			queue_unlock(hb);
 			put_futex_key(&q.key);

On Fri, 2014-06-13 at 11:44 +0200, Thomas Gleixner wrote:
Two general concerns, we appear to be eliminating both the force_take and the retry.

The force_take only occurs if TID==0, and that is covered here in a cleaner way, so I believe we are good here.

As for the retry, the remaining use case (outside of TID==0 -> force_take=1 -> retry) appears to be that userspace changed the value while we were running. Reading the value early doesn't protect us from this scenario. How does this change account for that?

It looks to me that before we would retry, while here we just give up and return -EAGAIN..., which is addressed in futex_lock_pi(), but not in the futex_requeue() callsite for futex_proxy_trylock_atomic. It does handle it, but I guess also needs a comment update to "The owner was exiting" to include "or userspace changed the value" as you did for futex_lock_pi().

Quoted 1 line

From my analysis, this is a good cleanup and makes the code for

explicit. I'm nervous about missing corner cases, and would like to understand what level of testing this has received. We need to add PI locking tests to futextest. There are some in glibc. Which tests were run to validate PI locking?