//! btrfs, read-only, hand-written (no crate except the zlib and zstd
//! decompressors). btrfs ("B-tree file system", Chris Mason, 2007) is the
//! copy-on-write file system that Fedora, openSUSE and Synology use by
//! default. This driver reads it: enough to list, open and read every
//! file, follow symlinks and walk into subvolumes. Anything that would
//! change the disk fails with `EROFS`.
//!
//! # The big idea: everything is a B-tree, and nothing is overwritten
//!
//! ext2 has fixed places for things (inode tables, bitmaps). btrfs has
//! almost nothing at a fixed place: just the **superblock** at 64 KiB.
//! Everything else lives in **B-trees** made of fixed-size **nodes**
//! (16 KiB by default), and the trees point at each other.
//!
//! * A **leaf** (level 0) holds **items**, sorted by a 17-byte **key**
//!   `(objectid u64, type u8, offset u64)`. The item headers sit at the
//!   front of the leaf and the item data at the back:
//!
//!   ```text
//!   | header 101 B | item 0 | item 1 | ...  free space ...  | data 1 | data 0 |
//!                    key + offset + size (25 bytes each)  ^
//!   ```
//! * An **internal node** (level 1+) holds `(key, child pointer)` pairs.
//!   The child holds keys from its key up to the next pair's key.
//! * Every node starts with a header: a checksum of the rest of the node,
//!   the file system's UUID, the node's own address, and its level. So a
//!   misdirected or torn write is caught. We check all of that on every
//!   node we read.
//!
//! **Copy-on-write**: to change a leaf, btrfs writes a changed *copy*
//! somewhere free, then a copy of its parent pointing at the new leaf, and
//! so on up to the root, then finally the superblock. Until that last
//! write, the old tree is untouched. A crash can't leave it half-updated,
//! and a **snapshot** is just a second pointer to an old root.
//!
//! # Logical addresses and chunks
//!
//! Tree pointers are **logical** addresses, not disk offsets. The **chunk
//! tree** maps logical ranges (chunks, 8 MiB to 1 GiB) to places on the
//! device(s), which is how btrfs does RAID and DUP:
//!
//! ```text
//! logical 30408704 +32 MiB  METADATA|DUP  -> device 1 @ 38797312  and  @ 72351744
//! logical 13631488 +8 MiB   DATA (single) -> device 1 @ 13631488
//! ```
//!
//! **DUP** keeps two copies on the same disk (the default for metadata on
//! one disk); if one copy's checksum is bad we read the other. The chunk
//! tree is itself a B-tree at a logical address. To read it you'd need the
//! chunk tree, so the superblock carries a few chunk items of its own (the
//! `sys_chunk_array`) for the SYSTEM chunks that hold the chunk tree.
//!
//! # The trees we read
//!
//! ```text
//! superblock -> root tree      ROOT_ITEMs: where every other tree's root is
//!            -> chunk tree     CHUNK_ITEMs: logical -> physical
//! root tree  -> FS tree (5)    the files of the top-level subvolume
//!            -> subvolume 256, 257...  one FS tree each
//!            -> csum tree (7)  a crc32c for every 4 KiB of file data
//! ```
//!
//! In an FS tree, a file or directory is an **inode number** (objectid) and
//! its items, in key order:
//!
//! ```text
//! (257 INODE_ITEM 0)         size, mode, link count, times, flags
//! (257 INODE_REF 256)        "my name in directory 256 is docs"
//! (257 DIR_ITEM <hash>)      directory entry, found by a crc32c hash of the name
//! (257 DIR_INDEX <n>)        the same entry again, keyed by creation order
//! (258 EXTENT_DATA <offset>) "file bytes from <offset> are in this extent"
//! ```
//!
//! A directory's entries are stored twice. DIR_ITEMs, keyed by name hash,
//! make a lookup one tree search. DIR_INDEXes, keyed by a counter, make a
//! listing come out in creation order.
//!
//! **File data** is a list of EXTENT_DATA items:
//! * **inline**: the bytes are right in the leaf (small files and symlinks);
//! * **regular**: `disk_bytenr` + `disk_num_bytes` say where the extent is.
//!   The file uses `num_bytes` of it starting `offset` bytes in, so several
//!   files (or snapshots) can share pieces of one extent. `disk_bytenr` 0 is
//!   a hole;
//! * **prealloc**: reserved by `fallocate`, never written: reads as zeros.
//!
//! Any of them can be **compressed** (zlib, lzo or zstd): then the extent is
//! decompressed whole (up to 128 KiB) and `offset`/`num_bytes` index the
//! *decompressed* bytes. With the NO_HOLES feature (the default), holes have
//! no item at all: a gap between extents reads as zeros.
//!
//! A **subvolume** is a separate FS tree. Its parent directory has an entry
//! whose "location" is a ROOT_ITEM key instead of an inode, so a lookup
//! steps from one tree into another. ROOT_REF items in the root tree list
//! which subvolume sits in which directory.
//!
//! # Checksums
//!
//! crc32c everywhere: the superblock and every node (over everything after
//! the 32-byte checksum field), and every 4 KiB of file data (stored in
//! the csum tree, checked here on every read). A name hash is crc32c too,
//! with seed `!1` and no final inversion. Other checksum types (xxhash64,
//! sha256, blake2b) are refused at mount with a clear message.
//!
//! # Why read-only
//!
//! Reading needs: superblock, chunks, B-tree search, a handful of item
//! types, decompression. Writing needs everything *else*. You'd COW every
//! node from leaf to root on each change, rebalance (split and merge
//! nodes), and allocate space from block groups via the extent tree,
//! keeping its back-references and reference counts right. You'd also have
//! to update the csum tree and the free-space tree, and commit transactions
//! in the right order with the superblock last. That's a much bigger
//! project than this whole driver; see the README.

use super::{DirEntry, FileSystem, Inode, InodeKind};
use crate::block::{BlockDevice, SECTOR_SIZE};
use crate::errno::Errno;
use alloc::{collections::BTreeMap, format, string::String, sync::Arc, vec, vec::Vec};
use spin::Mutex;

// ---------------------------------------------------------------------------
// On-disk constants
// ---------------------------------------------------------------------------

const SUPER_OFFSET: u64 = 0x10000; // the primary superblock: 64 KiB in
const SUPER_SIZE: usize = 4096;
const MAGIC: &[u8; 8] = b"_BHRfS_M";

// Superblock fields (byte offsets).
const SB_FSID: usize = 0x20;
const SB_MAGIC: usize = 0x40;
const SB_GENERATION: usize = 0x48;
const SB_ROOT: usize = 0x50; // logical address of the root tree
const SB_CHUNK_ROOT: usize = 0x58;
const SB_TOTAL_BYTES: usize = 0x70;
const SB_BYTES_USED: usize = 0x78;
const SB_NUM_DEVICES: usize = 0x88;
const SB_SECTORSIZE: usize = 0x90;
const SB_NODESIZE: usize = 0x94;
const SB_SYS_CHUNK_ARRAY_SIZE: usize = 0xa0;
const SB_INCOMPAT: usize = 0xbc;
const SB_CSUM_TYPE: usize = 0xc4;
const SB_ROOT_LEVEL: usize = 0xc6;
const SB_CHUNK_ROOT_LEVEL: usize = 0xc7;
const SB_DEV_ITEM: usize = 0xc9; // our device; its id (u64) comes first
const SB_LABEL: usize = 0x12b; // 256 bytes, NUL-padded
const SB_METADATA_UUID: usize = 0x23b;
const SB_SYS_CHUNK_ARRAY: usize = 0x32b;

// Incompat feature bits we can read. Anything else: refuse to mount.
const INCOMPAT_METADATA_UUID: u64 = 0x400;
const INCOMPAT_OK: u64 = 0x1 // mixed back-references
    | 0x2      // a default subvolume other than 5
    | 0x4      // data and metadata in the same block groups
    | 0x8 | 0x10 // lzo, zstd were used
    | 0x20     // nodes bigger than 4 KiB
    | 0x40     // extended inode refs (lots of hard links)
    | 0x100    // skinny extent-tree metadata items
    | 0x200    // NO_HOLES: holes have no items
    | INCOMPAT_METADATA_UUID
    | 0x800    // raid1c3/raid1c4 exist (irrelevant on one device)
    | 0x10000; // simple quotas

// Node header (101 bytes), then items (leaf) or key pointers (internal).
const HDR_FSID: usize = 0x20;
const HDR_BYTENR: usize = 0x30;
const HDR_NRITEMS: usize = 0x60;
const HDR_LEVEL: usize = 0x64;
const HEADER_SIZE: usize = 0x65;
const ITEM_SIZE: usize = 25; // key (17) + data offset u32 + data size u32
const KEY_PTR_SIZE: usize = 33; // key (17) + child address u64 + generation u64

// Item types (the middle field of a key).
const INODE_ITEM: u8 = 1;
const INODE_REF: u8 = 12;
const DIR_ITEM: u8 = 84;
const DIR_INDEX: u8 = 96;
const EXTENT_DATA: u8 = 108;
const EXTENT_CSUM: u8 = 128;
const ROOT_ITEM: u8 = 132;
const ROOT_REF: u8 = 156;
const CHUNK_ITEM: u8 = 228;

// Well-known objectids.
const FS_TREE: u64 = 5; // the top-level subvolume
const ROOT_TREE_DIR: u64 = 6; // holds the "default" subvolume entry
const CSUM_TREE: u64 = 7;
const FIRST_CHUNK_TREE: u64 = 256;
const CSUM_OBJECTID: u64 = -10i64 as u64; // EXTENT_CSUM items' objectid

// Chunk type bits: what it holds, and how it's laid out.
const BG_DATA: u64 = 1;
const BG_SYSTEM: u64 = 2;
const BG_METADATA: u64 = 4;
const BG_DUP: u64 = 0x20;
const BG_PROFILES: u64 = 0x8 | 0x10 | 0x20 | 0x40 | 0x80 | 0x100 | 0x200 | 0x400;

// Inode item fields (160 bytes, also the first part of a ROOT_ITEM).
const INODE_SIZE: usize = 16;
const INODE_MODE: usize = 52;
const INODE_FLAGS: usize = 64;
const INODE_NODATASUM: u64 = 1;
const S_IFMT: u32 = 0o170000;
const S_IFDIR: u32 = 0o040000;
const S_IFLNK: u32 = 0o120000;
// ROOT_ITEM fields after its inode item.
const ROOT_DIRID: usize = 168; // inode number of the subvolume's top directory
const ROOT_BYTENR: usize = 176;
const ROOT_FLAGS: usize = 208;
const ROOT_LEVEL: usize = 238;
const ROOT_RDONLY: u64 = 1;

// EXTENT_DATA fields.
const EXT_RAM_BYTES: usize = 8; // size once decompressed
const EXT_COMPRESSION: usize = 16;
const EXT_ENCRYPTION: usize = 17;
const EXT_OTHER_ENCODING: usize = 18;
const EXT_TYPE: usize = 20; // 0 inline, 1 regular, 2 prealloc
const EXT_INLINE_DATA: usize = 21;
const EXT_DISK_BYTENR: usize = 21;
const EXT_DISK_NUM_BYTES: usize = 29;
const EXT_OFFSET: usize = 37;
const EXT_NUM_BYTES: usize = 45;
const EXT_REGULAR_SIZE: usize = 53;

/// How much node data each volume keeps cached, in bytes.
const NODE_CACHE_BYTES: usize = 256 * 1024;

fn get16(b: &[u8], at: usize) -> u16 {
    u16::from_le_bytes([b[at], b[at + 1]])
}
fn get32(b: &[u8], at: usize) -> u32 {
    u32::from_le_bytes(b[at..at + 4].try_into().unwrap())
}
fn get64(b: &[u8], at: usize) -> u64 {
    u64::from_le_bytes(b[at..at + 8].try_into().unwrap())
}

// ---------------------------------------------------------------------------
// crc32c (Castagnoli), table-driven; the table is built at compile time
// ---------------------------------------------------------------------------

const CRC32C_TABLE: [u32; 256] = {
    let mut table = [0u32; 256];
    let mut i = 0;
    while i < 256 {
        let mut c = i as u32;
        let mut bit = 0;
        while bit < 8 {
            c = if c & 1 != 0 { (c >> 1) ^ 0x82F6_3B78 } else { c >> 1 };
            bit += 1;
        }
        table[i] = c;
        i += 1;
    }
    table
};

/// The raw crc32c update: no inversion at the start or end.
fn crc32c_update(mut crc: u32, data: &[u8]) -> u32 {
    for &b in data {
        crc = CRC32C_TABLE[((crc ^ b as u32) & 0xff) as usize] ^ (crc >> 8);
    }
    crc
}

/// The standard crc32c, as stored for the superblock, nodes and data.
pub fn crc32c(data: &[u8]) -> u32 {
    !crc32c_update(!0, data)
}

/// The DIR_ITEM key offset for a name: crc32c with seed `!1`, not inverted.
pub fn name_hash(name: &[u8]) -> u64 {
    crc32c_update(!1, name) as u64
}

/// Is there a btrfs superblock on this device?
pub fn probe(dev: &dyn BlockDevice) -> bool {
    let mut sector = [0u8; SECTOR_SIZE];
    if dev.sector_count() < (SUPER_OFFSET + SUPER_SIZE as u64) / SECTOR_SIZE as u64 {
        return false;
    }
    dev.read_sectors(SUPER_OFFSET / SECTOR_SIZE as u64, &mut sector).is_ok() && &sector[SB_MAGIC..SB_MAGIC + 8] == MAGIC
}

// ---------------------------------------------------------------------------
// Keys and trees
// ---------------------------------------------------------------------------

/// A B-tree key. The derived ordering (objectid, then type, then offset) is
/// exactly btrfs's.
#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord)]
pub struct Key {
    pub objectid: u64,
    pub kind: u8,
    pub offset: u64,
}

impl Key {
    const fn new(objectid: u64, kind: u8, offset: u64) -> Key {
        Key { objectid, kind, offset }
    }
    fn parse(b: &[u8], at: usize) -> Key {
        Key { objectid: get64(b, at), kind: b[at + 8], offset: get64(b, at + 9) }
    }
}

/// Where a tree's root node is, and its level (0 = the root is a leaf).
#[derive(Debug, Clone, Copy)]
struct Tree {
    bytenr: u64,
    level: u8,
}

/// One chunk: `length` bytes from `logical` are stored at each physical
/// offset in `copies` (one for single, two for DUP).
struct Chunk {
    logical: u64,
    length: u64,
    kind: u64,
    copies: Vec<u64>,
}

/// A file or directory: which FS tree (subvolume) and which inode in it.
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
struct Loc {
    root: u64,
    ino: u64,
}

/// The parts of an INODE_ITEM we use.
struct InodeItem {
    size: u64,
    mode: u32,
    /// Hard links, owner and group (stage 17: stat shows them).
    nlink: u32,
    uid: u32,
    gid: u32,
    flags: u64,
    /// atime, mtime, ctime as [seconds, nanoseconds] (stage 16: for stat).
    times: [[i64; 2]; 3],
}

/// One entry of a DIR_ITEM or DIR_INDEX item.
struct DirItem {
    location: Key, // (inode, INODE_ITEM, 0) or (subvolume id, ROOT_ITEM, ...)
    name: Vec<u8>,
    file_type: u8, // 1 file, 2 directory, 7 symlink
}

/// A subvolume, for the boot log and tests.
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct Subvolume {
    pub id: u64,
    pub path: String, // from the top-level subvolume, e.g. "projects"
    pub read_only: bool,
}

/// One EXTENT_DATA item.
enum Extent<'a> {
    Inline { compression: u8, data: &'a [u8], ram_bytes: u64 },
    Regular { compression: u8, disk_bytenr: u64, disk_num_bytes: u64, offset: u64, num_bytes: u64, ram_bytes: u64 },
    Prealloc { num_bytes: u64 },
}

impl<'a> Extent<'a> {
    fn parse(d: &'a [u8]) -> Result<Extent<'a>, Errno> {
        if d.len() < EXT_INLINE_DATA {
            return Err(Errno::EIO);
        }
        if d[EXT_ENCRYPTION] != 0 || get16(d, EXT_OTHER_ENCODING) != 0 {
            crate::kprintln!("[btrfs] encrypted extents are not supported");
            return Err(Errno::EIO);
        }
        let compression = d[EXT_COMPRESSION];
        let ram_bytes = get64(d, EXT_RAM_BYTES);
        match d[EXT_TYPE] {
            0 => Ok(Extent::Inline { compression, data: &d[EXT_INLINE_DATA..], ram_bytes }),
            t @ (1 | 2) if d.len() >= EXT_REGULAR_SIZE => {
                let num_bytes = get64(d, EXT_NUM_BYTES);
                if t == 2 {
                    return Ok(Extent::Prealloc { num_bytes });
                }
                Ok(Extent::Regular {
                    compression,
                    disk_bytenr: get64(d, EXT_DISK_BYTENR),
                    disk_num_bytes: get64(d, EXT_DISK_NUM_BYTES),
                    offset: get64(d, EXT_OFFSET),
                    num_bytes,
                    ram_bytes,
                })
            }
            _ => Err(Errno::EIO),
        }
    }

    /// How many bytes of the file this extent covers.
    fn len(&self) -> u64 {
        match self {
            Extent::Inline { ram_bytes, .. } => *ram_bytes,
            Extent::Regular { num_bytes, .. } | Extent::Prealloc { num_bytes } => *num_bytes,
        }
    }
}

/// Decompress a whole extent (`compression`: 1 zlib, 2 lzo, 3 zstd) to
/// `ram_bytes`, padding with zeros if the stream is shorter.
fn decompress(compression: u8, src: &[u8], ram_bytes: usize, sectorsize: usize) -> Result<Vec<u8>, Errno> {
    let fail = |what: &str| {
        crate::kprintln!("[btrfs] {}", what);
        Errno::EIO
    };
    let mut out = match compression {
        1 => miniz_oxide::inflate::decompress_to_vec_zlib_with_limit(src, ram_bytes).map_err(|_| fail("bad zlib data"))?,
        2 => {
            // btrfs's lzo framing: a u32 total length, then segments of
            // (u32 length, LZO1X stream) that each decompress to at most one
            // sector. A segment header never straddles a sector boundary:
            // if fewer than 4 bytes are left in the sector, skip to the next.
            if src.len() < 4 {
                return Err(fail("bad lzo data"));
            }
            let total = (get32(src, 0) as usize).min(src.len());
            let (mut pos, mut out) = (4, Vec::with_capacity(ram_bytes));
            while pos < total && out.len() < ram_bytes {
                if sectorsize - pos % sectorsize < 4 {
                    pos = pos.next_multiple_of(sectorsize);
                }
                if pos + 4 > total {
                    break;
                }
                let len = get32(src, pos) as usize;
                let seg = src.get(pos + 4..pos + 4 + len).ok_or_else(|| fail("bad lzo segment"))?;
                super::lzo::decompress(seg, &mut out, sectorsize).map_err(|e| fail(e))?;
                pos += 4 + len;
            }
            out
        }
        3 => {
            // One zstd frame, followed by zero padding up to the sector.
            let mut decoder = ruzstd::decoding::FrameDecoder::new();
            let mut input = src;
            decoder.init(&mut input).map_err(|_| fail("bad zstd frame header"))?;
            decoder
                .decode_blocks(&mut input, ruzstd::decoding::BlockDecodingStrategy::All)
                .map_err(|_| fail("bad zstd data"))?;
            decoder.collect().unwrap_or_default()
        }
        n => return Err(fail(&format!("unknown compression type {}", n))),
    };
    out.resize(ram_bytes, 0);
    Ok(out)
}

// ---------------------------------------------------------------------------
// The volume: superblock, chunks, and B-tree search
// ---------------------------------------------------------------------------

struct Volume {
    dev: Arc<dyn BlockDevice>,
    sectorsize: usize,
    nodesize: usize,
    metadata_fsid: [u8; 16], // what every node header must carry
    label: String,
    generation: u64,
    total_bytes: u64,
    bytes_used: u64,
    chunks: Vec<Chunk>,
    root_tree: Tree,
    csum_tree: Option<Tree>,
    default_subvol: u64,
    fs_trees: BTreeMap<u64, (Tree, u64)>, // subvolume id -> (tree, top dir inode)
    node_cache: Vec<(u64, Arc<Vec<u8>>)>, // most recently used last
    extent_cache: Option<(u64, Arc<Vec<u8>>)>, // last decompressed extent
}

impl Volume {
    fn open(dev: Arc<dyn BlockDevice>) -> Result<Volume, String> {
        let mut sb = vec![0u8; SUPER_SIZE];
        dev.read_sectors(SUPER_OFFSET / SECTOR_SIZE as u64, &mut sb).map_err(|e| format!("can't read the superblock: {:?}", e))?;
        if &sb[SB_MAGIC..SB_MAGIC + 8] != MAGIC {
            return Err(String::from("no btrfs magic"));
        }
        let csum_type = get16(&sb, SB_CSUM_TYPE);
        if csum_type != 0 {
            let name = ["crc32c", "xxhash64", "sha256", "blake2b"].get(csum_type as usize).copied().unwrap_or("unknown");
            return Err(format!("checksum type {} ({}) is not supported, only crc32c", csum_type, name));
        }
        let (stored, computed) = (get32(&sb, 0), crc32c(&sb[0x20..]));
        if stored != computed {
            return Err(format!("bad superblock checksum ({:#010x}, should be {:#010x})", stored, computed));
        }
        let incompat = get64(&sb, SB_INCOMPAT);
        if incompat & !INCOMPAT_OK != 0 {
            return Err(format!("unsupported feature flags {:#x}", incompat & !INCOMPAT_OK));
        }
        if get64(&sb, SB_NUM_DEVICES) != 1 {
            return Err(String::from("multi-device file systems are not supported"));
        }
        let sectorsize = get32(&sb, SB_SECTORSIZE) as usize;
        let nodesize = get32(&sb, SB_NODESIZE) as usize;
        if !sectorsize.is_power_of_two() || sectorsize < SECTOR_SIZE || !nodesize.is_power_of_two() || nodesize < sectorsize {
            return Err(format!("odd sizes: sector {} node {}", sectorsize, nodesize));
        }
        let fsid_at = if incompat & INCOMPAT_METADATA_UUID != 0 { SB_METADATA_UUID } else { SB_FSID };
        let label_bytes = &sb[SB_LABEL..SB_LABEL + 256];
        let label_len = label_bytes.iter().position(|&b| b == 0).unwrap_or(256);
        let mut vol = Volume {
            dev,
            sectorsize,
            nodesize,
            metadata_fsid: sb[fsid_at..fsid_at + 16].try_into().unwrap(),
            label: String::from_utf8_lossy(&label_bytes[..label_len]).into_owned(),
            generation: get64(&sb, SB_GENERATION),
            total_bytes: get64(&sb, SB_TOTAL_BYTES),
            bytes_used: get64(&sb, SB_BYTES_USED),
            chunks: Vec::new(),
            root_tree: Tree { bytenr: get64(&sb, SB_ROOT), level: sb[SB_ROOT_LEVEL] },
            csum_tree: None,
            default_subvol: FS_TREE,
            fs_trees: BTreeMap::new(),
            node_cache: Vec::new(),
            extent_cache: None,
        };
        let devid = get64(&sb, SB_DEV_ITEM);

        // 1. Bootstrap: the SYSTEM chunks listed in the superblock itself
        //    (disk key + chunk item, repeated), enough to read the chunk tree.
        let array_len = (get32(&sb, SB_SYS_CHUNK_ARRAY_SIZE) as usize).min(2048);
        let array = &sb[SB_SYS_CHUNK_ARRAY..SB_SYS_CHUNK_ARRAY + array_len];
        let mut at = 0;
        while at + 17 + 48 <= array.len() {
            let key = Key::parse(array, at);
            let size = 48 + 32 * get16(array, at + 17 + 44) as usize;
            if key.kind != CHUNK_ITEM || at + 17 + size > array.len() {
                return Err(String::from("bad sys_chunk_array"));
            }
            vol.add_chunk(key.offset, &array[at + 17..at + 17 + size], devid)?;
            at += 17 + size;
        }

        // 2. The whole chunk tree: every chunk, DATA and METADATA too.
        let chunk_tree = Tree { bytenr: get64(&sb, SB_CHUNK_ROOT), level: sb[SB_CHUNK_ROOT_LEVEL] };
        let all = Key::new(FIRST_CHUNK_TREE, CHUNK_ITEM, 0)..=Key::new(FIRST_CHUNK_TREE, CHUNK_ITEM, u64::MAX);
        let items = vol.range(chunk_tree, *all.start(), *all.end()).map_err(|e| format!("can't read the chunk tree: {:?}", e))?;
        vol.chunks.clear();
        for (key, data) in items {
            vol.add_chunk(key.offset, &data, devid)?;
        }

        // 3. The root tree tells us where the csum tree is, and (through the
        //    "default" entry in directory 6) which subvolume to show.
        vol.csum_tree = vol.root_of(CSUM_TREE).ok().map(|(tree, _)| tree);
        let default = Key::new(ROOT_TREE_DIR, DIR_ITEM, name_hash(b"default"));
        if let Ok(Some(data)) = vol.get(vol.root_tree, default) {
            if let Some(entry) = parse_dir_items(&data).into_iter().find(|e| e.name == b"default") {
                vol.default_subvol = entry.location.objectid;
            }
        }
        vol.fs_tree(vol.default_subvol).map_err(|e| format!("can't find the default subvolume: {:?}", e))?;
        Ok(vol)
    }

    /// Remember one chunk item (`data`: the chunk item with its stripes).
    fn add_chunk(&mut self, logical: u64, data: &[u8], devid: u64) -> Result<(), String> {
        let kind = get64(data, 24);
        let profile = kind & BG_PROFILES;
        if profile != 0 && profile != BG_DUP {
            return Err(format!("chunk at {} uses a RAID profile ({:#x}); only single and DUP are supported", logical, profile));
        }
        let stripes = get16(data, 44) as usize;
        let mut copies = Vec::new();
        for s in 0..stripes {
            let at = 48 + 32 * s;
            if get64(data, at) != devid {
                return Err(format!("chunk at {} is on another device", logical));
            }
            copies.push(get64(data, at + 8));
        }
        self.chunks.push(Chunk { logical, length: get64(data, 0), kind, copies });
        Ok(())
    }

    /// The chunk holding `logical`, and how far into it that is.
    fn chunk(&self, logical: u64) -> Result<(&Chunk, u64), Errno> {
        self.chunks
            .iter()
            .find(|c| logical >= c.logical && logical - c.logical < c.length)
            .map(|c| (c, logical - c.logical))
            .ok_or(Errno::EIO)
    }

    /// Read `len` bytes at a logical address from copy number `copy`
    /// (0 for single; 0 or 1 for DUP). The range must not cross a chunk
    /// (nodes and extents never do).
    fn read_logical(&self, logical: u64, len: usize, copy: usize) -> Result<Vec<u8>, Errno> {
        let (chunk, into) = self.chunk(logical)?;
        if into + len as u64 > chunk.length {
            return Err(Errno::EIO);
        }
        let physical = chunk.copies.get(copy).ok_or(Errno::EIO)? + into;
        // Our reads are sector-aligned; round out just in case.
        let skip = (physical % SECTOR_SIZE as u64) as usize;
        let mut buf = vec![0u8; (skip + len).next_multiple_of(SECTOR_SIZE)];
        self.dev.read_sectors(physical / SECTOR_SIZE as u64, &mut buf)?;
        if skip != 0 || buf.len() != len {
            buf = buf[skip..skip + len].to_vec();
        }
        Ok(buf)
    }

    fn copies(&self, logical: u64) -> usize {
        self.chunk(logical).map(|(c, _)| c.copies.len()).unwrap_or(1)
    }

    /// Read and check one tree node. A copy with a bad checksum or a wrong
    /// header is skipped in favor of the next copy (DUP metadata).
    fn read_node(&mut self, bytenr: u64) -> Result<Arc<Vec<u8>>, Errno> {
        if let Some(i) = self.node_cache.iter().position(|(b, _)| *b == bytenr) {
            let entry = self.node_cache.remove(i);
            let node = entry.1.clone();
            self.node_cache.push(entry);
            return Ok(node);
        }
        for copy in 0..self.copies(bytenr) {
            let node = self.read_logical(bytenr, self.nodesize, copy)?;
            let (stored, computed) = (get32(&node, 0), crc32c(&node[0x20..]));
            let problem = if stored != computed {
                format!("bad checksum {:#010x}, should be {:#010x}", stored, computed)
            } else if get64(&node, HDR_BYTENR) != bytenr {
                format!("header says it's node {}", get64(&node, HDR_BYTENR))
            } else if node[HDR_FSID..HDR_FSID + 16] != self.metadata_fsid {
                String::from("it belongs to another file system")
            } else {
                if copy > 0 {
                    crate::kprintln!("[btrfs] node {}: copy 0 was bad, copy {} is good", bytenr, copy);
                }
                let node = Arc::new(node);
                if self.node_cache.len() >= (NODE_CACHE_BYTES / self.nodesize).max(2) {
                    self.node_cache.remove(0);
                }
                self.node_cache.push((bytenr, node.clone()));
                return Ok(node);
            };
            crate::kprintln!("[btrfs] node {} copy {}: {}", bytenr, copy, problem);
        }
        Err(Errno::EIO)
    }

    /// Every item with `min <= key <= max`, in key order, with a copy of
    /// its data.
    fn range(&mut self, tree: Tree, min: Key, max: Key) -> Result<Vec<(Key, Vec<u8>)>, Errno> {
        let mut out = Vec::new();
        self.walk(tree.bytenr, tree.level, min, max, &mut out)?;
        Ok(out)
    }

    fn walk(&mut self, bytenr: u64, level: u8, min: Key, max: Key, out: &mut Vec<(Key, Vec<u8>)>) -> Result<(), Errno> {
        let node = self.read_node(bytenr)?;
        if node[HDR_LEVEL] != level {
            crate::kprintln!("[btrfs] node {} has level {}, expected {}", bytenr, node[HDR_LEVEL], level);
            return Err(Errno::EIO);
        }
        let n = get32(&node, HDR_NRITEMS) as usize;
        if level == 0 {
            for i in 0..n.min((self.nodesize - HEADER_SIZE) / ITEM_SIZE) {
                let at = HEADER_SIZE + i * ITEM_SIZE;
                let key = Key::parse(&node, at);
                if key > max {
                    break;
                }
                if key >= min {
                    let (off, size) = (get32(&node, at + 17) as usize, get32(&node, at + 21) as usize);
                    let data = node.get(HEADER_SIZE + off..HEADER_SIZE + off + size).ok_or(Errno::EIO)?;
                    out.push((key, data.to_vec()));
                }
            }
            return Ok(());
        }
        // Child i holds keys from key[i] up to (not including) key[i + 1].
        let n = n.min((self.nodesize - HEADER_SIZE) / KEY_PTR_SIZE);
        for i in 0..n {
            let at = HEADER_SIZE + i * KEY_PTR_SIZE;
            if Key::parse(&node, at) > max {
                break;
            }
            if i + 1 < n && Key::parse(&node, at + KEY_PTR_SIZE) <= min {
                continue; // everything in this child is below `min`
            }
            self.walk(get64(&node, at + 17), level - 1, min, max, out)?;
        }
        Ok(())
    }

    /// The item with the largest key `<= key`, if any.
    fn search_le(&mut self, tree: Tree, key: Key) -> Result<Option<(Key, Vec<u8>)>, Errno> {
        let (mut bytenr, mut level) = (tree.bytenr, tree.level);
        loop {
            let node = self.read_node(bytenr)?;
            if node[HDR_LEVEL] != level {
                return Err(Errno::EIO);
            }
            let n = get32(&node, HDR_NRITEMS) as usize;
            let size = if level == 0 { ITEM_SIZE } else { KEY_PTR_SIZE };
            // The last slot whose key is <= key (a binary search would do too).
            let Some(i) = (0..n.min((self.nodesize - HEADER_SIZE) / size))
                .take_while(|&i| Key::parse(&node, HEADER_SIZE + i * size) <= key)
                .last()
            else {
                return Ok(None);
            };
            let at = HEADER_SIZE + i * size;
            if level == 0 {
                let (off, len) = (get32(&node, at + 17) as usize, get32(&node, at + 21) as usize);
                let data = node.get(HEADER_SIZE + off..HEADER_SIZE + off + len).ok_or(Errno::EIO)?;
                return Ok(Some((Key::parse(&node, at), data.to_vec())));
            }
            bytenr = get64(&node, at + 17);
            level -= 1;
        }
    }

    /// The data of the item with exactly this key.
    fn get(&mut self, tree: Tree, key: Key) -> Result<Option<Vec<u8>>, Errno> {
        Ok(self.search_le(tree, key)?.filter(|(k, _)| *k == key).map(|(_, d)| d))
    }

    /// A tree's root and (for subvolumes) top directory, from its ROOT_ITEM.
    /// A ROOT_ITEM's key offset is 0 or a transaction number: take the last.
    fn root_of(&mut self, id: u64) -> Result<(Tree, u64), Errno> {
        let (key, item) = self.search_le(self.root_tree, Key::new(id, ROOT_ITEM, u64::MAX))?.ok_or(Errno::ENOENT)?;
        if key.objectid != id || key.kind != ROOT_ITEM || item.len() <= ROOT_LEVEL {
            return Err(Errno::ENOENT);
        }
        Ok((Tree { bytenr: get64(&item, ROOT_BYTENR), level: item[ROOT_LEVEL] }, get64(&item, ROOT_DIRID)))
    }

    fn fs_tree(&mut self, subvol: u64) -> Result<(Tree, u64), Errno> {
        if let Some(t) = self.fs_trees.get(&subvol) {
            return Ok(*t);
        }
        let t = self.root_of(subvol)?;
        self.fs_trees.insert(subvol, t);
        Ok(t)
    }

    // ---- files and directories -----------------------------------------

    fn inode(&mut self, loc: Loc) -> Result<InodeItem, Errno> {
        let (tree, _) = self.fs_tree(loc.root)?;
        let d = self.get(tree, Key::new(loc.ino, INODE_ITEM, 0))?.ok_or(Errno::ENOENT)?;
        if d.len() < 160 {
            return Err(Errno::EIO);
        }
        // The four btrfs_timespecs (u64 seconds + u32 nanoseconds) at the
        // end: atime 112, ctime 124, mtime 136, otime 148.
        let ts = |at: usize| [get64(&d, at) as i64, get32(&d, at + 8) as i64];
        let times = [ts(112), ts(136), ts(124)];
        Ok(InodeItem {
            size: get64(&d, INODE_SIZE),
            mode: get32(&d, INODE_MODE),
            nlink: get32(&d, 40),
            uid: get32(&d, 44),
            gid: get32(&d, 48),
            flags: get64(&d, INODE_FLAGS),
            times,
        })
    }

    /// Where a directory entry points: an inode in the same tree, or the
    /// top directory of another subvolume.
    fn follow(&mut self, dir: Loc, entry: &DirItem) -> Result<Loc, Errno> {
        if entry.location.kind == ROOT_ITEM {
            let (_, top) = self.fs_tree(entry.location.objectid)?;
            Ok(Loc { root: entry.location.objectid, ino: top })
        } else {
            Ok(Loc { root: dir.root, ino: entry.location.objectid })
        }
    }

    /// Look a name up with one search: DIR_ITEMs are keyed by the name's
    /// hash (an item holds several entries if their hashes collide).
    fn lookup(&mut self, dir: Loc, name: &str) -> Result<Loc, Errno> {
        let (tree, _) = self.fs_tree(dir.root)?;
        let data = self.get(tree, Key::new(dir.ino, DIR_ITEM, name_hash(name.as_bytes())))?.ok_or(Errno::ENOENT)?;
        let entry = parse_dir_items(&data).into_iter().find(|e| e.name == name.as_bytes()).ok_or(Errno::ENOENT)?;
        self.follow(dir, &entry)
    }

    /// A directory's entries in creation order (its DIR_INDEX items).
    fn list(&mut self, dir: Loc) -> Result<Vec<DirItem>, Errno> {
        let (tree, _) = self.fs_tree(dir.root)?;
        let items = self.range(tree, Key::new(dir.ino, DIR_INDEX, 0), Key::new(dir.ino, DIR_INDEX, u64::MAX))?;
        Ok(items.iter().flat_map(|(_, d)| parse_dir_items(d)).collect())
    }

    /// Read file bytes at `pos` into `buf`; returns the count (0 at EOF).
    fn read_file(&mut self, loc: Loc, pos: u64, buf: &mut [u8]) -> Result<usize, Errno> {
        let inode = self.inode(loc)?;
        if pos >= inode.size {
            return Ok(0);
        }
        let n = (buf.len() as u64).min(inode.size - pos) as usize;
        let buf = &mut buf[..n];
        buf.fill(0); // holes (no extent at all) read as zeros
        let verify = inode.flags & INODE_NODATASUM == 0;
        let (tree, _) = self.fs_tree(loc.root)?;
        // The extent that starts at or before `pos`, and all up to the end.
        let first = match self.search_le(tree, Key::new(loc.ino, EXTENT_DATA, pos))? {
            Some((k, _)) if k.objectid == loc.ino && k.kind == EXTENT_DATA => k.offset,
            _ => 0,
        };
        let end = pos + n as u64;
        for (key, data) in self.range(tree, Key::new(loc.ino, EXTENT_DATA, first), Key::new(loc.ino, EXTENT_DATA, end - 1))? {
            let ext = Extent::parse(&data)?;
            // The overlap of this extent's file range and the request.
            let (from, to) = (key.offset.max(pos), (key.offset + ext.len()).min(end));
            if from >= to {
                continue;
            }
            let dst = &mut buf[(from - pos) as usize..(to - pos) as usize];
            let skip = (from - key.offset) as usize; // bytes into the extent's file range
            match ext {
                Extent::Prealloc { .. } => {} // reserved, never written: zeros
                Extent::Inline { compression: 0, data, .. } => {
                    let src = data.get(skip..skip + dst.len()).ok_or(Errno::EIO)?;
                    dst.copy_from_slice(src);
                }
                Extent::Inline { compression, data, ram_bytes } => {
                    let plain = decompress(compression, data, ram_bytes as usize, self.sectorsize)?;
                    dst.copy_from_slice(&plain[skip..skip + dst.len()]);
                }
                Extent::Regular { disk_bytenr: 0, .. } => {} // an explicit hole
                Extent::Regular { compression: 0, disk_bytenr, offset, .. } => {
                    self.read_data(disk_bytenr + offset + skip as u64, dst, verify)?;
                }
                Extent::Regular { compression, disk_bytenr, disk_num_bytes, offset, ram_bytes, .. } => {
                    let plain = self.decompressed(compression, disk_bytenr, disk_num_bytes, ram_bytes, verify)?;
                    let at = offset as usize + skip;
                    dst.copy_from_slice(plain.get(at..at + dst.len()).ok_or(Errno::EIO)?);
                }
            }
        }
        Ok(n)
    }

    /// A compressed extent, read, checked and decompressed whole. The last
    /// one is cached: `cat` reads a 128 KiB extent in many small pieces.
    fn decompressed(&mut self, compression: u8, bytenr: u64, disk_len: u64, ram: u64, verify: bool) -> Result<Arc<Vec<u8>>, Errno> {
        if let Some((b, data)) = &self.extent_cache {
            if *b == bytenr {
                return Ok(data.clone());
            }
        }
        let mut raw = vec![0u8; disk_len as usize];
        self.read_data(bytenr, &mut raw, verify)?;
        let plain = Arc::new(decompress(compression, &raw, ram as usize, self.sectorsize)?);
        self.extent_cache = Some((bytenr, plain.clone()));
        Ok(plain)
    }

    /// Read file data at a logical address, whole sectors at a time, and
    /// check each sector against the csum tree.
    fn read_data(&mut self, logical: u64, out: &mut [u8], verify: bool) -> Result<(), Errno> {
        let ss = self.sectorsize as u64;
        let start = logical / ss * ss;
        let len = (logical + out.len() as u64).next_multiple_of(ss) - start;
        let mut last_err = Errno::EIO;
        for copy in 0..self.copies(start) {
            let data = self.read_logical(start, len as usize, copy)?;
            match if verify { self.verify_data(start, &data) } else { Ok(()) } {
                Ok(()) => {
                    let skip = (logical - start) as usize;
                    out.copy_from_slice(&data[skip..skip + out.len()]);
                    return Ok(());
                }
                Err(e) => last_err = e,
            }
        }
        Err(last_err)
    }

    /// Compare each sector of `data` (at logical `start`) with its crc32c
    /// in the csum tree. EXTENT_CSUM items are keyed by the logical address
    /// of their first sector and hold one u32 per sector. Sectors without a
    /// checksum (NODATASUM files) are taken as they are.
    fn verify_data(&mut self, start: u64, data: &[u8]) -> Result<(), Errno> {
        let Some(tree) = self.csum_tree else { return Ok(()) };
        let ss = self.sectorsize;
        let mut item: Option<(u64, Vec<u8>)> = None;
        for (i, sector) in data.chunks(ss).enumerate() {
            let at = start + (i * ss) as u64;
            let covers = |it: &Option<(u64, Vec<u8>)>| matches!(it, Some((s, d)) if at >= *s && at < s + (d.len() / 4 * ss) as u64);
            if !covers(&item) {
                item = match self.search_le(tree, Key::new(CSUM_OBJECTID, EXTENT_CSUM, at))? {
                    Some((k, d)) if k.objectid == CSUM_OBJECTID && k.kind == EXTENT_CSUM => Some((k.offset, d)),
                    _ => None,
                };
                if !covers(&item) {
                    continue; // no checksum for this sector
                }
            }
            let (s, d) = item.as_ref().unwrap();
            let want = get32(d, ((at - s) / ss as u64) as usize * 4);
            let got = crc32c(sector);
            if got != want {
                crate::kprintln!("[btrfs] data at {}: checksum {:#010x}, should be {:#010x}", at, got, want);
                return Err(Errno::EIO);
            }
        }
        Ok(())
    }

    // ---- subvolumes and the boot log -------------------------------------

    /// The path of inode `ino` in subvolume `root`, from its INODE_REFs.
    fn path_in(&mut self, root: u64, mut ino: u64) -> Result<String, Errno> {
        let (tree, top) = self.fs_tree(root)?;
        let mut parts = Vec::new();
        while ino != top {
            let refs = self.range(tree, Key::new(ino, INODE_REF, 0), Key::new(ino, INODE_REF, u64::MAX))?;
            let (key, d) = refs.first().ok_or(Errno::EIO)?;
            // INODE_REF: index u64, name_len u16, name.
            let len = get16(d, 8) as usize;
            parts.push(String::from_utf8_lossy(d.get(10..10 + len).ok_or(Errno::EIO)?).into_owned());
            ino = key.offset; // the parent directory
        }
        parts.reverse();
        Ok(parts.join("/"))
    }

    /// Every subvolume below the top level, from the root tree's ROOT_REFs
    /// `(parent ROOT_REF child)`: dirid u64, sequence u64, name_len u16, name.
    fn subvolumes(&mut self) -> Result<Vec<Subvolume>, Errno> {
        let all = self.range(self.root_tree, Key::new(0, 0, 0), Key::new(u64::MAX, u8::MAX, u64::MAX))?;
        let refs: Vec<(u64, u64, u64, String)> = all
            .iter()
            .filter(|(k, d)| k.kind == ROOT_REF && d.len() >= 18)
            .map(|(k, d)| {
                let len = get16(d, 16) as usize;
                (k.objectid, k.offset, get64(d, 0), String::from_utf8_lossy(&d[18..(18 + len).min(d.len())]).into_owned())
            })
            .collect();
        let mut out = Vec::new();
        for (parent, child, dirid, name) in &refs {
            let mut path = self.path_in(*parent, *dirid)?;
            // Prefix the parent subvolume's own path (nested subvolumes).
            let mut p = *parent;
            while let Some((pp, _, pdir, pname)) = refs.iter().find(|r| r.1 == p) {
                let above = self.path_in(*pp, *pdir)?;
                path = [above, pname.clone(), path].iter().filter(|s| !s.is_empty()).cloned().collect::<Vec<_>>().join("/");
                p = *pp;
            }
            let full = if path.is_empty() { name.clone() } else { format!("{}/{}", path, name) };
            let read_only = all
                .iter()
                .rev()
                .find(|(k, _)| k.objectid == *child && k.kind == ROOT_ITEM)
                .map(|(_, d)| d.len() > ROOT_FLAGS && get64(d, ROOT_FLAGS) & ROOT_RDONLY != 0)
                .unwrap_or(false);
            out.push(Subvolume { id: *child, path: full, read_only });
        }
        Ok(out)
    }

    fn profile(&self, what: u64) -> &'static str {
        match self.chunks.iter().find(|c| c.kind & what != 0) {
            Some(c) if c.kind & BG_DUP != 0 => "DUP",
            Some(_) => "single",
            None => "none",
        }
    }
}

/// A DIR_ITEM or DIR_INDEX item's entries: location key (17), transid u64,
/// data_len u16, name_len u16, type u8, then the name (and xattr data).
fn parse_dir_items(mut d: &[u8]) -> Vec<DirItem> {
    let mut out = Vec::new();
    while d.len() >= 30 {
        let (data_len, name_len) = (get16(d, 25) as usize, get16(d, 27) as usize);
        let Some(name) = d.get(30..30 + name_len) else { break };
        out.push(DirItem { location: Key::parse(d, 0), name: name.to_vec(), file_type: d[29] });
        d = d.get(30 + name_len + data_len..).unwrap_or(&[]);
    }
    out
}

fn kind_of_mode(mode: u32) -> InodeKind {
    match mode & S_IFMT {
        S_IFDIR => InodeKind::Directory,
        S_IFLNK => InodeKind::Symlink,
        _ => InodeKind::File,
    }
}

// ---------------------------------------------------------------------------
// The VFS side
// ---------------------------------------------------------------------------

pub struct BtrfsFs {
    vol: Arc<Mutex<Volume>>,
    root: Loc,
}

impl BtrfsFs {
    /// Mount, or say in words why not (bad checksum, sha256, RAID...).
    pub fn mount(dev: Arc<dyn BlockDevice>) -> Result<Arc<BtrfsFs>, String> {
        let mut vol = Volume::open(dev)?;
        let (_, top) = vol.fs_tree(vol.default_subvol).map_err(|e| format!("{:?}", e))?;
        let root = Loc { root: vol.default_subvol, ino: top };
        Ok(Arc::new(BtrfsFs { vol: Arc::new(Mutex::new(vol)), root }))
    }

    /// For the boot log, e.g. `btrfs volume "TYLERBTRFS" (16 KiB nodes,
    /// metadata DUP, data single, 2 subvolumes)`.
    pub fn describe(&self) -> String {
        let mut v = self.vol.lock();
        let subvols = v.subvolumes().map(|s| s.len()).unwrap_or(0);
        format!(
            "btrfs volume \"{}\" ({} KiB nodes, metadata {}, data {}, {} subvolume{}, read-only)",
            v.label,
            v.nodesize / 1024,
            v.profile(BG_METADATA | BG_SYSTEM),
            v.profile(BG_DATA),
            subvols,
            if subvols == 1 { "" } else { "s" }
        )
    }

    pub fn label(&self) -> String {
        self.vol.lock().label.clone()
    }

    /// (sector size, node size, generation, total bytes, bytes used).
    pub fn geometry(&self) -> (usize, usize, u64, u64, u64) {
        let v = self.vol.lock();
        (v.sectorsize, v.nodesize, v.generation, v.total_bytes, v.bytes_used)
    }

    pub fn subvolumes(&self) -> Result<Vec<Subvolume>, Errno> {
        self.vol.lock().subvolumes()
    }

    // ---- for tests/btrfs.rs, which damages bytes on purpose to check
    //      that the checksums catch it ------------------------------------

    /// Byte offsets on the disk of every copy of a logical address.
    pub fn physical(&self, logical: u64) -> Vec<u64> {
        let v = self.vol.lock();
        v.chunk(logical).map(|(c, into)| c.copies.iter().map(|p| p + into).collect()).unwrap_or_default()
    }

    /// The logical address of the default subvolume's FS tree root node.
    pub fn fs_tree_root(&self) -> u64 {
        let mut v = self.vol.lock();
        let id = v.default_subvol;
        v.fs_tree(id).map(|(t, _)| t.bytenr).unwrap_or(0)
    }

    /// The logical address of a file's first on-disk extent (`path` is
    /// relative to the volume's root, no symlinks).
    pub fn first_extent(&self, path: &str) -> Result<u64, Errno> {
        let mut v = self.vol.lock();
        let mut loc = self.root;
        for name in path.split('/').filter(|n| !n.is_empty()) {
            loc = v.lookup(loc, name)?;
        }
        let (tree, _) = v.fs_tree(loc.root)?;
        for (_, data) in v.range(tree, Key::new(loc.ino, EXTENT_DATA, 0), Key::new(loc.ino, EXTENT_DATA, u64::MAX))? {
            if let Extent::Regular { disk_bytenr, .. } = Extent::parse(&data)? {
                if disk_bytenr != 0 {
                    return Ok(disk_bytenr);
                }
            }
        }
        Err(Errno::ENOENT)
    }
}

impl FileSystem for BtrfsFs {
    fn name(&self) -> &'static str {
        "btrfs"
    }
    fn root(&self) -> Arc<dyn Inode> {
        Arc::new(BtrfsInode { vol: self.vol.clone(), loc: self.root, kind: InodeKind::Directory })
    }
    /// From the superblock's totals (in sectors). btrfs doesn't count
    /// inodes (it makes them as needed), so files = 0, like Linux.
    fn statfs(&self) -> super::StatFs {
        let v = self.vol.lock();
        let bs = v.sectorsize.max(1) as u64;
        let free = v.total_bytes.saturating_sub(v.bytes_used) / bs;
        super::StatFs {
            magic: super::BTRFS_MAGIC,
            block_size: bs,
            blocks: v.total_bytes / bs,
            free_blocks: free,
            avail_blocks: free,
            files: 0,
            free_files: 0,
            name_max: 255,
            read_only: true, // our driver only reads
        }
    }
}

/// An inode number unique across subvolumes: each subvolume numbers its
/// inodes from 256, so other subvolumes' get their tree id on top.
fn ino_of(loc: Loc) -> u64 {
    if loc.root == FS_TREE { loc.ino } else { loc.ino | loc.root << 40 }
}

/// A file, directory or symlink: (subvolume, inode number).
pub struct BtrfsInode {
    vol: Arc<Mutex<Volume>>,
    loc: Loc,
    kind: InodeKind,
}

impl BtrfsInode {
    fn dir_only(&self) -> Result<(), Errno> {
        if self.kind == InodeKind::Directory { Ok(()) } else { Err(Errno::ENOTDIR) }
    }
}

impl Inode for BtrfsInode {
    fn kind(&self) -> InodeKind {
        self.kind
    }

    fn size(&self) -> usize {
        if self.kind == InodeKind::Directory {
            return self.list().map(|l| l.len()).unwrap_or(0);
        }
        self.vol.lock().inode(self.loc).map(|i| i.size as usize).unwrap_or(0)
    }

    fn mode(&self) -> u32 {
        self.vol.lock().inode(self.loc).map(|i| i.mode & 0o7777).unwrap_or(0)
    }

    fn times(&self) -> Option<[[i64; 2]; 3]> {
        self.vol.lock().inode(self.loc).ok().map(|i| i.times)
    }

    fn readlink(&self) -> Result<String, Errno> {
        if self.kind != InodeKind::Symlink {
            return Err(Errno::EINVAL);
        }
        // A symlink's target is its file data (an inline extent).
        let mut vol = self.vol.lock();
        let size = vol.inode(self.loc)?.size as usize;
        let mut buf = vec![0u8; size];
        let n = vol.read_file(self.loc, 0, &mut buf)?;
        String::from_utf8(buf[..n].to_vec()).map_err(|_| Errno::EINVAL)
    }

    fn read_at(&self, offset: usize, buf: &mut [u8]) -> Result<usize, Errno> {
        if self.kind == InodeKind::Directory {
            return Err(Errno::EISDIR);
        }
        self.vol.lock().read_file(self.loc, offset as u64, buf)
    }

    fn lookup(&self, name: &str) -> Result<Arc<dyn Inode>, Errno> {
        self.dir_only()?;
        let mut vol = self.vol.lock();
        let loc = vol.lookup(self.loc, name)?;
        let kind = kind_of_mode(vol.inode(loc)?.mode);
        Ok(Arc::new(BtrfsInode { vol: self.vol.clone(), loc, kind }))
    }

    fn list(&self) -> Result<Vec<DirEntry>, Errno> {
        self.dir_only()?;
        let entries = self.vol.lock().list(self.loc)?;
        Ok(entries
            .into_iter()
            .map(|e| DirEntry {
                ino: if e.location.kind == ROOT_ITEM { 256 | e.location.objectid << 40 } else { ino_of(Loc { root: self.loc.root, ino: e.location.objectid }) },
                name: String::from_utf8_lossy(&e.name).into_owned(),
                kind: match e.file_type {
                    2 => InodeKind::Directory,
                    7 => InodeKind::Symlink,
                    _ => InodeKind::File,
                },
            })
            .collect())
    }

    // Read-only: everything that would change the disk.
    fn write_at(&self, _offset: usize, _buf: &[u8]) -> Result<usize, Errno> {
        Err(Errno::EROFS)
    }
    fn truncate(&self) -> Result<(), Errno> {
        Err(Errno::EROFS)
    }
    fn set_len(&self, _len: usize) -> Result<(), Errno> {
        Err(Errno::EROFS)
    }
    fn set_mode(&self, _mode: u32) -> Result<(), Errno> {
        Err(Errno::EROFS)
    }
    fn set_times(&self, _atime: Option<[i64; 2]>, _mtime: Option<[i64; 2]>) -> Result<(), Errno> {
        Err(Errno::EROFS)
    }
    fn create(&self, _name: &str, _kind: InodeKind) -> Result<Arc<dyn Inode>, Errno> {
        Err(Errno::EROFS)
    }
    fn remove(&self, _name: &str) -> Result<(), Errno> {
        Err(Errno::EROFS)
    }
    fn set_owner(&self, _uid: Option<u32>, _gid: Option<u32>) -> Result<(), Errno> {
        Err(Errno::EROFS)
    }
    fn symlink(&self, _name: &str, _target: &str) -> Result<Arc<dyn Inode>, Errno> {
        Err(Errno::EROFS)
    }
    fn link(&self, _name: &str, _target: &Arc<dyn Inode>) -> Result<(), Errno> {
        Err(Errno::EROFS)
    }
    fn rename_entry(&self, _old: &str, _new_dir: &Arc<dyn Inode>, _new: &str) -> Result<(), Errno> {
        Err(Errno::EROFS)
    }

    fn ino(&self) -> Option<u64> {
        Some(ino_of(self.loc))
    }
    fn nlink(&self) -> Option<u64> {
        self.vol.lock().inode(self.loc).ok().map(|i| i.nlink as u64)
    }
    fn owner(&self) -> (u32, u32) {
        self.vol.lock().inode(self.loc).map(|i| (i.uid, i.gid)).unwrap_or((0, 0))
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test_case]
    fn crc32c_known_answers() {
        assert_eq!(crc32c(b"123456789"), 0xE306_9283); // the standard check value
        assert_eq!(name_hash(b"default"), 2378154706); // seen in mkfs.btrfs's root tree
    }

    #[test_case]
    fn prealloc_and_hole_extents_read_as_nothing() {
        // mkfs.btrfs never makes prealloc extents, so build one by hand:
        // generation, ram_bytes, compression, encryption, other_encoding,
        // type 2, disk_bytenr, disk_num_bytes, offset, num_bytes.
        let mut item = vec![0u8; EXT_REGULAR_SIZE];
        item[EXT_TYPE] = 2;
        item[EXT_NUM_BYTES..EXT_NUM_BYTES + 8].copy_from_slice(&8192u64.to_le_bytes());
        assert!(matches!(Extent::parse(&item), Ok(Extent::Prealloc { num_bytes: 8192 })));
        item[EXT_TYPE] = 1; // regular with disk_bytenr 0: an explicit hole
        assert!(matches!(Extent::parse(&item), Ok(Extent::Regular { disk_bytenr: 0, .. })));
        item[EXT_ENCRYPTION] = 1;
        assert!(Extent::parse(&item).is_err());
    }

    #[test_case]
    fn lzo_literals_and_overlapping_match() {
        // "abc" as a first-byte literal run (17 + 3), then an M2 match of
        // length 6 at distance 3 (t = (6-1)<<5 | (3-1)<<2 = 0xA8, next byte 0),
        // then the end marker 0x11 0x00 0x00.
        let mut out = Vec::new();
        super::super::lzo::decompress(&[20, b'a', b'b', b'c', 0xA8, 0, 0x11, 0, 0], &mut out, 100).unwrap();
        assert_eq!(&out, b"abcabcabc");
    }
}