| atomic.rs |
|
55387 |
| collector.rs |
|
12179 |
| default.rs |
The default garbage collector.
For each thread, a participant is lazily initialized on its first use, when the current thread
is registered in the default collector. If initialized, the thread's participant will get
destructed on thread exit, which in turn unregisters the thread. |
2501 |
| deferred.rs |
|
4053 |
| epoch.rs |
The global epoch
The last bit in this number is unused and is always zero. Every so often the global epoch is
incremented, i.e. we say it "advances". A pinned participant may advance the global epoch only
if all currently pinned participants have been pinned in the current epoch.
If an object became garbage in some epoch, then we can be sure that after two advancements no
participant will hold a reference to it. That is the crux of safe memory reclamation. |
4751 |
| guard.rs |
|
19403 |
| internal.rs |
The global data and participant for garbage collection.
# Registration
In order to track all participants in one place, we need some form of participant
registration. When a participant is created, it is registered to a global lock-free
singly-linked list of registries; and when a participant is leaving, it is unregistered from the
list.
# Pinning
Every participant contains an integer that tells whether the participant is pinned and if so,
what was the global epoch at the time it was pinned. Participants also hold a pin counter that
aids in periodic global epoch advancement.
When a participant is pinned, a `Guard` is returned as a witness that the participant is pinned.
Guards are necessary for performing atomic operations, and for freeing/dropping locations.
# Thread-local bag
Objects that get unlinked from concurrent data structures must be stashed away until the global
epoch sufficiently advances so that they become safe for destruction. Pointers to such objects
are pushed into a thread-local bag, and when it becomes full, the bag is marked with the current
global epoch and pushed into the global queue of bags. We store objects in thread-local storages
for amortizing the synchronization cost of pushing the garbages to a global queue.
# Global queue
Whenever a bag is pushed into a queue, the objects in some bags in the queue are collected and
destroyed along the way. This design reduces contention on data structures. The global queue
cannot be explicitly accessed: the only way to interact with it is by calling functions
`defer()` that adds an object to the thread-local bag, or `collect()` that manually triggers
garbage collection.
Ideally each instance of concurrent data structure may have its own queue that gets fully
destroyed as soon as the data structure gets dropped. |
21497 |
| lib.rs |
Epoch-based memory reclamation.
An interesting problem concurrent collections deal with comes from the remove operation.
Suppose that a thread removes an element from a lock-free map, while another thread is reading
that same element at the same time. The first thread must wait until the second thread stops
reading the element. Only then it is safe to destruct it.
Programming languages that come with garbage collectors solve this problem trivially. The
garbage collector will destruct the removed element when no thread can hold a reference to it
anymore.
This crate implements a basic memory reclamation mechanism, which is based on epochs. When an
element gets removed from a concurrent collection, it is inserted into a pile of garbage and
marked with the current epoch. Every time a thread accesses a collection, it checks the current
epoch, attempts to increment it, and destructs some garbage that became so old that no thread
can be referencing it anymore.
That is the general mechanism behind epoch-based memory reclamation, but the details are a bit
more complicated. Anyhow, memory reclamation is designed to be fully automatic and something
users of concurrent collections don't have to worry much about.
# Pointers
Concurrent collections are built using atomic pointers. This module provides [`Atomic`], which
is just a shared atomic pointer to a heap-allocated object. Loading an [`Atomic`] yields a
[`Shared`], which is an epoch-protected pointer through which the loaded object can be safely
read.
# Pinning
Before an [`Atomic`] can be loaded, a participant must be [`pin`]ned. By pinning a participant
we declare that any object that gets removed from now on must not be destructed just
yet. Garbage collection of newly removed objects is suspended until the participant gets
unpinned.
# Garbage
Objects that get removed from concurrent collections must be stashed away until all currently
pinned participants get unpinned. Such objects can be stored into a thread-local or global
storage, where they are kept until the right time for their destruction comes.
There is a global shared instance of garbage queue. You can [`defer`](Guard::defer) the execution of an
arbitrary function until the global epoch is advanced enough. Most notably, concurrent data
structures may defer the deallocation of an object.
# APIs
For majority of use cases, just use the default garbage collector by invoking [`pin`]. If you
want to create your own garbage collector, use the [`Collector`] API. |
6331 |
| sync |
|
|