acyclic_fs/kernel/
codec.rs

1//! Small fail-closed codec used by every hash-bearing filesystem object.
2
3use thiserror::Error;
4
5#[derive(Clone, Copy, Debug, Eq, PartialEq)]
6pub(crate) enum DecodedPageKind {
7    Leaf,
8    Internal,
9}
10
11#[derive(Clone, Copy, Debug, Eq, PartialEq)]
12pub(crate) struct DecodedPageShape {
13    pub(crate) kind: DecodedPageKind,
14    pub(crate) items: usize,
15    pub(crate) nested_bytes: u64,
16}
17
18/// Allocation and collection bounds for one canonical object decode.
19#[derive(Clone, Copy, Debug, Eq, Hash, Ord, PartialEq, PartialOrd)]
20pub struct DecodeLimits {
21    /// Maximum complete canonical object bytes.
22    pub maximum_object_bytes: u64,
23    /// Maximum bytes in one logical name.
24    pub maximum_name_bytes: u32,
25    /// Maximum entries or children in one page.
26    pub maximum_page_items: u32,
27    /// Maximum canonical bytes in one authenticated index/page object.
28    pub maximum_page_bytes: u32,
29    /// Maximum authenticated page levels followed by one operation.
30    pub maximum_page_height: u16,
31    /// Maximum distinct authenticated pages retained for cycle/alias checks.
32    pub maximum_visited_pages: u32,
33}
34
35impl Default for DecodeLimits {
36    fn default() -> Self {
37        Self {
38            maximum_object_bytes: 64 * 1024 * 1024,
39            maximum_name_bytes: 255,
40            maximum_page_items: 1_024,
41            maximum_page_bytes: 256 * 1024,
42            maximum_page_height: 64,
43            maximum_visited_pages: 4_096,
44        }
45    }
46}
47
48impl DecodeLimits {
49    pub(crate) fn maximum_page_object_bytes(self) -> u64 {
50        self.maximum_object_bytes
51            .min(u64::from(self.maximum_page_bytes))
52    }
53
54    pub(crate) fn page_limits_valid(self, minimum_items: u32) -> bool {
55        self.maximum_page_items >= minimum_items
56            && self.maximum_page_bytes != 0
57            && self.maximum_page_height != 0
58            && self.maximum_visited_pages != 0
59    }
60}
61
62pub(crate) struct Encoder {
63    bytes: Vec<u8>,
64}
65
66impl Encoder {
67    pub(crate) fn new(domain: &[u8], version: u16) -> Self {
68        let mut bytes = Vec::with_capacity(domain.len() + 2);
69        bytes.extend_from_slice(domain);
70        bytes.extend_from_slice(&version.to_le_bytes());
71        Self { bytes }
72    }
73
74    pub(crate) fn with_exact_capacity(
75        domain: &[u8],
76        version: u16,
77        capacity: usize,
78    ) -> Result<Self, CanonicalDecodeError> {
79        let minimum = domain
80            .len()
81            .checked_add(2)
82            .ok_or(CanonicalDecodeError::LengthOverflow)?;
83        if capacity < minimum {
84            return Err(CanonicalDecodeError::LengthOverflow);
85        }
86        let mut bytes = Vec::new();
87        bytes
88            .try_reserve_exact(capacity)
89            .map_err(|_| CanonicalDecodeError::AllocationFailed)?;
90        bytes.extend_from_slice(domain);
91        bytes.extend_from_slice(&version.to_le_bytes());
92        Ok(Self { bytes })
93    }
94
95    pub(crate) fn u8(&mut self, value: u8) {
96        self.bytes.push(value);
97    }
98
99    pub(crate) fn u32(&mut self, value: u32) {
100        self.bytes.extend_from_slice(&value.to_le_bytes());
101    }
102
103    pub(crate) fn u64(&mut self, value: u64) {
104        self.bytes.extend_from_slice(&value.to_le_bytes());
105    }
106
107    pub(crate) fn i64(&mut self, value: i64) {
108        self.bytes.extend_from_slice(&value.to_le_bytes());
109    }
110
111    pub(crate) fn fixed(&mut self, value: &[u8]) {
112        self.bytes.extend_from_slice(value);
113    }
114
115    pub(crate) fn bounded_bytes(&mut self, value: &[u8]) -> Result<(), CanonicalDecodeError> {
116        let length =
117            u32::try_from(value.len()).map_err(|_| CanonicalDecodeError::LengthOverflow)?;
118        self.u32(length);
119        self.fixed(value);
120        Ok(())
121    }
122
123    pub(crate) fn finish(self) -> Vec<u8> {
124        self.bytes
125    }
126}
127
128pub(crate) struct Decoder<'a> {
129    bytes: &'a [u8],
130    cursor: usize,
131}
132
133impl<'a> Decoder<'a> {
134    pub(crate) fn new(
135        bytes: &'a [u8],
136        domain: &[u8],
137        expected_version: u16,
138        maximum_object_bytes: u64,
139    ) -> Result<Self, CanonicalDecodeError> {
140        let observed = u64::try_from(bytes.len()).unwrap_or(u64::MAX);
141        if observed > maximum_object_bytes {
142            return Err(CanonicalDecodeError::ObjectTooLarge {
143                observed,
144                maximum: maximum_object_bytes,
145            });
146        }
147        let header_length = domain
148            .len()
149            .checked_add(2)
150            .ok_or(CanonicalDecodeError::LengthOverflow)?;
151        let domain_prefix = bytes
152            .get(..domain.len())
153            .ok_or(CanonicalDecodeError::WrongDomain)?;
154        if bytes.len() < header_length || domain_prefix != domain {
155            return Err(CanonicalDecodeError::WrongDomain);
156        }
157        let version_bytes: [u8; 2] = bytes
158            .get(domain.len()..header_length)
159            .ok_or(CanonicalDecodeError::Truncated)?
160            .try_into()
161            .map_err(|_| CanonicalDecodeError::Truncated)?;
162        let version = u16::from_le_bytes(version_bytes);
163        if version != expected_version {
164            return Err(CanonicalDecodeError::UnsupportedVersion(version));
165        }
166        Ok(Self {
167            bytes,
168            cursor: header_length,
169        })
170    }
171
172    pub(crate) fn u8(&mut self) -> Result<u8, CanonicalDecodeError> {
173        let value = *self
174            .bytes
175            .get(self.cursor)
176            .ok_or(CanonicalDecodeError::Truncated)?;
177        self.cursor = self
178            .cursor
179            .checked_add(1)
180            .ok_or(CanonicalDecodeError::LengthOverflow)?;
181        Ok(value)
182    }
183
184    pub(crate) fn u32(&mut self) -> Result<u32, CanonicalDecodeError> {
185        let bytes: [u8; 4] = self
186            .take(4)?
187            .try_into()
188            .map_err(|_| CanonicalDecodeError::Truncated)?;
189        Ok(u32::from_le_bytes(bytes))
190    }
191
192    pub(crate) fn u64(&mut self) -> Result<u64, CanonicalDecodeError> {
193        let bytes: [u8; 8] = self
194            .take(8)?
195            .try_into()
196            .map_err(|_| CanonicalDecodeError::Truncated)?;
197        Ok(u64::from_le_bytes(bytes))
198    }
199
200    pub(crate) fn i64(&mut self) -> Result<i64, CanonicalDecodeError> {
201        let bytes: [u8; 8] = self
202            .take(8)?
203            .try_into()
204            .map_err(|_| CanonicalDecodeError::Truncated)?;
205        Ok(i64::from_le_bytes(bytes))
206    }
207
208    pub(crate) fn fixed<const N: usize>(&mut self) -> Result<[u8; N], CanonicalDecodeError> {
209        self.take(N)?
210            .try_into()
211            .map_err(|_| CanonicalDecodeError::Truncated)
212    }
213
214    pub(crate) fn bounded_bytes(&mut self, maximum: u32) -> Result<Vec<u8>, CanonicalDecodeError> {
215        let length = self.u32()?;
216        if length > maximum {
217            return Err(CanonicalDecodeError::FieldTooLarge {
218                observed: length,
219                maximum,
220            });
221        }
222        let length = usize::try_from(length).map_err(|_| CanonicalDecodeError::LengthOverflow)?;
223        let source = self.take(length)?;
224        let mut value = Vec::new();
225        value
226            .try_reserve_exact(length)
227            .map_err(|_| CanonicalDecodeError::AllocationFailed)?;
228        value.extend_from_slice(source);
229        Ok(value)
230    }
231
232    pub(crate) fn skip_bounded_bytes(
233        &mut self,
234        maximum: u32,
235    ) -> Result<usize, CanonicalDecodeError> {
236        let length = self.u32()?;
237        if length > maximum {
238            return Err(CanonicalDecodeError::FieldTooLarge {
239                observed: length,
240                maximum,
241            });
242        }
243        let length = usize::try_from(length).map_err(|_| CanonicalDecodeError::LengthOverflow)?;
244        self.take(length)?;
245        Ok(length)
246    }
247
248    pub(crate) fn take_exact(&mut self, length: usize) -> Result<&'a [u8], CanonicalDecodeError> {
249        self.take(length)
250    }
251
252    fn take(&mut self, length: usize) -> Result<&'a [u8], CanonicalDecodeError> {
253        let end = self
254            .cursor
255            .checked_add(length)
256            .ok_or(CanonicalDecodeError::LengthOverflow)?;
257        let value = self
258            .bytes
259            .get(self.cursor..end)
260            .ok_or(CanonicalDecodeError::Truncated)?;
261        self.cursor = end;
262        Ok(value)
263    }
264
265    pub(crate) fn finish(self) -> Result<(), CanonicalDecodeError> {
266        if self.cursor == self.bytes.len() {
267            Ok(())
268        } else {
269            Err(CanonicalDecodeError::TrailingBytes)
270        }
271    }
272}
273
274/// Fail-closed canonical object decoding failures.
275#[derive(Clone, Debug, Eq, Error, PartialEq)]
276pub enum CanonicalDecodeError {
277    /// Object belongs to another canonical domain.
278    #[error("canonical object domain is invalid")]
279    WrongDomain,
280    /// Object format version is unsupported.
281    #[error("unsupported canonical object version {0}")]
282    UnsupportedVersion(u16),
283    /// Object ended before a declared field was complete.
284    #[error("canonical object is truncated")]
285    Truncated,
286    /// Complete object exceeds the admitted allocation/work bound.
287    #[error("canonical object has {observed} bytes; maximum is {maximum}")]
288    ObjectTooLarge {
289        /// Observed bytes.
290        observed: u64,
291        /// Admitted maximum.
292        maximum: u64,
293    },
294    /// One bounded field exceeds its admitted bytes.
295    #[error("canonical field has {observed} bytes; maximum is {maximum}")]
296    FieldTooLarge {
297        /// Observed bytes or items.
298        observed: u32,
299        /// Admitted maximum.
300        maximum: u32,
301    },
302    /// Length arithmetic cannot be represented safely.
303    #[error("canonical object length overflowed")]
304    LengthOverflow,
305    /// A bounded canonical encoding or decoding allocation failed.
306    #[error("canonical codec allocation failed")]
307    AllocationFailed,
308    /// Canonical object contains bytes after its final field.
309    #[error("canonical object has trailing bytes")]
310    TrailingBytes,
311    /// A field tag is not recognized by this version.
312    #[error("unknown {field} tag {tag}")]
313    UnknownTag {
314        /// Stable field description.
315        field: &'static str,
316        /// Unknown tag.
317        tag: u8,
318    },
319    /// Decoded fields violate a semantic page invariant.
320    #[error("canonical object invariant failed: {0}")]
321    Invariant(String),
322}
323
324#[cfg(test)]
325#[path = "tests/codec.rs"]
326mod tests;
acyclic_fs/kernel/codec.rs

acyclic_fs/kernel/
codec.rs
