| 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] |
| 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)] |
| 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] |
| 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 |
} |