vault

The Kernel Futex Interface

19 min read

The Kernel Futex Interface

A futex (“fast userspace mutex”) is the kernel-side substrate that almost every userspace blocking lock on Linux — pthread_mutex_t, pthread_cond_t, glibc semaphores, the Go runtime’s thread parking — is built on. Its defining idea, due to Hubertus Franke, Rusty Russell, and Matthew Kirkwood (OLS 2002, “Fuss, Futexes and Furwocks”), is that the uncontended lock and unlock operations happen entirely in userspace as a single atomic read-modify-write on a shared 32-bit word — “in the uncontended case, no system calls are made, and no kernel involvement is necessary.” The kernel is entered through the futex() syscall only on contention: to block a thread whose lock attempt failed (FUTEX_WAIT), or to wake a blocked thread when the lock is released (FUTEX_WAKE). The kernel keeps no per-lock object at all in the common case — it materializes wait state lazily, in a global hash table keyed by the physical identity of the futex word, only while a thread is actually parked. This note covers the in-kernel mechanism and the two synchronization-correctness variants — priority-inheritance (PI) futexes and robust futexes — pinned to Linux 6.12 LTS (released 2024-11-17). The userspace-facing futex() syscall API as an IPC surface is the subject of the Linux IPC MOC’s futex note; the generic/Go-runtime angle lives in Futex and OS Synchronization Primitives; this note is deliberately scoped to the kernel internals and the sync variants and cross-links rather than re-derives those siblings.

Mental Model — A Lock That Doesn’t Exist Until It’s Contended

The mental shift that makes futexes click is that there is no kernel lock object. A traditional kernel-mediated lock (a SysV semaphore, say) is a kernel data structure you create, reference by an ID, and destroy. A futex is none of that: it is just a u32 of ordinary user memory that userspace agrees, by convention, to treat as a lock word. The kernel does not know that word exists until a thread comes to it saying “I read this word, it had value V, and based on V I need to sleep — FUTEX_WAIT(uaddr, V).” Only then does the kernel create a transient wait-queue entry, and it tears that entry down the moment the thread is woken. Between contended episodes, the lock costs the kernel exactly nothing.

This is why the fast path is free. A userspace mutex unlock that has no waiters is a single atomic store (or compare-and-swap) to the word — no syscall, no kernel transition, no scheduler involvement. The expensive futex() syscall is paid only when a thread genuinely must block or genuinely must wake someone. The art of the futex protocol, then, is the userspace/kernel handshake that ensures a waiter and a waker never miss each other across that boundary — the classic lost-wakeup race.

flowchart TB
  subgraph US["Userspace (no kernel involvement)"]
    L["lock(): CAS word 0->1<br/>uncontended: done"]
    U["unlock(): word = 0<br/>uncontended: done"]
  end
  subgraph K["Kernel — only on contention"]
    HT["futex hash table<br/>jhash(key) -> bucket"]
    HB["futex_hash_bucket<br/>spinlock + plist of waiters"]
    W["FUTEX_WAIT:<br/>lock bucket, re-read word,<br/>if still == val: enqueue + schedule()"]
    WK["FUTEX_WAKE:<br/>lock bucket, walk plist,<br/>wake_up_q the matches"]
    HT --> HB
    HB --> W
    HB --> WK
  end
  L -.->|"CAS fails (contended)<br/>FUTEX_WAIT syscall"| W
  U -.->|"saw waiters bit<br/>FUTEX_WAKE syscall"| WK

The two-level futex architecture. What it shows: the lock/unlock fast paths are pure userspace atomics on the shared word; the kernel is reached only when an atomic op observes contention, at which point a global hash table maps the futex’s identity to a per-bucket lock and waiter list. The insight to take: the kernel holds no state at all for an uncontended futex — wait state is allocated lazily on the slow path and freed on wakeup, which is precisely what makes the common case cost zero syscalls.

Mechanical Walk-through — Hash Table, Keys, Wait and Wake

Identifying a futex: the key and the hash bucket

Because a futex is just user memory, the kernel must derive a stable identity for the word so that a waiter and a waker who touch the same lock land on the same wait queue — even across processes sharing memory. That identity is the union futex_key, computed by get_futex_key() in core.c. The kernel distinguishes two cases (core.c, v6.12):

  • Private futexes (the FUTEX_PRIVATE_FLAG is set, meaning the futex is only used within one address space). The key is simply (current->mm, address, 0) — the mm pointer plus the virtual address. No page lookup is needed: “As the mm cannot disappear under us and the ‘key’ only needs virtual address, we dont even have to find the underlying vma.” This is the fast, common case for an ordinary process-local pthread_mutex_t.
  • Shared futexes (no private flag; the futex word lives in memory shared between processes via mmap/shmem). The key must be independent of any one process’s virtual address, so it is (inode->i_sequence, page->index, offset_within_page) — anchored to the physical backing object. get_futex_key() calls get_user_pages_fast() to pin the page and resolve its mapping, then derives a machine-wide-unique inode sequence number via get_inode_sequence_number().

The key is then hashed into the global table by futex_hash():

struct futex_hash_bucket *futex_hash(union futex_key *key)
{
	u32 hash = jhash2((u32 *)key, offsetof(typeof(*key), both.offset) / 4,
			  key->both.offset);
	return &futex_queues[hash & (futex_hashsize - 1)];
}

jhash2 is Bob Jenkins’ hash over the key words; the result is masked into the power-of-two-sized futex_queues array. The table is global and sized at boot proportional to the number of CPUs. Multiple distinct futexes can collide into one bucket — that is fine, because each waiter records its own futex_key and the wake path matches on the full key, not on the bucket.

A futex_hash_bucket is deliberately tiny and cache-line aligned (futex.h, v6.12):

struct futex_hash_bucket {
	atomic_t waiters;
	spinlock_t lock;
	struct plist_head chain;
} ____cacheline_aligned_in_smp;

The lock serializes all operations on the bucket; chain is a priority-sorted list (plist) of waiters, so that a wake can prefer the highest-priority waiter (important for real-time correctness); and waiters is an atomic counter used by the lock-free wakeup-skip optimization described below. Each parked task is represented by a struct futex_q linked into chain, carrying its task, its key, the lock_ptr of the bucket, a wake handler, and a bitset.

FUTEX_WAIT: verify-then-sleep, under the bucket lock

The single most important invariant of FUTEX_WAIT is that the kernel re-reads the futex word under the bucket lock and checks it still equals the caller’s expected value before sleeping. Without this, a wakeup that happened between userspace’s read and the syscall would be lost forever. The path is futex_wait() → __futex_wait() → futex_wait_setup() then futex_wait_queue() (waitwake.c, v6.12).

futex_wait_setup() resolves the key, locks the bucket, and reads the current word uval:

ret = get_futex_key(uaddr, flags, &q->key, FUTEX_READ);
...
*hb = futex_q_lock(q);
ret = futex_get_value_locked(&uval, uaddr);
...
if (uval != val) {
	futex_q_unlock(*hb);
	ret = -EWOULDBLOCK;
}

If the word no longer equals the value userspace passed in (val), the lock was released or grabbed by someone else in the interim, so the kernel returns -EWOULDBLOCK (which surfaces to userspace as EAGAIN) without sleeping — userspace retries its atomic. The source comment states the contract exactly: “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… If we locked the hash-bucket after testing *uaddr, that would open a race condition where we could block indefinitely with cond(var) false.” Locking the bucket before the final read is what closes that window.

If the word matches, futex_wait_queue() enqueues the futex_q and sleeps:

set_current_state(TASK_INTERRUPTIBLE|TASK_FREEZABLE);
futex_queue(q, hb);   /* enqueue then release hb->lock */
if (timeout) hrtimer_sleeper_start_expires(timeout, HRTIMER_MODE_ABS);
if (likely(!plist_node_empty(&q->list))) {
	if (!timeout || timeout->task)
		schedule();
}
__set_current_state(TASK_RUNNING);

The task state is set to TASK_INTERRUPTIBLE before enqueueing and releasing the bucket lock, so any concurrent waker that takes the bucket lock after this point will find the task on the list and its state already set — no wakeup can slip through. After schedule() returns (woken, timed out, or signalled), __futex_wait() calls futex_unqueue(); if the task was not still on the list, it was woken legitimately and returns success.

FUTEX_WAKE: walk the bucket, mark, wake outside the lock

futex_wake() resolves the key, locks the bucket, walks chain, and for each futex_q whose key matches it invokes the wake handler:

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 (!(this->bitset & bitset)) continue;
		this->wake(&wake_q, this);
		if (++ret >= nr_wake) break;
	}
}
spin_unlock(&hb->lock);
wake_up_q(&wake_q);

Two subtleties: the wake handler (futex_wake_mark) does not call wake_up() directly — it removes the futex_q from the list and adds the task to a wake_q, and only wake_up_q() after the bucket lock is dropped actually makes tasks runnable, to keep the bucket lock hold-time minimal. And nr_wake (the syscall’s val argument) bounds how many are woken — a plain mutex unlock wakes one; a condition-variable broadcast might wake INT_MAX.

Closing the lost-wakeup race with the waiters counter

There is a lock-free fast path on the wake side: if no thread is parked, the waker can skip taking the bucket lock entirely (futex_hb_waiters_pending() reads the atomic waiters count and returns early when it is zero). This optimization is dangerous unless it is impossible for a waker to both miss the futex-value change and miss the enqueue. The kernel proves it cannot, with a pair of memory barriers documented at the top of waitwake.c. The waiter does waiters++ (barrier A) then reads the futex word; the waker writes the futex word then (barrier B) reads waiters. This is a Dekker-style store-load pattern:

X = Y = 0
w[X]=1     w[Y]=1
MB         MB
r[Y]=y     r[X]=x

The barriers guarantee x==0 && y==0 is impossible — i.e. the waker cannot simultaneously read “no waiters” and have its value-change be missed by the waiter. Either the waiter sees the new value (and bails out of FUTEX_WAIT with -EWOULDBLOCK), or the waker sees a nonzero waiter count (and takes the bucket lock to wake it). This is the formal heart of futex correctness and connects directly to the kernel memory barriers and the LKMM.

The Core and Bitset Operations

The futex() syscall multiplexes operations through its op argument, dispatched by do_futex() in syscalls.c. The numeric op codes are defined in the UAPI header (uapi/linux/futex.h, v6.12):

  • FUTEX_WAIT (0) / FUTEX_WAKE (1) — the bread and butter described above. FUTEX_WAIT(uaddr, val) blocks while *uaddr == val; FUTEX_WAKE(uaddr, n) wakes up to n waiters on uaddr.
  • FUTEX_WAIT_BITSET (9) / FUTEX_WAKE_BITSET (10) — a generalization carrying a 32-bit bitset. A waiter is only woken if its bitset intersects the waker’s bitset (this->bitset & bitset in the wake loop above). The plain FUTEX_WAIT/FUTEX_WAKE are simply the bitset variants with bitset == FUTEX_BITSET_MATCH_ANY (0xffffffff), which do_futex() substitutes via val3 = FUTEX_BITSET_MATCH_ANY. The bitset is how glibc implements a single wait-queue that distinguishes, e.g., reader vs writer wakeups without spurious wakeups. A second difference: FUTEX_WAIT_BITSET’s timeout is treated as an absolute time (and can use CLOCK_REALTIME via the FUTEX_CLOCK_REALTIME flag), whereas plain FUTEX_WAIT’s timeout is relative.
  • FUTEX_WAKE_OP (5) — an atomic “modify second futex, then conditionally wake on both” operation (futex_atomic_op_inuser), used by glibc to fuse a condition-variable internal state update with a wake.

Requeue and the condition-variable thundering herd

FUTEX_REQUEUE (3) / FUTEX_CMP_REQUEUE (4) exist to fix a specific, real performance disaster in pthread_cond_broadcast(). A POSIX condition variable is, internally, two futexes: the condvar’s own word and the associated mutex. When pthread_cond_broadcast() must wake everyone waiting on the condvar, a naïve implementation would FUTEX_WAKE all of them — but every woken thread immediately tries to lock the same associated mutex, so all but one instantly block again on the mutex. That is the thundering herd: a storm of wakeups, context switches, and re-sleeps for threads that had no chance of making progress. The FUTEX_CMP_REQUEUE man page states the fix exactly (FUTEX_CMP_REQUEUE(2const)):

“If a waker thread used FUTEX_WAKE, then all waiters waiting on B would be woken up, and they would all try to acquire lock A. However, waking all of the threads in this manner would be pointless because all except one of the threads would immediately block on lock A again. By contrast, a requeue operation wakes just one waiter and moves the other waiters to lock A, and when the woken waiter unlocks A then the next waiter can proceed.”

Requeue therefore wakes nr_wake waiters (typically one) on the source futex and atomically moves (requeue_futex() in requeue.c) up to nr_requeue of the remaining waiters from the source bucket’s chain to the target futex’s bucket, without waking them. They wake naturally, one at a time, as the mutex is handed off. FUTEX_CMP_REQUEUE additionally takes an expected value val3 and verifies the source word still equals it under the bucket lock before requeueing — closing a race where the condvar state changed between userspace’s decision to broadcast and the syscall; FUTEX_REQUEUE (no compare) is the older, racier form and is effectively deprecated for this reason. The requeue acquires both buckets’ locks via double_lock_hb(), which orders the two locks by address to avoid an AB-BA deadlock (the kind lockdep would otherwise flag).

PI-Futexes — Priority Inheritance in the Word

A plain futex cannot solve priority inversion: if a low-priority thread holds a futex that a high-priority thread needs, and a medium-priority thread is runnable, the medium thread starves the holder and the high thread is blocked indefinitely. The cure is priority inheritance — temporarily boosting the holder to the waiter’s priority — and Linux exposes it to userspace (as pthread_mutexattr_setprotocol(PTHREAD_PRIO_INHERIT)) via PI-futexes: FUTEX_LOCK_PI (6), FUTEX_UNLOCK_PI (7), FUTEX_TRYLOCK_PI (8), and FUTEX_LOCK_PI2 (13, the absolute-CLOCK_MONOTONIC-timeout variant). The full PI protocol, the chain walk, and the rt_mutex machinery are the subject of Priority Inheritance and the RT-Mutex; here we cover only the futex-specific glue.

PI-futexes impose a defined layout on the futex word, unlike plain futexes where the value is opaque to the kernel. The word encodes the owner’s thread ID in its low 30 bits plus two flag bits (uapi/linux/futex.h):

#define FUTEX_WAITERS    0x80000000   /* contended: kernel state exists */
#define FUTEX_OWNER_DIED 0x40000000   /* owner died holding the lock    */
#define FUTEX_TID_MASK   0x3fffffff   /* the owner's TID                */

The uncontended PI-lock fast path is still pure userspace: a CAS of 0 -> own_TID. On contention, the kernel side is futex_lock_pi_atomic() in pi.c (pi.c, v6.12). It reads the word, detects self-deadlock ((uval & FUTEX_TID_MASK) == vpid → -EDEADLK), and — being the first waiter — sets the waiters bit so the owner is forced into the kernel on unlock:

/* First waiter. Set the waiters bit before attaching ourself to the
 * owner. If owner tries to unlock, it will be forced into the kernel
 * and blocked on hb->lock. */
newval = uval | FUTEX_WAITERS;
ret = lock_pi_update_atomic(uaddr, uval, newval);
...
return attach_to_pi_owner(uaddr, newval, key, ps, exiting);

Setting FUTEX_WAITERS is the crux: once set, the owner’s userspace unlock CAS (own_TID -> 0) fails, forcing the owner into FUTEX_UNLOCK_PI where the kernel can perform the priority-deboost and hand the lock to the highest-priority waiter. The kernel then attaches a struct futex_pi_state — which embeds a real rt_mutex_base pi_mutex and tracks the owner task — and the waiting thread blocks on that rt_mutex via __rt_mutex_start_proxy_lock() + rt_mutex_wait_proxy_lock(). It is the rt_mutex, not the futex code, that runs the PI chain walk and boosts the owner. On FUTEX_UNLOCK_PI, wake_futex_pi() calls __rt_mutex_futex_unlock() to deboost and select the next owner, writing that owner’s TID into the userspace word. This is why a PI-futex word is kernel-readable: the kernel must know who owns the lock to run inheritance, whereas a plain futex word is meaningful only to userspace.

Robust Futexes — Surviving a Crashed Lock-Holder

A second correctness variant addresses a different failure: what happens when a thread dies while holding a futex? With a plain mutex, a crash mid-critical-section leaves the lock word stuck at the dead owner’s value forever — every other thread blocks on it eternally. Robust futexes let the kernel clean up after a dead holder so waiters are released.

The mechanism is a per-task robust list. A thread registers a struct robust_list_head once via set_robust_list(2), and thereafter (entirely in userspace, glibc does this) links each futex it locks into a per-thread linked list whose head the kernel knows. The structures are part of the syscall ABI (uapi/linux/futex.h):

struct robust_list { struct robust_list __user *next; };
struct robust_list_head {
	struct robust_list list;            /* head; points to itself if empty */
	long futex_offset;                  /* offset from list node to the futex word */
	struct robust_list __user *list_op_pending;  /* the in-flight lock, race window */
};

The clever detail is futex_offset and list_op_pending. The list links live inside each userspace lock object, at a fixed offset (futex_offset) from the futex word — so the kernel can walk the list of lock objects and find each one’s futex word without hardcoding any layout. And because adding yourself to the list cannot be atomic with acquiring the lock, userspace first stores the to-be-taken lock into list_op_pending, then acquires, then links it and clears the pending field — so the kernel always sees a lock the thread might hold even mid-acquire.

On thread exit (including a crash that the kernel turns into do_exit()), futex_cleanup() in core.c checks tsk->robust_list and, if set, calls exit_robust_list(). This walks the list (very defensively — it is userspace memory and could be corrupt or circular, hence the ROBUST_LIST_LIMIT of 2048 and cond_resched()), and for each entry calls handle_futex_death():

owner = uval & FUTEX_TID_MASK;
if (owner != task_pid_vnr(curr))
	return 0;                         /* not actually ours; skip */
/* Set the OWNER_DIED bit atomically via cmpxchg, preserving WAITERS,
 * then wake a waiter so it can take over and notice OWNER_DIED. */
mval = (uval & FUTEX_WAITERS) | FUTEX_OWNER_DIED;
... futex_cmpxchg_value_locked(&nval, uaddr, uval, mval) ...

So a dead holder’s futexes get the FUTEX_OWNER_DIED bit set in their word, and any waiter is woken with futex_wake(). The woken waiter sees FUTEX_OWNER_DIED and knows the lock’s protected data may be inconsistent — glibc surfaces this to the application as EOWNERDEAD from pthread_mutex_lock(), and the application can either recover the state and call pthread_mutex_consistent() or mark the mutex permanently unusable. The kernel only validates the owner TID matches the dying task, so a malformed robust list can at worst leak a lock, never wake the wrong waiter. Note PI-futexes and robust futexes compose: a robust PI-futex hands ownership through the rt_mutex path while also setting OWNER_DIED.

futex2 — futex_waitv() for Waiting on Multiple Futexes

The original futex() syscall waits on exactly one futex word. The futex2 family generalizes this; the piece merged so far is futex_waitv(), a dedicated syscall (number aside from the multiplexed futex()) that lets a thread wait on an array of up to FUTEX_WAITV_MAX (128) futexes at once and wake on the first of them (futex_waitv(2)). Each element is a struct futex_waitv { __u64 val; __u64 uaddr; __u32 flags; __u32 __reserved; } with per-element FUTEX2_* flags (FUTEX2_SIZE_U32, FUTEX2_PRIVATE, FUTEX2_NUMA). The motivating consumer was game/graphics runtimes — notably Wine/Proton emulating the Windows WaitForMultipleObjects semantics, which the single-futex futex() could not express efficiently. In v6.12 only the 32-bit size is actually implemented (futex_flags_valid() rejects FLAGS_SIZE_64 etc.), even though the ABI reserves bits for 8/16/64-bit futexes. Internally futex_waitv() parses the array into struct futex_vectors, enqueues each on its bucket in a careful two-pass setup (futex_wait_multiple_setup() in waitwake.c) that pins all keys before sleeping to avoid losing a wakeup, then sleeps until any one is woken and returns its index.

Uncertain

Verify: that futex_waitv() was merged in Linux 5.16. Reason: the futex_waitv(2) man page’s HISTORY/VERSIONS section states “Linux 5.16,” which is authoritative, but I did not confirm the exact merge commit against the v5.16 release tag. To resolve: check git log --oneline v5.15..v5.16 -- kernel/futex/syscalls.c for the SYSCALL_DEFINE5(futex_waitv, ...) introduction, or the merge-window LWN summary for 5.16. uncertain

Uncertain

Verify: whether the rest of futex2 (e.g. separate futex_wake/futex_wait/futex_requeue futex2 syscalls and NUMA / variable-size support) is fully wired and usable as of v6.12, versus partially present. Reason: v6.12’s syscalls.c does define SYSCALL_DEFINE4(futex_wake), SYSCALL_DEFINE6(futex_wait), and SYSCALL_DEFINE4(futex_requeue) (futex2 forms), and futex.h carries FLAGS_NUMA, but futex_flags_valid() still rejects all sizes except 32-bit, so NUMA/size functionality may be ABI-reserved-but-not-active. To resolve: trace futex2_to_flags() / futex_flags_valid() consumers and the merge-window notes for 6.x where futex2 NUMA/sizes were enabled. uncertain

Failure Modes and Common Misunderstandings

“The futex word is the lock — the kernel reads it.” For plain futexes, false: the value is entirely opaque to the kernel, which only ever compares it to the val the caller passed. For PI and robust futexes it is true — those impose the TID/WAITERS/OWNER_DIED layout precisely because the kernel must interpret ownership. Conflating these is the most common futex misconception.

Lost wakeups from skipping the kernel re-read. A userspace lock implementation that calls FUTEX_WAIT without re-reading and re-checking the word after a failed CAS (or that passes a stale val) can sleep forever: the kernel’s uval == val check is what makes the wait safe, but only if val reflects the value the thread last observed. Drepper’s “Futexes Are Tricky” is the canonical catalogue of these userspace-side bugs (cited in Futex and OS Synchronization Primitives).

Stale EWOULDBLOCK/EAGAIN is normal, not an error. FUTEX_WAIT returning EAGAIN simply means the word changed before the kernel could enqueue the waiter — userspace must loop and retry, never treat it as fatal.

Private vs shared key mismatch. Using FUTEX_WAIT_PRIVATE on one side and a shared wait on the other (or vice versa) yields different keys for the same memory, so waiters and wakers never meet and the wakeup is silently lost. glibc is careful to use the private flag consistently for process-local mutexes.

Robust list corruption only leaks, never misfires. Because handle_futex_death() re-validates the owner TID against the dying task and bounds the walk at ROBUST_LIST_LIMIT, a buggy or malicious robust list cannot cause the kernel to wake the wrong waiter or set OWNER_DIED on a futex the task did not own — the worst outcome is that a genuinely-held lock is not cleaned up.

See Also

Graph View