[[Allocation_Groups]]
= Allocation Groups

As mentioned earlier, XFS filesystems are divided into a number of equally
sized chunks called Allocation Groups. Each AG can almost be thought of as an
individual filesystem that maintains its own space usage. Each AG can be up to
one terabyte in size (512 bytes × 2^31^), regardless of the underlying device's
sector size.

Each AG has the following characteristics:

         * A super block describing overall filesystem info
         * Free space management
         * Inode allocation and tracking
         * Reverse block-mapping index (optional)
         * Data block reference count index (optional)

Having multiple AGs allows XFS to handle most operations in parallel without
degrading performance as the number of concurrent accesses increases.

The only global information maintained by the first AG (primary) is free space
across the filesystem and total inode counts. If the
+XFS_SB_VERSION2_LAZYSBCOUNTBIT+ flag is set in the superblock, these are only
updated on-disk when the filesystem is cleanly unmounted (umount or shutdown).

Immediately after a +mkfs.xfs+, the primary AG has the following disk layout;
the subsequent AGs do not have any inodes allocated:

.Allocation group layout
image::images/6.png[]

Each of these structures are expanded upon in the following sections.

include::superblock.asciidoc[]

[[AG_Free_Space_Management]]
== AG Free Space Management

The XFS filesystem tracks free space in an allocation group using two B+trees.
One B+tree tracks space by block number, the second by the size of the free
space block. This scheme allows XFS to find quickly free space near a given
block or of a given size.

All block numbers, indexes, and counts are AG relative.

[[AG_Free_Space_Block]]
=== AG Free Space Block

The second sector in an AG contains the information about the two free space
B+trees and associated free space information for the AG. The ``AG Free Space
Block'' also knows as the +AGF+, uses the following structure:

[source, c]
----
struct xfs_agf {
     __be32              agf_magicnum;
     __be32              agf_versionnum;
     __be32              agf_seqno;
     __be32              agf_length;
     __be32              agf_roots[XFS_BTNUM_AGF];
     __be32              agf_levels[XFS_BTNUM_AGF];
     __be32              agf_flfirst;
     __be32              agf_fllast;
     __be32              agf_flcount;
     __be32              agf_freeblks;
     __be32              agf_longest;
     __be32              agf_btreeblks;

     /* version 5 filesystem fields start here */
     uuid_t              agf_uuid;
     __be32              agf_rmap_blocks;
     __be32              agf_refcount_blocks;
     __be32              agf_refcount_root;
     __be32              agf_refcount_level;
     __be64              agf_spare64[14];

     /* unlogged fields, written during buffer writeback. */
     __be64              agf_lsn;
     __be32              agf_crc;
     __be32              agf_spare2;
};
----

The rest of the bytes in the sector are zeroed. +XFS_BTNUM_AGF+ is set to 3:
index 0 for the free space B+tree indexed by block number; index 1 for the free
space B+tree indexed by extent size; and index 2 for the reverse-mapping
B+tree.

*agf_magicnum*::
Specifies the magic number for the AGF sector: ``XAGF'' (0x58414746).

*agf_versionnum*::
Set to +XFS_AGF_VERSION+ which is currently 1.

*agf_seqno*::
Specifies the AG number for the sector.

*agf_length*::
Specifies the size of the AG in filesystem blocks. For all AGs except the last,
this must be equal to the superblock's +sb_agblocks+ value. For the last AG,
this could be less than the +sb_agblocks+ value. It is this value that should
be used to determine the size of the AG.

*agf_roots*::
Specifies the block number for the root of the two free space B+trees and the
reverse-mapping B+tree, if enabled.

*agf_levels*::
Specifies the level or depth of the two free space B+trees and the
reverse-mapping B+tree, if enabled.  For a fresh AG, this value will be one,
and the ``roots'' will point to a single leaf of level 0.

*agf_flfirst*::
Specifies the index of the first ``free list'' block. Free lists are covered in
more detail later on.

*agf_fllast*::
Specifies the index of the last ``free list'' block.

*agf_flcount*::
Specifies the number of blocks in the ``free list''.

*agf_freeblks*::
Specifies the current number of free blocks in the AG.

*agf_longest*::
Specifies the number of blocks of longest contiguous free space in the AG.

*agf_btreeblks*::
Specifies the number of blocks used for the free space B+trees. This is only
used if the +XFS_SB_VERSION2_LAZYSBCOUNTBIT+ bit is set in +sb_features2+.

*agf_uuid*::
The UUID of this block, which must match either +sb_uuid+ or +sb_meta_uuid+
depending on which features are set.

*agf_rmap_blocks*::
The size of the reverse mapping B+tree in this allocation group, in blocks.

*agf_refcount_blocks*::
The size of the reference count B+tree in this allocation group, in blocks.

*agf_refcount_root*::
Block number for the root of the reference count B+tree, if enabled.

*agf_refcount_level*::
Depth of the reference count B+tree, if enabled.

*agf_spare64*::
Empty space in the logged part of the AGF sector, for use for future features.

*agf_lsn*::
Log sequence number of the last AGF write.

*agf_crc*::
Checksum of the AGF sector.

*agf_spare2*::
Empty space in the unlogged part of the AGF sector.

[[AG_Free_Space_Btrees]]
=== 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.

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

[source, c]
----
struct xfs_alloc_rec {
     __be32                    ar_startblock;
     __be32                    ar_blockcount;
};
----

*ar_startblock*::
AG block number of the start of the free space.

*ar_blockcount*::
Length of the free space.

Node pointers are an AG relative block pointer:

[source, c]
----
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.  On a v5
filesystem, these are ``AB3B'' (0x41423342) and ``AB3C'' (0x41423343),
respectively.
* 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:

.Freespace B+tree with one leaf.
image::images/15a.png[]

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:

.Multi-level freespace B+tree.
image::images/15b.png[]

[[AG_Free_List]]
=== AG Free List

The AG Free List is located in the 4^th^ sector of each AG and is known as the
AGFL. It is an array of AG relative block pointers for reserved space for
growing the free space B+trees. This space cannot be used for general user data
including inodes, data, directories and extended attributes.

With a freshly made filesystem, 4 blocks are reserved immediately after the free
space B+tree root blocks (blocks 4 to 7). As they are used up as the free space
fragments, additional blocks will be reserved from the AG and added to the free
list array.  This size may increase as features are added.

As the free list array is located within a single sector, a typical device will
have space for 128 elements in the array (512 bytes per sector, 4 bytes per AG
relative block pointer). The actual size can be determined by using the
+XFS_AGFL_SIZE+ macro.

Active elements in the array are specified by the
xref:AG_Free_Space_Block[AGF's] +agf_flfirst+, +agf_fllast+ and +agf_flcount+
values. The array is managed as a circular list.

On a v5 filesystem, the following header precedes the free list entries:

[source, c]
----
struct xfs_agfl {
     __be32              agfl_magicnum;
     __be32              agfl_seqno;
     uuid_t              agfl_uuid;
     __be64              agfl_lsn;
     __be32              agfl_crc;
};
----

*agfl_magicnum*::
Specifies the magic number for the AGFL sector: "XAFL" (0x5841464c).

*agfl_seqno*::
Specifies the AG number for the sector.

*agfl_uuid*::
The UUID of this block, which must match either +sb_uuid+ or +sb_meta_uuid+
depending on which features are set.

*agfl_lsn*::
Log sequence number of the last AGFL write.

*agfl_crc*::
Checksum of the AGFL sector.

On a v4 filesystem there is no header; the array of free block numbers begins
at the beginning of the sector.

.AG Free List layout
image::images/16.png[]

The presence of these reserved blocks guarantees that the free space B+trees
can be updated if any blocks are freed by extent changes in a full AG.

==== xfs_db AGF Example

These examples are derived from an AG that has been deliberately fragmented.
The AGF:

----
xfs_db> agf 0
xfs_db> p
magicnum = 0x58414746
versionnum = 1
seqno = 0
length = 3923122
bnoroot = 7
cntroot = 83343
bnolevel = 2
cntlevel = 2
flfirst = 22
fllast = 27
flcount = 6
freeblks = 3654234
longest = 3384327
btreeblks = 0
----

In the AGFL, the active elements are from 22 to 27 inclusive which are obtained
from the +flfirst+ and +fllast+ values from the +agf+ in the previous example:

----
xfs_db> agfl 0
xfs_db> p
bno[0-127] = 0:4 1:5 2:6 3:7 4:83342 5:83343 6:83344 7:83345 8:83346 9:83347
             10:4 11:5 12:80205 13:80780 14:81496 15:81766 16:83346 17:4 18:5
             19:80205 20:82449 21:81496 22:81766 23:82455 24:80780 25:5
             26:80205 27:83344
----

The root block of the free space B+tree sorted by block offset is found in the
AGF's +bnoroot+ value:

----
xfs_db> fsblock 7
xfs_db> type bnobt
xfs_db> p
magic = 0x41425442
level = 1
numrecs = 4
leftsib = null
rightsib = null
keys[1-4] = [startblock,blockcount]
           1:[12,16] 2:[184586,3] 3:[225579,1] 4:[511629,1]
ptrs[1-4] = 1:2 2:83347 3:6 4:4
----

Blocks 2, 83347, 6 and 4 contain the leaves for the free space B+tree by
starting block. Block 2 would contain offsets 12 up to but not including 184586
while block 4 would have all offsets from 511629 to the end of the AG.

The root block of the free space B+tree sorted by block count is found in the
AGF's +cntroot+ value:

----
xfs_db> fsblock 83343
xfs_db> type cntbt
xfs_db> p
magic = 0x41425443
level = 1
numrecs = 4
leftsib = null
rightsib = null
keys[1-4] = [blockcount,startblock]
           1:[1,81496] 2:[1,511729] 3:[3,191875] 4:[6,184595]
ptrs[1-4] = 1:3 2:83345 3:83342 4:83346
----

The leaf in block 3, in this example, would only contain single block counts.
The offsets are sorted in ascending order if the block count is the same.

Inspecting the leaf in block 83346, we can see the largest block at the end:

----
xfs_db> fsblock 83346
xfs_db> type cntbt
xfs_db> p
magic = 0x41425443
level = 0
numrecs = 344
leftsib = 83342
rightsib = null
recs[1-344] = [startblock,blockcount]
           1:[184595,6] 2:[187573,6] 3:[187776,6]
           ...
           342:[513712,755] 343:[230317,258229] 344:[538795,3384327]
----

The longest block count (3384327) must be the same as the AGF's +longest+ value.

[[AG_Inode_Management]]
== AG Inode Management

[[Inode_Numbers]]
=== Inode Numbers

Inode numbers in XFS come in two forms: AG relative and absolute.

AG relative inode numbers always fit within 32 bits. The number of bits actually
used is determined by the sum of the xref:Superblocks[superblock's] +sb_inoplog+
and +sb_agblklog+ values. Relative inode numbers are found within the AG's inode
structures.

Absolute inode numbers include the AG number in the high bits, above the bits
used for the AG relative inode number. Absolute inode numbers are found in
xref:Directories[directory] entries and the superblock.

.Inode number formats
image::images/18.png[]

[[Inode_Information]]
=== Inode Information

Each AG manages its own inodes. The third sector in the AG contains information
about the AG's inodes and is known as the AGI.

The AGI uses the following structure:

[source, c]
----
struct xfs_agi {
     __be32              agi_magicnum;
     __be32              agi_versionnum;
     __be32              agi_seqno
     __be32              agi_length;
     __be32              agi_count;
     __be32              agi_root;
     __be32              agi_level;
     __be32              agi_freecount;
     __be32              agi_newino;
     __be32              agi_dirino;
     __be32              agi_unlinked[64];

     /*
      * v5 filesystem fields start here; this marks the end of logging region 1
      * and start of logging region 2.
      */
     uuid_t              agi_uuid;
     __be32              agi_crc;
     __be32              agi_pad32;
     __be64              agi_lsn;

     __be32              agi_free_root;
     __be32              agi_free_level;

     __be32              agi_iblocks;
     __be32              agi_fblocks;

}
----
*agi_magicnum*::
Specifies the magic number for the AGI sector: ``XAGI'' (0x58414749).

*agi_versionnum*::
Set to +XFS_AGI_VERSION+ which is currently 1.

*agi_seqno*::
Specifies the AG number for the sector.

*agi_length*::
Specifies the size of the AG in filesystem blocks.

*agi_count*::
Specifies the number of inodes allocated for the AG.

*agi_root*::
Specifies the block number in the AG containing the root of the inode B+tree.

*agi_level*::
Specifies the number of levels in the inode B+tree.

*agi_freecount*::
Specifies the number of free inodes in the AG.

*agi_newino*::
Specifies AG-relative inode number of the most recently allocated chunk.

*agi_dirino*::
Deprecated and not used, this is always set to NULL (-1).

*agi_unlinked[64]*::
Hash table of unlinked (deleted) inodes that are still being referenced. Refer
to xref:Unlinked_Pointer[unlinked list pointers] for more information.

*agi_uuid*::
The UUID of this block, which must match either +sb_uuid+ or +sb_meta_uuid+
depending on which features are set.

*agi_crc*::
Checksum of the AGI sector.

*agi_pad32*::
Padding field, otherwise unused.

*agi_lsn*::
Log sequence number of the last write to this block.

*agi_free_root*::
Specifies the block number in the AG containing the root of the free inode
B+tree.

*agi_free_level*::
Specifies the number of levels in the free inode B+tree.

*agi_iblocks*::
The number of blocks in the inode B+tree, including the root.
This field is zero if the +XFS_SB_FEAT_RO_COMPAT_INOBTCNT+ feature is not
enabled.

*agi_fblocks*::
The number of blocks in the free inode B+tree, including the root.
This field is zero if the +XFS_SB_FEAT_RO_COMPAT_INOBTCNT+ feature is not
enabled.

[[Inode_Btrees]]
== Inode B+trees

Inodes are traditionally 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.  If the
+XFS_SB_FEAT_RO_COMPAT_FINOBT+ feature is enabled, a second B+tree is used to
track the chunks containing free inodes; this is an optimization to speed up
inode allocation.

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 xref:AG_Free_Space_Btrees[AGF
B+trees].

The magic number of the inode B+tree is ``IABT'' (0x49414254).  On a v5
filesystem, the magic number is ``IAB3'' (0x49414233).

The magic number of the free inode B+tree is ``FIBT'' (0x46494254).  On a v5
filesystem, the magic number is ``FIB3'' (0x46494254).

Leaves contain an array of the following structure:

[source,c]
----
struct xfs_inobt_rec {
     __be32                    ir_startino;
     __be32                    ir_freecount;
     __be64                    ir_free;
};
----

*ir_startino*::
The lowest-numbered inode in this chunk.

*ir_freecount*::
Number of free inodes in this chunk.

*ir_free*::
A 64 element bitmap showing which inodes in this chunk are free.

Nodes contain key/pointer pairs using the following types:

[source,c]
----
struct xfs_inobt_key {
     __be32                     ir_startino;
};
typedef __be32 xfs_inobt_ptr_t;
----

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

.Single Level inode B+tree
image::images/20a.png[]


And a 2-level inode B+tree:

.Multi-Level inode B+tree
image::images/20b.png[]


=== xfs_db AGI Example

This is an AGI of a freshly populated filesystem:

----
xfs_db> agi 0
xfs_db> p
magicnum = 0x58414749
versionnum = 1
seqno = 0
length = 825457
count = 5440
root = 3
level = 1
freecount = 9
newino = 5792
dirino = null
unlinked[0-63] =
uuid = 3dfa1e5c-5a5f-4ca2-829a-000e453600fe
lsn = 0x1000032c2
crc = 0x14cb7e5c (correct)
free_root = 4
free_level = 1
----

From this example, we see that the inode B+tree is rooted at AG block 3 and
that the free inode B+tree is rooted at AG block 4.  Let's look at the
inode B+tree:

----
xfs_db> addr root
xfs_db> p
magic = 0x49414233
level = 0
numrecs = 85
leftsib = null
rightsib = null
bno = 24
lsn = 0x1000032c2
uuid = 3dfa1e5c-5a5f-4ca2-829a-000e453600fe
owner = 0
crc = 0x768f9592 (correct)
recs[1-85] = [startino,freecount,free]
        1:[96,0,0] 2:[160,0,0] 3:[224,0,0] 4:[288,0,0]
        5:[352,0,0] 6:[416,0,0] 7:[480,0,0] 8:[544,0,0]
        9:[608,0,0] 10:[672,0,0] 11:[736,0,0] 12:[800,0,0]
        ...
        85:[5792,9,0xff80000000000000]
----

Most of the inode chunks on this filesystem are totally full, since the +free+
value is zero.  This means that we ought to expect inode 160 to be linked
somewhere in the directory structure.  However, notice that 0xff80000000000000
in record 85 -- this means that we would expect inode 5847 to be free.  Moving
on to the free inode B+tree, we see that this is indeed the case:

----
xfs_db> addr free_root
xfs_db> p
magic = 0x46494233
level = 0
numrecs = 1
leftsib = null
rightsib = null
bno = 32
lsn = 0x1000032c2
uuid = 3dfa1e5c-5a5f-4ca2-829a-000e453600fe
owner = 0
crc = 0x338af88a (correct)
recs[1] = [startino,freecount,free] 1:[5792,9,0xff80000000000000]
----

Observe also that the AGI's +agi_newino+ points to this chunk, which has never
been fully allocated.

[[Sparse_Inodes]]
== Sparse Inodes

As mentioned in the previous section, XFS allocates inodes in chunks of 64.  If
there are no free extents large enough to hold a full chunk of 64 inodes, the
inode allocation fails and XFS claims to have run out of space.  On a
filesystem with highly fragmented free space, this can lead to out of space
errors long before the filesystem runs out of free blocks.

The sparse inode feature tracks inode chunks in the inode B+tree as if they
were full chunks but uses some previously unused bits in the freecount field to
track which parts of the inode chunk are not allocated for use as inodes.  This
allows XFS to allocate inodes one block at a time if absolutely necessary.

The inode and free inode B+trees operate in the same manner as they do without
the sparse inode feature; 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
xref:AG_Free_Space_Btrees[AGF B+trees].

It is theoretically possible for a sparse inode B+tree record to reference
multiple non-contiguous inode chunks.

Leaves contain an array of the following structure:

[source,c]
----
struct xfs_inobt_rec {
     __be32                    ir_startino;
     __be16                    ir_holemask;
     __u8                      ir_count;
     __u8                      ir_freecount;
     __be64                    ir_free;
};
----

*ir_startino*::
The lowest-numbered inode in this chunk, rounded down to the nearest multiple
of 64, even if the start of this chunk is sparse.

*ir_holemask*::
A 16 element bitmap showing which parts of the chunk are not allocated to
inodes.  Each bit represents four inodes; if a bit is marked here, the
corresponding bits in ir_free must also be marked.

*ir_count*::
Number of inodes allocated to this chunk.

*ir_freecount*::
Number of free inodes in this chunk.

*ir_free*::
A 64 element bitmap showing which inodes in this chunk are not available for
allocation.

=== xfs_db Sparse Inode AGI Example

This example derives from an AG that has been deliberately fragmented.  The
inode B+tree:

----
xfs_db> agi 0
xfs_db> p
magicnum = 0x58414749
versionnum = 1
seqno = 0
length = 6400
count = 10432
root = 2381
level = 2
freecount = 0
newino = 14912
dirino = null
unlinked[0-63] =
uuid = b9b4623b-f678-4d48-8ce7-ce08950e3cd6
lsn = 0x600000ac4
crc = 0xef550dbc (correct)
free_root = 4
free_level = 1
----

This AGI was formatted on a v5 filesystem; notice the extra v5 fields.  So far
everything else looks much the same as always.

----
xfs_db> addr root
magic = 0x49414233
level = 1
numrecs = 2
leftsib = null
rightsib = null
bno = 19048
lsn = 0x50000192b
uuid = b9b4623b-f678-4d48-8ce7-ce08950e3cd6
owner = 0
crc = 0xd98cd2ca (correct)
keys[1-2] = [startino] 1:[128] 2:[35136]
ptrs[1-2] = 1:3 2:2380
xfs_db> addr ptrs[1]
xfs_db> p
magic = 0x49414233
level = 0
numrecs = 159
leftsib = null
rightsib = 2380
bno = 24
lsn = 0x600000ac4
uuid = b9b4623b-f678-4d48-8ce7-ce08950e3cd6
owner = 0
crc = 0x836768a6 (correct)
recs[1-159] = [startino,holemask,count,freecount,free]
        1:[128,0,64,0,0]
        2:[14912,0xff,32,0,0xffffffff]
        3:[15040,0,64,0,0]
        4:[15168,0xff00,32,0,0xffffffff00000000]
        5:[15296,0,64,0,0]
        6:[15424,0xff,32,0,0xffffffff]
        7:[15552,0,64,0,0]
        8:[15680,0xff00,32,0,0xffffffff00000000]
        9:[15808,0,64,0,0]
        10:[15936,0xff,32,0,0xffffffff]
----

Here we see the difference in the inode B+tree records.  For example, in record
2, we see that the holemask has a value of 0xff.  This means that the first
sixteen inodes in this chunk record do not actually map to inode blocks; the
first inode in this chunk is actually inode 14944:

----
xfs_db> inode 14912
Metadata corruption detected at block 0x3a40/0x2000
...
Metadata CRC error detected for ino 14912
xfs_db> p core.magic
core.magic = 0
xfs_db> inode 14944
xfs_db> p core.magic
core.magic = 0x494e
----

The chunk record also indicates that this chunk has 32 inodes, and that the
missing inodes are also ``free''.