rust-kernel

//! ext2, the "second extended file system" (Rémy Card, 1993): Linux's main
//! file system through the 1990s, and the base that ext3 and ext4 grew from.
//! Written by hand here, no crate. It's the classic file system to learn
//! from: everything on disk is an array of fixed-size records.
//!
//! # On-disk layout
//!
//! The disk is cut into **blocks** of 1, 2 or 4 KiB (`1024 << s_log_block_size`).
//! Blocks are numbered from 0 and grouped into **block groups** of
//! `s_blocks_per_group` blocks (8192 with 1 KiB blocks). Our 32 MiB disk has
//! 1 KiB blocks, so it has 4 groups:
//!
//! ```text
//! byte 0     1024          block 2 (with 1 KiB blocks)
//! | boot     | superblock  | group descriptor table | reserved GDT blocks |
//! | block bitmap | inode bitmap | inode table ...   | data blocks ...      |   <- group 0
//! | (superblock + GDT backup) | block bitmap | inode bitmap | inode table | data... |   <- group 1
//! ...
//! ```
//!
//! * **Superblock** (always at byte 1024, 1024 bytes): the totals.
//!   It records the block size, blocks and inodes per group, free
//!   counts, the magic number 0xEF53, the revision and feature flags.
//!   "sparse_super" keeps backup copies only in groups 0, 1 and powers of
//!   3, 5 and 7. We read and update only the primary copy, like Linux.
//! * **Group descriptor table** (the block after the superblock): 32 bytes per
//!   group, saying where that group's block bitmap, inode bitmap and inode
//!   table are, and its free block and inode counts.
//! * **Bitmaps**: one block each, one bit per block or inode in the group;
//!   1 = in use. Allocating means finding a 0 bit.
//! * **Inode table**: `s_inodes_per_group` inodes of `s_inode_size` bytes
//!   (128 in revision 0; usually 256 in revision 1, where only the first 128
//!   are classic ext2 fields). Inode numbers start at 1; inode N lives in
//!   group (N-1) / inodes_per_group. Inode 2 is the root directory, 1-10 are
//!   reserved, and 11 is usually lost+found.
//! * **An inode** describes one file. It holds the mode (type + permissions),
//!   size, link count and times, plus 15 block pointers:
//!
//!   ```text
//!   i_block[0..12]  -> data blocks 0..11 directly
//!   i_block[12]     -> a block of block numbers           (single indirect)
//!   i_block[13]     -> a block of single-indirect blocks  (double indirect)
//!   i_block[14]     -> a block of double-indirect blocks  (triple indirect)
//!   ```
//!
//!   With 1 KiB blocks an indirect block holds 256 numbers. Direct blocks
//!   cover 12 KiB, single indirect up to 268 KiB, double up to ~64 MiB, and
//!   triple up to ~16 GiB. A 0 pointer is a *hole*, which reads as zeros
//!   (sparse files).
//! * **A directory** is a file of variable-length entries:
//!   `inode u32, rec_len u16, name_len u8, file_type u8, name`. The entries
//!   are padded to 4 bytes and never cross a block. `rec_len` jumps to the
//!   next entry, so deleting just adds the entry's length to the previous
//!   one, and the last entry stretches to the end of the block. Revision 0
//!   has no file_type byte (name_len is 16 bits). Every directory starts
//!   with "." and "..".
//! * **Symlinks**: a target shorter than 60 bytes is stored right inside
//!   `i_block` (a "fast" symlink). Longer ones get a data block ("slow").
//!
//! # What we do
//!
//! * **Reading:** all of the above, including holes and both symlink kinds.
//!   Large "dir_index" (htree) directories also work: their hash index
//!   hides inside entries that plain ext2 code skips.
//! * **Writing:**
//!   - We create files and directories, write and append, truncate to 0,
//!     and unlink and rmdir.
//!   - Blocks and inodes come from the bitmaps. The free counts are kept
//!     right in the group descriptors and the superblock, so `e2fsck` finds
//!     a clean file system.
//!   - When we change an htree directory, we clear its index flag, like
//!     Linux's ext2 driver does.
//! * **Not supported:**
//!   - Creating symlinks or hard links, and rename.
//!   - Extended attribute blocks: deleting a file that has one gives
//!     EOPNOTSUPP.
//!   - Files bigger than 2 GiB on write.
//! * **Unknown features:**
//!   - A file system with an "incompat" feature we don't know refuses to
//!     mount (ext4's extents, for example).
//!   - An unknown "ro_compat" feature mounts read-only.
//!
//! Every operation reads what it needs straight from the disk: there's no
//! cache, and writes go straight through. One Mutex serializes the volume.
//! There's no journal (that's ext3), so a crash in the middle of an
//! operation can leave work for e2fsck, just like real ext2.

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

const MAGIC: u16 = 0xEF53;
const ROOT_INO: u32 = 2;

// Superblock fields (byte offsets inside the 1024-byte superblock).
const SB_INODES_COUNT: usize = 0;
const SB_BLOCKS_COUNT: usize = 4;
const SB_R_BLOCKS: usize = 8; // blocks reserved for root
const SB_FREE_BLOCKS: usize = 12;
const SB_FREE_INODES: usize = 16;
const SB_FIRST_DATA_BLOCK: usize = 20; // block holding the superblock: 1 with 1 KiB blocks, else 0
const SB_LOG_BLOCK_SIZE: usize = 24;
const SB_BLOCKS_PER_GROUP: usize = 32;
const SB_INODES_PER_GROUP: usize = 40;
const SB_WTIME: usize = 48;
const SB_MAGIC: usize = 56;
const SB_REV_LEVEL: usize = 76;
const SB_FIRST_INO: usize = 84; // revision 1+
const SB_INODE_SIZE: usize = 88; // revision 1+ (u16)
const SB_FEATURE_INCOMPAT: usize = 96;
const SB_FEATURE_RO_COMPAT: usize = 100;
const SB_VOLUME_NAME: usize = 120; // 16 bytes

// Feature flags we understand.
const INCOMPAT_FILETYPE: u32 = 0x0002; // directory entries have a file type byte
const RO_COMPAT_SPARSE_SUPER: u32 = 0x0001; // fewer superblock backups
const RO_COMPAT_LARGE_FILE: u32 = 0x0002; // files > 2 GiB (we only read them)
const RO_COMPAT_BTREE_DIR: u32 = 0x0004; // never used by anyone

// Group descriptor fields (32 bytes per group).
const GD_SIZE: usize = 32;
const GD_BLOCK_BITMAP: usize = 0;
const GD_INODE_BITMAP: usize = 4;
const GD_INODE_TABLE: usize = 8;
const GD_FREE_BLOCKS: usize = 12; // u16
const GD_FREE_INODES: usize = 14; // u16
const GD_USED_DIRS: usize = 16; // u16

// Inode fields (the classic first 128 bytes).
const I_MODE: usize = 0; // u16
const I_UID: usize = 2; // u16 (low half; the high half is at I_UID_HIGH)
const I_GID: usize = 24; // u16
const I_UID_HIGH: usize = 120; // in the Linux part of "osd2"
const I_GID_HIGH: usize = 122;
const I_SIZE: usize = 4;
const I_ATIME: usize = 8;
const I_CTIME: usize = 12;
const I_MTIME: usize = 16;
const I_DTIME: usize = 20; // deletion time (0 = in use)
const I_LINKS: usize = 26; // u16
const I_SECTORS: usize = 28; // "i_blocks": counted in 512-byte sectors!
const I_FLAGS: usize = 32;
const I_BLOCK: usize = 40; // 15 block pointers (60 bytes)
const I_FILE_ACL: usize = 104; // extended attribute block
const I_SIZE_HIGH: usize = 108; // upper 32 bits of the size (regular files)

// i_mode: the top 4 bits are the type, the low 12 the permissions.
const S_IFMT: u16 = 0o170000;
const S_IFREG: u16 = 0o100000;
const S_IFDIR: u16 = 0o040000;
const S_IFLNK: u16 = 0o120000;

// Directory entry file types (with INCOMPAT_FILETYPE).
const FT_REG: u8 = 1;
const FT_DIR: u8 = 2;
const FT_SYMLINK: u8 = 7;

const INDEX_FL: u32 = 0x1000; // directory has an htree index

/// Biggest file we write (bigger needs the large_file feature handling).
const MAX_WRITE_SIZE: u64 = (1 << 31) - 1;

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], b[at + 1], b[at + 2], b[at + 3]])
}
fn put16(b: &mut [u8], at: usize, v: u16) {
    b[at..at + 2].copy_from_slice(&v.to_le_bytes());
}
fn put32(b: &mut [u8], at: usize, v: u32) {
    b[at..at + 4].copy_from_slice(&v.to_le_bytes());
}

/// Does `dev` hold an ext2 (or ext3/ext4) file system? Checks the magic
/// number in the superblock at byte 1024 (= sectors 2 and 3).
pub fn probe(dev: &dyn BlockDevice) -> bool {
    let mut sb = [0u8; 1024];
    dev.read_sectors(2, &mut sb).is_ok() && get16(&sb, SB_MAGIC) == MAGIC
}

// ---------------------------------------------------------------------------
// One inode, as on disk
// ---------------------------------------------------------------------------

/// An inode's bytes (all `s_inode_size` of them, so writing it back keeps
/// the fields we don't interpret), with accessors for the ones we use.
#[derive(Clone)]
struct DiskInode {
    ino: u32,
    raw: Vec<u8>,
}

impl DiskInode {
    fn mode(&self) -> u16 {
        get16(&self.raw, I_MODE)
    }
    fn kind(&self) -> InodeKind {
        match self.mode() & S_IFMT {
            S_IFDIR => InodeKind::Directory,
            S_IFLNK => InodeKind::Symlink,
            _ => InodeKind::File, // regular files (devices, fifos: treated as files)
        }
    }
    fn is_regular(&self) -> bool {
        self.mode() & S_IFMT == S_IFREG
    }
    fn size(&self) -> u64 {
        let high = if self.is_regular() { get32(&self.raw, I_SIZE_HIGH) as u64 } else { 0 };
        (high << 32) | get32(&self.raw, I_SIZE) as u64
    }
    fn set_size(&mut self, size: u64) {
        put32(&mut self.raw, I_SIZE, size as u32);
        if self.is_regular() {
            put32(&mut self.raw, I_SIZE_HIGH, (size >> 32) as u32);
        }
    }
    fn links(&self) -> u16 {
        get16(&self.raw, I_LINKS)
    }
    fn set_links(&mut self, n: u16) {
        put16(&mut self.raw, I_LINKS, n);
    }
    fn sectors(&self) -> u32 {
        get32(&self.raw, I_SECTORS)
    }
    fn add_sectors(&mut self, n: i64) {
        let sectors = (self.sectors() as i64 + n) as u32;
        put32(&mut self.raw, I_SECTORS, sectors);
    }
    fn block(&self, slot: usize) -> u32 {
        get32(&self.raw, I_BLOCK + 4 * slot)
    }
    fn set_block(&mut self, slot: usize, b: u32) {
        put32(&mut self.raw, I_BLOCK + 4 * slot, b);
    }
    fn file_acl(&self) -> u32 {
        get32(&self.raw, I_FILE_ACL)
    }
    fn set_times(&mut self, which: &[usize], t: u32) {
        which.iter().for_each(|&at| put32(&mut self.raw, at, t));
    }
    fn owner(&self) -> (u32, u32) {
        let uid = get16(&self.raw, I_UID) as u32 | (get16(&self.raw, I_UID_HIGH) as u32) << 16;
        let gid = get16(&self.raw, I_GID) as u32 | (get16(&self.raw, I_GID_HIGH) as u32) << 16;
        (uid, gid)
    }
    fn set_owner(&mut self, uid: Option<u32>, gid: Option<u32>) {
        if let Some(uid) = uid {
            put16(&mut self.raw, I_UID, uid as u16);
            put16(&mut self.raw, I_UID_HIGH, (uid >> 16) as u16);
        }
        if let Some(gid) = gid {
            put16(&mut self.raw, I_GID, gid as u16);
            put16(&mut self.raw, I_GID_HIGH, (gid >> 16) as u16);
        }
    }
    /// The directory-entry type byte for this inode.
    fn file_type(&self) -> u8 {
        match self.kind() {
            InodeKind::Directory => FT_DIR,
            InodeKind::Symlink => FT_SYMLINK,
            _ => FT_REG,
        }
    }
}

/// One directory entry, as read from disk.
struct RawDirEntry {
    ino: u32,
    name: String,
    file_type: u8, // 0 = unknown (revision 0 file systems)
}

/// Size a directory entry with this name needs: 8-byte header + name,
/// rounded up to 4 bytes.
fn entry_size(name_len: usize) -> usize {
    (8 + name_len + 3) & !3
}

// ---------------------------------------------------------------------------
// The volume: superblock, group descriptors and all the disk work
// ---------------------------------------------------------------------------

struct Volume {
    dev: Arc<dyn BlockDevice>,
    sb: Vec<u8>,  // the 1024-byte superblock, as on disk
    gdt: Vec<u8>, // the group descriptor table, as on disk (whole blocks)
    block_size: usize,
    groups: u32,
    gdt_block: u32, // where the descriptor table starts
    inode_size: usize,
    first_ino: u32, // first inode for ordinary files (11)
    revision: u32,
    filetype: bool, // directory entries carry a file type
    writable: bool,
}

impl Volume {
    fn open(dev: Arc<dyn BlockDevice>) -> Result<Volume, Errno> {
        let mut sb = vec![0u8; 1024];
        dev.read_sectors(2, &mut sb)?;
        if get16(&sb, SB_MAGIC) != MAGIC {
            return Err(Errno::EINVAL);
        }
        let log = get32(&sb, SB_LOG_BLOCK_SIZE);
        if log > 6 {
            return Err(Errno::EINVAL); // > 64 KiB: corrupted
        }
        let block_size = 1024usize << log;
        let revision = get32(&sb, SB_REV_LEVEL);
        let (inode_size, first_ino, incompat, ro_compat) = if revision == 0 {
            (128, 11, 0, 0) // revision 0: fixed sizes, no feature flags
        } else {
            (
                get16(&sb, SB_INODE_SIZE) as usize,
                get32(&sb, SB_FIRST_INO),
                get32(&sb, SB_FEATURE_INCOMPAT),
                get32(&sb, SB_FEATURE_RO_COMPAT),
            )
        };
        if inode_size < 128 || !inode_size.is_power_of_two() || inode_size > block_size {
            return Err(Errno::EINVAL);
        }
        // "incompat" features change the format: if we don't know one, we
        // can't even read safely (ext4 extents, a journal needing recovery...).
        if incompat & !INCOMPAT_FILETYPE != 0 {
            return Err(Errno::EOPNOTSUPP);
        }
        // "ro_compat" features: reading is fine, writing could break them.
        let writable = ro_compat & !(RO_COMPAT_SPARSE_SUPER | RO_COMPAT_LARGE_FILE | RO_COMPAT_BTREE_DIR) == 0;

        let blocks_count = get32(&sb, SB_BLOCKS_COUNT);
        let first_data = get32(&sb, SB_FIRST_DATA_BLOCK);
        let per_group = get32(&sb, SB_BLOCKS_PER_GROUP);
        if per_group == 0 || get32(&sb, SB_INODES_PER_GROUP) == 0 || blocks_count <= first_data {
            return Err(Errno::EINVAL);
        }
        let groups = (blocks_count - first_data).div_ceil(per_group);
        let gdt_block = first_data + 1;
        let gdt_blocks = (groups as usize * GD_SIZE).div_ceil(block_size);
        let mut gdt = vec![0u8; gdt_blocks * block_size];
        dev.read_sectors(gdt_block as u64 * (block_size / SECTOR_SIZE) as u64, &mut gdt)?;
        Ok(Volume {
            dev,
            sb,
            gdt,
            block_size,
            groups,
            gdt_block,
            inode_size,
            first_ino,
            revision,
            filetype: incompat & INCOMPAT_FILETYPE != 0,
            writable,
        })
    }

    fn sb32(&self, at: usize) -> u32 {
        get32(&self.sb, at)
    }

    /// Timestamp for new and changed inodes: the wall clock (stage 17;
    /// before, with no clock driver, the superblock's "last written" time).
    fn now(&self) -> u32 {
        (super::now_timespec()[0].clamp(0, u32::MAX as i64) as u32).max(self.sb32(SB_WTIME)).max(1)
    }

    // ---- blocks ----------------------------------------------------------

    fn read_block(&self, block: u32) -> Result<Vec<u8>, Errno> {
        if block == 0 || block >= self.sb32(SB_BLOCKS_COUNT) {
            return Err(Errno::EIO); // a bad pointer: corrupted file system
        }
        let mut data = vec![0u8; self.block_size];
        self.dev.read_sectors(block as u64 * (self.block_size / SECTOR_SIZE) as u64, &mut data)?;
        Ok(data)
    }

    fn write_block(&self, block: u32, data: &[u8]) -> Result<(), Errno> {
        if block == 0 || block >= self.sb32(SB_BLOCKS_COUNT) {
            return Err(Errno::EIO);
        }
        self.dev.write_sectors(block as u64 * (self.block_size / SECTOR_SIZE) as u64, data)
    }

    // ---- group descriptors and counters ----------------------------------

    fn gd32(&self, group: u32, field: usize) -> u32 {
        get32(&self.gdt, group as usize * GD_SIZE + field)
    }
    fn gd16(&self, group: u32, field: usize) -> u16 {
        get16(&self.gdt, group as usize * GD_SIZE + field)
    }

    /// Change a group's free-block / free-inode / directory counts (and the
    /// superblock totals), and write both back to disk.
    fn adjust_counts(&mut self, group: u32, blocks: i32, inodes: i32, dirs: i32) -> Result<(), Errno> {
        let at = group as usize * GD_SIZE;
        for (field, delta) in [(GD_FREE_BLOCKS, blocks), (GD_FREE_INODES, inodes), (GD_USED_DIRS, dirs)] {
            let v = get16(&self.gdt, at + field) as i32 + delta;
            put16(&mut self.gdt, at + field, v as u16);
        }
        for (field, delta) in [(SB_FREE_BLOCKS, blocks), (SB_FREE_INODES, inodes)] {
            let v = get32(&self.sb, field) as i64 + delta as i64;
            put32(&mut self.sb, field, v as u32);
        }
        // Write the descriptor table block holding this group, then the
        // superblock (sectors 2-3, wherever block 0/1 boundaries are).
        let index = at / self.block_size;
        let bs = self.block_size;
        self.write_block(self.gdt_block + index as u32, &self.gdt[index * bs..(index + 1) * bs])?;
        self.dev.write_sectors(2, &self.sb)
    }

    // ---- bitmaps: allocating and freeing ---------------------------------

    /// Find a 0 bit among the first `bits` of group `group`'s bitmap (block
    /// or inode bitmap, by `field`), set it, and return its index.
    fn take_bit(&self, group: u32, field: usize, bits: u32) -> Result<Option<u32>, Errno> {
        let block = self.gd32(group, field);
        let mut map = self.read_block(block)?;
        for i in 0..bits.min(self.block_size as u32 * 8) {
            let (byte, mask) = ((i / 8) as usize, 1u8 << (i % 8));
            if map[byte] & mask == 0 {
                map[byte] |= mask;
                self.write_block(block, &map)?;
                return Ok(Some(i));
            }
        }
        Ok(None) // the counts said there was room: they were wrong
    }

    fn clear_bit(&self, group: u32, field: usize, i: u32) -> Result<(), Errno> {
        let block = self.gd32(group, field);
        let mut map = self.read_block(block)?;
        let (byte, mask) = ((i / 8) as usize, 1u8 << (i % 8));
        if map[byte] & mask == 0 {
            return Err(Errno::EIO); // freeing something free: corrupted
        }
        map[byte] &= !mask;
        self.write_block(block, &map)
    }

    /// Allocate a block, preferably in `goal` (the group of its inode, so a
    /// file's blocks stay near each other). The new block is zeroed.
    fn alloc_block(&mut self, goal: u32) -> Result<u32, Errno> {
        let per_group = self.sb32(SB_BLOCKS_PER_GROUP);
        let first_data = self.sb32(SB_FIRST_DATA_BLOCK);
        for k in 0..self.groups {
            let group = (goal + k) % self.groups;
            if self.gd16(group, GD_FREE_BLOCKS) == 0 {
                continue;
            }
            // The last group can be shorter than the others.
            let start = first_data + group * per_group;
            let bits = per_group.min(self.sb32(SB_BLOCKS_COUNT) - start);
            if let Some(i) = self.take_bit(group, GD_BLOCK_BITMAP, bits)? {
                self.adjust_counts(group, -1, 0, 0)?;
                let block = start + i;
                self.write_block(block, &vec![0u8; self.block_size])?;
                return Ok(block);
            }
        }
        Err(Errno::ENOSPC)
    }

    fn free_block(&mut self, block: u32) -> Result<(), Errno> {
        let first_data = self.sb32(SB_FIRST_DATA_BLOCK);
        if block < first_data || block >= self.sb32(SB_BLOCKS_COUNT) {
            return Err(Errno::EIO);
        }
        let per_group = self.sb32(SB_BLOCKS_PER_GROUP);
        let group = (block - first_data) / per_group;
        self.clear_bit(group, GD_BLOCK_BITMAP, (block - first_data) % per_group)?;
        self.adjust_counts(group, 1, 0, 0)
    }

    /// Allocate an inode number, preferably in group `goal`, and zero it.
    fn alloc_inode(&mut self, goal: u32, dir: bool) -> Result<DiskInode, Errno> {
        let per_group = self.sb32(SB_INODES_PER_GROUP);
        for k in 0..self.groups {
            let group = (goal + k) % self.groups;
            if self.gd16(group, GD_FREE_INODES) == 0 {
                continue;
            }
            if let Some(i) = self.take_bit(group, GD_INODE_BITMAP, per_group)? {
                let ino = group * per_group + i + 1; // inode numbers start at 1
                if ino < self.first_ino {
                    return Err(Errno::EIO); // reserved inodes must be marked used
                }
                self.adjust_counts(group, 0, -1, dir as i32)?;
                let inode = DiskInode { ino, raw: vec![0u8; self.inode_size] };
                self.write_inode(&inode)?;
                return Ok(inode);
            }
        }
        Err(Errno::ENOSPC)
    }

    fn free_inode(&mut self, ino: u32, dir: bool) -> Result<(), Errno> {
        let per_group = self.sb32(SB_INODES_PER_GROUP);
        let group = (ino - 1) / per_group;
        self.clear_bit(group, GD_INODE_BITMAP, (ino - 1) % per_group)?;
        self.adjust_counts(group, 0, 1, -(dir as i32))
    }

    // ---- inodes ----------------------------------------------------------

    /// Which block of the inode table holds inode `ino`, and where in it.
    fn inode_location(&self, ino: u32) -> Result<(u32, usize), Errno> {
        if ino == 0 || ino > self.sb32(SB_INODES_COUNT) {
            return Err(Errno::EIO);
        }
        let per_group = self.sb32(SB_INODES_PER_GROUP);
        let (group, index) = ((ino - 1) / per_group, (ino - 1) % per_group);
        let byte = index as usize * self.inode_size;
        let block = self.gd32(group, GD_INODE_TABLE) + (byte / self.block_size) as u32;
        Ok((block, byte % self.block_size))
    }

    fn read_inode(&self, ino: u32) -> Result<DiskInode, Errno> {
        let (block, at) = self.inode_location(ino)?;
        let data = self.read_block(block)?;
        Ok(DiskInode { ino, raw: data[at..at + self.inode_size].to_vec() })
    }

    fn write_inode(&self, inode: &DiskInode) -> Result<(), Errno> {
        let (block, at) = self.inode_location(inode.ino)?;
        let mut data = self.read_block(block)?;
        data[at..at + self.inode_size].copy_from_slice(&inode.raw);
        self.write_block(block, &data)
    }

    fn group_of(&self, ino: u32) -> u32 {
        (ino - 1) / self.sb32(SB_INODES_PER_GROUP)
    }

    // ---- file block mapping: direct and indirect blocks ------------------

    /// Which disk block holds block number `index` of the file? 0 = a hole.
    /// With `alloc`, holes are filled with new zeroed blocks (and any
    /// missing indirect blocks on the way); the caller then writes `inode`
    /// back, since its block pointers and sector count changed.
    fn bmap(&mut self, inode: &mut DiskInode, index: u64, alloc: bool) -> Result<u32, Errno> {
        let p = (self.block_size / 4) as u64; // pointers per indirect block
        // Which of the 15 pointers, how many indirect levels below it, and
        // the index inside that tree.
        let (slot, levels, mut rest) = if index < 12 {
            (index as usize, 0, 0)
        } else if index - 12 < p {
            (12, 1, index - 12)
        } else if index - 12 - p < p * p {
            (13, 2, index - 12 - p)
        } else if index - 12 - p - p * p < p * p * p {
            (14, 3, index - 12 - p - p * p)
        } else {
            return Err(Errno::EFBIG);
        };
        let goal = self.group_of(inode.ino);
        let sectors_per_block = (self.block_size / SECTOR_SIZE) as i64;
        let mut block = inode.block(slot);
        if block == 0 {
            if !alloc {
                return Ok(0);
            }
            block = self.alloc_block(goal)?;
            inode.set_block(slot, block);
            inode.add_sectors(sectors_per_block);
        }
        // Walk down the indirect blocks: at each level, pick the pointer for
        // our part of the tree (like digits of `rest` in base p).
        for level in (0..levels).rev() {
            let span = p.pow(level);
            let i = (rest / span) as usize;
            rest %= span;
            let mut table = self.read_block(block)?;
            let mut next = get32(&table, 4 * i);
            if next == 0 {
                if !alloc {
                    return Ok(0);
                }
                next = self.alloc_block(goal)?;
                put32(&mut table, 4 * i, next);
                self.write_block(block, &table)?;
                inode.add_sectors(sectors_per_block);
            }
            block = next;
        }
        Ok(block)
    }

    /// Free a block and, for indirect blocks (`levels` > 0), everything it
    /// points to.
    fn free_tree(&mut self, block: u32, levels: u32) -> Result<(), Errno> {
        if levels > 0 {
            let table = self.read_block(block)?;
            for i in 0..self.block_size / 4 {
                let next = get32(&table, 4 * i);
                if next != 0 {
                    self.free_tree(next, levels - 1)?;
                }
            }
        }
        self.free_block(block)
    }

    /// Free all of a file's data blocks: size 0, no blocks (truncate).
    fn free_data(&mut self, inode: &mut DiskInode) -> Result<(), Errno> {
        if !self.is_fast_symlink(inode) {
            for slot in 0..15 {
                let block = inode.block(slot);
                if block != 0 {
                    let levels = slot.saturating_sub(11) as u32; // 12 -> 1, 13 -> 2, 14 -> 3
                    self.free_tree(block, levels)?;
                    inode.set_block(slot, 0);
                }
            }
            // What's left in i_blocks is the extended attribute block, if any.
            let ea = if inode.file_acl() != 0 { self.block_size / SECTOR_SIZE } else { 0 };
            put32(&mut inode.raw, I_SECTORS, ea as u32);
        }
        inode.set_size(0);
        Ok(())
    }

    /// A symlink whose target is stored inside i_block (no data blocks).
    fn is_fast_symlink(&self, inode: &DiskInode) -> bool {
        let ea = if inode.file_acl() != 0 { (self.block_size / SECTOR_SIZE) as u32 } else { 0 };
        inode.kind() == InodeKind::Symlink && inode.sectors() == ea
    }

    // ---- file contents ---------------------------------------------------

    fn read_file(&mut self, inode: &DiskInode, offset: u64, buf: &mut [u8]) -> Result<usize, Errno> {
        let size = inode.size();
        if offset >= size {
            return Ok(0);
        }
        let len = buf.len().min((size - offset) as usize);
        let bs = self.block_size as u64;
        let mut inode = inode.clone(); // bmap wants &mut (it won't change it without alloc)
        let mut done = 0;
        while done < len {
            let pos = offset + done as u64;
            let within = (pos % bs) as usize;
            let n = (self.block_size - within).min(len - done);
            match self.bmap(&mut inode, pos / bs, false)? {
                0 => buf[done..done + n].fill(0), // a hole
                block => buf[done..done + n].copy_from_slice(&self.read_block(block)?[within..within + n]),
            }
            done += n;
        }
        Ok(done)
    }

    fn write_file(&mut self, inode: &mut DiskInode, offset: u64, buf: &[u8]) -> Result<usize, Errno> {
        let end = offset.checked_add(buf.len() as u64).ok_or(Errno::EFBIG)?;
        if end > MAX_WRITE_SIZE {
            return Err(Errno::EFBIG);
        }
        let bs = self.block_size as u64;
        let mut done = 0;
        let mut result = Ok(());
        while done < buf.len() {
            let pos = offset + done as u64;
            let within = (pos % bs) as usize;
            let n = (self.block_size - within).min(buf.len() - done);
            let step = (|| {
                let block = self.bmap(inode, pos / bs, true)?;
                // A whole block is simply overwritten; part of one is
                // read-modify-write.
                let mut data = if n == self.block_size { vec![0u8; n] } else { self.read_block(block)? };
                data[within..within + n].copy_from_slice(&buf[done..done + n]);
                self.write_block(block, &data)
            })();
            if let Err(e) = step {
                result = Err(e); // e.g. ENOSPC: keep what was written so far
                break;
            }
            done += n;
        }
        // Always save the inode: bmap may have allocated blocks even if a
        // later step failed.
        let new_end = offset + done as u64;
        if new_end > inode.size() {
            inode.set_size(new_end);
        }
        let now = self.now();
        inode.set_times(&[I_MTIME, I_CTIME], now);
        self.write_inode(inode)?;
        match result {
            Err(e) if done == 0 => Err(e),
            _ => Ok(done),
        }
    }

    // ---- directories -----------------------------------------------------

    /// Parse the entry at `at` in a directory block: (inode, rec_len, name_len, type).
    fn parse_entry(&self, data: &[u8], at: usize) -> Result<(u32, usize, usize, u8), Errno> {
        let rec_len = get16(data, at + 4) as usize;
        let (name_len, file_type) =
            if self.filetype { (data[at + 6] as usize, data[at + 7]) } else { (get16(data, at + 6) as usize, 0) };
        if rec_len < 8 || rec_len % 4 != 0 || at + rec_len > data.len() || 8 + name_len > rec_len {
            return Err(Errno::EIO); // corrupted directory
        }
        Ok((get32(data, at), rec_len, name_len, file_type))
    }

    fn write_entry(&self, data: &mut [u8], at: usize, ino: u32, rec_len: usize, name: &str, file_type: u8) {
        put32(data, at, ino);
        put16(data, at + 4, rec_len as u16);
        if self.filetype {
            data[at + 6] = name.len() as u8;
            data[at + 7] = file_type;
        } else {
            put16(data, at + 6, name.len() as u16);
        }
        data[at + 8..at + 8 + name.len()].copy_from_slice(name.as_bytes());
    }

    fn dir_blocks(&self, dir: &DiskInode) -> u64 {
        dir.size().div_ceil(self.block_size as u64)
    }

    /// All entries of a directory, "." and ".." included.
    fn read_dir(&mut self, dir: &DiskInode) -> Result<Vec<RawDirEntry>, Errno> {
        let mut out = Vec::new();
        let mut dir = dir.clone();
        for index in 0..self.dir_blocks(&dir) {
            let block = self.bmap(&mut dir, index, false)?;
            if block == 0 {
                continue;
            }
            let data = self.read_block(block)?;
            let mut at = 0;
            while at < data.len() {
                let (ino, rec_len, name_len, file_type) = self.parse_entry(&data, at)?;
                if ino != 0 {
                    let name = String::from_utf8_lossy(&data[at + 8..at + 8 + name_len]).into_owned();
                    out.push(RawDirEntry { ino, name, file_type });
                }
                at += rec_len;
            }
        }
        Ok(out)
    }

    fn find_entry(&mut self, dir: &DiskInode, name: &str) -> Result<Option<u32>, Errno> {
        Ok(self.read_dir(dir)?.into_iter().find(|e| e.name == name).map(|e| e.ino))
    }

    /// We don't keep the htree hash index of big directories up to date,
    /// so mark it gone when changing a directory (like Linux's ext2 does).
    fn drop_index(dir: &mut DiskInode) {
        let flags = get32(&dir.raw, I_FLAGS);
        put32(&mut dir.raw, I_FLAGS, flags & !INDEX_FL);
    }

    /// Add `name -> ino` to a directory: in the slack space after an
    /// existing entry if there is room, else in a new block at the end.
    fn add_entry(&mut self, dir: &mut DiskInode, name: &str, ino: u32, file_type: u8) -> Result<(), Errno> {
        let need = entry_size(name.len());
        Self::drop_index(dir);
        for index in 0..self.dir_blocks(dir) {
            let block = self.bmap(dir, index, false)?;
            if block == 0 {
                continue;
            }
            let mut data = self.read_block(block)?;
            let mut at = 0;
            while at < data.len() {
                let (e_ino, rec_len, name_len, _) = self.parse_entry(&data, at)?;
                let used = if e_ino == 0 { 0 } else { entry_size(name_len) };
                if rec_len - used >= need {
                    if e_ino == 0 {
                        // An unused entry (start of a block): take it over.
                        self.write_entry(&mut data, at, ino, rec_len, name, file_type);
                    } else {
                        // Shrink this entry to its real size; we get the rest.
                        put16(&mut data, at + 4, used as u16);
                        self.write_entry(&mut data, at + used, ino, rec_len - used, name, file_type);
                    }
                    self.write_block(block, &data)?;
                    return self.write_inode(dir);
                }
                at += rec_len;
            }
        }
        // No room anywhere: grow the directory by one block.
        let index = self.dir_blocks(dir);
        let block = self.bmap(dir, index, true)?;
        let mut data = vec![0u8; self.block_size];
        self.write_entry(&mut data, 0, ino, self.block_size, name, file_type);
        self.write_block(block, &data)?;
        dir.set_size((index + 1) * self.block_size as u64);
        self.write_inode(dir)
    }

    /// Remove `name` from a directory; returns its inode number. The entry
    /// is merged into the previous one (or, first in its block, marked
    /// unused with inode 0).
    fn remove_entry(&mut self, dir: &mut DiskInode, name: &str) -> Result<u32, Errno> {
        Self::drop_index(dir);
        for index in 0..self.dir_blocks(dir) {
            let block = self.bmap(dir, index, false)?;
            if block == 0 {
                continue;
            }
            let mut data = self.read_block(block)?;
            let (mut at, mut prev) = (0, None);
            while at < data.len() {
                let (e_ino, rec_len, name_len, _) = self.parse_entry(&data, at)?;
                if e_ino != 0 && &data[at + 8..at + 8 + name_len] == name.as_bytes() {
                    match prev {
                        Some(p) => {
                            let merged = get16(&data, p + 4) as usize + rec_len;
                            put16(&mut data, p + 4, merged as u16);
                        }
                        None => put32(&mut data, at, 0),
                    }
                    self.write_block(block, &data)?;
                    self.write_inode(dir)?;
                    return Ok(e_ino);
                }
                prev = Some(at);
                at += rec_len;
            }
        }
        Err(Errno::ENOENT)
    }

    // ---- the operations the VFS uses -------------------------------------

    fn create(&mut self, parent_ino: u32, name: &str, kind: InodeKind) -> Result<u32, Errno> {
        if !self.writable {
            return Err(Errno::EROFS);
        }
        if name.is_empty() || name == "." || name == ".." || name.contains('/') {
            return Err(Errno::EINVAL);
        }
        if name.len() > 255 {
            return Err(Errno::ENAMETOOLONG);
        }
        let mut parent = self.read_inode(parent_ino)?;
        if parent.kind() != InodeKind::Directory {
            return Err(Errno::ENOTDIR);
        }
        if self.find_entry(&parent, name)?.is_some() {
            return Err(Errno::EEXIST);
        }
        let dir = match kind {
            InodeKind::File => false,
            InodeKind::Directory => true,
            InodeKind::Symlink | InodeKind::Device => return Err(Errno::EOPNOTSUPP), // no symlink/mknod syscall yet
        };
        let mut inode = self.alloc_inode(self.group_of(parent_ino), dir)?;
        let now = self.now();
        inode.set_times(&[I_ATIME, I_CTIME, I_MTIME], now);
        if dir {
            put16(&mut inode.raw, I_MODE, S_IFDIR | 0o755);
            inode.set_links(2); // the parent's entry + its own "."
        } else {
            put16(&mut inode.raw, I_MODE, S_IFREG | 0o644);
            inode.set_links(1);
        }
        let result = (|| {
            if dir {
                // A new directory holds "." and ".." (which takes the rest of the block).
                let block = self.bmap(&mut inode, 0, true)?;
                let mut data = vec![0u8; self.block_size];
                self.write_entry(&mut data, 0, inode.ino, 12, ".", FT_DIR);
                self.write_entry(&mut data, 12, parent_ino, self.block_size - 12, "..", FT_DIR);
                self.write_block(block, &data)?;
                inode.set_size(self.block_size as u64);
            }
            self.write_inode(&inode)?;
            self.add_entry(&mut parent, name, inode.ino, if dir { FT_DIR } else { FT_REG })?;
            if dir {
                parent.set_links(parent.links() + 1); // the new ".." points at it
                self.write_inode(&parent)?;
            }
            Ok(())
        })();
        if let Err(e) = result {
            // Undo (e.g. the parent directory couldn't grow: ENOSPC).
            let _ = self.free_data(&mut inode);
            let _ = self.free_inode(inode.ino, dir);
            return Err(e);
        }
        Ok(inode.ino)
    }

    fn remove(&mut self, parent_ino: u32, name: &str) -> Result<(), Errno> {
        if !self.writable {
            return Err(Errno::EROFS);
        }
        let mut parent = self.read_inode(parent_ino)?;
        let ino = self.find_entry(&parent, name)?.ok_or(Errno::ENOENT)?;
        let mut child = self.read_inode(ino)?;
        let is_dir = child.kind() == InodeKind::Directory;
        if is_dir && self.read_dir(&child)?.iter().any(|e| e.name != "." && e.name != "..") {
            return Err(Errno::ENOTEMPTY);
        }
        let last_link = is_dir || child.links() <= 1;
        if last_link && child.file_acl() != 0 {
            return Err(Errno::EOPNOTSUPP); // we don't do extended attribute blocks
        }
        self.remove_entry(&mut parent, name)?;
        if is_dir {
            parent.set_links(parent.links() - 1); // its ".." is gone
            self.write_inode(&parent)?;
        }
        if !last_link {
            child.set_links(child.links() - 1); // another hard link remains
            return self.write_inode(&child);
        }
        // Last link gone: free the data, mark the inode deleted, free it.
        self.free_data(&mut child)?;
        child.set_links(0);
        let now = self.now();
        child.set_times(&[I_DTIME, I_CTIME], now);
        self.write_inode(&child)?;
        self.free_inode(ino, is_dir)
    }

    /// Checks every new name goes through: writable, a valid name, the
    /// parent a directory without that name yet. Returns the parent.
    fn check_new_entry(&mut self, parent_ino: u32, name: &str) -> Result<DiskInode, Errno> {
        if !self.writable {
            return Err(Errno::EROFS);
        }
        if name.is_empty() || name == "." || name == ".." || name.contains('/') {
            return Err(Errno::EINVAL);
        }
        if name.len() > 255 {
            return Err(Errno::ENAMETOOLONG);
        }
        let parent = self.read_inode(parent_ino)?;
        if parent.kind() != InodeKind::Directory {
            return Err(Errno::ENOTDIR);
        }
        if self.find_entry(&parent, name)?.is_some() {
            return Err(Errno::EEXIST);
        }
        Ok(parent)
    }

    /// symlink (stage 17). Like Linux, a target of up to 60 bytes is a
    /// "fast" symlink: stored in the inode's block pointers themselves, no
    /// data block. Longer targets (up to one block) get a data block.
    fn symlink(&mut self, parent_ino: u32, name: &str, target: &str) -> Result<u32, Errno> {
        let mut parent = self.check_new_entry(parent_ino, name)?;
        if target.len() > self.block_size.min(4095) {
            return Err(Errno::ENAMETOOLONG);
        }
        let mut inode = self.alloc_inode(self.group_of(parent_ino), false)?;
        let now = self.now();
        inode.set_times(&[I_ATIME, I_CTIME, I_MTIME], now);
        put16(&mut inode.raw, I_MODE, S_IFLNK | 0o777);
        inode.set_links(1);
        let result = (|| {
            if target.len() <= 60 {
                inode.raw[I_BLOCK..I_BLOCK + target.len()].copy_from_slice(target.as_bytes());
                inode.set_size(target.len() as u64);
                self.write_inode(&inode)?;
            } else {
                self.write_file(&mut inode, 0, target.as_bytes())?; // (writes the inode)
            }
            self.add_entry(&mut parent, name, inode.ino, FT_SYMLINK)
        })();
        if let Err(e) = result {
            if target.len() > 60 {
                let _ = self.free_data(&mut inode);
            }
            let _ = self.free_inode(inode.ino, false);
            return Err(e);
        }
        Ok(inode.ino)
    }

    /// Hard link (stage 17): one more entry for inode `ino`, one more in
    /// its link count.
    fn link(&mut self, parent_ino: u32, name: &str, ino: u32) -> Result<(), Errno> {
        let mut parent = self.check_new_entry(parent_ino, name)?;
        let mut child = self.read_inode(ino)?;
        if child.kind() == InodeKind::Directory {
            return Err(Errno::EPERM);
        }
        if child.links() >= 32000 {
            return Err(Errno::EMLINK); // Linux's EXT2_LINK_MAX
        }
        self.add_entry(&mut parent, name, ino, child.file_type())?;
        child.set_links(child.links() + 1);
        let now = self.now();
        child.set_times(&[I_CTIME], now);
        self.write_inode(&child)
    }

    /// rename (stage 17): add the new entry, drop the old one. A replaced
    /// file loses a link (and is freed if that was its last); a moved
    /// directory gets its ".." pointed at the new parent. The VFS checked
    /// the kinds and that a replaced directory is empty.
    fn rename(&mut self, old_parent: u32, old: &str, new_parent: u32, new: &str) -> Result<(), Errno> {
        if !self.writable {
            return Err(Errno::EROFS);
        }
        if new.is_empty() || new == "." || new == ".." || new.contains('/') {
            return Err(Errno::EINVAL);
        }
        if new.len() > 255 {
            return Err(Errno::ENAMETOOLONG);
        }
        let dir = self.read_inode(old_parent)?;
        let ino = self.find_entry(&dir, old)?.ok_or(Errno::ENOENT)?;
        let mut child = self.read_inode(ino)?;
        let is_dir = child.kind() == InodeKind::Directory;
        let target_dir = self.read_inode(new_parent)?;
        if let Some(existing) = self.find_entry(&target_dir, new)? {
            if existing == ino {
                return Ok(());
            }
            self.remove(new_parent, new)?;
        }
        let mut target_dir = self.read_inode(new_parent)?;
        self.add_entry(&mut target_dir, new, ino, child.file_type())?;
        let mut dir = self.read_inode(old_parent)?;
        self.remove_entry(&mut dir, old)?;
        if is_dir && old_parent != new_parent {
            self.set_dotdot(&mut child, new_parent)?;
            let mut from = self.read_inode(old_parent)?;
            from.set_links(from.links() - 1);
            self.write_inode(&from)?;
            let mut to = self.read_inode(new_parent)?;
            to.set_links(to.links() + 1);
            self.write_inode(&to)?;
        }
        let now = self.now();
        child.set_times(&[I_CTIME], now);
        self.write_inode(&child)
    }

    /// Point a directory's ".." entry at `parent`.
    fn set_dotdot(&mut self, dir: &mut DiskInode, parent: u32) -> Result<(), Errno> {
        let block = self.bmap(dir, 0, false)?;
        if block == 0 {
            return Err(Errno::EIO);
        }
        let mut data = self.read_block(block)?;
        let mut at = 0;
        while at < data.len() {
            let (e_ino, rec_len, name_len, _) = self.parse_entry(&data, at)?;
            if e_ino != 0 && &data[at + 8..at + 8 + name_len] == b".." {
                put32(&mut data, at, parent);
                return self.write_block(block, &data);
            }
            at += rec_len;
        }
        Err(Errno::EIO) // a directory without ".."
    }

    fn truncate(&mut self, ino: u32) -> Result<(), Errno> {
        if !self.writable {
            return Err(Errno::EROFS);
        }
        let mut inode = self.read_inode(ino)?;
        self.free_data(&mut inode)?;
        let now = self.now();
        inode.set_times(&[I_MTIME, I_CTIME], now);
        self.write_inode(&inode)
    }

    fn readlink(&mut self, inode: &DiskInode) -> Result<String, Errno> {
        let size = inode.size() as usize;
        let bytes = if self.is_fast_symlink(inode) {
            inode.raw[I_BLOCK..I_BLOCK + size.min(60)].to_vec() // stored in i_block itself
        } else {
            let mut buf = vec![0u8; size];
            let n = self.read_file(inode, 0, &mut buf)?;
            buf.truncate(n);
            buf
        };
        String::from_utf8(bytes).map_err(|_| Errno::EINVAL)
    }

    fn label(&self) -> String {
        let raw = &self.sb[SB_VOLUME_NAME..SB_VOLUME_NAME + 16];
        let len = raw.iter().position(|&b| b == 0).unwrap_or(16);
        String::from_utf8_lossy(&raw[..len]).into_owned()
    }
}

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

/// A mounted ext2 volume.
pub struct Ext2Fs {
    vol: Arc<Mutex<Volume>>,
}

impl Ext2Fs {
    pub fn mount(dev: Arc<dyn BlockDevice>) -> Result<Arc<Ext2Fs>, Errno> {
        let vol = Volume::open(dev)?;
        let root = vol.read_inode(ROOT_INO)?;
        if root.kind() != InodeKind::Directory {
            return Err(Errno::EIO);
        }
        Ok(Arc::new(Ext2Fs { vol: Arc::new(Mutex::new(vol)) }))
    }

    /// For the boot log, e.g. `ext2 volume "RUSTBELT" (rev 1, 1 KiB blocks, 4 groups)`.
    pub fn describe(&self) -> String {
        let v = self.vol.lock();
        format!(
            "ext2 volume \"{}\" (rev {}, {} KiB blocks, {} groups{})",
            v.label(),
            v.revision,
            v.block_size / 1024,
            v.groups,
            if v.writable { "" } else { ", read-only" }
        )
    }

    /// (free blocks, total blocks, free inodes, total inodes), from the superblock.
    pub fn counts(&self) -> (u32, u32, u32, u32) {
        let v = self.vol.lock();
        (v.sb32(SB_FREE_BLOCKS), v.sb32(SB_BLOCKS_COUNT), v.sb32(SB_FREE_INODES), v.sb32(SB_INODES_COUNT))
    }
}

impl FileSystem for Ext2Fs {
    fn name(&self) -> &'static str {
        "ext2"
    }
    fn root(&self) -> Arc<dyn Inode> {
        Arc::new(Ext2Inode { vol: self.vol.clone(), ino: ROOT_INO, kind: InodeKind::Directory })
    }
    fn statfs(&self) -> super::StatFs {
        let v = self.vol.lock();
        let free = v.sb32(SB_FREE_BLOCKS) as u64;
        super::StatFs {
            magic: super::EXT2_MAGIC,
            block_size: v.block_size as u64,
            blocks: v.sb32(SB_BLOCKS_COUNT) as u64,
            free_blocks: free,
            avail_blocks: free.saturating_sub(v.sb32(SB_R_BLOCKS) as u64),
            files: v.sb32(SB_INODES_COUNT) as u64,
            free_files: v.sb32(SB_FREE_INODES) as u64,
            name_max: 255,
            read_only: !v.writable,
        }
    }
}

/// A file, directory or symlink on an ext2 volume: just its inode number.
/// Every operation reads the on-disk inode fresh.
pub struct Ext2Inode {
    vol: Arc<Mutex<Volume>>,
    ino: u32,
    kind: InodeKind,
}

impl Ext2Inode {
    fn child(&self, ino: u32, kind: InodeKind) -> Arc<dyn Inode> {
        Arc::new(Ext2Inode { vol: self.vol.clone(), ino, kind })
    }
    fn dir_only(&self) -> Result<(), Errno> {
        if self.kind == InodeKind::Directory { Ok(()) } else { Err(Errno::ENOTDIR) }
    }
}

impl Inode for Ext2Inode {
    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);
        }
        let vol = self.vol.lock();
        vol.read_inode(self.ino).map(|i| i.size() as usize).unwrap_or(0)
    }

    fn mode(&self) -> u32 {
        let vol = self.vol.lock();
        // (chmod 000 is a real mode here: MODE_SET says so.)
        vol.read_inode(self.ino).map(|i| (i.mode() & 0o7777) as u32 | super::MODE_SET * (i.mode() & 0o7777 == 0) as u32).unwrap_or(0)
    }

    /// chmod: the low 12 bits of i_mode (the type bits above stay).
    fn set_mode(&self, mode: u32) -> Result<(), Errno> {
        let vol = self.vol.lock();
        if !vol.writable {
            return Err(Errno::EROFS);
        }
        let mut inode = vol.read_inode(self.ino)?;
        let new = (inode.mode() & !0o7777) | (mode & 0o7777) as u16;
        put16(&mut inode.raw, I_MODE, new);
        inode.set_times(&[I_CTIME], super::now_timespec()[0] as u32);
        vol.write_inode(&inode)
    }

    /// ext2 keeps whole seconds (32-bit: until 2106).
    fn times(&self) -> Option<[[i64; 2]; 3]> {
        let vol = self.vol.lock();
        let inode = vol.read_inode(self.ino).ok()?;
        let t = |at| [get32(&inode.raw, at) as i64, 0];
        Some([t(I_ATIME), t(I_MTIME), t(I_CTIME)])
    }

    fn set_times(&self, atime: Option<[i64; 2]>, mtime: Option<[i64; 2]>) -> Result<(), Errno> {
        let vol = self.vol.lock();
        if !vol.writable {
            return Err(Errno::EROFS);
        }
        let mut inode = vol.read_inode(self.ino)?;
        let secs = |t: [i64; 2]| t[0].clamp(0, u32::MAX as i64) as u32;
        if let Some(t) = atime {
            inode.set_times(&[I_ATIME], secs(t));
        }
        if let Some(t) = mtime {
            inode.set_times(&[I_MTIME], secs(t));
        }
        inode.set_times(&[I_CTIME], super::now_timespec()[0] as u32);
        vol.write_inode(&inode)
    }

    fn readlink(&self) -> Result<String, Errno> {
        if self.kind != InodeKind::Symlink {
            return Err(Errno::EINVAL);
        }
        let mut vol = self.vol.lock();
        let inode = vol.read_inode(self.ino)?;
        vol.readlink(&inode)
    }

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

    fn write_at(&self, offset: usize, buf: &[u8]) -> Result<usize, Errno> {
        if self.kind == InodeKind::Directory {
            return Err(Errno::EISDIR);
        }
        let mut vol = self.vol.lock();
        if !vol.writable {
            return Err(Errno::EROFS);
        }
        let mut inode = vol.read_inode(self.ino)?;
        vol.write_file(&mut inode, offset as u64, buf)
    }

    fn truncate(&self) -> Result<(), Errno> {
        if self.kind == InodeKind::Directory {
            return Err(Errno::EISDIR);
        }
        self.vol.lock().truncate(self.ino)
    }

    fn lookup(&self, name: &str) -> Result<Arc<dyn Inode>, Errno> {
        self.dir_only()?;
        let mut vol = self.vol.lock();
        let dir = vol.read_inode(self.ino)?;
        let ino = vol.find_entry(&dir, name)?.ok_or(Errno::ENOENT)?;
        let kind = vol.read_inode(ino)?.kind();
        Ok(self.child(ino, kind))
    }

    fn create(&self, name: &str, kind: InodeKind) -> Result<Arc<dyn Inode>, Errno> {
        self.dir_only()?;
        let ino = self.vol.lock().create(self.ino, name, kind)?;
        Ok(self.child(ino, kind))
    }

    fn list(&self) -> Result<Vec<DirEntry>, Errno> {
        self.dir_only()?;
        let mut vol = self.vol.lock();
        let dir = vol.read_inode(self.ino)?;
        let mut out = Vec::new();
        for e in vol.read_dir(&dir)? {
            if e.name == "." || e.name == ".." {
                continue;
            }
            let kind = match e.file_type {
                1 => InodeKind::File,
                2 => InodeKind::Directory,
                7 => InodeKind::Symlink,
                _ => vol.read_inode(e.ino)?.kind(), // revision 0: no type in the entry
            };
            out.push(DirEntry { name: e.name, kind, ino: e.ino as u64 });
        }
        Ok(out)
    }

    fn remove(&self, name: &str) -> Result<(), Errno> {
        self.dir_only()?;
        self.vol.lock().remove(self.ino, name)
    }

    // --- stage 17 ----------------------------------------------------------

    fn ino(&self) -> Option<u64> {
        Some(self.ino as u64)
    }

    fn nlink(&self) -> Option<u64> {
        self.vol.lock().read_inode(self.ino).ok().map(|i| i.links() as u64)
    }

    fn owner(&self) -> (u32, u32) {
        self.vol.lock().read_inode(self.ino).map(|i| i.owner()).unwrap_or((0, 0))
    }

    fn set_owner(&self, uid: Option<u32>, gid: Option<u32>) -> Result<(), Errno> {
        let vol = self.vol.lock();
        if !vol.writable {
            return Err(Errno::EROFS);
        }
        let mut inode = vol.read_inode(self.ino)?;
        inode.set_owner(uid, gid);
        inode.set_times(&[I_CTIME], vol.now());
        vol.write_inode(&inode)
    }

    fn symlink(&self, name: &str, target: &str) -> Result<Arc<dyn Inode>, Errno> {
        self.dir_only()?;
        let ino = self.vol.lock().symlink(self.ino, name, target)?;
        Ok(self.child(ino, InodeKind::Symlink))
    }

    fn link(&self, name: &str, target: &Arc<dyn Inode>) -> Result<(), Errno> {
        self.dir_only()?;
        let other = super::downcast::<Ext2Inode>(target).filter(|o| Arc::ptr_eq(&o.vol, &self.vol)).ok_or(Errno::EXDEV)?;
        self.vol.lock().link(self.ino, name, other.ino)
    }

    fn rename_entry(&self, old: &str, new_dir: &Arc<dyn Inode>, new: &str) -> Result<(), Errno> {
        self.dir_only()?;
        let other = super::downcast::<Ext2Inode>(new_dir).filter(|o| Arc::ptr_eq(&o.vol, &self.vol)).ok_or(Errno::EXDEV)?;
        self.vol.lock().rename(self.ino, old, other.ino, new)
    }

    fn as_any(self: Arc<Self>) -> Option<Arc<dyn core::any::Any + Send + Sync>> {
        Some(self)
    }
}