ic_storage/runtime/
directory_model.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"ICDIRR01";
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
87impl Image {
88    fn encode(&self, budget: StorageConfig) -> Result<Vec<u8>, Error> {
89        let mut limits = budget.wire;
90        limits.bytes = limits.bytes.checked_sub(FRAME.len()).ok_or(Error::Budget)?;
91        let payload = ic_wire::native::encode(self, limits)?;
92        let mut bytes = Vec::with_capacity(FRAME.len() + payload.len());
93        bytes.extend_from_slice(FRAME);
94        bytes.extend_from_slice(&payload);
95        Ok(bytes)
96    }
97}
98
99#[derive(Debug, thiserror::Error)]
100pub enum Error {
101    /// Logical page count overflowed before any backing access.
102    #[error("allocation page count overflow")]
103    ArithmeticOverflow,
104    #[error("directory budget exceeded")]
105    Budget,
106    #[error("invalid directory: {0}")]
107    Invalid(&'static str),
108    #[error("allocation already has a live lease")]
109    AlreadyOpen,
110    #[error("access exceeds allocation bounds")]
111    Bounds,
112    #[error("backing already has a live owner")]
113    AlreadyClaimed,
114    #[error("allocation does not exist")]
115    Missing,
116    #[error("prepared directory belongs to a stale generation")]
117    Stale,
118    #[error("backing growth refused")]
119    Growth,
120    #[error("directory owner is poisoned after interrupted backing IO")]
121    Poisoned,
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    // Derived only from validated extents; never persisted as a second authority.
131    logical_ends: Vec<Vec<u64>>,
132    budget: StorageConfig,
133}
134
135impl Directory {
136    fn empty(budget: StorageConfig, data_start: u64) -> Result<Self, Error> {
137        Self::validate(
138            Image {
139                generation: 0,
140                next_id: 1,
141                next_page: data_start,
142                metadata: vec![],
143                entries: vec![],
144            },
145            budget,
146            data_start,
147        )
148    }
149
150    fn validate(image: Image, budget: StorageConfig, data_start: u64) -> Result<Self, Error> {
151        if image.entries.len() > budget.allocations || image.next_page > budget.pages {
152            return Err(Error::Budget);
153        }
154        if data_start == 0 || image.next_page < data_start || image.next_id == 0 {
155            return Err(Error::Invalid("root boundary or identity watermark"));
156        }
157        let mut by_key = BTreeMap::new();
158        if image.metadata.len() > 128 {
159            return Err(Error::Budget);
160        }
161        let mut ranges = Vec::new();
162        for extent in &image.metadata {
163            let end = extent
164                .start
165                .checked_add(extent.pages)
166                .ok_or(Error::Budget)?;
167            if extent.pages == 0 || extent.start < data_start || end > image.next_page {
168                return Err(Error::Invalid("metadata arena outside backing"));
169            }
170            ranges.push((extent.start, end));
171        }
172        let mut data_extents = 0;
173        let mut previous = None;
174        for entry in &image.entries {
175            if entry.id.0 == 0
176                || entry.id.0 >= image.next_id
177                || previous.is_some_and(|id| id >= entry.id)
178            {
179                return Err(Error::Invalid("noncanonical allocation identities"));
180            }
181            previous = Some(entry.id);
182            if by_key.insert(entry.key.clone(), entry.id).is_some() {
183                return Err(Error::Invalid("duplicate stable key"));
184            }
185            if entry.extents.len() > budget.extents.saturating_sub(data_extents) {
186                return Err(Error::Budget);
187            }
188            data_extents += entry.extents.len();
189            for extent in &entry.extents {
190                let end = extent
191                    .start
192                    .checked_add(extent.pages)
193                    .ok_or(Error::Invalid("extent overflow"))?;
194                if extent.pages == 0 || extent.start < data_start || end > image.next_page {
195                    return Err(Error::Invalid("extent outside data region"));
196                }
197                ranges.push((extent.start, end));
198            }
199        }
200        ranges.sort_unstable();
201        if ranges.windows(2).any(|pair| pair[0].1 > pair[1].0) {
202            return Err(Error::Invalid("overlapping physical extents"));
203        }
204        let logical_ends = image
205            .entries
206            .iter()
207            .map(|entry| {
208                let mut total = 0;
209                entry
210                    .extents
211                    .iter()
212                    .map(|extent| {
213                        // Disjoint ranges fit within the admitted physical watermark.
214                        total += extent.pages;
215                        total
216                    })
217                    .collect()
218            })
219            .collect();
220        Ok(Self {
221            image,
222            by_key,
223            logical_ends,
224            budget,
225        })
226    }
227
228    // Validation admits strictly increasing opaque IDs, including gaps. The
229    // canonical entries already provide this index; no second heap tree is needed.
230    fn entry_index(&self, id: AllocationId) -> Result<usize, Error> {
231        self.image
232            .entries
233            .binary_search_by_key(&id, |entry| entry.id)
234            .map_err(|_| Error::Missing)
235    }
236
237    fn decode(bytes: &[u8], budget: StorageConfig, data_start: u64) -> Result<Self, Error> {
238        if bytes.len() > budget.wire.bytes {
239            return Err(Error::Budget);
240        }
241        let payload = bytes
242            .strip_prefix(FRAME)
243            .ok_or(Error::Invalid("directory frame"))?;
244        let image = ic_wire::native::decode(payload, budget.wire)?;
245        Self::validate(image, budget, data_start)
246    }
247
248    // Extend the validated base directly; no second indexed Directory is needed
249    // merely to account for a native write's uncommitted physical tail.
250    fn candidate_image(
251        &self,
252        keys: Vec<StableKey>,
253        growth: &[(AllocationId, u64)],
254        physical_end: u64,
255    ) -> Result<Image, Error> {
256        let mut image = self.image.clone();
257        image.next_page = image.next_page.max(physical_end);
258        let keys: BTreeSet<_> = keys.into_iter().collect();
259        for key in keys {
260            if self.by_key.contains_key(&key) {
261                continue;
262            }
263            if image.entries.len() >= self.budget.allocations {
264                return Err(Error::Budget);
265            }
266            let id = AllocationId(image.next_id);
267            image.next_id = image.next_id.checked_add(1).ok_or(Error::Budget)?;
268            image.entries.push(Entry {
269                id,
270                key,
271                extents: vec![],
272            });
273        }
274        for &(id, pages) in growth {
275            // Growth applies only to bindings already present in the base.
276            let index = self.entry_index(id)?;
277            if pages == 0 {
278                continue;
279            }
280            let start = image.next_page;
281            image.next_page = start.checked_add(pages).ok_or(Error::Budget)?;
282            if let Some(last) = image.entries[index].extents.last_mut()
283                && last.start + last.pages == start
284            {
285                last.pages += pages;
286            } else {
287                image.entries[index].extents.push(Extent { start, pages });
288            }
289        }
290        image.generation = image.generation.checked_add(1).ok_or(Error::Budget)?;
291        Ok(image)
292    }
293}
294
295#[cfg(test)]
296mod tests;
ic_storage/runtime/directory_model.rs

ic_storage/runtime/
directory_model.rs
