bcachefs: Rework lru btree

This patch changes how the LRU index works:

Instead of using KEY_TYPE_lru where the bucket the lru entry points to
is part of the value, this switches to KEY_TYPE_set and encoding the
bucket we refer to in the low bits of the key.

This means that we no longer have to check for collisions when inserting
LRU entries. We'll be making using of this in the next patch, which adds
a btree write buffer - a pure write buffer for btree updates, where
updates are appended to a simple array and then periodically sorted and
batch inserted.

This is a new on disk format version, and a forced upgrade.

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

1 files changed, 38 insertions, 82 deletions

diff --git a/fs/bcachefs/lru.c b/fs/bcachefs/lru.c
index 12821868df71..6f7becb051bc 100644
--- a/fs/bcachefs/lru.c
+++ b/fs/bcachefs/lru.c
@@ -8,6 +8,7 @@
 #include "lru.h"
 #include "recovery.h"
 
+/* KEY_TYPE_lru is obsolete: */
 int bch2_lru_invalid(const struct bch_fs *c, struct bkey_s_c k,
 		     int rw, struct printbuf *err)
 {
@@ -19,7 +20,7 @@ int bch2_lru_invalid(const struct bch_fs *c, struct bkey_s_c k,
 		return -BCH_ERR_invalid_bkey;
 	}
 
-	if (!k.k->p.offset) {
+	if (!lru_pos_time(k.k->p)) {
 		prt_printf(err, "lru entry at time=0");
 		return -BCH_ERR_invalid_bkey;
 
@@ -36,101 +37,57 @@ void bch2_lru_to_text(struct printbuf *out, struct bch_fs *c,
 	prt_printf(out, "idx %llu", le64_to_cpu(lru->idx));
 }
 
-int bch2_lru_delete(struct btree_trans *trans, u64 id, u64 idx, u64 time,
-		    struct bkey_s_c orig_k)
+static int __bch2_lru_set(struct btree_trans *trans, u16 lru_id,
+			u64 dev_bucket, u64 time, unsigned key_type)
 {
 	struct btree_iter iter;
-	struct bkey_s_c k;
-	u64 existing_idx;
-	struct printbuf buf = PRINTBUF;
+	struct bkey_i *k;
 	int ret = 0;
 
 	if (!time)
 		return 0;
 
-	bch2_trans_iter_init(trans, &iter, BTREE_ID_lru,
-			     POS(id, time),
-			     BTREE_ITER_INTENT|
-			     BTREE_ITER_WITH_UPDATES);
-	k = bch2_btree_iter_peek_slot(&iter);
-	ret = bkey_err(k);
-	if (ret)
-		goto err;
+	k = bch2_trans_kmalloc_nomemzero(trans, sizeof(*k));
+	ret = PTR_ERR_OR_ZERO(k);
+	if (unlikely(ret))
+		return ret;
 
-	if (k.k->type != KEY_TYPE_lru) {
-		bch2_bkey_val_to_text(&buf, trans->c, orig_k);
-		bch2_trans_inconsistent(trans,
-			"pointer to nonexistent lru %llu:%llu\n%s",
-			id, time, buf.buf);
-		ret = -EIO;
-		goto err;
-	}
+	bkey_init(&k->k);
+	k->k.type = key_type;
+	k->k.p = lru_pos(lru_id, dev_bucket, time);
 
-	existing_idx = le64_to_cpu(bkey_s_c_to_lru(k).v->idx);
-	if (existing_idx != idx) {
-		bch2_bkey_val_to_text(&buf, trans->c, orig_k);
-		bch2_trans_inconsistent(trans,
-			"lru %llu:%llu with wrong backpointer: got %llu, should be %llu\n%s",
-			id, time, existing_idx, idx, buf.buf);
-		ret = -EIO;
-		goto err;
-	}
+	EBUG_ON(lru_pos_id(k->k.p) != lru_id);
+	EBUG_ON(lru_pos_time(k->k.p) != time);
+	EBUG_ON(k->k.p.offset != dev_bucket);
 
-	ret = bch2_btree_delete_at(trans, &iter, 0);
-err:
+	bch2_trans_iter_init(trans, &iter, BTREE_ID_lru,
+			     k->k.p, BTREE_ITER_INTENT);
+
+	ret = bch2_btree_iter_traverse(&iter) ?:
+		bch2_trans_update(trans, &iter, k, 0);
 	bch2_trans_iter_exit(trans, &iter);
-	printbuf_exit(&buf);
 	return ret;
 }
 
-int bch2_lru_set(struct btree_trans *trans, u64 lru_id, u64 idx, u64 *time)
+int bch2_lru_del(struct btree_trans *trans, u16 lru_id, u64 dev_bucket, u64 time)
 {
-	struct btree_iter iter;
-	struct bkey_s_c k;
-	struct bkey_i_lru *lru;
-	int ret = 0;
-
-	if (!*time)
-		return 0;
-
-	for_each_btree_key_norestart(trans, iter, BTREE_ID_lru,
-			POS(lru_id, *time),
-			BTREE_ITER_SLOTS|
-			BTREE_ITER_INTENT|
-			BTREE_ITER_WITH_UPDATES, k, ret)
-		if (bkey_deleted(k.k))
-			break;
-
-	if (ret)
-		goto err;
-
-	BUG_ON(iter.pos.inode != lru_id);
-	*time = iter.pos.offset;
-
-	lru = bch2_bkey_alloc(trans, &iter, lru);
-	ret = PTR_ERR_OR_ZERO(lru);
-	if (ret)
-		goto err;
-
-	lru->v.idx = cpu_to_le64(idx);
+	return __bch2_lru_set(trans, lru_id, dev_bucket, time, KEY_TYPE_deleted);
+}
 
-	ret = bch2_trans_update(trans, &iter, &lru->k_i, 0);
-	if (ret)
-		goto err;
-err:
-	bch2_trans_iter_exit(trans, &iter);
-	return ret;
+int bch2_lru_set(struct btree_trans *trans, u16 lru_id, u64 dev_bucket, u64 time)
+{
+	return __bch2_lru_set(trans, lru_id, dev_bucket, time, KEY_TYPE_set);
 }
 
-int bch2_lru_change(struct btree_trans *trans, u64 id, u64 idx,
-		    u64 old_time, u64 *new_time,
-		    struct bkey_s_c k)
+int bch2_lru_change(struct btree_trans *trans,
+		    u16 lru_id, u64 dev_bucket,
+		    u64 old_time, u64 new_time)
 {
-	if (old_time == *new_time)
+	if (old_time == new_time)
 		return 0;
 
-	return  bch2_lru_delete(trans, id, idx, old_time, k) ?:
-		bch2_lru_set(trans, id, idx, new_time);
+	return  bch2_lru_del(trans, lru_id, dev_bucket, old_time) ?:
+		bch2_lru_set(trans, lru_id, dev_bucket, new_time);
 }
 
 static int bch2_check_lru_key(struct btree_trans *trans,
@@ -144,12 +101,9 @@ static int bch2_check_lru_key(struct btree_trans *trans,
 	const struct bch_alloc_v4 *a;
 	struct printbuf buf1 = PRINTBUF;
 	struct printbuf buf2 = PRINTBUF;
-	struct bpos alloc_pos;
+	struct bpos alloc_pos = u64_to_bucket(lru_k.k->p.offset);
 	int ret;
 
-	alloc_pos = POS(lru_k.k->p.inode,
-			le64_to_cpu(bkey_s_c_to_lru(lru_k).v->idx));
-
 	if (fsck_err_on(!bch2_dev_bucket_exists(c, alloc_pos), c,
 			"lru key points to nonexistent device:bucket %llu:%llu",
 			alloc_pos.inode, alloc_pos.offset))
@@ -163,10 +117,12 @@ static int bch2_check_lru_key(struct btree_trans *trans,
 
 	a = bch2_alloc_to_v4(k, &a_convert);
 
-	if (fsck_err_on(a->data_type != BCH_DATA_cached ||
-			a->io_time[READ] != lru_k.k->p.offset, c,
-			"incorrect lru entry %s\n"
+	if (fsck_err_on(lru_k.k->type != KEY_TYPE_set ||
+			a->data_type != BCH_DATA_cached ||
+			a->io_time[READ] != lru_pos_time(lru_k.k->p), c,
+			"incorrect lru entry (time %llu) %s\n"
 			"  for %s",
+			lru_pos_time(lru_k.k->p),
 			(bch2_bkey_val_to_text(&buf1, c, lru_k), buf1.buf),
 			(bch2_bkey_val_to_text(&buf2, c, k), buf2.buf))) {
 		ret = bch2_btree_delete_at(trans, lru_iter, 0);