ext4_metadata/
lib.rs

1// Copyright 2023 The Fuchsia Authors. All rights reserved.
2// Use of this source code is governed by a BSD-style license that can be
3// found in the LICENSE file.
4
5use flyweights::{FlyByteStr, FlyStr};
6use serde::{Deserialize, Serialize};
7use sorted_vec_map::SortedVecMap;
8use std::collections::{BTreeMap, HashSet};
9use std::sync::Arc;
10use thiserror::Error;
11
12// This is deliberately the same as ext4.
13pub const ROOT_INODE_NUM: u64 = 2;
14
15pub const S_IFDIR: u16 = 0x4000;
16pub const S_IFREG: u16 = 0x8000;
17pub const S_IFLNK: u16 = 0xa000;
18pub const S_IFMT: u16 = 0xf000;
19
20#[derive(Error, Debug)]
21pub enum MetadataError {
22    #[error("Node not found")]
23    NotFound,
24    #[error("Node is not a directory")]
25    NotDir,
26    #[error("Failed to deserialize metadata (corrupt?)")]
27    FailedToDeserialize,
28}
29
30#[derive(Serialize, Deserialize)]
31pub struct Metadata {
32    nodes: SortedVecMap<u64, Node>,
33}
34
35impl Metadata {
36    pub fn new() -> Self {
37        Self { nodes: SortedVecMap::new() }
38    }
39
40    /// Finds the node with name `name` in directory with inode number `parent`.
41    pub fn lookup(&self, parent: u64, name: &str) -> Result<u64, MetadataError> {
42        self.nodes
43            .get(&parent)
44            .ok_or(MetadataError::NotFound)?
45            .directory()
46            .ok_or(MetadataError::NotDir)?
47            .children
48            .get(&FlyStr::from(name))
49            .ok_or(MetadataError::NotFound)
50            .cloned()
51    }
52
53    /// Returns the node with inode number `inode_num`.
54    pub fn get(&self, inode_num: u64) -> Option<&Node> {
55        self.nodes.get(&inode_num)
56    }
57
58    /// Deserializes the metadata.
59    pub fn deserialize(bytes: &[u8]) -> Result<Self, MetadataError> {
60        let mut metadata: Self =
61            bincode::deserialize(bytes).map_err(|_| MetadataError::FailedToDeserialize)?;
62        metadata.dedup_xattrs();
63        Ok(metadata)
64    }
65
66    /// Serializes the metadata.
67    pub fn serialize(&self) -> Vec<u8> {
68        bincode::serialize(&self).unwrap()
69    }
70
71    /// Add a child at `path` with inode number `inode_num`.
72    pub fn add_child(&mut self, path: &[&str], inode_num: u64) {
73        for component in path {
74            assert!(
75                *component != "."
76                    && *component != ".."
77                    && !component.contains(|c| c == '/' || c == '\0'),
78                "Invalid path component {component:?} in {path:?}"
79            );
80        }
81
82        let mut node = self.nodes.get_mut(&ROOT_INODE_NUM).unwrap().directory_mut().unwrap();
83        let mut iter = path.iter();
84        let name = *iter.next_back().unwrap();
85        for component in iter {
86            let inode_num = *node.children.get(&FlyStr::from(*component)).unwrap();
87            node = self.nodes.get_mut(&inode_num).unwrap().directory_mut().unwrap();
88        }
89        node.children.insert(name.into(), inode_num);
90    }
91
92    /// Inserts a directory node.  This will not add a child to a directory; see `add_child`.
93    pub fn insert_directory(
94        &mut self,
95        inode_num: u64,
96        mode: u16,
97        uid: u16,
98        gid: u16,
99        extended_attributes: ExtendedAttributes,
100    ) {
101        assert_eq!(mode & S_IFMT, S_IFDIR);
102        self.nodes.insert(
103            inode_num,
104            Node {
105                info: NodeInfo::Directory(Directory { children: SortedVecMap::new() }),
106                mode,
107                uid,
108                gid,
109                extended_attributes,
110            },
111        );
112    }
113
114    /// Inserts a file node.  This will not add a child to a directory; see `add_child`.
115    pub fn insert_file(
116        &mut self,
117        inode_num: u64,
118        mode: u16,
119        uid: u16,
120        gid: u16,
121        extended_attributes: ExtendedAttributes,
122    ) {
123        assert_eq!(mode & S_IFMT, S_IFREG);
124        self.nodes.insert(
125            inode_num,
126            Node { info: NodeInfo::File(File), mode, uid, gid, extended_attributes },
127        );
128    }
129
130    /// Inserts a symlink node.  This will not add a child to a directory; see `add_child`.
131    pub fn insert_symlink(
132        &mut self,
133        inode_num: u64,
134        target: String,
135        mode: u16,
136        uid: u16,
137        gid: u16,
138        extended_attributes: ExtendedAttributes,
139    ) {
140        assert_eq!(mode & S_IFMT, S_IFLNK);
141        self.nodes.insert(
142            inode_num,
143            Node {
144                info: NodeInfo::Symlink(Symlink { target: target.into() }),
145                mode,
146                uid,
147                gid,
148                extended_attributes,
149            },
150        );
151    }
152
153    /// Nodes will often have the exact same set of extended attributes as other nodes. For this
154    /// reason, entire sets of extended attributes are reference counted and shared between nodes.
155    /// The serialized format of the metadata writes out the extended attributes along with each
156    /// node. After deserializing the metadata, each node will contain its own copy of the extended
157    /// attributes. This function scans all of the nodes and deduplicates the extended attributes to
158    /// save memory.
159    fn dedup_xattrs(&mut self) {
160        let mut xattrs: HashSet<Arc<SortedVecMap<FlyByteStr, FlyByteStr>>> = HashSet::new();
161        for node in self.nodes.values_mut() {
162            match xattrs.get(node.extended_attributes.0.as_ref()) {
163                Some(existing) => {
164                    node.extended_attributes.0 = existing.clone();
165                }
166                None => {
167                    xattrs.insert(node.extended_attributes.0.clone());
168                }
169            }
170        }
171    }
172}
173
174#[derive(Default, Clone, PartialEq, Eq, Debug)]
175pub struct ExtendedAttributes(Arc<SortedVecMap<FlyByteStr, FlyByteStr>>);
176
177impl<'de> serde::Deserialize<'de> for ExtendedAttributes {
178    fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>
179    where
180        D: serde::Deserializer<'de>,
181    {
182        let mut map = SortedVecMap::deserialize(deserializer)?;
183        map.shrink_to_fit();
184        Ok(Self(Arc::new(map)))
185    }
186}
187
188impl serde::Serialize for ExtendedAttributes {
189    fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error>
190    where
191        S: serde::Serializer,
192    {
193        self.0.as_ref().serialize(serializer)
194    }
195}
196
197impl FromIterator<(FlyByteStr, FlyByteStr)> for ExtendedAttributes {
198    fn from_iter<T: IntoIterator<Item = (FlyByteStr, FlyByteStr)>>(iter: T) -> Self {
199        let mut map = SortedVecMap::from_iter(iter);
200        map.shrink_to_fit();
201        ExtendedAttributes(Arc::new(map))
202    }
203}
204
205impl<const N: usize> From<[(FlyByteStr, FlyByteStr); N]> for ExtendedAttributes {
206    fn from(value: [(FlyByteStr, FlyByteStr); N]) -> Self {
207        value.into_iter().collect()
208    }
209}
210
211impl From<BTreeMap<Box<[u8]>, Box<[u8]>>> for ExtendedAttributes {
212    fn from(value: BTreeMap<Box<[u8]>, Box<[u8]>>) -> Self {
213        value.into_iter().map(|(k, v)| (k.into(), v.into())).collect()
214    }
215}
216
217impl ExtendedAttributes {
218    pub fn get(&self, key: &[u8]) -> Option<&FlyByteStr> {
219        self.0.get(&FlyByteStr::from(key))
220    }
221
222    pub fn keys(&self) -> impl Iterator<Item = &FlyByteStr> {
223        self.0.keys()
224    }
225
226    pub fn is_empty(&self) -> bool {
227        self.0.is_empty()
228    }
229}
230
231#[derive(Serialize, Deserialize)]
232pub struct Node {
233    info: NodeInfo,
234    pub mode: u16,
235    pub uid: u16,
236    pub gid: u16,
237    pub extended_attributes: ExtendedAttributes,
238}
239
240impl Node {
241    pub fn info(&self) -> &NodeInfo {
242        &self.info
243    }
244
245    pub fn directory(&self) -> Option<&Directory> {
246        match &self.info {
247            NodeInfo::Directory(d) => Some(d),
248            _ => None,
249        }
250    }
251
252    pub fn directory_mut(&mut self) -> Option<&mut Directory> {
253        match &mut self.info {
254            NodeInfo::Directory(d) => Some(d),
255            _ => None,
256        }
257    }
258
259    pub fn file(&self) -> Option<&File> {
260        match &self.info {
261            NodeInfo::File(f) => Some(f),
262            _ => None,
263        }
264    }
265
266    pub fn symlink(&self) -> Option<&Symlink> {
267        match &self.info {
268            NodeInfo::Symlink(s) => Some(s),
269            _ => None,
270        }
271    }
272}
273
274#[derive(Debug, Serialize, Deserialize)]
275pub enum NodeInfo {
276    Directory(Directory),
277    File(File),
278    Symlink(Symlink),
279}
280
281#[derive(Debug, Serialize, Deserialize)]
282pub struct Directory {
283    pub children: SortedVecMap<FlyStr, u64>,
284}
285
286#[derive(Debug, Serialize, Deserialize)]
287pub struct File;
288
289#[derive(Debug, Serialize, Deserialize)]
290pub struct Symlink {
291    pub target: FlyStr,
292}
293
294#[cfg(test)]
295mod tests {
296    use super::{
297        ExtendedAttributes, Metadata, NodeInfo, ROOT_INODE_NUM, S_IFDIR, S_IFLNK, S_IFREG,
298    };
299    use assert_matches::assert_matches;
300    use std::collections::BTreeMap;
301    use std::sync::Arc;
302
303    #[test]
304    fn test_serialize_and_deserialize() {
305        let mut m = Metadata::new();
306        let xattr: ExtendedAttributes =
307            [((*b"a").into(), (*b"apple").into()), ((*b"b").into(), (*b"ball").into())].into();
308        m.insert_directory(ROOT_INODE_NUM, S_IFDIR | 0o755, 2, 3, Default::default());
309        m.insert_directory(3, S_IFDIR | 0o775, 2, 3, xattr.clone());
310        m.add_child(&["foo"], 3);
311        m.insert_file(4, S_IFREG | 0o644, 2, 3, xattr.clone());
312        m.add_child(&["foo", "bar"], 4);
313        m.insert_symlink(5, "symlink-target".to_string(), S_IFLNK | 0o777, 2, 3, xattr.clone());
314        m.add_child(&["foo", "baz"], 5);
315
316        let m = Metadata::deserialize(&m.serialize()).expect("deserialize failed");
317        let node = m.get(ROOT_INODE_NUM).expect("root not found");
318        assert_matches!(node.info(), NodeInfo::Directory(_));
319        assert_eq!(node.mode, S_IFDIR | 0o755);
320        assert_eq!(node.uid, 2);
321        assert_eq!(node.gid, 3);
322        assert!(node.extended_attributes.is_empty());
323
324        assert_eq!(m.lookup(ROOT_INODE_NUM, "foo").expect("foo not found"), 3);
325        let node = m.get(3).expect("root not found");
326        assert_matches!(node.info(), NodeInfo::Directory(_));
327        assert_eq!(node.mode, S_IFDIR | 0o775);
328        assert_eq!(node.uid, 2);
329        assert_eq!(node.gid, 3);
330        assert_eq!(&node.extended_attributes, &xattr);
331
332        assert_eq!(m.lookup(3, "bar").expect("foo/bar not found"), 4);
333        let node = m.get(4).expect("root not found");
334        assert_matches!(node.info(), NodeInfo::File(_));
335        assert_eq!(node.mode, S_IFREG | 0o644);
336        assert_eq!(node.uid, 2);
337        assert_eq!(node.gid, 3);
338        assert_eq!(&node.extended_attributes, &xattr);
339
340        assert_eq!(m.lookup(3, "baz").expect("foo/baz not found"), 5);
341        let node = m.get(5).expect("root not found");
342        assert_matches!(node.info(), NodeInfo::Symlink(_));
343        assert_eq!(node.mode, S_IFLNK | 0o777);
344        assert_eq!(node.uid, 2);
345        assert_eq!(node.gid, 3);
346        assert_eq!(&node.extended_attributes, &xattr);
347    }
348
349    #[test]
350    fn test_serialization_is_deterministic() {
351        // Builds a Metadata instance with fixed contents.
352        let build_fs = || {
353            let mut m = Metadata::new();
354            let xattr: ExtendedAttributes =
355                [((*b"a").into(), (*b"apple").into()), ((*b"b").into(), (*b"ball").into())].into();
356            m.insert_directory(ROOT_INODE_NUM, S_IFDIR | 0o755, 2, 3, Default::default());
357            m.insert_directory(3, S_IFDIR | 0o775, 2, 3, xattr.clone());
358            m.add_child(&["foo"], 3);
359            m.insert_file(4, S_IFREG | 0o644, 2, 3, xattr.clone());
360            m.add_child(&["foo", "bar"], 4);
361            m.insert_symlink(5, "symlink-target".to_string(), S_IFLNK | 0o777, 2, 3, xattr.clone());
362            m.add_child(&["foo", "baz"], 5);
363            m
364        };
365
366        // Build it twice and verify that the serialized representations match.
367        let data1 = build_fs().serialize();
368        let data2 = build_fs().serialize();
369        assert_eq!(data1, data2);
370    }
371
372    #[test]
373    fn test_dedup_extended_attributes() {
374        let mut m = Metadata::new();
375        m.insert_directory(ROOT_INODE_NUM, S_IFDIR | 0o755, 2, 3, Default::default());
376        m.insert_file(3, S_IFREG, 2, 3, [("a".into(), "b".into())].into());
377        m.add_child(&["foo"], 3);
378        m.insert_file(4, S_IFREG, 2, 3, [("a".into(), "b".into())].into());
379        m.add_child(&["bar"], 4);
380
381        // The extended attributes are equal but they haven't been deduplicated yet.
382        assert_eq!(
383            m.get(3).unwrap().extended_attributes.0,
384            m.get(4).unwrap().extended_attributes.0
385        );
386        assert!(!Arc::ptr_eq(
387            &m.get(3).unwrap().extended_attributes.0,
388            &m.get(4).unwrap().extended_attributes.0
389        ));
390
391        m.dedup_xattrs();
392        // The extended attributes are now deduplicated.
393        assert!(Arc::ptr_eq(
394            &m.get(3).unwrap().extended_attributes.0,
395            &m.get(4).unwrap().extended_attributes.0
396        ));
397
398        // The extended attributes are duplicated in the serialized data but get deduplicated again
399        // when being deserialized.
400        let m = Metadata::deserialize(&m.serialize()).unwrap();
401        assert!(Arc::ptr_eq(
402            &m.get(3).unwrap().extended_attributes.0,
403            &m.get(4).unwrap().extended_attributes.0
404        ));
405    }
406
407    #[test]
408    fn test_extended_attribute_serialization_backwards_compatibility() {
409        let xattrs = [(b"a", b"b"), (b"c", b"d"), (b"e", b"f")];
410        let btree_map: BTreeMap<Box<[u8]>, Box<[u8]>> =
411            xattrs.iter().map(|&(&k, &v)| (k.into(), v.into())).collect();
412
413        let serialized = bincode::serialize(&btree_map).unwrap();
414
415        let extended_attributes: ExtendedAttributes = bincode::deserialize(&serialized).unwrap();
416        let expected_xattrs: ExtendedAttributes =
417            xattrs.iter().map(|&(&k, &v)| (k.into(), v.into())).collect();
418        assert_eq!(extended_attributes, expected_xattrs);
419    }
420
421    #[test]
422    fn test_extended_attribute_serialization_forwards_compatibility() {
423        let xattrs = [(b"a", b"b"), (b"c", b"d"), (b"e", b"f")];
424        let extended_attributes: ExtendedAttributes =
425            xattrs.iter().map(|&(&k, &v)| (k.into(), v.into())).collect();
426
427        let serialized = bincode::serialize(&extended_attributes).unwrap();
428
429        let btree_map: BTreeMap<Box<[u8]>, Box<[u8]>> = bincode::deserialize(&serialized).unwrap();
430        let expected_xattrs: BTreeMap<Box<[u8]>, Box<[u8]>> =
431            xattrs.iter().map(|&(&k, &v)| (k.into(), v.into())).collect();
432        assert_eq!(btree_map, expected_xattrs);
433    }
434}
ext4_metadata/lib.rs

ext4_metadata/
lib.rs
