futex: fix a race condition between REQUEUE_PI and task death

pi_state_free and exit_pi_state_list both clean up futex_pi_state's. exit_pi_state_list takes the hb lock first, and most callers of pi_state_free do too. requeue_pi didn't, which causes lots of problems. Move the pi_state_free calls in requeue_pi to before it drops the hb locks which it's already holding.

I have test code that forks a bunch of processes, which all fork more processes that do futex(FUTEX_WAIT_REQUEUE_PI), then do futex(FUTEX_CMP_REQUEUE_PI) before killing the waiting processes. That test consistently breaks QEMU VMs without this patch.

Although they both make it faster to crash, CONFIG_PREEMPT_RT and lots of CPUs are not necessary to reproduce this problem. The symptoms range from random reboots to corrupting the test program to corrupting whole filesystems to strange BIOS errors. Crashdumps (when they get created at all) are usually a mess, to the point of crashing tools used to examine them.

Signed-off-by Brian Silverman <[email protected]>

---
I am not subscribed to the list so please CC me on any responses.

 kernel/futex.c |   32 +++++++++++++++++++++-----------
 1 file changed, 21 insertions(+), 11 deletions(-)

kernel/futex.c +21 -12

index 815d7af..dc69775 100644
@@ -639,6 +639,9 @@ static struct futex_pi_state * alloc_pi_state(void)
        return pi_state;
 }
 
+/**
+ * Must be called with the hb lock held.
+ */
 static void free_pi_state(struct futex_pi_state *pi_state)
 {
        if (!atomic_dec_and_test(&pi_state->refcount))

@@ -1519,15 +1522,6 @@ static int futex_requeue(u32 __user *uaddr1, unsigned int flags,
        }
 
 retry:
-       if (pi_state != NULL) {
-               /*
-                * We will have to lookup the pi_state again, so free this one
-                * to keep the accounting correct.
-                */
-               free_pi_state(pi_state);
-               pi_state = NULL;
-       }
-
        ret = get_futex_key(uaddr1, flags & FLAGS_SHARED, &key1, VERIFY_READ);
        if (unlikely(ret != 0))
                goto out;

@@ -1558,6 +1552,14 @@ retry_private:
                ret = get_futex_value_locked(&curval, uaddr1);
 
                if (unlikely(ret)) {
+                       if (flags & FLAGS_SHARED && pi_state != NULL) {
+                               /*
+                                * We will have to lookup the pi_state again, so
+                                * free this one to keep the accounting correct.
+                                */
+                               free_pi_state(pi_state);
+                               pi_state = NULL;
+                       }
                        double_unlock_hb(hb1, hb2);
                        hb_waiters_dec(hb2);
 

@@ -1617,6 +1619,10 @@ retry_private:
                case 0:
                        break;
                case -EFAULT:
+                       if (pi_state != NULL) {
+                               free_pi_state(pi_state);
+                               pi_state = NULL;
+                       }
                        double_unlock_hb(hb1, hb2);
                        hb_waiters_dec(hb2);
                        put_futex_key(&key2);

@@ -1632,6 +1638,10 @@ retry_private:
                         *   exit to complete.
                         * - The user space value changed.
                         */
+                       if (pi_state != NULL) {
+                               free_pi_state(pi_state);
+                               pi_state = NULL;
+                       }
                        double_unlock_hb(hb1, hb2);
                        hb_waiters_dec(hb2);
                        put_futex_key(&key2);

@@ -1708,6 +1718,8 @@ retry_private:
        }
 
 out_unlock:
+       if (pi_state != NULL)
+               free_pi_state(pi_state);
        double_unlock_hb(hb1, hb2);
        hb_waiters_dec(hb2);
 

@@ -1725,8 +1737,6 @@ out_put_keys:
 out_put_key1:
        put_futex_key(&key1);
 out:
-       if (pi_state != NULL)
-               free_pi_state(pi_state);
        return ret ? ret : task_count;
 }
 
--

1.7.10.4

Here's the test code:

Here's the test code:

Quoted 2 lines · Brian Silverman

Here's the test code:

I want to say "Thanks!" and pull it into futextest... but destroying filesystems and BIOS errors?!? may not be ideal failure detection modes.

pi_state_free and exit_pi_state_list both clean up futex_pi_state's. exit_pi_state_list takes the hb lock first, and most callers of pi_state_free do too. requeue_pi didn't, which causes lots of problems.

+/**
+ * Must be called with the hb lock held.
+ */

Quoted 3 lines

pi_state_free and exit_pi_state_list both clean up futex_pi_state's. exit_pi_state_list takes the hb lock first, and most callers of pi_state_free do too. requeue_pi didn't, which causes lots of problems.

"causes lots of problems" is not really a good explanation of the root cause. That wants a proper description of the race, i.e.

CPU 0 CPU 1
... ....

I'm surely someone who is familiar with that code, but it took me quite some time to understand whats going on. The casual reader will just go into brain spiral mode and give up.

kernel/futex.c retry_private: · line 1555

Quoted 7 lines

static void free_pi_state(struct futex_pi_state *pi_state)

kernel/futex.c +1 -0

@@ -1558,6 +1552,14 @@ retry_private:
              ret = get_futex_value_locked(&curval, uaddr1);
 
              if (unlikely(ret)) {
+                     if (flags & FLAGS_SHARED && pi_state != NULL) {

Why is this dependend on "flags & FLAGS_SHARED"? The shared/private property has nothing to do with that at all, but I might be missing something.

Quoted 10 lines · Thomas Gleixner

Quoted 3 lines

pi_state_free and exit_pi_state_list both clean up futex_pi_state's. exit_pi_state_list takes the hb lock first, and most callers of pi_state_free do too. requeue_pi didn't, which causes lots of problems.

"causes lots of problems" is not really a good explanation of the root cause. That wants a proper description of the race, i.e.

CPU 0 CPU 1
... ....

Quoted 3 lines

I'm surely someone who is familiar with that code, but it took me quite some time to understand whats going on. The casual reader will just go into brain spiral mode and give up.

Thinking about it again, I'm no longer so sure that exit_pi_state_list is the only place that it can race against. However, I did catch that one with a particularly lucky crashdump, so I know it _can_ happen there. Is just giving an example for that good?

free_pi_state and exit_pi_state_list both clean up futex_pi_state's. exit_pi_state_list takes the hb lock first, and most callers of free_pi_state do too. requeue_pi didn't, which means free_pi_state can free the pi_state out from under exit_pi_state_list. For example:

task A                            |  task B
exit_pi_state_list                |
  pi_state =                      |
      curr->pi_state_list->next   |
                                  |  futex_requeue(requeue_pi=1)
                                  |    // pi_state is the same as
                                  |    // the one in task A
                                  |    free_pi_state(pi_state)
                                  |      list_del_init(&pi_state->list)
                                  |      kfree(pi_state)
  list_del_init(&pi_state->list)  |

Move the free_pi_state calls in requeue_pi to before it drops the hb locks which it's already holding.

I have test code that forks a bunch of processes, which all fork more processes that do futex(FUTEX_WAIT_REQUEUE_PI), then do futex(FUTEX_CMP_REQUEUE_PI) before killing the waiting processes. That test consistently breaks QEMU VMs without this patch.

Although they both make it faster to crash, CONFIG_PREEMPT_RT and lots of CPUs are not necessary to reproduce this problem. The symptoms range from random reboots to corrupting the test program to corrupting whole filesystems to strange BIOS errors. Crashdumps (when they get created at all) are usually a mess, to the point of crashing tools used to examine them.

Signed-off-by Brian Silverman <[email protected]>

---
 kernel/futex.c |   44 +++++++++++++++++++++++++++-----------------
 1 file changed, 27 insertions(+), 17 deletions(-)

kernel/futex.c +27 -17

index 815d7af..c2c35a5 100644
@@ -64,6 +64,7 @@
 #include <linux/hugetlb.h>
 #include <linux/freezer.h>
 #include <linux/bootmem.h>
+#include <linux/lockdep.h>
 
 #include <asm/futex.h>
 

@@ -639,8 +640,16 @@ static struct futex_pi_state * alloc_pi_state(void)
 	return pi_state;
 }
 
-static void free_pi_state(struct futex_pi_state *pi_state)
+/**
+ * Must be called with the hb lock held.
+ */
+static void free_pi_state(struct futex_pi_state *pi_state,
+					struct futex_hash_bucket *hb)
 {
+	if (!pi_state) return;
+
+	lockdep_assert_held(&hb->lock);
+
 	if (!atomic_dec_and_test(&pi_state->refcount))
 		return;
 

@@ -1519,15 +1528,6 @@ static int futex_requeue(u32 __user *uaddr1, unsigned int flags,
 	}
 
 retry:
-	if (pi_state != NULL) {
-		/*
-		 * We will have to lookup the pi_state again, so free this one
-		 * to keep the accounting correct.
-		 */
-		free_pi_state(pi_state);
-		pi_state = NULL;
-	}
-
 	ret = get_futex_key(uaddr1, flags & FLAGS_SHARED, &key1, VERIFY_READ);
 	if (unlikely(ret != 0))
 		goto out;

@@ -1558,6 +1558,12 @@ retry_private:
 		ret = get_futex_value_locked(&curval, uaddr1);
 
 		if (unlikely(ret)) {
+			/*
+			 * We will have to lookup the pi_state again, so
+			 * free this one to keep the accounting correct.
+			 */
+			free_pi_state(pi_state, hb2);
+			pi_state = NULL;
 			double_unlock_hb(hb1, hb2);
 			hb_waiters_dec(hb2);
 

@@ -1617,6 +1623,8 @@ retry_private:
 		case 0:
 			break;
 		case -EFAULT:
+			free_pi_state(pi_state, hb2);
+			pi_state = NULL;
 			double_unlock_hb(hb1, hb2);
 			hb_waiters_dec(hb2);
 			put_futex_key(&key2);

@@ -1632,6 +1640,8 @@ retry_private:
 			 *   exit to complete.
 			 * - The user space value changed.
 			 */
+			free_pi_state(pi_state, hb2);
+			pi_state = NULL;
 			double_unlock_hb(hb1, hb2);
 			hb_waiters_dec(hb2);
 			put_futex_key(&key2);

@@ -1699,7 +1709,7 @@ retry_private:
 			} else if (ret) {
 				/* -EDEADLK */
 				this->pi_state = NULL;
-				free_pi_state(pi_state);
+				free_pi_state(pi_state, hb2);
 				goto out_unlock;
 			}
 		}

@@ -1708,6 +1718,7 @@ retry_private:
 	}
 
 out_unlock:
+	free_pi_state(pi_state, hb2);
 	double_unlock_hb(hb1, hb2);
 	hb_waiters_dec(hb2);
 

@@ -1725,8 +1736,6 @@ out_put_keys:
 out_put_key1:
 	put_futex_key(&key1);
 out:
-	if (pi_state != NULL)
-		free_pi_state(pi_state);
 	return ret ? ret : task_count;
 }
 

@@ -1850,14 +1859,15 @@ retry:
  * PI futexes can not be requeued and must remove themself from the
  * hash bucket. The hash bucket lock (i.e. lock_ptr) is held on entry
  * and dropped here.
+ * Must be called with the hb lock held.
  */
-static void unqueue_me_pi(struct futex_q *q)
+static void unqueue_me_pi(struct futex_q *q, struct futex_hash_bucket *hb)
 	__releases(q->lock_ptr)
 {
 	__unqueue_futex(q);
 
 	BUG_ON(!q->pi_state);
-	free_pi_state(q->pi_state);
+	free_pi_state(q->pi_state, hb);
 	q->pi_state = NULL;
 
 	spin_unlock(q->lock_ptr);

@@ -2340,7 +2350,7 @@ retry_private:
 		rt_mutex_unlock(&q.pi_state->pi_mutex);
 
 	/* Unqueue and drop the lock */
-	unqueue_me_pi(&q);
+	unqueue_me_pi(&q, hb);
 
 	goto out_put_key;
 

@@ -2651,7 +2661,7 @@ static int futex_wait_requeue_pi(u32 __user *uaddr, unsigned int flags,
 			ret = (res < 0) ? res : 0;
 
 		/* Unqueue and drop the lock. */
-		unqueue_me_pi(&q);
+		unqueue_me_pi(&q, hb);
 	}
 
 	/*