Reconciling Event Structures with Modern Multiprocessors

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

TL;DR

This paper provides the first mechanized proof that Weakestmo, a modern concurrency model designed to eliminate "out-of-thin-air" (OOTA) bugs, can be correctly and efficiently compiled to major hardware architectures like x86, ARM, and POWER. By extending an intermediate memory model (IMM) and using the Coq proof assistant, the authors bridge the gap between high-level language semantics and low-level hardware execution.

What Problem Does This Paper Address?

In the world of concurrent programming, compilers and hardware often reorder instructions to boost performance. However, if these reorderings are too aggressive, they can lead to "out-of-thin-air" (OOTA) behaviors—where a value appears in a register despite no part of the program ever producing it. This makes programs impossible to reason about and creates massive security holes.

The Weakestmo model was recently proposed to solve this. It uses a mathematical framework called event structures to allow common optimizations (like reordering a load after a store) while strictly forbidding OOTA cycles. While Weakestmo looked good on paper, its "compilation correctness"—the guarantee that it doesn't break when translated into the machine code that runs on your phone or laptop—had never been formally proven. Previous attempts were "suboptimal," meaning they forced the compiler to add unnecessary, slow "fence" instructions just to stay safe.

Methods

The authors used the Coq proof assistant to build a rigorous, machine-checked mathematical proof. Their strategy relied on a "hub-and-spoke" approach:

  1. The Intermediate Bridge: Instead of proving correctness for every hardware type individually, they used the Intermediate Memory Model (IMM). IMM acts as a middle ground that looks like hardware but is easier to reason about.
  2. Extending the Hub: They extended IMM to support sequentially consistent (SC) accesses (the strictest type of memory access), creating a more robust version called $IMM_{SC}$.
  3. The Simulation Relation: The core of the work is a complex "simulation" proof. They showed that for every valid execution allowed by the hardware-like IMM, there exists a corresponding "event structure" in Weakestmo that justifies it.
  4. Step-by-Step Traversal: They proved that an event structure can be built incrementally by "traversing" a hardware execution graph, carefully adding branches to represent different possible futures (a technique borrowed from "promising semantics").

Datasets

As a theoretical paper in formal verification, this work does not use traditional datasets. Instead, the "data" consists of:

  • Formal Hardware Models: Existing mathematical definitions of x86-TSO, POWER, ARMv7, and ARMv8.
  • The Coq Development: A massive codebase of approximately 30,000 lines of new Coq code, built on top of an existing 20,000-line infrastructure.

Key Insights and Ideas

  • Reconciling Two Worlds: Hardware models usually look at a single execution and check for dependency cycles. Weakestmo looks at multiple possible executions simultaneously (the event structure). The paper’s "aha moment" is the formal method for mapping these two fundamentally different ways of thinking about time and causality.
  • Efficiency Matters: Unlike previous work, this proof establishes that you don't need "fake" dependencies or extra fences for relaxed memory accesses. This confirms that Weakestmo is not just safe, but also fast.
  • The Power of Modularity: By proving the mapping from $Weakestmo \to IMM$, the authors automatically gained correctness for x86, ARM, and POWER by leveraging existing proofs that map $IMM \to Hardware$.

Key Results

  • First of its Kind: This is the first mechanized compilation proof for any event-structure-based memory model.
  • Broad Support: The proof covers a wide range of hardware, including the complex memory models of POWER and ARMv8.
  • Bug Squashing: During the mechanization process, the authors discovered and fixed several minor deficiencies in the original 2019 definition of Weakestmo.
  • SC Accesses: The work provides the first mechanized proof for a weak memory model supporting sequentially consistent accesses across such a diverse range of platforms.

Limitations and Future Work

  • ARMv8 RMW Instructions: Due to technical limitations in the current IMM framework, the proof handles Read-Modify-Write (RMW) operations on ARMv8 using older "load-exclusive/store-conditional" loops rather than the newer, more specialized single-instruction RMWs (like CAS or LDADD).
  • Weakening IMM: The authors note that IMM currently enforces a very strict ordering between RMW events and subsequent accesses. They suggest that future work could involve weakening these constraints to allow even more efficient compilation to ARMv8.
  • Alternative Models: While they proved Weakestmo is correct, they acknowledge that other models (like Promising-ARM) exist, and a direct comparison or a unified proof remains an open challenge.

Summary updated

Abstract

Weakestmo is a recently proposed memory consistency model that uses event structures to resolve the infamous "out-of-thin-air" problem and to enable efficient compilation to hardware. Nevertheless, this latter property - compilation correctness - has not yet been formally established. This paper closes this gap by establishing correctness of the intended compilation schemes from Weakestmo to a wide range of formal hardware memory models (x86, POWER, ARMv7, ARMv8) in the Coq proof assistant. Our proof is the first that establishes correctness of compilation of an event-structure-based model that forbids "out-of-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},
}

Loading related content...

Figure