Extent Trees and the Replacement of Indirect Block Maps

The original Unix block map answers one question per entry: given a logical block number, which physical block holds it? A file’s metadata is an array of answers, and the array is indexed directly for the first twelve blocks, then through one, two, or three levels of pointer blocks. The scheme is compact for small files and pessimal for large contiguous ones, because a gigabyte file needs a pointer entry for every 4 KiB of data no matter how sequential that data is.

An extent replaces the per-block answer with a range answer. Instead of “logical block 900 is physical block 40012”, the record says “logical blocks 800 through 1023 are physical blocks 40000 through 40223”. One record covers 224 blocks. The format that stores a sorted set of such records is a tree, and the tree’s root lives in the inode’s own 60-byte pointer area.

The shape of a record

An extent is twelve bytes: a 32-bit logical block number, a 16-bit length, and a 48-bit physical block number. The length field counts blocks, not bytes, and it is overloaded. A value of 32768 or less is an initialised extent of that many blocks. A value above 32768 is an uninitialised extent, and its real length is the value minus 32768. The maximum initialised extent is therefore 32768 blocks and the maximum uninitialised one is 32767, which at a 4 KiB block size caps a single extent at 128 MiB. A file larger than that necessarily has more than one extent even if it is perfectly contiguous on disk.

struct ext4_extent {
    __le32 ee_block;      /* first logical block covered */
    __le16 ee_len;        /* blocks; >32768 means uninit, minus 32768 */
    __le16 ee_start_hi;   /* high 16 bits of the physical block */
    __le32 ee_start_lo;   /* low 32 bits */
};

The 48-bit physical block field is a deliberate compromise. A 32-bit field caps a filesystem at 2^32 blocks, which at 4 KiB per block is 16 TiB; the extra 16 bits raise the cap to 2^48 blocks, far beyond any current device, while keeping the record at twelve bytes so that a node header plus four records fit in the inode’s 60-byte area with no padding.

A length above 32768 marks an uninitialised extent. Such an extent has blocks allocated on disk but no data written to them; reads return zeroes without touching the device. Preallocation uses this to reserve contiguous space without paying for the write, and a subsequent write converts the range to initialised in place. A driver that ignores the flag returns whatever stale bytes the device holds.

Why the root lives in the inode

The inode’s pointer area is 60 bytes, located by the arithmetic in Inode Tables and the Arithmetic of Inode Numbers. An extent tree node header takes twelve of them: a magic value, the number of valid entries, the maximum entries the node can hold, the depth, and a generation number. That leaves 48 bytes, exactly four extent records. So a file with up to four extents, or up to 4 × 32768 blocks if each extent is maximal, needs no external metadata whatsoever: opening it reads one inode and the entire block map is in hand.

The threshold matters in practice because most files are small and most small files are contiguous. A file under roughly 128 MiB that was written once in one pass typically has one or two extents and therefore an entirely in-inode map. The lookup cost for such a file is zero additional I/O, which is strictly better than the indirect scheme, where even a 100 KiB file needs a pointer block read.

struct ext4_extent_header {
    __le16 eh_magic;      /* 0xF30A */
    __le16 eh_entries;    /* records in use */
    __le16 eh_max;        /* capacity of this node */
    __le16 eh_depth;      /* 0 = leaf, >0 = index node */
    __le32 eh_generation;
};

struct ext4_extent_idx {
    __le32 ei_block;      /* first logical block of the subtree */
    __le32 ei_leaf_lo;
    __le16 ei_leaf_hi;
    __le16 ei_unused;
};

When the fourth extent is not enough, the root stops holding extent records and starts holding index entries, and eh_depth becomes 1. An index entry is also twelve bytes and holds a logical block number plus a pointer to a child node, so the inode’s area now holds four pointers. Each child is a full block whose header says how many records it holds and at what depth. The tree grows by adding a level at the root, never by moving the root, which is why the inode’s layout does not change as the file grows.

Splitting, and what triggers it

Insertion into a leaf is ordered by logical block number. A new extent that overlaps an existing one is not inserted; it either extends the existing record, if it is physically and logically adjacent, or splits it, if it covers a range inside it. Splitting an extent produces two or three records from one, and the leaf may then exceed eh_max, at which point it splits into two leaves and a new index entry is added to the parent, which may in turn split.

Two records merge when they are logically adjacent and physically adjacent, which is the mechanism that keeps a sequentially written file at one extent despite being written in many small appends: each append extends the last extent rather than adding a new one. The condition is exact, not approximate: the physical block following the last block of record i must be the first block of record i+1, and the logical numbers must be consecutive. A single out-of-order allocation in the middle of a write breaks the chain permanently, because the format has no way to record a gap as part of an extent.

Fragmentation is therefore visible in the tree. A file written in one pass on an empty filesystem has one extent; the same file rewritten in place block by block, with other allocations interleaved, has as many extents as there were interruptions. A leaf node in a 4 KiB block holds (4096 - 12) / 12, or 340, extent records, so a single full leaf can describe more than eleven million blocks. Depth grows only when the number of disjoint physical ranges exceeds what one level can index, which is why even a badly fragmented file usually has a tree two levels deep.

Reading a logical block through the tree

Lookup descends from the root, at each index node selecting the last entry whose logical block is not greater than the target. The invariant that makes this correct is that each index entry’s logical block is the first block covered by its subtree, and the entries are sorted, so the appropriate child is found by a binary search or a linear scan from the end.

/* Schematic descent: at each index node pick the last entry whose
 * logical block is <= the target, then scan the leaf. */
struct extent *lookup(struct inode *in, uint32_t lblk)
{
        struct header *h = inode_extent_header(in);
        void *node = h;
        while (h->depth > 0) {                    /* 0 means this is a leaf */
                struct index_entry *ix = (char *)node + sizeof(*h);
                int i = h->entries - 1;
                while (i > 0 && ix[i].logical > lblk)
                        i--;                      /* entries are sorted */
                node = read_block(ix[i].leaf);
                h = node;
        }
        for (int i = 0; i < h->entries; i++)      /* binary search in practice */
                if (covers(&h->extent[i], lblk))
                        return &h->extent[i];
        return NULL;
}

A lookup at depth d costs d block reads, none of which are cached by the format itself; the page cache or the buffer cache may hold them, and the driver may cache the last few nodes per inode. Because the tree is a search structure over logical block numbers, a sequential read pattern resolves the same leaf repeatedly: the reader walks the leaf’s records in order rather than re-descending for every block.

The invariants a repair tool checks

The tree is a set of claims about which physical blocks belong to the file, and the repair pass has to verify them against the block bitmap. Three invariants are structural: every node’s entries are sorted by logical block, no two extents in a leaf overlap, and every index entry’s logical block equals the first logical block of the subtree it points to. A violation of any of these means the map cannot be trusted and must be rebuilt.

Two more are semantic: the sum of the extents’ lengths must be consistent with the inode’s size field, and the physical ranges must not collide with blocks claimed by another inode. A collision is the more serious finding, because it means two files believe they own the same bytes; the repair resolves it by keeping one claim and truncating the other. That resolution order, and why it must come after the inode scan and before the directory check, is the subject of fsck and the Ordering of Repairs.

The extent tree is a good illustration of a general pattern in on-disk design: when the common case is contiguous and the general case is not, store the common case inline in the object’s own record and make the general case a tree that grows outward. The inode stays the same size, the small file stays cheap, and the large fragmented file pays only for the structure it actually needs.