Futex-based mutex

Deep dive

How it works

In: a 32-bit word in memory · Out: mutual exclusion that sleeps only under contention · State: the word (0 unlocked, 1 locked, 2 locked with waiters) · Cost: uncontended lock+unlock 2 atomic RMWs, no syscall; contended adds one wait and one wake syscall

state: 0 = unlocked   1 = locked, no waiters   2 = locked, maybe waiters

lock:   CAS 0->1 ok? done.                      unlock: swap(0) == 2 ? FUTEX_WAKE(1)
        else spin while state == 1 (bounded)
        loop { if swap(2) == 0: done (we own it, conservatively marked contended)
               FUTEX_WAIT(state, 2) }          // sleeps only if state is still 2

1. Fast path: compare_exchange(0, 1, Acquire).
2. Contended: spin up to ~100 iterations while the state is 1 (owner likely about to release), retry the CAS.
3. Swap in 2 so the eventual unlocker knows to wake someone. If the swap returned 0 the lock was free and is now ours (state 2 may cause one unnecessary wake later; that is the accepted cost).
4. Otherwise FUTEX_WAIT(&state, 2): the kernel re-checks state == 2 under its hash-bucket lock and sleeps; any change before that returns EAGAIN immediately.
5. Unlock: swap(0, Release); if the old value was 2, FUTEX_WAKE(&state, 1).

Code

// Linux only; needs the `libc` crate.
use std::cell::UnsafeCell;
use std::ops::{Deref, DerefMut};
use std::sync::atomic::{AtomicU32, Ordering::{Acquire, Relaxed, Release}};

fn futex_wait(a: &AtomicU32, expected: u32) {
    unsafe {
        libc::syscall(libc::SYS_futex, a.as_ptr(), libc::FUTEX_WAIT | libc::FUTEX_PRIVATE_FLAG,
                      expected, std::ptr::null::<libc::timespec>());
    } // spurious wakeups and EAGAIN are fine: the caller loops
}
fn futex_wake_one(a: &AtomicU32) {
    unsafe { libc::syscall(libc::SYS_futex, a.as_ptr(), libc::FUTEX_WAKE | libc::FUTEX_PRIVATE_FLAG, 1); }
}

pub struct Mutex<T> { state: AtomicU32, value: UnsafeCell<T> }
unsafe impl<T: Send> Sync for Mutex<T> {}

pub struct Guard<'a, T> { m: &'a Mutex<T> }

impl<T> Mutex<T> {
    pub const fn new(v: T) -> Self { Mutex { state: AtomicU32::new(0), value: UnsafeCell::new(v) } }

    pub fn lock(&self) -> Guard<'_, T> {
        if self.state.compare_exchange(0, 1, Acquire, Relaxed).is_err() { self.lock_contended(); }
        Guard { m: self }
    }

    #[cold]
    fn lock_contended(&self) {
        let mut spins = 0;
        while self.state.load(Relaxed) == 1 && spins < 100 { // owner running, no waiters yet
            std::hint::spin_loop();
            spins += 1;
        }
        if self.state.compare_exchange(0, 1, Acquire, Relaxed).is_ok() { return; }
        while self.state.swap(2, Acquire) != 0 {
            futex_wait(&self.state, 2);
        }
    }
}

impl<T> Drop for Guard<'_, T> {
    fn drop(&mut self) {
        if self.m.state.swap(0, Release) == 2 { futex_wake_one(&self.m.state); }
    }
}
impl<T> Deref for Guard<'_, T> { type Target = T; fn deref(&self) -> &T { unsafe { &*self.m.value.get() } } }
impl<T> DerefMut for Guard<'_, T> { fn deref_mut(&mut self) -> &mut T { unsafe { &mut *self.m.value.get() } } }

Complexity and constants

• Fast path: 2 locked RMWs (order of 20 cycles each on x86) plus the cache miss if another core touched the lock last (order of 50-100 ns).
• Contended path per handoff: wake syscall + scheduler wakeup + migration, order of µs. A convoy of sleeping waiters caps throughput at roughly 10^5-10^6 handoffs/s.
• Kernel side: private futexes hash (mm, address) into a global table of buckets, each with a spinlock and wait list.
• Memory: 4 bytes. Glibc's pthread_mutex_t is 40 bytes (type, owner, count, etc.).

Efficiency

• Cost: uncontended lock+unlock is order of 10-25 ns (two locked RMWs, plus a line transfer of order 50-100 ns if another core held it last). A futex syscall is order of 0.1-1 µs and wake-to-run order of 2-10 µs, so a convoy of sleepers caps handoffs at roughly 10^5-10^6 per second. Memory: 4 bytes. Bound: cache-line transfer when uncontended, scheduler latency when contended.
• Levers:
  • three-state word (0/1/2) — no wake syscall when there are no waiters (Drepper, Futexes Are Tricky) — every unlock
  • bounded spinning before sleeping — skips a context switch when the owner releases soon (order of 100 iterations here) — short critical sections
  • FUTEX_PRIVATE_FLAG — skips the shared-mapping lookup (futex(2)) — locks not shared across processes
  • FUTEX_CMP_REQUEUE for condvars — avoids thundering herds (futex(2)) — condvar broadcast
  • one-byte lock word with a global parking table — 1 byte per lock instead of 4-40 (WebKit, parking_lot) — millions of locks
• Naive → standard → state of the art:
  • spin lock · burns a core while waiting, collapses when the owner is preempted
  • always-syscall mutex · order of 0.1-1 µs per lock and unlock even uncontended
  • futex word with spin-then-park · order of 10-25 ns uncontended, a syscall only under contention

Implementation notes

• FUTEX_PRIVATE_FLAG skips the shared-mapping lookup; use it unless the lock lives in memory shared between processes.
• Spin with spin_loop() (pause on x86, whose latency ranges from about 10 to about 140 cycles across Intel generations; yield/isb on ARM). Bound spinning by count or time, not by a fixed cycle assumption; the owner may be preempted.
• Unfair by design: an unlocking thread can re-lock before the woken waiter runs ("barging"). Great throughput, possible starvation. parking_lot adds "eventual fairness": a forced direct handoff about every 0.5 ms.
• Condvars on futexes: wait on a sequence counter; notify increments and wakes. Requeue (FUTEX_CMP_REQUEUE) moves waiters from the condvar to the mutex to avoid thundering herds.
• Priority inheritance (FUTEX_LOCK_PI) for real-time threads; robust futexes for process-shared locks whose owner may die.
• futex_waitv (Linux 5.16) waits on several futexes at once (used by Wine/Proton).
• Keep the lock word on its own cache line if other hot data is written nearby (false sharing).

Pitfalls

• Two-state lock that always calls FUTEX_WAKE on unlock: a syscall per unlock even with no waiters.
• Unlock by store(0) then checking a separate waiter count non-atomically: lost wakeups (Drepper's paper walks through these bugs).
• Not looping after FUTEX_WAIT: spurious wakeups and EAGAIN are normal.
• Spinning without a bound, or spinning when the state is 2 (others are already sleeping, the owner may be descheduled).
• Holding a lock across blocking I/O or await points.
• Measuring "mutex is slow" when the real cost is the contended cache line; a lock-free structure contending on one line is not faster.

Variants and alternatives

In production

OS kernels: Linux mutex (optimistic spinning + wait list) and glibc NPTL pthread_mutex (futex). Language runtimes: Rust std::sync::Mutex/Condvar/RwLock on Linux, Go (futexsleep/futexwakeup in lock_futex.go), and the Rust crate parking_lot. Browsers: WebKit WTF::Lock (one byte, parking-lot based).

Implementations

Sources

• Hubertus Franke, Rusty Russell, Matthew Kirkwood, Fuss, Futexes and Furwocks: Fast Userlevel Locking in Linux, Ottawa Linux Symposium 2002. paper
• Ulrich Drepper, Futexes Are Tricky, Red Hat, 2004 (revised 2011). paper
• Mara Bos, Rust Atomics and Locks, O'Reilly, 2023 (chapter 9: building locks). book · code
• Filip Pizlo, Locking in WebKit, webkit.org blog, 2016. post
• Linux futex(2) manual page. docs