X-Git-Url: https://git.sesse.net/?a=blobdiff_plain;f=libbcachefs%2Fbset.c;h=bb73ba9017b006e7fe181e19b7cccfe8494c1339;hb=f76d246fff1c3c5b091fb2b910067d893620dc5e;hp=19f13b7e61e60745346b7f0f4761bbcf0a42d698;hpb=6016d33b801a5fe13e86e5be3abf68ed166c0796;p=bcachefs-tools-debian

diff --git a/libbcachefs/bset.c b/libbcachefs/bset.c
index 19f13b7..bb73ba9 100644
--- a/libbcachefs/bset.c
+++ b/libbcachefs/bset.c
@@ -10,6 +10,7 @@
 #include "btree_cache.h"
 #include "bset.h"
 #include "eytzinger.h"
+#include "trace.h"
 #include "util.h"
 
 #include <asm/unaligned.h>
@@ -17,10 +18,6 @@
 #include <linux/random.h>
 #include <linux/prefetch.h>
 
-/* hack.. */
-#include "alloc_types.h"
-#include <trace/events/bcachefs.h>
-
 static inline void __bch2_btree_node_iter_advance(struct btree_node_iter *,
 						  struct btree *);
 
@@ -36,16 +33,7 @@ static inline unsigned __btree_node_iter_used(struct btree_node_iter *iter)
 
 struct bset_tree *bch2_bkey_to_bset(struct btree *b, struct bkey_packed *k)
 {
-	unsigned offset = __btree_node_key_to_offset(b, k);
-	struct bset_tree *t;
-
-	for_each_bset(b, t)
-		if (offset <= t->end_offset) {
-			EBUG_ON(offset < btree_bkey_first_offset(t));
-			return t;
-		}
-
-	BUG();
+	return bch2_bkey_to_bset_inlined(b, k);
 }
 
 /*
@@ -64,54 +52,56 @@ struct bset_tree *bch2_bkey_to_bset(struct btree *b, struct bkey_packed *k)
  * by the time we actually do the insert will all be deleted.
  */
 
-void bch2_dump_bset(struct btree *b, struct bset *i, unsigned set)
+void bch2_dump_bset(struct bch_fs *c, struct btree *b,
+		    struct bset *i, unsigned set)
 {
 	struct bkey_packed *_k, *_n;
-	struct bkey k, n;
-	char buf[120];
+	struct bkey uk, n;
+	struct bkey_s_c k;
+	struct printbuf buf = PRINTBUF;
 
 	if (!i->u64s)
 		return;
 
-	for (_k = i->start, k = bkey_unpack_key(b, _k);
+	for (_k = i->start;
 	     _k < vstruct_last(i);
-	     _k = _n, k = n) {
-		_n = bkey_next(_k);
+	     _k = _n) {
+		_n = bkey_p_next(_k);
 
-		bch2_bkey_to_text(&PBUF(buf), &k);
-		printk(KERN_ERR "block %u key %5u: %s\n", set,
-		       __btree_node_key_to_offset(b, _k), buf);
+		k = bkey_disassemble(b, _k, &uk);
+
+		printbuf_reset(&buf);
+		if (c)
+			bch2_bkey_val_to_text(&buf, c, k);
+		else
+			bch2_bkey_to_text(&buf, k.k);
+		printk(KERN_ERR "block %u key %5zu: %s\n", set,
+		       _k->_data - i->_data, buf.buf);
 
 		if (_n == vstruct_last(i))
 			continue;
 
 		n = bkey_unpack_key(b, _n);
 
-		if (bkey_cmp(bkey_start_pos(&n), k.p) < 0) {
+		if (bpos_lt(n.p, k.k->p)) {
 			printk(KERN_ERR "Key skipped backwards\n");
 			continue;
 		}
 
-		/*
-		 * Weird check for duplicate non extent keys: extents are
-		 * deleted iff they have 0 size, so if it has zero size and it's
-		 * not deleted these aren't extents:
-		 */
-		if (((!k.size && !bkey_deleted(&k)) ||
-		     (!n.size && !bkey_deleted(&n))) &&
-		    !bkey_deleted(&k) &&
-		    !bkey_cmp(n.p, k.p))
+		if (!bkey_deleted(k.k) && bpos_eq(n.p, k.k->p))
 			printk(KERN_ERR "Duplicate keys\n");
 	}
+
+	printbuf_exit(&buf);
 }
 
-void bch2_dump_btree_node(struct btree *b)
+void bch2_dump_btree_node(struct bch_fs *c, struct btree *b)
 {
 	struct bset_tree *t;
 
 	console_lock();
 	for_each_bset(b, t)
-		bch2_dump_bset(b, bset(b, t), t - b->set);
+		bch2_dump_bset(c, b, bset(b, t), t - b->set);
 	console_unlock();
 }
 
@@ -119,6 +109,7 @@ void bch2_dump_btree_node_iter(struct btree *b,
 			      struct btree_node_iter *iter)
 {
 	struct btree_node_iter_set *set;
+	struct printbuf buf = PRINTBUF;
 
 	printk(KERN_ERR "btree node iter with %u/%u sets:\n",
 	       __btree_node_iter_used(iter), b->nsets);
@@ -127,12 +118,14 @@ void bch2_dump_btree_node_iter(struct btree *b,
 		struct bkey_packed *k = __btree_node_offset_to_key(b, set->k);
 		struct bset_tree *t = bch2_bkey_to_bset(b, k);
 		struct bkey uk = bkey_unpack_key(b, k);
-		char buf[100];
 
-		bch2_bkey_to_text(&PBUF(buf), &uk);
+		printbuf_reset(&buf);
+		bch2_bkey_to_text(&buf, &uk);
 		printk(KERN_ERR "set %zu key %u: %s\n",
-		       t - b->set, set->k, buf);
+		       t - b->set, set->k, buf.buf);
 	}
+
+	printbuf_exit(&buf);
 }
 
 #ifdef CONFIG_BCACHEFS_DEBUG
@@ -144,10 +137,8 @@ void __bch2_verify_btree_nr_keys(struct btree *b)
 	struct btree_nr_keys nr = { 0 };
 
 	for_each_bset(b, t)
-		for (k = btree_bkey_first(b, t);
-		     k != btree_bkey_last(b, t);
-		     k = bkey_next(k))
-			if (!bkey_whiteout(k))
+		bset_tree_for_each_key(b, t, k)
+			if (!bkey_deleted(k))
 				btree_keys_account_key_add(&nr, t - b->set, k);
 
 	BUG_ON(memcmp(&nr, &b->nr, sizeof(nr)));
@@ -170,20 +161,21 @@ static void bch2_btree_node_iter_next_check(struct btree_node_iter *_iter,
 		struct btree_node_iter_set *set;
 		struct bkey ku = bkey_unpack_key(b, k);
 		struct bkey nu = bkey_unpack_key(b, n);
-		char buf1[80], buf2[80];
+		struct printbuf buf1 = PRINTBUF;
+		struct printbuf buf2 = PRINTBUF;
 
-		bch2_dump_btree_node(b);
-		bch2_bkey_to_text(&PBUF(buf1), &ku);
-		bch2_bkey_to_text(&PBUF(buf2), &nu);
+		bch2_dump_btree_node(NULL, b);
+		bch2_bkey_to_text(&buf1, &ku);
+		bch2_bkey_to_text(&buf2, &nu);
 		printk(KERN_ERR "out of order/overlapping:\n%s\n%s\n",
-		       buf1, buf2);
+		       buf1.buf, buf2.buf);
 		printk(KERN_ERR "iter was:");
 
 		btree_node_iter_for_each(_iter, set) {
-			struct bkey_packed *k = __btree_node_offset_to_key(b, set->k);
-			struct bset_tree *t = bch2_bkey_to_bset(b, k);
+			struct bkey_packed *k2 = __btree_node_offset_to_key(b, set->k);
+			struct bset_tree *t = bch2_bkey_to_bset(b, k2);
 			printk(" [%zi %zi]", t - b->set,
-			       k->_data - bset(b, t)->_data);
+			       k2->_data - bset(b, t)->_data);
 		}
 		panic("\n");
 	}
@@ -200,9 +192,11 @@ void bch2_btree_node_iter_verify(struct btree_node_iter *iter,
 		return;
 
 	/* Verify no duplicates: */
-	btree_node_iter_for_each(iter, set)
+	btree_node_iter_for_each(iter, set) {
+		BUG_ON(set->k > set->end);
 		btree_node_iter_for_each(iter, s2)
 			BUG_ON(set != s2 && set->end == s2->end);
+	}
 
 	/* Verify that set->end is correct: */
 	btree_node_iter_for_each(iter, set) {
@@ -238,7 +232,9 @@ void bch2_verify_insert_pos(struct btree *b, struct bkey_packed *where,
 {
 	struct bset_tree *t = bch2_bkey_to_bset(b, where);
 	struct bkey_packed *prev = bch2_bkey_prev_all(b, t, where);
-	struct bkey_packed *next = (void *) (where->_data + clobber_u64s);
+	struct bkey_packed *next = (void *) ((u64 *) where->_data + clobber_u64s);
+	struct printbuf buf1 = PRINTBUF;
+	struct printbuf buf2 = PRINTBUF;
 #if 0
 	BUG_ON(prev &&
 	       bkey_iter_cmp(b, prev, insert) > 0);
@@ -247,18 +243,15 @@ void bch2_verify_insert_pos(struct btree *b, struct bkey_packed *where,
 	    bkey_iter_cmp(b, prev, insert) > 0) {
 		struct bkey k1 = bkey_unpack_key(b, prev);
 		struct bkey k2 = bkey_unpack_key(b, insert);
-		char buf1[100];
-		char buf2[100];
 
-		bch2_dump_btree_node(b);
-		bch2_bkey_to_text(&PBUF(buf1), &k1);
-		bch2_bkey_to_text(&PBUF(buf2), &k2);
+		bch2_dump_btree_node(NULL, b);
+		bch2_bkey_to_text(&buf1, &k1);
+		bch2_bkey_to_text(&buf2, &k2);
 
 		panic("prev > insert:\n"
-		      "prev    key %5u %s\n"
-		      "insert  key %5u %s\n",
-		       __btree_node_key_to_offset(b, prev), buf1,
-		       __btree_node_key_to_offset(b, insert), buf2);
+		      "prev    key %s\n"
+		      "insert  key %s\n",
+		      buf1.buf, buf2.buf);
 	}
 #endif
 #if 0
@@ -269,18 +262,15 @@ void bch2_verify_insert_pos(struct btree *b, struct bkey_packed *where,
 	    bkey_iter_cmp(b, insert, next) > 0) {
 		struct bkey k1 = bkey_unpack_key(b, insert);
 		struct bkey k2 = bkey_unpack_key(b, next);
-		char buf1[100];
-		char buf2[100];
 
-		bch2_dump_btree_node(b);
-		bch2_bkey_to_text(&PBUF(buf1), &k1);
-		bch2_bkey_to_text(&PBUF(buf2), &k2);
+		bch2_dump_btree_node(NULL, b);
+		bch2_bkey_to_text(&buf1, &k1);
+		bch2_bkey_to_text(&buf2, &k2);
 
 		panic("insert > next:\n"
-		      "insert  key %5u %s\n"
-		      "next    key %5u %s\n",
-		       __btree_node_key_to_offset(b, insert), buf1,
-		       __btree_node_key_to_offset(b, next), buf2);
+		      "insert  key %s\n"
+		      "next    key %s\n",
+		      buf1.buf, buf2.buf);
 	}
 #endif
 }
@@ -294,38 +284,24 @@ static inline void bch2_btree_node_iter_next_check(struct btree_node_iter *iter,
 
 /* Auxiliary search trees */
 
-#define BFLOAT_FAILED_UNPACKED	(U8_MAX - 0)
-#define BFLOAT_FAILED_PREV	(U8_MAX - 1)
-#define BFLOAT_FAILED_OVERFLOW	(U8_MAX - 2)
-#define BFLOAT_FAILED		(U8_MAX - 2)
-
-#define KEY_WORDS		BITS_TO_LONGS(1 << BKEY_EXPONENT_BITS)
+#define BFLOAT_FAILED_UNPACKED	U8_MAX
+#define BFLOAT_FAILED		U8_MAX
 
 struct bkey_float {
 	u8		exponent;
 	u8		key_offset;
-	union {
-		u32	mantissa32;
-	struct {
-		u16	mantissa16;
-		u16	_pad;
-	};
-	};
-} __packed;
-
-#define BFLOAT_32BIT_NR		32U
+	u16		mantissa;
+};
+#define BKEY_MANTISSA_BITS	16
 
 static unsigned bkey_float_byte_offset(unsigned idx)
 {
-	int d = (idx - BFLOAT_32BIT_NR) << 1;
-
-	d &= ~(d >> 31);
-
-	return idx * 6 - d;
+	return idx * sizeof(struct bkey_float);
 }
 
 struct ro_aux_tree {
-	struct bkey_float	_d[0];
+	u8			nothing[0];
+	struct bkey_float	f[];
 };
 
 struct rw_aux_tree {
@@ -333,44 +309,6 @@ struct rw_aux_tree {
 	struct bpos	k;
 };
 
-/*
- * BSET_CACHELINE was originally intended to match the hardware cacheline size -
- * it used to be 64, but I realized the lookup code would touch slightly less
- * memory if it was 128.
- *
- * It definites the number of bytes (in struct bset) per struct bkey_float in
- * the auxiliar search tree - when we're done searching the bset_float tree we
- * have this many bytes left that we do a linear search over.
- *
- * Since (after level 5) every level of the bset_tree is on a new cacheline,
- * we're touching one fewer cacheline in the bset tree in exchange for one more
- * cacheline in the linear search - but the linear search might stop before it
- * gets to the second cacheline.
- */
-
-#define BSET_CACHELINE		128
-
-/* Space required for the btree node keys */
-static inline size_t btree_keys_bytes(struct btree *b)
-{
-	return PAGE_SIZE << b->page_order;
-}
-
-static inline size_t btree_keys_cachelines(struct btree *b)
-{
-	return btree_keys_bytes(b) / BSET_CACHELINE;
-}
-
-static inline size_t btree_aux_data_bytes(struct btree *b)
-{
-	return btree_keys_cachelines(b) * 8;
-}
-
-static inline size_t btree_aux_data_u64s(struct btree *b)
-{
-	return btree_aux_data_bytes(b) / sizeof(u64);
-}
-
 static unsigned bset_aux_tree_buf_end(const struct bset_tree *t)
 {
 	BUG_ON(t->aux_data_offset == U16_MAX);
@@ -380,8 +318,8 @@ static unsigned bset_aux_tree_buf_end(const struct bset_tree *t)
 		return t->aux_data_offset;
 	case BSET_RO_AUX_TREE:
 		return t->aux_data_offset +
-			DIV_ROUND_UP(bkey_float_byte_offset(t->size) +
-				     sizeof(u8) * t->size, 8);
+			DIV_ROUND_UP(t->size * sizeof(struct bkey_float) +
+				     t->size * sizeof(u8), 8);
 	case BSET_RW_AUX_TREE:
 		return t->aux_data_offset +
 			DIV_ROUND_UP(sizeof(struct rw_aux_tree) * t->size, 8);
@@ -420,23 +358,17 @@ static u8 *ro_aux_tree_prev(const struct btree *b,
 	return __aux_tree_base(b, t) + bkey_float_byte_offset(t->size);
 }
 
-static struct bkey_float *bkey_float_get(struct ro_aux_tree *b,
-					 unsigned idx)
-{
-	return (void *) b + bkey_float_byte_offset(idx);
-}
-
 static struct bkey_float *bkey_float(const struct btree *b,
 				     const struct bset_tree *t,
 				     unsigned idx)
 {
-	return bkey_float_get(ro_aux_tree_base(b, t), idx);
+	return ro_aux_tree_base(b, t)->f + idx;
 }
 
-static void bset_aux_tree_verify(struct btree *b)
+static void bset_aux_tree_verify(const struct btree *b)
 {
 #ifdef CONFIG_BCACHEFS_DEBUG
-	struct bset_tree *t;
+	const struct bset_tree *t;
 
 	for_each_bset(b, t) {
 		if (t->aux_data_offset == U16_MAX)
@@ -452,38 +384,13 @@ static void bset_aux_tree_verify(struct btree *b)
 #endif
 }
 
-/* Memory allocation */
-
-void bch2_btree_keys_free(struct btree *b)
-{
-	vfree(b->aux_data);
-	b->aux_data = NULL;
-}
-
-#ifndef PAGE_KERNEL_EXEC
-# define PAGE_KERNEL_EXEC PAGE_KERNEL
-#endif
-
-int bch2_btree_keys_alloc(struct btree *b, unsigned page_order, gfp_t gfp)
-{
-	b->page_order	= page_order;
-	b->aux_data	= __vmalloc(btree_aux_data_bytes(b), gfp,
-				    PAGE_KERNEL_EXEC);
-	if (!b->aux_data)
-		return -ENOMEM;
-
-	return 0;
-}
-
-void bch2_btree_keys_init(struct btree *b, bool *expensive_debug_checks)
+void bch2_btree_keys_init(struct btree *b)
 {
 	unsigned i;
 
 	b->nsets		= 0;
 	memset(&b->nr, 0, sizeof(b->nr));
-#ifdef CONFIG_BCACHEFS_DEBUG
-	b->expensive_debug_checks = expensive_debug_checks;
-#endif
+
 	for (i = 0; i < MAX_BSETS; i++)
 		b->set[i].data_offset = U16_MAX;
 
@@ -560,7 +467,7 @@ static inline struct bkey_packed *tree_to_bkey(const struct btree *b,
 					       unsigned j)
 {
 	return cacheline_to_bkey(b, t,
-			__eytzinger1_to_inorder(j, t->size, t->extra),
+			__eytzinger1_to_inorder(j, t->size - 1, t->extra),
 			bkey_float(b, t, j)->key_offset);
 }
 
@@ -570,7 +477,7 @@ static struct bkey_packed *tree_to_prev_bkey(const struct btree *b,
 {
 	unsigned prev_u64s = ro_aux_tree_prev(b, t)[j];
 
-	return (void *) (tree_to_bkey(b, t, j)->_data - prev_u64s);
+	return (void *) ((u64 *) tree_to_bkey(b, t, j)->_data - prev_u64s);
 }
 
 static struct rw_aux_tree *rw_aux_tree(const struct btree *b,
@@ -609,7 +516,7 @@ static void bch2_bset_verify_rw_aux_tree(struct btree *b,
 	struct bkey_packed *k = btree_bkey_first(b, t);
 	unsigned j = 0;
 
-	if (!btree_keys_expensive_checks(b))
+	if (!bch2_expensive_debug_checks)
 		return;
 
 	BUG_ON(bset_has_ro_aux_tree(t));
@@ -623,7 +530,7 @@ static void bch2_bset_verify_rw_aux_tree(struct btree *b,
 	goto start;
 	while (1) {
 		if (rw_aux_to_bkey(b, t, j) == k) {
-			BUG_ON(bkey_cmp(rw_aux_tree(b, t)[j].k,
+			BUG_ON(!bpos_eq(rw_aux_tree(b, t)[j].k,
 					bkey_unpack_pos(b, k)));
 start:
 			if (++j == t->size)
@@ -633,7 +540,7 @@ start:
 			       rw_aux_tree(b, t)[j - 1].offset);
 		}
 
-		k = bkey_next(k);
+		k = bkey_p_next(k);
 		BUG_ON(k >= btree_bkey_last(b, t));
 	}
 }
@@ -669,21 +576,6 @@ static unsigned rw_aux_tree_bsearch(struct btree *b,
 	return idx;
 }
 
-static inline unsigned bfloat_mantissa(const struct bkey_float *f,
-				       unsigned idx)
-{
-	return idx < BFLOAT_32BIT_NR ? f->mantissa32 : f->mantissa16;
-}
-
-static inline void bfloat_mantissa_set(struct bkey_float *f,
-				       unsigned idx, unsigned mantissa)
-{
-	if (idx < BFLOAT_32BIT_NR)
-		f->mantissa32 = mantissa;
-	else
-		f->mantissa16 = mantissa;
-}
-
 static inline unsigned bkey_mantissa(const struct bkey_packed *k,
 				     const struct bkey_float *f,
 				     unsigned idx)
@@ -703,69 +595,33 @@ static inline unsigned bkey_mantissa(const struct bkey_packed *k,
 #if __BYTE_ORDER__ == __ORDER_LITTLE_ENDIAN__
 	v >>= f->exponent & 7;
 #else
-	v >>= 64 - (f->exponent & 7) - (idx < BFLOAT_32BIT_NR ? 32 : 16);
+	v >>= 64 - (f->exponent & 7) - BKEY_MANTISSA_BITS;
 #endif
-	return idx < BFLOAT_32BIT_NR ? (u32) v : (u16) v;
+	return (u16) v;
 }
 
-static void make_bfloat(struct btree *b, struct bset_tree *t,
-			unsigned j,
-			struct bkey_packed *min_key,
-			struct bkey_packed *max_key)
+static __always_inline void make_bfloat(struct btree *b, struct bset_tree *t,
+					unsigned j,
+					struct bkey_packed *min_key,
+					struct bkey_packed *max_key)
 {
 	struct bkey_float *f = bkey_float(b, t, j);
 	struct bkey_packed *m = tree_to_bkey(b, t, j);
-	struct bkey_packed *p = tree_to_prev_bkey(b, t, j);
-	struct bkey_packed *l, *r;
-	unsigned bits = j < BFLOAT_32BIT_NR ? 32 : 16;
+	struct bkey_packed *l = is_power_of_2(j)
+		? min_key
+		: tree_to_prev_bkey(b, t, j >> ffs(j));
+	struct bkey_packed *r = is_power_of_2(j + 1)
+		? max_key
+		: tree_to_bkey(b, t, j >> (ffz(j) + 1));
 	unsigned mantissa;
 	int shift, exponent, high_bit;
 
-	EBUG_ON(bkey_next(p) != m);
-
-	if (is_power_of_2(j)) {
-		l = min_key;
-
-		if (!l->u64s) {
-			if (!bkey_pack_pos(l, b->data->min_key, b)) {
-				struct bkey_i tmp;
-
-				bkey_init(&tmp.k);
-				tmp.k.p = b->data->min_key;
-				bkey_copy(l, &tmp);
-			}
-		}
-	} else {
-		l = tree_to_prev_bkey(b, t, j >> ffs(j));
-
-		EBUG_ON(m < l);
-	}
-
-	if (is_power_of_2(j + 1)) {
-		r = max_key;
-
-		if (!r->u64s) {
-			if (!bkey_pack_pos(r, t->max_key, b)) {
-				struct bkey_i tmp;
-
-				bkey_init(&tmp.k);
-				tmp.k.p = t->max_key;
-				bkey_copy(r, &tmp);
-			}
-		}
-	} else {
-		r = tree_to_bkey(b, t, j >> (ffz(j) + 1));
-
-		EBUG_ON(m > r);
-	}
-
 	/*
 	 * for failed bfloats, the lookup code falls back to comparing against
 	 * the original key.
 	 */
 
-	if (!bkey_packed(l) || !bkey_packed(r) ||
-	    !bkey_packed(p) || !bkey_packed(m) ||
+	if (!bkey_packed(l) || !bkey_packed(r) || !bkey_packed(m) ||
 	    !b->nr_key_bits) {
 		f->exponent = BFLOAT_FAILED_UNPACKED;
 		return;
@@ -782,8 +638,8 @@ static void make_bfloat(struct btree *b, struct bset_tree *t,
 	 * of the key: we handle this later:
 	 */
 	high_bit = max(bch2_bkey_greatest_differing_bit(b, l, r),
-		       min_t(unsigned, bits, b->nr_key_bits) - 1);
-	exponent = high_bit - (bits - 1);
+		       min_t(unsigned, BKEY_MANTISSA_BITS, b->nr_key_bits) - 1);
+	exponent = high_bit - (BKEY_MANTISSA_BITS - 1);
 
 	/*
 	 * Then we calculate the actual shift value, from the start of the key
@@ -792,12 +648,12 @@ static void make_bfloat(struct btree *b, struct bset_tree *t,
 #if __BYTE_ORDER__ == __ORDER_LITTLE_ENDIAN__
 	shift = (int) (b->format.key_u64s * 64 - b->nr_key_bits) + exponent;
 
-	EBUG_ON(shift + bits > b->format.key_u64s * 64);
+	EBUG_ON(shift + BKEY_MANTISSA_BITS > b->format.key_u64s * 64);
 #else
 	shift = high_bit_offset +
 		b->nr_key_bits -
 		exponent -
-		bits;
+		BKEY_MANTISSA_BITS;
 
 	EBUG_ON(shift < KEY_PACKED_BITS_START);
 #endif
@@ -813,65 +669,29 @@ static void make_bfloat(struct btree *b, struct bset_tree *t,
 	if (exponent < 0)
 		mantissa |= ~(~0U << -exponent);
 
-	bfloat_mantissa_set(f, j, mantissa);
-
-	/*
-	 * The bfloat must be able to tell its key apart from the previous key -
-	 * if its key and the previous key don't differ in the required bits,
-	 * flag as failed - unless the keys are actually equal, in which case
-	 * we aren't required to return a specific one:
-	 */
-	if (exponent > 0 &&
-	    bfloat_mantissa(f, j) == bkey_mantissa(p, f, j) &&
-	    bkey_cmp_packed(b, p, m)) {
-		f->exponent = BFLOAT_FAILED_PREV;
-		return;
-	}
-
-	/*
-	 * f->mantissa must compare >= the original key - for transitivity with
-	 * the comparison in bset_search_tree. If we're dropping set bits,
-	 * increment it:
-	 */
-	if (exponent > (int) bch2_bkey_ffs(b, m)) {
-		if (j < BFLOAT_32BIT_NR
-		    ? f->mantissa32 == U32_MAX
-		    : f->mantissa16 == U16_MAX)
-			f->exponent = BFLOAT_FAILED_OVERFLOW;
-
-		if (j < BFLOAT_32BIT_NR)
-			f->mantissa32++;
-		else
-			f->mantissa16++;
-	}
+	f->mantissa = mantissa;
 }
 
 /* bytes remaining - only valid for last bset: */
-static unsigned __bset_tree_capacity(struct btree *b, struct bset_tree *t)
+static unsigned __bset_tree_capacity(const struct btree *b, const struct bset_tree *t)
 {
 	bset_aux_tree_verify(b);
 
 	return btree_aux_data_bytes(b) - t->aux_data_offset * sizeof(u64);
 }
 
-static unsigned bset_ro_tree_capacity(struct btree *b, struct bset_tree *t)
+static unsigned bset_ro_tree_capacity(const struct btree *b, const struct bset_tree *t)
 {
-	unsigned bytes = __bset_tree_capacity(b, t);
-
-	if (bytes < 7 * BFLOAT_32BIT_NR)
-		return bytes / 7;
-
-	bytes -= 7 * BFLOAT_32BIT_NR;
-
-	return BFLOAT_32BIT_NR + bytes / 5;
+	return __bset_tree_capacity(b, t) /
+		(sizeof(struct bkey_float) + sizeof(u8));
 }
 
-static unsigned bset_rw_tree_capacity(struct btree *b, struct bset_tree *t)
+static unsigned bset_rw_tree_capacity(const struct btree *b, const struct bset_tree *t)
 {
 	return __bset_tree_capacity(b, t) / sizeof(struct rw_aux_tree);
 }
 
-static void __build_rw_aux_tree(struct btree *b, struct bset_tree *t)
+static noinline void __build_rw_aux_tree(struct btree *b, struct bset_tree *t)
 {
 	struct bkey_packed *k;
 
@@ -880,9 +700,7 @@ static void __build_rw_aux_tree(struct btree *b, struct bset_tree *t)
 	rw_aux_tree(b, t)[0].offset =
 		__btree_node_key_to_offset(b, btree_bkey_first(b, t));
 
-	for (k = btree_bkey_first(b, t);
-	     k != btree_bkey_last(b, t);
-	     k = bkey_next(k)) {
+	bset_tree_for_each_key(b, t, k) {
 		if (t->size == bset_rw_tree_capacity(b, t))
 			break;
 
@@ -892,15 +710,12 @@ static void __build_rw_aux_tree(struct btree *b, struct bset_tree *t)
 	}
 }
 
-static void __build_ro_aux_tree(struct btree *b, struct bset_tree *t)
+static noinline void __build_ro_aux_tree(struct btree *b, struct bset_tree *t)
 {
 	struct bkey_packed *prev = NULL, *k = btree_bkey_first(b, t);
-	struct bkey_packed min_key, max_key;
+	struct bkey_i min_key, max_key;
 	unsigned j, cacheline = 1;
 
-	/* signal to make_bfloat() that they're uninitialized: */
-	min_key.u64s = max_key.u64s = 0;
-
 	t->size = min(bkey_to_cacheline(b, t, btree_bkey_last(b, t)),
 		      bset_ro_tree_capacity(b, t));
 retry:
@@ -913,9 +728,9 @@ retry:
 	t->extra = (t->size - rounddown_pow_of_two(t->size - 1)) << 1;
 
 	/* First we figure out where the first key in each cacheline is */
-	eytzinger1_for_each(j, t->size) {
+	eytzinger1_for_each(j, t->size - 1) {
 		while (bkey_to_cacheline(b, t, k) < cacheline)
-			prev = k, k = bkey_next(k);
+			prev = k, k = bkey_p_next(k);
 
 		if (k >= btree_bkey_last(b, t)) {
 			/* XXX: this path sucks */
@@ -931,14 +746,24 @@ retry:
 		EBUG_ON(tree_to_bkey(b, t, j) != k);
 	}
 
-	while (bkey_next(k) != btree_bkey_last(b, t))
-		k = bkey_next(k);
+	while (k != btree_bkey_last(b, t))
+		prev = k, k = bkey_p_next(k);
 
-	t->max_key = bkey_unpack_pos(b, k);
+	if (!bkey_pack_pos(bkey_to_packed(&min_key), b->data->min_key, b)) {
+		bkey_init(&min_key.k);
+		min_key.k.p = b->data->min_key;
+	}
+
+	if (!bkey_pack_pos(bkey_to_packed(&max_key), b->data->max_key, b)) {
+		bkey_init(&max_key.k);
+		max_key.k.p = b->data->max_key;
+	}
 
 	/* Then we build the tree */
-	eytzinger1_for_each(j, t->size)
-		make_bfloat(b, t, j, &min_key, &max_key);
+	eytzinger1_for_each(j, t->size - 1)
+		make_bfloat(b, t, j,
+			    bkey_to_packed(&min_key),
+			    bkey_to_packed(&max_key));
 }
 
 static void bset_alloc_tree(struct btree *b, struct bset_tree *t)
@@ -1037,7 +862,7 @@ static struct bkey_packed *__bkey_prev(struct btree *b, struct bset_tree *t,
 		do {
 			p = j ? tree_to_bkey(b, t,
 					__inorder_to_eytzinger1(j--,
-							t->size, t->extra))
+							t->size - 1, t->extra))
 			      : btree_bkey_first(b, t);
 		} while (p >= k);
 		break;
@@ -1060,19 +885,21 @@ struct bkey_packed *bch2_bkey_prev_filter(struct btree *b,
 	struct bkey_packed *p, *i, *ret = NULL, *orig_k = k;
 
 	while ((p = __bkey_prev(b, t, k)) && !ret) {
-		for (i = p; i != k; i = bkey_next(i))
+		for (i = p; i != k; i = bkey_p_next(i))
 			if (i->type >= min_key_type)
 				ret = i;
 
 		k = p;
 	}
 
-	if (btree_keys_expensive_checks(b)) {
+	if (bch2_expensive_debug_checks) {
 		BUG_ON(ret >= orig_k);
 
-		for (i = ret ? bkey_next(ret) : btree_bkey_first(b, t);
+		for (i = ret
+			? bkey_p_next(ret)
+			: btree_bkey_first(b, t);
 		     i != orig_k;
-		     i = bkey_next(i))
+		     i = bkey_p_next(i))
 			BUG_ON(i->type >= min_key_type);
 	}
 
@@ -1081,93 +908,6 @@ struct bkey_packed *bch2_bkey_prev_filter(struct btree *b,
 
 /* Insert */
 
-static void rw_aux_tree_fix_invalidated_key(struct btree *b,
-					    struct bset_tree *t,
-					    struct bkey_packed *k)
-{
-	unsigned offset = __btree_node_key_to_offset(b, k);
-	unsigned j = rw_aux_tree_bsearch(b, t, offset);
-
-	if (j < t->size &&
-	    rw_aux_tree(b, t)[j].offset == offset)
-		rw_aux_tree_set(b, t, j, k);
-
-	bch2_bset_verify_rw_aux_tree(b, t);
-}
-
-static void ro_aux_tree_fix_invalidated_key(struct btree *b,
-					    struct bset_tree *t,
-					    struct bkey_packed *k)
-{
-	struct bkey_packed min_key, max_key;
-	unsigned inorder, j;
-
-	EBUG_ON(bset_aux_tree_type(t) != BSET_RO_AUX_TREE);
-
-	/* signal to make_bfloat() that they're uninitialized: */
-	min_key.u64s = max_key.u64s = 0;
-
-	if (bkey_next(k) == btree_bkey_last(b, t)) {
-		t->max_key = bkey_unpack_pos(b, k);
-
-		for (j = 1; j < t->size; j = j * 2 + 1)
-			make_bfloat(b, t, j, &min_key, &max_key);
-	}
-
-	inorder = bkey_to_cacheline(b, t, k);
-
-	if (inorder &&
-	    inorder < t->size) {
-		j = __inorder_to_eytzinger1(inorder, t->size, t->extra);
-
-		if (k == tree_to_bkey(b, t, j)) {
-			/* Fix the node this key corresponds to */
-			make_bfloat(b, t, j, &min_key, &max_key);
-
-			/* Children for which this key is the right boundary */
-			for (j = eytzinger1_left_child(j);
-			     j < t->size;
-			     j = eytzinger1_right_child(j))
-				make_bfloat(b, t, j, &min_key, &max_key);
-		}
-	}
-
-	if (inorder + 1 < t->size) {
-		j = __inorder_to_eytzinger1(inorder + 1, t->size, t->extra);
-
-		if (k == tree_to_prev_bkey(b, t, j)) {
-			make_bfloat(b, t, j, &min_key, &max_key);
-
-			/* Children for which this key is the left boundary */
-			for (j = eytzinger1_right_child(j);
-			     j < t->size;
-			     j = eytzinger1_left_child(j))
-				make_bfloat(b, t, j, &min_key, &max_key);
-		}
-	}
-}
-
-/**
- * bch2_bset_fix_invalidated_key() - given an existing  key @k that has been
- * modified, fix any auxiliary search tree by remaking all the nodes in the
- * auxiliary search tree that @k corresponds to
- */
-void bch2_bset_fix_invalidated_key(struct btree *b, struct bkey_packed *k)
-{
-	struct bset_tree *t = bch2_bkey_to_bset(b, k);
-
-	switch (bset_aux_tree_type(t)) {
-	case BSET_NO_AUX_TREE:
-		break;
-	case BSET_RO_AUX_TREE:
-		ro_aux_tree_fix_invalidated_key(b, t, k);
-		break;
-	case BSET_RW_AUX_TREE:
-		rw_aux_tree_fix_invalidated_key(b, t, k);
-		break;
-	}
-}
-
 static void bch2_bset_fix_lookup_table(struct btree *b,
 				       struct bset_tree *t,
 				       struct bkey_packed *_where,
@@ -1212,7 +952,7 @@ static void bch2_bset_fix_lookup_table(struct btree *b,
 	t->size -= j - l;
 
 	for (j = l; j < t->size; j++)
-	       rw_aux_tree(b, t)[j].offset += shift;
+		rw_aux_tree(b, t)[j].offset += shift;
 
 	EBUG_ON(l < t->size &&
 		rw_aux_tree(b, t)[l].offset ==
@@ -1231,7 +971,7 @@ static void bch2_bset_fix_lookup_table(struct btree *b,
 		struct bkey_packed *k = start;
 
 		while (1) {
-			k = bkey_next(k);
+			k = bkey_p_next(k);
 			if (k == end)
 				break;
 
@@ -1267,12 +1007,12 @@ void bch2_bset_insert(struct btree *b,
 	if (bch2_bkey_pack_key(&packed, &insert->k, f))
 		src = &packed;
 
-	if (!bkey_whiteout(&insert->k))
+	if (!bkey_deleted(&insert->k))
 		btree_keys_account_key_add(&b->nr, t - b->set, src);
 
 	if (src->u64s != clobber_u64s) {
-		u64 *src_p = where->_data + clobber_u64s;
-		u64 *dst_p = where->_data + src->u64s;
+		u64 *src_p = (u64 *) where->_data + clobber_u64s;
+		u64 *dst_p = (u64 *) where->_data + src->u64s;
 
 		EBUG_ON((int) le16_to_cpu(bset(b, t)->u64s) <
 			(int) clobber_u64s - src->u64s);
@@ -1282,12 +1022,13 @@ void bch2_bset_insert(struct btree *b,
 		set_btree_bset_end(b, t);
 	}
 
-	memcpy_u64s(where, src,
+	memcpy_u64s_small(where, src,
 		    bkeyp_key_u64s(f, src));
 	memcpy_u64s(bkeyp_val(f, where), &insert->v,
 		    bkeyp_val_u64s(f, src));
 
-	bch2_bset_fix_lookup_table(b, t, where, clobber_u64s, src->u64s);
+	if (src->u64s != clobber_u64s)
+		bch2_bset_fix_lookup_table(b, t, where, clobber_u64s, src->u64s);
 
 	bch2_verify_btree_nr_keys(b);
 }
@@ -1297,7 +1038,7 @@ void bch2_bset_delete(struct btree *b,
 		      unsigned clobber_u64s)
 {
 	struct bset_tree *t = bset_tree_last(b);
-	u64 *src_p = where->_data + clobber_u64s;
+	u64 *src_p = (u64 *) where->_data + clobber_u64s;
 	u64 *dst_p = where->_data;
 
 	bch2_bset_verify_rw_aux_tree(b, t);
@@ -1316,15 +1057,14 @@ void bch2_bset_delete(struct btree *b,
 __flatten
 static struct bkey_packed *bset_search_write_set(const struct btree *b,
 				struct bset_tree *t,
-				struct bpos *search,
-				const struct bkey_packed *packed_search)
+				struct bpos *search)
 {
 	unsigned l = 0, r = t->size;
 
 	while (l + 1 != r) {
 		unsigned m = (l + r) >> 1;
 
-		if (bkey_cmp(rw_aux_tree(b, t)[m].k, *search) < 0)
+		if (bpos_lt(rw_aux_tree(b, t)[m].k, *search))
 			l = m;
 		else
 			r = m;
@@ -1333,92 +1073,98 @@ static struct bkey_packed *bset_search_write_set(const struct btree *b,
 	return rw_aux_to_bkey(b, t, l);
 }
 
-noinline
-static int bset_search_tree_slowpath(const struct btree *b,
-				struct bset_tree *t, struct bpos *search,
-				const struct bkey_packed *packed_search,
-				unsigned n)
+static inline void prefetch_four_cachelines(void *p)
+{
+#ifdef CONFIG_X86_64
+	asm("prefetcht0 (-127 + 64 * 0)(%0);"
+	    "prefetcht0 (-127 + 64 * 1)(%0);"
+	    "prefetcht0 (-127 + 64 * 2)(%0);"
+	    "prefetcht0 (-127 + 64 * 3)(%0);"
+	    :
+	    : "r" (p + 127));
+#else
+	prefetch(p + L1_CACHE_BYTES * 0);
+	prefetch(p + L1_CACHE_BYTES * 1);
+	prefetch(p + L1_CACHE_BYTES * 2);
+	prefetch(p + L1_CACHE_BYTES * 3);
+#endif
+}
+
+static inline bool bkey_mantissa_bits_dropped(const struct btree *b,
+					      const struct bkey_float *f,
+					      unsigned idx)
 {
-	return bkey_cmp_p_or_unp(b, tree_to_bkey(b, t, n),
-				 packed_search, search) < 0;
+#if __BYTE_ORDER__ == __ORDER_LITTLE_ENDIAN__
+	unsigned key_bits_start = b->format.key_u64s * 64 - b->nr_key_bits;
+
+	return f->exponent > key_bits_start;
+#else
+	unsigned key_bits_end = high_bit_offset + b->nr_key_bits;
+
+	return f->exponent + BKEY_MANTISSA_BITS < key_bits_end;
+#endif
 }
 
 __flatten
 static struct bkey_packed *bset_search_tree(const struct btree *b,
-				struct bset_tree *t,
-				struct bpos *search,
+				const struct bset_tree *t,
+				const struct bpos *search,
 				const struct bkey_packed *packed_search)
 {
 	struct ro_aux_tree *base = ro_aux_tree_base(b, t);
-	struct bkey_float *f = bkey_float_get(base, 1);
-	void *p;
-	unsigned inorder, n = 1;
+	struct bkey_float *f;
+	struct bkey_packed *k;
+	unsigned inorder, n = 1, l, r;
+	int cmp;
 
-	while (1) {
-		if (likely(n << 4 < t->size)) {
-			p = bkey_float_get(base, n << 4);
-			prefetch(p);
-		} else if (n << 3 < t->size) {
-			inorder = __eytzinger1_to_inorder(n, t->size, t->extra);
-			p = bset_cacheline(b, t, inorder);
-#ifdef CONFIG_X86_64
-			asm(".intel_syntax noprefix;"
-			    "prefetcht0 [%0 - 127 + 64 * 0];"
-			    "prefetcht0 [%0 - 127 + 64 * 1];"
-			    "prefetcht0 [%0 - 127 + 64 * 2];"
-			    "prefetcht0 [%0 - 127 + 64 * 3];"
-			    ".att_syntax prefix;"
-			    :
-			    : "r" (p + 127));
-#else
-			prefetch(p + L1_CACHE_BYTES * 0);
-			prefetch(p + L1_CACHE_BYTES * 1);
-			prefetch(p + L1_CACHE_BYTES * 2);
-			prefetch(p + L1_CACHE_BYTES * 3);
-#endif
-		} else if (n >= t->size)
-			break;
+	do {
+		if (likely(n << 4 < t->size))
+			prefetch(&base->f[n << 4]);
 
-		f = bkey_float_get(base, n);
+		f = &base->f[n];
+		if (unlikely(f->exponent >= BFLOAT_FAILED))
+			goto slowpath;
 
-		if (packed_search &&
-		    likely(f->exponent < BFLOAT_FAILED))
-			n = n * 2 + (bfloat_mantissa(f, n) <
-				     bkey_mantissa(packed_search, f, n));
-		else
-			n = n * 2 + bset_search_tree_slowpath(b, t,
-						search, packed_search, n);
+		l = f->mantissa;
+		r = bkey_mantissa(packed_search, f, n);
+
+		if (unlikely(l == r) && bkey_mantissa_bits_dropped(b, f, n))
+			goto slowpath;
+
+		n = n * 2 + (l < r);
+		continue;
+slowpath:
+		k = tree_to_bkey(b, t, n);
+		cmp = bkey_cmp_p_or_unp(b, k, packed_search, search);
+		if (!cmp)
+			return k;
+
+		n = n * 2 + (cmp < 0);
 	} while (n < t->size);
 
-	inorder = __eytzinger1_to_inorder(n >> 1, t->size, t->extra);
+	inorder = __eytzinger1_to_inorder(n >> 1, t->size - 1, t->extra);
 
 	/*
 	 * n would have been the node we recursed to - the low bit tells us if
 	 * we recursed left or recursed right.
 	 */
-	if (n & 1) {
-		return cacheline_to_bkey(b, t, inorder, f->key_offset);
-	} else {
-		if (--inorder) {
-			n = eytzinger1_prev(n >> 1, t->size);
-			f = bkey_float_get(base, n);
-			return cacheline_to_bkey(b, t, inorder, f->key_offset);
-		} else
+	if (likely(!(n & 1))) {
+		--inorder;
+		if (unlikely(!inorder))
 			return btree_bkey_first(b, t);
+
+		f = &base->f[eytzinger1_prev(n >> 1, t->size - 1)];
 	}
+
+	return cacheline_to_bkey(b, t, inorder, f->key_offset);
 }
 
-/*
- * Returns the first key greater than or equal to @search
- */
-__always_inline __flatten
-static struct bkey_packed *bch2_bset_search(struct btree *b,
+static __always_inline __flatten
+struct bkey_packed *__bch2_bset_search(struct btree *b,
 				struct bset_tree *t,
 				struct bpos *search,
-				struct bkey_packed *packed_search,
 				const struct bkey_packed *lossy_packed_search)
 {
-	struct bkey_packed *m;
 
 	/*
 	 * First, we search for a cacheline, then lastly we do a linear search
@@ -1437,43 +1183,41 @@ static struct bkey_packed *bch2_bset_search(struct btree *b,
 
 	switch (bset_aux_tree_type(t)) {
 	case BSET_NO_AUX_TREE:
-		m = btree_bkey_first(b, t);
-		break;
+		return btree_bkey_first(b, t);
 	case BSET_RW_AUX_TREE:
-		m = bset_search_write_set(b, t, search, lossy_packed_search);
-		break;
+		return bset_search_write_set(b, t, search);
 	case BSET_RO_AUX_TREE:
-		/*
-		 * Each node in the auxiliary search tree covers a certain range
-		 * of bits, and keys above and below the set it covers might
-		 * differ outside those bits - so we have to special case the
-		 * start and end - handle that here:
-		 */
-
-		if (bkey_cmp(*search, t->max_key) > 0)
-			return btree_bkey_last(b, t);
-
-		m = bset_search_tree(b, t, search, lossy_packed_search);
-		break;
+		return bset_search_tree(b, t, search, lossy_packed_search);
+	default:
+		BUG();
 	}
+}
 
+static __always_inline __flatten
+struct bkey_packed *bch2_bset_search_linear(struct btree *b,
+				struct bset_tree *t,
+				struct bpos *search,
+				struct bkey_packed *packed_search,
+				const struct bkey_packed *lossy_packed_search,
+				struct bkey_packed *m)
+{
 	if (lossy_packed_search)
 		while (m != btree_bkey_last(b, t) &&
-		       bkey_iter_cmp_p_or_unp(b, search, lossy_packed_search,
-					      m) > 0)
-			m = bkey_next(m);
+		       bkey_iter_cmp_p_or_unp(b, m,
+					lossy_packed_search, search) < 0)
+			m = bkey_p_next(m);
 
 	if (!packed_search)
 		while (m != btree_bkey_last(b, t) &&
-		       bkey_iter_pos_cmp(b, search, m) > 0)
-			m = bkey_next(m);
+		       bkey_iter_pos_cmp(b, m, search) < 0)
+			m = bkey_p_next(m);
 
-	if (btree_keys_expensive_checks(b)) {
+	if (bch2_expensive_debug_checks) {
 		struct bkey_packed *prev = bch2_bkey_prev_all(b, t, m);
 
 		BUG_ON(prev &&
-		       bkey_iter_cmp_p_or_unp(b, search, packed_search,
-					      prev) <= 0);
+		       bkey_iter_cmp_p_or_unp(b, prev,
+					packed_search, search) >= 0);
 	}
 
 	return m;
@@ -1509,26 +1253,29 @@ void bch2_btree_node_iter_push(struct btree_node_iter *iter,
 	bch2_btree_node_iter_sort(iter, b);
 }
 
-noinline __flatten __attribute__((cold))
+noinline __flatten __cold
 static void btree_node_iter_init_pack_failed(struct btree_node_iter *iter,
 			      struct btree *b, struct bpos *search)
 {
-	struct bset_tree *t;
+	struct bkey_packed *k;
 
 	trace_bkey_pack_pos_fail(search);
 
-	for_each_bset(b, t)
-		__bch2_btree_node_iter_push(iter, b,
-			bch2_bset_search(b, t, search, NULL, NULL),
-			btree_bkey_last(b, t));
+	bch2_btree_node_iter_init_from_start(iter, b);
 
-	bch2_btree_node_iter_sort(iter, b);
+	while ((k = bch2_btree_node_iter_peek(iter, b)) &&
+	       bkey_iter_pos_cmp(b, k, search) < 0)
+		bch2_btree_node_iter_advance(iter, b);
 }
 
 /**
- * bch_btree_node_iter_init - initialize a btree node iterator, starting from a
+ * bch2_btree_node_iter_init - initialize a btree node iterator, starting from a
  * given position
  *
+ * @iter:	iterator to initialize
+ * @b:		btree node to search
+ * @search:	search key
+ *
  * Main entry point to the lookup code for individual btree nodes:
  *
  * NOTE:
@@ -1556,7 +1303,7 @@ static void btree_node_iter_init_pack_failed(struct btree_node_iter *iter,
  *    to the search key is going to have 0 sectors after the search key.
  *
  *    But this does mean that we can't just search for
- *    bkey_successor(start_of_range) to get the first extent that overlaps with
+ *    bpos_successor(start_of_range) to get the first extent that overlaps with
  *    the range we want - if we're unlucky and there's an extent that ends
  *    exactly where we searched, then there could be a deleted key at the same
  *    position and we'd get that when we search instead of the preceding extent
@@ -1569,11 +1316,13 @@ __flatten
 void bch2_btree_node_iter_init(struct btree_node_iter *iter,
 			       struct btree *b, struct bpos *search)
 {
-	struct bset_tree *t;
 	struct bkey_packed p, *packed_search = NULL;
 	struct btree_node_iter_set *pos = iter->data;
+	struct bkey_packed *k[MAX_BSETS];
+	unsigned i;
 
-	EBUG_ON(bkey_cmp(*search, b->data->min_key) < 0);
+	EBUG_ON(bpos_lt(*search, b->data->min_key));
+	EBUG_ON(bpos_gt(*search, b->data->max_key));
 	bset_aux_tree_verify(b);
 
 	memset(iter, 0, sizeof(*iter));
@@ -1590,14 +1339,20 @@ void bch2_btree_node_iter_init(struct btree_node_iter *iter,
 		return;
 	}
 
-	for_each_bset(b, t) {
-		struct bkey_packed *k = bch2_bset_search(b, t, search,
-							 packed_search, &p);
+	for (i = 0; i < b->nsets; i++) {
+		k[i] = __bch2_bset_search(b, b->set + i, search, &p);
+		prefetch_four_cachelines(k[i]);
+	}
+
+	for (i = 0; i < b->nsets; i++) {
+		struct bset_tree *t = b->set + i;
 		struct bkey_packed *end = btree_bkey_last(b, t);
 
-		if (k != end)
+		k[i] = bch2_bset_search_linear(b, t, search,
+					       packed_search, &p, k[i]);
+		if (k[i] != end)
 			*pos++ = (struct btree_node_iter_set) {
-				__btree_node_key_to_offset(b, k),
+				__btree_node_key_to_offset(b, k[i]),
 				__btree_node_key_to_offset(b, end)
 			};
 	}
@@ -1677,7 +1432,10 @@ static inline void __bch2_btree_node_iter_advance(struct btree_node_iter *iter,
 	EBUG_ON(iter->data->k > iter->data->end);
 
 	if (unlikely(__btree_node_iter_set_end(iter, 0))) {
-		bch2_btree_node_iter_set_drop(iter, iter->data);
+		/* avoid an expensive memmove call: */
+		iter->data[0] = iter->data[1];
+		iter->data[1] = iter->data[2];
+		iter->data[2] = (struct btree_node_iter_set) { 0, 0 };
 		return;
 	}
 
@@ -1696,7 +1454,7 @@ static inline void __bch2_btree_node_iter_advance(struct btree_node_iter *iter,
 void bch2_btree_node_iter_advance(struct btree_node_iter *iter,
 				  struct btree *b)
 {
-	if (btree_keys_expensive_checks(b)) {
+	if (bch2_expensive_debug_checks) {
 		bch2_btree_node_iter_verify(iter, b);
 		bch2_btree_node_iter_next_check(iter, b);
 	}
@@ -1715,7 +1473,8 @@ struct bkey_packed *bch2_btree_node_iter_prev_all(struct btree_node_iter *iter,
 	struct bset_tree *t;
 	unsigned end = 0;
 
-	bch2_btree_node_iter_verify(iter, b);
+	if (bch2_expensive_debug_checks)
+		bch2_btree_node_iter_verify(iter, b);
 
 	for_each_bset(b, t) {
 		k = bch2_bkey_prev_all(b, t,
@@ -1750,19 +1509,19 @@ found:
 	iter->data[0].k = __btree_node_key_to_offset(b, prev);
 	iter->data[0].end = end;
 
-	bch2_btree_node_iter_verify(iter, b);
+	if (bch2_expensive_debug_checks)
+		bch2_btree_node_iter_verify(iter, b);
 	return prev;
 }
 
-struct bkey_packed *bch2_btree_node_iter_prev_filter(struct btree_node_iter *iter,
-						     struct btree *b,
-						     unsigned min_key_type)
+struct bkey_packed *bch2_btree_node_iter_prev(struct btree_node_iter *iter,
+					      struct btree *b)
 {
 	struct bkey_packed *prev;
 
 	do {
 		prev = bch2_btree_node_iter_prev_all(iter, b);
-	} while (prev && prev->type < min_key_type);
+	} while (prev && bkey_deleted(prev));
 
 	return prev;
 }
@@ -1778,9 +1537,9 @@ struct bkey_s_c bch2_btree_node_iter_peek_unpack(struct btree_node_iter *iter,
 
 /* Mergesort */
 
-void bch2_btree_keys_stats(struct btree *b, struct bset_stats *stats)
+void bch2_btree_keys_stats(const struct btree *b, struct bset_stats *stats)
 {
-	struct bset_tree *t;
+	const struct bset_tree *t;
 
 	for_each_bset(b, t) {
 		enum bset_aux_tree_type type = bset_aux_tree_type(t);
@@ -1794,17 +1553,9 @@ void bch2_btree_keys_stats(struct btree *b, struct bset_stats *stats)
 			stats->floats += t->size - 1;
 
 			for (j = 1; j < t->size; j++)
-				switch (bkey_float(b, t, j)->exponent) {
-				case BFLOAT_FAILED_UNPACKED:
-					stats->failed_unpacked++;
-					break;
-				case BFLOAT_FAILED_PREV:
-					stats->failed_prev++;
-					break;
-				case BFLOAT_FAILED_OVERFLOW:
-					stats->failed_overflow++;
-					break;
-				}
+				stats->failed +=
+					bkey_float(b, t, j)->exponent ==
+					BFLOAT_FAILED;
 		}
 	}
 }
@@ -1813,14 +1564,9 @@ void bch2_bfloat_to_text(struct printbuf *out, struct btree *b,
 			 struct bkey_packed *k)
 {
 	struct bset_tree *t = bch2_bkey_to_bset(b, k);
-	struct bkey_packed *l, *r, *p;
-	struct bkey uk, up;
-	char buf1[200], buf2[200];
+	struct bkey uk;
 	unsigned j, inorder;
 
-	if (out->pos != out->end)
-		*out->pos = '\0';
-
 	if (!bset_has_ro_aux_tree(t))
 		return;
 
@@ -1828,54 +1574,19 @@ void bch2_bfloat_to_text(struct printbuf *out, struct btree *b,
 	if (!inorder || inorder >= t->size)
 		return;
 
-	j = __inorder_to_eytzinger1(inorder, t->size, t->extra);
+	j = __inorder_to_eytzinger1(inorder, t->size - 1, t->extra);
 	if (k != tree_to_bkey(b, t, j))
 		return;
 
 	switch (bkey_float(b, t, j)->exponent) {
-	case BFLOAT_FAILED_UNPACKED:
+	case BFLOAT_FAILED:
 		uk = bkey_unpack_key(b, k);
-		pr_buf(out,
+		prt_printf(out,
 		       "    failed unpacked at depth %u\n"
-		       "\t%llu:%llu\n",
-		       ilog2(j),
-		       uk.p.inode, uk.p.offset);
-		break;
-	case BFLOAT_FAILED_PREV:
-		p = tree_to_prev_bkey(b, t, j);
-		l = is_power_of_2(j)
-			? btree_bkey_first(b, t)
-			: tree_to_prev_bkey(b, t, j >> ffs(j));
-		r = is_power_of_2(j + 1)
-			? bch2_bkey_prev_all(b, t, btree_bkey_last(b, t))
-			: tree_to_bkey(b, t, j >> (ffz(j) + 1));
-
-		up = bkey_unpack_key(b, p);
-		uk = bkey_unpack_key(b, k);
-		bch2_to_binary(buf1, high_word(&b->format, p), b->nr_key_bits);
-		bch2_to_binary(buf2, high_word(&b->format, k), b->nr_key_bits);
-
-		pr_buf(out,
-		       "    failed prev at depth %u\n"
-		       "\tkey starts at bit %u but first differing bit at %u\n"
-		       "\t%llu:%llu\n"
-		       "\t%llu:%llu\n"
-		       "\t%s\n"
-		       "\t%s\n",
-		       ilog2(j),
-		       bch2_bkey_greatest_differing_bit(b, l, r),
-		       bch2_bkey_greatest_differing_bit(b, p, k),
-		       uk.p.inode, uk.p.offset,
-		       up.p.inode, up.p.offset,
-		       buf1, buf2);
-		break;
-	case BFLOAT_FAILED_OVERFLOW:
-		uk = bkey_unpack_key(b, k);
-		pr_buf(out,
-		       "    failed overflow at depth %u\n"
-		       "\t%llu:%llu\n",
-		       ilog2(j),
-		       uk.p.inode, uk.p.offset);
+		       "\t",
+		       ilog2(j));
+		bch2_bpos_to_text(out, uk.p);
+		prt_printf(out, "\n");
 		break;
 	}
 }