3 #include "btree_update.h"
13 #include <linux/dcache.h> /* struct qstr */
14 #include <linux/generic-radix-tree.h>
16 #define QSTR(n) { { { .len = strlen(n) } }, .name = n }
18 static int remove_dirent(struct bch_fs *c, struct btree_iter *iter,
19 struct bkey_s_c_dirent dirent)
22 struct bch_inode_unpacked dir_inode;
23 struct bch_hash_info dir_hash_info;
24 u64 dir_inum = dirent.k->p.inode;
28 name.len = bch2_dirent_name_bytes(dirent);
29 buf = kmalloc(name.len + 1, GFP_KERNEL);
33 memcpy(buf, dirent.v->d_name, name.len);
37 /* Unlock iter so we don't deadlock, after copying name: */
38 bch2_btree_iter_unlock(iter);
40 ret = bch2_inode_find_by_inum(c, dir_inum, &dir_inode);
42 bch_err(c, "remove_dirent: err %i looking up directory inode", ret);
46 dir_hash_info = bch2_hash_info_init(c, &dir_inode);
48 ret = bch2_dirent_delete(c, dir_inum, &dir_hash_info, &name, NULL);
50 bch_err(c, "remove_dirent: err %i deleting dirent", ret);
56 static int reattach_inode(struct bch_fs *c,
57 struct bch_inode_unpacked *lostfound_inode,
60 struct bch_hash_info lostfound_hash_info =
61 bch2_hash_info_init(c, lostfound_inode);
62 struct bkey_inode_buf packed;
67 snprintf(name_buf, sizeof(name_buf), "%llu", inum);
68 name = (struct qstr) QSTR(name_buf);
70 lostfound_inode->bi_nlink++;
72 bch2_inode_pack(&packed, lostfound_inode);
74 ret = bch2_btree_insert(c, BTREE_ID_INODES, &packed.inode.k_i,
75 NULL, NULL, BTREE_INSERT_NOFAIL);
77 bch_err(c, "error %i reattaching inode %llu while updating lost+found",
82 ret = bch2_dirent_create(c, lostfound_inode->bi_inum,
84 DT_DIR, &name, inum, NULL,
87 bch_err(c, "error %i reattaching inode %llu while creating new dirent",
95 bool first_this_inode;
98 struct bch_inode_unpacked inode;
101 static struct inode_walker inode_walker_init(void)
103 return (struct inode_walker) {
109 static int walk_inode(struct bch_fs *c, struct inode_walker *w, u64 inum)
111 w->first_this_inode = inum != w->cur_inum;
114 if (w->first_this_inode) {
115 int ret = bch2_inode_find_by_inum(c, inum, &w->inode);
117 if (ret && ret != -ENOENT)
120 w->have_inode = !ret;
127 struct bch_hash_info info;
128 struct btree_trans *trans;
130 /* start of current chain of hash collisions: */
131 struct btree_iter *chain;
133 /* next offset in current chain of hash collisions: */
137 static void hash_check_init(const struct bch_hash_desc desc,
138 struct btree_trans *trans,
139 struct hash_check *h)
142 h->chain = bch2_trans_get_iter(trans, desc.btree_id, POS_MIN, 0);
146 static void hash_check_set_inode(struct hash_check *h, struct bch_fs *c,
147 const struct bch_inode_unpacked *bi)
149 h->info = bch2_hash_info_init(c, bi);
153 static int hash_redo_key(const struct bch_hash_desc desc,
154 struct hash_check *h, struct bch_fs *c,
155 struct btree_iter *k_iter, struct bkey_s_c k,
161 tmp = kmalloc(bkey_bytes(k.k), GFP_KERNEL);
165 bkey_reassemble(tmp, k);
167 ret = bch2_btree_delete_at(k_iter, 0);
171 bch2_btree_iter_unlock(k_iter);
173 bch2_hash_set(desc, &h->info, c, k_iter->pos.inode, NULL, tmp,
175 BCH_HASH_SET_MUST_CREATE);
181 /* fsck hasn't been converted to new transactions yet: */
182 static int fsck_hash_delete_at(const struct bch_hash_desc desc,
183 struct bch_hash_info *info,
184 struct btree_iter *orig_iter)
186 struct btree_trans trans;
187 struct btree_iter *iter;
190 bch2_btree_iter_unlock(orig_iter);
192 bch2_trans_init(&trans, orig_iter->c);
194 bch2_trans_begin(&trans);
196 iter = bch2_trans_copy_iter(&trans, orig_iter);
202 ret = bch2_hash_delete_at(&trans, desc, info, iter) ?:
203 bch2_trans_commit(&trans, NULL, NULL,
205 BTREE_INSERT_NOFAIL);
210 bch2_trans_exit(&trans);
214 static int hash_check_duplicates(const struct bch_hash_desc desc,
215 struct hash_check *h, struct bch_fs *c,
216 struct btree_iter *k_iter, struct bkey_s_c k)
218 struct btree_iter *iter;
223 if (!bkey_cmp(h->chain->pos, k_iter->pos))
226 iter = bch2_trans_copy_iter(h->trans, h->chain);
227 BUG_ON(IS_ERR(iter));
229 for_each_btree_key_continue(iter, 0, k2) {
230 if (bkey_cmp(k2.k->p, k.k->p) >= 0)
233 if (fsck_err_on(k2.k->type == desc.key_type &&
234 !desc.cmp_bkey(k, k2), c,
235 "duplicate hash table keys:\n%s",
236 (bch2_bkey_val_to_text(&PBUF(buf), c,
237 bkey_type(0, desc.btree_id),
239 ret = fsck_hash_delete_at(desc, &h->info, k_iter);
247 bch2_trans_iter_free(h->trans, iter);
251 static bool key_has_correct_hash(const struct bch_hash_desc desc,
252 struct hash_check *h, struct bch_fs *c,
253 struct btree_iter *k_iter, struct bkey_s_c k)
257 if (k.k->type != desc.whiteout_type &&
258 k.k->type != desc.key_type)
261 if (k.k->p.offset != h->next)
262 bch2_btree_iter_copy(h->chain, k_iter);
263 h->next = k.k->p.offset + 1;
265 if (k.k->type != desc.key_type)
268 hash = desc.hash_bkey(&h->info, k);
270 return hash >= h->chain->pos.offset &&
271 hash <= k.k->p.offset;
274 static int hash_check_key(const struct bch_hash_desc desc,
275 struct hash_check *h, struct bch_fs *c,
276 struct btree_iter *k_iter, struct bkey_s_c k)
282 if (k.k->type != desc.whiteout_type &&
283 k.k->type != desc.key_type)
286 if (k.k->p.offset != h->next)
287 bch2_btree_iter_copy(h->chain, k_iter);
288 h->next = k.k->p.offset + 1;
290 if (k.k->type != desc.key_type)
293 hashed = desc.hash_bkey(&h->info, k);
295 if (fsck_err_on(hashed < h->chain->pos.offset ||
296 hashed > k.k->p.offset, c,
297 "hash table key at wrong offset: btree %u, %llu, "
298 "hashed to %llu chain starts at %llu\n%s",
299 desc.btree_id, k.k->p.offset,
300 hashed, h->chain->pos.offset,
301 (bch2_bkey_val_to_text(&PBUF(buf), c,
302 bkey_type(0, desc.btree_id),
304 ret = hash_redo_key(desc, h, c, k_iter, k, hashed);
306 bch_err(c, "hash_redo_key err %i", ret);
312 ret = hash_check_duplicates(desc, h, c, k_iter, k);
317 static int check_dirent_hash(struct hash_check *h, struct bch_fs *c,
318 struct btree_iter *iter, struct bkey_s_c *k)
320 struct bkey_i_dirent *d = NULL;
326 if (key_has_correct_hash(bch2_dirent_hash_desc, h, c, iter, *k))
329 len = bch2_dirent_name_bytes(bkey_s_c_to_dirent(*k));
332 memcpy(buf, bkey_s_c_to_dirent(*k).v->d_name, len);
335 d = kmalloc(bkey_bytes(k->k), GFP_KERNEL);
337 bch_err(c, "memory allocation failure");
341 bkey_reassemble(&d->k_i, *k);
348 d->k.u64s = BKEY_U64s + dirent_val_u64s(len);
350 BUG_ON(bkey_val_bytes(&d->k) <
351 offsetof(struct bch_dirent, d_name) + len);
353 memset(d->v.d_name + len, 0,
354 bkey_val_bytes(&d->k) -
355 offsetof(struct bch_dirent, d_name) - len);
357 hash = bch2_dirent_hash_desc.hash_bkey(&h->info,
358 bkey_i_to_s_c(&d->k_i));
359 } while (hash < h->chain->pos.offset ||
360 hash > k->k->p.offset);
362 if (fsck_err(c, "dirent with junk at end, was %s (%zu) now %s (%u)",
363 buf, strlen(buf), d->v.d_name, len)) {
364 ret = bch2_btree_insert_at(c, NULL, NULL,
366 BTREE_INSERT_ENTRY(iter, &d->k_i));
370 *k = bch2_btree_iter_peek(iter);
372 BUG_ON(k->k->type != BCH_DIRENT);
379 hash = bch2_dirent_hash_desc.hash_bkey(&h->info, *k);
381 if (fsck_err(c, "cannot fix dirent by removing trailing garbage %s (%zu)\n"
382 "hash table key at wrong offset: btree %u, offset %llu, "
383 "hashed to %llu chain starts at %llu\n%s",
384 buf, strlen(buf), BTREE_ID_DIRENTS,
385 k->k->p.offset, hash, h->chain->pos.offset,
386 (bch2_bkey_val_to_text(&PBUF(buf), c,
387 bkey_type(0, BTREE_ID_DIRENTS),
389 ret = hash_redo_key(bch2_dirent_hash_desc,
390 h, c, iter, *k, hash);
392 bch_err(c, "hash_redo_key err %i", ret);
400 static int bch2_inode_truncate(struct bch_fs *c, u64 inode_nr, u64 new_size)
402 return bch2_btree_delete_range(c, BTREE_ID_EXTENTS,
403 POS(inode_nr, round_up(new_size, block_bytes(c)) >> 9),
404 POS(inode_nr + 1, 0), NULL);
408 * Walk extents: verify that extents have a corresponding S_ISREG inode, and
409 * that i_size an i_sectors are consistent
412 static int check_extents(struct bch_fs *c)
414 struct inode_walker w = inode_walker_init();
415 struct btree_iter iter;
420 bch_verbose(c, "checking extents");
422 for_each_btree_key(&iter, c, BTREE_ID_EXTENTS,
423 POS(BCACHEFS_ROOT_INO, 0), 0, k) {
424 ret = walk_inode(c, &w, k.k->p.inode);
428 if (fsck_err_on(!w.have_inode, c,
429 "extent type %u for missing inode %llu",
430 k.k->type, k.k->p.inode) ||
431 fsck_err_on(w.have_inode &&
432 !S_ISREG(w.inode.bi_mode) && !S_ISLNK(w.inode.bi_mode), c,
433 "extent type %u for non regular file, inode %llu mode %o",
434 k.k->type, k.k->p.inode, w.inode.bi_mode)) {
435 bch2_btree_iter_unlock(&iter);
437 ret = bch2_inode_truncate(c, k.k->p.inode, 0);
443 if (fsck_err_on(w.first_this_inode &&
445 !(w.inode.bi_flags & BCH_INODE_I_SECTORS_DIRTY) &&
446 w.inode.bi_sectors !=
447 (i_sectors = bch2_count_inode_sectors(c, w.cur_inum)),
448 c, "i_sectors wrong: got %llu, should be %llu",
449 w.inode.bi_sectors, i_sectors)) {
450 struct bkey_inode_buf p;
452 w.inode.bi_sectors = i_sectors;
454 bch2_btree_iter_unlock(&iter);
456 bch2_inode_pack(&p, &w.inode);
458 ret = bch2_btree_insert(c, BTREE_ID_INODES,
459 &p.inode.k_i, NULL, NULL,
460 BTREE_INSERT_NOFAIL);
462 bch_err(c, "error in fs gc: error %i "
463 "updating inode", ret);
467 /* revalidate iterator: */
468 k = bch2_btree_iter_peek(&iter);
471 if (fsck_err_on(w.have_inode &&
472 !(w.inode.bi_flags & BCH_INODE_I_SIZE_DIRTY) &&
473 k.k->type != BCH_RESERVATION &&
474 k.k->p.offset > round_up(w.inode.bi_size, PAGE_SIZE) >> 9, c,
475 "extent type %u offset %llu past end of inode %llu, i_size %llu",
476 k.k->type, k.k->p.offset, k.k->p.inode, w.inode.bi_size)) {
477 bch2_btree_iter_unlock(&iter);
479 ret = bch2_inode_truncate(c, k.k->p.inode,
488 return bch2_btree_iter_unlock(&iter) ?: ret;
492 * Walk dirents: verify that they all have a corresponding S_ISDIR inode,
496 static int check_dirents(struct bch_fs *c)
498 struct inode_walker w = inode_walker_init();
500 struct btree_trans trans;
501 struct btree_iter *iter;
507 bch_verbose(c, "checking dirents");
509 bch2_trans_init(&trans, c);
511 bch2_trans_preload_iters(&trans);
513 iter = bch2_trans_get_iter(&trans, BTREE_ID_DIRENTS,
514 POS(BCACHEFS_ROOT_INO, 0), 0);
516 hash_check_init(bch2_dirent_hash_desc, &trans, &h);
518 for_each_btree_key_continue(iter, 0, k) {
519 struct bkey_s_c_dirent d;
520 struct bch_inode_unpacked target;
524 ret = walk_inode(c, &w, k.k->p.inode);
528 if (fsck_err_on(!w.have_inode, c,
529 "dirent in nonexisting directory:\n%s",
530 (bch2_bkey_val_to_text(&PBUF(buf), c,
533 fsck_err_on(!S_ISDIR(w.inode.bi_mode), c,
534 "dirent in non directory inode type %u:\n%s",
535 mode_to_type(w.inode.bi_mode),
536 (bch2_bkey_val_to_text(&PBUF(buf), c,
539 ret = bch2_btree_delete_at(iter, 0);
545 if (w.first_this_inode && w.have_inode)
546 hash_check_set_inode(&h, c, &w.inode);
548 ret = check_dirent_hash(&h, c, iter, &k);
559 if (k.k->type != BCH_DIRENT)
562 d = bkey_s_c_to_dirent(k);
563 d_inum = le64_to_cpu(d.v->d_inum);
565 name_len = bch2_dirent_name_bytes(d);
567 if (fsck_err_on(!name_len, c, "empty dirent") ||
568 fsck_err_on(name_len == 1 &&
569 !memcmp(d.v->d_name, ".", 1), c,
571 fsck_err_on(name_len == 2 &&
572 !memcmp(d.v->d_name, "..", 2), c,
574 fsck_err_on(name_len == 2 &&
575 !memcmp(d.v->d_name, "..", 2), c,
577 fsck_err_on(memchr(d.v->d_name, '/', name_len), c,
578 "dirent name has invalid chars")) {
579 ret = remove_dirent(c, iter, d);
585 if (fsck_err_on(d_inum == d.k->p.inode, c,
586 "dirent points to own directory:\n%s",
587 (bch2_bkey_val_to_text(&PBUF(buf), c,
590 ret = remove_dirent(c, iter, d);
596 ret = bch2_inode_find_by_inum(c, d_inum, &target);
597 if (ret && ret != -ENOENT)
603 if (fsck_err_on(!have_target, c,
604 "dirent points to missing inode:\n%s",
605 (bch2_bkey_val_to_text(&PBUF(buf), c,
608 ret = remove_dirent(c, iter, d);
614 if (fsck_err_on(have_target &&
616 mode_to_type(target.bi_mode), c,
617 "incorrect d_type: should be %u:\n%s",
618 mode_to_type(target.bi_mode),
619 (bch2_bkey_val_to_text(&PBUF(buf), c,
622 struct bkey_i_dirent *n;
624 n = kmalloc(bkey_bytes(d.k), GFP_KERNEL);
630 bkey_reassemble(&n->k_i, d.s_c);
631 n->v.d_type = mode_to_type(target.bi_mode);
633 ret = bch2_btree_insert_at(c, NULL, NULL,
635 BTREE_INSERT_ENTRY(iter, &n->k_i));
644 return bch2_trans_exit(&trans) ?: ret;
648 * Walk xattrs: verify that they all have a corresponding inode
651 static int check_xattrs(struct bch_fs *c)
653 struct inode_walker w = inode_walker_init();
655 struct btree_trans trans;
656 struct btree_iter *iter;
660 bch_verbose(c, "checking xattrs");
662 bch2_trans_init(&trans, c);
664 bch2_trans_preload_iters(&trans);
666 iter = bch2_trans_get_iter(&trans, BTREE_ID_XATTRS,
667 POS(BCACHEFS_ROOT_INO, 0), 0);
669 hash_check_init(bch2_xattr_hash_desc, &trans, &h);
671 for_each_btree_key_continue(iter, 0, k) {
672 ret = walk_inode(c, &w, k.k->p.inode);
676 if (fsck_err_on(!w.have_inode, c,
677 "xattr for missing inode %llu",
679 ret = bch2_btree_delete_at(iter, 0);
685 if (w.first_this_inode && w.have_inode)
686 hash_check_set_inode(&h, c, &w.inode);
688 ret = hash_check_key(bch2_xattr_hash_desc, &h, c, iter, k);
694 return bch2_trans_exit(&trans) ?: ret;
697 /* Get root directory, create if it doesn't exist: */
698 static int check_root(struct bch_fs *c, struct bch_inode_unpacked *root_inode)
700 struct bkey_inode_buf packed;
703 bch_verbose(c, "checking root directory");
705 ret = bch2_inode_find_by_inum(c, BCACHEFS_ROOT_INO, root_inode);
706 if (ret && ret != -ENOENT)
709 if (fsck_err_on(ret, c, "root directory missing"))
712 if (fsck_err_on(!S_ISDIR(root_inode->bi_mode), c,
713 "root inode not a directory"))
720 bch2_inode_init(c, root_inode, 0, 0, S_IFDIR|S_IRWXU|S_IRUGO|S_IXUGO,
722 root_inode->bi_inum = BCACHEFS_ROOT_INO;
724 bch2_inode_pack(&packed, root_inode);
726 return bch2_btree_insert(c, BTREE_ID_INODES, &packed.inode.k_i,
727 NULL, NULL, BTREE_INSERT_NOFAIL);
730 /* Get lost+found, create if it doesn't exist: */
731 static int check_lostfound(struct bch_fs *c,
732 struct bch_inode_unpacked *root_inode,
733 struct bch_inode_unpacked *lostfound_inode)
735 struct qstr lostfound = QSTR("lost+found");
736 struct bch_hash_info root_hash_info =
737 bch2_hash_info_init(c, root_inode);
738 struct bkey_inode_buf packed;
742 bch_verbose(c, "checking lost+found");
744 inum = bch2_dirent_lookup(c, BCACHEFS_ROOT_INO, &root_hash_info,
747 bch_notice(c, "creating lost+found");
748 goto create_lostfound;
751 ret = bch2_inode_find_by_inum(c, inum, lostfound_inode);
752 if (ret && ret != -ENOENT)
755 if (fsck_err_on(ret, c, "lost+found missing"))
756 goto create_lostfound;
758 if (fsck_err_on(!S_ISDIR(lostfound_inode->bi_mode), c,
759 "lost+found inode not a directory"))
760 goto create_lostfound;
766 root_inode->bi_nlink++;
768 bch2_inode_pack(&packed, root_inode);
770 ret = bch2_btree_insert(c, BTREE_ID_INODES, &packed.inode.k_i,
771 NULL, NULL, BTREE_INSERT_NOFAIL);
775 bch2_inode_init(c, lostfound_inode, 0, 0, S_IFDIR|S_IRWXU|S_IRUGO|S_IXUGO,
778 ret = bch2_inode_create(c, lostfound_inode, BLOCKDEV_INODE_MAX, 0,
779 &c->unused_inode_hint);
783 ret = bch2_dirent_create(c, BCACHEFS_ROOT_INO, &root_hash_info, DT_DIR,
784 &lostfound, lostfound_inode->bi_inum, NULL,
785 BTREE_INSERT_NOFAIL);
792 struct inode_bitmap {
797 static inline bool inode_bitmap_test(struct inode_bitmap *b, size_t nr)
799 return nr < b->size ? test_bit(nr, b->bits) : false;
802 static inline int inode_bitmap_set(struct inode_bitmap *b, size_t nr)
805 size_t new_size = max_t(size_t, max_t(size_t,
811 new_size = roundup_pow_of_two(new_size);
812 n = krealloc(b->bits, new_size / 8, GFP_KERNEL|__GFP_ZERO);
821 __set_bit(nr, b->bits);
829 struct pathbuf_entry {
835 static int path_down(struct pathbuf *p, u64 inum)
837 if (p->nr == p->size) {
838 size_t new_size = max_t(size_t, 256UL, p->size * 2);
839 void *n = krealloc(p->entries,
840 new_size * sizeof(p->entries[0]),
849 p->entries[p->nr++] = (struct pathbuf_entry) {
857 static int check_directory_structure(struct bch_fs *c,
858 struct bch_inode_unpacked *lostfound_inode)
860 struct inode_bitmap dirs_done = { NULL, 0 };
861 struct pathbuf path = { 0, 0, NULL };
862 struct pathbuf_entry *e;
863 struct btree_iter iter;
865 struct bkey_s_c_dirent dirent;
866 bool had_unreachable;
870 bch_verbose(c, "checking directory structure");
874 had_unreachable = false;
876 ret = inode_bitmap_set(&dirs_done, BCACHEFS_ROOT_INO);
878 bch_err(c, "memory allocation failure in inode_bitmap_set()");
882 ret = path_down(&path, BCACHEFS_ROOT_INO);
889 e = &path.entries[path.nr - 1];
891 if (e->offset == U64_MAX)
894 for_each_btree_key(&iter, c, BTREE_ID_DIRENTS,
895 POS(e->inum, e->offset + 1), 0, k) {
896 if (k.k->p.inode != e->inum)
899 e->offset = k.k->p.offset;
901 if (k.k->type != BCH_DIRENT)
904 dirent = bkey_s_c_to_dirent(k);
906 if (dirent.v->d_type != DT_DIR)
909 d_inum = le64_to_cpu(dirent.v->d_inum);
911 if (fsck_err_on(inode_bitmap_test(&dirs_done, d_inum), c,
912 "directory %llu has multiple hardlinks",
914 ret = remove_dirent(c, &iter, dirent);
920 ret = inode_bitmap_set(&dirs_done, d_inum);
922 bch_err(c, "memory allocation failure in inode_bitmap_set()");
926 ret = path_down(&path, d_inum);
931 bch2_btree_iter_unlock(&iter);
934 ret = bch2_btree_iter_unlock(&iter);
936 bch_err(c, "btree error %i in fsck", ret);
943 for_each_btree_key(&iter, c, BTREE_ID_INODES, POS_MIN, 0, k) {
944 if (k.k->type != BCH_INODE_FS)
947 if (!S_ISDIR(le16_to_cpu(bkey_s_c_to_inode(k).v->bi_mode)))
950 if (!bch2_empty_dir(c, k.k->p.inode))
953 if (fsck_err_on(!inode_bitmap_test(&dirs_done, k.k->p.inode), c,
954 "unreachable directory found (inum %llu)",
956 bch2_btree_iter_unlock(&iter);
958 ret = reattach_inode(c, lostfound_inode, k.k->p.inode);
963 had_unreachable = true;
966 ret = bch2_btree_iter_unlock(&iter);
970 if (had_unreachable) {
971 bch_info(c, "reattached unreachable directories, restarting pass to check for loops");
972 kfree(dirs_done.bits);
974 memset(&dirs_done, 0, sizeof(dirs_done));
975 memset(&path, 0, sizeof(path));
980 kfree(dirs_done.bits);
985 ret = bch2_btree_iter_unlock(&iter) ?: ret;
994 typedef GENRADIX(struct nlink) nlink_table;
996 static void inc_link(struct bch_fs *c, nlink_table *links,
997 u64 range_start, u64 *range_end,
1002 if (inum < range_start || inum >= *range_end)
1005 link = genradix_ptr_alloc(links, inum - range_start, GFP_KERNEL);
1007 bch_verbose(c, "allocation failed during fs gc - will need another pass");
1019 static int bch2_gc_walk_dirents(struct bch_fs *c, nlink_table *links,
1020 u64 range_start, u64 *range_end)
1022 struct btree_iter iter;
1024 struct bkey_s_c_dirent d;
1028 inc_link(c, links, range_start, range_end, BCACHEFS_ROOT_INO, false);
1030 for_each_btree_key(&iter, c, BTREE_ID_DIRENTS, POS_MIN, 0, k) {
1031 switch (k.k->type) {
1033 d = bkey_s_c_to_dirent(k);
1034 d_inum = le64_to_cpu(d.v->d_inum);
1036 if (d.v->d_type == DT_DIR)
1037 inc_link(c, links, range_start, range_end,
1038 d.k->p.inode, true);
1040 inc_link(c, links, range_start, range_end,
1046 bch2_btree_iter_cond_resched(&iter);
1048 ret = bch2_btree_iter_unlock(&iter);
1050 bch_err(c, "error in fs gc: btree error %i while walking dirents", ret);
1055 s64 bch2_count_inode_sectors(struct bch_fs *c, u64 inum)
1057 struct btree_iter iter;
1061 for_each_btree_key(&iter, c, BTREE_ID_EXTENTS, POS(inum, 0), 0, k) {
1062 if (k.k->p.inode != inum)
1065 if (bkey_extent_is_allocation(k.k))
1066 sectors += k.k->size;
1069 return bch2_btree_iter_unlock(&iter) ?: sectors;
1072 static int check_inode_nlink(struct bch_fs *c,
1073 struct bch_inode_unpacked *lostfound_inode,
1074 struct bch_inode_unpacked *u,
1078 u32 i_nlink = u->bi_flags & BCH_INODE_UNLINKED
1080 : u->bi_nlink + nlink_bias(u->bi_mode);
1082 link->count * nlink_bias(u->bi_mode) +
1087 * These should have been caught/fixed by earlier passes, we don't
1090 if (S_ISDIR(u->bi_mode) && link->count > 1) {
1091 need_fsck_err(c, "directory %llu with multiple hardlinks: %u",
1092 u->bi_inum, link->count);
1096 if (S_ISDIR(u->bi_mode) && !link->count) {
1097 need_fsck_err(c, "unreachable directory found (inum %llu)",
1102 if (!S_ISDIR(u->bi_mode) && link->dir_count) {
1103 need_fsck_err(c, "non directory with subdirectories",
1109 !(u->bi_flags & BCH_INODE_UNLINKED) &&
1110 (c->sb.features & (1 << BCH_FEATURE_ATOMIC_NLINK))) {
1111 if (fsck_err(c, "unreachable inode %llu not marked as unlinked (type %u)",
1112 u->bi_inum, mode_to_type(u->bi_mode)) ==
1116 ret = reattach_inode(c, lostfound_inode, u->bi_inum);
1121 real_i_nlink = nlink_bias(u->bi_mode) + link->dir_count;
1125 if (i_nlink < link->count) {
1126 if (fsck_err(c, "inode %llu i_link too small (%u < %u, type %i)",
1127 u->bi_inum, i_nlink, link->count,
1128 mode_to_type(u->bi_mode)) == FSCK_ERR_IGNORE)
1133 if (i_nlink != real_i_nlink &&
1135 if (fsck_err(c, "filesystem marked clean, "
1136 "but inode %llu has wrong i_nlink "
1137 "(type %u i_nlink %u, should be %u)",
1138 u->bi_inum, mode_to_type(u->bi_mode),
1139 i_nlink, real_i_nlink) == FSCK_ERR_IGNORE)
1144 if (i_nlink != real_i_nlink &&
1145 (c->sb.features & (1 << BCH_FEATURE_ATOMIC_NLINK))) {
1146 if (fsck_err(c, "inode %llu has wrong i_nlink "
1147 "(type %u i_nlink %u, should be %u)",
1148 u->bi_inum, mode_to_type(u->bi_mode),
1149 i_nlink, real_i_nlink) == FSCK_ERR_IGNORE)
1154 if (real_i_nlink && i_nlink != real_i_nlink)
1155 bch_verbose(c, "setting inode %llu nlink from %u to %u",
1156 u->bi_inum, i_nlink, real_i_nlink);
1158 if (i_nlink != real_i_nlink) {
1160 u->bi_nlink = real_i_nlink - nlink_bias(u->bi_mode);
1161 u->bi_flags &= ~BCH_INODE_UNLINKED;
1164 u->bi_flags |= BCH_INODE_UNLINKED;
1173 static int check_inode(struct bch_fs *c,
1174 struct bch_inode_unpacked *lostfound_inode,
1175 struct btree_iter *iter,
1176 struct bkey_s_c_inode inode,
1179 struct bch_inode_unpacked u;
1180 bool do_update = false;
1183 ret = bch2_inode_unpack(inode, &u);
1184 if (bch2_fs_inconsistent_on(ret, c,
1185 "error unpacking inode %llu in fsck",
1190 ret = check_inode_nlink(c, lostfound_inode, &u, link,
1196 if (u.bi_flags & BCH_INODE_UNLINKED) {
1197 bch_verbose(c, "deleting inode %llu", u.bi_inum);
1199 ret = bch2_inode_rm(c, u.bi_inum);
1201 bch_err(c, "error in fs gc: error %i "
1202 "while deleting inode", ret);
1206 if (u.bi_flags & BCH_INODE_I_SIZE_DIRTY) {
1207 fsck_err_on(c->sb.clean, c,
1208 "filesystem marked clean, "
1209 "but inode %llu has i_size dirty",
1212 bch_verbose(c, "truncating inode %llu", u.bi_inum);
1215 * XXX: need to truncate partial blocks too here - or ideally
1216 * just switch units to bytes and that issue goes away
1219 ret = bch2_inode_truncate(c, u.bi_inum, u.bi_size);
1221 bch_err(c, "error in fs gc: error %i "
1222 "truncating inode", ret);
1227 * We truncated without our normal sector accounting hook, just
1228 * make sure we recalculate it:
1230 u.bi_flags |= BCH_INODE_I_SECTORS_DIRTY;
1232 u.bi_flags &= ~BCH_INODE_I_SIZE_DIRTY;
1236 if (u.bi_flags & BCH_INODE_I_SECTORS_DIRTY) {
1239 fsck_err_on(c->sb.clean, c,
1240 "filesystem marked clean, "
1241 "but inode %llu has i_sectors dirty",
1244 bch_verbose(c, "recounting sectors for inode %llu",
1247 sectors = bch2_count_inode_sectors(c, u.bi_inum);
1249 bch_err(c, "error in fs gc: error %i "
1250 "recounting inode sectors",
1255 u.bi_sectors = sectors;
1256 u.bi_flags &= ~BCH_INODE_I_SECTORS_DIRTY;
1261 struct bkey_inode_buf p;
1263 bch2_inode_pack(&p, &u);
1265 ret = bch2_btree_insert_at(c, NULL, NULL,
1266 BTREE_INSERT_NOFAIL,
1267 BTREE_INSERT_ENTRY(iter, &p.inode.k_i));
1268 if (ret && ret != -EINTR)
1269 bch_err(c, "error in fs gc: error %i "
1270 "updating inode", ret);
1277 static int bch2_gc_walk_inodes(struct bch_fs *c,
1278 struct bch_inode_unpacked *lostfound_inode,
1280 u64 range_start, u64 range_end)
1282 struct btree_iter iter;
1284 struct nlink *link, zero_links = { 0, 0 };
1285 struct genradix_iter nlinks_iter;
1286 int ret = 0, ret2 = 0;
1289 bch2_btree_iter_init(&iter, c, BTREE_ID_INODES, POS(range_start, 0), 0);
1290 nlinks_iter = genradix_iter_init(links, 0);
1292 while ((k = bch2_btree_iter_peek(&iter)).k &&
1293 !btree_iter_err(k)) {
1294 peek_nlinks: link = genradix_iter_peek(&nlinks_iter, links);
1296 if (!link && (!k.k || iter.pos.inode >= range_end))
1299 nlinks_pos = range_start + nlinks_iter.pos;
1300 if (iter.pos.inode > nlinks_pos) {
1301 /* Should have been caught by dirents pass: */
1302 need_fsck_err_on(link && link->count, c,
1303 "missing inode %llu (nlink %u)",
1304 nlinks_pos, link->count);
1305 genradix_iter_advance(&nlinks_iter, links);
1309 if (iter.pos.inode < nlinks_pos || !link)
1312 if (k.k && k.k->type == BCH_INODE_FS) {
1314 * Avoid potential deadlocks with iter for
1317 bch2_btree_iter_unlock(&iter);
1319 ret = check_inode(c, lostfound_inode, &iter,
1320 bkey_s_c_to_inode(k), link);
1321 BUG_ON(ret == -EINTR);
1326 atomic_long_inc(&c->nr_inodes);
1328 /* Should have been caught by dirents pass: */
1329 need_fsck_err_on(link->count, c,
1330 "missing inode %llu (nlink %u)",
1331 nlinks_pos, link->count);
1334 if (nlinks_pos == iter.pos.inode)
1335 genradix_iter_advance(&nlinks_iter, links);
1337 bch2_btree_iter_next(&iter);
1338 bch2_btree_iter_cond_resched(&iter);
1341 ret2 = bch2_btree_iter_unlock(&iter);
1343 bch_err(c, "error in fs gc: btree error %i while walking inodes", ret2);
1349 static int check_inode_nlinks(struct bch_fs *c,
1350 struct bch_inode_unpacked *lostfound_inode)
1353 u64 this_iter_range_start, next_iter_range_start = 0;
1356 bch_verbose(c, "checking inode nlinks");
1358 genradix_init(&links);
1361 this_iter_range_start = next_iter_range_start;
1362 next_iter_range_start = U64_MAX;
1364 ret = bch2_gc_walk_dirents(c, &links,
1365 this_iter_range_start,
1366 &next_iter_range_start);
1370 ret = bch2_gc_walk_inodes(c, lostfound_inode, &links,
1371 this_iter_range_start,
1372 next_iter_range_start);
1376 genradix_free(&links);
1377 } while (next_iter_range_start != U64_MAX);
1379 genradix_free(&links);
1385 static int check_inodes_fast(struct bch_fs *c)
1387 struct btree_iter iter;
1389 struct bkey_s_c_inode inode;
1390 unsigned long nr_inodes = 0;
1393 for_each_btree_key(&iter, c, BTREE_ID_INODES, POS_MIN, 0, k) {
1394 if (k.k->type != BCH_INODE_FS)
1397 inode = bkey_s_c_to_inode(k);
1399 if (!(inode.v->bi_flags & BCH_INODE_UNLINKED))
1402 if (inode.v->bi_flags &
1403 (BCH_INODE_I_SIZE_DIRTY|
1404 BCH_INODE_I_SECTORS_DIRTY|
1405 BCH_INODE_UNLINKED)) {
1406 fsck_err_on(c->sb.clean, c,
1407 "filesystem marked clean but found inode %llu with flags %x",
1408 inode.k->p.inode, inode.v->bi_flags);
1409 ret = check_inode(c, NULL, &iter, inode, NULL);
1410 BUG_ON(ret == -EINTR);
1415 atomic_long_set(&c->nr_inodes, nr_inodes);
1417 return bch2_btree_iter_unlock(&iter) ?: ret;
1421 * Checks for inconsistencies that shouldn't happen, unless we have a bug.
1422 * Doesn't fix them yet, mainly because they haven't yet been observed:
1424 static int bch2_fsck_full(struct bch_fs *c)
1426 struct bch_inode_unpacked root_inode, lostfound_inode;
1429 bch_verbose(c, "starting fsck:");
1430 ret = check_extents(c) ?:
1433 check_root(c, &root_inode) ?:
1434 check_lostfound(c, &root_inode, &lostfound_inode) ?:
1435 check_directory_structure(c, &lostfound_inode) ?:
1436 check_inode_nlinks(c, &lostfound_inode);
1438 bch2_flush_fsck_errs(c);
1439 bch_verbose(c, "fsck done");
1444 static int bch2_fsck_inode_nlink(struct bch_fs *c)
1446 struct bch_inode_unpacked root_inode, lostfound_inode;
1449 bch_verbose(c, "checking inode link counts:");
1450 ret = check_root(c, &root_inode) ?:
1451 check_lostfound(c, &root_inode, &lostfound_inode) ?:
1452 check_inode_nlinks(c, &lostfound_inode);
1454 bch2_flush_fsck_errs(c);
1455 bch_verbose(c, "done");
1460 static int bch2_fsck_walk_inodes_only(struct bch_fs *c)
1464 bch_verbose(c, "walking inodes:");
1465 ret = check_inodes_fast(c);
1467 bch2_flush_fsck_errs(c);
1468 bch_verbose(c, "done");
1473 int bch2_fsck(struct bch_fs *c)
1476 return bch2_fsck_full(c);
1479 !(c->sb.features & (1 << BCH_FEATURE_ATOMIC_NLINK)))
1480 return bch2_fsck_inode_nlink(c);
1482 return bch2_fsck_walk_inodes_only(c);