The Tux3 free block map is a dynamically allocated tree, and this
introduces a recursion: what happens when we try to allocate a block
but the leaf of the tree that maps the block does not exist yet, has to
be allocated, and we want to allocate it on that same free map leaf
that does not yet exist? Answer: infinite recursion ending with stack
overflow, unless the recursion is limited in some way. I considered
two obvious approaches:
* Do not record allocations of free tree leaves or nodes in the free
tree itself, but log them using a logical log entry as already
planned for the atomic commit mechanism.
* Use bitmaps for now, not extents. Preallocate the whole free map
without using an allocator, deciding where to place the blocks by
an ad hoc method. Once fully preallocated, enter the btree block
addresses into the free map "by hand" as ddsnap does.
Then I thought: since I am going to allocate with bitmaps at first
anyway, why not put the bitmaps in a file instead of a special purpose
btree. Then the bitmap blocks can be accessed through the file cache
(aka page cache in kernel, or logical block cache as I have sometimes
called it).
The really cool thing about this strategy is, it unexpectedly solves
the above recursion. Changes to the bitmap are made in the cache,
which is a simple logically indexed array. This naturally defers the
actual allocations until the cache is flushed to disk.
Woohoo, this is nice. Now what about when we go to extent based free
space mapping? Ok, that is easy. There will be a separate free map
btree with extents at the leaves. That btree could be mapped into a
file just like an htree directory index, but that would not avoid the
recursion. This is where the logical logging method described above
can be used.
(It is not yet clear to me whether it is best to map the free extent
btree into a file or have it separate, at the same level in the Tux3
structure as the inode table.)
An extent based free map is efficient o...
