1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187
//! 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.
#![doc(test(
no_crate_inject,
attr(
deny(warnings, rust_2018_idioms),
allow(dead_code, unused_assignments, unused_variables)
)
))]
#![warn(
missing_docs,
missing_debug_implementations,
rust_2018_idioms,
unreachable_pub
)]
#![cfg_attr(not(feature = "std"), no_std)]
#![cfg_attr(feature = "nightly", feature(cfg_target_has_atomic))]
#![cfg_attr(feature = "nightly", feature(const_fn))]
#[cfg(crossbeam_loom)]
extern crate loom_crate as loom;
use cfg_if::cfg_if;
#[cfg(crossbeam_loom)]
#[allow(unused_imports, dead_code)]
mod primitive {
pub(crate) mod cell {
pub(crate) use loom::cell::UnsafeCell;
}
pub(crate) mod sync {
pub(crate) mod atomic {
use core::sync::atomic::Ordering;
pub(crate) use loom::sync::atomic::AtomicUsize;
pub(crate) fn fence(ord: Ordering) {
if let Ordering::Acquire = ord {
} else {
// FIXME: loom only supports acquire fences at the moment.
// https://github.com/tokio-rs/loom/issues/117
// let's at least not panic...
// this may generate some false positives (`SeqCst` is stronger than `Acquire`
// for example), and some false negatives (`Relaxed` is weaker than `Acquire`),
// but it's the best we can do for the time being.
}
loom::sync::atomic::fence(Ordering::Acquire)
}
// FIXME: loom does not support compiler_fence at the moment.
// https://github.com/tokio-rs/loom/issues/117
// we use fence as a stand-in for compiler_fence for the time being.
// this may miss some races since fence is stronger than compiler_fence,
// but it's the best we can do for the time being.
pub(crate) use self::fence as compiler_fence;
}
pub(crate) use loom::sync::Arc;
}
pub(crate) use loom::lazy_static;
pub(crate) use loom::thread_local;
}
#[cfg(not(crossbeam_loom))]
#[allow(unused_imports, dead_code)]
mod primitive {
#[cfg(any(feature = "alloc", feature = "std"))]
pub(crate) mod cell {
#[derive(Debug)]
#[repr(transparent)]
pub(crate) struct UnsafeCell<T>(::core::cell::UnsafeCell<T>);
// loom's UnsafeCell has a slightly different API than the standard library UnsafeCell.
// Since we want the rest of the code to be agnostic to whether it's running under loom or
// not, we write this small wrapper that provides the loom-supported API for the standard
// library UnsafeCell. This is also what the loom documentation recommends:
// https://github.com/tokio-rs/loom#handling-loom-api-differences
impl<T> UnsafeCell<T> {
#[inline]
pub(crate) fn new(data: T) -> UnsafeCell<T> {
UnsafeCell(::core::cell::UnsafeCell::new(data))
}
#[inline]
pub(crate) fn with<R>(&self, f: impl FnOnce(*const T) -> R) -> R {
f(self.0.get())
}
#[inline]
pub(crate) fn with_mut<R>(&self, f: impl FnOnce(*mut T) -> R) -> R {
f(self.0.get())
}
}
}
#[cfg(any(feature = "alloc", feature = "std"))]
pub(crate) mod sync {
pub(crate) mod atomic {
pub(crate) use core::sync::atomic::compiler_fence;
pub(crate) use core::sync::atomic::fence;
pub(crate) use core::sync::atomic::AtomicUsize;
}
#[cfg_attr(feature = "nightly", cfg(target_has_atomic = "ptr"))]
pub(crate) use alloc::sync::Arc;
}
#[cfg(feature = "std")]
pub(crate) use std::thread_local;
#[cfg(feature = "std")]
pub(crate) use lazy_static::lazy_static;
}
#[cfg_attr(feature = "nightly", cfg(target_has_atomic = "ptr"))]
cfg_if! {
if #[cfg(feature = "alloc")] {
extern crate alloc;
mod atomic;
mod collector;
mod deferred;
mod epoch;
mod guard;
mod internal;
mod sync;
pub use self::atomic::{
Pointable, Atomic, CompareExchangeError,
Owned, Pointer, Shared,
};
pub use self::collector::{Collector, LocalHandle};
pub use self::guard::{unprotected, Guard};
#[allow(deprecated)]
pub use self::atomic::{CompareAndSetError, CompareAndSetOrdering};
}
}
cfg_if! {
if #[cfg(feature = "std")] {
mod default;
pub use self::default::{default_collector, is_pinned, pin};
}
}