Futexes, in depth: the compare-and-sleep contract, kernel wait queues, requeue, PI and robust futexes, futex2 and a futex semaphore

The contract: compare, then sleep

Everything follows from two operations. FUTEX_WAIT(addr, val) says: if the 32-bit word at addr still holds val, put me to sleep on that address; otherwise return EAGAIN immediately. FUTEX_WAKE(addr, n) says: wake up to n threads sleeping on that address and tell me how many were woken. The value never travels to the kernel in any other way; the kernel does not know what the word means. Whether 1 means locked, set, or has-permits is entirely your convention.

The crucial property is that the comparison and the enqueue happen atomically with respect to wakers. Without it you get the classic lost wakeup: a waiter reads the word, sees 0, decides to sleep; before it sleeps, a waker stores 1 and calls wake, finds nobody, and returns; the waiter then sleeps forever. With futexes the waiter passes the value it saw, and the kernel re-reads the word after it has made the waiter visible to wakers. Either the waker's store is already visible, so the kernel returns EAGAIN, or the waiter is already queued, so the wake finds it.

Three consequences shape every correct futex user. Waits return for reasons other than your wake: EAGAIN, EINTR from a signal, a timeout, or a plain spurious wakeup. So every wait sits in a loop that re-checks the user-space condition. Second, the word is always 32 bits on every architecture, even on 64-bit systems, so counters that need more bits must keep the waited-on part in a separate word. Third, the fast path never enters the kernel: if nobody waits, wake is unnecessary, and correct primitives track whether waiters might exist so they can skip it.

What the kernel keeps

Inside the kernel there is no per-futex object while nobody waits. A wait computes a key from the address. For a private futex, requested with FUTEX_PRIVATE_FLAG, the key is the process's address space plus the virtual address; this is cheap. For a shared futex, which may be mapped at different addresses in different processes, the kernel has to resolve the address to the underlying page or file offset, which costs a page-table walk and locking. The key is hashed into a table of buckets, each holding a spinlock and a list of waiters.

The wait path increments the bucket's waiter count with a full memory barrier, takes the bucket lock, reads the user word, and either returns EAGAIN or links itself into the list and sleeps. The wake path hashes the same key, checks the waiter count without the lock and returns at once if it is zero, and otherwise takes the lock, walks the list waking up to n entries whose key matches exactly. Unrelated futexes that hash to the same bucket share its lock, which is the source of the hash contention that newer kernels address with per-process private hash tables, controlled through prctl(PR_FUTEX_HASH, ...) as documented in the PR_FUTEX_HASH(2const) man page.

Building a primitive: a futex semaphore

Here is a counting semaphore built directly on the futex, with deadlines. The code follows the documented futex(2) contract but was not compiled or run for this article; treat it as a reviewed sketch and put it through ThreadSanitizer and a stress test before relying on it.

#define _GNU_SOURCE
#include <errno.h>
#include <limits.h>
#include <linux/futex.h>
#include <stdatomic.h>
#include <stdint.h>
#include <sys/syscall.h>
#include <time.h>
#include <unistd.h>

/* glibc has no futex() wrapper: call it through syscall(2). */
static long sys_futex(_Atomic uint32_t *uaddr, int op, uint32_t val,
                      const struct timespec *ts, uint32_t *uaddr2, uint32_t val3)
{
    return syscall(SYS_futex, uaddr, op, val, ts, uaddr2, val3);
}

/* Sleep while *addr == expected, until an ABSOLUTE CLOCK_MONOTONIC deadline
 * (NULL = forever). Returns 0 (woken, maybe spuriously), EAGAIN, EINTR or
 * ETIMEDOUT. Callers always re-check their own condition afterwards. */
static int futex_wait_until(_Atomic uint32_t *addr, uint32_t expected,
                            const struct timespec *deadline)
{
    long r = sys_futex(addr, FUTEX_WAIT_BITSET | FUTEX_PRIVATE_FLAG, expected,
                       deadline, NULL, FUTEX_BITSET_MATCH_ANY);
    return r == 0 ? 0 : errno;
}

static void futex_wake(_Atomic uint32_t *addr, int n)
{
    sys_futex(addr, FUTEX_WAKE | FUTEX_PRIVATE_FLAG, n, NULL, NULL, 0);
}

/* Counting semaphore: count is the futex word; waiters lets post skip the syscall. */
typedef struct { _Atomic uint32_t count, waiters; } fsem;

void fsem_post(fsem *s)
{
    atomic_fetch_add(&s->count, 1);              /* seq_cst on purpose */
    if (atomic_load(&s->waiters) > 0)
        futex_wake(&s->count, 1);
}

int fsem_wait(fsem *s, const struct timespec *deadline)
{
    for (;;) {
        uint32_t c = atomic_load_explicit(&s->count, memory_order_relaxed);
        while (c > 0)
            if (atomic_compare_exchange_weak_explicit(&s->count, &c, c - 1,
                    memory_order_acquire, memory_order_relaxed))
                return 0;
        atomic_fetch_add(&s->waiters, 1);
        int r = futex_wait_until(&s->count, 0, deadline);
        atomic_fetch_sub(&s->waiters, 1);
        if (r == ETIMEDOUT)
            return ETIMEDOUT;                    /* 0, EAGAIN, EINTR: loop */
    }
}

Walk the race that matters. A poster increments count and then reads waiters; a waiter increments waiters and then asks the kernel to sleep only if count is still 0. Both pairs are sequentially consistent, so in the single total order either the poster's read of waiters comes after the waiter's increment, and the wake is issued, or it comes before, in which case the count increment also precedes the waiter's increment and the kernel's re-read sees count above 0 and returns EAGAIN. Weaken either pair to acquire/release and this argument breaks: that is the store-buffer pattern, and it is the most common bug in hand-written futex code.

Beyond wait and wake

• Timeouts. Plain FUTEX_WAIT takes a relative timeout measured against CLOCK_MONOTONIC. FUTEX_WAIT_BITSET takes an absolute deadline, which is what you want inside a retry loop so spurious wakeups do not extend the total wait; add FUTEX_CLOCK_REALTIME for wall-clock deadlines.
• Bitsets. The bitset variants tag waiters with a 32-bit mask and wake only waiters whose mask intersects the waker's, letting one word serve several classes of waiter, for example readers and writers.
• Requeue. FUTEX_CMP_REQUEUE wakes some waiters and moves the rest onto a second address without waking them, if the first word still holds an expected value. It was designed so condition-variable broadcast would not wake every waiter only to have them pile onto the mutex. glibc's condition variable, rewritten for glibc 2.25, no longer uses it, but the operation remains.
• Priority inheritance. FUTEX_LOCK_PI, FUTEX_UNLOCK_PI and FUTEX_TRYLOCK_PI fix the word's meaning: it holds the owner's thread id, with FUTEX_WAITERS (0x80000000) set when someone sleeps. Because the kernel knows the owner, it can boost the owner's priority while a higher-priority thread waits; this is what PTHREAD_PRIO_INHERIT mutexes use.
• Robust futexes. Each thread registers a list of held locks with set_robust_list. If the thread dies holding one, the kernel sets FUTEX_OWNER_DIED (0x40000000) in the word and wakes a waiter, which surfaces as EOWNERDEAD from pthread and must be acknowledged with pthread_mutex_consistent.
• futex2. futex_waitv (Linux 5.16) waits on several futexes at once, added for Windows-style wait-for-multiple in Wine and Proton. Linux 6.7 added futex_wake, futex_wait and futex_requeue as separate system calls with a cleaner flags model; the classic multiplexed futex() call remains supported.

Futex equivalents on other systems

Other systems now offer the same deal. Windows has WaitOnAddress with WakeByAddressSingle and WakeByAddressAll, which accept 1, 2, 4 or 8 byte values within one process. macOS 14.4 and the matching iOS release added a public os_sync_wait_on_address with os_sync_wake_by_address_any and os_sync_wake_by_address_all, replacing reliance on the private __ulock_wait; Apple notes it has no priority-inversion avoidance and should back primitives without ownership, such as semaphores and condition variables, not locks. Portable C++20 code can use atomic::wait, notify_one and notify_all; for sizes the platform cannot wait on directly, standard libraries wait on a proxy word in a shared table, so do not assume one syscall per call.

Debugging and operations

Futex trouble shows up as threads blocked in the kernel. Use strace -f -e trace=futex on a test run to see waits, wakes and their return values; a storm of EAGAIN returns means waiters are racing a word that changes too often. In production prefer perf lock contention on recent perf, off-CPU flame graphs, or a bpftrace probe on syscalls:sys_enter_futex keyed by address to find the hot word. A wake returning a large count followed by a burst of re-waits is a thundering herd; wake one waiter, or requeue. For a wider methodology see lock contention diagnosis.

Failure modes

• Mixing private and shared operations on one word. They compute different keys, so a private wake never finds a shared waiter. In memory shared between processes, every operation must omit FUTEX_PRIVATE_FLAG.
• Waiting without a loop. Treating a return of 0 as proof the condition holds breaks on spurious wakeups and on wakes meant for reused memory.
• Relative timeouts in a retry loop. Each spurious wakeup restarts the clock and the caller waits far longer than asked; use absolute deadlines.
• Unconditional wake. Correct, but it puts a syscall on every unlock or post; track waiters, as the three-state mutex and the semaphore above do.
• Priority inversion. A plain futex lock cannot boost its owner; real-time threads need PI futexes, as covered in priority inversion.
• Wrapping 32-bit sequence words. A waiter that sleeps through exactly 2³² increments sees its old value and sleeps on; rare, but design for it in long-lived counters.

Trade-offs

What to do next

1. Run a contended program of yours under strace -f -e trace=futex and classify every return code you see.
2. Implement the semaphore above, then break it by weakening the seq_cst operations, and confirm a stress test finds the lost wakeup.
3. Rewrite one relative-timeout wait loop in your code to use an absolute deadline.
4. Audit shared-memory locks for private-flag mismatches and robust-list registration.
5. Read condition variables and atomic operations to connect the futex to the ordering guarantees above it.