• Christoph Hellwig's avatar
    xfs: use a b+tree for the in-core extent list · 6bdcf26a
    Christoph Hellwig authored
    Replace the current linear list and the indirection array for the in-core
    extent list with a b+tree to avoid the need for larger memory allocations
    for the indirection array when lots of extents are present.  The current
    extent list implementations leads to heavy pressure on the memory
    allocator when modifying files with a high extent count, and can lead
    to high latencies because of that.
    
    The replacement is a b+tree with a few quirks.  The leaf nodes directly
    store the extent record in two u64 values.  The encoding is a little bit
    different from the existing in-core extent records so that the start
    offset and length which are required for lookups can be retreived with
    simple mask operations.  The inner nodes store a 64-bit key containing
    the start offset in the first half of the node, and the pointers to the
    next lower level in the second half.  In either case we walk the node
    from the beginninig to the end and do a linear search, as that is more
    efficient for the low number of cache lines touched during a search
    (2 for the inner nodes, 4 for the leaf nodes) than a binary search.
    We store termination markers (zero length for the leaf nodes, an
    otherwise impossible high bit for the inner nodes) to terminate the key
    list / records instead of storing a count to use the available cache
    lines as efficiently as possible.
    
    One quirk of the algorithm is that while we normally split a node half and
    half like usual btree implementations we just spill over entries added at
    the very end of the list to a new node on its own.  This means we get a
    100% fill grade for the common cases of bulk insertion when reading an
    inode into memory, and when only sequentially appending to a file.  The
    downside is a slightly higher chance of splits on the first random
    insertions.
    
    Both insert and removal manually recurse into the lower levels, but
    the bulk deletion of the whole tree is still implemented as a recursive
    function call, although one limited by the overall depth and with very
    little stack usage in every iteration.
    
    For the first few extents we dynamically grow the list from a single
    extent to the next powers of two until we have a first full leaf block
    and that building the actual tree.
    
    The code started out based on the generic lib/btree.c code from Joern
    Engel based on earlier work from Peter Zijlstra, but has since been
    rewritten beyond recognition.
    Signed-off-by: 's avatarChristoph Hellwig <hch@lst.de>
    Reviewed-by: 's avatarDarrick J. Wong <darrick.wong@oracle.com>
    Signed-off-by: 's avatarDarrick J. Wong <darrick.wong@oracle.com>
    6bdcf26a