forensic_mount/
archive_tree.rs

1#![forbid(unsafe_code)]
2
3//! Shared synthetic-inode directory tree for archive formats (zip, tar, 7z).
4//!
5//! Archives list a flat set of `path` entries; this builds the directory
6//! hierarchy those paths imply, assigning synthetic inode numbers (root = 2,
7//! mirroring the ext4/ISO convention) and auto-creating intermediate
8//! directories that the archive did not list explicitly.
9//!
10//! Each leaf file carries an opaque `payload_id` — an index the concrete
11//! format module uses to fetch the file's bytes from its backend (a zip entry
12//! index, or a slot in an extracted-data vector). The tree itself never holds
13//! file contents.
14
15use crate::{FsDirEntry, FsError, FsFileType, FsMetadata, FsResult, FsTimestamp};
16use std::collections::HashMap;
17
18/// Root synthetic inode (mirrors ext4/ISO: root = 2).
19pub const ROOT_INO: u64 = 2;
20
21/// One node in the synthetic tree.
22struct Node {
23    name: Vec<u8>,
24    is_dir: bool,
25    size: u64,
26    mtime: FsTimestamp,
27    /// Backend payload handle for leaf files; `None` for directories.
28    payload_id: Option<usize>,
29    children: Vec<u64>,
30}
31
32/// A directory tree built from archive entry paths.
33pub struct ArchiveTree {
34    nodes: HashMap<u64, Node>,
35    /// Map from a parent inode + child name to the child's inode, for fast
36    /// path-component resolution while building and for `lookup`.
37    index: HashMap<(u64, Vec<u8>), u64>,
38    next_ino: u64,
39}
40
41impl Default for ArchiveTree {
42    fn default() -> Self {
43        Self::new()
44    }
45}
46
47impl ArchiveTree {
48    /// Create an empty tree containing only the root directory.
49    pub fn new() -> Self {
50        let mut nodes = HashMap::new();
51        nodes.insert(
52            ROOT_INO,
53            Node {
54                name: b"/".to_vec(),
55                is_dir: true,
56                size: 0,
57                mtime: FsTimestamp::default(),
58                payload_id: None,
59                children: vec![],
60            },
61        );
62        Self {
63            nodes,
64            index: HashMap::new(),
65            next_ino: ROOT_INO + 1,
66        }
67    }
68
69    /// Insert a file (or explicit directory) at `path`, creating any missing
70    /// intermediate directories. Returns the leaf inode, or `None` if the path
71    /// is unsafe (absolute, empty, or contains a `..` component) and was
72    /// skipped.
73    pub fn insert(
74        &mut self,
75        path: &str,
76        is_dir: bool,
77        size: u64,
78        mtime: FsTimestamp,
79        payload_id: Option<usize>,
80    ) -> Option<u64> {
81        let components = sanitize_path(path)?;
82        if components.is_empty() {
83            return None;
84        }
85        let last = components.len() - 1;
86        let mut parent = ROOT_INO;
87        for (i, comp) in components.iter().enumerate() {
88            let leaf = i == last;
89            let key = (parent, comp.clone());
90            if let Some(&existing) = self.index.get(&key) {
91                // A path may re-list an intermediate directory; reuse it. A leaf
92                // colliding with an existing node keeps the first (archives can
93                // carry duplicate names; the tree shows one).
94                parent = existing;
95                continue;
96            }
97            let ino = self.next_ino;
98            self.next_ino += 1;
99            let node = Node {
100                name: comp.clone(),
101                is_dir: if leaf { is_dir } else { true },
102                size: if leaf && !is_dir { size } else { 0 },
103                mtime: if leaf { mtime } else { FsTimestamp::default() },
104                payload_id: if leaf && !is_dir { payload_id } else { None },
105                children: vec![],
106            };
107            self.nodes.insert(ino, node);
108            self.index.insert(key, ino);
109            if let Some(p) = self.nodes.get_mut(&parent) {
110                p.children.push(ino);
111            }
112            parent = ino;
113        }
114        Some(parent)
115    }
116
117    /// The root inode.
118    pub fn root_ino(&self) -> u64 {
119        ROOT_INO
120    }
121
122    /// The backend payload handle for a leaf file, if any.
123    pub fn payload_id(&self, ino: u64) -> Option<usize> {
124        self.nodes.get(&ino).and_then(|n| n.payload_id)
125    }
126
127    /// List a directory's children.
128    pub fn read_dir(&self, ino: u64) -> FsResult<Vec<FsDirEntry>> {
129        let node = self.node(ino)?;
130        let mut out = Vec::with_capacity(node.children.len());
131        for &child in &node.children {
132            if let Some(c) = self.nodes.get(&child) {
133                out.push(FsDirEntry {
134                    inode: child,
135                    name: c.name.clone(),
136                    file_type: if c.is_dir {
137                        FsFileType::Directory
138                    } else {
139                        FsFileType::RegularFile
140                    },
141                });
142            }
143        }
144        Ok(out)
145    }
146
147    /// Look up a child by name within a directory.
148    pub fn lookup(&self, parent_ino: u64, name: &[u8]) -> FsResult<Option<u64>> {
149        // Validate the parent exists so a lookup on a bogus inode errors rather
150        // than silently returning "not found".
151        self.node(parent_ino)?;
152        Ok(self.index.get(&(parent_ino, name.to_vec())).copied())
153    }
154
155    /// Metadata for an inode.
156    pub fn metadata(&self, ino: u64) -> FsResult<FsMetadata> {
157        let node = self.node(ino)?;
158        let (file_type, mode) = if node.is_dir {
159            (FsFileType::Directory, 0o40555)
160        } else {
161            (FsFileType::RegularFile, 0o100_444)
162        };
163        Ok(FsMetadata {
164            ino,
165            file_type,
166            mode,
167            uid: 0,
168            gid: 0,
169            size: node.size,
170            links_count: 1,
171            atime: node.mtime,
172            mtime: node.mtime,
173            ctime: node.mtime,
174            crtime: node.mtime,
175            allocated: true,
176        })
177    }
178
179    fn node(&self, ino: u64) -> FsResult<&Node> {
180        self.nodes
181            .get(&ino)
182            .ok_or_else(|| FsError::NotFound(format!("inode {ino}")))
183    }
184
185    /// Number of nodes (including the root), for diagnostics.
186    pub fn len(&self) -> usize {
187        self.nodes.len()
188    }
189
190    /// Whether the tree holds only the root.
191    pub fn is_empty(&self) -> bool {
192        self.nodes.len() <= 1
193    }
194}
195
196/// Split an archive entry path into safe components, or `None` if the path is
197/// absolute, empty, or escapes its root via a `..` component (zip-slip / tar
198/// traversal). `.` and empty components are dropped; a trailing slash collapses.
199fn sanitize_path(path: &str) -> Option<Vec<Vec<u8>>> {
200    if path.starts_with('/') {
201        return None;
202    }
203    let mut out = Vec::new();
204    for comp in path.split('/') {
205        match comp {
206            "" | "." => {}
207            ".." => return None,
208            c => out.push(c.as_bytes().to_vec()),
209        }
210    }
211    if out.is_empty() {
212        return None;
213    }
214    Some(out)
215}
216
217/// Seconds from the Unix epoch for a civil UTC date (Howard Hinnant's
218/// algorithm). Shared by archive formats whose entry timestamps are broken-down
219/// calendar fields (e.g. ZIP's MS-DOS date, 7z's component date).
220pub(crate) fn civil_to_unix(y: i64, m: i64, d: i64, hh: i64, mm: i64, ss: i64) -> i64 {
221    let y = if m <= 2 { y - 1 } else { y };
222    let era = if y >= 0 { y } else { y - 399 } / 400;
223    let yoe = y - era * 400;
224    let mp = (m + 9) % 12;
225    let doy = (153 * mp + 2) / 5 + d - 1;
226    let doe = yoe * 365 + yoe / 4 - yoe / 100 + doy;
227    let days = era * 146_097 + doe - 719_468;
228    days * 86_400 + hh * 3_600 + mm * 60 + ss
229}
230
231#[cfg(test)]
232mod tests {
233    use super::*;
234
235    fn ts() -> FsTimestamp {
236        FsTimestamp {
237            seconds: 1_700_000_000,
238            nanoseconds: 0,
239        }
240    }
241
242    #[test]
243    fn new_tree_has_only_root() {
244        let t = ArchiveTree::new();
245        assert_eq!(t.root_ino(), ROOT_INO);
246        assert!(t.is_empty());
247        assert_eq!(
248            t.metadata(ROOT_INO).unwrap().file_type,
249            FsFileType::Directory
250        );
251    }
252
253    #[test]
254    fn insert_file_at_root() {
255        let mut t = ArchiveTree::new();
256        let ino = t.insert("hello.txt", false, 11, ts(), Some(0)).unwrap();
257        assert_eq!(t.lookup(ROOT_INO, b"hello.txt").unwrap(), Some(ino));
258        let meta = t.metadata(ino).unwrap();
259        assert_eq!(meta.file_type, FsFileType::RegularFile);
260        assert_eq!(meta.size, 11);
261        assert_eq!(t.payload_id(ino), Some(0));
262    }
263
264    #[test]
265    fn insert_creates_intermediate_dirs() {
266        let mut t = ArchiveTree::new();
267        let ino = t.insert("a/b/c.txt", false, 3, ts(), Some(0)).unwrap();
268        let a = t.lookup(ROOT_INO, b"a").unwrap().expect("a created");
269        assert_eq!(t.metadata(a).unwrap().file_type, FsFileType::Directory);
270        let b = t.lookup(a, b"b").unwrap().expect("b created");
271        let c = t.lookup(b, b"c.txt").unwrap().expect("c.txt created");
272        assert_eq!(c, ino);
273    }
274
275    #[test]
276    fn read_dir_lists_children() {
277        let mut t = ArchiveTree::new();
278        t.insert("x.txt", false, 1, ts(), Some(0)).unwrap();
279        t.insert("y.txt", false, 1, ts(), Some(1)).unwrap();
280        let names: Vec<String> = t
281            .read_dir(ROOT_INO)
282            .unwrap()
283            .iter()
284            .map(FsDirEntry::name_str)
285            .collect();
286        assert!(names.contains(&"x.txt".to_string()));
287        assert!(names.contains(&"y.txt".to_string()));
288    }
289
290    #[test]
291    fn explicit_dir_entry_is_directory() {
292        let mut t = ArchiveTree::new();
293        t.insert("subdir/", true, 0, ts(), None).unwrap();
294        let d = t.lookup(ROOT_INO, b"subdir").unwrap().expect("subdir");
295        assert_eq!(t.metadata(d).unwrap().file_type, FsFileType::Directory);
296    }
297
298    #[test]
299    fn duplicate_intermediate_dir_is_shared() {
300        let mut t = ArchiveTree::new();
301        t.insert("a/b.txt", false, 1, ts(), Some(0)).unwrap();
302        t.insert("a/c.txt", false, 1, ts(), Some(1)).unwrap();
303        let a = t.lookup(ROOT_INO, b"a").unwrap().unwrap();
304        let kids = t.read_dir(a).unwrap();
305        assert_eq!(kids.len(), 2, "a/ holds exactly b.txt and c.txt");
306    }
307
308    #[test]
309    fn unsafe_paths_are_skipped() {
310        let mut t = ArchiveTree::new();
311        assert_eq!(t.insert("../escape", false, 1, ts(), Some(0)), None);
312        assert_eq!(t.insert("/abs", false, 1, ts(), Some(0)), None);
313        assert_eq!(t.insert("", false, 1, ts(), Some(0)), None);
314        assert_eq!(t.insert("a/../b", false, 1, ts(), Some(0)), None);
315    }
316
317    #[test]
318    fn leading_dot_slash_normalized() {
319        let mut t = ArchiveTree::new();
320        let ino = t.insert("./file.txt", false, 1, ts(), Some(0)).unwrap();
321        assert_eq!(t.lookup(ROOT_INO, b"file.txt").unwrap(), Some(ino));
322    }
323
324    #[test]
325    fn metadata_missing_inode_errs() {
326        let t = ArchiveTree::new();
327        assert!(t.metadata(9999).is_err());
328    }
329}
forensic_mount/archive_tree.rs

forensic_mount/
archive_tree.rs
