path: root/fs/bcachefs/fsck.c

// SPDX-License-Identifier: GPL-2.0

#include "bcachefs.h"
#include "btree_update.h"
#include "dirent.h"
#include "error.h"
#include "fs.h"
#include "fsck.h"
#include "inode.h"
#include "keylist.h"
#include "super.h"
#include "xattr.h"

#include <linux/dcache.h> /* struct qstr */
#include <linux/generic-radix-tree.h>

#define QSTR(n) { { { .len = strlen(n) } }, .name = n }

static s64 bch2_count_inode_sectors(struct btree_trans *trans, u64 inum)
{
	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, ret) {
		if (k.k->p.inode != inum)
			break;

		if (bkey_extent_is_allocation(k.k))
			sectors += k.k->size;
	}

	bch2_trans_iter_free(trans, iter);

	return ret ?: sectors;
}

static int remove_dirent(struct btree_trans *trans,
			 struct bkey_s_c_dirent dirent)
{
	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;
	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;

	/* Unlock so we don't deadlock, after copying name: */
	bch2_btree_trans_unlock(trans);

	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;
	}

	dir_hash_info = bch2_hash_info_init(c, &dir_inode);

	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;
}

static int reattach_inode(struct bch_fs *c,
			  struct bch_inode_unpacked *lostfound_inode,
			  u64 inum)
{
	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;
	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);

	ret = bch2_btree_insert(c, BTREE_ID_INODES, &packed.inode.k_i,
				NULL, NULL,
				BTREE_INSERT_NOFAIL|
				BTREE_INSERT_LAZY_RW);
	if (ret) {
		bch_err(c, "error %i reattaching inode %llu while updating lost+found",
			ret, inum);
		return ret;
	}

	ret = bch2_dirent_create(c, lostfound_inode->bi_inum,
				 &lostfound_hash_info,
				 DT_DIR, &name, inum, NULL,
				 BTREE_INSERT_NOFAIL|
				 BTREE_INSERT_LAZY_RW);
	if (ret) {
		bch_err(c, "error %i reattaching inode %llu while creating new dirent",
			ret, inum);
		return ret;
	}
	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)
{
	return (struct inode_walker) {
		.cur_inum	= -1,
		.have_inode	= false,
	};
}

static int walk_inode(struct btree_trans *trans,
		      struct inode_walker *w, u64 inum)
{
	if (inum != w->cur_inum) {
		int ret = bch2_inode_find_by_inum_trans(trans, inum,
							&w->inode);

		if (ret && ret != -ENOENT)
			return ret;

		w->have_inode	= !ret;
		w->cur_inum	= inum;
		w->first_this_inode = true;
	} else {
		w->first_this_inode = false;
	}

	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;
}

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)
{
	h->info = bch2_hash_info_init(trans->c, bi);
	hash_stop_chain(trans, h);
}

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)
{
	struct bkey_i *tmp;
	int ret = 0;

	tmp = kmalloc(bkey_bytes(k.k), GFP_KERNEL);
	if (!tmp)
		return -ENOMEM;

	bkey_reassemble(tmp, k);

	ret = bch2_btree_delete_at(trans, k_iter, 0);
	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);
err:
	kfree(tmp);
	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)
{
	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;
}

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)
{
	struct bch_fs *c = trans->c;
	struct btree_iter *iter;
	struct bkey_s_c k2;
	char buf[200];
	int ret = 0;

	if (!bkey_cmp(h->chain->pos, k_iter->pos))
		return 0;

	iter = bch2_trans_copy_iter(trans, h->chain);
	BUG_ON(IS_ERR(iter));

	for_each_btree_key_continue(iter, 0, k2) {
		if (bkey_cmp(k2.k->p, k.k->p) >= 0)
			break;

		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);
	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)
{
	bool hole = (k.k->type != KEY_TYPE_whiteout &&
		     k.k->type != desc.key_type);

	if (hole || k.k->p.offset > h->chain_end + 1)
		hash_stop_chain(trans, h);

	if (!hole) {
		if (!h->chain) {
			h->chain = bch2_trans_copy_iter(trans, k_iter);
			BUG_ON(IS_ERR(h->chain));
		}

		h->chain_end = k.k->p.offset;
	}
}

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;

	hash_set_chain_start(trans, desc, h, k_iter, k);

	if (k.k->type != desc.key_type)
		return true;

	hash = desc.hash_bkey(&h->info, k);

	return hash >= h->chain->pos.offset &&
		hash <= k.k->p.offset;
}

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)
{
	struct bch_fs *c = trans->c;
	char buf[200];
	u64 hashed;
	int ret = 0;

	hash_set_chain_start(trans, desc, h, k_iter, k);

	if (k.k->type != desc.key_type)
		return 0;

	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%