Data Race Freedom à la Mode
Open Access
- 7 January 2025
- journal article
- Published by Association for Computing Machinery (ACM) in Proceedings of the ACM on Programming Languages
- Vol. 9 (POPL) , 656-686
Abstract
We present DRFCaml, an extension of OCaml’s type system that guarantees data race freedom for multithreaded OCaml programs while retaining backward compatibility with existing sequential OCaml code. We build on recent work of Lorenzen et al., who extend OCaml with modes that keep track of locality, uniqueness, and affinity. We introduce two new mode axes, contention and portability , which record whether data has been shared or can be shared between multiple threads. Although this basic type-and-mode system has limited expressive power by itself, it does let us express APIs for capsules , regions of memory whose access is controlled by a unique ghost key, and reader-writer locks , which allow a thread to safely acquire partial or full ownership of a key. We show that this allows complex data structures (which may involve aliasing and mutable state) to be safely shared between threads. We formalize the complete system and establish its soundness by building a semantic model of it in the Iris program logic on top of the Rocq proof assistant.Keywords
This publication has 26 references indexed in Scilit:
- Iris from the ground up: A modular foundation for higher-order concurrent separation logicJournal of Functional Programming, 2018
- LaCasa: lightweight affinity and object capabilities in Scala2016
- The Essence of Dependent Object Types2016
- Uniqueness and reference immutability for safe parallelism2012
- The impact of higher-order state and control effects on local relational reasoningJournal of Functional Programming, 2012
- RELAY2007
- Effective static race detection for Java2006
- RacerXACM SIGOPS Operating Systems Review, 2003
- Capabilities for Sharing2001
- Region-Based Memory ManagementInformation and Computation, 1997