Nonblocking data structures face a \emph{safe memory reclamation} (SMR) problem. In these algorithms, a node removed from the data structure cannot be reclaimed (freed) immediately, as other threads may be about to access it. The goal of an SMR scheme is to minimize the number of removed nodes that cannot be reclaimed—called \emph{wasted memory}—while imposing low run-time overhead. It is also desirable for an SMR scheme to be \emph{self-contained} and not require specific OS features.

No existing self-contained SMR scheme can guarantee a predetermined bound on wasted memory without imposing significant run-time overhead. In this paper, we introduce \emph{margin pointers} (MP), the first nonblocking, self-contained SMR scheme featuring both predetermined bounded wasted memory and low run-time overhead. MP targets search data structures, such as binary trees and skip lists, which are important SMR clients and also victims of its high overhead. MP’s novelty lies in its protecting \emph{logical} subsets of the data structure from being reclaimed, as opposed to previous work, which protects \emph{physical} locations (explicit nodes).