Artifact for Article "Memento: A Framework for Detectable Recoverability in Persistent Memory"

<strong>Memento: A Framework for Detectable Recoverability in Persistent Memory</strong> This is the artifact for the following paper: Memento: A Framework for Detectable Recoverability in Persistent Memory. PLDI 2023. Contributions (paper §1) In §2, we describe how to design programs that are deterministically replayed after a crash. We do so using two primitive operations, detectably recoverable checkpoint and CAS, by composing them with usual control constructs such as sequential composition, conditionals, and loops. In §3, we design a core language for persistent programming and its associated type system for deterministic replay, and prove that well-typed programs are detectably recoverable. In §4, we present an implementation of our core language in the Intel-x86 Optane DCPMM architecture. Our construction is not tightly coupled with Intel-x86, and we believe that our implementation can be straightforwardly adapted to other PM architectures. In §5, we adapt several volatile, lock-free data structures (DSs) to satisfy our type system, automatically deriving detectable, persistent lock-free DSs. These include a detectable, persistent linked-list [Harris 2001], Treiber stack [Treiber 1986], Michael-Scott queue [Michael and Scott 1996], a combining queue, and Clevel hash table [Chen et al. 2020]. In doing so, we capture the optimizations of hand-tuned persistent lock-free DSs with additional primitives and type derivation rules (§B and §C), and support safe memory reclamation even in the presence of crashes (§D). In §6, we evaluate the detectability and performance of our CAS and automatically derived persistent DSs. They recover from random thread crashes in stress tests (§6.1); and perform comparably with the existing persistent DSs with and without detectability (§6.2). Artifacts Implementation of the Memento framework and its primitives (§4 : <code>memento/</code>) Implementation of several detectably persistent DSs based on Memento (§5 : <code>memento/</code>) Evaluation programs (correctness and performance) (§7 : <code>memento/</code>) Full result data of benchmark (§7 : <code>evaluation_data/</code>) Appendix including full algorithm of CAS (§A), insert/delete operations (§B), advanced optimizations (§C), safe memory reclamation (§D), full evaluation results (§E), full core langue syntax, semantics and type system (§F, §G) and proof of detectability theorem (§H) (<code>appendix.pdf</code>) Getting Started Guide You can either reuse a pre-built docker image <code>memento-image.tar</code> or manually build the framework. Requirements Ubuntu 20.04 or later Intel® Optane™ Persistent Memory 100 Series (mounted at <code>/mnt/pmem0</code>). In case that a persistent memory is not mounted, you can still perform a <em>limited</em> evaluation on DRAM. Option 1: Running on Docker (Loading Docker Image) You can reuse a pre-built docker image by loading <code>memento-image.tar</code>: <pre><code>docker load -i memento-image.tar docker run -it -v /mnt/pmem0:/mnt/pmem0 --cap-add=SYS_NICE memento # persistent memory must be mounted at /mnt/pmem0 </code></pre> Here, <code>-v /mnt/pmem0:/mnt/pmem0</code> option is required to share the mounted persistent memory area with the container. Also, <code>--cap-add=SYS_NICE</code> option is needed to evalute performance by unifying all used cores into a single numa node. You can re-build a docker image by <code>docker build -t memento memento/</code>. (It may take more than 30 minutes.) Option 2: Running on host Dependencies Rust <pre><code>curl --proto '=https' --tlsv1.2 -sSf https://sh.rustup.rs | sh </code></pre> Additional dependencies for evaluation: <pre><code>apt install build-essential clang python3-pip numactl \ libpmemobj-dev libvmem-dev libgflags-dev \ libpmemobj1 libpmemobj-cpp-dev \ libatomic1 libnuma1 libvmmalloc1 libvmem1 libpmem1 pip3 install --user pandas matplotlib gitpython </code></pre> Build To build our framework including detectable operations, DSs and SMR libraries: <pre><code>cd memento git submodule update --init --recursive (cd ext/pmdk-rs; git apply ../pmdk-rs.patch) cargo build --release </code></pre> If persistent memory is <em>not</em> mounted on your machine, add a feature flag with <code>no_persist</code> as follows: <pre><code>cd memento cargo build --release --features no_persist </code></pre> Step-by-Step Instructions This artifact aims to achieve the following goals: G1: Locating our framework's core concepts (§4,5,B,D) in the development G2: Reproducing the detectability evaluation (§6.1) G3: Reproducing the performance evaluation (§6.2) G1: Locating our framework's core concepts (§4,5,B,D) in the development <code>src/ploc/</code>: persistent memory (PM) infrastructure and primitive operations (§4, §B) <code>src/ds/</code>: memento-based persistent, detectable DSs supporting exactly-once semantics (§5) <code>crossbeam-persistency/</code>: safe memory reclamation scheme (§D) PM Infrastructure (§4.1) <code>src/pmem/ll.rs</code>: Low-level PM instructions (§4.1) <code>src/pmem/pool.rs</code>: PM pool manager and <strong>crash handler</strong> (§4.1) Primitive Operations (§4, §B) <code>src/ploc/common.rs</code>: Timestamp calibration (§4.1) and Checkpoint (§4.2) <code>src/ploc/detectable_cas.rs</code>: Atomic Pointer Location supporting Detectable CAS (§4.3) <code>src/ploc/insert_delete.rs</code>: Insertion and Deletion (§B in Appendix) Concurrent Data Structures (§5) <code>src/ds/comb.rs</code>: A memento-based detectable combining operation. We convert the original PBComb to one using mementos to support multi-time detectability. (<strong>Comb-mmt</strong>) <code>src/ds/list.rs</code>: A memento-based lock-free list that uses <code>DetectableCas</code> and <code>Checkpoint</code> based on Harris' ordered linked list. (<strong>List-mmt</strong>) <code>src/ds/treiber_stack.rs</code>: A memento-based lock-free stack that uses <code>DetectableCas</code> and <code>Checkpoint</code> based on Treiber's stack. (<strong>TreiberS-mmt</strong>) <code>src/ds/queue_general.rs</code>: A memento-based lock-free queue that uses <code>DetectableCas</code> and <code>Checkpoint</code> based on Michael-Scott Queue. (<strong>MSQ-mmt-O0</strong>) <code>src/ds/queue_lp.rs</code>: A memento-based lock-free queue that uses <code>Insert</code>, <code>Delete</code> and <code>Checkpoint</code>. The difference from <code>queue.rs</code> is that this queue uses general <code>link-persist</code> technique rather than exploits DS-specific invariant for issuing less flushes when loading shared pointer. (<strong>MSQ-mmt-O1</strong>) <code>src/ds/queue_comb.rs</code>: A memento-based combining queue that uses <code>Combining</code> operation. (<strong>CombQ-mmt</strong>) <code>src/ds/clevel.rs</code>: A memento-based Clevel extensible hash table. We convert original Clevel to one using mementos. (<strong>Clevel-mmt</strong>) <code>src/ds/queue.rs</code>: A memento-based lock-free queue that uses <code>Insert</code>, <code>Delete</code> and <code>Checkpoint</code> based on Michael-Scott Queue. (<strong>MSQ-mmt-O2</strong>) Safe Memory Reclamation (§D) <code>crossbeam-persistency/crossbeam-epoch/src/guard.rs</code>: "Flushing Location before Retirement" <code>crossbeam-persistency/crossbeam-epoch/src/internal.rs</code>: "Allowing Double Retirement" G2: Reproducing the detectability evaluation (§6.1) Thread Crash Test We evaluate the detectability in case of thread crashes by randomly crashing an arbitrary thread while running the integration test. To crash a specific thread, we use the tgkill system call to send the SIGUSR1 signal to the thread and let its signal handler abort its execution. Install <pre><code>cd memento/evaluation/correctness/tcrash ./build.sh # specially build for the thread crash test </code></pre> Run You can test each DS with the following command: <pre><code>./run.sh [tested DS] </code></pre> where <code>tested DS</code> should be replaced with one of supported tests (listed below). For example, the following command is to infinitely check that the test of <strong><em>MSQ-mmt-O0</em></strong> in the paper always pass in case of an unexpected thread crash: <pre><code>./run.sh queue_general </code></pre> Then the output is printed out like below: <pre><code>clear queue_general ⎾⎺⎺⎺⎺⎺⎺⎺⎺⎺⎺⎺⎺ thread crash-recovery test queue_general 1 (retry: 0) ⎺⎺⎺⎺⎺⎺⎺⎺⎺⎺⎺⎺⏋ run queue_general [Test 1] success clear queue_general ⎾⎺⎺⎺⎺⎺⎺⎺⎺⎺⎺⎺⎺ thread crash-recovery test queue_general 2 (retry: 0) ⎺⎺⎺⎺⎺⎺⎺⎺⎺⎺⎺⎺⏋ run queue_general [Test 2] success clear queue_general ⎾⎺⎺⎺⎺⎺⎺⎺⎺⎺⎺⎺⎺ thread crash-recovery test queue_general 3 (retry: 0) ⎺⎺⎺⎺⎺⎺⎺⎺⎺⎺⎺⎺⏋ run queue_general [Test 3] success clear queue_general ⎾⎺⎺⎺⎺⎺⎺⎺⎺⎺⎺⎺⎺ thread crash-recovery test queue_general 4 (retry: 0) ⎺⎺⎺⎺⎺⎺⎺⎺⎺⎺⎺⎺⏋ run queue_general ^C </code></pre> It also creates a short progress log and a full test log under <code>./out</code>. If a bug exists (just for an example), the output is like below: <pre><code>clear queue_general ⎾⎺⎺⎺⎺⎺⎺⎺⎺⎺⎺⎺⎺ thread crash-recovery test queue_general 1 (retry: 0) ⎺⎺⎺⎺⎺⎺⎺⎺⎺⎺⎺⎺⏋ run queue_general ./run.sh: line 51: 855011 Aborted RUST_BACKTRACE=1 RUST_MIN_STACK=2000000000 numactl --cpunodebind=0 --membind=0 timeout $TIMEOUT $SCRIPT_DIR/../../target/x86_64-unknown-linux-gnu/release/deps/memento-* $target::test --nocapture &amp;&gt;&gt; $log_tmp fails with exit code 134 [Test 1] fails with exit code 134 clear queue_general ⎾⎺⎺⎺⎺⎺⎺⎺⎺⎺⎺⎺⎺ thread crash-recovery test queue_general 2 (retry: 0) ⎺⎺⎺⎺⎺⎺⎺⎺⎺⎺⎺⎺⏋ run queue_general ^C </code></pre> It then generates a bug directory consisting of a text file containg specific error log (<code>info.txt</code>) and a PM pool files (<code>queue_general.pool_*</code>) of the buggy execution so that we can debug the DS using it. For each primitive and DS, we observe <em>no</em> test failures for 1M runs with thread crashes. Supported tests For primitives <code>checkpoint</code> <code>detectable_cas</code> For data structures <code>queue_general</code>

Fetched live from OpenAlex and de-inverted. Abstracts are not stored in this database: the inverted indexes are 8.6 GB of the frame’s 9.3 GB of text, and the host has 13 GB free.