All pointer-based nonblocking concurrent data structures should deal with the problem of \emph{safe
memory reclamation}: before reclaiming a memory block, a thread should ensure no other threads
hold a local pointer to the block that may later be dereferenced. Various safe memory reclamation
schemes have been proposed in the literature, but none of them satisfy the following desired
properties at the same time: $(i)$ \emph{robust}: a non-cooperative thread does not prevent the
other threads from reclaiming an unbounded number of blocks; $(ii)$ \emph{fast}: it does not incur
significant time overhead; $(iii)$ \emph{compact}: it does not incur significant space overhead;
$(iv)$ \emph{self-contained}: it neither relies on special hardware/OS supports nor intrusively
affects execution environments; and $(v)$ \emph{widely applicable}: it supports many data
structures.
We introduce PEBR, which we believe is the first scheme that satisfies all the properties above.
PEBR is inspired by Snowflake's hybrid design of pointer- and epoch-based reclamation schemes (PBR
and EBR, resp.) that is mostly robust, fast, and compact but neither self-contained nor widely
applicable. To achieve self-containedness, we design algorithms using only the standard C/C++
concurrency features and process-wide memory fence. To achieve wide applicability, we characterize
PEBR's requirement for safe reclamation that is satisfied by a variety of data structures, including
Harris's and Harris-Herlihy-Shavit's lists that are not supported by PBR. We experimentally
evaluate whether PEBR is fast and robust using microbenchmarks, for which PEBR performs comparably
to the state-of-the-art schemes.
Wed 17 JunDisplayed time zone: Pacific Time (US & Canada) change
09:20 - 10:20 | Memory ManagementPLDI Research Papers at PLDI Research Papers live stream Chair(s): Ting Cao Microsoft Research | ||
09:20 20mTalk | Improving Program Locality in the GC using Hotness PLDI Research Papers Albert Mingkun Yang Uppsala University, Sweden, Erik Ă–sterlund Oracle, Sweden, Tobias Wrigstad Uppsala University, Sweden | ||
09:40 20mTalk | A Marriage of Pointer- and Epoch-Based Reclamation PLDI Research Papers | ||
10:00 20mTalk | CARAT: A Case for Virtual Memory through Compiler- and Runtime-Based Address Translation PLDI Research Papers Brian Suchy Northwestern University, USA, Simone Campanoni Northwestern University, USA, Nikos Hardavellas Northwestern University, USA, Peter Dinda Northwestern University, USA |