Vardalith: Hybrid Detection of Persistent Memory Concurrency Bugs

To illustrate the advantages of PIFRs, consider Figure 1, which shows a program, inspired by a few of the bugs detailed in § 6.2, with two threads (left) and a lattice of all possible interleavings (right).

Thread $t_1$ begins by getting a pointer to a PM variable $x$ (line A:1). The value of $x$ is determined dynamically by the result of the function call, but for the sake of the example, we assume $x$ is the same for both threads. Then, $t_1$ checks an unlikely condition (line A:2), for instance, to trigger a data structure resizing operation. If the condition is true, it performs an acquire over resource $b$, computes value $y$, stores it in $x$, performs a call to an auxiliary function that eventually persists $x$, and releases resource $b$ (lines A:3–7). Otherwise, if the condition is false, it performs an acquire over resource $a$, computes value $z$, stores it in $x$, releases resource $a$, persists $x$, and performs some cleanup (lines A:9–13). Concurrently, thread $t_2$ acquires resource $a$, loads the value of $x$, releases resource $a$, and returns the value (lines B:1–5).

Note that in the lattice, and for simplicity, we represented all lines as atomic operations, although they are split across multiple machine instructions.

Let us first consider the case where the unlikely condition is true. In this case, there is an interleaving that triggers a PIR if $t_2$ executes line B:3 after $t_1$ executes line A:6 but before line A:7, since $t_2$ observes the store done by $t_1$ before its explicit persistence. In this case, there is also a conventional data race, detectable by regular tools, since both threads access the same address without proper synchronization.

Existing approaches [11, 25] must observe this specific interleaving (denoted with a red bolt $R_1$) to detect the race. The key advantage of our approach is that we are able to detect the race in a substantially larger set of interleavings. In particular, as long as we observe an execution where the Load PIFR of $t_2$, $LP$, overlaps with the Store PIFR of $t_1$, $S{P}_1$, denoted with orange arrows, we report a race. This means that there are multiple interleavings that do not trigger the race, and thus are not detected by existing tools, but are detected by Vardalith and guarantee the existence of the PIR in at least some interleaving.

Next, we analyze the case where the unlikely condition is false (the common case). In this case, both accesses are synchronized correctly, however the persistency occurs outside the synchronized region. Similarly, there is a specific interleaving (denoted with red bolt $R_2$) that triggers a PIR if $t_2$ executes line B:3 after $t_1$ executes line A:10 but before line A:12. Since line A:10 and B:3 are properly synchronized, this also represents a very narrow window. Consequently, existing tools must either repeatedly execute these code segments in the hope of observing this specific interleaving, or steer the execution to force it to happen. This results in an undesirable trade-off between execution time and coverage. In contrast, since the PIFRs $S{P}_2$ and $LP$ overlap in both cases, Vardalith reports a PIR in both. Moreover, $S{P}_2$ never closes because $t_1$ does not perform any release action after the store is explicitly persisted. Hence, this PIFR will extend until $t_1$ performs another release action, or until the end of the program, further widening the detection window. As such, this means that any interleaving that includes one of the transitions marked in orange will inevitably be detected by Vardalith as a PIR. Note that this is not a conventional data race and therefore existing volatile data race detectors [20, 21, 23] would not detect a race in any interleaving where $t_1$ takes the else branch since the memory accesses are properly synchronized, highlighting a key semantic difference between detecting PIRs and conventional data races.

We formally define PIRs and PIFRs over execution traces and prove our first main result establishing that if a Store PIFR for a thread $t_1$ overlaps with a Load PIFR for a thread $t_2$, then threads $t_1$ and $t_2$ can execute in a way that causes a persistency-induced race.

Before formalizing the result and its proof, we must first establish the program execution model. We assume the PM Intel x86-TSO memory model [75]: memory visibility follows x86-TSO consistency, while durability is decoupled from visibility. This means that writes may become visible without being persistent, and persistence is guaranteed only after explicit flush and ordering fence instructions. Since release actions imply a memory fence, we focus on flushes. Additionally, we assume stores are explicitly persisted by the thread that issued them. As such, we do not model cross-thread persistence (i.e., one thread explicitly persisting another thread’s store), which we treat as out of scope for this formalization (see § 8.1 for a discussion on this design choice).

Following previous work [20], we model program executions as triples $(A,{\le }_{sb},{\le }_{sw})$, where:

• $\mathrm{■}$

  $A$ is a set of actions, with each action $a\in A$ consisting of a triple $(t,k,u)$, written ${𝐤}^t(u)$ for short, where: (1) $k$ is the type of action, (2) $t$ is a thread identifier, and (3) $u$ is the unique action identifier. We do not detail all the types of actions that occur during the execution, but assume that there are: persistent memory stores, ${𝐬}_x$, persistent memory loads, ${𝐥}_x$, and persistency instructions, ${𝐩}_x$, where $x$ denotes the target address.

• $\mathrm{■}$

  The sequenced-before relation, ${\le }_{sb}$, totally orders actions that happen within the same thread.

• $\mathrm{■}$

  The synchronizes-with relation, ${\le }_{sw}$, orders synchronization actions; $u_1{\le }_{sw}{u}_2$ implies that $u_1$ is the identifier of a release action and $u_2$ is the identifier of an acquire action for the same synchronization primitive.

The standard happens-before relation, ${\le }_{hb}$, is simply the reflexive-transitive closure of the union of ${\le }_{sb}$ and ${\le }_{sw}$; put formally: ${\le }_{hb}\triangleq {({\le }_{sb}\cup {\le }_{sw})}^{\ast }$.

In order to formally define the concept of PIR, we need to first formalize the concept of non-persistency window. Intuitively, a non-persistency window corresponds to the fragment of the execution that spans from a persistent memory store to its explicit persistency. Formally, two actions ${𝐬}_x^t(u_s)$ and ${𝐩}_x^t(u_p)$ are said to form a non-persistency window, written as ${𝕎}_x^t⟨u_s,u_p⟩$, if and there is no action ${𝐩}_x^t(u_p^{\prime })$ such that . Given that, a PIR occurs when a load for a given persistent memory address $x$ can occur during a non-persistency window for that memory address belonging to another thread. Put formally:

Next, we formalize Load PIFRs and Store PIFRs over ordered sequences of actions:

We say that a Store PIFR, $𝕊{\mathbb{P}}_x^{t_1}⟨u_b,u_e⟩$ overlaps with a Load PIFR, $𝕃{\mathbb{P}}_x^{t_2}⟨u_b^{\prime },u_e^{\prime }⟩$, if there exists a scheduling of threads $t_1$ and $t_2$ that does not force one of the regions to end before the other begins; put formally: if and . Finally, we prove our first main result: if a Store PIFR for a thread $t_1$ overlaps with a Load PIFR for a thread $t_2$, then threads $t_1$ and $t_2$ can execute in a way that causes a PIR to occur. Theorem 3 captures this intuition.

Vardalith’s pipeline is divided into three stages, as depicted in Figure 4. The first stage takes the program binary as input and uses static analysis to determine the PIFR starts (§ 4.1.1). The second stage instruments the binary with calls to our runtime whenever the program enters a PIFR or performs a call with release semantics, which may delimit PIFR ends (§ 4.1.2). Finally, the third stage takes a user-provided workload as input and performs a series of testing runs of the instrumented binary (§ 4.1.3).

In this section, we describe Vardalith ’s static analysis algorithm. We first introduce the necessary preliminaries (§ 4.2.1), then present the algorithm itself (§ 4.2.2), walk through an example execution (§ 4.2.3), and conclude with a proof of correctness (§ 4.2.4).

Working at the binary level has advantages, such as generality and practicality, but also implementation challenges and drawbacks, most notably the concept of target address and scope. Approaches that work over source code or intermediate representations, such as LLVM IR [49], have variable names with scopes defined. In contrast, in compiled binaries, accesses are performed on memory operands. For x86, these operands are represented as base_register + (index_register * scale) + displacement, with some parameters being optional. The same expression might refer to different memory locations within the same function, especially since compilers reuse registers when possible. To address this, for each PM access we capture its destination operand (if the access is a store) or source operand (if the access is a load) and save the respective expression, together with the registers it depends upon. For example, if the original access is mov [rax], rdx, which stores the value of rdx in the address stored in rax, then the target expression is a single register, rax. During backwards analysis, for each processed instruction that writes to any of the relevant registers, we update the expression accordingly so that we can recompute the original address.

The base design of Vardalith does not actively steer the execution towards specific interleavings. Instead, it executes the program under test and detects overlapping PIFRs dynamically. To complement the base design, we implemented two additional optional features in the prototype: sampling and scheduling. Sampling offers a configurable trade-off between execution time and coverage. Although Vardalith is generally fast, certain testing scenarios can take more time than desired, for instance if Vardalith is included as part of the build process to check for PIRs as the code is developed. Vardalith can be configured with a sampling rate of $1/n$, in which case it only keeps track of $1$ out of $n$ PIFRs. This reduces bookkeeping costs and testing time but since fewer PIFRs are open at any given time, it also reduces coverage. We study this trade-off in § 6.4.

We also implemented a delay injection-based scheduling component, whose goal is twofold. First, we want to assess the extent to which PIFR’s larger windows can still benefit from guiding the execution to specific interleavings. Second, we use it as a baseline, to compare the effects of enlarging the detection windows with PIFRs versus doing so through delay injection to force specific interleavings. Following previous works on race detection [54, 88], we implemented an active delay injection mechanism paired with a probability decay. Each time we reach a release action and before closing the respective PIFR, we inject a delay with probability $p$ (starting at 100%). After the delay, we assess whether any races were detected during that period. If no races were found, we decrease the probability of injecting a delay at that point by a configurable constant. This tries to minimize the delays at ineffective locations, and maximize the chances of finding PIRs while minimizing the testing time required to do so. We evaluate the effectiveness of active delay injection, both standalone and in combination with PIFRs in § 6.3 and § 6.4.

Our implementation assumes that synchronization is used explicitly, as the result of function calls (e.g., a call to a mutex lock function, semaphore, or a conditional variable). These functions can sometimes be inlined for performance, but debug builds generally do not perform this inlining and therefore suffice for Vardalith. Nevertheless, the use of C/C++ macros to define synchronization primitives can be problematic since these are inlined even in debug builds. In such cases, the programmer needs to wrap/replace the macros with inlined function calls, so that these calls are present on debug binaries but optimized in release builds. This is a simple change that we performed manually on P-CLHT [50] by modifying less than 20 lines.

We used a dual-socket 64 core Intel Xeon Gold 6338N, with 256 GB of RAM, and 1 TB Intel DCPMM, running Ubuntu 22.04 with Linux kernel 5.15.

We analyzed 12 programs: P-CLHT [50], FAST-FAIR [37], Memcached [52], Apex [61], and WIPE [96] using the authors’ implementation [89, 45, 53, 60, 95]; SEPH [92], Level Hashing [105], Clevel Hashing [10] and CCEH/CCEH-CoW [67], using SEPH’s benchmark and implementations [64]; and P-ART and P-Masstree [50] using the implementations provided by Durinn [46], as was done in [72]. All experiments ran using 8 threads and workloads of 1k, 10k, and 100k operations, with the exception of P-ART since this implementation does not work with workloads larger than 1k operations [72]. The P-CLHT and SEPH benchmarks use a YCSB [13] workload with a single-threaded load phase, followed by 50% gets and 50% updates. FAST-FAIR uses its own benchmark, which performs inserts/updates/gets/deletes. Memcached uses a Python client that performs all the operations available in the protocol in round-robin fashion. All workloads access keys following a zipfian distribution.

Vardalith found 26 bugs, 7 of which are new. For comparison, PMRace [11] found 8 bugs (4 new), labeled as PM inter-thread inconsistency in the original paper, Durinn [25] found 10 bugs (10 new), labeled as visible-but-not-durable bugs in the original paper, and HawkSet [72] found 20 bugs (7 new). The results are summarized in Table 1, where we also report when multiple read/write accesses trigger the same bug. Considering the intersection of evaluated systems, Vardalith finds all bugs reported by PMRace on P-CLHT, FAST-FAIR, and Memcached, and all bugs reported by HawkSet on FAST-FAIR, P-CLHT, P-Masstree, P-ART, Memcached, WIPE, and APEX, i.e., all bugs listed in those tools’ evaluation tables for the overlapping systems. Durinn works at the operation level and hence reports bugs at the operation declaration rather than at the PM access as done by Vardalith, PMRace, and HawkSet. Therefore, these reports are not directly comparable on a one-to-one basis. Nonetheless, Vardalith detects races on the same operations reported by Durinn in P-Masstree and P-ART, so we follow the same best-effort reasoning presented in [72] and consider that Vardalith also finds the 5 PIRs reported by Durinn in those systems We reported all the new bugs to the developers, and one has already been confirmed. Next, for each program, we briefly discuss the new bugs found by Vardalith. A detailed description of each new bug is provided in the appendix.

P-CLHT [50] is a persistent cache-friendly hash table. Bug #2 is caused by two stores during garbage collection that are not persisted, leading to a double-free after a crash and potential data corruption. Note that this bug stems from an unpersisted store and therefore also manifests in single-threaded executions.

Level Hashing [105] is a PM write-optimized hashing index. Bug #8 occurs when two threads concurrently insert the same key. The first thread completes the insert but before it is persisted, the second thread, without proper synchronization, observes the inserted entry and reports its existence to the client. Following a crash, this can result in a causality violation.

CCEH [67] is a variant of extendible hashing for PM. Bug #9 results from incorrect synchronization during a directory doubling operation, allowing concurrent inserts to store data based on an unpersisted pointer, leading to data loss after a crash. CCEH-CoW is a variant that uses copy on write. Since it shares part of the CCEH implementation, it exhibits the same issue (Bug #10). Bug #11 occurs because the implementation of a lock-free search in CCEH-CoW allows a get operation to return an unpersisted value. Following a crash, this can result in a causality violation.

Finally, we use the new bugs found by Vardalith in Memcached [52] as a case study for our approach. Bug #14 and Bug #15 are triggered by similar executions, depicted in Figure 6. Briefly, Thread $t_1$ receives an increment/decrement request, acquires the item lock, and performs the operation by issuing calls to memcpy and memset, which store the new value of the item. It then releases the lock without explicitly persisting those stores. Subsequently, Thread $t_2$ receives a request to perform a prepend operation on the same key. This involves acquiring the lock and copying the existing data to a new item. A subsequent crash results in inconsistent data and client observations. Since the stores performed in lines 4292 and 4293 were never explicitly persisted, the Store PIFRs remain open indefinitely. Therefore, any subsequent prepend operation on the same key opens a Load PIFR on the same address, resulting in a report. These bugs are similar to Bug #16 and Bug #17, previously reported by PMRace [11], which occur when the append operation occurs concurrently with an increment/decrement on the same key.

We now assess the effectiveness of PIFRs. We start by comparing Vardalith with a baseline implementation. The baseline shares the same code base of Vardalith but, rather than using PIFRs, the regions just enclose the PM accesses mimicking what is done in approaches such as PMRace. We test both variants with different scheduling parameters (§ 5) and workloads of 1k, 10k and 100k operations. Additionally, we also tested Vardalith with sampling. We ran Vardalith five times (which took 90 minutes for the largest workload) and counted the number of unique PIRs found. Then, for the baseline, we ran it until it either found the same number of unique races or until a timeout of one week. Figure 7 presents the results.

While we ran this experiment for other programs, we only present the results for FAST-FAIR, since it has a large number of PIRs (as detailed in § 6.4) and thus represents a favorable case for the baseline approach.

There are a few takeaways from these results. First, Vardalith detects the unique races substantially faster than the baseline. For the 1k workload, it takes 3 days for the baseline approach to find the same number of unique PIRs that Vardalith finds in 5 testing runs, each run taking, even in the most unfavorable case, less than 2 seconds on average (§ 6.4). For larger workloads, we timed out the baseline execution after a week, and by then it found less than half the PIRs that Vardalith found in 5 runs. Furthermore, even in the most unfavorable case, each of these 5 runs took on average 1.2 and 13.75 minutes for 10k and 100k workloads, respectively. Second, Vardalith scales well, detecting more PIRs as the workload size increases. These additional races stem from the need to perform rebalancing operations that are only triggered for large workloads and hence can only be tested with scalable tools. Interestingly, the baseline performance degrades with increasing workloads. We attribute this to the fact that conflicts become sparser as the workload increases which reduces the probability of detection given the baseline’s small detection window. Finally, and as detailed in § 6.4, sampling affects the number of unique races detected, but even with sampling Vardalith is much more effective than the baseline.

Next, to understand why PIFRs are more effective, we compared their size, in terms of encompassed basic blocks, with two baselines: IFRs [20], which encompass the region from the immediately preceding acquire to the immediately succeeding release for each memory access, regardless of persistency; and the non-persistency windows (Non-Perst), which represent the region between a store and its explicit persistency (as defined in § 3.2). The results are shown in Figure 8. For brevity, we only present results for FAST-FAIR, but the other programs follow a similar trend. The key observation is that PIFRs are significantly larger than the alternatives. Interestingly, as the workload increases, the size of Store IFRs becomes slightly smaller than the regions defined by stores and their explicit persistency. This is because some stores are not explicitly persisted within their respective IFRs, underscoring a fundamental distinction to PIFRs.

Figure 9 shows the number of instructions per basic block belonging to at least one PIFR. While some blocks are small, roughly half encompass a few dozen instructions. These results illustrate how PIFRs, by defining larger regions (10s–100s of instructions) that are more likely to overlap, provide a more efficient detection mechanism than existing approaches that require overlap with a single load instruction, as depicted in Figure 1.

We now investigate the trade-offs of the different sampling and scheduling configurations (§ 5). We varied the following parameters: no delay, $1ms$ delay without decay, and $1ms$ delay with $5\%$ decay. These are tested without sampling and with a $10\%$ sampling rate, for a total of 6 configurations. Table 2 displays the average and standard deviation of 3 executions. Due to the large number of experiments (6 configurations, 3 workloads, 12 programs, and 3 runs, for a total of 648 executions), we capped the execution time of each experiment at 90 minutes. The executions that did not finish within this time are identified with a “—” in Table 2.

The main conclusion is that sampling presents an interesting trade-off: a sample rate of 10% results in $3$ to $15\times$ faster executions and detects around $30\%$ to $50\%$ of the PIRs when compared with sampling disabled. Notably, the vast majority of the bugs reported in Table 1 were detected with the 10% sampling rate. This suggests that developers can use sampling as part of the build process to spot PIRs early on, and disable sampling in the nightly tests and builds. In § 8 we discuss how developers can use the output of Vardalith to narrow down the bugs.

Manipulating the thread scheduling with delay injection substantially increases testing time, as expected. The results also show that using constant delays has diminishing returns, and we attribute this to the fact that PIFRs already result in large detection windows and hence the effect of simultaneously delaying multiple concurrent threads is not beneficial. However, we note that the use of active delay injection still yields more races at the cost of increased testing time.

To illustrate that multiple PIRs can trigger the same bug, and since Bug #1 was already known, we ran a version of P-CLHT where this bug was fixed. The results show an average decrease of 5 races reported per test, which is consistent with our observation that Bug #1 was triggered by 5 different PIRs (Table 1). The takeaway is that a single fix can have a noticeable impact in the number of PIRs reported.

We compared Vardalith with PMRace [11] using P-CLHT, FAST-FAIR and Memcached. The goal of this direct comparison is to shed light on the effectiveness of PIFRs versus traditional interleaving exploration techniques. We only considered PMRace’s first phase, making it an apples-to-apples comparison with Vardalith, as we detail in § 7. Following the authors’ instructions, we configured PMRace with 4 workers, the full set of seeds, and timeouts of 1, 10 (the default), and 30 minutes. As for Vardalith, we used the same experiments as before, with active delay injection and sampling disabled (corresponding to the sixth column of Table 2). We ran each experiment 3 times and compared the time taken and the detection rate of each known bug.

The results are shown in Table 3. There are two main observations. First, Vardalith is more consistent than PMRace at detecting PIRs. Considering P-CLHT and FAST-FAIR, the only instances where Vardalith missed bugs were either in smaller workloads that did not exercise the buggy code paths (P-CLHT, 1k and 10k operations), and Bug #13 which is known to be hard to reach [72]. As for Memcached, Vardalith still compares favorably with PMRace: PMRace failed to detect 3 of the 8 bugs in all 9 runs, while Vardalith only failed to detect Bug #19 in this configuration (though the bug was detected in other configurations shown in Table 2). Second, Vardalith was significantly faster while using fewer resources than PMRace, which used four parallel workers exploring the search space.

We ran all programs from Table 2 with ThreadSanitizer [86], a widely used dynamic data race detector. ThreadSanitizer uses a hybrid algorithm combining happens-before and lockset analysis to detect concurrent, unsynchronized accesses to shared memory. It tracks memory access and synchronization events (locks, unlocks, happens-before arcs) and flags pairs of accesses that are neither ordered by the happens-before relation nor protected by a common lock. However, ThreadSanitizer has no notion of PM semantics: it does not track persistence operations such as flushes and fences, and therefore cannot detect cases where accesses are properly synchronized from a concurrency standpoint but persistence operations fall outside critical sections. As expected, ThreadSanitizer did not report any of the bugs that stem from incorrectly synchronized persistence, as these do not constitute classic data races (Figure 1). In contrast, Vardalith reports all of the PM data races found by ThreadSanitizer, in addition to the 9 PIRs that ThreadSanitizer misses.

The improper utilization or absence of flush and fence instructions can result in durability, ordering, atomicity, and performance bugs, which led to the development of tools to detect them in single-threaded executions [28, 59, 58, 68, 17, 48, 31, 32, 24]. Most of these tools either lack support for concurrent executions or passively uncover PIRs by chance. Some approaches [76, 30, 33] establish stricter persistency models, flagging and/or correcting deviations from them. Robustness-based approaches [30, 33] require that every weak-persistency execution correspond to some strictly persistent execution, flagging any execution whose post-crash state could not have arisen from a program-order-consistent pre-crash history. These definitions, however, do not subsume our notion of PIR. In particular, PIRs additionally capture genuine bugs that robustness checks miss: cases in which a program observes unpersisted data and subsequently produces an externally visible effect other than a persistent store. Others [25, 11, 72], like Vardalith, actively search for PM concurrency bugs.

PMRace [11] focuses on narrower PIRs (termed inter-thread inconsistencies) where the reading of non-persisted data has persistent side effects, whereas Vardalith considers any side effects. It works in two phases. It uses PM-aware fuzzing tailored to key-value store semantics, along with interleaving exploration that selects pairs of accesses to the same target and injects delays to ensure that the read operation takes place right after the store but before it is persisted. This is similar to the scheduling strategy we discussed in § 5 and evaluated in § 6.3. This approach requires many runs to find PIRs, hindering the scalability of the system to large workloads. The second phase validates if the PIRs detected correspond to bugs, or if the behaviour is tolerated by the program, by checking if PIR-causally dependent PM stores are overwritten by the recovery. However, this technique only covers some recovery mechanisms, so PMRace still reports recoverable races in many instances [11].

Durinn [25] reasons about key-value store operations rather than PM accesses. The approach involves defining linearization points (LP) as points in the program where data becomes visible to other threads, and durability points (DP) as points in the program where data is persisted. It works by trying to force data to be read while the writer is between the LP and the DP for a given operation. To that end, Durinn generates a synchronous trace from a predefined workload and identifies pairs of potentially racy operations. It then reorders the operations in the workload to force one thread to read another’s unpersisted data, crashes the application, and checks for consistency using an approach similar to output equivalence checking [24]. Despite being highly effective, Durinn is tied to key-value store semantics and requires hand-written test drivers, limiting its applicability to other types of PM applications.

HawkSet [72] is a recent work that uses lockset analysis [83] to detect PIRs. While fast and scalable, HawkSet inherits the usual limitations of lockset analysis: it relies on locks as the only synchronization mechanism and can flag pairs of accesses that cannot actually occur concurrently in practice. Vardalith, in turn, follows a principled approach that does not depend on any specific synchronization mechanism and is formally proven correct, ensuring it only reports genuine races.

The literature in data race detection is vast and spans static [8, 74] and dynamic [83, 23, 86, 81, 20, 43, 80] approaches. Static detectors predict races without running the application but lack precision whereas dynamic approaches observe execution traces to detect actual races. Happens-before analysis [47, 23, 86] imposes a strict partial order on events based on program and synchronization order, which is conservative. However, HB analyses do not reason about persistency actions, and thus cannot capture non-persistency windows that define PIRs. Partial-order-based predictive search [80, 43, 81] achieves a greater detection rate with comparable performance. IFRit [20] uses Interference-Free Regions to extend the race detection window and thus increases the probability of detecting races. However, none of these approaches can detect PIRs that result from persisting outside the critical section.

Systematic testing [65, 27] explores all possible thread interleavings but does not scale. Partial-order reduction [26, 1, 44] soundly reduces the number of interleavings to explore by skipping equivalent executions. Randomized testing [9, 100] employs probabilistic scheduling but sacrifices completeness and tends to explore equivalent interleavings. Delay injection influences scheduling without controlling it. Some approaches [22] perform lightweight analysis and inject delays probabilistically at many locations, while others perform extensive analysis to select few locations [85, 73]. Active delay injection [54, 88] offers a middle ground by selecting many locations at the start and dynamically adjusting their probabilities based on their effectiveness. However, in Vardalith, since PIFRs already extend the race detection window, the impact of these techniques is reduced, as illustrated in § 6.3.

All races reported by Vardalith are true PIRs– that is, Vardalith guarantees that whenever it reports a bug, there exists an interleaving in which a non-persisted write is read by a concurrent thread. However, the application under analysis may include recovery mechanisms that restore a consistent state after a crash, depending on its semantics. Existing tools do not handle this well: HawkSet [72] simply ignores recovery, with the added problem that lockset analysis can flag pairs of accesses that cannot even occur concurrently in practice; PMRace [11] accounts for some recovery mechanisms but still reports benign races in many instances [11]. Vardalith explores a different point in the design space: it takes care of the hard part – proving that a concurrent interleaving witnessing the race exists – and leaves the developer with the easier job of checking whether recovery covers it.

We assume threads persist their own stores and do not consider the flush-on-read pattern [93], where a thread that reads from PM flushes the loaded value before performing any operation that depends on it. Our choice is consistent with most PM applications we are aware of, including all programs we and the state-of-the-art analyze [37, 67, 92, 50, 52, 96, 61, 105, 10], which rely on writers to flush. One likely reason is cost: having readers flush can dominate runtime when readers vastly outnumber writers, even though recent work proposes mitigations [97]. Alternative persistency models, such as epochs [98], propose writing to intermediate structures that are asynchronously persisted in the background. Similarly to the state-of-the-art [72, 25, 11], we do not consider these alternative models.

Vardalith outputs two artifacts: a list of overlapping PIFR identifiers and detailed PIFR backtraces. Based on our experience in analyzing the PM programs from § 6, we developed the following methodology to translate these outputs into actionable bug fixes:

1. 1.

   Prioritization: Sort PIFR pairs to identify the most prevalent race patterns, which often indicate systemic issues rather than isolated bugs.

2. 2.

   Filter Benign Cases: Exclude known benign races that represent intentional design choices. For example, in Memcached, $\approx 60\%$ of the races involve unpersisted stores to the LRU cache fields and bitwise operations on flags that are rebuilt after crashes.

3. 3.

   Focus on Critical Paths: Analyze remaining races in important code sections, particularly those involving resizing of data structures, which is often linked to data loss bugs, as exemplified by Bugs #1, #9, #10, #12, #13, and #24 from Table 1.

This approach proved effective despite our initial unfamiliarity with the codebases. Developers with domain knowledge should be able to identify critical issues even more efficiently.

While some PIRs are also traditional data races, many critical PM bugs occur despite proper synchronization, when persistence operations happen outside critical sections. In such cases, traditional data race detectors like ThreadSanitizer [86] are ineffective, as shown in § 6.3. This gap is fundamental: PIRs arise from the interaction between concurrency and persistency semantics, which traditional detectors simply do not model. Of the 26 bugs Vardalith detected, 9 are not traditional data races and would be missed by such tools.

Similarly, even though PIFRs draw inspiration from Interference-Free Regions (IFRs) [19], the differences between volatile and PM semantics make IFRs inadequate for PIR detection. Computing PIFRs is substantially harder than computing IFRs. An IFR surrounds a single memory access delimited by the nearest acquire and release. A Store PIFR, in contrast, must additionally reason about the persistency operation that pertains to the enclosed store, since the region extends until the first release after explicit persistence. This requires value-level reasoning to match flushes to prior stores by address range, which is already non-trivial within a single function and is compounded by the fact that persistency operations are frequently encapsulated in auxiliary functions or separate procedures, demanding interprocedural analysis that is provably expensive or even impossible in some cases [79], as discussed in § 4. Our hybrid design addresses this by under-approximating PIFR starts intraprocedurally via static analysis and deferring the precise determination of PIFR ends to the dynamic component.

Despite Intel Optane’s discontinuation [15], PM remains highly relevant as the industry moves towards CXL-based solutions [12, 16, 87]. CXL is rapidly gaining traction in both academia and industry [55, 101, 103], with CXL Type 3 [87] introducing explicit support for PM. Multiple vendors have announced upcoming PM devices for the near future [82, 63, 70], indicating industry commitment to these technologies.

Based on the available information, we expect CXL-based PM devices to present similar semantic challenges to Optane. In particular, given the intrinsic differences in access latency and capacity among the cache, RAM, and PM: i) any memory-mapped persistent storage solution must rely on CPU caches for performance, and ii) the hardware must continue to provide explicit primitives to control the transitions between volatile and persistent domains. As a result, the decoupling between visibility and durability remains, meaning PIRs can still occur. Therefore, developers must still handle these transitions carefully, as with Optane.

At the same time, our paper assumes a crash-consistency model and does not explicitly model the partial failures that may arise in some CXL settings. We view these directions as complementary: Vardalith focuses on efficiently detecting PIRs, while other approaches can extend the failure model to reason about partial failures more explicitly [31].

Overall, Vardalith’s approach is particularly well-suited to this evolving landscape. By operating at the binary level and relying only on a few simple and fundamental primitives common across implementations, our approach can adapt to diverse vendor-specific devices and libraries.