Tux3 Allocation Glossary

[Daniel Phillips]

For the next few weeks we will be talking about the last remaining big
Tux3 design issue: allocation heuristics. This is largely uncharted
territory with little formal research available as a guide. Further, we
have a new requirement specific to our atomic commit strategy: data
obsoleted by a delta may not be freed and reallocated until the delta
commit completes. Therefore, the ideal goal for a given allocation will
often not be available and some less desirable location will need to
be used in its place. The immediate effect of this is that we cannot
simply copy the effective algorithms used by the Ext2/3/4 family.

To help us get started studying specific issues and solutions for
Tux3, I have prepared a short glossary of terminology we have been
developing in discussions recently. There are specific, in some
respects novel, algorithms implied by the definitions below, which
will be described later with the help of this basic terminology.

Tux3 Allocation Glossary

   Allocation group

       All the blocks mapped by one bitmap block. We might change the
       granularity of this eventually, but for now an allocation group has
       2**(12 + 3) = 2**15 blocks.

   Free tag map

       Quick means of knowing how much free space is available in each
       allocation group (exactly or approximately depending on
       implementation). For now, this is implemented as an array of 16 bit
       counts of allocated blocks per allocation group.

   Bounce

       We tried to satisfy an allocation request within a target region of the
       volume and failed, so bounce to some new region and try again.
       Search regions successively further away from the orignal goal using a
       generating function to generate the search sequence so the search
       pattern is repeatable, given the same file

   Bounce pattern

       The generating function used to compute successive bounce goals. Must
       be repeatable per file. Must have good coverage properties so that
       volume space tends to consumed evenly. Must fall back to exhaustive
       search (with the help of free tags) after some number of bounces in
       order to ensure that all the space in a volume can eventually be used.

   Slack space

       Extra space left near files and around directories to handle growth
       or rewrites or both.

  Population pressure

       Fullness of nearby allocation groups. Controls amount of directory
       spread and slack space.

  Directory spread

       If nearby allocation groups have low allocation counts, new directories
       will spread out further.

   Linear allocation

       Search for a new extent to allocate just above the previously allocated
       extent. For CPU efficiency and good layout, we want to do this most of
       the time using a simple test to determine whether this is appropriate.

   Extrapolation

       The logical position of data in a file and position of the file in its
       sirectory is extrapolated to determine an initial allocation goal
       Extrapolation is to find a good allocation goal for data of a particular
       file, using a simple formula based on the position of the dirent in a
       directory and the logical position of the data in a file.