Strong Logic for Weak Memory: Reasoning About Release-Acquire Consistency in Iris
Jan-Oliver Kaiser, Hoang-Hai Dang, Derek Dreyer, Ori Lahav, and Viktor Vafeiadis
Max Planck Institute for Software Systems (MPI-SWS)
The field of concurrent separation logics (CSLs) has recently undergone two exciting developments: (1) the Iris framework for encoding and unifying advanced higher-order CSLs and formalizing them in Coq, and (2) the adaptation of CSLs to account for weak memory models, notably C11's release-acquire (RA) consistency. Unfortunately, these developments are seemingly incompatible, since Iris only applies to languages with an operational interleaving semantics, while C11 is defined by a declarative (axiomatic) semantics.
In this paper, we show that, on the contrary, it is not only feasible but useful to marry these developments together. Our first step is to provide a novel operational characterization of RA+NA, the fragment of C11 containing RA accesses and "non-atomic" (normal data) accesses. Instantiating Iris with this semantics, we then derive higher-order variants of two prominent RA+NA logics, GPS and RSL. Finally, we deploy these derived logics in order to perform the first mechanical verifications (in Coq) of several interesting case studies of RA+NA programming. In a nutshell, we provide the first foundationally verified framework for proving programs correct under C11's weak-memory semantics.
Papers
- Full paper with appendix, in ECOOP 2017 [Best Paper Award].
Talks
-
Talk at ECOOP 2017, Barcelona (22 June 2017):
- Online presentation
- Full HD video (better video, poorer audio)
- Video by ECOOP (better audio, poorer video)
- Talk at Aarhus Concurrency Workshop (31 May 2017): PDF | Online presentation.
Resources
- Coq repository, with README containing mapping between the paper and the Coq development, and instructions to build from source.
- A VirtualBox-based VM [VM description], that is pre-configured with a copy of the Coq development, for quick testing.
- DRAFT in progress: Technical report (June 2017).