CSE Roadmap

Core tier · about 3 hours · 7 parts

Part 6 of 7 · 3 min read

Free space

Tracking free space

Think of a cinema with a seat plan. A plan with a tick for each taken seat shows at once where a group of five empty seats is. A list of empty seats is shorter when the cinema is nearly full, and it takes longer to find a group. The analogy stops in one place: a cinema fills once, while a disk is allocated and freed constantly.

In plain words: A file system must find free blocks quickly. A bitmap has one bit for each block, so the whole state of a disk is visible in a compact form, and a run of free blocks is found by scanning for zero bits. It is easy to find a block near another one, which keeps files together. A free list chains the free blocks, which costs almost no space when the disk is nearly full, and gives no easy way to find a long run. Most modern file systems use bitmaps, often with extra structures for speed. When a block is chosen, the file system tries to put it close to the previous block of the same file (locality) and to leave room for growth.

A worked example. With 4 KiB blocks, a bitmap of a 1 TiB disk has 2^40 / 2^12 = 268,435,456 bits, which is 268,435,456 / 8 = 33,554,432 bytes, or 32 MiB. One bitmap block describes 32,768 blocks, which is 128 MiB of disk. That is 8,192 bitmap blocks for the whole disk, as many as there are block groups on page 2. To find a free run of 10 blocks near block 5,000, the system reads the bitmap block that covers it and scans the bits there.

The key lines. The cost of tracking free space is small: 32 MiB for 1 TiB, which is 0.003% of the disk. The cost of a poor choice of blocks is large, since it fragments files, as section 4 showed. The allocator is therefore more important than the data structure of the free list.

Free-space bitmap

A free-space bitmap is an array with one bit for each block of a file system, where one value means that the block is free and the other that it is in use. It lets the file system find free blocks, and runs of free blocks, with a scan.

Example: a bitmap of 4,096 bits (512 bytes) describes 4,096 blocks of 4 KiB, which is 16 MiB.

Interview angle

A common question is "How does a file system find the block of byte N of a file?" A good answer divides N by the block size, then follows the allocation method: direct pointers, indirect blocks, an extent search or a FAT walk. It adds the number of disk reads that each case needs.

Check yourself: 1. How big is the bitmap of a 1 TiB disk with 4 KiB blocks? 2. Which method of tracking free space helps to find a long run? 3. Why does the choice of the block matter more than the structure of the free list?

Words you will meet

Word Meaning
Contiguous allocation A file occupies consecutive blocks.
FAT A table of next-block numbers, kept in memory.
Indirect block A block that holds block numbers.
Extent A run of consecutive blocks: start and length.
Bitmap One bit for each block: free or used.

Quick notes

  • A method must read in order fast, reach any offset fast, waste little, and let files grow.
  • Contiguous allocation is fast and fragments externally. Linked allocation has no gaps and slow random access.
  • A FAT moves the links into one in-memory table. Its size is clusters x entry size.
  • The Unix inode has 12 direct pointers and single, double and triple indirect blocks. Max size is about 4 TiB at 4 KiB blocks.
  • Extents store runs as start and length. filefrag shows them.
  • A bitmap of a 1 TiB disk with 4 KiB blocks takes 32 MiB.