futex: Prevent robust futex exit race more
Subsystems (4)
PATCH 1/1 futex: Prevent robust futex exit race more
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.
---
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:
--- kernel/futex/core.c | 85 +++++++++++++++++++++++++++++++-------------- 1 file changed, 58 insertions(+), 27 deletions(-)
kernel/futex/core.c +0 -0
@@ -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
Thomas Gleixner
maintainerQuoted 12 lines · Keno Fischer
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_WAITERSwhen it unlocks and wakes nobody. The remaining waiters sleep forever behind a free futex:A owns the futex, B and C sleep in
FUTEX_WAITuval == 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
Quoted 8 lines
B killed before acting on the wakeup
B exit walk, pending op: owner D != B -> no action D unlock: noFUTEX_WAITERS-> no wake
C sleeps foreverFix 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_WAITERSis *NOT* set.
While your change "fixes" this particular problem, it leaves the related UAF problem unsolved.
The more complete solution is:
https://lore.kernel.org/all/[email protected]/
which is upstream now. Specifically the combined unlock/wake part
https://lore.kernel.org/all/[email protected]/
ensures that your scenario can't happen and provides at the same time one part of the solution for the UAF exit race.
Quoted 3 lines
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.
What's the actual problem with that?
Thanks,
tglx
Quoted 10 lines · Thomas Gleixner
Quoted 3 lines · Keno Fischer
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_WAITERSis *NOT* set.While your change "fixes" this particular problem, it leaves the related UAF problem unsolved.
The more complete solution is:
Quoted 8 lines
https://lore.kernel.org/all/[email protected]/which is upstream now. Specifically the combined unlock/wake part
https://lore.kernel.org/all/[email protected]/ensures that your scenario can't happen and provides at the same time one part of the solution for the UAF exit race.
Yes, I'm aware of that patch series.
However, this is not quite the same race.
As the updated comment indicates, the combined unlock/wake prevents one of the three race scenarios that causes problems.
However, if a *woken up* task dies before it can re-acquire the futex, the kernel must still pass the baton down the line to the next task. The existing code handled this case for the scenario where there was no interfering third task (the second scenario in the original comment). However, the possibility that a third task could perform an uncontested acquire in the meantime was not accounted for.
Quoted 5 lines
Quoted 3 lines
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.
What's the actual problem with that?
I was planning to write it up with that patch series, but here's the abbreviated version: Embedded databases (e.g. LMBD) use shared-memory robust mutexes (glibc pthread_mutex in the LMDB case) to coordinate access to the database file among users. However, if those users are in different pid namespaces, the mutex silently fails to provide mutual exclusion, causing corruption and hangs (bad for a database). We (the Julia programming language project) found this out when we added an LMDB-backed cache to our compiler. As it turns out, a significant fraction of our users like to bind mount the directory in question into their containers (because sharing the caches makes things faster and they're using the containers for consistency of environment not as a security boundary) or share it among multiple different containers (AI sandboxes are a common example). For now we're detecting this scenario and disabling the cache, but it doesn't seem like a patently unreasonable use case to me. Yes, perhaps it's a bit odd to have shared-memory communication over what is supposed to be a an isolation boundary, but it is what users do In actual practice.
Thomas Gleixner
maintainerQuoted 20 lines · Keno Fischer
Quoted 10 lines · Thomas Gleixner
Quoted 3 lines · Keno Fischer
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_WAITERSis *NOT* set.While your change "fixes" this particular problem, it leaves the related UAF problem unsolved.
The more complete solution is:
Quoted 8 lines
https://lore.kernel.org/all/[email protected]/which is upstream now. Specifically the combined unlock/wake part
https://lore.kernel.org/all/[email protected]/ensures that your scenario can't happen and provides at the same time one part of the solution for the UAF exit race.
Quoted 10 lines
Yes, I'm aware of that patch series.
However, this is not quite the same race.
As the updated comment indicates, the combined unlock/wake prevents one of the three race scenarios that causes problems.
However, if a *woken up* task dies before it can re-acquire the futex, the kernel must still pass the baton down the line to the next task. The existing code handled this case for the scenario where there was no interfering third task (the second scenario in the original comment). However, the possibility that a third task could perform an uncontested acquire in the meantime was not accounted for.
Which means that the handling of the FUTEX_WAITER bit for robust non-PI futexes in the unlock path is inconsistent, which means the unconditional store 0 is the real problem.
We should rather fix that than hacking around it in the exit handling code.
Let me think about it some more.
Quoted 6 lines
Quoted 5 lines
Quoted 3 lines
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.
What's the actual problem with that?
Quoted 7 lines
I was planning to write it up with that patch series, but here's the abbreviated version: Embedded databases (e.g. LMBD) use shared-memory robust mutexes (glibc
pthread_mutexin the LMDB case) to coordinate access to the database file among users. However, if those users are in different pid namespaces, the mutex silently fails to provide mutual exclusion, causing corruption and hangs (bad for a database).
Unsurprisingly a robust futex depends on unique PIDs, which are not obviously not guaranteed accross multiple PID namespaces.
TBH, I'm not really keen to see the hacks required to make this "work" and thereby violating all isolation rules which come with namespaces.
Thanks,
tglx
Quoted 55 lines · Thomas Gleixner
Quoted 20 lines · Keno Fischer
Quoted 10 lines · Thomas Gleixner
Quoted 3 lines · Keno Fischer
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_WAITERSis *NOT* set.While your change "fixes" this particular problem, it leaves the related UAF problem unsolved.
The more complete solution is:
Quoted 8 lines
https://lore.kernel.org/all/[email protected]/which is upstream now. Specifically the combined unlock/wake part
https://lore.kernel.org/all/[email protected]/ensures that your scenario can't happen and provides at the same time one part of the solution for the UAF exit race.
Quoted 10 lines
Yes, I'm aware of that patch series.
However, this is not quite the same race.
As the updated comment indicates, the combined unlock/wake prevents one of the three race scenarios that causes problems.
However, if a *woken up* task dies before it can re-acquire the futex, the kernel must still pass the baton down the line to the next task. The existing code handled this case for the scenario where there was no interfering third task (the second scenario in the original comment). However, the possibility that a third task could perform an uncontested acquire in the meantime was not accounted for.Which means that the handling of the
FUTEX_WAITERbit for robust non-PI futexes in the unlock path is inconsistent, which means the unconditional store 0 is the real problem.We should rather fix that than hacking around it in the exit handling code.
Let me think about it some more.
Quoted 6 lines
Quoted 5 lines
Quoted 3 lines
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.
What's the actual problem with that?
Quoted 7 lines
I was planning to write it up with that patch series, but here's the abbreviated version: Embedded databases (e.g. LMBD) use shared-memory robust mutexes (glibc
pthread_mutexin the LMDB case) to coordinate access to the database file among users. However, if those users are in different pid namespaces, the mutex silently fails to provide mutual exclusion, causing corruption and hangs (bad for a database).
Quoted 2 lines
Unsurprisingly a robust futex depends on unique PIDs, which are not obviously not guaranteed accross multiple PID namespaces.
Fwiw, I added unique inode numbers for the lifetime of the system to pidfds some time ago. The inode number is allocated for every struct pid and available via pid->ino. A pidfd can be stat()ed to retrieve it. Just mentioning it in case this may be useful.
* Christian Brauner:
Quoted 4 lines
Fwiw, I added unique inode numbers for the lifetime of the system to pidfds some time ago. The inode number is allocated for every struct pid and available via
pid->ino. A pidfd can be stat()ed to retrieve it. Just mentioning it in case this may be useful.
Is there an efficient way to get this without allocating a file descriptor, and without /proc being mounted?
Thanks,
Florian
Quoted 9 lines · Florian Weimer
* Christian Brauner:
Quoted 4 lines
Fwiw, I added unique inode numbers for the lifetime of the system to pidfds some time ago. The inode number is allocated for every struct pid and available via
pid->ino. A pidfd can be stat()ed to retrieve it. Just mentioning it in case this may be useful.Is there an efficient way to get this without allocating a file descriptor, and without /proc being mounted?
No. You need to allocate a pidfd to get access to them. I have never considered upgrading them to a generic propery. They are tied to pidfds by design and to inodes. And I think introducing that number as an orthogonal concept would risk implicily upgrading it to the system call layer. Which seems less than ideal... Fwiw, pidfds also support file handles where the inode number is encoded into the handle.
Quoted 8 lines · Christian Brauner
Quoted 2 lines · Thomas Gleixner
Unsurprisingly a robust futex depends on unique PIDs, which are not obviously not guaranteed accross multiple PID namespaces.
Fwiw, I added unique inode numbers for the lifetime of the system to pidfds some time ago. The inode number is allocated for every struct pid and available via
pid->ino. A pidfd can be stat()ed to retrieve it. Just mentioning it in case this may be useful.
They have the correct property of being unique cookies but they don't (currently) fit in a 32-bit futex word. And if we ever get 64-bit futex words, I think userspace could just mint cookies themselves per-operation. That said, perhaps they could be useful for the PI case, although that's much trickier and I'm much less convinced that cross-pid-namespace PI futexes are useful or desirable. It is a bit awkward in that all threads do already have systemwide unique ids in the root pid namespace, but whether or not they can read them depends on whether they have access to a /proc that was mounted by the original pid namespace. That's why I was sort of hoping to get the kernel out of the business on interpreting the value of the futex cookie in the non-PI case and let userspace figure out where to get a unique id depending on the circumstances and isolation requirements.
Quoted 2 lines · Thomas Gleixner
We should rather fix that than hacking around it in the exit handling code.
Ok, I do think that would be better. If we changed the FUTEX_ROBUST_UNLOCK semantics to set FUTEX_WAITERS if and only if there are any remaining waiters (being careful to synchronize this with the addition of new waiters in FUTEX_WAIT),
then we don't need this code in the exit processing. It is also better because it avoids the extra wakeup just to re-set FUTEX_WAITERS and it solves the related (minor) annoyance that userspace currently cannot know whether there are remaining waiters and has to conservatively go through the contended unlock path after any wait. I've tried the quick-and-dirty candidate patch below and it fixes the issue. See if you like that approach better.
The main downside I think is that this would be a userspace-visible change to the futex ABI protocol. Of course, it is opt-in using FUTEX_ROBUST_UNLOCK, so there's no problem from the kernel perspective, but for cross-process mutexes userspace will have to coordinate to make sure that all processes in question (including statically linked ones, etc.) upgrade simultaneously. glibc could potentially use a free kind bit to coordinate and make an ABI mismatch loud,
but I don't see a good way for musl to do this.
That said, both libcs have made these kinds of breaking ABI changes before (although
rarely), so perhaps that's not a real concern.
Quoted 2 lines
Unsurprisingly a robust futex depends on unique PIDs, which are not obviously not guaranteed accross multiple PID namespaces.
Well, non-PI robust futexes depend on each thread in the synchronization domain having a unique token for their process lifetimes, but it doesn't necessarily have to be a PID - anything that can be robustly released would do (obviously the situation is different for PI futexes since the kernel needs to be able to find the owner). The proposal here would be to let userspace decide what that token is (either in the robust list head or in each entry). Some applications already have suitable tokens (e.g. LMDB assigns a reader index for each reader, although its protocol for doing so would need adjustment since it assumes mutexes work), but there are several options - I don't think the kernel has to care.
-- >8 --
Subject: [PATCH] futex: Retain FUTEX_WAITERS across a contended robust unlock
In the contended unlock path of a futex (using FUTEX_ROBUST_UNLOCK for the sake of the present discussion - the legacy path has additional races anyway), the kernel will store 0 to release the futex word, clean up the robust list pending entry and wake the appropriate number of waiting tasks (if any).
However, because userspace does not know if there were any remaining waiters on the futex, this opens up a race: After the futex word is released, an unrelated thread can perform an uncontended acquire without setting FUTEX_WAITERS. If the woken-up thread dies before it has a chance to set FUTEX_WAITERS, there is no indication to userspace that the next release needs the contended-unlock path and thus any remaining waiters will never be woken. An example sequence is the following:
A owns the futex, B and C sleep in FUTEX_WAIT
uval == A | FUTEX_WAITERS
A FUTEX_ROBUST_UNLOCK: store 0, 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
This closes that race by instead having the kernel retain the FUTEX_WAITERS bit to indicate whether any waiters remain. Another thread is only permitted to perform an uncontended lock if there are no remaining waiters. The release store is performed under the futex spinlock, and thus synchronizes with the check of the futex word in FUTEX_WAIT.
This is a change in the futex protocol. 0|FUTEX_WAITERS was previously not a state that was used in the futex state machine (although very old glibc versions have a bug that produces it). Userspace implementations will need to be adapted to handle this state when switching to FUTEX_ROBUST_UNLOCK.
--- Documentation/locking/robust-futex-ABI.rst | 17 ++- kernel/futex/futex.h | 12 ++ kernel/futex/waitwake.c | 123 ++++++++++++++------- 3 files changed, 113 insertions(+), 39 deletions(-)
(quoted diff) +0 -0
b/Documentation/locking/robust-futex-ABI.rst
index 5e6a0665b8ba..7e83b3d6f4f0 100644
Documentation/locking/robust-futex-ABI.rst +0 -0
@@ -215,8 +215,21 @@ For the contended unlock case, where other
threads are waiting for the lock
release, there's the ``FUTEX_ROBUST_UNLOCK`` operation feature flag for the ``futex()`` system call, which must be used with one of the following
operations: ``FUTEX_WAKE``, ``FUTEX_WAKE_BITSET`` or ``FUTEX_UNLOCK_PI``.
-The kernel will release the lock (set the futex word to zero), clean the -``list_op_pending`` field. Then, it will proceed with the normal wake path. +The kernel will release the lock, clean the ``list_op_pending`` field and +wake the requested number of waiters. The value stored into the futex word +by the release reflects the remaining contention: if waiters remain queued +in the kernel after the wakeup, the futex word is set to ``FUTEX_WAITERS``, +otherwise to zero. This keeps subsequent lock acquisitions on the contended +path so that every unlock wakes the next waiter, even if a woken waiter is +killed before it can take over the lock in user space (the released, +ownerless futex word also lets the robust list exit handling of such a +waiter wake its successor).
+
+Lock implementations using ``FUTEX_ROBUST_UNLOCK`` must therefore treat a +futex word whose TID portion is zero as free regardless of the +``FUTEX_WAITERS`` bit: it is acquired with an atomic compare-and-exchange +which preserves ``FUTEX_WAITERS``, and a thread must never wait on a futex +word with a zero TID portion.
For the non-contended path, there's still a race between checking the
futex word
and clearing the ``list_op_pending`` field. To solve this without the need of a
kernel/futex/futex.h +0 -0
@@ -305,6 +305,18 @@ static inline int futex_get_value_locked(u32
*dest, u32 __user *from)
return get_user_inline(*dest, from);
}
+/* Store to user memory with release ordering and pagefaults disabled */ +static inline int futex_put_value_locked(u32 val, u32 __user *to) +{
+ guard(pagefault)();
+
+ scoped_user_write_access(to, efault)
+ unsafe_atomic_store_release_user(val, to, efault);
+ return 0;
+efault:
+ return -EFAULT;
+}
+
extern void __futex_unqueue(struct futex_q *q);
extern void __futex_queue(struct futex_q *q, struct futex_hash_bucket *hb,
struct task_struct *task);
kernel/futex/waitwake.c +0 -0
@@ -150,26 +150,69 @@ void futex_wake_mark(struct wake_q_head *wake_q,
struct futex_q *q)
}
/*
- * If requested, clear the robust list pending op and unlock the futex
+ * Mark up to @nr_wake waiters for wake up. Must be called with @hb->lock held.
+ * Returns the number of marked waiters (or -EINVAL).
*/
-static bool futex_robust_unlock(u32 __user *uaddr, unsigned int flags, void __user *pop)
+static int futex_wake_locked(struct futex_hash_bucket *hb, union futex_key *key,
+ struct wake_q_head *wake_q, int nr_wake, u32 bitset)
{
- if (!(flags & FLAGS_ROBUST_UNLOCK))
- return true;
+ struct futex_q *this, *next;
+ int ret = 0;
- /* First unlock the futex, which requires release semantics. */
- scoped_user_write_access(uaddr, efault)
- unsafe_atomic_store_release_user(0, uaddr, efault);
+ plist_for_each_entry_safe(this, next, &hb->chain, list) {
+ if (futex_match(&this->key, key)) {
+ if (this->pi_state || this->rt_waiter)
+ return -EINVAL;
- /*
- * Clear the pending list op now. If that fails, then the task is in
- * deeper trouble as the robust list head is usually part of the TLS.
- * The chance of survival is close to zero.
- */
- return futex_robust_list_clear_pending(pop, flags);
+ /* Check if one of the bits is set in both bitsets */
+ if (!(this->bitset & bitset))
+ continue;
+
+ this->wake(wake_q, this);
+ if (++ret >= nr_wake)
+ break;
+ }
+ }
+ return ret;
+}
+
+/*
+ * Release the futex word of a robust futex (FUTEX_ROBUST_UNLOCK) by storing
+ * either 0 or (0)|FUTEX_WAITERS depending on the presence of remaining waiters.
+ * Must be called with @hb->lock held. The lock may be dropped and reacquired
+ * to fault in the futex word.
+ */
+static int futex_robust_release(struct futex_hash_bucket *hb, union futex_key *key,
+ u32 __user *uaddr)
+{
+ struct futex_q *this;
+ int ret;
+
+ for (;;) {
+ u32 mval = 0;
+
+ /*
+ * Check for remaining waiters on this futex. Error
+ * conditions from futex_wake_locked() are ignored here to
+ * ensure that the next wake takes the contended path and
+ * observes those errors.
+ */
+ plist_for_each_entry(this, &hb->chain, list) {
+ if (futex_match(&this->key, key)) {
+ mval = FUTEX_WAITERS;
+ break;
+ }
+ }
+
+ if (!futex_put_value_locked(mval, uaddr))
+ return 0;
-efault:
- return false;
+ spin_unlock(&hb->lock);
+ ret = fault_in_user_writeable(uaddr) ? -EFAULT : 0;
+ spin_lock(&hb->lock);
+ if (ret)
+ return ret;
+ }
}
/*
@@ -177,8 +220,9 @@ static bool futex_robust_unlock(u32 __user *uaddr, unsigned int flags, void __us
*/
int futex_wake(u32 __user *uaddr, unsigned int flags, void __user
*pop, int nr_wake, u32 bitset)
{
+ bool robust = flags & FLAGS_ROBUST_UNLOCK;
+ bool wake = !((flags & FLAGS_STRICT) && !nr_wake);
union futex_key key = FUTEX_KEY_INIT;
- struct futex_q *this, *next;
DEFINE_WAKE_Q(wake_q);
int ret;
@@ -189,39 +233,44 @@ int futex_wake(u32 __user *uaddr, unsigned int flags, void __user *pop, int nr_w
if (unlikely(ret != 0))
return ret;
- if (!futex_robust_unlock(uaddr, flags, pop))
- return -EFAULT;
-
- if ((flags & FLAGS_STRICT) && !nr_wake)
+ if (!robust && !wake)
return 0;
CLASS(hbr, hbr)(&key);
auto hb = hbr.hb;
- /* Make sure we really have tasks to wakeup */
- if (!futex_hb_waiters_pending(hb))
- return ret;
+ /*
+ * Make sure we really have tasks to wakeup. No fast path for @robust,
+ * the unlock needs to happen regardless.
+ */
+ if (!robust && !futex_hb_waiters_pending(hb))
+ return 0;
spin_lock(&hb->lock);
- plist_for_each_entry_safe(this, next, &hb->chain, list) {
- if (futex_match (&this->key, &key)) {
- if (this->pi_state || this->rt_waiter) {
- ret = -EINVAL;
- break;
- }
+ if (wake)
+ ret = futex_wake_locked(hb, &key, &wake_q, nr_wake, bitset);
- /* Check if one of the bits is set in both bitsets */
- if (!(this->bitset & bitset))
- continue;
-
- this->wake(&wake_q, this);
- if (++ret >= nr_wake)
- break;
- }
+ if (robust && futex_robust_release(hb, &key, uaddr)) {
+ spin_unlock(&hb->lock);
+ /*
+ * The futex word could not be released. Keep the pending list armed.
+ */
+ ret = -EFAULT;
+ goto out;
}
spin_unlock(&hb->lock);
+
+ /*
+ * With the futex word released, clear the pending list op now. If
+ * that fails, then the task is in deeper trouble as the robust list
+ * head is usually part of the TLS. The chance of survival is close
+ * to zero.
+ */
+ if (robust && !futex_robust_list_clear_pending(pop, flags))
+ ret = -EFAULT;
+out:
wake_up_q(&wake_q);
return ret;
}
Signature · 1 line
2.54.0
Thomas Gleixner
maintainerReview
Quoted 3 lines · Keno Fischer
(quoted diff) +2
-0+/* Store to user memory with release ordering and pagefaults disabled */ +static inline int futex_put_value_locked(u32 val, u32 __user *to)
'put' is a bad name as it does not express the release() semantics.
Review
Quoted 11 lines
(quoted diff) +11
-0+ /* + * Check for remaining waiters on this futex. Error + * conditions from futex_wake_locked() are ignored here to + * ensure that the next wake takes the contended path and + * observes those errors. + */ + plist_for_each_entry(this, &hb->chain, list) { + if (futex_match(&this->key, key)) { + mval = FUTEX_WAITERS; + break; + }
That can be done in the loop which collects waiters for wakeup.
Review
Quoted 13 lines
(quoted diff) +10
-2+ } + + if (!futex_put_value_locked(mval, uaddr)) + return 0; -efault: - return false; + spin_unlock(&hb->lock); + ret = fault_in_user_writeable(uaddr) ? -EFAULT : 0; + spin_lock(&hb->lock); + if (ret) + return ret; + }
You _cannot_ loop here without reevaluating the futex key if the futex is shared. The key stays only valid for private futexes.
Review
Quoted 11 lines
}
/*
(quoted diff) +0
-0@@ -177,8 +220,9 @@ static bool futex_robust_unlock(u32 __user *uaddr,unsigned int flags, void
__us
*/
int futex_wake(u32__user*uaddr, unsigned int flags, void__user
*pop, intnr_wake, u32 bitset)
{(quoted diff) +2
-0+ bool robust = flags & FLAGS_ROBUST_UNLOCK; + bool wake = !((flags & FLAGS_STRICT) && !nr_wake);
Clever, but I had to read this five times to convince myself that it and it's usage are correct. :(
Quoted 7 lines
(quoted diff) +0
-1union futex_key key = FUTEX_KEY_INIT; - struct futex_q *this, *next; DEFINE_WAKE_Q(wake_q); int ret;@@ -189,39 +233,44 @@ int futex_wake(u32 __user *uaddr, unsigned intflags, void
__user*pop, intnr_w
Review
Quoted 9 lines
(quoted diff) +1
-4if (unlikely(ret != 0)) return ret; - if (!futex_robust_unlock(uaddr, flags, pop)) - return -EFAULT; - - if ((flags & FLAGS_STRICT) && !nr_wake) + if (!robust && !wake) return 0;
To me a robust unlock operation with zero wakeups does not make any sense. The point of FLAGS_ROBUST_UNLOCK is that the user space (VDSO) transition from TID to 0 failed due to the waiter bit being set. That requires to go into the kernel to handle the unlock, pending op and wakeup sequence atomically, which is not possible in user space. So I'd rather return -EINVAL for that case.
Review
Quoted 9 lines
(quoted diff) +3
-3CLASS(hbr, hbr)(&key); auto hb = hbr.hb; - /* Make sure we really have tasks to wakeup */ - if (!futex_hb_waiters_pending(hb)) - return ret; + /* + * Make sure we really have tasks to wakeup. No fast path for @robust, + * the unlock needs to happen regardless.
That's a pretty meager comment. If you look carefully then you'll notice that the futex code has a comment to code ratio of 0.75. That's not because we love comments so much :)
Quoted 35 lines
(quoted diff) +14
-14+ */ + if (!robust && !futex_hb_waiters_pending(hb)) + return 0; spin_lock(&hb->lock); - plist_for_each_entry_safe(this, next, &hb->chain, list) { - if (futex_match (&this->key, &key)) { - if (this->pi_state || this->rt_waiter) { - ret = -EINVAL; - break; - } + if (wake) + ret = futex_wake_locked(hb, &key, &wake_q, nr_wake, bitset); - /* Check if one of the bits is set in both bitsets */ - if (!(this->bitset & bitset)) - continue; - - this->wake(&wake_q, this); - if (++ret >= nr_wake) - break; - } + if (robust && futex_robust_release(hb, &key, uaddr)) { + spin_unlock(&hb->lock); + /* + * The futex word could not be released. Keep the pending list armed. + */ + ret = -EFAULT; + goto out; } spin_unlock(&hb->lock); + + /*
Review
Quoted 10 lines
(quoted diff) +8
-0+ * With the futex word released, clear the pending list op now. If + * that fails, then the task is in deeper trouble as the robust list + * head is usually part of the TLS. The chance of survival is close + * to zero. + */ + if (robust && !futex_robust_list_clear_pending(pop, flags)) + ret = -EFAULT; +out: wake_up_q(&wake_q); return ret;
For my taste there are too many if (robust) conditionals in this code. I really prefer a clear separation of the regular wake() path and the robust_unlock() case.
Something like the compiled but completely untested below.
Thanks,
tglx
--- kernel/futex/futex.h | 4 kernel/futex/waitwake.c | 234 +++++++++++++++++++++++++++++++++++++----------- 2 files changed, 187 insertions(+), 51 deletions(-)
kernel/futex/futex.h +2 -2
@@ -347,7 +347,7 @@ static inline void futex_hb_waiters_inc(#ifdef CONFIG_SMP atomic_inc (&hb->waiters);/* -* Full barrier (A), see the ordering comment above. +* Full barrier (A), see the ordering comment in waitwake.c */ smp_mb__after_atomic ();#endif
@@ -368,7 +368,7 @@ static inline int futex_hb_waiters_pendi {#ifdef CONFIG_SMP /* -* Full barrier (B), see the ordering comment above. +* Full barrier (B), see the ordering comment in waitwake.c */ smp_mb ();return atomic_read (&hb->waiters);
kernel/futex/waitwake.c +185 -49
266 lines not on this page · raw message
Quoted 1 line · Thomas Gleixner
Something like the compiled but completely untested below.
Two issues noted below. With those fixed, passed my local test cases. However, I re-ran the full TLA+ analysis over this protocol and it doesn't fully resolve the lost-wakeup issue (both your and my revised patch). In particular, if we drop the hb lock for a pagefault,
the waiter(s) we collected could have died and run exit processing before we perform the store (so exit handling wouldn't have performed the extra wakeup). In that case, waiters behind are stranded. I think the simplest fix would be to separate the count and waiter collection and only ->wake the waiters *AFTER* the release store has run successfully.
kernel/futex/waitwake.c void futex_wake_mark(struct wake_q_head · line 168
Quoted 5 lines
kernel/futex/waitwake.c +5
-0+static int collect_waiters (struct futex_hash_bucket *hb,struct futex_wake_q_head *fwake_q, +union futex_key *key,unsigned int nr_wake,u32 bitset) +{ +struct futex_q *this, *next; +unsigned int matches =0 ;
matches cannot be local here - either needs to go into futex_wake_q_head or needs to set waiters_left in continue path an the robust nr_wake path.
kernel/futex/waitwake.c void futex_wake_mark(struct wake_q_head · line 348
Quoted 6 lines
kernel/futex/waitwake.c +6
-0+/* +* Wake up waiters matching bitset queued on this futex (uaddr). +*/ +int futex_wake (u32 __user *uaddr,unsigned int flags,void __user *pop,int nr_wake,u32 bitset) +{ +bool robust_unlock = !!(flags &FUTEX_ROBUST_UNLOCK );
FLAGS_ROBUST_UNLOCK
kernel/futex/waitwake.c void futex_wake_mark(struct wake_q_head · line 351
Quoted 2 lines
kernel/futex/waitwake.c +2
-0+if (!bitset || nr_wake <0 ) +return -EINVAL ;
Noting that this changes userspace ABI for nr_wake < 0 (e.g. for userspace accidentally passing UINT_MAX rather than INT_MAX), although the current behavior is of course surprising and in a quick audit, I didn't see any public userspace code that gets this wrong, so worth trying probably. It's certainly better behavior.
Thomas Gleixner
maintainerKeno!
Quoted 10 lines · Keno Fischer
Quoted 1 line · Thomas Gleixner
Something like the compiled but completely untested below.
Two issues noted below. With those fixed, passed my local test cases. However, I re-ran the full TLA+ analysis over this protocol and it doesn't fully resolve the lost-wakeup issue (both your and my revised patch). In particular, if we drop the hb lock for a pagefault,
the waiter(s) we collected could have died and run exit processing before we perform the store (so exit handling wouldn't have performed the extra wakeup). In that case, waiters behind are stranded.
The problem is independent of the pagefault and the hash bucket lock. At the point where the waiter is dequeued from the hash bucket it can vanish:
collect_waiters()
collect T2
q->lock_ptr = NULL kill(T2);
T2 runs
if (!q->lock_ptr)
return;
exit_to_user()
handle_signal()
do_exit()
handle_futex_death()
// observes lock = TID(T1)
lock = FUTEX_WAITERS;Quoted 3 lines
I think the simplest fix would be to separate the count and waiter collection and only ->wake the waiters *AFTER* the release store has run successfully.
I really wanted to avoid the double search, but yes ...
Quoted 9 lines
Review
Quoted 5 lines
(quoted diff) +5
-0+static int collect_waiters(struct futex_hash_bucket *hb, struct futex_wake_q_head *fwake_q, + union futex_key *key, unsigned int nr_wake, u32 bitset) +{ + struct futex_q *this, *next; + unsigned int matches = 0;
matchescannot be local here - either needs to go intofutex_wake_q_heador needs to setwaiters_leftincontinuepath an the robustnr_wakepath.
It can be set unconditionally here:
unsigned int matches = fwake_q->wakees;
But with the separate count/collect it does not matter anymore.
Quoted 8 lines
Review
Quoted 6 lines
(quoted diff) +6
-0+/* + * Wake up waiters matching bitset queued on this futex (uaddr). + */ +int futex_wake(u32 __user *uaddr, unsigned int flags, void __user *pop, int nr_wake, u32 bitset) +{ + bool robust_unlock = !!(flags & FUTEX_ROBUST_UNLOCK);
FLAGS_ROBUST_UNLOCK
Indeed.
Quoted 8 lines
Review
Quoted 2 lines
(quoted diff) +2
-0+ if (!bitset || nr_wake < 0) + return -EINVAL;Noting that this changes userspace ABI for
nr_wake < 0(e.g. for userspace accidentally passingUINT_MAXrather thanINT_MAX), although the current behavior is of course surprising and in a quick audit, I didn't see any public userspace code that gets this wrong, so worth trying probably. It's certainly better behavior.
I did'nt find any evidence either. It bugged me because it's ill defined.
Aside of that any value > INT_MAX will not result in the intended mass wake up in the current code. It will wake exactly one waiter due to the loop termination condition:
if (++waiters >= nr_wake)
break;So that'd be broken already and I rather be explicit about it than silently "handling" it. The other option to solve this is to make the @nr_wake argument of futex_wake() unsigned int. That would be consistent with the sys_futex() @val argument is u32, but the @nr_wake argument of sys_futex_wake() is int. Duh!
Reworked version below.
Thanks,
tglx
---
kernel/futex/futex.h +2 -2
@@ -347,7 +347,7 @@ static inline void futex_hb_waiters_inc(#ifdef CONFIG_SMP atomic_inc (&hb->waiters);/* -* Full barrier (A), see the ordering comment above. +* Full barrier (A), see the ordering comment in waitwake.c */ smp_mb__after_atomic ();#endif
@@ -368,7 +368,7 @@ static inline int futex_hb_waiters_pendi {#ifdef CONFIG_SMP /* -* Full barrier (B), see the ordering comment above. +* Full barrier (B), see the ordering comment in waitwake.c */ smp_mb ();return atomic_read (&hb->waiters);
kernel/futex/waitwake.c +222 -48
305 lines not on this page · raw message
Quoted 1 line · Thomas Gleixner
Reworked version below.
Patch looks good and passes all my local tests! Thanks!
Keno
Thomas Gleixner
maintainerQuoted 4 lines · Keno Fischer
Quoted 1 line · Thomas Gleixner
Reworked version below.
Patch looks good and passes all my local tests! Thanks!
Let me write a change log then ...
Thomas Gleixner
maintainerQuoted 8 lines · Thomas Gleixner
Quoted 4 lines · Keno Fischer
Quoted 1 line · Thomas Gleixner
Reworked version below.
Patch looks good and passes all my local tests! Thanks!
Let me write a change log then ...
While doing so I thought about your initial fix some more.
I still hate it because it papers over the underlying problem, but on the other hand it'll take quite some time until the robust unlock changes will be adopted by libraries and backport wise this is innocuous enough. So I'm going to apply it under protest :)
Rusty Russel said in 2002: "Futexes are really cursed." See kernel/futex/core.c::31
Maybe I should remove that comment to put that to an end :)
Thanks,
tglx
Thomas Gleixner
maintainerQuoted 8 lines · Thomas Gleixner
Quoted 4 lines · Keno Fischer
Quoted 1 line · Thomas Gleixner
Reworked version below.
Patch looks good and passes all my local tests! Thanks!
Let me write a change log then ...
And while I did so, I came up with a trivial optimization for the most common use case where @nr_wake = 1, which allows to skip the second list walk completely.
I'll post that final patch in a few, so please have an eye on that change.
Thanks,
tglx
Thomas Gleixner
maintainerPATCH 1/1 futex: Make FUTEX_WAITERS state consistent for robust futex unlock
Keno reported another subtle futex exit race, which is neither handled by commit 3ca9595d9fb6 ("futex: Add support for unlocking robust futexes") nor by the recent efforts around commit 3ca9595d9fb6 ("futex: Add support for unlocking robust futexes").
The problem requires four tasks:
T1 owns the futex, T2 and T3 sleep on the futex. The user space lock value is TID(T1) | FUTEX_WAITERS.
T1
Either:
lockval = 0; // Clears the FUTEX_WAITERS bit
sys_futex(WAKE)
wakeup(T2)
Or:
sys_futex(ROBUST_UNLOCK)
lockval = 0; // Clears the FUTEX_WAITERS bit
wakeup(T2)
Note that both have the same issue:
T4 pthread_mutex_lock()
cmpxchg(0 -> TID(T4)) succeeds
T2 exit_to_user()
handle_signal()
do_exit()
exit_robust_list()
observes lockval = TID(T4)
T4 pthread_mutex_unlock()
cmpxchg(TID(T4) -> 0) succeeds as the FUTEX_WAITERS bit is 0
That leaves T3 queued in the kernel. It only can get woken up by chance when the futex becomes contended again.
Keno worked around this by unconditionally waking up a potential waiter when exit_robust_list() observes that the user space lock value is owned by another thread, but the FUTEX_WAITERS bit is not set. That "works", but the whole mechanism is still inconsistent. Relying on a waiter eventually coming around to clean up the mess in the robust list exit path has to be considered the last resort.
Similar to PI futexes, robust futexes rely on consistent state, but robust futexes lack the waiter accounting through the shared PI state of PI futex waiters.
commit 3ca9595d9fb6 ("futex: Add support for unlocking robust futexes") added support for unlocking contended robust futexes completely in the kernel to "atomically" unlock the user space lock, clear the robust list pending operation pointer and wake up eventually queued waiters, but the unlock still unconditionally clears the FUTEX_WAITERS bit.
Amend that proceedure so it does the following steps:
1) Skip the lockless check whether the hash bucket has waiters at all.
This is required because using the quick check would still have the
same problem:
user_lock |= FUTEX_WAITERS;
if (!futex_hb_waiters_pending(hb))
robust_unlock(0) atomic_inc(hb::waiters);
lock(hb);
// Succeeds!
if (compare_user_lock())
queue();
user_lock = 0; // clears the FUTEX_WAITERS bit
Though as the preceeding user space TIF(owner) -> 0 transition failed
due to the FUTEX_WAITERS bit set it's likely that there is a waiter
pending. The case where the waiter set the FUTEX_WAITERS bit in user
space but did not make it into the waiters queue is unfortunate but
unavoidable.2) Lock the hash bucket
This ensures that any newly incoming waiters are serialized until the unlock operation has completed and observe the new state.
3) Count the to be woken up tasks and check whether there are remaining waiters.
4) Try to unlock the user space lock value either with 0 or FUTEX_WAITERS according to the result of #3
5) If #4 succeeded proceed to #6. If not try to resolve the page fault and if successful go back to #1 otherwise fail.
6) Collect the to be woken waiters
7) Unlock the hash bucket
8) Clear the robust list pending operation pointer in user space
9) Wake the collected waiters
While it preserves the FUTEX_WAITERS bit when there are still waiters queued after collecting the to be woken waiters, it still creates a window of harmless inconsistency versus a newly incoming waiter:
T1 T2
#2 lock(hb);
#3 remaining = evaluate_waiters(); if (!cmpxchg(0 -> TID))
#4 lockval = remaining ? FUTEX_WAITERS : 0; sys_futex(WAIT, lockval)
#6 collect_waiters(); lock(hb) ...
#7 unlock(hb);
if (lockval != uval)
return -EWOULDBLOCK;
lockval |= FUTEX_WAITERS;
sys_futex(WAIT, lockval)When T1 sets the lock value to 0 because it can't find remaining waiters, then T2 will observe under the hash bucket lock that the lock value has changed and goes back to try again. That's part of the futex protocol and both kernel and user space are prepared to handle it not only for this case.
As #3 and #6 seem to be redundant operations they are not because as explained above the elegible waiters cannot be collected into the wake queue before the to be set state of the FUTEX_WAITERS bit has been established.
Though this double list walk is avoided for the most common use case, which just wakes exactly one waiter. That just requires to cache the pointer to that wake up elegible waiter in #3, i.e. evaluate_waiters(), skipping the second list walk in #6, i.e. collect_waiters() and collecting that cached waiter directly. That's safe because the hash bucket lock is held across the whole set of operations, i.e.the list is immutable.
--- kernel/futex/futex.h | 4 kernel/futex/waitwake.c | 288 ++++++++++++++++++++++++++++++++++++++++-------- 2 files changed, 242 insertions(+), 50 deletions(-)
kernel/futex/futex.h +2 -2
@@ -347,7 +347,7 @@ static inline void futex_hb_waiters_inc(#ifdef CONFIG_SMP atomic_inc (&hb->waiters);/* -* Full barrier (A), see the ordering comment above. +* Full barrier (A), see the ordering comment in waitwake.c */ smp_mb__after_atomic ();#endif
@@ -368,7 +368,7 @@ static inline int futex_hb_waiters_pendi {#ifdef CONFIG_SMP /* -* Full barrier (B), see the ordering comment above. +* Full barrier (B), see the ordering comment in waitwake.c */ smp_mb ();return atomic_read (&hb->waiters);
kernel/futex/waitwake.c +240 -48
323 lines not on this page · raw message
Re: [PATCH] futex: Make FUTEX_WAITERS state consistent for robust futex unlock
Thanks for the detailed changelog - I think it lays everything out very nicely. The optimization added in this revision isn't quite sound as written, but should be easy to fix - see below. Just a few minor nits on the changelog language otherwise.
Quoted 4 lines · Thomas Gleixner
Keno reported another subtle futex exit race, which is neither handled by commit
3ca9595d9fb6("futex: Add support for unlocking robust futexes") nor by the recent efforts around commit3ca9595d9fb6("futex: Add support for unlocking robust futexes").
Duplicate shas - ca16d5bee598 ("futex: Prevent robust futex exit race") for the first one?
Quoted 1 line
Amend that proceedure so it does the following steps:
typo
Quoted 2 lines
4) Try to unlock the user space lock value either with 0 or
FUTEX_WAITERSaccording to the result of #3
I think it would be good to note here (or in robust-futex-ABI.rst) that this is a change to the non-PI futex protocol ABI so that userspace can appropriately coordinate the ABI versioning when adopting FUTEX_ROBUST_UNLOCK.
Quoted 4 lines
As #3 and #6 seem to be redundant operations they are not because as explained above the elegible waiters cannot be collected into the wake queue before the to be set state of the
FUTEX_WAITERSbit has been established.
typo 'elegible' -> 'eligible'; same in the paragraph below this
kernel/futex/waitwake.c void futex_wake_mark(struct wake_q_head · line 173
Quoted 9 lines
kernel/futex/waitwake.c +9
-0+/* +* Waiters are counted independent of the bitset match. Stop the +* list walk when the total number of waiters becomes larger +* than the number of to be woken up tasks. In that case it does +* not matter how many wakees have been found. There will be +* waiters queued after the wake up no matter what. +*/ +if (++waiters > nr_wake) +return 1 ;
On bitset mismatch, this will early-out before caching the wakee below, losing the wake.
kernel/futex/waitwake.c void futex_wake_mark(struct wake_q_head · line 325
Quoted 6 lines
kernel/futex/waitwake.c +6
-0+/* +* This should never happen because evaluate_waiters() would +* have detected a PI futex mixup already. +*/ +if (WARN_ON_ONCE (nr_woken <0 )) +return nr_woken;
I missed this before, but the same issue makes this WARN reachable. If there's a bunch of bitset-mismatched waiters at the start of the queue, then the check will early out and the PI mixup will not be discovered until the second walk.
Thanks for pushing this through!
Keno
Thomas Gleixner
maintainerRe: [PATCH] futex: Make FUTEX_WAITERS state consistent for robust futex unlock
Quoted 5 lines · Keno Fischer
Thanks for the detailed changelog - I think it lays everything out very nicely. The optimization added in this revision isn't quite sound as written, but should be easy to fix - see below. Just a few minor nits on the changelog language otherwise.
Quoted 8 lines
Quoted 4 lines · Thomas Gleixner
Keno reported another subtle futex exit race, which is neither handled by commit
3ca9595d9fb6("futex: Add support for unlocking robust futexes") nor by the recent efforts around commit3ca9595d9fb6("futex: Add support for unlocking robust futexes").Duplicate shas -
ca16d5bee598("futex: Prevent robust futex exit race") for the first one?
Wanted to referrence ca16d5bee598 ("futex: Prevent robust futex exit race") obviously.
Quoted 11 lines
Quoted 1 line
Amend that proceedure so it does the following steps:
typo
Quoted 2 lines
4) Try to unlock the user space lock value either with 0 or
FUTEX_WAITERSaccording to the result of #3I think it would be good to note here (or in
robust-futex-ABI.rst) that this is a change to the non-PI futex protocol ABI so that userspace can appropriately coordinate the ABI versioning when adoptingFUTEX_ROBUST_UNLOCK.
Makes sense
Quoted 17 lines
Quoted 4 lines
As #3 and #6 seem to be redundant operations they are not because as explained above the elegible waiters cannot be collected into the wake queue before the to be set state of the
FUTEX_WAITERSbit has been established.typo 'elegible' -> 'eligible'; same in the paragraph below this
kernel/futex/waitwake.c void futex_wake_mark(struct wake_q_head · line 173
Quoted 9 lines
kernel/futex/waitwake.c +9
-0+/* +* Waiters are counted independent of the bitset match. Stop the +* list walk when the total number of waiters becomes larger +* than the number of to be woken up tasks. In that case it does +* not matter how many wakees have been found. There will be +* waiters queued after the wake up no matter what. +*/ +if (++waiters > nr_wake) +return 1 ;
Quoted 2 lines
On bitset mismatch, this will early-out before caching the wakee below, losing the wake.
Duh. Heat induced brain fart.
Quoted 10 lines
kernel/futex/waitwake.c void futex_wake_mark(struct wake_q_head · line 325
Quoted 6 lines
kernel/futex/waitwake.c +6
-0+/* +* This should never happen because evaluate_waiters() would +* have detected a PI futex mixup already. +*/ +if (WARN_ON_ONCE (nr_woken <0 )) +return nr_woken;I missed this before, but the same issue makes this WARN reachable. If there's a bunch of bitset-mismatched waiters at the start of the queue, then the check will early out and the PI mixup will not be discovered until the second walk.
Yes, but that has been the case forever and it's done opportunisticly to avoid full hash bucket walks wherever possible.
Thanks,
tglx
Thomas Gleixner
maintainerRe: [PATCH] futex: Make FUTEX_WAITERS state consistent for robust futex unlock
Quoted 8 lines · Thomas Gleixner
Quoted 7 lines · Keno Fischer
Quoted 6 lines
kernel/futex/waitwake.c +6
-0+/* +* This should never happen because evaluate_waiters() would +* have detected a PI futex mixup already. +*/ +if (WARN_ON_ONCE (nr_woken <0 )) +return nr_woken;
Quoted 6 lines
Quoted 3 lines
I missed this before, but the same issue makes this WARN reachable. If there's a bunch of bitset-mismatched waiters at the start of the queue, then the check will early out and the PI mixup will not be discovered until the second walk.
Yes, but that has been the case forever and it's done opportunisticly to avoid full hash bucket walks wherever possible.
Duh. I misread what you said, but yes with the changes I did now it should all be fine.
I'll post the lot later.
Re: [PATCH] futex: Make FUTEX_WAITERS state consistent for robust futex unlock
Quoted 1 line · Thomas Gleixner
I'll post the lot later.
Was there an updated version of this patch?
If we still want to do this, I think it would be good to get it in sooner rather than later so userspace can adopt the new ABI alongside the new robust unlock path. My apologies if there is a v2 and I missed it.
Thomas Gleixner
maintainerOn Mon, Jul 20 2026 at 23:26, Keno Fischer wrote:
...
patching file kernel/futex/core.c
patch: **** malformed patch at line 69: struct task_struct *curr,
kernel/futex/core.c static int handle_futex_death(u32 __user *uaddr, · line 982
Quoted 4 lines
kernel/futex/core.c +0
-0@@ -982,8 +982,11 @@ static int handle_futex_death(u32 __user *uaddr, struct task_struct *curr,
Here and ...
kernel/futex/core.c static int handle_futex_death(u32 __user *uaddr, · line 995
Quoted 2 lines
kernel/futex/core.c +0
-0@@ -992,42 +995,70 @@ static int handle_futex_death(u32 __user *uaddr, struct task_struct *curr,
.. here and some other instance.
Seems your mail client mangled the patch. See:
Documentation/process/email-clients.rst
The only known way to send patches with the gmail web client is as attachment, but that's a pain for reviewing, replying and applying.
But you can use git send-email with gmail smtp and that will do the right thing.
Thanks,
tglx
Quoted 1 line · Thomas Gleixner
Seems your mail client mangled the patch. See:
Yeah, sorry about that, I've fixed that since. Gmail is a huge pain here.
Thomas Gleixner
maintainerQuoted 4 lines · Keno Fischer
Quoted 1 line · Thomas Gleixner
Seems your mail client mangled the patch. See:
Yeah, sorry about that, I've fixed that since. Gmail is a huge pain here.
Can you please resend then?
Quoted 9 lines · Thomas Gleixner
Quoted 4 lines · Keno Fischer
Quoted 1 line · Thomas Gleixner
Seems your mail client mangled the patch. See:
Yeah, sorry about that, I've fixed that since. Gmail is a huge pain here.
Can you please resend then?
Of course - resent below. Sorry again for the hassle.
-- >8 --
Date: Tue, 21 Jul 2026 00:31:48 +0000
Subject: [PATCH] futex: Prevent robust futex exit race more
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.
--- kernel/futex/core.c | 85 +++++++++++++++++++++++++++++++-------------- 1 file changed, 58 insertions(+), 27 deletions(-)
kernel/futex/core.c +0 -0
@@ -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
Signature · 1 line
2.54.0
Thomas Gleixner
maintainerQuoted 11 lines · Keno Fischer
Quoted 9 lines · Thomas Gleixner
Quoted 4 lines · Keno Fischer
Quoted 1 line · Thomas Gleixner
Seems your mail client mangled the patch. See:
Yeah, sorry about that, I've fixed that since. Gmail is a huge pain here.
Can you please resend then?
Of course - resent below. Sorry again for the hassle.
It's slightly less mangled than the original one, which replaced tabs with spaces in some places, but still fails to apply out of the box.
kernel/futex/core.c static int handle_futex_death(u32 __user *uaddr, · line 982
Quoted 4 lines
kernel/futex/core.c +0
-0@@ -982,8 +982,11 @@ static int handle_futex_death(u32 __user *uaddr, struct task_struct *curr,
Forced line break. Still causes:
Applying: futex: Prevent robust futex exit race more
error: corrupt patch at line 10
Quoted 14 lines
kernel/futex/core.c +5
-2return -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 kernel/futex/core.c +0
-0* before it can execute the futex() syscall to wake up
kernel/futex/core.c static int handle_futex_death(u32 __user *uaddr, · line 995
Quoted 1 line
kernel/futex/core.c +0
-0@@ -992,42 +995,70 @@ static int handle_futex_death(u32 __user *uaddr, struct task_struct *curr,
Ditto
kernel/futex/core.c static int handle_futex_death(u32 __user *uaddr, · line 1001
Quoted 6 lines
kernel/futex/core.c +0
-0* 2. A woken up waiter is killed before it can acquire the * futex in user space. * */ owner = uval &FUTEX_TID_MASK ;
This empty line got the leading space, which is prepended by diff, stripped off. Some tools tolerate that, some not.
kernel/futex/core.c static int handle_futex_death(u32 __user *uaddr, · line 1009
Quoted 11 lines
kernel/futex/core.c +5
-3-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 ; }
Same here.
kernel/futex/core.c static int handle_futex_death(u32 __user *uaddr, · line 1012
Quoted 6 lines
kernel/futex/core.c +0
-3-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
Please send the patch to yourself, save the mail and try to apply it with git am.
Quoted 2 lines · Thomas Gleixner
It's slightly less mangled than the original one, which replaced tabs with spaces in some places, but still fails to apply out of the box.
[...]
Quoted 2 lines
Please send the patch to yourself, save the mail and try to apply it with git am.
Welp, I learned yet more about all the different ways in which our email system likes to mangle things. I hope third time is the charm. I've sent it to my self and git am --scissors is clean on the downloaded email. If anything is still off, please let me know.
-- >8 --
Date: Tue, 21 Jul 2026 00:31:48 +0000
Subject: [PATCH] futex: Prevent robust futex exit race more
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.
--- kernel/futex/core.c | 85 +++++++++++++++++++++++++++++++-------------- 1 file changed, 58 insertions(+), 27 deletions(-)
kernel/futex/core.c +58 -27
@@ -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
Signature · 1 line
2.54.0
The following commit has been merged into the locking/futex branch of tip:
The following commit has been merged into the locking/futex branch of tip:
Commit-ID: 474a57058e84c05665c3ffbe7953fab56c032f0d Gitweb: https://git.kernel.org/tip/474a57058e84c05665c3ffbe7953fab56c032f0d Author: Keno Fischer <[email protected]> AuthorDate: Tue, 21 Jul 2026 00:31:48 Committer: Thomas Gleixner <[email protected]> CommitterDate: Thu, 30 Jul 2026 22:34:18 +02:00
futex: Prevent robust futex exit race more
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
This is clearly a short coming in the implementation, which fails to keep the FUTEX_WAITERS bit consistent.
Work around 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.
This does not fix the problem of a non-contended take over/release and free sequence, which has been discussed for years and has been addressed by commit 3ca9595d9fb6 ("futex: Add support for unlocking robust futexes") and subsequent changes, but failed to take the problem described above into account.
A more complete solution which is based on the in kernel unlock of contended robust futexes has been discussed in the context of this change and should show up in mainline sooner than later.
[ tglx: Amend change log slightly and fixup coding style ]
--- kernel/futex/core.c | 85 ++++++++++++++++++++++++++++++-------------- 1 file changed, 58 insertions(+), 27 deletions(-)
kernel/futex/core.c +58 -27
@@ -982,8 +982,11 @@ retry: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 @@ retry:* 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
[tip: locking/urgent] futex: Prevent robust futex exit race some more
In reply to Keno FischerThe following commit has been merged into the locking/urgent branch of tip:
The following commit has been merged into the locking/urgent branch of tip:
Commit-ID: 6d4514ca9cdf61fec4ec634cf50386f6f7e69748 Gitweb: https://git.kernel.org/tip/6d4514ca9cdf61fec4ec634cf50386f6f7e69748 Author: Keno Fischer <[email protected]> AuthorDate: Tue, 21 Jul 2026 00:31:48 Committer: Ingo Molnar <[email protected]> CommitterDate: Sun, 02 Aug 2026 09:57:35 +02:00
futex: Prevent robust futex exit race some more
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
This is clearly a shortcoming in the implementation, which fails to keep the FUTEX_WAITERS bit consistent.
Work around 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.
This does not fix the problem of a non-contended take over/release and free sequence, which has been discussed for years and has been addressed by commit 3ca9595d9fb6 ("futex: Add support for unlocking robust futexes") and subsequent changes, but failed to take the problem described above into account.
A more complete solution which is based on the in kernel unlock of contended robust futexes has been discussed in the context of this change and should show up in mainline sooner than later.
[ tglx: Amend change log slightly and fixup coding style ]
--- kernel/futex/core.c | 85 ++++++++++++++++++++++++++++++-------------- 1 file changed, 58 insertions(+), 27 deletions(-)
kernel/futex/core.c +58 -27
@@ -982,8 +982,11 @@ retry: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 @@ retry:* 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