#include "btrfsck.h"
#include "qgroup-verify.h"
#include "rbtree-utils.h"
+#include "backref.h"
+#include "ulist.h"
static u64 bytes_used = 0;
static u64 total_csum_bytes = 0;
backref->errors |= REF_ERR_DUP_INODE_REF;
if (backref->found_dir_index && backref->index != index)
backref->errors |= REF_ERR_INDEX_UNMATCH;
+ else
+ backref->index = index;
backref->ref_type = itemtype;
- backref->index = index;
backref->found_inode_ref = 1;
} else {
BUG_ON(1);
return 0;
}
+/*
+ * Returns:
+ * < 0 - on error
+ * 1 - if the root with id child_root_id is a child of root parent_root_id
+ * 0 - if the root child_root_id isn't a child of the root parent_root_id but
+ * has other root(s) as parent(s)
+ * 2 - if the root child_root_id doesn't have any parent roots
+ */
static int is_child_root(struct btrfs_root *root, u64 parent_root_id,
u64 child_root_id)
{
btrfs_release_path(&path);
if (ret < 0)
return ret;
- return has_parent? 0 : -1;
+ return has_parent ? 0 : 2;
}
static int process_dir_item(struct btrfs_root *root,
static int walk_down_tree(struct btrfs_root *root, struct btrfs_path *path,
struct walk_control *wc, int *level)
{
+ enum btrfs_tree_block_status status;
u64 bytenr;
u64 ptr_gen;
struct extent_buffer *next;
err = ret;
goto out;
}
+
+ if (btrfs_is_leaf(next))
+ status = btrfs_check_leaf(root, NULL, next);
+ else
+ status = btrfs_check_node(root, NULL, next);
+ if (status != BTRFS_TREE_BLOCK_CLEAN) {
+ free_extent_buffer(next);
+ err = -EIO;
+ goto out;
+ }
+
*level = *level - 1;
free_extent_buffer(path->nodes[*level]);
path->nodes[*level] = next;
if (rec->ino == root_dirid && backref->index == 0)
continue;
- if (delete && backref->found_dir_index &&
- !backref->found_inode_ref) {
+ if (delete &&
+ ((backref->found_dir_index && !backref->found_inode_ref) ||
+ (backref->found_dir_index && backref->found_inode_ref &&
+ (backref->errors & REF_ERR_INDEX_UNMATCH)))) {
ret = delete_dir_index(root, inode_cache, rec, backref);
if (ret)
break;
struct shared_node root_node;
struct root_record *rec;
struct btrfs_root_item *root_item = &root->root_item;
+ enum btrfs_tree_block_status status;
if (root->root_key.objectid != BTRFS_TREE_RELOC_OBJECTID) {
rec = get_root_rec(root_cache, root->root_key.objectid);
wc->active_node = level;
wc->root_level = level;
+ /* We may not have checked the root block, lets do that now */
+ if (btrfs_is_leaf(root->node))
+ status = btrfs_check_leaf(root, NULL, root->node);
+ else
+ status = btrfs_check_node(root, NULL, root->node);
+ if (status != BTRFS_TREE_BLOCK_CLEAN)
+ return -EIO;
+
if (btrfs_root_refs(root_item) > 0 ||
btrfs_disk_key_objectid(&root_item->drop_progress) == 0) {
path.nodes[level] = root->node;
return 0;
}
+static int fix_key_order(struct btrfs_trans_handle *trans,
+ struct btrfs_root *root,
+ struct btrfs_path *path)
+{
+ struct extent_buffer *buf;
+ struct btrfs_key k1, k2;
+ int i;
+ int level = path->lowest_level;
+ int ret;
+
+ buf = path->nodes[level];
+ for (i = 0; i < btrfs_header_nritems(buf) - 1; i++) {
+ if (level) {
+ btrfs_node_key_to_cpu(buf, &k1, i);
+ btrfs_node_key_to_cpu(buf, &k2, i + 1);
+ } else {
+ btrfs_item_key_to_cpu(buf, &k1, i);
+ btrfs_item_key_to_cpu(buf, &k2, i + 1);
+ }
+ if (btrfs_comp_cpu_keys(&k1, &k2) < 0)
+ continue;
+ ret = swap_values(root, path, buf, i);
+ if (ret)
+ break;
+ btrfs_mark_buffer_dirty(buf);
+ i = 0;
+ }
+ return ret;
+}
+
+static int delete_bogus_item(struct btrfs_trans_handle *trans,
+ struct btrfs_root *root,
+ struct btrfs_path *path,
+ struct extent_buffer *buf, int slot)
+{
+ struct btrfs_key key;
+ int nritems = btrfs_header_nritems(buf);
+
+ btrfs_item_key_to_cpu(buf, &key, slot);
+
+ /* These are all the keys we can deal with missing. */
+ if (key.type != BTRFS_DIR_INDEX_KEY &&
+ key.type != BTRFS_EXTENT_ITEM_KEY &&
+ key.type != BTRFS_METADATA_ITEM_KEY &&
+ key.type != BTRFS_TREE_BLOCK_REF_KEY &&
+ key.type != BTRFS_EXTENT_DATA_REF_KEY)
+ return -1;
+
+ printf("Deleting bogus item [%llu,%u,%llu] at slot %d on block %llu\n",
+ (unsigned long long)key.objectid, key.type,
+ (unsigned long long)key.offset, slot, buf->start);
+ memmove_extent_buffer(buf, btrfs_item_nr_offset(slot),
+ btrfs_item_nr_offset(slot + 1),
+ sizeof(struct btrfs_item) *
+ (nritems - slot - 1));
+ btrfs_set_header_nritems(buf, nritems - 1);
+ if (slot == 0) {
+ struct btrfs_disk_key disk_key;
+
+ btrfs_item_key(buf, &disk_key, 0);
+ btrfs_fixup_low_keys(root, path, &disk_key, 1);
+ }
+ btrfs_mark_buffer_dirty(buf);
+ return 0;
+}
+
+static int fix_item_offset(struct btrfs_trans_handle *trans,
+ struct btrfs_root *root,
+ struct btrfs_path *path)
+{
+ struct extent_buffer *buf;
+ int i;
+ int ret = 0;
+
+ /* We should only get this for leaves */
+ BUG_ON(path->lowest_level);
+ buf = path->nodes[0];
+again:
+ for (i = 0; i < btrfs_header_nritems(buf); i++) {
+ unsigned int shift = 0, offset;
+
+ if (i == 0 && btrfs_item_end_nr(buf, i) !=
+ BTRFS_LEAF_DATA_SIZE(root)) {
+ if (btrfs_item_end_nr(buf, i) >
+ BTRFS_LEAF_DATA_SIZE(root)) {
+ ret = delete_bogus_item(trans, root, path,
+ buf, i);
+ if (!ret)
+ goto again;
+ fprintf(stderr, "item is off the end of the "
+ "leaf, can't fix\n");
+ ret = -EIO;
+ break;
+ }
+ shift = BTRFS_LEAF_DATA_SIZE(root) -
+ btrfs_item_end_nr(buf, i);
+ } else if (i > 0 && btrfs_item_end_nr(buf, i) !=
+ btrfs_item_offset_nr(buf, i - 1)) {
+ if (btrfs_item_end_nr(buf, i) >
+ btrfs_item_offset_nr(buf, i - 1)) {
+ ret = delete_bogus_item(trans, root, path,
+ buf, i);
+ if (!ret)
+ goto again;
+ fprintf(stderr, "items overlap, can't fix\n");
+ ret = -EIO;
+ break;
+ }
+ shift = btrfs_item_offset_nr(buf, i - 1) -
+ btrfs_item_end_nr(buf, i);
+ }
+ if (!shift)
+ continue;
+
+ printf("Shifting item nr %d by %u bytes in block %llu\n",
+ i, shift, (unsigned long long)buf->start);
+ offset = btrfs_item_offset_nr(buf, i);
+ memmove_extent_buffer(buf,
+ btrfs_leaf_data(buf) + offset + shift,
+ btrfs_leaf_data(buf) + offset,
+ btrfs_item_size_nr(buf, i));
+ btrfs_set_item_offset(buf, btrfs_item_nr(i),
+ offset + shift);
+ btrfs_mark_buffer_dirty(buf);
+ }
+
+ /*
+ * We may have moved things, in which case we want to exit so we don't
+ * write those changes out. Once we have proper abort functionality in
+ * progs this can be changed to something nicer.
+ */
+ BUG_ON(ret);
+ return ret;
+}
+
/*
- * Attempt to fix basic block failures. Currently we only handle bad key
- * orders, we will cycle through the keys and swap them if necessary.
+ * Attempt to fix basic block failures. If we can't fix it for whatever reason
+ * then just return -EIO.
*/
static int try_to_fix_bad_block(struct btrfs_trans_handle *trans,
struct btrfs_root *root,
struct extent_buffer *buf,
- struct btrfs_disk_key *parent_key,
enum btrfs_tree_block_status status)
{
+ struct ulist *roots;
+ struct ulist_node *node;
+ struct btrfs_root *search_root;
struct btrfs_path *path;
- struct btrfs_key k1, k2;
- int i;
- int level;
+ struct ulist_iterator iter;
+ struct btrfs_key root_key, key;
int ret;
- if (status != BTRFS_TREE_BLOCK_BAD_KEY_ORDER)
- return -EIO;
-
- k1.objectid = btrfs_header_owner(buf);
- k1.type = BTRFS_ROOT_ITEM_KEY;
- k1.offset = (u64)-1;
-
- root = btrfs_read_fs_root(root->fs_info, &k1);
- if (IS_ERR(root))
+ if (status != BTRFS_TREE_BLOCK_BAD_KEY_ORDER &&
+ status != BTRFS_TREE_BLOCK_INVALID_OFFSETS)
return -EIO;
- record_root_in_trans(trans, root);
-
path = btrfs_alloc_path();
if (!path)
return -EIO;
- level = btrfs_header_level(buf);
- path->lowest_level = level;
- path->skip_check_block = 1;
- if (level)
- btrfs_node_key_to_cpu(buf, &k1, 0);
- else
- btrfs_item_key_to_cpu(buf, &k1, 0);
-
- ret = btrfs_search_slot(trans, root, &k1, path, 0, 1);
+ ret = btrfs_find_all_roots(trans, root->fs_info, buf->start,
+ 0, &roots);
if (ret) {
btrfs_free_path(path);
return -EIO;
}
- buf = path->nodes[level];
- for (i = 0; i < btrfs_header_nritems(buf) - 1; i++) {
- if (level) {
- btrfs_node_key_to_cpu(buf, &k1, i);
- btrfs_node_key_to_cpu(buf, &k2, i + 1);
- } else {
- btrfs_item_key_to_cpu(buf, &k1, i);
- btrfs_item_key_to_cpu(buf, &k2, i + 1);
+ ULIST_ITER_INIT(&iter);
+ while ((node = ulist_next(roots, &iter))) {
+ root_key.objectid = node->val;
+ root_key.type = BTRFS_ROOT_ITEM_KEY;
+ root_key.offset = (u64)-1;
+
+ search_root = btrfs_read_fs_root(root->fs_info, &root_key);
+ if (IS_ERR(root)) {
+ ret = -EIO;
+ break;
}
- if (btrfs_comp_cpu_keys(&k1, &k2) < 0)
- continue;
- ret = swap_values(root, path, buf, i);
+
+ record_root_in_trans(trans, search_root);
+
+ path->lowest_level = btrfs_header_level(buf);
+ path->skip_check_block = 1;
+ if (path->lowest_level)
+ btrfs_node_key_to_cpu(buf, &key, 0);
+ else
+ btrfs_item_key_to_cpu(buf, &key, 0);
+ ret = btrfs_search_slot(trans, search_root, &key, path, 0, 1);
+ if (ret) {
+ ret = -EIO;
+ break;
+ }
+ if (status == BTRFS_TREE_BLOCK_BAD_KEY_ORDER)
+ ret = fix_key_order(trans, search_root, path);
+ else if (status == BTRFS_TREE_BLOCK_INVALID_OFFSETS)
+ ret = fix_item_offset(trans, search_root, path);
if (ret)
break;
- btrfs_mark_buffer_dirty(buf);
- i = 0;
+ btrfs_release_path(path);
}
-
+ ulist_free(roots);
btrfs_free_path(path);
return ret;
}
if (status != BTRFS_TREE_BLOCK_CLEAN) {
if (repair)
status = try_to_fix_bad_block(trans, root, buf,
- &rec->parent_key,
status);
if (status != BTRFS_TREE_BLOCK_CLEAN) {
ret = -EIO;