Free Space Management

Introduction

A file system must track which disk blocks are occupied and which are free. When a new file is created or an existing file grows, the system needs to quickly find free blocks. When a file is deleted, its blocks must be marked as free for reuse. Free space management is this bookkeeping — and doing it efficiently matters because file creation and deletion happen constantly.

Method 1: Bitmap (Bit Vector)

Each disk block is represented by one bit: 1 = free, 0 = allocated (or vice versa).

Advantages: Simple, efficient hardware support for finding free blocks (bit scan instructions), easy to get contiguous blocks (scan for consecutive 1s).

Disadvantages: Bitmap must be kept in memory for efficiency (32 MB for 1 TB disk), does not scale well for very large disks.

Used in: ext4, NTFS, most modern file systems.

Method 2: Linked Free List

All free blocks are linked together in a list. The head pointer is stored in a known location. Each free block contains a pointer to the next free block.

Advantages: No wasted space (pointers are in the free blocks themselves), no extra data structure needed.

Disadvantages: Finding contiguous blocks is difficult (must traverse list), traversal is slow for any operation requiring multiple blocks.

Method 3: Grouping

First free block stores addresses of N free blocks. The last of those N blocks stores addresses of the next N free blocks, and so on.

Advantage: Can find many free blocks quickly (read one block, get N addresses). Better than scanning a linked list block by block.

Method 4: Counting

Store (start_block, count) pairs instead of individual blocks. Works well when free space tends to be contiguous (common after sequential allocation).

Advantage: Very compact when free regions are large and contiguous. Used in extent-based file systems.

Comparison

Real-World Analogy

Free space management is like managing empty seats in a cinema. A bitmap is a seating chart where each seat has a colored dot (red = taken, green = available). A linked list is like asking each empty seat "where's the next empty one?" — tedious. Grouping is like the usher saying "there are 5 seats available in row J and 3 in row M." Counting is "rows A-C are completely empty, row F has seats 5 through 12 available."

Key Takeaways

• The bitmap approach is most common in modern file systems — simple, efficient, hardware-supported
• Linked lists waste no space but are slow for finding contiguous blocks
• Counting is efficient when free space is naturally contiguous (extent-based systems)
• Free space management must be fast because every file create/grow/delete uses it
• The bitmap is typically cached in memory for fast allocation decisions
• Choice of method affects file creation speed, fragmentation handling, and space overhead