btrfs-progs: Fix delayed ref leakage

[BUG]
Btrfs-progs sometimes fails to find certain extent backref when committing transaction.
The most reliable way to reproduce it is fsck-test/013 on 64K page sized system:
[...]
adding new data backref on 315859712 root 287 owner 292 offset 0 found 1 btrfs unable to find ref byte nr 31850496 parent 0 root 2 owner 0 offset 0 Failed to find [30867456, 168, 65536]

Also there are some github bug reports related to this problem.

[CAUSE]
Commit 909357e86799 ("btrfs-progs: Wire up delayed refs") introduced delayed refs in btrfs-progs.

However in that commit, delayed refs are not run at correct timing. That commit calls btrfs_run_delayed_refs() before btrfs_write_dirty_block_groups(), which needs to update BLOCK_GROUP_ITEMs in extent tree, thus could cause new delayed refs.

This means each time we commit a transaction, we may screw up the extent tree by dropping some pending delayed refs, like:

Transaction 711:
btrfs_commit_transaction()

|- btrfs_run_delayed_refs()
|  Now all delayed refs are written to extent tree
|
|- btrfs_write_dirty_block_groups()
|  Needs to update extent tree root
|  ADD_DELAYED_REF to 315859712.
|  Delayed refs are attached to current trans handle.
|
|- __commit_transaction()
|- write_ctree_super()
|- btrfs_finish_extent_commit()
|- kfree(trans)

Now delayed ref for 315859712 are lost

Transaction 712:
Tree block 315859712 get dropped
btrfs_commit_transaction()
|- btrfs_run_delayed_refs()
|- run_one_delayed_ref()
|- __free_extent()
As previous ADD_DELAYED_REF to 315859712 is lost, extent tree doesn't has any backref for 315859712, causing the bug

In fact, commit c31edf610cbe ("btrfs-progs: Fix false ENOSPC alert by tracking used space correctly") detects the tree block leakage, but in the reproducer we have too many noise, thus nobody notices the leakage warning.

[FIX]
We can't just move btrfs_run_delayed_refs() after btrfs_write_dirty_block_groups(), as during btrfs_run_delayed_refs(), we can re-dirty block groups.
Thus we need to exhaust both delayed refs and dirty blocks.

This patch will call btrfs_write_dirty_block_groups() and btrfs_run_delayed_refs() in a loop until both delayed refs and dirty blocks are exhausted. Much like what we do in commit_cowonly_roots() in kernel.

Also, to prevent such problem from happening again (and not to debug such problem again), add extra check on delayed refs before freeing the trans handle.

Reported-by Klemens Schölhorn <[email protected]>

Issue: 187

Signed-off-by Qu Wenruo <[email protected]>

---
 transaction.c | 27 +++++++++++++++++++++------
 1 file changed, 21 insertions(+), 6 deletions(-)

transaction.c +21 -6

index 551fb24e674d..3b0a428db76e 100644
@@ -193,17 +193,32 @@ commit_tree:
 	ret = commit_tree_roots(trans, fs_info);
 	if (ret < 0)
 		goto error;
+
 	/*
-	 * Ensure that all committed roots are properly accounted in the
-	 * extent tree
+	 * btrfs_write_dirty_block_groups() can cause CoW thus new delayed
+	 * tree refs, while run such delayed tree refs can dirty block groups
+	 * again, we need to exhause both dirty blocks and delayed refs
 	 */
-	ret = btrfs_run_delayed_refs(trans, -1);
-	if (ret < 0)
-		goto error;
-	btrfs_write_dirty_block_groups(trans);
+	while (!RB_EMPTY_ROOT(&trans->delayed_refs.href_root) ||
+		test_range_bit(&fs_info->block_group_cache, 0, (u64)-1,
+			       BLOCK_GROUP_DIRTY, 0))
+	{
+		ret = btrfs_write_dirty_block_groups(trans);
+		if (ret < 0)
+			goto error;
+		ret = btrfs_run_delayed_refs(trans, -1);
+		if (ret < 0)
+			goto error;
+	}
 	__commit_transaction(trans, root);
 	if (ret < 0)
 		goto error;
+
+	/* There should be no pending delayed refs now */
+	if (!RB_EMPTY_ROOT(&trans->delayed_refs.href_root)) {
+		error("Uncommitted delayed refs detected");
+		goto error;
+	}
 	ret = write_ctree_super(trans);
 	btrfs_finish_extent_commit(trans);
 	kfree(trans);

Reported-by Klemens Schölhorn <[email protected]>

Issue: 187

Signed-off-by Qu Wenruo <[email protected]>

In write_one_cache_group() we always do COW to update BLOCK_GROUP_ITEM. However under a lot of cases, the cache->item is not changed at all.

E.g:
Transaction 123, block group [1M, 1M + 16M)

tree block 1M + 0 get freed
tree block 1M + 16K get allocated.

Transaction 123 get committed.

In this case, used space of block group [1M, 1M + 16M) doesn't changed at all, thus we don't need to do COW to update block group item.

This patch will make write_one_cache_group() to do a read-only search first, then do COW if we really need to update block group item.

This should reduce the btrfs_write_dirty_block_groups() and btrfs_run_delayed_refs() loop introduced in previous commit.

Signed-off-by Qu Wenruo <[email protected]>

---
 extent-tree.c | 26 +++++++++++++++++++++++++-
 1 file changed, 25 insertions(+), 1 deletion(-)

extent-tree.c +25 -1

index 932af2c644bd..24d3a1ab3f25 100644
@@ -1533,10 +1533,34 @@ static int write_one_cache_group(struct btrfs_trans_handle *trans,
 	unsigned long bi;
 	struct extent_buffer *leaf;
 
+	/* Do a read only check to see if we need to update BLOCK_GROUP_ITEM */
+	ret = btrfs_search_slot(NULL, extent_root, &cache->key, path, 0, 0);
+	if (ret < 0)
+		goto fail;
+	if (ret > 0) {
+		ret = -ENOENT;
+		error("failed to find block group %llu in extent tree",
+			cache->key.objectid);
+		goto fail;
+	}
+	leaf = path->nodes[0];
+	bi = btrfs_item_ptr_offset(leaf, path->slots[0]);
+	ret = memcmp_extent_buffer(leaf, &cache->item, bi, sizeof(cache->item));
+	btrfs_release_path(path);
+	/* No need to update */
+	if (ret == 0)
+		return ret;
+
+	/* Do the COW to update BLOCK_GROUP_ITEM */
 	ret = btrfs_search_slot(trans, extent_root, &cache->key, path, 0, 1);
 	if (ret < 0)
 		goto fail;
-	BUG_ON(ret);
+	if (ret > 0) {
+		ret = -ENOENT;
+		error("failed to find block group %llu in extent tree",
+			cache->key.objectid);
+		goto fail;
+	}
 
 	leaf = path->nodes[0];
 	bi = btrfs_item_ptr_offset(leaf, path->slots[0]);

Quoted 17 lines · Qu Wenruo

In write_one_cache_group() we always do COW to update BLOCK_GROUP_ITEM. However under a lot of cases, the cache->item is not changed at all.

E.g:
Transaction 123, block group [1M, 1M + 16M)

tree block 1M + 0 get freed
tree block 1M + 16K get allocated.

Transaction 123 get committed.

In this case, used space of block group [1M, 1M + 16M) doesn't changed at all, thus we don't need to do COW to update block group item.

This patch will make write_one_cache_group() to do a read-only search first, then do COW if we really need to update block group item.

Quoted 4 lines

This should reduce the btrfs_write_dirty_block_groups() and btrfs_run_delayed_refs() loop introduced in previous commit.

Signed-off-by Qu Wenruo <[email protected]>

I'm not sure how effective this is going to be

and isn't this premature
optimization, have you done any measurements?

Quoted 47 lines

---
 extent-tree.c | 26 +++++++++++++++++++++++++-
 1 file changed, 25 insertions(+), 1 deletion(-)

extent-tree.c +25 -1

index 932af2c644bd..24d3a1ab3f25 100644
@@ -1533,10 +1533,34 @@ static int write_one_cache_group(struct btrfs_trans_handle *trans,
 	unsigned long bi;
 	struct extent_buffer *leaf;
 
+	/* Do a read only check to see if we need to update BLOCK_GROUP_ITEM */
+	ret = btrfs_search_slot(NULL, extent_root, &cache->key, path, 0, 0);
+	if (ret < 0)
+		goto fail;
+	if (ret > 0) {
+		ret = -ENOENT;
+		error("failed to find block group %llu in extent tree",
+			cache->key.objectid);
+		goto fail;
+	}
+	leaf = path->nodes[0];
+	bi = btrfs_item_ptr_offset(leaf, path->slots[0]);
+	ret = memcmp_extent_buffer(leaf, &cache->item, bi, sizeof(cache->item));
+	btrfs_release_path(path);
+	/* No need to update */
+	if (ret == 0)
+		return ret;
+
+	/* Do the COW to update BLOCK_GROUP_ITEM */
 	ret = btrfs_search_slot(trans, extent_root, &cache->key, path, 0, 1);
 	if (ret < 0)
 		goto fail;
-	BUG_ON(ret);
+	if (ret > 0) {
+		ret = -ENOENT;
+		error("failed to find block group %llu in extent tree",
+			cache->key.objectid);
+		goto fail;
+	}
 
 	leaf = path->nodes[0];
 	bi = btrfs_item_ptr_offset(leaf, path->slots[0]);

Quoted 20 lines · Nikolay Borisov

Quoted 17 lines · Qu Wenruo

In write_one_cache_group() we always do COW to update BLOCK_GROUP_ITEM. However under a lot of cases, the cache->item is not changed at all.

E.g:
Transaction 123, block group [1M, 1M + 16M)

tree block 1M + 0 get freed
tree block 1M + 16K get allocated.

Transaction 123 get committed.

In this case, used space of block group [1M, 1M + 16M) doesn't changed at all, thus we don't need to do COW to update block group item.

This patch will make write_one_cache_group() to do a read-only search first, then do COW if we really need to update block group item.

Quoted 6 lines

Quoted 4 lines

This should reduce the btrfs_write_dirty_block_groups() and btrfs_run_delayed_refs() loop introduced in previous commit.

Signed-off-by Qu Wenruo <[email protected]>

I'm not sure how effective this is going to be

The effectiveness is indeed low.

For btrfs/013 test case, 64K page size, it reduces total number of delayed refs by less than 2% (5/300+)

And similar result for total number of dirty block groups.

Quoted 2 lines

and isn't this premature
optimization, have you done any measurements?

For the optimization part, I'd say it should be pretty safe. It just really skips unnecessary CoW.

The only downside to me is the extra tree search, thus killing the "optimization" part.

Quoted 43 lines · Qu Wenruo

Quoted 20 lines · Nikolay Borisov

Quoted 17 lines · Qu Wenruo

In write_one_cache_group() we always do COW to update BLOCK_GROUP_ITEM. However under a lot of cases, the cache->item is not changed at all.

E.g:
Transaction 123, block group [1M, 1M + 16M)

tree block 1M + 0 get freed
tree block 1M + 16K get allocated.

Transaction 123 get committed.

In this case, used space of block group [1M, 1M + 16M) doesn't changed at all, thus we don't need to do COW to update block group item.

This patch will make write_one_cache_group() to do a read-only search first, then do COW if we really need to update block group item.

Quoted 6 lines

Quoted 4 lines

This should reduce the btrfs_write_dirty_block_groups() and btrfs_run_delayed_refs() loop introduced in previous commit.

Signed-off-by Qu Wenruo <[email protected]>

I'm not sure how effective this is going to be

The effectiveness is indeed low.

For btrfs/013 test case, 64K page size, it reduces total number of delayed refs by less than 2% (5/300+)

And similar result for total number of dirty block groups.

Quoted 2 lines

and isn't this premature
optimization, have you done any measurements?

For the optimization part, I'd say it should be pretty safe. It just really skips unnecessary CoW.

Quoted 3 lines

The only downside to me is the extra tree search, thus killing the "optimization" part.

If that's the case then I'd rather see the 2nd patch dropped. It adds more code for no gain.

<snip>

Quoted 5 lines · Nikolay Borisov

Quoted 2 lines · Qu Wenruo

Quoted 1 line · Nikolay Borisov

On 8.07.19 г. 10:33 ч., Qu Wenruo wrote:

If that's the case then I'd rather see the 2nd patch dropped. It adds more code for no gain.

Makes sense. I'm OK to drop it.