1 // SPDX-License-Identifier: GPL-2.0
5 #include "btree_update.h"
15 #include <linux/bsearch.h>
16 #include <linux/dcache.h> /* struct qstr */
18 #define QSTR(n) { { { .len = strlen(n) } }, .name = n }
20 static s64 bch2_count_inode_sectors(struct btree_trans *trans, u64 inum)
22 struct btree_iter *iter;
27 for_each_btree_key(trans, iter, BTREE_ID_extents,
28 POS(inum, 0), 0, k, ret) {
29 if (k.k->p.inode != inum)
32 if (bkey_extent_is_allocation(k.k))
36 bch2_trans_iter_free(trans, iter);
38 return ret ?: sectors;
41 static int __lookup_inode(struct btree_trans *trans, u64 inode_nr,
42 struct bch_inode_unpacked *inode,
45 struct btree_iter *iter;
49 iter = bch2_trans_get_iter(trans, BTREE_ID_inodes,
51 k = bch2_btree_iter_peek_slot(iter);
57 *snapshot = iter->pos.snapshot;
58 ret = k.k->type == KEY_TYPE_inode
59 ? bch2_inode_unpack(bkey_s_c_to_inode(k), inode)
62 bch2_trans_iter_free(trans, iter);
66 static int lookup_inode(struct btree_trans *trans, u64 inode_nr,
67 struct bch_inode_unpacked *inode,
70 return lockrestart_do(trans, __lookup_inode(trans, inode_nr, inode, snapshot));
73 static int __write_inode(struct btree_trans *trans,
74 struct bch_inode_unpacked *inode,
77 struct btree_iter *inode_iter =
78 bch2_trans_get_iter(trans, BTREE_ID_inodes,
79 SPOS(0, inode->bi_inum, snapshot),
81 int ret = bch2_inode_write(trans, inode_iter, inode);
82 bch2_trans_iter_put(trans, inode_iter);
86 static int write_inode(struct btree_trans *trans,
87 struct bch_inode_unpacked *inode,
90 int ret = __bch2_trans_do(trans, NULL, NULL,
93 __write_inode(trans, inode, snapshot));
95 bch_err(trans->c, "error in fsck: error %i updating inode", ret);
99 static int __remove_dirent(struct btree_trans *trans, struct bpos pos)
101 struct bch_fs *c = trans->c;
102 struct btree_iter *iter;
103 struct bch_inode_unpacked dir_inode;
104 struct bch_hash_info dir_hash_info;
107 ret = lookup_inode(trans, pos.inode, &dir_inode, NULL);
111 dir_hash_info = bch2_hash_info_init(c, &dir_inode);
113 iter = bch2_trans_get_iter(trans, BTREE_ID_dirents, pos, BTREE_ITER_INTENT);
115 ret = bch2_hash_delete_at(trans, bch2_dirent_hash_desc,
116 &dir_hash_info, iter);
117 bch2_trans_iter_put(trans, iter);
121 static int remove_dirent(struct btree_trans *trans, struct bpos pos)
123 int ret = __bch2_trans_do(trans, NULL, NULL,
125 BTREE_INSERT_LAZY_RW,
126 __remove_dirent(trans, pos));
128 bch_err(trans->c, "remove_dirent: err %i deleting dirent", ret);
132 /* Get lost+found, create if it doesn't exist: */
133 static int lookup_lostfound(struct btree_trans *trans,
134 struct bch_inode_unpacked *lostfound)
136 struct bch_fs *c = trans->c;
137 struct bch_inode_unpacked root;
138 struct bch_hash_info root_hash_info;
139 struct qstr lostfound_str = QSTR("lost+found");
144 ret = lookup_inode(trans, BCACHEFS_ROOT_INO, &root, &snapshot);
145 if (ret && ret != -ENOENT)
148 root_hash_info = bch2_hash_info_init(c, &root);
149 inum = bch2_dirent_lookup(c, BCACHEFS_ROOT_INO, &root_hash_info,
152 bch_notice(c, "creating lost+found");
153 goto create_lostfound;
156 ret = lookup_inode(trans, inum, lostfound, &snapshot);
157 if (ret && ret != -ENOENT) {
159 * The check_dirents pass has already run, dangling dirents
160 * shouldn't exist here:
162 bch_err(c, "error looking up lost+found: %i", ret);
166 if (ret == -ENOENT) {
168 bch2_inode_init_early(c, lostfound);
170 ret = __bch2_trans_do(trans, NULL, NULL,
172 BTREE_INSERT_LAZY_RW,
173 bch2_create_trans(trans,
174 BCACHEFS_ROOT_INO, &root,
177 0, 0, S_IFDIR|0700, 0, NULL, NULL));
179 bch_err(c, "error creating lost+found: %i", ret);
185 static int reattach_inode(struct btree_trans *trans,
186 struct bch_inode_unpacked *inode)
188 struct bch_hash_info dir_hash;
189 struct bch_inode_unpacked lostfound;
195 ret = lookup_lostfound(trans, &lostfound);
199 if (S_ISDIR(inode->bi_mode)) {
200 lostfound.bi_nlink++;
202 ret = write_inode(trans, &lostfound, U32_MAX);
207 dir_hash = bch2_hash_info_init(trans->c, &lostfound);
209 snprintf(name_buf, sizeof(name_buf), "%llu", inode->bi_inum);
210 name = (struct qstr) QSTR(name_buf);
212 ret = __bch2_trans_do(trans, NULL, NULL, BTREE_INSERT_LAZY_RW,
213 bch2_dirent_create(trans, lostfound.bi_inum, &dir_hash,
214 mode_to_type(inode->bi_mode),
215 &name, inode->bi_inum, &dir_offset,
216 BCH_HASH_SET_MUST_CREATE));
218 bch_err(trans->c, "error %i reattaching inode %llu",
219 ret, inode->bi_inum);
223 inode->bi_dir = lostfound.bi_inum;
224 inode->bi_dir_offset = dir_offset;
226 return write_inode(trans, inode, U32_MAX);
229 static int remove_backpointer(struct btree_trans *trans,
230 struct bch_inode_unpacked *inode)
232 struct btree_iter *iter;
236 iter = bch2_trans_get_iter(trans, BTREE_ID_dirents,
237 POS(inode->bi_dir, inode->bi_dir_offset), 0);
238 k = bch2_btree_iter_peek_slot(iter);
242 if (k.k->type != KEY_TYPE_dirent) {
247 ret = remove_dirent(trans, k.k->p);
249 bch2_trans_iter_put(trans, iter);
253 struct inode_walker {
254 bool first_this_inode;
258 struct bch_inode_unpacked inode;
261 static struct inode_walker inode_walker_init(void)
263 return (struct inode_walker) {
269 static int walk_inode(struct btree_trans *trans,
270 struct inode_walker *w, u64 inum)
272 if (inum != w->cur_inum) {
273 int ret = lookup_inode(trans, inum, &w->inode, &w->snapshot);
275 if (ret && ret != -ENOENT)
278 w->have_inode = !ret;
280 w->first_this_inode = true;
282 w->first_this_inode = false;
288 static int hash_redo_key(struct btree_trans *trans,
289 const struct bch_hash_desc desc,
290 struct bch_hash_info *hash_info,
291 struct btree_iter *k_iter, struct bkey_s_c k)
293 struct bkey_i *delete;
296 delete = bch2_trans_kmalloc(trans, sizeof(*delete));
298 return PTR_ERR(delete);
300 tmp = bch2_trans_kmalloc(trans, bkey_bytes(k.k));
304 bkey_reassemble(tmp, k);
306 bkey_init(&delete->k);
307 delete->k.p = k_iter->pos;
308 bch2_trans_update(trans, k_iter, delete, 0);
310 return bch2_hash_set(trans, desc, hash_info, k_iter->pos.inode, tmp, 0);
313 static int fsck_hash_delete_at(struct btree_trans *trans,
314 const struct bch_hash_desc desc,
315 struct bch_hash_info *info,
316 struct btree_iter *iter)
320 ret = bch2_hash_delete_at(trans, desc, info, iter) ?:
321 bch2_trans_commit(trans, NULL, NULL,
323 BTREE_INSERT_LAZY_RW);
325 ret = bch2_btree_iter_traverse(iter);
333 static int hash_check_key(struct btree_trans *trans,
334 const struct bch_hash_desc desc,
335 struct bch_hash_info *hash_info,
336 struct btree_iter *k_iter, struct bkey_s_c hash_k)
338 struct bch_fs *c = trans->c;
339 struct btree_iter *iter = NULL;
345 if (hash_k.k->type != desc.key_type)
348 hash = desc.hash_bkey(hash_info, hash_k);
350 if (likely(hash == hash_k.k->p.offset))
353 if (hash_k.k->p.offset < hash)
356 for_each_btree_key(trans, iter, desc.btree_id, POS(hash_k.k->p.inode, hash),
357 BTREE_ITER_SLOTS, k, ret) {
358 if (!bkey_cmp(k.k->p, hash_k.k->p))
361 if (fsck_err_on(k.k->type == desc.key_type &&
362 !desc.cmp_bkey(k, hash_k), c,
363 "duplicate hash table keys:\n%s",
364 (bch2_bkey_val_to_text(&PBUF(buf), c,
366 ret = fsck_hash_delete_at(trans, desc, hash_info, k_iter);
373 if (bkey_deleted(k.k)) {
374 bch2_trans_iter_free(trans, iter);
379 bch2_trans_iter_free(trans, iter);
382 if (fsck_err(c, "hash table key at wrong offset: btree %u inode %llu offset %llu, "
383 "hashed to %llu\n%s",
384 desc.btree_id, hash_k.k->p.inode, hash_k.k->p.offset, hash,
385 (bch2_bkey_val_to_text(&PBUF(buf), c, hash_k), buf)) == FSCK_ERR_IGNORE)
388 ret = __bch2_trans_do(trans, NULL, NULL,
389 BTREE_INSERT_NOFAIL|BTREE_INSERT_LAZY_RW,
390 hash_redo_key(trans, desc, hash_info, k_iter, hash_k));
392 bch_err(c, "hash_redo_key err %i", ret);
400 static int check_inode(struct btree_trans *trans,
401 struct btree_iter *iter,
402 struct bkey_s_c_inode inode)
404 struct bch_fs *c = trans->c;
405 struct bch_inode_unpacked u;
406 bool do_update = false;
409 ret = bch2_inode_unpack(inode, &u);
411 if (bch2_fs_inconsistent_on(ret, c,
412 "error unpacking inode %llu in fsck",
416 if (u.bi_flags & BCH_INODE_UNLINKED &&
418 fsck_err(c, "filesystem marked clean, but inode %llu unlinked",
420 bch_verbose(c, "deleting inode %llu", u.bi_inum);
422 bch2_trans_unlock(trans);
425 ret = bch2_inode_rm(c, u.bi_inum, false);
427 bch_err(c, "error in fsck: error %i while deleting inode", ret);
431 if (u.bi_flags & BCH_INODE_I_SIZE_DIRTY &&
433 fsck_err(c, "filesystem marked clean, but inode %llu has i_size dirty",
435 bch_verbose(c, "truncating inode %llu", u.bi_inum);
437 bch2_trans_unlock(trans);
441 * XXX: need to truncate partial blocks too here - or ideally
442 * just switch units to bytes and that issue goes away
444 ret = bch2_btree_delete_range_trans(trans, BTREE_ID_extents,
445 POS(u.bi_inum, round_up(u.bi_size, block_bytes(c))),
446 POS(u.bi_inum, U64_MAX),
449 bch_err(c, "error in fsck: error %i truncating inode", ret);
454 * We truncated without our normal sector accounting hook, just
455 * make sure we recalculate it:
457 u.bi_flags |= BCH_INODE_I_SECTORS_DIRTY;
459 u.bi_flags &= ~BCH_INODE_I_SIZE_DIRTY;
463 if (u.bi_flags & BCH_INODE_I_SECTORS_DIRTY &&
465 fsck_err(c, "filesystem marked clean, but inode %llu has i_sectors dirty",
469 bch_verbose(c, "recounting sectors for inode %llu",
472 sectors = bch2_count_inode_sectors(trans, u.bi_inum);
474 bch_err(c, "error in fsck: error %i recounting inode sectors",
479 u.bi_sectors = sectors;
480 u.bi_flags &= ~BCH_INODE_I_SECTORS_DIRTY;
484 if (u.bi_flags & BCH_INODE_BACKPTR_UNTRUSTED) {
487 u.bi_flags &= ~BCH_INODE_BACKPTR_UNTRUSTED;
492 ret = __bch2_trans_do(trans, NULL, NULL,
494 BTREE_INSERT_LAZY_RW,
495 bch2_inode_write(trans, iter, &u));
497 bch_err(c, "error in fsck: error %i "
498 "updating inode", ret);
505 static int check_inodes(struct bch_fs *c, bool full)
507 struct btree_trans trans;
508 struct btree_iter *iter;
510 struct bkey_s_c_inode inode;
513 bch2_trans_init(&trans, c, BTREE_ITER_MAX, 0);
515 for_each_btree_key(&trans, iter, BTREE_ID_inodes, POS_MIN, 0, k, ret) {
516 if (k.k->type != KEY_TYPE_inode)
519 inode = bkey_s_c_to_inode(k);
522 (inode.v->bi_flags & (BCH_INODE_I_SIZE_DIRTY|
523 BCH_INODE_I_SECTORS_DIRTY|
524 BCH_INODE_UNLINKED))) {
525 ret = check_inode(&trans, iter, inode);
530 bch2_trans_iter_put(&trans, iter);
532 BUG_ON(ret == -EINTR);
534 return bch2_trans_exit(&trans) ?: ret;
537 static int fix_overlapping_extent(struct btree_trans *trans,
538 struct bkey_s_c k, struct bpos cut_at)
540 struct btree_iter *iter;
544 u = bch2_trans_kmalloc(trans, bkey_bytes(k.k));
545 ret = PTR_ERR_OR_ZERO(u);
549 bkey_reassemble(u, k);
550 bch2_cut_front(cut_at, u);
554 * We don't want to go through the extent_handle_overwrites path:
556 * XXX: this is going to screw up disk accounting, extent triggers
557 * assume things about extent overwrites - we should be running the
558 * triggers manually here
560 iter = bch2_trans_get_iter(trans, BTREE_ID_extents, u->k.p,
561 BTREE_ITER_INTENT|BTREE_ITER_NOT_EXTENTS);
563 BUG_ON(iter->flags & BTREE_ITER_IS_EXTENTS);
564 bch2_trans_update(trans, iter, u, BTREE_TRIGGER_NORUN);
565 bch2_trans_iter_put(trans, iter);
567 return bch2_trans_commit(trans, NULL, NULL,
569 BTREE_INSERT_LAZY_RW);
572 static int inode_backpointer_exists(struct btree_trans *trans,
573 struct bch_inode_unpacked *inode)
575 struct btree_iter *iter;
579 iter = bch2_trans_get_iter(trans, BTREE_ID_dirents,
580 POS(inode->bi_dir, inode->bi_dir_offset), 0);
581 k = bch2_btree_iter_peek_slot(iter);
585 if (k.k->type != KEY_TYPE_dirent)
588 ret = le64_to_cpu(bkey_s_c_to_dirent(k).v->d_inum) == inode->bi_inum;
590 bch2_trans_iter_free(trans, iter);
594 static bool inode_backpointer_matches(struct bkey_s_c_dirent d,
595 struct bch_inode_unpacked *inode)
597 return d.k->p.inode == inode->bi_dir &&
598 d.k->p.offset == inode->bi_dir_offset;
602 * Walk extents: verify that extents have a corresponding S_ISREG inode, and
603 * that i_size an i_sectors are consistent
606 static int check_extents(struct bch_fs *c)
608 struct inode_walker w = inode_walker_init();
609 struct btree_trans trans;
610 struct btree_iter *iter;
612 struct bkey_buf prev;
616 bch2_bkey_buf_init(&prev);
617 prev.k->k = KEY(0, 0, 0);
618 bch2_trans_init(&trans, c, BTREE_ITER_MAX, 0);
620 bch_verbose(c, "checking extents");
622 iter = bch2_trans_get_iter(&trans, BTREE_ID_extents,
623 POS(BCACHEFS_ROOT_INO, 0),
626 while ((k = bch2_btree_iter_peek(iter)).k &&
627 !(ret = bkey_err(k))) {
629 w.cur_inum != k.k->p.inode &&
630 !(w.inode.bi_flags & BCH_INODE_I_SECTORS_DIRTY) &&
631 fsck_err_on(w.inode.bi_sectors != i_sectors, c,
632 "inode %llu has incorrect i_sectors: got %llu, should be %llu",
634 w.inode.bi_sectors, i_sectors)) {
635 w.inode.bi_sectors = i_sectors;
637 ret = write_inode(&trans, &w.inode, w.snapshot);
642 if (bkey_cmp(prev.k->k.p, bkey_start_pos(k.k)) > 0) {
646 bch2_bkey_val_to_text(&PBUF(buf1), c, bkey_i_to_s_c(prev.k));
647 bch2_bkey_val_to_text(&PBUF(buf2), c, k);
649 if (fsck_err(c, "overlapping extents:\n%s\n%s", buf1, buf2))
650 return fix_overlapping_extent(&trans, k, prev.k->k.p) ?: -EINTR;
653 ret = walk_inode(&trans, &w, k.k->p.inode);
657 if (w.first_this_inode)
660 if (fsck_err_on(!w.have_inode, c,
661 "extent type %u for missing inode %llu",
662 k.k->type, k.k->p.inode) ||
663 fsck_err_on(w.have_inode &&
664 !S_ISREG(w.inode.bi_mode) && !S_ISLNK(w.inode.bi_mode), c,
665 "extent type %u for non regular file, inode %llu mode %o",
666 k.k->type, k.k->p.inode, w.inode.bi_mode)) {
668 return bch2_btree_delete_range_trans(&trans, BTREE_ID_extents,
669 POS(k.k->p.inode, 0),
670 POS(k.k->p.inode, U64_MAX),
674 if (fsck_err_on(w.have_inode &&
675 !(w.inode.bi_flags & BCH_INODE_I_SIZE_DIRTY) &&
676 k.k->type != KEY_TYPE_reservation &&
677 k.k->p.offset > round_up(w.inode.bi_size, block_bytes(c)) >> 9, c,
678 "extent type %u offset %llu past end of inode %llu, i_size %llu",
679 k.k->type, k.k->p.offset, k.k->p.inode, w.inode.bi_size)) {
681 return bch2_btree_delete_range_trans(&trans, BTREE_ID_extents,
682 POS(k.k->p.inode, round_up(w.inode.bi_size, block_bytes(c))),
683 POS(k.k->p.inode, U64_MAX),
687 if (bkey_extent_is_allocation(k.k))
688 i_sectors += k.k->size;
689 bch2_bkey_buf_reassemble(&prev, c, k);
691 bch2_btree_iter_advance(iter);
696 bch2_trans_iter_put(&trans, iter);
697 bch2_bkey_buf_exit(&prev, c);
698 return bch2_trans_exit(&trans) ?: ret;
702 * Walk dirents: verify that they all have a corresponding S_ISDIR inode,
706 static int check_dirents(struct bch_fs *c)
708 struct inode_walker w = inode_walker_init();
709 struct bch_hash_info hash_info;
710 struct btree_trans trans;
711 struct btree_iter *iter;
714 unsigned nr_subdirs = 0;
717 bch_verbose(c, "checking dirents");
719 bch2_trans_init(&trans, c, BTREE_ITER_MAX, 0);
721 iter = bch2_trans_get_iter(&trans, BTREE_ID_dirents,
722 POS(BCACHEFS_ROOT_INO, 0), 0);
724 while ((k = bch2_btree_iter_peek(iter)).k &&
725 !(ret = bkey_err(k))) {
726 struct bkey_s_c_dirent d;
727 struct bch_inode_unpacked target;
730 bool backpointer_exists = true;
734 w.cur_inum != k.k->p.inode &&
735 fsck_err_on(w.inode.bi_nlink != nr_subdirs, c,
736 "directory %llu with wrong i_nlink: got %u, should be %u",
737 w.inode.bi_inum, w.inode.bi_nlink, nr_subdirs)) {
738 w.inode.bi_nlink = nr_subdirs;
739 ret = write_inode(&trans, &w.inode, w.snapshot);
744 ret = walk_inode(&trans, &w, k.k->p.inode);
748 if (w.first_this_inode)
751 if (fsck_err_on(!w.have_inode, c,
752 "dirent in nonexisting directory:\n%s",
753 (bch2_bkey_val_to_text(&PBUF(buf), c,
755 fsck_err_on(!S_ISDIR(w.inode.bi_mode), c,
756 "dirent in non directory inode type %u:\n%s",
757 mode_to_type(w.inode.bi_mode),
758 (bch2_bkey_val_to_text(&PBUF(buf), c,
760 ret = lockrestart_do(&trans,
761 bch2_btree_delete_at(&trans, iter, 0));
770 if (w.first_this_inode)
771 hash_info = bch2_hash_info_init(c, &w.inode);
773 ret = hash_check_key(&trans, bch2_dirent_hash_desc,
774 &hash_info, iter, k);
782 if (k.k->type != KEY_TYPE_dirent)
785 d = bkey_s_c_to_dirent(k);
786 d_inum = le64_to_cpu(d.v->d_inum);
788 ret = lookup_inode(&trans, d_inum, &target, &target_snapshot);
789 if (ret && ret != -ENOENT)
795 if (fsck_err_on(!have_target, c,
796 "dirent points to missing inode:\n%s",
797 (bch2_bkey_val_to_text(&PBUF(buf), c,
799 ret = remove_dirent(&trans, d.k->p);
808 if (!target.bi_dir &&
809 !target.bi_dir_offset) {
810 target.bi_dir = k.k->p.inode;
811 target.bi_dir_offset = k.k->p.offset;
813 ret = write_inode(&trans, &target, target_snapshot);
818 if (!inode_backpointer_matches(d, &target)) {
819 ret = inode_backpointer_exists(&trans, &target);
823 backpointer_exists = ret;
826 if (fsck_err_on(S_ISDIR(target.bi_mode) &&
827 backpointer_exists, c,
828 "directory %llu with multiple links",
830 ret = remove_dirent(&trans, d.k->p);
836 if (fsck_err_on(backpointer_exists &&
838 "inode %llu has multiple links but i_nlink 0",
841 target.bi_flags &= ~BCH_INODE_UNLINKED;
843 ret = write_inode(&trans, &target, target_snapshot);
848 if (fsck_err_on(!backpointer_exists, c,
849 "inode %llu has wrong backpointer:\n"
851 "should be %llu:%llu",
854 target.bi_dir_offset,
857 target.bi_dir = k.k->p.inode;
858 target.bi_dir_offset = k.k->p.offset;
860 ret = write_inode(&trans, &target, target_snapshot);
866 if (fsck_err_on(d.v->d_type != mode_to_type(target.bi_mode), c,
867 "incorrect d_type: should be %u:\n%s",
868 mode_to_type(target.bi_mode),
869 (bch2_bkey_val_to_text(&PBUF(buf), c,
871 struct bkey_i_dirent *n;
873 n = kmalloc(bkey_bytes(d.k), GFP_KERNEL);
879 bkey_reassemble(&n->k_i, d.s_c);
880 n->v.d_type = mode_to_type(target.bi_mode);
882 ret = __bch2_trans_do(&trans, NULL, NULL,
884 BTREE_INSERT_LAZY_RW,
885 (bch2_trans_update(&trans, iter, &n->k_i, 0), 0));
892 nr_subdirs += d.v->d_type == DT_DIR;
894 bch2_btree_iter_advance(iter);
901 bch2_trans_iter_put(&trans, iter);
902 return bch2_trans_exit(&trans) ?: ret;
906 * Walk xattrs: verify that they all have a corresponding inode
909 static int check_xattrs(struct bch_fs *c)
911 struct inode_walker w = inode_walker_init();
912 struct bch_hash_info hash_info;
913 struct btree_trans trans;
914 struct btree_iter *iter;
918 bch_verbose(c, "checking xattrs");
920 bch2_trans_init(&trans, c, BTREE_ITER_MAX, 0);
922 iter = bch2_trans_get_iter(&trans, BTREE_ID_xattrs,
923 POS(BCACHEFS_ROOT_INO, 0), 0);
925 while ((k = bch2_btree_iter_peek(iter)).k &&
926 !(ret = bkey_err(k))) {
927 ret = walk_inode(&trans, &w, k.k->p.inode);
931 if (fsck_err_on(!w.have_inode, c,
932 "xattr for missing inode %llu",
934 ret = bch2_btree_delete_at(&trans, iter, 0);
940 if (w.first_this_inode && w.have_inode)
941 hash_info = bch2_hash_info_init(c, &w.inode);
943 ret = hash_check_key(&trans, bch2_xattr_hash_desc,
944 &hash_info, iter, k);
948 bch2_btree_iter_advance(iter);
954 bch2_trans_iter_put(&trans, iter);
955 return bch2_trans_exit(&trans) ?: ret;
958 /* Get root directory, create if it doesn't exist: */
959 static int check_root(struct bch_fs *c, struct bch_inode_unpacked *root_inode)
961 struct bkey_inode_buf packed;
965 bch_verbose(c, "checking root directory");
967 ret = bch2_trans_do(c, NULL, NULL, 0,
968 lookup_inode(&trans, BCACHEFS_ROOT_INO, root_inode, &snapshot));
969 if (ret && ret != -ENOENT)
972 if (fsck_err_on(ret, c, "root directory missing"))
975 if (fsck_err_on(!S_ISDIR(root_inode->bi_mode), c,
976 "root inode not a directory"))
983 bch2_inode_init(c, root_inode, 0, 0, S_IFDIR|0755,
985 root_inode->bi_inum = BCACHEFS_ROOT_INO;
987 bch2_inode_pack(c, &packed, root_inode);
989 return bch2_btree_insert(c, BTREE_ID_inodes, &packed.inode.k_i,
992 BTREE_INSERT_LAZY_RW);
999 struct pathbuf_entry {
1004 static int path_down(struct pathbuf *p, u64 inum)
1006 if (p->nr == p->size) {
1007 size_t new_size = max_t(size_t, 256UL, p->size * 2);
1008 void *n = krealloc(p->entries,
1009 new_size * sizeof(p->entries[0]),
1019 p->entries[p->nr++] = (struct pathbuf_entry) {
1025 static int check_path(struct btree_trans *trans,
1027 struct bch_inode_unpacked *inode)
1029 struct bch_fs *c = trans->c;
1036 while (inode->bi_inum != BCACHEFS_ROOT_INO) {
1037 ret = lockrestart_do(trans,
1038 inode_backpointer_exists(trans, inode));
1043 if (fsck_err(c, "unreachable inode %llu, type %u nlink %u backptr %llu:%llu",
1045 mode_to_type(inode->bi_mode),
1048 inode->bi_dir_offset))
1049 ret = reattach_inode(trans, inode);
1054 if (!S_ISDIR(inode->bi_mode))
1057 ret = path_down(p, inode->bi_inum);
1059 bch_err(c, "memory allocation failure");
1063 for (i = 0; i < p->nr; i++) {
1064 if (inode->bi_dir != p->entries[i].inum)
1067 /* XXX print path */
1068 if (!fsck_err(c, "directory structure loop"))
1071 ret = lockrestart_do(trans,
1072 remove_backpointer(trans, inode));
1074 bch_err(c, "error removing dirent: %i", ret);
1078 ret = reattach_inode(trans, inode);
1082 ret = lookup_inode(trans, inode->bi_dir, inode, &snapshot);
1084 /* Should have been caught in dirents pass */
1085 bch_err(c, "error looking up parent directory: %i", ret);
1091 bch_err(c, "%s: err %i", __func__, ret);
1096 * Check for unreachable inodes, as well as loops in the directory structure:
1097 * After check_dirents(), if an inode backpointer doesn't exist that means it's
1100 static int check_directory_structure(struct bch_fs *c)
1102 struct btree_trans trans;
1103 struct btree_iter *iter;
1105 struct bch_inode_unpacked u;
1106 struct pathbuf path = { 0, 0, NULL };
1109 bch2_trans_init(&trans, c, BTREE_ITER_MAX, 0);
1111 for_each_btree_key(&trans, iter, BTREE_ID_inodes, POS_MIN, 0, k, ret) {
1112 if (k.k->type != KEY_TYPE_inode)
1115 ret = bch2_inode_unpack(bkey_s_c_to_inode(k), &u);
1117 /* Should have been caught earlier in fsck: */
1118 bch_err(c, "error unpacking inode %llu: %i", k.k->p.offset, ret);
1122 ret = check_path(&trans, &path, &u);
1126 bch2_trans_iter_put(&trans, iter);
1128 BUG_ON(ret == -EINTR);
1130 kfree(path.entries);
1132 return bch2_trans_exit(&trans) ?: ret;
1135 struct nlink_table {
1146 static int add_nlink(struct nlink_table *t, u64 inum, u32 snapshot)
1148 if (t->nr == t->size) {
1149 size_t new_size = max_t(size_t, 128UL, t->size * 2);
1150 void *d = kvmalloc(new_size * sizeof(t->d[0]), GFP_KERNEL);
1155 memcpy(d, t->d, t->size * sizeof(t->d[0]));
1163 t->d[t->nr++] = (struct nlink) {
1165 .snapshot = snapshot,
1171 static int nlink_cmp(const void *_l, const void *_r)
1173 const struct nlink *l = _l;
1174 const struct nlink *r = _r;
1176 return cmp_int(l->inum, r->inum) ?: cmp_int(l->snapshot, r->snapshot);
1179 static void inc_link(struct bch_fs *c, struct nlink_table *links,
1180 u64 range_start, u64 range_end, u64 inum)
1182 struct nlink *link, key = {
1183 .inum = inum, .snapshot = U32_MAX,
1186 if (inum < range_start || inum >= range_end)
1189 link = __inline_bsearch(&key, links->d, links->nr,
1190 sizeof(links->d[0]), nlink_cmp);
1196 static int check_nlinks_find_hardlinks(struct bch_fs *c,
1197 struct nlink_table *t,
1198 u64 start, u64 *end)
1200 struct btree_trans trans;
1201 struct btree_iter *iter;
1203 struct bkey_s_c_inode inode;
1204 struct bch_inode_unpacked u;
1207 bch2_trans_init(&trans, c, BTREE_ITER_MAX, 0);
1209 for_each_btree_key(&trans, iter, BTREE_ID_inodes,
1210 POS(0, start), 0, k, ret) {
1211 if (k.k->type != KEY_TYPE_inode)
1214 inode = bkey_s_c_to_inode(k);
1217 * Backpointer and directory structure checks are sufficient for
1218 * directories, since they can't have hardlinks:
1220 if (S_ISDIR(le16_to_cpu(inode.v->bi_mode)))
1223 /* Should never fail, checked by bch2_inode_invalid: */
1224 BUG_ON(bch2_inode_unpack(inode, &u));
1229 ret = add_nlink(t, k.k->p.offset, k.k->p.snapshot);
1231 *end = k.k->p.offset;
1237 bch2_trans_iter_put(&trans, iter);
1238 bch2_trans_exit(&trans);
1241 bch_err(c, "error in fsck: btree error %i while walking inodes", ret);
1247 static int check_nlinks_walk_dirents(struct bch_fs *c, struct nlink_table *links,
1248 u64 range_start, u64 range_end)
1250 struct btree_trans trans;
1251 struct btree_iter *iter;
1253 struct bkey_s_c_dirent d;
1256 bch2_trans_init(&trans, c, BTREE_ITER_MAX, 0);
1258 for_each_btree_key(&trans, iter, BTREE_ID_dirents, POS_MIN, 0, k, ret) {
1259 switch (k.k->type) {
1260 case KEY_TYPE_dirent:
1261 d = bkey_s_c_to_dirent(k);
1263 if (d.v->d_type != DT_DIR)
1264 inc_link(c, links, range_start, range_end,
1265 le64_to_cpu(d.v->d_inum));
1269 bch2_trans_cond_resched(&trans);
1271 bch2_trans_iter_put(&trans, iter);
1273 ret = bch2_trans_exit(&trans) ?: ret;
1275 bch_err(c, "error in fsck: btree error %i while walking dirents", ret);
1281 static int check_nlinks_update_hardlinks(struct bch_fs *c,
1282 struct nlink_table *links,
1283 u64 range_start, u64 range_end)
1285 struct btree_trans trans;
1286 struct btree_iter *iter;
1288 struct bkey_s_c_inode inode;
1289 struct bch_inode_unpacked u;
1290 struct nlink *link = links->d;
1293 bch2_trans_init(&trans, c, BTREE_ITER_MAX, 0);
1295 for_each_btree_key(&trans, iter, BTREE_ID_inodes,
1296 POS(0, range_start), 0, k, ret) {
1297 if (k.k->p.offset >= range_end)
1300 if (k.k->type != KEY_TYPE_inode)
1303 inode = bkey_s_c_to_inode(k);
1304 if (S_ISDIR(le16_to_cpu(inode.v->bi_mode)))
1307 BUG_ON(bch2_inode_unpack(inode, &u));
1312 while (link->inum < k.k->p.offset) {
1314 BUG_ON(link >= links->d + links->nr);
1317 if (fsck_err_on(bch2_inode_nlink_get(&u) != link->count, c,
1318 "inode %llu has wrong i_nlink (type %u i_nlink %u, should be %u)",
1319 u.bi_inum, mode_to_type(u.bi_mode),
1320 bch2_inode_nlink_get(&u), link->count)) {
1321 bch2_inode_nlink_set(&u, link->count);
1323 ret = __bch2_trans_do(&trans, NULL, NULL,
1324 BTREE_INSERT_NOFAIL|
1325 BTREE_INSERT_LAZY_RW,
1326 bch2_inode_write(&trans, iter, &u));
1328 bch_err(c, "error in fsck: error %i updating inode", ret);
1332 bch2_trans_iter_put(&trans, iter);
1333 bch2_trans_exit(&trans);
1336 bch_err(c, "error in fsck: btree error %i while walking inodes", ret);
1342 static int check_nlinks(struct bch_fs *c)
1344 struct nlink_table links = { 0 };
1345 u64 this_iter_range_start, next_iter_range_start = 0;
1348 bch_verbose(c, "checking inode nlinks");
1351 this_iter_range_start = next_iter_range_start;
1352 next_iter_range_start = U64_MAX;
1354 ret = check_nlinks_find_hardlinks(c, &links,
1355 this_iter_range_start,
1356 &next_iter_range_start);
1358 ret = check_nlinks_walk_dirents(c, &links,
1359 this_iter_range_start,
1360 next_iter_range_start);
1364 ret = check_nlinks_update_hardlinks(c, &links,
1365 this_iter_range_start,
1366 next_iter_range_start);
1371 } while (next_iter_range_start != U64_MAX);
1379 * Checks for inconsistencies that shouldn't happen, unless we have a bug.
1380 * Doesn't fix them yet, mainly because they haven't yet been observed:
1382 int bch2_fsck_full(struct bch_fs *c)
1384 struct bch_inode_unpacked root_inode;
1386 return check_inodes(c, true) ?:
1390 check_root(c, &root_inode) ?:
1391 check_directory_structure(c) ?:
1395 int bch2_fsck_walk_inodes_only(struct bch_fs *c)
1397 return check_inodes(c, false);