Skip to main content

store_io_engine/domain/
mod.rs

1//! The flush domain: one per device (one per container file in the default
2//! layout). It decides when a barrier needs a new device flush and lets
3//! concurrent barriers share one, with no timer and no waiting for company.
4//!
5//! # The join rule
6//!
7//! A barrier covering writes `W` (all already completed) loads
8//! `e = issued` **after** the last write in `W` completed. Flush number
9//! `e + 1` is issued only after `issued` is incremented to `e + 1`, which the
10//! load preceded, so flush `e + 1` (and every later one) was issued after
11//! every write in `W` completed and covers them (a device flush persists
12//! every write that completed before it was submitted). The barrier
13//! therefore needs `done >= e + 1`, where `done` is the highest `k` such that
14//! flushes `1..=k` **all** succeeded.
15//!
16//! # Leader-inline flushing, on up to `slots` handles at once
17//!
18//! A barrier that needs a flush, finds none issued since its ticket, and
19//! finds a free **slot** becomes a **leader**: it takes the slot, increments
20//! `issued` (under the slot lock) *before* calling the flush, runs the flush
21//! on its own thread (no hand-off: measured at +7.7% p50 on Windows when
22//! handed to a dedicated thread), records the success, and wakes the
23//! **followers**. A follower that needed a later flush than the ones that
24//! finished loops and may lead the next one. A lone writer therefore pays
25//! exactly one flush; concurrent writers share flushes.
26//!
27//! With one slot (the default), at most one flush is in flight. With more
28//! (D-124), up to that many run at once, each on the slot's own file handle
29//! and queue (the caller maps a slot to them): flushes may then finish out of
30//! order, and `done` advances only over an unbroken run of successes, so a
31//! barrier is never satisfied while an earlier flush is unfinished or
32//! failed. Separate handles keep each flush's failure report its own (on
33//! Linux the write-back error sequence is per open file description: two
34//! flushes on one handle could see one failure between them, and the other
35//! report success). Slot 0 is the caller's main handle; a barrier that can
36//! only flush through it (metadata writes) leads on slot 0 alone, and any
37//! other flush of the main handle runs holding slot 0
38//! ([`Domain::exclusive_main`]). The platform must also persist, through a
39//! flush on any handle, the writes completed through every handle of the
40//! file (`Platform::flush_errors_per_handle`).
41//!
42//! # Waking (D-125, D-126)
43//!
44//! A barrier that must wait registers under the slot lock, then sleeps on a
45//! [`WaitWord`] without it, in one of three places:
46//! - the **bucket** of the flush it needs (`need % BUCKETS`) when a flush
47//!   covering it is in flight, or will be led by the designate; a bucket
48//!   holds the barriers of one need at a time;
49//! - as the **designate**, on a word of its own, when it needs the next
50//!   flush (the only one it may lead) and no barrier waits to lead it yet;
51//! - on the **shared** word otherwise: its bucket held another need (rare),
52//!   it may lead on fewer slots than the domain has (`barrier_main`), or it
53//!   is an `exclusive_main` caller waiting for slot 0.
54//!
55//! A leader whose flush finished, still under the lock, deregisters every
56//! bucket its flush covered, the designate (a slot is free) and the shared
57//! sleepers, and bumps their words; after releasing the lock it wakes each
58//! word with one call. The kernel wakes all of a bucket's barriers at once,
59//! and each returns on reading `done`, never re-taking the lock: on a
60//! virtual machine every wake is an interrupt to another processor, and a
61//! chain of wakes, each woken barrier re-taking the lock to wake the next,
62//! cost the last barrier one interrupt and one lock per barrier ahead of it
63//! (G15, D-125, D-126). The designate re-takes the lock and leads the next
64//! flush, or, if a new barrier led it first, sleeps in its bucket. Barriers
65//! needing a later flush are not woken by an earlier one. Poison, a failed
66//! flush and a panicked leader wake everyone; slot 0 freed by
67//! `exclusive_main` wakes the designate and the shared sleepers (no bucket
68//! sleeper waits for a slot: each waits for `done` or for the designate).
69//!
70//! A barrier that must wait first gives its processor up, at most
71//! `YIELDS` times for each `done` it waits for, reading `done` without
72//! the lock, and sleeps only if that was not enough. Where a flush is
73//! cheap, the sleep and the wake are the dearest part of a shared flush; and
74//! with more writers than processors the thread a waiter waits for is
75//! often queued behind it, so spinning keeps it out where yielding lets it
76//! run, without an interrupt to another processor. Measured over null_blk
77//! on CI (D-139): eight writers made 1.56-1.71x the durable writes they
78//! made sleeping, as many as eight writers each flushing its own, at 0.36
79//! sleeps a write against 1.3. A flush that outlasts the yields gains
80//! nothing, so `Patience` stops yielding after `MISSES` waits in a row
81//! that ran out, and tries again after `SKIPS` more. Yielding changes
82//! only how a barrier waits: it holds nothing, and then re-takes the lock
83//! and decides as it would have. A wait that knows how long its answer
84//! should take (a set barrier's caller, its own flush timed: `multi.rs`,
85//! D-155) yields past its `YIELDS` for that long, at most `BUDGET_MAX_NS`;
86//! 32 yields take 11 to 28 us, depending on the processor, and on one of
87//! CI's processors the answers of a set's other stores came later than
88//! that in 14 to 23 calls of 100.
89//!
90//! A sleeper reads its word under the lock when it registers, and a waker
91//! bumps it under the lock when it deregisters: so a waker's bump always
92//! follows the registration it ends, a sleeper registered later reads the
93//! bumped value, and a wake sent after the lock is released either finds the
94//! sleeper asleep or finds the word already moved. A sleeper leaves only
95//! when its word has moved, so a spurious return of the OS's wait changes
96//! nothing.
97//!
98//! # Poison
99//!
100//! The first failed flush poisons the domain forever: `done` never advances
101//! again, the leader gets the failure, and every waiting or later barrier gets
102//! [`Error::Poisoned`]. A barrier that was already satisfied before it
103//! observed the poison keeps its result. A flush is never retried.
104//!
105//! The poison is set in three places: [`Domain::poison`] and a leader's
106//! panic set it before taking the slot lock, a leader's failed flush under
107//! it; every leader reads it under the lock before issuing a flush, so none
108//! is issued once a poisoning has taken the lock. All three end in one function, which releases the lock,
109//! wakes the barriers asleep here, then wakes every registered
110//! `PoisonWaker` (a set barrier waiting for this domain's flush thread,
111//! `multi.rs`), copied under their own lock and woken after it is released.
112
113use std::sync::{Arc, OnceLock};
114
115#[cfg(loom)]
116use loom::sync::{Mutex, MutexGuard};
117#[cfg(not(loom))]
118use std::sync::{Mutex, MutexGuard};
119
120use store_io_buf::{CachePadded, WaitWord};
121use store_io_core::IoClass;
122use store_io_core::error::{Error, ErrorContext, FirstCause, Op, OsError};
123
124use crate::sync::{AtomicU64, Ordering, yield_now};
125
126/// The most flushes a domain runs at once.
127pub const MAX_FLUSH_SLOTS: usize = 4;
128
129/// Flushes issued past `done` (in flight, or finished and waiting for an
130/// earlier one) beyond which no new flush is issued: the successes kept
131/// above `done` fit a 64-bit mask.
132const WINDOW: u64 = 32;
133
134/// How many times a waiting barrier yields, for one goal, before it sleeps.
135#[cfg(not(loom))]
136const YIELDS: u32 = 32;
137#[cfg(loom)]
138const YIELDS: u32 = 1;
139
140/// Waits in a row that ran out of yields, after which waits stop yielding.
141const MISSES: u32 = 8;
142
143/// The longest a wait with a budget yields ([`Patience::yield_within`]):
144/// about ten thread wakes on a virtual machine, so a wait that outlasts it
145/// pays at most a tenth more for sleeping (D-155).
146const BUDGET_MAX_NS: u64 = 200_000;
147
148/// The most yields of a wait with a budget, whatever its clock says: a
149/// clock that does not move (the simulator's, between a test's advances)
150/// still ends the yields.
151#[cfg(not(loom))]
152const YIELDS_MAX: u32 = 4096;
153#[cfg(loom)]
154const YIELDS_MAX: u32 = 2;
155
156/// Waits that do not yield, after [`MISSES`] missed.
157const SKIPS: u32 = 256;
158
159/// Whether waiting barriers yield: learned from what yielding achieved, so
160/// a device whose flushes outlast the yields pays for one try in
161/// [`SKIPS`]. A hint, read and written without order: a race loses a count,
162/// and only ever changes whether a barrier yields before it sleeps. Plain
163/// atomics, not modelled under loom for the same reason.
164#[derive(Debug, Default)]
165#[repr(align(128))]
166pub(crate) struct Patience {
167    /// Waits in a row that ran out of yields.
168    missed: core::sync::atomic::AtomicU32,
169    /// Waits left that do not yield.
170    skip: core::sync::atomic::AtomicU32,
171}
172
173impl Patience {
174    /// Whether this wait should yield.
175    fn try_yield(&self) -> bool {
176        use core::sync::atomic::Ordering::Relaxed;
177        let skip = self.skip.load(Relaxed);
178        if skip == 0 {
179            return true;
180        }
181        self.skip.store(skip - 1, Relaxed);
182        false
183    }
184
185    /// The yields were enough. No write when there is nothing to forget:
186    /// every waiter passes here, and the line must not bounce between them.
187    fn reached(&self) {
188        use core::sync::atomic::Ordering::Relaxed;
189        if self.missed.load(Relaxed) != 0 {
190            self.missed.store(0, Relaxed);
191        }
192    }
193
194    /// The yields ran out. The next try after the skips is the only one: a
195    /// miss then skips again at once.
196    fn ran_out(&self) {
197        use core::sync::atomic::Ordering::Relaxed;
198        let missed = self.missed.load(Relaxed) + 1;
199        if missed >= MISSES {
200            self.missed.store(MISSES - 1, Relaxed);
201            self.skip.store(SKIPS, Relaxed);
202        } else {
203            self.missed.store(missed, Relaxed);
204        }
205    }
206
207    /// A wait about to sleep: if waits yield now, yields until `reached`,
208    /// at most [`YIELDS`] times, and notes whether that was enough. Returns
209    /// whether `reached` held (always false when waits skip yielding).
210    pub(crate) fn yield_until(&self, reached: impl Fn() -> bool) -> bool {
211        if !self.try_yield() {
212            return false;
213        }
214        self.yields(reached)
215    }
216
217    /// [`Self::yield_until`] for a wait whose goal should be reached within
218    /// `budget_ns` of `start` (D-155): past its [`YIELDS`] it yields on
219    /// until that has passed on `now` (at most [`BUDGET_MAX_NS`]; at most
220    /// [`YIELDS_MAX`] yields in all, whatever `now` says). A budget of 0
221    /// waits as [`Self::yield_until`], and reads no clock.
222    pub(crate) fn yield_within(
223        &self,
224        start: u64,
225        budget_ns: u64,
226        now: impl Fn() -> u64,
227        reached: impl Fn() -> bool,
228    ) -> bool {
229        if !self.try_yield() {
230            return false;
231        }
232        let budget = budget_ns.min(BUDGET_MAX_NS);
233        let mut n = 0u32;
234        while !reached() {
235            if n >= YIELDS {
236                if budget == 0 || n >= YIELDS_MAX {
237                    break;
238                }
239                if now().saturating_sub(start) >= budget {
240                    break;
241                }
242            }
243            yield_now();
244            n += 1;
245        }
246        self.note(reached())
247    }
248
249    /// Yields until `reached`, at most [`YIELDS`] times, and notes whether
250    /// that was enough.
251    fn yields(&self, reached: impl Fn() -> bool) -> bool {
252        for _ in 0..YIELDS {
253            if reached() {
254                break;
255            }
256            yield_now();
257        }
258        self.note(reached())
259    }
260
261    /// Notes whether a wait's yields were `enough`, and returns it.
262    fn note(&self, enough: bool) -> bool {
263        if enough {
264            self.reached();
265        } else {
266            self.ran_out();
267        }
268        enough
269    }
270}
271
272/// Woken when a domain is poisoned: a set barrier waiting on this domain's
273/// flush thread (`multi.rs`), so a store's poison ends the wait.
274pub(crate) trait PoisonWaker: Send + Sync {
275    /// The domain was poisoned. Called with no lock of the domain held.
276    fn poisoned(&self);
277}
278
279/// The registered poison wakers ([`Domain::on_poison`]).
280#[derive(Default)]
281struct PoisonWakers {
282    next: u64,
283    list: Vec<(u64, Arc<dyn PoisonWaker>)>,
284}
285
286impl core::fmt::Debug for PoisonWakers {
287    fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
288        f.debug_struct("PoisonWakers")
289            .field("registered", &self.list.len())
290            .finish()
291    }
292}
293
294/// Counters a domain exposes for observability.
295#[derive(Debug, Clone, Copy, Default, PartialEq, Eq)]
296pub struct DomainStats {
297    /// Flushes issued.
298    pub flushes: u64,
299    /// Barriers satisfied by a flush another barrier issued.
300    pub joined: u64,
301    /// Barriers that issued the flush themselves.
302    pub led: u64,
303    /// Receipts returned without a barrier because the target was already
304    /// durable (SIO-TYP-02: a barrier is never a silent no-op).
305    pub already_durable: u64,
306    /// The most flushes that were in flight at once (at most the domain's
307    /// slots, D-124).
308    pub peak_in_flight: u64,
309    /// Flushes that succeeded while an earlier one was still unfinished
310    /// (kept until it finished, D-124).
311    pub out_of_order: u64,
312}
313
314/// Wait buckets, one word each. Needs that can wait in a bucket lie in
315/// `(done, issued + 1]`, at most `WINDOW + 1` values, so with 64 a bucket
316/// rarely meets a second need; tests use 2, so it often does.
317#[cfg(not(any(test, loom)))]
318const BUCKETS: usize = 64;
319#[cfg(any(test, loom))]
320const BUCKETS: usize = 2;
321
322// Bucket indices are kept in a byte.
323const _: () = assert!(BUCKETS <= 256);
324
325/// The barriers registered in one bucket, all of one need.
326#[derive(Debug, Default, Clone, Copy)]
327struct Bucket {
328    /// Barriers registered here (until a waker deregisters them).
329    waiting: u32,
330    /// Their need, while `waiting > 0`.
331    need: u64,
332}
333
334/// Where a waiting barrier sleeps.
335#[derive(Debug, Clone, Copy)]
336enum Bed {
337    Bucket(usize),
338    Designate,
339    Shared,
340}
341
342/// Wakes decided (and their words bumped) under the slot lock, sent after
343/// it is released.
344struct Wakes {
345    /// Buckets to wake, each at most once.
346    buckets: [u8; BUCKETS],
347    len: usize,
348    designate: bool,
349    shared: bool,
350}
351
352impl Wakes {
353    fn new() -> Self {
354        Self {
355            buckets: [0; BUCKETS],
356            len: 0,
357            designate: false,
358            shared: false,
359        }
360    }
361
362    fn send(self, d: &Domain) {
363        // The designate first: the next flush waits for it, and waking a
364        // bucket of many barriers takes the kernel longest.
365        if self.designate {
366            d.designate_word.wake_all();
367        }
368        for &b in &self.buckets[..self.len] {
369            d.bucket_words[usize::from(b)].wake_all();
370        }
371        if self.shared {
372            d.shared_word.wake_all();
373        }
374    }
375}
376
377/// Observability counters counted without the slot lock, on a cache line of
378/// their own: incrementing them must not evict the line every barrier reads
379/// (`issued`, `done`). Those counted under the lock live in [`Slots`], on
380/// the line a leader holds anyway (no locked add, no line of its own, per
381/// flush).
382#[derive(Debug)]
383#[repr(align(128))]
384struct Counters {
385    joined: AtomicU64,
386    already_durable: AtomicU64,
387}
388
389/// What the slot lock guards. `done` changes only under it.
390#[derive(Debug)]
391struct Slots {
392    /// Bit `s`: slot `s` has a flush in flight.
393    busy: u32,
394    /// Bit `i`: flush `done + 1 + i` succeeded (waiting for an earlier one).
395    ahead: u64,
396    /// The wait buckets (`BUCKETS` of them).
397    buckets: [Bucket; BUCKETS],
398    /// The need of the barrier registered as the designate, if any.
399    designate: Option<u64>,
400    /// Sleepers registered on the shared word.
401    shared: u32,
402    /// Callers of `exclusive_main` waiting for slot 0: leaders leave it to
403    /// them, so a full flush waits at most for the flush running on slot 0
404    /// (and any full flush ahead of it).
405    main_waiting: u32,
406    /// Flushes led, the most in flight at once, and those that finished
407    /// before an earlier one (observability).
408    led: u64,
409    peak: u64,
410    out_of_order: u64,
411}
412
413/// A flush domain.
414#[derive(Debug)]
415pub struct Domain {
416    issued: AtomicU64,
417    done: AtomicU64,
418    counters: Counters,
419    poison: OnceLock<FirstCause>,
420    slots: u32,
421    patience: Patience,
422    state: Mutex<Slots>,
423    /// Woken after the poison is set ([`Self::wake_poisoned`]).
424    poison_wakers: Mutex<PoisonWakers>,
425    /// One per wait bucket, each on its own cache line.
426    bucket_words: Box<[CachePadded<WaitWord>]>,
427    designate_word: CachePadded<WaitWord>,
428    shared_word: CachePadded<WaitWord>,
429    /// The store's device group and its platform's clock (PLANNING R5.4):
430    /// every barrier's entry, leading or joining, marks the group's commits
431    /// active. `None` for a domain no store owns (tests, models).
432    activity: Option<Activity>,
433    /// Auto-tuning (V3f3): the entry of the earliest commit-class barrier
434    /// waiting for a flush not yet issued (`u64::MAX`: none), its `from`
435    /// when it has one (D-160). Set under
436    /// the lock by such a waiter, only while auto-tuning is on; taken (a
437    /// swap back to `u64::MAX`) by every leader as it issues, so the next
438    /// flush, the one that covers those waiters, is timed from the
439    /// earliest of them when a background barrier leads it.
440    earliest: AtomicU64,
441}
442
443/// What a barrier's entry stamps.
444struct Activity {
445    qos: Arc<crate::qos::Qos>,
446    clock: store_io_platform::Clock,
447    /// The background call the store belongs to (a store created at
448    /// `Background`: `copy_store`'s target): its barriers and its `dsync`
449    /// writes are that call's, never commits, and its metadata writes are
450    /// the call's pieces.
451    pace: Option<crate::pace::Pace>,
452}
453
454impl core::fmt::Debug for Activity {
455    fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
456        f.write_str("Activity")
457    }
458}
459
460impl Default for Domain {
461    fn default() -> Self {
462        Self::new()
463    }
464}
465
466impl Domain {
467    /// A fresh, healthy domain with one flush slot.
468    #[must_use]
469    pub fn new() -> Self {
470        Self::with_slots(1)
471    }
472
473    /// A fresh, healthy domain running up to `slots` flushes at once
474    /// (clamped to `1..=MAX_FLUSH_SLOTS`). The caller maps each slot to a
475    /// handle and queue of its own.
476    #[must_use]
477    pub fn with_slots(slots: usize) -> Self {
478        Self {
479            issued: AtomicU64::new(0),
480            done: AtomicU64::new(0),
481            counters: Counters {
482                joined: AtomicU64::new(0),
483                already_durable: AtomicU64::new(0),
484            },
485            poison: OnceLock::new(),
486            slots: slots.clamp(1, MAX_FLUSH_SLOTS) as u32,
487            patience: Patience::default(),
488            state: Mutex::new(Slots {
489                busy: 0,
490                ahead: 0,
491                buckets: [Bucket {
492                    waiting: 0,
493                    need: 0,
494                }; BUCKETS],
495                designate: None,
496                shared: 0,
497                main_waiting: 0,
498                led: 0,
499                peak: 0,
500                out_of_order: 0,
501            }),
502            poison_wakers: Mutex::new(PoisonWakers::default()),
503            bucket_words: (0..BUCKETS)
504                .map(|_| CachePadded::new(WaitWord::new()))
505                .collect(),
506            designate_word: CachePadded::new(WaitWord::new()),
507            shared_word: CachePadded::new(WaitWord::new()),
508            activity: None,
509            earliest: AtomicU64::new(u64::MAX),
510        }
511    }
512
513    /// The domain of a store in the device group `qos`, its barriers
514    /// stamping commit activity with `clock` (its platform's fine clock),
515    /// unless the store belongs to the background call `pace`.
516    pub(crate) fn with_activity(
517        mut self,
518        qos: Arc<crate::qos::Qos>,
519        clock: store_io_platform::Clock,
520        pace: Option<crate::pace::Pace>,
521    ) -> Self {
522        self.activity = Some(Activity { qos, clock, pace });
523        self
524    }
525
526    /// The background call the store belongs to, if any (see
527    /// [`Self::with_activity`]): its metadata and data writes are that
528    /// call's pieces, admitted by its device group (PLANNING R5.4).
529    pub(crate) fn pace(&self) -> Option<&crate::pace::Pace> {
530        self.activity.as_ref().and_then(|a| a.pace.as_ref())
531    }
532
533    /// A new background call on the store's device group (a caller's scan:
534    /// R5.4's class `Background`, an issuer record of its own); `None` for
535    /// a domain without activity (never paced).
536    pub(crate) fn new_pace(&self) -> Option<crate::pace::Pace> {
537        self.activity
538            .as_ref()
539            .map(|a| crate::pace::Pace::new(&a.qos, Arc::clone(&a.clock)))
540    }
541
542    /// Marks the store's device group's commits active (a commit-class
543    /// barrier's entry, or a commit-class `dsync` write on a power-safe
544    /// store, where no barrier flushes): one clock read, a relaxed load and
545    /// a compare; a store at most once a millisecond (R5.4). A background
546    /// call's store marks nothing: its every barrier and write is the
547    /// call's (so a copy's own metadata never marks its group active).
548    ///
549    /// Returns the clock it read (`None`: it read none), the entry of
550    /// auto-tuning's sample.
551    pub(crate) fn note_commit(&self) -> Option<u64> {
552        let a = self.activity.as_ref().filter(|a| a.pace.is_none())?;
553        let now = (a.clock)();
554        a.qos.commit(now);
555        Some(now)
556    }
557
558    /// Whether auto-tuning samples this store's commits: its device
559    /// group's auto-tuning is on, and the store is no background call's.
560    fn tuned(&self) -> bool {
561        self.activity
562            .as_ref()
563            .is_some_and(|a| a.pace.is_none() && a.qos.tuned())
564    }
565
566    /// The clock, for the entry of auto-tuning's sample (`None` unless
567    /// auto-tuning is on): a commit's arrival at the store's flush thread,
568    /// whose batch is timed from its earliest commit's arrival, or a
569    /// commit's entry before its write (`Store::write_entry`).
570    pub(crate) fn arrival(&self) -> Option<u64> {
571        self.activity
572            .as_ref()
573            .filter(|_| self.tuned())
574            .map(|a| (a.clock)())
575    }
576
577    /// Auto-tuning's sample of a commit that entered at `entry` and is done
578    /// now (a power-safe store's `dsync` write, where no barrier flushes):
579    /// one more clock read, only when auto-tuning is on.
580    pub(crate) fn sample_since(&self, entry: Option<u64>) {
581        if let (Some(at), Some(a)) = (entry, self.activity.as_ref()) {
582            if self.tuned() {
583                a.qos.sample((a.clock)().saturating_sub(at));
584            }
585        }
586    }
587
588    /// The flush slots: how many flushes run at once at most.
589    #[must_use]
590    pub fn slots(&self) -> usize {
591        self.slots as usize
592    }
593
594    /// The failure that poisoned the domain, if any.
595    #[must_use]
596    pub fn poisoned(&self) -> Option<FirstCause> {
597        self.poison.get().copied()
598    }
599
600    /// Poisons the domain (explicitly by a caller's watchdog, or after a
601    /// failed write). Wakes every follower and every poison waker.
602    /// Idempotent: the first cause wins.
603    pub fn poison(&self, cause: FirstCause) {
604        let _first_cause_kept = self.poison.set(cause);
605        let mut st = self.lock();
606        let mut wakes = Wakes::new();
607        self.take_everyone(&mut st, &mut wakes);
608        self.wake_poisoned(st, wakes);
609    }
610
611    /// Registers `w`, woken when the domain is poisoned after this call (a
612    /// poison before it wakes nobody: the caller reads the poison after
613    /// registering, and so sees it). Returns the key that
614    /// unregisters it ([`Self::forget_poison_waker`]). Must not be called
615    /// holding a lock `w.poisoned` takes.
616    pub(crate) fn on_poison(&self, w: Arc<dyn PoisonWaker>) -> u64 {
617        let mut all = lock_wakers(&self.poison_wakers);
618        all.next += 1;
619        let key = all.next;
620        all.list.push((key, w));
621        key
622    }
623
624    /// Unregisters the poison waker `key` (see [`Self::on_poison`]).
625    pub(crate) fn forget_poison_waker(&self, key: u64) {
626        lock_wakers(&self.poison_wakers)
627            .list
628            .retain(|(k, _)| *k != key);
629    }
630
631    /// The end of every poisoning: with the poison set under `st`, releases
632    /// the slot lock, wakes the sleepers `wakes` holds, then every poison
633    /// waker, copied under their lock and woken after it is released (a
634    /// waker's own lock is never taken under a domain lock, and a waker
635    /// being unregistered never waits on a wake in progress).
636    fn wake_poisoned(&self, st: MutexGuard<'_, Slots>, wakes: Wakes) {
637        drop(st);
638        wakes.send(self);
639        let wakers: Vec<Arc<dyn PoisonWaker>> = lock_wakers(&self.poison_wakers)
640            .list
641            .iter()
642            .map(|(_, w)| Arc::clone(w))
643            .collect();
644        for w in wakers {
645            w.poisoned();
646        }
647    }
648
649    /// Observability counters: a consistent snapshot, read under the slot
650    /// lock (briefly; every barrier takes it), so not for a hot loop.
651    #[must_use]
652    pub fn stats(&self) -> DomainStats {
653        let st = self.lock();
654        DomainStats {
655            flushes: self.issued.load(Ordering::Acquire),
656            joined: self.counters.joined.load(Ordering::Relaxed),
657            led: st.led,
658            already_durable: self.counters.already_durable.load(Ordering::Relaxed),
659            peak_in_flight: st.peak,
660            out_of_order: st.out_of_order,
661        }
662    }
663
664    /// Counts a receipt returned without a barrier because its target was
665    /// already durable.
666    #[inline]
667    pub fn count_already_durable(&self) {
668        let _previous = self
669            .counters
670            .already_durable
671            .fetch_add(1, Ordering::Relaxed);
672    }
673
674    /// The ticket a barrier needs, to be taken **after** every write it must
675    /// cover has completed (and its completion has been observed).
676    #[inline]
677    #[must_use]
678    pub fn ticket(&self) -> u64 {
679        self.issued.load(Ordering::SeqCst).wrapping_add(1)
680    }
681
682    /// Whether a flush `>= need` has already succeeded (a barrier for it
683    /// would return at once); counted as a joined barrier when it has.
684    pub(crate) fn join_if_done(&self, need: u64) -> bool {
685        let done = self.done.load(Ordering::SeqCst) >= need;
686        if done {
687            let _count = self.counters.joined.fetch_add(1, Ordering::Relaxed);
688        }
689        done
690    }
691
692    /// Blocks until flushes `1..=need` have all succeeded, leading a flush on
693    /// this thread, on any free slot, if none has been issued since `need`'s
694    /// ticket.
695    ///
696    /// `flush(slot, k)` performs flush number `k` through slot `slot`'s
697    /// handle and returns the raw outcome; it is called at most once per
698    /// call to `barrier`, and only by the leader.
699    ///
700    /// # Errors
701    ///
702    /// [`Error::DurabilityUnknown`] if this call led a flush that failed;
703    /// [`Error::Poisoned`] if the domain is poisoned.
704    pub fn barrier(
705        &self,
706        need: u64,
707        flush: impl FnMut(usize, u64) -> Result<(), Option<OsError>>,
708    ) -> Result<(), Error> {
709        self.barrier_in(need, self.slots, IoClass::Commit, None, flush)
710    }
711
712    /// [`Self::barrier`] for a caller of `class` (PLANNING R5.4): the
713    /// protocol is the same for every class (a background barrier joins a
714    /// flush in flight or the designate's next, else leads); only a
715    /// commit-class barrier's entry marks the device's commits active.
716    #[cfg(all(test, not(loom)))]
717    pub(crate) fn barrier_classed(
718        &self,
719        need: u64,
720        class: IoClass,
721        flush: impl FnMut(usize, u64) -> Result<(), Option<OsError>>,
722    ) -> Result<(), Error> {
723        self.barrier_in(need, self.slots, class, None, flush)
724    }
725
726    /// [`Self::barrier_classed`] timed, for auto-tuning, from `entry` (a
727    /// flush thread's batch's earliest commit's arrival, or a commit's
728    /// entry before its write: `Store::write_entry`) instead of this
729    /// call's entry.
730    pub(crate) fn barrier_classed_from(
731        &self,
732        need: u64,
733        class: IoClass,
734        entry: Option<u64>,
735        flush: impl FnMut(usize, u64) -> Result<(), Option<OsError>>,
736    ) -> Result<(), Error> {
737        self.barrier_in(need, self.slots, class, entry, flush)
738    }
739
740    /// As [`Self::barrier`], leading only on slot 0 (the caller's main
741    /// handle), for a caller that can flush through no other.
742    ///
743    /// # Errors
744    ///
745    /// As [`Self::barrier`].
746    pub fn barrier_main(
747        &self,
748        need: u64,
749        mut flush: impl FnMut() -> Result<(), Option<OsError>>,
750    ) -> Result<(), Error> {
751        self.barrier_in(need, 1, IoClass::Commit, None, |_slot, _k| flush())
752    }
753
754    fn barrier_in(
755        &self,
756        need: u64,
757        usable: u32,
758        class: IoClass,
759        from: Option<u64>,
760        mut flush: impl FnMut(usize, u64) -> Result<(), Option<OsError>>,
761    ) -> Result<(), Error> {
762        // A commit-class barrier's entry marks commits active, whether it
763        // leads or joins (so a commit joining a background-led flush counts);
764        // a background one's never does. Its clock read is auto-tuning's
765        // entry (or the flush thread's batch's, `from`).
766        let entry = if class.is_commit() {
767            self.note_commit().map(|now| from.unwrap_or(now))
768        } else {
769            None
770        };
771        let tuned = self.tuned();
772        let mut waiting_noted = false;
773        let mut led_flush = false;
774        // The highest `done` this call has yielded for: one goal, one try.
775        let mut yielded_to = 0;
776        loop {
777            // A woken barrier comes back here and, covered, returns without
778            // the lock.
779            if self.done.load(Ordering::SeqCst) >= need {
780                if !led_flush {
781                    let _count = self.counters.joined.fetch_add(1, Ordering::Relaxed);
782                }
783                return Ok(());
784            }
785            if let Some(first) = self.poison.get() {
786                return Err(Error::Poisoned { first: *first });
787            }
788            let mut st = self.lock();
789            // Re-checked under the lock: every change to `done`, `issued`
790            // and the slots happens under it, so nothing is missed between
791            // these checks and the registration.
792            let done = self.done.load(Ordering::SeqCst);
793            if done >= need || self.poison.get().is_some() {
794                continue;
795            }
796            let issued = self.issued.load(Ordering::SeqCst);
797            // A flush issued since the ticket covers `need`: wait for it
798            // (and every earlier one) to finish. Otherwise lead, given a
799            // free slot and room in the window.
800            let mut free = (!st.busy) & ((1u32 << usable) - 1);
801            // A full flush waiting for slot 0 has it next: every leader
802            // leaves it (none holds what that flush needs: it takes no lock).
803            if st.main_waiting > 0 {
804                free &= !1;
805            }
806            if issued >= need || free == 0 || issued - done >= WINDOW {
807                // A commit waiting for a flush not yet issued is covered by
808                // the next one (its ticket is that flush's number): its
809                // entry is that flush's sample's start if a background
810                // barrier leads it.
811                if let (true, Some(at), false) = (tuned, entry, waiting_noted) {
812                    if need > issued {
813                        let _was = self.earliest.fetch_min(at, Ordering::SeqCst);
814                        waiting_noted = true;
815                    }
816                }
817                // Covered: until `need` is done. Needing the next flush:
818                // until the one before it is, and it may lead.
819                let goal = need.min(issued);
820                if goal > yielded_to && self.patience.try_yield() {
821                    yielded_to = goal;
822                    drop(st);
823                    self.yield_to(goal);
824                    continue;
825                }
826                // A barrier that would lead but may use fewer slots than
827                // the domain has must not take the designate's wake.
828                let narrow = need > issued && usable < self.slots;
829                let bed = Self::bed(&st, need, issued, narrow);
830                // `sleep` releases the lock; the loop re-checks.
831                self.sleep(st, need, bed);
832                continue;
833            }
834            // The highest free slot: slot 0, the only one a main-handle
835            // flush can use, is taken by data leaders last.
836            let slot = 31 - free.leading_zeros();
837            st.busy |= 1 << slot;
838            st.peak = st.peak.max(u64::from(st.busy.count_ones()));
839            st.led += 1;
840            // k = issued + 1 >= need: issued only grows, and the ticket
841            // read need - 1 before this.
842            let k = self.issued.fetch_add(1, Ordering::SeqCst).wrapping_add(1);
843            // Every leader takes the waiters' entry as it issues, tuned or
844            // not (a word set while auto-tuning was on is never left for a
845            // later flush): they are this flush's, never a later one's.
846            let waited = if self.earliest.load(Ordering::SeqCst) == u64::MAX {
847                u64::MAX
848            } else {
849                self.earliest.swap(u64::MAX, Ordering::SeqCst)
850            };
851            drop(st);
852            led_flush = true;
853            // A flush that panics leaves the device's state unknown: the
854            // guard poisons the domain and frees the slot, so no later
855            // barrier waits for a leader that is gone.
856            let unwinding = LeaderGuard { domain: self, slot };
857            let outcome = flush(slot as usize, k);
858            core::mem::forget(unwinding);
859            // Auto-tuning's sample: from the earliest commit the flush
860            // covers, the leader's own entry or a waiter's (a commit that
861            // took a freed slot ahead of an earlier waiter is timed from
862            // that waiter: the queueing counts); a background leader with
863            // no commit waiting takes none.
864            if tuned && outcome.is_ok() {
865                let waited = (waited != u64::MAX).then_some(waited);
866                let start = match (entry, waited) {
867                    (Some(e), Some(w)) => Some(e.min(w)),
868                    (e, w) => e.or(w),
869                };
870                self.sample_since(start);
871            }
872            let mut st = self.lock();
873            st.busy &= !(1 << slot);
874            let failed = outcome.err();
875            let before = self.done.load(Ordering::SeqCst);
876            match failed {
877                None if self.poison.get().is_none() => self.record(&mut st, k),
878                None => {}
879                Some(raw) => {
880                    let _first_cause_kept = self.poison.set(FirstCause {
881                        op: Some(Op::FlushData),
882                        raw,
883                    });
884                }
885            }
886            let mut wakes = Wakes::new();
887            if self.poison.get().is_some() {
888                self.take_everyone(&mut st, &mut wakes);
889                self.wake_poisoned(st, wakes);
890            } else {
891                self.take_covered(&mut st, before, &mut wakes);
892                // A slot is free: the designate may lead on it, and the
893                // shared sleepers include those that wait for a slot.
894                self.take_designate(&mut st, &mut wakes);
895                self.take_shared(&mut st, &mut wakes);
896                drop(st);
897                wakes.send(self);
898            }
899            if let Some(raw) = failed {
900                return Err(Error::DurabilityUnknown {
901                    op: Op::FlushData,
902                    raw,
903                    ctx: ErrorContext::default(),
904                });
905            }
906        }
907    }
908
909    /// Yields until `done` reaches `goal` or the domain is poisoned, at
910    /// most [`YIELDS`] times, and notes whether that was enough.
911    fn yield_to(&self, goal: u64) {
912        let reached = || self.done.load(Ordering::SeqCst) >= goal || self.poison.get().is_some();
913        let _enough = self.patience.yields(reached);
914    }
915
916    /// Records flush `k`'s success and advances `done` over the unbroken
917    /// run of successes that follows it.
918    fn record(&self, st: &mut Slots, k: u64) {
919        let mut done = self.done.load(Ordering::SeqCst);
920        // k > done: flush k has not been counted, and done only covers
921        // finished flushes; k - done <= WINDOW by the issue rule.
922        if k > done + 1 {
923            st.out_of_order += 1;
924        }
925        st.ahead |= 1u64 << (k - done - 1);
926        while st.ahead & 1 == 1 {
927            st.ahead >>= 1;
928            done += 1;
929        }
930        self.done.store(done, Ordering::SeqCst);
931    }
932
933    /// Runs `f` holding slot 0, the main handle's (waiting until it is
934    /// free; leaders leave it to a waiting caller): for a flush of the
935    /// main handle outside a barrier (a full flush), which must not run
936    /// beside a data flush on the same handle. Records nothing; the caller
937    /// handles `f`'s outcome. Runs `f` even on a poisoned domain.
938    ///
939    /// Deadlock: while a caller waits here, every barrier that would lead on
940    /// slot 0 waits for it, so `f` must not block on anything a barrier's
941    /// caller may hold (a lock, a lane), and the caller must hold nothing a
942    /// slot-0 leader's flush needs.
943    pub fn exclusive_main<R>(&self, f: impl FnOnce() -> R) -> R {
944        let mut st = self.lock();
945        st.main_waiting += 1;
946        while st.busy & 1 == 1 {
947            // Woken with the shared sleepers whenever a slot is freed.
948            self.sleep(st, 0, Bed::Shared);
949            st = self.lock();
950        }
951        st.main_waiting -= 1;
952        st.busy |= 1;
953        drop(st);
954        // Slot 0 is given back however `f` ends, a panic included.
955        let _held = MainGuard { domain: self };
956        f()
957    }
958
959    /// Takes every flush slot, as leaders flushing would (tests: every
960    /// barrier that needs a flush then waits until [`Self::drop_leadership`]).
961    #[cfg(test)]
962    pub(crate) fn hold_leadership(&self) -> bool {
963        let mut st = self.lock();
964        if st.busy != 0 {
965            return false;
966        }
967        st.busy = (1u32 << self.slots) - 1;
968        true
969    }
970
971    /// Gives back the slots taken by [`Self::hold_leadership`].
972    #[cfg(test)]
973    pub(crate) fn drop_leadership(&self) {
974        let mut st = self.lock();
975        st.busy = 0;
976        let mut wakes = Wakes::new();
977        self.take_everyone(&mut st, &mut wakes);
978        drop(st);
979        wakes.send(self);
980    }
981
982    /// Barriers and `exclusive_main` callers registered asleep (tests).
983    #[cfg(test)]
984    pub(crate) fn waiting(&self) -> u32 {
985        let st = self.lock();
986        st.buckets.iter().map(|b| b.waiting).sum::<u32>()
987            + u32::from(st.designate.is_some())
988            + st.shared
989    }
990
991    /// Poisons the domain (a flush whose outcome is unknown), frees its slot
992    /// and wakes every waiter.
993    fn poison_unknown_flush(&self, slot: u32) {
994        let _first_cause_kept = self.poison.set(FirstCause {
995            op: Some(Op::FlushData),
996            raw: None,
997        });
998        let mut st = self.lock();
999        st.busy &= !(1 << slot);
1000        let mut wakes = Wakes::new();
1001        self.take_everyone(&mut st, &mut wakes);
1002        self.wake_poisoned(st, wakes);
1003    }
1004
1005    /// Where a barrier for `need` that must wait sleeps (see the module
1006    /// documentation): `issued` and the registrations as read under the
1007    /// lock.
1008    fn bed(st: &Slots, need: u64, issued: u64, narrow: bool) -> Bed {
1009        if narrow {
1010            return Bed::Shared;
1011        }
1012        // Needs the next flush and nobody waits to lead it: this barrier will.
1013        if need > issued && st.designate.is_none() {
1014            return Bed::Designate;
1015        }
1016        // Covered by a flush in flight, or by the one the designate will
1017        // lead: in its bucket, unless the bucket holds another need.
1018        let b = (need % BUCKETS as u64) as usize;
1019        let bucket = st.buckets[b];
1020        let covered_later = need <= issued || st.designate == Some(need);
1021        if covered_later && (bucket.waiting == 0 || bucket.need == need) {
1022            Bed::Bucket(b)
1023        } else {
1024            Bed::Shared
1025        }
1026    }
1027
1028    /// Registers in `bed`, reading its word, releases the lock and sleeps
1029    /// until a waker has deregistered this sleeper (the word moved). The
1030    /// caller re-checks; a woken barrier re-takes the lock only if it is
1031    /// not yet satisfied.
1032    fn sleep(&self, mut st: MutexGuard<'_, Slots>, need: u64, bed: Bed) {
1033        let word: &WaitWord = match bed {
1034            Bed::Bucket(b) => {
1035                st.buckets[b].need = need;
1036                st.buckets[b].waiting += 1;
1037                &self.bucket_words[b]
1038            }
1039            Bed::Designate => {
1040                st.designate = Some(need);
1041                &self.designate_word
1042            }
1043            Bed::Shared => {
1044                st.shared += 1;
1045                &self.shared_word
1046            }
1047        };
1048        let seen = word.load();
1049        drop(st);
1050        // The word moves only when a waker deregisters this bed (and every
1051        // sleeper in it): a return of the wait with the word unmoved is
1052        // spurious. (A sleeper would need 2^32 bumps between its read and
1053        // its wait to miss one.)
1054        while word.load() == seen {
1055            word.wait(seen);
1056        }
1057    }
1058
1059    /// After `done` moved from `before`: every bucket whose need it now
1060    /// covers.
1061    fn take_covered(&self, st: &mut Slots, before: u64, wakes: &mut Wakes) {
1062        let after = self.done.load(Ordering::SeqCst);
1063        // Registered needs exceed `done` when registered, so a covered one
1064        // lies in (before, after]; a bucket is visited once.
1065        for d in before + 1..=after.min(before + BUCKETS as u64) {
1066            let b = (d % BUCKETS as u64) as usize;
1067            let w = st.buckets[b];
1068            if w.waiting > 0 && w.need > before && w.need <= after {
1069                self.take_bucket(st, b, wakes);
1070            }
1071        }
1072    }
1073
1074    fn take_bucket(&self, st: &mut Slots, b: usize, wakes: &mut Wakes) {
1075        st.buckets[b].waiting = 0;
1076        self.bucket_words[b].bump();
1077        // Each bucket is taken at most once per decision: never full.
1078        debug_assert!(wakes.len < wakes.buckets.len(), "wake list full");
1079        if let Some(slot) = wakes.buckets.get_mut(wakes.len) {
1080            *slot = b as u8;
1081            wakes.len += 1;
1082        }
1083    }
1084
1085    fn take_designate(&self, st: &mut Slots, wakes: &mut Wakes) {
1086        if st.designate.take().is_some() {
1087            self.designate_word.bump();
1088            wakes.designate = true;
1089        }
1090    }
1091
1092    fn take_shared(&self, st: &mut Slots, wakes: &mut Wakes) {
1093        if st.shared > 0 {
1094            st.shared = 0;
1095            self.shared_word.bump();
1096            wakes.shared = true;
1097        }
1098    }
1099
1100    /// Every sleeper: poison, a failed flush, a panicked leader, and the
1101    /// tests' `drop_leadership`.
1102    fn take_everyone(&self, st: &mut Slots, wakes: &mut Wakes) {
1103        for b in 0..BUCKETS {
1104            if st.buckets[b].waiting > 0 {
1105                self.take_bucket(st, b, wakes);
1106            }
1107        }
1108        self.take_designate(st, wakes);
1109        self.take_shared(st, wakes);
1110    }
1111
1112    fn lock(&self) -> MutexGuard<'_, Slots> {
1113        self.state
1114            .lock()
1115            .unwrap_or_else(std::sync::PoisonError::into_inner)
1116    }
1117
1118    #[cfg(all(test, not(loom)))]
1119    fn notify(&self) {
1120        let mut st = self.lock();
1121        let mut wakes = Wakes::new();
1122        self.take_everyone(&mut st, &mut wakes);
1123        drop(st);
1124        wakes.send(self);
1125    }
1126}
1127
1128fn lock_wakers(m: &Mutex<PoisonWakers>) -> MutexGuard<'_, PoisonWakers> {
1129    m.lock().unwrap_or_else(std::sync::PoisonError::into_inner)
1130}
1131
1132/// Holds slot 0 for [`Domain::exclusive_main`]; gives it back on drop.
1133struct MainGuard<'a> {
1134    domain: &'a Domain,
1135}
1136
1137impl Drop for MainGuard<'_> {
1138    fn drop(&mut self) {
1139        let d = self.domain;
1140        let mut st = d.lock();
1141        st.busy &= !1;
1142        // Slot 0 is free: whoever waits for a slot.
1143        let mut wakes = Wakes::new();
1144        d.take_designate(&mut st, &mut wakes);
1145        d.take_shared(&mut st, &mut wakes);
1146        drop(st);
1147        wakes.send(d);
1148    }
1149}
1150
1151/// Held by a flush leader while its flush runs; dropped only if the flush
1152/// panics (the leader forgets it otherwise).
1153struct LeaderGuard<'a> {
1154    domain: &'a Domain,
1155    slot: u32,
1156}
1157
1158impl Drop for LeaderGuard<'_> {
1159    fn drop(&mut self) {
1160        self.domain.poison_unknown_flush(self.slot);
1161    }
1162}
1163
1164#[cfg(all(test, not(loom)))]
1165mod tests;
1166#[cfg(all(test, not(loom)))]
1167mod wake_tests;
1168
1169#[cfg(all(test, loom))]
1170mod loom_tests {
1171    use super::*;
1172    use loom::sync::Arc;
1173
1174    use store_io_core::error::OsErrorSource;
1175
1176    /// Runs a model on a domain of `slots`, with waiting barriers yielding
1177    /// and again with them going straight to sleep: loom runs a thread that
1178    /// yields only once nothing else can run, so yielding alone would hide
1179    /// the schedules that reach a sleep.
1180    fn model(slots: usize, f: impl Fn(Arc<Domain>) + Send + Sync + 'static) {
1181        let f = std::sync::Arc::new(f);
1182        for sleep in [false, true] {
1183            let f = std::sync::Arc::clone(&f);
1184            loom::model(move || {
1185                let d = Domain::with_slots(slots);
1186                if sleep {
1187                    d.patience
1188                        .skip
1189                        .store(u32::MAX, core::sync::atomic::Ordering::Relaxed);
1190                }
1191                f(Arc::new(d));
1192            });
1193        }
1194    }
1195
1196    /// Two barriers race; each must observe a flush issued after its ticket,
1197    /// and a failing flush must poison the other.
1198    #[test]
1199    fn loom_two_barriers_share_or_issue_and_poison_propagates() {
1200        model(1, |d| {
1201            let flushes = Arc::new(loom::sync::atomic::AtomicUsize::new(0));
1202            let spawn = |fail: bool| {
1203                let (d, flushes) = (d.clone(), flushes.clone());
1204                loom::thread::spawn(move || {
1205                    let need = d.ticket();
1206                    let r = d.barrier(need, |_, _| {
1207                        let _n = flushes.fetch_add(1, loom::sync::atomic::Ordering::SeqCst);
1208                        if fail {
1209                            Err(Some(OsError {
1210                                code: 5,
1211                                source: OsErrorSource::Sim,
1212                            }))
1213                        } else {
1214                            Ok(())
1215                        }
1216                    });
1217                    (need, r.is_ok())
1218                })
1219            };
1220            let a = spawn(false);
1221            let b = spawn(true);
1222            let (need_a, ok_a) = a.join().unwrap_or((0, false));
1223            let (_need_b, _ok_b) = b.join().unwrap_or((0, false));
1224            if ok_a {
1225                assert!(d.done.load(Ordering::SeqCst) >= need_a);
1226            }
1227            assert!(flushes.load(loom::sync::atomic::Ordering::SeqCst) <= 2);
1228        });
1229    }
1230
1231    /// One leader and two barriers of the same need: whoever sleeps is woken
1232    /// (the leader wakes their bucket at once), and all three return
1233    /// satisfied by one or more flushes.
1234    #[test]
1235    fn loom_every_barrier_of_one_need_is_woken() {
1236        model(1, |d| {
1237            let need = d.ticket();
1238            let spawn = || {
1239                let d = d.clone();
1240                loom::thread::spawn(move || d.barrier(need, |_, _| Ok(())).is_ok())
1241            };
1242            let all = [spawn(), spawn(), spawn()];
1243            for t in all {
1244                assert!(t.join().unwrap_or(false));
1245            }
1246            assert!(d.done.load(Ordering::SeqCst) >= need);
1247            assert_eq!(d.waiting(), 0);
1248        });
1249    }
1250
1251    /// Three barriers take their tickets as they run, so some need the
1252    /// next flush while one is in flight: whoever sleeps as the designate,
1253    /// in a bucket or on the shared word is woken, and every barrier
1254    /// returns satisfied with nobody left registered.
1255    #[test]
1256    fn loom_barriers_needing_the_next_flush_are_led_and_woken() {
1257        model(1, |d| {
1258            let spawn = || {
1259                let d = d.clone();
1260                loom::thread::spawn(move || {
1261                    let need = d.ticket();
1262                    (need, d.barrier(need, |_, _| Ok(())).is_ok())
1263                })
1264            };
1265            let all = [spawn(), spawn(), spawn()];
1266            for t in all {
1267                let (need, ok) = t.join().unwrap_or((0, false));
1268                assert!(ok);
1269                assert!(d.done.load(Ordering::SeqCst) >= need);
1270            }
1271            assert_eq!(d.waiting(), 0);
1272        });
1273    }
1274
1275    /// One slot: a barrier, a barrier taking its ticket as it runs (it may
1276    /// become the designate) and a full flush: the designate parked behind
1277    /// the full flush's claim on slot 0 is woken when slot 0 is freed, and
1278    /// everyone returns.
1279    #[test]
1280    fn loom_a_full_flush_and_the_designate() {
1281        model(1, |d| {
1282            let spawn = || {
1283                let d = d.clone();
1284                loom::thread::spawn(move || {
1285                    let need = d.ticket();
1286                    (need, d.barrier(need, |_, _| Ok(())).is_ok())
1287                })
1288            };
1289            let a = spawn();
1290            let b = spawn();
1291            d.exclusive_main(|| {});
1292            for t in [a, b] {
1293                let (need, ok) = t.join().unwrap_or((0, false));
1294                assert!(ok);
1295                assert!(d.done.load(Ordering::SeqCst) >= need);
1296            }
1297            assert_eq!(d.waiting(), 0);
1298        });
1299    }
1300
1301    /// Two slots: a barrier that may lead only on slot 0 and two that may
1302    /// lead on either, tickets taken as they run: the narrow one never takes
1303    /// the designate's place, and all return.
1304    #[test]
1305    fn loom_narrow_and_wide_barriers_on_two_slots() {
1306        model(2, |d| {
1307            let main = {
1308                let d = d.clone();
1309                loom::thread::spawn(move || {
1310                    let need = d.ticket();
1311                    (need, d.barrier_main(need, || Ok(())).is_ok())
1312                })
1313            };
1314            let wide = |d: &Arc<Domain>| {
1315                let d = d.clone();
1316                loom::thread::spawn(move || {
1317                    let need = d.ticket();
1318                    (need, d.barrier(need, |_, _| Ok(())).is_ok())
1319                })
1320            };
1321            let a = wide(&d);
1322            let b = wide(&d);
1323            for t in [main, a, b] {
1324                let (need, ok) = t.join().unwrap_or((0, false));
1325                assert!(ok);
1326                assert!(d.done.load(Ordering::SeqCst) >= need);
1327            }
1328            assert_eq!(d.waiting(), 0);
1329        });
1330    }
1331
1332    /// Poison from outside races two barriers on one slot (one may sleep as
1333    /// the designate, one in a bucket): each either returned satisfied
1334    /// before the poison or fails, and nobody is left registered.
1335    #[test]
1336    fn loom_outside_poison_wakes_the_designate_and_the_bucket() {
1337        model(1, |d| {
1338            let spawn = || {
1339                let d = d.clone();
1340                loom::thread::spawn(move || {
1341                    let need = d.ticket();
1342                    (need, d.barrier(need, |_, _| Ok(())).is_ok())
1343                })
1344            };
1345            let a = spawn();
1346            let b = spawn();
1347            d.poison(FirstCause {
1348                op: None,
1349                raw: None,
1350            });
1351            for t in [a, b] {
1352                let (need, ok) = t.join().unwrap_or((0, false));
1353                if ok {
1354                    assert!(d.done.load(Ordering::SeqCst) >= need);
1355                }
1356            }
1357            assert_eq!(d.waiting(), 0);
1358        });
1359    }
1360
1361    /// Two slots, two barriers, one failing flush: a barrier that returns
1362    /// success saw every flush up to its need succeed. With at most two
1363    /// flushes, success beside the other's failure means its own flush was
1364    /// flush 1 and `done` stopped there.
1365    #[test]
1366    fn loom_two_slots_never_satisfy_past_a_failure() {
1367        model(2, |d| {
1368            let spawn = |fail: bool| {
1369                let d = d.clone();
1370                loom::thread::spawn(move || {
1371                    let need = d.ticket();
1372                    let r = d.barrier(need, |_, _| {
1373                        if fail {
1374                            Err(Some(OsError {
1375                                code: 5,
1376                                source: OsErrorSource::Sim,
1377                            }))
1378                        } else {
1379                            Ok(())
1380                        }
1381                    });
1382                    (need, r.is_ok())
1383                })
1384            };
1385            let a = spawn(false);
1386            let b = spawn(true);
1387            let (need_a, ok_a) = a.join().unwrap_or((0, false));
1388            let (_need_b, ok_b) = b.join().unwrap_or((0, true));
1389            let done = d.done.load(Ordering::SeqCst);
1390            if ok_a {
1391                assert!(done >= need_a);
1392            }
1393            if ok_a && !ok_b {
1394                assert_eq!(done, 1, "satisfied past a failed flush");
1395            }
1396            assert!(d.stats().flushes <= 2);
1397        });
1398    }
1399
1400    /// A main-handle barrier and a data barrier race on two slots: both are
1401    /// satisfied, by flushes issued after their tickets, and the data
1402    /// leader never shares slot 0 with the main one.
1403    #[test]
1404    fn loom_a_main_barrier_and_a_data_barrier() {
1405        model(2, |d| {
1406            let in_main = Arc::new(loom::sync::atomic::AtomicBool::new(false));
1407            let main = {
1408                let (d, in_main) = (d.clone(), in_main.clone());
1409                loom::thread::spawn(move || {
1410                    let need = d.ticket();
1411                    let r = d.barrier_main(need, || {
1412                        in_main.store(true, loom::sync::atomic::Ordering::SeqCst);
1413                        in_main.store(false, loom::sync::atomic::Ordering::SeqCst);
1414                        Ok(())
1415                    });
1416                    (need, r.is_ok())
1417                })
1418            };
1419            let data = {
1420                let (d, in_main) = (d.clone(), in_main.clone());
1421                loom::thread::spawn(move || {
1422                    let need = d.ticket();
1423                    let r = d.barrier(need, |slot, _| {
1424                        if slot == 0 {
1425                            assert!(!in_main.load(loom::sync::atomic::Ordering::SeqCst));
1426                        }
1427                        Ok(())
1428                    });
1429                    (need, r.is_ok())
1430                })
1431            };
1432            let (need_m, ok_m) = main.join().unwrap_or((0, false));
1433            let (need_d, ok_d) = data.join().unwrap_or((0, false));
1434            assert!(ok_m && ok_d);
1435            let done = d.done.load(Ordering::SeqCst);
1436            assert!(done >= need_m && done >= need_d);
1437        });
1438    }
1439
1440    /// Poison from outside races a leader: a barrier that returns success
1441    /// had its flush recorded before the poison, and nobody is left waiting.
1442    #[test]
1443    fn loom_outside_poison_races_a_leader() {
1444        model(2, |d| {
1445            let leader = {
1446                let d = d.clone();
1447                loom::thread::spawn(move || {
1448                    let need = d.ticket();
1449                    (need, d.barrier(need, |_, _| Ok(())).is_ok())
1450                })
1451            };
1452            let poisoner = {
1453                let d = d.clone();
1454                loom::thread::spawn(move || {
1455                    d.poison(FirstCause {
1456                        op: None,
1457                        raw: None,
1458                    });
1459                })
1460            };
1461            let (need, ok) = leader.join().unwrap_or((0, false));
1462            let _p = poisoner.join();
1463            if ok {
1464                assert!(d.done.load(Ordering::SeqCst) >= need);
1465            }
1466            assert!(d.poisoned().is_some());
1467        });
1468    }
1469}