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
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    record
134        .stable_key
135        .validate()
136        .map_err(LedgerIntegrityError::InvalidStableKey)?;
137    record
138        .slot
139        .validate()
140        .map_err(LedgerIntegrityError::InvalidSlotDescriptor)?;
141
142    if record.first_generation > record.last_seen_generation {
143        return Err(LedgerIntegrityError::InvalidRecordGenerationOrder {
144            stable_key: record.stable_key.clone(),
145            first_generation: record.first_generation,
146            last_seen_generation: record.last_seen_generation,
147        });
148    }
149    if record.last_seen_generation > current_generation {
150        return Err(LedgerIntegrityError::FutureRecordGeneration {
151            stable_key: record.stable_key.clone(),
152            generation: record.last_seen_generation,
153            current_generation,
154        });
155    }
156
157    match (record.state, record.retired_generation) {
158        (AllocationState::Retired, Some(retired_generation)) => {
159            if retired_generation < record.first_generation {
160                return Err(LedgerIntegrityError::RetiredBeforeFirstGeneration {
161                    stable_key: record.stable_key.clone(),
162                    first_generation: record.first_generation,
163                    retired_generation,
164                });
165            }
166            if retired_generation > current_generation {
167                return Err(LedgerIntegrityError::FutureRecordGeneration {
168                    stable_key: record.stable_key.clone(),
169                    generation: retired_generation,
170                    current_generation,
171                });
172            }
173        }
174        (AllocationState::Retired, None) => {
175            return Err(LedgerIntegrityError::MissingRetiredGeneration {
176                stable_key: record.stable_key.clone(),
177            });
178        }
179        (AllocationState::Reserved | AllocationState::Active, Some(_)) => {
180            return Err(LedgerIntegrityError::UnexpectedRetiredGeneration {
181                stable_key: record.stable_key.clone(),
182            });
183        }
184        (AllocationState::Reserved | AllocationState::Active, None) => {}
185    }
186
187    validate_schema_history_integrity(current_generation, record)
188}
189
190fn validate_known_record_generation(
191    known_generations: &BTreeSet<u64>,
192    stable_key: &StableKey,
193    generation: u64,
194) -> Result<(), LedgerIntegrityError> {
195    if known_generations.contains(&generation) {
196        return Ok(());
197    }
198    Err(LedgerIntegrityError::UnknownRecordGeneration {
199        stable_key: stable_key.clone(),
200        generation,
201    })
202}
203
204fn validate_schema_history_integrity(
205    current_generation: u64,
206    record: &AllocationRecord,
207) -> Result<(), LedgerIntegrityError> {
208    if record.schema_history.is_empty() {
209        return Err(LedgerIntegrityError::EmptySchemaHistory {
210            stable_key: record.stable_key.clone(),
211        });
212    }
213
214    let mut previous = None;
215    for schema in &record.schema_history {
216        schema
217            .schema
218            .validate()
219            .map_err(|error| LedgerIntegrityError::InvalidSchemaMetadata {
220                stable_key: record.stable_key.clone(),
221                generation: schema.generation,
222                error,
223            })?;
224        if previous.is_some_and(|generation| schema.generation <= generation) {
225            return Err(LedgerIntegrityError::NonIncreasingSchemaHistory {
226                stable_key: record.stable_key.clone(),
227            });
228        }
229        if schema.generation < record.first_generation || schema.generation > current_generation {
230            return Err(LedgerIntegrityError::SchemaHistoryOutOfBounds {
231                stable_key: record.stable_key.clone(),
232                generation: schema.generation,
233            });
234        }
235        previous = Some(schema.generation);
236    }
237
238    Ok(())
239}
ic_memory/ledger/integrity.rs

ic_memory/ledger/
integrity.rs
