[PATCH 1/3] btrfs-progs: remove comments about delayed ref in backref.c

[PATCH 1/3] btrfs-progs: remove comments about delayed ref in backref.c

[Su Yue]

There is no delayed ref in btrfs-progs, so remove related comments.

Signed-off-by: Su Yue <suy.fnst@cn.fujitsu.com>
---
 backref.c | 19 +++----------------
 1 file changed, 3 insertions(+), 16 deletions(-)

diff --git a/backref.c b/backref.c
index 27309e07a1e9..c144dbf060f2 100644
--- a/backref.c
+++ b/backref.c
@@ -155,19 +155,6 @@ static void init_pref_state(struct pref_state *prefstate)
  * - if you cannot add the parent or a correct key, then we will look into the
  *   block later to set a correct key
  *
- * delayed refs
- * ============
- *        backref type | shared | indirect | shared | indirect
- * information         |   tree |     tree |   data |     data
- * --------------------+--------+----------+--------+----------
- *      parent logical |    y   |     -    |    -   |     -
- *      key to resolve |    -   |     y    |    y   |     y
- *  tree block logical |    -   |     -    |    -   |     -
- *  root for resolving |    y   |     y    |    y   |     y
- *
- * - column 1:       we've the parent -> done
- * - column 2, 3, 4: we use the key to find the parent
- *
  * on disk refs (inline or keyed)
  * ==============================
  *        backref type | shared | indirect | shared | indirect
@@ -735,9 +722,9 @@ static int __add_keyed_refs(struct btrfs_fs_info *fs_info,
 }
 
 /*
- * this adds all existing backrefs (inline backrefs, backrefs and delayed
- * refs) for the given bytenr to the refs list, merges duplicates and resolves
- * indirect refs to their parent bytenr.
+ * this adds all existing backrefs (inline backrefs, backrefs for the given
+ * bytenr to the refs list, merges duplicates and resolves indirect refs to
+ * their parent bytenr.
  * When roots are found, they're added to the roots list
  *
  * FIXME some caching might speed things up
-- 
2.17.0

[PATCH 2/3] btrfs-progs: remove useless branch in __merge_refs

[Su Yue]

After call of ref_for_same_block, ref1->parent must equals to
ref2->parent, the block of exchange is never reached.

So remove the block of exchange.

Signed-off-by: Su Yue <suy.fnst@cn.fujitsu.com>
---
 backref.c | 6 ------
 1 file changed, 6 deletions(-)

diff --git a/backref.c b/backref.c
index c144dbf060f2..51553c702187 100644
--- a/backref.c
+++ b/backref.c
@@ -497,7 +497,6 @@ static void __merge_refs(struct pref_state *prefstate, int mode)
 		for (pos2 = pos1->next, n2 = pos2->next; pos2 != head;
 		     pos2 = n2, n2 = pos2->next) {
 			struct __prelim_ref *ref2;
-			struct __prelim_ref *xchg;
 			struct extent_inode_elem *eie;
 
 			ref2 = list_entry(pos2, struct __prelim_ref, list);
@@ -505,11 +504,6 @@ static void __merge_refs(struct pref_state *prefstate, int mode)
 			if (mode == 1) {
 				if (!ref_for_same_block(ref1, ref2))
 					continue;
-				if (!ref1->parent && ref2->parent) {
-					xchg = ref1;
-					ref1 = ref2;
-					ref2 = xchg;
-				}
 			} else {
 				if (ref1->parent != ref2->parent)
 					continue;
-- 
2.17.0

[PATCH 3/3] btrfs-progs: do not merge tree block refs have different root_id

[Su Yue]

For an extent item which contains many tree block backrefs, like
=================================================================
In 020-extent-ref-cases/keyed_block_ref.img

item 10 key (29470720 METADATA_ITEM 0) itemoff 3450 itemsize 222
                refs 23 gen 10 flags TREE_BLOCK
                tree block skinny level 0
                tree block backref root 278
                tree block backref root 277
                tree block backref root 276
                tree block backref root 275
                tree block backref root 274
                tree block backref root 273
                tree block backref root 272
                tree block backref root 271
                tree block backref root 270
                tree block backref root 269
                tree block backref root 268
                tree block backref root 267
                tree block backref root 266
                tree block backref root 265
                tree block backref root 264
                tree block backref root 263
                tree block backref root 262
                tree block backref root 261
                tree block backref root 260
                tree block backref root 259
                tree block backref root 258
                tree block backref root 257
=================================================================
In find_parent_nodes(), these refs's parents are 0, then __merge_refs
will merge refs to one ref. It causes only one root to be returned.

So, if both parents are 0, do not merge refs.

Lowmem check calls find_parent_nodes frequently to decide whether.
check an extent buffer or not. These bug influences bytes accounting.

Signed-off-by: Su Yue <suy.fnst@cn.fujitsu.com>
---
 backref.c | 2 ++
 1 file changed, 2 insertions(+)

diff --git a/backref.c b/backref.c
index 51553c702187..daadb6299c79 100644
--- a/backref.c
+++ b/backref.c
@@ -507,6 +507,8 @@ static void __merge_refs(struct pref_state *prefstate, int mode)
 			} else {
 				if (ref1->parent != ref2->parent)
 					continue;
+				if (ref1->parent == 0)
+					continue;
 			}
 
 			eie = ref1->inode_list;
-- 
2.17.0

Re: [PATCH 1/3] btrfs-progs: remove comments about delayed ref in backref.c

[Qu Wenruo]

[-- Attachment #1.1: Type: text/plain, Size: 2174 bytes --]



On 2018年04月24日 13:52, Su Yue wrote:
> There is no delayed ref in btrfs-progs, so remove related comments.
> 

Indeed.
Delayed ref is only used to speed up extent tree modification with the
cost of code complexity.

For btrfs-progs we don't need to worry about it at all.

Thanks,
Qu

> Signed-off-by: Su Yue <suy.fnst@cn.fujitsu.com>
> ---
>  backref.c | 19 +++----------------
>  1 file changed, 3 insertions(+), 16 deletions(-)
> 
> diff --git a/backref.c b/backref.c
> index 27309e07a1e9..c144dbf060f2 100644
> --- a/backref.c
> +++ b/backref.c
> @@ -155,19 +155,6 @@ static void init_pref_state(struct pref_state *prefstate)
>   * - if you cannot add the parent or a correct key, then we will look into the
>   *   block later to set a correct key
>   *
> - * delayed refs
> - * ============
> - *        backref type | shared | indirect | shared | indirect
> - * information         |   tree |     tree |   data |     data
> - * --------------------+--------+----------+--------+----------
> - *      parent logical |    y   |     -    |    -   |     -
> - *      key to resolve |    -   |     y    |    y   |     y
> - *  tree block logical |    -   |     -    |    -   |     -
> - *  root for resolving |    y   |     y    |    y   |     y
> - *
> - * - column 1:       we've the parent -> done
> - * - column 2, 3, 4: we use the key to find the parent
> - *
>   * on disk refs (inline or keyed)
>   * ==============================
>   *        backref type | shared | indirect | shared | indirect
> @@ -735,9 +722,9 @@ static int __add_keyed_refs(struct btrfs_fs_info *fs_info,
>  }
>  
>  /*
> - * this adds all existing backrefs (inline backrefs, backrefs and delayed
> - * refs) for the given bytenr to the refs list, merges duplicates and resolves
> - * indirect refs to their parent bytenr.
> + * this adds all existing backrefs (inline backrefs, backrefs for the given
> + * bytenr to the refs list, merges duplicates and resolves indirect refs to
> + * their parent bytenr.
>   * When roots are found, they're added to the roots list
>   *
>   * FIXME some caching might speed things up
> 


[-- Attachment #2: OpenPGP digital signature --]
[-- Type: application/pgp-signature, Size: 488 bytes --]

Re: [PATCH 2/3] btrfs-progs: remove useless branch in __merge_refs

[Qu Wenruo]

[-- Attachment #1.1: Type: text/plain, Size: 1422 bytes --]



On 2018年04月24日 13:52, Su Yue wrote:
> After call of ref_for_same_block, ref1->parent must equals to
> ref2->parent, the block of exchange is never reached.
> 
> So remove the block of exchange.

Reviewed-by: Qu Wenruo <wqu@suse.com>

The patch looks good, but considering how much difference the kernel and
btrfs-progs have in backref.c, I think it would be much better to start
merging code for it.

Thanks,
Qu

> 
> Signed-off-by: Su Yue <suy.fnst@cn.fujitsu.com>
> ---
>  backref.c | 6 ------
>  1 file changed, 6 deletions(-)
> 
> diff --git a/backref.c b/backref.c
> index c144dbf060f2..51553c702187 100644
> --- a/backref.c
> +++ b/backref.c
> @@ -497,7 +497,6 @@ static void __merge_refs(struct pref_state *prefstate, int mode)
>  		for (pos2 = pos1->next, n2 = pos2->next; pos2 != head;
>  		     pos2 = n2, n2 = pos2->next) {
>  			struct __prelim_ref *ref2;
> -			struct __prelim_ref *xchg;
>  			struct extent_inode_elem *eie;
>  
>  			ref2 = list_entry(pos2, struct __prelim_ref, list);
> @@ -505,11 +504,6 @@ static void __merge_refs(struct pref_state *prefstate, int mode)
>  			if (mode == 1) {
>  				if (!ref_for_same_block(ref1, ref2))
>  					continue;> -				if (!ref1->parent && ref2->parent) {
> -					xchg = ref1;
> -					ref1 = ref2;
> -					ref2 = xchg;
> -				}
>  			} else {
>  				if (ref1->parent != ref2->parent)
>  					continue;
> 


[-- Attachment #2: OpenPGP digital signature --]
[-- Type: application/pgp-signature, Size: 488 bytes --]

Re: [PATCH 3/3] btrfs-progs: do not merge tree block refs have different root_id

[Qu Wenruo]

[-- Attachment #1.1: Type: text/plain, Size: 3014 bytes --]



On 2018年04月24日 13:52, Su Yue wrote:
> For an extent item which contains many tree block backrefs, like
> =================================================================
> In 020-extent-ref-cases/keyed_block_ref.img
> 
> item 10 key (29470720 METADATA_ITEM 0) itemoff 3450 itemsize 222
>                 refs 23 gen 10 flags TREE_BLOCK
>                 tree block skinny level 0
>                 tree block backref root 278
>                 tree block backref root 277
>                 tree block backref root 276
>                 tree block backref root 275
>                 tree block backref root 274
>                 tree block backref root 273
>                 tree block backref root 272
>                 tree block backref root 271
>                 tree block backref root 270
>                 tree block backref root 269
>                 tree block backref root 268
>                 tree block backref root 267
>                 tree block backref root 266
>                 tree block backref root 265
>                 tree block backref root 264
>                 tree block backref root 263
>                 tree block backref root 262
>                 tree block backref root 261
>                 tree block backref root 260
>                 tree block backref root 259
>                 tree block backref root 258
>                 tree block backref root 257
> =================================================================
> In find_parent_nodes(), these refs's parents are 0, then __merge_refs
> will merge refs to one ref. It causes only one root to be returned.

This is a pretty big problem, and it would cause qgroup verification
code to cause false alerts.

So a new test case would do great help here.

> 
> So, if both parents are 0, do not merge refs.
> 
> Lowmem check calls find_parent_nodes frequently to decide whether.
> check an extent buffer or not. These bug influences bytes accounting.

Although it looks good so far, and would fix the problem you found, but
I strongly recommend to port kernel backref code to btrfs-progs here, as
kernel backref code is more tested than btrfs-progs backref code.

I'm pretty sure we have more bugs in btrfs-progs backref, and I'm not a
big fan of playing whac-a-mole here.

> 
> Signed-off-by: Su Yue <suy.fnst@cn.fujitsu.com>
> ---
>  backref.c | 2 ++
>  1 file changed, 2 insertions(+)
> 
> diff --git a/backref.c b/backref.c
> index 51553c702187..daadb6299c79 100644
> --- a/backref.c
> +++ b/backref.c
> @@ -507,6 +507,8 @@ static void __merge_refs(struct pref_state *prefstate, int mode)
>  			} else {
>  				if (ref1->parent != ref2->parent)
>  					continue;
> +				if (ref1->parent == 0)
> +					continue;

It's better to put it above (ref1->parent != ref2->parent).
As parent == 0 means we haven't resolve the parent bytenr yet, so can't
be merged nor compared.

Thanks,
Qu

>  			}
>  
>  			eie = ref1->inode_list;
> 


[-- Attachment #2: OpenPGP digital signature --]
[-- Type: application/pgp-signature, Size: 488 bytes --]

Re: [PATCH 3/3] btrfs-progs: do not merge tree block refs have different root_id

[Su Yue]

On 04/24/2018 02:17 PM, Qu Wenruo wrote:
> 
> 
> On 2018年04月24日 13:52, Su Yue wrote:
>> For an extent item which contains many tree block backrefs, like
>> =================================================================
>> In 020-extent-ref-cases/keyed_block_ref.img
>>
>> item 10 key (29470720 METADATA_ITEM 0) itemoff 3450 itemsize 222
>>                  refs 23 gen 10 flags TREE_BLOCK
>>                  tree block skinny level 0
>>                  tree block backref root 278
>>                  tree block backref root 277
>>                  tree block backref root 276
>>                  tree block backref root 275
>>                  tree block backref root 274
>>                  tree block backref root 273
>>                  tree block backref root 272
>>                  tree block backref root 271
>>                  tree block backref root 270
>>                  tree block backref root 269
>>                  tree block backref root 268
>>                  tree block backref root 267
>>                  tree block backref root 266
>>                  tree block backref root 265
>>                  tree block backref root 264
>>                  tree block backref root 263
>>                  tree block backref root 262
>>                  tree block backref root 261
>>                  tree block backref root 260
>>                  tree block backref root 259
>>                  tree block backref root 258
>>                  tree block backref root 257
>> =================================================================
>> In find_parent_nodes(), these refs's parents are 0, then __merge_refs
>> will merge refs to one ref. It causes only one root to be returned.
> 
> This is a pretty big problem, and it would cause qgroup verification
> code to cause false alerts.
> 
> So a new test case would do great help here.
> 
Let me think how to construct a test case a while.
If I remember correctly, the function is called rarely only
in check/lowmem check.
Check calls it in a very corner case.
As you know, extent check in lowmme is buggy which I'm try to fix.

>>
>> So, if both parents are 0, do not merge refs.
>>
>> Lowmem check calls find_parent_nodes frequently to decide whether.
>> check an extent buffer or not. These bug influences bytes accounting.
> 
> Although it looks good so far, and would fix the problem you found, but

Fixing another bug in lowmem, found it by accident.

> I strongly recommend to port kernel backref code to btrfs-progs here, as
> kernel backref code is more tested than btrfs-progs backref code.
> 
It's a fact. Seen backref.c in btrfs-progs, there are many useless codes
and confusing logicals.
I agree that port kernel backref code to btrfs-progs.

> I'm pretty sure we have more bugs in btrfs-progs backref, and I'm not a
> big fan of playing whac-a-mole here.
> 
>>
>> Signed-off-by: Su Yue <suy.fnst@cn.fujitsu.com>
>> ---
>>   backref.c | 2 ++
>>   1 file changed, 2 insertions(+)
>>
>> diff --git a/backref.c b/backref.c
>> index 51553c702187..daadb6299c79 100644
>> --- a/backref.c
>> +++ b/backref.c
>> @@ -507,6 +507,8 @@ static void __merge_refs(struct pref_state *prefstate, int mode)
>>   			} else {
>>   				if (ref1->parent != ref2->parent)
>>   					continue;
>> +				if (ref1->parent == 0)
>> +					continue;
> 
> It's better to put it above (ref1->parent != ref2->parent).
> As parent == 0 means we haven't resolve the parent bytenr yet, so can't
> be merged nor compared.

Ok, will do it in V2.

Thanks,
Su
> 
> Thanks,
> Qu
> 
>>   			}
>>   
>>   			eie = ref1->inode_list;
>>
> 

Re: [PATCH 1/3] btrfs-progs: remove comments about delayed ref in backref.c

[Su Yue]

On 04/24/2018 02:02 PM, Qu Wenruo wrote:
> 
> 
> On 2018年04月24日 13:52, Su Yue wrote:
>> There is no delayed ref in btrfs-progs, so remove related comments.
>>
> 
> Indeed.
> Delayed ref is only used to speed up extent tree modification with the
> cost of code complexity.
> 
Thanks for your explanation :).

> For btrfs-progs we don't need to worry about it at all.
> 
So I suggest to remove comments in progs.

Thanks,
Su

> Thanks,
> Qu
> 
>> Signed-off-by: Su Yue <suy.fnst@cn.fujitsu.com>
>> ---
>>   backref.c | 19 +++----------------
>>   1 file changed, 3 insertions(+), 16 deletions(-)
>>
>> diff --git a/backref.c b/backref.c
>> index 27309e07a1e9..c144dbf060f2 100644
>> --- a/backref.c
>> +++ b/backref.c
>> @@ -155,19 +155,6 @@ static void init_pref_state(struct pref_state *prefstate)
>>    * - if you cannot add the parent or a correct key, then we will look into the
>>    *   block later to set a correct key
>>    *
>> - * delayed refs
>> - * ============
>> - *        backref type | shared | indirect | shared | indirect
>> - * information         |   tree |     tree |   data |     data
>> - * --------------------+--------+----------+--------+----------
>> - *      parent logical |    y   |     -    |    -   |     -
>> - *      key to resolve |    -   |     y    |    y   |     y
>> - *  tree block logical |    -   |     -    |    -   |     -
>> - *  root for resolving |    y   |     y    |    y   |     y
>> - *
>> - * - column 1:       we've the parent -> done
>> - * - column 2, 3, 4: we use the key to find the parent
>> - *
>>    * on disk refs (inline or keyed)
>>    * ==============================
>>    *        backref type | shared | indirect | shared | indirect
>> @@ -735,9 +722,9 @@ static int __add_keyed_refs(struct btrfs_fs_info *fs_info,
>>   }
>>   
>>   /*
>> - * this adds all existing backrefs (inline backrefs, backrefs and delayed
>> - * refs) for the given bytenr to the refs list, merges duplicates and resolves
>> - * indirect refs to their parent bytenr.
>> + * this adds all existing backrefs (inline backrefs, backrefs for the given
>> + * bytenr to the refs list, merges duplicates and resolves indirect refs to
>> + * their parent bytenr.
>>    * When roots are found, they're added to the roots list
>>    *
>>    * FIXME some caching might speed things up
>>
> 

Re: [PATCH 3/3] btrfs-progs: do not merge tree block refs have different root_id

[Qu Wenruo]

[-- Attachment #1.1: Type: text/plain, Size: 4852 bytes --]



On 2018年04月24日 14:43, Su Yue wrote:
> 
> 
> On 04/24/2018 02:17 PM, Qu Wenruo wrote:
>>
>>
>> On 2018年04月24日 13:52, Su Yue wrote:
>>> For an extent item which contains many tree block backrefs, like
>>> ===============================================================
>>> In 020-extent-ref-cases/keyed_block_ref.img
>>>
>>> item 10 key (29470720 METADATA_ITEM 0) itemoff 3450 itemsize 222
>>>                  refs 23 gen 10 flags TREE_BLOCK
>>>                  tree block skinny level 0
>>>                  tree block backref root 278
>>>                  tree block backref root 277
>>>                  tree block backref root 276
>>>                  tree block backref root 275
>>>                  tree block backref root 274
>>>                  tree block backref root 273
>>>                  tree block backref root 272
>>>                  tree block backref root 271
>>>                  tree block backref root 270
>>>                  tree block backref root 269
>>>                  tree block backref root 268
>>>                  tree block backref root 267
>>>                  tree block backref root 266
>>>                  tree block backref root 265
>>>                  tree block backref root 264
>>>                  tree block backref root 263
>>>                  tree block backref root 262
>>>                  tree block backref root 261
>>>                  tree block backref root 260
>>>                  tree block backref root 259
>>>                  tree block backref root 258
>>>                  tree block backref root 257
>>> ===============================================================
>>> In find_parent_nodes(), these refs's parents are 0, then __merge_refs
>>> will merge refs to one ref. It causes only one root to be returned.
>>
>> This is a pretty big problem, and it would cause qgroup verification
>> code to cause false alerts.
>>
>> So a new test case would do great help here.
>>
> Let me think how to construct a test case a while.
> If I remember correctly, the function is called rarely only
> in check/lowmem check.
> Check calls it in a very corner case.
> As you know, extent check in lowmme is buggy which I'm try to fix.

I mean, if the problem is find_parent_nodes() can only return one root,
it would definitely cause problem for qgroup_verify_all() function, then
it should be pretty easy to craft a test image.

Thanks,
Qu

> 
>>>
>>> So, if both parents are 0, do not merge refs.
>>>
>>> Lowmem check calls find_parent_nodes frequently to decide whether.
>>> check an extent buffer or not. These bug influences bytes accounting.
>>
>> Although it looks good so far, and would fix the problem you found, but
> 
> Fixing another bug in lowmem, found it by accident.
> 
>> I strongly recommend to port kernel backref code to btrfs-progs here, as
>> kernel backref code is more tested than btrfs-progs backref code.
>>
> It's a fact. Seen backref.c in btrfs-progs, there are many useless codes
> and confusing logicals.
> I agree that port kernel backref code to btrfs-progs.
> 
>> I'm pretty sure we have more bugs in btrfs-progs backref, and I'm not a
>> big fan of playing whac-a-mole here.
>>
>>>
>>> Signed-off-by: Su Yue <suy.fnst@cn.fujitsu.com>
>>> ---
>>>   backref.c | 2 ++
>>>   1 file changed, 2 insertions(+)
>>>
>>> diff --git a/backref.c b/backref.c
>>> index 51553c702187..daadb6299c79 100644
>>> --- a/backref.c
>>> +++ b/backref.c
>>> @@ -507,6 +507,8 @@ static void __merge_refs(struct pref_state
>>> *prefstate, int mode)
>>>               } else {
>>>                   if (ref1->parent !=ef2->parent)
>>>                       continue;
>>> +                if (ref1->parent =0)
>>> +                    continue;
>>
>> It's better to put it above (ref1->parent !=ef2->parent).
>> As parent =0 means we haven't resolve the parent bytenr yet, so can't
>> be merged nor compared.
> 
> Ok, will do it in V2.
> 
> Thanks,
> Su
>>
>> Thanks,
>> Qu
>>
>>>               }
>>>                 eie =ef1->inode_list;
>>>
>>
> 
> 
> -- 
> To unsubscribe from this list: send the line "unsubscribe linux-btrfs" in
> the body of a message to majordomo@vger.kernel.org
> More majordomo info at  http://vger.kernel.org/majordomo-info.html


[-- Attachment #2: OpenPGP digital signature --]
[-- Type: application/pgp-signature, Size: 488 bytes --]

Re: [PATCH 1/3] btrfs-progs: remove comments about delayed ref in backref.c

[Qu Wenruo]

[-- Attachment #1.1: Type: text/plain, Size: 2834 bytes --]



On 2018年04月24日 14:48, Su Yue wrote:
> 
> 
> On 04/24/2018 02:02 PM, Qu Wenruo wrote:
>>
>>
>> On 2018年04月24日 13:52, Su Yue wrote:
>>> There is no delayed ref in btrfs-progs, so remove related comments.
>>>
>>
>> Indeed.
>> Delayed ref is only used to speed up extent tree modification with the
>> cost of code complexity.
>>
> Thanks for your explanation :).
> 
>> For btrfs-progs we don't need to worry about it at all.
>>
> So I suggest to remove comments in progs.

Yep, I totally agree with that.

Just forgot to add:

Reviewed-by: Qu Wenruo <wqu@suse.com>

Thanks,
Qu

> 
> Thanks,
> Su
> 
>> Thanks,
>> Qu
>>
>>> Signed-off-by: Su Yue <suy.fnst@cn.fujitsu.com>
>>> ---
>>>   backref.c | 19 +++----------------
>>>   1 file changed, 3 insertions(+), 16 deletions(-)
>>>
>>> diff --git a/backref.c b/backref.c
>>> index 27309e07a1e9..c144dbf060f2 100644
>>> --- a/backref.c
>>> +++ b/backref.c
>>> @@ -155,19 +155,6 @@ static void init_pref_state(struct pref_state
>>> *prefstate)
>>>    * - if you cannot add the parent or a correct key, then we will
>>> look into the
>>>    *   block later to set a correct key
>>>    *
>>> - * delayed refs
>>> - * ============
>>> - *        backref type | shared | indirect | shared | indirect
>>> - * information         |   tree |     tree |   data |     data
>>> - * --------------------+--------+----------+--------+----------
>>> - *      parent logical |    y   |     -    |    -   |     -
>>> - *      key to resolve |    -   |     y    |    y   |     y
>>> - *  tree block logical |    -   |     -    |    -   |     -
>>> - *  root for resolving |    y   |     y    |    y   |     y
>>> - *
>>> - * - column 1:       we've the parent -> done
>>> - * - column 2, 3, 4: we use the key to find the parent
>>> - *
>>>    * on disk refs (inline or keyed)
>>>    * ==============================
>>>    *        backref type | shared | indirect | shared | indirect
>>> @@ -735,9 +722,9 @@ static int __add_keyed_refs(struct btrfs_fs_info
>>> *fs_info,
>>>   }
>>>     /*
>>> - * this adds all existing backrefs (inline backrefs, backrefs and
>>> delayed
>>> - * refs) for the given bytenr to the refs list, merges duplicates
>>> and resolves
>>> - * indirect refs to their parent bytenr.
>>> + * this adds all existing backrefs (inline backrefs, backrefs for
>>> the given
>>> + * bytenr to the refs list, merges duplicates and resolves indirect
>>> refs to
>>> + * their parent bytenr.
>>>    * When roots are found, they're added to the roots list
>>>    *
>>>    * FIXME some caching might speed things up
>>>
>>
> 
> 


[-- Attachment #2: OpenPGP digital signature --]
[-- Type: application/pgp-signature, Size: 488 bytes --]

[PATCH V2] btrfs-progs: do not merge tree block refs have different root_id

[Su Yue]

For an extent item which contains many tree block backrefs, like
=================================================================
In 020-extent-ref-cases/keyed_block_ref.img

item 10 key (29470720 METADATA_ITEM 0) itemoff 3450 itemsize 222
                refs 23 gen 10 flags TREE_BLOCK
                tree block skinny level 0
                tree block backref root 278
                tree block backref root 277
                tree block backref root 276
                tree block backref root 275
                tree block backref root 274
                tree block backref root 273
                tree block backref root 272
                tree block backref root 271
                tree block backref root 270
                tree block backref root 269
                tree block backref root 268
                tree block backref root 267
                tree block backref root 266
                tree block backref root 265
                tree block backref root 264
                tree block backref root 263
                tree block backref root 262
                tree block backref root 261
                tree block backref root 260
                tree block backref root 259
                tree block backref root 258
                tree block backref root 257
=================================================================
In find_parent_nodes(), these refs's parents are 0, then __merge_refs
will merge refs to one ref. It causes only one root to be returned.

So, if both parents are 0, do not merge refs.

Lowmem check calls find_parent_nodes frequently to decide whether
check an extent buffer or not. The bug influences bytes accounting.

Signed-off-by: Su Yue <suy.fnst@cn.fujitsu.com>
---
Changelog:
v2:
  Put judgment of ref->parent above comparison.
  Add the comment.
  Fix typos.
---
 backref.c | 7 +++++++
 1 file changed, 7 insertions(+)

diff --git a/backref.c b/backref.c
index 51553c702187..d5772ec228c3 100644
--- a/backref.c
+++ b/backref.c
@@ -505,8 +505,15 @@ static void __merge_refs(struct pref_state *prefstate, int mode)
 				if (!ref_for_same_block(ref1, ref2))
 					continue;
 			} else {
+				/*
+				 * Parent == 0 means that the ref is tree block
+				 * backref or its parent is unresolved.
+				 */
+				if (!ref1->parent || !ref2->parent)
+					continue;
 				if (ref1->parent != ref2->parent)
 					continue;
+
 			}
 
 			eie = ref1->inode_list;
-- 
2.17.0

[PATCH V2.1] btrfs-progs: do not merge tree block refs have different root_id

[Su Yue]

For an extent item which contains many tree block backrefs, like
=================================================================
In 020-extent-ref-cases/keyed_block_ref.img

item 10 key (29470720 METADATA_ITEM 0) itemoff 3450 itemsize 222
                refs 23 gen 10 flags TREE_BLOCK
                tree block skinny level 0
                tree block backref root 278
                tree block backref root 277
                tree block backref root 276
                tree block backref root 275
                tree block backref root 274
                tree block backref root 273
                tree block backref root 272
                tree block backref root 271
                tree block backref root 270
                tree block backref root 269
                tree block backref root 268
                tree block backref root 267
                tree block backref root 266
                tree block backref root 265
                tree block backref root 264
                tree block backref root 263
                tree block backref root 262
                tree block backref root 261
                tree block backref root 260
                tree block backref root 259
                tree block backref root 258
                tree block backref root 257
=================================================================
In find_parent_nodes(), these refs's parents are 0, then __merge_refs
will merge refs to one ref. It causes only one root to be returned.

So, if both parents are 0, do not merge refs.

Lowmem check calls find_parent_nodes frequently to decide whether
check an extent buffer or not. The bug influences bytes accounting.

Signed-off-by: Su Yue <suy.fnst@cn.fujitsu.com>
---
Changelog:
v2:
  Put judgment of ref->parent above comparison.
  Add the comment.
  Fix typos.
v2.1:
  Remove the change of adding a new line.
---
 backref.c | 6 ++++++
 1 file changed, 6 insertions(+)

diff --git a/backref.c b/backref.c
index 51553c702187..23a394edfd02 100644
--- a/backref.c
+++ b/backref.c
@@ -505,6 +505,12 @@ static void __merge_refs(struct pref_state *prefstate, int mode)
 				if (!ref_for_same_block(ref1, ref2))
 					continue;
 			} else {
+				/*
+				 * Parent == 0 means that the ref is tree block
+				 * backref or its parent is unresolved.
+				 */
+				if (!ref1->parent || !ref2->parent)
+					continue;
 				if (ref1->parent != ref2->parent)
 					continue;
 			}
-- 
2.17.0

Re: [PATCH 3/3] btrfs-progs: do not merge tree block refs have different root_id

[Su Yue]

On 04/24/2018 02:50 PM, Qu Wenruo wrote:
> 
> 
> On 2018年04月24日 14:43, Su Yue wrote:
>>
>>
>> On 04/24/2018 02:17 PM, Qu Wenruo wrote:
>>>
>>>
>>> On 2018年04月24日 13:52, Su Yue wrote:
>>>> For an extent item which contains many tree block backrefs, like
>>>> ===============================================================
>>>> In 020-extent-ref-cases/keyed_block_ref.img
>>>>
>>>> item 10 key (29470720 METADATA_ITEM 0) itemoff 3450 itemsize 222
>>>>                   refs 23 gen 10 flags TREE_BLOCK
>>>>                   tree block skinny level 0
>>>>                   tree block backref root 278
>>>>                   tree block backref root 277
>>>>                   tree block backref root 276
>>>>                   tree block backref root 275
>>>>                   tree block backref root 274
>>>>                   tree block backref root 273
>>>>                   tree block backref root 272
>>>>                   tree block backref root 271
>>>>                   tree block backref root 270
>>>>                   tree block backref root 269
>>>>                   tree block backref root 268
>>>>                   tree block backref root 267
>>>>                   tree block backref root 266
>>>>                   tree block backref root 265
>>>>                   tree block backref root 264
>>>>                   tree block backref root 263
>>>>                   tree block backref root 262
>>>>                   tree block backref root 261
>>>>                   tree block backref root 260
>>>>                   tree block backref root 259
>>>>                   tree block backref root 258
>>>>                   tree block backref root 257
>>>> ===============================================================
>>>> In find_parent_nodes(), these refs's parents are 0, then __merge_refs
>>>> will merge refs to one ref. It causes only one root to be returned.
>>>
>>> This is a pretty big problem, and it would cause qgroup verification
>>> code to cause false alerts.
>>>
>>> So a new test case would do great help here.
>>>
>> Let me think how to construct a test case a while.
>> If I remember correctly, the function is called rarely only
>> in check/lowmem check.
>> Check calls it in a very corner case.
>> As you know, extent check in lowmme is buggy which I'm try to fix.
> 
> I mean, if the problem is find_parent_nodes() can only return one root,
> it would definitely cause problem for qgroup_verify_all() function, then
> it should be pretty easy to craft a test image.
> 

Unfortunately, qgroup_verify_all() uses another version
find_parent_roots() written by itself own.
The test case is hard to create.

The best solution still is porting codes from kernel to btrfs-progs.
But the work needs some time to do.
The v2.1 version of this patch is temporary fix at present.

Thanks,
Su
> Thanks,
> Qu
> 
>>
>>>>
>>>> So, if both parents are 0, do not merge refs.
>>>>
>>>> Lowmem check calls find_parent_nodes frequently to decide whether.
>>>> check an extent buffer or not. These bug influences bytes accounting.
>>>
>>> Although it looks good so far, and would fix the problem you found, but
>>
>> Fixing another bug in lowmem, found it by accident.
>>
>>> I strongly recommend to port kernel backref code to btrfs-progs here, as
>>> kernel backref code is more tested than btrfs-progs backref code.
>>>
>> It's a fact. Seen backref.c in btrfs-progs, there are many useless codes
>> and confusing logicals.
>> I agree that port kernel backref code to btrfs-progs.
>>
>>> I'm pretty sure we have more bugs in btrfs-progs backref, and I'm not a
>>> big fan of playing whac-a-mole here.
>>>
>>>>
>>>> Signed-off-by: Su Yue <suy.fnst@cn.fujitsu.com>
>>>> ---
>>>>    backref.c | 2 ++
>>>>    1 file changed, 2 insertions(+)
>>>>
>>>> diff --git a/backref.c b/backref.c
>>>> index 51553c702187..daadb6299c79 100644
>>>> --- a/backref.c
>>>> +++ b/backref.c
>>>> @@ -507,6 +507,8 @@ static void __merge_refs(struct pref_state
>>>> *prefstate, int mode)
>>>>                } else {
>>>>                    if (ref1->parent !=ef2->parent)
>>>>                        continue;
>>>> +                if (ref1->parent =0)
>>>> +                    continue;
>>>
>>> It's better to put it above (ref1->parent !=ef2->parent).
>>> As parent =0 means we haven't resolve the parent bytenr yet, so can't
>>> be merged nor compared.
>>
>> Ok, will do it in V2.
>>
>> Thanks,
>> Su
>>>
>>> Thanks,
>>> Qu
>>>
>>>>                }
>>>>                  eie =ef1->inode_list;
>>>>
>>>
>>
>>
>> -- 
>> To unsubscribe from this list: send the line "unsubscribe linux-btrfs" in
>> the body of a message to majordomo@vger.kernel.org
>> More majordomo info at  http://vger.kernel.org/majordomo-info.html
> 

Re: [PATCH V2.1] btrfs-progs: do not merge tree block refs have different root_id

[Qu Wenruo]

[-- Attachment #1.1: Type: text/plain, Size: 2831 bytes --]



On 2018年04月25日 13:19, Su Yue wrote:
> For an extent item which contains many tree block backrefs, like
> =================================================================
> In 020-extent-ref-cases/keyed_block_ref.img
> 
> item 10 key (29470720 METADATA_ITEM 0) itemoff 3450 itemsize 222
>                 refs 23 gen 10 flags TREE_BLOCK
>                 tree block skinny level 0
>                 tree block backref root 278
>                 tree block backref root 277
>                 tree block backref root 276
>                 tree block backref root 275
>                 tree block backref root 274
>                 tree block backref root 273
>                 tree block backref root 272
>                 tree block backref root 271
>                 tree block backref root 270
>                 tree block backref root 269
>                 tree block backref root 268
>                 tree block backref root 267
>                 tree block backref root 266
>                 tree block backref root 265
>                 tree block backref root 264
>                 tree block backref root 263
>                 tree block backref root 262
>                 tree block backref root 261
>                 tree block backref root 260
>                 tree block backref root 259
>                 tree block backref root 258
>                 tree block backref root 257
> =================================================================
> In find_parent_nodes(), these refs's parents are 0, then __merge_refs
> will merge refs to one ref. It causes only one root to be returned.
> 
> So, if both parents are 0, do not merge refs.
> 
> Lowmem check calls find_parent_nodes frequently to decide whether
> check an extent buffer or not. The bug influences bytes accounting.
> 
> Signed-off-by: Su Yue <suy.fnst@cn.fujitsu.com>

Reviewed-by: Qu Wenruo <wqu@suse.com>

Waiting for the kernel port of backref.c to solve the problem permanently.

Thanks,
Qu

> ---
> Changelog:
> v2:
>   Put judgment of ref->parent above comparison.
>   Add the comment.
>   Fix typos.
> v2.1:
>   Remove the change of adding a new line.
> ---
>  backref.c | 6 ++++++
>  1 file changed, 6 insertions(+)
> 
> diff --git a/backref.c b/backref.c
> index 51553c702187..23a394edfd02 100644
> --- a/backref.c
> +++ b/backref.c
> @@ -505,6 +505,12 @@ static void __merge_refs(struct pref_state *prefstate, int mode)
>  				if (!ref_for_same_block(ref1, ref2))
>  					continue;
>  			} else {
> +				/*
> +				 * Parent == 0 means that the ref is tree block
> +				 * backref or its parent is unresolved.
> +				 */
> +				if (!ref1->parent || !ref2->parent)
> +					continue;
>  				if (ref1->parent != ref2->parent)
>  					continue;
>  			}
> 


[-- Attachment #2: OpenPGP digital signature --]
[-- Type: application/pgp-signature, Size: 488 bytes --]

Re: [PATCH 1/3] btrfs-progs: remove comments about delayed ref in backref.c

[David Sterba]

On Tue, Apr 24, 2018 at 01:52:31PM +0800, Su Yue wrote:
> There is no delayed ref in btrfs-progs, so remove related comments.
> 
> Signed-off-by: Su Yue <suy.fnst@cn.fujitsu.com>

1-3 applied. Please send cover letter for patch series with more than 1
patch.