Skip to content
Tutorials Center
My learning

Topics

Lesson 49 of 66 ยท Files and Storage

Free Space Management

See how a file system tracks free disk blocks with bit vectors, linked lists, grouping, counting and space maps, compare their costs, and try each in Python.

Creating a file needs blocks, and deleting one gives blocks back. The file system must therefore know, at all times, which blocks are free. That bookkeeping is called free-space management, and the structure that holds it is the free-space list. Despite the name, it does not have to be a list.

Every method answers the same two questions quickly: "give me one free block (or n in a row)" and "this block is free again". The methods differ in how much space the bookkeeping takes, how fast allocation is, and how well they find contiguous runs, which matters for contiguous allocation and extents.

1. Bit vector (bitmap)

Use one bit per block: 1 means free, 0 means allocated (or the reverse). A 1 TB disk with 4 KB blocks has about 268 million blocks, so the bitmap is 268 million bits, which is 32 MB. That is small enough to cache, and it gets better with locality.

  • Find the first free block: scan words, skipping words that are all zero, then use a hardware instruction (count-leading-zeros / find-first-set) on the first non-zero word. Fast on modern CPUs.
  • Find a run of n free blocks: look for n consecutive set bits. This is natural with a bitmap, which is its greatest strength.
  • Cost: the whole bitmap must be in memory to be fast, and it is always the same size however full the disk is.

2. Linked list of free blocks

Keep a pointer to the first free block, and store in each free block a pointer to the next free block. Nothing extra is stored for allocated space and no memory is wasted when the disk is full.

  • Allocate: take the head of the list: one read.
  • Free: put the block at the head.
  • Cost: finding n contiguous blocks is hard, and walking the list means one disk read per block, so it is rarely used for bulk work.

3. Grouping

A variation of the linked list. The first free block holds the addresses of n other free blocks. The last of these addresses points to another block with n more addresses. A large number of free blocks can now be found with a single read.

4. Counting

Free space often comes in runs, so record each run as (first block, count). A free area of 500 consecutive blocks needs one entry rather than 500. Entries are kept in a sorted structure (such as a balanced tree) so neighbouring runs merge. This is the idea behind extent-based file systems and ZFS's space maps.

5. Space maps (log-structured)

ZFS divides the disk into regions called metaslabs, each with a log of allocate/free events in time order. The log is replayed into an in-memory tree when needed and compacted occasionally. Updates are sequential appends, which is cheap on any device.

Comparison

Method Memory/disk overhead Find one block Find n contiguous Typical use
Bit vector 1 bit per block, fixed Very fast Easy ext4, NTFS, most systems
Linked list None extra Very fast (head) Poor Simple/old systems
Grouping Small Fast, batches Poor Older Unix
Counting Proportional to number of runs Fast Natural Extent-based systems
Space map Log plus tree Fast Natural ZFS

A bit vector in Python

The next program implements a bitmap allocator on a 32-block disk. Python integers can hold any number of bits, so a single int plays the role of the bitmap.

Python Bitmap allocator: first-free and contiguous runs

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The new four-block run reuses the hole left by the freed five-block run. This is first fit, the simplest placement policy for runs.

Linked list versus counting

Here the same freed blocks are tracked two ways. After a burst of frees, the counting method needs only a few entries while the linked list needs one node per block.

Python Linked free list vs counting runs

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Ten free blocks became three runs, and asking for a given size became a quick scan of three entries.

Practical issues

  • Crash consistency. Allocating a block means updating both the free-space structure and the file's metadata. If the system crashes between the two, a block can be "in use" yet owned by nobody (a leak), or owned by a file and also marked free (a disaster). Journaling exists to prevent this.
  • TRIM / discard. On SSDs, the file system tells the drive which blocks are free so the drive can erase them in advance and keep writes fast.
  • Locality. Good allocators prefer free blocks near the file's existing blocks (ext4 uses block groups for this).
  • Lazy initialization. Many systems only mark ranges free in the bitmap and defer zeroing the data until needed.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. How much memory does a bit vector need for a disk of 1,000,000 blocks?

    One bit per block gives 1,000,000 bits, which is 125,000 bytes, and the size does not change as the disk fills.
  2. 2. Which method finds a run of several contiguous free blocks most naturally?

    A bitmap shows neighbouring bits directly, and counting stores runs as (start, length).
  3. 3. What is the advantage of grouping over a plain linked free list?

    The first free block holds the addresses of n others, so a batch of free blocks can be found with one disk read.
  4. 4. Why does crash consistency matter for free-space management?

    Two structures must change together. If only one change reaches the disk, the file system becomes inconsistent.

Summary

  • The free-space list records which blocks are available; allocation takes from it and deletion returns to it.
  • A bit vector uses one bit per block and finds runs easily; a linked list costs nothing extra but is slow for runs; grouping batches addresses; counting stores (start, length) runs; space maps log changes.
  • Real systems care about crash consistency, locality and SSD TRIM, not just speed.

Next: The Unix File System and Journaling