rust-fs-ext4 0.8.0

//! Extent tree mutation — planning layer (E7).
//!
//! Produces typed [`ExtentMutation`] values describing how the extent tree
//! should change. Does NOT write to disk; E10 composes these into file write
//! operations and E11 journals them.
//!
//! Scope for Phase 4 initial landing:
//! - Operations on the inline root (leaf, depth 0). The inline root carries up
//!   to 4 entries on a standard 60-byte i_block area, which covers the common
//!   case of small files (≤ 4 contiguous extents).
//! - `insert_extent`: place a new leaf extent in sorted position; returns an
//!   error tagged `LEAF_FULL_NEEDS_PROMOTION` when the root is saturated and
//!   the caller must promote to depth > 0 (future task).
//! - `split_extent`: split one extent at a logical-block boundary (used when
//!   partially overwriting, freeing a middle run, or converting uninit→init on
//!   a sub-range).
//! - `merge_adjacent`: fuse two neighbours whose `[log+len, phys+len)` line up.
//! - `free_extent`: drop an entry and report the physical block range to
//!   hand to the block bitmap freer (E5).
//!
//! Multi-level tree mutation (leaf-block split, internal-node rebalance) is
//! deferred. Hitting it returns [`Error::Corrupt`] with a clear message so
//! callers can fall back to copy-on-write or error out cleanly.

use crate::error::{Error, Result};
use crate::extent::{
    Extent, ExtentHeader, ExtentIdx, EXT4_EXT_MAGIC, EXT4_EXT_MAX_DEPTH, EXT4_EXT_NODE_SIZE,
    EXT_INIT_MAX_LEN,
};

// Byte offsets within a 12-byte extent tree node header.
const EXT4_EXT_HDR_MAGIC_OFF: usize = 0;
const EXT4_EXT_HDR_ENTRIES_OFF: usize = 2;
const EXT4_EXT_HDR_MAX_OFF: usize = 4;
const EXT4_EXT_HDR_DEPTH_OFF: usize = 6;
const EXT4_EXT_HDR_GEN_OFF: usize = 8;

/// Byte offset of extent entry `i` within a node body (entries follow the
/// 12-byte header, so entry 0 is at offset `EXT4_EXT_NODE_SIZE`).
#[inline]
fn extent_entry_offset(i: usize) -> usize {
    EXT4_EXT_NODE_SIZE * (1 + i)
}

/// Split a 64-bit physical block address into the hi u16 and lo u32 fields
/// used by ext4 extent and index entries.
#[inline]
pub(crate) fn split_phys_block(block: u64) -> (u16, u32) {
    let hi = ((block >> 32) & 0xFFFF) as u16;
    let lo = (block & 0xFFFF_FFFF) as u32;
    (hi, lo)
}

/// A primitive change the extent-write path wants to make to the tree. The
/// caller (E10 or a test) converts this into real I/O under a transaction.
#[derive(Debug, Clone, PartialEq, Eq)]
pub enum ExtentMutation {
    /// Overwrite the inline root (60 bytes of `i_block`) with these bytes.
    WriteRoot { bytes: Vec<u8> },
    /// Rewrite an existing external extent node. The filesystem patches its
    /// checksum and journals this together with the inode and bitmap updates.
    WriteTreeBlock { block: u64, bytes: Vec<u8> },
    /// Allocate a fresh leaf block and write these bytes to it. Returned for
    /// future multi-level operations; not produced by the current plan fns.
    AllocLeafBlock { bytes: Vec<u8> },
    /// Free a previously-used leaf/index block back to the bitmap.
    FreeLeafBlock { block: u64 },
    /// Free a contiguous physical-block run back to the bitmap (from a
    /// dropped leaf extent). `start` is the first physical block, `len` is
    /// the count.
    FreePhysicalRun { start: u64, len: u32 },
}

/// Build a leaf extent entry's 12 bytes.
fn encode_extent(e: &Extent) -> [u8; EXT4_EXT_NODE_SIZE] {
    let mut buf = [0u8; EXT4_EXT_NODE_SIZE];
    buf[0..4].copy_from_slice(&e.logical_block.to_le_bytes());
    let ee_len: u16 = if e.uninitialized {
        e.length + EXT_INIT_MAX_LEN
    } else {
        e.length
    };
    buf[4..6].copy_from_slice(&ee_len.to_le_bytes());
    let (phys_hi, phys_lo) = split_phys_block(e.physical_block);
    buf[6..8].copy_from_slice(&phys_hi.to_le_bytes());
    buf[8..12].copy_from_slice(&phys_lo.to_le_bytes());
    buf
}

/// Re-emit the inline root from a header + sorted extent list. `root_len` is
/// the size of the i_block area (always 60 for inline root, larger for a
/// full-block leaf).
fn build_root(header: &ExtentHeader, extents: &[Extent], root_len: usize) -> Vec<u8> {
    let mut out = vec![0u8; root_len];
    out[EXT4_EXT_HDR_MAGIC_OFF..EXT4_EXT_HDR_MAGIC_OFF + 2]
        .copy_from_slice(&EXT4_EXT_MAGIC.to_le_bytes());
    out[EXT4_EXT_HDR_ENTRIES_OFF..EXT4_EXT_HDR_ENTRIES_OFF + 2]
        .copy_from_slice(&(extents.len() as u16).to_le_bytes());
    out[EXT4_EXT_HDR_MAX_OFF..EXT4_EXT_HDR_MAX_OFF + 2].copy_from_slice(&header.max.to_le_bytes());
    out[EXT4_EXT_HDR_DEPTH_OFF..EXT4_EXT_HDR_DEPTH_OFF + 2]
        .copy_from_slice(&header.depth.to_le_bytes());
    out[EXT4_EXT_HDR_GEN_OFF..EXT4_EXT_HDR_GEN_OFF + 4]
        .copy_from_slice(&header.generation.to_le_bytes());
    for (i, e) in extents.iter().enumerate() {
        let off = extent_entry_offset(i);
        out[off..off + EXT4_EXT_NODE_SIZE].copy_from_slice(&encode_extent(e));
    }
    out
}

/// Read the leaf entries from an inline root. Errors on non-leaf (the root
/// has descended into index entries — caller must handle the multi-level
/// case separately).
fn read_leaf_entries(root: &[u8]) -> Result<(ExtentHeader, Vec<Extent>)> {
    let header = ExtentHeader::parse(root)?;
    if !header.is_leaf() {
        return Err(Error::CorruptExtentTree(
            "extent_mut: multi-level tree mutation not yet supported",
        ));
    }
    let mut out = Vec::with_capacity(header.entries as usize);
    for i in 0..header.entries {
        let off = extent_entry_offset(i as usize);
        if off + EXT4_EXT_NODE_SIZE > root.len() {
            return Err(Error::CorruptExtentTree("leaf entry out of range"));
        }
        out.push(Extent::parse(&root[off..off + EXT4_EXT_NODE_SIZE])?);
    }
    Ok((header, out))
}

/// Longest extent `ee_len` can describe in `uninitialized` state: 32768
/// initialized blocks, 32767 uninitialized (an `ee_len` above 32768 is what
/// marks an extent uninitialized, so 32768 itself is reserved for the
/// initialized one). These are the two maxima the format documentation
/// gives with `ee_len`, and a merge never crosses them.
fn max_extent_len(uninitialized: bool) -> u32 {
    if uninitialized {
        u32::from(EXT_INIT_MAX_LEN) - 1
    } else {
        u32::from(EXT_INIT_MAX_LEN)
    }
}

/// Returns true iff two adjacent leaf extents are physically contiguous, in
/// the same uninit state, and short enough together to be one extent —
/// candidate for a merge.
///
/// The length cap is not optional (#387): an initialized extent longer than
/// 32768 blocks encodes as an uninitialized one of `len - 32768`, and two
/// uninitialized ones past 32767 overflow `ee_len`.
fn are_contiguous(a: &Extent, b: &Extent) -> bool {
    if a.uninitialized != b.uninitialized {
        return false;
    }
    if u32::from(a.length) + u32::from(b.length) > max_extent_len(a.uninitialized) {
        return false;
    }
    let a_log_end = a.logical_block as u64 + a.length as u64;
    let a_phys_end = a.physical_block + a.length as u64;
    a_log_end == b.logical_block as u64 && a_phys_end == b.physical_block
}

/// Plan insertion of `new` into the inline-root leaf. Preserves sort order on
/// `logical_block`, rejects overlaps, and auto-merges with the prev / next
/// entry when contiguous.
///
/// Errors:
/// - `LEAF_FULL_NEEDS_PROMOTION` if there is no room AND no merge was
///   possible. Caller must promote to an internal-root tree (future task).
/// - `extent overlaps existing` if `new`'s logical range overlaps an existing
///   entry.
pub fn plan_insert_extent(root: &[u8], new: Extent) -> Result<Vec<ExtentMutation>> {
    let (header, mut entries) = read_leaf_entries(root)?;

    // Reject overlaps. Assumes entries sorted by logical_block.
    for e in &entries {
        let e_end = e.logical_block as u64 + e.length as u64;
        let n_end = new.logical_block as u64 + new.length as u64;
        if !(n_end <= e.logical_block as u64 || new.logical_block as u64 >= e_end) {
            return Err(Error::CorruptExtentTree("extent overlaps existing"));
        }
    }

    // Find insert position (stable — first index whose logical_block > new).
    let pos = entries
        .iter()
        .position(|e| e.logical_block as u64 > new.logical_block as u64)
        .unwrap_or(entries.len());
    entries.insert(pos, new);

    // Auto-merge with left neighbour if contiguous.
    if pos > 0 && are_contiguous(&entries[pos - 1], &entries[pos]) {
        let right = entries.remove(pos);
        entries[pos - 1].length += right.length;
    }
    // Auto-merge with right neighbour (pos may have shifted — recompute).
    let pos = entries
        .iter()
        .position(|e| {
            e.logical_block == new.logical_block
                || (e.logical_block as u64) < new.logical_block as u64
                    && (e.logical_block as u64 + e.length as u64) > new.logical_block as u64
        })
        .unwrap_or(entries.len().saturating_sub(1));
    if pos + 1 < entries.len() && are_contiguous(&entries[pos], &entries[pos + 1]) {
        let right = entries.remove(pos + 1);
        entries[pos].length += right.length;
    }

    if entries.len() as u16 > header.max {
        return Err(Error::CorruptExtentTree(
            "LEAF_FULL_NEEDS_PROMOTION: root has no slot for new extent",
        ));
    }

    let new_root = build_root(&header, &entries, root.len());
    Ok(vec![ExtentMutation::WriteRoot { bytes: new_root }])
}

/// Layout for a promote-leaf-to-depth-1 operation: the new leaf block that
/// holds the five entries (four old + the new one), and the rewritten inline
/// root that indexes it.
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct PromotionPlan {
    /// Full-block bytes for the freshly-allocated leaf node. Header at the
    /// start, sorted leaf entries, zeros to end. If `reserved_tail_csum` was
    /// true the last 4 bytes are reserved for the caller to patch with
    /// `checksum.patch_extent_tail`.
    pub leaf_bytes: Vec<u8>,
    /// 60 bytes of the new inline root: depth=1, entries=1, single index
    /// entry whose logical_block = 0 and leaf_block = the physical block the
    /// caller allocated for `leaf_bytes`.
    pub new_root_bytes: Vec<u8>,
}

/// Build a depth-0 leaf block (full `block_size` bytes). Reserves 4 tail
/// bytes for the ext4_extent_tail CRC when `reserved_tail_csum` is true.
fn build_leaf_block(
    generation: u32,
    extents: &[Extent],
    block_size: usize,
    reserved_tail_csum: bool,
) -> Vec<u8> {
    let mut out = vec![0u8; block_size];
    let header_body_len = block_size.saturating_sub(if reserved_tail_csum { 4 } else { 0 });
    let max_entries = ((header_body_len - EXT4_EXT_NODE_SIZE) / EXT4_EXT_NODE_SIZE) as u16;
    out[EXT4_EXT_HDR_MAGIC_OFF..EXT4_EXT_HDR_MAGIC_OFF + 2]
        .copy_from_slice(&EXT4_EXT_MAGIC.to_le_bytes());
    out[EXT4_EXT_HDR_ENTRIES_OFF..EXT4_EXT_HDR_ENTRIES_OFF + 2]
        .copy_from_slice(&(extents.len() as u16).to_le_bytes());
    out[EXT4_EXT_HDR_MAX_OFF..EXT4_EXT_HDR_MAX_OFF + 2].copy_from_slice(&max_entries.to_le_bytes());
    out[EXT4_EXT_HDR_DEPTH_OFF..EXT4_EXT_HDR_DEPTH_OFF + 2].copy_from_slice(&0u16.to_le_bytes());
    out[EXT4_EXT_HDR_GEN_OFF..EXT4_EXT_HDR_GEN_OFF + 4].copy_from_slice(&generation.to_le_bytes());
    for (i, e) in extents.iter().enumerate() {
        let off = extent_entry_offset(i);
        out[off..off + EXT4_EXT_NODE_SIZE].copy_from_slice(&encode_extent(e));
    }
    out
}

/// Build a 60-byte depth-1 inline root containing a single index entry
/// pointing at `leaf_phys` (logical 0).
fn build_depth1_index_root(generation: u32, leaf_phys: u64) -> Vec<u8> {
    let mut out = vec![0u8; 60];
    out[EXT4_EXT_HDR_MAGIC_OFF..EXT4_EXT_HDR_MAGIC_OFF + 2]
        .copy_from_slice(&EXT4_EXT_MAGIC.to_le_bytes());
    out[EXT4_EXT_HDR_ENTRIES_OFF..EXT4_EXT_HDR_ENTRIES_OFF + 2]
        .copy_from_slice(&1u16.to_le_bytes()); // entries=1
    out[EXT4_EXT_HDR_MAX_OFF..EXT4_EXT_HDR_MAX_OFF + 2].copy_from_slice(&4u16.to_le_bytes()); // max=4 (inline root)
    out[EXT4_EXT_HDR_DEPTH_OFF..EXT4_EXT_HDR_DEPTH_OFF + 2].copy_from_slice(&1u16.to_le_bytes()); // depth=1
    out[EXT4_EXT_HDR_GEN_OFF..EXT4_EXT_HDR_GEN_OFF + 4].copy_from_slice(&generation.to_le_bytes());
    let ei_block: u32 = 0;
    let (ei_leaf_hi, ei_leaf_lo) = split_phys_block(leaf_phys);
    out[12..16].copy_from_slice(&ei_block.to_le_bytes());
    out[16..20].copy_from_slice(&ei_leaf_lo.to_le_bytes());
    out[20..22].copy_from_slice(&ei_leaf_hi.to_le_bytes());
    out
}

/// Plan a depth-0 → depth-1 promotion. The caller must have already seen
/// `LEAF_FULL_NEEDS_PROMOTION` from `plan_insert_extent` and allocated one
/// fresh filesystem block to hold the new leaf.
///
/// Produces:
///   - `leaf_bytes`: the entire new leaf block (`block_size` bytes) containing
///     all existing extents + `new`, sorted and merge-compatible with the
///     existing layout. Last 4 bytes are reserved for the caller to patch
///     with `checksum.patch_extent_tail` when metadata_csum is on.
///   - `new_root_bytes`: 60 bytes, depth=1, one index entry → `new_leaf_phys`.
///
/// Errors if `root` is not a leaf (depth != 0) — the multi-level split case
/// is a further task. Also rejects overlaps with existing entries.
pub fn plan_promote_leaf(
    root: &[u8],
    new: Extent,
    block_size: usize,
    new_leaf_phys: u64,
    reserved_tail_csum: bool,
) -> Result<PromotionPlan> {
    let (header, mut entries) = read_leaf_entries(root)?;

    for e in &entries {
        let e_end = e.logical_block as u64 + e.length as u64;
        let n_end = new.logical_block as u64 + new.length as u64;
        if !(n_end <= e.logical_block as u64 || new.logical_block as u64 >= e_end) {
            return Err(Error::CorruptExtentTree("extent overlaps existing"));
        }
    }

    let pos = entries
        .iter()
        .position(|e| e.logical_block as u64 > new.logical_block as u64)
        .unwrap_or(entries.len());
    entries.insert(pos, new);

    if pos > 0 && are_contiguous(&entries[pos - 1], &entries[pos]) {
        let right = entries.remove(pos);
        entries[pos - 1].length += right.length;
    }
    let merged_pos = entries
        .iter()
        .position(|e| {
            e.logical_block == new.logical_block
                || ((e.logical_block as u64) < new.logical_block as u64
                    && (e.logical_block as u64 + e.length as u64) > new.logical_block as u64)
        })
        .unwrap_or(entries.len().saturating_sub(1));
    if merged_pos + 1 < entries.len()
        && are_contiguous(&entries[merged_pos], &entries[merged_pos + 1])
    {
        let right = entries.remove(merged_pos + 1);
        entries[merged_pos].length += right.length;
    }

    let leaf_capacity_bytes = block_size.saturating_sub(if reserved_tail_csum { 4 } else { 0 });
    let leaf_max = ((leaf_capacity_bytes - EXT4_EXT_NODE_SIZE) / EXT4_EXT_NODE_SIZE) as u16;
    if entries.len() as u16 > leaf_max {
        return Err(Error::CorruptExtentTree(
            "plan_promote_leaf: entry count exceeds leaf capacity",
        ));
    }

    let leaf_bytes = build_leaf_block(header.generation, &entries, block_size, reserved_tail_csum);
    let new_root_bytes = build_depth1_index_root(header.generation, new_leaf_phys);
    Ok(PromotionPlan {
        leaf_bytes,
        new_root_bytes,
    })
}

// ----------------------------------------------------------------------------
// Depth ≥ 2 mutation: descend, insert at leaf, propagate splits, promote root.
// ----------------------------------------------------------------------------

/// Read interface used by [`plan_insert_extent_deep`] to fetch any internal
/// or leaf block referenced by an index entry on the way down. Callers wire
/// this through a `BlockDevice` (or a buffered cache when running under a
/// transaction).
pub trait DeepReader {
    /// Read exactly `out.len()` bytes of the block numbered `block`. The
    /// caller picks the buffer size (always `block_size`).
    fn read_block(&self, block: u64, out: &mut [u8]) -> Result<()>;
}

/// Result of a deep insert. The caller stages each component into its
/// transaction (inode-i_block patch + per-block writes + bitmap/BGD updates
/// for the freshly-allocated blocks).
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct DeepInsertPlan {
    /// New 60 bytes of `i_block`. Depth may have changed (root promotion).
    pub new_root: Vec<u8>,
    /// Block writes, one per modified-or-new block. Each entry is
    /// `(block_num, full block_size bytes)`. Non-root blocks have their last
    /// 4 bytes zeroed and reserved — the caller patches `et_checksum` via
    /// [`crate::checksum::Checksummer::patch_extent_tail`].
    pub block_writes: Vec<(u64, Vec<u8>)>,
    /// Block numbers freshly pulled from the allocator closure, in the order
    /// they were drawn. The caller marks each used in the bitmap and bumps
    /// BGD/SB counters in the same transaction.
    pub allocated_blocks: Vec<u64>,
}

/// One frame on the descent path: the block we read and its raw bytes.
///
/// The root frame uses `block = 0` as a placeholder — root is recognised
/// by its position (the first frame) rather than by the field.
///
/// It also carried `idx_in_parent`, the position of the index entry in
/// the parent that selected this child. Every construction site set it
/// and nothing ever read it; the crate-wide `allow(dead_code)` is what
/// kept that invisible. If a rebalance ever needs to rewrite a parent's
/// entry in place, it comes back — as a field something reads.
struct PathFrame {
    /// Block number of this node. `0` if this is the inline root.
    block: u64,
    /// Raw bytes (60 for root, `block_size` for everything below).
    bytes: Vec<u8>,
}

/// Encode a 12-byte index entry pointing at `child_phys` for the subtree
/// whose smallest logical block is `logical_block`.
fn encode_index(logical_block: u32, child_phys: u64) -> [u8; EXT4_EXT_NODE_SIZE] {
    let mut buf = [0u8; EXT4_EXT_NODE_SIZE];
    let (leaf_hi, leaf_lo) = split_phys_block(child_phys);
    buf[0..4].copy_from_slice(&logical_block.to_le_bytes());
    buf[4..8].copy_from_slice(&leaf_lo.to_le_bytes());
    buf[8..10].copy_from_slice(&leaf_hi.to_le_bytes());
    // 0x0A..0x0C is ei_unused — already zero.
    buf
}

/// Read every leaf entry from a node body, regardless of whether it's inline
/// or a full block. Caller has already verified the header is a leaf.
fn parse_leaf_entries(node: &[u8], header: &ExtentHeader) -> Result<Vec<Extent>> {
    let mut out = Vec::with_capacity(header.entries as usize);
    for i in 0..header.entries {
        let off = extent_entry_offset(i as usize);
        if off + EXT4_EXT_NODE_SIZE > node.len() {
            return Err(Error::CorruptExtentTree("leaf entry out of range"));
        }
        out.push(Extent::parse(&node[off..off + EXT4_EXT_NODE_SIZE])?);
    }
    Ok(out)
}

/// Read every index entry from an internal node body. Caller has already
/// verified the header is non-leaf.
fn parse_index_entries(node: &[u8], header: &ExtentHeader) -> Result<Vec<ExtentIdx>> {
    let mut out = Vec::with_capacity(header.entries as usize);
    for i in 0..header.entries {
        let off = extent_entry_offset(i as usize);
        if off + EXT4_EXT_NODE_SIZE > node.len() {
            return Err(Error::CorruptExtentTree("index entry out of range"));
        }
        out.push(ExtentIdx::parse(&node[off..off + EXT4_EXT_NODE_SIZE])?);
    }
    Ok(out)
}

/// Capacity (in entries) of a non-root leaf or index block. The trailing
/// 4-byte tail is always reserved — every consumer that uses this code path
/// is on a metadata_csum volume in practice, and reserving the slot when it
/// isn't strictly needed costs nothing on layout.
fn node_max_entries(block_size: usize) -> u16 {
    ((block_size - EXT4_EXT_NODE_SIZE - 4) / EXT4_EXT_NODE_SIZE) as u16
}

/// Build a leaf block (full `block_size` bytes) from the given entries. Last
/// 4 bytes are zeroed and reserved for the caller to patch with the
/// extent_tail CRC.
fn build_full_leaf_block(generation: u32, extents: &[Extent], block_size: usize) -> Vec<u8> {
    let mut out = vec![0u8; block_size];
    let max = node_max_entries(block_size);
    out[EXT4_EXT_HDR_MAGIC_OFF..EXT4_EXT_HDR_MAGIC_OFF + 2]
        .copy_from_slice(&EXT4_EXT_MAGIC.to_le_bytes());
    out[EXT4_EXT_HDR_ENTRIES_OFF..EXT4_EXT_HDR_ENTRIES_OFF + 2]
        .copy_from_slice(&(extents.len() as u16).to_le_bytes());
    out[EXT4_EXT_HDR_MAX_OFF..EXT4_EXT_HDR_MAX_OFF + 2].copy_from_slice(&max.to_le_bytes());
    out[EXT4_EXT_HDR_DEPTH_OFF..EXT4_EXT_HDR_DEPTH_OFF + 2].copy_from_slice(&0u16.to_le_bytes());
    out[EXT4_EXT_HDR_GEN_OFF..EXT4_EXT_HDR_GEN_OFF + 4].copy_from_slice(&generation.to_le_bytes());
    for (i, e) in extents.iter().enumerate() {
        let off = extent_entry_offset(i);
        out[off..off + EXT4_EXT_NODE_SIZE].copy_from_slice(&encode_extent(e));
    }
    out
}

/// Build a non-root index block (full `block_size` bytes) at the given
/// depth. Last 4 bytes are zeroed and reserved for the extent_tail CRC.
fn build_full_index_block(
    generation: u32,
    depth: u16,
    indices: &[(u32, u64)],
    block_size: usize,
) -> Vec<u8> {
    let mut out = vec![0u8; block_size];
    let max = node_max_entries(block_size);
    out[EXT4_EXT_HDR_MAGIC_OFF..EXT4_EXT_HDR_MAGIC_OFF + 2]
        .copy_from_slice(&EXT4_EXT_MAGIC.to_le_bytes());
    out[EXT4_EXT_HDR_ENTRIES_OFF..EXT4_EXT_HDR_ENTRIES_OFF + 2]
        .copy_from_slice(&(indices.len() as u16).to_le_bytes());
    out[EXT4_EXT_HDR_MAX_OFF..EXT4_EXT_HDR_MAX_OFF + 2].copy_from_slice(&max.to_le_bytes());
    out[EXT4_EXT_HDR_DEPTH_OFF..EXT4_EXT_HDR_DEPTH_OFF + 2].copy_from_slice(&depth.to_le_bytes());
    out[EXT4_EXT_HDR_GEN_OFF..EXT4_EXT_HDR_GEN_OFF + 4].copy_from_slice(&generation.to_le_bytes());
    for (i, (logical, child)) in indices.iter().enumerate() {
        let off = extent_entry_offset(i);
        out[off..off + EXT4_EXT_NODE_SIZE].copy_from_slice(&encode_index(*logical, *child));
    }
    out
}

/// Build the 60-byte inline root for an index node at the given depth.
fn build_inline_index_root(generation: u32, depth: u16, indices: &[(u32, u64)]) -> Vec<u8> {
    let mut out = vec![0u8; 60];
    out[EXT4_EXT_HDR_MAGIC_OFF..EXT4_EXT_HDR_MAGIC_OFF + 2]
        .copy_from_slice(&EXT4_EXT_MAGIC.to_le_bytes());
    out[EXT4_EXT_HDR_ENTRIES_OFF..EXT4_EXT_HDR_ENTRIES_OFF + 2]
        .copy_from_slice(&(indices.len() as u16).to_le_bytes());
    out[EXT4_EXT_HDR_MAX_OFF..EXT4_EXT_HDR_MAX_OFF + 2].copy_from_slice(&4u16.to_le_bytes()); // max=4 (inline root)
    out[EXT4_EXT_HDR_DEPTH_OFF..EXT4_EXT_HDR_DEPTH_OFF + 2].copy_from_slice(&depth.to_le_bytes());
    out[EXT4_EXT_HDR_GEN_OFF..EXT4_EXT_HDR_GEN_OFF + 4].copy_from_slice(&generation.to_le_bytes());
    for (i, (logical, child)) in indices.iter().enumerate() {
        let off = extent_entry_offset(i);
        out[off..off + EXT4_EXT_NODE_SIZE].copy_from_slice(&encode_index(*logical, *child));
    }
    out
}

/// Build the 60-byte inline root for a leaf node (depth 0).
fn build_inline_leaf_root(generation: u32, extents: &[Extent]) -> Vec<u8> {
    let header = ExtentHeader {
        magic: EXT4_EXT_MAGIC,
        entries: extents.len() as u16,
        max: 4,
        depth: 0,
        generation,
    };
    build_root(&header, extents, 60)
}

/// An extent tree laid out again over blocks the file already owns.
pub struct RepackedTree {
    /// The 60 bytes for the inode's `i_block`.
    pub new_root: Vec<u8>,
    /// Blocks to write, and what to write into them. The tail checksum is
    /// the caller's, as everywhere else here.
    pub block_writes: Vec<(u64, Vec<u8>)>,
    /// The blocks from `nodes` that the layout used, in the order it used
    /// them. Everything else in `nodes` is now unreferenced.
    pub used_nodes: Vec<u64>,
    /// Blocks `alloc` handed out, when the file's own were not enough. The
    /// caller accounts for them as it does for any allocation.
    pub allocated_blocks: Vec<u64>,
}

/// Lay `entries` out again as a tree over `nodes`, packing every node full.
///
/// This is what a punch needs. The survivors of a punch are a subset of the
/// entries the tree already held, so packing them takes no more nodes than
/// the tree already has, and the blocks it does not use go back to free
/// space. Nothing is allocated: a punch frees, and an allocation inside it
/// would be a second thing that can fail.
///
/// Four or fewer entries need no nodes at all — they go in the inode, which
/// is the case the punch path handled before (#258).
///
/// `alloc` covers the case where they are not enough. A punch inside one
/// extent leaves a head and a tail where there was one record, so the
/// survivors can outnumber the entries by one — and since this packs every
/// node full, a tree it laid out before has no spare room for that one. It is
/// called only then, and only for as many blocks as the layout is short.
///
/// # Errors
///
/// Whatever `alloc` returns when the layout needs a block the file does not
/// already hold.
pub fn plan_repack_tree(
    generation: u32,
    entries: &[Extent],
    block_size: u32,
    nodes: &[u64],
    alloc: &mut dyn FnMut() -> Result<u64>,
) -> Result<RepackedTree> {
    let bs = block_size as usize;
    let mut used_nodes: Vec<u64> = Vec::new();
    let mut allocated_blocks: Vec<u64> = Vec::new();
    let mut block_writes: Vec<(u64, Vec<u8>)> = Vec::new();

    if entries.len() <= 4 {
        return Ok(RepackedTree {
            new_root: build_inline_leaf_root(generation, entries),
            block_writes,
            used_nodes,
            allocated_blocks,
        });
    }

    let mut supply = nodes.iter().copied();
    let mut take = |used: &mut Vec<u64>, fresh: &mut Vec<u64>| -> Result<u64> {
        match supply.next() {
            Some(block) => {
                used.push(block);
                Ok(block)
            }
            None => {
                let block = alloc()?;
                fresh.push(block);
                Ok(block)
            }
        }
    };

    let cap = node_max_entries(bs) as usize;

    // The leaves, each packed full, and the index entries naming them.
    let mut indices: Vec<(u32, u64)> = Vec::new();
    for chunk in entries.chunks(cap) {
        let block = take(&mut used_nodes, &mut allocated_blocks)?;
        block_writes.push((block, build_full_leaf_block(generation, chunk, bs)));
        indices.push((chunk[0].logical_block, block));
    }

    // Index levels, until what is left fits the inode's four entries.
    let mut depth = 1u16;
    while indices.len() > 4 {
        let mut above: Vec<(u32, u64)> = Vec::new();
        for chunk in indices.chunks(cap) {
            let block = take(&mut used_nodes, &mut allocated_blocks)?;
            block_writes.push((block, build_full_index_block(generation, depth, chunk, bs)));
            above.push((chunk[0].0, block));
        }
        indices = above;
        depth += 1;
    }

    Ok(RepackedTree {
        new_root: build_inline_index_root(generation, depth, &indices),
        block_writes,
        used_nodes,
        allocated_blocks,
    })
}

/// Reject any insert whose logical range overlaps an existing leaf entry.
fn check_no_overlap(entries: &[Extent], new: &Extent) -> Result<()> {
    let n_start = new.logical_block as u64;
    let n_end = n_start + new.length as u64;
    for e in entries {
        let e_start = e.logical_block as u64;
        let e_end = e_start + e.length as u64;
        if !(n_end <= e_start || n_start >= e_end) {
            return Err(Error::CorruptExtentTree("extent overlaps existing"));
        }
    }
    Ok(())
}

/// Insert `new` into `entries` (sorted by `logical_block`) and auto-merge
/// with neighbours when contiguous. Mirrors `plan_insert_extent`'s logic but
/// works on a generic vector rather than the inline root.
fn insert_into_leaf_sorted(entries: &mut Vec<Extent>, new: Extent) {
    let pos = entries
        .iter()
        .position(|e| e.logical_block as u64 > new.logical_block as u64)
        .unwrap_or(entries.len());
    entries.insert(pos, new);
    if pos > 0 && are_contiguous(&entries[pos - 1], &entries[pos]) {
        let right = entries.remove(pos);
        entries[pos - 1].length += right.length;
    }
    // Recompute the merged-into position to consider a right merge.
    let merged_pos = entries
        .iter()
        .position(|e| {
            e.logical_block == new.logical_block
                || ((e.logical_block as u64) < new.logical_block as u64
                    && (e.logical_block as u64 + e.length as u64) > new.logical_block as u64)
        })
        .unwrap_or(entries.len().saturating_sub(1));
    if merged_pos + 1 < entries.len()
        && are_contiguous(&entries[merged_pos], &entries[merged_pos + 1])
    {
        let right = entries.remove(merged_pos + 1);
        entries[merged_pos].length += right.length;
    }
}

/// Insert a new index entry in sorted-by-logical_block order.
fn insert_into_index_sorted(entries: &mut Vec<(u32, u64)>, new_logical: u32, new_child: u64) {
    let pos = entries
        .iter()
        .position(|(l, _)| *l > new_logical)
        .unwrap_or(entries.len());
    entries.insert(pos, (new_logical, new_child));
}

/// State carried up the tree during split propagation. When `Some`, the
/// parent must absorb a new index entry pointing at the freshly-split-off
/// sibling.
struct PropagatedSplit {
    /// First logical block in the new sibling subtree.
    new_logical: u32,
    /// Block number of the new sibling node.
    new_child: u64,
}

/// Walk the tree from the root to the leaf that should hold `target_logical`.
/// Returns the descent path with one frame per level (root first, leaf last).
fn descend_to_leaf(
    root_bytes: &[u8],
    target_logical: u32,
    block_size: u32,
    reader: &dyn DeepReader,
) -> Result<Vec<PathFrame>> {
    let root_header = ExtentHeader::parse(root_bytes)?;
    if root_header.depth > EXT4_EXT_MAX_DEPTH {
        return Err(Error::CorruptExtentTree(
            "extent tree depth exceeds spec maximum",
        ));
    }
    let mut path = Vec::with_capacity(root_header.depth as usize + 1);
    path.push(PathFrame {
        block: 0,
        bytes: root_bytes.to_vec(),
    });

    loop {
        let frame = path.last().unwrap();
        let header = ExtentHeader::parse(&frame.bytes)?;
        if header.is_leaf() {
            return Ok(path);
        }
        if header.entries == 0 {
            return Err(Error::CorruptExtentTree(
                "internal node with zero index entries",
            ));
        }
        // Find largest index entry whose ei_block <= target_logical (mirrors
        // the read-side descent in extent::lookup_verified).
        //
        // `ExtentHeader::parse` bounds `entries` by `max` but nothing bounds
        // `max` by the node, so every entry is range-checked here: a root
        // claiming five index entries in its four-entry area, or a child
        // block claiming more than the block holds, is corrupt (#327).
        let entries = parse_index_entries(&frame.bytes, &header)?;
        let chosen_idx = entries
            .iter()
            .take_while(|idx| idx.logical_block <= target_logical)
            .last();
        // If target is below the smallest index entry, descend into the
        // first child (the new extent will sort into the leftmost subtree).
        let idx = *chosen_idx.unwrap_or(&entries[0]);
        let mut child_buf = vec![0u8; block_size as usize];
        reader.read_block(idx.leaf_block, &mut child_buf)?;
        path.push(PathFrame {
            block: idx.leaf_block,
            bytes: child_buf,
        });
    }
}

/// Insert `new` into the extent tree rooted at `root_bytes` (60 bytes from
/// the inode's `i_block`), descending through internal nodes as needed,
/// splitting full nodes, and promoting the root if the inline area can no
/// longer hold the post-split index entries.
///
/// `block_size` must match the volume's filesystem block size.
///
/// `reader` provides the bytes of any internal/leaf block we walk through on
/// the way down. `alloc` is called once per freshly-needed block; the caller
/// is responsible for marking each result used in the bitmap (and bumping
/// BGD/SB counters) inside the same transaction as the inode write.
///
/// Caps the post-insert tree depth at [`EXT4_EXT_MAX_DEPTH`]. Beyond that
/// returns [`Error::CorruptExtentTree`].
pub fn plan_insert_extent_deep(
    root_bytes: &[u8],
    new: Extent,
    block_size: u32,
    reader: &dyn DeepReader,
    alloc: &mut dyn FnMut() -> Result<u64>,
) -> Result<DeepInsertPlan> {
    if root_bytes.len() < 12 {
        return Err(Error::CorruptExtentTree("root buffer too small"));
    }
    let bs = block_size as usize;
    let root_header = ExtentHeader::parse(root_bytes)?;
    let generation = root_header.generation;

    // Descend to the leaf that should hold `new`.
    let mut path = descend_to_leaf(root_bytes, new.logical_block, block_size, reader)?;

    let mut block_writes: Vec<(u64, Vec<u8>)> = Vec::new();
    let mut allocated_blocks: Vec<u64> = Vec::new();

    // ---- Leaf level ----
    let leaf_frame = path.pop().unwrap();
    let leaf_header = ExtentHeader::parse(&leaf_frame.bytes)?;
    debug_assert!(leaf_header.is_leaf());
    let mut leaf_entries = parse_leaf_entries(&leaf_frame.bytes, &leaf_header)?;
    check_no_overlap(&leaf_entries, &new)?;
    // THE KEY A PARENT HOLDS FOR THIS LEAF, which is the leaf's first
    // logical block. An insert in front of everything moves it, and a parent
    // still naming the old one describes a tree e2fsck rejects:
    // "Logical start N does not match logical start M at next level" (#260).
    // Each index key must equal the first logical block of the subtree it
    // points at, so every ancestor's key is corrected here.
    let first_key_before = leaf_entries.first().map(|e| e.logical_block);
    insert_into_leaf_sorted(&mut leaf_entries, new);

    // Capacity for this leaf depends on whether it's the inline root or a
    // full block. The inline root holds up to 4 entries (no tail); a full
    // block holds up to `node_max_entries(bs)` entries (with tail reserved).
    let is_root_leaf = path.is_empty();
    let leaf_cap = if is_root_leaf {
        4
    } else {
        node_max_entries(bs)
    };

    // `propagated` carries the (logical, block) tuple of the split-off
    // sibling that the next-higher level must absorb as a new index entry.
    // Initially set by the leaf-split branch below; replaced by the in-loop
    // split branch each time a non-root index node also overflows.
    let mut propagated: Option<PropagatedSplit>;
    // `(child block, its new first key)`, while a parent still names the old
    // one.
    let mut correction: Option<(u64, u32)> = None;

    if (leaf_entries.len() as u16) <= leaf_cap {
        // Leaf fits — emit it.
        if is_root_leaf {
            // Root + leaf: rewrite the inline root and we're done.
            let new_root = build_inline_leaf_root(generation, &leaf_entries);
            return Ok(DeepInsertPlan {
                new_root,
                block_writes,
                allocated_blocks,
            });
        }
        let new_leaf = build_full_leaf_block(generation, &leaf_entries, bs);
        block_writes.push((leaf_frame.block, new_leaf));
        let first_key = leaf_entries[0].logical_block;
        if first_key_before == Some(first_key) {
            // Every level above is unchanged, so the inline root bytes go
            // back verbatim.
            return Ok(DeepInsertPlan {
                new_root: root_bytes.to_vec(),
                block_writes,
                allocated_blocks,
            });
        }
        // The leaf's first key moved, so the keys naming it have to follow.
        propagated = None;
        correction = Some((leaf_frame.block, first_key));
    } else {
        // Leaf overflowed — split it 50/50.
        if is_root_leaf {
            // Special case: inline root is a leaf and overflowed. Promote to
            // depth 1 by allocating a single block and dumping all entries
            // there, then rewriting the root with a single index entry.
            // (This mirrors `plan_promote_leaf`, inlined so we control the
            // alloc + write emission.)
            let new_leaf_block = alloc()?;
            allocated_blocks.push(new_leaf_block);
            let new_leaf_bytes = build_full_leaf_block(generation, &leaf_entries, bs);
            block_writes.push((new_leaf_block, new_leaf_bytes));
            let new_root = build_inline_index_root(
                generation,
                1,
                &[(leaf_entries[0].logical_block, new_leaf_block)],
            );
            return Ok(DeepInsertPlan {
                new_root,
                block_writes,
                allocated_blocks,
            });
        }
        // Non-root leaf split.
        let mid = leaf_entries.len() / 2;
        let right_entries: Vec<Extent> = leaf_entries.split_off(mid);
        let left_entries = leaf_entries;
        let right_first_logical = right_entries[0].logical_block;
        let new_right_block = alloc()?;
        allocated_blocks.push(new_right_block);

        let left_bytes = build_full_leaf_block(generation, &left_entries, bs);
        let right_bytes = build_full_leaf_block(generation, &right_entries, bs);
        block_writes.push((leaf_frame.block, left_bytes));
        block_writes.push((new_right_block, right_bytes));

        propagated = Some(PropagatedSplit {
            new_logical: right_first_logical,
            new_child: new_right_block,
        });
        let left_first = left_entries[0].logical_block;
        if first_key_before != Some(left_first) {
            correction = Some((leaf_frame.block, left_first));
        }
    }

    // ---- Walk up internal levels, absorbing the propagated split. ----
    // Invariant: at the top of every loop iteration, `propagated` is Some —
    // a level absorbs without overflow (sets propagated=None) only on a
    // path that returns immediately, since every higher level is unchanged.
    while let Some(frame) = path.pop() {
        let header = ExtentHeader::parse(&frame.bytes)?;
        debug_assert!(!header.is_leaf());
        let mut indices: Vec<(u32, u64)> = parse_index_entries(&frame.bytes, &header)?
            .into_iter()
            .map(|i| (i.logical_block, i.leaf_block))
            .collect();

        // A child whose first key moved is named here; correct it, and pass
        // the correction on only while it is this node's own first key,
        // which is what the node above holds for it.
        if let Some((child, key)) = correction.take() {
            let at = indices
                .iter()
                .position(|(_, block)| *block == child)
                .ok_or(Error::CorruptExtentTree(
                    "the index entry naming a child this insert changed is missing",
                ))?;
            indices[at].0 = key;
            if at == 0 && frame.block != 0 {
                correction = Some((frame.block, key));
            }
        }

        if let Some(split) = propagated.take() {
            insert_into_index_sorted(&mut indices, split.new_logical, split.new_child);
        }

        let is_root_here = path.is_empty();
        let cap = if is_root_here {
            4
        } else {
            node_max_entries(bs)
        };

        if (indices.len() as u16) <= cap {
            if is_root_here {
                let new_root = build_inline_index_root(generation, header.depth, &indices);
                return Ok(DeepInsertPlan {
                    new_root,
                    block_writes,
                    allocated_blocks,
                });
            }
            let bytes = build_full_index_block(generation, header.depth, &indices, bs);
            block_writes.push((frame.block, bytes));
            if correction.is_some() {
                // This node is written, but the key naming it above moved
                // too, so the level above still has to be rewritten.
                continue;
            }
            // No more propagation — every level above this is unchanged, so
            // the inline root bytes can be returned verbatim.
            return Ok(DeepInsertPlan {
                new_root: root_bytes.to_vec(),
                block_writes,
                allocated_blocks,
            });
        } else {
            // Index overflow.
            if is_root_here {
                // Root promotion: allocate two new index blocks, split the
                // index entries 50/50 between them, rewrite the inline root
                // as depth+1 with two index entries.
                let new_depth = header.depth + 1;
                if new_depth > EXT4_EXT_MAX_DEPTH {
                    return Err(Error::CorruptExtentTree(
                        "extent tree depth would exceed spec maximum",
                    ));
                }
                let mid = indices.len() / 2;
                let right_indices: Vec<(u32, u64)> = indices.split_off(mid);
                let left_indices = indices;
                let left_first = left_indices[0].0;
                let right_first = right_indices[0].0;
                let left_block = alloc()?;
                allocated_blocks.push(left_block);
                let right_block = alloc()?;
                allocated_blocks.push(right_block);
                let left_bytes =
                    build_full_index_block(generation, header.depth, &left_indices, bs);
                let right_bytes =
                    build_full_index_block(generation, header.depth, &right_indices, bs);
                block_writes.push((left_block, left_bytes));
                block_writes.push((right_block, right_bytes));
                let new_root = build_inline_index_root(
                    generation,
                    new_depth,
                    &[(left_first, left_block), (right_first, right_block)],
                );
                return Ok(DeepInsertPlan {
                    new_root,
                    block_writes,
                    allocated_blocks,
                });
            }
            // Non-root index split.
            let mid = indices.len() / 2;
            let right_indices: Vec<(u32, u64)> = indices.split_off(mid);
            let left_indices = indices;
            let right_first = right_indices[0].0;
            let new_right_block = alloc()?;
            allocated_blocks.push(new_right_block);
            let left_bytes = build_full_index_block(generation, header.depth, &left_indices, bs);
            let right_bytes = build_full_index_block(generation, header.depth, &right_indices, bs);
            block_writes.push((frame.block, left_bytes));
            block_writes.push((new_right_block, right_bytes));
            propagated = Some(PropagatedSplit {
                new_logical: right_first,
                new_child: new_right_block,
            });
        }
    }

    // The loop only exits when every level absorbed without spilling to the
    // root, but in that case we already returned from inside the loop. If
    // execution reaches here the invariant above is broken — surface as a
    // logic bug rather than silently producing the wrong tree.
    Err(Error::CorruptExtentTree(
        "deep insert: unexpected path exhaustion",
    ))
}

/// Plan a split of `entries[idx]` at logical block `split_at` — the entry is
/// replaced by two halves [`start..split_at`, `split_at..end`]. The caller
/// uses this when partially overwriting, freeing a middle run, or converting
/// uninit→init on a sub-range.
///
/// Errors if `split_at` is not strictly inside the chosen extent.
pub fn plan_split_extent(root: &[u8], idx: usize, split_at: u32) -> Result<Vec<ExtentMutation>> {
    let (header, mut entries) = read_leaf_entries(root)?;
    let e = *entries
        .get(idx)
        .ok_or(Error::CorruptExtentTree("split idx out of range"))?;
    let start = e.logical_block;
    let end = start + e.length as u32;
    if split_at <= start || split_at >= end {
        return Err(Error::CorruptExtentTree("split point outside extent"));
    }
    let left = Extent {
        logical_block: start,
        length: (split_at - start) as u16,
        physical_block: e.physical_block,
        uninitialized: e.uninitialized,
    };
    let right = Extent {
        logical_block: split_at,
        length: (end - split_at) as u16,
        physical_block: e.physical_block + (split_at - start) as u64,
        uninitialized: e.uninitialized,
    };
    entries[idx] = left;
    entries.insert(idx + 1, right);

    if entries.len() as u16 > header.max {
        return Err(Error::CorruptExtentTree(
            "LEAF_FULL_NEEDS_PROMOTION: split exceeds root capacity",
        ));
    }

    let new_root = build_root(&header, &entries, root.len());
    Ok(vec![ExtentMutation::WriteRoot { bytes: new_root }])
}

/// Plan fusing entries[i] and entries[i+1] when they're physically adjacent
/// and in the same uninit state. No-op (returns empty mutation list) if the
/// pair isn't contiguous.
pub fn plan_merge_adjacent(root: &[u8], i: usize) -> Result<Vec<ExtentMutation>> {
    let (header, mut entries) = read_leaf_entries(root)?;
    if i + 1 >= entries.len() {
        return Err(Error::CorruptExtentTree("merge idx out of range"));
    }
    if !are_contiguous(&entries[i], &entries[i + 1]) {
        return Ok(Vec::new());
    }
    let right = entries.remove(i + 1);
    entries[i].length += right.length;
    let new_root = build_root(&header, &entries, root.len());
    Ok(vec![ExtentMutation::WriteRoot { bytes: new_root }])
}

/// Plan removal of `entries[idx]`: drops the entry from the root and emits a
/// [`ExtentMutation::FreePhysicalRun`] so the caller can free the backing
/// blocks via the bitmap allocator (E5).
pub fn plan_free_extent(root: &[u8], idx: usize) -> Result<Vec<ExtentMutation>> {
    let (header, mut entries) = read_leaf_entries(root)?;
    let removed = entries
        .get(idx)
        .copied()
        .ok_or(Error::CorruptExtentTree("free idx out of range"))?;
    entries.remove(idx);
    let new_root = build_root(&header, &entries, root.len());
    Ok(vec![
        ExtentMutation::WriteRoot { bytes: new_root },
        ExtentMutation::FreePhysicalRun {
            start: removed.physical_block,
            len: removed.length as u32,
        },
    ])
}

/// Plan marking logical blocks `[first, end)` initialized in an inline-root
/// leaf, wherever an uninitialized extent covers them.
///
/// Each uninitialized extent the range touches is split into at most three:
/// an uninitialized head, the initialized middle and an uninitialized tail.
/// A piece contiguous with its neighbour in the same state is merged back.
/// Returns the new root and the logical blocks that changed state. Those
/// blocks read as zeros until now, and their physical contents are whatever
/// was there, so the caller has to write every byte of them.
///
/// Errors:
/// - `multi-level tree mutation not yet supported` on a root that isn't a leaf;
/// - `LEAF_FULL_NEEDS_PROMOTION` if the pieces don't fit in the root.
pub fn plan_initialize_range(root: &[u8], first: u32, end: u32) -> Result<(Vec<u8>, Vec<u32>)> {
    let (header, entries) = read_leaf_entries(root)?;
    let mut out: Vec<Extent> = Vec::with_capacity(entries.len() + 2);
    let mut converted = Vec::new();
    for e in entries {
        let el = e.logical_block;
        let er = el + u32::from(e.length);
        if !e.uninitialized || er <= first || el >= end {
            out.push(e);
            continue;
        }
        let lo = el.max(first);
        let hi = er.min(end);
        let piece = |from: u32, to: u32, uninitialized: bool| Extent {
            logical_block: from,
            length: (to - from) as u16,
            physical_block: e.physical_block + u64::from(from - el),
            uninitialized,
        };
        if el < lo {
            out.push(piece(el, lo, true));
        }
        out.push(piece(lo, hi, false));
        if hi < er {
            out.push(piece(hi, er, true));
        }
        converted.extend(lo..hi);
    }
    let mut merged: Vec<Extent> = Vec::with_capacity(out.len());
    for e in out {
        match merged.last_mut() {
            Some(prev) if are_contiguous(prev, &e) => prev.length += e.length,
            _ => merged.push(e),
        }
    }
    if merged.len() as u16 > header.max {
        return Err(Error::CorruptExtentTree(
            "LEAF_FULL_NEEDS_PROMOTION: initializing part of an extent exceeds root capacity",
        ));
    }
    let header = ExtentHeader {
        entries: merged.len() as u16,
        ..header
    };
    Ok((build_root(&header, &merged, root.len()), converted))
}

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

    /// Build an inline root (60 bytes) for a leaf with the given extents.
    fn mk_root(extents: &[Extent]) -> Vec<u8> {
        let header = ExtentHeader {
            magic: EXT4_EXT_MAGIC,
            entries: extents.len() as u16,
            max: 4,
            depth: 0,
            generation: 0,
        };
        build_root(&header, extents, 60)
    }

    fn ext(log: u32, len: u16, phys: u64, uninit: bool) -> Extent {
        Extent {
            logical_block: log,
            length: len,
            physical_block: phys,
            uninitialized: uninit,
        }
    }

    /// `n` single-block extents, one every other block.
    fn striped(n: u32) -> Vec<Extent> {
        (0..n)
            .map(|i| ext(i * 2, 1, 1000 + i as u64, false))
            .collect()
    }

    /// The layout uses the file's own blocks, and packs every node full.
    #[test]
    fn a_repack_uses_the_blocks_the_file_already_holds() {
        let bs = 1024u32;
        let cap = node_max_entries(bs as usize) as usize;
        let entries = striped(3 * cap as u32);
        let nodes: Vec<u64> = (5000..5100).collect();
        let mut refused = || {
            Err(Error::CorruptExtentTree(
                "a repack of these must not allocate",
            ))
        };
        let plan = plan_repack_tree(7, &entries, bs, &nodes, &mut refused).expect("repack");

        assert_eq!(plan.allocated_blocks, Vec::<u64>::new());
        assert_eq!(
            plan.used_nodes,
            nodes[..3],
            "three full leaves, nothing more"
        );
        assert_eq!(plan.block_writes.len(), 3);
        let root = ExtentHeader::parse(&plan.new_root).expect("root");
        assert_eq!((root.depth, root.entries), (1, 3));
    }

    /// Four or fewer survivors go in the inode, and the file's blocks are
    /// all left over for the caller to free.
    #[test]
    fn a_repack_of_four_entries_needs_no_blocks() {
        let entries = striped(4);
        let nodes = [5000u64, 5001];
        let mut refused = || Err(Error::CorruptExtentTree("must not allocate"));
        let plan = plan_repack_tree(7, &entries, 1024, &nodes, &mut refused).expect("repack");

        assert!(plan.used_nodes.is_empty() && plan.block_writes.is_empty());
        let root = ExtentHeader::parse(&plan.new_root).expect("root");
        assert_eq!((root.depth, root.entries), (0, 4));
    }

    /// A punch inside one extent leaves a head and a tail where there was one
    /// record, so the survivors can outnumber the entries — and a tree this
    /// packed full has no room for the extra. The layout then allocates, and
    /// only for what it is short (CodeRabbit on #262).
    #[test]
    fn a_repack_allocates_only_what_the_file_cannot_cover() {
        let bs = 1024u32;
        let cap = node_max_entries(bs as usize) as usize;
        // A full root over full leaves: four leaves, each packed.
        let entries = striped((4 * cap + 1) as u32);
        let nodes: Vec<u64> = (5000..5004).collect();
        let mut next = 9000u64;
        let mut alloc = || {
            next += 1;
            Ok(next)
        };
        let plan = plan_repack_tree(7, &entries, bs, &nodes, &mut alloc).expect("repack");

        // Five leaves for the extra entry, and an index level over them,
        // because five index entries do not fit the inode's four.
        assert_eq!(
            plan.used_nodes, nodes,
            "every block the file held is reused"
        );
        assert_eq!(plan.allocated_blocks, vec![9001, 9002]);
        assert_eq!(plan.block_writes.len(), 6);
        let root = ExtentHeader::parse(&plan.new_root).expect("root");
        assert_eq!((root.depth, root.entries), (2, 1));
    }

    fn read_back(bytes: &[u8]) -> Vec<Extent> {
        read_leaf_entries(bytes).unwrap().1
    }

    fn shape(extents: Vec<Extent>) -> Vec<(u32, u16, u64, bool)> {
        extents
            .iter()
            .map(|e| (e.logical_block, e.length, e.physical_block, e.uninitialized))
            .collect()
    }

    #[test]
    fn initializing_the_middle_of_an_uninit_extent_splits_it_in_three() {
        let root = mk_root(&[ext(0, 16, 1000, true)]);
        let (bytes, converted) = plan_initialize_range(&root, 4, 6).unwrap();
        assert_eq!(converted, vec![4, 5]);
        assert_eq!(
            shape(read_back(&bytes)),
            vec![(0, 4, 1000, true), (4, 2, 1004, false), (6, 10, 1006, true)]
        );
    }

    #[test]
    fn initializing_all_of_an_uninit_extent_merges_with_an_initialized_neighbour() {
        let root = mk_root(&[ext(0, 4, 1000, false), ext(4, 4, 1004, true)]);
        let (bytes, converted) = plan_initialize_range(&root, 4, 20).unwrap();
        assert_eq!(converted, vec![4, 5, 6, 7]);
        assert_eq!(shape(read_back(&bytes)), vec![(0, 8, 1000, false)]);
    }

    #[test]
    fn initialized_extents_and_ranges_outside_are_left_alone() {
        let root = mk_root(&[ext(0, 4, 1000, false), ext(10, 4, 2000, true)]);
        let (bytes, converted) = plan_initialize_range(&root, 0, 10).unwrap();
        assert!(converted.is_empty());
        assert_eq!(shape(read_back(&bytes)), shape(read_back(&root)));
    }

    #[test]
    fn initializing_that_overflows_the_root_is_refused() {
        let root = mk_root(&[
            ext(0, 16, 1000, true),
            ext(20, 1, 3000, false),
            ext(30, 1, 4000, false),
        ]);
        let err = plan_initialize_range(&root, 4, 6).unwrap_err();
        assert!(
            format!("{err:?}").contains("LEAF_FULL_NEEDS_PROMOTION"),
            "{err:?}"
        );
    }

    #[test]
    fn insert_into_empty_root() {
        let root = mk_root(&[]);
        let muts = plan_insert_extent(&root, ext(0, 10, 1000, false)).unwrap();
        assert_eq!(muts.len(), 1);
        let ExtentMutation::WriteRoot { bytes } = &muts[0] else {
            panic!("expected WriteRoot");
        };
        let back = read_back(bytes);
        assert_eq!(back.len(), 1);
        assert_eq!(back[0].logical_block, 0);
        assert_eq!(back[0].length, 10);
    }

    #[test]
    fn insert_sorted_ordering() {
        let root = mk_root(&[ext(100, 5, 2000, false)]);
        let muts = plan_insert_extent(&root, ext(0, 10, 1000, false)).unwrap();
        let ExtentMutation::WriteRoot { bytes } = &muts[0] else {
            panic!()
        };
        let back = read_back(bytes);
        assert_eq!(back[0].logical_block, 0);
        assert_eq!(back[1].logical_block, 100);
    }

    #[test]
    fn insert_merges_left_contiguous() {
        let root = mk_root(&[ext(0, 10, 1000, false)]);
        // New extent at logical 10, phys 1010 — contiguous with the first.
        let muts = plan_insert_extent(&root, ext(10, 5, 1010, false)).unwrap();
        let ExtentMutation::WriteRoot { bytes } = &muts[0] else {
            panic!()
        };
        let back = read_back(bytes);
        assert_eq!(back.len(), 1, "should merge into single extent");
        assert_eq!(back[0].length, 15);
    }

    #[test]
    fn insert_does_not_merge_across_uninit_boundary() {
        let root = mk_root(&[ext(0, 10, 1000, false)]);
        // Contiguous physically/logically but marked uninitialised — must NOT merge.
        let muts = plan_insert_extent(&root, ext(10, 5, 1010, true)).unwrap();
        let ExtentMutation::WriteRoot { bytes } = &muts[0] else {
            panic!()
        };
        let back = read_back(bytes);
        assert_eq!(back.len(), 2);
        assert!(!back[0].uninitialized);
        assert!(back[1].uninitialized);
    }

    #[test]
    fn insert_rejects_overlap() {
        let root = mk_root(&[ext(0, 10, 1000, false)]);
        let err = plan_insert_extent(&root, ext(5, 5, 2000, false)).unwrap_err();
        match err {
            Error::CorruptExtentTree(msg) => assert!(msg.contains("overlaps")),
            _ => panic!("wrong error kind"),
        }
    }

    #[test]
    fn insert_fails_when_root_full_and_no_merge() {
        let root = mk_root(&[
            ext(0, 5, 1000, false),
            ext(100, 5, 2000, false),
            ext(200, 5, 3000, false),
            ext(300, 5, 4000, false),
        ]);
        let err = plan_insert_extent(&root, ext(500, 5, 5000, false)).unwrap_err();
        match err {
            Error::CorruptExtentTree(msg) => assert!(msg.contains("LEAF_FULL_NEEDS_PROMOTION")),
            _ => panic!("wrong error kind"),
        }
    }

    #[test]
    fn split_extent_at_midpoint() {
        let root = mk_root(&[ext(0, 10, 1000, false)]);
        let muts = plan_split_extent(&root, 0, 4).unwrap();
        let ExtentMutation::WriteRoot { bytes } = &muts[0] else {
            panic!()
        };
        let back = read_back(bytes);
        assert_eq!(back.len(), 2);
        assert_eq!(back[0].logical_block, 0);
        assert_eq!(back[0].length, 4);
        assert_eq!(back[0].physical_block, 1000);
        assert_eq!(back[1].logical_block, 4);
        assert_eq!(back[1].length, 6);
        assert_eq!(back[1].physical_block, 1004);
    }

    #[test]
    fn split_rejects_boundary_point() {
        let root = mk_root(&[ext(0, 10, 1000, false)]);
        assert!(plan_split_extent(&root, 0, 0).is_err()); // start
        assert!(plan_split_extent(&root, 0, 10).is_err()); // end
    }

    #[test]
    fn merge_adjacent_contiguous_pair() {
        let root = mk_root(&[
            ext(0, 5, 1000, false),
            ext(5, 5, 1005, false), // contiguous
        ]);
        let muts = plan_merge_adjacent(&root, 0).unwrap();
        let ExtentMutation::WriteRoot { bytes } = &muts[0] else {
            panic!()
        };
        let back = read_back(bytes);
        assert_eq!(back.len(), 1);
        assert_eq!(back[0].length, 10);
    }

    #[test]
    fn merge_noop_when_not_contiguous() {
        let root = mk_root(&[
            ext(0, 5, 1000, false),
            ext(5, 5, 5000, false), // physically apart
        ]);
        let muts = plan_merge_adjacent(&root, 0).unwrap();
        assert!(muts.is_empty(), "no-op when not contiguous");
    }

    #[test]
    fn free_extent_emits_physical_run() {
        let root = mk_root(&[ext(0, 5, 1000, false), ext(10, 3, 2000, false)]);
        let muts = plan_free_extent(&root, 0).unwrap();
        assert_eq!(muts.len(), 2);
        match &muts[1] {
            ExtentMutation::FreePhysicalRun { start, len } => {
                assert_eq!(*start, 1000);
                assert_eq!(*len, 5);
            }
            _ => panic!("expected FreePhysicalRun"),
        }
        let ExtentMutation::WriteRoot { bytes } = &muts[0] else {
            panic!()
        };
        let back = read_back(bytes);
        assert_eq!(back.len(), 1);
        assert_eq!(back[0].logical_block, 10);
    }

    #[test]
    fn promote_leaf_moves_entries_into_new_leaf_block() {
        let root = mk_root(&[
            ext(0, 5, 1000, false),
            ext(100, 5, 2000, false),
            ext(200, 5, 3000, false),
            ext(300, 5, 4000, false),
        ]);
        let plan = plan_promote_leaf(&root, ext(500, 5, 5000, false), 4096, 900_000, true).unwrap();

        assert_eq!(plan.new_root_bytes.len(), 60);
        let hdr = ExtentHeader::parse(&plan.new_root_bytes).unwrap();
        assert_eq!(hdr.depth, 1);
        assert_eq!(hdr.entries, 1);
        assert_eq!(hdr.max, 4);
        let idx = crate::extent::ExtentIdx::parse(
            &plan.new_root_bytes[EXT4_EXT_NODE_SIZE..2 * EXT4_EXT_NODE_SIZE],
        )
        .unwrap();
        assert_eq!(idx.logical_block, 0);
        assert_eq!(idx.leaf_block, 900_000);

        assert_eq!(plan.leaf_bytes.len(), 4096);
        let leaf_hdr = ExtentHeader::parse(&plan.leaf_bytes).unwrap();
        assert_eq!(leaf_hdr.depth, 0);
        assert_eq!(leaf_hdr.entries, 5);
        let expected_max = ((4096 - 12 - 4) / 12) as u16;
        assert_eq!(leaf_hdr.max, expected_max);
        let parsed = read_back(&plan.leaf_bytes[..12 + 5 * 12]);
        assert_eq!(parsed.len(), 5);
        let logs: Vec<u32> = parsed.iter().map(|e| e.logical_block).collect();
        assert_eq!(logs, vec![0, 100, 200, 300, 500]);
    }

    #[test]
    fn promote_leaf_rejects_overlap() {
        let root = mk_root(&[
            ext(0, 5, 1000, false),
            ext(100, 5, 2000, false),
            ext(200, 5, 3000, false),
            ext(300, 5, 4000, false),
        ]);
        let err = plan_promote_leaf(&root, ext(2, 5, 9000, false), 4096, 500, true).unwrap_err();
        match err {
            Error::CorruptExtentTree(m) => assert!(m.contains("overlaps")),
            _ => panic!("wrong error kind"),
        }
    }

    #[test]
    fn promote_leaf_preserves_generation() {
        let extents = [
            ext(0, 5, 1000, false),
            ext(100, 5, 2000, false),
            ext(200, 5, 3000, false),
            ext(300, 5, 4000, false),
        ];
        let header = ExtentHeader {
            magic: EXT4_EXT_MAGIC,
            entries: 4,
            max: 4,
            depth: 0,
            generation: 0xDEAD_BEEF,
        };
        let root = build_root(&header, &extents, 60);
        let plan = plan_promote_leaf(&root, ext(500, 5, 5000, false), 4096, 777, false).unwrap();
        assert_eq!(
            ExtentHeader::parse(&plan.new_root_bytes)
                .unwrap()
                .generation,
            0xDEAD_BEEF
        );
        assert_eq!(
            ExtentHeader::parse(&plan.leaf_bytes).unwrap().generation,
            0xDEAD_BEEF
        );
    }

    #[test]
    fn promote_leaf_merges_when_contiguous_with_new() {
        let root = mk_root(&[
            ext(0, 5, 1000, false),
            ext(100, 5, 2000, false),
            ext(200, 5, 3000, false),
            ext(300, 5, 4000, false),
        ]);
        let plan = plan_promote_leaf(&root, ext(305, 5, 4005, false), 4096, 123, false).unwrap();
        let leaf_hdr = ExtentHeader::parse(&plan.leaf_bytes).unwrap();
        assert_eq!(leaf_hdr.entries, 4);
        let parsed = read_back(&plan.leaf_bytes[..12 + 4 * 12]);
        assert_eq!(parsed[3].logical_block, 300);
        assert_eq!(parsed[3].length, 10);
    }

    #[test]
    fn multi_level_tree_refused_cleanly() {
        // Synthetic internal-node root (depth=1).
        let mut buf = vec![0u8; 60];
        buf[0..2].copy_from_slice(&EXT4_EXT_MAGIC.to_le_bytes());
        buf[2..4].copy_from_slice(&0u16.to_le_bytes());
        buf[4..6].copy_from_slice(&4u16.to_le_bytes());
        buf[6..8].copy_from_slice(&1u16.to_le_bytes()); // depth=1 → not leaf
        let err = plan_insert_extent(&buf, ext(0, 1, 1000, false)).unwrap_err();
        match err {
            Error::CorruptExtentTree(msg) => assert!(msg.contains("multi-level")),
            _ => panic!("wrong error kind"),
        }
    }

    /// The `WriteRoot` bytes of a single-mutation plan.
    fn root_of(muts: Vec<ExtentMutation>) -> Vec<u8> {
        match muts.into_iter().next() {
            Some(ExtentMutation::WriteRoot { bytes }) => bytes,
            other => panic!("expected WriteRoot, got {other:?}"),
        }
    }

    /// Sum of the lengths, and whether any entry reads back uninitialized.
    fn total_and_any_uninit(entries: &[Extent]) -> (u64, bool) {
        (
            entries.iter().map(|e| e.length as u64).sum(),
            entries.iter().any(|e| e.uninitialized),
        )
    }

    /// Two contiguous initialized extents whose sum passes 32768 stay two
    /// (#387): one `ee_len` over 32768 reads back as an uninitialized extent.
    #[test]
    fn an_insert_does_not_merge_past_the_initialized_extent_limit() {
        let m = plan_insert_extent(
            &mk_root(&[ext(0, 32768, 1000, false)]),
            ext(32768, 1, 33768, false),
        )
        .unwrap();
        let entries = read_back(&root_of(m));
        assert_eq!(
            total_and_any_uninit(&entries),
            (32769, false),
            "{entries:?}"
        );
        assert_eq!(entries.len(), 2, "{entries:?}");
    }

    /// Two contiguous uninit extents whose sum passes 32767 stay two
    /// (#387): the merge used to overflow `ee_len`'s u16.
    #[test]
    fn an_insert_does_not_merge_past_the_uninit_extent_limit() {
        let r = std::panic::catch_unwind(|| {
            plan_insert_extent(
                &mk_root(&[ext(0, 20000, 1000, true)]),
                ext(20000, 20000, 21000, true),
            )
        });
        let entries = read_back(&root_of(r.expect("no panic").unwrap()));
        assert_eq!(total_and_any_uninit(&entries), (40000, true), "{entries:?}");
        assert!(entries.iter().all(|e| e.uninitialized), "{entries:?}");
    }

    /// A merge exactly at the limit still happens: the cap is `<=`.
    #[test]
    fn an_insert_still_merges_up_to_the_limit() {
        let m = plan_insert_extent(
            &mk_root(&[ext(0, 32767, 1000, false)]),
            ext(32767, 1, 33767, false),
        )
        .unwrap();
        let entries = read_back(&root_of(m));
        assert_eq!(shape(entries), vec![(0, 32768, 1000, false)]);
        let m = plan_insert_extent(
            &mk_root(&[ext(0, 32766, 1000, true)]),
            ext(32766, 1, 33766, true),
        )
        .unwrap();
        assert_eq!(shape(read_back(&root_of(m))), vec![(0, 32767, 1000, true)]);
    }

    /// A merge with the right-hand neighbour is capped too.
    #[test]
    fn an_insert_does_not_merge_right_past_the_limit() {
        let m = plan_insert_extent(
            &mk_root(&[ext(1, 32768, 1001, false)]),
            ext(0, 1, 1000, false),
        )
        .unwrap();
        let entries = read_back(&root_of(m));
        assert_eq!(
            total_and_any_uninit(&entries),
            (32769, false),
            "{entries:?}"
        );
    }

    /// `plan_merge_adjacent` refuses a pair whose sum passes the limit.
    #[test]
    fn an_explicit_merge_does_not_pass_the_extent_limit() {
        let root = mk_root(&[ext(0, 30000, 1000, false), ext(30000, 5000, 31000, false)]);
        let m = plan_merge_adjacent(&root, 0).unwrap();
        assert!(m.is_empty(), "a merge past 32768 was planned: {m:?}");
    }

    /// The deep-tree leaf insert (`insert_into_leaf_sorted`) is capped too.
    #[test]
    fn a_deep_leaf_insert_does_not_merge_past_the_extent_limit() {
        let mut entries = vec![ext(0, 30000, 1000, false)];
        insert_into_leaf_sorted(&mut entries, ext(30000, 5000, 31000, false));
        assert_eq!(
            total_and_any_uninit(&entries),
            (35000, false),
            "{entries:?}"
        );
        assert!(entries.iter().all(|e| e.length <= 32768), "{entries:?}");
    }

    /// Promoting a full root to depth 1 does not merge past the limit.
    #[test]
    fn a_promotion_does_not_merge_past_the_extent_limit() {
        let root = mk_root(&[
            ext(0, 5, 1000, false),
            ext(100, 5, 2000, false),
            ext(200, 5, 3000, false),
            ext(300, 30000, 4000, false),
        ]);
        let plan =
            plan_promote_leaf(&root, ext(30300, 5000, 34000, false), 4096, 123, false).unwrap();
        let hdr = ExtentHeader::parse(&plan.leaf_bytes).unwrap();
        let entries = read_back(&plan.leaf_bytes[..12 + hdr.entries as usize * 12]);
        assert_eq!(
            total_and_any_uninit(&entries),
            (35015, false),
            "{entries:?}"
        );
    }

    /// Index node bytes: `entries` index entries (all at logical 0, all
    /// pointing at `child`) under a header claiming `max`, at `depth`.
    fn index_node(len: usize, entries: u16, max: u16, depth: u16, child: u64) -> Vec<u8> {
        let mut buf = vec![0u8; len];
        buf[0..2].copy_from_slice(&EXT4_EXT_MAGIC.to_le_bytes());
        buf[2..4].copy_from_slice(&entries.to_le_bytes());
        buf[4..6].copy_from_slice(&max.to_le_bytes());
        buf[6..8].copy_from_slice(&depth.to_le_bytes());
        for i in 0..entries as usize {
            let off = extent_entry_offset(i);
            if off + EXT4_EXT_NODE_SIZE > len {
                break;
            }
            let (hi, lo) = split_phys_block(child);
            buf[off + 4..off + 8].copy_from_slice(&lo.to_le_bytes());
            buf[off + 8..off + 10].copy_from_slice(&hi.to_le_bytes());
        }
        buf
    }

    /// Serves one block for every read.
    struct OneBlock(Vec<u8>);

    impl DeepReader for OneBlock {
        fn read_block(&self, _block: u64, out: &mut [u8]) -> Result<()> {
            out.copy_from_slice(&self.0);
            Ok(())
        }
    }

    /// `ExtentHeader::parse` checks `entries <= max` but not `max` against
    /// the node, so a 60-byte root claiming five index entries sent the
    /// descent slicing `[60..72]` (#327).
    #[test]
    fn a_root_claiming_more_index_entries_than_it_holds_is_refused() {
        let root = index_node(60, 5, 5, 1, 7000);
        let reader = OneBlock(vec![0u8; 1024]);
        let mut alloc = || -> Result<u64> { panic!("nothing is allocated") };
        let err =
            plan_insert_extent_deep(&root, ext(1000, 1, 9000, false), 1024, &reader, &mut alloc)
                .expect_err("a root with five index entries in a four-entry area");
        assert!(matches!(err, Error::CorruptExtentTree(_)), "{err:?}");
    }

    /// The same through a child block whose header claims more entries
    /// than the block holds (#327).
    #[test]
    fn a_child_claiming_more_index_entries_than_its_block_holds_is_refused() {
        let root = index_node(60, 1, 4, 2, 7000);
        // 100 entries of 12 bytes after a 12-byte header: 1212 > 1024.
        let reader = OneBlock(index_node(1024, 100, 100, 1, 7001));
        let mut alloc = || -> Result<u64> { panic!("nothing is allocated") };
        let err =
            plan_insert_extent_deep(&root, ext(1000, 1, 9000, false), 1024, &reader, &mut alloc)
                .expect_err("a child with a hundred index entries in a 1 KiB block");
        assert!(matches!(err, Error::CorruptExtentTree(_)), "{err:?}");
    }
}