1 // SPDX-License-Identifier: GPL-2.0
5 #include "btree_update.h"
15 #include <linux/dcache.h> /* struct qstr */
16 #include <linux/generic-radix-tree.h>
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 write_inode(struct btree_trans *trans,
67 struct bch_inode_unpacked *inode,
70 struct btree_iter *inode_iter =
71 bch2_trans_get_iter(trans, BTREE_ID_inodes,
72 SPOS(0, inode->bi_inum, snapshot),
74 int ret = __bch2_trans_do(trans, NULL, NULL,
77 bch2_inode_write(trans, inode_iter, inode));
78 bch2_trans_iter_put(trans, inode_iter);
80 bch_err(trans->c, "error in fsck: error %i updating inode", ret);
84 static int __remove_dirent(struct btree_trans *trans,
85 struct bkey_s_c_dirent dirent)
87 struct bch_fs *c = trans->c;
89 struct bch_inode_unpacked dir_inode;
90 struct bch_hash_info dir_hash_info;
91 u64 dir_inum = dirent.k->p.inode;
95 name.len = bch2_dirent_name_bytes(dirent);
96 buf = bch2_trans_kmalloc(trans, name.len + 1);
100 memcpy(buf, dirent.v->d_name, name.len);
101 buf[name.len] = '\0';
104 ret = lookup_inode(trans, dir_inum, &dir_inode, NULL);
105 if (ret && ret != -EINTR)
106 bch_err(c, "remove_dirent: err %i looking up directory inode", ret);
110 dir_hash_info = bch2_hash_info_init(c, &dir_inode);
112 ret = bch2_hash_delete(trans, bch2_dirent_hash_desc,
113 &dir_hash_info, dir_inum, &name);
114 if (ret && ret != -EINTR)
115 bch_err(c, "remove_dirent: err %i deleting dirent", ret);
122 static int remove_dirent(struct btree_trans *trans,
123 struct bkey_s_c_dirent dirent)
125 return __bch2_trans_do(trans, NULL, NULL,
127 BTREE_INSERT_LAZY_RW,
128 __remove_dirent(trans, dirent));
131 static int __reattach_inode(struct btree_trans *trans,
132 struct bch_inode_unpacked *lostfound,
135 struct bch_hash_info dir_hash =
136 bch2_hash_info_init(trans->c, lostfound);
137 struct bch_inode_unpacked inode_u;
144 snprintf(name_buf, sizeof(name_buf), "%llu", inum);
145 name = (struct qstr) QSTR(name_buf);
147 ret = lookup_inode(trans, inum, &inode_u, &snapshot);
151 if (S_ISDIR(inode_u.bi_mode)) {
152 lostfound->bi_nlink++;
154 ret = write_inode(trans, lostfound, U32_MAX);
159 ret = bch2_dirent_create(trans, lostfound->bi_inum, &dir_hash,
160 mode_to_type(inode_u.bi_mode),
161 &name, inum, &dir_offset,
162 BCH_HASH_SET_MUST_CREATE);
166 inode_u.bi_dir = lostfound->bi_inum;
167 inode_u.bi_dir_offset = dir_offset;
169 return write_inode(trans, &inode_u, U32_MAX);
172 static int reattach_inode(struct btree_trans *trans,
173 struct bch_inode_unpacked *lostfound,
176 struct bch_fs *c = trans->c;
179 ret = __bch2_trans_do(trans, NULL, NULL, BTREE_INSERT_LAZY_RW,
180 __reattach_inode(trans, lostfound, inum));
182 bch_err(c, "error %i reattaching inode %llu", ret, inum);
187 static int remove_backpointer(struct btree_trans *trans,
188 struct bch_inode_unpacked *inode)
190 struct btree_iter *iter;
194 iter = bch2_trans_get_iter(trans, BTREE_ID_dirents,
195 POS(inode->bi_dir, inode->bi_dir_offset), 0);
196 k = bch2_btree_iter_peek_slot(iter);
200 if (k.k->type != KEY_TYPE_dirent) {
205 ret = remove_dirent(trans, bkey_s_c_to_dirent(k));
207 bch2_trans_iter_put(trans, iter);
211 struct inode_walker {
212 bool first_this_inode;
216 struct bch_inode_unpacked inode;
219 static struct inode_walker inode_walker_init(void)
221 return (struct inode_walker) {
227 static int walk_inode(struct btree_trans *trans,
228 struct inode_walker *w, u64 inum)
230 if (inum != w->cur_inum) {
231 int ret = lookup_inode(trans, inum, &w->inode, &w->snapshot);
233 if (ret && ret != -ENOENT)
236 w->have_inode = !ret;
238 w->first_this_inode = true;
240 w->first_this_inode = false;
246 static int hash_redo_key(struct btree_trans *trans,
247 const struct bch_hash_desc desc,
248 struct bch_hash_info *hash_info,
249 struct btree_iter *k_iter, struct bkey_s_c k)
251 struct bkey_i delete;
254 tmp = bch2_trans_kmalloc(trans, bkey_bytes(k.k));
258 bkey_reassemble(tmp, k);
260 bkey_init(&delete.k);
261 delete.k.p = k_iter->pos;
262 bch2_trans_update(trans, k_iter, &delete, 0);
264 return bch2_hash_set(trans, desc, hash_info, k_iter->pos.inode,
268 static int fsck_hash_delete_at(struct btree_trans *trans,
269 const struct bch_hash_desc desc,
270 struct bch_hash_info *info,
271 struct btree_iter *iter)
275 ret = bch2_hash_delete_at(trans, desc, info, iter) ?:
276 bch2_trans_commit(trans, NULL, NULL,
278 BTREE_INSERT_LAZY_RW);
280 ret = bch2_btree_iter_traverse(iter);
288 static int hash_check_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 hash_k)
293 struct bch_fs *c = trans->c;
294 struct btree_iter *iter = NULL;
300 if (hash_k.k->type != desc.key_type)
303 hash = desc.hash_bkey(hash_info, hash_k);
305 if (likely(hash == hash_k.k->p.offset))
308 if (hash_k.k->p.offset < hash)
311 for_each_btree_key(trans, iter, desc.btree_id, POS(hash_k.k->p.inode, hash),
312 BTREE_ITER_SLOTS, k, ret) {
313 if (!bkey_cmp(k.k->p, hash_k.k->p))
316 if (fsck_err_on(k.k->type == desc.key_type &&
317 !desc.cmp_bkey(k, hash_k), c,
318 "duplicate hash table keys:\n%s",
319 (bch2_bkey_val_to_text(&PBUF(buf), c,
321 ret = fsck_hash_delete_at(trans, desc, hash_info, k_iter);
328 if (bkey_deleted(k.k)) {
329 bch2_trans_iter_free(trans, iter);
334 bch2_trans_iter_free(trans, iter);
337 if (fsck_err(c, "hash table key at wrong offset: btree %u inode %llu offset %llu, "
338 "hashed to %llu should be at %llu\n%s",
339 desc.btree_id, hash_k.k->p.inode, hash_k.k->p.offset,
340 hash, iter->pos.offset,
341 (bch2_bkey_val_to_text(&PBUF(buf), c, hash_k), buf)) == FSCK_ERR_IGNORE)
344 ret = __bch2_trans_do(trans, NULL, NULL,
345 BTREE_INSERT_NOFAIL|BTREE_INSERT_LAZY_RW,
346 hash_redo_key(trans, desc, hash_info, k_iter, hash_k));
348 bch_err(c, "hash_redo_key err %i", ret);
356 static int check_inode(struct btree_trans *trans,
357 struct btree_iter *iter,
358 struct bkey_s_c_inode inode)
360 struct bch_fs *c = trans->c;
361 struct bch_inode_unpacked u;
362 bool do_update = false;
365 ret = bch2_inode_unpack(inode, &u);
367 if (bch2_fs_inconsistent_on(ret, c,
368 "error unpacking inode %llu in fsck",
372 if (u.bi_flags & BCH_INODE_UNLINKED &&
374 fsck_err(c, "filesystem marked clean, but inode %llu unlinked",
376 bch_verbose(c, "deleting inode %llu", u.bi_inum);
378 bch2_trans_unlock(trans);
381 ret = bch2_inode_rm(c, u.bi_inum, false);
383 bch_err(c, "error in fsck: error %i while deleting inode", ret);
387 if (u.bi_flags & BCH_INODE_I_SIZE_DIRTY &&
389 fsck_err(c, "filesystem marked clean, but inode %llu has i_size dirty",
391 bch_verbose(c, "truncating inode %llu", u.bi_inum);
393 bch2_trans_unlock(trans);
397 * XXX: need to truncate partial blocks too here - or ideally
398 * just switch units to bytes and that issue goes away
400 ret = bch2_btree_delete_range_trans(trans, BTREE_ID_extents,
401 POS(u.bi_inum, round_up(u.bi_size, block_bytes(c))),
402 POS(u.bi_inum, U64_MAX),
405 bch_err(c, "error in fsck: error %i truncating inode", ret);
410 * We truncated without our normal sector accounting hook, just
411 * make sure we recalculate it:
413 u.bi_flags |= BCH_INODE_I_SECTORS_DIRTY;
415 u.bi_flags &= ~BCH_INODE_I_SIZE_DIRTY;
419 if (u.bi_flags & BCH_INODE_I_SECTORS_DIRTY &&
421 fsck_err(c, "filesystem marked clean, but inode %llu has i_sectors dirty",
425 bch_verbose(c, "recounting sectors for inode %llu",
428 sectors = bch2_count_inode_sectors(trans, u.bi_inum);
430 bch_err(c, "error in fsck: error %i recounting inode sectors",
435 u.bi_sectors = sectors;
436 u.bi_flags &= ~BCH_INODE_I_SECTORS_DIRTY;
440 if (u.bi_flags & BCH_INODE_BACKPTR_UNTRUSTED) {
443 u.bi_flags &= ~BCH_INODE_BACKPTR_UNTRUSTED;
448 ret = __bch2_trans_do(trans, NULL, NULL,
450 BTREE_INSERT_LAZY_RW,
451 bch2_inode_write(trans, iter, &u));
453 bch_err(c, "error in fsck: error %i "
454 "updating inode", ret);
461 static int check_inodes(struct bch_fs *c, bool full)
463 struct btree_trans trans;
464 struct btree_iter *iter;
466 struct bkey_s_c_inode inode;
469 bch2_trans_init(&trans, c, BTREE_ITER_MAX, 0);
471 for_each_btree_key(&trans, iter, BTREE_ID_inodes, POS_MIN, 0, k, ret) {
472 if (k.k->type != KEY_TYPE_inode)
475 inode = bkey_s_c_to_inode(k);
478 (inode.v->bi_flags & (BCH_INODE_I_SIZE_DIRTY|
479 BCH_INODE_I_SECTORS_DIRTY|
480 BCH_INODE_UNLINKED))) {
481 ret = check_inode(&trans, iter, inode);
486 bch2_trans_iter_put(&trans, iter);
488 BUG_ON(ret == -EINTR);
490 return bch2_trans_exit(&trans) ?: ret;
493 static int fix_overlapping_extent(struct btree_trans *trans,
494 struct bkey_s_c k, struct bpos cut_at)
496 struct btree_iter *iter;
500 u = bch2_trans_kmalloc(trans, bkey_bytes(k.k));
501 ret = PTR_ERR_OR_ZERO(u);
505 bkey_reassemble(u, k);
506 bch2_cut_front(cut_at, u);
510 * We don't want to go through the extent_handle_overwrites path:
512 * XXX: this is going to screw up disk accounting, extent triggers
513 * assume things about extent overwrites - we should be running the
514 * triggers manually here
516 iter = bch2_trans_get_iter(trans, BTREE_ID_extents, u->k.p,
517 BTREE_ITER_INTENT|BTREE_ITER_NOT_EXTENTS);
519 BUG_ON(iter->flags & BTREE_ITER_IS_EXTENTS);
520 bch2_trans_update(trans, iter, u, BTREE_TRIGGER_NORUN);
521 bch2_trans_iter_put(trans, iter);
523 return bch2_trans_commit(trans, NULL, NULL,
525 BTREE_INSERT_LAZY_RW);
528 static int inode_backpointer_exists(struct btree_trans *trans,
529 struct bch_inode_unpacked *inode)
531 struct btree_iter *iter;
535 iter = bch2_trans_get_iter(trans, BTREE_ID_dirents,
536 POS(inode->bi_dir, inode->bi_dir_offset), 0);
537 k = bch2_btree_iter_peek_slot(iter);
541 if (k.k->type != KEY_TYPE_dirent)
544 ret = le64_to_cpu(bkey_s_c_to_dirent(k).v->d_inum) == inode->bi_inum;
546 bch2_trans_iter_free(trans, iter);
550 static bool inode_backpointer_matches(struct bkey_s_c_dirent d,
551 struct bch_inode_unpacked *inode)
553 return d.k->p.inode == inode->bi_dir &&
554 d.k->p.offset == inode->bi_dir_offset;
558 * Walk extents: verify that extents have a corresponding S_ISREG inode, and
559 * that i_size an i_sectors are consistent
562 static int check_extents(struct bch_fs *c)
564 struct inode_walker w = inode_walker_init();
565 struct btree_trans trans;
566 struct btree_iter *iter;
568 struct bkey_buf prev;
572 bch2_bkey_buf_init(&prev);
573 prev.k->k = KEY(0, 0, 0);
574 bch2_trans_init(&trans, c, BTREE_ITER_MAX, 0);
576 bch_verbose(c, "checking extents");
578 iter = bch2_trans_get_iter(&trans, BTREE_ID_extents,
579 POS(BCACHEFS_ROOT_INO, 0),
582 while ((k = bch2_btree_iter_peek(iter)).k &&
583 !(ret = bkey_err(k))) {
585 w.cur_inum != k.k->p.inode &&
586 !(w.inode.bi_flags & BCH_INODE_I_SECTORS_DIRTY) &&
587 fsck_err_on(w.inode.bi_sectors != i_sectors, c,
588 "inode %llu has incorrect i_sectors: got %llu, should be %llu",
590 w.inode.bi_sectors, i_sectors)) {
591 w.inode.bi_sectors = i_sectors;
593 ret = write_inode(&trans, &w.inode, w.snapshot);
598 if (bkey_cmp(prev.k->k.p, bkey_start_pos(k.k)) > 0) {
602 bch2_bkey_val_to_text(&PBUF(buf1), c, bkey_i_to_s_c(prev.k));
603 bch2_bkey_val_to_text(&PBUF(buf2), c, k);
605 if (fsck_err(c, "overlapping extents:\n%s\n%s", buf1, buf2))
606 return fix_overlapping_extent(&trans, k, prev.k->k.p) ?: -EINTR;
609 ret = walk_inode(&trans, &w, k.k->p.inode);
613 if (w.first_this_inode)
616 if (fsck_err_on(!w.have_inode, c,
617 "extent type %u for missing inode %llu",
618 k.k->type, k.k->p.inode) ||
619 fsck_err_on(w.have_inode &&
620 !S_ISREG(w.inode.bi_mode) && !S_ISLNK(w.inode.bi_mode), c,
621 "extent type %u for non regular file, inode %llu mode %o",
622 k.k->type, k.k->p.inode, w.inode.bi_mode)) {
624 return bch2_btree_delete_range_trans(&trans, BTREE_ID_extents,
625 POS(k.k->p.inode, 0),
626 POS(k.k->p.inode, U64_MAX),
630 if (fsck_err_on(w.have_inode &&
631 !(w.inode.bi_flags & BCH_INODE_I_SIZE_DIRTY) &&
632 k.k->type != KEY_TYPE_reservation &&
633 k.k->p.offset > round_up(w.inode.bi_size, block_bytes(c)) >> 9, c,
634 "extent type %u offset %llu past end of inode %llu, i_size %llu",
635 k.k->type, k.k->p.offset, k.k->p.inode, w.inode.bi_size)) {
637 return bch2_btree_delete_range_trans(&trans, BTREE_ID_extents,
638 POS(k.k->p.inode, round_up(w.inode.bi_size, block_bytes(c))),
639 POS(k.k->p.inode, U64_MAX),
643 if (bkey_extent_is_allocation(k.k))
644 i_sectors += k.k->size;
645 bch2_bkey_buf_reassemble(&prev, c, k);
647 bch2_btree_iter_advance(iter);
652 bch2_trans_iter_put(&trans, iter);
653 bch2_bkey_buf_exit(&prev, c);
654 return bch2_trans_exit(&trans) ?: ret;
658 * Walk dirents: verify that they all have a corresponding S_ISDIR inode,
662 static int check_dirents(struct bch_fs *c)
664 struct inode_walker w = inode_walker_init();
665 struct bch_hash_info hash_info;
666 struct btree_trans trans;
667 struct btree_iter *iter;
670 unsigned nr_subdirs = 0;
673 bch_verbose(c, "checking dirents");
675 bch2_trans_init(&trans, c, BTREE_ITER_MAX, 0);
677 iter = bch2_trans_get_iter(&trans, BTREE_ID_dirents,
678 POS(BCACHEFS_ROOT_INO, 0), 0);
680 while ((k = bch2_btree_iter_peek(iter)).k &&
681 !(ret = bkey_err(k))) {
682 struct bkey_s_c_dirent d;
683 struct bch_inode_unpacked target;
686 bool backpointer_exists = true;
690 w.cur_inum != k.k->p.inode &&
691 fsck_err_on(w.inode.bi_nlink != nr_subdirs, c,
692 "directory %llu with wrong i_nlink: got %u, should be %u",
693 w.inode.bi_inum, w.inode.bi_nlink, nr_subdirs)) {
694 w.inode.bi_nlink = nr_subdirs;
695 ret = write_inode(&trans, &w.inode, w.snapshot);
700 ret = walk_inode(&trans, &w, k.k->p.inode);
704 if (w.first_this_inode)
707 if (fsck_err_on(!w.have_inode, c,
708 "dirent in nonexisting directory:\n%s",
709 (bch2_bkey_val_to_text(&PBUF(buf), c,
711 fsck_err_on(!S_ISDIR(w.inode.bi_mode), c,
712 "dirent in non directory inode type %u:\n%s",
713 mode_to_type(w.inode.bi_mode),
714 (bch2_bkey_val_to_text(&PBUF(buf), c,
716 ret = lockrestart_do(&trans,
717 bch2_btree_delete_at(&trans, iter, 0));
726 if (w.first_this_inode)
727 hash_info = bch2_hash_info_init(c, &w.inode);
729 ret = hash_check_key(&trans, bch2_dirent_hash_desc,
730 &hash_info, iter, k);
738 if (k.k->type != KEY_TYPE_dirent)
741 d = bkey_s_c_to_dirent(k);
742 d_inum = le64_to_cpu(d.v->d_inum);
744 ret = lookup_inode(&trans, d_inum, &target, &target_snapshot);
745 if (ret && ret != -ENOENT)
751 if (fsck_err_on(!have_target, c,
752 "dirent points to missing inode:\n%s",
753 (bch2_bkey_val_to_text(&PBUF(buf), c,
755 ret = remove_dirent(&trans, d);
764 if (!target.bi_dir &&
765 !target.bi_dir_offset) {
766 target.bi_dir = k.k->p.inode;
767 target.bi_dir_offset = k.k->p.offset;
769 ret = write_inode(&trans, &target, target_snapshot);
774 if (!inode_backpointer_matches(d, &target)) {
775 ret = inode_backpointer_exists(&trans, &target);
779 backpointer_exists = ret;
782 if (fsck_err_on(S_ISDIR(target.bi_mode) &&
783 backpointer_exists, c,
784 "directory %llu with multiple links",
786 ret = remove_dirent(&trans, d);
792 if (fsck_err_on(backpointer_exists &&
794 "inode %llu has multiple links but i_nlink 0",
797 target.bi_flags &= ~BCH_INODE_UNLINKED;
799 ret = write_inode(&trans, &target, target_snapshot);
804 if (fsck_err_on(!backpointer_exists, c,
805 "inode %llu has wrong backpointer:\n"
807 "should be %llu:%llu",
810 target.bi_dir_offset,
813 target.bi_dir = k.k->p.inode;
814 target.bi_dir_offset = k.k->p.offset;
816 ret = write_inode(&trans, &target, target_snapshot);
822 if (fsck_err_on(d.v->d_type != mode_to_type(target.bi_mode), c,
823 "incorrect d_type: should be %u:\n%s",
824 mode_to_type(target.bi_mode),
825 (bch2_bkey_val_to_text(&PBUF(buf), c,
827 struct bkey_i_dirent *n;
829 n = kmalloc(bkey_bytes(d.k), GFP_KERNEL);
835 bkey_reassemble(&n->k_i, d.s_c);
836 n->v.d_type = mode_to_type(target.bi_mode);
838 ret = __bch2_trans_do(&trans, NULL, NULL,
840 BTREE_INSERT_LAZY_RW,
841 (bch2_trans_update(&trans, iter, &n->k_i, 0), 0));
848 nr_subdirs += d.v->d_type == DT_DIR;
850 bch2_btree_iter_advance(iter);
857 bch2_trans_iter_put(&trans, iter);
858 return bch2_trans_exit(&trans) ?: ret;
862 * Walk xattrs: verify that they all have a corresponding inode
865 static int check_xattrs(struct bch_fs *c)
867 struct inode_walker w = inode_walker_init();
868 struct bch_hash_info hash_info;
869 struct btree_trans trans;
870 struct btree_iter *iter;
874 bch_verbose(c, "checking xattrs");
876 bch2_trans_init(&trans, c, BTREE_ITER_MAX, 0);
878 iter = bch2_trans_get_iter(&trans, BTREE_ID_xattrs,
879 POS(BCACHEFS_ROOT_INO, 0), 0);
881 while ((k = bch2_btree_iter_peek(iter)).k &&
882 !(ret = bkey_err(k))) {
883 ret = walk_inode(&trans, &w, k.k->p.inode);
887 if (fsck_err_on(!w.have_inode, c,
888 "xattr for missing inode %llu",
890 ret = bch2_btree_delete_at(&trans, iter, 0);
896 if (w.first_this_inode && w.have_inode)
897 hash_info = bch2_hash_info_init(c, &w.inode);
899 ret = hash_check_key(&trans, bch2_xattr_hash_desc,
900 &hash_info, iter, k);
904 bch2_btree_iter_advance(iter);
910 bch2_trans_iter_put(&trans, iter);
911 return bch2_trans_exit(&trans) ?: ret;
914 /* Get root directory, create if it doesn't exist: */
915 static int check_root(struct bch_fs *c, struct bch_inode_unpacked *root_inode)
917 struct bkey_inode_buf packed;
921 bch_verbose(c, "checking root directory");
923 ret = bch2_trans_do(c, NULL, NULL, 0,
924 lookup_inode(&trans, BCACHEFS_ROOT_INO, root_inode, &snapshot));
925 if (ret && ret != -ENOENT)
928 if (fsck_err_on(ret, c, "root directory missing"))
931 if (fsck_err_on(!S_ISDIR(root_inode->bi_mode), c,
932 "root inode not a directory"))
939 bch2_inode_init(c, root_inode, 0, 0, S_IFDIR|0755,
941 root_inode->bi_inum = BCACHEFS_ROOT_INO;
943 bch2_inode_pack(c, &packed, root_inode);
945 return bch2_btree_insert(c, BTREE_ID_inodes, &packed.inode.k_i,
948 BTREE_INSERT_LAZY_RW);
951 /* Get lost+found, create if it doesn't exist: */
952 static int check_lostfound(struct bch_fs *c,
953 struct bch_inode_unpacked *root_inode,
954 struct bch_inode_unpacked *lostfound_inode)
956 struct qstr lostfound = QSTR("lost+found");
957 struct bch_hash_info root_hash_info =
958 bch2_hash_info_init(c, root_inode);
963 bch_verbose(c, "checking lost+found");
965 inum = bch2_dirent_lookup(c, BCACHEFS_ROOT_INO, &root_hash_info,
968 bch_notice(c, "creating lost+found");
969 goto create_lostfound;
972 ret = bch2_trans_do(c, NULL, NULL, 0,
973 lookup_inode(&trans, inum, lostfound_inode, &snapshot));
974 if (ret && ret != -ENOENT)
977 if (fsck_err_on(ret, c, "lost+found missing"))
978 goto create_lostfound;
980 if (fsck_err_on(!S_ISDIR(lostfound_inode->bi_mode), c,
981 "lost+found inode not a directory"))
982 goto create_lostfound;
988 bch2_inode_init_early(c, lostfound_inode);
990 ret = bch2_trans_do(c, NULL, NULL,
992 BTREE_INSERT_LAZY_RW,
993 bch2_create_trans(&trans,
994 BCACHEFS_ROOT_INO, root_inode,
995 lostfound_inode, &lostfound,
996 0, 0, S_IFDIR|0700, 0, NULL, NULL));
998 bch_err(c, "error creating lost+found: %i", ret);
1007 struct pathbuf_entry {
1012 static int path_down(struct pathbuf *p, u64 inum)
1014 if (p->nr == p->size) {
1015 size_t new_size = max_t(size_t, 256UL, p->size * 2);
1016 void *n = krealloc(p->entries,
1017 new_size * sizeof(p->entries[0]),
1027 p->entries[p->nr++] = (struct pathbuf_entry) {
1033 static int check_path(struct btree_trans *trans,
1034 struct bch_inode_unpacked *lostfound,
1036 struct bch_inode_unpacked *inode)
1038 struct bch_fs *c = trans->c;
1045 while (inode->bi_inum != BCACHEFS_ROOT_INO) {
1046 ret = lockrestart_do(trans,
1047 inode_backpointer_exists(trans, inode));
1052 if (fsck_err(c, "unreachable inode %llu, type %u nlink %u backptr %llu:%llu",
1054 mode_to_type(inode->bi_mode),
1057 inode->bi_dir_offset))
1058 ret = reattach_inode(trans, lostfound, inode->bi_inum);
1063 if (!S_ISDIR(inode->bi_mode))
1066 ret = path_down(p, inode->bi_inum);
1068 bch_err(c, "memory allocation failure");
1072 for (i = 0; i < p->nr; i++) {
1073 if (inode->bi_dir != p->entries[i].inum)
1076 /* XXX print path */
1077 if (!fsck_err(c, "directory structure loop"))
1080 ret = lockrestart_do(trans,
1081 remove_backpointer(trans, inode));
1083 bch_err(c, "error removing dirent: %i", ret);
1087 ret = reattach_inode(trans, lostfound, inode->bi_inum);
1091 ret = lockrestart_do(trans,
1092 lookup_inode(trans, inode->bi_dir, inode, &snapshot));
1094 /* Should have been caught in dirents pass */
1095 bch_err(c, "error looking up parent directory: %i", ret);
1101 bch_err(c, "%s: err %i", __func__, ret);
1106 * Check for unreachable inodes, as well as loops in the directory structure:
1107 * After check_dirents(), if an inode backpointer doesn't exist that means it's
1110 static int check_directory_structure(struct bch_fs *c,
1111 struct bch_inode_unpacked *lostfound)
1113 struct btree_trans trans;
1114 struct btree_iter *iter;
1116 struct bch_inode_unpacked u;
1117 struct pathbuf path = { 0, 0, NULL };
1120 bch2_trans_init(&trans, c, BTREE_ITER_MAX, 0);
1122 for_each_btree_key(&trans, iter, BTREE_ID_inodes, POS_MIN, 0, k, ret) {
1123 if (k.k->type != KEY_TYPE_inode)
1126 ret = bch2_inode_unpack(bkey_s_c_to_inode(k), &u);
1128 /* Should have been caught earlier in fsck: */
1129 bch_err(c, "error unpacking inode %llu: %i", k.k->p.offset, ret);
1133 ret = check_path(&trans, lostfound, &path, &u);
1137 bch2_trans_iter_put(&trans, iter);
1139 BUG_ON(ret == -EINTR);
1141 kfree(path.entries);
1143 return bch2_trans_exit(&trans) ?: ret;
1150 typedef GENRADIX(struct nlink) nlink_table;
1152 static void inc_link(struct bch_fs *c, nlink_table *links,
1153 u64 range_start, u64 *range_end, u64 inum)
1157 if (inum < range_start || inum >= *range_end)
1160 if (inum - range_start >= SIZE_MAX / sizeof(struct nlink)) {
1165 link = genradix_ptr_alloc(links, inum - range_start, GFP_KERNEL);
1167 bch_verbose(c, "allocation failed during fsck - will need another pass");
1176 static int bch2_gc_walk_dirents(struct bch_fs *c, nlink_table *links,
1177 u64 range_start, u64 *range_end)
1179 struct btree_trans trans;
1180 struct btree_iter *iter;
1182 struct bkey_s_c_dirent d;
1185 bch2_trans_init(&trans, c, BTREE_ITER_MAX, 0);
1187 for_each_btree_key(&trans, iter, BTREE_ID_dirents, POS_MIN, 0, k, ret) {
1188 switch (k.k->type) {
1189 case KEY_TYPE_dirent:
1190 d = bkey_s_c_to_dirent(k);
1192 if (d.v->d_type != DT_DIR)
1193 inc_link(c, links, range_start, range_end,
1194 le64_to_cpu(d.v->d_inum));
1198 bch2_trans_cond_resched(&trans);
1200 bch2_trans_iter_put(&trans, iter);
1202 ret = bch2_trans_exit(&trans) ?: ret;
1204 bch_err(c, "error in fsck: btree error %i while walking dirents", ret);
1209 static int check_inode_nlink(struct btree_trans *trans,
1210 struct bch_inode_unpacked *lostfound_inode,
1211 struct btree_iter *iter,
1212 struct bkey_s_c_inode inode,
1215 struct bch_fs *c = trans->c;
1216 struct bch_inode_unpacked u;
1220 * Backpointer and directory structure checks are sufficient for
1221 * directories, since they can't have hardlinks:
1223 if (S_ISDIR(le16_to_cpu(inode.v->bi_mode)))
1227 bch_err(c, "no links found to inode %llu", inode.k->p.offset);
1231 ret = bch2_inode_unpack(inode, &u);
1233 /* Should never happen, checked by bch2_inode_invalid: */
1234 if (bch2_fs_inconsistent_on(ret, c,
1235 "error unpacking inode %llu in fsck",
1239 if (fsck_err_on(bch2_inode_nlink_get(&u) != nlink, c,
1240 "inode %llu has wrong i_nlink (type %u i_nlink %u, should be %u)",
1241 u.bi_inum, mode_to_type(u.bi_mode),
1242 bch2_inode_nlink_get(&u), nlink)) {
1243 bch2_inode_nlink_set(&u, nlink);
1245 ret = __bch2_trans_do(trans, NULL, NULL,
1246 BTREE_INSERT_NOFAIL|
1247 BTREE_INSERT_LAZY_RW,
1248 bch2_inode_write(trans, iter, &u));
1250 bch_err(c, "error in fsck: error %i updating inode", ret);
1257 static int bch2_gc_walk_inodes(struct bch_fs *c,
1258 struct bch_inode_unpacked *lostfound_inode,
1260 u64 range_start, u64 range_end)
1262 struct btree_trans trans;
1263 struct btree_iter *iter;
1268 bch2_trans_init(&trans, c, BTREE_ITER_MAX, 0);
1270 for_each_btree_key(&trans, iter, BTREE_ID_inodes,
1271 POS(0, range_start), 0, k, ret) {
1272 if (!k.k || k.k->p.offset >= range_end)
1275 if (k.k->type != KEY_TYPE_inode)
1278 link = genradix_ptr(links, k.k->p.offset - range_start);
1279 ret = check_inode_nlink(&trans, lostfound_inode, iter,
1280 bkey_s_c_to_inode(k), link ? link->count : 0);
1285 bch2_trans_iter_put(&trans, iter);
1286 bch2_trans_exit(&trans);
1289 bch_err(c, "error in fsck: btree error %i while walking inodes", ret);
1295 static int check_nlinks(struct bch_fs *c,
1296 struct bch_inode_unpacked *lostfound_inode)
1299 u64 this_iter_range_start, next_iter_range_start = 0;
1302 bch_verbose(c, "checking inode nlinks");
1304 genradix_init(&links);
1307 this_iter_range_start = next_iter_range_start;
1308 next_iter_range_start = U64_MAX;
1310 ret = bch2_gc_walk_dirents(c, &links,
1311 this_iter_range_start,
1312 &next_iter_range_start);
1316 ret = bch2_gc_walk_inodes(c, lostfound_inode, &links,
1317 this_iter_range_start,
1318 next_iter_range_start);
1322 genradix_free(&links);
1323 } while (next_iter_range_start != U64_MAX);
1325 genradix_free(&links);
1331 * Checks for inconsistencies that shouldn't happen, unless we have a bug.
1332 * Doesn't fix them yet, mainly because they haven't yet been observed:
1334 int bch2_fsck_full(struct bch_fs *c)
1336 struct bch_inode_unpacked root_inode, lostfound_inode;
1338 return check_inodes(c, true) ?:
1342 check_root(c, &root_inode) ?:
1343 check_lostfound(c, &root_inode, &lostfound_inode) ?:
1344 check_directory_structure(c, &lostfound_inode) ?:
1345 check_nlinks(c, &lostfound_inode);
1348 int bch2_fsck_walk_inodes_only(struct bch_fs *c)
1350 return check_inodes(c, false);