sensor-db 0.1.0

Append-only sensor database for NOR flash on embedded devices
Documentation
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
//! On-medium replication cursor: the record that says how far a copy got.
//!
//! Pure module — wire format and address arithmetic only, no I/O.
//!
//! # Why the cursor lives on the replica
//!
//! The replica is the only thing that knows what it actually received. Keeping
//! the cursor there (rather than on the source) means two removable media can be
//! rotated against one log with no local state at all: whichever one is inserted
//! says where *it* got to.
//!
//! # Why two records per batch instead of one flag flip
//!
//! Entry headers get away with flipping `0xFF → 0x00` in place because both of
//! their CRCs mask the flags byte. A cursor cannot do that: a commit record
//! carries information the intent did not have — the exact end position, the
//! entry count, the last timestamp — and NOR flash can only clear bits, so those
//! fields cannot be filled in after the fact.
//!
//! So a batch writes two independent records: an **intent** before copying and a
//! **commit** after the data is durable. Both cost one page write, exactly what
//! an in-place flip would have cost, and a torn record simply fails its CRC and
//! is ignored.

use zerocopy::{
    FromBytes, Immutable, IntoBytes, KnownLayout, Unaligned,
    little_endian::{U32, U64},
};

use crate::db::LogPosition;
use crate::error::Error;
use crate::sector::LogId;

/// Magic bytes identifying a spool cursor record.
pub const SPOOL_CURSOR_MAGIC: [u8; 4] = *b"SPC1";

/// Format version of the cursor record.
pub const SPOOL_CURSOR_VERSION: u8 = 1;

/// Size of a cursor record in bytes.
pub const CURSOR_RECORD_SIZE: usize = 60;

/// Byte length covered by the record CRC (everything before it).
const CURSOR_CRC_COVERAGE: usize = CURSOR_RECORD_SIZE - 4;

/// Number of erase sectors the cursor region occupies. They are ping-ponged so
/// one always holds valid records while the other is being reclaimed.
pub const CURSOR_SECTORS: u8 = 2;

const CURSOR_CRC: crc::Crc<u32> = crc::Crc::<u32>::new(&crc::CRC_32_ISCSI);

/// Which half of a batch a record represents.
///
/// The discriminants are deliberately neither `0x00` nor `0xFF`, so an erased
/// page and a page of zeros are both rejected before the CRC is even consulted.
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
#[cfg_attr(feature = "defmt", derive(defmt::Format))]
pub enum CursorKind {
    /// Written before a batch is copied. Records where the batch *starts*.
    Intent,
    /// Written after a batch is durable. Records where the batch *ends*.
    Commit,
}

/// Raw byte for [`CursorKind::Intent`].
pub const CURSOR_KIND_INTENT: u8 = 0xA1;
/// Raw byte for [`CursorKind::Commit`].
pub const CURSOR_KIND_COMMIT: u8 = 0xC0;

impl CursorKind {
    fn from_raw(raw: u8) -> Option<Self> {
        match raw {
            CURSOR_KIND_INTENT => Some(Self::Intent),
            CURSOR_KIND_COMMIT => Some(Self::Commit),
            _ => None,
        }
    }

    fn to_raw(self) -> u8 {
        match self {
            Self::Intent => CURSOR_KIND_INTENT,
            Self::Commit => CURSOR_KIND_COMMIT,
        }
    }
}

/// Wire-format cursor record (60 bytes), one per page-sized slot.
///
/// Every position field is in **source** coordinates. That is what makes the
/// record portable: the medium can be read on a machine that has never seen the
/// source device, and the descriptors still say exactly which source range each
/// region of the replica came from.
#[derive(FromBytes, IntoBytes, KnownLayout, Immutable, Unaligned, Clone, Copy)]
#[repr(C, packed)]
pub struct SpoolCursorWire {
    /// [`SPOOL_CURSOR_MAGIC`].
    pub magic: [u8; 4],
    /// [`SPOOL_CURSOR_VERSION`].
    pub version: u8,
    /// [`CURSOR_KIND_INTENT`] or [`CURSOR_KIND_COMMIT`].
    pub kind: u8,
    /// Zero.
    pub reserved: [u8; 2],
    /// Identity of the source log this batch came from.
    pub source_log_id: U32,
    /// Epoch of the source sector this batch was read from.
    ///
    /// Batches never span source sectors, so this names exactly one run of the
    /// source device — which is how a reader attributes copied entries to a run
    /// when the source clock restarts at zero on every boot.
    pub source_epoch: U32,
    /// Monotonic batch counter. An intent and its commit share one.
    ///
    /// `u32` wraps after ~4 billion batches — at one batch per second, 136
    /// years. The wrap is handled rather than merely survived: the cursor region
    /// holds only a few hundred records, so the batches on any one medium always
    /// sit inside a tiny window of the counter, and
    /// [`CursorFold`](crate::spool::policy::CursorFold) orders them with
    /// serial-number arithmetic instead of `<`.
    pub batch_id: U32,
    /// Source position the batch starts at (inclusive).
    pub from_sequence: U32,
    /// Byte offset of [`Self::from_sequence`].
    pub from_offset: U32,
    /// Commit: the exact end position (exclusive). Intent: the planned bound.
    pub upto_sequence: U32,
    /// Byte offset of [`Self::upto_sequence`].
    pub upto_offset: U32,
    /// Commit: entries actually copied. Intent: the budget.
    pub entry_count: U32,
    /// Replica-side position the batch's first entry landed at.
    pub dest_sequence: U32,
    /// Byte offset of [`Self::dest_sequence`].
    pub dest_offset: U32,
    /// Commit: the highest source timestamp in the batch. Intent: zero.
    pub last_timestamp: U64,
    /// CRC-32C over the preceding 56 bytes. Nothing is masked.
    pub record_crc: U32,
}

impl SpoolCursorWire {
    /// Build a record and compute its CRC.
    #[allow(clippy::too_many_arguments)]
    pub fn new(
        kind: CursorKind,
        source_log_id: Option<LogId>,
        source_epoch: u32,
        batch_id: u32,
        from: LogPosition,
        upto: LogPosition,
        entry_count: u32,
        dest: LogPosition,
        last_timestamp: u64,
    ) -> Self {
        let mut record = Self {
            magic: SPOOL_CURSOR_MAGIC,
            version: SPOOL_CURSOR_VERSION,
            kind: kind.to_raw(),
            reserved: [0; 2],
            source_log_id: U32::new(source_log_id.map_or(0, LogId::get)),
            source_epoch: U32::new(source_epoch),
            batch_id: U32::new(batch_id),
            from_sequence: U32::new(from.sequence),
            from_offset: U32::new(from.offset),
            upto_sequence: U32::new(upto.sequence),
            upto_offset: U32::new(upto.offset),
            entry_count: U32::new(entry_count),
            dest_sequence: U32::new(dest.sequence),
            dest_offset: U32::new(dest.offset),
            last_timestamp: U64::new(last_timestamp),
            record_crc: U32::new(0),
        };
        record.record_crc = U32::new(record.compute_crc());
        record
    }

    fn compute_crc(&self) -> u32 {
        CURSOR_CRC.checksum(&self.as_bytes()[..CURSOR_CRC_COVERAGE])
    }

    /// Whether this record is structurally intact and of a known version.
    pub fn is_valid(&self) -> bool {
        self.magic == SPOOL_CURSOR_MAGIC
            && self.version == SPOOL_CURSOR_VERSION
            && CursorKind::from_raw(self.kind).is_some()
            && self.record_crc.get() == self.compute_crc()
    }

    /// The kind of record, or `None` if the byte is not a known kind.
    pub fn kind(&self) -> Option<CursorKind> {
        CursorKind::from_raw(self.kind)
    }

    /// Source position the batch starts at.
    pub fn from(&self) -> LogPosition {
        LogPosition {
            sequence: self.from_sequence.get(),
            offset: self.from_offset.get(),
        }
    }

    /// Source position the batch ends at.
    pub fn upto(&self) -> LogPosition {
        LogPosition {
            sequence: self.upto_sequence.get(),
            offset: self.upto_offset.get(),
        }
    }

    /// Replica position the batch landed at.
    pub fn dest(&self) -> LogPosition {
        LogPosition {
            sequence: self.dest_sequence.get(),
            offset: self.dest_offset.get(),
        }
    }

    /// The source position it is safe to resume from, given only this record.
    ///
    /// A commit proves everything up to `upto` is durable on the replica. An
    /// intent proves only that the batch *started* at `from` — the copy may have
    /// been interrupted anywhere after that — so `from` is the safe answer.
    ///
    /// Taking intents into account is what bounds duplicates to a single batch
    /// even when a commit record is torn: by construction
    /// `intent(n).from == commit(n-1).upto`, so a lost commit is recovered from
    /// the next intent.
    pub fn resume_point(&self) -> LogPosition {
        match self.kind() {
            Some(CursorKind::Commit) => self.upto(),
            _ => self.from(),
        }
    }
}

/// Address arithmetic for the two-sector cursor region.
///
/// A record occupies one page-sized **slot**, because a page is the smallest
/// unit this crate can write.
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
#[cfg_attr(feature = "defmt", derive(defmt::Format))]
pub struct CursorRegion {
    base: u32,
    sector_size: u32,
    page_size: u32,
}

impl CursorRegion {
    /// Describe a cursor region starting at `base`.
    ///
    /// # Errors
    /// - `InvalidConfig` if the page cannot hold a record, if the sector is not
    ///   a whole number of pages, or if fewer than two slots would fit
    /// - `Overflow` if the region does not fit in `u32` address space
    pub fn new(base: u32, sector_size: u32, page_size: u32) -> Result<Self, Error> {
        if page_size < CURSOR_RECORD_SIZE as u32
            || sector_size == 0
            || page_size == 0
            || !sector_size.is_multiple_of(page_size)
            || sector_size / page_size < 2
        {
            return Err(Error::InvalidConfig);
        }
        let span = sector_size
            .checked_mul(CURSOR_SECTORS as u32)
            .ok_or(Error::Overflow)?;
        base.checked_add(span).ok_or(Error::Overflow)?;
        Ok(Self {
            base,
            sector_size,
            page_size,
        })
    }

    /// Slots available in one cursor sector.
    pub fn slots_per_sector(&self) -> u32 {
        self.sector_size / self.page_size
    }

    /// Total bytes the region occupies.
    pub fn total_size(&self) -> u32 {
        self.sector_size * CURSOR_SECTORS as u32
    }

    /// First byte of the region.
    pub fn base(&self) -> u32 {
        self.base
    }

    /// Byte after the last byte of the region.
    pub fn end(&self) -> u32 {
        self.base + self.total_size()
    }

    /// Offset of a cursor sector **within the region**.
    ///
    /// Region-relative, not a flash address: every access goes through a
    /// [`Partition`](crate::Partition) based at [`base`](Self::base), which is
    /// what keeps the spooler from being able to address the replica's database
    /// sectors at all.
    pub fn sector_offset(&self, sector: u8) -> u32 {
        (sector % CURSOR_SECTORS) as u32 * self.sector_size
    }

    /// The half-open offset range one cursor sector occupies, for an erase.
    ///
    /// Region-relative, like every other offset here. It exists so the erase
    /// bound is stated once: the two drivers had derived the same range by
    /// different arithmetic — `total_size() / 2` against
    /// `total_size() / CURSOR_SECTORS` — which agree only for as long as
    /// [`CURSOR_SECTORS`] stays 2.
    pub fn sector_range(&self, sector: u8) -> (u32, u32) {
        let from = self.sector_offset(sector);
        (from, from + self.sector_size)
    }

    /// Offset of a slot within the region. Region-relative; see
    /// [`sector_offset`](Self::sector_offset).
    pub fn slot_offset(&self, sector: u8, slot: u32) -> u32 {
        self.sector_offset(sector) + slot * self.page_size
    }

    /// Every slot in the region, in address order.
    ///
    /// The scan has to read all of them — a resume point can be justified by any
    /// record, and a torn slot in the middle still consumes its place — so the
    /// traversal itself carries no decisions and belongs here rather than in a
    /// driver's nested loop.
    pub fn slots(&self) -> impl Iterator<Item = SlotAddress> + '_ {
        let region = *self;
        (0..CURSOR_SECTORS).flat_map(move |sector| {
            (0..region.slots_per_sector()).map(move |slot| SlotAddress {
                sector,
                slot,
                offset: region.slot_offset(sector, slot),
            })
        })
    }
}

/// One slot's place in the cursor region, as [`CursorRegion::slots`] yields it.
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
#[cfg_attr(feature = "defmt", derive(defmt::Format))]
pub struct SlotAddress {
    /// Which cursor sector the slot is in.
    pub sector: u8,
    /// The slot's index within that sector.
    pub slot: u32,
    /// Region-relative byte offset of the slot.
    pub offset: u32,
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn record_size_matches_the_constant() {
        assert_eq!(CURSOR_RECORD_SIZE, core::mem::size_of::<SpoolCursorWire>());
    }

    fn sample(kind: CursorKind) -> SpoolCursorWire {
        SpoolCursorWire::new(
            kind,
            LogId::new(0xABCD),
            7,
            42,
            LogPosition {
                sequence: 3,
                offset: 100,
            },
            LogPosition {
                sequence: 3,
                offset: 500,
            },
            17,
            LogPosition {
                sequence: 9,
                offset: 28,
            },
            123_456,
        )
    }

    #[test]
    fn round_trips_through_bytes() {
        let record = sample(CursorKind::Commit);
        let bytes = record.as_bytes().to_vec();
        let parsed = SpoolCursorWire::read_from_bytes(&bytes).unwrap();
        assert!(parsed.is_valid());
        assert_eq!(parsed.kind(), Some(CursorKind::Commit));
        assert_eq!(parsed.batch_id.get(), 42);
        assert_eq!(parsed.source_epoch.get(), 7);
        assert_eq!(parsed.from().offset, 100);
        assert_eq!(parsed.upto().offset, 500);
        assert_eq!(parsed.dest().sequence, 9);
        assert_eq!(parsed.last_timestamp.get(), 123_456);
    }

    #[test]
    fn a_single_flipped_bit_fails_the_crc() {
        let record = sample(CursorKind::Commit);
        let mut bytes = record.as_bytes().to_vec();
        bytes[20] ^= 0x01;
        let parsed = SpoolCursorWire::read_from_bytes(&bytes).unwrap();
        assert!(!parsed.is_valid(), "a torn record must not be trusted");
    }

    #[test]
    fn an_erased_page_is_not_a_record() {
        let bytes = [0xFFu8; CURSOR_RECORD_SIZE];
        let parsed = SpoolCursorWire::read_from_bytes(&bytes).unwrap();
        assert!(!parsed.is_valid());
        assert_eq!(parsed.kind(), None);
    }

    #[test]
    fn a_zeroed_page_is_not_a_record() {
        let bytes = [0x00u8; CURSOR_RECORD_SIZE];
        let parsed = SpoolCursorWire::read_from_bytes(&bytes).unwrap();
        assert!(!parsed.is_valid());
    }

    #[test]
    fn resume_point_trusts_commits_and_distrusts_intents() {
        let commit = sample(CursorKind::Commit);
        assert_eq!(commit.resume_point(), commit.upto());

        let intent = sample(CursorKind::Intent);
        assert_eq!(
            intent.resume_point(),
            intent.from(),
            "an intent proves only where the batch started"
        );
    }

    #[test]
    fn region_rejects_geometry_that_cannot_hold_records() {
        // Page too small for a record.
        assert!(CursorRegion::new(0, 4096, 32).is_err());
        // Sector not a whole number of pages.
        assert!(CursorRegion::new(0, 4000, 256).is_err());
        // Fewer than two slots: a batch needs an intent and a commit.
        assert!(CursorRegion::new(0, 256, 256).is_err());
        // Region runs off the end of the address space.
        assert!(CursorRegion::new(u32::MAX - 1024, 4096, 256).is_err());
    }

    #[test]
    fn region_addresses_are_laid_out_as_documented() {
        let region = CursorRegion::new(0x1000, 4096, 256).unwrap();
        assert_eq!(region.slots_per_sector(), 16);
        assert_eq!(region.total_size(), 8192);
        assert_eq!(region.base(), 0x1000);
        assert_eq!(region.end(), 0x1000 + 8192);
        // Offsets are region-relative: `base` appears in none of them, because
        // the spooler reaches flash through a partition based there.
        assert_eq!(region.sector_offset(0), 0);
        assert_eq!(region.sector_offset(1), 4096);
        assert_eq!(region.slot_offset(0, 0), 0);
        assert_eq!(region.slot_offset(0, 3), 3 * 256);
        assert_eq!(region.slot_offset(1, 15), 4096 + 15 * 256);
        // …and the last slot still lands inside the region.
        assert!(region.base() + region.slot_offset(1, 15) < region.end());
    }

    #[test]
    fn a_sector_range_covers_exactly_one_cursor_sector() {
        let region = CursorRegion::new(0x1000, 4096, 256).unwrap();
        assert_eq!(region.sector_range(0), (0, 4096));
        assert_eq!(region.sector_range(1), (4096, 8192));
        // The two together tile the region, with no overlap and no hole — which
        // is the property an erase of one must not violate.
        assert_eq!(region.sector_range(1).1, region.total_size());
    }

    #[test]
    fn the_slot_iterator_visits_every_slot_once_in_address_order() {
        let region = CursorRegion::new(0x1000, 4096, 256).unwrap();

        let mut visited = 0u32;
        let mut previous: Option<SlotAddress> = None;
        for at in region.slots() {
            assert_eq!(at.offset, region.slot_offset(at.sector, at.slot));
            // Strictly increasing: every slot is visited, and none twice.
            if let Some(before) = previous {
                assert!(before.offset < at.offset);
            }
            previous = Some(at);
            visited += 1;
        }

        assert_eq!(visited, 2 * region.slots_per_sector());
        assert_eq!(
            region.slots().next().unwrap(),
            SlotAddress {
                sector: 0,
                slot: 0,
                offset: 0
            }
        );
        assert_eq!(
            previous.unwrap(),
            SlotAddress {
                sector: 1,
                slot: 15,
                offset: 4096 + 15 * 256
            }
        );
    }
}