[U-Boot] [PATCH] fs: btrfs: Fix tree traversal with btrfs_next_slot()

[U-Boot] [PATCH] fs: btrfs: Fix tree traversal with btrfs_next_slot()

[Yevgeny Popovych]

When traversing slots in a btree (via btrfs_path) with btrfs_next_slot(),
we didn't correctly identify that the last slot in the leaf was reached
and we should jump to the next leaf.

This could lead to any kind of runtime errors or corruptions, like:
* file data not being read at all, or is read partially
* file is read but is corrupted
* (any) metadata being corrupted or not read at all, etc

The easiest way to reproduce this is to read a large enough file that
its EXTENT_DATA items don't fit into a single leaf.

Signed-off-by: Yevgeny Popovych <yevgenyp@pointgrab.com>
Cc: Marek Behun <marek.behun@nic.cz>
---
 fs/btrfs/ctree.c | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

diff --git a/fs/btrfs/ctree.c b/fs/btrfs/ctree.c
index 4da36a9..b44a47e 100644
--- a/fs/btrfs/ctree.c
+++ b/fs/btrfs/ctree.c
@@ -270,7 +270,7 @@ int btrfs_next_slot(struct btrfs_path *p)
 {
 	struct btrfs_leaf *leaf = &p->nodes[0]->leaf;
 
-	if (p->slots[0] >= leaf->header.nritems)
+	if (p->slots[0] + 1 >= leaf->header.nritems)
 		return jump_leaf(p, 1);
 
 	p->slots[0]++;
-- 
2.7.4

[U-Boot] [PATCH] fs: btrfs: Fix tree traversal with btrfs_next_slot()

[Yevgeny Popovych]

Just a kindly reminder :)

On 09/07/2018 12:59 PM, Yevgeny Popovych wrote:
> When traversing slots in a btree (via btrfs_path) with btrfs_next_slot(),
> we didn't correctly identify that the last slot in the leaf was reached
> and we should jump to the next leaf.
> 
> This could lead to any kind of runtime errors or corruptions, like:
> * file data not being read at all, or is read partially
> * file is read but is corrupted
> * (any) metadata being corrupted or not read at all, etc
> 
> The easiest way to reproduce this is to read a large enough file that
> its EXTENT_DATA items don't fit into a single leaf.
> 
> Signed-off-by: Yevgeny Popovych <yevgenyp@pointgrab.com>
> Cc: Marek Behun <marek.behun@nic.cz>
> ---
>  fs/btrfs/ctree.c | 2 +-
>  1 file changed, 1 insertion(+), 1 deletion(-)
> 
> diff --git a/fs/btrfs/ctree.c b/fs/btrfs/ctree.c
> index 4da36a9..b44a47e 100644
> --- a/fs/btrfs/ctree.c
> +++ b/fs/btrfs/ctree.c
> @@ -270,7 +270,7 @@ int btrfs_next_slot(struct btrfs_path *p)
>  {
>  	struct btrfs_leaf *leaf = &p->nodes[0]->leaf;
>  
> -	if (p->slots[0] >= leaf->header.nritems)
> +	if (p->slots[0] + 1 >= leaf->header.nritems)
>  		return jump_leaf(p, 1);
>  
>  	p->slots[0]++;
> 

-- 
Sincerely,
Yevgeny Popovych

[U-Boot] [PATCH] fs: btrfs: Fix tree traversal with btrfs_next_slot()

[Marek Behún]

I shall test this today or tomorrow, but have too many things on my
head, sorry :(
You saying that this will fix reading large files? I haven't
encountered such an error yet, but can try creating a large enough
file. How large should it be? 

On Mon, 1 Oct 2018 08:50:11 +0300
Yevgeny Popovych <yevgenyp@pointgrab.com> wrote:

> Just a kindly reminder :)
> 
> On 09/07/2018 12:59 PM, Yevgeny Popovych wrote:
> > When traversing slots in a btree (via btrfs_path) with
> > btrfs_next_slot(), we didn't correctly identify that the last slot
> > in the leaf was reached and we should jump to the next leaf.
> > 
> > This could lead to any kind of runtime errors or corruptions, like:
> > * file data not being read at all, or is read partially
> > * file is read but is corrupted
> > * (any) metadata being corrupted or not read at all, etc
> > 
> > The easiest way to reproduce this is to read a large enough file
> > that its EXTENT_DATA items don't fit into a single leaf.
> > 
> > Signed-off-by: Yevgeny Popovych <yevgenyp@pointgrab.com>
> > Cc: Marek Behun <marek.behun@nic.cz>
> > ---
> >  fs/btrfs/ctree.c | 2 +-
> >  1 file changed, 1 insertion(+), 1 deletion(-)
> > 
> > diff --git a/fs/btrfs/ctree.c b/fs/btrfs/ctree.c
> > index 4da36a9..b44a47e 100644
> > --- a/fs/btrfs/ctree.c
> > +++ b/fs/btrfs/ctree.c
> > @@ -270,7 +270,7 @@ int btrfs_next_slot(struct btrfs_path *p)
> >  {
> >  	struct btrfs_leaf *leaf = &p->nodes[0]->leaf;
> >  
> > -	if (p->slots[0] >= leaf->header.nritems)
> > +	if (p->slots[0] + 1 >= leaf->header.nritems)
> >  		return jump_leaf(p, 1);
> >  
> >  	p->slots[0]++;
> >   
> 

[U-Boot] [PATCH] fs: btrfs: Fix tree traversal with btrfs_next_slot()

[Yevgeny Popovych]

Hi Marek,

No hurry from my side, please take your time!

I think that might be the case for every file that is > 32 MiB
but it definitely depends on filesystem layout (other files) and
maybe some options (my EXTENT_DATA describe blocks of 1MiB size)?
This also can happen to almost any file that is > 1 MiB given that
there are enough files + some luck.

Bottom line - create a 50MiB file and add 50 2 MiB files to the
filesystem. I would expect that to create necessary conditions.
After trying to read the file - check file checksum
(no guarantee that it will end up with an error).

You can inspect FS with dump-tree to check if EXTENT_DATA items of
this inode (large file) is split across the tree leaves.

Thanks!


On 10/01/2018 01:35 PM, Marek Behún wrote:
> I shall test this today or tomorrow, but have too many things on my
> head, sorry :(
> You saying that this will fix reading large files? I haven't
> encountered such an error yet, but can try creating a large enough
> file. How large should it be? 
> 
> On Mon, 1 Oct 2018 08:50:11 +0300
> Yevgeny Popovych <yevgenyp@pointgrab.com> wrote:
> 
>> Just a kindly reminder :)
>>
>> On 09/07/2018 12:59 PM, Yevgeny Popovych wrote:
>>> When traversing slots in a btree (via btrfs_path) with
>>> btrfs_next_slot(), we didn't correctly identify that the last slot
>>> in the leaf was reached and we should jump to the next leaf.
>>>
>>> This could lead to any kind of runtime errors or corruptions, like:
>>> * file data not being read at all, or is read partially
>>> * file is read but is corrupted
>>> * (any) metadata being corrupted or not read at all, etc
>>>
>>> The easiest way to reproduce this is to read a large enough file
>>> that its EXTENT_DATA items don't fit into a single leaf.
>>>
>>> Signed-off-by: Yevgeny Popovych <yevgenyp@pointgrab.com>
>>> Cc: Marek Behun <marek.behun@nic.cz>
>>> ---
>>>  fs/btrfs/ctree.c | 2 +-
>>>  1 file changed, 1 insertion(+), 1 deletion(-)
>>>
>>> diff --git a/fs/btrfs/ctree.c b/fs/btrfs/ctree.c
>>> index 4da36a9..b44a47e 100644
>>> --- a/fs/btrfs/ctree.c
>>> +++ b/fs/btrfs/ctree.c
>>> @@ -270,7 +270,7 @@ int btrfs_next_slot(struct btrfs_path *p)
>>>  {
>>>  	struct btrfs_leaf *leaf = &p->nodes[0]->leaf;
>>>  
>>> -	if (p->slots[0] >= leaf->header.nritems)
>>> +	if (p->slots[0] + 1 >= leaf->header.nritems)
>>>  		return jump_leaf(p, 1);
>>>  
>>>  	p->slots[0]++;
>>>   
>>
> 

-- 
Sincerely,
Yevgeny Popovych

[U-Boot] [PATCH] fs: btrfs: Fix tree traversal with btrfs_next_slot()

[Marek Behún]

Tested-by: Marek Behún <marek.behun@nic.cz>

Hello Tom, could you please apply the patch by Yevgeny?

Marek

On Fri,  7 Sep 2018 12:59:30 +0300
Yevgeny Popovych <yevgenyp@pointgrab.com> wrote:

> When traversing slots in a btree (via btrfs_path) with
> btrfs_next_slot(), we didn't correctly identify that the last slot in
> the leaf was reached and we should jump to the next leaf.
> 
> This could lead to any kind of runtime errors or corruptions, like:
> * file data not being read at all, or is read partially
> * file is read but is corrupted
> * (any) metadata being corrupted or not read at all, etc
> 
> The easiest way to reproduce this is to read a large enough file that
> its EXTENT_DATA items don't fit into a single leaf.
> 
> Signed-off-by: Yevgeny Popovych <yevgenyp@pointgrab.com>
> Cc: Marek Behun <marek.behun@nic.cz>
> ---
>  fs/btrfs/ctree.c | 2 +-
>  1 file changed, 1 insertion(+), 1 deletion(-)
> 
> diff --git a/fs/btrfs/ctree.c b/fs/btrfs/ctree.c
> index 4da36a9..b44a47e 100644
> --- a/fs/btrfs/ctree.c
> +++ b/fs/btrfs/ctree.c
> @@ -270,7 +270,7 @@ int btrfs_next_slot(struct btrfs_path *p)
>  {
>  	struct btrfs_leaf *leaf = &p->nodes[0]->leaf;
>  
> -	if (p->slots[0] >= leaf->header.nritems)
> +	if (p->slots[0] + 1 >= leaf->header.nritems)
>  		return jump_leaf(p, 1);
>  
>  	p->slots[0]++;

[U-Boot] [PATCH] fs: btrfs: Fix tree traversal with btrfs_next_slot()

[Tom Rini]

On Tue, Oct 02, 2018 at 01:22:28PM +0200, Marek Behún wrote:

> Tested-by: Marek Behún <marek.behun@nic.cz>
> 
> Hello Tom, could you please apply the patch by Yevgeny?

Sorry, I'll just lament that patchwork no longer has the ability to list
unassigned patches anymore.  I've given this to myself in patchwork and
will pick it up shortly.  Thanks!

> 
> Marek
> 
> On Fri,  7 Sep 2018 12:59:30 +0300
> Yevgeny Popovych <yevgenyp@pointgrab.com> wrote:
> 
> > When traversing slots in a btree (via btrfs_path) with
> > btrfs_next_slot(), we didn't correctly identify that the last slot in
> > the leaf was reached and we should jump to the next leaf.
> > 
> > This could lead to any kind of runtime errors or corruptions, like:
> > * file data not being read at all, or is read partially
> > * file is read but is corrupted
> > * (any) metadata being corrupted or not read at all, etc
> > 
> > The easiest way to reproduce this is to read a large enough file that
> > its EXTENT_DATA items don't fit into a single leaf.
> > 
> > Signed-off-by: Yevgeny Popovych <yevgenyp@pointgrab.com>
> > Cc: Marek Behun <marek.behun@nic.cz>
> > ---
> >  fs/btrfs/ctree.c | 2 +-
> >  1 file changed, 1 insertion(+), 1 deletion(-)
> > 
> > diff --git a/fs/btrfs/ctree.c b/fs/btrfs/ctree.c
> > index 4da36a9..b44a47e 100644
> > --- a/fs/btrfs/ctree.c
> > +++ b/fs/btrfs/ctree.c
> > @@ -270,7 +270,7 @@ int btrfs_next_slot(struct btrfs_path *p)
> >  {
> >  	struct btrfs_leaf *leaf = &p->nodes[0]->leaf;
> >  
> > -	if (p->slots[0] >= leaf->header.nritems)
> > +	if (p->slots[0] + 1 >= leaf->header.nritems)
> >  		return jump_leaf(p, 1);
> >  
> >  	p->slots[0]++;
> 

-- 
Tom
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 819 bytes
Desc: not available
URL: <http://lists.denx.de/pipermail/u-boot/attachments/20181008/0bf06144/attachment.sig>

[U-Boot] fs: btrfs: Fix tree traversal with btrfs_next_slot()

[Tom Rini]

On Fri, Sep 07, 2018 at 12:59:30PM +0300, Yevgeny Popovych wrote:

> When traversing slots in a btree (via btrfs_path) with btrfs_next_slot(),
> we didn't correctly identify that the last slot in the leaf was reached
> and we should jump to the next leaf.
> 
> This could lead to any kind of runtime errors or corruptions, like:
> * file data not being read at all, or is read partially
> * file is read but is corrupted
> * (any) metadata being corrupted or not read at all, etc
> 
> The easiest way to reproduce this is to read a large enough file that
> its EXTENT_DATA items don't fit into a single leaf.
> 
> Signed-off-by: Yevgeny Popovych <yevgenyp@pointgrab.com>
> Cc: Marek Behun <marek.behun@nic.cz>
> Tested-by: Marek Behún <marek.behun@nic.cz>

Applied to u-boot/master, thanks!

-- 
Tom
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 819 bytes
Desc: not available
URL: <http://lists.denx.de/pipermail/u-boot/attachments/20181011/6d5093cd/attachment.sig>