Skip to contentSkip to conversation

fs: btrfs: fix false negatives in ROOT_ITEM search

PATCH In review Pierre Bourdon 2 participants 6 messages Apr 13, 2019 – Apr 27, 2019 Btrfs file system

lore
Share & tools
lore
#0 lore raw

PATCH 1/1 fs: btrfs: fix false negatives in ROOT_ITEM search

ROOT_ITEMs in btrfs are referenced without knowing their actual "offset" value. To perform these searches using only two items from the key, the btrfs driver uses a special "btrfs_search_tree_key_type" function.

The algorithm used by that function to transform a 3-tuple search into a 2-tuple search was subtly broken, leading to items not being found if they were the first in their tree node.

This commit fixes btrfs_search_tree_key_type to properly behave in these situations.

---
 fs/btrfs/ctree.h | 44 ++++++++++++++++++++++++++++++++++++++------
 1 file changed, 38 insertions(+), 6 deletions(-)
fs/btrfs/ctree.h +38 -6
index 65c152a52f..ca44a2404d 100644
@@ -292,20 +292,52 @@ btrfs_search_tree_key_type(const struct btrfs_root *root, u64 objectid,
 {
 	struct btrfs_key key, *res;
 
+	/*
+	 * In some cases (e.g. tree roots), we need to look for a given
+	 * objectid and type without knowing the offset value (3rd element of a
+	 * btrfs tree node key). We can rely on the fact that btrfs_search_tree
+	 * returns the first element with key >= search_key, and then perform
+	 * our own comparison between the returned element and the search key.
+	 *
+	 * It is tempting to use a search key with offset 0 to perform this
+	 * "fuzzy search". This would return the first item with the (objectid,
+	 * type) we're looking for. However, using offset 0 has the wrong
+	 * behavior when the wanted item is the first in a leaf: since our
+	 * search key will be lower than the wanted item, the recursive search
+	 * will explore the wrong branch of the tree.
+	 *
+	 * Instead, use the largest possible offset (-1). The result of this
+	 * search will either be:
+	 *   1. An element with the (objectid, type) we're looking for, if it
+	 *      has offset -1 or if it is the last element in its leaf.
+	 *   2. The first element *after* an element with the (objectid, type)
+	 */
 	key.objectid = objectid;
 	key.type = type;
-	key.offset = 0;
+	key.offset = -1;
 
 	if (btrfs_search_tree(root, &key, path))
 		return NULL;
 
-	res = btrfs_path_leaf_key(path);
-	if (btrfs_comp_keys_type(&key, res)) {
-		btrfs_free_path(path);
-		return NULL;
+	/*
+	 * Compare with the previous element first -- this is the likely case
+	 * since the result of the search is only what we want if it had offset
+	 * == -1 or if it was last in its leaf.
+	 */
+	if (path->slots[0] > 0) {
+		path->slots[0]--;
+		res = btrfs_path_leaf_key(path);
+		if (!btrfs_comp_keys_type(&key, res))
+			return res;
+		path->slots[0]++;
 	}
 
-	return res;
+	res = btrfs_path_leaf_key(path);
+	if (!btrfs_comp_keys_type(&key, res))
+		return res;
+
+	btrfs_free_path(path);
+	return NULL;
 }
 
 static inline u32 btrfs_path_item_size(struct btrfs_path *p)
Signature · 1 line
2.19.2
#1 lore raw

PATCH 1/1 fs: btrfs: fix false negatives in ROOT_ITEM search

Quoted 11 lines · Pierre Bourdon

ROOT_ITEMs in btrfs are referenced without knowing their actual "offset" value. To perform these searches using only two items from the key, the btrfs driver uses a special "btrfs_search_tree_key_type" function.

The algorithm used by that function to transform a 3-tuple search into a 2-tuple search was subtly broken, leading to items not being found if they were the first in their tree node.

This commit fixes btrfs_search_tree_key_type to properly behave in these situations.

A more practical example in case the explanation isn't clear:

root tree
node 122216448 level 1 items 6 free 115 generation 12246 owner ROOT_TREE fs uuid b516974e-a94e-469c-a9ff-d237ce96b03b
chunk uuid ecfa1e4e-8832-49c1-bb0c-2f08b95586a0

        key (EXTENT_TREE ROOT_ITEM 0) block 122810368 gen 12246
        key (ROOT_TREE_DIR INODE_REF 6) block 122339328 gen 12246
        key (344 ROOT_ITEM 9422) block 209317888 gen 12115
        key (344 ROOT_BACKREF 5) block 226222080 gen 12126
        key (368 ROOT_ITEM 11665) block 114966528 gen 12127
        key (375 ROOT_ITEM 12127) block 122949632 gen 12246

If you look for (375 ROOT_ITEM) then using (375 ROOT_ITEM 0) as the search key will end up walking to block 114966528 (because (375 ROOT_ITEM 0) < (375 ROOT_ITEM 12127)). Using instead (375 ROOT_ITEM -1) will go to the right leaf, return the first item after (375 ROOT_ITEM 12127), and we can then walk back one slot to get the item we wanted.

Signature · 3 lines
Pierre Bourdon <[email protected]>
Software Engineer @ Zürich, Switzerland
https://delroth.net/
#2 lore raw

PATCH 1/1 fs: btrfs: fix false negatives in ROOT_ITEM search

Quoted 13 lines · Pierre Bourdon

A more practical example in case the explanation isn't clear:

root tree
node 122216448 level 1 items 6 free 115 generation 12246 owner ROOT_TREE fs uuid b516974e-a94e-469c-a9ff-d237ce96b03b
chunk uuid ecfa1e4e-8832-49c1-bb0c-2f08b95586a0

        key (EXTENT_TREE ROOT_ITEM 0) block 122810368 gen 12246
        key (ROOT_TREE_DIR INODE_REF 6) block 122339328 gen 12246
        key (344 ROOT_ITEM 9422) block 209317888 gen 12115
        key (344 ROOT_BACKREF 5) block 226222080 gen 12126
        key (368 ROOT_ITEM 11665) block 114966528 gen 12127
        key (375 ROOT_ITEM 12127) block 122949632 gen 12246
Quoted 6 lines

If you look for (375 ROOT_ITEM) then using (375 ROOT_ITEM 0) as the search key will end up walking to block 114966528 (because (375 ROOT_ITEM 0) < (375 ROOT_ITEM 12127)). Using instead (375 ROOT_ITEM -1) will go to the right leaf, return the first item after (375 ROOT_ITEM 12127), and we can then walk back one slot to get the item we wanted.

So turns out there's a very similar bug when iterating DIR_INDEX entries -- but that one isn't using btrfs_search_tree_key_type. It's doing its own thing with offset = 0 to enumerate multiple items of the same oid/type.

Looking back at this, I think there's a much better way to fix both issues. Currently, btrfs_search_tree will return an invalid path if it's asked to look for an item between end of leaf N and beginning of leaf N+1. Invalid, as in, accessing the element at this path reads past the end of an array... This seems like a very broken behavior given that callers have no way of knowing the path is invalid without dereferencing it.

Instead, btrfs_search_tree should be fixed so that it always returns either:
1. The first element >= searched element.
2. An error if no such element exists.

This can be done with a fairly trivial change to btrfs_search_tree: if we're about to return something that's past the end of the leaf (slot

Quoted 1 line

= nritems), call btrfs_next_slot on the path. If btrfs_next_slot

works return that, otherwise return an error.

I'll send another patch which implements that instead. I've verified it fixes both the root lookup issue I was originally looking for + the DIR_INDEX issue as well. Please disregard the patch I originally sent.

--
Pierre Bourdon <[email protected]>
Software Engineer @ Zürich, Switzerland
https://delroth.net/

#3 lore raw
In reply to Pierre Bourdon
Quoted 8 lines · Pierre Bourdon

ROOT_ITEMs in btrfs are referenced without knowing their actual "offset" value. To perform these searches using only two items from the key, the btrfs driver uses a special "btrfs_search_tree_key_type" function.

The algorithm used by that function to transform a 3-tuple search into a 2-tuple search was subtly broken, leading to items not being found if they were the first in their tree node.

Quoted 5 lines

This commit fixes btrfs_search_tree_key_type to properly behave in these situations.

Applied to u-boot/master, thanks!

Signature · 8 lines
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/20190427/a5fefc5e/attachment.sig>
#4 lore raw

Hi Tom,

Quoted 9 lines · Tom Rini
Quoted 8 lines · Pierre Bourdon

ROOT_ITEMs in btrfs are referenced without knowing their actual "offset" value. To perform these searches using only two items from the key, the btrfs driver uses a special "btrfs_search_tree_key_type" function.

The algorithm used by that function to transform a 3-tuple search into a 2-tuple search was subtly broken, leading to items not being found if they were the first in their tree node.

Quoted 7 lines
Quoted 5 lines

This commit fixes btrfs_search_tree_key_type to properly behave in these situations.

Applied to u-boot/master, thanks!

Please disregard this patch as was mentioned in a followup email on the thread.

https://patchwork.ozlabs.org/patch/1085991/ implements a better way of addressing the problem and fixes a 2nd btrfs bug that was missed in this first revision.

Sorry for the mixup,
Best,

--
Pierre Bourdon <[email protected]>
Software Engineer @ Zürich, Switzerland
https://delroth.net/

#5 lore raw
Quoted 20 lines · Pierre Bourdon

Hi Tom,

Quoted 9 lines · Tom Rini
Quoted 8 lines · Pierre Bourdon

ROOT_ITEMs in btrfs are referenced without knowing their actual "offset" value. To perform these searches using only two items from the key, the btrfs driver uses a special "btrfs_search_tree_key_type" function.

The algorithm used by that function to transform a 3-tuple search into a 2-tuple search was subtly broken, leading to items not being found if they were the first in their tree node.

Quoted 7 lines
Quoted 5 lines

This commit fixes btrfs_search_tree_key_type to properly behave in these situations.

Applied to u-boot/master, thanks!

Quoted 7 lines

Please disregard this patch as was mentioned in a followup email on the thread.

https://patchwork.ozlabs.org/patch/1085991/ implements a better way of addressing the problem and fixes a 2nd btrfs bug that was missed in this first revision.

Sorry for the mixup,

OK, I'll take care of things, thanks!

Signature · 8 lines
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/20190427/21e9e704/attachment.sig>