Btrfs : improve the speed of compare orphan item and dead roots with tree root when mount
PATCH v2 1/1 Btrfs : improve the speed of compare orphan item and dead roots with tree root when mount
From: Robbie Ko <[email protected]>
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.
---
Changes in v2:
- update changelog
--- fs/btrfs/inode.c | 20 +++++++++----------- 1 file changed, 9 insertions(+), 11 deletions(-)
fs/btrfs/inode.c +9 -11
@@ -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 ;
Signature · 1 line
2.17.1
Quoted 19 lines · robbieko
From: Robbie Ko <[email protected]>
When mounting, we handle deleted subvol and orphan items. First, find add orphan roots, then add them to
fs_rootradix 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_rootshas already ran before us, and added deleted subvol tofs_rootsradix tree.The fs root will only be removed from the
fs_rootsradix tree after the cleaner is processed, and the cleaner will only start execution after the mount is complete.
Quoted 8 lines
btrfs_orphan_cleanupcan 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_rootsradix tree.Signed-off-by Robbie Ko <[email protected]>
"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.
Quoted 42 lines
---
Changes in v2:
- update changelog--- fs/btrfs/inode.c | 20 +++++++++----------- 1 file changed, 9 insertions(+), 11 deletions(-)fs/btrfs/inode.c +9
-12@@ -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
Signature · 3 lines
Filipe David Manana, “Whether you think you can, or you think you can't — you're right.”
Quoted 22 lines · robbieko
From: Robbie Ko <[email protected]>
When mounting, we handle deleted subvol and orphan items. First, find add orphan roots, then add them to
fs_rootradix 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_rootshas already ran before us, and added deleted subvol tofs_rootsradix tree.The fs root will only be removed from the
fs_rootsradix tree after the cleaner is processed, and the cleaner will only start execution after the mount is complete.
btrfs_orphan_cleanupcan 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.
Quoted 7 lines
So we can quickly check whether the orphan item is dead root through the
fs_rootsradix tree.Signed-off-by Robbie Ko <[email protected]>---
Changes in v2:
- update changelog
Thanks, added to misc-next, with the updated subject.