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