Linux synchronization / futex internals

Linux futex wait/wake: atomic compare-and-sleep and the lost-wakeup trap

A futex is not a lock. It is a kernel-assisted way to put a thread to sleep while a user-space word still has a particular value. The essential guarantee is small, precise, and easy to misuse: check the word and enqueue the waiter as one atomic operation.

Linux deep dive · Concurrency and synchronization

The concrete problem

Suppose two threads share an integer called state. The consumer should sleep while state == 0; the producer sets it to 1 and wakes the consumer. A naïve implementation looks like this:

consumer:                  producer:
if (state == 0)            state = 1;
    sleep();               wake(consumer);

There is a race between the consumer's test and its sleep:

This is the lost-wakeup problem. A condition variable solves it by coupling a predicate check with a mutex, but a mutex and a condition variable are not always the lowest-level mechanism a runtime wants. Linux futexes let the uncontended path stay in user space while giving the contended path an atomic “check, enqueue, and sleep” operation in the kernel.

What a futex actually is

“Futex” means fast userspace mutex, but the Linux primitive is more general. A futex is normally a 32-bit aligned integer in shared memory plus a system call that operates on that integer. The kernel does not own the value and does not normally modify it for an ordinary futex. User space changes the word using atomic operations; the kernel only maintains a temporary wait queue for threads that cannot make progress.

The address is important because it identifies the wait location. For a private futex, the kernel can use the current process's address space as part of the key. For a process-shared futex, the key refers to the backing shared-memory object and page offset, so two processes mapping the same shared page can wait and wake each other.

The wait/wake protocol

The modern interface is exposed through futex(2). The two operations needed for a basic predicate are:

The canonical loop is therefore not “wait once”; it is:

for (;;) {
    if (predicate_is_true())
        break;

    int expected = 0;
    int rc = futex_wait(&word, expected);
    if (rc == -1 && errno != EAGAIN && errno != EINTR)
        fail();
    /* Any return means: inspect the predicate again. */
}

The producer updates the predicate before waking:

atomic_store_explicit(&word, 1, memory_order_release);
futex_wake(&word, 1);

The release store and an acquire load by the consumer create the visibility edge for the protected data. FUTEX_WAKE is a scheduling operation, not a substitute for C or C++ memory ordering.

Why the atomic check closes the race

Consider the critical interval again. The consumer reads the old value, then enters FUTEX_WAIT(addr, old). The kernel takes the futex hash-bucket lock, checks the user word, and enqueues the task only if the value still equals old. A producer's matching wake cannot be lost between that check and queue insertion: either the waiter's enqueue becomes visible first and the wake finds it, or the producer changes the word first and the wait returns EAGAIN without sleeping.

The kernel does not make the entire application condition atomic. It makes only this small relation atomic: “the observed futex value is still the expected value” versus “this task is now a waiter.” Your application must choose a predicate and update it with a matching memory-ordering protocol.

Inside the Linux implementation

The syscall entry is do_futex() in kernel/futex/syscalls.c. It decodes the operation, validates the user address, and dispatches to wait, wake, requeue, or priority-inheritance paths. Common wait setup eventually reaches code in kernel/futex/waitwake.c; wake and waiters are organized around hashed futex queues rather than one kernel object allocated for every futex word.

The hash table is an implementation tradeoff. It avoids allocating a permanent kernel object for every user-space word, but unrelated hot futexes can hash to the same bucket and contend on its lock. A collision does not make wakeups incorrect—the key comparison still distinguishes waiters—but it can add kernel lock contention and latency.

How pthread mutexes and condition variables use it

Most applications should use pthread_mutex_t and pthread_cond_t, not issue raw futex syscalls. The value of understanding futexes is that it explains the fast and slow paths underneath those abstractions.

A normal mutex typically attempts an atomic user-space state transition first. If the transition succeeds, no syscall occurs. If another thread owns it, the implementation records contention and waits on a futex word. Unlocking changes the state and performs a wake only when contention is possible.

A condition variable has a sequence or generation value. The waiter holds the associated mutex while checking the application predicate, records the sequence it observed, then atomically releases the mutex as it begins waiting. The signaler changes the sequence and wakes waiters. On return, the waiter reacquires the mutex and checks the predicate again. This is why the POSIX rule is “wait in a loop,” even when the implementation underneath is carefully engineered.

Failure modes and tradeoffs

There is a deliberate asymmetry: a wake can be cheap when nobody waits, while a wait can be cheap when the value changed before the syscall. This is the “fast userspace” part. Under contention, the kernel becomes a scheduler and queue manager, so the slow path is not free.

Security and robustness

A futex address is supplied by user space, so the kernel must safely read the user word, canonicalize its key, and handle page faults or unmapped memory without corrupting kernel state. Historically, futex bugs have been security-sensitive because the primitive crosses the user/kernel boundary while coordinating task state and shared memory.

At the application level, untrusted code can cause contention, deliberately hold a shared lock, or create a wake storm. Do not put a process-shared futex in memory whose lifetime is shorter than its waiters' lifetime. Destroying or unmapping synchronization storage while another thread can still wait on it is a lifetime bug, not a futex feature.

Priority inheritance, robust mutexes, and process-shared synchronization each add metadata and failure cases. Robust mutexes can report that an owner died; they do not magically repair protected application state. Treat recovery as a transaction problem: validate the state, repair or discard it, and mark the lock consistent only after recovery.

Debugging method

1. Write down the predicate, its owner, and the state transition that should make it true. If there is no explicit predicate, the protocol is already difficult to review.
2. Check memory ordering separately from scheduling. A wake can make a thread runnable without making non-atomic data safely visible.
3. Trace syscalls with timestamps. Repeated FUTEX_WAIT returning EAGAIN means a race was handled correctly; repeated waits with no matching wake suggests a protocol or lifetime bug.
4. Inspect wait-channel stacks with strace, perf, or scheduler tracing. A task blocked in futex_wait_queue is evidence of waiting, not evidence that the predicate is false.
5. Look for thundering herds: one wake followed by many runnable threads and only one successful lock acquisition.

# Linux: trace futex operations for a process
strace -f -tt -e trace=futex -p "$PID"

# Find threads sleeping in a futex wait channel.
for task in /proc/"$PID"/task/*; do
  printf '%s ' "$task"
  sed -n 's/^wchan:[[:space:]]*//p' "$task/../wchan" 2>/dev/null
done

# Show scheduler and futex-related tracepoints when available.
perf trace -p "$PID" -e futex:* 2>/dev/null || true

Tracepoint names and permissions vary by kernel. If perf trace cannot attach, start with strace, then inspect the process's source-level predicate and add a sequence counter around every state transition. The most useful log is usually “predicate before wait, expected word, futex return/errno, predicate after return,” not a generic “woke up” message.

Compact reproducible lab

Goal

Observe the two outcomes guaranteed by FUTEX_WAIT: a waiter sleeps when the word still equals the expected value, but returns immediately with EAGAIN when a producer changed the word first.

Prerequisites

A Linux host or VM with GCC, Python 3, and strace if you want syscall evidence. The program uses the raw Linux syscall, so it is intentionally not portable to macOS or other Unix systems.

Exact commands

cat > /tmp/futex-lab.c <<'C'
#define _GNU_SOURCE
#include <errno.h>
#include <linux/futex.h>
#include <stdatomic.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <sys/syscall.h>
#include <pthread.h>
#include <unistd.h>

static _Atomic int word = 0;

static int futex_wait(_Atomic int *p, int expected) {
    return syscall(SYS_futex, p, FUTEX_WAIT | FUTEX_PRIVATE_FLAG,
                   expected, NULL, NULL, 0);
}

static int futex_wake(_Atomic int *p, int count) {
    return syscall(SYS_futex, p, FUTEX_WAKE | FUTEX_PRIVATE_FLAG,
                   count, NULL, NULL, 0);
}

static void *waker(void *unused) {
    (void)unused;
    usleep(200000);
    atomic_store_explicit(&word, 1, memory_order_release);
    printf("waker: woke=%d\n", futex_wake(&word, 1));
    return NULL;
}

int main(void) {
    puts("case 1: value changes before wait");
    atomic_store_explicit(&word, 1, memory_order_release);
    errno = 0;
    int rc = futex_wait(&word, 0);
    printf("return=%d errno=%d (%s) word=%d\n", rc, errno, strerror(errno),
           atomic_load_explicit(&word, memory_order_acquire));

    puts("case 2: wait, then wake from another thread");
    atomic_store_explicit(&word, 0, memory_order_release);
    pthread_t thread;
    pthread_create(&thread, NULL, waker, NULL);
    errno = 0;
    rc = futex_wait(&word, 0);
    printf("waiter: return=%d errno=%d (%s) word=%d\n", rc, errno, strerror(errno),
           atomic_load_explicit(&word, memory_order_acquire));
    pthread_join(thread, NULL);
    return 0;
}
C

gcc -O2 -Wall -pthread /tmp/futex-lab.c -o /tmp/futex-lab
/tmp/futex-lab

# Optional: observe the two futex syscalls and their timing.
strace -f -tt -e trace=futex /tmp/futex-lab

The first wait should return -1 with errno=EAGAIN because the kernel observed word != 0 at the wait boundary. In the second case, the main thread sleeps in the kernel; the waker thread stores 1 and wakes one waiter, after which the main thread returns. The futex is marked private because both threads share one process address space.

Environment result: this run is on macOS, where linux/futex.h, SYS_futex, and Linux futex behavior are unavailable, so the live lab was not executed here. Use a Linux VM or container for the exact commands. The HTML structure and link checks were run locally.

Revealing variations

Change the first expected value from 0 to 1. The call will actually sleep, demonstrating that the comparison is a gate, not a notification read. Then change futex_wake(&word, 1) to futex_wake(&word, 0); the waiter will not be released, demonstrating that changing the word and waking waiters are separate application actions.

Production example: a thread pool handoff

A bounded work queue often has a count or sequence word. Producers append work under a short critical section, increment the sequence, and wake one sleeping worker. Workers lock the queue, remove work if available, and otherwise record the sequence they observed before waiting. When they wake, they reacquire the queue lock and test the queue again.

The sequence word matters when multiple producers and consumers race. It prevents a worker from sleeping on an old observation, while the queue predicate prevents a spurious or stolen wake from becoming a false “work exists” assumption. Under sustained overload, futex correctness will not rescue the queue: measure queue depth, runnable threads, lock hold time, and wakeups per item.

Primary sources

• Linux futex(2) manual
• Linux kernel documentation: futexes and RT-mutexes
• Linux source: futex syscall dispatch
• Linux source: futex wait/wake core
• Linux source: futex keys, queues, and wake paths
• glibc source: futex internal wrappers
• Futexes Are Tricky (Franke, Russel, Kirkwood, 2002)

Remember: the futex word describes a predicate; FUTEX_WAIT atomically validates the old observation before sleeping; FUTEX_WAKE only makes waiters runnable. Correctness lives in the loop, the memory ordering, and the lifetime of the shared word.