#![deny(unsafe_op_in_unsafe_fn, clippy::undocumented_unsafe_blocks)]
use crate::sync::atomic::{fence, AtomicU64, AtomicU8, Ordering};
#[cfg(loom)]
pub(crate) mod mutants {
use std::cell::Cell;
std::thread_local! {
pub(crate) static SKIP_W1_FENCE: Cell<bool> = const { Cell::new(false) };
pub(crate) static SKIP_R5_FENCE: Cell<bool> = const { Cell::new(false) };
pub(crate) static SKIP_R4_COUPLING: Cell<bool> = const { Cell::new(false) };
pub(crate) static CHAIN_POSITION_UNLATCHED: Cell<bool> = const { Cell::new(false) };
}
}
pub(crate) const LOCK_BIT: u64 = 0b01;
pub(crate) const OBSOLETE_BIT: u64 = 0b10;
pub(crate) const VERSION_STEP: u64 = 0b100;
#[repr(transparent)]
pub(crate) struct HybridLatch {
version: AtomicU64,
}
#[must_use = "dropping a WriteGuard immediately releases the latch"]
pub(crate) struct WriteGuard<'l> {
latch: &'l HybridLatch,
v: u64,
}
impl HybridLatch {
crate::sync::const_fn_unless_loom! {
#[inline]
pub(crate) fn new() -> Self {
Self {
version: AtomicU64::new(0),
}
}
}
#[inline]
pub(crate) fn read_version(&self) -> Option<u64> {
let v = self.version.load(Ordering::Acquire);
(v & (LOCK_BIT | OBSOLETE_BIT) == 0).then_some(v)
}
#[inline]
pub(crate) fn validate(&self, v: u64) -> bool {
#[cfg(loom)]
if mutants::SKIP_R5_FENCE.with(|m| m.get()) {
return self.version.load(Ordering::Relaxed) == v;
}
fence(Ordering::Acquire);
self.version.load(Ordering::Relaxed) == v
}
#[inline]
pub(crate) fn is_obsolete(&self) -> bool {
self.version.load(Ordering::Acquire) & OBSOLETE_BIT != 0
}
#[must_use = "binding the guard is what holds the latch"]
#[inline]
pub(crate) fn try_upgrade(&self, v: u64) -> Option<WriteGuard<'_>> {
if v & (LOCK_BIT | OBSOLETE_BIT) != 0 {
return None;
}
self.version
.compare_exchange(v, v | LOCK_BIT, Ordering::Acquire, Ordering::Relaxed)
.ok()?;
#[cfg(loom)]
if mutants::SKIP_W1_FENCE.with(|m| m.get()) {
return Some(WriteGuard { latch: self, v });
}
fence(Ordering::Release);
Some(WriteGuard { latch: self, v })
}
#[must_use = "binding the guard is what holds the latch"]
pub(crate) fn lock(&self) -> Option<WriteGuard<'_>> {
let mut backoff = SpinBackoff::new();
loop {
let v = self.version.load(Ordering::Relaxed);
if v & OBSOLETE_BIT != 0 {
return None;
}
if v & LOCK_BIT == 0 {
if let Some(w) = self.try_upgrade(v) {
return Some(w);
}
}
backoff.spin();
}
}
}
impl WriteGuard<'_> {
#[inline]
pub(crate) fn unlock(self) -> u64 {
let nv = self.v.wrapping_add(VERSION_STEP);
self.latch.version.store(nv, Ordering::Release);
std::mem::forget(self);
nv
}
#[inline]
pub(crate) fn mark_obsolete(self) {
self.latch
.version
.store(self.v | OBSOLETE_BIT, Ordering::Release);
std::mem::forget(self);
}
#[allow(dead_code)] #[inline]
pub(crate) fn latch(&self) -> &HybridLatch {
self.latch
}
#[inline]
pub(crate) fn holds(&self, latch: &HybridLatch) -> bool {
std::ptr::eq(self.latch, latch)
}
}
impl Drop for WriteGuard<'_> {
#[inline]
fn drop(&mut self) {
self.latch
.version
.store(self.v.wrapping_add(VERSION_STEP), Ordering::Release);
}
}
#[repr(transparent)]
pub(crate) struct ChainLock {
locked: AtomicU8,
}
#[must_use = "dropping a ChainGuard immediately releases the lock"]
pub(crate) struct ChainGuard<'l> {
lock: &'l ChainLock,
}
impl ChainLock {
crate::sync::const_fn_unless_loom! {
#[inline]
pub(crate) fn new() -> Self {
Self {
locked: AtomicU8::new(0),
}
}
}
#[must_use = "binding the guard is what holds the lock"]
#[inline]
pub(crate) fn lock(&self) -> ChainGuard<'_> {
let mut backoff = SpinBackoff::new();
loop {
if self
.locked
.compare_exchange_weak(0, 1, Ordering::Acquire, Ordering::Relaxed)
.is_ok()
{
return ChainGuard { lock: self };
}
while self.locked.load(Ordering::Relaxed) != 0 {
backoff.spin();
}
}
}
}
impl ChainGuard<'_> {
#[inline]
pub(crate) fn holds(&self, lock: &ChainLock) -> bool {
std::ptr::eq(self.lock, lock)
}
}
impl Drop for ChainGuard<'_> {
#[inline]
fn drop(&mut self) {
self.lock.locked.store(0, Ordering::Release);
}
}
pub(crate) struct AbortOnUnwind;
impl AbortOnUnwind {
#[inline]
pub(crate) fn defuse(self) {
std::mem::forget(self)
}
}
impl Drop for AbortOnUnwind {
#[cold]
fn drop(&mut self) {
eprintln!("artmap: panic inside a commit phase; aborting to avoid publishing a torn node");
std::process::abort()
}
}
pub(crate) struct SpinBackoff {
step: u32,
}
impl SpinBackoff {
#[inline]
pub(crate) const fn new() -> Self {
Self { step: 0 }
}
#[inline]
pub(crate) fn spin(&mut self) {
if cfg!(loom) || self.step > 6 {
crate::sync::yield_now();
} else {
for _ in 0..(1u32 << self.step) {
crate::sync::spin_loop();
}
}
if self.step < 16 {
self.step += 1;
}
}
}
#[cfg(all(test, not(loom)))]
mod tests {
use super::*;
fn fails(r: Option<WriteGuard<'_>>) -> bool {
r.is_none()
}
#[test]
fn latch_lifecycle() {
let latch = HybridLatch::new();
let v0 = latch.read_version().expect("initial version");
assert!(latch.validate(v0));
let w = latch.try_upgrade(v0).expect("upgrade");
assert!(w.holds(&latch));
assert!(
latch.read_version().is_none(),
"locked latch has no read version"
);
assert!(!latch.validate(v0), "validation fails while locked");
let v1 = w.unlock();
assert_eq!(v1, v0 + VERSION_STEP);
assert_eq!(latch.read_version(), Some(v1));
assert!(!latch.validate(v0));
assert!(fails(latch.try_upgrade(v0)), "stale version cannot upgrade");
let w = latch.lock().expect("lock");
w.mark_obsolete();
assert!(latch.is_obsolete());
assert!(latch.read_version().is_none());
assert!(fails(latch.lock()), "obsolete latch cannot be locked");
}
#[test]
fn upgrade_rejects_flagged_versions() {
let latch = HybridLatch::new();
assert!(fails(latch.try_upgrade(LOCK_BIT)));
assert!(fails(latch.try_upgrade(OBSOLETE_BIT)));
let w = latch.lock().unwrap();
assert!(fails(latch.try_upgrade(LOCK_BIT)));
drop(w);
}
#[test]
fn concurrent_mutual_exclusion() {
use std::cell::UnsafeCell;
use std::sync::{Arc, Barrier};
struct Shared {
latch: HybridLatch,
counter: UnsafeCell<usize>,
}
unsafe impl Sync for Shared {}
let threads = if cfg!(miri) { 3 } else { 16 };
let per = if cfg!(miri) { 50 } else { 20_000 };
let s = Arc::new(Shared {
latch: HybridLatch::new(),
counter: UnsafeCell::new(0),
});
let barrier = Arc::new(Barrier::new(threads));
let handles: Vec<_> = (0..threads)
.map(|_| {
let (s, barrier) = (Arc::clone(&s), Arc::clone(&barrier));
std::thread::spawn(move || {
barrier.wait();
for _ in 0..per {
let w = s.latch.lock().unwrap();
unsafe { *s.counter.get() += 1 };
drop(w);
}
})
})
.collect();
for h in handles {
h.join().unwrap();
}
assert_eq!(unsafe { *s.counter.get() }, threads * per);
assert!(s.latch.read_version().is_some());
}
#[test]
fn validation_fails_across_a_concurrent_write() {
use std::sync::atomic::AtomicBool;
use std::sync::Arc;
let latch = Arc::new(HybridLatch::new());
let running = Arc::new(AtomicBool::new(true));
let (l, r) = (Arc::clone(&latch), Arc::clone(&running));
let writer = std::thread::spawn(move || {
let mut n = 0;
while r.load(std::sync::atomic::Ordering::Relaxed) && n < 50_000 {
let w = l.lock().unwrap();
std::hint::spin_loop();
drop(w);
n += 1;
}
});
for _ in 0..if cfg!(miri) { 200 } else { 100_000 } {
if let Some(v) = latch.read_version() {
std::hint::spin_loop();
std::hint::black_box(latch.validate(v));
}
}
running.store(false, std::sync::atomic::Ordering::Relaxed);
writer.join().unwrap();
let v = latch.read_version().expect("no writer holds the latch");
assert!(latch.validate(v));
}
#[test]
fn obsolete_is_permanent() {
let latch = HybridLatch::new();
let v = latch.read_version().unwrap();
latch.lock().unwrap().mark_obsolete();
assert!(latch.is_obsolete());
assert!(fails(latch.lock()));
assert!(fails(latch.try_upgrade(v)));
assert!(latch.read_version().is_none());
assert!(!latch.validate(v));
}
#[test]
fn guard_drop_unlocks_on_unwind() {
let latch = HybridLatch::new();
let r = std::panic::catch_unwind(std::panic::AssertUnwindSafe(|| {
let _w = latch.lock().unwrap();
panic!("prepare phase panic");
}));
assert!(r.is_err());
assert!(
latch.read_version().is_some(),
"latch released by unwinding"
);
}
}