ic_memory/ledger/
integrity.rs

1use super::{AllocationLedger, AllocationRecord, AllocationState, LedgerIntegrityError};
2use crate::{declaration::validate_runtime_fingerprint, key::StableKey, validation::Validate};
3use std::collections::BTreeSet;
4
5impl AllocationLedger {
6    /// Validate structural ledger invariants before recovery or commit.
7    pub fn validate_integrity(&self) -> Result<(), LedgerIntegrityError> {
8        let mut stable_keys = BTreeSet::new();
9        let mut slots = BTreeSet::new();
10
11        for record in self.allocation_history.records() {
12            if !stable_keys.insert(record.stable_key.clone()) {
13                return Err(LedgerIntegrityError::DuplicateStableKey {
14                    stable_key: record.stable_key.clone(),
15                });
16            }
17            if !slots.insert(record.slot.clone()) {
18                return Err(LedgerIntegrityError::DuplicateSlot {
19                    slot: Box::new(record.slot.clone()),
20                });
21            }
22            validate_record_integrity(self.current_generation, record)?;
23        }
24
25        let mut generations = BTreeSet::new();
26        for generation in self.allocation_history.generations() {
27            if !generations.insert(generation.generation) {
28                return Err(LedgerIntegrityError::DuplicateGeneration {
29                    generation: generation.generation,
30                });
31            }
32            if generation.generation > self.current_generation {
33                return Err(LedgerIntegrityError::FutureGeneration {
34                    generation: generation.generation,
35                    current_generation: self.current_generation,
36                });
37            }
38            if generation.parent_generation >= generation.generation {
39                return Err(LedgerIntegrityError::InvalidParentGeneration {
40                    generation: generation.generation,
41                    parent_generation: generation.parent_generation,
42                });
43            }
44        }
45
46        Ok(())
47    }
48
49    /// Validate strict committed-ledger invariants before recovery or commit.
50    ///
51    /// Public durable structs are DTOs: decoded or manually constructed values
52    /// are untrusted until this method succeeds.
53    pub fn validate_committed_integrity(&self) -> Result<(), LedgerIntegrityError> {
54        self.validate_integrity()?;
55
56        if self.current_generation != 0
57            && !self
58                .allocation_history
59                .generations()
60                .iter()
61                .any(|record| record.generation == self.current_generation)
62        {
63            return Err(LedgerIntegrityError::MissingCurrentGenerationRecord {
64                current_generation: self.current_generation,
65            });
66        }
67
68        let mut previous = None;
69        let mut known_generations = BTreeSet::new();
70        for generation in self.allocation_history.generations() {
71            validate_runtime_fingerprint(generation.runtime_fingerprint.as_deref())
72                .map_err(LedgerIntegrityError::DiagnosticMetadata)?;
73
74            let expected_generation = previous.map_or(1, |previous| previous + 1);
75            if generation.generation != expected_generation {
76                return Err(LedgerIntegrityError::NonIncreasingGenerationRecords {
77                    generation: generation.generation,
78                });
79            }
80
81            let expected_parent = previous.unwrap_or(0);
82            if generation.parent_generation != expected_parent {
83                return Err(LedgerIntegrityError::BrokenGenerationChain {
84                    generation: generation.generation,
85                    expected_parent,
86                    actual_parent: generation.parent_generation,
87                });
88            }
89
90            known_generations.insert(generation.generation);
91            previous = Some(generation.generation);
92        }
93
94        for record in self.allocation_history.records() {
95            validate_known_record_generation(
96                &known_generations,
97                &record.stable_key,
98                record.first_generation,
99            )?;
100            validate_known_record_generation(
101                &known_generations,
102                &record.stable_key,
103                record.last_seen_generation,
104            )?;
105            if let Some(retired_generation) = record.retired_generation {
106                validate_known_record_generation(
107                    &known_generations,
108                    &record.stable_key,
109                    retired_generation,
110                )?;
111            }
112            for schema in &record.schema_history {
113                validate_known_record_generation(
114                    &known_generations,
115                    &record.stable_key,
116                    schema.generation,
117                )?;
118            }
119        }
120
121        Ok(())
122    }
123}
124
125fn validate_record_integrity(
126    current_generation: u64,
127    record: &AllocationRecord,
128) -> Result<(), LedgerIntegrityError> {
129    record
130        .stable_key
131        .validate()
132        .map_err(LedgerIntegrityError::InvalidStableKey)?;
133    record
134        .slot
135        .validate()
136        .map_err(LedgerIntegrityError::InvalidSlotDescriptor)?;
137
138    if record.first_generation > record.last_seen_generation {
139        return Err(LedgerIntegrityError::InvalidRecordGenerationOrder {
140            stable_key: record.stable_key.clone(),
141            first_generation: record.first_generation,
142            last_seen_generation: record.last_seen_generation,
143        });
144    }
145    if record.last_seen_generation > current_generation {
146        return Err(LedgerIntegrityError::FutureRecordGeneration {
147            stable_key: record.stable_key.clone(),
148            generation: record.last_seen_generation,
149            current_generation,
150        });
151    }
152
153    match (record.state, record.retired_generation) {
154        (AllocationState::Retired, Some(retired_generation)) => {
155            if retired_generation < record.first_generation {
156                return Err(LedgerIntegrityError::RetiredBeforeFirstGeneration {
157                    stable_key: record.stable_key.clone(),
158                    first_generation: record.first_generation,
159                    retired_generation,
160                });
161            }
162            if retired_generation > current_generation {
163                return Err(LedgerIntegrityError::FutureRecordGeneration {
164                    stable_key: record.stable_key.clone(),
165                    generation: retired_generation,
166                    current_generation,
167                });
168            }
169            if retired_generation <= record.last_seen_generation {
170                return Err(LedgerIntegrityError::RetirementNotAfterLastSeen {
171                    stable_key: record.stable_key.clone(),
172                    last_seen_generation: record.last_seen_generation,
173                    retired_generation,
174                });
175            }
176        }
177        (AllocationState::Retired, None) => {
178            return Err(LedgerIntegrityError::MissingRetiredGeneration {
179                stable_key: record.stable_key.clone(),
180            });
181        }
182        (AllocationState::Reserved | AllocationState::Active, Some(_)) => {
183            return Err(LedgerIntegrityError::UnexpectedRetiredGeneration {
184                stable_key: record.stable_key.clone(),
185            });
186        }
187        (AllocationState::Reserved | AllocationState::Active, None) => {}
188    }
189
190    validate_schema_history_integrity(current_generation, record)
191}
192
193fn validate_known_record_generation(
194    known_generations: &BTreeSet<u64>,
195    stable_key: &StableKey,
196    generation: u64,
197) -> Result<(), LedgerIntegrityError> {
198    if known_generations.contains(&generation) {
199        return Ok(());
200    }
201    Err(LedgerIntegrityError::UnknownRecordGeneration {
202        stable_key: stable_key.clone(),
203        generation,
204    })
205}
206
207fn validate_schema_history_integrity(
208    current_generation: u64,
209    record: &AllocationRecord,
210) -> Result<(), LedgerIntegrityError> {
211    if record.schema_history.is_empty() {
212        return Err(LedgerIntegrityError::EmptySchemaHistory {
213            stable_key: record.stable_key.clone(),
214        });
215    }
216
217    let first_schema_generation = record.schema_history[0].generation;
218    if first_schema_generation != record.first_generation {
219        return Err(LedgerIntegrityError::SchemaHistoryStartMismatch {
220            stable_key: record.stable_key.clone(),
221            first_generation: record.first_generation,
222            schema_generation: first_schema_generation,
223        });
224    }
225
226    let mut previous = None;
227    for schema in &record.schema_history {
228        schema
229            .schema
230            .validate()
231            .map_err(|error| LedgerIntegrityError::InvalidSchemaMetadata {
232                stable_key: record.stable_key.clone(),
233                generation: schema.generation,
234                error,
235            })?;
236        if previous.is_some_and(|generation| schema.generation <= generation) {
237            return Err(LedgerIntegrityError::NonIncreasingSchemaHistory {
238                stable_key: record.stable_key.clone(),
239            });
240        }
241        if schema.generation < record.first_generation || schema.generation > current_generation {
242            return Err(LedgerIntegrityError::SchemaHistoryOutOfBounds {
243                stable_key: record.stable_key.clone(),
244                generation: schema.generation,
245            });
246        }
247        if schema.generation > record.last_seen_generation {
248            return Err(LedgerIntegrityError::SchemaHistoryAfterLastSeen {
249                stable_key: record.stable_key.clone(),
250                generation: schema.generation,
251                last_seen_generation: record.last_seen_generation,
252            });
253        }
254        previous = Some(schema.generation);
255    }
256
257    Ok(())
258}
ic_memory/ledger/integrity.rs

ic_memory/ledger/
integrity.rs
