Free Space Management

Introduction

When you save files on your computer, they need to be stored somewhere on your hard drive or SSD. But how does your computer know which parts of the storage device are available? This is where free space management comes in.

Free space management is a critical component of file systems that tracks which storage blocks are in use and which are available. It's like a librarian keeping track of which shelves have space for new books.

In this guide, we'll explore different techniques file systems use to manage free storage space, understand their advantages and limitations, and see how they're implemented in real-world systems.

Why Free Space Management Matters

Efficient free space management is essential for:

• Performance: Finding free space quickly means faster file operations
• Space utilization: Maximizing available storage by avoiding fragmentation
• Reliability: Preventing accidental overwrites of existing data

Common Free Space Management Techniques

Let's explore the most common methods used by file systems to track and allocate free space.

1. Bit Vector (Bitmap)

A bit vector uses a single bit to represent each block on the storage device:

• 0 indicates the block is free
• 1 indicates the block is in use (or vice versa)

+---+---+---+---+---+---+---+---+
| 1 | 1 | 0 | 0 | 1 | 0 | 1 | 1 |
+---+---+---+---+---+---+---+---+
  |   |   |   |   |   |   |   |
  v   v   v   v   v   v   v   v
Block: 0   1   2   3   4   5   6   7
Status: In  In  Free Free In  Free In  In
        Use Use          Use      Use Use

Advantages

• Simple: Easy to implement and understand
• Efficient lookups: Finding a specific block's status is an O(1) operation
• Space efficiency: Requires only 1 bit per block

Disadvantages

• Memory requirements: For very large storage devices, the bitmap can become quite large
• Finding contiguous free space: Requires scanning the bitmap

Example Implementation (C)

c

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

#define TOTAL_BLOCKS 1024
#define WORD_SIZE 32  // 32 bits in an integer

// Bitmap array (each integer stores 32 blocks)
int bitmap[TOTAL_BLOCKS / WORD_SIZE];

// Initialize all blocks as free (0)
void initializeBitmap() {
    for (int i = 0; i < TOTAL_BLOCKS / WORD_SIZE; i++) {
        bitmap[i] = 0;
    }
}

// Mark a block as used (1)
void markBlockUsed(int blockNum) {
    int index = blockNum / WORD_SIZE;
    int offset = blockNum % WORD_SIZE;
    bitmap[index] |= (1 << offset);
}

// Mark a block as free (0)
void markBlockFree(int blockNum) {
    int index = blockNum / WORD_SIZE;
    int offset = blockNum % WORD_SIZE;
    bitmap[index] &= ~(1 << offset);
}

// Check if a block is free
bool isBlockFree(int blockNum) {
    int index = blockNum / WORD_SIZE;
    int offset = blockNum % WORD_SIZE;
    return (bitmap[index] & (1 << offset)) == 0;
}

// Find first free block
int findFirstFreeBlock() {
    for (int i = 0; i < TOTAL_BLOCKS / WORD_SIZE; i++) {
        if (bitmap[i] != ~0) {  // If not all bits are 1
            // Find the first 0 bit
            for (int j = 0; j < WORD_SIZE; j++) {
                if ((bitmap[i] & (1 << j)) == 0) {
                    return i * WORD_SIZE + j;
                }
            }
        }
    }
    return -1;  // No free blocks
}

int main() {
    initializeBitmap();
    
    // Mark some blocks as used
    markBlockUsed(10);
    markBlockUsed(20);
    markBlockUsed(30);
    
    // Check block status
    printf("Block 10 is %s
", isBlockFree(10) ? "free" : "used");
    printf("Block 11 is %s
", isBlockFree(11) ? "free" : "used");
    
    // Find a free block
    int freeBlock = findFirstFreeBlock();
    printf("First free block: %d
", freeBlock);
    
    return 0;
}

Output:

Block 10 is used
Block 11 is free
First free block: 0

2. Linked List

In this approach, free blocks are connected in a linked list. Each free block contains a pointer (block number) to the next free block.

Advantages

• No external data structure: The free list is stored within the free blocks themselves
• Efficient allocation: Simply remove the first block from the list

Disadvantages

• Finding specific free blocks is slow: Requires traversing the list
• Can't easily find contiguous free blocks: Blocks in the list might be scattered
• Space overhead: Each free block needs space for the next pointer

Example Implementation (C)

c

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

#define BLOCK_SIZE 512
#define TOTAL_BLOCKS 1024

// Simple block structure with a next pointer
typedef struct Block {
    int blockNum;
    struct Block* next;
} Block;

// Head of the free block list
Block* freeListHead = NULL;

// Initialize all blocks as free
void initializeFreeList() {
    Block* prev = NULL;
    
    // Create linked list of free blocks (in reverse order)
    for (int i = TOTAL_BLOCKS - 1; i >= 0; i--) {
        Block* newBlock = (Block*)malloc(sizeof(Block));
        newBlock->blockNum = i;
        newBlock->next = prev;
        prev = newBlock;
    }
    
    freeListHead = prev;
}

// Allocate a block
int allocateBlock() {
    if (freeListHead == NULL) {
        return -1;  // No free blocks
    }
    
    // Remove first block from free list
    Block* allocatedBlock = freeListHead;
    freeListHead = freeListHead->next;
    
    int blockNum = allocatedBlock->blockNum;
    free(allocatedBlock);
    
    return blockNum;
}

// Free a block
void freeBlock(int blockNum) {
    // Create new block entry
    Block* newFreeBlock = (Block*)malloc(sizeof(Block));
    newFreeBlock->blockNum = blockNum;
    
    // Add to head of free list
    newFreeBlock->next = freeListHead;
    freeListHead = newFreeBlock;
}

// Print the free list
void printFreeList() {
    Block* current = freeListHead;
    printf("Free blocks: ");
    while (current != NULL) {
        printf("%d ", current->blockNum);
        current = current->next;
    }
    printf("
");
}

int main() {
    initializeFreeList();
    
    printf("Initial ");
    printFreeList();
    
    // Allocate some blocks
    int b1 = allocateBlock();
    int b2 = allocateBlock();
    int b3 = allocateBlock();
    
    printf("After allocation: ");
    printFreeList();
    
    // Free a block
    freeBlock(b2);
    
    printf("After freeing block %d: ", b2);
    printFreeList();
    
    return 0;
}

Output:

Initial Free blocks: 0 1 2 3 4 5 ... 1022 1023
After allocation: Free blocks: 3 4 5 ... 1022 1023
After freeing block 1: Free blocks: 1 3 4 5 ... 1022 1023

3. Counting Approach

Instead of tracking each block individually, we keep track of runs of free blocks.

+-------------+-------------+-------------+
| <3,0>       | <2,4>       | <4,8>       |
+-------------+-------------+-------------+
 3 free blocks  2 free blocks  4 free blocks
 starting at    starting at    starting at
 block 0        block 4        block 8

Advantages

• Compact representation: Especially efficient when there are large contiguous free regions
• Easy to find contiguous blocks: The information is already grouped

Disadvantages

• Overhead for highly fragmented storage: Could require more space than a bitmap
• Complex updates: When allocating or freeing blocks, we may need to split or merge entries

4. Grouping Approach (Free Space Extents)

Similar to the counting approach but we explicitly track the start and end of each free region.

+---------------+---------------+---------------+
| <0,2>         | <4,5>         | <8,11>        |
+---------------+---------------+---------------+
 Free region     Free region     Free region
 from block 0    from block 4    from block 8
 to block 2      to block 5      to block 11

This approach is common in modern file systems that support extents (contiguous regions of blocks).

Free Space Management in Real File Systems

ext4 (Linux)

The ext4 file system uses a combination of bitmaps and extent trees:

• Block bitmaps track the allocation status of data blocks
• Extent trees efficiently represent contiguous regions

NTFS (Windows)

NTFS uses a Master File Table (MFT) and a bitmap to track free clusters:

• NTFS uses a bitmap for free space tracking
• Each bit represents a cluster (allocation unit)
• The bitmap itself is stored as a special file in the MFT

ZFS (Solaris, FreeBSD)

ZFS uses a space map:

• Tracks space usage with a log-structured format
• Uses B-trees to index free space

Advanced Concepts

Fragmentation Management

Free space fragmentation occurs when free blocks become scattered across the disk, making it difficult to allocate large contiguous files.

Techniques to handle fragmentation:

• Delayed allocation: Wait to assign blocks until data is actually written
• Space reservation: Reserve extra space around files to allow for growth
• Defragmentation: Reorganize files to create larger contiguous free regions

Allocation Policies

How free blocks are selected can significantly impact performance:

• First-fit: Allocate the first free block/extent large enough
• Best-fit: Allocate the smallest free block/extent that can satisfy the request
• Worst-fit: Allocate the largest free block/extent (to minimize fragmentation)
• Next-fit: Start searching from where the last allocation ended

Locality Optimizations

Modern file systems try to place related data close together:

• Files in the same directory
• File metadata near the file data
• Sequential file blocks together

Practical Example: Building a Simple File System

Let's create a simplified in-memory file system to demonstrate free space management using the bitmap approach.

c

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

#define BLOCK_SIZE 1024
#define TOTAL_BLOCKS 128
#define MAX_FILES 16
#define MAX_FILENAME 32

// Bitmap to track free blocks
unsigned char bitmap[TOTAL_BLOCKS / 8];

// File metadata structure
typedef struct {
    char name[MAX_FILENAME];
    int startBlock;
    int numBlocks;
    bool used;
} FileEntry;

// File table
FileEntry fileTable[MAX_FILES];

// Storage (simulated blocks)
char storage[TOTAL_BLOCKS][BLOCK_SIZE];

// Initialize the file system
void initFS() {
    // Clear bitmap (all blocks free)
    memset(bitmap, 0, sizeof(bitmap));
    
    // Clear file table
    memset(fileTable, 0, sizeof(fileTable));
}

// Check if a block is free
bool isBlockFree(int blockNum) {
    int byte = blockNum / 8;
    int bit = blockNum % 8;
    return !(bitmap[byte] & (1 << bit));
}

// Mark a block as used
void markBlockUsed(int blockNum) {
    int byte = blockNum / 8;
    int bit = blockNum % 8;
    bitmap[byte] |= (1 << bit);
}

// Mark a block as free
void markBlockFree(int blockNum) {
    int byte = blockNum / 8;
    int bit = blockNum % 8;
    bitmap[byte] &= ~(1 << bit);
}

// Find contiguous free blocks
int findFreeBlocks(int numBlocks) {
    int count = 0;
    int startBlock = -1;
    
    for (int i = 0; i < TOTAL_BLOCKS; i++) {
        if (isBlockFree(i)) {
            if (count == 0) {
                startBlock = i;
            }
            count++;
            
            if (count == numBlocks) {
                return startBlock;
            }
        } else {
            count = 0;
            startBlock = -1;
        }
    }
    
    return -1; // Not enough contiguous blocks
}

// Find an unused file entry
int findUnusedFileEntry() {
    for (int i = 0; i < MAX_FILES; i++) {
        if (!fileTable[i].used) {
            return i;
        }
    }
    return -1; // No free file entries
}

// Create a new file
bool createFile(const char* filename, int size) {
    int numBlocks = (size + BLOCK_SIZE - 1) / BLOCK_SIZE; // Round up
    
    // Find free blocks
    int startBlock = findFreeBlocks(numBlocks);
    if (startBlock == -1) {
        printf("Error: Not enough contiguous free space
");
        return false;
    }
    
    // Find free file entry
    int fileIndex = findUnusedFileEntry();
    if (fileIndex == -1) {
        printf("Error: File table full
");
        return false;
    }
    
    // Update file table
    strncpy(fileTable[fileIndex].name, filename, MAX_FILENAME - 1);
    fileTable[fileIndex].startBlock = startBlock;
    fileTable[fileIndex].numBlocks = numBlocks;
    fileTable[fileIndex].used = true;
    
    // Mark blocks as used
    for (int i = 0; i < numBlocks; i++) {
        markBlockUsed(startBlock + i);
    }
    
    printf("File '%s' created with %d blocks starting at block %d
", 
           filename, numBlocks, startBlock);
    return true;
}

// Delete a file
bool deleteFile(const char* filename) {
    // Find the file
    int fileIndex = -1;
    for (int i = 0; i < MAX_FILES; i++) {
        if (fileTable[i].used && strcmp(fileTable[i].name, filename) == 0) {
            fileIndex = i;
            break;
        }
    }
    
    if (fileIndex == -1) {
        printf("Error: File '%s' not found
", filename);
        return false;
    }
    
    // Mark blocks as free
    for (int i = 0; i < fileTable[fileIndex].numBlocks; i++) {
        markBlockFree(fileTable[fileIndex].startBlock + i);
    }
    
    // Free file entry
    fileTable[fileIndex].used = false;
    
    printf("File '%s' deleted
", filename);
    return true;
}

// Print free space info
void printFreeSpace() {
    int freeBlocks = 0;
    int largestContiguous = 0;
    int currentRun = 0;
    
    for (int i = 0; i < TOTAL_BLOCKS; i++) {
        if (isBlockFree(i)) {
            freeBlocks++;
            currentRun++;
            if (currentRun > largestContiguous) {
                largestContiguous = currentRun;
            }
        } else {
            currentRun = 0;
        }
    }
    
    printf("Free space: %d/%d blocks (%d KB)
", 
           freeBlocks, TOTAL_BLOCKS, freeBlocks * BLOCK_SIZE / 1024);
    printf("Largest contiguous free space: %d blocks (%d KB)
", 
           largestContiguous, largestContiguous * BLOCK_SIZE / 1024);
}

// Print file system state
void printFSState() {
    printf("
--- File System State ---
");
    
    // Print files
    printf("Files:
");
    bool hasFiles = false;
    for (int i = 0; i < MAX_FILES; i++) {
        if (fileTable[i].used) {
            hasFiles = true;
            printf("  %s: %d blocks, starting at block %d
", 
                   fileTable[i].name, fileTable[i].numBlocks, fileTable[i].startBlock);
        }
    }
    if (!hasFiles) {
        printf("  (No files)
");
    }
    
    // Print free space
    printFreeSpace();
    printf("------------------------

");
}

int main() {
    // Initialize the file system
    initFS();
    printf("File system initialized with %d blocks (%d KB total)
", 
           TOTAL_BLOCKS, TOTAL_BLOCKS * BLOCK_SIZE / 1024);
    
    // Initial state
    printFSState();
    
    // Create some files
    createFile("document.txt", 2500);
    createFile("image.jpg", 5000);
    createFile("video.mp4", 15000);
    
    // Check state
    printFSState();
    
    // Delete a file
    deleteFile("image.jpg");
    
    // Final state
    printFSState();
    
    return 0;
}

Output:

File system initialized with 128 blocks (128 KB total)

--- File System State ---
Files:
  (No files)
Free space: 128/128 blocks (128 KB)
Largest contiguous free space: 128 blocks (128 KB)
------------------------

File 'document.txt' created with 3 blocks starting at block 0
File 'image.jpg' created with 5 blocks starting at block 3
File 'video.mp4' created with 15 blocks starting at block 8

--- File System State ---
Files:
  document.txt: 3 blocks, starting at block 0
  image.jpg: 5 blocks, starting at block 3
  video.mp4: 15 blocks, starting at block 8
Free space: 105/128 blocks (105 KB)
Largest contiguous free space: 105 blocks (105 KB)
------------------------

File 'image.jpg' deleted

--- File System State ---
Files:
  document.txt: 3 blocks, starting at block 0
  video.mp4: 15 blocks, starting at block 8
Free space: 110/128 blocks (110 KB)
Largest contiguous free space: 105 blocks (105 KB)
------------------------

Performance Considerations

The choice of free space management technique affects several key performance metrics:

1. Space efficiency: How much overhead is required to track free space
2. Allocation speed: How quickly free blocks can be found
3. Contiguous allocation: Ability to find large contiguous free regions
4. Fragmentation resistance: How well the system avoids creating small unusable free spaces

The ideal technique depends on the specific use case and the expected patterns of file creation and deletion.

Summary

Free space management is a critical aspect of file system design that tracks and allocates available storage blocks. We've explored several approaches:

• Bit vectors (bitmaps): Simple, space-efficient, but may be slow for finding contiguous space
• Linked lists: Low overhead, but poor for locating specific regions
• Counting/grouping: Efficient for representing large contiguous regions
• Hybrid approaches: Combining techniques for better performance

Modern file systems like ext4, NTFS, and ZFS use sophisticated combinations of these techniques to balance performance, space efficiency, and reliability.

Understanding free space management helps you appreciate how your computer efficiently stores files and provides insights into file system performance characteristics.

Exercises

1. Implement a free space management system using the linked list approach and compare its performance with the bitmap approach.

2. Modify the simple file system example to support fragmented files (non-contiguous allocation).

3. Design a free space management system that optimizes for quick allocation of large contiguous regions.

4. Implement a file system benchmark that measures allocation and deallocation performance under different workloads.

5. Research how a specific file system (e.g., ext4, NTFS, or ZFS) handles free space management and write a report on its techniques.

Additional Resources

• "Operating Systems: Three Easy Pieces" by Remzi H. Arpaci-Dusseau and Andrea C. Arpaci-Dusseau
• "The Design and Implementation of the FreeBSD Operating System" by Marshall Kirk McKusick
• "Modern File Systems Internals" by Steve D. Pate
• Linux kernel documentation for ext4
• NTFS documentation from Microsoft