Lowmem mode btrfs fixes exposed by complex tree

The patchset can be fetched from github:
https://github.com/adam900710/btrfs-progs/tree/lowmem_fix

The patchset is mostly rebased to v4.14, since there is some conflicts with lowmem repair enhancement from Su Yue.

However the lowmem repair enhancement from Su Yue caused one regression, and the original lowmem code also has some problem handling tree reloc tree.

The first 2 patches are newly introduced to address this. The rest are not touched at all (except the conflicts).

As always, the 9th patch may not reach mail list due to its size. Please use github repo to fetch that file.

Qu Wenruo (11):
btrfs-progs: lowmem check: Fix regression which screws up extent
allocator
btrfs-progs: lowmem check: Fix NULL pointer access caused by large
tree reloc tree
btrfs-progs: lowmem check: Fix inlined data extent ref lookup
btrfs-progs: lowmem check: Fix false backref lost warning for keyed
extent data ref
btrfs-progs: fsck-test: Introduce test case for false data extent
backref lost
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
btrfs-progs: lowmem check: Fix false alerts of referencer count
mismatch for snapshot
btrfs-progs: fsck-tests: Introduce test case with keyed data backref
with shared tree blocks

 backref.c                                          |   3 +
 cmds-check.c                                       |  79 +++++++++++++++------
 .../020-extent-ref-cases/keyed_data_ref_only.img   | Bin 0 -> 4096 bytes
 .../keyed_data_ref_with_shared_leaf.img            | Bin 0 -> 19456 bytes
 .../shared_block_ref_only.raw.xz                   | Bin 0 -> 217204 bytes
 5 files changed, 61 insertions(+), 21 deletions(-)
 create mode 100644 tests/fsck-tests/020-extent-ref-cases/keyed_data_ref_only.img
 create mode 100644 tests/fsck-tests/020-extent-ref-cases/keyed_data_ref_with_shared_leaf.img
 create mode 100644 tests/fsck-tests/020-extent-ref-cases/shared_block_ref_only.raw.xz

2.15.0

[BUG]
Commit 723427d7e6b7 ("btrfs-progs: check: change the way lowmem mode traverses metadata") introduces a regression which could make some fsck self test case to fail.

For fsck test case 004-no-dir-item, btrfs check --mode=lowmem --repair can cause BUG_ON() with ret = -17 (-EEXIST) when committing transaction.

The problem happens with the following backtrace:

./btrfs(+0x22045)[0x555d0dade045] ./btrfs(+0x2216f)[0x555d0dade16f] ./btrfs(+0x29df1)[0x555d0dae5df1] ./btrfs(+0x2a142)[0x555d0dae6142] ./btrfs(btrfs_alloc_free_block+0x78)[0x555d0dae6202] ./btrfs(__btrfs_cow_block+0x177)[0x555d0dad00a2] ./btrfs(btrfs_cow_block+0x116)[0x555d0dad05a8] ./btrfs(commit_tree_roots+0x91)[0x555d0db1fd4f] ./btrfs(btrfs_commit_transaction+0x18c)[0x555d0db20100] ./btrfs(btrfs_fix_super_size+0x190)[0x555d0db005a4] ./btrfs(btrfs_fix_device_and_super_size+0x177)[0x555d0db00771] ./btrfs(cmd_check+0x1757)[0x555d0db4f6ab] ./btrfs(main+0x138)[0x555d0dace5dd] /usr/lib/libc.so.6(__libc_start_main+0xea)[0x7fa5e4613f6a] ./btrfs(_start+0x2a)[0x555d0dacddda]

The bug is triggered by that, extent allocator considers range [29360128, 29376512) is free and allocate it.
However when inserting EXTENT_ITEM, btrfs finds there is already one tree block (fs tree root), returning -EEXIST and causing later BUG_ON().

[CAUSE]
The cause is in repair mode, lowmem check always pins all metadata blocks.
However pinned metadata blocks will be unpin when transaction commits, and will be marked as *FREE* space.

So later extent allocator will consider such range free and allocate them wrongly.

[FIX]
Don't pin metadata blocks without valid reason or preparation (like discard all free space cache to re-calculate free space on next write).

---
 cmds-check.c | 10 ----------
 1 file changed, 10 deletions(-)

index a93ac2c88a38..644ee084cb8e 100644
@@ -6623,8 +6623,6 @@ out:
 	return ret;
 }
 
-static int pin_metadata_blocks(struct btrfs_fs_info *fs_info);
-
 /*
  * Iterate all items in the tree and call check_inode_item() to check.
  *

@@ -13306,8 +13304,6 @@ out:
 	return err;
 }
 
-static int pin_metadata_blocks(struct btrfs_fs_info *fs_info);
-
 /*
  * Low memory usage version check_chunks_and_extents.
  */

@@ -13326,12 +13322,6 @@ static int check_chunks_and_extents_v2(struct btrfs_fs_info *fs_info)
 	root = fs_info->fs_root;
 
 	if (repair) {
-		/* pin every tree block to avoid extent overwrite */
-		ret = pin_metadata_blocks(fs_info);
-		if (ret) {
-			error("failed to pin metadata blocks");
-			return ret;
-		}
 		trans = btrfs_start_transaction(fs_info->extent_root, 1);
 		if (IS_ERR(trans)) {
 			error("failed to start transaction before check");

2.15.0

[BUG]
v4.14 btrfs-progs can't pass new self test image with large tree reloc trees.
It will fail with later "shared_block_ref_only.raw.xz" test image with NULL pointer access.

[CAUSE]
For image with higher (level >= 2) tree reloc tree, for function need_check() its ulist will be empty as tree reloc tree won't be accounted in btrfs_find_all_roots().
Then accessing ulist->roots with rb_first() will return NULL pointer.

[FIX]
For need_check() function, if @roots is empty, meaning it's a tree reloc tree, always check them.
Although this can be slow, but at least it's safe that we won't skip any possible wrong tree block.

---
 cmds-check.c | 7 ++++++-
 1 file changed, 6 insertions(+), 1 deletion(-)

index 644ee084cb8e..03ff89a4221c 100644
@@ -2149,7 +2149,12 @@ static int need_check(struct btrfs_root *root, struct ulist *roots)
 	struct rb_node *node;
 	struct ulist_node *u;
 
-	if (roots->nnodes == 1)
+	/*
+	 * @roots can be empty if it belongs to tree reloc tree
+	 * In that case, we should always check the leaf, as we can't use
+	 * the tree owner to ensure some other root will check it.
+	 */
+	if (roots->nnodes == 1 || roots->nnodes == 0)
 		return 1;
 
 	node = rb_first(&roots->root);

2.15.0

When lowmem fsck tries to find backref of a specified file extent, it searches inlined data ref first.

However, extent data ref contains both owner root objectid, inode number and calculated offset (file offset - extent offset).

The code only checks owner root objectid, not checking inode number nor calculated offset.

This makes lowmem mode fails to detect any backref mismatch if there is a inlined data ref with the same owner objectid.

Fix it by also checking extent data ref's objectid and offset.

---
 cmds-check.c | 18 +++++++++++++++---
 1 file changed, 15 insertions(+), 3 deletions(-)

index 03ff89a4221c..9f9eb504ae8e 100644
@@ -12005,11 +12005,11 @@ static int check_extent_data_item(struct btrfs_root *root,
 	u64 disk_num_bytes;
 	u64 extent_num_bytes;
 	u64 extent_flags;
+	u64 offset;
 	u32 item_size;
 	unsigned long end;
 	unsigned long ptr;
 	int type;
-	u64 ref_root;
 	int found_dbackref = 0;
 	int slot = pathp->slots[0];
 	int err = 0;

@@ -12027,6 +12027,7 @@ static int check_extent_data_item(struct btrfs_root *root,
 	disk_bytenr = btrfs_file_extent_disk_bytenr(eb, fi);
 	disk_num_bytes = btrfs_file_extent_disk_num_bytes(eb, fi);
 	extent_num_bytes = btrfs_file_extent_num_bytes(eb, fi);
+	offset = btrfs_file_extent_offset(eb, fi);
 
 	/* Check unaligned disk_num_bytes and num_bytes */
 	if (!IS_ALIGNED(disk_num_bytes, root->fs_info->sectorsize)) {

@@ -12081,6 +12082,11 @@ static int check_extent_data_item(struct btrfs_root *root,
 	strict = should_check_extent_strictly(root, nrefs, -1);
 
 	while (ptr < end) {
+		u64 ref_root;
+		u64 ref_objectid;
+		u64 ref_offset;
+		bool match = false;
+
 		iref = (struct btrfs_extent_inline_ref *)ptr;
 		type = btrfs_extent_inline_ref_type(leaf, iref);
 		dref = (struct btrfs_extent_data_ref *)(&iref->offset);

@@ -12092,9 +12098,15 @@ static int check_extent_data_item(struct btrfs_root *root,
 		}
 		if (type == BTRFS_EXTENT_DATA_REF_KEY) {
 			ref_root = btrfs_extent_data_ref_root(leaf, dref);
-			if (ref_root == root->objectid)
+			ref_objectid = btrfs_extent_data_ref_objectid(leaf, dref);
+			ref_offset = btrfs_extent_data_ref_offset(leaf, dref);
+
+			if (ref_objectid == fi_key.objectid &&
+			    ref_offset == fi_key.offset - offset)
+				match = true;
+			if (ref_root == root->objectid && match)
 				found_dbackref = 1;
-			else if (!strict && owner == ref_root)
+			else if (!strict && owner == ref_root && match)
 				found_dbackref = 1;
 		} else if (type == BTRFS_SHARED_DATA_REF_KEY) {
 			found_dbackref = !check_tree_block_ref(root, NULL,

2.15.0

For keyed extent ref, its offset is calculated offset (file offset - file extent offset), just like inlined extent data ref.

However the code is using file offset to hash extent data ref offset, causing false backref lost warning like:
------
ERROR: data extent[16913485824 7577600] backref lost
------

---
 cmds-check.c | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

index 9f9eb504ae8e..452e715bf245 100644
@@ -12126,7 +12126,7 @@ static int check_extent_data_item(struct btrfs_root *root,
 		dbref_key.objectid = btrfs_file_extent_disk_bytenr(eb, fi);
 		dbref_key.type = BTRFS_EXTENT_DATA_REF_KEY;
 		dbref_key.offset = hash_extent_data_ref(root->objectid,
-				fi_key.objectid, fi_key.offset);
+				fi_key.objectid, fi_key.offset - offset);
 
 		ret = btrfs_search_slot(NULL, root->fs_info->extent_root,
 					&dbref_key, &path, 0, 0);

2.15.0

Introduce a new test image, which has an extent item with no inlined extent data ref, but all keyed extent data ref.

Only in this case we can trigger fase data extent backref lost bug in lowmem mode.

---
 .../020-extent-ref-cases/keyed_data_ref_only.img         | Bin 0 -> 4096 bytes
 1 file changed, 0 insertions(+), 0 deletions(-)
 create mode 100644 tests/fsck-tests/020-extent-ref-cases/keyed_data_ref_only.img

new file mode 100644
index 0000000000000000000000000000000000000000..668589f46d330cb5d6ff10b108e62585875548ca
GIT binary patch

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 | 10 +++++-----
 1 file changed, 5 insertions(+), 5 deletions(-)

index 452e715bf245..7eb08b6cb962 100644
@@ -11700,16 +11700,12 @@ 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;
 	int strict = 1;
 	int parent = 0;
 
-	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))

@@ -11817,8 +11813,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 {
 				/*

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 7eb08b6cb962..791fab6b3e6a 100644
@@ -11850,6 +11850,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

Btrfs lowmem check reports such false alerts:
------
ERROR: extent[366498091008, 134217728] referencer count mismatch (root: 827, owner: 73782, offset: 134217728) wanted: 4, have: 26
ERROR: extent[366498091008, 134217728] referencer count mismatch (root: 818, owner: 73782, offset: 134217728) wanted: 4, have: 26
ERROR: extent[366498091008, 134217728] referencer count mismatch (root: 870, owner: 73782, offset: 134217728) wanted: 4, have: 26
------

While in extent tree, the extent has:
------

        item 81 key (366498091008 EXTENT_ITEM 134217728) itemoff 9008 itemsize 169
                refs 39 gen 224 flags DATA
                extent data backref root 827 objectid 73782 offset 134217728 count 4
                extent data backref root 818 objectid 73782 offset 134217728 count 4
                extent data backref root 259 objectid 73482 offset 134217728 count 1
                extent data backref root 644 objectid 73782 offset 134217728 count 26
                extent data backref root 870 objectid 73782 offset 134217728 count 4

------

And in root 827, there is one leaf with 4 references to that extent which is owned by 827:
------
leaf 714964992 items 68 free space 10019 generation 641 owner 827 leaf 714964992 flags 0x1(WRITTEN) backref revision 1
......

        item 64 key (73782 EXTENT_DATA 134217728) itemoff 11878 itemsize 53
                generation 224 type 1 (regular)
                extent data disk byte 366498091008 nr 134217728
                extent data offset 0 nr 6410240 ram 134217728
                extent compression 0 (none)
        item 65 key (73782 EXTENT_DATA 140627968) itemoff 11825 itemsize 53
                generation 224 type 1 (regular)
                extent data disk byte 366498091008 nr 134217728
                extent data offset 6410240 nr 5120000 ram 134217728
                extent compression 0 (none)
        item 66 key (73782 EXTENT_DATA 145747968) itemoff 11772 itemsize 53
                generation 224 type 1 (regular)
                extent data disk byte 366498091008 nr 134217728
                extent data offset 11530240 nr 7675904 ram 134217728
                extent compression 0 (none)
        item 67 key (73782 EXTENT_DATA 153423872) itemoff 11719 itemsize 53
                generation 224 type 1 (regular)
                extent data disk byte 366498091008 nr 134217728
                extent data offset 19206144 nr 6397952 ram 134217728
                extent compression 0 (none)

------

And starts from next leaf, there are 22 references to the data extent:
------
leaf 894861312 items 208 free space 59 generation 261 owner 644 leaf 894861312 flags 0x1(WRITTEN) backref revision 1

        item 0 key (73782 EXTENT_DATA 159821824) itemoff 16230 itemsize 53
                generation 224 type 1 (regular)
                extent data disk byte 366498091008 nr 134217728
                extent data offset 25604096 nr 8192 ram 134217728
                extent compression 0 (none)
        item 1 key (73782 EXTENT_DATA 159830016) itemoff 16177 itemsize 53
                generation 224 type 1 (regular)
                extent data disk byte 366498091008 nr 134217728
                extent data offset 25612288 nr 7675904 ram 134217728
                extent compression 0 (none)

......
------

However the next leaf is owned by other subvolume, normally owned by (part of) the snapshot source.

Fix it by also checking the leaf's owner before increasing the reference counter.

---
 cmds-check.c | 8 +++++++-
 1 file changed, 7 insertions(+), 1 deletion(-)

index 791fab6b3e6a..e746ee7b281d 100644
@@ -12518,11 +12518,17 @@ static int check_extent_data_backref(struct btrfs_fs_info *fs_info,
 		 * Except normal disk bytenr and disk num bytes, we still
 		 * need to do extra check on dbackref offset as
 		 * dbackref offset = file_offset - file_extent_offset
+		 *
+		 * Also, we must check the leaf owner.
+		 * In case of shared tree blocks (snapshots) we can inherit
+		 * leaves from source snapshot.
+		 * In that case, reference from source snapshot should not
+		 * count.
 		 */
 		if (btrfs_file_extent_disk_bytenr(leaf, fi) == bytenr &&
 		    btrfs_file_extent_disk_num_bytes(leaf, fi) == len &&
 		    (u64)(key.offset - btrfs_file_extent_offset(leaf, fi)) ==
-		    offset)
+		    offset && btrfs_header_owner(leaf) == root_id)
 			found_count++;
 
 next:

2.15.0

For snapshot shared tree blocks with source subvolume, the keyed backref counter only counts the exclusive owned references.

In the following case, 258 is a snapshot of 257, which inherits all the reference to this data extent.
------
item 4 key (12582912 EXTENT_ITEM 524288) itemoff 3741 itemsize 140
refs 179 gen 9 flags DATA
extent data backref root 257 objectid 258 offset 0 count 49 extent data backref root 257 objectid 257 offset 0 count 1 extent data backref root 256 objectid 258 offset 0 count 128 extent data backref root 256 objectid 257 offset 0 count 1
------

However lowmem mode used to iterate the whole inode to find all reference, and doesn't care if the reference is already counted by the shared tree block.

And the test case to check it.

---
 .../keyed_data_ref_with_shared_leaf.img                 | Bin 0 -> 19456 bytes
 1 file changed, 0 insertions(+), 0 deletions(-)
 create mode 100644 tests/fsck-tests/020-extent-ref-cases/keyed_data_ref_with_shared_leaf.img

new file mode 100644
index 0000000000000000000000000000000000000000..2ce5068f01c693e577de8b9a536fdeb360029e5f
GIT binary patch

2.15.0

Thanks for the fixes, patchset added to devel. I've also enabled the lowmem mode in the CI build tests.