The lock-free, ordered, singly linked list as proposed in [5, 8] is a textbook example of a concurrent data structure [6, 10]. The data structure supports lock-free insertion and deletion, and wait-free contains operations on items identified by a unique key. The lock-free implementation is actually quite subtle. The ordering condition and a relaxed invariant makes it possible to do with a single-word Compare-And-Swap operation (CAS), and all operations can be shown to be linearizable even though linearization does not always happen at fixed points in the code. The lock-free data structure has many direct and indirect applications, notably in the implementation of concurrent skiplists and hash tables [8, 9, 11, 12].

The memory reclamation problem is to determine, for any given allocated memory node, when there are no more references to the node, allowing it to be safely returned to the memory management system. In a concurrent context, the memory reclamation problem is highly non-trivial, since there may be more than one thread referencing an allocated node unbeknownst to the other threads.

We present Stamp-it, a new, general, portable, lock-less concurrent memory reclamation scheme with amortized, constant-time (thread-count independent) reclamation overhead. Stamp-it has been implemented and proved correct in the C++ memory model using as weak memory-consistency assumptions as possible. We have (re)implemented six other comparable reclamation schemes. By a detailed performance comparison, we show that Stamp-it performs favorably, sometimes better, but at least as good as these other schemes while being able to reclaim free memory nodes earlier.