3.3.3. Inode B+trees

Inodes are allocated in chunks of 64, and a B+tree is used to track these chunks of inodes as they are allocated and freed. The block containing root of the B+tree is defined by the AGI's agi_root value.

The B+tree header for the nodes and leaves use the xfs_btree_sblock structure which is the same as the header used in the AGF B+trees (Section 3.2.2, “AG Free Space B+trees”):

typedef struct xfs_btree_sblock xfs_inobt_block_t;

Leaves contain an array of the following structure:

typedef struct xfs_inobt_rec {
     __be32                    ir_startino;
     __be32                    ir_freecount;
     __be64                    ir_free;
} xfs_inobt_rec_t;

Nodes contain key/pointer pairs using the following types:

typedef struct xfs_inobt_key {
     __be32                     ir_startino;
} xfs_inobt_key_t;
typedef __be32 xfs_inobt_ptr_t;

For the leaf entries, ir_startino specifies the starting inode number for the chunk, ir_freecount specifies the number of free entries in the chuck, and the ir_free is a 64 element bit array specifying which entries are free in the chunk.

The following diagram illustrates a single level inode B+tree:

And a 2-level inode B+tree:

xfs_db Examples:

TODO: