[PATCH] futex: Avoid hash-bucket locking for mismatched waits

[PATCH] futex: Avoid hash-bucket locking for mismatched waits

[Usama Arif]

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.

Signed-off-by: Usama Arif <usama.arif@linux.dev>
---
 kernel/futex/waitwake.c                       | 30 +++++++++++++++----
 .../selftests/futex/functional/futex_numa.c   |  6 ++--
 2 files changed, 28 insertions(+), 8 deletions(-)

diff --git a/kernel/futex/waitwake.c b/kernel/futex/waitwake.c
index d4483d15d30a..dc22aea9808a 100644
--- a/kernel/futex/waitwake.c
+++ b/kernel/futex/waitwake.c
@@ -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);
diff --git a/tools/testing/selftests/futex/functional/futex_numa.c b/tools/testing/selftests/futex/functional/futex_numa.c
index e0a33510ccb6..029a9a6afd95 100644
--- a/tools/testing/selftests/futex/functional/futex_numa.c
+++ b/tools/testing/selftests/futex/functional/futex_numa.c
@@ -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++;
-- 
2.53.0-Meta

Re: [PATCH] futex: Avoid hash-bucket locking for mismatched waits

[Dmitry Ilvokhin]

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 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?
 
> 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?

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.

Re: [PATCH] futex: Avoid hash-bucket locking for mismatched waits

[Usama Arif]

On Tue, 4 Aug 2026 17:07:59 +0000 Dmitry Ilvokhin <d@ilvokhin.com> 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;
}