P99 futexes: non-blocking integer valued condition variables

A while ago I already have written about Linux futexes as a really nice concept for a control data structure that goes beyond the ones that we learn or teach in school (mutex, semaphore, condition variable…). I have now gone one step further and integrated futexes into P99; if used on Linux this will evidently use the corresponding Linux feature under the hood, on other platforms a C11 thread implementation using mutexes and condition variables can be used.

One of the real disadvantages of most of the control structures is that they have two very different kinds of events: user events (e.g a call to cnd_signal) and system events, often called “spurious wakeups”. Unless we program system code, these spurious wakeups are just an annoyance. They are easily forgotten during development and lead to subtle bugs that only appear on heavy load or when changing the platform and handling them often makes the user code overly complex.

p99_futex are designed to work around this type of problems, by still providing a close integration of the control structure into the system and by efficiently distinguishing a “fast path” for operations from a “slow path” where we handle congestion. They provide a counter similar to a conditional variable that allows atomic increments and to wait for it, just as the Linux system call does. (Only that for ideological reasons the base type is an unsigned, instead of an int as in Linux.)

linux futexes: non-blocking integer valued condition variables

POSIX’ condition variables pthread_cond_t unfortunately have some drawbacks:

• They require the use of at least two separate other objects that are only loosely coupled with the condition variable itself:
  • A plain variable, say X of type int, that actually holds the value of which the condition depends.
  • A mutex that is just to regulate the access to X and to the condition variable.
• Generally they are not lock free. To access X we have to
  • lock the mutex
  • inspect X
  • eventually wait for the condition to become true
  • do changes
  • eventually signal other waiters about the changes we made
  • unlock the mutex

Linux’ concept of futexes allows to associate an equivalent concept directly to the variable X and to access this variable without taking locks directly in most of the cases.