futex: Cure exit race

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

kernel/futex.c +11 -0

@@ -1148,11 +1148,60 @@ static int attach_to_pi_state(u32 __user
 	return ret;
 }
 
+static int handle_exit_race(u32 __user *uaddr, u32 uval, struct task_struct *tsk)
+{
+	u32 uval2;
+
+	/*
+	 * If PF_EXITPIDONE is not yet set try again.
+	 */
+	if (!(tsk->flags & PF_EXITPIDONE))
+		return -EAGAIN;
+
+	/*

kernel/futex.c +9 -0

+	 *      Set owner died		  attach_to_pi_owner() {
+	 *    *uaddr = 0xC0000000;	   tsk = get_task(PID);
+	 *   }				   if (!tsk->flags & PF_EXITING) {
+	 *  ...				     attach();
+	 *  tsk->flags |= PF_EXITPIDONE;   } else {
+	 *				     if (!(tsk->flags & PF_EXITPIDONE))
+	 *				       return -EAGAIN;
+	 *				     return -ESRCH; <--- FAIL
+	 *				   }

On Mon, Dec 10, 2018 at 04:23:06PM +0100, Thomas Gleixner wrote:
There is another callers of futex_lock_pi_atomic(), futex_proxy_trylock_atomic(), which is part of futex_requeue(), that too does a retry loop on -EAGAIN.

And there is another caller of attach_to_pi_owner(): lookup_pi_state(), and that too is in futex_requeue() and handles the retry case properly.

Yes, this all looks good.

Acked-by Peter Zijlstra (Intel) <[email protected]>

Quoted 11 lines · Peter Zijlstra

On Mon, Dec 10, 2018 at 04:23:06PM +0100, Thomas Gleixner wrote:
There is another callers of futex_lock_pi_atomic(), futex_proxy_trylock_atomic(), which is part of futex_requeue(), that too does a retry loop on -EAGAIN.

And there is another caller of attach_to_pi_owner(): lookup_pi_state(), and that too is in futex_requeue() and handles the retry case properly.

Yes, this all looks good.

Acked-by Peter Zijlstra (Intel) <[email protected]>

Bah. The little devil in the unconcious part of my brain insisted on thinking further about that EAGAIN loop even despite my attempt to page that futex horrors out again immediately after sending that patch.

There is another related issue which is even worse than just mildly confusing user space:

   task1(SCHED_OTHER)
   sys_exit()
     do_exit()
      exit_mm()
       task1->flags |= PF_EXITING;

   ---> preemption

   task2(SCHED_FIFO)
     sys_futex(LOCK_PI)
       ....
       attach_to_pi_owner() {
         ...
         if (!task1->flags & PF_EXITING) {
           attach();
         } else {
              if (!(tsk->flags & PF_EXITPIDONE))
	         return -EAGAIN;

Now assume UP or both tasks pinned on the same CPU. That results in a livelock because task2 is going to loop forever.

No immediate idea how to cure that one w/o creating a mess.

kernel/exit.c void __noreturn do_exit(long code) · line 810

Quoted 7 lines · Peter Zijlstra

On Mon, Dec 10, 2018 at 06:43:51PM +0100, Thomas Gleixner wrote:

kernel/exit.c +2 -0

@@ -806,6 +806,8 @@ void __noreturn do_exit(long code)
 		 * task into the wait for ever nirwana as well.
 		 */
 		tsk->flags |= PF_EXITPIDONE;
+		smp_mb();
+		wake_up_bit(&tsk->flags, 3 /* PF_EXITPIDONE */);

Using ilog2(PF_EXITPIDONE) spares that horrible inline comment and more importantly selects the right bit. 0x04 is bit 2 ....

Quoted 11 lines · Thomas Gleixner

kernel/exit.c void __noreturn do_exit(long code) · line 810

Quoted 7 lines · Peter Zijlstra

On Mon, Dec 10, 2018 at 06:43:51PM +0100, Thomas Gleixner wrote:

kernel/exit.c +2 -0

@@ -806,6 +806,8 @@ void __noreturn do_exit(long code)
 		 * task into the wait for ever nirwana as well.
 		 */
 		tsk->flags |= PF_EXITPIDONE;
+		smp_mb();
+		wake_up_bit(&tsk->flags, 3 /* PF_EXITPIDONE */);

Using ilog2(PF_EXITPIDONE) spares that horrible inline comment and more importantly selects the right bit. 0x04 is bit 2 ....

Plus wake_up_bit() and wait_on_bit() want an unsigned long, but tsk->flags is unsigned int....

Moar staring....

This commit has been processed because it contains a -stable tag. The stable tag indicates that it's relevant for the following trees: all

The bot has tested the following trees: v4.19.8, v4.14.87, v4.9.144, v4.4.166, v3.18.128,

v4.19.8: Build OK!
v4.14.87: Build OK!
v4.9.144: Build failed! Errors:
kernel/futex.c:1186:28: error: ???uaddr??? undeclared (first use in this function)

v4.4.166: Build failed! Errors:
kernel/futex.c:1181:28: error: ???uaddr??? undeclared (first use in this function)

v3.18.128: Build failed! Errors:
kernel/futex.c:1103:28: error: ???uaddr??? undeclared (first use in this function)

How should we proceed with this patch?

Quoted 13 lines · Sasha Levin

This commit has been processed because it contains a -stable tag. The stable tag indicates that it's relevant for the following trees: all

The bot has tested the following trees: v4.19.8, v4.14.87, v4.9.144, v4.4.166, v3.18.128,

v4.19.8: Build OK!
v4.14.87: Build OK!
v4.9.144: Build failed! Errors:
kernel/futex.c:1186:28: error: ???uaddr??? undeclared (first use in this function)

v4.4.166: Build failed! Errors:
kernel/futex.c:1181:28: error: ???uaddr??? undeclared (first use in this function)

Quoted 4 lines

v3.18.128: Build failed! Errors:
kernel/futex.c:1103:28: error: ???uaddr??? undeclared (first use in this function)

How should we proceed with this patch?

I'll look into that once this is sorted... I so love these rotten kernels.

Quoted 4 lines · Thomas Gleixner

Quoted 1 line · Sasha Levin

How should we proceed with this patch?

I'll look into that once this is sorted... I so love these rotten kernels.

It seems we need:

	734009e96d19 ("futex: Change locking rules")

Which isn't trivial to backport.

Stefan reported, that the glibc tst-robustpi4 test case fails occasionally. That case creates the following race between sys_exit() and sys_futex(LOCK_PI):

CPU0 CPU1

sys_exit() sys_futex()
do_exit() futex_lock_pi()
exit_signals(tsk) No waiters:
tsk->flags |= PF_EXITING; *uaddr == 0x00000PID
mm_release(tsk) Set waiter bit

    exit_robust_list(tsk) {	  *uaddr = 0x80000PID;
       Set owner died		  attach_to_pi_owner() {
     *uaddr = 0xC0000000;	   tsk = get_task(PID);
    }				   if (!tsk->flags & PF_EXITING) {
   ...				     attach();
   tsk->flags |= PF_EXITPIDONE;	   } else {
				     if (!(tsk->flags & PF_EXITPIDONE))
				       return -EAGAIN;
				     return -ESRCH; <--- FAIL
				   }

ESRCH is returned all the way to user space, which triggers the glibc test case assert. Returning ESRCH unconditionally is wrong here because the user space value has been changed by the exiting task to 0xC0000000, i.e. the FUTEX_OWNER_DIED bit is set and the futex PID value has been cleared. This is a valid state and the kernel has to handle it, i.e. taking the futex.

Cure it by rereading the user space value when PF_EXITING and PF_EXITPIDONE is set in the task which owns the futex. If the value has changed, let the kernel retry the operation, which includes all regular sanity checks and correctly handles the FUTEX_OWNER_DIED case.

If it hasn't changed, then return ESRCH as there is no way to distinguish this case from malfunctioning user space. This happens when the exiting task did not have a robust list, the robust list was corrupted or the user space value in the futex was simply bogus.

Reported-by Stefan Liebler <[email protected]>

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

Cc Heiko Carstens <[email protected]>

Cc Peter Zijlstra <[email protected]>

Cc Darren Hart <[email protected]>

Cc Ingo Molnar <[email protected]>

Cc [email protected]

Link https://bugzilla.kernel.org/show_bug.cgi?id=200467

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

kernel/futex.c +53 -4

@@ -1148,11 +1148,60 @@ static int attach_to_pi_state(u32 __user
  	return ret;
  }
 
+static int handle_exit_race(u32 __user *uaddr, u32 uval, struct task_struct *tsk)
+{
+	u32 uval2;
+
+	/*
+	 * If PF_EXITPIDONE is not yet set try again.
+	 */
+	if (!(tsk->flags & PF_EXITPIDONE))
+		return -EAGAIN;
+
+	/*
+	 * Reread the user space value to handle the following situation:
+	 *
+	 * CPU0				CPU1
+	 *
+	 * sys_exit()			sys_futex()
+	 *  do_exit()			 futex_lock_pi()
+	 *   exit_signals(tsk)		  No waiters:
+	 *    tsk->flags |= PF_EXITING;	  *uaddr == 0x00000PID
+	 *  mm_release(tsk)		  Set waiter bit
+	 *   exit_robust_list(tsk) {	  *uaddr = 0x80000PID;
+	 *      Set owner died		  attach_to_pi_owner() {
+	 *    *uaddr = 0xC0000000;	   tsk = get_task(PID);
+	 *   }				   if (!tsk->flags & PF_EXITING) {
+	 *  ...				     attach();
+	 *  tsk->flags |= PF_EXITPIDONE;   } else {
+	 *				     if (!(tsk->flags & PF_EXITPIDONE))
+	 *				       return -EAGAIN;
+	 *				     return -ESRCH; <--- FAIL
+	 *				   }
+	 *
+	 * Returning ESRCH unconditionally is wrong here because the
+	 * user space value has been changed by the exiting task.
+	 */
+	if (get_futex_value_locked(&uval2, uaddr))
+		return -EFAULT;
+
+	/* If the user space value has changed, try again. */
+	if (uval2 != uval)
+		return -EAGAIN;
+
+	/*
+	 * The exiting task did not have a robust list, the robust list was
+	 * corrupted or the user space value in *uaddr is simply bogus.
+	 * Give up and tell user space.
+	 */
+	return -ESRCH;
+}
+
  /*
   * Lookup the task for the TID provided from user space and attach to
   * it after doing proper sanity checks.
   */
-static int attach_to_pi_owner(u32 uval, union futex_key *key,
+static int attach_to_pi_owner(u32 __user *uaddr, u32 uval, union futex_key *key,
  			      struct futex_pi_state **ps)
  {
  	pid_t pid = uval & FUTEX_TID_MASK;

@@ -1187,7 +1236,7 @@ static int attach_to_pi_owner(u32 uval,
  		 * set, we know that the task has finished the
  		 * cleanup:
  		 */
-		int ret = (p->flags & PF_EXITPIDONE) ? -ESRCH : -EAGAIN;
+		int ret = handle_exit_race(uaddr, uval, p);
 
  		raw_spin_unlock_irq(&p->pi_lock);
  		put_task_struct(p);

@@ -1244,7 +1293,7 @@ static int lookup_pi_state(u32 __user *u
  	 * We are the first waiter - try to look up the owner based on
  	 * @uval and attach to it.
  	 */
-	return attach_to_pi_owner(uval, key, ps);
+	return attach_to_pi_owner(uaddr, uval, key, ps);
  }
 
  static int lock_pi_update_atomic(u32 __user *uaddr, u32 uval, u32 newval)

@@ -1352,7 +1401,7 @@ static int futex_lock_pi_atomic(u32 __us
  	 * attach to the owner. If that fails, no harm done, we only
  	 * set the FUTEX_WAITERS bit in the user space variable.
  	 */
-	return attach_to_pi_owner(uval, key, ps);
+	return attach_to_pi_owner(uaddr, uval, key, ps);
  }
 
  /**

does this also handle the ESRCH returned by
attach_to_pi_owner(...)
{...

	if (!pid)
		return -ESRCH;
	p = find_get_task_by_vpid(pid);
	if (!p)
		return -ESRCH;

...

I think pid should never be zero when attach_to_pi_owner is called.

But it can happen that p is null? At least I traced the "return -ESRCH" with the 4.17 kernel. Unfortunately both returns were done by the same instruction address.