2.7. Block Allocation

All read-write file systems have to deal with the problem of assigning blocks to files. There are actually two problems that may be solved separately: finding a free block (which requires remembering which blocks are free and which are not), and remembering the blocks that store the data of a certain file.

The first distinguishing feature is the use of extents. An extent specifies a range of blocks by giving the first block's number and the length of the range in blocks. The alternative is to store each block's number separately, which usually takes more space, but is slightly simpler to handle.

Many file systems use an allocation bitmap to store which blocks are used. That bitmap requires one bit per useable block. Searching such a bitmap can be quite slow. Some file systems cache a short list of free blocks, which can be updated in the background.

The traditional Unix way to store the blocks that make up a file doesn't use extents, but a block number list. The first few numbers are stored in the inode structure; these are called direct blocks. If that space is exhausted, one block is allocated to store further block numbers. Only the block number of this indirect block is stored in the inode structure. If that space is also exhausted, the method is applied recursively, leading to double-indirect and sometimes triple-indirect blocks.