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`](Guard::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#![doc(test(
52 no_crate_inject,
53 attr(
54 deny(warnings, rust_2018_idioms),
55 allow(dead_code, unused_assignments, unused_variables)
56 )
57))]
58#![warn(
59 missing_docs,
60 missing_debug_implementations,
61 rust_2018_idioms,
62 unreachable_pub
63)]
64#![cfg_attr(not(feature = "std"), no_std)]
65
66#[cfg(crossbeam_loom)]
67extern crate loom_crate as loom;
68
69#[cfg(crossbeam_loom)]
70#[allow(unused_imports, dead_code)]
71mod primitive {
72 pub(crate) mod cell {
73 pub(crate) use loom::cell::UnsafeCell;
74 }
75 pub(crate) mod sync {
76 pub(crate) mod atomic {
77 pub(crate) use loom::sync::atomic::{fence, AtomicPtr, AtomicUsize, Ordering};
78
79 // FIXME: loom does not support compiler_fence at the moment.
80 // https://github.com/tokio-rs/loom/issues/117
81 // we use fence as a stand-in for compiler_fence for the time being.
82 // this may miss some races since fence is stronger than compiler_fence,
83 // but it's the best we can do for the time being.
84 pub(crate) use self::fence as compiler_fence;
85 }
86 pub(crate) use loom::sync::Arc;
87 }
88 pub(crate) use loom::thread_local;
89}
90#[cfg(target_has_atomic = "ptr")]
91#[cfg(not(crossbeam_loom))]
92#[allow(unused_imports, dead_code)]
93mod primitive {
94 pub(crate) mod cell {
95 #[derive(Debug)]
96 #[repr(transparent)]
97 pub(crate) struct UnsafeCell<T>(::core::cell::UnsafeCell<T>);
98
99 // loom's UnsafeCell has a slightly different API than the standard library UnsafeCell.
100 // Since we want the rest of the code to be agnostic to whether it's running under loom or
101 // not, we write this small wrapper that provides the loom-supported API for the standard
102 // library UnsafeCell. This is also what the loom documentation recommends:
103 // https://github.com/tokio-rs/loom#handling-loom-api-differences
104 impl<T> UnsafeCell<T> {
105 #[inline]
106 pub(crate) const fn new(data: T) -> UnsafeCell<T> {
107 UnsafeCell(::core::cell::UnsafeCell::new(data))
108 }
109
110 #[inline]
111 pub(crate) fn with<R>(&self, f: impl FnOnce(*const T) -> R) -> R {
112 f(self.0.get())
113 }
114
115 #[inline]
116 pub(crate) fn with_mut<R>(&self, f: impl FnOnce(*mut T) -> R) -> R {
117 f(self.0.get())
118 }
119 }
120 }
121 pub(crate) mod sync {
122 pub(crate) mod atomic {
123 pub(crate) use core::sync::atomic::{
124 compiler_fence, fence, AtomicPtr, AtomicUsize, Ordering,
125 };
126 }
127 #[cfg(feature = "alloc")]
128 pub(crate) use alloc::sync::Arc;
129 }
130
131 #[cfg(feature = "std")]
132 pub(crate) use std::thread_local;
133}
134
135#[cfg(all(feature = "alloc", target_has_atomic = "ptr"))]
136extern crate alloc;
137
138#[cfg(all(feature = "alloc", target_has_atomic = "ptr"))]
139mod atomic;
140#[cfg(all(feature = "alloc", target_has_atomic = "ptr"))]
141mod collector;
142#[cfg(all(feature = "alloc", target_has_atomic = "ptr"))]
143mod deferred;
144#[cfg(all(feature = "alloc", target_has_atomic = "ptr"))]
145mod epoch;
146#[cfg(all(feature = "alloc", target_has_atomic = "ptr"))]
147mod guard;
148#[cfg(all(feature = "alloc", target_has_atomic = "ptr"))]
149mod internal;
150#[cfg(all(feature = "alloc", target_has_atomic = "ptr"))]
151mod sync;
152
153#[cfg(all(feature = "alloc", target_has_atomic = "ptr"))]
154#[allow(deprecated)]
155pub use crate::atomic::{CompareAndSetError, CompareAndSetOrdering};
156#[cfg(all(feature = "alloc", target_has_atomic = "ptr"))]
157pub use crate::{
158 atomic::{Atomic, CompareExchangeError, Owned, Pointable, Pointer, Shared},
159 collector::{Collector, LocalHandle},
160 guard::{unprotected, Guard},
161};
162
163#[cfg(feature = "std")]
164mod default;
165#[cfg(feature = "std")]
166pub use crate::default::{default_collector, is_pinned, pin};
167