Update bcachefs sources to 6a20aede29 bcachefs: Fix quotas + snapshots

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

77 files changed, 1244 insertions, 712 deletions

diff --git a/.bcachefs_revision b/.bcachefs_revision
index bed19acb..e5747fce 100644
--- a/.bcachefs_revision
+++ b/.bcachefs_revision
@@ -1 +1 @@
-fd6fb298aa869dc009e525baa9be67ad52588361
+6a20aede294f72f3920146a352aa102a9fd3d0aa
diff --git a/Makefile b/Makefile
index 31fb9ac0..3fc52cfc 100644
--- a/Makefile
+++ b/Makefile
@@ -184,8 +184,6 @@ update-bcachefs-sources:
 	test -d libbcachefs || mkdir libbcachefs
 	cp $(LINUX_DIR)/fs/bcachefs/*.[ch] libbcachefs/
 	git add libbcachefs/*.[ch]
-	cp $(LINUX_DIR)/include/trace/events/bcachefs.h include/trace/events/
-	git add include/trace/events/bcachefs.h
 	cp $(LINUX_DIR)/include/linux/closure.h include/linux/
 	git add include/linux/closure.h
 	cp $(LINUX_DIR)/lib/closure.c linux/
diff --git a/Makefile.compiler b/Makefile.compiler
index 3d8adfd3..7aa1fbc4 100644
--- a/Makefile.compiler
+++ b/Makefile.compiler
@@ -29,16 +29,16 @@ try-run = $(shell set -e;		\
 	fi)
 
 # as-option
-# Usage: cflags-y += $(call as-option,-Wa$(comma)-isa=foo,)
+# Usage: aflags-y += $(call as-option,-Wa$(comma)-isa=foo,)
 
 as-option = $(call try-run,\
-	$(CC) $(KBUILD_CFLAGS) $(1) -c -x assembler /dev/null -o "$$TMP",$(1),$(2))
+	$(CC) -Werror $(KBUILD_AFLAGS) $(1) -c -x assembler-with-cpp /dev/null -o "$$TMP",$(1),$(2))
 
 # as-instr
-# Usage: cflags-y += $(call as-instr,instr,option1,option2)
+# Usage: aflags-y += $(call as-instr,instr,option1,option2)
 
 as-instr = $(call try-run,\
-	printf "%b\n" "$(1)" | $(CC) $(KBUILD_AFLAGS) -c -x assembler -o "$$TMP" -,$(2),$(3))
+	printf "%b\n" "$(1)" | $(CC) -Werror $(KBUILD_AFLAGS) -c -x assembler-with-cpp -o "$$TMP" -,$(2),$(3))
 
 # __cc-option
 # Usage: MY_CFLAGS += $(call __cc-option,$(CC),$(MY_CFLAGS),-march=winchip-c6,-march=i586)
diff --git a/include/linux/kernel.h b/include/linux/kernel.h
index a55b8a9b..01466c40 100644
--- a/include/linux/kernel.h
+++ b/include/linux/kernel.h
@@ -96,6 +96,14 @@
 	(type *)((char *)__mptr - offsetof(type, member)); })
 #endif
 
+#define __struct_group(TAG, NAME, ATTRS, MEMBERS...) \
+	union { \
+		struct { MEMBERS } ATTRS; \
+		struct TAG { MEMBERS } ATTRS NAME; \
+	}
+#define struct_group(NAME, MEMBERS...)	\
+	__struct_group(/* no tag */, NAME, /* no attrs */, MEMBERS)
+
 #define max(x, y) ({				\
 	typeof(x) _max1 = (x);			\
 	typeof(y) _max2 = (y);			\
diff --git a/include/linux/poison.h b/include/linux/poison.h
index 2d3249eb..851a855d 100644
--- a/include/linux/poison.h
+++ b/include/linux/poison.h
@@ -81,7 +81,13 @@
 /********** net/core/page_pool.c **********/
 #define PP_SIGNATURE		(0x40 + POISON_POINTER_DELTA)
 
+/********** net/core/skbuff.c **********/
+#define SKB_LIST_POISON_NEXT	((void *)(0x800 + POISON_POINTER_DELTA))
+
 /********** kernel/bpf/ **********/
 #define BPF_PTR_POISON ((void *)(0xeB9FUL + POISON_POINTER_DELTA))
 
+/********** VFS **********/
+#define VFS_PTR_POISON ((void *)(0xF5 + POISON_POINTER_DELTA))
+
 #endif
diff --git a/include/linux/types.h b/include/linux/types.h
index fc05e23a..ce454e26 100644
--- a/include/linux/types.h
+++ b/include/linux/types.h
@@ -82,5 +82,6 @@ typedef int (*cmp_func_t)(const void *a, const void *b);
 typedef unsigned int __bitwise slab_flags_t;
 typedef u64 phys_addr_t;
 struct vm_struct;
+struct mnt_idmap;
 
 #endif /* _TOOLS_LINUX_TYPES_H_ */
diff --git a/include/linux/uuid.h b/include/linux/uuid.h
index c8eeb708..4674746f 100644
--- a/include/linux/uuid.h
+++ b/include/linux/uuid.h
@@ -41,9 +41,4 @@ typedef struct {
    ((c) >> 8) & 0xff, (c) & 0xff,					\
    (d0), (d1), (d2), (d3), (d4), (d5), (d6), (d7) }})
 
-static inline int uuid_le_cmp(const uuid_le u1, const uuid_le u2)
-{
-	return memcmp(&u1, &u2, sizeof(uuid_le));
-}
-
 #endif
diff --git a/include/linux/xattr.h b/include/linux/xattr.h
index 222c72fe..dcdff6e8 100644
--- a/include/linux/xattr.h
+++ b/include/linux/xattr.h
@@ -42,7 +42,7 @@ struct xattr_handler {
 		   struct inode *inode, const char *name, void *buffer,
 		   size_t size);
 	int (*set)(const struct xattr_handler *,
-		   struct user_namespace *mnt_userns, struct dentry *dentry,
+		   struct mnt_idmap *idmap, struct dentry *dentry,
 		   struct inode *inode, const char *name, const void *buffer,
 		   size_t size, int flags);
 };
diff --git a/libbcachefs/acl.c b/libbcachefs/acl.c
index 5cb06ac5..2bf58aa8 100644
--- a/libbcachefs/acl.c
+++ b/libbcachefs/acl.c
@@ -212,7 +212,7 @@ bch2_acl_to_xattr(struct btree_trans *trans,
 	return xattr;
 }
 
-struct posix_acl *bch2_get_acl(struct user_namespace *mnt_userns,
+struct posix_acl *bch2_get_acl(struct mnt_idmap *idmap,
 			       struct dentry *dentry, int type)
 {
 	struct bch_inode_info *inode = to_bch_ei(dentry->d_inode);
@@ -290,7 +290,7 @@ int bch2_set_acl_trans(struct btree_trans *trans, subvol_inum inum,
 	return ret == -ENOENT ? 0 : ret;
 }
 
-int bch2_set_acl(struct user_namespace *mnt_userns,
+int bch2_set_acl(struct mnt_idmap *idmap,
 		 struct dentry *dentry,
 		 struct posix_acl *_acl, int type)
 {
@@ -317,7 +317,7 @@ retry:
 	mode = inode_u.bi_mode;
 
 	if (type == ACL_TYPE_ACCESS) {
-		ret = posix_acl_update_mode(mnt_userns, &inode->v, &mode, &acl);
+		ret = posix_acl_update_mode(idmap, &inode->v, &mode, &acl);
 		if (ret)
 			goto btree_err;
 	}
diff --git a/libbcachefs/acl.h b/libbcachefs/acl.h
index ac206f65..bb21d8d6 100644
--- a/libbcachefs/acl.h
+++ b/libbcachefs/acl.h
@@ -26,12 +26,12 @@ typedef struct {
 	__le32		a_version;
 } bch_acl_header;
 
-struct posix_acl *bch2_get_acl(struct user_namespace *, struct dentry *, int);
+struct posix_acl *bch2_get_acl(struct mnt_idmap *, struct dentry *, int);
 
 int bch2_set_acl_trans(struct btree_trans *, subvol_inum,
 		       struct bch_inode_unpacked *,
 		       struct posix_acl *, int);
-int bch2_set_acl(struct user_namespace *, struct dentry *, struct posix_acl *, int);
+int bch2_set_acl(struct mnt_idmap *, struct dentry *, struct posix_acl *, int);
 int bch2_acl_chmod(struct btree_trans *, subvol_inum,
 		   struct bch_inode_unpacked *,
 		   umode_t, struct posix_acl **);
diff --git a/libbcachefs/alloc_background.c b/libbcachefs/alloc_background.c
index 81620870..dcdef3bc 100644
--- a/libbcachefs/alloc_background.c
+++ b/libbcachefs/alloc_background.c
@@ -18,6 +18,7 @@
 #include "error.h"
 #include "lru.h"
 #include "recovery.h"
+#include "trace.h"
 #include "varint.h"
 
 #include <linux/kthread.h>
@@ -27,7 +28,6 @@
 #include <linux/rcupdate.h>
 #include <linux/sched/task.h>
 #include <linux/sort.h>
-#include <trace/events/bcachefs.h>
 
 /* Persistent alloc info: */
 
@@ -511,18 +511,8 @@ static inline struct bkey_i_alloc_v4 *bch2_alloc_to_v4_mut_inlined(struct btree_
 
 	if (likely(k.k->type == KEY_TYPE_alloc_v4) &&
 	    ((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...
-		 */
-		struct bkey_i_alloc_v4 *ret =
-			bch2_trans_kmalloc_nomemzero(trans, bkey_bytes(k.k) + sizeof(struct bch_backpointer));
-		if (!IS_ERR(ret))
-			bkey_reassemble(&ret->k_i, k);
-		return ret;
-	}
+	     BCH_ALLOC_V4_NR_BACKPOINTERS(a.v) == 0))
+		return bch2_bkey_make_mut_noupdate_typed(trans, k, alloc_v4);
 
 	return __bch2_alloc_to_v4_mut(trans, k);
 }
@@ -540,14 +530,13 @@ bch2_trans_start_alloc_update(struct btree_trans *trans, struct btree_iter *iter
 	struct bkey_i_alloc_v4 *a;
 	int ret;
 
-	bch2_trans_iter_init(trans, iter, BTREE_ID_alloc, pos,
+	k = bch2_bkey_get_iter(trans, iter, BTREE_ID_alloc, pos,
 			     BTREE_ITER_WITH_UPDATES|
 			     BTREE_ITER_CACHED|
 			     BTREE_ITER_INTENT);
-	k = bch2_btree_iter_peek_slot(iter);
 	ret = bkey_err(k);
 	if (unlikely(ret))
-		goto err;
+		return ERR_PTR(ret);
 
 	a = bch2_alloc_to_v4_mut_inlined(trans, k);
 	ret = PTR_ERR_OR_ZERO(a);
@@ -789,13 +778,12 @@ static int bch2_bucket_do_index(struct btree_trans *trans,
 		return 0;
 	}
 
-	bch2_trans_iter_init(trans, &iter, btree,
+	old = bch2_bkey_get_iter(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;
+		return ret;
 
 	if (ca->mi.freespace_initialized &&
 	    test_bit(BCH_FS_CHECK_ALLOC_DONE, &c->flags) &&
@@ -833,13 +821,12 @@ static noinline int bch2_bucket_gen_update(struct btree_trans *trans,
 	if (ret)
 		return ret;
 
-	bch2_trans_iter_init(trans, &iter, BTREE_ID_bucket_gens, pos,
-			     BTREE_ITER_INTENT|
-			     BTREE_ITER_WITH_UPDATES);
-	k = bch2_btree_iter_peek_slot(&iter);
+	k = bch2_bkey_get_iter(trans, &iter, BTREE_ID_bucket_gens, pos,
+			       BTREE_ITER_INTENT|
+			       BTREE_ITER_WITH_UPDATES);
 	ret = bkey_err(k);
 	if (ret)
-		goto err;
+		return ret;
 
 	if (k.k->type != KEY_TYPE_bucket_gens) {
 		bkey_bucket_gens_init(&g->k_i);
@@ -851,7 +838,6 @@ static noinline int bch2_bucket_gen_update(struct btree_trans *trans,
 	g->v.gens[offset] = gen;
 
 	ret = bch2_trans_update(trans, &iter, &g->k_i, 0);
-err:
 	bch2_trans_iter_exit(trans, &iter);
 	return ret;
 }
@@ -1312,18 +1298,16 @@ static int bch2_check_discard_freespace_key(struct btree_trans *trans,
 	pos.offset &= ~(~0ULL << 56);
 	genbits = iter->pos.offset & (~0ULL << 56);
 
-	bch2_trans_iter_init(trans, &alloc_iter, BTREE_ID_alloc, pos, 0);
+	alloc_k = bch2_bkey_get_iter(trans, &alloc_iter, BTREE_ID_alloc, pos, 0);
+	ret = bkey_err(alloc_k);
+	if (ret)
+		return ret;
 
 	if (fsck_err_on(!bch2_dev_bucket_exists(c, pos), c,
 			"entry in %s btree for nonexistant dev:bucket %llu:%llu",
 			bch2_btree_ids[iter->btree_id], pos.inode, pos.offset))
 		goto delete;
 
-	alloc_k = bch2_btree_iter_peek_slot(&alloc_iter);
-	ret = bkey_err(alloc_k);
-	if (ret)
-		goto err;
-
 	a = bch2_alloc_to_v4(alloc_k, &a_convert);
 
 	if (fsck_err_on(a->data_type != state ||
@@ -1336,7 +1320,6 @@ static int bch2_check_discard_freespace_key(struct btree_trans *trans,
 			genbits >> 56, alloc_freespace_genbits(*a) >> 56))
 		goto delete;
 out:
-err:
 fsck_err:
 	bch2_trans_iter_exit(trans, &alloc_iter);
 	printbuf_exit(&buf);
@@ -1525,7 +1508,7 @@ static int bch2_check_alloc_to_lru_ref(struct btree_trans *trans,
 	struct btree_iter lru_iter;
 	struct bch_alloc_v4 a_convert;
 	const struct bch_alloc_v4 *a;
-	struct bkey_s_c alloc_k, k;
+	struct bkey_s_c alloc_k, lru_k;
 	struct printbuf buf = PRINTBUF;
 	int ret;
 
@@ -1542,21 +1525,20 @@ static int bch2_check_alloc_to_lru_ref(struct btree_trans *trans,
 	if (a->data_type != BCH_DATA_cached)
 		return 0;
 
-	bch2_trans_iter_init(trans, &lru_iter, BTREE_ID_lru,
+	lru_k = bch2_bkey_get_iter(trans, &lru_iter, BTREE_ID_lru,
 			     lru_pos(alloc_k.k->p.inode,
 				     bucket_to_u64(alloc_k.k->p),
 				     a->io_time[READ]), 0);
-	k = bch2_btree_iter_peek_slot(&lru_iter);
-	ret = bkey_err(k);
+	ret = bkey_err(lru_k);
 	if (ret)
-		goto err;
+		return ret;
 
 	if (fsck_err_on(!a->io_time[READ], c,
 			"cached bucket with read_time 0\n"
 			"  %s",
 		(printbuf_reset(&buf),
 		 bch2_bkey_val_to_text(&buf, c, alloc_k), buf.buf)) ||
-	    fsck_err_on(k.k->type != KEY_TYPE_set, c,
+	    fsck_err_on(lru_k.k->type != KEY_TYPE_set, c,
 			"missing lru entry\n"
 			"  %s",
 			(printbuf_reset(&buf),
@@ -1645,10 +1627,9 @@ static int bch2_discard_one_bucket(struct btree_trans *trans,
 		goto out;
 	}
 
-	bch2_trans_iter_init(trans, &iter, BTREE_ID_alloc,
-			     need_discard_iter->pos,
-			     BTREE_ITER_CACHED);
-	k = bch2_btree_iter_peek_slot(&iter);
+	k = bch2_bkey_get_iter(trans, &iter, BTREE_ID_alloc,
+			       need_discard_iter->pos,
+			       BTREE_ITER_CACHED);
 	ret = bkey_err(k);
 	if (ret)
 		goto out;
diff --git a/libbcachefs/alloc_background.h b/libbcachefs/alloc_background.h
index 32479839..fc4420f4 100644
--- a/libbcachefs/alloc_background.h
+++ b/libbcachefs/alloc_background.h
@@ -159,6 +159,7 @@ void bch2_alloc_to_text(struct printbuf *, struct bch_fs *, struct bkey_s_c);
 	.val_to_text	= bch2_alloc_to_text,		\
 	.trans_trigger	= bch2_trans_mark_alloc,	\
 	.atomic_trigger	= bch2_mark_alloc,		\
+	.min_val_size	= 8,				\
 })
 
 #define bch2_bkey_ops_alloc_v2 ((struct bkey_ops) {	\
@@ -166,6 +167,7 @@ void bch2_alloc_to_text(struct printbuf *, struct bch_fs *, struct bkey_s_c);
 	.val_to_text	= bch2_alloc_to_text,		\
 	.trans_trigger	= bch2_trans_mark_alloc,	\
 	.atomic_trigger	= bch2_mark_alloc,		\
+	.min_val_size	= 8,				\
 })
 
 #define bch2_bkey_ops_alloc_v3 ((struct bkey_ops) {	\
@@ -173,6 +175,7 @@ void bch2_alloc_to_text(struct printbuf *, struct bch_fs *, struct bkey_s_c);
 	.val_to_text	= bch2_alloc_to_text,		\
 	.trans_trigger	= bch2_trans_mark_alloc,	\
 	.atomic_trigger	= bch2_mark_alloc,		\
+	.min_val_size	= 16,				\
 })
 
 #define bch2_bkey_ops_alloc_v4 ((struct bkey_ops) {	\
@@ -181,6 +184,7 @@ void bch2_alloc_to_text(struct printbuf *, struct bch_fs *, struct bkey_s_c);
 	.swab		= bch2_alloc_v4_swab,		\
 	.trans_trigger	= bch2_trans_mark_alloc,	\
 	.atomic_trigger	= bch2_mark_alloc,		\
+	.min_val_size	= 56,				\
 })
 
 int bch2_bucket_gens_invalid(const struct bch_fs *, struct bkey_s_c, unsigned, struct printbuf *);
diff --git a/libbcachefs/alloc_foreground.c b/libbcachefs/alloc_foreground.c
index 350635f3..ec77601e 100644
--- a/libbcachefs/alloc_foreground.c
+++ b/libbcachefs/alloc_foreground.c
@@ -29,11 +29,11 @@
 #include "journal.h"
 #include "movinggc.h"
 #include "nocow_locking.h"
+#include "trace.h"
 
 #include <linux/math64.h>
 #include <linux/rculist.h>
 #include <linux/rcupdate.h>
-#include <trace/events/bcachefs.h>
 
 const char * const bch2_alloc_reserves[] = {
 #define x(t) #t,
@@ -303,8 +303,9 @@ static struct open_bucket *try_alloc_bucket(struct btree_trans *trans, struct bc
 		goto err;
 	}
 
-	bch2_trans_iter_init(trans, &iter, BTREE_ID_alloc, POS(ca->dev_idx, b), BTREE_ITER_CACHED);
-	k = bch2_btree_iter_peek_slot(&iter);
+	k = bch2_bkey_get_iter(trans, &iter,
+			       BTREE_ID_alloc, POS(ca->dev_idx, b),
+			       BTREE_ITER_CACHED);
 	ret = bkey_err(k);
 	if (ret) {
 		ob = ERR_PTR(ret);
diff --git a/libbcachefs/backpointers.c b/libbcachefs/backpointers.c
index a3a1ed6e..e9ae623c 100644
--- a/libbcachefs/backpointers.c
+++ b/libbcachefs/backpointers.c
@@ -43,11 +43,6 @@ int bch2_backpointer_invalid(const struct bch_fs *c, struct bkey_s_c k,
 	struct bkey_s_c_backpointer bp = bkey_s_c_to_backpointer(k);
 	struct bpos bucket = bp_pos_to_bucket(c, bp.k->p);
 
-	if (bkey_val_bytes(bp.k) < sizeof(*bp.v)) {
-		prt_str(err, "incorrect value size");
-		return -BCH_ERR_invalid_bkey;
-	}
-
 	if (!bpos_eq(bp.k->p, bucket_pos_to_bp(c, bucket, bp.v->bucket_offset))) {
 		prt_str(err, "backpointer at wrong pos");
 		return -BCH_ERR_invalid_bkey;
@@ -163,12 +158,11 @@ int bch2_bucket_backpointer_mod_nowritebuffer(struct btree_trans *trans,
 		set_bkey_val_u64s(&bp_k->k, 0);
 	}
 
-	bch2_trans_iter_init(trans, &bp_iter, BTREE_ID_backpointers,
-			     bp_k->k.p,
-			     BTREE_ITER_INTENT|
-			     BTREE_ITER_SLOTS|
-			     BTREE_ITER_WITH_UPDATES);
-	k = bch2_btree_iter_peek_slot(&bp_iter);
+	k = bch2_bkey_get_iter(trans, &bp_iter, BTREE_ID_backpointers,
+			       bp_k->k.p,
+			       BTREE_ITER_INTENT|
+			       BTREE_ITER_SLOTS|
+			       BTREE_ITER_WITH_UPDATES);
 	ret = bkey_err(k);
 	if (ret)
 		goto err;
@@ -207,9 +201,8 @@ int bch2_get_next_backpointer(struct btree_trans *trans,
 		goto done;
 
 	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);
+		k = bch2_bkey_get_iter(trans, &alloc_iter, BTREE_ID_alloc,
+				       bucket, BTREE_ITER_CACHED|iter_flags);
 		ret = bkey_err(k);
 		if (ret)
 			goto out;
@@ -386,10 +379,8 @@ static int bch2_check_btree_backpointer(struct btree_trans *trans, struct btree_
 
 	ca = bch_dev_bkey_exists(c, k.k->p.inode);
 
-	bch2_trans_iter_init(trans, &alloc_iter, BTREE_ID_alloc,
-			     bp_pos_to_bucket(c, k.k->p), 0);
-
-	alloc_k = bch2_btree_iter_peek_slot(&alloc_iter);
+	alloc_k = bch2_bkey_get_iter(trans, &alloc_iter, BTREE_ID_alloc,
+				     bp_pos_to_bucket(c, k.k->p), 0);
 	ret = bkey_err(alloc_k);
 	if (ret)
 		goto out;
@@ -447,10 +438,9 @@ static int check_bp_exists(struct btree_trans *trans,
 	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, bp.bucket_offset),
-			     0);
-	bp_k = bch2_btree_iter_peek_slot(&bp_iter);
+	bp_k = bch2_bkey_get_iter(trans, &bp_iter, BTREE_ID_backpointers,
+				  bucket_pos_to_bp(c, bucket, bp.bucket_offset),
+				  0);
 	ret = bkey_err(bp_k);
 	if (ret)
 		goto err;
diff --git a/libbcachefs/backpointers.h b/libbcachefs/backpointers.h
index 9c03709a..3994bc83 100644
--- a/libbcachefs/backpointers.h
+++ b/libbcachefs/backpointers.h
@@ -17,6 +17,7 @@ void bch2_backpointer_swab(struct bkey_s);
 	.key_invalid	= bch2_backpointer_invalid,	\
 	.val_to_text	= bch2_backpointer_k_to_text,	\
 	.swab		= bch2_backpointer_swab,	\
+	.min_val_size	= 32,				\
 })
 
 #define MAX_EXTENT_COMPRESS_RATIO_SHIFT		10
diff --git a/libbcachefs/bcachefs.h b/libbcachefs/bcachefs.h
index 1e7c810d..e8ec7b84 100644
--- a/libbcachefs/bcachefs.h
+++ b/libbcachefs/bcachefs.h
@@ -445,6 +445,7 @@ enum gc_phase {
 	GC_PHASE_BTREE_need_discard,
 	GC_PHASE_BTREE_backpointers,
 	GC_PHASE_BTREE_bucket_gens,
+	GC_PHASE_BTREE_snapshot_trees,
 
 	GC_PHASE_PENDING_DELETE,
 };
diff --git a/libbcachefs/bcachefs_format.h b/libbcachefs/bcachefs_format.h
index 7d1c0b1e..4d142b2e 100644
--- a/libbcachefs/bcachefs_format.h
+++ b/libbcachefs/bcachefs_format.h
@@ -250,6 +250,11 @@ struct bkey_packed {
 	__u8		pad[sizeof(struct bkey) - 3];
 } __packed __aligned(8);
 
+typedef struct {
+	__le64			lo;
+	__le64			hi;
+} bch_le128;
+
 #define BKEY_U64s			(sizeof(struct bkey) / sizeof(__u64))
 #define BKEY_U64s_MAX			U8_MAX
 #define BKEY_VAL_U64s_MAX		(BKEY_U64s_MAX - BKEY_U64s)
@@ -360,7 +365,8 @@ static inline void bkey_init(struct bkey *k)
 	x(alloc_v4,		27)			\
 	x(backpointer,		28)			\
 	x(inode_v3,		29)			\
-	x(bucket_gens,		30)
+	x(bucket_gens,		30)			\
+	x(snapshot_tree,	31)
 
 enum bch_bkey_type {
 #define x(name, nr) KEY_TYPE_##name	= nr,
@@ -1101,6 +1107,9 @@ struct bch_subvolume {
 	__le32			flags;
 	__le32			snapshot;
 	__le64			inode;
+	__le32			parent;
+	__le32			pad;
+	bch_le128		otime;
 };
 
 LE32_BITMASK(BCH_SUBVOLUME_RO,		struct bch_subvolume, flags,  0,  1)
@@ -1119,7 +1128,7 @@ struct bch_snapshot {
 	__le32			parent;
 	__le32			children[2];
 	__le32			subvol;
-	__le32			pad;
+	__le32			tree;
 };
 
 LE32_BITMASK(BCH_SNAPSHOT_DELETED,	struct bch_snapshot, flags,  0,  1)
@@ -1127,6 +1136,19 @@ 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)
 
+/*
+ * Snapshot trees:
+ *
+ * The snapshot_trees btree gives us persistent indentifier for each tree of
+ * bch_snapshot nodes, and allow us to record and easily find the root/master
+ * subvolume that other snapshots were created from:
+ */
+struct bch_snapshot_tree {
+	struct bch_val		v;
+	__le32			master_subvol;
+	__le32			root_snapshot;
+};
+
 /* LRU btree: */
 
 struct bch_lru {
@@ -1555,7 +1577,8 @@ struct bch_sb_field_journal_seq_blacklist {
 	x(bucket_gens,			25)		\
 	x(lru_v2,			26)		\
 	x(fragmentation_lru,		27)		\
-	x(no_bps_in_alloc_keys,		28)
+	x(no_bps_in_alloc_keys,		28)		\
+	x(snapshot_trees,		29)
 
 enum bcachefs_metadata_version {
 	bcachefs_metadata_version_min = 9,
@@ -1565,6 +1588,8 @@ enum bcachefs_metadata_version {
 	bcachefs_metadata_version_max
 };
 
+static const unsigned bcachefs_metadata_required_upgrade_below = bcachefs_metadata_version_snapshot_trees;
+
 #define bcachefs_metadata_version_current	(bcachefs_metadata_version_max - 1)
 
 #define BCH_SB_SECTOR			8
@@ -2091,7 +2116,8 @@ LE32_BITMASK(JSET_NO_FLUSH,	struct jset, flags, 5, 6);
 	x(freespace,		11)		\
 	x(need_discard,		12)		\
 	x(backpointers,		13)		\
-	x(bucket_gens,		14)
+	x(bucket_gens,		14)		\
+	x(snapshot_trees,	15)
 
 enum btree_id {
 #define x(kwd, val) BTREE_ID_##kwd = val,
diff --git a/libbcachefs/bkey.h b/libbcachefs/bkey.h
index 2650bd63..727bed99 100644
--- a/libbcachefs/bkey.h
+++ b/libbcachefs/bkey.h
@@ -611,20 +611,20 @@ struct bkey_s_##name {							\
 									\
 static inline struct bkey_i_##name *bkey_i_to_##name(struct bkey_i *k)	\
 {									\
-	EBUG_ON(k->k.type != KEY_TYPE_##name);				\
+	EBUG_ON(!IS_ERR_OR_NULL(k) && k->k.type != KEY_TYPE_##name);	\
 	return container_of(&k->k, struct bkey_i_##name, k);		\
 }									\
 									\
 static inline const struct bkey_i_##name *				\
 bkey_i_to_##name##_c(const struct bkey_i *k)				\
 {									\
-	EBUG_ON(k->k.type != KEY_TYPE_##name);				\
+	EBUG_ON(!IS_ERR_OR_NULL(k) && k->k.type != KEY_TYPE_##name);	\
 	return container_of(&k->k, struct bkey_i_##name, k);		\
 }									\
 									\
 static inline struct bkey_s_##name bkey_s_to_##name(struct bkey_s k)	\
 {									\
-	EBUG_ON(k.k->type != KEY_TYPE_##name);				\
+	EBUG_ON(!IS_ERR_OR_NULL(k.k) && k.k->type != KEY_TYPE_##name);	\
 	return (struct bkey_s_##name) {					\
 		.k = k.k,						\
 		.v = container_of(k.v, struct bch_##name, v),		\
@@ -633,7 +633,7 @@ static inline struct bkey_s_##name bkey_s_to_##name(struct bkey_s k)	\
 									\
 static inline struct bkey_s_c_##name bkey_s_c_to_##name(struct bkey_s_c k)\
 {									\
-	EBUG_ON(k.k->type != KEY_TYPE_##name);				\
+	EBUG_ON(!IS_ERR_OR_NULL(k.k) && k.k->type != KEY_TYPE_##name);	\
 	return (struct bkey_s_c_##name) {				\
 		.k = k.k,						\
 		.v = container_of(k.v, struct bch_##name, v),		\
@@ -659,7 +659,7 @@ name##_i_to_s_c(const struct bkey_i_##name *k)				\
 									\
 static inline struct bkey_s_##name bkey_i_to_s_##name(struct bkey_i *k)	\
 {									\
-	EBUG_ON(k->k.type != KEY_TYPE_##name);				\
+	EBUG_ON(!IS_ERR_OR_NULL(k) && k->k.type != KEY_TYPE_##name);	\
 	return (struct bkey_s_##name) {					\
 		.k = &k->k,						\
 		.v = container_of(&k->v, struct bch_##name, v),		\
@@ -669,7 +669,7 @@ static inline struct bkey_s_##name bkey_i_to_s_##name(struct bkey_i *k)	\
 static inline struct bkey_s_c_##name					\
 bkey_i_to_s_c_##name(const struct bkey_i *k)				\
 {									\
-	EBUG_ON(k->k.type != KEY_TYPE_##name);				\
+	EBUG_ON(!IS_ERR_OR_NULL(k) && k->k.type != KEY_TYPE_##name);	\
 	return (struct bkey_s_c_##name) {				\
 		.k = &k->k,						\
 		.v = container_of(&k->v, struct bch_##name, v),		\
diff --git a/libbcachefs/bkey_methods.c b/libbcachefs/bkey_methods.c
index 72d95831..79f3fbe9 100644
--- a/libbcachefs/bkey_methods.c
+++ b/libbcachefs/bkey_methods.c
@@ -56,17 +56,12 @@ static int empty_val_key_invalid(const struct bch_fs *c, struct bkey_s_c k,
 static int key_type_cookie_invalid(const struct bch_fs *c, struct bkey_s_c k,
 				   unsigned flags, struct printbuf *err)
 {
-	if (bkey_val_bytes(k.k) != sizeof(struct bch_cookie)) {
-		prt_printf(err, "incorrect value size (%zu != %zu)",
-		       bkey_val_bytes(k.k), sizeof(struct bch_cookie));
-		return -BCH_ERR_invalid_bkey;
-	}
-
 	return 0;
 }
 
 #define bch2_bkey_ops_cookie ((struct bkey_ops) {	\
-	.key_invalid = key_type_cookie_invalid,		\
+	.key_invalid	= key_type_cookie_invalid,	\
+	.min_val_size	= 8,				\
 })
 
 #define bch2_bkey_ops_hash_whiteout ((struct bkey_ops) {\
@@ -126,12 +121,22 @@ const struct bkey_ops bch2_bkey_ops[] = {
 int bch2_bkey_val_invalid(struct bch_fs *c, struct bkey_s_c k,
 			  unsigned flags, struct printbuf *err)
 {
+	const struct bkey_ops *ops;
+
 	if (k.k->type >= KEY_TYPE_MAX) {
 		prt_printf(err, "invalid type (%u >= %u)", k.k->type, KEY_TYPE_MAX);
 		return -BCH_ERR_invalid_bkey;
 	}
 
-	return bch2_bkey_ops[k.k->type].key_invalid(c, k, flags, err);
+	ops = &bch2_bkey_ops[k.k->type];
+
+	if (bkey_val_bytes(k.k) < ops->min_val_size) {
+		prt_printf(err, "bad val size (%zu < %u)",
+			   bkey_val_bytes(k.k), ops->min_val_size);
+		return -BCH_ERR_invalid_bkey;
+	}
+
+	return ops->key_invalid(c, k, flags, err);
 }
 
 static unsigned bch2_key_types_allowed[] = {
@@ -199,6 +204,9 @@ static unsigned bch2_key_types_allowed[] = {
 	[BKEY_TYPE_bucket_gens] =
 		(1U << KEY_TYPE_deleted)|
 		(1U << KEY_TYPE_bucket_gens),
+	[BKEY_TYPE_snapshot_trees] =
+		(1U << KEY_TYPE_deleted)|
+		(1U << KEY_TYPE_snapshot_tree),
 	[BKEY_TYPE_btree] =
 		(1U << KEY_TYPE_deleted)|
 		(1U << KEY_TYPE_btree_ptr)|
diff --git a/libbcachefs/bkey_methods.h b/libbcachefs/bkey_methods.h
index 6ae51788..a65756e3 100644
--- a/libbcachefs/bkey_methods.h
+++ b/libbcachefs/bkey_methods.h
@@ -34,6 +34,9 @@ struct bkey_ops {
 	void		(*compat)(enum btree_id id, unsigned version,
 				  unsigned big_endian, int write,
 				  struct bkey_s);
+
+	/* Size of value type when first created: */
+	unsigned	min_val_size;
 };
 
 extern const struct bkey_ops bch2_bkey_ops[];
@@ -80,10 +83,9 @@ static inline int bch2_mark_key(struct btree_trans *trans,
 }
 
 enum btree_update_flags {
-	__BTREE_UPDATE_INTERNAL_SNAPSHOT_NODE,
+	__BTREE_UPDATE_INTERNAL_SNAPSHOT_NODE = __BTREE_ITER_FLAGS_END,
 	__BTREE_UPDATE_NOJOURNAL,
 	__BTREE_UPDATE_KEY_CACHE_RECLAIM,
-	__BTREE_UPDATE_NO_KEY_CACHE_COHERENCY,
 
 	__BTREE_TRIGGER_NORUN,		/* Don't run triggers at all */
 
@@ -98,8 +100,6 @@ enum btree_update_flags {
 #define BTREE_UPDATE_INTERNAL_SNAPSHOT_NODE (1U << __BTREE_UPDATE_INTERNAL_SNAPSHOT_NODE)
 #define BTREE_UPDATE_NOJOURNAL		(1U << __BTREE_UPDATE_NOJOURNAL)
 #define BTREE_UPDATE_KEY_CACHE_RECLAIM	(1U << __BTREE_UPDATE_KEY_CACHE_RECLAIM)
-#define BTREE_UPDATE_NO_KEY_CACHE_COHERENCY	\
-	(1U << __BTREE_UPDATE_NO_KEY_CACHE_COHERENCY)
 
 #define BTREE_TRIGGER_NORUN		(1U << __BTREE_TRIGGER_NORUN)
 
diff --git a/libbcachefs/bset.c b/libbcachefs/bset.c
index 0216ad96..a4c06e85 100644
--- a/libbcachefs/bset.c
+++ b/libbcachefs/bset.c
@@ -10,6 +10,7 @@
 #include "btree_cache.h"
 #include "bset.h"
 #include "eytzinger.h"
+#include "trace.h"
 #include "util.h"
 
 #include <asm/unaligned.h>
@@ -17,10 +18,6 @@
 #include <linux/random.h>
 #include <linux/prefetch.h>
 
-/* hack.. */
-#include "alloc_types.h"
-#include <trace/events/bcachefs.h>
-
 static inline void __bch2_btree_node_iter_advance(struct btree_node_iter *,
 						  struct btree *);
 
diff --git a/libbcachefs/btree_cache.c b/libbcachefs/btree_cache.c
index c53597a2..73d32688 100644
--- a/libbcachefs/btree_cache.c
+++ b/libbcachefs/btree_cache.c
@@ -9,11 +9,11 @@
 #include "debug.h"
 #include "errcode.h"
 #include "error.h"
+#include "trace.h"
 
 #include <linux/prefetch.h>
 #include <linux/sched/mm.h>
 #include <linux/seq_buf.h>
-#include <trace/events/bcachefs.h>
 
 #define BTREE_CACHE_NOT_FREED_INCREMENT(counter) \
 do {						 \
diff --git a/libbcachefs/btree_gc.c b/libbcachefs/btree_gc.c
index fb4226aa..02154c38 100644
--- a/libbcachefs/btree_gc.c
+++ b/libbcachefs/btree_gc.c
@@ -27,6 +27,7 @@
 #include "reflink.h"
 #include "replicas.h"
 #include "super-io.h"
+#include "trace.h"
 
 #include <linux/slab.h>
 #include <linux/bitops.h>
@@ -35,7 +36,6 @@
 #include <linux/preempt.h>
 #include <linux/rcupdate.h>
 #include <linux/sched/task.h>
-#include <trace/events/bcachefs.h>
 
 #define DROP_THIS_NODE		10
 #define DROP_PREV_NODE		11
@@ -1594,7 +1594,7 @@ static int bch2_gc_write_reflink_key(struct btree_trans *trans,
 			"  should be %u",
 			(bch2_bkey_val_to_text(&buf, c, k), buf.buf),
 			r->refcount)) {
-		struct bkey_i *new = bch2_bkey_make_mut(trans, k);
+		struct bkey_i *new = bch2_bkey_make_mut(trans, iter, k, 0);
 
 		ret = PTR_ERR_OR_ZERO(new);
 		if (ret)
@@ -1604,8 +1604,6 @@ static int bch2_gc_write_reflink_key(struct btree_trans *trans,
 			new->k.type = KEY_TYPE_deleted;
 		else
 			*bkey_refcount(new) = cpu_to_le64(r->refcount);
-
-		ret = bch2_trans_update(trans, iter, new, 0);
 	}
 fsck_err:
 	printbuf_exit(&buf);
@@ -1802,9 +1800,10 @@ again:
 
 	bch2_mark_superblocks(c);
 
-	if (BCH_SB_HAS_TOPOLOGY_ERRORS(c->disk_sb.sb) &&
-	    !test_bit(BCH_FS_INITIAL_GC_DONE, &c->flags) &&
-	    c->opts.fix_errors != FSCK_OPT_NO) {
+	if (IS_ENABLED(CONFIG_BCACHEFS_DEBUG) ||
+	    (BCH_SB_HAS_TOPOLOGY_ERRORS(c->disk_sb.sb) &&
+	     !test_bit(BCH_FS_INITIAL_GC_DONE, &c->flags) &&
+	     c->opts.fix_errors != FSCK_OPT_NO)) {
 		bch_info(c, "Starting topology repair pass");
 		ret = bch2_repair_topology(c);
 		if (ret)
@@ -1920,13 +1919,13 @@ static int gc_btree_gens_key(struct btree_trans *trans,
 	percpu_up_read(&c->mark_lock);
 	return 0;
 update:
-	u = bch2_bkey_make_mut(trans, k);
+	u = bch2_bkey_make_mut(trans, iter, k, 0);
 	ret = PTR_ERR_OR_ZERO(u);
 	if (ret)
 		return ret;
 
 	bch2_extent_normalize(c, bkey_i_to_s(u));
-	return bch2_trans_update(trans, iter, u, 0);
+	return 0;
 }
 
 static int bch2_alloc_write_oldest_gen(struct btree_trans *trans, struct btree_iter *iter,
diff --git a/libbcachefs/btree_io.c b/libbcachefs/btree_io.c
index 945d1b9e..decbbaac 100644
--- a/libbcachefs/btree_io.c
+++ b/libbcachefs/btree_io.c
@@ -18,9 +18,9 @@
 #include "journal_reclaim.h"
 #include "journal_seq_blacklist.h"
 #include "super-io.h"
+#include "trace.h"
 
 #include <linux/sched/mm.h>
-#include <trace/events/bcachefs.h>
 
 void bch2_btree_node_io_unlock(struct btree *b)
 {
@@ -105,8 +105,8 @@ static void btree_bounce_free(struct bch_fs *c, size_t size,
 		vpfree(p, size);
 }
 
-static void *_btree_bounce_alloc(struct bch_fs *c, size_t size,
-				 bool *used_mempool)
+static void *btree_bounce_alloc(struct bch_fs *c, size_t size,
+				bool *used_mempool)
 {
 	unsigned flags = memalloc_nofs_save();
 	void *p;
@@ -114,7 +114,7 @@ static void *_btree_bounce_alloc(struct bch_fs *c, size_t size,
 	BUG_ON(size > btree_bytes(c));
 
 	*used_mempool = false;
-	p = _vpmalloc(size, __GFP_NOWARN|GFP_NOWAIT);
+	p = vpmalloc(size, __GFP_NOWARN|GFP_NOWAIT);
 	if (!p) {
 		*used_mempool = true;
 		p = mempool_alloc(&c->btree_bounce_pool, GFP_NOIO);
@@ -122,8 +122,6 @@ static void *_btree_bounce_alloc(struct bch_fs *c, size_t size,
 	memalloc_nofs_restore(flags);
 	return p;
 }
-#define btree_bounce_alloc(_c, _size, _used_mempool)		\
-	alloc_hooks(_btree_bounce_alloc(_c, _size, _used_mempool), void *, NULL)
 
 static void sort_bkey_ptrs(const struct btree *bt,
 			   struct bkey_packed **ptrs, unsigned nr)
diff --git a/libbcachefs/btree_iter.c b/libbcachefs/btree_iter.c
index f524e4b3..365794dc 100644
--- a/libbcachefs/btree_iter.c
+++ b/libbcachefs/btree_iter.c
@@ -15,10 +15,10 @@
 #include "recovery.h"
 #include "replicas.h"
 #include "subvolume.h"
+#include "trace.h"
 
 #include <linux/random.h>
 #include <linux/prefetch.h>
-#include <trace/events/bcachefs.h>
 
 static inline void btree_path_list_remove(struct btree_trans *, struct btree_path *);
 static inline void btree_path_list_add(struct btree_trans *, struct btree_path *,
diff --git a/libbcachefs/btree_iter.h b/libbcachefs/btree_iter.h
index 6b7cef14..02dd81a1 100644
--- a/libbcachefs/btree_iter.h
+++ b/libbcachefs/btree_iter.h
@@ -4,8 +4,14 @@
 
 #include "bset.h"
 #include "btree_types.h"
+#include "trace.h"
 
-#include <trace/events/bcachefs.h>
+static inline int __bkey_err(const struct bkey *k)
+{
+	return PTR_ERR_OR_ZERO(k);
+}
+
+#define bkey_err(_k)	__bkey_err((_k).k)
 
 static inline void __btree_path_get(struct btree_path *path, bool intent)
 {
@@ -477,48 +483,61 @@ static inline void *bch2_trans_kmalloc_nomemzero(struct btree_trans *trans, size
 	}
 }
 
-static inline struct bkey_i *bch2_bkey_make_mut(struct btree_trans *trans, struct bkey_s_c k)
+static inline struct bkey_s_c __bch2_bkey_get_iter(struct btree_trans *trans,
+				struct btree_iter *iter,
+				unsigned btree_id, struct bpos pos,
+				unsigned flags, unsigned type)
 {
-	struct bkey_i *mut = bch2_trans_kmalloc_nomemzero(trans, bkey_bytes(k.k));
+	struct bkey_s_c k;
 
-	if (!IS_ERR(mut))
-		bkey_reassemble(mut, k);
-	return mut;
+	bch2_trans_iter_init(trans, iter, btree_id, pos, flags);
+	k = bch2_btree_iter_peek_slot(iter);
+
+	if (!bkey_err(k) && type && k.k->type != type)
+		k = bkey_s_c_err(-ENOENT);
+	if (unlikely(bkey_err(k)))
+		bch2_trans_iter_exit(trans, iter);
+	return k;
 }
 
-static inline struct bkey_i *bch2_bkey_get_mut(struct btree_trans *trans,
-					       struct btree_iter *iter)
+static inline struct bkey_s_c bch2_bkey_get_iter(struct btree_trans *trans,
+				struct btree_iter *iter,
+				unsigned btree_id, struct bpos pos,
+				unsigned flags)
 {
-	struct bkey_s_c k = bch2_btree_iter_peek_slot(iter);
-
-	return unlikely(IS_ERR(k.k))
-		? ERR_CAST(k.k)
-		: bch2_bkey_make_mut(trans, k);
+	return __bch2_bkey_get_iter(trans, iter, btree_id, pos, flags, 0);
 }
 
-#define bch2_bkey_get_mut_typed(_trans, _iter, _type)			\
-({									\
-	struct bkey_i *_k = bch2_bkey_get_mut(_trans, _iter);		\
-	struct bkey_i_##_type *_ret;					\
-									\
-	if (IS_ERR(_k))							\
-		_ret = ERR_CAST(_k);					\
-	else if (unlikely(_k->k.type != KEY_TYPE_##_type))		\
-		_ret = ERR_PTR(-ENOENT);				\
-	else								\
-		_ret = bkey_i_to_##_type(_k);				\
-	_ret;								\
-})
+#define bch2_bkey_get_iter_typed(_trans, _iter, _btree_id, _pos, _flags, _type)\
+	bkey_s_c_to_##_type(__bch2_bkey_get_iter(_trans, _iter,			\
+				       _btree_id, _pos, _flags, KEY_TYPE_##_type))
 
-#define bch2_bkey_alloc(_trans, _iter, _type)				\
-({									\
-	struct bkey_i_##_type *_k = bch2_trans_kmalloc_nomemzero(_trans, sizeof(*_k));\
-	if (!IS_ERR(_k)) {						\
-		bkey_##_type##_init(&_k->k_i);				\
-		_k->k.p	= (_iter)->pos;					\
-	}								\
-	_k;								\
-})
+static inline int __bch2_bkey_get_val_typed(struct btree_trans *trans,
+				unsigned btree_id, struct bpos pos,
+				unsigned flags, unsigned type,
+				unsigned val_size, void *val)
+{
+	struct btree_iter iter;
+	struct bkey_s_c k;
+	int ret;
+
+	k = __bch2_bkey_get_iter(trans, &iter, btree_id, pos, flags, type);
+	ret = bkey_err(k);
+	if (!ret) {
+		unsigned b = min_t(unsigned, bkey_val_bytes(k.k), val_size);
+
+		memcpy(val, k.v, b);
+		if (unlikely(b < sizeof(*val)))
+			memset((void *) val + b, 0, sizeof(*val) - b);
+		bch2_trans_iter_exit(trans, &iter);
+	}
+
+	return ret;
+}
+
+#define bch2_bkey_get_val_typed(_trans, _btree_id, _pos, _flags, _type, _val)\
+	__bch2_bkey_get_val_typed(_trans, _btree_id, _pos, _flags,	\
+				  KEY_TYPE_##_type, sizeof(*_val), _val)
 
 u32 bch2_trans_begin(struct btree_trans *);
 
@@ -540,11 +559,6 @@ u32 bch2_trans_begin(struct btree_trans *);
 	__for_each_btree_node(_trans, _iter, _btree_id, _start,		\
 			      0, 0, _flags, _b, _ret)
 
-static inline int bkey_err(struct bkey_s_c k)
-{
-	return PTR_ERR_OR_ZERO(k.k);
-}
-
 static inline struct bkey_s_c bch2_btree_iter_peek_prev_type(struct btree_iter *iter,
 							     unsigned flags)
 {
diff --git a/libbcachefs/btree_key_cache.c b/libbcachefs/btree_key_cache.c
index 33269afe..3b333e3b 100644
--- a/libbcachefs/btree_key_cache.c
+++ b/libbcachefs/btree_key_cache.c
@@ -10,10 +10,10 @@
 #include "error.h"
 #include "journal.h"
 #include "journal_reclaim.h"
+#include "trace.h"
 
 #include <linux/sched/mm.h>
 #include <linux/seq_buf.h>
-#include <trace/events/bcachefs.h>
 
 static inline bool btree_uses_pcpu_readers(enum btree_id id)
 {
@@ -387,10 +387,9 @@ static int btree_key_cache_fill(struct btree_trans *trans,
 	struct bkey_i *new_k = NULL;
 	int ret;
 
-	bch2_trans_iter_init(trans, &iter, ck->key.btree_id, ck->key.pos,
-			     BTREE_ITER_KEY_CACHE_FILL|
-			     BTREE_ITER_CACHED_NOFILL);
-	k = bch2_btree_iter_peek_slot(&iter);
+	k = bch2_bkey_get_iter(trans, &iter, ck->key.btree_id, ck->key.pos,
+			       BTREE_ITER_KEY_CACHE_FILL|
+			       BTREE_ITER_CACHED_NOFILL);
 	ret = bkey_err(k);
 	if (ret)
 		goto err;
diff --git a/libbcachefs/btree_types.h b/libbcachefs/btree_types.h
index 6250f34f..d4ff7212 100644
--- a/libbcachefs/btree_types.h
+++ b/libbcachefs/btree_types.h
@@ -221,6 +221,7 @@ static const u16 BTREE_ITER_FILTER_SNAPSHOTS	= 1 << 12;
 static const u16 BTREE_ITER_NOPRESERVE		= 1 << 13;
 static const u16 BTREE_ITER_CACHED_NOFILL	= 1 << 14;
 static const u16 BTREE_ITER_KEY_CACHE_FILL	= 1 << 15;
+#define __BTREE_ITER_FLAGS_END			       16
 
 enum btree_path_uptodate {
 	BTREE_ITER_UPTODATE		= 0,
diff --git a/libbcachefs/btree_update.h b/libbcachefs/btree_update.h
index 4adb6f64..1ac3a81e 100644
--- a/libbcachefs/btree_update.h
+++ b/libbcachefs/btree_update.h
@@ -86,6 +86,9 @@ int bch2_btree_node_update_key_get_iter(struct btree_trans *,
 int bch2_trans_update_extent(struct btree_trans *, struct btree_iter *,
 			     struct bkey_i *, enum btree_update_flags);
 
+int bch2_bkey_get_empty_slot(struct btree_trans *, struct btree_iter *,
+			     enum btree_id, struct bpos);
+
 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 *,
@@ -183,4 +186,150 @@ static inline void bch2_trans_reset_updates(struct btree_trans *trans)
 	}
 }
 
+static inline struct bkey_i *__bch2_bkey_make_mut_noupdate(struct btree_trans *trans, struct bkey_s_c k,
+						  unsigned type, unsigned min_bytes)
+{
+	unsigned bytes = max_t(unsigned, min_bytes, bkey_bytes(k.k));
+	struct bkey_i *mut;
+
+	if (type && k.k->type != type)
+		return ERR_PTR(-ENOENT);
+
+	mut = bch2_trans_kmalloc_nomemzero(trans, bytes);
+	if (!IS_ERR(mut)) {
+		bkey_reassemble(mut, k);
+
+		if (unlikely(bytes > bkey_bytes(k.k))) {
+			memset((void *) mut + bkey_bytes(k.k), 0,
+			       bytes - bkey_bytes(k.k));
+			mut->k.u64s = DIV_ROUND_UP(bytes, sizeof(u64));
+		}
+	}
+	return mut;
+}
+
+static inline struct bkey_i *bch2_bkey_make_mut_noupdate(struct btree_trans *trans, struct bkey_s_c k)
+{
+	return __bch2_bkey_make_mut_noupdate(trans, k, 0, 0);
+}
+
+#define bch2_bkey_make_mut_noupdate_typed(_trans, _k, _type)		\
+	bkey_i_to_##_type(__bch2_bkey_make_mut_noupdate(_trans, _k,	\
+				KEY_TYPE_##_type, sizeof(struct bkey_i_##_type)))
+
+static inline struct bkey_i *__bch2_bkey_make_mut(struct btree_trans *trans, struct btree_iter *iter,
+					struct bkey_s_c k, unsigned flags,
+					unsigned type, unsigned min_bytes)
+{
+	struct bkey_i *mut = __bch2_bkey_make_mut_noupdate(trans, k, type, min_bytes);
+	int ret;
+
+	if (IS_ERR(mut))
+		return mut;
+
+	ret = bch2_trans_update(trans, iter, mut, flags);
+	if (ret)
+		return ERR_PTR(ret);
+	return mut;
+}
+
+static inline struct bkey_i *bch2_bkey_make_mut(struct btree_trans *trans, struct btree_iter *iter,
+						struct bkey_s_c k, unsigned flags)
+{
+	return __bch2_bkey_make_mut(trans, iter, k, flags, 0, 0);
+}
+
+#define bch2_bkey_make_mut_typed(_trans, _iter, _k, _flags, _type)	\
+	bkey_i_to_##_type(__bch2_bkey_make_mut(_trans, _iter, _k, _flags,\
+				KEY_TYPE_##_type, sizeof(struct bkey_i_##_type)))
+
+static inline struct bkey_i *__bch2_bkey_get_mut_noupdate(struct btree_trans *trans,
+					 struct btree_iter *iter,
+					 unsigned btree_id, struct bpos pos,
+					 unsigned flags, unsigned type, unsigned min_bytes)
+{
+	struct bkey_s_c k = __bch2_bkey_get_iter(trans, iter,
+				btree_id, pos, flags|BTREE_ITER_INTENT, type);
+	struct bkey_i *ret = unlikely(IS_ERR(k.k))
+		? ERR_CAST(k.k)
+		: __bch2_bkey_make_mut_noupdate(trans, k, 0, min_bytes);
+	if (unlikely(IS_ERR(ret)))
+		bch2_trans_iter_exit(trans, iter);
+	return ret;
+}
+
+static inline struct bkey_i *bch2_bkey_get_mut_noupdate(struct btree_trans *trans,
+					       struct btree_iter *iter,
+					       unsigned btree_id, struct bpos pos,
+					       unsigned flags)
+{
+	return __bch2_bkey_get_mut_noupdate(trans, iter, btree_id, pos, flags, 0, 0);
+}
+
+static inline struct bkey_i *__bch2_bkey_get_mut(struct btree_trans *trans,
+					 struct btree_iter *iter,
+					 unsigned btree_id, struct bpos pos,
+					 unsigned flags, unsigned type, unsigned min_bytes)
+{
+	struct bkey_i *mut = __bch2_bkey_get_mut_noupdate(trans, iter,
+				btree_id, pos, flags|BTREE_ITER_INTENT, type, min_bytes);
+	int ret;
+
+	if (IS_ERR(mut))
+		return mut;
+
+	ret = bch2_trans_update(trans, iter, mut, flags);
+	if (ret) {
+		bch2_trans_iter_exit(trans, iter);
+		return ERR_PTR(ret);
+	}
+
+	return mut;
+}
+
+static inline struct bkey_i *bch2_bkey_get_mut_minsize(struct btree_trans *trans,
+						       struct btree_iter *iter,
+						       unsigned btree_id, struct bpos pos,
+						       unsigned flags, unsigned min_bytes)
+{
+	return __bch2_bkey_get_mut(trans, iter, btree_id, pos, flags, 0, min_bytes);
+}
+
+static inline struct bkey_i *bch2_bkey_get_mut(struct btree_trans *trans,
+					       struct btree_iter *iter,
+					       unsigned btree_id, struct bpos pos,
+					       unsigned flags)
+{
+	return __bch2_bkey_get_mut(trans, iter, btree_id, pos, flags, 0, 0);
+}
+
+#define bch2_bkey_get_mut_typed(_trans, _iter, _btree_id, _pos, _flags, _type)\
+	bkey_i_to_##_type(__bch2_bkey_get_mut(_trans, _iter,		\
+			_btree_id, _pos, _flags,			\
+			KEY_TYPE_##_type, sizeof(struct bkey_i_##_type)))
+
+static inline struct bkey_i *__bch2_bkey_alloc(struct btree_trans *trans, struct btree_iter *iter,
+					       unsigned flags, unsigned type, unsigned val_size)
+{
+	struct bkey_i *k = bch2_trans_kmalloc(trans, sizeof(*k) + val_size);
+	int ret;
+
+	if (IS_ERR(k))
+		return k;
+
+	bkey_init(&k->k);
+	k->k.p = iter->pos;
+	k->k.type = type;
+	set_bkey_val_bytes(&k->k, val_size);
+
+	ret = bch2_trans_update(trans, iter, k, flags);
+	if (unlikely(ret))
+		return ERR_PTR(ret);
+	return k;
+}
+
+#define bch2_bkey_alloc(_trans, _iter, _flags, _type)			\
+	bkey_i_to_##_type(__bch2_bkey_alloc(_trans, _iter, _flags,	\
+				KEY_TYPE_##_type, sizeof(struct bch_##_type)))
+
 #endif /* _BCACHEFS_BTREE_UPDATE_H */
diff --git a/libbcachefs/btree_update_interior.c b/libbcachefs/btree_update_interior.c
index e42e8521..6ba0954e 100644
--- a/libbcachefs/btree_update_interior.c
+++ b/libbcachefs/btree_update_interior.c
@@ -20,9 +20,9 @@
 #include "recovery.h"
 #include "replicas.h"
 #include "super-io.h"
+#include "trace.h"
 
 #include <linux/random.h>
-#include <trace/events/bcachefs.h>
 
 static int bch2_btree_insert_node(struct btree_update *, struct btree_trans *,
 				  struct btree_path *, struct btree *,
diff --git a/libbcachefs/btree_update_leaf.c b/libbcachefs/btree_update_leaf.c
index c17d048b..33693467 100644
--- a/libbcachefs/btree_update_leaf.c
+++ b/libbcachefs/btree_update_leaf.c
@@ -20,10 +20,10 @@
 #include "recovery.h"
 #include "subvolume.h"
 #include "replicas.h"
+#include "trace.h"
 
 #include <linux/prefetch.h>
 #include <linux/sort.h>
-#include <trace/events/bcachefs.h>
 
 /*
  * bch2_btree_path_peek_slot() for a cached iterator might return a key in a
@@ -1268,7 +1268,7 @@ static noinline int extent_front_merge(struct btree_trans *trans,
 	struct bkey_i *update;
 	int ret;
 
-	update = bch2_bkey_make_mut(trans, k);
+	update = bch2_bkey_make_mut_noupdate(trans, k);
 	ret = PTR_ERR_OR_ZERO(update);
 	if (ret)
 		return ret;
@@ -1390,7 +1390,7 @@ int bch2_trans_update_extent(struct btree_trans *trans,
 			trans->extra_journal_res += compressed_sectors;
 
 		if (front_split) {
-			update = bch2_bkey_make_mut(trans, k);
+			update = bch2_bkey_make_mut_noupdate(trans, k);
 			if ((ret = PTR_ERR_OR_ZERO(update)))
 				goto err;
 
@@ -1404,7 +1404,7 @@ int bch2_trans_update_extent(struct btree_trans *trans,
 
 		if (k.k->p.snapshot != insert->k.p.snapshot &&
 		    (front_split || back_split)) {
-			update = bch2_bkey_make_mut(trans, k);
+			update = bch2_bkey_make_mut_noupdate(trans, k);
 			if ((ret = PTR_ERR_OR_ZERO(update)))
 				goto err;
 
@@ -1443,7 +1443,7 @@ int bch2_trans_update_extent(struct btree_trans *trans,
 		}
 
 		if (back_split) {
-			update = bch2_bkey_make_mut(trans, k);
+			update = bch2_bkey_make_mut_noupdate(trans, k);
 			if ((ret = PTR_ERR_OR_ZERO(update)))
 				goto err;
 
@@ -1501,21 +1501,31 @@ static noinline int flush_new_cached_update(struct btree_trans *trans,
 					    unsigned long ip)
 {
 	struct btree_path *btree_path;
+	struct bkey k;
 	int ret;
 
-	i->key_cache_already_flushed = true;
-	i->flags |= BTREE_TRIGGER_NORUN;
-
 	btree_path = bch2_path_get(trans, path->btree_id, path->pos, 1, 0,
 				   BTREE_ITER_INTENT, _THIS_IP_);
-
 	ret = bch2_btree_path_traverse(trans, btree_path, 0);
 	if (ret)
-		goto err;
+		goto out;
+
+	/*
+	 * The old key in the insert entry might actually refer to an existing
+	 * key in the btree that has been deleted from cache and not yet
+	 * flushed. Check for this and skip the flush so we don't run triggers
+	 * against a stale key.
+	 */
+	bch2_btree_path_peek_slot_exact(btree_path, &k);
+	if (!bkey_deleted(&k))
+		goto out;
+
+	i->key_cache_already_flushed = true;
+	i->flags |= BTREE_TRIGGER_NORUN;
 
 	btree_path_set_should_be_locked(btree_path);
 	ret = bch2_trans_update_by_path_trace(trans, btree_path, i->k, flags, ip);
-err:
+out:
 	bch2_path_put(trans, btree_path, true);
 	return ret;
 }
@@ -1596,9 +1606,7 @@ bch2_trans_update_by_path_trace(struct btree_trans *trans, struct btree_path *pa
 	 * the key cache - but the key has to exist in the btree for that to
 	 * work:
 	 */
-	if (path->cached &&
-	    bkey_deleted(&i->old_k) &&
-	    !(flags & BTREE_UPDATE_NO_KEY_CACHE_COHERENCY))
+	if (path->cached && bkey_deleted(&i->old_k))
 		return flush_new_cached_update(trans, path, i, flags, ip);
 
 	return 0;
@@ -1727,6 +1735,37 @@ int __must_check bch2_trans_update_buffered(struct btree_trans *trans,
 	return 0;
 }
 
+int bch2_bkey_get_empty_slot(struct btree_trans *trans, struct btree_iter *iter,
+			     enum btree_id btree, struct bpos end)
+{
+	struct bkey_s_c k;
+	int ret = 0;
+
+	bch2_trans_iter_init(trans, iter, btree, POS_MAX, BTREE_ITER_INTENT);
+	k = bch2_btree_iter_prev(iter);
+	ret = bkey_err(k);
+	if (ret)
+		goto err;
+
+	bch2_btree_iter_advance(iter);
+	k = bch2_btree_iter_peek_slot(iter);
+	ret = bkey_err(k);
+	if (ret)
+		goto err;
+
+	BUG_ON(k.k->type != KEY_TYPE_deleted);
+
+	if (bkey_gt(k.k->p, end)) {
+		ret = -BCH_ERR_ENOSPC_btree_slot;
+		goto err;
+	}
+
+	return 0;
+err:
+	bch2_trans_iter_exit(trans, iter);
+	return ret;
+}
+
 void bch2_trans_commit_hook(struct btree_trans *trans,
 			    struct btree_trans_commit_hook *h)
 {
diff --git a/libbcachefs/buckets.c b/libbcachefs/buckets.c
index 0362e10e..bce42eef 100644
--- a/libbcachefs/buckets.c
+++ b/libbcachefs/buckets.c
@@ -21,9 +21,9 @@
 #include "reflink.h"
 #include "replicas.h"
 #include "subvolume.h"
+#include "trace.h"
 
 #include <linux/preempt.h>
-#include <trace/events/bcachefs.h>
 
 static inline void fs_usage_data_type_to_base(struct bch_fs_usage *fs_usage,
 					      enum bch_data_type data_type,
@@ -1448,10 +1448,9 @@ static int bch2_trans_mark_stripe_ptr(struct btree_trans *trans,
 	struct bch_replicas_padded r;
 	int ret = 0;
 
-	bch2_trans_iter_init(trans, &iter, BTREE_ID_stripes, POS(0, p.ec.idx),
-			     BTREE_ITER_INTENT|
-			     BTREE_ITER_WITH_UPDATES);
-	s = bch2_bkey_get_mut_typed(trans, &iter, stripe);
+	s = bch2_bkey_get_mut_typed(trans, &iter,
+			BTREE_ID_stripes, POS(0, p.ec.idx),
+			BTREE_ITER_WITH_UPDATES, stripe);
 	ret = PTR_ERR_OR_ZERO(s);
 	if (unlikely(ret)) {
 		bch2_trans_inconsistent_on(ret == -ENOENT, trans,
@@ -1472,10 +1471,6 @@ static int bch2_trans_mark_stripe_ptr(struct btree_trans *trans,
 		stripe_blockcount_get(&s->v, p.ec.block) +
 		sectors);
 
-	ret = bch2_trans_update(trans, &iter, &s->k_i, 0);
-	if (ret)
-		goto err;
-
 	bch2_bkey_to_replicas(&r.e, bkey_i_to_s_c(&s->k_i));
 	r.e.data_type = data_type;
 	update_replicas_list(trans, &r.e, sectors);
@@ -1750,10 +1745,9 @@ static int __bch2_trans_mark_reflink_p(struct btree_trans *trans,
 	struct printbuf buf = PRINTBUF;
 	int ret;
 
-	bch2_trans_iter_init(trans, &iter, BTREE_ID_reflink, POS(0, *idx),
-			     BTREE_ITER_INTENT|
-			     BTREE_ITER_WITH_UPDATES);
-	k = bch2_bkey_get_mut(trans, &iter);
+	k = bch2_bkey_get_mut_noupdate(trans, &iter,
+			BTREE_ID_reflink, POS(0, *idx),
+			BTREE_ITER_WITH_UPDATES);
 	ret = PTR_ERR_OR_ZERO(k);
 	if (ret)
 		goto err;
diff --git a/libbcachefs/data_update.c b/libbcachefs/data_update.c
index 0e29ff56..c709538c 100644
--- a/libbcachefs/data_update.c
+++ b/libbcachefs/data_update.c
@@ -14,8 +14,7 @@
 #include "move.h"
 #include "nocow_locking.h"
 #include "subvolume.h"
-
-#include <trace/events/bcachefs.h>
+#include "trace.h"
 
 static int insert_snapshot_whiteouts(struct btree_trans *trans,
 				     enum btree_id id,
@@ -58,10 +57,9 @@ static int insert_snapshot_whiteouts(struct btree_trans *trans,
 
 			whiteout_pos.snapshot = k.k->p.snapshot;
 
-			bch2_trans_iter_init(trans, &iter2, id, whiteout_pos,
-					     BTREE_ITER_NOT_EXTENTS|
-					     BTREE_ITER_INTENT);
-			k2 = bch2_btree_iter_peek_slot(&iter2);
+			k2 = bch2_bkey_get_iter(trans, &iter2, id, whiteout_pos,
+						BTREE_ITER_NOT_EXTENTS|
+						BTREE_ITER_INTENT);
 			ret = bkey_err(k2);
 
 			if (!ret && k2.k->type == KEY_TYPE_deleted) {
diff --git a/libbcachefs/dirent.c b/libbcachefs/dirent.c
index 4c85d339..1544fc56 100644
--- a/libbcachefs/dirent.c
+++ b/libbcachefs/dirent.c
@@ -89,12 +89,6 @@ int bch2_dirent_invalid(const struct bch_fs *c, struct bkey_s_c k,
 	struct bkey_s_c_dirent d = bkey_s_c_to_dirent(k);
 	unsigned len;
 
-	if (bkey_val_bytes(k.k) < sizeof(struct bch_dirent)) {
-		prt_printf(err, "incorrect value size (%zu < %zu)",
-		       bkey_val_bytes(k.k), sizeof(*d.v));
-		return -BCH_ERR_invalid_bkey;
-	}
-
 	len = bch2_dirent_name_bytes(d);
 	if (!len) {
 		prt_printf(err, "empty name");
diff --git a/libbcachefs/dirent.h b/libbcachefs/dirent.h
index ad131e8e..bf9ea2e3 100644
--- a/libbcachefs/dirent.h
+++ b/libbcachefs/dirent.h
@@ -12,6 +12,7 @@ void bch2_dirent_to_text(struct printbuf *, struct bch_fs *, struct bkey_s_c);
 #define bch2_bkey_ops_dirent ((struct bkey_ops) {	\
 	.key_invalid	= bch2_dirent_invalid,		\
 	.val_to_text	= bch2_dirent_to_text,		\
+	.min_val_size	= 16,				\
 })
 
 struct qstr;
diff --git a/libbcachefs/ec.c b/libbcachefs/ec.c
index 1855d08e..439fa540 100644
--- a/libbcachefs/ec.c
+++ b/libbcachefs/ec.c
@@ -119,12 +119,6 @@ int bch2_stripe_invalid(const struct bch_fs *c, struct bkey_s_c k,
 		return -BCH_ERR_invalid_bkey;
 	}
 
-	if (bkey_val_bytes(k.k) < sizeof(*s)) {
-		prt_printf(err, "incorrect value size (%zu < %zu)",
-		       bkey_val_bytes(k.k), sizeof(*s));
-		return -BCH_ERR_invalid_bkey;
-	}
-
 	if (bkey_val_u64s(k.k) < stripe_val_u64s(s)) {
 		prt_printf(err, "incorrect value size (%zu < %u)",
 		       bkey_val_u64s(k.k), stripe_val_u64s(s));
@@ -458,9 +452,8 @@ static int get_stripe_key_trans(struct btree_trans *trans, u64 idx,
 	struct bkey_s_c k;
 	int ret;
 
-	bch2_trans_iter_init(trans, &iter, BTREE_ID_stripes,
-			     POS(0, idx), BTREE_ITER_SLOTS);
-	k = bch2_btree_iter_peek_slot(&iter);
+	k = bch2_bkey_get_iter(trans, &iter, BTREE_ID_stripes,
+			       POS(0, idx), BTREE_ITER_SLOTS);
 	ret = bkey_err(k);
 	if (ret)
 		goto err;
@@ -761,9 +754,8 @@ static int ec_stripe_delete(struct btree_trans *trans, u64 idx)
 	struct bkey_s_c_stripe s;
 	int ret;
 
-	bch2_trans_iter_init(trans, &iter, BTREE_ID_stripes, POS(0, idx),
-			     BTREE_ITER_INTENT);
-	k = bch2_btree_iter_peek_slot(&iter);
+	k = bch2_bkey_get_iter(trans, &iter, BTREE_ID_stripes, POS(0, idx),
+			       BTREE_ITER_INTENT);
 	ret = bkey_err(k);
 	if (ret)
 		goto err;
@@ -841,9 +833,8 @@ static int ec_stripe_key_update(struct btree_trans *trans,
 	struct bkey_s_c k;
 	int ret;
 
-	bch2_trans_iter_init(trans, &iter, BTREE_ID_stripes,
-			     new->k.p, BTREE_ITER_INTENT);
-	k = bch2_btree_iter_peek_slot(&iter);
+	k = bch2_bkey_get_iter(trans, &iter, BTREE_ID_stripes,
+			       new->k.p, BTREE_ITER_INTENT);
 	ret = bkey_err(k);
 	if (ret)
 		goto err;
diff --git a/libbcachefs/ec.h b/libbcachefs/ec.h
index 7c08a49d..3995b707 100644
--- a/libbcachefs/ec.h
+++ b/libbcachefs/ec.h
@@ -17,6 +17,7 @@ void bch2_stripe_to_text(struct printbuf *, struct bch_fs *,
 	.swab		= bch2_ptr_swab,		\
 	.trans_trigger	= bch2_trans_mark_stripe,	\
 	.atomic_trigger	= bch2_mark_stripe,		\
+	.min_val_size	= 8,				\
 })
 
 static inline unsigned stripe_csums_per_device(const struct bch_stripe *s)
diff --git a/libbcachefs/errcode.h b/libbcachefs/errcode.h
index 4304e25a..c8ac08e5 100644
--- a/libbcachefs/errcode.h
+++ b/libbcachefs/errcode.h
@@ -92,6 +92,8 @@
 	x(ENOSPC,			ENOSPC_sb_replicas)			\
 	x(ENOSPC,			ENOSPC_sb_members)			\
 	x(ENOSPC,			ENOSPC_sb_crypt)			\
+	x(ENOSPC,			ENOSPC_btree_slot)			\
+	x(ENOSPC,			ENOSPC_snapshot_tree)			\
 	x(0,				open_buckets_empty)			\
 	x(0,				freelist_empty)				\
 	x(BCH_ERR_freelist_empty,	no_buckets_found)			\
diff --git a/libbcachefs/extents.c b/libbcachefs/extents.c
index b35b5841..e2b126ad 100644
--- a/libbcachefs/extents.c
+++ b/libbcachefs/extents.c
@@ -22,10 +22,9 @@
 #include "replicas.h"
 #include "super.h"
 #include "super-io.h"
+#include "trace.h"
 #include "util.h"
 
-#include <trace/events/bcachefs.h>
-
 static unsigned bch2_crc_field_size_max[] = {
 	[BCH_EXTENT_ENTRY_crc32] = CRC32_SIZE_MAX,
 	[BCH_EXTENT_ENTRY_crc64] = CRC64_SIZE_MAX,
@@ -184,27 +183,12 @@ void bch2_btree_ptr_to_text(struct printbuf *out, struct bch_fs *c,
 int bch2_btree_ptr_v2_invalid(const struct bch_fs *c, struct bkey_s_c k,
 			      unsigned flags, struct printbuf *err)
 {
-	struct bkey_s_c_btree_ptr_v2 bp = bkey_s_c_to_btree_ptr_v2(k);
-
-	if (bkey_val_bytes(k.k) <= sizeof(*bp.v)) {
-		prt_printf(err, "value too small (%zu <= %zu)",
-		       bkey_val_bytes(k.k), sizeof(*bp.v));
-		return -BCH_ERR_invalid_bkey;
-	}
-
 	if (bkey_val_u64s(k.k) > BKEY_BTREE_PTR_VAL_U64s_MAX) {
 		prt_printf(err, "value too big (%zu > %zu)",
 		       bkey_val_u64s(k.k), BKEY_BTREE_PTR_VAL_U64s_MAX);
 		return -BCH_ERR_invalid_bkey;
 	}
 
-	if (c->sb.version < bcachefs_metadata_version_snapshot &&
-	    bp.v->min_key.snapshot) {
-		prt_printf(err, "invalid min_key.snapshot (%u != 0)",
-		       bp.v->min_key.snapshot);
-		return -BCH_ERR_invalid_bkey;
-	}
-
 	return bch2_bkey_ptrs_invalid(c, k, flags, err);
 }
 
@@ -391,12 +375,6 @@ int bch2_reservation_invalid(const struct bch_fs *c, struct bkey_s_c k,
 {
 	struct bkey_s_c_reservation r = bkey_s_c_to_reservation(k);
 
-	if (bkey_val_bytes(k.k) != sizeof(struct bch_reservation)) {
-		prt_printf(err, "incorrect value size (%zu != %zu)",
-		       bkey_val_bytes(k.k), sizeof(*r.v));
-		return -BCH_ERR_invalid_bkey;
-	}
-
 	if (!r.v->nr_replicas || r.v->nr_replicas > BCH_REPLICAS_MAX) {
 		prt_printf(err, "invalid nr_replicas (%u)",
 		       r.v->nr_replicas);
diff --git a/libbcachefs/extents.h b/libbcachefs/extents.h
index 9b026ae9..31c81409 100644
--- a/libbcachefs/extents.h
+++ b/libbcachefs/extents.h
@@ -407,6 +407,7 @@ void bch2_btree_ptr_v2_compat(enum btree_id, unsigned, unsigned,
 	.compat		= bch2_btree_ptr_v2_compat,		\
 	.trans_trigger	= bch2_trans_mark_extent,		\
 	.atomic_trigger	= bch2_mark_extent,			\
+	.min_val_size	= 40,					\
 })
 
 /* KEY_TYPE_extent: */
@@ -436,6 +437,7 @@ bool bch2_reservation_merge(struct bch_fs *, struct bkey_s, struct bkey_s_c);
 	.key_merge	= bch2_reservation_merge,		\
 	.trans_trigger	= bch2_trans_mark_reservation,		\
 	.atomic_trigger	= bch2_mark_reservation,		\
+	.min_val_size	= 8,					\
 })
 
 /* Extent checksum entries: */
diff --git a/libbcachefs/fs-io.c b/libbcachefs/fs-io.c
index 43c39c62..3e104bf0 100644
--- a/libbcachefs/fs-io.c
+++ b/libbcachefs/fs-io.c
@@ -19,6 +19,7 @@
 #include "keylist.h"
 #include "quota.h"
 #include "reflink.h"
+#include "trace.h"
 
 #include <linux/aio.h>
 #include <linux/backing-dev.h>
@@ -32,7 +33,6 @@
 #include <linux/uio.h>
 #include <linux/writeback.h>
 
-#include <trace/events/bcachefs.h>
 #include <trace/events/writeback.h>
 
 /*
@@ -290,6 +290,9 @@ static int bch2_quota_reservation_add(struct bch_fs *c,
 {
 	int ret;
 
+	if (test_bit(EI_INODE_SNAPSHOT, &inode->ei_flags))
+		return 0;
+
 	mutex_lock(&inode->ei_quota_lock);
 	ret = bch2_quota_acct(c, inode->ei_qid, Q_SPC, sectors,
 			      check_enospc ? KEY_TYPE_QUOTA_PREALLOC : KEY_TYPE_QUOTA_NOCHECK);
@@ -371,7 +374,9 @@ static void __i_sectors_acct(struct bch_fs *c, struct bch_inode_info *inode,
 	inode->v.i_blocks += sectors;
 
 #ifdef CONFIG_BCACHEFS_QUOTA
-	if (quota_res && sectors > 0) {
+	if (quota_res &&
+	    !test_bit(EI_INODE_SNAPSHOT, &inode->ei_flags) &&
+	    sectors > 0) {
 		BUG_ON(sectors > quota_res->sectors);
 		BUG_ON(sectors > inode->ei_quota_reserved);
 
@@ -1512,11 +1517,10 @@ static void bch2_writepage_io_alloc(struct bch_fs *c,
 	op->wbio.bio.bi_opf	= wbc_to_write_flags(wbc);
 }
 
-static int __bch2_writepage(struct page *_page,
+static int __bch2_writepage(struct folio *folio,
 			    struct writeback_control *wbc,
 			    void *data)
 {
-	struct folio *folio = page_folio(_page);
 	struct bch_inode_info *inode = to_bch_ei(folio->mapping->host);
 	struct bch_fs *c = inode->v.i_sb->s_fs_info;
 	struct bch_writepage_state *w = data;
@@ -2912,7 +2916,7 @@ static int bch2_truncate_folios(struct bch_inode_info *inode,
 	return ret;
 }
 
-static int bch2_extend(struct user_namespace *mnt_userns,
+static int bch2_extend(struct mnt_idmap *idmap,
 		       struct bch_inode_info *inode,
 		       struct bch_inode_unpacked *inode_u,
 		       struct iattr *iattr)
@@ -2931,7 +2935,7 @@ static int bch2_extend(struct user_namespace *mnt_userns,
 
 	truncate_setsize(&inode->v, iattr->ia_size);
 
-	return bch2_setattr_nonsize(mnt_userns, inode, iattr);
+	return bch2_setattr_nonsize(idmap, inode, iattr);
 }
 
 static int bch2_truncate_finish_fn(struct bch_inode_info *inode,
@@ -2952,7 +2956,7 @@ static int bch2_truncate_start_fn(struct bch_inode_info *inode,
 	return 0;
 }
 
-int bch2_truncate(struct user_namespace *mnt_userns,
+int bch2_truncate(struct mnt_idmap *idmap,
 		  struct bch_inode_info *inode, struct iattr *iattr)
 {
 	struct bch_fs *c = inode->v.i_sb->s_fs_info;
@@ -2997,7 +3001,7 @@ int bch2_truncate(struct user_namespace *mnt_userns,
 		  (u64) inode->v.i_size, inode_u.bi_size);
 
 	if (iattr->ia_size > inode->v.i_size) {
-		ret = bch2_extend(mnt_userns, inode, &inode_u, iattr);
+		ret = bch2_extend(idmap, inode, &inode_u, iattr);
 		goto err;
 	}
 
@@ -3055,7 +3059,7 @@ int bch2_truncate(struct user_namespace *mnt_userns,
 	ret = bch2_write_inode(c, inode, bch2_truncate_finish_fn, NULL, 0);
 	mutex_unlock(&inode->ei_update_lock);
 
-	ret = bch2_setattr_nonsize(mnt_userns, inode, iattr);
+	ret = bch2_setattr_nonsize(idmap, inode, iattr);
 err:
 	bch2_pagecache_block_put(inode);
 	return bch2_err_class(ret);
diff --git a/libbcachefs/fs-io.h b/libbcachefs/fs-io.h
index a8835298..af905331 100644
--- a/libbcachefs/fs-io.h
+++ b/libbcachefs/fs-io.h
@@ -30,7 +30,7 @@ ssize_t bch2_write_iter(struct kiocb *, struct iov_iter *);
 
 int bch2_fsync(struct file *, loff_t, loff_t, int);
 
-int bch2_truncate(struct user_namespace *,
+int bch2_truncate(struct mnt_idmap *,
 		  struct bch_inode_info *, struct iattr *);
 long bch2_fallocate_dispatch(struct file *, int, loff_t, loff_t);
 
diff --git a/libbcachefs/fs-ioctl.c b/libbcachefs/fs-ioctl.c
index 571b4dca..269af939 100644
--- a/libbcachefs/fs-ioctl.c
+++ b/libbcachefs/fs-ioctl.c
@@ -93,7 +93,7 @@ static int bch2_ioc_setflags(struct bch_fs *c,
 		return ret;
 
 	inode_lock(&inode->v);
-	if (!inode_owner_or_capable(file_mnt_user_ns(file), &inode->v)) {
+	if (!inode_owner_or_capable(file_mnt_idmap(file), &inode->v)) {
 		ret = -EACCES;
 		goto setflags_out;
 	}
@@ -172,7 +172,7 @@ static int bch2_ioc_fssetxattr(struct bch_fs *c,
 		return ret;
 
 	inode_lock(&inode->v);
-	if (!inode_owner_or_capable(file_mnt_user_ns(file), &inode->v)) {
+	if (!inode_owner_or_capable(file_mnt_idmap(file), &inode->v)) {
 		ret = -EACCES;
 		goto err;
 	}
@@ -393,7 +393,7 @@ retry:
 		goto err3;
 	}
 
-	error = inode_permission(file_mnt_user_ns(filp),
+	error = inode_permission(file_mnt_idmap(filp),
 				 dir, MAY_WRITE | MAY_EXEC);
 	if (error)
 		goto err3;
@@ -409,7 +409,7 @@ retry:
 	    !arg.src_ptr)
 		snapshot_src.subvol = to_bch_ei(dir)->ei_inode.bi_subvol;
 
-	inode = __bch2_create(file_mnt_user_ns(filp), to_bch_ei(dir),
+	inode = __bch2_create(file_mnt_idmap(filp), to_bch_ei(dir),
 			      dst_dentry, arg.mode|S_IFDIR,
 			      0, snapshot_src, create_flags);
 	error = PTR_ERR_OR_ZERO(inode);
diff --git a/libbcachefs/fs.c b/libbcachefs/fs.c
index 6dbbc6ff..56091ce8 100644
--- a/libbcachefs/fs.c
+++ b/libbcachefs/fs.c
@@ -216,7 +216,7 @@ struct inode *bch2_vfs_inode_get(struct bch_fs *c, subvol_inum inum)
 }
 
 struct bch_inode_info *
-__bch2_create(struct user_namespace *mnt_userns,
+__bch2_create(struct mnt_idmap *idmap,
 	      struct bch_inode_info *dir, struct dentry *dentry,
 	      umode_t mode, dev_t rdev, subvol_inum snapshot_src,
 	      unsigned flags)
@@ -262,8 +262,8 @@ retry:
 				  inode_inum(dir), &dir_u, &inode_u,
 				  !(flags & BCH_CREATE_TMPFILE)
 				  ? &dentry->d_name : NULL,
-				  from_kuid(mnt_userns, current_fsuid()),
-				  from_kgid(mnt_userns, current_fsgid()),
+				  from_kuid(i_user_ns(&dir->v), current_fsuid()),
+				  from_kgid(i_user_ns(&dir->v), current_fsgid()),
 				  mode, rdev,
 				  default_acl, acl, snapshot_src, flags) ?:
 		bch2_quota_acct(c, bch_qid(&inode_u), Q_INO, 1,
@@ -370,12 +370,12 @@ static struct dentry *bch2_lookup(struct inode *vdir, struct dentry *dentry,
 	return d_splice_alias(vinode, dentry);
 }
 
-static int bch2_mknod(struct user_namespace *mnt_userns,
+static int bch2_mknod(struct mnt_idmap *idmap,
 		      struct inode *vdir, struct dentry *dentry,
 		      umode_t mode, dev_t rdev)
 {
 	struct bch_inode_info *inode =
-		__bch2_create(mnt_userns, to_bch_ei(vdir), dentry, mode, rdev,
+		__bch2_create(idmap, to_bch_ei(vdir), dentry, mode, rdev,
 			      (subvol_inum) { 0 }, 0);
 
 	if (IS_ERR(inode))
@@ -385,11 +385,11 @@ static int bch2_mknod(struct user_namespace *mnt_userns,
 	return 0;
 }
 
-static int bch2_create(struct user_namespace *mnt_userns,
+static int bch2_create(struct mnt_idmap *idmap,
 		       struct inode *vdir, struct dentry *dentry,
 		       umode_t mode, bool excl)
 {
-	return bch2_mknod(mnt_userns, vdir, dentry, mode|S_IFREG, 0);
+	return bch2_mknod(idmap, vdir, dentry, mode|S_IFREG, 0);
 }
 
 static int __bch2_link(struct bch_fs *c,
@@ -486,7 +486,7 @@ static int bch2_unlink(struct inode *vdir, struct dentry *dentry)
 	return __bch2_unlink(vdir, dentry, false);
 }
 
-static int bch2_symlink(struct user_namespace *mnt_userns,
+static int bch2_symlink(struct mnt_idmap *idmap,
 			struct inode *vdir, struct dentry *dentry,
 			const char *symname)
 {
@@ -494,7 +494,7 @@ static int bch2_symlink(struct user_namespace *mnt_userns,
 	struct bch_inode_info *dir = to_bch_ei(vdir), *inode;
 	int ret;
 
-	inode = __bch2_create(mnt_userns, dir, dentry, S_IFLNK|S_IRWXUGO, 0,
+	inode = __bch2_create(idmap, dir, dentry, S_IFLNK|S_IRWXUGO, 0,
 			      (subvol_inum) { 0 }, BCH_CREATE_TMPFILE);
 	if (IS_ERR(inode))
 		return bch2_err_class(PTR_ERR(inode));
@@ -521,13 +521,13 @@ err:
 	return ret;
 }
 
-static int bch2_mkdir(struct user_namespace *mnt_userns,
+static int bch2_mkdir(struct mnt_idmap *idmap,
 		      struct inode *vdir, struct dentry *dentry, umode_t mode)
 {
-	return bch2_mknod(mnt_userns, vdir, dentry, mode|S_IFDIR, 0);
+	return bch2_mknod(idmap, vdir, dentry, mode|S_IFDIR, 0);
 }
 
-static int bch2_rename2(struct user_namespace *mnt_userns,
+static int bch2_rename2(struct mnt_idmap *idmap,
 			struct inode *src_vdir, struct dentry *src_dentry,
 			struct inode *dst_vdir, struct dentry *dst_dentry,
 			unsigned flags)
@@ -634,7 +634,7 @@ err:
 	return ret;
 }
 
-static void bch2_setattr_copy(struct user_namespace *mnt_userns,
+static void bch2_setattr_copy(struct mnt_idmap *idmap,
 			      struct bch_inode_info *inode,
 			      struct bch_inode_unpacked *bi,
 			      struct iattr *attr)
@@ -643,9 +643,9 @@ static void bch2_setattr_copy(struct user_namespace *mnt_userns,
 	unsigned int ia_valid = attr->ia_valid;
 
 	if (ia_valid & ATTR_UID)
-		bi->bi_uid = from_kuid(mnt_userns, attr->ia_uid);
+		bi->bi_uid = from_kuid(i_user_ns(&inode->v), attr->ia_uid);
 	if (ia_valid & ATTR_GID)
-		bi->bi_gid = from_kgid(mnt_userns, attr->ia_gid);
+		bi->bi_gid = from_kgid(i_user_ns(&inode->v), attr->ia_gid);
 
 	if (ia_valid & ATTR_SIZE)
 		bi->bi_size = attr->ia_size;
@@ -664,13 +664,13 @@ static void bch2_setattr_copy(struct user_namespace *mnt_userns,
 			: inode->v.i_gid;
 
 		if (!in_group_p(gid) &&
-		    !capable_wrt_inode_uidgid(mnt_userns, &inode->v, CAP_FSETID))
+		    !capable_wrt_inode_uidgid(idmap, &inode->v, CAP_FSETID))
 			mode &= ~S_ISGID;
 		bi->bi_mode = mode;
 	}
 }
 
-int bch2_setattr_nonsize(struct user_namespace *mnt_userns,
+int bch2_setattr_nonsize(struct mnt_idmap *idmap,
 			 struct bch_inode_info *inode,
 			 struct iattr *attr)
 {
@@ -687,10 +687,10 @@ int bch2_setattr_nonsize(struct user_namespace *mnt_userns,
 	qid = inode->ei_qid;
 
 	if (attr->ia_valid & ATTR_UID)
-		qid.q[QTYP_USR] = from_kuid(mnt_userns, attr->ia_uid);
+		qid.q[QTYP_USR] = from_kuid(i_user_ns(&inode->v), attr->ia_uid);
 
 	if (attr->ia_valid & ATTR_GID)
-		qid.q[QTYP_GRP] = from_kgid(mnt_userns, attr->ia_gid);
+		qid.q[QTYP_GRP] = from_kgid(i_user_ns(&inode->v), attr->ia_gid);
 
 	ret = bch2_fs_quota_transfer(c, inode, qid, ~0,
 				     KEY_TYPE_QUOTA_PREALLOC);
@@ -708,7 +708,7 @@ retry:
 	if (ret)
 		goto btree_err;
 
-	bch2_setattr_copy(mnt_userns, inode, &inode_u, attr);
+	bch2_setattr_copy(idmap, inode, &inode_u, attr);
 
 	if (attr->ia_valid & ATTR_MODE) {
 		ret = bch2_acl_chmod(&trans, inode_inum(inode), &inode_u,
@@ -740,7 +740,7 @@ err:
 	return bch2_err_class(ret);
 }
 
-static int bch2_getattr(struct user_namespace *mnt_userns,
+static int bch2_getattr(struct mnt_idmap *idmap,
 			const struct path *path, struct kstat *stat,
 			u32 request_mask, unsigned query_flags)
 {
@@ -781,7 +781,7 @@ static int bch2_getattr(struct user_namespace *mnt_userns,
 	return 0;
 }
 
-static int bch2_setattr(struct user_namespace *mnt_userns,
+static int bch2_setattr(struct mnt_idmap *idmap,
 			struct dentry *dentry, struct iattr *iattr)
 {
 	struct bch_inode_info *inode = to_bch_ei(dentry->d_inode);
@@ -789,20 +789,20 @@ static int bch2_setattr(struct user_namespace *mnt_userns,
 
 	lockdep_assert_held(&inode->v.i_rwsem);
 
-	ret = setattr_prepare(mnt_userns, dentry, iattr);
+	ret = setattr_prepare(idmap, dentry, iattr);
 	if (ret)
 		return ret;
 
 	return iattr->ia_valid & ATTR_SIZE
-		? bch2_truncate(mnt_userns, inode, iattr)
-		: bch2_setattr_nonsize(mnt_userns, inode, iattr);
+		? bch2_truncate(idmap, inode, iattr)
+		: bch2_setattr_nonsize(idmap, inode, iattr);
 }
 
-static int bch2_tmpfile(struct user_namespace *mnt_userns,
+static int bch2_tmpfile(struct mnt_idmap *idmap,
 			struct inode *vdir, struct file *file, umode_t mode)
 {
 	struct bch_inode_info *inode =
-		__bch2_create(mnt_userns, to_bch_ei(vdir),
+		__bch2_create(idmap, to_bch_ei(vdir),
 			      file->f_path.dentry, mode, 0,
 			      (subvol_inum) { 0 }, BCH_CREATE_TMPFILE);
 
diff --git a/libbcachefs/fs.h b/libbcachefs/fs.h
index cf041353..2e63cb66 100644
--- a/libbcachefs/fs.h
+++ b/libbcachefs/fs.h
@@ -149,7 +149,7 @@ struct bch_inode_unpacked;
 #ifndef NO_BCACHEFS_FS
 
 struct bch_inode_info *
-__bch2_create(struct user_namespace *, struct bch_inode_info *,
+__bch2_create(struct mnt_idmap *, struct bch_inode_info *,
 	      struct dentry *, umode_t, dev_t, subvol_inum, unsigned);
 
 int bch2_fs_quota_transfer(struct bch_fs *,
@@ -184,7 +184,7 @@ void bch2_inode_update_after_write(struct btree_trans *,
 int __must_check bch2_write_inode(struct bch_fs *, struct bch_inode_info *,
 				  inode_set_fn, void *, unsigned);
 
-int bch2_setattr_nonsize(struct user_namespace *,
+int bch2_setattr_nonsize(struct mnt_idmap *,
 			 struct bch_inode_info *,
 			 struct iattr *);
 int __bch2_unlink(struct inode *, struct dentry *, bool);
diff --git a/libbcachefs/fsck.c b/libbcachefs/fsck.c
index 4e710057..eb3609aa 100644
--- a/libbcachefs/fsck.c
+++ b/libbcachefs/fsck.c
@@ -72,26 +72,14 @@ static s64 bch2_count_subdirs(struct btree_trans *trans, u64 inum,
 static int __snapshot_lookup_subvol(struct btree_trans *trans, u32 snapshot,
 				    u32 *subvol)
 {
-	struct btree_iter iter;
-	struct bkey_s_c k;
-	int ret;
-
-	bch2_trans_iter_init(trans, &iter, BTREE_ID_snapshots,
-			     POS(0, snapshot), 0);
-	k = bch2_btree_iter_peek_slot(&iter);
-	ret = bkey_err(k);
-	if (ret)
-		goto err;
-
-	if (k.k->type != KEY_TYPE_snapshot) {
+	struct bch_snapshot s;
+	int ret = bch2_bkey_get_val_typed(trans, BTREE_ID_snapshots,
+					  POS(0, snapshot), 0,
+					  snapshot, &s);
+	if (!ret)
+		*subvol = le32_to_cpu(s.subvol);
+	else if (ret == -ENOENT)
 		bch_err(trans->c, "snapshot %u not fonud", snapshot);
-		ret = -ENOENT;
-		goto err;
-	}
-
-	*subvol = le32_to_cpu(bkey_s_c_to_snapshot(k).v->subvol);
-err:
-	bch2_trans_iter_exit(trans, &iter);
 	return ret;
 
 }
@@ -152,9 +140,8 @@ static int __lookup_inode(struct btree_trans *trans, u64 inode_nr,
 	struct bkey_s_c k;
 	int ret;
 
-	bch2_trans_iter_init(trans, &iter, BTREE_ID_inodes,
-			     SPOS(0, inode_nr, *snapshot), 0);
-	k = bch2_btree_iter_peek_slot(&iter);
+	k = bch2_bkey_get_iter(trans, &iter, BTREE_ID_inodes,
+			       SPOS(0, inode_nr, *snapshot), 0);
 	ret = bkey_err(k);
 	if (ret)
 		goto err;
@@ -259,10 +246,8 @@ static int fsck_inode_rm(struct btree_trans *trans, u64 inum, u32 snapshot)
 retry:
 	bch2_trans_begin(trans);
 
-	bch2_trans_iter_init(trans, &iter, BTREE_ID_inodes,
-			     SPOS(0, inum, snapshot), BTREE_ITER_INTENT);
-	k = bch2_btree_iter_peek_slot(&iter);
-
+	k = bch2_bkey_get_iter(trans, &iter, BTREE_ID_inodes,
+			       SPOS(0, inum, snapshot), BTREE_ITER_INTENT);
 	ret = bkey_err(k);
 	if (ret)
 		goto err;
@@ -453,22 +438,14 @@ static int remove_backpointer(struct btree_trans *trans,
 			      struct bch_inode_unpacked *inode)
 {
 	struct btree_iter iter;
-	struct bkey_s_c k;
+	struct bkey_s_c_dirent d;
 	int ret;
 
-	bch2_trans_iter_init(trans, &iter, BTREE_ID_dirents,
-			     POS(inode->bi_dir, inode->bi_dir_offset), 0);
-	k = bch2_btree_iter_peek_slot(&iter);
-	ret = bkey_err(k);
-	if (ret)
-		goto out;
-	if (k.k->type != KEY_TYPE_dirent) {
-		ret = -ENOENT;
-		goto out;
-	}
-
-	ret = __remove_dirent(trans, k.k->p);
-out:
+	d = bch2_bkey_get_iter_typed(trans, &iter, BTREE_ID_dirents,
+				     POS(inode->bi_dir, inode->bi_dir_offset), 0,
+				     dirent);
+	ret =   bkey_err(d) ?:
+		__remove_dirent(trans, d.k->p);
 	bch2_trans_iter_exit(trans, &iter);
 	return ret;
 }
@@ -788,7 +765,7 @@ static int hash_redo_key(struct btree_trans *trans,
 	if (IS_ERR(delete))
 		return PTR_ERR(delete);
 
-	tmp = bch2_bkey_make_mut(trans, k);
+	tmp = bch2_bkey_make_mut_noupdate(trans, k);
 	if (IS_ERR(tmp))
 		return PTR_ERR(tmp);
 
@@ -1081,20 +1058,7 @@ static struct bkey_s_c_dirent dirent_get_by_pos(struct btree_trans *trans,
 						struct btree_iter *iter,
 						struct bpos pos)
 {
-	struct bkey_s_c k;
-	int ret;
-
-	bch2_trans_iter_init(trans, iter, BTREE_ID_dirents, pos, 0);
-	k = bch2_btree_iter_peek_slot(iter);
-	ret = bkey_err(k);
-	if (!ret && k.k->type != KEY_TYPE_dirent)
-		ret = -ENOENT;
-	if (ret) {
-		bch2_trans_iter_exit(trans, iter);
-		return (struct bkey_s_c_dirent) { .k = ERR_PTR(ret) };
-	}
-
-	return bkey_s_c_to_dirent(k);
+	return bch2_bkey_get_iter_typed(trans, iter, BTREE_ID_dirents, pos, 0, dirent);
 }
 
 static bool inode_points_to_dirent(struct bch_inode_unpacked *inode,
@@ -1122,7 +1086,7 @@ static int inode_backpointer_exists(struct btree_trans *trans,
 
 	d = dirent_get_by_pos(trans, &iter,
 			SPOS(inode->bi_dir, inode->bi_dir_offset, snapshot));
-	ret = bkey_err(d.s_c);
+	ret = bkey_err(d);
 	if (ret)
 		return ret == -ENOENT ? 0 : ret;
 
@@ -2463,7 +2427,8 @@ int bch2_fsck_full(struct bch_fs *c)
 {
 	int ret;
 again:
-	ret =   bch2_fs_check_snapshots(c) ?:
+	ret =   bch2_fs_check_snapshot_trees(c);
+		bch2_fs_check_snapshots(c) ?:
 		bch2_fs_check_subvols(c) ?:
 		bch2_delete_dead_snapshots(c) ?:
 		check_inodes(c, true) ?:
diff --git a/libbcachefs/inode.c b/libbcachefs/inode.c
index 7ccbc00b..ddcd7b12 100644
--- a/libbcachefs/inode.c
+++ b/libbcachefs/inode.c
@@ -329,13 +329,12 @@ int bch2_inode_peek(struct btree_trans *trans,
 	if (ret)
 		return ret;
 
-	bch2_trans_iter_init(trans, iter, BTREE_ID_inodes,
-			     SPOS(0, inum.inum, snapshot),
-			     flags|BTREE_ITER_CACHED);
-	k = bch2_btree_iter_peek_slot(iter);
+	k = bch2_bkey_get_iter(trans, iter, BTREE_ID_inodes,
+			       SPOS(0, inum.inum, snapshot),
+			       flags|BTREE_ITER_CACHED);
 	ret = bkey_err(k);
 	if (ret)
-		goto err;
+		return ret;
 
 	ret = bkey_is_inode(k.k) ? 0 : -ENOENT;
 	if (ret)
@@ -437,12 +436,6 @@ int bch2_inode_invalid(const struct bch_fs *c, struct bkey_s_c k,
 {
 	struct bkey_s_c_inode inode = bkey_s_c_to_inode(k);
 
-	if (bkey_val_bytes(k.k) < sizeof(*inode.v)) {
-		prt_printf(err, "incorrect value size (%zu < %zu)",
-		       bkey_val_bytes(k.k), sizeof(*inode.v));
-		return -BCH_ERR_invalid_bkey;
-	}
-
 	if (INODE_STR_HASH(inode.v) >= BCH_STR_HASH_NR) {
 		prt_printf(err, "invalid str hash type (%llu >= %u)",
 		       INODE_STR_HASH(inode.v), BCH_STR_HASH_NR);
@@ -457,12 +450,6 @@ int bch2_inode_v2_invalid(const struct bch_fs *c, struct bkey_s_c k,
 {
 	struct bkey_s_c_inode_v2 inode = bkey_s_c_to_inode_v2(k);
 
-	if (bkey_val_bytes(k.k) < sizeof(*inode.v)) {
-		prt_printf(err, "incorrect value size (%zu < %zu)",
-		       bkey_val_bytes(k.k), sizeof(*inode.v));
-		return -BCH_ERR_invalid_bkey;
-	}
-
 	if (INODEv2_STR_HASH(inode.v) >= BCH_STR_HASH_NR) {
 		prt_printf(err, "invalid str hash type (%llu >= %u)",
 		       INODEv2_STR_HASH(inode.v), BCH_STR_HASH_NR);
@@ -477,12 +464,6 @@ int bch2_inode_v3_invalid(const struct bch_fs *c, struct bkey_s_c k,
 {
 	struct bkey_s_c_inode_v3 inode = bkey_s_c_to_inode_v3(k);
 
-	if (bkey_val_bytes(k.k) < sizeof(*inode.v)) {
-		prt_printf(err, "incorrect value size (%zu < %zu)",
-		       bkey_val_bytes(k.k), sizeof(*inode.v));
-		return -BCH_ERR_invalid_bkey;
-	}
-
 	if (INODEv3_FIELDS_START(inode.v) < INODEv3_FIELDS_START_INITIAL ||
 	    INODEv3_FIELDS_START(inode.v) > bkey_val_u64s(inode.k)) {
 		prt_printf(err, "invalid fields_start (got %llu, min %u max %zu)",
@@ -543,12 +524,6 @@ int bch2_inode_generation_invalid(const struct bch_fs *c, struct bkey_s_c k,
 		return -BCH_ERR_invalid_bkey;
 	}
 
-	if (bkey_val_bytes(k.k) != sizeof(struct bch_inode_generation)) {
-		prt_printf(err, "incorrect value size (%zu != %zu)",
-		       bkey_val_bytes(k.k), sizeof(struct bch_inode_generation));
-		return -BCH_ERR_invalid_bkey;
-	}
-
 	return 0;
 }
 
@@ -784,11 +759,9 @@ retry:
 	if (ret)
 		goto err;
 
-	bch2_trans_iter_init(&trans, &iter, BTREE_ID_inodes,
-			     SPOS(0, inum.inum, snapshot),
-			     BTREE_ITER_INTENT|BTREE_ITER_CACHED);
-	k = bch2_btree_iter_peek_slot(&iter);
-
+	k = bch2_bkey_get_iter(&trans, &iter, BTREE_ID_inodes,
+			       SPOS(0, inum.inum, snapshot),
+			       BTREE_ITER_INTENT|BTREE_ITER_CACHED);
 	ret = bkey_err(k);
 	if (ret)
 		goto err;
diff --git a/libbcachefs/inode.h b/libbcachefs/inode.h
index f5066afb..0c3022d3 100644
--- a/libbcachefs/inode.h
+++ b/libbcachefs/inode.h
@@ -17,6 +17,7 @@ void bch2_inode_to_text(struct printbuf *, struct bch_fs *, struct bkey_s_c);
 	.val_to_text	= bch2_inode_to_text,		\
 	.trans_trigger	= bch2_trans_mark_inode,	\
 	.atomic_trigger	= bch2_mark_inode,		\
+	.min_val_size	= 16,				\
 })
 
 #define bch2_bkey_ops_inode_v2 ((struct bkey_ops) {	\
@@ -24,6 +25,7 @@ void bch2_inode_to_text(struct printbuf *, struct bch_fs *, struct bkey_s_c);
 	.val_to_text	= bch2_inode_to_text,		\
 	.trans_trigger	= bch2_trans_mark_inode,	\
 	.atomic_trigger	= bch2_mark_inode,		\
+	.min_val_size	= 32,				\
 })
 
 #define bch2_bkey_ops_inode_v3 ((struct bkey_ops) {	\
@@ -31,6 +33,7 @@ void bch2_inode_to_text(struct printbuf *, struct bch_fs *, struct bkey_s_c);
 	.val_to_text	= bch2_inode_to_text,		\
 	.trans_trigger	= bch2_trans_mark_inode,	\
 	.atomic_trigger	= bch2_mark_inode,		\
+	.min_val_size	= 48,				\
 })
 
 static inline bool bkey_is_inode(const struct bkey *k)
@@ -47,6 +50,7 @@ void bch2_inode_generation_to_text(struct printbuf *, struct bch_fs *, struct bk
 #define bch2_bkey_ops_inode_generation ((struct bkey_ops) {	\
 	.key_invalid	= bch2_inode_generation_invalid,	\
 	.val_to_text	= bch2_inode_generation_to_text,	\
+	.min_val_size	= 8,					\
 })
 
 #if 0
diff --git a/libbcachefs/io.c b/libbcachefs/io.c
index c0371e23..5a04ee51 100644
--- a/libbcachefs/io.c
+++ b/libbcachefs/io.c
@@ -32,14 +32,13 @@
 #include "subvolume.h"
 #include "super.h"
 #include "super-io.h"
+#include "trace.h"
 
 #include <linux/blkdev.h>
 #include <linux/prefetch.h>
 #include <linux/random.h>
 #include <linux/sched/mm.h>
 
-#include <trace/events/bcachefs.h>
-
 const char *bch2_blk_status_to_str(blk_status_t status)
 {
 	if (status == BLK_STS_REMOVED)
@@ -258,15 +257,14 @@ static inline int bch2_extent_update_i_size_sectors(struct btree_trans *trans,
 	unsigned inode_update_flags = BTREE_UPDATE_NOJOURNAL;
 	int ret;
 
-	bch2_trans_iter_init(trans, &iter, BTREE_ID_inodes,
-			     SPOS(0,
-				  extent_iter->pos.inode,
-				  extent_iter->snapshot),
-			     BTREE_ITER_INTENT|BTREE_ITER_CACHED);
-	k = bch2_bkey_get_mut(trans, &iter);
+	k = bch2_bkey_get_mut_noupdate(trans, &iter, BTREE_ID_inodes,
+			      SPOS(0,
+				   extent_iter->pos.inode,
+				   extent_iter->snapshot),
+			      BTREE_ITER_CACHED);
 	ret = PTR_ERR_OR_ZERO(k);
 	if (unlikely(ret))
-		goto err;
+		return ret;
 
 	if (unlikely(k->k.type != KEY_TYPE_inode_v3)) {
 		k = bch2_inode_to_v3(trans, k);
@@ -1395,7 +1393,7 @@ static int bch2_nocow_write_convert_one_unwritten(struct btree_trans *trans,
 		return 0;
 	}
 
-	new = bch2_bkey_make_mut(trans, k);
+	new = bch2_bkey_make_mut_noupdate(trans, k);
 	ret = PTR_ERR_OR_ZERO(new);
 	if (ret)
 		return ret;
@@ -2313,9 +2311,8 @@ static int __bch2_rbio_narrow_crcs(struct btree_trans *trans,
 	if (crc_is_compressed(rbio->pick.crc))
 		return 0;
 
-	bch2_trans_iter_init(trans, &iter, rbio->data_btree, rbio->data_pos,
-			     BTREE_ITER_SLOTS|BTREE_ITER_INTENT);
-	k = bch2_btree_iter_peek_slot(&iter);
+	k = bch2_bkey_get_iter(trans, &iter, rbio->data_btree, rbio->data_pos,
+			       BTREE_ITER_SLOTS|BTREE_ITER_INTENT);
 	if ((ret = bkey_err(k)))
 		goto out;
 
@@ -2551,10 +2548,8 @@ int __bch2_read_indirect_extent(struct btree_trans *trans,
 	reflink_offset = le64_to_cpu(bkey_i_to_reflink_p(orig_k->k)->v.idx) +
 		*offset_into_extent;
 
-	bch2_trans_iter_init(trans, &iter, BTREE_ID_reflink,
-			     POS(0, reflink_offset),
-			     BTREE_ITER_SLOTS);
-	k = bch2_btree_iter_peek_slot(&iter);
+	k = bch2_bkey_get_iter(trans, &iter, BTREE_ID_reflink,
+			       POS(0, reflink_offset), 0);
 	ret = bkey_err(k);
 	if (ret)
 		goto err;
diff --git a/libbcachefs/io.h b/libbcachefs/io.h
index 90948bb0..87d80fb2 100644
--- a/libbcachefs/io.h
+++ b/libbcachefs/io.h
@@ -113,7 +113,7 @@ static inline struct bch_write_bio *wbio_init(struct bio *bio)
 {
 	struct bch_write_bio *wbio = to_wbio(bio);
 
-	memset(wbio, 0, offsetof(struct bch_write_bio, bio));
+	memset(&wbio->wbio, 0, sizeof(wbio->wbio));
 	return wbio;
 }
 
diff --git a/libbcachefs/io_types.h b/libbcachefs/io_types.h
index 3b2ed0fa..4149291c 100644
--- a/libbcachefs/io_types.h
+++ b/libbcachefs/io_types.h
@@ -83,6 +83,7 @@ struct bch_read_bio {
 };
 
 struct bch_write_bio {
+	struct_group(wbio,
 	struct bch_fs		*c;
 	struct bch_write_bio	*parent;
 
@@ -99,6 +100,7 @@ struct bch_write_bio {
 				nocow:1,
 				used_mempool:1,
 				first_btree_write:1;
+	);
 
 	struct bio		bio;
 };
diff --git a/libbcachefs/journal.c b/libbcachefs/journal.c
index 3f0e6d71..433c9784 100644
--- a/libbcachefs/journal.c
+++ b/libbcachefs/journal.c
@@ -17,8 +17,7 @@
 #include "journal_reclaim.h"
 #include "journal_sb.h"
 #include "journal_seq_blacklist.h"
-
-#include <trace/events/bcachefs.h>
+#include "trace.h"
 
 #define x(n)	#n,
 static const char * const bch2_journal_watermarks[] = {
diff --git a/libbcachefs/journal_io.c b/libbcachefs/journal_io.c
index 45b1b839..38458ab0 100644
--- a/libbcachefs/journal_io.c
+++ b/libbcachefs/journal_io.c
@@ -14,8 +14,7 @@
 #include "journal_reclaim.h"
 #include "journal_seq_blacklist.h"
 #include "replicas.h"
-
-#include <trace/events/bcachefs.h>
+#include "trace.h"
 
 static struct nonce journal_nonce(const struct jset *jset)
 {
diff --git a/libbcachefs/journal_reclaim.c b/libbcachefs/journal_reclaim.c
index 37c6846a..29d843e6 100644
--- a/libbcachefs/journal_reclaim.c
+++ b/libbcachefs/journal_reclaim.c
@@ -10,10 +10,10 @@
 #include "journal_reclaim.h"
 #include "replicas.h"
 #include "super.h"
+#include "trace.h"
 
 #include <linux/kthread.h>
 #include <linux/sched/mm.h>
-#include <trace/events/bcachefs.h>
 
 /* Free space calculations: */
 
diff --git a/libbcachefs/lru.c b/libbcachefs/lru.c
index c2dece27..4f23e88f 100644
--- a/libbcachefs/lru.c
+++ b/libbcachefs/lru.c
@@ -13,14 +13,6 @@
 int bch2_lru_invalid(const struct bch_fs *c, struct bkey_s_c k,
 		     unsigned flags, struct printbuf *err)
 {
-	const struct bch_lru *lru = bkey_s_c_to_lru(k).v;
-
-	if (bkey_val_bytes(k.k) < sizeof(*lru)) {
-		prt_printf(err, "incorrect value size (%zu < %zu)",
-		       bkey_val_bytes(k.k), sizeof(*lru));
-		return -BCH_ERR_invalid_bkey;
-	}
-
 	if (!lru_pos_time(k.k->p)) {
 		prt_printf(err, "lru entry at time=0");
 		return -BCH_ERR_invalid_bkey;
@@ -122,8 +114,7 @@ static int bch2_check_lru_key(struct btree_trans *trans,
 			alloc_pos.inode, alloc_pos.offset))
 		return bch2_btree_delete_at(trans, lru_iter, 0);
 
-	bch2_trans_iter_init(trans, &iter, BTREE_ID_alloc, alloc_pos, 0);
-	k = bch2_btree_iter_peek_slot(&iter);
+	k = bch2_bkey_get_iter(trans, &iter, BTREE_ID_alloc, alloc_pos, 0);
 	ret = bkey_err(k);
 	if (ret)
 		goto err;
diff --git a/libbcachefs/lru.h b/libbcachefs/lru.h
index 78a60769..adb98429 100644
--- a/libbcachefs/lru.h
+++ b/libbcachefs/lru.h
@@ -51,6 +51,7 @@ void bch2_lru_pos_to_text(struct printbuf *, struct bpos);
 #define bch2_bkey_ops_lru ((struct bkey_ops) {	\
 	.key_invalid	= bch2_lru_invalid,	\
 	.val_to_text	= bch2_lru_to_text,	\
+	.min_val_size	= 8,			\
 })
 
 int bch2_lru_del(struct btree_trans *, u16, u64, u64);
diff --git a/libbcachefs/migrate.c b/libbcachefs/migrate.c
index d93db07f..0898fa49 100644
--- a/libbcachefs/migrate.c
+++ b/libbcachefs/migrate.c
@@ -49,7 +49,7 @@ static int bch2_dev_usrdata_drop_key(struct btree_trans *trans,
 	if (!bch2_bkey_has_device_c(k, dev_idx))
 		return 0;
 
-	n = bch2_bkey_make_mut(trans, k);
+	n = bch2_bkey_make_mut(trans, iter, k, BTREE_UPDATE_INTERNAL_SNAPSHOT_NODE);
 	ret = PTR_ERR_OR_ZERO(n);
 	if (ret)
 		return ret;
@@ -73,8 +73,7 @@ static int bch2_dev_usrdata_drop_key(struct btree_trans *trans,
 	 */
 	if (bkey_deleted(&n->k))
 		n->k.size = 0;
-
-	return bch2_trans_update(trans, iter, n, BTREE_UPDATE_INTERNAL_SNAPSHOT_NODE);
+	return 0;
 }
 
 static int bch2_dev_usrdata_drop(struct bch_fs *c, unsigned dev_idx, int flags)
diff --git a/libbcachefs/move.c b/libbcachefs/move.c
index 200aa5dc..7e22176a 100644
--- a/libbcachefs/move.c
+++ b/libbcachefs/move.c
@@ -16,16 +16,15 @@
 #include "inode.h"
 #include "io.h"
 #include "journal_reclaim.h"
+#include "keylist.h"
 #include "move.h"
 #include "replicas.h"
 #include "super-io.h"
-#include "keylist.h"
+#include "trace.h"
 
 #include <linux/ioprio.h>
 #include <linux/kthread.h>
 
-#include <trace/events/bcachefs.h>
-
 static void trace_move_extent2(struct bch_fs *c, struct bkey_s_c k)
 {
 	if (trace_move_extent_enabled()) {
@@ -252,7 +251,7 @@ static int bch2_extent_drop_ptrs(struct btree_trans *trans,
 	struct bkey_i *n;
 	int ret;
 
-	n = bch2_bkey_make_mut(trans, k);
+	n = bch2_bkey_make_mut_noupdate(trans, k);
 	ret = PTR_ERR_OR_ZERO(n);
 	if (ret)
 		return ret;
@@ -676,7 +675,7 @@ int __bch2_evacuate_bucket(struct btree_trans *trans,
 	struct bpos bp_pos = POS_MIN;
 	int ret = 0;
 
-	trace_bucket_evacuate(c, bucket);
+	trace_bucket_evacuate(c, &bucket);
 
 	bch2_bkey_buf_init(&sk);
 
diff --git a/libbcachefs/movinggc.c b/libbcachefs/movinggc.c
index c0fc669c..0d96346d 100644
--- a/libbcachefs/movinggc.c
+++ b/libbcachefs/movinggc.c
@@ -24,8 +24,8 @@
 #include "move.h"
 #include "movinggc.h"
 #include "super-io.h"
+#include "trace.h"
 
-#include <trace/events/bcachefs.h>
 #include <linux/bsearch.h>
 #include <linux/freezer.h>
 #include <linux/kthread.h>
@@ -91,12 +91,9 @@ static int bch2_bucket_is_movable(struct btree_trans *trans,
 				b->k.bucket.offset))
 		return 0;
 
-	bch2_trans_iter_init(trans, &iter, BTREE_ID_alloc,
-			     b->k.bucket, BTREE_ITER_CACHED);
-	k = bch2_btree_iter_peek_slot(&iter);
+	k = bch2_bkey_get_iter(trans, &iter, BTREE_ID_alloc,
+			       b->k.bucket, BTREE_ITER_CACHED);
 	ret = bkey_err(k);
-	bch2_trans_iter_exit(trans, &iter);
-
 	if (ret)
 		return ret;
 
@@ -108,14 +105,7 @@ static int bch2_bucket_is_movable(struct btree_trans *trans,
 		a->fragmentation_lru &&
 		a->fragmentation_lru <= time;
 
-	if (!ret) {
-		struct printbuf buf = PRINTBUF;
-
-		bch2_bkey_val_to_text(&buf, trans->c, k);
-		pr_debug("%s", buf.buf);
-		printbuf_exit(&buf);
-	}
-
+	bch2_trans_iter_exit(trans, &iter);
 	return ret;
 }
 
@@ -205,6 +195,7 @@ static int bch2_copygc_get_buckets(struct btree_trans *trans,
 	return ret < 0 ? ret : 0;
 }
 
+noinline
 static int bch2_copygc(struct btree_trans *trans,
 		       struct moving_context *ctxt,
 		       struct buckets_in_flight *buckets_in_flight)
diff --git a/libbcachefs/quota.c b/libbcachefs/quota.c
index 331f2283..cc0db72c 100644
--- a/libbcachefs/quota.c
+++ b/libbcachefs/quota.c
@@ -67,12 +67,6 @@ int bch2_quota_invalid(const struct bch_fs *c, struct bkey_s_c k,
 		return -BCH_ERR_invalid_bkey;
 	}
 
-	if (bkey_val_bytes(k.k) != sizeof(struct bch_quota)) {
-		prt_printf(err, "incorrect value size (%zu != %zu)",
-		       bkey_val_bytes(k.k), sizeof(struct bch_quota));
-		return -BCH_ERR_invalid_bkey;
-	}
-
 	return 0;
 }
 
@@ -562,23 +556,22 @@ static int bch2_fs_quota_read_inode(struct btree_trans *trans,
 {
 	struct bch_fs *c = trans->c;
 	struct bch_inode_unpacked u;
-	struct bch_subvolume subvolume;
+	struct bch_snapshot_tree s_t;
 	int ret;
 
-	ret = bch2_snapshot_get_subvol(trans, k.k->p.snapshot, &subvolume);
+	ret = bch2_snapshot_tree_lookup(trans,
+			snapshot_t(c, k.k->p.snapshot)->tree, &s_t);
 	if (ret)
 		return ret;
 
-	/*
-	 * We don't do quota accounting in snapshots:
-	 */
-	if (BCH_SUBVOLUME_SNAP(&subvolume))
+	if (!s_t.master_subvol)
 		goto advance;
 
-	if (!bkey_is_inode(k.k))
-		goto advance;
-
-	ret = bch2_inode_unpack(k, &u);
+	ret = bch2_inode_find_by_inum_trans(trans,
+				(subvol_inum) {
+					le32_to_cpu(s_t.master_subvol),
+					k.k->p.offset,
+				}, &u);
 	if (ret)
 		return ret;
 
@@ -587,7 +580,7 @@ static int bch2_fs_quota_read_inode(struct btree_trans *trans,
 	bch2_quota_acct(c, bch_qid(&u), Q_INO, 1,
 			KEY_TYPE_QUOTA_NOCHECK);
 advance:
-	bch2_btree_iter_set_pos(iter, POS(iter->pos.inode, iter->pos.offset + 1));
+	bch2_btree_iter_set_pos(iter, bpos_nosnap_successor(iter->pos));
 	return 0;
 }
 
@@ -907,10 +900,8 @@ static int bch2_set_quota_trans(struct btree_trans *trans,
 	struct bkey_s_c k;
 	int ret;
 
-	bch2_trans_iter_init(trans, &iter, BTREE_ID_quotas, new_quota->k.p,
-			     BTREE_ITER_SLOTS|BTREE_ITER_INTENT);
-	k = bch2_btree_iter_peek_slot(&iter);
-
+	k = bch2_bkey_get_iter(trans, &iter, BTREE_ID_quotas, new_quota->k.p,
+			       BTREE_ITER_SLOTS|BTREE_ITER_INTENT);
 	ret = bkey_err(k);
 	if (unlikely(ret))
 		return ret;
diff --git a/libbcachefs/quota.h b/libbcachefs/quota.h
index 146264fd..b0f7d4ee 100644
--- a/libbcachefs/quota.h
+++ b/libbcachefs/quota.h
@@ -13,6 +13,7 @@ void bch2_quota_to_text(struct printbuf *, struct bch_fs *, struct bkey_s_c);
 #define bch2_bkey_ops_quota ((struct bkey_ops) {	\
 	.key_invalid	= bch2_quota_invalid,		\
 	.val_to_text	= bch2_quota_to_text,		\
+	.min_val_size	= 32,				\
 })
 
 static inline struct bch_qid bch_qid(struct bch_inode_unpacked *u)
diff --git a/libbcachefs/rebalance.c b/libbcachefs/rebalance.c
index 4df981bd..66c40999 100644
--- a/libbcachefs/rebalance.c
+++ b/libbcachefs/rebalance.c
@@ -12,11 +12,11 @@
 #include "move.h"
 #include "rebalance.h"
 #include "super-io.h"
+#include "trace.h"
 
 #include <linux/freezer.h>
 #include <linux/kthread.h>
 #include <linux/sched/cputime.h>
-#include <trace/events/bcachefs.h>
 
 /*
  * Check if an extent should be moved:
diff --git a/libbcachefs/recovery.c b/libbcachefs/recovery.c
index 91a66b59..af76c029 100644
--- a/libbcachefs/recovery.c
+++ b/libbcachefs/recovery.c
@@ -1025,16 +1025,25 @@ fsck_err:
 
 static int bch2_fs_initialize_subvolumes(struct bch_fs *c)
 {
-	struct bkey_i_snapshot	root_snapshot;
-	struct bkey_i_subvolume root_volume;
+	struct bkey_i_snapshot_tree	root_tree;
+	struct bkey_i_snapshot		root_snapshot;
+	struct bkey_i_subvolume		root_volume;
 	int ret;
 
+	bkey_snapshot_tree_init(&root_tree.k_i);
+	root_tree.k.p.offset		= 1;
+	root_tree.v.master_subvol	= cpu_to_le32(1);
+	root_tree.v.root_snapshot	= cpu_to_le32(U32_MAX);
+	ret = bch2_btree_insert(c, BTREE_ID_snapshot_trees,
+				&root_tree.k_i,
+				NULL, NULL, 0);
+
 	bkey_snapshot_init(&root_snapshot.k_i);
 	root_snapshot.k.p.offset = U32_MAX;
 	root_snapshot.v.flags	= 0;
 	root_snapshot.v.parent	= 0;
 	root_snapshot.v.subvol	= BCACHEFS_ROOT_SUBVOL;
-	root_snapshot.v.pad	= 0;
+	root_snapshot.v.tree	= cpu_to_le32(1);
 	SET_BCH_SNAPSHOT_SUBVOL(&root_snapshot.v, true);
 
 	ret = bch2_btree_insert(c, BTREE_ID_snapshots,
@@ -1065,12 +1074,11 @@ static int bch2_fs_upgrade_for_subvolumes(struct btree_trans *trans)
 	struct bch_inode_unpacked inode;
 	int ret;
 
-	bch2_trans_iter_init(trans, &iter, BTREE_ID_inodes,
-			     SPOS(0, BCACHEFS_ROOT_INO, U32_MAX), 0);
-	k = bch2_btree_iter_peek_slot(&iter);
+	k = bch2_bkey_get_iter(trans, &iter, BTREE_ID_inodes,
+			       SPOS(0, BCACHEFS_ROOT_INO, U32_MAX), 0);
 	ret = bkey_err(k);
 	if (ret)
-		goto err;
+		return ret;
 
 	if (!bkey_is_inode(k.k)) {
 		bch_err(trans->c, "root inode not found");
@@ -1136,8 +1144,12 @@ int bch2_fs_recovery(struct bch_fs *c)
 	}
 
 	if (!c->opts.nochanges) {
-		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");
+		if (c->sb.version < bcachefs_metadata_required_upgrade_below) {
+			bch_info(c, "version %s (%u) prior to %s (%u), upgrade and fsck required",
+				 bch2_metadata_versions[c->sb.version],
+				 c->sb.version,
+				 bch2_metadata_versions[bcachefs_metadata_required_upgrade_below],
+				 bcachefs_metadata_required_upgrade_below);
 			c->opts.version_upgrade	= true;
 			c->opts.fsck		= true;
 			c->opts.fix_errors	= FSCK_OPT_YES;
diff --git a/libbcachefs/reflink.c b/libbcachefs/reflink.c
index d8426e75..9430899a 100644
--- a/libbcachefs/reflink.c
+++ b/libbcachefs/reflink.c
@@ -30,12 +30,6 @@ int bch2_reflink_p_invalid(const struct bch_fs *c, struct bkey_s_c k,
 {
 	struct bkey_s_c_reflink_p p = bkey_s_c_to_reflink_p(k);
 
-	if (bkey_val_bytes(p.k) != sizeof(*p.v)) {
-		prt_printf(err, "incorrect value size (%zu != %zu)",
-		       bkey_val_bytes(p.k), sizeof(*p.v));
-		return -EINVAL;
-	}
-
 	if (c->sb.version >= bcachefs_metadata_version_reflink_p_fix &&
 	    le64_to_cpu(p.v->idx) < le32_to_cpu(p.v->front_pad)) {
 		prt_printf(err, "idx < front_pad (%llu < %u)",
@@ -80,14 +74,6 @@ bool bch2_reflink_p_merge(struct bch_fs *c, struct bkey_s _l, struct bkey_s_c _r
 int bch2_reflink_v_invalid(const struct bch_fs *c, struct bkey_s_c k,
 			   unsigned flags, struct printbuf *err)
 {
-	struct bkey_s_c_reflink_v r = bkey_s_c_to_reflink_v(k);
-
-	if (bkey_val_bytes(r.k) < sizeof(*r.v)) {
-		prt_printf(err, "incorrect value size (%zu < %zu)",
-		       bkey_val_bytes(r.k), sizeof(*r.v));
-		return -BCH_ERR_invalid_bkey;
-	}
-
 	return bch2_bkey_ptrs_invalid(c, k, flags, err);
 }
 
@@ -133,12 +119,6 @@ int bch2_trans_mark_reflink_v(struct btree_trans *trans,
 int bch2_indirect_inline_data_invalid(const struct bch_fs *c, struct bkey_s_c k,
 				      unsigned flags, struct printbuf *err)
 {
-	if (bkey_val_bytes(k.k) < sizeof(struct bch_indirect_inline_data)) {
-		prt_printf(err, "incorrect value size (%zu < %zu)",
-		       bkey_val_bytes(k.k), sizeof(struct bch_indirect_inline_data));
-		return -BCH_ERR_invalid_bkey;
-	}
-
 	return 0;
 }
 
diff --git a/libbcachefs/reflink.h b/libbcachefs/reflink.h
index 2391037c..ba400188 100644
--- a/libbcachefs/reflink.h
+++ b/libbcachefs/reflink.h
@@ -14,6 +14,7 @@ bool bch2_reflink_p_merge(struct bch_fs *, struct bkey_s, struct bkey_s_c);
 	.key_merge	= bch2_reflink_p_merge,			\
 	.trans_trigger	= bch2_trans_mark_reflink_p,		\
 	.atomic_trigger	= bch2_mark_reflink_p,			\
+	.min_val_size	= 16,					\
 })
 
 int bch2_reflink_v_invalid(const struct bch_fs *, struct bkey_s_c,
@@ -29,6 +30,7 @@ int bch2_trans_mark_reflink_v(struct btree_trans *, enum btree_id, unsigned,
 	.swab		= bch2_ptr_swab,			\
 	.trans_trigger	= bch2_trans_mark_reflink_v,		\
 	.atomic_trigger	= bch2_mark_extent,			\
+	.min_val_size	= 8,					\
 })
 
 int bch2_indirect_inline_data_invalid(const struct bch_fs *, struct bkey_s_c,
@@ -44,6 +46,7 @@ int bch2_trans_mark_indirect_inline_data(struct btree_trans *,
 	.key_invalid	= bch2_indirect_inline_data_invalid,	\
 	.val_to_text	= bch2_indirect_inline_data_to_text,	\
 	.trans_trigger	= bch2_trans_mark_indirect_inline_data,	\
+	.min_val_size	= 8,					\
 })
 
 static inline const __le64 *bkey_refcount_c(struct bkey_s_c k)
diff --git a/libbcachefs/subvolume.c b/libbcachefs/subvolume.c
index 6407d19e..68121df2 100644
--- a/libbcachefs/subvolume.c
+++ b/libbcachefs/subvolume.c
@@ -8,8 +8,75 @@
 #include "fs.h"
 #include "subvolume.h"
 
+static int bch2_subvolume_delete(struct btree_trans *, u32);
+
 /* Snapshot tree: */
 
+void bch2_snapshot_tree_to_text(struct printbuf *out, struct bch_fs *c,
+				struct bkey_s_c k)
+{
+	struct bkey_s_c_snapshot_tree t = bkey_s_c_to_snapshot_tree(k);
+
+	prt_printf(out, "subvol %u root snapshot %u",
+		   le32_to_cpu(t.v->master_subvol),
+		   le32_to_cpu(t.v->root_snapshot));
+}
+
+int bch2_snapshot_tree_invalid(const struct bch_fs *c, struct bkey_s_c k,
+			       unsigned flags, struct printbuf *err)
+{
+	if (bkey_gt(k.k->p, POS(0, U32_MAX)) ||
+	    bkey_lt(k.k->p, POS(0, 1))) {
+		prt_printf(err, "bad pos");
+		return -BCH_ERR_invalid_bkey;
+	}
+
+	return 0;
+}
+
+int bch2_snapshot_tree_lookup(struct btree_trans *trans, u32 id,
+			      struct bch_snapshot_tree *s)
+{
+	return bch2_bkey_get_val_typed(trans, BTREE_ID_snapshot_trees, POS(0, id),
+				       BTREE_ITER_WITH_UPDATES, snapshot_tree, s);
+}
+
+static struct bkey_i_snapshot_tree *
+__snapshot_tree_create(struct btree_trans *trans)
+{
+	struct btree_iter iter;
+	int ret = bch2_bkey_get_empty_slot(trans, &iter,
+			BTREE_ID_snapshot_trees, POS(0, U32_MAX));
+	struct bkey_i_snapshot_tree *s_t;
+
+	if (ret == -BCH_ERR_ENOSPC_btree_slot)
+		ret = -BCH_ERR_ENOSPC_snapshot_tree;
+	if (ret)
+		return ERR_PTR(ret);
+
+	s_t = bch2_bkey_alloc(trans, &iter, 0, snapshot_tree);
+	ret = PTR_ERR_OR_ZERO(s_t);
+	bch2_trans_iter_exit(trans, &iter);
+	return ret ? ERR_PTR(ret) : s_t;
+}
+
+static int snapshot_tree_create(struct btree_trans *trans,
+				u32 root_id, u32 subvol_id, u32 *tree_id)
+{
+	struct bkey_i_snapshot_tree *n_tree =
+		__snapshot_tree_create(trans);
+
+	if (IS_ERR(n_tree))
+		return PTR_ERR(n_tree);
+
+	n_tree->v.master_subvol	= cpu_to_le32(subvol_id);
+	n_tree->v.root_snapshot	= cpu_to_le32(root_id);
+	*tree_id = n_tree->k.p.offset;
+	return 0;
+}
+
+/* Snapshot nodes: */
+
 void bch2_snapshot_to_text(struct printbuf *out, struct bch_fs *c,
 			   struct bkey_s_c k)
 {
@@ -36,12 +103,6 @@ int bch2_snapshot_invalid(const struct bch_fs *c, struct bkey_s_c k,
 		return -BCH_ERR_invalid_bkey;
 	}
 
-	if (bkey_val_bytes(k.k) != sizeof(struct bch_snapshot)) {
-		prt_printf(err, "bad val size (%zu != %zu)",
-		       bkey_val_bytes(k.k), sizeof(struct bch_snapshot));
-		return -BCH_ERR_invalid_bkey;
-	}
-
 	s = bkey_s_c_to_snapshot(k);
 
 	id = le32_to_cpu(s.v->parent);
@@ -96,11 +157,13 @@ int bch2_mark_snapshot(struct btree_trans *trans,
 		t->children[0]	= le32_to_cpu(s.v->children[0]);
 		t->children[1]	= le32_to_cpu(s.v->children[1]);
 		t->subvol	= BCH_SNAPSHOT_SUBVOL(s.v) ? le32_to_cpu(s.v->subvol) : 0;
+		t->tree		= le32_to_cpu(s.v->tree);
 	} else {
 		t->parent	= 0;
 		t->children[0]	= 0;
 		t->children[1]	= 0;
 		t->subvol	= 0;
+		t->tree		= 0;
 	}
 
 	return 0;
@@ -109,20 +172,8 @@ int bch2_mark_snapshot(struct btree_trans *trans,
 static int snapshot_lookup(struct btree_trans *trans, u32 id,
 			   struct bch_snapshot *s)
 {
-	struct btree_iter iter;
-	struct bkey_s_c k;
-	int ret;
-
-	bch2_trans_iter_init(trans, &iter, BTREE_ID_snapshots, POS(0, id),
-			     BTREE_ITER_WITH_UPDATES);
-	k = bch2_btree_iter_peek_slot(&iter);
-	ret = bkey_err(k) ?: k.k->type == KEY_TYPE_snapshot ? 0 : -ENOENT;
-
-	if (!ret)
-		*s = *bkey_s_c_to_snapshot(k).v;
-
-	bch2_trans_iter_exit(trans, &iter);
-	return ret;
+	return bch2_bkey_get_val_typed(trans, BTREE_ID_snapshots, POS(0, id),
+				       BTREE_ITER_WITH_UPDATES, snapshot, s);
 }
 
 static int snapshot_live(struct btree_trans *trans, u32 id)
@@ -175,6 +226,266 @@ static int bch2_snapshot_set_equiv(struct btree_trans *trans, struct bkey_s_c k)
 }
 
 /* fsck: */
+
+static u32 bch2_snapshot_child(struct bch_fs *c, u32 id, unsigned child)
+{
+	return snapshot_t(c, id)->children[child];
+}
+
+static u32 bch2_snapshot_left_child(struct bch_fs *c, u32 id)
+{
+	return bch2_snapshot_child(c, id, 0);
+}
+
+static u32 bch2_snapshot_right_child(struct bch_fs *c, u32 id)
+{
+	return bch2_snapshot_child(c, id, 1);
+}
+
+static u32 bch2_snapshot_tree_next(struct bch_fs *c, u32 id)
+{
+	u32 n, parent;
+
+	n = bch2_snapshot_left_child(c, id);
+	if (n)
+		return n;
+
+	while ((parent = bch2_snapshot_parent(c, id))) {
+		n = bch2_snapshot_right_child(c, parent);
+		if (n && n != id)
+			return n;
+		id = parent;
+	}
+
+	return 0;
+}
+
+static u32 bch2_snapshot_tree_oldest_subvol(struct bch_fs *c, u32 snapshot_root)
+{
+	u32 id = snapshot_root;
+	u32 subvol = 0, s;
+
+	while (id) {
+		s = snapshot_t(c, id)->subvol;
+
+		if (s && (!subvol || s < subvol))
+			subvol = s;
+
+		id = bch2_snapshot_tree_next(c, id);
+	}
+
+	return subvol;
+}
+
+static int bch2_snapshot_tree_master_subvol(struct btree_trans *trans,
+					    u32 snapshot_root, u32 *subvol_id)
+{
+	struct bch_fs *c = trans->c;
+	struct btree_iter iter;
+	struct bkey_s_c k;
+	struct bkey_s_c_subvolume s;
+	int ret;
+
+	for_each_btree_key_norestart(trans, iter, BTREE_ID_subvolumes, POS_MIN,
+				     0, k, ret) {
+		if (k.k->type != KEY_TYPE_subvolume)
+			continue;
+
+		s = bkey_s_c_to_subvolume(k);
+		if (!bch2_snapshot_is_ancestor(c, le32_to_cpu(s.v->snapshot), snapshot_root))
+			continue;
+		if (!BCH_SUBVOLUME_SNAP(s.v)) {
+			*subvol_id = s.k->p.offset;
+			goto found;
+		}
+	}
+	ret = ret ?: -ENOENT;
+found:
+	bch2_trans_iter_exit(trans, &iter);
+
+	if (ret == -ENOENT) {
+		struct bkey_i_subvolume *s;
+
+		*subvol_id = bch2_snapshot_tree_oldest_subvol(c, snapshot_root);
+
+		s = bch2_bkey_get_mut_typed(trans, &iter,
+					    BTREE_ID_subvolumes, POS(0, *subvol_id),
+					    0, subvolume);
+		ret = PTR_ERR_OR_ZERO(s);
+		if (ret)
+			return ret;
+
+		SET_BCH_SUBVOLUME_SNAP(&s->v, false);
+	}
+
+	return ret;
+}
+
+static int check_snapshot_tree(struct btree_trans *trans,
+			       struct btree_iter *iter,
+			       struct bkey_s_c k)
+{
+	struct bch_fs *c = trans->c;
+	struct bkey_s_c_snapshot_tree st;
+	struct bch_snapshot s;
+	struct bch_subvolume subvol;
+	struct printbuf buf = PRINTBUF;
+	u32 root_id;
+	int ret;
+
+	if (k.k->type != KEY_TYPE_snapshot_tree)
+		return 0;
+
+	st = bkey_s_c_to_snapshot_tree(k);
+	root_id = le32_to_cpu(st.v->root_snapshot);
+
+	ret = snapshot_lookup(trans, root_id, &s);
+	if (ret && !bch2_err_matches(ret, ENOENT))
+		goto err;
+
+	if (fsck_err_on(ret ||
+			root_id != bch2_snapshot_root(c, root_id) ||
+			st.k->p.offset != le32_to_cpu(s.tree),
+			c,
+			"snapshot tree points to missing/incorrect snapshot:\n  %s",
+			(bch2_bkey_val_to_text(&buf, c, st.s_c), buf.buf))) {
+		ret = bch2_btree_delete_at(trans, iter, 0);
+		goto err;
+	}
+
+	ret = bch2_subvolume_get(trans, le32_to_cpu(st.v->master_subvol),
+				 false, 0, &subvol);
+	if (ret && !bch2_err_matches(ret, ENOENT))
+		goto err;
+
+	if (fsck_err_on(ret ||
+			!bch2_snapshot_is_ancestor(c,
+						   le32_to_cpu(subvol.snapshot),
+						   root_id) ||
+			!BCH_SUBVOLUME_SNAP(&subvol), c,
+			"snapshot tree points to missing/incorrect subvolume:\n  %s",
+			(printbuf_reset(&buf),
+			 bch2_bkey_val_to_text(&buf, c, st.s_c), buf.buf))) {
+		struct bkey_i_snapshot_tree *u;
+		u32 subvol_id;
+
+		ret = bch2_snapshot_tree_master_subvol(trans, root_id, &subvol_id);
+		if (ret)
+			goto err;
+
+		u = bch2_bkey_make_mut_typed(trans, iter, k, 0, snapshot_tree);
+		ret = PTR_ERR_OR_ZERO(u);
+		if (ret)
+			goto err;
+
+		u->v.master_subvol = cpu_to_le32(subvol_id);
+		st = snapshot_tree_i_to_s_c(u);
+	}
+err:
+fsck_err:
+	printbuf_exit(&buf);
+	return ret;
+}
+
+/*
+ * For each snapshot_tree, make sure it points to the root of a snapshot tree
+ * and that snapshot entry points back to it, or delete it.
+ *
+ * And, make sure it points to a subvolume within that snapshot tree, or correct
+ * it to point to the oldest subvolume within that snapshot tree.
+ */
+int bch2_fs_check_snapshot_trees(struct bch_fs *c)
+{
+	struct btree_iter iter;
+	struct bkey_s_c k;
+	int ret;
+
+	ret = bch2_trans_run(c,
+		for_each_btree_key_commit(&trans, iter,
+			BTREE_ID_snapshot_trees, POS_MIN,
+			BTREE_ITER_PREFETCH, k,
+			NULL, NULL, BTREE_INSERT_LAZY_RW|BTREE_INSERT_NOFAIL,
+		check_snapshot_tree(&trans, &iter, k)));
+
+	if (ret)
+		bch_err(c, "error %i checking snapshot trees", ret);
+	return ret;
+}
+
+/*
+ * Look up snapshot tree for @tree_id and find root,
+ * make sure @snap_id is a descendent:
+ */
+static int snapshot_tree_ptr_good(struct btree_trans *trans,
+				  u32 snap_id, u32 tree_id)
+{
+	struct bch_snapshot_tree s_t;
+	int ret = bch2_snapshot_tree_lookup(trans, tree_id, &s_t);
+
+	if (ret)
+		return ret;
+
+	return bch2_snapshot_is_ancestor(trans->c, snap_id, le32_to_cpu(s_t.root_snapshot));
+}
+
+/*
+ * snapshot_tree pointer was incorrect: look up root snapshot node, make sure
+ * its snapshot_tree pointer is correct (allocate new one if necessary), then
+ * update this node's pointer to root node's pointer:
+ */
+static int snapshot_tree_ptr_repair(struct btree_trans *trans,
+				    struct btree_iter *iter,
+				    struct bkey_s_c_snapshot *s)
+{
+	struct bch_fs *c = trans->c;
+	struct btree_iter root_iter;
+	struct bch_snapshot_tree s_t;
+	struct bkey_s_c_snapshot root;
+	struct bkey_i_snapshot *u;
+	u32 root_id = bch2_snapshot_root(c, s->k->p.offset), tree_id;
+	int ret;
+
+	root = bch2_bkey_get_iter_typed(trans, &root_iter,
+			       BTREE_ID_snapshots, POS(0, root_id),
+			       BTREE_ITER_WITH_UPDATES, snapshot);
+	ret = bkey_err(root);
+	if (ret)
+		goto err;
+
+	tree_id = le32_to_cpu(root.v->tree);
+
+	ret = bch2_snapshot_tree_lookup(trans, tree_id, &s_t);
+	if (ret)
+		return ret;
+
+	if (le32_to_cpu(s_t.root_snapshot) != root_id) {
+		u = bch2_bkey_make_mut_typed(trans, &root_iter, root.s_c, 0, snapshot);
+		ret =   PTR_ERR_OR_ZERO(u) ?:
+			snapshot_tree_create(trans, root_id,
+				bch2_snapshot_tree_oldest_subvol(c, root_id),
+				&tree_id);
+		if (ret)
+			goto err;
+
+		u->v.tree = cpu_to_le32(tree_id);
+		if (s->k->p.snapshot == root_id)
+			*s = snapshot_i_to_s_c(u);
+	}
+
+	if (s->k->p.snapshot != root_id) {
+		u = bch2_bkey_make_mut_typed(trans, iter, s->s_c, 0, snapshot);
+		ret = PTR_ERR_OR_ZERO(u);
+		if (ret)
+			goto err;
+
+		u->v.tree = cpu_to_le32(tree_id);
+		*s = snapshot_i_to_s_c(u);
+	}
+err:
+	bch2_trans_iter_exit(trans, &root_iter);
+	return ret;
+}
+
 static int check_snapshot(struct btree_trans *trans,
 			  struct btree_iter *iter,
 			  struct bkey_s_c k)
@@ -260,9 +571,22 @@ static int check_snapshot(struct btree_trans *trans,
 			ret = bch2_trans_update(trans, iter, &u->k_i, 0);
 			if (ret)
 				goto err;
+
+			s = snapshot_i_to_s_c(u);
 		}
 	}
 
+	ret = snapshot_tree_ptr_good(trans, s.k->p.offset, le32_to_cpu(s.v->tree));
+	if (ret < 0)
+		goto err;
+
+	if (fsck_err_on(!ret, c, "snapshot points to missing/incorrect tree:\n  %s",
+			(bch2_bkey_val_to_text(&buf, c, s.s_c), buf.buf))) {
+		ret = snapshot_tree_ptr_repair(trans, iter, &s);
+		if (ret)
+			goto err;
+	}
+
 	if (BCH_SNAPSHOT_DELETED(s.v))
 		set_bit(BCH_FS_HAVE_DELETED_SNAPSHOTS, &c->flags);
 err:
@@ -273,23 +597,19 @@ fsck_err:
 
 int bch2_fs_check_snapshots(struct bch_fs *c)
 {
-	struct btree_trans trans;
 	struct btree_iter iter;
 	struct bkey_s_c k;
 	int ret;
 
-	bch2_trans_init(&trans, c, 0, 0);
-
-	ret = for_each_btree_key_commit(&trans, iter,
+	ret = bch2_trans_run(c,
+		for_each_btree_key_commit(&trans, iter,
 			BTREE_ID_snapshots, POS_MIN,
 			BTREE_ITER_PREFETCH, k,
 			NULL, NULL, BTREE_INSERT_LAZY_RW|BTREE_INSERT_NOFAIL,
-		check_snapshot(&trans, &iter, k));
+		check_snapshot(&trans, &iter, k)));
 
 	if (ret)
 		bch_err(c, "error %i checking snapshots", ret);
-
-	bch2_trans_exit(&trans);
 	return ret;
 }
 
@@ -297,10 +617,11 @@ static int check_subvol(struct btree_trans *trans,
 			struct btree_iter *iter,
 			struct bkey_s_c k)
 {
+	struct bch_fs *c = trans->c;
 	struct bkey_s_c_subvolume subvol;
 	struct bch_snapshot snapshot;
 	unsigned snapid;
-	int ret;
+	int ret = 0;
 
 	if (k.k->type != KEY_TYPE_subvolume)
 		return 0;
@@ -310,21 +631,44 @@ static int check_subvol(struct btree_trans *trans,
 	ret = snapshot_lookup(trans, snapid, &snapshot);
 
 	if (ret == -ENOENT)
-		bch_err(trans->c, "subvolume %llu points to nonexistent snapshot %u",
+		bch_err(c, "subvolume %llu points to nonexistent snapshot %u",
 			k.k->p.offset, snapid);
 	if (ret)
 		return ret;
 
 	if (BCH_SUBVOLUME_UNLINKED(subvol.v)) {
+		bch2_fs_lazy_rw(c);
+
 		ret = bch2_subvolume_delete(trans, iter->pos.offset);
-		if (ret && !bch2_err_matches(ret, BCH_ERR_transaction_restart))
-			bch_err(trans->c, "error deleting subvolume %llu: %s",
+		if (ret)
+			bch_err(c, "error deleting subvolume %llu: %s",
 				iter->pos.offset, bch2_err_str(ret));
+		return ret ?: -BCH_ERR_transaction_restart_nested;
+	}
+
+	if (!BCH_SUBVOLUME_SNAP(subvol.v)) {
+		u32 snapshot_root = bch2_snapshot_root(c, le32_to_cpu(subvol.v->snapshot));
+		struct bch_snapshot_tree st;
+
+		ret = bch2_snapshot_tree_lookup(trans, snapshot_root, &st);
 		if (ret)
 			return ret;
+
+		if (fsck_err_on(le32_to_cpu(st.master_subvol) != subvol.k->p.offset, c,
+				"subvolume %llu is not set as snapshot but is not master subvolume",
+				k.k->p.offset)) {
+			struct bkey_i_subvolume *s =
+				bch2_bkey_make_mut_typed(trans, iter, subvol.s_c, 0, subvolume);
+			ret = PTR_ERR_OR_ZERO(s);
+			if (ret)
+				return ret;
+
+			SET_BCH_SUBVOLUME_SNAP(&s->v, true);
+		}
 	}
 
-	return 0;
+fsck_err:
+	return ret;
 }
 
 int bch2_fs_check_subvols(struct bch_fs *c)
@@ -381,13 +725,13 @@ static int bch2_snapshot_node_set_deleted(struct btree_trans *trans, u32 id)
 	struct bkey_i_snapshot *s;
 	int ret = 0;
 
-	bch2_trans_iter_init(trans, &iter, BTREE_ID_snapshots, POS(0, id),
-			     BTREE_ITER_INTENT);
-	s = bch2_bkey_get_mut_typed(trans, &iter, snapshot);
+	s = bch2_bkey_get_mut_typed(trans, &iter,
+				    BTREE_ID_snapshots, POS(0, id),
+				    0, snapshot);
 	ret = PTR_ERR_OR_ZERO(s);
 	if (unlikely(ret)) {
 		bch2_fs_inconsistent_on(ret == -ENOENT, trans->c, "missing snapshot %u", id);
-		goto err;
+		return ret;
 	}
 
 	/* already deleted? */
@@ -397,10 +741,6 @@ static int bch2_snapshot_node_set_deleted(struct btree_trans *trans, u32 id)
 	SET_BCH_SNAPSHOT_DELETED(&s->v, true);
 	SET_BCH_SNAPSHOT_SUBVOL(&s->v, false);
 	s->v.subvol = 0;
-
-	ret = bch2_trans_update(trans, &iter, &s->k_i, 0);
-	if (ret)
-		goto err;
 err:
 	bch2_trans_iter_exit(trans, &iter);
 	return ret;
@@ -408,27 +748,21 @@ err:
 
 static int bch2_snapshot_node_delete(struct btree_trans *trans, u32 id)
 {
+	struct bch_fs *c = trans->c;
 	struct btree_iter iter, p_iter = (struct btree_iter) { NULL };
-	struct bkey_s_c k;
+	struct btree_iter tree_iter = (struct btree_iter) { NULL };
 	struct bkey_s_c_snapshot s;
 	u32 parent_id;
 	unsigned i;
 	int ret = 0;
 
-	bch2_trans_iter_init(trans, &iter, BTREE_ID_snapshots, POS(0, id),
-			     BTREE_ITER_INTENT);
-	k = bch2_btree_iter_peek_slot(&iter);
-	ret = bkey_err(k);
-	if (ret)
-		goto err;
+	s = bch2_bkey_get_iter_typed(trans, &iter, BTREE_ID_snapshots, POS(0, id),
+				     BTREE_ITER_INTENT, snapshot);
+	ret = bkey_err(s);
+	bch2_fs_inconsistent_on(ret == -ENOENT, c, "missing snapshot %u", id);
 
-	if (k.k->type != KEY_TYPE_snapshot) {
-		bch2_fs_inconsistent(trans->c, "missing snapshot %u", id);
-		ret = -ENOENT;
+	if (ret)
 		goto err;
-	}
-
-	s = bkey_s_c_to_snapshot(k);
 
 	BUG_ON(!BCH_SNAPSHOT_DELETED(s.v));
 	parent_id = le32_to_cpu(s.v->parent);
@@ -436,13 +770,12 @@ static int bch2_snapshot_node_delete(struct btree_trans *trans, u32 id)
 	if (parent_id) {
 		struct bkey_i_snapshot *parent;
 
-		bch2_trans_iter_init(trans, &p_iter, BTREE_ID_snapshots,
-				     POS(0, parent_id),
-				     BTREE_ITER_INTENT);
-		parent = bch2_bkey_get_mut_typed(trans, &p_iter, snapshot);
+		parent = bch2_bkey_get_mut_typed(trans, &p_iter,
+				     BTREE_ID_snapshots, POS(0, parent_id),
+				     0, snapshot);
 		ret = PTR_ERR_OR_ZERO(parent);
 		if (unlikely(ret)) {
-			bch2_fs_inconsistent_on(ret == -ENOENT, trans->c, "missing snapshot %u", parent_id);
+			bch2_fs_inconsistent_on(ret == -ENOENT, c, "missing snapshot %u", parent_id);
 			goto err;
 		}
 
@@ -451,7 +784,7 @@ static int bch2_snapshot_node_delete(struct btree_trans *trans, u32 id)
 				break;
 
 		if (i == 2)
-			bch_err(trans->c, "snapshot %u missing child pointer to %u",
+			bch_err(c, "snapshot %u missing child pointer to %u",
 				parent_id, id);
 		else
 			parent->v.children[i] = 0;
@@ -460,29 +793,49 @@ static int bch2_snapshot_node_delete(struct btree_trans *trans, u32 id)
 		    le32_to_cpu(parent->v.children[1]))
 			swap(parent->v.children[0],
 			     parent->v.children[1]);
+	} else {
+		/*
+		 * We're deleting the root of a snapshot tree: update the
+		 * snapshot_tree entry to point to the new root, or delete it if
+		 * this is the last snapshot ID in this tree:
+		 */
+		struct bkey_i_snapshot_tree *s_t;
+
+		BUG_ON(s.v->children[1]);
 
-		ret = bch2_trans_update(trans, &p_iter, &parent->k_i, 0);
+		s_t = bch2_bkey_get_mut_typed(trans, &tree_iter,
+				BTREE_ID_snapshot_trees, POS(0, le32_to_cpu(s.v->tree)),
+				0, snapshot_tree);
+		ret = PTR_ERR_OR_ZERO(s_t);
 		if (ret)
 			goto err;
+
+		if (s.v->children[0]) {
+			s_t->v.root_snapshot = cpu_to_le32(s.v->children[0]);
+		} else {
+			s_t->k.type = KEY_TYPE_deleted;
+			set_bkey_val_u64s(&s_t->k, 0);
+		}
 	}
 
 	ret = bch2_btree_delete_at(trans, &iter, 0);
 err:
+	bch2_trans_iter_exit(trans, &tree_iter);
 	bch2_trans_iter_exit(trans, &p_iter);
 	bch2_trans_iter_exit(trans, &iter);
 	return ret;
 }
 
-int bch2_snapshot_node_create(struct btree_trans *trans, u32 parent,
-			      u32 *new_snapids,
-			      u32 *snapshot_subvols,
-			      unsigned nr_snapids)
+static int create_snapids(struct btree_trans *trans, u32 parent, u32 tree,
+			  u32 *new_snapids,
+			  u32 *snapshot_subvols,
+			  unsigned nr_snapids)
 {
 	struct btree_iter iter;
 	struct bkey_i_snapshot *n;
 	struct bkey_s_c k;
 	unsigned i;
-	int ret = 0;
+	int ret;
 
 	bch2_trans_iter_init(trans, &iter, BTREE_ID_snapshots,
 			     POS_MIN, BTREE_ITER_INTENT);
@@ -502,7 +855,7 @@ int bch2_snapshot_node_create(struct btree_trans *trans, u32 parent,
 			goto err;
 		}
 
-		n = bch2_bkey_alloc(trans, &iter, snapshot);
+		n = bch2_bkey_alloc(trans, &iter, 0, snapshot);
 		ret = PTR_ERR_OR_ZERO(n);
 		if (ret)
 			goto err;
@@ -510,47 +863,102 @@ int bch2_snapshot_node_create(struct btree_trans *trans, u32 parent,
 		n->v.flags	= 0;
 		n->v.parent	= cpu_to_le32(parent);
 		n->v.subvol	= cpu_to_le32(snapshot_subvols[i]);
-		n->v.pad	= 0;
+		n->v.tree	= cpu_to_le32(tree);
 		SET_BCH_SNAPSHOT_SUBVOL(&n->v, true);
 
-		ret   = bch2_trans_update(trans, &iter, &n->k_i, 0) ?:
-			bch2_mark_snapshot(trans, BTREE_ID_snapshots, 0,
-					   bkey_s_c_null, bkey_i_to_s_c(&n->k_i), 0);
+		ret = bch2_mark_snapshot(trans, BTREE_ID_snapshots, 0,
+					 bkey_s_c_null, bkey_i_to_s_c(&n->k_i), 0);
 		if (ret)
 			goto err;
 
 		new_snapids[i]	= iter.pos.offset;
 	}
+err:
+	bch2_trans_iter_exit(trans, &iter);
+	return ret;
+}
 
-	if (parent) {
-		bch2_btree_iter_set_pos(&iter, POS(0, parent));
-		n = bch2_bkey_get_mut_typed(trans, &iter, snapshot);
-		ret = PTR_ERR_OR_ZERO(n);
-		if (unlikely(ret)) {
-			if (ret == -ENOENT)
-				bch_err(trans->c, "snapshot %u not found", parent);
-			goto err;
-		}
+/*
+ * Create new snapshot IDs as children of an existing snapshot ID:
+ */
+static int bch2_snapshot_node_create_children(struct btree_trans *trans, u32 parent,
+			      u32 *new_snapids,
+			      u32 *snapshot_subvols,
+			      unsigned nr_snapids)
+{
+	struct btree_iter iter;
+	struct bkey_i_snapshot *n_parent;
+	int ret = 0;
 
-		if (n->v.children[0] || n->v.children[1]) {
-			bch_err(trans->c, "Trying to add child snapshot nodes to parent that already has children");
-			ret = -EINVAL;
-			goto err;
-		}
+	n_parent = bch2_bkey_get_mut_typed(trans, &iter,
+			BTREE_ID_snapshots, POS(0, parent),
+			0, snapshot);
+	ret = PTR_ERR_OR_ZERO(n_parent);
+	if (unlikely(ret)) {
+		if (ret == -ENOENT)
+			bch_err(trans->c, "snapshot %u not found", parent);
+		return ret;
+	}
 
-		n->v.children[0] = cpu_to_le32(new_snapids[0]);
-		n->v.children[1] = cpu_to_le32(new_snapids[1]);
-		n->v.subvol = 0;
-		SET_BCH_SNAPSHOT_SUBVOL(&n->v, false);
-		ret   = bch2_trans_update(trans, &iter, &n->k_i, 0);
-		if (ret)
-			goto err;
+	if (n_parent->v.children[0] || n_parent->v.children[1]) {
+		bch_err(trans->c, "Trying to add child snapshot nodes to parent that already has children");
+		ret = -EINVAL;
+		goto err;
 	}
+
+	ret = create_snapids(trans, parent, le32_to_cpu(n_parent->v.tree),
+			     new_snapids, snapshot_subvols, nr_snapids);
+	if (ret)
+		goto err;
+
+	n_parent->v.children[0] = cpu_to_le32(new_snapids[0]);
+	n_parent->v.children[1] = cpu_to_le32(new_snapids[1]);
+	n_parent->v.subvol = 0;
+	SET_BCH_SNAPSHOT_SUBVOL(&n_parent->v, false);
 err:
 	bch2_trans_iter_exit(trans, &iter);
 	return ret;
 }
 
+/*
+ * Create a snapshot node that is the root of a new tree:
+ */
+static int bch2_snapshot_node_create_tree(struct btree_trans *trans,
+			      u32 *new_snapids,
+			      u32 *snapshot_subvols,
+			      unsigned nr_snapids)
+{
+	struct bkey_i_snapshot_tree *n_tree;
+	int ret;
+
+	n_tree = __snapshot_tree_create(trans);
+	ret =   PTR_ERR_OR_ZERO(n_tree) ?:
+		create_snapids(trans, 0, n_tree->k.p.offset,
+			     new_snapids, snapshot_subvols, nr_snapids);
+	if (ret)
+		return ret;
+
+	n_tree->v.master_subvol	= cpu_to_le32(snapshot_subvols[0]);
+	n_tree->v.root_snapshot	= cpu_to_le32(new_snapids[0]);
+	return 0;
+}
+
+int bch2_snapshot_node_create(struct btree_trans *trans, u32 parent,
+			      u32 *new_snapids,
+			      u32 *snapshot_subvols,
+			      unsigned nr_snapids)
+{
+	BUG_ON((parent == 0) != (nr_snapids == 1));
+	BUG_ON((parent != 0) != (nr_snapids == 2));
+
+	return parent
+		? bch2_snapshot_node_create_children(trans, parent,
+				new_snapids, snapshot_subvols, nr_snapids)
+		: bch2_snapshot_node_create_tree(trans,
+				new_snapids, snapshot_subvols, nr_snapids);
+
+}
+
 static int snapshot_delete_key(struct btree_trans *trans,
 			       struct btree_iter *iter,
 			       struct bkey_s_c k,
@@ -743,12 +1151,6 @@ int bch2_subvolume_invalid(const struct bch_fs *c, struct bkey_s_c k,
 		return -BCH_ERR_invalid_bkey;
 	}
 
-	if (bkey_val_bytes(k.k) != sizeof(struct bch_subvolume)) {
-		prt_printf(err, "incorrect value size (%zu != %zu)",
-		       bkey_val_bytes(k.k), sizeof(struct bch_subvolume));
-		return -BCH_ERR_invalid_bkey;
-	}
-
 	return 0;
 }
 
@@ -758,8 +1160,11 @@ void bch2_subvolume_to_text(struct printbuf *out, struct bch_fs *c,
 	struct bkey_s_c_subvolume s = bkey_s_c_to_subvolume(k);
 
 	prt_printf(out, "root %llu snapshot id %u",
-	       le64_to_cpu(s.v->inode),
-	       le32_to_cpu(s.v->snapshot));
+		   le64_to_cpu(s.v->inode),
+		   le32_to_cpu(s.v->snapshot));
+
+	if (bkey_val_bytes(s.k) > offsetof(struct bch_subvolume, parent))
+		prt_printf(out, " parent %u", le32_to_cpu(s.v->parent));
 }
 
 static __always_inline int
@@ -768,21 +1173,10 @@ bch2_subvolume_get_inlined(struct btree_trans *trans, unsigned subvol,
 			   int iter_flags,
 			   struct bch_subvolume *s)
 {
-	struct btree_iter iter;
-	struct bkey_s_c k;
-	int ret;
-
-	bch2_trans_iter_init(trans, &iter, BTREE_ID_subvolumes, POS(0, subvol),
-			     iter_flags);
-	k = bch2_btree_iter_peek_slot(&iter);
-	ret = bkey_err(k) ?: k.k->type == KEY_TYPE_subvolume ? 0 : -ENOENT;
-
-	if (ret == -ENOENT && inconsistent_if_not_found)
-		bch2_fs_inconsistent(trans->c, "missing subvolume %u", subvol);
-	if (!ret)
-		*s = *bkey_s_c_to_subvolume(k).v;
-
-	bch2_trans_iter_exit(trans, &iter);
+	int ret = bch2_bkey_get_val_typed(trans, BTREE_ID_subvolumes, POS(0, subvol),
+					  iter_flags, subvolume, s);
+	bch2_fs_inconsistent_on(ret == -ENOENT && inconsistent_if_not_found,
+				trans->c, "missing subvolume %u", subvol);
 	return ret;
 }
 
@@ -806,47 +1200,87 @@ int bch2_snapshot_get_subvol(struct btree_trans *trans, u32 snapshot,
 int bch2_subvolume_get_snapshot(struct btree_trans *trans, u32 subvol,
 				u32 *snapid)
 {
-	struct bch_subvolume s;
+	struct btree_iter iter;
+	struct bkey_s_c k;
 	int ret;
 
-	ret = bch2_subvolume_get_inlined(trans, subvol, true,
-					 BTREE_ITER_CACHED|
-					 BTREE_ITER_WITH_UPDATES,
-					 &s);
-	if (!ret)
-		*snapid = le32_to_cpu(s.snapshot);
+	k = bch2_bkey_get_iter(trans, &iter, BTREE_ID_subvolumes, POS(0, subvol),
+			       BTREE_ITER_CACHED|
+			       BTREE_ITER_WITH_UPDATES);
+	ret = bkey_err(k) ?: k.k->type == KEY_TYPE_subvolume ? 0 : -ENOENT;
+
+	if (likely(!ret))
+		*snapid = le32_to_cpu(bkey_s_c_to_subvolume(k).v->snapshot);
+	else if (ret == -ENOENT)
+		bch2_fs_inconsistent(trans->c, "missing subvolume %u", subvol);
+	bch2_trans_iter_exit(trans, &iter);
 	return ret;
 }
 
+static int bch2_subvolume_reparent(struct btree_trans *trans,
+				   struct btree_iter *iter,
+				   struct bkey_s_c k,
+				   u32 old_parent, u32 new_parent)
+{
+	struct bkey_i_subvolume *s;
+	int ret;
+
+	if (k.k->type != KEY_TYPE_subvolume)
+		return 0;
+
+	if (bkey_val_bytes(k.k) > offsetof(struct bch_subvolume, parent) &&
+	    le32_to_cpu(bkey_s_c_to_subvolume(k).v->parent) != old_parent)
+		return 0;
+
+	s = bch2_bkey_make_mut_typed(trans, iter, k, 0, subvolume);
+	ret = PTR_ERR_OR_ZERO(s);
+	if (ret)
+		return ret;
+
+	s->v.parent = cpu_to_le32(new_parent);
+	return 0;
+}
+
+/*
+ * Scan for subvolumes with parent @subvolid_to_delete, reparent:
+ */
+static int bch2_subvolumes_reparent(struct btree_trans *trans, u32 subvolid_to_delete)
+{
+	struct btree_iter iter;
+	struct bkey_s_c k;
+	struct bch_subvolume s;
+
+	return lockrestart_do(trans,
+			bch2_subvolume_get(trans, subvolid_to_delete, true,
+				   BTREE_ITER_CACHED, &s)) ?:
+		for_each_btree_key_commit(trans, iter,
+				BTREE_ID_subvolumes, POS_MIN, BTREE_ITER_PREFETCH, k,
+				NULL, NULL, BTREE_INSERT_NOFAIL,
+			bch2_subvolume_reparent(trans, &iter, k,
+					subvolid_to_delete, le32_to_cpu(s.parent)));
+}
+
 /*
  * Delete subvolume, mark snapshot ID as deleted, queue up snapshot
  * deletion/cleanup:
  */
-int bch2_subvolume_delete(struct btree_trans *trans, u32 subvolid)
+static int __bch2_subvolume_delete(struct btree_trans *trans, u32 subvolid)
 {
 	struct btree_iter iter;
-	struct bkey_s_c k;
 	struct bkey_s_c_subvolume subvol;
 	struct btree_trans_commit_hook *h;
 	u32 snapid;
 	int ret = 0;
 
-	bch2_trans_iter_init(trans, &iter, BTREE_ID_subvolumes,
-			     POS(0, subvolid),
-			     BTREE_ITER_CACHED|
-			     BTREE_ITER_INTENT);
-	k = bch2_btree_iter_peek_slot(&iter);
-	ret = bkey_err(k);
+	subvol = bch2_bkey_get_iter_typed(trans, &iter,
+				BTREE_ID_subvolumes, POS(0, subvolid),
+				BTREE_ITER_CACHED|BTREE_ITER_INTENT,
+				subvolume);
+	ret = bkey_err(subvol);
+	bch2_fs_inconsistent_on(ret == -ENOENT, trans->c, "missing subvolume %u", subvolid);
 	if (ret)
-		goto err;
-
-	if (k.k->type != KEY_TYPE_subvolume) {
-		bch2_fs_inconsistent(trans->c, "missing subvolume %u", subvolid);
-		ret = -EIO;
-		goto err;
-	}
+		return ret;
 
-	subvol = bkey_s_c_to_subvolume(k);
 	snapid = le32_to_cpu(subvol.v->snapshot);
 
 	ret = bch2_btree_delete_at(trans, &iter, 0);
@@ -869,6 +1303,13 @@ err:
 	return ret;
 }
 
+static int bch2_subvolume_delete(struct btree_trans *trans, u32 subvolid)
+{
+	return bch2_subvolumes_reparent(trans, subvolid) ?:
+		commit_do(trans, NULL, NULL, BTREE_INSERT_NOFAIL,
+			  __bch2_subvolume_delete(trans, subvolid));
+}
+
 void bch2_subvolume_wait_for_pagecache_and_delete(struct work_struct *work)
 {
 	struct bch_fs *c = container_of(work, struct bch_fs,
@@ -889,8 +1330,7 @@ void bch2_subvolume_wait_for_pagecache_and_delete(struct work_struct *work)
 		bch2_evict_subvolume_inodes(c, &s);
 
 		for (id = s.data; id < s.data + s.nr; id++) {
-			ret = bch2_trans_do(c, NULL, NULL, BTREE_INSERT_NOFAIL,
-				      bch2_subvolume_delete(&trans, *id));
+			ret = bch2_trans_run(c, bch2_subvolume_delete(&trans, *id));
 			if (ret) {
 				bch_err(c, "error deleting subvolume %u: %s", *id, bch2_err_str(ret));
 				break;
@@ -938,32 +1378,25 @@ int bch2_subvolume_unlink(struct btree_trans *trans, u32 subvolid)
 	struct subvolume_unlink_hook *h;
 	int ret = 0;
 
-	bch2_trans_iter_init(trans, &iter, BTREE_ID_subvolumes,
-			     POS(0, subvolid),
-			     BTREE_ITER_CACHED|
-			     BTREE_ITER_INTENT);
-	n = bch2_bkey_get_mut_typed(trans, &iter, subvolume);
-	ret = PTR_ERR_OR_ZERO(n);
-	if (unlikely(ret)) {
-		bch2_fs_inconsistent_on(ret == -ENOENT, trans->c, "missing subvolume %u", subvolid);
-		goto err;
-	}
-
-	SET_BCH_SUBVOLUME_UNLINKED(&n->v, true);
-
-	ret = bch2_trans_update(trans, &iter, &n->k_i, 0);
-	if (ret)
-		goto err;
-
 	h = bch2_trans_kmalloc(trans, sizeof(*h));
 	ret = PTR_ERR_OR_ZERO(h);
 	if (ret)
-		goto err;
+		return ret;
 
 	h->h.fn		= bch2_subvolume_wait_for_pagecache_and_delete_hook;
 	h->subvol	= subvolid;
 	bch2_trans_commit_hook(trans, &h->h);
-err:
+
+	n = bch2_bkey_get_mut_typed(trans, &iter,
+			BTREE_ID_subvolumes, POS(0, subvolid),
+			BTREE_ITER_CACHED, subvolume);
+	ret = PTR_ERR_OR_ZERO(n);
+	if (unlikely(ret)) {
+		bch2_fs_inconsistent_on(ret == -ENOENT, trans->c, "missing subvolume %u", subvolid);
+		return ret;
+	}
+
+	SET_BCH_SUBVOLUME_UNLINKED(&n->v, true);
 	bch2_trans_iter_exit(trans, &iter);
 	return ret;
 }
@@ -978,42 +1411,28 @@ int bch2_subvolume_create(struct btree_trans *trans, u64 inode,
 	struct btree_iter dst_iter, src_iter = (struct btree_iter) { NULL };
 	struct bkey_i_subvolume *new_subvol = NULL;
 	struct bkey_i_subvolume *src_subvol = NULL;
-	struct bkey_s_c k;
 	u32 parent = 0, new_nodes[2], snapshot_subvols[2];
 	int ret = 0;
 
-	for_each_btree_key(trans, dst_iter, BTREE_ID_subvolumes, SUBVOL_POS_MIN,
-			   BTREE_ITER_SLOTS|BTREE_ITER_INTENT, k, ret) {
-		if (bkey_gt(k.k->p, SUBVOL_POS_MAX))
-			break;
-
-		/*
-		 * bch2_subvolume_delete() doesn't flush the btree key cache -
-		 * ideally it would but that's tricky
-		 */
-		if (bkey_deleted(k.k) &&
-		    !bch2_btree_key_cache_find(c, BTREE_ID_subvolumes, dst_iter.pos))
-			goto found_slot;
-	}
-
-	if (!ret)
+	ret = bch2_bkey_get_empty_slot(trans, &dst_iter,
+				BTREE_ID_subvolumes, POS(0, U32_MAX));
+	if (ret == -BCH_ERR_ENOSPC_btree_slot)
 		ret = -BCH_ERR_ENOSPC_subvolume_create;
-	goto err;
-found_slot:
+	if (ret)
+		return ret;
+
 	snapshot_subvols[0] = dst_iter.pos.offset;
 	snapshot_subvols[1] = src_subvolid;
 
 	if (src_subvolid) {
 		/* Creating a snapshot: */
 
-		bch2_trans_iter_init(trans, &src_iter, BTREE_ID_subvolumes,
-				     POS(0, src_subvolid),
-				     BTREE_ITER_CACHED|
-				     BTREE_ITER_INTENT);
-		src_subvol = bch2_bkey_get_mut_typed(trans, &src_iter, subvolume);
+		src_subvol = bch2_bkey_get_mut_typed(trans, &src_iter,
+				BTREE_ID_subvolumes, POS(0, src_subvolid),
+				BTREE_ITER_CACHED, subvolume);
 		ret = PTR_ERR_OR_ZERO(src_subvol);
 		if (unlikely(ret)) {
-			bch2_fs_inconsistent_on(ret == -ENOENT, trans->c,
+			bch2_fs_inconsistent_on(ret == -ENOENT, c,
 						"subvolume %u not found", src_subvolid);
 			goto err;
 		}
@@ -1034,7 +1453,7 @@ found_slot:
 			goto err;
 	}
 
-	new_subvol = bch2_bkey_alloc(trans, &dst_iter, subvolume);
+	new_subvol = bch2_bkey_alloc(trans, &dst_iter, 0, subvolume);
 	ret = PTR_ERR_OR_ZERO(new_subvol);
 	if (ret)
 		goto err;
@@ -1042,11 +1461,12 @@ found_slot:
 	new_subvol->v.flags	= 0;
 	new_subvol->v.snapshot	= cpu_to_le32(new_nodes[0]);
 	new_subvol->v.inode	= cpu_to_le64(inode);
+	new_subvol->v.parent	= cpu_to_le32(src_subvolid);
+	new_subvol->v.otime.lo	= cpu_to_le64(bch2_current_time(c));
+	new_subvol->v.otime.hi	= 0;
+
 	SET_BCH_SUBVOLUME_RO(&new_subvol->v, ro);
 	SET_BCH_SUBVOLUME_SNAP(&new_subvol->v, src_subvolid != 0);
-	ret = bch2_trans_update(trans, &dst_iter, &new_subvol->k_i, 0);
-	if (ret)
-		goto err;
 
 	*new_subvolid	= new_subvol->k.p.offset;
 	*new_snapshotid	= new_nodes[0];
diff --git a/libbcachefs/subvolume.h b/libbcachefs/subvolume.h
index df665795..1a39f713 100644
--- a/libbcachefs/subvolume.h
+++ b/libbcachefs/subvolume.h
@@ -5,6 +5,18 @@
 #include "darray.h"
 #include "subvolume_types.h"
 
+void bch2_snapshot_tree_to_text(struct printbuf *, struct bch_fs *, struct bkey_s_c);
+int bch2_snapshot_tree_invalid(const struct bch_fs *, struct bkey_s_c,
+			       unsigned, struct printbuf *);
+
+#define bch2_bkey_ops_snapshot_tree ((struct bkey_ops) {	\
+	.key_invalid	= bch2_snapshot_tree_invalid,		\
+	.val_to_text	= bch2_snapshot_tree_to_text,		\
+	.min_val_size	= 8,					\
+})
+
+int bch2_snapshot_tree_lookup(struct btree_trans *, u32, struct bch_snapshot_tree *);
+
 void bch2_snapshot_to_text(struct printbuf *, struct bch_fs *, struct bkey_s_c);
 int bch2_snapshot_invalid(const struct bch_fs *, struct bkey_s_c,
 			  unsigned, struct printbuf *);
@@ -15,6 +27,7 @@ int bch2_mark_snapshot(struct btree_trans *, enum btree_id, unsigned,
 	.key_invalid	= bch2_snapshot_invalid,		\
 	.val_to_text	= bch2_snapshot_to_text,		\
 	.atomic_trigger	= bch2_mark_snapshot,			\
+	.min_val_size	= 24,					\
 })
 
 static inline struct snapshot_t *snapshot_t(struct bch_fs *c, u32 id)
@@ -27,6 +40,15 @@ static inline u32 bch2_snapshot_parent(struct bch_fs *c, u32 id)
 	return snapshot_t(c, id)->parent;
 }
 
+static inline u32 bch2_snapshot_root(struct bch_fs *c, u32 id)
+{
+	u32 parent;
+
+	while ((parent = bch2_snapshot_parent(c, id)))
+		id = parent;
+	return id;
+}
+
 static inline u32 bch2_snapshot_equiv(struct bch_fs *c, u32 id)
 {
 	return snapshot_t(c, id)->equiv;
@@ -106,6 +128,7 @@ static inline int snapshot_list_add(struct bch_fs *c, snapshot_id_list *s, u32 i
 	return ret;
 }
 
+int bch2_fs_check_snapshot_trees(struct bch_fs *);
 int bch2_fs_check_snapshots(struct bch_fs *);
 int bch2_fs_check_subvols(struct bch_fs *);
 
@@ -119,6 +142,7 @@ void bch2_subvolume_to_text(struct printbuf *, struct bch_fs *, struct bkey_s_c)
 #define bch2_bkey_ops_subvolume ((struct bkey_ops) {		\
 	.key_invalid	= bch2_subvolume_invalid,		\
 	.val_to_text	= bch2_subvolume_to_text,		\
+	.min_val_size	= 16,					\
 })
 
 int bch2_subvolume_get(struct btree_trans *, unsigned,
@@ -134,7 +158,6 @@ int bch2_snapshot_node_create(struct btree_trans *, u32,
 int bch2_delete_dead_snapshots(struct bch_fs *);
 void bch2_delete_dead_snapshots_async(struct bch_fs *);
 
-int bch2_subvolume_delete(struct btree_trans *, u32);
 int bch2_subvolume_unlink(struct btree_trans *, u32);
 int bch2_subvolume_create(struct btree_trans *, u64, u32,
 			  u32 *, u32 *, bool);
diff --git a/libbcachefs/subvolume_types.h b/libbcachefs/subvolume_types.h
index aa49c45a..c6c1cbad 100644
--- a/libbcachefs/subvolume_types.h
+++ b/libbcachefs/subvolume_types.h
@@ -10,6 +10,7 @@ struct snapshot_t {
 	u32			parent;
 	u32			children[2];
 	u32			subvol; /* Nonzero only if a subvolume points to this node: */
+	u32			tree;
 	u32			equiv;
 };
 
diff --git a/libbcachefs/super-io.c b/libbcachefs/super-io.c
index 519df099..5a15d649 100644
--- a/libbcachefs/super-io.c
+++ b/libbcachefs/super-io.c
@@ -16,14 +16,13 @@
 #include "quota.h"
 #include "super-io.h"
 #include "super.h"
+#include "trace.h"
 #include "vstructs.h"
 #include "counters.h"
 
 #include <linux/backing-dev.h>
 #include <linux/sort.h>
 
-#include <trace/events/bcachefs.h>
-
 const char * const bch2_sb_fields[] = {
 #define x(name, nr)	#name,
 	BCH_SB_FIELDS()
diff --git a/libbcachefs/super.c b/libbcachefs/super.c
index 066a72a2..696ea138 100644
--- a/libbcachefs/super.c
+++ b/libbcachefs/super.c
@@ -22,6 +22,7 @@
 #include "checksum.h"
 #include "clock.h"
 #include "compress.h"
+#include "counters.h"
 #include "debug.h"
 #include "disk_groups.h"
 #include "ec.h"
@@ -47,7 +48,7 @@
 #include "super.h"
 #include "super-io.h"
 #include "sysfs.h"
-#include "counters.h"
+#include "trace.h"
 
 #include <linux/backing-dev.h>
 #include <linux/blkdev.h>
@@ -60,8 +61,6 @@
 #include <linux/sysfs.h>
 #include <crypto/hash.h>
 
-#include <trace/events/bcachefs.h>
-
 MODULE_LICENSE("GPL");
 MODULE_AUTHOR("Kent Overstreet <kent.overstreet@gmail.com>");
 
diff --git a/libbcachefs/trace.c b/libbcachefs/trace.c
index 6813147d..d294b3d7 100644
--- a/libbcachefs/trace.c
+++ b/libbcachefs/trace.c
@@ -13,4 +13,4 @@
 #include <linux/six.h>
 
 #define CREATE_TRACE_POINTS
-#include <trace/events/bcachefs.h>
+#include "trace.h"
diff --git a/include/trace/events/bcachefs.h b/libbcachefs/trace.h
index e8cfae6b..8027c2a1 100644
--- a/include/trace/events/bcachefs.h
+++ b/libbcachefs/trace.h
@@ -2,8 +2,8 @@
 #undef TRACE_SYSTEM
 #define TRACE_SYSTEM bcachefs
 
-#if !defined(_TRACE_BCACHE_H) || defined(TRACE_HEADER_MULTI_READ)
-#define _TRACE_BCACHE_H
+#if !defined(_TRACE_BCACHEFS_H) || defined(TRACE_HEADER_MULTI_READ)
+#define _TRACE_BCACHEFS_H
 
 #include <linux/tracepoint.h>
 
@@ -663,7 +663,7 @@ TRACE_EVENT(bucket_invalidate,
 /* Moving IO */
 
 TRACE_EVENT(bucket_evacuate,
-	TP_PROTO(struct bch_fs *c, struct bpos bucket),
+	TP_PROTO(struct bch_fs *c, struct bpos *bucket),
 	TP_ARGS(c, bucket),
 
 	TP_STRUCT__entry(
@@ -674,8 +674,8 @@ TRACE_EVENT(bucket_evacuate,
 
 	TP_fast_assign(
 		__entry->dev		= c->dev;
-		__entry->dev_idx	= bucket.inode;
-		__entry->bucket		= bucket.offset;
+		__entry->dev_idx	= bucket->inode;
+		__entry->bucket		= bucket->offset;
 	),
 
 	TP_printk("%d:%d %u:%llu",
@@ -1250,7 +1250,13 @@ TRACE_EVENT(write_buffer_flush_slowpath,
 	TP_printk("%zu/%zu", __entry->nr, __entry->size)
 );
 
-#endif /* _TRACE_BCACHE_H */
+#endif /* _TRACE_BCACHEFS_H */
 
 /* This part must be outside protection */
+#undef TRACE_INCLUDE_PATH
+#define TRACE_INCLUDE_PATH ../../fs/bcachefs
+
+#undef TRACE_INCLUDE_FILE
+#define TRACE_INCLUDE_FILE trace
+
 #include <trace/define_trace.h>
diff --git a/libbcachefs/util.c b/libbcachefs/util.c
index c50473d4..dfc55fe4 100644
--- a/libbcachefs/util.c
+++ b/libbcachefs/util.c
@@ -761,10 +761,10 @@ void bch2_bio_map(struct bio *bio, void *base, size_t size)
 	}
 }
 
-int _bch2_bio_alloc_pages(struct bio *bio, size_t size, gfp_t gfp_mask)
+int bch2_bio_alloc_pages(struct bio *bio, size_t size, gfp_t gfp_mask)
 {
 	while (size) {
-		struct page *page = _alloc_pages(gfp_mask, 0);
+		struct page *page = alloc_pages(gfp_mask, 0);
 		unsigned len = min_t(size_t, PAGE_SIZE, size);
 
 		if (!page)
diff --git a/libbcachefs/util.h b/libbcachefs/util.h
index ecfe5401..9eb86c58 100644
--- a/libbcachefs/util.h
+++ b/libbcachefs/util.h
@@ -60,14 +60,12 @@ static inline void vpfree(void *p, size_t size)
 		free_pages((unsigned long) p, get_order(size));
 }
 
-static inline void *_vpmalloc(size_t size, gfp_t gfp_mask)
+static inline void *vpmalloc(size_t size, gfp_t gfp_mask)
 {
-	return (void *) _get_free_pages(gfp_mask|__GFP_NOWARN,
+	return (void *) __get_free_pages(gfp_mask|__GFP_NOWARN,
 					 get_order(size)) ?:
 		__vmalloc(size, gfp_mask);
 }
-#define vpmalloc(_size, _gfp)			\
-	alloc_hooks(_vpmalloc(_size, _gfp), void *, NULL)
 
 static inline void kvpfree(void *p, size_t size)
 {
@@ -77,14 +75,12 @@ static inline void kvpfree(void *p, size_t size)
 		vpfree(p, size);
 }
 
-static inline void *_kvpmalloc(size_t size, gfp_t gfp_mask)
+static inline void *kvpmalloc(size_t size, gfp_t gfp_mask)
 {
 	return size < PAGE_SIZE
-		? _kmalloc(size, gfp_mask)
-		: _vpmalloc(size, gfp_mask);
+		? kmalloc(size, gfp_mask)
+		: vpmalloc(size, gfp_mask);
 }
-#define kvpmalloc(_size, _gfp)			\
-	alloc_hooks(_kvpmalloc(_size, _gfp), void *, NULL)
 
 int mempool_init_kvpmalloc_pool(mempool_t *, int, size_t);
 
@@ -534,9 +530,7 @@ static inline unsigned fract_exp_two(unsigned x, unsigned fract_bits)
 }
 
 void bch2_bio_map(struct bio *bio, void *base, size_t);
-int _bch2_bio_alloc_pages(struct bio *, size_t, gfp_t);
-#define bch2_bio_alloc_pages(_bio, _size, _gfp)				\
-	alloc_hooks(_bch2_bio_alloc_pages(_bio, _size, _gfp), int, -ENOMEM)
+int bch2_bio_alloc_pages(struct bio *, size_t, gfp_t);
 
 static inline sector_t bdev_sectors(struct block_device *bdev)
 {
@@ -843,4 +837,11 @@ static inline int u8_cmp(u8 l, u8 r)
 	return cmp_int(l, r);
 }
 
+#include <linux/uuid.h>
+
+static inline int uuid_le_cmp(const uuid_le u1, const uuid_le u2)
+{
+	return memcmp(&u1, &u2, sizeof(uuid_le));
+}
+
 #endif /* _BCACHEFS_UTIL_H */
diff --git a/libbcachefs/xattr.c b/libbcachefs/xattr.c
index 9f77bb2e..4fc6e065 100644
--- a/libbcachefs/xattr.c
+++ b/libbcachefs/xattr.c
@@ -75,12 +75,6 @@ int bch2_xattr_invalid(const struct bch_fs *c, struct bkey_s_c k,
 	const struct xattr_handler *handler;
 	struct bkey_s_c_xattr xattr = bkey_s_c_to_xattr(k);
 
-	if (bkey_val_bytes(k.k) < sizeof(struct bch_xattr)) {
-		prt_printf(err, "incorrect value size (%zu < %zu)",
-		       bkey_val_bytes(k.k), sizeof(*xattr.v));
-		return -BCH_ERR_invalid_bkey;
-	}
-
 	if (bkey_val_u64s(k.k) <
 	    xattr_val_u64s(xattr.v->x_name_len,
 			   le16_to_cpu(xattr.v->x_val_len))) {
@@ -378,7 +372,7 @@ static int bch2_xattr_get_handler(const struct xattr_handler *handler,
 }
 
 static int bch2_xattr_set_handler(const struct xattr_handler *handler,
-				  struct user_namespace *mnt_userns,
+				  struct mnt_idmap *idmap,
 				  struct dentry *dentry, struct inode *vinode,
 				  const char *name, const void *value,
 				  size_t size, int flags)
@@ -517,7 +511,7 @@ static int inode_opt_set_fn(struct bch_inode_info *inode,
 }
 
 static int bch2_xattr_bcachefs_set(const struct xattr_handler *handler,
-				   struct user_namespace *mnt_userns,
+				   struct mnt_idmap *idmap,
 				   struct dentry *dentry, struct inode *vinode,
 				   const char *name, const void *value,
 				   size_t size, int flags)
diff --git a/libbcachefs/xattr.h b/libbcachefs/xattr.h
index 1a4cff3a..b3e16729 100644
--- a/libbcachefs/xattr.h
+++ b/libbcachefs/xattr.h
@@ -12,6 +12,7 @@ void bch2_xattr_to_text(struct printbuf *, struct bch_fs *, struct bkey_s_c);
 #define bch2_bkey_ops_xattr ((struct bkey_ops) {	\
 	.key_invalid	= bch2_xattr_invalid,		\
 	.val_to_text	= bch2_xattr_to_text,		\
+	.min_val_size	= 8,				\
 })
 
 static inline unsigned xattr_val_u64s(unsigned name_len, unsigned val_len)
diff --git a/rust-src/bch_bindgen/src/bkey.rs b/rust-src/bch_bindgen/src/bkey.rs
index 36106b5e..64697ea6 100644
--- a/rust-src/bch_bindgen/src/bkey.rs
+++ b/rust-src/bch_bindgen/src/bkey.rs
@@ -46,6 +46,7 @@ pub enum BkeyValC<'a> {
     backpointer(&'a c::bch_backpointer),
     inode_v3(&'a c::bch_inode_v3),
     bucket_gens(&'a c::bch_bucket_gens),
+    snapshot_tree(&'a c::bch_snapshot_tree),
 }
 
 impl<'a, 'b> BkeySC<'a> {
@@ -94,6 +95,7 @@ impl<'a, 'b> BkeySC<'a> {
             KEY_TYPE_backpointer            => backpointer(unsafe { transmute(self.v) }),
             KEY_TYPE_inode_v3               => inode_v3(unsafe { transmute(self.v) }),
             KEY_TYPE_bucket_gens            => bucket_gens(unsafe { transmute(self.v) }),
+            KEY_TYPE_snapshot_tree          => snapshot_tree(unsafe { transmute(self.v) }),
             KEY_TYPE_MAX                    => unreachable!(),
         }
     }