Btrfs: fix infinite loop when tree log recovery

Commit Message

robbieko Oct. 7, 2016, 9:30 a.m. UTC

From: Robbie Ko <[e-mail]>

if log tree like below:
leaf N:
        ...
        item 240 key (282 DIR_LOG_ITEM 0) itemoff 8189 itemsize 8
                dir log end 1275809046
leaf N+1:
        item 0 key (282 DIR_LOG_ITEM 3936149215) itemoff 16275 itemsize 8
                dir log end 18446744073709551615
        ...

when start_ret > 1275809046, but slot[0] never >= nritems,
so never go to next leaf.

Signed-off-by: Robbie Ko <[e-mail]>
---
 fs/btrfs/tree-log.c | 3 +--
 1 file changed, 1 insertion(+), 2 deletions(-)

Comments

Filipe Manana Nov. 30, 2016, 4:53 p.m. UTC | #1

On Fri, Oct 7, 2016 at 10:30 AM, robbieko <[e-mail]> wrote:
> From: Robbie Ko <[e-mail]>
>
> if log tree like below:
> leaf N:
>         ...
>         item 240 key (282 DIR_LOG_ITEM 0) itemoff 8189 itemsize 8
>                 dir log end 1275809046
> leaf N+1:
>         item 0 key (282 DIR_LOG_ITEM 3936149215) itemoff 16275 itemsize 8
>                 dir log end 18446744073709551615
>         ...
>
> when start_ret > 1275809046, but slot[0] never >= nritems,
> so never go to next leaf.

This doesn't explain how the infinite loop happens. Nor exactly how
any problem happens.

It's important to have detailed information in the change logs. I
understand that english isn't your native tongue (it's not mine
either, and I'm far from mastering it), but that's not an excuse to
not express all the important information in detail (we can all live
with grammar errors and typos, and we all do such errors frequently).

I've added this patch to my branch at
https://git.kernel.org/cgit/linux/kernel/git/fdmanana/linux.git/log/?h=for-chris-4.10
but with a modified changelog and subject.

The results of the wrong logic that decides when to move to the next
leaf are unpredictable, and it won't always result in an infinite
loop. We are accessing a slot that doesn't point to an item, to a
memory location containing garbage to something unexpected, and in the
worst case that location is beyond the last page of the extent buffer.

Thanks.


>
> Signed-off-by: Robbie Ko <[e-mail]>
> ---
>  fs/btrfs/tree-log.c | 3 +--
>  1 file changed, 1 insertion(+), 2 deletions(-)
>
> diff --git a/fs/btrfs/tree-log.c b/fs/btrfs/tree-log.c
> index ef9c55b..e63dd99 100644
> --- a/fs/btrfs/tree-log.c
> +++ b/fs/btrfs/tree-log.c
> @@ -1940,12 +1940,11 @@ static noinline int find_dir_range(struct btrfs_root *root,
>  next:
>         /* check the next slot in the tree to see if it is a valid item */
>         nritems = btrfs_header_nritems(path->nodes[0]);
> +       path->slots[0]++;
>         if (path->slots[0] >= nritems) {
>                 ret = btrfs_next_leaf(root, path);
>                 if (ret)
>                         goto out;
> -       } else {
> -               path->slots[0]++;
>         }
>
>         btrfs_item_key_to_cpu(path->nodes[0], &key, path->slots[0]);
> --
> 1.9.1
>
> --
> To unsubscribe from this list: send the line "unsubscribe linux-btrfs" in
> the body of a message to [e-mail]
> More majordomo info at  http://vger.kernel.org/majordomo-info.html

robbieko Dec. 1, 2016, 1:42 a.m. UTC | #2

Hi Filipe,

Thank you for your review.
I have seen your modified change log with below
     Btrfs: fix tree search logic when replaying directory entry deletes
     Btrfs: fix deadlock caused by fsync when logging directory entries
     Btrfs: fix enospc in hole punching
So what's the next step ?
modify patch change log and then send again ?

Thanks.
robbieko

Filipe Manana 於 2016-12-01 00:53 寫到:
> On Fri, Oct 7, 2016 at 10:30 AM, robbieko <[e-mail]> 
> wrote:
>> From: Robbie Ko <[e-mail]>
>> 
>> if log tree like below:
>> leaf N:
>>         ...
>>         item 240 key (282 DIR_LOG_ITEM 0) itemoff 8189 itemsize 8
>>                 dir log end 1275809046
>> leaf N+1:
>>         item 0 key (282 DIR_LOG_ITEM 3936149215) itemoff 16275 
>> itemsize 8
>>                 dir log end 18446744073709551615
>>         ...
>> 
>> when start_ret > 1275809046, but slot[0] never >= nritems,
>> so never go to next leaf.
> 
> This doesn't explain how the infinite loop happens. Nor exactly how
> any problem happens.
> 
> It's important to have detailed information in the change logs. I
> understand that english isn't your native tongue (it's not mine
> either, and I'm far from mastering it), but that's not an excuse to
> not express all the important information in detail (we can all live
> with grammar errors and typos, and we all do such errors frequently).
> 
> I've added this patch to my branch at
> https://git.kernel.org/cgit/linux/kernel/git/fdmanana/linux.git/log/?h=for-chris-4.10
> but with a modified changelog and subject.
> 
> The results of the wrong logic that decides when to move to the next
> leaf are unpredictable, and it won't always result in an infinite
> loop. We are accessing a slot that doesn't point to an item, to a
> memory location containing garbage to something unexpected, and in the
> worst case that location is beyond the last page of the extent buffer.
> 
> Thanks.
> 
> 
>> 
>> Signed-off-by: Robbie Ko <[e-mail]>
>> ---
>>  fs/btrfs/tree-log.c | 3 +--
>>  1 file changed, 1 insertion(+), 2 deletions(-)
>> 
>> diff --git a/fs/btrfs/tree-log.c b/fs/btrfs/tree-log.c
>> index ef9c55b..e63dd99 100644
>> --- a/fs/btrfs/tree-log.c
>> +++ b/fs/btrfs/tree-log.c
>> @@ -1940,12 +1940,11 @@ static noinline int find_dir_range(struct 
>> btrfs_root *root,
>>  next:
>>         /* check the next slot in the tree to see if it is a valid 
>> item */
>>         nritems = btrfs_header_nritems(path->nodes[0]);
>> +       path->slots[0]++;
>>         if (path->slots[0] >= nritems) {
>>                 ret = btrfs_next_leaf(root, path);
>>                 if (ret)
>>                         goto out;
>> -       } else {
>> -               path->slots[0]++;
>>         }
>> 
>>         btrfs_item_key_to_cpu(path->nodes[0], &key, path->slots[0]);
>> --
>> 1.9.1
>> 
>> --
>> To unsubscribe from this list: send the line "unsubscribe linux-btrfs" 
>> in
>> the body of a message to [e-mail]
>> More majordomo info at  http://vger.kernel.org/majordomo-info.html



--
To unsubscribe from this list: send the line "unsubscribe linux-btrfs" in
the body of a message to [e-mail]
More majordomo info at  http://vger.kernel.org/majordomo-info.html

Filipe Manana Dec. 1, 2016, 11:14 a.m. UTC | #3

On Thu, Dec 1, 2016 at 1:42 AM, robbieko <[e-mail]> wrote:
> Hi Filipe,
>
> Thank you for your review.
> I have seen your modified change log with below
>     Btrfs: fix tree search logic when replaying directory entry deletes
>     Btrfs: fix deadlock caused by fsync when logging directory entries
>     Btrfs: fix enospc in hole punching
> So what's the next step ?
> modify patch change log and then send again ?

You don't need to do anything else for those patches.
Thanks.

>
> Thanks.
> robbieko
>
> Filipe Manana 於 2016-12-01 00:53 寫到:
>
>> On Fri, Oct 7, 2016 at 10:30 AM, robbieko <[e-mail]> wrote:
>>>
>>> From: Robbie Ko <[e-mail]>
>>>
>>> if log tree like below:
>>> leaf N:
>>>         ...
>>>         item 240 key (282 DIR_LOG_ITEM 0) itemoff 8189 itemsize 8
>>>                 dir log end 1275809046
>>> leaf N+1:
>>>         item 0 key (282 DIR_LOG_ITEM 3936149215) itemoff 16275 itemsize 8
>>>                 dir log end 18446744073709551615
>>>         ...
>>>
>>> when start_ret > 1275809046, but slot[0] never >= nritems,
>>> so never go to next leaf.
>>
>>
>> This doesn't explain how the infinite loop happens. Nor exactly how
>> any problem happens.
>>
>> It's important to have detailed information in the change logs. I
>> understand that english isn't your native tongue (it's not mine
>> either, and I'm far from mastering it), but that's not an excuse to
>> not express all the important information in detail (we can all live
>> with grammar errors and typos, and we all do such errors frequently).
>>
>> I've added this patch to my branch at
>>
>> https://git.kernel.org/cgit/linux/kernel/git/fdmanana/linux.git/log/?h=for-chris-4.10
>> but with a modified changelog and subject.
>>
>> The results of the wrong logic that decides when to move to the next
>> leaf are unpredictable, and it won't always result in an infinite
>> loop. We are accessing a slot that doesn't point to an item, to a
>> memory location containing garbage to something unexpected, and in the
>> worst case that location is beyond the last page of the extent buffer.
>>
>> Thanks.
>>
>>
>>>
>>> Signed-off-by: Robbie Ko <[e-mail]>
>>> ---
>>>  fs/btrfs/tree-log.c | 3 +--
>>>  1 file changed, 1 insertion(+), 2 deletions(-)
>>>
>>> diff --git a/fs/btrfs/tree-log.c b/fs/btrfs/tree-log.c
>>> index ef9c55b..e63dd99 100644
>>> --- a/fs/btrfs/tree-log.c
>>> +++ b/fs/btrfs/tree-log.c
>>> @@ -1940,12 +1940,11 @@ static noinline int find_dir_range(struct
>>> btrfs_root *root,
>>>  next:
>>>         /* check the next slot in the tree to see if it is a valid item
>>> */
>>>         nritems = btrfs_header_nritems(path->nodes[0]);
>>> +       path->slots[0]++;
>>>         if (path->slots[0] >= nritems) {
>>>                 ret = btrfs_next_leaf(root, path);
>>>                 if (ret)
>>>                         goto out;
>>> -       } else {
>>> -               path->slots[0]++;
>>>         }
>>>
>>>         btrfs_item_key_to_cpu(path->nodes[0], &key, path->slots[0]);
>>> --
>>> 1.9.1
>>>
>>> --
>>> To unsubscribe from this list: send the line "unsubscribe linux-btrfs" in
>>> the body of a message to [e-mail]
>>> More majordomo info at  http://vger.kernel.org/majordomo-info.html
>
>
>
>

robbieko Dec. 2, 2016, 1:32 a.m. UTC | #4

Hi Filipe,

Thank you for your help.

I will make up the incremental send change log as soon as possible.

Thanks.
robbieko

Filipe Manana 於 2016-12-01 19:14 寫到:
> On Thu, Dec 1, 2016 at 1:42 AM, robbieko <[e-mail]> wrote:
>> Hi Filipe,
>> 
>> Thank you for your review.
>> I have seen your modified change log with below
>>     Btrfs: fix tree search logic when replaying directory entry 
>> deletes
>>     Btrfs: fix deadlock caused by fsync when logging directory entries
>>     Btrfs: fix enospc in hole punching
>> So what's the next step ?
>> modify patch change log and then send again ?
> 
> You don't need to do anything else for those patches.
> Thanks.
> 
>> 
>> Thanks.
>> robbieko
>> 
>> Filipe Manana 於 2016-12-01 00:53 寫到:
>> 
>>> On Fri, Oct 7, 2016 at 10:30 AM, robbieko <[e-mail]> 
>>> wrote:
>>>> 
>>>> From: Robbie Ko <[e-mail]>
>>>> 
>>>> if log tree like below:
>>>> leaf N:
>>>>         ...
>>>>         item 240 key (282 DIR_LOG_ITEM 0) itemoff 8189 itemsize 8
>>>>                 dir log end 1275809046
>>>> leaf N+1:
>>>>         item 0 key (282 DIR_LOG_ITEM 3936149215) itemoff 16275 
>>>> itemsize 8
>>>>                 dir log end 18446744073709551615
>>>>         ...
>>>> 
>>>> when start_ret > 1275809046, but slot[0] never >= nritems,
>>>> so never go to next leaf.
>>> 
>>> 
>>> This doesn't explain how the infinite loop happens. Nor exactly how
>>> any problem happens.
>>> 
>>> It's important to have detailed information in the change logs. I
>>> understand that english isn't your native tongue (it's not mine
>>> either, and I'm far from mastering it), but that's not an excuse to
>>> not express all the important information in detail (we can all live
>>> with grammar errors and typos, and we all do such errors frequently).
>>> 
>>> I've added this patch to my branch at
>>> 
>>> https://git.kernel.org/cgit/linux/kernel/git/fdmanana/linux.git/log/?h=for-chris-4.10
>>> but with a modified changelog and subject.
>>> 
>>> The results of the wrong logic that decides when to move to the next
>>> leaf are unpredictable, and it won't always result in an infinite
>>> loop. We are accessing a slot that doesn't point to an item, to a
>>> memory location containing garbage to something unexpected, and in 
>>> the
>>> worst case that location is beyond the last page of the extent 
>>> buffer.
>>> 
>>> Thanks.
>>> 
>>> 
>>>> 
>>>> Signed-off-by: Robbie Ko <[e-mail]>
>>>> ---
>>>>  fs/btrfs/tree-log.c | 3 +--
>>>>  1 file changed, 1 insertion(+), 2 deletions(-)
>>>> 
>>>> diff --git a/fs/btrfs/tree-log.c b/fs/btrfs/tree-log.c
>>>> index ef9c55b..e63dd99 100644
>>>> --- a/fs/btrfs/tree-log.c
>>>> +++ b/fs/btrfs/tree-log.c
>>>> @@ -1940,12 +1940,11 @@ static noinline int find_dir_range(struct
>>>> btrfs_root *root,
>>>>  next:
>>>>         /* check the next slot in the tree to see if it is a valid 
>>>> item
>>>> */
>>>>         nritems = btrfs_header_nritems(path->nodes[0]);
>>>> +       path->slots[0]++;
>>>>         if (path->slots[0] >= nritems) {
>>>>                 ret = btrfs_next_leaf(root, path);
>>>>                 if (ret)
>>>>                         goto out;
>>>> -       } else {
>>>> -               path->slots[0]++;
>>>>         }
>>>> 
>>>>         btrfs_item_key_to_cpu(path->nodes[0], &key, path->slots[0]);
>>>> --
>>>> 1.9.1
>>>> 
>>>> --
>>>> To unsubscribe from this list: send the line "unsubscribe 
>>>> linux-btrfs" in
>>>> the body of a message to [e-mail]
>>>> More majordomo info at  http://vger.kernel.org/majordomo-info.html
>> 
>> 
>> 
>> 


--
To unsubscribe from this list: send the line "unsubscribe linux-btrfs" in
the body of a message to [e-mail]
More majordomo info at  http://vger.kernel.org/majordomo-info.html

Patch

diff --git a/fs/btrfs/tree-log.c b/fs/btrfs/tree-log.c
index ef9c55b..e63dd99 100644
--- a/fs/btrfs/tree-log.c
+++ b/fs/btrfs/tree-log.c
@@ -1940,12 +1940,11 @@  static noinline int find_dir_range(struct btrfs_root *root,
 next:
 	/* check the next slot in the tree to see if it is a valid item */
 	nritems = btrfs_header_nritems(path->nodes[0]);
+	path->slots[0]++;
 	if (path->slots[0] >= nritems) {
 		ret = btrfs_next_leaf(root, path);
 		if (ret)
 			goto out;
-	} else {
-		path->slots[0]++;
 	}
 
 	btrfs_item_key_to_cpu(path->nodes[0], &key, path->slots[0]);