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
//! Sector header and in-RAM sector index.

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

/// Sector magic bytes: "SD05" (current and only supported format).
pub const SECTOR_MAGIC: [u8; 4] = *b"SD05";

/// Format version carried in the sector header.
///
/// Redundant with the magic today, and kept anyway: with a version byte the
/// *next* format change can keep the magic and bump this instead, so an old
/// sector is reported as unsupported rather than silently reclassified as free
/// and overwritten.
pub const SECTOR_FORMAT_VERSION: u8 = 5;

/// Size of the sector header in bytes (28, SD05).
pub const SECTOR_HEADER_SIZE: usize = 28;

/// Byte length of the header fields covered by the header CRC (everything but
/// the trailing CRC field itself).
const SECTOR_HEADER_CRC_COVERAGE: usize = SECTOR_HEADER_SIZE - 4;

/// CRC-32C (same algorithm as the entry CRC) used to integrity-check the header.
const SECTOR_CRC: Crc<u32> = Crc::<u32>::new(&CRC_32_ISCSI);

/// Identity of a logical log.
///
/// A database may declare a `LogId`, which is written into every sector header.
/// This is what lets a device tell *its own* removable medium from someone
/// else's: mounting a volume whose sectors carry a different id fails with
/// [`Error::ForeignVolume`](crate::Error::ForeignVolume) instead of treating the
/// sectors as free space and erasing them.
///
/// A replica carries the id of the log it replicates, not an identity of its
/// own — the medium is a copy of exactly one log.
///
/// Backed by `NonZeroU32` so `Option<LogId>` is four bytes and "unset" is
/// unrepresentable in the typed API. Zero on the wire means *anonymous*, which
/// matches any configuration.
#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash, PartialOrd, Ord)]
#[cfg_attr(feature = "defmt", derive(defmt::Format))]
pub struct LogId(core::num::NonZeroU32);

impl LogId {
    /// Create a `LogId` from a raw value. Returns `None` for zero, which is
    /// reserved to mean "anonymous" on the wire.
    pub const fn new(raw: u32) -> Option<Self> {
        match core::num::NonZeroU32::new(raw) {
            Some(v) => Some(Self(v)),
            None => None,
        }
    }

    /// The raw value, always non-zero.
    pub const fn get(self) -> u32 {
        self.0.get()
    }
}

/// How a sector's header reads to a database configured with a given [`LogId`].
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
#[cfg_attr(feature = "defmt", derive(defmt::Format))]
pub enum SectorClass {
    /// A well-formed sector belonging to this log.
    Valid,
    /// Not a sector of this format: erased, never written, or foreign data that
    /// does not parse. Safe to treat as free space.
    Free,
    /// A well-formed sector of this format that belongs to a *different* log.
    ///
    /// Never treat this as free: erasing it would destroy another device's data.
    Foreign {
        /// The `log_id` found on the medium (0 if anonymous).
        found: u32,
    },
    /// A well-formed header of this family with a version this build cannot read.
    Unsupported {
        /// The version byte found on the medium.
        found: u8,
    },
}

/// Wire-format sector header for zerocopy serialization.
///
/// Layout (28 bytes, SD05):
/// - `magic: [u8; 4]` — "SD05"
/// - `version: u8` — [`SECTOR_FORMAT_VERSION`]
/// - `reserved: [u8; 3]` — zero
/// - `log_id: u32 LE` — identity of the owning log (0 = anonymous)
/// - `epoch: u32 LE` — the mount generation that *created this sector*; see
///   [`SensorDb::epoch`](crate::SensorDb::epoch) for what it can and cannot
///   distinguish
/// - `sequence: u32 LE` — monotonic sector counter
/// - `erase_count: u32 LE` — number of times this sector has been erased
/// - `header_crc: u32 LE` — CRC-32C over the preceding 24 bytes
///
/// The header CRC lets `mount` accept a sector body only when its header is
/// structurally intact, so stale data that happens to start with the magic bytes
/// is not mistaken for a valid sector.
#[derive(FromBytes, IntoBytes, KnownLayout, Immutable, Unaligned, Clone, Copy)]
#[repr(C, packed)]
pub struct SectorHeader {
    /// Format magic, always [`SECTOR_MAGIC`].
    pub magic: [u8; 4],
    /// Format version, always [`SECTOR_FORMAT_VERSION`].
    pub version: u8,
    /// Padding to align the fields that follow; written as zero.
    pub reserved: [u8; 3],
    /// Identity of the owning log; `0` is anonymous. A mismatch aborts the
    /// mount with [`Error::ForeignVolume`](crate::Error::ForeignVolume).
    pub log_id: U32,
    /// The mount generation that created this sector.
    pub epoch: U32,
    /// Monotonic sector counter, which is what reconstructs ring order.
    pub sequence: U32,
    /// Times this sector has been erased; the wear-levelling input.
    pub erase_count: U32,
    /// CRC-32C over the preceding 24 bytes.
    pub header_crc: U32,
}

impl SectorHeader {
    /// Create a new sector header.
    ///
    /// The header CRC is computed over every preceding field.
    pub fn new(log_id: Option<LogId>, epoch: u32, sequence: u32, erase_count: u32) -> Self {
        let mut header = Self {
            magic: SECTOR_MAGIC,
            version: SECTOR_FORMAT_VERSION,
            reserved: [0; 3],
            log_id: U32::new(log_id.map_or(0, LogId::get)),
            epoch: U32::new(epoch),
            sequence: U32::new(sequence),
            erase_count: U32::new(erase_count),
            header_crc: U32::new(0),
        };
        header.header_crc = U32::new(header.compute_crc());
        header
    }

    /// Compute the CRC-32C over the header fields excluding the CRC itself.
    fn compute_crc(&self) -> u32 {
        SECTOR_CRC.checksum(&self.as_bytes()[..SECTOR_HEADER_CRC_COVERAGE])
    }

    /// Check if this header is a structurally valid sector header of this
    /// format version: correct magic, known version, and matching header CRC.
    pub fn is_valid(&self) -> bool {
        self.magic == SECTOR_MAGIC
            && self.version == SECTOR_FORMAT_VERSION
            && self.header_crc.get() == self.compute_crc()
    }

    /// Classify this header for a database configured with `expected`.
    ///
    /// An anonymous database (`expected == None`) accepts any log id, which
    /// preserves the behaviour of databases that never declare an identity.
    /// A named database accepts its own id and anonymous media, and rejects
    /// anything else as [`SectorClass::Foreign`].
    pub fn classify(&self, expected: Option<LogId>) -> SectorClass {
        if self.magic != SECTOR_MAGIC || self.header_crc.get() != self.compute_crc() {
            return SectorClass::Free;
        }
        if self.version != SECTOR_FORMAT_VERSION {
            return SectorClass::Unsupported {
                found: self.version,
            };
        }
        let found = self.log_id.get();
        match expected {
            // Anonymous readers accept anything they can parse.
            None => SectorClass::Valid,
            // A named reader accepts its own sectors, and adopts anonymous ones
            // (a medium formatted before an identity was assigned).
            Some(id) if found == 0 || found == id.get() => SectorClass::Valid,
            _ => SectorClass::Foreign { found },
        }
    }
}

/// State of a sector in the ring buffer.
#[derive(Debug, Clone, Copy, PartialEq, Eq, Default)]
#[cfg_attr(feature = "defmt", derive(defmt::Format))]
pub enum SectorState {
    /// Sector is erased (all 0xFF).
    #[default]
    Erased,
    /// Sector is the current write target.
    Active,
    /// Sector is full and sealed (read-only).
    Sealed,
}

/// In-RAM summary of a sector for fast queries.
#[derive(Debug, Clone, Copy)]
#[cfg_attr(feature = "defmt", derive(defmt::Format))]
pub struct SectorSummary {
    /// Current state of the sector.
    pub state: SectorState,
    /// Sequence number from header (0 if erased).
    pub sequence: u32,
    /// Number of valid entries in this sector.
    ///
    /// *Entries*, not samples: a [run](crate::run) is one entry however many
    /// samples it holds. This is the unit replication works in — the spooler
    /// copies entries, and the eviction accounting has to agree with it — so it
    /// is deliberately not the number a reader sees. That is
    /// [`sample_count`](Self::sample_count).
    pub entry_count: u32,
    /// Number of samples readable from this sector.
    ///
    /// Equal to [`entry_count`](Self::entry_count) unless the sector holds
    /// runs, each of which contributes all of its samples. This is what `count`
    /// reports and what a query yields, because a run expands transparently.
    pub sample_count: u32,
    /// Next write offset within the sector.
    pub write_offset: u32,
    /// Minimum timestamp of entries in this sector.
    pub min_timestamp: u64,
    /// Maximum timestamp of any *sample* in this sector.
    ///
    /// A run reaches past its entry header's timestamp, so it contributes the
    /// timestamp of its last sample. Keeping this the maximum over samples
    /// rather than over headers is what lets sector pruning stay exact: a query
    /// for a run's tail must not skip the sector the run began in.
    pub max_timestamp: u64,
    /// Bloom filter bitset of sensor IDs present in this sector.
    ///
    /// Each sensor ID is hashed to one of 64 bits using Fibonacci hashing.
    /// For ≤16 distinct sensors (typical), near-zero false positives.
    /// No false negatives by construction.
    pub sensor_bloom: u64,
    /// Number of times this sector has been erased (from the SD03 header).
    pub erase_count: u32,
}

impl Default for SectorSummary {
    #[allow(clippy::derivable_impls)]
    fn default() -> Self {
        Self {
            state: SectorState::Erased,
            sequence: 0,
            entry_count: 0,
            sample_count: 0,
            write_offset: 0,
            min_timestamp: u64::MAX,
            max_timestamp: 0,
            sensor_bloom: 0,
            erase_count: 0,
        }
    }
}

/// Map a sensor ID to a single bit in a 64-bit bloom filter using Fibonacci hashing.
///
/// Uses the golden-ratio constant `0x9E3779B9` to spread sensor IDs across 64 bits.
/// For ≤16 distinct sensors, collisions are near-zero.
pub fn sensor_id_to_bit(sensor_id: u16) -> u64 {
    let hash = (sensor_id as u32).wrapping_mul(0x9E37_79B9);
    1u64 << ((hash >> 26) & 0x3F)
}

impl SectorSummary {
    /// Create a new erased sector summary.
    pub fn erased() -> Self {
        Self::default()
    }

    /// Check if a timestamp range overlaps with this sector's entries.
    pub fn overlaps_time_range(&self, t_start: u64, t_end: u64) -> bool {
        if self.entry_count == 0 {
            return false;
        }
        // Range [t_start, t_end] overlaps [min, max] if t_start <= max && t_end >= min
        t_start <= self.max_timestamp && t_end >= self.min_timestamp
    }

    /// Record a sensor ID in this sector's bloom filter.
    pub fn record_sensor(&mut self, sensor_id: u16) {
        self.sensor_bloom |= sensor_id_to_bit(sensor_id);
    }

    /// Check if this sector might contain entries for a given sensor ID.
    ///
    /// Returns `false` only if the sensor is definitely absent (no false negatives).
    /// May return `true` for absent sensors (false positives possible but rare for ≤16 sensors).
    pub fn might_contain_sensor(&self, sensor_id: u16) -> bool {
        self.sensor_bloom & sensor_id_to_bit(sensor_id) != 0
    }

    /// Widen the sector's bounds to cover an entry spanning `first..=last`.
    ///
    /// A single sample passes its timestamp twice; a [run](crate::run) passes
    /// the timestamps of its first and last samples, which is what keeps
    /// [`overlaps_time_range`](Self::overlaps_time_range) exact for a query
    /// aimed at a run's tail.
    pub fn record_span(&mut self, first: u64, last: u64) {
        self.update_timestamps(first);
        self.update_timestamps(last);
    }

    /// Update timestamp bounds with a new entry.
    pub fn update_timestamps(&mut self, timestamp: u64) {
        if timestamp < self.min_timestamp {
            self.min_timestamp = timestamp;
        }
        if timestamp > self.max_timestamp {
            self.max_timestamp = timestamp;
        }
    }
}

/// Sector footer magic: "SDF2".
///
/// `SDF1` differed only in lacking [`sample_count`](SectorFooter::sample_count),
/// which a sector holding [runs](crate::run) needs. A footer of the old format
/// fails [`describes`](SectorFooter::describes) and the sector falls back to a
/// body scan — the same path a torn or absent footer takes — so an existing
/// medium stays readable and simply loses the fast mount for its sealed sectors.
pub const SECTOR_FOOTER_MAGIC: [u8; 4] = *b"SDF2";

/// Format version carried in the sector footer.
pub const SECTOR_FOOTER_VERSION: u8 = 2;

/// Size of the sector footer in bytes (52).
///
/// The footer occupies the first bytes of a whole reserved *page* — see
/// [`SectorFooter`] — so this constant bounds nothing but the struct itself.
pub const SECTOR_FOOTER_SIZE: usize = 52;

/// Byte length of the footer fields covered by the footer CRC.
const SECTOR_FOOTER_CRC_COVERAGE: usize = SECTOR_FOOTER_SIZE - 4;

// `compute_crc` slices `as_bytes()` by `SECTOR_FOOTER_CRC_COVERAGE`, so a struct
// that grew past the constant would silently leave its new fields unprotected.
const _: () = assert!(core::mem::size_of::<SectorFooter>() == SECTOR_FOOTER_SIZE);

/// A sealed sector's [`SectorSummary`], written into the sector's last page.
///
/// # Why it exists
///
/// Without it, rebuilding the index means reading *every byte of stored data*:
/// on a 2 MB region that is 2 MB over the bus on every boot, and
/// [`MountMode::HeadersOnly`](crate::db::MountMode) avoids it only by giving up
/// queries entirely. A sealed sector that carries its own summary costs **one
/// page read** instead of a full body scan, so a full, queryable mount becomes
/// `O(sector_count)` rather than `O(bytes stored)`.
///
/// The whole summary is stored, not just the timestamp bounds: rebuilding the
/// bloom filter and the entry count is the part that actually forces the body
/// scan.
///
/// # Layout (52 bytes)
///
/// - `magic: [u8; 4]` — [`SECTOR_FOOTER_MAGIC`]
/// - `version: u8` — [`SECTOR_FOOTER_VERSION`]
/// - `reserved: [u8; 3]` — zero
/// - `sequence: u32 LE` — the sequence of the sector this describes
/// - `entry_count: u32 LE`
/// - `sample_count: u32 LE`
/// - `write_offset: u32 LE`
/// - `min_timestamp: u64 LE`
/// - `max_timestamp: u64 LE`
/// - `sensor_bloom: u64 LE`
/// - `footer_crc: u32 LE` — CRC-32C over the preceding 48 bytes
///
/// # Why a whole page, and why the last one
///
/// Writes are page-granular, so the footer costs a page whatever its size. It
/// gets its *own* page rather than sharing the header's so that a torn footer
/// write can damage nothing but the footer: the alternative — reprogramming
/// page 0 with the footer filled into a reserved hole — puts the sector header
/// and the sector's first entries inside the blast radius of a write that
/// happens exactly at power loss, and the sector header is what makes the
/// sector readable at all.
///
/// The cost is `PAGE_SIZE / ERASE_SIZE` of raw capacity — 6.25% at the common
/// 256-byte page / 4 KB sector, 12.5% on a geometry with only eight pages per
/// sector.
///
/// # It is never a correctness dependency
///
/// A footer is written at seal time and read at mount. Anything that does not
/// validate — missing, torn, or describing a different `sequence` — is ignored
/// and the sector's body is scanned exactly as before, which is also what
/// happens to the sector a crashed run left active. The entry CRCs are
/// unaffected: every read still verifies the entry it returns.
#[derive(FromBytes, IntoBytes, KnownLayout, Immutable, Unaligned, Clone, Copy)]
#[repr(C, packed)]
pub struct SectorFooter {
    /// Format magic, always [`SECTOR_FOOTER_MAGIC`].
    pub magic: [u8; 4],
    /// Format version, always [`SECTOR_FOOTER_VERSION`].
    pub version: u8,
    /// Padding to align the fields that follow; written as zero.
    pub reserved: [u8; 3],
    /// Sequence of the sector this footer describes.
    ///
    /// Checked against the sector header before the footer is believed, so a
    /// footer that somehow outlived the data it summarises is rejected.
    pub sequence: U32,
    /// Valid entries in the sector, as counted when it was sealed.
    pub entry_count: U32,
    /// Readable samples in the sector, which exceeds `entry_count` by what its
    /// [runs](crate::run) hold.
    pub sample_count: U32,
    /// Byte after the last byte an entry occupies.
    pub write_offset: U32,
    /// Lowest timestamp in the sector (`u64::MAX` if it holds no entries).
    pub min_timestamp: U64,
    /// Highest *sample* timestamp in the sector (`0` if it holds no entries),
    /// so a run contributes the end of its span.
    pub max_timestamp: U64,
    /// The sector's sensor-ID bloom filter.
    pub sensor_bloom: U64,
    /// CRC-32C over the preceding 48 bytes.
    pub footer_crc: U32,
}

impl SectorFooter {
    /// Build the footer describing `summary`, a sector about to be sealed.
    pub fn new(summary: &SectorSummary) -> Self {
        let mut footer = Self {
            magic: SECTOR_FOOTER_MAGIC,
            version: SECTOR_FOOTER_VERSION,
            reserved: [0; 3],
            sequence: U32::new(summary.sequence),
            entry_count: U32::new(summary.entry_count),
            sample_count: U32::new(summary.sample_count),
            write_offset: U32::new(summary.write_offset),
            min_timestamp: U64::new(summary.min_timestamp),
            max_timestamp: U64::new(summary.max_timestamp),
            sensor_bloom: U64::new(summary.sensor_bloom),
            footer_crc: U32::new(0),
        };
        footer.footer_crc = U32::new(footer.compute_crc());
        footer
    }

    /// Compute the CRC-32C over the footer fields excluding the CRC itself.
    fn compute_crc(&self) -> u32 {
        SECTOR_CRC.checksum(&self.as_bytes()[..SECTOR_FOOTER_CRC_COVERAGE])
    }

    /// Whether this footer is intact *and* describes the sector whose header
    /// carries `sequence`.
    ///
    /// Both halves matter. The CRC says the bytes are a footer this build wrote;
    /// the sequence says they belong to the sector's current incarnation rather
    /// than to one an interrupted erase left partly behind.
    pub fn describes(&self, sequence: u32) -> bool {
        self.magic == SECTOR_FOOTER_MAGIC
            && self.version == SECTOR_FOOTER_VERSION
            && self.sequence.get() == sequence
            && self.footer_crc.get() == self.compute_crc()
    }

    /// Copy this footer's fields into `summary`.
    ///
    /// Leaves `state`, `sequence` and `erase_count` alone: those come from the
    /// sector *header*, which mount has already read and validated.
    pub fn apply_to(&self, summary: &mut SectorSummary) {
        summary.entry_count = self.entry_count.get();
        summary.sample_count = self.sample_count.get();
        summary.write_offset = self.write_offset.get();
        summary.min_timestamp = self.min_timestamp.get();
        summary.max_timestamp = self.max_timestamp.get();
        summary.sensor_bloom = self.sensor_bloom.get();
    }
}