Classes
struct	LocalBmbtRec

Functions
uint32_t	ibt_maxrecs (uint32_t blocksize, uint32_t header_size, uint32_t level)
uint64_t	ag_block_to_disk_offset (const VolumeContext &vol, uint32_t agno, uint32_t agbno)
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)
void	decode_bmbt_record_local (const unsigned char *buf16, LocalBmbtRec &r)
uint64_t	fsb_to_byte_offset_local (uint64_t fsb, const VolumeContext &vol)
void	push_extent (std::vector< Extent > &out, const LocalBmbtRec &r)
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)

Variables
constexpr uint32_t	IBT_REC_SIZE = 16
constexpr uint32_t	IBT_KEY_SIZE = 4
constexpr uint32_t	IBT_PTR_SIZE = 4
constexpr size_t	MAX_NODES_PER_AG = 1'000'000

Function Documentation

◆ ag_block_to_disk_offset()

uint64_t xfs::anonymous_namespace{xfs_btree.cpp}::ag_block_to_disk_offset	(	const VolumeContext &	vol,
		uint32_t	agno,
		uint32_t	agbno )

Definition at line 59 of file xfs_btree.cpp.

                                                                {
    return vol.volume_offset
         + static_cast<uint64_t>(agno) * vol.sb.agblocks * vol.sb.blocksize
         + static_cast<uint64_t>(agbno) * vol.sb.blocksize;
}

References ag_block_to_disk_offset(), xfs::Superblock::agblocks, xfs::Superblock::blocksize, xfs::VolumeContext::sb, and xfs::VolumeContext::volume_offset.

Referenced by ag_block_to_disk_offset(), and walk_ibt_block().

◆ decode_bmbt_record_local()

void xfs::anonymous_namespace{xfs_btree.cpp}::decode_bmbt_record_local	(	const unsigned char *	buf16,
		LocalBmbtRec &	r )

Definition at line 517 of file xfs_btree.cpp.

                                                                           {
    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));
}

References xfs::be64(), and decode_bmbt_record_local().

Referenced by decode_bmbt_record_local(), and walk_bmbt_block().

◆ fsb_to_byte_offset_local()

uint64_t xfs::anonymous_namespace{xfs_btree.cpp}::fsb_to_byte_offset_local	(	uint64_t	fsb,
		const VolumeContext &	vol )

Definition at line 528 of file xfs_btree.cpp.

                                                                          {
    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;
}

References xfs::Superblock::agblklog, xfs::Superblock::agblocks, xfs::Superblock::blocksize, fsb_to_byte_offset_local(), xfs::VolumeContext::sb, and xfs::VolumeContext::volume_offset.

Referenced by fsb_to_byte_offset_local(), and walk_bmbt_block().

◆ ibt_maxrecs()

uint32_t xfs::anonymous_namespace{xfs_btree.cpp}::ibt_maxrecs	(	uint32_t	blocksize,
		uint32_t	header_size,
		uint32_t	level )

Definition at line 52 of file xfs_btree.cpp.

                                                                               {
    const uint32_t avail = blocksize - header_size;
    return (level == 0) ? (avail / IBT_REC_SIZE)
                        : (avail / (IBT_KEY_SIZE + IBT_PTR_SIZE));
}

References IBT_KEY_SIZE, ibt_maxrecs(), IBT_PTR_SIZE, and IBT_REC_SIZE.

Referenced by ibt_maxrecs(), and walk_ibt_block().

◆ push_extent()

void xfs::anonymous_namespace{xfs_btree.cpp}::push_extent	(	std::vector< Extent > &	out,
		const LocalBmbtRec &	r )

Definition at line 565 of file xfs_btree.cpp.

                                                                {
    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);
}

References xfs::Extent::length_blocks, xfs::Extent::logical_off_blocks, xfs::Extent::physical_block, push_extent(), and xfs::Extent::unwritten.

Referenced by push_extent(), and walk_bmbt_block().

◆ walk_bmbt_block()

bool xfs::anonymous_namespace{xfs_btree.cpp}::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 )

Definition at line 577 of file xfs_btree.cpp.

                                            {
    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;
}

References xfs::be64(), xfs::Superblock::blocksize, xfs::BMBT_KEY_SIZE_LONG, xfs::BMBT_PTR_SIZE_LONG, xfs::BMBT_REC_SIZE, xfs::btree_long_header_size(), decode_bmbt_record_local(), fsb_to_byte_offset_local(), xfs::BtreeLongHeader::is_v5_header, xfs::BtreeLongHeader::level, xfs::NULLFSBLOCK, xfs::BtreeLongHeader::numrecs, xfs::parse_btree_long_header(), push_extent(), DiskReader::read_at(), xfs::VolumeContext::sb, walk_bmbt_block(), xfs::XFS_BMBT_MAGIC_V4, and xfs::XFS_BMBT_MAGIC_V5.

Referenced by walk_bmbt_block().

◆ walk_ibt_block()

bool xfs::anonymous_namespace{xfs_btree.cpp}::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 )

Definition at line 134 of file xfs_btree.cpp.

                                            {
    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;
}