title: Semaphore without destruction/unmapping race condition
body: <p><em>Note: I have heavily edited this question for clarity after making a mess of it brainstorming in public. However the actual algorithms described, and the question about whether they're sufficient to avoid races, should be identical.</em></p>
  
  <p>I'm trying to implement semaphores that avoid the race condition described in glibc bug number 12674:</p>
  
  <p><a href="http://sourceware.org/bugzilla/show_bug.cgi?id=12674" rel="nofollow">http://sourceware.org/bugzilla/show_bug.cgi?id=12674</a></p>
  
  <p>Basically, the efficient way to write a futex-based semaphore if you don't care about this race condition for destruction is:</p>
  
  <p>Post:</p>
  
  <ol>
  <li>Atomic increment semaphore value.</li>
  <li>Examine waiter count. If it's nonzero, perform a futex wake.</li>
  </ol>
  
  <p>Wait:</p>
  
  <ol>
  <li>Atomic decrement-if-positive on the semaphore value (and return if it succeeds).</li>
  <li>If this fails, increment waiters and perform a futex wait.</li>
  <li>On wakeup, decrement waiters, loop and retry.</li>
  </ol>
  
  <p>Step 2 of the post operation is what's unsafe.</p>
  
  <p>There are two obvious implementations which avoid this issue, but both have major problems:</p>
  
  <p>The first solution is not to store a waiter count or flag at all, and always perform a futex wake on post. This is obviously safe, but defeats the whole purpose of futexes (keeping the uncontended case in userspace).</p>
  
  <p>The second solution is not to store a waiter count, but instead let the semaphore value decrement to -1 on wait contention. The post operation then transitions from -1 to 1 and wakes <strong>all</strong> the waiters. One of them succeeds in decrementing the semaphore value to 0, and if any remain, they set the value to -1, so the next post will perform another wake. This solution is also obviously safe, but it results in a stampede of threads contending for the semaphore when it's posted.</p>
  
  <p>In summary, the first solution only works well for semaphores that are always contended, and the latter only works well for semaphores that usually have no more than one waiter. Neither is acceptable for general use.</p>
  
  <p><strong>Now, on to an attempt at a real solution...</strong></p>
  
  <p><em>At this point, it should be noted that there are a few other requirements that complicate a real-world implementation. The post operation is required to be async-signal-safe (so it basically cannot use locks), and the wait operation is required to allow interruption by signals, timeout, or thread cancellation. In practice this means the post operation must be able to safely "back out" any changes it makes to the semaphore state. I have glossed over such issues because I my approach seems to have no problems with them, but they do make some otherwise-obvious changes/solutions impossible, so anyone suggesting new approaches as an answer should be aware of these issues...</em></p>
  
  <p>I have a proposed solution, but I'm unsure whether it's subject to new (and possibly worse) race conditions. I will describe it here, and I hope some concurrency gods (or demigods at least) might have the kindness to review it for correctness.</p>
  
  <p>My approach is something of a hybrid of the second "bad" solution I described above, and the original approach (with the race described in the glibc bug report). It uses both a waiter count and a waiter flag (-1 stored in the semaphore value).</p>
  
  <p>The key change to the wait operation is that it stores -1 instead of 0 in the semaphore value whenever there are waiters (preexisting waiter count or itself as a new waiter).</p>
  
  <p>Wait:</p>
  
  <ol>
  <li>Read semaphore value.</li>
  <li>If the value is positive, determine a new semaphore value as follows: if the value is exactly 1 and there are waiters, the new value should be -1; otherwise just decrement the old value. Use compare-and-swap to update the value, and return success if this succeeds.</li>
  <li>Otherwise, increment waiters, atomically replace a value of 0 with -1, and perform a futex wait with -1 as the value.</li>
  <li>On wakeup, decrement waiters, loop and retry.</li>
  </ol>
  
  <p>The key change to the post operation is that it performs the read on the waiter count <strong>before</strong> incrementing the semaphore value, rather than afterwards:</p>
  
  <p>Post:</p>
  
  <ol>
  <li>Read and save semaphore value.</li>
  <li>Read and save waiter count.</li>
  <li>Determine new semaphore value (-1 becomes 1, otherwise just increment).</li>
  <li>Atomic compare-and-swap to update semaphore value. On failure, goto 1.</li>
  <li>If the saved waiter count was nonzero or the semaphore value was -1, perform futex wake.</li>
  </ol>
  
  <p>The compare-and-swap in step 4 provides some safety that the waiter count is still correct, but there's still an ABA race - between steps 1 and 4, it's possible that other threads perform wait and post operations that leave the semaphore value the same as its initial value.</p>
  
  <p>In looking for cases where this algorithm might fail to wake waiters, we need only consider cases where the initial waiter count read is 0 and the semaphore value read is not -1. Further, if the semaphore value is positive and there are no preexisting waiters, the current post is not responsible for any wakeups, so this case is not interesting either. We're left examining cases where the wait operation begins with a zero semaphore value and zero wait count. In this situation, in order not to have a race condition, any event that happens between steps 2 and 4 that results in new waiters must change the semaphore value, so that the compare-and-swap at step 4 fails. Clearly any single intervening post or wait will change the semaphore value (to 1 or -1, respectively), so the case of concern, more specifically, is sequences of operations which result in a semaphore value of 0 but the presence of waiters.</p>
  
  <p><strong>I believe this cannot happen due to the procedure followed in the wait operation, but I haven't convinced myself 100%.</strong></p>
  
  <hr>
  
  <p>Finally, here are some examples of races that happen if you weaken my algorithm, in order to establish the motivations for what it's doing if that's not clear.</p>
  
  <p>Failure 1: Using a pure wait count, no -1 flag in the semaphore value. Trivial race looks like:</p>
  
  <ol>
  <li>Semaphore value starts at 0</li>
  <li>Thread 1 starts post, reads 0 semaphore value and 0 wait count.</li>
  <li>Thread 2 starts wait, increments wait count and futex waits.</li>
  <li>Thread 1 performs successful compare-and-swap, returns without waking the waiter.</li>
  </ol>
  
  <p>Failure 2: Using waiter count and having new waiters set the semaphore value to -1, but simply decrementing the semaphore value when wait succeeds (without setting it to -1 if other threads are still waiting):</p>
  
  <ol>
  <li>Semaphore value starts at 0</li>
  <li>Thread 1 starts post, reads 0 semaphore value and 0 wait count.</li>
  <li>Threads 2 and 3 wait, incrementing wait count and futex waiting.</li>
  <li>Thread 4 posts, setting semaphore value to 1.</li>
  <li>Thread 2 wakes and decrements semaphore value to 0, waiter count to 1.</li>
  <li>Thread 1 performs successful compare-and-swap, returns without waking thread 3.</li>
  </ol>