Skip to contentSkip to conversation

btrfs: Open code key_search

PATCH In review Nikolay Borisov 3 participants 6 messages May 27, 2020 Btrfs file system

lore
Share & tools
lore
#0 lore raw

PATCH 1/1 btrfs: Open code key_search

This function wraps the optimisation implemented by d7396f07358a, however this optimisation is really used in only one place - btrfs_search_slot. Just open code the optimisation and also add a comment explaining how it works since it's not clear just by looking at the code - the key point here is it depends on an internal invariant that BTRFS' btree provides, namely intermediate pointers always contain the key at slot0 at the child node. So in the case of exact match we can safely assume that the given key will always be in slot 0 on lower levels.

Furthermore this results in a reduction of btrfs_search_slot's size:

./scripts/bloat-o-meter ctree.orig fs/btrfs/ctree.o add/remove: 0/0 grow/shrink: 0/1 up/down: 0/-75 (-75)
Function old new delta
btrfs_search_slot 2783 2708 -75
Total: Before=50423, After=50348, chg -0.15%

---
 fs/btrfs/ctree.c | 41 ++++++++++++++++++-----------------------
 1 file changed, 18 insertions(+), 23 deletions(-)
fs/btrfs/ctree.c +18 -23
index 92775554d1cc..3ab307b4b294 100644
@@ -2488,19 +2488,6 @@ setup_nodes_for_search(struct btrfs_trans_handle *trans,
 	return ret;
 }
 
-static int key_search(struct extent_buffer *b, const struct btrfs_key *key,
-		      int *prev_cmp, int *slot)
-{
-	if (*prev_cmp != 0) {
-		*prev_cmp = btrfs_bin_search(b, key, slot);
-		return *prev_cmp;
-	}
-
-	*slot = 0;
-
-	return 0;
-}
-
 int btrfs_find_item(struct btrfs_root *fs_root, struct btrfs_path *path,
 		u64 iobjectid, u64 ioff, u8 key_type,
 		struct btrfs_key *found_key)
@@ -2770,9 +2757,23 @@ int btrfs_search_slot(struct btrfs_trans_handle *trans, struct btrfs_root *root,
 			}
 		}
 
-		ret = key_search(b, key, &prev_cmp, &slot);
-		if (ret < 0)
-			goto done;
+		/*
+		 * If btrfs_bin_search returns an exact match (prev_cmp == 0)
+		 * we can safely assume the target key will always be in
+		 * slot 0 on lower levels due to the invariants BTRFS' btree
+		 * provides, namely that a btrfs_key_ptr entry always points
+		 * to the lowest key in the child node, thus we can skip
+		 * searching lower levels
+		 */
+		if (prev_cmp == 0) {
+			slot = 0;
+			ret = 0;
+		} else {
+			ret = btrfs_bin_search(b, key, &slot);
+			prev_cmp = ret;
+			if (ret < 0)
+				goto done;
+		}
 
 		if (level == 0) {
 			p->slots[level] = slot;
@@ -2896,7 +2897,6 @@ int btrfs_search_old_slot(struct btrfs_root *root, const struct btrfs_key *key,
 	int level;
 	int lowest_unlock = 1;
 	u8 lowest_level = 0;
-	int prev_cmp = -1;
 
 	lowest_level = p->lowest_level;
 	WARN_ON(p->nodes[0] != NULL);
@@ -2929,12 +2929,7 @@ int btrfs_search_old_slot(struct btrfs_root *root, const struct btrfs_key *key,
 		 */
 		btrfs_unlock_up_safe(p, level + 1);
 
-		/*
-		 * Since we can unwind ebs we want to do a real search every
-		 * time.
-		 */
-		prev_cmp = -1;
-		ret = key_search(b, key, &prev_cmp, &slot);
+		ret = btrfs_bin_search(b, key, &slot);
 		if (ret < 0)
 			goto done;
 

--
2.17.1

Reviewed-by on v1 1/1
#1 lore raw

On 27/05/2020 12:11, Nikolay Borisov wrote:

Looks good,

One nit though:

fs/btrfs/ctree.c int btrfs_search_slot(struct btrfs_trans_handle *trans, struct btrfs_root *root, · line 2773

Quoted 2 lines
fs/btrfs/ctree.c +2 -0
+			ret = btrfs_bin_search(b, key, &slot);
+			prev_cmp = ret;

I actually find:

			ret = prev_cmp = brtfs_bin_search(b, key, &slot);

a bit more readable in this case.

#2 lore raw
Quoted 7 lines · Johannes Thumshirn

On 27/05/2020 12:11, Nikolay Borisov wrote:

Looks good,

One nit though:

Quoted 8 lines

fs/btrfs/ctree.c int btrfs_search_slot(struct btrfs_trans_handle *trans, struct btrfs_root *root, · line 2773

Quoted 2 lines
fs/btrfs/ctree.c +2 -0
+			ret = btrfs_bin_search(b, key, &slot);
+			prev_cmp = ret;

I actually find:

			ret = prev_cmp = brtfs_bin_search(b, key, &slot);

a bit more readable in this case.

True, AFAIK David is not a fan of multiple assignments on the same line ;)

#3 lore raw
Quoted 1 line · Nikolay Borisov

True, AFAIK David is not a fan of multiple assignments on the same line ;)

Yes I remember him saying something like this.

#4 lore raw
Quoted 4 lines · Johannes Thumshirn
Quoted 1 line · Nikolay Borisov

True, AFAIK David is not a fan of multiple assignments on the same line ;)

Yes I remember him saying something like this.

I can point you to the kernel coding style any number of times:

https://www.kernel.org/doc/html/latest/process/coding-style.html#indentation

"Don’t put multiple assignments on a single line either. Kernel coding
style is super simple. Avoid tricky expressions."

#5 lore raw
In reply to Nikolay Borisov
Quoted 12 lines · Nikolay Borisov

This function wraps the optimisation implemented by d7396f07358a, however this optimisation is really used in only one place - btrfs_search_slot. Just open code the optimisation and also add a comment explaining how it works since it's not clear just by looking at the code - the key point here is it depends on an internal invariant that BTRFS' btree provides, namely intermediate pointers always contain the key at slot0 at the child node. So in the case of exact match we can safely assume that the given key will always be in slot 0 on lower levels.

Furthermore this results in a reduction of btrfs_search_slot's size:

Quoted 7 lines

./scripts/bloat-o-meter ctree.orig fs/btrfs/ctree.o add/remove: 0/0 grow/shrink: 0/1 up/down: 0/-75 (-75)
Function old new delta
btrfs_search_slot 2783 2708 -75
Total: Before=50423, After=50348, chg -0.15%

Added to misc-next, thanks.