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