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}