use core::sync::atomic::{AtomicU8, AtomicUsize, Ordering};
const UNSET: u8 = 0;
const SLEEPY: u8 = 1;
const SLEEPING: u8 = 2;
const SET: u8 = 3;
#[derive(Debug)]
pub struct CoreLatch {
state: AtomicU8,
}
impl Default for CoreLatch {
fn default() -> Self {
Self::new()
}
}
impl CoreLatch {
#[inline]
pub const fn new() -> Self {
Self {
state: AtomicU8::new(UNSET),
}
}
#[inline]
pub(crate) fn line(&self) -> *const u8 {
(&raw const self.state).cast::<u8>()
}
#[inline]
pub fn get_sleepy(&self) -> bool {
self.state
.compare_exchange(UNSET, SLEEPY, Ordering::SeqCst, Ordering::Relaxed)
.is_ok()
}
#[inline]
pub fn fall_asleep(&self) -> bool {
self.state
.compare_exchange(SLEEPY, SLEEPING, Ordering::SeqCst, Ordering::Relaxed)
.is_ok()
}
#[inline]
pub fn wake_up(&self) {
if !self.is_set() {
let _ = self.state.compare_exchange(
SLEEPING,
UNSET,
Ordering::SeqCst,
Ordering::Relaxed,
);
}
}
#[inline]
pub fn is_set(&self) -> bool {
self.state.load(Ordering::Acquire) == SET
}
#[inline]
pub(crate) unsafe fn set(this: *const Self) -> bool {
let old = unsafe { (*this).state.swap(SET, Ordering::AcqRel) };
old == SLEEPING
}
}
pub trait Latch {
unsafe fn set(this: *const Self);
}
impl Latch for CoreLatch {
#[inline]
unsafe fn set(this: *const Self) {
let _ = unsafe { CoreLatch::set(this) };
}
}
pub struct SpinLatch {
pub core: CoreLatch,
pub parker: std::sync::Arc<crate::sched::sleep::Parker>,
}
impl SpinLatch {
#[inline]
pub fn new(parker: std::sync::Arc<crate::sched::sleep::Parker>) -> Self {
Self {
core: CoreLatch::new(),
parker,
}
}
#[inline]
pub fn is_set(&self) -> bool {
self.core.is_set()
}
#[inline]
pub fn get_sleepy(&self) -> bool {
self.core.get_sleepy()
}
#[inline]
pub fn fall_asleep(&self) -> bool {
self.core.fall_asleep()
}
#[inline]
pub fn wake_up(&self) {
self.core.wake_up();
}
}
impl Latch for SpinLatch {
#[inline]
unsafe fn set(this: *const Self) {
let parker = unsafe { (*this).parker.clone() };
let was_sleeping = unsafe { CoreLatch::set(&(*this).core) };
if was_sleeping {
parker.unpark();
}
}
}
pub struct JoinLatch {
word: AtomicUsize,
}
const STATE_BITS: usize = 0b11;
impl JoinLatch {
#[inline]
pub fn new(parker: &crate::sched::sleep::Parker) -> Self {
let address = core::ptr::from_ref(parker) as usize;
debug_assert_eq!(address & STATE_BITS, 0, "a Parker is 64-byte aligned");
Self {
word: AtomicUsize::new(address | usize::from(UNSET)),
}
}
#[inline]
fn address(&self) -> usize {
self.word.load(Ordering::Relaxed) & !STATE_BITS
}
#[inline]
fn transition(&self, from: u8, to: u8) -> bool {
let address = self.address();
self.word
.compare_exchange(
address | usize::from(from),
address | usize::from(to),
Ordering::SeqCst,
Ordering::Relaxed,
)
.is_ok()
}
#[inline]
pub fn is_set(&self) -> bool {
self.word.load(Ordering::Acquire) & STATE_BITS == usize::from(SET)
}
#[inline]
pub fn get_sleepy(&self) -> bool {
self.transition(UNSET, SLEEPY)
}
#[inline]
pub fn fall_asleep(&self) -> bool {
self.transition(SLEEPY, SLEEPING)
}
#[inline]
pub fn wake_up(&self) {
if !self.is_set() {
self.transition(SLEEPING, UNSET);
}
}
#[inline]
pub fn parker(&self) -> &crate::sched::sleep::Parker {
unsafe { &*(self.address() as *const crate::sched::sleep::Parker) }
}
}
impl Latch for JoinLatch {
#[inline]
unsafe fn set(this: *const Self) {
let address = unsafe { (*this).address() };
let old = unsafe {
(*this)
.word
.swap(address | usize::from(SET), Ordering::AcqRel)
};
if old & STATE_BITS == usize::from(SLEEPING) {
unsafe { &*(address as *const crate::sched::sleep::Parker) }.unpark();
}
}
}
pub struct CountLatch {
count: std::sync::atomic::AtomicUsize,
core: CoreLatch,
parker: std::sync::Arc<crate::sched::sleep::Parker>,
}
impl CountLatch {
#[inline]
pub fn new(n: usize, parker: std::sync::Arc<crate::sched::sleep::Parker>) -> Self {
assert!(n > 0, "CountLatch requires at least 1 participant");
Self {
count: std::sync::atomic::AtomicUsize::new(n),
core: CoreLatch::new(),
parker,
}
}
#[inline]
pub fn is_set(&self) -> bool {
self.core.is_set()
}
#[inline]
pub fn get_sleepy(&self) -> bool {
self.core.get_sleepy()
}
#[inline]
pub fn fall_asleep(&self) -> bool {
self.core.fall_asleep()
}
#[inline]
pub fn wake_up(&self) {
self.core.wake_up();
}
#[inline]
pub fn outstanding(&self) -> usize {
self.count.load(std::sync::atomic::Ordering::Acquire)
}
}
impl Latch for CountLatch {
#[inline]
unsafe fn set(this: *const Self) {
let prior = unsafe {
(*this).count.fetch_sub(1, std::sync::atomic::Ordering::AcqRel)
};
debug_assert!(prior > 0, "CountLatch::set called more times than the construction count");
if prior > 1 {
return;
}
let parker = unsafe { (*this).parker.clone() };
let was_sleeping = unsafe { CoreLatch::set(&(*this).core) };
if was_sleeping {
parker.unpark();
}
}
}
pub struct LockLatch {
flag: std::sync::atomic::AtomicBool,
waiter: std::sync::OnceLock<std::thread::Thread>,
}
impl Default for LockLatch {
fn default() -> Self {
Self::new()
}
}
impl LockLatch {
#[inline]
pub fn new() -> Self {
Self {
flag: std::sync::atomic::AtomicBool::new(false),
waiter: std::sync::OnceLock::new(),
}
}
pub fn wait(&self) {
if locklatch_diagnose_enabled() {
notice!("[locklatch] wait enter tid={:?}", std::thread::current().id());
}
if self.flag.load(std::sync::atomic::Ordering::Acquire) {
if locklatch_diagnose_enabled() {
notice!("[locklatch] wait exit (fast) tid={:?}", std::thread::current().id());
}
return;
}
let our_handle = std::thread::current();
drop(self.waiter.set(our_handle));
if self.flag.load(std::sync::atomic::Ordering::Acquire) {
if locklatch_diagnose_enabled() {
notice!("[locklatch] wait exit (race) tid={:?}", std::thread::current().id());
}
return;
}
while !self.flag.load(std::sync::atomic::Ordering::Acquire) {
std::thread::park();
}
if locklatch_diagnose_enabled() {
notice!("[locklatch] wait exit tid={:?}", std::thread::current().id());
}
}
pub fn is_set(&self) -> bool {
self.flag.load(std::sync::atomic::Ordering::Acquire)
}
pub fn wait_spin_then_monitor(&self, spin_cycles: usize) {
let budget_cycles = crate::sched::par_iter::installed_dispatch_cost_ns()
.saturating_mul(crate::sched::par_iter::tsc_per_ns_16())
/ 16;
let use_monitor = crate::sched::levers::latch_monitor()
&& budget_cycles > 0
&& crate::sched::sleep::monitor_wait_available();
if !use_monitor {
for _ in 0..spin_cycles {
if self.is_set() {
return;
}
std::hint::spin_loop();
}
self.wait();
return;
}
let floor_start = crate::sched::sleep::cycles_now();
for _ in 0..MONITOR_SPIN_FLOOR {
if self.is_set() {
return;
}
std::hint::spin_loop();
}
let per_poll = crate::sched::sleep::cycles_now().saturating_sub(floor_start)
/ MONITOR_SPIN_FLOOR as u64;
if per_poll == 0 || per_poll > MAX_MEASURED_POLL_CYCLES {
for _ in MONITOR_SPIN_FLOOR..spin_cycles {
if self.is_set() {
return;
}
std::hint::spin_loop();
}
self.wait();
return;
}
let ladder_cycles =
(spin_cycles.saturating_sub(MONITOR_SPIN_FLOOR) as u64).saturating_mul(per_poll);
let line = (&raw const self.flag).cast::<u8>();
crate::sched::sleep::note_latch_monitor_wait(false);
let ladder_start = crate::sched::sleep::cycles_now();
loop {
if self.is_set() {
return;
}
let spent = crate::sched::sleep::cycles_now().saturating_sub(ladder_start);
let left = ladder_cycles.saturating_sub(spent);
if left == 0 {
break;
}
crate::sched::sleep::note_latch_monitor_arm();
let waited =
unsafe { crate::sched::sleep::monitor_wait_once(line, left, || self.is_set()) };
if !waited {
break;
}
}
self.wait();
}
}
pub(crate) const MONITOR_SPIN_FLOOR: usize = 512;
pub(crate) const MAX_MEASURED_POLL_CYCLES: u64 = 512;
fn locklatch_diagnose_enabled() -> bool {
static CACHE: std::sync::OnceLock<bool> = std::sync::OnceLock::new();
*CACHE.get_or_init(|| {
std::env::var("FLYNNEL_LOCKLATCH_DIAGNOSE")
.map(|v| v == "1" || v.eq_ignore_ascii_case("true"))
.unwrap_or(false)
})
}
impl Latch for LockLatch {
#[inline]
unsafe fn set(this: *const Self) {
let waiter_opt = unsafe { (*this).waiter.get().cloned() };
unsafe { (*this).flag.store(true, std::sync::atomic::Ordering::Release) };
if let Some(handle) = waiter_opt {
handle.unpark();
}
}
}
#[cfg(test)]
mod tests {
use super::*;
use std::sync::Arc;
use std::sync::atomic::AtomicUsize;
use std::thread;
use std::time::{Duration, Instant};
#[test]
fn new_latch_is_unset() {
let l = CoreLatch::new();
assert!(!l.is_set());
}
#[test]
fn set_marks_set() {
let l = CoreLatch::new();
unsafe { Latch::set(&l) };
assert!(l.is_set());
}
#[test]
fn spin_latch_wakes_parked_thread() {
use std::sync::mpsc;
let (tx, rx) = mpsc::channel::<Arc<SpinLatch>>();
let waiter = thread::spawn(move || {
let parker = Arc::new(crate::sched::sleep::Parker::new(0));
let latch = Arc::new(SpinLatch::new(parker));
tx.send(latch.clone()).unwrap();
assert!(latch.get_sleepy(), "fresh latch must accept get_sleepy");
assert!(!latch.is_set(), "no setter has run yet");
assert!(
latch.fall_asleep(),
"no setter raced us between get_sleepy and fall_asleep"
);
let _unparked: bool = latch.parker.park_until(|| latch.is_set());
latch.wake_up();
assert!(latch.is_set(), "must observe SET after wake");
});
let latch = rx.recv().expect("waiter must send latch");
thread::sleep(Duration::from_millis(50));
unsafe { Latch::set(&*latch) };
let t0 = Instant::now();
loop {
if waiter.is_finished() {
waiter.join().unwrap();
break;
}
if t0.elapsed() > Duration::from_secs(5) {
panic!("waiter did not wake within 5s after Latch::set");
}
thread::sleep(Duration::from_millis(10));
}
}
#[test]
fn join_latch_wakes_its_parked_owner() {
use std::sync::mpsc;
let (tx, rx) = mpsc::channel::<Arc<JoinLatch>>();
let waiter = thread::spawn(move || {
let parker: &'static crate::sched::sleep::Parker =
Box::leak(Box::new(crate::sched::sleep::Parker::with_strategy(
0,
crate::sched::sleep::WaitStrategy::StdPark,
)));
let latch = Arc::new(JoinLatch::new(parker));
tx.send(latch.clone()).unwrap();
while !latch.is_set() {
if latch.get_sleepy() && latch.fall_asleep() {
let _unparked: bool = latch.parker().park_until(|| latch.is_set());
}
latch.wake_up();
}
});
let latch = rx.recv().expect("waiter must send latch");
thread::sleep(Duration::from_millis(50));
unsafe { Latch::set(&*latch) };
let t0 = Instant::now();
loop {
if waiter.is_finished() {
waiter.join().unwrap();
break;
}
if t0.elapsed() > Duration::from_secs(5) {
panic!("owner did not wake within 5s after the JoinLatch was set");
}
thread::sleep(Duration::from_millis(10));
}
}
#[test]
fn join_latch_set_before_any_park_refuses_the_handshake() {
let parker = crate::sched::sleep::Parker::with_strategy(
0,
crate::sched::sleep::WaitStrategy::StdPark,
);
let latch = JoinLatch::new(&parker);
unsafe { Latch::set(&latch) };
assert!(latch.is_set());
assert!(
!latch.get_sleepy(),
"a set latch must not let its owner park"
);
}
#[test]
fn count_latch_only_sets_on_final_decrement() {
let parker = Arc::new(crate::sched::sleep::Parker::new(0));
let latch = CountLatch::new(3, parker);
assert_eq!(latch.outstanding(), 3);
assert!(!latch.is_set());
unsafe { Latch::set(&latch) };
assert_eq!(latch.outstanding(), 2);
assert!(!latch.is_set(), "must not set until final decrement");
unsafe { Latch::set(&latch) };
assert_eq!(latch.outstanding(), 1);
assert!(!latch.is_set(), "must not set until final decrement");
unsafe { Latch::set(&latch) };
assert_eq!(latch.outstanding(), 0);
assert!(latch.is_set(), "final decrement must transition to SET");
}
#[test]
fn count_latch_wakes_parked_thread_on_final_set() {
use std::sync::mpsc;
let (tx, rx) = mpsc::channel::<Arc<CountLatch>>();
let n = 4usize;
let waiter = thread::spawn(move || {
let parker = Arc::new(crate::sched::sleep::Parker::new(0));
let latch = Arc::new(CountLatch::new(n, parker));
tx.send(latch.clone()).unwrap();
assert!(latch.get_sleepy());
assert!(latch.fall_asleep());
let _unparked: bool = latch.parker.park_until(|| latch.is_set());
latch.wake_up();
assert!(latch.is_set(), "must observe SET after final decrement");
});
let latch = rx.recv().expect("waiter sent latch");
thread::sleep(Duration::from_millis(20));
let mut setters = Vec::new();
for _ in 0..n {
let l2 = latch.clone();
setters.push(thread::spawn(move || unsafe { Latch::set(&*l2) }));
}
for s in setters {
s.join().unwrap();
}
let t0 = Instant::now();
loop {
if waiter.is_finished() {
waiter.join().unwrap();
break;
}
if t0.elapsed() > Duration::from_secs(5) {
panic!("waiter did not wake within 5s after N decrements");
}
thread::sleep(Duration::from_millis(10));
}
}
#[test]
fn lock_latch_wakes_cross_thread_waiter() {
let latch = Arc::new(LockLatch::new());
assert!(!latch.is_set());
let l2 = latch.clone();
let setter = thread::spawn(move || {
thread::sleep(Duration::from_millis(30));
unsafe { Latch::set(&*l2) };
});
let t0 = Instant::now();
latch.wait();
let elapsed = t0.elapsed();
assert!(latch.is_set());
assert!(
elapsed >= Duration::from_millis(20),
"wait must have actually blocked (got {elapsed:?})"
);
assert!(
elapsed < Duration::from_secs(5),
"wait must wake within 5s (got {elapsed:?})"
);
setter.join().unwrap();
}
#[test]
fn lock_latch_wait_returns_immediately_when_already_set() {
let latch = LockLatch::new();
unsafe { Latch::set(&latch) };
let t0 = Instant::now();
latch.wait();
assert!(
t0.elapsed() < Duration::from_millis(50),
"wait on already-set latch must return immediately"
);
assert!(latch.is_set());
}
#[test]
fn spin_latch_already_set_does_not_park() {
let parker = Arc::new(crate::sched::sleep::Parker::new(0));
let latch = SpinLatch::new(parker);
unsafe { Latch::set(&latch) };
assert!(latch.is_set());
assert!(!latch.get_sleepy(), "get_sleepy must fail on already-set latch");
}
#[test]
fn get_sleepy_succeeds_then_fails_after_set() {
let l = CoreLatch::new();
assert!(l.get_sleepy(), "UNSET -> SLEEPY should succeed");
assert!(!l.get_sleepy(), "SLEEPY -> SLEEPY should fail");
unsafe { Latch::set(&l) };
assert!(!l.get_sleepy(), "SET -> SLEEPY should fail");
}
#[test]
fn fall_asleep_requires_sleepy_first() {
let l = CoreLatch::new();
assert!(!l.fall_asleep(), "UNSET -> SLEEPING must fail");
assert!(l.get_sleepy());
assert!(l.fall_asleep(), "SLEEPY -> SLEEPING should succeed");
assert!(!l.fall_asleep());
}
#[test]
fn set_returns_true_when_prior_was_sleeping() {
let l = CoreLatch::new();
assert!(l.get_sleepy());
assert!(l.fall_asleep());
let was_sleeping = unsafe { CoreLatch::set(&l) };
assert!(was_sleeping, "set must return true when prior was SLEEPING");
}
#[test]
fn set_returns_false_when_prior_was_unset() {
let l = CoreLatch::new();
let was_sleeping = unsafe { CoreLatch::set(&l) };
assert!(!was_sleeping, "set must return false when prior was UNSET");
}
#[test]
fn set_returns_false_when_prior_was_sleepy() {
let l = CoreLatch::new();
assert!(l.get_sleepy());
let was_sleeping = unsafe { CoreLatch::set(&l) };
assert!(!was_sleeping, "set must return false when prior was SLEEPY");
}
#[test]
fn wake_up_reverts_sleeping_to_unset() {
let l = CoreLatch::new();
assert!(l.get_sleepy());
assert!(l.fall_asleep());
l.wake_up();
assert!(!l.is_set());
assert!(l.get_sleepy());
}
#[test]
fn wake_up_after_set_is_noop() {
let l = CoreLatch::new();
assert!(l.get_sleepy());
assert!(l.fall_asleep());
unsafe { Latch::set(&l) };
l.wake_up();
assert!(l.is_set(), "set state must not be reverted by wake_up");
}
#[test]
fn concurrent_get_sleepy_serializes_to_one_winner() {
let l = Arc::new(CoreLatch::new());
let wins = Arc::new(AtomicUsize::new(0));
let mut handles = Vec::new();
for _ in 0..8 {
let l = Arc::clone(&l);
let wins = Arc::clone(&wins);
handles.push(thread::spawn(move || {
if l.get_sleepy() {
wins.fetch_add(1, Ordering::SeqCst);
}
}));
}
for h in handles {
h.join().unwrap();
}
assert_eq!(wins.load(Ordering::SeqCst), 1,
"exactly one thread should win the UNSET -> SLEEPY CAS");
}
#[test]
fn set_synchronizes_publisher_and_observer() {
let l = Arc::new(CoreLatch::new());
let payload: Arc<AtomicUsize> = Arc::new(AtomicUsize::new(0));
let l_pub = Arc::clone(&l);
let payload_pub = Arc::clone(&payload);
let pub_handle = thread::spawn(move || {
payload_pub.store(0xDEAD_BEEF, Ordering::Relaxed);
unsafe { Latch::set(&*l_pub) };
});
let l_obs = Arc::clone(&l);
let payload_obs = Arc::clone(&payload);
let obs_handle = thread::spawn(move || {
let deadline = Instant::now() + Duration::from_secs(2);
while !l_obs.is_set() {
if Instant::now() > deadline {
panic!("observer never saw set within 2s");
}
std::thread::yield_now();
}
payload_obs.load(Ordering::Relaxed)
});
pub_handle.join().unwrap();
let observed = obs_handle.join().unwrap();
assert_eq!(observed, 0xDEAD_BEEF,
"observer must see publisher's writes after is_set");
}
}