fs/bcachefs/snapshot.c

   1 // SPDX-License-Identifier: GPL-2.0
   2
   3 #include "bcachefs.h"
   4 #include "bkey_buf.h"
   5 #include "btree_key_cache.h"
   6 #include "btree_update.h"
   7 #include "buckets.h"
   8 #include "errcode.h"
   9 #include "error.h"
  10 #include "fs.h"
  11 #include "recovery_passes.h"
  12 #include "snapshot.h"
  13
  14 #include <linux/random.h>
  15
  16 /*
  17  * Snapshot trees:
  18  *
  19  * Keys in BTREE_ID_snapshot_trees identify a whole tree of snapshot nodes; they
  20  * exist to provide a stable identifier for the whole lifetime of a snapshot
  21  * tree.
  22  */
  23
  24 void bch2_snapshot_tree_to_text(struct printbuf *out, struct bch_fs *c,
  25                                 struct bkey_s_c k)
  26 {
  27         struct bkey_s_c_snapshot_tree t = bkey_s_c_to_snapshot_tree(k);
  28
  29         prt_printf(out, "subvol %u root snapshot %u",
  30                    le32_to_cpu(t.v->master_subvol),
  31                    le32_to_cpu(t.v->root_snapshot));
  32 }
  33
  34 int bch2_snapshot_tree_validate(struct bch_fs *c, struct bkey_s_c k,
  35                                enum bch_validate_flags flags)
  36 {
  37         int ret = 0;
  38
  39         bkey_fsck_err_on(bkey_gt(k.k->p, POS(0, U32_MAX)) ||
  40                          bkey_lt(k.k->p, POS(0, 1)),
  41                          c, snapshot_tree_pos_bad,
  42                          "bad pos");
  43 fsck_err:
  44         return ret;
  45 }
  46
  47 int bch2_snapshot_tree_lookup(struct btree_trans *trans, u32 id,
  48                               struct bch_snapshot_tree *s)
  49 {
  50         int ret = bch2_bkey_get_val_typed(trans, BTREE_ID_snapshot_trees, POS(0, id),
  51                                           BTREE_ITER_with_updates, snapshot_tree, s);
  52
  53         if (bch2_err_matches(ret, ENOENT))
  54                 ret = -BCH_ERR_ENOENT_snapshot_tree;
  55         return ret;
  56 }
  57
  58 struct bkey_i_snapshot_tree *
  59 __bch2_snapshot_tree_create(struct btree_trans *trans)
  60 {
  61         struct btree_iter iter;
  62         int ret = bch2_bkey_get_empty_slot(trans, &iter,
  63                         BTREE_ID_snapshot_trees, POS(0, U32_MAX));
  64         struct bkey_i_snapshot_tree *s_t;
  65
  66         if (ret == -BCH_ERR_ENOSPC_btree_slot)
  67                 ret = -BCH_ERR_ENOSPC_snapshot_tree;
  68         if (ret)
  69                 return ERR_PTR(ret);
  70
  71         s_t = bch2_bkey_alloc(trans, &iter, 0, snapshot_tree);
  72         ret = PTR_ERR_OR_ZERO(s_t);
  73         bch2_trans_iter_exit(trans, &iter);
  74         return ret ? ERR_PTR(ret) : s_t;
  75 }
  76
  77 static int bch2_snapshot_tree_create(struct btree_trans *trans,
  78                                 u32 root_id, u32 subvol_id, u32 *tree_id)
  79 {
  80         struct bkey_i_snapshot_tree *n_tree =
  81                 __bch2_snapshot_tree_create(trans);
  82
  83         if (IS_ERR(n_tree))
  84                 return PTR_ERR(n_tree);
  85
  86         n_tree->v.master_subvol = cpu_to_le32(subvol_id);
  87         n_tree->v.root_snapshot = cpu_to_le32(root_id);
  88         *tree_id = n_tree->k.p.offset;
  89         return 0;
  90 }
  91
  92 /* Snapshot nodes: */
  93
  94 static bool __bch2_snapshot_is_ancestor_early(struct snapshot_table *t, u32 id, u32 ancestor)
  95 {
  96         while (id && id < ancestor) {
  97                 const struct snapshot_t *s = __snapshot_t(t, id);
  98                 id = s ? s->parent : 0;
  99         }
 100         return id == ancestor;
 101 }
 102
 103 static bool bch2_snapshot_is_ancestor_early(struct bch_fs *c, u32 id, u32 ancestor)
 104 {
 105         rcu_read_lock();
 106         bool ret = __bch2_snapshot_is_ancestor_early(rcu_dereference(c->snapshots), id, ancestor);
 107         rcu_read_unlock();
 108
 109         return ret;
 110 }
 111
 112 static inline u32 get_ancestor_below(struct snapshot_table *t, u32 id, u32 ancestor)
 113 {
 114         const struct snapshot_t *s = __snapshot_t(t, id);
 115         if (!s)
 116                 return 0;
 117
 118         if (s->skip[2] <= ancestor)
 119                 return s->skip[2];
 120         if (s->skip[1] <= ancestor)
 121                 return s->skip[1];
 122         if (s->skip[0] <= ancestor)
 123                 return s->skip[0];
 124         return s->parent;
 125 }
 126
 127 static bool test_ancestor_bitmap(struct snapshot_table *t, u32 id, u32 ancestor)
 128 {
 129         const struct snapshot_t *s = __snapshot_t(t, id);
 130         if (!s)
 131                 return false;
 132
 133         return test_bit(ancestor - id - 1, s->is_ancestor);
 134 }
 135
 136 bool __bch2_snapshot_is_ancestor(struct bch_fs *c, u32 id, u32 ancestor)
 137 {
 138         bool ret;
 139
 140         rcu_read_lock();
 141         struct snapshot_table *t = rcu_dereference(c->snapshots);
 142
 143         if (unlikely(c->recovery_pass_done < BCH_RECOVERY_PASS_check_snapshots)) {
 144                 ret = __bch2_snapshot_is_ancestor_early(t, id, ancestor);
 145                 goto out;
 146         }
 147
 148         while (id && id < ancestor - IS_ANCESTOR_BITMAP)
 149                 id = get_ancestor_below(t, id, ancestor);
 150
 151         ret = id && id < ancestor
 152                 ? test_ancestor_bitmap(t, id, ancestor)
 153                 : id == ancestor;
 154
 155         EBUG_ON(ret != __bch2_snapshot_is_ancestor_early(t, id, ancestor));
 156 out:
 157         rcu_read_unlock();
 158
 159         return ret;
 160 }
 161
 162 static noinline struct snapshot_t *__snapshot_t_mut(struct bch_fs *c, u32 id)
 163 {
 164         size_t idx = U32_MAX - id;
 165         struct snapshot_table *new, *old;
 166
 167         size_t new_bytes = kmalloc_size_roundup(struct_size(new, s, idx + 1));
 168         size_t new_size = (new_bytes - sizeof(*new)) / sizeof(new->s[0]);
 169
 170         if (unlikely(new_bytes > INT_MAX))
 171                 return NULL;
 172
 173         new = kvzalloc(new_bytes, GFP_KERNEL);
 174         if (!new)
 175                 return NULL;
 176
 177         new->nr = new_size;
 178
 179         old = rcu_dereference_protected(c->snapshots, true);
 180         if (old)
 181                 memcpy(new->s, old->s, sizeof(old->s[0]) * old->nr);
 182
 183         rcu_assign_pointer(c->snapshots, new);
 184         kvfree_rcu(old, rcu);
 185
 186         return &rcu_dereference_protected(c->snapshots,
 187                                 lockdep_is_held(&c->snapshot_table_lock))->s[idx];
 188 }
 189
 190 static inline struct snapshot_t *snapshot_t_mut(struct bch_fs *c, u32 id)
 191 {
 192         size_t idx = U32_MAX - id;
 193         struct snapshot_table *table =
 194                 rcu_dereference_protected(c->snapshots,
 195                                 lockdep_is_held(&c->snapshot_table_lock));
 196
 197         lockdep_assert_held(&c->snapshot_table_lock);
 198
 199         if (likely(table && idx < table->nr))
 200                 return &table->s[idx];
 201
 202         return __snapshot_t_mut(c, id);
 203 }
 204
 205 void bch2_snapshot_to_text(struct printbuf *out, struct bch_fs *c,
 206                            struct bkey_s_c k)
 207 {
 208         struct bkey_s_c_snapshot s = bkey_s_c_to_snapshot(k);
 209
 210         prt_printf(out, "is_subvol %llu deleted %llu parent %10u children %10u %10u subvol %u tree %u",
 211                BCH_SNAPSHOT_SUBVOL(s.v),
 212                BCH_SNAPSHOT_DELETED(s.v),
 213                le32_to_cpu(s.v->parent),
 214                le32_to_cpu(s.v->children[0]),
 215                le32_to_cpu(s.v->children[1]),
 216                le32_to_cpu(s.v->subvol),
 217                le32_to_cpu(s.v->tree));
 218
 219         if (bkey_val_bytes(k.k) > offsetof(struct bch_snapshot, depth))
 220                 prt_printf(out, " depth %u skiplist %u %u %u",
 221                            le32_to_cpu(s.v->depth),
 222                            le32_to_cpu(s.v->skip[0]),
 223                            le32_to_cpu(s.v->skip[1]),
 224                            le32_to_cpu(s.v->skip[2]));
 225 }
 226
 227 int bch2_snapshot_validate(struct bch_fs *c, struct bkey_s_c k,
 228                           enum bch_validate_flags flags)
 229 {
 230         struct bkey_s_c_snapshot s;
 231         u32 i, id;
 232         int ret = 0;
 233
 234         bkey_fsck_err_on(bkey_gt(k.k->p, POS(0, U32_MAX)) ||
 235                          bkey_lt(k.k->p, POS(0, 1)),
 236                          c, snapshot_pos_bad,
 237                          "bad pos");
 238
 239         s = bkey_s_c_to_snapshot(k);
 240
 241         id = le32_to_cpu(s.v->parent);
 242         bkey_fsck_err_on(id && id <= k.k->p.offset,
 243                          c, snapshot_parent_bad,
 244                          "bad parent node (%u <= %llu)",
 245                          id, k.k->p.offset);
 246
 247         bkey_fsck_err_on(le32_to_cpu(s.v->children[0]) < le32_to_cpu(s.v->children[1]),
 248                          c, snapshot_children_not_normalized,
 249                          "children not normalized");
 250
 251         bkey_fsck_err_on(s.v->children[0] && s.v->children[0] == s.v->children[1],
 252                          c, snapshot_child_duplicate,
 253                          "duplicate child nodes");
 254
 255         for (i = 0; i < 2; i++) {
 256                 id = le32_to_cpu(s.v->children[i]);
 257
 258                 bkey_fsck_err_on(id >= k.k->p.offset,
 259                                  c, snapshot_child_bad,
 260                                  "bad child node (%u >= %llu)",
 261                                  id, k.k->p.offset);
 262         }
 263
 264         if (bkey_val_bytes(k.k) > offsetof(struct bch_snapshot, skip)) {
 265                 bkey_fsck_err_on(le32_to_cpu(s.v->skip[0]) > le32_to_cpu(s.v->skip[1]) ||
 266                                  le32_to_cpu(s.v->skip[1]) > le32_to_cpu(s.v->skip[2]),
 267                                  c, snapshot_skiplist_not_normalized,
 268                                  "skiplist not normalized");
 269
 270                 for (i = 0; i < ARRAY_SIZE(s.v->skip); i++) {
 271                         id = le32_to_cpu(s.v->skip[i]);
 272
 273                         bkey_fsck_err_on(id && id < le32_to_cpu(s.v->parent),
 274                                          c, snapshot_skiplist_bad,
 275                                          "bad skiplist node %u", id);
 276                 }
 277         }
 278 fsck_err:
 279         return ret;
 280 }
 281
 282 static void __set_is_ancestor_bitmap(struct bch_fs *c, u32 id)
 283 {
 284         struct snapshot_t *t = snapshot_t_mut(c, id);
 285         u32 parent = id;
 286
 287         while ((parent = bch2_snapshot_parent_early(c, parent)) &&
 288                parent - id - 1 < IS_ANCESTOR_BITMAP)
 289                 __set_bit(parent - id - 1, t->is_ancestor);
 290 }
 291
 292 static void set_is_ancestor_bitmap(struct bch_fs *c, u32 id)
 293 {
 294         mutex_lock(&c->snapshot_table_lock);
 295         __set_is_ancestor_bitmap(c, id);
 296         mutex_unlock(&c->snapshot_table_lock);
 297 }
 298
 299 static int __bch2_mark_snapshot(struct btree_trans *trans,
 300                        enum btree_id btree, unsigned level,
 301                        struct bkey_s_c old, struct bkey_s_c new,
 302                        enum btree_iter_update_trigger_flags flags)
 303 {
 304         struct bch_fs *c = trans->c;
 305         struct snapshot_t *t;
 306         u32 id = new.k->p.offset;
 307         int ret = 0;
 308
 309         mutex_lock(&c->snapshot_table_lock);
 310
 311         t = snapshot_t_mut(c, id);
 312         if (!t) {
 313                 ret = -BCH_ERR_ENOMEM_mark_snapshot;
 314                 goto err;
 315         }
 316
 317         if (new.k->type == KEY_TYPE_snapshot) {
 318                 struct bkey_s_c_snapshot s = bkey_s_c_to_snapshot(new);
 319
 320                 t->parent       = le32_to_cpu(s.v->parent);
 321                 t->children[0]  = le32_to_cpu(s.v->children[0]);
 322                 t->children[1]  = le32_to_cpu(s.v->children[1]);
 323                 t->subvol       = BCH_SNAPSHOT_SUBVOL(s.v) ? le32_to_cpu(s.v->subvol) : 0;
 324                 t->tree         = le32_to_cpu(s.v->tree);
 325
 326                 if (bkey_val_bytes(s.k) > offsetof(struct bch_snapshot, depth)) {
 327                         t->depth        = le32_to_cpu(s.v->depth);
 328                         t->skip[0]      = le32_to_cpu(s.v->skip[0]);
 329                         t->skip[1]      = le32_to_cpu(s.v->skip[1]);
 330                         t->skip[2]      = le32_to_cpu(s.v->skip[2]);
 331                 } else {
 332                         t->depth        = 0;
 333                         t->skip[0]      = 0;
 334                         t->skip[1]      = 0;
 335                         t->skip[2]      = 0;
 336                 }
 337
 338                 __set_is_ancestor_bitmap(c, id);
 339
 340                 if (BCH_SNAPSHOT_DELETED(s.v)) {
 341                         set_bit(BCH_FS_need_delete_dead_snapshots, &c->flags);
 342                         if (c->curr_recovery_pass > BCH_RECOVERY_PASS_delete_dead_snapshots)
 343                                 bch2_delete_dead_snapshots_async(c);
 344                 }
 345         } else {
 346                 memset(t, 0, sizeof(*t));
 347         }
 348 err:
 349         mutex_unlock(&c->snapshot_table_lock);
 350         return ret;
 351 }
 352
 353 int bch2_mark_snapshot(struct btree_trans *trans,
 354                        enum btree_id btree, unsigned level,
 355                        struct bkey_s_c old, struct bkey_s new,
 356                        enum btree_iter_update_trigger_flags flags)
 357 {
 358         return __bch2_mark_snapshot(trans, btree, level, old, new.s_c, flags);
 359 }
 360
 361 int bch2_snapshot_lookup(struct btree_trans *trans, u32 id,
 362                          struct bch_snapshot *s)
 363 {
 364         return bch2_bkey_get_val_typed(trans, BTREE_ID_snapshots, POS(0, id),
 365                                        BTREE_ITER_with_updates, snapshot, s);
 366 }
 367
 368 static int bch2_snapshot_live(struct btree_trans *trans, u32 id)
 369 {
 370         struct bch_snapshot v;
 371         int ret;
 372
 373         if (!id)
 374                 return 0;
 375
 376         ret = bch2_snapshot_lookup(trans, id, &v);
 377         if (bch2_err_matches(ret, ENOENT))
 378                 bch_err(trans->c, "snapshot node %u not found", id);
 379         if (ret)
 380                 return ret;
 381
 382         return !BCH_SNAPSHOT_DELETED(&v);
 383 }
 384
 385 /*
 386  * If @k is a snapshot with just one live child, it's part of a linear chain,
 387  * which we consider to be an equivalence class: and then after snapshot
 388  * deletion cleanup, there should only be a single key at a given position in
 389  * this equivalence class.
 390  *
 391  * This sets the equivalence class of @k to be the child's equivalence class, if
 392  * it's part of such a linear chain: this correctly sets equivalence classes on
 393  * startup if we run leaf to root (i.e. in natural key order).
 394  */
 395 static int bch2_snapshot_set_equiv(struct btree_trans *trans, struct bkey_s_c k)
 396 {
 397         struct bch_fs *c = trans->c;
 398         unsigned i, nr_live = 0, live_idx = 0;
 399         struct bkey_s_c_snapshot snap;
 400         u32 id = k.k->p.offset, child[2];
 401
 402         if (k.k->type != KEY_TYPE_snapshot)
 403                 return 0;
 404
 405         snap = bkey_s_c_to_snapshot(k);
 406
 407         child[0] = le32_to_cpu(snap.v->children[0]);
 408         child[1] = le32_to_cpu(snap.v->children[1]);
 409
 410         for (i = 0; i < 2; i++) {
 411                 int ret = bch2_snapshot_live(trans, child[i]);
 412
 413                 if (ret < 0)
 414                         return ret;
 415
 416                 if (ret)
 417                         live_idx = i;
 418                 nr_live += ret;
 419         }
 420
 421         mutex_lock(&c->snapshot_table_lock);
 422
 423         snapshot_t_mut(c, id)->equiv = nr_live == 1
 424                 ? snapshot_t_mut(c, child[live_idx])->equiv
 425                 : id;
 426
 427         mutex_unlock(&c->snapshot_table_lock);
 428
 429         return 0;
 430 }
 431
 432 /* fsck: */
 433
 434 static u32 bch2_snapshot_child(struct bch_fs *c, u32 id, unsigned child)
 435 {
 436         return snapshot_t(c, id)->children[child];
 437 }
 438
 439 static u32 bch2_snapshot_left_child(struct bch_fs *c, u32 id)
 440 {
 441         return bch2_snapshot_child(c, id, 0);
 442 }
 443
 444 static u32 bch2_snapshot_right_child(struct bch_fs *c, u32 id)
 445 {
 446         return bch2_snapshot_child(c, id, 1);
 447 }
 448
 449 static u32 bch2_snapshot_tree_next(struct bch_fs *c, u32 id)
 450 {
 451         u32 n, parent;
 452
 453         n = bch2_snapshot_left_child(c, id);
 454         if (n)
 455                 return n;
 456
 457         while ((parent = bch2_snapshot_parent(c, id))) {
 458                 n = bch2_snapshot_right_child(c, parent);
 459                 if (n && n != id)
 460                         return n;
 461                 id = parent;
 462         }
 463
 464         return 0;
 465 }
 466
 467 static u32 bch2_snapshot_tree_oldest_subvol(struct bch_fs *c, u32 snapshot_root)
 468 {
 469         u32 id = snapshot_root;
 470         u32 subvol = 0, s;
 471
 472         rcu_read_lock();
 473         while (id) {
 474                 s = snapshot_t(c, id)->subvol;
 475
 476                 if (s && (!subvol || s < subvol))
 477                         subvol = s;
 478
 479                 id = bch2_snapshot_tree_next(c, id);
 480         }
 481         rcu_read_unlock();
 482
 483         return subvol;
 484 }
 485
 486 static int bch2_snapshot_tree_master_subvol(struct btree_trans *trans,
 487                                             u32 snapshot_root, u32 *subvol_id)
 488 {
 489         struct bch_fs *c = trans->c;
 490         struct btree_iter iter;
 491         struct bkey_s_c k;
 492         bool found = false;
 493         int ret;
 494
 495         for_each_btree_key_norestart(trans, iter, BTREE_ID_subvolumes, POS_MIN,
 496                                      0, k, ret) {
 497                 if (k.k->type != KEY_TYPE_subvolume)
 498                         continue;
 499
 500                 struct bkey_s_c_subvolume s = bkey_s_c_to_subvolume(k);
 501                 if (!bch2_snapshot_is_ancestor(c, le32_to_cpu(s.v->snapshot), snapshot_root))
 502                         continue;
 503                 if (!BCH_SUBVOLUME_SNAP(s.v)) {
 504                         *subvol_id = s.k->p.offset;
 505                         found = true;
 506                         break;
 507                 }
 508         }
 509
 510         bch2_trans_iter_exit(trans, &iter);
 511
 512         if (!ret && !found) {
 513                 struct bkey_i_subvolume *u;
 514
 515                 *subvol_id = bch2_snapshot_tree_oldest_subvol(c, snapshot_root);
 516
 517                 u = bch2_bkey_get_mut_typed(trans, &iter,
 518                                             BTREE_ID_subvolumes, POS(0, *subvol_id),
 519                                             0, subvolume);
 520                 ret = PTR_ERR_OR_ZERO(u);
 521                 if (ret)
 522                         return ret;
 523
 524                 SET_BCH_SUBVOLUME_SNAP(&u->v, false);
 525         }
 526
 527         return ret;
 528 }
 529
 530 static int check_snapshot_tree(struct btree_trans *trans,
 531                                struct btree_iter *iter,
 532                                struct bkey_s_c k)
 533 {
 534         struct bch_fs *c = trans->c;
 535         struct bkey_s_c_snapshot_tree st;
 536         struct bch_snapshot s;
 537         struct bch_subvolume subvol;
 538         struct printbuf buf = PRINTBUF;
 539         u32 root_id;
 540         int ret;
 541
 542         if (k.k->type != KEY_TYPE_snapshot_tree)
 543                 return 0;
 544
 545         st = bkey_s_c_to_snapshot_tree(k);
 546         root_id = le32_to_cpu(st.v->root_snapshot);
 547
 548         ret = bch2_snapshot_lookup(trans, root_id, &s);
 549         if (ret && !bch2_err_matches(ret, ENOENT))
 550                 goto err;
 551
 552         if (fsck_err_on(ret ||
 553                         root_id != bch2_snapshot_root(c, root_id) ||
 554                         st.k->p.offset != le32_to_cpu(s.tree),
 555                         trans, snapshot_tree_to_missing_snapshot,
 556                         "snapshot tree points to missing/incorrect snapshot:\n  %s",
 557                         (bch2_bkey_val_to_text(&buf, c, st.s_c), buf.buf))) {
 558                 ret = bch2_btree_delete_at(trans, iter, 0);
 559                 goto err;
 560         }
 561
 562         ret = bch2_subvolume_get(trans, le32_to_cpu(st.v->master_subvol),
 563                                  false, 0, &subvol);
 564         if (ret && !bch2_err_matches(ret, ENOENT))
 565                 goto err;
 566
 567         if (fsck_err_on(ret,
 568                         trans, snapshot_tree_to_missing_subvol,
 569                         "snapshot tree points to missing subvolume:\n  %s",
 570                         (printbuf_reset(&buf),
 571                          bch2_bkey_val_to_text(&buf, c, st.s_c), buf.buf)) ||
 572             fsck_err_on(!bch2_snapshot_is_ancestor(c,
 573                                                 le32_to_cpu(subvol.snapshot),
 574                                                 root_id),
 575                         trans, snapshot_tree_to_wrong_subvol,
 576                         "snapshot tree points to subvolume that does not point to snapshot in this tree:\n  %s",
 577                         (printbuf_reset(&buf),
 578                          bch2_bkey_val_to_text(&buf, c, st.s_c), buf.buf)) ||
 579             fsck_err_on(BCH_SUBVOLUME_SNAP(&subvol),
 580                         trans, snapshot_tree_to_snapshot_subvol,
 581                         "snapshot tree points to snapshot subvolume:\n  %s",
 582                         (printbuf_reset(&buf),
 583                          bch2_bkey_val_to_text(&buf, c, st.s_c), buf.buf))) {
 584                 struct bkey_i_snapshot_tree *u;
 585                 u32 subvol_id;
 586
 587                 ret = bch2_snapshot_tree_master_subvol(trans, root_id, &subvol_id);
 588                 bch_err_fn(c, ret);
 589
 590                 if (bch2_err_matches(ret, ENOENT)) { /* nothing to be done here */
 591                         ret = 0;
 592                         goto err;
 593                 }
 594
 595                 if (ret)
 596                         goto err;
 597
 598                 u = bch2_bkey_make_mut_typed(trans, iter, &k, 0, snapshot_tree);
 599                 ret = PTR_ERR_OR_ZERO(u);
 600                 if (ret)
 601                         goto err;
 602
 603                 u->v.master_subvol = cpu_to_le32(subvol_id);
 604                 st = snapshot_tree_i_to_s_c(u);
 605         }
 606 err:
 607 fsck_err:
 608         printbuf_exit(&buf);
 609         return ret;
 610 }
 611
 612 /*
 613  * For each snapshot_tree, make sure it points to the root of a snapshot tree
 614  * and that snapshot entry points back to it, or delete it.
 615  *
 616  * And, make sure it points to a subvolume within that snapshot tree, or correct
 617  * it to point to the oldest subvolume within that snapshot tree.
 618  */
 619 int bch2_check_snapshot_trees(struct bch_fs *c)
 620 {
 621         int ret = bch2_trans_run(c,
 622                 for_each_btree_key_commit(trans, iter,
 623                         BTREE_ID_snapshot_trees, POS_MIN,
 624                         BTREE_ITER_prefetch, k,
 625                         NULL, NULL, BCH_TRANS_COMMIT_no_enospc,
 626                 check_snapshot_tree(trans, &iter, k)));
 627         bch_err_fn(c, ret);
 628         return ret;
 629 }
 630
 631 /*
 632  * Look up snapshot tree for @tree_id and find root,
 633  * make sure @snap_id is a descendent:
 634  */
 635 static int snapshot_tree_ptr_good(struct btree_trans *trans,
 636                                   u32 snap_id, u32 tree_id)
 637 {
 638         struct bch_snapshot_tree s_t;
 639         int ret = bch2_snapshot_tree_lookup(trans, tree_id, &s_t);
 640
 641         if (bch2_err_matches(ret, ENOENT))
 642                 return 0;
 643         if (ret)
 644                 return ret;
 645
 646         return bch2_snapshot_is_ancestor_early(trans->c, snap_id, le32_to_cpu(s_t.root_snapshot));
 647 }
 648
 649 u32 bch2_snapshot_skiplist_get(struct bch_fs *c, u32 id)
 650 {
 651         const struct snapshot_t *s;
 652
 653         if (!id)
 654                 return 0;
 655
 656         rcu_read_lock();
 657         s = snapshot_t(c, id);
 658         if (s->parent)
 659                 id = bch2_snapshot_nth_parent(c, id, get_random_u32_below(s->depth));
 660         rcu_read_unlock();
 661
 662         return id;
 663 }
 664
 665 static int snapshot_skiplist_good(struct btree_trans *trans, u32 id, struct bch_snapshot s)
 666 {
 667         unsigned i;
 668
 669         for (i = 0; i < 3; i++)
 670                 if (!s.parent) {
 671                         if (s.skip[i])
 672                                 return false;
 673                 } else {
 674                         if (!bch2_snapshot_is_ancestor_early(trans->c, id, le32_to_cpu(s.skip[i])))
 675                                 return false;
 676                 }
 677
 678         return true;
 679 }
 680
 681 /*
 682  * snapshot_tree pointer was incorrect: look up root snapshot node, make sure
 683  * its snapshot_tree pointer is correct (allocate new one if necessary), then
 684  * update this node's pointer to root node's pointer:
 685  */
 686 static int snapshot_tree_ptr_repair(struct btree_trans *trans,
 687                                     struct btree_iter *iter,
 688                                     struct bkey_s_c k,
 689                                     struct bch_snapshot *s)
 690 {
 691         struct bch_fs *c = trans->c;
 692         struct btree_iter root_iter;
 693         struct bch_snapshot_tree s_t;
 694         struct bkey_s_c_snapshot root;
 695         struct bkey_i_snapshot *u;
 696         u32 root_id = bch2_snapshot_root(c, k.k->p.offset), tree_id;
 697         int ret;
 698
 699         root = bch2_bkey_get_iter_typed(trans, &root_iter,
 700                                BTREE_ID_snapshots, POS(0, root_id),
 701                                BTREE_ITER_with_updates, snapshot);
 702         ret = bkey_err(root);
 703         if (ret)
 704                 goto err;
 705
 706         tree_id = le32_to_cpu(root.v->tree);
 707
 708         ret = bch2_snapshot_tree_lookup(trans, tree_id, &s_t);
 709         if (ret && !bch2_err_matches(ret, ENOENT))
 710                 return ret;
 711
 712         if (ret || le32_to_cpu(s_t.root_snapshot) != root_id) {
 713                 u = bch2_bkey_make_mut_typed(trans, &root_iter, &root.s_c, 0, snapshot);
 714                 ret =   PTR_ERR_OR_ZERO(u) ?:
 715                         bch2_snapshot_tree_create(trans, root_id,
 716                                 bch2_snapshot_tree_oldest_subvol(c, root_id),
 717                                 &tree_id);
 718                 if (ret)
 719                         goto err;
 720
 721                 u->v.tree = cpu_to_le32(tree_id);
 722                 if (k.k->p.offset == root_id)
 723                         *s = u->v;
 724         }
 725
 726         if (k.k->p.offset != root_id) {
 727                 u = bch2_bkey_make_mut_typed(trans, iter, &k, 0, snapshot);
 728                 ret = PTR_ERR_OR_ZERO(u);
 729                 if (ret)
 730                         goto err;
 731
 732                 u->v.tree = cpu_to_le32(tree_id);
 733                 *s = u->v;
 734         }
 735 err:
 736         bch2_trans_iter_exit(trans, &root_iter);
 737         return ret;
 738 }
 739
 740 static int check_snapshot(struct btree_trans *trans,
 741                           struct btree_iter *iter,
 742                           struct bkey_s_c k)
 743 {
 744         struct bch_fs *c = trans->c;
 745         struct bch_snapshot s;
 746         struct bch_subvolume subvol;
 747         struct bch_snapshot v;
 748         struct bkey_i_snapshot *u;
 749         u32 parent_id = bch2_snapshot_parent_early(c, k.k->p.offset);
 750         u32 real_depth;
 751         struct printbuf buf = PRINTBUF;
 752         u32 i, id;
 753         int ret = 0;
 754
 755         if (k.k->type != KEY_TYPE_snapshot)
 756                 return 0;
 757
 758         memset(&s, 0, sizeof(s));
 759         memcpy(&s, k.v, min(sizeof(s), bkey_val_bytes(k.k)));
 760
 761         id = le32_to_cpu(s.parent);
 762         if (id) {
 763                 ret = bch2_snapshot_lookup(trans, id, &v);
 764                 if (bch2_err_matches(ret, ENOENT))
 765                         bch_err(c, "snapshot with nonexistent parent:\n  %s",
 766                                 (bch2_bkey_val_to_text(&buf, c, k), buf.buf));
 767                 if (ret)
 768                         goto err;
 769
 770                 if (le32_to_cpu(v.children[0]) != k.k->p.offset &&
 771                     le32_to_cpu(v.children[1]) != k.k->p.offset) {
 772                         bch_err(c, "snapshot parent %u missing pointer to child %llu",
 773                                 id, k.k->p.offset);
 774                         ret = -EINVAL;
 775                         goto err;
 776                 }
 777         }
 778
 779         for (i = 0; i < 2 && s.children[i]; i++) {
 780                 id = le32_to_cpu(s.children[i]);
 781
 782                 ret = bch2_snapshot_lookup(trans, id, &v);
 783                 if (bch2_err_matches(ret, ENOENT))
 784                         bch_err(c, "snapshot node %llu has nonexistent child %u",
 785                                 k.k->p.offset, id);
 786                 if (ret)
 787                         goto err;
 788
 789                 if (le32_to_cpu(v.parent) != k.k->p.offset) {
 790                         bch_err(c, "snapshot child %u has wrong parent (got %u should be %llu)",
 791                                 id, le32_to_cpu(v.parent), k.k->p.offset);
 792                         ret = -EINVAL;
 793                         goto err;
 794                 }
 795         }
 796
 797         bool should_have_subvol = BCH_SNAPSHOT_SUBVOL(&s) &&
 798                 !BCH_SNAPSHOT_DELETED(&s);
 799
 800         if (should_have_subvol) {
 801                 id = le32_to_cpu(s.subvol);
 802                 ret = bch2_subvolume_get(trans, id, 0, false, &subvol);
 803                 if (bch2_err_matches(ret, ENOENT))
 804                         bch_err(c, "snapshot points to nonexistent subvolume:\n  %s",
 805                                 (bch2_bkey_val_to_text(&buf, c, k), buf.buf));
 806                 if (ret)
 807                         goto err;
 808
 809                 if (BCH_SNAPSHOT_SUBVOL(&s) != (le32_to_cpu(subvol.snapshot) == k.k->p.offset)) {
 810                         bch_err(c, "snapshot node %llu has wrong BCH_SNAPSHOT_SUBVOL",
 811                                 k.k->p.offset);
 812                         ret = -EINVAL;
 813                         goto err;
 814                 }
 815         } else {
 816                 if (fsck_err_on(s.subvol,
 817                                 trans, snapshot_should_not_have_subvol,
 818                                 "snapshot should not point to subvol:\n  %s",
 819                                 (bch2_bkey_val_to_text(&buf, c, k), buf.buf))) {
 820                         u = bch2_bkey_make_mut_typed(trans, iter, &k, 0, snapshot);
 821                         ret = PTR_ERR_OR_ZERO(u);
 822                         if (ret)
 823                                 goto err;
 824
 825                         u->v.subvol = 0;
 826                         s = u->v;
 827                 }
 828         }
 829
 830         ret = snapshot_tree_ptr_good(trans, k.k->p.offset, le32_to_cpu(s.tree));
 831         if (ret < 0)
 832                 goto err;
 833
 834         if (fsck_err_on(!ret,
 835                         trans, snapshot_to_bad_snapshot_tree,
 836                         "snapshot points to missing/incorrect tree:\n  %s",
 837                         (bch2_bkey_val_to_text(&buf, c, k), buf.buf))) {
 838                 ret = snapshot_tree_ptr_repair(trans, iter, k, &s);
 839                 if (ret)
 840                         goto err;
 841         }
 842         ret = 0;
 843
 844         real_depth = bch2_snapshot_depth(c, parent_id);
 845
 846         if (fsck_err_on(le32_to_cpu(s.depth) != real_depth,
 847                         trans, snapshot_bad_depth,
 848                         "snapshot with incorrect depth field, should be %u:\n  %s",
 849                         real_depth, (bch2_bkey_val_to_text(&buf, c, k), buf.buf))) {
 850                 u = bch2_bkey_make_mut_typed(trans, iter, &k, 0, snapshot);
 851                 ret = PTR_ERR_OR_ZERO(u);
 852                 if (ret)
 853                         goto err;
 854
 855                 u->v.depth = cpu_to_le32(real_depth);
 856                 s = u->v;
 857         }
 858
 859         ret = snapshot_skiplist_good(trans, k.k->p.offset, s);
 860         if (ret < 0)
 861                 goto err;
 862
 863         if (fsck_err_on(!ret,
 864                         trans, snapshot_bad_skiplist,
 865                         "snapshot with bad skiplist field:\n  %s",
 866                         (bch2_bkey_val_to_text(&buf, c, k), buf.buf))) {
 867                 u = bch2_bkey_make_mut_typed(trans, iter, &k, 0, snapshot);
 868                 ret = PTR_ERR_OR_ZERO(u);
 869                 if (ret)
 870                         goto err;
 871
 872                 for (i = 0; i < ARRAY_SIZE(u->v.skip); i++)
 873                         u->v.skip[i] = cpu_to_le32(bch2_snapshot_skiplist_get(c, parent_id));
 874
 875                 bubble_sort(u->v.skip, ARRAY_SIZE(u->v.skip), cmp_le32);
 876                 s = u->v;
 877         }
 878         ret = 0;
 879 err:
 880 fsck_err:
 881         printbuf_exit(&buf);
 882         return ret;
 883 }
 884
 885 int bch2_check_snapshots(struct bch_fs *c)
 886 {
 887         /*
 888          * We iterate backwards as checking/fixing the depth field requires that
 889          * the parent's depth already be correct:
 890          */
 891         int ret = bch2_trans_run(c,
 892                 for_each_btree_key_reverse_commit(trans, iter,
 893                                 BTREE_ID_snapshots, POS_MAX,
 894                                 BTREE_ITER_prefetch, k,
 895                                 NULL, NULL, BCH_TRANS_COMMIT_no_enospc,
 896                         check_snapshot(trans, &iter, k)));
 897         bch_err_fn(c, ret);
 898         return ret;
 899 }
 900
 901 static int check_snapshot_exists(struct btree_trans *trans, u32 id)
 902 {
 903         struct bch_fs *c = trans->c;
 904
 905         if (bch2_snapshot_equiv(c, id))
 906                 return 0;
 907
 908         /* 0 is an invalid tree ID */
 909         u32 tree_id = 0;
 910         int ret = bch2_snapshot_tree_create(trans, id, 0, &tree_id);
 911         if (ret)
 912                 return ret;
 913
 914         struct bkey_i_snapshot *snapshot = bch2_trans_kmalloc(trans, sizeof(*snapshot));
 915         ret = PTR_ERR_OR_ZERO(snapshot);
 916         if (ret)
 917                 return ret;
 918
 919         bkey_snapshot_init(&snapshot->k_i);
 920         snapshot->k.p           = POS(0, id);
 921         snapshot->v.tree        = cpu_to_le32(tree_id);
 922         snapshot->v.btime.lo    = cpu_to_le64(bch2_current_time(c));
 923
 924         return  bch2_btree_insert_trans(trans, BTREE_ID_snapshots, &snapshot->k_i, 0) ?:
 925                 bch2_mark_snapshot(trans, BTREE_ID_snapshots, 0,
 926                                    bkey_s_c_null, bkey_i_to_s(&snapshot->k_i), 0) ?:
 927                 bch2_snapshot_set_equiv(trans, bkey_i_to_s_c(&snapshot->k_i));
 928 }
 929
 930 /* Figure out which snapshot nodes belong in the same tree: */
 931 struct snapshot_tree_reconstruct {
 932         enum btree_id                   btree;
 933         struct bpos                     cur_pos;
 934         snapshot_id_list                cur_ids;
 935         DARRAY(snapshot_id_list)        trees;
 936 };
 937
 938 static void snapshot_tree_reconstruct_exit(struct snapshot_tree_reconstruct *r)
 939 {
 940         darray_for_each(r->trees, i)
 941                 darray_exit(i);
 942         darray_exit(&r->trees);
 943         darray_exit(&r->cur_ids);
 944 }
 945
 946 static inline bool same_snapshot(struct snapshot_tree_reconstruct *r, struct bpos pos)
 947 {
 948         return r->btree == BTREE_ID_inodes
 949                 ? r->cur_pos.offset == pos.offset
 950                 : r->cur_pos.inode == pos.inode;
 951 }
 952
 953 static inline bool snapshot_id_lists_have_common(snapshot_id_list *l, snapshot_id_list *r)
 954 {
 955         darray_for_each(*l, i)
 956                 if (snapshot_list_has_id(r, *i))
 957                         return true;
 958         return false;
 959 }
 960
 961 static void snapshot_id_list_to_text(struct printbuf *out, snapshot_id_list *s)
 962 {
 963         bool first = true;
 964         darray_for_each(*s, i) {
 965                 if (!first)
 966                         prt_char(out, ' ');
 967                 first = false;
 968                 prt_printf(out, "%u", *i);
 969         }
 970 }
 971
 972 static int snapshot_tree_reconstruct_next(struct bch_fs *c, struct snapshot_tree_reconstruct *r)
 973 {
 974         if (r->cur_ids.nr) {
 975                 darray_for_each(r->trees, i)
 976                         if (snapshot_id_lists_have_common(i, &r->cur_ids)) {
 977                                 int ret = snapshot_list_merge(c, i, &r->cur_ids);
 978                                 if (ret)
 979                                         return ret;
 980                                 goto out;
 981                         }
 982                 darray_push(&r->trees, r->cur_ids);
 983                 darray_init(&r->cur_ids);
 984         }
 985 out:
 986         r->cur_ids.nr = 0;
 987         return 0;
 988 }
 989
 990 static int get_snapshot_trees(struct bch_fs *c, struct snapshot_tree_reconstruct *r, struct bpos pos)
 991 {
 992         if (!same_snapshot(r, pos))
 993                 snapshot_tree_reconstruct_next(c, r);
 994         r->cur_pos = pos;
 995         return snapshot_list_add_nodup(c, &r->cur_ids, pos.snapshot);
 996 }
 997
 998 int bch2_reconstruct_snapshots(struct bch_fs *c)
 999 {
1000         struct btree_trans *trans = bch2_trans_get(c);
1001         struct printbuf buf = PRINTBUF;
1002         struct snapshot_tree_reconstruct r = {};
1003         int ret = 0;
1004
1005         for (unsigned btree = 0; btree < BTREE_ID_NR; btree++) {
1006                 if (btree_type_has_snapshots(btree)) {
1007                         r.btree = btree;
1008
1009                         ret = for_each_btree_key(trans, iter, btree, POS_MIN,
1010                                         BTREE_ITER_all_snapshots|BTREE_ITER_prefetch, k, ({
1011                                 get_snapshot_trees(c, &r, k.k->p);
1012                         }));
1013                         if (ret)
1014                                 goto err;
1015
1016                         snapshot_tree_reconstruct_next(c, &r);
1017                 }
1018         }
1019
1020         darray_for_each(r.trees, t) {
1021                 printbuf_reset(&buf);
1022                 snapshot_id_list_to_text(&buf, t);
1023
1024                 darray_for_each(*t, id) {
1025                         if (fsck_err_on(!bch2_snapshot_equiv(c, *id),
1026                                         trans, snapshot_node_missing,
1027                                         "snapshot node %u from tree %s missing, recreate?", *id, buf.buf)) {
1028                                 if (t->nr > 1) {
1029                                         bch_err(c, "cannot reconstruct snapshot trees with multiple nodes");
1030                                         ret = -BCH_ERR_fsck_repair_unimplemented;
1031                                         goto err;
1032                                 }
1033
1034                                 ret = commit_do(trans, NULL, NULL, BCH_TRANS_COMMIT_no_enospc,
1035                                                 check_snapshot_exists(trans, *id));
1036                                 if (ret)
1037                                         goto err;
1038                         }
1039                 }
1040         }
1041 fsck_err:
1042 err:
1043         bch2_trans_put(trans);
1044         snapshot_tree_reconstruct_exit(&r);
1045         printbuf_exit(&buf);
1046         bch_err_fn(c, ret);
1047         return ret;
1048 }
1049
1050 int bch2_check_key_has_snapshot(struct btree_trans *trans,
1051                                 struct btree_iter *iter,
1052                                 struct bkey_s_c k)
1053 {
1054         struct bch_fs *c = trans->c;
1055         struct printbuf buf = PRINTBUF;
1056         int ret = 0;
1057
1058         if (fsck_err_on(!bch2_snapshot_equiv(c, k.k->p.snapshot),
1059                         trans, bkey_in_missing_snapshot,
1060                         "key in missing snapshot %s, delete?",
1061                         (bch2_bkey_val_to_text(&buf, c, k), buf.buf)))
1062                 ret = bch2_btree_delete_at(trans, iter,
1063                                             BTREE_UPDATE_internal_snapshot_node) ?: 1;
1064 fsck_err:
1065         printbuf_exit(&buf);
1066         return ret;
1067 }
1068
1069 /*
1070  * Mark a snapshot as deleted, for future cleanup:
1071  */
1072 int bch2_snapshot_node_set_deleted(struct btree_trans *trans, u32 id)
1073 {
1074         struct btree_iter iter;
1075         struct bkey_i_snapshot *s;
1076         int ret = 0;
1077
1078         s = bch2_bkey_get_mut_typed(trans, &iter,
1079                                     BTREE_ID_snapshots, POS(0, id),
1080                                     0, snapshot);
1081         ret = PTR_ERR_OR_ZERO(s);
1082         if (unlikely(ret)) {
1083                 bch2_fs_inconsistent_on(bch2_err_matches(ret, ENOENT),
1084                                         trans->c, "missing snapshot %u", id);
1085                 return ret;
1086         }
1087
1088         /* already deleted? */
1089         if (BCH_SNAPSHOT_DELETED(&s->v))
1090                 goto err;
1091
1092         SET_BCH_SNAPSHOT_DELETED(&s->v, true);
1093         SET_BCH_SNAPSHOT_SUBVOL(&s->v, false);
1094         s->v.subvol = 0;
1095 err:
1096         bch2_trans_iter_exit(trans, &iter);
1097         return ret;
1098 }
1099
1100 static inline void normalize_snapshot_child_pointers(struct bch_snapshot *s)
1101 {
1102         if (le32_to_cpu(s->children[0]) < le32_to_cpu(s->children[1]))
1103                 swap(s->children[0], s->children[1]);
1104 }
1105
1106 static int bch2_snapshot_node_delete(struct btree_trans *trans, u32 id)
1107 {
1108         struct bch_fs *c = trans->c;
1109         struct btree_iter iter, p_iter = (struct btree_iter) { NULL };
1110         struct btree_iter c_iter = (struct btree_iter) { NULL };
1111         struct btree_iter tree_iter = (struct btree_iter) { NULL };
1112         struct bkey_s_c_snapshot s;
1113         u32 parent_id, child_id;
1114         unsigned i;
1115         int ret = 0;
1116
1117         s = bch2_bkey_get_iter_typed(trans, &iter, BTREE_ID_snapshots, POS(0, id),
1118                                      BTREE_ITER_intent, snapshot);
1119         ret = bkey_err(s);
1120         bch2_fs_inconsistent_on(bch2_err_matches(ret, ENOENT), c,
1121                                 "missing snapshot %u", id);
1122
1123         if (ret)
1124                 goto err;
1125
1126         BUG_ON(s.v->children[1]);
1127
1128         parent_id = le32_to_cpu(s.v->parent);
1129         child_id = le32_to_cpu(s.v->children[0]);
1130
1131         if (parent_id) {
1132                 struct bkey_i_snapshot *parent;
1133
1134                 parent = bch2_bkey_get_mut_typed(trans, &p_iter,
1135                                      BTREE_ID_snapshots, POS(0, parent_id),
1136                                      0, snapshot);
1137                 ret = PTR_ERR_OR_ZERO(parent);
1138                 bch2_fs_inconsistent_on(bch2_err_matches(ret, ENOENT), c,
1139                                         "missing snapshot %u", parent_id);
1140                 if (unlikely(ret))
1141                         goto err;
1142
1143                 /* find entry in parent->children for node being deleted */
1144                 for (i = 0; i < 2; i++)
1145                         if (le32_to_cpu(parent->v.children[i]) == id)
1146                                 break;
1147
1148                 if (bch2_fs_inconsistent_on(i == 2, c,
1149                                         "snapshot %u missing child pointer to %u",
1150                                         parent_id, id))
1151                         goto err;
1152
1153                 parent->v.children[i] = cpu_to_le32(child_id);
1154
1155                 normalize_snapshot_child_pointers(&parent->v);
1156         }
1157
1158         if (child_id) {
1159                 struct bkey_i_snapshot *child;
1160
1161                 child = bch2_bkey_get_mut_typed(trans, &c_iter,
1162                                      BTREE_ID_snapshots, POS(0, child_id),
1163                                      0, snapshot);
1164                 ret = PTR_ERR_OR_ZERO(child);
1165                 bch2_fs_inconsistent_on(bch2_err_matches(ret, ENOENT), c,
1166                                         "missing snapshot %u", child_id);
1167                 if (unlikely(ret))
1168                         goto err;
1169
1170                 child->v.parent = cpu_to_le32(parent_id);
1171
1172                 if (!child->v.parent) {
1173                         child->v.skip[0] = 0;
1174                         child->v.skip[1] = 0;
1175                         child->v.skip[2] = 0;
1176                 }
1177         }
1178
1179         if (!parent_id) {
1180                 /*
1181                  * We're deleting the root of a snapshot tree: update the
1182                  * snapshot_tree entry to point to the new root, or delete it if
1183                  * this is the last snapshot ID in this tree:
1184                  */
1185                 struct bkey_i_snapshot_tree *s_t;
1186
1187                 BUG_ON(s.v->children[1]);
1188
1189                 s_t = bch2_bkey_get_mut_typed(trans, &tree_iter,
1190                                 BTREE_ID_snapshot_trees, POS(0, le32_to_cpu(s.v->tree)),
1191                                 0, snapshot_tree);
1192                 ret = PTR_ERR_OR_ZERO(s_t);
1193                 if (ret)
1194                         goto err;
1195
1196                 if (s.v->children[0]) {
1197                         s_t->v.root_snapshot = s.v->children[0];
1198                 } else {
1199                         s_t->k.type = KEY_TYPE_deleted;
1200                         set_bkey_val_u64s(&s_t->k, 0);
1201                 }
1202         }
1203
1204         ret = bch2_btree_delete_at(trans, &iter, 0);
1205 err:
1206         bch2_trans_iter_exit(trans, &tree_iter);
1207         bch2_trans_iter_exit(trans, &p_iter);
1208         bch2_trans_iter_exit(trans, &c_iter);
1209         bch2_trans_iter_exit(trans, &iter);
1210         return ret;
1211 }
1212
1213 static int create_snapids(struct btree_trans *trans, u32 parent, u32 tree,
1214                           u32 *new_snapids,
1215                           u32 *snapshot_subvols,
1216                           unsigned nr_snapids)
1217 {
1218         struct bch_fs *c = trans->c;
1219         struct btree_iter iter;
1220         struct bkey_i_snapshot *n;
1221         struct bkey_s_c k;
1222         unsigned i, j;
1223         u32 depth = bch2_snapshot_depth(c, parent);
1224         int ret;
1225
1226         bch2_trans_iter_init(trans, &iter, BTREE_ID_snapshots,
1227                              POS_MIN, BTREE_ITER_intent);
1228         k = bch2_btree_iter_peek(&iter);
1229         ret = bkey_err(k);
1230         if (ret)
1231                 goto err;
1232
1233         for (i = 0; i < nr_snapids; i++) {
1234                 k = bch2_btree_iter_prev_slot(&iter);
1235                 ret = bkey_err(k);
1236                 if (ret)
1237                         goto err;
1238
1239                 if (!k.k || !k.k->p.offset) {
1240                         ret = -BCH_ERR_ENOSPC_snapshot_create;
1241                         goto err;
1242                 }
1243
1244                 n = bch2_bkey_alloc(trans, &iter, 0, snapshot);
1245                 ret = PTR_ERR_OR_ZERO(n);
1246                 if (ret)
1247                         goto err;
1248
1249                 n->v.flags      = 0;
1250                 n->v.parent     = cpu_to_le32(parent);
1251                 n->v.subvol     = cpu_to_le32(snapshot_subvols[i]);
1252                 n->v.tree       = cpu_to_le32(tree);
1253                 n->v.depth      = cpu_to_le32(depth);
1254                 n->v.btime.lo   = cpu_to_le64(bch2_current_time(c));
1255                 n->v.btime.hi   = 0;
1256
1257                 for (j = 0; j < ARRAY_SIZE(n->v.skip); j++)
1258                         n->v.skip[j] = cpu_to_le32(bch2_snapshot_skiplist_get(c, parent));
1259
1260                 bubble_sort(n->v.skip, ARRAY_SIZE(n->v.skip), cmp_le32);
1261                 SET_BCH_SNAPSHOT_SUBVOL(&n->v, true);
1262
1263                 ret = __bch2_mark_snapshot(trans, BTREE_ID_snapshots, 0,
1264                                          bkey_s_c_null, bkey_i_to_s_c(&n->k_i), 0);
1265                 if (ret)
1266                         goto err;
1267
1268                 new_snapids[i]  = iter.pos.offset;
1269
1270                 mutex_lock(&c->snapshot_table_lock);
1271                 snapshot_t_mut(c, new_snapids[i])->equiv = new_snapids[i];
1272                 mutex_unlock(&c->snapshot_table_lock);
1273         }
1274 err:
1275         bch2_trans_iter_exit(trans, &iter);
1276         return ret;
1277 }
1278
1279 /*
1280  * Create new snapshot IDs as children of an existing snapshot ID:
1281  */
1282 static int bch2_snapshot_node_create_children(struct btree_trans *trans, u32 parent,
1283                               u32 *new_snapids,
1284                               u32 *snapshot_subvols,
1285                               unsigned nr_snapids)
1286 {
1287         struct btree_iter iter;
1288         struct bkey_i_snapshot *n_parent;
1289         int ret = 0;
1290
1291         n_parent = bch2_bkey_get_mut_typed(trans, &iter,
1292                         BTREE_ID_snapshots, POS(0, parent),
1293                         0, snapshot);
1294         ret = PTR_ERR_OR_ZERO(n_parent);
1295         if (unlikely(ret)) {
1296                 if (bch2_err_matches(ret, ENOENT))
1297                         bch_err(trans->c, "snapshot %u not found", parent);
1298                 return ret;
1299         }
1300
1301         if (n_parent->v.children[0] || n_parent->v.children[1]) {
1302                 bch_err(trans->c, "Trying to add child snapshot nodes to parent that already has children");
1303                 ret = -EINVAL;
1304                 goto err;
1305         }
1306
1307         ret = create_snapids(trans, parent, le32_to_cpu(n_parent->v.tree),
1308                              new_snapids, snapshot_subvols, nr_snapids);
1309         if (ret)
1310                 goto err;
1311
1312         n_parent->v.children[0] = cpu_to_le32(new_snapids[0]);
1313         n_parent->v.children[1] = cpu_to_le32(new_snapids[1]);
1314         n_parent->v.subvol = 0;
1315         SET_BCH_SNAPSHOT_SUBVOL(&n_parent->v, false);
1316 err:
1317         bch2_trans_iter_exit(trans, &iter);
1318         return ret;
1319 }
1320
1321 /*
1322  * Create a snapshot node that is the root of a new tree:
1323  */
1324 static int bch2_snapshot_node_create_tree(struct btree_trans *trans,
1325                               u32 *new_snapids,
1326                               u32 *snapshot_subvols,
1327                               unsigned nr_snapids)
1328 {
1329         struct bkey_i_snapshot_tree *n_tree;
1330         int ret;
1331
1332         n_tree = __bch2_snapshot_tree_create(trans);
1333         ret =   PTR_ERR_OR_ZERO(n_tree) ?:
1334                 create_snapids(trans, 0, n_tree->k.p.offset,
1335                              new_snapids, snapshot_subvols, nr_snapids);
1336         if (ret)
1337                 return ret;
1338
1339         n_tree->v.master_subvol = cpu_to_le32(snapshot_subvols[0]);
1340         n_tree->v.root_snapshot = cpu_to_le32(new_snapids[0]);
1341         return 0;
1342 }
1343
1344 int bch2_snapshot_node_create(struct btree_trans *trans, u32 parent,
1345                               u32 *new_snapids,
1346                               u32 *snapshot_subvols,
1347                               unsigned nr_snapids)
1348 {
1349         BUG_ON((parent == 0) != (nr_snapids == 1));
1350         BUG_ON((parent != 0) != (nr_snapids == 2));
1351
1352         return parent
1353                 ? bch2_snapshot_node_create_children(trans, parent,
1354                                 new_snapids, snapshot_subvols, nr_snapids)
1355                 : bch2_snapshot_node_create_tree(trans,
1356                                 new_snapids, snapshot_subvols, nr_snapids);
1357
1358 }
1359
1360 /*
1361  * If we have an unlinked inode in an internal snapshot node, and the inode
1362  * really has been deleted in all child snapshots, how does this get cleaned up?
1363  *
1364  * first there is the problem of how keys that have been overwritten in all
1365  * child snapshots get deleted (unimplemented?), but inodes may perhaps be
1366  * special?
1367  *
1368  * also: unlinked inode in internal snapshot appears to not be getting deleted
1369  * correctly if inode doesn't exist in leaf snapshots
1370  *
1371  * solution:
1372  *
1373  * for a key in an interior snapshot node that needs work to be done that
1374  * requires it to be mutated: iterate over all descendent leaf nodes and copy
1375  * that key to snapshot leaf nodes, where we can mutate it
1376  */
1377
1378 static int delete_dead_snapshots_process_key(struct btree_trans *trans,
1379                                struct btree_iter *iter,
1380                                struct bkey_s_c k,
1381                                snapshot_id_list *deleted,
1382                                snapshot_id_list *equiv_seen,
1383                                struct bpos *last_pos)
1384 {
1385         int ret = bch2_check_key_has_snapshot(trans, iter, k);
1386         if (ret)
1387                 return ret < 0 ? ret : 0;
1388
1389         struct bch_fs *c = trans->c;
1390         u32 equiv = bch2_snapshot_equiv(c, k.k->p.snapshot);
1391         if (!equiv) /* key for invalid snapshot node, but we chose not to delete */
1392                 return 0;
1393
1394         if (!bkey_eq(k.k->p, *last_pos))
1395                 equiv_seen->nr = 0;
1396
1397         if (snapshot_list_has_id(deleted, k.k->p.snapshot))
1398                 return bch2_btree_delete_at(trans, iter,
1399                                             BTREE_UPDATE_internal_snapshot_node);
1400
1401         if (!bpos_eq(*last_pos, k.k->p) &&
1402             snapshot_list_has_id(equiv_seen, equiv))
1403                 return bch2_btree_delete_at(trans, iter,
1404                                             BTREE_UPDATE_internal_snapshot_node);
1405
1406         *last_pos = k.k->p;
1407
1408         ret = snapshot_list_add_nodup(c, equiv_seen, equiv);
1409         if (ret)
1410                 return ret;
1411
1412         /*
1413          * When we have a linear chain of snapshot nodes, we consider
1414          * those to form an equivalence class: we're going to collapse
1415          * them all down to a single node, and keep the leaf-most node -
1416          * which has the same id as the equivalence class id.
1417          *
1418          * If there are multiple keys in different snapshots at the same
1419          * position, we're only going to keep the one in the newest
1420          * snapshot (we delete the others above) - the rest have been
1421          * overwritten and are redundant, and for the key we're going to keep we
1422          * need to move it to the equivalance class ID if it's not there
1423          * already.
1424          */
1425         if (equiv != k.k->p.snapshot) {
1426                 struct bkey_i *new = bch2_bkey_make_mut_noupdate(trans, k);
1427                 int ret = PTR_ERR_OR_ZERO(new);
1428                 if (ret)
1429                         return ret;
1430
1431                 new->k.p.snapshot = equiv;
1432
1433                 struct btree_iter new_iter;
1434                 bch2_trans_iter_init(trans, &new_iter, iter->btree_id, new->k.p,
1435                                      BTREE_ITER_all_snapshots|
1436                                      BTREE_ITER_cached|
1437                                      BTREE_ITER_intent);
1438
1439                 ret =   bch2_btree_iter_traverse(&new_iter) ?:
1440                         bch2_trans_update(trans, &new_iter, new,
1441                                         BTREE_UPDATE_internal_snapshot_node) ?:
1442                         bch2_btree_delete_at(trans, iter,
1443                                         BTREE_UPDATE_internal_snapshot_node);
1444                 bch2_trans_iter_exit(trans, &new_iter);
1445                 if (ret)
1446                         return ret;
1447         }
1448
1449         return 0;
1450 }
1451
1452 static int bch2_snapshot_needs_delete(struct btree_trans *trans, struct bkey_s_c k)
1453 {
1454         struct bkey_s_c_snapshot snap;
1455         u32 children[2];
1456         int ret;
1457
1458         if (k.k->type != KEY_TYPE_snapshot)
1459                 return 0;
1460
1461         snap = bkey_s_c_to_snapshot(k);
1462         if (BCH_SNAPSHOT_DELETED(snap.v) ||
1463             BCH_SNAPSHOT_SUBVOL(snap.v))
1464                 return 0;
1465
1466         children[0] = le32_to_cpu(snap.v->children[0]);
1467         children[1] = le32_to_cpu(snap.v->children[1]);
1468
1469         ret   = bch2_snapshot_live(trans, children[0]) ?:
1470                 bch2_snapshot_live(trans, children[1]);
1471         if (ret < 0)
1472                 return ret;
1473         return !ret;
1474 }
1475
1476 /*
1477  * For a given snapshot, if it doesn't have a subvolume that points to it, and
1478  * it doesn't have child snapshot nodes - it's now redundant and we can mark it
1479  * as deleted.
1480  */
1481 static int bch2_delete_redundant_snapshot(struct btree_trans *trans, struct bkey_s_c k)
1482 {
1483         int ret = bch2_snapshot_needs_delete(trans, k);
1484
1485         return ret <= 0
1486                 ? ret
1487                 : bch2_snapshot_node_set_deleted(trans, k.k->p.offset);
1488 }
1489
1490 static inline u32 bch2_snapshot_nth_parent_skip(struct bch_fs *c, u32 id, u32 n,
1491                                                 snapshot_id_list *skip)
1492 {
1493         rcu_read_lock();
1494         while (snapshot_list_has_id(skip, id))
1495                 id = __bch2_snapshot_parent(c, id);
1496
1497         while (n--) {
1498                 do {
1499                         id = __bch2_snapshot_parent(c, id);
1500                 } while (snapshot_list_has_id(skip, id));
1501         }
1502         rcu_read_unlock();
1503
1504         return id;
1505 }
1506
1507 static int bch2_fix_child_of_deleted_snapshot(struct btree_trans *trans,
1508                                               struct btree_iter *iter, struct bkey_s_c k,
1509                                               snapshot_id_list *deleted)
1510 {
1511         struct bch_fs *c = trans->c;
1512         u32 nr_deleted_ancestors = 0;
1513         struct bkey_i_snapshot *s;
1514         int ret;
1515
1516         if (k.k->type != KEY_TYPE_snapshot)
1517                 return 0;
1518
1519         if (snapshot_list_has_id(deleted, k.k->p.offset))
1520                 return 0;
1521
1522         s = bch2_bkey_make_mut_noupdate_typed(trans, k, snapshot);
1523         ret = PTR_ERR_OR_ZERO(s);
1524         if (ret)
1525                 return ret;
1526
1527         darray_for_each(*deleted, i)
1528                 nr_deleted_ancestors += bch2_snapshot_is_ancestor(c, s->k.p.offset, *i);
1529
1530         if (!nr_deleted_ancestors)
1531                 return 0;
1532
1533         le32_add_cpu(&s->v.depth, -nr_deleted_ancestors);
1534
1535         if (!s->v.depth) {
1536                 s->v.skip[0] = 0;
1537                 s->v.skip[1] = 0;
1538                 s->v.skip[2] = 0;
1539         } else {
1540                 u32 depth = le32_to_cpu(s->v.depth);
1541                 u32 parent = bch2_snapshot_parent(c, s->k.p.offset);
1542
1543                 for (unsigned j = 0; j < ARRAY_SIZE(s->v.skip); j++) {
1544                         u32 id = le32_to_cpu(s->v.skip[j]);
1545
1546                         if (snapshot_list_has_id(deleted, id)) {
1547                                 id = bch2_snapshot_nth_parent_skip(c,
1548                                                         parent,
1549                                                         depth > 1
1550                                                         ? get_random_u32_below(depth - 1)
1551                                                         : 0,
1552                                                         deleted);
1553                                 s->v.skip[j] = cpu_to_le32(id);
1554                         }
1555                 }
1556
1557                 bubble_sort(s->v.skip, ARRAY_SIZE(s->v.skip), cmp_le32);
1558         }
1559
1560         return bch2_trans_update(trans, iter, &s->k_i, 0);
1561 }
1562
1563 int bch2_delete_dead_snapshots(struct bch_fs *c)
1564 {
1565         struct btree_trans *trans;
1566         snapshot_id_list deleted = { 0 };
1567         snapshot_id_list deleted_interior = { 0 };
1568         int ret = 0;
1569
1570         if (!test_and_clear_bit(BCH_FS_need_delete_dead_snapshots, &c->flags))
1571                 return 0;
1572
1573         trans = bch2_trans_get(c);
1574
1575         /*
1576          * For every snapshot node: If we have no live children and it's not
1577          * pointed to by a subvolume, delete it:
1578          */
1579         ret = for_each_btree_key_commit(trans, iter, BTREE_ID_snapshots,
1580                         POS_MIN, 0, k,
1581                         NULL, NULL, 0,
1582                 bch2_delete_redundant_snapshot(trans, k));
1583         bch_err_msg(c, ret, "deleting redundant snapshots");
1584         if (ret)
1585                 goto err;
1586
1587         ret = for_each_btree_key(trans, iter, BTREE_ID_snapshots,
1588                                  POS_MIN, 0, k,
1589                 bch2_snapshot_set_equiv(trans, k));
1590         bch_err_msg(c, ret, "in bch2_snapshots_set_equiv");
1591         if (ret)
1592                 goto err;
1593
1594         ret = for_each_btree_key(trans, iter, BTREE_ID_snapshots,
1595                                  POS_MIN, 0, k, ({
1596                 if (k.k->type != KEY_TYPE_snapshot)
1597                         continue;
1598
1599                 BCH_SNAPSHOT_DELETED(bkey_s_c_to_snapshot(k).v)
1600                         ? snapshot_list_add(c, &deleted, k.k->p.offset)
1601                         : 0;
1602         }));
1603         bch_err_msg(c, ret, "walking snapshots");
1604         if (ret)
1605                 goto err;
1606
1607         for (unsigned btree = 0; btree < BTREE_ID_NR; btree++) {
1608                 struct bpos last_pos = POS_MIN;
1609                 snapshot_id_list equiv_seen = { 0 };
1610                 struct disk_reservation res = { 0 };
1611
1612                 if (!btree_type_has_snapshots(btree))
1613                         continue;
1614
1615                 ret = for_each_btree_key_commit(trans, iter,
1616                                 btree, POS_MIN,
1617                                 BTREE_ITER_prefetch|BTREE_ITER_all_snapshots, k,
1618                                 &res, NULL, BCH_TRANS_COMMIT_no_enospc,
1619                         delete_dead_snapshots_process_key(trans, &iter, k, &deleted,
1620                                                           &equiv_seen, &last_pos));
1621
1622                 bch2_disk_reservation_put(c, &res);
1623                 darray_exit(&equiv_seen);
1624
1625                 bch_err_msg(c, ret, "deleting keys from dying snapshots");
1626                 if (ret)
1627                         goto err;
1628         }
1629
1630         bch2_trans_unlock(trans);
1631         down_write(&c->snapshot_create_lock);
1632
1633         ret = for_each_btree_key(trans, iter, BTREE_ID_snapshots,
1634                                  POS_MIN, 0, k, ({
1635                 u32 snapshot = k.k->p.offset;
1636                 u32 equiv = bch2_snapshot_equiv(c, snapshot);
1637
1638                 equiv != snapshot
1639                         ? snapshot_list_add(c, &deleted_interior, snapshot)
1640                         : 0;
1641         }));
1642
1643         bch_err_msg(c, ret, "walking snapshots");
1644         if (ret)
1645                 goto err_create_lock;
1646
1647         /*
1648          * Fixing children of deleted snapshots can't be done completely
1649          * atomically, if we crash between here and when we delete the interior
1650          * nodes some depth fields will be off:
1651          */
1652         ret = for_each_btree_key_commit(trans, iter, BTREE_ID_snapshots, POS_MIN,
1653                                   BTREE_ITER_intent, k,
1654                                   NULL, NULL, BCH_TRANS_COMMIT_no_enospc,
1655                 bch2_fix_child_of_deleted_snapshot(trans, &iter, k, &deleted_interior));
1656         if (ret)
1657                 goto err_create_lock;
1658
1659         darray_for_each(deleted, i) {
1660                 ret = commit_do(trans, NULL, NULL, 0,
1661                         bch2_snapshot_node_delete(trans, *i));
1662                 bch_err_msg(c, ret, "deleting snapshot %u", *i);
1663                 if (ret)
1664                         goto err_create_lock;
1665         }
1666
1667         darray_for_each(deleted_interior, i) {
1668                 ret = commit_do(trans, NULL, NULL, 0,
1669                         bch2_snapshot_node_delete(trans, *i));
1670                 bch_err_msg(c, ret, "deleting snapshot %u", *i);
1671                 if (ret)
1672                         goto err_create_lock;
1673         }
1674 err_create_lock:
1675         up_write(&c->snapshot_create_lock);
1676 err:
1677         darray_exit(&deleted_interior);
1678         darray_exit(&deleted);
1679         bch2_trans_put(trans);
1680         bch_err_fn(c, ret);
1681         return ret;
1682 }
1683
1684 void bch2_delete_dead_snapshots_work(struct work_struct *work)
1685 {
1686         struct bch_fs *c = container_of(work, struct bch_fs, snapshot_delete_work);
1687
1688         set_worker_desc("bcachefs-delete-dead-snapshots/%s", c->name);
1689
1690         bch2_delete_dead_snapshots(c);
1691         bch2_write_ref_put(c, BCH_WRITE_REF_delete_dead_snapshots);
1692 }
1693
1694 void bch2_delete_dead_snapshots_async(struct bch_fs *c)
1695 {
1696         if (bch2_write_ref_tryget(c, BCH_WRITE_REF_delete_dead_snapshots) &&
1697             !queue_work(c->write_ref_wq, &c->snapshot_delete_work))
1698                 bch2_write_ref_put(c, BCH_WRITE_REF_delete_dead_snapshots);
1699 }
1700
1701 int __bch2_key_has_snapshot_overwrites(struct btree_trans *trans,
1702                                        enum btree_id id,
1703                                        struct bpos pos)
1704 {
1705         struct bch_fs *c = trans->c;
1706         struct btree_iter iter;
1707         struct bkey_s_c k;
1708         int ret;
1709
1710         bch2_trans_iter_init(trans, &iter, id, pos,
1711                              BTREE_ITER_not_extents|
1712                              BTREE_ITER_all_snapshots);
1713         while (1) {
1714                 k = bch2_btree_iter_prev(&iter);
1715                 ret = bkey_err(k);
1716                 if (ret)
1717                         break;
1718
1719                 if (!k.k)
1720                         break;
1721
1722                 if (!bkey_eq(pos, k.k->p))
1723                         break;
1724
1725                 if (bch2_snapshot_is_ancestor(c, k.k->p.snapshot, pos.snapshot)) {
1726                         ret = 1;
1727                         break;
1728                 }
1729         }
1730         bch2_trans_iter_exit(trans, &iter);
1731
1732         return ret;
1733 }
1734
1735 static u32 bch2_snapshot_smallest_child(struct bch_fs *c, u32 id)
1736 {
1737         const struct snapshot_t *s = snapshot_t(c, id);
1738
1739         return s->children[1] ?: s->children[0];
1740 }
1741
1742 static u32 bch2_snapshot_smallest_descendent(struct bch_fs *c, u32 id)
1743 {
1744         u32 child;
1745
1746         while ((child = bch2_snapshot_smallest_child(c, id)))
1747                 id = child;
1748         return id;
1749 }
1750
1751 static int bch2_propagate_key_to_snapshot_leaf(struct btree_trans *trans,
1752                                                enum btree_id btree,
1753                                                struct bkey_s_c interior_k,
1754                                                u32 leaf_id, struct bpos *new_min_pos)
1755 {
1756         struct btree_iter iter;
1757         struct bpos pos = interior_k.k->p;
1758         struct bkey_s_c k;
1759         struct bkey_i *new;
1760         int ret;
1761
1762         pos.snapshot = leaf_id;
1763
1764         bch2_trans_iter_init(trans, &iter, btree, pos, BTREE_ITER_intent);
1765         k = bch2_btree_iter_peek_slot(&iter);
1766         ret = bkey_err(k);
1767         if (ret)
1768                 goto out;
1769
1770         /* key already overwritten in this snapshot? */
1771         if (k.k->p.snapshot != interior_k.k->p.snapshot)
1772                 goto out;
1773
1774         if (bpos_eq(*new_min_pos, POS_MIN)) {
1775                 *new_min_pos = k.k->p;
1776                 new_min_pos->snapshot = leaf_id;
1777         }
1778
1779         new = bch2_bkey_make_mut_noupdate(trans, interior_k);
1780         ret = PTR_ERR_OR_ZERO(new);
1781         if (ret)
1782                 goto out;
1783
1784         new->k.p.snapshot = leaf_id;
1785         ret = bch2_trans_update(trans, &iter, new, 0);
1786 out:
1787         bch2_set_btree_iter_dontneed(&iter);
1788         bch2_trans_iter_exit(trans, &iter);
1789         return ret;
1790 }
1791
1792 int bch2_propagate_key_to_snapshot_leaves(struct btree_trans *trans,
1793                                           enum btree_id btree,
1794                                           struct bkey_s_c k,
1795                                           struct bpos *new_min_pos)
1796 {
1797         struct bch_fs *c = trans->c;
1798         struct bkey_buf sk;
1799         u32 restart_count = trans->restart_count;
1800         int ret = 0;
1801
1802         bch2_bkey_buf_init(&sk);
1803         bch2_bkey_buf_reassemble(&sk, c, k);
1804         k = bkey_i_to_s_c(sk.k);
1805
1806         *new_min_pos = POS_MIN;
1807
1808         for (u32 id = bch2_snapshot_smallest_descendent(c, k.k->p.snapshot);
1809              id < k.k->p.snapshot;
1810              id++) {
1811                 if (!bch2_snapshot_is_ancestor(c, id, k.k->p.snapshot) ||
1812                     !bch2_snapshot_is_leaf(c, id))
1813                         continue;
1814 again:
1815                 ret =   btree_trans_too_many_iters(trans) ?:
1816                         bch2_propagate_key_to_snapshot_leaf(trans, btree, k, id, new_min_pos) ?:
1817                         bch2_trans_commit(trans, NULL, NULL, 0);
1818                 if (ret && bch2_err_matches(ret, BCH_ERR_transaction_restart)) {
1819                         bch2_trans_begin(trans);
1820                         goto again;
1821                 }
1822
1823                 if (ret)
1824                         break;
1825         }
1826
1827         bch2_bkey_buf_exit(&sk, c);
1828
1829         return ret ?: trans_was_restarted(trans, restart_count);
1830 }
1831
1832 static int bch2_check_snapshot_needs_deletion(struct btree_trans *trans, struct bkey_s_c k)
1833 {
1834         struct bch_fs *c = trans->c;
1835         struct bkey_s_c_snapshot snap;
1836         int ret = 0;
1837
1838         if (k.k->type != KEY_TYPE_snapshot)
1839                 return 0;
1840
1841         snap = bkey_s_c_to_snapshot(k);
1842         if (BCH_SNAPSHOT_DELETED(snap.v) ||
1843             bch2_snapshot_equiv(c, k.k->p.offset) != k.k->p.offset ||
1844             (ret = bch2_snapshot_needs_delete(trans, k)) > 0) {
1845                 set_bit(BCH_FS_need_delete_dead_snapshots, &c->flags);
1846                 return 0;
1847         }
1848
1849         return ret;
1850 }
1851
1852 int bch2_snapshots_read(struct bch_fs *c)
1853 {
1854         int ret = bch2_trans_run(c,
1855                 for_each_btree_key(trans, iter, BTREE_ID_snapshots,
1856                                    POS_MIN, 0, k,
1857                         __bch2_mark_snapshot(trans, BTREE_ID_snapshots, 0, bkey_s_c_null, k, 0) ?:
1858                         bch2_snapshot_set_equiv(trans, k) ?:
1859                         bch2_check_snapshot_needs_deletion(trans, k)) ?:
1860                 for_each_btree_key(trans, iter, BTREE_ID_snapshots,
1861                                    POS_MIN, 0, k,
1862                            (set_is_ancestor_bitmap(c, k.k->p.offset), 0)));
1863         bch_err_fn(c, ret);
1864
1865         /*
1866          * It's important that we check if we need to reconstruct snapshots
1867          * before going RW, so we mark that pass as required in the superblock -
1868          * otherwise, we could end up deleting keys with missing snapshot nodes
1869          * instead
1870          */
1871         BUG_ON(!test_bit(BCH_FS_new_fs, &c->flags) &&
1872                test_bit(BCH_FS_may_go_rw, &c->flags));
1873
1874         if (bch2_err_matches(ret, EIO) ||
1875             (c->sb.btrees_lost_data & BIT_ULL(BTREE_ID_snapshots)))
1876                 ret = bch2_run_explicit_recovery_pass_persistent(c, BCH_RECOVERY_PASS_reconstruct_snapshots);
1877
1878         return ret;
1879 }
1880
1881 void bch2_fs_snapshots_exit(struct bch_fs *c)
1882 {
1883         kvfree(rcu_dereference_protected(c->snapshots, true));
1884 }