Lowmem mode btrfs fixes exposed by complex tree

The patchset (along with "backref lost" bug fixes and test cases) can be fetched from github:
https://github.com/adam900710/btrfs-progs/tree/lowmem_fix

Despite the backref lost false alerts reported by Chris Murphy, there are still some other bugs to be fixed.

One is also exposed by Chris Murphy, where btrfs-progs backref can't handle shared block ref for metadata. Fix by 1st patch.

And 2 more bugs exposed by the test image which is originally designed for the bug fixed by 1st patch.

Last but not the least, here comes the test image. Which is an image with a lot of metadata and under a relocation. It is definitely a bomb for old lowmem check.

Qu Wenruo (4):
btrfs-progs: backref: Allow backref walk to handle direct parent ref
btrfs-progs: lowmem check: Fix function call stack overflow caused by
wrong tree reloc tree detection
btrfs-progs: lowmem check: Fix false alerts for image with shared
block ref only backref
btrfs-progs: fsck-test: Add new image with shared block ref only
metadata backref

 backref.c                                          |   3 ++
 cmds-check.c                                       |  35 +++++++++++++++++----
 .../020-extent-ref-cases/shared_block_ref_only.img | Bin 0 -> 304128 bytes
 3 files changed, 32 insertions(+), 6 deletions(-)
 create mode 100644 tests/fsck-tests/020-extent-ref-cases/shared_block_ref_only.img

2.15.0

[BUG]
Btrfs lowmem mode fails with the following ASSERT() on certain valid image.
------
backref.c:466: __add_missing_keys: Assertion ref->root_id failed, value 0
------

[REASON]
Lowmem mode uses btrfs_find_all_roots() when walking down fs trees.

However if a tree block with only shared parent backref like below, backref code from btrfs-progs doesn't handle it correct.
------

        item 72 key (604653731840 METADATA_ITEM 0) itemoff 13379 itemsize 60
                refs 4 gen 7198 flags TREE_BLOCK|FULL_BACKREF
                tree block skinny level 0
                shared block backref parent 604498477056
                shared block backref parent 604498460672
                shared block backref parent 604498444288
                shared block backref parent 604498411520

------

Such shared block ref is *direct* ref, which means we don't need to solve its key, nor its rootid.

As the objective of backref walk is to find all direct parents until it reaches tree root.
So for such direct ref, it should be pended to pref_stat->pending, other than pending it to pref_stat->pending_missing_key.

[FIX]
For direct ref, pending it to pref_state->pending directly to solve the problem.

---
 backref.c | 3 +++
 1 file changed, 3 insertions(+)

index 8615f6b8677a..27309e07a1e9 100644
@@ -206,6 +206,9 @@ static int __add_prelim_ref(struct pref_state *prefstate, u64 root_id,
 	if (key) {
 		ref->key_for_search = *key;
 		head = &prefstate->pending;
+	} else if (parent) {
+		memset(&ref->key_for_search, 0, sizeof(ref->key_for_search));
+		head = &prefstate->pending;
 	} else {
 		memset(&ref->key_for_search, 0, sizeof(ref->key_for_search));
 		head = &prefstate->pending_missing_keys;

2.15.0

For tree reloc tree root, its backref points to it self. So for such case, we should finish the lookup.

Previous end condition is to ensure it's tree reloc tree *and* needs its root bytenr to match the bytenr passed in.

However the @root passed in can be other tree, e.g. other tree reloc tree which shares the node/leaf.
This makes any check based on @root passed in invalid.

The patch removes the unreliable root objectid detection, and only use root->bytenr check.
For the possibility of invalid self-pointing backref, extent tree checker should have already handled it, so we don't need to bother in fs tree checker.

---
 cmds-check.c | 11 +++++------
 1 file changed, 5 insertions(+), 6 deletions(-)

index b9943a0d3a0f..36e4a91b7e17 100644
@@ -10251,15 +10251,10 @@ static int check_tree_block_ref(struct btrfs_root *root,
 	u32 nodesize = root->fs_info->nodesize;
 	u32 item_size;
 	u64 offset;
-	int tree_reloc_root = 0;
 	int found_ref = 0;
 	int err = 0;
 	int ret;
 
-	if (root->root_key.objectid == BTRFS_TREE_RELOC_OBJECTID &&
-	    btrfs_header_bytenr(root->node) == bytenr)
-		tree_reloc_root = 1;
-
 	btrfs_init_path(&path);
 	key.objectid = bytenr;
 	if (btrfs_fs_incompat(root->fs_info, SKINNY_METADATA))

@@ -10350,8 +10345,12 @@ static int check_tree_block_ref(struct btrfs_root *root,
 			/*
 			 * Backref of tree reloc root points to itself, no need
 			 * to check backref any more.
+			 *
+			 * This may be an error of loop backref, but extent tree
+			 * checker should have already handled it.
+			 * Here we only need to avoid infinite iteration.
 			 */
-			if (tree_reloc_root)
+			if (offset == bytenr)
 				found_ref = 1;
 			else
 			/* Check if the backref points to valid referencer */

2.15.0

[BUG]
For image with shared block ref only metadata item like:
------
item 66 key (21573632 METADATA_ITEM 0) itemoff 3971 itemsize 24
refs 66 gen 9 flags TREE_BLOCK|FULL_BACKREF
tree block skinny level 0
item 0 key (21573632 SHARED_BLOCK_REF 21676032) itemoff 3995 itemsize 0
shared block backref
item 1 key (21573632 SHARED_BLOCK_REF 21921792) itemoff 3995 itemsize 0
shared block backref
item 2 key (21573632 SHARED_BLOCK_REF 21995520) itemoff 3995 itemsize 0
shared block backref
item 3 key (21573632 SHARED_BLOCK_REF 22077440) itemoff 3995 itemsize 0
shared block backref
...
------

Lowmem mode check will report false alerts like:
------
ERROR: extent[21573632 4096] backref lost (owner: 256, level: 0)
------

[CAUSE]
In fact, the false alerts is not even from extent tree verfication, but a fs tree helper which is designed to make sure there is some tree block referring to the fs tree block.

The idea is to find inlined tree backref then keyed TREE_BLOCK_REF_KEY. However it missed SHARED_BLOCK_REF_KEY, and caused such false alert.

[FIX]
Add SHARED_BLOCK_REF_KEY to make the warning shut up.

---
 cmds-check.c | 24 ++++++++++++++++++++++++
 1 file changed, 24 insertions(+)

index 36e4a91b7e17..4805e11b752b 100644
@@ -10377,6 +10377,30 @@ static int check_tree_block_ref(struct btrfs_root *root,
 		if (!ret)
 			found_ref = 1;
 	}
+	/*
+	 * Finally check SHARED BLOCK REF, any found will be good
+	 * Here we're not doing comprehensive extent backref checking,
+	 * only need to ensure there is some extent referring to this
+	 * tree block.
+	 */
+	if (!found_ref) {
+		btrfs_release_path(&path);
+		key.objectid = bytenr;
+		key.type = BTRFS_SHARED_BLOCK_REF_KEY;
+		key.offset = (u64)-1;
+
+		ret = btrfs_search_slot(NULL, extent_root, &key, &path, 0, 0);
+		if (ret < 0) {
+			err |= BACKREF_MISSING;
+			goto out;
+		}
+		ret = btrfs_previous_extent_item(extent_root, &path, bytenr);
+		if (ret) {
+			err |= BACKREF_MISSING;
+			goto out;
+		}
+		found_ref = 1;
+	}
 	if (!found_ref)
 		err |= BACKREF_MISSING;
 out:

2.15.0

The last patch is a little big.

Even the image is dumped by -c9, it still takes near 300KiB.

Anyway, it's a binary patch, submitting to mail list doesn't help much to review.

If any one want to test or just to see the last image, please fetch it from github.

Thanks,
Qu

Branch updated with new fixes for "referencer count mismatch". Thanks Chris Murphy for his image.

If nothing goes wrong, the branch should fix all the problem Chris Murphy found.

Thanks,
Qu