X-Git-Url: https://git.sesse.net/?a=blobdiff_plain;f=libbcachefs%2Ffsck.c;h=16a1eae9b374b953ddb9f7078214745325fc6ddb;hb=e61b61c03bf1f1eedc5e2dbd6887f77e45144a31;hp=5c2329d91bcca83d576f0b2194d0f42721895073;hpb=133dfeb64843af65a018be770eb005363ca59bd9;p=bcachefs-tools-debian diff --git a/libbcachefs/fsck.c b/libbcachefs/fsck.c index 5c2329d..16a1eae 100644 --- a/libbcachefs/fsck.c +++ b/libbcachefs/fsck.c @@ -1,27 +1,33 @@ +// SPDX-License-Identifier: GPL-2.0 #include "bcachefs.h" +#include "bkey_buf.h" #include "btree_update.h" #include "dirent.h" #include "error.h" -#include "fs.h" +#include "fs-common.h" #include "fsck.h" #include "inode.h" #include "keylist.h" +#include "subvolume.h" #include "super.h" #include "xattr.h" +#include #include /* struct qstr */ -#include #define QSTR(n) { { { .len = strlen(n) } }, .name = n } -static s64 bch2_count_inode_sectors(struct btree_trans *trans, u64 inum) +static s64 bch2_count_inode_sectors(struct btree_trans *trans, u64 inum, + u32 snapshot) { - struct btree_iter *iter; + struct btree_iter iter; struct bkey_s_c k; u64 sectors = 0; + int ret; - for_each_btree_key(trans, iter, BTREE_ID_EXTENTS, POS(inum, 0), 0, k) { + for_each_btree_key(trans, iter, BTREE_ID_extents, + SPOS(inum, 0, snapshot), 0, k, ret) { if (k.k->p.inode != inum) break; @@ -29,644 +35,1570 @@ static s64 bch2_count_inode_sectors(struct btree_trans *trans, u64 inum) sectors += k.k->size; } - return bch2_trans_iter_free(trans, iter) ?: sectors; + bch2_trans_iter_exit(trans, &iter); + + return ret ?: sectors; } -static int remove_dirent(struct btree_trans *trans, - struct bkey_s_c_dirent dirent) +static s64 bch2_count_subdirs(struct btree_trans *trans, u64 inum, + u32 snapshot) { - struct bch_fs *c = trans->c; - struct qstr name; - struct bch_inode_unpacked dir_inode; - struct bch_hash_info dir_hash_info; - u64 dir_inum = dirent.k->p.inode; + struct btree_iter iter; + struct bkey_s_c k; + struct bkey_s_c_dirent d; + u64 subdirs = 0; int ret; - char *buf; - name.len = bch2_dirent_name_bytes(dirent); - buf = kmalloc(name.len + 1, GFP_KERNEL); - if (!buf) - return -ENOMEM; - - memcpy(buf, dirent.v->d_name, name.len); - buf[name.len] = '\0'; - name.name = buf; + for_each_btree_key(trans, iter, BTREE_ID_dirents, + SPOS(inum, 0, snapshot), 0, k, ret) { + if (k.k->p.inode != inum) + break; - /* Unlock so we don't deadlock, after copying name: */ - bch2_btree_trans_unlock(trans); + if (k.k->type != KEY_TYPE_dirent) + continue; - ret = bch2_inode_find_by_inum(c, dir_inum, &dir_inode); - if (ret) { - bch_err(c, "remove_dirent: err %i looking up directory inode", ret); - goto err; + d = bkey_s_c_to_dirent(k); + if (d.v->d_type == DT_DIR) + subdirs++; } - dir_hash_info = bch2_hash_info_init(c, &dir_inode); + bch2_trans_iter_exit(trans, &iter); - ret = bch2_dirent_delete(c, dir_inum, &dir_hash_info, &name, NULL); - if (ret) - bch_err(c, "remove_dirent: err %i deleting dirent", ret); -err: - kfree(buf); - return ret; + return ret ?: subdirs; } -static int reattach_inode(struct bch_fs *c, - struct bch_inode_unpacked *lostfound_inode, - u64 inum) +static int __snapshot_lookup_subvol(struct btree_trans *trans, u32 snapshot, + u32 *subvol) { - struct bch_hash_info lostfound_hash_info = - bch2_hash_info_init(c, lostfound_inode); - struct bkey_inode_buf packed; - char name_buf[20]; - struct qstr name; + struct btree_iter iter; + struct bkey_s_c k; int ret; - snprintf(name_buf, sizeof(name_buf), "%llu", inum); - name = (struct qstr) QSTR(name_buf); - - lostfound_inode->bi_nlink++; - - bch2_inode_pack(&packed, lostfound_inode); + bch2_trans_iter_init(trans, &iter, BTREE_ID_snapshots, + POS(0, snapshot), 0); + k = bch2_btree_iter_peek_slot(&iter); + ret = bkey_err(k); + if (ret) + goto err; - ret = bch2_btree_insert(c, BTREE_ID_INODES, &packed.inode.k_i, - NULL, NULL, BTREE_INSERT_NOFAIL); - if (ret) { - bch_err(c, "error %i reattaching inode %llu while updating lost+found", - ret, inum); - return ret; + if (k.k->type != KEY_TYPE_snapshot) { + bch_err(trans->c, "snapshot %u not fonud", snapshot); + ret = -ENOENT; + goto err; } - ret = bch2_dirent_create(c, lostfound_inode->bi_inum, - &lostfound_hash_info, - DT_DIR, &name, inum, NULL, - BTREE_INSERT_NOFAIL); - if (ret) { - bch_err(c, "error %i reattaching inode %llu while creating new dirent", - ret, inum); - return ret; - } + *subvol = le32_to_cpu(bkey_s_c_to_snapshot(k).v->subvol); +err: + bch2_trans_iter_exit(trans, &iter); return ret; -} -struct inode_walker { - bool first_this_inode; - bool have_inode; - u64 cur_inum; - struct bch_inode_unpacked inode; -}; +} -static struct inode_walker inode_walker_init(void) +static int snapshot_lookup_subvol(struct btree_trans *trans, u32 snapshot, + u32 *subvol) { - return (struct inode_walker) { - .cur_inum = -1, - .have_inode = false, - }; + return lockrestart_do(trans, __snapshot_lookup_subvol(trans, snapshot, subvol)); } -static int walk_inode(struct bch_fs *c, struct inode_walker *w, u64 inum) +static int __subvol_lookup(struct btree_trans *trans, u32 subvol, + u32 *snapshot, u64 *inum) { - w->first_this_inode = inum != w->cur_inum; - w->cur_inum = inum; - - if (w->first_this_inode) { - int ret = bch2_inode_find_by_inum(c, inum, &w->inode); + struct btree_iter iter; + struct bkey_s_c k; + int ret; - if (ret && ret != -ENOENT) - return ret; + bch2_trans_iter_init(trans, &iter, BTREE_ID_subvolumes, + POS(0, subvol), 0); + k = bch2_btree_iter_peek_slot(&iter); + ret = bkey_err(k); + if (ret) + goto err; - w->have_inode = !ret; + if (k.k->type != KEY_TYPE_subvolume) { + bch_err(trans->c, "subvolume %u not fonud", subvol); + ret = -ENOENT; + goto err; } - return 0; -} - -struct hash_check { - struct bch_hash_info info; - - /* start of current chain of hash collisions: */ - struct btree_iter *chain; - - /* next offset in current chain of hash collisions: */ - u64 chain_end; -}; - -static void hash_check_init(struct hash_check *h) -{ - h->chain = NULL; -} + *snapshot = le32_to_cpu(bkey_s_c_to_subvolume(k).v->snapshot); + *inum = le64_to_cpu(bkey_s_c_to_subvolume(k).v->inode); +err: + bch2_trans_iter_exit(trans, &iter); + return ret; -static void hash_stop_chain(struct btree_trans *trans, - struct hash_check *h) -{ - if (h->chain) - bch2_trans_iter_free(trans, h->chain); - h->chain = NULL; } -static void hash_check_set_inode(struct btree_trans *trans, - struct hash_check *h, - const struct bch_inode_unpacked *bi) +static int subvol_lookup(struct btree_trans *trans, u32 subvol, + u32 *snapshot, u64 *inum) { - h->info = bch2_hash_info_init(trans->c, bi); - hash_stop_chain(trans, h); + return lockrestart_do(trans, __subvol_lookup(trans, subvol, snapshot, inum)); } -static int hash_redo_key(const struct bch_hash_desc desc, - struct btree_trans *trans, struct hash_check *h, - struct btree_iter *k_iter, struct bkey_s_c k, - u64 hashed) +static int __lookup_inode(struct btree_trans *trans, u64 inode_nr, + struct bch_inode_unpacked *inode, + u32 *snapshot) { - struct bkey_i *tmp; - int ret = 0; - - tmp = kmalloc(bkey_bytes(k.k), GFP_KERNEL); - if (!tmp) - return -ENOMEM; - - bkey_reassemble(tmp, k); + struct btree_iter iter; + struct bkey_s_c k; + int ret; - ret = bch2_btree_delete_at(trans, k_iter, 0); + bch2_trans_iter_init(trans, &iter, BTREE_ID_inodes, + SPOS(0, inode_nr, *snapshot), 0); + k = bch2_btree_iter_peek_slot(&iter); + ret = bkey_err(k); if (ret) goto err; - bch2_hash_set(trans, desc, &h->info, k_iter->pos.inode, - tmp, BCH_HASH_SET_MUST_CREATE); - ret = bch2_trans_commit(trans, NULL, NULL, - BTREE_INSERT_NOFAIL| - BTREE_INSERT_LAZY_RW); + *snapshot = iter.pos.snapshot; + ret = k.k->type == KEY_TYPE_inode + ? bch2_inode_unpack(bkey_s_c_to_inode(k), inode) + : -ENOENT; err: - kfree(tmp); + bch2_trans_iter_exit(trans, &iter); return ret; } -static int fsck_hash_delete_at(struct btree_trans *trans, - const struct bch_hash_desc desc, - struct bch_hash_info *info, - struct btree_iter *iter) +static int lookup_inode(struct btree_trans *trans, u64 inode_nr, + struct bch_inode_unpacked *inode, + u32 *snapshot) { + return lockrestart_do(trans, __lookup_inode(trans, inode_nr, inode, snapshot)); +} + +static int __lookup_dirent(struct btree_trans *trans, + struct bch_hash_info hash_info, + subvol_inum dir, struct qstr *name, + u64 *target, unsigned *type) +{ + struct btree_iter iter; + struct bkey_s_c_dirent d; int ret; -retry: - ret = bch2_hash_delete_at(trans, desc, info, iter) ?: - bch2_trans_commit(trans, NULL, NULL, - BTREE_INSERT_ATOMIC| - BTREE_INSERT_NOFAIL| - BTREE_INSERT_LAZY_RW); - if (ret == -EINTR) { - ret = bch2_btree_iter_traverse(iter); - if (!ret) - goto retry; - } - return ret; + ret = bch2_hash_lookup(trans, &iter, bch2_dirent_hash_desc, + &hash_info, dir, name, 0); + if (ret) + return ret; + + d = bkey_s_c_to_dirent(bch2_btree_iter_peek_slot(&iter)); + *target = le64_to_cpu(d.v->d_inum); + *type = d.v->d_type; + bch2_trans_iter_exit(trans, &iter); + return 0; } -static int hash_check_duplicates(struct btree_trans *trans, - const struct bch_hash_desc desc, struct hash_check *h, - struct btree_iter *k_iter, struct bkey_s_c k) +static int lookup_dirent(struct btree_trans *trans, + struct bch_hash_info hash_info, + subvol_inum dir, struct qstr *name, + u64 *target, unsigned *type) { - struct bch_fs *c = trans->c; - struct btree_iter *iter; - struct bkey_s_c k2; - char buf[200]; - int ret = 0; + return lockrestart_do(trans, + __lookup_dirent(trans, hash_info, dir, name, target, type)); +} - if (!bkey_cmp(h->chain->pos, k_iter->pos)) - return 0; +static int __write_inode(struct btree_trans *trans, + struct bch_inode_unpacked *inode, + u32 snapshot) +{ + struct btree_iter iter; + int ret; - iter = bch2_trans_copy_iter(trans, h->chain); - BUG_ON(IS_ERR(iter)); + bch2_trans_iter_init(trans, &iter, BTREE_ID_inodes, + SPOS(0, inode->bi_inum, snapshot), + BTREE_ITER_INTENT); - for_each_btree_key_continue(iter, 0, k2) { - if (bkey_cmp(k2.k->p, k.k->p) >= 0) - break; + ret = bch2_btree_iter_traverse(&iter) ?: + bch2_inode_write(trans, &iter, inode); + bch2_trans_iter_exit(trans, &iter); + return ret; +} - if (fsck_err_on(k2.k->type == desc.key_type && - !desc.cmp_bkey(k, k2), c, - "duplicate hash table keys:\n%s", - (bch2_bkey_val_to_text(&PBUF(buf), c, - k), buf))) { - ret = fsck_hash_delete_at(trans, desc, &h->info, k_iter); - if (ret) - return ret; - ret = 1; - break; - } - } -fsck_err: - bch2_trans_iter_free(trans, iter); +static int write_inode(struct btree_trans *trans, + struct bch_inode_unpacked *inode, + u32 snapshot) +{ + int ret = __bch2_trans_do(trans, NULL, NULL, + BTREE_INSERT_NOFAIL| + BTREE_INSERT_LAZY_RW, + __write_inode(trans, inode, snapshot)); + if (ret) + bch_err(trans->c, "error in fsck: error %i updating inode", ret); return ret; } -static void hash_set_chain_start(struct btree_trans *trans, - const struct bch_hash_desc desc, - struct hash_check *h, - struct btree_iter *k_iter, struct bkey_s_c k) +static int fsck_inode_rm(struct btree_trans *trans, u64 inum, u32 snapshot) { - bool hole = (k.k->type != KEY_TYPE_whiteout && - k.k->type != desc.key_type); + struct btree_iter iter = { NULL }; + struct bkey_i_inode_generation delete; + struct bch_inode_unpacked inode_u; + struct bkey_s_c k; + int ret; + + ret = bch2_btree_delete_range_trans(trans, BTREE_ID_extents, + SPOS(inum, 0, snapshot), + SPOS(inum, U64_MAX, snapshot), + 0, NULL) ?: + bch2_btree_delete_range_trans(trans, BTREE_ID_dirents, + SPOS(inum, 0, snapshot), + SPOS(inum, U64_MAX, snapshot), + 0, NULL) ?: + bch2_btree_delete_range_trans(trans, BTREE_ID_xattrs, + SPOS(inum, 0, snapshot), + SPOS(inum, U64_MAX, snapshot), + 0, NULL); + if (ret) + goto err; +retry: + bch2_trans_begin(trans); - if (hole || k.k->p.offset > h->chain_end + 1) - hash_stop_chain(trans, h); + bch2_trans_iter_init(trans, &iter, BTREE_ID_inodes, + SPOS(0, inum, snapshot), BTREE_ITER_INTENT); + k = bch2_btree_iter_peek_slot(&iter); - if (!hole) { - if (!h->chain) { - h->chain = bch2_trans_copy_iter(trans, k_iter); - BUG_ON(IS_ERR(h->chain)); - } + ret = bkey_err(k); + if (ret) + goto err; - h->chain_end = k.k->p.offset; + if (k.k->type != KEY_TYPE_inode) { + bch2_fs_inconsistent(trans->c, + "inode %llu:%u not found when deleting", + inum, snapshot); + ret = -EIO; + goto err; } -} -static bool key_has_correct_hash(struct btree_trans *trans, - const struct bch_hash_desc desc, - struct hash_check *h, - struct btree_iter *k_iter, struct bkey_s_c k) -{ - u64 hash; + bch2_inode_unpack(bkey_s_c_to_inode(k), &inode_u); - hash_set_chain_start(trans, desc, h, k_iter, k); + /* Subvolume root? */ + if (inode_u.bi_subvol) { + ret = bch2_subvolume_delete(trans, inode_u.bi_subvol, -1); + if (ret) + goto err; + } - if (k.k->type != desc.key_type) - return true; + bkey_inode_generation_init(&delete.k_i); + delete.k.p = iter.pos; + delete.v.bi_generation = cpu_to_le32(inode_u.bi_generation + 1); - hash = desc.hash_bkey(&h->info, k); + ret = bch2_trans_update(trans, &iter, &delete.k_i, 0) ?: + bch2_trans_commit(trans, NULL, NULL, + BTREE_INSERT_NOFAIL); +err: + bch2_trans_iter_exit(trans, &iter); + if (ret == -EINTR) + goto retry; - return hash >= h->chain->pos.offset && - hash <= k.k->p.offset; + return ret; } -static int hash_check_key(struct btree_trans *trans, - const struct bch_hash_desc desc, struct hash_check *h, - struct btree_iter *k_iter, struct bkey_s_c k) +static int __remove_dirent(struct btree_trans *trans, struct bpos pos) { struct bch_fs *c = trans->c; - char buf[200]; - u64 hashed; - int ret = 0; + struct btree_iter iter; + struct bch_inode_unpacked dir_inode; + struct bch_hash_info dir_hash_info; + int ret; - hash_set_chain_start(trans, desc, h, k_iter, k); + ret = lookup_inode(trans, pos.inode, &dir_inode, NULL); + if (ret) + return ret; - if (k.k->type != desc.key_type) - return 0; + dir_hash_info = bch2_hash_info_init(c, &dir_inode); - hashed = desc.hash_bkey(&h->info, k); - - if (fsck_err_on(hashed < h->chain->pos.offset || - hashed > k.k->p.offset, c, - "hash table key at wrong offset: btree %u, %llu, " - "hashed to %llu chain starts at %llu\n%s", - desc.btree_id, k.k->p.offset, - hashed, h->chain->pos.offset, - (bch2_bkey_val_to_text(&PBUF(buf), c, - k), buf))) { - ret = hash_redo_key(desc, trans, h, k_iter, k, hashed); - if (ret) { - bch_err(c, "hash_redo_key err %i", ret); - return ret; - } - return 1; - } + bch2_trans_iter_init(trans, &iter, BTREE_ID_dirents, pos, BTREE_ITER_INTENT); - ret = hash_check_duplicates(trans, desc, h, k_iter, k); -fsck_err: + ret = bch2_hash_delete_at(trans, bch2_dirent_hash_desc, + &dir_hash_info, &iter, 0); + bch2_trans_iter_exit(trans, &iter); + return ret; +} + +static int remove_dirent(struct btree_trans *trans, struct bpos pos) +{ + int ret = __bch2_trans_do(trans, NULL, NULL, + BTREE_INSERT_NOFAIL| + BTREE_INSERT_LAZY_RW, + __remove_dirent(trans, pos)); + if (ret) + bch_err(trans->c, "remove_dirent: err %i deleting dirent", ret); return ret; } -static int check_dirent_hash(struct btree_trans *trans, struct hash_check *h, - struct btree_iter *iter, struct bkey_s_c *k) +/* Get lost+found, create if it doesn't exist: */ +static int lookup_lostfound(struct btree_trans *trans, u32 subvol, + struct bch_inode_unpacked *lostfound) { struct bch_fs *c = trans->c; - struct bkey_i_dirent *d = NULL; - int ret = -EINVAL; - char buf[200]; - unsigned len; - u64 hash; + struct bch_inode_unpacked root; + struct bch_hash_info root_hash_info; + struct qstr lostfound_str = QSTR("lost+found"); + subvol_inum root_inum = { .subvol = subvol }; + u64 inum = 0; + unsigned d_type = 0; + u32 snapshot; + int ret; - if (key_has_correct_hash(trans, bch2_dirent_hash_desc, h, iter, *k)) - return 0; + ret = subvol_lookup(trans, subvol, &snapshot, &root_inum.inum); + if (ret) + return ret; - len = bch2_dirent_name_bytes(bkey_s_c_to_dirent(*k)); - BUG_ON(!len); + ret = lookup_inode(trans, root_inum.inum, &root, &snapshot); + if (ret) { + bch_err(c, "error fetching subvol root: %i", ret); + return ret; + } - memcpy(buf, bkey_s_c_to_dirent(*k).v->d_name, len); - buf[len] = '\0'; + root_hash_info = bch2_hash_info_init(c, &root); - d = kmalloc(bkey_bytes(k->k), GFP_KERNEL); - if (!d) { - bch_err(c, "memory allocation failure"); - return -ENOMEM; + ret = lookup_dirent(trans, root_hash_info, root_inum, + &lostfound_str, &inum, &d_type); + if (ret == -ENOENT) { + bch_notice(c, "creating lost+found"); + goto create_lostfound; } - bkey_reassemble(&d->k_i, *k); + if (ret) { + bch_err(c, "error looking up lost+found: %i", ret); + return ret; + } - do { - --len; - if (!len) - goto err_redo; + if (d_type != DT_DIR) { + bch_err(c, "error looking up lost+found: not a directory"); + return ret; - d->k.u64s = BKEY_U64s + dirent_val_u64s(len); + } - BUG_ON(bkey_val_bytes(&d->k) < - offsetof(struct bch_dirent, d_name) + len); + ret = lookup_inode(trans, inum, lostfound, &snapshot); + if (ret && ret != -ENOENT) { + /* + * The check_dirents pass has already run, dangling dirents + * shouldn't exist here: + */ + bch_err(c, "error looking up lost+found: %i", ret); + return ret; + } - memset(d->v.d_name + len, 0, - bkey_val_bytes(&d->k) - - offsetof(struct bch_dirent, d_name) - len); + if (ret == -ENOENT) { +create_lostfound: + bch2_inode_init_early(c, lostfound); + + ret = __bch2_trans_do(trans, NULL, NULL, + BTREE_INSERT_NOFAIL| + BTREE_INSERT_LAZY_RW, + bch2_create_trans(trans, root_inum, &root, + lostfound, &lostfound_str, + 0, 0, S_IFDIR|0700, 0, NULL, NULL, + (subvol_inum) { }, 0)); + if (ret) + bch_err(c, "error creating lost+found: %i", ret); + } - hash = bch2_dirent_hash_desc.hash_bkey(&h->info, - bkey_i_to_s_c(&d->k_i)); - } while (hash < h->chain->pos.offset || - hash > k->k->p.offset); + return 0; +} - if (fsck_err(c, "dirent with junk at end, was %s (%zu) now %s (%u)", - buf, strlen(buf), d->v.d_name, len)) { - bch2_trans_update(trans, BTREE_INSERT_ENTRY(iter, &d->k_i)); +static int reattach_inode(struct btree_trans *trans, + struct bch_inode_unpacked *inode, + u32 inode_snapshot) +{ + struct bch_hash_info dir_hash; + struct bch_inode_unpacked lostfound; + char name_buf[20]; + struct qstr name; + u64 dir_offset = 0; + u32 subvol; + int ret; - ret = bch2_trans_commit(trans, NULL, NULL, - BTREE_INSERT_NOFAIL| - BTREE_INSERT_LAZY_RW); - if (ret) - goto err; + ret = snapshot_lookup_subvol(trans, inode_snapshot, &subvol); + if (ret) + return ret; - *k = bch2_btree_iter_peek(iter); + ret = lookup_lostfound(trans, subvol, &lostfound); + if (ret) + return ret; - BUG_ON(k->k->type != KEY_TYPE_dirent); - } -err: -fsck_err: - kfree(d); - return ret; -err_redo: - hash = bch2_dirent_hash_desc.hash_bkey(&h->info, *k); - - if (fsck_err(c, "cannot fix dirent by removing trailing garbage %s (%zu)\n" - "hash table key at wrong offset: btree %u, offset %llu, " - "hashed to %llu chain starts at %llu\n%s", - buf, strlen(buf), BTREE_ID_DIRENTS, - k->k->p.offset, hash, h->chain->pos.offset, - (bch2_bkey_val_to_text(&PBUF(buf), c, - *k), buf))) { - ret = hash_redo_key(bch2_dirent_hash_desc, trans, - h, iter, *k, hash); + if (S_ISDIR(inode->bi_mode)) { + lostfound.bi_nlink++; + + ret = write_inode(trans, &lostfound, U32_MAX); if (ret) - bch_err(c, "hash_redo_key err %i", ret); - else - ret = 1; + return ret; } - goto err; -} + dir_hash = bch2_hash_info_init(trans->c, &lostfound); -static int bch2_inode_truncate(struct bch_fs *c, u64 inode_nr, u64 new_size) -{ - return bch2_btree_delete_range(c, BTREE_ID_EXTENTS, - POS(inode_nr, round_up(new_size, block_bytes(c)) >> 9), - POS(inode_nr + 1, 0), NULL); + snprintf(name_buf, sizeof(name_buf), "%llu", inode->bi_inum); + name = (struct qstr) QSTR(name_buf); + + ret = __bch2_trans_do(trans, NULL, NULL, BTREE_INSERT_LAZY_RW, + bch2_dirent_create(trans, + (subvol_inum) { + .subvol = subvol, + .inum = lostfound.bi_inum, + }, + &dir_hash, + mode_to_type(inode->bi_mode), + &name, inode->bi_inum, &dir_offset, + BCH_HASH_SET_MUST_CREATE)); + if (ret) { + bch_err(trans->c, "error %i reattaching inode %llu", + ret, inode->bi_inum); + return ret; + } + + inode->bi_dir = lostfound.bi_inum; + inode->bi_dir_offset = dir_offset; + + return write_inode(trans, inode, inode_snapshot); } -/* - * Walk extents: verify that extents have a corresponding S_ISREG inode, and - * that i_size an i_sectors are consistent - */ -noinline_for_stack -static int check_extents(struct bch_fs *c) +static int remove_backpointer(struct btree_trans *trans, + struct bch_inode_unpacked *inode) { - struct inode_walker w = inode_walker_init(); - struct btree_trans trans; - struct btree_iter *iter; + struct btree_iter iter; struct bkey_s_c k; - u64 i_sectors; - int ret = 0; + int ret; - bch2_trans_init(&trans, c); + bch2_trans_iter_init(trans, &iter, BTREE_ID_dirents, + POS(inode->bi_dir, inode->bi_dir_offset), 0); + k = bch2_btree_iter_peek_slot(&iter); + ret = bkey_err(k); + if (ret) + goto out; + if (k.k->type != KEY_TYPE_dirent) { + ret = -ENOENT; + goto out; + } - bch_verbose(c, "checking extents"); + ret = remove_dirent(trans, k.k->p); +out: + bch2_trans_iter_exit(trans, &iter); + return ret; +} - for_each_btree_key(&trans, iter, BTREE_ID_EXTENTS, - POS(BCACHEFS_ROOT_INO, 0), 0, k) { - ret = walk_inode(c, &w, k.k->p.inode); - if (ret) - break; +static int snapshots_seen_update(struct bch_fs *c, struct snapshots_seen *s, struct bpos pos) +{ + pos.snapshot = snapshot_t(c, pos.snapshot)->equiv; - if (fsck_err_on(!w.have_inode, c, - "extent type %u for missing inode %llu", - k.k->type, k.k->p.inode) || - fsck_err_on(w.have_inode && - !S_ISREG(w.inode.bi_mode) && !S_ISLNK(w.inode.bi_mode), c, - "extent type %u for non regular file, inode %llu mode %o", - k.k->type, k.k->p.inode, w.inode.bi_mode)) { - bch2_trans_unlock(&trans); + if (bkey_cmp(s->pos, pos)) + s->nr = 0; + s->pos = pos; - ret = bch2_inode_truncate(c, k.k->p.inode, 0); - if (ret) - goto err; - continue; - } + /* Might get called multiple times due to lock restarts */ + if (s->nr && s->d[s->nr - 1] == pos.snapshot) + return 0; - if (fsck_err_on(w.first_this_inode && - w.have_inode && - !(w.inode.bi_flags & BCH_INODE_I_SECTORS_DIRTY) && - w.inode.bi_sectors != - (i_sectors = bch2_count_inode_sectors(&trans, w.cur_inum)), - c, "i_sectors wrong: got %llu, should be %llu", - w.inode.bi_sectors, i_sectors)) { - struct bkey_inode_buf p; + return snapshots_seen_add(c, s, pos.snapshot); +} - w.inode.bi_sectors = i_sectors; +/** + * key_visible_in_snapshot - returns true if @id is a descendent of @ancestor, + * and @ancestor hasn't been overwritten in @seen + * + * That is, returns whether key in @ancestor snapshot is visible in @id snapshot + */ +static bool key_visible_in_snapshot(struct bch_fs *c, struct snapshots_seen *seen, + u32 id, u32 ancestor) +{ + ssize_t i; - bch2_trans_unlock(&trans); + BUG_ON(id > ancestor); - bch2_inode_pack(&p, &w.inode); + id = snapshot_t(c, id)->equiv; + ancestor = snapshot_t(c, ancestor)->equiv; - ret = bch2_btree_insert(c, BTREE_ID_INODES, - &p.inode.k_i, NULL, NULL, - BTREE_INSERT_NOFAIL); - if (ret) { - bch_err(c, "error in fs gc: error %i " - "updating inode", ret); - goto err; - } + /* @ancestor should be the snapshot most recently added to @seen */ + BUG_ON(!seen->nr || seen->d[seen->nr - 1] != ancestor); + BUG_ON(seen->pos.snapshot != ancestor); - /* revalidate iterator: */ - k = bch2_btree_iter_peek(iter); - } + if (id == ancestor) + return true; - if (fsck_err_on(w.have_inode && - !(w.inode.bi_flags & BCH_INODE_I_SIZE_DIRTY) && - k.k->type != KEY_TYPE_reservation && - k.k->p.offset > round_up(w.inode.bi_size, PAGE_SIZE) >> 9, c, - "extent type %u offset %llu past end of inode %llu, i_size %llu", - k.k->type, k.k->p.offset, k.k->p.inode, w.inode.bi_size)) { - bch2_trans_unlock(&trans); + if (!bch2_snapshot_is_ancestor(c, id, ancestor)) + return false; - ret = bch2_inode_truncate(c, k.k->p.inode, - w.inode.bi_size); - if (ret) - goto err; - continue; - } - } -err: -fsck_err: - return bch2_trans_exit(&trans) ?: ret; + for (i = seen->nr - 2; + i >= 0 && seen->d[i] >= id; + --i) + if (bch2_snapshot_is_ancestor(c, id, seen->d[i]) && + bch2_snapshot_is_ancestor(c, seen->d[i], ancestor)) + return false; + + return true; } -/* - * Walk dirents: verify that they all have a corresponding S_ISDIR inode, - * validate d_type +/** + * ref_visible - given a key with snapshot id @src that points to a key with + * snapshot id @dst, test whether there is some snapshot in which @dst is + * visible. + * + * This assumes we're visiting @src keys in natural key order. + * + * @s - list of snapshot IDs already seen at @src + * @src - snapshot ID of src key + * @dst - snapshot ID of dst key */ -noinline_for_stack -static int check_dirents(struct bch_fs *c) +static int ref_visible(struct bch_fs *c, struct snapshots_seen *s, + u32 src, u32 dst) { - struct inode_walker w = inode_walker_init(); - struct hash_check h; - struct btree_trans trans; - struct btree_iter *iter; - struct bkey_s_c k; - unsigned name_len; + return dst <= src + ? key_visible_in_snapshot(c, s, dst, src) + : bch2_snapshot_is_ancestor(c, src, dst); +} + +#define for_each_visible_inode(_c, _s, _w, _snapshot, _i) \ + for (_i = (_w)->d; _i < (_w)->d + (_w)->nr && (_i)->snapshot <= (_snapshot); _i++)\ + if (key_visible_in_snapshot(_c, _s, _i->snapshot, _snapshot)) + +struct inode_walker { + bool first_this_inode; + u64 cur_inum; + + size_t nr; + size_t size; + struct inode_walker_entry { + struct bch_inode_unpacked inode; + u32 snapshot; + u64 count; + } *d; +}; + +static void inode_walker_exit(struct inode_walker *w) +{ + kfree(w->d); + w->d = NULL; +} + +static struct inode_walker inode_walker_init(void) +{ + return (struct inode_walker) { 0, }; +} + +static int inode_walker_realloc(struct inode_walker *w) +{ + if (w->nr == w->size) { + size_t new_size = max_t(size_t, 8UL, w->size * 2); + void *d = krealloc(w->d, new_size * sizeof(w->d[0]), + GFP_KERNEL); + if (!d) + return -ENOMEM; + + w->d = d; + w->size = new_size; + } + + return 0; +} + +static int add_inode(struct bch_fs *c, struct inode_walker *w, + struct bkey_s_c_inode inode) +{ + struct bch_inode_unpacked u; + int ret; + + ret = inode_walker_realloc(w); + if (ret) + return ret; + + BUG_ON(bch2_inode_unpack(inode, &u)); + + w->d[w->nr++] = (struct inode_walker_entry) { + .inode = u, + .snapshot = snapshot_t(c, inode.k->p.snapshot)->equiv, + }; + + return 0; +} + +static int __walk_inode(struct btree_trans *trans, + struct inode_walker *w, struct bpos pos) +{ + struct bch_fs *c = trans->c; + struct btree_iter iter; + struct bkey_s_c k; + unsigned i, ancestor_pos; + int ret; + + pos.snapshot = snapshot_t(c, pos.snapshot)->equiv; + + if (pos.inode == w->cur_inum) { + w->first_this_inode = false; + goto lookup_snapshot; + } + + w->nr = 0; + + for_each_btree_key(trans, iter, BTREE_ID_inodes, POS(0, pos.inode), + BTREE_ITER_ALL_SNAPSHOTS, k, ret) { + if (k.k->p.offset != pos.inode) + break; + + if (k.k->type == KEY_TYPE_inode) + add_inode(c, w, bkey_s_c_to_inode(k)); + } + bch2_trans_iter_exit(trans, &iter); + + if (ret) + return ret; + + w->cur_inum = pos.inode; + w->first_this_inode = true; +lookup_snapshot: + for (i = 0; i < w->nr; i++) + if (bch2_snapshot_is_ancestor(c, pos.snapshot, w->d[i].snapshot)) + goto found; + return INT_MAX; +found: + BUG_ON(pos.snapshot > w->d[i].snapshot); + + if (pos.snapshot != w->d[i].snapshot) { + ancestor_pos = i; + + while (i && w->d[i - 1].snapshot > pos.snapshot) + --i; + + ret = inode_walker_realloc(w); + if (ret) + return ret; + + array_insert_item(w->d, w->nr, i, w->d[ancestor_pos]); + w->d[i].snapshot = pos.snapshot; + w->d[i].count = 0; + } + + return i; +} + +static int walk_inode(struct btree_trans *trans, + struct inode_walker *w, struct bpos pos) +{ + return lockrestart_do(trans, __walk_inode(trans, w, pos)); +} + +static int __get_visible_inodes(struct btree_trans *trans, + struct inode_walker *w, + struct snapshots_seen *s, + u64 inum) +{ + struct bch_fs *c = trans->c; + struct btree_iter iter; + struct bkey_s_c k; + int ret; + + w->nr = 0; + + for_each_btree_key(trans, iter, BTREE_ID_inodes, POS(0, inum), + BTREE_ITER_ALL_SNAPSHOTS, k, ret) { + if (k.k->p.offset != inum) + break; + + if (k.k->type != KEY_TYPE_inode) + continue; + + if (ref_visible(c, s, s->pos.snapshot, k.k->p.snapshot)) { + add_inode(c, w, bkey_s_c_to_inode(k)); + if (k.k->p.snapshot >= s->pos.snapshot) + break; + } + } + bch2_trans_iter_exit(trans, &iter); + + return ret; +} + +static int check_key_has_snapshot(struct btree_trans *trans, + struct btree_iter *iter, + struct bkey_s_c k) +{ + struct bch_fs *c = trans->c; char buf[200]; int ret = 0; - bch_verbose(c, "checking dirents"); + if (fsck_err_on(!snapshot_t(c, k.k->p.snapshot)->equiv, c, + "key in missing snapshot: %s", + (bch2_bkey_val_to_text(&PBUF(buf), c, k), buf))) { + ret = __bch2_trans_do(trans, NULL, NULL, BTREE_INSERT_LAZY_RW, + bch2_btree_delete_at(trans, iter, + BTREE_UPDATE_INTERNAL_SNAPSHOT_NODE)); + return ret ?: -EINTR; + } +fsck_err: + return ret; +} + +static int hash_redo_key(struct btree_trans *trans, + const struct bch_hash_desc desc, + struct bch_hash_info *hash_info, + struct btree_iter *k_iter, struct bkey_s_c k) +{ + bch_err(trans->c, "hash_redo_key() not implemented yet"); + return -EINVAL; +#if 0 + struct bkey_i *delete; + struct bkey_i *tmp; + + delete = bch2_trans_kmalloc(trans, sizeof(*delete)); + if (IS_ERR(delete)) + return PTR_ERR(delete); + + tmp = bch2_trans_kmalloc(trans, bkey_bytes(k.k)); + if (IS_ERR(tmp)) + return PTR_ERR(tmp); + + bkey_reassemble(tmp, k); + + bkey_init(&delete->k); + delete->k.p = k_iter->pos; + return bch2_btree_iter_traverse(k_iter) ?: + bch2_trans_update(trans, k_iter, delete, 0) ?: + bch2_hash_set(trans, desc, hash_info, k_iter->pos.inode, tmp, 0); +#endif +} + +static int fsck_hash_delete_at(struct btree_trans *trans, + const struct bch_hash_desc desc, + struct bch_hash_info *info, + struct btree_iter *iter) +{ + int ret; +retry: + ret = bch2_hash_delete_at(trans, desc, info, iter, 0) ?: + bch2_trans_commit(trans, NULL, NULL, + BTREE_INSERT_NOFAIL| + BTREE_INSERT_LAZY_RW); + if (ret == -EINTR) { + ret = bch2_btree_iter_traverse(iter); + if (!ret) + goto retry; + } + + return ret; +} + +static int hash_check_key(struct btree_trans *trans, + const struct bch_hash_desc desc, + struct bch_hash_info *hash_info, + struct btree_iter *k_iter, struct bkey_s_c hash_k) +{ + struct bch_fs *c = trans->c; + struct btree_iter iter = { NULL }; + char buf[200]; + struct bkey_s_c k; + u64 hash; + int ret = 0; + + if (hash_k.k->type != desc.key_type) + return 0; + + hash = desc.hash_bkey(hash_info, hash_k); + + if (likely(hash == hash_k.k->p.offset)) + return 0; + + if (hash_k.k->p.offset < hash) + goto bad_hash; + + for_each_btree_key(trans, iter, desc.btree_id, POS(hash_k.k->p.inode, hash), + BTREE_ITER_SLOTS, k, ret) { + if (!bkey_cmp(k.k->p, hash_k.k->p)) + break; + + if (fsck_err_on(k.k->type == desc.key_type && + !desc.cmp_bkey(k, hash_k), c, + "duplicate hash table keys:\n%s", + (bch2_bkey_val_to_text(&PBUF(buf), c, + hash_k), buf))) { + ret = fsck_hash_delete_at(trans, desc, hash_info, k_iter); + if (ret) + return ret; + ret = 1; + break; + } + + if (bkey_deleted(k.k)) { + bch2_trans_iter_exit(trans, &iter); + goto bad_hash; + } + + } + bch2_trans_iter_exit(trans, &iter); + return ret; +bad_hash: + if (fsck_err(c, "hash table key at wrong offset: btree %u inode %llu offset %llu, " + "hashed to %llu\n%s", + desc.btree_id, hash_k.k->p.inode, hash_k.k->p.offset, hash, + (bch2_bkey_val_to_text(&PBUF(buf), c, hash_k), buf)) == FSCK_ERR_IGNORE) + return 0; + + ret = __bch2_trans_do(trans, NULL, NULL, + BTREE_INSERT_NOFAIL|BTREE_INSERT_LAZY_RW, + hash_redo_key(trans, desc, hash_info, k_iter, hash_k)); + if (ret) { + bch_err(c, "hash_redo_key err %i", ret); + return ret; + } + return -EINTR; +fsck_err: + return ret; +} + +static int check_inode(struct btree_trans *trans, + struct btree_iter *iter, + struct bch_inode_unpacked *prev, + struct bch_inode_unpacked u) +{ + struct bch_fs *c = trans->c; + bool do_update = false; + int ret = 0; + + if (fsck_err_on(prev && + (prev->bi_hash_seed != u.bi_hash_seed || + mode_to_type(prev->bi_mode) != mode_to_type(u.bi_mode)), c, + "inodes in different snapshots don't match")) { + bch_err(c, "repair not implemented yet"); + return -EINVAL; + } + + if (u.bi_flags & BCH_INODE_UNLINKED && + (!c->sb.clean || + fsck_err(c, "filesystem marked clean, but inode %llu unlinked", + u.bi_inum))) { + bch2_trans_unlock(trans); + bch2_fs_lazy_rw(c); + + ret = fsck_inode_rm(trans, u.bi_inum, iter->pos.snapshot); + if (ret) + bch_err(c, "error in fsck: error %i while deleting inode", ret); + return ret; + } + + if (u.bi_flags & BCH_INODE_I_SIZE_DIRTY && + (!c->sb.clean || + fsck_err(c, "filesystem marked clean, but inode %llu has i_size dirty", + u.bi_inum))) { + bch_verbose(c, "truncating inode %llu", u.bi_inum); + + bch2_trans_unlock(trans); + bch2_fs_lazy_rw(c); + + /* + * XXX: need to truncate partial blocks too here - or ideally + * just switch units to bytes and that issue goes away + */ + ret = bch2_btree_delete_range_trans(trans, BTREE_ID_extents, + SPOS(u.bi_inum, round_up(u.bi_size, block_bytes(c)) >> 9, + iter->pos.snapshot), + POS(u.bi_inum, U64_MAX), + 0, NULL); + if (ret) { + bch_err(c, "error in fsck: error %i truncating inode", ret); + return ret; + } + + /* + * We truncated without our normal sector accounting hook, just + * make sure we recalculate it: + */ + u.bi_flags |= BCH_INODE_I_SECTORS_DIRTY; + + u.bi_flags &= ~BCH_INODE_I_SIZE_DIRTY; + do_update = true; + } + + if (u.bi_flags & BCH_INODE_I_SECTORS_DIRTY && + (!c->sb.clean || + fsck_err(c, "filesystem marked clean, but inode %llu has i_sectors dirty", + u.bi_inum))) { + s64 sectors; + + bch_verbose(c, "recounting sectors for inode %llu", + u.bi_inum); + + sectors = bch2_count_inode_sectors(trans, u.bi_inum, iter->pos.snapshot); + if (sectors < 0) { + bch_err(c, "error in fsck: error %i recounting inode sectors", + (int) sectors); + return sectors; + } + + u.bi_sectors = sectors; + u.bi_flags &= ~BCH_INODE_I_SECTORS_DIRTY; + do_update = true; + } + + if (u.bi_flags & BCH_INODE_BACKPTR_UNTRUSTED) { + u.bi_dir = 0; + u.bi_dir_offset = 0; + u.bi_flags &= ~BCH_INODE_BACKPTR_UNTRUSTED; + do_update = true; + } + + if (do_update) { + ret = write_inode(trans, &u, iter->pos.snapshot); + if (ret) + bch_err(c, "error in fsck: error %i " + "updating inode", ret); + } +fsck_err: + return ret; +} + +noinline_for_stack +static int check_inodes(struct bch_fs *c, bool full) +{ + struct btree_trans trans; + struct btree_iter iter; + struct bkey_s_c k; + struct bkey_s_c_inode inode; + struct bch_inode_unpacked prev, u; + int ret; + + memset(&prev, 0, sizeof(prev)); + + bch2_trans_init(&trans, c, BTREE_ITER_MAX, 0); + + for_each_btree_key(&trans, iter, BTREE_ID_inodes, POS_MIN, + BTREE_ITER_INTENT| + BTREE_ITER_PREFETCH| + BTREE_ITER_ALL_SNAPSHOTS, k, ret) { + ret = check_key_has_snapshot(&trans, &iter, k); + if (ret) + break; + + /* + * if snapshot id isn't a leaf node, skip it - deletion in + * particular is not atomic, so on the internal snapshot nodes + * we can see inodes marked for deletion after a clean shutdown + */ + if (bch2_snapshot_internal_node(c, k.k->p.snapshot)) + continue; + + if (k.k->type != KEY_TYPE_inode) + continue; + + inode = bkey_s_c_to_inode(k); + + if (!full && + !(inode.v->bi_flags & (BCH_INODE_I_SIZE_DIRTY| + BCH_INODE_I_SECTORS_DIRTY| + BCH_INODE_UNLINKED))) + continue; + + BUG_ON(bch2_inode_unpack(inode, &u)); + + ret = check_inode(&trans, &iter, + full && prev.bi_inum == u.bi_inum + ? &prev : NULL, u); + if (ret) + break; + + prev = u; + } + bch2_trans_iter_exit(&trans, &iter); + + BUG_ON(ret == -EINTR); + + return bch2_trans_exit(&trans) ?: ret; +} + +noinline_for_stack +static int check_subvols(struct bch_fs *c) +{ + struct btree_trans trans; + struct btree_iter iter; + struct bkey_s_c k; + int ret; - bch2_trans_init(&trans, c); + bch2_trans_init(&trans, c, BTREE_ITER_MAX, 0); - bch2_trans_preload_iters(&trans); + for_each_btree_key(&trans, iter, BTREE_ID_subvolumes, POS_MIN, + 0, k, ret) { + } + bch2_trans_iter_exit(&trans, &iter); + + bch2_trans_exit(&trans); + return ret; +} + +/* + * Checking for overlapping extents needs to be reimplemented + */ +#if 0 +static int fix_overlapping_extent(struct btree_trans *trans, + struct bkey_s_c k, struct bpos cut_at) +{ + struct btree_iter iter; + struct bkey_i *u; + int ret; + + u = bch2_trans_kmalloc(trans, bkey_bytes(k.k)); + ret = PTR_ERR_OR_ZERO(u); + if (ret) + return ret; - iter = bch2_trans_get_iter(&trans, BTREE_ID_DIRENTS, - POS(BCACHEFS_ROOT_INO, 0), 0); + bkey_reassemble(u, k); + bch2_cut_front(cut_at, u); - hash_check_init(&h); - for_each_btree_key_continue(iter, 0, k) { - struct bkey_s_c_dirent d; - struct bch_inode_unpacked target; - bool have_target; - u64 d_inum; + /* + * We don't want to go through the extent_handle_overwrites path: + * + * XXX: this is going to screw up disk accounting, extent triggers + * assume things about extent overwrites - we should be running the + * triggers manually here + */ + bch2_trans_iter_init(trans, &iter, BTREE_ID_extents, u->k.p, + BTREE_ITER_INTENT|BTREE_ITER_NOT_EXTENTS); + + BUG_ON(iter.flags & BTREE_ITER_IS_EXTENTS); + ret = bch2_btree_iter_traverse(&iter) ?: + bch2_trans_update(trans, &iter, u, BTREE_TRIGGER_NORUN) ?: + bch2_trans_commit(trans, NULL, NULL, + BTREE_INSERT_NOFAIL| + BTREE_INSERT_LAZY_RW); + bch2_trans_iter_exit(trans, &iter); + return ret; +} +#endif + +static int inode_backpointer_exists(struct btree_trans *trans, + struct bch_inode_unpacked *inode, + u32 snapshot) +{ + struct btree_iter iter; + struct bkey_s_c k; + int ret; + + bch2_trans_iter_init(trans, &iter, BTREE_ID_dirents, + SPOS(inode->bi_dir, inode->bi_dir_offset, snapshot), 0); + k = bch2_btree_iter_peek_slot(&iter); + ret = bkey_err(k); + if (ret) + goto out; + if (k.k->type != KEY_TYPE_dirent) + goto out; + + ret = le64_to_cpu(bkey_s_c_to_dirent(k).v->d_inum) == inode->bi_inum; +out: + bch2_trans_iter_exit(trans, &iter); + return ret; +} + +static bool inode_backpointer_matches(struct bkey_s_c_dirent d, + struct bch_inode_unpacked *inode) +{ + return d.k->p.inode == inode->bi_dir && + d.k->p.offset == inode->bi_dir_offset; +} + +static int check_i_sectors(struct btree_trans *trans, struct inode_walker *w) +{ + struct bch_fs *c = trans->c; + struct inode_walker_entry *i; + int ret = 0, ret2 = 0; + s64 count2; + + for (i = w->d; i < w->d + w->nr; i++) { + if (i->inode.bi_sectors == i->count) + continue; + + count2 = lockrestart_do(trans, + bch2_count_inode_sectors(trans, w->cur_inum, i->snapshot)); + + if (i->count != count2) { + bch_err(c, "fsck counted i_sectors wrong: got %llu should be %llu", + i->count, count2); + i->count = count2; + if (i->inode.bi_sectors == i->count) + continue; + } + + if (fsck_err_on(!(i->inode.bi_flags & BCH_INODE_I_SECTORS_DIRTY), c, + "inode %llu:%u has incorrect i_sectors: got %llu, should be %llu", + w->cur_inum, i->snapshot, + i->inode.bi_sectors, i->count) == FSCK_ERR_IGNORE) + continue; + + i->inode.bi_sectors = i->count; + ret = write_inode(trans, &i->inode, i->snapshot); + if (ret) + break; + ret2 = -EINTR; + } +fsck_err: + return ret ?: ret2; +} + +static int check_extent(struct btree_trans *trans, struct btree_iter *iter, + struct inode_walker *inode, + struct snapshots_seen *s) +{ + struct bch_fs *c = trans->c; + struct bkey_s_c k; + struct inode_walker_entry *i; + char buf[200]; + int ret = 0; + + k = bch2_btree_iter_peek(iter); + if (!k.k) + return 0; + + ret = bkey_err(k); + if (ret) + return ret; + + ret = check_key_has_snapshot(trans, iter, k); + if (ret) + return ret; + + ret = snapshots_seen_update(c, s, k.k->p); + if (ret) + return ret; + + if (k.k->type == KEY_TYPE_whiteout) + return 0; + + if (inode->cur_inum != k.k->p.inode) { + ret = check_i_sectors(trans, inode); + if (ret) + return ret; + } +#if 0 + if (bkey_cmp(prev.k->k.p, bkey_start_pos(k.k)) > 0) { + char buf1[200]; + char buf2[200]; + + bch2_bkey_val_to_text(&PBUF(buf1), c, bkey_i_to_s_c(prev.k)); + bch2_bkey_val_to_text(&PBUF(buf2), c, k); + + if (fsck_err(c, "overlapping extents:\n%s\n%s", buf1, buf2)) + return fix_overlapping_extent(trans, k, prev.k->k.p) ?: -EINTR; + } +#endif + ret = __walk_inode(trans, inode, k.k->p); + if (ret < 0) + return ret; + + if (fsck_err_on(ret == INT_MAX, c, + "extent in missing inode:\n %s", + (bch2_bkey_val_to_text(&PBUF(buf), c, k), buf))) + return __bch2_trans_do(trans, NULL, NULL, BTREE_INSERT_LAZY_RW, + bch2_btree_delete_at(trans, iter, + BTREE_UPDATE_INTERNAL_SNAPSHOT_NODE)); + + if (ret == INT_MAX) + return 0; + + i = inode->d + ret; + ret = 0; + + if (fsck_err_on(!S_ISREG(i->inode.bi_mode) && + !S_ISLNK(i->inode.bi_mode), c, + "extent in non regular inode mode %o:\n %s", + i->inode.bi_mode, + (bch2_bkey_val_to_text(&PBUF(buf), c, k), buf))) + return __bch2_trans_do(trans, NULL, NULL, BTREE_INSERT_LAZY_RW, + bch2_btree_delete_at(trans, iter, + BTREE_UPDATE_INTERNAL_SNAPSHOT_NODE)); + + if (!bch2_snapshot_internal_node(c, k.k->p.snapshot)) { + for_each_visible_inode(c, s, inode, k.k->p.snapshot, i) { + if (fsck_err_on(!(i->inode.bi_flags & BCH_INODE_I_SIZE_DIRTY) && + k.k->type != KEY_TYPE_reservation && + k.k->p.offset > round_up(i->inode.bi_size, block_bytes(c)) >> 9, c, + "extent type %u offset %llu past end of inode %llu, i_size %llu", + k.k->type, k.k->p.offset, k.k->p.inode, i->inode.bi_size)) { + bch2_fs_lazy_rw(c); + return bch2_btree_delete_range_trans(trans, BTREE_ID_extents, + SPOS(k.k->p.inode, round_up(i->inode.bi_size, block_bytes(c)) >> 9, + k.k->p.snapshot), + POS(k.k->p.inode, U64_MAX), + 0, NULL) ?: -EINTR; + } + } + } + + if (bkey_extent_is_allocation(k.k)) + for_each_visible_inode(c, s, inode, k.k->p.snapshot, i) + i->count += k.k->size; +#if 0 + bch2_bkey_buf_reassemble(&prev, c, k); +#endif + +fsck_err: + return ret; +} + +/* + * Walk extents: verify that extents have a corresponding S_ISREG inode, and + * that i_size an i_sectors are consistent + */ +noinline_for_stack +static int check_extents(struct bch_fs *c) +{ + struct inode_walker w = inode_walker_init(); + struct snapshots_seen s; + struct btree_trans trans; + struct btree_iter iter; + int ret = 0; + +#if 0 + struct bkey_buf prev; + bch2_bkey_buf_init(&prev); + prev.k->k = KEY(0, 0, 0); +#endif + snapshots_seen_init(&s); + bch2_trans_init(&trans, c, BTREE_ITER_MAX, 0); + + bch_verbose(c, "checking extents"); + + bch2_trans_iter_init(&trans, &iter, BTREE_ID_extents, + POS(BCACHEFS_ROOT_INO, 0), + BTREE_ITER_INTENT| + BTREE_ITER_PREFETCH| + BTREE_ITER_ALL_SNAPSHOTS); + + do { + ret = lockrestart_do(&trans, + check_extent(&trans, &iter, &w, &s)); + if (ret) + break; + } while (bch2_btree_iter_advance(&iter)); + bch2_trans_iter_exit(&trans, &iter); +#if 0 + bch2_bkey_buf_exit(&prev, c); +#endif + inode_walker_exit(&w); + bch2_trans_exit(&trans); + snapshots_seen_exit(&s); + + return ret; +} + +static int check_subdir_count(struct btree_trans *trans, struct inode_walker *w) +{ + struct bch_fs *c = trans->c; + struct inode_walker_entry *i; + int ret = 0, ret2 = 0; + s64 count2; + + for (i = w->d; i < w->d + w->nr; i++) { + if (i->inode.bi_nlink == i->count) + continue; + + count2 = lockrestart_do(trans, + bch2_count_subdirs(trans, w->cur_inum, i->snapshot)); + + if (i->count != count2) { + bch_err(c, "fsck counted subdirectories wrong: got %llu should be %llu", + i->count, count2); + i->count = count2; + if (i->inode.bi_nlink == i->count) + continue; + } + + if (fsck_err_on(i->inode.bi_nlink != i->count, c, + "directory %llu:%u with wrong i_nlink: got %u, should be %llu", + w->cur_inum, i->snapshot, i->inode.bi_nlink, i->count)) { + i->inode.bi_nlink = i->count; + ret = write_inode(trans, &i->inode, i->snapshot); + if (ret) + break; + ret2 = -EINTR; + } + } +fsck_err: + return ret ?: ret2; +} + +static int check_dirent_target(struct btree_trans *trans, + struct btree_iter *iter, + struct bkey_s_c_dirent d, + struct bch_inode_unpacked *target, + u32 target_snapshot) +{ + struct bch_fs *c = trans->c; + bool backpointer_exists = true; + char buf[200]; + int ret = 0; + + if (!target->bi_dir && + !target->bi_dir_offset) { + target->bi_dir = d.k->p.inode; + target->bi_dir_offset = d.k->p.offset; + + ret = write_inode(trans, target, target_snapshot); + if (ret) + goto err; + } + + if (!inode_backpointer_matches(d, target)) { + ret = inode_backpointer_exists(trans, target, d.k->p.snapshot); + if (ret < 0) + goto err; + + backpointer_exists = ret; + ret = 0; + + if (fsck_err_on(S_ISDIR(target->bi_mode) && + backpointer_exists, c, + "directory %llu with multiple links", + target->bi_inum)) { + ret = remove_dirent(trans, d.k->p); + if (ret) + goto err; + return 0; + } + + if (fsck_err_on(backpointer_exists && + !target->bi_nlink, c, + "inode %llu has multiple links but i_nlink 0", + target->bi_inum)) { + target->bi_nlink++; + target->bi_flags &= ~BCH_INODE_UNLINKED; - ret = walk_inode(c, &w, k.k->p.inode); - if (ret) - break; + ret = write_inode(trans, target, target_snapshot); + if (ret) + goto err; + } - if (fsck_err_on(!w.have_inode, c, - "dirent in nonexisting directory:\n%s", - (bch2_bkey_val_to_text(&PBUF(buf), c, - k), buf)) || - fsck_err_on(!S_ISDIR(w.inode.bi_mode), c, - "dirent in non directory inode type %u:\n%s", - mode_to_type(w.inode.bi_mode), - (bch2_bkey_val_to_text(&PBUF(buf), c, - k), buf))) { - ret = bch2_btree_delete_at(&trans, iter, 0); + if (fsck_err_on(!backpointer_exists, c, + "inode %llu has wrong backpointer:\n" + "got %llu:%llu\n" + "should be %llu:%llu", + target->bi_inum, + target->bi_dir, + target->bi_dir_offset, + d.k->p.inode, + d.k->p.offset)) { + target->bi_dir = d.k->p.inode; + target->bi_dir_offset = d.k->p.offset; + + ret = write_inode(trans, target, target_snapshot); if (ret) goto err; - continue; } + } - if (w.first_this_inode && w.have_inode) - hash_check_set_inode(&trans, &h, &w.inode); + if (fsck_err_on(vfs_d_type(d.v->d_type) != mode_to_type(target->bi_mode), c, + "incorrect d_type: should be %u:\n%s", + mode_to_type(target->bi_mode), + (bch2_bkey_val_to_text(&PBUF(buf), c, d.s_c), buf))) { + struct bkey_i_dirent *n; - ret = check_dirent_hash(&trans, &h, iter, &k); - if (ret > 0) { - ret = 0; - continue; + n = kmalloc(bkey_bytes(d.k), GFP_KERNEL); + if (!n) { + ret = -ENOMEM; + goto err; } + + bkey_reassemble(&n->k_i, d.s_c); + n->v.d_type = mode_to_type(target->bi_mode); + + ret = __bch2_trans_do(trans, NULL, NULL, + BTREE_INSERT_NOFAIL| + BTREE_INSERT_LAZY_RW, + bch2_trans_update(trans, iter, &n->k_i, 0)); + kfree(n); if (ret) - goto fsck_err; + goto err; + } +err: +fsck_err: + return ret; +} + +static int check_dirent(struct btree_trans *trans, struct btree_iter *iter, + struct bch_hash_info *hash_info, + struct inode_walker *dir, + struct inode_walker *target, + struct snapshots_seen *s) +{ + struct bch_fs *c = trans->c; + struct bkey_s_c k; + struct bkey_s_c_dirent d; + struct inode_walker_entry *i; + u32 target_snapshot; + u32 target_subvol; + u64 target_inum; + char buf[200]; + int ret; + + k = bch2_btree_iter_peek(iter); + if (!k.k) + return 0; + ret = bkey_err(k); + if (ret) + return ret; + + ret = check_key_has_snapshot(trans, iter, k); + if (ret) + return ret; + + ret = snapshots_seen_update(c, s, k.k->p); + if (ret) + return ret; + + if (k.k->type == KEY_TYPE_whiteout) + return 0; + + if (dir->cur_inum != k.k->p.inode) { + ret = check_subdir_count(trans, dir); if (ret) - goto fsck_err; + return ret; + } - if (k.k->type != KEY_TYPE_dirent) - continue; + ret = __walk_inode(trans, dir, k.k->p); + if (ret < 0) + return ret; - d = bkey_s_c_to_dirent(k); - d_inum = le64_to_cpu(d.v->d_inum); - - name_len = bch2_dirent_name_bytes(d); - - if (fsck_err_on(!name_len, c, "empty dirent") || - fsck_err_on(name_len == 1 && - !memcmp(d.v->d_name, ".", 1), c, - ". dirent") || - fsck_err_on(name_len == 2 && - !memcmp(d.v->d_name, "..", 2), c, - ".. dirent") || - fsck_err_on(name_len == 2 && - !memcmp(d.v->d_name, "..", 2), c, - ".. dirent") || - fsck_err_on(memchr(d.v->d_name, '/', name_len), c, - "dirent name has invalid chars")) { - ret = remove_dirent(&trans, d); - if (ret) - goto err; - continue; + if (fsck_err_on(ret == INT_MAX, c, + "dirent in nonexisting directory:\n%s", + (bch2_bkey_val_to_text(&PBUF(buf), c, k), buf))) + return __bch2_trans_do(trans, NULL, NULL, BTREE_INSERT_LAZY_RW, + bch2_btree_delete_at(trans, iter, + BTREE_UPDATE_INTERNAL_SNAPSHOT_NODE)); + + if (ret == INT_MAX) + return 0; + + i = dir->d + ret; + ret = 0; + + if (fsck_err_on(!S_ISDIR(i->inode.bi_mode), c, + "dirent in non directory inode type %u:\n%s", + mode_to_type(i->inode.bi_mode), + (bch2_bkey_val_to_text(&PBUF(buf), c, k), buf))) + return __bch2_trans_do(trans, NULL, NULL, 0, + bch2_btree_delete_at(trans, iter, 0)); + + if (dir->first_this_inode) + *hash_info = bch2_hash_info_init(c, &dir->d[0].inode); + + ret = hash_check_key(trans, bch2_dirent_hash_desc, + hash_info, iter, k); + if (ret < 0) + return ret; + if (ret) /* dirent has been deleted */ + return 0; + + if (k.k->type != KEY_TYPE_dirent) + return 0; + + d = bkey_s_c_to_dirent(k); + + ret = __bch2_dirent_read_target(trans, d, + &target_subvol, + &target_snapshot, + &target_inum, + true); + if (ret && ret != -ENOENT) + return ret; + + if (fsck_err_on(ret, c, + "dirent points to missing subvolume %llu", + le64_to_cpu(d.v->d_inum))) + return remove_dirent(trans, d.k->p); + + if (target_subvol) { + struct bch_inode_unpacked subvol_root; + + ret = __lookup_inode(trans, target_inum, + &subvol_root, &target_snapshot); + if (ret && ret != -ENOENT) + return ret; + + if (fsck_err_on(ret, c, + "subvolume %u points to missing subvolume root %llu", + target_subvol, + target_inum)) { + bch_err(c, "repair not implemented yet"); + return -EINVAL; } - if (fsck_err_on(d_inum == d.k->p.inode, c, - "dirent points to own directory:\n%s", - (bch2_bkey_val_to_text(&PBUF(buf), c, - k), buf))) { - ret = remove_dirent(&trans, d); + if (fsck_err_on(subvol_root.bi_subvol != target_subvol, c, + "subvol root %llu has wrong bi_subvol field: got %u, should be %u", + target_inum, + subvol_root.bi_subvol, target_subvol)) { + subvol_root.bi_subvol = target_subvol; + ret = write_inode(trans, &subvol_root, target_snapshot); if (ret) - goto err; - continue; + return ret; } - ret = bch2_inode_find_by_inum(c, d_inum, &target); - if (ret && ret != -ENOENT) - break; - - have_target = !ret; - ret = 0; + ret = check_dirent_target(trans, iter, d, &subvol_root, + target_snapshot); + if (ret) + return ret; + } else { + ret = __get_visible_inodes(trans, target, s, target_inum); + if (ret) + return ret; - if (fsck_err_on(!have_target, c, + if (fsck_err_on(!target->nr, c, "dirent points to missing inode:\n%s", (bch2_bkey_val_to_text(&PBUF(buf), c, k), buf))) { - ret = remove_dirent(&trans, d); + ret = remove_dirent(trans, d.k->p); if (ret) - goto err; - continue; + return ret; } - if (fsck_err_on(have_target && - d.v->d_type != - mode_to_type(target.bi_mode), c, - "incorrect d_type: should be %u:\n%s", - mode_to_type(target.bi_mode), - (bch2_bkey_val_to_text(&PBUF(buf), c, - k), buf))) { - struct bkey_i_dirent *n; + for (i = target->d; i < target->d + target->nr; i++) { + ret = check_dirent_target(trans, iter, d, + &i->inode, i->snapshot); + if (ret) + return ret; + } + } - n = kmalloc(bkey_bytes(d.k), GFP_KERNEL); - if (!n) { - ret = -ENOMEM; - goto err; - } + if (d.v->d_type == DT_DIR) + for_each_visible_inode(c, s, dir, d.k->p.snapshot, i) + i->count++; - bkey_reassemble(&n->k_i, d.s_c); - n->v.d_type = mode_to_type(target.bi_mode); +fsck_err: + return ret; +} - bch2_trans_update(&trans, - BTREE_INSERT_ENTRY(iter, &n->k_i)); +/* + * Walk dirents: verify that they all have a corresponding S_ISDIR inode, + * validate d_type + */ +noinline_for_stack +static int check_dirents(struct bch_fs *c) +{ + struct inode_walker dir = inode_walker_init(); + struct inode_walker target = inode_walker_init(); + struct snapshots_seen s; + struct bch_hash_info hash_info; + struct btree_trans trans; + struct btree_iter iter; + int ret = 0; - ret = bch2_trans_commit(&trans, NULL, NULL, - BTREE_INSERT_NOFAIL| - BTREE_INSERT_LAZY_RW); - kfree(n); - if (ret) - goto err; + bch_verbose(c, "checking dirents"); - } - } + snapshots_seen_init(&s); + bch2_trans_init(&trans, c, BTREE_ITER_MAX, 0); - hash_stop_chain(&trans, &h); -err: -fsck_err: - return bch2_trans_exit(&trans) ?: ret; + bch2_trans_iter_init(&trans, &iter, BTREE_ID_dirents, + POS(BCACHEFS_ROOT_INO, 0), + BTREE_ITER_INTENT| + BTREE_ITER_PREFETCH| + BTREE_ITER_ALL_SNAPSHOTS); + + do { + ret = lockrestart_do(&trans, + check_dirent(&trans, &iter, &hash_info, + &dir, &target, &s)); + if (ret) + break; + } while (bch2_btree_iter_advance(&iter)); + bch2_trans_iter_exit(&trans, &iter); + + bch2_trans_exit(&trans); + snapshots_seen_exit(&s); + inode_walker_exit(&dir); + inode_walker_exit(&target); + return ret; } /* @@ -676,176 +1608,123 @@ noinline_for_stack static int check_xattrs(struct bch_fs *c) { struct inode_walker w = inode_walker_init(); - struct hash_check h; + struct bch_hash_info hash_info; struct btree_trans trans; - struct btree_iter *iter; + struct btree_iter iter; struct bkey_s_c k; int ret = 0; bch_verbose(c, "checking xattrs"); - bch2_trans_init(&trans, c); - - bch2_trans_preload_iters(&trans); + bch2_trans_init(&trans, c, BTREE_ITER_MAX, 0); - iter = bch2_trans_get_iter(&trans, BTREE_ID_XATTRS, - POS(BCACHEFS_ROOT_INO, 0), 0); - - hash_check_init(&h); + bch2_trans_iter_init(&trans, &iter, BTREE_ID_xattrs, + POS(BCACHEFS_ROOT_INO, 0), + BTREE_ITER_INTENT| + BTREE_ITER_PREFETCH| + BTREE_ITER_ALL_SNAPSHOTS); +retry: + bch2_trans_begin(&trans); - for_each_btree_key_continue(iter, 0, k) { - ret = walk_inode(c, &w, k.k->p.inode); + while ((k = bch2_btree_iter_peek(&iter)).k && + !(ret = bkey_err(k))) { + ret = check_key_has_snapshot(&trans, &iter, k); if (ret) break; - if (fsck_err_on(!w.have_inode, c, + ret = walk_inode(&trans, &w, k.k->p); + if (ret < 0) + break; + + if (fsck_err_on(ret == INT_MAX, c, "xattr for missing inode %llu", k.k->p.inode)) { - ret = bch2_btree_delete_at(&trans, iter, 0); + ret = bch2_btree_delete_at(&trans, &iter, 0); if (ret) - goto err; + break; continue; } - if (w.first_this_inode && w.have_inode) - hash_check_set_inode(&trans, &h, &w.inode); + if (ret == INT_MAX) + goto next; + ret = 0; + + if (w.first_this_inode) + hash_info = bch2_hash_info_init(c, &w.d[0].inode); ret = hash_check_key(&trans, bch2_xattr_hash_desc, - &h, iter, k); + &hash_info, &iter, k); if (ret) - goto fsck_err; + break; +next: + bch2_btree_iter_advance(&iter); } -err: fsck_err: + if (ret == -EINTR) + goto retry; + + bch2_trans_iter_exit(&trans, &iter); return bch2_trans_exit(&trans) ?: ret; } /* Get root directory, create if it doesn't exist: */ -static int check_root(struct bch_fs *c, struct bch_inode_unpacked *root_inode) +static int check_root(struct bch_fs *c) { - struct bkey_inode_buf packed; + struct btree_trans trans; + struct bch_inode_unpacked root_inode; + u32 snapshot; + u64 inum; int ret; + bch2_trans_init(&trans, c, 0, 0); + bch_verbose(c, "checking root directory"); - ret = bch2_inode_find_by_inum(c, BCACHEFS_ROOT_INO, root_inode); + ret = subvol_lookup(&trans, BCACHEFS_ROOT_SUBVOL, &snapshot, &inum); if (ret && ret != -ENOENT) return ret; - if (fsck_err_on(ret, c, "root directory missing")) - goto create_root; - - if (fsck_err_on(!S_ISDIR(root_inode->bi_mode), c, - "root inode not a directory")) - goto create_root; - - return 0; -fsck_err: - return ret; -create_root: - bch2_inode_init(c, root_inode, 0, 0, S_IFDIR|S_IRWXU|S_IRUGO|S_IXUGO, - 0, NULL); - root_inode->bi_inum = BCACHEFS_ROOT_INO; - - bch2_inode_pack(&packed, root_inode); - - return bch2_btree_insert(c, BTREE_ID_INODES, &packed.inode.k_i, - NULL, NULL, BTREE_INSERT_NOFAIL); -} - -/* Get lost+found, create if it doesn't exist: */ -static int check_lostfound(struct bch_fs *c, - struct bch_inode_unpacked *root_inode, - struct bch_inode_unpacked *lostfound_inode) -{ - struct qstr lostfound = QSTR("lost+found"); - struct bch_hash_info root_hash_info = - bch2_hash_info_init(c, root_inode); - struct bkey_inode_buf packed; - u64 inum; - int ret; - - bch_verbose(c, "checking lost+found"); + if (mustfix_fsck_err_on(ret, c, "root subvol missing")) { + struct bkey_i_subvolume root_subvol; + + snapshot = U32_MAX; + inum = BCACHEFS_ROOT_INO; + + bkey_subvolume_init(&root_subvol.k_i); + root_subvol.k.p.offset = BCACHEFS_ROOT_SUBVOL; + root_subvol.v.flags = 0; + root_subvol.v.snapshot = cpu_to_le32(snapshot); + root_subvol.v.inode = cpu_to_le64(inum); + ret = __bch2_trans_do(&trans, NULL, NULL, + BTREE_INSERT_NOFAIL| + BTREE_INSERT_LAZY_RW, + __bch2_btree_insert(&trans, BTREE_ID_subvolumes, &root_subvol.k_i)); + if (ret) { + bch_err(c, "error writing root subvol: %i", ret); + goto err; + } - inum = bch2_dirent_lookup(c, BCACHEFS_ROOT_INO, &root_hash_info, - &lostfound); - if (!inum) { - bch_notice(c, "creating lost+found"); - goto create_lostfound; } - ret = bch2_inode_find_by_inum(c, inum, lostfound_inode); + ret = lookup_inode(&trans, BCACHEFS_ROOT_INO, &root_inode, &snapshot); if (ret && ret != -ENOENT) return ret; - if (fsck_err_on(ret, c, "lost+found missing")) - goto create_lostfound; - - if (fsck_err_on(!S_ISDIR(lostfound_inode->bi_mode), c, - "lost+found inode not a directory")) - goto create_lostfound; + if (mustfix_fsck_err_on(ret, c, "root directory missing") || + mustfix_fsck_err_on(!S_ISDIR(root_inode.bi_mode), c, + "root inode not a directory")) { + bch2_inode_init(c, &root_inode, 0, 0, S_IFDIR|0755, + 0, NULL); + root_inode.bi_inum = inum; - return 0; + ret = write_inode(&trans, &root_inode, snapshot); + if (ret) + bch_err(c, "error writing root inode: %i", ret); + } +err: fsck_err: + bch2_trans_exit(&trans); return ret; -create_lostfound: - root_inode->bi_nlink++; - - bch2_inode_pack(&packed, root_inode); - - ret = bch2_btree_insert(c, BTREE_ID_INODES, &packed.inode.k_i, - NULL, NULL, BTREE_INSERT_NOFAIL); - if (ret) - return ret; - - bch2_inode_init(c, lostfound_inode, 0, 0, S_IFDIR|S_IRWXU|S_IRUGO|S_IXUGO, - 0, root_inode); - - ret = bch2_inode_create(c, lostfound_inode, BLOCKDEV_INODE_MAX, 0, - &c->unused_inode_hint); - if (ret) - return ret; - - ret = bch2_dirent_create(c, BCACHEFS_ROOT_INO, &root_hash_info, DT_DIR, - &lostfound, lostfound_inode->bi_inum, NULL, - BTREE_INSERT_NOFAIL); - if (ret) - return ret; - - return 0; -} - -struct inode_bitmap { - unsigned long *bits; - size_t size; -}; - -static inline bool inode_bitmap_test(struct inode_bitmap *b, size_t nr) -{ - return nr < b->size ? test_bit(nr, b->bits) : false; -} - -static inline int inode_bitmap_set(struct inode_bitmap *b, size_t nr) -{ - if (nr >= b->size) { - size_t new_size = max_t(size_t, max_t(size_t, - PAGE_SIZE * 8, - b->size * 2), - nr + 1); - void *n; - - new_size = roundup_pow_of_two(new_size); - n = krealloc(b->bits, new_size / 8, GFP_KERNEL|__GFP_ZERO); - if (!n) { - return -ENOMEM; - } - - b->bits = n; - b->size = new_size; - } - - __set_bit(nr, b->bits); - return 0; } struct pathbuf { @@ -854,7 +1733,6 @@ struct pathbuf { struct pathbuf_entry { u64 inum; - u64 offset; } *entries; }; @@ -865,8 +1743,9 @@ static int path_down(struct pathbuf *p, u64 inum) void *n = krealloc(p->entries, new_size * sizeof(p->entries[0]), GFP_KERNEL); - if (!n) + if (!n) { return -ENOMEM; + } p->entries = n; p->size = new_size; @@ -874,636 +1753,421 @@ static int path_down(struct pathbuf *p, u64 inum) p->entries[p->nr++] = (struct pathbuf_entry) { .inum = inum, - .offset = 0, }; return 0; } -noinline_for_stack -static int check_directory_structure(struct bch_fs *c, - struct bch_inode_unpacked *lostfound_inode) +static int check_path(struct btree_trans *trans, + struct pathbuf *p, + struct bch_inode_unpacked *inode, + u32 snapshot) { - struct inode_bitmap dirs_done = { NULL, 0 }; - struct pathbuf path = { 0, 0, NULL }; - struct pathbuf_entry *e; - struct btree_trans trans; - struct btree_iter *iter; - struct bkey_s_c k; - struct bkey_s_c_dirent dirent; - bool had_unreachable; - u64 d_inum; - int ret = 0; - - bch2_trans_init(&trans, c); - - bch_verbose(c, "checking directory structure"); - - /* DFS: */ -restart_dfs: - had_unreachable = false; - - ret = inode_bitmap_set(&dirs_done, BCACHEFS_ROOT_INO); - if (ret) { - bch_err(c, "memory allocation failure in inode_bitmap_set()"); - goto err; - } - - ret = path_down(&path, BCACHEFS_ROOT_INO); - if (ret) { - return ret; - } - - while (path.nr) { -next: - e = &path.entries[path.nr - 1]; - - if (e->offset == U64_MAX) - goto up; - - for_each_btree_key(&trans, iter, BTREE_ID_DIRENTS, - POS(e->inum, e->offset + 1), 0, k) { - if (k.k->p.inode != e->inum) - break; - - e->offset = k.k->p.offset; - - if (k.k->type != KEY_TYPE_dirent) - continue; - - dirent = bkey_s_c_to_dirent(k); - - if (dirent.v->d_type != DT_DIR) - continue; - - d_inum = le64_to_cpu(dirent.v->d_inum); - - if (fsck_err_on(inode_bitmap_test(&dirs_done, d_inum), c, - "directory %llu has multiple hardlinks", - d_inum)) { - ret = remove_dirent(&trans, dirent); - if (ret) - goto err; - continue; - } - - ret = inode_bitmap_set(&dirs_done, d_inum); - if (ret) { - bch_err(c, "memory allocation failure in inode_bitmap_set()"); - goto err; - } - - ret = path_down(&path, d_inum); - if (ret) { - goto err; - } - - ret = bch2_trans_iter_free(&trans, iter); - if (ret) { - bch_err(c, "btree error %i in fsck", ret); - goto err; - } - goto next; - } - ret = bch2_trans_iter_free(&trans, iter); - if (ret) { - bch_err(c, "btree error %i in fsck", ret); - goto err; - } -up: - path.nr--; - } - - for_each_btree_key(&trans, iter, BTREE_ID_INODES, POS_MIN, 0, k) { - if (k.k->type != KEY_TYPE_inode) - continue; - - if (!S_ISDIR(le16_to_cpu(bkey_s_c_to_inode(k).v->bi_mode))) - continue; - - if (!bch2_empty_dir(c, k.k->p.inode)) - continue; + struct bch_fs *c = trans->c; + size_t i; + int ret = 0; - if (fsck_err_on(!inode_bitmap_test(&dirs_done, k.k->p.inode), c, - "unreachable directory found (inum %llu)", - k.k->p.inode)) { - bch2_btree_trans_unlock(&trans); + snapshot = snapshot_t(c, snapshot)->equiv; + p->nr = 0; - ret = reattach_inode(c, lostfound_inode, k.k->p.inode); - if (ret) { - goto err; - } + while (inode->bi_inum != BCACHEFS_ROOT_INO) { + ret = lockrestart_do(trans, + inode_backpointer_exists(trans, inode, snapshot)); + if (ret < 0) + break; - had_unreachable = true; + if (!ret) { + if (fsck_err(c, "unreachable inode %llu:%u, type %u nlink %u backptr %llu:%llu", + inode->bi_inum, snapshot, + mode_to_type(inode->bi_mode), + inode->bi_nlink, + inode->bi_dir, + inode->bi_dir_offset)) + ret = reattach_inode(trans, inode, snapshot); + break; } - } - ret = bch2_trans_iter_free(&trans, iter); - if (ret) - goto err; + ret = 0; - if (had_unreachable) { - bch_info(c, "reattached unreachable directories, restarting pass to check for loops"); - kfree(dirs_done.bits); - kfree(path.entries); - memset(&dirs_done, 0, sizeof(dirs_done)); - memset(&path, 0, sizeof(path)); - goto restart_dfs; - } + if (!S_ISDIR(inode->bi_mode)) + break; -out: - kfree(dirs_done.bits); - kfree(path.entries); - return ret; -err: -fsck_err: - ret = bch2_trans_exit(&trans) ?: ret; - goto out; -} + ret = path_down(p, inode->bi_inum); + if (ret) { + bch_err(c, "memory allocation failure"); + return ret; + } -struct nlink { - u32 count; - u32 dir_count; -}; + for (i = 0; i < p->nr; i++) { + if (inode->bi_dir != p->entries[i].inum) + continue; -typedef GENRADIX(struct nlink) nlink_table; + /* XXX print path */ + if (!fsck_err(c, "directory structure loop")) + return 0; -static void inc_link(struct bch_fs *c, nlink_table *links, - u64 range_start, u64 *range_end, - u64 inum, bool dir) -{ - struct nlink *link; + ret = lockrestart_do(trans, + remove_backpointer(trans, inode)); + if (ret) { + bch_err(c, "error removing dirent: %i", ret); + break; + } - if (inum < range_start || inum >= *range_end) - return; + ret = reattach_inode(trans, inode, snapshot); + break; + } - link = genradix_ptr_alloc(links, inum - range_start, GFP_KERNEL); - if (!link) { - bch_verbose(c, "allocation failed during fs gc - will need another pass"); - *range_end = inum; - return; + ret = lookup_inode(trans, inode->bi_dir, inode, &snapshot); + if (ret) { + /* Should have been caught in dirents pass */ + bch_err(c, "error looking up parent directory: %i", ret); + break; + } } - - if (dir) - link->dir_count++; - else - link->count++; +fsck_err: + if (ret) + bch_err(c, "%s: err %i", __func__, ret); + return ret; } -noinline_for_stack -static int bch2_gc_walk_dirents(struct bch_fs *c, nlink_table *links, - u64 range_start, u64 *range_end) +/* + * Check for unreachable inodes, as well as loops in the directory structure: + * After check_dirents(), if an inode backpointer doesn't exist that means it's + * unreachable: + */ +static int check_directory_structure(struct bch_fs *c) { struct btree_trans trans; - struct btree_iter *iter; + struct btree_iter iter; struct bkey_s_c k; - struct bkey_s_c_dirent d; - u64 d_inum; + struct bch_inode_unpacked u; + struct pathbuf path = { 0, 0, NULL }; int ret; - bch2_trans_init(&trans, c); - - inc_link(c, links, range_start, range_end, BCACHEFS_ROOT_INO, false); - - for_each_btree_key(&trans, iter, BTREE_ID_DIRENTS, POS_MIN, 0, k) { - switch (k.k->type) { - case KEY_TYPE_dirent: - d = bkey_s_c_to_dirent(k); - d_inum = le64_to_cpu(d.v->d_inum); - - if (d.v->d_type == DT_DIR) - inc_link(c, links, range_start, range_end, - d.k->p.inode, true); + bch2_trans_init(&trans, c, BTREE_ITER_MAX, 0); - inc_link(c, links, range_start, range_end, - d_inum, false); + for_each_btree_key(&trans, iter, BTREE_ID_inodes, POS_MIN, + BTREE_ITER_INTENT| + BTREE_ITER_PREFETCH| + BTREE_ITER_ALL_SNAPSHOTS, k, ret) { + if (k.k->type != KEY_TYPE_inode) + continue; + ret = bch2_inode_unpack(bkey_s_c_to_inode(k), &u); + if (ret) { + /* Should have been caught earlier in fsck: */ + bch_err(c, "error unpacking inode %llu: %i", k.k->p.offset, ret); break; } - bch2_trans_cond_resched(&trans); + if (u.bi_flags & BCH_INODE_UNLINKED) + continue; + + ret = check_path(&trans, &path, &u, iter.pos.snapshot); + if (ret) + break; } - ret = bch2_trans_exit(&trans); - if (ret) - bch_err(c, "error in fs gc: btree error %i while walking dirents", ret); + bch2_trans_iter_exit(&trans, &iter); - return ret; -} + BUG_ON(ret == -EINTR); -static int check_inode_nlink(struct bch_fs *c, - struct bch_inode_unpacked *lostfound_inode, - struct bch_inode_unpacked *u, - struct nlink *link, - bool *do_update) -{ - u32 i_nlink = u->bi_flags & BCH_INODE_UNLINKED - ? 0 - : u->bi_nlink + nlink_bias(u->bi_mode); - u32 real_i_nlink = - link->count * nlink_bias(u->bi_mode) + - link->dir_count; - int ret = 0; + kfree(path.entries); - /* - * These should have been caught/fixed by earlier passes, we don't - * repair them here: - */ - if (S_ISDIR(u->bi_mode) && link->count > 1) { - need_fsck_err(c, "directory %llu with multiple hardlinks: %u", - u->bi_inum, link->count); - return 0; - } + return bch2_trans_exit(&trans) ?: ret; +} - if (S_ISDIR(u->bi_mode) && !link->count) { - need_fsck_err(c, "unreachable directory found (inum %llu)", - u->bi_inum); - return 0; - } +struct nlink_table { + size_t nr; + size_t size; - if (!S_ISDIR(u->bi_mode) && link->dir_count) { - need_fsck_err(c, "non directory with subdirectories", - u->bi_inum); - return 0; - } + struct nlink { + u64 inum; + u32 snapshot; + u32 count; + } *d; +}; - if (!link->count && - !(u->bi_flags & BCH_INODE_UNLINKED) && - (c->sb.features & (1 << BCH_FEATURE_ATOMIC_NLINK))) { - if (fsck_err(c, "unreachable inode %llu not marked as unlinked (type %u)", - u->bi_inum, mode_to_type(u->bi_mode)) == - FSCK_ERR_IGNORE) - return 0; +static int add_nlink(struct nlink_table *t, u64 inum, u32 snapshot) +{ + if (t->nr == t->size) { + size_t new_size = max_t(size_t, 128UL, t->size * 2); + void *d = kvmalloc(new_size * sizeof(t->d[0]), GFP_KERNEL); + if (!d) { + return -ENOMEM; + } - ret = reattach_inode(c, lostfound_inode, u->bi_inum); - if (ret) - return ret; + if (t->d) + memcpy(d, t->d, t->size * sizeof(t->d[0])); + kvfree(t->d); - link->count = 1; - real_i_nlink = nlink_bias(u->bi_mode) + link->dir_count; - goto set_i_nlink; + t->d = d; + t->size = new_size; } - if (i_nlink < link->count) { - if (fsck_err(c, "inode %llu i_link too small (%u < %u, type %i)", - u->bi_inum, i_nlink, link->count, - mode_to_type(u->bi_mode)) == FSCK_ERR_IGNORE) - return 0; - goto set_i_nlink; - } - if (i_nlink != real_i_nlink && - c->sb.clean) { - if (fsck_err(c, "filesystem marked clean, " - "but inode %llu has wrong i_nlink " - "(type %u i_nlink %u, should be %u)", - u->bi_inum, mode_to_type(u->bi_mode), - i_nlink, real_i_nlink) == FSCK_ERR_IGNORE) - return 0; - goto set_i_nlink; - } + t->d[t->nr++] = (struct nlink) { + .inum = inum, + .snapshot = snapshot, + }; - if (i_nlink != real_i_nlink && - (c->sb.features & (1 << BCH_FEATURE_ATOMIC_NLINK))) { - if (fsck_err(c, "inode %llu has wrong i_nlink " - "(type %u i_nlink %u, should be %u)", - u->bi_inum, mode_to_type(u->bi_mode), - i_nlink, real_i_nlink) == FSCK_ERR_IGNORE) - return 0; - goto set_i_nlink; - } + return 0; +} - if (real_i_nlink && i_nlink != real_i_nlink) - bch_verbose(c, "setting inode %llu nlink from %u to %u", - u->bi_inum, i_nlink, real_i_nlink); -set_i_nlink: - if (i_nlink != real_i_nlink) { - if (real_i_nlink) { - u->bi_nlink = real_i_nlink - nlink_bias(u->bi_mode); - u->bi_flags &= ~BCH_INODE_UNLINKED; - } else { - u->bi_nlink = 0; - u->bi_flags |= BCH_INODE_UNLINKED; - } +static int nlink_cmp(const void *_l, const void *_r) +{ + const struct nlink *l = _l; + const struct nlink *r = _r; - *do_update = true; - } -fsck_err: - return ret; + return cmp_int(l->inum, r->inum) ?: cmp_int(l->snapshot, r->snapshot); } -static int check_inode(struct btree_trans *trans, - struct bch_inode_unpacked *lostfound_inode, - struct btree_iter *iter, - struct bkey_s_c_inode inode, - struct nlink *link) +static void inc_link(struct bch_fs *c, struct snapshots_seen *s, + struct nlink_table *links, + u64 range_start, u64 range_end, u64 inum, u32 snapshot) { - struct bch_fs *c = trans->c; - struct bch_inode_unpacked u; - bool do_update = false; - int ret = 0; - - ret = bch2_inode_unpack(inode, &u); + struct nlink *link, key = { + .inum = inum, .snapshot = U32_MAX, + }; - bch2_btree_trans_unlock(trans); + if (inum < range_start || inum >= range_end) + return; - if (bch2_fs_inconsistent_on(ret, c, - "error unpacking inode %llu in fsck", - inode.k->p.inode)) - return ret; + link = __inline_bsearch(&key, links->d, links->nr, + sizeof(links->d[0]), nlink_cmp); + if (!link) + return; - if (link) { - ret = check_inode_nlink(c, lostfound_inode, &u, link, - &do_update); - if (ret) - return ret; - } + while (link > links->d && link[0].inum == link[-1].inum) + --link; - if (u.bi_flags & BCH_INODE_UNLINKED) { - fsck_err_on(c->sb.clean, c, - "filesystem marked clean, " - "but inode %llu unlinked", - u.bi_inum); + for (; link < links->d + links->nr && link->inum == inum; link++) + if (ref_visible(c, s, snapshot, link->snapshot)) { + link->count++; + if (link->snapshot >= snapshot) + break; + } +} - bch_verbose(c, "deleting inode %llu", u.bi_inum); +noinline_for_stack +static int check_nlinks_find_hardlinks(struct bch_fs *c, + struct nlink_table *t, + u64 start, u64 *end) +{ + struct btree_trans trans; + struct btree_iter iter; + struct bkey_s_c k; + struct bkey_s_c_inode inode; + struct bch_inode_unpacked u; + int ret = 0; - ret = bch2_inode_rm(c, u.bi_inum); - if (ret) - bch_err(c, "error in fs gc: error %i " - "while deleting inode", ret); - return ret; - } + bch2_trans_init(&trans, c, BTREE_ITER_MAX, 0); - if (u.bi_flags & BCH_INODE_I_SIZE_DIRTY) { - fsck_err_on(c->sb.clean, c, - "filesystem marked clean, " - "but inode %llu has i_size dirty", - u.bi_inum); + for_each_btree_key(&trans, iter, BTREE_ID_inodes, + POS(0, start), + BTREE_ITER_INTENT| + BTREE_ITER_PREFETCH| + BTREE_ITER_ALL_SNAPSHOTS, k, ret) { + if (k.k->type != KEY_TYPE_inode) + continue; - bch_verbose(c, "truncating inode %llu", u.bi_inum); + inode = bkey_s_c_to_inode(k); /* - * XXX: need to truncate partial blocks too here - or ideally - * just switch units to bytes and that issue goes away + * Backpointer and directory structure checks are sufficient for + * directories, since they can't have hardlinks: */ + if (S_ISDIR(le16_to_cpu(inode.v->bi_mode))) + continue; + + /* Should never fail, checked by bch2_inode_invalid: */ + BUG_ON(bch2_inode_unpack(inode, &u)); - ret = bch2_inode_truncate(c, u.bi_inum, u.bi_size); + if (!u.bi_nlink) + continue; + + ret = add_nlink(t, k.k->p.offset, k.k->p.snapshot); if (ret) { - bch_err(c, "error in fs gc: error %i " - "truncating inode", ret); - return ret; + *end = k.k->p.offset; + ret = 0; + break; } - /* - * We truncated without our normal sector accounting hook, just - * make sure we recalculate it: - */ - u.bi_flags |= BCH_INODE_I_SECTORS_DIRTY; - - u.bi_flags &= ~BCH_INODE_I_SIZE_DIRTY; - do_update = true; } + bch2_trans_iter_exit(&trans, &iter); + bch2_trans_exit(&trans); - if (u.bi_flags & BCH_INODE_I_SECTORS_DIRTY) { - s64 sectors; + if (ret) + bch_err(c, "error in fsck: btree error %i while walking inodes", ret); - fsck_err_on(c->sb.clean, c, - "filesystem marked clean, " - "but inode %llu has i_sectors dirty", - u.bi_inum); + return ret; +} - bch_verbose(c, "recounting sectors for inode %llu", - u.bi_inum); +noinline_for_stack +static int check_nlinks_walk_dirents(struct bch_fs *c, struct nlink_table *links, + u64 range_start, u64 range_end) +{ + struct btree_trans trans; + struct snapshots_seen s; + struct btree_iter iter; + struct bkey_s_c k; + struct bkey_s_c_dirent d; + int ret; - sectors = bch2_count_inode_sectors(trans, u.bi_inum); - if (sectors < 0) { - bch_err(c, "error in fs gc: error %i " - "recounting inode sectors", - (int) sectors); - return sectors; - } + snapshots_seen_init(&s); - u.bi_sectors = sectors; - u.bi_flags &= ~BCH_INODE_I_SECTORS_DIRTY; - do_update = true; - } + bch2_trans_init(&trans, c, BTREE_ITER_MAX, 0); - if (do_update) { - struct bkey_inode_buf p; + for_each_btree_key(&trans, iter, BTREE_ID_dirents, POS_MIN, + BTREE_ITER_INTENT| + BTREE_ITER_PREFETCH| + BTREE_ITER_ALL_SNAPSHOTS, k, ret) { + ret = snapshots_seen_update(c, &s, k.k->p); + if (ret) + break; + + switch (k.k->type) { + case KEY_TYPE_dirent: + d = bkey_s_c_to_dirent(k); - bch2_inode_pack(&p, &u); - bch2_trans_update(trans, BTREE_INSERT_ENTRY(iter, &p.inode.k_i)); + if (d.v->d_type != DT_DIR && + d.v->d_type != DT_SUBVOL) + inc_link(c, &s, links, range_start, range_end, + le64_to_cpu(d.v->d_inum), + d.k->p.snapshot); + break; + } - ret = bch2_trans_commit(trans, NULL, NULL, - BTREE_INSERT_NOFAIL| - BTREE_INSERT_LAZY_RW); - if (ret && ret != -EINTR) - bch_err(c, "error in fs gc: error %i " - "updating inode", ret); + bch2_trans_cond_resched(&trans); } -fsck_err: + bch2_trans_iter_exit(&trans, &iter); + + if (ret) + bch_err(c, "error in fsck: btree error %i while walking dirents", ret); + + bch2_trans_exit(&trans); + snapshots_seen_exit(&s); return ret; } noinline_for_stack -static int bch2_gc_walk_inodes(struct bch_fs *c, - struct bch_inode_unpacked *lostfound_inode, - nlink_table *links, +static int check_nlinks_update_hardlinks(struct bch_fs *c, + struct nlink_table *links, u64 range_start, u64 range_end) { struct btree_trans trans; - struct btree_iter *iter; + struct btree_iter iter; struct bkey_s_c k; - struct nlink *link, zero_links = { 0, 0 }; - struct genradix_iter nlinks_iter; - int ret = 0, ret2 = 0; - u64 nlinks_pos; + struct bkey_s_c_inode inode; + struct bch_inode_unpacked u; + struct nlink *link = links->d; + int ret = 0; + + bch2_trans_init(&trans, c, BTREE_ITER_MAX, 0); - bch2_trans_init(&trans, c); + for_each_btree_key(&trans, iter, BTREE_ID_inodes, + POS(0, range_start), + BTREE_ITER_INTENT| + BTREE_ITER_PREFETCH| + BTREE_ITER_ALL_SNAPSHOTS, k, ret) { + if (k.k->p.offset >= range_end) + break; - iter = bch2_trans_get_iter(&trans, BTREE_ID_INODES, - POS(range_start, 0), 0); - nlinks_iter = genradix_iter_init(links, 0); + if (k.k->type != KEY_TYPE_inode) + continue; - while ((k = bch2_btree_iter_peek(iter)).k && - !(ret2 = bkey_err(k))) { -peek_nlinks: link = genradix_iter_peek(&nlinks_iter, links); + inode = bkey_s_c_to_inode(k); + if (S_ISDIR(le16_to_cpu(inode.v->bi_mode))) + continue; - if (!link && (!k.k || iter->pos.inode >= range_end)) - break; + BUG_ON(bch2_inode_unpack(inode, &u)); - nlinks_pos = range_start + nlinks_iter.pos; - if (iter->pos.inode > nlinks_pos) { - /* Should have been caught by dirents pass: */ - need_fsck_err_on(link && link->count, c, - "missing inode %llu (nlink %u)", - nlinks_pos, link->count); - genradix_iter_advance(&nlinks_iter, links); - goto peek_nlinks; - } + if (!u.bi_nlink) + continue; - if (iter->pos.inode < nlinks_pos || !link) - link = &zero_links; + while ((cmp_int(link->inum, k.k->p.offset) ?: + cmp_int(link->snapshot, k.k->p.snapshot)) < 0) { + link++; + BUG_ON(link >= links->d + links->nr); + } - if (k.k && k.k->type == KEY_TYPE_inode) { - ret = check_inode(&trans, lostfound_inode, iter, - bkey_s_c_to_inode(k), link); - BUG_ON(ret == -EINTR); + if (fsck_err_on(bch2_inode_nlink_get(&u) != link->count, c, + "inode %llu has wrong i_nlink (type %u i_nlink %u, should be %u)", + u.bi_inum, mode_to_type(u.bi_mode), + bch2_inode_nlink_get(&u), link->count)) { + bch2_inode_nlink_set(&u, link->count); + + ret = __bch2_trans_do(&trans, NULL, NULL, + BTREE_INSERT_NOFAIL| + BTREE_INSERT_LAZY_RW, + bch2_btree_iter_traverse(&iter) ?: + bch2_inode_write(&trans, &iter, &u)); if (ret) - break; - } else { - /* Should have been caught by dirents pass: */ - need_fsck_err_on(link->count, c, - "missing inode %llu (nlink %u)", - nlinks_pos, link->count); + bch_err(c, "error in fsck: error %i updating inode", ret); } - - if (nlinks_pos == iter->pos.inode) - genradix_iter_advance(&nlinks_iter, links); - - bch2_btree_iter_next(iter); - bch2_trans_cond_resched(&trans); } fsck_err: + bch2_trans_iter_exit(&trans, &iter); bch2_trans_exit(&trans); - if (ret2) - bch_err(c, "error in fs gc: btree error %i while walking inodes", ret2); + if (ret) + bch_err(c, "error in fsck: btree error %i while walking inodes", ret); - return ret ?: ret2; + return ret; } noinline_for_stack -static int check_inode_nlinks(struct bch_fs *c, - struct bch_inode_unpacked *lostfound_inode) +static int check_nlinks(struct bch_fs *c) { - nlink_table links; + struct nlink_table links = { 0 }; u64 this_iter_range_start, next_iter_range_start = 0; int ret = 0; bch_verbose(c, "checking inode nlinks"); - genradix_init(&links); - do { this_iter_range_start = next_iter_range_start; next_iter_range_start = U64_MAX; - ret = bch2_gc_walk_dirents(c, &links, + ret = check_nlinks_find_hardlinks(c, &links, + this_iter_range_start, + &next_iter_range_start); + + ret = check_nlinks_walk_dirents(c, &links, this_iter_range_start, - &next_iter_range_start); + next_iter_range_start); if (ret) break; - ret = bch2_gc_walk_inodes(c, lostfound_inode, &links, + ret = check_nlinks_update_hardlinks(c, &links, this_iter_range_start, next_iter_range_start); if (ret) break; - genradix_free(&links); + links.nr = 0; } while (next_iter_range_start != U64_MAX); - genradix_free(&links); + kvfree(links.d); return ret; } -noinline_for_stack -static int check_inodes_fast(struct bch_fs *c) -{ - struct btree_trans trans; - struct btree_iter *iter; - struct bkey_s_c k; - struct bkey_s_c_inode inode; - int ret = 0, ret2; - - bch2_trans_init(&trans, c); - - iter = bch2_trans_get_iter(&trans, BTREE_ID_INODES, - POS_MIN, 0); - - for_each_btree_key_continue(iter, 0, k) { - if (k.k->type != KEY_TYPE_inode) - continue; - - inode = bkey_s_c_to_inode(k); - - if (inode.v->bi_flags & - (BCH_INODE_I_SIZE_DIRTY| - BCH_INODE_I_SECTORS_DIRTY| - BCH_INODE_UNLINKED)) { - ret = check_inode(&trans, NULL, iter, inode, NULL); - BUG_ON(ret == -EINTR); - if (ret) - break; - } - } - - ret2 = bch2_trans_exit(&trans); - - return ret ?: ret2; -} - /* * Checks for inconsistencies that shouldn't happen, unless we have a bug. * Doesn't fix them yet, mainly because they haven't yet been observed: */ -static int bch2_fsck_full(struct bch_fs *c) +int bch2_fsck_full(struct bch_fs *c) { - struct bch_inode_unpacked root_inode, lostfound_inode; - int ret; - - bch_verbose(c, "starting fsck:"); - ret = check_extents(c) ?: + return bch2_fs_snapshots_check(c) ?: + check_inodes(c, true) ?: + check_subvols(c) ?: + check_extents(c) ?: check_dirents(c) ?: check_xattrs(c) ?: - check_root(c, &root_inode) ?: - check_lostfound(c, &root_inode, &lostfound_inode) ?: - check_directory_structure(c, &lostfound_inode) ?: - check_inode_nlinks(c, &lostfound_inode); - - bch2_flush_fsck_errs(c); - bch_verbose(c, "fsck done"); - - return ret; -} - -static int bch2_fsck_inode_nlink(struct bch_fs *c) -{ - struct bch_inode_unpacked root_inode, lostfound_inode; - int ret; - - bch_verbose(c, "checking inode link counts:"); - ret = check_root(c, &root_inode) ?: - check_lostfound(c, &root_inode, &lostfound_inode) ?: - check_inode_nlinks(c, &lostfound_inode); - - bch2_flush_fsck_errs(c); - bch_verbose(c, "done"); - - return ret; -} - -static int bch2_fsck_walk_inodes_only(struct bch_fs *c) -{ - int ret; - - bch_verbose(c, "walking inodes:"); - ret = check_inodes_fast(c); - - bch2_flush_fsck_errs(c); - bch_verbose(c, "done"); - - return ret; + check_root(c) ?: + check_directory_structure(c) ?: + check_nlinks(c); } -int bch2_fsck(struct bch_fs *c) +int bch2_fsck_walk_inodes_only(struct bch_fs *c) { - if (c->opts.fsck) - return bch2_fsck_full(c); - - if (c->sb.clean) - return 0; - - return c->sb.features & (1 << BCH_FEATURE_ATOMIC_NLINK) - ? bch2_fsck_walk_inodes_only(c) - : bch2_fsck_inode_nlink(c); + return check_inodes(c, false); }