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}