debra_common/
epoch.rs

1//! Type-safe epoch counters for tracking operations of threads.
2
3use core::fmt;
4use core::ops::{Add, Sub};
5use core::sync::atomic::{AtomicUsize, Ordering};
6
7////////////////////////////////////////////////////////////////////////////////////////////////////
8// Epoch
9////////////////////////////////////////////////////////////////////////////////////////////////////
10
11const EPOCH_INCREMENT: usize = 2;
12
13/// A monotonically increasing epoch counter with wrapping overflow behaviour.
14#[derive(Copy, Clone, Debug, Default, Eq, Ord, PartialEq, PartialOrd)]
15pub struct Epoch(usize);
16
17impl Epoch {
18    /// Creates a new [`Epoch`] starting at zero.
19    #[inline]
20    pub fn new() -> Self {
21        Self(0)
22    }
23
24    /// Returns the [`PossibleAge`] of the epoch relative to `global_epoch`.
25    ///
26    /// Since the global epoch is explicitly allowed to wrap around, it is not
27    /// possible to unambiguously determine the relative age of an epoch.
28    /// However, since epochs are monotonically increasing it is certain that
29    /// any previously observed epoch must be older of equal than the global
30    /// epoch.
31    /// Consequently, it is possible to determine if an epoch **could** be
32    /// within the critical range of two epochs, during which reclamation of
33    /// records **must** be avoided, and is in order to be conservative.
34    #[inline]
35    pub fn relative_age(self, global_epoch: Epoch) -> Result<PossibleAge, Undetermined> {
36        match global_epoch.0.wrapping_sub(self.0) {
37            0 => Ok(PossibleAge::SameEpoch),
38            2 => Ok(PossibleAge::OneEpoch),
39            4 => Ok(PossibleAge::TwoEpochs),
40            _ => Err(Undetermined),
41        }
42    }
43
44    #[inline]
45    pub(crate) fn with_epoch(epoch: usize) -> Self {
46        debug_assert_eq!(epoch % EPOCH_INCREMENT, 0);
47        Self(epoch)
48    }
49
50    #[inline]
51    pub(crate) fn into_inner(self) -> usize {
52        self.0
53    }
54}
55
56impl Add<usize> for Epoch {
57    type Output = Self;
58
59    #[inline]
60    fn add(self, rhs: usize) -> Self::Output {
61        Self(self.0.wrapping_add(rhs * EPOCH_INCREMENT))
62    }
63}
64
65impl Sub<usize> for Epoch {
66    type Output = Self;
67
68    #[inline]
69    fn sub(self, rhs: usize) -> Self::Output {
70        Self(self.0.wrapping_sub(rhs * EPOCH_INCREMENT))
71    }
72}
73
74impl fmt::Display for Epoch {
75    #[inline]
76    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
77        write!(f, "epoch {}", self.0 / EPOCH_INCREMENT)
78    }
79}
80
81////////////////////////////////////////////////////////////////////////////////////////////////////
82// AtomicEpoch
83////////////////////////////////////////////////////////////////////////////////////////////////////
84
85/// An atomic and concurrently accessible [`Epoch`].
86pub struct AtomicEpoch(AtomicUsize);
87
88impl AtomicEpoch {
89    /// Creates a new [`AtomicEpoch`] starting at zero.
90    #[inline]
91    pub const fn new() -> Self {
92        Self(AtomicUsize::new(0))
93    }
94
95    /// Loads the [`Epoch`] value.
96    ///
97    /// `load` takes an [`Ordering`][ordering] argument, which describes the
98    /// memory ordering of this operation.
99    ///
100    /// # Panics
101    ///
102    /// Panics if `order` is [`Release`][release] or [`AcqRel`][acq_rel].
103    ///
104    /// [ordering]: core::sync::atomic::Ordering
105    /// [release]: core::sync::atomic::Ordering::Release
106    /// [acq_rel]: core::sync::atomic::Ordering::AcqRel
107    #[inline]
108    pub fn load(&self, order: Ordering) -> Epoch {
109        Epoch(self.0.load(order))
110    }
111
112    /// Stores a value into the [`Epoch`] if the current value is equal to
113    /// `current`.
114    ///
115    /// The return value is always the previous value. If it is equal to
116    /// `current`, then the value was updated.
117    ///
118    /// `compare_and_swap` also takes an [`Ordering`][ordering] argument, which
119    /// describes the memory ordering of this operation.
120    /// Notice that even when using [`AcqRel`][acq_rel], the operation might
121    /// fail and hence just perform an `Acquire` load, but not have `Release`
122    /// semantics.
123    /// Using [`Acquire`][acquire] makes the store part of this operation
124    /// [`Relaxed`][relaxed], if it happens, and using [`Release`][release]
125    /// makes the load part [`Relaxed`][relaxed].
126    ///
127    /// [ordering]: core::sync::atomic::Ordering
128    /// [acquire]: core::sync::atomic::Ordering::Acquire
129    /// [acq_rel]: core::sync::atomic::Ordering::AcqRel
130    /// [relaxed]: core::sync::atomic::Ordering::Relaxed
131    /// [release]: core::sync::atomic::Ordering::Release
132    #[inline]
133    pub fn compare_and_swap(&self, current: Epoch, new: Epoch, order: Ordering) -> Epoch {
134        Epoch(self.0.compare_and_swap(current.0, new.0, order))
135    }
136}
137
138impl fmt::Debug for AtomicEpoch {
139    #[inline]
140    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
141        f.debug_struct("AtomicEpoch").field("epoch", &self.0.load(Ordering::SeqCst)).finish()
142    }
143}
144
145impl fmt::Display for AtomicEpoch {
146    #[inline]
147    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
148        write!(f, "epoch {}", self.0.load(Ordering::SeqCst) / EPOCH_INCREMENT)
149    }
150}
151
152////////////////////////////////////////////////////////////////////////////////////////////////////
153// PossibleAge
154////////////////////////////////////////////////////////////////////////////////////////////////////
155
156/// The possible age of an epoch in relation to global epoch within a two-epoch
157/// range.
158///
159/// See [`relative_age`][Epoch::relative_age] for more details.
160#[derive(Debug, Copy, Clone, Eq, Ord, PartialEq, PartialOrd)]
161pub enum PossibleAge {
162    /// Epoch *may* be the same as the global epoch.
163    SameEpoch,
164    /// Epoch *may* be one epoch older than the global epoch.
165    OneEpoch,
166    /// Epoch *may* be two epochs older than the global epoch.
167    TwoEpochs,
168}
169
170impl fmt::Display for PossibleAge {
171    #[inline]
172    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
173        match *self {
174            PossibleAge::SameEpoch => write!(f, "epoch could be the same"),
175            PossibleAge::OneEpoch => write!(f, "epoch could be one epoch old"),
176            PossibleAge::TwoEpochs => write!(f, "epoch could be two epochs old"),
177        }
178    }
179}
180
181////////////////////////////////////////////////////////////////////////////////////////////////////
182// Undetermined
183////////////////////////////////////////////////////////////////////////////////////////////////////
184
185/// A type indicating that the age of an [`Epoch`] can not be determined, but is
186/// definitely older than two epochs.
187#[derive(Debug, Default, Copy, Clone, Eq, Ord, PartialEq, PartialOrd)]
188pub struct Undetermined;
189
190impl fmt::Display for Undetermined {
191    #[inline]
192    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
193        write!(f, "epoch age is undetermined, but older than two epochs")
194    }
195}
196
197#[cfg(test)]
198mod tests {
199    use std::sync::atomic::Ordering::Relaxed;
200
201    use super::{AtomicEpoch, Epoch, PossibleAge};
202
203    #[test]
204    fn new_epoch() {
205        let zero = Epoch::new();
206        assert_eq!(zero.into_inner(), 0);
207        let ten = Epoch::with_epoch(20);
208        assert_eq!(ten.into_inner(), 20);
209        assert_eq!(zero + 10, ten);
210    }
211
212    #[cfg(debug_assertions)]
213    #[test]
214    #[should_panic]
215    fn illegal_epoch() {
216        let _epoch = Epoch::with_epoch(11);
217    }
218
219    #[test]
220    fn relative_age() {
221        let zero = Epoch::new();
222        assert_eq!(zero.relative_age(zero).unwrap(), PossibleAge::SameEpoch);
223        assert_eq!(zero.relative_age(zero + 1).unwrap(), PossibleAge::OneEpoch);
224        assert_eq!(zero.relative_age(zero + 2).unwrap(), PossibleAge::TwoEpochs);
225
226        let max = Epoch::with_epoch(std::usize::MAX - 1);
227        assert_eq!(max.relative_age(zero).unwrap(), PossibleAge::OneEpoch);
228        assert_eq!((max - 1).relative_age(zero).unwrap(), PossibleAge::TwoEpochs);
229    }
230
231    #[test]
232    fn atomic_epoch() {
233        let atomic_epoch = AtomicEpoch::new();
234        let epoch = atomic_epoch.load(Relaxed);
235        assert_eq!(epoch.into_inner(), 0);
236    }
237
238    #[test]
239    fn atomic_epoch_cas() {
240        let atomic_epoch = AtomicEpoch::new();
241        let epoch = atomic_epoch.load(Relaxed);
242        let prev = atomic_epoch.compare_and_swap(Epoch::new(), epoch + 1, Relaxed);
243
244        assert_eq!(prev, Epoch::new());
245        assert_eq!(atomic_epoch.load(Relaxed), Epoch::new() + 1);
246    }
247}
debra_common/epoch.rs

debra_common/
epoch.rs
