Re: [PATCH] futex: Avoid hash-bucket locking for mismatched waits
From: Usama Arif
Date: Wed Aug 05 2026 - 09:32:19 EST
On Tue, 4 Aug 2026 17:07:59 +0000 Dmitry Ilvokhin <d@xxxxxxxxxxxx> wrote:
> On Fri, Jul 31, 2026 at 12:26:24PM -0700, Usama Arif wrote:
> > 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.
>
> 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% woken
>
> 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.
>
> 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?
>
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.
> > 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).
> >
>
> 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.
>
> 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;
}