CSE Roadmap

Core tier · about 3 hours · 7 parts

Part 5 of 7 · 3 min read

Extents

Think of a train timetable. Instead of listing every station, it says "from A to F, every stop". A run is one line, and a gap is a new line. The analogy stops in one place: a timetable is fixed, while the runs of a file change as the file grows.

In plain words: An extent is a run of consecutive blocks, stored as a start block and a length. A file of 1 MiB laid out in one run needs one extent, and not 256 pointers. ext4 stores up to four extents in the inode itself and uses a small tree of extent blocks for more. A file that is written in one go, or that asks for space in advance with fallocate, gets few long extents. A file that grows slowly in small steps while other files grow too may get many short ones.

A worked example. On the test image, debugfs showed the 1 MiB file meg.bin as one extent, (0-255):804-1059: 256 blocks in a row. The program below makes a worse case. It appends one block at a time to two files in turn, forcing each block to disk with fsync, and then makes a third file with posix_fallocate, which asks for 200 blocks in one request.

#include <fcntl.h>
#include <stdio.h>
#include <string.h>
#include <unistd.h>

int main(void) {
    int a = open("a.dat", O_CREAT | O_WRONLY | O_TRUNC, 0644);
    int b = open("b.dat", O_CREAT | O_WRONLY | O_TRUNC, 0644);
    char blk[4096]; memset(blk, 'x', sizeof blk);
    for (int i = 0; i < 200; i++) {            /* append one block to each file in turn */
        if (write(a, blk, sizeof blk) < 0 || write(b, blk, sizeof blk) < 0) return 1;
        fsync(a); fsync(b);                    /* force allocation now, so the blocks interleave */
    }
    close(a); close(b);
    int c = open("c.dat", O_CREAT | O_WRONLY | O_TRUNC, 0644);
    if (posix_fallocate(c, 0, 200 * 4096)) return 1;   /* ask for 200 blocks in one request */
    close(c);
    return 0;
}

Output of filefrag on the test machine:

a.dat: 20 extents found
b.dat: 20 extents found
c.dat: 1 extent found

The first rows of filefrag -v a.dat showed single-block extents at the blocks 1066, 1579, 1581, 1583 and 1585, so the two files took turns at every other block. The two files that grew together ended up with 20 pieces each, and the file that asked for its space at once got one piece.

The key lines. Fewer extents mean fewer seeks on a spinning disk and less metadata for any device. Programs that know a file's final size can help, by calling fallocate first. ext4 also delays the choice of blocks until the data is written out (delayed allocation), which lets it see more of the file at once. The fsync in the test program defeated that on purpose, to show the effect.

Extent

An extent is a contiguous run of blocks of a file, recorded as a starting block and a length. A file system that stores extents needs one record for each run and not one pointer for each block, which saves space and makes large sequential files cheap to describe.

Example: the extent (0-255):804-1059 says that blocks 0 to 255 of the file are stored in disk blocks 804 to 1,059.

Read it as

In filefrag -v output, each row is one extent. Many short rows mean a fragmented file. One long row means a contiguous file.

Check yourself: 1. How many extents does a file of 1 MiB need if it is contiguous? 2. Why did the two files of the test program end up with 20 extents each? 3. How can a program reduce the number of extents of a file it will write?