Weekly edition	Kernel	Security	Distributions	Contact Us	Search
Archives	Calendar	Subscribe	Write for LWN	LWN.net FAQ	Sponsors

Free space management?

Posted Jul 25, 2009 16:01 UTC (Sat) by Yenya (subscriber, #52846)
Parent article: A short history of btrfs

How do COW btree-based filesystems manage the free disk space? I presume it is not in the btree itself, because for allocation of the new block it would be necessary to - well - allocate a COW block for the new version of (at least) the btree leaf.

(Log in to post comments)

Posted Jul 25, 2009 21:28 UTC (Sat) by bronson (subscriber, #4806) [Link]

Good question. Last I heard, btrfs just keeps writing data toward the end of the disk until it runs out of disk. Then it panics.

This appears to have been fixed, and doesn't invovled anything so crufty as a vacuum running in the background, but I can't find specifics. Does anybody have up to date info?

Free space management?

Posted Jul 27, 2009 14:38 UTC (Mon) by masoncl (subscriber, #47138) [Link]

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.

Free space management?

Posted Jul 27, 2009 22:02 UTC (Mon) by Yenya (subscriber, #52846) [Link]

Thanks for the explanation!

BTW, where should I post issues with BTRFS? I have a testing BTRFS over 8 drives (both data and metadata mirrored), and recently one of the drives died. Now when I want to access the BTRFS volume, add a new drive, or whatever, it crashes on me (2.6.30, I think; I can compile any kernel
you point me at, though). Is the kernel bugzilla the right place?

Free space management?

Posted Jul 27, 2009 23:01 UTC (Mon) by masoncl (subscriber, #47138) [Link]

Both the kernel.org bugzilla and the btrfs mailing list are good resources (linux-
btrfs@vger.kernel.org)

Free space management?

Posted Aug 10, 2009 14:05 UTC (Mon) by Yenya (subscriber, #52846) [Link]

FWIW, I have reported this as http://bugzilla.kernel.org/show_bug.cgi?id=13957. However, I can no longer use this HW for testing, sorry.