Skip to contentSkip to conversation

Fixup and optimization for write time tree checker

PATCH In review Qu Wenruo 4 participants 11 messages Apr 4, 2019 – Apr 12, 2019 Btrfs file system

lore
Share & tools
lore

Qu Wenruo

author
#0 lore raw

cover Fixup and optimization for write time tree checker

This patchset can be fetched from github:
https://github.com/adam900710/linux/tree/tree_checker_testing

Which is based on misc-next, with the following commit as HEAD:
commit 56d46f96de92ec69963acb7b1d9aed83d2a56a7b (david/misc-next-with-write-checks, david/misc-next)

Author: Nikolay Borisov <[email protected]>
Date:   Wed Mar 27 14:24:18 2019 +0200

btrfs: Switch btrfs_trim_free_extents to find_first_clear_extent_bit

These two patches changes the behavior of write time tree-checker, where the initial patches didn't check the content of the leaf, leaving memory bit flipping possible to sneak in.

This patchset also introduces a new optimization, where original empty leaf owner check can be pretty expensive and cause false alerts for write time tree checker.
With this new optimization, write time tree checker can reuse the existing btrfs_check_leaf_full().

Qu Wenruo (2):
btrfs: tree-checker: Remove comprehensive root owner check
btrfs: Do mandatory tree block check before submitting bio

 fs/btrfs/disk-io.c      | 13 +++++++++++++
 fs/btrfs/tree-checker.c | 24 ------------------------
 2 files changed, 13 insertions(+), 24 deletions(-)
Signature · 1 line
2.21.0
author
#1 lore raw

PATCH 1/2 btrfs: tree-checker: Remove comprehensive root owner check

Commit 1ba98d086fe3 ("Btrfs: detect corruption when non-root leaf has zero item") introduced comprehensive root owner checker.

However it's pretty expensive tree search to locate the owner root, especially when it get reused by mandatory read and write time tree-checker.

This patch will remove that check, and completely rely on owner based empty leaf check, which is much faster and still works fine for most case.

And since we skip the old root owner check, now write time tree check can be merged with btrfs_check_leaf_full().

---
 fs/btrfs/tree-checker.c | 24 ------------------------
 1 file changed, 24 deletions(-)
fs/btrfs/tree-checker.c +0 -24
index d2c3c1f8870d..e325d4df5c23 100644
@@ -838,7 +838,6 @@ static int check_leaf(struct extent_buffer *leaf, bool check_item_data)
 	 */
 	if (nritems == 0 && !btrfs_header_flag(leaf, BTRFS_HEADER_FLAG_RELOC)) {
 		u64 owner = btrfs_header_owner(leaf);
-		struct btrfs_root *check_root;
 
 		/* These trees must never be empty */
 		if (owner == BTRFS_ROOT_TREE_OBJECTID ||
@@ -852,29 +851,6 @@ static int check_leaf(struct extent_buffer *leaf, bool check_item_data)
 				    owner);
 			return -EUCLEAN;
 		}
-		key.objectid = owner;
-		key.type = BTRFS_ROOT_ITEM_KEY;
-		key.offset = (u64)-1;
-
-		check_root = btrfs_get_fs_root(fs_info, &key, false);
-		/*
-		 * The only reason we also check NULL here is that during
-		 * open_ctree() some roots has not yet been set up.
-		 */
-		if (!IS_ERR_OR_NULL(check_root)) {
-			struct extent_buffer *eb;
-
-			eb = btrfs_root_node(check_root);
-			/* if leaf is the root, then it's fine */
-			if (leaf != eb) {
-				generic_err(leaf, 0,
-		"invalid nritems, have %u should not be 0 for non-root leaf",
-					nritems);
-				free_extent_buffer(eb);
-				return -EUCLEAN;
-			}
-			free_extent_buffer(eb);
-		}
 		return 0;
 	}
 
Signature · 1 line
2.21.0
#2 lore raw

Re: [PATCH 1/2] btrfs: tree-checker: Remove comprehensive root owner check

Quoted 7 lines · Qu Wenruo

Commit 1ba98d086fe3 ("Btrfs: detect corruption when non-root leaf has zero item") introduced comprehensive root owner checker.

However it's pretty expensive tree search to locate the owner root, especially when it get reused by mandatory read and write time tree-checker.

Quoted 8 lines

This patch will remove that check, and completely rely on owner based empty leaf check, which is much faster and still works fine for most case.

And since we skip the old root owner check, now write time tree check can be merged with btrfs_check_leaf_full().

This patch was sent yesterday, now it's sent again with no material changes whatsoever? What's the point?

Quoted 47 lines
---
 fs/btrfs/tree-checker.c | 24 ------------------------
 1 file changed, 24 deletions(-)
fs/btrfs/tree-checker.c +0 -24
index d2c3c1f8870d..e325d4df5c23 100644
@@ -838,7 +838,6 @@ static int check_leaf(struct extent_buffer *leaf, bool check_item_data)
 	 */
 	if (nritems == 0 && !btrfs_header_flag(leaf, BTRFS_HEADER_FLAG_RELOC)) {
 		u64 owner = btrfs_header_owner(leaf);
-		struct btrfs_root *check_root;
 
 		/* These trees must never be empty */
 		if (owner == BTRFS_ROOT_TREE_OBJECTID ||
@@ -852,29 +851,6 @@ static int check_leaf(struct extent_buffer *leaf, bool check_item_data)
 				    owner);
 			return -EUCLEAN;
 		}
-		key.objectid = owner;
-		key.type = BTRFS_ROOT_ITEM_KEY;
-		key.offset = (u64)-1;
-
-		check_root = btrfs_get_fs_root(fs_info, &key, false);
-		/*
-		 * The only reason we also check NULL here is that during
-		 * open_ctree() some roots has not yet been set up.
-		 */
-		if (!IS_ERR_OR_NULL(check_root)) {
-			struct extent_buffer *eb;
-
-			eb = btrfs_root_node(check_root);
-			/* if leaf is the root, then it's fine */
-			if (leaf != eb) {
-				generic_err(leaf, 0,
-		"invalid nritems, have %u should not be 0 for non-root leaf",
-					nritems);
-				free_extent_buffer(eb);
-				return -EUCLEAN;
-			}
-			free_extent_buffer(eb);
-		}
 		return 0;
 	}
 
#3 lore raw

Re: [PATCH 1/2] btrfs: tree-checker: Remove comprehensive root owner check

Quoted 14 lines · Nikolay Borisov
Quoted 11 lines · Qu Wenruo

Commit 1ba98d086fe3 ("Btrfs: detect corruption when non-root leaf has zero item") introduced comprehensive root owner checker.

However it's pretty expensive tree search to locate the owner root, especially when it get reused by mandatory read and write time tree-checker.

This patch will remove that check, and completely rely on owner based empty leaf check, which is much faster and still works fine for most case.

Quoted 7 lines
Quoted 4 lines

And since we skip the old root owner check, now write time tree check can be merged with btrfs_check_leaf_full().

This patch was sent yesterday, now it's sent again with no material changes whatsoever? What's the point?

This is the version to be applied on misc-next.

Thanks,
Qu

Quoted 48 lines
Quoted 48 lines
---
 fs/btrfs/tree-checker.c | 24 ------------------------
 1 file changed, 24 deletions(-)
fs/btrfs/tree-checker.c +0 -24
index d2c3c1f8870d..e325d4df5c23 100644
@@ -838,7 +838,6 @@ static int check_leaf(struct extent_buffer *leaf, bool check_item_data)
 	 */
 	if (nritems == 0 && !btrfs_header_flag(leaf, BTRFS_HEADER_FLAG_RELOC)) {
 		u64 owner = btrfs_header_owner(leaf);
-		struct btrfs_root *check_root;
 
 		/* These trees must never be empty */
 		if (owner == BTRFS_ROOT_TREE_OBJECTID ||
@@ -852,29 +851,6 @@ static int check_leaf(struct extent_buffer *leaf, bool check_item_data)
 				    owner);
 			return -EUCLEAN;
 		}
-		key.objectid = owner;
-		key.type = BTRFS_ROOT_ITEM_KEY;
-		key.offset = (u64)-1;
-
-		check_root = btrfs_get_fs_root(fs_info, &key, false);
-		/*
-		 * The only reason we also check NULL here is that during
-		 * open_ctree() some roots has not yet been set up.
-		 */
-		if (!IS_ERR_OR_NULL(check_root)) {
-			struct extent_buffer *eb;
-
-			eb = btrfs_root_node(check_root);
-			/* if leaf is the root, then it's fine */
-			if (leaf != eb) {
-				generic_err(leaf, 0,
-		"invalid nritems, have %u should not be 0 for non-root leaf",
-					nritems);
-				free_extent_buffer(eb);
-				return -EUCLEAN;
-			}
-			free_extent_buffer(eb);
-		}
 		return 0;
 	}
 
#4 lore raw

Re: [PATCH 1/2] btrfs: tree-checker: Remove comprehensive root owner check

In reply to Nikolay Borisov
Quoted 14 lines · Nikolay Borisov
Quoted 11 lines · Qu Wenruo

Commit 1ba98d086fe3 ("Btrfs: detect corruption when non-root leaf has zero item") introduced comprehensive root owner checker.

However it's pretty expensive tree search to locate the owner root, especially when it get reused by mandatory read and write time tree-checker.

This patch will remove that check, and completely rely on owner based empty leaf check, which is much faster and still works fine for most case.

Quoted 7 lines
Quoted 4 lines

And since we skip the old root owner check, now write time tree check can be merged with btrfs_check_leaf_full().

This patch was sent yesterday, now it's sent again with no material changes whatsoever? What's the point?

The core change is the same, but there are removed hunks compared to v1. We've discussed that yesterday and Qu did it right.

author
#5 lore raw

PATCH 2/2 btrfs: Do mandatory tree block check before submitting bio

In reply to Qu Wenruo

There are at least 2 reports about a memory bit flip sneaking into on-disk data.

Currently we only have a relaxed check triggered at btrfs_mark_buffer_dirty() time, as it's not mandatory and only for CONFIG_BTRFS_FS_CHECK_INTEGRITY enabled build, it doesn't help users to detect such problem.

This patch will address the hole by triggering comprehensive check on tree blocks before writing it back to disk.

The design points are:

- Timing of the check: Tree block write hook
This timing is chosen to reduce the overhead.
The comprehensive check should be as expensive as a checksum calculation.
Doing full check at btrfs_mark_buffer_dirty() is too expensive for end user.

- Loose empty leaf check
Originally for an empty leaf, tree-checker will report error if it's not a tree root.

The problem for such check at write time is:
* False alert for tree root created in current transaction In that case, the commit root still needs to be written to disk. And since current root can differ from commit root, then it will cause false alert.
This happens for log tree.

* False alert for relocated tree block
Relocated tree block can be written to disk due to memory pressure, in that case an empty csum tree root can be written to disk and cause false alert, since csum root node hasn't been updated.

Previous patch of removing comprehensive empty leaf owner check has paved the way for this patch.

The example error output will be something like:

BTRFS critical (device dm-3): corrupt leaf: root=2 block=1350630375424 slot=68, bad key order, prev (10510212874240 169 0) current (1714119868416 169 0) BTRFS error (device dm-3): block=1350630375424 write time tree block corruption detected
BTRFS: error (device dm-3) in btrfs_commit_transaction:2220: errno=-5 IO failure (Error while writing out transaction)
BTRFS info (device dm-3): forced readonly
BTRFS warning (device dm-3): Skipping commit of aborted transaction.
BTRFS: error (device dm-3) in cleanup_transaction:1839: errno=-5 IO failure
BTRFS info (device dm-3): delayed_refs has NO entry

---
 fs/btrfs/disk-io.c | 13 +++++++++++++
 1 file changed, 13 insertions(+)
fs/btrfs/disk-io.c +13 -0
index 0b2b75a7efbd..c2c0640aea55 100644
@@ -514,6 +514,7 @@ static int csum_dirty_buffer(struct btrfs_fs_info *fs_info, struct page *page)
 	u8 result[BTRFS_CSUM_SIZE];
 	u16 csum_size = btrfs_super_csum_size(fs_info->super_copy);
 	struct extent_buffer *eb;
+	int err;
 
 	eb = (struct extent_buffer *)page->private;
 	if (page != eb->pages[0])
@@ -535,7 +536,19 @@ static int csum_dirty_buffer(struct btrfs_fs_info *fs_info, struct page *page)
 	if (csum_tree_block(eb, result))
 		return -EINVAL;
 
+	if (btrfs_header_level(eb))
+		err = btrfs_check_node(fs_info, eb);
+	else
+		err = btrfs_check_leaf_full(fs_info, eb);
+
+	if (err < 0) {
+		btrfs_err(fs_info,
+		"block=%llu write time tree block corruption detected",
+			  eb->start);
+		return err;
+	}
 	write_extent_buffer(eb, result, 0, csum_size);
+
 	return 0;
 }
 
Signature · 1 line
2.21.0
#6 lore raw

Re: [PATCH 2/2] btrfs: Do mandatory tree block check before submitting bio

fs/btrfs/disk-io.c static int csum_dirty_buffer(struct btrfs_fs_info *fs_info, struct page *page) · line 517

Quoted 5 lines · Qu Wenruo
fs/btrfs/disk-io.c +1 -0
@@ -514,6 +514,7 @@ static int csum_dirty_buffer(struct btrfs_fs_info *fs_info, struct page *page)
 	u8 result[BTRFS_CSUM_SIZE];
 	u16 csum_size = btrfs_super_csum_size(fs_info->super_copy);
 	struct extent_buffer *eb;
+	int err;

Please next time user 'ret' for newly added return values, I've fixed that in the commit.

#7 lore raw
In reply to Qu Wenruo
Quoted 14 lines · Qu Wenruo

This patchset can be fetched from github:
https://github.com/adam900710/linux/tree/tree_checker_testing

Which is based on misc-next, with the following commit as HEAD:
commit 56d46f96de92ec69963acb7b1d9aed83d2a56a7b (david/misc-next-with-write-checks, david/misc-next)

Author: Nikolay Borisov <[email protected]>
Date:   Wed Mar 27 14:24:18 2019 +0200

btrfs: Switch btrfs_trim_free_extents to find_first_clear_extent_bit

These two patches changes the behavior of write time tree-checker, where the initial patches didn't check the content of the leaf, leaving memory bit flipping possible to sneak in.

Quoted 5 lines

This patchset also introduces a new optimization, where original empty leaf owner check can be pretty expensive and cause false alerts for write time tree checker.
With this new optimization, write time tree checker can reuse the existing btrfs_check_leaf_full().

This on top of misc-next throws 6 'write time' errors:

btrfs/101 [14:00:24][ 3963.736352] run fstests btrfs/101 at 2019-04-05 14:00:24

[ 3970.417649] BTRFS error (device vdc): block=2446344192 write time tree block corruption detected

btrfs/151 [14:06:52][ 4351.133395] run fstests btrfs/151 at 2019-04-05 14:06:52

[ 4351.659771] BTRFS error (device vdb): block=570572800 write time tree block corruption detected

btrfs/164 [14:07:19][ 4378.349990] run fstests btrfs/164 at 2019-04-05 14:07:19

[ 4380.645918] BTRFS error (device vdb): block=2479882240 write time tree block corruption detected

btrfs/176 [14:07:39][ 4398.493736] run fstests btrfs/176 at 2019-04-05 14:07:39

[ 4399.186203] BTRFS error (device vdb): block=22036480 write time tree block corruption detected
[ 4399.302700] BTRFS error (device vdb): block=1372585984 write time tree block corruption detected

btrfs/184 [14:10:13][ 4552.496289] run fstests btrfs/184 at 2019-04-05 14:10:13

[ 4553.292780] BTRFS error (device vdb): block=4602216448 write time tree block corruption detected

Have you seen the errors during your testing?

#8 lore raw
Quoted 21 lines · David Sterba
Quoted 14 lines · Qu Wenruo

This patchset can be fetched from github:
https://github.com/adam900710/linux/tree/tree_checker_testing

Which is based on misc-next, with the following commit as HEAD:
commit 56d46f96de92ec69963acb7b1d9aed83d2a56a7b (david/misc-next-with-write-checks, david/misc-next)

Author: Nikolay Borisov <[email protected]>
Date:   Wed Mar 27 14:24:18 2019 +0200

btrfs: Switch btrfs_trim_free_extents to find_first_clear_extent_bit

These two patches changes the behavior of write time tree-checker, where the initial patches didn't check the content of the leaf, leaving memory bit flipping possible to sneak in.

Quoted 5 lines

This patchset also introduces a new optimization, where original empty leaf owner check can be pretty expensive and cause false alerts for write time tree checker.
With this new optimization, write time tree checker can reuse the existing btrfs_check_leaf_full().

Quoted 4 lines

This on top of misc-next throws 6 'write time' errors:

btrfs/101 [14:00:24][ 3963.736352] run fstests btrfs/101 at 2019-04-05 14:00:24

[ 3970.417649] BTRFS error (device vdc): block=2446344192 write time tree block corruption detected

In my case, these tests just pass, so I haven't checked the dmesg.

But indeed I can reproduce the same dmesg line.

Before removing the device, btrfs will use btrfs_shrink_device(new_size = 0) to remove all data from that device.

And that will cause on-disk total_bytes to be 0, triggering the bug.

So indeed the behavior is different between read and write time.

I'll check how to do it correctly.

Thanks,
Qu

Quoted 16 lines

btrfs/151 [14:06:52][ 4351.133395] run fstests btrfs/151 at 2019-04-05 14:06:52

[ 4351.659771] BTRFS error (device vdb): block=570572800 write time tree block corruption detected

btrfs/164 [14:07:19][ 4378.349990] run fstests btrfs/164 at 2019-04-05 14:07:19

[ 4380.645918] BTRFS error (device vdb): block=2479882240 write time tree block corruption detected

btrfs/176 [14:07:39][ 4398.493736] run fstests btrfs/176 at 2019-04-05 14:07:39

[ 4399.186203] BTRFS error (device vdb): block=22036480 write time tree block corruption detected
[ 4399.302700] BTRFS error (device vdb): block=1372585984 write time tree block corruption detected

btrfs/184 [14:10:13][ 4552.496289] run fstests btrfs/184 at 2019-04-05 14:10:13

[ 4553.292780] BTRFS error (device vdb): block=4602216448 write time tree block corruption detected

Have you seen the errors during your testing?

#9 lore raw
Quoted 24 lines · Qu Wenruo
Quoted 21 lines · David Sterba
Quoted 19 lines · Qu Wenruo

This patchset can be fetched from github:
https://github.com/adam900710/linux/tree/tree_checker_testing

Which is based on misc-next, with the following commit as HEAD:
commit 56d46f96de92ec69963acb7b1d9aed83d2a56a7b (david/misc-next-with-write-checks, david/misc-next)

Author: Nikolay Borisov <[email protected]>
Date:   Wed Mar 27 14:24:18 2019 +0200

btrfs: Switch btrfs_trim_free_extents to find_first_clear_extent_bit

These two patches changes the behavior of write time tree-checker, where the initial patches didn't check the content of the leaf, leaving memory bit flipping possible to sneak in.

This patchset also introduces a new optimization, where original empty leaf owner check can be pretty expensive and cause false alerts for write time tree checker.
With this new optimization, write time tree checker can reuse the existing btrfs_check_leaf_full().

Quoted 6 lines
Quoted 4 lines

This on top of misc-next throws 6 'write time' errors:

btrfs/101 [14:00:24][ 3963.736352] run fstests btrfs/101 at 2019-04-05 14:00:24

[ 3970.417649] BTRFS error (device vdc): block=2446344192 write time tree block corruption detected

In my case, these tests just pass, so I haven't checked the dmesg.

Oh, those tests passes because of a bug in mainline.

6dc4f100c175 ("block: allow bio_for_each_segment_all() to iterate over multi-page bvec") prevents us from breaking bio_for_each_segment_all() loop, thus not triggering transaction abort.

A nice finding digging into the report.

Thanks,
Qu

Quoted 32 lines

But indeed I can reproduce the same dmesg line.

Before removing the device, btrfs will use btrfs_shrink_device(new_size = 0) to remove all data from that device.

And that will cause on-disk total_bytes to be 0, triggering the bug.

So indeed the behavior is different between read and write time.

I'll check how to do it correctly.

Thanks,
Qu

Quoted 16 lines

btrfs/151 [14:06:52][ 4351.133395] run fstests btrfs/151 at 2019-04-05 14:06:52

[ 4351.659771] BTRFS error (device vdb): block=570572800 write time tree block corruption detected

btrfs/164 [14:07:19][ 4378.349990] run fstests btrfs/164 at 2019-04-05 14:07:19

[ 4380.645918] BTRFS error (device vdb): block=2479882240 write time tree block corruption detected

btrfs/176 [14:07:39][ 4398.493736] run fstests btrfs/176 at 2019-04-05 14:07:39

[ 4399.186203] BTRFS error (device vdb): block=22036480 write time tree block corruption detected
[ 4399.302700] BTRFS error (device vdb): block=1372585984 write time tree block corruption detected

btrfs/184 [14:10:13][ 4552.496289] run fstests btrfs/184 at 2019-04-05 14:10:13

[ 4553.292780] BTRFS error (device vdb): block=4602216448 write time tree block corruption detected

Have you seen the errors during your testing?

#10 lore raw
Quoted 7 lines · Qu Wenruo
Quoted 7 lines
Quoted 7 lines
Quoted 6 lines

This patchset also introduces a new optimization, where original empty leaf owner check can be pretty expensive and cause false alerts for write time tree checker.
With this new optimization, write time tree checker can reuse the existing btrfs_check_leaf_full().

Quoted 6 lines
Quoted 6 lines
Quoted 4 lines

This on top of misc-next throws 6 'write time' errors:

btrfs/101 [14:00:24][ 3963.736352] run fstests btrfs/101 at 2019-04-05 14:00:24

[ 3970.417649] BTRFS error (device vdc): block=2446344192 write time tree block corruption detected

In my case, these tests just pass, so I haven't checked the dmesg.

I have a filter for log (it's mix of terminal and kernel log)

egrep -a '(run fstests|WARNING:|BUG:|RIP:|UBSAN:|^\s+[+-]|CPU:.*Comm:|write time|read time|blocked for more than|Linux version)'

so the unexpected output is not lost among other messages.

Quoted 7 lines

Oh, those tests passes because of a bug in mainline.

6dc4f100c175 ("block: allow bio_for_each_segment_all() to iterate over multi-page bvec") prevents us from breaking bio_for_each_segment_all() loop, thus not triggering transaction abort.

A nice finding digging into the report.

Indeed, thanks. The hidden for-in-for in the macro would bite us later.