rust-kernel

//! Build script, two jobs:
//!
//! 0. Compile the vDSO (vdso/, stage 19) into OUT_DIR/vdso.so.
//!
//! 1. Compile the user programs in user/ into ELF executables in OUT_DIR
//!    (stage 19: also C programs against musl, see `MUSL_PROGRAMS`).
//!    They're compiled with plain `rustc` for the built-in
//!    `x86_64-unknown-none` target (prebuilt `core`, so no build-std
//!    needed), as static executables (`relocation-model=static`) linked at a
//!    high user address -- which needs the `large` code model (the default
//!    ones assume code in the low/high 2 GiB).
//!
//! 2. Build the second QEMU disk, `target/disk.img` (64 MiB):
//!      * a GPT partition table (made with `sfdisk`) with one partition
//!        starting at sector 2048 (1 MiB, the usual alignment),
//!      * in it a FAT32 file system (`mkfs.vfat`), filled with `mtools`
//!        (`mmd`/`mcopy` write into an image file directly -- no root, no
//!        loop-mounting needed): everything in disk/ plus the user programs
//!        in /bin.
//!    The kernel finds the disk on the PCI bus, reads the GPT, mounts the
//!    FAT32 partition at /mnt/disk0 and loads programs from /mnt/disk0/bin.
//!    QEMU opens it with `snapshot=on`, so the kernel's writes never change
//!    this file (every boot and every test starts from the same disk).
//!
//! 3. Build the third QEMU disk, `target/ext2.img` (32 MiB): a whole-disk
//!    ext2 file system (no partition table) made by `mke2fs -d`, which
//!    copies a directory tree into the new file system. The tree is disk2/
//!    plus generated files: big.txt (big enough for double-indirect blocks),
//!    sparse.bin (66 MiB of mostly holes, reaching the triple-indirect
//!    blocks), and two symlinks (one short = "fast", one long = "slow").
//!    Mounted at /mnt/disk1 (drive C: in the shell).
//!    Two more small images are for `cargo test` only (see Cargo.toml
//!    test-args): ext2-4k.img (4 KiB blocks) and ext2-rev0.img (the original
//!    1993 revision 0 format: fixed 128-byte inodes, no file types in
//!    directory entries).
//!
//! 4. Build the fourth QEMU disk, `target/exfat.img` (32 MiB): a whole-disk
//!    exFAT file system. `mkfs.exfat` formats it, but no tool can copy files
//!    into an exFAT image without mounting it (root or a loop device), so
//!    build/exfat_populate.rs does that itself: a small exFAT writer of its
//!    own, separate from the kernel's driver. The tree is disk3/ (long
//!    names with spaces, mixed case, non-ASCII) plus numbers.txt (340 KB,
//!    contiguous) and frag-chain.txt (fragmented, linked through the FAT).
//!    Mounted at /mnt/disk2 (drive D:). exfat-512.img (512-byte clusters,
//!    so everything spans many clusters) is for `cargo test` only.
//!
//! 5. Build the fifth QEMU disk, `target/btrfs.img` (128 MiB): a btrfs file
//!    system made by `mkfs.btrfs --rootdir`, which (like `mke2fs -d`) copies
//!    a directory tree in. The tree is disk4/ plus generated files: big.txt
//!    (2 MiB of text: many compressed extents), random.bin (incompressible,
//!    so stored uncompressed), zeros.bin, empty.txt and symlinks.
//!    `--compress zlib` compresses it; `-u projects -u ro:archive` turns
//!    those two directories into subvolumes. Mounted at /mnt/disk3 (E:).
//!    For `cargo test` only: the same tree with lzo and 4 KiB B-tree nodes
//!    (deeper trees), with zstd and 64 KiB nodes, a btrfs made by
//!    `btrfs-convert` from an ext2 image (the only way to get real holes
//!    and extents shared by several files without mounting anything), and
//!    one with sha256 checksums, which the driver must refuse.
//!    It also writes manifests (target/btrfs-*.manifest): every path with
//!    its size and CRC-32, which tests/btrfs.rs and scripts/btrfs-check.sh
//!    compare with what Rustbelt reads.
//!
//! Needs dosfstools (mkfs.vfat), mtools (mmd, mcopy), fdisk (sfdisk),
//! e2fsprogs (mke2fs), exfatprogs (mkfs.exfat) and btrfs-progs
//! (mkfs.btrfs, btrfs-convert):
//!     sudo apt install dosfstools mtools fdisk e2fsprogs exfatprogs btrfs-progs

use std::{env, fs, io::Write, path::{Path, PathBuf}, process::{Command, Stdio}};

#[path = "build/exfat_populate.rs"]
mod exfat_populate;

/// Everything in /bin on the disk: the shell, its tools, and the test and
/// demo programs of the earlier stages.
const PROGRAMS: &[&str] = &[
    "sh", "ls", "cat", "wc", "grep", "mkdir", "rm", "touch", "cp", "sleep", // the shell + tools
    "hello", "evil", "spin", "demo", "child", // stage 5/6 demos and tests
    "sysinfo", "overflow", // stage 11: CPU load, and a stack overflow (guard pages)
    "ifconfig", "ping", "host", "fetch", "httpd", // stage 12: networking
    "random", "getty", "tile", // stage 13: virtual drivers
    "forktest", "cowtest", "mmaptest", "sigtest", // stage 14: processes
    "threads", "echoserver", "ptytest", "nbtest", // stage 15: libc plumbing
    "fputest", "pathtest", // stage 15.1: musl prerequisites
    "libctest", // stage 16: libc batch 1
    "coretest", // stage 17: coreutils batch 2
    "unixtest", // stage 18: Unix sockets, /proc/self
];

/// C programs in /bin, built with the host's C compiler and no libc at all:
/// plain Linux binaries that check Rustbelt speaks the Linux ABI.
const C_PROGRAMS: &[&str] = &["rawabi"]; // stage 15.1

/// Stage 19: C programs built against a real C library, musl, with the
/// `musl-gcc` wrapper (Debian/Ubuntu: `sudo apt install musl-tools`).
#[derive(Clone, Copy)]
enum Musl {
    /// Stock `musl-gcc -static-pie`: a position-independent executable.
    StaticPie,
    /// A classic static ET_EXEC. It must live at Rustbelt's user base, so
    /// the plain `musl-gcc -static` recipe (linked at 0x400000) needs help:
    /// see `build_musl_program`.
    StaticExec,
    /// Plain dynamic linking (PT_INTERP): Rustbelt must refuse it.
    Dynamic,
}
const MUSL_PROGRAMS: &[(&str, Musl)] = &[
    ("vdsotest", Musl::StaticExec),
    ("piehello", Musl::StaticPie),
    ("piethreads", Musl::StaticPie),
    ("dynhello", Musl::Dynamic),
    ("remaptest", Musl::StaticPie),
];

const DISK_SECTORS: u64 = 64 * 1024 * 1024 / 512;
const PART_START: u64 = 2048;
/// Leave 1 MiB at the end too (the backup GPT lives in the last 33 sectors).
const PART_SECTORS: u64 = DISK_SECTORS - 2 * PART_START;

fn main() {
    let manifest = PathBuf::from(env::var("CARGO_MANIFEST_DIR").unwrap());
    let out_dir = PathBuf::from(env::var("OUT_DIR").unwrap());
    let user_dir = manifest.join("user");
    println!("cargo:rerun-if-changed=user");
    println!("cargo:rerun-if-changed=disk");
    println!("cargo:rerun-if-changed=disk2");
    println!("cargo:rerun-if-changed=disk3");
    println!("cargo:rerun-if-changed=disk4");
    println!("cargo:rerun-if-changed=build");
    println!("cargo:rerun-if-changed=build.rs");
    println!("cargo:rerun-if-changed=vdso");

    build_vdso(&manifest, &out_dir);
    for program in PROGRAMS {
        build_program(&user_dir, &out_dir, program);
    }
    for program in C_PROGRAMS {
        build_c_program(&user_dir, &out_dir, program);
    }
    for &(program, kind) in MUSL_PROGRAMS {
        build_musl_program(&user_dir, &out_dir, program, kind);
    }
    build_disk(&manifest, &out_dir);
    build_ext2_disks(&manifest, &out_dir);
    build_exfat_disks(&manifest, &out_dir);
    build_btrfs_disks(&manifest, &out_dir);
}

fn build_program(user_dir: &Path, out_dir: &Path, program: &str) {
    let rustc = env::var("RUSTC").unwrap_or_else(|_| "rustc".into());
    let status = Command::new(&rustc)
        .args(["--edition", "2024", "--target", "x86_64-unknown-none"])
        .args(["-C", "panic=abort", "-C", "opt-level=2", "-C", "debuginfo=0", "-C", "strip=debuginfo"])
        .args(["-C", "relocation-model=static", "-C", "code-model=large"])
        .arg("-C")
        .arg(format!("link-arg=-T{}", user_dir.join("link.ld").display()))
        .arg("-o")
        .arg(out_dir.join(program))
        .arg(user_dir.join(format!("{program}.rs")))
        .status()
        .expect("failed to run rustc for a user program");
    assert!(status.success(), "building user program {program} failed");
}

/// A freestanding C program: no libc, no startup files, just raw syscalls.
/// -fpie makes the code RIP-relative so it can live at Rustbelt's user base
/// (0x80_0000_0000, above 4 GiB); -no-pie still makes an ordinary static
/// ET_EXEC file, which also runs as-is on a real x86_64 Linux machine.
fn build_c_program(user_dir: &Path, out_dir: &Path, program: &str) {
    let cc = env::var("CC").unwrap_or_else(|_| "cc".into());
    let status = Command::new(&cc)
        .args(["-O2", "-static", "-nostdlib", "-ffreestanding", "-fno-stack-protector"])
        .args(["-fpie", "-no-pie", "-Wall", "-Wextra"])
        .args(["-Wl,-Ttext-segment=0x8000400000", "-Wl,--build-id=none", "-z", "noexecstack"])
        .arg("-o")
        .arg(out_dir.join(program))
        .arg(user_dir.join(format!("{program}.c")))
        .status()
        .expect("failed to run the C compiler (install gcc)");
    assert!(status.success(), "building C program {program} failed");
}

/// The vDSO (stage 19, see vdso/vdso.c): a tiny shared library the kernel
/// maps into every process; src/vdso.rs embeds the result with
/// `include_bytes!`. -fPIC and no libc: it has to work at any address and
/// without anything else loaded. The linker script vdso/vdso.lds lays it
/// out as one page (ELF header first) and names the version LINUX_2.6;
/// --hash-style=both writes the old SysV hash table too, which musl needs.
fn build_vdso(manifest: &Path, out_dir: &Path) {
    let cc = env::var("CC").unwrap_or_else(|_| "cc".into());
    let dir = manifest.join("vdso");
    let status = Command::new(&cc)
        .args(["-O2", "-fPIC", "-shared", "-nostdlib", "-ffreestanding", "-fno-stack-protector"])
        .args(["-fno-builtin", "-fno-asynchronous-unwind-tables", "-Wall", "-Wextra", "-s"])
        .arg(format!("-Wl,-T,{}", dir.join("vdso.lds").display()))
        .args(["-Wl,--hash-style=both", "-Wl,-soname=linux-vdso.so.1", "-Wl,--no-undefined"])
        .args(["-Wl,-z,max-page-size=4096", "-Wl,--build-id=none", "-Wl,-z,noexecstack"])
        .arg("-o")
        .arg(out_dir.join("vdso.so"))
        .arg(dir.join("vdso.c"))
        .status()
        .expect("failed to run the C compiler (install gcc)");
    assert!(status.success(), "building the vDSO failed");
}

/// A C program linked with musl (stage 19).
///
/// StaticExec: the ELF type the stock recipe makes (ET_EXEC), but moved to
/// Rustbelt's user base (0x80_0000_0000; the kernel owns the low addresses)
/// with `-Ttext-segment`. Debian's musl start files are compiled as
/// position-independent code, which then needs three more tricks: musl's
/// own crt1.o instead of gcc's crtbegin (which can't reach a far-away
/// `__cxa_finalize`), `--no-relax`, and a dummy `_DYNAMIC` (crt1's `_start`
/// takes its address, which is 0 -- too far away -- in a static program).
/// Static PIEs need none of this, which is why stage 19 added them.
fn build_musl_program(user_dir: &Path, out_dir: &Path, program: &str, kind: Musl) {
    let musl = Path::new("/usr/lib/x86_64-linux-musl");
    let mut cmd = Command::new("musl-gcc");
    cmd.args(["-O2", "-Wall", "-Wextra", "-pthread", "-Wl,--build-id=none"]);
    let source = user_dir.join(format!("{program}.c"));
    match kind {
        Musl::StaticPie => {
            cmd.arg("-static-pie").arg(&source);
        }
        Musl::Dynamic => {
            cmd.args(["-fPIE", "-pie"]).arg(&source);
        }
        Musl::StaticExec => {
            cmd.args(["-static", "-no-pie", "-nostartfiles"])
                .args(["-Wl,-Ttext-segment=0x8000400000", "-Wl,--defsym=_DYNAMIC=0x8000400000", "-Wl,--no-relax"])
                .arg(musl.join("crt1.o"))
                .arg(musl.join("crti.o"))
                .arg(&source)
                .arg(musl.join("crtn.o"));
        }
    }
    let status = cmd
        .arg("-o")
        .arg(out_dir.join(program))
        .status()
        .expect("failed to run musl-gcc (install it: `sudo apt install musl-tools`)");
    assert!(status.success(), "building musl program {program} failed");
}

/// Find a tool in PATH or the sbin directories (often not in a user's PATH).
fn tool(name: &str) -> PathBuf {
    let path = env::var("PATH").unwrap_or_default();
    for dir in path.split(':').chain(["/usr/sbin", "/sbin", "/usr/bin"]) {
        let candidate = Path::new(dir).join(name);
        if candidate.is_file() {
            return candidate;
        }
    }
    panic!("`{name}` not found: install it with `sudo apt install dosfstools mtools fdisk e2fsprogs exfatprogs`");
}

fn run(cmd: &mut Command, stdin: Option<&str>) {
    cmd.stdin(if stdin.is_some() { Stdio::piped() } else { Stdio::null() });
    let mut child = cmd.spawn().unwrap_or_else(|e| panic!("can't run {cmd:?}: {e}"));
    if let Some(input) = stdin {
        child.stdin.take().unwrap().write_all(input.as_bytes()).unwrap();
    }
    let status = child.wait().unwrap();
    assert!(status.success(), "{cmd:?} failed");
}

fn build_disk(manifest: &Path, out_dir: &Path) {
    let target_dir = env::var("CARGO_TARGET_DIR").map(PathBuf::from).unwrap_or_else(|_| manifest.join("target"));
    fs::create_dir_all(&target_dir).unwrap();
    let disk = target_dir.join("disk.img");
    let part = out_dir.join("part.img");

    // 1. The FAT32 file system, as its own image first. -s 1: one sector per
    //    cluster (FAT32 needs >= 65525 clusters, so small disks need small
    //    clusters). -n: volume label.
    let _ = fs::remove_file(&part);
    run(
        Command::new(tool("mkfs.vfat"))
            .args(["-F", "32", "-s", "1", "-n", "TYLERDISK", "-C"])
            .arg(&part)
            .arg((PART_SECTORS / 2).to_string()), // size in KiB
        None,
    );
    let mtools = |name: &str, args: &[&str]| {
        let mut cmd = Command::new(tool(name));
        cmd.env("MTOOLS_SKIP_CHECK", "1").arg("-i").arg(&part).args(args);
        run(&mut cmd, None);
    };
    // Copy disk/ (text files, subdirectories) to the root of the volume...
    for entry in fs::read_dir(manifest.join("disk")).unwrap() {
        let path = entry.unwrap().path();
        mtools("mcopy", &["-s", path.to_str().unwrap(), "::/"]);
    }
    // ...and the user programs to /bin.
    mtools("mmd", &["::/bin"]);
    let musl = MUSL_PROGRAMS.iter().map(|(name, _)| name);
    for program in PROGRAMS.iter().chain(C_PROGRAMS).chain(musl) {
        mtools("mcopy", &[out_dir.join(program).to_str().unwrap(), &format!("::/bin/{program}")]);
    }

    // 2. The whole disk: zeros + GPT partition table (sfdisk works on image
    //    files too), then the FAT32 image copied into the partition.
    let _ = fs::remove_file(&disk);
    fs::File::create(&disk).unwrap().set_len(DISK_SECTORS * 512).unwrap();
    let layout = format!(
        "label: gpt\nstart={PART_START}, size={PART_SECTORS}, type=EBD0A0A2-B9E5-4433-87C0-68B6B72699C7, name=\"fat32\"\n"
    );
    run(Command::new(tool("sfdisk")).arg("--quiet").arg(&disk), Some(&layout));
    let fat = fs::read(&part).unwrap();
    assert_eq!(fat.len() as u64, PART_SECTORS * 512);
    let mut file = fs::OpenOptions::new().write(true).open(&disk).unwrap();
    use std::io::{Seek, SeekFrom};
    file.seek(SeekFrom::Start(PART_START * 512)).unwrap();
    file.write_all(&fat).unwrap();
}

/// The lines of big.txt: line i is `big.txt line {i:05}` (19 bytes with the
/// newline), so tests can check any offset. 16000 lines = 304000 bytes:
/// with 1 KiB blocks that's past the 12 direct + 256 single-indirect blocks.
pub const BIG_LINES: usize = 16000;

/// sparse.bin: 66 MiB, all holes except these 1 KiB chunks of text. With
/// 1 KiB blocks, 40 MiB is in the double-indirect range and 65 MiB in the
/// triple-indirect range (which starts at 12 + 256 + 256*256 KiB ~ 64.3 MiB).
pub const SPARSE_SIZE: u64 = 66 * 1024 * 1024;
pub const SPARSE_MARKS: &[u64] = &[0, 40 * 1024 * 1024, 65 * 1024 * 1024];

/// Copy a directory tree (files and directories only).
fn copy_tree(from: &Path, to: &Path) {
    fs::create_dir_all(to).unwrap();
    for entry in fs::read_dir(from).unwrap() {
        let path = entry.unwrap().path();
        let dest = to.join(path.file_name().unwrap());
        if path.is_dir() {
            copy_tree(&path, &dest);
        } else {
            fs::copy(&path, &dest).unwrap();
        }
    }
}

fn build_ext2_disks(manifest: &Path, out_dir: &Path) {
    use std::os::unix::fs::symlink;
    let target_dir = env::var("CARGO_TARGET_DIR").map(PathBuf::from).unwrap_or_else(|_| manifest.join("target"));

    // The tree to copy in: disk2/ + generated files.
    let tree = out_dir.join("ext2-tree");
    let _ = fs::remove_dir_all(&tree);
    copy_tree(&manifest.join("disk2"), &tree);
    let big: String = (0..BIG_LINES).map(|i| format!("big.txt line {i:05}\n")).collect();
    fs::write(tree.join("big.txt"), &big).unwrap();
    {
        use std::io::{Seek, SeekFrom};
        let mut f = fs::File::create(tree.join("sparse.bin")).unwrap();
        f.set_len(SPARSE_SIZE).unwrap(); // a file of holes...
        for &at in SPARSE_MARKS {
            // ...with a few 1 KiB blocks of text (mke2fs -d keeps all-zero
            // blocks as holes, so the image stays small).
            let text = format!("sparse.bin data at offset {at}\n");
            let mut block = text.repeat(1024 / text.len()).into_bytes();
            block.resize(1024, b'.');
            f.seek(SeekFrom::Start(at)).unwrap();
            f.write_all(&block).unwrap();
        }
    }
    // A "fast" symlink: the target (< 60 bytes) fits inside the inode.
    symlink("hello.txt", tree.join("hello-link")).unwrap();
    // A "slow" symlink: the target is too long, so it gets a data block.
    symlink("./deep/../deep/er/../er/./../../../docs/./deep/er/../../deep/er/nested.txt", tree.join("docs/long-link")).unwrap();

    // -t ext2: no journal, no extents. -b 1024: 1 KiB blocks. -m 0: no
    // blocks reserved for root. -E root_owner: the root directory belongs to
    // root (the other files keep their owner from the build machine).
    // -F: it's a file, not a block device; just do it.
    let mke2fs = |img: &Path, size: &str, extra: &[&str], src: &Path| {
        let _ = fs::remove_file(img);
        run(
            Command::new(tool("mke2fs"))
                .args(["-q", "-F", "-t", "ext2", "-m", "0"])
                .args(extra)
                .arg("-d")
                .arg(src)
                .arg(img)
                .arg(size),
            None,
        );
    };
    mke2fs(&target_dir.join("ext2.img"), "32M", &["-b", "1024", "-L", "RUSTBELT", "-E", "root_owner=0:0"], &tree);

    // Smaller tree for the test-only images.
    let small = out_dir.join("ext2-small");
    let _ = fs::remove_dir_all(&small);
    copy_tree(&manifest.join("disk2/docs"), &small.join("docs"));
    fs::copy(manifest.join("disk2/hello.txt"), small.join("hello.txt")).unwrap();
    fs::write(small.join("big.txt"), &big).unwrap();
    symlink("hello.txt", small.join("hello-link")).unwrap();
    mke2fs(&target_dir.join("ext2-4k.img"), "8M", &["-b", "4096", "-L", "FOURK", "-E", "root_owner=0:0"], &small);
    mke2fs(&target_dir.join("ext2-rev0.img"), "4M", &["-b", "1024", "-E", "root_owner=0:0,revision=0"], &small);
}

/// numbers.txt on the exFAT disk: 20 000 lines of 17 bytes = 340 000 bytes.
pub const NUMBER_LINES: usize = 20_000;
/// frag-chain.txt: 2 000 lines of 19 bytes = 38 000 bytes.
pub const FRAG_LINES: usize = 2_000;

fn build_exfat_disks(manifest: &Path, out_dir: &Path) {
    let target_dir = env::var("CARGO_TARGET_DIR").map(PathBuf::from).unwrap_or_else(|_| manifest.join("target"));
    let numbers: String = (0..NUMBER_LINES).map(|i| format!("exfat line {i:05}\n")).collect();
    let frag: String = (0..FRAG_LINES).map(|i| format!("fragment line {i:04}\n")).collect();

    let tree = out_dir.join("exfat-tree");
    let _ = fs::remove_dir_all(&tree);
    copy_tree(&manifest.join("disk3"), &tree);
    fs::write(tree.join("numbers.txt"), &numbers).unwrap();
    fs::write(tree.join("frag-chain.txt"), &frag).unwrap();

    // A small tree for the test image with 512-byte clusters (its root
    // directory is one 512-byte cluster: room for 16 entries).
    let small = out_dir.join("exfat-small");
    let _ = fs::remove_dir_all(&small);
    copy_tree(&manifest.join("disk3/Photos"), &small.join("Photos"));
    fs::copy(manifest.join("disk3/MixedCase.TXT"), small.join("MixedCase.TXT")).unwrap();
    fs::write(small.join("numbers.txt"), &numbers).unwrap();
    fs::write(small.join("frag-chain.txt"), &frag).unwrap();

    // mkfs.exfat wants an existing file of the right size.
    let mkfs = |img: &Path, size: u64, cluster: &str, label: &str, src: &Path| {
        let _ = fs::remove_file(img);
        fs::File::create(img).unwrap().set_len(size).unwrap();
        run(Command::new(tool("mkfs.exfat")).args(["-q", "-c", cluster, "-L", label]).arg(img), None);
        exfat_populate::populate(img, src);
    };
    mkfs(&target_dir.join("exfat.img"), 32 << 20, "4K", "TYLEREXFAT", &tree);
    mkfs(&target_dir.join("exfat-512.img"), 8 << 20, "512", "SMALLCLUST", &small);
}

// --- btrfs (stage 10) --------------------------------------------------------

/// CRC-32 (the zlib/PNG one), for the manifests. tests/btrfs.rs has its own
/// copy; scripts/btrfs-check.sh uses Python's zlib.crc32.
fn crc32(data: &[u8]) -> u32 {
    let mut crc = !0u32;
    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
}

/// One line per path under `dir`, sorted: `D\tpath`, `F\tpath\tsize\tcrc32`
/// or `L\tpath\ttarget`. Paths are relative, with `/` separators.
fn manifest_lines(dir: &Path, prefix: &str, out: &mut Vec<String>) {
    for entry in fs::read_dir(dir).unwrap() {
        let entry = entry.unwrap();
        let name = entry.file_name().into_string().unwrap();
        let rel = if prefix.is_empty() { name.clone() } else { format!("{prefix}/{name}") };
        let meta = fs::symlink_metadata(entry.path()).unwrap();
        if meta.file_type().is_symlink() {
            out.push(format!("L\t{rel}\t{}", fs::read_link(entry.path()).unwrap().display()));
        } else if meta.is_dir() {
            out.push(format!("D\t{rel}"));
            manifest_lines(&entry.path(), &rel, out);
        } else {
            let data = fs::read(entry.path()).unwrap();
            out.push(format!("F\t{rel}\t{}\t{:08x}", data.len(), crc32(&data)));
        }
    }
}

fn write_manifest(dir: &Path, extra: &[String], to: &Path) {
    let mut lines = Vec::new();
    manifest_lines(dir, "", &mut lines);
    lines.extend_from_slice(extra);
    lines.sort_by(|a, b| a.split('\t').nth(1).cmp(&b.split('\t').nth(1)));
    fs::write(to, lines.join("\n") + "\n").unwrap();
}

/// Pseudo-random bytes (a fixed LCG, so every build makes the same file).
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()
}

const BTRFS_LINES: usize = 120_000; // big.txt: 120 000 x 18 bytes = 2.16 MB

fn build_btrfs_disks(manifest: &Path, out_dir: &Path) {
    use std::io::{Seek, SeekFrom};
    use std::os::unix::fs::symlink;
    let target_dir = env::var("CARGO_TARGET_DIR").map(PathBuf::from).unwrap_or_else(|_| manifest.join("target"));

    // The main tree: disk4/ + generated files and symlinks.
    let tree = out_dir.join("btrfs-tree");
    let _ = fs::remove_dir_all(&tree);
    copy_tree(&manifest.join("disk4"), &tree);
    let big: String = (0..BTRFS_LINES).map(|i| format!("btrfs line {i:06}\n")).collect();
    fs::write(tree.join("big.txt"), big).unwrap();
    fs::write(tree.join("random.bin"), noise(1_500_000)).unwrap();
    fs::write(tree.join("zeros.bin"), vec![0u8; 1 << 20]).unwrap();
    fs::write(tree.join("empty.txt"), b"").unwrap();
    symlink("hello.txt", tree.join("hello-link")).unwrap();
    symlink("btrfs/cow.txt", tree.join("docs/cow-link")).unwrap();
    // From inside a subvolume back out to the volume root.
    symlink("../hello.txt", tree.join("projects/hello-link")).unwrap();
    write_manifest(&tree, &[], &target_dir.join("btrfs-tree.manifest"));

    // mkfs.btrfs wants an existing file (or -b SIZE); 128 MiB is roomy.
    let mkfs = |img: &Path, args: &[&str], src: &Path| {
        let _ = fs::remove_file(img);
        fs::File::create(img).unwrap().set_len(128 << 20).unwrap();
        run(Command::new(tool("mkfs.btrfs")).arg("-q").args(args).arg("--rootdir").arg(src).arg(img), None);
    };
    let subvols = ["-u", "projects", "-u", "ro:archive"];
    let with = |a: &[&'static str]| -> Vec<&'static str> { [a, &subvols[..]].concat() };
    mkfs(&target_dir.join("btrfs.img"), &with(&["-L", "TYLERBTRFS", "--compress", "zlib"]), &tree);
    mkfs(&target_dir.join("btrfs-lzo.img"), &with(&["-L", "LZO4K", "--compress", "lzo", "-n", "4096", "-m", "single"]), &tree);
    mkfs(&target_dir.join("btrfs-zstd.img"), &with(&["-L", "ZSTD64K", "--compress", "zstd", "-n", "65536"]), &tree);

    // A btrfs with a checksum type the driver doesn't do (it must say so).
    let tiny = out_dir.join("btrfs-tiny");
    let _ = fs::remove_dir_all(&tiny);
    fs::create_dir_all(&tiny).unwrap();
    fs::write(tiny.join("hello.txt"), b"sha256 checksums\n").unwrap();
    mkfs(&target_dir.join("btrfs-sha256.img"), &["-L", "SHA256", "--csum", "sha256"], &tiny);

    // btrfs-convert: an ext2 image (4 KiB blocks) turned into btrfs in place.
    // mkfs.btrfs writes zeros as real data, but here the ext2 holes become
    // btrfs holes, and the converter's extents are shared: each file points
    // into one big extent that also backs ext2_saved/image (the old ext2).
    let ctree = out_dir.join("btrfs-convert-tree");
    let _ = fs::remove_dir_all(&ctree);
    fs::create_dir_all(ctree.join("sub/dir")).unwrap();
    fs::write(ctree.join("small.txt"), b"converted from ext2\n").unwrap();
    fs::write(ctree.join("sub/dir/deep.txt"), b"a nested file in a converted file system\n").unwrap();
    fs::write(ctree.join("medium.bin"), noise(200_000)).unwrap();
    symlink("sub/dir/deep.txt", ctree.join("deep-link")).unwrap();
    {
        // sparse.bin: 5 MiB, data only at 0, 1 MiB and the very end.
        let mut f = fs::File::create(ctree.join("sparse.bin")).unwrap();
        f.set_len(5 << 20).unwrap();
        for (at, text) in [(0u64, &b"start of sparse.bin"[..]), (1 << 20, b"one MiB in"), ((5 << 20) - 7, b"the end")] {
            f.seek(SeekFrom::Start(at)).unwrap();
            f.write_all(text).unwrap();
        }
    }
    let conv = target_dir.join("btrfs-convert.img");
    let conv_size: u64 = 256 << 20; // btrfs-convert silently fails on 64 MiB
    let _ = fs::remove_file(&conv);
    run(
        Command::new(tool("mke2fs"))
            .args(["-q", "-F", "-t", "ext2", "-b", "4096", "-L", "CONVERTED", "-d"])
            .arg(&ctree)
            .arg(&conv)
            .arg(format!("{}M", conv_size >> 20)),
        None,
    );
    run(Command::new(tool("btrfs-convert")).arg(&conv), None);
    // lost+found came from mke2fs; ext2_saved/image is the old ext2 (only
    // its size is listed: reading 256 MiB in a test would take too long).
    let extra = [
        String::from("D\tlost+found"),
        String::from("D\text2_saved"),
        format!("S\text2_saved/image\t{conv_size}"),
    ];
    write_manifest(&ctree, &extra, &target_dir.join("btrfs-convert.manifest"));
}