Futex
lastmod 2025-08-22created 2025-08-222 edits
In computer science, a futex (fast userspace mutex) is a system call provided by the Linux kernel that developers can use to implement basic locking, or as a building block for higher-level locking abstractions such as semaphores, POSIX mutexes, and condition variables.
Operations
The basic operations of a futex are based on only two specific operations, WAIT and WAKE. Some futex implementations that depend only on specific versions of the Linux kernel have a few more operations for specific purposes.[1]
- WAIT (addr, val)
- Checks whether the value stored at address addr is val, and if so, puts the current thread to sleep.
- WAKE (addr, val)
- Wakes val by the number of threads waiting at address addr.
About
Futexes are a core component of efficient synchronization in modern parallel programming, outperforming the older System V-based locks
Futexes separate lock acquisition from the wait/wake functionality, a structure that reduces unnecessary system calls and overhead
Introduction
- Phil Eaton started a book club for 'The Art of Multiprocessor Programming, 2nd Edition'
- The book is considered an authoritative textbook in parallel programming, but the author points out its lack of practicality
- In particular, the author criticizes it for not covering the futex, a core synchronization technique, despite targeting fourth-year undergraduates and graduate students
What is a futex – and why it matters
- Futex is short for "fast user space mutex"; it is really less a mutex than an OS-supported synchronization primitive for building modern locks
- In the past, most locks were implemented on top of System V IPC semaphores, which limited efficiency and scalability
- When futexes were introduced in Linux in 2002, they were 20–120 times faster than System V locks in an environment with 1000 concurrent tasks
- Other OSes such as Windows (2012) and macOS (2016) adopted similar mechanisms
- Locks in widely used system libraries today, such as pthreads, use futexes
How futexes work and what sets them apart
- Traditional semaphores combined locking and waiting, but futexes separate lock acquisition from waiting/waking
- This reduces unnecessary delays and system calls, and when releasing a lock there is no need to enter the kernel if it is certain there are no waiting threads
- The futex wait call "waits only if the value at a specific memory address is in the expected state", and also supports timeouts
- The futex wake call wakes the desired number of threads from the internal wait list associated with a specific memory address
- It requires verifying the actual value at the memory address, preventing unnecessary waits when the state has already changed
Using futexes in practice – implementing it yourself
- Since the futex is a low-level primitive, atomic types are used to account for memory-ordering issues in the compiler and hardware
- On Linux the futex system call must be invoked directly via syscall, while on MacOS the __ulock interface is used (an easier API was added recently)
- By default, a futex wait returns 0 on success and an error code (timeout, etc.) on failure
- Core futex-based operations:
- h4x0r_futex_wait_timespec() : waits if the expected value matches; a timeout can be applied
- h4x0r_futex_wake() : wakes one or all waiters
Practical examples of mutex/spinlock/recursive lock implementations
Spinlock
- The simplest form of lock, operating on just a single bit (atomic_fetch_or)
- Loops forever ("spins") until it gets the lock, but has structural problems under high contention such as wasted CPU, incorrect releases, and the risk of deadlock on recursive calls
Hybrid mutex ('unsafe' mutex)
- Usually tries as a spinlock first, then switches to a futex after a certain number of failures for efficient blocking
- Unnecessary system calls are avoided when there are no waiters, and wake system calls for waiters can be minimized
- Lacks strict ownership verification and recursion handling, hence the name "unsafe"
Waiter-counting mutex
- One bit is used for the lock state and the rest for counting waiters, to reduce unnecessary wake system calls
- Still no ownership or recursion handling
Mutex with ownership management
- Clearly tracks the lock owner and state through a pthread_t value, catching problems with incorrect unlocks or recursive use
- Lock acquisition, release, and waiter management are all strictly controlled with atomic operations
Recursive lock
- Adds a per-thread nesting count (depth) counter so the same thread can acquire the lock in a nested fashion
- On unlock the depth is decremented; when it reaches 0, the actual unlock and wake take place
- Each operation is implemented with atomic operations and strict ownership checks
Full code example
#include <stdint.h> // For uint32_t
#include <stdbool.h> // For bool
#include <time.h> // For struct timespec
#include <stdatomic.h> // For atomic_fetch_or, atomic_fetch_add, ...
#include <pthread.h> // For pthread_self
#include <stdlib.h> // For abort
#include <stdio.h> // For printf
#include <errno.h> // For ETIMEDOUT
#include <limits.h>
typedef _Atomic(uint32_t) h4x0r_futex_t;
#if defined(__linux__)
#if !defined(_GNU_SOURCE)
#define _GNU_SOURCE
#endif
#include <linux/futex.h>
#include <sys/syscall.h>
#include <unistd.h>
static inline int
h4x0r_futex_wait_timespec(h4x0r_futex_t *futex,
uint32_t expected,
struct timespec *timeout_ptr)
{
int err = syscall(SYS_futex,
futex,
FUTEX_WAIT_PRIVATE,
expected,
timeout_ptr,
NULL,
0);
if (err == -1) {
return errno;
}
return 0;
}
static inline int
h4x0r_futex_wake(h4x0r_futex_t *futex, bool all)
{
uint32_t n = all ? INT_MAX : 1;
return syscall(SYS_futex,
futex,
FUTEX_WAKE_PRIVATE,
n,
NULL,
NULL,
0);
}
#elif defined(__APPLE__)
// These were never exposed in any headers.
extern int __ulock_wait2(uint32_t, void *, uint64_t, uint64_t, uint64_t);
extern int __ulock_wake(uint32_t, void *, uint64_t);
#define H4X0R_NSEC_PER_SEC 1000000000
#define H4X0R_LOCK_COMPARE_AND_WAIT 1
#define H4X0R_LOCK_WAKE_ALL 0x00000100
#define H4X0R_LOCK_WAKE_THREAD 0x00000200
#define H4X0R_WAKE_ALL (H4X0R_LOCK_COMPARE_AND_WAIT | H4X0R_LOCK_WAKE_ALL)
#define H4X0R_WAKE_THREAD (H4X0R_LOCK_COMPARE_AND_WAIT | H4X0R_LOCK_WAKE_THREAD)
static inline int
h4x0r_futex_wait_timespec(h4x0r_futex_t *futex,
uint32_t expected,
struct timespec *timeout)
{
uint64_t timeout_ns = 0;
if (timeout) {
timeout_ns = timeout->tv_nsec + timeout->tv_sec * H4X0R_NSEC_PER_SEC;
}
return __ulock_wait2(H4X0R_LOCK_COMPARE_AND_WAIT,
futex,
(uint64_t)expected,
timeout_ns,
0);
}
static inline int
h4x0r_futex_wake(h4x0r_futex_t *futex, bool all)
{
return __ulock_wake(all ? H4X0R_WAKE_ALL : H4X0R_WAKE_THREAD,
futex,
0ULL);
}
#endif
#define H4X0R_SPIN_COUNT 16
typedef h4x0r_futex_t h4x0r_mutex_unsafe_t;
static inline void
h4x0r_mutex_unsafe_init(h4x0r_mutex_unsafe_t *lock)
{
atomic_store(lock, 0);
}
static inline void
h4x0r_mutex_unsafe_acquire(h4x0r_mutex_unsafe_t *lock)
{
for (uint32_t i = 0; i < H4X0R_SPIN_COUNT; i++) {
if (!atomic_fetch_or(lock, 1)) {
return;
}
}
while (true) {
h4x0r_futex_wait_timespec((h4x0r_futex_t *)lock, 1, NULL);
if (!atomic_fetch_or(lock, 1)) {
return;
}
}
}
static inline void
h4x0r_mutex_unsafe_release(h4x0r_mutex_unsafe_t *lock)
{
atomic_store(lock, 0);
h4x0r_futex_wake(lock, false);
}
// First one is OR'd in, the second is AND'd in.
#define H4X0R_MUTEX_LOCK_ON (1 << 31)
#define H4X0R_MUTEX_LOCK_OFF ~(H4X0R_MUTEX_LOCK_ON)
static inline bool
h4x0r_mutex_value_is_unlocked(uint32_t value)
{
return !(value & H4X0R_MUTEX_LOCK_ON);
}
static inline bool
h4x0r_mutex_unsafe2_try_lock(h4x0r_mutex_unsafe_t *lock)
{
uint32_t value = atomic_fetch_or(lock, H4X0R_MUTEX_LOCK_ON);
return h4x0r_mutex_value_is_unlocked(value);
}
static inline uint32_t
h4x0r_mutex_unsafe2_add_waiter(h4x0r_mutex_unsafe_t *lock)
{
return 1 + atomic_fetch_add(lock, 1);
}
static inline void
h4x0r_mutex_unsafe2_acquire(h4x0r_mutex_unsafe_t *lock)
{
uint32_t expected;
for (uint32_t i = 0; i < H4X0R_SPIN_COUNT; i++) {
if (h4x0r_mutex_unsafe2_try_lock(lock)) {
return;
}
}
expected = h4x0r_mutex_unsafe2_add_waiter(lock);
while (true) {
if (h4x0r_mutex_value_is_unlocked(expected)
&& h4x0r_mutex_unsafe2_try_lock(lock)) {
atomic_fetch_add(lock, -1);
return;
}
h4x0r_futex_wait_timespec((h4x0r_futex_t *)lock, expected, NULL);
expected = atomic_load(lock);
}
}
static inline void
h4x0r_mutex_unsafe2_release(h4x0r_mutex_unsafe_t *lock)
{
uint32_t waiters = atomic_fetch_and(lock, H4X0R_MUTEX_LOCK_OFF);
if (waiters != H4X0R_MUTEX_LOCK_ON) {
h4x0r_futex_wake(lock, false);
}
}
typedef struct {
h4x0r_futex_t futex;
_Atomic(pthread_t) owner;
_Atomic(bool) owned;
} h4x0r_mutex_t;
static inline void
h4x0r_mutex_init(h4x0r_mutex_t *mutex)
{
*mutex = (h4x0r_mutex_t) {
.futex = 0,
.owned = false,
};
}
static inline bool
h4x0r_mutex_try_lock(h4x0r_mutex_t *lock)
{
uint32_t value = atomic_fetch_or(&lock->futex, H4X0R_MUTEX_LOCK_ON);
pthread_t self;
if (!h4x0r_mutex_value_is_unlocked(value)) {
return false;
}
// If what we read when we wrote says "unlocked", then we
// successfully acquired the lock.
self = pthread_self();
if (atomic_load(&lock->owned)) {
if (pthread_equal(self, atomic_load(&lock->owner))) {
fprintf(stderr, "Mutex was used recursively.\n");
}
else {
fprintf(stderr, "Acquired a lock owner didn't properly yield.\n");
}
abort();
}
// We have the lock, so we make it known.
atomic_store(&lock->owned, true);
atomic_store(&lock->owner, self);
return true;
}
static inline uint32_t
h4x0r_mutex_add_waiter(h4x0r_mutex_t *lock)
{
return 1 + atomic_fetch_add(&lock->futex, 1);
}
static inline bool
h4x0r_mutex_acquire(h4x0r_mutex_t *lock, struct timespec *timeout)
{
uint32_t expected;
for (uint32_t i = 0; i < H4X0R_SPIN_COUNT; i++) {
if (h4x0r_mutex_try_lock(lock)) {
return true;
}
}
expected = h4x0r_mutex_add_waiter(lock);
while (true) {
if (h4x0r_mutex_value_is_unlocked(expected)
&& h4x0r_mutex_try_lock(lock)) {
atomic_fetch_add(&lock->futex, -1);
return true;
}
int err = h4x0r_futex_wait_timespec((h4x0r_futex_t *)&lock->futex,
expected,
timeout);
if (err == ETIMEDOUT) {
return false;
}
expected = atomic_load(&lock->futex);
}
}
static inline void
h4x0r_mutex_release(h4x0r_mutex_t *lock)
{
if (!atomic_load(&lock->owned)
|| !pthread_equal(pthread_self(), atomic_load(&lock->owner))) {
fprintf(stderr, "Thread unlocked a mutex it doesn't own.\n");
abort();
}
atomic_store(&lock->owned, true);
uint32_t waiters = atomic_fetch_and(&lock->futex, H4X0R_MUTEX_LOCK_OFF);
if (waiters != H4X0R_MUTEX_LOCK_ON) {
h4x0r_futex_wake(&lock->futex, false);
}
}
typedef struct {
h4x0r_futex_t futex;
_Atomic(uint32_t) depth;
_Atomic(pthread_t) owner;
_Atomic(bool) owned;
} h4x0r_mutex_recursive_t;
static inline void
h4x0r_mutex_recursive_init(h4x0r_mutex_recursive_t *mutex)
{
*mutex = (h4x0r_mutex_recursive_t) {
.futex = 0,
.depth = 0,
.owned = false,
};
}
static inline bool
h4x0r_mutex_recursive_check_ownership(h4x0r_mutex_recursive_t *lock,
pthread_t self)
{
if (!atomic_load(&lock->owned)) {
return false;
}
if (pthread_equal(self, atomic_load(&lock->owner))) {
atomic_fetch_add(&lock->depth, 1);
return true;
}
return false;
}
// Called from our internal try-lock call, once it knows we definitely
// just acquired ownership.
static inline void
h4x0r_mutex_recursive_new_ownership(h4x0r_mutex_recursive_t *lock,
pthread_t self)
{
if (atomic_load(&lock->owned)) {
fprintf(stderr, "Acquired a lock owner didn't properly yield.\n");
abort();
}
atomic_store(&lock->owned, true);
atomic_store(&lock->owner, self);
atomic_store(&lock->depth, 1);
}
// Called when definitely holding the lock.
// Returns true if we are nested, and false if we aren't (proper unlock).
static inline bool
h4x0r_mutex_recursive_nesting_check(h4x0r_mutex_recursive_t *lock)
{
if (!pthread_equal(pthread_self(), atomic_load(&lock->owner))) {
fprintf(stderr, "Thread is trying to unlock a lock it doesn't own.\n");
abort();
}
if (atomic_fetch_add(&lock->depth, -1) > 1) {
return true;
}
atomic_store(&lock->owned, false);
return false;
}
static inline bool
h4x0r_mutex_recursive_internal_try_lock(h4x0r_mutex_recursive_t *lock, pthread_t self)
{
uint32_t value = atomic_fetch_or(&lock->futex, H4X0R_MUTEX_LOCK_ON);
bool result = h4x0r_mutex_value_is_unlocked(value);
if (result) {
h4x0r_mutex_recursive_new_ownership(lock, self);
}
return result;
}
static inline uint32_t
h4x0r_mutex_recursive_add_waiter(h4x0r_mutex_recursive_t *lock)
{
return 1 + atomic_fetch_add(&lock->futex, 1);
}
static inline bool
h4x0r_mutex_recursive_acquire(h4x0r_mutex_recursive_t *lock,
struct timespec *timeout)
{
uint32_t expected;
pthread_t self = pthread_self();
if (h4x0r_mutex_recursive_check_ownership(lock, self)) {
// We already owned the lock, and incremented the nesting count.
return true;
}
for (uint32_t i = 0; i < H4X0R_SPIN_COUNT; i++) {
if (h4x0r_mutex_recursive_internal_try_lock(lock, self)) {
// internal_try_lock will set up ownership.
return true;
}
}
expected = h4x0r_mutex_recursive_add_waiter(lock);
while (true) {
if (h4x0r_mutex_value_is_unlocked(expected)
&& h4x0r_mutex_recursive_internal_try_lock(lock, self)) {
atomic_fetch_add(&lock->futex, -1);
return true;
}
int err = h4x0r_futex_wait_timespec((h4x0r_futex_t *)&lock->futex,
expected,
timeout);
if (err == ETIMEDOUT) {
return false;
}
expected = atomic_load(&lock->futex);
}
}
static inline bool
h4x0r_mutex_recursive_try_lock(h4x0r_mutex_recursive_t *lock)
{
pthread_t self = pthread_self();
if (h4x0r_mutex_recursive_check_ownership(lock, self)) {
// We already owned the lock, and incremented the nesting count.
return true;
}
return h4x0r_mutex_recursive_internal_try_lock(lock, self);
}
static inline void
h4x0r_mutex_recursive_release(h4x0r_mutex_recursive_t *lock)
{
if (h4x0r_mutex_recursive_nesting_check(lock)) {
// We were nested, and the decrement happened, so we're done.
return;
}
uint32_t waiters = atomic_fetch_and(&lock->futex, H4X0R_MUTEX_LOCK_OFF);
if (waiters != H4X0R_MUTEX_LOCK_ON) {
h4x0r_futex_wake(&lock->futex, false);
}
}
Remaining challenges and real-world engineering
- When the thread holding a lock terminates abnormally or dies, extra management is needed, such as a separate management list for locks and exit callbacks
- Mutexes shared between processes also need additional consideration for managing state changes
- POSIX RW locks do not define recursive nesting behavior and it differs between implementations, so safety is hard to guarantee in practice
- The author criticizes the book for not including the concurrency issues that really matter in practice (futexes, recursive locks, async runtimes, etc.) in its curriculum
Conclusion
- 'The Art of Multiprocessor Programming' leans toward a historical or theoretical perspective and fails to properly cover important modern practical knowledge of parallel programming
- Not properly covering core synchronization components such as futexes that actually run in systems may do real harm to future students
- The author stresses the need to reflect up-to-date concepts and supplement practical content