git.sesse.net Git - bcachefs-tools-debian/blob - libbcachefs/subvolume.c

   1 // SPDX-License-Identifier: GPL-2.0
   2
   3 #include "bcachefs.h"
   4 #include "btree_key_cache.h"
   5 #include "btree_update.h"
   6 #include "errcode.h"
   7 #include "error.h"
   8 #include "fs.h"
   9 #include "subvolume.h"
  10
  11 static int bch2_subvolume_delete(struct btree_trans *, u32);
  12
  13 /* Snapshot tree: */
  14
  15 void bch2_snapshot_tree_to_text(struct printbuf *out, struct bch_fs *c,
  16                                 struct bkey_s_c k)
  17 {
  18         struct bkey_s_c_snapshot_tree t = bkey_s_c_to_snapshot_tree(k);
  19
  20         prt_printf(out, "subvol %u root snapshot %u",
  21                    le32_to_cpu(t.v->master_subvol),
  22                    le32_to_cpu(t.v->root_snapshot));
  23 }
  24
  25 int bch2_snapshot_tree_invalid(const struct bch_fs *c, struct bkey_s_c k,
  26                                unsigned flags, struct printbuf *err)
  27 {
  28         if (bkey_gt(k.k->p, POS(0, U32_MAX)) ||
  29             bkey_lt(k.k->p, POS(0, 1))) {
  30                 prt_printf(err, "bad pos");
  31                 return -BCH_ERR_invalid_bkey;
  32         }
  33
  34         return 0;
  35 }
  36
  37 int bch2_snapshot_tree_lookup(struct btree_trans *trans, u32 id,
  38                               struct bch_snapshot_tree *s)
  39 {
  40         return bch2_bkey_get_val_typed(trans, BTREE_ID_snapshot_trees, POS(0, id),
  41                                        BTREE_ITER_WITH_UPDATES, snapshot_tree, s);
  42 }
  43
  44 static struct bkey_i_snapshot_tree *
  45 __snapshot_tree_create(struct btree_trans *trans)
  46 {
  47         struct btree_iter iter;
  48         int ret = bch2_bkey_get_empty_slot(trans, &iter,
  49                         BTREE_ID_snapshot_trees, POS(0, U32_MAX));
  50         struct bkey_i_snapshot_tree *s_t;
  51
  52         if (ret == -BCH_ERR_ENOSPC_btree_slot)
  53                 ret = -BCH_ERR_ENOSPC_snapshot_tree;
  54         if (ret)
  55                 return ERR_PTR(ret);
  56
  57         s_t = bch2_bkey_alloc(trans, &iter, 0, snapshot_tree);
  58         ret = PTR_ERR_OR_ZERO(s_t);
  59         bch2_trans_iter_exit(trans, &iter);
  60         return ret ? ERR_PTR(ret) : s_t;
  61 }
  62
  63 static int snapshot_tree_create(struct btree_trans *trans,
  64                                 u32 root_id, u32 subvol_id, u32 *tree_id)
  65 {
  66         struct bkey_i_snapshot_tree *n_tree =
  67                 __snapshot_tree_create(trans);
  68
  69         if (IS_ERR(n_tree))
  70                 return PTR_ERR(n_tree);
  71
  72         n_tree->v.master_subvol = cpu_to_le32(subvol_id);
  73         n_tree->v.root_snapshot = cpu_to_le32(root_id);
  74         *tree_id = n_tree->k.p.offset;
  75         return 0;
  76 }
  77
  78 /* Snapshot nodes: */
  79
  80 void bch2_snapshot_to_text(struct printbuf *out, struct bch_fs *c,
  81                            struct bkey_s_c k)
  82 {
  83         struct bkey_s_c_snapshot s = bkey_s_c_to_snapshot(k);
  84
  85         prt_printf(out, "is_subvol %llu deleted %llu parent %10u children %10u %10u subvol %u",
  86                BCH_SNAPSHOT_SUBVOL(s.v),
  87                BCH_SNAPSHOT_DELETED(s.v),
  88                le32_to_cpu(s.v->parent),
  89                le32_to_cpu(s.v->children[0]),
  90                le32_to_cpu(s.v->children[1]),
  91                le32_to_cpu(s.v->subvol));
  92 }
  93
  94 int bch2_snapshot_invalid(const struct bch_fs *c, struct bkey_s_c k,
  95                           unsigned flags, struct printbuf *err)
  96 {
  97         struct bkey_s_c_snapshot s;
  98         u32 i, id;
  99
 100         if (bkey_gt(k.k->p, POS(0, U32_MAX)) ||
 101             bkey_lt(k.k->p, POS(0, 1))) {
 102                 prt_printf(err, "bad pos");
 103                 return -BCH_ERR_invalid_bkey;
 104         }
 105
 106         s = bkey_s_c_to_snapshot(k);
 107
 108         id = le32_to_cpu(s.v->parent);
 109         if (id && id <= k.k->p.offset) {
 110                 prt_printf(err, "bad parent node (%u <= %llu)",
 111                        id, k.k->p.offset);
 112                 return -BCH_ERR_invalid_bkey;
 113         }
 114
 115         if (le32_to_cpu(s.v->children[0]) < le32_to_cpu(s.v->children[1])) {
 116                 prt_printf(err, "children not normalized");
 117                 return -BCH_ERR_invalid_bkey;
 118         }
 119
 120         if (s.v->children[0] &&
 121             s.v->children[0] == s.v->children[1]) {
 122                 prt_printf(err, "duplicate child nodes");
 123                 return -BCH_ERR_invalid_bkey;
 124         }
 125
 126         for (i = 0; i < 2; i++) {
 127                 id = le32_to_cpu(s.v->children[i]);
 128
 129                 if (id >= k.k->p.offset) {
 130                         prt_printf(err, "bad child node (%u >= %llu)",
 131                                id, k.k->p.offset);
 132                         return -BCH_ERR_invalid_bkey;
 133                 }
 134         }
 135
 136         return 0;
 137 }
 138
 139 int bch2_mark_snapshot(struct btree_trans *trans,
 140                        enum btree_id btree, unsigned level,
 141                        struct bkey_s_c old, struct bkey_s_c new,
 142                        unsigned flags)
 143 {
 144         struct bch_fs *c = trans->c;
 145         struct snapshot_t *t;
 146
 147         t = genradix_ptr_alloc(&c->snapshots,
 148                                U32_MAX - new.k->p.offset,
 149                                GFP_KERNEL);
 150         if (!t)
 151                 return -BCH_ERR_ENOMEM_mark_snapshot;
 152
 153         if (new.k->type == KEY_TYPE_snapshot) {
 154                 struct bkey_s_c_snapshot s = bkey_s_c_to_snapshot(new);
 155
 156                 t->parent       = le32_to_cpu(s.v->parent);
 157                 t->children[0]  = le32_to_cpu(s.v->children[0]);
 158                 t->children[1]  = le32_to_cpu(s.v->children[1]);
 159                 t->subvol       = BCH_SNAPSHOT_SUBVOL(s.v) ? le32_to_cpu(s.v->subvol) : 0;
 160                 t->tree         = le32_to_cpu(s.v->tree);
 161         } else {
 162                 t->parent       = 0;
 163                 t->children[0]  = 0;
 164                 t->children[1]  = 0;
 165                 t->subvol       = 0;
 166                 t->tree         = 0;
 167         }
 168
 169         return 0;
 170 }
 171
 172 static int snapshot_lookup(struct btree_trans *trans, u32 id,
 173                            struct bch_snapshot *s)
 174 {
 175         return bch2_bkey_get_val_typed(trans, BTREE_ID_snapshots, POS(0, id),
 176                                        BTREE_ITER_WITH_UPDATES, snapshot, s);
 177 }
 178
 179 static int snapshot_live(struct btree_trans *trans, u32 id)
 180 {
 181         struct bch_snapshot v;
 182         int ret;
 183
 184         if (!id)
 185                 return 0;
 186
 187         ret = snapshot_lookup(trans, id, &v);
 188         if (ret == -ENOENT)
 189                 bch_err(trans->c, "snapshot node %u not found", id);
 190         if (ret)
 191                 return ret;
 192
 193         return !BCH_SNAPSHOT_DELETED(&v);
 194 }
 195
 196 static int bch2_snapshot_set_equiv(struct btree_trans *trans, struct bkey_s_c k)
 197 {
 198         struct bch_fs *c = trans->c;
 199         unsigned i, nr_live = 0, live_idx = 0;
 200         struct bkey_s_c_snapshot snap;
 201         u32 id = k.k->p.offset, child[2];
 202
 203         if (k.k->type != KEY_TYPE_snapshot)
 204                 return 0;
 205
 206         snap = bkey_s_c_to_snapshot(k);
 207
 208         child[0] = le32_to_cpu(snap.v->children[0]);
 209         child[1] = le32_to_cpu(snap.v->children[1]);
 210
 211         for (i = 0; i < 2; i++) {
 212                 int ret = snapshot_live(trans, child[i]);
 213
 214                 if (ret < 0)
 215                         return ret;
 216
 217                 if (ret)
 218                         live_idx = i;
 219                 nr_live += ret;
 220         }
 221
 222         snapshot_t(c, id)->equiv = nr_live == 1
 223                 ? snapshot_t(c, child[live_idx])->equiv
 224                 : id;
 225         return 0;
 226 }
 227
 228 /* fsck: */
 229
 230 static u32 bch2_snapshot_child(struct bch_fs *c, u32 id, unsigned child)
 231 {
 232         return snapshot_t(c, id)->children[child];
 233 }
 234
 235 static u32 bch2_snapshot_left_child(struct bch_fs *c, u32 id)
 236 {
 237         return bch2_snapshot_child(c, id, 0);
 238 }
 239
 240 static u32 bch2_snapshot_right_child(struct bch_fs *c, u32 id)
 241 {
 242         return bch2_snapshot_child(c, id, 1);
 243 }
 244
 245 static u32 bch2_snapshot_tree_next(struct bch_fs *c, u32 id)
 246 {
 247         u32 n, parent;
 248
 249         n = bch2_snapshot_left_child(c, id);
 250         if (n)
 251                 return n;
 252
 253         while ((parent = bch2_snapshot_parent(c, id))) {
 254                 n = bch2_snapshot_right_child(c, parent);
 255                 if (n && n != id)
 256                         return n;
 257                 id = parent;
 258         }
 259
 260         return 0;
 261 }
 262
 263 static u32 bch2_snapshot_tree_oldest_subvol(struct bch_fs *c, u32 snapshot_root)
 264 {
 265         u32 id = snapshot_root;
 266         u32 subvol = 0, s;
 267
 268         while (id) {
 269                 s = snapshot_t(c, id)->subvol;
 270
 271                 if (s && (!subvol || s < subvol))
 272                         subvol = s;
 273
 274                 id = bch2_snapshot_tree_next(c, id);
 275         }
 276
 277         return subvol;
 278 }
 279
 280 static int bch2_snapshot_tree_master_subvol(struct btree_trans *trans,
 281                                             u32 snapshot_root, u32 *subvol_id)
 282 {
 283         struct bch_fs *c = trans->c;
 284         struct btree_iter iter;
 285         struct bkey_s_c k;
 286         struct bkey_s_c_subvolume s;
 287         int ret;
 288
 289         for_each_btree_key_norestart(trans, iter, BTREE_ID_subvolumes, POS_MIN,
 290                                      0, k, ret) {
 291                 if (k.k->type != KEY_TYPE_subvolume)
 292                         continue;
 293
 294                 s = bkey_s_c_to_subvolume(k);
 295                 if (!bch2_snapshot_is_ancestor(c, le32_to_cpu(s.v->snapshot), snapshot_root))
 296                         continue;
 297                 if (!BCH_SUBVOLUME_SNAP(s.v)) {
 298                         *subvol_id = s.k->p.offset;
 299                         goto found;
 300                 }
 301         }
 302         ret = ret ?: -ENOENT;
 303 found:
 304         bch2_trans_iter_exit(trans, &iter);
 305
 306         if (ret == -ENOENT) {
 307                 struct bkey_i_subvolume *s;
 308
 309                 *subvol_id = bch2_snapshot_tree_oldest_subvol(c, snapshot_root);
 310
 311                 s = bch2_bkey_get_mut_typed(trans, &iter,
 312                                             BTREE_ID_subvolumes, POS(0, *subvol_id),
 313                                             0, subvolume);
 314                 ret = PTR_ERR_OR_ZERO(s);
 315                 if (ret)
 316                         return ret;
 317
 318                 SET_BCH_SUBVOLUME_SNAP(&s->v, false);
 319         }
 320
 321         return ret;
 322 }
 323
 324 static int check_snapshot_tree(struct btree_trans *trans,
 325                                struct btree_iter *iter,
 326                                struct bkey_s_c k)
 327 {
 328         struct bch_fs *c = trans->c;
 329         struct bkey_s_c_snapshot_tree st;
 330         struct bch_snapshot s;
 331         struct bch_subvolume subvol;
 332         struct printbuf buf = PRINTBUF;
 333         u32 root_id;
 334         int ret;
 335
 336         if (k.k->type != KEY_TYPE_snapshot_tree)
 337                 return 0;
 338
 339         st = bkey_s_c_to_snapshot_tree(k);
 340         root_id = le32_to_cpu(st.v->root_snapshot);
 341
 342         ret = snapshot_lookup(trans, root_id, &s);
 343         if (ret && !bch2_err_matches(ret, ENOENT))
 344                 goto err;
 345
 346         if (fsck_err_on(ret ||
 347                         root_id != bch2_snapshot_root(c, root_id) ||
 348                         st.k->p.offset != le32_to_cpu(s.tree),
 349                         c,
 350                         "snapshot tree points to missing/incorrect snapshot:\n  %s",
 351                         (bch2_bkey_val_to_text(&buf, c, st.s_c), buf.buf))) {
 352                 ret = bch2_btree_delete_at(trans, iter, 0);
 353                 goto err;
 354         }
 355
 356         ret = bch2_subvolume_get(trans, le32_to_cpu(st.v->master_subvol),
 357                                  false, 0, &subvol);
 358         if (ret && !bch2_err_matches(ret, ENOENT))
 359                 goto err;
 360
 361         if (fsck_err_on(ret ||
 362                         !bch2_snapshot_is_ancestor(c,
 363                                                    le32_to_cpu(subvol.snapshot),
 364                                                    root_id) ||
 365                         !BCH_SUBVOLUME_SNAP(&subvol), c,
 366                         "snapshot tree points to missing/incorrect subvolume:\n  %s",
 367                         (printbuf_reset(&buf),
 368                          bch2_bkey_val_to_text(&buf, c, st.s_c), buf.buf))) {
 369                 struct bkey_i_snapshot_tree *u;
 370                 u32 subvol_id;
 371
 372                 ret = bch2_snapshot_tree_master_subvol(trans, root_id, &subvol_id);
 373                 if (ret)
 374                         goto err;
 375
 376                 u = bch2_bkey_make_mut_typed(trans, iter, k, 0, snapshot_tree);
 377                 ret = PTR_ERR_OR_ZERO(u);
 378                 if (ret)
 379                         goto err;
 380
 381                 u->v.master_subvol = cpu_to_le32(subvol_id);
 382                 st = snapshot_tree_i_to_s_c(u);
 383         }
 384 err:
 385 fsck_err:
 386         printbuf_exit(&buf);
 387         return ret;
 388 }
 389
 390 /*
 391  * For each snapshot_tree, make sure it points to the root of a snapshot tree
 392  * and that snapshot entry points back to it, or delete it.
 393  *
 394  * And, make sure it points to a subvolume within that snapshot tree, or correct
 395  * it to point to the oldest subvolume within that snapshot tree.
 396  */
 397 int bch2_fs_check_snapshot_trees(struct bch_fs *c)
 398 {
 399         struct btree_iter iter;
 400         struct bkey_s_c k;
 401         int ret;
 402
 403         ret = bch2_trans_run(c,
 404                 for_each_btree_key_commit(&trans, iter,
 405                         BTREE_ID_snapshot_trees, POS_MIN,
 406                         BTREE_ITER_PREFETCH, k,
 407                         NULL, NULL, BTREE_INSERT_LAZY_RW|BTREE_INSERT_NOFAIL,
 408                 check_snapshot_tree(&trans, &iter, k)));
 409
 410         if (ret)
 411                 bch_err(c, "error %i checking snapshot trees", ret);
 412         return ret;
 413 }
 414
 415 /*
 416  * Look up snapshot tree for @tree_id and find root,
 417  * make sure @snap_id is a descendent:
 418  */
 419 static int snapshot_tree_ptr_good(struct btree_trans *trans,
 420                                   u32 snap_id, u32 tree_id)
 421 {
 422         struct bch_snapshot_tree s_t;
 423         int ret = bch2_snapshot_tree_lookup(trans, tree_id, &s_t);
 424
 425         if (ret)
 426                 return ret;
 427
 428         return bch2_snapshot_is_ancestor(trans->c, snap_id, le32_to_cpu(s_t.root_snapshot));
 429 }
 430
 431 /*
 432  * snapshot_tree pointer was incorrect: look up root snapshot node, make sure
 433  * its snapshot_tree pointer is correct (allocate new one if necessary), then
 434  * update this node's pointer to root node's pointer:
 435  */
 436 static int snapshot_tree_ptr_repair(struct btree_trans *trans,
 437                                     struct btree_iter *iter,
 438                                     struct bkey_s_c_snapshot *s)
 439 {
 440         struct bch_fs *c = trans->c;
 441         struct btree_iter root_iter;
 442         struct bch_snapshot_tree s_t;
 443         struct bkey_s_c_snapshot root;
 444         struct bkey_i_snapshot *u;
 445         u32 root_id = bch2_snapshot_root(c, s->k->p.offset), tree_id;
 446         int ret;
 447
 448         root = bch2_bkey_get_iter_typed(trans, &root_iter,
 449                                BTREE_ID_snapshots, POS(0, root_id),
 450                                BTREE_ITER_WITH_UPDATES, snapshot);
 451         ret = bkey_err(root);
 452         if (ret)
 453                 goto err;
 454
 455         tree_id = le32_to_cpu(root.v->tree);
 456
 457         ret = bch2_snapshot_tree_lookup(trans, tree_id, &s_t);
 458         if (ret)
 459                 return ret;
 460
 461         if (le32_to_cpu(s_t.root_snapshot) != root_id) {
 462                 u = bch2_bkey_make_mut_typed(trans, &root_iter, root.s_c, 0, snapshot);
 463                 ret =   PTR_ERR_OR_ZERO(u) ?:
 464                         snapshot_tree_create(trans, root_id,
 465                                 bch2_snapshot_tree_oldest_subvol(c, root_id),
 466                                 &tree_id);
 467                 if (ret)
 468                         goto err;
 469
 470                 u->v.tree = cpu_to_le32(tree_id);
 471                 if (s->k->p.snapshot == root_id)
 472                         *s = snapshot_i_to_s_c(u);
 473         }
 474
 475         if (s->k->p.snapshot != root_id) {
 476                 u = bch2_bkey_make_mut_typed(trans, iter, s->s_c, 0, snapshot);
 477                 ret = PTR_ERR_OR_ZERO(u);
 478                 if (ret)
 479                         goto err;
 480
 481                 u->v.tree = cpu_to_le32(tree_id);
 482                 *s = snapshot_i_to_s_c(u);
 483         }
 484 err:
 485         bch2_trans_iter_exit(trans, &root_iter);
 486         return ret;
 487 }
 488
 489 static int check_snapshot(struct btree_trans *trans,
 490                           struct btree_iter *iter,
 491                           struct bkey_s_c k)
 492 {
 493         struct bch_fs *c = trans->c;
 494         struct bkey_s_c_snapshot s;
 495         struct bch_subvolume subvol;
 496         struct bch_snapshot v;
 497         struct printbuf buf = PRINTBUF;
 498         bool should_have_subvol;
 499         u32 i, id;
 500         int ret = 0;
 501
 502         if (k.k->type != KEY_TYPE_snapshot)
 503                 return 0;
 504
 505         s = bkey_s_c_to_snapshot(k);
 506         id = le32_to_cpu(s.v->parent);
 507         if (id) {
 508                 ret = snapshot_lookup(trans, id, &v);
 509                 if (ret == -ENOENT)
 510                         bch_err(c, "snapshot with nonexistent parent:\n  %s",
 511                                 (bch2_bkey_val_to_text(&buf, c, s.s_c), buf.buf));
 512                 if (ret)
 513                         goto err;
 514
 515                 if (le32_to_cpu(v.children[0]) != s.k->p.offset &&
 516                     le32_to_cpu(v.children[1]) != s.k->p.offset) {
 517                         bch_err(c, "snapshot parent %u missing pointer to child %llu",
 518                                 id, s.k->p.offset);
 519                         ret = -EINVAL;
 520                         goto err;
 521                 }
 522         }
 523
 524         for (i = 0; i < 2 && s.v->children[i]; i++) {
 525                 id = le32_to_cpu(s.v->children[i]);
 526
 527                 ret = snapshot_lookup(trans, id, &v);
 528                 if (ret == -ENOENT)
 529                         bch_err(c, "snapshot node %llu has nonexistent child %u",
 530                                 s.k->p.offset, id);
 531                 if (ret)
 532                         goto err;
 533
 534                 if (le32_to_cpu(v.parent) != s.k->p.offset) {
 535                         bch_err(c, "snapshot child %u has wrong parent (got %u should be %llu)",
 536                                 id, le32_to_cpu(v.parent), s.k->p.offset);
 537                         ret = -EINVAL;
 538                         goto err;
 539                 }
 540         }
 541
 542         should_have_subvol = BCH_SNAPSHOT_SUBVOL(s.v) &&
 543                 !BCH_SNAPSHOT_DELETED(s.v);
 544
 545         if (should_have_subvol) {
 546                 id = le32_to_cpu(s.v->subvol);
 547                 ret = bch2_subvolume_get(trans, id, 0, false, &subvol);
 548                 if (ret == -ENOENT)
 549                         bch_err(c, "snapshot points to nonexistent subvolume:\n  %s",
 550                                 (bch2_bkey_val_to_text(&buf, c, s.s_c), buf.buf));
 551                 if (ret)
 552                         goto err;
 553
 554                 if (BCH_SNAPSHOT_SUBVOL(s.v) != (le32_to_cpu(subvol.snapshot) == s.k->p.offset)) {
 555                         bch_err(c, "snapshot node %llu has wrong BCH_SNAPSHOT_SUBVOL",
 556                                 s.k->p.offset);
 557                         ret = -EINVAL;
 558                         goto err;
 559                 }
 560         } else {
 561                 if (fsck_err_on(s.v->subvol, c, "snapshot should not point to subvol:\n  %s",
 562                                 (bch2_bkey_val_to_text(&buf, c, s.s_c), buf.buf))) {
 563                         struct bkey_i_snapshot *u = bch2_trans_kmalloc(trans, sizeof(*u));
 564
 565                         ret = PTR_ERR_OR_ZERO(u);
 566                         if (ret)
 567                                 goto err;
 568
 569                         bkey_reassemble(&u->k_i, s.s_c);
 570                         u->v.subvol = 0;
 571                         ret = bch2_trans_update(trans, iter, &u->k_i, 0);
 572                         if (ret)
 573                                 goto err;
 574
 575                         s = snapshot_i_to_s_c(u);
 576                 }
 577         }
 578
 579         ret = snapshot_tree_ptr_good(trans, s.k->p.offset, le32_to_cpu(s.v->tree));
 580         if (ret < 0)
 581                 goto err;
 582
 583         if (fsck_err_on(!ret, c, "snapshot points to missing/incorrect tree:\n  %s",
 584                         (bch2_bkey_val_to_text(&buf, c, s.s_c), buf.buf))) {
 585                 ret = snapshot_tree_ptr_repair(trans, iter, &s);
 586                 if (ret)
 587                         goto err;
 588         }
 589
 590         if (BCH_SNAPSHOT_DELETED(s.v))
 591                 set_bit(BCH_FS_HAVE_DELETED_SNAPSHOTS, &c->flags);
 592 err:
 593 fsck_err:
 594         printbuf_exit(&buf);
 595         return ret;
 596 }
 597
 598 int bch2_fs_check_snapshots(struct bch_fs *c)
 599 {
 600         struct btree_iter iter;
 601         struct bkey_s_c k;
 602         int ret;
 603
 604         ret = bch2_trans_run(c,
 605                 for_each_btree_key_commit(&trans, iter,
 606                         BTREE_ID_snapshots, POS_MIN,
 607                         BTREE_ITER_PREFETCH, k,
 608                         NULL, NULL, BTREE_INSERT_LAZY_RW|BTREE_INSERT_NOFAIL,
 609                 check_snapshot(&trans, &iter, k)));
 610
 611         if (ret)
 612                 bch_err(c, "error %i checking snapshots", ret);
 613         return ret;
 614 }
 615
 616 static int check_subvol(struct btree_trans *trans,
 617                         struct btree_iter *iter,
 618                         struct bkey_s_c k)
 619 {
 620         struct bch_fs *c = trans->c;
 621         struct bkey_s_c_subvolume subvol;
 622         struct bch_snapshot snapshot;
 623         unsigned snapid;
 624         int ret = 0;
 625
 626         if (k.k->type != KEY_TYPE_subvolume)
 627                 return 0;
 628
 629         subvol = bkey_s_c_to_subvolume(k);
 630         snapid = le32_to_cpu(subvol.v->snapshot);
 631         ret = snapshot_lookup(trans, snapid, &snapshot);
 632
 633         if (ret == -ENOENT)
 634                 bch_err(c, "subvolume %llu points to nonexistent snapshot %u",
 635                         k.k->p.offset, snapid);
 636         if (ret)
 637                 return ret;
 638
 639         if (BCH_SUBVOLUME_UNLINKED(subvol.v)) {
 640                 bch2_fs_lazy_rw(c);
 641
 642                 ret = bch2_subvolume_delete(trans, iter->pos.offset);
 643                 if (ret)
 644                         bch_err(c, "error deleting subvolume %llu: %s",
 645                                 iter->pos.offset, bch2_err_str(ret));
 646                 return ret ?: -BCH_ERR_transaction_restart_nested;
 647         }
 648
 649         if (!BCH_SUBVOLUME_SNAP(subvol.v)) {
 650                 u32 snapshot_root = bch2_snapshot_root(c, le32_to_cpu(subvol.v->snapshot));
 651                 struct bch_snapshot_tree st;
 652
 653                 ret = bch2_snapshot_tree_lookup(trans, snapshot_root, &st);
 654                 if (ret)
 655                         return ret;
 656
 657                 if (fsck_err_on(le32_to_cpu(st.master_subvol) != subvol.k->p.offset, c,
 658                                 "subvolume %llu is not set as snapshot but is not master subvolume",
 659                                 k.k->p.offset)) {
 660                         struct bkey_i_subvolume *s =
 661                                 bch2_bkey_make_mut_typed(trans, iter, subvol.s_c, 0, subvolume);
 662                         ret = PTR_ERR_OR_ZERO(s);
 663                         if (ret)
 664                                 return ret;
 665
 666                         SET_BCH_SUBVOLUME_SNAP(&s->v, true);
 667                 }
 668         }
 669
 670 fsck_err:
 671         return ret;
 672 }
 673
 674 int bch2_fs_check_subvols(struct bch_fs *c)
 675 {
 676         struct btree_trans trans;
 677         struct btree_iter iter;
 678         struct bkey_s_c k;
 679         int ret;
 680
 681         bch2_trans_init(&trans, c, 0, 0);
 682
 683         ret = for_each_btree_key_commit(&trans, iter,
 684                         BTREE_ID_subvolumes, POS_MIN, BTREE_ITER_PREFETCH, k,
 685                         NULL, NULL, BTREE_INSERT_LAZY_RW|BTREE_INSERT_NOFAIL,
 686                 check_subvol(&trans, &iter, k));
 687
 688         bch2_trans_exit(&trans);
 689
 690         return ret;
 691 }
 692
 693 void bch2_fs_snapshots_exit(struct bch_fs *c)
 694 {
 695         genradix_free(&c->snapshots);
 696 }
 697
 698 int bch2_fs_snapshots_start(struct bch_fs *c)
 699 {
 700         struct btree_trans trans;
 701         struct btree_iter iter;
 702         struct bkey_s_c k;
 703         int ret = 0;
 704
 705         bch2_trans_init(&trans, c, 0, 0);
 706
 707         for_each_btree_key2(&trans, iter, BTREE_ID_snapshots,
 708                            POS_MIN, 0, k,
 709                 bch2_mark_snapshot(&trans, BTREE_ID_snapshots, 0, bkey_s_c_null, k, 0) ?:
 710                 bch2_snapshot_set_equiv(&trans, k));
 711
 712         bch2_trans_exit(&trans);
 713
 714         if (ret)
 715                 bch_err(c, "error starting snapshots: %s", bch2_err_str(ret));
 716         return ret;
 717 }
 718
 719 /*
 720  * Mark a snapshot as deleted, for future cleanup:
 721  */
 722 static int bch2_snapshot_node_set_deleted(struct btree_trans *trans, u32 id)
 723 {
 724         struct btree_iter iter;
 725         struct bkey_i_snapshot *s;
 726         int ret = 0;
 727
 728         s = bch2_bkey_get_mut_typed(trans, &iter,
 729                                     BTREE_ID_snapshots, POS(0, id),
 730                                     0, snapshot);
 731         ret = PTR_ERR_OR_ZERO(s);
 732         if (unlikely(ret)) {
 733                 bch2_fs_inconsistent_on(ret == -ENOENT, trans->c, "missing snapshot %u", id);
 734                 return ret;
 735         }
 736
 737         /* already deleted? */
 738         if (BCH_SNAPSHOT_DELETED(&s->v))
 739                 goto err;
 740
 741         SET_BCH_SNAPSHOT_DELETED(&s->v, true);
 742         SET_BCH_SNAPSHOT_SUBVOL(&s->v, false);
 743         s->v.subvol = 0;
 744 err:
 745         bch2_trans_iter_exit(trans, &iter);
 746         return ret;
 747 }
 748
 749 static int bch2_snapshot_node_delete(struct btree_trans *trans, u32 id)
 750 {
 751         struct bch_fs *c = trans->c;
 752         struct btree_iter iter, p_iter = (struct btree_iter) { NULL };
 753         struct btree_iter tree_iter = (struct btree_iter) { NULL };
 754         struct bkey_s_c_snapshot s;
 755         u32 parent_id;
 756         unsigned i;
 757         int ret = 0;
 758
 759         s = bch2_bkey_get_iter_typed(trans, &iter, BTREE_ID_snapshots, POS(0, id),
 760                                      BTREE_ITER_INTENT, snapshot);
 761         ret = bkey_err(s);
 762         bch2_fs_inconsistent_on(ret == -ENOENT, c, "missing snapshot %u", id);
 763
 764         if (ret)
 765                 goto err;
 766
 767         BUG_ON(!BCH_SNAPSHOT_DELETED(s.v));
 768         parent_id = le32_to_cpu(s.v->parent);
 769
 770         if (parent_id) {
 771                 struct bkey_i_snapshot *parent;
 772
 773                 parent = bch2_bkey_get_mut_typed(trans, &p_iter,
 774                                      BTREE_ID_snapshots, POS(0, parent_id),
 775                                      0, snapshot);
 776                 ret = PTR_ERR_OR_ZERO(parent);
 777                 if (unlikely(ret)) {
 778                         bch2_fs_inconsistent_on(ret == -ENOENT, c, "missing snapshot %u", parent_id);
 779                         goto err;
 780                 }
 781
 782                 for (i = 0; i < 2; i++)
 783                         if (le32_to_cpu(parent->v.children[i]) == id)
 784                                 break;
 785
 786                 if (i == 2)
 787                         bch_err(c, "snapshot %u missing child pointer to %u",
 788                                 parent_id, id);
 789                 else
 790                         parent->v.children[i] = 0;
 791
 792                 if (le32_to_cpu(parent->v.children[0]) <
 793                     le32_to_cpu(parent->v.children[1]))
 794                         swap(parent->v.children[0],
 795                              parent->v.children[1]);
 796         } else {
 797                 /*
 798                  * We're deleting the root of a snapshot tree: update the
 799                  * snapshot_tree entry to point to the new root, or delete it if
 800                  * this is the last snapshot ID in this tree:
 801                  */
 802                 struct bkey_i_snapshot_tree *s_t;
 803
 804                 BUG_ON(s.v->children[1]);
 805
 806                 s_t = bch2_bkey_get_mut_typed(trans, &tree_iter,
 807                                 BTREE_ID_snapshot_trees, POS(0, le32_to_cpu(s.v->tree)),
 808                                 0, snapshot_tree);
 809                 ret = PTR_ERR_OR_ZERO(s_t);
 810                 if (ret)
 811                         goto err;
 812
 813                 if (s.v->children[0]) {
 814                         s_t->v.root_snapshot = cpu_to_le32(s.v->children[0]);
 815                 } else {
 816                         s_t->k.type = KEY_TYPE_deleted;
 817                         set_bkey_val_u64s(&s_t->k, 0);
 818                 }
 819         }
 820
 821         ret = bch2_btree_delete_at(trans, &iter, 0);
 822 err:
 823         bch2_trans_iter_exit(trans, &tree_iter);
 824         bch2_trans_iter_exit(trans, &p_iter);
 825         bch2_trans_iter_exit(trans, &iter);
 826         return ret;
 827 }
 828
 829 static int create_snapids(struct btree_trans *trans, u32 parent, u32 tree,
 830                           u32 *new_snapids,
 831                           u32 *snapshot_subvols,
 832                           unsigned nr_snapids)
 833 {
 834         struct btree_iter iter;
 835         struct bkey_i_snapshot *n;
 836         struct bkey_s_c k;
 837         unsigned i;
 838         int ret;
 839
 840         bch2_trans_iter_init(trans, &iter, BTREE_ID_snapshots,
 841                              POS_MIN, BTREE_ITER_INTENT);
 842         k = bch2_btree_iter_peek(&iter);
 843         ret = bkey_err(k);
 844         if (ret)
 845                 goto err;
 846
 847         for (i = 0; i < nr_snapids; i++) {
 848                 k = bch2_btree_iter_prev_slot(&iter);
 849                 ret = bkey_err(k);
 850                 if (ret)
 851                         goto err;
 852
 853                 if (!k.k || !k.k->p.offset) {
 854                         ret = -BCH_ERR_ENOSPC_snapshot_create;
 855                         goto err;
 856                 }
 857
 858                 n = bch2_bkey_alloc(trans, &iter, 0, snapshot);
 859                 ret = PTR_ERR_OR_ZERO(n);
 860                 if (ret)
 861                         goto err;
 862
 863                 n->v.flags      = 0;
 864                 n->v.parent     = cpu_to_le32(parent);
 865                 n->v.subvol     = cpu_to_le32(snapshot_subvols[i]);
 866                 n->v.tree       = cpu_to_le32(tree);
 867                 SET_BCH_SNAPSHOT_SUBVOL(&n->v, true);
 868
 869                 ret = bch2_mark_snapshot(trans, BTREE_ID_snapshots, 0,
 870                                          bkey_s_c_null, bkey_i_to_s_c(&n->k_i), 0);
 871                 if (ret)
 872                         goto err;
 873
 874                 new_snapids[i]  = iter.pos.offset;
 875         }
 876 err:
 877         bch2_trans_iter_exit(trans, &iter);
 878         return ret;
 879 }
 880
 881 /*
 882  * Create new snapshot IDs as children of an existing snapshot ID:
 883  */
 884 static int bch2_snapshot_node_create_children(struct btree_trans *trans, u32 parent,
 885                               u32 *new_snapids,
 886                               u32 *snapshot_subvols,
 887                               unsigned nr_snapids)
 888 {
 889         struct btree_iter iter;
 890         struct bkey_i_snapshot *n_parent;
 891         int ret = 0;
 892
 893         n_parent = bch2_bkey_get_mut_typed(trans, &iter,
 894                         BTREE_ID_snapshots, POS(0, parent),
 895                         0, snapshot);
 896         ret = PTR_ERR_OR_ZERO(n_parent);
 897         if (unlikely(ret)) {
 898                 if (ret == -ENOENT)
 899                         bch_err(trans->c, "snapshot %u not found", parent);
 900                 return ret;
 901         }
 902
 903         if (n_parent->v.children[0] || n_parent->v.children[1]) {
 904                 bch_err(trans->c, "Trying to add child snapshot nodes to parent that already has children");
 905                 ret = -EINVAL;
 906                 goto err;
 907         }
 908
 909         ret = create_snapids(trans, parent, le32_to_cpu(n_parent->v.tree),
 910                              new_snapids, snapshot_subvols, nr_snapids);
 911         if (ret)
 912                 goto err;
 913
 914         n_parent->v.children[0] = cpu_to_le32(new_snapids[0]);
 915         n_parent->v.children[1] = cpu_to_le32(new_snapids[1]);
 916         n_parent->v.subvol = 0;
 917         SET_BCH_SNAPSHOT_SUBVOL(&n_parent->v, false);
 918 err:
 919         bch2_trans_iter_exit(trans, &iter);
 920         return ret;
 921 }
 922
 923 /*
 924  * Create a snapshot node that is the root of a new tree:
 925  */
 926 static int bch2_snapshot_node_create_tree(struct btree_trans *trans,
 927                               u32 *new_snapids,
 928                               u32 *snapshot_subvols,
 929                               unsigned nr_snapids)
 930 {
 931         struct bkey_i_snapshot_tree *n_tree;
 932         int ret;
 933
 934         n_tree = __snapshot_tree_create(trans);
 935         ret =   PTR_ERR_OR_ZERO(n_tree) ?:
 936                 create_snapids(trans, 0, n_tree->k.p.offset,
 937                              new_snapids, snapshot_subvols, nr_snapids);
 938         if (ret)
 939                 return ret;
 940
 941         n_tree->v.master_subvol = cpu_to_le32(snapshot_subvols[0]);
 942         n_tree->v.root_snapshot = cpu_to_le32(new_snapids[0]);
 943         return 0;
 944 }
 945
 946 int bch2_snapshot_node_create(struct btree_trans *trans, u32 parent,
 947                               u32 *new_snapids,
 948                               u32 *snapshot_subvols,
 949                               unsigned nr_snapids)
 950 {
 951         BUG_ON((parent == 0) != (nr_snapids == 1));
 952         BUG_ON((parent != 0) != (nr_snapids == 2));
 953
 954         return parent
 955                 ? bch2_snapshot_node_create_children(trans, parent,
 956                                 new_snapids, snapshot_subvols, nr_snapids)
 957                 : bch2_snapshot_node_create_tree(trans,
 958                                 new_snapids, snapshot_subvols, nr_snapids);
 959
 960 }
 961
 962 static int snapshot_delete_key(struct btree_trans *trans,
 963                                struct btree_iter *iter,
 964                                struct bkey_s_c k,
 965                                snapshot_id_list *deleted,
 966                                snapshot_id_list *equiv_seen,
 967                                struct bpos *last_pos)
 968 {
 969         struct bch_fs *c = trans->c;
 970         u32 equiv = snapshot_t(c, k.k->p.snapshot)->equiv;
 971
 972         if (!bkey_eq(k.k->p, *last_pos))
 973                 equiv_seen->nr = 0;
 974         *last_pos = k.k->p;
 975
 976         if (snapshot_list_has_id(deleted, k.k->p.snapshot) ||
 977             snapshot_list_has_id(equiv_seen, equiv)) {
 978                 return bch2_btree_delete_at(trans, iter,
 979                                             BTREE_UPDATE_INTERNAL_SNAPSHOT_NODE);
 980         } else {
 981                 return snapshot_list_add(c, equiv_seen, equiv);
 982         }
 983 }
 984
 985 static int bch2_delete_redundant_snapshot(struct btree_trans *trans, struct btree_iter *iter,
 986                                           struct bkey_s_c k)
 987 {
 988         struct bkey_s_c_snapshot snap;
 989         u32 children[2];
 990         int ret;
 991
 992         if (k.k->type != KEY_TYPE_snapshot)
 993                 return 0;
 994
 995         snap = bkey_s_c_to_snapshot(k);
 996         if (BCH_SNAPSHOT_DELETED(snap.v) ||
 997             BCH_SNAPSHOT_SUBVOL(snap.v))
 998                 return 0;
 999
1000         children[0] = le32_to_cpu(snap.v->children[0]);
1001         children[1] = le32_to_cpu(snap.v->children[1]);
1002
1003         ret   = snapshot_live(trans, children[0]) ?:
1004                 snapshot_live(trans, children[1]);
1005         if (ret < 0)
1006                 return ret;
1007
1008         if (!ret)
1009                 return bch2_snapshot_node_set_deleted(trans, k.k->p.offset);
1010         return 0;
1011 }
1012
1013 int bch2_delete_dead_snapshots(struct bch_fs *c)
1014 {
1015         struct btree_trans trans;
1016         struct btree_iter iter;
1017         struct bkey_s_c k;
1018         struct bkey_s_c_snapshot snap;
1019         snapshot_id_list deleted = { 0 };
1020         u32 i, id;
1021         int ret = 0;
1022
1023         if (!test_bit(BCH_FS_HAVE_DELETED_SNAPSHOTS, &c->flags))
1024                 return 0;
1025
1026         if (!test_bit(BCH_FS_STARTED, &c->flags)) {
1027                 ret = bch2_fs_read_write_early(c);
1028                 if (ret) {
1029                         bch_err(c, "error deleleting dead snapshots: error going rw: %s", bch2_err_str(ret));
1030                         return ret;
1031                 }
1032         }
1033
1034         bch2_trans_init(&trans, c, 0, 0);
1035
1036         /*
1037          * For every snapshot node: If we have no live children and it's not
1038          * pointed to by a subvolume, delete it:
1039          */
1040         ret = for_each_btree_key_commit(&trans, iter, BTREE_ID_snapshots,
1041                         POS_MIN, 0, k,
1042                         NULL, NULL, 0,
1043                 bch2_delete_redundant_snapshot(&trans, &iter, k));
1044         if (ret) {
1045                 bch_err(c, "error deleting redundant snapshots: %s", bch2_err_str(ret));
1046                 goto err;
1047         }
1048
1049         for_each_btree_key2(&trans, iter, BTREE_ID_snapshots,
1050                            POS_MIN, 0, k,
1051                 bch2_snapshot_set_equiv(&trans, k));
1052         if (ret) {
1053                 bch_err(c, "error in bch2_snapshots_set_equiv: %s", bch2_err_str(ret));
1054                 goto err;
1055         }
1056
1057         for_each_btree_key(&trans, iter, BTREE_ID_snapshots,
1058                            POS_MIN, 0, k, ret) {
1059                 if (k.k->type != KEY_TYPE_snapshot)
1060                         continue;
1061
1062                 snap = bkey_s_c_to_snapshot(k);
1063                 if (BCH_SNAPSHOT_DELETED(snap.v)) {
1064                         ret = snapshot_list_add(c, &deleted, k.k->p.offset);
1065                         if (ret)
1066                                 break;
1067                 }
1068         }
1069         bch2_trans_iter_exit(&trans, &iter);
1070
1071         if (ret) {
1072                 bch_err(c, "error walking snapshots: %s", bch2_err_str(ret));
1073                 goto err;
1074         }
1075
1076         for (id = 0; id < BTREE_ID_NR; id++) {
1077                 struct bpos last_pos = POS_MIN;
1078                 snapshot_id_list equiv_seen = { 0 };
1079
1080                 if (!btree_type_has_snapshots(id))
1081                         continue;
1082
1083                 ret = for_each_btree_key_commit(&trans, iter,
1084                                 id, POS_MIN,
1085                                 BTREE_ITER_PREFETCH|BTREE_ITER_ALL_SNAPSHOTS, k,
1086                                 NULL, NULL, BTREE_INSERT_NOFAIL,
1087                         snapshot_delete_key(&trans, &iter, k, &deleted, &equiv_seen, &last_pos));
1088
1089                 darray_exit(&equiv_seen);
1090
1091                 if (ret) {
1092                         bch_err(c, "error deleting snapshot keys: %s", bch2_err_str(ret));
1093                         goto err;
1094                 }
1095         }
1096
1097         for (i = 0; i < deleted.nr; i++) {
1098                 ret = commit_do(&trans, NULL, NULL, 0,
1099                         bch2_snapshot_node_delete(&trans, deleted.data[i]));
1100                 if (ret) {
1101                         bch_err(c, "error deleting snapshot %u: %s",
1102                                 deleted.data[i], bch2_err_str(ret));
1103                         goto err;
1104                 }
1105         }
1106
1107         clear_bit(BCH_FS_HAVE_DELETED_SNAPSHOTS, &c->flags);
1108 err:
1109         darray_exit(&deleted);
1110         bch2_trans_exit(&trans);
1111         return ret;
1112 }
1113
1114 static void bch2_delete_dead_snapshots_work(struct work_struct *work)
1115 {
1116         struct bch_fs *c = container_of(work, struct bch_fs, snapshot_delete_work);
1117
1118         bch2_delete_dead_snapshots(c);
1119         bch2_write_ref_put(c, BCH_WRITE_REF_delete_dead_snapshots);
1120 }
1121
1122 void bch2_delete_dead_snapshots_async(struct bch_fs *c)
1123 {
1124         if (bch2_write_ref_tryget(c, BCH_WRITE_REF_delete_dead_snapshots) &&
1125             !queue_work(c->write_ref_wq, &c->snapshot_delete_work))
1126                 bch2_write_ref_put(c, BCH_WRITE_REF_delete_dead_snapshots);
1127 }
1128
1129 static int bch2_delete_dead_snapshots_hook(struct btree_trans *trans,
1130                                            struct btree_trans_commit_hook *h)
1131 {
1132         struct bch_fs *c = trans->c;
1133
1134         set_bit(BCH_FS_HAVE_DELETED_SNAPSHOTS, &c->flags);
1135
1136         if (!test_bit(BCH_FS_FSCK_DONE, &c->flags))
1137                 return 0;
1138
1139         bch2_delete_dead_snapshots_async(c);
1140         return 0;
1141 }
1142
1143 /* Subvolumes: */
1144
1145 int bch2_subvolume_invalid(const struct bch_fs *c, struct bkey_s_c k,
1146                            unsigned flags, struct printbuf *err)
1147 {
1148         if (bkey_lt(k.k->p, SUBVOL_POS_MIN) ||
1149             bkey_gt(k.k->p, SUBVOL_POS_MAX)) {
1150                 prt_printf(err, "invalid pos");
1151                 return -BCH_ERR_invalid_bkey;
1152         }
1153
1154         return 0;
1155 }
1156
1157 void bch2_subvolume_to_text(struct printbuf *out, struct bch_fs *c,
1158                             struct bkey_s_c k)
1159 {
1160         struct bkey_s_c_subvolume s = bkey_s_c_to_subvolume(k);
1161
1162         prt_printf(out, "root %llu snapshot id %u",
1163                    le64_to_cpu(s.v->inode),
1164                    le32_to_cpu(s.v->snapshot));
1165
1166         if (bkey_val_bytes(s.k) > offsetof(struct bch_subvolume, parent))
1167                 prt_printf(out, " parent %u", le32_to_cpu(s.v->parent));
1168 }
1169
1170 static __always_inline int
1171 bch2_subvolume_get_inlined(struct btree_trans *trans, unsigned subvol,
1172                            bool inconsistent_if_not_found,
1173                            int iter_flags,
1174                            struct bch_subvolume *s)
1175 {
1176         int ret = bch2_bkey_get_val_typed(trans, BTREE_ID_subvolumes, POS(0, subvol),
1177                                           iter_flags, subvolume, s);
1178         bch2_fs_inconsistent_on(ret == -ENOENT && inconsistent_if_not_found,
1179                                 trans->c, "missing subvolume %u", subvol);
1180         return ret;
1181 }
1182
1183 int bch2_subvolume_get(struct btree_trans *trans, unsigned subvol,
1184                        bool inconsistent_if_not_found,
1185                        int iter_flags,
1186                        struct bch_subvolume *s)
1187 {
1188         return bch2_subvolume_get_inlined(trans, subvol, inconsistent_if_not_found, iter_flags, s);
1189 }
1190
1191 int bch2_snapshot_get_subvol(struct btree_trans *trans, u32 snapshot,
1192                              struct bch_subvolume *subvol)
1193 {
1194         struct bch_snapshot snap;
1195
1196         return  snapshot_lookup(trans, snapshot, &snap) ?:
1197                 bch2_subvolume_get(trans, le32_to_cpu(snap.subvol), true, 0, subvol);
1198 }
1199
1200 int bch2_subvolume_get_snapshot(struct btree_trans *trans, u32 subvol,
1201                                 u32 *snapid)
1202 {
1203         struct btree_iter iter;
1204         struct bkey_s_c k;
1205         int ret;
1206
1207         k = bch2_bkey_get_iter(trans, &iter, BTREE_ID_subvolumes, POS(0, subvol),
1208                                BTREE_ITER_CACHED|
1209                                BTREE_ITER_WITH_UPDATES);
1210         ret = bkey_err(k) ?: k.k->type == KEY_TYPE_subvolume ? 0 : -ENOENT;
1211
1212         if (likely(!ret))
1213                 *snapid = le32_to_cpu(bkey_s_c_to_subvolume(k).v->snapshot);
1214         else if (ret == -ENOENT)
1215                 bch2_fs_inconsistent(trans->c, "missing subvolume %u", subvol);
1216         bch2_trans_iter_exit(trans, &iter);
1217         return ret;
1218 }
1219
1220 static int bch2_subvolume_reparent(struct btree_trans *trans,
1221                                    struct btree_iter *iter,
1222                                    struct bkey_s_c k,
1223                                    u32 old_parent, u32 new_parent)
1224 {
1225         struct bkey_i_subvolume *s;
1226         int ret;
1227
1228         if (k.k->type != KEY_TYPE_subvolume)
1229                 return 0;
1230
1231         if (bkey_val_bytes(k.k) > offsetof(struct bch_subvolume, parent) &&
1232             le32_to_cpu(bkey_s_c_to_subvolume(k).v->parent) != old_parent)
1233                 return 0;
1234
1235         s = bch2_bkey_make_mut_typed(trans, iter, k, 0, subvolume);
1236         ret = PTR_ERR_OR_ZERO(s);
1237         if (ret)
1238                 return ret;
1239
1240         s->v.parent = cpu_to_le32(new_parent);
1241         return 0;
1242 }
1243
1244 /*
1245  * Scan for subvolumes with parent @subvolid_to_delete, reparent:
1246  */
1247 static int bch2_subvolumes_reparent(struct btree_trans *trans, u32 subvolid_to_delete)
1248 {
1249         struct btree_iter iter;
1250         struct bkey_s_c k;
1251         struct bch_subvolume s;
1252
1253         return lockrestart_do(trans,
1254                         bch2_subvolume_get(trans, subvolid_to_delete, true,
1255                                    BTREE_ITER_CACHED, &s)) ?:
1256                 for_each_btree_key_commit(trans, iter,
1257                                 BTREE_ID_subvolumes, POS_MIN, BTREE_ITER_PREFETCH, k,
1258                                 NULL, NULL, BTREE_INSERT_NOFAIL,
1259                         bch2_subvolume_reparent(trans, &iter, k,
1260                                         subvolid_to_delete, le32_to_cpu(s.parent)));
1261 }
1262
1263 /*
1264  * Delete subvolume, mark snapshot ID as deleted, queue up snapshot
1265  * deletion/cleanup:
1266  */
1267 static int __bch2_subvolume_delete(struct btree_trans *trans, u32 subvolid)
1268 {
1269         struct btree_iter iter;
1270         struct bkey_s_c_subvolume subvol;
1271         struct btree_trans_commit_hook *h;
1272         u32 snapid;
1273         int ret = 0;
1274
1275         subvol = bch2_bkey_get_iter_typed(trans, &iter,
1276                                 BTREE_ID_subvolumes, POS(0, subvolid),
1277                                 BTREE_ITER_CACHED|BTREE_ITER_INTENT,
1278                                 subvolume);
1279         ret = bkey_err(subvol);
1280         bch2_fs_inconsistent_on(ret == -ENOENT, trans->c, "missing subvolume %u", subvolid);
1281         if (ret)
1282                 return ret;
1283
1284         snapid = le32_to_cpu(subvol.v->snapshot);
1285
1286         ret = bch2_btree_delete_at(trans, &iter, 0);
1287         if (ret)
1288                 goto err;
1289
1290         ret = bch2_snapshot_node_set_deleted(trans, snapid);
1291         if (ret)
1292                 goto err;
1293
1294         h = bch2_trans_kmalloc(trans, sizeof(*h));
1295         ret = PTR_ERR_OR_ZERO(h);
1296         if (ret)
1297                 goto err;
1298
1299         h->fn = bch2_delete_dead_snapshots_hook;
1300         bch2_trans_commit_hook(trans, h);
1301 err:
1302         bch2_trans_iter_exit(trans, &iter);
1303         return ret;
1304 }
1305
1306 static int bch2_subvolume_delete(struct btree_trans *trans, u32 subvolid)
1307 {
1308         return bch2_subvolumes_reparent(trans, subvolid) ?:
1309                 commit_do(trans, NULL, NULL, BTREE_INSERT_NOFAIL,
1310                           __bch2_subvolume_delete(trans, subvolid));
1311 }
1312
1313 void bch2_subvolume_wait_for_pagecache_and_delete(struct work_struct *work)
1314 {
1315         struct bch_fs *c = container_of(work, struct bch_fs,
1316                                 snapshot_wait_for_pagecache_and_delete_work);
1317         snapshot_id_list s;
1318         u32 *id;
1319         int ret = 0;
1320
1321         while (!ret) {
1322                 mutex_lock(&c->snapshots_unlinked_lock);
1323                 s = c->snapshots_unlinked;
1324                 darray_init(&c->snapshots_unlinked);
1325                 mutex_unlock(&c->snapshots_unlinked_lock);
1326
1327                 if (!s.nr)
1328                         break;
1329
1330                 bch2_evict_subvolume_inodes(c, &s);
1331
1332                 for (id = s.data; id < s.data + s.nr; id++) {
1333                         ret = bch2_trans_run(c, bch2_subvolume_delete(&trans, *id));
1334                         if (ret) {
1335                                 bch_err(c, "error deleting subvolume %u: %s", *id, bch2_err_str(ret));
1336                                 break;
1337                         }
1338                 }
1339
1340                 darray_exit(&s);
1341         }
1342
1343         bch2_write_ref_put(c, BCH_WRITE_REF_snapshot_delete_pagecache);
1344 }
1345
1346 struct subvolume_unlink_hook {
1347         struct btree_trans_commit_hook  h;
1348         u32                             subvol;
1349 };
1350
1351 int bch2_subvolume_wait_for_pagecache_and_delete_hook(struct btree_trans *trans,
1352                                                       struct btree_trans_commit_hook *_h)
1353 {
1354         struct subvolume_unlink_hook *h = container_of(_h, struct subvolume_unlink_hook, h);
1355         struct bch_fs *c = trans->c;
1356         int ret = 0;
1357
1358         mutex_lock(&c->snapshots_unlinked_lock);
1359         if (!snapshot_list_has_id(&c->snapshots_unlinked, h->subvol))
1360                 ret = snapshot_list_add(c, &c->snapshots_unlinked, h->subvol);
1361         mutex_unlock(&c->snapshots_unlinked_lock);
1362
1363         if (ret)
1364                 return ret;
1365
1366         if (!bch2_write_ref_tryget(c, BCH_WRITE_REF_snapshot_delete_pagecache))
1367                 return -EROFS;
1368
1369         if (!queue_work(c->write_ref_wq, &c->snapshot_wait_for_pagecache_and_delete_work))
1370                 bch2_write_ref_put(c, BCH_WRITE_REF_snapshot_delete_pagecache);
1371         return 0;
1372 }
1373
1374 int bch2_subvolume_unlink(struct btree_trans *trans, u32 subvolid)
1375 {
1376         struct btree_iter iter;
1377         struct bkey_i_subvolume *n;
1378         struct subvolume_unlink_hook *h;
1379         int ret = 0;
1380
1381         h = bch2_trans_kmalloc(trans, sizeof(*h));
1382         ret = PTR_ERR_OR_ZERO(h);
1383         if (ret)
1384                 return ret;
1385
1386         h->h.fn         = bch2_subvolume_wait_for_pagecache_and_delete_hook;
1387         h->subvol       = subvolid;
1388         bch2_trans_commit_hook(trans, &h->h);
1389
1390         n = bch2_bkey_get_mut_typed(trans, &iter,
1391                         BTREE_ID_subvolumes, POS(0, subvolid),
1392                         BTREE_ITER_CACHED, subvolume);
1393         ret = PTR_ERR_OR_ZERO(n);
1394         if (unlikely(ret)) {
1395                 bch2_fs_inconsistent_on(ret == -ENOENT, trans->c, "missing subvolume %u", subvolid);
1396                 return ret;
1397         }
1398
1399         SET_BCH_SUBVOLUME_UNLINKED(&n->v, true);
1400         bch2_trans_iter_exit(trans, &iter);
1401         return ret;
1402 }
1403
1404 int bch2_subvolume_create(struct btree_trans *trans, u64 inode,
1405                           u32 src_subvolid,
1406                           u32 *new_subvolid,
1407                           u32 *new_snapshotid,
1408                           bool ro)
1409 {
1410         struct bch_fs *c = trans->c;
1411         struct btree_iter dst_iter, src_iter = (struct btree_iter) { NULL };
1412         struct bkey_i_subvolume *new_subvol = NULL;
1413         struct bkey_i_subvolume *src_subvol = NULL;
1414         u32 parent = 0, new_nodes[2], snapshot_subvols[2];
1415         int ret = 0;
1416
1417         ret = bch2_bkey_get_empty_slot(trans, &dst_iter,
1418                                 BTREE_ID_subvolumes, POS(0, U32_MAX));
1419         if (ret == -BCH_ERR_ENOSPC_btree_slot)
1420                 ret = -BCH_ERR_ENOSPC_subvolume_create;
1421         if (ret)
1422                 return ret;
1423
1424         snapshot_subvols[0] = dst_iter.pos.offset;
1425         snapshot_subvols[1] = src_subvolid;
1426
1427         if (src_subvolid) {
1428                 /* Creating a snapshot: */
1429
1430                 src_subvol = bch2_bkey_get_mut_typed(trans, &src_iter,
1431                                 BTREE_ID_subvolumes, POS(0, src_subvolid),
1432                                 BTREE_ITER_CACHED, subvolume);
1433                 ret = PTR_ERR_OR_ZERO(src_subvol);
1434                 if (unlikely(ret)) {
1435                         bch2_fs_inconsistent_on(ret == -ENOENT, c,
1436                                                 "subvolume %u not found", src_subvolid);
1437                         goto err;
1438                 }
1439
1440                 parent = le32_to_cpu(src_subvol->v.snapshot);
1441         }
1442
1443         ret = bch2_snapshot_node_create(trans, parent, new_nodes,
1444                                         snapshot_subvols,
1445                                         src_subvolid ? 2 : 1);
1446         if (ret)
1447                 goto err;
1448
1449         if (src_subvolid) {
1450                 src_subvol->v.snapshot = cpu_to_le32(new_nodes[1]);
1451                 ret = bch2_trans_update(trans, &src_iter, &src_subvol->k_i, 0);
1452                 if (ret)
1453                         goto err;
1454         }
1455
1456         new_subvol = bch2_bkey_alloc(trans, &dst_iter, 0, subvolume);
1457         ret = PTR_ERR_OR_ZERO(new_subvol);
1458         if (ret)
1459                 goto err;
1460
1461         new_subvol->v.flags     = 0;
1462         new_subvol->v.snapshot  = cpu_to_le32(new_nodes[0]);
1463         new_subvol->v.inode     = cpu_to_le64(inode);
1464         new_subvol->v.parent    = cpu_to_le32(src_subvolid);
1465         new_subvol->v.otime.lo  = cpu_to_le64(bch2_current_time(c));
1466         new_subvol->v.otime.hi  = 0;
1467
1468         SET_BCH_SUBVOLUME_RO(&new_subvol->v, ro);
1469         SET_BCH_SUBVOLUME_SNAP(&new_subvol->v, src_subvolid != 0);
1470
1471         *new_subvolid   = new_subvol->k.p.offset;
1472         *new_snapshotid = new_nodes[0];
1473 err:
1474         bch2_trans_iter_exit(trans, &src_iter);
1475         bch2_trans_iter_exit(trans, &dst_iter);
1476         return ret;
1477 }
1478
1479 int bch2_fs_subvolumes_init(struct bch_fs *c)
1480 {
1481         INIT_WORK(&c->snapshot_delete_work, bch2_delete_dead_snapshots_work);
1482         INIT_WORK(&c->snapshot_wait_for_pagecache_and_delete_work,
1483                   bch2_subvolume_wait_for_pagecache_and_delete);
1484         mutex_init(&c->snapshots_unlinked_lock);
1485         return 0;
1486 }