rust-kernel

//! VFS (virtual file system): the layer every concrete file system plugs into.
//!
//! Modelled (very loosely) on Linux:
//!
//! * [`Inode`] -- one file or directory *inside some file system*. Knows how to
//!   read/write its bytes at an offset and (for directories) look up, create,
//!   list and remove children. ramfs, FAT32, ext2, exFAT and (read-only)
//!   btrfs implement it.
//! * [`FileSystem`] -- a mounted instance (e.g. "the FAT32 volume on vda1");
//!   gives you its root inode.
//! * the **mount table** -- which file system is attached at which path ("/",
//!   "/tmp", "/mnt/disk0"). `lookup("/tmp/x")` finds the longest matching
//!   mount point and walks the rest of the path from that file system's root.
//! * [`file::File`] -- an *open* file (what a file descriptor points to): an
//!   inode plus a current offset, or the console, or a pipe. The per-process
//!   fd table holds `Arc<dyn File>`s, so syscalls don't care what's behind it.
//!
//! Paths: every path is first turned into a clean absolute path by
//! [`normalize`] (relative paths are joined to the process's current
//! directory; ".", ".." and "//" are resolved by plain string processing).
//! That makes ".." work across mount points for free. Real kernels track
//! parent dentries instead.
//!
//! Symlinks (ext2 has them): [`lookup`] follows them. When a path component
//! is a symlink, its target is joined to the directory the link is in, the
//! rest of the path is appended, and the lookup starts over (at most 8
//! times, then ELOOP). Since ".." is handled as text, `link/..` is the
//! directory holding `link`, not the parent of the link's target. Linux does
//! the latter; ours is simpler and fine for a hobby kernel.

pub mod btrfs;
pub mod exfat;
pub mod lzo;
pub mod ext2;
pub mod fat;
pub mod file;
pub mod pipe;
pub mod ramfs;

use crate::errno::Errno;
use alloc::{format, string::String, sync::Arc, vec::Vec};
use spin::Mutex;

#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum InodeKind {
    File,
    Directory,
    /// A symbolic link: a small file holding a path ([`Inode::readlink`]).
    Symlink,
    /// A device file in /dev (opening it gives the driver's own `File`).
    Device,
}

/// One entry of a directory listing.
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct DirEntry {
    pub name: String,
    pub kind: InodeKind,
}

/// A file or directory inside a file system.
///
/// Default method bodies return the error a "wrong kind" of inode would give
/// (e.g. `lookup` on a file -> ENOTDIR), so implementations only override
/// what makes sense for them.
pub trait Inode: Send + Sync {
    fn kind(&self) -> InodeKind;
    /// Size in bytes (files) or number of entries (directories).
    fn size(&self) -> usize;
    /// Unix permission bits like 0o644, or 0 if the file system has none
    /// (FAT, ramfs).
    fn mode(&self) -> u32 {
        0
    }
    /// The target path of a symlink.
    fn readlink(&self) -> Result<String, Errno> {
        Err(Errno::EINVAL)
    }
    /// Read bytes starting at `offset`; returns how many were read (0 = EOF).
    fn read_at(&self, _offset: usize, _buf: &mut [u8]) -> Result<usize, Errno> {
        Err(Errno::EISDIR)
    }
    /// Write bytes at `offset` (growing the file if needed).
    fn write_at(&self, _offset: usize, _buf: &[u8]) -> Result<usize, Errno> {
        Err(Errno::EISDIR)
    }
    /// Cut the file to length 0 (for `open(..., O_TRUNC)`, i.e. shell `>`).
    fn truncate(&self) -> Result<(), Errno> {
        Err(Errno::EISDIR)
    }
    /// Find a child of this directory by name.
    fn lookup(&self, _name: &str) -> Result<Arc<dyn Inode>, Errno> {
        Err(Errno::ENOTDIR)
    }
    /// Create a child of this directory.
    fn create(&self, _name: &str, _kind: InodeKind) -> Result<Arc<dyn Inode>, Errno> {
        Err(Errno::ENOTDIR)
    }
    /// All children of this directory (without "." and "..").
    fn list(&self) -> Result<Vec<DirEntry>, Errno> {
        Err(Errno::ENOTDIR)
    }
    /// Delete a child (a file, or an *empty* directory).
    fn remove(&self, _name: &str) -> Result<(), Errno> {
        Err(Errno::ENOTDIR)
    }
    /// Device files: the `File` that `open` should return (None = an
    /// ordinary inode, opened as an `InodeFile`).
    fn open_device(&self) -> Result<Option<Arc<dyn file::File>>, Errno> {
        Ok(None)
    }
}

/// A mounted file system.
pub trait FileSystem: Send + Sync {
    /// Type name, like the `-t` argument of `mount` ("ramfs", "fat32", ...).
    fn name(&self) -> &'static str;
    fn root(&self) -> Arc<dyn Inode>;
}

struct Mount {
    path: String, // normalized, e.g. "/" or "/tmp"
    fs: Arc<dyn FileSystem>,
}

/// The mount table. Lookups take the lock only briefly (never while doing
/// I/O), so it's fine as a spinlock. Not used from interrupt handlers.
static MOUNTS: Mutex<Vec<Mount>> = Mutex::new(Vec::new());

/// Attach `fs` at `path` (absolute, like "/" or "/tmp").
pub fn mount(path: &str, fs: Arc<dyn FileSystem>) -> Result<(), Errno> {
    if !path.starts_with('/') {
        return Err(Errno::EINVAL);
    }
    let path = normalize("/", path)?;
    let mut mounts = MOUNTS.lock();
    if mounts.iter().any(|m| m.path == path) {
        return Err(Errno::EEXIST);
    }
    mounts.push(Mount { path, fs });
    Ok(())
}

/// (mount path, fs type) of every mount, for printing.
pub fn mounts() -> Vec<(String, &'static str)> {
    MOUNTS.lock().iter().map(|m| (m.path.clone(), m.fs.name())).collect()
}

/// Does mount point `mount` contain `path`? ("/tmp" contains "/tmp/x" but
/// not "/tmpfoo"; "/" contains everything.)
fn mount_contains(mount: &str, path: &str) -> bool {
    mount == "/"
        || path == mount
        || (path.starts_with(mount) && path.as_bytes().get(mount.len()) == Some(&b'/'))
}

/// Turn `path` into a clean absolute path. Relative paths start at `cwd`
/// (which must be absolute). "." is dropped, ".." removes the previous
/// component (".." of "/" is "/", like Unix).
///   normalize("/home", "../etc//motd") == "/etc/motd"
pub fn normalize(cwd: &str, path: &str) -> Result<String, Errno> {
    if path.is_empty() {
        return Err(Errno::ENOENT); // like Linux: "" is not a path
    }
    let mut parts: Vec<&str> = Vec::new();
    let joined = if path.starts_with('/') { String::from(path) } else { format!("{}/{}", cwd, path) };
    for component in joined.split('/') {
        match component {
            "" | "." => {}
            ".." => {
                parts.pop();
            }
            name if name.len() > 255 => return Err(Errno::ENAMETOOLONG),
            name => parts.push(name),
        }
    }
    let result = format!("/{}", parts.join("/"));
    if result.len() > 4096 {
        return Err(Errno::ENAMETOOLONG);
    }
    Ok(result)
}

/// Resolve an absolute path to an inode, following symlinks.
pub fn lookup(path: &str) -> Result<Arc<dyn Inode>, Errno> {
    walk(path, true, 0)
}

/// Like [`lookup`], but if the *last* component is a symlink, return the
/// link itself (for `readlink`, and for deleting a link, not its target).
pub fn lookup_nofollow(path: &str) -> Result<Arc<dyn Inode>, Errno> {
    walk(path, false, 0)
}

/// The target of the symlink at absolute `path`.
pub fn readlink(path: &str) -> Result<String, Errno> {
    lookup_nofollow(path)?.readlink()
}

/// How many symlinks one lookup may follow (Linux allows 40).
const MAX_SYMLINKS: usize = 8;

fn walk(path: &str, follow_last: bool, links_followed: usize) -> Result<Arc<dyn Inode>, Errno> {
    if !path.starts_with('/') {
        return Err(Errno::EINVAL); // callers resolve relative paths first
    }
    let path = normalize("/", path)?;
    // Longest mount point that contains the path wins.
    let (root, mount_path, rest) = {
        let mounts = MOUNTS.lock();
        let m = mounts
            .iter()
            .filter(|m| mount_contains(&m.path, &path))
            .max_by_key(|m| m.path.len())
            .ok_or(Errno::ENOENT)?;
        let rest = String::from(if m.path == "/" { &path[..] } else { &path[m.path.len()..] });
        (m.fs.root(), m.path.clone(), rest)
    };
    // Walk the remaining components ("a/b/c") from that file system's root.
    let names: Vec<&str> = rest.split('/').filter(|c| !c.is_empty()).collect();
    let mut inode = root;
    let mut dir = mount_path; // absolute path of `inode` so far
    for (i, name) in names.iter().enumerate() {
        let child = inode.lookup(name)?;
        let last = i + 1 == names.len();
        if child.kind() == InodeKind::Symlink && (follow_last || !last) {
            if links_followed == MAX_SYMLINKS {
                return Err(Errno::ELOOP);
            }
            // Replace "dir/link/rest..." by "dir/<target>/rest..." and start over.
            let mut new_path = normalize(&dir, &child.readlink()?)?;
            for rest in &names[i + 1..] {
                new_path.push('/');
                new_path.push_str(rest);
            }
            return walk(&new_path, follow_last, links_followed + 1);
        }
        dir = if dir == "/" { format!("/{}", name) } else { format!("{}/{}", dir, name) };
        inode = child;
    }
    Ok(inode)
}

/// Split a normalized path into (parent directory inode, last component).
fn parent_of(path: &str) -> Result<(Arc<dyn Inode>, String), Errno> {
    let path = normalize("/", path)?;
    let (parent, name) = path.rsplit_once('/').ok_or(Errno::EINVAL)?;
    if name.is_empty() {
        return Err(Errno::EEXIST); // "/" itself
    }
    Ok((lookup(if parent.is_empty() { "/" } else { parent })?, String::from(name)))
}

/// Create a file or directory at absolute `path` (parent must exist).
pub fn create(path: &str, kind: InodeKind) -> Result<Arc<dyn Inode>, Errno> {
    let (parent, name) = parent_of(path)?;
    parent.create(&name, kind)
}

/// Delete the file (`want_dir` false, like `unlink`) or empty directory
/// (`want_dir` true, like `rmdir`) at absolute `path`.
pub fn remove(path: &str, want_dir: bool) -> Result<(), Errno> {
    let normalized = normalize("/", path)?;
    if MOUNTS.lock().iter().any(|m| m.path == normalized) {
        return Err(Errno::EBUSY); // can't delete a mount point
    }
    // Don't follow a symlink here: `rm link` deletes the link.
    let inode = lookup_nofollow(&normalized)?;
    match (inode.kind(), want_dir) {
        (InodeKind::Directory, false) => return Err(Errno::EISDIR),
        (InodeKind::File | InodeKind::Symlink, true) => return Err(Errno::ENOTDIR),
        _ => {}
    }
    let (parent, name) = parent_of(&normalized)?;
    parent.remove(&name)
}

/// The mount point `path` (absolute, normalized) lives under.
fn mount_of(path: &str) -> Option<String> {
    let mounts = MOUNTS.lock();
    mounts.iter().filter(|m| mount_contains(&m.path, path)).max_by_key(|m| m.path.len()).map(|m| m.path.clone())
}

/// rename(old, new). Our `Inode` trait has no "move this entry" operation
/// yet, so we do it the long way, which is enough for what programs use
/// rename for (save to a temp file, then rename it over the real one):
///   - a file: copy its bytes to `new` (replacing a file there), then
///     delete `old`;
///   - an empty directory: create `new` (or reuse an empty one), delete `old`;
///   - anything else (a non-empty directory, a symlink, a device), or
///     across file systems: EXDEV, which tells `mv` to copy and delete
///     itself, like Linux does across file systems.
/// Not atomic, unlike Linux's: a crash in the middle can leave both.
pub fn rename(old: &str, new: &str) -> Result<(), Errno> {
    let (old, new) = (normalize("/", old)?, normalize("/", new)?);
    let src = lookup_nofollow(&old)?;
    if old == new {
        return Ok(());
    }
    if new.starts_with(&old) && new.as_bytes().get(old.len()) == Some(&b'/') {
        return Err(Errno::EINVAL); // a directory into itself
    }
    if MOUNTS.lock().iter().any(|m| m.path == old || m.path == new) {
        return Err(Errno::EBUSY);
    }
    if mount_of(&old) != mount_of(&new) {
        return Err(Errno::EXDEV);
    }
    let existing = lookup_nofollow(&new).ok();
    match src.kind() {
        InodeKind::File => {
            if let Some(dst) = &existing {
                if dst.kind() == InodeKind::Directory {
                    return Err(Errno::EISDIR);
                }
                remove(&new, false)?;
            }
            let data = read_all(&old)?;
            let dst = create(&new, InodeKind::File)?;
            let mut done = 0;
            while done < data.len() {
                done += dst.write_at(done, &data[done..])?;
            }
            remove(&old, false)
        }
        InodeKind::Directory => {
            if !src.list()?.is_empty() {
                return Err(Errno::EXDEV);
            }
            match &existing {
                Some(dst) if dst.kind() != InodeKind::Directory => return Err(Errno::ENOTDIR),
                Some(dst) if !dst.list()?.is_empty() => return Err(Errno::ENOTEMPTY),
                Some(_) => {}
                None => {
                    create(&new, InodeKind::Directory)?;
                }
            }
            remove(&old, true)
        }
        _ => Err(Errno::EXDEV),
    }
}

/// Read a whole file into memory (used to load programs).
pub fn read_all(path: &str) -> Result<Vec<u8>, Errno> {
    let inode = lookup(path)?;
    if inode.kind() == InodeKind::Directory {
        return Err(Errno::EISDIR);
    }
    let mut data = alloc::vec![0u8; inode.size()];
    let mut done = 0;
    while done < data.len() {
        match inode.read_at(done, &mut data[done..])? {
            0 => break,
            n => done += n,
        }
    }
    data.truncate(done);
    Ok(data)
}

/// Boot-time file system setup: a ramfs as "/", with a few files, and a
/// second, empty ramfs mounted at "/tmp" (to exercise the mount table).
pub fn init() {
    let root = ramfs::RamFs::new();
    let dir = root.root();
    let hello = dir.create("hello.txt", InodeKind::File).unwrap();
    hello.write_at(0, b"Hello from the ramfs! This is /hello.txt.\n").unwrap();
    let etc = dir.create("etc", InodeKind::Directory).unwrap();
    let motd = etc.create("motd", InodeKind::File).unwrap();
    motd.write_at(0, b"Welcome to Tyler's kernel. Next up: SMP, then networking.\n").unwrap();
    dir.create("tmp", InodeKind::Directory).unwrap(); // mount point
    dir.create("mnt", InodeKind::Directory).unwrap(); // disks go to /mnt/diskN
    dir.create("dev", InodeKind::Directory).unwrap(); // device files (dev.rs)
    mount("/", root).unwrap();
    mount("/tmp", ramfs::RamFs::new()).unwrap();
    mount("/dev", Arc::new(crate::dev::DevFs)).unwrap();
}

/// Try to mount every registered partition (and unpartitioned disk) at
/// /mnt/disk0, /mnt/disk1, ... Returns log lines.
///
/// Which driver? Like Linux's `mount` without `-t`, we look for each file
/// system's *magic number*: ext2 has 0xEF53 at byte 56 of its superblock
/// (which starts at byte 1024); exFAT says "EXFAT   " at byte 3 of its boot
/// sector; btrfs has "_BHRfS_M" at byte 64 of its superblock (at 64 KiB);
/// anything else is tried as FAT (fatfs checks the boot sector itself).
/// A disk whose driver refuses it (say, a btrfs with sha256 checksums)
/// gets a log line saying why, and no /mnt/diskN.
pub fn mount_disks() -> Vec<String> {
    let mut log = Vec::new();
    let devices = crate::block::devices();
    let mut n = 0;
    for (name, dev) in &devices {
        // Skip a whole disk if it has partitions ("vda" when "vda1" exists).
        let has_partitions = devices.iter().any(|(other, _)| other.len() > name.len() && other.starts_with(name.as_str()));
        if has_partitions {
            continue;
        }
        let path = format!("/mnt/disk{}", n);
        let (fs, description): (Arc<dyn FileSystem>, String) = if ext2::probe(&**dev) {
            match ext2::Ext2Fs::mount(dev.clone()) {
                Ok(fs) => {
                    let d = fs.describe();
                    (fs, d)
                }
                Err(e) => {
                    log.push(format!("{}: ext2, but can't mount it: {:?}", name, e));
                    continue;
                }
            }
        } else if exfat::probe(&**dev) {
            match exfat::ExfatFs::mount(dev.clone()) {
                Ok(fs) => {
                    let d = fs.describe();
                    (fs, d)
                }
                Err(e) => {
                    log.push(format!("{}: exFAT, but can't mount it: {:?}", name, e));
                    continue;
                }
            }
        } else if btrfs::probe(&**dev) {
            match btrfs::BtrfsFs::mount(dev.clone()) {
                Ok(fs) => {
                    let d = fs.describe();
                    (fs, d)
                }
                Err(e) => {
                    log.push(format!("{}: btrfs, but can't mount it: {}", name, e));
                    continue;
                }
            }
        } else {
            match fat::FatFs::mount(dev.clone()) {
                Ok(fs) => {
                    let d = format!("FAT32 volume \"{}\"", fs.label());
                    (fs, d)
                }
                Err(e) => {
                    log.push(format!("{}: no file system we know ({:?})", name, e));
                    continue;
                }
            }
        };
        let _ = create(&path, InodeKind::Directory); // mount point (may exist)
        match mount(&path, fs) {
            Ok(()) => log.push(format!("{}: {} mounted at {}", name, description, path)),
            Err(e) => log.push(format!("{}: mount at {} failed: {:?}", name, path, e)),
        }
        n += 1;
    }
    log
}