bcachefs: improved rw_aux_tree_bsearch()

shouldn't be any reason for an actual binary search here

Signed-off-by: Kent Overstreet <kent.overstreet@linux.dev>

2 files changed, 24 insertions, 21 deletions

diff --git a/fs/bcachefs/bset.c b/fs/bcachefs/bset.c
index faf58b4c0eb4..a74e93a7215c 100644
--- a/fs/bcachefs/bset.c
+++ b/fs/bcachefs/bset.c
@@ -614,28 +614,30 @@ static unsigned rw_aux_tree_bsearch(struct btree *b,
 				    struct bset_tree *t,
 				    unsigned offset)
 {
-	unsigned l = 0, r = t->size;
+	unsigned bset_offs = offset - btree_bkey_first_offset(t);
+	unsigned bset_u64s = t->end_offset - btree_bkey_first_offset(t);
+	unsigned idx = bset_u64s ? bset_offs * t->size / bset_u64s : 0;
 
 	EBUG_ON(bset_aux_tree_type(t) != BSET_RW_AUX_TREE);
+	EBUG_ON(!t->size);
+	EBUG_ON(idx > t->size);
 
-	while (l < r) {
-		unsigned m = (l + r) >> 1;
+	while (idx < t->size &&
+	       rw_aux_tree(b, t)[idx].offset < offset)
+		idx++;
 
-		if (rw_aux_tree(b, t)[m].offset < offset)
-			l = m + 1;
-		else
-			r = m;
-	}
+	while (idx &&
+	       rw_aux_tree(b, t)[idx - 1].offset >= offset)
+		idx--;
 
-	EBUG_ON(l < t->size &&
-		rw_aux_tree(b, t)[l].offset < offset);
-	EBUG_ON(l &&
-		rw_aux_tree(b, t)[l - 1].offset >= offset);
-
-	EBUG_ON(l > r);
-	EBUG_ON(l > t->size);
+	EBUG_ON(idx < t->size &&
+		rw_aux_tree(b, t)[idx].offset < offset);
+	EBUG_ON(idx && rw_aux_tree(b, t)[idx - 1].offset >= offset);
+	EBUG_ON(idx + 1 < t->size &&
+		rw_aux_tree(b, t)[idx].offset ==
+		rw_aux_tree(b, t)[idx + 1].offset);
 
-	return l;
+	return idx;
 }
 
 static inline unsigned bfloat_mantissa(const struct bkey_float *f,
@@ -1150,13 +1152,9 @@ static void bch2_bset_fix_lookup_table(struct btree *b,
 	if (!bset_has_rw_aux_tree(t))
 		return;
 
+	/* returns first entry >= where */
 	l = rw_aux_tree_bsearch(b, t, where);
 
-	/* l is first >= than @where */
-
-	EBUG_ON(l < t->size && rw_aux_tree(b, t)[l].offset < where);
-	EBUG_ON(l && rw_aux_tree(b, t)[l - 1].offset >= where);
-
 	if (!l) /* never delete first entry */
 		l++;
 	else if (l < t->size &&
diff --git a/fs/bcachefs/btree_types.h b/fs/bcachefs/btree_types.h
index 2ca3b1f0236f..fcd660470e52 100644
--- a/fs/bcachefs/btree_types.h
+++ b/fs/bcachefs/btree_types.h
@@ -371,6 +371,11 @@ __btree_node_offset_to_key(const struct btree *b, u16 k)
 	return (void *) ((u64 *) b->data + k + 1);
 }
 
+static inline unsigned btree_bkey_first_offset(const struct bset_tree *t)
+{
+	return t->data_offset + offsetof(struct bset, _data) / sizeof(u64);
+}
+
 #define btree_bkey_first(_b, _t)	(bset(_b, _t)->start)
 
 #define btree_bkey_last(_b, _t)						\