sys/vfs/hammer2/FREEMAP

   1
   2                         HAMMER2 Freemap Design Notes
   3
   4                                 Overview
   5
   6     HAMMER2 Media is broken down into 2 GByte zones.  Each 2 GByte zone
   7     contains a 4 MByte header (64 x 64K blocks).  The blocks in this header
   8     are reserved for various purposes.  For example, block #0 is used for
   9     the volume header or for a volume header backup.
  10
  11     * It is very important to remember that the Freemap only uses blocks
  12       from these reserved areas.  Freemap blocks are NOT dynamically
  13       allocated.
  14
  15     * On-mount, the synchronization TID for the main H2 filesystem is
  16       compared against the synchronization TID of the freemap and the
  17       H2 topology is incrementally iterated using mirror_tid to update
  18       the freemap with any missing information.  This way the freemap flush
  19       does not need to be synchronized with the normal H2 flush.  This
  20       can be done very quickly on-mount.
  21
  22     * The freemap is flushed in a manner similar to the normal H2 filesystem,
  23       but as mentioned above it can be synchronized independently of the data
  24       it represents.  One freemap flush could cover several H2 flushes.  A
  25       freemap flush is not necessary for e.g. a fsync() or sync() to
  26       complete successfully.
  27
  28     * The freemap granularity is 64KB (radix of 16) but the minimum
  29       allocation radix for code is 1KB (radix of 10).  1KB inodes can
  30       hold up to 512 bytes of direct data, so small files eat exactly
  31       1KB of media storage inclusive of the inode.
  32
  33     * Representation of storage is block-oriented with ~1KB granularity
  34       in the filesystem topology.  However, H2 also stores freemap locality
  35       hints in the inode at all levels which specifies which freemap zones
  36       all storage allocations made by the sub-tree are allocated from.  Up
  37       to four zones may be listed in each inode.  The zones are power-of-2
  38       sized and aligned the same and use a base/radix representation
  39       (same as used for blockref->data_off).
  40
  41       During updates higher level inodes may not have a sufficient number of
  42       entries to represent the storage used on a fine-grain.  In this
  43       situation the representations back-off to larger radix values.
  44
  45       Ultimately these representations will be optimized by background scans.
  46       That is, ultimately storage localization can be optimized bottom-up
  47       such that it winds up being fairly optimal.  This includes the ability
  48       to detect when a writable snapshot has differentiated sufficiently to
  49       warrant a split.  This optimization should NOT attempt to dup common
  50       data blocks.
  51
  52       XXX
  53
  54     * The zone oriented forward storage references in the inode (the four
  55       entries) is used by the bulk free-scan to reduce the amount of
  56       meta-data which must be duplicatively scanned.  More specifically,
  57       when the sysadmin deletes storage and/or files or even whole directory
  58       subhierachies, it is possible for a bulk free-scan to incrementally
  59       scan the meta-data topology that covers ONLY those areas to determine
  60       if it is possible to free up any actual blocks.
  61
  62       XXX
  63
  64     * H2 does not require that a rm -rf or snapshot destruction, truncation,
  65       or any other operation actually mark freemap blocks as being
  66       almost-free.  That is, the freemap elements can remain set to
  67       ALLOCATED (11).  In fact, it is possible to just delete the directory
  68       inode itself and not even recursively scan or delete sub-directories or
  69       files.  The related storage will eventually be freed by an exhaustive
  70       bulk free-scan anyway.
  71
  72                                 Freemap Topology
  73
  74     The freemap topology contains 4 levels of meta-data (blockref arrays),
  75     one of which is embedded in the volume header (so only three real
  76     meta-data levels), plus one level of leaf-data.
  77
  78     Level 1 - (radix 10) 64KB blockmap representing 2GB.  There are 1024
  79               entries representing ~2MB worth of media storage per entry.
  80
  81               Each entry maps 32 x 64KB allocations @ 2 bits per allocation,
  82               plus contains additional meta-data which allows H2 to cluster
  83               I/O operations.  Each entry locks the allocation granularity
  84               (e.g. to 1KB = radix 10 for inodes).
  85
  86     Level 2 - (radix 10) 64KB blockmap representing 2TB (~2GB per entry)
  87     Level 3 - (radix 10) 64KB blockmap representing 2PB (~2TB per entry)
  88     Level 4 - (radix 10) 64KB blockmap representing 2EB (~2PB per entry)
  89     Level 5 - (radix 3) blockref x 8 in volume header representing 16EB (2^64)
  90               (this conveniently eats one 512-byte 'sector' of the 64KB
  91               volume header).
  92
  93     Each level is assign reserved blocks in the 4MB header per 2GB zone.
  94     Since we use block 0 for the volume header / volume header backup,
  95     our level names above can simply also represent the relative block
  96     number.  Level 1 uses block 1 through level 4 using block 4.  Level 5
  97     is stored in the volume header.
  98
  99     In addition there are FOUR SETS, A, B, C, and D, each containing blocks
 100     for level 1-4.  Hammer2 alternates between sets on a block-by-block basis
 101     in order to maintain consistency when updating the freemap.
 102
 103                                 Leaf Substructure
 104
 105     * radix  - Clustering radix.  All allocations for any given ~2MB zone
 106                are always the same size, allowing the filesystem code to
 107                cluster buffer cache I/O.
 108
 109     * bitmap - four 32 bit words representing ~2MB in 64KB allocation chunks
 110                at 2 bits per chunk.  The filesystem allocation granularity
 111                can be smaller (currently ~1KB minimum), and the live
 112                filesystem keeps caches iterations when allocating multiple
 113                chunks.  However, on remount any partial allocations out of
 114                a 64KB allocation block causes the entire 64KB to be
 115                considered allocated.  Fragmented space can potentially be
 116                reclaimed and/or relocated by the bulk block free scan.
 117
 118                The 2-bit bitmap fields are assigned as follows:
 119
 120                00       FREE
 121                01       ARMED for free stage (future use)
 122                10       ARMED for free stage (future use)
 123                11       ALLOCATED
 124
 125                It should be noted that in some cases, such as snapshot
 126                destruction, H2 does not bother to actually ARM the related
 127                blocks (which would take a long time).  Instead, the bulk
 128                free-scan may have to do a more exhaustive scan.
 129
 130                               Blockref Substructure
 131
 132     The blockref substructure at each level steals some space from the
 133     check code area (a 24-byte area).  We only need 4 bytes for the check
 134     code icrc.  We use some of the remaining space to store information
 135     that allows the block allocator to do its work more efficiently.
 136
 137     * bigmask - A mask of radixes available for allocation under this
 138                 blockref.  Typically initialized to -1.
 139
 140     * avail   - Total available space in bytes.
 141
 142     The freemap allocator uses a cylinder-group-like abstraction using
 143     the localized allocation concept first implemented by UFS.  In HAMMER2
 144     there is no such thing as a real cylinder group, but we do the next
 145     best thing by implementing our layer 1 blockmap representing 2GB.
 146
 147     The layer 1 blockmap is an array of 1024 blockrefs, so each blockref
 148     covers 2MB worth of media storage.  HAMMER2's 'cylinder group' concept
 149     thus has a minimum granularity of 2MB.  A typical setting might be e.g.
 150     10MB.
 151
 152     By localizing allocations to cylinder groups based on various bits of
 153     information, HAMMER2 tries to allocate space on the disk and still leave
 154     some left over for localized expansion and to reduce fragmentation at
 155     the same time.  Not an easy task, especially considering the copy-on-write
 156     nature of the filesystem.  This part of the algorithm likely needs a lot
 157     of work but I hope I've laid down a media format that will not have to be
 158     changed down the line to accomodate better allocation strategies.
 159
 160                                 Initial Conditions
 161
 162     The freemap is a multi-indirect block structure but there is no real
 163     reason to pre-format it in newfs_hammer2.  Instead, newfs_hammer2 simply
 164     leaves the associated top-level indirect blocks empty and uses the
 165     (voldata->allocator_beg) field to allocate space linearly, then leaves
 166     it to the live filesystem to initialize the freemap as more space gets
 167     allocated.
 168
 169                                 How blocks are freed
 170
 171     The freemap bit patterns for each 64KB block are as follows:
 172
 173        00       FREE
 174        01       ARMED (for free) (future use)
 175        10       ARMED (for free) (future use)
 176        11       ALLOCATED
 177
 178     Currently H2 only implements 00 and 11.  When a file, topology, or
 179     snapshot is deleted H2 simply leaves the blocks marked allocated but
 180     records the related freezone/radix(s) in memory.
 181
 182     At some point a background bulk free-scan will run.  This code must
 183     scan meta-data and has a limited cache to detect duplicative sub-trees
 184     (due to snapshots).  It uses the freezone/radix information recorded
 185     in memory to reduce the complexity of the scan, find all references to
 186     the related blocks in the meta-data, and determines what can actually
 187     be freed.  Once this determination is made the bulk free-scan sets
 188     the related freemap bits to FREE (00).
 189
 190     An exhaustive free-scan is not usually required during normal operation
 191     but is typically run incrementally by cron every so often to ensure, over
 192     time, that all freeable blocks are actually freed.  This is most useful
 193     when maintaining multiple snapshots.
 194
 195                         Use of Generic indirect-block API
 196
 197     I decided to use the same indirect-block allocation model for the
 198     freemap that normal files use, with a few special cases added to force
 199     specific radix values and to 'allocate' the freemap-related blocks
 200     and indirect blocks via a reserved-block calculation and (obviously)
 201     not via a recursive call to the allocator.
 202
 203     The Freemap is defined above as a fixed 5-level scheme (level 1-5),
 204     but in actual operation the radix tree can be shortcut just as it
 205     is with normal files.  However, shorcuts are forced into the radix
 206     values of this specification and reserved blocks are calculated based
 207     on the radix level and offset, so as the freemap becomes more fleshed
 208     out the tree looks more and more like the specification.
 209
 210     One advantage of doing things this way is that smaller filesystems
 211     won't actually use a 6-level scheme.  A 16GB filesystem can use 8
 212     blockrefs at layer 5 (in the volume header) that point directly to
 213     layer 1.  A 16TB filesystem can use 8 blockrefs at layer5 that point
 214     to layer 2.  And so forth.
 215
 216     At the moment we have no plans to return any of the unused 4MB zone
 217     header space (per 2GB of storage) back to the filesystem for general use.
 218     There are lots of things we may want to use the reserved areas for in
 219     the future.