xfs_btree.hpp

Go to the documentation of this file.

// xfs_btree.hpp -- Generic B+tree walker for XFS (V4 + V5).
//
// XFS uses B+trees pervasively: free-space, inode allocation, extent
// mapping (BMBT), reverse-mapping (V5), reference-count (V5). All share
// the same node header layout and traversal pattern; only the record
// format and key format differ per tree type.
//
// In session 2 we only USE this walker to enumerate the inode B+tree
// (IBT). The walker is generic so the next sessions can plug in BMBT
// for extent decoding without rewriting the traversal logic.
//
// NODE HEADER LAYOUTS
// -------------------
//   V4 short-form header (used in per-AG B+trees: IBT, ABTB, ABTC):
//     offset 0x00: __be32 magic         "IABT" (V4) or "IAB3" (V5)
//     offset 0x04: __be16 level         0 = leaf, >0 = internal
//     offset 0x06: __be16 numrecs       number of records/keys in this block
//     offset 0x08: __be32 leftsib       left sibling block (NULLAGBLOCK if none)
//     offset 0x0C: __be32 rightsib      right sibling block
//     header length = 16 bytes
//
//   V5 short-form header (per-AG B+trees, with CRC):
//     offset 0x00: __be32 magic         "IAB3"
//     offset 0x04: __be16 level
//     offset 0x06: __be16 numrecs
//     offset 0x08: __be32 leftsib
//     offset 0x0C: __be32 rightsib
//     offset 0x10: __be64 blkno         block number of THIS block
//     offset 0x18: __be64 lsn           log sequence number
//     offset 0x20: uuid_t  uuid         (16 bytes)
//     offset 0x30: __be32 owner         AG number
//     offset 0x34: __be32 crc           CRC32
//     header length = 56 bytes
//
//   We don't validate the V5 CRC -- we want to read damaged volumes too --
//   but we MUST account for the larger header when computing the offset of
//   the records/keys array.
//
// IBT RECORD (leaf level)
// -----------------------
//   struct xfs_inobt_rec_t {
//     __be32 ir_startino;     // starting AG-relative inode number
//     __be32 ir_freecount;    // number of free inodes in this chunk (V4)
//                             //   OR ir_holemask (V5 SPARSE feature)
//                             //   We treat the field generically and pick
//                             //   the right meaning based on SB features.
//     __be64 ir_free;         // bitmap: bit i set => inode (start+i) is FREE
//   };
//   Size: 16 bytes per record. A "chunk" is exactly 64 inodes.
//
//   For V5 with SPARSE inodes (XFS_SB_FEAT_INCOMPAT_SPINODES), the layout
//   becomes:
//     __be32 ir_startino;
//     __be16 ir_holemask;     // bit i set => sub-chunk i is a hole
//     __u8   ir_count;        // total inodes in this chunk
//     __u8   ir_freecount;    // free inodes in this chunk
//     __be64 ir_free;
//   Size still 16 bytes.
//
// IBT KEY (internal nodes)
// ------------------------
//   struct xfs_inobt_key_t { __be32 ir_startino; };
//   Size: 4 bytes per key.
//
// IBT POINTER (internal nodes)
// ----------------------------
//   __be32 ptr;  // child block (AG-relative). Size: 4 bytes.
//
// In an internal block of `numrecs` entries, we have `numrecs` keys
// followed by `maxrecs` pointers (XFS reserves space for max even if
// not used). For traversal we only need numrecs keys + numrecs pointers.
 
#pragma once
 
#include "xfs_format.hpp"
 
#include <cstdint>
#include <functional>
#include <string>
#include <vector>
 
namespace xfs {
 
// "NULL" block sentinel for sibling/child pointers
constexpr uint32_t NULLAGBLOCK = 0xFFFFFFFFu;
constexpr uint64_t NULLFSBLOCK = 0xFFFFFFFFFFFFFFFFull;
 
// Decoded short-form B+tree node header
struct BtreeNodeHeader {
    uint32_t magic   {0};
    uint16_t level   {0};
    uint16_t numrecs {0};
    uint32_t leftsib {NULLAGBLOCK};
    uint32_t rightsib{NULLAGBLOCK};
    // V5-only fields (zero on V4)
    uint64_t blkno   {0};
    uint64_t lsn     {0};
    uint32_t owner   {0};
    uint32_t crc     {0};
    // Computed from the magic number / SB version
    bool is_v5_header{false};
};
 
// Returns the byte length of the node header (16 for V4, 56 for V5).
inline uint32_t btree_header_size(bool is_v5) {
    return is_v5 ? 56u : 16u;
}
 
// Parse a short-form B+tree node header from a block buffer.
// `buf` must point to at least `btree_header_size(is_v5)` bytes.
// Returns false on invalid magic or implausible field values.
//
// `expected_magic_v4` and `expected_magic_v5` let the caller restrict
// matches to a specific tree kind (IBT, ABTB, ABTC, BMBT, ...).
bool parse_btree_header(const unsigned char* buf,
                        uint32_t expected_magic_v4,
                        uint32_t expected_magic_v5,
                        BtreeNodeHeader& out);
 
// Decoded inode B+tree leaf record.
struct InobtRec {
    uint32_t startino   {0}; // AG-relative starting inode number
    uint16_t holemask   {0}; // V5 sparse only; 0 on V4
    uint8_t  count      {64};// total inodes in the chunk; defaults to 64
    uint8_t  freecount  {0}; // free inodes in the chunk
    uint64_t freemask   {0}; // bit i set => inode (startino+i) is FREE
    bool     sparse     {false}; // true when V5 SPARSE feature was used
};
 
// Parse one inode-B+tree leaf record (16 bytes).
//
// `is_v5_sparse` selects between classic V4 layout (ir_freecount as 32-bit
// at offset 4) and V5 SPARSE layout (holemask + count + freecount packed
// into bytes 4..7).
//
// The `freemask` semantics are unchanged across formats.
void parse_inobt_record(const unsigned char* buf, bool is_v5_sparse,
                        InobtRec& out);
 
// =============================================================================
//  Traversal API
// =============================================================================
//
// We expose two callback flavours:
//
//   * walk_inode_btree(reader, vol, agno, on_record, logs, error)
//       Calls `on_record(rec, agno)` for every IBT leaf record found
//       under AGI[agno].root, in B+tree order. Returns false on fatal
//       I/O / format error. Damage in one branch logs a warning but
//       does not abort the traversal of the other branches.
//
//   * walk_all_inode_records(reader, vol, on_record, logs)
//       Convenience wrapper: walks the IBT of every AG and calls the
//       callback for every leaf record across the whole filesystem.
//
// The callback returns `false` to stop traversal early (e.g. on a
// fatal user-level error); `true` to continue.
 
} // namespace xfs
 
class DiskReader; // forward (defined in disk_reader.hpp)
 
namespace xfs {
 
using InobtRecordCallback =
    std::function<bool(const InobtRec& rec, uint32_t agno)>;
 
bool walk_inode_btree(DiskReader& reader,
                      const VolumeContext& vol,
                      uint32_t agno,
                      const InobtRecordCallback& on_record,
                      std::vector<std::string>& logs,
                      std::string& error);
 
bool walk_all_inode_records(DiskReader& reader,
                            const VolumeContext& vol,
                            const InobtRecordCallback& on_record,
                            std::vector<std::string>& logs);
 
// =============================================================================
//  FINOBT (free-inode B+tree, V5 only)
// =============================================================================
//
// Same record/key/pointer encoding as the IBT, but the magic numbers are
// FIBT (V4 -- not used in practice since FINOBT is V5-only) and FIB3 (V5).
// The root/depth come from agi_free_root / agi_free_level instead of
// agi_root / agi_level.
//
// Walks one AG's free-inode B+tree and yields each leaf record. Records
// expose `freemask`: bits set there mean the inode at (startino + bit) is
// FREE -- i.e. either never used or recently deleted. By reading the
// dinode at that disk offset we can attempt to recover deleted-file data
// for cancellations that haven't yet been overwritten by a new alloc.
//
// IMPORTANT: this only works on V5 volumes with the FINOBT feature
// (XFS_SB_FEAT_RO_COMPAT_FINOBT). On V4, agi.free_root/free_level are
// zero and the walker will simply yield nothing.
//
// FINOBT magic numbers (XFS_FIBT_MAGIC_V4/V5) are already declared in
// xfs_format.hpp.
 
// Same callback type (records have identical layout).
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);
 
bool walk_all_free_inode_records(DiskReader& reader,
                                  const VolumeContext& vol,
                                  const InobtRecordCallback& on_record,
                                  std::vector<std::string>& logs);
 
// =============================================================================
//  Inode iteration helpers
// =============================================================================
//
// Once we have an InobtRec, we know the chunk of 64 (or fewer, with sparse)
// inodes starting at `startino` and which of them are allocated. The
// caller will typically want to:
//   1. iterate bit positions 0..63 in the chunk
//   2. skip bits where `holemask` says "hole" (V5 sparse)
//   3. skip bits where `freemask` bit is set (free => not allocated)
//   4. for each allocated bit, compute the global inode number and the
//      disk byte offset of the dinode
//
// The helper below does this packaging. It does NOT read the dinode
// itself -- that's session 3.
 
struct AllocatedInode {
    uint64_t ino {0};            // global 64-bit inode number
    uint32_t agno {0};
    uint32_t agbno {0};          // AG-relative block where the chunk starts
    uint32_t in_chunk_index {0}; // 0..63
    uint64_t disk_offset {0};    // absolute byte offset to the dinode
};
 
// Expand a single InobtRec into a list of AllocatedInode entries.
// Appends to `out`. Skips holes and free inodes.
void expand_chunk(const InobtRec& rec, uint32_t agno,
                  const VolumeContext& vol,
                  std::vector<AllocatedInode>& out);
 
// Mirror of expand_chunk(), but emits inodes whose freemask bit IS set
// (= free / recently deleted). Used by FINOBT recovery: each entry
// points to a dinode slot that may still hold recoverable content.
void expand_chunk_free(const InobtRec& rec, uint32_t agno,
                        const VolumeContext& vol,
                        std::vector<AllocatedInode>& out);
 
// =============================================================================
//  BMBT (block-map B+tree) -- LONG-FORM
// =============================================================================
//
// Used by the data fork of an inode when di_format == 3 ("btree"). This
// happens when the inline extent list overflows what fits inside the
// fork buffer.
//
// Header layouts (DIFFERENT from the short-form per-AG B+trees!):
//
//   V4 long-form header (24 bytes):
//     0x00 __be32 magic   ("BMAP" 0x424D4150)
//     0x04 __be16 level
//     0x06 __be16 numrecs
//     0x08 __be64 leftsib   FSB (NULLFSBLOCK if none)
//     0x10 __be64 rightsib
//
//   V5 long-form header (72 bytes):
//     0x00 __be32 magic   ("BMA3" 0x424D4133)
//     0x04 __be16 level
//     0x06 __be16 numrecs
//     0x08 __be64 leftsib
//     0x10 __be64 rightsib
//     0x18 __be64 blkno
//     0x20 __be64 lsn
//     0x28 uuid_t uuid (16 bytes)
//     0x38 __be64 owner    (inode number)
//     0x40 __be32 crc
//     0x44 __be32 pad
//
// Internal-node layout (long-form):
//   [ header ][ keys[maxrecs] ][ ptrs[maxrecs] ]
//   key  = __be64 startoff  (8 bytes)
//   ptr  = __be64 child FSB (8 bytes)
//
// Leaf records: 16-byte BMBT records with the same bit-packed encoding
// as inline extents (see xfs_inode.cpp::decode_extent_record).
//
// THE ROOT:
// When di_format=3, the data fork itself contains a TRUNCATED long-form
// header (called the "root header" or "bmdr") followed by keys/pointers
// to the first level of children. The "root" in the fork is NOT a full
// 24/72-byte header -- it's a 4-byte mini-header (level + numrecs) plus
// the keys/pointers list. From there we descend into real BMBT blocks
// on disk that DO use the full 24/72-byte long-form header.
//
//   bmdr (in inode fork):
//     0x00 __be16 level
//     0x02 __be16 numrecs
//     0x04 keys[]   (8 bytes each, __be64 startoff)
//     ...  ptrs[]   (8 bytes each, __be64 FSB)
//
// `walk_extent_btree_root` accepts the inode's data-fork buffer and
// the volume context, decodes the bmdr root, then walks every child
// down to the leaves yielding leaf extents into `out`. Per-branch
// corruption is reported in `logs` but does not abort siblings
// (BALANCED behaviour).
 
constexpr uint32_t XFS_BMBT_MAGIC_V4 = 0x424D4150u; // "BMAP"
constexpr uint32_t XFS_BMBT_MAGIC_V5 = 0x424D4133u; // "BMA3"
 
// Long-form BMBT: 8-byte keys (startoff), 8-byte pointers (FSB), 16-byte recs
constexpr uint32_t BMBT_KEY_SIZE_LONG = 8;
constexpr uint32_t BMBT_PTR_SIZE_LONG = 8;
constexpr uint32_t BMBT_REC_SIZE      = 16;
 
// Long-form B+tree node header (decoded form).
struct BtreeLongHeader {
    uint32_t magic    {0};
    uint16_t level    {0};
    uint16_t numrecs  {0};
    uint64_t leftsib  {NULLFSBLOCK};
    uint64_t rightsib {NULLFSBLOCK};
    // V5 extras:
    uint64_t blkno    {0};
    uint64_t lsn      {0};
    uint64_t owner    {0};
    uint32_t crc      {0};
    bool     is_v5_header {false};
};
 
inline uint32_t btree_long_header_size(bool is_v5) {
    return is_v5 ? 72u : 24u;
}
 
// Parse a long-form B+tree header. Returns false on bad magic.
bool parse_btree_long_header(const unsigned char* buf,
                             uint32_t expected_magic_v4,
                             uint32_t expected_magic_v5,
                             BtreeLongHeader& out);
 
// Forward-declared, defined in xfs_inode.hpp. We keep this header lean
// by not pulling xfs_inode.hpp here.
struct Extent;
 
// Walk the BMBT whose ROOT lives in an inode's data fork (di_format=3).
//
// `root_buf`     points to the start of the bmdr root (= the first byte
//                 of the data fork in the dinode buffer).
// `root_len`     is the number of valid bytes available at `root_buf`,
//                 i.e. the data-fork length.
// `is_v5_volume` selects between V4 BMAP and V5 BMA3 magics on children.
// `max_extents`  is a safety cap (suggested: 1'000'000).
//
// Appends every leaf extent record found into `out`. Returns false ONLY
// on fatal error (root header malformed, max_extents reached). Per-block
// damage on children is logged and does not abort sibling branches.
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);
 
} // namespace xfs