1 // SPDX-License-Identifier: GPL-2.0
4 #include "btree_key_cache.h"
5 #include "btree_update.h"
11 static int bch2_subvolume_delete(struct btree_trans *, u32);
15 void bch2_snapshot_tree_to_text(struct printbuf *out, struct bch_fs *c,
18 struct bkey_s_c_snapshot_tree t = bkey_s_c_to_snapshot_tree(k);
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));
25 int bch2_snapshot_tree_invalid(const struct bch_fs *c, struct bkey_s_c k,
26 enum bkey_invalid_flags flags,
29 if (bkey_gt(k.k->p, POS(0, U32_MAX)) ||
30 bkey_lt(k.k->p, POS(0, 1))) {
31 prt_printf(err, "bad pos");
32 return -BCH_ERR_invalid_bkey;
38 int bch2_snapshot_tree_lookup(struct btree_trans *trans, u32 id,
39 struct bch_snapshot_tree *s)
41 int ret = bch2_bkey_get_val_typed(trans, BTREE_ID_snapshot_trees, POS(0, id),
42 BTREE_ITER_WITH_UPDATES, snapshot_tree, s);
44 if (bch2_err_matches(ret, ENOENT))
45 ret = -BCH_ERR_ENOENT_snapshot_tree;
49 static struct bkey_i_snapshot_tree *
50 __snapshot_tree_create(struct btree_trans *trans)
52 struct btree_iter iter;
53 int ret = bch2_bkey_get_empty_slot(trans, &iter,
54 BTREE_ID_snapshot_trees, POS(0, U32_MAX));
55 struct bkey_i_snapshot_tree *s_t;
57 if (ret == -BCH_ERR_ENOSPC_btree_slot)
58 ret = -BCH_ERR_ENOSPC_snapshot_tree;
62 s_t = bch2_bkey_alloc(trans, &iter, 0, snapshot_tree);
63 ret = PTR_ERR_OR_ZERO(s_t);
64 bch2_trans_iter_exit(trans, &iter);
65 return ret ? ERR_PTR(ret) : s_t;
68 static int snapshot_tree_create(struct btree_trans *trans,
69 u32 root_id, u32 subvol_id, u32 *tree_id)
71 struct bkey_i_snapshot_tree *n_tree =
72 __snapshot_tree_create(trans);
75 return PTR_ERR(n_tree);
77 n_tree->v.master_subvol = cpu_to_le32(subvol_id);
78 n_tree->v.root_snapshot = cpu_to_le32(root_id);
79 *tree_id = n_tree->k.p.offset;
85 void bch2_snapshot_to_text(struct printbuf *out, struct bch_fs *c,
88 struct bkey_s_c_snapshot s = bkey_s_c_to_snapshot(k);
90 prt_printf(out, "is_subvol %llu deleted %llu parent %10u children %10u %10u subvol %u tree %u",
91 BCH_SNAPSHOT_SUBVOL(s.v),
92 BCH_SNAPSHOT_DELETED(s.v),
93 le32_to_cpu(s.v->parent),
94 le32_to_cpu(s.v->children[0]),
95 le32_to_cpu(s.v->children[1]),
96 le32_to_cpu(s.v->subvol),
97 le32_to_cpu(s.v->tree));
100 int bch2_snapshot_invalid(const struct bch_fs *c, struct bkey_s_c k,
101 enum bkey_invalid_flags flags,
102 struct printbuf *err)
104 struct bkey_s_c_snapshot s;
107 if (bkey_gt(k.k->p, POS(0, U32_MAX)) ||
108 bkey_lt(k.k->p, POS(0, 1))) {
109 prt_printf(err, "bad pos");
110 return -BCH_ERR_invalid_bkey;
113 s = bkey_s_c_to_snapshot(k);
115 id = le32_to_cpu(s.v->parent);
116 if (id && id <= k.k->p.offset) {
117 prt_printf(err, "bad parent node (%u <= %llu)",
119 return -BCH_ERR_invalid_bkey;
122 if (le32_to_cpu(s.v->children[0]) < le32_to_cpu(s.v->children[1])) {
123 prt_printf(err, "children not normalized");
124 return -BCH_ERR_invalid_bkey;
127 if (s.v->children[0] &&
128 s.v->children[0] == s.v->children[1]) {
129 prt_printf(err, "duplicate child nodes");
130 return -BCH_ERR_invalid_bkey;
133 for (i = 0; i < 2; i++) {
134 id = le32_to_cpu(s.v->children[i]);
136 if (id >= k.k->p.offset) {
137 prt_printf(err, "bad child node (%u >= %llu)",
139 return -BCH_ERR_invalid_bkey;
146 int bch2_mark_snapshot(struct btree_trans *trans,
147 enum btree_id btree, unsigned level,
148 struct bkey_s_c old, struct bkey_s_c new,
151 struct bch_fs *c = trans->c;
152 struct snapshot_t *t;
154 t = genradix_ptr_alloc(&c->snapshots,
155 U32_MAX - new.k->p.offset,
158 return -BCH_ERR_ENOMEM_mark_snapshot;
160 if (new.k->type == KEY_TYPE_snapshot) {
161 struct bkey_s_c_snapshot s = bkey_s_c_to_snapshot(new);
163 t->parent = le32_to_cpu(s.v->parent);
164 t->children[0] = le32_to_cpu(s.v->children[0]);
165 t->children[1] = le32_to_cpu(s.v->children[1]);
166 t->subvol = BCH_SNAPSHOT_SUBVOL(s.v) ? le32_to_cpu(s.v->subvol) : 0;
167 t->tree = le32_to_cpu(s.v->tree);
179 static int snapshot_lookup(struct btree_trans *trans, u32 id,
180 struct bch_snapshot *s)
182 return bch2_bkey_get_val_typed(trans, BTREE_ID_snapshots, POS(0, id),
183 BTREE_ITER_WITH_UPDATES, snapshot, s);
186 static int snapshot_live(struct btree_trans *trans, u32 id)
188 struct bch_snapshot v;
194 ret = snapshot_lookup(trans, id, &v);
195 if (bch2_err_matches(ret, ENOENT))
196 bch_err(trans->c, "snapshot node %u not found", id);
200 return !BCH_SNAPSHOT_DELETED(&v);
203 static int bch2_snapshot_set_equiv(struct btree_trans *trans, struct bkey_s_c k)
205 struct bch_fs *c = trans->c;
206 unsigned i, nr_live = 0, live_idx = 0;
207 struct bkey_s_c_snapshot snap;
208 u32 id = k.k->p.offset, child[2];
210 if (k.k->type != KEY_TYPE_snapshot)
213 snap = bkey_s_c_to_snapshot(k);
215 child[0] = le32_to_cpu(snap.v->children[0]);
216 child[1] = le32_to_cpu(snap.v->children[1]);
218 for (i = 0; i < 2; i++) {
219 int ret = snapshot_live(trans, child[i]);
229 snapshot_t(c, id)->equiv = nr_live == 1
230 ? snapshot_t(c, child[live_idx])->equiv
237 static u32 bch2_snapshot_child(struct bch_fs *c, u32 id, unsigned child)
239 return snapshot_t(c, id)->children[child];
242 static u32 bch2_snapshot_left_child(struct bch_fs *c, u32 id)
244 return bch2_snapshot_child(c, id, 0);
247 static u32 bch2_snapshot_right_child(struct bch_fs *c, u32 id)
249 return bch2_snapshot_child(c, id, 1);
252 static u32 bch2_snapshot_tree_next(struct bch_fs *c, u32 id)
256 n = bch2_snapshot_left_child(c, id);
260 while ((parent = bch2_snapshot_parent(c, id))) {
261 n = bch2_snapshot_right_child(c, parent);
270 static u32 bch2_snapshot_tree_oldest_subvol(struct bch_fs *c, u32 snapshot_root)
272 u32 id = snapshot_root;
276 s = snapshot_t(c, id)->subvol;
278 if (s && (!subvol || s < subvol))
281 id = bch2_snapshot_tree_next(c, id);
287 static int bch2_snapshot_tree_master_subvol(struct btree_trans *trans,
288 u32 snapshot_root, u32 *subvol_id)
290 struct bch_fs *c = trans->c;
291 struct btree_iter iter;
293 struct bkey_s_c_subvolume s;
297 for_each_btree_key_norestart(trans, iter, BTREE_ID_subvolumes, POS_MIN,
299 if (k.k->type != KEY_TYPE_subvolume)
302 s = bkey_s_c_to_subvolume(k);
303 if (!bch2_snapshot_is_ancestor(c, le32_to_cpu(s.v->snapshot), snapshot_root))
305 if (!BCH_SUBVOLUME_SNAP(s.v)) {
306 *subvol_id = s.k->p.offset;
312 bch2_trans_iter_exit(trans, &iter);
314 if (!ret && !found) {
315 struct bkey_i_subvolume *s;
317 *subvol_id = bch2_snapshot_tree_oldest_subvol(c, snapshot_root);
319 s = bch2_bkey_get_mut_typed(trans, &iter,
320 BTREE_ID_subvolumes, POS(0, *subvol_id),
322 ret = PTR_ERR_OR_ZERO(s);
326 SET_BCH_SUBVOLUME_SNAP(&s->v, false);
332 static int check_snapshot_tree(struct btree_trans *trans,
333 struct btree_iter *iter,
336 struct bch_fs *c = trans->c;
337 struct bkey_s_c_snapshot_tree st;
338 struct bch_snapshot s;
339 struct bch_subvolume subvol;
340 struct printbuf buf = PRINTBUF;
344 if (k.k->type != KEY_TYPE_snapshot_tree)
347 st = bkey_s_c_to_snapshot_tree(k);
348 root_id = le32_to_cpu(st.v->root_snapshot);
350 ret = snapshot_lookup(trans, root_id, &s);
351 if (ret && !bch2_err_matches(ret, ENOENT))
354 if (fsck_err_on(ret ||
355 root_id != bch2_snapshot_root(c, root_id) ||
356 st.k->p.offset != le32_to_cpu(s.tree),
358 "snapshot tree points to missing/incorrect snapshot:\n %s",
359 (bch2_bkey_val_to_text(&buf, c, st.s_c), buf.buf))) {
360 ret = bch2_btree_delete_at(trans, iter, 0);
364 ret = bch2_subvolume_get(trans, le32_to_cpu(st.v->master_subvol),
366 if (ret && !bch2_err_matches(ret, ENOENT))
369 if (fsck_err_on(ret, c,
370 "snapshot tree points to missing subvolume:\n %s",
371 (printbuf_reset(&buf),
372 bch2_bkey_val_to_text(&buf, c, st.s_c), buf.buf)) ||
373 fsck_err_on(!bch2_snapshot_is_ancestor(c,
374 le32_to_cpu(subvol.snapshot),
376 "snapshot tree points to subvolume that does not point to snapshot in this tree:\n %s",
377 (printbuf_reset(&buf),
378 bch2_bkey_val_to_text(&buf, c, st.s_c), buf.buf)) ||
379 fsck_err_on(BCH_SUBVOLUME_SNAP(&subvol), c,
380 "snapshot tree points to snapshot subvolume:\n %s",
381 (printbuf_reset(&buf),
382 bch2_bkey_val_to_text(&buf, c, st.s_c), buf.buf))) {
383 struct bkey_i_snapshot_tree *u;
386 ret = bch2_snapshot_tree_master_subvol(trans, root_id, &subvol_id);
390 u = bch2_bkey_make_mut_typed(trans, iter, &k, 0, snapshot_tree);
391 ret = PTR_ERR_OR_ZERO(u);
395 u->v.master_subvol = cpu_to_le32(subvol_id);
396 st = snapshot_tree_i_to_s_c(u);
405 * For each snapshot_tree, make sure it points to the root of a snapshot tree
406 * and that snapshot entry points back to it, or delete it.
408 * And, make sure it points to a subvolume within that snapshot tree, or correct
409 * it to point to the oldest subvolume within that snapshot tree.
411 int bch2_check_snapshot_trees(struct bch_fs *c)
413 struct btree_iter iter;
417 ret = bch2_trans_run(c,
418 for_each_btree_key_commit(&trans, iter,
419 BTREE_ID_snapshot_trees, POS_MIN,
420 BTREE_ITER_PREFETCH, k,
421 NULL, NULL, BTREE_INSERT_LAZY_RW|BTREE_INSERT_NOFAIL,
422 check_snapshot_tree(&trans, &iter, k)));
425 bch_err(c, "error %i checking snapshot trees", ret);
430 * Look up snapshot tree for @tree_id and find root,
431 * make sure @snap_id is a descendent:
433 static int snapshot_tree_ptr_good(struct btree_trans *trans,
434 u32 snap_id, u32 tree_id)
436 struct bch_snapshot_tree s_t;
437 int ret = bch2_snapshot_tree_lookup(trans, tree_id, &s_t);
439 if (bch2_err_matches(ret, ENOENT))
444 return bch2_snapshot_is_ancestor(trans->c, snap_id, le32_to_cpu(s_t.root_snapshot));
448 * snapshot_tree pointer was incorrect: look up root snapshot node, make sure
449 * its snapshot_tree pointer is correct (allocate new one if necessary), then
450 * update this node's pointer to root node's pointer:
452 static int snapshot_tree_ptr_repair(struct btree_trans *trans,
453 struct btree_iter *iter,
454 struct bkey_s_c_snapshot *s)
456 struct bch_fs *c = trans->c;
457 struct btree_iter root_iter;
458 struct bch_snapshot_tree s_t;
459 struct bkey_s_c_snapshot root;
460 struct bkey_i_snapshot *u;
461 u32 root_id = bch2_snapshot_root(c, s->k->p.offset), tree_id;
464 root = bch2_bkey_get_iter_typed(trans, &root_iter,
465 BTREE_ID_snapshots, POS(0, root_id),
466 BTREE_ITER_WITH_UPDATES, snapshot);
467 ret = bkey_err(root);
471 tree_id = le32_to_cpu(root.v->tree);
473 ret = bch2_snapshot_tree_lookup(trans, tree_id, &s_t);
474 if (ret && !bch2_err_matches(ret, ENOENT))
477 if (ret || le32_to_cpu(s_t.root_snapshot) != root_id) {
478 u = bch2_bkey_make_mut_typed(trans, &root_iter, &root.s_c, 0, snapshot);
479 ret = PTR_ERR_OR_ZERO(u) ?:
480 snapshot_tree_create(trans, root_id,
481 bch2_snapshot_tree_oldest_subvol(c, root_id),
486 u->v.tree = cpu_to_le32(tree_id);
487 if (s->k->p.snapshot == root_id)
488 *s = snapshot_i_to_s_c(u);
491 if (s->k->p.snapshot != root_id) {
492 u = bch2_bkey_make_mut_typed(trans, iter, &s->s_c, 0, snapshot);
493 ret = PTR_ERR_OR_ZERO(u);
497 u->v.tree = cpu_to_le32(tree_id);
498 *s = snapshot_i_to_s_c(u);
501 bch2_trans_iter_exit(trans, &root_iter);
505 static int check_snapshot(struct btree_trans *trans,
506 struct btree_iter *iter,
509 struct bch_fs *c = trans->c;
510 struct bkey_s_c_snapshot s;
511 struct bch_subvolume subvol;
512 struct bch_snapshot v;
513 struct printbuf buf = PRINTBUF;
514 bool should_have_subvol;
518 if (k.k->type != KEY_TYPE_snapshot)
521 s = bkey_s_c_to_snapshot(k);
522 id = le32_to_cpu(s.v->parent);
524 ret = snapshot_lookup(trans, id, &v);
525 if (bch2_err_matches(ret, ENOENT))
526 bch_err(c, "snapshot with nonexistent parent:\n %s",
527 (bch2_bkey_val_to_text(&buf, c, s.s_c), buf.buf));
531 if (le32_to_cpu(v.children[0]) != s.k->p.offset &&
532 le32_to_cpu(v.children[1]) != s.k->p.offset) {
533 bch_err(c, "snapshot parent %u missing pointer to child %llu",
540 for (i = 0; i < 2 && s.v->children[i]; i++) {
541 id = le32_to_cpu(s.v->children[i]);
543 ret = snapshot_lookup(trans, id, &v);
544 if (bch2_err_matches(ret, ENOENT))
545 bch_err(c, "snapshot node %llu has nonexistent child %u",
550 if (le32_to_cpu(v.parent) != s.k->p.offset) {
551 bch_err(c, "snapshot child %u has wrong parent (got %u should be %llu)",
552 id, le32_to_cpu(v.parent), s.k->p.offset);
558 should_have_subvol = BCH_SNAPSHOT_SUBVOL(s.v) &&
559 !BCH_SNAPSHOT_DELETED(s.v);
561 if (should_have_subvol) {
562 id = le32_to_cpu(s.v->subvol);
563 ret = bch2_subvolume_get(trans, id, 0, false, &subvol);
564 if (bch2_err_matches(ret, ENOENT))
565 bch_err(c, "snapshot points to nonexistent subvolume:\n %s",
566 (bch2_bkey_val_to_text(&buf, c, s.s_c), buf.buf));
570 if (BCH_SNAPSHOT_SUBVOL(s.v) != (le32_to_cpu(subvol.snapshot) == s.k->p.offset)) {
571 bch_err(c, "snapshot node %llu has wrong BCH_SNAPSHOT_SUBVOL",
577 if (fsck_err_on(s.v->subvol, c, "snapshot should not point to subvol:\n %s",
578 (bch2_bkey_val_to_text(&buf, c, s.s_c), buf.buf))) {
579 struct bkey_i_snapshot *u = bch2_trans_kmalloc(trans, sizeof(*u));
581 ret = PTR_ERR_OR_ZERO(u);
585 bkey_reassemble(&u->k_i, s.s_c);
587 ret = bch2_trans_update(trans, iter, &u->k_i, 0);
591 s = snapshot_i_to_s_c(u);
595 ret = snapshot_tree_ptr_good(trans, s.k->p.offset, le32_to_cpu(s.v->tree));
599 if (fsck_err_on(!ret, c, "snapshot points to missing/incorrect tree:\n %s",
600 (bch2_bkey_val_to_text(&buf, c, s.s_c), buf.buf))) {
601 ret = snapshot_tree_ptr_repair(trans, iter, &s);
607 if (BCH_SNAPSHOT_DELETED(s.v))
608 set_bit(BCH_FS_HAVE_DELETED_SNAPSHOTS, &c->flags);
615 int bch2_check_snapshots(struct bch_fs *c)
617 struct btree_iter iter;
621 ret = bch2_trans_run(c,
622 for_each_btree_key_commit(&trans, iter,
623 BTREE_ID_snapshots, POS_MIN,
624 BTREE_ITER_PREFETCH, k,
625 NULL, NULL, BTREE_INSERT_LAZY_RW|BTREE_INSERT_NOFAIL,
626 check_snapshot(&trans, &iter, k)));
632 static int check_subvol(struct btree_trans *trans,
633 struct btree_iter *iter,
636 struct bch_fs *c = trans->c;
637 struct bkey_s_c_subvolume subvol;
638 struct bch_snapshot snapshot;
642 if (k.k->type != KEY_TYPE_subvolume)
645 subvol = bkey_s_c_to_subvolume(k);
646 snapid = le32_to_cpu(subvol.v->snapshot);
647 ret = snapshot_lookup(trans, snapid, &snapshot);
649 if (bch2_err_matches(ret, ENOENT))
650 bch_err(c, "subvolume %llu points to nonexistent snapshot %u",
651 k.k->p.offset, snapid);
655 if (BCH_SUBVOLUME_UNLINKED(subvol.v)) {
658 ret = bch2_subvolume_delete(trans, iter->pos.offset);
660 bch_err(c, "error deleting subvolume %llu: %s",
661 iter->pos.offset, bch2_err_str(ret));
662 return ret ?: -BCH_ERR_transaction_restart_nested;
665 if (!BCH_SUBVOLUME_SNAP(subvol.v)) {
666 u32 snapshot_root = bch2_snapshot_root(c, le32_to_cpu(subvol.v->snapshot));
667 u32 snapshot_tree = snapshot_t(c, snapshot_root)->tree;
668 struct bch_snapshot_tree st;
670 ret = bch2_snapshot_tree_lookup(trans, snapshot_tree, &st);
672 bch2_fs_inconsistent_on(bch2_err_matches(ret, ENOENT), c,
673 "%s: snapshot tree %u not found", __func__, snapshot_tree);
678 if (fsck_err_on(le32_to_cpu(st.master_subvol) != subvol.k->p.offset, c,
679 "subvolume %llu is not set as snapshot but is not master subvolume",
681 struct bkey_i_subvolume *s =
682 bch2_bkey_make_mut_typed(trans, iter, &subvol.s_c, 0, subvolume);
683 ret = PTR_ERR_OR_ZERO(s);
687 SET_BCH_SUBVOLUME_SNAP(&s->v, true);
695 int bch2_check_subvols(struct bch_fs *c)
697 struct btree_iter iter;
701 ret = bch2_trans_run(c,
702 for_each_btree_key_commit(&trans, iter,
703 BTREE_ID_subvolumes, POS_MIN, BTREE_ITER_PREFETCH, k,
704 NULL, NULL, BTREE_INSERT_LAZY_RW|BTREE_INSERT_NOFAIL,
705 check_subvol(&trans, &iter, k)));
711 void bch2_fs_snapshots_exit(struct bch_fs *c)
713 genradix_free(&c->snapshots);
716 int bch2_snapshots_read(struct bch_fs *c)
718 struct btree_iter iter;
722 ret = bch2_trans_run(c,
723 for_each_btree_key2(&trans, iter, BTREE_ID_snapshots,
725 bch2_mark_snapshot(&trans, BTREE_ID_snapshots, 0, bkey_s_c_null, k, 0) ?:
726 bch2_snapshot_set_equiv(&trans, k)));
733 * Mark a snapshot as deleted, for future cleanup:
735 static int bch2_snapshot_node_set_deleted(struct btree_trans *trans, u32 id)
737 struct btree_iter iter;
738 struct bkey_i_snapshot *s;
741 s = bch2_bkey_get_mut_typed(trans, &iter,
742 BTREE_ID_snapshots, POS(0, id),
744 ret = PTR_ERR_OR_ZERO(s);
746 bch2_fs_inconsistent_on(bch2_err_matches(ret, ENOENT),
747 trans->c, "missing snapshot %u", id);
751 /* already deleted? */
752 if (BCH_SNAPSHOT_DELETED(&s->v))
755 SET_BCH_SNAPSHOT_DELETED(&s->v, true);
756 SET_BCH_SNAPSHOT_SUBVOL(&s->v, false);
759 bch2_trans_iter_exit(trans, &iter);
763 static int bch2_snapshot_node_delete(struct btree_trans *trans, u32 id)
765 struct bch_fs *c = trans->c;
766 struct btree_iter iter, p_iter = (struct btree_iter) { NULL };
767 struct btree_iter tree_iter = (struct btree_iter) { NULL };
768 struct bkey_s_c_snapshot s;
773 s = bch2_bkey_get_iter_typed(trans, &iter, BTREE_ID_snapshots, POS(0, id),
774 BTREE_ITER_INTENT, snapshot);
776 bch2_fs_inconsistent_on(bch2_err_matches(ret, ENOENT), c,
777 "missing snapshot %u", id);
782 BUG_ON(!BCH_SNAPSHOT_DELETED(s.v));
783 parent_id = le32_to_cpu(s.v->parent);
786 struct bkey_i_snapshot *parent;
788 parent = bch2_bkey_get_mut_typed(trans, &p_iter,
789 BTREE_ID_snapshots, POS(0, parent_id),
791 ret = PTR_ERR_OR_ZERO(parent);
793 bch2_fs_inconsistent_on(bch2_err_matches(ret, ENOENT), c,
794 "missing snapshot %u", parent_id);
798 for (i = 0; i < 2; i++)
799 if (le32_to_cpu(parent->v.children[i]) == id)
803 bch_err(c, "snapshot %u missing child pointer to %u",
806 parent->v.children[i] = 0;
808 if (le32_to_cpu(parent->v.children[0]) <
809 le32_to_cpu(parent->v.children[1]))
810 swap(parent->v.children[0],
811 parent->v.children[1]);
814 * We're deleting the root of a snapshot tree: update the
815 * snapshot_tree entry to point to the new root, or delete it if
816 * this is the last snapshot ID in this tree:
818 struct bkey_i_snapshot_tree *s_t;
820 BUG_ON(s.v->children[1]);
822 s_t = bch2_bkey_get_mut_typed(trans, &tree_iter,
823 BTREE_ID_snapshot_trees, POS(0, le32_to_cpu(s.v->tree)),
825 ret = PTR_ERR_OR_ZERO(s_t);
829 if (s.v->children[0]) {
830 s_t->v.root_snapshot = s.v->children[0];
832 s_t->k.type = KEY_TYPE_deleted;
833 set_bkey_val_u64s(&s_t->k, 0);
837 ret = bch2_btree_delete_at(trans, &iter, 0);
839 bch2_trans_iter_exit(trans, &tree_iter);
840 bch2_trans_iter_exit(trans, &p_iter);
841 bch2_trans_iter_exit(trans, &iter);
845 static int create_snapids(struct btree_trans *trans, u32 parent, u32 tree,
847 u32 *snapshot_subvols,
850 struct btree_iter iter;
851 struct bkey_i_snapshot *n;
856 bch2_trans_iter_init(trans, &iter, BTREE_ID_snapshots,
857 POS_MIN, BTREE_ITER_INTENT);
858 k = bch2_btree_iter_peek(&iter);
863 for (i = 0; i < nr_snapids; i++) {
864 k = bch2_btree_iter_prev_slot(&iter);
869 if (!k.k || !k.k->p.offset) {
870 ret = -BCH_ERR_ENOSPC_snapshot_create;
874 n = bch2_bkey_alloc(trans, &iter, 0, snapshot);
875 ret = PTR_ERR_OR_ZERO(n);
880 n->v.parent = cpu_to_le32(parent);
881 n->v.subvol = cpu_to_le32(snapshot_subvols[i]);
882 n->v.tree = cpu_to_le32(tree);
883 SET_BCH_SNAPSHOT_SUBVOL(&n->v, true);
885 ret = bch2_mark_snapshot(trans, BTREE_ID_snapshots, 0,
886 bkey_s_c_null, bkey_i_to_s_c(&n->k_i), 0);
890 new_snapids[i] = iter.pos.offset;
893 bch2_trans_iter_exit(trans, &iter);
898 * Create new snapshot IDs as children of an existing snapshot ID:
900 static int bch2_snapshot_node_create_children(struct btree_trans *trans, u32 parent,
902 u32 *snapshot_subvols,
905 struct btree_iter iter;
906 struct bkey_i_snapshot *n_parent;
909 n_parent = bch2_bkey_get_mut_typed(trans, &iter,
910 BTREE_ID_snapshots, POS(0, parent),
912 ret = PTR_ERR_OR_ZERO(n_parent);
914 if (bch2_err_matches(ret, ENOENT))
915 bch_err(trans->c, "snapshot %u not found", parent);
919 if (n_parent->v.children[0] || n_parent->v.children[1]) {
920 bch_err(trans->c, "Trying to add child snapshot nodes to parent that already has children");
925 ret = create_snapids(trans, parent, le32_to_cpu(n_parent->v.tree),
926 new_snapids, snapshot_subvols, nr_snapids);
930 n_parent->v.children[0] = cpu_to_le32(new_snapids[0]);
931 n_parent->v.children[1] = cpu_to_le32(new_snapids[1]);
932 n_parent->v.subvol = 0;
933 SET_BCH_SNAPSHOT_SUBVOL(&n_parent->v, false);
935 bch2_trans_iter_exit(trans, &iter);
940 * Create a snapshot node that is the root of a new tree:
942 static int bch2_snapshot_node_create_tree(struct btree_trans *trans,
944 u32 *snapshot_subvols,
947 struct bkey_i_snapshot_tree *n_tree;
950 n_tree = __snapshot_tree_create(trans);
951 ret = PTR_ERR_OR_ZERO(n_tree) ?:
952 create_snapids(trans, 0, n_tree->k.p.offset,
953 new_snapids, snapshot_subvols, nr_snapids);
957 n_tree->v.master_subvol = cpu_to_le32(snapshot_subvols[0]);
958 n_tree->v.root_snapshot = cpu_to_le32(new_snapids[0]);
962 int bch2_snapshot_node_create(struct btree_trans *trans, u32 parent,
964 u32 *snapshot_subvols,
967 BUG_ON((parent == 0) != (nr_snapids == 1));
968 BUG_ON((parent != 0) != (nr_snapids == 2));
971 ? bch2_snapshot_node_create_children(trans, parent,
972 new_snapids, snapshot_subvols, nr_snapids)
973 : bch2_snapshot_node_create_tree(trans,
974 new_snapids, snapshot_subvols, nr_snapids);
978 static int snapshot_delete_key(struct btree_trans *trans,
979 struct btree_iter *iter,
981 snapshot_id_list *deleted,
982 snapshot_id_list *equiv_seen,
983 struct bpos *last_pos)
985 struct bch_fs *c = trans->c;
986 u32 equiv = snapshot_t(c, k.k->p.snapshot)->equiv;
988 if (!bkey_eq(k.k->p, *last_pos))
992 if (snapshot_list_has_id(deleted, k.k->p.snapshot) ||
993 snapshot_list_has_id(equiv_seen, equiv)) {
994 return bch2_btree_delete_at(trans, iter,
995 BTREE_UPDATE_INTERNAL_SNAPSHOT_NODE);
997 return snapshot_list_add(c, equiv_seen, equiv);
1001 static int bch2_delete_redundant_snapshot(struct btree_trans *trans, struct btree_iter *iter,
1004 struct bkey_s_c_snapshot snap;
1008 if (k.k->type != KEY_TYPE_snapshot)
1011 snap = bkey_s_c_to_snapshot(k);
1012 if (BCH_SNAPSHOT_DELETED(snap.v) ||
1013 BCH_SNAPSHOT_SUBVOL(snap.v))
1016 children[0] = le32_to_cpu(snap.v->children[0]);
1017 children[1] = le32_to_cpu(snap.v->children[1]);
1019 ret = snapshot_live(trans, children[0]) ?:
1020 snapshot_live(trans, children[1]);
1025 return bch2_snapshot_node_set_deleted(trans, k.k->p.offset);
1029 int bch2_delete_dead_snapshots(struct bch_fs *c)
1031 struct btree_trans trans;
1032 struct btree_iter iter;
1034 struct bkey_s_c_snapshot snap;
1035 snapshot_id_list deleted = { 0 };
1039 if (!test_bit(BCH_FS_HAVE_DELETED_SNAPSHOTS, &c->flags))
1042 if (!test_bit(BCH_FS_STARTED, &c->flags)) {
1043 ret = bch2_fs_read_write_early(c);
1045 bch_err(c, "error deleleting dead snapshots: error going rw: %s", bch2_err_str(ret));
1050 bch2_trans_init(&trans, c, 0, 0);
1053 * For every snapshot node: If we have no live children and it's not
1054 * pointed to by a subvolume, delete it:
1056 ret = for_each_btree_key_commit(&trans, iter, BTREE_ID_snapshots,
1059 bch2_delete_redundant_snapshot(&trans, &iter, k));
1061 bch_err(c, "error deleting redundant snapshots: %s", bch2_err_str(ret));
1065 for_each_btree_key2(&trans, iter, BTREE_ID_snapshots,
1067 bch2_snapshot_set_equiv(&trans, k));
1069 bch_err(c, "error in bch2_snapshots_set_equiv: %s", bch2_err_str(ret));
1073 for_each_btree_key(&trans, iter, BTREE_ID_snapshots,
1074 POS_MIN, 0, k, ret) {
1075 if (k.k->type != KEY_TYPE_snapshot)
1078 snap = bkey_s_c_to_snapshot(k);
1079 if (BCH_SNAPSHOT_DELETED(snap.v)) {
1080 ret = snapshot_list_add(c, &deleted, k.k->p.offset);
1085 bch2_trans_iter_exit(&trans, &iter);
1088 bch_err(c, "error walking snapshots: %s", bch2_err_str(ret));
1092 for (id = 0; id < BTREE_ID_NR; id++) {
1093 struct bpos last_pos = POS_MIN;
1094 snapshot_id_list equiv_seen = { 0 };
1096 if (!btree_type_has_snapshots(id))
1099 ret = for_each_btree_key_commit(&trans, iter,
1101 BTREE_ITER_PREFETCH|BTREE_ITER_ALL_SNAPSHOTS, k,
1102 NULL, NULL, BTREE_INSERT_NOFAIL,
1103 snapshot_delete_key(&trans, &iter, k, &deleted, &equiv_seen, &last_pos));
1105 darray_exit(&equiv_seen);
1108 bch_err(c, "error deleting snapshot keys: %s", bch2_err_str(ret));
1113 for (i = 0; i < deleted.nr; i++) {
1114 ret = commit_do(&trans, NULL, NULL, 0,
1115 bch2_snapshot_node_delete(&trans, deleted.data[i]));
1117 bch_err(c, "error deleting snapshot %u: %s",
1118 deleted.data[i], bch2_err_str(ret));
1123 clear_bit(BCH_FS_HAVE_DELETED_SNAPSHOTS, &c->flags);
1125 darray_exit(&deleted);
1126 bch2_trans_exit(&trans);
1132 static void bch2_delete_dead_snapshots_work(struct work_struct *work)
1134 struct bch_fs *c = container_of(work, struct bch_fs, snapshot_delete_work);
1136 bch2_delete_dead_snapshots(c);
1137 bch2_write_ref_put(c, BCH_WRITE_REF_delete_dead_snapshots);
1140 void bch2_delete_dead_snapshots_async(struct bch_fs *c)
1142 if (bch2_write_ref_tryget(c, BCH_WRITE_REF_delete_dead_snapshots) &&
1143 !queue_work(c->write_ref_wq, &c->snapshot_delete_work))
1144 bch2_write_ref_put(c, BCH_WRITE_REF_delete_dead_snapshots);
1147 static int bch2_delete_dead_snapshots_hook(struct btree_trans *trans,
1148 struct btree_trans_commit_hook *h)
1150 struct bch_fs *c = trans->c;
1152 set_bit(BCH_FS_HAVE_DELETED_SNAPSHOTS, &c->flags);
1154 if (c->curr_recovery_pass <= BCH_RECOVERY_PASS_delete_dead_snapshots)
1157 bch2_delete_dead_snapshots_async(c);
1163 int bch2_subvolume_invalid(const struct bch_fs *c, struct bkey_s_c k,
1164 unsigned flags, struct printbuf *err)
1166 if (bkey_lt(k.k->p, SUBVOL_POS_MIN) ||
1167 bkey_gt(k.k->p, SUBVOL_POS_MAX)) {
1168 prt_printf(err, "invalid pos");
1169 return -BCH_ERR_invalid_bkey;
1175 void bch2_subvolume_to_text(struct printbuf *out, struct bch_fs *c,
1178 struct bkey_s_c_subvolume s = bkey_s_c_to_subvolume(k);
1180 prt_printf(out, "root %llu snapshot id %u",
1181 le64_to_cpu(s.v->inode),
1182 le32_to_cpu(s.v->snapshot));
1184 if (bkey_val_bytes(s.k) > offsetof(struct bch_subvolume, parent))
1185 prt_printf(out, " parent %u", le32_to_cpu(s.v->parent));
1188 static __always_inline int
1189 bch2_subvolume_get_inlined(struct btree_trans *trans, unsigned subvol,
1190 bool inconsistent_if_not_found,
1192 struct bch_subvolume *s)
1194 int ret = bch2_bkey_get_val_typed(trans, BTREE_ID_subvolumes, POS(0, subvol),
1195 iter_flags, subvolume, s);
1196 bch2_fs_inconsistent_on(bch2_err_matches(ret, ENOENT) &&
1197 inconsistent_if_not_found,
1198 trans->c, "missing subvolume %u", subvol);
1202 int bch2_subvolume_get(struct btree_trans *trans, unsigned subvol,
1203 bool inconsistent_if_not_found,
1205 struct bch_subvolume *s)
1207 return bch2_subvolume_get_inlined(trans, subvol, inconsistent_if_not_found, iter_flags, s);
1210 int bch2_snapshot_get_subvol(struct btree_trans *trans, u32 snapshot,
1211 struct bch_subvolume *subvol)
1213 struct bch_snapshot snap;
1215 return snapshot_lookup(trans, snapshot, &snap) ?:
1216 bch2_subvolume_get(trans, le32_to_cpu(snap.subvol), true, 0, subvol);
1219 int bch2_subvolume_get_snapshot(struct btree_trans *trans, u32 subvol,
1222 struct btree_iter iter;
1226 k = bch2_bkey_get_iter(trans, &iter, BTREE_ID_subvolumes, POS(0, subvol),
1228 BTREE_ITER_WITH_UPDATES);
1229 ret = bkey_err(k) ?: k.k->type == KEY_TYPE_subvolume ? 0 : -BCH_ERR_ENOENT_subvolume;
1232 *snapid = le32_to_cpu(bkey_s_c_to_subvolume(k).v->snapshot);
1233 else if (bch2_err_matches(ret, ENOENT))
1234 bch2_fs_inconsistent(trans->c, "missing subvolume %u", subvol);
1235 bch2_trans_iter_exit(trans, &iter);
1239 static int bch2_subvolume_reparent(struct btree_trans *trans,
1240 struct btree_iter *iter,
1242 u32 old_parent, u32 new_parent)
1244 struct bkey_i_subvolume *s;
1247 if (k.k->type != KEY_TYPE_subvolume)
1250 if (bkey_val_bytes(k.k) > offsetof(struct bch_subvolume, parent) &&
1251 le32_to_cpu(bkey_s_c_to_subvolume(k).v->parent) != old_parent)
1254 s = bch2_bkey_make_mut_typed(trans, iter, &k, 0, subvolume);
1255 ret = PTR_ERR_OR_ZERO(s);
1259 s->v.parent = cpu_to_le32(new_parent);
1264 * Scan for subvolumes with parent @subvolid_to_delete, reparent:
1266 static int bch2_subvolumes_reparent(struct btree_trans *trans, u32 subvolid_to_delete)
1268 struct btree_iter iter;
1270 struct bch_subvolume s;
1272 return lockrestart_do(trans,
1273 bch2_subvolume_get(trans, subvolid_to_delete, true,
1274 BTREE_ITER_CACHED, &s)) ?:
1275 for_each_btree_key_commit(trans, iter,
1276 BTREE_ID_subvolumes, POS_MIN, BTREE_ITER_PREFETCH, k,
1277 NULL, NULL, BTREE_INSERT_NOFAIL,
1278 bch2_subvolume_reparent(trans, &iter, k,
1279 subvolid_to_delete, le32_to_cpu(s.parent)));
1283 * Delete subvolume, mark snapshot ID as deleted, queue up snapshot
1286 static int __bch2_subvolume_delete(struct btree_trans *trans, u32 subvolid)
1288 struct btree_iter iter;
1289 struct bkey_s_c_subvolume subvol;
1290 struct btree_trans_commit_hook *h;
1294 subvol = bch2_bkey_get_iter_typed(trans, &iter,
1295 BTREE_ID_subvolumes, POS(0, subvolid),
1296 BTREE_ITER_CACHED|BTREE_ITER_INTENT,
1298 ret = bkey_err(subvol);
1299 bch2_fs_inconsistent_on(bch2_err_matches(ret, ENOENT), trans->c,
1300 "missing subvolume %u", subvolid);
1304 snapid = le32_to_cpu(subvol.v->snapshot);
1306 ret = bch2_btree_delete_at(trans, &iter, 0);
1310 ret = bch2_snapshot_node_set_deleted(trans, snapid);
1314 h = bch2_trans_kmalloc(trans, sizeof(*h));
1315 ret = PTR_ERR_OR_ZERO(h);
1319 h->fn = bch2_delete_dead_snapshots_hook;
1320 bch2_trans_commit_hook(trans, h);
1322 bch2_trans_iter_exit(trans, &iter);
1326 static int bch2_subvolume_delete(struct btree_trans *trans, u32 subvolid)
1328 return bch2_subvolumes_reparent(trans, subvolid) ?:
1329 commit_do(trans, NULL, NULL, BTREE_INSERT_NOFAIL,
1330 __bch2_subvolume_delete(trans, subvolid));
1333 static void bch2_subvolume_wait_for_pagecache_and_delete(struct work_struct *work)
1335 struct bch_fs *c = container_of(work, struct bch_fs,
1336 snapshot_wait_for_pagecache_and_delete_work);
1342 mutex_lock(&c->snapshots_unlinked_lock);
1343 s = c->snapshots_unlinked;
1344 darray_init(&c->snapshots_unlinked);
1345 mutex_unlock(&c->snapshots_unlinked_lock);
1350 bch2_evict_subvolume_inodes(c, &s);
1352 for (id = s.data; id < s.data + s.nr; id++) {
1353 ret = bch2_trans_run(c, bch2_subvolume_delete(&trans, *id));
1355 bch_err(c, "error deleting subvolume %u: %s", *id, bch2_err_str(ret));
1363 bch2_write_ref_put(c, BCH_WRITE_REF_snapshot_delete_pagecache);
1366 struct subvolume_unlink_hook {
1367 struct btree_trans_commit_hook h;
1371 static int bch2_subvolume_wait_for_pagecache_and_delete_hook(struct btree_trans *trans,
1372 struct btree_trans_commit_hook *_h)
1374 struct subvolume_unlink_hook *h = container_of(_h, struct subvolume_unlink_hook, h);
1375 struct bch_fs *c = trans->c;
1378 mutex_lock(&c->snapshots_unlinked_lock);
1379 if (!snapshot_list_has_id(&c->snapshots_unlinked, h->subvol))
1380 ret = snapshot_list_add(c, &c->snapshots_unlinked, h->subvol);
1381 mutex_unlock(&c->snapshots_unlinked_lock);
1386 if (!bch2_write_ref_tryget(c, BCH_WRITE_REF_snapshot_delete_pagecache))
1389 if (!queue_work(c->write_ref_wq, &c->snapshot_wait_for_pagecache_and_delete_work))
1390 bch2_write_ref_put(c, BCH_WRITE_REF_snapshot_delete_pagecache);
1394 int bch2_subvolume_unlink(struct btree_trans *trans, u32 subvolid)
1396 struct btree_iter iter;
1397 struct bkey_i_subvolume *n;
1398 struct subvolume_unlink_hook *h;
1401 h = bch2_trans_kmalloc(trans, sizeof(*h));
1402 ret = PTR_ERR_OR_ZERO(h);
1406 h->h.fn = bch2_subvolume_wait_for_pagecache_and_delete_hook;
1407 h->subvol = subvolid;
1408 bch2_trans_commit_hook(trans, &h->h);
1410 n = bch2_bkey_get_mut_typed(trans, &iter,
1411 BTREE_ID_subvolumes, POS(0, subvolid),
1412 BTREE_ITER_CACHED, subvolume);
1413 ret = PTR_ERR_OR_ZERO(n);
1414 if (unlikely(ret)) {
1415 bch2_fs_inconsistent_on(bch2_err_matches(ret, ENOENT), trans->c,
1416 "missing subvolume %u", subvolid);
1420 SET_BCH_SUBVOLUME_UNLINKED(&n->v, true);
1421 bch2_trans_iter_exit(trans, &iter);
1425 int bch2_subvolume_create(struct btree_trans *trans, u64 inode,
1428 u32 *new_snapshotid,
1431 struct bch_fs *c = trans->c;
1432 struct btree_iter dst_iter, src_iter = (struct btree_iter) { NULL };
1433 struct bkey_i_subvolume *new_subvol = NULL;
1434 struct bkey_i_subvolume *src_subvol = NULL;
1435 u32 parent = 0, new_nodes[2], snapshot_subvols[2];
1438 ret = bch2_bkey_get_empty_slot(trans, &dst_iter,
1439 BTREE_ID_subvolumes, POS(0, U32_MAX));
1440 if (ret == -BCH_ERR_ENOSPC_btree_slot)
1441 ret = -BCH_ERR_ENOSPC_subvolume_create;
1445 snapshot_subvols[0] = dst_iter.pos.offset;
1446 snapshot_subvols[1] = src_subvolid;
1449 /* Creating a snapshot: */
1451 src_subvol = bch2_bkey_get_mut_typed(trans, &src_iter,
1452 BTREE_ID_subvolumes, POS(0, src_subvolid),
1453 BTREE_ITER_CACHED, subvolume);
1454 ret = PTR_ERR_OR_ZERO(src_subvol);
1455 if (unlikely(ret)) {
1456 bch2_fs_inconsistent_on(bch2_err_matches(ret, ENOENT), c,
1457 "subvolume %u not found", src_subvolid);
1461 parent = le32_to_cpu(src_subvol->v.snapshot);
1464 ret = bch2_snapshot_node_create(trans, parent, new_nodes,
1466 src_subvolid ? 2 : 1);
1471 src_subvol->v.snapshot = cpu_to_le32(new_nodes[1]);
1472 ret = bch2_trans_update(trans, &src_iter, &src_subvol->k_i, 0);
1477 new_subvol = bch2_bkey_alloc(trans, &dst_iter, 0, subvolume);
1478 ret = PTR_ERR_OR_ZERO(new_subvol);
1482 new_subvol->v.flags = 0;
1483 new_subvol->v.snapshot = cpu_to_le32(new_nodes[0]);
1484 new_subvol->v.inode = cpu_to_le64(inode);
1485 new_subvol->v.parent = cpu_to_le32(src_subvolid);
1486 new_subvol->v.otime.lo = cpu_to_le64(bch2_current_time(c));
1487 new_subvol->v.otime.hi = 0;
1489 SET_BCH_SUBVOLUME_RO(&new_subvol->v, ro);
1490 SET_BCH_SUBVOLUME_SNAP(&new_subvol->v, src_subvolid != 0);
1492 *new_subvolid = new_subvol->k.p.offset;
1493 *new_snapshotid = new_nodes[0];
1495 bch2_trans_iter_exit(trans, &src_iter);
1496 bch2_trans_iter_exit(trans, &dst_iter);
1500 int bch2_fs_subvolumes_init(struct bch_fs *c)
1502 INIT_WORK(&c->snapshot_delete_work, bch2_delete_dead_snapshots_work);
1503 INIT_WORK(&c->snapshot_wait_for_pagecache_and_delete_work,
1504 bch2_subvolume_wait_for_pagecache_and_delete);
1505 mutex_init(&c->snapshots_unlinked_lock);