1 // SPDX-License-Identifier: GPL-2.0 2 3 #include "bcachefs.h" 4 #include "bkey_buf.h" 5 #include "btree_cache.h" 6 #include "btree_update.h" 7 #include "buckets.h" 8 #include "darray.h" 9 #include "dirent.h" 10 #include "error.h" 11 #include "fs-common.h" 12 #include "fsck.h" 13 #include "inode.h" 14 #include "keylist.h" 15 #include "recovery.h" 16 #include "snapshot.h" 17 #include "super.h" 18 #include "xattr.h" 19 20 #include <linux/bsearch.h> 21 #include <linux/dcache.h> /* struct qstr */ 22 23 #define QSTR(n) { { { .len = strlen(n) } }, .name = n } 24 25 /* 26 * XXX: this is handling transaction restarts without returning 27 * -BCH_ERR_transaction_restart_nested, this is not how we do things anymore: 28 */ 29 static s64 bch2_count_inode_sectors(struct btree_trans *trans, u64 inum, 30 u32 snapshot) 31 { 32 struct btree_iter iter; 33 struct bkey_s_c k; 34 u64 sectors = 0; 35 int ret; 36 37 for_each_btree_key_upto(trans, iter, BTREE_ID_extents, 38 SPOS(inum, 0, snapshot), 39 POS(inum, U64_MAX), 40 0, k, ret) 41 if (bkey_extent_is_allocation(k.k)) 42 sectors += k.k->size; 43 44 bch2_trans_iter_exit(trans, &iter); 45 46 return ret ?: sectors; 47 } 48 49 static s64 bch2_count_subdirs(struct btree_trans *trans, u64 inum, 50 u32 snapshot) 51 { 52 struct btree_iter iter; 53 struct bkey_s_c k; 54 struct bkey_s_c_dirent d; 55 u64 subdirs = 0; 56 int ret; 57 58 for_each_btree_key_upto(trans, iter, BTREE_ID_dirents, 59 SPOS(inum, 0, snapshot), 60 POS(inum, U64_MAX), 61 0, k, ret) { 62 if (k.k->type != KEY_TYPE_dirent) 63 continue; 64 65 d = bkey_s_c_to_dirent(k); 66 if (d.v->d_type == DT_DIR) 67 subdirs++; 68 } 69 bch2_trans_iter_exit(trans, &iter); 70 71 return ret ?: subdirs; 72 } 73 74 static int __snapshot_lookup_subvol(struct btree_trans *trans, u32 snapshot, 75 u32 *subvol) 76 { 77 struct bch_snapshot s; 78 int ret = bch2_bkey_get_val_typed(trans, BTREE_ID_snapshots, 79 POS(0, snapshot), 0, 80 snapshot, &s); 81 if (!ret) 82 *subvol = le32_to_cpu(s.subvol); 83 else if (bch2_err_matches(ret, ENOENT)) 84 bch_err(trans->c, "snapshot %u not found", snapshot); 85 return ret; 86 87 } 88 89 static int __subvol_lookup(struct btree_trans *trans, u32 subvol, 90 u32 *snapshot, u64 *inum) 91 { 92 struct bch_subvolume s; 93 int ret; 94 95 ret = bch2_subvolume_get(trans, subvol, false, 0, &s); 96 97 *snapshot = le32_to_cpu(s.snapshot); 98 *inum = le64_to_cpu(s.inode); 99 return ret; 100 } 101 102 static int subvol_lookup(struct btree_trans *trans, u32 subvol, 103 u32 *snapshot, u64 *inum) 104 { 105 return lockrestart_do(trans, __subvol_lookup(trans, subvol, snapshot, inum)); 106 } 107 108 static int lookup_first_inode(struct btree_trans *trans, u64 inode_nr, 109 struct bch_inode_unpacked *inode) 110 { 111 struct btree_iter iter; 112 struct bkey_s_c k; 113 int ret; 114 115 bch2_trans_iter_init(trans, &iter, BTREE_ID_inodes, 116 POS(0, inode_nr), 117 BTREE_ITER_ALL_SNAPSHOTS); 118 k = bch2_btree_iter_peek(&iter); 119 ret = bkey_err(k); 120 if (ret) 121 goto err; 122 123 if (!k.k || !bkey_eq(k.k->p, POS(0, inode_nr))) { 124 ret = -BCH_ERR_ENOENT_inode; 125 goto err; 126 } 127 128 ret = bch2_inode_unpack(k, inode); 129 err: 130 bch_err_msg(trans->c, ret, "fetching inode %llu", inode_nr); 131 bch2_trans_iter_exit(trans, &iter); 132 return ret; 133 } 134 135 static int __lookup_inode(struct btree_trans *trans, u64 inode_nr, 136 struct bch_inode_unpacked *inode, 137 u32 *snapshot) 138 { 139 struct btree_iter iter; 140 struct bkey_s_c k; 141 int ret; 142 143 k = bch2_bkey_get_iter(trans, &iter, BTREE_ID_inodes, 144 SPOS(0, inode_nr, *snapshot), 0); 145 ret = bkey_err(k); 146 if (ret) 147 goto err; 148 149 ret = bkey_is_inode(k.k) 150 ? bch2_inode_unpack(k, inode) 151 : -BCH_ERR_ENOENT_inode; 152 if (!ret) 153 *snapshot = iter.pos.snapshot; 154 err: 155 bch_err_msg(trans->c, ret, "fetching inode %llu:%u", inode_nr, *snapshot); 156 bch2_trans_iter_exit(trans, &iter); 157 return ret; 158 } 159 160 static int lookup_inode(struct btree_trans *trans, u64 inode_nr, 161 struct bch_inode_unpacked *inode, 162 u32 *snapshot) 163 { 164 return lockrestart_do(trans, __lookup_inode(trans, inode_nr, inode, snapshot)); 165 } 166 167 static int __lookup_dirent(struct btree_trans *trans, 168 struct bch_hash_info hash_info, 169 subvol_inum dir, struct qstr *name, 170 u64 *target, unsigned *type) 171 { 172 struct btree_iter iter; 173 struct bkey_s_c_dirent d; 174 int ret; 175 176 ret = bch2_hash_lookup(trans, &iter, bch2_dirent_hash_desc, 177 &hash_info, dir, name, 0); 178 if (ret) 179 return ret; 180 181 d = bkey_s_c_to_dirent(bch2_btree_iter_peek_slot(&iter)); 182 *target = le64_to_cpu(d.v->d_inum); 183 *type = d.v->d_type; 184 bch2_trans_iter_exit(trans, &iter); 185 return 0; 186 } 187 188 static int __write_inode(struct btree_trans *trans, 189 struct bch_inode_unpacked *inode, 190 u32 snapshot) 191 { 192 struct bkey_inode_buf *inode_p = 193 bch2_trans_kmalloc(trans, sizeof(*inode_p)); 194 195 if (IS_ERR(inode_p)) 196 return PTR_ERR(inode_p); 197 198 bch2_inode_pack(inode_p, inode); 199 inode_p->inode.k.p.snapshot = snapshot; 200 201 return bch2_btree_insert_nonextent(trans, BTREE_ID_inodes, 202 &inode_p->inode.k_i, 203 BTREE_UPDATE_INTERNAL_SNAPSHOT_NODE); 204 } 205 206 static int fsck_write_inode(struct btree_trans *trans, 207 struct bch_inode_unpacked *inode, 208 u32 snapshot) 209 { 210 int ret = commit_do(trans, NULL, NULL, 211 BTREE_INSERT_NOFAIL| 212 BTREE_INSERT_LAZY_RW, 213 __write_inode(trans, inode, snapshot)); 214 if (ret) 215 bch_err_fn(trans->c, ret); 216 return ret; 217 } 218 219 static int __remove_dirent(struct btree_trans *trans, struct bpos pos) 220 { 221 struct bch_fs *c = trans->c; 222 struct btree_iter iter; 223 struct bch_inode_unpacked dir_inode; 224 struct bch_hash_info dir_hash_info; 225 int ret; 226 227 ret = lookup_first_inode(trans, pos.inode, &dir_inode); 228 if (ret) 229 goto err; 230 231 dir_hash_info = bch2_hash_info_init(c, &dir_inode); 232 233 bch2_trans_iter_init(trans, &iter, BTREE_ID_dirents, pos, BTREE_ITER_INTENT); 234 235 ret = bch2_hash_delete_at(trans, bch2_dirent_hash_desc, 236 &dir_hash_info, &iter, 237 BTREE_UPDATE_INTERNAL_SNAPSHOT_NODE); 238 bch2_trans_iter_exit(trans, &iter); 239 err: 240 bch_err_fn(c, ret); 241 return ret; 242 } 243 244 /* Get lost+found, create if it doesn't exist: */ 245 static int lookup_lostfound(struct btree_trans *trans, u32 subvol, 246 struct bch_inode_unpacked *lostfound) 247 { 248 struct bch_fs *c = trans->c; 249 struct bch_inode_unpacked root; 250 struct bch_hash_info root_hash_info; 251 struct qstr lostfound_str = QSTR("lost+found"); 252 subvol_inum root_inum = { .subvol = subvol }; 253 u64 inum = 0; 254 unsigned d_type = 0; 255 u32 snapshot; 256 int ret; 257 258 ret = __subvol_lookup(trans, subvol, &snapshot, &root_inum.inum); 259 if (ret) 260 return ret; 261 262 ret = __lookup_inode(trans, root_inum.inum, &root, &snapshot); 263 if (ret) 264 return ret; 265 266 root_hash_info = bch2_hash_info_init(c, &root); 267 268 ret = __lookup_dirent(trans, root_hash_info, root_inum, 269 &lostfound_str, &inum, &d_type); 270 if (bch2_err_matches(ret, ENOENT)) { 271 bch_notice(c, "creating lost+found"); 272 goto create_lostfound; 273 } 274 275 bch_err_fn(c, ret); 276 if (ret) 277 return ret; 278 279 if (d_type != DT_DIR) { 280 bch_err(c, "error looking up lost+found: not a directory"); 281 return -BCH_ERR_ENOENT_not_directory; 282 } 283 284 /* 285 * The bch2_check_dirents pass has already run, dangling dirents 286 * shouldn't exist here: 287 */ 288 return __lookup_inode(trans, inum, lostfound, &snapshot); 289 290 create_lostfound: 291 bch2_inode_init_early(c, lostfound); 292 293 ret = bch2_create_trans(trans, root_inum, &root, 294 lostfound, &lostfound_str, 295 0, 0, S_IFDIR|0700, 0, NULL, NULL, 296 (subvol_inum) { }, 0); 297 bch_err_msg(c, ret, "creating lost+found"); 298 return ret; 299 } 300 301 static int __reattach_inode(struct btree_trans *trans, 302 struct bch_inode_unpacked *inode, 303 u32 inode_snapshot) 304 { 305 struct bch_hash_info dir_hash; 306 struct bch_inode_unpacked lostfound; 307 char name_buf[20]; 308 struct qstr name; 309 u64 dir_offset = 0; 310 u32 subvol; 311 int ret; 312 313 ret = __snapshot_lookup_subvol(trans, inode_snapshot, &subvol); 314 if (ret) 315 return ret; 316 317 ret = lookup_lostfound(trans, subvol, &lostfound); 318 if (ret) 319 return ret; 320 321 if (S_ISDIR(inode->bi_mode)) { 322 lostfound.bi_nlink++; 323 324 ret = __write_inode(trans, &lostfound, U32_MAX); 325 if (ret) 326 return ret; 327 } 328 329 dir_hash = bch2_hash_info_init(trans->c, &lostfound); 330 331 snprintf(name_buf, sizeof(name_buf), "%llu", inode->bi_inum); 332 name = (struct qstr) QSTR(name_buf); 333 334 ret = bch2_dirent_create(trans, 335 (subvol_inum) { 336 .subvol = subvol, 337 .inum = lostfound.bi_inum, 338 }, 339 &dir_hash, 340 inode_d_type(inode), 341 &name, inode->bi_inum, &dir_offset, 342 BCH_HASH_SET_MUST_CREATE); 343 if (ret) 344 return ret; 345 346 inode->bi_dir = lostfound.bi_inum; 347 inode->bi_dir_offset = dir_offset; 348 349 return __write_inode(trans, inode, inode_snapshot); 350 } 351 352 static int reattach_inode(struct btree_trans *trans, 353 struct bch_inode_unpacked *inode, 354 u32 inode_snapshot) 355 { 356 int ret = commit_do(trans, NULL, NULL, 357 BTREE_INSERT_LAZY_RW| 358 BTREE_INSERT_NOFAIL, 359 __reattach_inode(trans, inode, inode_snapshot)); 360 bch_err_msg(trans->c, ret, "reattaching inode %llu", inode->bi_inum); 361 return ret; 362 } 363 364 static int remove_backpointer(struct btree_trans *trans, 365 struct bch_inode_unpacked *inode) 366 { 367 struct btree_iter iter; 368 struct bkey_s_c_dirent d; 369 int ret; 370 371 d = bch2_bkey_get_iter_typed(trans, &iter, BTREE_ID_dirents, 372 POS(inode->bi_dir, inode->bi_dir_offset), 0, 373 dirent); 374 ret = bkey_err(d) ?: 375 __remove_dirent(trans, d.k->p); 376 bch2_trans_iter_exit(trans, &iter); 377 return ret; 378 } 379 380 struct snapshots_seen_entry { 381 u32 id; 382 u32 equiv; 383 }; 384 385 struct snapshots_seen { 386 struct bpos pos; 387 DARRAY(struct snapshots_seen_entry) ids; 388 }; 389 390 static inline void snapshots_seen_exit(struct snapshots_seen *s) 391 { 392 darray_exit(&s->ids); 393 } 394 395 static inline void snapshots_seen_init(struct snapshots_seen *s) 396 { 397 memset(s, 0, sizeof(*s)); 398 } 399 400 static int snapshots_seen_add_inorder(struct bch_fs *c, struct snapshots_seen *s, u32 id) 401 { 402 struct snapshots_seen_entry *i, n = { 403 .id = id, 404 .equiv = bch2_snapshot_equiv(c, id), 405 }; 406 int ret = 0; 407 408 darray_for_each(s->ids, i) { 409 if (i->id == id) 410 return 0; 411 if (i->id > id) 412 break; 413 } 414 415 ret = darray_insert_item(&s->ids, i - s->ids.data, n); 416 if (ret) 417 bch_err(c, "error reallocating snapshots_seen table (size %zu)", 418 s->ids.size); 419 return ret; 420 } 421 422 static int snapshots_seen_update(struct bch_fs *c, struct snapshots_seen *s, 423 enum btree_id btree_id, struct bpos pos) 424 { 425 struct snapshots_seen_entry *i, n = { 426 .id = pos.snapshot, 427 .equiv = bch2_snapshot_equiv(c, pos.snapshot), 428 }; 429 int ret = 0; 430 431 if (!bkey_eq(s->pos, pos)) 432 s->ids.nr = 0; 433 434 s->pos = pos; 435 s->pos.snapshot = n.equiv; 436 437 darray_for_each(s->ids, i) { 438 if (i->id == n.id) 439 return 0; 440 441 /* 442 * We currently don't rigorously track for snapshot cleanup 443 * needing to be run, so it shouldn't be a fsck error yet: 444 */ 445 if (i->equiv == n.equiv) { 446 bch_err(c, "snapshot deletion did not finish:\n" 447 " duplicate keys in btree %s at %llu:%llu snapshots %u, %u (equiv %u)\n", 448 bch2_btree_id_str(btree_id), 449 pos.inode, pos.offset, 450 i->id, n.id, n.equiv); 451 set_bit(BCH_FS_NEED_DELETE_DEAD_SNAPSHOTS, &c->flags); 452 return bch2_run_explicit_recovery_pass(c, BCH_RECOVERY_PASS_delete_dead_snapshots); 453 } 454 } 455 456 ret = darray_push(&s->ids, n); 457 if (ret) 458 bch_err(c, "error reallocating snapshots_seen table (size %zu)", 459 s->ids.size); 460 return ret; 461 } 462 463 /** 464 * key_visible_in_snapshot - returns true if @id is a descendent of @ancestor, 465 * and @ancestor hasn't been overwritten in @seen 466 * 467 * @c: filesystem handle 468 * @seen: list of snapshot ids already seen at current position 469 * @id: descendent snapshot id 470 * @ancestor: ancestor snapshot id 471 * 472 * Returns: whether key in @ancestor snapshot is visible in @id snapshot 473 */ 474 static bool key_visible_in_snapshot(struct bch_fs *c, struct snapshots_seen *seen, 475 u32 id, u32 ancestor) 476 { 477 ssize_t i; 478 479 EBUG_ON(id > ancestor); 480 EBUG_ON(!bch2_snapshot_is_equiv(c, id)); 481 EBUG_ON(!bch2_snapshot_is_equiv(c, ancestor)); 482 483 /* @ancestor should be the snapshot most recently added to @seen */ 484 EBUG_ON(ancestor != seen->pos.snapshot); 485 EBUG_ON(ancestor != seen->ids.data[seen->ids.nr - 1].equiv); 486 487 if (id == ancestor) 488 return true; 489 490 if (!bch2_snapshot_is_ancestor(c, id, ancestor)) 491 return false; 492 493 /* 494 * We know that @id is a descendant of @ancestor, we're checking if 495 * we've seen a key that overwrote @ancestor - i.e. also a descendent of 496 * @ascestor and with @id as a descendent. 497 * 498 * But we already know that we're scanning IDs between @id and @ancestor 499 * numerically, since snapshot ID lists are kept sorted, so if we find 500 * an id that's an ancestor of @id we're done: 501 */ 502 503 for (i = seen->ids.nr - 2; 504 i >= 0 && seen->ids.data[i].equiv >= id; 505 --i) 506 if (bch2_snapshot_is_ancestor(c, id, seen->ids.data[i].equiv)) 507 return false; 508 509 return true; 510 } 511 512 /** 513 * ref_visible - given a key with snapshot id @src that points to a key with 514 * snapshot id @dst, test whether there is some snapshot in which @dst is 515 * visible. 516 * 517 * @c: filesystem handle 518 * @s: list of snapshot IDs already seen at @src 519 * @src: snapshot ID of src key 520 * @dst: snapshot ID of dst key 521 * Returns: true if there is some snapshot in which @dst is visible 522 * 523 * Assumes we're visiting @src keys in natural key order 524 */ 525 static bool ref_visible(struct bch_fs *c, struct snapshots_seen *s, 526 u32 src, u32 dst) 527 { 528 return dst <= src 529 ? key_visible_in_snapshot(c, s, dst, src) 530 : bch2_snapshot_is_ancestor(c, src, dst); 531 } 532 533 static int ref_visible2(struct bch_fs *c, 534 u32 src, struct snapshots_seen *src_seen, 535 u32 dst, struct snapshots_seen *dst_seen) 536 { 537 src = bch2_snapshot_equiv(c, src); 538 dst = bch2_snapshot_equiv(c, dst); 539 540 if (dst > src) { 541 swap(dst, src); 542 swap(dst_seen, src_seen); 543 } 544 return key_visible_in_snapshot(c, src_seen, dst, src); 545 } 546 547 #define for_each_visible_inode(_c, _s, _w, _snapshot, _i) \ 548 for (_i = (_w)->inodes.data; _i < (_w)->inodes.data + (_w)->inodes.nr && \ 549 (_i)->snapshot <= (_snapshot); _i++) \ 550 if (key_visible_in_snapshot(_c, _s, _i->snapshot, _snapshot)) 551 552 struct inode_walker_entry { 553 struct bch_inode_unpacked inode; 554 u32 snapshot; 555 bool seen_this_pos; 556 u64 count; 557 }; 558 559 struct inode_walker { 560 bool first_this_inode; 561 bool recalculate_sums; 562 struct bpos last_pos; 563 564 DARRAY(struct inode_walker_entry) inodes; 565 }; 566 567 static void inode_walker_exit(struct inode_walker *w) 568 { 569 darray_exit(&w->inodes); 570 } 571 572 static struct inode_walker inode_walker_init(void) 573 { 574 return (struct inode_walker) { 0, }; 575 } 576 577 static int add_inode(struct bch_fs *c, struct inode_walker *w, 578 struct bkey_s_c inode) 579 { 580 struct bch_inode_unpacked u; 581 582 BUG_ON(bch2_inode_unpack(inode, &u)); 583 584 return darray_push(&w->inodes, ((struct inode_walker_entry) { 585 .inode = u, 586 .snapshot = bch2_snapshot_equiv(c, inode.k->p.snapshot), 587 })); 588 } 589 590 static int get_inodes_all_snapshots(struct btree_trans *trans, 591 struct inode_walker *w, u64 inum) 592 { 593 struct bch_fs *c = trans->c; 594 struct btree_iter iter; 595 struct bkey_s_c k; 596 u32 restart_count = trans->restart_count; 597 int ret; 598 599 w->recalculate_sums = false; 600 w->inodes.nr = 0; 601 602 for_each_btree_key(trans, iter, BTREE_ID_inodes, POS(0, inum), 603 BTREE_ITER_ALL_SNAPSHOTS, k, ret) { 604 if (k.k->p.offset != inum) 605 break; 606 607 if (bkey_is_inode(k.k)) 608 add_inode(c, w, k); 609 } 610 bch2_trans_iter_exit(trans, &iter); 611 612 if (ret) 613 return ret; 614 615 w->first_this_inode = true; 616 617 return trans_was_restarted(trans, restart_count); 618 } 619 620 static struct inode_walker_entry * 621 lookup_inode_for_snapshot(struct bch_fs *c, struct inode_walker *w, 622 u32 snapshot, bool is_whiteout) 623 { 624 struct inode_walker_entry *i; 625 626 snapshot = bch2_snapshot_equiv(c, snapshot); 627 628 darray_for_each(w->inodes, i) 629 if (bch2_snapshot_is_ancestor(c, snapshot, i->snapshot)) 630 goto found; 631 632 return NULL; 633 found: 634 BUG_ON(snapshot > i->snapshot); 635 636 if (snapshot != i->snapshot && !is_whiteout) { 637 struct inode_walker_entry new = *i; 638 size_t pos; 639 int ret; 640 641 new.snapshot = snapshot; 642 new.count = 0; 643 644 bch_info(c, "have key for inode %llu:%u but have inode in ancestor snapshot %u", 645 w->last_pos.inode, snapshot, i->snapshot); 646 647 while (i > w->inodes.data && i[-1].snapshot > snapshot) 648 --i; 649 650 pos = i - w->inodes.data; 651 ret = darray_insert_item(&w->inodes, pos, new); 652 if (ret) 653 return ERR_PTR(ret); 654 655 i = w->inodes.data + pos; 656 } 657 658 return i; 659 } 660 661 static struct inode_walker_entry *walk_inode(struct btree_trans *trans, 662 struct inode_walker *w, struct bpos pos, 663 bool is_whiteout) 664 { 665 if (w->last_pos.inode != pos.inode) { 666 int ret = get_inodes_all_snapshots(trans, w, pos.inode); 667 if (ret) 668 return ERR_PTR(ret); 669 } else if (bkey_cmp(w->last_pos, pos)) { 670 struct inode_walker_entry *i; 671 672 darray_for_each(w->inodes, i) 673 i->seen_this_pos = false; 674 675 } 676 677 w->last_pos = pos; 678 679 return lookup_inode_for_snapshot(trans->c, w, pos.snapshot, is_whiteout); 680 } 681 682 static int __get_visible_inodes(struct btree_trans *trans, 683 struct inode_walker *w, 684 struct snapshots_seen *s, 685 u64 inum) 686 { 687 struct bch_fs *c = trans->c; 688 struct btree_iter iter; 689 struct bkey_s_c k; 690 int ret; 691 692 w->inodes.nr = 0; 693 694 for_each_btree_key_norestart(trans, iter, BTREE_ID_inodes, POS(0, inum), 695 BTREE_ITER_ALL_SNAPSHOTS, k, ret) { 696 u32 equiv = bch2_snapshot_equiv(c, k.k->p.snapshot); 697 698 if (k.k->p.offset != inum) 699 break; 700 701 if (!ref_visible(c, s, s->pos.snapshot, equiv)) 702 continue; 703 704 if (bkey_is_inode(k.k)) 705 add_inode(c, w, k); 706 707 if (equiv >= s->pos.snapshot) 708 break; 709 } 710 bch2_trans_iter_exit(trans, &iter); 711 712 return ret; 713 } 714 715 static int check_key_has_snapshot(struct btree_trans *trans, 716 struct btree_iter *iter, 717 struct bkey_s_c k) 718 { 719 struct bch_fs *c = trans->c; 720 struct printbuf buf = PRINTBUF; 721 int ret = 0; 722 723 if (mustfix_fsck_err_on(!bch2_snapshot_equiv(c, k.k->p.snapshot), c, 724 bkey_in_missing_snapshot, 725 "key in missing snapshot: %s", 726 (bch2_bkey_val_to_text(&buf, c, k), buf.buf))) 727 ret = bch2_btree_delete_at(trans, iter, 728 BTREE_UPDATE_INTERNAL_SNAPSHOT_NODE) ?: 1; 729 fsck_err: 730 printbuf_exit(&buf); 731 return ret; 732 } 733 734 static int hash_redo_key(struct btree_trans *trans, 735 const struct bch_hash_desc desc, 736 struct bch_hash_info *hash_info, 737 struct btree_iter *k_iter, struct bkey_s_c k) 738 { 739 struct bkey_i *delete; 740 struct bkey_i *tmp; 741 742 delete = bch2_trans_kmalloc(trans, sizeof(*delete)); 743 if (IS_ERR(delete)) 744 return PTR_ERR(delete); 745 746 tmp = bch2_bkey_make_mut_noupdate(trans, k); 747 if (IS_ERR(tmp)) 748 return PTR_ERR(tmp); 749 750 bkey_init(&delete->k); 751 delete->k.p = k_iter->pos; 752 return bch2_btree_iter_traverse(k_iter) ?: 753 bch2_trans_update(trans, k_iter, delete, 0) ?: 754 bch2_hash_set_snapshot(trans, desc, hash_info, 755 (subvol_inum) { 0, k.k->p.inode }, 756 k.k->p.snapshot, tmp, 757 BCH_HASH_SET_MUST_CREATE, 758 BTREE_UPDATE_INTERNAL_SNAPSHOT_NODE) ?: 759 bch2_trans_commit(trans, NULL, NULL, 760 BTREE_INSERT_NOFAIL| 761 BTREE_INSERT_LAZY_RW); 762 } 763 764 static int hash_check_key(struct btree_trans *trans, 765 const struct bch_hash_desc desc, 766 struct bch_hash_info *hash_info, 767 struct btree_iter *k_iter, struct bkey_s_c hash_k) 768 { 769 struct bch_fs *c = trans->c; 770 struct btree_iter iter = { NULL }; 771 struct printbuf buf = PRINTBUF; 772 struct bkey_s_c k; 773 u64 hash; 774 int ret = 0; 775 776 if (hash_k.k->type != desc.key_type) 777 return 0; 778 779 hash = desc.hash_bkey(hash_info, hash_k); 780 781 if (likely(hash == hash_k.k->p.offset)) 782 return 0; 783 784 if (hash_k.k->p.offset < hash) 785 goto bad_hash; 786 787 for_each_btree_key_norestart(trans, iter, desc.btree_id, 788 SPOS(hash_k.k->p.inode, hash, hash_k.k->p.snapshot), 789 BTREE_ITER_SLOTS, k, ret) { 790 if (bkey_eq(k.k->p, hash_k.k->p)) 791 break; 792 793 if (fsck_err_on(k.k->type == desc.key_type && 794 !desc.cmp_bkey(k, hash_k), c, 795 hash_table_key_duplicate, 796 "duplicate hash table keys:\n%s", 797 (printbuf_reset(&buf), 798 bch2_bkey_val_to_text(&buf, c, hash_k), 799 buf.buf))) { 800 ret = bch2_hash_delete_at(trans, desc, hash_info, k_iter, 0) ?: 1; 801 break; 802 } 803 804 if (bkey_deleted(k.k)) { 805 bch2_trans_iter_exit(trans, &iter); 806 goto bad_hash; 807 } 808 } 809 out: 810 bch2_trans_iter_exit(trans, &iter); 811 printbuf_exit(&buf); 812 return ret; 813 bad_hash: 814 if (fsck_err(c, hash_table_key_wrong_offset, 815 "hash table key at wrong offset: btree %s inode %llu offset %llu, hashed to %llu\n%s", 816 bch2_btree_id_str(desc.btree_id), hash_k.k->p.inode, hash_k.k->p.offset, hash, 817 (printbuf_reset(&buf), 818 bch2_bkey_val_to_text(&buf, c, hash_k), buf.buf))) { 819 ret = hash_redo_key(trans, desc, hash_info, k_iter, hash_k); 820 bch_err_fn(c, ret); 821 if (ret) 822 return ret; 823 ret = -BCH_ERR_transaction_restart_nested; 824 } 825 fsck_err: 826 goto out; 827 } 828 829 static int check_inode(struct btree_trans *trans, 830 struct btree_iter *iter, 831 struct bkey_s_c k, 832 struct bch_inode_unpacked *prev, 833 struct snapshots_seen *s, 834 bool full) 835 { 836 struct bch_fs *c = trans->c; 837 struct bch_inode_unpacked u; 838 bool do_update = false; 839 int ret; 840 841 ret = check_key_has_snapshot(trans, iter, k); 842 if (ret < 0) 843 goto err; 844 if (ret) 845 return 0; 846 847 ret = snapshots_seen_update(c, s, iter->btree_id, k.k->p); 848 if (ret) 849 goto err; 850 851 if (!bkey_is_inode(k.k)) 852 return 0; 853 854 BUG_ON(bch2_inode_unpack(k, &u)); 855 856 if (!full && 857 !(u.bi_flags & (BCH_INODE_i_size_dirty| 858 BCH_INODE_i_sectors_dirty| 859 BCH_INODE_unlinked))) 860 return 0; 861 862 if (prev->bi_inum != u.bi_inum) 863 *prev = u; 864 865 if (fsck_err_on(prev->bi_hash_seed != u.bi_hash_seed || 866 inode_d_type(prev) != inode_d_type(&u), 867 c, inode_snapshot_mismatch, 868 "inodes in different snapshots don't match")) { 869 bch_err(c, "repair not implemented yet"); 870 return -EINVAL; 871 } 872 873 if ((u.bi_flags & (BCH_INODE_i_size_dirty|BCH_INODE_unlinked)) && 874 bch2_key_has_snapshot_overwrites(trans, BTREE_ID_inodes, k.k->p)) { 875 struct bpos new_min_pos; 876 877 ret = bch2_propagate_key_to_snapshot_leaves(trans, iter->btree_id, k, &new_min_pos); 878 if (ret) 879 goto err; 880 881 u.bi_flags &= ~BCH_INODE_i_size_dirty|BCH_INODE_unlinked; 882 883 ret = __write_inode(trans, &u, iter->pos.snapshot); 884 bch_err_msg(c, ret, "in fsck updating inode"); 885 if (ret) 886 return ret; 887 888 if (!bpos_eq(new_min_pos, POS_MIN)) 889 bch2_btree_iter_set_pos(iter, bpos_predecessor(new_min_pos)); 890 return 0; 891 } 892 893 if (u.bi_flags & BCH_INODE_unlinked && 894 (!c->sb.clean || 895 fsck_err(c, inode_unlinked_but_clean, 896 "filesystem marked clean, but inode %llu unlinked", 897 u.bi_inum))) { 898 bch2_trans_unlock(trans); 899 bch2_fs_lazy_rw(c); 900 901 ret = bch2_inode_rm_snapshot(trans, u.bi_inum, iter->pos.snapshot); 902 bch_err_msg(c, ret, "in fsck deleting inode"); 903 return ret; 904 } 905 906 if (u.bi_flags & BCH_INODE_i_size_dirty && 907 (!c->sb.clean || 908 fsck_err(c, inode_i_size_dirty_but_clean, 909 "filesystem marked clean, but inode %llu has i_size dirty", 910 u.bi_inum))) { 911 bch_verbose(c, "truncating inode %llu", u.bi_inum); 912 913 bch2_trans_unlock(trans); 914 bch2_fs_lazy_rw(c); 915 916 /* 917 * XXX: need to truncate partial blocks too here - or ideally 918 * just switch units to bytes and that issue goes away 919 */ 920 ret = bch2_btree_delete_range_trans(trans, BTREE_ID_extents, 921 SPOS(u.bi_inum, round_up(u.bi_size, block_bytes(c)) >> 9, 922 iter->pos.snapshot), 923 POS(u.bi_inum, U64_MAX), 924 0, NULL); 925 bch_err_msg(c, ret, "in fsck truncating inode"); 926 if (ret) 927 return ret; 928 929 /* 930 * We truncated without our normal sector accounting hook, just 931 * make sure we recalculate it: 932 */ 933 u.bi_flags |= BCH_INODE_i_sectors_dirty; 934 935 u.bi_flags &= ~BCH_INODE_i_size_dirty; 936 do_update = true; 937 } 938 939 if (u.bi_flags & BCH_INODE_i_sectors_dirty && 940 (!c->sb.clean || 941 fsck_err(c, inode_i_sectors_dirty_but_clean, 942 "filesystem marked clean, but inode %llu has i_sectors dirty", 943 u.bi_inum))) { 944 s64 sectors; 945 946 bch_verbose(c, "recounting sectors for inode %llu", 947 u.bi_inum); 948 949 sectors = bch2_count_inode_sectors(trans, u.bi_inum, iter->pos.snapshot); 950 if (sectors < 0) { 951 bch_err_msg(c, sectors, "in fsck recounting inode sectors"); 952 return sectors; 953 } 954 955 u.bi_sectors = sectors; 956 u.bi_flags &= ~BCH_INODE_i_sectors_dirty; 957 do_update = true; 958 } 959 960 if (u.bi_flags & BCH_INODE_backptr_untrusted) { 961 u.bi_dir = 0; 962 u.bi_dir_offset = 0; 963 u.bi_flags &= ~BCH_INODE_backptr_untrusted; 964 do_update = true; 965 } 966 967 if (do_update) { 968 ret = __write_inode(trans, &u, iter->pos.snapshot); 969 bch_err_msg(c, ret, "in fsck updating inode"); 970 if (ret) 971 return ret; 972 } 973 err: 974 fsck_err: 975 bch_err_fn(c, ret); 976 return ret; 977 } 978 979 noinline_for_stack 980 int bch2_check_inodes(struct bch_fs *c) 981 { 982 bool full = c->opts.fsck; 983 struct btree_trans *trans = bch2_trans_get(c); 984 struct btree_iter iter; 985 struct bch_inode_unpacked prev = { 0 }; 986 struct snapshots_seen s; 987 struct bkey_s_c k; 988 int ret; 989 990 snapshots_seen_init(&s); 991 992 ret = for_each_btree_key_commit(trans, iter, BTREE_ID_inodes, 993 POS_MIN, 994 BTREE_ITER_PREFETCH|BTREE_ITER_ALL_SNAPSHOTS, k, 995 NULL, NULL, BTREE_INSERT_LAZY_RW|BTREE_INSERT_NOFAIL, 996 check_inode(trans, &iter, k, &prev, &s, full)); 997 998 snapshots_seen_exit(&s); 999 bch2_trans_put(trans); 1000 bch_err_fn(c, ret); 1001 return ret; 1002 } 1003 1004 static struct bkey_s_c_dirent dirent_get_by_pos(struct btree_trans *trans, 1005 struct btree_iter *iter, 1006 struct bpos pos) 1007 { 1008 return bch2_bkey_get_iter_typed(trans, iter, BTREE_ID_dirents, pos, 0, dirent); 1009 } 1010 1011 static bool inode_points_to_dirent(struct bch_inode_unpacked *inode, 1012 struct bkey_s_c_dirent d) 1013 { 1014 return inode->bi_dir == d.k->p.inode && 1015 inode->bi_dir_offset == d.k->p.offset; 1016 } 1017 1018 static bool dirent_points_to_inode(struct bkey_s_c_dirent d, 1019 struct bch_inode_unpacked *inode) 1020 { 1021 return d.v->d_type == DT_SUBVOL 1022 ? le32_to_cpu(d.v->d_child_subvol) == inode->bi_subvol 1023 : le64_to_cpu(d.v->d_inum) == inode->bi_inum; 1024 } 1025 1026 static int inode_backpointer_exists(struct btree_trans *trans, 1027 struct bch_inode_unpacked *inode, 1028 u32 snapshot) 1029 { 1030 struct btree_iter iter; 1031 struct bkey_s_c_dirent d; 1032 int ret; 1033 1034 d = dirent_get_by_pos(trans, &iter, 1035 SPOS(inode->bi_dir, inode->bi_dir_offset, snapshot)); 1036 ret = bkey_err(d); 1037 if (ret) 1038 return bch2_err_matches(ret, ENOENT) ? 0 : ret; 1039 1040 ret = dirent_points_to_inode(d, inode); 1041 bch2_trans_iter_exit(trans, &iter); 1042 return ret; 1043 } 1044 1045 static int check_i_sectors(struct btree_trans *trans, struct inode_walker *w) 1046 { 1047 struct bch_fs *c = trans->c; 1048 struct inode_walker_entry *i; 1049 u32 restart_count = trans->restart_count; 1050 int ret = 0; 1051 s64 count2; 1052 1053 darray_for_each(w->inodes, i) { 1054 if (i->inode.bi_sectors == i->count) 1055 continue; 1056 1057 count2 = bch2_count_inode_sectors(trans, w->last_pos.inode, i->snapshot); 1058 1059 if (w->recalculate_sums) 1060 i->count = count2; 1061 1062 if (i->count != count2) { 1063 bch_err(c, "fsck counted i_sectors wrong for inode %llu:%u: got %llu should be %llu", 1064 w->last_pos.inode, i->snapshot, i->count, count2); 1065 return -BCH_ERR_internal_fsck_err; 1066 } 1067 1068 if (fsck_err_on(!(i->inode.bi_flags & BCH_INODE_i_sectors_dirty), 1069 c, inode_i_sectors_wrong, 1070 "inode %llu:%u has incorrect i_sectors: got %llu, should be %llu", 1071 w->last_pos.inode, i->snapshot, 1072 i->inode.bi_sectors, i->count)) { 1073 i->inode.bi_sectors = i->count; 1074 ret = fsck_write_inode(trans, &i->inode, i->snapshot); 1075 if (ret) 1076 break; 1077 } 1078 } 1079 fsck_err: 1080 bch_err_fn(c, ret); 1081 return ret ?: trans_was_restarted(trans, restart_count); 1082 } 1083 1084 struct extent_end { 1085 u32 snapshot; 1086 u64 offset; 1087 struct snapshots_seen seen; 1088 }; 1089 1090 struct extent_ends { 1091 struct bpos last_pos; 1092 DARRAY(struct extent_end) e; 1093 }; 1094 1095 static void extent_ends_reset(struct extent_ends *extent_ends) 1096 { 1097 struct extent_end *i; 1098 1099 darray_for_each(extent_ends->e, i) 1100 snapshots_seen_exit(&i->seen); 1101 1102 extent_ends->e.nr = 0; 1103 } 1104 1105 static void extent_ends_exit(struct extent_ends *extent_ends) 1106 { 1107 extent_ends_reset(extent_ends); 1108 darray_exit(&extent_ends->e); 1109 } 1110 1111 static void extent_ends_init(struct extent_ends *extent_ends) 1112 { 1113 memset(extent_ends, 0, sizeof(*extent_ends)); 1114 } 1115 1116 static int extent_ends_at(struct bch_fs *c, 1117 struct extent_ends *extent_ends, 1118 struct snapshots_seen *seen, 1119 struct bkey_s_c k) 1120 { 1121 struct extent_end *i, n = (struct extent_end) { 1122 .offset = k.k->p.offset, 1123 .snapshot = k.k->p.snapshot, 1124 .seen = *seen, 1125 }; 1126 1127 n.seen.ids.data = kmemdup(seen->ids.data, 1128 sizeof(seen->ids.data[0]) * seen->ids.size, 1129 GFP_KERNEL); 1130 if (!n.seen.ids.data) 1131 return -BCH_ERR_ENOMEM_fsck_extent_ends_at; 1132 1133 darray_for_each(extent_ends->e, i) { 1134 if (i->snapshot == k.k->p.snapshot) { 1135 snapshots_seen_exit(&i->seen); 1136 *i = n; 1137 return 0; 1138 } 1139 1140 if (i->snapshot >= k.k->p.snapshot) 1141 break; 1142 } 1143 1144 return darray_insert_item(&extent_ends->e, i - extent_ends->e.data, n); 1145 } 1146 1147 static int overlapping_extents_found(struct btree_trans *trans, 1148 enum btree_id btree, 1149 struct bpos pos1, struct snapshots_seen *pos1_seen, 1150 struct bkey pos2, 1151 bool *fixed, 1152 struct extent_end *extent_end) 1153 { 1154 struct bch_fs *c = trans->c; 1155 struct printbuf buf = PRINTBUF; 1156 struct btree_iter iter1, iter2 = { NULL }; 1157 struct bkey_s_c k1, k2; 1158 int ret; 1159 1160 BUG_ON(bkey_le(pos1, bkey_start_pos(&pos2))); 1161 1162 bch2_trans_iter_init(trans, &iter1, btree, pos1, 1163 BTREE_ITER_ALL_SNAPSHOTS| 1164 BTREE_ITER_NOT_EXTENTS); 1165 k1 = bch2_btree_iter_peek_upto(&iter1, POS(pos1.inode, U64_MAX)); 1166 ret = bkey_err(k1); 1167 if (ret) 1168 goto err; 1169 1170 prt_str(&buf, "\n "); 1171 bch2_bkey_val_to_text(&buf, c, k1); 1172 1173 if (!bpos_eq(pos1, k1.k->p)) { 1174 prt_str(&buf, "\n wanted\n "); 1175 bch2_bpos_to_text(&buf, pos1); 1176 prt_str(&buf, "\n "); 1177 bch2_bkey_to_text(&buf, &pos2); 1178 1179 bch_err(c, "%s: error finding first overlapping extent when repairing, got%s", 1180 __func__, buf.buf); 1181 ret = -BCH_ERR_internal_fsck_err; 1182 goto err; 1183 } 1184 1185 bch2_trans_copy_iter(&iter2, &iter1); 1186 1187 while (1) { 1188 bch2_btree_iter_advance(&iter2); 1189 1190 k2 = bch2_btree_iter_peek_upto(&iter2, POS(pos1.inode, U64_MAX)); 1191 ret = bkey_err(k2); 1192 if (ret) 1193 goto err; 1194 1195 if (bpos_ge(k2.k->p, pos2.p)) 1196 break; 1197 } 1198 1199 prt_str(&buf, "\n "); 1200 bch2_bkey_val_to_text(&buf, c, k2); 1201 1202 if (bpos_gt(k2.k->p, pos2.p) || 1203 pos2.size != k2.k->size) { 1204 bch_err(c, "%s: error finding seconding overlapping extent when repairing%s", 1205 __func__, buf.buf); 1206 ret = -BCH_ERR_internal_fsck_err; 1207 goto err; 1208 } 1209 1210 prt_printf(&buf, "\n overwriting %s extent", 1211 pos1.snapshot >= pos2.p.snapshot ? "first" : "second"); 1212 1213 if (fsck_err(c, extent_overlapping, 1214 "overlapping extents%s", buf.buf)) { 1215 struct btree_iter *old_iter = &iter1; 1216 struct disk_reservation res = { 0 }; 1217 1218 if (pos1.snapshot < pos2.p.snapshot) { 1219 old_iter = &iter2; 1220 swap(k1, k2); 1221 } 1222 1223 trans->extra_journal_res += bch2_bkey_sectors_compressed(k2); 1224 1225 ret = bch2_trans_update_extent_overwrite(trans, old_iter, 1226 BTREE_UPDATE_INTERNAL_SNAPSHOT_NODE, 1227 k1, k2) ?: 1228 bch2_trans_commit(trans, &res, NULL, 1229 BTREE_INSERT_LAZY_RW|BTREE_INSERT_NOFAIL); 1230 bch2_disk_reservation_put(c, &res); 1231 1232 if (ret) 1233 goto err; 1234 1235 *fixed = true; 1236 1237 if (pos1.snapshot == pos2.p.snapshot) { 1238 /* 1239 * We overwrote the first extent, and did the overwrite 1240 * in the same snapshot: 1241 */ 1242 extent_end->offset = bkey_start_offset(&pos2); 1243 } else if (pos1.snapshot > pos2.p.snapshot) { 1244 /* 1245 * We overwrote the first extent in pos2's snapshot: 1246 */ 1247 ret = snapshots_seen_add_inorder(c, pos1_seen, pos2.p.snapshot); 1248 } else { 1249 /* 1250 * We overwrote the second extent - restart 1251 * check_extent() from the top: 1252 */ 1253 ret = -BCH_ERR_transaction_restart_nested; 1254 } 1255 } 1256 fsck_err: 1257 err: 1258 bch2_trans_iter_exit(trans, &iter2); 1259 bch2_trans_iter_exit(trans, &iter1); 1260 printbuf_exit(&buf); 1261 return ret; 1262 } 1263 1264 static int check_overlapping_extents(struct btree_trans *trans, 1265 struct snapshots_seen *seen, 1266 struct extent_ends *extent_ends, 1267 struct bkey_s_c k, 1268 u32 equiv, 1269 struct btree_iter *iter, 1270 bool *fixed) 1271 { 1272 struct bch_fs *c = trans->c; 1273 struct extent_end *i; 1274 int ret = 0; 1275 1276 /* transaction restart, running again */ 1277 if (bpos_eq(extent_ends->last_pos, k.k->p)) 1278 return 0; 1279 1280 if (extent_ends->last_pos.inode != k.k->p.inode) 1281 extent_ends_reset(extent_ends); 1282 1283 darray_for_each(extent_ends->e, i) { 1284 if (i->offset <= bkey_start_offset(k.k)) 1285 continue; 1286 1287 if (!ref_visible2(c, 1288 k.k->p.snapshot, seen, 1289 i->snapshot, &i->seen)) 1290 continue; 1291 1292 ret = overlapping_extents_found(trans, iter->btree_id, 1293 SPOS(iter->pos.inode, 1294 i->offset, 1295 i->snapshot), 1296 &i->seen, 1297 *k.k, fixed, i); 1298 if (ret) 1299 goto err; 1300 } 1301 1302 ret = extent_ends_at(c, extent_ends, seen, k); 1303 if (ret) 1304 goto err; 1305 1306 extent_ends->last_pos = k.k->p; 1307 err: 1308 return ret; 1309 } 1310 1311 static int check_extent_overbig(struct btree_trans *trans, struct btree_iter *iter, 1312 struct bkey_s_c k) 1313 { 1314 struct bch_fs *c = trans->c; 1315 struct bkey_ptrs_c ptrs = bch2_bkey_ptrs_c(k); 1316 struct bch_extent_crc_unpacked crc; 1317 const union bch_extent_entry *i; 1318 unsigned encoded_extent_max_sectors = c->opts.encoded_extent_max >> 9; 1319 1320 bkey_for_each_crc(k.k, ptrs, crc, i) 1321 if (crc_is_encoded(crc) && 1322 crc.uncompressed_size > encoded_extent_max_sectors) { 1323 struct printbuf buf = PRINTBUF; 1324 1325 bch2_bkey_val_to_text(&buf, c, k); 1326 bch_err(c, "overbig encoded extent, please report this:\n %s", buf.buf); 1327 printbuf_exit(&buf); 1328 } 1329 1330 return 0; 1331 } 1332 1333 static int check_extent(struct btree_trans *trans, struct btree_iter *iter, 1334 struct bkey_s_c k, 1335 struct inode_walker *inode, 1336 struct snapshots_seen *s, 1337 struct extent_ends *extent_ends) 1338 { 1339 struct bch_fs *c = trans->c; 1340 struct inode_walker_entry *i; 1341 struct printbuf buf = PRINTBUF; 1342 struct bpos equiv = k.k->p; 1343 int ret = 0; 1344 1345 equiv.snapshot = bch2_snapshot_equiv(c, k.k->p.snapshot); 1346 1347 ret = check_key_has_snapshot(trans, iter, k); 1348 if (ret) { 1349 ret = ret < 0 ? ret : 0; 1350 goto out; 1351 } 1352 1353 if (inode->last_pos.inode != k.k->p.inode) { 1354 ret = check_i_sectors(trans, inode); 1355 if (ret) 1356 goto err; 1357 } 1358 1359 i = walk_inode(trans, inode, equiv, k.k->type == KEY_TYPE_whiteout); 1360 ret = PTR_ERR_OR_ZERO(i); 1361 if (ret) 1362 goto err; 1363 1364 ret = snapshots_seen_update(c, s, iter->btree_id, k.k->p); 1365 if (ret) 1366 goto err; 1367 1368 if (k.k->type != KEY_TYPE_whiteout) { 1369 if (fsck_err_on(!i, c, extent_in_missing_inode, 1370 "extent in missing inode:\n %s", 1371 (printbuf_reset(&buf), 1372 bch2_bkey_val_to_text(&buf, c, k), buf.buf))) 1373 goto delete; 1374 1375 if (fsck_err_on(i && 1376 !S_ISREG(i->inode.bi_mode) && 1377 !S_ISLNK(i->inode.bi_mode), 1378 c, extent_in_non_reg_inode, 1379 "extent in non regular inode mode %o:\n %s", 1380 i->inode.bi_mode, 1381 (printbuf_reset(&buf), 1382 bch2_bkey_val_to_text(&buf, c, k), buf.buf))) 1383 goto delete; 1384 1385 ret = check_overlapping_extents(trans, s, extent_ends, k, 1386 equiv.snapshot, iter, 1387 &inode->recalculate_sums); 1388 if (ret) 1389 goto err; 1390 } 1391 1392 /* 1393 * Check inodes in reverse order, from oldest snapshots to newest, 1394 * starting from the inode that matches this extent's snapshot. If we 1395 * didn't have one, iterate over all inodes: 1396 */ 1397 if (!i) 1398 i = inode->inodes.data + inode->inodes.nr - 1; 1399 1400 for (; 1401 inode->inodes.data && i >= inode->inodes.data; 1402 --i) { 1403 if (i->snapshot > equiv.snapshot || 1404 !key_visible_in_snapshot(c, s, i->snapshot, equiv.snapshot)) 1405 continue; 1406 1407 if (k.k->type != KEY_TYPE_whiteout) { 1408 if (fsck_err_on(!(i->inode.bi_flags & BCH_INODE_i_size_dirty) && 1409 k.k->p.offset > round_up(i->inode.bi_size, block_bytes(c)) >> 9 && 1410 !bkey_extent_is_reservation(k), 1411 c, extent_past_end_of_inode, 1412 "extent type past end of inode %llu:%u, i_size %llu\n %s", 1413 i->inode.bi_inum, i->snapshot, i->inode.bi_size, 1414 (bch2_bkey_val_to_text(&buf, c, k), buf.buf))) { 1415 struct btree_iter iter2; 1416 1417 bch2_trans_copy_iter(&iter2, iter); 1418 bch2_btree_iter_set_snapshot(&iter2, i->snapshot); 1419 ret = bch2_btree_iter_traverse(&iter2) ?: 1420 bch2_btree_delete_at(trans, &iter2, 1421 BTREE_UPDATE_INTERNAL_SNAPSHOT_NODE); 1422 bch2_trans_iter_exit(trans, &iter2); 1423 if (ret) 1424 goto err; 1425 1426 iter->k.type = KEY_TYPE_whiteout; 1427 } 1428 1429 if (bkey_extent_is_allocation(k.k)) 1430 i->count += k.k->size; 1431 } 1432 1433 i->seen_this_pos = true; 1434 } 1435 out: 1436 err: 1437 fsck_err: 1438 printbuf_exit(&buf); 1439 bch_err_fn(c, ret); 1440 return ret; 1441 delete: 1442 ret = bch2_btree_delete_at(trans, iter, BTREE_UPDATE_INTERNAL_SNAPSHOT_NODE); 1443 goto out; 1444 } 1445 1446 /* 1447 * Walk extents: verify that extents have a corresponding S_ISREG inode, and 1448 * that i_size an i_sectors are consistent 1449 */ 1450 int bch2_check_extents(struct bch_fs *c) 1451 { 1452 struct inode_walker w = inode_walker_init(); 1453 struct snapshots_seen s; 1454 struct btree_trans *trans = bch2_trans_get(c); 1455 struct btree_iter iter; 1456 struct bkey_s_c k; 1457 struct extent_ends extent_ends; 1458 struct disk_reservation res = { 0 }; 1459 int ret = 0; 1460 1461 snapshots_seen_init(&s); 1462 extent_ends_init(&extent_ends); 1463 1464 ret = for_each_btree_key_commit(trans, iter, BTREE_ID_extents, 1465 POS(BCACHEFS_ROOT_INO, 0), 1466 BTREE_ITER_PREFETCH|BTREE_ITER_ALL_SNAPSHOTS, k, 1467 &res, NULL, 1468 BTREE_INSERT_LAZY_RW|BTREE_INSERT_NOFAIL, ({ 1469 bch2_disk_reservation_put(c, &res); 1470 check_extent(trans, &iter, k, &w, &s, &extent_ends) ?: 1471 check_extent_overbig(trans, &iter, k); 1472 })) ?: 1473 check_i_sectors(trans, &w); 1474 1475 bch2_disk_reservation_put(c, &res); 1476 extent_ends_exit(&extent_ends); 1477 inode_walker_exit(&w); 1478 snapshots_seen_exit(&s); 1479 bch2_trans_put(trans); 1480 1481 bch_err_fn(c, ret); 1482 return ret; 1483 } 1484 1485 int bch2_check_indirect_extents(struct bch_fs *c) 1486 { 1487 struct btree_trans *trans = bch2_trans_get(c); 1488 struct btree_iter iter; 1489 struct bkey_s_c k; 1490 struct disk_reservation res = { 0 }; 1491 int ret = 0; 1492 1493 ret = for_each_btree_key_commit(trans, iter, BTREE_ID_reflink, 1494 POS_MIN, 1495 BTREE_ITER_PREFETCH, k, 1496 &res, NULL, 1497 BTREE_INSERT_LAZY_RW|BTREE_INSERT_NOFAIL, ({ 1498 bch2_disk_reservation_put(c, &res); 1499 check_extent_overbig(trans, &iter, k); 1500 })); 1501 1502 bch2_disk_reservation_put(c, &res); 1503 bch2_trans_put(trans); 1504 1505 bch_err_fn(c, ret); 1506 return ret; 1507 } 1508 1509 static int check_subdir_count(struct btree_trans *trans, struct inode_walker *w) 1510 { 1511 struct bch_fs *c = trans->c; 1512 struct inode_walker_entry *i; 1513 u32 restart_count = trans->restart_count; 1514 int ret = 0; 1515 s64 count2; 1516 1517 darray_for_each(w->inodes, i) { 1518 if (i->inode.bi_nlink == i->count) 1519 continue; 1520 1521 count2 = bch2_count_subdirs(trans, w->last_pos.inode, i->snapshot); 1522 if (count2 < 0) 1523 return count2; 1524 1525 if (i->count != count2) { 1526 bch_err(c, "fsck counted subdirectories wrong: got %llu should be %llu", 1527 i->count, count2); 1528 i->count = count2; 1529 if (i->inode.bi_nlink == i->count) 1530 continue; 1531 } 1532 1533 if (fsck_err_on(i->inode.bi_nlink != i->count, 1534 c, inode_dir_wrong_nlink, 1535 "directory %llu:%u with wrong i_nlink: got %u, should be %llu", 1536 w->last_pos.inode, i->snapshot, i->inode.bi_nlink, i->count)) { 1537 i->inode.bi_nlink = i->count; 1538 ret = fsck_write_inode(trans, &i->inode, i->snapshot); 1539 if (ret) 1540 break; 1541 } 1542 } 1543 fsck_err: 1544 bch_err_fn(c, ret); 1545 return ret ?: trans_was_restarted(trans, restart_count); 1546 } 1547 1548 static int check_dirent_target(struct btree_trans *trans, 1549 struct btree_iter *iter, 1550 struct bkey_s_c_dirent d, 1551 struct bch_inode_unpacked *target, 1552 u32 target_snapshot) 1553 { 1554 struct bch_fs *c = trans->c; 1555 struct bkey_i_dirent *n; 1556 bool backpointer_exists = true; 1557 struct printbuf buf = PRINTBUF; 1558 int ret = 0; 1559 1560 if (!target->bi_dir && 1561 !target->bi_dir_offset) { 1562 target->bi_dir = d.k->p.inode; 1563 target->bi_dir_offset = d.k->p.offset; 1564 1565 ret = __write_inode(trans, target, target_snapshot); 1566 if (ret) 1567 goto err; 1568 } 1569 1570 if (!inode_points_to_dirent(target, d)) { 1571 ret = inode_backpointer_exists(trans, target, d.k->p.snapshot); 1572 if (ret < 0) 1573 goto err; 1574 1575 backpointer_exists = ret; 1576 ret = 0; 1577 1578 if (fsck_err_on(S_ISDIR(target->bi_mode) && backpointer_exists, 1579 c, inode_dir_multiple_links, 1580 "directory %llu with multiple links", 1581 target->bi_inum)) { 1582 ret = __remove_dirent(trans, d.k->p); 1583 goto out; 1584 } 1585 1586 if (fsck_err_on(backpointer_exists && !target->bi_nlink, 1587 c, inode_multiple_links_but_nlink_0, 1588 "inode %llu type %s has multiple links but i_nlink 0", 1589 target->bi_inum, bch2_d_types[d.v->d_type])) { 1590 target->bi_nlink++; 1591 target->bi_flags &= ~BCH_INODE_unlinked; 1592 1593 ret = __write_inode(trans, target, target_snapshot); 1594 if (ret) 1595 goto err; 1596 } 1597 1598 if (fsck_err_on(!backpointer_exists, 1599 c, inode_wrong_backpointer, 1600 "inode %llu:%u has wrong backpointer:\n" 1601 "got %llu:%llu\n" 1602 "should be %llu:%llu", 1603 target->bi_inum, target_snapshot, 1604 target->bi_dir, 1605 target->bi_dir_offset, 1606 d.k->p.inode, 1607 d.k->p.offset)) { 1608 target->bi_dir = d.k->p.inode; 1609 target->bi_dir_offset = d.k->p.offset; 1610 1611 ret = __write_inode(trans, target, target_snapshot); 1612 if (ret) 1613 goto err; 1614 } 1615 } 1616 1617 if (fsck_err_on(d.v->d_type != inode_d_type(target), 1618 c, dirent_d_type_wrong, 1619 "incorrect d_type: got %s, should be %s:\n%s", 1620 bch2_d_type_str(d.v->d_type), 1621 bch2_d_type_str(inode_d_type(target)), 1622 (printbuf_reset(&buf), 1623 bch2_bkey_val_to_text(&buf, c, d.s_c), buf.buf))) { 1624 n = bch2_trans_kmalloc(trans, bkey_bytes(d.k)); 1625 ret = PTR_ERR_OR_ZERO(n); 1626 if (ret) 1627 goto err; 1628 1629 bkey_reassemble(&n->k_i, d.s_c); 1630 n->v.d_type = inode_d_type(target); 1631 1632 ret = bch2_trans_update(trans, iter, &n->k_i, 0); 1633 if (ret) 1634 goto err; 1635 1636 d = dirent_i_to_s_c(n); 1637 } 1638 1639 if (d.v->d_type == DT_SUBVOL && 1640 target->bi_parent_subvol != le32_to_cpu(d.v->d_parent_subvol) && 1641 (c->sb.version < bcachefs_metadata_version_subvol_dirent || 1642 fsck_err(c, dirent_d_parent_subvol_wrong, 1643 "dirent has wrong d_parent_subvol field: got %u, should be %u", 1644 le32_to_cpu(d.v->d_parent_subvol), 1645 target->bi_parent_subvol))) { 1646 n = bch2_trans_kmalloc(trans, bkey_bytes(d.k)); 1647 ret = PTR_ERR_OR_ZERO(n); 1648 if (ret) 1649 goto err; 1650 1651 bkey_reassemble(&n->k_i, d.s_c); 1652 n->v.d_parent_subvol = cpu_to_le32(target->bi_parent_subvol); 1653 1654 ret = bch2_trans_update(trans, iter, &n->k_i, 0); 1655 if (ret) 1656 goto err; 1657 1658 d = dirent_i_to_s_c(n); 1659 } 1660 out: 1661 err: 1662 fsck_err: 1663 printbuf_exit(&buf); 1664 bch_err_fn(c, ret); 1665 return ret; 1666 } 1667 1668 static int check_dirent(struct btree_trans *trans, struct btree_iter *iter, 1669 struct bkey_s_c k, 1670 struct bch_hash_info *hash_info, 1671 struct inode_walker *dir, 1672 struct inode_walker *target, 1673 struct snapshots_seen *s) 1674 { 1675 struct bch_fs *c = trans->c; 1676 struct bkey_s_c_dirent d; 1677 struct inode_walker_entry *i; 1678 struct printbuf buf = PRINTBUF; 1679 struct bpos equiv; 1680 int ret = 0; 1681 1682 ret = check_key_has_snapshot(trans, iter, k); 1683 if (ret) { 1684 ret = ret < 0 ? ret : 0; 1685 goto out; 1686 } 1687 1688 equiv = k.k->p; 1689 equiv.snapshot = bch2_snapshot_equiv(c, k.k->p.snapshot); 1690 1691 ret = snapshots_seen_update(c, s, iter->btree_id, k.k->p); 1692 if (ret) 1693 goto err; 1694 1695 if (k.k->type == KEY_TYPE_whiteout) 1696 goto out; 1697 1698 if (dir->last_pos.inode != k.k->p.inode) { 1699 ret = check_subdir_count(trans, dir); 1700 if (ret) 1701 goto err; 1702 } 1703 1704 BUG_ON(!iter->path->should_be_locked); 1705 1706 i = walk_inode(trans, dir, equiv, k.k->type == KEY_TYPE_whiteout); 1707 ret = PTR_ERR_OR_ZERO(i); 1708 if (ret < 0) 1709 goto err; 1710 1711 if (dir->first_this_inode && dir->inodes.nr) 1712 *hash_info = bch2_hash_info_init(c, &dir->inodes.data[0].inode); 1713 dir->first_this_inode = false; 1714 1715 if (fsck_err_on(!i, c, dirent_in_missing_dir_inode, 1716 "dirent in nonexisting directory:\n%s", 1717 (printbuf_reset(&buf), 1718 bch2_bkey_val_to_text(&buf, c, k), buf.buf))) { 1719 ret = bch2_btree_delete_at(trans, iter, 1720 BTREE_UPDATE_INTERNAL_SNAPSHOT_NODE); 1721 goto out; 1722 } 1723 1724 if (!i) 1725 goto out; 1726 1727 if (fsck_err_on(!S_ISDIR(i->inode.bi_mode), 1728 c, dirent_in_non_dir_inode, 1729 "dirent in non directory inode type %s:\n%s", 1730 bch2_d_type_str(inode_d_type(&i->inode)), 1731 (printbuf_reset(&buf), 1732 bch2_bkey_val_to_text(&buf, c, k), buf.buf))) { 1733 ret = bch2_btree_delete_at(trans, iter, 0); 1734 goto out; 1735 } 1736 1737 ret = hash_check_key(trans, bch2_dirent_hash_desc, hash_info, iter, k); 1738 if (ret < 0) 1739 goto err; 1740 if (ret) { 1741 /* dirent has been deleted */ 1742 ret = 0; 1743 goto out; 1744 } 1745 1746 if (k.k->type != KEY_TYPE_dirent) 1747 goto out; 1748 1749 d = bkey_s_c_to_dirent(k); 1750 1751 if (d.v->d_type == DT_SUBVOL) { 1752 struct bch_inode_unpacked subvol_root; 1753 u32 target_subvol = le32_to_cpu(d.v->d_child_subvol); 1754 u32 target_snapshot; 1755 u64 target_inum; 1756 1757 ret = __subvol_lookup(trans, target_subvol, 1758 &target_snapshot, &target_inum); 1759 if (ret && !bch2_err_matches(ret, ENOENT)) 1760 goto err; 1761 1762 if (fsck_err_on(ret, c, dirent_to_missing_subvol, 1763 "dirent points to missing subvolume %u", 1764 le32_to_cpu(d.v->d_child_subvol))) { 1765 ret = __remove_dirent(trans, d.k->p); 1766 goto err; 1767 } 1768 1769 ret = __lookup_inode(trans, target_inum, 1770 &subvol_root, &target_snapshot); 1771 if (ret && !bch2_err_matches(ret, ENOENT)) 1772 goto err; 1773 1774 if (fsck_err_on(ret, c, subvol_to_missing_root, 1775 "subvolume %u points to missing subvolume root %llu", 1776 target_subvol, 1777 target_inum)) { 1778 bch_err(c, "repair not implemented yet"); 1779 ret = -EINVAL; 1780 goto err; 1781 } 1782 1783 if (fsck_err_on(subvol_root.bi_subvol != target_subvol, 1784 c, subvol_root_wrong_bi_subvol, 1785 "subvol root %llu has wrong bi_subvol field: got %u, should be %u", 1786 target_inum, 1787 subvol_root.bi_subvol, target_subvol)) { 1788 subvol_root.bi_subvol = target_subvol; 1789 ret = __write_inode(trans, &subvol_root, target_snapshot); 1790 if (ret) 1791 goto err; 1792 } 1793 1794 ret = check_dirent_target(trans, iter, d, &subvol_root, 1795 target_snapshot); 1796 if (ret) 1797 goto err; 1798 } else { 1799 ret = __get_visible_inodes(trans, target, s, le64_to_cpu(d.v->d_inum)); 1800 if (ret) 1801 goto err; 1802 1803 if (fsck_err_on(!target->inodes.nr, 1804 c, dirent_to_missing_inode, 1805 "dirent points to missing inode: (equiv %u)\n%s", 1806 equiv.snapshot, 1807 (printbuf_reset(&buf), 1808 bch2_bkey_val_to_text(&buf, c, k), 1809 buf.buf))) { 1810 ret = __remove_dirent(trans, d.k->p); 1811 if (ret) 1812 goto err; 1813 } 1814 1815 darray_for_each(target->inodes, i) { 1816 ret = check_dirent_target(trans, iter, d, 1817 &i->inode, i->snapshot); 1818 if (ret) 1819 goto err; 1820 } 1821 } 1822 1823 if (d.v->d_type == DT_DIR) 1824 for_each_visible_inode(c, s, dir, equiv.snapshot, i) 1825 i->count++; 1826 1827 out: 1828 err: 1829 fsck_err: 1830 printbuf_exit(&buf); 1831 bch_err_fn(c, ret); 1832 return ret; 1833 } 1834 1835 /* 1836 * Walk dirents: verify that they all have a corresponding S_ISDIR inode, 1837 * validate d_type 1838 */ 1839 int bch2_check_dirents(struct bch_fs *c) 1840 { 1841 struct inode_walker dir = inode_walker_init(); 1842 struct inode_walker target = inode_walker_init(); 1843 struct snapshots_seen s; 1844 struct bch_hash_info hash_info; 1845 struct btree_trans *trans = bch2_trans_get(c); 1846 struct btree_iter iter; 1847 struct bkey_s_c k; 1848 int ret = 0; 1849 1850 snapshots_seen_init(&s); 1851 1852 ret = for_each_btree_key_commit(trans, iter, BTREE_ID_dirents, 1853 POS(BCACHEFS_ROOT_INO, 0), 1854 BTREE_ITER_PREFETCH|BTREE_ITER_ALL_SNAPSHOTS, 1855 k, 1856 NULL, NULL, 1857 BTREE_INSERT_LAZY_RW|BTREE_INSERT_NOFAIL, 1858 check_dirent(trans, &iter, k, &hash_info, &dir, &target, &s)); 1859 1860 bch2_trans_put(trans); 1861 snapshots_seen_exit(&s); 1862 inode_walker_exit(&dir); 1863 inode_walker_exit(&target); 1864 bch_err_fn(c, ret); 1865 return ret; 1866 } 1867 1868 static int check_xattr(struct btree_trans *trans, struct btree_iter *iter, 1869 struct bkey_s_c k, 1870 struct bch_hash_info *hash_info, 1871 struct inode_walker *inode) 1872 { 1873 struct bch_fs *c = trans->c; 1874 struct inode_walker_entry *i; 1875 int ret; 1876 1877 ret = check_key_has_snapshot(trans, iter, k); 1878 if (ret) 1879 return ret; 1880 1881 i = walk_inode(trans, inode, k.k->p, k.k->type == KEY_TYPE_whiteout); 1882 ret = PTR_ERR_OR_ZERO(i); 1883 if (ret) 1884 return ret; 1885 1886 if (inode->first_this_inode && inode->inodes.nr) 1887 *hash_info = bch2_hash_info_init(c, &inode->inodes.data[0].inode); 1888 inode->first_this_inode = false; 1889 1890 if (fsck_err_on(!i, c, xattr_in_missing_inode, 1891 "xattr for missing inode %llu", 1892 k.k->p.inode)) 1893 return bch2_btree_delete_at(trans, iter, 0); 1894 1895 if (!i) 1896 return 0; 1897 1898 ret = hash_check_key(trans, bch2_xattr_hash_desc, hash_info, iter, k); 1899 fsck_err: 1900 bch_err_fn(c, ret); 1901 return ret; 1902 } 1903 1904 /* 1905 * Walk xattrs: verify that they all have a corresponding inode 1906 */ 1907 int bch2_check_xattrs(struct bch_fs *c) 1908 { 1909 struct inode_walker inode = inode_walker_init(); 1910 struct bch_hash_info hash_info; 1911 struct btree_iter iter; 1912 struct bkey_s_c k; 1913 int ret = 0; 1914 1915 ret = bch2_trans_run(c, 1916 for_each_btree_key_commit(trans, iter, BTREE_ID_xattrs, 1917 POS(BCACHEFS_ROOT_INO, 0), 1918 BTREE_ITER_PREFETCH|BTREE_ITER_ALL_SNAPSHOTS, 1919 k, 1920 NULL, NULL, 1921 BTREE_INSERT_LAZY_RW|BTREE_INSERT_NOFAIL, 1922 check_xattr(trans, &iter, k, &hash_info, &inode))); 1923 bch_err_fn(c, ret); 1924 return ret; 1925 } 1926 1927 static int check_root_trans(struct btree_trans *trans) 1928 { 1929 struct bch_fs *c = trans->c; 1930 struct bch_inode_unpacked root_inode; 1931 u32 snapshot; 1932 u64 inum; 1933 int ret; 1934 1935 ret = __subvol_lookup(trans, BCACHEFS_ROOT_SUBVOL, &snapshot, &inum); 1936 if (ret && !bch2_err_matches(ret, ENOENT)) 1937 return ret; 1938 1939 if (mustfix_fsck_err_on(ret, c, root_subvol_missing, 1940 "root subvol missing")) { 1941 struct bkey_i_subvolume root_subvol; 1942 1943 snapshot = U32_MAX; 1944 inum = BCACHEFS_ROOT_INO; 1945 1946 bkey_subvolume_init(&root_subvol.k_i); 1947 root_subvol.k.p.offset = BCACHEFS_ROOT_SUBVOL; 1948 root_subvol.v.flags = 0; 1949 root_subvol.v.snapshot = cpu_to_le32(snapshot); 1950 root_subvol.v.inode = cpu_to_le64(inum); 1951 ret = commit_do(trans, NULL, NULL, 1952 BTREE_INSERT_NOFAIL| 1953 BTREE_INSERT_LAZY_RW, 1954 bch2_btree_insert_trans(trans, BTREE_ID_subvolumes, 1955 &root_subvol.k_i, 0)); 1956 bch_err_msg(c, ret, "writing root subvol"); 1957 if (ret) 1958 goto err; 1959 1960 } 1961 1962 ret = __lookup_inode(trans, BCACHEFS_ROOT_INO, &root_inode, &snapshot); 1963 if (ret && !bch2_err_matches(ret, ENOENT)) 1964 return ret; 1965 1966 if (mustfix_fsck_err_on(ret, c, root_dir_missing, 1967 "root directory missing") || 1968 mustfix_fsck_err_on(!S_ISDIR(root_inode.bi_mode), 1969 c, root_inode_not_dir, 1970 "root inode not a directory")) { 1971 bch2_inode_init(c, &root_inode, 0, 0, S_IFDIR|0755, 1972 0, NULL); 1973 root_inode.bi_inum = inum; 1974 1975 ret = __write_inode(trans, &root_inode, snapshot); 1976 bch_err_msg(c, ret, "writing root inode"); 1977 } 1978 err: 1979 fsck_err: 1980 return ret; 1981 } 1982 1983 /* Get root directory, create if it doesn't exist: */ 1984 int bch2_check_root(struct bch_fs *c) 1985 { 1986 int ret; 1987 1988 ret = bch2_trans_do(c, NULL, NULL, 1989 BTREE_INSERT_NOFAIL| 1990 BTREE_INSERT_LAZY_RW, 1991 check_root_trans(trans)); 1992 bch_err_fn(c, ret); 1993 return ret; 1994 } 1995 1996 struct pathbuf_entry { 1997 u64 inum; 1998 u32 snapshot; 1999 }; 2000 2001 typedef DARRAY(struct pathbuf_entry) pathbuf; 2002 2003 static bool path_is_dup(pathbuf *p, u64 inum, u32 snapshot) 2004 { 2005 struct pathbuf_entry *i; 2006 2007 darray_for_each(*p, i) 2008 if (i->inum == inum && 2009 i->snapshot == snapshot) 2010 return true; 2011 2012 return false; 2013 } 2014 2015 static int path_down(struct bch_fs *c, pathbuf *p, 2016 u64 inum, u32 snapshot) 2017 { 2018 int ret = darray_push(p, ((struct pathbuf_entry) { 2019 .inum = inum, 2020 .snapshot = snapshot, 2021 })); 2022 2023 if (ret) 2024 bch_err(c, "fsck: error allocating memory for pathbuf, size %zu", 2025 p->size); 2026 return ret; 2027 } 2028 2029 /* 2030 * Check that a given inode is reachable from the root: 2031 * 2032 * XXX: we should also be verifying that inodes are in the right subvolumes 2033 */ 2034 static int check_path(struct btree_trans *trans, 2035 pathbuf *p, 2036 struct bch_inode_unpacked *inode, 2037 u32 snapshot) 2038 { 2039 struct bch_fs *c = trans->c; 2040 int ret = 0; 2041 2042 snapshot = bch2_snapshot_equiv(c, snapshot); 2043 p->nr = 0; 2044 2045 while (!(inode->bi_inum == BCACHEFS_ROOT_INO && 2046 inode->bi_subvol == BCACHEFS_ROOT_SUBVOL)) { 2047 struct btree_iter dirent_iter; 2048 struct bkey_s_c_dirent d; 2049 u32 parent_snapshot = snapshot; 2050 2051 if (inode->bi_subvol) { 2052 u64 inum; 2053 2054 ret = subvol_lookup(trans, inode->bi_parent_subvol, 2055 &parent_snapshot, &inum); 2056 if (ret) 2057 break; 2058 } 2059 2060 ret = lockrestart_do(trans, 2061 PTR_ERR_OR_ZERO((d = dirent_get_by_pos(trans, &dirent_iter, 2062 SPOS(inode->bi_dir, inode->bi_dir_offset, 2063 parent_snapshot))).k)); 2064 if (ret && !bch2_err_matches(ret, ENOENT)) 2065 break; 2066 2067 if (!ret && !dirent_points_to_inode(d, inode)) { 2068 bch2_trans_iter_exit(trans, &dirent_iter); 2069 ret = -BCH_ERR_ENOENT_dirent_doesnt_match_inode; 2070 } 2071 2072 if (bch2_err_matches(ret, ENOENT)) { 2073 if (fsck_err(c, inode_unreachable, 2074 "unreachable inode %llu:%u, type %s nlink %u backptr %llu:%llu", 2075 inode->bi_inum, snapshot, 2076 bch2_d_type_str(inode_d_type(inode)), 2077 inode->bi_nlink, 2078 inode->bi_dir, 2079 inode->bi_dir_offset)) 2080 ret = reattach_inode(trans, inode, snapshot); 2081 break; 2082 } 2083 2084 bch2_trans_iter_exit(trans, &dirent_iter); 2085 2086 if (!S_ISDIR(inode->bi_mode)) 2087 break; 2088 2089 ret = path_down(c, p, inode->bi_inum, snapshot); 2090 if (ret) { 2091 bch_err(c, "memory allocation failure"); 2092 return ret; 2093 } 2094 2095 snapshot = parent_snapshot; 2096 2097 ret = lookup_inode(trans, inode->bi_dir, inode, &snapshot); 2098 if (ret) { 2099 /* Should have been caught in dirents pass */ 2100 bch_err(c, "error looking up parent directory: %i", ret); 2101 break; 2102 } 2103 2104 if (path_is_dup(p, inode->bi_inum, snapshot)) { 2105 struct pathbuf_entry *i; 2106 2107 /* XXX print path */ 2108 bch_err(c, "directory structure loop"); 2109 2110 darray_for_each(*p, i) 2111 pr_err("%llu:%u", i->inum, i->snapshot); 2112 pr_err("%llu:%u", inode->bi_inum, snapshot); 2113 2114 if (!fsck_err(c, dir_loop, 2115 "directory structure loop")) 2116 return 0; 2117 2118 ret = commit_do(trans, NULL, NULL, 2119 BTREE_INSERT_NOFAIL| 2120 BTREE_INSERT_LAZY_RW, 2121 remove_backpointer(trans, inode)); 2122 if (ret) { 2123 bch_err(c, "error removing dirent: %i", ret); 2124 break; 2125 } 2126 2127 ret = reattach_inode(trans, inode, snapshot); 2128 } 2129 } 2130 fsck_err: 2131 bch_err_fn(c, ret); 2132 return ret; 2133 } 2134 2135 /* 2136 * Check for unreachable inodes, as well as loops in the directory structure: 2137 * After bch2_check_dirents(), if an inode backpointer doesn't exist that means it's 2138 * unreachable: 2139 */ 2140 int bch2_check_directory_structure(struct bch_fs *c) 2141 { 2142 struct btree_trans *trans = bch2_trans_get(c); 2143 struct btree_iter iter; 2144 struct bkey_s_c k; 2145 struct bch_inode_unpacked u; 2146 pathbuf path = { 0, }; 2147 int ret; 2148 2149 for_each_btree_key(trans, iter, BTREE_ID_inodes, POS_MIN, 2150 BTREE_ITER_INTENT| 2151 BTREE_ITER_PREFETCH| 2152 BTREE_ITER_ALL_SNAPSHOTS, k, ret) { 2153 if (!bkey_is_inode(k.k)) 2154 continue; 2155 2156 ret = bch2_inode_unpack(k, &u); 2157 if (ret) { 2158 /* Should have been caught earlier in fsck: */ 2159 bch_err(c, "error unpacking inode %llu: %i", k.k->p.offset, ret); 2160 break; 2161 } 2162 2163 if (u.bi_flags & BCH_INODE_unlinked) 2164 continue; 2165 2166 ret = check_path(trans, &path, &u, iter.pos.snapshot); 2167 if (ret) 2168 break; 2169 } 2170 bch2_trans_iter_exit(trans, &iter); 2171 bch2_trans_put(trans); 2172 darray_exit(&path); 2173 bch_err_fn(c, ret); 2174 return ret; 2175 } 2176 2177 struct nlink_table { 2178 size_t nr; 2179 size_t size; 2180 2181 struct nlink { 2182 u64 inum; 2183 u32 snapshot; 2184 u32 count; 2185 } *d; 2186 }; 2187 2188 static int add_nlink(struct bch_fs *c, struct nlink_table *t, 2189 u64 inum, u32 snapshot) 2190 { 2191 if (t->nr == t->size) { 2192 size_t new_size = max_t(size_t, 128UL, t->size * 2); 2193 void *d = kvmalloc_array(new_size, sizeof(t->d[0]), GFP_KERNEL); 2194 2195 if (!d) { 2196 bch_err(c, "fsck: error allocating memory for nlink_table, size %zu", 2197 new_size); 2198 return -BCH_ERR_ENOMEM_fsck_add_nlink; 2199 } 2200 2201 if (t->d) 2202 memcpy(d, t->d, t->size * sizeof(t->d[0])); 2203 kvfree(t->d); 2204 2205 t->d = d; 2206 t->size = new_size; 2207 } 2208 2209 2210 t->d[t->nr++] = (struct nlink) { 2211 .inum = inum, 2212 .snapshot = snapshot, 2213 }; 2214 2215 return 0; 2216 } 2217 2218 static int nlink_cmp(const void *_l, const void *_r) 2219 { 2220 const struct nlink *l = _l; 2221 const struct nlink *r = _r; 2222 2223 return cmp_int(l->inum, r->inum) ?: cmp_int(l->snapshot, r->snapshot); 2224 } 2225 2226 static void inc_link(struct bch_fs *c, struct snapshots_seen *s, 2227 struct nlink_table *links, 2228 u64 range_start, u64 range_end, u64 inum, u32 snapshot) 2229 { 2230 struct nlink *link, key = { 2231 .inum = inum, .snapshot = U32_MAX, 2232 }; 2233 2234 if (inum < range_start || inum >= range_end) 2235 return; 2236 2237 link = __inline_bsearch(&key, links->d, links->nr, 2238 sizeof(links->d[0]), nlink_cmp); 2239 if (!link) 2240 return; 2241 2242 while (link > links->d && link[0].inum == link[-1].inum) 2243 --link; 2244 2245 for (; link < links->d + links->nr && link->inum == inum; link++) 2246 if (ref_visible(c, s, snapshot, link->snapshot)) { 2247 link->count++; 2248 if (link->snapshot >= snapshot) 2249 break; 2250 } 2251 } 2252 2253 noinline_for_stack 2254 static int check_nlinks_find_hardlinks(struct bch_fs *c, 2255 struct nlink_table *t, 2256 u64 start, u64 *end) 2257 { 2258 struct btree_trans *trans = bch2_trans_get(c); 2259 struct btree_iter iter; 2260 struct bkey_s_c k; 2261 struct bch_inode_unpacked u; 2262 int ret = 0; 2263 2264 for_each_btree_key(trans, iter, BTREE_ID_inodes, 2265 POS(0, start), 2266 BTREE_ITER_INTENT| 2267 BTREE_ITER_PREFETCH| 2268 BTREE_ITER_ALL_SNAPSHOTS, k, ret) { 2269 if (!bkey_is_inode(k.k)) 2270 continue; 2271 2272 /* Should never fail, checked by bch2_inode_invalid: */ 2273 BUG_ON(bch2_inode_unpack(k, &u)); 2274 2275 /* 2276 * Backpointer and directory structure checks are sufficient for 2277 * directories, since they can't have hardlinks: 2278 */ 2279 if (S_ISDIR(u.bi_mode)) 2280 continue; 2281 2282 if (!u.bi_nlink) 2283 continue; 2284 2285 ret = add_nlink(c, t, k.k->p.offset, k.k->p.snapshot); 2286 if (ret) { 2287 *end = k.k->p.offset; 2288 ret = 0; 2289 break; 2290 } 2291 2292 } 2293 bch2_trans_iter_exit(trans, &iter); 2294 bch2_trans_put(trans); 2295 2296 if (ret) 2297 bch_err(c, "error in fsck: btree error %i while walking inodes", ret); 2298 2299 return ret; 2300 } 2301 2302 noinline_for_stack 2303 static int check_nlinks_walk_dirents(struct bch_fs *c, struct nlink_table *links, 2304 u64 range_start, u64 range_end) 2305 { 2306 struct btree_trans *trans = bch2_trans_get(c); 2307 struct snapshots_seen s; 2308 struct btree_iter iter; 2309 struct bkey_s_c k; 2310 struct bkey_s_c_dirent d; 2311 int ret; 2312 2313 snapshots_seen_init(&s); 2314 2315 for_each_btree_key(trans, iter, BTREE_ID_dirents, POS_MIN, 2316 BTREE_ITER_INTENT| 2317 BTREE_ITER_PREFETCH| 2318 BTREE_ITER_ALL_SNAPSHOTS, k, ret) { 2319 ret = snapshots_seen_update(c, &s, iter.btree_id, k.k->p); 2320 if (ret) 2321 break; 2322 2323 switch (k.k->type) { 2324 case KEY_TYPE_dirent: 2325 d = bkey_s_c_to_dirent(k); 2326 2327 if (d.v->d_type != DT_DIR && 2328 d.v->d_type != DT_SUBVOL) 2329 inc_link(c, &s, links, range_start, range_end, 2330 le64_to_cpu(d.v->d_inum), 2331 bch2_snapshot_equiv(c, d.k->p.snapshot)); 2332 break; 2333 } 2334 } 2335 bch2_trans_iter_exit(trans, &iter); 2336 2337 if (ret) 2338 bch_err(c, "error in fsck: btree error %i while walking dirents", ret); 2339 2340 bch2_trans_put(trans); 2341 snapshots_seen_exit(&s); 2342 return ret; 2343 } 2344 2345 static int check_nlinks_update_inode(struct btree_trans *trans, struct btree_iter *iter, 2346 struct bkey_s_c k, 2347 struct nlink_table *links, 2348 size_t *idx, u64 range_end) 2349 { 2350 struct bch_fs *c = trans->c; 2351 struct bch_inode_unpacked u; 2352 struct nlink *link = &links->d[*idx]; 2353 int ret = 0; 2354 2355 if (k.k->p.offset >= range_end) 2356 return 1; 2357 2358 if (!bkey_is_inode(k.k)) 2359 return 0; 2360 2361 BUG_ON(bch2_inode_unpack(k, &u)); 2362 2363 if (S_ISDIR(u.bi_mode)) 2364 return 0; 2365 2366 if (!u.bi_nlink) 2367 return 0; 2368 2369 while ((cmp_int(link->inum, k.k->p.offset) ?: 2370 cmp_int(link->snapshot, k.k->p.snapshot)) < 0) { 2371 BUG_ON(*idx == links->nr); 2372 link = &links->d[++*idx]; 2373 } 2374 2375 if (fsck_err_on(bch2_inode_nlink_get(&u) != link->count, 2376 c, inode_wrong_nlink, 2377 "inode %llu type %s has wrong i_nlink (%u, should be %u)", 2378 u.bi_inum, bch2_d_types[mode_to_type(u.bi_mode)], 2379 bch2_inode_nlink_get(&u), link->count)) { 2380 bch2_inode_nlink_set(&u, link->count); 2381 ret = __write_inode(trans, &u, k.k->p.snapshot); 2382 } 2383 fsck_err: 2384 return ret; 2385 } 2386 2387 noinline_for_stack 2388 static int check_nlinks_update_hardlinks(struct bch_fs *c, 2389 struct nlink_table *links, 2390 u64 range_start, u64 range_end) 2391 { 2392 struct btree_iter iter; 2393 struct bkey_s_c k; 2394 size_t idx = 0; 2395 int ret = 0; 2396 2397 ret = bch2_trans_run(c, 2398 for_each_btree_key_commit(trans, iter, BTREE_ID_inodes, 2399 POS(0, range_start), 2400 BTREE_ITER_INTENT|BTREE_ITER_PREFETCH|BTREE_ITER_ALL_SNAPSHOTS, k, 2401 NULL, NULL, BTREE_INSERT_LAZY_RW|BTREE_INSERT_NOFAIL, 2402 check_nlinks_update_inode(trans, &iter, k, links, &idx, range_end))); 2403 if (ret < 0) { 2404 bch_err(c, "error in fsck: btree error %i while walking inodes", ret); 2405 return ret; 2406 } 2407 2408 return 0; 2409 } 2410 2411 int bch2_check_nlinks(struct bch_fs *c) 2412 { 2413 struct nlink_table links = { 0 }; 2414 u64 this_iter_range_start, next_iter_range_start = 0; 2415 int ret = 0; 2416 2417 do { 2418 this_iter_range_start = next_iter_range_start; 2419 next_iter_range_start = U64_MAX; 2420 2421 ret = check_nlinks_find_hardlinks(c, &links, 2422 this_iter_range_start, 2423 &next_iter_range_start); 2424 2425 ret = check_nlinks_walk_dirents(c, &links, 2426 this_iter_range_start, 2427 next_iter_range_start); 2428 if (ret) 2429 break; 2430 2431 ret = check_nlinks_update_hardlinks(c, &links, 2432 this_iter_range_start, 2433 next_iter_range_start); 2434 if (ret) 2435 break; 2436 2437 links.nr = 0; 2438 } while (next_iter_range_start != U64_MAX); 2439 2440 kvfree(links.d); 2441 bch_err_fn(c, ret); 2442 return ret; 2443 } 2444 2445 static int fix_reflink_p_key(struct btree_trans *trans, struct btree_iter *iter, 2446 struct bkey_s_c k) 2447 { 2448 struct bkey_s_c_reflink_p p; 2449 struct bkey_i_reflink_p *u; 2450 int ret; 2451 2452 if (k.k->type != KEY_TYPE_reflink_p) 2453 return 0; 2454 2455 p = bkey_s_c_to_reflink_p(k); 2456 2457 if (!p.v->front_pad && !p.v->back_pad) 2458 return 0; 2459 2460 u = bch2_trans_kmalloc(trans, sizeof(*u)); 2461 ret = PTR_ERR_OR_ZERO(u); 2462 if (ret) 2463 return ret; 2464 2465 bkey_reassemble(&u->k_i, k); 2466 u->v.front_pad = 0; 2467 u->v.back_pad = 0; 2468 2469 return bch2_trans_update(trans, iter, &u->k_i, BTREE_TRIGGER_NORUN); 2470 } 2471 2472 int bch2_fix_reflink_p(struct bch_fs *c) 2473 { 2474 struct btree_iter iter; 2475 struct bkey_s_c k; 2476 int ret; 2477 2478 if (c->sb.version >= bcachefs_metadata_version_reflink_p_fix) 2479 return 0; 2480 2481 ret = bch2_trans_run(c, 2482 for_each_btree_key_commit(trans, iter, 2483 BTREE_ID_extents, POS_MIN, 2484 BTREE_ITER_INTENT|BTREE_ITER_PREFETCH| 2485 BTREE_ITER_ALL_SNAPSHOTS, k, 2486 NULL, NULL, BTREE_INSERT_NOFAIL|BTREE_INSERT_LAZY_RW, 2487 fix_reflink_p_key(trans, &iter, k))); 2488 bch_err_fn(c, ret); 2489 return ret; 2490 } 2491