ccl_crossbeam_epoch/
lib.rs

1//! Epoch-based memory reclamation.
2//!
3//! An interesting problem concurrent collections deal with comes from the remove operation.
4//! Suppose that a thread removes an element from a lock-free map, while another thread is reading
5//! that same element at the same time. The first thread must wait until the second thread stops
6//! reading the element. Only then it is safe to destruct it.
7//!
8//! Programming languages that come with garbage collectors solve this problem trivially. The
9//! garbage collector will destruct the removed element when no thread can hold a reference to it
10//! anymore.
11//!
12//! This crate implements a basic memory reclamation mechanism, which is based on epochs. When an
13//! element gets removed from a concurrent collection, it is inserted into a pile of garbage and
14//! marked with the current epoch. Every time a thread accesses a collection, it checks the current
15//! epoch, attempts to increment it, and destructs some garbage that became so old that no thread
16//! can be referencing it anymore.
17//!
18//! That is the general mechanism behind epoch-based memory reclamation, but the details are a bit
19//! more complicated. Anyhow, memory reclamation is designed to be fully automatic and something
20//! users of concurrent collections don't have to worry much about.
21//!
22//! # Pointers
23//!
24//! Concurrent collections are built using atomic pointers. This module provides [`Atomic`], which
25//! is just a shared atomic pointer to a heap-allocated object. Loading an [`Atomic`] yields a
26//! [`Shared`], which is an epoch-protected pointer through which the loaded object can be safely
27//! read.
28//!
29//! # Pinning
30//!
31//! Before an [`Atomic`] can be loaded, a participant must be [`pin`]ned. By pinning a participant
32//! we declare that any object that gets removed from now on must not be destructed just
33//! yet. Garbage collection of newly removed objects is suspended until the participant gets
34//! unpinned.
35//!
36//! # Garbage
37//!
38//! Objects that get removed from concurrent collections must be stashed away until all currently
39//! pinned participants get unpinned. Such objects can be stored into a thread-local or global
40//! storage, where they are kept until the right time for their destruction comes.
41//!
42//! There is a global shared instance of garbage queue. You can [`defer`] the execution of an
43//! arbitrary function until the global epoch is advanced enough. Most notably, concurrent data
44//! structures may defer the deallocation of an object.
45//!
46//! # APIs
47//!
48//! For majority of use cases, just use the default garbage collector by invoking [`pin`]. If you
49//! want to create your own garbage collector, use the [`Collector`] API.
50//!
51//! [`Atomic`]: struct.Atomic.html
52//! [`Collector`]: struct.Collector.html
53//! [`Shared`]: struct.Shared.html
54//! [`pin`]: fn.pin.html
55//! [`defer`]: fn.defer.html
56
57#![warn(missing_docs)]
58#![warn(missing_debug_implementations)]
59#![cfg_attr(not(feature = "std"), no_std)]
60#![cfg_attr(feature = "nightly", feature(const_fn))]
61#![cfg_attr(feature = "nightly", feature(cfg_target_has_atomic))]
62
63#[macro_use]
64extern crate cfg_if;
65#[cfg(feature = "std")]
66extern crate core;
67
68cfg_if! {
69    if #[cfg(feature = "alloc")] {
70        extern crate alloc;
71    } else if #[cfg(feature = "std")] {
72        extern crate std as alloc;
73    }
74}
75
76#[cfg_attr(
77    feature = "nightly",
78    cfg(all(target_has_atomic = "cas", target_has_atomic = "ptr"))
79)]
80cfg_if! {
81    if #[cfg(any(feature = "alloc", feature = "std"))] {
82        extern crate arrayvec;
83        extern crate crossbeam_utils;
84        #[macro_use]
85        extern crate memoffset;
86        #[macro_use]
87        extern crate scopeguard;
88
89        mod atomic;
90        mod collector;
91        mod deferred;
92        mod epoch;
93        mod guard;
94        mod internal;
95        mod sync;
96
97        pub use self::atomic::{Atomic, CompareAndSetError, CompareAndSetOrdering, Owned, Pointer, Shared};
98        pub use self::collector::{Collector, LocalHandle};
99        pub use self::guard::{unprotected, Guard};
100    }
101}
102
103cfg_if! {
104    if #[cfg(feature = "std")] {
105        #[macro_use]
106        extern crate lazy_static;
107
108        mod default;
109        pub use self::default::{default_collector, is_pinned, pin};
110    }
111}
ccl_crossbeam_epoch/lib.rs

ccl_crossbeam_epoch/
lib.rs
