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) {
54                return Err(LedgerIntegrityError::DuplicateStableKey {
55                    stable_key: record.stable_key.clone(),
56                });
57            }
58            if !slots.insert(&record.slot) {
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        for generation in self.allocation_history.generations() {
111            validate_runtime_fingerprint(generation.runtime_fingerprint.as_deref())
112                .map_err(LedgerIntegrityError::DiagnosticMetadata)?;
113
114            let expected_generation = previous.map_or(1, |previous| previous + 1);
115            if generation.generation != expected_generation {
116                return Err(LedgerIntegrityError::NonIncreasingGenerationRecords {
117                    generation: generation.generation,
118                });
119            }
120
121            let expected_parent = previous.unwrap_or(0);
122            if generation.parent_generation != expected_parent {
123                return Err(LedgerIntegrityError::BrokenGenerationChain {
124                    generation: generation.generation,
125                    expected_parent,
126                    actual_parent: generation.parent_generation,
127                });
128            }
129
130            previous = Some(generation.generation);
131        }
132
133        // The checked chain contains exactly generations 1..=current_generation.
134        for record in self.allocation_history.records() {
135            validate_known_record_generation(
136                self.current_generation,
137                &record.stable_key,
138                record.first_generation,
139            )?;
140            validate_known_record_generation(
141                self.current_generation,
142                &record.stable_key,
143                record.last_seen_generation,
144            )?;
145            if let AllocationState::Retired {
146                generation: retired_generation,
147            } = record.state
148            {
149                validate_known_record_generation(
150                    self.current_generation,
151                    &record.stable_key,
152                    retired_generation,
153                )?;
154            }
155            for schema in &record.schema_history {
156                validate_known_record_generation(
157                    self.current_generation,
158                    &record.stable_key,
159                    schema.generation,
160                )?;
161            }
162        }
163
164        Ok(())
165    }
166}
167
168fn validate_record_integrity(
169    current_generation: u64,
170    record: &AllocationRecord,
171) -> Result<(), LedgerIntegrityError> {
172    record
173        .stable_key
174        .validate()
175        .map_err(LedgerIntegrityError::InvalidStableKey)?;
176    record
177        .slot
178        .validate()
179        .map_err(LedgerIntegrityError::InvalidSlotDescriptor)?;
180
181    if record.first_generation > record.last_seen_generation {
182        return Err(LedgerIntegrityError::InvalidRecordGenerationOrder {
183            stable_key: record.stable_key.clone(),
184            first_generation: record.first_generation,
185            last_seen_generation: record.last_seen_generation,
186        });
187    }
188    if record.last_seen_generation > current_generation {
189        return Err(LedgerIntegrityError::FutureRecordGeneration {
190            stable_key: record.stable_key.clone(),
191            generation: record.last_seen_generation,
192            current_generation,
193        });
194    }
195
196    match record.state {
197        AllocationState::Retired {
198            generation: retired_generation,
199        } => {
200            if retired_generation < record.first_generation {
201                return Err(LedgerIntegrityError::RetiredBeforeFirstGeneration {
202                    stable_key: record.stable_key.clone(),
203                    first_generation: record.first_generation,
204                    retired_generation,
205                });
206            }
207            if retired_generation > current_generation {
208                return Err(LedgerIntegrityError::FutureRecordGeneration {
209                    stable_key: record.stable_key.clone(),
210                    generation: retired_generation,
211                    current_generation,
212                });
213            }
214            if retired_generation <= record.last_seen_generation {
215                return Err(LedgerIntegrityError::RetirementNotAfterLastSeen {
216                    stable_key: record.stable_key.clone(),
217                    last_seen_generation: record.last_seen_generation,
218                    retired_generation,
219                });
220            }
221        }
222        AllocationState::Reserved | AllocationState::Active => {}
223    }
224
225    validate_schema_history_integrity(current_generation, record)
226}
227
228fn validate_known_record_generation(
229    current_generation: u64,
230    stable_key: &StableKey,
231    generation: u64,
232) -> Result<(), LedgerIntegrityError> {
233    if (1..=current_generation).contains(&generation) {
234        return Ok(());
235    }
236    Err(LedgerIntegrityError::UnknownRecordGeneration {
237        stable_key: stable_key.clone(),
238        generation,
239    })
240}
241
242fn validate_schema_history_integrity(
243    current_generation: u64,
244    record: &AllocationRecord,
245) -> Result<(), LedgerIntegrityError> {
246    if record.schema_history.is_empty() {
247        return Err(LedgerIntegrityError::EmptySchemaHistory {
248            stable_key: record.stable_key.clone(),
249        });
250    }
251
252    let first_schema_generation = record.schema_history[0].generation;
253    if first_schema_generation != record.first_generation {
254        return Err(LedgerIntegrityError::SchemaHistoryStartMismatch {
255            stable_key: record.stable_key.clone(),
256            first_generation: record.first_generation,
257            schema_generation: first_schema_generation,
258        });
259    }
260
261    let mut previous = None;
262    for schema in &record.schema_history {
263        schema
264            .schema
265            .validate()
266            .map_err(|error| LedgerIntegrityError::InvalidSchemaMetadata {
267                stable_key: record.stable_key.clone(),
268                generation: schema.generation,
269                error,
270            })?;
271        if previous.is_some_and(|generation| schema.generation <= generation) {
272            return Err(LedgerIntegrityError::NonIncreasingSchemaHistory {
273                stable_key: record.stable_key.clone(),
274            });
275        }
276        if schema.generation < record.first_generation || schema.generation > current_generation {
277            return Err(LedgerIntegrityError::SchemaHistoryOutOfBounds {
278                stable_key: record.stable_key.clone(),
279                generation: schema.generation,
280            });
281        }
282        if schema.generation > record.last_seen_generation {
283            return Err(LedgerIntegrityError::SchemaHistoryAfterLastSeen {
284                stable_key: record.stable_key.clone(),
285                generation: schema.generation,
286                last_seen_generation: record.last_seen_generation,
287            });
288        }
289        previous = Some(schema.generation);
290    }
291
292    Ok(())
293}
ic_memory/ledger/integrity.rs

ic_memory/ledger/
integrity.rs
