§ RTFM : manpage for futex(2)

NAME
       futex - fast user-space locking

LIBRARY
       Standard C library (libc, -lc)

SYNOPSIS
       #include <linux/futex.h>      /* Definition of FUTEX_* constants */
       #include <sys/syscall.h>      /* Definition of SYS_* constants */
       #include <unistd.h>

       long syscall(SYS_futex,
                    uint32_t *uaddr,    // points to futex word
                    int futex_op,
                    uint32_t val,
                    const struct timespec *timeout,   /* or: uint32_t val2 */
                    uint32_t *uaddr2,
                    uint32_t val3);

Note: glibc provides no wrapper for futex(), necessitating the use of syscall

• futex is always 32bit value (refered to by *uaddr) and must be 4-byte aligned.
• futex syscall takes process userspace virt addr, but it’s internally handled by the kernel via physical address (thus allowing sharing among different processes

FUTEX_OP FLAGS

FUTEX_PRIVATE_FLAG (can be used for all)
    the futex is process-private and is not shared with another process. For
    convenience some futex_op flags can have _PRIVATE suffix e.g.
    FUTEX_WAIT_PRIVATE == FUTEX_WAIT_PRIVATE | FUTEX_PRIVATE_FLAG

FUTEX_CLOCK_REALTIME (check manual for applied futex_ops)
    either the timeout is measure against the CLOCK_REALTIME clock or
    (default / unset) CLOCK_MONOTONIC clock
    

FUTEX_WAIT and FUTEX_WAKE

PARAS
    uaddr       : points to the futex (for all futex_op)

FUTEX_WAIT
    val         : expected value of the futex (as poitned by uaddr)
    timeout     : (relative) timeout for the sleep; if NULL the call blocks
                  indefinitely until waken
    uaddr2/val3 : ignored

FUTEX_WAKE
    val         : max number of waiters to wake up (INT_MAX to wake all)
    timeout     : ignored
    uaddr2/val3 : ignored    

if expected val doesn’t match actual value (via a atomic load in the kernel) the call will return immediately with EAGAIN (was EDOUBLELOCK in earlier versions)

FUTEX_WAKE_OP

PARAS - WAKE_OP

    timeout     : used as val2, (max waiters to wake for futex2)
    uaddr2      : points to the second futex

    val3        : compond value as folows
    +---+---+-----------+-----------+
    |op |cmp|   oparg   |  cmparg   |
    +---+---+-----------+-----------+
    4   4       12          12    <== # of bits

is equivalent to executing the following code atomically and totally ordered wrt. other futex operations on any of the the two supplied futex words

1
2
3
4
5

uint32_t oldval = *(uint32_t *) uaddr2;
*(uint32_t *) uaddr2 = oldval op oparg;
futex(uaddr, FUTEX_WAKE, val, 0, 0, 0);
if (oldval cmp cmparg)
    futex(uaddr2, FUTEX_WAKE, val2, 0, 0, 0);

• saves the old futex2 value (pointed by uaddr2) and performs an operation to modity the value of futex2 (via a Read-Modify-Write atomic memory op).
• wakes up max val waiter on futex1 (*uaddr) like FUTEX_WAKE
• dependent on the results of a test of the old value of futex2, wakes up max val2 waiters

FUTEX_WAIT_BITSET and FUTEX_WAKE_BITSET (TODO)

§ userspace lock implementations with futex

share futex between processes via manual mmap(). Code from here

iaddr = mmap(NULL,              /* no addr specs for the allocation */
    sizeof(int) * 2,            /* mapping for 2 futexes */
    PROT_READ | PROT_WRITE,     /* allow read write access */
    MAP_ANONYMOUS | MAP_SHARED, /* anonymous mapping + shared */
    -1, 0                       /* fd = -1 for anon mapping, no offset */
    )

futex1 = &iaddr[0];
futex2 = &iaddr[1];

pid = fork();                   /* child inherits the shared anon mapping */

if (pid == -1) {/* fork error */}
if (cpid == 0) {/* child */ } else {/* parent */}

CODE EXAMPLES

impl MUTEX via FUTEX

Ulricht ¹ lists in their paper a few mutex implementations via futex, which seem intuitive but turn out to be incorrect. Here are some recaps, refer to the paper for details

Mutex, Take 1 from ¹

class mutex {
private:
    int val;
public:
    mutex () : val (0) { }
    void lock () {
        int c;
        while ((c =atomic_inc (val)) != 0)
            futex_wait (&val, c + 1);
    }
    void unlock () {
        val = 0;
        futex_wake (&val, 1);
    }
};

pitfalls:

• livelock : two lock() calls repeatedly cause each other to fail. Since the val doesn’t match the old value before the sleep, futex_wait call returns immediately with EAGAIN

  AC: atomic_inc
  FW: futex_wait 
  
               AC      FW          AC                 FW
  thread 1: ---XX------XX-[EAGAIN]-XX-----------------XX-[EAGAIN]-
  thread 2: ------XX------------------XX-[EAGAIN]--XX-------------
                  AC                  FW           AC
  

• int wraparound on futex val (since waiters unconditionally increment it)
• unlock() unnecessarily calls futex_wake() even when uncontested

Mutex, Take 3 from ¹ (same as take 2 but optimized by replacing some cmpxchg with less expensive xchg)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

#define UNLOCKED    0
#define NO_WATER    1
#define HAS_WATER   2

static int val = UNLOCKED;

static void lock () {
    int c;
    if ((c = cmpxchg (val, UNLOCKED, NO_WAITER)) != UNLOCKED) {
        // lock is contested
        if (c != HAS_WAITER)              /* the first waiter */
            c = xchg (val, HAS_WAITER);
        while (c != UNLOCKED) {
            futex_wait (&val, HAS_WAITER);
            c = xchg (val, HAS_WAITER);   /* even the last waiter */
        }
    }
    // else: sucessfully taken the lock while there is no waiter
}

static void unlock () {
    if (atomic_dec (val) != NO_WAITER) {
        val = UNLOCKED;
        // <<-- another thread could cut in here
        futex_wake (&val, NO_WAITER);
    }
    // else: take the shortpath, save one syscall
    // in either case val is reset to UNLOCKED
}

§ TODOs

Priority-inheritance futex (TODO)