Skip to main content

sensor_db/
sector.rs

1//! Sector header and in-RAM sector index.
2
3use crc::{CRC_32_ISCSI, Crc};
4use zerocopy::{
5    FromBytes, Immutable, IntoBytes, KnownLayout, Unaligned,
6    little_endian::{U32, U64},
7};
8
9/// Sector magic bytes: "SD05" (current and only supported format).
10pub const SECTOR_MAGIC: [u8; 4] = *b"SD05";
11
12/// Format version carried in the sector header.
13///
14/// Redundant with the magic today, and kept anyway: with a version byte the
15/// *next* format change can keep the magic and bump this instead, so an old
16/// sector is reported as unsupported rather than silently reclassified as free
17/// and overwritten.
18pub const SECTOR_FORMAT_VERSION: u8 = 5;
19
20/// Size of the sector header in bytes (28, SD05).
21pub const SECTOR_HEADER_SIZE: usize = 28;
22
23/// Byte length of the header fields covered by the header CRC (everything but
24/// the trailing CRC field itself).
25const SECTOR_HEADER_CRC_COVERAGE: usize = SECTOR_HEADER_SIZE - 4;
26
27/// CRC-32C (same algorithm as the entry CRC) used to integrity-check the header.
28const SECTOR_CRC: Crc<u32> = Crc::<u32>::new(&CRC_32_ISCSI);
29
30/// Identity of a logical log.
31///
32/// A database may declare a `LogId`, which is written into every sector header.
33/// This is what lets a device tell *its own* removable medium from someone
34/// else's: mounting a volume whose sectors carry a different id fails with
35/// [`Error::ForeignVolume`](crate::Error::ForeignVolume) instead of treating the
36/// sectors as free space and erasing them.
37///
38/// A replica carries the id of the log it replicates, not an identity of its
39/// own — the medium is a copy of exactly one log.
40///
41/// Backed by `NonZeroU32` so `Option<LogId>` is four bytes and "unset" is
42/// unrepresentable in the typed API. Zero on the wire means *anonymous*, which
43/// matches any configuration.
44#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash, PartialOrd, Ord)]
45#[cfg_attr(feature = "defmt", derive(defmt::Format))]
46pub struct LogId(core::num::NonZeroU32);
47
48impl LogId {
49    /// Create a `LogId` from a raw value. Returns `None` for zero, which is
50    /// reserved to mean "anonymous" on the wire.
51    pub const fn new(raw: u32) -> Option<Self> {
52        match core::num::NonZeroU32::new(raw) {
53            Some(v) => Some(Self(v)),
54            None => None,
55        }
56    }
57
58    /// The raw value, always non-zero.
59    pub const fn get(self) -> u32 {
60        self.0.get()
61    }
62}
63
64/// How a sector's header reads to a database configured with a given [`LogId`].
65#[derive(Debug, Clone, Copy, PartialEq, Eq)]
66#[cfg_attr(feature = "defmt", derive(defmt::Format))]
67pub enum SectorClass {
68    /// A well-formed sector belonging to this log.
69    Valid,
70    /// Not a sector of this format: erased, never written, or foreign data that
71    /// does not parse. Safe to treat as free space.
72    Free,
73    /// A well-formed sector of this format that belongs to a *different* log.
74    ///
75    /// Never treat this as free: erasing it would destroy another device's data.
76    Foreign {
77        /// The `log_id` found on the medium (0 if anonymous).
78        found: u32,
79    },
80    /// A well-formed header of this family with a version this build cannot read.
81    Unsupported {
82        /// The version byte found on the medium.
83        found: u8,
84    },
85}
86
87/// Wire-format sector header for zerocopy serialization.
88///
89/// Layout (28 bytes, SD05):
90/// - `magic: [u8; 4]` — "SD05"
91/// - `version: u8` — [`SECTOR_FORMAT_VERSION`]
92/// - `reserved: [u8; 3]` — zero
93/// - `log_id: u32 LE` — identity of the owning log (0 = anonymous)
94/// - `epoch: u32 LE` — the mount generation that *created this sector*; see
95///   [`SensorDb::epoch`](crate::SensorDb::epoch) for what it can and cannot
96///   distinguish
97/// - `sequence: u32 LE` — monotonic sector counter
98/// - `erase_count: u32 LE` — number of times this sector has been erased
99/// - `header_crc: u32 LE` — CRC-32C over the preceding 24 bytes
100///
101/// The header CRC lets `mount` accept a sector body only when its header is
102/// structurally intact, so stale data that happens to start with the magic bytes
103/// is not mistaken for a valid sector.
104#[derive(FromBytes, IntoBytes, KnownLayout, Immutable, Unaligned, Clone, Copy)]
105#[repr(C, packed)]
106pub struct SectorHeader {
107    /// Format magic, always [`SECTOR_MAGIC`].
108    pub magic: [u8; 4],
109    /// Format version, always [`SECTOR_FORMAT_VERSION`].
110    pub version: u8,
111    /// Padding to align the fields that follow; written as zero.
112    pub reserved: [u8; 3],
113    /// Identity of the owning log; `0` is anonymous. A mismatch aborts the
114    /// mount with [`Error::ForeignVolume`](crate::Error::ForeignVolume).
115    pub log_id: U32,
116    /// The mount generation that created this sector.
117    pub epoch: U32,
118    /// Monotonic sector counter, which is what reconstructs ring order.
119    pub sequence: U32,
120    /// Times this sector has been erased; the wear-levelling input.
121    pub erase_count: U32,
122    /// CRC-32C over the preceding 24 bytes.
123    pub header_crc: U32,
124}
125
126impl SectorHeader {
127    /// Create a new sector header.
128    ///
129    /// The header CRC is computed over every preceding field.
130    pub fn new(log_id: Option<LogId>, epoch: u32, sequence: u32, erase_count: u32) -> Self {
131        let mut header = Self {
132            magic: SECTOR_MAGIC,
133            version: SECTOR_FORMAT_VERSION,
134            reserved: [0; 3],
135            log_id: U32::new(log_id.map_or(0, LogId::get)),
136            epoch: U32::new(epoch),
137            sequence: U32::new(sequence),
138            erase_count: U32::new(erase_count),
139            header_crc: U32::new(0),
140        };
141        header.header_crc = U32::new(header.compute_crc());
142        header
143    }
144
145    /// Compute the CRC-32C over the header fields excluding the CRC itself.
146    fn compute_crc(&self) -> u32 {
147        SECTOR_CRC.checksum(&self.as_bytes()[..SECTOR_HEADER_CRC_COVERAGE])
148    }
149
150    /// Check if this header is a structurally valid sector header of this
151    /// format version: correct magic, known version, and matching header CRC.
152    pub fn is_valid(&self) -> bool {
153        self.magic == SECTOR_MAGIC
154            && self.version == SECTOR_FORMAT_VERSION
155            && self.header_crc.get() == self.compute_crc()
156    }
157
158    /// Classify this header for a database configured with `expected`.
159    ///
160    /// An anonymous database (`expected == None`) accepts any log id, which
161    /// preserves the behaviour of databases that never declare an identity.
162    /// A named database accepts its own id and anonymous media, and rejects
163    /// anything else as [`SectorClass::Foreign`].
164    pub fn classify(&self, expected: Option<LogId>) -> SectorClass {
165        if self.magic != SECTOR_MAGIC || self.header_crc.get() != self.compute_crc() {
166            return SectorClass::Free;
167        }
168        if self.version != SECTOR_FORMAT_VERSION {
169            return SectorClass::Unsupported {
170                found: self.version,
171            };
172        }
173        let found = self.log_id.get();
174        match expected {
175            // Anonymous readers accept anything they can parse.
176            None => SectorClass::Valid,
177            // A named reader accepts its own sectors, and adopts anonymous ones
178            // (a medium formatted before an identity was assigned).
179            Some(id) if found == 0 || found == id.get() => SectorClass::Valid,
180            _ => SectorClass::Foreign { found },
181        }
182    }
183}
184
185/// State of a sector in the ring buffer.
186#[derive(Debug, Clone, Copy, PartialEq, Eq, Default)]
187#[cfg_attr(feature = "defmt", derive(defmt::Format))]
188pub enum SectorState {
189    /// Sector is erased (all 0xFF).
190    #[default]
191    Erased,
192    /// Sector is the current write target.
193    Active,
194    /// Sector is full and sealed (read-only).
195    Sealed,
196}
197
198/// In-RAM summary of a sector for fast queries.
199#[derive(Debug, Clone, Copy)]
200#[cfg_attr(feature = "defmt", derive(defmt::Format))]
201pub struct SectorSummary {
202    /// Current state of the sector.
203    pub state: SectorState,
204    /// Sequence number from header (0 if erased).
205    pub sequence: u32,
206    /// Number of valid entries in this sector.
207    ///
208    /// *Entries*, not samples: a [run](crate::run) is one entry however many
209    /// samples it holds. This is the unit replication works in — the spooler
210    /// copies entries, and the eviction accounting has to agree with it — so it
211    /// is deliberately not the number a reader sees. That is
212    /// [`sample_count`](Self::sample_count).
213    pub entry_count: u32,
214    /// Number of samples readable from this sector.
215    ///
216    /// Equal to [`entry_count`](Self::entry_count) unless the sector holds
217    /// runs, each of which contributes all of its samples. This is what `count`
218    /// reports and what a query yields, because a run expands transparently.
219    pub sample_count: u32,
220    /// Next write offset within the sector.
221    pub write_offset: u32,
222    /// Minimum timestamp of entries in this sector.
223    pub min_timestamp: u64,
224    /// Maximum timestamp of any *sample* in this sector.
225    ///
226    /// A run reaches past its entry header's timestamp, so it contributes the
227    /// timestamp of its last sample. Keeping this the maximum over samples
228    /// rather than over headers is what lets sector pruning stay exact: a query
229    /// for a run's tail must not skip the sector the run began in.
230    pub max_timestamp: u64,
231    /// Bloom filter bitset of sensor IDs present in this sector.
232    ///
233    /// Each sensor ID is hashed to one of 64 bits using Fibonacci hashing.
234    /// For ≤16 distinct sensors (typical), near-zero false positives.
235    /// No false negatives by construction.
236    pub sensor_bloom: u64,
237    /// Number of times this sector has been erased (from the SD03 header).
238    pub erase_count: u32,
239}
240
241impl Default for SectorSummary {
242    #[allow(clippy::derivable_impls)]
243    fn default() -> Self {
244        Self {
245            state: SectorState::Erased,
246            sequence: 0,
247            entry_count: 0,
248            sample_count: 0,
249            write_offset: 0,
250            min_timestamp: u64::MAX,
251            max_timestamp: 0,
252            sensor_bloom: 0,
253            erase_count: 0,
254        }
255    }
256}
257
258/// Map a sensor ID to a single bit in a 64-bit bloom filter using Fibonacci hashing.
259///
260/// Uses the golden-ratio constant `0x9E3779B9` to spread sensor IDs across 64 bits.
261/// For ≤16 distinct sensors, collisions are near-zero.
262pub fn sensor_id_to_bit(sensor_id: u16) -> u64 {
263    let hash = (sensor_id as u32).wrapping_mul(0x9E37_79B9);
264    1u64 << ((hash >> 26) & 0x3F)
265}
266
267impl SectorSummary {
268    /// Create a new erased sector summary.
269    pub fn erased() -> Self {
270        Self::default()
271    }
272
273    /// Check if a timestamp range overlaps with this sector's entries.
274    pub fn overlaps_time_range(&self, t_start: u64, t_end: u64) -> bool {
275        if self.entry_count == 0 {
276            return false;
277        }
278        // Range [t_start, t_end] overlaps [min, max] if t_start <= max && t_end >= min
279        t_start <= self.max_timestamp && t_end >= self.min_timestamp
280    }
281
282    /// Record a sensor ID in this sector's bloom filter.
283    pub fn record_sensor(&mut self, sensor_id: u16) {
284        self.sensor_bloom |= sensor_id_to_bit(sensor_id);
285    }
286
287    /// Check if this sector might contain entries for a given sensor ID.
288    ///
289    /// Returns `false` only if the sensor is definitely absent (no false negatives).
290    /// May return `true` for absent sensors (false positives possible but rare for ≤16 sensors).
291    pub fn might_contain_sensor(&self, sensor_id: u16) -> bool {
292        self.sensor_bloom & sensor_id_to_bit(sensor_id) != 0
293    }
294
295    /// Widen the sector's bounds to cover an entry spanning `first..=last`.
296    ///
297    /// A single sample passes its timestamp twice; a [run](crate::run) passes
298    /// the timestamps of its first and last samples, which is what keeps
299    /// [`overlaps_time_range`](Self::overlaps_time_range) exact for a query
300    /// aimed at a run's tail.
301    pub fn record_span(&mut self, first: u64, last: u64) {
302        self.update_timestamps(first);
303        self.update_timestamps(last);
304    }
305
306    /// Update timestamp bounds with a new entry.
307    pub fn update_timestamps(&mut self, timestamp: u64) {
308        if timestamp < self.min_timestamp {
309            self.min_timestamp = timestamp;
310        }
311        if timestamp > self.max_timestamp {
312            self.max_timestamp = timestamp;
313        }
314    }
315}
316
317/// Sector footer magic: "SDF2".
318///
319/// `SDF1` differed only in lacking [`sample_count`](SectorFooter::sample_count),
320/// which a sector holding [runs](crate::run) needs. A footer of the old format
321/// fails [`describes`](SectorFooter::describes) and the sector falls back to a
322/// body scan — the same path a torn or absent footer takes — so an existing
323/// medium stays readable and simply loses the fast mount for its sealed sectors.
324pub const SECTOR_FOOTER_MAGIC: [u8; 4] = *b"SDF2";
325
326/// Format version carried in the sector footer.
327pub const SECTOR_FOOTER_VERSION: u8 = 2;
328
329/// Size of the sector footer in bytes (52).
330///
331/// The footer occupies the first bytes of a whole reserved *page* — see
332/// [`SectorFooter`] — so this constant bounds nothing but the struct itself.
333pub const SECTOR_FOOTER_SIZE: usize = 52;
334
335/// Byte length of the footer fields covered by the footer CRC.
336const SECTOR_FOOTER_CRC_COVERAGE: usize = SECTOR_FOOTER_SIZE - 4;
337
338// `compute_crc` slices `as_bytes()` by `SECTOR_FOOTER_CRC_COVERAGE`, so a struct
339// that grew past the constant would silently leave its new fields unprotected.
340const _: () = assert!(core::mem::size_of::<SectorFooter>() == SECTOR_FOOTER_SIZE);
341
342/// A sealed sector's [`SectorSummary`], written into the sector's last page.
343///
344/// # Why it exists
345///
346/// Without it, rebuilding the index means reading *every byte of stored data*:
347/// on a 2 MB region that is 2 MB over the bus on every boot, and
348/// [`MountMode::HeadersOnly`](crate::db::MountMode) avoids it only by giving up
349/// queries entirely. A sealed sector that carries its own summary costs **one
350/// page read** instead of a full body scan, so a full, queryable mount becomes
351/// `O(sector_count)` rather than `O(bytes stored)`.
352///
353/// The whole summary is stored, not just the timestamp bounds: rebuilding the
354/// bloom filter and the entry count is the part that actually forces the body
355/// scan.
356///
357/// # Layout (52 bytes)
358///
359/// - `magic: [u8; 4]` — [`SECTOR_FOOTER_MAGIC`]
360/// - `version: u8` — [`SECTOR_FOOTER_VERSION`]
361/// - `reserved: [u8; 3]` — zero
362/// - `sequence: u32 LE` — the sequence of the sector this describes
363/// - `entry_count: u32 LE`
364/// - `sample_count: u32 LE`
365/// - `write_offset: u32 LE`
366/// - `min_timestamp: u64 LE`
367/// - `max_timestamp: u64 LE`
368/// - `sensor_bloom: u64 LE`
369/// - `footer_crc: u32 LE` — CRC-32C over the preceding 48 bytes
370///
371/// # Why a whole page, and why the last one
372///
373/// Writes are page-granular, so the footer costs a page whatever its size. It
374/// gets its *own* page rather than sharing the header's so that a torn footer
375/// write can damage nothing but the footer: the alternative — reprogramming
376/// page 0 with the footer filled into a reserved hole — puts the sector header
377/// and the sector's first entries inside the blast radius of a write that
378/// happens exactly at power loss, and the sector header is what makes the
379/// sector readable at all.
380///
381/// The cost is `PAGE_SIZE / ERASE_SIZE` of raw capacity — 6.25% at the common
382/// 256-byte page / 4 KB sector, 12.5% on a geometry with only eight pages per
383/// sector.
384///
385/// # It is never a correctness dependency
386///
387/// A footer is written at seal time and read at mount. Anything that does not
388/// validate — missing, torn, or describing a different `sequence` — is ignored
389/// and the sector's body is scanned exactly as before, which is also what
390/// happens to the sector a crashed run left active. The entry CRCs are
391/// unaffected: every read still verifies the entry it returns.
392#[derive(FromBytes, IntoBytes, KnownLayout, Immutable, Unaligned, Clone, Copy)]
393#[repr(C, packed)]
394pub struct SectorFooter {
395    /// Format magic, always [`SECTOR_FOOTER_MAGIC`].
396    pub magic: [u8; 4],
397    /// Format version, always [`SECTOR_FOOTER_VERSION`].
398    pub version: u8,
399    /// Padding to align the fields that follow; written as zero.
400    pub reserved: [u8; 3],
401    /// Sequence of the sector this footer describes.
402    ///
403    /// Checked against the sector header before the footer is believed, so a
404    /// footer that somehow outlived the data it summarises is rejected.
405    pub sequence: U32,
406    /// Valid entries in the sector, as counted when it was sealed.
407    pub entry_count: U32,
408    /// Readable samples in the sector, which exceeds `entry_count` by what its
409    /// [runs](crate::run) hold.
410    pub sample_count: U32,
411    /// Byte after the last byte an entry occupies.
412    pub write_offset: U32,
413    /// Lowest timestamp in the sector (`u64::MAX` if it holds no entries).
414    pub min_timestamp: U64,
415    /// Highest *sample* timestamp in the sector (`0` if it holds no entries),
416    /// so a run contributes the end of its span.
417    pub max_timestamp: U64,
418    /// The sector's sensor-ID bloom filter.
419    pub sensor_bloom: U64,
420    /// CRC-32C over the preceding 48 bytes.
421    pub footer_crc: U32,
422}
423
424impl SectorFooter {
425    /// Build the footer describing `summary`, a sector about to be sealed.
426    pub fn new(summary: &SectorSummary) -> Self {
427        let mut footer = Self {
428            magic: SECTOR_FOOTER_MAGIC,
429            version: SECTOR_FOOTER_VERSION,
430            reserved: [0; 3],
431            sequence: U32::new(summary.sequence),
432            entry_count: U32::new(summary.entry_count),
433            sample_count: U32::new(summary.sample_count),
434            write_offset: U32::new(summary.write_offset),
435            min_timestamp: U64::new(summary.min_timestamp),
436            max_timestamp: U64::new(summary.max_timestamp),
437            sensor_bloom: U64::new(summary.sensor_bloom),
438            footer_crc: U32::new(0),
439        };
440        footer.footer_crc = U32::new(footer.compute_crc());
441        footer
442    }
443
444    /// Compute the CRC-32C over the footer fields excluding the CRC itself.
445    fn compute_crc(&self) -> u32 {
446        SECTOR_CRC.checksum(&self.as_bytes()[..SECTOR_FOOTER_CRC_COVERAGE])
447    }
448
449    /// Whether this footer is intact *and* describes the sector whose header
450    /// carries `sequence`.
451    ///
452    /// Both halves matter. The CRC says the bytes are a footer this build wrote;
453    /// the sequence says they belong to the sector's current incarnation rather
454    /// than to one an interrupted erase left partly behind.
455    pub fn describes(&self, sequence: u32) -> bool {
456        self.magic == SECTOR_FOOTER_MAGIC
457            && self.version == SECTOR_FOOTER_VERSION
458            && self.sequence.get() == sequence
459            && self.footer_crc.get() == self.compute_crc()
460    }
461
462    /// Copy this footer's fields into `summary`.
463    ///
464    /// Leaves `state`, `sequence` and `erase_count` alone: those come from the
465    /// sector *header*, which mount has already read and validated.
466    pub fn apply_to(&self, summary: &mut SectorSummary) {
467        summary.entry_count = self.entry_count.get();
468        summary.sample_count = self.sample_count.get();
469        summary.write_offset = self.write_offset.get();
470        summary.min_timestamp = self.min_timestamp.get();
471        summary.max_timestamp = self.max_timestamp.get();
472        summary.sensor_bloom = self.sensor_bloom.get();
473    }
474}