Abstract
Modern multiprocessors employ relaxed memory models that can break the logic of concurrent programs. To ensure Sequential Consistency (SC), programmers must insert memory fences, a task that is error-prone and architecture-specific. We present Musketeer, a tool that uses static analysis and axiomatic memory models to automatically insert fences. By identifying critical cycles in an Abstract Event Graph and solving an optimization problem via Integer Linear Programming, Musketeer achieves high scalability and low performance overhead. Evaluation on real-world codebases like memcached demonstrates that Musketeer can process 10,000 lines of code in seconds with nearly zero overhead on x86 and ARM architectures.
Introduction
Writing concurrent programs is notoriously difficult because modern multiprocessors (like ARM and Power) do not follow the intuitive "Sequential Consistency" (SC) model. To optimize performance, hardware reorders instructions, buffers stores, and relaxes atomicity. While beneficial for single-threaded execution, these optimizations can introduce subtle, non-deterministic bugs in multi-threaded environments.
To restore SC, programmers must insert memory fences. However, manual insertion is challenging due to architecture specificity and the high performance cost of fences. Existing automated tools often rely on operational models that explore every possible thread interleaving, leading to state-space explosion and limiting their use to small programs.
Methods
Musketeer adopts a static approach based on axiomatic memory models rather than operational simulation.
Abstract Event Graph (AEG) and Critical Cycles
The tool builds an AEG, a static over-approximation of all possible executions, mapping memory operations and their relationships (program order and potential communications). It then identifies "critical cycles" within this graph. These cycles represent minimal violations of SC. Breaking every critical cycle by placing a fence on one of its edges guarantees SC.
Optimization and Synthesis
Musketeer treats fence placement as an optimization problem. Using Integer Linear Programming (ILP), it selects the set of fences that breaks all critical cycles at the minimum performance cost. This is particularly useful for architectures like Power, which offer various synchronization mechanisms with different costs. Finally, Musketeer performs a source-to-source transformation to modify the C code, ensuring the compiler does not optimize away the inserted synchronization.
Evaluation
The authors evaluated Musketeer across several benchmark suites, including standard mutual exclusion algorithms (CLASSIC), complex concurrent data structures (FAST), and a large set of executables from Debian Linux, including the high-performance caching system memcached (~10,000 lines of code).
Scalability and Performance
Musketeer demonstrated exceptional scalability, processing memcached in 14 seconds for x86 and 90 seconds for Power—tasks where previous tools timed out. Performance benchmarks on lock-free stacks and queues showed that Musketeer-inserted fences resulted in nearly zero overhead.
As shown in the figure above, Musketeer (M) achieves overheads as low as 0.3% on ARM for a lock-free stack, whereas naive "fence everything" strategies (H) can reach over 30% overhead.
Conclusion
Musketeer represents a significant advancement in automatic fence insertion by prioritizing scalability through static over-approximation. While this approach may occasionally insert redundant fences due to its pessimistic nature, it enables the analysis of real-world software that was previously out of reach. Future work involves improving the underlying pointer analysis to reduce over-approximation and exploring guarantees for liveness and progress.
Summary updated