Mechanized verification of a fine-grained concurrent queue from meta’s folly library
Open Access
- 11 January 2022
- conference paper
- Published by Association for Computing Machinery (ACM)
- p. 100-115
Abstract
We present the first formal specification and verification of the fine-grained concurrent multi-producer-multi-consumer queue algorithm from Meta’s C++ library Folly of core infrastructure components. The queue is highly optimized, practical, and used by Meta in production where it scales to thousands of consumer and producer threads. We present an implementation of the algorithm in an ML-like language and formally prove that it is a contextual refinement of a simple coarse-grained queue (a property that implies that the MPMC queue is linearizable). We use the ReLoC relational logic and the Iris program logic to carry out the proof and to mechanize it in the Coq proof assistant. The MPMC queue is implemented using three modules, and our proof is similarly modular. By using ReLoC and Iris’s support for modular reasoning we verify each module in isolation and compose these together. A key challenge of the MPMC queue is that it has a so-called external linearization point, which ReLoC has no support for reasoning about. Thus we extend ReLoC, both on paper and in Coq, with novel support for reasoning about external linearization points.Keywords
Funding Information
- NWO (016.Vidi.189.046)
- Villum Fonden (25804)
This publication has 40 references indexed in Scilit:
- Impredicative Concurrent Abstract Predicates2014
- Communicating State Transition Systems for Fine-Grained Concurrent Resources2014
- Abstraction for concurrent objectsTheoretical Computer Science, 2010
- Concurrent Abstract Predicates2010
- Local Reasoning for Storable Locks and Threads2007
- A Marriage of Rely/Guarantee and Separation LogicLecture Notes in Computer Science, 2007
- BI-hyperdoctrines, higher-order separation logic, and abstractionACM Transactions on Programming Languages and Systems, 2007
- Algorithms for scalable synchronization on shared-memory multiprocessorsACM Transactions on Computer Systems, 1991
- Linearizability: a correctness condition for concurrent objectsACM Transactions on Programming Languages and Systems, 1990
- Why Functional Programming MattersThe Computer Journal, 1989