Allocation Bitmaps

To track which blocks/inodes are free, FS uses bitmaps.

Block bitmap: 1 bit per data block.

• 0 = free.
• 1 = allocated.

For a 1 TiB disk with 4 KiB blocks: 256M blocks → 32 MiB bitmap. Reasonable.

Inode bitmap: 1 bit per inode.

Allocation:

Optimizations:

• Cache hint: remember last-allocated block, search from there.
• First-fit vs best-fit (less common in FS).
• Per-CPU local hint to reduce contention.

ext4 block groups:

• Disk divided into block groups (~128 MiB each).
• Each group has its own block bitmap + inode bitmap + inode table.
• Allocates near related data to improve locality.

For 1 TiB disk:

• ~8000 block groups.
• Per group: 32 KiB block bitmap, 8 KiB inode bitmap.

Free space tracking:

• Bitmap-based: scan to allocate, slow at high utilization.
• Free list: list of free block IDs. Fast alloc but ordering may fragment.
• Tree-based (xfs B-tree of free space): O(log) alloc + free.

Bitmap-locked operations:

• Allocate: clear-then-set bit. Must be atomic.
• Concurrency: lock per-block-group typical.
• Crash safety: bitmap update must hit disk before metadata using the block.

Modern: ext4 also keeps free space INSIDE group descriptors (count only) for fast queries.