Preemption is GC for memory reordering - Paul Khuong: some Lisp

I previously noted how preemption makes lock-free programming harder in userspace than in the kernel.<br>I now believe that preemption ought to be treated as a sunk cost, like<br>garbage collection: we’re already paying for it, so we might as<br>well use it. Interrupt processing (returning from an interrupt<br>handler, actually) is fully serialising on x86, and on other<br>platforms, no doubt: any userspace instruction either fully executes<br>before the interrupt, or is (re-)executed from scratch some time after<br>the return back to userspace. That’s something we can abuse to<br>guarantee ordering between memory accesses, without explicit barriers.

This abuse of interrupts is complementary to Bounded TSO.<br>Bounded TSO measures the hardware limit on the number of store instructions<br>that may concurrently be in-flight (and combines that with the<br>knowledge that instructions are retired in order) to guarantee<br>liveness without explicit barriers, with no overhead, and usually<br>marginal latency. However, without worst-case execution<br>time information, it’s hard to map instruction counts to real time.<br>Tracking interrupts lets us determine when enough real time has<br>elapsed that earlier writes have definitely retired,<br>albeit after a more conservative delay than Bounded TSO’s typical<br>case.

I reached this position after working on two lock-free<br>synchronisation primitives—event counts,<br>and asymmetric flag flips as used in hazard pointers<br>and epoch reclamation—that<br>are similar in that a slow path waits for a sign of life from a fast<br>path, but differ in the way they handle “stuck” fast paths. I’ll cover<br>the event count and flag flip implementations that I came to on<br>Linux/x86[-64], which both rely on interrupts for ordering. Hopefully<br>that will convince you too that preemption is a useful source of<br>pre-paid barriers for lock-free code in userspace.

I’m writing this for readers who are already familiar with<br>lock-free programming,<br>safe memory reclamation techniques in particular, and have some<br>experience reasoning with formal memory models.<br>For more references, Samy’s overview in the ACM Queue is a good resource.<br>I already committed the code for<br>event counts in Concurrency Kit,<br>and for interrupt-based reverse barriers in my barrierd project.

Event counts with x86-TSO and futexes

An event count<br>is essentially a version counter that lets threads wait<br>until the current version differs from an arbitrary prior version. A<br>trivial “wait” implementation could spin on the version counter.<br>However, the value of event counts is that they let lock-free code<br>integrate with OS-level blocking: waiters can grab the event count’s<br>current version v0, do what they want with the versioned data, and<br>wait for new data by sleeping rather than burning cycles until the<br>event count’s version differs from v0. The event count is a common<br>synchronisation primitive that is often reinvented and goes by many<br>names (e.g.,<br>blockpoints);<br>what matters is that writers can update the version counter, and<br>waiters can read the version, run arbitrary code, then efficiently<br>wait while the version counter is still equal to that previous<br>version.

The explicit version counter solves the lost wake-up issue associated<br>with misused condition variables, as in the pseudocode below.

bad condition waiter:

while True:<br>atomically read data<br>if need to wait:<br>WaitOnConditionVariable(cv)<br>else:<br>break

In order to work correctly, condition variables require waiters to<br>acquire a mutex that protects both data and the condition variable,<br>before checking that the wait condition still holds and then waiting<br>on the condition variable.

good condition waiter:

while True:<br>with(mutex):<br>read data<br>if need to wait:<br>WaitOnConditionVariable(cv, mutex)<br>else:<br>break Waiters must prevent writers from making changes to the data, otherwise the data change (and associated condition variable wake-up) could occur between checking the wait condition, and starting to wait on the condition variable. The waiter would then have missed a wake-up and could end up sleeping forever, waiting for something that has already happened.

good condition waker:

with(mutex):<br>update data<br>SignalConditionVariable(cv)

The six diagrams below show the possible interleavings between the<br>signaler (writer) making changes to the data and waking waiters, and<br>a waiter observing the data and entering the queue to wait for<br>changes. The two left-most diagrams don’t interleave anything; these<br>are the only scenarios allowed by correct locking. The remaining four<br>actually interleave the waiter and signaler, and show that, while<br>three are accidentally correct (lucky), there is one case, WSSW,<br>where the waiter misses its wake-up.

If any waiter can prevent writers from making progress, we don’t have<br>a lock-free protocol. Event counts let waiters detect when they would<br>have been woken up (the event count’s version counter has changed),<br>and thus patch up this window where waiters can miss...