]>
Commit | Line | Data |
---|---|---|
2c00a5a8 XL |
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 core::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 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 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 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 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 fn pinned(self) -> Epoch { | |
49 | Epoch { data: self.data | 1 } | |
50 | } | |
51 | ||
52 | /// Returns the same epoch, but marked as unpinned. | |
53 | #[inline] | |
54 | pub fn unpinned(self) -> Epoch { | |
55 | Epoch { data: self.data & !1 } | |
56 | } | |
57 | ||
58 | /// Returns the successor epoch. | |
59 | /// | |
60 | /// The returned epoch will be marked as pinned only if the previous one was as well. | |
61 | #[inline] | |
62 | pub fn successor(self) -> Epoch { | |
63 | Epoch { data: self.data.wrapping_add(2) } | |
64 | } | |
65 | } | |
66 | ||
67 | /// An atomic value that holds an `Epoch`. | |
68 | #[derive(Default, Debug)] | |
69 | pub struct AtomicEpoch { | |
70 | /// Since `Epoch` is just a wrapper around `usize`, an `AtomicEpoch` is similarly represented | |
71 | /// using an `AtomicUsize`. | |
72 | data: AtomicUsize, | |
73 | } | |
74 | ||
75 | impl AtomicEpoch { | |
76 | /// Creates a new atomic epoch. | |
77 | #[inline] | |
78 | pub fn new(epoch: Epoch) -> Self { | |
79 | let data = AtomicUsize::new(epoch.data); | |
80 | AtomicEpoch { data: data } | |
81 | } | |
82 | ||
83 | /// Loads a value from the atomic epoch. | |
84 | #[inline] | |
85 | pub fn load(&self, ord: Ordering) -> Epoch { | |
86 | Epoch { data: self.data.load(ord) } | |
87 | } | |
88 | ||
89 | /// Stores a value into the atomic epoch. | |
90 | #[inline] | |
91 | pub fn store(&self, epoch: Epoch, ord: Ordering) { | |
92 | self.data.store(epoch.data, ord); | |
93 | } | |
94 | ||
95 | /// Stores a value into the atomic epoch if the current value is the same as `current`. | |
96 | /// | |
97 | /// The return value is always the previous value. If it is equal to `current`, then the value | |
98 | /// is updated. | |
99 | /// | |
100 | /// The `Ordering` argument describes the memory ordering of this operation. | |
101 | #[inline] | |
102 | pub fn compare_and_swap(&self, current: Epoch, new: Epoch, ord: Ordering) -> Epoch { | |
103 | let data = self.data.compare_and_swap(current.data, new.data, ord); | |
104 | Epoch { data: data } | |
105 | } | |
106 | } |