[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