Skip to main content

sensor_db/spool/
cursor.rs

1//! On-medium replication cursor: the record that says how far a copy got.
2//!
3//! Pure module — wire format and address arithmetic only, no I/O.
4//!
5//! # Why the cursor lives on the replica
6//!
7//! The replica is the only thing that knows what it actually received. Keeping
8//! the cursor there (rather than on the source) means two removable media can be
9//! rotated against one log with no local state at all: whichever one is inserted
10//! says where *it* got to.
11//!
12//! # Why two records per batch instead of one flag flip
13//!
14//! Entry headers get away with flipping `0xFF → 0x00` in place because both of
15//! their CRCs mask the flags byte. A cursor cannot do that: a commit record
16//! carries information the intent did not have — the exact end position, the
17//! entry count, the last timestamp — and NOR flash can only clear bits, so those
18//! fields cannot be filled in after the fact.
19//!
20//! So a batch writes two independent records: an **intent** before copying and a
21//! **commit** after the data is durable. Both cost one page write, exactly what
22//! an in-place flip would have cost, and a torn record simply fails its CRC and
23//! is ignored.
24
25use zerocopy::{
26    FromBytes, Immutable, IntoBytes, KnownLayout, Unaligned,
27    little_endian::{U32, U64},
28};
29
30use crate::db::LogPosition;
31use crate::error::Error;
32use crate::sector::LogId;
33
34/// Magic bytes identifying a spool cursor record.
35pub const SPOOL_CURSOR_MAGIC: [u8; 4] = *b"SPC1";
36
37/// Format version of the cursor record.
38pub const SPOOL_CURSOR_VERSION: u8 = 1;
39
40/// Size of a cursor record in bytes.
41pub const CURSOR_RECORD_SIZE: usize = 60;
42
43/// Byte length covered by the record CRC (everything before it).
44const CURSOR_CRC_COVERAGE: usize = CURSOR_RECORD_SIZE - 4;
45
46/// Number of erase sectors the cursor region occupies. They are ping-ponged so
47/// one always holds valid records while the other is being reclaimed.
48pub const CURSOR_SECTORS: u8 = 2;
49
50const CURSOR_CRC: crc::Crc<u32> = crc::Crc::<u32>::new(&crc::CRC_32_ISCSI);
51
52/// Which half of a batch a record represents.
53///
54/// The discriminants are deliberately neither `0x00` nor `0xFF`, so an erased
55/// page and a page of zeros are both rejected before the CRC is even consulted.
56#[derive(Debug, Clone, Copy, PartialEq, Eq)]
57#[cfg_attr(feature = "defmt", derive(defmt::Format))]
58pub enum CursorKind {
59    /// Written before a batch is copied. Records where the batch *starts*.
60    Intent,
61    /// Written after a batch is durable. Records where the batch *ends*.
62    Commit,
63}
64
65/// Raw byte for [`CursorKind::Intent`].
66pub const CURSOR_KIND_INTENT: u8 = 0xA1;
67/// Raw byte for [`CursorKind::Commit`].
68pub const CURSOR_KIND_COMMIT: u8 = 0xC0;
69
70impl CursorKind {
71    fn from_raw(raw: u8) -> Option<Self> {
72        match raw {
73            CURSOR_KIND_INTENT => Some(Self::Intent),
74            CURSOR_KIND_COMMIT => Some(Self::Commit),
75            _ => None,
76        }
77    }
78
79    fn to_raw(self) -> u8 {
80        match self {
81            Self::Intent => CURSOR_KIND_INTENT,
82            Self::Commit => CURSOR_KIND_COMMIT,
83        }
84    }
85}
86
87/// Wire-format cursor record (60 bytes), one per page-sized slot.
88///
89/// Every position field is in **source** coordinates. That is what makes the
90/// record portable: the medium can be read on a machine that has never seen the
91/// source device, and the descriptors still say exactly which source range each
92/// region of the replica came from.
93#[derive(FromBytes, IntoBytes, KnownLayout, Immutable, Unaligned, Clone, Copy)]
94#[repr(C, packed)]
95pub struct SpoolCursorWire {
96    /// [`SPOOL_CURSOR_MAGIC`].
97    pub magic: [u8; 4],
98    /// [`SPOOL_CURSOR_VERSION`].
99    pub version: u8,
100    /// [`CURSOR_KIND_INTENT`] or [`CURSOR_KIND_COMMIT`].
101    pub kind: u8,
102    /// Zero.
103    pub reserved: [u8; 2],
104    /// Identity of the source log this batch came from.
105    pub source_log_id: U32,
106    /// Epoch of the source sector this batch was read from.
107    ///
108    /// Batches never span source sectors, so this names exactly one run of the
109    /// source device — which is how a reader attributes copied entries to a run
110    /// when the source clock restarts at zero on every boot.
111    pub source_epoch: U32,
112    /// Monotonic batch counter. An intent and its commit share one.
113    ///
114    /// `u32` wraps after ~4 billion batches — at one batch per second, 136
115    /// years. The wrap is handled rather than merely survived: the cursor region
116    /// holds only a few hundred records, so the batches on any one medium always
117    /// sit inside a tiny window of the counter, and
118    /// [`CursorFold`](crate::spool::policy::CursorFold) orders them with
119    /// serial-number arithmetic instead of `<`.
120    pub batch_id: U32,
121    /// Source position the batch starts at (inclusive).
122    pub from_sequence: U32,
123    /// Byte offset of [`Self::from_sequence`].
124    pub from_offset: U32,
125    /// Commit: the exact end position (exclusive). Intent: the planned bound.
126    pub upto_sequence: U32,
127    /// Byte offset of [`Self::upto_sequence`].
128    pub upto_offset: U32,
129    /// Commit: entries actually copied. Intent: the budget.
130    pub entry_count: U32,
131    /// Replica-side position the batch's first entry landed at.
132    pub dest_sequence: U32,
133    /// Byte offset of [`Self::dest_sequence`].
134    pub dest_offset: U32,
135    /// Commit: the highest source timestamp in the batch. Intent: zero.
136    pub last_timestamp: U64,
137    /// CRC-32C over the preceding 56 bytes. Nothing is masked.
138    pub record_crc: U32,
139}
140
141impl SpoolCursorWire {
142    /// Build a record and compute its CRC.
143    #[allow(clippy::too_many_arguments)]
144    pub fn new(
145        kind: CursorKind,
146        source_log_id: Option<LogId>,
147        source_epoch: u32,
148        batch_id: u32,
149        from: LogPosition,
150        upto: LogPosition,
151        entry_count: u32,
152        dest: LogPosition,
153        last_timestamp: u64,
154    ) -> Self {
155        let mut record = Self {
156            magic: SPOOL_CURSOR_MAGIC,
157            version: SPOOL_CURSOR_VERSION,
158            kind: kind.to_raw(),
159            reserved: [0; 2],
160            source_log_id: U32::new(source_log_id.map_or(0, LogId::get)),
161            source_epoch: U32::new(source_epoch),
162            batch_id: U32::new(batch_id),
163            from_sequence: U32::new(from.sequence),
164            from_offset: U32::new(from.offset),
165            upto_sequence: U32::new(upto.sequence),
166            upto_offset: U32::new(upto.offset),
167            entry_count: U32::new(entry_count),
168            dest_sequence: U32::new(dest.sequence),
169            dest_offset: U32::new(dest.offset),
170            last_timestamp: U64::new(last_timestamp),
171            record_crc: U32::new(0),
172        };
173        record.record_crc = U32::new(record.compute_crc());
174        record
175    }
176
177    fn compute_crc(&self) -> u32 {
178        CURSOR_CRC.checksum(&self.as_bytes()[..CURSOR_CRC_COVERAGE])
179    }
180
181    /// Whether this record is structurally intact and of a known version.
182    pub fn is_valid(&self) -> bool {
183        self.magic == SPOOL_CURSOR_MAGIC
184            && self.version == SPOOL_CURSOR_VERSION
185            && CursorKind::from_raw(self.kind).is_some()
186            && self.record_crc.get() == self.compute_crc()
187    }
188
189    /// The kind of record, or `None` if the byte is not a known kind.
190    pub fn kind(&self) -> Option<CursorKind> {
191        CursorKind::from_raw(self.kind)
192    }
193
194    /// Source position the batch starts at.
195    pub fn from(&self) -> LogPosition {
196        LogPosition {
197            sequence: self.from_sequence.get(),
198            offset: self.from_offset.get(),
199        }
200    }
201
202    /// Source position the batch ends at.
203    pub fn upto(&self) -> LogPosition {
204        LogPosition {
205            sequence: self.upto_sequence.get(),
206            offset: self.upto_offset.get(),
207        }
208    }
209
210    /// Replica position the batch landed at.
211    pub fn dest(&self) -> LogPosition {
212        LogPosition {
213            sequence: self.dest_sequence.get(),
214            offset: self.dest_offset.get(),
215        }
216    }
217
218    /// The source position it is safe to resume from, given only this record.
219    ///
220    /// A commit proves everything up to `upto` is durable on the replica. An
221    /// intent proves only that the batch *started* at `from` — the copy may have
222    /// been interrupted anywhere after that — so `from` is the safe answer.
223    ///
224    /// Taking intents into account is what bounds duplicates to a single batch
225    /// even when a commit record is torn: by construction
226    /// `intent(n).from == commit(n-1).upto`, so a lost commit is recovered from
227    /// the next intent.
228    pub fn resume_point(&self) -> LogPosition {
229        match self.kind() {
230            Some(CursorKind::Commit) => self.upto(),
231            _ => self.from(),
232        }
233    }
234}
235
236/// Address arithmetic for the two-sector cursor region.
237///
238/// A record occupies one page-sized **slot**, because a page is the smallest
239/// unit this crate can write.
240#[derive(Debug, Clone, Copy, PartialEq, Eq)]
241#[cfg_attr(feature = "defmt", derive(defmt::Format))]
242pub struct CursorRegion {
243    base: u32,
244    sector_size: u32,
245    page_size: u32,
246}
247
248impl CursorRegion {
249    /// Describe a cursor region starting at `base`.
250    ///
251    /// # Errors
252    /// - `InvalidConfig` if the page cannot hold a record, if the sector is not
253    ///   a whole number of pages, or if fewer than two slots would fit
254    /// - `Overflow` if the region does not fit in `u32` address space
255    pub fn new(base: u32, sector_size: u32, page_size: u32) -> Result<Self, Error> {
256        if page_size < CURSOR_RECORD_SIZE as u32
257            || sector_size == 0
258            || page_size == 0
259            || !sector_size.is_multiple_of(page_size)
260            || sector_size / page_size < 2
261        {
262            return Err(Error::InvalidConfig);
263        }
264        let span = sector_size
265            .checked_mul(CURSOR_SECTORS as u32)
266            .ok_or(Error::Overflow)?;
267        base.checked_add(span).ok_or(Error::Overflow)?;
268        Ok(Self {
269            base,
270            sector_size,
271            page_size,
272        })
273    }
274
275    /// Slots available in one cursor sector.
276    pub fn slots_per_sector(&self) -> u32 {
277        self.sector_size / self.page_size
278    }
279
280    /// Total bytes the region occupies.
281    pub fn total_size(&self) -> u32 {
282        self.sector_size * CURSOR_SECTORS as u32
283    }
284
285    /// First byte of the region.
286    pub fn base(&self) -> u32 {
287        self.base
288    }
289
290    /// Byte after the last byte of the region.
291    pub fn end(&self) -> u32 {
292        self.base + self.total_size()
293    }
294
295    /// Offset of a cursor sector **within the region**.
296    ///
297    /// Region-relative, not a flash address: every access goes through a
298    /// [`Partition`](crate::Partition) based at [`base`](Self::base), which is
299    /// what keeps the spooler from being able to address the replica's database
300    /// sectors at all.
301    pub fn sector_offset(&self, sector: u8) -> u32 {
302        (sector % CURSOR_SECTORS) as u32 * self.sector_size
303    }
304
305    /// The half-open offset range one cursor sector occupies, for an erase.
306    ///
307    /// Region-relative, like every other offset here. It exists so the erase
308    /// bound is stated once: the two drivers had derived the same range by
309    /// different arithmetic — `total_size() / 2` against
310    /// `total_size() / CURSOR_SECTORS` — which agree only for as long as
311    /// [`CURSOR_SECTORS`] stays 2.
312    pub fn sector_range(&self, sector: u8) -> (u32, u32) {
313        let from = self.sector_offset(sector);
314        (from, from + self.sector_size)
315    }
316
317    /// Offset of a slot within the region. Region-relative; see
318    /// [`sector_offset`](Self::sector_offset).
319    pub fn slot_offset(&self, sector: u8, slot: u32) -> u32 {
320        self.sector_offset(sector) + slot * self.page_size
321    }
322
323    /// Every slot in the region, in address order.
324    ///
325    /// The scan has to read all of them — a resume point can be justified by any
326    /// record, and a torn slot in the middle still consumes its place — so the
327    /// traversal itself carries no decisions and belongs here rather than in a
328    /// driver's nested loop.
329    pub fn slots(&self) -> impl Iterator<Item = SlotAddress> + '_ {
330        let region = *self;
331        (0..CURSOR_SECTORS).flat_map(move |sector| {
332            (0..region.slots_per_sector()).map(move |slot| SlotAddress {
333                sector,
334                slot,
335                offset: region.slot_offset(sector, slot),
336            })
337        })
338    }
339}
340
341/// One slot's place in the cursor region, as [`CursorRegion::slots`] yields it.
342#[derive(Debug, Clone, Copy, PartialEq, Eq)]
343#[cfg_attr(feature = "defmt", derive(defmt::Format))]
344pub struct SlotAddress {
345    /// Which cursor sector the slot is in.
346    pub sector: u8,
347    /// The slot's index within that sector.
348    pub slot: u32,
349    /// Region-relative byte offset of the slot.
350    pub offset: u32,
351}
352
353#[cfg(test)]
354mod tests {
355    use super::*;
356
357    #[test]
358    fn record_size_matches_the_constant() {
359        assert_eq!(CURSOR_RECORD_SIZE, core::mem::size_of::<SpoolCursorWire>());
360    }
361
362    fn sample(kind: CursorKind) -> SpoolCursorWire {
363        SpoolCursorWire::new(
364            kind,
365            LogId::new(0xABCD),
366            7,
367            42,
368            LogPosition {
369                sequence: 3,
370                offset: 100,
371            },
372            LogPosition {
373                sequence: 3,
374                offset: 500,
375            },
376            17,
377            LogPosition {
378                sequence: 9,
379                offset: 28,
380            },
381            123_456,
382        )
383    }
384
385    #[test]
386    fn round_trips_through_bytes() {
387        let record = sample(CursorKind::Commit);
388        let bytes = record.as_bytes().to_vec();
389        let parsed = SpoolCursorWire::read_from_bytes(&bytes).unwrap();
390        assert!(parsed.is_valid());
391        assert_eq!(parsed.kind(), Some(CursorKind::Commit));
392        assert_eq!(parsed.batch_id.get(), 42);
393        assert_eq!(parsed.source_epoch.get(), 7);
394        assert_eq!(parsed.from().offset, 100);
395        assert_eq!(parsed.upto().offset, 500);
396        assert_eq!(parsed.dest().sequence, 9);
397        assert_eq!(parsed.last_timestamp.get(), 123_456);
398    }
399
400    #[test]
401    fn a_single_flipped_bit_fails_the_crc() {
402        let record = sample(CursorKind::Commit);
403        let mut bytes = record.as_bytes().to_vec();
404        bytes[20] ^= 0x01;
405        let parsed = SpoolCursorWire::read_from_bytes(&bytes).unwrap();
406        assert!(!parsed.is_valid(), "a torn record must not be trusted");
407    }
408
409    #[test]
410    fn an_erased_page_is_not_a_record() {
411        let bytes = [0xFFu8; CURSOR_RECORD_SIZE];
412        let parsed = SpoolCursorWire::read_from_bytes(&bytes).unwrap();
413        assert!(!parsed.is_valid());
414        assert_eq!(parsed.kind(), None);
415    }
416
417    #[test]
418    fn a_zeroed_page_is_not_a_record() {
419        let bytes = [0x00u8; CURSOR_RECORD_SIZE];
420        let parsed = SpoolCursorWire::read_from_bytes(&bytes).unwrap();
421        assert!(!parsed.is_valid());
422    }
423
424    #[test]
425    fn resume_point_trusts_commits_and_distrusts_intents() {
426        let commit = sample(CursorKind::Commit);
427        assert_eq!(commit.resume_point(), commit.upto());
428
429        let intent = sample(CursorKind::Intent);
430        assert_eq!(
431            intent.resume_point(),
432            intent.from(),
433            "an intent proves only where the batch started"
434        );
435    }
436
437    #[test]
438    fn region_rejects_geometry_that_cannot_hold_records() {
439        // Page too small for a record.
440        assert!(CursorRegion::new(0, 4096, 32).is_err());
441        // Sector not a whole number of pages.
442        assert!(CursorRegion::new(0, 4000, 256).is_err());
443        // Fewer than two slots: a batch needs an intent and a commit.
444        assert!(CursorRegion::new(0, 256, 256).is_err());
445        // Region runs off the end of the address space.
446        assert!(CursorRegion::new(u32::MAX - 1024, 4096, 256).is_err());
447    }
448
449    #[test]
450    fn region_addresses_are_laid_out_as_documented() {
451        let region = CursorRegion::new(0x1000, 4096, 256).unwrap();
452        assert_eq!(region.slots_per_sector(), 16);
453        assert_eq!(region.total_size(), 8192);
454        assert_eq!(region.base(), 0x1000);
455        assert_eq!(region.end(), 0x1000 + 8192);
456        // Offsets are region-relative: `base` appears in none of them, because
457        // the spooler reaches flash through a partition based there.
458        assert_eq!(region.sector_offset(0), 0);
459        assert_eq!(region.sector_offset(1), 4096);
460        assert_eq!(region.slot_offset(0, 0), 0);
461        assert_eq!(region.slot_offset(0, 3), 3 * 256);
462        assert_eq!(region.slot_offset(1, 15), 4096 + 15 * 256);
463        // …and the last slot still lands inside the region.
464        assert!(region.base() + region.slot_offset(1, 15) < region.end());
465    }
466
467    #[test]
468    fn a_sector_range_covers_exactly_one_cursor_sector() {
469        let region = CursorRegion::new(0x1000, 4096, 256).unwrap();
470        assert_eq!(region.sector_range(0), (0, 4096));
471        assert_eq!(region.sector_range(1), (4096, 8192));
472        // The two together tile the region, with no overlap and no hole — which
473        // is the property an erase of one must not violate.
474        assert_eq!(region.sector_range(1).1, region.total_size());
475    }
476
477    #[test]
478    fn the_slot_iterator_visits_every_slot_once_in_address_order() {
479        let region = CursorRegion::new(0x1000, 4096, 256).unwrap();
480
481        let mut visited = 0u32;
482        let mut previous: Option<SlotAddress> = None;
483        for at in region.slots() {
484            assert_eq!(at.offset, region.slot_offset(at.sector, at.slot));
485            // Strictly increasing: every slot is visited, and none twice.
486            if let Some(before) = previous {
487                assert!(before.offset < at.offset);
488            }
489            previous = Some(at);
490            visited += 1;
491        }
492
493        assert_eq!(visited, 2 * region.slots_per_sector());
494        assert_eq!(
495            region.slots().next().unwrap(),
496            SlotAddress {
497                sector: 0,
498                slot: 0,
499                offset: 0
500            }
501        );
502        assert_eq!(
503            previous.unwrap(),
504            SlotAddress {
505                sector: 1,
506                slot: 15,
507                offset: 4096 + 15 * 256
508            }
509        );
510    }
511}