Skip to main content

ic_storage/runtime/directory_model/
mod.rs

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