Ext2/Ext3/Ext4 File Systems

Consider a 4 GB video file stored on an ext2/ext3 filesystem with 4 KB blocks. To describe where all that data lives on disk, the filesystem must maintain approximately one million block pointers—each pointing to a single 4 KB block. These pointers consume over 4 MB of space just for metadata, and accessing the file requires traversing multiple levels of indirect blocks.

Now imagine describing that same file with a single statement: "Logical blocks 0 through 1,048,575 are stored contiguously starting at physical block 50,000,000." One structure, one lookup, done.

This is the power of extents—ext4's revolutionary approach to block mapping. Rather than maintaining exhaustive lists of individual blocks, extents describe contiguous ranges. A perfectly contiguous file requires only a single extent, regardless of size. Even fragmented files typically need just a handful of extents.

The result: dramatic reductions in metadata overhead, faster file access, and more efficient use of disk space. Extents are the single most impactful feature distinguishing ext4 from its predecessors.

Before appreciating extents, let's understand what they replace: the indirect block scheme used by ext2/ext3.

ext2/ext3 Block Pointer Structure:

The traditional inode contains 15 block pointers:

i_block[0-11]:   12 direct pointers (point directly to data blocks)
i_block[12]:     1 indirect pointer (points to block of pointers)
i_block[13]:     1 double indirect pointer (pointer → pointers → pointers)
i_block[14]:     1 triple indirect pointer (three levels of indirection)

Capacity Calculations (4 KB blocks, 4-byte pointers):

Total maximum file size: ~4 TB (with 4 KB blocks)

Problems with Indirect Blocks:

1. Excessive Metadata for Large Files

   • A 1 GB file needs ~256,000 block pointers
   • These pointers require ~250 indirect blocks (1 MB of metadata)
   • Metadata scales linearly with file size

2. Multiple Disk Seeks for Access

   • Accessing block 1,000,000 requires:
     • Read inode → Read double indirect → Read indirect → Read data
     • 4 disk accesses for a single block (uncached)

3. Fragmented Pointer Storage

   • Indirect blocks themselves may be scattered
   • Sequential file read becomes random I/O for pointers

4. Inefficient for Contiguous Data

   • Even perfectly sequential file storage needs individual pointers
   • No way to express "1,000 blocks starting at X"

An extent is a compact descriptor for a contiguous range of blocks. Instead of "block 100, block 101, block 102, ..., block 200," an extent says "100 blocks starting at block 100."

ext4 Extent Structure:

Extent Field Details:

Maximum Single Extent:

• Length: 32,768 blocks (0x8000, with high bit reserved)
• At 4 KB blocks: 128 MB per extent
• A 1 GB file needs minimum 8 extents (if contiguous)

Physical Block Addressing: The 48-bit physical block address enables addressing:

2^48 blocks × 4 KB = 1 Exabyte (1,152,921,504,606,846,976 bytes)

Uninitialized Extents: The high bit of ee_len marks uninitialized (preallocated but unwritten) extents:

#define EXT_INIT_MAX_LEN    32768   // Max initialized extent
#define EXT_UNWRITTEN_MAX_LEN 32768 // Max unwritten extent
#define EXT4_EXT_UNWRITTEN  0x8000  // Flag for unwritten

bool is_unwritten(struct ext4_extent *ext) {
    return ext->ee_len & cpu_to_le16(EXT4_EXT_UNWRITTEN);
}

uint16_t extent_length(struct ext4_extent *ext) {
    return le16_to_cpu(ext->ee_len) & ~EXT4_EXT_UNWRITTEN;
}

Uninitialized extents represent space reserved via fallocate() but not yet written. Reading them returns zeros without accessing disk.

While many files can be described by a handful of extents fitting directly in the inode, fragmented files may need hundreds or thousands of extents. The extent tree organizes these efficiently.

Inode Extent Storage:

The inode's i_block field (60 bytes) is reused for extent storage:

+-------------------+
| Extent Header     |  12 bytes
+-------------------+
| Extent/Index 0    |  12 bytes
+-------------------+
| Extent/Index 1    |  12 bytes
+-------------------+
| Extent/Index 2    |  12 bytes
+-------------------+
| Extent/Index 3    |  12 bytes
+-------------------+

Total: 60 bytes = 1 header + 4 entries

With 4 extents in the inode, a file with < 5 fragments needs no additional blocks for metadata.

Tree Depth and Capacity:

Each tree block (4 KB) holds:

• 1 header (12 bytes)
• (4096 - 12) / 12 = 340 entries

*Assuming each extent covers 128 MB (32,768 blocks)

Binary Search for Lookup:

Extent tree lookup is O(depth × log(entries)):

struct ext4_extent *ext4_find_extent(inode, logical_block) {
    struct ext4_extent_header *eh = inode->i_block;
    
    while (eh->eh_depth > 0) {
        // Binary search for containing index
        struct ext4_extent_idx *idx = binary_search(
            (struct ext4_extent_idx *)(eh + 1),
            eh->eh_entries,
            logical_block
        );
        
        // Follow index to child block
        pblock = idx->ei_leaf;
        eh = read_block(pblock);
    }
    
    // At leaf level: binary search for extent
    return binary_search(
        (struct ext4_extent *)(eh + 1),
        eh->eh_entries,
        logical_block
    );
}

ext4's multiblock allocator (mballoc) is designed to create large, contiguous extents whenever possible.

Delayed Allocation:

The key to effective extent allocation is delayed allocation (delalloc):

1. Application writes data to page cache
2. Kernel marks pages dirty but DOESN'T allocate disk blocks
3. At writeback time (or sync), kernel knows the full write size
4. Allocator finds contiguous space for the entire write
5. Single extent covers what could have been many small allocations

Allocation Goals:

The allocator tries to place new extents:

1. Adjacent to previous extent: Extends contiguous range, may merge
2. In same block group as inode: Locality benefit
3. In block group with most free space: Maximizes contiguous potential

Extent Merging:

When a new extent is adjacent to an existing one, they merge:

before: [extent: blocks 0-99 @ 1000-1099]
        [extent: blocks 100-199 @ 1100-1199]  // Adjacent!

after:  [extent: blocks 0-199 @ 1000-1199]    // Merged!

Merging reduces extent count and improves access patterns.

Preallocation with fallocate():

# Preallocate 1 GB for a database file
fallocate -l 1G /var/lib/db/data.db

// Kernel creates uninitialized extent(s)
extent: ee_block=0, ee_len=262144|UNWRITTEN, ee_start=1000000
// 1 million blocks reserved, marked unwritten
// Reads return zeros, writes convert to written

Preallocation guarantees contiguous space, essential for databases and VMs.

The extent tree supports efficient insert, delete, and split operations to maintain a balanced, searchable structure.

Inserting a New Extent:

1. Find insertion point (binary search)
2. If adjacent to existing extent: merge
3. If room in leaf block: insert directly
4. If leaf full: split leaf, redistribute entries
5. If split propagates up: may need new root

Truncating (Removing Extents):

When a file is truncated or deleted, extents must be removed:

1. Find extent(s) covering truncation point
2. For partial first extent: shrink its length
3. For fully covered extents: remove entirely
4. Free physical blocks to block allocator
5. If tree becomes sparse: may reduce depth

Punch Hole (Sparse Files):

ext4 supports punching holes in existing files:

fallocate -p -o 1G -l 100M largefile.dat
# Deallocates 100 MB starting at offset 1 GB

The result is a sparse file where reading the hole returns zeros without consuming disk space:

before: [extent: 0-500000]
hole:   [remove blocks 250000-274999]
after:  [extent: 0-249999] [gap] [extent: 275000-500000]

Extent Status Tree:

ext4 maintains an in-memory cache of extent status:

struct extent_status {
    struct rb_node  rb_node;    // Red-black tree node
    ext4_lblk_t     es_lblk;    // Logical block
    ext4_lblk_t     es_len;     // Length
    ext4_fsblk_t    es_pblk;    // Physical block (or 0 for hole)
    unsigned int    es_status;  // Written, unwritten, delayed, hole
};

This cache enables O(log n) extent lookups without disk I/O, crucial for performance with large files.

Extents provide multiple layers of performance improvement over indirect blocks.

1. Reduced Metadata Overhead:

2. Faster Sequential Access:

With extents, sequential read/write knows the entire contiguous range:

// With indirect blocks
for (block = 0; block < 1000000; block++) {
    pblock = lookup_indirect(block);  // Up to 4 lookups each
    read_block(pblock);
}

// With extents
extent = lookup_extent(0);  // One lookup
for (block = 0; block < extent.len; block++) {
    read_block(extent.start + block);  // No more lookups!
}

3. Better Disk Scheduling:

Knowing contiguous ranges enables:

• Larger I/O requests (1 request for 128 MB vs 32,768 requests)
• Optimal disk head scheduling
• Better NCQ/TCQ utilization on modern drives

4. Efficient Sparse Files:

Extents naturally represent holes (gaps in logical-to-physical mapping):

File with hole:
  [extent: blocks 0-99 @ physical 1000-1099]
  (no extent for blocks 100-199 = hole)
  [extent: blocks 200-299 @ physical 2000-2099]

Reading blocks 100-199 returns zeros without disk access.

Understanding how to inspect, optimize, and troubleshoot extent-based files is essential for system administration.

Viewing Extent Information:

Defragmenting Extent Files:

# Online defragmentation (ext4 only)
e4defrag /path/to/file    # Defragment single file
e4defrag /mount/point     # Defragment entire filesystem
e4defrag -v /path/to/file # Verbose output

# Check fragmentation score
filefrag largefile.dat
# "8 extents found" - lower is better

# Pre-defrag: check if worth it
e4defrag -c /path/to/file
# Shows current vs optimal extent count

Preallocation Strategies:

# Create contiguous preallocated file
fallocate -l 10G /var/lib/mysql/ibdata1

# Posix-style (portable)
dd if=/dev/zero of=datafile bs=1M count=10240 status=progress

# For databases: ensure files stay contiguous
# MySQL: innodb_file_per_table = OFF (single large file)
# PostgreSQL: Set large segment size at initdb

Converting Indirect → Extent:

Files created before ext4 or with extent disabled use indirect blocks:

# Enable extent feature on filesystem
tune2fs -O extent /dev/sda1

# Existing files remain indirect
# To convert: must rewrite file
cp oldfile newfile  # newfile uses extents
mv newfile oldfile

# Or use e2image for full filesystem conversion

Extents represent the most significant architectural advancement from ext3 to ext4, transforming how file systems handle large files and modern workloads.

Module Complete: Ext2/Ext3/Ext4

You've now explored the complete ext file system family:

• Page 1: Historical evolution and design philosophy
• Page 2: Block groups and allocation strategies
• Page 3: Superblock structure and recovery
• Page 4: Journaling for crash consistency
• Page 5: Extents for efficient block mapping

Together, these concepts explain how the most widely deployed Linux file system operates—from the high-level organization down to individual data structures. This knowledge is essential for performance tuning, troubleshooting, recovery operations, and understanding modern file system design.