portable_atomic/imp/fallback/
seq_lock_wide.rs

1// SPDX-License-Identifier: Apache-2.0 OR MIT
2
3// Adapted from https://github.com/crossbeam-rs/crossbeam/blob/crossbeam-utils-0.8.21/crossbeam-utils/src/atomic/seq_lock_wide.rs.
4
5include!("seq_lock_common.rs");
6
7use crate::imp::core_atomic::AtomicU32;
8
9pub(super) type State = u32;
10
11/// A simple stamped lock.
12///
13/// The state is represented as two `AtomicU32`: `state_hi` for high bits and `state_lo` for low
14/// bits.
15pub(super) struct SeqLock {
16    /// The high bits of the current state of the lock.
17    state_hi: AtomicU32,
18
19    /// The low bits of the current state of the lock.
20    ///
21    /// All bits except the least significant one hold the current stamp. When locked, the state_lo
22    /// equals 1 and doesn't contain a valid stamp.
23    state: AtomicU32,
24}
25
26impl SeqLock {
27    #[inline]
28    pub(super) const fn new() -> Self {
29        Self { state_hi: AtomicU32::new(0), state: AtomicU32::new(0) }
30    }
31
32    /// If not locked, returns the current stamp.
33    ///
34    /// This method should be called before optimistic reads.
35    #[inline]
36    pub(super) fn optimistic_read(&self) -> Option<(State, State)> {
37        // The acquire loads from `state_hi` and `state_lo` synchronize with the release stores in
38        // `SeqLockWriteGuard::drop` and `SeqLockWriteGuard::abort`.
39        //
40        // As a consequence, we can make sure that (1) all writes within the era of `state_hi - 1`
41        // happens before now; and therefore, (2) if `state_lo` is even, all writes within the
42        // critical section of (`state_hi`, `state_lo`) happens before now.
43        let state_hi = self.state_hi.load(Ordering::Acquire);
44        let state_lo = self.state.load(Ordering::Acquire);
45        if state_lo == LOCKED { None } else { Some((state_hi, state_lo)) }
46    }
47
48    /// Returns `true` if the current stamp is equal to `stamp`.
49    ///
50    /// This method should be called after optimistic reads to check whether they are valid. The
51    /// argument `stamp` should correspond to the one returned by method `optimistic_read`.
52    #[inline]
53    pub(super) fn validate_read(&self, stamp: (State, State)) -> bool {
54        // Thanks to the fence, if we're noticing any modification to the data at the critical
55        // section of `(stamp.0, stamp.1)`, then the critical section's write of 1 to state_lo
56        // should be visible.
57        crate::fence(Ordering::Acquire);
58
59        // So if `state_lo` coincides with `stamp.1`, then either (1) we're noticing no modification
60        // to the data after the critical section of `(stamp.0, stamp.1)`, or (2) `state_lo` wrapped
61        // around.
62        //
63        // If (2) is the case, the acquire ordering ensures we see the new value of `state_hi`.
64        let state_lo = self.state.load(Ordering::Acquire);
65
66        // If (2) is the case and `state_hi` coincides with `stamp.0`, then `state_hi` also wrapped
67        // around, which we give up to correctly validate the read.
68        let state_hi = self.state_hi.load(Ordering::Relaxed);
69
70        // Except for the case that both `state_hi` and `state_lo` wrapped around, the following
71        // condition implies that we're noticing no modification to the data after the critical
72        // section of `(stamp.0, stamp.1)`.
73        (state_hi, state_lo) == stamp
74    }
75}
76
77impl SeqLockWriteGuard<'_> {
78    #[inline]
79    fn next_stamp(&self) -> State {
80        let state_lo = self.state.wrapping_add(2);
81
82        // Increase the high bits if the low bits wrap around.
83        //
84        // Release ordering for synchronizing with `optimistic_read`.
85        if state_lo == 0 {
86            let state_hi = self.lock.state_hi.load(Ordering::Relaxed);
87            self.lock.state_hi.store(state_hi.wrapping_add(1), Ordering::Release);
88        }
89
90        state_lo
91    }
92}
portable_atomic/imp/fallback/seq_lock_wide.rs

portable_atomic/imp/fallback/
seq_lock_wide.rs
