diff options
author | Valentin Popov <valentin@popov.link> | 2024-07-19 15:37:58 +0300 |
---|---|---|
committer | Valentin Popov <valentin@popov.link> | 2024-07-19 15:37:58 +0300 |
commit | a990de90fe41456a23e58bd087d2f107d321f3a1 (patch) | |
tree | 15afc392522a9e85dc3332235e311b7d39352ea9 /vendor/crossbeam-utils/src/atomic/seq_lock_wide.rs | |
parent | 3d48cd3f81164bbfc1a755dc1d4a9a02f98c8ddd (diff) | |
download | fparkan-a990de90fe41456a23e58bd087d2f107d321f3a1.tar.xz fparkan-a990de90fe41456a23e58bd087d2f107d321f3a1.zip |
Deleted vendor folder
Diffstat (limited to 'vendor/crossbeam-utils/src/atomic/seq_lock_wide.rs')
-rw-r--r-- | vendor/crossbeam-utils/src/atomic/seq_lock_wide.rs | 155 |
1 files changed, 0 insertions, 155 deletions
diff --git a/vendor/crossbeam-utils/src/atomic/seq_lock_wide.rs b/vendor/crossbeam-utils/src/atomic/seq_lock_wide.rs deleted file mode 100644 index ef5d94a..0000000 --- a/vendor/crossbeam-utils/src/atomic/seq_lock_wide.rs +++ /dev/null @@ -1,155 +0,0 @@ -use core::mem; -use core::sync::atomic::{self, AtomicUsize, Ordering}; - -use crate::Backoff; - -/// A simple stamped lock. -/// -/// The state is represented as two `AtomicUsize`: `state_hi` for high bits and `state_lo` for low -/// bits. -pub(crate) struct SeqLock { - /// The high bits of the current state of the lock. - state_hi: AtomicUsize, - - /// The low bits of the current state of the lock. - /// - /// All bits except the least significant one hold the current stamp. When locked, the state_lo - /// equals 1 and doesn't contain a valid stamp. - state_lo: AtomicUsize, -} - -impl SeqLock { - pub(crate) const fn new() -> Self { - Self { - state_hi: AtomicUsize::new(0), - state_lo: AtomicUsize::new(0), - } - } - - /// If not locked, returns the current stamp. - /// - /// This method should be called before optimistic reads. - #[inline] - pub(crate) fn optimistic_read(&self) -> Option<(usize, usize)> { - // The acquire loads from `state_hi` and `state_lo` synchronize with the release stores in - // `SeqLockWriteGuard::drop`. - // - // As a consequence, we can make sure that (1) all writes within the era of `state_hi - 1` - // happens before now; and therefore, (2) if `state_lo` is even, all writes within the - // critical section of (`state_hi`, `state_lo`) happens before now. - let state_hi = self.state_hi.load(Ordering::Acquire); - let state_lo = self.state_lo.load(Ordering::Acquire); - if state_lo == 1 { - None - } else { - Some((state_hi, state_lo)) - } - } - - /// Returns `true` if the current stamp is equal to `stamp`. - /// - /// This method should be called after optimistic reads to check whether they are valid. The - /// argument `stamp` should correspond to the one returned by method `optimistic_read`. - #[inline] - pub(crate) fn validate_read(&self, stamp: (usize, usize)) -> bool { - // Thanks to the fence, if we're noticing any modification to the data at the critical - // section of `(a, b)`, then the critical section's write of 1 to state_lo should be - // visible. - atomic::fence(Ordering::Acquire); - - // So if `state_lo` coincides with `stamp.1`, then either (1) we're noticing no modification - // to the data after the critical section of `(stamp.0, stamp.1)`, or (2) `state_lo` wrapped - // around. - // - // If (2) is the case, the acquire ordering ensures we see the new value of `state_hi`. - let state_lo = self.state_lo.load(Ordering::Acquire); - - // If (2) is the case and `state_hi` coincides with `stamp.0`, then `state_hi` also wrapped - // around, which we give up to correctly validate the read. - let state_hi = self.state_hi.load(Ordering::Relaxed); - - // Except for the case that both `state_hi` and `state_lo` wrapped around, the following - // condition implies that we're noticing no modification to the data after the critical - // section of `(stamp.0, stamp.1)`. - (state_hi, state_lo) == stamp - } - - /// Grabs the lock for writing. - #[inline] - pub(crate) fn write(&'static self) -> SeqLockWriteGuard { - let backoff = Backoff::new(); - loop { - let previous = self.state_lo.swap(1, Ordering::Acquire); - - if previous != 1 { - // To synchronize with the acquire fence in `validate_read` via any modification to - // the data at the critical section of `(state_hi, previous)`. - atomic::fence(Ordering::Release); - - return SeqLockWriteGuard { - lock: self, - state_lo: previous, - }; - } - - backoff.snooze(); - } - } -} - -/// An RAII guard that releases the lock and increments the stamp when dropped. -pub(crate) struct SeqLockWriteGuard { - /// The parent lock. - lock: &'static SeqLock, - - /// The stamp before locking. - state_lo: usize, -} - -impl SeqLockWriteGuard { - /// Releases the lock without incrementing the stamp. - #[inline] - pub(crate) fn abort(self) { - self.lock.state_lo.store(self.state_lo, Ordering::Release); - mem::forget(self); - } -} - -impl Drop for SeqLockWriteGuard { - #[inline] - fn drop(&mut self) { - let state_lo = self.state_lo.wrapping_add(2); - - // Increase the high bits if the low bits wrap around. - // - // Release ordering for synchronizing with `optimistic_read`. - if state_lo == 0 { - let state_hi = self.lock.state_hi.load(Ordering::Relaxed); - self.lock - .state_hi - .store(state_hi.wrapping_add(1), Ordering::Release); - } - - // Release the lock and increment the stamp. - // - // Release ordering for synchronizing with `optimistic_read`. - self.lock.state_lo.store(state_lo, Ordering::Release); - } -} - -#[cfg(test)] -mod tests { - use super::SeqLock; - - #[test] - fn test_abort() { - static LK: SeqLock = SeqLock::new(); - let before = LK.optimistic_read().unwrap(); - { - let guard = LK.write(); - guard.abort(); - } - let after = LK.optimistic_read().unwrap(); - assert_eq!(before, after, "aborted write does not update the stamp"); - } -} |