[PATCH] btrfs-progs: Check the consistence between the parent node and child node/leaf.

[PATCH] btrfs-progs: Check the consistence between the parent node and child node/leaf.

[Qu Wenruo]

When btrfs-progs walk down the tree, it does not check whether the child
node/leaf is valid.
In fact, there is some corrupted image whose csum is all valid but
parent node points to a invalid leaf.

In my case, the parent node in fs tree point to a invalid leaf(gen 11),
whose generation(15) and first key(EXTENT_TREE ROOT_ITEM 0) is
completely invalid, and will cause BUG_ON in process_inode_item().

Unfortunately, we are unable to fix when it happens.
So we can only output meaningful error message and avoid the insane
node/leaf, which is still much better than the original BUG_ON().

Signed-off-by: Qu Wenruo <quwenruo@cn.fujitsu.com>
---
 cmds-check.c | 51 +++++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 51 insertions(+)

diff --git a/cmds-check.c b/cmds-check.c
index d479361..9471709 100644
--- a/cmds-check.c
+++ b/cmds-check.c
@@ -1302,6 +1302,52 @@ static void reada_walk_down(struct btrfs_root *root,
 	}
 }
 
+/*
+ * Check the child node/leaf by the following condition:
+ * 1. the first item key of the node/leaf should be the same with the one
+ *    in parent.
+ * 2. block in parent node should match the child node/leaf.
+ * 3. generation of parent node and child's header should be consistent.
+ *
+ * Or the child node/leaf pointed by the key in parent is not valid.
+ *
+ * We hope to check leaf owner too, but since subvol may share leaves,
+ * which makes leaf owner check not so strong, key check should be
+ * sufficient enough for that case.
+ */
+static int check_child_node(struct btrfs_root *root,
+			    struct extent_buffer *parent, int slot,
+			    struct extent_buffer *child)
+{
+	struct btrfs_key parent_key;
+	struct btrfs_key child_key;
+	int ret = 0;
+
+	btrfs_item_key_to_cpu(parent, &parent_key, slot);
+	btrfs_item_key_to_cpu(child, &child_key, 0);
+	if (memcmp(&parent_key, &child_key, sizeof(parent_key))) {
+		ret = -EINVAL;
+		fprintf(stderr,
+			"Wrong key of child node/leaf, wanted: (%llu, %u, %llu), have: (%llu, %u, %llu)\n",
+			parent_key.objectid, parent_key.type, parent_key.offset,
+			child_key.objectid, child_key.type, child_key.offset);
+	}
+	if (btrfs_header_bytenr(child) != btrfs_node_blockptr(parent, slot)) {
+		ret = -EINVAL;
+		fprintf(stderr, "Wrong block of child node/leaf, wanted: %llu, have: %llu\n",
+			btrfs_node_blockptr(parent, slot),
+			btrfs_header_bytenr(child));
+	}
+	if (btrfs_node_ptr_generation(parent, slot) !=
+	    btrfs_header_generation(child)) {
+		ret = -EINVAL;
+		fprintf(stderr, "Wrong generation of child node/leaf, wanted: %llu, have: %llu\n",
+			btrfs_header_generation(child),
+			btrfs_node_ptr_generation(parent, slot));
+	}
+	return ret;
+}
+
 static int walk_down_tree(struct btrfs_root *root, struct btrfs_path *path,
 			  struct walk_control *wc, int *level)
 {
@@ -1375,6 +1421,11 @@ static int walk_down_tree(struct btrfs_root *root, struct btrfs_path *path,
 			}
 		}
 
+		ret = check_child_node(root, cur, path->slots[*level], next);
+		if (ret) {
+			err = ret;
+			goto out;
+		}
 		*level = *level - 1;
 		free_extent_buffer(path->nodes[*level]);
 		path->nodes[*level] = next;
-- 
2.1.1

Re: [PATCH] btrfs-progs: Check the consistence between the parent node and child node/leaf.

[Chris Mason]

On Fri, Sep 26, 2014 at 3:36 AM, Qu Wenruo <quwenruo@cn.fujitsu.com> 
wrote:
> When btrfs-progs walk down the tree, it does not check whether the 
> child
> node/leaf is valid.
> In fact, there is some corrupted image whose csum is all valid but
> parent node points to a invalid leaf.
> 
> In my case, the parent node in fs tree point to a invalid leaf(gen 
> 11),
> whose generation(15) and first key(EXTENT_TREE ROOT_ITEM 0) is
> completely invalid, and will cause BUG_ON in process_inode_item().
> 
> Unfortunately, we are unable to fix when it happens.
> So we can only output meaningful error message and avoid the insane
> node/leaf, which is still much better than the original BUG_ON().
> 
> Signed-off-by: Qu Wenruo <quwenruo@cn.fujitsu.com>
> ---
>  cmds-check.c | 51 +++++++++++++++++++++++++++++++++++++++++++++++++++
>  1 file changed, 51 insertions(+)
> 
> diff --git a/cmds-check.c b/cmds-check.c
> index d479361..9471709 100644
> --- a/cmds-check.c
> +++ b/cmds-check.c
> @@ -1302,6 +1302,52 @@ static void reada_walk_down(struct btrfs_root 
> *root,
>  	}
>  }
> 
> +/*
> + * Check the child node/leaf by the following condition:
> + * 1. the first item key of the node/leaf should be the same with 
> the one
> + *    in parent.
> + * 2. block in parent node should match the child node/leaf.
> + * 3. generation of parent node and child's header should be 
> consistent.
> + *
> + * Or the child node/leaf pointed by the key in parent is not valid.
> + *
> + * We hope to check leaf owner too, but since subvol may share 
> leaves,
> + * which makes leaf owner check not so strong, key check should be
> + * sufficient enough for that case.
> + */
> +static int check_child_node(struct btrfs_root *root,
> +			    struct extent_buffer *parent, int slot,
> +			    struct extent_buffer *child)
> +{
> +	struct btrfs_key parent_key;
> +	struct btrfs_key child_key;
> +	int ret = 0;
> +
> +	btrfs_item_key_to_cpu(parent, &parent_key, slot);

Dave mentioned he was getting a bunch of Wrong key of child node 
messages from his current tree.  I should have spotted it sooner, but 
this call should be btrfs_node_key_to_cpu(), since the parent is always 
a node.

> 
> +	btrfs_item_key_to_cpu(child, &child_key, 0);

This should check the level and only use btrfs_item_key_to_cpu on the 
leaves.

Thanks!

-chris

Re: [PATCH] btrfs-progs: Check the consistence between the parent node and child node/leaf.

[Qu Wenruo]

-------- Original Message --------
Subject: Re: [PATCH] btrfs-progs: Check the consistence between the 
parent node and child node/leaf.
From: Chris Mason <clm@fb.com>
To: Qu Wenruo <quwenruo@cn.fujitsu.com>
Date: 2014年10月01日 23:49
> On Fri, Sep 26, 2014 at 3:36 AM, Qu Wenruo <quwenruo@cn.fujitsu.com> 
> wrote:
>> When btrfs-progs walk down the tree, it does not check whether the child
>> node/leaf is valid.
>> In fact, there is some corrupted image whose csum is all valid but
>> parent node points to a invalid leaf.
>>
>> In my case, the parent node in fs tree point to a invalid leaf(gen 11),
>> whose generation(15) and first key(EXTENT_TREE ROOT_ITEM 0) is
>> completely invalid, and will cause BUG_ON in process_inode_item().
>>
>> Unfortunately, we are unable to fix when it happens.
>> So we can only output meaningful error message and avoid the insane
>> node/leaf, which is still much better than the original BUG_ON().
>>
>> Signed-off-by: Qu Wenruo <quwenruo@cn.fujitsu.com>
>> ---
>>  cmds-check.c | 51 +++++++++++++++++++++++++++++++++++++++++++++++++++
>>  1 file changed, 51 insertions(+)
>>
>> diff --git a/cmds-check.c b/cmds-check.c
>> index d479361..9471709 100644
>> --- a/cmds-check.c
>> +++ b/cmds-check.c
>> @@ -1302,6 +1302,52 @@ static void reada_walk_down(struct btrfs_root 
>> *root,
>>      }
>>  }
>>
>> +/*
>> + * Check the child node/leaf by the following condition:
>> + * 1. the first item key of the node/leaf should be the same with 
>> the one
>> + *    in parent.
>> + * 2. block in parent node should match the child node/leaf.
>> + * 3. generation of parent node and child's header should be 
>> consistent.
>> + *
>> + * Or the child node/leaf pointed by the key in parent is not valid.
>> + *
>> + * We hope to check leaf owner too, but since subvol may share leaves,
>> + * which makes leaf owner check not so strong, key check should be
>> + * sufficient enough for that case.
>> + */
>> +static int check_child_node(struct btrfs_root *root,
>> +                struct extent_buffer *parent, int slot,
>> +                struct extent_buffer *child)
>> +{
>> +    struct btrfs_key parent_key;
>> +    struct btrfs_key child_key;
>> +    int ret = 0;
>> +
>> +    btrfs_item_key_to_cpu(parent, &parent_key, slot);
>
> Dave mentioned he was getting a bunch of Wrong key of child node 
> messages from his current tree.  I should have spotted it sooner, but 
> this call should be btrfs_node_key_to_cpu(), since the parent is 
> always a node.
>
>>
>> +    btrfs_item_key_to_cpu(child, &child_key, 0);
>
> This should check the level and only use btrfs_item_key_to_cpu on the 
> leaves.
>
> Thanks!
>
> -chris
>
>
Oh, that's completely right...
I forgot node and leaf should use different key to cpu func... :(

I'll fix it soon.

Thanks,
Qu