3.2.2. AG Free Space B+trees

The two Free Space B+trees store a sorted array of block offset and block counts in the leaves of the B+tree. The first B+tree is sorted by the offset, the second by the count or size.

The trees use the following header:

typedef struct xfs_btree_sblock {
     __be32                    bb_magic;
     __be16                    bb_level;
     __be16                    bb_numrecs;
     __be32                    bb_leftsib;
     __be32                    bb_rightsib;
} xfs_btree_sblock_t;

Leaves contain a sorted array of offset/count pairs which are also used for node keys:

typedef struct xfs_alloc_rec {
     __be32                    ar_startblock;
     __be32                    ar_blockcount;
} xfs_alloc_rec_t, xfs_alloc_key_t;

Node pointers are an AG relative block pointer:

typedef __be32 xfs_alloc_ptr_t;

As the free space tracking is AG relative, all the block numbers are only 32-bits.
The bb_magic value depends on the B+tree: "ABTB" (0x41425442) for the block offset B+tree, "ABTC" (0x41425443) for the block count B+tree.
The xfs_btree_sblock_t header is used for intermediate B+tree node as well as the leaves.
For a typical 4KB filesystem block size, the offset for the xfs_alloc_ptr_t array would be 0xab0 (2736 decimal).
There are a series of macros in xfs_btree.h for deriving the offsets, counts, maximums, etc for the B+trees used in XFS.

The following diagram shows a single level B+tree which consists of one leaf:

With the intermediate nodes, the associated leaf pointers are stored in a separate array about two thirds into the block. The following diagram illustrates a 2-level B+tree for a free space B+tree: