Memory-management support for lock-free data structures is well known to be a tough problem. Recent work has successfully reduced the overhead of such schemes. However, applying memory-management support to a data structure remains complex and, in many cases, requires redesigning the data structure. In this paper, we present the first lock-free memory-management scheme that is applicable to general (arbitrary) lock-free data structures and that can be applied automatically via a compiler plug-in. In addition to the simplicity of incorporating to data structures, this scheme provides low overhead and does not rely on the lock freedom of any OS services. This work is licensed under a Creative Commons Attribution 4.0 International License. Nachshon Cohen a (possibly non-expert) practitioner to apply a memory-reclamation scheme when incorporating the data structure into a real application. However, state-of-the-art memory reclamation schemes require the data structure to satisfy certain algorithmic properties that are not met by many practical data-structures. If a data structure does not satisfy the required properties, there is no clear recipe for modifying it so that it would be amenable to memory reclamation. In general, applying a lock-free memory-reclamation scheme to a given data structure might requires expertise that is not available to all practitioners, might modify the properties of the data structure, or might not be possible at all. Consider, for example, Harris's linked list [Harris 2001 ] that stands at the core of many lock-free data structures. The original hazard pointers paper [Michael 2002a ] states that Harris's linked list is łinherently incompatiblež with the hazard-pointers scheme 1 . Instead, they designed a variation of this data structure Ð the Harris-Michael linked list [Michael 2002b ] Ð on which hazard pointers can be applied. The differences between these data structures are subtle, hence it is easy to confuse them. Such confusion can lead even experienced researchers to apply hazard pointers on the wrong data structure, resulting in an incorrect design. Furthermore, it was later shown that the Harris-Herlihy-Shavit linked list [Herlihy and Shavit 2012] is also incompatible with the hazardpointers scheme. This data structure offers stronger progress guarantees (i.e., wait-free searches) and better performance than the Harris-Michael linked list [Cohen and Petrank 2015a]. Other recent memory-reclamation schemes [Alistarh et al. 2015; Balmau et al. 2016; Braginsky et al. 2013; Brown 2015; Cohen and Petrank 2015b; Dice et al. 2016] are similarly incompatible with the Harris and Harris-Herlihy-Shavit linked-list data structures. In this paper, we present Free Access: the first memory-reclamation scheme that stands up to the expectations of the data-structure designers. The Free Access scheme does not require the data structure to satisfy any algorithmic properties, hence making it generally applicable for existing and future lock-free data structures. Instead, it requires only that no instruction simultaneously reads a new pointer and writes to the shared memory. All lock-free data structures we are aware of satisfy this property without any modification. We cannot preclude a future novel design that uses an unsupported instruction, but even such a design could be modified easily by replacing the unsupported instruction with a Compare-And-Swap (CAS) loop, enabling Free Access to be applied 2 . The main impact of the Free Access scheme is the decoupling of the design of lock-free data structures from the memory-reclamation effort; this decoupling enables designers of lock-free data structures to concentrate on designing the data structure without worrying whether their design is amenable to memory reclamation. The Free Access scheme is based on the concept of data-structure-specific garbage collection, introduced by Cohen and Petrank [2015a]. During the execution of the program, Free Access automatically determines the set of unreachable data-structure nodes and reclaims them for future allocations. The reclamation algorithm of Free Access is very similar to the Automatic Optimistic Access (AOA) scheme [Cohen and Petrank 2015a] and is loosely based on the mark&sweep garbagecollection technique. It starts by gathering the global roots, data-structure nodes that are reachable by all threads (e.g., the head of a linked list); and the local roots, the data-structure nodes residing in the registers and stack of each thread. Then, it traces these roots and marks all data-structure nodes that are reachable from one of the roots. Finally, it reclaims all data-structures nodes that are unmarked. (More background information is provided in Section 2). Although the reclamation algorithm of Free Access is very similar to the AOA scheme, there is a major difference between the two. The AOA scheme is applicable only for data structures written 1 Section 2.2.1 provides more background on this incompatibility 2 Section 6 discusses this unsupported instruction and presents the replacement algorithm.
Free Access REF ] automates the application of Automatic Optimistic Access.
Every data structure deserves lock-free memory reclamation
PACMPL
Computer Science