ic_storage/runtime/directory_model/
mod.rs1pub(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#[derive(Clone, Copy, Debug)]
19pub struct StorageConfig {
20 pub allocations: usize,
22 pub extents: usize,
24 pub pages: u64,
26 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#[derive(Clone, Copy, Debug, Deserialize, Eq, Ord, PartialEq, PartialOrd, Serialize)]
53pub struct AllocationId(u64);
54impl AllocationId {
55 #[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 extents: Vec<Extent>,
74}
75
76#[derive(Clone, Debug, Deserialize, Eq, PartialEq, Serialize)]
77struct Image {
78 generation: u64,
79 next_id: u64,
80 next_page: u64,
82 metadata: Vec<Extent>,
84 entries: Vec<Entry>,
85}
86
87#[derive(Debug, thiserror::Error)]
89pub enum Error {
90 #[error("allocation page count overflow")]
93 ArithmeticOverflow,
94 #[error("directory budget exceeded")]
96 Budget,
97 #[error("invalid directory: {0}")]
99 Invalid(&'static str),
100 #[error("allocation already has a live lease")]
102 AlreadyOpen,
103 #[error("access exceeds allocation bounds")]
105 Bounds,
106 #[error("backing already has a live owner")]
108 AlreadyClaimed,
109 #[error("allocation does not exist")]
111 Missing,
112 #[error("prepared directory belongs to a stale generation")]
114 Stale,
115 #[error("backing growth refused")]
117 Growth,
118 #[error("directory owner is poisoned after interrupted backing IO")]
120 Poisoned,
121 #[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 logical_ends: Vec<Vec<u64>>,
133 budget: StorageConfig,
134 data_start: u64,
135}
136
137#[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 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 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 #[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 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;