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, 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)] 17 pub(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 22 impl Epoch { 23 /// Returns the starting epoch in unpinned state. 24 #[inline] starting() -> Self25 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. wrapping_sub(self, rhs: Self) -> isize33 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] is_pinned(self) -> bool42 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] pinned(self) -> Epoch48 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] unpinned(self) -> Epoch56 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] successor(self) -> Epoch66 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)] 75 pub(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 81 impl AtomicEpoch { 82 /// Creates a new atomic epoch. 83 #[inline] new(epoch: Epoch) -> Self84 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] load(&self, ord: Ordering) -> Epoch91 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] store(&self, epoch: Epoch, ord: Ordering)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] compare_exchange( &self, current: Epoch, new: Epoch, success: Ordering, failure: Ordering, ) -> Result<Epoch, Epoch>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