[PATCH] futex: Prevent robust futex exit race more

[Keno Fischer]

A robust futex unlock stores 0 over the whole futex value - wiping
FUTEX_WAITERS - and wakes a single waiter. That wakeup is a one-shot
notification: the protocol relies on its recipient to either acquire
the futex (and eventually unlock while aware of the remaining
contention) or re-arm FUTEX_WAITERS before sleeping again.
If the woken waiter is killed before it can do either, the kernel
must jump in and wake the next task down the line.

This is a known complication of the futex protocol with a previous
partial fix in commit ca16d5bee598 ("futex: Prevent robust futex exit
race"). Unfortunately, that fix is insufficient.

If a third task re-acquired the futex through the uncontended fast
path in the meantime, the notification is lost: Robust exit processing
sees that it is owned by another task and does nothing, while the new
owner sees no FUTEX_WAITERS when it unlocks and wakes nobody.
The remaining waiters sleep forever behind a free futex:

  A owns the futex, B and C sleep in FUTEX_WAIT
                                        uval == A | FUTEX_WAITERS
  A robust unlock: store 0, FUTEX_WAKE(1) wakes B
                                        uval == 0
  D fast path acquire: cmpxchg(0 -> D)
                                        uval == D, no FUTEX_WAITERS
  B killed before acting on the wakeup
  B exit walk, pending op: owner D != B -> no action
  D unlock: no FUTEX_WAITERS -> no wake
                                        C sleeps forever

Fix this by augmenting the robust list exit processing to also
perform the extra wakeup if the futex word is owned by another
thread but FUTEX_WAITERS is *NOT* set.

Fixes: ca16d5bee598 ("futex: Prevent robust futex exit race")
Cc: stable@xxxxxxxxxxxxxxx
Signed-off-by: Keno Fischer <keno@xxxxxxxxxxxx>
Assisted-by: ClaudeCode:claude-fable-5 tla+
---

This issues was discovered as part of a larger attempt to resolve the
long-standing issue that robust futexes are not safely usable across
pid namespaces. I will be submitting an RFC series for that proposal
at some point in the near future. However, as part of an AI-assisted
attempt to formally verify the correctness of that protocol using TLA+,
I obtained the above described counter-example which is also present on
current mainline. A standalone (AI-generated) reproducer showing the
lost-wakeup issue using glibc pthread mutexes is available in my WIP
repository for that effort at:

Link: https://github.com/Keno/robust-futex-cookies/blob/main/repro/robust_lost_wakeup_glibc.c

---
 kernel/futex/core.c | 85 +++++++++++++++++++++++++++++++--------------
 1 file changed, 58 insertions(+), 27 deletions(-)

diff --git a/kernel/futex/core.c b/kernel/futex/core.c
index 179b26e9c934..74aa6aa87eb9 100644
--- a/kernel/futex/core.c
+++ b/kernel/futex/core.c
@@ -982,8 +982,11 @@ static int handle_futex_death(u32 __user *uaddr,
struct task_struct *curr,
                return -1;

        /*
-        * Special case for regular (non PI) futexes. The unlock path in
-        * user space has two race scenarios:
+        * Special case for regular (non PI) futexes. Ordinarily, we do
+        * not perform any processing here unless the current thread was
+        * the owner of the futex (by the TID check below).
+        *
+        * However, the unlock path has three race scenarios:
         *
         * 1. The unlock path releases the user space futex value and
         *    before it can execute the futex() syscall to wake up
@@ -992,42 +995,70 @@ static int handle_futex_death(u32 __user *uaddr,
struct task_struct *curr,
         * 2. A woken up waiter is killed before it can acquire the
         *    futex in user space.
         *
-        * In the second case, the wake up notification could be generated
-        * by the unlock path in user space after setting the futex value
-        * to zero or by the kernel after setting the OWNER_DIED bit below.
+        * 3. A woken up waiter is killed in user space after another
+        *    thread has acquired the futex, but before it can set
+        *    FUTEX_WAITERS.
+        *
+        * Note that, if userspace uses the FUTEX_ROBUST_UNLOCK flag, we
+        * will not see case 1 here.
+        *
+        * In the second and third case, the wake up notification could
+        * be generated from any of:
+        *
+        *    i.   An ordinary futex wakeup after unlock (with or
+        *         without FUTEX_ROBUST_UNLOCK)
+        *    ii.  A robust wakeup from another thread's death
+        *    iii. A previous round through this special case
+        *
+        * As a result, the futex world will be in one of four states:
+        *
+        *    A. The futex word is 0 (unlocked)
+        *    B. The futex word is owned by another thread
+        *       (FUTEX_WAITERS is not set)
+        *    C. The futex word is owned by another thread
+        *       (FUTEX_WAITERS set)
+        *    D. The futex's owner died and OWNER_DIED is set
+        *       (the owner part of the word is 0)
         *
-        * In both cases the TID validation below prevents a wakeup of
-        * potential waiters which can cause these waiters to block
-        * forever.
+        * The key issue is that the kernel usually (at least from
+        * sources ii. and iii. or when so requested by userspace from
+        * source i.) only ever wakes *one* waiter at a time. If this
+        * waiter dies before acquiring the futex (or setting the
+        * FUTEX_WAITERS bit), the kernel *must* still wake the next
+        * waiter down the line to uphold the futex invariants and
+        * avoid lost wakeups. Note we do not need to handle state C,
+        * as it does not matter to us whether *we* successfully set
+        * the bit or a third thread did so in the meantime.
         *
-        * In both cases the following conditions are met:
+        * Therefore, in these cases we must issue an additional
+        * futex_wake(). Note however that we *must not* set OWNER_DIED
+        * here. Our thread is *not* the owner of the futex.
         *
-        *      1) task->futex.robust_list->list_op_pending != NULL
-        *         @pending_op == true
-        *      2) The owner part of user space futex value == 0
+        * Thus to summarize, the conditions for needing the additional
+        * futex_wake() are:
+        *
+        *      1) @pending_op == true (the thread has not finished the
+        *         mutex operation)
+        *      2) The futex word is in one of the states A, B or D
         *      3) Regular futex: @pi == false
         *
-        * If these conditions are met, it is safe to attempt waking up a
-        * potential waiter without touching the user space futex value and
-        * trying to set the OWNER_DIED bit. If the futex value is zero,
-        * the rest of the user space mutex state is consistent, so a woken
-        * waiter will just take over the uncontended futex. Setting the
-        * OWNER_DIED bit would create inconsistent state and malfunction
-        * of the user space owner died handling. Otherwise, the OWNER_DIED
-        * bit is already set, and the woken waiter is expected to deal with
-        * this.
+        * Note in particular that in all of the states A-D the owner
+        * portion of the futex word differs from our thread's TID
+        * (unless the actual owner has the same TID in another PID
+        * namespace, but we cannot currently distinguish that
+        * scenario), so this can be a special-case wakeup in the bail
+        * path of the ordinary TID check.
         */
        owner = uval & FUTEX_TID_MASK;

-       if (pending_op && !pi && !owner) {
-               futex_wake(uaddr, FLAGS_SIZE_32 | FLAGS_SHARED, NULL, 1,
-                          FUTEX_BITSET_MATCH_ANY);
+       if (owner != task_pid_vnr(curr)) {
+               if (pending_op && !pi &&
+                   (!owner || !(uval & FUTEX_WAITERS)))
+                       futex_wake(uaddr, FLAGS_SIZE_32 | FLAGS_SHARED, NULL, 1,
+                                  FUTEX_BITSET_MATCH_ANY);
                return 0;
        }

-       if (owner != task_pid_vnr(curr))
-               return 0;
-
        /*
         * Ok, this dying thread is truly holding a futex
         * of interest. Set the OWNER_DIED bit atomically
--
2.54.0