futex_unlock_pi() hurts my brain and may cause application deadlock

All,
So we've been seeing PI mutex deadlocks with a few of our applications
using the -rt kernel. After narrowing things down, we were finding that the applications were indirectly calling futex_unlock_pi(), which on occasion would return -EFAULT, which is promptly ignored by glibc. This would cause the application to continue on as if it has unlocked the mutex, until it tried to reacquire it and deadlock.

In looking into why the kernel was returning -EFAULT, I found the following:

...
retry_locked:

	/*
	 * To avoid races, try to do the TID -> 0 atomic transition
	 * again. If it succeeds then we can return without waking
	 * anyone else up:
	 */
	if (!(uval & FUTEX_OWNER_DIED)) {
		pagefault_disable();
		uval = futex_atomic_cmpxchg_inatomic(uaddr, current->pid, 0);
		pagefault_enable();
	}

	if (unlikely(uval == -EFAULT))
		goto pi_faulted;
...[snip]...
pi_faulted:
	/*
	 * We have to r/w  *(int __user *)uaddr, but we can't modify it
	 * non-atomically.  Therefore, if get_user below is not
	 * enough, we need to handle the fault ourselves, while
	 * still holding the mmap_sem.
	 */
	if (attempt++) {
		ret = futex_handle_fault((unsigned long)uaddr, fshared,
					 attempt);
		if (ret)
			goto out_unlock;
		goto retry_locked;
	}

Should we fault through normal causes, on the second round we call futex_handle_fault, which faults in the address, and we then jump back to retry_locked. However, since uval is -EFAULT from the last cmpxchg, it &s w/ FUTEX_OWNER_DIED so we don't enter the first conditional to try to cmpxchg again. So since uval is still -EFAULT, we loop back to pi_faulted! This will loop until futex_handle_fault() bombs out because attempt is too big and we return -EFAULT.

I *think* this is a possible quick fix here, but I'm no futex guru, so I wanted to run it by folks for review.

Big thanks to Sripathi and Angela Lin for helping debug this, and Steven for suggesting a cleaner fix then what I first tried.

thanks
-john

Avoid futex_unlock_pi returning -EFAULT (which results in deadlock), by clearing uval before jumping to retry_locked.

---

index b7ce15c..9969b36 100644
@@ -2011,6 +2011,7 @@ pi_faulted:
 					 attempt);
 		if (ret)
 			goto out_unlock;
+		uval = 0;
 		goto retry_locked;
 	}
 

My question is to all the futex gurus out there.

This code is in futex_unlock_pi. Can the owner of the mutex really die? Isn't the owner the one doing the unlock?

-- Steve

This is part of the implementation of robust PI futexes. The semantics is that if the owner of a robust futex dies the futex is marked with FUTEX_OWNER_DIED. The next locking thread then has to clear that bit before calling pthread_mutex_unlock. If the bit is still set while unlocking the mutex is permanently marked unusable. I cannot say right now whether this is the semantics implemented above. I'll have to check the glibc test suite whether we check for that semantic.

[CC'ing Uli because John forgot to with the original patch]

As John found with futex_unlock_pi (which that patch should apply nicely to the -rt tree), the code can get screwed up with faulting in at the cmpxchg in futex_unlock_pi code.

----
In looking into why the kernel was returning -EFAULT, I found the following:

...
retry_locked:
/*
* To avoid races, try to do the TID -> 0 atomic transition
* again. If it succeeds then we can return without waking
* anyone else up:
*/
if (!(uval & FUTEX_OWNER_DIED)) {
pagefault_disable();
uval = futex_atomic_cmpxchg_inatomic(uaddr,

current->pid, 0);
                pagefault_enable();
        }

        if (unlikely(uval == -EFAULT))
                goto pi_faulted;
...[snip]...
pi_faulted:
        /*
         * We have to r/w  *(int __user *)uaddr, but we can't modify it
         * non-atomically.  Therefore, if get_user below is not
         * enough, we need to handle the fault ourselves, while
         * still holding the mmap_sem.
         */
        if (attempt++) {
                ret = futex_handle_fault((unsigned long)uaddr, fshared,
                                         attempt);
                if (ret)
                        goto out_unlock;
                goto retry_locked;
        }

----

We see that uval is -EFAULT when jumping to pi_faulted. But when it goes back to retry_locked, the uval is still -EFAULT. Which just happens to have the FUTEX_OWNER_DIED bit set. So we don't do the futex_atomic_cmpxchg_inatomic call, and go to the next conditional which just so happens to be a check of uval for -EFAULT. And guess what? it still is!!

Way to go John in finding this!!

But, the -rt kernel has pretty much the same code for the futex_unlock_pi64, and it has the same bug. Hence this email.

This patch is the same fix that John posted, but simply for the futex_unlock_pi64 that exists in the RT kernel and not the mainline.

Index: linux-2.6-rt-work/kernel/futex.c
===================================================================
@@ -3503,6 +3503,7 @@ pi_faulted:
 			ret = -EFAULT;
 			goto out_unlock;
 		}
+		uval = 0;
 		goto retry_locked;
 	}
 

Ingo,

This patch contains both John's and mine for -rt. Might as well make it a single patch to pull in.

---

Index: linux-2.6.21-rt9/kernel/futex.c
===================================================================
@@ -1839,6 +1839,7 @@ static int futex_lock_pi(u32 __user *uad
 			ret = -EFAULT;
 			goto out_unlock_release_sem;
 		}
+		uval = 0;
 		goto retry_locked;
 	}
 

@@ -3503,6 +3504,7 @@ pi_faulted:
 			ret = -EFAULT;
 			goto out_unlock;
 		}
+		uval = 0;
 		goto retry_locked;
 	}
 

Why would you use futex_unlock_pi64?

In fact, the whole 64-bit futex patch should be reviewed and cut down to the bare minimum. I know, I was asking for it loudly but it became to Jakub and me after adding the private futexes that all these orthogonal extensions don't make sense. So far we need 64-bit futexes only for some rwlocks and here only a few operations (wait, wake). We don't need 64-bit extended to PI, we don't need requeue.

Yes, if we had started out with 64-bit futexes on 64-bit platforms, that would be fine. But as it is today making 64-bit a new dimension is not needed.

Do you have a URL or subject line for the discussion? I'll take a look and give them a whirl.

thanks
-john

i meant to say Alexey, not Oleg :-) Here's the thread:

http://lkml.org/lkml/2007/5/7/129

i've Cc:-ed Alexey too.

Ingo

I haven't had a chance to run it, but reviewing at Alexey's changes, they do not look to be sufficient to the issue we were hitting. We still need to clear uval to avoid -EFAULT &'ing w/ FUTEX_OWNER_DIED.

Here's the patch against -rt9 (which also contains Alexey's fix)

diff -rup 2.6-rt/kernel/futex.c 2.6-rtnew/kernel/futex.c
@@ -1954,6 +1954,7 @@ pi_faulted:
 			ret = -EFAULT;
 			goto out_unlock;
 		}
+		uval = 0;
 		goto retry_locked;
 	}
 

@@ -3503,6 +3504,7 @@ pi_faulted:
 			ret = -EFAULT;
 			goto out_unlock;
 		}
+		uval = 0;
 		goto retry_locked;
 	}
 

Hey Ingo,
I sent this fix for this back in the 2.6.21-rt9 era, and I thought to
picked it up, but I think it arrived amid some futex churn and apparently has been dropped or was just lost.

Some of our testers have been reporting futex deadlocks and this fix resolves it, so I believe it to still be needed.

thanks
-john

Avoid futex_unlock_pi returning -EFAULT (which results in deadlock), by clearing uval before jumping to retry_locked.

Index: 2.6-rt/kernel/futex.c
===================================================================
@@ -1673,6 +1673,7 @@ pi_faulted:
 					 attempt);
 		if (ret)
 			goto out;
+		uval = 0;
 		goto retry_unlocked;
 	}
 

--

Heh, I remember this bug. Wasn't there another patch that modified this. I almost definitly remember this getting into the patch queue, but it must have been dropped later.

John, thanks for looking into this deeper!

From: john stultz <[email protected]>
Date: Tue, 31 Jul 2007 16:53:39 -0700

This bug seems to exist in mainline too.

Sparc users have been seeing something that smells like this bug, I will ask them to test this fix out.

hmm ... so the many rounds of pi-futex fixes from Alexey and Thomas did not resolve that deadlock?

Ingo