acyclic_fs/kernel/
generation.rs

1//! Canonical immutable volume-generation roots and parent lineage.
2
3use super::codec::{CanonicalDecodeError, DecodeLimits, Decoder, Encoder};
4use super::types::digest_object;
5use crate::foundation::{Digest, FileId, GenerationId, VolumeId};
6use crate::storage::{ObjectId, ObjectKind, object_digest};
7
8const DOMAIN: &[u8; 8] = b"ACYFSGEN";
9const VERSION: u16 = 1;
10const MAXIMUM_PARENTS: u32 = 2;
11/// Largest canonical generation-root object in this format version.
12pub const MAXIMUM_GENERATION_ROOT_BYTES: u64 = 150;
13
14/// One immutable volume generation.
15#[derive(Clone, Debug, Eq, PartialEq)]
16pub struct GenerationRoot {
17    /// Independently configured/versioned volume identity.
18    pub volume_id: VolumeId,
19    /// Root directory's path-independent file identity.
20    pub root_file_id: FileId,
21    /// Authenticated file-table root containing every reachable file record.
22    pub file_table: ObjectId,
23    /// Ordered zero-, one-, or two-parent lineage.
24    pub parents: Vec<GenerationId>,
25    /// Required format semantics; unknown bits are rejected by this version.
26    pub required_features: u64,
27}
28
29impl GenerationRoot {
30    fn validate(&self) -> Result<(), CanonicalDecodeError> {
31        if self.file_table.kind != ObjectKind::FileTablePage {
32            return Err(invariant("generation file table has the wrong object kind"));
33        }
34        if self.parents.len() > usize::try_from(MAXIMUM_PARENTS).unwrap_or(usize::MAX) {
35            return Err(invariant("generation has too many parents"));
36        }
37        if let [first, second] = self.parents.as_slice()
38            && first == second
39        {
40            return Err(invariant("generation parents are duplicated"));
41        }
42        if self.required_features != 0 {
43            return Err(invariant("generation requires unsupported format features"));
44        }
45        Ok(())
46    }
47}
48
49/// Encodes one validated canonical generation root.
50///
51/// # Errors
52///
53/// Rejects wrong object classes, duplicate/excess parents, and unsupported
54/// required feature bits.
55pub fn encode_generation_root(root: &GenerationRoot) -> Result<Vec<u8>, CanonicalDecodeError> {
56    root.validate()?;
57    let mut encoder = Encoder::new(DOMAIN, VERSION);
58    encoder.fixed(&root.volume_id.into_bytes());
59    encoder.fixed(&root.root_file_id.into_bytes());
60    encoder.fixed(root.file_table.digest.as_bytes());
61    encoder
62        .u32(u32::try_from(root.parents.len()).map_err(|_| CanonicalDecodeError::LengthOverflow)?);
63    for parent in &root.parents {
64        encoder.fixed(parent.digest().as_bytes());
65    }
66    encoder.u64(root.required_features);
67    Ok(encoder.finish())
68}
69
70/// Decodes one bounded canonical generation root.
71///
72/// # Errors
73///
74/// Fails closed on malformed bytes, unsupported versions/features, excessive or
75/// duplicate parents, and trailing bytes.
76pub fn decode_generation_root(
77    bytes: &[u8],
78    limits: DecodeLimits,
79) -> Result<GenerationRoot, CanonicalDecodeError> {
80    let mut decoder = Decoder::new(bytes, DOMAIN, VERSION, limits.maximum_object_bytes)?;
81    let volume_id = VolumeId::from_bytes(decoder.fixed()?);
82    let root_file_id = FileId::from_bytes(decoder.fixed()?);
83    let file_table = digest_object(ObjectKind::FileTablePage, decoder.fixed()?);
84    let parent_count = decoder.u32()?;
85    if parent_count > MAXIMUM_PARENTS {
86        return Err(CanonicalDecodeError::FieldTooLarge {
87            observed: parent_count,
88            maximum: MAXIMUM_PARENTS,
89        });
90    }
91    let parent_count =
92        usize::try_from(parent_count).map_err(|_| CanonicalDecodeError::LengthOverflow)?;
93    let mut parents = Vec::new();
94    parents
95        .try_reserve_exact(parent_count)
96        .map_err(|_| CanonicalDecodeError::AllocationFailed)?;
97    for _ in 0..parent_count {
98        parents.push(GenerationId::new(Digest::from_bytes(decoder.fixed()?)));
99    }
100    let required_features = decoder.u64()?;
101    decoder.finish()?;
102    let root = GenerationRoot {
103        volume_id,
104        root_file_id,
105        file_table,
106        parents,
107        required_features,
108    };
109    root.validate()?;
110    Ok(root)
111}
112
113pub(crate) fn generation_root_parent_count(
114    bytes: &[u8],
115    limits: DecodeLimits,
116) -> Result<usize, CanonicalDecodeError> {
117    let mut decoder = Decoder::new(bytes, DOMAIN, VERSION, limits.maximum_object_bytes)?;
118    let _: [u8; 16] = decoder.fixed()?;
119    let _: [u8; 16] = decoder.fixed()?;
120    let _: [u8; 32] = decoder.fixed()?;
121    let parent_count = decoder.u32()?;
122    if parent_count > MAXIMUM_PARENTS {
123        return Err(CanonicalDecodeError::FieldTooLarge {
124            observed: parent_count,
125            maximum: MAXIMUM_PARENTS,
126        });
127    }
128    usize::try_from(parent_count).map_err(|_| CanonicalDecodeError::LengthOverflow)
129}
130
131/// Computes the typed object identity and generation identity of one root.
132///
133/// # Errors
134///
135/// Returns the same validation errors as [`encode_generation_root`].
136pub fn generation_root_id(
137    root: &GenerationRoot,
138) -> Result<(ObjectId, GenerationId), CanonicalDecodeError> {
139    let bytes = encode_generation_root(root)?;
140    let object = ObjectId {
141        kind: ObjectKind::GenerationRoot,
142        digest: object_digest(ObjectKind::GenerationRoot, &bytes),
143    };
144    Ok((object, GenerationId::new(object.digest)))
145}
146
147fn invariant(message: &str) -> CanonicalDecodeError {
148    CanonicalDecodeError::Invariant(message.to_owned())
149}
150
151#[cfg(test)]
152#[path = "tests/generation.rs"]
153mod tests;
acyclic_fs/kernel/generation.rs

acyclic_fs/kernel/
generation.rs
