Read the original article here.

---

The Forbidden Art of Memory Fences: Taming CPU Reordering for Concurrent Programming

Welcome, fellow code spelunkers, to a dive into the dark arts of concurrent programming – techniques often hinted at but rarely explicitly taught in the standard curriculum. We're pulling back the curtain on memory barriers, also known as memory fences or fence instructions. These aren't your garden-variety programming constructs; they are low-level directives essential for controlling how multiple processors or devices see changes in shared memory. Master them, and you gain fine-grained control over system behavior. Ignore them, and your concurrent programs will suffer from unpredictable, often devastating bugs.

The Illusion of Order: Why We Need Fences

In a perfect world, a program's instructions would execute exactly in the order you write them. In the real world of modern high-performance computing, that's a naive fantasy. CPUs and compilers employ aggressive optimizations to make your code run faster.

The Problem: Out-of-Order Execution (CPU Level)

Modern CPUs are incredibly complex machines capable of executing multiple instructions simultaneously or starting subsequent instructions before previous ones have fully completed. They use techniques like instruction pipelining, multiple execution units, and speculative execution.

Out-of-Order Execution: A CPU optimization technique where instructions are executed in an order different from the program order to make better use of processor resources, hide memory latency, and increase throughput. While the CPU usually ensures the single-thread outcome appears correct, the timing and visibility of memory operations to other threads or devices can be altered.

While the CPU works hard to make this look consistent to a single thread, the visibility of memory writes (stores) and the timing of memory reads (loads) to other threads or hardware can be completely reordered from the perspective of external observers.

The Problem: Compiler Reordering (Compiler Level)

Compilers are also performance wizards. They analyze your code and might rearrange instructions to improve cache usage, minimize register spills, or eliminate redundant operations.

Compiler Reordering: An optimization technique where a compiler changes the order of instructions in the compiled machine code from the original source code order, based on data dependencies and potential performance gains.

Just like CPU reordering, compiler reordering can break assumptions about memory visibility and instruction timing when multiple threads are involved.

The Consequence:

When your program runs on a single CPU without any interaction with external devices or other threads, these reorderings are usually transparent. The CPU and compiler maintain the illusion of program order for that single stream of execution.

However, when you enter the realm of:

1. Multiprocessor Systems: Multiple CPUs executing different threads of the same program and sharing memory.
2. Device Drivers: Software interacting directly with hardware memory-mapped registers or device memory.

...the illusion shatters. A memory write performed by one CPU might not be immediately visible to another CPU, or writes might become visible in a different order than they were issued. This leads to data races, stale data reads, and general chaos in concurrent operations.

Erecting the Fences: The Power of Memory Barriers

This is where memory barriers come in. They are explicit instructions or directives that tell the CPU (and sometimes the compiler) to enforce specific ordering constraints on memory operations.

Memory Barrier (Membar, Memory Fence, Fence Instruction): An instruction that enforces an ordering constraint on memory operations issued before and after the barrier. It typically guarantees that all memory operations initiated before the barrier are completed and their effects are visible to other processors/devices before any memory operations initiated after the barrier begin their globally visible effects.

Think of a memory barrier as a checkpoint. The CPU cannot pass certain memory operations beyond the barrier until all relevant memory operations before the barrier have reached a certain state of completion and visibility.

The exact behavior of a memory barrier is defined by the processor's memory ordering model or memory consistency model. Some architectures provide different types of barriers (e.g., full barriers, acquire barriers, release barriers) that enforce different subsets of ordering constraints (e.g., only loads before/after, only stores before/after, or both). For simplicity, we often talk about 'full' barriers which order all types of memory operations relative to each other.

Scenario 1: The Classic Synchronization Problem

Let's revisit a common problem in concurrent programming: signaling that data is ready. Consider two threads sharing memory locations x and f, initially both 0.

• Thread #1 (Reader/Consumer): Waits for f to become non-zero, then reads and prints x.
• Thread #2 (Writer/Producer): Writes a value (e.g., 42) to x, then sets f to 1 to signal that x is ready.

Here's the pseudo-code:

// Shared variables, initially x = 0, f = 0

// Thread #1 (Core #1)
while (f == 0) {
    // Spin or yield
}
// f is non-zero, data *should* be ready
print x;

// Thread #2 (Core #2)
x = 42;
f = 1; // Signal that x is ready

The Danger:

On a system with aggressive reordering, the CPU executing Thread #2 might reorder the writes, making f = 1 globally visible before x = 42 is globally visible.

If Thread #1 is spinning quickly, it could see f become 1, exit its loop, and then read x before Thread #2's write to x (the value 42) has become visible on Core #1. The result? Thread #1 prints 0 instead of 42. This is a classic data race and a visibility problem.

The Forbidden Solution: Inserting Memory Barriers

To fix this, we need memory barriers to enforce the intended order of operations becoming visible.

// Shared variables, initially x = 0, f = 0

// Thread #1 (Core #1)
while (f == 0) {
    // Spin or yield
}
// --- Memory Barrier #2 Needed Here ---
// Ensure f's change is seen BEFORE reading x
print x;

// Thread #2 (Core #2)
x = 42;
// --- Memory Barrier #1 Needed Here ---
// Ensure x's change is seen BEFORE f signals readiness
f = 1; // Signal that x is ready

• Memory Barrier #1: Placed after writing to x and before writing to f in Thread #2. It ensures that the store to x is completed and globally visible before the store to f becomes globally visible. When Thread #1 sees f as 1, it's guaranteed that the new value of x (42) is also visible (or will become visible momentarily without further synchronization needed between the barrier and the f=1 store).

• Memory Barrier #2: Placed after detecting that f is non-zero and before reading x in Thread #1. It ensures that the load of f (which returned a non-zero value) is completed and that any subsequent loads (like reading x) reflect memory state that is at least as up-to-date as the state that showed f as non-zero. Without this, Thread #1 might cache the old value of x (0) even after seeing the new value of f (1).

By strategically placing these barriers, we ensure that the intended causality (x is ready then f signals readiness) is respected across the different cores accessing the shared memory.

This pattern is fundamental to building correct synchronization primitives like spinlocks or semaphores from scratch.

Scenario 2: The Device Driver Predicament

Another crucial low-level application is in device drivers communicating with hardware peripherals via memory-mapped I/O.

Imagine a driver that needs to write configuration data to a device's memory buffer and then write a command to a control register to tell the device to process the data.

// Shared memory area for device data buffer
// Memory-mapped control register

// Driver Thread
write_data_to_device_buffer(...);
write_command_to_control_register(CMD_PROCESS_DATA);

The Danger:

The CPU might reorder the writes, making the write_command_to_control_register visible to the hardware before the write_data_to_device_buffer is complete and visible in the device's memory space.

The hardware then starts processing but reads stale or incomplete data from the buffer, leading to incorrect operation or device errors.

The Forbidden Solution: A Driver's Fence

The fix is similar: insert a memory barrier after the data write and before the command write.

// Shared memory area for device data buffer
// Memory-mapped control register

// Driver Thread
write_data_to_device_buffer(...);
// --- Memory Barrier Needed Here ---
// Ensure data writes are visible to the device BEFORE sending command
write_command_to_control_register(CMD_PROCESS_DATA);

This barrier guarantees that all stores to the device buffer are completed and visible to the hardware device before the store to the control register (which triggers the device's action) becomes visible.

The volatile Illusion: Compiler vs. Hardware Fences

A common misconception, especially in older C and C++ programming (pre-C++11/C11), involves the volatile keyword. While related to memory ordering concerns, volatile addresses a different aspect and is not a general solution for inter-thread memory synchronization.

volatile (C/C++): A type qualifier that tells the compiler that a variable's value can be changed by something outside the normal flow of the program (e.g., hardware, another thread). The compiler is instructed not to optimize away or reorder reads/writes to that specific volatile variable relative to other reads/writes to that same volatile variable.

What volatile guarantees is that each access (read or write) to a volatile variable in the source code corresponds to an actual hardware access in the compiled code, and these accesses will happen in the order specified in the source code for that volatile variable.

What volatile does NOT guarantee:

1. Ordering relative to non-volatile accesses: The compiler is free to reorder a volatile access relative to an access to a non-volatile variable.
2. Cache coherence/Visibility to other cores: volatile doesn't issue CPU memory barrier instructions necessary to make the changes visible to other processors or devices. It only affects compiler optimizations.
3. Atomicity: Accesses to volatile variables are not necessarily atomic operations.

Therefore, using volatile alone (e.g., volatile int flag;) for signaling between threads is typically insufficient and incorrect on most modern multiprocessor systems. While it prevents the compiler from optimizing away the loop waiting for flag to change or reordering writes to flag itself, it does nothing about CPU reordering or ensuring that other variables written before flag are visible when flag is finally seen by another thread.

Modern C++ (C++11 and later) provides std::atomic types and explicit memory order specifications (like std::memory_order_acquire, std::memory_order_release) which do generate the necessary compiler directives and CPU memory barrier instructions. This is the correct way to handle inter-thread synchronization in modern standard C++.

When to Embrace the Forbidden Code

For the vast majority of application-level multi-threaded programming using high-level languages and libraries (like Java, C#, Python, or C++ using std::mutex, std::condition_variable, std::atomic), you typically do not need to use explicit memory barrier instructions. The synchronization primitives provided by these environments are carefully implemented using memory barriers internally to provide the required memory visibility semantics.

You must venture into the world of explicit memory barriers when you are:

1. Implementing operating system kernels: Managing shared resources and scheduling across multiple cores.
2. Writing device drivers: Communicating directly with hardware via memory-mapped I/O.
3. Developing custom synchronization primitives: Building mutexes, semaphores, spinlocks, or other synchronization mechanisms from the ground up.
4. Implementing lock-free or wait-free data structures: Complex algorithms designed to avoid traditional locks, relying instead on atomic operations and precise memory ordering.
5. Working with specific hardware architectures: Where standard library abstractions might not apply or you need highly optimized, architecture-specific control.

In these low-level scenarios, a deep understanding of memory models, CPU reordering, compiler optimizations, and the specific memory barrier instructions available on your target architecture (like PowerPC's eieio or ARM's DMB, DSB, ISB) is absolutely critical for writing correct and robust code.

Conclusion

Memory barriers are not just arcane knowledge for kernel hackers; they are fundamental tools for anyone who needs to truly understand and control the behavior of concurrent programs on modern hardware. They are the necessary bridge between the idealized world of sequential program execution and the chaotic, optimized reality of multi-core processors and interacting hardware. While hidden within high-level abstractions for everyday tasks, mastering the concept of memory barriers unlocks the ability to build those very abstractions and to write reliable code in the deepest layers of a system. It's a forbidden art, perhaps, but one essential for true mastery of the machine.