• Filipe Manana's avatar
    btrfs: use rbtree with leftmost node cached for tracking lowest block group · 08dddb29
    Filipe Manana authored
    We keep track of the start offset of the block group with the lowest start
    offset at fs_info->first_logical_byte. This requires explicitly updating
    that field every time we add, delete or lookup a block group to/from the
    red black tree at fs_info->block_group_cache_tree.
    
    Since the block group with the lowest start address happens to always be
    the one that is the leftmost node of the tree, we can use a red black tree
    that caches the left most node. Then when we need the start address of
    that block group, we can just quickly get the leftmost node in the tree
    and extract the start offset of that node's block group. This avoids the
    need to explicitly keep track of that address in the dedicated member
    fs_info->first_logical_byte, and it also allows the next patch in the
    series to switch the lock that protects the red black tree from a spin
    lock to a read/write lock - without this change it would be tricky
    because block group searches also update fs_info->first_logical_byte.
    Reviewed-by: default avatarNikolay Borisov <nborisov@suse.com>
    Signed-off-by: default avatarFilipe Manana <fdmanana@suse.com>
    Reviewed-by: default avatarDavid Sterba <dsterba@suse.com>
    Signed-off-by: default avatarDavid Sterba <dsterba@suse.com>
    08dddb29
free-space-tree.c 40.2 KB