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 10 use crate::primitive::sync::atomic::AtomicUsize; 11 use 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)] 18 pub(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 23 impl Epoch { 24 /// Returns the starting epoch in unpinned state. 25 #[inline] starting() -> Self26 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. wrapping_sub(self, rhs: Self) -> isize34 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] is_pinned(self) -> bool43 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] pinned(self) -> Epoch49 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] unpinned(self) -> Epoch57 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] successor(self) -> Epoch67 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)] 76 pub(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 82 impl AtomicEpoch { 83 /// Creates a new atomic epoch. 84 #[inline] new(epoch: Epoch) -> Self85 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] load(&self, ord: Ordering) -> Epoch92 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] store(&self, epoch: Epoch, ord: Ordering)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] compare_exchange( &self, current: Epoch, new: Epoch, success: Ordering, failure: Ordering, ) -> Result<Epoch, Epoch>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 } 134