Skip to contentSkip to conversation

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

PATCH Superseded robbieko 2 participants 5 messages Apr 27, 2020 – May 6, 2020 Btrfs file system

v1 of 2 Superseded Latest is v2 →

lore
Share & tools
lore

robbieko

author
#0 lore raw

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

We can quickly check whether the orphan item is dead root through the fs_roots radix tree.

---
 fs/btrfs/inode.c | 20 +++++++++-----------
 1 file changed, 9 insertions(+), 11 deletions(-)
fs/btrfs/inode.c +9 -11
index 320d1062068d..1becf5c63e5a 100644
@@ -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
#1 lore raw
Quoted 37 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_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.

---
 fs/btrfs/inode.c | 20 +++++++++-----------
 1 file changed, 9 insertions(+), 11 deletions(-)
fs/btrfs/inode.c +1 -8
index 320d1062068d..1becf5c63e5a 100644
@@ -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;

fs/btrfs/inode.c int btrfs_orphan_cleanup(struct btrfs_root *root) · line 3011

Quoted 10 lines
fs/btrfs/inode.c +7 -3
-				}
-			}
-			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);

The list uses fs_info::trans_lock and the radix uses fs_roots_radix_lock. I'd like to know why you think it's safe.

The trans_lock is used for a lot of things, fs_roots_radix_lock is for the radix tree insertion/deletion/update/lookup so it does not seem like an equivalent change. It could be functionally equivalent due to some other constraint, like that the number of references is 0 and the tree won't be ever touched outside of the orphan cleanup process.

btrfs_orphan_cleanup can be called during the whole filesystem mount lifetime, so we can't rely on the mount time where nothing can iterfere.

author
#2 lore raw

David Sterba 於 2020-04-27 23:46 寫到:

Quoted 53 lines · robbieko
Quoted 38 lines

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.

We can quickly check whether the orphan item is dead root through the fs_roots radix tree.

---
 fs/btrfs/inode.c | 20 +++++++++-----------
 1 file changed, 9 insertions(+), 11 deletions(-)
fs/btrfs/inode.c +1 -8
index 320d1062068d..1becf5c63e5a 100644
@@ -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;

fs/btrfs/inode.c int btrfs_orphan_cleanup(struct btrfs_root · line 3012

Quoted 10 lines
fs/btrfs/inode.c +7 -3
-				}
-			}
-			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);

The list uses fs_info::trans_lock and the radix uses fs_roots_radix_lock. I'd like to know why you think it's safe.

Quoted 5 lines

The trans_lock is used for a lot of things, fs_roots_radix_lock is for the radix tree insertion/deletion/update/lookup so it does not seem like an equivalent change. It could be functionally equivalent due to some other constraint, like that the number of references is 0 and the tree won't be ever touched outside of the orphan cleanup process.

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.

So we can directly find the root from the radix tree.

Quoted 3 lines

btrfs_orphan_cleanup can be called during the whole filesystem mount lifetime, so we can't rely on the mount time where nothing can iterfere.

Only "tree root" will be used in this section of code, and only mount time will be brought into tree root.

author
#3 lore raw

Hi

Does anyone have suggestions ?

Thanks.
Robbie Ko

robbieko 於 2020-04-28 11:12 寫到:

Quoted 75 lines

David Sterba 於 2020-04-27 23:46 寫到:

Quoted 53 lines · robbieko
Quoted 38 lines

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.

We can quickly check whether the orphan item is dead root through the fs_roots radix tree.

---
 fs/btrfs/inode.c | 20 +++++++++-----------
 1 file changed, 9 insertions(+), 11 deletions(-)
fs/btrfs/inode.c +1 -8
index 320d1062068d..1becf5c63e5a 100644
@@ -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;

fs/btrfs/inode.c int btrfs_orphan_cleanup(struct btrfs_root · line 3012

Quoted 10 lines
fs/btrfs/inode.c +7 -3
-				}
-			}
-			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);

The list uses fs_info::trans_lock and the radix uses fs_roots_radix_lock. I'd like to know why you think it's safe.

Quoted 5 lines

The trans_lock is used for a lot of things, fs_roots_radix_lock is for the radix tree insertion/deletion/update/lookup so it does not seem like an equivalent change. It could be functionally equivalent due to some other constraint, like that the number of references is 0 and the tree won't be ever touched outside of the orphan cleanup process.

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.

So we can directly find the root from the radix tree.

Quoted 3 lines

btrfs_orphan_cleanup can be called during the whole filesystem mount lifetime, so we can't rely on the mount time where nothing can iterfere.

Only "tree root" will be used in this section of code, and only mount time will be brought into tree root.

#4 lore raw
Quoted 3 lines · robbieko

Hi

Does anyone have suggestions ?

Please update the changelog explaining the locking change and resend, thanks.