Locality and The Fast File System

Why the Original UNIX File System Was Extremely Slow

The superblock, the entire inode table and the data region occupied three large consecutive areas. An inode and its data were frequently far apart, the free-list degenerated into scattered holes, and new files therefore received non-contiguous blocks. Combined with 512-byte blocks that each required a positioning operation, even a logically sequential file produced a stream of long seeks and delivered only about two percent of the disk’s peak bandwidth.

Cylinder Groups: Putting Related Items in the Same Small Room

FFS slices the disk into cylinder groups (logical block groups on today’s drives). Every group stores its own superblock replica, inode bitmap, data bitmap, inode table and data blocks. Once a directory and all of its files live inside one group, typical open-read-write sequences stay within a few millimetres of track, eliminating the long seeks that killed the old design.

Three Simple Heuristics Decide Placement

A new directory is placed in the group that currently holds the fewest directories yet still has free inodes. Ordinary files follow their parent directory and prefer consecutive blocks. Only very large files are deliberately spread across groups so that no single group fills up. Unrelated files are steered elsewhere. The net effect is “keep related things together, keep unrelated things apart.”

How Bitmaps Replaced the Fragmenting Free List

The old free-list rapidly became a collection of random pointers, so the allocator received isolated single blocks. Per-group inode and data bitmaps turn “find a long run of free blocks” into a cheap bit-scan. The same maps also reveal which groups are already crowded, letting the allocator spread new data evenly and keep the disk balanced over time.

Pitfalls

• Assuming modern file systems still see real cylinder geometry; disks export only a linear block address space, so implementations use block groups.
• Forgetting that replicating the superblock in every group is a reliability feature that lets the volume be mounted even after one copy is corrupted.
• Thinking larger blocks are always worse because of internal fragmentation; FFS chose 4 KB as a deliberate trade-off that slashed positioning overhead.

Minimum C11 · complete program · Download .c

#include <stdio.h>

int main(void) {
    printf("Simulating FFS locality-aware allocation\n\n");
    printf("Cylinder/Block Groups:\n");
    printf("  Group 0: [SB][ib][db] inodes... data blocks (home dir + files)\n");
    printf("  Group 1: [SB][ib][db] inodes... data blocks (usr files)\n");
    printf("  Group 2: [SB][ib][db] inodes... data blocks (tmp files)\n\n");
    printf("Heuristic: Place new directory in group with fewest dirs.\n");
    printf("Then place its files in the same group for locality.\n");
    printf("Large sequential files get consecutive blocks inside the group.\n");
    printf("This avoids the random seeks of the original UNIX FS.\n");
    return 0;
}

Compile locally

gcc -std=c11 -Wall -Wextra -Wpedantic -Werror ostep-41-ffs.c -o example && ./example

Expected result

Simulating FFS locality-aware allocation

Cylinder/Block Groups:
  Group 0: [SB][ib][db] inodes... data blocks (home dir + files)
  Group 1: [SB][ib][db] inodes... data blocks (usr files)
  Group 2: [SB][ib][db] inodes... data blocks (tmp files)

Heuristic: Place new directory in group with fewest dirs.
Then place its files in the same group for locality.
Large sequential files get consecutive blocks inside the group.
This avoids the random seeks of the original UNIX FS.

CHECK YOUR UNDERSTANDING

Close the answer. Explain it.

A user first creates directory /work and then two small files inside it. According to FFS policy, in which group are the two files most likely to reside, and why?

Check the sources

• OSTEP chapter PDF

Drafts and official chapters change. The version mark is only the example’s minimum.