use std::sync::OnceLock;
#[cfg(loom)]
use loom::sync::{Mutex, MutexGuard};
#[cfg(not(loom))]
use std::sync::{Mutex, MutexGuard};
use store_io_buf::{CachePadded, WaitWord};
use store_io_core::error::{Error, ErrorContext, FirstCause, Op, OsError};
use crate::sync::{AtomicU64, Ordering, yield_now};
pub const MAX_FLUSH_SLOTS: usize = 4;
const WINDOW: u64 = 32;
#[cfg(not(loom))]
const YIELDS: u32 = 32;
#[cfg(loom)]
const YIELDS: u32 = 1;
const MISSES: u32 = 8;
const SKIPS: u32 = 256;
#[derive(Debug, Default)]
#[repr(align(128))]
struct Patience {
missed: core::sync::atomic::AtomicU32,
skip: core::sync::atomic::AtomicU32,
}
impl Patience {
fn try_yield(&self) -> bool {
use core::sync::atomic::Ordering::Relaxed;
let skip = self.skip.load(Relaxed);
if skip == 0 {
return true;
}
self.skip.store(skip - 1, Relaxed);
false
}
fn reached(&self) {
use core::sync::atomic::Ordering::Relaxed;
if self.missed.load(Relaxed) != 0 {
self.missed.store(0, Relaxed);
}
}
fn ran_out(&self) {
use core::sync::atomic::Ordering::Relaxed;
let missed = self.missed.load(Relaxed) + 1;
if missed >= MISSES {
self.missed.store(MISSES - 1, Relaxed);
self.skip.store(SKIPS, Relaxed);
} else {
self.missed.store(missed, Relaxed);
}
}
}
#[derive(Debug, Clone, Copy, Default, PartialEq, Eq)]
pub struct DomainStats {
pub flushes: u64,
pub joined: u64,
pub led: u64,
pub already_durable: u64,
pub peak_in_flight: u64,
pub out_of_order: u64,
}
#[cfg(not(any(test, loom)))]
const BUCKETS: usize = 64;
#[cfg(any(test, loom))]
const BUCKETS: usize = 2;
const _: () = assert!(BUCKETS <= 256);
#[derive(Debug, Default, Clone, Copy)]
struct Bucket {
waiting: u32,
need: u64,
}
#[derive(Debug, Clone, Copy)]
enum Bed {
Bucket(usize),
Designate,
Shared,
}
struct Wakes {
buckets: [u8; BUCKETS],
len: usize,
designate: bool,
shared: bool,
}
impl Wakes {
fn new() -> Self {
Self {
buckets: [0; BUCKETS],
len: 0,
designate: false,
shared: false,
}
}
fn send(self, d: &Domain) {
if self.designate {
d.designate_word.wake_all();
}
for &b in &self.buckets[..self.len] {
d.bucket_words[usize::from(b)].wake_all();
}
if self.shared {
d.shared_word.wake_all();
}
}
}
#[derive(Debug)]
#[repr(align(128))]
struct Counters {
joined: AtomicU64,
already_durable: AtomicU64,
}
#[derive(Debug)]
struct Slots {
busy: u32,
ahead: u64,
buckets: [Bucket; BUCKETS],
designate: Option<u64>,
shared: u32,
main_waiting: u32,
led: u64,
peak: u64,
out_of_order: u64,
}
#[derive(Debug)]
pub struct Domain {
issued: AtomicU64,
done: AtomicU64,
counters: Counters,
poison: OnceLock<FirstCause>,
slots: u32,
patience: Patience,
state: Mutex<Slots>,
bucket_words: Box<[CachePadded<WaitWord>]>,
designate_word: CachePadded<WaitWord>,
shared_word: CachePadded<WaitWord>,
}
impl Default for Domain {
fn default() -> Self {
Self::new()
}
}
impl Domain {
#[must_use]
pub fn new() -> Self {
Self::with_slots(1)
}
#[must_use]
pub fn with_slots(slots: usize) -> Self {
Self {
issued: AtomicU64::new(0),
done: AtomicU64::new(0),
counters: Counters {
joined: AtomicU64::new(0),
already_durable: AtomicU64::new(0),
},
poison: OnceLock::new(),
slots: slots.clamp(1, MAX_FLUSH_SLOTS) as u32,
patience: Patience::default(),
state: Mutex::new(Slots {
busy: 0,
ahead: 0,
buckets: [Bucket {
waiting: 0,
need: 0,
}; BUCKETS],
designate: None,
shared: 0,
main_waiting: 0,
led: 0,
peak: 0,
out_of_order: 0,
}),
bucket_words: (0..BUCKETS)
.map(|_| CachePadded::new(WaitWord::new()))
.collect(),
designate_word: CachePadded::new(WaitWord::new()),
shared_word: CachePadded::new(WaitWord::new()),
}
}
#[must_use]
pub fn slots(&self) -> usize {
self.slots as usize
}
#[must_use]
pub fn poisoned(&self) -> Option<FirstCause> {
self.poison.get().copied()
}
pub fn poison(&self, cause: FirstCause) {
let _first_cause_kept = self.poison.set(cause);
self.notify();
}
#[must_use]
pub fn stats(&self) -> DomainStats {
let st = self.lock();
DomainStats {
flushes: self.issued.load(Ordering::Acquire),
joined: self.counters.joined.load(Ordering::Relaxed),
led: st.led,
already_durable: self.counters.already_durable.load(Ordering::Relaxed),
peak_in_flight: st.peak,
out_of_order: st.out_of_order,
}
}
#[inline]
pub fn count_already_durable(&self) {
let _previous = self
.counters
.already_durable
.fetch_add(1, Ordering::Relaxed);
}
#[inline]
#[must_use]
pub fn ticket(&self) -> u64 {
self.issued.load(Ordering::SeqCst).wrapping_add(1)
}
pub(crate) fn join_if_done(&self, need: u64) -> bool {
let done = self.done.load(Ordering::SeqCst) >= need;
if done {
let _count = self.counters.joined.fetch_add(1, Ordering::Relaxed);
}
done
}
pub fn barrier(
&self,
need: u64,
flush: impl FnMut(usize, u64) -> Result<(), Option<OsError>>,
) -> Result<(), Error> {
self.barrier_in(need, self.slots, flush)
}
pub fn barrier_main(
&self,
need: u64,
mut flush: impl FnMut() -> Result<(), Option<OsError>>,
) -> Result<(), Error> {
self.barrier_in(need, 1, |_slot, _k| flush())
}
fn barrier_in(
&self,
need: u64,
usable: u32,
mut flush: impl FnMut(usize, u64) -> Result<(), Option<OsError>>,
) -> Result<(), Error> {
let mut led_flush = false;
let mut yielded_to = 0;
loop {
if self.done.load(Ordering::SeqCst) >= need {
if !led_flush {
let _count = self.counters.joined.fetch_add(1, Ordering::Relaxed);
}
return Ok(());
}
if let Some(first) = self.poison.get() {
return Err(Error::Poisoned { first: *first });
}
let mut st = self.lock();
let done = self.done.load(Ordering::SeqCst);
if done >= need || self.poison.get().is_some() {
continue;
}
let issued = self.issued.load(Ordering::SeqCst);
let mut free = (!st.busy) & ((1u32 << usable) - 1);
if st.main_waiting > 0 {
free &= !1;
}
if issued >= need || free == 0 || issued - done >= WINDOW {
let goal = need.min(issued);
if goal > yielded_to && self.patience.try_yield() {
yielded_to = goal;
drop(st);
self.yield_to(goal);
continue;
}
let narrow = need > issued && usable < self.slots;
let bed = Self::bed(&st, need, issued, narrow);
self.sleep(st, need, bed);
continue;
}
let slot = 31 - free.leading_zeros();
st.busy |= 1 << slot;
st.peak = st.peak.max(u64::from(st.busy.count_ones()));
st.led += 1;
let k = self.issued.fetch_add(1, Ordering::SeqCst).wrapping_add(1);
drop(st);
led_flush = true;
let unwinding = LeaderGuard { domain: self, slot };
let outcome = flush(slot as usize, k);
core::mem::forget(unwinding);
let mut st = self.lock();
st.busy &= !(1 << slot);
let failed = outcome.err();
let before = self.done.load(Ordering::SeqCst);
match failed {
None if self.poison.get().is_none() => self.record(&mut st, k),
None => {}
Some(raw) => {
let _first_cause_kept = self.poison.set(FirstCause {
op: Some(Op::FlushData),
raw,
});
}
}
let mut wakes = Wakes::new();
if self.poison.get().is_some() {
self.take_everyone(&mut st, &mut wakes);
} else {
self.take_covered(&mut st, before, &mut wakes);
self.take_designate(&mut st, &mut wakes);
self.take_shared(&mut st, &mut wakes);
}
drop(st);
wakes.send(self);
if let Some(raw) = failed {
return Err(Error::DurabilityUnknown {
op: Op::FlushData,
raw,
ctx: ErrorContext::default(),
});
}
}
}
fn yield_to(&self, goal: u64) {
let reached = || self.done.load(Ordering::SeqCst) >= goal || self.poison.get().is_some();
for _ in 0..YIELDS {
if reached() {
break;
}
yield_now();
}
if reached() {
self.patience.reached();
} else {
self.patience.ran_out();
}
}
fn record(&self, st: &mut Slots, k: u64) {
let mut done = self.done.load(Ordering::SeqCst);
if k > done + 1 {
st.out_of_order += 1;
}
st.ahead |= 1u64 << (k - done - 1);
while st.ahead & 1 == 1 {
st.ahead >>= 1;
done += 1;
}
self.done.store(done, Ordering::SeqCst);
}
pub fn exclusive_main<R>(&self, f: impl FnOnce() -> R) -> R {
let mut st = self.lock();
st.main_waiting += 1;
while st.busy & 1 == 1 {
self.sleep(st, 0, Bed::Shared);
st = self.lock();
}
st.main_waiting -= 1;
st.busy |= 1;
drop(st);
let _held = MainGuard { domain: self };
f()
}
#[cfg(test)]
pub(crate) fn hold_leadership(&self) -> bool {
let mut st = self.lock();
if st.busy != 0 {
return false;
}
st.busy = (1u32 << self.slots) - 1;
true
}
#[cfg(test)]
pub(crate) fn drop_leadership(&self) {
let mut st = self.lock();
st.busy = 0;
let mut wakes = Wakes::new();
self.take_everyone(&mut st, &mut wakes);
drop(st);
wakes.send(self);
}
#[cfg(test)]
pub(crate) fn waiting(&self) -> u32 {
let st = self.lock();
st.buckets.iter().map(|b| b.waiting).sum::<u32>()
+ u32::from(st.designate.is_some())
+ st.shared
}
fn poison_unknown_flush(&self, slot: u32) {
let _first_cause_kept = self.poison.set(FirstCause {
op: Some(Op::FlushData),
raw: None,
});
let mut st = self.lock();
st.busy &= !(1 << slot);
let mut wakes = Wakes::new();
self.take_everyone(&mut st, &mut wakes);
drop(st);
wakes.send(self);
}
fn bed(st: &Slots, need: u64, issued: u64, narrow: bool) -> Bed {
if narrow {
return Bed::Shared;
}
if need > issued && st.designate.is_none() {
return Bed::Designate;
}
let b = (need % BUCKETS as u64) as usize;
let bucket = st.buckets[b];
let covered_later = need <= issued || st.designate == Some(need);
if covered_later && (bucket.waiting == 0 || bucket.need == need) {
Bed::Bucket(b)
} else {
Bed::Shared
}
}
fn sleep(&self, mut st: MutexGuard<'_, Slots>, need: u64, bed: Bed) {
let word: &WaitWord = match bed {
Bed::Bucket(b) => {
st.buckets[b].need = need;
st.buckets[b].waiting += 1;
&self.bucket_words[b]
}
Bed::Designate => {
st.designate = Some(need);
&self.designate_word
}
Bed::Shared => {
st.shared += 1;
&self.shared_word
}
};
let seen = word.load();
drop(st);
while word.load() == seen {
word.wait(seen);
}
}
fn take_covered(&self, st: &mut Slots, before: u64, wakes: &mut Wakes) {
let after = self.done.load(Ordering::SeqCst);
for d in before + 1..=after.min(before + BUCKETS as u64) {
let b = (d % BUCKETS as u64) as usize;
let w = st.buckets[b];
if w.waiting > 0 && w.need > before && w.need <= after {
self.take_bucket(st, b, wakes);
}
}
}
fn take_bucket(&self, st: &mut Slots, b: usize, wakes: &mut Wakes) {
st.buckets[b].waiting = 0;
self.bucket_words[b].bump();
debug_assert!(wakes.len < wakes.buckets.len(), "wake list full");
if let Some(slot) = wakes.buckets.get_mut(wakes.len) {
*slot = b as u8;
wakes.len += 1;
}
}
fn take_designate(&self, st: &mut Slots, wakes: &mut Wakes) {
if st.designate.take().is_some() {
self.designate_word.bump();
wakes.designate = true;
}
}
fn take_shared(&self, st: &mut Slots, wakes: &mut Wakes) {
if st.shared > 0 {
st.shared = 0;
self.shared_word.bump();
wakes.shared = true;
}
}
fn take_everyone(&self, st: &mut Slots, wakes: &mut Wakes) {
for b in 0..BUCKETS {
if st.buckets[b].waiting > 0 {
self.take_bucket(st, b, wakes);
}
}
self.take_designate(st, wakes);
self.take_shared(st, wakes);
}
fn lock(&self) -> MutexGuard<'_, Slots> {
self.state
.lock()
.unwrap_or_else(std::sync::PoisonError::into_inner)
}
fn notify(&self) {
let mut st = self.lock();
let mut wakes = Wakes::new();
self.take_everyone(&mut st, &mut wakes);
drop(st);
wakes.send(self);
}
}
struct MainGuard<'a> {
domain: &'a Domain,
}
impl Drop for MainGuard<'_> {
fn drop(&mut self) {
let d = self.domain;
let mut st = d.lock();
st.busy &= !1;
let mut wakes = Wakes::new();
d.take_designate(&mut st, &mut wakes);
d.take_shared(&mut st, &mut wakes);
drop(st);
wakes.send(d);
}
}
struct LeaderGuard<'a> {
domain: &'a Domain,
slot: u32,
}
impl Drop for LeaderGuard<'_> {
fn drop(&mut self) {
self.domain.poison_unknown_flush(self.slot);
}
}
#[cfg(all(test, not(loom)))]
mod tests;
#[cfg(all(test, not(loom)))]
mod wake_tests;
#[cfg(all(test, loom))]
mod loom_tests {
use super::*;
use loom::sync::Arc;
use store_io_core::error::OsErrorSource;
fn model(slots: usize, f: impl Fn(Arc<Domain>) + Send + Sync + 'static) {
let f = std::sync::Arc::new(f);
for sleep in [false, true] {
let f = std::sync::Arc::clone(&f);
loom::model(move || {
let d = Domain::with_slots(slots);
if sleep {
d.patience
.skip
.store(u32::MAX, core::sync::atomic::Ordering::Relaxed);
}
f(Arc::new(d));
});
}
}
#[test]
fn loom_two_barriers_share_or_issue_and_poison_propagates() {
model(1, |d| {
let flushes = Arc::new(loom::sync::atomic::AtomicUsize::new(0));
let spawn = |fail: bool| {
let (d, flushes) = (d.clone(), flushes.clone());
loom::thread::spawn(move || {
let need = d.ticket();
let r = d.barrier(need, |_, _| {
let _n = flushes.fetch_add(1, loom::sync::atomic::Ordering::SeqCst);
if fail {
Err(Some(OsError {
code: 5,
source: OsErrorSource::Sim,
}))
} else {
Ok(())
}
});
(need, r.is_ok())
})
};
let a = spawn(false);
let b = spawn(true);
let (need_a, ok_a) = a.join().unwrap_or((0, false));
let (_need_b, _ok_b) = b.join().unwrap_or((0, false));
if ok_a {
assert!(d.done.load(Ordering::SeqCst) >= need_a);
}
assert!(flushes.load(loom::sync::atomic::Ordering::SeqCst) <= 2);
});
}
#[test]
fn loom_every_barrier_of_one_need_is_woken() {
model(1, |d| {
let need = d.ticket();
let spawn = || {
let d = d.clone();
loom::thread::spawn(move || d.barrier(need, |_, _| Ok(())).is_ok())
};
let all = [spawn(), spawn(), spawn()];
for t in all {
assert!(t.join().unwrap_or(false));
}
assert!(d.done.load(Ordering::SeqCst) >= need);
assert_eq!(d.waiting(), 0);
});
}
#[test]
fn loom_barriers_needing_the_next_flush_are_led_and_woken() {
model(1, |d| {
let spawn = || {
let d = d.clone();
loom::thread::spawn(move || {
let need = d.ticket();
(need, d.barrier(need, |_, _| Ok(())).is_ok())
})
};
let all = [spawn(), spawn(), spawn()];
for t in all {
let (need, ok) = t.join().unwrap_or((0, false));
assert!(ok);
assert!(d.done.load(Ordering::SeqCst) >= need);
}
assert_eq!(d.waiting(), 0);
});
}
#[test]
fn loom_a_full_flush_and_the_designate() {
model(1, |d| {
let spawn = || {
let d = d.clone();
loom::thread::spawn(move || {
let need = d.ticket();
(need, d.barrier(need, |_, _| Ok(())).is_ok())
})
};
let a = spawn();
let b = spawn();
d.exclusive_main(|| {});
for t in [a, b] {
let (need, ok) = t.join().unwrap_or((0, false));
assert!(ok);
assert!(d.done.load(Ordering::SeqCst) >= need);
}
assert_eq!(d.waiting(), 0);
});
}
#[test]
fn loom_narrow_and_wide_barriers_on_two_slots() {
model(2, |d| {
let main = {
let d = d.clone();
loom::thread::spawn(move || {
let need = d.ticket();
(need, d.barrier_main(need, || Ok(())).is_ok())
})
};
let wide = |d: &Arc<Domain>| {
let d = d.clone();
loom::thread::spawn(move || {
let need = d.ticket();
(need, d.barrier(need, |_, _| Ok(())).is_ok())
})
};
let a = wide(&d);
let b = wide(&d);
for t in [main, a, b] {
let (need, ok) = t.join().unwrap_or((0, false));
assert!(ok);
assert!(d.done.load(Ordering::SeqCst) >= need);
}
assert_eq!(d.waiting(), 0);
});
}
#[test]
fn loom_outside_poison_wakes_the_designate_and_the_bucket() {
model(1, |d| {
let spawn = || {
let d = d.clone();
loom::thread::spawn(move || {
let need = d.ticket();
(need, d.barrier(need, |_, _| Ok(())).is_ok())
})
};
let a = spawn();
let b = spawn();
d.poison(FirstCause {
op: None,
raw: None,
});
for t in [a, b] {
let (need, ok) = t.join().unwrap_or((0, false));
if ok {
assert!(d.done.load(Ordering::SeqCst) >= need);
}
}
assert_eq!(d.waiting(), 0);
});
}
#[test]
fn loom_two_slots_never_satisfy_past_a_failure() {
model(2, |d| {
let spawn = |fail: bool| {
let d = d.clone();
loom::thread::spawn(move || {
let need = d.ticket();
let r = d.barrier(need, |_, _| {
if fail {
Err(Some(OsError {
code: 5,
source: OsErrorSource::Sim,
}))
} else {
Ok(())
}
});
(need, r.is_ok())
})
};
let a = spawn(false);
let b = spawn(true);
let (need_a, ok_a) = a.join().unwrap_or((0, false));
let (_need_b, ok_b) = b.join().unwrap_or((0, true));
let done = d.done.load(Ordering::SeqCst);
if ok_a {
assert!(done >= need_a);
}
if ok_a && !ok_b {
assert_eq!(done, 1, "satisfied past a failed flush");
}
assert!(d.stats().flushes <= 2);
});
}
#[test]
fn loom_a_main_barrier_and_a_data_barrier() {
model(2, |d| {
let in_main = Arc::new(loom::sync::atomic::AtomicBool::new(false));
let main = {
let (d, in_main) = (d.clone(), in_main.clone());
loom::thread::spawn(move || {
let need = d.ticket();
let r = d.barrier_main(need, || {
in_main.store(true, loom::sync::atomic::Ordering::SeqCst);
in_main.store(false, loom::sync::atomic::Ordering::SeqCst);
Ok(())
});
(need, r.is_ok())
})
};
let data = {
let (d, in_main) = (d.clone(), in_main.clone());
loom::thread::spawn(move || {
let need = d.ticket();
let r = d.barrier(need, |slot, _| {
if slot == 0 {
assert!(!in_main.load(loom::sync::atomic::Ordering::SeqCst));
}
Ok(())
});
(need, r.is_ok())
})
};
let (need_m, ok_m) = main.join().unwrap_or((0, false));
let (need_d, ok_d) = data.join().unwrap_or((0, false));
assert!(ok_m && ok_d);
let done = d.done.load(Ordering::SeqCst);
assert!(done >= need_m && done >= need_d);
});
}
#[test]
fn loom_outside_poison_races_a_leader() {
model(2, |d| {
let leader = {
let d = d.clone();
loom::thread::spawn(move || {
let need = d.ticket();
(need, d.barrier(need, |_, _| Ok(())).is_ok())
})
};
let poisoner = {
let d = d.clone();
loom::thread::spawn(move || {
d.poison(FirstCause {
op: None,
raw: None,
});
})
};
let (need, ok) = leader.join().unwrap_or((0, false));
let _p = poisoner.join();
if ok {
assert!(d.done.load(Ordering::SeqCst) >= need);
}
assert!(d.poisoned().is_some());
});
}
}