futex: The Kernel Hop in Userspace Locks

Coverage: futex(FUTEX_WAIT/FUTEX_WAKE) → pthread_mutex internals → PI futex → robust futex → futex2 (6.x) Applicable to: Linux userspace, glibc pthread, any language runtime

Overview

futex (Fast Userspace muTEX) is the foundation for all userspace synchronization primitives on Linux. pthread_mutex, semaphore, barrier, Rust std::sync::Mutex, and Go runtime semaphores are all built on futex. Its core idea is: resolve contention in userspace when it's low (using atomic CAS), and only enter the kernel when you truly need to wait/wake.

futex System Call

#include <linux/futex.h>
#include <sys/syscall.h>

// futex(uaddr, futex_op, val, timeout, uaddr2, val3);

// Wait: if *uaddr == val → sleep and wait
syscall(SYS_futex, uaddr, FUTEX_WAIT, val, NULL, NULL, 0);

// Wake: wake up to val threads waiting on uaddr
syscall(SYS_futex, uaddr, FUTEX_WAKE, val, NULL, NULL, 0);

// Wait + Atomic Operation (FUTEX_OP):
//   if *uaddr2 == val3 → uaddr2 += op → then FUTEX_WAIT on uaddr

pthread_mutex Internals: The Classic futex Pattern

// glibc: nptl/pthread_mutex_lock.c (simplified)
// State: 0=idle, 1=locked (no waiters), 2=locked (has waiters)

void pthread_mutex_lock(pthread_mutex_t *m) {
    // Fast path: CAS to acquire lock (userspace, no syscall!)
    int old = 0;
    if (atomic_compare_exchange_strong(&m->__lock, &old, 1))
        return;  // Lock acquired! Zero syscalls

    // Slow path: someone holds the lock
    // Set lock to 2 (notify unlock: there are waiters, need futex_wake)
    if (atomic_exchange(&m->__lock, 2) == 0)
        return;  // Lock became idle during exchange → acquired

    // Really need to wait:
    while (atomic_exchange(&m->__lock, 2) != 0) {
        // FUTEX_WAIT_PRIVATE: within the same process → no need to look up mm_struct
        futex_wait(&m->__lock, 2, NULL);
    }
}

void pthread_mutex_unlock(pthread_mutex_t *m) {
    // If lock == 1 → set back to 0 (no waiters) → no need for futex_wake!
    if (atomic_exchange(&m->__lock, 0) == 1)
        return;  // Release successful! Zero syscalls

    // There are waiters (lock was 2) → need to wake up
    futex_wake(&m->__lock, 1);  // Wake 1 waiter
}

Analysis

No contention: lock + unlock takes 2 atomic CAS operations → ~20ns → zero syscalls!
Light contention: lock takes slow path, unlock has no waiters → 1 futex_wake per lock cycle
Heavy contention: lock is always waiting → 1 futex_wait + 1 futex_wake per lock cycle

This is why "locks are slow" actually means "lock contention is slow"

PI futex: Priority Inheritance

// Problem: High-priority thread waits for lock → low-priority holder is preempted by medium-priority thread
//          → Priority inversion (Mars Pathfinder 1997)

// PI futex: Holder temporarily boosted to the highest priority among waiters
pthread_mutexattr_setprotocol(&attr, PTHREAD_PRIO_INHERIT);
// → Kernel futex(PI) mechanism automatically manages priorities → suitable for real-time systems

Robust futex: Holder Crash Protection

// Problem: Thread crashes while holding lock → lock never released → other threads deadlock

// Robust mutex:
pthread_mutexattr_setrobust(&attr, PTHREAD_MUTEX_ROBUST);
pthread_mutex_lock(&m);
// If it returns EOWNERDEAD:
//   → Previous holder crashed → lock is in "dirty" state
//   → Need to check data structures and fix them → pthread_mutex_consistent(&m)

futex2: Next Generation (6.x)

// Current futex issues:
//   - Only 32-bit futex word (need extra lock for 64-bit)
//   - NUMA-unaware (wake might happen on CPU of remote NUMA node)
//   - No deadline-aware waiting

// futex2 (6.x, discussion since 5.x):
//   - Supports 8/16/32/64-bit futex words
//   - NUMA-aware wake (prioritize waking waiters on local node)
//   - FUTEX_WAIT_MULTIPLE (wait on multiple futexes simultaneously, similar to select)

References

• man: futex(2), pthread_mutex(3)
• Source code: kernel kernel/futex/, glibc nptl/pthread_mutex_lock.c
• LWN: "Futexes are tricky", "The futex2 proposal"
• Paper: "Fuss, Futexes and Furwocks: Fast Userlevel Locking in Linux" (2002)

Keywords: futex, FUTEX_WAIT, FUTEX_WAKE, pthread_mutex, CAS, PI futex, robust futex, futex2