The proliferation of fast, dense, byte-addressable nonvolatile memory suggests the possibility of keeping data in pointer-rich “in-memory” format across program runs and even crashes. For full generality, such data requires dynamic memory allocation. Toward this end, we introduce \emph{recoverability}, a correctness criterion for persistent allocators, together with a nonblocking allocator, \emph{Ralloc}, that satisfies this criterion. Ralloc is based on \emph{LRMalloc}, with three key innovations. First, we persist just enough information during normal operation to permit reconstruction of the heap after a full-system crash. Our reconstruction mechanism performs garbage collection (GC) to identify and remedy any failure-induced memory leaks. Second, in support of GC, we introduce the notion of \emph{filter functions}, which identify the locations of pointers within persistent blocks. Third, to allow persistent regions to be mapped at an arbitrary address, we employ the position-independent pointer representation of Chen et al., both in data and in allocator metadata.

Experiments show that Ralloc provides scalable performance competitive to that of both \emph{Makalu}, the state-of-the-art lock-based persistent allocator, and the best transient allocators (e.g., \emph{JEMalloc}).