[PATCH 0/4] Lowmem mode btrfs fixes exposed by complex tree

[PATCH 0/4] Lowmem mode btrfs fixes exposed by complex tree

[Qu Wenruo]

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

[PATCH 1/4] btrfs-progs: backref: Allow backref walk to handle direct parent ref

[Qu Wenruo]

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

Reported-by: Chris Murphy <chris@colorremedies.com>
Signed-off-by: Qu Wenruo <wqu@suse.com>
---
 backref.c | 3 +++
 1 file changed, 3 insertions(+)

diff --git a/backref.c b/backref.c
index 8615f6b8677a..27309e07a1e9 100644
--- a/backref.c
+++ b/backref.c
@@ -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

[PATCH 2/4] btrfs-progs: lowmem check: Fix function call stack overflow caused by wrong tree reloc tree detection

[Qu Wenruo]

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.

Fixes: 54c8f9152fd9 ("btrfs-progs: check: Fix lowmem mode stack overflow caused by fsck/023")
Signed-off-by: Qu Wenruo <wqu@suse.com>
---
 cmds-check.c | 11 +++++------
 1 file changed, 5 insertions(+), 6 deletions(-)

diff --git a/cmds-check.c b/cmds-check.c
index b9943a0d3a0f..36e4a91b7e17 100644
--- a/cmds-check.c
+++ b/cmds-check.c
@@ -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

[PATCH 3/4] btrfs-progs: lowmem check: Fix false alerts for image with shared block ref only backref

[Qu Wenruo]

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

Signed-off-by: Qu Wenruo <wqu@suse.com>
---
 cmds-check.c | 24 ++++++++++++++++++++++++
 1 file changed, 24 insertions(+)

diff --git a/cmds-check.c b/cmds-check.c
index 36e4a91b7e17..4805e11b752b 100644
--- a/cmds-check.c
+++ b/cmds-check.c
@@ -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

Re: [PATCH 0/4] Lowmem mode btrfs fixes exposed by complex tree

[Qu Wenruo]

[-- Attachment #1.1: Type: text/plain, Size: 1825 bytes --]



On 2017年11月13日 15:34, Qu Wenruo wrote:
> 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

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

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


[-- Attachment #2: OpenPGP digital signature --]
[-- Type: application/pgp-signature, Size: 520 bytes --]

Re: [PATCH 0/4] Lowmem mode btrfs fixes exposed by complex tree

[Qu Wenruo]

[-- Attachment #1.1: Type: text/plain, Size: 1737 bytes --]



On 2017年11月13日 15:34, Qu Wenruo wrote:
> 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

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


[-- Attachment #2: OpenPGP digital signature --]
[-- Type: application/pgp-signature, Size: 520 bytes --]