summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorPierre Bourdon <delroth@gmail.com>2019-04-13 23:50:49 +0200
committerTom Rini <trini@konsulko.com>2019-04-26 17:53:15 -0400
commit633967f9818cb6a0e87ffa8cba33148a5bcc6edb (patch)
treed39538815561b60490eb32e5d394609090b7e69f
parent74ee9dc502de45bf44a8d5b94458ef12437085f4 (diff)
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. Signed-off-by: Pierre Bourdon <delroth@gmail.com> Cc: Marek Behun <marek.behun@nic.cz>
-rw-r--r--fs/btrfs/ctree.h44
1 files changed, 38 insertions, 6 deletions
diff --git a/fs/btrfs/ctree.h b/fs/btrfs/ctree.h
index 65c152a52f..ca44a2404d 100644
--- a/fs/btrfs/ctree.h
+++ b/fs/btrfs/ctree.h
@@ -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)