crossbeam_epoch/
epoch.rs

Help
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::AtomicUsize;
11use core::sync::atomic::Ordering;
12
13/// An epoch that can be marked as pinned or unpinned.
14///
15/// Internally, the epoch is represented as an integer that wraps around at some unspecified point
16/// and a flag that represents whether it is pinned or unpinned.
17#[derive(Copy, Clone, Default, Debug, Eq, PartialEq)]
18pub(crate) struct Epoch {
19    /// The least significant bit is set if pinned. The rest of the bits hold the epoch.
20    data: usize,
21}
22
23impl Epoch {
24    /// Returns the starting epoch in unpinned state.
25    #[inline]
26    pub(crate) fn starting() -> Self {
27        Self::default()
28    }
29
30    /// Returns the number of epochs `self` is ahead of `rhs`.
31    ///
32    /// Internally, epochs are represented as numbers in the range `(isize::MIN / 2) .. (isize::MAX
33    /// / 2)`, so the returned distance will be in the same interval.
34    pub(crate) fn wrapping_sub(self, rhs: Self) -> isize {
35        // The result is the same with `(self.data & !1).wrapping_sub(rhs.data & !1) as isize >> 1`,
36        // because the possible difference of LSB in `(self.data & !1).wrapping_sub(rhs.data & !1)`
37        // will be ignored in the shift operation.
38        self.data.wrapping_sub(rhs.data & !1) as isize >> 1
39    }
40
41    /// Returns `true` if the epoch is marked as pinned.
42    #[inline]
43    pub(crate) fn is_pinned(self) -> bool {
44        (self.data & 1) == 1
45    }
46
47    /// Returns the same epoch, but marked as pinned.
48    #[inline]
49    pub(crate) fn pinned(self) -> Epoch {
50        Epoch {
51            data: self.data | 1,
52        }
53    }
54
55    /// Returns the same epoch, but marked as unpinned.
56    #[inline]
57    pub(crate) fn unpinned(self) -> Epoch {
58        Epoch {
59            data: self.data & !1,
60        }
61    }
62
63    /// Returns the successor epoch.
64    ///
65    /// The returned epoch will be marked as pinned only if the previous one was as well.
66    #[inline]
67    pub(crate) fn successor(self) -> Epoch {
68        Epoch {
69            data: self.data.wrapping_add(2),
70        }
71    }
72}
73
74/// An atomic value that holds an `Epoch`.
75#[derive(Default, Debug)]
76pub(crate) struct AtomicEpoch {
77    /// Since `Epoch` is just a wrapper around `usize`, an `AtomicEpoch` is similarly represented
78    /// using an `AtomicUsize`.
79    data: AtomicUsize,
80}
81
82impl AtomicEpoch {
83    /// Creates a new atomic epoch.
84    #[inline]
85    pub(crate) fn new(epoch: Epoch) -> Self {
86        let data = AtomicUsize::new(epoch.data);
87        AtomicEpoch { data }
88    }
89
90    /// Loads a value from the atomic epoch.
91    #[inline]
92    pub(crate) fn load(&self, ord: Ordering) -> Epoch {
93        Epoch {
94            data: self.data.load(ord),
95        }
96    }
97
98    /// Stores a value into the atomic epoch.
99    #[inline]
100    pub(crate) fn store(&self, epoch: Epoch, ord: Ordering) {
101        self.data.store(epoch.data, ord);
102    }
103
104    /// Stores a value into the atomic epoch if the current value is the same as `current`.
105    ///
106    /// The return value is a result indicating whether the new value was written and containing
107    /// the previous value. On success this value is guaranteed to be equal to `current`.
108    ///
109    /// This method takes two `Ordering` arguments to describe the memory
110    /// ordering of this operation. `success` describes the required ordering for the
111    /// read-modify-write operation that takes place if the comparison with `current` succeeds.
112    /// `failure` describes the required ordering for the load operation that takes place when
113    /// the comparison fails. Using `Acquire` as success ordering makes the store part
114    /// of this operation `Relaxed`, and using `Release` makes the successful load
115    /// `Relaxed`. The failure ordering can only be `SeqCst`, `Acquire` or `Relaxed`
116    /// and must be equivalent to or weaker than the success ordering.
117    #[inline]
118    pub(crate) fn compare_exchange(
119        &self,
120        current: Epoch,
121        new: Epoch,
122        success: Ordering,
123        failure: Ordering,
124    ) -> Result<Epoch, Epoch> {
125        match self
126            .data
127            .compare_exchange(current.data, new.data, success, failure)
128        {
129            Ok(data) => Ok(Epoch { data }),
130            Err(data) => Err(Epoch { data }),
131        }
132    }
133}
crossbeam_epoch/epoch.rs

crossbeam_epoch/
epoch.rs
