When does a disk turn a file away while it still has room?

A file system implemented in C++ over a flat block device. Free space is tracked with a bitmap, files are described by inode-style metadata records, and allocation uses a First-Fit scan for contiguous runs of blocks. Building it meant confronting the trade-off that makes First-Fit interesting: it is cheap to compute and keeps small files near the start of the disk, but repeated allocate and delete cycles strand free blocks in runs too short to reuse. The simulator below is a browser reimplementation of that allocator, so the fragmentation behaviour can be watched directly.

Problem

A file system has to answer two questions quickly: which blocks are free, and where should a new file go. Answering them naively means scanning the whole disk on every write. Answering them well means picking a free-space representation and an allocation policy, then living with the failure mode each one implies.

Approach

Free space is held in a bitmap, one bit per block, so a lookup is a bit test rather than a walk over file metadata. Files carry inode-style records holding their starting block and length, which keeps contiguous files cheap to read sequentially. Allocation scans for the first run of free blocks large enough to hold the file. The cost of that choice is external fragmentation: as files are deleted, the free space that returns is scattered in runs that may each be too small for the next allocation even when the total free space is ample. The interactive simulator makes this visible — allocating and deleting repeatedly drives the fragmentation figure up while total free blocks stay unchanged. Running the same allocator against a fixed workload puts a number on it: on a 1024-block device held at 80% occupancy for 3,000 delete/allocate cycles, the longest usable run falls from 189 blocks to around 32 while total free space stays near 198, and 6.7% of writes are refused on a disk that was never actually full.