Product SiteDocumentation Site

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;
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: