Debian Codegraph @

.cargo/vendor/crossbeam-utils/src/atomic/seq_lock_wide.rs

raw
1 use core::mem;
2 use core::sync::atomic::{self, AtomicUsize, Ordering};
3
4 use crate::Backoff;
5
6 /// A simple stamped lock.
7 ///
8 /// The state is represented as two `AtomicUsize`: `state_hi` for high bits and `state_lo` for low
9 /// bits.
10 pub(crate) struct SeqLock {
11 /// The high bits of the current state of the lock.
12 state_hi: AtomicUsize,
13
14 /// The low bits of the current state of the lock.
15 ///
16 /// All bits except the least significant one hold the current stamp. When locked, the state_lo
17 /// equals 1 and doesn't contain a valid stamp.
18 state_lo: AtomicUsize,
19 }
20
21 impl SeqLock {
22 pub(crate) const fn new() -> Self {
23 Self {
24 state_hi: AtomicUsize::new(0),
25 state_lo: AtomicUsize::new(0),
26 }
27 }
28
29 /// If not locked, returns the current stamp.
30 ///
31 /// This method should be called before optimistic reads.
32 #[inline]
33 pub(crate) fn optimistic_read(&self) -> Option<(usize, usize)> {
34 // The acquire loads from `state_hi` and `state_lo` synchronize with the release stores in
35 // `SeqLockWriteGuard::drop`.
36 //
37 // As a consequence, we can make sure that (1) all writes within the era of `state_hi - 1`
38 // happens before now; and therefore, (2) if `state_lo` is even, all writes within the
39 // critical section of (`state_hi`, `state_lo`) happens before now.
40 let state_hi = self.state_hi.load(Ordering::Acquire);
41 let state_lo = self.state_lo.load(Ordering::Acquire);
42 if state_lo == 1 {
43 None
44 } else {
45 Some((state_hi, state_lo))
46 }
47 }
48
49 /// Returns `true` if the current stamp is equal to `stamp`.
50 ///
51 /// This method should be called after optimistic reads to check whether they are valid. The
52 /// argument `stamp` should correspond to the one returned by method `optimistic_read`.
53 #[inline]
54 pub(crate) fn validate_read(&self, stamp: (usize, usize)) -> bool {
55 // Thanks to the fence, if we're noticing any modification to the data at the critical
56 // section of `(a, b)`, then the critical section's write of 1 to state_lo should be
57 // visible.
58 atomic::fence(Ordering::Acquire);
59
60 // So if `state_lo` coincides with `stamp.1`, then either (1) we're noticing no modification
61 // to the data after the critical section of `(stamp.0, stamp.1)`, or (2) `state_lo` wrapped
62 // around.
63 //
64 // If (2) is the case, the acquire ordering ensures we see the new value of `state_hi`.
65 let state_lo = self.state_lo.load(Ordering::Acquire);
66
67 // If (2) is the case and `state_hi` coincides with `stamp.0`, then `state_hi` also wrapped
68 // around, which we give up to correctly validate the read.
69 let state_hi = self.state_hi.load(Ordering::Relaxed);
70
71 // Except for the case that both `state_hi` and `state_lo` wrapped around, the following
72 // condition implies that we're noticing no modification to the data after the critical
73 // section of `(stamp.0, stamp.1)`.
74 (state_hi, state_lo) == stamp
75 }
76
77 /// Grabs the lock for writing.
78 #[inline]
79 pub(crate) fn write(&'static self) -> SeqLockWriteGuard {
80 let backoff = Backoff::new();
81 loop {
82 let previous = self.state_lo.swap(1, Ordering::Acquire);
83
84 if previous != 1 {
85 // To synchronize with the acquire fence in `validate_read` via any modification to
86 // the data at the critical section of `(state_hi, previous)`.
87 atomic::fence(Ordering::Release);
88
89 return SeqLockWriteGuard {
90 lock: self,
91 state_lo: previous,
92 };
93 }
94
95 backoff.snooze();
96 }
97 }
98 }
99
100 /// An RAII guard that releases the lock and increments the stamp when dropped.
101 pub(crate) struct SeqLockWriteGuard {
102 /// The parent lock.
103 lock: &'static SeqLock,
104
105 /// The stamp before locking.
106 state_lo: usize,
107 }
108
109 impl SeqLockWriteGuard {
110 /// Releases the lock without incrementing the stamp.
111 #[inline]
112 pub(crate) fn abort(self) {
113 self.lock.state_lo.store(self.state_lo, Ordering::Release);
114 mem::forget(self);
115 }
116 }
117
118 impl Drop for SeqLockWriteGuard {
119 #[inline]
120 fn drop(&mut self) {
121 let state_lo = self.state_lo.wrapping_add(2);
122
123 // Increase the high bits if the low bits wrap around.
124 //
125 // Release ordering for synchronizing with `optimistic_read`.
126 if state_lo == 0 {
127 let state_hi = self.lock.state_hi.load(Ordering::Relaxed);
128 self.lock
129 .state_hi
130 .store(state_hi.wrapping_add(1), Ordering::Release);
131 }
132
133 // Release the lock and increment the stamp.
134 //
135 // Release ordering for synchronizing with `optimistic_read`.
136 self.lock.state_lo.store(state_lo, Ordering::Release);
137 }
138 }
139
140 #[cfg(test)]
141 mod tests {
142 use super::SeqLock;
143
144 #[test]
145 fn test_abort() {
146 static LK: SeqLock = SeqLock::new();
147 let before = LK.optimistic_read().unwrap();
148 {
149 let guard = LK.write();
150 guard.abort();
151 }
152 let after = LK.optimistic_read().unwrap();
153 assert_eq!(before, after, "aborted write does not update the stamp");
154 }
155 }