Silhouette: Leveraging Consistency Mechanisms to Detect Bugs in Persistent Memory-Based File Systems
Grants: NSF grants DGE-2146354 and FSU Research Foundation
Writing file system code for persistent memory is challenging because writes may not be propagated to persistent memory in the correct order, resulting in inconsistency after crashes. Theoretically, we want to examine crashed system images resulting from all possible persistence orderings of pending writes, but this search space grows exponentially as the number of pending writes increases. Existing systems use sampling to trim this search space by skipping analyses for classes of writes, resulting in missing opportunities to detect bugs.
We introduced the Silhouette framework, which leverages the observation that file systems tend to use a few common consistency mechanisms (e.g., journal) to persist data. Therefore, instead of exploring the persistence ordering constraints of individual writes, we explored the ordering constraints at a higher level of persistence phases in common consistency mechanisms. Once we have verified that these mechanisms are correct, we only need to examine the remaining writes that are not protected by these mechanisms.
Compared to the state of the art, our solution reduced the search space by 3,300x, accelerated the bug-finding process by 10x, and found all bugs discovered by existing systems and 15 new bugs not previously reported.
Figure 1: Undo Journal Invariants.
Figure 2: Mapping Low-level Stores to High-level Consistency Mechanisms.