• Robbie Ko's avatar
    btrfs: speedup dead root detection during orphan cleanup · a619b3c7
    Robbie Ko authored
    When mounting, we handle deleted subvolume and orphan items.  First,
    find add orphan roots, then add them to fs_root radix tree.  Second, in
    tree-root, process each orphan item, skip if it is dead root.
    
    The original algorithm is based on the list of dead_roots, one by one to
    visit and check whether the objectid is consistent, the time complexity
    is O (n ^ 2).  When processing 50000 deleted subvols, it takes about
    120s.
    
    Because btrfs_find_orphan_roots has already ran before us, and added
    deleted subvol to fs_roots radix tree.
    
    The fs root will only be removed from the fs_roots radix tree after the
    cleaner process is started, and the cleaner will only start execution
    after the mount is complete.
    
    btrfs_orphan_cleanup can be called during the whole filesystem mount
    lifetime, but only "tree root" will be used in this section of code, and
    only mount time will be brought into tree root.
    
    So we can quickly check whether the orphan item is dead root through the
    fs_roots radix tree.
    Reviewed-by: default avatarFilipe Manana <fdmanana@suse.com>
    Signed-off-by: default avatarRobbie Ko <robbieko@synology.com>
    Signed-off-by: default avatarDavid Sterba <dsterba@suse.com>
    a619b3c7
inode.c 281 KB