Skip to main content

sensor_db/spool/
policy.rs

1//! Replication policy: what to copy next, and where the cursor record goes.
2//!
3//! Pure module — no I/O. Everything here is decidable from records already read
4//! and counters already held, which is what lets the blocking and async drivers
5//! share it verbatim.
6
7use zerocopy::FromBytes;
8
9use crate::db::{DbStats, LogPosition, ReadCursor, Replicated};
10use crate::error::Error;
11use crate::sector::LogId;
12use crate::spool::cursor::{
13    CURSOR_RECORD_SIZE, CURSOR_SECTORS, CursorKind, CursorRegion, SlotAddress, SpoolCursorWire,
14};
15
16/// Whether `a` is a later batch than `b`, allowing for the counter wrapping.
17///
18/// Batch ids are a `u32` that increments forever, so eventually it wraps and the
19/// newest record on a medium carries a *smaller* number than the oldest. Plain
20/// `>` reads that backwards, picks the wrong cursor sector as active, and —
21/// because [`plan_slots`] erases the sector it moves into — erases the one
22/// holding the true resume point. Replication would then replay from far behind.
23///
24/// The fix is serial-number arithmetic (RFC 1982): `a` is newer when the
25/// unsigned distance forward from `b` to `a` is less than half the space. That
26/// is unambiguous here by construction, because the whole cursor region holds
27/// only `2 × slots_per_sector` records — at most a few hundred consecutive
28/// batches, nowhere near the 2³¹ needed to make the comparison ambiguous.
29fn batch_is_newer(a: u32, b: u32) -> bool {
30    a != b && a.wrapping_sub(b) < 1 << 31
31}
32
33/// How much one [`Spooler::spool`](crate::spool::Spooler::spool) pass may copy.
34#[derive(Debug, Clone, Copy, PartialEq, Eq)]
35#[cfg_attr(feature = "defmt", derive(defmt::Format))]
36pub struct SpoolBudget {
37    /// Maximum entries copied in one pass.
38    ///
39    /// **This is the duplicate bound.** A power cut or an unclean removal can
40    /// replay at most the batch that was in flight, so this value is the worst
41    /// case number of duplicated entries on the replica. Smaller batches mean
42    /// fewer possible duplicates and more cursor writes; larger batches mean the
43    /// opposite.
44    pub max_entries: u32,
45}
46
47impl Default for SpoolBudget {
48    fn default() -> Self {
49        Self { max_entries: 64 }
50    }
51}
52
53impl SpoolBudget {
54    /// A budget of `max_entries` entries per pass.
55    pub const fn new(max_entries: u32) -> Self {
56        Self { max_entries }
57    }
58}
59
60/// What a successful [`attach`](crate::spool::Spooler::attach) found.
61#[derive(Debug, Clone, Copy, PartialEq, Eq)]
62#[cfg_attr(feature = "defmt", derive(defmt::Format))]
63pub struct Attached {
64    /// Source position replication will resume from, before reconciliation.
65    ///
66    /// When [`recovered_entries`](Self::recovered_entries) is non-zero this is
67    /// the *start* of the batch that was interrupted; the first replication pass
68    /// skips that many entries before copying anything, so the effective resume
69    /// point is further on. [`Spooler::reconcile`](crate::spool::Spooler::reconcile)
70    /// applies the skip eagerly and reports the reconciled position.
71    pub resume_from: LogPosition,
72    /// The most recent batch id on the medium, or 0 if it is fresh.
73    pub batch_id: u32,
74    /// A batch was in flight when the medium was last detached. This is that
75    /// batch's budget — the number of entries it was *allowed* to copy, and so
76    /// the worst case duplication if it cannot be reconciled.
77    ///
78    /// See [`recovered_entries`](Self::recovered_entries) for what actually
79    /// happens: when reconciliation succeeds, duplication is zero.
80    pub in_flight_entries: u32,
81    /// Entries of the interrupted batch found durable **on the replica**.
82    ///
83    /// This is one side of the reconciliation. Skipping them on the source is
84    /// the other, and it can still be abandoned — if the source ring has wrapped
85    /// past them, or if the two runs do not fingerprint alike. Read
86    /// [`resume_from`](Self::resume_from) to see whether the skip applied:
87    /// [`TieredDb::attach`] reconciles before returning, so there it already
88    /// accounts for the outcome, while after
89    /// [`Spooler::attach`](crate::spool::Spooler::attach) the skip is still
90    /// pending.
91    ///
92    /// Zero when no batch was in flight, and zero when the replica's own ring
93    /// had wrapped past where the batch landed — the run would then begin with
94    /// entries from earlier batches, so nothing about it can be trusted.
95    ///
96    /// [`TieredDb::attach`]: crate::spool::TieredDb::attach
97    pub recovered_entries: u32,
98    /// The medium carried no cursor: it is new to this log.
99    pub fresh: bool,
100}
101
102/// What one replication pass achieved.
103#[derive(Debug, Clone, Copy, PartialEq, Eq, Default)]
104#[cfg_attr(feature = "defmt", derive(defmt::Format))]
105pub struct SpoolProgress {
106    /// Entries copied in this pass.
107    pub entries_copied: u32,
108    /// Source position now durably replicated.
109    pub committed_upto: LogPosition,
110    /// Nothing further is waiting: the replica is level with the source's
111    /// durable tail.
112    pub caught_up: bool,
113    /// The resume point had fallen off the tail of the source ring, so entries
114    /// between it and the oldest retained sector were never copied.
115    ///
116    /// Not an error: it is what happens when a medium stays away long enough for
117    /// the ring to wrap.
118    pub gap: bool,
119    /// Sectors the pass erased **on the volume**.
120    ///
121    /// [`SpoolBudget`] bounds how much a pass copies, but not how long it takes,
122    /// and an erase is the one operation whose cost is nothing like the rest:
123    /// 100 ms or more on many NOR parts, against microseconds for a page write.
124    /// A pass that fills the replica's active sector, or that wraps the cursor
125    /// region, pays that.
126    ///
127    /// Use it to back off — spool less often, or with a smaller budget — when a
128    /// caller has latency it must meet elsewhere. Zero for most passes.
129    ///
130    /// This covers erases the *replication* pass caused. Under
131    /// [`WritePolicy::CardFirst`](crate::spool::WritePolicy::CardFirst) samples
132    /// go straight to the volume, so the same spike can land on `append`
133    /// instead; [`SensorDb::sectors_erased`](crate::SensorDb::sectors_erased) on
134    /// the volume is the counter that sees those.
135    pub volume_erased: u32,
136}
137
138impl SpoolProgress {
139    /// The outcome of a pass that found nothing waiting.
140    ///
141    /// Reported before any cursor record is written, so an idle poll costs no
142    /// slots — which is why this is not simply `default()` with a position: it
143    /// is `caught_up`, and it carries whatever the probe learned about a gap.
144    pub(crate) fn idle(at: LogPosition, gap: bool) -> Self {
145        Self {
146            entries_copied: 0,
147            committed_upto: at,
148            caught_up: true,
149            gap,
150            volume_erased: 0,
151        }
152    }
153
154    /// Fold a later pass into a running total.
155    ///
156    /// Counts add, positions and `caught_up` take the later pass's answer, and
157    /// `gap` sticks: a gap in any pass of the sequence is a gap in the whole of
158    /// it, and a pass that found nothing missing cannot un-report one.
159    pub(crate) fn absorb(&mut self, later: &Self) {
160        self.entries_copied += later.entries_copied;
161        self.committed_upto = later.committed_upto;
162        self.caught_up = later.caught_up;
163        self.gap |= later.gap;
164        self.volume_erased += later.volume_erased;
165    }
166}
167
168/// Erases one replication pass caused on the volume, from both sides of it.
169///
170/// The volume's own log counts the rotations its appends cause, but the cursor
171/// region is written through a [`Partition`](crate::Partition) — behind the
172/// database's back — so those erases reach no counter and have to be added by
173/// hand. Getting that wrong under-reports the one cost worth reporting: an erase
174/// is 100 ms or more on many NOR parts, against microseconds for a page write.
175#[derive(Debug, Clone, Copy)]
176pub(crate) struct EraseTally {
177    start: u32,
178    cursor: u32,
179}
180
181impl EraseTally {
182    /// Begin counting from the volume's current erase count.
183    pub(crate) fn new(volume_erased_so_far: u32) -> Self {
184        Self {
185            start: volume_erased_so_far,
186            cursor: 0,
187        }
188    }
189
190    /// Record an erase the spooler performed on the cursor region itself.
191    pub(crate) fn cursor_erase(&mut self) {
192        self.cursor += 1;
193    }
194
195    /// Total erases the pass caused, given the volume's count now.
196    pub(crate) fn total(&self, volume_erased_now: u32) -> u32 {
197        self.cursor + volume_erased_now.saturating_sub(self.start)
198    }
199}
200
201/// How much room is left on a log, and how close it is to overwriting.
202///
203/// Built from [`DbStats`] by [`from_stats`](Self::from_stats), and reached
204/// through [`TieredDb::volume_fill`](crate::spool::TieredDb::volume_fill).
205///
206/// # Why this matters more on a removable volume
207///
208/// Under [`WritePolicy::OnboardFirst`](crate::spool::WritePolicy::OnboardFirst)
209/// a full volume wraps and overwrites its own oldest copy of data the onboard
210/// log may still hold — bad, but recoverable. Under
211/// [`CardFirst`](crate::spool::WritePolicy::CardFirst) the volume holds the
212/// *only* copy of everything past the point it took over, so wrapping is real
213/// loss. Neither is reported as an error at the time it happens, because the
214/// ring overwriting its tail is normal operation for a log. Watching this is how
215/// an operator learns the swap window is closing while there is still time to
216/// swap.
217#[derive(Debug, Clone, Copy, PartialEq, Eq, Default)]
218#[cfg_attr(feature = "defmt", derive(defmt::Format))]
219pub struct VolumeFill {
220    /// Sectors holding data — sealed, plus the one being written.
221    pub used_sectors: u16,
222    /// Sectors still erased. Writes have this much room before the ring starts
223    /// reclaiming sectors that hold data.
224    pub free_sectors: u16,
225    /// Sectors in the volume's database region.
226    pub total_sectors: u16,
227    /// Entries the volume holds.
228    pub entries: u32,
229}
230
231impl VolumeFill {
232    /// Summarise a volume's statistics.
233    pub fn from_stats(stats: &DbStats) -> Self {
234        Self {
235            used_sectors: stats.used_sectors,
236            free_sectors: stats.free_sectors,
237            total_sectors: stats.used_sectors.saturating_add(stats.free_sectors),
238            entries: stats.total_entries,
239        }
240    }
241
242    /// Fraction of the region holding data, in tenths of a percent (`0..=1000`).
243    ///
244    /// Tenths rather than percent because a large card has enough sectors that
245    /// whole percent is a coarse warning, and this crate cannot use floats.
246    /// Zero when the geometry is empty.
247    pub fn used_permille(&self) -> u16 {
248        if self.total_sectors == 0 {
249            return 0;
250        }
251        ((self.used_sectors as u32 * 1000) / self.total_sectors as u32) as u16
252    }
253
254    /// No erased sectors remain, so the next sector rotation reclaims one that
255    /// holds data.
256    ///
257    /// The last moment at which swapping the medium still costs nothing: the
258    /// sector being written is not full yet, so this warns of loss rather than
259    /// reporting it. A volume configured with enough reserved sectors refuses
260    /// the write with `NoSpace` instead of overwriting, which is louder but
261    /// arrives just as late.
262    pub fn will_overwrite(&self) -> bool {
263        self.free_sectors == 0
264    }
265}
266
267/// Outcome of reading every slot in the cursor region.
268#[derive(Debug, Clone, Copy, PartialEq, Eq)]
269#[cfg_attr(feature = "defmt", derive(defmt::Format))]
270pub struct CursorScan {
271    /// Safe source position to resume from.
272    pub resume: LogPosition,
273    /// Highest batch id found.
274    pub last_batch_id: u32,
275    /// Entries an unfinished batch may duplicate.
276    pub in_flight: u32,
277    /// Replica position the unfinished batch's first entry landed at.
278    ///
279    /// Reading the replica forward from here counts what the batch actually
280    /// managed to store, which is what turns the [`in_flight`](Self::in_flight)
281    /// bound into an exact answer. Meaningless when `in_flight` is zero.
282    pub in_flight_dest: LogPosition,
283    /// Cursor sector to append the next record to.
284    pub active: u8,
285    /// Next free slot in `active`.
286    pub next_slot: u32,
287    /// Whether any valid record was found at all.
288    pub found: bool,
289}
290
291impl Default for CursorScan {
292    fn default() -> Self {
293        Self {
294            resume: LogPosition::BEGINNING,
295            last_batch_id: 0,
296            in_flight: 0,
297            in_flight_dest: LogPosition::BEGINNING,
298            active: 0,
299            next_slot: 0,
300            found: false,
301        }
302    }
303}
304
305impl CursorScan {
306    /// Where on the replica to read, and how far, to find what an interrupted
307    /// batch actually stored.
308    ///
309    /// `None` when no batch was in flight, which is the ordinary case and the
310    /// one that must cost no reads.
311    ///
312    /// The bound is deliberately **one past** the batch's budget: a run that
313    /// comes back longer than the batch was ever allowed to copy proves `dest`
314    /// is not describing this batch, and truncating the read at the budget would
315    /// hide exactly that.
316    pub(crate) fn landed_probe(&self) -> Option<(LogPosition, u32)> {
317        (self.in_flight > 0).then_some((self.in_flight_dest, self.in_flight + 1))
318    }
319
320    /// Decide whether a run read from the replica may be reconciled against.
321    ///
322    /// Returns an empty fingerprint — meaning "reconcile nothing, replay the
323    /// batch whole" — when the replica's own ring has wrapped past where the
324    /// batch landed, so the run would begin with entries from earlier batches,
325    /// or when it is longer than the batch's budget.
326    ///
327    /// Both fall back to duplicating rather than skipping, which is the rule the
328    /// whole reconciliation is built on: duplication is bounded and visible, a
329    /// wrong skip is silent loss.
330    pub(crate) fn accept_landed(&self, run: RunFingerprint, cursor: &ReadCursor) -> RunFingerprint {
331        if cursor.gap || run.entries() > self.in_flight {
332            return RunFingerprint::new();
333        }
334        run
335    }
336}
337
338/// A failure during a replication pass, tagged with which side it came from.
339///
340/// Both sides surface as [`Error::Flash`], and the two mean opposite things. A
341/// *volume* flash error is treated as the medium having gone — a driver cannot
342/// tell a yanked card from a genuine fault, both arrive as
343/// `NorFlashErrorKind::Other`, so the spooler faults the volume and stops. A
344/// *source* flash error says the device's own storage is failing and nothing
345/// about the card; condemning the card for it would report the wrong part as
346/// broken and force a needless detach while the real fault went unnoticed.
347///
348/// Internal to the drivers: it exists so that distinction survives the `?`
349/// operator between an operation and the place that decides what to do.
350#[derive(Debug)]
351pub(crate) struct SpoolFailure {
352    /// The error to report to the caller.
353    pub error: Error,
354    /// The failure came from reading the source log, not from the volume.
355    pub from_source: bool,
356}
357
358impl From<Error> for SpoolFailure {
359    /// Attribute an untagged failure to the **volume**.
360    ///
361    /// Most of a replication pass is volume work, so this is what makes a bare
362    /// `?` correct there. It is also the safer default of the two: attributing a
363    /// volume failure to the source would leave the spooler retrying against a
364    /// medium that is no longer present, whereas the reverse merely
365    /// over-reports. Source operations must still say so explicitly — see
366    /// [`SpoolFailure::from_source`].
367    fn from(error: Error) -> Self {
368        Self {
369            error,
370            from_source: false,
371        }
372    }
373}
374
375impl SpoolFailure {
376    /// Tag a result from an operation on the **source** log.
377    pub fn from_source<T>(result: Result<T, Error>) -> Result<T, Self> {
378        result.map_err(|error| Self {
379            error,
380            from_source: true,
381        })
382    }
383}
384
385/// Identity of a contiguous run of entries: how many, and which ones bound it.
386///
387/// Reconciling an interrupted batch means skipping, on the source, exactly the
388/// entries the replica already holds. Getting that count *too low* costs
389/// duplicates; getting it too high skips entries no replica ever received, which
390/// is silent data loss. So the count is never trusted on its own: the run is
391/// fingerprinted on both sides and the skip is abandoned unless they agree.
392///
393/// Two entries can legitimately share a sensor and a timestamp, so this is a
394/// consistency check rather than a proof. It is enough to catch the failures
395/// that matter — a `dest` that does not line up with where the batch began, and
396/// a replica whose copy is not a prefix of the source range it claims.
397#[derive(Debug, Clone, Copy, PartialEq, Eq, Default)]
398#[cfg_attr(feature = "defmt", derive(defmt::Format))]
399pub struct RunFingerprint {
400    entries: u32,
401    /// `(sensor_id, timestamp)` of the first entry in the run.
402    first: (u16, u64),
403    /// `(sensor_id, timestamp)` of the last.
404    last: (u16, u64),
405}
406
407impl RunFingerprint {
408    /// An empty run.
409    pub fn new() -> Self {
410        Self::default()
411    }
412
413    /// Note one more entry. Must be called in log order.
414    pub fn push(&mut self, sensor_id: u16, timestamp: u64) {
415        if self.entries == 0 {
416            self.first = (sensor_id, timestamp);
417        }
418        self.last = (sensor_id, timestamp);
419        self.entries += 1;
420    }
421
422    /// How many entries the run holds.
423    pub fn entries(&self) -> u32 {
424        self.entries
425    }
426
427    /// Whether the run is empty, in which case there is nothing to reconcile.
428    pub fn is_empty(&self) -> bool {
429        self.entries == 0
430    }
431}
432
433/// The newest batch seen so far, and what its records proved.
434#[derive(Debug, Clone, Copy)]
435struct NewestBatch {
436    batch_id: u32,
437    /// Whether a commit record for this batch was read.
438    committed: bool,
439    /// Commit: entries copied. Intent: the budget.
440    entries: u32,
441    /// Replica position the batch's first entry landed at.
442    dest: LogPosition,
443    /// Cursor sector its records live in. A batch's intent and commit are always
444    /// in the same sector — [`plan_slots`] moves to the other one rather than
445    /// split a pair — so one sector per batch is well defined.
446    sector: u8,
447}
448
449/// Folds cursor records into a [`CursorScan`] as they are read.
450///
451/// The driver reads slots in whatever order is convenient and feeds them here;
452/// all the ordering logic lives in this type.
453#[derive(Debug, Clone, Copy)]
454pub struct CursorFold {
455    scan: CursorScan,
456    /// Slot after the last occupied one, per cursor sector.
457    fill: [u32; CURSOR_SECTORS as usize],
458    /// The newest batch any record named.
459    newest_batch: Option<NewestBatch>,
460}
461
462impl Default for CursorFold {
463    fn default() -> Self {
464        Self::new()
465    }
466}
467
468impl CursorFold {
469    /// Start a fresh scan.
470    pub fn new() -> Self {
471        Self {
472            scan: CursorScan::default(),
473            fill: [0; CURSOR_SECTORS as usize],
474            newest_batch: None,
475        }
476    }
477
478    /// Note that a slot has been written to, whatever it now contains.
479    ///
480    /// This must be called for **every** slot that is not fully erased,
481    /// including ones whose contents fail validation. A torn write leaves a slot
482    /// with some bits cleared; NOR flash cannot write it again without an erase,
483    /// so the next record has to go after it. Tracking only valid records would
484    /// aim the next write straight at the damaged slot.
485    pub fn occupied(&mut self, sector: u8, slot: u32) {
486        let sector_idx = (sector % CURSOR_SECTORS) as usize;
487        self.fill[sector_idx] = self.fill[sector_idx].max(slot + 1);
488    }
489
490    /// Offer one structurally valid record, read from `sector`/`slot`.
491    ///
492    /// Implies [`occupied`](Self::occupied). The caller must have checked
493    /// [`SpoolCursorWire::is_valid`] and that the record belongs to the expected
494    /// source log.
495    pub fn record(&mut self, sector: u8, slot: u32, record: &SpoolCursorWire) {
496        self.occupied(sector, slot);
497
498        // The resume point is the highest any record can justify. Commits
499        // contribute their end, intents only their start.
500        let candidate = record.resume_point();
501        if candidate > self.scan.resume {
502            self.scan.resume = candidate;
503        }
504
505        let batch_id = record.batch_id.get();
506        let is_commit = record.kind() == Some(CursorKind::Commit);
507        let seen = NewestBatch {
508            batch_id,
509            committed: is_commit,
510            entries: record.entry_count.get(),
511            dest: record.dest(),
512            sector: sector % CURSOR_SECTORS,
513        };
514
515        // Ordering is wrapping-aware, so a region spanning the point where the
516        // batch counter rolled over still picks the true newest record.
517        self.newest_batch = Some(match self.newest_batch {
518            // Same batch: remember whether its commit made it to flash. An
519            // intent and its commit carry the same `dest`, so either will do.
520            Some(newest) if batch_id == newest.batch_id => NewestBatch {
521                committed: newest.committed || is_commit,
522                ..seen
523            },
524            Some(newest) if !batch_is_newer(batch_id, newest.batch_id) => newest,
525            _ => seen,
526        });
527
528        self.scan.found = true;
529    }
530
531    /// Feed one slot's raw bytes, read from `at`.
532    ///
533    /// This is the whole of what a scan decides, so the drivers contribute only
534    /// the read. Three rules, in order:
535    ///
536    /// - A slot with **any** bit cleared counts as [`occupied`](Self::occupied),
537    ///   valid or not. NOR cannot rewrite it without an erase, so the next
538    ///   record has to go after it; tracking only readable records would aim the
539    ///   next write straight at a slot a torn write had damaged. Only the record
540    ///   area can be dirty — the rest of the page is written as `0xFF`, which
541    ///   clears nothing.
542    /// - A record that fails [`is_valid`](SpoolCursorWire::is_valid) is skipped.
543    ///   It still occupied its slot.
544    /// - A record naming a **different** source log aborts the scan with
545    ///   [`Error::ForeignVolume`]: this medium is not ours, however plausible
546    ///   its database region looks. `expected == 0` (an anonymous log) or a
547    ///   record's own `0` matches anything.
548    ///
549    /// # Errors
550    /// - `CorruptCursor` if `buf` cannot be interpreted as a record at all
551    /// - `ForeignVolume` if the slot belongs to a different log
552    pub fn feed(
553        &mut self,
554        at: SlotAddress,
555        buf: &[u8; CURSOR_RECORD_SIZE],
556        expected: u32,
557    ) -> Result<(), Error> {
558        if buf.iter().all(|b| *b == 0xFF) {
559            return Ok(());
560        }
561        self.occupied(at.sector, at.slot);
562
563        let record = SpoolCursorWire::read_from_bytes(buf).map_err(|_| Error::CorruptCursor)?;
564        if !record.is_valid() {
565            return Ok(());
566        }
567        let found = record.source_log_id.get();
568        if expected != 0 && found != 0 && found != expected {
569            return Err(Error::ForeignVolume { expected, found });
570        }
571        self.record(at.sector, at.slot, &record);
572        Ok(())
573    }
574
575    /// Finish the scan.
576    pub fn finish(mut self) -> CursorScan {
577        // Everything about "where writing continues" follows from the newest
578        // batch, so it is derived here rather than accumulated per record —
579        // the comparison that decides which batch that is has to see them all.
580        if let Some(newest) = self.newest_batch {
581            self.scan.last_batch_id = newest.batch_id;
582            self.scan.active = newest.sector;
583            // An intent whose commit never landed: that batch may have been
584            // partly copied, so replaying it blind can duplicate up to its
585            // budget. `dest` says where on the replica to look to find out how
586            // much actually landed, which is what lets a driver replay exactly
587            // the remainder.
588            if !newest.committed {
589                self.scan.in_flight = newest.entries;
590                self.scan.in_flight_dest = newest.dest;
591            }
592        }
593        // After `active`, which selects which sector's fill level applies.
594        self.scan.next_slot = self.fill[self.scan.active as usize];
595        self.scan
596    }
597}
598
599/// Where the next pair of cursor records should go.
600#[derive(Debug, Clone, Copy, PartialEq, Eq)]
601#[cfg_attr(feature = "defmt", derive(defmt::Format))]
602pub struct SlotPlan {
603    /// Cursor sector to write into.
604    pub sector: u8,
605    /// Slot for the intent record. The commit goes in `slot + 1`.
606    pub slot: u32,
607    /// Whether `sector` must be erased before writing.
608    ///
609    /// True only when wrapping to the other sector. The sector being left behind
610    /// still holds valid records at that moment, so the resume point is never
611    /// unrecoverable — which is exactly why the *target* is erased on the way in
612    /// rather than the *source* on the way out.
613    pub erase_first: bool,
614}
615
616/// Decide where the next batch's records go.
617///
618/// A batch needs two consecutive slots. When fewer than two remain, it moves to
619/// the other cursor sector and erases it on arrival.
620pub fn plan_slots(region: &CursorRegion, active: u8, next_slot: u32) -> SlotPlan {
621    if next_slot + 2 <= region.slots_per_sector() {
622        SlotPlan {
623            sector: active % CURSOR_SECTORS,
624            slot: next_slot,
625            erase_first: false,
626        }
627    } else {
628        SlotPlan {
629            sector: (active + 1) % CURSOR_SECTORS,
630            slot: 0,
631            erase_first: true,
632        }
633    }
634}
635
636/// One replication batch, from planned to committed.
637///
638/// Produced by [`SpoolerState::plan_batch`] and consumed by
639/// [`SpoolerState::commit_batch`], with the driver's reads and writes in
640/// between. It is what keeps the two-record protocol stated once: which fields
641/// an intent carries and which a commit fills in is the reason the cursor needs
642/// two records at all, and it was previously written out in both drivers.
643#[derive(Debug, Clone, Copy)]
644pub(crate) struct Batch {
645    slots: SlotPlan,
646    batch_id: u32,
647    source_log: Option<LogId>,
648    source_epoch: u32,
649    from: LogPosition,
650    dest: LogPosition,
651    budget: SpoolBudget,
652}
653
654impl Batch {
655    /// The cursor sector this batch's two records go in.
656    pub(crate) fn sector(&self) -> u8 {
657        self.slots.sector
658    }
659
660    /// Slot for the intent record.
661    pub(crate) fn intent_slot(&self) -> u32 {
662        self.slots.slot
663    }
664
665    /// Slot for the commit record.
666    ///
667    /// Always immediately after the intent: [`plan_slots`] moves to the other
668    /// cursor sector rather than split a pair across the boundary, which is what
669    /// lets [`CursorFold`] treat one sector per batch as well defined.
670    pub(crate) fn commit_slot(&self) -> u32 {
671        self.slots.slot + 1
672    }
673
674    /// The region-relative range to erase before writing, if any.
675    pub(crate) fn erase(&self, region: &CursorRegion) -> Option<(u32, u32)> {
676        self.slots
677            .erase_first
678            .then(|| region.sector_range(self.slots.sector))
679    }
680
681    /// The record written **before** anything is copied.
682    ///
683    /// It can only promise where the batch starts, so `upto` repeats `from` and
684    /// the count is the *budget* — the most this batch may copy, which is what
685    /// bounds duplication when the commit never lands.
686    pub(crate) fn intent(&self) -> SpoolCursorWire {
687        SpoolCursorWire::new(
688            CursorKind::Intent,
689            self.source_log,
690            self.source_epoch,
691            self.batch_id,
692            self.from,
693            self.from,
694            self.budget.max_entries,
695            self.dest,
696            0,
697        )
698    }
699
700    /// The record written **after** the copy is durable.
701    ///
702    /// `copied` is counted in **entries**, not samples: the cursor describes a
703    /// range of the source log, and a run is one entry there however many
704    /// samples it holds.
705    pub(crate) fn commit(
706        &self,
707        upto: LogPosition,
708        copied: Replicated,
709        last_timestamp: u64,
710    ) -> SpoolCursorWire {
711        SpoolCursorWire::new(
712            CursorKind::Commit,
713            self.source_log,
714            self.source_epoch,
715            self.batch_id,
716            self.from,
717            upto,
718            copied.entries,
719            self.dest,
720            last_timestamp,
721        )
722    }
723}
724
725/// The one source sector a batch is confined to.
726///
727/// A batch never spans two source sectors, so each cursor record names exactly
728/// one source epoch — which is what lets a reader attribute copied entries to a
729/// particular run of the source device, whose clock restarts at zero on every
730/// boot. It usually costs nothing: a sector holds far more entries than a
731/// typical [`SpoolBudget`].
732#[derive(Debug, Clone, Copy, Default)]
733pub(crate) struct BatchSector(Option<u32>);
734
735impl BatchSector {
736    /// A batch that has not seen an entry yet.
737    pub(crate) fn new() -> Self {
738        Self::default()
739    }
740
741    /// Whether an entry from source sector `sequence` still belongs to this
742    /// batch, adopting that sector if it is the first entry offered.
743    pub(crate) fn admits(&mut self, sequence: u32) -> bool {
744        match self.0 {
745            Some(seq) => seq == sequence,
746            None => {
747                self.0 = Some(sequence);
748                true
749            }
750        }
751    }
752}
753
754/// Everything a spooler knows that is not the volume itself.
755///
756/// The blocking and async spoolers hold one of these and supply only the reads
757/// and writes around it: `attach` is a cursor scan fed to [`CursorFold`] and
758/// [`adopt_scan`](Self::adopt_scan); `reconcile` is
759/// [`take_pending`](Self::take_pending) → a source read →
760/// [`accept_skip`](Self::accept_skip); and a `spool` pass is
761/// [`plan_batch`](Self::plan_batch) → erase, intent, copy, sync, commit →
762/// [`commit_batch`](Self::commit_batch).
763///
764/// **A spooler method that is more than I/O choreography belongs here instead.**
765/// The two drivers are unrelated trait families, so their flash calls cannot be
766/// shared — but a decision duplicated between them is invisible to
767/// `tests/tiered_async.rs`, which asserts the two produce identical media and
768/// therefore calls a bug present in both correct. That has happened: the
769/// `attach`-before-`reconcile` ordering bug lived in exactly this code.
770#[derive(Debug, Clone, Copy)]
771pub(crate) struct SpoolerState {
772    source_log: Option<LogId>,
773    region: CursorRegion,
774    /// Cursor sector currently being appended to.
775    active: u8,
776    /// Next free slot in `active`.
777    next_slot: u32,
778    /// Highest batch id written so far.
779    last_batch_id: u32,
780    /// Source position replication resumes from.
781    resume: LogPosition,
782    /// The part of an interrupted batch already durable on the replica.
783    pending: RunFingerprint,
784}
785
786impl SpoolerState {
787    /// State for a fresh spooler with no volume attached.
788    ///
789    /// # Errors
790    /// - `InvalidConfig` if the geometry cannot hold cursor records
791    /// - `Overflow` if the region runs past the end of the address space
792    pub(crate) fn new(
793        source_log: Option<LogId>,
794        cursor_base: u32,
795        sector_size: u32,
796        page_size: u32,
797    ) -> Result<Self, Error> {
798        Ok(Self {
799            source_log,
800            region: CursorRegion::new(cursor_base, sector_size, page_size)?,
801            active: 0,
802            next_slot: 0,
803            last_batch_id: 0,
804            resume: LogPosition::BEGINNING,
805            pending: RunFingerprint::new(),
806        })
807    }
808
809    /// Identity of the log being replicated.
810    pub(crate) fn source_log(&self) -> Option<LogId> {
811        self.source_log
812    }
813
814    /// The log id a cursor record must carry, or 0 for an anonymous log.
815    pub(crate) fn expected_log(&self) -> u32 {
816        self.source_log.map_or(0, LogId::get)
817    }
818
819    /// Layout of the cursor region on the volume.
820    pub(crate) fn region(&self) -> &CursorRegion {
821        &self.region
822    }
823
824    /// Source position replication resumes from.
825    pub(crate) fn resume(&self) -> LogPosition {
826        self.resume
827    }
828
829    /// Entries an attach found on the replica that the next pass will skip.
830    pub(crate) fn pending_reconciliation(&self) -> u32 {
831        self.pending.entries()
832    }
833
834    /// Adopt what a cursor scan and a replica read found, and describe it.
835    pub(crate) fn adopt_scan(&mut self, scan: CursorScan, landed: RunFingerprint) -> Attached {
836        self.active = scan.active;
837        self.next_slot = scan.next_slot;
838        self.last_batch_id = scan.last_batch_id;
839        self.resume = scan.resume;
840        self.pending = landed;
841
842        Attached {
843            resume_from: scan.resume,
844            batch_id: scan.last_batch_id,
845            in_flight_entries: scan.in_flight,
846            recovered_entries: landed.entries(),
847            fresh: !scan.found,
848        }
849    }
850
851    /// Forget the volume that is leaving.
852    ///
853    /// The resume point and the pending reconciliation both describe *that*
854    /// medium — the cursor lives on the replica precisely so two cards can be
855    /// rotated with no local state — so the next attach recomputes them.
856    pub(crate) fn reset(&mut self) {
857        self.resume = LogPosition::BEGINNING;
858        self.pending = RunFingerprint::new();
859    }
860
861    /// Take the interrupted batch's fingerprint, leaving nothing behind.
862    ///
863    /// Taking rather than reading is what makes reconciliation idempotent: an
864    /// attempt that is abandoned must not be retried on the next pass, because
865    /// the resume point it would be judged against has since moved.
866    pub(crate) fn take_pending(&mut self) -> RunFingerprint {
867        core::mem::take(&mut self.pending)
868    }
869
870    /// Decide whether the source run just read may be skipped as already
871    /// replicated, advancing the resume point if so.
872    ///
873    /// The skip is abandoned — leaving the batch to replay whole — when the
874    /// source ring has wrapped past the resume point, so the entries the replica
875    /// holds are gone and skipping the same *count* from the new tail would step
876    /// over entries that were never copied; or when the two runs do not
877    /// [fingerprint](RunFingerprint) alike.
878    ///
879    /// Both fall back to duplicating, never to skipping.
880    pub(crate) fn accept_skip(
881        &mut self,
882        landed: &RunFingerprint,
883        found: &RunFingerprint,
884        cursor: &ReadCursor,
885    ) -> bool {
886        if cursor.gap || found != landed {
887            return false;
888        }
889        self.resume = cursor.next;
890        true
891    }
892
893    /// Plan the next batch: where its records go, and what they will say.
894    pub(crate) fn plan_batch(
895        &self,
896        source_epoch: u32,
897        dest: LogPosition,
898        budget: SpoolBudget,
899    ) -> Batch {
900        Batch {
901            slots: plan_slots(&self.region, self.active, self.next_slot),
902            batch_id: self.last_batch_id.wrapping_add(1),
903            source_log: self.source_log,
904            source_epoch,
905            from: self.resume,
906            dest,
907            budget,
908        }
909    }
910
911    /// Adopt a batch whose commit record is durable.
912    ///
913    /// **Only after the commit write succeeds.** Advancing `resume` is what
914    /// lets the source reclaim those sectors, so doing it any earlier trades the
915    /// crate's one hard guarantee — no loss — for nothing.
916    pub(crate) fn commit_batch(&mut self, batch: &Batch, upto: LogPosition) {
917        self.active = batch.slots.sector;
918        self.next_slot = batch.commit_slot() + 1;
919        self.last_batch_id = batch.batch_id;
920        self.resume = upto;
921    }
922}
923
924#[cfg(test)]
925mod tests {
926    use super::*;
927
928    fn region() -> CursorRegion {
929        CursorRegion::new(0, 4096, 256).unwrap()
930    }
931
932    fn pos(sequence: u32, offset: u32) -> LogPosition {
933        LogPosition { sequence, offset }
934    }
935
936    /// Replica position a batch's records name. Derived from the batch id so
937    /// each batch has a distinguishable one. Wrapping so the batch ids near
938    /// `u32::MAX` used by the wrap tests do not overflow it.
939    fn dest_of(batch_id: u32) -> LogPosition {
940        pos(100u32.wrapping_add(batch_id), 28)
941    }
942
943    fn intent(batch_id: u32, from: LogPosition, budget: u32) -> SpoolCursorWire {
944        SpoolCursorWire::new(
945            CursorKind::Intent,
946            LogId::new(1),
947            1,
948            batch_id,
949            from,
950            from,
951            budget,
952            dest_of(batch_id),
953            0,
954        )
955    }
956
957    fn commit(batch_id: u32, from: LogPosition, upto: LogPosition, n: u32) -> SpoolCursorWire {
958        SpoolCursorWire::new(
959            CursorKind::Commit,
960            LogId::new(1),
961            1,
962            batch_id,
963            from,
964            upto,
965            n,
966            dest_of(batch_id),
967            0,
968        )
969    }
970
971    #[test]
972    fn an_empty_region_resumes_from_the_beginning() {
973        let scan = CursorFold::new().finish();
974        assert!(!scan.found);
975        assert_eq!(scan.resume, LogPosition::BEGINNING);
976        assert_eq!(scan.next_slot, 0);
977        assert_eq!(scan.in_flight, 0);
978    }
979
980    #[test]
981    fn a_completed_batch_resumes_after_it() {
982        let mut fold = CursorFold::new();
983        fold.record(0, 0, &intent(1, pos(1, 28), 64));
984        fold.record(0, 1, &commit(1, pos(1, 28), pos(1, 900), 40));
985        let scan = fold.finish();
986
987        assert_eq!(scan.resume, pos(1, 900), "the commit is authoritative");
988        assert_eq!(scan.last_batch_id, 1);
989        assert_eq!(scan.next_slot, 2);
990        assert_eq!(scan.in_flight, 0, "the batch finished");
991    }
992
993    #[test]
994    fn an_unfinished_batch_reports_where_on_the_replica_it_landed() {
995        let mut fold = CursorFold::new();
996        fold.record(0, 0, &intent(1, pos(1, 28), 64));
997        fold.record(0, 1, &commit(1, pos(1, 28), pos(1, 900), 40));
998        fold.record(0, 2, &intent(2, pos(1, 900), 64));
999        let scan = fold.finish();
1000
1001        assert_eq!(
1002            scan.in_flight_dest,
1003            dest_of(2),
1004            "reconciling batch 2 means reading the replica from where it began"
1005        );
1006    }
1007
1008    #[test]
1009    fn a_finished_batch_reports_no_replica_position() {
1010        let mut fold = CursorFold::new();
1011        fold.record(0, 0, &intent(1, pos(1, 28), 64));
1012        fold.record(0, 1, &commit(1, pos(1, 28), pos(1, 900), 40));
1013        let scan = fold.finish();
1014
1015        assert_eq!(scan.in_flight, 0);
1016        assert_eq!(
1017            scan.in_flight_dest,
1018            LogPosition::BEGINNING,
1019            "nothing to reconcile, so nothing to read"
1020        );
1021    }
1022
1023    #[test]
1024    fn an_intent_and_its_commit_agree_on_the_replica_position() {
1025        // The commit copies `dest` from the intent, so a fold that sees only one
1026        // of them must reach the same answer as one that sees both.
1027        let mut intent_only = CursorFold::new();
1028        intent_only.record(0, 0, &intent(3, pos(2, 28), 64));
1029
1030        let mut both = CursorFold::new();
1031        both.record(0, 0, &intent(3, pos(2, 28), 64));
1032        both.record(0, 1, &commit(3, pos(2, 28), pos(2, 500), 20));
1033
1034        assert_eq!(intent_only.finish().in_flight_dest, dest_of(3));
1035        assert_eq!(both.finish().in_flight, 0);
1036    }
1037
1038    #[test]
1039    fn a_run_fingerprint_distinguishes_length_and_bounds() {
1040        let mut a = RunFingerprint::new();
1041        assert!(a.is_empty());
1042        for (sensor, ts) in [(1u16, 10u64), (1, 11), (2, 12)] {
1043            a.push(sensor, ts);
1044        }
1045        assert_eq!(a.entries(), 3);
1046        assert!(!a.is_empty());
1047
1048        // Same entries: identical.
1049        let mut same = RunFingerprint::new();
1050        for (sensor, ts) in [(1u16, 10u64), (1, 11), (2, 12)] {
1051            same.push(sensor, ts);
1052        }
1053        assert_eq!(a, same);
1054
1055        // A shorter run, a different start, and a different end all differ.
1056        let mut shorter = RunFingerprint::new();
1057        for (sensor, ts) in [(1u16, 10u64), (1, 11)] {
1058            shorter.push(sensor, ts);
1059        }
1060        assert_ne!(a, shorter);
1061
1062        let mut shifted = RunFingerprint::new();
1063        for (sensor, ts) in [(1u16, 11u64), (2, 12), (2, 13)] {
1064            shifted.push(sensor, ts);
1065        }
1066        assert_ne!(a, shifted, "a run starting one entry late must not match");
1067
1068        let mut other_end = RunFingerprint::new();
1069        for (sensor, ts) in [(1u16, 10u64), (1, 11), (2, 99)] {
1070            other_end.push(sensor, ts);
1071        }
1072        assert_ne!(a, other_end);
1073    }
1074
1075    #[test]
1076    fn a_torn_commit_falls_back_to_the_intent_start() {
1077        // The crash case: the intent is durable, the data may be partly copied,
1078        // and the commit never landed.
1079        let mut fold = CursorFold::new();
1080        fold.record(0, 0, &intent(1, pos(1, 28), 64));
1081        fold.record(0, 1, &commit(1, pos(1, 28), pos(1, 900), 40));
1082        fold.record(0, 2, &intent(2, pos(1, 900), 64));
1083        let scan = fold.finish();
1084
1085        assert_eq!(
1086            scan.resume,
1087            pos(1, 900),
1088            "resume where the unfinished batch began, so nothing is skipped"
1089        );
1090        assert_eq!(scan.last_batch_id, 2);
1091        assert_eq!(
1092            scan.in_flight, 64,
1093            "the unfinished batch may have copied up to its budget"
1094        );
1095    }
1096
1097    #[test]
1098    fn a_lost_commit_is_recovered_from_the_next_intent() {
1099        // batch 1's commit is missing entirely, but batch 2's intent records the
1100        // same position by construction, so no data is re-copied unnecessarily.
1101        let mut fold = CursorFold::new();
1102        fold.record(0, 0, &intent(1, pos(1, 28), 64));
1103        fold.record(0, 2, &intent(2, pos(1, 900), 64));
1104        fold.record(0, 3, &commit(2, pos(1, 900), pos(2, 300), 30));
1105        let scan = fold.finish();
1106
1107        assert_eq!(scan.resume, pos(2, 300));
1108        assert_eq!(scan.in_flight, 0);
1109    }
1110
1111    #[test]
1112    fn record_order_does_not_matter() {
1113        let records = [
1114            (0u8, 0u32, intent(1, pos(1, 28), 64)),
1115            (0, 1, commit(1, pos(1, 28), pos(1, 900), 40)),
1116            (0, 2, intent(2, pos(1, 900), 64)),
1117            (0, 3, commit(2, pos(1, 900), pos(2, 300), 30)),
1118        ];
1119
1120        let mut forward = CursorFold::new();
1121        for (s, i, r) in records.iter() {
1122            forward.record(*s, *i, r);
1123        }
1124        let mut backward = CursorFold::new();
1125        for (s, i, r) in records.iter().rev() {
1126            backward.record(*s, *i, r);
1127        }
1128        assert_eq!(forward.finish(), backward.finish());
1129    }
1130
1131    #[test]
1132    fn the_newest_batch_wins_across_cursor_sectors() {
1133        // After a wrap, the old sector still holds lower-numbered batches.
1134        let mut fold = CursorFold::new();
1135        fold.record(0, 14, &commit(9, pos(4, 28), pos(4, 900), 10));
1136        fold.record(1, 0, &intent(10, pos(4, 900), 64));
1137        fold.record(1, 1, &commit(10, pos(4, 900), pos(5, 100), 20));
1138        let scan = fold.finish();
1139
1140        assert_eq!(scan.active, 1, "writing continues in the newer sector");
1141        assert_eq!(scan.next_slot, 2);
1142        assert_eq!(scan.resume, pos(5, 100));
1143        assert_eq!(scan.last_batch_id, 10);
1144    }
1145
1146    #[test]
1147    fn a_torn_slot_still_consumes_its_place() {
1148        // A slot damaged by an interrupted write cannot be written again without
1149        // an erase, so the next record must go after it — even though nothing
1150        // valid was ever read from it.
1151        let mut fold = CursorFold::new();
1152        fold.record(0, 0, &intent(1, pos(1, 28), 64));
1153        fold.record(0, 1, &commit(1, pos(1, 28), pos(1, 900), 40));
1154        fold.record(0, 2, &intent(2, pos(1, 900), 64));
1155        fold.occupied(0, 3); // torn commit for batch 2
1156        let scan = fold.finish();
1157
1158        assert_eq!(scan.next_slot, 4, "the damaged slot is not reusable");
1159        assert_eq!(scan.resume, pos(1, 900), "and its batch replays");
1160        assert_eq!(scan.in_flight, 64);
1161    }
1162
1163    #[test]
1164    fn a_region_holding_only_a_torn_slot_skips_past_it() {
1165        let mut fold = CursorFold::new();
1166        fold.occupied(0, 0);
1167        let scan = fold.finish();
1168
1169        assert!(!scan.found, "no valid record was read");
1170        assert_eq!(scan.resume, LogPosition::BEGINNING);
1171        assert_eq!(scan.next_slot, 1, "but slot 0 is spent");
1172    }
1173
1174    #[test]
1175    fn batch_ordering_is_serial_not_numeric() {
1176        assert!(batch_is_newer(2, 1));
1177        assert!(!batch_is_newer(1, 2));
1178        assert!(!batch_is_newer(7, 7), "a batch is not newer than itself");
1179
1180        // The point of the exercise: across the wrap, the smaller number is the
1181        // newer batch.
1182        assert!(batch_is_newer(0, u32::MAX));
1183        assert!(batch_is_newer(3, u32::MAX - 3));
1184        assert!(!batch_is_newer(u32::MAX, 0));
1185    }
1186
1187    #[test]
1188    fn the_newest_batch_survives_the_counter_wrapping() {
1189        // Sector 0 holds the last batches before the counter wrapped; sector 1
1190        // holds the first ones after. Comparing ids with `<` reads this exactly
1191        // backwards — it calls u32::MAX the newest — and so would name sector 0
1192        // as active. The next batch would then be planned into sector 0 and,
1193        // once it filled, `plan_slots` would erase sector 1: the one holding the
1194        // true resume point.
1195        let mut fold = CursorFold::new();
1196        fold.record(0, 0, &intent(u32::MAX - 1, pos(1, 28), 64));
1197        fold.record(0, 1, &commit(u32::MAX - 1, pos(1, 28), pos(1, 500), 20));
1198        fold.record(0, 2, &intent(u32::MAX, pos(1, 500), 64));
1199        fold.record(0, 3, &commit(u32::MAX, pos(1, 500), pos(1, 900), 20));
1200        fold.record(1, 0, &intent(0, pos(1, 900), 64));
1201        fold.record(1, 1, &commit(0, pos(1, 900), pos(2, 300), 20));
1202        fold.record(1, 2, &intent(1, pos(2, 300), 64));
1203        fold.record(1, 3, &commit(1, pos(2, 300), pos(2, 700), 20));
1204        let scan = fold.finish();
1205
1206        assert_eq!(
1207            scan.active, 1,
1208            "writing continues where the newest batch is"
1209        );
1210        assert_eq!(scan.next_slot, 4);
1211        assert_eq!(scan.last_batch_id, 1);
1212        assert_eq!(scan.resume, pos(2, 700));
1213    }
1214
1215    #[test]
1216    fn an_unfinished_batch_is_still_detected_across_the_wrap() {
1217        // The dangerous half of the same bug: a torn commit on the batch *after*
1218        // the wrap. Numeric ordering would call u32::MAX the newest batch, see
1219        // its commit, and report nothing in flight — so reconciliation would not
1220        // run and the interrupted batch would replay whole, duplicating.
1221        let mut fold = CursorFold::new();
1222        fold.record(0, 0, &intent(u32::MAX, pos(1, 28), 64));
1223        fold.record(0, 1, &commit(u32::MAX, pos(1, 28), pos(1, 900), 20));
1224        fold.record(1, 0, &intent(0, pos(1, 900), 64));
1225        let scan = fold.finish();
1226
1227        assert_eq!(scan.in_flight, 64, "batch 0 is the newest, and unfinished");
1228        assert_eq!(scan.in_flight_dest, dest_of(0));
1229        assert_eq!(scan.resume, pos(1, 900), "the interrupted batch replays");
1230        assert_eq!(scan.active, 1);
1231    }
1232
1233    #[test]
1234    fn a_wrapped_region_folds_the_same_in_any_order() {
1235        let records = [
1236            (0u8, 2u32, intent(u32::MAX, pos(1, 500), 64)),
1237            (0, 3, commit(u32::MAX, pos(1, 500), pos(1, 900), 20)),
1238            (1, 0, intent(0, pos(1, 900), 64)),
1239            (1, 1, commit(0, pos(1, 900), pos(2, 300), 20)),
1240        ];
1241
1242        let mut forward = CursorFold::new();
1243        for (s, i, r) in records.iter() {
1244            forward.record(*s, *i, r);
1245        }
1246        let mut backward = CursorFold::new();
1247        for (s, i, r) in records.iter().rev() {
1248            backward.record(*s, *i, r);
1249        }
1250        assert_eq!(forward.finish(), backward.finish());
1251    }
1252
1253    #[test]
1254    fn volume_fill_reports_headroom_and_the_last_moment_to_swap() {
1255        let fill = VolumeFill::from_stats(&DbStats {
1256            total_entries: 4200,
1257            total_samples: 4200,
1258            used_sectors: 6,
1259            free_sectors: 2,
1260            reserved_sectors: 1,
1261            min_erase_count: 1,
1262            max_erase_count: 1,
1263            total_erase_count: 8,
1264        });
1265
1266        assert_eq!(fill.total_sectors, 8);
1267        assert_eq!(fill.entries, 4200);
1268        assert_eq!(fill.used_permille(), 750);
1269        assert!(!fill.will_overwrite(), "two sectors of headroom remain");
1270
1271        let full = VolumeFill::from_stats(&DbStats {
1272            used_sectors: 8,
1273            free_sectors: 0,
1274            ..DbStats {
1275                total_entries: 0,
1276                total_samples: 0,
1277                used_sectors: 0,
1278                free_sectors: 0,
1279                reserved_sectors: 0,
1280                min_erase_count: 0,
1281                max_erase_count: 0,
1282                total_erase_count: 0,
1283            }
1284        });
1285        assert_eq!(full.used_permille(), 1000);
1286        assert!(
1287            full.will_overwrite(),
1288            "the next rotation reclaims a sector holding data"
1289        );
1290
1291        // An empty geometry must not divide by zero.
1292        assert_eq!(VolumeFill::default().used_permille(), 0);
1293    }
1294
1295    #[test]
1296    fn a_batch_is_confined_to_the_first_source_sector_it_sees() {
1297        let mut batch = BatchSector::new();
1298        // The first entry chooses the sector; it can never be refused.
1299        assert!(batch.admits(7));
1300        assert!(batch.admits(7));
1301
1302        // The next sector ends the batch — and keeps ending it, so a caller that
1303        // asks twice does not accidentally adopt the new sector.
1304        assert!(!batch.admits(8));
1305        assert!(!batch.admits(8));
1306        assert!(batch.admits(7), "the batch still belongs to sector 7");
1307
1308        // A batch that has seen nothing adopts whatever it is offered, including
1309        // sector 0 — which an `Option`-free `u32` sentinel would get wrong.
1310        let mut from_zero = BatchSector::new();
1311        assert!(from_zero.admits(0));
1312        assert!(!from_zero.admits(1));
1313    }
1314
1315    #[test]
1316    fn slots_are_allocated_in_pairs_then_wrap_to_the_other_sector() {
1317        let region = region();
1318        assert_eq!(region.slots_per_sector(), 16);
1319
1320        let plan = plan_slots(&region, 0, 0);
1321        assert_eq!(
1322            plan,
1323            SlotPlan {
1324                sector: 0,
1325                slot: 0,
1326                erase_first: false
1327            }
1328        );
1329
1330        // 14 leaves room for exactly one more pair.
1331        let plan = plan_slots(&region, 0, 14);
1332        assert_eq!(
1333            plan,
1334            SlotPlan {
1335                sector: 0,
1336                slot: 14,
1337                erase_first: false
1338            }
1339        );
1340
1341        // 15 does not: a pair would not fit, so wrap and erase on arrival.
1342        let plan = plan_slots(&region, 0, 15);
1343        assert_eq!(
1344            plan,
1345            SlotPlan {
1346                sector: 1,
1347                slot: 0,
1348                erase_first: true
1349            }
1350        );
1351
1352        // ...and back again.
1353        let plan = plan_slots(&region, 1, 16);
1354        assert_eq!(
1355            plan,
1356            SlotPlan {
1357                sector: 0,
1358                slot: 0,
1359                erase_first: true
1360            }
1361        );
1362    }
1363}