Free List

The free list occupies a whole number of blocks following the directory. It is viewed as an array of block numbers and is large enough to contain the number of every block on the disk, plus enough spare to make it up to a whole number of blocks.

The free list is organized as a circular list with a head and a tail. Blocks are allocated from the head and are freed to the tail. When they reach the top of the free list, the head and tail pointers wrap back around to zero. These pointers are not stored on the disk but are discovered each time the filesystem is mounted by scanning the free list.

The free list is organized in this way for several reasons. First, it separates block allocation from freeing. Allocations need to proceed at a rate determined by the streaming of data onto the disk. Blocks are only freed when a file is deleted, and can be handled as a background task. Second, the separation makes recovery of filesystem integrity simpler, since blocks will not get reused immediately they are freed. Third, blocks that are allocated together in a particular file will be returned to the free list together, preserving locality.