Quelle  snapshot.c   Sprache: C

// SPDX-License-Identifier: GPL-2.0

#include "bcachefs.h"
#include "bbpos.h"
#include "bkey_buf.h"
#include "btree_cache.h"
#include "btree_key_cache.h"
#include "btree_update.h"
#include "buckets.h"
#include "enumerated_ref.h"
#include "errcode.h"
#include "error.h"
#include "fs.h"
#include "recovery_passes.h"
#include "snapshot.h"

#include <linux/random.h>

/*
 * Snapshot trees:
 *
 * Keys in BTREE_ID_snapshot_trees identify a whole tree of snapshot nodes; they
 * exist to provide a stable identifier for the whole lifetime of a 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_validate(struct bch_fs *c, struct bkey_s_c k,
    struct bkey_validate_context from)
{
 int ret = 0;

 bkey_fsck_err_on(bkey_gt(k.k->p, POS(0, U32_MAX)) ||
    bkey_lt(k.k->p, POS(0, 1)),
    c, snapshot_tree_pos_bad,
    "bad pos");
fsck_err:
 return ret;
}

int bch2_snapshot_tree_lookup(struct btree_trans *trans, u32 id,
         struct bch_snapshot_tree *s)
{
 int ret = bch2_bkey_get_val_typed(trans, BTREE_ID_snapshot_trees, POS(0, id),
       BTREE_ITER_with_updates, snapshot_tree, s);

 if (bch2_err_matches(ret, ENOENT))
  ret = bch_err_throw(trans->c, ENOENT_snapshot_tree);
 return ret;
}

struct bkey_i_snapshot_tree *
__bch2_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_throw(trans->c, 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 bch2_snapshot_tree_create(struct btree_trans *trans,
    u32 root_id, u32 subvol_id, u32 *tree_id)
{
 struct bkey_i_snapshot_tree *n_tree =
  __bch2_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: */

static bool __bch2_snapshot_is_ancestor_early(struct snapshot_table *t, u32 id, u32 ancestor)
{
 while (id && id < ancestor) {
  const struct snapshot_t *s = __snapshot_t(t, id);
  id = s ? s->parent : 0;
 }
 return id == ancestor;
}

static bool bch2_snapshot_is_ancestor_early(struct bch_fs *c, u32 id, u32 ancestor)
{
 guard(rcu)();
 return __bch2_snapshot_is_ancestor_early(rcu_dereference(c->snapshots), 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);
 if (!s)
  return 0;

 if (s->skip[2] <= ancestor)
  return s->skip[2];
 if (s->skip[1] <= ancestor)
  return s->skip[1];
 if (s->skip[0] <= ancestor)
  return s->skip[0];
 return s->parent;
}

static bool test_ancestor_bitmap(struct snapshot_table *t, u32 id, u32 ancestor)
{
 const struct snapshot_t *s = __snapshot_t(t, id);
 if (!s)
  return false;

 return test_bit(ancestor - id - 1, s->is_ancestor);
}

bool __bch2_snapshot_is_ancestor(struct bch_fs *c, u32 id, u32 ancestor)
{
#ifdef CONFIG_BCACHEFS_DEBUG
 u32 orig_id = id;
#endif

 guard(rcu)();
 struct snapshot_table *t = rcu_dereference(c->snapshots);

 if (unlikely(c->recovery.pass_done < BCH_RECOVERY_PASS_check_snapshots))
  return __bch2_snapshot_is_ancestor_early(t, id, ancestor);

 if (likely(ancestor >= IS_ANCESTOR_BITMAP))
  while (id && id < ancestor - IS_ANCESTOR_BITMAP)
   id = get_ancestor_below(t, id, ancestor);

 bool ret = id && id < ancestor
  ? test_ancestor_bitmap(t, id, ancestor)
  : id == ancestor;

 EBUG_ON(ret != __bch2_snapshot_is_ancestor_early(t, orig_id, ancestor));
 return ret;
}

static noinline struct snapshot_t *__snapshot_t_mut(struct bch_fs *c, u32 id)
{
 size_t idx = U32_MAX - id;
 struct snapshot_table *new, *old;

 size_t new_bytes = kmalloc_size_roundup(struct_size(new, s, idx + 1));
 size_t new_size = (new_bytes - sizeof(*new)) / sizeof(new->s[0]);

 if (unlikely(new_bytes > INT_MAX))
  return NULL;

 new = kvzalloc(new_bytes, GFP_KERNEL);
 if (!new)
  return NULL;

 new->nr = new_size;

 old = rcu_dereference_protected(c->snapshots, true);
 if (old)
  memcpy(new->s, old->s, sizeof(old->s[0]) * old->nr);

 rcu_assign_pointer(c->snapshots, new);
 kvfree_rcu(old, rcu);

 return &rcu_dereference_protected(c->snapshots,
    lockdep_is_held(&c->snapshot_table_lock))->s[idx];
}

static inline struct snapshot_t *snapshot_t_mut(struct bch_fs *c, u32 id)
{
 size_t idx = U32_MAX - id;
 struct snapshot_table *table =
  rcu_dereference_protected(c->snapshots,
    lockdep_is_held(&c->snapshot_table_lock));

 lockdep_assert_held(&c->snapshot_table_lock);

 if (likely(table && idx < table->nr))
  return &table->s[idx];

 return __snapshot_t_mut(c, id);
}

void bch2_snapshot_to_text(struct printbuf *out, struct bch_fs *c,
      struct bkey_s_c k)
{
 struct bkey_s_c_snapshot s = bkey_s_c_to_snapshot(k);

 if (BCH_SNAPSHOT_SUBVOL(s.v))
  prt_str(out, "subvol ");
 if (BCH_SNAPSHOT_WILL_DELETE(s.v))
  prt_str(out, "will_delete ");
 if (BCH_SNAPSHOT_DELETED(s.v))
  prt_str(out, "deleted ");

 prt_printf(out, "parent %10u children %10u %10u subvol %u tree %u",
        le32_to_cpu(s.v->parent),
        le32_to_cpu(s.v->children[0]),
        le32_to_cpu(s.v->children[1]),
        le32_to_cpu(s.v->subvol),
        le32_to_cpu(s.v->tree));

 if (bkey_val_bytes(k.k) > offsetof(struct bch_snapshot, depth))
  prt_printf(out, " depth %u skiplist %u %u %u",
      le32_to_cpu(s.v->depth),
      le32_to_cpu(s.v->skip[0]),
      le32_to_cpu(s.v->skip[1]),
      le32_to_cpu(s.v->skip[2]));
}

int bch2_snapshot_validate(struct bch_fs *c, struct bkey_s_c k,
      struct bkey_validate_context from)
{
 struct bkey_s_c_snapshot s;
 u32 i, id;
 int ret = 0;

 bkey_fsck_err_on(bkey_gt(k.k->p, POS(0, U32_MAX)) ||
    bkey_lt(k.k->p, POS(0, 1)),
    c, snapshot_pos_bad,
    "bad pos");

 s = bkey_s_c_to_snapshot(k);

 id = le32_to_cpu(s.v->parent);
 bkey_fsck_err_on(id && id <= k.k->p.offset,
    c, snapshot_parent_bad,
    "bad parent node (%u <= %llu)",
    id, k.k->p.offset);

 bkey_fsck_err_on(le32_to_cpu(s.v->children[0]) < le32_to_cpu(s.v->children[1]),
    c, snapshot_children_not_normalized,
    "children not normalized");

 bkey_fsck_err_on(s.v->children[0] && s.v->children[0] == s.v->children[1],
    c, snapshot_child_duplicate,
    "duplicate child nodes");

 for (i = 0; i < 2; i++) {
  id = le32_to_cpu(s.v->children[i]);

  bkey_fsck_err_on(id >= k.k->p.offset,
     c, snapshot_child_bad,
     "bad child node (%u >= %llu)",
     id, k.k->p.offset);
 }

 if (bkey_val_bytes(k.k) > offsetof(struct bch_snapshot, skip)) {
  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, 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]);

   bkey_fsck_err_on(id && id < le32_to_cpu(s.v->parent),
      c, snapshot_skiplist_bad,
      "bad skiplist node %u", id);
  }
 }
fsck_err:
 return ret;
}

static int bch2_snapshot_table_make_room(struct bch_fs *c, u32 id)
{
 mutex_lock(&c->snapshot_table_lock);
 int ret = snapshot_t_mut(c, id)
  ? 0
  : bch_err_throw(c, ENOMEM_mark_snapshot);
 mutex_unlock(&c->snapshot_table_lock);
 return ret;
}

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,
         enum btree_iter_update_trigger_flags flags)
{
 struct bch_fs *c = trans->c;
 struct snapshot_t *t;
 u32 id = new.k->p.offset;
 int ret = 0;

 mutex_lock(&c->snapshot_table_lock);

 t = snapshot_t_mut(c, id);
 if (!t) {
  ret = bch_err_throw(c, ENOMEM_mark_snapshot);
  goto err;
 }

 if (new.k->type == KEY_TYPE_snapshot) {
  struct bkey_s_c_snapshot s = bkey_s_c_to_snapshot(new);

  t->state = !BCH_SNAPSHOT_DELETED(s.v)
   ? SNAPSHOT_ID_live
   : SNAPSHOT_ID_deleted;
  t->parent = le32_to_cpu(s.v->parent);
  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);

  if (bkey_val_bytes(s.k) > offsetof(struct bch_snapshot, depth)) {
   t->depth = le32_to_cpu(s.v->depth);
   t->skip[0] = le32_to_cpu(s.v->skip[0]);
   t->skip[1] = le32_to_cpu(s.v->skip[1]);
   t->skip[2] = le32_to_cpu(s.v->skip[2]);
  } else {
   t->depth = 0;
   t->skip[0] = 0;
   t->skip[1] = 0;
   t->skip[2] = 0;
  }

  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);

  if (BCH_SNAPSHOT_WILL_DELETE(s.v)) {
   set_bit(BCH_FS_need_delete_dead_snapshots, &c->flags);
   if (c->recovery.pass_done > BCH_RECOVERY_PASS_delete_dead_snapshots)
    bch2_delete_dead_snapshots_async(c);
  }
 } else {
  memset(t, 0, sizeof(*t));
 }
err:
 mutex_unlock(&c->snapshot_table_lock);
 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,
         enum btree_iter_update_trigger_flags 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)
{
 return bch2_bkey_get_val_typed(trans, BTREE_ID_snapshots, POS(0, id),
           BTREE_ITER_with_updates, snapshot, s);
}

/* 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;
}

u32 bch2_snapshot_oldest_subvol(struct bch_fs *c, u32 snapshot_root,
    snapshot_id_list *skip)
{
 guard(rcu)();
 u32 id, subvol = 0, s;
retry:
 id = snapshot_root;
 while (id && bch2_snapshot_exists(c, id)) {
  if (!(skip && snapshot_list_has_id(skip, id))) {
   s = snapshot_t(c, id)->subvol;

   if (s && (!subvol || s < subvol))
    subvol = s;
  }
  id = bch2_snapshot_tree_next(c, id);
  if (id == snapshot_root)
   break;
 }

 if (!subvol && skip) {
  skip = NULL;
  goto retry;
 }

 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;
 bool found = false;
 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;

  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)) {
   *subvol_id = s.k->p.offset;
   found = true;
   break;
  }
 }
 bch2_trans_iter_exit(trans, &iter);

 if (!ret && !found) {
  struct bkey_i_subvolume *u;

  *subvol_id = bch2_snapshot_oldest_subvol(c, snapshot_root, NULL);

  u = bch2_bkey_get_mut_typed(trans, &iter,
         BTREE_ID_subvolumes, POS(0, *subvol_id),
         0, subvolume);
  ret = PTR_ERR_OR_ZERO(u);
  if (ret)
   return ret;

  SET_BCH_SUBVOLUME_SNAP(&u->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;
 struct btree_iter snapshot_iter = {};
 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);

 struct bkey_s_c_snapshot snapshot_k =
  bch2_bkey_get_iter_typed(trans, &snapshot_iter, BTREE_ID_snapshots,
      POS(0, root_id), 0, snapshot);
 ret = bkey_err(snapshot_k);
 if (ret && !bch2_err_matches(ret, ENOENT))
  goto err;

 if (!ret)
  bkey_val_copy(&s, snapshot_k);

 if (fsck_err_on(ret ||
   root_id != bch2_snapshot_root(c, root_id) ||
   st.k->p.offset != le32_to_cpu(s.tree),
   trans, snapshot_tree_to_missing_snapshot,
   "snapshot tree points to missing/incorrect snapshot:\n%s",
   (bch2_bkey_val_to_text(&buf, c, st.s_c),
    prt_newline(&buf),
    ret
    ? prt_printf(&buf, "(%s)", bch2_err_str(ret))
    : bch2_bkey_val_to_text(&buf, c, snapshot_k.s_c),
    buf.buf))) {
  ret = bch2_btree_delete_at(trans, iter, 0);
  goto err;
 }

 if (!st.v->master_subvol)
  goto out;

 ret = bch2_subvolume_get(trans, le32_to_cpu(st.v->master_subvol), false, &subvol);
 if (ret && !bch2_err_matches(ret, ENOENT))
  goto err;

 if (fsck_err_on(ret,
   trans, 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(c,
      le32_to_cpu(subvol.snapshot),
      root_id),
   trans, 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),
   trans, 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))) {
  struct bkey_i_snapshot_tree *u;
  u32 subvol_id;

  ret = bch2_snapshot_tree_master_subvol(trans, root_id, &subvol_id);
  bch_err_fn(c, ret);

  if (bch2_err_matches(ret, ENOENT)) { /* nothing to be done here */
   ret = 0;
   goto err;
  }

  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);
 }
out:
err:
fsck_err:
 bch2_trans_iter_exit(trans, &snapshot_iter);
 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_check_snapshot_trees(struct bch_fs *c)
{
 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, BCH_TRANS_COMMIT_no_enospc,
  check_snapshot_tree(trans, &iter, k)));
 bch_err_fn(c, 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 (bch2_err_matches(ret, ENOENT))
  return 0;
 if (ret)
  return ret;

 return bch2_snapshot_is_ancestor_early(trans->c, snap_id, le32_to_cpu(s_t.root_snapshot));
}

u32 bch2_snapshot_skiplist_get(struct bch_fs *c, u32 id)
{
 if (!id)
  return 0;

 guard(rcu)();
 const struct snapshot_t *s = snapshot_t(c, id);
 return s->parent
  ? bch2_snapshot_nth_parent(c, id, get_random_u32_below(s->depth))
  : id;
}

static int snapshot_skiplist_good(struct btree_trans *trans, u32 id, struct bch_snapshot s)
{
 unsigned i;

 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;
}

/*
 * 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 k,
        struct bch_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, k.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 && !bch2_err_matches(ret, ENOENT))
  return ret;

 if (ret || 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) ?:
   bch2_snapshot_tree_create(trans, root_id,
    bch2_snapshot_oldest_subvol(c, root_id, NULL),
    &tree_id);
  if (ret)
   goto err;

  u->v.tree = cpu_to_le32(tree_id);
  if (k.k->p.offset == root_id)
   *s = u->v;
 }

 if (k.k->p.offset != root_id) {
  u = bch2_bkey_make_mut_typed(trans, iter, &k, 0, snapshot);
  ret = PTR_ERR_OR_ZERO(u);
  if (ret)
   goto err;

  u->v.tree = cpu_to_le32(tree_id);
  *s = u->v;
 }
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)
{
 struct bch_fs *c = trans->c;
 struct bch_snapshot s;
 struct bch_subvolume subvol;
 struct bch_snapshot v;
 struct bkey_i_snapshot *u;
 u32 parent_id = bch2_snapshot_parent_early(c, k.k->p.offset);
 u32 real_depth;
 struct printbuf buf = PRINTBUF;
 u32 i, id;
 int ret = 0;

 if (k.k->type != KEY_TYPE_snapshot)
  return 0;

 memset(&s, 0, sizeof(s));
 memcpy(&s, k.v, min(sizeof(s), bkey_val_bytes(k.k)));

 if (BCH_SNAPSHOT_DELETED(&s))
  return 0;

 id = le32_to_cpu(s.parent);
 if (id) {
  ret = bch2_snapshot_lookup(trans, id, &v);
  if (bch2_err_matches(ret, ENOENT))
   bch_err(c, "snapshot with nonexistent parent:\n %s",
    (bch2_bkey_val_to_text(&buf, c, k), buf.buf));
  if (ret)
   goto err;

  if (le32_to_cpu(v.children[0]) != k.k->p.offset &&
      le32_to_cpu(v.children[1]) != k.k->p.offset) {
   bch_err(c, "snapshot parent %u missing pointer to child %llu",
    id, k.k->p.offset);
   ret = -EINVAL;
   goto err;
  }
 }

 for (i = 0; i < 2 && s.children[i]; i++) {
  id = le32_to_cpu(s.children[i]);

  ret = bch2_snapshot_lookup(trans, id, &v);
  if (bch2_err_matches(ret, ENOENT))
   bch_err(c, "snapshot node %llu has nonexistent child %u",
    k.k->p.offset, id);
  if (ret)
   goto err;

  if (le32_to_cpu(v.parent) != k.k->p.offset) {
   bch_err(c, "snapshot child %u has wrong parent (got %u should be %llu)",
    id, le32_to_cpu(v.parent), k.k->p.offset);
   ret = -EINVAL;
   goto err;
  }
 }

 bool should_have_subvol = BCH_SNAPSHOT_SUBVOL(&s) &&
  !BCH_SNAPSHOT_WILL_DELETE(&s);

 if (should_have_subvol) {
  id = le32_to_cpu(s.subvol);
  ret = bch2_subvolume_get(trans, id, false, &subvol);
  if (bch2_err_matches(ret, ENOENT))
   bch_err(c, "snapshot points to nonexistent subvolume:\n %s",
    (bch2_bkey_val_to_text(&buf, c, k), buf.buf));
  if (ret)
   goto err;

  if (BCH_SNAPSHOT_SUBVOL(&s) != (le32_to_cpu(subvol.snapshot) == k.k->p.offset)) {
   bch_err(c, "snapshot node %llu has wrong BCH_SNAPSHOT_SUBVOL",
    k.k->p.offset);
   ret = -EINVAL;
   goto err;
  }
 } else {
  if (fsck_err_on(s.subvol,
    trans, 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);
   if (ret)
    goto err;

   u->v.subvol = 0;
   s = u->v;
  }
 }

 ret = snapshot_tree_ptr_good(trans, k.k->p.offset, le32_to_cpu(s.tree));
 if (ret < 0)
  goto err;

 if (fsck_err_on(!ret,
   trans, 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)
   goto err;
 }
 ret = 0;

 real_depth = bch2_snapshot_depth(c, parent_id);

 if (fsck_err_on(le32_to_cpu(s.depth) != real_depth,
   trans, 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)
   goto err;

  u->v.depth = cpu_to_le32(real_depth);
  s = u->v;
 }

 ret = snapshot_skiplist_good(trans, k.k->p.offset, s);
 if (ret < 0)
  goto err;

 if (fsck_err_on(!ret,
   trans, 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)
   goto err;

  for (i = 0; i < ARRAY_SIZE(u->v.skip); i++)
   u->v.skip[i] = cpu_to_le32(bch2_snapshot_skiplist_get(c, parent_id));

  bubble_sort(u->v.skip, ARRAY_SIZE(u->v.skip), cmp_le32);
  s = u->v;
 }
 ret = 0;
err:
fsck_err:
 printbuf_exit(&buf);
 return ret;
}

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;
}

static int check_snapshot_exists(struct btree_trans *trans, u32 id)
{
 struct bch_fs *c = trans->c;

 /* Do we need to reconstruct the snapshot_tree entry as well? */
 struct btree_iter iter;
 struct bkey_s_c k;
 int ret = 0;
 u32 tree_id = 0;

 for_each_btree_key_norestart(trans, iter, BTREE_ID_snapshot_trees, POS_MIN,
         0, k, ret) {
  if (k.k->type == KEY_TYPE_snapshot_tree &&
      le32_to_cpu(bkey_s_c_to_snapshot_tree(k).v->root_snapshot) == id) {
   tree_id = k.k->p.offset;
   break;
  }
 }
 bch2_trans_iter_exit(trans, &iter);

 if (ret)
  return ret;

 if (!tree_id) {
  ret = bch2_snapshot_tree_create(trans, id, 0, &tree_id);
  if (ret)
   return ret;
 }

 struct bkey_i_snapshot *snapshot = bch2_trans_kmalloc(trans, sizeof(*snapshot));
 ret = PTR_ERR_OR_ZERO(snapshot);
 if (ret)
  return ret;

 bkey_snapshot_init(&snapshot->k_i);
 snapshot->k.p  = POS(0, id);
 snapshot->v.tree = cpu_to_le32(tree_id);
 snapshot->v.btime.lo = cpu_to_le64(bch2_current_time(c));

 for_each_btree_key_norestart(trans, iter, BTREE_ID_subvolumes, POS_MIN,
         0, k, ret) {
  if (k.k->type == KEY_TYPE_subvolume &&
      le32_to_cpu(bkey_s_c_to_subvolume(k).v->snapshot) == id) {
   snapshot->v.subvol = cpu_to_le32(k.k->p.offset);
   SET_BCH_SNAPSHOT_SUBVOL(&snapshot->v, true);
   break;
  }
 }
 bch2_trans_iter_exit(trans, &iter);

 return  bch2_snapshot_table_make_room(c, id) ?:
  bch2_btree_insert_trans(trans, BTREE_ID_snapshots, &snapshot->k_i, 0);
}

/* Figure out which snapshot nodes belong in the same tree: */
struct snapshot_tree_reconstruct {
 enum btree_id   btree;
 struct bpos   cur_pos;
 snapshot_id_list  cur_ids;
 DARRAY(snapshot_id_list) trees;
};

static void snapshot_tree_reconstruct_exit(struct snapshot_tree_reconstruct *r)
{
 darray_for_each(r->trees, i)
  darray_exit(i);
 darray_exit(&r->trees);
 darray_exit(&r->cur_ids);
}

static inline bool same_snapshot(struct snapshot_tree_reconstruct *r, struct bpos pos)
{
 return r->btree == BTREE_ID_inodes
  ? r->cur_pos.offset == pos.offset
  : r->cur_pos.inode == pos.inode;
}

static inline bool snapshot_id_lists_have_common(snapshot_id_list *l, snapshot_id_list *r)
{
 return darray_find_p(*l, i, snapshot_list_has_id(r, *i)) != NULL;
}

static void snapshot_id_list_to_text(struct printbuf *out, snapshot_id_list *s)
{
 bool first = true;
 darray_for_each(*s, i) {
  if (!first)
   prt_char(out, ' ');
  first = false;
  prt_printf(out, "%u", *i);
 }
}

static int snapshot_tree_reconstruct_next(struct bch_fs *c, struct snapshot_tree_reconstruct *r)
{
 if (r->cur_ids.nr) {
  darray_for_each(r->trees, i)
   if (snapshot_id_lists_have_common(i, &r->cur_ids)) {
    int ret = snapshot_list_merge(c, i, &r->cur_ids);
    if (ret)
     return ret;
    goto out;
   }
  darray_push(&r->trees, r->cur_ids);
  darray_init(&r->cur_ids);
 }
out:
 r->cur_ids.nr = 0;
 return 0;
}

static int get_snapshot_trees(struct bch_fs *c, struct snapshot_tree_reconstruct *r, struct bpos pos)
{
 if (!same_snapshot(r, pos))
  snapshot_tree_reconstruct_next(c, r);
 r->cur_pos = pos;
 return snapshot_list_add_nodup(c, &r->cur_ids, pos.snapshot);
}

int bch2_reconstruct_snapshots(struct bch_fs *c)
{
 struct btree_trans *trans = bch2_trans_get(c);
 struct printbuf buf = PRINTBUF;
 struct snapshot_tree_reconstruct r = {};
 int ret = 0;

 for (unsigned btree = 0; btree < BTREE_ID_NR; btree++) {
  if (btree_type_has_snapshots(btree)) {
   r.btree = btree;

   ret = for_each_btree_key(trans, iter, btree, POS_MIN,
     BTREE_ITER_all_snapshots|BTREE_ITER_prefetch, k, ({
    get_snapshot_trees(c, &r, k.k->p);
   }));
   if (ret)
    goto err;

   snapshot_tree_reconstruct_next(c, &r);
  }
 }

 darray_for_each(r.trees, t) {
  printbuf_reset(&buf);
  snapshot_id_list_to_text(&buf, t);

  darray_for_each(*t, id) {
   if (fsck_err_on(bch2_snapshot_id_state(c, *id) == SNAPSHOT_ID_empty,
     trans, snapshot_node_missing,
     "snapshot node %u from tree %s missing, recreate?", *id, buf.buf)) {
    if (t->nr > 1) {
     bch_err(c, "cannot reconstruct snapshot trees with multiple nodes");
     ret = bch_err_throw(c, fsck_repair_unimplemented);
     goto err;
    }

    ret = commit_do(trans, NULL, NULL, BCH_TRANS_COMMIT_no_enospc,
      check_snapshot_exists(trans, *id));
    if (ret)
     goto err;
   }
  }
 }
fsck_err:
err:
 bch2_trans_put(trans);
 snapshot_tree_reconstruct_exit(&r);
 printbuf_exit(&buf);
 bch_err_fn(c, ret);
 return ret;
}

int __bch2_check_key_has_snapshot(struct btree_trans *trans,
      struct btree_iter *iter,
      struct bkey_s_c k)
{
 struct bch_fs *c = trans->c;
 struct printbuf buf = PRINTBUF;
 int ret = 0;
 enum snapshot_id_state state = bch2_snapshot_id_state(c, k.k->p.snapshot);

 /* Snapshot was definitively deleted, this error is marked autofix */
 if (fsck_err_on(state == SNAPSHOT_ID_deleted,
   trans, bkey_in_deleted_snapshot,
   "key in deleted snapshot %s, delete?",
   (bch2_btree_id_to_text(&buf, iter->btree_id),
    prt_char(&buf, ' '),
    bch2_bkey_val_to_text(&buf, c, k), buf.buf)))
  ret = bch2_btree_delete_at(trans, iter,
        BTREE_UPDATE_internal_snapshot_node) ?: 1;

 if (state == SNAPSHOT_ID_empty) {
  /*
 * Snapshot missing: we should have caught this with btree_lost_data and
 * kicked off reconstruct_snapshots, so if we end up here we have no
 * idea what happened.
 *
 * Do not delete unless we know that subvolumes and snapshots
 * are consistent:
 *
 * XXX:
 *
 * We could be smarter here, and instead of using the generic
 * recovery pass ratelimiting, track if there have been any
 * changes to the snapshots or inodes btrees since those passes
 * last ran.
 */
  ret = bch2_require_recovery_pass(c, &buf, BCH_RECOVERY_PASS_check_snapshots) ?: ret;
  ret = bch2_require_recovery_pass(c, &buf, BCH_RECOVERY_PASS_check_subvols) ?: ret;

  if (c->sb.btrees_lost_data & BIT_ULL(BTREE_ID_snapshots))
   ret = bch2_require_recovery_pass(c, &buf, BCH_RECOVERY_PASS_reconstruct_snapshots) ?: ret;

  unsigned repair_flags = FSCK_CAN_IGNORE | (!ret ? FSCK_CAN_FIX : 0);

  if (__fsck_err(trans, repair_flags, bkey_in_missing_snapshot,
        "key in missing snapshot %s, delete?",
        (bch2_btree_id_to_text(&buf, iter->btree_id),
         prt_char(&buf, ' '),
         bch2_bkey_val_to_text(&buf, c, k), buf.buf))) {
   ret = bch2_btree_delete_at(trans, iter,
         BTREE_UPDATE_internal_snapshot_node) ?: 1;
  }
 }
fsck_err:
 printbuf_exit(&buf);
 return ret;
}

int __bch2_get_snapshot_overwrites(struct btree_trans *trans,
       enum btree_id btree, struct bpos pos,
       snapshot_id_list *s)
{
 struct bch_fs *c = trans->c;
 struct btree_iter iter;
 struct bkey_s_c k;
 int ret = 0;

 for_each_btree_key_reverse_norestart(trans, iter, btree, bpos_predecessor(pos),
          BTREE_ITER_all_snapshots, k, ret) {
  if (!bkey_eq(k.k->p, pos))
   break;

  if (!bch2_snapshot_is_ancestor(c, k.k->p.snapshot, pos.snapshot) ||
      snapshot_list_has_ancestor(c, s, k.k->p.snapshot))
   continue;

  ret = snapshot_list_add(c, s, k.k->p.snapshot);
  if (ret)
   break;
 }
 bch2_trans_iter_exit(trans, &iter);
 if (ret)
  darray_exit(s);

 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 =
  bch2_bkey_get_mut_typed(trans, &iter,
        BTREE_ID_snapshots, POS(0, id),
        0, snapshot);
 int 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_WILL_DELETE(&s->v))
  goto err;

 SET_BCH_SNAPSHOT_WILL_DELETE(&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 c_iter = {};
 struct btree_iter tree_iter = {};
 u32 parent_id, child_id;
 unsigned i;
 int ret = 0;

 struct bkey_i_snapshot *s =
  bch2_bkey_get_mut_typed(trans, &iter, BTREE_ID_snapshots, POS(0, id),
     BTREE_ITER_intent, snapshot);
 ret = PTR_ERR_OR_ZERO(s);
 bch2_fs_inconsistent_on(bch2_err_matches(ret, ENOENT), c,
    "missing snapshot %u", id);

 if (ret)
  goto err;

 BUG_ON(BCH_SNAPSHOT_DELETED(&s->v));
 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);
  }
 }

 if (!bch2_request_incompat_feature(c, bcachefs_metadata_version_snapshot_deletion_v2)) {
  SET_BCH_SNAPSHOT_DELETED(&s->v, true);
  s->v.parent  = 0;
  s->v.children[0] = 0;
  s->v.children[1] = 0;
  s->v.subvol  = 0;
  s->v.tree  = 0;
  s->v.depth  = 0;
  s->v.skip[0]  = 0;
  s->v.skip[1]  = 0;
  s->v.skip[2]  = 0;
 } else {
  s->k.type = KEY_TYPE_deleted;
  set_bkey_val_u64s(&s->k, 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(trans, &iter);
 ret = bkey_err(k);
 if (ret)
  goto err;

 for (i = 0; i < nr_snapids; i++) {
  k = bch2_btree_iter_prev_slot(trans, &iter);
  ret = bkey_err(k);
  if (ret)
   goto err;

  if (!k.k || !k.k->p.offset) {
   ret = bch_err_throw(c, 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;
 }
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 inline u32 interior_delete_has_id(interior_delete_list *l, u32 id)
{
 struct snapshot_interior_delete *i = darray_find_p(*l, i, i->id == id);
 return i ? i->live_child : 0;
}

static unsigned __live_child(struct snapshot_table *t, u32 id,
        snapshot_id_list *delete_leaves,
        interior_delete_list *delete_interior)
{
 struct snapshot_t *s = __snapshot_t(t, id);
 if (!s)
  return 0;

 for (unsigned i = 0; i < ARRAY_SIZE(s->children); i++)
  if (s->children[i] &&
      !snapshot_list_has_id(delete_leaves, s->children[i]) &&
      !interior_delete_has_id(delete_interior, s->children[i]))
   return s->children[i];

 for (unsigned i = 0; i < ARRAY_SIZE(s->children); i++) {
  u32 live_child = s->children[i]
   ? __live_child(t, s->children[i], delete_leaves, delete_interior)
   : 0;
  if (live_child)
   return live_child;
 }

 return 0;
}

static unsigned live_child(struct bch_fs *c, u32 id)
{
 struct snapshot_delete *d = &c->snapshot_delete;

 guard(rcu)();
 return __live_child(rcu_dereference(c->snapshots), id,
       &d->delete_leaves, &d->delete_interior);
}

static bool snapshot_id_dying(struct snapshot_delete *d, unsigned id)
{
 return snapshot_list_has_id(&d->delete_leaves, id) ||
  interior_delete_has_id(&d->delete_interior, id) != 0;
}

static int delete_dead_snapshots_process_key(struct btree_trans *trans,
          struct btree_iter *iter,
          struct bkey_s_c k)
{
 struct snapshot_delete *d = &trans->c->snapshot_delete;

 if (snapshot_list_has_id(&d->delete_leaves, k.k->p.snapshot))
  return bch2_btree_delete_at(trans, iter,
         BTREE_UPDATE_internal_snapshot_node);

 u32 live_child = interior_delete_has_id(&d->delete_interior, k.k->p.snapshot);
 if (live_child) {
  struct bkey_i *new = bch2_bkey_make_mut_noupdate(trans, k);
  int ret = PTR_ERR_OR_ZERO(new);
  if (ret)
   return ret;

  new->k.p.snapshot = live_child;

  struct btree_iter dst_iter;
  struct bkey_s_c dst_k = bch2_bkey_get_iter(trans, &dst_iter,
          iter->btree_id, new->k.p,
          BTREE_ITER_all_snapshots|
          BTREE_ITER_intent);
  ret = bkey_err(dst_k);
  if (ret)
   return ret;

  ret =   (bkey_deleted(dst_k.k)
    ? bch2_trans_update(trans, &dst_iter, new,
          BTREE_UPDATE_internal_snapshot_node)
    : 0) ?:
   bch2_btree_delete_at(trans, iter,
          BTREE_UPDATE_internal_snapshot_node);
  bch2_trans_iter_exit(trans, &dst_iter);
  return ret;
 }

 return 0;
}

static bool skip_unrelated_snapshot_tree(struct btree_trans *trans, struct btree_iter *iter, u64 *prev_inum)
{
 struct bch_fs *c = trans->c;
 struct snapshot_delete *d = &c->snapshot_delete;

 u64 inum = iter->btree_id != BTREE_ID_inodes
  ? iter->pos.inode
  : iter->pos.offset;

 if (*prev_inum == inum)
  return false;

 *prev_inum = inum;

 bool ret = !snapshot_list_has_id(&d->deleting_from_trees,
      bch2_snapshot_tree(c, iter->pos.snapshot));
 if (unlikely(ret)) {
  struct bpos pos = iter->pos;
  pos.snapshot = 0;
  if (iter->btree_id != BTREE_ID_inodes)
   pos.offset = U64_MAX;
  bch2_btree_iter_set_pos(trans, iter, bpos_nosnap_successor(pos));
 }

 return ret;
}

static int delete_dead_snapshot_keys_v1(struct btree_trans *trans)
{
 struct bch_fs *c = trans->c;
 struct snapshot_delete *d = &c->snapshot_delete;

 for (d->pos.btree = 0; d->pos.btree < BTREE_ID_NR; d->pos.btree++) {
  struct disk_reservation res = { 0 };
  u64 prev_inum = 0;

  d->pos.pos = POS_MIN;

  if (!btree_type_has_snapshots(d->pos.btree))
   continue;

  int ret = for_each_btree_key_commit(trans, iter,
    d->pos.btree, POS_MIN,
    BTREE_ITER_prefetch|BTREE_ITER_all_snapshots, k,
    &res, NULL, BCH_TRANS_COMMIT_no_enospc, ({
   d->pos.pos = iter.pos;

   if (skip_unrelated_snapshot_tree(trans, &iter, &prev_inum))
    continue;

   delete_dead_snapshots_process_key(trans, &iter, k);
  }));

  bch2_disk_reservation_put(c, &res);

  if (ret)
   return ret;
 }

 return 0;
}

static int delete_dead_snapshot_keys_range(struct btree_trans *trans, enum btree_id btree,
        struct bpos start, struct bpos end)
{
 struct bch_fs *c = trans->c;
 struct snapshot_delete *d = &c->snapshot_delete;
 struct disk_reservation res = { 0 };

 d->pos.btree = btree;
 d->pos.pos = POS_MIN;

 int ret = for_each_btree_key_max_commit(trans, iter,
   btree, start, end,
   BTREE_ITER_prefetch|BTREE_ITER_all_snapshots, k,
   &res, NULL, BCH_TRANS_COMMIT_no_enospc, ({
  d->pos.pos = iter.pos;
  delete_dead_snapshots_process_key(trans, &iter, k);
 }));

 bch2_disk_reservation_put(c, &res);
 return ret;
}

static int delete_dead_snapshot_keys_v2(struct btree_trans *trans)
{
 struct bch_fs *c = trans->c;
 struct snapshot_delete *d = &c->snapshot_delete;
 struct disk_reservation res = { 0 };
 u64 prev_inum = 0;
 int ret = 0;

 struct btree_iter iter;
 bch2_trans_iter_init(trans, &iter, BTREE_ID_inodes, POS_MIN,
        BTREE_ITER_prefetch|BTREE_ITER_all_snapshots);

 while (1) {
  struct bkey_s_c k;
  ret = lockrestart_do(trans,
    bkey_err(k = bch2_btree_iter_peek(trans, &iter)));
  if (ret)
   break;

  if (!k.k)
   break;

  d->pos.btree = iter.btree_id;
  d->pos.pos = iter.pos;

  if (skip_unrelated_snapshot_tree(trans, &iter, &prev_inum))
   continue;

  if (snapshot_id_dying(d, k.k->p.snapshot)) {
   struct bpos start = POS(k.k->p.offset, 0);
   struct bpos end  = POS(k.k->p.offset, U64_MAX);

   ret   = delete_dead_snapshot_keys_range(trans, BTREE_ID_extents, start, end) ?:
    delete_dead_snapshot_keys_range(trans, BTREE_ID_dirents, start, end) ?:
    delete_dead_snapshot_keys_range(trans, BTREE_ID_xattrs, start, end);
   if (ret)
    break;

   bch2_btree_iter_set_pos(trans, &iter, POS(0, k.k->p.offset + 1));
  } else {
   bch2_btree_iter_advance(trans, &iter);
  }
 }
 bch2_trans_iter_exit(trans, &iter);

 if (ret)
  goto err;

 prev_inum = 0;
 ret = for_each_btree_key_commit(trans, iter,
   BTREE_ID_inodes, POS_MIN,
   BTREE_ITER_prefetch|BTREE_ITER_all_snapshots, k,
   &res, NULL, BCH_TRANS_COMMIT_no_enospc, ({
  d->pos.btree = iter.btree_id;
  d->pos.pos = iter.pos;

  if (skip_unrelated_snapshot_tree(trans, &iter, &prev_inum))
   continue;

  delete_dead_snapshots_process_key(trans, &iter, k);
 }));
err:
 bch2_disk_reservation_put(c, &res);
 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 check_should_delete_snapshot(struct btree_trans *trans, struct bkey_s_c k)
{
 if (k.k->type != KEY_TYPE_snapshot)
  return 0;

 struct bch_fs *c = trans->c;
 struct snapshot_delete *d = &c->snapshot_delete;
 struct bkey_s_c_snapshot s = bkey_s_c_to_snapshot(k);
 unsigned live_children = 0;
 int ret = 0;

 if (BCH_SNAPSHOT_SUBVOL(s.v))
  return 0;

 if (BCH_SNAPSHOT_DELETED(s.v))
  return 0;

 mutex_lock(&d->progress_lock);
 for (unsigned i = 0; i < 2; i++) {
  u32 child = le32_to_cpu(s.v->children[i]);

  live_children += child &&
   !snapshot_list_has_id(&d->delete_leaves, child);
 }

 u32 tree = bch2_snapshot_tree(c, s.k->p.offset);

 if (live_children == 0) {
  ret =   snapshot_list_add_nodup(c, &d->deleting_from_trees, tree) ?:
   snapshot_list_add(c, &d->delete_leaves, s.k->p.offset);
 } else if (live_children == 1) {
  struct snapshot_interior_delete n = {
   .id  = s.k->p.offset,
   .live_child = live_child(c, s.k->p.offset),
  };

  if (!n.live_child) {
   bch_err(c, "error finding live child of snapshot %u", n.id);
   ret = -EINVAL;
  } else {
   ret =   snapshot_list_add_nodup(c, &d->deleting_from_trees, tree) ?:
    darray_push(&d->delete_interior, n);
  }
 }
 mutex_unlock(&d->progress_lock);

 return ret;
}

static inline u32 bch2_snapshot_nth_parent_skip(struct bch_fs *c, u32 id, u32 n,
      interior_delete_list *skip)
{
 guard(rcu)();
 while (interior_delete_has_id(skip, id))
  id = __bch2_snapshot_parent(c, id);

 while (n--) {
  do {
   id = __bch2_snapshot_parent(c, id);
  } while (interior_delete_has_id(skip, id));
 }

 return id;
}

static int bch2_fix_child_of_deleted_snapshot(struct btree_trans *trans,
           struct btree_iter *iter, struct bkey_s_c k,
           interior_delete_list *deleted)
{
 struct bch_fs *c = trans->c;
 u32 nr_deleted_ancestors = 0;
 struct bkey_i_snapshot *s;
 int ret;

 if (!bch2_snapshot_exists(c, k.k->p.offset))
  return 0;

 if (k.k->type != KEY_TYPE_snapshot)
  return 0;

 if (interior_delete_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->id);

 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 (interior_delete_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);
}

static void bch2_snapshot_delete_nodes_to_text(struct printbuf *out, struct snapshot_delete *d)
{
 prt_printf(out, "deleting from trees");
 darray_for_each(d->deleting_from_trees, i)
  prt_printf(out, " %u", *i);

 prt_printf(out, "deleting leaves");
 darray_for_each(d->delete_leaves, i)
  prt_printf(out, " %u", *i);
 prt_newline(out);

 prt_printf(out, "interior");
 darray_for_each(d->delete_interior, i)
  prt_printf(out, " %u->%u", i->id, i->live_child);
 prt_newline(out);
}

int __bch2_delete_dead_snapshots(struct bch_fs *c)
{
 struct snapshot_delete *d = &c->snapshot_delete;
 int ret = 0;

 if (!mutex_trylock(&d->lock))
  return 0;

 if (!test_and_clear_bit(BCH_FS_need_delete_dead_snapshots, &c->flags))
  goto out_unlock;

 struct btree_trans *trans = bch2_trans_get(c);

 /*
 * For every snapshot node: If we have no live children and it's not
 * pointed to by a subvolume, delete it:
 */
 d->running = true;
 d->pos = BBPOS_MIN;

 ret = for_each_btree_key(trans, iter, BTREE_ID_snapshots, POS_MIN, 0, k,
  check_should_delete_snapshot(trans, k));
 if (!bch2_err_matches(ret, EROFS))
  bch_err_msg(c, ret, "walking snapshots");
 if (ret)
  goto err;

 if (!d->delete_leaves.nr && !d->delete_interior.nr)
  goto err;

 {
  struct printbuf buf = PRINTBUF;
  bch2_snapshot_delete_nodes_to_text(&buf, d);

  ret = commit_do(trans, NULL, NULL, 0, bch2_trans_log_msg(trans, &buf));
  printbuf_exit(&buf);
  if (ret)
   goto err;
 }

 ret = !bch2_request_incompat_feature(c, bcachefs_metadata_version_snapshot_deletion_v2)
  ? delete_dead_snapshot_keys_v2(trans)
  : delete_dead_snapshot_keys_v1(trans);
 if (!bch2_err_matches(ret, EROFS))
  bch_err_msg(c, ret, "deleting keys from dying snapshots");
 if (ret)
  goto err;

 darray_for_each(d->delete_leaves, i) {
  ret = commit_do(trans, NULL, NULL, 0,
   bch2_snapshot_node_delete(trans, *i));
  if (!bch2_err_matches(ret, EROFS))
   bch_err_msg(c, ret, "deleting snapshot %u", *i);
  if (ret)
   goto err;
 }

 /*
 * 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, &d->delete_interior));
 if (ret)
  goto err;

 darray_for_each(d->delete_interior, i) {
  ret = commit_do(trans, NULL, NULL, 0,
   bch2_snapshot_node_delete(trans, i->id));
  if (!bch2_err_matches(ret, EROFS))
   bch_err_msg(c, ret, "deleting snapshot %u", i->id);
  if (ret)
   goto err;
 }
err:
 mutex_lock(&d->progress_lock);
 darray_exit(&d->deleting_from_trees);
 darray_exit(&d->delete_interior);
 darray_exit(&d->delete_leaves);
 d->running = false;
 mutex_unlock(&d->progress_lock);
 bch2_trans_put(trans);

 bch2_recovery_pass_set_no_ratelimit(c, BCH_RECOVERY_PASS_check_snapshots);
out_unlock:
 mutex_unlock(&d->lock);
 if (!bch2_err_matches(ret, EROFS))
  bch_err_fn(c, ret);
 return ret;
}

int bch2_delete_dead_snapshots(struct bch_fs *c)
{
 if (!c->opts.auto_snapshot_deletion)
  return 0;

 return __bch2_delete_dead_snapshots(c);
}

void bch2_delete_dead_snapshots_work(struct work_struct *work)
{
 struct bch_fs *c = container_of(work, struct bch_fs, snapshot_delete.work);

 set_worker_desc("bcachefs-delete-dead-snapshots/%s", c->name);

 bch2_delete_dead_snapshots(c);
 enumerated_ref_put(&c->writes, BCH_WRITE_REF_delete_dead_snapshots);
}

void bch2_delete_dead_snapshots_async(struct bch_fs *c)
{
 if (!c->opts.auto_snapshot_deletion)
  return;

 if (!enumerated_ref_tryget(&c->writes, BCH_WRITE_REF_delete_dead_snapshots))
  return;

 BUG_ON(!test_bit(BCH_FS_may_go_rw, &c->flags));

 if (!queue_work(system_long_wq, &c->snapshot_delete.work))
  enumerated_ref_put(&c->writes, BCH_WRITE_REF_delete_dead_snapshots);
}

void bch2_snapshot_delete_status_to_text(struct printbuf *out, struct bch_fs *c)
{
 struct snapshot_delete *d = &c->snapshot_delete;

 if (!d->running) {
  prt_str(out, "(not running)");
  return;
 }

 mutex_lock(&d->progress_lock);
 bch2_snapshot_delete_nodes_to_text(out, d);

 bch2_bbpos_to_text(out, d->pos);
 mutex_unlock(&d->progress_lock);
}

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;

 for_each_btree_key_reverse_norestart(trans, iter, id, bpos_predecessor(pos),
          BTREE_ITER_not_extents|
          BTREE_ITER_all_snapshots,
          k, ret) {
  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 bool interior_snapshot_needs_delete(struct bkey_s_c_snapshot snap)
{
 /* If there's one child, it's redundant and keys will be moved to the child */
 return !!snap.v->children[0] + !!snap.v->children[1] == 1;
}

static int bch2_check_snapshot_needs_deletion(struct btree_trans *trans, struct bkey_s_c k)
{
 if (k.k->type != KEY_TYPE_snapshot)
  return 0;

 struct bkey_s_c_snapshot snap = bkey_s_c_to_snapshot(k);
 if (BCH_SNAPSHOT_WILL_DELETE(snap.v) ||
     interior_snapshot_needs_delete(snap))
  set_bit(BCH_FS_need_delete_dead_snapshots, &trans->c->flags);

 return 0;
}

int bch2_snapshots_read(struct bch_fs *c)
{
 /*
 * Initializing the is_ancestor bitmaps requires ancestors to already be
 * initialized - so mark in reverse:
 */
 int ret = bch2_trans_run(c,
  for_each_btree_key_reverse(trans, iter, BTREE_ID_snapshots,
       POS_MAX, 0, k,
   __bch2_mark_snapshot(trans, BTREE_ID_snapshots, 0, bkey_s_c_null, k, 0) ?:
   bch2_check_snapshot_needs_deletion(trans, k)));
 bch_err_fn(c, ret);

 /*
 * It's important that we check if we need to reconstruct snapshots
 * before going RW, so we mark that pass as required in the superblock -
 * otherwise, we could end up deleting keys with missing snapshot nodes
 * instead
 */
 BUG_ON(!test_bit(BCH_FS_new_fs, &c->flags) &&
        test_bit(BCH_FS_may_go_rw, &c->flags));

 return ret;
}

void bch2_fs_snapshots_exit(struct bch_fs *c)
{
 kvfree(rcu_dereference_protected(c->snapshots, true));
}

void bch2_fs_snapshots_init_early(struct bch_fs *c)
{
 INIT_WORK(&c->snapshot_delete.work, bch2_delete_dead_snapshots_work);
 mutex_init(&c->snapshot_delete.lock);
 mutex_init(&c->snapshot_delete.progress_lock);
 mutex_init(&c->snapshots_unlinked_lock);
}