| Message ID | 20200507025440.6619-1-robbieko@synology.com (mailing list archive) |
|---|---|
| State | New, archived |
| Headers | show |
| Series | [v2] Btrfs : improve the speed of compare orphan item and dead roots with tree root when mount | expand |
On Thu, May 7, 2020 at 4:27 AM robbieko <robbieko@synology.com> wrote: > > From: Robbie Ko <robbieko@synology.com> > > When mounting, we handle deleted subvol 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 is processed, 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. > > Signed-off-by: Robbie Ko <robbieko@synology.com> "Btrfs : improve the speed of compare orphan item and dead roots with tree root when mount" That's a really long subject and confusing - compare orphan item? All we do is check whether a root is dead or not. So I would suggest some shorter and clear: "Btrfs: speedup dead root detection during orphan cleanup" Other than that, looks good, thanks. Reviewed-by: Filipe Manana <fdmanana@suse.com> > --- > Changes in v2: > - update changelog > --- > fs/btrfs/inode.c | 20 +++++++++----------- > 1 file changed, 9 insertions(+), 11 deletions(-) > > diff --git a/fs/btrfs/inode.c b/fs/btrfs/inode.c > index 320d1062068d..1becf5c63e5a 100644 > --- a/fs/btrfs/inode.c > +++ b/fs/btrfs/inode.c > @@ -3000,18 +3000,16 @@ int btrfs_orphan_cleanup(struct btrfs_root *root) > * orphan must not get deleted. > * find_dead_roots already ran before us, so if this > * is a snapshot deletion, we should find the root > - * in the dead_roots list > + * in the fs_roots radix tree. > */ > - spin_lock(&fs_info->trans_lock); > - list_for_each_entry(dead_root, &fs_info->dead_roots, > - root_list) { > - if (dead_root->root_key.objectid == > - found_key.objectid) { > - is_dead_root = 1; > - break; > - } > - } > - spin_unlock(&fs_info->trans_lock); > + > + spin_lock(&fs_info->fs_roots_radix_lock); > + dead_root = radix_tree_lookup(&fs_info->fs_roots_radix, > + (unsigned long)found_key.objectid); > + if (dead_root && btrfs_root_refs(&dead_root->root_item) == 0) > + is_dead_root = 1; > + spin_unlock(&fs_info->fs_roots_radix_lock); > + > if (is_dead_root) { > /* prevent this orphan from being found again */ > key.offset = found_key.objectid - 1; > -- > 2.17.1 >
On Thu, May 07, 2020 at 10:54:40AM +0800, robbieko wrote: > From: Robbie Ko <robbieko@synology.com> > > When mounting, we handle deleted subvol 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 is processed, 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. > > Signed-off-by: Robbie Ko <robbieko@synology.com> > --- > Changes in v2: > - update changelog Thanks, added to misc-next, with the updated subject.
diff --git a/fs/btrfs/inode.c b/fs/btrfs/inode.c index 320d1062068d..1becf5c63e5a 100644 --- a/fs/btrfs/inode.c +++ b/fs/btrfs/inode.c @@ -3000,18 +3000,16 @@ int btrfs_orphan_cleanup(struct btrfs_root *root) * orphan must not get deleted. * find_dead_roots already ran before us, so if this * is a snapshot deletion, we should find the root - * in the dead_roots list + * in the fs_roots radix tree. */ - spin_lock(&fs_info->trans_lock); - list_for_each_entry(dead_root, &fs_info->dead_roots, - root_list) { - if (dead_root->root_key.objectid == - found_key.objectid) { - is_dead_root = 1; - break; - } - } - spin_unlock(&fs_info->trans_lock); + + spin_lock(&fs_info->fs_roots_radix_lock); + dead_root = radix_tree_lookup(&fs_info->fs_roots_radix, + (unsigned long)found_key.objectid); + if (dead_root && btrfs_root_refs(&dead_root->root_item) == 0) + is_dead_root = 1; + spin_unlock(&fs_info->fs_roots_radix_lock); + if (is_dead_root) { /* prevent this orphan from being found again */ key.offset = found_key.objectid - 1;