Safe Memory Reclamation for Dynamic Lock-Free Objects Using Atomic Reads and Writes

An earlier version of this paper was publicly available from this site as RC22317 in January 2002.

A major obstacle to the wide use of lock-free objects, despite their many advantages, is the absence of practical lock-free methods for reclaiming the memory of dynamic nodes re- moved from dynamic lock-free objects for arbitrary reuse. Prior memory management methods for dynamic lock-free objects suffer from one or more serious drawbacks: not allowing arbitrary memory reuse, allowing the failure or delay of a thread to cause an unbounded number of nodes to be not freed indefinitely, requiring special operating system support, or using atomic instructions not supported on any current processor architecture. This paper presents the first memory management method for dynamic lock-free objects that allows arbitrary memory reuse, guarantees an upper bound on the number of removed nodes not freed at any time regardless of thread failures and delays, and does not require special operating system or hardware support. Furthermore, it is wait-free, is only logarithmically contention-sensitive, and uses only atomic reads and writes for its operations. In addition, it can be used to prevent the ABA problem for pointers to dynamic nodes in most algorithms, without requiring extra space per pointer or per node.