Efficiently detecting concurrency bugs in persistent memory programs

Two threads can each be individually correct about flushing their writes to persistent memory and still leave the system corrupted after a crash — PMRace hunts the interleavings where one thread durably acts on data another thread has written but not yet persisted.

Why this problem is worth solving

Persistent memory promised memory-speed access with data that survives a power cut, and Intel shipped it in modules of up to 512 gigabytes. What it did not come with is a programming model anyone finds easy. A store to persistent memory goes into the ordinary write-back CPU cache; it becomes durable only when a flush instruction pushes that cache line out, and because cache eviction can reorder, the order in which writes become durable need not match the order they were issued. Writing correct code means placing flushes and fences so that whatever survives a crash can be recovered into something sensible — the property called

The tooling that grew up around this problem is genuinely useful and looks at one thread. It asks whether a write was followed by a flush, whether an ordering constraint was respected, whether the output after recovery matches the output without a crash. But persistent-memory systems are almost all concurrent, because the whole point of the technology is throughput, and the interesting failures live between threads. The paper’s motivating case is a real hash table where one thread swaps in a new table pointer without flushing it, and another thread reads that pointer from the cache and inserts an item through it. Both threads flush what they wrote. Crash at the wrong moment and the item is durably in a table nobody can find. No single-threaded checker sees anything wrong, because nothing single-threaded is wrong.

What people did before, and where it broke

• Check for missing flushes and fences. The workhorse of persistent-memory tooling. Necessary, and blind to whether the data being flushed was itself trustworthy.
• Annotate assertions about consistency. Effective where the programmer already knows what invariant to state, which is exactly where bugs are least likely.
• Match known bug patterns. Catch the shapes people have already been caught by. Concurrency-specific shapes were not among them.
• Symbolic execution and model checking. Thorough on small programs and defeated by the state space of a concurrent persistent-memory system, where every write has a persistency state as well as a value.
• Output equivalence checking. Witcher’s approach: compare the program’s output after a simulated crash and recovery against its output without one. Avoids false positives cleanly, but misses any bug that does not change the output — a persistent-memory leak, or redundant flushes, both of which matter. It is also single-threaded.
• Use a conventional concurrency bug detector. Data race detectors and interleaving explorers know about threads and know nothing about persistence, so they cannot tell a benign read from a read of data that is not yet durable.
• The gap. One community modelled persistence without concurrency and the other modelled concurrency without persistence. The bugs sitting in the overlap had no detector, and concurrency bugs are already the hardest kind to find.

How PMRace hunts the interleavings that matter

The idea

Name the bug class before hunting it. The contribution that carries the paper is definitional. Two failure modes are identified and given precise meaning. Inter-thread inconsistency is when one thread makes a durable change based on data another thread wrote but has not yet persisted — the hash table case. Synchronization inconsistency is stranger and more interesting: if a lock itself lives in persistent memory, but the threads holding locks do not, then a crash while a lock is held resurrects a locked lock with no owner, and every future attempt to acquire it hangs forever. These map onto two broader categories the authors call interleaving concurrency bugs and execution context bugs. Having the definitions is what makes detection tractable, because a detector can look for a specific, checkable event rather than for badness in general. Staking out an intersection that two mature literatures had each left to the other, and defining the failures that live there, is the same move made by work naming persistency races as a distinct hazard, covered elsewhere on this site.

A coverage metric shaped like the bug you are looking for.

An inconsistency is not a bug until recovery declines to fix it. The hardest practical problem is false positives, because real systems repair themselves. A persistent-memory allocation made inside an uncommitted transaction looks exactly like a leak until you notice the transaction will roll back. Rather than tighten the detector until it stops reporting these — which is how you get false negatives instead — PMRace resolves the question empirically. When an inconsistency is found, it snapshots the memory pool at that point, records the addresses involved as pool-relative offsets so that address randomisation cannot confuse it, then runs the application’s own recovery code and checks whether the inconsistent data is overwritten. What survives recovery is a bug; what does not was a symptom. This pruning is substantial: checking for durable side effects removes 68.5% of candidates, and post-failure validation removes another 65 inconsistencies, 62 of them in a single system. Deciding what counts as a violation precisely and then establishing it by execution rather than by reasoning about the code is the same methodology behind testing processors against a stated contract, covered elsewhere on this site.

Following one bug from candidate to report

Preemption points come from a priority queue built from frequent accesses to shared persistent data. Blocking a reader until a writer acts is what creates the unpersisted-read window on purpose, instead of hoping a random delay lands there.

Why it works

• Persistency state turns identical code paths into distinct test cases. The coverage metric records whether each access saw durable or non-durable data → two runs of the same code count as different if their persistency states differ → so the fuzzer can tell it is making progress in the dimension where these bugs live.
• Scheduling manufactures the window instead of waiting for it. A reader is blocked on a condition variable until the matching writer stores without flushing → the dangerous interleaving is produced deliberately → which the paper shows finds inconsistencies faster than injecting random delays at persistent-memory accesses.
• Taint analysis separates a suspicious read from a harmful one. Reading unpersisted data is common and mostly harmless; the damage needs a durable consequence → following the value to a durable side effect prunes 68.5% of candidates → so what is reported is already narrowed to cases that could corrupt something.
• Running recovery answers the question the analysis cannot. Applications repair themselves in application-specific ways → replaying the real recovery code decides whether an inconsistency matters → removing 65 further false positives, 62 of them in one system, without the false negatives that output-comparison approaches accept.
• Escalating tiers stop the search from spinning. Repeat the execution, then vary the interleaving, then change the seed → each tier is tried only when the cheaper one stops improving coverage → and the ablation shows removing either the interleaving tier or the seed tier flattens coverage growth.

What it costs (trade-offs and scope)

• Better hardware deletes half the contribution. The authors say so directly. With eADR — batteries that make the CPU caches themselves a persistence domain — flush instructions are no longer needed, and inter-thread inconsistency cannot occur. Synchronization inconsistency survives, since a lock stored in persistent memory still outlives a crash, but the larger of the two bug classes has a hardware expiry date.
• Some of the fourteen bugs are not crash-consistency bugs. One is redundant persistent writes, a performance issue. One is an ordinary concurrency bug — a missing unlock — that the fuzzing happened to trigger. Both are real findings; neither is what the tool is for.
• False positives remain, unevenly. The filtering is effective on most systems but not all: a B+-tree using lazy recovery tolerates inconsistencies by design, so 69 reported inconsistencies there reduced to a single bug. The whitelist of known-safe patterns is application-specific, and the authors note that adding more rules would reduce the rate further — which means tuning per target.
• It needs human input. Synchronization variables must be annotated, though only six annotations were needed across two systems. Each tested system also needs a hand-written driver that issues concurrent requests.
• Only four threads. The driver runs four threads, justified by the observation that most known concurrency bugs involve very few. Reasonable, and it bounds what can be found.
• The in-memory checkpoint optimisation is not universally safe. It speeds fuzzing by 199% on average by reusing an initialised pool, but the authors recommend disabling it for programs built on the lower-level library, where it does not apply.

The evaluation

Check yourself

Sources

The paper is “Efficiently Detecting Concurrency Bugs in Persistent Memory Programs” by Zhangyu Chen, Yu Hua, Yongle Zhang and Luochangqi Ding, published at ASPLOS 2022, pages 873-887, DOI 10.1145/3503222.3507755. The authors are at Huazhong University of Science and Technology and Purdue University, and the tool is named PMRace.

This explainer is written from the full text, read from the author-hosted copy on Yu Hua’s page. All figures above come from the paper’s own sections 3 through 6: the definitions of the two inconsistency types and the two bug categories they represent, the alias pair coverage metric and the three exploration tiers, the counts of 501 inter-thread candidates reducing to 160 inconsistencies and then to 8 unique bugs after 65 validated and 6 whitelisted false positives were removed, the 68.5% pruning rate from checking durable side effects, the 14 unique bugs of which 10 are new and 10 are persistent-memory concurrency bugs, the 6 annotations required across two systems, the 199% and 65% fuzzing speedups from in-memory pool checkpoints, and the evaluation platform of a two-socket Xeon Gold 6230R with 1.5 TB of Intel Optane persistent memory. The discussion of eADR and its effect on the inter-thread inconsistency class is the authors’ own, in section 6.5.