bcachefs: Freespace, need_discard btrees

This adds two new btrees for the upcoming allocator rewrite: an extents
btree of free buckets, and a btree for buckets awaiting discards.

We also add a new trigger for alloc keys to keep the new btrees up to
date, and a compatibility path to initialize them on existing
filesystems.

Signed-off-by: Kent Overstreet <kent.overstreet@gmail.com>

17 files changed, 384 insertions, 58 deletions

diff --git a/fs/bcachefs/alloc_background.c b/fs/bcachefs/alloc_background.c
index 4afb2d457fb0..26568cd15aa3 100644
--- a/fs/bcachefs/alloc_background.c
+++ b/fs/bcachefs/alloc_background.c
@@ -14,6 +14,7 @@
 #include "debug.h"
 #include "ec.h"
 #include "error.h"
+#include "lru.h"
 #include "recovery.h"
 #include "varint.h"
 
@@ -39,6 +40,15 @@ static const unsigned BCH_ALLOC_V1_FIELD_BYTES[] = {
 #undef x
 };
 
+const char * const bch2_bucket_states[] = {
+	"free",
+	"need gc gens",
+	"need discard",
+	"cached",
+	"dirty",
+	NULL
+};
+
 /* Persistent alloc info: */
 
 static inline u64 alloc_field_v1_get(const struct bch_alloc *a,
@@ -161,6 +171,7 @@ static int bch2_alloc_unpack_v3(struct bkey_alloc_unpacked *out,
 	out->gen	= a.v->gen;
 	out->oldest_gen	= a.v->oldest_gen;
 	out->data_type	= a.v->data_type;
+	out->need_discard = BCH_ALLOC_NEED_DISCARD(a.v);
 	out->journal_seq = le64_to_cpu(a.v->journal_seq);
 
 #define x(_name, _bits)							\
@@ -197,6 +208,7 @@ static void bch2_alloc_pack_v3(struct bkey_alloc_buf *dst,
 	a->v.oldest_gen	= src.oldest_gen;
 	a->v.data_type	= src.data_type;
 	a->v.journal_seq = cpu_to_le64(src.journal_seq);
+	SET_BCH_ALLOC_NEED_DISCARD(&a->v, src.need_discard);
 
 #define x(_name, _bits)							\
 	nr_fields++;							\
@@ -325,9 +337,9 @@ void bch2_alloc_to_text(struct printbuf *out, struct bch_fs *c,
 {
 	struct bkey_alloc_unpacked u = bch2_alloc_unpack(k);
 
-	pr_buf(out, "gen %u oldest_gen %u data_type %s journal_seq %llu",
+	pr_buf(out, "gen %u oldest_gen %u data_type %s journal_seq %llu need_discard %u",
 	       u.gen, u.oldest_gen, bch2_data_types[u.data_type],
-	       u.journal_seq);
+	       u.journal_seq, u.need_discard);
 #define x(_name, ...)	pr_buf(out, " " #_name " %llu", (u64) u._name);
 	BCH_ALLOC_FIELDS_V2()
 #undef  x
@@ -384,6 +396,221 @@ int bch2_alloc_read(struct bch_fs *c, bool gc, bool metadata_only)
 	return ret;
 }
 
+/* Free space/discard btree: */
+
+static int bch2_bucket_do_index(struct btree_trans *trans,
+				struct bkey_s_c alloc_k,
+				struct bkey_alloc_unpacked a,
+				bool set)
+{
+	struct bch_fs *c = trans->c;
+	struct bch_dev *ca = bch_dev_bkey_exists(c, a.dev);
+	struct btree_iter iter;
+	struct bkey_s_c old;
+	struct bkey_i *k;
+	enum bucket_state state = bucket_state(a);
+	enum btree_id btree;
+	enum bch_bkey_type old_type = !set ? KEY_TYPE_set : KEY_TYPE_deleted;
+	enum bch_bkey_type new_type =  set ? KEY_TYPE_set : KEY_TYPE_deleted;
+	struct printbuf buf = PRINTBUF;
+	int ret;
+
+	if (state != BUCKET_free &&
+	    state != BUCKET_need_discard)
+		return 0;
+
+	k = bch2_trans_kmalloc(trans, sizeof(*k));
+	if (IS_ERR(k))
+		return PTR_ERR(k);
+
+	bkey_init(&k->k);
+	k->k.type = new_type;
+
+	switch (state) {
+	case BUCKET_free:
+		btree = BTREE_ID_freespace;
+		k->k.p = alloc_freespace_pos(a);
+		bch2_key_resize(&k->k, 1);
+		break;
+	case BUCKET_need_discard:
+		btree = BTREE_ID_need_discard;
+		k->k.p = POS(a.dev, a.bucket);
+		break;
+	default:
+		return 0;
+	}
+
+	bch2_trans_iter_init(trans, &iter, btree,
+			     bkey_start_pos(&k->k),
+			     BTREE_ITER_INTENT);
+	old = bch2_btree_iter_peek_slot(&iter);
+	ret = bkey_err(old);
+	if (ret)
+		goto err;
+
+	if (ca->mi.freespace_initialized &&
+	    bch2_fs_inconsistent_on(old.k->type != old_type, c,
+			"incorrect key when %s %s btree (got %s should be %s)\n"
+			"  for %s",
+			set ? "setting" : "clearing",
+			bch2_btree_ids[btree],
+			bch2_bkey_types[old.k->type],
+			bch2_bkey_types[old_type],
+			(bch2_bkey_val_to_text(&buf, c, alloc_k), buf.buf))) {
+		ret = -EIO;
+		goto err;
+	}
+
+	ret = bch2_trans_update(trans, &iter, k, 0);
+err:
+	bch2_trans_iter_exit(trans, &iter);
+	printbuf_exit(&buf);
+	return ret;
+}
+
+int bch2_trans_mark_alloc(struct btree_trans *trans,
+			  struct bkey_s_c old, struct bkey_i *new,
+			  unsigned flags)
+{
+	struct bch_fs *c = trans->c;
+	struct bch_dev *ca = bch_dev_bkey_exists(c, new->k.p.inode);
+	struct bkey_alloc_unpacked old_u = bch2_alloc_unpack(old);
+	struct bkey_alloc_unpacked new_u = bch2_alloc_unpack(bkey_i_to_s_c(new));
+	u64 old_lru, new_lru;
+	bool need_repack = false;
+	int ret = 0;
+
+	if (old_u.data_type && !new_u.data_type && ca->mi.discard) {
+		new_u.need_discard = true;
+		need_repack = true;
+	}
+
+	if (new_u.dirty_sectors > old_u.dirty_sectors ||
+	    new_u.cached_sectors > old_u.cached_sectors) {
+		new_u.read_time = max_t(u64, 1, atomic64_read(&c->io_clock[READ].now));
+		new_u.write_time = max_t(u64, 1, atomic64_read(&c->io_clock[WRITE].now));
+		need_repack = true;
+	}
+
+	if (old_u.data_type && !new_u.data_type &&
+	    old_u.gen == new_u.gen &&
+	    !bch2_bucket_is_open(c, new->k.p.inode, new->k.p.offset) &&
+	    !bch2_bucket_is_open_safe(c, new->k.p.inode, new->k.p.offset)) {
+		new_u.gen++;
+		need_repack = true;
+	}
+
+	if (bucket_state(old_u) != bucket_state(new_u) ||
+	    (bucket_state(new_u) == BUCKET_free &&
+	     alloc_freespace_genbits(old_u) != alloc_freespace_genbits(new_u))) {
+		ret =   bch2_bucket_do_index(trans, old, old_u, false) ?:
+			bch2_bucket_do_index(trans, bkey_i_to_s_c(new), new_u, true);
+		if (ret)
+			return ret;
+	}
+
+	old_lru = alloc_lru_idx(old_u);
+	new_lru = alloc_lru_idx(new_u);
+
+	if (old_lru != new_lru) {
+		ret = bch2_lru_change(trans, new->k.p.inode, new->k.p.offset,
+				      old_lru, &new_lru);
+		if (ret)
+			return ret;
+
+		if (new_lru && new_u.read_time != new_lru) {
+			new_u.read_time = new_lru;
+			need_repack = true;
+		}
+	}
+
+	if (need_repack && !bkey_deleted(&new->k))
+		bch2_alloc_pack_v3((void *) new, new_u);
+
+	return 0;
+}
+
+static int bch2_dev_freespace_init(struct bch_fs *c, struct bch_dev *ca)
+{
+	struct btree_trans trans;
+	struct btree_iter iter;
+	struct bkey_s_c k;
+	struct bkey_alloc_unpacked a;
+	struct bch_member *m;
+	int ret;
+
+	bch2_trans_init(&trans, c, 0, 0);
+
+	for_each_btree_key(&trans, iter, BTREE_ID_alloc,
+			   POS(ca->dev_idx, ca->mi.first_bucket),
+			   BTREE_ITER_SLOTS|
+			   BTREE_ITER_PREFETCH, k, ret) {
+		if (iter.pos.offset >= ca->mi.nbuckets)
+			break;
+
+		a = bch2_alloc_unpack(k);
+		ret = __bch2_trans_do(&trans, NULL, NULL,
+				      BTREE_INSERT_LAZY_RW,
+				 bch2_bucket_do_index(&trans, k, a, true));
+		if (ret)
+			break;
+	}
+	bch2_trans_iter_exit(&trans, &iter);
+
+	bch2_trans_exit(&trans);
+
+	if (ret) {
+		bch_err(ca, "error initializing free space: %i", ret);
+		return ret;
+	}
+
+	mutex_lock(&c->sb_lock);
+	m = bch2_sb_get_members(c->disk_sb.sb)->members + ca->dev_idx;
+	SET_BCH_MEMBER_FREESPACE_INITIALIZED(m, true);
+	mutex_unlock(&c->sb_lock);
+
+	return ret;
+}
+
+int bch2_fs_freespace_init(struct bch_fs *c)
+{
+	struct bch_dev *ca;
+	unsigned i;
+	int ret = 0;
+	bool doing_init = false;
+
+	/*
+	 * We can crash during the device add path, so we need to check this on
+	 * every mount:
+	 */
+
+	for_each_member_device(ca, c, i) {
+		if (ca->mi.freespace_initialized)
+			continue;
+
+		if (!doing_init) {
+			bch_info(c, "initializing freespace");
+			doing_init = true;
+		}
+
+		ret = bch2_dev_freespace_init(c, ca);
+		if (ret) {
+			percpu_ref_put(&ca->ref);
+			return ret;
+		}
+	}
+
+	if (doing_init) {
+		mutex_lock(&c->sb_lock);
+		bch2_write_super(c);
+		mutex_unlock(&c->sb_lock);
+
+		bch_verbose(c, "done initializing freespace");
+	}
+
+	return ret;
+}
+
 /* Bucket IO clocks: */
 
 int bch2_bucket_io_time_reset(struct btree_trans *trans, unsigned dev,
@@ -428,6 +655,16 @@ out:
  * commands to the newly free buckets, then puts them on the various freelists.
  */
 
+/*
+ * bucket_gc_gen() returns the difference between the bucket's current gen and
+ * the oldest gen of any pointer into that bucket in the btree.
+ */
+
+static inline u8 bucket_gc_gen(struct bucket *g)
+{
+	return g->mark.gen - g->oldest_gen;
+}
+
 static bool bch2_can_invalidate_bucket(struct bch_dev *ca, size_t b,
 				       struct bucket_mark m)
 {
diff --git a/fs/bcachefs/alloc_background.h b/fs/bcachefs/alloc_background.h
index 3eaa6d204286..c45a702c9e7f 100644
--- a/fs/bcachefs/alloc_background.h
+++ b/fs/bcachefs/alloc_background.h
@@ -17,6 +17,7 @@ struct bkey_alloc_unpacked {
 	u8		gen;
 	u8		oldest_gen;
 	u8		data_type;
+	bool		need_discard:1;
 #define x(_name, _bits)	u##_bits _name;
 	BCH_ALLOC_FIELDS_V2()
 #undef  x
@@ -25,6 +26,50 @@ struct bkey_alloc_unpacked {
 /* How out of date a pointer gen is allowed to be: */
 #define BUCKET_GC_GEN_MAX	96U
 
+static inline u8 alloc_gc_gen(struct bkey_alloc_unpacked a)
+{
+	return a.gen - a.oldest_gen;
+}
+
+enum bucket_state {
+	BUCKET_free,
+	BUCKET_need_gc_gens,
+	BUCKET_need_discard,
+	BUCKET_cached,
+	BUCKET_dirty,
+};
+
+extern const char * const bch2_bucket_states[];
+
+static inline enum bucket_state bucket_state(struct bkey_alloc_unpacked a)
+{
+	if (a.dirty_sectors || a.stripe)
+		return BUCKET_dirty;
+	if (a.cached_sectors)
+		return BUCKET_cached;
+	BUG_ON(a.data_type);
+	if (a.need_discard)
+		return BUCKET_need_discard;
+	if (alloc_gc_gen(a) >= BUCKET_GC_GEN_MAX)
+		return BUCKET_need_gc_gens;
+	return BUCKET_free;
+}
+
+static inline u64 alloc_lru_idx(struct bkey_alloc_unpacked a)
+{
+	return bucket_state(a) == BUCKET_cached ? a.read_time : 0;
+}
+
+static inline u64 alloc_freespace_genbits(struct bkey_alloc_unpacked a)
+{
+	return ((u64) alloc_gc_gen(a) >> 4) << 56;
+}
+
+static inline struct bpos alloc_freespace_pos(struct bkey_alloc_unpacked a)
+{
+	return POS(a.dev, a.bucket | alloc_freespace_genbits(a));
+}
+
 /* returns true if not equal */
 static inline bool bkey_alloc_unpacked_cmp(struct bkey_alloc_unpacked l,
 					   struct bkey_alloc_unpacked r)
@@ -65,18 +110,21 @@ void bch2_alloc_to_text(struct printbuf *, struct bch_fs *, struct bkey_s_c);
 #define bch2_bkey_ops_alloc (struct bkey_ops) {		\
 	.key_invalid	= bch2_alloc_v1_invalid,	\
 	.val_to_text	= bch2_alloc_to_text,		\
+	.trans_trigger	= bch2_trans_mark_alloc,	\
 	.atomic_trigger	= bch2_mark_alloc,		\
 }
 
 #define bch2_bkey_ops_alloc_v2 (struct bkey_ops) {	\
 	.key_invalid	= bch2_alloc_v2_invalid,	\
 	.val_to_text	= bch2_alloc_to_text,		\
+	.trans_trigger	= bch2_trans_mark_alloc,	\
 	.atomic_trigger	= bch2_mark_alloc,		\
 }
 
 #define bch2_bkey_ops_alloc_v3 (struct bkey_ops) {	\
 	.key_invalid	= bch2_alloc_v3_invalid,	\
 	.val_to_text	= bch2_alloc_to_text,		\
+	.trans_trigger	= bch2_trans_mark_alloc,	\
 	.atomic_trigger	= bch2_mark_alloc,		\
 }
 
@@ -89,6 +137,10 @@ static inline bool bkey_is_alloc(const struct bkey *k)
 
 int bch2_alloc_read(struct bch_fs *, bool, bool);
 
+int bch2_trans_mark_alloc(struct btree_trans *, struct bkey_s_c,
+			  struct bkey_i *, unsigned);
+int bch2_fs_freespace_init(struct bch_fs *);
+
 static inline void bch2_wake_allocator(struct bch_dev *ca)
 {
 	struct task_struct *p;
diff --git a/fs/bcachefs/alloc_foreground.h b/fs/bcachefs/alloc_foreground.h
index d466bda9afc8..aa35801605dc 100644
--- a/fs/bcachefs/alloc_foreground.h
+++ b/fs/bcachefs/alloc_foreground.h
@@ -115,6 +115,17 @@ static inline bool bch2_bucket_is_open(struct bch_fs *c, unsigned dev, u64 bucke
 	return false;
 }
 
+static inline bool bch2_bucket_is_open_safe(struct bch_fs *c, unsigned dev, u64 bucket)
+{
+	bool ret;
+
+	spin_lock(&c->freelist_lock);
+	ret = bch2_bucket_is_open(c, dev, bucket);
+	spin_unlock(&c->freelist_lock);
+
+	return ret;
+}
+
 int bch2_bucket_alloc_set(struct bch_fs *, struct open_buckets *,
 		      struct dev_stripe_state *, struct bch_devs_mask *,
 		      unsigned, unsigned *, bool *, enum alloc_reserve,
diff --git a/fs/bcachefs/bcachefs.h b/fs/bcachefs/bcachefs.h
index 42ff5e48910d..7350fb6a8355 100644
--- a/fs/bcachefs/bcachefs.h
+++ b/fs/bcachefs/bcachefs.h
@@ -392,6 +392,8 @@ enum gc_phase {
 	GC_PHASE_BTREE_subvolumes,
 	GC_PHASE_BTREE_snapshots,
 	GC_PHASE_BTREE_lru,
+	GC_PHASE_BTREE_freespace,
+	GC_PHASE_BTREE_need_discard,
 
 	GC_PHASE_PENDING_DELETE,
 };
diff --git a/fs/bcachefs/bcachefs_format.h b/fs/bcachefs/bcachefs_format.h
index 9785c8275570..e80d2ea26807 100644
--- a/fs/bcachefs/bcachefs_format.h
+++ b/fs/bcachefs/bcachefs_format.h
@@ -899,11 +899,12 @@ struct bch_alloc_v3 {
 	__u8			data[];
 } __attribute__((packed, aligned(8)));
 
+LE32_BITMASK(BCH_ALLOC_NEED_DISCARD,struct bch_alloc_v3, flags,  0,  1)
+
 enum {
 #define x(name, _bits) BCH_ALLOC_FIELD_V1_##name,
 	BCH_ALLOC_FIELDS_V1()
 #undef x
-	BCH_ALLOC_FIELD_NR
 };
 
 /* Quotas: */
@@ -1102,6 +1103,8 @@ LE64_BITMASK(BCH_MEMBER_DISCARD,	struct bch_member, flags[0], 14, 15)
 LE64_BITMASK(BCH_MEMBER_DATA_ALLOWED,	struct bch_member, flags[0], 15, 20)
 LE64_BITMASK(BCH_MEMBER_GROUP,		struct bch_member, flags[0], 20, 28)
 LE64_BITMASK(BCH_MEMBER_DURABILITY,	struct bch_member, flags[0], 28, 30)
+LE64_BITMASK(BCH_MEMBER_FREESPACE_INITIALIZED,
+					struct bch_member, flags[0], 30, 31)
 
 #if 0
 LE64_BITMASK(BCH_MEMBER_NR_READ_ERRORS,	struct bch_member, flags[1], 0,  20);
@@ -1320,7 +1323,8 @@ enum bcachefs_metadata_version {
 	bcachefs_metadata_version_reflink_p_fix		= 16,
 	bcachefs_metadata_version_subvol_dirent		= 17,
 	bcachefs_metadata_version_inode_v2		= 18,
-	bcachefs_metadata_version_max			= 19,
+	bcachefs_metadata_version_freespace		= 19,
+	bcachefs_metadata_version_max			= 20,
 };
 
 #define bcachefs_metadata_version_current	(bcachefs_metadata_version_max - 1)
@@ -1838,7 +1842,9 @@ LE32_BITMASK(JSET_NO_FLUSH,	struct jset, flags, 5, 6);
 	x(reflink,	7)			\
 	x(subvolumes,	8)			\
 	x(snapshots,	9)			\
-	x(lru,		10)
+	x(lru,		10)			\
+	x(freespace,	11)			\
+	x(need_discard,	12)
 
 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 9e3fbb673559..3c1bf3310d99 100644
--- a/fs/bcachefs/bkey_methods.c
+++ b/fs/bcachefs/bkey_methods.c
@@ -169,6 +169,12 @@ static unsigned bch2_key_types_allowed[] = {
 	[BKEY_TYPE_lru] =
 		(1U << KEY_TYPE_deleted)|
 		(1U << KEY_TYPE_lru),
+	[BKEY_TYPE_freespace] =
+		(1U << KEY_TYPE_deleted)|
+		(1U << KEY_TYPE_set),
+	[BKEY_TYPE_need_discard] =
+		(1U << KEY_TYPE_deleted)|
+		(1U << KEY_TYPE_set),
 	[BKEY_TYPE_btree] =
 		(1U << KEY_TYPE_deleted)|
 		(1U << KEY_TYPE_btree_ptr)|
diff --git a/fs/bcachefs/btree_gc.c b/fs/bcachefs/btree_gc.c
index 73b947a493a2..a8c566fd12bb 100644
--- a/fs/bcachefs/btree_gc.c
+++ b/fs/bcachefs/btree_gc.c
@@ -1379,7 +1379,7 @@ static int bch2_alloc_write_key(struct btree_trans *trans,
 	if (IS_ERR(a))
 		return PTR_ERR(a);
 
-	ret = bch2_trans_update(trans, iter, &a->k, BTREE_TRIGGER_NORUN);
+	ret = bch2_trans_update(trans, iter, &a->k, 0);
 fsck_err:
 	return ret;
 }
@@ -1891,7 +1891,7 @@ static int bch2_alloc_write_oldest_gen(struct btree_trans *trans, struct btree_i
 
 	u.oldest_gen = ca->oldest_gen[iter->pos.offset];
 
-	return bch2_alloc_write(trans, iter, &u, BTREE_TRIGGER_NORUN);
+	return bch2_alloc_write(trans, iter, &u, 0);
 }
 
 int bch2_gc_gens(struct bch_fs *c)
diff --git a/fs/bcachefs/btree_io.c b/fs/bcachefs/btree_io.c
index e6cea4c687e1..1df454f24b54 100644
--- a/fs/bcachefs/btree_io.c
+++ b/fs/bcachefs/btree_io.c
@@ -930,7 +930,7 @@ int bch2_btree_node_read_done(struct bch_fs *c, struct bch_dev *ca,
 					"error decrypting btree node: %i", ret))
 				goto fsck_err;
 
-			btree_err_on(btree_node_is_extents(b) &&
+			btree_err_on(btree_node_type_is_extents(btree_node_type(b)) &&
 				     !BTREE_NODE_NEW_EXTENT_OVERWRITE(b->data),
 				     BTREE_ERR_FATAL, c, NULL, b, NULL,
 				     "btree node does not have NEW_EXTENT_OVERWRITE set");
diff --git a/fs/bcachefs/btree_types.h b/fs/bcachefs/btree_types.h
index 575635b5fa10..788b9811148f 100644
--- a/fs/bcachefs/btree_types.h
+++ b/fs/bcachefs/btree_types.h
@@ -596,24 +596,9 @@ static inline enum btree_node_type btree_node_type(struct btree *b)
 	return __btree_node_type(b->c.level, b->c.btree_id);
 }
 
-static inline bool btree_node_type_is_extents(enum btree_node_type type)
-{
-	switch (type) {
-	case BKEY_TYPE_extents:
-	case BKEY_TYPE_reflink:
-		return true;
-	default:
-		return false;
-	}
-}
-
-static inline bool btree_node_is_extents(struct btree *b)
-{
-	return btree_node_type_is_extents(btree_node_type(b));
-}
-
 #define BTREE_NODE_TYPE_HAS_TRANS_TRIGGERS		\
 	((1U << BKEY_TYPE_extents)|			\
+	 (1U << BKEY_TYPE_alloc)|			\
 	 (1U << BKEY_TYPE_inodes)|			\
 	 (1U << BKEY_TYPE_stripes)|			\
 	 (1U << BKEY_TYPE_reflink)|			\
@@ -629,6 +614,16 @@ static inline bool btree_node_is_extents(struct btree *b)
 	(BTREE_NODE_TYPE_HAS_TRANS_TRIGGERS|		\
 	 BTREE_NODE_TYPE_HAS_MEM_TRIGGERS)
 
+#define BTREE_ID_IS_EXTENTS				\
+	((1U << BTREE_ID_extents)|			\
+	 (1U << BTREE_ID_reflink)|			\
+	 (1U << BTREE_ID_freespace))
+
+static inline bool btree_node_type_is_extents(enum btree_node_type type)
+{
+	return (1U << type) & BTREE_ID_IS_EXTENTS;
+}
+
 #define BTREE_ID_HAS_SNAPSHOTS				\
 	((1U << BTREE_ID_extents)|			\
 	 (1U << BTREE_ID_inodes)|			\
diff --git a/fs/bcachefs/buckets.c b/fs/bcachefs/buckets.c
index d52263759ee5..b5178d3067a9 100644
--- a/fs/bcachefs/buckets.c
+++ b/fs/bcachefs/buckets.c
@@ -555,6 +555,11 @@ int bch2_mark_alloc(struct btree_trans *trans,
 		}
 	}
 
+	if (bucket_state(new_u) == BUCKET_need_gc_gens) {
+		atomic_inc(&c->kick_gc);
+		wake_up_process(c->gc_thread);
+	}
+
 	percpu_down_read(&c->mark_lock);
 	if (!gc && new_u.gen != old_u.gen)
 		*bucket_gen(ca, new_u.bucket) = new_u.gen;
diff --git a/fs/bcachefs/buckets.h b/fs/bcachefs/buckets.h
index 392e03d4c319..07fe5cddbb41 100644
--- a/fs/bcachefs/buckets.h
+++ b/fs/bcachefs/buckets.h
@@ -81,16 +81,6 @@ static inline u8 *bucket_gen(struct bch_dev *ca, size_t b)
 	return gens->b + b;
 }
 
-/*
- * bucket_gc_gen() returns the difference between the bucket's current gen and
- * the oldest gen of any pointer into that bucket in the btree.
- */
-
-static inline u8 bucket_gc_gen(struct bucket *g)
-{
-	return g->mark.gen - g->oldest_gen;
-}
-
 static inline size_t PTR_BUCKET_NR(const struct bch_dev *ca,
 				   const struct bch_extent_ptr *ptr)
 {
diff --git a/fs/bcachefs/extent_update.c b/fs/bcachefs/extent_update.c
index 58b2c96f450c..2fd5d9672a44 100644
--- a/fs/bcachefs/extent_update.c
+++ b/fs/bcachefs/extent_update.c
@@ -15,17 +15,26 @@ static unsigned bch2_bkey_nr_alloc_ptrs(struct bkey_s_c k)
 {
 	struct bkey_ptrs_c ptrs = bch2_bkey_ptrs_c(k);
 	const union bch_extent_entry *entry;
-	unsigned ret = 0;
+	unsigned ret = 0, lru = 0;
 
 	bkey_extent_entry_for_each(ptrs, entry) {
 		switch (__extent_entry_type(entry)) {
 		case BCH_EXTENT_ENTRY_ptr:
+			/* Might also be updating LRU btree */
+			if (entry->ptr.cached)
+				lru++;
+
+			fallthrough;
 		case BCH_EXTENT_ENTRY_stripe_ptr:
 			ret++;
 		}
 	}
 
-	return ret;
+	/*
+	 * Updating keys in the alloc btree may also update keys in the
+	 * freespace or discard btrees:
+	 */
+	return lru + ret * 2;
 }
 
 static int count_iters_for_insert(struct btree_trans *trans,
diff --git a/fs/bcachefs/recovery.c b/fs/bcachefs/recovery.c
index 887971559214..4d01a01ea5c5 100644
--- a/fs/bcachefs/recovery.c
+++ b/fs/bcachefs/recovery.c
@@ -1027,8 +1027,8 @@ int bch2_fs_recovery(struct bch_fs *c)
 			bch_info(c, "filesystem version is prior to subvol_dirent - upgrading");
 			c->opts.version_upgrade = true;
 			c->opts.fsck		= true;
-		} else if (c->sb.version < bcachefs_metadata_version_inode_v2) {
-			bch_info(c, "filesystem version is prior to inode_v2 - upgrading");
+		} else if (c->sb.version < bcachefs_metadata_version_freespace) {
+			bch_info(c, "filesystem version is prior to freespace - upgrading");
 			c->opts.version_upgrade = true;
 		}
 	}
@@ -1196,6 +1196,11 @@ use_clean:
 	if (c->opts.verbose || !c->sb.clean)
 		bch_info(c, "journal replay done");
 
+	err = "error initializing freespace";
+	ret = bch2_fs_freespace_init(c);
+	if (ret)
+		goto err;
+
 	if (c->sb.version < bcachefs_metadata_version_snapshot_2) {
 		bch2_fs_lazy_rw(c);
 
@@ -1379,6 +1384,11 @@ int bch2_fs_initialize(struct bch_fs *c)
 		ca->new_fs_bucket_idx = 0;
 	}
 
+	err = "error initializing freespace";
+	ret = bch2_fs_freespace_init(c);
+	if (ret)
+		goto err;
+
 	err = "error creating root snapshot node";
 	ret = bch2_fs_initialize_subvolumes(c);
 	if (ret)
diff --git a/fs/bcachefs/super-io.c b/fs/bcachefs/super-io.c
index aa10be8edfe7..95af515a01cd 100644
--- a/fs/bcachefs/super-io.c
+++ b/fs/bcachefs/super-io.c
@@ -1052,6 +1052,11 @@ static void bch2_sb_members_to_text(struct printbuf *out, struct bch_sb *sb,
 		pr_buf(out, "%llu", BCH_MEMBER_DISCARD(m));
 		pr_newline(out);
 
+		pr_buf(out, "Freespace initialized:");
+		pr_tab(out);
+		pr_buf(out, "%llu", BCH_MEMBER_FREESPACE_INITIALIZED(m));
+		pr_newline(out);
+
 		pr_indent_pop(out, 2);
 	}
 }
diff --git a/fs/bcachefs/super-io.h b/fs/bcachefs/super-io.h
index 7fc56321922f..14a25f6fe29a 100644
--- a/fs/bcachefs/super-io.h
+++ b/fs/bcachefs/super-io.h
@@ -103,6 +103,7 @@ static inline struct bch_member_cpu bch2_mi_to_cpu(struct bch_member *mi)
 		.durability	= BCH_MEMBER_DURABILITY(mi)
 			? BCH_MEMBER_DURABILITY(mi) - 1
 			: 1,
+		.freespace_initialized = BCH_MEMBER_FREESPACE_INITIALIZED(mi),
 		.valid		= !bch2_is_zero(mi->uuid.b, sizeof(uuid_le)),
 	};
 }
diff --git a/fs/bcachefs/super.c b/fs/bcachefs/super.c
index 46947163a8dc..019cbf32d40e 100644
--- a/fs/bcachefs/super.c
+++ b/fs/bcachefs/super.c
@@ -1468,30 +1468,20 @@ int bch2_dev_set_state(struct bch_fs *c, struct bch_dev *ca,
 
 static int bch2_dev_remove_alloc(struct bch_fs *c, struct bch_dev *ca)
 {
-	struct btree_trans trans;
-	size_t i;
+	struct bpos start	= POS(ca->dev_idx, 0);
+	struct bpos end		= POS(ca->dev_idx, U64_MAX);
 	int ret;
 
-	bch2_trans_init(&trans, c, 0, 0);
-
-	for (i = 0; i < ca->mi.nbuckets; i++) {
-		ret = lockrestart_do(&trans,
-			bch2_btree_key_cache_flush(&trans,
-				BTREE_ID_alloc, POS(ca->dev_idx, i)));
-		if (ret)
-			break;
-	}
-	bch2_trans_exit(&trans);
-
-	if (ret) {
+	ret =   bch2_btree_delete_range(c, BTREE_ID_alloc, start, end,
+					BTREE_TRIGGER_NORUN, NULL) ?:
+		bch2_btree_delete_range(c, BTREE_ID_freespace, start, end,
+					BTREE_TRIGGER_NORUN, NULL) ?:
+		bch2_btree_delete_range(c, BTREE_ID_need_discard, start, end,
+					BTREE_TRIGGER_NORUN, NULL);
+	if (ret)
 		bch_err(c, "error %i removing dev alloc info", ret);
-		return ret;
-	}
 
-	return bch2_btree_delete_range(c, BTREE_ID_alloc,
-				       POS(ca->dev_idx, 0),
-				       POS(ca->dev_idx + 1, 0),
-				       0, NULL);
+	return ret;
 }
 
 int bch2_dev_remove(struct bch_fs *c, struct bch_dev *ca, int flags)
@@ -1709,6 +1699,12 @@ have_slot:
 		goto err_late;
 	}
 
+	ret = bch2_fs_freespace_init(c);
+	if (ret) {
+		bch_err(c, "device add error: error initializing free space: %i", ret);
+		goto err_late;
+	}
+
 	ca->new_fs_bucket_idx = 0;
 
 	if (ca->mi.state == BCH_MEMBER_STATE_rw) {
diff --git a/fs/bcachefs/super_types.h b/fs/bcachefs/super_types.h
index d8b159a5b7f7..89419fc7930d 100644
--- a/fs/bcachefs/super_types.h
+++ b/fs/bcachefs/super_types.h
@@ -32,6 +32,7 @@ struct bch_member_cpu {
 	u8			discard;
 	u8			data_allowed;
 	u8			durability;
+	u8			freespace_initialized;
 	u8			valid;
 };