[PATCH] Btrfs : improve the speed of compare orphan item and dead roots with tree root when mount

[robbieko <robbieko@synology.com>]

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.

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>
---
 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