bcachefs: btree write buffer update ordering

This adds an option to specify whether btree write buffer updates go on
to the head or the tail of the list of pending updates.

When triggers are updating backpointers btree, we need deletions to run
before updates. When an extent is being updated in place, we need the
updates from deleting the old version of the extent to happen before the
updates adding backpointers for the new version of the extent, otherwise
we'll incorrectly delete our new backpointers.

This is contrary to what we need for alloc info/reflink btree updates,
where we need inserts to happen before overwrites: for alloc info, if an
extent is being moved we need to process the insert of the new version
of the extent before the deletion of the old extent - otherwise an
indirect extent or bucket could end up being marked as not in use
because the new reference hasn't been processed yet.

To solve this, add an explicit ordering parameter to
bch2_trans_update_buffered().

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

5 files changed, 21 insertions, 20 deletions

diff --git a/fs/bcachefs/backpointers.h b/fs/bcachefs/backpointers.h
index 3994bc83d69d..c52954e2e875 100644
--- a/fs/bcachefs/backpointers.h
+++ b/fs/bcachefs/backpointers.h
@@ -84,7 +84,7 @@ static inline int bch2_bucket_backpointer_mod(struct btree_trans *trans,
 		set_bkey_val_u64s(&bp_k->k, 0);
 	}
 
-	return bch2_trans_update_buffered(trans, BTREE_ID_backpointers, &bp_k->k_i);
+	return bch2_trans_update_buffered(trans, BTREE_ID_backpointers, &bp_k->k_i, !insert);
 }
 
 static inline enum bch_data_type bkey_ptr_data_type(enum btree_id btree_id, unsigned level,
diff --git a/fs/bcachefs/btree_update.h b/fs/bcachefs/btree_update.h
index e90cf292f80b..21850d6aabf4 100644
--- a/fs/bcachefs/btree_update.h
+++ b/fs/bcachefs/btree_update.h
@@ -115,7 +115,7 @@ int bch2_bkey_get_empty_slot(struct btree_trans *, struct btree_iter *,
 int __must_check bch2_trans_update(struct btree_trans *, struct btree_iter *,
 				   struct bkey_i *, enum btree_update_flags);
 int __must_check bch2_trans_update_buffered(struct btree_trans *,
-					    enum btree_id, struct bkey_i *);
+					    enum btree_id, struct bkey_i *, bool);
 
 void bch2_trans_commit_hook(struct btree_trans *,
 			    struct btree_trans_commit_hook *);
diff --git a/fs/bcachefs/btree_update_leaf.c b/fs/bcachefs/btree_update_leaf.c
index b42b83c55c5b..0e5b6f4d4e4e 100644
--- a/fs/bcachefs/btree_update_leaf.c
+++ b/fs/bcachefs/btree_update_leaf.c
@@ -1718,21 +1718,14 @@ int __must_check bch2_trans_update(struct btree_trans *trans, struct btree_iter
 
 int __must_check bch2_trans_update_buffered(struct btree_trans *trans,
 					    enum btree_id btree,
-					    struct bkey_i *k)
+					    struct bkey_i *k,
+					    bool head)
 {
-	struct btree_write_buffered_key *i;
-	int ret;
+	int ret, pos;
 
 	EBUG_ON(trans->nr_wb_updates > trans->wb_updates_size);
 	EBUG_ON(k->k.u64s > BTREE_WRITE_BUFERED_U64s_MAX);
 
-	trans_for_each_wb_update(trans, i) {
-		if (i->btree == btree && bpos_eq(i->k.k.p, k->k.p)) {
-			bkey_copy(&i->k, k);
-			return 0;
-		}
-	}
-
 	if (!trans->wb_updates ||
 	    trans->nr_wb_updates == trans->wb_updates_size) {
 		struct btree_write_buffered_key *u;
@@ -1759,13 +1752,18 @@ int __must_check bch2_trans_update_buffered(struct btree_trans *trans,
 		trans->wb_updates = u;
 	}
 
-	trans->wb_updates[trans->nr_wb_updates] = (struct btree_write_buffered_key) {
-		.btree	= btree,
-	};
+	if (head) {
+		memmove(&trans->wb_updates[1],
+			&trans->wb_updates[0],
+			sizeof(trans->wb_updates[0]) * trans->nr_wb_updates);
+		pos = 0;
+	} else {
+		pos = trans->nr_wb_updates;
+	}
 
-	bkey_copy(&trans->wb_updates[trans->nr_wb_updates].k, k);
+	trans->wb_updates[pos] = (struct btree_write_buffered_key) { .btree = btree, };
+	bkey_copy(&trans->wb_updates[pos].k, k);
 	trans->nr_wb_updates++;
-
 	return 0;
 }
 
@@ -1886,7 +1884,7 @@ int bch2_btree_delete_at_buffered(struct btree_trans *trans,
 
 	bkey_init(&k->k);
 	k->k.p = pos;
-	return bch2_trans_update_buffered(trans, btree, k);
+	return bch2_trans_update_buffered(trans, btree, k, false);
 }
 
 int bch2_btree_delete_range_trans(struct btree_trans *trans, enum btree_id id,
diff --git a/fs/bcachefs/btree_write_buffer.c b/fs/bcachefs/btree_write_buffer.c
index 88c4b50dd70f..8b7fffb2bf57 100644
--- a/fs/bcachefs/btree_write_buffer.c
+++ b/fs/bcachefs/btree_write_buffer.c
@@ -279,6 +279,7 @@ int bch2_btree_insert_keys_write_buffer(struct btree_trans *trans)
 	struct btree_write_buffer *wb = &c->btree_write_buffer;
 	struct btree_write_buffered_key *i;
 	union btree_write_buffer_state old, new;
+	unsigned offset = 0;
 	int ret = 0;
 	u64 v;
 
@@ -286,7 +287,8 @@ int bch2_btree_insert_keys_write_buffer(struct btree_trans *trans)
 		EBUG_ON(i->k.k.u64s > BTREE_WRITE_BUFERED_U64s_MAX);
 
 		i->journal_seq		= trans->journal_res.seq;
-		i->journal_offset	= trans->journal_res.offset;
+		i->journal_offset	= trans->journal_res.offset + offset;
+		offset++;
 	}
 
 	preempt_disable();
diff --git a/fs/bcachefs/lru.c b/fs/bcachefs/lru.c
index e04c037f0c01..d3242511605d 100644
--- a/fs/bcachefs/lru.c
+++ b/fs/bcachefs/lru.c
@@ -61,7 +61,8 @@ static int __bch2_lru_set(struct btree_trans *trans, u16 lru_id,
 	EBUG_ON(lru_pos_time(k->k.p) != time);
 	EBUG_ON(k->k.p.offset != dev_bucket);
 
-	return bch2_trans_update_buffered(trans, BTREE_ID_lru, k);
+	return bch2_trans_update_buffered(trans, BTREE_ID_lru, k,
+					  key_type == KEY_TYPE_deleted);
 }
 
 int bch2_lru_del(struct btree_trans *trans, u16 lru_id, u64 dev_bucket, u64 time)