Mutexes from futexes

mutex.txt

There are two basic algorithms I've found for building mutexes from futexes: I'll call them  "tristate" and "waiter count" based on the state they maintain in the futex word.

The "tristate" algorithm allows the futex word to be in exactly 3 states: UNLOCKED, LOCKED, LOCKED_WITH_POSSIBLE_WAITERS. It is introduced in Ulrich Drepper's 2004 paper "Futexes Are Tricky" as "mutex3":
https://dept-info.labri.fr/~denis/Enseignement/2008-IR/Articles/01-futex.pdf#page=7
The same algorithm is used for pthreads mutexes in glibc as the "low-level lock" (LLL):
https://codebrowser.dev/glibc/glibc/sysdeps/nptl/lowlevellock.h.html
https://codebrowser.dev/glibc/glibc/nptl/lowlevellock.c.html
Other languages have implemented the same algorithm for mutexes on Linux, such as Go:
https://golang.bg/src/runtime/lock_futex_tristate.go
Here is a version that adds adaptive spinning and uses byte-width atomics, storing the "locked" and "maybe_waiters" bits in separate bytes (and uses all 4 possible states instead of just 3):
https://locklessinc.com/articles/mutex_cv_futex/

The "waiter count" algorithm packs a lock bit and a waiter count into the futex word. It has a very simple implementation in glibc ("generic mutex", AFAICT not the algorithm currently used for pthreads mutex):
https://elixir.bootlin.com/glibc/glibc-2.5/source/nptl/lowlevellock.h
If you look at lines 57-59, it's clear that the BTS/FAA sequence can be replaced with a single CAS (test for clear lock bit and decrement waiter count within the CAS). The musl pthreads mutex implementation (which I find less readable overall) applies this simple optimization:
https://git.musl-libc.org/cgit/musl/tree/src/thread/__lock.c

Both algorithms are correct and have only a single atomic RMW op on the lock and unlock fast paths (release-store unlock only works for spinlocks), but the "tristate" algorithm needs only 2 bits of state, while the "waiter count" algorithm avoids an unnecessary wakeup when the last waiter unlocks. Additionally, storing the exact waiter count might be useful for logic like avoiding the spinning fast path when there are >N waiters queued. Not storing the waiter count could be helpful if there is other state we want to pack into the 32-bit futex word. Note that although 64-bit futexes have never been implemented (due to opposition from Linus), since 5.16 the futex_waitv() syscall has been available, which allows you to wait on multiple futexes, so you could effectively use 2 futexes for 64 bits of state:
https://docs.kernel.org/userspace-api/futex2.html

Note that none of these algorithms should be employed without adaptive spinning. The basic idea of adaptive spinning for locks is that the lock acquire path should attempt the CAS (or TAS) first to optimize for no contention, and then should spin on a relaxed load of the lock word, with exponential backoff using PAUSE between CAS attempts, for up to context switch latency (say 5-10us), then call sched_yield() for a few iterations, and finally block in a syscall like futex_wait.
Some of these implementations entangle adaptive spinning heuristics with the core locking logic, but I find it cleaner to separate them. Note that we could use an adaptive spinning implementation outside of locks to mitigate contention in CAS loops.
I think Rust's parking_lot_core::SpinWait is a good example of nicely encapsulating adaptive spinning logic:
https://amanieu.github.io/parking_lot/src/parking_lot_core/spinwait.rs.html#70-118
And Intel's TBB spinning primitives:
https://github.com/uxlfoundation/oneTBB/blob/0cd32ab10a84eabf780bb699b17430deb028c0a4/include/oneapi/tbb/detail/_utils.h#L45
https://github.com/uxlfoundation/oneTBB/blob/0cd32ab10a84eabf780bb699b17430deb028c0a4/include/oneapi/tbb/detail/_utils.h#L123-L133
Here is some more inspiration for adaptive spinning heuristics:
https://www.1024cores.net/home/lock-free-algorithms/tricks/spinning
And here is Example 2.10 from the Intel x86_64 optimization manual (https://software.intel.com/content/www/us/en/develop/download/intel-64-and-ia-32-architectures-optimization-reference-manual.html):

/*******************/
/*Baseline Version */
/*******************/
// atomic {if (lock == free) then change lock state to busy}
while (cmpxchg(lock, free, busy) == fail)
{
    while (lock == busy)
    {
        __asm__ (“pause”);
    }
}

/*******************/
/*Improved Version */
/*******************/
int mask = 1;
int const max = 64; //MAX_BACKOFF
while (cmpxchg(lock, free, busy) == fail)
{
    while (lock == busy)
    {
        for (int i=mask; i; --i)
        {
            __asm__ (“pause”);
        }
        mask = mask < max ? mask<<1 : max;
    }
}

see discussion of futex-based locks in https://lobste.rs/s/va2mvi/without_futex_it_s_futile
A