Extents (ext4 / xfs)

Indirect-block addressing (ext2/3) is wasteful for large contiguous files: 1 GiB file = 1 GiB / 4 KiB = 262144 pointers + indirection overhead.

Extents: each extent describes a contiguous run.

struct extent {
    uint32_t logical_block;   // file offset (in blocks)
    uint16_t length;          // # of contiguous blocks (max 32768)
    uint16_t physical_hi;
    uint32_t physical_lo;     // start block on disk
};

For a contiguous 1 GiB file: 1 extent = 12 bytes describes everything. vs 1 MiB of pointers.

For fragmented files: multiple extents.

Extent tree (when too many to fit inline):

• Inode has root entries.
• Internal nodes: index extents (point to other extent blocks).
• Leaf nodes: actual extents.
• B+ tree-style.

Insertion + lookup: O(log F) where F = number of extents.

Lookup file block by offset:

1. Start at inode's extent tree root.
2. Binary search for logical_block in current node.
3. Descend if internal; else compute physical block = phys_start + (logical_block - extent_logical).

Allocation strategy with extents:

• Try to extend existing extent (allocate next contiguous block).
• Reduces fragmentation.
• Failing that: pick new region.

ext2 had no extents — millions of indirect block walks for big files = slow.

Modern FS (ext4, xfs, btrfs, NTFS) all use extents.

Trade-off:

• Extents efficient for large contiguous files.
• For small/fragmented files, pointer-block approach was simpler.
• Hybrid: extents for size + pointer fallback in some FS.