rust-kernel

//! btrfs (read-only) through the VFS. Cargo.toml's test-args attach these
//! images that build.rs makes (snapshot=on: the corruption test at the end
//! damages a disk on purpose, and that vanishes when QEMU exits):
//!
//!   vdd  target/btrfs.img          /mnt/disk3  zlib, 16 KiB nodes, metadata DUP
//!   vdh  target/btrfs-lzo.img      /mnt/disk7  lzo, 4 KiB nodes (a 2-level tree)
//!   vdi  target/btrfs-zstd.img     /mnt/disk8  zstd, 64 KiB nodes
//!   vdj  target/btrfs-convert.img  /mnt/disk9  btrfs-convert'ed ext2: holes,
//!                                              shared extents, ext2_saved
//!   vdk  target/btrfs-sha256.img   (refused)   sha256 checksums
//!
//! The first three hold the same tree (disk4/ plus big.txt, random.bin...)
//! with subvolumes `archive` (256, read-only) and `projects` (257).
//!
//! The main test reads *every* file and compares its size and CRC-32 with
//! the manifests build.rs wrote from the host's copy. It also prints one
//! `[btrfs-file]` line per file, which scripts/btrfs-check.sh compares
//! again, independently, against Python's zlib.crc32 of the host files.
#![no_std]
#![no_main]
#![feature(custom_test_frameworks)]
#![test_runner(rustbelt::test_runner)]
#![reexport_test_harness_main = "test_main"]

extern crate alloc;

use alloc::{format, string::String, vec, vec::Vec};
use bootloader::{BootInfo, entry_point};
use core::panic::PanicInfo;
use rustbelt::block;
use rustbelt::errno::Errno;
use rustbelt::fs::btrfs::{BtrfsFs, Subvolume};
use rustbelt::fs::{self, InodeKind};
use rustbelt::serial_println;

entry_point!(main);

fn main(boot_info: &'static BootInfo) -> ! {
    rustbelt::init();
    rustbelt::init_memory(boot_info);
    rustbelt::init_smp(); // all 4 CPUs run threads
    fs::init();
    rustbelt::init_storage();
    test_main();
    rustbelt::hlt_loop();
}

const E: &str = "/mnt/disk3";
const LZO: &str = "/mnt/disk7";
const ZSTD: &str = "/mnt/disk8";
const CONVERT: &str = "/mnt/disk9";

const TREE: &str = include_str!("../target/btrfs-tree.manifest");
const CONVERT_TREE: &str = include_str!("../target/btrfs-convert.manifest");

/// CRC-32 (IEEE, as zlib and the manifests use), bit by bit: slow but
/// obviously right, and independent of the driver's crc32c.
fn crc32(crc: u32, data: &[u8]) -> u32 {
    let mut crc = !crc;
    for &b in data {
        crc ^= b as u32;
        for _ in 0..8 {
            crc = if crc & 1 != 0 { (crc >> 1) ^ 0xEDB8_8320 } else { crc >> 1 };
        }
    }
    !crc
}

/// build.rs's random.bin generator.
fn noise(len: usize) -> Vec<u8> {
    let mut x: u64 = 0x2545_F491_4F6C_DD1D;
    (0..len)
        .map(|_| {
            x = x.wrapping_mul(6364136223846793005).wrapping_add(1442695040888963407);
            (x >> 33) as u8
        })
        .collect()
}

fn read(path: &str, offset: usize, len: usize) -> Vec<u8> {
    let mut buf = vec![0u8; len];
    let n = fs::lookup(path).unwrap().read_at(offset, &mut buf).unwrap();
    buf.truncate(n);
    buf
}

/// (size, CRC-32) of a file, read in 64 KiB pieces like `cat` would.
fn checksum(path: &str) -> (usize, u32) {
    let inode = fs::lookup(path).unwrap();
    let (mut at, mut crc, mut buf) = (0, 0, vec![0u8; 65536]);
    loop {
        let n = inode.read_at(at, &mut buf).unwrap();
        if n == 0 {
            return (at, crc);
        }
        crc = crc32(crc, &buf[..n]);
        at += n;
    }
}

/// Walk a mounted volume and describe it in the manifest's format. Paths
/// the manifest lists as `S` (size only) are not read.
fn walk(mount: &str, rel: &str, manifest: &str, out: &mut Vec<String>) {
    let dir = if rel.is_empty() { String::from(mount) } else { format!("{}/{}", mount, rel) };
    for entry in fs::lookup(&dir).unwrap().list().unwrap() {
        let path = if rel.is_empty() { entry.name.clone() } else { format!("{}/{}", rel, entry.name) };
        let full = format!("{}/{}", mount, path);
        let line = match entry.kind {
            InodeKind::Directory => {
                walk(mount, &path, manifest, out);
                format!("D\t{}", path)
            }
            InodeKind::Symlink => format!("L\t{}\t{}", path, fs::readlink(&full).unwrap()),
            _ if manifest.lines().any(|l| l == format!("S\t{}\t{}", path, l.rsplit('\t').next().unwrap())) => {
                format!("S\t{}\t{}", path, fs::lookup(&full).unwrap().size())
            }
            _ => {
                let (size, crc) = checksum(&full);
                assert_eq!(size, fs::lookup(&full).unwrap().size(), "{}", full);
                format!("F\t{}\t{}\t{:08x}", path, size, crc)
            }
        };
        serial_println!("[btrfs-file] {}\t{}", mount, line);
        out.push(line);
    }
}

fn matches_manifest(mount: &str, manifest: &str) {
    let mut got = Vec::new();
    walk(mount, "", manifest, &mut got);
    // Both sides sorted by path (the second field), like build.rs does.
    let path = |l: &str| String::from(l.split('\t').nth(1).unwrap());
    got.sort_by_key(|l| path(l));
    let mut want: Vec<&str> = manifest.lines().collect();
    want.sort_by_key(|l| path(l));
    assert_eq!(got, want, "{} differs from the host's tree", mount);
}

#[test_case]
fn mounted_as_btrfs() {
    let mounts = fs::mounts();
    for path in [E, LZO, ZSTD, CONVERT] {
        assert!(mounts.iter().any(|(p, name)| p == path && *name == "btrfs"), "{} not btrfs", path);
    }
    // vdk (sha256) was refused, so nothing got /mnt/disk10.
    assert!(!mounts.iter().any(|(p, _)| p == "/mnt/disk10"));
    let describe = |dev: &str| BtrfsFs::mount(block::get(dev).unwrap()).unwrap().describe();
    assert_eq!(describe("vdd"), "btrfs volume \"TYLERBTRFS\" (16 KiB nodes, metadata DUP, data single, 2 subvolumes, read-only)");
    assert_eq!(describe("vdh"), "btrfs volume \"LZO4K\" (4 KiB nodes, metadata single, data single, 2 subvolumes, read-only)");
    assert_eq!(describe("vdi"), "btrfs volume \"ZSTD64K\" (64 KiB nodes, metadata DUP, data single, 2 subvolumes, read-only)");
    assert_eq!(describe("vdj"), "btrfs volume \"CONVERTED\" (16 KiB nodes, metadata single, data single, 1 subvolume, read-only)");
    let (sector, node, _, total, used) = BtrfsFs::mount(block::get("vdd").unwrap()).unwrap().geometry();
    assert_eq!((sector, node, total), (4096, 16384, 128 << 20));
    // random.bin (1.5 MB) is stored as it is; the rest compresses well.
    assert!(used > 1_500_000 && used < 8_000_000, "bytes used {}", used);
}

#[test_case]
fn every_file_matches_the_host_zlib() {
    matches_manifest(E, TREE);
}

#[test_case]
fn every_file_matches_the_host_lzo() {
    matches_manifest(LZO, TREE);
}

#[test_case]
fn every_file_matches_the_host_zstd() {
    matches_manifest(ZSTD, TREE);
}

#[test_case]
fn every_file_matches_the_host_converted() {
    matches_manifest(CONVERT, CONVERT_TREE);
}

#[test_case]
fn holes_and_the_saved_ext2_image() {
    // sparse.bin: three bits of text in 5 MiB of holes.
    let path = format!("{}/sparse.bin", CONVERT);
    assert_eq!(read(&path, 0, 19), b"start of sparse.bin");
    assert_eq!(read(&path, 19, 4096), [0u8; 4096]); // rest of the first block
    assert_eq!(read(&path, (1 << 20) - 3, 13), b"\0\0\0one MiB in");
    assert_eq!(read(&path, 3 << 20, 8), [0u8; 8]); // deep inside a hole
    assert_eq!(read(&path, (5 << 20) - 10, 100), b"\0\0\0the end"); // short read at EOF
    // ext2_saved/image is the old ext2 file system, sharing its extents
    // with the converted files: the ext2 magic is where it should be.
    let image = format!("{}/ext2_saved/image", CONVERT);
    assert_eq!(read(&image, 1024 + 56, 2), [0x53, 0xEF]);
    let saved = BtrfsFs::mount(block::get("vdj").unwrap()).unwrap().subvolumes().unwrap();
    assert_eq!(saved.len(), 1);
    assert_eq!((saved[0].path.as_str(), saved[0].read_only), ("ext2_saved", false));
}

#[test_case]
fn reads_across_extent_boundaries() {
    // big.txt is line i = "btrfs line {i:06}\n" (18 bytes) at 18 * i, in
    // 128 KiB compressed extents; random.bin is stored as 1 MiB plain extents.
    let big = |at: usize, len: usize| -> Vec<u8> {
        let lines: String = (at / 18..(at + len) / 18 + 1).map(|i| format!("btrfs line {:06}\n", i)).collect();
        lines.as_bytes()[at % 18..at % 18 + len].to_vec()
    };
    let random = noise(1_500_000);
    for dir in [E, LZO, ZSTD] {
        for (at, len) in [(0, 18), (131072 - 5, 40), (2 * 131072 - 1, 3), (1_000_000, 70000), (2_160_000 - 18, 18)] {
            assert_eq!(read(&format!("{}/big.txt", dir), at, len), big(at, len), "{} big.txt at {}", dir, at);
        }
        for (at, len) in [(1 << 20) - 100, 4096 * 3 + 1, 1_499_990].into_iter().zip([200, 5000, 10]) {
            assert_eq!(read(&format!("{}/random.bin", dir), at, len), random[at..at + len], "{} random.bin at {}", dir, at);
        }
        assert_eq!(read(&format!("{}/zeros.bin", dir), 500_000, 1000), [0u8; 1000]);
        assert_eq!(read(&format!("{}/empty.txt", dir), 0, 10), b"");
    }
}

#[test_case]
fn lookups_symlinks_and_subvolumes() {
    // DIR_ITEM lookups are by crc32c hash: exact names only.
    assert!(read(&format!("{}/hello.txt", E), 0, 100).starts_with(b"Hello from btrfs!"));
    assert_eq!(fs::lookup(&format!("{}/HELLO.TXT", E)).err(), Some(Errno::ENOENT));
    assert_eq!(fs::lookup(&format!("{}/Music/Road Trip/playlist.txt", E)).unwrap().size(), 66);
    assert_eq!(fs::lookup(&format!("{}/hello.txt/x", E)).err(), Some(Errno::ENOTDIR));
    // Symlinks, including one from inside a subvolume back out of it.
    assert_eq!(fs::readlink(&format!("{}/docs/cow-link", E)).unwrap(), "btrfs/cow.txt");
    assert_eq!(read(&format!("{}/hello-link", E), 0, 17), b"Hello from btrfs!");
    assert_eq!(read(&format!("{}/projects/hello-link", E), 0, 17), b"Hello from btrfs!");
    assert_eq!(fs::lookup_nofollow(&format!("{}/hello-link", E)).unwrap().kind(), InodeKind::Symlink);
    // Into the subvolumes: separate trees, each with its own inode 256.
    assert!(read(&format!("{}/projects/rustbelt/stage10.txt", E), 0, 200).len() == 127);
    assert!(read(&format!("{}/archive/2025-notes.txt", E), 0, 200).len() == 136);
    let names = |p: &str| {
        let mut v: Vec<String> = fs::lookup(p).unwrap().list().unwrap().into_iter().map(|e| e.name).collect();
        v.sort();
        v
    };
    assert_eq!(names(&format!("{}/projects", E)), ["README.txt", "hello-link", "rustbelt"]);
    let want = vec![
        // mkfs.btrfs numbers them in its own order, not the command line's.
        Subvolume { id: 256, path: "archive".into(), read_only: true },
        Subvolume { id: 257, path: "projects".into(), read_only: false },
    ];
    for dev in ["vdd", "vdh", "vdi"] {
        assert_eq!(BtrfsFs::mount(block::get(dev).unwrap()).unwrap().subvolumes().unwrap(), want);
    }
    // Directory permissions come through (mkfs copies the host's).
    assert_eq!(fs::lookup(&format!("{}/docs", E)).unwrap().kind(), InodeKind::Directory);
}

#[test_case]
fn sha256_volume_is_refused_with_a_reason() {
    let err = BtrfsFs::mount(block::get("vdk").unwrap()).err().unwrap();
    assert_eq!(err, "checksum type 2 (sha256) is not supported, only crc32c");
}

#[test_case]
fn writes_are_refused() {
    let hello = format!("{}/hello.txt", E);
    let before = fs::read_all(&hello).unwrap();
    let file = fs::lookup(&hello).unwrap();
    assert_eq!(file.write_at(0, b"overwritten"), Err(Errno::EROFS));
    assert_eq!(file.truncate(), Err(Errno::EROFS));
    assert_eq!(fs::create(&format!("{}/new.txt", E), InodeKind::File).err(), Some(Errno::EROFS));
    assert_eq!(fs::create(&format!("{}/docs/newdir", E), InodeKind::Directory).err(), Some(Errno::EROFS));
    assert_eq!(fs::remove(&hello, false), Err(Errno::EROFS));
    assert_eq!(fs::remove(&format!("{}/docs/btrfs", E), true), Err(Errno::EROFS));
    assert_eq!(fs::read_all(&hello).unwrap(), before);
}

/// Flip one byte on the disk, under the driver's feet.
fn damage(dev: &str, at: u64) {
    let dev = block::get(dev).unwrap();
    let mut sector = [0u8; 512];
    dev.read_sectors(at / 512, &mut sector).unwrap();
    sector[(at % 512) as usize] ^= 0xFF;
    dev.write_sectors(at / 512, &sector).unwrap();
}

/// Last (alphabetically, so last to run): it damages vdi (zstd, metadata
/// DUP), which no other test reads afterwards.
#[test_case]
fn zz_checksums_catch_damage() {
    let fresh = || BtrfsFs::mount(block::get("vdi").unwrap()).unwrap(); // no cached nodes
    let read_via = |fs: &BtrfsFs, path: &str, at: usize, len: usize| -> Result<Vec<u8>, Errno> {
        use rustbelt::fs::FileSystem;
        let mut inode = fs.root();
        for name in path.split('/') {
            inode = inode.lookup(name)?;
        }
        let mut buf = vec![0u8; len];
        let n = inode.read_at(at, &mut buf)?;
        buf.truncate(n);
        Ok(buf)
    };
    let fs = fresh();
    let leaf = fs.fs_tree_root();
    let copies = fs.physical(leaf);
    assert_eq!(copies.len(), 2, "metadata should be DUP");
    let data = fs.physical(fs.first_extent("random.bin").unwrap());
    assert_eq!(data.len(), 1, "data should be single");

    // 1. Damage copy 0 of the FS tree's root: copy 1 still works.
    damage("vdi", copies[0] + 300);
    assert_eq!(read_via(&fresh(), "hello.txt", 0, 17).unwrap(), b"Hello from btrfs!");
    // 2. A damaged data sector: that sector fails with EIO, others don't.
    damage("vdi", data[0] + 100);
    let fs = fresh();
    assert_eq!(read_via(&fs, "random.bin", 0, 10), Err(Errno::EIO));
    assert_eq!(read_via(&fs, "random.bin", 8192, 10).unwrap(), noise(8202)[8192..]);
    // 3. Both copies of the node damaged: nothing to fall back to.
    damage("vdi", copies[1] + 300);
    assert_eq!(read_via(&fresh(), "hello.txt", 0, 17).err(), Some(Errno::EIO));
}

#[panic_handler]
fn panic(info: &PanicInfo) -> ! {
    rustbelt::test_panic_handler(info)
}