ic_storage/runtime/directory_model/
mod.rs1#[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#[derive(Clone, Copy, Debug)]
20pub struct StorageConfig {
21 pub allocations: usize,
23 pub extents: usize,
25 pub pages: u64,
27 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#[derive(Clone, Copy, Debug, Deserialize, Eq, Ord, PartialEq, PartialOrd, Serialize)]
44pub struct AllocationId(u64);
45impl AllocationId {
46 #[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 extents: Vec<Extent>,
65}
66
67#[derive(Clone, Debug, Eq, PartialEq)]
68struct Image {
69 generation: u64,
70 next_id: u64,
71 next_page: u64,
73 metadata: Vec<Extent>,
75 entries: Vec<Entry>,
76}
77
78#[derive(Debug, thiserror::Error)]
80pub enum Error {
81 #[error("allocation page count overflow")]
84 ArithmeticOverflow,
85 #[error("directory budget exceeded")]
87 Budget,
88 #[error("invalid directory: {0}")]
90 Invalid(&'static str),
91 #[error("allocation already has a live lease")]
93 AlreadyOpen,
94 #[error("access exceeds allocation bounds")]
96 Bounds,
97 #[error("backing already has a live owner")]
99 AlreadyClaimed,
100 #[error("allocation does not exist")]
102 Missing,
103 #[error("prepared directory belongs to a stale generation")]
105 Stale,
106 #[error("backing growth refused")]
108 Growth,
109 #[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 logical_ends: Vec<Vec<u64>>,
121 budget: StorageConfig,
122 data_start: u64,
123}
124
125#[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 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 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 #[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 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}