use std::sync::atomic::{AtomicU64, Ordering};
pub const LOCK_BIT: u64 = 0b01;
pub const OBSOLETE_BIT: u64 = 0b10;
pub const LOCKED_OR_OBSOLETE: u64 = LOCK_BIT | OBSOLETE_BIT;
pub const VERSION_STEP: u64 = 0b100;
#[derive(Copy, Clone, Debug, PartialEq, Eq)]
pub enum LockError {
Obsolete,
}
#[repr(transparent)]
#[derive(Debug)]
pub struct HybridLatch {
version: AtomicU64,
}
impl Default for HybridLatch {
#[inline]
fn default() -> Self {
Self::new()
}
}
impl HybridLatch {
#[inline]
pub const fn new() -> Self {
Self {
version: AtomicU64::new(0),
}
}
#[inline]
pub fn read_version(&self) -> Option<u64> {
let v = self.version.load(Ordering::Acquire);
if v & LOCKED_OR_OBSOLETE != 0 {
None
} else {
Some(v)
}
}
#[inline]
pub fn validate(&self, start_version: u64) -> bool {
std::sync::atomic::fence(Ordering::Acquire);
self.version.load(Ordering::Relaxed) == start_version
}
#[inline]
pub fn is_obsolete(&self) -> bool {
self.version.load(Ordering::Acquire) & OBSOLETE_BIT != 0
}
#[inline]
pub fn try_lock(&self) -> Result<u64, bool> {
let v = self.version.load(Ordering::Relaxed);
if v & OBSOLETE_BIT != 0 {
return Err(true);
}
if v & LOCK_BIT != 0 {
return Err(false);
}
match self.version.compare_exchange_weak(
v,
v | LOCK_BIT,
Ordering::Acquire,
Ordering::Relaxed,
) {
Ok(_) => Ok(v),
Err(_) => Err(false),
}
}
#[inline]
pub fn lock(&self) -> Result<u64, LockError> {
let mut backoff = SpinBackoff::new();
loop {
match self.try_lock() {
Ok(v) => return Ok(v),
Err(true) => return Err(LockError::Obsolete),
Err(false) => backoff.spin(),
}
}
}
#[inline]
pub fn unlock(&self) {
let current = self.version.load(Ordering::Relaxed);
debug_assert_ne!(current & LOCK_BIT, 0, "unlock called on un-locked latch");
let new_version = (current & !LOCK_BIT).wrapping_add(VERSION_STEP);
self.version.store(new_version, Ordering::Release);
}
#[inline]
pub fn mark_obsolete_and_unlock(&self) {
let current = self.version.load(Ordering::Relaxed);
debug_assert_ne!(
current & LOCK_BIT,
0,
"mark_obsolete called on un-locked latch"
);
let new_version = (current & !LOCK_BIT) | OBSOLETE_BIT;
self.version.store(new_version, Ordering::Release);
}
}
pub struct SpinBackoff {
step: u32,
}
impl Default for SpinBackoff {
fn default() -> Self {
Self::new()
}
}
impl SpinBackoff {
#[inline]
pub const fn new() -> Self {
Self { step: 0 }
}
#[inline]
pub fn spin(&mut self) {
if self.step <= 10 {
let spins = 1 << self.step.min(8);
for _ in 0..spins {
std::hint::spin_loop();
}
} else {
std::thread::yield_now();
}
if self.step < 16 {
self.step += 1;
}
}
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn test_latch_lifecycle() {
let latch = HybridLatch::new();
assert!(!latch.is_obsolete());
let v0 = latch.read_version().expect("should read initial version");
assert!(latch.validate(v0));
let v_lock = latch.lock().expect("should acquire lock");
assert_eq!(v_lock, v0);
assert!(
latch.read_version().is_none(),
"read_version must return None while locked"
);
assert!(!latch.validate(v0), "validation must fail while locked");
latch.unlock();
let v1 = latch.read_version().expect("should read updated version");
assert_eq!(v1, v0 + VERSION_STEP);
assert!(!latch.validate(v0));
assert!(latch.validate(v1));
let _ = latch.lock().expect("should acquire lock again");
latch.mark_obsolete_and_unlock();
assert!(latch.is_obsolete());
assert!(latch.read_version().is_none());
assert!(!latch.validate(v1));
assert_eq!(
latch.lock(),
Err(LockError::Obsolete),
"cannot lock obsolete node"
);
}
}