crossbeam_epoch/
epoch.rs

1//! The global epoch
2//!
3//! The last bit in this number is unused and is always zero. Every so often the global epoch is
4//! incremented, i.e. we say it "advances". A pinned participant may advance the global epoch only
5//! if all currently pinned participants have been pinned in the current epoch.
6//!
7//! If an object became garbage in some epoch, then we can be sure that after two advancements no
8//! participant will hold a reference to it. That is the crux of safe memory reclamation.
9
10use crate::primitive::sync::atomic::Ordering;
11
12// Ideally, we want to always use AtomicU64, but since it is not available on all platforms,
13// we only use it when it is available for now.
14// TODO: On platforms where AtomicU64 is unavailable, we may want to use AtomicCell instead of
15// AtomicUsize. (https://github.com/crossbeam-rs/crossbeam/issues/433)
16#[cfg(target_has_atomic = "64")]
17type AtomicEpochRepr = crate::primitive::sync::atomic::AtomicU64;
18#[cfg(not(target_has_atomic = "64"))]
19type AtomicEpochRepr = crate::primitive::sync::atomic::AtomicUsize;
20#[cfg(target_has_atomic = "64")]
21type EpochRepr = u64;
22#[cfg(not(target_has_atomic = "64"))]
23type EpochRepr = usize;
24#[cfg(target_has_atomic = "64")]
25type EpochReprSigned = i64;
26#[cfg(not(target_has_atomic = "64"))]
27type EpochReprSigned = isize;
28
29/// An epoch that can be marked as pinned or unpinned.
30///
31/// Internally, the epoch is represented as an integer that wraps around at some unspecified point
32/// and a flag that represents whether it is pinned or unpinned.
33#[derive(Copy, Clone, Default, Debug, Eq, PartialEq)]
34pub(crate) struct Epoch {
35    /// The least significant bit is set if pinned. The rest of the bits hold the epoch.
36    data: EpochRepr,
37}
38
39impl Epoch {
40    /// Returns the starting epoch in unpinned state.
41    #[inline]
42    pub(crate) fn starting() -> Self {
43        Self::default()
44    }
45
46    /// Returns the number of epochs `self` is ahead of `rhs`.
47    ///
48    /// Internally, epochs are represented as numbers in the range `(isize::MIN / 2) .. (isize::MAX
49    /// / 2)`, so the returned distance will be in the same interval.
50    pub(crate) fn wrapping_sub(self, rhs: Self) -> EpochReprSigned {
51        // The result is the same with `(self.data & !1).wrapping_sub(rhs.data & !1) as isize >> 1`,
52        // because the possible difference of LSB in `(self.data & !1).wrapping_sub(rhs.data & !1)`
53        // will be ignored in the shift operation.
54        self.data.wrapping_sub(rhs.data & !1) as EpochReprSigned >> 1
55    }
56
57    /// Returns `true` if the epoch is marked as pinned.
58    #[inline]
59    pub(crate) fn is_pinned(self) -> bool {
60        (self.data & 1) == 1
61    }
62
63    /// Returns the same epoch, but marked as pinned.
64    #[inline]
65    pub(crate) fn pinned(self) -> Epoch {
66        Epoch {
67            data: self.data | 1,
68        }
69    }
70
71    /// Returns the same epoch, but marked as unpinned.
72    #[inline]
73    pub(crate) fn unpinned(self) -> Epoch {
74        Epoch {
75            data: self.data & !1,
76        }
77    }
78
79    /// Returns the successor epoch.
80    ///
81    /// The returned epoch will be marked as pinned only if the previous one was as well.
82    #[inline]
83    pub(crate) fn successor(self) -> Epoch {
84        Epoch {
85            data: self.data.wrapping_add(2),
86        }
87    }
88}
89
90/// An atomic value that holds an `Epoch`.
91#[derive(Default, Debug)]
92pub(crate) struct AtomicEpoch {
93    /// Since `Epoch` is just a wrapper around `usize`, an `AtomicEpoch` is similarly represented
94    /// using an `AtomicUsize`.
95    data: AtomicEpochRepr,
96}
97
98impl AtomicEpoch {
99    /// Creates a new atomic epoch.
100    #[inline]
101    pub(crate) fn new(epoch: Epoch) -> Self {
102        let data = AtomicEpochRepr::new(epoch.data);
103        Self { data }
104    }
105
106    /// Loads a value from the atomic epoch.
107    #[inline]
108    pub(crate) fn load(&self, ord: Ordering) -> Epoch {
109        Epoch {
110            data: self.data.load(ord),
111        }
112    }
113
114    /// Stores a value into the atomic epoch.
115    #[inline]
116    pub(crate) fn store(&self, epoch: Epoch, ord: Ordering) {
117        self.data.store(epoch.data, ord);
118    }
119
120    /// Stores a value into the atomic epoch if the current value is the same as `current`.
121    ///
122    /// The return value is a result indicating whether the new value was written and containing
123    /// the previous value. On success this value is guaranteed to be equal to `current`.
124    ///
125    /// This method takes two `Ordering` arguments to describe the memory
126    /// ordering of this operation. `success` describes the required ordering for the
127    /// read-modify-write operation that takes place if the comparison with `current` succeeds.
128    /// `failure` describes the required ordering for the load operation that takes place when
129    /// the comparison fails. Using `Acquire` as success ordering makes the store part
130    /// of this operation `Relaxed`, and using `Release` makes the successful load
131    /// `Relaxed`. The failure ordering can only be `SeqCst`, `Acquire` or `Relaxed`
132    /// and must be equivalent to or weaker than the success ordering.
133    #[inline]
134    pub(crate) fn compare_exchange(
135        &self,
136        current: Epoch,
137        new: Epoch,
138        success: Ordering,
139        failure: Ordering,
140    ) -> Result<Epoch, Epoch> {
141        match self
142            .data
143            .compare_exchange(current.data, new.data, success, failure)
144        {
145            Ok(data) => Ok(Epoch { data }),
146            Err(data) => Err(Epoch { data }),
147        }
148    }
149}
crossbeam_epoch/epoch.rs

crossbeam_epoch/
epoch.rs
