]> git.sesse.net Git - bcachefs-tools-debian/blobdiff - libbcachefs/snapshot.c
Disable pristine-tar option in gbp.conf, since there is no pristine-tar branch.
[bcachefs-tools-debian] / libbcachefs / snapshot.c
index 824259178dab00ff2dfbfd665dc344340e3b6278..45f67e8b29eb67f188e5cfb32aa39e0b1ad1d625 100644 (file)
@@ -1,8 +1,10 @@
 // SPDX-License-Identifier: GPL-2.0
 
 #include "bcachefs.h"
+#include "bkey_buf.h"
 #include "btree_key_cache.h"
 #include "btree_update.h"
+#include "buckets.h"
 #include "errcode.h"
 #include "error.h"
 #include "fs.h"
@@ -28,17 +30,18 @@ void bch2_snapshot_tree_to_text(struct printbuf *out, struct bch_fs *c,
                   le32_to_cpu(t.v->root_snapshot));
 }
 
-int bch2_snapshot_tree_invalid(const struct bch_fs *c, struct bkey_s_c k,
+int bch2_snapshot_tree_invalid(struct bch_fs *c, struct bkey_s_c k,
                               enum bkey_invalid_flags 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;
-       }
+       int ret = 0;
 
-       return 0;
+       bkey_fsck_err_on(bkey_gt(k.k->p, POS(0, U32_MAX)) ||
+                        bkey_lt(k.k->p, POS(0, 1)), c, err,
+                        snapshot_tree_pos_bad,
+                        "bad pos");
+fsck_err:
+       return ret;
 }
 
 int bch2_snapshot_tree_lookup(struct btree_trans *trans, u32 id,
@@ -88,6 +91,20 @@ static int bch2_snapshot_tree_create(struct btree_trans *trans,
 
 /* Snapshot nodes: */
 
+static bool bch2_snapshot_is_ancestor_early(struct bch_fs *c, u32 id, u32 ancestor)
+{
+       struct snapshot_table *t;
+
+       rcu_read_lock();
+       t = rcu_dereference(c->snapshots);
+
+       while (id && id < ancestor)
+               id = __snapshot_t(t, id)->parent;
+       rcu_read_unlock();
+
+       return id == ancestor;
+}
+
 static inline u32 get_ancestor_below(struct snapshot_table *t, u32 id, u32 ancestor)
 {
        const struct snapshot_t *s = __snapshot_t(t, id);
@@ -106,7 +123,7 @@ bool __bch2_snapshot_is_ancestor(struct bch_fs *c, u32 id, u32 ancestor)
        struct snapshot_table *t;
        bool ret;
 
-       EBUG_ON(c->curr_recovery_pass <= BCH_RECOVERY_PASS_check_snapshots);
+       EBUG_ON(c->recovery_pass_done <= BCH_RECOVERY_PASS_check_snapshots);
 
        rcu_read_lock();
        t = rcu_dereference(c->snapshots);
@@ -114,26 +131,17 @@ bool __bch2_snapshot_is_ancestor(struct bch_fs *c, u32 id, u32 ancestor)
        while (id && id < ancestor - IS_ANCESTOR_BITMAP)
                id = get_ancestor_below(t, id, ancestor);
 
-       ret = id && id < ancestor
-               ? test_bit(ancestor - id - 1, __snapshot_t(t, id)->is_ancestor)
-               : id == ancestor;
-       rcu_read_unlock();
-
-       return ret;
-}
+       if (id && id < ancestor) {
+               ret = test_bit(ancestor - id - 1, __snapshot_t(t, id)->is_ancestor);
 
-static bool bch2_snapshot_is_ancestor_early(struct bch_fs *c, u32 id, u32 ancestor)
-{
-       struct snapshot_table *t;
-
-       rcu_read_lock();
-       t = rcu_dereference(c->snapshots);
+               EBUG_ON(ret != bch2_snapshot_is_ancestor_early(c, id, ancestor));
+       } else {
+               ret = id == ancestor;
+       }
 
-       while (id && id < ancestor)
-               id = __snapshot_t(t, id)->parent;
        rcu_read_unlock();
 
-       return id == ancestor;
+       return ret;
 }
 
 static noinline struct snapshot_t *__snapshot_t_mut(struct bch_fs *c, u32 id)
@@ -156,8 +164,7 @@ static noinline struct snapshot_t *__snapshot_t_mut(struct bch_fs *c, u32 id)
 
        rcu_assign_pointer(c->snapshots, new);
        c->snapshot_table_size = new_size;
-       if (old)
-               kvfree_rcu(old);
+       kvfree_rcu_mightsleep(old);
 
        return &rcu_dereference_protected(c->snapshots, true)->s[idx];
 }
@@ -196,72 +203,80 @@ void bch2_snapshot_to_text(struct printbuf *out, struct bch_fs *c,
                           le32_to_cpu(s.v->skip[2]));
 }
 
-int bch2_snapshot_invalid(const struct bch_fs *c, struct bkey_s_c k,
+int bch2_snapshot_invalid(struct bch_fs *c, struct bkey_s_c k,
                          enum bkey_invalid_flags flags,
                          struct printbuf *err)
 {
        struct bkey_s_c_snapshot s;
        u32 i, id;
+       int ret = 0;
 
-       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;
-       }
+       bkey_fsck_err_on(bkey_gt(k.k->p, POS(0, U32_MAX)) ||
+                        bkey_lt(k.k->p, POS(0, 1)), c, err,
+                        snapshot_pos_bad,
+                        "bad pos");
 
        s = bkey_s_c_to_snapshot(k);
 
        id = le32_to_cpu(s.v->parent);
-       if (id && id <= k.k->p.offset) {
-               prt_printf(err, "bad parent node (%u <= %llu)",
-                      id, k.k->p.offset);
-               return -BCH_ERR_invalid_bkey;
-       }
+       bkey_fsck_err_on(id && id <= k.k->p.offset, c, err,
+                        snapshot_parent_bad,
+                        "bad parent node (%u <= %llu)",
+                        id, k.k->p.offset);
 
-       if (le32_to_cpu(s.v->children[0]) < le32_to_cpu(s.v->children[1])) {
-               prt_printf(err, "children not normalized");
-               return -BCH_ERR_invalid_bkey;
-       }
+       bkey_fsck_err_on(le32_to_cpu(s.v->children[0]) < le32_to_cpu(s.v->children[1]), c, err,
+                        snapshot_children_not_normalized,
+                        "children not normalized");
 
-       if (s.v->children[0] &&
-           s.v->children[0] == s.v->children[1]) {
-               prt_printf(err, "duplicate child nodes");
-               return -BCH_ERR_invalid_bkey;
-       }
+       bkey_fsck_err_on(s.v->children[0] && s.v->children[0] == s.v->children[1], c, err,
+                        snapshot_child_duplicate,
+                        "duplicate child nodes");
 
        for (i = 0; i < 2; i++) {
                id = le32_to_cpu(s.v->children[i]);
 
-               if (id >= k.k->p.offset) {
-                       prt_printf(err, "bad child node (%u >= %llu)",
-                              id, k.k->p.offset);
-                       return -BCH_ERR_invalid_bkey;
-               }
+               bkey_fsck_err_on(id >= k.k->p.offset, c, err,
+                                snapshot_child_bad,
+                                "bad child node (%u >= %llu)",
+                                id, k.k->p.offset);
        }
 
        if (bkey_val_bytes(k.k) > offsetof(struct bch_snapshot, skip)) {
-               if (le32_to_cpu(s.v->skip[0]) > le32_to_cpu(s.v->skip[1]) ||
-                   le32_to_cpu(s.v->skip[1]) > le32_to_cpu(s.v->skip[2])) {
-                       prt_printf(err, "skiplist not normalized");
-                       return -BCH_ERR_invalid_bkey;
-               }
+               bkey_fsck_err_on(le32_to_cpu(s.v->skip[0]) > le32_to_cpu(s.v->skip[1]) ||
+                                le32_to_cpu(s.v->skip[1]) > le32_to_cpu(s.v->skip[2]), c, err,
+                                snapshot_skiplist_not_normalized,
+                                "skiplist not normalized");
 
                for (i = 0; i < ARRAY_SIZE(s.v->skip); i++) {
                        id = le32_to_cpu(s.v->skip[i]);
 
-                       if (!id != !s.v->parent ||
-                           (s.v->parent &&
-                            id <= k.k->p.offset)) {
-                               prt_printf(err, "bad skiplist node %u)", id);
-                               return -BCH_ERR_invalid_bkey;
-                       }
+                       bkey_fsck_err_on(id && id < le32_to_cpu(s.v->parent), c, err,
+                                        snapshot_skiplist_bad,
+                                        "bad skiplist node %u", id);
                }
        }
+fsck_err:
+       return ret;
+}
 
-       return 0;
+static void __set_is_ancestor_bitmap(struct bch_fs *c, u32 id)
+{
+       struct snapshot_t *t = snapshot_t_mut(c, id);
+       u32 parent = id;
+
+       while ((parent = bch2_snapshot_parent_early(c, parent)) &&
+              parent - id - 1 < IS_ANCESTOR_BITMAP)
+               __set_bit(parent - id - 1, t->is_ancestor);
 }
 
-int bch2_mark_snapshot(struct btree_trans *trans,
+static void set_is_ancestor_bitmap(struct bch_fs *c, u32 id)
+{
+       mutex_lock(&c->snapshot_table_lock);
+       __set_is_ancestor_bitmap(c, id);
+       mutex_unlock(&c->snapshot_table_lock);
+}
+
+static int __bch2_mark_snapshot(struct btree_trans *trans,
                       enum btree_id btree, unsigned level,
                       struct bkey_s_c old, struct bkey_s_c new,
                       unsigned flags)
@@ -281,7 +296,6 @@ int bch2_mark_snapshot(struct btree_trans *trans,
 
        if (new.k->type == KEY_TYPE_snapshot) {
                struct bkey_s_c_snapshot s = bkey_s_c_to_snapshot(new);
-               u32 parent = id;
 
                t->parent       = le32_to_cpu(s.v->parent);
                t->children[0]  = le32_to_cpu(s.v->children[0]);
@@ -301,13 +315,12 @@ int bch2_mark_snapshot(struct btree_trans *trans,
                        t->skip[2]      = 0;
                }
 
-               while ((parent = bch2_snapshot_parent_early(c, parent)) &&
-                      parent - id - 1 < IS_ANCESTOR_BITMAP)
-                       __set_bit(parent - id - 1, t->is_ancestor);
+               __set_is_ancestor_bitmap(c, id);
 
                if (BCH_SNAPSHOT_DELETED(s.v)) {
-                       set_bit(BCH_FS_HAVE_DELETED_SNAPSHOTS, &c->flags);
-                       c->recovery_passes_explicit |= BIT_ULL(BCH_RECOVERY_PASS_delete_dead_snapshots);
+                       set_bit(BCH_FS_need_delete_dead_snapshots, &c->flags);
+                       if (c->curr_recovery_pass > BCH_RECOVERY_PASS_delete_dead_snapshots)
+                               bch2_delete_dead_snapshots_async(c);
                }
        } else {
                memset(t, 0, sizeof(*t));
@@ -317,6 +330,14 @@ err:
        return ret;
 }
 
+int bch2_mark_snapshot(struct btree_trans *trans,
+                      enum btree_id btree, unsigned level,
+                      struct bkey_s_c old, struct bkey_s new,
+                      unsigned flags)
+{
+       return __bch2_mark_snapshot(trans, btree, level, old, new.s_c, flags);
+}
+
 int bch2_snapshot_lookup(struct btree_trans *trans, u32 id,
                         struct bch_snapshot *s)
 {
@@ -324,7 +345,7 @@ int bch2_snapshot_lookup(struct btree_trans *trans, u32 id,
                                       BTREE_ITER_WITH_UPDATES, snapshot, s);
 }
 
-int bch2_snapshot_live(struct btree_trans *trans, u32 id)
+static int bch2_snapshot_live(struct btree_trans *trans, u32 id)
 {
        struct bch_snapshot v;
        int ret;
@@ -351,7 +372,7 @@ int bch2_snapshot_live(struct btree_trans *trans, u32 id)
  * it's part of such a linear chain: this correctly sets equivalence classes on
  * startup if we run leaf to root (i.e. in natural key order).
  */
-int bch2_snapshot_set_equiv(struct btree_trans *trans, struct bkey_s_c k)
+static int bch2_snapshot_set_equiv(struct btree_trans *trans, struct bkey_s_c k)
 {
        struct bch_fs *c = trans->c;
        unsigned i, nr_live = 0, live_idx = 0;
@@ -446,7 +467,6 @@ static int bch2_snapshot_tree_master_subvol(struct btree_trans *trans,
        struct bch_fs *c = trans->c;
        struct btree_iter iter;
        struct bkey_s_c k;
-       struct bkey_s_c_subvolume s;
        bool found = false;
        int ret;
 
@@ -455,7 +475,7 @@ static int bch2_snapshot_tree_master_subvol(struct btree_trans *trans,
                if (k.k->type != KEY_TYPE_subvolume)
                        continue;
 
-               s = bkey_s_c_to_subvolume(k);
+               struct bkey_s_c_subvolume 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)) {
@@ -468,18 +488,18 @@ static int bch2_snapshot_tree_master_subvol(struct btree_trans *trans,
        bch2_trans_iter_exit(trans, &iter);
 
        if (!ret && !found) {
-               struct bkey_i_subvolume *s;
+               struct bkey_i_subvolume *u;
 
                *subvol_id = bch2_snapshot_tree_oldest_subvol(c, snapshot_root);
 
-               s = bch2_bkey_get_mut_typed(trans, &iter,
+               u = bch2_bkey_get_mut_typed(trans, &iter,
                                            BTREE_ID_subvolumes, POS(0, *subvol_id),
                                            0, subvolume);
-               ret = PTR_ERR_OR_ZERO(s);
+               ret = PTR_ERR_OR_ZERO(u);
                if (ret)
                        return ret;
 
-               SET_BCH_SUBVOLUME_SNAP(&s->v, false);
+               SET_BCH_SUBVOLUME_SNAP(&u->v, false);
        }
 
        return ret;
@@ -510,7 +530,7 @@ static int check_snapshot_tree(struct btree_trans *trans,
        if (fsck_err_on(ret ||
                        root_id != bch2_snapshot_root(c, root_id) ||
                        st.k->p.offset != le32_to_cpu(s.tree),
-                       c,
+                       c, snapshot_tree_to_missing_snapshot,
                        "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);
@@ -522,17 +542,20 @@ static int check_snapshot_tree(struct btree_trans *trans,
        if (ret && !bch2_err_matches(ret, ENOENT))
                goto err;
 
-       if (fsck_err_on(ret, c,
+       if (fsck_err_on(ret,
+                       c, snapshot_tree_to_missing_subvol,
                        "snapshot tree points to missing subvolume:\n  %s",
                        (printbuf_reset(&buf),
                         bch2_bkey_val_to_text(&buf, c, st.s_c), buf.buf)) ||
            fsck_err_on(!bch2_snapshot_is_ancestor_early(c,
                                                le32_to_cpu(subvol.snapshot),
-                                               root_id), c,
+                                               root_id),
+                       c, snapshot_tree_to_wrong_subvol,
                        "snapshot tree points to subvolume that does not point to snapshot in this tree:\n  %s",
                        (printbuf_reset(&buf),
                         bch2_bkey_val_to_text(&buf, c, st.s_c), buf.buf)) ||
-           fsck_err_on(BCH_SUBVOLUME_SNAP(&subvol), c,
+           fsck_err_on(BCH_SUBVOLUME_SNAP(&subvol),
+                       c, snapshot_tree_to_snapshot_subvol,
                        "snapshot tree points to snapshot subvolume:\n  %s",
                        (printbuf_reset(&buf),
                         bch2_bkey_val_to_text(&buf, c, st.s_c), buf.buf))) {
@@ -566,19 +589,13 @@ fsck_err:
  */
 int bch2_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,
+       int 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);
+                       NULL, NULL, BCH_TRANS_COMMIT_no_enospc,
+               check_snapshot_tree(trans, &iter, k)));
+       bch_err_fn(c, ret);
        return ret;
 }
 
@@ -616,28 +633,18 @@ u32 bch2_snapshot_skiplist_get(struct bch_fs *c, u32 id)
        return id;
 }
 
-static int snapshot_skiplist_good(struct btree_trans *trans, struct bch_snapshot s)
+static int snapshot_skiplist_good(struct btree_trans *trans, u32 id, struct bch_snapshot s)
 {
-       struct bch_snapshot a;
        unsigned i;
-       int ret;
-
-       for (i = 0; i < 3; i++) {
-               if (!s.parent != !s.skip[i])
-                       return false;
-
-               if (!s.parent)
-                       continue;
 
-               ret = bch2_snapshot_lookup(trans, le32_to_cpu(s.skip[i]), &a);
-               if (bch2_err_matches(ret, ENOENT))
-                       return false;
-               if (ret)
-                       return ret;
-
-               if (a.tree != s.tree)
-                       return false;
-       }
+       for (i = 0; i < 3; i++)
+               if (!s.parent) {
+                       if (s.skip[i])
+                               return false;
+               } else {
+                       if (!bch2_snapshot_is_ancestor_early(trans->c, id, le32_to_cpu(s.skip[i])))
+                               return false;
+               }
 
        return true;
 }
@@ -778,7 +785,9 @@ static int check_snapshot(struct btree_trans *trans,
                        goto err;
                }
        } else {
-               if (fsck_err_on(s.subvol, c, "snapshot should not point to subvol:\n  %s",
+               if (fsck_err_on(s.subvol,
+                               c, snapshot_should_not_have_subvol,
+                               "snapshot should not point to subvol:\n  %s",
                                (bch2_bkey_val_to_text(&buf, c, k), buf.buf))) {
                        u = bch2_bkey_make_mut_typed(trans, iter, &k, 0, snapshot);
                        ret = PTR_ERR_OR_ZERO(u);
@@ -794,7 +803,8 @@ static int check_snapshot(struct btree_trans *trans,
        if (ret < 0)
                goto err;
 
-       if (fsck_err_on(!ret, c, "snapshot points to missing/incorrect tree:\n  %s",
+       if (fsck_err_on(!ret, c, snapshot_to_bad_snapshot_tree,
+                       "snapshot points to missing/incorrect tree:\n  %s",
                        (bch2_bkey_val_to_text(&buf, c, k), buf.buf))) {
                ret = snapshot_tree_ptr_repair(trans, iter, k, &s);
                if (ret)
@@ -804,10 +814,10 @@ static int check_snapshot(struct btree_trans *trans,
 
        real_depth = bch2_snapshot_depth(c, parent_id);
 
-       if (le32_to_cpu(s.depth) != real_depth &&
-           (c->sb.version_upgrade_complete < bcachefs_metadata_version_snapshot_skiplists ||
-            fsck_err(c, "snapshot with incorrect depth field, should be %u:\n  %s",
-                     real_depth, (bch2_bkey_val_to_text(&buf, c, k), buf.buf)))) {
+       if (fsck_err_on(le32_to_cpu(s.depth) != real_depth,
+                       c, snapshot_bad_depth,
+                       "snapshot with incorrect depth field, should be %u:\n  %s",
+                       real_depth, (bch2_bkey_val_to_text(&buf, c, k), buf.buf))) {
                u = bch2_bkey_make_mut_typed(trans, iter, &k, 0, snapshot);
                ret = PTR_ERR_OR_ZERO(u);
                if (ret)
@@ -817,14 +827,13 @@ static int check_snapshot(struct btree_trans *trans,
                s = u->v;
        }
 
-       ret = snapshot_skiplist_good(trans, s);
+       ret = snapshot_skiplist_good(trans, k.k->p.offset, s);
        if (ret < 0)
                goto err;
 
-       if (!ret &&
-           (c->sb.version_upgrade_complete < bcachefs_metadata_version_snapshot_skiplists ||
-            fsck_err(c, "snapshot with bad skiplist field:\n  %s",
-                     (bch2_bkey_val_to_text(&buf, c, k), buf.buf)))) {
+       if (fsck_err_on(!ret, c, snapshot_bad_skiplist,
+                       "snapshot with bad skiplist field:\n  %s",
+                       (bch2_bkey_val_to_text(&buf, c, k), buf.buf))) {
                u = bch2_bkey_make_mut_typed(trans, iter, &k, 0, snapshot);
                ret = PTR_ERR_OR_ZERO(u);
                if (ret)
@@ -844,43 +853,835 @@ fsck_err:
 }
 
 int bch2_check_snapshots(struct bch_fs *c)
+{
+       /*
+        * We iterate backwards as checking/fixing the depth field requires that
+        * the parent's depth already be correct:
+        */
+       int ret = bch2_trans_run(c,
+               for_each_btree_key_reverse_commit(trans, iter,
+                               BTREE_ID_snapshots, POS_MAX,
+                               BTREE_ITER_PREFETCH, k,
+                               NULL, NULL, BCH_TRANS_COMMIT_no_enospc,
+                       check_snapshot(trans, &iter, k)));
+       bch_err_fn(c, ret);
+       return ret;
+}
+
+/*
+ * Mark a snapshot as deleted, for future cleanup:
+ */
+int bch2_snapshot_node_set_deleted(struct btree_trans *trans, u32 id)
 {
        struct btree_iter iter;
+       struct bkey_i_snapshot *s;
+       int ret = 0;
+
+       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(bch2_err_matches(ret, ENOENT),
+                                       trans->c, "missing snapshot %u", id);
+               return ret;
+       }
+
+       /* already deleted? */
+       if (BCH_SNAPSHOT_DELETED(&s->v))
+               goto err;
+
+       SET_BCH_SNAPSHOT_DELETED(&s->v, true);
+       SET_BCH_SNAPSHOT_SUBVOL(&s->v, false);
+       s->v.subvol = 0;
+err:
+       bch2_trans_iter_exit(trans, &iter);
+       return ret;
+}
+
+static inline void normalize_snapshot_child_pointers(struct bch_snapshot *s)
+{
+       if (le32_to_cpu(s->children[0]) < le32_to_cpu(s->children[1]))
+               swap(s->children[0], s->children[1]);
+}
+
+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 btree_iter c_iter = (struct btree_iter) { NULL };
+       struct btree_iter tree_iter = (struct btree_iter) { NULL };
+       struct bkey_s_c_snapshot s;
+       u32 parent_id, child_id;
+       unsigned i;
+       int ret = 0;
+
+       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(bch2_err_matches(ret, ENOENT), c,
+                               "missing snapshot %u", id);
+
+       if (ret)
+               goto err;
+
+       BUG_ON(s.v->children[1]);
+
+       parent_id = le32_to_cpu(s.v->parent);
+       child_id = le32_to_cpu(s.v->children[0]);
+
+       if (parent_id) {
+               struct bkey_i_snapshot *parent;
+
+               parent = bch2_bkey_get_mut_typed(trans, &p_iter,
+                                    BTREE_ID_snapshots, POS(0, parent_id),
+                                    0, snapshot);
+               ret = PTR_ERR_OR_ZERO(parent);
+               bch2_fs_inconsistent_on(bch2_err_matches(ret, ENOENT), c,
+                                       "missing snapshot %u", parent_id);
+               if (unlikely(ret))
+                       goto err;
+
+               /* find entry in parent->children for node being deleted */
+               for (i = 0; i < 2; i++)
+                       if (le32_to_cpu(parent->v.children[i]) == id)
+                               break;
+
+               if (bch2_fs_inconsistent_on(i == 2, c,
+                                       "snapshot %u missing child pointer to %u",
+                                       parent_id, id))
+                       goto err;
+
+               parent->v.children[i] = cpu_to_le32(child_id);
+
+               normalize_snapshot_child_pointers(&parent->v);
+       }
+
+       if (child_id) {
+               struct bkey_i_snapshot *child;
+
+               child = bch2_bkey_get_mut_typed(trans, &c_iter,
+                                    BTREE_ID_snapshots, POS(0, child_id),
+                                    0, snapshot);
+               ret = PTR_ERR_OR_ZERO(child);
+               bch2_fs_inconsistent_on(bch2_err_matches(ret, ENOENT), c,
+                                       "missing snapshot %u", child_id);
+               if (unlikely(ret))
+                       goto err;
+
+               child->v.parent = cpu_to_le32(parent_id);
+
+               if (!child->v.parent) {
+                       child->v.skip[0] = 0;
+                       child->v.skip[1] = 0;
+                       child->v.skip[2] = 0;
+               }
+       }
+
+       if (!parent_id) {
+               /*
+                * 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]);
+
+               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 = 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, &c_iter);
+       bch2_trans_iter_exit(trans, &iter);
+       return ret;
+}
+
+static int create_snapids(struct btree_trans *trans, u32 parent, u32 tree,
+                         u32 *new_snapids,
+                         u32 *snapshot_subvols,
+                         unsigned nr_snapids)
+{
+       struct bch_fs *c = trans->c;
+       struct btree_iter iter;
+       struct bkey_i_snapshot *n;
        struct bkey_s_c k;
+       unsigned i, j;
+       u32 depth = bch2_snapshot_depth(c, parent);
+       int ret;
+
+       bch2_trans_iter_init(trans, &iter, BTREE_ID_snapshots,
+                            POS_MIN, BTREE_ITER_INTENT);
+       k = bch2_btree_iter_peek(&iter);
+       ret = bkey_err(k);
+       if (ret)
+               goto err;
+
+       for (i = 0; i < nr_snapids; i++) {
+               k = bch2_btree_iter_prev_slot(&iter);
+               ret = bkey_err(k);
+               if (ret)
+                       goto err;
+
+               if (!k.k || !k.k->p.offset) {
+                       ret = -BCH_ERR_ENOSPC_snapshot_create;
+                       goto err;
+               }
+
+               n = bch2_bkey_alloc(trans, &iter, 0, snapshot);
+               ret = PTR_ERR_OR_ZERO(n);
+               if (ret)
+                       goto err;
+
+               n->v.flags      = 0;
+               n->v.parent     = cpu_to_le32(parent);
+               n->v.subvol     = cpu_to_le32(snapshot_subvols[i]);
+               n->v.tree       = cpu_to_le32(tree);
+               n->v.depth      = cpu_to_le32(depth);
+               n->v.btime.lo   = cpu_to_le64(bch2_current_time(c));
+               n->v.btime.hi   = 0;
+
+               for (j = 0; j < ARRAY_SIZE(n->v.skip); j++)
+                       n->v.skip[j] = cpu_to_le32(bch2_snapshot_skiplist_get(c, parent));
+
+               bubble_sort(n->v.skip, ARRAY_SIZE(n->v.skip), cmp_le32);
+               SET_BCH_SNAPSHOT_SUBVOL(&n->v, true);
+
+               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;
+
+               mutex_lock(&c->snapshot_table_lock);
+               snapshot_t_mut(c, new_snapids[i])->equiv = new_snapids[i];
+               mutex_unlock(&c->snapshot_table_lock);
+       }
+err:
+       bch2_trans_iter_exit(trans, &iter);
+       return ret;
+}
+
+/*
+ * 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;
+
+       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 (bch2_err_matches(ret, ENOENT))
+                       bch_err(trans->c, "snapshot %u not found", parent);
+               return ret;
+       }
+
+       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 = __bch2_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);
+
+}
+
+/*
+ * If we have an unlinked inode in an internal snapshot node, and the inode
+ * really has been deleted in all child snapshots, how does this get cleaned up?
+ *
+ * first there is the problem of how keys that have been overwritten in all
+ * child snapshots get deleted (unimplemented?), but inodes may perhaps be
+ * special?
+ *
+ * also: unlinked inode in internal snapshot appears to not be getting deleted
+ * correctly if inode doesn't exist in leaf snapshots
+ *
+ * solution:
+ *
+ * for a key in an interior snapshot node that needs work to be done that
+ * requires it to be mutated: iterate over all descendent leaf nodes and copy
+ * that key to snapshot leaf nodes, where we can mutate it
+ */
+
+static int snapshot_delete_key(struct btree_trans *trans,
+                              struct btree_iter *iter,
+                              struct bkey_s_c k,
+                              snapshot_id_list *deleted,
+                              snapshot_id_list *equiv_seen,
+                              struct bpos *last_pos)
+{
+       struct bch_fs *c = trans->c;
+       u32 equiv = bch2_snapshot_equiv(c, k.k->p.snapshot);
+
+       if (!bkey_eq(k.k->p, *last_pos))
+               equiv_seen->nr = 0;
+       *last_pos = k.k->p;
+
+       if (snapshot_list_has_id(deleted, k.k->p.snapshot) ||
+           snapshot_list_has_id(equiv_seen, equiv)) {
+               return bch2_btree_delete_at(trans, iter,
+                                           BTREE_UPDATE_INTERNAL_SNAPSHOT_NODE);
+       } else {
+               return snapshot_list_add(c, equiv_seen, equiv);
+       }
+}
+
+static int move_key_to_correct_snapshot(struct btree_trans *trans,
+                              struct btree_iter *iter,
+                              struct bkey_s_c k)
+{
+       struct bch_fs *c = trans->c;
+       u32 equiv = bch2_snapshot_equiv(c, k.k->p.snapshot);
+
+       /*
+        * When we have a linear chain of snapshot nodes, we consider
+        * those to form an equivalence class: we're going to collapse
+        * them all down to a single node, and keep the leaf-most node -
+        * which has the same id as the equivalence class id.
+        *
+        * If there are multiple keys in different snapshots at the same
+        * position, we're only going to keep the one in the newest
+        * snapshot - the rest have been overwritten and are redundant,
+        * and for the key we're going to keep we need to move it to the
+        * equivalance class ID if it's not there already.
+        */
+       if (equiv != k.k->p.snapshot) {
+               struct bkey_i *new = bch2_bkey_make_mut_noupdate(trans, k);
+               struct btree_iter new_iter;
+               int ret;
+
+               ret = PTR_ERR_OR_ZERO(new);
+               if (ret)
+                       return ret;
+
+               new->k.p.snapshot = equiv;
+
+               bch2_trans_iter_init(trans, &new_iter, iter->btree_id, new->k.p,
+                                    BTREE_ITER_ALL_SNAPSHOTS|
+                                    BTREE_ITER_CACHED|
+                                    BTREE_ITER_INTENT);
+
+               ret =   bch2_btree_iter_traverse(&new_iter) ?:
+                       bch2_trans_update(trans, &new_iter, new,
+                                       BTREE_UPDATE_INTERNAL_SNAPSHOT_NODE) ?:
+                       bch2_btree_delete_at(trans, iter,
+                                       BTREE_UPDATE_INTERNAL_SNAPSHOT_NODE);
+               bch2_trans_iter_exit(trans, &new_iter);
+               if (ret)
+                       return ret;
+       }
+
+       return 0;
+}
+
+static int bch2_snapshot_needs_delete(struct btree_trans *trans, struct bkey_s_c k)
+{
+       struct bkey_s_c_snapshot snap;
+       u32 children[2];
        int ret;
 
+       if (k.k->type != KEY_TYPE_snapshot)
+               return 0;
+
+       snap = bkey_s_c_to_snapshot(k);
+       if (BCH_SNAPSHOT_DELETED(snap.v) ||
+           BCH_SNAPSHOT_SUBVOL(snap.v))
+               return 0;
+
+       children[0] = le32_to_cpu(snap.v->children[0]);
+       children[1] = le32_to_cpu(snap.v->children[1]);
+
+       ret   = bch2_snapshot_live(trans, children[0]) ?:
+               bch2_snapshot_live(trans, children[1]);
+       if (ret < 0)
+               return ret;
+       return !ret;
+}
+
+/*
+ * For a given snapshot, if it doesn't have a subvolume that points to it, and
+ * it doesn't have child snapshot nodes - it's now redundant and we can mark it
+ * as deleted.
+ */
+static int bch2_delete_redundant_snapshot(struct btree_trans *trans, struct bkey_s_c k)
+{
+       int ret = bch2_snapshot_needs_delete(trans, k);
+
+       return ret <= 0
+               ? ret
+               : bch2_snapshot_node_set_deleted(trans, k.k->p.offset);
+}
+
+static inline u32 bch2_snapshot_nth_parent_skip(struct bch_fs *c, u32 id, u32 n,
+                                               snapshot_id_list *skip)
+{
+       rcu_read_lock();
+       while (snapshot_list_has_id(skip, id))
+               id = __bch2_snapshot_parent(c, id);
+
+       while (n--) {
+               do {
+                       id = __bch2_snapshot_parent(c, id);
+               } while (snapshot_list_has_id(skip, id));
+       }
+       rcu_read_unlock();
+
+       return id;
+}
+
+static int bch2_fix_child_of_deleted_snapshot(struct btree_trans *trans,
+                                             struct btree_iter *iter, struct bkey_s_c k,
+                                             snapshot_id_list *deleted)
+{
+       struct bch_fs *c = trans->c;
+       u32 nr_deleted_ancestors = 0;
+       struct bkey_i_snapshot *s;
+       int ret;
+
+       if (k.k->type != KEY_TYPE_snapshot)
+               return 0;
+
+       if (snapshot_list_has_id(deleted, k.k->p.offset))
+               return 0;
+
+       s = bch2_bkey_make_mut_noupdate_typed(trans, k, snapshot);
+       ret = PTR_ERR_OR_ZERO(s);
+       if (ret)
+               return ret;
+
+       darray_for_each(*deleted, i)
+               nr_deleted_ancestors += bch2_snapshot_is_ancestor(c, s->k.p.offset, *i);
+
+       if (!nr_deleted_ancestors)
+               return 0;
+
+       le32_add_cpu(&s->v.depth, -nr_deleted_ancestors);
+
+       if (!s->v.depth) {
+               s->v.skip[0] = 0;
+               s->v.skip[1] = 0;
+               s->v.skip[2] = 0;
+       } else {
+               u32 depth = le32_to_cpu(s->v.depth);
+               u32 parent = bch2_snapshot_parent(c, s->k.p.offset);
+
+               for (unsigned j = 0; j < ARRAY_SIZE(s->v.skip); j++) {
+                       u32 id = le32_to_cpu(s->v.skip[j]);
+
+                       if (snapshot_list_has_id(deleted, id)) {
+                               id = bch2_snapshot_nth_parent_skip(c,
+                                                       parent,
+                                                       depth > 1
+                                                       ? get_random_u32_below(depth - 1)
+                                                       : 0,
+                                                       deleted);
+                               s->v.skip[j] = cpu_to_le32(id);
+                       }
+               }
+
+               bubble_sort(s->v.skip, ARRAY_SIZE(s->v.skip), cmp_le32);
+       }
+
+       return bch2_trans_update(trans, iter, &s->k_i, 0);
+}
+
+int bch2_delete_dead_snapshots(struct bch_fs *c)
+{
+       struct btree_trans *trans;
+       snapshot_id_list deleted = { 0 };
+       snapshot_id_list deleted_interior = { 0 };
+       u32 id;
+       int ret = 0;
+
+       if (!test_and_clear_bit(BCH_FS_need_delete_dead_snapshots, &c->flags))
+               return 0;
+
+       if (!test_bit(BCH_FS_started, &c->flags)) {
+               ret = bch2_fs_read_write_early(c);
+               bch_err_msg(c, ret, "deleting dead snapshots: error going rw");
+               if (ret)
+                       return ret;
+       }
+
+       trans = bch2_trans_get(c);
+
        /*
-        * We iterate backwards as checking/fixing the depth field requires that
-        * the parent's depth already be correct:
+        * For every snapshot node: If we have no live children and it's not
+        * pointed to by a subvolume, delete it:
         */
-       ret = bch2_trans_run(c,
-               for_each_btree_key_reverse_commit(&trans, iter,
-                       BTREE_ID_snapshots, POS_MAX,
-                       BTREE_ITER_PREFETCH, k,
-                       NULL, NULL, BTREE_INSERT_LAZY_RW|BTREE_INSERT_NOFAIL,
-               check_snapshot(&trans, &iter, k)));
+       ret = for_each_btree_key_commit(trans, iter, BTREE_ID_snapshots,
+                       POS_MIN, 0, k,
+                       NULL, NULL, 0,
+               bch2_delete_redundant_snapshot(trans, k));
+       bch_err_msg(c, ret, "deleting redundant snapshots");
        if (ret)
-               bch_err_fn(c, ret);
+               goto err;
+
+       ret = for_each_btree_key(trans, iter, BTREE_ID_snapshots,
+                                POS_MIN, 0, k,
+               bch2_snapshot_set_equiv(trans, k));
+       bch_err_msg(c, ret, "in bch2_snapshots_set_equiv");
+       if (ret)
+               goto err;
+
+       ret = for_each_btree_key(trans, iter, BTREE_ID_snapshots,
+                                POS_MIN, 0, k, ({
+               if (k.k->type != KEY_TYPE_snapshot)
+                       continue;
+
+               BCH_SNAPSHOT_DELETED(bkey_s_c_to_snapshot(k).v)
+                       ? snapshot_list_add(c, &deleted, k.k->p.offset)
+                       : 0;
+       }));
+       bch_err_msg(c, ret, "walking snapshots");
+       if (ret)
+               goto err;
+
+       for (id = 0; id < BTREE_ID_NR; id++) {
+               struct bpos last_pos = POS_MIN;
+               snapshot_id_list equiv_seen = { 0 };
+               struct disk_reservation res = { 0 };
+
+               if (!btree_type_has_snapshots(id))
+                       continue;
+
+               /*
+                * deleted inodes btree is maintained by a trigger on the inodes
+                * btree - no work for us to do here, and it's not safe to scan
+                * it because we'll see out of date keys due to the btree write
+                * buffer:
+                */
+               if (id == BTREE_ID_deleted_inodes)
+                       continue;
+
+               ret = for_each_btree_key_commit(trans, iter,
+                               id, POS_MIN,
+                               BTREE_ITER_PREFETCH|BTREE_ITER_ALL_SNAPSHOTS, k,
+                               &res, NULL, BCH_TRANS_COMMIT_no_enospc,
+                       snapshot_delete_key(trans, &iter, k, &deleted, &equiv_seen, &last_pos)) ?:
+                     for_each_btree_key_commit(trans, iter,
+                               id, POS_MIN,
+                               BTREE_ITER_PREFETCH|BTREE_ITER_ALL_SNAPSHOTS, k,
+                               &res, NULL, BCH_TRANS_COMMIT_no_enospc,
+                       move_key_to_correct_snapshot(trans, &iter, k));
+
+               bch2_disk_reservation_put(c, &res);
+               darray_exit(&equiv_seen);
+
+               bch_err_msg(c, ret, "deleting keys from dying snapshots");
+               if (ret)
+                       goto err;
+       }
+
+       bch2_trans_unlock(trans);
+       down_write(&c->snapshot_create_lock);
+
+       ret = for_each_btree_key(trans, iter, BTREE_ID_snapshots,
+                                POS_MIN, 0, k, ({
+               u32 snapshot = k.k->p.offset;
+               u32 equiv = bch2_snapshot_equiv(c, snapshot);
+
+               equiv != snapshot
+                       ? snapshot_list_add(c, &deleted_interior, snapshot)
+                       : 0;
+       }));
+
+       bch_err_msg(c, ret, "walking snapshots");
+       if (ret)
+               goto err_create_lock;
+
+       /*
+        * Fixing children of deleted snapshots can't be done completely
+        * atomically, if we crash between here and when we delete the interior
+        * nodes some depth fields will be off:
+        */
+       ret = for_each_btree_key_commit(trans, iter, BTREE_ID_snapshots, POS_MIN,
+                                 BTREE_ITER_INTENT, k,
+                                 NULL, NULL, BCH_TRANS_COMMIT_no_enospc,
+               bch2_fix_child_of_deleted_snapshot(trans, &iter, k, &deleted_interior));
+       if (ret)
+               goto err_create_lock;
+
+       darray_for_each(deleted, i) {
+               ret = commit_do(trans, NULL, NULL, 0,
+                       bch2_snapshot_node_delete(trans, *i));
+               bch_err_msg(c, ret, "deleting snapshot %u", *i);
+               if (ret)
+                       goto err_create_lock;
+       }
+
+       darray_for_each(deleted_interior, i) {
+               ret = commit_do(trans, NULL, NULL, 0,
+                       bch2_snapshot_node_delete(trans, *i));
+               bch_err_msg(c, ret, "deleting snapshot %u", *i);
+               if (ret)
+                       goto err_create_lock;
+       }
+err_create_lock:
+       up_write(&c->snapshot_create_lock);
+err:
+       darray_exit(&deleted_interior);
+       darray_exit(&deleted);
+       bch2_trans_put(trans);
+       bch_err_fn(c, ret);
        return ret;
 }
 
-int bch2_snapshots_read(struct bch_fs *c)
+void bch2_delete_dead_snapshots_work(struct work_struct *work)
+{
+       struct bch_fs *c = container_of(work, struct bch_fs, snapshot_delete_work);
+
+       bch2_delete_dead_snapshots(c);
+       bch2_write_ref_put(c, BCH_WRITE_REF_delete_dead_snapshots);
+}
+
+void bch2_delete_dead_snapshots_async(struct bch_fs *c)
 {
+       if (bch2_write_ref_tryget(c, BCH_WRITE_REF_delete_dead_snapshots) &&
+           !queue_work(c->write_ref_wq, &c->snapshot_delete_work))
+               bch2_write_ref_put(c, BCH_WRITE_REF_delete_dead_snapshots);
+}
+
+int __bch2_key_has_snapshot_overwrites(struct btree_trans *trans,
+                                      enum btree_id id,
+                                      struct bpos pos)
+{
+       struct bch_fs *c = trans->c;
        struct btree_iter iter;
        struct bkey_s_c k;
-       int ret = 0;
+       int ret;
+
+       bch2_trans_iter_init(trans, &iter, id, pos,
+                            BTREE_ITER_NOT_EXTENTS|
+                            BTREE_ITER_ALL_SNAPSHOTS);
+       while (1) {
+               k = bch2_btree_iter_prev(&iter);
+               ret = bkey_err(k);
+               if (ret)
+                       break;
+
+               if (!k.k)
+                       break;
+
+               if (!bkey_eq(pos, k.k->p))
+                       break;
+
+               if (bch2_snapshot_is_ancestor(c, k.k->p.snapshot, pos.snapshot)) {
+                       ret = 1;
+                       break;
+               }
+       }
+       bch2_trans_iter_exit(trans, &iter);
+
+       return ret;
+}
+
+static u32 bch2_snapshot_smallest_child(struct bch_fs *c, u32 id)
+{
+       const struct snapshot_t *s = snapshot_t(c, id);
+
+       return s->children[1] ?: s->children[0];
+}
 
-       ret = bch2_trans_run(c,
-               for_each_btree_key2(&trans, iter, BTREE_ID_snapshots,
-                          POS_MIN, 0, k,
-                       bch2_mark_snapshot(&trans, BTREE_ID_snapshots, 0, bkey_s_c_null, k, 0) ?:
-                       bch2_snapshot_set_equiv(&trans, k)));
+static u32 bch2_snapshot_smallest_descendent(struct bch_fs *c, u32 id)
+{
+       u32 child;
+
+       while ((child = bch2_snapshot_smallest_child(c, id)))
+               id = child;
+       return id;
+}
+
+static int bch2_propagate_key_to_snapshot_leaf(struct btree_trans *trans,
+                                              enum btree_id btree,
+                                              struct bkey_s_c interior_k,
+                                              u32 leaf_id, struct bpos *new_min_pos)
+{
+       struct btree_iter iter;
+       struct bpos pos = interior_k.k->p;
+       struct bkey_s_c k;
+       struct bkey_i *new;
+       int ret;
+
+       pos.snapshot = leaf_id;
+
+       bch2_trans_iter_init(trans, &iter, btree, pos, BTREE_ITER_INTENT);
+       k = bch2_btree_iter_peek_slot(&iter);
+       ret = bkey_err(k);
        if (ret)
-               bch_err_fn(c, ret);
+               goto out;
+
+       /* key already overwritten in this snapshot? */
+       if (k.k->p.snapshot != interior_k.k->p.snapshot)
+               goto out;
+
+       if (bpos_eq(*new_min_pos, POS_MIN)) {
+               *new_min_pos = k.k->p;
+               new_min_pos->snapshot = leaf_id;
+       }
+
+       new = bch2_bkey_make_mut_noupdate(trans, interior_k);
+       ret = PTR_ERR_OR_ZERO(new);
+       if (ret)
+               goto out;
+
+       new->k.p.snapshot = leaf_id;
+       ret = bch2_trans_update(trans, &iter, new, 0);
+out:
+       bch2_trans_iter_exit(trans, &iter);
+       return ret;
+}
+
+int bch2_propagate_key_to_snapshot_leaves(struct btree_trans *trans,
+                                         enum btree_id btree,
+                                         struct bkey_s_c k,
+                                         struct bpos *new_min_pos)
+{
+       struct bch_fs *c = trans->c;
+       struct bkey_buf sk;
+       u32 restart_count = trans->restart_count;
+       int ret = 0;
+
+       bch2_bkey_buf_init(&sk);
+       bch2_bkey_buf_reassemble(&sk, c, k);
+       k = bkey_i_to_s_c(sk.k);
+
+       *new_min_pos = POS_MIN;
+
+       for (u32 id = bch2_snapshot_smallest_descendent(c, k.k->p.snapshot);
+            id < k.k->p.snapshot;
+            id++) {
+               if (!bch2_snapshot_is_ancestor(c, id, k.k->p.snapshot) ||
+                   !bch2_snapshot_is_leaf(c, id))
+                       continue;
+again:
+               ret =   btree_trans_too_many_iters(trans) ?:
+                       bch2_propagate_key_to_snapshot_leaf(trans, btree, k, id, new_min_pos) ?:
+                       bch2_trans_commit(trans, NULL, NULL, 0);
+               if (ret && bch2_err_matches(ret, BCH_ERR_transaction_restart)) {
+                       bch2_trans_begin(trans);
+                       goto again;
+               }
+
+               if (ret)
+                       break;
+       }
+
+       bch2_bkey_buf_exit(&sk, c);
+
+       return ret ?: trans_was_restarted(trans, restart_count);
+}
+
+static int bch2_check_snapshot_needs_deletion(struct btree_trans *trans, struct bkey_s_c k)
+{
+       struct bch_fs *c = trans->c;
+       struct bkey_s_c_snapshot snap;
+       int ret = 0;
+
+       if (k.k->type != KEY_TYPE_snapshot)
+               return 0;
+
+       snap = bkey_s_c_to_snapshot(k);
+       if (BCH_SNAPSHOT_DELETED(snap.v) ||
+           bch2_snapshot_equiv(c, k.k->p.offset) != k.k->p.offset ||
+           (ret = bch2_snapshot_needs_delete(trans, k)) > 0) {
+               set_bit(BCH_FS_need_delete_dead_snapshots, &c->flags);
+               return 0;
+       }
+
+       return ret;
+}
+
+int bch2_snapshots_read(struct bch_fs *c)
+{
+       int ret = bch2_trans_run(c,
+               for_each_btree_key(trans, iter, BTREE_ID_snapshots,
+                                  POS_MIN, 0, k,
+                       __bch2_mark_snapshot(trans, BTREE_ID_snapshots, 0, bkey_s_c_null, k, 0) ?:
+                       bch2_snapshot_set_equiv(trans, k) ?:
+                       bch2_check_snapshot_needs_deletion(trans, k)) ?:
+               for_each_btree_key(trans, iter, BTREE_ID_snapshots,
+                                  POS_MIN, 0, k,
+                          (set_is_ancestor_bitmap(c, k.k->p.offset), 0)));
+       bch_err_fn(c, ret);
        return ret;
 }
 
 void bch2_fs_snapshots_exit(struct bch_fs *c)
 {
-       kfree(rcu_dereference_protected(c->snapshots, true));
+       kvfree(rcu_dereference_protected(c->snapshots, true));
 }