acyclic_fs/kernel/
attribute.rs

1//! Authenticated scalable named attributes, alternate streams, and resource forks.
2
3use super::codec::{
4    CanonicalDecodeError, DecodeLimits, DecodedPageKind, DecodedPageShape, Decoder, Encoder,
5};
6use super::types::digest_object;
7use crate::storage::{ObjectId, ObjectKind, object_digest};
8use thiserror::Error;
9
10const DOMAIN: &[u8; 8] = b"ACYFSATR";
11const VERSION: u16 = 1;
12
13/// Source semantics of one named metadata payload.
14#[derive(Clone, Copy, Debug, Eq, Ord, PartialEq, PartialOrd)]
15pub enum AttributeClass {
16    /// POSIX extended attribute.
17    PosixXattr,
18    /// Windows alternate data stream.
19    WindowsStream,
20    /// macOS resource fork or Finder metadata stream.
21    MacResourceFork,
22}
23
24impl AttributeClass {
25    const fn tag(self) -> u8 {
26        match self {
27            Self::PosixXattr => 1,
28            Self::WindowsStream => 2,
29            Self::MacResourceFork => 3,
30        }
31    }
32
33    const fn from_tag(tag: u8) -> Result<Self, AttributeError> {
34        match tag {
35            1 => Ok(Self::PosixXattr),
36            2 => Ok(Self::WindowsStream),
37            3 => Ok(Self::MacResourceFork),
38            value => Err(AttributeError::UnknownClass(value)),
39        }
40    }
41}
42
43/// Canonical namespace plus raw, separator-independent attribute name.
44#[derive(Clone, Debug, Eq, Ord, PartialEq, PartialOrd)]
45pub struct AttributeName {
46    class: AttributeClass,
47    bytes: Vec<u8>,
48}
49
50impl AttributeName {
51    /// Validates an exact bounded attribute name.
52    ///
53    /// # Errors
54    ///
55    /// Rejects empty, oversized, or NUL-bearing names.
56    pub fn new(
57        class: AttributeClass,
58        bytes: Vec<u8>,
59        maximum_bytes: u32,
60    ) -> Result<Self, AttributeError> {
61        if bytes.is_empty()
62            || bytes.contains(&0)
63            || u32::try_from(bytes.len()).unwrap_or(u32::MAX) > maximum_bytes
64        {
65            return Err(AttributeError::InvalidName);
66        }
67        Ok(Self { class, bytes })
68    }
69
70    /// Returns source semantics.
71    #[must_use]
72    pub const fn class(&self) -> AttributeClass {
73        self.class
74    }
75
76    /// Borrows exact canonical name bytes.
77    #[must_use]
78    pub fn as_bytes(&self) -> &[u8] {
79        &self.bytes
80    }
81}
82
83/// One named immutable payload.
84#[derive(Clone, Debug, Eq, PartialEq)]
85pub struct AttributeEntry {
86    /// Canonical attribute name.
87    pub name: AttributeName,
88    /// Exact payload bytes.
89    pub value_bytes: u64,
90    /// Authenticated blob-index root.
91    pub value: ObjectId,
92}
93
94/// One lower-bound-to-page attribute-tree child.
95#[derive(Clone, Debug, Eq, PartialEq)]
96pub struct AttributeChild {
97    /// Exact first name in the child subtree.
98    pub first_name: AttributeName,
99    /// Authenticated attribute page.
100    pub page: ObjectId,
101}
102
103/// One authenticated named-attribute B+tree page.
104#[derive(Clone, Debug, Eq, PartialEq)]
105pub enum AttributePage {
106    /// Strictly ordered named values.
107    Leaf(Vec<AttributeEntry>),
108    /// Strictly ordered child lower bounds.
109    Internal(Vec<AttributeChild>),
110}
111
112impl AttributePage {
113    fn validate(&self, maximum_items: u32) -> Result<(), AttributeError> {
114        let count = match self {
115            Self::Leaf(entries) => {
116                if entries
117                    .windows(2)
118                    .any(|pair| matches!(pair, [left, right] if left.name >= right.name))
119                    || entries
120                        .iter()
121                        .any(|entry| entry.value.kind != ObjectKind::Blob)
122                {
123                    return Err(AttributeError::InvalidPage);
124                }
125                entries.len()
126            }
127            Self::Internal(children) => {
128                if children.is_empty()
129                    || children.windows(2).any(
130                        |pair| matches!(pair, [left, right] if left.first_name >= right.first_name),
131                    )
132                    || children
133                        .iter()
134                        .any(|child| child.page.kind != ObjectKind::AttributePage)
135                {
136                    return Err(AttributeError::InvalidPage);
137                }
138                children.len()
139            }
140        };
141        if u32::try_from(count).unwrap_or(u32::MAX) > maximum_items {
142            return Err(AttributeError::TooManyItems);
143        }
144        Ok(())
145    }
146}
147
148/// Encodes one canonical attribute page.
149///
150/// # Errors
151///
152/// Rejects invalid ordering, object classes, names, or item bounds.
153pub fn encode_attribute_page(
154    page: &AttributePage,
155    maximum_items: u32,
156) -> Result<Vec<u8>, CanonicalDecodeError> {
157    match page {
158        AttributePage::Leaf(entries) => encode_attribute_leaf_entries(entries, maximum_items),
159        AttributePage::Internal(children) => encode_attribute_internal_children(
160            children.iter().map(|child| (&child.first_name, child.page)),
161            maximum_items,
162        ),
163    }
164}
165
166pub(crate) fn encode_attribute_leaf_entries(
167    entries: &[AttributeEntry],
168    maximum_items: u32,
169) -> Result<Vec<u8>, CanonicalDecodeError> {
170    validate_leaf_entries(entries, maximum_items)?;
171    let encoded_length = attribute_leaf_page_encoded_length(entries, maximum_items)?;
172    let mut encoder = Encoder::with_exact_capacity(DOMAIN, VERSION, encoded_length)?;
173    encoder.u8(1);
174    encoder.u32(count(entries.len())?);
175    for entry in entries {
176        encode_name(&mut encoder, &entry.name)?;
177        encoder.u64(entry.value_bytes);
178        encoder.fixed(entry.value.digest.as_bytes());
179    }
180    Ok(encoder.finish())
181}
182
183pub(crate) fn encode_attribute_internal_children<'a, I>(
184    children: I,
185    maximum_items: u32,
186) -> Result<Vec<u8>, CanonicalDecodeError>
187where
188    I: Clone + ExactSizeIterator<Item = (&'a AttributeName, ObjectId)>,
189{
190    validate_internal_children(children.clone(), maximum_items)?;
191    let encoded_length = attribute_internal_page_encoded_length(children.clone(), maximum_items)?;
192    let mut encoder = Encoder::with_exact_capacity(DOMAIN, VERSION, encoded_length)?;
193    encoder.u8(2);
194    encoder.u32(count(children.len())?);
195    for (first_name, page) in children {
196        encode_name(&mut encoder, first_name)?;
197        encoder.fixed(page.digest.as_bytes());
198    }
199    Ok(encoder.finish())
200}
201
202pub(crate) fn attribute_leaf_page_encoded_length(
203    entries: &[AttributeEntry],
204    maximum_items: u32,
205) -> Result<usize, CanonicalDecodeError> {
206    if u32::try_from(entries.len()).unwrap_or(u32::MAX) > maximum_items {
207        return Err(CanonicalDecodeError::LengthOverflow);
208    }
209    entries
210        .iter()
211        .try_fold(DOMAIN.len() + 2 + 1 + 4, |bytes, entry| {
212            bytes
213                .checked_add(attribute_leaf_item_encoded_length(entry))
214                .ok_or(CanonicalDecodeError::LengthOverflow)
215        })
216}
217
218pub(crate) fn attribute_internal_page_encoded_length<'a, I>(
219    mut children: I,
220    maximum_items: u32,
221) -> Result<usize, CanonicalDecodeError>
222where
223    I: ExactSizeIterator<Item = (&'a AttributeName, ObjectId)>,
224{
225    if u32::try_from(children.len()).unwrap_or(u32::MAX) > maximum_items {
226        return Err(CanonicalDecodeError::LengthOverflow);
227    }
228    children.try_fold(DOMAIN.len() + 2 + 1 + 4, |bytes, (name, _)| {
229        bytes
230            .checked_add(attribute_internal_item_encoded_length(name))
231            .ok_or(CanonicalDecodeError::LengthOverflow)
232    })
233}
234
235pub(crate) fn attribute_leaf_item_encoded_length(entry: &AttributeEntry) -> usize {
236    1 + 4 + entry.name.as_bytes().len() + 8 + 32
237}
238
239pub(crate) fn attribute_internal_item_encoded_length(name: &AttributeName) -> usize {
240    1 + 4 + name.as_bytes().len() + 32
241}
242
243fn validate_internal_children<'a, I>(
244    children: I,
245    maximum_items: u32,
246) -> Result<(), CanonicalDecodeError>
247where
248    I: ExactSizeIterator<Item = (&'a AttributeName, ObjectId)>,
249{
250    if children.len() == 0 || u32::try_from(children.len()).unwrap_or(u32::MAX) > maximum_items {
251        return Err(invariant(AttributeError::InvalidPage));
252    }
253    let mut prior: Option<&AttributeName> = None;
254    for (name, page) in children {
255        if prior.is_some_and(|prior| prior >= name) || page.kind != ObjectKind::AttributePage {
256            return Err(invariant(AttributeError::InvalidPage));
257        }
258        prior = Some(name);
259    }
260    Ok(())
261}
262
263fn validate_leaf_entries(
264    entries: &[AttributeEntry],
265    maximum_items: u32,
266) -> Result<(), CanonicalDecodeError> {
267    if u32::try_from(entries.len()).unwrap_or(u32::MAX) > maximum_items
268        || entries
269            .windows(2)
270            .any(|pair| matches!(pair, [left, right] if left.name >= right.name))
271        || entries
272            .iter()
273            .any(|entry| entry.value.kind != ObjectKind::Blob)
274    {
275        return Err(invariant(AttributeError::InvalidPage));
276    }
277    Ok(())
278}
279
280pub(crate) fn attribute_page_decode_shape(
281    bytes: &[u8],
282    limits: DecodeLimits,
283) -> Result<DecodedPageShape, CanonicalDecodeError> {
284    let mut decoder = Decoder::new(bytes, DOMAIN, VERSION, limits.maximum_page_object_bytes())?;
285    let tag = decoder.u8()?;
286    let item_count = decoder.u32()?;
287    if item_count > limits.maximum_page_items {
288        return Err(CanonicalDecodeError::FieldTooLarge {
289            observed: item_count,
290            maximum: limits.maximum_page_items,
291        });
292    }
293    let mut nested_bytes = 0_u64;
294    let kind = match tag {
295        1 | 2 => {
296            for _ in 0..item_count {
297                decoder.u8()?;
298                let name_bytes = decoder.skip_bounded_bytes(limits.maximum_name_bytes)?;
299                nested_bytes = nested_bytes
300                    .checked_add(u64::try_from(name_bytes).unwrap_or(u64::MAX))
301                    .ok_or(CanonicalDecodeError::LengthOverflow)?;
302                if tag == 1 {
303                    decoder.u64()?;
304                }
305                let _: [u8; 32] = decoder.fixed()?;
306            }
307            if tag == 1 {
308                DecodedPageKind::Leaf
309            } else {
310                DecodedPageKind::Internal
311            }
312        }
313        value => {
314            return Err(CanonicalDecodeError::UnknownTag {
315                field: "attribute_page",
316                tag: value,
317            });
318        }
319    };
320    decoder.finish()?;
321    Ok(DecodedPageShape {
322        kind,
323        items: usize::try_from(item_count).map_err(|_| CanonicalDecodeError::LengthOverflow)?,
324        nested_bytes,
325    })
326}
327
328/// Decodes one bounded canonical attribute page.
329///
330/// # Errors
331///
332/// Fails closed on malformed bytes, names, tags, ordering, bounds, or trailing data.
333pub fn decode_attribute_page(
334    bytes: &[u8],
335    limits: DecodeLimits,
336) -> Result<AttributePage, CanonicalDecodeError> {
337    let mut decoder = Decoder::new(bytes, DOMAIN, VERSION, limits.maximum_page_object_bytes())?;
338    let tag = decoder.u8()?;
339    let item_count = decoder.u32()?;
340    if item_count > limits.maximum_page_items {
341        return Err(CanonicalDecodeError::FieldTooLarge {
342            observed: item_count,
343            maximum: limits.maximum_page_items,
344        });
345    }
346    let capacity = usize::try_from(item_count).map_err(|_| CanonicalDecodeError::LengthOverflow)?;
347    let page = match tag {
348        1 => {
349            let mut entries = Vec::new();
350            entries
351                .try_reserve_exact(capacity)
352                .map_err(|_| CanonicalDecodeError::AllocationFailed)?;
353            for _ in 0..item_count {
354                entries.push(AttributeEntry {
355                    name: decode_name(&mut decoder, limits.maximum_name_bytes)?,
356                    value_bytes: decoder.u64()?,
357                    value: digest_object(ObjectKind::Blob, decoder.fixed()?),
358                });
359            }
360            AttributePage::Leaf(entries)
361        }
362        2 => {
363            let mut children = Vec::new();
364            children
365                .try_reserve_exact(capacity)
366                .map_err(|_| CanonicalDecodeError::AllocationFailed)?;
367            for _ in 0..item_count {
368                children.push(AttributeChild {
369                    first_name: decode_name(&mut decoder, limits.maximum_name_bytes)?,
370                    page: digest_object(ObjectKind::AttributePage, decoder.fixed()?),
371                });
372            }
373            AttributePage::Internal(children)
374        }
375        value => {
376            return Err(CanonicalDecodeError::UnknownTag {
377                field: "attribute_page",
378                tag: value,
379            });
380        }
381    };
382    decoder.finish()?;
383    page.validate(limits.maximum_page_items)
384        .map_err(invariant)?;
385    Ok(page)
386}
387
388/// Computes one typed authenticated attribute-page identity.
389///
390/// # Errors
391///
392/// Returns the same validation errors as [`encode_attribute_page`].
393pub fn attribute_page_id(
394    page: &AttributePage,
395    maximum_items: u32,
396) -> Result<ObjectId, CanonicalDecodeError> {
397    let bytes = encode_attribute_page(page, maximum_items)?;
398    Ok(ObjectId {
399        kind: ObjectKind::AttributePage,
400        digest: object_digest(ObjectKind::AttributePage, &bytes),
401    })
402}
403
404/// Named-attribute invariant failures.
405#[derive(Clone, Copy, Debug, Eq, Error, PartialEq)]
406pub enum AttributeError {
407    /// Attribute class tag is unknown.
408    #[error("unknown attribute class {0}")]
409    UnknownClass(u8),
410    /// Name is empty, oversized, or contains NUL.
411    #[error("attribute name is invalid")]
412    InvalidName,
413    /// Page ordering or referenced object class is invalid.
414    #[error("attribute page is invalid")]
415    InvalidPage,
416    /// Page exceeds its admitted item bound.
417    #[error("attribute page exceeds its item bound")]
418    TooManyItems,
419}
420
421fn encode_name(encoder: &mut Encoder, name: &AttributeName) -> Result<(), CanonicalDecodeError> {
422    encoder.u8(name.class.tag());
423    encoder.bounded_bytes(name.as_bytes())
424}
425
426fn decode_name(
427    decoder: &mut Decoder<'_>,
428    maximum_bytes: u32,
429) -> Result<AttributeName, CanonicalDecodeError> {
430    let class = AttributeClass::from_tag(decoder.u8()?).map_err(invariant)?;
431    let bytes = decoder.bounded_bytes(maximum_bytes)?;
432    AttributeName::new(class, bytes, maximum_bytes).map_err(invariant)
433}
434
435fn count(value: usize) -> Result<u32, CanonicalDecodeError> {
436    u32::try_from(value).map_err(|_| CanonicalDecodeError::LengthOverflow)
437}
438
439fn invariant(error: AttributeError) -> CanonicalDecodeError {
440    CanonicalDecodeError::Invariant(error.to_string())
441}
442
443#[cfg(test)]
444#[path = "tests/attribute.rs"]
445mod tests;
acyclic_fs/kernel/attribute.rs

acyclic_fs/kernel/
attribute.rs
