PaperlayerView exact revision on arXiv

Source-linked AI summary

Reclaiming memory for lock-free data structures: there has to be a better way

Trevor Brown

arXiv:1712.01044v1cs.DC

TL;DR

Lock-free reclamation must account for sleeping processes that may still hold pointers, while existing techniques can be inefficient or unsuitable for many data structures. The paper presents distributed epoch-based reclamation schemes and a lock-free memory-management abstraction. Experiments report low overhead for DEBRA and strong performance relative to hazard pointers.

  • Problem

    Lock-free reclamation must protect objects that sleeping processes may still access, while existing techniques are inefficient or unsuitable for many natural data structures.

    Source: §1 · pp. 1–2

  • Method

    DEBRA+ adds signaling to distributed epoch-based reclamation, and the Record Manager separates memory reclamation from lock-free data-structure code.

    Source: §1 · p. 3, §8 · p. 24

  • Results

    DEBRA is 4% slower on average than performing no reclamation, while DEBRA+ adds 2.5% average overhead and outperforms hazard pointers by 75% on average.

    Source: §1 · p. 3

  • Takeaways & Limitations

    The Record Manager lets a dynamic data structure be implemented without knowing how its records will be allocated or reclaimed.

    Source: §8 · p. 24

    Hazard pointers cannot be used with many lock-free data structures when operations cannot determine whether a node is retired.

    Source: §3 · p. 6

Abstract

from arXiv · show

Memory reclamation for lock-based data structures is typically easy. However, it is a significant challenge for lock-free data structures. Automatic techniques such as garbage collection are inefficient or use locks, and non-automatic techniques either have high overhead, or do not work for many data structures. For example, subtle problems can arise when hazard pointers, one of the most common non-automatic techniques, are applied to many lock-free data structures. Epoch based reclamation (EBR), which is by far the most efficient non-automatic technique, allows the number of unreclaimed objects to grow without bound, because one crashed process can prevent all other processes from reclaiming memory. We develop a more efficient, distributed variant of EBR that solves this problem. It is based on signaling, which is provided by many operating systems, such as Linux and UNIX. Our new scheme takes $O(1)$ amortized steps per high-level operation on the data structure and $O(1)$ steps in the worst case each time an object is removed from the data structure. At any point, $O(mn^2)$ objects are waiting to be freed, where $n$ is the number of processes and $m$ is a small constant for most data structures. Experiments show that our scheme has very low overhead: on average 10\%, and at worst 28\%, for a balanced binary search tree over many thread counts, operation mixes and contention levels. Our scheme also outperforms a highly tuned implementation of hazard pointers by an average of 75\%. Typically, memory reclamation is tightly woven into lock-free data structure code. To improve modularity and facilitate the comparison of different memory reclamation schemes, we also introduce a highly flexible abstraction. It allows a programmer to easily interchange schemes for reclamation, object pooling, allocation and deallocation with virtually no overhead, by changing a single line of code.

1 Introduction

Lock-free reclamation must protect nodes that sleeping processes may still access, while existing approaches can be inefficient or unsuitable for many data structures. The paper introduces DEBRA, DEBRA+, and a lock-free allocator abstraction, and reports low overhead for its reclamation schemes.

1 Introduction

  • Lock-free reclamation must coordinate around processes that may retain pointers to removed nodes, since freeing a node too early can cause crashes or subtle errors.Classical EBR can stop reclaiming memory if a process sleeps or crashes during an operation.Source: §1 · pp. 1, 3
  • Memory reclamation can be automatic or non-automatic; non-automatic schemes require data-structure operations to invoke procedures when records are removed.When processes can crash, a scheme cannot guarantee every retired record will eventually be reclaimed; fault tolerance instead bounds how many records crashes can prevent from being reclaimed.Source: §1 · p. 2
  • DEBRA distributes epoch-based reclamation and reduces overhead through amortized epoch checks, private limbo bags, and cache-aware optimizations.It performs O(1) steps at each operation’s beginning and end and each time a record is removed.Source: §1 · p. 3
  • DEBRA+ uses signals to make epoch advancement fault-tolerant, with at most O(mn^2) records waiting to be freed, where m is the largest number removed by one operation.Its goal is to let reclamation proceed without waiting indefinitely for slow or crashed processes that have not announced the current epoch.Source: §1 · p. 3
  • The lock-free Allocator abstraction separates reclamation choices from data-structure code, allowing schemes to be interchanged without requiring the structure to know when records are safe to free.The standard Allocator abstraction does not directly fit lock-free reclamation because its operations do not align with reclamation schemes.Source: §1 · p. 3
  • DEBRA is 4% slower on average and 21% slower at worst than performing no reclamation; DEBRA+ adds 2.5% average overhead and outperforms hazard pointers by 75% on average.DEBRA can improve performance by as much as 20% in some experiments.Source: §1 · p. 3

2 Model

The model is an asynchronous shared-memory system with n processes, primitive atomic objects, and records composed of fields. It also specifies cache-coherence, NUMA, and hardware-transactional-memory assumptions.

2 Model

  • The system has n asynchronous processes, private local memory, shared memory, and hardware-provided atomic primitive objects such as registers, CAS, and DWCAS.Records are collections of fields; data structures consist of entry points and records reachable from them, and an allocator allocates and frees records.Source: §2 · p. 4
  • The cache model uses MESI coherence: writes obtain a cache line in exclusive mode and invalidate copies in other processes’ caches.A last-level cache miss requires retrieving the cache line from main memory.Source: §2 · p. 4
  • The NUMA model places processes on sockets that share a last-level cache; writes invalidate copies on other sockets but not within the same socket’s shared cache.A remote-socket access may require retrieving the cache line from main memory.Source: §2 · p. 4
  • The model includes hardware transactional memory, where transactions commit atomically or abort without affecting shared memory.The considered Intel HTM implementation is best-effort and provides no guarantee that a transaction will commit.Source: §2 · p. 4

3 Related work

This section surveys memory-reclamation approaches for lock-free data structures, outlining limitations and alternatives across hazard pointers, reference counting, signaling, transactional, and epoch-based methods. It also covers fault-tolerant combinations of hazard pointers and epoch-based reclamation, and optimistic access with restrictive requirements.

Reference Counting and Beware & Cleanup

  • Reference counting can incur high overhead, needs extra per-record memory, and cannot reclaim cycles; Beware & Cleanup adds complexity and requires retired records to stop pointing to other retired records.B&C also has significantly higher overhead than hazard pointers, and designing its pointer-replacement procedure while preserving thread semantics is non-trivial.Source: §3 · pp. 5, 8

Hazard Pointers

  • Traditional hazard pointers require a memory barrier after each announcement, while scanning all processes’ pointers costs Θ(nk) steps and can leave O(kn^2) records awaiting reclamation.Batched scanning with a hash table gives expected amortized O(1) retirement cost; on modern Intel and AMD systems, delaying the barrier can cause reclamation to miss a hazard pointer.Source: §3 · pp. 5–6

Problems with Hazard Pointers

  • Hazard pointers can be unusable when operations cannot determine whether an announced node is retired; restarting on marked nodes can loop forever and violate lock-freedom.The problem arises when traversals can follow pointers from retired nodes to other retired nodes, including in search procedures that cannot safely restart.Source: §3 · pp. 6–7

ThreadScan

  • ThreadScan uses signals to scan private memory, but its global reclamation lock, wait for every acknowledgment, and delete-buffer assumption limit its progress guarantees and applicability.Its assumption that buffered records cannot be reached through heap or shared references excludes traversals from retired records to other retired records; the section notes that this assumption is stronger than those in HP and Pass-the-Buck.Source: §3 · pp. 8–9

Dynamic Collect and StackTrack

  • Dynamic collect and StackTrack explore transactional memory for tracking accesses, but StackTrack cannot handle traversals from retired nodes to other retired nodes.StackTrack splits operations into transactions and falls back to hazard pointers after repeated aborts; in the described list example, a node can be freed before a later segment reaches it, preventing progress.Source: §3 · pp. 9–10

Epochs

  • Epoch-based reclamation is efficient when processes do not carry pointers across operations, but is not fault-tolerant; QSBR permits saved pointers but requires manually identifying quiescent times.EBR uses three limbo bags and frees records from the oldest bag when the global epoch advances; its low overhead comes from announcing only at operation beginnings rather than on each record access.Source: §3 · p. 10

Drop the Anchor (DTA)

  • DTA is a fault-tolerant, singly linked-list technique that acquires a hazard pointer every c reads and cuts nodes a stalled process might access from the list.The process that detects the stall replaces the cut nodes with copies and marks the old nodes; a crashed process may leave those old nodes unreclaimed.Source: §3 · p. 10
  • DTA’s worst case leaves Ω(scn^2) retired nodes unreclaimed, and its list-specific design is difficult to extend and must integrate with list-update synchronization.The synchronization integration is needed because nodes may be cut out concurrently with other list updates.Source: §3 · pp. 10–11

QSense (QS)

  • QS requires a known ε bound and nonfailing rooster processes, so it is not fully asynchronous; a crash on the slow path can also prevent return to EBR.QS also cannot handle data structures where operations traverse pointers from one retired record to another.Source: §3 · p. 11
  • QS uses an EBR fast path while processes progress and switches to a hazard-pointer slow path when one stalls; EBR avoids scanning hazard pointers on the fast path.Rooster processes trigger context switches so reclaimers can see hazard-pointer announcements without requiring an additional barrier after each announcement.Source: §3 · p. 11

Optimistic Access (OA)

  • OA requires access to reclaimed memory without crashing, via unreleased memory or trapped faults, and entails extensive code changes that can complicate debugging and application.Each read becomes two reads, a branch, and possible write and jump; writes and CAS operations require four to seven writes plus additional steps.Source: §3 · pp. 11–12
  • OA [10] checks warning bits after reads and restarts from a safe checkpoint when reclamation is underway; it uses hazard pointers to protect records before CAS operations.OA requires algorithms in normalized lock-free form, where operations proceed through CAS generation, CAS execution, and wrap-up phases.Source: §3 · p. 12

4 DEBRA: Distributed Epoch Based Reclamation

DEBRA distributes epoch-based reclamation work across processes, reducing the cost of checking announcements while allowing reclamation to continue when a process is inactive outside an operation. Its local limbo bags and cache-conscious optimizations further reduce shared-memory overhead.

4 DEBRA: Distributed Epoch Based Reclamation

  • DEBRA lets reclamation continue when a process sleeps or crashes outside a data-structure operation; only a process currently executing an operation can block others.This can allow processes to be terminated or reassigned without permanently halting reclamation.Source: §4 · p. 13
  • Processes check epoch announcements incrementally across operations, reducing the overall cost of reads while potentially delaying reclamation.The cost reduction is especially relevant on NUMA systems, where cross-socket reads can incur expensive cache misses.Source: §4 · pp. 13, 16
  • Each process maintains its own local epoch bags, so reclamation proceeds independently rather than synchronizing on shared epoch bags.The bags are optimized for cache performance and low overhead.Source: §4 · p. 13
  • DEBRA provides four worst-case O(1)-step operations and assumes processes hold no record pointers between successive data-structure operations.A structure invokes leaveQstate and enterQstate around each operation and retire(r) when removing a record.Source: §4 · p. 13
  • DEBRA uses three limbo bags per process, moving records from the current bag toward a pool as announcements and epochs advance.Processes check other processes’ announcements and quiescent bits incrementally during leaveQstate.Source: §4 · pp. 14–15, Figure 4 · p. 14
  • Blockbags move full blocks between limbo and pool bags; per-process block pools keeping up to 16 blocks reduced block allocations by more than 99.9% in experiments.The experiments used blocks of 256 records; blocks moved to the shared bag reduce synchronization costs.Source: §4 · p. 15
  • Using the least significant announcement bit as a quiescent bit reduces shared-memory reads and writes, while thresholds limit checks that can add overhead.INCR_THRESH was 100 in the experiments; checking announcements less frequently can delay reclamation.Source: Figure 4 · p. 14, §4 · pp. 15–16

5 Adding fault tolerance

DEBRA+ adds fault tolerance to epoch-based reclamation by signaling and neutralizing processes that delay epoch advancement. Recovery code and limited hazard-pointer protections make interrupted operations safe, while the scheme bounds the number of records awaiting reclamation.

5 Adding fault tolerance

  • DEBRA’s own reclamation can be blocked indefinitely by a crashed or slow process that remains non-quiescent, leaving the number of waiting records unbounded.DEBRA+ addresses this with its neutralizing mechanism.Source: §5 · pp. 16, 18
  • A signal can neutralize a non-quiescent process, which enters a quiescent state and runs recovery code before resuming or restarting its operation.The scheme relies on the operating system guaranteeing that the signal handler runs the next time the process takes a step.Source: §5 · pp. 16–17
  • Operations suited to DEBRA+ separate quiescent preamble and postamble work from a non-quiescent body, where neutralization may occur.Allocation, deallocation, persistent local-state changes, and other non-reentrant actions belong outside the body.Source: §5 · p. 17
  • Recovery checks whether the operation descriptor was announced: if so, it helps complete the operation; otherwise, it can restart the body.Helping is safe if another process already helped because the help procedure is idempotent.Source: §5 · p. 17
  • Limited hazard pointers protect the descriptor and records needed during recovery, allowing reclamation to continue while a process recovers in a quiescent state.The process announces protections before helping and releases them after recovery or operation completion.Source: §5 · p. 18
  • DEBRA+ bounds waiting records by O(n(nm+c)), where n is the process count, m the maximum records removed per operation, and c a constant.The bound follows when a process neutralizes a non-quiescent process if its current limbo bag exceeds c.Source: §5 · pp. 18, 20
  • DEBRA+ scans limbo records only after a bag reaches a threshold, then hashes hazard-pointer addresses and rearranges blocks for efficient reclamation.The expected amortized cost to move or free a record is O(1).Source: §5 · p. 20
  • DEBRA+ is difficult to apply to lock-based structures because interrupting and restarting a process while it holds a lock is dangerous.The paper recommends DEBRA instead for lock-based structures.Source: §5 · p. 20

6 A lock-free memory management abstraction

The Record Manager separates data-structure code from allocation, reclamation, and pooling, making memory-management components easier to interchange. Its templated modular implementation avoids runtime dispatch overhead.

6 A lock-free memory management abstraction

  • The abstraction supports many reclamation schemes, including HPs, EBR, DEBRA, and DEBRA+, but not ST or OA, which require broader code instrumentation.ST requires transactions throughout the code; OA requires instrumentation of each read and CAS.Source: §6 · pp. 20–21
  • The Record Manager combines an Allocator, Reclaimer, and Pool, separating record allocation, safe reclamation, and decisions about reuse or freeing.Figure 7's arrows distinguish operations that invoke another component from those that may invoke one.Source: §6 · p. 21, Figure 7 · p. 21
  • C++ templates select component implementations at compile time, avoiding the runtime dispatch overhead that inheritance can introduce.Small functions can be inlined, eliminating the call altogether.Source: §6 · p. 21
  • The Reclaimer interface covers operation boundaries, pointer protection, retirement, quiescence checks, and crash-recovery protection.A successful protect permits access to a record's fields until it is unprotected or the process becomes quiescent.Source: §6 · p. 21
  • DEBRA and DEBRA+ compile protection calls away, while HP uses them to announce and release protected pointers and scan retired-record bags.The Record Manager maps the same interface to scheme-specific behavior.Source: §6 · p. 21
  • A compile-time supportsCrashRecovery predicate lets code invoke recovery operations for supported Reclaimers without adding those checks' runtime overhead to others.The experiments use it to invoke sigsetjmp only for DEBRA+.Source: §6 · pp. 21–22

7 Experiments

Experiments compare DEBRA and DEBRA+ with hazard pointers, transactional-memory reclamation, and no reclamation across tree and skip-list workloads. DEBRA-family reclamation generally has low overhead, while DEBRA+ limits memory growth when processes are delayed.

Experimental setup

  • The BST comparison includes HP, whose use required restarting operations that suspect retired nodes, thereby removing its lock-free progress guarantee.The same restarting behavior was added to DEBRA, with small performance impact; HP was tuned for performance rather than space efficiency.Source: §7 · p. 22
  • The skip-list comparison used ST instead of DEBRA+ because the lock-based skip list cannot use DEBRA+.The code was adapted to use a Record Manager for allocation and pooling.Source: §7 · p. 22
  • Trials used random operations on uniformly random keys for two seconds, after prefilling the structure to half the key range; each plotted data point averaged eight trials.The BST experiments varied thread count, operation mix, and key range.Source: §7 · p. 23

Experiment 1

  • In the BST, DEBRA averages 12% overhead and DEBRA+ 17%; DEBRA performs 94% more operations than HP on average, and DEBRA+ performs 83% more.In the skip list, DEBRA averages 4% overhead and outperforms HP by 200% and ST by 133% on average.Source: §7 · p. 23

Experiment 2

  • In the BST, DEBRA is 8% slower than None on average and sometimes 12% faster; DEBRA+ averages 10% slower, while DEBRA averages 80% faster than HP.In the skip list, DEBRA performs as well as None and averages 160% faster than ST.Source: §7 · p. 23
  • With 16 processes, DEBRA+ neutralizes processes an average of 935 times per trial, reducing peak memory usage by an average of 94% over DEBRA.Above eight processes, context-switched processes often prevent DEBRA from advancing the epoch promptly.Source: §7 · p. 24

Experiment 3

  • With malloc/free allocation, throughput is significantly lower than in earlier experiments; the results are otherwise similar, and uniform added overhead disproportionately affects low-overhead algorithms.HP and ST are proportionally less affected than None, DEBRA, and DEBRA+.Source: §7 · p. 24

8 Conclusion

DEBRA and DEBRA+ provide distributed epoch-based reclamation with reported performance and memory benefits; the Record Manager separates reclamation from lock-free data-structure code. The conclusion also identifies possible extensions of the neutralizing technique.

8 Conclusion

  • Figure 10 plots throughput in millions of operations per second against process count for Experiment 3, which uses malloc and a pool.Source: Figure 10 · p. 24
  • DEBRA is 4% slower on average than no reclamation and 21% slower at worst, while DEBRA+ is 10% slower on average and outperforms hazard pointers by 70% on average.DEBRA also outperforms StackTrack by 138% on average; DEBRA+ reduces memory consumption over DEBRA by 94%.Source: §8 · p. 24
  • DEBRA adds O(1) steps per data-structure operation and per retired record; DEBRA+ allows reclamation to continue after a process crashes, with O(mn^2) objects waiting to be freed.The cost to reuse or free a record is O(1) expected amortized time.Source: §8 · p. 24
  • The Record Manager separates memory reclamation from lock-free data-structure code, allowing allocation and reclamation choices to be changed with virtually no overhead.Programmers can interchange reclamation, pooling, allocation, and deallocation techniques by changing one line of code.Source: §8 · pp. 24–25
  • The authors identify adapting neutralizing to different operating systems, garbage collection, and some lock-based algorithms as possible directions for future work.Source: §8 · p. 25
Loading 1712.01044v1…