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