summaryrefslogtreecommitdiff
path: root/fs
diff options
context:
space:
mode:
authorKent Overstreet <kent.overstreet@gmail.com>2021-12-05 00:31:54 -0500
committerKent Overstreet <kent.overstreet@linux.dev>2023-10-22 17:09:29 -0400
commitd326ab2f5de201b9b7e790c653a2b925e7032d3b (patch)
tree228f5e7af8165a24b890ffbc7501513dbfd24e63 /fs
parent179e3434fac14a100bad2edba4fd401bffb67802 (diff)
bcachefs: LRU btree
This implements new persistent LRUs, to be used for buckets containing cached data, as well as stripes ordered by time when a block became empty. Signed-off-by: Kent Overstreet <kent.overstreet@gmail.com>
Diffstat (limited to 'fs')
-rw-r--r--fs/bcachefs/Makefile1
-rw-r--r--fs/bcachefs/bcachefs.h1
-rw-r--r--fs/bcachefs/bcachefs_format.h15
-rw-r--r--fs/bcachefs/bkey_methods.c4
-rw-r--r--fs/bcachefs/lru.c119
-rw-r--r--fs/bcachefs/lru.h15
6 files changed, 153 insertions, 2 deletions
diff --git a/fs/bcachefs/Makefile b/fs/bcachefs/Makefile
index d3808249948c..17423584a3f3 100644
--- a/fs/bcachefs/Makefile
+++ b/fs/bcachefs/Makefile
@@ -41,6 +41,7 @@ bcachefs-y := \
journal_sb.o \
journal_seq_blacklist.o \
keylist.o \
+ lru.o \
migrate.o \
move.o \
movinggc.o \
diff --git a/fs/bcachefs/bcachefs.h b/fs/bcachefs/bcachefs.h
index 01e9ed5dfc61..7891ad208a33 100644
--- a/fs/bcachefs/bcachefs.h
+++ b/fs/bcachefs/bcachefs.h
@@ -391,6 +391,7 @@ enum gc_phase {
GC_PHASE_BTREE_reflink,
GC_PHASE_BTREE_subvolumes,
GC_PHASE_BTREE_snapshots,
+ GC_PHASE_BTREE_lru,
GC_PHASE_PENDING_DELETE,
};
diff --git a/fs/bcachefs/bcachefs_format.h b/fs/bcachefs/bcachefs_format.h
index 350317e8b34f..982409ed940e 100644
--- a/fs/bcachefs/bcachefs_format.h
+++ b/fs/bcachefs/bcachefs_format.h
@@ -352,7 +352,8 @@ static inline void bkey_init(struct bkey *k)
x(snapshot, 22) \
x(inode_v2, 23) \
x(alloc_v3, 24) \
- x(set, 25)
+ x(set, 25) \
+ x(lru, 26)
enum bch_bkey_type {
#define x(name, nr) KEY_TYPE_##name = nr,
@@ -1024,6 +1025,15 @@ LE32_BITMASK(BCH_SNAPSHOT_DELETED, struct bch_snapshot, flags, 0, 1)
/* True if a subvolume points to this snapshot node: */
LE32_BITMASK(BCH_SNAPSHOT_SUBVOL, struct bch_snapshot, flags, 1, 2)
+/* LRU btree: */
+
+struct bch_lru {
+ struct bch_val v;
+ __le64 idx;
+} __attribute__((packed, aligned(8)));
+
+#define LRU_ID_STRIPES (1U << 16)
+
/* Optional/variable size superblock sections: */
struct bch_sb_field {
@@ -1838,7 +1848,8 @@ LE32_BITMASK(JSET_NO_FLUSH, struct jset, flags, 5, 6);
x(stripes, 6) \
x(reflink, 7) \
x(subvolumes, 8) \
- x(snapshots, 9)
+ x(snapshots, 9) \
+ x(lru, 10)
enum btree_id {
#define x(kwd, val) BTREE_ID_##kwd = val,
diff --git a/fs/bcachefs/bkey_methods.c b/fs/bcachefs/bkey_methods.c
index d938ee826c75..8757218e571b 100644
--- a/fs/bcachefs/bkey_methods.c
+++ b/fs/bcachefs/bkey_methods.c
@@ -9,6 +9,7 @@
#include "error.h"
#include "extents.h"
#include "inode.h"
+#include "lru.h"
#include "quota.h"
#include "reflink.h"
#include "subvolume.h"
@@ -165,6 +166,9 @@ static unsigned bch2_key_types_allowed[] = {
[BKEY_TYPE_snapshots] =
(1U << KEY_TYPE_deleted)|
(1U << KEY_TYPE_snapshot),
+ [BKEY_TYPE_lru] =
+ (1U << KEY_TYPE_deleted)|
+ (1U << KEY_TYPE_lru),
[BKEY_TYPE_btree] =
(1U << KEY_TYPE_deleted)|
(1U << KEY_TYPE_btree_ptr)|
diff --git a/fs/bcachefs/lru.c b/fs/bcachefs/lru.c
new file mode 100644
index 000000000000..2ababca5efe5
--- /dev/null
+++ b/fs/bcachefs/lru.c
@@ -0,0 +1,119 @@
+// SPDX-License-Identifier: GPL-2.0
+
+#include "bcachefs.h"
+#include "btree_iter.h"
+#include "btree_update.h"
+#include "error.h"
+#include "lru.h"
+
+const char *bch2_lru_invalid(const struct bch_fs *c, struct bkey_s_c k)
+{
+ const struct bch_lru *lru = bkey_s_c_to_lru(k).v;
+
+ if (bkey_val_bytes(k.k) < sizeof(*lru))
+ return "incorrect value size";
+
+ return NULL;
+}
+
+void bch2_lru_to_text(struct printbuf *out, struct bch_fs *c,
+ struct bkey_s_c k)
+{
+ const struct bch_lru *lru = bkey_s_c_to_lru(k).v;
+
+ pr_buf(out, "idx %llu", le64_to_cpu(lru->idx));
+}
+
+static int lru_delete(struct btree_trans *trans, u64 id, u64 idx, u64 time)
+{
+ struct bch_fs *c = trans->c;
+ struct btree_iter iter;
+ struct bkey_s_c k;
+ u64 existing_idx;
+ 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;
+
+ if (k.k->type != KEY_TYPE_lru) {
+ bch2_fs_inconsistent(c,
+ "pointer to nonexistent lru %llu:%llu",
+ id, time);
+ ret = -EIO;
+ goto err;
+ }
+
+ existing_idx = le64_to_cpu(bkey_s_c_to_lru(k).v->idx);
+ if (existing_idx != idx) {
+ bch2_fs_inconsistent(c,
+ "lru %llu:%llu with wrong backpointer: got %llu, should be %llu",
+ id, time, existing_idx, idx);
+ ret = -EIO;
+ goto err;
+ }
+
+ ret = bch2_btree_delete_at(trans, &iter, 0);
+err:
+ bch2_trans_iter_exit(trans, &iter);
+ return ret;
+}
+
+static int lru_set(struct btree_trans *trans, u64 lru_id, u64 idx, 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_trans_kmalloc(trans, sizeof(*lru));
+ ret = PTR_ERR_OR_ZERO(lru);
+ if (ret)
+ goto err;
+
+ bkey_lru_init(&lru->k_i);
+ lru->k.p = iter.pos;
+ lru->v.idx = cpu_to_le64(idx);
+
+ 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_change(struct btree_trans *trans, u64 id, u64 idx,
+ u64 old_time, u64 *new_time)
+{
+ if (old_time == *new_time)
+ return 0;
+
+ return lru_delete(trans, id, idx, old_time) ?:
+ lru_set(trans, id, idx, new_time);
+}
diff --git a/fs/bcachefs/lru.h b/fs/bcachefs/lru.h
new file mode 100644
index 000000000000..c3121cfee285
--- /dev/null
+++ b/fs/bcachefs/lru.h
@@ -0,0 +1,15 @@
+/* SPDX-License-Identifier: GPL-2.0 */
+#ifndef _BCACHEFS_LRU_H
+#define _BCACHEFS_LRU_H
+
+const char *bch2_lru_invalid(const struct bch_fs *, struct bkey_s_c);
+void bch2_lru_to_text(struct printbuf *, struct bch_fs *, struct bkey_s_c);
+
+#define bch2_bkey_ops_lru (struct bkey_ops) { \
+ .key_invalid = bch2_lru_invalid, \
+ .val_to_text = bch2_lru_to_text, \
+}
+
+int bch2_lru_change(struct btree_trans *, u64, u64, u64, u64 *);
+
+#endif /* _BCACHEFS_LRU_H */