diff options
Diffstat (limited to 'third_party/rust/crossbeam-epoch/src/lib.rs')
| -rw-r--r-- | third_party/rust/crossbeam-epoch/src/lib.rs | 169 |
1 files changed, 169 insertions, 0 deletions
diff --git a/third_party/rust/crossbeam-epoch/src/lib.rs b/third_party/rust/crossbeam-epoch/src/lib.rs new file mode 100644 index 0000000000..b432c1f401 --- /dev/null +++ b/third_party/rust/crossbeam-epoch/src/lib.rs @@ -0,0 +1,169 @@ +//! 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(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::{fence, AtomicUsize}; + + // 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::thread_local; +} +#[cfg(not(crossbeam_no_atomic_cas))] +#[cfg(not(crossbeam_loom))] +#[allow(unused_imports, dead_code)] +mod primitive { + #[cfg(feature = "alloc")] + 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) const 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(feature = "alloc")] + 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; + } + pub(crate) use alloc::sync::Arc; + } + + #[cfg(feature = "std")] + pub(crate) use std::thread_local; +} + +#[cfg(not(crossbeam_no_atomic_cas))] +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}; + } +} |