futex: Avoid hash-bucket locking for mismatched waits
Subsystems (3)
PATCH 1/1 futex: Avoid hash-bucket locking for mismatched waits
futex_wait_setup() increments the bucket waiter count in futex_q_lock() and takes hb->lock before checking whether the futex word matches the expected value. A mismatch then immediately undoes the waiter accounting and drops the lock again without queueing anything.
In a fleet-wide sampled profile at Meta, among samples whose leaf was native_queued_spin_lock_slowpath(), the top call paths were:
shrink_inactive_list() (lru_lock) 25.0%
futex_wait_setup() (hb->lock) 21.6%
futex_wake() (hb->lock) 19.5%
raw_spin_rq_lock() (rq lock) 6.1% __remove_mapping() 3.3%
lock_list_lru_of_memcg() 3.1%
Together, the two futex paths represented 41.1% of sampled qspinlock slowpath events in this profile.
Read the futex word once before taking hb->lock. That read sits outside the waiters/value ordering documented at the top of waitwake.c and may be stale, so it may only be used to refuse to block: a mismatch is a valid outcome for the wait as a whole and is returned as -EWOULDBLOCK without locating the hash bucket. A match proves nothing and is discarded; the decision to queue is still taken by the existing test under hb->lock. This reaches the futex_wake() side too, as dropping the transient futex_hb_waiters_inc()/dec() pair lets a concurrent waker find the bucket empty in futex_hb_waiters_pending() and skip hb->lock as well.
get_futex_key() runs get_user_pages_fast() only for shared futexes, so their page has just been faulted in and the non-faulting futex_get_value_locked() normally succeeds. The reference is dropped again before get_futex_key() returns, so the page can go away; the locked path below recovers when it does. A private futex may still be nonresident, so read it faultably with get_user_inline().
The precheck stays after get_futex_key() so that its address validation, alignment and access_ok() included, keeps taking precedence over -EWOULDBLOCK. All three callers, __futex_wait(), futex_wait_requeue_pi() and io_futex_wait(), already treat a nonzero return as failure with hb->lock not held. futex_wait_multiple_setup() keeps the old sequence:FUTEX_WAITV has to set TASK_INTERRUPTIBLE before queueing the first futex of the vector.
perf bench futex hash only ever mismatches, as its futex words are calloc()ed to zero while every operation waits for 1234. On a 16-vCPU, 8-GiB guest, median of five 'perf bench futex hash -r 5 $args' runs of the reported mean per-thread throughput, in operations per second:
$args benchmark parent patched change
-b 2 private, two buckets 303,410 4,392,639 14.5x
-b 0 private, global hash 2,776,498 4,397,887 +58.4%
-b 0 -S shared 1,990,412 2,727,487 +37.0%This benchmark no longer measures futex hash bucket contention, because its words never match and every operation now returns before the bucket is
located: neither futex_hash() nor hb->lock is reached, and the -b knob stops affecting the result (both patched rows are ~4.4M).
The futex functional selftests pass with PROVE_LOCKING, DEBUG_ATOMIC_SLEEP and FAIL_FUTEX enabled.
--- kernel/futex/waitwake.c | 30 +++++++++++++++---- .../selftests/futex/functional/futex_numa.c | 6 ++-- 2 files changed, 28 insertions(+), 8 deletions(-)
kernel/futex/waitwake.c +25 -5
@@ -627,17 +627,18 @@ int futex_wait_setup(u32 __user *uaddr, u32 val, unsigned int flags,int ret;/* -* Access the page AFTER the hash-bucket is locked. -* Order is important: +* Perform the authoritative value check AFTER the hash-bucket is +* locked. Order is important: * * Userspace waiter: val = var; if (cond(val)) futex_wait(&var, val); * Userspace waker: if (cond(var)) { var = new; futex_wake(&var); } * * The basic logical guarantee of a futex is that it blocks ONLY * if cond(var) is known to be true at the time of blocking, for -* any cond. If we locked the hash-bucket after testing *uaddr, that -* would open a race condition where we could block indefinitely with -* cond(var) false, which would violate the guarantee. +* any cond. If the decision to block came from a test of *uaddr taken +* before the hash-bucket is locked, that would open a race where we +* could block indefinitely with cond(var) false, violating the +* guarantee. The unlocked test below may only refuse to block. * * On the other hand, we insert q and release the hash-bucket only * after testing *uaddr. This guarantees that futex_wait() will NOT
@@ -649,6 +650,25 @@ int futex_wait_setup(u32 __user *uaddr, u32 val, unsigned int flags,if (unlikely (ret !=0 ))return ret; +/* +* A mismatch here refuses the wait without locating the hash bucket; +* a match is rechecked under the lock below before queueing. +* +* get_futex_key() runs get_user_pages_fast() only for shared futexes, +* so their page is resident and the non-faulting read suffices, with +* the locked path recovering if it does not. A private futex may +* still be nonresident, so read it faultably here. Note that +* futex_get_value_locked() only disables faults, it does not need +* hb->lock. +*/ +if (flags &FLAGS_SHARED ) + ret =futex_get_value_locked (&uval, uaddr); +else + ret =get_user_inline (uval, uaddr); + +if (!ret && uval != val) +return -EWOULDBLOCK ; + retry_private:if (1 ) {CLASS (hbr, hbr)(&q->key);
tools/testing/selftests/futex/functional/futex_numa.c +3 -3
@@ -144,9 +144,9 @@ static void *contendfn(void *_arg)while (!*args->done) {/* -* futex2_wait() will take hb-lock, verify *var == val and -* queue/abort. By knowingly setting val 'wrong' this will -* abort and thereby generate hb-lock contention. +* By knowingly setting val 'wrong' this wait is always +* refused. futex2_wait() now detects that before taking +* hb-lock, so this no longer generates hb-lock contention. */ futex2_wait (&args->lock->val, ~0U , fflags,NULL ,0 ); args->val++;
Signature · 1 line
2.53.0-Meta
Quoted 12 lines · Usama Arif
futex_wait_setup()increments the bucket waiter count infutex_q_lock()and takeshb->lockbefore checking whether the futex word matches the expected value. A mismatch then immediately undoes the waiter accounting and drops the lock again without queueing anything.In a fleet-wide sampled profile at Meta, among samples whose leaf was
native_queued_spin_lock_slowpath(), the top call paths were:shrink_inactive_list() (lru_lock) 25.0% futex_wait_setup() (hb->lock) 21.6% futex_wake() (hb->lock) 19.5% raw_spin_rq_lock() (rq lock) 6.1%
Quoted 5 lines
__remove_mapping()3.3%
lock_list_lru_of_memcg()3.1%Together, the two futex paths represented 41.1% of sampled qspinlock slowpath events in this profile.
I couldn't work out from the changelog how much of that hb->lock contention is actually the uval/val mismatch. A contended userspace mutex would produce the same profile, and the two want different fixes, so I had a look on a couple of Meta workloads.
-EWOULDBLOCK reaches futex_wait() only from futex_wait_setup()'s value check, so the return value is the outcome:
timeout 10s bpftrace -e 'fexit:futex_wait { @[retval] = count(); }'On a workload available to me:
@[-516]: 29
@[-512]: 48
@[-11]: 7039 1.9% -EWOULDBLOCK
@[-110]: 35296 9.5% -ETIMEDOUT
@[0]: 328583 88.6% wokenSo 1.9% of calls take the path this patch optimises. Another host running a different application gives 6.2%, so it varies, but not by anything like the margin perf bench futex hash suggests.
The other 98% might be worth a number too. We expect __futex_wait() to end up waiting, and for that common case uaddr is now read twice: once in the precheck and once under hb->lock. Probably fine, but do you have a measurement for it?
Quoted 10 lines
perf bench futex hash only ever mismatches, as its futex words are calloc()ed to zero while every operation waits for 1234. On a 16-vCPU, 8-GiB guest, median of five 'perf bench futex hash -r 5 $args' runs of the reported mean per-thread throughput, in operations per second:
$args benchmark parent patched change -b 2 private, two buckets 303,410 4,392,639 14.5x -b 0 private, global hash 2,776,498 4,397,887 +58.4% -b 0 -S shared 1,990,412 2,727,487 +37.0%
Quoted 5 lines
This benchmark no longer measures futex hash bucket contention, because its words never match and every operation now returns before the bucket is
located: neitherfutex_hash()norhb->lockis reached, and the -b knob stops affecting the result (both patched rows are ~4.4M).
After this patch perf bench futex hash no longer really measures what it was written for, since the bucket is never located. It is probably not the best benchmark for this change either, as it only ever exercises the path being skipped. Might be worth a look as part of the series?
None of this is an objection to the approach, just that we likely need more data than a benchmark which is not exactly measuring what we care about.
Quoted 37 lines · On Tue, 4 Aug 2026 17:07:59 +0000 Dmitry Ilvokhin <[email protected]> wrote:
Quoted 12 lines · Usama Arif
futex_wait_setup()increments the bucket waiter count infutex_q_lock()and takeshb->lockbefore checking whether the futex word matches the expected value. A mismatch then immediately undoes the waiter accounting and drops the lock again without queueing anything.In a fleet-wide sampled profile at Meta, among samples whose leaf was
native_queued_spin_lock_slowpath(), the top call paths were:shrink_inactive_list() (lru_lock) 25.0% futex_wait_setup() (hb->lock) 21.6% futex_wake() (hb->lock) 19.5% raw_spin_rq_lock() (rq lock) 6.1%Quoted 5 lines
__remove_mapping()3.3%
lock_list_lru_of_memcg()3.1%Together, the two futex paths represented 41.1% of sampled qspinlock slowpath events in this profile.
I couldn't work out from the changelog how much of that
hb->lockcontention is actually the uval/val mismatch. A contended userspace mutex would produce the same profile, and the two want different fixes, so I had a look on a couple of Meta workloads.
-EWOULDBLOCKreachesfutex_wait()only from futex_wait_setup()'s value check, so the return value is the outcome:timeout 10s bpftrace -e 'fexit:futex_wait { @[retval] = count(); }'On a workload available to me:
@[-516]: 29 @[-512]: 48 @[-11]: 7039 1.9% -EWOULDBLOCK @[-110]: 35296 9.5% -ETIMEDOUT @[0]: 328583 88.6% woken
Quoted 3 lines
So 1.9% of calls take the path this patch optimises. Another host running a different application gives 6.2%, so it varies, but not by anything like the margin perf bench futex hash suggests.
The number of calls is not the right thing to measure here. Whats important is time spent in futex_q_lock().
I ran the script at the end the reply on one of the largest workloads in our fleet, running on hundreds of thousands of servers.
@calls[mismatch]: 83033
@calls[match]: 1214134
@lock_ns[mismatch]: 155373529
@lock_ns[match]: 539660978
@lock_us[mismatch]:
[0] 61175 |@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@| [1] 6250 |@@@@@ | [2, 4) 5253 |@@@@ | [4, 8) 4755 |@@@@ | [8, 16) 4048 |@@@ | [16, 32) 1429 |@ | [32, 64) 123 | |
@lock_us[match]:
[0] 1186732 |@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@| [1] 19845 | | [2, 4) 3860 | | [4, 8) 2110 | | [8, 16) 1197 | | [16, 32) 273 | | [32, 64) 116 | | [64, 128) 1 | |
As you can see, eventhough its 6.4% of the calls, 22.4% of the lock time:
1871ns per mismatching wait against 444ns per matching one.
Counting waits that spent over a microsecond in futex_q_lock():
mismatch 21,858 / 83,033 26.3%
match 27,402 / 1,214,134 2.3%A mismatching wait is about twelve times more likely to land on a contended lock.
A second-order effect pushes the same way. On a mismatch the patch also skips futex_hb_waiters_inc()/dec(), so the concurrent waker's futex_hb_waiters_pending() can find the bucket empty and skip hb->lock altogether.
Quoted 6 lines
The other 98% might be worth a number too. We expect
__futex_wait()to end up waiting, and for that common case uaddr is now read twice: once in the precheck and once underhb->lock. Probably fine, but do you have a measurement for it?
I measured the matching path separately because perf bench futex hash only exercises mismatches. I used a prefaulted private futex that is never changed and a 100-us timeout, so every call matches, queues under hb->lock, exercises the blocking timeout path, and returns ETIMEDOUT.
Over 5 boots, the median wall time was 167.092us on the parent and 166.984us patched (-0.06%). There is no latency regression because of an extra read.
Quoted 16 lines
Quoted 10 lines
perf bench futex hash only ever mismatches, as its futex words are calloc()ed to zero while every operation waits for 1234. On a 16-vCPU, 8-GiB guest, median of five 'perf bench futex hash -r 5 $args' runs of the reported mean per-thread throughput, in operations per second:
$args benchmark parent patched change -b 2 private, two buckets 303,410 4,392,639 14.5x -b 0 private, global hash 2,776,498 4,397,887 +58.4% -b 0 -S shared 1,990,412 2,727,487 +37.0%Quoted 5 lines
This benchmark no longer measures futex hash bucket contention, because its words never match and every operation now returns before the bucket is
located: neitherfutex_hash()norhb->lockis reached, and the -b knob stops affecting the result (both patched rows are ~4.4M).
Quoted 4 lines
After this patch perf bench futex hash no longer really measures what it was written for, since the bucket is never located. It is probably not the best benchmark for this change either, as it only ever exercises the path being skipped. Might be worth a look as part of the series?
Yes, this is what I meant when I wrote above that
"This benchmark no longer measures futex hash bucket contention".
I would be happy to rewrite perf bench futex to something more meaningful, I wanted to first get reviews on the kernel change itself.
Quoted 5 lines
None of this is an objection to the approach, just that we likely need more data than a benchmark which is not exactly measuring what we care about.
Thanks for taking a look!
The above data shows the significance of the patch.
It provides a very meaningful improvement (22.4% of time spent in futex_q_lock() will be significantly optimized and will also deliver second-order effects) and has no measurable impact on latency in the matching path.
IMHO, this patch is a free lunch.
futex-mismatch-cost.bt
---------------------
config = {
max_map_keys = 65536;
}fentry:futex_wait
{
@in[tid] = 1;
$a = delete(@acc, tid);
}fentry:futex_q_lock
/@in[tid]/
{
@qs[tid] = (int64)nsecs;
}/* __futex_wait() retries, so accumulate rather than overwrite. */ fexit:futex_q_lock
/@qs[tid]/
{
@acc[tid] += (int64)nsecs - @qs[tid];
$b = delete(@qs, tid);
}fexit:futex_wait
/@in[tid]/
{
$outcome = retval == -11 ? "mismatch" : "match";
$ns = (uint64)@acc[tid];
@calls[$outcome] = count();
@lock_ns[$outcome] = sum($ns);
@lock_us[$outcome] = hist($ns / 1000);
$c = delete(@in, tid);
$d = delete(@acc, tid);
}interval:s:30 { exit(); }
END
{
clear(@in);
clear(@qs);
clear(@acc);
}futex_wait_timeout.c
-------------------
#include <errno.h>
#include <inttypes.h>
#include <linux/futex.h>
#include <stdatomic.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <sys/resource.h>
#include <sys/syscall.h>
#include <time.h>
#include <unistd.h>
static _Atomic uint32_t futex_word __attribute__((aligned(64)));
static uint64_t now_ns(void)
{
struct timespec now;
if (clock_gettime(CLOCK_MONOTONIC_RAW, &now)) {
perror("clock_gettime");
exit(1);
}
return (uint64_t)now.tv_sec * 1000000000ULL + now.tv_nsec;
}int main(int argc, char **argv)
{
uint64_t iterations = 20000;
uint64_t timeout_ns = 100000;
uint64_t start, elapsed;
struct timespec timeout;
struct rusage before, after;
uint64_t i;
/* Prefault the resident private word before measuring it. */
atomic_store_explicit(&futex_word, 0, memory_order_relaxed);
timeout.tv_sec = 0;
timeout.tv_nsec = timeout_ns;
if (getrusage(RUSAGE_SELF, &before)) {
perror("getrusage");
return 1;
}
start = now_ns();
for (i = 0; i < iterations; i++) {
int ret;
errno = 0;
ret = syscall(SYS_futex, &futex_word, FUTEX_WAIT_PRIVATE, 0,
&timeout, NULL, 0);
if (ret != -1 || errno != ETIMEDOUT) {
fprintf(stderr,
"iteration %" PRIu64 ": ret=%d errno=%d\n",
i, ret, errno);
return 1;
}
}
elapsed = now_ns() - start;
if (getrusage(RUSAGE_SELF, &after)) {
perror("getrusage");
return 1;
}
printf("iterations=%" PRIu64 " timeout_ns=%" PRIu64
" elapsed_ns=%" PRIu64 " ns_per_wait=%.3f waits_per_sec=%.3f\n",
iterations, timeout_ns, elapsed, (double)elapsed / iterations,
(double)iterations * 1000000000.0 / elapsed);
printf("voluntary_cs=%ld involuntary_cs=%ld voluntary_cs_per_wait=%.6f\n",
after.ru_nvcsw - before.ru_nvcsw,
after.ru_nivcsw - before.ru_nivcsw,
(double)(after.ru_nvcsw - before.ru_nvcsw) / iterations);
return 0;
}Thomas Gleixner
maintainerQuoted 6 lines · Usama Arif
On Tue, 4 Aug 2026 17:07:59 +0000 Dmitry Ilvokhin <[email protected]> wrote:
The above data shows the significance of the patch.
It provides a very meaningful improvement (22.4% of time spent infutex_q_lock()will be significantly optimized and will also deliver second-order effects) and has no measurable impact on latency in the matching path.
IMHO, this patch is a free lunch.
Not really free. The user space access is not exactly cheap either because CLAC/STAC are memory fencing to meet the SMAP guarantees.
I've tried that lockless read/test before and gave up when a multi-waiter real world test case degraded by 5-10% depending on micro architecture.
It's carefully written to minimize lock contention in order to optimize wakeup latencies. The effect of the extra unlocked access and it's side effects shifts the timing enough that it runs into significantly more lock contentions than before.
So it might be great for your use case, but not so great for others.
Thanks,
tglx
Quoted 11 lines · Thomas Gleixner
Quoted 6 lines · Usama Arif
On Tue, 4 Aug 2026 17:07:59 +0000 Dmitry Ilvokhin <[email protected]> wrote:
The above data shows the significance of the patch.
It provides a very meaningful improvement (22.4% of time spent infutex_q_lock()will be significantly optimized and will also deliver second-order effects) and has no measurable impact on latency in the matching path.
IMHO, this patch is a free lunch.Not really free. The user space access is not exactly cheap either because CLAC/STAC are memory fencing to meet the SMAP guarantees.
My understanding from 86e6b1547b3d is that STAC/CLAC “end up serializing execution on older Zen,” while Zen 5’s AC renaming “improves performance of STAC/CLAC a lot a lot.” Architecturally, they only change the AC bit. They are not memory-ordering instructions like LFENCE. I am currently testing on Zen5 which could be why I didn't see any wall-time regression in futex_wait_timeout.c from [1].
Quoted 4 lines
I've tried that lockless read/test before and gave up when a multi-waiter real world test case degraded by 5-10% depending on micro architecture.
futex_wait_timeout.c [1] deliberately makes every call take the two-read path and doesnt show any wall-time regression. The extra userspace read ofcourse introduces additional instructions, but it is not showing up in any metric what I thought would be the worst case in real world metrics.
The precheck adds no work while hb->lock is held, so it won't cause any more contention.
I have been trying to coming up with some example userspace program that would be negatively impacted by this patch and can't. I am not sure how multi-waiter case that you described can result in 5-10% degradation as the extra read is not showing up in wall clock time and we are not adding more work under lock. I am currently testing on a Zen5 system. Could you share the reproducer, thread topology, measured metric, and CPU model on which you saw the 5–10% regression?
Thomas Gleixner
maintainerQuoted 9 lines · Usama Arif
Quoted 8 lines · Thomas Gleixner
Quoted 6 lines · Usama Arif
On Tue, 4 Aug 2026 17:07:59 +0000 Dmitry Ilvokhin <[email protected]> wrote:
The above data shows the significance of the patch.
It provides a very meaningful improvement (22.4% of time spent infutex_q_lock()will be significantly optimized and will also deliver second-order effects) and has no measurable impact on latency in the matching path.
IMHO, this patch is a free lunch.
Quoted 7 lines
Quoted 2 lines
Not really free. The user space access is not exactly cheap either because CLAC/STAC are memory fencing to meet the SMAP guarantees.
My understanding from
86e6b1547b3dis that STAC/CLAC “end up serializing execution on older Zen,” while Zen 5’s AC renaming “improves performance of STAC/CLAC a lot a lot.” Architecturally, they only change the AC bit. They are not memory-ordering instructions like LFENCE.
It's not a memory ordering instruction, but it has to guarantee that the AC change is effective when the subsequent permission check happens. That's true for both STAC and CLAC.
So it _cannot_ be free by definition and the penalty depends on the micro architecture.
Quoted 2 lines
I am currently testing on Zen5 which could be why I didn't see any wall-time regression in
futex_wait_timeout.cfrom [1].
It's not relevant whether your ZEN5 works fine or not. We are not optimizing for a particular machine.
A trivial futex bouncing test case with two threads degrades on a ZEN3 by ~20% and when looking at it with perf top clearly the extra user access stands out very prominently.
The below variant does not expose that behavior and actually improves the same test case by ~5% on that machine.
Thanks,
tglx
--- kernel/futex/waitwake.c | 12 +++++++++++- 1 file changed, 11 insertions(+), 1 deletion(-)
kernel/futex/waitwake.c +11 -1
@@ -857,7 +857,17 @@ int futex_wait_setup(u32 __user *uaddr,CLASS (hbr, hbr)(&q->key); auto hb = hbr.hb; -futex_q_lock (q, hb); +futex_hb_waiters_inc (hb); + q->lock_ptr = &hb->lock; + +if (!spin_trylock (&hb->lock)) { + ret =get_user_inline (uval, uaddr); +if (ret) +return ret; +if (uval != val) +return -EWOULDBLOCK ; +spin_lock (&hb->lock); + } ret =futex_get_value_locked (&uval, uaddr);
Thomas Gleixner
maintainerQuoted 31 lines · Thomas Gleixner
Quoted 9 lines · Usama Arif
Quoted 8 lines · Thomas Gleixner
Quoted 6 lines · Usama Arif
On Tue, 4 Aug 2026 17:07:59 +0000 Dmitry Ilvokhin <[email protected]> wrote:
The above data shows the significance of the patch.
It provides a very meaningful improvement (22.4% of time spent infutex_q_lock()will be significantly optimized and will also deliver second-order effects) and has no measurable impact on latency in the matching path.
IMHO, this patch is a free lunch.Quoted 7 lines
Quoted 2 lines
Not really free. The user space access is not exactly cheap either because CLAC/STAC are memory fencing to meet the SMAP guarantees.
My understanding from
86e6b1547b3dis that STAC/CLAC “end up serializing execution on older Zen,” while Zen 5’s AC renaming “improves performance of STAC/CLAC a lot a lot.” Architecturally, they only change the AC bit. They are not memory-ordering instructions like LFENCE.It's not a memory ordering instruction, but it has to guarantee that the AC change is effective when the subsequent permission check happens. That's true for both STAC and CLAC.
So it _cannot_ be free by definition and the penalty depends on the micro architecture.
Quoted 2 lines
I am currently testing on Zen5 which could be why I didn't see any wall-time regression in
futex_wait_timeout.cfrom [1].It's not relevant whether your ZEN5 works fine or not. We are not optimizing for a particular machine.
Quoted 6 lines
A trivial futex bouncing test case with two threads degrades on a ZEN3 by ~20% and when looking at it with perf top clearly the extra user access stands out very prominently.
The below variant does not expose that behavior and actually improves the same test case by ~5% on that machine.
Bah. Included the broken version. Fixed one is below.
Thanks,
tglx
--- kernel/futex/waitwake.c | 16 +++++++++++++++- 1 file changed, 15 insertions(+), 1 deletion(-)
kernel/futex/waitwake.c +15 -1
@@ -857,7 +857,21 @@ int futex_wait_setup(u32 __user *uaddr,CLASS (hbr, hbr)(&q->key); auto hb = hbr.hb; -futex_q_lock (q, hb); +futex_hb_waiters_inc (hb); + q->lock_ptr = &hb->lock; + +if (!spin_trylock (&hb->lock)) { + ret =get_user_inline (uval, uaddr); +if (ret) { +futex_hb_waiters_dec (hb); +return ret; + } +if (uval != val) { +futex_hb_waiters_dec (hb); +return -EWOULDBLOCK ; + } +spin_lock (&hb->lock); + } ret =futex_get_value_locked (&uval, uaddr);
Quoted 63 lines · Thomas Gleixner
Quoted 31 lines · Thomas Gleixner
Quoted 9 lines · Usama Arif
Quoted 8 lines · Thomas Gleixner
Quoted 6 lines · Usama Arif
On Tue, 4 Aug 2026 17:07:59 +0000 Dmitry Ilvokhin <[email protected]> wrote:
The above data shows the significance of the patch.
It provides a very meaningful improvement (22.4% of time spent infutex_q_lock()will be significantly optimized and will also deliver second-order effects) and has no measurable impact on latency in the matching path.
IMHO, this patch is a free lunch.Quoted 7 lines
Quoted 2 lines
Not really free. The user space access is not exactly cheap either because CLAC/STAC are memory fencing to meet the SMAP guarantees.
My understanding from
86e6b1547b3dis that STAC/CLAC “end up serializing execution on older Zen,” while Zen 5’s AC renaming “improves performance of STAC/CLAC a lot a lot.” Architecturally, they only change the AC bit. They are not memory-ordering instructions like LFENCE.It's not a memory ordering instruction, but it has to guarantee that the AC change is effective when the subsequent permission check happens. That's true for both STAC and CLAC.
So it _cannot_ be free by definition and the penalty depends on the micro architecture.
Quoted 2 lines
I am currently testing on Zen5 which could be why I didn't see any wall-time regression in
futex_wait_timeout.cfrom [1].It's not relevant whether your ZEN5 works fine or not. We are not optimizing for a particular machine.
Quoted 6 lines
A trivial futex bouncing test case with two threads degrades on a ZEN3 by ~20% and when looking at it with perf top clearly the extra user access stands out very prominently.
The below variant does not expose that behavior and actually improves the same test case by ~5% on that machine.
Bah. Included the broken version. Fixed one is below.
Thanks,
tglx
--- kernel/futex/waitwake.c | 16 +++++++++++++++- 1 file changed, 15 insertions(+), 1 deletion(-)kernel/futex/waitwake.c +8
-1@@ -857,7 +857,21 @@ int futex_wait_setup(u32 __user *uaddr,CLASS (hbr, hbr)(&q->key); auto hb = hbr.hb; -futex_q_lock (q, hb); +futex_hb_waiters_inc (hb); + q->lock_ptr = &hb->lock; + +if (!spin_trylock (&hb->lock)) { + ret =get_user_inline (uval, uaddr); +if (ret) { +futex_hb_waiters_dec (hb); +return ret;
kernel/futex/waitwake.c int futex_wait_setup(u32 __user *uaddr, · line 877
Quoted 10 lines
kernel/futex/waitwake.c +7
-0+ } +if (uval != val) { +futex_hb_waiters_dec (hb); +return -EWOULDBLOCK ; + } +spin_lock (&hb->lock); + } ret =futex_get_value_locked (&uval, uaddr);
Hi Thomas,
Sorry for the late reply.
I like this approach; it makes the trade-off much better than my patch. When spin_trylock() succeeds, the matching path performs only the existing single user access, rather than the two accesses in my version.
Is it alright if I send v2 of the patch with your diff above? Or would you like to send it?
Please let me know how you would like it attributed if I send it.
Thanks!
Usama
Thomas Gleixner
maintainerUsama!
Quoted 24 lines · Usama Arif
Quoted 23 lines · Thomas Gleixner
kernel/futex/waitwake.c +15
-1@@ -857,7 +857,21 @@ int futex_wait_setup(u32 __user *uaddr,CLASS (hbr, hbr)(&q->key); auto hb = hbr.hb; -futex_q_lock (q, hb); +futex_hb_waiters_inc (hb); + q->lock_ptr = &hb->lock; + +if (!spin_trylock (&hb->lock)) { + ret =get_user_inline (uval, uaddr); +if (ret) { +futex_hb_waiters_dec (hb); +return ret; + } +if (uval != val) { +futex_hb_waiters_dec (hb); +return -EWOULDBLOCK ; + } +spin_lock (&hb->lock); + }
Quoted 5 lines
kernel/futex/waitwake.c int futex_wait_setup(u32 __user *uaddr, · line 877
Quoted 2 lines
kernel/futex/waitwake.c +0
-0ret =futex_get_value_locked (&uval, uaddr);I like this approach; it makes the trade-off much better than my patch. When
spin_trylock()succeeds, the matching path performs only the existing single user access, rather than the two accesses in my version.
Correct.
Quoted 2 lines
Is it alright if I send v2 of the patch with your diff above? Or would you like to send it?
Go wild.
It lacks an __acquire(q->lock_ptr) annotation and a comment for this trylock muck and the open coded hb_waiter_inc(). The latter can just refer to futex_q_lock().
Also the exit condition should be simplified into one "if (ret || uval != val)", which removes four lines of code.
Quoted 1 line
Please let me know how you would like it attributed if I send it.
Suggested-by is fine.
Thanks,
tglx
Quoted 33 lines · Thomas Gleixner
Usama!
Quoted 24 lines · Usama Arif
Quoted 23 lines · Thomas Gleixner
kernel/futex/waitwake.c +15
-1@@ -857,7 +857,21 @@ int futex_wait_setup(u32 __user *uaddr,CLASS (hbr, hbr)(&q->key); auto hb = hbr.hb; -futex_q_lock (q, hb); +futex_hb_waiters_inc (hb); + q->lock_ptr = &hb->lock; + +if (!spin_trylock (&hb->lock)) { + ret =get_user_inline (uval, uaddr); +if (ret) { +futex_hb_waiters_dec (hb); +return ret; + } +if (uval != val) { +futex_hb_waiters_dec (hb); +return -EWOULDBLOCK ; + } +spin_lock (&hb->lock); + }Quoted 5 lines
kernel/futex/waitwake.c int futex_wait_setup(u32 __user *uaddr, · line 877
Quoted 2 lines
kernel/futex/waitwake.c +0
-0ret =futex_get_value_locked (&uval, uaddr);I like this approach; it makes the trade-off much better than my patch. When
spin_trylock()succeeds, the matching path performs only the existing single user access, rather than the two accesses in my version.
Quoted 7 lines
Correct.
Quoted 2 lines
Is it alright if I send v2 of the patch with your diff above? Or would you like to send it?
Go wild.
Thanks! I am going to try and run this in production workloads to gather data. Should be done in the next few days and send it early next week.
Quoted 14 lines
It lacks an
__acquire(q->lock_ptr)annotation and a comment for this trylock muck and the open codedhb_waiter_inc(). The latter can just refer tofutex_q_lock().Also the exit condition should be simplified into one "if (ret || uval != val)", which removes four lines of code.
Quoted 1 line
Please let me know how you would like it attributed if I send it.
Suggested-by is fine.
Thanks,
tglx
Quoted 38 lines · On Thu, 20 Aug 2026 19:05:31 +0100 Usama Arif <[email protected]> wrote:
Quoted 35 lines · Thomas Gleixner
Usama!
Quoted 24 lines · Usama Arif
Quoted 23 lines · Thomas Gleixner
kernel/futex/waitwake.c +15
-1@@ -857,7 +857,21 @@ int futex_wait_setup(u32 __user *uaddr,CLASS (hbr, hbr)(&q->key); auto hb = hbr.hb; -futex_q_lock (q, hb); +futex_hb_waiters_inc (hb); + q->lock_ptr = &hb->lock; + +if (!spin_trylock (&hb->lock)) { + ret =get_user_inline (uval, uaddr); +if (ret) { +futex_hb_waiters_dec (hb); +return ret; + } +if (uval != val) { +futex_hb_waiters_dec (hb); +return -EWOULDBLOCK ; + } +spin_lock (&hb->lock); + }Quoted 5 lines
kernel/futex/waitwake.c int futex_wait_setup(u32 __user *uaddr, · line 877
Quoted 2 lines
kernel/futex/waitwake.c +0
-0ret =futex_get_value_locked (&uval, uaddr);I like this approach; it makes the trade-off much better than my patch. When
spin_trylock()succeeds, the matching path performs only the existing single user access, rather than the two accesses in my version.Correct.
Quoted 8 lines
Quoted 5 lines
Quoted 2 lines
Is it alright if I send v2 of the patch with your diff above? Or would you like to send it?
Go wild.
Thanks! I am going to try and run this in production workloads to gather data. Should be done in the next few days and send it early next week.
Just coming back on this, its taking more time than I would like to setup a hosts with custom kernel on production traffic, I will update here once I have something with this patch.
Quoted 63 lines · Thomas Gleixner
Quoted 31 lines · Thomas Gleixner
Quoted 9 lines · Usama Arif
Quoted 8 lines · Thomas Gleixner
Quoted 6 lines · Usama Arif
On Tue, 4 Aug 2026 17:07:59 +0000 Dmitry Ilvokhin <[email protected]> wrote:
The above data shows the significance of the patch.
It provides a very meaningful improvement (22.4% of time spent infutex_q_lock()will be significantly optimized and will also deliver second-order effects) and has no measurable impact on latency in the matching path.
IMHO, this patch is a free lunch.Quoted 7 lines
Quoted 2 lines
Not really free. The user space access is not exactly cheap either because CLAC/STAC are memory fencing to meet the SMAP guarantees.
My understanding from
86e6b1547b3dis that STAC/CLAC “end up serializing execution on older Zen,” while Zen 5’s AC renaming “improves performance of STAC/CLAC a lot a lot.” Architecturally, they only change the AC bit. They are not memory-ordering instructions like LFENCE.It's not a memory ordering instruction, but it has to guarantee that the AC change is effective when the subsequent permission check happens. That's true for both STAC and CLAC.
So it _cannot_ be free by definition and the penalty depends on the micro architecture.
Quoted 2 lines
I am currently testing on Zen5 which could be why I didn't see any wall-time regression in
futex_wait_timeout.cfrom [1].It's not relevant whether your ZEN5 works fine or not. We are not optimizing for a particular machine.
Quoted 6 lines
A trivial futex bouncing test case with two threads degrades on a ZEN3 by ~20% and when looking at it with perf top clearly the extra user access stands out very prominently.
The below variant does not expose that behavior and actually improves the same test case by ~5% on that machine.
Bah. Included the broken version. Fixed one is below.
Thanks,
tglx
--- kernel/futex/waitwake.c | 16 +++++++++++++++- 1 file changed, 15 insertions(+), 1 deletion(-)kernel/futex/waitwake.c +8
-1@@ -857,7 +857,21 @@ int futex_wait_setup(u32 __user *uaddr,CLASS (hbr, hbr)(&q->key); auto hb = hbr.hb; -futex_q_lock (q, hb); +futex_hb_waiters_inc (hb); + q->lock_ptr = &hb->lock; + +if (!spin_trylock (&hb->lock)) { + ret =get_user_inline (uval, uaddr); +if (ret) { +futex_hb_waiters_dec (hb); +return ret;
kernel/futex/waitwake.c int futex_wait_setup(u32 __user *uaddr, · line 877
Quoted 10 lines
kernel/futex/waitwake.c +7
-0+ } +if (uval != val) { +futex_hb_waiters_dec (hb); +return -EWOULDBLOCK ; + } +spin_lock (&hb->lock); + } ret =futex_get_value_locked (&uval, uaddr);
I looked at production data to understand better where futex_wait_setup() calls are coming from. Majority of the cost is contended userspace mutex hammering the same futex word from different threads, where amount of threads differ from usecase to usecase.
The userspace mutex implementation is pthread_mutex_t from glibc, which has only three states: free (0), locked (1) and locked with waiters (2). When critcal section is short, mutex releaser and winner acquirer switch the state from 2 to 0 and 1 and this produces high futex value missmatch rate. The higher contention is, the higher futex value missmatch rate is.
I've built a benchmark to simulate this behaviour on the smaller scale and run it with two threads and nproc threads to simulate low and high contention cases. The benchmark is a bit on a extreme side, but I think it approximates the real world case quite well.
The numbers below are averaged across 10 runs.
SKYLAKE (2 NUMA NODES, 80 CPUS, Intel(R) Xeon(R) Gold 6138 CPU)
Threads Baseline (ops/sec) Patched 95% CI Diff
-----------------------------------------------------------------------
2 5,917,777 6,441,061 [ -1.98%, +19.67%] +8.84%
80 122,926 77,801 [-41.17%, -32.25%] -36.71%
BERGAMO (1 NUMA NODE, 176 CPUS, AMD EPYC 9D64)
Threads Baseline (ops/sec) Patched 95% CI Diff
-----------------------------------------------------------------------
2 14,952,962 14,482,494 [ -4.62%, -1.68%] -3.15%
176 161,294 127,563 [-21.72%, -20.11%] -20.91%
Skylake two thread case seems in line with ~5% improvement you measured, but numbers are quite noisy. Other runs do not look encouraging.
It looks like early bail out amplifies contention problem even more. Instead of letting thread spin on the hb->lock, early check returns just for userspace to retry again moment later. Ideally, it would be better to park spinning thread as fast as possible and with early bail out we do opposite of that.
Anyway, I would be curious to know what do you think about it. Maybe there is a better way to measure this optimization.
From 34184a0324ca734dc46aa957242c59ff9522ac54 Mon Sep 17 00:00:00 2001
From: Dmitry Ilvokhin <[email protected]>
Date: Wed, 19 Aug 2026 10:13:34 -0700
Subject: [PATCH] perf bench futex: Add wait/wake benchmark
Userspace uses futex_wait() and futex_wake() to implement sleepable synchronization primitives. Currently, there is no benchmark to measure futex_wait()/futex_wake() calls throughput.
Introduce perf bench futex wait-wake benchmark that stresses kernel's futex_wait()/futex_wake() implementation and measures throughput of paired calls.
--- tools/perf/Documentation/perf-bench.txt | 3 + tools/perf/bench/Build | 1 + tools/perf/bench/bench.h | 1 + tools/perf/bench/futex-wait-wake.c | 254 ++++++++++++++++++++++++ tools/perf/builtin-bench.c | 1 + 5 files changed, 260 insertions(+) create mode 100644 tools/perf/bench/futex-wait-wake.c
tools/perf/Documentation/perf-bench.txt +3 -0
@@ -294,6 +294,9 @@ Suite for evaluating wake calls. *wake-parallel*:: Suite for evaluating parallel wake calls. +*wait-wake*:: +Suite for evaluating parallel wait/wake calls. + *requeue*:: Suite for evaluating requeue calls.
tools/perf/bench/Build +1 -0
@@ -7,6 +7,7 @@ perf-bench-y += futex.o perf-bench-y += futex-hash.o perf-bench-y += futex-wake.o perf-bench-y += futex-wake-parallel.o +perf-bench-y += futex-wait-wake.o perf-bench-y += futex-requeue.o perf-bench-y += futex-lock-pi.o perf-bench-y += epoll-wait.o
tools/perf/bench/bench.h +1 -0
@@ -33,6 +33,7 @@ int bench_mem_find_bit(int argc, const char **argv);int bench_futex_hash (int argc,const char **argv);int bench_futex_wake (int argc,const char **argv);int bench_futex_wake_parallel (int argc,const char **argv); +int bench_futex_wait_wake (int argc,const char **argv);int bench_futex_requeue (int argc,const char **argv);/* pi futexes */ int bench_futex_lock_pi (int argc,const char **argv);
tools/perf/bench/futex-wait-wake.c new file +254 -0
254 lines not on this page · raw message
tools/perf/builtin-bench.c +1 -0
@@ -74,6 +74,7 @@ static const struct bench futex_benchmarks[] = { { "hash", "Benchmark for futex hash table", bench_futex_hash }, { "wake", "Benchmark for futex wake calls", bench_futex_wake }, { "wake-parallel", "Benchmark for parallel futex wake calls", bench_futex_wake_parallel }, + { "wait-wake", "Benchmark for futex wait/wake calls", bench_futex_wait_wake }, { "requeue", "Benchmark for futex requeue calls", bench_futex_requeue },/* pi-futexes */ { "lock-pi", "Benchmark for futex lock_pi calls", bench_futex_lock_pi },
Signature · 1 line
2.53.0-Meta
Thomas Gleixner
maintainerQuoted 24 lines · Dmitry Ilvokhin
On Fri, Aug 14, 2026 at 06:02:45PM +0200, Thomas Gleixner wrote:
I've built a benchmark to simulate this behaviour on the smaller scale and run it with two threads andnprocthreads to simulate low and high contention cases. The benchmark is a bit on a extreme side, but I think it approximates the real world case quite well.The numbers below are averaged across 10 runs.
SKYLAKE (2 NUMA NODES, 80 CPUS, Intel(R) Xeon(R) Gold 6138 CPU)
Threads Baseline (ops/sec) Patched 95% CI Diff
-----------------------------------------------------------------------
2 5,917,777 6,441,061 [ -1.98%, +19.67%] +8.84%
80 122,926 77,801 [-41.17%, -32.25%] -36.71%BERGAMO (1 NUMA NODE, 176 CPUS, AMD EPYC 9D64)
Threads Baseline (ops/sec) Patched 95% CI Diff
-----------------------------------------------------------------------
2 14,952,962 14,482,494 [ -4.62%, -1.68%] -3.15%
176 161,294 127,563 [-21.72%, -20.11%] -20.91%
Quoted 8 lines
Skylake two thread case seems in line with ~5% improvement you measured, but numbers are quite noisy. Other runs do not look encouraging.
It looks like early bail out amplifies contention problem even more. Instead of letting thread spin on the
hb->lock, early check returns just for userspace to retry again moment later. Ideally, it would be better to park spinning thread as fast as possible and with early bail out we do opposite of that.
Changing the timing even slightly either in user space or in kernel space results in different outcomes depending on the micro architecture, NUMA, contention scenario ...
While it is benefical for some scenarios to avoid the wait/wake, for others especially those with high concurrency in trying to acquire the futex the cache line bouncing just gets worse.
And yes, you are right that with your benchmark the early bail amplifies exactly that problem. The hash bucket lock contention eases the cache line contention for the price of wasting CPU cycles in the kernel.
There is no magic cure for this with the current implementations and I doubt that any benchmark will give a satisfying answer which is generally useful accross a wider range of application scenarios.
This needs quite some thought and investigations to get right.
Thanks,
tglx
Thomas Gleixner
maintainerQuoted 6 lines · Thomas Gleixner
On Thu, Aug 20 2026 at 16:14, Dmitry Ilvokhin wrote:
There is no magic cure for this with the current implementations and I doubt that any benchmark will give a satisfying answer which is generally useful accross a wider range of application scenarios.This needs quite some thought and investigations to get right.
I looked a bit deeper into it. When the number of contenders is big enough to cause a massive cache line bouncing issue on the futex variable then the lock contention on hb lock helps to prevent it from becoming worse. It basically ensures that enough waiters are stuck in the kernel that the rest of the threads can make progress, even if they right away after acquiring the hash bucket lock.
Works by chance but certainly not by design :)
Thomas Gleixner
maintainerkernel/futex/waitwake.c int futex_wait_setup(u32 __user *uaddr, u32 val, unsigned int flags, · line 659
Quoted 8 lines · Usama Arif
kernel/futex/waitwake.c +7
-0+/* +* A mismatch here refuses the wait without locating the hash bucket; +* a match is rechecked under the lock below before queueing. +* +* get_futex_key() runs get_user_pages_fast() only for shared futexes, +* so their page is resident and the non-faulting read suffices, with +* the locked path recovering if it does not. A private futex may
That's a fairy tale:
get_futex_key()
...
// shared
get_user_pages_fast(); // gets a page reference
...
folio = page_folio(page);
...
out:
folio_put(folio); // drops the page referenceThanks,
tglx
Quoted 23 lines · Thomas Gleixner
kernel/futex/waitwake.c int futex_wait_setup(u32 __user *uaddr, u32 val, unsigned int flags, · line 659
Quoted 8 lines · Usama Arif
kernel/futex/waitwake.c +7
-0+/* +* A mismatch here refuses the wait without locating the hash bucket; +* a match is rechecked under the lock below before queueing. +* +* get_futex_key() runs get_user_pages_fast() only for shared futexes, +* so their page is resident and the non-faulting read suffices, with +* the locked path recovering if it does not. A private futex may That's a fairy tale:
get_futex_key() ... // shared get_user_pages_fast(); // gets a page reference ... folio = page_folio(page); ... out: folio_put(folio); // drops the page reference
Quoted 3 lines
Thanks,
tglx
I will fix the comment if the discussion in the other thread hopefully works out and there is a v2. folio_put() does not immediately evict the page; however as you point out it removes the guarantee that it stays available.
get_futex_key() has just resolved the shared page, so a non-faulting read is "very likely" to succeed. If it doesn't, we get -EFAULT and will then reach the existing locked check and continues to do what is done without the patch.
Thomas Gleixner
maintainerQuoted 33 lines · Usama Arif
Quoted 23 lines · Thomas Gleixner
kernel/futex/waitwake.c int futex_wait_setup(u32 __user *uaddr, u32 val, unsigned int flags, · line 659
Quoted 8 lines · Usama Arif
kernel/futex/waitwake.c +7
-0+/* +* A mismatch here refuses the wait without locating the hash bucket; +* a match is rechecked under the lock below before queueing. +* +* get_futex_key() runs get_user_pages_fast() only for shared futexes, +* so their page is resident and the non-faulting read suffices, with +* the locked path recovering if it does not. A private futex may That's a fairy tale:
get_futex_key() ... // shared get_user_pages_fast(); // gets a page reference ... folio = page_folio(page); ... out: folio_put(folio); // drops the page referenceQuoted 3 lines
Thanks,
tglx
I will fix the comment if the discussion in the other thread hopefully works out and there is a v2.
folio_put()does not immediately evict the page; however as you point out it removes the guarantee that it stays available.
Quoted 4 lines
get_futex_key()has just resolved the shared page, so a non-faulting read is "very likely" to succeed. If it doesn't, we get-EFAULTand will then reach the existing locked check and continues to do what is done without the patch.
What's the point of that exercise?
If the user access fails and it can fail with a page fault because it's preemptible context, then the operation is done and returns -EFAULT to user space.
This special handling of private futexes does not buy any value at all, actually it adds a pointless conditional and makes the code incomprehensible no matter how much effort you put into a comment.
Thanks,
tglx