Search code examples
concurrencyx86atomiclocklesswait-free

Are X86 atomic RMW instructions wait free

On x86, atomic RMW instructions like lock add dword [rdi], 1 are implemented using cache locking on modern CPUs. So a cache line is locked for duration of the instruction. This is done by getting the line EXCLUSIVE/MODIFIED state when value is read and the CPU will not respond to MESI requests from other CPU's until the instruction is finished.

There are 2 flavors of concurrent progress conditions, blocking and non-blocking. Atomic RMW instructions are non-blocking. CPU hardware will never sleep or do something else while holding a cache lock (an interrupt happens before or after an atomic RMW, not during), there is a finite (and small) upper bound on the number of steps before a cache line is released.

Non blocking algorithms can be split in 3 flavors in theoretical computer science:

  1. wait free: all threads will make progress in a finite number of steps.

  2. lock free: at least one thread will make progress in a finite number of steps

  3. obstruction free: if there is no contention, a thread will make progress in a finite number of steps

What kind of guarantee does x86 provide?

I guess it is at least lock free; if there is contention, at least one CPU will make progress.

But is x86 wait free for atomic instructions? Is every CPU guaranteed to make progress in a finite number of steps or could it be that one or more CPU's are starved and could potentially be delayed indefinitely?

So what happens when there are multiple cores doing atomic operations on the same cache line?

Solution

  • Consider the more general question: If there are multiple active hardware threads, does x86 guarantee that each thread make forward progress irrespective of what other threads do? The question you posed seems to be specifically about the case where each thread is simultaneously executing an atomic instruction to an overlapping memory location. If the answer is yes, then x86 can be described as "wait-free." (The term is usually only applied to describe a thread synchronization algorithm, but anyway.)

    I think it's important to define what "forward progress" means from the perspective of an architecture or an implementation thereof. I don't like to use the term "step" in the definition because it's not clear what is a step and what isn't a step. Instead, I'll use the following definition: An active hardware thread makes forward progress when it completes the next dynamic instruction in program order by retiring it or by switching to an exception handler in case of an error condition. If each active hardware thread can make forward progress in a finite amount of time irrespective of what the other threads do and irrespective of what instructions each thread is executing as long as they don't cause the thread to become inactive, then x86 is wait-free. (Note that interrupt handlers are not part of the program being executed on a hardware thread, so handling interrupts doesn't mean that the thread is making forward progress.)

    Is every CPU guaranteed to make progress in a finite number of steps or could it be that one or more CPU's are starved and could potentially be delayed indefinitely?

    You may be thinking here that if there are two cores continuously attempting to acquire atomic RMW access to the same location whether one of them will always succeed and the other will always fail, getting stuck trying to execute the same atomic instruction without making any progress because it's the next instruction in program order.

    This is actually a traditional problem in computer architecture. The reason I want to consider the more general question is because there are many points of possible contention between multiple hardware threads or agents other than acquiring locks. Consider what you said:

    CPU hardware will never sleep or do something else while holding a cache lock (an interrupt happens before or after an atomic RMW, not during), there is a finite (and small) upper bound on the number of steps before a cache line is released.
    ...
    I guess it is at least lock free; if there is contention, at least one CPU will make progress.

    Intel and AMD have never stated that "there is a finite upper bound on the number of steps before a cache line is released." This reasoning can be applied to almost any stage of an instruction's execution. Is there a finite upper found on the number of steps to fetch an instruction if the fetch missed in the private caches? Is there a finite upper found on the number of steps to read a value from the a shared cache? With hyperthreading, the potential for contention exists almost at every stage of executing any type of instruction. You could ask the same question for each of them. Atomic access contention is not special. One could ask other questions, such as whether it's possible for a core to arbitrarily enter a sleep state and never wake up.

    Fundamentally, it doesn't make sense to have multiple cores without making sure at the architectural level, by design, that each core is always able to make forward progress as long as it's active (according to the definition above). Otherwise, the implementation cannot be fully utilized. Every practical ISA has to provide the minimal forward progress guarantee, which is that any operation take a finite amount of time to complete and is preceded by a finite number of other operations in a global (or multi-agent) order of operations. Some ISAs, such as RISC-V, do explicitly state this.

    There are many examples where Intel has explicitly stated in the SDM manual and in many other documents that a shared structure is designed such that fairness is guaranteed, which is a stronger grantee than minimal forward progress. (For performance or other reasons, this may not always be accurate, though, because some types of requests may always have a higher or the highest priority. Maybe it's better to say that fairness is typically guaranteed and forward progress is guaranteed in general, or something like that.) These examples include the following (from the top of my head):

    • On multi-core processors before Nehalem and on multi-core Atom-branded processors, the L2 superqueue (which include the L2 controller) is designed to be (generally) fair and to guarantee progress of all agents that it interacts with.
    • The front-side bus (on systems that have an FSB) and the APIC bus (on systems that have a separate APIC bus) both are designed to be fair.
    • Most arbitration points between hardware threads on the same core are designed to be fair. One exception is the uop scheduler, on the microarchitectures that have a unified RS, or the uop schedulers, on the microarchitectures that have a distributed RS, which use a first-ready pseudo-FIFO algorithm.
    • On processors that use a crossbar interconnect, fairness is guaranteed at the L3 global queue.
    • On processors with ring interconnects, fairness is guaranteed at some ring stops while only forward progress is guaranteed at other ring stops.

    Therefore, if two cores are trying acquire atomic RMW access to the same location, the atomic instructions are guaranteed to make it through the pipelines and memory hierarchies of each core and each core's read-lock requests will eventually get its turn to be serviced. So, yes, x86 is wait-free according to the definition above. It's worth noting, though, that most or all Intel processors have rarely occurring bugs that cause all or a subset of processors to indefinitely hang.

    One interesting consideration is whether it's guaranteed that the progress of a core will not be indefinitely blocked due to continuous handling of interrupts. I think this is mostly dependent on the design of interrupt handlers, so the system software has to guarantee this.