src/vendor/crossbeam-epoch/src/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 [`Garbage`], where they are
  40 //! 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 #![cfg_attr(feature = "nightly", feature(const_fn))]
  58 #![cfg_attr(feature = "nightly", feature(alloc))]
  59 #![cfg_attr(not(test), no_std)]
  60
  61 #[cfg(all(not(test), feature = "use_std"))]
  62 #[macro_use]
  63 extern crate std;
  64 #[cfg(test)]
  65 extern crate core;
  66
  67 // Use liballoc on nightly to avoid a dependency on libstd
  68 #[cfg(feature = "nightly")]
  69 extern crate alloc;
  70 #[cfg(not(feature = "nightly"))]
  71 mod alloc {
  72     // Tweak the module layout to match the one in liballoc
  73     extern crate std;
  74     pub use self::std::boxed;
  75     pub use self::std::sync as arc;
  76 }
  77
  78 #[cfg(feature = "manually_drop")]
  79 mod nodrop {
  80     pub use std::mem::ManuallyDrop as NoDrop;
  81 }
  82 #[cfg(not(feature = "manually_drop"))]
  83 extern crate nodrop;
  84
  85 extern crate arrayvec;
  86 extern crate crossbeam_utils;
  87 #[cfg(feature = "use_std")]
  88 #[macro_use]
  89 extern crate lazy_static;
  90 #[macro_use]
  91 extern crate memoffset;
  92 #[macro_use]
  93 extern crate scopeguard;
  94
  95 mod atomic;
  96 mod collector;
  97 #[cfg(feature = "use_std")]
  98 mod default;
  99 mod deferred;
 100 mod epoch;
 101 mod garbage;
 102 mod guard;
 103 mod internal;
 104 mod sync;
 105
 106 pub use self::atomic::{Atomic, CompareAndSetError, CompareAndSetOrdering, Owned, Shared};
 107 pub use self::guard::{unprotected, Guard};
 108 #[cfg(feature = "use_std")]
 109 pub use self::default::{default_handle, is_pinned, pin};
 110 pub use self::collector::{Collector, Handle};