[PATCH] Btrfs: check btree node's nritems

[PATCH] Btrfs: check btree node's nritems

[Liu Bo]

When btree node (level = 1) has nritems which equals to zero,
we can end up with panic due to insert_ptr()'s

BUG_ON(slot > nritems);

where slot is 1 and nritems is 0, as copy_for_split() calls
insert_ptr(.., path->slots[1] + 1, ...);

A invalid value results in the whole mess, this adds the check
for btree's node nritems so that we stop reading block when
when something is wrong.

Signed-off-by: Liu Bo <bo.li.liu@oracle.com>
---
 fs/btrfs/disk-io.c | 17 +++++++++++++++++
 1 file changed, 17 insertions(+)

diff --git a/fs/btrfs/disk-io.c b/fs/btrfs/disk-io.c
index 37d1780..a5a22be 100644
--- a/fs/btrfs/disk-io.c
+++ b/fs/btrfs/disk-io.c
@@ -612,6 +612,20 @@ static noinline int check_leaf(struct btrfs_root *root,
 	return 0;
 }
 
+static noinline int check_node(struct btrfs_root *root,
+			       struct extent_buffer *node)
+{
+	unsigned long nr = btrfs_header_nritems(node);
+
+	if (nr <= 0 || nr >= BTRFS_NODEPTRS_PER_BLOCK(root)) {
+		btrfs_crit(root->fs_info,
+			   "corrupt node: block %llu root %llu nritems %lu\n",
+			   node->start, root->objectid, nr);
+		return -EIO;
+	}
+	return 0;
+}
+
 static int btree_readpage_end_io_hook(struct btrfs_io_bio *io_bio,
 				      u64 phy_offset, struct page *page,
 				      u64 start, u64 end, int mirror)
@@ -682,6 +696,9 @@ static int btree_readpage_end_io_hook(struct btrfs_io_bio *io_bio,
 		ret = -EIO;
 	}
 
+	if (found_level > 0 && check_node(root, eb))
+		ret = -EIO;
+
 	if (!ret)
 		set_extent_buffer_uptodate(eb);
 err:
-- 
2.5.5

Re: [PATCH] Btrfs: check btree node's nritems

[Holger Hoffstätte]

On Wed, 03 Aug 2016 12:57:28 -0700, Liu Bo wrote:

> When btree node (level = 1) has nritems which equals to zero,
> we can end up with panic due to insert_ptr()'s
> 
> BUG_ON(slot > nritems);
> 
> where slot is 1 and nritems is 0, as copy_for_split() calls
> insert_ptr(.., path->slots[1] + 1, ...);
> 
> A invalid value results in the whole mess, this adds the check
> for btree's node nritems so that we stop reading block when
> when something is wrong.
> 
> Signed-off-by: Liu Bo <bo.li.liu@oracle.com>
> ---
>  fs/btrfs/disk-io.c | 17 +++++++++++++++++
>  1 file changed, 17 insertions(+)
> 
> diff --git a/fs/btrfs/disk-io.c b/fs/btrfs/disk-io.c
> index 37d1780..a5a22be 100644
> --- a/fs/btrfs/disk-io.c
> +++ b/fs/btrfs/disk-io.c
> @@ -612,6 +612,20 @@ static noinline int check_leaf(struct btrfs_root *root,
>  	return 0;
>  }
>  
> +static noinline int check_node(struct btrfs_root *root,
> +			       struct extent_buffer *node)
> +{
> +	unsigned long nr = btrfs_header_nritems(node);
> +
> +	if (nr <= 0 || nr >= BTRFS_NODEPTRS_PER_BLOCK(root)) {
> +		btrfs_crit(root->fs_info,
> +			   "corrupt node: block %llu root %llu nritems %lu\n",

I think the trailing \n can be dropped here, btrfs_crit() already provides
a proper newline.

-h

Re: [PATCH] Btrfs: check btree node's nritems

[Holger Hoffstätte]

On 08/05/16 11:24, Holger Hoffstätte wrote:
> On Wed, 03 Aug 2016 12:57:28 -0700, Liu Bo wrote:
> 
>> When btree node (level = 1) has nritems which equals to zero,
>> we can end up with panic due to insert_ptr()'s
>>
>> BUG_ON(slot > nritems);
>>
>> where slot is 1 and nritems is 0, as copy_for_split() calls
>> insert_ptr(.., path->slots[1] + 1, ...);
>>
>> A invalid value results in the whole mess, this adds the check
>> for btree's node nritems so that we stop reading block when
>> when something is wrong.
>>
>> Signed-off-by: Liu Bo <bo.li.liu@oracle.com>
>> ---
>>  fs/btrfs/disk-io.c | 17 +++++++++++++++++
>>  1 file changed, 17 insertions(+)
>>
>> diff --git a/fs/btrfs/disk-io.c b/fs/btrfs/disk-io.c
>> index 37d1780..a5a22be 100644
>> --- a/fs/btrfs/disk-io.c
>> +++ b/fs/btrfs/disk-io.c
>> @@ -612,6 +612,20 @@ static noinline int check_leaf(struct btrfs_root *root,
>>  	return 0;
>>  }
>>  
>> +static noinline int check_node(struct btrfs_root *root,
>> +			       struct extent_buffer *node)
>> +{
>> +	unsigned long nr = btrfs_header_nritems(node);
>> +
>> +	if (nr <= 0 || nr >= BTRFS_NODEPTRS_PER_BLOCK(root)) {
>> +		btrfs_crit(root->fs_info,
>> +			   "corrupt node: block %llu root %llu nritems %lu\n",
> 
> I think the trailing \n can be dropped here, btrfs_crit() already provides
> a proper newline.

On top of that I get a whole bunch of false positives with this patch.
Files that are perfectly readable without it now error out, in which
case the logged nritems is always 493 - regardless of file or containing
subvolume. Something is fishy here.

-h

Re: [PATCH] Btrfs: check btree node's nritems

[David Sterba]

On Wed, Aug 03, 2016 at 12:57:28PM -0700, Liu Bo wrote:
> When btree node (level = 1) has nritems which equals to zero,
> we can end up with panic due to insert_ptr()'s
> 
> BUG_ON(slot > nritems);
> 
> where slot is 1 and nritems is 0, as copy_for_split() calls
> insert_ptr(.., path->slots[1] + 1, ...);
> 
> A invalid value results in the whole mess, this adds the check
> for btree's node nritems so that we stop reading block when
> when something is wrong.
> 
> Signed-off-by: Liu Bo <bo.li.liu@oracle.com>
> ---
>  fs/btrfs/disk-io.c | 17 +++++++++++++++++
>  1 file changed, 17 insertions(+)
> 
> diff --git a/fs/btrfs/disk-io.c b/fs/btrfs/disk-io.c
> index 37d1780..a5a22be 100644
> --- a/fs/btrfs/disk-io.c
> +++ b/fs/btrfs/disk-io.c
> @@ -612,6 +612,20 @@ static noinline int check_leaf(struct btrfs_root *root,
>  	return 0;
>  }
>  
> +static noinline int check_node(struct btrfs_root *root,
> +			       struct extent_buffer *node)
> +{
> +	unsigned long nr = btrfs_header_nritems(node);
> +
> +	if (nr <= 0 || nr >= BTRFS_NODEPTRS_PER_BLOCK(root)) {

nr is unsigned, so it's just  "== 0"

and the BTRFS_NODEPTRS_PER_BLOCK value is inclusive, which should
explain Holger's findings.

493 * sizeof (btrfs_key_ptr) + sizeof (btrfs_header) + slack = nodesize

493 * 33 + 101 + slack = 16k (the closest value)

gives slack = 14 (smaller than sizeof (btrfs_key_ptr))

Re: [PATCH] Btrfs: check btree node's nritems

[Liu Bo]

On Tue, Aug 16, 2016 at 06:50:00PM +0200, David Sterba wrote:
> On Wed, Aug 03, 2016 at 12:57:28PM -0700, Liu Bo wrote:
> > When btree node (level = 1) has nritems which equals to zero,
> > we can end up with panic due to insert_ptr()'s
> > 
> > BUG_ON(slot > nritems);
> > 
> > where slot is 1 and nritems is 0, as copy_for_split() calls
> > insert_ptr(.., path->slots[1] + 1, ...);
> > 
> > A invalid value results in the whole mess, this adds the check
> > for btree's node nritems so that we stop reading block when
> > when something is wrong.
> > 
> > Signed-off-by: Liu Bo <bo.li.liu@oracle.com>
> > ---
> >  fs/btrfs/disk-io.c | 17 +++++++++++++++++
> >  1 file changed, 17 insertions(+)
> > 
> > diff --git a/fs/btrfs/disk-io.c b/fs/btrfs/disk-io.c
> > index 37d1780..a5a22be 100644
> > --- a/fs/btrfs/disk-io.c
> > +++ b/fs/btrfs/disk-io.c
> > @@ -612,6 +612,20 @@ static noinline int check_leaf(struct btrfs_root *root,
> >  	return 0;
> >  }
> >  
> > +static noinline int check_node(struct btrfs_root *root,
> > +			       struct extent_buffer *node)
> > +{
> > +	unsigned long nr = btrfs_header_nritems(node);
> > +
> > +	if (nr <= 0 || nr >= BTRFS_NODEPTRS_PER_BLOCK(root)) {
> 
> nr is unsigned, so it's just  "== 0"
> 
> and the BTRFS_NODEPTRS_PER_BLOCK value is inclusive, which should
> explain Holger's findings.
> 
> 493 * sizeof (btrfs_key_ptr) + sizeof (btrfs_header) + slack = nodesize
> 
> 493 * 33 + 101 + slack = 16k (the closest value)
> 
> gives slack = 14 (smaller than sizeof (btrfs_key_ptr))

Oh, right, I made a mistake when getting the assumption from insert_ptr(), it should be nr > BTRFS_NODEPTRS_PER_BLOCK(root).

Thanks,

-liubo

[PATCH v2] Btrfs: check btree node's nritems

[Liu Bo]

When btree node (level = 1) has nritems which equals to zero,
we can end up with panic due to insert_ptr()'s

BUG_ON(slot > nritems);

where slot is 1 and nritems is 0, as copy_for_split() calls
insert_ptr(.., path->slots[1] + 1, ...);

A invalid value results in the whole mess, this adds the check
for btree's node nritems so that we stop reading block when
when something is wrong.

Signed-off-by: Liu Bo <bo.li.liu@oracle.com>
---
v2: - remove unnecessary "noinline"
    - fix to do the proper check as BTRFS_NODEPTRS_PER_BLOCK(root) is inclusive and nr is unsigned.

 fs/btrfs/disk-io.c | 16 ++++++++++++++++
 1 file changed, 16 insertions(+)

diff --git a/fs/btrfs/disk-io.c b/fs/btrfs/disk-io.c
index 90f57fa..682816d 100644
--- a/fs/btrfs/disk-io.c
+++ b/fs/btrfs/disk-io.c
@@ -633,6 +633,19 @@ static noinline int check_leaf(struct btrfs_root *root,
 	return 0;
 }
 
+static int check_node(struct btrfs_root *root, struct extent_buffer *node)
+{
+	unsigned long nr = btrfs_header_nritems(node);
+
+	if (nr == 0 || nr > BTRFS_NODEPTRS_PER_BLOCK(root)) {
+		btrfs_crit(root->fs_info,
+			   "corrupt node: block %llu root %llu nritems %lu\n",
+			   node->start, root->objectid, nr);
+		return -EIO;
+	}
+	return 0;
+}
+
 static int btree_readpage_end_io_hook(struct btrfs_io_bio *io_bio,
 				      u64 phy_offset, struct page *page,
 				      u64 start, u64 end, int mirror)
@@ -703,6 +716,9 @@ static int btree_readpage_end_io_hook(struct btrfs_io_bio *io_bio,
 		ret = -EIO;
 	}
 
+	if (found_level > 0 && check_node(root, eb))
+		ret = -EIO;
+
 	if (!ret)
 		set_extent_buffer_uptodate(eb);
 err:
-- 
2.5.5

Re: [PATCH v2] Btrfs: check btree node's nritems

[David Sterba]

On Tue, Aug 23, 2016 at 05:37:45PM -0700, Liu Bo wrote:
> When btree node (level = 1) has nritems which equals to zero,
> we can end up with panic due to insert_ptr()'s
> 
> BUG_ON(slot > nritems);
> 
> where slot is 1 and nritems is 0, as copy_for_split() calls
> insert_ptr(.., path->slots[1] + 1, ...);
> 
> A invalid value results in the whole mess, this adds the check
> for btree's node nritems so that we stop reading block when
> when something is wrong.
> 
> Signed-off-by: Liu Bo <bo.li.liu@oracle.com>

Reviewed-by: David Sterba <dsterba@suse.com>

> ---
> v2: - remove unnecessary "noinline"
>     - fix to do the proper check as BTRFS_NODEPTRS_PER_BLOCK(root) is inclusive and nr is unsigned.
> 
>  fs/btrfs/disk-io.c | 16 ++++++++++++++++
>  1 file changed, 16 insertions(+)
> 
> diff --git a/fs/btrfs/disk-io.c b/fs/btrfs/disk-io.c
> index 90f57fa..682816d 100644
> --- a/fs/btrfs/disk-io.c
> +++ b/fs/btrfs/disk-io.c
> @@ -633,6 +633,19 @@ static noinline int check_leaf(struct btrfs_root *root,
>  	return 0;
>  }
>  
> +static int check_node(struct btrfs_root *root, struct extent_buffer *node)
> +{
> +	unsigned long nr = btrfs_header_nritems(node);
> +
> +	if (nr == 0 || nr > BTRFS_NODEPTRS_PER_BLOCK(root)) {
> +		btrfs_crit(root->fs_info,
> +			   "corrupt node: block %llu root %llu nritems %lu\n",

I'll drop the newline.