Don't Sit on the Fence: A Static Analysis Approach to Automatic Fence Insertion

Jade Alglave, Daniel Kroening, Vincent Nimal, Daniel Poetzl

TL;DR

The paper introduces musketeer, a tool that uses static analysis and axiomatic memory models to automatically insert memory fences into concurrent code. By trading a small amount of precision for massive scalability, musketeer can handle real-world codebases like memcached (~10,000 lines of code) while ensuring Sequential Consistency (SC) with significantly lower performance overhead than existing automated methods.

What Problem Does This Paper Address?

Writing concurrent programs is notoriously difficult because modern multiprocessors (like ARM and Power) do not follow the intuitive "Sequential Consistency" (SC) model. To squeeze out performance, hardware reorders instructions, buffers stores, and relaxes atomicity. While these optimizations speed up single-threaded execution, they can break the logic of multi-threaded programs.

To restore order, programmers must insert memory fences (or barriers). However, manual fence insertion is a nightmare:

  1. Architecture Specificity: A fence on x86 (like mfence) behaves differently than fences on Power (like sync or lwsync).
  2. Performance Costs: Fences are expensive. Put too many in, and your performance tanks; put too few, and your code has subtle, non-deterministic bugs.
  3. Scalability: Existing "precise" tools for automatic fence insertion rely on exploring every possible thread interleaving. This leads to a state-space explosion, limiting them to programs with only a few hundred lines of code.

Methods

The authors propose a static approach that moves away from "operational" models (simulating every step) toward axiomatic models.

  1. Abstract Event Graph (AEG): Instead of executing the code, musketeer builds a static over-approximation of all possible executions. It maps out memory reads and writes and the relationships between them (program order and potential communications).
  2. Critical Cycle Detection: Drawing on established theory, the authors identify "critical cycles" in the AEG. These cycles represent the minimal violations of SC. If you "break" every critical cycle by placing a fence on one of its edges, you guarantee the program will behave as if it were sequentially consistent.
  3. Integer Linear Programming (ILP): Since architectures like Power offer multiple types of synchronization (full fences, lightweight fences, or data dependencies), musketeer treats fence placement as an optimization problem. It uses ILP to find the set of fences that breaks all critical cycles at the lowest "cost" (performance penalty).
  4. Source-to-Source Transformation: Musketeer automatically modifies C code, inlining assembly fences or rewriting code to enforce dependencies that the compiler cannot optimize away.

Datasets

The authors evaluated musketeer against several suites:

  • CLASSIC: Standard mutual exclusion algorithms (e.g., Dekker, Peterson, Lamport’s fast mutex).
  • FAST: Complex concurrent data structures and work-stealing queues (e.g., Chase-Lev queue, Michael & Scott FIFO).
  • DEBIAN: A massive set of over 350 executables from Debian Linux 7.1. This includes the high-performance caching system memcached (~10,000 LoC), which served as the primary "stress test" for scalability.

Key Insights and Ideas

  • Precision vs. Scalability: The "aha moment" is that you don't need to explore every interleaving to be safe. By using a static over-approximation, you might insert a few "extra" fences that aren't strictly necessary, but you gain the ability to analyze programs that are orders of magnitude larger than what previous tools could handle.
  • Cost-Aware Synthesis: On architectures like Power, a data dependency is much cheaper than a full sync fence. Musketeer is unique because its ILP solver understands these cost hierarchies, allowing it to choose the most efficient synchronization mechanism for a specific architectural "delay."
  • Handling the Compiler: The authors realized that simply adding fences isn't enough; compilers often try to optimize them away. They developed techniques to "fence the compiler" using inline assembly and volatile variables to ensure the hardware actually sees the intended synchronization.

Key Results

  • Scalability: Musketeer successfully processed memcached in roughly 14 seconds for x86 and 90 seconds for Power. Previous state-of-the-art tools (like trencher or memorax) simply timed out or crashed on code of this size.
  • Performance: In benchmarks on a lock-free stack and queue, musketeer-inserted fences resulted in nearly zero overhead on x86 (0.6%) and very low overhead on ARM (0.3%). In contrast, naive "fence everything" strategies saw overheads as high as 25-30%.
  • Comparison: Musketeer proved to be the most precise of all existing static analysis methods, meaning it inserts fewer unnecessary fences than its static predecessors while remaining much faster than dynamic/operational tools.

Limitations and Future Work

  • Over-approximation: Because the tool is static, it is inherently "pessimistic." It may detect critical cycles that can never actually happen in a real execution, leading to the insertion of redundant fences.
  • Pointer Analysis Dependency: The accuracy of the AEG depends heavily on the quality of the underlying pointer analysis. If the analysis can't determine which variables a pointer might hit, musketeer must assume the worst, potentially bloating the fence count.
  • Liveness and Progress: The current tool focuses on safety (preventing bad behaviors) but does not explicitly guarantee liveness (ensuring the program doesn't lock up), though the authors note that restoring SC generally helps with stability.

Summary updated

Abstract

Modern architectures rely on memory fences to prevent undesired weakenings of memory consistency. As the fences’ semantics may be subtle, the automation of their placement is highly desirable. But precise methods for restoring consistency do not scale to deployed systems’ code. We choose to trade some precision for genuine scalability: our technique is suitable for large code bases. We implement it in our new musketeer tool and report experiments on more than 700 executables from packages found in Debian GNU/Linux 7.1, including memcached with about 10,000 LoC.
BibTeX
@article{alglave2014don,
  author = {Jade Alglave and Daniel Kroening and Vincent Nimal and Daniel Poetzl},
  title = {{Don't Sit on the Fence: A Static Analysis Approach to Automatic Fence Insertion}},
  journal = {ACM Trans. Program. Lang. Syst.},
  year = {2014},
}
Figure