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
//! 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)] #![cfg_attr(not(feature = "std"), no_std)] #![cfg_attr(feature = "nightly", feature(cfg_target_has_atomic))] #![cfg_attr(feature = "nightly", feature(const_fn))] // matches! requires Rust 1.42 #![allow(clippy::match_like_matches_macro)] use cfg_if::cfg_if; #[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, CompareAndSetError, CompareAndSetOrdering, Owned, Pointer, Shared}; pub use self::collector::{Collector, LocalHandle}; pub use self::guard::{unprotected, Guard}; } } cfg_if! { if #[cfg(feature = "std")] { mod default; pub use self::default::{default_collector, is_pinned, pin}; } }