ic_memory/ledger/
integrity.rs

1use super::{AllocationLedger, AllocationRecord, AllocationState, LedgerIntegrityError};
2use crate::{declaration::validate_runtime_fingerprint, key::StableKey};
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
39                .parent_generation
40                .is_some_and(|parent| parent >= generation.generation)
41            {
42                return Err(LedgerIntegrityError::InvalidParentGeneration {
43                    generation: generation.generation,
44                    parent_generation: generation.parent_generation,
45                });
46            }
47        }
48
49        Ok(())
50    }
51
52    /// Validate strict committed-ledger invariants before recovery or commit.
53    ///
54    /// Public durable structs are DTOs: decoded or manually constructed values
55    /// are untrusted until this method succeeds.
56    pub fn validate_committed_integrity(&self) -> Result<(), LedgerIntegrityError> {
57        self.validate_integrity()?;
58
59        if self.current_generation != 0
60            && !self
61                .allocation_history
62                .generations()
63                .iter()
64                .any(|record| record.generation == self.current_generation)
65        {
66            return Err(LedgerIntegrityError::MissingCurrentGenerationRecord {
67                current_generation: self.current_generation,
68            });
69        }
70
71        let mut previous = None;
72        let mut known_generations = BTreeSet::new();
73        for generation in self.allocation_history.generations() {
74            validate_runtime_fingerprint(generation.runtime_fingerprint.as_deref())
75                .map_err(LedgerIntegrityError::DiagnosticMetadata)?;
76
77            let expected_generation = previous.map_or(1, |previous| previous + 1);
78            if generation.generation != expected_generation {
79                return Err(LedgerIntegrityError::NonIncreasingGenerationRecords {
80                    generation: generation.generation,
81                });
82            }
83
84            let expected_parent =
85                previous.or_else(|| (generation.parent_generation == Some(0)).then_some(0));
86            if generation.parent_generation != expected_parent {
87                return Err(LedgerIntegrityError::BrokenGenerationChain {
88                    generation: generation.generation,
89                    expected_parent,
90                    actual_parent: generation.parent_generation,
91                });
92            }
93
94            known_generations.insert(generation.generation);
95            previous = Some(generation.generation);
96        }
97
98        for record in self.allocation_history.records() {
99            validate_known_record_generation(
100                &known_generations,
101                &record.stable_key,
102                record.first_generation,
103            )?;
104            validate_known_record_generation(
105                &known_generations,
106                &record.stable_key,
107                record.last_seen_generation,
108            )?;
109            if let Some(retired_generation) = record.retired_generation {
110                validate_known_record_generation(
111                    &known_generations,
112                    &record.stable_key,
113                    retired_generation,
114                )?;
115            }
116            for schema in &record.schema_history {
117                validate_known_record_generation(
118                    &known_generations,
119                    &record.stable_key,
120                    schema.generation,
121                )?;
122            }
123        }
124
125        Ok(())
126    }
127}
128
129fn validate_record_integrity(
130    current_generation: u64,
131    record: &AllocationRecord,
132) -> Result<(), LedgerIntegrityError> {
133    if record.first_generation > record.last_seen_generation {
134        return Err(LedgerIntegrityError::InvalidRecordGenerationOrder {
135            stable_key: record.stable_key.clone(),
136            first_generation: record.first_generation,
137            last_seen_generation: record.last_seen_generation,
138        });
139    }
140    if record.last_seen_generation > current_generation {
141        return Err(LedgerIntegrityError::FutureRecordGeneration {
142            stable_key: record.stable_key.clone(),
143            generation: record.last_seen_generation,
144            current_generation,
145        });
146    }
147
148    match (record.state, record.retired_generation) {
149        (AllocationState::Retired, Some(retired_generation)) => {
150            if retired_generation < record.first_generation {
151                return Err(LedgerIntegrityError::RetiredBeforeFirstGeneration {
152                    stable_key: record.stable_key.clone(),
153                    first_generation: record.first_generation,
154                    retired_generation,
155                });
156            }
157            if retired_generation > current_generation {
158                return Err(LedgerIntegrityError::FutureRecordGeneration {
159                    stable_key: record.stable_key.clone(),
160                    generation: retired_generation,
161                    current_generation,
162                });
163            }
164        }
165        (AllocationState::Retired, None) => {
166            return Err(LedgerIntegrityError::MissingRetiredGeneration {
167                stable_key: record.stable_key.clone(),
168            });
169        }
170        (AllocationState::Reserved | AllocationState::Active, Some(_)) => {
171            return Err(LedgerIntegrityError::UnexpectedRetiredGeneration {
172                stable_key: record.stable_key.clone(),
173            });
174        }
175        (AllocationState::Reserved | AllocationState::Active, None) => {}
176    }
177
178    validate_schema_history_integrity(current_generation, record)
179}
180
181fn validate_known_record_generation(
182    known_generations: &BTreeSet<u64>,
183    stable_key: &StableKey,
184    generation: u64,
185) -> Result<(), LedgerIntegrityError> {
186    if known_generations.contains(&generation) {
187        return Ok(());
188    }
189    Err(LedgerIntegrityError::UnknownRecordGeneration {
190        stable_key: stable_key.clone(),
191        generation,
192    })
193}
194
195fn validate_schema_history_integrity(
196    current_generation: u64,
197    record: &AllocationRecord,
198) -> Result<(), LedgerIntegrityError> {
199    if record.schema_history.is_empty() {
200        return Err(LedgerIntegrityError::EmptySchemaHistory {
201            stable_key: record.stable_key.clone(),
202        });
203    }
204
205    let mut previous = None;
206    for schema in &record.schema_history {
207        schema
208            .schema
209            .validate()
210            .map_err(|error| LedgerIntegrityError::InvalidSchemaMetadata {
211                stable_key: record.stable_key.clone(),
212                generation: schema.generation,
213                error,
214            })?;
215        if previous.is_some_and(|generation| schema.generation <= generation) {
216            return Err(LedgerIntegrityError::NonIncreasingSchemaHistory {
217                stable_key: record.stable_key.clone(),
218            });
219        }
220        if schema.generation < record.first_generation || schema.generation > current_generation {
221            return Err(LedgerIntegrityError::SchemaHistoryOutOfBounds {
222                stable_key: record.stable_key.clone(),
223                generation: schema.generation,
224            });
225        }
226        previous = Some(schema.generation);
227    }
228
229    Ok(())
230}
ic_memory/ledger/integrity.rs

ic_memory/ledger/
integrity.rs
