{'fraction_non_alphanumeric': 0.03297859899426968, 'fraction_numerical': 0.008069231668810666, 'mean_word_length': 4.788897664447704, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Tracking in Order to Recover: Detectable Recovery of Lock-Free Data Structures

This paper presents the tracking approach for deriving detectably recoverable (and thus also durable) implementations of many widely-used concurrent data structures. Such data structures, satisfying detectable recovery, are appealing for emerging systems featuring byte-addressable non-volatile main memory (NVRAM), whose persistence allows to efficiently resurrect failed processes after crashes. Detectable recovery ensures that after a crash, every executed operation is able to recover and return a correct response, and that the state of the data structure is not corrupted. Info-Structure Based (ISB)-tracking amends descriptor objects used in existing lock-free helping schemes with additional fields that track an operation's progress towards completion and persists these fields to memory in order to ensure detectable recovery. ISB-tracking avoids full-fledged logging and tracks the progress of concurrent operations in a per-process manner, thus reducing the cost of ensuring detectable recovery. We have applied ISB-tracking to derive detectably recoverable implementations of a queue, a linked list, a binary search tree, and an exchanger. Experimental results show the feasibility of the technique.


Introduction
Byte-addressable non-volatile main memory (NVRAM) combines the performance benefits of conventional main memory with the durability of secondary storage. Systems with NVRAM are anticipated to be more prevalent in the near future. The availability of durable main memory has increased the interest in the crash-recovery model, in which failed processes may be resurrected after the system crashes. Of particular interest is the design of recoverable concurrent objects (also called persistent [8,10] or durable [36]), whose operations can recover from crash-failures. It is also important to be able to tell after recovery whether an operation was executed to completion and if so, what its response was, a property called detectable recovery [1,20].
In many computer systems (e.g., databases), detectable recovery is supported by precisely logging the progress of computations to non-volatile storage, and replaying the log during recovery. Logging imposes significant overheads in time and space. This cost is even more pronounced for concurrent data structures, where there is an extra cost of synchronizing accesses to the log. Furthermore, replaying an operation in our setting, where some processes may be concurrently recovering from crash-failures while others have already completed recovery and proceed their normal execution, requires to add new mechanisms to the original, non-recoverable, implementation.
A key observation is that in the context of concurrent data structures, full-fledged logging is not needed, and the progress of an operation can be tracked individually, in a way supporting detectable recovery. Moreover, many lock-free implementations already encompass such tracking mechanisms, which can be easily adapted to support detectable recovery. This leads to the ISB-tracking approach for designing recoverable objects, based on explicitly maintaining an Info structure, stored in non-volatile memory, to track an operation's progress as it executes. The Info structure allows a process to decide, upon recovery, whether the operation's effect has already become visible to other processes, in which case, the mechanism allows to determine the response of the operation. (See Section 3.) In many cases, ISB-tracking requires small changes to the original code. It significantly saves on the cost (in both time and memory) incurred by tracking operations' progress, by not having to track which instructions have been performed exactly, but rather, specific stages of the operation. Furthermore, even this can often be piggybacked on information already tracked by lock-free concurrent data structures, within operation descriptors. This means that operations efficiently maintain and persist sufficient information for recovery, and that the corresponding recovery code infers whether the operation took effect before the failure, in which case its response value is computed and returned. These properties are what make our approach attractive.
ISB-tracking is widely applicable-it can be used to derive recoverable versions of a large collection of concurrent data structures. We have applied it to derive a queue [30], a linked list [23] (Section 4), a binary search tree [17], and an exchanger object [34]. The approach can be combined with a technique we call direct-tracking which follows similar ideas as the log-queue [20] to get an elimination stack [24].
Detectability is a challenge even if caches are non-volatile, i.e., writes are immediately persisted, in program order. However, ISB-tracking informs how persistency instructions (flushes and fences) should be inserted for ensuring an implementation's correctness in an efficient manner, even when cache memories are volatile and their content is lost upon a systemwide failure [27] (see Section 3).
We provide an experimental analysis (Section 5) to compare the performance of ISB-tracking with all other generic schemes we are aware of that can be used for deriving detectable recoverable data structures. The results show the feasibility of ISB-tracking. We have also implemented (in C++) hand-tuned, highly-optimized versions of detectably recoverable linked lists, one using an existing general transformation [3], and another based on ideas from [20].
Experiments show that ISB-tracking performs better when contention is high. For linked-lists, this is because ISB-tracking allows more precise insertion of persistency instructions, based on a nuanced understanding of the consistency requirements of the implementation.
Summarizing, the main contributions of this paper are: • We propose ISB-tracking, a new mechanical transformation for deriving detectably recoverable implementations of concurrent data structures. • In a system with volatile caches, we present how persistency instructions can be added in ISB-tracking in a manner that enhances efficiency and scalability. • We apply ISB-tracking to get new detectably recoverable implementations of queues, linked lists, binary search trees, and exchangers. • We provide an experimental analysis to compare with all existing relevant transformations and detectably recoverable concurrent data structures we are aware of. They show the feasibility of ISB-tracking and the good scalability it exhibits in many cases.

System Model
We consider a system of asynchronous crash-prone processes which communicate through base objects supporting atomic read, write, and Compare&Swap (CAS) primitive operations.
In the shared cache model, the main memory is non-volatile, whereas the data in the cache or registers are volatile. Thus, primitive operations are applied to volatile memory, and writes can be persisted to the non-volatile memory using explicit flush instructions, or when a cache line is evicted. Under explicit epoch persistency [27], a write-back to persistent storage is triggered by a persistent write-back (pwb) instruction. The process may continue its execution after pwb. The order of pwb instructions is not necessarily preserved. When ordering is required, a pfence instruction orders preceding pwb instructions before all subsequent pwb instructions. A psync instruction waits until all previous pwb instructions complete the write back. For each location, persistent writebacks preserve program order. We assume the Total Store Order (TSO) model, supported by the x86 and SPARC architectures, where writes become visible in program order.
The pseudocode for our generic technique (Section 3) includes necessary persistency instructions, showing how to efficiently persist information. A simpler model is the private cache model [3], in which shared variables are always persistent. In that model, primitive operations are immediately applied on the persistent memory, and the state of each process is partitioned into non-volatile private variables, and local variables stored in volatile processor registers. In both models, private and local variables are accessed only by the process they belong to.
At any point during the execution of an operation, a system-wide crash-failure (or simply a crash) resets all volatile variables to their initial values, while the values of (shared and local) non-volatile variables are retained. 1 A process invokes to start its execution; Op completes by returning a response value, which is stored to a local variable of . The response value is always lost if a crash occurs before persists it (i.e., before it writes it to a non-volatile variable).
A recoverable operation has an associated recovery function, denoted .Recover, which the system calls when recovering after a system-failure that occurred while it was executing . Failed processes are recovered by the system asynchronously, independently of each other; the system may recover only a subset of these processes before another crash occurs. The recovery code is responsible for finishing 's execution and returning its response. An 1 In the private cache model, our approach and the derived algorithms work also in the more general failure model where a process may fail individually.
implementation is recoverable if all its operations are recoverable. Process may incur multiple crashes while executing and .Recover, so .Recover may be invoked multiple times before completes. We assume that the system invokes .Recover with the same arguments as those with which was invoked when the crash occurred. For each process , we also use a non-volatile private variable CP , that recoverable operations and recovery functions use for managing check-points in their execution flow. 2 When invokes a recoverable operation , the system sets CP to 0 just before 's execution starts. CP can be read and written by recoverable operations (and their recovery functions). CP is used by in order to persistently report that the execution reached a certain point. The recovery function can use this information in order to correctly recover and to avoid re-execution of critical instructions such as CAS.
is completed either directly or when, after one or more crashes, the execution of the last instance of .Recover invoked for is complete. In either case, 's response is written to a local variable of . We ensure detectability [20]: it is possible to determine, upon recovery, whether the operation took effect, and its response value, if it did.
A recoverable implementation is wait-free if, when no crash occurs during the execution of a recoverable operation (including its recovery function), it completes in a finite number of steps. It is lock-free if, when no crash occurs, some recoverable operation completes in a finite number of steps.

Info-Structure Based Tracking
Many lock-free implementations of data structures (e.g., [2,[16][17][18]38]) employ a helping mechanism to ensure global progress, even if processes crash. They associate an information (Info) structure with each update, tracking the progress of the update by storing sufficient information to allow its completion by concurrent operations.
Our approach takes advantage of this Info-Structure-Based (ISB) helping to provide detectable recovery. In brief, ISB helping works as follows: An operation Op by process initializes an Info structure and then attempts to install it in every node that Op is trying to change; this is done by executing a CAS to set a pointer in each of these nodes to point to the Info structure initialized by Op. Once the Info structure is successfully installed, continues the execution of Op using the information stored in the Info structure. Once the update completes, Op invalidates the Info structure in all nodes pointed to it. If it fails to install the Info structure on some node, finds the Info structure of another operation installed at the node, uses the information in it to complete the operation, and then restarts Op.
A key observation is that ISB helping goes a long way towards making a data structure recoverable: updates are idempotent and not susceptible to the ABA problem, since they must ensure that an update is done exactly once, even if several processes attempt to concurrently help it complete. So, if the system crashes while is executing an operation Op, upon recovery, can essentially re-execute to completion by either using the information in the Info structure for Op (if it has already been installed) or by starting from scratch.
To support detectability, when recovers from a crash that occurred while executing one of its operations Op, its recovery code must be able to access the Info structure of Op. This is achieved by allocating, for every process , a designated persistent recovery data variable, , that stores a reference to . Furthermore, a recovering process must be able to figure out whether its failed operation took effect, and if it did, what its response was. To ensure this, a result field is added to the Info structure. Process , and every process helping Op, sets the result in before invalidating from the relevant nodes. Upon recovery, reads a reference to the last Info structure from and uses it to complete its last operation. If the result field of the Info structure is set, the operation took effect, and returns its value. Otherwise, Op did not take effect and it can be restarted. Even if Op performed changes that have been later obliterated by other operations, the result field of Op would still be set. Detailed description. Consider an implementation of a data structure that is represented as a set of nodes, each with data fields and pointers to other nodes in the data structure. Each node is augmented with an info field containing a pointer to an Info structure, which may be tagged. (We implement tagging by setting the less significant bit of info.) When an Info structure is first installed in (i.e., 's info field is set to point to this Info structure), the node pointer to the Info structure is always tagged. A node is tagged if its info field is tagged. Tagging a node acts like locking it. The node may be later unlocked by untagging it.
High-level pseudocode appears in Algorithm 1 (where the code in blue, dealing with recovery, and the code in red, dealing with persistency, are explained below). GetTagged (getUntagged) returns a tagged (untagged) version of its argument without changing its value. We assume that CAS returns the value it read from the variable. An execution of an operation Op by a process goes through one or more attempts, each of which is an iteration of a while loop (Line 6), until one of them is successful and Op returns. In each of its attempts, Op first executes its gather phase, where it traverses the data structure gathering those nodes that it will affect, i.e., those nodes that it will attempt to update or delete, nodes that need to be locked for performing these updates and deletions, as well as nodes that contain values the operation will return or are needed to determine the operation's response. As an example, in a sorted linked list, a successful insert (or delete) affects the last two nodes it accesses during its search. On the other hand, a Find (or an unsuccessful update) affects only the last node it accesses. This set of nodes is called the AffectSet of Op. Specifically, the AffectSet is comprised of pairs, each containing a pointer to such a node and the value of its info field.
Op then proceeds to its helping phase. If an info field nd-Info (of a node nd) in AffectSet is tagged, then Help is used to complete the operation that tagged the node (i.e. the operation for which information is stored in ndInfo), before starting a new attempt. After the helping phase, the WriteSet and the NewSet-needed to complete Op-are created. The WriteSet contains those fields of nodes from AffectSet that need to change, together with an old and a new value for each of them (needed to perform the change using CAS). The NewSet contains all newly allocated nodes by Op that are necessary for applying its updates (all these nodes are initially tagged with a pointer to Op's opInfo). Then, the type of Op, its AffectSet, its WriteSet, its NewSet, and the value ⊥ (which is the initial value for the result field) are stored in the Info structure pointed to by opInfo. Next, Help is called with parameter opInfo to complete Op itself. If Help returns with result ≠ ⊥, then has been performed and its result is returned; otherwise, a new attempt is started.
Help tries to complete the operation described by opInfo. First, it applies CAS to try to install opInfo in every node of AffectSet, in order (tagging phase). If any of these CAS operations fails or the associated Info field is tagged by another operation, then a backtrack phase untags the nodes in AffectSet, in reverse order. After backtracking, Help returns. If every node of AffectSet is successfully tagged with opInfo, then all changes to the WriteSet are being performed and the result field is updated. Finally, a cleanup phase untags every node of AffectSet and NewSet still in the data structure.
Note that a new Info structure is allocated only initially (Line 1) and after a non-empty backtrack phase (Line 35). This avoids the unnecessary overhead of allocating a new Info structure before calling Help in each attempt. Note also that no process is aware of an operation if its invoker does not tag at least one node. Thus, given that tagging starts with the first node in the AffectSet, operations that help do not need to try tagging that node. This is implemented with the second parameter of Help which differentiates the invoker of by its helpers and starts tagging either from the first or the second element of 's AffectSet, respectively.
We make the following assumptions about the implementation: (a) It handles the ABA problem, i.e., it does not store the same value into the same shared variable more than once in any execution. (b) The nodes in the AffectSet or WriteSet are always accessed in the same order. 3 (c) Help is idempotent and can be executed concurrently by several processes; Help is idempotent if its changes are applied exactly once independently of how many times they will be performed.
If Help completes the tagging phase for the opInfo of Op, it returns only after Op takes effect: all CAS operations are applied to its WriteSet, its result is updated and the cleanup phase is done. If no process completes the tagging phase of Help, then Op does not take effect.
In order to support detectable recovery, a pointer to the Info structure being used in the last attempt of Op is persisted in RD (recall that is the process that invoked Op). Initially, RD is set to Null, and a check-point is set, indicating that a new operation has started. A pointer to the Info structure used in each attempt is stored in RD before Help is called. Upon recovery, Op-Recover is called with the same arguments as that of Op (see Section 2). If the check-point is not set or RD is still Null, Op has made no changes and can simply be restarted. Otherwise, the Info structure pointed to by RD , opInfo, indicates whether the last attempt of Op was successful, and if not, whether it crashed while making changes. Since Help is idempotent, recovery can call Help(opInfo) to complete Op, in case it is still in progress. When Help returns, either Op took effect and result stores its response, or it did not and result is ⊥; in the latter case, Op can be re-invoked. It is necessary to call Help first, to deal with the case in which result has been written but the operation still needs to clean up, in order to keep the data structure in a consistent state, without nodes tagged by Op. Lock-freedom (proof outline). Since Help is wait-free, as it contains no unbounded loops, recovery is also wait-free.
If in an execution, all processes repeatedly perform failed attempts, then the data structure remains static, and only info fields are changed. Note that in this case, after some point, it must hold that for every active operation Op, Op's tagging phase does not complete. By inspecting the pseudocode, we see that, otherwise, Op would also complete successfully (contradicting our hypothesis that all processes repeatedly perform failed attempts).
Consider a process making infinitely many failed attempts while executing Op. Each attempt has a gather phase, followed by a call to Help that fails tagging and performs a backtrack phase. Since only info fields are changed, completes the gather phase with the same AffectSet. An attempt fails because some node in AffectSet is tagged by another operation Op ′ . If the process executing Op ′ does not take steps (i.e. it is inactive), then the node is untagged, by or 3 Many generic techniques assume a similar total order assumption for ensuring lock-freedom and avoiding live-lock. The total order can be imposed in many ways and is not necessarily fixed at the beginning of the execution. For example, in a binary search tree, ordering can be determined by inorder or other traversal orders. Note also that it is only the concurrently active processes that need to use the same total order, so different orderings can be used during a single execution. Traverse the data structure gathering pairs ⟨nd, ndinfo⟩ of pointers to those nodes (and to their info fields) that Op will affect, e.g. will try to update or delete, as well as nodes that contain the values the operation will return (the info field of each node is gathered on the first access to it) Eventually, we reach a scenario where all operations perform failed attempts, each with the same AffectSet, in which one of the nodes is tagged by another active operation. We now show that the total order assumption prevents such a scenario (of having a livelock). Let ′ be the process that tagged the latest node in the total order by which processes tag the nodes in their AffectSet. Clearly, no later node in AffectSet of ′ is tagged by an active operation, and thus ′ will complete its tagging phase, and its attempt successfully. Linearizability (proof outline). Intuitively, tagging puts "soft" locks on the nodes in the AffectSet of an operation Op (initiated by a process ): it ensures that these nodes are not updated (by operations not helping Op) until Op's backtrack or cleanup phase completes. The cleanup phase starts only after some process successfully updates Op's WriteSet and the response in result. Since Help is idempotent, a node is changed exactly once. It can be shown that the info field of a node does not hold the same pointer twice whenever it is tagged. Other fields are not prone to ABA, by assumption.
These features ensure that Help succeeds in updating the write set, unless some other Help invocation for Op has started the cleanup phase, implying that the WriteSet has already been updated. Thus, Op succeeds after its invocator collects a consistent set of nodes, which do not change until some process completes the updates on the WriteSet.
We linearize Op at the beginning of the update phase. The above argument implies linearizability, as at this point the operation is guaranteed to complete, and other operations accessing any node in the AffectSet must first help Op to complete. Moreover, detectability follows as well, since a cleanup phase is performed only after Op completes all its updates, and result is updated with Op's response. Persistency instructions for the shared cache model. There is a simple transformation [27] from the private cache to the shared cache model, which puts a pbarrier (a pwb followed by a pfence) after each access to a shared object, and a psync before returning from an operation. However, the overhead of this transformation is very big (see Section 5).
We now explain the customized persistence code, shown in red. We note that an operation Op tags news nodes it allocates with a pointer to its Info structure, before including them in its NewSet.
After setting the check-point, allocating a new Info structure and storing a reference to it in , a pwb followed by a psync ensures that the data is accessible upon recovery. A pbarrier after initializing ensures that pwbs are executed in program order. We also insert pwb after every CAS and write in Help. A psync at the end of every phase persists its changes before the next phase.
An attempt to execute the changes of an operation Op, with an Info structure opInfo, happens after tagging is complete and persisted in Help(opInfo). A crash before tagging ends may result in an old copy for the Info field of some nodes, but in this case, no process started the update phase using the lost opInfo. Thus, upon recovery, the initiator of Op will call Help(opInfo) to tag again. Nodes are updated only after all nodes in AffectSet, as well as new nodes added to the data structure, are tagged and persisted. Every operation affected by these nodes, must first complete Help(opInfo). A node is untagged only in the cleanup phase, after all changes of the operation and its result field are persisted.
A crash during cleanup may cause an untagged node nd to be tagged, although another operation Op ′ might have tagged nd in the meantime. Then the tagging phase by Op ′ is yet to be completed, and both Op and Op ′ invoke Help on recovery. Thus, Op must first untag nd before Op ′ can tag it again. To improve performance, all pwb instructions can be issued at the end of the phase, before the psync; a single pwb flushes all fields fitting in a cache line.
The correctness argument remains the same, although the following scenario may occur: a tagging phase (for opInfo) may tag all the AffectSet, but some of these tags (not necessarily in order) were not persisted when a crash occurs. At recovery, a different operation may already tagged some of these untagged nodes, and re-tagging may fail. Then, backtracking will only untag a prefix of AffectSet, while other nodes are still tagged (for opInfo). A similar scenario occurs if a process fails during cleanup. These scenarios do not violate durable linearizability or lock-freedom: Since Help is idempotent, any process that later observes one of these tagged nodes, will fail during tagging and untag the node. Optimizing for read-only operations. We now discuss cases where ISB-tracking can be optimized to achieve better performance. Many concurrent data structures, including those implementing dictionaries, support read-only operations (e.g., Finds) for which the AffectSet contains just a single element; moreover, they determine their response values based on node fields that are immutable. Under these conditions, ISB-tracking can be optimized so that a process Traverse the data structure gathering pairs ⟨nd, ndinfo⟩ of pointers to those nodes (and to their info fields) that Op will affect, e.g. will try to update or delete, as well as nodes that contain the values the operation will return (the info field of each node is gathered on the first access to it) executing such a read-only operation is performed without executing Help for , i.e. by skipping the last three phases of Algorithm 1. The optimized pseudocode appears in Algorithm 2 (with changes appearing in green on Lines 73-74 and 78-79). It checks whether the appropriate conditions hold for the operation (i.e., if it is read-only and its AffectSet contains a single element), and if this is the case, it computes (Line 74) and returns (Line 79) its response (without calling Help). Note that the response, once computed, needs to be persisted. To reduce the persistency cost, we compute the response earlier than the place we return it, so it is persisted through the pbarrier of Line 75 and the psync of Line 77. Section 4 provides an example of a sorted linked list which we obtain by applying Algorithm 2. Note that optimizations aiming to improve the performance of read-only operations may affect the way we assign linearization points. For instance, in Algorithm 2, updates are still linearized at the beginning of their update phase. However, a read-only operation (that satisfies the optimization condition) is linearized at the point that the Info field of the single node added in the AffectSet is read in 's last attempt. To argue about correctness, we provide a simulation proof, where for each execution of Algorithm 2, we present a valid execution ′ of Algorithm 1 which contains the same operations as and each operation has the same response in both and ′ . Consider a read-only operation (that satisfies the optimization condition) executed by some process in . We construct ′ by letting execute solo (i.e., without any other process taking steps concurently with it), starting from the instruction at which it is linearized, the part of (Algorithm 1) that it is still to be executed in order to complete. Since Op does not change the data stucture, the resulting execution (in which tags and untags the single node in its AffectSet before any other process takes steps) is a valid execution of Algorithm 1. To get ′ , we apply this technique to all read-only operations that can be optimized .

Detectably Recoverable Linked List
In this section, we illustrate how to apply Algorithm 2 to get a detectable linked list. The list is sorted in increasing order of keys, with two sentinel nodes, head and tail, holding keys −∞ and +∞. The next field of a node points to the next node in the list. A node may be tagged either for update (indicating its next field is about to change), in which case it is untagged after the update completes, or for deletion (indicating it is to be deleted), in which case it remains tagged forever. When is tagged, its Info structure contains information necessary to complete the operation that tagged . A field opType in the Info structure indicates the operation type (Insert or Delete). (More details, including data types, shared variables, and initialization values of the algorithm are provided in the supplementary material.) An instance of Insert( ) (Algorithm 3), executed by a process , calls Search during its gather phase (Lines 90-91) to get pointers pred and curr to the nodes between which should be added, and their info fields. If is successful, these are the nodes contained in 's AffectSet. Thus, the helping phase (Lines 94-98) simply checks whether these two nodes are tagged and calls Help if needed.
If the key to be inserted is already in the list, is readonly and behaves like a Find. So, in this case, the AffectSet includes just the last node accessed by its search. We can then apply the optimization for read-only operations, as shown in Lines 104-105 and 109-109. Otherwise, calls Help (Line 110), shown in Algorithm 4. Help starts by executing 's tagging phase: It first tries to tag pred for update (Line 129), so that it can later change its next field (Line 144). (IsTagged checks whether the Info field of a node is tagged.) Next, Help tries to tag curr for deletion by a mark CAS (Line 133). If this CAS fails, untags (Line 138) and restarts its own operation. Once both nodes are tagged, Insert is guaranteed to succeed. The new node containing is inserted between pred and the copy of curr, by a CAS that points the next field of pred to the new node (Line 144). A copy of curr is used to avoid the ABA problem. A successful Insert allocates two new nodes, as well as a new Info object only each time it fails to tag (Line 136). Delete is simpler than Insert since it does not allocate new nodes; its code appears as Algorithm 5 in the supplementary material. Delete( ) uses Search to get pred and curr, and then tries to tag pred for update (Line 129) and curr for deletion (Line 133). If both nodes are tagged, Delete is guaranteed to succeed. The node with key is physically deleted from the list with a CAS (Line 144).
Find( ) (Algorithm 3) is read-only and computes its response based on immutable fields. Moreover, 's AffectSet contains just the node pointed by . Therefore, Find is optimized to avoid installing an Info structure. Recovery is achieved in exactly the same way as in Algorithm 2.

Evaluation
Evaluated Implementations. For our experiments, we use the Harris' linked list [23,25] as our example data structure. We compare our general approach (described in Algorithm 2) with capsules [3]. Capsules is a syntactical transformation which can be applied to concurrent algorithms that use only read and CAS operations to make them detectably recoverable. They achieve this by partitioning their code into capsules, each containing a single CAS operation, and replacing each CAS with its recoverable version [1]. In general, a single operation may be partitioned to multiple capsules, but normalized implementations [35] can be optimized so that each operation is partitioned to only two capsules. We experimented with both the general and the normalized variants. Since the normalized variant consistently outperformed the general variant, we only present the results of the former. To appropriately add persistency instructions to capsules without jeopardizing the generality of the approach, it is proposed in [3] to use a general durability transformation [27] (which adds pwb and pfence after each access to shared memory).
We compare the detectably recoverable linked list of Section 4, which we call Isb, with a linked list implementation, called Capsules, obtained by applying the capsules transformation (plus the durability transformation of [27]), to Harris' linked list [23,25]. We are not aware of other general schemes for deriving detectably recoverable data structures in the literature. As ensuring detectability is costly, we did not compare the performance of Isb with other schemes (e.g. [7,11,14,26,29,37]) that are durable but not detectable.
We have also undertaken the challenging task of adding persistency instructions in a manual, hand-tuned way to both Isb and Capsules. This resulted in two new implementations, called Isb-Opt and Capsules-Opt, respectively. Moreover, we developed an additional technique, called direct tracking (DT). Direct tracking uses an algorithmic idea utilized in [20] for implementing a recoverable queue. It is applicable to implementations in which every update takes effect in a single CAS (e.g., [19,23,30]) and requires an arbitration mechanism that helps determine the responses of updates that failed while competing to apply the same change to the data structure (e.g., deleting the same node). Upon recovery, each of these processes competes to become the one to which the successful execution of the primitive operation is attributed, thereby determining its response value. Persistency instructions (i.e., flushes and fences) were added based on the abstract guidelines provided in [20]. Doing so was not an easy task as [20] does not provide a mechanical approach for applying the guidelines in order to get a recoverable data structure. The resulted implementation has been optimized in a hand-tuned way to further reduce the persistency overhead. This resulted in DT-Opt.
In addition to linked list algorithms, we also implemented an ISB-based queue and compared it against a capsules-based queue [3] and a log queue [20]. Evaluation results show that none of the queue algorithms scale and their throughput becomes very low for 16 or more threads. The ISB-based queue outperforms the two other algorithms for 8 or more threads. For lack of space, the results of our queue experiments are described in the supplementary material. Experimental setting and benchmarks. We used a 40core machine with 4 Intel(R) Xeon(R) E5-4610 v3 1.7Ghz CPUs with 10 cores each with hyper-threading support (for a total of 80 hardware threads) and 25MB L3 cache. The machine runs CentOS Linux 7.5.1804 with kernel version 3.10.0-862.14.4.el7.x86_64 and has 256GB RAM. Code is written in C++ and compiled using g++ (version 4.8.5) with O3 optimizations. Each experiment lasts 5 seconds and each data point is the average of 10 experiments. Keys are chosen uniformly at random from the ranges [1,500] or [1,1500].
Experiments with more key ranges can be found in the supplementary material, while they exhibit the same trends with our analysis below. The list is initially populated by performing 250 or 750 Inserts, respectively, resulting in an almost 40%-full list. We present update-intensive (30% finds) and read-intensive (70% finds) benchmarks. Results for other operation type distributions were similar.
As we do not have machines with NVRAM in our sites to run our experiments, we follow a similar approach as in [3,20] and simulate pwb using clflush and psync using mfence, expecting performance overhead close to the real overhead of a persistency instruction [4,6] in systems supporting NVRAM (such as 3DXPoint). Since we assume TSO, there is no need to simulate pfence. Experimentation on machines with NVRAM is left for future work. Experimental Analysis. The results of our experiments are shown in Figure 1. Throughput evaluation results are shown by Figures 1a, 1d, 1e and 1f. The throughput of Capsules is extremely low due to the high number of persistency instructions incurred by the transformation in [27]. On the contrary, Isb exhibits good performance despite its generality.
We next compare the performance of Isb with the linked list implementations that have been optimized in a handtuned manner, namely Capsules-Opt and DT-Opt. As we see in Figure 1, our general scheme has comparable (and sometimes better) performance to that of these algorithms. This shows that the overhead of Isb is low.
To achieve a fairer comparison, we have developed a handtuned optimized version of Isb, called Isb-Opt, which we compare with Capsules-Opt and DT-Opt. It can be seen that Isb-Opt's relative performance improves as the number of threads increases. Specifically, in the read-intensive case and for small key ranges (that result in higher contention), the speedup of both DT-Opt and Capsules-Opt becomes very small after 32 threads, whereas Isb-Opt continues to exhibit significant speedup up to the 80 supported threads. Isb-Opt's scalability stems from the fact that it performs fewer barriers per operation (Figure 1b).
We note that if a node is deleted, its marked bit must be persisted. Otherwise, the following bad scenario may happen: a thread executing Find, searching for a key which has been logically deleted without persisting its marked bit, may run to completion and return false. Then, a crash may cause the logically deleted node to appear in the linked list as unmarked. A subsequent Find would then return true, which is incorrect. Because of the way helping is performed in ISB-tracking, no paths of marked nodes can be created in the data structure. Therefore, there are no chains of nodes that have changed and need to be persisted. So, a thread has to perform barrier (i.e., a clflush followed by an mfence) only on nodes in the AffectSet of its current operation . It thus performs a constant number of barriers in each attempt of , regardless of the total number of threads (see Figure 1b). In contrast, in both Capsules-Opt and DT-Opt, an operation may depend on a long chain of nodes that are yet to be persisted. So, both Capsules-Opt and DT-Opt perform a barrier each time they traverse a marked node. As the number of threads increases, barrier is performed on more marked nodes, increasing the persistency cost.
We also see (Figure 1c) that Isb-Opt performs on average more stand-alone clflush instructions (not included in a barrier) than the other algorithms (but still only a constant number per operation). This results from the need to persist , , and other variables. This explains why Isb-Opt is outperformed by the other algorithms when the number of threads is small, as well as why the crossing point of the Isb-Opt curve with the other curves moves to the right in update-intensive workloads. For large key ranges, the list is longer and marked nodes are more scattered in the list, so a thread traverses more nodes between two marked nodes 1 and 2 . This often provides sufficient time for the thread that marked 2 to physically remove it from the list, so that never reaches it, thus reducing the number of marked nodes traversed by threads. Experimental results for the privatecache model, where no algorithm incurs persistency cost, support these observations (see supplementary material).

Detectably Recoverable Versions of Additional Data Structures
We briefly discuss additional data structures that can become detectably recoverable by applying the ISB approach. Due to lack of space, the details of the implementations discussed below will be provided in the paper's full version.
Detectably Recoverable Binary Search Tree. The algorithm in [17] (LF-BST) implements a leaf-oriented (external) binary search tree. It uses CAS to flag an internal node whenever a child pointer of it is to be changed, and to mark it whenever it is to be deleted. A process , executing an update , allocates an Info structure where it records the information needed by other processes to help complete. Each internal node contains an update field which stores a reference to an Info structure and a 2-bits field which indicates whether the node is flagged for insertion, flagged for deletion, marked, or clean. Each successful flag or mark CAS installs a pointer to the Info structure of the relevant operation in the update field of the node it is applied on.
We employ the ISB-tracking approach (Algorithm 2) to make LF-BST detectably recoverable. Consider an operation and let , and be pointers to the leaf 's search arrives at, to its parent and to its grandparent, respectively. If is an Insert, it replaces the node pointed to by with a subtree of three nodes. Thus, 's AffectSet contains a pointer to and a pointer to (as its child pointer will change to point from to the root of the new subtree). 's WriteSet contains , and 's NewSet contains the three new nodes of the subtree that replaces . If is a Delete, changes the appropriate child pointer of to point to the sibling of . For applying ISB-tracking, we need to create a copy of this sibling, to avoid the ABA problem. Therefore, 's AffectSet contains , , , and a pointer to 's sibling; its WriteSet contains and its NewSet the new node that replaces 's sibling. The AffectSet of a Find contains only . Finds can be further optimized to have their AffectSet be equal to the empty set. Processes can use the field that already exists in the tree nodes and the Info structures used in LF-BST, to implement ISB-tracking without any significant memory overhead. Also, the tagging mechanism is provided for free through the flagging and marking mechanism of LF-BST. Detectably Recoverable Exchanger. An Exchanger [25,34] allows two processes to pair-up the operations they are executing and exchange values. The first process, , to arrive to an Exchanger, finds it free and captures it by atomically writing to it its value. Then, busy-waits until another process collides with it: if arrives while is waiting, it reads 's value in the Exchanger, and tries to atomically write its value to it and inform of a successful collision.
We employ the tracking approach to achieve recoverability: processes exchange Info structures (ExInfo) instead of values. In addition to state and value fields, ExInfo contains a result field, and a partner field pointing to the ExInfo of the operation with which is trying to collide.

Related Work and Discussion
We present the ISB-tracking approach for detectable recovery of concurrent data structures and apply it to many wellknown concurrent data structures, e.g., queues, linked lists, trees, as well as to exchangers. There are several recoverable concurrent implementations of specific data structures such as mutual exclusion locks [21,22], queues [20,28] and B-trees [9,31,36], with optimizations exploiting specific aspects of the objects. In contrast, our approach is general and derives recoverable implementations from their nonrecoverable counterparts, preserving their efficiency.
Our implementations are strictly recoverable [1]: the response of a recoverable operation is made persistent before completes, so that a higher-level operation that invokes is able to access 's response value, even if a crash occurs after completes. They also satisfy nesting-safe recoverable linearizability (NRL) [1]: a failed operation is linearized within an interval that includes its failures and recovery attempts. This implies durable linearizability (DL) [27]the state of the object after a crash reflects a consistent operation sub-history including all operations completed by the time of the crash, and some operations in progress when the crash occurred may be lost. Info structures were used in DL implementations of several data structures [10,32,39], and other transformations that avoid logging [15,27], but none of them ensures detectability.
The recoverable log queue [20] augments queue nodes with tracking information, which is used after a system-wide crash to synchronously try and complete all pending operations from the previous phase before starting a new phase. Two other recoverable queues in [20] are not detectable.
An NRL implementation can be obtained from any algorithm using only read, write and CAS primitives by replacing each primitive with its (NRL) recoverable version (see [1]). Implementations using only read and CAS can be made recoverable and detectable using capsules [3] (see Section 5).
A recoverable lock-free universal implementation [12] requires only one round trip to NVRAM per operation, which is optimal. It is essentially log-based, keeping the entire history of the object in a designated shared queue. It also keeps a per-process persistent log, such that, collectively, these logs keep the entire history, but different logs may have a big overlap. To determine the response of an operation, the entire history is read until its linearization point, where the operation's response can be determined, making the construction detectable. This construction makes the strong assumption that a single recovery function is executed upon recovery, consistently reconstructing the data structure, whereas we allow failed processes to be recovered by the system in an asynchronous manner. Romulus [13] is a persistent transactional memory framework that provides durability and detectability. However, it is blocking, satisfying only starvation-freedom for update transactions. Other logging-based approaches are [7,11].
Our observations that helping can be leveraged for recovery resemble the usage of re-entrant and idempotent helping for lock-free memory reclamation in lock-free data structures [5].
Our recoverable implementations-as well as the original, non-recoverable implementations-rely on garbage collectors that correctly recycle memory once it becomes unreachable. This naturally motivates the question of implementing lock-free recoverable memory managers [4,33], which we plan to investigate in future work. Another research avenue we plan to pursue is further experimental evaluation of our recoverable implementations, in particular, the interaction of the NVRAM with system caches. In this section, we provide additional material for the detectably recoverable linked list implementation presented in Section 4, including data types, shared variables, and initialization values in Figure 2 and the pseudocode for Delete in Algorithm 5. Figure 3 illustrates the throughput of all linked list algorithms for the following key ranges: [1,1000], [1,2000]. Results for the read-intensive workload are presented on the left and those for the update-intensive workload are presented on the right. Throughput results exhibit the same trends we described and analyzed in Section 5 for other key ranges. Figure 4 presents the performance of the evaluated algorithms in the private cache model, where the persistency cost is zero (since no flushes or fences are required). This experiment emphasizes the overheads that are incurred by the algorithms due to additional metadata maintenance and CAS operations performed for guaranteeing detectable recoverability. In addition to evaluating the ISB-based, capsules and direct tracking linked lists, we also evaluate the original (nonrecoverable) linked list implementation of Tim Harris [23], which we name Harris-LL. All algorithms exhibit speedup, when there is no persistency cost. As expected, the performance of the Harris-LL algorithm is almost identical to that of direct tracking since the latter is based on the former and mainly adds to it persistency instructions required for detectability, which are not performed in the private cache  Procedure ⟨Node * , Node * , Info * , Info * ⟩ Search (T ) Figure 3. Throughput for key ranges [1,1000] and [1,2000] (the read-intensive benchmarks are shown on the left and the update-intensive benchmarks are shown on the right).

B.1 Linked Lists
As we have shown in Section 5, this gap is decreased and even reversed for large numbers of threads, when persistence instructions are performed, as explained by our analysis in Section 5. Figure 5 and 6 show the numbers of pbarriers and standalone clflush instructions for the read-intensive and the update-intensive benchmarks, respectively, and key ranges: [1,1000], [1,1500], [1,2000]. They show the same trends exhibited by the experiments described in Section 5.

B.2 Queues
We also implemented an ISB-based queue, after adding flushes and fences as described in Section 3, and compared it with two other recoverable and detectable queues: the log queue [20] and the capsules-based queue [3], obtained by applying the capsules transformation to MS-Queue [30]. Specifically, we compared our ISB-based queue with two variants resulting from the capsules transformation: Capsules-General applies the capsules transformation to any data structure implementation, while Capsules-Normal applies a version of the capsules transformation that is optimized for normalized implementations [35], since the corresponding queue implementation is normalized. Persistency instructions were added to these implementations and were hand-tuned. The implementations of the log queue and the two capsule-based queues were provided by their authors.
As in [3,20,30], each thread applies pairs of enqueue and dequeue operations. Each experiment runs over 5 seconds and each data point is the average of 10 experiments. The queue is initially populated with one million nodes. As in [3,20], we simulate pwb using clflush and psync using mfence, expecting performance overhead close to the real performance overhead of a persistency instruction [4,6] in systems supporting NVM (such as 3DXPoint). Since we assume TSO, there is no need to simulate pfence.
The results (Figure 7) show that no algorithm is scalable and the throughput of the ISB-based queue exceeds that of the other algorithms for 8 threads or more. Additionally, the ISB-based queue performs better than Capsules-General for 3 or more threads and better than log queue for 6 or more threads.