Merge branch '2019-04-27-master-imports'

- Various vexpress, taurus, da850evm, lpc32xx, brxre1 fixes/updates
- btrfs fixes
- Add AM65x HS EVM
- Other small fixes

2 files changed, 50 insertions, 8 deletions

diff --git a/fs/btrfs/ctree.c b/fs/btrfs/ctree.c
index d248d79932..7fae383f15 100644
--- a/fs/btrfs/ctree.c
+++ b/fs/btrfs/ctree.c
@@ -185,10 +185,20 @@ int btrfs_search_tree(const struct btrfs_root *root, struct btrfs_key *key,
 		p->slots[lvl] = slot;
 		p->nodes[lvl] = buf;
 
-		if (lvl)
+		if (lvl) {
 			logical = buf->node.ptrs[slot].blockptr;
-		else
+		} else {
+			/*
+			 * The path might be invalid if:
+			 *   cur leaf max < searched value < next leaf min
+			 *
+			 * Jump to the next valid element if it exists.
+			 */
+			if (slot >= buf->header.nritems)
+				if (btrfs_next_slot(p) < 0)
+					goto err;
 			break;
+		}
 	}
 
 	return 0;
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)