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.