1 // SPDX-License-Identifier: GPL-2.0
4 #include "btree_update.h"
14 #include <linux/dcache.h> /* struct qstr */
15 #include <linux/generic-radix-tree.h>
17 #define QSTR(n) { { { .len = strlen(n) } }, .name = n }
19 static s64 bch2_count_inode_sectors(struct btree_trans *trans, u64 inum)
21 struct btree_iter *iter;
26 for_each_btree_key(trans, iter, BTREE_ID_EXTENTS,
27 POS(inum, 0), 0, k, ret) {
28 if (k.k->p.inode != inum)
31 if (bkey_extent_is_allocation(k.k))
35 bch2_trans_iter_free(trans, iter);
37 return ret ?: sectors;
40 static int __remove_dirent(struct btree_trans *trans,
41 struct bkey_s_c_dirent dirent)
43 struct bch_fs *c = trans->c;
45 struct bch_inode_unpacked dir_inode;
46 struct bch_hash_info dir_hash_info;
47 u64 dir_inum = dirent.k->p.inode;
51 name.len = bch2_dirent_name_bytes(dirent);
52 buf = bch2_trans_kmalloc(trans, name.len + 1);
56 memcpy(buf, dirent.v->d_name, name.len);
60 ret = bch2_inode_find_by_inum_trans(trans, dir_inum, &dir_inode);
61 if (ret && ret != -EINTR)
62 bch_err(c, "remove_dirent: err %i looking up directory inode", ret);
66 dir_hash_info = bch2_hash_info_init(c, &dir_inode);
68 ret = bch2_hash_delete(trans, bch2_dirent_hash_desc,
69 &dir_hash_info, dir_inum, &name);
70 if (ret && ret != -EINTR)
71 bch_err(c, "remove_dirent: err %i deleting dirent", ret);
78 static int remove_dirent(struct btree_trans *trans,
79 struct bkey_s_c_dirent dirent)
81 return __bch2_trans_do(trans, NULL, NULL,
85 __remove_dirent(trans, dirent));
88 static int reattach_inode(struct bch_fs *c,
89 struct bch_inode_unpacked *lostfound_inode,
92 struct bch_inode_unpacked dir_u, inode_u;
97 snprintf(name_buf, sizeof(name_buf), "%llu", inum);
98 name = (struct qstr) QSTR(name_buf);
100 ret = bch2_trans_do(c, NULL, NULL,
101 BTREE_INSERT_LAZY_RW,
102 bch2_link_trans(&trans, lostfound_inode->bi_inum,
103 inum, &dir_u, &inode_u, &name));
105 bch_err(c, "error %i reattaching inode %llu", ret, inum);
110 struct inode_walker {
111 bool first_this_inode;
114 struct bch_inode_unpacked inode;
117 static struct inode_walker inode_walker_init(void)
119 return (struct inode_walker) {
125 static int walk_inode(struct btree_trans *trans,
126 struct inode_walker *w, u64 inum)
128 if (inum != w->cur_inum) {
129 int ret = bch2_inode_find_by_inum_trans(trans, inum,
132 if (ret && ret != -ENOENT)
135 w->have_inode = !ret;
137 w->first_this_inode = true;
139 w->first_this_inode = false;
146 struct bch_hash_info info;
148 /* start of current chain of hash collisions: */
149 struct btree_iter *chain;
151 /* next offset in current chain of hash collisions: */
155 static void hash_check_init(struct hash_check *h)
161 static void hash_stop_chain(struct btree_trans *trans,
162 struct hash_check *h)
165 bch2_trans_iter_free(trans, h->chain);
169 static void hash_check_set_inode(struct btree_trans *trans,
170 struct hash_check *h,
171 const struct bch_inode_unpacked *bi)
173 h->info = bch2_hash_info_init(trans->c, bi);
174 hash_stop_chain(trans, h);
177 static int hash_redo_key(const struct bch_hash_desc desc,
178 struct btree_trans *trans, struct hash_check *h,
179 struct btree_iter *k_iter, struct bkey_s_c k,
182 struct bkey_i delete;
185 bch2_trans_reset(trans, TRANS_RESET_MEM);
187 tmp = bch2_trans_kmalloc(trans, bkey_bytes(k.k));
191 bkey_reassemble(tmp, k);
193 bkey_init(&delete.k);
194 delete.k.p = k_iter->pos;
195 bch2_trans_update(trans, k_iter, &delete);
197 return bch2_hash_set(trans, desc, &h->info, k_iter->pos.inode,
198 tmp, BCH_HASH_SET_MUST_CREATE) ?:
199 bch2_trans_commit(trans, NULL, NULL,
201 BTREE_INSERT_LAZY_RW);
204 static int fsck_hash_delete_at(struct btree_trans *trans,
205 const struct bch_hash_desc desc,
206 struct bch_hash_info *info,
207 struct btree_iter *iter)
211 ret = bch2_hash_delete_at(trans, desc, info, iter) ?:
212 bch2_trans_commit(trans, NULL, NULL,
214 BTREE_INSERT_LAZY_RW);
216 ret = bch2_btree_iter_traverse(iter);
224 static int hash_check_duplicates(struct btree_trans *trans,
225 const struct bch_hash_desc desc, struct hash_check *h,
226 struct btree_iter *k_iter, struct bkey_s_c k)
228 struct bch_fs *c = trans->c;
229 struct btree_iter *iter;
234 if (!bkey_cmp(h->chain->pos, k_iter->pos))
237 iter = bch2_trans_copy_iter(trans, h->chain);
238 BUG_ON(IS_ERR(iter));
240 for_each_btree_key_continue(iter, 0, k2, ret) {
241 if (bkey_cmp(k2.k->p, k.k->p) >= 0)
244 if (fsck_err_on(k2.k->type == desc.key_type &&
245 !desc.cmp_bkey(k, k2), c,
246 "duplicate hash table keys:\n%s",
247 (bch2_bkey_val_to_text(&PBUF(buf), c,
249 ret = fsck_hash_delete_at(trans, desc, &h->info, k_iter);
257 bch2_trans_iter_free(trans, iter);
261 static void hash_set_chain_start(struct btree_trans *trans,
262 const struct bch_hash_desc desc,
263 struct hash_check *h,
264 struct btree_iter *k_iter, struct bkey_s_c k)
266 bool hole = (k.k->type != KEY_TYPE_whiteout &&
267 k.k->type != desc.key_type);
269 if (hole || k.k->p.offset > h->chain_end + 1)
270 hash_stop_chain(trans, h);
274 h->chain = bch2_trans_copy_iter(trans, k_iter);
275 BUG_ON(IS_ERR(h->chain));
278 h->chain_end = k.k->p.offset;
282 static bool key_has_correct_hash(struct btree_trans *trans,
283 const struct bch_hash_desc desc,
284 struct hash_check *h,
285 struct btree_iter *k_iter, struct bkey_s_c k)
289 hash_set_chain_start(trans, desc, h, k_iter, k);
291 if (k.k->type != desc.key_type)
294 hash = desc.hash_bkey(&h->info, k);
296 return hash >= h->chain->pos.offset &&
297 hash <= k.k->p.offset;
300 static int hash_check_key(struct btree_trans *trans,
301 const struct bch_hash_desc desc, struct hash_check *h,
302 struct btree_iter *k_iter, struct bkey_s_c k)
304 struct bch_fs *c = trans->c;
309 hash_set_chain_start(trans, desc, h, k_iter, k);
311 if (k.k->type != desc.key_type)
314 hashed = desc.hash_bkey(&h->info, k);
316 if (fsck_err_on(hashed < h->chain->pos.offset ||
317 hashed > k.k->p.offset, c,
318 "hash table key at wrong offset: btree %u, %llu, "
319 "hashed to %llu chain starts at %llu\n%s",
320 desc.btree_id, k.k->p.offset,
321 hashed, h->chain->pos.offset,
322 (bch2_bkey_val_to_text(&PBUF(buf), c, k), buf))) {
324 ret = hash_redo_key(desc, trans, h, k_iter, k, hashed);
325 } while (ret == -EINTR);
328 bch_err(c, "hash_redo_key err %i", ret);
334 ret = hash_check_duplicates(trans, desc, h, k_iter, k);
339 static int check_dirent_hash(struct btree_trans *trans, struct hash_check *h,
340 struct btree_iter *iter, struct bkey_s_c *k)
342 struct bch_fs *c = trans->c;
343 struct bkey_i_dirent *d = NULL;
349 if (key_has_correct_hash(trans, bch2_dirent_hash_desc, h, iter, *k))
352 len = bch2_dirent_name_bytes(bkey_s_c_to_dirent(*k));
355 memcpy(buf, bkey_s_c_to_dirent(*k).v->d_name, len);
358 d = kmalloc(bkey_bytes(k->k), GFP_KERNEL);
360 bch_err(c, "memory allocation failure");
364 bkey_reassemble(&d->k_i, *k);
371 d->k.u64s = BKEY_U64s + dirent_val_u64s(len);
373 BUG_ON(bkey_val_bytes(&d->k) <
374 offsetof(struct bch_dirent, d_name) + len);
376 memset(d->v.d_name + len, 0,
377 bkey_val_bytes(&d->k) -
378 offsetof(struct bch_dirent, d_name) - len);
380 hash = bch2_dirent_hash_desc.hash_bkey(&h->info,
381 bkey_i_to_s_c(&d->k_i));
382 } while (hash < h->chain->pos.offset ||
383 hash > k->k->p.offset);
385 if (fsck_err(c, "dirent with junk at end, was %s (%zu) now %s (%u)",
386 buf, strlen(buf), d->v.d_name, len)) {
387 ret = __bch2_trans_do(trans, NULL, NULL,
389 BTREE_INSERT_LAZY_RW,
391 (bch2_trans_update(trans, iter, &d->k_i), 0));
395 *k = bch2_btree_iter_peek(iter);
397 BUG_ON(k->k->type != KEY_TYPE_dirent);
404 hash = bch2_dirent_hash_desc.hash_bkey(&h->info, *k);
406 if (fsck_err(c, "cannot fix dirent by removing trailing garbage %s (%zu)\n"
407 "hash table key at wrong offset: btree %u, offset %llu, "
408 "hashed to %llu chain starts at %llu\n%s",
409 buf, strlen(buf), BTREE_ID_DIRENTS,
410 k->k->p.offset, hash, h->chain->pos.offset,
411 (bch2_bkey_val_to_text(&PBUF(buf), c,
414 ret = hash_redo_key(bch2_dirent_hash_desc, trans,
416 } while (ret == -EINTR);
419 bch_err(c, "hash_redo_key err %i", ret);
427 static int bch2_inode_truncate(struct bch_fs *c, u64 inode_nr, u64 new_size)
429 return bch2_btree_delete_range(c, BTREE_ID_EXTENTS,
430 POS(inode_nr, round_up(new_size, block_bytes(c)) >> 9),
431 POS(inode_nr + 1, 0), NULL);
435 * Walk extents: verify that extents have a corresponding S_ISREG inode, and
436 * that i_size an i_sectors are consistent
439 static int check_extents(struct bch_fs *c)
441 struct inode_walker w = inode_walker_init();
442 struct btree_trans trans;
443 struct btree_iter *iter;
448 bch2_trans_init(&trans, c, BTREE_ITER_MAX, 0);
450 bch_verbose(c, "checking extents");
452 iter = bch2_trans_get_iter(&trans, BTREE_ID_EXTENTS,
453 POS(BCACHEFS_ROOT_INO, 0), 0);
455 for_each_btree_key_continue(iter, 0, k, ret) {
456 ret = walk_inode(&trans, &w, k.k->p.inode);
460 if (fsck_err_on(!w.have_inode, c,
461 "extent type %u for missing inode %llu",
462 k.k->type, k.k->p.inode) ||
463 fsck_err_on(w.have_inode &&
464 !S_ISREG(w.inode.bi_mode) && !S_ISLNK(w.inode.bi_mode), c,
465 "extent type %u for non regular file, inode %llu mode %o",
466 k.k->type, k.k->p.inode, w.inode.bi_mode)) {
467 bch2_trans_unlock(&trans);
469 ret = bch2_inode_truncate(c, k.k->p.inode, 0);
475 if (fsck_err_on(w.first_this_inode &&
477 !(w.inode.bi_flags & BCH_INODE_I_SECTORS_DIRTY) &&
478 w.inode.bi_sectors !=
479 (i_sectors = bch2_count_inode_sectors(&trans, w.cur_inum)),
480 c, "i_sectors wrong: got %llu, should be %llu",
481 w.inode.bi_sectors, i_sectors)) {
482 struct bkey_inode_buf p;
484 w.inode.bi_sectors = i_sectors;
486 bch2_trans_unlock(&trans);
488 bch2_inode_pack(&p, &w.inode);
490 ret = bch2_btree_insert(c, BTREE_ID_INODES,
491 &p.inode.k_i, NULL, NULL,
493 BTREE_INSERT_LAZY_RW);
495 bch_err(c, "error in fsck: error %i updating inode", ret);
499 /* revalidate iterator: */
500 k = bch2_btree_iter_peek(iter);
503 if (fsck_err_on(w.have_inode &&
504 !(w.inode.bi_flags & BCH_INODE_I_SIZE_DIRTY) &&
505 k.k->type != KEY_TYPE_reservation &&
506 k.k->p.offset > round_up(w.inode.bi_size, block_bytes(c)) >> 9, c,
507 "extent type %u offset %llu past end of inode %llu, i_size %llu",
508 k.k->type, k.k->p.offset, k.k->p.inode, w.inode.bi_size)) {
509 bch2_trans_unlock(&trans);
511 ret = bch2_inode_truncate(c, k.k->p.inode,
522 return bch2_trans_exit(&trans) ?: ret;
526 * Walk dirents: verify that they all have a corresponding S_ISDIR inode,
530 static int check_dirents(struct bch_fs *c)
532 struct inode_walker w = inode_walker_init();
534 struct btree_trans trans;
535 struct btree_iter *iter;
541 bch_verbose(c, "checking dirents");
543 bch2_trans_init(&trans, c, BTREE_ITER_MAX, 0);
547 iter = bch2_trans_get_iter(&trans, BTREE_ID_DIRENTS,
548 POS(BCACHEFS_ROOT_INO, 0), 0);
550 for_each_btree_key_continue(iter, 0, k, ret) {
551 struct bkey_s_c_dirent d;
552 struct bch_inode_unpacked target;
556 ret = walk_inode(&trans, &w, k.k->p.inode);
560 if (fsck_err_on(!w.have_inode, c,
561 "dirent in nonexisting directory:\n%s",
562 (bch2_bkey_val_to_text(&PBUF(buf), c,
564 fsck_err_on(!S_ISDIR(w.inode.bi_mode), c,
565 "dirent in non directory inode type %u:\n%s",
566 mode_to_type(w.inode.bi_mode),
567 (bch2_bkey_val_to_text(&PBUF(buf), c,
569 ret = bch2_btree_delete_at(&trans, iter, 0);
575 if (w.first_this_inode && w.have_inode)
576 hash_check_set_inode(&trans, &h, &w.inode);
578 ret = check_dirent_hash(&trans, &h, iter, &k);
589 if (k.k->type != KEY_TYPE_dirent)
592 d = bkey_s_c_to_dirent(k);
593 d_inum = le64_to_cpu(d.v->d_inum);
595 name_len = bch2_dirent_name_bytes(d);
597 if (fsck_err_on(!name_len, c, "empty dirent") ||
598 fsck_err_on(name_len == 1 &&
599 !memcmp(d.v->d_name, ".", 1), c,
601 fsck_err_on(name_len == 2 &&
602 !memcmp(d.v->d_name, "..", 2), c,
604 fsck_err_on(name_len == 2 &&
605 !memcmp(d.v->d_name, "..", 2), c,
607 fsck_err_on(memchr(d.v->d_name, '/', name_len), c,
608 "dirent name has invalid chars")) {
609 ret = remove_dirent(&trans, d);
615 if (fsck_err_on(d_inum == d.k->p.inode, c,
616 "dirent points to own directory:\n%s",
617 (bch2_bkey_val_to_text(&PBUF(buf), c,
619 ret = remove_dirent(&trans, d);
625 ret = bch2_inode_find_by_inum_trans(&trans, d_inum, &target);
626 if (ret && ret != -ENOENT)
632 if (fsck_err_on(!have_target, c,
633 "dirent points to missing inode:\n%s",
634 (bch2_bkey_val_to_text(&PBUF(buf), c,
636 ret = remove_dirent(&trans, d);
642 if (fsck_err_on(have_target &&
644 mode_to_type(target.bi_mode), c,
645 "incorrect d_type: should be %u:\n%s",
646 mode_to_type(target.bi_mode),
647 (bch2_bkey_val_to_text(&PBUF(buf), c,
649 struct bkey_i_dirent *n;
651 n = kmalloc(bkey_bytes(d.k), GFP_KERNEL);
657 bkey_reassemble(&n->k_i, d.s_c);
658 n->v.d_type = mode_to_type(target.bi_mode);
660 ret = __bch2_trans_do(&trans, NULL, NULL,
662 BTREE_INSERT_LAZY_RW,
664 (bch2_trans_update(&trans, iter, &n->k_i), 0));
672 hash_stop_chain(&trans, &h);
678 return bch2_trans_exit(&trans) ?: ret;
682 * Walk xattrs: verify that they all have a corresponding inode
685 static int check_xattrs(struct bch_fs *c)
687 struct inode_walker w = inode_walker_init();
689 struct btree_trans trans;
690 struct btree_iter *iter;
694 bch_verbose(c, "checking xattrs");
698 bch2_trans_init(&trans, c, BTREE_ITER_MAX, 0);
700 iter = bch2_trans_get_iter(&trans, BTREE_ID_XATTRS,
701 POS(BCACHEFS_ROOT_INO, 0), 0);
703 for_each_btree_key_continue(iter, 0, k, ret) {
704 ret = walk_inode(&trans, &w, k.k->p.inode);
708 if (fsck_err_on(!w.have_inode, c,
709 "xattr for missing inode %llu",
711 ret = bch2_btree_delete_at(&trans, iter, 0);
717 if (w.first_this_inode && w.have_inode)
718 hash_check_set_inode(&trans, &h, &w.inode);
720 ret = hash_check_key(&trans, bch2_xattr_hash_desc,
729 return bch2_trans_exit(&trans) ?: ret;
732 /* Get root directory, create if it doesn't exist: */
733 static int check_root(struct bch_fs *c, struct bch_inode_unpacked *root_inode)
735 struct bkey_inode_buf packed;
738 bch_verbose(c, "checking root directory");
740 ret = bch2_inode_find_by_inum(c, BCACHEFS_ROOT_INO, root_inode);
741 if (ret && ret != -ENOENT)
744 if (fsck_err_on(ret, c, "root directory missing"))
747 if (fsck_err_on(!S_ISDIR(root_inode->bi_mode), c,
748 "root inode not a directory"))
755 bch2_inode_init(c, root_inode, 0, 0, S_IFDIR|0755,
757 root_inode->bi_inum = BCACHEFS_ROOT_INO;
759 bch2_inode_pack(&packed, root_inode);
761 return bch2_btree_insert(c, BTREE_ID_INODES, &packed.inode.k_i,
764 BTREE_INSERT_LAZY_RW);
767 /* Get lost+found, create if it doesn't exist: */
768 static int check_lostfound(struct bch_fs *c,
769 struct bch_inode_unpacked *root_inode,
770 struct bch_inode_unpacked *lostfound_inode)
772 struct qstr lostfound = QSTR("lost+found");
773 struct bch_hash_info root_hash_info =
774 bch2_hash_info_init(c, root_inode);
778 bch_verbose(c, "checking lost+found");
780 inum = bch2_dirent_lookup(c, BCACHEFS_ROOT_INO, &root_hash_info,
783 bch_notice(c, "creating lost+found");
784 goto create_lostfound;
787 ret = bch2_inode_find_by_inum(c, inum, lostfound_inode);
788 if (ret && ret != -ENOENT)
791 if (fsck_err_on(ret, c, "lost+found missing"))
792 goto create_lostfound;
794 if (fsck_err_on(!S_ISDIR(lostfound_inode->bi_mode), c,
795 "lost+found inode not a directory"))
796 goto create_lostfound;
802 bch2_inode_init_early(c, lostfound_inode);
804 ret = bch2_trans_do(c, NULL, NULL,
806 BTREE_INSERT_LAZY_RW,
807 bch2_create_trans(&trans,
808 BCACHEFS_ROOT_INO, root_inode,
809 lostfound_inode, &lostfound,
810 0, 0, S_IFDIR|0700, 0, NULL, NULL));
812 bch_err(c, "error creating lost+found: %i", ret);
817 struct inode_bitmap {
822 static inline bool inode_bitmap_test(struct inode_bitmap *b, size_t nr)
824 return nr < b->size ? test_bit(nr, b->bits) : false;
827 static inline int inode_bitmap_set(struct inode_bitmap *b, size_t nr)
830 size_t new_size = max_t(size_t, max_t(size_t,
836 new_size = roundup_pow_of_two(new_size);
837 n = krealloc(b->bits, new_size / 8, GFP_KERNEL|__GFP_ZERO);
846 __set_bit(nr, b->bits);
854 struct pathbuf_entry {
860 static int path_down(struct pathbuf *p, u64 inum)
862 if (p->nr == p->size) {
863 size_t new_size = max_t(size_t, 256UL, p->size * 2);
864 void *n = krealloc(p->entries,
865 new_size * sizeof(p->entries[0]),
874 p->entries[p->nr++] = (struct pathbuf_entry) {
882 static int check_directory_structure(struct bch_fs *c,
883 struct bch_inode_unpacked *lostfound_inode)
885 struct inode_bitmap dirs_done = { NULL, 0 };
886 struct pathbuf path = { 0, 0, NULL };
887 struct pathbuf_entry *e;
888 struct btree_trans trans;
889 struct btree_iter *iter;
891 struct bkey_s_c_dirent dirent;
892 bool had_unreachable;
896 bch2_trans_init(&trans, c, BTREE_ITER_MAX, 0);
898 bch_verbose(c, "checking directory structure");
902 had_unreachable = false;
904 ret = inode_bitmap_set(&dirs_done, BCACHEFS_ROOT_INO);
906 bch_err(c, "memory allocation failure in inode_bitmap_set()");
910 ret = path_down(&path, BCACHEFS_ROOT_INO);
916 e = &path.entries[path.nr - 1];
918 if (e->offset == U64_MAX)
921 for_each_btree_key(&trans, iter, BTREE_ID_DIRENTS,
922 POS(e->inum, e->offset + 1), 0, k, ret) {
923 if (k.k->p.inode != e->inum)
926 e->offset = k.k->p.offset;
928 if (k.k->type != KEY_TYPE_dirent)
931 dirent = bkey_s_c_to_dirent(k);
933 if (dirent.v->d_type != DT_DIR)
936 d_inum = le64_to_cpu(dirent.v->d_inum);
938 if (fsck_err_on(inode_bitmap_test(&dirs_done, d_inum), c,
939 "directory %llu has multiple hardlinks",
941 ret = remove_dirent(&trans, dirent);
947 ret = inode_bitmap_set(&dirs_done, d_inum);
949 bch_err(c, "memory allocation failure in inode_bitmap_set()");
953 ret = path_down(&path, d_inum);
958 ret = bch2_trans_iter_free(&trans, iter);
960 bch_err(c, "btree error %i in fsck", ret);
965 ret = bch2_trans_iter_free(&trans, iter) ?: ret;
967 bch_err(c, "btree error %i in fsck", ret);
974 iter = bch2_trans_get_iter(&trans, BTREE_ID_INODES, POS_MIN, 0);
976 for_each_btree_key_continue(iter, 0, k, ret) {
977 if (k.k->type != KEY_TYPE_inode)
980 if (!S_ISDIR(le16_to_cpu(bkey_s_c_to_inode(k).v->bi_mode)))
983 ret = bch2_empty_dir_trans(&trans, k.k->p.inode);
989 if (fsck_err_on(!inode_bitmap_test(&dirs_done, k.k->p.inode), c,
990 "unreachable directory found (inum %llu)",
992 bch2_trans_unlock(&trans);
994 ret = reattach_inode(c, lostfound_inode, k.k->p.inode);
999 had_unreachable = true;
1002 bch2_trans_iter_free(&trans, iter);
1006 if (had_unreachable) {
1007 bch_info(c, "reattached unreachable directories, restarting pass to check for loops");
1008 kfree(dirs_done.bits);
1009 kfree(path.entries);
1010 memset(&dirs_done, 0, sizeof(dirs_done));
1011 memset(&path, 0, sizeof(path));
1016 ret = bch2_trans_exit(&trans) ?: ret;
1017 kfree(dirs_done.bits);
1018 kfree(path.entries);
1027 typedef GENRADIX(struct nlink) nlink_table;
1029 static void inc_link(struct bch_fs *c, nlink_table *links,
1030 u64 range_start, u64 *range_end,
1035 if (inum < range_start || inum >= *range_end)
1038 link = genradix_ptr_alloc(links, inum - range_start, GFP_KERNEL);
1040 bch_verbose(c, "allocation failed during fsck - will need another pass");
1052 static int bch2_gc_walk_dirents(struct bch_fs *c, nlink_table *links,
1053 u64 range_start, u64 *range_end)
1055 struct btree_trans trans;
1056 struct btree_iter *iter;
1058 struct bkey_s_c_dirent d;
1062 bch2_trans_init(&trans, c, BTREE_ITER_MAX, 0);
1064 inc_link(c, links, range_start, range_end, BCACHEFS_ROOT_INO, false);
1066 for_each_btree_key(&trans, iter, BTREE_ID_DIRENTS, POS_MIN, 0, k, ret) {
1067 switch (k.k->type) {
1068 case KEY_TYPE_dirent:
1069 d = bkey_s_c_to_dirent(k);
1070 d_inum = le64_to_cpu(d.v->d_inum);
1072 if (d.v->d_type == DT_DIR)
1073 inc_link(c, links, range_start, range_end,
1074 d.k->p.inode, true);
1076 inc_link(c, links, range_start, range_end,
1082 bch2_trans_cond_resched(&trans);
1084 ret = bch2_trans_exit(&trans) ?: ret;
1086 bch_err(c, "error in fsck: btree error %i while walking dirents", ret);
1091 static int check_inode_nlink(struct bch_fs *c,
1092 struct bch_inode_unpacked *lostfound_inode,
1093 struct bch_inode_unpacked *u,
1097 u32 i_nlink = bch2_inode_nlink_get(u);
1099 link->count * nlink_bias(u->bi_mode) +
1104 * These should have been caught/fixed by earlier passes, we don't
1107 if (S_ISDIR(u->bi_mode) && link->count > 1) {
1108 need_fsck_err(c, "directory %llu with multiple hardlinks: %u",
1109 u->bi_inum, link->count);
1113 if (S_ISDIR(u->bi_mode) && !link->count) {
1114 need_fsck_err(c, "unreachable directory found (inum %llu)",
1119 if (!S_ISDIR(u->bi_mode) && link->dir_count) {
1120 need_fsck_err(c, "non directory with subdirectories",
1126 !(u->bi_flags & BCH_INODE_UNLINKED) &&
1127 (c->sb.features & (1 << BCH_FEATURE_ATOMIC_NLINK))) {
1128 if (fsck_err(c, "unreachable inode %llu not marked as unlinked (type %u)",
1129 u->bi_inum, mode_to_type(u->bi_mode)) ==
1133 ret = reattach_inode(c, lostfound_inode, u->bi_inum);
1138 real_i_nlink = nlink_bias(u->bi_mode) + link->dir_count;
1142 if (i_nlink < link->count) {
1143 if (fsck_err(c, "inode %llu i_link too small (%u < %u, type %i)",
1144 u->bi_inum, i_nlink, link->count,
1145 mode_to_type(u->bi_mode)) == FSCK_ERR_IGNORE)
1150 if (i_nlink != real_i_nlink &&
1152 if (fsck_err(c, "filesystem marked clean, "
1153 "but inode %llu has wrong i_nlink "
1154 "(type %u i_nlink %u, should be %u)",
1155 u->bi_inum, mode_to_type(u->bi_mode),
1156 i_nlink, real_i_nlink) == FSCK_ERR_IGNORE)
1161 if (i_nlink != real_i_nlink &&
1162 (c->sb.features & (1 << BCH_FEATURE_ATOMIC_NLINK))) {
1163 if (fsck_err(c, "inode %llu has wrong i_nlink "
1164 "(type %u i_nlink %u, should be %u)",
1165 u->bi_inum, mode_to_type(u->bi_mode),
1166 i_nlink, real_i_nlink) == FSCK_ERR_IGNORE)
1171 if (real_i_nlink && i_nlink != real_i_nlink)
1172 bch_verbose(c, "setting inode %llu nlink from %u to %u",
1173 u->bi_inum, i_nlink, real_i_nlink);
1175 if (i_nlink != real_i_nlink) {
1176 bch2_inode_nlink_set(u, real_i_nlink);
1183 static int check_inode(struct btree_trans *trans,
1184 struct bch_inode_unpacked *lostfound_inode,
1185 struct btree_iter *iter,
1186 struct bkey_s_c_inode inode,
1189 struct bch_fs *c = trans->c;
1190 struct bch_inode_unpacked u;
1191 bool do_update = false;
1194 ret = bch2_inode_unpack(inode, &u);
1196 bch2_trans_unlock(trans);
1198 if (bch2_fs_inconsistent_on(ret, c,
1199 "error unpacking inode %llu in fsck",
1204 ret = check_inode_nlink(c, lostfound_inode, &u, link,
1210 if (u.bi_flags & BCH_INODE_UNLINKED &&
1212 fsck_err(c, "filesystem marked clean, but inode %llu unlinked",
1214 bch_verbose(c, "deleting inode %llu", u.bi_inum);
1216 ret = bch2_inode_rm(c, u.bi_inum);
1218 bch_err(c, "error in fsck: error %i while deleting inode", ret);
1222 if (u.bi_flags & BCH_INODE_I_SIZE_DIRTY &&
1224 fsck_err(c, "filesystem marked clean, but inode %llu has i_size dirty",
1226 bch_verbose(c, "truncating inode %llu", u.bi_inum);
1229 * XXX: need to truncate partial blocks too here - or ideally
1230 * just switch units to bytes and that issue goes away
1233 ret = bch2_inode_truncate(c, u.bi_inum, u.bi_size);
1235 bch_err(c, "error in fsck: error %i truncating inode", ret);
1240 * We truncated without our normal sector accounting hook, just
1241 * make sure we recalculate it:
1243 u.bi_flags |= BCH_INODE_I_SECTORS_DIRTY;
1245 u.bi_flags &= ~BCH_INODE_I_SIZE_DIRTY;
1249 if (u.bi_flags & BCH_INODE_I_SECTORS_DIRTY &&
1251 fsck_err(c, "filesystem marked clean, but inode %llu has i_sectors dirty",
1255 bch_verbose(c, "recounting sectors for inode %llu",
1258 sectors = bch2_count_inode_sectors(trans, u.bi_inum);
1260 bch_err(c, "error in fsck: error %i recounting inode sectors",
1265 u.bi_sectors = sectors;
1266 u.bi_flags &= ~BCH_INODE_I_SECTORS_DIRTY;
1271 struct bkey_inode_buf p;
1273 bch2_inode_pack(&p, &u);
1275 ret = __bch2_trans_do(trans, NULL, NULL,
1276 BTREE_INSERT_NOFAIL|
1277 BTREE_INSERT_LAZY_RW,
1279 (bch2_trans_update(trans, iter, &p.inode.k_i), 0));
1281 bch_err(c, "error in fsck: error %i "
1282 "updating inode", ret);
1289 static int bch2_gc_walk_inodes(struct bch_fs *c,
1290 struct bch_inode_unpacked *lostfound_inode,
1292 u64 range_start, u64 range_end)
1294 struct btree_trans trans;
1295 struct btree_iter *iter;
1297 struct nlink *link, zero_links = { 0, 0 };
1298 struct genradix_iter nlinks_iter;
1299 int ret = 0, ret2 = 0;
1302 bch2_trans_init(&trans, c, BTREE_ITER_MAX, 0);
1304 iter = bch2_trans_get_iter(&trans, BTREE_ID_INODES,
1305 POS(range_start, 0), 0);
1306 nlinks_iter = genradix_iter_init(links, 0);
1308 while ((k = bch2_btree_iter_peek(iter)).k &&
1309 !(ret2 = bkey_err(k))) {
1310 peek_nlinks: link = genradix_iter_peek(&nlinks_iter, links);
1312 if (!link && (!k.k || iter->pos.inode >= range_end))
1315 nlinks_pos = range_start + nlinks_iter.pos;
1316 if (iter->pos.inode > nlinks_pos) {
1317 /* Should have been caught by dirents pass: */
1318 need_fsck_err_on(link && link->count, c,
1319 "missing inode %llu (nlink %u)",
1320 nlinks_pos, link->count);
1321 genradix_iter_advance(&nlinks_iter, links);
1325 if (iter->pos.inode < nlinks_pos || !link)
1328 if (k.k && k.k->type == KEY_TYPE_inode) {
1329 ret = check_inode(&trans, lostfound_inode, iter,
1330 bkey_s_c_to_inode(k), link);
1331 BUG_ON(ret == -EINTR);
1335 /* Should have been caught by dirents pass: */
1336 need_fsck_err_on(link->count, c,
1337 "missing inode %llu (nlink %u)",
1338 nlinks_pos, link->count);
1341 if (nlinks_pos == iter->pos.inode)
1342 genradix_iter_advance(&nlinks_iter, links);
1344 bch2_btree_iter_next(iter);
1345 bch2_trans_cond_resched(&trans);
1348 bch2_trans_exit(&trans);
1351 bch_err(c, "error in fsck: btree error %i while walking inodes", ret2);
1357 static int check_inode_nlinks(struct bch_fs *c,
1358 struct bch_inode_unpacked *lostfound_inode)
1361 u64 this_iter_range_start, next_iter_range_start = 0;
1364 bch_verbose(c, "checking inode nlinks");
1366 genradix_init(&links);
1369 this_iter_range_start = next_iter_range_start;
1370 next_iter_range_start = U64_MAX;
1372 ret = bch2_gc_walk_dirents(c, &links,
1373 this_iter_range_start,
1374 &next_iter_range_start);
1378 ret = bch2_gc_walk_inodes(c, lostfound_inode, &links,
1379 this_iter_range_start,
1380 next_iter_range_start);
1384 genradix_free(&links);
1385 } while (next_iter_range_start != U64_MAX);
1387 genradix_free(&links);
1393 * Checks for inconsistencies that shouldn't happen, unless we have a bug.
1394 * Doesn't fix them yet, mainly because they haven't yet been observed:
1396 int bch2_fsck_full(struct bch_fs *c)
1398 struct bch_inode_unpacked root_inode, lostfound_inode;
1400 return check_extents(c) ?:
1403 check_root(c, &root_inode) ?:
1404 check_lostfound(c, &root_inode, &lostfound_inode) ?:
1405 check_directory_structure(c, &lostfound_inode) ?:
1406 check_inode_nlinks(c, &lostfound_inode);
1409 int bch2_fsck_inode_nlink(struct bch_fs *c)
1411 struct bch_inode_unpacked root_inode, lostfound_inode;
1413 return check_root(c, &root_inode) ?:
1414 check_lostfound(c, &root_inode, &lostfound_inode) ?:
1415 check_inode_nlinks(c, &lostfound_inode);
1418 int bch2_fsck_walk_inodes_only(struct bch_fs *c)
1420 struct btree_trans trans;
1421 struct btree_iter *iter;
1423 struct bkey_s_c_inode inode;
1426 bch2_trans_init(&trans, c, BTREE_ITER_MAX, 0);
1428 for_each_btree_key(&trans, iter, BTREE_ID_INODES, POS_MIN, 0, k, ret) {
1429 if (k.k->type != KEY_TYPE_inode)
1432 inode = bkey_s_c_to_inode(k);
1434 if (inode.v->bi_flags &
1435 (BCH_INODE_I_SIZE_DIRTY|
1436 BCH_INODE_I_SECTORS_DIRTY|
1437 BCH_INODE_UNLINKED)) {
1438 ret = check_inode(&trans, NULL, iter, inode, NULL);
1439 BUG_ON(ret == -EINTR);
1444 BUG_ON(ret == -EINTR);
1446 return bch2_trans_exit(&trans) ?: ret;