Skip to main content

ic_storage/runtime/directory_model/
mod.rs

1//! Owned named-allocation directory and durable extent validation.
2
3#[cfg(test)]
4mod tests;
5
6mod format;
7pub(super) mod leases;
8mod persistence;
9
10use crate::{StableKey, hash};
11use serde::{Deserialize, Serialize};
12use std::collections::{BTreeMap, BTreeSet};
13
14const MAX_METADATA_ARENAS: usize = 128;
15const FRAME: &[u8] = b"ICDIRS02";
16
17/// Resource ceilings checked when creating, opening and extending the directory.
18/// Physical page accounting includes retained metadata and abandoned tails.
19#[derive(Clone, Copy, Debug)]
20pub struct StorageConfig {
21    /// Maximum retained named allocations, including currently omitted names.
22    pub allocations: usize,
23    /// Maximum total data extents across every allocation.
24    pub extents: usize,
25    /// Maximum physical backing extent, in 64 KiB Wasm pages.
26    pub pages: u64,
27    /// Encoding and decoding budgets for each directory snapshot.
28    pub directory_bytes: usize,
29}
30
31impl Default for StorageConfig {
32    fn default() -> Self {
33        Self {
34            allocations: 4_096,
35            extents: 16_384,
36            pages: 1_048_576,
37            directory_bytes: 4 * 1024 * 1024,
38        }
39    }
40}
41
42/// Opaque durable identity assigned by the directory. It grants no access.
43#[derive(Clone, Copy, Debug, Deserialize, Eq, Ord, PartialEq, PartialOrd, Serialize)]
44pub struct AllocationId(u64);
45impl AllocationId {
46    /// Opaque diagnostic identity; callers cannot choose an allocation ID.
47    #[must_use]
48    pub const fn get(self) -> u64 {
49        self.0
50    }
51}
52
53#[derive(Clone, Debug, Eq, PartialEq)]
54struct Extent {
55    start: u64,
56    pub pages: u64,
57}
58
59#[derive(Clone, Debug, Eq, PartialEq)]
60struct Entry {
61    id: AllocationId,
62    key: StableKey,
63    // Logical page order is explicit; physical ranges need not be contiguous.
64    extents: Vec<Extent>,
65}
66
67#[derive(Clone, Debug, Eq, PartialEq)]
68struct Image {
69    generation: u64,
70    next_id: u64,
71    // High-water mark, including space reserved for directory persistence.
72    next_page: u64,
73    // Reserved snapshot arenas, including the active arena. Never application data.
74    metadata: Vec<Extent>,
75    entries: Vec<Entry>,
76}
77
78/// Directory validation, custody and backing failures.
79#[derive(Debug, thiserror::Error)]
80pub enum Error {
81    /// Logical page count overflowed before any backing access.
82    /// allocation page count overflow.
83    #[error("allocation page count overflow")]
84    ArithmeticOverflow,
85    /// directory budget exceeded.
86    #[error("directory budget exceeded")]
87    Budget,
88    /// invalid directory: {0}.
89    #[error("invalid directory: {0}")]
90    Invalid(&'static str),
91    /// allocation already has a live lease.
92    #[error("allocation already has a live lease")]
93    AlreadyOpen,
94    /// access exceeds allocation bounds.
95    #[error("access exceeds allocation bounds")]
96    Bounds,
97    /// backing already has a live owner.
98    #[error("backing already has a live owner")]
99    AlreadyClaimed,
100    /// allocation does not exist.
101    #[error("allocation does not exist")]
102    Missing,
103    /// prepared directory belongs to a stale generation.
104    #[error("prepared directory belongs to a stale generation")]
105    Stale,
106    /// backing growth refused.
107    #[error("backing growth refused")]
108    Growth,
109    /// directory owner is poisoned after interrupted backing IO.
110    #[error("directory owner is poisoned after interrupted backing IO")]
111    Poisoned,
112}
113
114#[derive(Clone, Debug)]
115struct Directory {
116    image: Image,
117    by_key: BTreeMap<StableKey, AllocationId>,
118    by_id: BTreeMap<AllocationId, usize>,
119    // Derived only from validated extents; never persisted as a second authority.
120    logical_ends: Vec<Vec<u64>>,
121    budget: StorageConfig,
122    data_start: u64,
123}
124
125// A candidate owns all tentative changes. Preparation never mutates its base.
126#[derive(Debug)]
127struct Prepared {
128    base: Image,
129    candidate: Directory,
130}
131
132impl Directory {
133    fn empty(budget: StorageConfig, data_start: u64) -> Result<Self, Error> {
134        Self::validate(
135            Image {
136                generation: 0,
137                next_id: 1,
138                next_page: data_start,
139                metadata: vec![],
140                entries: vec![],
141            },
142            budget,
143            data_start,
144        )
145    }
146
147    fn validate(image: Image, budget: StorageConfig, data_start: u64) -> Result<Self, Error> {
148        if image.entries.len() > budget.allocations || image.next_page > budget.pages {
149            return Err(Error::Budget);
150        }
151        if data_start == 0 || image.next_page < data_start || image.next_id == 0 {
152            return Err(Error::Invalid("root boundary or identity watermark"));
153        }
154        let mut by_key = BTreeMap::new();
155        let mut by_id = BTreeMap::new();
156        if image.metadata.len() > MAX_METADATA_ARENAS {
157            return Err(Error::Budget);
158        }
159        let mut ranges = Vec::new();
160        for extent in &image.metadata {
161            let end = extent
162                .start
163                .checked_add(extent.pages)
164                .ok_or(Error::Budget)?;
165            if extent.pages == 0 || extent.start < data_start || end > image.next_page {
166                return Err(Error::Invalid("metadata arena outside backing"));
167            }
168            ranges.push((extent.start, end));
169        }
170        let mut data_extents = 0;
171        let mut previous = None;
172        for (index, entry) in image.entries.iter().enumerate() {
173            if entry.id.0 == 0
174                || entry.id.0 >= image.next_id
175                || previous.is_some_and(|id| id >= entry.id)
176            {
177                return Err(Error::Invalid("noncanonical allocation identities"));
178            }
179            previous = Some(entry.id);
180            if by_key.insert(entry.key.clone(), entry.id).is_some() {
181                return Err(Error::Invalid("duplicate stable key"));
182            }
183            by_id.insert(entry.id, index);
184            if entry.extents.len() > budget.extents.saturating_sub(data_extents) {
185                return Err(Error::Budget);
186            }
187            data_extents += entry.extents.len();
188            for extent in &entry.extents {
189                let end = extent
190                    .start
191                    .checked_add(extent.pages)
192                    .ok_or(Error::Invalid("extent overflow"))?;
193                if extent.pages == 0 || extent.start < data_start || end > image.next_page {
194                    return Err(Error::Invalid("extent outside data region"));
195                }
196                ranges.push((extent.start, end));
197            }
198        }
199        ranges.sort_unstable();
200        if ranges.windows(2).any(|pair| pair[0].1 > pair[1].0) {
201            return Err(Error::Invalid("overlapping physical extents"));
202        }
203        let logical_ends = image
204            .entries
205            .iter()
206            .map(|entry| {
207                let mut total = 0;
208                entry
209                    .extents
210                    .iter()
211                    .map(|extent| {
212                        // Disjoint ranges fit within the admitted physical watermark.
213                        total += extent.pages;
214                        total
215                    })
216                    .collect()
217            })
218            .collect();
219        Ok(Self {
220            image,
221            by_key,
222            by_id,
223            logical_ends,
224            budget,
225            data_start,
226        })
227    }
228
229    fn decode(bytes: &[u8], budget: StorageConfig, data_start: u64) -> Result<Self, Error> {
230        if bytes.len() > budget.directory_bytes {
231            return Err(Error::Budget);
232        }
233        let payload = bytes
234            .strip_prefix(FRAME)
235            .ok_or(Error::Invalid("directory frame"))?;
236        let image = format::decode(payload, budget)?;
237        Self::validate(image, budget, data_start)
238    }
239
240    fn encode(&self) -> Result<Vec<u8>, Error> {
241        format::encode(&self.image, self.budget.directory_bytes)
242    }
243
244    fn prepare(
245        &self,
246        keys: Vec<StableKey>,
247        growth: &[(AllocationId, u64)],
248    ) -> Result<Prepared, Error> {
249        let mut image = self.image.clone();
250        let keys: BTreeSet<_> = keys.into_iter().collect();
251        for key in keys {
252            if self.by_key.contains_key(&key) {
253                continue;
254            }
255            if image.entries.len() >= self.budget.allocations {
256                return Err(Error::Budget);
257            }
258            let id = AllocationId(image.next_id);
259            image.next_id = image.next_id.checked_add(1).ok_or(Error::Budget)?;
260            image.entries.push(Entry {
261                id,
262                key,
263                extents: vec![],
264            });
265        }
266        for &(id, pages) in growth {
267            // Growth applies only to bindings already present in the base.
268            let index = *self.by_id.get(&id).ok_or(Error::Missing)?;
269            if pages == 0 {
270                continue;
271            }
272            let start = image.next_page;
273            image.next_page = start.checked_add(pages).ok_or(Error::Budget)?;
274            if let Some(last) = image.entries[index].extents.last_mut()
275                && last.start + last.pages == start
276            {
277                last.pages += pages;
278            } else {
279                image.entries[index].extents.push(Extent { start, pages });
280            }
281        }
282        image.generation = image.generation.checked_add(1).ok_or(Error::Budget)?;
283        let candidate = Self::validate(image, self.budget, self.data_start)?;
284        Ok(Prepared {
285            base: self.image.clone(),
286            candidate,
287        })
288    }
289
290    // Model-only publication; durable publication belongs to Store.
291    #[cfg(test)]
292    fn publish(&mut self, prepared: Prepared) -> Result<(), Error> {
293        if self.image != prepared.base || self.data_start != prepared.candidate.data_start {
294            return Err(Error::Stale);
295        }
296        // Re-admit the candidate under this owner's budgets, even when two
297        // owners began from the same image with different local limits.
298        let candidate = Self::validate(prepared.candidate.image, self.budget, self.data_start)?;
299        candidate.encode()?;
300        *self = candidate;
301        Ok(())
302    }
303
304    fn page_span(&self, id: AllocationId, logical: u64) -> Option<(u64, u64)> {
305        let index = *self.by_id.get(&id)?;
306        let ends = &self.logical_ends[index];
307        let slot = ends.partition_point(|&end| end <= logical);
308        let extent = self.image.entries[index].extents.get(slot)?;
309        let start = if slot == 0 { 0 } else { ends[slot - 1] };
310        Some((extent.start + logical - start, ends[slot] - logical))
311    }
312
313    #[cfg(test)]
314    fn page(&self, id: AllocationId, logical: u64) -> Option<u64> {
315        self.page_span(id, logical).map(|(page, _)| page)
316    }
317}