store-io-engine 0.5.1

The store-io engine: volumes, regions, barriers with flush sharing, receipts, provisioning and A/B slot objects over any store-io platform.
Documentation
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
//! Running operations on platform queues from the blocking layers.
//!
//! The simple and batch layers block their caller until the I/O is done. Each
//! call borrows one queue from a small per-store set with a non-blocking
//! `try_lock` (one atomic compare-and-swap when uncontended; a queue is held
//! only for the duration of one call's I/O, never while waiting for someone
//! else's flush). Only when every queue is busy does a caller wait, and then
//! for whichever queue is returned first: the guard's drop wakes one waiter.
//!
//! The wake-up is lost-wake-free without sequentially consistent loads: a
//! returning thread unlocks its queue (a read-modify-write of the mutex) and
//! then reads the waiter count with a read-modify-write; a waiter increments
//! the count and then retries every queue with `try_lock` (read-modify-writes)
//! while holding the wake mutex. Either the waiter's retry finds the returned
//! queue, or the returner sees the waiter and signals under the same mutex.

use std::ops::{Deref, DerefMut};
use std::sync::{Arc, Condvar, Mutex, MutexGuard, OnceLock, PoisonError, TryLockError};
use store_io_core::observe::{Counter, Observer};

use store_io_core::error::OsError;
use store_io_platform::{Completion, CompletionBuf, IoBuf, IoOp, Queue, RawResult, Rejected};

use crate::optable::Kind;
use crate::queue_core::Core;
use crate::sync::{AtomicBool, AtomicU64, Ordering};

/// A fixed set of queues shared by the blocking layers, plus an optional
/// flush lane and, created on first use, as many parallel lanes.
///
/// The flush lane (D-070) is used only by the thread holding a flush
/// domain's leadership. Leadership is exclusive, so the lane is never
/// contended, and a leader never waits for one of the shared queues, which
/// followers may be holding while they wait for that very leader.
///
/// Parallel lanes (D-096) hold queues asked to run their operations
/// concurrently (`QueueConfig::parallel`): a call that submits several
/// independent operations before it waits (a page batch of several writes,
/// a read or scan spanning more than one buffer) takes one. Everything else
/// keeps the shared lanes, so a single write or a read of one buffer never
/// leaves the caller's thread. They are created by the
/// first such call (on the Linux synchronous tier that starts the platform's
/// worker pool); if they cannot be, that call and every later one use the
/// shared lanes.
pub(crate) struct QueueSet<Q> {
    queues: Box<[Mutex<Lane<Q>>]>,
    /// The flush lanes, one per flush slot (D-070, D-124); empty when the
    /// set has none.
    flush: Box<[Mutex<Lane<Q>>]>,
    parallel: OnceLock<Box<[Mutex<Lane<Q>>]>>,
    /// Serialises creating the parallel lanes.
    parallel_init: Mutex<()>,
    /// The parallel queues' worker threads (`Queue::workers`), once created.
    parallel_workers: OnceLock<Option<usize>>,
    /// Creating the parallel queues failed: every later call uses a shared
    /// lane at once, without retrying (no lock convoy, no failed spawn per
    /// call).
    parallel_off: AtomicBool,
    depth: usize,
    /// One busy mark per shared lane, then one per parallel lane, then one
    /// per flush lane (at least one, D-095), each alone on its cache line and published
    /// by its lane's op table: odd while an operation is in flight on the
    /// lane (`2 * oldest + 1`, so it changes when the oldest completes),
    /// even otherwise. Only the holder writes it; a watchdog reads it
    /// without the lock. A lane not created yet keeps its mark even.
    marks: Box<[Arc<LaneMark>]>,
    waiters: AtomicU64,
    wake: Mutex<()>,
    returned: Condvar,
}

/// A [`Core`] (a queue and its op table, A1, PLANNING R3.3), as the
/// `Submitter` is one: one row per operation in flight. Every operation is
/// submitted under its row's tag (index and generation), so a completion is
/// matched to exactly the operation that made it, and the next holder of the
/// lane clears an earlier holder's abandoned operations row by row.
pub(crate) struct Lane<Q> {
    core: Core<Q>,
    /// This holder's completed operations, under the holder's own tags.
    pub(crate) done: CompletionBuf,
}

impl<Q: Queue> Lane<Q> {
    /// Submits `op` in a free row; the completion comes back in `done` with
    /// `tag`. A lane with no free row refuses it as a full queue (`raw:
    /// None`, the buffer returned).
    pub(crate) fn submit(&mut self, op: IoOp<'_, Q::File>, tag: u64) -> Result<(), Rejected> {
        let Some((index, qtag)) = self.core.table.claim() else {
            let buf = match op {
                IoOp::Write { buf, .. } | IoOp::Read { buf, .. } => Some(buf),
                IoOp::FlushData { .. } => None,
            };
            return Err(Rejected { buf, raw: None });
        };
        self.core.table.start(index, tag, Kind::Raw, None, false);
        self.core
            .queue
            .submit(op, qtag)
            .inspect_err(|_| self.core.table.abort(index))
    }

    /// Performs `op` at once when the lane holds nothing and its queue
    /// performs operations inside `submit` (`Queue::performs`: the inline
    /// synchronous queue): no row, no completion. Its busy mark is
    /// published for the duration, so a hung device stays visible to
    /// `Store::oldest_outstanding` (A1 C6). Otherwise the operation comes
    /// back for [`Self::submit`].
    #[allow(clippy::type_complexity)]
    pub(crate) fn perform<'a>(
        &mut self,
        op: IoOp<'a, Q::File>,
    ) -> Result<Result<(Option<IoBuf>, RawResult<usize>), IoOp<'a, Q::File>>, Rejected> {
        if self.core.table.live > 0 || !self.done.is_empty() || !self.core.queue.performs() {
            return Ok(Err(op));
        }
        /// Publishes the mark again when dropped: also if the call panics,
        /// so no performed operation is left looking outstanding.
        struct Idle<'t>(&'t crate::optable::Table);
        impl Drop for Idle<'_> {
            fn drop(&mut self) {
                self.0.publish();
            }
        }
        self.core.table.busy();
        let _idle = Idle(&self.core.table);
        self.core.queue.perform(op)
    }

    /// Waits until at least `min` of the queue's operations complete, then
    /// moves every completion that arrived into `done` under its caller's
    /// tag (also when the wait then failed). Returns how many arrived.
    ///
    /// # Errors
    ///
    /// The raw error if waiting failed: the operations still in flight keep
    /// their rows and their buffers stay with the queue.
    pub(crate) fn wait(&mut self, min: usize) -> Result<usize, OsError> {
        let waited = self.core.queue.wait(min, &mut self.core.raw);
        let n = self.collect();
        waited.map(|_| n)
    }

    /// Operations of this lane in flight.
    pub(crate) fn in_flight(&self) -> usize {
        self.core.table.live
    }

    fn collect(&mut self) -> usize {
        let mut n = 0;
        for c in self.core.raw.drain() {
            // A completion names a row in use: the queue is this lane's alone
            // and every tag names one use of one row.
            let Some(tag) = self.core.table.take(c.tag) else {
                debug_assert!(false, "a lane completion matched no row");
                continue;
            };
            n += 1;
            // `done` holds at most one completion per row (depth) and every
            // holder drains it before waiting again: a completion that did
            // not fit would be a result lost, so this stops instead.
            assert!(
                self.done.push(Completion { tag, ..c }).is_ok(),
                "a lane's completions overflowed"
            );
        }
        n
    }
}

/// A lane's busy mark, alone on its cache line so that lanes used by
/// different threads never share one. A `Submitter` keeps one too (D-098).
#[repr(align(128))]
pub(crate) struct LaneMark(AtomicU64);

impl LaneMark {
    pub(crate) fn new() -> Self {
        Self(AtomicU64::new(0))
    }

    /// Sets the mark (its only writer: the owner).
    #[inline]
    pub(crate) fn set(&self, v: u64) {
        self.0.store(v, Ordering::Relaxed);
    }

    pub(crate) fn get(&self) -> u64 {
        self.0.load(Ordering::Relaxed)
    }
}

/// A borrowed queue; returning a shared one wakes one caller waiting for a
/// shared queue (nothing waits for a parallel lane: a call that finds them
/// all busy takes a shared one).
///
/// Fields drop in declaration order: the queue's lock is released first,
/// then [`Notify`] wakes a waiter, which therefore always finds it free.
/// An operation abandoned on the lane (a failed wait) stays in its row, and
/// outstanding, until the next holder clears it.
pub(crate) struct LaneGuard<'a, Q: Queue> {
    guard: MutexGuard<'a, Lane<Q>>,
    _notify: Option<Notify<'a, Q>>,
}

/// The flush lane, borrowed by the flush leader.
pub(crate) struct FlushGuard<'a, Q: Queue> {
    guard: MutexGuard<'a, Lane<Q>>,
}

impl<Q: Queue> Deref for FlushGuard<'_, Q> {
    type Target = Lane<Q>;

    fn deref(&self) -> &Lane<Q> {
        &self.guard
    }
}

impl<Q: Queue> DerefMut for FlushGuard<'_, Q> {
    fn deref_mut(&mut self) -> &mut Lane<Q> {
        &mut self.guard
    }
}

/// Wakes one waiting caller, if any, when dropped.
struct Notify<'a, Q> {
    set: &'a QueueSet<Q>,
}

impl<Q> Drop for Notify<'_, Q> {
    fn drop(&mut self) {
        if self.set.waiters.fetch_add(0, Ordering::AcqRel) > 0 {
            let _wake = self.set.wake.lock().unwrap_or_else(PoisonError::into_inner);
            self.set.returned.notify_one();
        }
    }
}

impl<Q: Queue> LaneGuard<'_, Q> {
    /// A shared lane, which other callers wait for (a parallel lane is
    /// waited for by no one).
    pub(crate) fn is_shared(&self) -> bool {
        self._notify.is_some()
    }
}

impl<Q: Queue> Deref for LaneGuard<'_, Q> {
    type Target = Lane<Q>;

    fn deref(&self) -> &Lane<Q> {
        &self.guard
    }
}

impl<Q: Queue> DerefMut for LaneGuard<'_, Q> {
    fn deref_mut(&mut self) -> &mut Lane<Q> {
        &mut self.guard
    }
}

impl<Q: Queue> QueueSet<Q> {
    /// Wraps already-created queues; no flush lane.
    pub(crate) fn new(queues: Vec<Q>, depth: usize) -> Self {
        Self::build(queues, Vec::new(), depth)
    }

    /// Wraps already-created queues and dedicated flush lanes, one per
    /// flush slot.
    pub(crate) fn with_flush_lanes(queues: Vec<Q>, flush: Vec<Q>, depth: usize) -> Self {
        Self::build(queues, flush, depth)
    }

    fn build(queues: Vec<Q>, flush: Vec<Q>, depth: usize) -> Self {
        // One mark per shared lane, one per parallel lane, then one per
        // flush lane (one at least, which stays even when there is none).
        let n = queues.len();
        let marks: Box<[Arc<LaneMark>]> = (0..2 * n + flush.len().max(1))
            .map(|_| Arc::new(LaneMark(AtomicU64::new(0))))
            .collect();
        Self {
            queues: queues
                .into_iter()
                .zip(marks.iter())
                .map(|(q, m)| lane(q, m, depth))
                .collect(),
            flush: flush
                .into_iter()
                .zip(&marks[2 * n..])
                .map(|(q, m)| lane(q, m, depth))
                .collect(),
            parallel: OnceLock::new(),
            parallel_init: Mutex::new(()),
            parallel_workers: OnceLock::new(),
            parallel_off: AtomicBool::new(false),
            depth,
            marks,
            waiters: AtomicU64::new(0),
            wake: Mutex::new(()),
            returned: Condvar::new(),
        }
    }

    /// Flush slot `slot`'s lane, for the thread leading a flush on that
    /// slot only; `None` when the set has none.
    pub(crate) fn flush_lane(&self, slot: usize) -> Option<FlushGuard<'_, Q>> {
        self.flush.get(slot).map(|m| {
            let guard = m.lock().unwrap_or_else(PoisonError::into_inner);
            FlushGuard { guard }
        })
    }

    /// A parallel lane (see [`QueueSet`]), starting the search at `hint`.
    /// When every parallel lane is busy, the call takes a shared lane
    /// instead (waiting, as any shared call does, for whichever is returned
    /// first): never worse than a set without parallel lanes, and a thread
    /// that already holds a parallel lane (a scan's visitor reading) can
    /// never wait for itself. The first call creates them with
    /// `make(count)`; if that fails, or returns another count, this and every
    /// later call uses the shared lanes.
    pub(crate) fn get_parallel(
        &self,
        hint: usize,
        make: impl FnOnce(usize) -> Option<Vec<Q>>,
    ) -> LaneGuard<'_, Q> {
        let n = self.queues.len();
        if self.parallel_off.load(Ordering::Relaxed) {
            return self.get(hint);
        }
        let parallel = self.parallel.get().map(|b| &**b);
        let Some(lanes) = parallel.or_else(|| self.create_parallel(make)) else {
            return self.get(hint);
        };
        let found = (0..n).find_map(|i| {
            let at = (hint % n + i) % n;
            match lanes[at].try_lock() {
                Ok(g) => Some((at, g)),
                Err(TryLockError::Poisoned(p)) => Some((at, p.into_inner())),
                Err(TryLockError::WouldBlock) => None,
            }
        });
        let Some((_, guard)) = found else {
            return self.get(hint);
        };
        LaneGuard {
            guard,
            _notify: None,
        }
    }

    fn create_parallel(
        &self,
        make: impl FnOnce(usize) -> Option<Vec<Q>>,
    ) -> Option<&[Mutex<Lane<Q>>]> {
        let _one = self
            .parallel_init
            .lock()
            .unwrap_or_else(PoisonError::into_inner);
        if let Some(lanes) = self.parallel.get() {
            return Some(&**lanes);
        }
        // A caller that queued here behind a failed start does not try again.
        if self.parallel_off.load(Ordering::Relaxed) {
            return None;
        }
        let n = self.queues.len();
        let Some(queues) = make(n).filter(|qs| qs.len() == n && n > 0) else {
            self.parallel_off.store(true, Ordering::Relaxed);
            return None;
        };
        let _workers = self
            .parallel_workers
            .set(queues.first().and_then(Queue::workers));
        let lanes: Box<[Mutex<Lane<Q>>]> = queues
            .into_iter()
            .zip(&self.marks[n..2 * n])
            .map(|(q, m)| lane(q, m, self.depth))
            .collect();
        let _set = self.parallel.set(lanes);
        self.parallel.get().map(|b| &**b)
    }

    /// Whether the parallel lanes exist.
    #[cfg(test)]
    pub(crate) fn has_parallel(&self) -> bool {
        self.parallel.get().is_some()
    }

    /// Worker threads running the parallel lanes' operations, once they
    /// exist and the backend runs them on a pool (`Queue::workers`).
    pub(crate) fn parallel_workers(&self) -> Option<usize> {
        self.parallel_workers.get().copied().flatten()
    }

    /// The flush lanes, one per flush slot (0 when the set has none).
    pub(crate) fn flush_lanes(&self) -> usize {
        self.flush.len()
    }

    /// Keeps only the first `n` flush lanes (at least one when there are
    /// any), closing the rest: those of a store found read-only after its
    /// queues were made, and those left without a handle. Their busy marks
    /// stay, always even.
    pub(crate) fn keep_flush_lanes(&mut self, n: usize) {
        let mut lanes = core::mem::take(&mut self.flush).into_vec();
        lanes.truncate(n.max(1));
        self.flush = lanes.into_boxed_slice();
    }

    /// The shared lanes (as many parallel lanes follow them).
    pub(crate) fn shared_len(&self) -> usize {
        self.queues.len()
    }

    /// Every lane's busy mark: the shared lanes in order, the parallel lanes,
    /// then the flush lanes (odd while an operation is in flight on it;
    /// always even for a lane that does not exist).
    pub(crate) fn marks(&self) -> impl ExactSizeIterator<Item = u64> + '_ {
        self.marks.iter().map(|m| m.0.load(Ordering::Relaxed))
    }

    fn try_any(&self, hint: usize) -> Option<(usize, MutexGuard<'_, Lane<Q>>)> {
        let n = self.queues.len();
        (0..n).find_map(|i| {
            let at = (hint % n + i) % n;
            match self.queues[at].try_lock() {
                Ok(g) => Some((at, g)),
                Err(TryLockError::Poisoned(p)) => Some((at, p.into_inner())),
                Err(TryLockError::WouldBlock) => None,
            }
        })
    }

    /// Borrows a free queue, starting the search at `hint`; when all are
    /// busy, waits for the first one returned.
    pub(crate) fn get(&self, hint: usize) -> LaneGuard<'_, Q> {
        if let Some((_, guard)) = self.try_any(hint) {
            return LaneGuard {
                guard,
                _notify: Some(Notify { set: self }),
            };
        }
        let _registered = self.waiters.fetch_add(1, Ordering::AcqRel);
        let mut wake = self.wake.lock().unwrap_or_else(PoisonError::into_inner);
        let (_, guard) = loop {
            if let Some(found) = self.try_any(hint) {
                break found;
            }
            wake = self
                .returned
                .wait(wake)
                .unwrap_or_else(PoisonError::into_inner);
        };
        drop(wake);
        let _unregistered = self.waiters.fetch_sub(1, Ordering::AcqRel);
        LaneGuard {
            guard,
            _notify: Some(Notify { set: self }),
        }
    }
}

/// A lane over `queue` for one caller alone, outside any set (its busy
/// mark read by no one): the format-2 open's region header reads.
pub(crate) fn solo_lane<Q>(queue: Q, depth: usize) -> Lane<Q> {
    lane(queue, &Arc::new(LaneMark::new()), depth)
        .into_inner()
        .unwrap_or_else(PoisonError::into_inner)
}

/// A lane over `queue` with its completion buffer and busy mark.
fn lane<Q>(queue: Q, mark: &Arc<LaneMark>, depth: usize) -> Mutex<Lane<Q>> {
    let depth = depth.max(1);
    Mutex::new(Lane {
        // The table publishes the lane's busy mark (D-095).
        core: Core::new(queue, depth, Arc::clone(mark)),
        done: CompletionBuf::with_capacity(depth),
    })
}

/// What became of an operation that reached the queue.
pub(crate) enum Ran {
    /// It completed: its buffer (if any) and the raw result.
    Done {
        buf: Option<IoBuf>,
        result: RawResult<usize>,
    },
    /// Waiting failed with it in flight (or the queue could not even be
    /// cleared for it), so there is no result. Its buffer stays with the
    /// queue until it completes, and the next holder of the lane discards
    /// that completion ([`clear_stale`]). For a write, durability is unknown;
    /// for a read, it is a failure of the queue, never a verdict on the
    /// media.
    Abandoned(OsError),
}

/// Collects and discards what an earlier holder of this lane left in flight
/// when its wait failed, row by row, so that every holder starts with no
/// operation in flight and no completion can ever be taken for another
/// operation's. A completion means the device is done with its buffer, so
/// dropping one is safe. Nothing to clear (every time, unless a wait has
/// failed): three counts read, no call into the queue past `in_flight`.
///
/// # Errors
///
/// The raw error if waiting for them fails; nothing of the caller's has been
/// submitted.
pub(crate) fn clear_stale<Q: Queue>(lane: &mut Lane<Q>) -> Result<(), OsError> {
    if lane.done.is_empty() && lane.in_flight() == 0 && lane.core.queue.in_flight() == 0 {
        return Ok(());
    }
    lane.done.drain().for_each(drop);
    while lane.core.queue.in_flight() > 0 {
        let n = lane.core.queue.in_flight();
        let _added = lane.wait(n)?;
        lane.done.drain().for_each(drop);
    }
    // Rows whose queue holds nothing can never complete (a backend that lost
    // their completions): freed, so the lane is usable.
    debug_assert_eq!(lane.in_flight(), 0, "lane rows outlived their operations");
    if lane.in_flight() > 0 {
        lane.core.table.forget();
    }
    Ok(())
}

/// Submits one operation and waits for its completion.
///
/// # Errors
///
/// `Err((buf, raw))` when the operation was refused before reaching the
/// device (media untouched); the buffer is returned. If clearing an earlier
/// holder's abandoned operations fails first, the result is
/// [`Ran::Abandoned`].
pub(crate) fn run<Q: Queue>(
    slot: &mut Lane<Q>,
    op: IoOp<'_, Q::File>,
) -> Result<Ran, (Option<IoBuf>, Option<OsError>)> {
    const TAG: u64 = 0x5110;
    let is_read = matches!(op, IoOp::Read { .. });
    if let Err(raw) = clear_stale(slot) {
        // The queue cannot be waited on: nothing of this operation was
        // submitted, but the queue is broken, so it is abandoned, which
        // every caller treats as fail-stop (never as a refusal whose code
        // could read as "out of space").
        drop(op);
        return Ok(Ran::Abandoned(raw));
    }
    // Nothing in flight: a queue that runs operations inside `submit`
    // performs it here, without a row or a completion.
    let op = match slot.perform(op) {
        Ok(Ok((buf, result))) => {
            debug_assert!(
                !is_read || buf.is_some() || result.is_err(),
                "a read succeeded without its buffer (platform contract 1)"
            );
            return Ok(Ran::Done { buf, result });
        }
        Ok(Err(op)) => op,
        Err(r) => return Err((r.buf, r.raw)),
    };
    slot.submit(op, TAG).map_err(|r| (r.buf, r.raw))?;
    loop {
        for c in slot.done.drain() {
            if c.tag == TAG {
                debug_assert!(
                    !is_read || c.buf.is_some() || c.result.is_err(),
                    "a read succeeded without its buffer (platform contract 1)"
                );
                return Ok(Ran::Done {
                    buf: c.buf,
                    result: c.result,
                });
            }
        }
        if let Err(raw) = slot.wait(1) {
            // Waiting failed but the operation is in flight: its buffer is
            // still owned by the kernel and must not be released (its row
            // stays, for the next holder to clear).
            return Ok(Ran::Abandoned(raw));
        }
    }
}

/// A producer of writes for [`pump`].
pub(crate) trait Source {
    /// The next write as `(container offset, buffer)`, [`Next::Wait`] when a
    /// buffer must come back first, or [`Next::Done`].
    fn next(&mut self) -> Next;
    /// A buffer whose write completed in full; the source may reuse it.
    fn recycle(&mut self, buf: IoBuf);
    /// Whether this is one write larger than a buffer, submitted as several
    /// device writes (observability only; a batch of several is not).
    fn is_split(&self) -> bool {
        false
    }
}

/// What a [`Source`] has to offer.
pub(crate) enum Next {
    /// Write this buffer at this container offset.
    Write(u64, IoBuf),
    /// Nothing until a buffer is recycled.
    Wait,
    /// Every write has been produced.
    Done,
}

/// Outcome of [`pump`].
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub(crate) enum Pumped {
    /// Every write transferred its full length.
    All,
    /// The first write was refused before reaching the device and nothing
    /// was submitted: the media is untouched.
    Refused(Option<OsError>),
    /// A write failed, transferred short, or was refused after others had
    /// been submitted; or waiting failed. Durability is unknown.
    Failed(Option<OsError>),
}

/// Submits every write `src` produces on one queue, keeping as many in
/// flight as the queue accepts, and waits for all of them. On a queue that
/// performs operations at once (`Lane::perform`: the inline synchronous
/// queue) each write is performed in turn, nothing in flight between them,
/// and the first failure stops the call.
///
/// After the first failure nothing new is submitted, but every write already
/// in flight is still waited for: its buffer belongs to the kernel until its
/// completion arrives. Only a failed wait returns early, leaving those
/// buffers with the queue, which never releases a buffer the kernel owns.
pub(crate) fn pump<Q: Queue>(
    lane: &mut Lane<Q>,
    file: &Q::File,
    dsync: bool,
    src: &mut impl Source,
    obs: &Observer,
) -> Pumped {
    const TAG: u64 = 0x5111;
    // The caller's lane is already cleared (`Store::lane`).
    let mut in_flight = 0usize;
    let mut submitted = 0usize;
    let mut failure: Option<Option<OsError>> = None;
    let mut held: Option<(u64, IoBuf)> = None;
    let mut producing = true;
    loop {
        while failure.is_none() && producing {
            let (offset, buf) = match held.take() {
                Some(w) => w,
                None => match src.next() {
                    Next::Write(offset, buf) => (offset, buf),
                    Next::Wait => break,
                    Next::Done => {
                        producing = false;
                        break;
                    }
                },
            };
            let bytes = buf.len() as u64;
            let op = IoOp::Write {
                file,
                offset,
                buf,
                dsync,
            };
            // Nothing in flight: a queue that runs operations inside
            // `submit` performs it here, settled as its completion would be.
            let op = if in_flight == 0 {
                match lane.perform(op) {
                    Ok(Ok((buf, result))) => {
                        submitted += 1;
                        obs.add(Counter::Writes, 1);
                        obs.add(Counter::WriteBytes, bytes);
                        match (result, buf) {
                            (Ok(n), Some(buf)) if n == buf.len() => src.recycle(buf),
                            (result, _) => failure = Some(result.err()),
                        }
                        continue;
                    }
                    Ok(Err(op)) => op,
                    Err(r) => {
                        if submitted == 0 {
                            return Pumped::Refused(r.raw);
                        }
                        failure = Some(r.raw);
                        break;
                    }
                }
            } else {
                op
            };
            match lane.submit(op, TAG) {
                Ok(()) => {
                    in_flight += 1;
                    submitted += 1;
                    obs.add(Counter::Writes, 1);
                    obs.add(Counter::WriteBytes, bytes);
                }
                // Full: keep the write and retry once a completion frees room.
                Err(r) if r.raw.is_none() && in_flight > 0 => {
                    match r.buf {
                        Some(buf) => held = Some((offset, buf)),
                        // A refusal that did not return the buffer (a backend
                        // breaking platform contract 1): the write is lost,
                        // so the call fails rather than being acknowledged
                        // short.
                        None => failure = Some(None),
                    }
                    break;
                }
                Err(r) => {
                    if submitted == 0 {
                        return Pumped::Refused(r.raw);
                    }
                    failure = Some(r.raw);
                }
            }
        }
        if in_flight == 0 {
            if producing && failure.is_none() {
                // The source waits for a buffer while none is in flight: it
                // can never be satisfied. Fail rather than report success.
                if submitted == 0 {
                    return Pumped::Refused(None);
                }
                failure = Some(None);
            }
            break;
        }
        if let Err(raw) = lane.wait(1) {
            return Pumped::Failed(Some(raw));
        }
        for c in lane.done.drain() {
            in_flight = in_flight.saturating_sub(1);
            match (c.result, c.buf) {
                (Ok(n), Some(buf)) if n == buf.len() => src.recycle(buf),
                (result, _) => {
                    if failure.is_none() {
                        failure = Some(result.err());
                    }
                }
            }
        }
    }
    match failure {
        None => Pumped::All,
        Some(raw) => Pumped::Failed(raw),
    }
}

#[cfg(test)]
mod tests {
    #![allow(clippy::unwrap_used)]

    use std::path::Path;

    use store_io_core::error::ErrorContext;
    use store_io_platform::IoOp;
    use store_io_sim::{SimConfig, SimPlatform};

    use crate::{Store, StoreOptions};

    /// A completion left in the lane's buffer (a wait that collected it,
    /// then failed) is discarded by the next holder even with nothing in
    /// flight: never taken for another operation's.
    #[test]
    fn test_a_stale_completion_is_discarded_with_nothing_in_flight() {
        let p = SimPlatform::new(SimConfig::volatile(41));
        let s = Store::create(p, Path::new("/db"), StoreOptions::default()).unwrap();
        let mut lane = s.inner.queues.get(0);
        let stale = store_io_platform::Completion {
            tag: 0x5110,
            buf: None,
            result: Ok(4096),
        };
        assert!(lane.done.push(stale).is_ok());
        assert_eq!(lane.in_flight(), 0);
        super::clear_stale(&mut lane).unwrap();
        assert!(lane.done.is_empty(), "the stale completion was kept");
    }

    /// A refused submission gives its row back at once, within the same
    /// hold of the lane (A1 C5): nothing is left in flight for a later
    /// holder to clear.
    #[test]
    fn test_a_refused_lane_submission_leaves_nothing_in_flight() {
        let p = SimPlatform::new(SimConfig::volatile(40));
        let s = Store::create(p.clone(), Path::new("/db"), StoreOptions::default()).unwrap();
        let mut lane = s.inner.queues.get(0);
        for _ in 0..3 {
            p.with_world(|w| {
                let next = w.write_submits() + 1;
                w.faults_mut().fail_submit = Some((next, 5));
            });
            let buf = s.take(4096, ErrorContext::default()).unwrap();
            let op = IoOp::Write {
                file: &s.inner.file,
                offset: 0,
                buf,
                dsync: false,
            };
            let refused = lane.submit(op, 7).unwrap_err();
            assert!(refused.buf.is_some() && refused.raw.is_some());
            assert_eq!(lane.in_flight(), 0, "the refused row was not given back");
        }
    }
}