Free space management?

In general, the allocator is going to be one of the most complex parts of a cow based
filesystem. Log structured filesystems have segments, where they force reasonably sized
units of the disk to become free and then allocate out of that.

Btrfs uses a btree to record which extents are in use, and free space is anything that isn't
recorded in that btree. So if it says we have an extent allocated from [16-20k ] and one at
[24-28k], then we have 4k free from 20k to 24k.

The part where btrfs gets complex in a hurry is that every extent in use in the filesystem is
recorded in this btree, including the extents that make up that btree. All of the btrees in
btrfs are managed with COW.

This doesn't spiral out of control because COW is strictly done as copy on write. Meaning
that as long as we haven't yet written a block we are allowed to keep changing it. The end
result is that we allocate blocks to hold new copies of the btree blocks and then are able to
make a number of modifications to those new blocks before they get written to disk.

As extents are freed we are able to reuse them, so we don't just keep walking to the end of
the drive. Btrfs does still have problems with ENOSPC, but this is mostly an accounting
problem of making sure there are enough free extents to make all of the btree modifications
we've promised we're going to make.