xref: /dragonfly/sys/vfs/hammer2/FREEMAP (revision bbb35c81)

			HAMMER2 Freemap Design Notes

				Overview

    HAMMER2 Media is broken down into 2 GByte zones.  Each 2 GByte zone
    contains a 4 MByte header (64 x 64K blocks = 0.2% of storage).  The
    blocks in this header are reserved for various purposes.  For example,
    block #0 is reserved for a volume header in the first four zones.  Most
    of the remaining 64KB blocks in this header are reserved for use by the
    freemap.

    The freemap only uses blocks from these reserved areas.  In order to
    ensure that any of the four volume headers can be used by the mount code
    (in case some are found to be corrupted), each freemap block in the
    logical freemap topology will iterate through up to 8 copies whos
    block numbers are taken the reserved area.

    - Four copies, one for each of the four volume headers which H2 sequences
      through on each flush.  This ensures that a mount from any of the four
      volume headers is handed a consistent freemap topology.

    - One copy to ensure that recovery operations during mount do not modify
      the state of the freemap topology pointed to by older volume headers
      which are still valid.  Note that the freemap for volume headers
      indexed after the mount point being recovered may lose freemap
      consistency, so if you choose an older mount point for a RW mount,
      you have to stick with it.

    - One copy for live operations.  This allows HAMMER2 to retire the
      related buffer asynchronously in the background (or for the OS to
      retire the buffer cache buffer on its own) prior to the formal
      flush.  The later formal flush then has less work to do.

    - The two remaining copies add robustness to the specification.  For
      example, with appropriate feature code added the filesystem can
      tolerate a limited number of bad blocks in the reserved area.

    For the moment we use a simple calculation for the freemap block.  In
    a later version I would like to mix the blocks up a bit so the blocks
    in each set of 8 are not situated near each other.

			    RW Mount Restrictions

    If an older volume header is explicitly selected by the mount code, any
    newer (presumably corrupt since the mount code didn't select it) volume
    headers will lose freemap consistency as the freemap code rotates into
    freemap blocks that might have been used by the topology pointed to by
    the newer (but not selected) volume headers.  For a RW mount, this means
    that if an older volume header is selected, the newer ones that were
    not selected WILL be formally invalidated by the mount code and cannot
    be used in a remount attempt.

    During normal operation, each filesystem flush rotates to a new volume
    header.  A filesystem may have up to four volume headers spread at 2GB
    intervals.  Filesystems smaller than ~9GB or so will have fewer volume
    headers to rotate through.

				Freemap Topology

    The freemap topology contains 4 levels of meta-data (blockref arrays),
    one of which is embedded in the volume header (so only three real
    meta-data levels), plus one level of leaf-data.  Unlike normal files,
    which use a variable-radix, the freemap topology uses a fixed radix to
    simplify the algorithm and to ensure freemap locality to the blocks
    under management.

    Freemap blocks are allocated from the reserved area in each 2GB zone.
    The leafs represent data in the zone.  Higher levels in the freemap
    topology will cover more area but the physical freemap meta-data blocks
    always occur prior to the area being covered.  Thus a HAMMER2 filesystem
    of almost any size can be formatted and the related freemap blocks
    will always exist.

    Level 1 - (radix 10 + 21) 64KB representing 2GB.  This is represented
	      by a hammer2_bmap_data[1024] array.  Each entry represents
	      2MB worth of media storage x 1024 entries to represent 2GB.
	      Each entry contains a 128x2 bit bitmap representing 16KB
	      of storage in 2 bits (128 x 16KB = 2MB).

    Level 2 - (radix 10) 64KB blockmap representing 2TB (~2GB per entry)
    Level 3 - (radix 10) 64KB blockmap representing 2PB (~2TB per entry)
    Level 4 - (radix 10) 64KB blockmap representing 2EB (~2PB per entry)
    Level 5 - (radix 3) blockref x 8 in volume header representing 16EB (2^64)
	      (this conveniently eats one 512-byte 'sector' of the 64KB
	      volume header).

    Each level is assign reserved blocks in the 4MB header per 2GB zone.
    Since we use block 0 for the volume header, the first freemap reserved
    block in the zone begins at block 1.

    Freemap copy #0:
	Level 1 uses block 1 (this is the leaf block)
	Level 2 uses block 2
	Level 3 uses block 3
	Level 4 uses block 4

    Freemap copy #1:
	Level 1 uses block 5 (this is the leaf block)
	Level 2 uses block 6
	Level 3 uses block 7
	Level 4 uses block 8

    ... and so forth up to Freemap copy #7 using blocks 29, 30, 31, and 32.

				    Flushing

    The freemap does not have to be flushed by fsync/sync, but should probably
    be flushed at least once a minute by the normal filesystem sync.  The
    reason it does not have to be flushed with fsync is that freemap recovery
    is executed on-mount and will use the last fully flushed freemap TID
    stored in the volume header to do an incremental meta-data scan of the
    H2 filesystem between that TID and the last flushed TID.  All blocks not
    found to have been marked allocated will be marked allocated.  Simple as
    that.  Since the scan is incremental, this typically costs very little
    time.

				Freemap Granularity

    The freemap granularity is 16KB (radix of 14) but the minimum
    allocation radix is 1KB (radix of 10) (and can be in multiples of
    1KB with some coding).  1KB inodes can hold up to 512 bytes of direct
    data, so tiny files eat exactly 1KB of media storage inclusive of the
    inode.

    The freemap keeps track of partial allocations in-memory but not
    on-media, so even a normal umount will cause partially allocated
    blocks to appear fully allocated until some later date when the
    bulk scan code defragments it.

				 Block Selection

    Block selection is localized to be near the inode's (or nearby data)
    blockref.  The algorithmic complexity of determining locality is not
    defined here atm.

			     Freemap Leaf Substructure

    * linear - Linear sub-granular allocation offset.  Allows ~1KB granular
	       linear allocations.

    * class  - Allocation clustering class ((type << 8) | radix).

    * avail  - Available space in bytes, currently only used by layer 1 leaf.
	       Used as an allocation clustering aid.

    * bitmap - Eight 32 bit words representing ~2MB in 16KB allocation chunks
	       at 2 bits per chunk.  The filesystem allocation granularity
	       can be smaller (currently ~1KB minimum), and the live
	       filesystem caches iterations when allocating multiple chunks.
	       However, on remount any partial allocations out of a 64KB
	       allocation block MAY cause the entire 64KB to be considered
	       allocated.  Fragmented space can potentially be reclaimed
	       and/or relocated by the bulk block free scan.

	       The 2-bit bitmap fields are assigned as follows:

	       00	FREE
	       01	POSSIBLY FREE (type 1)
	       10	POSSIBLY FREE (type 2)
	       11	ALLOCATED

			  Freemap Metadata Substructure
			     (Levels 2, 3, 4, and 5)

    Freemap layers 2, 3, 4, and 5 operate as arrays of blockrefs but steal
    some of the check area (a 24-byte area) for freemap-specific meta-data.
    We reserve a few fields to store information which allows the block
    allocator to do its work more efficiently.

    * bigmask - A mask of radixes available for allocation under this
		blockref.  Typically initialized to -1.

    * avail   - Total available space in bytes.

    The freemap allocator uses a cylinder-group-like abstraction using
    the localized allocation concept first implemented by UFS.  In HAMMER2
    there is no such thing as a real cylinder group, nor are there specific
    reserved areas for inodes vs data, but we do the next best thing by
    roughly typing leafs (each leaf representing ~2MB) to hopefully allow
    the drive to employ its zone-cache to make both stat-only and tar-style
    bulk accesses efficient (in addition to normal file accesses).

    Levels 2, 3, and 4 contains an array blockmap[1024] (64KB total),
    supplying 10 bits of address space each.  Level 5 is a blockmap[8]
    stored in the volume header supplying 3 bits of address space.
    (level 0 supplies 10 + 21 bits of address space).

    The Level1 blockmap is HAMMER2's idea of a 'cylinder group', thus
    effectively fixed at multiples of ~2MB or so.

			        Initial Conditions

    newfs_hammer2 does not need to format the freemap.  Instead, newfs_hammer2
    simply leaves the associated top-level indirect blocks empty and uses
    the (voldata->allocator_beg) field to allocate space linearly, then
    leaves it to the live filesystem to initialize the freemap as more space
    gets allocated.

    The freemap does NOT use a fixed 5-level radix tree.  It uses the same
    blockmap algorithm used for file blocks but restricts any recursion to
    specific radix values.  This means that small filesystems will have much
    smaller freemap depths.  2 layers (and not counting the volume header as
    a layer) gets us 16GB, 3 layers gets us 16TB.

			How blocks are allocated and freed

    The H2 freemap leaf bitmap operates in 16KB chunks, but the leaf also
    contains a linear allocation offset that can keep track of sub-16KB
    allocations with certain restrictions.  More random sub-16KB allocations
    are tracked in-memory, but will be lost (assumed to be a full 16KB) if
    a crash occurs.  Each 16KB chunk is denoted by a 2-bit pattern 00, 01, 10,
    or 11.

    NOTE!  All operations on the freemap occur on the current live version
	   of the freemap, including bulkfree operations.

    Blocks are allocated by transitioning the 2-bit pattern in the leaf
    to 11.  That is, (00, 01, 10) -> (11).

    The primary mechanism used to free a block is via the asynchronous
    bulkfree scan.  This scans all filesystem meta-data in two major passes
    (and potentially multiple sub-passes).

    Pass#1 - The first pass figures which blocks might be freeable.  The
	     most recently flushed meta-data topology (including all four
	     volume headers and all snapshots) is scanned and an in-memory
	     copy of the FreeMap is built from scratch.  Multiple sub-scans
	     might be required to break the larger scan up into more easily
	     digested pieces based on the amount of memory available to hold
	     the temporary freemap.

	     Any allocated blocks in the live freemap are then transitioned
	     from (11) to either (10) or (01) if after the scan they are
	     found to not be allocated.

	     The blocks are still assumed to be allocated at this time and
	     any new allocations will transition them back to (11).

    Pass#2 - The second pass is required to deal with races against the
	     live filesystem while the freemap scan was running. It also
	     allows the freemap scans to run asynchronously from any flush,
	     improving concurrency.  However, at least one synchronous flush
	     is required between Pass#1 and Pass#2.

	     The second pass is a duplicate of the first pass.  The meta-data
	     topology is scanned and a freemap is built in-memory and then
	     compared against the live freemap.  Instead transitioning from
	     (11)->(10)/(01) this pass transitions from (10)/(01) to (00).

	     If a block that it thinks is free is (11), no transition occurs
	     because this could be due to a race against the live filesystem.

	     This pass will incidentally transition (10)/(01) back to (11)
	     if the block was found not to be allocated, but it is perfectly
	     acceptable for the block to remain in a (10)/(01) state after
	     completion.

    NOTE! The meta-data scanning passes must also explicitly scan blocks
	  associated with any open files, since these might represent
	  open-but-deleted files.  These blocks must not be accidentally freed
	  while the system is still using the file.  Again, since this is
	  done in two passes it does not have to be synchronized against
	  frontend operations.  So in total:

	  * Topology under all four volume headers.  This includes all
	    PFSs and snapshots.

	  * Topology under all open hammer2 files.

    The Bulk-free operation is expensive but uses a bounded amount of ram.
    The ADVANTAGE of this mechanism is that deletions in the live filesystem
    do not have to clean up the freemap and thus do not have to recurse
    the topology during the deletion.  In fact, a 'rm -rf' equivalent of a
    directory topology can be handled simply by blowing away the top-level
    directory inode.  This is instantanious and thus can be dangerous but
    you always have your snapshots to fall-back on.

    The DISADVANTAGE is that all meta-data must be scanned.  Twice.  This
    can be mitigated by using swapcache(8) to cache the meta-data on a SSD.
    This is also mitigated by the fact that you can do the bulkfree scan less
    often on very large filesystems which presumably have a lot of freespace
    (so the interval is not as big an issue).  In a sense the operation does
    scale in that it takes longer on larger filesystems but also can be run
    less often.

    The biggest issue is that *NO* space can be freed up by the live
    filesystem without the bulkfree process unless we optimize the case
    where data is created and deleted from within a single snapshot.
    This is made more difficult by the fact that each flush represents
    a fine-grained snapshot (up to four, representing the four volume
    headers the flush iterates through).

		      Snapshots and Replicated Topologies

    The bulkfree code maintains information in-memory to the best of its
    ability for a multitude of reasons, including attempting to detect
    snapshot recursions down block chains which have already been scanned
    via some other snapshot.  Without this, a large number of snapshots
    can cause a huge multiplication of disk I/O reads (but not writes) during
    the topology scan.

			Use of Generic indirect-block API

    I decided to use the same indirect-block allocation model for the
    freemap that normal files use, with a few special cases added to force
    specific radix values and to 'allocate' the freemap-related blocks
    and indirect blocks via a reserved-block calculation and (obviously)
    not via a recursive call to the allocator.

    The Freemap is defined above as a fixed 5-level scheme (level 1-5),
    but in actual operation the radix tree can be shortcut just as it
    is with normal files.  However, unlike normal files, shorcuts will
    be forced to use specific radix values in order to guarantee that
    reserved block numbers can be trivially calculated.  As the freemap
    becomes more fleshed out the tree on-media will look more and more like
    the actual specification.

    One advantage of doing things this way is that smaller filesystems
    won't actually use a 5-level scheme.  A 16GB filesystem can use 8
    blockrefs in the volume header which point directly to layer 1 leaf
    blocks.  A 16TB filesystem can be managed with only three levels
    (layer 3, 2, and 1 only where the 8 x layer 3 blockrefs are stored in
    the volume header).  And so forth.

    At the moment we have no plans to return any of the unused 4MB zone
    header space (per 2GB of storage) back to the filesystem for general use.
    There are lots of things we may want to use the reserved areas for in
    the future.

				Emergency Deletions

    All filesystem modifications including deletions must allocate blocks
    in order to update the main topology all the way to the root.  H2 will
    reserve roughly 5% of the available blocks in the filesystem for
    deletions in order to allow a system operator to recover from a
    filesystem full condition.

    However, due to the snapshot capability as well as the possibility of
    fragmentation, it is possible for the administrator to not delete enough
    to actually be able to free up blocks.  Once the reserve is used up
    the filesystem can become unwritable.

    When this situation occurs the only way to recover is to update blocks
    in-place.  Updating blocks in-place will destroy the data on any
    related snapshots or otherwise corrupt the snapshots.  Emergency recovery
    thus recommends that all related snapshots be destroyed.  You can choose
    not to do this in which case your snapshots might wind up containing
    broken links and generate CRC failure messages.

    For the moment the spec for dealing with these situations remains
    incomplete.