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

ic_memory/ledger/
integrity.rs
