ferrosys 0.8.0

Pure-Rust filesystem formatter and reader: ext4, ext3, ext2, FAT32, FAT16, FAT12, exFAT, btrfs, and APFS — rootless, in userspace, byte-reproducible
Documentation
//! The depth-first walk every family's reader is driven by.
//!
//! Walking a filesystem tree is the same algorithm whatever the format: seed a frontier from
//! the root's children, pop a name, descend into it the first time its directory is reached,
//! push its children in reverse order so they pop in order, and yield each name once. What
//! differs between the families is three things and no more — what sits on the frontier, what
//! identifies a directory for the cycle check, and how a name's children are read — and
//! [`Walk`] is exactly those three.
//!
//! # The bounds are the reason this is one function
//!
//! A walk reads a tree it has no reason to trust, and three separate properties of the input
//! could make it run without end or without bound:
//!
//! - **A cycle.** Nothing in a directory entry says it does not point back up the tree, and a
//!   crafted image can say a directory is its own ancestor. Descending into a directory only
//!   the first time its identity is reached terminates that. Reaching one again is a tree no
//!   family here holds when it is sound, so the family judges it under its read policy as
//!   well: a strict read refuses the tree, and a lenient one passes the repeat over, bounded.
//! - **The frontier.** Each iteration may push a whole directory's worth of children, and
//!   distinct directories may map the same storage — so bounding only the names *popped*
//!   would leave the stack bounded by the cap times a directory's fan-out rather than by the
//!   cap. Every name pushed is a name this walk must yield, so a frontier already past what
//!   is left of the cap is a walk past it, reported before the memory is spent.
//! - **Depth.** An explicit stack rather than recursion, so a tree nested arbitrarily deep is
//!   walked without a call-stack bound.
//!
//! Each of those is a bound a reader has to get exactly right, and none of them is visible in
//! what a walk *returns* — a walk missing one is a walk that works on every sound filesystem
//! and runs without end on a crafted one. So they are stated here, once, and a family
//! supplies only what it genuinely decides.

use std::collections::HashSet;
use std::hash::Hash;

use crate::policy::MAX_PATH;

/// What a depth-first walk needs of a filesystem's reader.
pub(crate) trait Walk {
    /// What sits on the frontier: the least a family needs to visit a name later.
    ///
    /// A family that can re-read a node cheaply keeps a locator here rather than the node
    /// itself, since the frontier holds every name reached and not yet visited.
    type Pending;

    /// What a visitor is handed: the resolved name.
    type Entry;

    /// What identifies a directory for the cycle check — an inode number, a first cluster.
    type Key: Eq + Hash;

    /// The family's own failure.
    type Error;

    /// The most names this walk may yield: the caller's bound and the filesystem's own
    /// storage ceiling, whichever is lower.
    fn cap(&mut self) -> usize;

    /// The frontier the root's children make, and the keys already occupied — the root's
    /// own, so a tree that points back at it does not descend twice.
    ///
    /// The root has no name, so a walk seeds from its children rather than from it.
    fn seed(&mut self) -> Result<Seed<Self>, Self::Error>;

    /// Resolve a frontier element into the entry a visitor receives.
    fn resolve(&mut self, pending: Self::Pending) -> Result<Self::Entry, Self::Error>;

    /// The key to descend under, or `None` for an entry that is not a directory with
    /// storage to descend into.
    fn descend_key(&self, entry: &Self::Entry) -> Option<Self::Key>;

    /// The names below `entry`, in reverse name order so a stack pops them in order.
    fn children(&mut self, entry: &Self::Entry) -> Result<Vec<Self::Pending>, Self::Error>;

    /// Judge `entry`, a directory whose identity the walk has already reached: a cycle, or a
    /// second name for one directory. The walk does not descend into it again whatever this
    /// answers; the answer is whether the reader's policy refuses the tree for it.
    fn repeated(&mut self, entry: &Self::Entry) -> Result<(), Self::Error>;

    /// The failure this family reports for a walk past `limit` names.
    fn too_large(limit: usize) -> Self::Error;
}

/// What a walk starts from: the root's children, and the keys already occupied.
pub(crate) type Seed<W> = (Vec<<W as Walk>::Pending>, Vec<<W as Walk>::Key>);

/// Walk every name below the root, calling `visit` for each in depth-first order with a
/// parent before its children and siblings in name order.
///
/// The visitor is handed the reader back, so it can stat, read, and resolve while the walk is
/// in progress and nothing has to be gathered up front. Its error type is its own, and the
/// walk's failures convert into it — so a consumer's own failure and the filesystem's each
/// reach the caller as themselves.
///
/// # Errors
///
/// Whatever `visit` returns, and the family's own errors converted into it.
pub(crate) fn drive<W, E>(
    walk: &mut W,
    mut visit: impl FnMut(&mut W, W::Entry) -> Result<(), E>,
) -> Result<(), E>
where
    W: Walk,
    E: From<W::Error>,
{
    let cap = walk.cap();
    let mut seen = 0usize;

    // Track the directories descended into: a well-formed tree reaches each exactly once, so
    // declining to re-descend a repeat bounds the walk against a cycle or a second name for
    // a directory rather than fanning out, and the family says whether the repeat is fatal.
    let mut visited: HashSet<W::Key> = HashSet::new();
    let (mut stack, seeded) = walk.seed().map_err(E::from)?;
    visited.extend(seeded);

    // The root's own children are the first frontier, and answer to the bound below like
    // every later one.
    if stack.len() > cap {
        return Err(E::from(W::too_large(cap)));
    }

    while let Some(pending) = stack.pop() {
        if seen >= cap {
            return Err(E::from(W::too_large(cap)));
        }
        seen += 1;
        let entry = walk.resolve(pending).map_err(E::from)?;
        // Descend into a subdirectory only the first time its identity is reached; a repeat
        // is a cycle or a second name for one directory, so re-descending would not
        // terminate, and the family judges it rather than this passing it over unasked.
        if let Some(key) = walk.descend_key(&entry) {
            if visited.insert(key) {
                let children = walk.children(&entry).map_err(E::from)?;
                // The cap bounds the names *pushed*, not only the names popped — see the
                // module documentation for why the difference matters.
                if seen
                    .saturating_add(stack.len())
                    .saturating_add(children.len())
                    > cap
                {
                    return Err(E::from(W::too_large(cap)));
                }
                stack.extend(children);
            } else {
                walk.repeated(&entry).map_err(E::from)?;
            }
        }
        visit(walk, entry)?;
    }
    Ok(())
}

/// The absolute path `name` has below `prefix`, or `None` where it would exceed
/// [`MAX_PATH`].
///
/// Every path a walk builds goes through here, so the bound holds for every family and the
/// separator is placed one way. The refusal is `None` rather than an error because the error
/// is the family's; each maps it to its own.
pub(crate) fn child_path(prefix: &[u8], name: &[u8]) -> Option<Vec<u8>> {
    let mut path = Vec::with_capacity(prefix.len() + 1 + name.len());
    path.extend_from_slice(prefix);
    path.push(b'/');
    path.extend_from_slice(name);
    (path.len() <= MAX_PATH).then_some(path)
}

/// What marks a scan's label as the end of a path rather than the whole of one.
#[cfg(any(feature = "fat", feature = "exfat", feature = "apfs"))]
const ELIDED: &[u8] = "\u{2026}".as_bytes();

/// What a scan calls `name` below `prefix`, which is the scan's own name for the directory
/// holding it: the absolute path while that is at most [`MAX_PATH`] bytes, and past it an
/// ellipsis and the path's last components, ending at `name`.
///
/// A scan reports what it finds by where it found it, and reads a tree however deep it nests:
/// a tree whose paths outgrow the ones a walk hands out is one every format here holds, and
/// one this crate's writers write. So a scan carries a label where a walk carries a path. A
/// label is at most [`MAX_PATH`] bytes, so what one costs stays the same however deep the
/// tree goes, where a path's cost grows with its depth and a deep tree's paths cost the scan
/// their sum.
#[cfg(any(feature = "fat", feature = "exfat", feature = "apfs"))]
pub(crate) fn label(prefix: &[u8], name: &[u8]) -> Vec<u8> {
    let mut label = Vec::with_capacity(prefix.len() + 1 + name.len());
    label.extend_from_slice(prefix);
    label.push(b'/');
    label.extend_from_slice(name);
    if label.len() <= MAX_PATH {
        return label;
    }
    // The last bytes the bound leaves room for beside the ellipsis, from the first separator
    // among them, so an elided label begins at a component as a path does.
    let tail = &label[label.len() - (MAX_PATH - ELIDED.len())..];
    let from = tail.iter().position(|&b| b == b'/').unwrap_or(0);
    let mut elided = Vec::with_capacity(ELIDED.len() + tail.len() - from);
    elided.extend_from_slice(ELIDED);
    elided.extend_from_slice(&tail[from..]);
    elided
}

/// The frontier the names `entries` make below `path`: each joined to it, with what the
/// family keeps to visit it later, in reverse order so a stack pops them in the order the
/// directory stores them.
///
/// A name no directory can hold stops the walk here rather than becoming a path, as `hostile`
/// says: a name carrying a separator would traverse out of its own directory in every path
/// built from it, which is what an extraction would then write. A path past the longest one
/// this crate builds is `too_long`, given the path as far as it went.
#[cfg(any(feature = "btrfs", feature = "apfs"))]
pub(crate) fn frontier<T, E>(
    path: &[u8],
    entries: impl IntoIterator<Item = (Vec<u8>, T)>,
    hostile: impl Fn(Vec<u8>) -> E,
    too_long: impl Fn(Vec<u8>) -> E,
) -> Result<Vec<(Vec<u8>, T)>, E> {
    frontier_by(path, entries, hostile, |path, name| {
        child_path(path, name).ok_or_else(|| {
            let mut long = path.to_vec();
            long.push(b'/');
            long.extend_from_slice(name);
            too_long(long)
        })
    })
}

/// The frontier a scan makes of the names `entries` below the directory it calls `prefix`:
/// [`frontier`]'s, with each name a [`label`] rather than a path, so no depth stops it.
#[cfg(feature = "apfs")]
pub(crate) fn labelled_frontier<T, E>(
    prefix: &[u8],
    entries: impl IntoIterator<Item = (Vec<u8>, T)>,
    hostile: impl Fn(Vec<u8>) -> E,
) -> Result<Vec<(Vec<u8>, T)>, E> {
    frontier_by(prefix, entries, hostile, |prefix, name| {
        Ok(label(prefix, name))
    })
}

/// The frontier `entries` make below `prefix`, each name joined to it by `join`, refusing a
/// name no directory can hold.
#[cfg(any(feature = "btrfs", feature = "apfs"))]
fn frontier_by<T, E>(
    prefix: &[u8],
    entries: impl IntoIterator<Item = (Vec<u8>, T)>,
    hostile: impl Fn(Vec<u8>) -> E,
    join: impl Fn(&[u8], &[u8]) -> Result<Vec<u8>, E>,
) -> Result<Vec<(Vec<u8>, T)>, E> {
    let mut out = Vec::new();
    for (name, keep) in entries {
        if crate::path::is_hostile_component(&name) {
            return Err(hostile(name));
        }
        out.push((join(prefix, &name)?, keep));
    }
    out.reverse();
    Ok(out)
}

#[cfg(test)]
mod tests {
    use super::{Seed, Walk, child_path, drive};
    use crate::policy::MAX_PATH;

    /// A tree of named directories by number, with the root as 0, and a refusal to give for
    /// a repeat or not.
    struct Graph {
        children: Vec<Vec<(&'static str, u32)>>,
        refuse: bool,
        repeats: Vec<Vec<u8>>,
    }

    impl Walk for Graph {
        type Pending = (Vec<u8>, u32);
        type Entry = (Vec<u8>, u32);
        type Key = u32;
        type Error = Vec<u8>;

        fn cap(&mut self) -> usize {
            100
        }

        fn seed(&mut self) -> Result<Seed<Self>, Vec<u8>> {
            let root = (Vec::new(), 0);
            Ok((self.children(&root)?, vec![0]))
        }

        fn resolve(&mut self, pending: (Vec<u8>, u32)) -> Result<(Vec<u8>, u32), Vec<u8>> {
            Ok(pending)
        }

        fn descend_key(&self, entry: &(Vec<u8>, u32)) -> Option<u32> {
            Some(entry.1)
        }

        fn children(&mut self, entry: &(Vec<u8>, u32)) -> Result<Vec<(Vec<u8>, u32)>, Vec<u8>> {
            Ok(self.children[entry.1 as usize]
                .iter()
                .rev()
                .map(|(name, number)| (child_path(&entry.0, name.as_bytes()).unwrap(), *number))
                .collect())
        }

        fn repeated(&mut self, entry: &(Vec<u8>, u32)) -> Result<(), Vec<u8>> {
            if self.refuse {
                return Err(entry.0.clone());
            }
            self.repeats.push(entry.0.clone());
            Ok(())
        }

        fn too_large(_: usize) -> Vec<u8> {
            b"too large".to_vec()
        }
    }

    #[test]
    fn a_directory_reached_again_is_judged_by_the_family_and_never_descended_twice() {
        // /a/b names the root: a cycle. A walk that passes it over yields every name once and
        // reports the repeat; one whose family refuses it stops there.
        let graph = |refuse| Graph {
            children: vec![vec![("a", 1)], vec![("b", 0)]],
            refuse,
            repeats: Vec::new(),
        };
        let mut lenient = graph(false);
        let mut seen = Vec::new();
        drive(
            &mut lenient,
            |_, entry: (Vec<u8>, u32)| -> Result<(), Vec<u8>> {
                seen.push(entry.0);
                Ok(())
            },
        )
        .expect("a lenient walk passes the repeat over");
        assert_eq!(seen, vec![b"/a".to_vec(), b"/a/b".to_vec()]);
        assert_eq!(lenient.repeats, vec![b"/a/b".to_vec()]);

        let mut strict = graph(true);
        let refused = drive(&mut strict, |_, _: (Vec<u8>, u32)| -> Result<(), Vec<u8>> {
            Ok(())
        });
        assert_eq!(refused, Err(b"/a/b".to_vec()));
    }

    #[cfg(any(feature = "fat", feature = "exfat", feature = "apfs"))]
    #[test]
    fn a_label_is_the_path_to_the_bound_and_the_end_of_it_past_the_bound() {
        use super::{ELIDED, label};

        assert_eq!(label(b"", b"etc"), b"/etc");
        assert_eq!(label(b"/etc", b"hostname"), b"/etc/hostname");
        // A label at the bound is the path itself, as a walk's path at the bound is.
        let at = vec![b'a'; MAX_PATH - 1];
        assert_eq!(label(b"", &at).len(), MAX_PATH);
        assert!(!label(b"", &at).starts_with(ELIDED));

        // Fifty levels of a hundred-byte name, and each label below the bound: the label is
        // the path until the path passes it, and past it the path's last whole components.
        let name = [b'n'; 100];
        let mut path = Vec::new();
        let mut labelled = Vec::new();
        for _ in 0..50 {
            path.push(b'/');
            path.extend_from_slice(&name);
            labelled = label(&labelled, &name);
            assert!(labelled.len() <= MAX_PATH);
            if path.len() <= MAX_PATH {
                assert_eq!(labelled, path);
            } else {
                let rest = labelled.strip_prefix(ELIDED).expect("an elided label");
                assert_eq!(
                    rest.first(),
                    Some(&b'/'),
                    "an elided label begins at a component"
                );
                assert!(path.ends_with(rest));
                // As many components as there is room for: one more would not fit.
                assert!(rest.len() + 1 + name.len() > MAX_PATH - ELIDED.len());
            }
        }
        assert_eq!(path.len(), 50 * 101);
    }

    #[test]
    fn a_child_path_joins_with_one_separator_and_stops_at_the_bound() {
        assert_eq!(child_path(b"", b"etc").as_deref(), Some(&b"/etc"[..]));
        assert_eq!(
            child_path(b"/etc", b"hostname").as_deref(),
            Some(&b"/etc/hostname"[..])
        );
        // The bound is on the whole path, and it is inclusive: a path exactly at the limit is
        // one a walk yields.
        let deep = vec![b'a'; MAX_PATH - 1];
        assert_eq!(child_path(b"", &deep).map(|p| p.len()), Some(MAX_PATH));
        assert_eq!(child_path(b"", &vec![b'a'; MAX_PATH]), None);
    }
}