futex(2): the syscall your mutex is too polite to mention
Published by RodHat
Every pthread_mutex_lock() call you’ve ever written either acquired the lock without touching the kernel, or it didn’t. If it didn’t, it called futex(2). That’s not an implementation detail you can ignore; it’s the design. The kernel provides two operations. Everything else is userspace code stacking on top.
futex stands for “fast userspace mutex.” The word “fast” is doing a lot of work there. The fast path is a compare-and-swap in userspace that the kernel never sees. The kernel only gets involved when the lock is contended, and even then, only to park and unpark threads.
The two operations
No glibc wrapper. You call the syscall directly:
#include <linux/futex.h>
#include <sys/syscall.h>
#include <stdint.h>
#include <unistd.h>
static inline long futex(uint32_t *uaddr, int op, uint32_t val,
const struct timespec *timeout,
uint32_t *uaddr2, uint32_t val3) {
return syscall(SYS_futex, uaddr, op, val, timeout, uaddr2, val3);
}FUTEX_WAIT: if the value at uaddr equals val, sleep until woken or timeout expires. The compare-and-sleep is atomic inside the kernel: it checks the value and queues the waiter in one step, so there’s no window where a wake could arrive before the sleep and be silently lost.
FUTEX_WAKE: wake up to val threads sleeping on uaddr. Returns the number actually woken.
That’s the core API. The rest of the operations (FUTEX_REQUEUE, FUTEX_LOCK_PI, FUTEX_WAIT_BITSET, etc.) are extensions, covered below.
A correct mutex in about 40 lines
The naive version uses two states: 0 for free, 1 for held. To acquire, CAS from 0 to 1. If that fails, call FUTEX_WAIT(1) to sleep until the value is no longer 1. To release, store 0 and call FUTEX_WAKE(1).
The problem: every release calls FUTEX_WAKE even when nobody is waiting. Every unlock is a syscall.
The correct design uses three states: 0 for free, 1 for held with no waiters, 2 for held with waiters. This is from Ulrich Drepper’s “Futexes Are Tricky,” first published in 2004, still the canonical reference for getting this right.
#include <stdatomic.h>
#include <linux/futex.h>
#include <sys/syscall.h>
#include <unistd.h>
#include <stdint.h>
typedef struct { _Atomic uint32_t state; } Mutex;
static inline long futex_wait(uint32_t *addr, uint32_t val) {
return syscall(SYS_futex, addr, FUTEX_WAIT | FUTEX_PRIVATE_FLAG,
val, NULL, NULL, 0);
}
static inline long futex_wake(uint32_t *addr, int n) {
return syscall(SYS_futex, addr, FUTEX_WAKE | FUTEX_PRIVATE_FLAG,
n, NULL, NULL, 0);
}
void mutex_lock(Mutex *m) {
uint32_t c;
/* Uncontended: 0 -> 1 without touching the kernel. */
c = 0;
if (atomic_compare_exchange_strong_explicit(
&m->state, &c, 1,
memory_order_acquire, memory_order_relaxed))
return;
/* Contended: mark as having waiters, then sleep. */
do {
/* If someone else already set state to 2, or we just did, sleep. */
if (c == 2 ||
atomic_compare_exchange_strong_explicit(
&m->state, &c, 2,
memory_order_acquire, memory_order_relaxed) ||
(c = 2))
futex_wait((uint32_t *)&m->state, 2);
/* Re-try fast path: 0 -> 2 (still marks waiters for next loser). */
c = 0;
} while (!atomic_compare_exchange_strong_explicit(
&m->state, &c, 2,
memory_order_acquire, memory_order_relaxed));
}
void mutex_unlock(Mutex *m) {
uint32_t prev = atomic_fetch_sub_explicit(
&m->state, 1, memory_order_release);
/* If prev was 1, nobody is waiting: store 0 and we're done. */
if (prev == 1)
return;
/* prev was 2: someone is waiting. Store 0, wake one thread. */
atomic_store_explicit(&m->state, 0, memory_order_release);
futex_wake((uint32_t *)&m->state, 1);
}FUTEX_PRIVATE_FLAG tells the kernel the futex is not shared across processes, which lets it skip a hash table lookup and use a per-mm queue instead. Always set this flag for in-process locks. Omit it only for futexes in shared memory across processes.
memory_order_acquire on the CAS and memory_order_release on unlock are load fences: they prevent the compiler and CPU from reordering accesses outside the critical section. Without them the mutex is syntactically correct and behaviorally wrong on any CPU with a weak memory model. x86 is strongly ordered so you might never see the bug there. ARM will teach you about it in production.
The loop in mutex_lock looks like a spin. It is not. The CAS attempts are bounded: if the CAS fails because the value is already 2, the code immediately calls futex_wait and parks. There’s at most a handful of CAS attempts before the thread sleeps.
FUTEX_REQUEUE: why cond broadcast doesn’t thundering-herd you to death
pthread_cond_broadcast wakes all threads waiting on a condition variable. If it called FUTEX_WAKE(INT_MAX) on the condvar futex, every woken thread would immediately race to acquire the mutex, and all but one would immediately park again. That’s a pile of useless context switches per broadcast.
FUTEX_REQUEUE avoids this. The operation: wake n threads and requeue the rest from one futex address to another. pthread wakes one thread (the one that will actually acquire the mutex) and requeues all the others to the mutex futex directly. The requeued threads are now sleeping in the mutex’s wait queue, where they’ll contend normally as the mutex is released and re-acquired one at a time.
futex(condvar, FUTEX_CMP_REQUEUE | FUTEX_PRIVATE_FLAG,
1, /* wake exactly one waiter */
INT_MAX, /* requeue the rest */
mutex, /* destination address */
expected_seq); /* check condvar sequence hasn't changed (race guard) */The FUTEX_CMP_REQUEUE variant checks expected_seq against the current value at condvar before operating. Without this check, a destroy-and-reinit race can cause the requeue to move waiters onto a completely unrelated futex. Use FUTEX_CMP_REQUEUE. Never use plain FUTEX_REQUEUE.
FUTEX_LOCK_PI: priority inheritance for realtime
The three-state mutex above doesn’t prevent priority inversion. If a high-priority thread is waiting on a lock held by a low-priority thread, and a medium-priority thread preempts the low-priority one, the high-priority thread is stuck while a lower-priority thread runs.
FUTEX_LOCK_PI and FUTEX_UNLOCK_PI fix this by storing the owner’s TID in the futex word (the low bit is the contention flag; the rest of the word is the TID). When a high-priority thread blocks, the kernel boosts the owner’s priority to match. This is how PTHREAD_PRIO_INHERIT mutexes are implemented.
The PI operations are strictly more expensive than the plain ones. They require kernel involvement even on the uncontended path (to store the owner TID). They exist for realtime scheduling classes where priority inversion is correctness-critical, not for general-purpose locking.
Reading futex waits in production
When a process is stuck, /proc/$pid/wchan tells you what kernel function it’s sleeping in. futex_wait_queue means it’s parked on a futex: a userspace lock is either deadlocked or waiting on something that isn’t making progress. That’s the first thing to check when reading a wedged process without a dashboard.
perf lock analyzes lock acquisition patterns: it records FUTEX_WAIT/WAKE events and attributes latency to specific call sites. The perf stat and record tip covers the workflow; when that shows high lock-wait time, perf lock report tells you which futex is responsible.
If you’re building a seccomp filter and your application uses any threading primitive, SYS_futex must be in the allowlist. Pull it and watch every pthread_mutex_lock SIGSYS on first contention. The seccomp-bpf tip covers this in the section on building allowlists from strace output.
FreeBSD
FreeBSD doesn’t have futex(2). It has _umtx_op(2), which is the same concept with a different interface. The operations map cleanly: UMTX_OP_WAIT_UINT is FUTEX_WAIT, UMTX_OP_WAKE is FUTEX_WAKE, UMTX_OP_MUTEX_WAIT and UMTX_OP_MUTEX_WAKE are the priority-inheritance variants.
The leading underscore is the kernel’s way of telling you this is not a stable API. libthr uses it internally for pthreads. You can too, but if you write code that calls _umtx_op directly, you own the FreeBSD-version compatibility problem. The pthread API above it is stable. For cross-platform code, stay at the pthread layer and use futex directly only when you’re writing something that’s Linux-only and needs to avoid any overhead the pthreads wrapper introduces.
The futex interface has been stable since Linux 2.6.0. The man page is futex(2). Drepper’s paper “Futexes Are Tricky” is worth reading in full; the current version is available from his site and the examples in it predate C11 atomics (it uses __sync_* GCC builtins), but the logic is correct and the analysis of the three-state design is still the best explanation of why it works.