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(®ion, 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(®ion, 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(®ion, 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(®ion, 1, 16);
1354 assert_eq!(
1355 plan,
1356 SlotPlan {
1357 sector: 0,
1358 slot: 0,
1359 erase_first: true
1360 }
1361 );
1362 }
1363}