[patch 00/12] futex: Cure robust/PI futex exit races

* [patch 00/12] futex: Cure robust/PI futex exit races
@ 2019-11-06 21:55 Thomas Gleixner
  2019-11-06 21:55 ` [patch 01/12] futex: Prevent robust futex exit race Thomas Gleixner
                   ` (16 more replies)
  0 siblings, 17 replies; 54+ messages in thread
From: Thomas Gleixner @ 2019-11-06 21:55 UTC (permalink / raw)
  To: LKML
  Cc: Peter Zijlstra, Ingo Molnar, Darren Hart, Yi Wang, Yang Tao,
	Oleg Nesterov, Florian Weimer, Carlos O'Donell,
	Alexander Viro

This series addresses a couple of robust/PI futex exit races:

 1) The unlock races debugged and fixed by Yi and Yang

    These races are really subtle and I'm still puzzled how to trigger them
    reliably enough to decode them.

    The basic issue is that:

    A) An unlocking task can be killed between clearing the user space
       futex value and calling futex(FUTEX_WAKE).

    B) A woken up waiter can be killed before it can acquire the futex
       after returning to user space.

    In both cases the futex value is 0 and due to that the robust list exit
    code refuses to wake up waiters as the futex is not owned by the
    exiting task. As a consequence all other waiters might be blocked
    forever.

 2) Oleg provided a test case which causes an infinite loop in the
    futex_lock_pi() code.

    The problem there is that an exiting task might be preempted by a
    waiter in a state which makes the waiter busy wait for the exiting task
    to complete the robust/PI exit cleanup code.

    That's obviously impossible when the waiter has higher priority than
    the exiting task and both are pinned on the same CPU resulting in a
    live lock.

#1 is a straight forward and simple fix 

    The solution Yi and Yang provided looks solid and in the worst case
    causes a spurious wakeup of a waiter which is nothing to worry about
    as all waiter code has to be prepared for that anyway.

#2 is more complex

   In the current implementation there is no way to block until the exiting
   task has finished the cleanup.

   To fix this there is quite some code reshuffling required which at the
   same time is a valuable cleanup.

   The final solution is to guard the futex exit handling with a per task
   mutex and make the waiter block on that mutex until the exiting task has
   the cleanup completed.

   Details why a simpler solution is not feasible can be found here:

   https://lore.kernel.org/r/20191105152728.GA5666@redhat.com

   Ignore my confusion of fork vs. vfork at the beginning of the thread.
   Futexes do that to human brains. :)

The following series addresses both issues.

Patch 1 is a slightly polished version of the original Yi and Yang
submission. It is included for completeness sake and because it
creates conflicts with the larger surgery which fixes issue #2. 

Aside of that a few eyeballs more on that subtlety are definitely not
a bad thing especially as this has a user space component in it.

The rest of the series addresses issue #2 which is more or less a kernel
only problem, but extra eyeballs are appreciated.

I'm certainly not proud about the solution for #2 but it's the best I could
come up with without violating the user/kernel state consistency
constraints.

Rusty Russell was definitely right when he said that futexes are cursed,
but as Peter Zijlstra pointed out he should have named them SNAFUtex
right away.

The series is also available from git:

  git://git.kernel.org/pub/scm/linux/kernel/git/tip/tip.git WIP.locking/futex

Thanks,

	tglx

8<-------------

 fs/exec.c                |    2 
 include/linux/compat.h   |    2 
 include/linux/futex.h    |   38 +++--
 include/linux/sched.h    |    3 
 include/linux/sched/mm.h |    6 
 kernel/exit.c            |   30 ----
 kernel/fork.c            |   40 ++---
 kernel/futex.c           |  324 ++++++++++++++++++++++++++++++++++++++++-------
 8 files changed, 330 insertions(+), 115 deletions(-)

^ permalink raw reply	[flat|nested] 54+ messages in thread