ic_memory/
physical.rs

1use serde::{Deserialize, Serialize};
2
3const COMMIT_MARKER: u64 = 0x4943_4D45_4D43_4F4D;
4const FNV_OFFSET: u64 = 0xcbf2_9ce4_8422_2325;
5const FNV_PRIME: u64 = 0x0000_0100_0000_01b3;
6
7///
8/// ProtectedGenerationSlot
9///
10/// One physical generation slot that can participate in protected recovery.
11pub trait ProtectedGenerationSlot {
12    /// Generation encoded by this slot.
13    fn generation(&self) -> u64;
14
15    /// Return whether the slot passed its marker/checksum validation.
16    fn validates(&self) -> bool;
17}
18
19///
20/// CommitSlotIndex
21///
22/// Physical dual-slot index selected by protected recovery.
23#[derive(Clone, Copy, Debug, Deserialize, Eq, Ord, PartialEq, PartialOrd, Serialize)]
24pub enum CommitSlotIndex {
25    /// First physical commit slot.
26    Slot0,
27    /// Second physical commit slot.
28    Slot1,
29}
30
31impl CommitSlotIndex {
32    /// Return the opposite physical slot.
33    #[must_use]
34    pub const fn opposite(self) -> Self {
35        match self {
36            Self::Slot0 => Self::Slot1,
37            Self::Slot1 => Self::Slot0,
38        }
39    }
40}
41
42///
43/// AuthoritativeSlot
44///
45/// Highest-generation valid slot selected by protected recovery.
46#[derive(Clone, Copy, Debug, Eq, PartialEq)]
47pub struct AuthoritativeSlot<'slot, T> {
48    /// Physical slot index.
49    pub index: CommitSlotIndex,
50    /// Valid committed generation in that slot.
51    pub record: &'slot T,
52}
53
54/// Select the highest-generation valid physical slot.
55pub fn select_authoritative_slot<'slot, T: ProtectedGenerationSlot>(
56    slot0: Option<&'slot T>,
57    slot1: Option<&'slot T>,
58) -> Result<AuthoritativeSlot<'slot, T>, CommitRecoveryError> {
59    let slot0 = slot0
60        .filter(|slot| slot.validates())
61        .map(|record| AuthoritativeSlot {
62            index: CommitSlotIndex::Slot0,
63            record,
64        });
65    let slot1 = slot1
66        .filter(|slot| slot.validates())
67        .map(|record| AuthoritativeSlot {
68            index: CommitSlotIndex::Slot1,
69            record,
70        });
71
72    match (slot0, slot1) {
73        (Some(left), Some(right)) if right.record.generation() > left.record.generation() => {
74            Ok(right)
75        }
76        (Some(left), Some(_) | None) => Ok(left),
77        (None, Some(right)) => Ok(right),
78        (None, None) => Err(CommitRecoveryError::NoValidGeneration),
79    }
80}
81
82///
83/// CommittedGenerationBytes
84///
85/// Physically committed ledger generation payload protected by a checksum.
86#[derive(Clone, Debug, Deserialize, Eq, PartialEq, Serialize)]
87pub struct CommittedGenerationBytes {
88    /// Generation number represented by this payload.
89    pub generation: u64,
90    /// Physical commit marker. Readers reject records with an invalid marker.
91    pub commit_marker: u64,
92    /// Checksum over the generation, marker, and payload bytes.
93    pub checksum: u64,
94    /// Encoded ledger generation payload.
95    pub payload: Vec<u8>,
96}
97
98impl CommittedGenerationBytes {
99    /// Build a committed generation record.
100    #[must_use]
101    pub fn new(generation: u64, payload: Vec<u8>) -> Self {
102        let mut record = Self {
103            generation,
104            commit_marker: COMMIT_MARKER,
105            checksum: 0,
106            payload,
107        };
108        record.checksum = generation_checksum(&record);
109        record
110    }
111
112    /// Return whether the marker and checksum validate.
113    #[must_use]
114    pub fn validates(&self) -> bool {
115        self.commit_marker == COMMIT_MARKER && self.checksum == generation_checksum(self)
116    }
117}
118
119impl ProtectedGenerationSlot for CommittedGenerationBytes {
120    fn generation(&self) -> u64 {
121        self.generation
122    }
123
124    fn validates(&self) -> bool {
125        self.validates()
126    }
127}
128
129///
130/// DualCommitStore
131///
132/// Dual-slot protected commit protocol for encoded ledger generations.
133///
134/// Writers stage a complete generation record into the inactive slot. Readers
135/// recover by selecting the highest-generation valid slot. A torn or partial
136/// write cannot become authoritative unless its marker and checksum validate.
137#[derive(Clone, Debug, Default, Deserialize, Eq, PartialEq, Serialize)]
138pub struct DualCommitStore {
139    /// First physical commit slot.
140    pub slot0: Option<CommittedGenerationBytes>,
141    /// Second physical commit slot.
142    pub slot1: Option<CommittedGenerationBytes>,
143}
144
145impl DualCommitStore {
146    /// Return true when no commit slot has ever been written.
147    #[must_use]
148    pub const fn is_uninitialized(&self) -> bool {
149        self.slot0.is_none() && self.slot1.is_none()
150    }
151
152    /// Return the highest-generation valid committed record.
153    pub fn authoritative(&self) -> Result<&CommittedGenerationBytes, CommitRecoveryError> {
154        select_authoritative_slot(self.slot0.as_ref(), self.slot1.as_ref())
155            .map(|authoritative| authoritative.record)
156    }
157
158    /// Build a read-only recovery diagnostic for the protected commit slots.
159    #[must_use]
160    pub fn diagnostic(&self) -> CommitStoreDiagnostic {
161        let authoritative = self.authoritative();
162        CommitStoreDiagnostic {
163            slot0: CommitSlotDiagnostic::from_slot(self.slot0.as_ref()),
164            slot1: CommitSlotDiagnostic::from_slot(self.slot1.as_ref()),
165            authoritative_generation: authoritative.ok().map(|record| record.generation),
166            recovery_error: authoritative.err(),
167        }
168    }
169
170    /// Commit a new payload to the inactive slot.
171    ///
172    /// The returned store models the post-write physical state. If a real
173    /// substrate traps before the inactive slot is fully written, the prior
174    /// valid slot remains authoritative under `authoritative`.
175    pub fn commit_payload(
176        &mut self,
177        payload: Vec<u8>,
178    ) -> Result<&CommittedGenerationBytes, CommitRecoveryError> {
179        let next_generation = self
180            .authoritative()
181            .map_or(0, |record| record.generation.saturating_add(1));
182        let next = CommittedGenerationBytes::new(next_generation, payload);
183
184        if self.inactive_slot_index() == 0 {
185            self.slot0 = Some(next);
186        } else {
187            self.slot1 = Some(next);
188        }
189
190        self.authoritative()
191    }
192
193    /// Simulate a torn write into the inactive slot.
194    ///
195    /// This helper is intentionally part of the model because recovery behavior
196    /// is an ABI requirement, not an implementation detail.
197    pub fn write_corrupt_inactive_slot(&mut self, generation: u64, payload: Vec<u8>) {
198        let mut corrupt = CommittedGenerationBytes::new(generation, payload);
199        corrupt.checksum = corrupt.checksum.wrapping_add(1);
200
201        if self.inactive_slot_index() == 0 {
202            self.slot0 = Some(corrupt);
203        } else {
204            self.slot1 = Some(corrupt);
205        }
206    }
207
208    fn inactive_slot_index(&self) -> u8 {
209        match select_authoritative_slot(self.slot0.as_ref(), self.slot1.as_ref()) {
210            Ok(authoritative) if authoritative.index == CommitSlotIndex::Slot0 => 1,
211            Ok(_) | Err(_) => 0,
212        }
213    }
214}
215
216///
217/// CommitStoreDiagnostic
218///
219/// Read-only diagnostic summary of protected commit recovery state.
220#[derive(Clone, Copy, Debug, Deserialize, Eq, PartialEq, Serialize)]
221pub struct CommitStoreDiagnostic {
222    /// First physical commit slot diagnostic.
223    pub slot0: CommitSlotDiagnostic,
224    /// Second physical commit slot diagnostic.
225    pub slot1: CommitSlotDiagnostic,
226    /// Highest valid generation selected by recovery.
227    pub authoritative_generation: Option<u64>,
228    /// Recovery error when no authoritative generation can be selected.
229    pub recovery_error: Option<CommitRecoveryError>,
230}
231
232///
233/// CommitSlotDiagnostic
234///
235/// Read-only diagnostic summary for one protected commit slot.
236#[derive(Clone, Copy, Debug, Deserialize, Eq, PartialEq, Serialize)]
237pub struct CommitSlotDiagnostic {
238    /// Whether a physical slot record is present.
239    pub present: bool,
240    /// Generation encoded by the slot, if present.
241    pub generation: Option<u64>,
242    /// Whether marker and checksum validation succeeded.
243    pub valid: bool,
244}
245
246impl CommitSlotDiagnostic {
247    fn from_slot(slot: Option<&CommittedGenerationBytes>) -> Self {
248        match slot {
249            Some(record) => Self {
250                present: true,
251                generation: Some(record.generation),
252                valid: record.validates(),
253            },
254            None => Self {
255                present: false,
256                generation: None,
257                valid: false,
258            },
259        }
260    }
261}
262
263///
264/// CommitRecoveryError
265///
266/// Protected commit recovery failure.
267#[derive(Clone, Copy, Debug, Deserialize, Eq, thiserror::Error, PartialEq, Serialize)]
268pub enum CommitRecoveryError {
269    /// No committed slot passed marker and checksum validation.
270    #[error("no valid committed ledger generation")]
271    NoValidGeneration,
272}
273
274fn generation_checksum(generation: &CommittedGenerationBytes) -> u64 {
275    let mut hash = FNV_OFFSET;
276    hash = hash_u64(hash, generation.generation);
277    hash = hash_u64(hash, generation.commit_marker);
278    hash = hash_usize(hash, generation.payload.len());
279    for byte in &generation.payload {
280        hash = hash_byte(hash, *byte);
281    }
282    hash
283}
284
285fn hash_usize(hash: u64, value: usize) -> u64 {
286    hash_u64(hash, value as u64)
287}
288
289fn hash_u64(mut hash: u64, value: u64) -> u64 {
290    for byte in value.to_le_bytes() {
291        hash = hash_byte(hash, byte);
292    }
293    hash
294}
295
296const fn hash_byte(hash: u64, byte: u8) -> u64 {
297    (hash ^ byte as u64).wrapping_mul(FNV_PRIME)
298}
299
300#[cfg(test)]
301mod tests {
302    use super::*;
303
304    fn payload(value: u8) -> Vec<u8> {
305        vec![value; 4]
306    }
307
308    #[test]
309    fn committed_generation_validates_marker_and_checksum() {
310        let mut generation = CommittedGenerationBytes::new(7, payload(1));
311        assert!(generation.validates());
312
313        generation.checksum = generation.checksum.wrapping_add(1);
314        assert!(!generation.validates());
315    }
316
317    #[test]
318    fn authoritative_selects_highest_valid_generation() {
319        let mut store = DualCommitStore::default();
320        store.commit_payload(payload(1)).expect("first commit");
321        store.commit_payload(payload(2)).expect("second commit");
322
323        let authoritative = store.authoritative().expect("authoritative");
324        let authoritative_slot =
325            select_authoritative_slot(store.slot0.as_ref(), store.slot1.as_ref())
326                .expect("authoritative slot");
327
328        assert_eq!(authoritative.generation, 1);
329        assert_eq!(authoritative.payload, payload(2));
330        assert_eq!(authoritative_slot.index, CommitSlotIndex::Slot1);
331        assert_eq!(authoritative_slot.record.payload, payload(2));
332    }
333
334    #[test]
335    fn corrupt_newer_slot_leaves_prior_generation_authoritative() {
336        let mut store = DualCommitStore::default();
337        store.commit_payload(payload(1)).expect("first commit");
338        store.write_corrupt_inactive_slot(1, payload(2));
339
340        let authoritative = store.authoritative().expect("authoritative");
341
342        assert_eq!(authoritative.generation, 0);
343        assert_eq!(authoritative.payload, payload(1));
344    }
345
346    #[test]
347    fn no_valid_generation_fails_closed() {
348        let mut store = DualCommitStore::default();
349        store.write_corrupt_inactive_slot(0, payload(1));
350        store.write_corrupt_inactive_slot(1, payload(2));
351
352        let err = store.authoritative().expect_err("no valid slot");
353
354        assert_eq!(err, CommitRecoveryError::NoValidGeneration);
355    }
356
357    #[test]
358    fn diagnostic_reports_authoritative_generation_and_corrupt_slots() {
359        let mut store = DualCommitStore::default();
360        store.commit_payload(payload(1)).expect("first commit");
361        store.write_corrupt_inactive_slot(1, payload(2));
362
363        let diagnostic = store.diagnostic();
364
365        assert_eq!(diagnostic.authoritative_generation, Some(0));
366        assert_eq!(diagnostic.recovery_error, None);
367        assert_eq!(diagnostic.slot0.generation, Some(0));
368        assert!(diagnostic.slot0.valid);
369        assert_eq!(diagnostic.slot1.generation, Some(1));
370        assert!(!diagnostic.slot1.valid);
371    }
372
373    #[test]
374    fn diagnostic_reports_no_valid_generation_for_empty_store() {
375        let diagnostic = DualCommitStore::default().diagnostic();
376
377        assert_eq!(diagnostic.authoritative_generation, None);
378        assert_eq!(
379            diagnostic.recovery_error,
380            Some(CommitRecoveryError::NoValidGeneration)
381        );
382        assert!(!diagnostic.slot0.present);
383        assert!(!diagnostic.slot1.present);
384    }
385
386    #[test]
387    fn uninitialized_distinguishes_empty_from_corrupt() {
388        let mut store = DualCommitStore::default();
389        assert!(store.is_uninitialized());
390
391        store.write_corrupt_inactive_slot(0, payload(1));
392
393        assert!(!store.is_uninitialized());
394    }
395
396    #[test]
397    fn commit_after_corrupt_slot_advances_from_prior_valid_generation() {
398        let mut store = DualCommitStore::default();
399        store.commit_payload(payload(1)).expect("first commit");
400        store.write_corrupt_inactive_slot(1, payload(2));
401        store.commit_payload(payload(3)).expect("third commit");
402
403        let authoritative = store.authoritative().expect("authoritative");
404
405        assert_eq!(authoritative.generation, 1);
406        assert_eq!(authoritative.payload, payload(3));
407    }
408}
ic_memory/physical.rs

ic_memory/
physical.rs
