Reconciling Event Structures with Modern Multiprocessors

Evgenii Moiseenko, Anton Podkopaev, Ori Lahav, Orestis Melkonian, Viktor Vafeiadis

Abstract

Weakestmo is a recently proposed memory consistency model that utilizes event structures to resolve the infamous "out-of-thin-air" (OOTA) problem. While Weakestmo offers significant theoretical advantages, its initial compilation schemes were suboptimal, often requiring more memory fences than necessary. This paper presents the first mechanized proof, conducted in the Coq proof assistant, of the intended efficient compilation schemes for Weakestmo across a variety of hardware memory models, including x86, POWER, ARMv7, ARMv8, and RISC-V. Our approach utilizes an extended Intermediate Memory Model ($IMM_{SC}$) to bridge the gap between high-level event structures and low-level hardware execution graphs.

The Out-of-Thin-Air Problem

In concurrent programming, performance optimizations by compilers and hardware can lead to counter-intuitive behaviors. A particularly dangerous phenomenon is the "out-of-thin-air" (OOTA) bug, where a value appears in a register even though no part of the program logic produced it. Such behaviors break the fundamental reasoning principles of programming languages and can lead to severe security vulnerabilities.

Weakestmo was designed to eliminate OOTA behaviors while still allowing standard optimizations, such as reordering a load after a store. It achieves this using event structures, a mathematical framework that represents multiple possible execution paths simultaneously. However, proving that these complex structures can be safely and efficiently translated into machine code for modern multiprocessors has remained a significant challenge.

A Hub-and-Spoke Compilation Strategy

To prove compilation correctness, the authors adopted a modular "hub-and-spoke" strategy. Rather than proving a direct mapping from Weakestmo to every individual hardware architecture, they utilized the Intermediate Memory Model (IMM) as a central hub.

The hub-and-spoke compilation strategy using IMM_SC as an intermediate bridge.

As shown in the diagram above, the authors extended the existing IMM to support sequentially consistent (SC) accesses, creating $IMM_{SC}$. By proving the correctness of the mapping from Weakestmo to $IMM_{SC}$, they automatically inherited the correctness of the mappings from $IMM_{SC}$ to specific hardware models like x86-TSO, POWER, and ARM, leveraging existing verified infrastructure.

Mechanized Verification in Coq

The core of the work is a machine-checked proof in Coq, comprising approximately 30,000 lines of new code. The central challenge was establishing a simulation relation between the hardware-like execution graphs of IMM and the event structures of Weakestmo.

Hardware models typically analyze a single execution at a time, checking for dependency cycles. In contrast, Weakestmo's event structures represent a forest of possible executions. The proof demonstrates that an event structure can be built incrementally by "traversing" a hardware execution graph. This process involves adding branches to the structure to represent different possible future states, ensuring that every valid hardware execution is justified by a corresponding event structure.

Step-by-step construction of an event structure (a-f) by traversing a hardware execution graph.

Key Results and Impact

This research provides several landmark contributions to the field of formal verification and memory models:

  • First Mechanized Proof: This is the first time a compilation proof for an event-structure-based memory model has been fully mechanized.
  • Efficiency Guaranteed: The proof confirms that Weakestmo can be compiled without the need for "fake" dependencies or excessive fence instructions for relaxed memory accesses, proving it is both safe and performant.
  • Broad Hardware Support: The verification covers a wide range of modern architectures, including the notoriously complex memory models of POWER and ARMv8.
  • Refining the Model: During the mechanization process, the authors identified and corrected several minor deficiencies in the original 2019 definition of Weakestmo, leading to a more robust specification.

Limitations and Future Work

While the proof is comprehensive, some areas remain for future optimization. Currently, Read-Modify-Write (RMW) operations on ARMv8 are handled via older load-exclusive/store-conditional loops. Future work could extend the IMM framework to support newer, single-instruction RMWs like CAS. Additionally, the authors suggest that the constraints within IMM itself could be further weakened to allow even more aggressive optimizations on ARMv8 platforms. Finally, comparing Weakestmo's approach to other modern models, such as Promising-ARM, remains an active area of research.

Summary updated

Abstract

Weakestmo is a recently proposed memory consistency model that uses event structures to resolve the infamous "out-of-thin-air" problem. Although it has been shown to have important benefits over other memory models, its established compilation schemes are suboptimal in that they add more fences than necessary. In this paper, we prove the correctness in Coq of the intended compilation schemes for Weakestmo to a range of hardware memory models (x86, POWER, ARMv7, ARMv8, RISC-V). Our proof is the first that establishes correctness of compilation of an event-structure-based model that forbids "thin-air" behaviors, as well as the first mechanized compilation proof of a weak memory model supporting sequentially consistent accesses to such a range of hardware platforms. Our compilation proof goes via the recent Intermediate Memory Model (IMM), which we suitably extend with sequentially consistent accesses.
BibTeX
@inproceedings{moiseenko2020reconciling,
  author = {Evgenii Moiseenko and Anton Podkopaev and Ori Lahav and Orestis Melkonian and Viktor Vafeiadis},
  title = {{Reconciling Event Structures with Modern Multiprocessors}},
  booktitle = {ECOOP},
  year = {2020},
  doi = {10.4230/lipics.ecoop.2020.5},
}
Figure