Futex

The kernel’s half is small. futex_wait (&val, v) puts the caller to sleep only if val still holds v, and otherwise returns at once with EWOULDBLOCK. futex_wake (&val, 1) wakes one thread sleeping on that word, if there is one. The one guarantee that makes it work is that the check and the sleep are a single step. Drepper says the test of the value “must be atomic, too”, and the manual page today says “The loading of the futex word’s value, the comparison of that value with the expected value, and the actual blocking will happen atomically”.

Everything else is the program’s. Drepper’s first mutex, from section 4 of the paper, keeps a count in the word: nought is free, anything else is taken. lock () adds one, and if the old value was not nought it sleeps on the value it made. unlock () stores nought and wakes one sleeper.

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

The marked row in the table below, an unlock with nobody waiting, is the cost a futex exists to avoid, and this mutex pays it anyway. Its unlock cannot tell whether anybody is waiting, so it asks the kernel every time. Run on a real Linux kernel with the real system call, one thread taking and releasing each mutex a thousand times made 1,000 futex calls with this one and none with the other two, counted by the program as it ran and again from outside by strace.

threads sharing the lock onetwothree

states the threads can reach

41

places an unlock calls futex_wake

14

and nobody is asleep to wake

12

With 2 threads, the model reaches 41 states. In 12 of the 14 places where an unlock calls futex_wake, nobody is asleep to be woken. Each of those is a system call made for nothing.

The first mutex has a worse problem than the wasted call, and Drepper calls it “quite serious in some situations but very hard to spot”. Thread 1 holds the lock. Two more threads each add one to the word and ask to sleep on the value they made. But each increment changes the word under the other thread’s futex_wait, so the kernel sends both straight back with EWOULDBLOCK, and they add one again. “This process can be continued ad infinitum.”

Not quite, because a word cannot count forever. Nobody can enumerate a 32-bit counter, so the counter here is narrow and its width is yours to set. Thread 1 is held still inside the lock, the other two may do anything the model allows, and the longest run of futex_waits that fail is counted.

the counter 2 bits

longest run of failed futex_waits, lock held

2

2 to the width, minus 2

2

states with two threads inside the lock

16

states, with thread 1 held still

82

The shortest schedule that ends with two threads inside, in the paper’s own calls:

The shortest schedule the model finds from thread 1 holding the lock to two threads inside it: 6 steps.

With the lock held and nobody releasing it, the two waiters can fail 2 futex_waits in a row, which is 2 to the 2 minus 2. Then the counter reads nought, the next increment returns nought, and a second thread walks into the lock beside the one holding it. On a 32-bit int the same path is 4,294,967,294 failed waits long: the formula, not a count, because nobody can enumerate it.

So the first bug feeds the second. Drepper’s second bug is the counter running out, after which “magically the variable is free”, and he asks when a futex_wait can return without the mutex having been released: “One example is the first bug above.” With only one waiter and no signals it cannot happen, because a failed wait then means the holder has already let go. It takes a second waiter to keep the first one awake. The first bug was “present in some form for many months” in the NPTL thread library, and fixing it, he reports, one real application on a four-processor machine “got sped up eight to ten times”.

The second mutex stops counting. The word holds one of three values: nought is free, 1 is locked with no waiters, 2 is locked with waiters, perhaps. A thread that finds the lock taken marks it 2 before it sleeps. Now an unlock that finds 1 knows nobody is asleep and skips the system call, and a waiter’s futex_wait always expects 2, which nobody changes while the lock is held.

void lock () {
  int c;
  if ((c = cmpxchg (val, 0, 1)) != 0)
    do {
      if (c == 2
          || cmpxchg (val, 1, 2) != 0)
        futex_wait (&val, 2);
    } while ((c = cmpxchg (val, 0, 2))
             != 0);
}
void unlock () {
  if (atomic_dec (val) != 1) {
    val = 0;
    futex_wake (&val, 1);
  }
}

threads sharing the lock twothreefour

retake the lock with 1 instead of 2

states the threads can reach

1,002

states with two threads inside the lock

0

longest run of failed futex_waits, lock held

0

states with a sleeper nothing running will wake

0

system calls in an uncontended unlock

0

With 3 threads: nobody else inside, no futex_wait that fails while the lock is held, and no sleeper left behind, over 1,002 states. Uncontended, unlock makes 0 system calls.

The button changes one constant: the value the loop writes when it finally takes the lock. Drepper’s reason for writing 2 is “because we do not know any better”. A thread that has just been woken cannot know whether others are still asleep behind it, and “being wrong in guessing sooner or later means running into a deadlock”. A sleeper is stranded when it is asleep, the lock is free, and every other thread has finished with it, which is his own requirement for a mutex turned upside down.

The shortest schedule to a stranded sleeper, when there is one:

The price of guessing 2 is paid the other way round. Sometimes an unlock finds 2, calls the kernel, and there is nobody left to wake. Drepper says so, and it is a system call spent to make sure no thread is ever stranded.

The third mutex is the second with the two compares in its loop replaced by an exchange, which writes 2 whatever the word held. The revision history in the paper dates it to February 2004, four months after the first draft, and it comes with a second table comparing it against the second mutex.

void lock () {
  int c;
  if ((c = cmpxchg (val, 0, 1)) != 0) {
    if (c != 2)
      c = xchg (val, 2);
    while (c != 0) {
      futex_wait (&val, 2);
      c = xchg (val, 2);
    }
  }
}
void unlock () {
  if (atomic_dec (val) != 1) {
    val = 0;
    futex_wake (&val, 1);
  }
}

Both tables print a contended lock’s atomic operations as two numbers. The second is the trip round the loop again, which in his words “represents the additional cost for the function call which has to be paid” when futex_wait returns and the thread has to go back to sleep. A stacked cell means “use the upper number, otherwise the lower number”: upper when there are waiters already. What the first number counts, the paper does not say. The model counts it both ways: as far as the first futex_wait, and the whole call when it waits exactly once.

Every printed cell is a number the model produces, but not under one count. The paper does not say what its first number counts, so what follows is this page's reading. The second mutex's column fits the whole call, including the compare that finally takes the lock; the other two fit only as far as the first futex_wait. Counted the second mutex's way, the first mutex is 2 and not 1, so the second makes 2 or 3 atomic operations against the first's 2, not “2 to 3 times” as many. And counted either way, the third mutex's first trip costs exactly what the second's does.

And the second number, what one more trip round the loop adds, every value the cost census reaches before its cap:

So the third mutex's saving is in the trips that fail: one exchange, always, where the second can need two compares, and more while other threads keep taking and dropping the lock between them. The model reaches extra trips of 1, 2, 3, 4 for the second, a list the census cuts off at 4 atomics and not the end of what the model can do, and 1 for the third.

These ran in this browser when the page loaded. Each claim, whether it held, and the number behind it.