rust-kernel

//! exFAT, Microsoft's "extended FAT" (2006): the file system on SD cards
//! over 32 GB and most USB sticks, made for flash. Written by hand from
//! Microsoft's published specification, no crate.
//!
//! # On-disk layout
//!
//! ```text
//! sector 0       1..8           9..10  11        12..23        FatOffset   ClusterHeapOffset
//! | boot sector | extended boot | OEM | checksum | backup copy | ... | FAT | ... | cluster heap ... |
//! ```
//!
//! * **Boot sector** (sector 0): "EXFAT   " at byte 3, then the geometry,
//!   all in sectors (whose size is `1 << BytesPerSectorShift`, 512-4096):
//!   where the FAT and the cluster heap start, how many clusters there are,
//!   the first cluster of the root directory, and the cluster size
//!   (`1 << SectorsPerClusterShift` sectors). Byte 112 is **PercentInUse**.
//! * **Boot checksum** (sector 11): sectors 0-10 summed with a "rotate right
//!   and add" checksum, skipping the three bytes that change while the
//!   volume is in use (VolumeFlags, PercentInUse). Sector 11 holds that
//!   32-bit value over and over. Sectors 12-23 are a backup of 0-11.
//! * **FAT**: one 32-bit entry per cluster, like FAT32: the number of the
//!   next cluster of a file, 0xFFFFFFFF at the end of a chain, 0xFFFFFFF7
//!   for a bad cluster. Clusters are numbered from 2.
//! * **Cluster heap**: cluster N starts at `ClusterHeapOffset + (N - 2) *
//!   cluster size`. Everything else lives here, *including* the system
//!   files that FAT32 kept in fixed places:
//!   - the **allocation bitmap**: 1 bit per cluster, 1 = in use. Unlike
//!     FAT32, a free FAT entry doesn't mean a free cluster: only the bitmap
//!     says what's free.
//!   - the **up-case table**: for each UTF-16 character, its upper-case
//!     form. Names are compared without case, and the table says exactly
//!     what "without case" means, so every implementation agrees. It's
//!     stored compressed: `0xFFFF, n` means "the next n characters map to
//!     themselves".
//!   - the **root directory**.
//!
//! # Directories and entry sets
//!
//! A directory is a file of 32-byte entries. Byte 0 is the type; bit 7 of
//! it means "in use", so deleting an entry just clears that bit, and type
//! 0x00 marks the end of the directory. The root directory holds the
//! special entries: volume label (0x83), allocation bitmap (0x81) and up-case
//! table (0x82). Each file is an **entry set** of 3 to 19 entries:
//!
//! ```text
//! 0x85 File            secondary count, SetChecksum, attributes, times
//! 0xC0 Stream Ext.     flags, name length, name hash, ValidDataLength,
//!                      first cluster, DataLength
//! 0xC1 File Name       15 UTF-16 characters  (as many as the name needs)
//! ```
//!
//! * **SetChecksum** (16 bits, "rotate right and add") covers every byte of
//!   the set except itself, so changing a size means recomputing it.
//! * **NameHash** is the same checksum over the up-cased name, to skip
//!   most non-matching names quickly.
//! * **NoFatChain**: a flag in the stream entry saying "my clusters are
//!   consecutive; don't look at the FAT". Most files are contiguous, so
//!   most files never touch the FAT at all. If a file can't grow in place,
//!   we write out its FAT chain and clear the flag.
//! * **ValidDataLength** <= DataLength: bytes past it read as zeros
//!   (Windows uses this to make big files quickly). We always write the
//!   two equal.
//! * Directories have no "." or "..", and their size is whole clusters.
//!   The root has no entry set at all, so its size comes from its FAT chain.
//!
//! # What we do
//!
//! * Read and write: create, write and append, truncate to 0, mkdir,
//!   unlink and rmdir. We keep the bitmap, FAT chains, SetChecksums and
//!   PercentInUse right, so the host's `fsck.exfat` finds a clean volume.
//! * Lookup is case-insensitive using the volume's own up-case table.
//! * We check the boot checksum and the up-case table's checksum at mount.
//! * Not supported: rename, timestamps (we have no clock: everything is
//!   1 Jan 2026), TexFAT's second FAT (a volume with two FATs mounts
//!   read-only), and the VolumeDirty flag (we write straight through and
//!   never leave half-done work behind a lock).
//!
//! Like our ext2, there's no cache except the bitmap, which we keep in
//! memory (one bit per cluster: 960 bytes for our 32 MiB disk) and write
//! through. Inodes are just paths, resolved again on every call.

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 core::cell::RefCell;
use spin::Mutex;

// Boot sector fields (byte offsets).
const BS_NAME: usize = 3; // "EXFAT   "
const BS_FAT_OFFSET: usize = 80; // in sectors
const BS_CLUSTER_HEAP_OFFSET: usize = 88; // in sectors
const BS_CLUSTER_COUNT: usize = 92;
const BS_ROOT_CLUSTER: usize = 96;
const BS_REVISION: usize = 104; // minor, major
const BS_VOLUME_FLAGS: usize = 106; // not in the checksum
const BS_SECTOR_SHIFT: usize = 108;
const BS_CLUSTER_SHIFT: usize = 109;
const BS_NUMBER_OF_FATS: usize = 110;
const BS_PERCENT_IN_USE: usize = 112; // not in the checksum

// Directory entry types (byte 0). Bit 7 = in use.
const ENTRY_END: u8 = 0x00;
const ENTRY_IN_USE: u8 = 0x80;
const ENTRY_BITMAP: u8 = 0x81;
const ENTRY_UPCASE: u8 = 0x82;
const ENTRY_LABEL: u8 = 0x83;
const ENTRY_FILE: u8 = 0x85;
const ENTRY_STREAM: u8 = 0xC0;
const ENTRY_NAME: u8 = 0xC1;
const ENTRY_SIZE: usize = 32;
const NAME_CHARS_PER_ENTRY: usize = 15;

// File entry fields.
const FILE_SECONDARY_COUNT: usize = 1;
const FILE_SET_CHECKSUM: usize = 2; // u16
const FILE_ATTRIBUTES: usize = 4; // u16
const FILE_TIMES: [usize; 3] = [8, 12, 16]; // created, modified, accessed
const ATTR_DIRECTORY: u16 = 0x10;
const ATTR_ARCHIVE: u16 = 0x20; // "changed since last backup": set on every new file
// Stream extension fields.
const STREAM_FLAGS: usize = 1;
const STREAM_NAME_LENGTH: usize = 3;
const STREAM_NAME_HASH: usize = 4; // u16
const STREAM_VALID_DATA_LENGTH: usize = 8; // u64
const STREAM_FIRST_CLUSTER: usize = 20; // u32 (also in bitmap/up-case entries)
const STREAM_DATA_LENGTH: usize = 24; // u64 (also in bitmap/up-case entries)
const FLAG_ALLOCATION_POSSIBLE: u8 = 0x01;
const FLAG_NO_FAT_CHAIN: u8 = 0x02;
// Up-case table entry: TableChecksum at byte 4.
const UPCASE_CHECKSUM: usize = 4;

const FAT_END: u32 = 0xFFFF_FFFF; // (0xFFFFFFF7, "bad", fails valid_cluster)
/// We have no clock: 2026-01-01 00:00:00 in exFAT's DOS-style format
/// (years since 1980 << 25 | month << 21 | day << 16 | h << 11 | m << 5 | s/2).
const TIMESTAMP: u32 = (46 << 25) | (1 << 21) | (1 << 16);

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())
}
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());
}
fn put64(b: &mut [u8], at: usize, v: u64) {
    b[at..at + 8].copy_from_slice(&v.to_le_bytes());
}

/// SetChecksum: rotate right by one bit, add the next byte. Bytes 2-3 (the
/// checksum itself) are skipped. NameHash uses the same 16-bit sum.
fn set_checksum(set: &[u8]) -> u16 {
    let mut sum: u16 = 0;
    for (i, &b) in set.iter().enumerate() {
        if i != FILE_SET_CHECKSUM && i != FILE_SET_CHECKSUM + 1 {
            sum = sum.rotate_right(1).wrapping_add(b as u16);
        }
    }
    sum
}

/// The 32-bit version, used for the boot region and the up-case table.
fn checksum32(sum: u32, bytes: &[u8]) -> u32 {
    bytes.iter().fold(sum, |s, &b| s.rotate_right(1).wrapping_add(b as u32))
}

/// Does `dev` hold an exFAT volume? Its boot sector says "EXFAT   " at byte 3.
pub fn probe(dev: &dyn BlockDevice) -> bool {
    let mut sector = [0u8; SECTOR_SIZE];
    dev.read_sectors(0, &mut sector).is_ok() && &sector[BS_NAME..BS_NAME + 8] == b"EXFAT   "
}

/// Where a file's clusters are. With `contiguous` (NoFatChain) they are
/// `first, first+1, ...`; otherwise follow the FAT from `first`. 0 = none.
#[derive(Clone, Copy)]
struct Chain {
    first: u32,
    contiguous: bool,
}

/// One file or directory found in a directory.
struct Found {
    /// Its parent directory's clusters, and the entry index of its File entry
    /// there: what we need to rewrite the entry set. None for the root.
    at: Option<(Vec<u32>, usize)>,
    attrs: u16,
    chain: Chain,
    size: u64,  // DataLength
    valid: u64, // ValidDataLength
}

impl Found {
    fn is_dir(&self) -> bool {
        self.attrs & ATTR_DIRECTORY != 0
    }
}

/// An entry set, parsed.
struct Set {
    index: usize, // entry index of the File entry in the directory
    name: Vec<u16>,
    attrs: u16,
    chain: Chain,
    size: u64,
    valid: u64,
}

struct Volume {
    dev: Arc<dyn BlockDevice>,
    writable: bool,
    cluster_size: usize,
    fat_offset: u64,  // bytes
    heap_offset: u64, // bytes
    cluster_count: u32,
    root_cluster: u32,
    /// The allocation bitmap, kept in memory, and where it lives on disk.
    bitmap: Vec<u8>,
    bitmap_clusters: Vec<u32>,
    used: u32,
    percent: u8,
    /// Where to start looking for a free cluster.
    hint: u32,
    /// Up-case table: only the characters that change, sorted.
    upcase: Vec<(u16, u16)>,
    label: String,
    /// The last FAT sector we read (device sector number, bytes), so that
    /// following a chain doesn't read the same sector 128 times. A RefCell
    /// because reading is `&self`; the Mutex around Volume serializes us.
    fat_cache: RefCell<Option<(u64, [u8; SECTOR_SIZE])>>,
}

impl Volume {
    fn open(dev: Arc<dyn BlockDevice>) -> Result<Volume, Errno> {
        let mut boot = vec![0u8; SECTOR_SIZE];
        dev.read_sectors(0, &mut boot)?;
        if &boot[BS_NAME..BS_NAME + 8] != b"EXFAT   " {
            return Err(Errno::EINVAL);
        }
        let sector_shift = boot[BS_SECTOR_SHIFT] as u32;
        let cluster_shift = boot[BS_CLUSTER_SHIFT] as u32;
        if !(9..=12).contains(&sector_shift) || sector_shift + cluster_shift > 25 || boot[BS_REVISION + 1] != 1 {
            return Err(Errno::EINVAL);
        }
        let sector = 1usize << sector_shift;

        // Boot checksum: sectors 0-10, skipping VolumeFlags and
        // PercentInUse, must match every u32 of sector 11.
        let mut region = vec![0u8; 12 * sector];
        dev.read_sectors(0, &mut region)?;
        let mut sum = 0;
        for (i, &b) in region[..11 * sector].iter().enumerate() {
            if i != BS_VOLUME_FLAGS && i != BS_VOLUME_FLAGS + 1 && i != BS_PERCENT_IN_USE {
                sum = checksum32(sum, &[b]);
            }
        }
        if region[11 * sector..].chunks(4).any(|c| get32(c, 0) != sum) {
            return Err(Errno::EIO);
        }

        let cluster_count = get32(&boot, BS_CLUSTER_COUNT);
        let mut vol = Volume {
            dev,
            // TexFAT's second FAT would need keeping in sync: read-only.
            writable: boot[BS_NUMBER_OF_FATS] == 1,
            cluster_size: sector << cluster_shift,
            fat_offset: get32(&boot, BS_FAT_OFFSET) as u64 * sector as u64,
            heap_offset: get32(&boot, BS_CLUSTER_HEAP_OFFSET) as u64 * sector as u64,
            cluster_count,
            root_cluster: get32(&boot, BS_ROOT_CLUSTER),
            bitmap: Vec::new(),
            bitmap_clusters: Vec::new(),
            used: 0,
            percent: boot[BS_PERCENT_IN_USE],
            hint: 2,
            upcase: Vec::new(),
            label: String::new(),
            fat_cache: RefCell::new(None),
        };
        if !vol.valid_cluster(vol.root_cluster) {
            return Err(Errno::EIO);
        }

        // The root directory has the label, bitmap and up-case entries.
        let root = vol.root()?;
        let clusters = vol.clusters(root.chain, root.size)?;
        let mut dir = vec![0u8; root.size as usize];
        vol.read_chain(&clusters, 0, &mut dir)?;
        let (mut bitmap, mut upcase) = (None, None);
        for e in dir.chunks(ENTRY_SIZE) {
            match e[0] {
                ENTRY_END => break,
                ENTRY_BITMAP if bitmap.is_none() => bitmap = Some((get32(e, STREAM_FIRST_CLUSTER), get64(e, STREAM_DATA_LENGTH))),
                ENTRY_UPCASE => upcase = Some((get32(e, STREAM_FIRST_CLUSTER), get64(e, STREAM_DATA_LENGTH), get32(e, UPCASE_CHECKSUM))),
                ENTRY_LABEL => {
                    let n = (e[1] as usize).min(11);
                    let units: Vec<u16> = (0..n).map(|i| get16(e, 2 + 2 * i)).collect();
                    vol.label = String::from_utf16_lossy(&units);
                }
                _ => {}
            }
        }
        let (Some((bm_first, bm_len)), Some((up_first, up_len, up_sum))) = (bitmap, upcase) else {
            return Err(Errno::EIO);
        };

        // The allocation bitmap: one bit per cluster.
        if bm_len < (cluster_count as u64).div_ceil(8) || bm_len > 1 << 29 {
            return Err(Errno::EIO);
        }
        let bm_clusters = vol.clusters(Chain { first: bm_first, contiguous: false }, bm_len)?;
        let mut bm = vec![0u8; bm_len as usize];
        vol.read_chain(&bm_clusters, 0, &mut bm)?;
        vol.bitmap_clusters = bm_clusters;
        vol.bitmap = bm;
        vol.used = (2..cluster_count + 2).filter(|&c| vol.is_used(c)).count() as u32;

        // The up-case table, checked against its checksum, then expanded.
        if up_len > 2 * 65536 * 2 {
            return Err(Errno::EIO);
        }
        let up_clusters = vol.clusters(Chain { first: up_first, contiguous: false }, up_len)?;
        let mut raw = vec![0u8; up_len as usize];
        vol.read_chain(&up_clusters, 0, &mut raw)?;
        if checksum32(0, &raw) != up_sum {
            return Err(Errno::EIO);
        }
        let mut ch: u32 = 0; // the character the next table slot is for
        let mut words = raw.chunks_exact(2).map(|c| get16(c, 0));
        while let Some(w) = words.next() {
            if w == 0xFFFF {
                ch += words.next().unwrap_or(0) as u32; // a run of "maps to itself"
            } else {
                if w as u32 != ch && ch <= 0xFFFF {
                    vol.upcase.push((ch as u16, w));
                }
                ch += 1;
            }
        }
        Ok(vol)
    }

    fn describe(&self) -> String {
        let size = if self.cluster_size >= 1024 { format!("{} KiB", self.cluster_size / 1024) } else { format!("{} byte", self.cluster_size) };
        format!(
            "exFAT volume \"{}\" ({} clusters, {} clusters{})",
            self.label,
            size,
            self.cluster_count,
            if self.writable { "" } else { ", read-only" }
        )
    }

    fn upcase(&self, c: u16) -> u16 {
        match self.upcase.binary_search_by_key(&c, |&(from, _)| from) {
            Ok(i) => self.upcase[i].1,
            Err(_) => c,
        }
    }

    fn same_name(&self, a: &[u16], b: &[u16]) -> bool {
        a.len() == b.len() && a.iter().zip(b).all(|(&x, &y)| self.upcase(x) == self.upcase(y))
    }

    // ---- bytes on the device -------------------------------------------

    /// Read `buf.len()` bytes at byte offset `pos` (any alignment).
    fn read_bytes(&self, pos: u64, buf: &mut [u8]) -> Result<(), Errno> {
        let skip = (pos % SECTOR_SIZE as u64) as usize;
        if skip == 0 && buf.len() % SECTOR_SIZE == 0 {
            return self.dev.read_sectors(pos / SECTOR_SIZE as u64, buf);
        }
        let mut tmp = vec![0u8; (skip + buf.len()).div_ceil(SECTOR_SIZE) * SECTOR_SIZE];
        self.dev.read_sectors(pos / SECTOR_SIZE as u64, &mut tmp)?;
        buf.copy_from_slice(&tmp[skip..skip + buf.len()]);
        Ok(())
    }

    /// Write `data` at byte offset `pos`: read-modify-write partial sectors.
    fn write_bytes(&self, pos: u64, data: &[u8]) -> Result<(), Errno> {
        let skip = (pos % SECTOR_SIZE as u64) as usize;
        if skip == 0 && data.len() % SECTOR_SIZE == 0 {
            return self.dev.write_sectors(pos / SECTOR_SIZE as u64, data);
        }
        let mut tmp = vec![0u8; (skip + data.len()).div_ceil(SECTOR_SIZE) * SECTOR_SIZE];
        self.dev.read_sectors(pos / SECTOR_SIZE as u64, &mut tmp)?;
        tmp[skip..skip + data.len()].copy_from_slice(data);
        self.dev.write_sectors(pos / SECTOR_SIZE as u64, &tmp)
    }

    fn cluster_pos(&self, cluster: u32) -> u64 {
        self.heap_offset + (cluster as u64 - 2) * self.cluster_size as u64
    }

    fn valid_cluster(&self, c: u32) -> bool {
        c >= 2 && c - 2 < self.cluster_count
    }

    // ---- FAT and bitmap --------------------------------------------------

    fn fat_get(&self, cluster: u32) -> Result<u32, Errno> {
        let pos = self.fat_offset + 4 * cluster as u64;
        let (lba, at) = (pos / SECTOR_SIZE as u64, (pos % SECTOR_SIZE as u64) as usize);
        let mut cache = self.fat_cache.borrow_mut();
        if cache.map(|(cached, _)| cached) != Some(lba) {
            let mut sector = [0u8; SECTOR_SIZE];
            self.dev.read_sectors(lba, &mut sector)?;
            *cache = Some((lba, sector));
        }
        Ok(get32(&cache.as_ref().unwrap().1, at))
    }

    fn fat_set(&self, cluster: u32, value: u32) -> Result<(), Errno> {
        let pos = self.fat_offset + 4 * cluster as u64;
        *self.fat_cache.borrow_mut() = None; // simplest way to keep it right
        self.write_bytes(pos, &value.to_le_bytes())
    }

    fn is_used(&self, cluster: u32) -> bool {
        let i = (cluster - 2) as usize;
        self.bitmap[i / 8] & (1 << (i % 8)) != 0
    }

    /// Flip one bitmap bit, in memory and on disk, and keep the counts.
    fn set_used(&mut self, cluster: u32, used: bool) -> Result<(), Errno> {
        let i = (cluster - 2) as usize;
        if used {
            self.bitmap[i / 8] |= 1 << (i % 8);
            self.used += 1;
        } else {
            self.bitmap[i / 8] &= !(1 << (i % 8));
            self.used -= 1;
        }
        let byte = i / 8;
        let on_disk = self.bitmap_clusters[byte / self.cluster_size];
        self.write_bytes(self.cluster_pos(on_disk) + (byte % self.cluster_size) as u64, &self.bitmap[byte..byte + 1])
    }

    /// Write PercentInUse (boot sector byte 112) if it changed. It's
    /// outside the boot checksum, so no other sector needs updating.
    fn update_percent(&mut self) -> Result<(), Errno> {
        let percent = (self.used as u64 * 100 / self.cluster_count as u64) as u8;
        if percent != self.percent {
            self.percent = percent;
            self.write_bytes(BS_PERCENT_IN_USE as u64, &[percent])?;
        }
        Ok(())
    }

    /// Take a free cluster, preferring `goal`, and fill it with zeros.
    fn alloc(&mut self, goal: u32) -> Result<u32, Errno> {
        let n = self.cluster_count;
        let start = if self.valid_cluster(goal) { goal - 2 } else { self.hint - 2 };
        let c = (0..n).map(|i| (start + i) % n + 2).find(|&c| !self.is_used(c)).ok_or(Errno::ENOSPC)?;
        self.set_used(c, true)?;
        self.hint = if c + 1 - 2 < n { c + 1 } else { 2 };
        self.write_bytes(self.cluster_pos(c), &vec![0u8; self.cluster_size])?;
        Ok(c)
    }

    // ---- chains ------------------------------------------------------------

    /// The clusters holding the first `size` bytes of a chain.
    fn clusters(&self, chain: Chain, size: u64) -> Result<Vec<u32>, Errno> {
        let n = size.div_ceil(self.cluster_size as u64);
        if n == 0 {
            return Ok(Vec::new());
        }
        if n > self.cluster_count as u64 || !self.valid_cluster(chain.first) {
            return Err(Errno::EIO);
        }
        if chain.contiguous {
            if chain.first as u64 - 2 + n > self.cluster_count as u64 {
                return Err(Errno::EIO);
            }
            return Ok((chain.first..chain.first + n as u32).collect());
        }
        let mut out = vec![chain.first];
        while (out.len() as u64) < n {
            let next = self.fat_get(*out.last().unwrap())?;
            if !self.valid_cluster(next) {
                return Err(Errno::EIO); // chain ends early, or is bad
            }
            out.push(next);
        }
        Ok(out)
    }

    /// The root directory: no entry set, so follow its FAT chain to the end.
    fn root(&self) -> Result<Found, Errno> {
        let mut n: u64 = 1;
        let mut c = self.root_cluster;
        loop {
            match self.fat_get(c)? {
                FAT_END => break,
                next if self.valid_cluster(next) && n < self.cluster_count as u64 => {
                    c = next;
                    n += 1;
                }
                _ => return Err(Errno::EIO), // free, bad, or a loop
            }
        }
        let size = n * self.cluster_size as u64;
        let chain = Chain { first: self.root_cluster, contiguous: false };
        Ok(Found { at: None, attrs: ATTR_DIRECTORY, chain, size, valid: size })
    }

    /// Copy bytes from offset `pos` of the data in `clusters` (merging
    /// consecutive clusters into one device read).
    fn read_chain(&self, clusters: &[u32], pos: u64, buf: &mut [u8]) -> Result<(), Errno> {
        self.chain_io(clusters, pos, buf.len(), |vol, disk, range| vol.read_bytes(disk, &mut buf[range]))
    }

    fn write_chain(&self, clusters: &[u32], pos: u64, data: &[u8]) -> Result<(), Errno> {
        self.chain_io(clusters, pos, data.len(), |vol, disk, range| vol.write_bytes(disk, &data[range]))
    }

    /// Split `len` bytes at chain offset `pos` into runs of consecutive
    /// clusters, calling `io(device byte offset, range of the buffer)`.
    fn chain_io(
        &self,
        clusters: &[u32],
        pos: u64,
        len: usize,
        mut io: impl FnMut(&Self, u64, core::ops::Range<usize>) -> Result<(), Errno>,
    ) -> Result<(), Errno> {
        let cs = self.cluster_size as u64;
        let mut done = 0;
        while done < len {
            let at = pos + done as u64;
            let mut k = (at / cs) as usize;
            let first = *clusters.get(k).ok_or(Errno::EIO)?;
            // Extend the run while the next cluster follows this one.
            let mut run_end = (k as u64 + 1) * cs;
            while run_end < at + (len - done) as u64 && k + 1 < clusters.len() && clusters[k + 1] == clusters[k] + 1 {
                k += 1;
                run_end += cs;
            }
            let n = ((run_end - at) as usize).min(len - done);
            io(self, self.cluster_pos(first) + at % cs, done..done + n)?;
            done += n;
        }
        Ok(())
    }

    /// Make `clusters` long enough for `size` bytes. Grows in place
    /// (NoFatChain stays set) while the next cluster is free; otherwise the
    /// chain is written into the FAT and continues elsewhere.
    fn grow(&mut self, chain: &mut Chain, clusters: &mut Vec<u32>, size: u64) -> Result<(), Errno> {
        while (clusters.len() as u64) * (self.cluster_size as u64) < size {
            let Some(&last) = clusters.last() else {
                let c = self.alloc(0)?;
                *chain = Chain { first: c, contiguous: true };
                clusters.push(c);
                continue;
            };
            let c = self.alloc(last + 1)?;
            if c != last + 1 && chain.contiguous {
                // Can't stay contiguous: give the existing clusters FAT links.
                for w in clusters.windows(2) {
                    self.fat_set(w[0], w[1])?;
                }
                chain.contiguous = false;
            }
            if !chain.contiguous {
                self.fat_set(last, c)?;
                self.fat_set(c, FAT_END)?;
            }
            clusters.push(c);
        }
        self.update_percent()
    }

    /// Free every cluster of a chain.
    fn free(&mut self, chain: Chain, clusters: &[u32]) -> Result<(), Errno> {
        for &c in clusters {
            if !chain.contiguous {
                self.fat_set(c, 0)?;
            }
            self.set_used(c, false)?;
        }
        self.update_percent()
    }

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

    /// Read a directory and parse its entry sets.
    fn read_dir(&self, dir: &Found) -> Result<(Vec<u32>, Vec<u8>, Vec<Set>), Errno> {
        let clusters = self.clusters(dir.chain, dir.size)?;
        let mut data = vec![0u8; dir.size as usize];
        self.read_chain(&clusters, 0, &mut data)?;
        let mut sets = Vec::new();
        let count = data.len() / ENTRY_SIZE;
        let mut i = 0;
        while i < count {
            let e = &data[i * ENTRY_SIZE..(i + 1) * ENTRY_SIZE];
            if e[0] == ENTRY_END {
                break;
            }
            if e[0] != ENTRY_FILE {
                i += 1; // deleted, label, bitmap, up-case... or a stray entry
                continue;
            }
            let entries = 1 + e[FILE_SECONDARY_COUNT] as usize;
            if let Some(set) = Self::parse_set(&data, i, entries) {
                sets.push(set);
                i += entries; // skip the whole set
            } else {
                i += 1; // damaged set: skip it (fsck can sort it out)
            }
        }
        Ok((clusters, data, sets))
    }

    fn parse_set(data: &[u8], index: usize, entries: usize) -> Option<Set> {
        let bytes = data.get(index * ENTRY_SIZE..(index + entries) * ENTRY_SIZE)?;
        if entries < 3 || bytes[ENTRY_SIZE] != ENTRY_STREAM || set_checksum(bytes) != get16(bytes, FILE_SET_CHECKSUM) {
            return None;
        }
        let stream = &bytes[ENTRY_SIZE..2 * ENTRY_SIZE];
        let len = stream[STREAM_NAME_LENGTH] as usize;
        let mut name = Vec::new();
        for e in bytes[2 * ENTRY_SIZE..].chunks(ENTRY_SIZE).filter(|e| e[0] == ENTRY_NAME) {
            name.extend((0..NAME_CHARS_PER_ENTRY).map(|j| get16(e, 2 + 2 * j)));
        }
        if len == 0 || name.len() < len {
            return None;
        }
        name.truncate(len);
        Some(Set {
            index,
            name,
            attrs: get16(bytes, FILE_ATTRIBUTES),
            chain: Chain {
                first: get32(stream, STREAM_FIRST_CLUSTER),
                contiguous: stream[STREAM_FLAGS] & FLAG_NO_FAT_CHAIN != 0,
            },
            size: get64(stream, STREAM_DATA_LENGTH),
            valid: get64(stream, STREAM_VALID_DATA_LENGTH),
        })
    }

    /// Follow a path (already split into names) from the root.
    fn resolve(&self, path: &[String]) -> Result<Found, Errno> {
        let mut cur = self.root()?;
        for name in path {
            if !cur.is_dir() {
                return Err(Errno::ENOTDIR);
            }
            let units: Vec<u16> = name.encode_utf16().collect();
            let (clusters, _, sets) = self.read_dir(&cur)?;
            let s = sets.into_iter().find(|s| self.same_name(&s.name, &units)).ok_or(Errno::ENOENT)?;
            cur = Found { at: Some((clusters, s.index)), attrs: s.attrs, chain: s.chain, size: s.size, valid: s.valid };
        }
        Ok(cur)
    }

    /// Rewrite a file's stream entry (where its data is and how big it is)
    /// and its SetChecksum.
    fn update_entry(&self, f: &Found) -> Result<(), Errno> {
        let Some((parent, index)) = &f.at else {
            return Ok(()); // the root has no entry; its size lives in the FAT
        };
        let pos = (*index * ENTRY_SIZE) as u64;
        let mut head = [0u8; ENTRY_SIZE];
        self.read_chain(parent, pos, &mut head)?;
        let mut set = vec![0u8; (1 + head[FILE_SECONDARY_COUNT] as usize) * ENTRY_SIZE];
        self.read_chain(parent, pos, &mut set)?;
        let stream = &mut set[ENTRY_SIZE..2 * ENTRY_SIZE];
        stream[STREAM_FLAGS] = FLAG_ALLOCATION_POSSIBLE | if f.chain.contiguous && f.chain.first != 0 { FLAG_NO_FAT_CHAIN } else { 0 };
        put64(stream, STREAM_VALID_DATA_LENGTH, f.valid);
        put32(stream, STREAM_FIRST_CLUSTER, f.chain.first);
        put64(stream, STREAM_DATA_LENGTH, f.size);
        let sum = set_checksum(&set);
        put16(&mut set, FILE_SET_CHECKSUM, sum);
        self.write_chain(parent, pos, &set)
    }

    /// Build the entry set for a new, empty file or directory.
    fn new_set(&self, name: &[u16], attrs: u16, chain: Chain, size: u64) -> Vec<u8> {
        let names = name.len().div_ceil(NAME_CHARS_PER_ENTRY);
        let mut set = vec![0u8; (2 + names) * ENTRY_SIZE];
        set[0] = ENTRY_FILE;
        set[FILE_SECONDARY_COUNT] = (1 + names) as u8;
        put16(&mut set, FILE_ATTRIBUTES, attrs);
        for at in FILE_TIMES {
            put32(&mut set, at, TIMESTAMP);
        }
        let mut hash_input = Vec::new();
        for &u in name {
            hash_input.extend_from_slice(&self.upcase(u).to_le_bytes());
        }
        let stream = &mut set[ENTRY_SIZE..2 * ENTRY_SIZE];
        stream[0] = ENTRY_STREAM;
        stream[STREAM_NAME_LENGTH] = name.len() as u8;
        // NameHash: the checksum over the up-cased name (no bytes skipped,
        // so sum by hand rather than with set_checksum).
        let hash = hash_input.iter().fold(0u16, |s, &b| s.rotate_right(1).wrapping_add(b as u16));
        put16(stream, STREAM_NAME_HASH, hash);
        stream[STREAM_FLAGS] = FLAG_ALLOCATION_POSSIBLE | if chain.contiguous && chain.first != 0 { FLAG_NO_FAT_CHAIN } else { 0 };
        put64(stream, STREAM_VALID_DATA_LENGTH, size);
        put32(stream, STREAM_FIRST_CLUSTER, chain.first);
        put64(stream, STREAM_DATA_LENGTH, size);
        for (k, chunk) in name.chunks(NAME_CHARS_PER_ENTRY).enumerate() {
            let e = &mut set[(2 + k) * ENTRY_SIZE..(3 + k) * ENTRY_SIZE];
            e[0] = ENTRY_NAME;
            for (j, &u) in chunk.iter().enumerate() {
                put16(e, 2 + 2 * j, u);
            }
        }
        let sum = set_checksum(&set);
        put16(&mut set, FILE_SET_CHECKSUM, sum);
        set
    }

    fn create(&mut self, dir_path: &[String], name: &str, kind: InodeKind) -> Result<(), Errno> {
        if !self.writable {
            return Err(Errno::EROFS);
        }
        let units = valid_name(name)?;
        let attrs = match kind {
            InodeKind::File => ATTR_ARCHIVE,
            InodeKind::Directory => ATTR_DIRECTORY,
            InodeKind::Symlink | InodeKind::Device => return Err(Errno::EOPNOTSUPP), // exFAT has neither
        };
        let mut dir = self.resolve(dir_path)?;
        if !dir.is_dir() {
            return Err(Errno::ENOTDIR);
        }
        let (mut clusters, data, sets) = self.read_dir(&dir)?;
        if sets.iter().any(|s| self.same_name(&s.name, &units)) {
            return Err(Errno::EEXIST);
        }
        let need = 2 + units.len().div_ceil(NAME_CHARS_PER_ENTRY);

        // First run of `need` free entries (not in use: deleted or past the
        // end). If the run reaches the end of the directory, grow it.
        let total = data.len() / ENTRY_SIZE;
        let is_free = |i: usize| i >= total || data[i * ENTRY_SIZE] & ENTRY_IN_USE == 0;
        let mut start = 0;
        while start < total && !(start..start + need).all(is_free) {
            start += 1;
        }
        let end = ((start + need) * ENTRY_SIZE) as u64;
        if end > dir.size {
            // Round up to whole clusters: a directory is always full clusters.
            let new_size = end.div_ceil(self.cluster_size as u64) * self.cluster_size as u64;
            let mut chain = dir.chain;
            self.grow(&mut chain, &mut clusters, new_size)?;
            dir.chain = chain;
            dir.size = new_size;
            dir.valid = new_size;
            self.update_entry(&dir)?;
        }

        // A directory gets one (zeroed) cluster: it must end with 0x00.
        let (chain, size) = if kind == InodeKind::Directory {
            let c = self.alloc(0)?;
            self.update_percent()?;
            (Chain { first: c, contiguous: true }, self.cluster_size as u64)
        } else {
            (Chain { first: 0, contiguous: false }, 0)
        };
        let set = self.new_set(&units, attrs, chain, size);
        self.write_chain(&clusters, (start * ENTRY_SIZE) as u64, &set)
    }

    fn remove(&mut self, dir_path: &[String], name: &str) -> Result<(), Errno> {
        if !self.writable {
            return Err(Errno::EROFS);
        }
        let mut path = dir_path.to_vec();
        path.push(name.into());
        let f = self.resolve(&path)?;
        let Some((parent, index)) = &f.at else {
            return Err(Errno::EBUSY); // the root
        };
        if f.is_dir() {
            let (_, data, _) = self.read_dir(&f)?;
            if data.chunks(ENTRY_SIZE).any(|e| e[0] & ENTRY_IN_USE != 0) {
                return Err(Errno::ENOTEMPTY);
            }
        }
        let clusters = self.clusters(f.chain, f.size)?;
        // Mark every entry of the set unused: clear bit 7 of its type.
        let pos = (*index * ENTRY_SIZE) as u64;
        let mut head = [0u8; ENTRY_SIZE];
        self.read_chain(parent, pos, &mut head)?;
        let mut set = vec![0u8; (1 + head[FILE_SECONDARY_COUNT] as usize) * ENTRY_SIZE];
        self.read_chain(parent, pos, &mut set)?;
        for e in set.chunks_mut(ENTRY_SIZE) {
            e[0] &= !ENTRY_IN_USE;
        }
        self.write_chain(parent, pos, &set)?;
        self.free(f.chain, &clusters)
    }

    fn read_file(&self, f: &Found, offset: u64, buf: &mut [u8]) -> Result<usize, Errno> {
        if offset >= f.size {
            return Ok(0);
        }
        let n = buf.len().min((f.size - offset) as usize);
        let clusters = self.clusters(f.chain, f.size)?;
        // Past ValidDataLength the data is "zeros" whatever the disk holds.
        let real = (f.valid.min(f.size).saturating_sub(offset) as usize).min(n);
        self.read_chain(&clusters, offset, &mut buf[..real])?;
        buf[real..n].fill(0);
        Ok(n)
    }

    fn write_file(&mut self, f: &mut Found, offset: u64, data: &[u8]) -> Result<usize, Errno> {
        if !self.writable {
            return Err(Errno::EROFS);
        }
        let end = offset.checked_add(data.len() as u64).ok_or(Errno::EFBIG)?;
        let mut clusters = self.clusters(f.chain, f.size)?;
        if f.valid < f.size.min(offset) {
            // Another system left bytes past ValidDataLength undefined; once
            // we make the file "all valid", they must really be zeros.
            let gap = f.size.min(offset) - f.valid;
            self.write_chain(&clusters, f.valid, &vec![0u8; gap as usize])?;
        }
        if end > f.size {
            let old = f.size;
            self.grow(&mut f.chain, &mut clusters, end)?;
            // Writing past the end leaves a gap that must read as zeros:
            // clear what's left of the old last cluster (new ones are zeroed).
            let allocated = old.div_ceil(self.cluster_size as u64) * self.cluster_size as u64;
            if offset > old && allocated > old {
                let gap = offset.min(allocated) - old;
                self.write_chain(&clusters, old, &vec![0u8; gap as usize])?;
            }
            f.size = end;
        }
        self.write_chain(&clusters, offset, data)?;
        f.valid = f.size;
        self.update_entry(f)?;
        Ok(data.len())
    }

    fn truncate(&mut self, path: &[String]) -> Result<(), Errno> {
        if !self.writable {
            return Err(Errno::EROFS);
        }
        let mut f = self.resolve(path)?;
        let clusters = self.clusters(f.chain, f.size)?;
        self.free(f.chain, &clusters)?;
        f.chain = Chain { first: 0, contiguous: false };
        f.size = 0;
        f.valid = 0;
        self.update_entry(&f)
    }
}

/// exFAT names: 1-255 UTF-16 units, no control characters or `"*/:<>?\|`.
fn valid_name(name: &str) -> Result<Vec<u16>, Errno> {
    let units: Vec<u16> = name.encode_utf16().collect();
    if units.len() > 255 {
        return Err(Errno::ENAMETOOLONG);
    }
    if units.is_empty() || name == "." || name == ".." || name.chars().any(|c| c < ' ' || "\"*/:<>?\\|".contains(c)) {
        return Err(Errno::EINVAL);
    }
    Ok(units)
}

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

pub struct ExfatFs {
    vol: Arc<Mutex<Volume>>,
}

impl ExfatFs {
    pub fn mount(dev: Arc<dyn BlockDevice>) -> Result<Arc<ExfatFs>, Errno> {
        Ok(Arc::new(ExfatFs { vol: Arc::new(Mutex::new(Volume::open(dev)?)) }))
    }

    /// For the boot log, e.g. `exFAT volume "TYLEREXFAT" (4 KiB clusters, 7680 clusters)`.
    pub fn describe(&self) -> String {
        self.vol.lock().describe()
    }

    /// (used clusters, total clusters), from the in-memory bitmap.
    pub fn usage(&self) -> (u32, u32) {
        let v = self.vol.lock();
        (v.used, v.cluster_count)
    }
}

impl FileSystem for ExfatFs {
    fn name(&self) -> &'static str {
        "exfat"
    }
    fn root(&self) -> Arc<dyn Inode> {
        Arc::new(ExfatInode { vol: self.vol.clone(), path: Vec::new(), kind: InodeKind::Directory })
    }
}

/// A file or directory on an exFAT volume. exFAT has no inode numbers (a
/// file *is* its directory entry), so we remember the path from the root
/// and look it up again on every call.
pub struct ExfatInode {
    vol: Arc<Mutex<Volume>>,
    path: Vec<String>,
    kind: InodeKind,
}

impl ExfatInode {
    fn dir_only(&self) -> Result<(), Errno> {
        if self.kind == InodeKind::Directory { Ok(()) } else { Err(Errno::ENOTDIR) }
    }
    fn file_only(&self) -> Result<(), Errno> {
        if self.kind == InodeKind::Directory { Err(Errno::EISDIR) } else { Ok(()) }
    }
    fn child(&self, name: &str, kind: InodeKind) -> Arc<dyn Inode> {
        let mut path = self.path.clone();
        path.push(name.into());
        Arc::new(ExfatInode { vol: self.vol.clone(), path, kind })
    }
}

impl Inode for ExfatInode {
    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().resolve(&self.path).map(|f| f.size as usize).unwrap_or(0)
    }

    fn read_at(&self, offset: usize, buf: &mut [u8]) -> Result<usize, Errno> {
        self.file_only()?;
        let vol = self.vol.lock();
        let f = vol.resolve(&self.path)?;
        vol.read_file(&f, offset as u64, buf)
    }

    fn write_at(&self, offset: usize, buf: &[u8]) -> Result<usize, Errno> {
        self.file_only()?;
        let mut vol = self.vol.lock();
        let mut f = vol.resolve(&self.path)?;
        vol.write_file(&mut f, offset as u64, buf)
    }

    fn truncate(&self) -> Result<(), Errno> {
        self.file_only()?;
        self.vol.lock().truncate(&self.path)
    }

    fn lookup(&self, name: &str) -> Result<Arc<dyn Inode>, Errno> {
        self.dir_only()?;
        let mut path = self.path.clone();
        path.push(name.into());
        let f = self.vol.lock().resolve(&path)?;
        Ok(self.child(name, if f.is_dir() { InodeKind::Directory } else { InodeKind::File }))
    }

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

    fn list(&self) -> Result<Vec<DirEntry>, Errno> {
        self.dir_only()?;
        let vol = self.vol.lock();
        let dir = vol.resolve(&self.path)?;
        let (_, _, sets) = vol.read_dir(&dir)?;
        Ok(sets
            .into_iter()
            .map(|s| DirEntry {
                name: String::from_utf16_lossy(&s.name),
                kind: if s.attrs & ATTR_DIRECTORY != 0 { InodeKind::Directory } else { InodeKind::File },
            })
            .collect())
    }

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