ic_storage/runtime/directory_model/
mod.rs1mod 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#[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)]
49pub struct AllocationId(u64);
50impl AllocationId {
51 #[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 extents: Vec<Extent>,
70}
71
72#[derive(Clone, Debug, Deserialize, Eq, PartialEq, Serialize)]
73struct Image {
74 generation: u64,
75 next_id: u64,
76 next_page: u64,
78 metadata: Vec<Extent>,
80 entries: Vec<Entry>,
81}
82
83#[derive(Debug, thiserror::Error)]
85pub enum Error {
86 #[error("allocation page count overflow")]
89 ArithmeticOverflow,
90 #[error("directory budget exceeded")]
92 Budget,
93 #[error("invalid directory: {0}")]
95 Invalid(&'static str),
96 #[error("allocation already has a live lease")]
98 AlreadyOpen,
99 #[error("access exceeds allocation bounds")]
101 Bounds,
102 #[error("backing already has a live owner")]
104 AlreadyClaimed,
105 #[error("allocation does not exist")]
107 Missing,
108 #[error("prepared directory belongs to a stale generation")]
110 Stale,
111 #[error("backing growth refused")]
113 Growth,
114 #[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 logical_ends: Vec<Vec<u64>>,
126 budget: StorageConfig,
127 data_start: u64,
128}
129
130#[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 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 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 #[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 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;