# Case Study: Linux Futex (Fast Userspace Mutex)

> ```c
> #include <linux/futex.h>
> #include <sys/time.h>
>
> int futex(int *uaddr, int futex_op, int val, const struct timespec *timeout);
> ```
>
> `uaddr` points to a 32-bit value in user space
>
> `futex_op`
>
> * `FUTEX_WAIT` – if `val == *uaddr` then sleep till FUTEX\_WAKE **Atomic** check that condition still holds after we disable interrupts (in kernel!)
> * `FUTEX_WAKE` – wake up at most `val` waiting threads
> * `FUTEX_FD`, `FUTEX_WAKE_OP`, `FUTEX_CMP_REQUEUE`: More interesting operations!
> * `timeout` - `ptr` to a *timespec* structure that specifies a timeout for the op

Interface to the kernel `sleep()` functionality. Let the thread put themselves to sleep conditionally.

## T\&S and Futex

```c
acquire(int *thelock) {
  while(__atomic_test_and_set(thelock, __ATOMIC_SEQ_CST)) {
    futex(thelock, FUTEX_WAIT, 1);
  }
}

release(int *thelock) {
  thelock = 0;
  futex(thelock, FUTEX_WAKE, 1);
}
```

**`acquire(int *thelock)`** This function is used to acquire the lock. The argument is a pointer to the lock variable.

* `futex(thelock, FUTEX_WAIT, 1)` is called when the lock is not available. This puts the calling thread to sleep until the lock becomes available. The `FUTEX_WAIT` operation suspends the thread if the current value of the futex word (i.e., the lock variable) is `1` (the third argument to `futex`).

**`release(int *thelock)`** This function is used to release the lock. The argument is a pointer to the lock variable.

* `futex(&thelock, FUTEX_WAKE, 1);` wakes up one of the threads waiting on the lock, if any. The `FUTEX_WAKE` operation wakes up a number of threads waiting on the futex word (i.e., the lock variable). The third argument to `futex` specifies the maximum number of threads to wake up, which in this case is `1`.

There is no busy waiting here. The acquire procedure simply sleeps until being waken up by the release. But we still have to tap into the kernel to **release** the lock even if there is no one who is acquring the lock.

So we provide a second implementation to be syscall-free in the uncontended case:

```c
void acquire(int *thelock, bool *maybe) {
    while (__atomic_test_and_set(thelock, __ATOMIC_SEQ_CST)) {
        // Sleep, since lock busy!
        *maybe = true;
        futex(thelock, FUTEX_WAIT, 1);
        // Make sure other sleepers are not stuck
        *maybe = true;
    }
}

void release(int *thelock, bool *maybe) {
    __atomic_clear(thelock, __ATOMIC_SEQ_CST);

    if (*maybe) {
        *maybe = false;
        // Try to wake up someone
        futex(thelock, FUTEX_WAKE, 1);
    }
}
```

A more elegant implementation:

```c
#include <stdint.h>
#include <linux/futex.h>
#include <unistd.h>

void acquire(Lock *thelock) {
    Lock expected = UNLOCKED;
    
    // If unlocked, grab lock!
    if (__atomic_compare_exchange_n(thelock, &expected, LOCKED, 0, __ATOMIC_SEQ_CST, __ATOMIC_SEQ_CST))
        return;

    // Keep trying to grab lock, sleep in futex
    while (__atomic_exchange_n(thelock, CONTESTED, __ATOMIC_SEQ_CST) != UNLOCKED)
        // Sleep unless someone releases here!
        futex((int *)thelock, FUTEX_WAIT, CONTESTED, NULL, NULL, 0);
}

void release(Lock *thelock) {
    // If someone is sleeping, 
    if (__atomic_exchange_n(thelock, UNLOCKED, __ATOMIC_SEQ_CST) == CONTESTED)
        futex((int *)thelock, FUTEX_WAKE, 1, NULL, NULL, 0);
}
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://osh.fducslg.com/notes/operating-systems/linux-futex.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.