Skip to main content

ic_storage/runtime/directory_model/
mod.rs

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