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