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