xfs_btree.cpp

Go to the documentation of this file.

// xfs_btree.cpp -- Generic B+tree traversal for XFS, plus IBT specialisation.
//
// In session 2 we only walk the inode allocation B+tree (IBT). The walker
// is structured so the caller plugs in:
//   - the expected magic numbers (V4 + V5) for the tree kind
//   - the per-AG root block (taken from AGI for IBT)
//   - the per-AG depth (taken from AGI.level)
//   - a leaf-record callback
//
// IMPORTANT layout details (see xfs_btree.hpp banner for the full picture):
//
// * V5 nodes have a 56-byte header (vs 16 on V4). All record/key/ptr
//   offsets must be measured relative to the right header size.
//
// * In an INTERNAL node, the record area for IBT is laid out as
//      keys[maxrecs]   followed by   ptrs[maxrecs]
//   where `maxrecs` is the max that fits in a block of size `blocksize`,
//   NOT the actual `numrecs` of the node. This matters: pointers begin
//   at offset `header + maxrecs*key_size`, regardless of how many keys
//   are actually used.
//
// * IBT records are 16 bytes each. IBT keys are 4 bytes (just startino).
//   IBT pointers are 4 bytes (AG-relative block number).
//
// * Leaf records are stored consecutively starting right after the header.
//
// We don't validate V5 CRCs: the goal is to read damaged volumes too.
// We DO validate magic, level, numrecs, and pointer ranges before
// recursing into a child block.
 
#include "xfs_btree.hpp"
#include "disk_reader.hpp"
 
#include <algorithm>
#include <array>
#include <set>
#include <sstream>
#include <vector>
 
namespace xfs {
 
namespace {
 
// IBT field sizes (constant across V4/V5)
constexpr uint32_t IBT_REC_SIZE = 16;  // ir_startino(4) + ir_*(4) + ir_free(8)
constexpr uint32_t IBT_KEY_SIZE = 4;   // ir_startino
constexpr uint32_t IBT_PTR_SIZE = 4;   // AG-relative block number
 
// Compute maxrecs for an IBT node at `level`.
//   level 0 (leaf):     records of IBT_REC_SIZE bytes
//   level > 0 (intern): pairs of (key + ptr) = IBT_KEY_SIZE + IBT_PTR_SIZE
uint32_t ibt_maxrecs(uint32_t blocksize, uint32_t header_size, uint32_t level) {
    const uint32_t avail = blocksize - header_size;
    return (level == 0) ? (avail / IBT_REC_SIZE)
                        : (avail / (IBT_KEY_SIZE + IBT_PTR_SIZE));
}
 
// Convert AG#+AG-relative block to absolute disk byte offset.
uint64_t ag_block_to_disk_offset(const VolumeContext& vol,
                                 uint32_t agno, uint32_t agbno) {
    return vol.volume_offset
         + static_cast<uint64_t>(agno) * vol.sb.agblocks * vol.sb.blocksize
         + static_cast<uint64_t>(agbno) * vol.sb.blocksize;
}
 
// Defensive: max nodes we'll ever traverse in a single AG. A pathological
// SB or a corruption loop should not walk forever.
constexpr size_t MAX_NODES_PER_AG = 1'000'000;
 
} // anonymous namespace
 
bool parse_btree_header(const unsigned char* buf,
                        uint32_t expected_magic_v4,
                        uint32_t expected_magic_v5,
                        BtreeNodeHeader& out) {
    if (buf == nullptr) return false;
    out = {};
 
    out.magic = be32(buf + 0x00);
 
    if (out.magic == expected_magic_v5) {
        out.is_v5_header = true;
    } else if (out.magic == expected_magic_v4) {
        out.is_v5_header = false;
    } else {
        return false;
    }
 
    out.level    = be16(buf + 0x04);
    out.numrecs  = be16(buf + 0x06);
    out.leftsib  = be32(buf + 0x08);
    out.rightsib = be32(buf + 0x0C);
 
    if (out.is_v5_header) {
        out.blkno = be64(buf + 0x10);
        out.lsn   = be64(buf + 0x18);
        // uuid at +0x20..+0x30 ignored
        out.owner = be32(buf + 0x30);
        out.crc   = be32(buf + 0x34);
    }
 
    // Sanity: level must be plausible (XFS B+trees never go beyond ~16)
    if (out.level > 16) return false;
    return true;
}
 
void parse_inobt_record(const unsigned char* buf, bool is_v5_sparse,
                        InobtRec& out) {
    out = {};
    out.startino = be32(buf + 0x00);
    if (is_v5_sparse) {
        // V5 sparse layout: 16-bit holemask, 8-bit count, 8-bit freecount
        out.holemask  = be16(buf + 0x04);
        out.count     = buf[0x06];
        out.freecount = buf[0x07];
        if (out.count == 0) out.count = 64; // some early kernels left 0; default
        out.sparse    = true;
    } else {
        // Classic layout: 32-bit freecount at offset 4
        const uint32_t freec32 = be32(buf + 0x04);
        out.freecount = static_cast<uint8_t>(std::min<uint32_t>(freec32, 64));
        out.holemask  = 0;
        out.count     = 64;
        out.sparse    = false;
    }
    out.freemask = be64(buf + 0x08);
}
 
// Recursive traversal of one IBT subtree rooted at `block`.
// Returns false on FATAL error (read/format) that should abort the whole
// walk for this AG; per-branch warnings are appended to `logs` instead.
namespace {
 
bool walk_ibt_block(DiskReader& reader,
                    const VolumeContext& vol,
                    uint32_t agno,
                    uint32_t agbno,
                    uint32_t expected_level,
                    uint32_t magic_v4,
                    uint32_t magic_v5,
                    const char* tree_label,
                    const InobtRecordCallback& on_record,
                    std::set<uint32_t>& visited,
                    size_t& nodes_visited,
                    std::vector<std::string>& logs,
                    std::string& error,
                    bool& callback_stopped) {
    if (callback_stopped) return true;
 
    if (agbno == 0 || agbno == NULLAGBLOCK || agbno >= vol.sb.agblocks) {
        std::ostringstream m;
        m << "XFS " << tree_label << " (AG " << agno << "): invalid child pointer " << agbno;
        logs.push_back(m.str());
        return true; // not fatal: skip this branch
    }
 
    if (++nodes_visited > MAX_NODES_PER_AG) {
        error = std::string("XFS ") + tree_label
              + ": traversal exceeded safety cap (possible loop)";
        return false;
    }
 
    if (!visited.insert(agbno).second) {
        std::ostringstream m;
        m << "XFS " << tree_label << " (AG " << agno
          << "): cycle detected at block " << agbno << ", skipping";
        logs.push_back(m.str());
        return true;
    }
 
    const uint64_t blk_off = ag_block_to_disk_offset(vol, agno, agbno);
    std::vector<unsigned char> block(vol.sb.blocksize, 0);
    if (!reader.read_at(blk_off, block.data(), block.size())) {
        std::ostringstream m;
        m << "XFS " << tree_label << " (AG " << agno
          << "): read failed for block " << agbno;
        logs.push_back(m.str());
        return true; // not fatal -- just lose this branch
    }
 
    BtreeNodeHeader hdr;
    if (!parse_btree_header(block.data(), magic_v4, magic_v5, hdr)) {
        std::ostringstream m;
        m << "XFS " << tree_label << " (AG " << agno
          << "): bad magic at block " << agbno;
        logs.push_back(m.str());
        return true;
    }
    if (hdr.level != expected_level) {
        std::ostringstream m;
        m << "XFS " << tree_label << " (AG " << agno
          << "): block " << agbno << " has level " << hdr.level
          << ", expected " << expected_level;
        logs.push_back(m.str());
        // Don't abort -- some damaged trees can still yield records
    }
 
    const uint32_t header_size = btree_header_size(hdr.is_v5_header);
    const bool is_v5 = vol.sb.is_v5();
    const bool is_v5_sparse =
        is_v5 && (vol.sb.features_incompat & XFS_SB_FEAT_INCOMPAT_SPINODES);
 
    if (hdr.level == 0) {
        // ----------- LEAF -----------
        const uint32_t maxrecs = ibt_maxrecs(vol.sb.blocksize, header_size, 0);
        if (hdr.numrecs > maxrecs) {
            std::ostringstream m;
            m << "XFS " << tree_label << " (AG " << agno
              << "): leaf at block " << agbno
              << " reports numrecs=" << hdr.numrecs
              << " > maxrecs=" << maxrecs << ", clamping";
            logs.push_back(m.str());
        }
        const uint32_t n = std::min<uint32_t>(hdr.numrecs, maxrecs);
        for (uint32_t i = 0; i < n; ++i) {
            const unsigned char* recp =
                block.data() + header_size + i * IBT_REC_SIZE;
            InobtRec rec;
            parse_inobt_record(recp, is_v5_sparse, rec);
            if (!on_record(rec, agno)) {
                callback_stopped = true;
                return true;
            }
        }
    } else {
        // ----------- INTERNAL -----------
        const uint32_t maxrecs = ibt_maxrecs(vol.sb.blocksize, header_size,
                                              hdr.level);
        if (hdr.numrecs > maxrecs) {
            std::ostringstream m;
            m << "XFS " << tree_label << " (AG " << agno
              << "): internal at block " << agbno
              << " reports numrecs=" << hdr.numrecs
              << " > maxrecs=" << maxrecs << ", clamping";
            logs.push_back(m.str());
        }
        const uint32_t n = std::min<uint32_t>(hdr.numrecs, maxrecs);
 
        // Pointers start AFTER the maxrecs key array (not numrecs!)
        const uint32_t ptrs_offset = header_size + maxrecs * IBT_KEY_SIZE;
 
        for (uint32_t i = 0; i < n; ++i) {
            const uint32_t ptr_off = ptrs_offset + i * IBT_PTR_SIZE;
            if (ptr_off + IBT_PTR_SIZE > vol.sb.blocksize) break;
            const uint32_t child = be32(block.data() + ptr_off);
            if (!walk_ibt_block(reader, vol, agno, child,
                                hdr.level - 1,
                                magic_v4, magic_v5, tree_label,
                                on_record, visited, nodes_visited,
                                logs, error, callback_stopped)) {
                return false;
            }
            if (callback_stopped) return true;
        }
    }
    return true;
}
 
} // anonymous namespace
 
bool walk_inode_btree(DiskReader& reader,
                      const VolumeContext& vol,
                      uint32_t agno,
                      const InobtRecordCallback& on_record,
                      std::vector<std::string>& logs,
                      std::string& error) {
    if (agno >= vol.ag.size()) {
        error = "walk_inode_btree: agno out of range";
        return false;
    }
    const auto& agctx = vol.ag[agno];
    if (!agctx.agi_loaded) {
        std::ostringstream m;
        m << "XFS IBT (AG " << agno << "): AGI not loaded, skipping";
        logs.push_back(m.str());
        return true;
    }
    const uint32_t root = agctx.agi.root;
    const uint32_t depth = agctx.agi.level;
 
    if (root == 0 || root == NULLAGBLOCK) {
        std::ostringstream m;
        m << "XFS IBT (AG " << agno << "): empty (root=" << root << ")";
        logs.push_back(m.str());
        return true;
    }
    if (depth > 16) {
        std::ostringstream m;
        m << "XFS IBT (AG " << agno << "): implausible depth " << depth;
        logs.push_back(m.str());
        return true;
    }
 
    std::set<uint32_t> visited;
    size_t nodes_visited = 0;
    bool callback_stopped = false;
    return walk_ibt_block(reader, vol, agno, root, depth,
                          XFS_IBT_MAGIC_V4, XFS_IBT_MAGIC_V5, "IBT",
                          on_record, visited, nodes_visited,
                          logs, error, callback_stopped);
}
 
bool walk_all_inode_records(DiskReader& reader,
                            const VolumeContext& vol,
                            const InobtRecordCallback& on_record,
                            std::vector<std::string>& logs) {
    bool any_error = false;
    for (uint32_t agno = 0; agno < vol.sb.agcount && agno < vol.ag.size(); ++agno) {
        std::string err;
        if (!walk_inode_btree(reader, vol, agno, on_record, logs, err)) {
            any_error = true;
            logs.push_back("XFS IBT (AG " + std::to_string(agno) + "): "
                           + err);
        }
    }
    return !any_error;
}
 
// =============================================================================
//  FINOBT walker (V5 only)
// =============================================================================
 
bool walk_free_inode_btree(DiskReader& reader,
                           const VolumeContext& vol,
                           uint32_t agno,
                           const InobtRecordCallback& on_record,
                           std::vector<std::string>& logs,
                           std::string& error) {
    if (agno >= vol.ag.size()) {
        error = "walk_free_inode_btree: agno out of range";
        return false;
    }
    const auto& agctx = vol.ag[agno];
    if (!agctx.agi_loaded) {
        std::ostringstream m;
        m << "XFS FINOBT (AG " << agno << "): AGI not loaded, skipping";
        logs.push_back(m.str());
        return true;
    }
    if (!vol.sb.is_v5() ||
        !(vol.sb.features_ro_compat & XFS_SB_FEAT_RO_COMPAT_FINOBT)) {
        // No FINOBT on this volume.
        return true;
    }
 
    const uint32_t root  = agctx.agi.free_root;
    const uint32_t depth = agctx.agi.free_level;
 
    if (root == 0 || root == NULLAGBLOCK) {
        std::ostringstream m;
        m << "XFS FINOBT (AG " << agno << "): empty (root=" << root << ")";
        logs.push_back(m.str());
        return true;
    }
    if (depth > 16) {
        std::ostringstream m;
        m << "XFS FINOBT (AG " << agno << "): implausible depth " << depth;
        logs.push_back(m.str());
        return true;
    }
 
    std::set<uint32_t> visited;
    size_t nodes_visited = 0;
    bool callback_stopped = false;
    return walk_ibt_block(reader, vol, agno, root, depth,
                          XFS_FIBT_MAGIC_V4, XFS_FIBT_MAGIC_V5, "FINOBT",
                          on_record, visited, nodes_visited,
                          logs, error, callback_stopped);
}
 
bool walk_all_free_inode_records(DiskReader& reader,
                                  const VolumeContext& vol,
                                  const InobtRecordCallback& on_record,
                                  std::vector<std::string>& logs) {
    if (!vol.sb.is_v5() ||
        !(vol.sb.features_ro_compat & XFS_SB_FEAT_RO_COMPAT_FINOBT)) {
        // V4 or feature missing -- nothing to do.
        return true;
    }
    bool any_error = false;
    for (uint32_t agno = 0; agno < vol.sb.agcount && agno < vol.ag.size(); ++agno) {
        std::string err;
        if (!walk_free_inode_btree(reader, vol, agno, on_record, logs, err)) {
            any_error = true;
            logs.push_back("XFS FINOBT (AG " + std::to_string(agno) + "): " + err);
        }
    }
    return !any_error;
}
 
void expand_chunk(const InobtRec& rec, uint32_t agno,
                  const VolumeContext& vol,
                  std::vector<AllocatedInode>& out) {
    // The chunk starts at AG-relative inode number `rec.startino`.
    // Convert that to an AG-relative block number for the chunk start:
    //    chunk_agbno = rec.startino / inopblock
    //    in-block-offset of inode i = (rec.startino + i) % inopblock
    const uint32_t inopblock = vol.sb.inopblock;
    const uint32_t inode_size = vol.sb.inodesize;
    if (inopblock == 0 || inode_size == 0) return;
 
    const uint32_t chunk_count = std::min<uint32_t>(rec.count, 64);
    for (uint32_t i = 0; i < chunk_count; ++i) {
        // Sparse: skip holes (16-bit holemask in 4-inode granularity:
        // each bit covers 4 consecutive inode positions)
        if (rec.sparse) {
            const uint32_t hole_bit = i / 4;
            if (rec.holemask & (1u << hole_bit)) continue;
        }
        // Skip inodes marked free
        if (rec.freemask & (1ull << i)) continue;
 
        const uint32_t agino = rec.startino + i;
        const uint32_t chunk_agbno = agino / inopblock;
        const uint32_t in_block_off = agino % inopblock;
 
        AllocatedInode ai;
        ai.agno = agno;
        ai.agbno = chunk_agbno;
        ai.in_chunk_index = i;
        // Reconstruct global 64-bit inode number
        ai.ino = (static_cast<uint64_t>(agno) <<
                   (vol.sb.agblklog + vol.sb.inopblog))
               | static_cast<uint64_t>(agino);
        ai.disk_offset = ag_block_to_disk_offset(vol, agno, chunk_agbno)
                       + static_cast<uint64_t>(in_block_off) * inode_size;
        out.push_back(ai);
    }
}
 
// Mirror of expand_chunk(), but emits inodes whose freemask bit IS set
// (= free / recently deleted). Skips holes (sparse). Used by FINOBT
// recovery -- each entry points to a dinode slot that may still hold
// recoverable content from a deleted file, until XFS reuses the slot.
void expand_chunk_free(const InobtRec& rec, uint32_t agno,
                        const VolumeContext& vol,
                        std::vector<AllocatedInode>& out) {
    const uint32_t inopblock = vol.sb.inopblock;
    const uint32_t inode_size = vol.sb.inodesize;
    if (inopblock == 0 || inode_size == 0) return;
 
    const uint32_t chunk_count = std::min<uint32_t>(rec.count, 64);
    for (uint32_t i = 0; i < chunk_count; ++i) {
        // Sparse: skip holes -- a hole means there's no real inode slot
        // at this position, so there's nothing to recover.
        if (rec.sparse) {
            const uint32_t hole_bit = i / 4;
            if (rec.holemask & (1u << hole_bit)) continue;
        }
        // Emit ONLY free slots (the opposite of expand_chunk).
        if (!(rec.freemask & (1ull << i))) continue;
 
        const uint32_t agino = rec.startino + i;
        const uint32_t chunk_agbno = agino / inopblock;
        const uint32_t in_block_off = agino % inopblock;
 
        AllocatedInode ai;  // re-using the type, but it's a "free" slot here
        ai.agno = agno;
        ai.agbno = chunk_agbno;
        ai.in_chunk_index = i;
        ai.ino = (static_cast<uint64_t>(agno) <<
                   (vol.sb.agblklog + vol.sb.inopblog))
               | static_cast<uint64_t>(agino);
        ai.disk_offset = ag_block_to_disk_offset(vol, agno, chunk_agbno)
                       + static_cast<uint64_t>(in_block_off) * inode_size;
        out.push_back(ai);
    }
}
 
// =============================================================================
//  BMBT (long-form) walker -- session 4
// =============================================================================
 
bool parse_btree_long_header(const unsigned char* buf,
                             uint32_t expected_magic_v4,
                             uint32_t expected_magic_v5,
                             BtreeLongHeader& out) {
    if (buf == nullptr) return false;
    out = {};
    out.magic = be32(buf + 0x00);
    if (out.magic == expected_magic_v5)      out.is_v5_header = true;
    else if (out.magic == expected_magic_v4) out.is_v5_header = false;
    else return false;
 
    out.level    = be16(buf + 0x04);
    out.numrecs  = be16(buf + 0x06);
    out.leftsib  = be64(buf + 0x08);
    out.rightsib = be64(buf + 0x10);
 
    if (out.is_v5_header) {
        out.blkno = be64(buf + 0x18);
        out.lsn   = be64(buf + 0x20);
        // uuid at +0x28..+0x38 ignored
        out.owner = be64(buf + 0x38);
        out.crc   = be32(buf + 0x40);
        // pad at +0x44 ignored
    }
    if (out.level > 32) return false;  // nonsense depth
    return true;
}
 
namespace {
 
// We need to forward-declare Extent's existence; the actual decoder
// lives in xfs_inode.cpp. To keep xfs_btree.cpp self-contained for
// header parsing, we implement a local 16-byte BMBT record decoder.
//
// This MUST stay byte-identical to xfs::decode_extent_record in
// xfs_inode.cpp -- both decode the same on-disk format.
struct LocalBmbtRec {
    uint64_t logical_off_blocks {0};
    uint64_t physical_block     {0};
    uint32_t length_blocks      {0};
    bool     unwritten          {false};
};
 
void decode_bmbt_record_local(const unsigned char* buf16, LocalBmbtRec& r) {
    const uint64_t w0 = be64(buf16 + 0);
    const uint64_t w1 = be64(buf16 + 8);
    r.unwritten           = ((w0 >> 63) & 1ull) != 0;
    r.logical_off_blocks  = (w0 >> 9) & ((1ull << 54) - 1ull);
    const uint64_t hi9    = w0 & 0x1FFull;
    const uint64_t lo43   = (w1 >> 21) & ((1ull << 43) - 1ull);
    r.physical_block      = (hi9 << 43) | lo43;
    r.length_blocks       = static_cast<uint32_t>(w1 & ((1ull << 21) - 1ull));
}
 
uint64_t fsb_to_byte_offset_local(uint64_t fsb, const VolumeContext& vol) {
    if (vol.sb.agblklog == 0) return vol.volume_offset + fsb * vol.sb.blocksize;
    const uint64_t mask  = (1ull << vol.sb.agblklog) - 1ull;
    const uint32_t agno  = static_cast<uint32_t>(fsb >> vol.sb.agblklog);
    const uint32_t agbno = static_cast<uint32_t>(fsb & mask);
    return vol.volume_offset
         + static_cast<uint64_t>(agno) * vol.sb.agblocks * vol.sb.blocksize
         + static_cast<uint64_t>(agbno) * vol.sb.blocksize;
}
 
// Append a LocalBmbtRec to the user's `out` vector via the public
// xfs::Extent type. We do this by writing the four fields directly --
// xfs::Extent has the same logical/physical/length/unwritten fields,
// but the type itself is forward-declared in this TU. To avoid
// pulling xfs_inode.hpp in, we let xfs_recovery.cpp / callers convert
// from LocalBmbtRec -- but in practice the pattern is so simple that
// we just memcpy via a struct-shaped buffer.
//
// To keep things truly clean: this function is implemented in the .cpp
// where xfs::Extent is FULLY known, by including xfs_inode.hpp once.
//
// (We do that via a separate trampoline included from the integration
// site below.)
 
} // anonymous namespace
 
} // namespace xfs
 
// We need xfs::Extent fully visible for the next function. Including
// the inode header here (only in the .cpp) is the cleanest way without
// creating a circular header chain.
#include "xfs_inode.hpp"
 
namespace xfs {
 
namespace {
 
void push_extent(std::vector<Extent>& out, const LocalBmbtRec& r) {
    Extent e;
    e.logical_off_blocks = r.logical_off_blocks;
    e.physical_block     = r.physical_block;
    e.length_blocks      = r.length_blocks;
    e.unwritten          = r.unwritten;
    out.push_back(e);
}
 
// Recursively walk a BMBT subtree rooted at FSB `child_fsb` with
// expected level `expected_level`. Per-branch errors get logged but
// don't abort sibling branches (balanced policy).
bool walk_bmbt_block(DiskReader& reader, const VolumeContext& vol,
                     uint64_t child_fsb, uint32_t expected_level,
                     bool is_v5,
                     std::vector<Extent>& out,
                     std::vector<std::string>& logs,
                     uint32_t max_extents,
                     std::set<uint64_t>& visited,
                     size_t& nodes_visited) {
    if (out.size() >= max_extents) return true;
    if (child_fsb == NULLFSBLOCK || child_fsb == 0) return true;
    if (++nodes_visited > 1'000'000) {
        logs.push_back("XFS BMBT: traversal cap reached (1M nodes), stopping");
        return false;
    }
    if (!visited.insert(child_fsb).second) {
        logs.push_back("XFS BMBT: cycle at FSB " + std::to_string(child_fsb)
                       + " (skipped)");
        return true;
    }
 
    const uint64_t off = fsb_to_byte_offset_local(child_fsb, vol);
    std::vector<unsigned char> blk(vol.sb.blocksize, 0);
    if (!reader.read_at(off, blk.data(), blk.size())) {
        logs.push_back("XFS BMBT: read failed at FSB " + std::to_string(child_fsb));
        return true;
    }
 
    BtreeLongHeader hdr;
    if (!parse_btree_long_header(blk.data(),
                                 XFS_BMBT_MAGIC_V4,
                                 XFS_BMBT_MAGIC_V5,
                                 hdr)) {
        logs.push_back("XFS BMBT: bad magic at FSB " + std::to_string(child_fsb));
        return true;
    }
    if (hdr.level != expected_level) {
        logs.push_back("XFS BMBT: level mismatch at FSB "
                       + std::to_string(child_fsb)
                       + " (got " + std::to_string(hdr.level)
                       + ", expected " + std::to_string(expected_level) + ")");
        // Continue anyway -- damaged trees can still yield records
    }
 
    const uint32_t hsize = btree_long_header_size(hdr.is_v5_header);
 
    if (hdr.level == 0) {
        // Leaf: numrecs records of 16 bytes each starting at hsize
        const uint32_t maxrecs_leaf =
            (vol.sb.blocksize - hsize) / BMBT_REC_SIZE;
        const uint32_t n =
            std::min<uint32_t>(hdr.numrecs, maxrecs_leaf);
        for (uint32_t i = 0; i < n; ++i) {
            if (out.size() >= max_extents) return true;
            LocalBmbtRec r;
            decode_bmbt_record_local(blk.data() + hsize + i * BMBT_REC_SIZE, r);
            if (r.length_blocks == 0) continue;  // tolerate
            push_extent(out, r);
        }
    } else {
        // Internal: numrecs keys followed by maxrecs_internal keys (XFS
        // reserves space for max). Pointers start at hsize + maxrecs *
        // KEY_SIZE.
        const uint32_t key_ptr_pair =
            BMBT_KEY_SIZE_LONG + BMBT_PTR_SIZE_LONG;
        const uint32_t maxrecs_internal =
            (vol.sb.blocksize - hsize) / key_ptr_pair;
        const uint32_t n =
            std::min<uint32_t>(hdr.numrecs, maxrecs_internal);
        const uint32_t ptrs_offset =
            hsize + maxrecs_internal * BMBT_KEY_SIZE_LONG;
        for (uint32_t i = 0; i < n; ++i) {
            const uint32_t poff = ptrs_offset + i * BMBT_PTR_SIZE_LONG;
            if (poff + BMBT_PTR_SIZE_LONG > vol.sb.blocksize) break;
            const uint64_t cf = be64(blk.data() + poff);
            if (!walk_bmbt_block(reader, vol, cf, hdr.level - 1, is_v5,
                                 out, logs, max_extents, visited,
                                 nodes_visited)) {
                return false;
            }
        }
    }
    return true;
}
 
} // anonymous namespace
 
bool walk_extent_btree_root(DiskReader& reader,
                            const VolumeContext& vol,
                            const unsigned char* root_buf,
                            uint32_t root_len,
                            bool is_v5_volume,
                            uint32_t max_extents,
                            std::vector<Extent>& out,
                            std::vector<std::string>& logs,
                            std::string& error) {
    // bmdr "root" header in the data fork: 2 bytes level + 2 bytes numrecs
    // followed by numrecs keys (8 each) and numrecs pointers (8 each).
    // No magic, no CRC. The compact root is what fits inside the dinode
    // and points to the first level of REAL on-disk BMBT blocks.
    if (root_buf == nullptr || root_len < 4) {
        error = "BMBT: data fork too small for bmdr root";
        return false;
    }
    const uint16_t level   = be16(root_buf + 0);
    const uint16_t numrecs = be16(root_buf + 2);
    if (level == 0) {
        // No internal levels -- the "root" is itself a leaf. In bmdr, leaf
        // records are 16-byte BMBT records.
        if (4u + static_cast<uint32_t>(numrecs) * 16u > root_len) {
            error = "BMBT: bmdr leaf records overflow data fork";
            return false;
        }
        for (uint16_t i = 0; i < numrecs; ++i) {
            LocalBmbtRec r;
            decode_bmbt_record_local(root_buf + 4 + i * 16, r);
            if (r.length_blocks == 0) continue;
            push_extent(out, r);
            if (out.size() >= max_extents) return true;
        }
        return true;
    }
 
    // Internal root: layout is keys[numrecs] then ptrs[numrecs] (in
    // bmdr, no maxrecs reservation -- it's compact).
    if (4u + static_cast<uint32_t>(numrecs) * 16u > root_len) {
        error = "BMBT: bmdr root records overflow data fork";
        return false;
    }
    std::set<uint64_t> visited;
    size_t nodes_visited = 0;
    const uint32_t ptrs_off = 4u + numrecs * 8u;  // keys are 8 each
    for (uint16_t i = 0; i < numrecs; ++i) {
        const uint64_t child_fsb = be64(root_buf + ptrs_off + i * 8u);
        if (!walk_bmbt_block(reader, vol, child_fsb, level - 1,
                             is_v5_volume, out, logs, max_extents,
                             visited, nodes_visited)) {
            return false;
        }
        if (out.size() >= max_extents) {
            logs.push_back("XFS BMBT: extent cap reached ("
                           + std::to_string(max_extents) + ")");
            break;
        }
    }
    return true;
}
 
} // namespace xfs