btrfs: fix for btrfs_prev_leaf() and unexport it
cover btrfs: fix for btrfs_prev_leaf() and unexport it
From: Filipe Manana <[email protected]>
A fix for btrfs_prev_leaf() where due to races with concurrent insertions, can return the same key again, and unexport it since it's not used outside ctree.c. More details on the individual changelogs.
Filipe Manana (2):
btrfs: fix btrfs_prev_leaf() to not return the same key twice
btrfs: unexport btrfs_prev_leaf()
fs/btrfs/ctree.c | 131 +++++++++++++++++++++++++++++------------------ fs/btrfs/ctree.h | 1 - 2 files changed, 81 insertions(+), 51 deletions(-)
Signature · 1 line
2.34.1
PATCH 1/2 btrfs: fix btrfs_prev_leaf() to not return the same key twice
From: Filipe Manana <[email protected]>
A call to btrfs_prev_leaf() may end up returning a path that points to the same item (key) again. This happens if while btrfs_prev_leaf(), after we release the path, a concurrent insertion happens, which moves items off from a sibbling into the front of the previous leaf, and an item with the computed previous key does not exists.
For example, suppose we have the two following leaves:
Leaf A
-------------------------------------------------------------
| ... key (300 96 10) key (300 96 15) key (300 96 16) |
-------------------------------------------------------------
slot 20 slot 21 slot 22
Leaf B
-------------------------------------------------------------
| key (300 96 20) key (300 96 21) key (300 96 22) ... |
-------------------------------------------------------------
slot 0 slot 1 slot 2
If we call btrfs_prev_leaf(), from btrfs_previous_item() for example, with a path pointing to leaf B and slot 0 and the following happens:
1) At btrfs_prev_leaf() we compute the previous key to search as:
(300 96 19), which is a key that does not exists in the tree;
2) Then we call btrfs_release_path() at btrfs_prev_leaf();
3) Some other task inserts a key at leaf A, that sorts before the key at slot 20, for example it has an objectid of 299. In order to make room for the new key, the key at slot 22 is moved to the front of leaf B. This happens at push_leaf_right(), called from split_leaf().
After this leaf B now looks like:
--------------------------------------------------------------------------------
| key (300 96 16) key (300 96 20) key (300 96 21) key (300 96 22) ... |
--------------------------------------------------------------------------------
slot 0 slot 1 slot 2 slot 3
4) At btrfs_prev_leaf() we call btrfs_search_slot() for the computed previous key: (300 96 19). Since the key does not exists, btrfs_search_slot() returns 1 and with a path pointing to leaf B and slot 1, the item with key (300 96 20);
5) This makes btrfs_prev_leaf() return a path that points to slot 1 of leaf B, the same key as before it was called, since the key at slot 0 of leaf B (300 96 16) is less than the computed previous key, which is (300 96 19);
6) As a consequence btrfs_previous_item() returns a path that points again to the item with key (300 96 20).
For some users of btrfs_prev_leaf() or btrfs_previous_item() this may not be functional a problem, despite not making sense to return a new path pointing again to the same item/key. However for a caller such as tree-log.c:log_dir_items(), this has a bad consequence, as it can result in not logging some dir index deletions in case the directory is being logged without holding the inode's VFS lock (logging triggered while logging a child inode for example) - for the example scenario above, in case the dir index keys 17, 18 and 19 were deleted in the current transaction.
--- fs/btrfs/ctree.c | 32 +++++++++++++++++++++++++++++++- 1 file changed, 31 insertions(+), 1 deletion(-)
fs/btrfs/ctree.c +31 -1
@@ -4478,10 +4478,12 @@ int btrfs_del_items(struct btrfs_trans_handle *trans, struct btrfs_root *root,int btrfs_prev_leaf (struct btrfs_root *root,struct btrfs_path *path) {struct btrfs_key key; +struct btrfs_key orig_key;struct btrfs_disk_key found_key;int ret;btrfs_item_key_to_cpu (path->nodes[0 ], &key,0 ); + orig_key = key;if (key.offset >0 ) { key.offset--;
@@ -4498,8 +4500,36 @@ int btrfs_prev_leaf(struct btrfs_root *root, struct btrfs_path *path)btrfs_release_path (path); ret =btrfs_search_slot (NULL , root, &key, path,0 ,0 ); -if (ret <0 ) +if (ret <=0 )return ret; + +/* +* Previous key not found. Even if we were at slot 0 of the leaf we had +* before releasing the path and calling btrfs_search_slot(), we now may +* be in a slot pointing to the same original key - this can happen if +* after we released the path, one of more items were moved from a +* sibbling leaf into the front of the leaf we had due to an insertion +* (see push_leaf_right()). +* If we hit this case and our slot is > 0 and just decrement the slot +* so that the caller does not process the same key again, which may or +* may not break the caller, depending on its logic. +*/ +if (path->slots[0 ] <btrfs_header_nritems (path->nodes[0 ])) { +btrfs_item_key (path->nodes[0 ], &found_key, path->slots[0 ]); + ret =comp_keys (&found_key, &orig_key); +if (ret ==0 ) { +if (path->slots[0 ] >0 ) { + path->slots[0 ]--; +return 0 ; + } +/* +* At slot 0, same key as before, it means orig_key is +* the lowest, leftmost, key in the tree. We're done. +*/ +return 1 ; + } + } +btrfs_item_key (path->nodes[0 ], &found_key,0 ); ret =comp_keys (&found_key, &key);/*
Signature · 1 line
2.34.1
Re: [PATCH 1/2] btrfs: fix btrfs_prev_leaf() to not return the same key twice
Hi,
Quoted 57 lines
From: Filipe Manana <[email protected]>
A call to
btrfs_prev_leaf()may end up returning a path that points to the same item (key) again. This happens if whilebtrfs_prev_leaf(), after we release the path, a concurrent insertion happens, which moves items off from a sibbling into the front of the previous leaf, and an item with the computed previous key does not exists.For example, suppose we have the two following leaves:
Leaf A
-------------------------------------------------------------
| ... key (300 96 10) key (300 96 15) key (300 96 16) |
-------------------------------------------------------------
slot 20 slot 21 slot 22Leaf B
-------------------------------------------------------------
| key (300 96 20) key (300 96 21) key (300 96 22) ... |
-------------------------------------------------------------
slot 0 slot 1 slot 2If we call
btrfs_prev_leaf(), frombtrfs_previous_item()for example, with a path pointing to leaf B and slot 0 and the following happens:1) At
btrfs_prev_leaf()we compute the previous key to search as:(300 96 19), which is a key that does not exists in the tree;2) Then we call
btrfs_release_path()atbtrfs_prev_leaf();3) Some other task inserts a key at leaf A, that sorts before the key at slot 20, for example it has an objectid of 299. In order to make room for the new key, the key at slot 22 is moved to the front of leaf B. This happens at
push_leaf_right(), called fromsplit_leaf().After this leaf B now looks like:
--------------------------------------------------------------------------------
| key (300 96 16) key (300 96 20) key (300 96 21) key (300 96 22) ... |
--------------------------------------------------------------------------------
slot 0 slot 1 slot 2 slot 34) At
btrfs_prev_leaf()we callbtrfs_search_slot()for the computed previous key: (300 96 19). Since the key does not exists,btrfs_search_slot()returns 1 and with a path pointing to leaf B and slot 1, the item with key (300 96 20);5) This makes
btrfs_prev_leaf()return a path that points to slot 1 of leaf B, the same key as before it was called, since the key at slot 0 of leaf B (300 96 16) is less than the computed previous key, which is (300 96 19);6) As a consequence
btrfs_previous_item()returns a path that points again to the item with key (300 96 20).
Quoted 9 lines
For some users of
btrfs_prev_leaf()orbtrfs_previous_item()this may not be functional a problem, despite not making sense to return a new path pointing again to the same item/key. However for a caller such as tree-log.c:log_dir_items(), this has a bad consequence, as it can result in not logging some dir index deletions in case the directory is being logged without holding the inode's VFS lock (logging triggered while logging a child inode for example) - for the example scenario above, in case the dir index keys 17, 18 and 19 were deleted in the current transaction.
fstests(btrfs/080) had few frequency(<1/10) to fail after this pacth is applied. but it is yet not clear enough.
# cat results//btrfs/080.out.bad QA output created by 080 Unexpected digest for file /mnt/scratch/20_40_30_986878191_snap/foobar_63 (see /usr/hpc-bio/xfstests/results//btrfs/080.full for details)
Best Regards
Wang Yugui ([email protected])
2023/04/14
Re: [PATCH 1/2] btrfs: fix btrfs_prev_leaf() to not return the same key twice
Hi,
Quoted 69 lines
Hi,
Quoted 57 lines
From: Filipe Manana <[email protected]>
A call to
btrfs_prev_leaf()may end up returning a path that points to the same item (key) again. This happens if whilebtrfs_prev_leaf(), after we release the path, a concurrent insertion happens, which moves items off from a sibbling into the front of the previous leaf, and an item with the computed previous key does not exists.For example, suppose we have the two following leaves:
Leaf A
-------------------------------------------------------------
| ... key (300 96 10) key (300 96 15) key (300 96 16) |
-------------------------------------------------------------
slot 20 slot 21 slot 22Leaf B
-------------------------------------------------------------
| key (300 96 20) key (300 96 21) key (300 96 22) ... |
-------------------------------------------------------------
slot 0 slot 1 slot 2If we call
btrfs_prev_leaf(), frombtrfs_previous_item()for example, with a path pointing to leaf B and slot 0 and the following happens:1) At
btrfs_prev_leaf()we compute the previous key to search as:(300 96 19), which is a key that does not exists in the tree;2) Then we call
btrfs_release_path()atbtrfs_prev_leaf();3) Some other task inserts a key at leaf A, that sorts before the key at slot 20, for example it has an objectid of 299. In order to make room for the new key, the key at slot 22 is moved to the front of leaf B. This happens at
push_leaf_right(), called fromsplit_leaf().After this leaf B now looks like:
--------------------------------------------------------------------------------
| key (300 96 16) key (300 96 20) key (300 96 21) key (300 96 22) ... |
--------------------------------------------------------------------------------
slot 0 slot 1 slot 2 slot 34) At
btrfs_prev_leaf()we callbtrfs_search_slot()for the computed previous key: (300 96 19). Since the key does not exists,btrfs_search_slot()returns 1 and with a path pointing to leaf B and slot 1, the item with key (300 96 20);5) This makes
btrfs_prev_leaf()return a path that points to slot 1 of leaf B, the same key as before it was called, since the key at slot 0 of leaf B (300 96 16) is less than the computed previous key, which is (300 96 19);6) As a consequence
btrfs_previous_item()returns a path that points again to the item with key (300 96 20).Quoted 9 lines
For some users of
btrfs_prev_leaf()orbtrfs_previous_item()this may not be functional a problem, despite not making sense to return a new path pointing again to the same item/key. However for a caller such as tree-log.c:log_dir_items(), this has a bad consequence, as it can result in not logging some dir index deletions in case the directory is being logged without holding the inode's VFS lock (logging triggered while logging a child inode for example) - for the example scenario above, in case the dir index keys 17, 18 and 19 were deleted in the current transaction.
Quoted 7 lines
fstests(btrfs/080) had few frequency(<1/10) to fail after this pacth is applied. but it is yet not clear enough.
# cat results//btrfs/080.out.bad QA output created by 080 Unexpected digest for file /mnt/scratch/20_40_30_986878191_snap/foobar_63 (see /usr/hpc-bio/xfstests/results//btrfs/080.full for details)
fstests(btrfs/080) failure happened without this patch too.
the next info update may take some long time, because of the low reproduce frequency.
Best Regards
Wang Yugui ([email protected])
2023/04/14
Re: [PATCH 1/2] btrfs: fix btrfs_prev_leaf() to not return the same key twice
Quoted 80 lines · Wang Yugui
Hi,
Quoted 69 lines
Hi,
Quoted 57 lines
From: Filipe Manana <[email protected]>
A call to
btrfs_prev_leaf()may end up returning a path that points to the same item (key) again. This happens if whilebtrfs_prev_leaf(), after we release the path, a concurrent insertion happens, which moves items off from a sibbling into the front of the previous leaf, and an item with the computed previous key does not exists.For example, suppose we have the two following leaves:
Leaf A
-------------------------------------------------------------
| ... key (300 96 10) key (300 96 15) key (300 96 16) |
-------------------------------------------------------------
slot 20 slot 21 slot 22Leaf B
-------------------------------------------------------------
| key (300 96 20) key (300 96 21) key (300 96 22) ... |
-------------------------------------------------------------
slot 0 slot 1 slot 2If we call
btrfs_prev_leaf(), frombtrfs_previous_item()for example, with a path pointing to leaf B and slot 0 and the following happens:1) At
btrfs_prev_leaf()we compute the previous key to search as:(300 96 19), which is a key that does not exists in the tree;2) Then we call
btrfs_release_path()atbtrfs_prev_leaf();3) Some other task inserts a key at leaf A, that sorts before the key at slot 20, for example it has an objectid of 299. In order to make room for the new key, the key at slot 22 is moved to the front of leaf B. This happens at
push_leaf_right(), called fromsplit_leaf().After this leaf B now looks like:
--------------------------------------------------------------------------------
| key (300 96 16) key (300 96 20) key (300 96 21) key (300 96 22) ... |
--------------------------------------------------------------------------------
slot 0 slot 1 slot 2 slot 34) At
btrfs_prev_leaf()we callbtrfs_search_slot()for the computed previous key: (300 96 19). Since the key does not exists,btrfs_search_slot()returns 1 and with a path pointing to leaf B and slot 1, the item with key (300 96 20);5) This makes
btrfs_prev_leaf()return a path that points to slot 1 of leaf B, the same key as before it was called, since the key at slot 0 of leaf B (300 96 16) is less than the computed previous key, which is (300 96 19);6) As a consequence
btrfs_previous_item()returns a path that points again to the item with key (300 96 20).Quoted 9 lines
For some users of
btrfs_prev_leaf()orbtrfs_previous_item()this may not be functional a problem, despite not making sense to return a new path pointing again to the same item/key. However for a caller such as tree-log.c:log_dir_items(), this has a bad consequence, as it can result in not logging some dir index deletions in case the directory is being logged without holding the inode's VFS lock (logging triggered while logging a child inode for example) - for the example scenario above, in case the dir index keys 17, 18 and 19 were deleted in the current transaction.Quoted 7 lines
fstests(btrfs/080) had few frequency(<1/10) to fail after this pacth is applied. but it is yet not clear enough.
# cat results//btrfs/080.out.bad QA output created by 080 Unexpected digest for file /mnt/scratch/20_40_30_986878191_snap/foobar_63 (see /usr/hpc-bio/xfstests/results//btrfs/080.full for details)
Quoted 4 lines
fstests(btrfs/080) failure happened without this patch too.
the next info update may take some long time, because of the low reproduce frequency.
That test sporadically fails without the patch yes.
Also, more important: the test does not exercise at all the function changed by this patch.
So you can save time and skip doing that pointless info update on frequency failure...
Thanks.
Quoted 6 lines
Best Regards
Wang Yugui ([email protected])
2023/04/14
PATCH 2/2 btrfs: unexport btrfs_prev_leaf()
In reply to [email protected]From: Filipe Manana <[email protected]>
btrfs_prev_leaf() is not used outside ctree.c, so there's no need to export it at ctree.h - just make it static at ctree.c and move its definition above btrfs_search_slot_for_read(), since that function calls it.
--- fs/btrfs/ctree.c | 161 ++++++++++++++++++++++++----------------------- fs/btrfs/ctree.h | 1 - 2 files changed, 81 insertions(+), 81 deletions(-)
fs/btrfs/ctree.c +81 -80
@@ -2378,6 +2378,87 @@ int btrfs_search_old_slot(struct btrfs_root *root, const struct btrfs_key *key,return ret; } +/* +* Search the tree again to find a leaf with smaller keys. +* Returns 0 if it found something. +* Returns 1 if there are no smaller keys. +* Returns < 0 on error. +* +* This may release the path, and so you may lose any locks held at the +* time you call it. +*/ +static int btrfs_prev_leaf (struct btrfs_root *root,struct btrfs_path *path) +{ +struct btrfs_key key; +struct btrfs_key orig_key; +struct btrfs_disk_key found_key; +int ret; + +btrfs_item_key_to_cpu (path->nodes[0 ], &key,0 ); + orig_key = key; + +if (key.offset >0 ) { + key.offset--; + }else if (key.type >0 ) { + key.type--; + key.offset = (u64)-1 ; + }else if (key.objectid >0 ) { + key.objectid--; + key.type = (u8)-1 ; + key.offset = (u64)-1 ; + }else { +return 1 ; + } + +btrfs_release_path (path); + ret =btrfs_search_slot (NULL , root, &key, path,0 ,0 ); +if (ret <=0 ) +return ret; + +/* +* Previous key not found. Even if we were at slot 0 of the leaf we had +* before releasing the path and calling btrfs_search_slot(), we now may +* be in a slot pointing to the same original key - this can happen if +* after we released the path, one of more items were moved from a +* sibbling leaf into the front of the leaf we had due to an insertion +* (see push_leaf_right()). +* If we hit this case and our slot is > 0 and just decrement the slot +* so that the caller does not process the same key again, which may or +* may not break the caller, depending on its logic. +*/ +if (path->slots[0 ] <btrfs_header_nritems (path->nodes[0 ])) { +btrfs_item_key (path->nodes[0 ], &found_key, path->slots[0 ]); + ret =comp_keys (&found_key, &orig_key); +if (ret ==0 ) { +if (path->slots[0 ] >0 ) { + path->slots[0 ]--; +return 0 ; + } +/* +* At slot 0, same key as before, it means orig_key is +* the lowest, leftmost, key in the tree. We're done. +*/ +return 1 ; + } + } + +btrfs_item_key (path->nodes[0 ], &found_key,0 ); + ret =comp_keys (&found_key, &key); +/* +* We might have had an item with the previous key in the tree right +* before we released our path. And after we released our path, that +* item might have been pushed to the first slot (0) of the leaf we +* were holding due to a tree balance. Alternatively, an item with the +* previous key can exist as the only element of a leaf (big fat item). +* Therefore account for these 2 cases, so that our callers (like +* btrfs_previous_item) don't miss an existing item with a key matching +* the previous key we computed above. +*/ +if (ret <=0 ) +return 0 ; +return 1 ; +} +/* * helper to use instead of search slot if no exact match is needed but * instead the next or previous item should be returned.
@@ -4467,86 +4548,6 @@ int btrfs_del_items(struct btrfs_trans_handle *trans, struct btrfs_root *root,return ret; } -/* -* search the tree again to find a leaf with lesser keys -* returns 0 if it found something or 1 if there are no lesser leaves. -* returns < 0 on io errors. -* -* This may release the path, and so you may lose any locks held at the -* time you call it. -*/ -int btrfs_prev_leaf (struct btrfs_root *root,struct btrfs_path *path) -{ -struct btrfs_key key; -struct btrfs_key orig_key; -struct btrfs_disk_key found_key; -int ret; - -btrfs_item_key_to_cpu (path->nodes[0 ], &key,0 ); - orig_key = key; - -if (key.offset >0 ) { - key.offset--; - }else if (key.type >0 ) { - key.type--; - key.offset = (u64)-1 ; - }else if (key.objectid >0 ) { - key.objectid--; - key.type = (u8)-1 ; - key.offset = (u64)-1 ; - }else { -return 1 ; - } - -btrfs_release_path (path); - ret =btrfs_search_slot (NULL , root, &key, path,0 ,0 ); -if (ret <=0 ) -return ret; - -/* -* Previous key not found. Even if we were at slot 0 of the leaf we had -* before releasing the path and calling btrfs_search_slot(), we now may -* be in a slot pointing to the same original key - this can happen if -* after we released the path, one of more items were moved from a -* sibbling leaf into the front of the leaf we had due to an insertion -* (see push_leaf_right()). -* If we hit this case and our slot is > 0 and just decrement the slot -* so that the caller does not process the same key again, which may or -* may not break the caller, depending on its logic. -*/ -if (path->slots[0 ] <btrfs_header_nritems (path->nodes[0 ])) { -btrfs_item_key (path->nodes[0 ], &found_key, path->slots[0 ]); - ret =comp_keys (&found_key, &orig_key); -if (ret ==0 ) { -if (path->slots[0 ] >0 ) { - path->slots[0 ]--; -return 0 ; - } -/* -* At slot 0, same key as before, it means orig_key is -* the lowest, leftmost, key in the tree. We're done. -*/ -return 1 ; - } - } - -btrfs_item_key (path->nodes[0 ], &found_key,0 ); - ret =comp_keys (&found_key, &key); -/* -* We might have had an item with the previous key in the tree right -* before we released our path. And after we released our path, that -* item might have been pushed to the first slot (0) of the leaf we -* were holding due to a tree balance. Alternatively, an item with the -* previous key can exist as the only element of a leaf (big fat item). -* Therefore account for these 2 cases, so that our callers (like -* btrfs_previous_item) don't miss an existing item with a key matching -* the previous key we computed above. -*/ -if (ret <=0 ) -return 0 ; -return 1 ; -} -/* * A helper function to walk down the tree starting at min_key, and looking * for nodes or leaves that are have a minimum transaction id.
fs/btrfs/ctree.h +0 -1
@@ -633,7 +633,6 @@ static inline int btrfs_insert_empty_item(struct btrfs_trans_handle *trans,return btrfs_insert_empty_items (trans, root, path, &batch); } -int btrfs_prev_leaf (struct btrfs_root *root,struct btrfs_path *path);int btrfs_next_old_leaf (struct btrfs_root *root,struct btrfs_path *path,u64 time_seq);
Signature · 1 line
2.34.1
Re: [PATCH 2/2] btrfs: unexport btrfs_prev_leaf()
Quoted 8 lines · On 12/4/23 18:33, [email protected] wrote:
From: Filipe Manana <[email protected]>
btrfs_prev_leaf()is not used outsidectree.c, so there's no need to export it atctree.h- just make it static atctree.cand move its definition abovebtrfs_search_slot_for_read(), since that function calls it.Signed-off-by Filipe Manana <[email protected]>
LGTM
Quoted 6 lines · On Wed, Apr 12, 2023 at 11:33:08AM +0100, [email protected] wrote:
From: Filipe Manana <[email protected]>
A fix for
btrfs_prev_leaf()where due to races with concurrent insertions, can return the same key again, and unexport it since it's not used outsidectree.c. More details on the individual changelogs.
Quoted 8 lines
Filipe Manana (2):
btrfs: fixbtrfs_prev_leaf()to not return the same key twice
btrfs: unexportbtrfs_prev_leaf()fs/btrfs/ctree.c | 131 +++++++++++++++++++++++++++++------------------ fs/btrfs/ctree.h | 1 - 2 files changed, 81 insertions(+), 51 deletions(-)
Thanks,
Josef
Quoted 9 lines · On Wed, Apr 12, 2023 at 11:33:08AM +0100, [email protected] wrote:
From: Filipe Manana <[email protected]>
A fix for
btrfs_prev_leaf()where due to races with concurrent insertions, can return the same key again, and unexport it since it's not used outsidectree.c. More details on the individual changelogs.Filipe Manana (2):
btrfs: fixbtrfs_prev_leaf()to not return the same key twice
btrfs: unexportbtrfs_prev_leaf()
Added to misc-next, thanks.