path: root/design/XFS_Filesystem_Structure/directories.asciidoc

[[Directories]]
= Directories

[NOTE]
Only v2 directories covered here. v1 directories are obsolete.

[NOTE]
The term ``block'' in this section will refer to directory blocks, not filesystem
blocks unless otherwise specified.

The size of a ``directory block'' is defined by the xref:Superblocks[superblock's]
+sb_dirblklog+ value. The size in bytes = +sb_blocksize+ × 2^sb_dirblklog^.
For example, if +sb_blocksize+ = 4096 and +sb_dirblklog+ = 2, the directory block
size is 16384 bytes. Directory blocks are always allocated in multiples based on
+sb_dirblklog+. Directory blocks cannot be more that 65536 bytes in size.

All directory entries contain the following ``data'':

* The entry's name (counted string consisting of a single byte +namelen+
followed by +name+ consisting of an array of 8-bit chars without a NULL
terminator).

* The entry's absolute xref:Inode_Numbers[inode number], which are
always 64 bits (8 bytes) in size except a special case for shortform
directories.

* An +offset+ or +tag+ used for iterative readdir calls.

* If the +XFS_SB_FEAT_INCOMPAT_FTYPE+ feature flag is set, each
directory entry contains an +ftype+ field that caches the inode's type
to avoid having to perform an inode lookup.

.ftype values
[options="header"]
|=====
| Flag				| Description
| +XFS_DIR3_FT_UNKNOWN+ |
Entry points to an unknown inode type.  This should never appear on disk.
| +XFS_DIR3_FT_REG_FILE+ |
Entry points to a file.
| +XFS_DIR3_FT_DIR+ |
Entry points to another directory.
| +XFS_DIR3_FT_CHRDEV+ |
Entry points to a character device.
| +XFS_DIR3_FT_BLKDEV+ |
Entry points to a block device.
| +XFS_DIR3_FT_FIFO+ |
Entry points to a FIFO.
| +XFS_DIR3_FT_SOCK+ |
Entry points to a socket.
| +XFS_DIR3_FT_SYMLINK+ |
Entry points to a symbolic link.
| +XFS_DIR3_FT_WHT+ |
Entry points to an overlayfs whiteout file.  This (as far as the author
knows) has never appeared on disk.
|=====

All non-shortform directories also contain two additional structures: ``leaves''
and ``freespace indexes''.

* Leaves contain the sorted hashed name value (+xfs_da_hashname()+ in
xfs_da_btree.c) and associated ``address'' which points to the effective offset
into the directory's data structures. Leaves are used to optimise lookup
operations.

* Freespace indexes contain free space/empty entry tracking for quickly finding an
appropriately sized location for new entries. They maintain the largest free
space for each ``data'' block.

A few common types are used for the directory structures:

[source, c]
----
typedef __uint16_t xfs_dir2_data_off_t;
typedef __uint32_t xfs_dir2_dataptr_t;
----


[[Shortform_Directories]]
== Short Form Directories

* Directory entries are stored within the inode.

* The only data stored is the name, inode number, and offset.  No ``leaf'' or
``freespace index'' information is required as an inode can only store a few
entries.

* ``.'' is not stored (as it's in the inode itself), and ``..'' is a dedicated
+parent+ field in the header.

* The number of directories that can be stored in an inode depends on the
xref:On-disk_Inode[inode] size, the number of entries, the length of the entry
names, and extended attribute data.

* Once the number of entries exceeds the space available in the inode, the
format is converted to a xref:Block_Directories[block directory].

* Shortform directory data is packed as tightly as possible on the disk with the
remaining space zeroed:

[source, c]
----
typedef struct xfs_dir2_sf {
     xfs_dir2_sf_hdr_t         hdr;
     xfs_dir2_sf_entry_t       list[1];
} xfs_dir2_sf_t;
----

*hdr*::
Short form directory header.

*list*::
An array of variable-length directory entry records.

[source, c]
----
typedef struct xfs_dir2_sf_hdr {
     __uint8_t                 count;
     __uint8_t                 i8count;
     xfs_dir2_inou_t           parent;
} xfs_dir2_sf_hdr_t;
----

*count*::
Number of directory entries.

*i8count*::
Number of directory entries requiring 64-bit entries, if any inode numbers
require 64-bits.  Zero otherwise.

*parent*::
The absolute inode number of this directory's parent.

[source, c]
----
typedef struct xfs_dir2_sf_entry {
     __uint8_t                 namelen;
     xfs_dir2_sf_off_t         offset;
     __uint8_t                 name[1];
     __uint8_t                 ftype;
     xfs_dir2_inou_t           inumber;
} xfs_dir2_sf_entry_t;
----

*namelen*::
Length of the name, in bytes.

*offset*::
Offset tag used to assist with directory iteration.

*name*::
The name of the directory entry.  The entry is not NULL-terminated.

*ftype*::
The type of the inode.  This is used to avoid reading the inode while iterating
a directory.  The +XFS_SB_VERSION2_FTYPE+ feature must be set, or this field
will not be present.

*inumber*::
The inode number that this entry points to.  The length is either 32 or 64
bits, depending on whether +icount+ or +i8count+, respectively, are set in the
header.

.Short form directory layout
image::images/39.png[]

* Inode numbers are stored using 4 or 8 bytes depending on whether all the inode
numbers for the directory fit in 4 bytes (32 bits) or not. If all inode numbers
fit in 4 bytes, the header's +count+ value specifies the number of entries in
the directory and +i8count+ will be zero. If any inode number exceeds 4 bytes,
all inode numbers will be 8 bytes in size and the header's +i8count+ value
specifies the number of entries requiring larger inodes.  +i4count+ is still
the number of entries.  The following union covers the shortform inode number
structure:

[source, c]
----
typedef struct { __uint8_t i[8]; } xfs_dir2_ino8_t;
typedef struct { __uint8_t i[4]; } xfs_dir2_ino4_t;
typedef union {
     xfs_dir2_ino8_t           i8;
     xfs_dir2_ino4_t           i4;
} xfs_dir2_inou_t;
----

=== xfs_db Short Form Directory Example

A directory is created with 4 files, all inode numbers fitting within 4 bytes:

----
xfs_db> inode <inode#>
xfs_db> p
core.magic = 0x494e
core.mode = 040755
core.version = 1
core.format = 1 (local)
core.nlinkv1 = 2
...
core.size = 94
core.nblocks = 0
core.extsize = 0
core.nextents = 0
...
u.sfdir2.hdr.count = 4
u.sfdir2.hdr.i8count = 0
u.sfdir2.hdr.parent.i4 = 128              /* parent = root inode */
u.sfdir2.list[0].namelen = 15
u.sfdir2.list[0].offset = 0x30
u.sfdir2.list[0].name = "frame000000.tst"
u.sfdir2.list[0].inumber.i4 = 25165953
u.sfdir2.list[1].namelen = 15
u.sfdir2.list[1].offset = 0x50
u.sfdir2.list[1].name = "frame000001.tst"
u.sfdir2.list[1].inumber.i4 = 25165954
u.sfdir2.list[2].namelen = 15
u.sfdir2.list[2].offset = 0x70
u.sfdir2.list[2].name = "frame000002.tst"
u.sfdir2.list[2].inumber.i4 = 25165955
u.sfdir2.list[3].namelen = 15
u.sfdir2.list[3].offset = 0x90
u.sfdir2.list[3].name = "frame000003.tst"
u.sfdir2.list[3].inumber.i4 = 25165956
----

The raw data on disk with the first entry highlighted. The six byte header
precedes the first entry:

[subs="quotes"]
----
xfs_db> type text
xfs_db> p
00: 49 4e 41 ed 01 01 00 02 00 00 00 00 00 00 00 00 INA.............
10: 00 00 00 02 00 00 00 00 00 00 00 00 00 00 00 02 ................
20: 44 ad 3a 83 1d a9 4a d0 44 ad 3a ab 0b c7 a7 d0 D.....J.D.......
30: 44 ad 3a ab 0b c7 a7 d0 00 00 00 00 00 00 00 5e D...............
40: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 ................
50: 00 00 00 02 00 00 00 00 00 00 00 00 00 00 00 00 ................
60: ff ff ff ff 04 00 00 00 00 80 *0f 00 30 66 72 61* ............0fra
70: *6d 65 30 30 30 30 30 30 2e 74 73 74 01 80 00 81* me000000.tst....
80: 0f 00 50 66 72 61 6d 65 30 30 30 30 30 31 2e 74 ..Pframe000001.t
90: 73 74 01 80 00 82 0f 00 70 66 72 61 6d 65 30 30 st......pframe00
a0: 30 30 30 32 2e 74 73 74 01 80 00 83 0f 00 90 66 0002.tst........
b0: 72 61 6d 65 30 30 30 30 30 33 2e 74 73 74 01 80 rame000003.tst..
cO: 00 84 00 00 00 00 00 00 00 00 00 00 00 00 00 00 ................
----

Next, an entry is deleted (frame000001.tst), and any entries after the deleted
entry are moved or compacted to ``cover'' the hole:

----
xfs_db> inode <inode#>
xfs_db> p
core.magic = 0x494e
core.mode = 040755
core.version = 1
core.format = 1 (local)
core.nlinkv1 = 2
...
core.size = 72
core.nblocks = 0
core.extsize = 0
core.nextents = 0
...
u.sfdir2.hdr.count = 3
u.sfdir2.hdr.i8count = 0
u.sfdir2.hdr.parent.i4 = 128
u.sfdir2.list[0].namelen = 15
u.sfdir2.list[0].offset = 0x30
u.sfdir2.list[0].name = "frame000000.tst"
u.sfdir2.list[0].inumber.i4 = 25165953
u.sfdir2.list[1].namelen = 15
u.sfdir2.list[1].offset = 0x70
u.sfdir2.list[1].name = "frame000002.tst"
u.sfdir2.list[1].inumber.i4 = 25165955
u.sfdir2.list[2].namelen = 15
u.sfdir2.list[2].offset = 0x90
u.sfdir2.list[2].name = "frame000003.tst"
u.sfdir2.list[2].inumber.i4 = 25165956
----

Raw disk data, the space beyond the shortform entries is invalid and could be non-zero:

----
xfs_db> type text
xfs_db> p
00: 49  4e 41 ed 01 01 00 02 00 00 00 00 00 00 00 00 INA.............
10: 00  00 00 02 00 00 00 00 00 00 00 00 00 00 00 03 ................
20: 44  b2 45 a2 09 fd e4 50 44 b2 45 a3 12 ee b5 d0 D.E....PD.E.....
30: 44  b2 45 a3 12 ee b5 d0 00 00 00 00 00 00 00 48 D.E............H
40: 00  00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 ................
50: 00  00 00 02 00 00 00 00 00 00 00 00 00 00 00 00 ................
60: ff  ff ff ff 03 00 00 00 00 80 0f 00 30 66 72 61 ............0fra
70: 6d  65 30 30 30 30 30 30 2e 74 73 74 01 80 00 81 me000000.tst....
80: 0f  00 70 66 72 61 6d 65 30 30 30 30 30 32 2e 74 ..pframe000002.t
90: 73  74 01 80 00 83 0f 00 90 66 72 61 6d 65 30 30 st.......frame00
a0: 30  30 30 33 2e 74 73 74 01 80 00 84 0f 00 90 66 0003.tst.......f
b0: 72  61 6d 65 30 30 30 30 30 33 2e 74 73 74 01 80 rame000003.tst..
c0: 00  84 00 00 00 00 00 00 00 00 00 00 00 00 00 00 ................
----

This is an example of mixed 4-byte and 8-byte inodes in a directory:

----
xfs_db> inode 1024
xfs_db> p
core.magic = 0x494e
core.mode = 040755
core.version = 3
core.format = 1 (local)
core.nlinkv2 = 9
...
core.size = 125
core.nblocks = 0
core.extsize = 0
core.nextents = 0
...
u3.sfdir3.hdr.count = 7
u3.sfdir3.hdr.i8count = 4
u3.sfdir3.hdr.parent.i8 = 1024
u3.sfdir3.list[0].namelen = 3
u3.sfdir3.list[0].offset = 0x60
u3.sfdir3.list[0].name = "git"
u3.sfdir3.list[0].inumber.i8 = 1027
u3.sfdir3.list[0].filetype = 2
u3.sfdir3.list[1].namelen = 4
u3.sfdir3.list[1].offset = 0x70
u3.sfdir3.list[1].name = "home"
u3.sfdir3.list[1].inumber.i8 = 13422826546
u3.sfdir3.list[1].filetype = 2
u3.sfdir3.list[2].namelen = 10
u3.sfdir3.list[2].offset = 0x80
u3.sfdir3.list[2].name = "mike"
u3.sfdir3.list[2].inumber.i8 = 4299308032
u3.sfdir3.list[2].filetype = 2
u3.sfdir3.list[3].namelen = 3
u3.sfdir3.list[3].offset = 0x98
u3.sfdir3.list[3].name = "mtr"
u3.sfdir3.list[3].inumber.i8 = 13433252916
u3.sfdir3.list[3].filetype = 2
u3.sfdir3.list[4].namelen = 3
u3.sfdir3.list[4].offset = 0xa8
u3.sfdir3.list[4].name = "vms"
u3.sfdir3.list[4].inumber.i8 = 16647516355
u3.sfdir3.list[4].filetype = 2
u3.sfdir3.list[5].namelen = 5
u3.sfdir3.list[5].offset = 0xb8
u3.sfdir3.list[5].name = "rsync"
u3.sfdir3.list[5].inumber.i8 = 3494912
u3.sfdir3.list[5].filetype = 2
u3.sfdir3.list[6].namelen = 3
u3.sfdir3.list[6].offset = 0xd0
u3.sfdir3.list[6].name = "tmp"
u3.sfdir3.list[6].inumber.i8 = 1593379
u3.sfdir3.list[6].filetype = 2
----

[[Block_Directories]]
== Block Directories

When the shortform directory space exceeds the space in an inode, the directory
data is moved into a new single directory block outside the inode. The inode's
format is changed from ``local'' to ``extent'' Following is a list of points about
block directories.

* All directory data is stored within the one directory block, including ``.'' and
``..'' entries which are mandatory.

* The block also contains ``leaf'' and ``freespace index'' information.

* The location of the block is defined by the inode's in-core
xref:Extent_List[extent list]: the +di_u.u_bmx[0]+ value. The file offset in
the extent must always be zero and the +length+ = (directory block size /
filesystem block size). The block number points to the filesystem block
containing the directory data.

* Block directory data is stored in the following structures:

[source, c]
----
#define XFS_DIR2_DATA_FD_COUNT 3
typedef struct xfs_dir2_block {
     xfs_dir2_data_hdr_t        hdr;
     xfs_dir2_data_union_t      u[1];
     xfs_dir2_leaf_entry_t      leaf[1];
     xfs_dir2_block_tail_t      tail;
} xfs_dir2_block_t;
----

*hdr*::
Directory block header.  On a v5 filesystem this is +xfs_dir3_data_hdr_t+.

*u*::
Union of directory and unused entries.

*leaf*::
Hash values of the entries in this block.

*tail*::
Bookkeeping for the leaf entries.

[source, c]
----
typedef struct xfs_dir2_data_hdr {
     __uint32_t                 magic;
     xfs_dir2_data_free_t       bestfree[XFS_DIR2_DATA_FD_COUNT];
} xfs_dir2_data_hdr_t;
----

*magic*::
Magic number for this directory block.

*bestfree*::
An array pointing to free regions in the directory block.

On a v5 filesystem, directory and attribute blocks are formatted with v3
headers, which contain extra data:

[source, c]
----
struct xfs_dir3_blk_hdr {
     __be32                     magic;
     __be32                     crc;
     __be64                     blkno;
     __be64                     lsn;
     uuid_t                     uuid;
     __be64                     owner;
};
----

*magic*::
Magic number for this directory block.

*crc*::
Checksum of the directory block.

*blkno*::
Block number of this directory block.

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

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

*owner*::
The inode number that this directory block belongs to.

[source, c]
----
struct xfs_dir3_data_hdr {
     struct xfs_dir3_blk_hdr    hdr;
     xfs_dir2_data_free_t       best_free[XFS_DIR2_DATA_FD_COUNT];
     __be32                     pad;
};
----

*hdr*::
The v5 directory/attribute block header.

*best_free*::
An array pointing to free regions in the directory block.

*pad*::
Padding to maintain a 64-bit alignment.

Within the block, data structures are as follows:

[source, c]
-----
typedef struct xfs_dir2_data_free {
     xfs_dir2_data_off_t        offset;
     xfs_dir2_data_off_t        length;
} xfs_dir2_data_free_t;
----

*offset*::
Block offset of a free block, in bytes.

*length*::
Length of the free block, in bytes.

Space inside the directory block can be used for directory entries or unused
entries.  This is signified via a union of the two types:

[source, c]
-----
typedef union {
     xfs_dir2_data_entry_t      entry;
     xfs_dir2_data_unused_t     unused;
} xfs_dir2_data_union_t;
----

*entry*::
A directory entry.

*unused*::
An unused entry.

[source, c]
-----
typedef struct xfs_dir2_data_entry {
     xfs_ino_t                  inumber;
     __uint8_t                  namelen;
     __uint8_t                  name[1];
     __uint8_t                  ftype;
     xfs_dir2_data_off_t        tag;
} xfs_dir2_data_entry_t;
----

*inumber*::
The inode number that this entry points to.

*namelen*::
Length of the name, in bytes.

*name*::
The name associated with this entry.

*ftype*::
The type of the inode.  This is used to avoid reading the inode while iterating
a directory.  The +XFS_SB_VERSION2_FTYPE+ feature must be set, or this field
will not be present.

*tag*::
Starting offset of the entry, in bytes.  This is used for directory iteration.

[source, c]
-----
typedef struct xfs_dir2_data_unused {
     __uint16_t                 freetag;  /* 0xffff */
     xfs_dir2_data_off_t        length;
     xfs_dir2_data_off_t        tag;
} xfs_dir2_data_unused_t;
----

*freetag*::
Magic number signifying that this is an unused entry.  Must be 0xFFFF.

*length*::
Length of this unused entry, in bytes.

*tag*::
Starting offset of the entry, in bytes.

[source, c]
-----
typedef struct xfs_dir2_leaf_entry {
     xfs_dahash_t               hashval;
     xfs_dir2_dataptr_t         address;
} xfs_dir2_leaf_entry_t;
----

*hashval*::
Hash value of the name of the directory entry.  This is used to speed up entry
lookups.

*address*::
Block offset of the entry, in eight byte units.

[source, c]
-----
typedef struct xfs_dir2_block_tail {
     __uint32_t                 count;
     __uint32_t                 stale;
} xfs_dir2_block_tail_t;
----

*count*::
Number of leaf entries.

*stale*::
Number of free leaf entries.

Following is a diagram of how these pieces fit together for a block directory.

.Block directory layout
image::images/43.png[]

* The magic number in the header is ``XD2B'' (0x58443242), or ``XDB3'' (0x58444233)
on a v5 filesystem.

* The +tag+ in the +xfs_dir2_data_entry_t+ structure stores its offset from the
start of the block.

* The start of a free space region is marked with the +xfs_dir2_data_unused_t+
structure where the +freetag+ is +0xffff+. The +freetag+ and +length+ overwrites
the +inumber+ for an entry. The +tag+ is located at +length - sizeof(tag)+ from
the start of the +unused+ entry on-disk.

* The +bestfree+ array in the header points to as many as three of the largest
spaces of free space within the block for storing new entries sorted by largest
to third largest. If there are less than 3 empty regions, the remaining
+bestfree+ elements are zeroed. The +offset+ specifies the offset from the start
of the block in bytes, and the +length+ specifies the size of the free space in
bytes. The location each points to must contain the above
+xfs_dir2_data_unused_t+ structure. As a block cannot exceed 64KB in size, each
is a 16-bit value. +bestfree+ is used to optimise the time required to locate
space to create an entry. It saves scanning through the block to find a location
suitable for every entry created.

* The +tail+ structure specifies the number of elements in the +leaf+ array and
the number of +stale+ entries in the array. The +tail+ is always located at the
end of the block. The +leaf+ data immediately precedes the +tail+ structure.

* The +leaf+ array, which grows from the end of the block just before the +tail+
structure, contains an array of hash/address pairs for quickly looking up a name
by a hash value. Hash values are covered by the introduction to directories. The
+address+ on-disk is the offset into the block divided by 8
(+XFS_DIR2_DATA_ALIGN+). Hash/address pairs are stored on disk to optimise
lookup speed for large directories. If they were not stored, the hashes would
have to be calculated for all entries each time a lookup occurs in a directory.


=== xfs_db Block Directory Example

A directory is created with 8 entries, directory block size = filesystem block size:

----
xfs_db> sb 0
xfs_db> p
magicnum = 0x58465342
blocksize = 4096
...
dirblklog = 0
...
xfs_db> inode <inode#>
xfs_db> p
core.magic = 0x494e
core.mode = 040755
core.version = 1
core.format = 2 (extents)
core.nlinkv1 = 2
...
core.size = 4096
core.nblocks = 1
core.extsize = 0
core.nextents = 1
...
u.bmx[0] = [startoff,startblock,blockcount,extentflag] 0:[0,2097164,1,0]
----

Go to the ``startblock'' and show the raw disk data:

----
xfs_db> dblock 0
xfs_db> type text
xfs_db> p
000: 58 44 32 42  01 30 0e 78 00 00 00 00 00 00 00 00 XD2B.0.x........
010: 00 00 00 00  02 00 00 80 01 2e 00 00 00 00 00 10 ................
020: 00 00 00 00  00 00 00 80 02 2e 2e 00 00 00 00 20 ................
030: 00 00 00 00  02 00 00 81 0f 66 72 61 6d 65 30 30 .........frame00
040: 30 30 30 30  2e 74 73 74 80 8e 59 00 00 00 00 30 0000.tst..Y....0
050: 00 00 00 00  02 00 00 82 0f 66 72 61 6d 65 30 30 .........frame00
060: 30 30 30 31  2e 74 73 74 d0 ca 5c 00 00 00 00 50 0001.tst.......P
070: 00 00 00 00  02 00 00 83 0f 66 72 61 6d 65 30 30 .........frame00
080: 30 30 30 32  2e 74 73 74 00 00 00 00 00 00 00 70 0002.tst.......p
090: 00 00 00 00  02 00 00 84 0f 66 72 61 6d 65 30 30 .........frame00
0a0: 30 30 30 33  2e 74 73 74 00 00 00 00 00 00 00 90 0003.tst........
0b0: 00 00 00 00  02 00 00 85 0f 66 72 61 6d 65 30 30 .........frame00
0c0: 30 30 30 34 2e 74 73 74 00 00 00 00 00 00 00 b0 0004.tst........
0d0: 00 00 00 00 02 00 00 86 0f 66 72 61 6d 65 30 30 .........frame00
0e0: 30 30 30 35 2e 74 73 74 00 00 00 00 00 00 00 d0 0005.tst........
0f0: 00 00 00 00 02 00 00 87 0f 66 72 61 6d 65 30 30 .........frame00
100: 30 30 30 36 2e 74 73 74 00 00 00 00 00 00 00 f0 0006.tst........
110: 00 00 00 00 02 00 00 88 0f 66 72 61 6d 65 30 30 .........frame00
120: 30 30 30 37 2e 74 73 74 00 00 00 00 00 00 01 10 0007.tst........
130: ff ff 0e 78 00 00 00 00 00 00 00 00 00 00 00 00 ...x............
----

The ``leaf'' and ``tail'' structures are stored at the end of the block, so as the
directory grows, the middle is filled in:

----
fa0: 00 00 00 00 00 00 01 30 00 00 00 2e 00 00 00 02 .......0........
fb0: 00 00 17 2e 00 00 00 04 83 a0 40 b4 00 00 00 0e ................
fc0: 93 a0 40 b4 00 00 00 12 a3 a0 40 b4 00 00 00 06 ................
fd0: b3 a0 40 b4 00 00 00 0a c3 a0 40 b4 00 00 00 1e ................
fe0: d3 a0 40 b4 00 00 00 22 e3 a0 40 b4 00 00 00 16 ................
ff0: f3 a0 40 b4 00 00 00 1a 00 00 00 0a 00 00 00 00 ................
----

In a readable format:

----
xfs_db> type dir2
xfs_db> p
bhdr.magic = 0x58443242
bhdr.bestfree[0].offset = 0x130
bhdr.bestfree[0].length = 0xe78
bhdr.bestfree[1].offset = 0
bhdr.bestfree[1].length = 0
bhdr.bestfree[2].offset = 0
bhdr.bestfree[2].length = 0
bu[0].inumber = 33554560
bu[0].namelen = 1
bu[0].name = "."
bu[0].tag = 0x10
bu[1].inumber = 128
bu[1].namelen = 2
bu[1].name = ".."
bu[1].tag = 0x20
bu[2].inumber = 33554561
bu[2].namelen = 15
bu[2].name = "frame000000.tst"
bu[2].tag = 0x30
bu[3].inumber = 33554562
bu[3].namelen = 15
bu[3].name = "frame000001.tst"
bu[3].tag = 0x50
...
bu[8].inumber = 33554567
bu[8].namelen = 15
bu[8].name = "frame000006.tst"
bu[8].tag = 0xf0
bu[9].inumber = 33554568
bu[9].namelen = 15
bu[9].name = "frame000007.tst"
bu[9].tag = 0x110
bu[10].freetag = 0xffff
bu[10].length = 0xe78
bu[10].tag = 0x130
bleaf[0].hashval = 0x2e
bleaf[0].address = 0x2
bleaf[1].hashval = 0x172e
bleaf[1].address = 0x4
bleaf[2].hashval = 0x83a040b4
bleaf[2].address = 0xe
...
bleaf[8].hashval = 0xe3a040b4
bleaf[8].address = 0x16
bleaf[9].hashval = 0xf3a040b4
bleaf[9].address = 0x1a
btail.count = 10
btail.stale = 0
----

[NOTE]
For block directories, all xfs_db fields are preceded with ``b''.

For a simple lookup example, the hash of frame000000.tst is 0xb3a040b4. Looking
up that value, we get an address of 0x6. Multiply that by 8, it becomes offset
0x30 and the inode at that point is 33554561. 

When we remove an entry from the middle (frame000004.tst), we can see how the
freespace details are adjusted:

----
bhdr.magic = 0x58443242
bhdr.bestfree[0].offset = 0x130
bhdr.bestfree[0].length = 0xe78
bhdr.bestfree[1].offset = 0xb0
bhdr.bestfree[1].length = 0x20
bhdr.bestfree[2].offset = 0
bhdr.bestfree[2].length = 0
...
bu[5].inumber = 33554564
bu[5].namelen = 15
bu[5].name = "frame000003.tst"
bu[5].tag = 0x90
bu[6].freetag = 0xffff
bu[6].length = 0x20
bu[6].tag = 0xb0
bu[7].inumber = 33554566
bu[7].namelen = 15
bu[7].name = "frame000005.tst"
bu[7].tag = 0xd0
...
bleaf[7].hashval = 0xd3a040b4
bleaf[7].address = 0x22
bleaf[8].hashval = 0xe3a040b4
bleaf[8].address = 0
bleaf[9].hashval = 0xf3a040b4
bleaf[9].address = 0x1a
btail.count = 10
btail.stale = 1
----

A new ``bestfree'' value is added for the entry, the start of the entry is marked
as unused with 0xffff (which overwrites the inode number for an actual entry),
and the length of the space. The tag remains intact at the +offset+length -
sizeof(tag)+. The address for the hash is also cleared. The affected areas are
highlighted below:

[subs="quotes"]
----
090: 00 00 00 00 02 00 00 84 0f 66 72 61 6d 65 30 30 ..........frame00
0a0: 30 30 30 33 2e 74 73 74 00 00 00 00 00 00 00 90 0003.tst.........
0b0: *ff ff 00 20* 02 00 00 85 0f 66 72 61 6d 65 30 30 ..........frame00
0c0: 30 30 30 34 2e 74 73 74 00 00 00 00 *00 00 00 b0* 0004.tst.........
0d0: 00 00 00 00 02 00 00 86 0f 66 72 61 6d 65 30 30 ..........frame00
0e0: 30 30 30 35 2e 74 73 74 00 00 00 00 00 00 00 0d 0005.tst.........
...
fb0: 00 00 17 2e 00 00 00 04 83 a0 40 b4 00 00 00 0e .................
fc0: 93 a0 40 b4 00 00 00 12 a3 a0 40 b4 00 00 00 06 .................
fd0: b3 a0 40 b4 00 00 00 0a c3 a0 40 b4 00 00 00 1e .................
fe0: d3 a0 40 b4 00 00 00 22 e3 a0 40 b4 *00 00 00 00* .................
ff0: f3 a0 40 b4 00 00 00 1a 00 00 00 0a *00 00 00 01* .................
----



[[Leaf_Directories]]
== Leaf Directories

Once a Block Directory has filled the block, the directory data is changed into
a new format. It still uses xref:Data_Extents[extents] and the same basic
structures, but the ``data'' and ``leaf'' are split up into their own extents. The
``leaf'' information only occupies one extent. As ``leaf'' information is more
compact than ``data'' information, more than one ``data'' extent is common.

* Block to Leaf conversions retain the existing block for the data entries and
allocate a new block for the leaf and freespace index information.

* As with all directories, data blocks must start at logical offset zero.

* The ``leaf'' block has a special offset defined by +XFS_DIR2_LEAF_OFFSET+.
Currently, this is 32GB and in the extent view, a block offset of
32GB / +sb_blocksize+. On a 4KB block filesystem, this is 0x800000 (8388608
decimal).

* Blocks with directory entries (``data'' extents) have the magic number ``X2D2''
(0x58443244), or ``XDD3'' (0x58444433) on a v5 filesystem.

* The ``data'' extents have a new header (no ``leaf'' data):

[source, c]
----
typedef struct xfs_dir2_data {
     xfs_dir2_data_hdr_t       hdr;
     xfs_dir2_data_union_t     u[1];
} xfs_dir2_data_t;
----

*hdr*::
Data block header.  On a v5 filesystem, this field is +struct xfs_dir3_data_hdr+.

*u*::
Union of directory and unused entries, exactly the same as in a block directory.

// split lists

* The ``leaf'' extent uses the following structures:

[source, c]
----
typedef struct xfs_dir2_leaf {
     xfs_dir2_leaf_hdr_t       hdr;
     xfs_dir2_leaf_entry_t     ents[1];
     xfs_dir2_data_off_t       bests[1];
     xfs_dir2_leaf_tail_t      tail;
} xfs_dir2_leaf_t;
----

*hdr*::
Directory leaf header.  On a v5 filesystem this is +struct
xfs_dir3_leaf_hdr_t+.

*ents*::
Hash values of the entries in this block.

*bests*::
An array pointing to free regions in the directory block.

*tail*::
Bookkeeping for the leaf entries.

[source, c]
----
typedef struct xfs_dir2_leaf_hdr {
     xfs_da_blkinfo_t          info;
     __uint16_t                count;
     __uint16_t                stale;
} xfs_dir2_leaf_hdr_t;
----

*info*::
Leaf btree block header.

*count*::
Number of leaf entries.

*stale*::
Number of stale/zeroed leaf entries.

[source, c]
----
struct xfs_dir3_leaf_hdr {
     struct xfs_da3_blkinfo    info;
     __uint16_t                count;
     __uint16_t                stale;
     __be32                    pad;
};
----

*info*::
Leaf B+tree block header.

*count*::
Number of leaf entries.

*stale*::
Number of stale/zeroed leaf entries.

*pad*::
Padding to maintain alignment rules.

[source, c]
----
typedef struct xfs_dir2_leaf_tail {
     __uint32_t                bestcount;
} xfs_dir2_leaf_tail_t;
----

*bestcount*::
Number of best free entries.

// split lists

* The magic number of the leaf block is +XFS_DIR2_LEAF1_MAGIC+ (0xd2f1); on a
v5 filesystem it is +XFS_DIR3_LEAF1_MAGIC+ (0x3df1).

* The size of the +ents+ array is specified by +hdr.count+.

* The size of the +bests+ array is specified by the +tail.bestcount+, which is
also the number of ``data'' blocks for  the directory. The bests array maintains
each data block's +bestfree[0].length+ value.

.Leaf directory free entry detail
image::images/48.png[]

=== xfs_db Leaf Directory Example

For this example, a directory was created with 256 entries (frame000000.tst to
frame000255.tst).  Some files were deleted (frame00005*, frame00018* and
frame000240.tst) to show free list characteristics.

----
xfs_db> inode <inode#>
xfs_db> p
core.magic = 0x494e
core.mode = 040755
core.version = 1
core.format = 2 (extents)
core.nlinkv1 = 2
...
core.size = 12288
core.nblocks = 4
core.extsize = 0
core.nextents = 3
...
u.bmx[0-2] = [startoff,startblock,blockcount,extentflag]
          0:[0,4718604,1,0]
          1:[1,4718610,2,0]
          2:[8388608,4718605,1,0]
----

As can be seen in this example, three blocks are used for ``data'' in two extents,
and the ``leaf'' extent has a logical offset of 8388608 blocks (32GB).

Examining the first block:

----
xfs_db> dblock 0
xfs_db> type dir2
xfs_db> p
dhdr.magic = 0x58443244
dhdr.bestfree[0].offset = 0x670
dhdr.bestfree[0].length = 0x140
dhdr.bestfree[1].offset = 0xff0
dhdr.bestfree[1].length = 0x10
dhdr.bestfree[2].offset = 0
dhdr.bestfree[2].length = 0
du[0].inumber = 75497600
du[0].namelen = 1
du[0].name = "."
du[0].tag = 0x10
du[1].inumber = 128
du[1].namelen = 2
du[1].name = ".."
du[1].tag = 0x20
du[2].inumber = 75497601
du[2].namelen = 15
du[2].name = "frame000000.tst"
du[2].tag = 0x30
du[3].inumber = 75497602
du[3].namelen = 15
du[3].name = "frame000001.tst"
du[3].tag = 0x50
...
du[51].inumber = 75497650
du[51].namelen = 15
du[51].name = "frame000049.tst"
du[51].tag = 0x650
du[52].freetag = 0xffff
du[52].length = 0x140
du[52].tag = 0x670
du[53].inumber = 75497661
du[53].namelen = 15
du[53].name = "frame000060.tst"
du[53].tag = 0x7b0
...
du[118].inumber = 75497758
du[118].namelen = 15
du[118].name = "frame000125.tst"
du[118].tag = 0xfd0
du[119].freetag = 0xffff
du[119].length = 0x10
du[119].tag = 0xff0
----

[NOTE]
The xfs_db field output is preceded by a ``d'' for ``data''.

The next ``data'' block:

----
xfs_db> dblock 1
xfs_db> type dir2
xfs_db> p
dhdr.magic = 0x58443244
dhdr.bestfree[0].offset = 0x6d0
dhdr.bestfree[0].length = 0x140
dhdr.bestfree[1].offset = 0xe50
dhdr.bestfree[1].length = 0x20
dhdr.bestfree[2].offset = 0xff0
dhdr.bestfree[2].length = 0x10
du[0].inumber = 75497759
du[0].namelen = 15
du[0].name = "frame000126.tst"
du[0].tag = 0x10
...
du[53].inumber = 75497844
du[53].namelen = 15
du[53].name = "frame000179.tst"
du[53].tag = 0x6b0
du[54].freetag = 0xffff
du[54].length = 0x140
du[54].tag = 0x6d0
du[55].inumber = 75497855
du[55].namelen = 15
du[55].name = "frame000190.tst"
du[55].tag = 0x810
...
du[104].inumber = 75497904
du[104].namelen = 15
du[104].name = "frame000239.tst"
du[104].tag = 0xe30
du[105].freetag = 0xffff
du[105].length = 0x20
du[105].tag = 0xe50
du[106].inumber = 75497906
du[106].namelen = 15
du[106].name = "frame000241.tst"
du[106].tag = 0xe70
...
du[117].inumber = 75497917
du[117].namelen = 15
du[117].name = "frame000252.tst"
du[117].tag = 0xfd0
du[118].freetag = 0xffff
du[118].length = 0x10
du[118].tag = 0xff0
----

And the last data block:


----
xfs_db> dblock 2
xfs_db> type dir2
xfs_db> p
dhdr.magic = 0x58443244
dhdr.bestfree[0].offset = 0x70
dhdr.bestfree[0].length = 0xf90
dhdr.bestfree[1].offset = 0
dhdr.bestfree[1].length = 0
dhdr.bestfree[2].offset = 0
dhdr.bestfree[2].length = 0
du[0].inumber = 75497918
du[0].namelen = 15
du[0].name = "frame000253.tst"
du[0].tag = 0x10
du[1].inumber = 75497919
du[1].namelen = 15
du[1].name = "frame000254.tst"
du[1].tag = 0x30
du[2].inumber = 75497920
du[2].namelen = 15
du[2].name = "frame000255.tst"
du[2].tag = 0x50
du[3].freetag = 0xffff
du[3].length = 0xf90
du[3].tag = 0x70
----

Examining the ``leaf'' block (with the fields preceded by an ``l'' for ``leaf''):

----
xfs_db> dblock 8388608
xfs_db> type dir2
xfs_db> p
lhdr.info.forw = 0
lhdr.info.back = 0
lhdr.info.magic = 0xd2f1
lhdr.count = 258
lhdr.stale = 0
lbests[0-2] = 0:0x10 1:0x10 2:0xf90
lents[0].hashval = 0x2e
lents[0].address = 0x2
lents[1].hashval = 0x172e
lents[1].address = 0x4
lents[2].hashval = 0x23a04084
lents[2].address = 0x116
...
lents[257].hashval = 0xf3a048bc
lents[257].address = 0x366
ltail.bestcount = 3
----

Note how the +lbests+ array correspond with the +bestfree[0].length+ values in
the ``data'' blocks:

----
xfs_db> dblock 0
xfs_db> type dir2
xfs_db> p
dhdr.magic = 0x58443244
dhdr.bestfree[0].offset = 0xff0
dhdr.bestfree[0].length = 0x10
...
xfs_db> dblock 1
xfs_db> type dir2
xfs_db> p
dhdr.magic = 0x58443244
dhdr.bestfree[0].offset = 0xff0
dhdr.bestfree[0].length = 0x10
...
xfs_db> dblock 2
xfs_db> type dir2
xfs_db> p
dhdr.magic = 0x58443244
dhdr.bestfree[0].offset = 0x70
dhdr.bestfree[0].length = 0xf90
----

Now after the entries have been deleted:

----
xfs_db> dblock 8388608
xfs_db> type dir2
xfs_db> p
lhdr.info.forw = 0
lhdr.info.back = 0
lhdr.info.magic = 0xd2f1
lhdr.count = 258
lhdr.stale = 21
lbests[0-2] = 0:0x140 1:0x140 2:0xf90
lents[0].hashval = 0x2e
lents[0].address = 0x2
lents[1].hashval = 0x172e
lents[1].address = 0x4
lents[2].hashval = 0x23a04084
lents[2].address = 0x116
...
----

As can be seen, the +lbests+ values have been update to contain each
+hdr.bestfree[0].length+ values. The leaf's +hdr.stale+ value has also been
updated to specify the number of stale entries in the array. The stale entries
have an address of zero.

TODO: Need an example for where new entries get inserted with several large free
spaces.


[[Node_Directories]]
== Node Directories

When the ``leaf'' information fills a block, the extents undergo another
separation. All ``freeindex'' information moves into its own extent. Like Leaf
Directories, the ``leaf'' block maintained the best free space information for
each ``data'' block. This is not possible with more than one leaf.

* The ``data'' blocks stay the same as leaf directories.

* After the ``freeindex'' data moves to its own block, it is possible for the
leaf data to fit within a single leaf block.  This single leaf block has a
magic number of +XFS_DIR2_LEAFN_MAGIC+ (0xd2ff) or on a v5 filesystem,
+XFS_DIR3_LEAFN_MAGIC+ (0x3dff).

* The ``leaf'' blocks eventually change into a B+tree with the generic B+tree
header pointing to directory ``leaves'' as described in
xref:Leaf_Directories[Leaf Directories]. Blocks with leaf data still have the
+LEAFN_MAGIC+ magic number as outlined above.  The top-level tree blocks are
called ``nodes'' and have a magic number of +XFS_DA_NODE_MAGIC+ (0xfebe), or on
a v5 filesystem, +XFS_DA3_NODE_MAGIC+ (0x3ebe).

* Distinguishing between a combined leaf/freeindex block (+LEAF1_MAGIC+), a
leaf-only block (+LEAFN_MAGIC+), and a btree node block (+NODE_MAGIC+) can only
be done by examining the magic number.

* The new ``freeindex'' block(s) only contains the bests for each data block.

* The freeindex block uses the following structures:

[source, c]
----
typedef struct xfs_dir2_free_hdr {
     __uint32_t                magic;
     __int32_t                 firstdb;
     __int32_t                 nvalid;
     __int32_t                 nused;
} xfs_dir2_free_hdr_t;
----

*magic*::
The magic number of the free block, ``XD2F'' (0x0x58443246).

*firstdb*::
The starting directory block number for the bests array.

*nvalid*::
Number of elements in the bests array.

*nused*::
Number of valid elements in the bests array.

[source, c]
----
typedef struct xfs_dir2_free {
     xfs_dir2_free_hdr_t       hdr;
     xfs_dir2_data_off_t       bests[1];
} xfs_dir2_free_t;
----

*hdr*::
Free block header.

*bests*::
An array specifying the best free counts in each directory data block.

// split lists

* On a v5 filesystem, the freeindex block uses the following structures:

[source, c]
----
struct xfs_dir3_free_hdr {
     struct xfs_dir3_blk_hdr   hdr;
     __int32_t                 firstdb;
     __int32_t                 nvalid;
     __int32_t                 nused;
     __int32_t                 pad;
};
----

*hdr*::
v3 directory block header.  The magic number is "XDF3" (0x0x58444633).

*firstdb*::
The starting directory block number for the bests array.

*nvalid*::
Number of elements in the bests array.

*nused*::
Number of valid elements in the bests array.

*pad*::
Padding to maintain alignment.

[source, c]
----
struct xfs_dir3_free {
     xfs_dir3_free_hdr_t       hdr;
     __be16                    bests[1];
};
----

*hdr*::
Free block header.

*bests*::
An array specifying the best free counts in each directory data block.

// split lists

* The location of the leaf blocks can be in any order, the only way to determine
the appropriate is by the node block hash/before values. Given a hash to look up,
you read the node's +btree+ array and first +hashval+ in the array that exceeds
the given hash and it can then be found in the block pointed to by the +before+
value. 

// split lists

* The freeindex's +bests+ array starts from the end of the block and grows to the
start of the block.

* When an data block becomes unused (ie. all entries in it have been deleted), the
block is freed, the data extents contain a hole, and the freeindex's +hdr.nused+
value is decremented and the associated +bests[]+ entry is set to 0xffff. 

* As the first data block always contains ``.'' and ``..'', it's invalid for the
directory to have a hole at the start.

* The freeindex's +hdr.nvalid+ should always be the same as the number of
allocated data directory blocks containing name/inode data and will always be
less than or equal to +hdr.nused+.  The value of +hdr.nused+ should be the same
as the index of the last data directory block plus one (i.e. when the last data
block is freed, +nused+ and +nvalid+ are decremented).

.Node directory layout
image::images/54.png[]

=== xfs_db Node Directory Example

With the node directory examples, we are using a filesystems with 4KB block
size, and a 16KB directory size. The directory has over 2000 entries:

----
xfs_db> sb 0
xfs_db> p
magicnum = 0x58465342
blocksize = 4096
...
dirblklog = 2
...
xfs_db> inode <inode#>
xfs_db> p
core.magic = 0x494e
core.mode = 040755
core.version = 1
core.format = 2 (extents)
...
core.size = 81920
core.nblocks = 36
core.extsize = 0
core.nextents = 8
...
u.bmx[0-7] = [startoff,startblock,blockcount,extentflag] 0:[0,7368,4,0]
1:[4,7408,4,0] 2:[8,7444,4,0] 3:[12,7480,4,0] 4:[16,7520,4,0]
5:[8388608,7396,4,0] 6:[8388612,7524,8,0] 7:[16777216,7516,4,0]
----

As can already be observed, all extents are allocated is multiples of 4 blocks.

Blocks 0 to 19 (16+4-1) are used for directory data blocks. Looking at blocks
16-19, we can seen that it's the same as the single-leaf format, except the
+length+ values are a lot larger to accommodate the increased directory block
size:

----
xfs_db> dblock 16
xfs_db> type dir2
xfs_db> p
dhdr.magic = 0x58443244
dhdr.bestfree[0].offset = 0xb0
dhdr.bestfree[0].length = 0x3f50
dhdr.bestfree[1].offset = 0
dhdr.bestfree[1].length = 0
dhdr.bestfree[2].offset = 0
dhdr.bestfree[2].length = 0
du[0].inumber = 120224
du[0].namelen = 15
du[0].name = "frame002043.tst"
du[0].tag = 0x10
du[1].inumber = 120225
du[1].namelen = 15
du[1].name = "frame002044.tst"
du[1].tag = 0x30
du[2].inumber = 120226
du[2].namelen = 15
du[2].name = "frame002045.tst"
du[2].tag = 0x50
du[3].inumber = 120227
du[3].namelen = 15
du[3].name = "frame002046.tst"
du[3].tag = 0x70
du[4].inumber = 120228
du[4].namelen = 15
du[4].name = "frame002047.tst"
du[4].tag = 0x90
du[5].freetag = 0xffff
du[5].length = 0x3f50
du[5].tag = 0
----

Next, the ``node'' block, the fields are preceded with 'n' for node blocks:

----
xfs_db> dblock 8388608
xfs_db> type dir2
xfs_db> p
nhdr.info.forw = 0
nhdr.info.back = 0
nhdr.info.magic = 0xfebe
nhdr.count = 2
nhdr.level = 1
nbtree[0-1] = [hashval,before] 0:[0xa3a440ac,8388616] 1:[0xf3a440bc,8388612]
----

The two following leaf blocks were allocated as part of the directory's
conversion to node format.  All hashes less than 0xa3a440ac are located at
directory offset 8,388,616, and hashes less than 0xf3a440bc are located at
directory offset 8,388,612.  Hashes greater or equal to 0xf3a440bc don't exist
in this directory.

----
xfs_db> dblock 8388616
xfs_db> type dir2
xfs_db> p
lhdr.info.forw = 8388612
lhdr.info.back = 0
lhdr.info.magic = 0xd2ff
lhdr.count = 1023
lhdr.stale = 0
lents[0].hashval = 0x2e
lents[0].address = 0x2
lents[1].hashval = 0x172e
lents[1].address = 0x4
lents[2].hashval = 0x23a04084
lents[2].address = 0x116
...
lents[1021].hashval = 0xa3a440a4
lents[1021].address = 0x1fa2
lents[1022].hashval = 0xa3a440ac
lents[1022].address = 0x1fca
xfs_db> dblock 8388612
xfs_db> type dir2
xfs_db> p
lhdr.info.forw = 0
lhdr.info.back = 8388616
lhdr.info.magic = 0xd2ff
lhdr.count = 1027
lhdr.stale = 0
lents[0].hashval = 0xa3a440b4
lents[0].address = 0x1f52
lents[1].hashval = 0xa3a440bc
lents[1].address = 0x1f7a
...
lents[1025].hashval = 0xf3a440b4
lents[1025].address = 0x1f66
lents[1026].hashval = 0xf3a440bc
lents[1026].address = 0x1f8e
----

An example lookup using xfs_db:

----
xfs_db> hash frame001845.tst
0xf3a26094
----

Doing a binary search through the array, we get address 0x1ce6, which is offset
0xe730. Each fsblock is 4KB in size (0x1000), so it will be offset 0x730 into
directory offset 14. From the extent map, this will be fsblock 7482:

----
xfs_db> fsblock 7482
xfs_db> type text
xfs_db> p
...
730: 00 00 00 00 00 01 d4 da 0f 66 72 61 6d 65 30 30 .........frame00
740: 31 38 34 35 2e 74 73 74 00 00 00 00 00 00 27 30 1845.tst.......0
----

Looking at the freeindex information (fields with an 'f' tag):

----
xfs_db> fsblock 7516
xfs_db> type dir2
xfs_db> p
fhdr.magic = 0x58443246
fhdr.firstdb = 0
fhdr.nvalid = 5
fhdr.nused = 5
fbests[0-4] = 0:0x10 1:0x10 2:0x10 3:0x10 4:0x3f50
----

Like the Leaf Directory, each of the +fbests+ values correspond to each data
block's +bestfree[0].length+ value. 

The +fbests+ array is highlighted in a raw block dump:

[subs="quotes"]
----
xfs_db> type text
xfs_db> p
000: 58 44 32 46 00 00 00 00 00 00 00 05 00 00 00 05 XD2F............
010: *00 10 00 10 00 10 00 10 3f 50* 00 00 1f 01 ff ff .........P......
----

TODO: Example with a hole in the middle


[[Btree_Directories]]
== B+tree Directories

When the extent map in an inode grows beyond the inode's space, the inode format
is changed to a ``btree''. The inode contains a filesystem block point to the
B+tree extent map for the directory's blocks. The B+tree extents contain the
extent map for the ``data'', ``node'', ``leaf'', and ``freeindex'' information as
described in Node Directories.

Refer to the previous section on B+tree xref:Btree_Extent_List[Data Extents] for
more information on XFS B+tree extents.

The following properties apply to both node and B+tree directories:

* The node/leaf trees can be more than one level deep.

* More than one freeindex block may exist, but this will be quite rare. It would
required hundreds of thousand files with quite long file names (or millions with
shorter names) to get a second freeindex block.

=== xfs_db B+tree Directory Example

A directory has been created with 200,000 entries with each entry being 100
characters long. The filesystem block size and directory block size are 4KB:

----
xfs_db> inode <inode#>
xfs_db> p
core.magic = 0x494e
core.mode = 040755
core.version = 1
core.format = 3 (btree)
...
core.size = 22757376
core.nblocks = 6145
core.extsize = 0
core.nextents = 234
core.naextents = 0
core.forkoff = 0
...
u.bmbt.level = 1
u.bmbt.numrecs = 1
u.bmbt.keys[1] = [startoff] 1:[0]
u.bmbt.ptrs[1] = 1:89
xfs_db> fsblock 89
xfs_db> type bmapbtd
xfs_db> p
magic = 0x424d4150
level = 0
numrecs = 234
leftsib = null
rightsib = null
recs[1-234] = [startoff,startblock,blockcount,extentflag]
   1:[0,53,1,0] 2:[1,55,13,0] 3:[14,69,1,0] 4:[15,72,13,0]
   5:[28,86,2,0] 6:[30,90,21,0] 7:[51,112,1,0] 8:[52,114,11,0]
   ...
   125:[5177,902,15,0] 126:[5192,918,6,0] 127:[5198,524786,358,0]
   128:[8388608,54,1,0] 129:[8388609,70,2,0] 130:[8388611,85,1,0]
   ...
   229:[8389164,917,1,0] 230:[8389165,924,19,0] 231:[8389184,944,9,0]
   232:[16777216,68,1,0] 233:[16777217,7340114,1,0] 234:[16777218,5767362,1,0]
----

We have 128 extents and a total of 5555 blocks being used to store name/inode
pairs. With only about 2000 values that can be stored in the freeindex block, 3
blocks have been allocated for this information. The +firstdb+ field specifies
the starting directory block number for each array:

----
xfs_db> dblock 16777216
xfs_db> type dir2
xfs_db> p
fhdr.magic = 0x58443246
fhdr.firstdb = 0
fhdr.nvalid = 2040
fhdr.nused = 2040
fbests[0-2039] = ...
xfs_db> dblock 16777217
xfs_db> type dir2
xfs_db> p
fhdr.magic = 0x58443246
fhdr.firstdb = 2040
fhdr.nvalid = 2040
fhdr.nused = 2040
fbests[0-2039] = ...
xfs_db> dblock 16777218
xfs_db> type dir2
xfs_db> p
fhdr.magic = 0x58443246
fhdr.firstdb = 4080
fhdr.nvalid = 1476
fhdr.nused = 1476
fbests[0-1475] = ...
----

Looking at the root node in the node block, it's a pretty deep tree:

----
xfs_db> dblock 8388608
xfs_db> type dir2
xfs_db> p
nhdr.info.forw = 0
nhdr.info.back = 0
nhdr.info.magic = 0xfebe
nhdr.count = 2
nhdr.level = 2
nbtree[0-1] = [hashval,before] 0:[0x6bbf6f39,8389121] 1:[0xfbbf7f79,8389120]
xfs_db> dblock 8389121
xfs_db> type dir2
xfs_db> p
nhdr.info.forw = 8389120
nhdr.info.back = 0
nhdr.info.magic = 0xfebe
nhdr.count = 263
nhdr.level = 1
nbtree[0-262] = ... 262:[0x6bbf6f39,8388928]
xfs_db> dblock 8389120
xfs_db> type dir2
xfs_db> p
nhdr.info.forw = 0
nhdr.info.back = 8389121
nhdr.info.magic = 0xfebe
nhdr.count = 319
nhdr.level = 1
nbtree[0-318] = [hashval,before] 0:[0x70b14711,8388919] ...
----

The leaves at each the end of a node always point to the end leaves in adjacent
nodes. Directory block 8388928 has a forward pointer to block 8388919 and block
8388919 has a previous pointer to block 8388928, as highlighted in the
following example:

[subs="quotes"]
----
xfs_db> dblock 8388928
xfs_db> type dir2
xfs_db> p
lhdr.info.forw = *8388919*
lhdr.info.back = 8388937
lhdr.info.magic = 0xd2ff
...

xfs_db> dblock 8388919
xfs_db> type dir2
xfs_db> p
lhdr.info.forw = 8388706
lhdr.info.back = *8388928*
lhdr.info.magic = 0xd2ff
...
----