An approach for modularly verifying the core of Rust’s atomic reference counting algorithm against the (X)C20 memory consistency model
Bart Jacobs and Justus Fasse · 2025
Read An approach for modularly verifying the core of Rust’s atomic reference counting algorithm against the (X)C20 memory consistency model by Bart Jacobs and Justus Fasse (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2505-00449.txt.
Introduction
Bart Jacobs and Justus Fasse verify shared memory code in this 2025 paper. Their target is the core of Rust's atomic reference counting, a scheme that frees shared data when the last user lets go. Relaxed memory rules, which let processors reorder accesses, make such code hard to prove correct.
Their modular approach suits programs built from relaxed atomic accesses and fences. They argue it is sound under the C20 memory model when paired with a simple static analysis, admitting one open sub-problem. Under a slightly strengthened model that bans out of thin air values, the approach stands alone, with no analysis and no assumptions. They define step by step semantics, prove them sound, and plug into existing concurrency logics.
Catalog record
| CREATOR | Bart Jacobs and Justus Fasse |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 59 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2505-00449
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
An approach for modularly verifying the core of Rust’s atomic reference counting algorithm against the (X)C20 memory consistency model Bart Jacobs and Justus Fasse Abstract We propose an approach for modular verification of programs that use relaxed-consistency atomic memory access primitives and fences, sufficient for verifying the core of Rust’s Atomic Reference Counting (ARC) algorithm, and we argue its soundness, when combined with a simple static analysis and admitting an open sub-problem, with respect to the C20 memory consistency model, as well as, even in the absence of any static analysis and without any assumptions, with respect to XC20, a recently proposed minor strengthening of C20 that rules out out-of-thin-air behaviors but allows load buffering. In contrast to existing work on verifying ARC, we do not assume acyclicity of the union of the program-order and reads-from relations. We define an interleaving operational semantics, prove its soundness with respect to (X)C20’s axiomatic semantics, and then apply any existing program logic for fine-grained interleaving concurrency, such as Iris. 1 Introduction Most work on modular verification of shared-memory multithreaded programs so far (e.g. [ 9 , 8 ] ) has assumed sequential consistency , i.e. that in each execution of the program, there exists some total order on the memory accesses such that each read access yields the value written by the most recent preceding write access in this total order. However, for performance reasons, many real-world concurrent algorithms, such as Rust’s Atomic Reference Counting (ARC) algorithm 1 1 1 https://doc.rust-lang.org/std/sync/struct.Arc.html , use relaxed-consistency memory accesses that do not respect such a total order. \begin{array}[]{c | c | c}&&\\ \begin{array}[]{c}X=Y=0\\ \begin{array}[]{l || l}a=X;&\,b=Y;\\ \mathbf{if}(a==1)&\,\mathbf{if}(b==1)\\ \quad Y=1;&\quad X=1;\end{array}\\ a=b=1\\ (\textrm{LBD})\end{array}&\begin{array}[]{c}X=Y=0\\ \begin{array}[]{l || l}a=X;&\,b=Y;\\ Y=1;&\,X=1;\end{array}\\ a=b=1\\ \\ (\textrm{LB})\end{array}&\begin{array}[]{c}X=Y=0\\ \begin{array}[]{l || l}a=X;&\,b=Y;\\ \mathbf{fence}_{\mathsf{acq}};&\,\mathbf{fence}_{\mathsf{acq}};\\ Y=1;&\,X=1;\end{array}\\ a=b=1\\ (\textrm{LBf})\end{array}\\ &&\end{array} Figure 1: Three memory consistency litmus tests Consider the three litmus tests LBD, LB, and LBf in Fig. 1 , small concurrent programs accompanied by a precondition X=Y=0 and a postcondition a=b=1 . We say the behavior specified by a litmus test is observable if the program has an execution that satisfies the pre- and postcondition. When implemented using relaxed accesses, the LB ( load buffering ) behavior is observable, because of instruction reorderings performed by the compiler and/or the processor. Since acquire fences have no effect in the absence of release operations, so is the LBf behavior. The LBD behavior, however, known as an out-of-thin-air (OOTA) behavior, is not observable on any real execution platform. Recent editions of the C standard attempt to precisely describe the concurrency behaviors that a C implementation is allowed to exhibit, by listing a number of axioms that each execution must satisfy. We refer to the formalization thereof used in [ 10 ] as C20. These axioms allow the LB and LBf behaviors; unfortunately, since the C20 concept of an execution does not consider dependencies, it cannot distinguish LBD from LB and allows it too. Strengthening C20 to rule out OOTA behaviors like LBD while still allowing all desirable optimizations, such as the reorderings exhibited by LB, has been a long-standing open problem. In the meantime, most work on modular verification of relaxed-consistency programs [ 11 , 4 , 5 , 3 ] , has assumed the absence of cycles in the union of program order ( \mathsf{po} , the total order on a thread’s memory accesses induced by the program’s control flow) and the reads-from ( \mathsf{rf} ) relation relating each write event to the read events that read from it, thus ruling out not just LBD but LB (and LBf) as well, but enabling soundness proofs of program logics by induction on the size of (\mathsf{po}\cup\mathsf{rf})^{+} prefixes of the execution. A breakthrough was achieved, however, with the very recent proposal of XMM [ 10 ] , a framework for concurrency semantics based on re-execution , that given an underlying memory model, restricts it very slightly to rule out OOTA behaviors, without ruling out \mathsf{porf} cycles altogether. Specifically, XMM incrementally builds executions through Execute steps and Re-Execute steps. An Execute step adds an event that reads from an existing event; it never introduces a \mathsf{porf} cycle. A Re-Execute step fixes an \mathsf{rf}^{-1} -closed subset of the events of the original execution, called the committed set , and then re-builds an execution from scratch, where read events may temporarily “read from nowhere” but only if they are in the committed set . Re-Execute steps enable the construction of \mathsf{porf} cycles, but the values read are grounded by an earlier execution. Applying XMM to C20 yields XC20, which allows LB (and LBf) but rules out LBD. In this paper, we propose an approach for modularly verifying relaxed-consistency programs that is sound in the presence of \mathsf{porf} cycles. We use the core of ARC as a motivating example; its code and intended separation logic specification are shown in Fig. 2 . Function \mathsf{alloc}(v) allocates an ARC instance whose payload is v . Every owner of a permission to access the ARC instance at address a holding payload v (denoted \mathsf{arc}(a,v) ) can read the payload using function \mathsf{get}(a) , implemented using a simple nonatomic read. Function \mathsf{clone}(a) duplicates the permission to access a , and \mathsf{drop}(a) destroys it. When the last permission is destroyed, the instance is deallocated. The first field of the ARC data structure is a counter, initialized to 1, incremented at each \mathsf{clone} using a relaxed-consistency fetch-and-add (FAA) instruction, and decremented at each \mathsf{drop} . Since the decrements have release consistency, they all synchronize with the acquire fence in the thread that reads counter value 1, ensuring that the deallocation does not race with any of the accesses. \begin{array}[]{l l}\begin{array}[]{l}\mathsf{alloc}(v)=\\ \quad{\color[rgb]{0,0,1}\{\mathsf{True}\}}\\ \quad\mathbf{cons}(1,v)\\ \quad{\color[rgb]{0,0,1}\{r.\;\mathsf{arc}(r,v)\}}\\ \\ \mathsf{get}(a)=\\ \quad{\color[rgb]{0,0,1}\{\mathsf{arc}(a,v)\}}\\ \quad[a+1]_{\mathbf{na}}\\ \quad{\color[rgb]{0,0,1}\{r.\;\mathsf{arc}(a,v)\land r=v\}}\\ \\ \mathsf{clone}(a)=\\ \quad{\color[rgb]{0,0,1}\{\mathsf{arc}(a,v)\}}\\ \quad\mathbf{FAA}_{\mathbf{rlx}}(a,1)\\ \quad{\color[rgb]{0,0,1}\{\mathsf{arc}(a,v)*\mathsf{arc}(a,v)\}}\\ \end{array}&\begin{array}[]{l}\mathsf{drop}(a)=\\ \quad{\color[rgb]{0,0,1}\{\mathsf{arc}(a,v)\}}\\ \quad\mathbf{let}\ n=\mathbf{FAA}_{\mathbf{rel}}(a,-1)\ \mathbf{in}\\ \quad\mathbf{if}\ n=1\ \mathbf{then}\ (\\ \quad\quad\mathbf{fence}_{\mathbf{acq}};\\ \quad\quad\mathbf{free}(a);\mathbf{free}(a+1)\\ \quad)\\ \quad{\color[rgb]{0,0,1}\{\mathsf{True}\}}\\ \end{array}\end{array} Figure 2: Core ARC, with desired specs As we will show, this algorithm is correct under C20 provided that the following two properties hold : All accesses of the counter are either increments or release decrements. (1) No access of the counter reads a value v\leq 0 . (2) (In particular, clearly, the presence of relaxed decrements would break the algorithm.) Verifying ( 1 ) or ( 2 ) using separation logic is tricky, and we don’t know how to do it. Indeed, consider LBf above. Suppose that we want to verify that all modifications of X and Y are release writes, so that they synchronize with the acquire fences. The problem here is that both writes are behind fences; to reason about the fences, we would have to assume the property before verifying it, which is unsound. Instead, we simply assume these properties. Actually, ( 1 ) can be verified using some syntactic approach, such as using a Java-like static type system to syntactically check all accesses of the \mathsf{Arc.counter} field. For ( 2 ), in contrast, we have no suggestions; we leave it as an open problem. In § 2 , we propose an approach for verifying programs under C20, under certain assumptions to be checked by other means, and we use it to verify Core ARC. Specifically, we propose an operational semantics (opsem) for C20 programs instrumented with an atomic specification