11 files changed, 135 insertions, 336 deletions

diff --git a/fs/bcachefs/alloc_background.c b/fs/bcachefs/alloc_background.c
index e5cbb4bce1ee..06032556d5c4 100644
--- a/fs/bcachefs/alloc_background.c
+++ b/fs/bcachefs/alloc_background.c
@@ -451,6 +451,8 @@ void __bch2_alloc_to_v4(struct bkey_s_c k, struct bch_alloc_v4 *out)
 
 		if (src < dst)
 			memset(src, 0, dst - src);
+
+		SET_BCH_ALLOC_V4_NR_BACKPOINTERS(out, 0);
 	} else {
 		struct bkey_alloc_unpacked u = bch2_alloc_unpack(k);
 
@@ -476,38 +478,26 @@ static noinline struct bkey_i_alloc_v4 *
 __bch2_alloc_to_v4_mut(struct btree_trans *trans, struct bkey_s_c k)
 {
 	struct bkey_i_alloc_v4 *ret;
+
+	ret = bch2_trans_kmalloc(trans, sizeof(struct bkey_i_alloc_v4));
+	if (IS_ERR(ret))
+		return ret;
+
 	if (k.k->type == KEY_TYPE_alloc_v4) {
-		struct bkey_s_c_alloc_v4 a = bkey_s_c_to_alloc_v4(k);
-		unsigned bytes = sizeof(struct bkey_i_alloc_v4) +
-			BCH_ALLOC_V4_NR_BACKPOINTERS(a.v) *
-			sizeof(struct bch_backpointer);
 		void *src, *dst;
 
-		/*
-		 * Reserve space for one more backpointer here:
-		 * Not sketchy at doing it this way, nope...
-		 */
-		ret = bch2_trans_kmalloc(trans, bytes + sizeof(struct bch_backpointer));
-		if (IS_ERR(ret))
-			return ret;
-
 		bkey_reassemble(&ret->k_i, k);
 
 		src = alloc_v4_backpointers(&ret->v);
 		SET_BCH_ALLOC_V4_BACKPOINTERS_START(&ret->v, BCH_ALLOC_V4_U64s);
 		dst = alloc_v4_backpointers(&ret->v);
 
-		memmove(dst, src, BCH_ALLOC_V4_NR_BACKPOINTERS(&ret->v) *
-			sizeof(struct bch_backpointer));
 		if (src < dst)
 			memset(src, 0, dst - src);
+
+		SET_BCH_ALLOC_V4_NR_BACKPOINTERS(&ret->v, 0);
 		set_alloc_v4_u64s(ret);
 	} else {
-		ret = bch2_trans_kmalloc(trans, sizeof(struct bkey_i_alloc_v4) +
-					 sizeof(struct bch_backpointer));
-		if (IS_ERR(ret))
-			return ret;
-
 		bkey_alloc_v4_init(&ret->k_i);
 		ret->k.p = k.k->p;
 		bch2_alloc_to_v4(k, &ret->v);
@@ -517,8 +507,12 @@ __bch2_alloc_to_v4_mut(struct btree_trans *trans, struct bkey_s_c k)
 
 static inline struct bkey_i_alloc_v4 *bch2_alloc_to_v4_mut_inlined(struct btree_trans *trans, struct bkey_s_c k)
 {
+	struct bkey_s_c_alloc_v4 a;
+
 	if (likely(k.k->type == KEY_TYPE_alloc_v4) &&
-	    BCH_ALLOC_V4_BACKPOINTERS_START(bkey_s_c_to_alloc_v4(k).v) == BCH_ALLOC_V4_U64s) {
+	    ((a = bkey_s_c_to_alloc_v4(k), true) &&
+	     BCH_ALLOC_V4_BACKPOINTERS_START(a.v) == BCH_ALLOC_V4_U64s &&
+	     BCH_ALLOC_V4_NR_BACKPOINTERS(a.v) == 0)) {
 		/*
 		 * Reserve space for one more backpointer here:
 		 * Not sketchy at doing it this way, nope...
diff --git a/fs/bcachefs/alloc_foreground.c b/fs/bcachefs/alloc_foreground.c
index 20c64882104e..368355de5f26 100644
--- a/fs/bcachefs/alloc_foreground.c
+++ b/fs/bcachefs/alloc_foreground.c
@@ -345,17 +345,17 @@ static struct open_bucket *try_alloc_bucket(struct btree_trans *trans, struct bc
 
 	if (!test_bit(BCH_FS_CHECK_BACKPOINTERS_DONE, &c->flags)) {
 		struct bch_backpointer bp;
-		u64 bp_offset = 0;
+		struct bpos bp_pos = POS_MIN;
 
 		ret = bch2_get_next_backpointer(trans, POS(ca->dev_idx, b), -1,
-						&bp_offset, &bp,
+						&bp_pos, &bp,
 						BTREE_ITER_NOPRESERVE);
 		if (ret) {
 			ob = ERR_PTR(ret);
 			goto err;
 		}
 
-		if (bp_offset != U64_MAX) {
+		if (!bkey_eq(bp_pos, POS_MAX)) {
 			/*
 			 * Bucket may have data in it - we don't call
 			 * bc2h_trans_inconnsistent() because fsck hasn't
diff --git a/fs/bcachefs/backpointers.c b/fs/bcachefs/backpointers.c
index 9121fae0fd6c..a3a1ed6e5968 100644
--- a/fs/bcachefs/backpointers.c
+++ b/fs/bcachefs/backpointers.c
@@ -69,6 +69,10 @@ void bch2_backpointer_to_text(struct printbuf *out, const struct bch_backpointer
 
 void bch2_backpointer_k_to_text(struct printbuf *out, struct bch_fs *c, struct bkey_s_c k)
 {
+	prt_str(out, "bucket=");
+	bch2_bpos_to_text(out, bp_pos_to_bucket(c, k.k->p));
+	prt_str(out, " ");
+
 	bch2_backpointer_to_text(out, bkey_s_c_to_backpointer(k).v);
 }
 
@@ -81,117 +85,6 @@ void bch2_backpointer_swab(struct bkey_s k)
 	bch2_bpos_swab(&bp.v->pos);
 }
 
-#define BACKPOINTER_OFFSET_MAX	((1ULL << 40) - 1)
-
-static inline int backpointer_cmp(struct bch_backpointer l, struct bch_backpointer r)
-{
-	return cmp_int(l.bucket_offset, r.bucket_offset);
-}
-
-static int bch2_backpointer_del_by_offset(struct btree_trans *trans,
-					  struct bpos bucket,
-					  u64 bp_offset,
-					  struct bch_backpointer bp)
-{
-	struct bch_fs *c = trans->c;
-	struct btree_iter iter;
-	struct bkey_s_c k;
-	int ret;
-
-	if (bp_offset < BACKPOINTER_OFFSET_MAX) {
-		struct bch_backpointer *bps;
-		struct bkey_i_alloc_v4 *a;
-		unsigned i, nr;
-
-		bch2_trans_iter_init(trans, &iter, BTREE_ID_alloc,
-				     bucket,
-				     BTREE_ITER_INTENT|
-				     BTREE_ITER_SLOTS|
-				     BTREE_ITER_WITH_UPDATES);
-		k = bch2_btree_iter_peek_slot(&iter);
-		ret = bkey_err(k);
-		if (ret)
-			goto err;
-
-		if (k.k->type != KEY_TYPE_alloc_v4) {
-			ret = -ENOENT;
-			goto err;
-		}
-
-		a = bch2_alloc_to_v4_mut(trans, k);
-		ret = PTR_ERR_OR_ZERO(a);
-		if (ret)
-			goto err;
-		bps = alloc_v4_backpointers(&a->v);
-		nr = BCH_ALLOC_V4_NR_BACKPOINTERS(&a->v);
-
-		for (i = 0; i < nr; i++) {
-			if (bps[i].bucket_offset == bp_offset)
-				goto found;
-			if (bps[i].bucket_offset > bp_offset)
-				break;
-		}
-
-		ret = -ENOENT;
-		goto err;
-found:
-		if (memcmp(&bps[i], &bp, sizeof(bp))) {
-			ret = -ENOENT;
-			goto err;
-		}
-		array_remove_item(bps, nr, i);
-		SET_BCH_ALLOC_V4_NR_BACKPOINTERS(&a->v, nr);
-		set_alloc_v4_u64s(a);
-		ret = bch2_trans_update(trans, &iter, &a->k_i, 0);
-	} else {
-		bp_offset -= BACKPOINTER_OFFSET_MAX;
-
-		bch2_trans_iter_init(trans, &iter, BTREE_ID_backpointers,
-				     bucket_pos_to_bp(c, bucket, bp_offset),
-				     BTREE_ITER_INTENT|
-				     BTREE_ITER_SLOTS|
-				     BTREE_ITER_WITH_UPDATES);
-		k = bch2_btree_iter_peek_slot(&iter);
-		ret = bkey_err(k);
-		if (ret)
-			goto err;
-
-		if (k.k->type != KEY_TYPE_backpointer ||
-		    memcmp(bkey_s_c_to_backpointer(k).v, &bp, sizeof(bp))) {
-			ret = -ENOENT;
-			goto err;
-		}
-
-		ret = bch2_btree_delete_at(trans, &iter, 0);
-	}
-err:
-	bch2_trans_iter_exit(trans, &iter);
-	return ret;
-}
-
-bool bch2_bucket_backpointer_del(struct btree_trans *trans,
-				 struct bkey_i_alloc_v4 *a,
-				 struct bch_backpointer bp)
-{
-	struct bch_backpointer *bps = alloc_v4_backpointers(&a->v);
-	unsigned i, nr = BCH_ALLOC_V4_NR_BACKPOINTERS(&a->v);
-
-	for (i = 0; i < nr; i++) {
-		int cmp = backpointer_cmp(bps[i], bp) ?:
-			memcmp(&bps[i], &bp, sizeof(bp));
-		if (!cmp) {
-			array_remove_item(bps, nr, i);
-			SET_BCH_ALLOC_V4_NR_BACKPOINTERS(&a->v, nr);
-			set_alloc_v4_u64s(a);
-			return true;
-		}
-		if (cmp >= 0)
-			break;
-	}
-
-	return false;
-}
-
 static noinline int backpointer_mod_err(struct btree_trans *trans,
 					struct bch_backpointer bp,
 					struct bkey_s_c bp_k,
@@ -245,7 +138,7 @@ static noinline int backpointer_mod_err(struct btree_trans *trans,
 }
 
 int bch2_bucket_backpointer_mod_nowritebuffer(struct btree_trans *trans,
-				struct bkey_i_alloc_v4 *a,
+				struct bpos bucket,
 				struct bch_backpointer bp,
 				struct bkey_s_c orig_k,
 				bool insert)
@@ -262,7 +155,7 @@ int bch2_bucket_backpointer_mod_nowritebuffer(struct btree_trans *trans,
 		return ret;
 
 	bkey_backpointer_init(&bp_k->k_i);
-	bp_k->k.p = bucket_pos_to_bp(c, a->k.p, bp.bucket_offset);
+	bp_k->k.p = bucket_pos_to_bp(c, bucket, bp.bucket_offset);
 	bp_k->v = bp;
 
 	if (!insert) {
@@ -271,7 +164,7 @@ int bch2_bucket_backpointer_mod_nowritebuffer(struct btree_trans *trans,
 	}
 
 	bch2_trans_iter_init(trans, &bp_iter, BTREE_ID_backpointers,
-			     bucket_pos_to_bp(c, a->k.p, bp.bucket_offset),
+			     bp_k->k.p,
 			     BTREE_ITER_INTENT|
 			     BTREE_ITER_SLOTS|
 			     BTREE_ITER_WITH_UPDATES);
@@ -298,94 +191,62 @@ err:
 /*
  * Find the next backpointer >= *bp_offset:
  */
-int __bch2_get_next_backpointer(struct btree_trans *trans,
-				struct bpos bucket, int gen,
-				u64 *bp_offset,
-				struct bpos *bp_pos_ret,
-				struct bch_backpointer *dst,
-				unsigned iter_flags)
+int bch2_get_next_backpointer(struct btree_trans *trans,
+			      struct bpos bucket, int gen,
+			      struct bpos *bp_pos,
+			      struct bch_backpointer *bp,
+			      unsigned iter_flags)
 {
 	struct bch_fs *c = trans->c;
-	struct bpos bp_pos, bp_end_pos;
-	struct btree_iter alloc_iter, bp_iter = { NULL };
+	struct bpos bp_end_pos = bucket_pos_to_bp(c, bpos_nosnap_successor(bucket), 0);
+	struct btree_iter alloc_iter = { NULL }, bp_iter = { NULL };
 	struct bkey_s_c k;
-	struct bkey_s_c_alloc_v4 a;
-	size_t i;
-	int ret;
-
-	if (*bp_offset == U64_MAX)
-		return 0;
-
-	bp_pos = bucket_pos_to_bp(c, bucket,
-				  max(*bp_offset, BACKPOINTER_OFFSET_MAX) - BACKPOINTER_OFFSET_MAX);
-	bp_end_pos = bucket_pos_to_bp(c, bpos_nosnap_successor(bucket), 0);
-
-	bch2_trans_iter_init(trans, &alloc_iter, BTREE_ID_alloc,
-			     bucket, BTREE_ITER_CACHED);
-	k = bch2_btree_iter_peek_slot(&alloc_iter);
-	ret = bkey_err(k);
-	if (ret)
-		goto out;
-
-	if (k.k->type != KEY_TYPE_alloc_v4)
-		goto done;
+	int ret = 0;
 
-	a = bkey_s_c_to_alloc_v4(k);
-	if (gen >= 0 && a.v->gen != gen)
+	if (bpos_ge(*bp_pos, bp_end_pos))
 		goto done;
 
-	for (i = 0; i < BCH_ALLOC_V4_NR_BACKPOINTERS(a.v); i++) {
-		if (alloc_v4_backpointers_c(a.v)[i].bucket_offset < *bp_offset)
-			continue;
+	if (gen >= 0) {
+		bch2_trans_iter_init(trans, &alloc_iter, BTREE_ID_alloc,
+				     bucket, BTREE_ITER_CACHED|iter_flags);
+		k = bch2_btree_iter_peek_slot(&alloc_iter);
+		ret = bkey_err(k);
+		if (ret)
+			goto out;
 
-		*dst = alloc_v4_backpointers_c(a.v)[i];
-		*bp_offset = dst->bucket_offset;
-		goto out;
+		if (k.k->type != KEY_TYPE_alloc_v4 ||
+		    bkey_s_c_to_alloc_v4(k).v->gen != gen)
+			goto done;
 	}
 
+	*bp_pos = bpos_max(*bp_pos, bucket_pos_to_bp(c, bucket, 0));
+
 	for_each_btree_key_norestart(trans, bp_iter, BTREE_ID_backpointers,
-				     bp_pos, 0, k, ret) {
+				     *bp_pos, iter_flags, k, ret) {
 		if (bpos_ge(k.k->p, bp_end_pos))
 			break;
 
-		if (k.k->type != KEY_TYPE_backpointer)
-			continue;
-
-		*dst = *bkey_s_c_to_backpointer(k).v;
-		*bp_offset = dst->bucket_offset + BACKPOINTER_OFFSET_MAX;
-		*bp_pos_ret = k.k->p;
+		*bp_pos = k.k->p;
+		*bp = *bkey_s_c_to_backpointer(k).v;
 		goto out;
 	}
 done:
-	*bp_offset = U64_MAX;
+	*bp_pos = SPOS_MAX;
 out:
 	bch2_trans_iter_exit(trans, &bp_iter);
 	bch2_trans_iter_exit(trans, &alloc_iter);
 	return ret;
 }
 
-int bch2_get_next_backpointer(struct btree_trans *trans,
-			      struct bpos bucket, int gen,
-			      u64 *bp_offset,
-			      struct bch_backpointer *dst,
-			      unsigned iter_flags)
-{
-	struct bpos bp_pos;
-
-	return __bch2_get_next_backpointer(trans, bucket, gen,
-					   bp_offset, &bp_pos,
-					   dst, iter_flags);
-}
-
 static void backpointer_not_found(struct btree_trans *trans,
-				  struct bpos bucket,
-				  u64 bp_offset,
+				  struct bpos bp_pos,
 				  struct bch_backpointer bp,
 				  struct bkey_s_c k,
 				  const char *thing_it_points_to)
 {
 	struct bch_fs *c = trans->c;
 	struct printbuf buf = PRINTBUF;
+	struct bpos bucket = bp_pos_to_bucket(c, bp_pos);
 
 	if (likely(!bch2_backpointers_no_use_write_buffer))
 		return;
@@ -396,14 +257,9 @@ static void backpointer_not_found(struct btree_trans *trans,
 	bch2_bpos_to_text(&buf, bucket);
 	prt_printf(&buf, "\n  ");
 
-	if (bp_offset >= BACKPOINTER_OFFSET_MAX) {
-		struct bpos bp_pos =
-			bucket_pos_to_bp(c, bucket,
-					bp_offset - BACKPOINTER_OFFSET_MAX);
-		prt_printf(&buf, "backpointer pos: ");
-		bch2_bpos_to_text(&buf, bp_pos);
-		prt_printf(&buf, "\n  ");
-	}
+	prt_printf(&buf, "backpointer pos: ");
+	bch2_bpos_to_text(&buf, bp_pos);
+	prt_printf(&buf, "\n  ");
 
 	bch2_backpointer_to_text(&buf, &bp);
 	prt_printf(&buf, "\n  ");
@@ -418,12 +274,12 @@ static void backpointer_not_found(struct btree_trans *trans,
 
 struct bkey_s_c bch2_backpointer_get_key(struct btree_trans *trans,
 					 struct btree_iter *iter,
-					 struct bpos bucket,
-					 u64 bp_offset,
+					 struct bpos bp_pos,
 					 struct bch_backpointer bp,
 					 unsigned iter_flags)
 {
 	struct bch_fs *c = trans->c;
+	struct bpos bucket = bp_pos_to_bucket(c, bp_pos);
 	struct bkey_s_c k;
 
 	bch2_trans_node_iter_init(trans, iter,
@@ -456,7 +312,7 @@ struct bkey_s_c bch2_backpointer_get_key(struct btree_trans *trans,
 			 * been written out yet - backpointer_get_node() checks for
 			 * this:
 			 */
-			b = bch2_backpointer_get_node(trans, iter, bucket, bp_offset, bp);
+			b = bch2_backpointer_get_node(trans, iter, bp_pos, bp);
 			if (!IS_ERR_OR_NULL(b))
 				return bkey_i_to_s_c(&b->key);
 
@@ -467,7 +323,7 @@ struct bkey_s_c bch2_backpointer_get_key(struct btree_trans *trans,
 			return bkey_s_c_null;
 		}
 
-		backpointer_not_found(trans, bucket, bp_offset, bp, k, "extent");
+		backpointer_not_found(trans, bp_pos, bp, k, "extent");
 	}
 
 	return bkey_s_c_null;
@@ -475,11 +331,11 @@ struct bkey_s_c bch2_backpointer_get_key(struct btree_trans *trans,
 
 struct btree *bch2_backpointer_get_node(struct btree_trans *trans,
 					struct btree_iter *iter,
-					struct bpos bucket,
-					u64 bp_offset,
+					struct bpos bp_pos,
 					struct bch_backpointer bp)
 {
 	struct bch_fs *c = trans->c;
+	struct bpos bucket = bp_pos_to_bucket(c, bp_pos);
 	struct btree *b;
 
 	BUG_ON(!bp.level);
@@ -502,7 +358,7 @@ struct btree *bch2_backpointer_get_node(struct btree_trans *trans,
 	if (b && btree_node_will_make_reachable(b)) {
 		b = ERR_PTR(-BCH_ERR_backpointer_to_overwritten_btree_node);
 	} else {
-		backpointer_not_found(trans, bucket, bp_offset, bp,
+		backpointer_not_found(trans, bp_pos, bp,
 				      bkey_i_to_s_c(&b->key), "btree node");
 		b = NULL;
 	}
@@ -571,7 +427,7 @@ struct bpos_level {
 };
 
 static int check_bp_exists(struct btree_trans *trans,
-			   struct bpos bucket_pos,
+			   struct bpos bucket,
 			   struct bch_backpointer bp,
 			   struct bkey_s_c orig_k,
 			   struct bpos bucket_start,
@@ -579,40 +435,20 @@ static int check_bp_exists(struct btree_trans *trans,
 			   struct bpos_level *last_flushed)
 {
 	struct bch_fs *c = trans->c;
-	struct btree_iter alloc_iter, bp_iter = { NULL };
+	struct btree_iter bp_iter = { NULL };
 	struct printbuf buf = PRINTBUF;
-	struct bkey_s_c alloc_k, bp_k;
+	struct bkey_s_c bp_k;
 	int ret;
 
-	if (bpos_lt(bucket_pos, bucket_start) ||
-	    bpos_gt(bucket_pos, bucket_end))
+	if (bpos_lt(bucket, bucket_start) ||
+	    bpos_gt(bucket, bucket_end))
 		return 0;
 
-	bch2_trans_iter_init(trans, &alloc_iter, BTREE_ID_alloc, bucket_pos, 0);
-	alloc_k = bch2_btree_iter_peek_slot(&alloc_iter);
-	ret = bkey_err(alloc_k);
-	if (ret)
-		goto err;
-
-	if (alloc_k.k->type == KEY_TYPE_alloc_v4) {
-		struct bkey_s_c_alloc_v4 a = bkey_s_c_to_alloc_v4(alloc_k);
-		const struct bch_backpointer *bps = alloc_v4_backpointers_c(a.v);
-		unsigned i, nr = BCH_ALLOC_V4_NR_BACKPOINTERS(a.v);
-
-		for (i = 0; i < nr; i++) {
-			int cmp = backpointer_cmp(bps[i], bp) ?:
-				memcmp(&bps[i], &bp, sizeof(bp));
-			if (!cmp)
-				goto out;
-			if (cmp >= 0)
-				break;
-		}
-	} else {
+	if (!bch2_dev_bucket_exists(c, bucket))
 		goto missing;
-	}
 
 	bch2_trans_iter_init(trans, &bp_iter, BTREE_ID_backpointers,
-			     bucket_pos_to_bp(c, bucket_pos, bp.bucket_offset),
+			     bucket_pos_to_bp(c, bucket, bp.bucket_offset),
 			     0);
 	bp_k = bch2_btree_iter_peek_slot(&bp_iter);
 	ret = bkey_err(bp_k);
@@ -636,11 +472,9 @@ out:
 err:
 fsck_err:
 	bch2_trans_iter_exit(trans, &bp_iter);
-	bch2_trans_iter_exit(trans, &alloc_iter);
 	printbuf_exit(&buf);
 	return ret;
 missing:
-
 	prt_printf(&buf, "missing backpointer for btree=%s l=%u ",
 	       bch2_btree_ids[bp.btree_id], bp.level);
 	bch2_bkey_val_to_text(&buf, c, orig_k);
@@ -649,12 +483,8 @@ missing:
 
 	if (c->sb.version < bcachefs_metadata_version_backpointers ||
 	    c->opts.reconstruct_alloc ||
-	    fsck_err(c, "%s", buf.buf)) {
-		struct bkey_i_alloc_v4 *a = bch2_alloc_to_v4_mut(trans, alloc_k);
-
-		ret   = PTR_ERR_OR_ZERO(a) ?:
-			bch2_bucket_backpointer_mod(trans, a, bp, orig_k, true);
-	}
+	    fsck_err(c, "%s", buf.buf))
+		ret = bch2_bucket_backpointer_mod(trans, bucket, bp, orig_k, true);
 
 	goto out;
 }
@@ -953,53 +783,40 @@ int bch2_check_extents_to_backpointers(struct bch_fs *c)
 }
 
 static int check_one_backpointer(struct btree_trans *trans,
-				 struct bpos bucket,
-				 u64 *bp_offset,
 				 struct bbpos start,
 				 struct bbpos end,
+				 struct bkey_s_c_backpointer bp,
 				 struct bpos *last_flushed_pos)
 {
 	struct bch_fs *c = trans->c;
 	struct btree_iter iter;
-	struct bch_backpointer bp;
-	struct bbpos pos;
-	struct bpos bp_pos;
+	struct bbpos pos = bp_to_bbpos(*bp.v);
 	struct bkey_s_c k;
 	struct printbuf buf = PRINTBUF;
 	int ret;
 
-	ret = __bch2_get_next_backpointer(trans, bucket, -1, bp_offset, &bp_pos, &bp, 0);
-	if (ret || *bp_offset == U64_MAX)
-		return ret;
-
-	pos = bp_to_bbpos(bp);
 	if (bbpos_cmp(pos, start) < 0 ||
 	    bbpos_cmp(pos, end) > 0)
 		return 0;
 
-	k = bch2_backpointer_get_key(trans, &iter, bucket, *bp_offset, bp, 0);
+	k = bch2_backpointer_get_key(trans, &iter, bp.k->p, *bp.v, 0);
 	ret = bkey_err(k);
 	if (ret == -BCH_ERR_backpointer_to_overwritten_btree_node)
 		return 0;
 	if (ret)
 		return ret;
 
-	if (!k.k && !bpos_eq(*last_flushed_pos, bp_pos)) {
-		*last_flushed_pos = bp_pos;
+	if (!k.k && !bpos_eq(*last_flushed_pos, bp.k->p)) {
+		*last_flushed_pos = bp.k->p;
 		ret = bch2_btree_write_buffer_flush_sync(trans) ?:
 			-BCH_ERR_transaction_restart_write_buffer_flush;
 		goto out;
 	}
 
 	if (fsck_err_on(!k.k, c,
-			"backpointer for %llu:%llu:%llu (btree pos %llu:%llu) points to missing extent\n  %s",
-			bucket.inode, bucket.offset, (u64) bp.bucket_offset,
-			bp_pos.inode, bp_pos.offset,
-			(bch2_backpointer_to_text(&buf, &bp), buf.buf))) {
-		ret = bch2_backpointer_del_by_offset(trans, bucket, *bp_offset, bp);
-		if (ret == -ENOENT)
-			bch_err(c, "backpointer at %llu not found", *bp_offset);
-	}
+			"backpointer for missing extent\n  %s",
+			(bch2_backpointer_k_to_text(&buf, c, bp.s_c), buf.buf)))
+		return bch2_btree_delete_at_buffered(trans, BTREE_ID_backpointers, bp.k->p);
 out:
 fsck_err:
 	bch2_trans_iter_exit(trans, &iter);
@@ -1014,25 +831,13 @@ static int bch2_check_backpointers_to_extents_pass(struct btree_trans *trans,
 	struct btree_iter iter;
 	struct bkey_s_c k;
 	struct bpos last_flushed_pos = SPOS_MAX;
-	int ret = 0;
 
-	for_each_btree_key(trans, iter, BTREE_ID_alloc, POS_MIN,
-			   BTREE_ITER_PREFETCH, k, ret) {
-		u64 bp_offset = 0;
-
-		while (!(ret = commit_do(trans, NULL, NULL,
-					 BTREE_INSERT_LAZY_RW|
-					 BTREE_INSERT_NOFAIL,
-				check_one_backpointer(trans, iter.pos, &bp_offset,
-						      start, end, &last_flushed_pos))) &&
-		       bp_offset < U64_MAX)
-			bp_offset++;
-
-		if (ret)
-			break;
-	}
-	bch2_trans_iter_exit(trans, &iter);
-	return ret < 0 ? ret : 0;
+	return for_each_btree_key_commit(trans, iter, BTREE_ID_backpointers,
+				  POS_MIN, BTREE_ITER_PREFETCH, k,
+				  NULL, NULL, BTREE_INSERT_LAZY_RW|BTREE_INSERT_NOFAIL,
+		check_one_backpointer(trans, start, end,
+				      bkey_s_c_to_backpointer(k),
+				      &last_flushed_pos));
 }
 
 int bch2_check_backpointers_to_extents(struct bch_fs *c)
diff --git a/fs/bcachefs/backpointers.h b/fs/bcachefs/backpointers.h
index ce75b8f50241..9c03709ade50 100644
--- a/fs/bcachefs/backpointers.h
+++ b/fs/bcachefs/backpointers.h
@@ -53,16 +53,11 @@ static inline struct bpos bucket_pos_to_bp(const struct bch_fs *c,
 	return ret;
 }
 
-bool bch2_bucket_backpointer_del(struct btree_trans *,
-				struct bkey_i_alloc_v4 *,
-				struct bch_backpointer);
-
-int bch2_bucket_backpointer_mod_nowritebuffer(struct btree_trans *,
-				struct bkey_i_alloc_v4 *,
+int bch2_bucket_backpointer_mod_nowritebuffer(struct btree_trans *, struct bpos,
 				struct bch_backpointer, struct bkey_s_c, bool);
 
 static inline int bch2_bucket_backpointer_mod(struct btree_trans *trans,
-				struct bkey_i_alloc_v4 *a,
+				struct bpos bucket,
 				struct bch_backpointer bp,
 				struct bkey_s_c orig_k,
 				bool insert)
@@ -71,13 +66,8 @@ static inline int bch2_bucket_backpointer_mod(struct btree_trans *trans,
 	struct bkey_i_backpointer *bp_k;
 	int ret;
 
-	if (!insert &&
-	    unlikely(BCH_ALLOC_V4_NR_BACKPOINTERS(&a->v)) &&
-	    bch2_bucket_backpointer_del(trans, a, bp))
-		return 0;
-
 	if (unlikely(bch2_backpointers_no_use_write_buffer))
-		return bch2_bucket_backpointer_mod_nowritebuffer(trans, a, bp, orig_k, insert);
+		return bch2_bucket_backpointer_mod_nowritebuffer(trans, bucket, bp, orig_k, insert);
 
 	bp_k = bch2_trans_kmalloc_nomemzero(trans, sizeof(struct bkey_i_backpointer));
 	ret = PTR_ERR_OR_ZERO(bp_k);
@@ -85,7 +75,7 @@ static inline int bch2_bucket_backpointer_mod(struct btree_trans *trans,
 		return ret;
 
 	bkey_backpointer_init(&bp_k->k_i);
-	bp_k->k.p = bucket_pos_to_bp(c, a->k.p, bp.bucket_offset);
+	bp_k->k.p = bucket_pos_to_bp(c, bucket, bp.bucket_offset);
 	bp_k->v = bp;
 
 	if (!insert) {
@@ -126,12 +116,12 @@ static inline void bch2_extent_ptr_to_bp(struct bch_fs *c,
 }
 
 int bch2_get_next_backpointer(struct btree_trans *, struct bpos, int,
-			      u64 *, struct bch_backpointer *, unsigned);
+			      struct bpos *, struct bch_backpointer *, unsigned);
 struct bkey_s_c bch2_backpointer_get_key(struct btree_trans *, struct btree_iter *,
-					 struct bpos, u64, struct bch_backpointer,
+					 struct bpos, struct bch_backpointer,
 					 unsigned);
 struct btree *bch2_backpointer_get_node(struct btree_trans *, struct btree_iter *,
-					struct bpos, u64, struct bch_backpointer);
+					struct bpos, struct bch_backpointer);
 
 int bch2_check_btree_backpointers(struct bch_fs *);
 int bch2_check_extents_to_backpointers(struct bch_fs *);
diff --git a/fs/bcachefs/bcachefs_format.h b/fs/bcachefs/bcachefs_format.h
index 8b29e462492b..7d1c0b1e3c54 100644
--- a/fs/bcachefs/bcachefs_format.h
+++ b/fs/bcachefs/bcachefs_format.h
@@ -1554,7 +1554,8 @@ struct bch_sb_field_journal_seq_blacklist {
 	x(unwritten_extents,		24)		\
 	x(bucket_gens,			25)		\
 	x(lru_v2,			26)		\
-	x(fragmentation_lru,		27)
+	x(fragmentation_lru,		27)		\
+	x(no_bps_in_alloc_keys,		28)
 
 enum bcachefs_metadata_version {
 	bcachefs_metadata_version_min = 9,
diff --git a/fs/bcachefs/btree_update.h b/fs/bcachefs/btree_update.h
index 5d5321dd42e8..4adb6f646655 100644
--- a/fs/bcachefs/btree_update.h
+++ b/fs/bcachefs/btree_update.h
@@ -60,6 +60,7 @@ enum btree_insert_flags {
 int bch2_btree_delete_extent_at(struct btree_trans *, struct btree_iter *,
 				unsigned, unsigned);
 int bch2_btree_delete_at(struct btree_trans *, struct btree_iter *, unsigned);
+int bch2_btree_delete_at_buffered(struct btree_trans *, enum btree_id, struct bpos);
 
 int bch2_btree_insert_nonextent(struct btree_trans *, enum btree_id,
 				struct bkey_i *, enum btree_update_flags);
diff --git a/fs/bcachefs/btree_update_leaf.c b/fs/bcachefs/btree_update_leaf.c
index 02d264b858ab..b8299914a0ab 100644
--- a/fs/bcachefs/btree_update_leaf.c
+++ b/fs/bcachefs/btree_update_leaf.c
@@ -1802,6 +1802,20 @@ int bch2_btree_delete_at(struct btree_trans *trans,
 	return bch2_btree_delete_extent_at(trans, iter, 0, update_flags);
 }
 
+int bch2_btree_delete_at_buffered(struct btree_trans *trans,
+				  enum btree_id btree, struct bpos pos)
+{
+	struct bkey_i *k;
+
+	k = bch2_trans_kmalloc(trans, sizeof(*k));
+	if (IS_ERR(k))
+		return PTR_ERR(k);
+
+	bkey_init(&k->k);
+	k->k.p = pos;
+	return bch2_trans_update_buffered(trans, btree, k);
+}
+
 int bch2_btree_delete_range_trans(struct btree_trans *trans, enum btree_id id,
 				  struct bpos start, struct bpos end,
 				  unsigned update_flags,
diff --git a/fs/bcachefs/buckets.c b/fs/bcachefs/buckets.c
index 6e2e2ed72f65..f3cee8f2b793 100644
--- a/fs/bcachefs/buckets.c
+++ b/fs/bcachefs/buckets.c
@@ -1407,17 +1407,17 @@ static inline int bch2_trans_mark_pointer(struct btree_trans *trans,
 	bool insert = !(flags & BTREE_TRIGGER_OVERWRITE);
 	struct btree_iter iter;
 	struct bkey_i_alloc_v4 *a;
-	struct bpos bucket_pos;
+	struct bpos bucket;
 	struct bch_backpointer bp;
 	s64 sectors;
 	int ret;
 
-	bch2_extent_ptr_to_bp(trans->c, btree_id, level, k, p, &bucket_pos, &bp);
+	bch2_extent_ptr_to_bp(trans->c, btree_id, level, k, p, &bucket, &bp);
 	sectors = bp.bucket_len;
 	if (!insert)
 		sectors = -sectors;
 
-	a = bch2_trans_start_alloc_update(trans, &iter, bucket_pos);
+	a = bch2_trans_start_alloc_update(trans, &iter, bucket);
 	if (IS_ERR(a))
 		return PTR_ERR(a);
 
@@ -1428,7 +1428,7 @@ static inline int bch2_trans_mark_pointer(struct btree_trans *trans,
 		goto err;
 
 	if (!p.ptr.cached) {
-		ret = bch2_bucket_backpointer_mod(trans, a, bp, k, insert);
+		ret = bch2_bucket_backpointer_mod(trans, bucket, bp, k, insert);
 		if (ret)
 			goto err;
 	}
diff --git a/fs/bcachefs/ec.c b/fs/bcachefs/ec.c
index d295e5401c7a..1855d08efd4b 100644
--- a/fs/bcachefs/ec.c
+++ b/fs/bcachefs/ec.c
@@ -887,7 +887,7 @@ err:
 static int ec_stripe_update_extent(struct btree_trans *trans,
 				   struct bpos bucket, u8 gen,
 				   struct ec_stripe_buf *s,
-				   u64 *bp_offset)
+				   struct bpos *bp_pos)
 {
 	struct bch_fs *c = trans->c;
 	struct bch_backpointer bp;
@@ -900,10 +900,10 @@ static int ec_stripe_update_extent(struct btree_trans *trans,
 	int ret, dev, block;
 
 	ret = bch2_get_next_backpointer(trans, bucket, gen,
-				bp_offset, &bp, BTREE_ITER_CACHED);
+				bp_pos, &bp, BTREE_ITER_CACHED);
 	if (ret)
 		return ret;
-	if (*bp_offset == U64_MAX)
+	if (bpos_eq(*bp_pos, SPOS_MAX))
 		return 0;
 
 	if (bp.level) {
@@ -911,7 +911,7 @@ static int ec_stripe_update_extent(struct btree_trans *trans,
 		struct btree_iter node_iter;
 		struct btree *b;
 
-		b = bch2_backpointer_get_node(trans, &node_iter, bucket, *bp_offset, bp);
+		b = bch2_backpointer_get_node(trans, &node_iter, *bp_pos, bp);
 		bch2_trans_iter_exit(trans, &node_iter);
 
 		if (!b)
@@ -925,8 +925,7 @@ static int ec_stripe_update_extent(struct btree_trans *trans,
 		return -EIO;
 	}
 
-	k = bch2_backpointer_get_key(trans, &iter, bucket, *bp_offset, bp,
-				     BTREE_ITER_INTENT);
+	k = bch2_backpointer_get_key(trans, &iter, *bp_pos, bp, BTREE_ITER_INTENT);
 	ret = bkey_err(k);
 	if (ret)
 		return ret;
@@ -985,7 +984,7 @@ static int ec_stripe_update_bucket(struct btree_trans *trans, struct ec_stripe_b
 	struct bch_fs *c = trans->c;
 	struct bch_extent_ptr bucket = s->key.v.ptrs[block];
 	struct bpos bucket_pos = PTR_BUCKET_POS(c, &bucket);
-	u64 bp_offset = 0;
+	struct bpos bp_pos = POS_MIN;
 	int ret = 0;
 
 	while (1) {
@@ -993,13 +992,13 @@ static int ec_stripe_update_bucket(struct btree_trans *trans, struct ec_stripe_b
 				BTREE_INSERT_NOCHECK_RW|
 				BTREE_INSERT_NOFAIL,
 			ec_stripe_update_extent(trans, bucket_pos, bucket.gen,
-						s, &bp_offset));
+						s, &bp_pos));
 		if (ret)
 			break;
-		if (bp_offset == U64_MAX)
+		if (bkey_eq(bp_pos, POS_MAX))
 			break;
 
-		bp_offset++;
+		bp_pos = bpos_nosnap_successor(bp_pos);
 	}
 
 	return ret;
diff --git a/fs/bcachefs/move.c b/fs/bcachefs/move.c
index be14d3737027..9c8af0872b29 100644
--- a/fs/bcachefs/move.c
+++ b/fs/bcachefs/move.c
@@ -626,7 +626,7 @@ void bch2_verify_bucket_evacuated(struct btree_trans *trans, struct bpos bucket,
 	struct bkey_s_c k;
 	struct printbuf buf = PRINTBUF;
 	struct bch_backpointer bp;
-	u64 bp_offset = 0;
+	struct bpos bp_pos = POS_MIN;
 	unsigned nr_bps = 0;
 	int ret;
 
@@ -668,17 +668,16 @@ failed_to_evacuate:
 		bch2_trans_begin(trans);
 
 		ret = bch2_get_next_backpointer(trans, bucket, gen,
-						&bp_offset, &bp,
+						&bp_pos, &bp,
 						BTREE_ITER_CACHED);
 		if (bch2_err_matches(ret, BCH_ERR_transaction_restart))
 			continue;
 		if (ret)
 			break;
-		if (bp_offset == U64_MAX)
+		if (bkey_eq(bp_pos, POS_MAX))
 			break;
 
-		k = bch2_backpointer_get_key(trans, &iter,
-					     bucket, bp_offset, bp, 0);
+		k = bch2_backpointer_get_key(trans, &iter, bp_pos, bp, 0);
 		ret = bkey_err(k);
 		if (bch2_err_matches(ret, BCH_ERR_transaction_restart))
 			continue;
@@ -692,7 +691,7 @@ failed_to_evacuate:
 
 		if (++nr_bps > 10)
 			break;
-		bp_offset++;
+		bp_pos = bpos_nosnap_successor(bp_pos);
 	}
 
 	bch2_print_string_as_lines(KERN_ERR, buf.buf);
@@ -716,7 +715,8 @@ int __bch2_evacuate_bucket(struct btree_trans *trans,
 	struct data_update_opts data_opts;
 	unsigned dirty_sectors, bucket_size;
 	u64 fragmentation;
-	u64 bp_offset = 0, cur_inum = U64_MAX;
+	u64 cur_inum = U64_MAX;
+	struct bpos bp_pos = POS_MIN;
 	int ret = 0;
 
 	bch2_bkey_buf_init(&sk);
@@ -752,13 +752,13 @@ int __bch2_evacuate_bucket(struct btree_trans *trans,
 		bch2_trans_begin(trans);
 
 		ret = bch2_get_next_backpointer(trans, bucket, gen,
-						&bp_offset, &bp,
+						&bp_pos, &bp,
 						BTREE_ITER_CACHED);
 		if (bch2_err_matches(ret, BCH_ERR_transaction_restart))
 			continue;
 		if (ret)
 			goto err;
-		if (bp_offset == U64_MAX)
+		if (bkey_eq(bp_pos, POS_MAX))
 			break;
 
 		if (!bp.level) {
@@ -766,8 +766,7 @@ int __bch2_evacuate_bucket(struct btree_trans *trans,
 			struct bkey_s_c k;
 			unsigned i = 0;
 
-			k = bch2_backpointer_get_key(trans, &iter,
-						bucket, bp_offset, bp, 0);
+			k = bch2_backpointer_get_key(trans, &iter, bp_pos, bp, 0);
 			ret = bkey_err(k);
 			if (bch2_err_matches(ret, BCH_ERR_transaction_restart))
 				continue;
@@ -822,8 +821,7 @@ int __bch2_evacuate_bucket(struct btree_trans *trans,
 		} else {
 			struct btree *b;
 
-			b = bch2_backpointer_get_node(trans, &iter,
-						bucket, bp_offset, bp);
+			b = bch2_backpointer_get_node(trans, &iter, bp_pos, bp);
 			ret = PTR_ERR_OR_ZERO(b);
 			if (ret == -BCH_ERR_backpointer_to_overwritten_btree_node)
 				continue;
@@ -851,7 +849,7 @@ int __bch2_evacuate_bucket(struct btree_trans *trans,
 			}
 		}
 next:
-		bp_offset++;
+		bp_pos = bpos_nosnap_successor(bp_pos);
 	}
 
 	trace_evacuate_bucket(c, &bucket, dirty_sectors, bucket_size, fragmentation, ret);
diff --git a/fs/bcachefs/recovery.c b/fs/bcachefs/recovery.c
index 1b9a8329654e..8cc8af6d29ef 100644
--- a/fs/bcachefs/recovery.c
+++ b/fs/bcachefs/recovery.c
@@ -1134,14 +1134,11 @@ int bch2_fs_recovery(struct bch_fs *c)
 	}
 
 	if (!c->opts.nochanges) {
-		if (c->sb.version < bcachefs_metadata_version_lru_v2) {
-			bch_info(c, "version prior to backpointers, upgrade and fsck required");
+		if (c->sb.version < bcachefs_metadata_version_no_bps_in_alloc_keys) {
+			bch_info(c, "version prior to no_bps_in_alloc_keys, upgrade and fsck required");
 			c->opts.version_upgrade	= true;
 			c->opts.fsck		= true;
 			c->opts.fix_errors	= FSCK_OPT_YES;
-		} else if (c->sb.version < bcachefs_metadata_version_fragmentation_lru) {
-			bch_info(c, "version prior to backpointers, upgrade required");
-			c->opts.version_upgrade	= true;
 		}
 	}