diff options
| -rw-r--r-- | Makefile | 2 | ||||
| -rw-r--r-- | check/lowmem.c | 4568 | ||||
| -rw-r--r-- | check/lowmem.h | 5 | ||||
| -rw-r--r-- | check/main.c | 4555 |
4 files changed, 4574 insertions, 4556 deletions
@@ -113,7 +113,7 @@ cmds_objects = cmds-subvolume.o cmds-filesystem.o cmds-device.o cmds-scrub.o \ cmds-restore.o cmds-rescue.o chunk-recover.o super-recover.o \ cmds-property.o cmds-fi-usage.o cmds-inspect-dump-tree.o \ cmds-inspect-dump-super.o cmds-inspect-tree-stats.o cmds-fi-du.o \ - mkfs/common.o check/common.o + mkfs/common.o check/common.o check/lowmem.o libbtrfs_objects = send-stream.o send-utils.o kernel-lib/rbtree.o btrfs-list.o \ kernel-lib/crc32c.o messages.o \ uuid-tree.o utils-lib.o rbtree-utils.o diff --git a/check/lowmem.c b/check/lowmem.c new file mode 100644 index 00000000..5d17961e --- /dev/null +++ b/check/lowmem.c @@ -0,0 +1,4568 @@ +/* + * This program is free software; you can redistribute it and/or + * modify it under the terms of the GNU General Public + * License v2 as published by the Free Software Foundation. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + * General Public License for more details. + * + * You should have received a copy of the GNU General Public + * License along with this program; if not, write to the + * Free Software Foundation, Inc., 59 Temple Place - Suite 330, + * Boston, MA 021110-1307, USA. + */ + +#include <time.h> +#include "ctree.h" +#include "repair.h" +#include "transaction.h" +#include "messages.h" +#include "disk-io.h" +#include "backref.h" +#include "hash.h" +#include "internal.h" +#include "utils.h" +#include "volumes.h" +#include "check/common.h" +#include "check/lowmem.h" + +static int calc_extent_flag_v2(struct btrfs_root *root, struct extent_buffer *eb, + u64 *flags_ret) +{ + struct btrfs_root *extent_root = root->fs_info->extent_root; + struct btrfs_root_item *ri = &root->root_item; + struct btrfs_extent_inline_ref *iref; + struct btrfs_extent_item *ei; + struct btrfs_key key; + struct btrfs_path *path = NULL; + unsigned long ptr; + unsigned long end; + u64 flags; + u64 owner = 0; + u64 offset; + int slot; + int type; + int ret = 0; + + /* + * Except file/reloc tree, we can not have FULL BACKREF MODE + */ + if (root->objectid < BTRFS_FIRST_FREE_OBJECTID) + goto normal; + + /* root node */ + if (eb->start == btrfs_root_bytenr(ri)) + goto normal; + + if (btrfs_header_flag(eb, BTRFS_HEADER_FLAG_RELOC)) + goto full_backref; + + owner = btrfs_header_owner(eb); + if (owner == root->objectid) + goto normal; + + path = btrfs_alloc_path(); + if (!path) + return -ENOMEM; + + key.objectid = btrfs_header_bytenr(eb); + key.type = (u8)-1; + key.offset = (u64)-1; + + ret = btrfs_search_slot(NULL, extent_root, &key, path, 0, 0); + if (ret <= 0) { + ret = -EIO; + goto out; + } + + if (ret > 0) { + ret = btrfs_previous_extent_item(extent_root, path, + key.objectid); + if (ret) + goto full_backref; + + } + btrfs_item_key_to_cpu(path->nodes[0], &key, path->slots[0]); + + eb = path->nodes[0]; + slot = path->slots[0]; + ei = btrfs_item_ptr(eb, slot, struct btrfs_extent_item); + + flags = btrfs_extent_flags(eb, ei); + if (flags & BTRFS_BLOCK_FLAG_FULL_BACKREF) + goto full_backref; + + ptr = (unsigned long)(ei + 1); + end = (unsigned long)ei + btrfs_item_size_nr(eb, slot); + + if (key.type == BTRFS_EXTENT_ITEM_KEY) + ptr += sizeof(struct btrfs_tree_block_info); + +next: + /* Reached extent item ends normally */ + if (ptr == end) + goto full_backref; + + /* Beyond extent item end, wrong item size */ + if (ptr > end) { + error("extent item at bytenr %llu slot %d has wrong size", + eb->start, slot); + goto full_backref; + } + + iref = (struct btrfs_extent_inline_ref *)ptr; + offset = btrfs_extent_inline_ref_offset(eb, iref); + type = btrfs_extent_inline_ref_type(eb, iref); + + if (type == BTRFS_TREE_BLOCK_REF_KEY && offset == owner) + goto normal; + ptr += btrfs_extent_inline_ref_size(type); + goto next; + +normal: + *flags_ret &= ~BTRFS_BLOCK_FLAG_FULL_BACKREF; + goto out; + +full_backref: + *flags_ret |= BTRFS_BLOCK_FLAG_FULL_BACKREF; +out: + btrfs_free_path(path); + return ret; +} + +/* + * for a tree node or leaf, if it's shared, indeed we don't need to iterate it + * in every fs or file tree check. Here we find its all root ids, and only check + * it in the fs or file tree which has the smallest root id. + */ +static int need_check(struct btrfs_root *root, struct ulist *roots) +{ + struct rb_node *node; + struct ulist_node *u; + + /* + * @roots can be empty if it belongs to tree reloc tree + * In that case, we should always check the leaf, as we can't use + * the tree owner to ensure some other root will check it. + */ + if (roots->nnodes == 1 || roots->nnodes == 0) + return 1; + + node = rb_first(&roots->root); + u = rb_entry(node, struct ulist_node, rb_node); + /* + * current root id is not smallest, we skip it and let it be checked + * in the fs or file tree who hash the smallest root id. + */ + if (root->objectid != u->val) + return 0; + + return 1; +} + +/* + * for a tree node or leaf, we record its reference count, so later if we still + * process this node or leaf, don't need to compute its reference count again. + * + * @bytenr if @bytenr == (u64)-1, only update nrefs->full_backref[level] + */ +static int update_nodes_refs(struct btrfs_root *root, u64 bytenr, + struct extent_buffer *eb, struct node_refs *nrefs, + u64 level, int check_all) +{ + struct ulist *roots; + u64 refs = 0; + u64 flags = 0; + int root_level = btrfs_header_level(root->node); + int check; + int ret; + + if (nrefs->bytenr[level] == bytenr) + return 0; + + if (bytenr != (u64)-1) { + /* the return value of this function seems a mistake */ + ret = btrfs_lookup_extent_info(NULL, root, bytenr, + level, 1, &refs, &flags); + /* temporary fix */ + if (ret < 0 && !check_all) + return ret; + + nrefs->bytenr[level] = bytenr; + nrefs->refs[level] = refs; + nrefs->full_backref[level] = 0; + nrefs->checked[level] = 0; + + if (refs > 1) { + ret = btrfs_find_all_roots(NULL, root->fs_info, bytenr, + 0, &roots); + if (ret) + return -EIO; + + check = need_check(root, roots); + ulist_free(roots); + nrefs->need_check[level] = check; + } else { + if (!check_all) { + nrefs->need_check[level] = 1; + } else { + if (level == root_level) { + nrefs->need_check[level] = 1; + } else { + /* + * The node refs may have not been + * updated if upper needs checking (the + * lowest root_objectid) the node can + * be checked. + */ + nrefs->need_check[level] = + nrefs->need_check[level + 1]; + } + } + } + } + + if (check_all && eb) { + calc_extent_flag_v2(root, eb, &flags); + if (flags & BTRFS_BLOCK_FLAG_FULL_BACKREF) + nrefs->full_backref[level] = 1; + } + + return 0; +} + +/* + * This function only handles BACKREF_MISSING, + * If corresponding extent item exists, increase the ref, else insert an extent + * item and backref. + * + * Returns error bits after repair. + */ +static int repair_tree_block_ref(struct btrfs_trans_handle *trans, + struct btrfs_root *root, + struct extent_buffer *node, + struct node_refs *nrefs, int level, int err) +{ + struct btrfs_fs_info *fs_info = root->fs_info; + struct btrfs_root *extent_root = fs_info->extent_root; + struct btrfs_path path; + struct btrfs_extent_item *ei; + struct btrfs_tree_block_info *bi; + struct btrfs_key key; + struct extent_buffer *eb; + u32 size = sizeof(*ei); + u32 node_size = root->fs_info->nodesize; + int insert_extent = 0; + int skinny_metadata = btrfs_fs_incompat(fs_info, SKINNY_METADATA); + int root_level = btrfs_header_level(root->node); + int generation; + int ret; + u64 owner; + u64 bytenr; + u64 flags = BTRFS_EXTENT_FLAG_TREE_BLOCK; + u64 parent = 0; + + if ((err & BACKREF_MISSING) == 0) + return err; + + WARN_ON(level > BTRFS_MAX_LEVEL); + WARN_ON(level < 0); + + btrfs_init_path(&path); + bytenr = btrfs_header_bytenr(node); + owner = btrfs_header_owner(node); + generation = btrfs_header_generation(node); + + key.objectid = bytenr; + key.type = (u8)-1; + key.offset = (u64)-1; + + /* Search for the extent item */ + ret = btrfs_search_slot(NULL, extent_root, &key, &path, 0, 0); + if (ret <= 0) { + ret = -EIO; + goto out; + } + + ret = btrfs_previous_extent_item(extent_root, &path, bytenr); + if (ret) + insert_extent = 1; + + /* calculate if the extent item flag is full backref or not */ + if (nrefs->full_backref[level] != 0) + flags |= BTRFS_BLOCK_FLAG_FULL_BACKREF; + + /* insert an extent item */ + if (insert_extent) { + struct btrfs_disk_key copy_key; + + generation = btrfs_header_generation(node); + + if (level < root_level && nrefs->full_backref[level + 1] && + owner != root->objectid) { + flags |= BTRFS_BLOCK_FLAG_FULL_BACKREF; + } + + key.objectid = bytenr; + if (!skinny_metadata) { + key.type = BTRFS_EXTENT_ITEM_KEY; + key.offset = node_size; + size += sizeof(*bi); + } else { + key.type = BTRFS_METADATA_ITEM_KEY; + key.offset = level; + } + + btrfs_release_path(&path); + ret = btrfs_insert_empty_item(trans, extent_root, &path, &key, + size); + if (ret) + goto out; + + eb = path.nodes[0]; + ei = btrfs_item_ptr(eb, path.slots[0], struct btrfs_extent_item); + + btrfs_set_extent_refs(eb, ei, 0); + btrfs_set_extent_generation(eb, ei, generation); + btrfs_set_extent_flags(eb, ei, flags); + + if (!skinny_metadata) { + bi = (struct btrfs_tree_block_info *)(ei + 1); + memset_extent_buffer(eb, 0, (unsigned long)bi, + sizeof(*bi)); + btrfs_set_disk_key_objectid(©_key, root->objectid); + btrfs_set_disk_key_type(©_key, 0); + btrfs_set_disk_key_offset(©_key, 0); + + btrfs_set_tree_block_level(eb, bi, level); + btrfs_set_tree_block_key(eb, bi, ©_key); + } + btrfs_mark_buffer_dirty(eb); + printf("Added an extent item [%llu %u]\n", bytenr, node_size); + btrfs_update_block_group(extent_root, bytenr, node_size, 1, 0); + + nrefs->refs[level] = 0; + nrefs->full_backref[level] = + flags & BTRFS_BLOCK_FLAG_FULL_BACKREF; + btrfs_release_path(&path); + } + + if (level < root_level && nrefs->full_backref[level + 1] && + owner != root->objectid) + parent = nrefs->bytenr[level + 1]; + + /* increase the ref */ + ret = btrfs_inc_extent_ref(trans, extent_root, bytenr, node_size, + parent, root->objectid, level, 0); + + nrefs->refs[level]++; +out: + btrfs_release_path(&path); + if (ret) { + error( + "failed to repair tree block ref start %llu root %llu due to %s", + bytenr, root->objectid, strerror(-ret)); + } else { + printf("Added one tree block ref start %llu %s %llu\n", + bytenr, parent ? "parent" : "root", + parent ? parent : root->objectid); + err &= ~BACKREF_MISSING; + } + + return err; +} + +/* + * Update global fs information. + */ +static void account_bytes(struct btrfs_root *root, struct btrfs_path *path, + int level) +{ + u32 free_nrs; + struct extent_buffer *eb = path->nodes[level]; + + total_btree_bytes += eb->len; + if (fs_root_objectid(root->objectid)) + total_fs_tree_bytes += eb->len; + if (btrfs_header_owner(eb) == BTRFS_EXTENT_TREE_OBJECTID) + total_extent_tree_bytes += eb->len; + + if (level == 0) { + btree_space_waste += btrfs_leaf_free_space(root, eb); + } else { + free_nrs = (BTRFS_NODEPTRS_PER_BLOCK(root->fs_info) - + btrfs_header_nritems(eb)); + btree_space_waste += free_nrs * sizeof(struct btrfs_key_ptr); + } +} + +/* + * Find the @index according by @ino and name. + * Notice:time efficiency is O(N) + * + * @root: the root of the fs/file tree + * @index_ret: the index as return value + * @namebuf: the name to match + * @name_len: the length of name to match + * @file_type: the file_type of INODE_ITEM to match + * + * Returns 0 if found and *@index_ret will be modified with right value + * Returns< 0 not found and *@index_ret will be (u64)-1 + */ +static int find_dir_index(struct btrfs_root *root, u64 dirid, u64 location_id, + u64 *index_ret, char *namebuf, u32 name_len, + u8 file_type) +{ + struct btrfs_path path; + struct extent_buffer *node; + struct btrfs_dir_item *di; + struct btrfs_key key; + struct btrfs_key location; + char name[BTRFS_NAME_LEN] = {0}; + + u32 total; + u32 cur = 0; + u32 len; + u32 data_len; + u8 filetype; + int slot; + int ret; + + ASSERT(index_ret); + + /* search from the last index */ + key.objectid = dirid; + key.offset = (u64)-1; + key.type = BTRFS_DIR_INDEX_KEY; + + btrfs_init_path(&path); + ret = btrfs_search_slot(NULL, root, &key, &path, 0, 0); + if (ret < 0) + return ret; + +loop: + ret = btrfs_previous_item(root, &path, dirid, BTRFS_DIR_INDEX_KEY); + if (ret) { + ret = -ENOENT; + *index_ret = (64)-1; + goto out; + } + /* Check whether inode_id/filetype/name match */ + node = path.nodes[0]; + slot = path.slots[0]; + di = btrfs_item_ptr(node, slot, struct btrfs_dir_item); + total = btrfs_item_size_nr(node, slot); + while (cur < total) { + ret = -ENOENT; + len = btrfs_dir_name_len(node, di); + data_len = btrfs_dir_data_len(node, di); + + btrfs_dir_item_key_to_cpu(node, di, &location); + if (location.objectid != location_id || + location.type != BTRFS_INODE_ITEM_KEY || + location.offset != 0) + goto next; + + filetype = btrfs_dir_type(node, di); + if (file_type != filetype) + goto next; + + if (len > BTRFS_NAME_LEN) + len = BTRFS_NAME_LEN; + + read_extent_buffer(node, name, (unsigned long)(di + 1), len); + if (len != name_len || strncmp(namebuf, name, len)) + goto next; + + btrfs_item_key_to_cpu(path.nodes[0], &key, path.slots[0]); + *index_ret = key.offset; + ret = 0; + goto out; +next: + len += sizeof(*di) + data_len; + di = (struct btrfs_dir_item *)((char *)di + len); + cur += len; + } + goto loop; + +out: + btrfs_release_path(&path); + return ret; +} + +/* + * Find DIR_ITEM/DIR_INDEX for the given key and check it with the specified + * INODE_REF/INODE_EXTREF match. + * + * @root: the root of the fs/file tree + * @key: the key of the DIR_ITEM/DIR_INDEX, key->offset will be right + * value while find index + * @location_key: location key of the struct btrfs_dir_item to match + * @name: the name to match + * @namelen: the length of name + * @file_type: the type of file to math + * + * Return 0 if no error occurred. + * Return DIR_ITEM_MISSING/DIR_INDEX_MISSING if couldn't find + * DIR_ITEM/DIR_INDEX + * Return DIR_ITEM_MISMATCH/DIR_INDEX_MISMATCH if INODE_REF/INODE_EXTREF + * and DIR_ITEM/DIR_INDEX mismatch + */ +static int find_dir_item(struct btrfs_root *root, struct btrfs_key *key, + struct btrfs_key *location_key, char *name, + u32 namelen, u8 file_type) +{ + struct btrfs_path path; + struct extent_buffer *node; + struct btrfs_dir_item *di; + struct btrfs_key location; + char namebuf[BTRFS_NAME_LEN] = {0}; + u32 total; + u32 cur = 0; + u32 len; + u32 data_len; + u8 filetype; + int slot; + int ret; + + /* get the index by traversing all index */ + if (key->type == BTRFS_DIR_INDEX_KEY && key->offset == (u64)-1) { + ret = find_dir_index(root, key->objectid, + location_key->objectid, &key->offset, + name, namelen, file_type); + if (ret) + ret = DIR_INDEX_MISSING; + return ret; + } + + btrfs_init_path(&path); + ret = btrfs_search_slot(NULL, root, key, &path, 0, 0); + if (ret) { + ret = key->type == BTRFS_DIR_ITEM_KEY ? DIR_ITEM_MISSING : + DIR_INDEX_MISSING; + goto out; + } + + /* Check whether inode_id/filetype/name match */ + node = path.nodes[0]; + slot = path.slots[0]; + di = btrfs_item_ptr(node, slot, struct btrfs_dir_item); + total = btrfs_item_size_nr(node, slot); + while (cur < total) { + ret = key->type == BTRFS_DIR_ITEM_KEY ? + DIR_ITEM_MISMATCH : DIR_INDEX_MISMATCH; + + len = btrfs_dir_name_len(node, di); + data_len = btrfs_dir_data_len(node, di); + + btrfs_dir_item_key_to_cpu(node, di, &location); + if (location.objectid != location_key->objectid || + location.type != location_key->type || + location.offset != location_key->offset) + goto next; + + filetype = btrfs_dir_type(node, di); + if (file_type != filetype) + goto next; + + if (len > BTRFS_NAME_LEN) { + len = BTRFS_NAME_LEN; + warning("root %llu %s[%llu %llu] name too long %u, trimmed", + root->objectid, + key->type == BTRFS_DIR_ITEM_KEY ? + "DIR_ITEM" : "DIR_INDEX", + key->objectid, key->offset, len); + } + read_extent_buffer(node, namebuf, (unsigned long)(di + 1), + len); + if (len != namelen || strncmp(namebuf, name, len)) + goto next; + + ret = 0; + goto out; +next: + len += sizeof(*di) + data_len; + di = (struct btrfs_dir_item *)((char *)di + len); + cur += len; + } + +out: + btrfs_release_path(&path); + return ret; +} + +/* + * The ternary means dir item, dir index and relative inode ref. + * The function handles errs: INODE_MISSING, DIR_INDEX_MISSING + * DIR_INDEX_MISMATCH, DIR_ITEM_MISSING, DIR_ITEM_MISMATCH by the follow + * strategy: + * If two of three is missing or mismatched, delete the existing one. + * If one of three is missing or mismatched, add the missing one. + * + * returns 0 means success. + * returns not 0 means on error; + */ +int repair_ternary_lowmem(struct btrfs_root *root, u64 dir_ino, u64 ino, + u64 index, char *name, int name_len, u8 filetype, + int err) +{ + struct btrfs_trans_handle *trans; + int stage = 0; + int ret = 0; + + /* + * stage shall be one of following valild values: + * 0: Fine, nothing to do. + * 1: One of three is wrong, so add missing one. + * 2: Two of three is wrong, so delete existed one. + */ + if (err & (DIR_INDEX_MISMATCH | DIR_INDEX_MISSING)) + stage++; + if (err & (DIR_ITEM_MISMATCH | DIR_ITEM_MISSING)) + stage++; + if (err & (INODE_REF_MISSING)) + stage++; + + /* stage must be smllarer than 3 */ + ASSERT(stage < 3); + + trans = btrfs_start_transaction(root, 1); + if (stage == 2) { + ret = btrfs_unlink(trans, root, ino, dir_ino, index, name, + name_len, 0); + goto out; + } + if (stage == 1) { + ret = btrfs_add_link(trans, root, ino, dir_ino, name, name_len, + filetype, &index, 1, 1); + goto out; + } +out: + btrfs_commit_transaction(trans, root); + + if (ret) + error("fail to repair inode %llu name %s filetype %u", + ino, name, filetype); + else + printf("%s ref/dir_item of inode %llu name %s filetype %u\n", + stage == 2 ? "Delete" : "Add", + ino, name, filetype); + + return ret; +} + +/* + * Prints inode ref error message + */ +static void print_inode_ref_err(struct btrfs_root *root, struct btrfs_key *key, + u64 index, const char *namebuf, int name_len, + u8 filetype, int err) +{ + if (!err) + return; + + /* root dir error */ + if (key->objectid == BTRFS_FIRST_FREE_OBJECTID) { + error( + "root %llu root dir shouldn't have INODE REF[%llu %llu] name %s", + root->objectid, key->objectid, key->offset, namebuf); + return; + } + + /* normal error */ + if (err & (DIR_ITEM_MISMATCH | DIR_ITEM_MISSING)) + error("root %llu DIR ITEM[%llu %llu] %s name %s filetype %u", + root->objectid, key->offset, + btrfs_name_hash(namebuf, name_len), + err & DIR_ITEM_MISMATCH ? "mismatch" : "missing", + namebuf, filetype); + if (err & (DIR_INDEX_MISMATCH | DIR_INDEX_MISSING)) + error("root %llu DIR INDEX[%llu %llu] %s name %s filetype %u", + root->objectid, key->offset, index, + err & DIR_ITEM_MISMATCH ? "mismatch" : "missing", + namebuf, filetype); +} + +/* + * Traverse the given INODE_REF and call find_dir_item() to find related + * DIR_ITEM/DIR_INDEX. + * + * @root: the root of the fs/file tree + * @ref_key: the key of the INODE_REF + * @path the path provides node and slot + * @refs: the count of INODE_REF + * @mode: the st_mode of INODE_ITEM + * @name_ret: returns with the first ref's name + * @name_len_ret: len of the name_ret + * + * Return 0 if no error occurred. + */ +static int check_inode_ref(struct btrfs_root *root, struct btrfs_key *ref_key, + struct btrfs_path *path, char *name_ret, + u32 *namelen_ret, u64 *refs_ret, int mode) +{ + struct btrfs_key key; + struct btrfs_key location; + struct btrfs_inode_ref *ref; + struct extent_buffer *node; + char namebuf[BTRFS_NAME_LEN] = {0}; + u32 total; + u32 cur = 0; + u32 len; + u32 name_len; + u64 index; + int ret; + int err = 0; + int tmp_err; + int slot; + int need_research = 0; + u64 refs; + +begin: + err = 0; + cur = 0; + refs = *refs_ret; + + /* since after repair, path and the dir item may be changed */ + if (need_research) { + need_research = 0; + btrfs_release_path(path); + ret = btrfs_search_slot(NULL, root, ref_key, path, 0, 0); + /* the item was deleted, let path point to the last checked item */ + if (ret > 0) { + if (path->slots[0] == 0) + btrfs_prev_leaf(root, path); + else + path->slots[0]--; + } + if (ret) + goto out; + } + + location.objectid = ref_key->objectid; + location.type = BTRFS_INODE_ITEM_KEY; + location.offset = 0; + node = path->nodes[0]; + slot = path->slots[0]; + + memset(namebuf, 0, sizeof(namebuf) / sizeof(*namebuf)); + ref = btrfs_item_ptr(node, slot, struct btrfs_inode_ref); + total = btrfs_item_size_nr(node, slot); + +next: + /* Update inode ref count */ + refs++; + tmp_err = 0; + index = btrfs_inode_ref_index(node, ref); + name_len = btrfs_inode_ref_name_len(node, ref); + + if (name_len <= BTRFS_NAME_LEN) { + len = name_len; + } else { + len = BTRFS_NAME_LEN; + warning("root %llu INODE_REF[%llu %llu] name too long", + root->objectid, ref_key->objectid, ref_key->offset); + } + + read_extent_buffer(node, namebuf, (unsigned long)(ref + 1), len); + + /* copy the first name found to name_ret */ + if (refs == 1 && name_ret) { + memcpy(name_ret, namebuf, len); + *namelen_ret = len; + } + + /* Check root dir ref */ + if (ref_key->objectid == BTRFS_FIRST_FREE_OBJECTID) { + if (index != 0 || len != strlen("..") || + strncmp("..", namebuf, len) || + ref_key->offset != BTRFS_FIRST_FREE_OBJECTID) { + /* set err bits then repair will delete the ref */ + err |= DIR_INDEX_MISSING; + err |= DIR_ITEM_MISSING; + } + goto end; + } + + /* Find related DIR_INDEX */ + key.objectid = ref_key->offset; + key.type = BTRFS_DIR_INDEX_KEY; + key.offset = index; + tmp_err |= find_dir_item(root, &key, &location, namebuf, len, + imode_to_type(mode)); + + /* Find related dir_item */ + key.objectid = ref_key->offset; + key.type = BTRFS_DIR_ITEM_KEY; + key.offset = btrfs_name_hash(namebuf, len); + tmp_err |= find_dir_item(root, &key, &location, namebuf, len, + imode_to_type(mode)); +end: + if (tmp_err && repair) { + ret = repair_ternary_lowmem(root, ref_key->offset, + ref_key->objectid, index, namebuf, + name_len, imode_to_type(mode), + tmp_err); + if (!ret) { + need_research = 1; + goto begin; + } + } + print_inode_ref_err(root, ref_key, index, namebuf, name_len, + imode_to_type(mode), tmp_err); + err |= tmp_err; + len = sizeof(*ref) + name_len; + ref = (struct btrfs_inode_ref *)((char *)ref + len); + cur += len; + if (cur < total) + goto next; + +out: + *refs_ret = refs; + return err; +} + +/* + * Traverse the given INODE_EXTREF and call find_dir_item() to find related + * DIR_ITEM/DIR_INDEX. + * + * @root: the root of the fs/file tree + * @ref_key: the key of the INODE_EXTREF + * @refs: the count of INODE_EXTREF + * @mode: the st_mode of INODE_ITEM + * + * Return 0 if no error occurred. + */ +static int check_inode_extref(struct btrfs_root *root, + struct btrfs_key *ref_key, + struct extent_buffer *node, int slot, u64 *refs, + int mode) +{ + struct btrfs_key key; + struct btrfs_key location; + struct btrfs_inode_extref *extref; + char namebuf[BTRFS_NAME_LEN] = {0}; + u32 total; + u32 cur = 0; + u32 len; + u32 name_len; + u64 index; + u64 parent; + int ret; + int err = 0; + + location.objectid = ref_key->objectid; + location.type = BTRFS_INODE_ITEM_KEY; + location.offset = 0; + + extref = btrfs_item_ptr(node, slot, struct btrfs_inode_extref); + total = btrfs_item_size_nr(node, slot); + +next: + /* update inode ref count */ + (*refs)++; + name_len = btrfs_inode_extref_name_len(node, extref); + index = btrfs_inode_extref_index(node, extref); + parent = btrfs_inode_extref_parent(node, extref); + if (name_len <= BTRFS_NAME_LEN) { + len = name_len; + } else { + len = BTRFS_NAME_LEN; + warning("root %llu INODE_EXTREF[%llu %llu] name too long", + root->objectid, ref_key->objectid, ref_key->offset); + } + read_extent_buffer(node, namebuf, (unsigned long)(extref + 1), len); + + /* Check root dir ref name */ + if (index == 0 && strncmp(namebuf, "..", name_len)) { + error("root %llu INODE_EXTREF[%llu %llu] ROOT_DIR name shouldn't be %s", + root->objectid, ref_key->objectid, ref_key->offset, + namebuf); + err |= ROOT_DIR_ERROR; + } + + /* find related dir_index */ + key.objectid = parent; + key.type = BTRFS_DIR_INDEX_KEY; + key.offset = index; + ret = find_dir_item(root, &key, &location, namebuf, len, mode); + err |= ret; + + /* find related dir_item */ + key.objectid = parent; + key.type = BTRFS_DIR_ITEM_KEY; + key.offset = btrfs_name_hash(namebuf, len); + ret = find_dir_item(root, &key, &location, namebuf, len, mode); + err |= ret; + + len = sizeof(*extref) + name_len; + extref = (struct btrfs_inode_extref *)((char *)extref + len); + cur += len; + + if (cur < total) + goto next; + + return err; +} + +/* + * Find INODE_REF/INODE_EXTREF for the given key and check it with the specified + * DIR_ITEM/DIR_INDEX match. + * Return with @index_ret. + * + * @root: the root of the fs/file tree + * @key: the key of the INODE_REF/INODE_EXTREF + * @name: the name in the INODE_REF/INODE_EXTREF + * @namelen: the length of name in the INODE_REF/INODE_EXTREF + * @index_ret: the index in the INODE_REF/INODE_EXTREF, + * value (64)-1 means do not check index + * @ext_ref: the EXTENDED_IREF feature + * + * Return 0 if no error occurred. + * Return >0 for error bitmap + */ +static int find_inode_ref(struct btrfs_root *root, struct btrfs_key *key, + char *name, int namelen, u64 *index_ret, + unsigned int ext_ref) +{ + struct btrfs_path path; + struct btrfs_inode_ref *ref; + struct btrfs_inode_extref *extref; + struct extent_buffer *node; + char ref_namebuf[BTRFS_NAME_LEN] = {0}; + u32 total; + u32 cur = 0; + u32 len; + u32 ref_namelen; + u64 ref_index; + u64 parent; + u64 dir_id; + int slot; + int ret; + + ASSERT(index_ret); + + btrfs_init_path(&path); + ret = btrfs_search_slot(NULL, root, key, &path, 0, 0); + if (ret) { + ret = INODE_REF_MISSING; + goto extref; + } + + node = path.nodes[0]; + slot = path.slots[0]; + + ref = btrfs_item_ptr(node, slot, struct btrfs_inode_ref); + total = btrfs_item_size_nr(node, slot); + + /* Iterate all entry of INODE_REF */ + while (cur < total) { + ret = INODE_REF_MISSING; + + ref_namelen = btrfs_inode_ref_name_len(node, ref); + ref_index = btrfs_inode_ref_index(node, ref); + if (*index_ret != (u64)-1 && *index_ret != ref_index) + goto next_ref; + + if (cur + sizeof(*ref) + ref_namelen > total || + ref_namelen > BTRFS_NAME_LEN) { + warning("root %llu INODE %s[%llu %llu] name too long", + root->objectid, + key->type == BTRFS_INODE_REF_KEY ? + "REF" : "EXTREF", + key->objectid, key->offset); + + if (cur + sizeof(*ref) > total) + break; + len = min_t(u32, total - cur - sizeof(*ref), + BTRFS_NAME_LEN); + } else { + len = ref_namelen; + } + + read_extent_buffer(node, ref_namebuf, (unsigned long)(ref + 1), + len); + + if (len != namelen || strncmp(ref_namebuf, name, len)) + goto next_ref; + + *index_ret = ref_index; + ret = 0; + goto out; +next_ref: + len = sizeof(*ref) + ref_namelen; + ref = (struct btrfs_inode_ref *)((char *)ref + len); + cur += len; + } + +extref: + /* Skip if not support EXTENDED_IREF feature */ + if (!ext_ref) + goto out; + + btrfs_release_path(&path); + btrfs_init_path(&path); + + dir_id = key->offset; + key->type = BTRFS_INODE_EXTREF_KEY; + key->offset = btrfs_extref_hash(dir_id, name, namelen); + + ret = btrfs_search_slot(NULL, root, key, &path, 0, 0); + if (ret) { + ret = INODE_REF_MISSING; + goto out; + } + + node = path.nodes[0]; + slot = path.slots[0]; + + extref = btrfs_item_ptr(node, slot, struct btrfs_inode_extref); + cur = 0; + total = btrfs_item_size_nr(node, slot); + + /* Iterate all entry of INODE_EXTREF */ + while (cur < total) { + ret = INODE_REF_MISSING; + + ref_namelen = btrfs_inode_extref_name_len(node, extref); + ref_index = btrfs_inode_extref_index(node, extref); + parent = btrfs_inode_extref_parent(node, extref); + if (*index_ret != (u64)-1 && *index_ret != ref_index) + goto next_extref; + + if (parent != dir_id) + goto next_extref; + + if (ref_namelen <= BTRFS_NAME_LEN) { + len = ref_namelen; + } else { + len = BTRFS_NAME_LEN; + warning("root %llu INODE %s[%llu %llu] name too long", + root->objectid, + key->type == BTRFS_INODE_REF_KEY ? + "REF" : "EXTREF", + key->objectid, key->offset); + } + read_extent_buffer(node, ref_namebuf, + (unsigned long)(extref + 1), len); + + if (len != namelen || strncmp(ref_namebuf, name, len)) + goto next_extref; + + *index_ret = ref_index; + ret = 0; + goto out; + +next_extref: + len = sizeof(*extref) + ref_namelen; + extref = (struct btrfs_inode_extref *)((char *)extref + len); + cur += len; + + } +out: + btrfs_release_path(&path); + return ret; +} + +static int create_inode_item_lowmem(struct btrfs_trans_handle *trans, + struct btrfs_root *root, u64 ino, + u8 filetype) +{ + u32 mode = (filetype == BTRFS_FT_DIR ? S_IFDIR : S_IFREG) | 0755; + + return insert_inode_item(trans, root, ino, 0, 0, 0, mode); +} + +/* + * Insert the missing inode item. + * + * Returns 0 means success. + * Returns <0 means error. + */ +static int repair_inode_item_missing(struct btrfs_root *root, u64 ino, + u8 filetype) +{ + struct btrfs_key key; + struct btrfs_trans_handle *trans; + struct btrfs_path path; + int ret; + + key.objectid = ino; + key.type = BTRFS_INODE_ITEM_KEY; + key.offset = 0; + + btrfs_init_path(&path); + trans = btrfs_start_transaction(root, 1); + if (IS_ERR(trans)) { + ret = -EIO; + goto out; + } + + ret = btrfs_search_slot(trans, root, &key, &path, 1, 1); + if (ret < 0 || !ret) + goto fail; + + /* insert inode item */ + create_inode_item_lowmem(trans, root, ino, filetype); + ret = 0; +fail: + btrfs_commit_transaction(trans, root); +out: + if (ret) + error("failed to repair root %llu INODE ITEM[%llu] missing", + root->objectid, ino); + btrfs_release_path(&path); + return ret; +} + +/* + * Call repair_inode_item_missing and repair_ternary_lowmem to repair + * + * Returns error after repair + */ +static int repair_dir_item(struct btrfs_root *root, u64 dirid, u64 ino, + u64 index, u8 filetype, char *namebuf, u32 name_len, + int err) +{ + int ret; + + if (err & INODE_ITEM_MISSING) { + ret = repair_inode_item_missing(root, ino, filetype); + if (!ret) + err &= ~(INODE_ITEM_MISMATCH | INODE_ITEM_MISSING); + } + + if (err & ~(INODE_ITEM_MISMATCH | INODE_ITEM_MISSING)) { + ret = repair_ternary_lowmem(root, dirid, ino, index, namebuf, + name_len, filetype, err); + if (!ret) { + err &= ~(DIR_INDEX_MISMATCH | DIR_INDEX_MISSING); + err &= ~(DIR_ITEM_MISMATCH | DIR_ITEM_MISSING); + err &= ~(INODE_REF_MISSING); + } + } + return err; +} + +static void print_dir_item_err(struct btrfs_root *root, struct btrfs_key *key, + u64 ino, u64 index, const char *namebuf, + int name_len, u8 filetype, int err) +{ + if (err & (DIR_ITEM_MISMATCH | DIR_ITEM_MISSING)) { + error("root %llu DIR ITEM[%llu %llu] name %s filetype %d %s", + root->objectid, key->objectid, key->offset, namebuf, + filetype, + err & DIR_ITEM_MISMATCH ? "mismath" : "missing"); + } + + if (err & (DIR_INDEX_MISMATCH | DIR_INDEX_MISSING)) { + error("root %llu DIR INDEX[%llu %llu] name %s filetype %d %s", + root->objectid, key->objectid, index, namebuf, filetype, + err & DIR_ITEM_MISMATCH ? "mismath" : "missing"); + } + + if (err & (INODE_ITEM_MISSING | INODE_ITEM_MISMATCH)) { + error( + "root %llu INODE_ITEM[%llu] index %llu name %s filetype %d %s", + root->objectid, ino, index, namebuf, filetype, + err & INODE_ITEM_MISMATCH ? "mismath" : "missing"); + } + + if (err & INODE_REF_MISSING) + error( + "root %llu INODE REF[%llu, %llu] name %s filetype %u missing", + root->objectid, ino, key->objectid, namebuf, filetype); + +} + +/* + * Traverse the given DIR_ITEM/DIR_INDEX and check related INODE_ITEM and + * call find_inode_ref() to check related INODE_REF/INODE_EXTREF. + * + * @root: the root of the fs/file tree + * @key: the key of the INODE_REF/INODE_EXTREF + * @path: the path + * @size: the st_size of the INODE_ITEM + * @ext_ref: the EXTENDED_IREF feature + * + * Return 0 if no error occurred. + * Return DIR_COUNT_AGAIN if the isize of the inode should be recalculated. + */ +static int check_dir_item(struct btrfs_root *root, struct btrfs_key *di_key, + struct btrfs_path *path, u64 *size, + unsigned int ext_ref) +{ + struct btrfs_dir_item *di; + struct btrfs_inode_item *ii; + struct btrfs_key key; + struct btrfs_key location; + struct extent_buffer *node; + int slot; + char namebuf[BTRFS_NAME_LEN] = {0}; + u32 total; + u32 cur = 0; + u32 len; + u32 name_len; + u32 data_len; + u8 filetype; + u32 mode = 0; + u64 index; + int ret; + int err; + int tmp_err; + int need_research = 0; + + /* + * For DIR_ITEM set index to (u64)-1, so that find_inode_ref + * ignore index check. + */ + if (di_key->type == BTRFS_DIR_INDEX_KEY) + index = di_key->offset; + else + index = (u64)-1; +begin: + err = 0; + cur = 0; + + /* since after repair, path and the dir item may be changed */ + if (need_research) { + need_research = 0; + err |= DIR_COUNT_AGAIN; + btrfs_release_path(path); + ret = btrfs_search_slot(NULL, root, di_key, path, 0, 0); + /* the item was deleted, let path point the last checked item */ + if (ret > 0) { + if (path->slots[0] == 0) + btrfs_prev_leaf(root, path); + else + path->slots[0]--; + } + if (ret) + goto out; + } + + node = path->nodes[0]; + slot = path->slots[0]; + + di = btrfs_item_ptr(node, slot, struct btrfs_dir_item); + total = btrfs_item_size_nr(node, slot); + memset(namebuf, 0, sizeof(namebuf) / sizeof(*namebuf)); + + while (cur < total) { + data_len = btrfs_dir_data_len(node, di); + tmp_err = 0; + if (data_len) + error("root %llu %s[%llu %llu] data_len shouldn't be %u", + root->objectid, + di_key->type == BTRFS_DIR_ITEM_KEY ? "DIR_ITEM" : "DIR_INDEX", + di_key->objectid, di_key->offset, data_len); + + name_len = btrfs_dir_name_len(node, di); + if (name_len <= BTRFS_NAME_LEN) { + len = name_len; + } else { + len = BTRFS_NAME_LEN; + warning("root %llu %s[%llu %llu] name too long", + root->objectid, + di_key->type == BTRFS_DIR_ITEM_KEY ? "DIR_ITEM" : "DIR_INDEX", + di_key->objectid, di_key->offset); + } + (*size) += name_len; + read_extent_buffer(node, namebuf, (unsigned long)(di + 1), + len); + filetype = btrfs_dir_type(node, di); + + if (di_key->type == BTRFS_DIR_ITEM_KEY && + di_key->offset != btrfs_name_hash(namebuf, len)) { + err |= -EIO; + error("root %llu DIR_ITEM[%llu %llu] name %s namelen %u filetype %u mismatch with its hash, wanted %llu have %llu", + root->objectid, di_key->objectid, di_key->offset, + namebuf, len, filetype, di_key->offset, + btrfs_name_hash(namebuf, len)); + } + + btrfs_dir_item_key_to_cpu(node, di, &location); + /* Ignore related ROOT_ITEM check */ + if (location.type == BTRFS_ROOT_ITEM_KEY) + goto next; + + btrfs_release_path(path); + /* Check relative INODE_ITEM(existence/filetype) */ + ret = btrfs_search_slot(NULL, root, &location, path, 0, 0); + if (ret) { + tmp_err |= INODE_ITEM_MISSING; + goto next; + } + + ii = btrfs_item_ptr(path->nodes[0], path->slots[0], + struct btrfs_inode_item); + mode = btrfs_inode_mode(path->nodes[0], ii); + if (imode_to_type(mode) != filetype) { + tmp_err |= INODE_ITEM_MISMATCH; + goto next; + } + + /* Check relative INODE_REF/INODE_EXTREF */ + key.objectid = location.objectid; + key.type = BTRFS_INODE_REF_KEY; + key.offset = di_key->objectid; + tmp_err |= find_inode_ref(root, &key, namebuf, len, + &index, ext_ref); + + /* check relative INDEX/ITEM */ + key.objectid = di_key->objectid; + if (key.type == BTRFS_DIR_ITEM_KEY) { + key.type = BTRFS_DIR_INDEX_KEY; + key.offset = index; + } else { + key.type = BTRFS_DIR_ITEM_KEY; + key.offset = btrfs_name_hash(namebuf, name_len); + } + + tmp_err |= find_dir_item(root, &key, &location, namebuf, + name_len, filetype); + /* find_dir_item may find index */ + if (key.type == BTRFS_DIR_INDEX_KEY) + index = key.offset; +next: + + if (tmp_err && repair) { + ret = repair_dir_item(root, di_key->objectid, + location.objectid, index, + imode_to_type(mode), namebuf, + name_len, tmp_err); + if (ret != tmp_err) { + need_research = 1; + goto begin; + } + } + btrfs_release_path(path); + print_dir_item_err(root, di_key, location.objectid, index, + namebuf, name_len, filetype, tmp_err); + err |= tmp_err; + len = sizeof(*di) + name_len + data_len; + di = (struct btrfs_dir_item *)((char *)di + len); + cur += len; + + if (di_key->type == BTRFS_DIR_INDEX_KEY && cur < total) { + error("root %llu DIR_INDEX[%llu %llu] should contain only one entry", + root->objectid, di_key->objectid, + di_key->offset); + break; + } + } +out: + /* research path */ + btrfs_release_path(path); + ret = btrfs_search_slot(NULL, root, di_key, path, 0, 0); + if (ret) + err |= ret > 0 ? -ENOENT : ret; + return err; +} + +/* + * Wrapper function of btrfs_punch_hole. + * + * Returns 0 means success. + * Returns not 0 means error. + */ +static int punch_extent_hole(struct btrfs_root *root, u64 ino, u64 start, + u64 len) +{ + struct btrfs_trans_handle *trans; + int ret = 0; + + trans = btrfs_start_transaction(root, 1); + if (IS_ERR(trans)) + return PTR_ERR(trans); + + ret = btrfs_punch_hole(trans, root, ino, start, len); + if (ret) + error("failed to add hole [%llu, %llu] in inode [%llu]", + start, len, ino); + else + printf("Add a hole [%llu, %llu] in inode [%llu]\n", start, len, + ino); + + btrfs_commit_transaction(trans, root); + return ret; +} + +/* + * Check file extent datasum/hole, update the size of the file extents, + * check and update the last offset of the file extent. + * + * @root: the root of fs/file tree. + * @fkey: the key of the file extent. + * @nodatasum: INODE_NODATASUM feature. + * @size: the sum of all EXTENT_DATA items size for this inode. + * @end: the offset of the last extent. + * + * Return 0 if no error occurred. + */ +static int check_file_extent(struct btrfs_root *root, struct btrfs_key *fkey, + struct extent_buffer *node, int slot, + unsigned int nodatasum, u64 *size, u64 *end) +{ + struct btrfs_file_extent_item *fi; + u64 disk_bytenr; + u64 disk_num_bytes; + u64 extent_num_bytes; + u64 extent_offset; + u64 csum_found; /* In byte size, sectorsize aligned */ + u64 search_start; /* Logical range start we search for csum */ + u64 search_len; /* Logical range len we search for csum */ + unsigned int extent_type; + unsigned int is_hole; + int compressed = 0; + int ret; + int err = 0; + + fi = btrfs_item_ptr(node, slot, struct btrfs_file_extent_item); + + /* Check inline extent */ + extent_type = btrfs_file_extent_type(node, fi); + if (extent_type == BTRFS_FILE_EXTENT_INLINE) { + struct btrfs_item *e = btrfs_item_nr(slot); + u32 item_inline_len; + + item_inline_len = btrfs_file_extent_inline_item_len(node, e); + extent_num_bytes = btrfs_file_extent_inline_len(node, slot, fi); + compressed = btrfs_file_extent_compression(node, fi); + if (extent_num_bytes == 0) { + error( + "root %llu EXTENT_DATA[%llu %llu] has empty inline extent", + root->objectid, fkey->objectid, fkey->offset); + err |= FILE_EXTENT_ERROR; + } + if (!compressed && extent_num_bytes != item_inline_len) { + error( + "root %llu EXTENT_DATA[%llu %llu] wrong inline size, have: %llu, expected: %u", + root->objectid, fkey->objectid, fkey->offset, + extent_num_bytes, item_inline_len); + err |= FILE_EXTENT_ERROR; + } + *end += extent_num_bytes; + *size += extent_num_bytes; + return err; + } + + /* Check extent type */ + if (extent_type != BTRFS_FILE_EXTENT_REG && + extent_type != BTRFS_FILE_EXTENT_PREALLOC) { + err |= FILE_EXTENT_ERROR; + error("root %llu EXTENT_DATA[%llu %llu] type bad", + root->objectid, fkey->objectid, fkey->offset); + return err; + } + + /* Check REG_EXTENT/PREALLOC_EXTENT */ + disk_bytenr = btrfs_file_extent_disk_bytenr(node, fi); + disk_num_bytes = btrfs_file_extent_disk_num_bytes(node, fi); + extent_num_bytes = btrfs_file_extent_num_bytes(node, fi); + extent_offset = btrfs_file_extent_offset(node, fi); + compressed = btrfs_file_extent_compression(node, fi); + is_hole = (disk_bytenr == 0) && (disk_num_bytes == 0); + + /* + * Check EXTENT_DATA csum + * + * For plain (uncompressed) extent, we should only check the range + * we're referring to, as it's possible that part of prealloc extent + * has been written, and has csum: + * + * |<--- Original large preallocated extent A ---->| + * |<- Prealloc File Extent ->|<- Regular Extent ->| + * No csum Has csum + * + * For compressed extent, we should check the whole range. + */ + if (!compressed) { + search_start = disk_bytenr + extent_offset; + search_len = extent_num_bytes; + } else { + search_start = disk_bytenr; + search_len = disk_num_bytes; + } + ret = count_csum_range(root->fs_info, search_start, search_len, &csum_found); + if (csum_found > 0 && nodatasum) { + err |= ODD_CSUM_ITEM; + error("root %llu EXTENT_DATA[%llu %llu] nodatasum shouldn't have datasum", + root->objectid, fkey->objectid, fkey->offset); + } else if (extent_type == BTRFS_FILE_EXTENT_REG && !nodatasum && + !is_hole && (ret < 0 || csum_found < search_len)) { + err |= CSUM_ITEM_MISSING; + error("root %llu EXTENT_DATA[%llu %llu] csum missing, have: %llu, expected: %llu", + root->objectid, fkey->objectid, fkey->offset, + csum_found, search_len); + } else if (extent_type == BTRFS_FILE_EXTENT_PREALLOC && csum_found > 0) { + err |= ODD_CSUM_ITEM; + error("root %llu EXTENT_DATA[%llu %llu] prealloc shouldn't have csum, but has: %llu", + root->objectid, fkey->objectid, fkey->offset, csum_found); + } + + /* Check EXTENT_DATA hole */ + if (!no_holes && *end != fkey->offset) { + if (repair) + ret = punch_extent_hole(root, fkey->objectid, + *end, fkey->offset - *end); + if (!repair || ret) { + err |= FILE_EXTENT_ERROR; + error( +"root %llu EXTENT_DATA[%llu %llu] gap exists, expected: EXTENT_DATA[%llu %llu]", + root->objectid, fkey->objectid, fkey->offset, + fkey->objectid, *end); + } + } + + *end += extent_num_bytes; + if (!is_hole) + *size += extent_num_bytes; + + return err; +} + +static int __count_dir_isize(struct btrfs_root *root, u64 ino, int type, + u64 *size_ret) +{ + struct btrfs_key key; + struct btrfs_path path; + u32 len; + struct btrfs_dir_item *di; + int ret; + int cur = 0; + int total = 0; + + ASSERT(size_ret); + *size_ret = 0; + + key.objectid = ino; + key.type = type; + key.offset = (u64)-1; + + btrfs_init_path(&path); + ret = btrfs_search_slot(NULL, root, &key, &path, 0, 0); + if (ret < 0) { + ret = -EIO; + goto out; + } + /* if found, go to spacial case */ + if (ret == 0) + goto special_case; + +loop: + ret = btrfs_previous_item(root, &path, ino, type); + + if (ret) { + ret = 0; + goto out; + } + +special_case: + di = btrfs_item_ptr(path.nodes[0], path.slots[0], struct btrfs_dir_item); + cur = 0; + total = btrfs_item_size_nr(path.nodes[0], path.slots[0]); + + while (cur < total) { + len = btrfs_dir_name_len(path.nodes[0], di); + if (len > BTRFS_NAME_LEN) + len = BTRFS_NAME_LEN; + *size_ret += len; + + len += btrfs_dir_data_len(path.nodes[0], di); + len += sizeof(*di); + di = (struct btrfs_dir_item *)((char *)di + len); + cur += len; + } + goto loop; + +out: + btrfs_release_path(&path); + return ret; +} + +static int count_dir_isize(struct btrfs_root *root, u64 ino, u64 *size) +{ + u64 item_size; + u64 index_size; + int ret; + + ASSERT(size); + ret = __count_dir_isize(root, ino, BTRFS_DIR_ITEM_KEY, &item_size); + if (ret) + goto out; + + ret = __count_dir_isize(root, ino, BTRFS_DIR_INDEX_KEY, &index_size); + if (ret) + goto out; + + *size = item_size + index_size; + +out: + if (ret) + error("failed to count root %llu INODE[%llu] root size", + root->objectid, ino); + return ret; +} + +/* + * Set inode item nbytes to @nbytes + * + * Returns 0 on success + * Returns != 0 on error + */ +static int repair_inode_nbytes_lowmem(struct btrfs_root *root, + struct btrfs_path *path, + u64 ino, u64 nbytes) +{ + struct btrfs_trans_handle *trans; + struct btrfs_inode_item *ii; + struct btrfs_key key; + struct btrfs_key research_key; + int err = 0; + int ret; + + btrfs_item_key_to_cpu(path->nodes[0], &research_key, path->slots[0]); + + key.objectid = ino; + key.type = BTRFS_INODE_ITEM_KEY; + key.offset = 0; + + trans = btrfs_start_transaction(root, 1); + if (IS_ERR(trans)) { + ret = PTR_ERR(trans); + err |= ret; + goto out; + } + + btrfs_release_path(path); + ret = btrfs_search_slot(trans, root, &key, path, 0, 1); + if (ret > 0) + ret = -ENOENT; + if (ret) { + err |= ret; + goto fail; + } + + ii = btrfs_item_ptr(path->nodes[0], path->slots[0], + struct btrfs_inode_item); + btrfs_set_inode_nbytes(path->nodes[0], ii, nbytes); + btrfs_mark_buffer_dirty(path->nodes[0]); +fail: + btrfs_commit_transaction(trans, root); +out: + if (ret) + error("failed to set nbytes in inode %llu root %llu", + ino, root->root_key.objectid); + else + printf("Set nbytes in inode item %llu root %llu\n to %llu", ino, + root->root_key.objectid, nbytes); + + /* research path */ + btrfs_release_path(path); + ret = btrfs_search_slot(NULL, root, &research_key, path, 0, 0); + err |= ret; + + return err; +} + +/* + * Set directory inode isize to @isize. + * + * Returns 0 on success. + * Returns != 0 on error. + */ +static int repair_dir_isize_lowmem(struct btrfs_root *root, + struct btrfs_path *path, + u64 ino, u64 isize) +{ + struct btrfs_trans_handle *trans; + struct btrfs_inode_item *ii; + struct btrfs_key key; + struct btrfs_key research_key; + int ret; + int err = 0; + + btrfs_item_key_to_cpu(path->nodes[0], &research_key, path->slots[0]); + + key.objectid = ino; + key.type = BTRFS_INODE_ITEM_KEY; + key.offset = 0; + + trans = btrfs_start_transaction(root, 1); + if (IS_ERR(trans)) { + ret = PTR_ERR(trans); + err |= ret; + goto out; + } + + btrfs_release_path(path); + ret = btrfs_search_slot(trans, root, &key, path, 0, 1); + if (ret > 0) + ret = -ENOENT; + if (ret) { + err |= ret; + goto fail; + } + + ii = btrfs_item_ptr(path->nodes[0], path->slots[0], + struct btrfs_inode_item); + btrfs_set_inode_size(path->nodes[0], ii, isize); + btrfs_mark_buffer_dirty(path->nodes[0]); +fail: + btrfs_commit_transaction(trans, root); +out: + if (ret) + error("failed to set isize in inode %llu root %llu", + ino, root->root_key.objectid); + else + printf("Set isize in inode %llu root %llu to %llu\n", + ino, root->root_key.objectid, isize); + + btrfs_release_path(path); + ret = btrfs_search_slot(NULL, root, &research_key, path, 0, 0); + err |= ret; + + return err; +} + +/* + * Wrapper function for btrfs_add_orphan_item(). + * + * Returns 0 on success. + * Returns != 0 on error. + */ +static int repair_inode_orphan_item_lowmem(struct btrfs_root *root, + struct btrfs_path *path, u64 ino) +{ + struct btrfs_trans_handle *trans; + struct btrfs_key research_key; + int ret; + int err = 0; + + btrfs_item_key_to_cpu(path->nodes[0], &research_key, path->slots[0]); + + trans = btrfs_start_transaction(root, 1); + if (IS_ERR(trans)) { + ret = PTR_ERR(trans); + err |= ret; + goto out; + } + + btrfs_release_path(path); + ret = btrfs_add_orphan_item(trans, root, path, ino); + err |= ret; + btrfs_commit_transaction(trans, root); +out: + if (ret) + error("failed to add inode %llu as orphan item root %llu", + ino, root->root_key.objectid); + else + printf("Added inode %llu as orphan item root %llu\n", + ino, root->root_key.objectid); + + btrfs_release_path(path); + ret = btrfs_search_slot(NULL, root, &research_key, path, 0, 0); + err |= ret; + + return err; +} + +/* Set inode_item nlink to @ref_count. + * If @ref_count == 0, move it to "lost+found" and increase @ref_count. + * + * Returns 0 on success + */ +static int repair_inode_nlinks_lowmem(struct btrfs_root *root, + struct btrfs_path *path, u64 ino, + const char *name, u32 namelen, + u64 ref_count, u8 filetype, u64 *nlink) +{ + struct btrfs_trans_handle *trans; + struct btrfs_inode_item *ii; + struct btrfs_key key; + struct btrfs_key old_key; + char namebuf[BTRFS_NAME_LEN] = {0}; + int name_len; + int ret; + int ret2; + + /* save the key */ + btrfs_item_key_to_cpu(path->nodes[0], &old_key, path->slots[0]); + + if (name && namelen) { + ASSERT(namelen <= BTRFS_NAME_LEN); + memcpy(namebuf, name, namelen); + name_len = namelen; + } else { + sprintf(namebuf, "%llu", ino); + name_len = count_digits(ino); + printf("Can't find file name for inode %llu, use %s instead\n", + ino, namebuf); + } + + trans = btrfs_start_transaction(root, 1); + if (IS_ERR(trans)) { + ret = PTR_ERR(trans); + goto out; + } + + btrfs_release_path(path); + /* if refs is 0, put it into lostfound */ + if (ref_count == 0) { + ret = link_inode_to_lostfound(trans, root, path, ino, namebuf, + name_len, filetype, &ref_count); + if (ret) + goto fail; + } + + /* reset inode_item's nlink to ref_count */ + key.objectid = ino; + key.type = BTRFS_INODE_ITEM_KEY; + key.offset = 0; + + btrfs_release_path(path); + ret = btrfs_search_slot(trans, root, &key, path, 0, 1); + if (ret > 0) + ret = -ENOENT; + if (ret) + goto fail; + + ii = btrfs_item_ptr(path->nodes[0], path->slots[0], + struct btrfs_inode_item); + btrfs_set_inode_nlink(path->nodes[0], ii, ref_count); + btrfs_mark_buffer_dirty(path->nodes[0]); + + if (nlink) + *nlink = ref_count; +fail: + btrfs_commit_transaction(trans, root); +out: + if (ret) + error( + "fail to repair nlink of inode %llu root %llu name %s filetype %u", + root->objectid, ino, namebuf, filetype); + else + printf("Fixed nlink of inode %llu root %llu name %s filetype %u\n", + root->objectid, ino, namebuf, filetype); + + /* research */ + btrfs_release_path(path); + ret2 = btrfs_search_slot(NULL, root, &old_key, path, 0, 0); + if (ret2 < 0) + return ret |= ret2; + return ret; +} + +/* + * Check INODE_ITEM and related ITEMs (the same inode number) + * 1. check link count + * 2. check inode ref/extref + * 3. check dir item/index + * + * @ext_ref: the EXTENDED_IREF feature + * + * Return 0 if no error occurred. + * Return >0 for error or hit the traversal is done(by error bitmap) + */ +static int check_inode_item(struct btrfs_root *root, struct btrfs_path *path, + unsigned int ext_ref) +{ + struct extent_buffer *node; + struct btrfs_inode_item *ii; + struct btrfs_key key; + struct btrfs_key last_key; + u64 inode_id; + u32 mode; + u64 nlink; + u64 nbytes; + u64 isize; + u64 size = 0; + u64 refs = 0; + u64 extent_end = 0; + u64 extent_size = 0; + unsigned int dir; + unsigned int nodatasum; + int slot; + int ret; + int err = 0; + char namebuf[BTRFS_NAME_LEN] = {0}; + u32 name_len = 0; + + node = path->nodes[0]; + slot = path->slots[0]; + + btrfs_item_key_to_cpu(node, &key, slot); + inode_id = key.objectid; + + if (inode_id == BTRFS_ORPHAN_OBJECTID) { + ret = btrfs_next_item(root, path); + if (ret > 0) + err |= LAST_ITEM; + return err; + } + + ii = btrfs_item_ptr(node, slot, struct btrfs_inode_item); + isize = btrfs_inode_size(node, ii); + nbytes = btrfs_inode_nbytes(node, ii); + mode = btrfs_inode_mode(node, ii); + dir = imode_to_type(mode) == BTRFS_FT_DIR; + nlink = btrfs_inode_nlink(node, ii); + nodatasum = btrfs_inode_flags(node, ii) & BTRFS_INODE_NODATASUM; + + while (1) { + btrfs_item_key_to_cpu(path->nodes[0], &last_key, path->slots[0]); + ret = btrfs_next_item(root, path); + if (ret < 0) { + /* out will fill 'err' rusing current statistics */ + goto out; + } else if (ret > 0) { + err |= LAST_ITEM; + goto out; + } + + node = path->nodes[0]; + slot = path->slots[0]; + btrfs_item_key_to_cpu(node, &key, slot); + if (key.objectid != inode_id) + goto out; + + switch (key.type) { + case BTRFS_INODE_REF_KEY: + ret = check_inode_ref(root, &key, path, namebuf, + &name_len, &refs, mode); + err |= ret; + break; + case BTRFS_INODE_EXTREF_KEY: + if (key.type == BTRFS_INODE_EXTREF_KEY && !ext_ref) + warning("root %llu EXTREF[%llu %llu] isn't supported", + root->objectid, key.objectid, + key.offset); + ret = check_inode_extref(root, &key, node, slot, &refs, + mode); + err |= ret; + break; + case BTRFS_DIR_ITEM_KEY: + case BTRFS_DIR_INDEX_KEY: + if (!dir) { + warning("root %llu INODE[%llu] mode %u shouldn't have DIR_INDEX[%llu %llu]", + root->objectid, inode_id, + imode_to_type(mode), key.objectid, + key.offset); + } + ret = check_dir_item(root, &key, path, &size, ext_ref); + err |= ret; + break; + case BTRFS_EXTENT_DATA_KEY: + if (dir) { + warning("root %llu DIR INODE[%llu] shouldn't EXTENT_DATA[%llu %llu]", + root->objectid, inode_id, key.objectid, + key.offset); + } + ret = check_file_extent(root, &key, node, slot, + nodatasum, &extent_size, + &extent_end); + err |= ret; + break; + case BTRFS_XATTR_ITEM_KEY: + break; + default: + error("ITEM[%llu %u %llu] UNKNOWN TYPE", + key.objectid, key.type, key.offset); + } + } + +out: + if (err & LAST_ITEM) { + btrfs_release_path(path); + ret = btrfs_search_slot(NULL, root, &last_key, path, 0, 0); + if (ret) + return err; + } + + /* verify INODE_ITEM nlink/isize/nbytes */ + if (dir) { + if (repair && (err & DIR_COUNT_AGAIN)) { + err &= ~DIR_COUNT_AGAIN; + count_dir_isize(root, inode_id, &size); + } + + if ((nlink != 1 || refs != 1) && repair) { + ret = repair_inode_nlinks_lowmem(root, path, inode_id, + namebuf, name_len, refs, imode_to_type(mode), + &nlink); + } + + if (nlink != 1) { + err |= LINK_COUNT_ERROR; + error("root %llu DIR INODE[%llu] shouldn't have more than one link(%llu)", + root->objectid, inode_id, nlink); + } + + /* + * Just a warning, as dir inode nbytes is just an + * instructive value. + */ + if (!IS_ALIGNED(nbytes, root->fs_info->nodesize)) { + warning("root %llu DIR INODE[%llu] nbytes should be aligned to %u", + root->objectid, inode_id, + root->fs_info->nodesize); + } + + if (isize != size) { + if (repair) + ret = repair_dir_isize_lowmem(root, path, + inode_id, size); + if (!repair || ret) { + err |= ISIZE_ERROR; + error( + "root %llu DIR INODE [%llu] size %llu not equal to %llu", + root->objectid, inode_id, isize, size); + } + } + } else { + if (nlink != refs) { + if (repair) + ret = repair_inode_nlinks_lowmem(root, path, + inode_id, namebuf, name_len, refs, + imode_to_type(mode), &nlink); + if (!repair || ret) { + err |= LINK_COUNT_ERROR; + error( + "root %llu INODE[%llu] nlink(%llu) not equal to inode_refs(%llu)", + root->objectid, inode_id, nlink, refs); + } + } else if (!nlink) { + if (repair) + ret = repair_inode_orphan_item_lowmem(root, + path, inode_id); + if (!repair || ret) { + err |= ORPHAN_ITEM; + error("root %llu INODE[%llu] is orphan item", + root->objectid, inode_id); + } + } + + if (!nbytes && !no_holes && extent_end < isize) { + if (repair) + ret = punch_extent_hole(root, inode_id, + extent_end, isize - extent_end); + if (!repair || ret) { + err |= NBYTES_ERROR; + error( + "root %llu INODE[%llu] size %llu should have a file extent hole", + root->objectid, inode_id, isize); + } + } + + if (nbytes != extent_size) { + if (repair) + ret = repair_inode_nbytes_lowmem(root, path, + inode_id, extent_size); + if (!repair || ret) { + err |= NBYTES_ERROR; + error( + "root %llu INODE[%llu] nbytes %llu not equal to extent_size %llu", + root->objectid, inode_id, nbytes, + extent_size); + } + } + } + + if (err & LAST_ITEM) + btrfs_next_item(root, path); + return err; +} + +/* + * Returns >0 Found error, not fatal, should continue + * Returns <0 Fatal error, must exit the whole check + * Returns 0 No errors found + */ +static int process_one_leaf_v2(struct btrfs_root *root, struct btrfs_path *path, + struct node_refs *nrefs, int *level, int ext_ref) +{ + struct extent_buffer *cur = path->nodes[0]; + struct btrfs_key key; + u64 cur_bytenr; + u32 nritems; + u64 first_ino = 0; + int root_level = btrfs_header_level(root->node); + int i; + int ret = 0; /* Final return value */ + int err = 0; /* Positive error bitmap */ + + cur_bytenr = cur->start; + + /* skip to first inode item or the first inode number change */ + nritems = btrfs_header_nritems(cur); + for (i = 0; i < nritems; i++) { + btrfs_item_key_to_cpu(cur, &key, i); + if (i == 0) + first_ino = key.objectid; + if (key.type == BTRFS_INODE_ITEM_KEY || + (first_ino && first_ino != key.objectid)) + break; + } + if (i == nritems) { + path->slots[0] = nritems; + return 0; + } + path->slots[0] = i; + +again: + err |= check_inode_item(root, path, ext_ref); + + /* modify cur since check_inode_item may change path */ + cur = path->nodes[0]; + + if (err & LAST_ITEM) + goto out; + + /* still have inode items in thie leaf */ + if (cur->start == cur_bytenr) + goto again; + + /* + * we have switched to another leaf, above nodes may + * have changed, here walk down the path, if a node + * or leaf is shared, check whether we can skip this + * node or leaf. + */ + for (i = root_level; i >= 0; i--) { + if (path->nodes[i]->start == nrefs->bytenr[i]) + continue; + + ret = update_nodes_refs(root, path->nodes[i]->start, + path->nodes[i], nrefs, i, 0); + if (ret) + goto out; + + if (!nrefs->need_check[i]) { + *level += 1; + break; + } + } + + for (i = 0; i < *level; i++) { + free_extent_buffer(path->nodes[i]); + path->nodes[i] = NULL; + } +out: + err &= ~LAST_ITEM; + if (err && !ret) + ret = err; + return ret; +} + +/* + * @level if @level == -1 means extent data item + * else normal treeblocl. + */ +static int should_check_extent_strictly(struct btrfs_root *root, + struct node_refs *nrefs, int level) +{ + int root_level = btrfs_header_level(root->node); + + if (level > root_level || level < -1) + return 1; + if (level == root_level) + return 1; + /* + * if the upper node is marked full backref, it should contain shared + * backref of the parent (except owner == root->objectid). + */ + while (++level <= root_level) + if (nrefs->refs[level] > 1) + return 0; + + return 1; +} + +static int check_extent_inline_ref(struct extent_buffer *eb, + struct btrfs_key *key, struct btrfs_extent_inline_ref *iref) +{ + int ret; + u8 type = btrfs_extent_inline_ref_type(eb, iref); + + switch (type) { + case BTRFS_TREE_BLOCK_REF_KEY: + case BTRFS_EXTENT_DATA_REF_KEY: + case BTRFS_SHARED_BLOCK_REF_KEY: + case BTRFS_SHARED_DATA_REF_KEY: + ret = 0; + break; + default: + error("extent[%llu %u %llu] has unknown ref type: %d", + key->objectid, key->type, key->offset, type); + ret = UNKNOWN_TYPE; + break; + } + + return ret; +} + +/* + * Check backrefs of a tree block given by @bytenr or @eb. + * + * @root: the root containing the @bytenr or @eb + * @eb: tree block extent buffer, can be NULL + * @bytenr: bytenr of the tree block to search + * @level: tree level of the tree block + * @owner: owner of the tree block + * + * Return >0 for any error found and output error message + * Return 0 for no error found + */ +static int check_tree_block_ref(struct btrfs_root *root, + struct extent_buffer *eb, u64 bytenr, + int level, u64 owner, struct node_refs *nrefs) +{ + struct btrfs_key key; + struct btrfs_root *extent_root = root->fs_info->extent_root; + struct btrfs_path path; + struct btrfs_extent_item *ei; + struct btrfs_extent_inline_ref *iref; + struct extent_buffer *leaf; + unsigned long end; + unsigned long ptr; + int slot; + int skinny_level; + int root_level = btrfs_header_level(root->node); + int type; + u32 nodesize = root->fs_info->nodesize; + u32 item_size; + u64 offset; + int found_ref = 0; + int err = 0; + int ret; + int strict = 1; + int parent = 0; + + btrfs_init_path(&path); + key.objectid = bytenr; + if (btrfs_fs_incompat(root->fs_info, SKINNY_METADATA)) + key.type = BTRFS_METADATA_ITEM_KEY; + else + key.type = BTRFS_EXTENT_ITEM_KEY; + key.offset = (u64)-1; + + /* Search for the backref in extent tree */ + ret = btrfs_search_slot(NULL, extent_root, &key, &path, 0, 0); + if (ret < 0) { + err |= BACKREF_MISSING; + goto out; + } + ret = btrfs_previous_extent_item(extent_root, &path, bytenr); + if (ret) { + err |= BACKREF_MISSING; + goto out; + } + + leaf = path.nodes[0]; + slot = path.slots[0]; + btrfs_item_key_to_cpu(leaf, &key, slot); + + ei = btrfs_item_ptr(leaf, slot, struct btrfs_extent_item); + + if (key.type == BTRFS_METADATA_ITEM_KEY) { + skinny_level = (int)key.offset; + iref = (struct btrfs_extent_inline_ref *)(ei + 1); + } else { + struct btrfs_tree_block_info *info; + + info = (struct btrfs_tree_block_info *)(ei + 1); + skinny_level = btrfs_tree_block_level(leaf, info); + iref = (struct btrfs_extent_inline_ref *)(info + 1); + } + + + if (eb) { + u64 header_gen; + u64 extent_gen; + + /* + * Due to the feature of shared tree blocks, if the upper node + * is a fs root or shared node, the extent of checked node may + * not be updated until the next CoW. + */ + if (nrefs) + strict = should_check_extent_strictly(root, nrefs, + level); + if (!(btrfs_extent_flags(leaf, ei) & + BTRFS_EXTENT_FLAG_TREE_BLOCK)) { + error( + "extent[%llu %u] backref type mismatch, missing bit: %llx", + key.objectid, nodesize, + BTRFS_EXTENT_FLAG_TREE_BLOCK); + err = BACKREF_MISMATCH; + } + header_gen = btrfs_header_generation(eb); + extent_gen = btrfs_extent_generation(leaf, ei); + if (header_gen != extent_gen) { + error( + "extent[%llu %u] backref generation mismatch, wanted: %llu, have: %llu", + key.objectid, nodesize, header_gen, + extent_gen); + err = BACKREF_MISMATCH; + } + if (level != skinny_level) { + error( + "extent[%llu %u] level mismatch, wanted: %u, have: %u", + key.objectid, nodesize, level, skinny_level); + err = BACKREF_MISMATCH; + } + if (!is_fstree(owner) && btrfs_extent_refs(leaf, ei) != 1) { + error( + "extent[%llu %u] is referred by other roots than %llu", + key.objectid, nodesize, root->objectid); + err = BACKREF_MISMATCH; + } + } + + /* + * Iterate the extent/metadata item to find the exact backref + */ + item_size = btrfs_item_size_nr(leaf, slot); + ptr = (unsigned long)iref; + end = (unsigned long)ei + item_size; + + while (ptr < end) { + iref = (struct btrfs_extent_inline_ref *)ptr; + type = btrfs_extent_inline_ref_type(leaf, iref); + offset = btrfs_extent_inline_ref_offset(leaf, iref); + + ret = check_extent_inline_ref(leaf, &key, iref); + if (ret) { + err |= ret; + break; + } + if (type == BTRFS_TREE_BLOCK_REF_KEY) { + if (offset == root->objectid) + found_ref = 1; + if (!strict && owner == offset) + found_ref = 1; + } else if (type == BTRFS_SHARED_BLOCK_REF_KEY) { + /* + * Backref of tree reloc root points to itself, no need + * to check backref any more. + * + * This may be an error of loop backref, but extent tree + * checker should have already handled it. + * Here we only need to avoid infinite iteration. + */ + if (offset == bytenr) { + found_ref = 1; + } else { + /* + * Check if the backref points to valid + * referencer + */ + found_ref = !check_tree_block_ref( root, NULL, + offset, level + 1, owner, + NULL); + } + } + + if (found_ref) + break; + ptr += btrfs_extent_inline_ref_size(type); + } + + /* + * Inlined extent item doesn't have what we need, check + * TREE_BLOCK_REF_KEY + */ + if (!found_ref) { + btrfs_release_path(&path); + key.objectid = bytenr; + key.type = BTRFS_TREE_BLOCK_REF_KEY; + key.offset = root->objectid; + + ret = btrfs_search_slot(NULL, extent_root, &key, &path, 0, 0); + if (!ret) + found_ref = 1; + } + /* + * Finally check SHARED BLOCK REF, any found will be good + * Here we're not doing comprehensive extent backref checking, + * only need to ensure there is some extent referring to this + * tree block. + */ + if (!found_ref) { + btrfs_release_path(&path); + key.objectid = bytenr; + key.type = BTRFS_SHARED_BLOCK_REF_KEY; + key.offset = (u64)-1; + + ret = btrfs_search_slot(NULL, extent_root, &key, &path, 0, 0); + if (ret < 0) { + err |= BACKREF_MISSING; + goto out; + } + ret = btrfs_previous_extent_item(extent_root, &path, bytenr); + if (ret) { + err |= BACKREF_MISSING; + goto out; + } + found_ref = 1; + } + if (!found_ref) + err |= BACKREF_MISSING; +out: + btrfs_release_path(&path); + if (nrefs && strict && + level < root_level && nrefs->full_backref[level + 1]) + parent = nrefs->bytenr[level + 1]; + if (eb && (err & BACKREF_MISSING)) + error( + "extent[%llu %u] backref lost (owner: %llu, level: %u) %s %llu", + bytenr, nodesize, owner, level, + parent ? "parent" : "root", + parent ? parent : root->objectid); + return err; +} + +/* + * If @err contains BACKREF_MISSING then add extent of the + * file_extent_data_item. + * + * Returns error bits after reapir. + */ +static int repair_extent_data_item(struct btrfs_trans_handle *trans, + struct btrfs_root *root, + struct btrfs_path *pathp, + struct node_refs *nrefs, + int err) +{ + struct btrfs_file_extent_item *fi; + struct btrfs_key fi_key; + struct btrfs_key key; + struct btrfs_extent_item *ei; + struct btrfs_path path; + struct btrfs_root *extent_root = root->fs_info->extent_root; + struct extent_buffer *eb; + u64 size; + u64 disk_bytenr; + u64 num_bytes; + u64 parent; + u64 offset; + u64 extent_offset; + u64 file_offset; + int generation; + int slot; + int ret = 0; + + eb = pathp->nodes[0]; + slot = pathp->slots[0]; + btrfs_item_key_to_cpu(eb, &fi_key, slot); + fi = btrfs_item_ptr(eb, slot, struct btrfs_file_extent_item); + + if (btrfs_file_extent_type(eb, fi) == BTRFS_FILE_EXTENT_INLINE || + btrfs_file_extent_disk_bytenr(eb, fi) == 0) + return err; + + file_offset = fi_key.offset; + generation = btrfs_file_extent_generation(eb, fi); + disk_bytenr = btrfs_file_extent_disk_bytenr(eb, fi); + num_bytes = btrfs_file_extent_disk_num_bytes(eb, fi); + extent_offset = btrfs_file_extent_offset(eb, fi); + offset = file_offset - extent_offset; + + /* now repair only adds backref */ + if ((err & BACKREF_MISSING) == 0) + return err; + + /* search extent item */ + key.objectid = disk_bytenr; + key.type = BTRFS_EXTENT_ITEM_KEY; + key.offset = num_bytes; + + btrfs_init_path(&path); + ret = btrfs_search_slot(NULL, extent_root, &key, &path, 0, 0); + if (ret < 0) { + ret = -EIO; + goto out; + } + + /* insert an extent item */ + if (ret > 0) { + key.objectid = disk_bytenr; + key.type = BTRFS_EXTENT_ITEM_KEY; + key.offset = num_bytes; + size = sizeof(*ei); + + btrfs_release_path(&path); + ret = btrfs_insert_empty_item(trans, extent_root, &path, &key, + size); + if (ret) + goto out; + eb = path.nodes[0]; + ei = btrfs_item_ptr(eb, path.slots[0], struct btrfs_extent_item); + + btrfs_set_extent_refs(eb, ei, 0); + btrfs_set_extent_generation(eb, ei, generation); + btrfs_set_extent_flags(eb, ei, BTRFS_EXTENT_FLAG_DATA); + + btrfs_mark_buffer_dirty(eb); + ret = btrfs_update_block_group(extent_root, disk_bytenr, + num_bytes, 1, 0); + btrfs_release_path(&path); + } + + if (nrefs->full_backref[0]) + parent = btrfs_header_bytenr(eb); + else + parent = 0; + + ret = btrfs_inc_extent_ref(trans, root, disk_bytenr, num_bytes, parent, + root->objectid, + parent ? BTRFS_FIRST_FREE_OBJECTID : fi_key.objectid, + offset); + if (ret) { + error( + "failed to increase extent data backref[%llu %llu] root %llu", + disk_bytenr, num_bytes, root->objectid); + goto out; + } else { + printf("Add one extent data backref [%llu %llu]\n", + disk_bytenr, num_bytes); + } + + err &= ~BACKREF_MISSING; +out: + if (ret) + error("can't repair root %llu extent data item[%llu %llu]", + root->objectid, disk_bytenr, num_bytes); + return err; +} + +/* + * Check EXTENT_DATA item, mainly for its dbackref in extent tree + * + * Return >0 any error found and output error message + * Return 0 for no error found + */ +static int check_extent_data_item(struct btrfs_root *root, + struct btrfs_path *pathp, + struct node_refs *nrefs, int account_bytes) +{ + struct btrfs_file_extent_item *fi; + struct extent_buffer *eb = pathp->nodes[0]; + struct btrfs_path path; + struct btrfs_root *extent_root = root->fs_info->extent_root; + struct btrfs_key fi_key; + struct btrfs_key dbref_key; + struct extent_buffer *leaf; + struct btrfs_extent_item *ei; + struct btrfs_extent_inline_ref *iref; + struct btrfs_extent_data_ref *dref; + u64 owner; + u64 disk_bytenr; + u64 disk_num_bytes; + u64 extent_num_bytes; + u64 extent_flags; + u64 offset; + u32 item_size; + unsigned long end; + unsigned long ptr; + int type; + int found_dbackref = 0; + int slot = pathp->slots[0]; + int err = 0; + int ret; + int strict; + + btrfs_item_key_to_cpu(eb, &fi_key, slot); + fi = btrfs_item_ptr(eb, slot, struct btrfs_file_extent_item); + + /* Nothing to check for hole and inline data extents */ + if (btrfs_file_extent_type(eb, fi) == BTRFS_FILE_EXTENT_INLINE || + btrfs_file_extent_disk_bytenr(eb, fi) == 0) + return 0; + + disk_bytenr = btrfs_file_extent_disk_bytenr(eb, fi); + disk_num_bytes = btrfs_file_extent_disk_num_bytes(eb, fi); + extent_num_bytes = btrfs_file_extent_num_bytes(eb, fi); + offset = btrfs_file_extent_offset(eb, fi); + + /* Check unaligned disk_num_bytes and num_bytes */ + if (!IS_ALIGNED(disk_num_bytes, root->fs_info->sectorsize)) { + error( +"file extent [%llu, %llu] has unaligned disk num bytes: %llu, should be aligned to %u", + fi_key.objectid, fi_key.offset, disk_num_bytes, + root->fs_info->sectorsize); + err |= BYTES_UNALIGNED; + } else if (account_bytes) { + data_bytes_allocated += disk_num_bytes; + } + if (!IS_ALIGNED(extent_num_bytes, root->fs_info->sectorsize)) { + error( +"file extent [%llu, %llu] has unaligned num bytes: %llu, should be aligned to %u", + fi_key.objectid, fi_key.offset, extent_num_bytes, + root->fs_info->sectorsize); + err |= BYTES_UNALIGNED; + } else if (account_bytes) { + data_bytes_referenced += extent_num_bytes; + } + owner = btrfs_header_owner(eb); + + /* Check the extent item of the file extent in extent tree */ + btrfs_init_path(&path); + dbref_key.objectid = btrfs_file_extent_disk_bytenr(eb, fi); + dbref_key.type = BTRFS_EXTENT_ITEM_KEY; + dbref_key.offset = btrfs_file_extent_disk_num_bytes(eb, fi); + + ret = btrfs_search_slot(NULL, extent_root, &dbref_key, &path, 0, 0); + if (ret) + goto out; + + leaf = path.nodes[0]; + slot = path.slots[0]; + ei = btrfs_item_ptr(leaf, slot, struct btrfs_extent_item); + + extent_flags = btrfs_extent_flags(leaf, ei); + + if (!(extent_flags & BTRFS_EXTENT_FLAG_DATA)) { + error( + "extent[%llu %llu] backref type mismatch, wanted bit: %llx", + disk_bytenr, disk_num_bytes, + BTRFS_EXTENT_FLAG_DATA); + err |= BACKREF_MISMATCH; + } + + /* Check data backref inside that extent item */ + item_size = btrfs_item_size_nr(leaf, path.slots[0]); + iref = (struct btrfs_extent_inline_ref *)(ei + 1); + ptr = (unsigned long)iref; + end = (unsigned long)ei + item_size; + strict = should_check_extent_strictly(root, nrefs, -1); + + while (ptr < end) { + u64 ref_root; + u64 ref_objectid; + u64 ref_offset; + bool match = false; + + iref = (struct btrfs_extent_inline_ref *)ptr; + type = btrfs_extent_inline_ref_type(leaf, iref); + dref = (struct btrfs_extent_data_ref *)(&iref->offset); + + ret = check_extent_inline_ref(leaf, &dbref_key, iref); + if (ret) { + err |= ret; + break; + } + if (type == BTRFS_EXTENT_DATA_REF_KEY) { + ref_root = btrfs_extent_data_ref_root(leaf, dref); + ref_objectid = btrfs_extent_data_ref_objectid(leaf, dref); + ref_offset = btrfs_extent_data_ref_offset(leaf, dref); + + if (ref_objectid == fi_key.objectid && + ref_offset == fi_key.offset - offset) + match = true; + if (ref_root == root->objectid && match) + found_dbackref = 1; + else if (!strict && owner == ref_root && match) + found_dbackref = 1; + } else if (type == BTRFS_SHARED_DATA_REF_KEY) { + found_dbackref = !check_tree_block_ref(root, NULL, + btrfs_extent_inline_ref_offset(leaf, iref), + 0, owner, NULL); + } + + if (found_dbackref) + break; + ptr += btrfs_extent_inline_ref_size(type); + } + + if (!found_dbackref) { + btrfs_release_path(&path); + + /* Didn't find inlined data backref, try EXTENT_DATA_REF_KEY */ + dbref_key.objectid = btrfs_file_extent_disk_bytenr(eb, fi); + dbref_key.type = BTRFS_EXTENT_DATA_REF_KEY; + dbref_key.offset = hash_extent_data_ref(root->objectid, + fi_key.objectid, fi_key.offset - offset); + + ret = btrfs_search_slot(NULL, root->fs_info->extent_root, + &dbref_key, &path, 0, 0); + if (!ret) { + found_dbackref = 1; + goto out; + } + + btrfs_release_path(&path); + + /* + * Neither inlined nor EXTENT_DATA_REF found, try + * SHARED_DATA_REF as last chance. + */ + dbref_key.objectid = disk_bytenr; + dbref_key.type = BTRFS_SHARED_DATA_REF_KEY; + dbref_key.offset = eb->start; + + ret = btrfs_search_slot(NULL, root->fs_info->extent_root, + &dbref_key, &path, 0, 0); + if (!ret) { + found_dbackref = 1; + goto out; + } + } + +out: + if (!found_dbackref) + err |= BACKREF_MISSING; + btrfs_release_path(&path); + if (err & BACKREF_MISSING) { + error("data extent[%llu %llu] backref lost", + disk_bytenr, disk_num_bytes); + } + return err; +} + +/* + * Check a block group item with its referener (chunk) and its used space + * with extent/metadata item + */ +static int check_block_group_item(struct btrfs_fs_info *fs_info, + struct extent_buffer *eb, int slot) +{ + struct btrfs_root *extent_root = fs_info->extent_root; + struct btrfs_root *chunk_root = fs_info->chunk_root; + struct btrfs_block_group_item *bi; + struct btrfs_block_group_item bg_item; + struct btrfs_path path; + struct btrfs_key bg_key; + struct btrfs_key chunk_key; + struct btrfs_key extent_key; + struct btrfs_chunk *chunk; + struct extent_buffer *leaf; + struct btrfs_extent_item *ei; + u32 nodesize = btrfs_super_nodesize(fs_info->super_copy); + u64 flags; + u64 bg_flags; + u64 used; + u64 total = 0; + int ret; + int err = 0; + + btrfs_item_key_to_cpu(eb, &bg_key, slot); + bi = btrfs_item_ptr(eb, slot, struct btrfs_block_group_item); + read_extent_buffer(eb, &bg_item, (unsigned long)bi, sizeof(bg_item)); + used = btrfs_block_group_used(&bg_item); + bg_flags = btrfs_block_group_flags(&bg_item); + + chunk_key.objectid = BTRFS_FIRST_CHUNK_TREE_OBJECTID; + chunk_key.type = BTRFS_CHUNK_ITEM_KEY; + chunk_key.offset = bg_key.objectid; + + btrfs_init_path(&path); + /* Search for the referencer chunk */ + ret = btrfs_search_slot(NULL, chunk_root, &chunk_key, &path, 0, 0); + if (ret) { + error( + "block group[%llu %llu] did not find the related chunk item", + bg_key.objectid, bg_key.offset); + err |= REFERENCER_MISSING; + } else { + chunk = btrfs_item_ptr(path.nodes[0], path.slots[0], + struct btrfs_chunk); + if (btrfs_chunk_length(path.nodes[0], chunk) != + bg_key.offset) { + error( + "block group[%llu %llu] related chunk item length does not match", + bg_key.objectid, bg_key.offset); + err |= REFERENCER_MISMATCH; + } + } + btrfs_release_path(&path); + + /* Search from the block group bytenr */ + extent_key.objectid = bg_key.objectid; + extent_key.type = 0; + extent_key.offset = 0; + + btrfs_init_path(&path); + ret = btrfs_search_slot(NULL, extent_root, &extent_key, &path, 0, 0); + if (ret < 0) + goto out; + + /* Iterate extent tree to account used space */ + while (1) { + leaf = path.nodes[0]; + + /* Search slot can point to the last item beyond leaf nritems */ + if (path.slots[0] >= btrfs_header_nritems(leaf)) + goto next; + + btrfs_item_key_to_cpu(leaf, &extent_key, path.slots[0]); + if (extent_key.objectid >= bg_key.objectid + bg_key.offset) + break; + + if (extent_key.type != BTRFS_METADATA_ITEM_KEY && + extent_key.type != BTRFS_EXTENT_ITEM_KEY) + goto next; + if (extent_key.objectid < bg_key.objectid) + goto next; + + if (extent_key.type == BTRFS_METADATA_ITEM_KEY) + total += nodesize; + else + total += extent_key.offset; + + ei = btrfs_item_ptr(leaf, path.slots[0], + struct btrfs_extent_item); + flags = btrfs_extent_flags(leaf, ei); + if (flags & BTRFS_EXTENT_FLAG_DATA) { + if (!(bg_flags & BTRFS_BLOCK_GROUP_DATA)) { + error( + "bad extent[%llu, %llu) type mismatch with chunk", + extent_key.objectid, + extent_key.objectid + extent_key.offset); + err |= CHUNK_TYPE_MISMATCH; + } + } else if (flags & BTRFS_EXTENT_FLAG_TREE_BLOCK) { + if (!(bg_flags & (BTRFS_BLOCK_GROUP_SYSTEM | + BTRFS_BLOCK_GROUP_METADATA))) { + error( + "bad extent[%llu, %llu) type mismatch with chunk", + extent_key.objectid, + extent_key.objectid + nodesize); + err |= CHUNK_TYPE_MISMATCH; + } + } +next: + ret = btrfs_next_item(extent_root, &path); + if (ret) + break; + } + +out: + btrfs_release_path(&path); + + if (total != used) { + error( + "block group[%llu %llu] used %llu but extent items used %llu", + bg_key.objectid, bg_key.offset, used, total); + err |= BG_ACCOUNTING_ERROR; + } + return err; +} + +/* + * Get real tree block level for the case like shared block + * Return >= 0 as tree level + * Return <0 for error + */ +static int query_tree_block_level(struct btrfs_fs_info *fs_info, u64 bytenr) +{ + struct extent_buffer *eb; + struct btrfs_path path; + struct btrfs_key key; + struct btrfs_extent_item *ei; + u64 flags; + u64 transid; + u8 backref_level; + u8 header_level; + int ret; + + /* Search extent tree for extent generation and level */ + key.objectid = bytenr; + key.type = BTRFS_METADATA_ITEM_KEY; + key.offset = (u64)-1; + + btrfs_init_path(&path); + ret = btrfs_search_slot(NULL, fs_info->extent_root, &key, &path, 0, 0); + if (ret < 0) + goto release_out; + ret = btrfs_previous_extent_item(fs_info->extent_root, &path, bytenr); + if (ret < 0) + goto release_out; + if (ret > 0) { + ret = -ENOENT; + goto release_out; + } + + btrfs_item_key_to_cpu(path.nodes[0], &key, path.slots[0]); + ei = btrfs_item_ptr(path.nodes[0], path.slots[0], + struct btrfs_extent_item); + flags = btrfs_extent_flags(path.nodes[0], ei); + if (!(flags & BTRFS_EXTENT_FLAG_TREE_BLOCK)) { + ret = -ENOENT; + goto release_out; + } + + /* Get transid for later read_tree_block() check */ + transid = btrfs_extent_generation(path.nodes[0], ei); + + /* Get backref level as one source */ + if (key.type == BTRFS_METADATA_ITEM_KEY) { + backref_level = key.offset; + } else { + struct btrfs_tree_block_info *info; + + info = (struct btrfs_tree_block_info *)(ei + 1); + backref_level = btrfs_tree_block_level(path.nodes[0], info); + } + btrfs_release_path(&path); + + /* Get level from tree block as an alternative source */ + eb = read_tree_block(fs_info, bytenr, transid); + if (!extent_buffer_uptodate(eb)) { + free_extent_buffer(eb); + return -EIO; + } + header_level = btrfs_header_level(eb); + free_extent_buffer(eb); + + if (header_level != backref_level) + return -EIO; + return header_level; + +release_out: + btrfs_release_path(&path); + return ret; +} + +/* + * Check if a tree block backref is valid (points to a valid tree block) + * if level == -1, level will be resolved + * Return >0 for any error found and print error message + */ +static int check_tree_block_backref(struct btrfs_fs_info *fs_info, u64 root_id, + u64 bytenr, int level) +{ + struct btrfs_root *root; + struct btrfs_key key; + struct btrfs_path path; + struct extent_buffer *eb; + struct extent_buffer *node; + u32 nodesize = btrfs_super_nodesize(fs_info->super_copy); + int err = 0; + int ret; + + /* Query level for level == -1 special case */ + if (level == -1) + level = query_tree_block_level(fs_info, bytenr); + if (level < 0) { + err |= REFERENCER_MISSING; + goto out; + } + + key.objectid = root_id; + key.type = BTRFS_ROOT_ITEM_KEY; + key.offset = (u64)-1; + + root = btrfs_read_fs_root(fs_info, &key); + if (IS_ERR(root)) { + err |= REFERENCER_MISSING; + goto out; + } + + /* Read out the tree block to get item/node key */ + eb = read_tree_block(fs_info, bytenr, 0); + if (!extent_buffer_uptodate(eb)) { + err |= REFERENCER_MISSING; + free_extent_buffer(eb); + goto out; + } + + /* Empty tree, no need to check key */ + if (!btrfs_header_nritems(eb) && !level) { + free_extent_buffer(eb); + goto out; + } + + if (level) + btrfs_node_key_to_cpu(eb, &key, 0); + else + btrfs_item_key_to_cpu(eb, &key, 0); + + free_extent_buffer(eb); + + btrfs_init_path(&path); + path.lowest_level = level; + /* Search with the first key, to ensure we can reach it */ + ret = btrfs_search_slot(NULL, root, &key, &path, 0, 0); + if (ret < 0) { + err |= REFERENCER_MISSING; + goto release_out; + } + + node = path.nodes[level]; + if (btrfs_header_bytenr(node) != bytenr) { + error( + "extent [%llu %d] referencer bytenr mismatch, wanted: %llu, have: %llu", + bytenr, nodesize, bytenr, + btrfs_header_bytenr(node)); + err |= REFERENCER_MISMATCH; + } + if (btrfs_header_level(node) != level) { + error( + "extent [%llu %d] referencer level mismatch, wanted: %d, have: %d", + bytenr, nodesize, level, + btrfs_header_level(node)); + err |= REFERENCER_MISMATCH; + } + +release_out: + btrfs_release_path(&path); +out: + if (err & REFERENCER_MISSING) { + if (level < 0) + error("extent [%llu %d] lost referencer (owner: %llu)", + bytenr, nodesize, root_id); + else + error( + "extent [%llu %d] lost referencer (owner: %llu, level: %u)", + bytenr, nodesize, root_id, level); + } + + return err; +} + +/* + * Check if tree block @eb is tree reloc root. + * Return 0 if it's not or any problem happens + * Return 1 if it's a tree reloc root + */ +static int is_tree_reloc_root(struct btrfs_fs_info *fs_info, + struct extent_buffer *eb) +{ + struct btrfs_root *tree_reloc_root; + struct btrfs_key key; + u64 bytenr = btrfs_header_bytenr(eb); + u64 owner = btrfs_header_owner(eb); + int ret = 0; + + key.objectid = BTRFS_TREE_RELOC_OBJECTID; + key.offset = owner; + key.type = BTRFS_ROOT_ITEM_KEY; + + tree_reloc_root = btrfs_read_fs_root_no_cache(fs_info, &key); + if (IS_ERR(tree_reloc_root)) + return 0; + + if (bytenr == btrfs_header_bytenr(tree_reloc_root->node)) + ret = 1; + btrfs_free_fs_root(tree_reloc_root); + return ret; +} + +/* + * Check referencer for shared block backref + * If level == -1, this function will resolve the level. + */ +static int check_shared_block_backref(struct btrfs_fs_info *fs_info, + u64 parent, u64 bytenr, int level) +{ + struct extent_buffer *eb; + u32 nr; + int found_parent = 0; + int i; + + eb = read_tree_block(fs_info, parent, 0); + if (!extent_buffer_uptodate(eb)) + goto out; + + if (level == -1) + level = query_tree_block_level(fs_info, bytenr); + if (level < 0) + goto out; + + /* It's possible it's a tree reloc root */ + if (parent == bytenr) { + if (is_tree_reloc_root(fs_info, eb)) + found_parent = 1; + goto out; + } + + if (level + 1 != btrfs_header_level(eb)) + goto out; + + nr = btrfs_header_nritems(eb); + for (i = 0; i < nr; i++) { + if (bytenr == btrfs_node_blockptr(eb, i)) { + found_parent = 1; + break; + } + } +out: + free_extent_buffer(eb); + if (!found_parent) { + error( + "shared extent[%llu %u] lost its parent (parent: %llu, level: %u)", + bytenr, fs_info->nodesize, parent, level); + return REFERENCER_MISSING; + } + return 0; +} + +/* + * Check referencer for normal (inlined) data ref + * If len == 0, it will be resolved by searching in extent tree + */ +static int check_extent_data_backref(struct btrfs_fs_info *fs_info, + u64 root_id, u64 objectid, u64 offset, + u64 bytenr, u64 len, u32 count) +{ + struct btrfs_root *root; + struct btrfs_root *extent_root = fs_info->extent_root; + struct btrfs_key key; + struct btrfs_path path; + struct extent_buffer *leaf; + struct btrfs_file_extent_item *fi; + u32 found_count = 0; + int slot; + int ret = 0; + + if (!len) { + key.objectid = bytenr; + key.type = BTRFS_EXTENT_ITEM_KEY; + key.offset = (u64)-1; + + btrfs_init_path(&path); + ret = btrfs_search_slot(NULL, extent_root, &key, &path, 0, 0); + if (ret < 0) + goto out; + ret = btrfs_previous_extent_item(extent_root, &path, bytenr); + if (ret) + goto out; + btrfs_item_key_to_cpu(path.nodes[0], &key, path.slots[0]); + if (key.objectid != bytenr || + key.type != BTRFS_EXTENT_ITEM_KEY) + goto out; + len = key.offset; + btrfs_release_path(&path); + } + key.objectid = root_id; + key.type = BTRFS_ROOT_ITEM_KEY; + key.offset = (u64)-1; + btrfs_init_path(&path); + + root = btrfs_read_fs_root(fs_info, &key); + if (IS_ERR(root)) + goto out; + + key.objectid = objectid; + key.type = BTRFS_EXTENT_DATA_KEY; + /* + * It can be nasty as data backref offset is + * file offset - file extent offset, which is smaller or + * equal to original backref offset. The only special case is + * overflow. So we need to special check and do further search. + */ + key.offset = offset & (1ULL << 63) ? 0 : offset; + + ret = btrfs_search_slot(NULL, root, &key, &path, 0, 0); + if (ret < 0) + goto out; + + /* + * Search afterwards to get correct one + * NOTE: As we must do a comprehensive check on the data backref to + * make sure the dref count also matches, we must iterate all file + * extents for that inode. + */ + while (1) { + leaf = path.nodes[0]; + slot = path.slots[0]; + + if (slot >= btrfs_header_nritems(leaf) || + btrfs_header_owner(leaf) != root_id) + goto next; + btrfs_item_key_to_cpu(leaf, &key, slot); + if (key.objectid != objectid || key.type != BTRFS_EXTENT_DATA_KEY) + break; + fi = btrfs_item_ptr(leaf, slot, struct btrfs_file_extent_item); + /* + * Except normal disk bytenr and disk num bytes, we still + * need to do extra check on dbackref offset as + * dbackref offset = file_offset - file_extent_offset + * + * Also, we must check the leaf owner. + * In case of shared tree blocks (snapshots) we can inherit + * leaves from source snapshot. + * In that case, reference from source snapshot should not + * count. + */ + if (btrfs_file_extent_disk_bytenr(leaf, fi) == bytenr && + btrfs_file_extent_disk_num_bytes(leaf, fi) == len && + (u64)(key.offset - btrfs_file_extent_offset(leaf, fi)) == + offset && btrfs_header_owner(leaf) == root_id) + found_count++; + +next: + ret = btrfs_next_item(root, &path); + if (ret) + break; + } +out: + btrfs_release_path(&path); + if (found_count != count) { + error( +"extent[%llu, %llu] referencer count mismatch (root: %llu, owner: %llu, offset: %llu) wanted: %u, have: %u", + bytenr, len, root_id, objectid, offset, count, found_count); + return REFERENCER_MISSING; + } + return 0; +} + +/* + * Check if the referencer of a shared data backref exists + */ +static int check_shared_data_backref(struct btrfs_fs_info *fs_info, + u64 parent, u64 bytenr) +{ + struct extent_buffer *eb; + struct btrfs_key key; + struct btrfs_file_extent_item *fi; + u32 nr; + int found_parent = 0; + int i; + + eb = read_tree_block(fs_info, parent, 0); + if (!extent_buffer_uptodate(eb)) + goto out; + + nr = btrfs_header_nritems(eb); + for (i = 0; i < nr; i++) { + btrfs_item_key_to_cpu(eb, &key, i); + if (key.type != BTRFS_EXTENT_DATA_KEY) + continue; + + fi = btrfs_item_ptr(eb, i, struct btrfs_file_extent_item); + if (btrfs_file_extent_type(eb, fi) == BTRFS_FILE_EXTENT_INLINE) + continue; + + if (btrfs_file_extent_disk_bytenr(eb, fi) == bytenr) { + found_parent = 1; + break; + } + } + +out: + free_extent_buffer(eb); + if (!found_parent) { + error("shared extent %llu referencer lost (parent: %llu)", + bytenr, parent); + return REFERENCER_MISSING; + } + return 0; +} + +/* + * Only delete backref if REFERENCER_MISSING now + * + * Returns <0 the extent was deleted + * Returns >0 the backref was deleted but extent still exists, returned value + * means error after repair + * Returns 0 nothing happened + */ +static int repair_extent_item(struct btrfs_trans_handle *trans, + struct btrfs_root *root, struct btrfs_path *path, + u64 bytenr, u64 num_bytes, u64 parent, u64 root_objectid, + u64 owner, u64 offset, int err) +{ + struct btrfs_key old_key; + int freed = 0; + int ret; + + btrfs_item_key_to_cpu(path->nodes[0], &old_key, path->slots[0]); + + if (err & (REFERENCER_MISSING | REFERENCER_MISMATCH)) { + /* delete the backref */ + ret = btrfs_free_extent(trans, root->fs_info->fs_root, bytenr, + num_bytes, parent, root_objectid, owner, offset); + if (!ret) { + freed = 1; + err &= ~REFERENCER_MISSING; + printf("Delete backref in extent [%llu %llu]\n", + bytenr, num_bytes); + } else { + error("fail to delete backref in extent [%llu %llu]", + bytenr, num_bytes); + } + } + + /* btrfs_free_extent may delete the extent */ + btrfs_release_path(path); + ret = btrfs_search_slot(NULL, root, &old_key, path, 0, 0); + + if (ret) + ret = -ENOENT; + else if (freed) + ret = err; + return ret; +} + +/* + * This function will check a given extent item, including its backref and + * itself (like crossing stripe boundary and type) + * + * Since we don't use extent_record anymore, introduce new error bit + */ +static int check_extent_item(struct btrfs_trans_handle *trans, + struct btrfs_fs_info *fs_info, + struct btrfs_path *path) +{ + struct btrfs_extent_item *ei; + struct btrfs_extent_inline_ref *iref; + struct btrfs_extent_data_ref *dref; + struct extent_buffer *eb = path->nodes[0]; + unsigned long end; + unsigned long ptr; + int slot = path->slots[0]; + int type; + u32 nodesize = btrfs_super_nodesize(fs_info->super_copy); + u32 item_size = btrfs_item_size_nr(eb, slot); + u64 flags; + u64 offset; + u64 parent; + u64 num_bytes; + u64 root_objectid; + u64 owner; + u64 owner_offset; + int metadata = 0; + int level; + struct btrfs_key key; + int ret; + int err = 0; + + btrfs_item_key_to_cpu(eb, &key, slot); + if (key.type == BTRFS_EXTENT_ITEM_KEY) { + bytes_used += key.offset; + num_bytes = key.offset; + } else { + bytes_used += nodesize; + num_bytes = nodesize; + } + + if (item_size < sizeof(*ei)) { + /* + * COMPAT_EXTENT_TREE_V0 case, but it's already a super + * old thing when on disk format is still un-determined. + * No need to care about it anymore + */ + error("unsupported COMPAT_EXTENT_TREE_V0 detected"); + return -ENOTTY; + } + + ei = btrfs_item_ptr(eb, slot, struct btrfs_extent_item); + flags = btrfs_extent_flags(eb, ei); + + if (flags & BTRFS_EXTENT_FLAG_TREE_BLOCK) + metadata = 1; + if (metadata && check_crossing_stripes(global_info, key.objectid, + eb->len)) { + error("bad metadata [%llu, %llu) crossing stripe boundary", + key.objectid, key.objectid + nodesize); + err |= CROSSING_STRIPE_BOUNDARY; + } + + ptr = (unsigned long)(ei + 1); + + if (metadata && key.type == BTRFS_EXTENT_ITEM_KEY) { + /* Old EXTENT_ITEM metadata */ + struct btrfs_tree_block_info *info; + + info = (struct btrfs_tree_block_info *)ptr; + level = btrfs_tree_block_level(eb, info); + ptr += sizeof(struct btrfs_tree_block_info); + } else { + /* New METADATA_ITEM */ + level = key.offset; + } + end = (unsigned long)ei + item_size; + +next: + /* Reached extent item end normally */ + if (ptr == end) + goto out; + + /* Beyond extent item end, wrong item size */ + if (ptr > end) { + err |= ITEM_SIZE_MISMATCH; + error("extent item at bytenr %llu slot %d has wrong size", + eb->start, slot); + goto out; + } + + parent = 0; + root_objectid = 0; + owner = 0; + owner_offset = 0; + /* Now check every backref in this extent item */ + iref = (struct btrfs_extent_inline_ref *)ptr; + type = btrfs_extent_inline_ref_type(eb, iref); + offset = btrfs_extent_inline_ref_offset(eb, iref); + switch (type) { + case BTRFS_TREE_BLOCK_REF_KEY: + root_objectid = offset; + owner = level; + ret = check_tree_block_backref(fs_info, offset, key.objectid, + level); + err |= ret; + break; + case BTRFS_SHARED_BLOCK_REF_KEY: + parent = offset; + ret = check_shared_block_backref(fs_info, offset, key.objectid, + level); + err |= ret; + break; + case BTRFS_EXTENT_DATA_REF_KEY: + dref = (struct btrfs_extent_data_ref *)(&iref->offset); + root_objectid = btrfs_extent_data_ref_root(eb, dref); + owner = btrfs_extent_data_ref_objectid(eb, dref); + owner_offset = btrfs_extent_data_ref_offset(eb, dref); + ret = check_extent_data_backref(fs_info, root_objectid, owner, + owner_offset, key.objectid, key.offset, + btrfs_extent_data_ref_count(eb, dref)); + err |= ret; + break; + case BTRFS_SHARED_DATA_REF_KEY: + parent = offset; + ret = check_shared_data_backref(fs_info, offset, key.objectid); + err |= ret; + break; + default: + error("extent[%llu %d %llu] has unknown ref type: %d", + key.objectid, key.type, key.offset, type); + ret = UNKNOWN_TYPE; + err |= ret; + goto out; + } + + if (err && repair) { + ret = repair_extent_item(trans, fs_info->extent_root, path, + key.objectid, num_bytes, parent, root_objectid, + owner, owner_offset, ret); + if (ret < 0) + goto out; + if (ret) { + goto next; + err = ret; + } + } + + ptr += btrfs_extent_inline_ref_size(type); + goto next; + +out: + return err; +} + +/* + * Check if a dev extent item is referred correctly by its chunk + */ +static int check_dev_extent_item(struct btrfs_fs_info *fs_info, + struct extent_buffer *eb, int slot) +{ + struct btrfs_root *chunk_root = fs_info->chunk_root; + struct btrfs_dev_extent *ptr; + struct btrfs_path path; + struct btrfs_key chunk_key; + struct btrfs_key devext_key; + struct btrfs_chunk *chunk; + struct extent_buffer *l; + int num_stripes; + u64 length; + int i; + int found_chunk = 0; + int ret; + + btrfs_item_key_to_cpu(eb, &devext_key, slot); + ptr = btrfs_item_ptr(eb, slot, struct btrfs_dev_extent); + length = btrfs_dev_extent_length(eb, ptr); + + chunk_key.objectid = btrfs_dev_extent_chunk_objectid(eb, ptr); + chunk_key.type = BTRFS_CHUNK_ITEM_KEY; + chunk_key.offset = btrfs_dev_extent_chunk_offset(eb, ptr); + + btrfs_init_path(&path); + ret = btrfs_search_slot(NULL, chunk_root, &chunk_key, &path, 0, 0); + if (ret) + goto out; + + l = path.nodes[0]; + chunk = btrfs_item_ptr(l, path.slots[0], struct btrfs_chunk); + ret = btrfs_check_chunk_valid(fs_info, l, chunk, path.slots[0], + chunk_key.offset); + if (ret < 0) + goto out; + + if (btrfs_stripe_length(fs_info, l, chunk) != length) + goto out; + + num_stripes = btrfs_chunk_num_stripes(l, chunk); + for (i = 0; i < num_stripes; i++) { + u64 devid = btrfs_stripe_devid_nr(l, chunk, i); + u64 offset = btrfs_stripe_offset_nr(l, chunk, i); + + if (devid == devext_key.objectid && + offset == devext_key.offset) { + found_chunk = 1; + break; + } + } +out: + btrfs_release_path(&path); + if (!found_chunk) { + error( + "device extent[%llu, %llu, %llu] did not find the related chunk", + devext_key.objectid, devext_key.offset, length); + return REFERENCER_MISSING; + } + return 0; +} + +/* + * Check if the used space is correct with the dev item + */ +static int check_dev_item(struct btrfs_fs_info *fs_info, + struct extent_buffer *eb, int slot) +{ + struct btrfs_root *dev_root = fs_info->dev_root; + struct btrfs_dev_item *dev_item; + struct btrfs_path path; + struct btrfs_key key; + struct btrfs_dev_extent *ptr; + u64 total_bytes; + u64 dev_id; + u64 used; + u64 total = 0; + int ret; + + dev_item = btrfs_item_ptr(eb, slot, struct btrfs_dev_item); + dev_id = btrfs_device_id(eb, dev_item); + used = btrfs_device_bytes_used(eb, dev_item); + total_bytes = btrfs_device_total_bytes(eb, dev_item); + + key.objectid = dev_id; + key.type = BTRFS_DEV_EXTENT_KEY; + key.offset = 0; + + btrfs_init_path(&path); + ret = btrfs_search_slot(NULL, dev_root, &key, &path, 0, 0); + if (ret < 0) { + btrfs_item_key_to_cpu(eb, &key, slot); + error("cannot find any related dev extent for dev[%llu, %u, %llu]", + key.objectid, key.type, key.offset); + btrfs_release_path(&path); + return REFERENCER_MISSING; + } + + /* Iterate dev_extents to calculate the used space of a device */ + while (1) { + if (path.slots[0] >= btrfs_header_nritems(path.nodes[0])) + goto next; + + btrfs_item_key_to_cpu(path.nodes[0], &key, path.slots[0]); + if (key.objectid > dev_id) + break; + if (key.type != BTRFS_DEV_EXTENT_KEY || key.objectid != dev_id) + goto next; + + ptr = btrfs_item_ptr(path.nodes[0], path.slots[0], + struct btrfs_dev_extent); + total += btrfs_dev_extent_length(path.nodes[0], ptr); +next: + ret = btrfs_next_item(dev_root, &path); + if (ret) + break; + } + btrfs_release_path(&path); + + if (used != total) { + btrfs_item_key_to_cpu(eb, &key, slot); + error( +"Dev extent's total-byte %llu is not equal to bytes-used %llu in dev[%llu, %u, %llu]", + total, used, BTRFS_ROOT_TREE_OBJECTID, + BTRFS_DEV_EXTENT_KEY, dev_id); + return ACCOUNTING_MISMATCH; + } + check_dev_size_alignment(dev_id, total_bytes, fs_info->sectorsize); + + return 0; +} + +/* + * Check a chunk item. + * Including checking all referred dev_extents and block group + */ +static int check_chunk_item(struct btrfs_fs_info *fs_info, + struct extent_buffer *eb, int slot) +{ + struct btrfs_root *extent_root = fs_info->extent_root; + struct btrfs_root *dev_root = fs_info->dev_root; + struct btrfs_path path; + struct btrfs_key chunk_key; + struct btrfs_key bg_key; + struct btrfs_key devext_key; + struct btrfs_chunk *chunk; + struct extent_buffer *leaf; + struct btrfs_block_group_item *bi; + struct btrfs_block_group_item bg_item; + struct btrfs_dev_extent *ptr; + u64 length; + u64 chunk_end; + u64 stripe_len; + u64 type; + int num_stripes; + u64 offset; + u64 objectid; + int i; + int ret; + int err = 0; + + btrfs_item_key_to_cpu(eb, &chunk_key, slot); + chunk = btrfs_item_ptr(eb, slot, struct btrfs_chunk); + length = btrfs_chunk_length(eb, chunk); + chunk_end = chunk_key.offset + length; + ret = btrfs_check_chunk_valid(fs_info, eb, chunk, slot, + chunk_key.offset); + if (ret < 0) { + error("chunk[%llu %llu) is invalid", chunk_key.offset, + chunk_end); + err |= BYTES_UNALIGNED | UNKNOWN_TYPE; + goto out; + } + type = btrfs_chunk_type(eb, chunk); + + bg_key.objectid = chunk_key.offset; + bg_key.type = BTRFS_BLOCK_GROUP_ITEM_KEY; + bg_key.offset = length; + + btrfs_init_path(&path); + ret = btrfs_search_slot(NULL, extent_root, &bg_key, &path, 0, 0); + if (ret) { + error( + "chunk[%llu %llu) did not find the related block group item", + chunk_key.offset, chunk_end); + err |= REFERENCER_MISSING; + } else{ + leaf = path.nodes[0]; + bi = btrfs_item_ptr(leaf, path.slots[0], + struct btrfs_block_group_item); + read_extent_buffer(leaf, &bg_item, (unsigned long)bi, + sizeof(bg_item)); + if (btrfs_block_group_flags(&bg_item) != type) { + error( +"chunk[%llu %llu) related block group item flags mismatch, wanted: %llu, have: %llu", + chunk_key.offset, chunk_end, type, + btrfs_block_group_flags(&bg_item)); + err |= REFERENCER_MISSING; + } + } + + num_stripes = btrfs_chunk_num_stripes(eb, chunk); + stripe_len = btrfs_stripe_length(fs_info, eb, chunk); + for (i = 0; i < num_stripes; i++) { + btrfs_release_path(&path); + btrfs_init_path(&path); + devext_key.objectid = btrfs_stripe_devid_nr(eb, chunk, i); + devext_key.type = BTRFS_DEV_EXTENT_KEY; + devext_key.offset = btrfs_stripe_offset_nr(eb, chunk, i); + + ret = btrfs_search_slot(NULL, dev_root, &devext_key, &path, + 0, 0); + if (ret) + goto not_match_dev; + + leaf = path.nodes[0]; + ptr = btrfs_item_ptr(leaf, path.slots[0], + struct btrfs_dev_extent); + objectid = btrfs_dev_extent_chunk_objectid(leaf, ptr); + offset = btrfs_dev_extent_chunk_offset(leaf, ptr); + if (objectid != chunk_key.objectid || + offset != chunk_key.offset || + btrfs_dev_extent_length(leaf, ptr) != stripe_len) + goto not_match_dev; + continue; +not_match_dev: + err |= BACKREF_MISSING; + error( + "chunk[%llu %llu) stripe %d did not find the related dev extent", + chunk_key.objectid, chunk_end, i); + continue; + } + btrfs_release_path(&path); +out: + return err; +} + +/* + * Add block group item to the extent tree if @err contains REFERENCER_MISSING. + * FIXME: We still need to repair error of dev_item. + * + * Returns error after repair. + */ +static int repair_chunk_item(struct btrfs_trans_handle *trans, + struct btrfs_root *chunk_root, + struct btrfs_path *path, int err) +{ + struct btrfs_chunk *chunk; + struct btrfs_key chunk_key; + struct extent_buffer *eb = path->nodes[0]; + u64 length; + int slot = path->slots[0]; + u64 type; + int ret = 0; + + btrfs_item_key_to_cpu(eb, &chunk_key, slot); + if (chunk_key.type != BTRFS_CHUNK_ITEM_KEY) + return err; + chunk = btrfs_item_ptr(eb, slot, struct btrfs_chunk); + type = btrfs_chunk_type(path->nodes[0], chunk); + length = btrfs_chunk_length(eb, chunk); + + if (err & REFERENCER_MISSING) { + ret = btrfs_make_block_group(trans, chunk_root->fs_info, 0, + type, chunk_key.offset, length); + if (ret) { + error("fail to add block group item[%llu %llu]", + chunk_key.offset, length); + goto out; + } else { + err &= ~REFERENCER_MISSING; + printf("Added block group item[%llu %llu]\n", + chunk_key.offset, length); + } + } + +out: + return err; +} + +static int delete_extent_tree_item(struct btrfs_trans_handle *trans, + struct btrfs_root *root, + struct btrfs_path *path) +{ + struct btrfs_key key; + int ret = 0; + + btrfs_item_key_to_cpu(path->nodes[0], &key, path->slots[0]); + btrfs_release_path(path); + ret = btrfs_search_slot(trans, root, &key, path, -1, 1); + if (ret) { + ret = -ENOENT; + goto out; + } + + ret = btrfs_del_item(trans, root, path); + if (ret) + goto out; + + if (path->slots[0] == 0) + btrfs_prev_leaf(root, path); + else + path->slots[0]--; +out: + if (ret) + error("failed to delete root %llu item[%llu, %u, %llu]", + root->objectid, key.objectid, key.type, key.offset); + else + printf("Deleted root %llu item[%llu, %u, %llu]\n", + root->objectid, key.objectid, key.type, key.offset); + return ret; +} + +/* + * Main entry function to check known items and update related accounting info + */ +static int check_leaf_items(struct btrfs_trans_handle *trans, + struct btrfs_root *root, struct btrfs_path *path, + struct node_refs *nrefs, int account_bytes) +{ + struct btrfs_fs_info *fs_info = root->fs_info; + struct btrfs_key key; + struct extent_buffer *eb; + int slot; + int type; + struct btrfs_extent_data_ref *dref; + int ret = 0; + int err = 0; + +again: + eb = path->nodes[0]; + slot = path->slots[0]; + if (slot >= btrfs_header_nritems(eb)) { + if (slot == 0) { + error("empty leaf [%llu %u] root %llu", eb->start, + root->fs_info->nodesize, root->objectid); + err |= EIO; + } + goto out; + } + + btrfs_item_key_to_cpu(eb, &key, slot); + type = key.type; + + switch (type) { + case BTRFS_EXTENT_DATA_KEY: + ret = check_extent_data_item(root, path, nrefs, account_bytes); + if (repair && ret) + ret = repair_extent_data_item(trans, root, path, nrefs, + ret); + err |= ret; + break; + case BTRFS_BLOCK_GROUP_ITEM_KEY: + ret = check_block_group_item(fs_info, eb, slot); + if (repair && + ret & REFERENCER_MISSING) + ret = delete_extent_tree_item(trans, root, path); + err |= ret; + break; + case BTRFS_DEV_ITEM_KEY: + ret = check_dev_item(fs_info, eb, slot); + err |= ret; + break; + case BTRFS_CHUNK_ITEM_KEY: + ret = check_chunk_item(fs_info, eb, slot); + if (repair && ret) + ret = repair_chunk_item(trans, root, path, ret); + err |= ret; + break; + case BTRFS_DEV_EXTENT_KEY: + ret = check_dev_extent_item(fs_info, eb, slot); + err |= ret; + break; + case BTRFS_EXTENT_ITEM_KEY: + case BTRFS_METADATA_ITEM_KEY: + ret = check_extent_item(trans, fs_info, path); + err |= ret; + break; + case BTRFS_EXTENT_CSUM_KEY: + total_csum_bytes += btrfs_item_size_nr(eb, slot); + err |= ret; + break; + case BTRFS_TREE_BLOCK_REF_KEY: + ret = check_tree_block_backref(fs_info, key.offset, + key.objectid, -1); + if (repair && + ret & (REFERENCER_MISMATCH | REFERENCER_MISSING)) + ret = delete_extent_tree_item(trans, root, path); + err |= ret; + break; + case BTRFS_EXTENT_DATA_REF_KEY: + dref = btrfs_item_ptr(eb, slot, struct btrfs_extent_data_ref); + ret = check_extent_data_backref(fs_info, + btrfs_extent_data_ref_root(eb, dref), + btrfs_extent_data_ref_objectid(eb, dref), + btrfs_extent_data_ref_offset(eb, dref), + key.objectid, 0, + btrfs_extent_data_ref_count(eb, dref)); + if (repair && + ret & (REFERENCER_MISMATCH | REFERENCER_MISSING)) + ret = delete_extent_tree_item(trans, root, path); + err |= ret; + break; + case BTRFS_SHARED_BLOCK_REF_KEY: + ret = check_shared_block_backref(fs_info, key.offset, + key.objectid, -1); + if (repair && + ret & (REFERENCER_MISMATCH | REFERENCER_MISSING)) + ret = delete_extent_tree_item(trans, root, path); + err |= ret; + break; + case BTRFS_SHARED_DATA_REF_KEY: + ret = check_shared_data_backref(fs_info, key.offset, + key.objectid); + if (repair && + ret & (REFERENCER_MISMATCH | REFERENCER_MISSING)) + ret = delete_extent_tree_item(trans, root, path); + err |= ret; + break; + default: + break; + } + + ++path->slots[0]; + goto again; +out: + return err; +} + +/* + * @trans just for lowmem repair mode + * @check all if not 0 then check all tree block backrefs and items + * 0 then just check relationship of items in fs tree(s) + * + * Returns >0 Found error, should continue + * Returns <0 Fatal error, must exit the whole check + * Returns 0 No errors found + */ +static int walk_down_tree_v2(struct btrfs_trans_handle *trans, + struct btrfs_root *root, struct btrfs_path *path, + int *level, struct node_refs *nrefs, int ext_ref, + int check_all) +{ + enum btrfs_tree_block_status status; + u64 bytenr; + u64 ptr_gen; + struct btrfs_fs_info *fs_info = root->fs_info; + struct extent_buffer *next; + struct extent_buffer *cur; + int ret; + int err = 0; + int check; + int account_file_data = 0; + + WARN_ON(*level < 0); + WARN_ON(*level >= BTRFS_MAX_LEVEL); + + ret = update_nodes_refs(root, btrfs_header_bytenr(path->nodes[*level]), + path->nodes[*level], nrefs, *level, check_all); + if (ret < 0) + return ret; + + while (*level >= 0) { + WARN_ON(*level < 0); + WARN_ON(*level >= BTRFS_MAX_LEVEL); + cur = path->nodes[*level]; + bytenr = btrfs_header_bytenr(cur); + check = nrefs->need_check[*level]; + + if (btrfs_header_level(cur) != *level) + WARN_ON(1); + /* + * Update bytes accounting and check tree block ref + * NOTE: Doing accounting and check before checking nritems + * is necessary because of empty node/leaf. + */ + if ((check_all && !nrefs->checked[*level]) || + (!check_all && nrefs->need_check[*level])) { + ret = check_tree_block_ref(root, cur, + btrfs_header_bytenr(cur), btrfs_header_level(cur), + btrfs_header_owner(cur), nrefs); + + if (repair && ret) + ret = repair_tree_block_ref(trans, root, + path->nodes[*level], nrefs, *level, ret); + err |= ret; + + if (check_all && nrefs->need_check[*level] && + nrefs->refs[*level]) { + account_bytes(root, path, *level); + account_file_data = 1; + } + nrefs->checked[*level] = 1; + } + + if (path->slots[*level] >= btrfs_header_nritems(cur)) + break; + + /* Don't forgot to check leaf/node validation */ + if (*level == 0) { + /* skip duplicate check */ + if (check || !check_all) { + ret = btrfs_check_leaf(root, NULL, cur); + if (ret != BTRFS_TREE_BLOCK_CLEAN) { + err |= -EIO; + break; + } + } + + ret = 0; + if (!check_all) + ret = process_one_leaf_v2(root, path, nrefs, + level, ext_ref); + else + ret = check_leaf_items(trans, root, path, + nrefs, account_file_data); + err |= ret; + break; + } else { + if (check || !check_all) { + ret = btrfs_check_node(root, NULL, cur); + if (ret != BTRFS_TREE_BLOCK_CLEAN) { + err |= -EIO; + break; + } + } + } + + bytenr = btrfs_node_blockptr(cur, path->slots[*level]); + ptr_gen = btrfs_node_ptr_generation(cur, path->slots[*level]); + + ret = update_nodes_refs(root, bytenr, NULL, nrefs, *level - 1, + check_all); + if (ret < 0) + break; + /* + * check all trees in check_chunks_and_extent_v2 + * check shared node once in check_fs_roots + */ + if (!check_all && !nrefs->need_check[*level - 1]) { + path->slots[*level]++; + continue; + } + + next = btrfs_find_tree_block(fs_info, bytenr, fs_info->nodesize); + if (!next || !btrfs_buffer_uptodate(next, ptr_gen)) { + free_extent_buffer(next); + reada_walk_down(root, cur, path->slots[*level]); + next = read_tree_block(fs_info, bytenr, ptr_gen); + if (!extent_buffer_uptodate(next)) { + struct btrfs_key node_key; + + btrfs_node_key_to_cpu(path->nodes[*level], + &node_key, + path->slots[*level]); + btrfs_add_corrupt_extent_record(fs_info, + &node_key, path->nodes[*level]->start, + fs_info->nodesize, *level); + err |= -EIO; + break; + } + } + + ret = check_child_node(cur, path->slots[*level], next); + err |= ret; + if (ret < 0) + break; + + 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; + break; + } + + *level = *level - 1; + free_extent_buffer(path->nodes[*level]); + path->nodes[*level] = next; + path->slots[*level] = 0; + account_file_data = 0; + + update_nodes_refs(root, (u64)-1, next, nrefs, *level, check_all); + } + return err; +} + +static int walk_up_tree_v2(struct btrfs_root *root, struct btrfs_path *path, + int *level) +{ + int i; + struct extent_buffer *leaf; + + for (i = *level; i < BTRFS_MAX_LEVEL - 1 && path->nodes[i]; i++) { + leaf = path->nodes[i]; + if (path->slots[i] + 1 < btrfs_header_nritems(leaf)) { + path->slots[i]++; + *level = i; + return 0; + } else { + free_extent_buffer(path->nodes[*level]); + path->nodes[*level] = NULL; + *level = i + 1; + } + } + return 1; +} + +/* + * Insert the missing inode item and inode ref. + * + * Normal INODE_ITEM_MISSING and INODE_REF_MISSING are handled in backref * dir. + * Root dir should be handled specially because root dir is the root of fs. + * + * returns err (>0 or 0) after repair + */ +static int repair_fs_first_inode(struct btrfs_root *root, int err) +{ + struct btrfs_trans_handle *trans; + struct btrfs_key key; + struct btrfs_path path; + int filetype = BTRFS_FT_DIR; + int ret = 0; + + btrfs_init_path(&path); + + if (err & INODE_REF_MISSING) { + key.objectid = BTRFS_FIRST_FREE_OBJECTID; + key.type = BTRFS_INODE_REF_KEY; + key.offset = BTRFS_FIRST_FREE_OBJECTID; + + trans = btrfs_start_transaction(root, 1); + if (IS_ERR(trans)) { + ret = PTR_ERR(trans); + goto out; + } + + btrfs_release_path(&path); + ret = btrfs_search_slot(trans, root, &key, &path, 1, 1); + if (ret) + goto trans_fail; + + ret = btrfs_insert_inode_ref(trans, root, "..", 2, + BTRFS_FIRST_FREE_OBJECTID, + BTRFS_FIRST_FREE_OBJECTID, 0); + if (ret) + goto trans_fail; + + printf("Add INODE_REF[%llu %llu] name %s\n", + BTRFS_FIRST_FREE_OBJECTID, BTRFS_FIRST_FREE_OBJECTID, + ".."); + err &= ~INODE_REF_MISSING; +trans_fail: + if (ret) + error("fail to insert first inode's ref"); + btrfs_commit_transaction(trans, root); + } + + if (err & INODE_ITEM_MISSING) { + ret = repair_inode_item_missing(root, + BTRFS_FIRST_FREE_OBJECTID, filetype); + if (ret) + goto out; + err &= ~INODE_ITEM_MISSING; + } +out: + if (ret) + error("fail to repair first inode"); + btrfs_release_path(&path); + return err; +} + +/* + * check first root dir's inode_item and inode_ref + * + * returns 0 means no error + * returns >0 means error + * returns <0 means fatal error + */ +static int check_fs_first_inode(struct btrfs_root *root, unsigned int ext_ref) +{ + struct btrfs_path path; + struct btrfs_key key; + struct btrfs_inode_item *ii; + u64 index; + u32 mode; + int err = 0; + int ret; + + key.objectid = BTRFS_FIRST_FREE_OBJECTID; + key.type = BTRFS_INODE_ITEM_KEY; + key.offset = 0; + + /* For root being dropped, we don't need to check first inode */ + if (btrfs_root_refs(&root->root_item) == 0 && + btrfs_disk_key_objectid(&root->root_item.drop_progress) >= + BTRFS_FIRST_FREE_OBJECTID) + return 0; + + btrfs_init_path(&path); + ret = btrfs_search_slot(NULL, root, &key, &path, 0, 0); + if (ret < 0) + goto out; + if (ret > 0) { + ret = 0; + err |= INODE_ITEM_MISSING; + } else { + ii = btrfs_item_ptr(path.nodes[0], path.slots[0], + struct btrfs_inode_item); + mode = btrfs_inode_mode(path.nodes[0], ii); + if (imode_to_type(mode) != BTRFS_FT_DIR) + err |= INODE_ITEM_MISMATCH; + } + + /* lookup first inode ref */ + key.offset = BTRFS_FIRST_FREE_OBJECTID; + key.type = BTRFS_INODE_REF_KEY; + /* special index value */ + index = 0; + + ret = find_inode_ref(root, &key, "..", strlen(".."), &index, ext_ref); + if (ret < 0) + goto out; + err |= ret; + +out: + btrfs_release_path(&path); + + if (err && repair) + err = repair_fs_first_inode(root, err); + + if (err & (INODE_ITEM_MISSING | INODE_ITEM_MISMATCH)) + error("root dir INODE_ITEM is %s", + err & INODE_ITEM_MISMATCH ? "mismatch" : "missing"); + if (err & INODE_REF_MISSING) + error("root dir INODE_REF is missing"); + + return ret < 0 ? ret : err; +} + +/* + * This function calls walk_down_tree_v2 and walk_up_tree_v2 to check tree + * blocks and integrity of fs tree items. + * + * @root: the root of the tree to be checked. + * @ext_ref feature EXTENDED_IREF is enable or not. + * @account if NOT 0 means check the tree (including tree)'s treeblocks. + * otherwise means check fs tree(s) items relationship and + * @root MUST be a fs tree root. + * Returns 0 represents OK. + * Returns not 0 represents error. + */ +static int check_btrfs_root(struct btrfs_trans_handle *trans, + struct btrfs_root *root, unsigned int ext_ref, + int check_all) +{ + struct btrfs_path path; + struct node_refs nrefs; + struct btrfs_root_item *root_item = &root->root_item; + int ret; + int level; + int err = 0; + + memset(&nrefs, 0, sizeof(nrefs)); + if (!check_all) { + /* + * We need to manually check the first inode item (256) + * As the following traversal function will only start from + * the first inode item in the leaf, if inode item (256) is + * missing we will skip it forever. + */ + ret = check_fs_first_inode(root, ext_ref); + if (ret < 0) + return ret; + } + + + level = btrfs_header_level(root->node); + btrfs_init_path(&path); + + if (btrfs_root_refs(root_item) > 0 || + btrfs_disk_key_objectid(&root_item->drop_progress) == 0) { + path.nodes[level] = root->node; + path.slots[level] = 0; + extent_buffer_get(root->node); + } else { + struct btrfs_key key; + + btrfs_disk_key_to_cpu(&key, &root_item->drop_progress); + level = root_item->drop_level; + path.lowest_level = level; + ret = btrfs_search_slot(NULL, root, &key, &path, 0, 0); + if (ret < 0) + goto out; + ret = 0; + } + + while (1) { + ret = walk_down_tree_v2(trans, root, &path, &level, &nrefs, + ext_ref, check_all); + + err |= !!ret; + + /* if ret is negative, walk shall stop */ + if (ret < 0) { + ret = err; + break; + } + + ret = walk_up_tree_v2(root, &path, &level); + if (ret != 0) { + /* Normal exit, reset ret to err */ + ret = err; + break; + } + } + +out: + btrfs_release_path(&path); + return ret; +} + +/* + * Iterate all items in the tree and call check_inode_item() to check. + * + * @root: the root of the tree to be checked. + * @ext_ref: the EXTENDED_IREF feature + * + * Return 0 if no error found. + * Return <0 for error. + */ +static int check_fs_root_v2(struct btrfs_root *root, unsigned int ext_ref) +{ + reset_cached_block_groups(root->fs_info); + return check_btrfs_root(NULL, root, ext_ref, 0); +} + +/* + * Find the relative ref for root_ref and root_backref. + * + * @root: the root of the root tree. + * @ref_key: the key of the root ref. + * + * Return 0 if no error occurred. + */ +static int check_root_ref(struct btrfs_root *root, struct btrfs_key *ref_key, + struct extent_buffer *node, int slot) +{ + struct btrfs_path path; + struct btrfs_key key; + struct btrfs_root_ref *ref; + struct btrfs_root_ref *backref; + char ref_name[BTRFS_NAME_LEN] = {0}; + char backref_name[BTRFS_NAME_LEN] = {0}; + u64 ref_dirid; + u64 ref_seq; + u32 ref_namelen; + u64 backref_dirid; + u64 backref_seq; + u32 backref_namelen; + u32 len; + int ret; + int err = 0; + + ref = btrfs_item_ptr(node, slot, struct btrfs_root_ref); + ref_dirid = btrfs_root_ref_dirid(node, ref); + ref_seq = btrfs_root_ref_sequence(node, ref); + ref_namelen = btrfs_root_ref_name_len(node, ref); + + if (ref_namelen <= BTRFS_NAME_LEN) { + len = ref_namelen; + } else { + len = BTRFS_NAME_LEN; + warning("%s[%llu %llu] ref_name too long", + ref_key->type == BTRFS_ROOT_REF_KEY ? + "ROOT_REF" : "ROOT_BACKREF", ref_key->objectid, + ref_key->offset); + } + read_extent_buffer(node, ref_name, (unsigned long)(ref + 1), len); + + /* Find relative root_ref */ + key.objectid = ref_key->offset; + key.type = BTRFS_ROOT_BACKREF_KEY + BTRFS_ROOT_REF_KEY - ref_key->type; + key.offset = ref_key->objectid; + + btrfs_init_path(&path); + ret = btrfs_search_slot(NULL, root, &key, &path, 0, 0); + if (ret) { + err |= ROOT_REF_MISSING; + error("%s[%llu %llu] couldn't find relative ref", + ref_key->type == BTRFS_ROOT_REF_KEY ? + "ROOT_REF" : "ROOT_BACKREF", + ref_key->objectid, ref_key->offset); + goto out; + } + + backref = btrfs_item_ptr(path.nodes[0], path.slots[0], + struct btrfs_root_ref); + backref_dirid = btrfs_root_ref_dirid(path.nodes[0], backref); + backref_seq = btrfs_root_ref_sequence(path.nodes[0], backref); + backref_namelen = btrfs_root_ref_name_len(path.nodes[0], backref); + + if (backref_namelen <= BTRFS_NAME_LEN) { + len = backref_namelen; + } else { + len = BTRFS_NAME_LEN; + warning("%s[%llu %llu] ref_name too long", + key.type == BTRFS_ROOT_REF_KEY ? + "ROOT_REF" : "ROOT_BACKREF", + key.objectid, key.offset); + } + read_extent_buffer(path.nodes[0], backref_name, + (unsigned long)(backref + 1), len); + + if (ref_dirid != backref_dirid || ref_seq != backref_seq || + ref_namelen != backref_namelen || + strncmp(ref_name, backref_name, len)) { + err |= ROOT_REF_MISMATCH; + error("%s[%llu %llu] mismatch relative ref", + ref_key->type == BTRFS_ROOT_REF_KEY ? + "ROOT_REF" : "ROOT_BACKREF", + ref_key->objectid, ref_key->offset); + } +out: + btrfs_release_path(&path); + return err; +} + +/* + * Check all fs/file tree in low_memory mode. + * + * 1. for fs tree root item, call check_fs_root_v2() + * 2. for fs tree root ref/backref, call check_root_ref() + * + * Return 0 if no error occurred. + */ +int check_fs_roots_v2(struct btrfs_fs_info *fs_info) +{ + struct btrfs_root *tree_root = fs_info->tree_root; + struct btrfs_root *cur_root = NULL; + struct btrfs_path path; + struct btrfs_key key; + struct extent_buffer *node; + unsigned int ext_ref; + int slot; + int ret; + int err = 0; + + ext_ref = btrfs_fs_incompat(fs_info, EXTENDED_IREF); + + btrfs_init_path(&path); + key.objectid = BTRFS_FS_TREE_OBJECTID; + key.offset = 0; + key.type = BTRFS_ROOT_ITEM_KEY; + + ret = btrfs_search_slot(NULL, tree_root, &key, &path, 0, 0); + if (ret < 0) { + err = ret; + goto out; + } else if (ret > 0) { + err = -ENOENT; + goto out; + } + + while (1) { + node = path.nodes[0]; + slot = path.slots[0]; + btrfs_item_key_to_cpu(node, &key, slot); + if (key.objectid > BTRFS_LAST_FREE_OBJECTID) + goto out; + if (key.type == BTRFS_ROOT_ITEM_KEY && + fs_root_objectid(key.objectid)) { + if (key.objectid == BTRFS_TREE_RELOC_OBJECTID) { + cur_root = btrfs_read_fs_root_no_cache(fs_info, + &key); + } else { + key.offset = (u64)-1; + cur_root = btrfs_read_fs_root(fs_info, &key); + } + + if (IS_ERR(cur_root)) { + error("Fail to read fs/subvol tree: %lld", + key.objectid); + err = -EIO; + goto next; + } + + ret = check_fs_root_v2(cur_root, ext_ref); + err |= ret; + + if (key.objectid == BTRFS_TREE_RELOC_OBJECTID) + btrfs_free_fs_root(cur_root); + } else if (key.type == BTRFS_ROOT_REF_KEY || + key.type == BTRFS_ROOT_BACKREF_KEY) { + ret = check_root_ref(tree_root, &key, node, slot); + err |= ret; + } +next: + ret = btrfs_next_item(tree_root, &path); + if (ret > 0) + goto out; + if (ret < 0) { + err = ret; + goto out; + } + } + +out: + btrfs_release_path(&path); + return err; +} + +/* + * Low memory usage version check_chunks_and_extents. + */ +int check_chunks_and_extents_v2(struct btrfs_fs_info *fs_info) +{ + struct btrfs_trans_handle *trans = NULL; + struct btrfs_path path; + struct btrfs_key old_key; + struct btrfs_key key; + struct btrfs_root *root1; + struct btrfs_root *root; + struct btrfs_root *cur_root; + int err = 0; + int ret; + + root = fs_info->fs_root; + + if (repair) { + trans = btrfs_start_transaction(fs_info->extent_root, 1); + if (IS_ERR(trans)) { + error("failed to start transaction before check"); + return PTR_ERR(trans); + } + } + + root1 = root->fs_info->chunk_root; + ret = check_btrfs_root(trans, root1, 0, 1); + err |= ret; + + root1 = root->fs_info->tree_root; + ret = check_btrfs_root(trans, root1, 0, 1); + err |= ret; + + btrfs_init_path(&path); + key.objectid = BTRFS_EXTENT_TREE_OBJECTID; + key.offset = 0; + key.type = BTRFS_ROOT_ITEM_KEY; + + ret = btrfs_search_slot(NULL, root1, &key, &path, 0, 0); + if (ret) { + error("cannot find extent tree in tree_root"); + goto out; + } + + while (1) { + btrfs_item_key_to_cpu(path.nodes[0], &key, path.slots[0]); + if (key.type != BTRFS_ROOT_ITEM_KEY) + goto next; + old_key = key; + key.offset = (u64)-1; + + if (key.objectid == BTRFS_TREE_RELOC_OBJECTID) + cur_root = btrfs_read_fs_root_no_cache(root->fs_info, + &key); + else + cur_root = btrfs_read_fs_root(root->fs_info, &key); + if (IS_ERR(cur_root) || !cur_root) { + error("failed to read tree: %lld", key.objectid); + goto next; + } + + ret = check_btrfs_root(trans, cur_root, 0, 1); + err |= ret; + + if (key.objectid == BTRFS_TREE_RELOC_OBJECTID) + btrfs_free_fs_root(cur_root); + + btrfs_release_path(&path); + ret = btrfs_search_slot(NULL, root->fs_info->tree_root, + &old_key, &path, 0, 0); + if (ret) + goto out; +next: + ret = btrfs_next_item(root1, &path); + if (ret) + goto out; + } +out: + + /* if repair, update block accounting */ + if (repair) { + ret = btrfs_fix_block_accounting(trans, root); + if (ret) + err |= ret; + else + err &= ~BG_ACCOUNTING_ERROR; + } + + if (trans) + btrfs_commit_transaction(trans, root->fs_info->extent_root); + + btrfs_release_path(&path); + + return err; +} diff --git a/check/lowmem.h b/check/lowmem.h index e6ca7634..d1051a0b 100644 --- a/check/lowmem.h +++ b/check/lowmem.h @@ -20,6 +20,8 @@ #ifndef __BTRFS_CHECK_LOWMEM_H__ #define __BTRFS_CHECK_LOWMEM_H__ +#include "check/common.h" + #define ROOT_DIR_ERROR (1<<1) /* bad ROOT_DIR */ #define DIR_ITEM_MISSING (1<<2) /* DIR_ITEM not found */ #define DIR_ITEM_MISMATCH (1<<3) /* DIR_ITEM found but not match */ @@ -59,4 +61,7 @@ #define ACCOUNTING_MISMATCH (1 << 7) /* Used space accounting error */ #define CHUNK_TYPE_MISMATCH (1 << 8) +int check_fs_roots_v2(struct btrfs_fs_info *fs_info); +int check_chunks_and_extents_v2(struct btrfs_fs_info *fs_info); + #endif diff --git a/check/main.c b/check/main.c index 6f5af7fb..98e24afb 100644 --- a/check/main.c +++ b/check/main.c @@ -1579,322 +1579,6 @@ static int process_one_leaf(struct btrfs_root *root, struct extent_buffer *eb, return ret; } -static int update_nodes_refs(struct btrfs_root *root, u64 bytenr, - struct extent_buffer *eb, struct node_refs *nrefs, - u64 level, int check_all); -static int check_inode_item(struct btrfs_root *root, struct btrfs_path *path, - unsigned int ext_ref); - -/* - * Returns >0 Found error, not fatal, should continue - * Returns <0 Fatal error, must exit the whole check - * Returns 0 No errors found - */ -static int process_one_leaf_v2(struct btrfs_root *root, struct btrfs_path *path, - struct node_refs *nrefs, int *level, int ext_ref) -{ - struct extent_buffer *cur = path->nodes[0]; - struct btrfs_key key; - u64 cur_bytenr; - u32 nritems; - u64 first_ino = 0; - int root_level = btrfs_header_level(root->node); - int i; - int ret = 0; /* Final return value */ - int err = 0; /* Positive error bitmap */ - - cur_bytenr = cur->start; - - /* skip to first inode item or the first inode number change */ - nritems = btrfs_header_nritems(cur); - for (i = 0; i < nritems; i++) { - btrfs_item_key_to_cpu(cur, &key, i); - if (i == 0) - first_ino = key.objectid; - if (key.type == BTRFS_INODE_ITEM_KEY || - (first_ino && first_ino != key.objectid)) - break; - } - if (i == nritems) { - path->slots[0] = nritems; - return 0; - } - path->slots[0] = i; - -again: - err |= check_inode_item(root, path, ext_ref); - - /* modify cur since check_inode_item may change path */ - cur = path->nodes[0]; - - if (err & LAST_ITEM) - goto out; - - /* still have inode items in thie leaf */ - if (cur->start == cur_bytenr) - goto again; - - /* - * we have switched to another leaf, above nodes may - * have changed, here walk down the path, if a node - * or leaf is shared, check whether we can skip this - * node or leaf. - */ - for (i = root_level; i >= 0; i--) { - if (path->nodes[i]->start == nrefs->bytenr[i]) - continue; - - ret = update_nodes_refs(root, path->nodes[i]->start, - path->nodes[i], nrefs, i, 0); - if (ret) - goto out; - - if (!nrefs->need_check[i]) { - *level += 1; - break; - } - } - - for (i = 0; i < *level; i++) { - free_extent_buffer(path->nodes[i]); - path->nodes[i] = NULL; - } -out: - err &= ~LAST_ITEM; - if (err && !ret) - ret = err; - return ret; -} - -/* - * for a tree node or leaf, if it's shared, indeed we don't need to iterate it - * in every fs or file tree check. Here we find its all root ids, and only check - * it in the fs or file tree which has the smallest root id. - */ -static int need_check(struct btrfs_root *root, struct ulist *roots) -{ - struct rb_node *node; - struct ulist_node *u; - - /* - * @roots can be empty if it belongs to tree reloc tree - * In that case, we should always check the leaf, as we can't use - * the tree owner to ensure some other root will check it. - */ - if (roots->nnodes == 1 || roots->nnodes == 0) - return 1; - - node = rb_first(&roots->root); - u = rb_entry(node, struct ulist_node, rb_node); - /* - * current root id is not smallest, we skip it and let it be checked - * in the fs or file tree who hash the smallest root id. - */ - if (root->objectid != u->val) - return 0; - - return 1; -} - -static int calc_extent_flag_v2(struct btrfs_root *root, struct extent_buffer *eb, - u64 *flags_ret) -{ - struct btrfs_root *extent_root = root->fs_info->extent_root; - struct btrfs_root_item *ri = &root->root_item; - struct btrfs_extent_inline_ref *iref; - struct btrfs_extent_item *ei; - struct btrfs_key key; - struct btrfs_path *path = NULL; - unsigned long ptr; - unsigned long end; - u64 flags; - u64 owner = 0; - u64 offset; - int slot; - int type; - int ret = 0; - - /* - * Except file/reloc tree, we can not have FULL BACKREF MODE - */ - if (root->objectid < BTRFS_FIRST_FREE_OBJECTID) - goto normal; - - /* root node */ - if (eb->start == btrfs_root_bytenr(ri)) - goto normal; - - if (btrfs_header_flag(eb, BTRFS_HEADER_FLAG_RELOC)) - goto full_backref; - - owner = btrfs_header_owner(eb); - if (owner == root->objectid) - goto normal; - - path = btrfs_alloc_path(); - if (!path) - return -ENOMEM; - - key.objectid = btrfs_header_bytenr(eb); - key.type = (u8)-1; - key.offset = (u64)-1; - - ret = btrfs_search_slot(NULL, extent_root, &key, path, 0, 0); - if (ret <= 0) { - ret = -EIO; - goto out; - } - - if (ret > 0) { - ret = btrfs_previous_extent_item(extent_root, path, - key.objectid); - if (ret) - goto full_backref; - - } - btrfs_item_key_to_cpu(path->nodes[0], &key, path->slots[0]); - - eb = path->nodes[0]; - slot = path->slots[0]; - ei = btrfs_item_ptr(eb, slot, struct btrfs_extent_item); - - flags = btrfs_extent_flags(eb, ei); - if (flags & BTRFS_BLOCK_FLAG_FULL_BACKREF) - goto full_backref; - - ptr = (unsigned long)(ei + 1); - end = (unsigned long)ei + btrfs_item_size_nr(eb, slot); - - if (key.type == BTRFS_EXTENT_ITEM_KEY) - ptr += sizeof(struct btrfs_tree_block_info); - -next: - /* Reached extent item ends normally */ - if (ptr == end) - goto full_backref; - - /* Beyond extent item end, wrong item size */ - if (ptr > end) { - error("extent item at bytenr %llu slot %d has wrong size", - eb->start, slot); - goto full_backref; - } - - iref = (struct btrfs_extent_inline_ref *)ptr; - offset = btrfs_extent_inline_ref_offset(eb, iref); - type = btrfs_extent_inline_ref_type(eb, iref); - - if (type == BTRFS_TREE_BLOCK_REF_KEY && offset == owner) - goto normal; - ptr += btrfs_extent_inline_ref_size(type); - goto next; - -normal: - *flags_ret &= ~BTRFS_BLOCK_FLAG_FULL_BACKREF; - goto out; - -full_backref: - *flags_ret |= BTRFS_BLOCK_FLAG_FULL_BACKREF; -out: - btrfs_free_path(path); - return ret; -} - -/* - * for a tree node or leaf, we record its reference count, so later if we still - * process this node or leaf, don't need to compute its reference count again. - * - * @bytenr if @bytenr == (u64)-1, only update nrefs->full_backref[level] - */ -static int update_nodes_refs(struct btrfs_root *root, u64 bytenr, - struct extent_buffer *eb, struct node_refs *nrefs, - u64 level, int check_all) -{ - struct ulist *roots; - u64 refs = 0; - u64 flags = 0; - int root_level = btrfs_header_level(root->node); - int check; - int ret; - - if (nrefs->bytenr[level] == bytenr) - return 0; - - if (bytenr != (u64)-1) { - /* the return value of this function seems a mistake */ - ret = btrfs_lookup_extent_info(NULL, root, bytenr, - level, 1, &refs, &flags); - /* temporary fix */ - if (ret < 0 && !check_all) - return ret; - - nrefs->bytenr[level] = bytenr; - nrefs->refs[level] = refs; - nrefs->full_backref[level] = 0; - nrefs->checked[level] = 0; - - if (refs > 1) { - ret = btrfs_find_all_roots(NULL, root->fs_info, bytenr, - 0, &roots); - if (ret) - return -EIO; - - check = need_check(root, roots); - ulist_free(roots); - nrefs->need_check[level] = check; - } else { - if (!check_all) { - nrefs->need_check[level] = 1; - } else { - if (level == root_level) { - nrefs->need_check[level] = 1; - } else { - /* - * The node refs may have not been - * updated if upper needs checking (the - * lowest root_objectid) the node can - * be checked. - */ - nrefs->need_check[level] = - nrefs->need_check[level + 1]; - } - } - } - } - - if (check_all && eb) { - calc_extent_flag_v2(root, eb, &flags); - if (flags & BTRFS_BLOCK_FLAG_FULL_BACKREF) - nrefs->full_backref[level] = 1; - } - - return 0; -} - -/* - * @level if @level == -1 means extent data item - * else normal treeblocl. - */ -static int should_check_extent_strictly(struct btrfs_root *root, - struct node_refs *nrefs, int level) -{ - int root_level = btrfs_header_level(root->node); - - if (level > root_level || level < -1) - return 1; - if (level == root_level) - return 1; - /* - * if the upper node is marked full backref, it should contain shared - * backref of the parent (except owner == root->objectid). - */ - while (++level <= root_level) - if (nrefs->refs[level] > 1) - return 0; - - return 1; -} - static int walk_down_tree(struct btrfs_root *root, struct btrfs_path *path, struct walk_control *wc, int *level, struct node_refs *nrefs) @@ -2024,341 +1708,6 @@ out: return err; } -/* - * Update global fs information. - */ -static void account_bytes(struct btrfs_root *root, struct btrfs_path *path, - int level) -{ - u32 free_nrs; - struct extent_buffer *eb = path->nodes[level]; - - total_btree_bytes += eb->len; - if (fs_root_objectid(root->objectid)) - total_fs_tree_bytes += eb->len; - if (btrfs_header_owner(eb) == BTRFS_EXTENT_TREE_OBJECTID) - total_extent_tree_bytes += eb->len; - - if (level == 0) { - btree_space_waste += btrfs_leaf_free_space(root, eb); - } else { - free_nrs = (BTRFS_NODEPTRS_PER_BLOCK(root->fs_info) - - btrfs_header_nritems(eb)); - btree_space_waste += free_nrs * sizeof(struct btrfs_key_ptr); - } -} - -/* - * This function only handles BACKREF_MISSING, - * If corresponding extent item exists, increase the ref, else insert an extent - * item and backref. - * - * Returns error bits after repair. - */ -static int repair_tree_block_ref(struct btrfs_trans_handle *trans, - struct btrfs_root *root, - struct extent_buffer *node, - struct node_refs *nrefs, int level, int err) -{ - struct btrfs_fs_info *fs_info = root->fs_info; - struct btrfs_root *extent_root = fs_info->extent_root; - struct btrfs_path path; - struct btrfs_extent_item *ei; - struct btrfs_tree_block_info *bi; - struct btrfs_key key; - struct extent_buffer *eb; - u32 size = sizeof(*ei); - u32 node_size = root->fs_info->nodesize; - int insert_extent = 0; - int skinny_metadata = btrfs_fs_incompat(fs_info, SKINNY_METADATA); - int root_level = btrfs_header_level(root->node); - int generation; - int ret; - u64 owner; - u64 bytenr; - u64 flags = BTRFS_EXTENT_FLAG_TREE_BLOCK; - u64 parent = 0; - - if ((err & BACKREF_MISSING) == 0) - return err; - - WARN_ON(level > BTRFS_MAX_LEVEL); - WARN_ON(level < 0); - - btrfs_init_path(&path); - bytenr = btrfs_header_bytenr(node); - owner = btrfs_header_owner(node); - generation = btrfs_header_generation(node); - - key.objectid = bytenr; - key.type = (u8)-1; - key.offset = (u64)-1; - - /* Search for the extent item */ - ret = btrfs_search_slot(NULL, extent_root, &key, &path, 0, 0); - if (ret <= 0) { - ret = -EIO; - goto out; - } - - ret = btrfs_previous_extent_item(extent_root, &path, bytenr); - if (ret) - insert_extent = 1; - - /* calculate if the extent item flag is full backref or not */ - if (nrefs->full_backref[level] != 0) - flags |= BTRFS_BLOCK_FLAG_FULL_BACKREF; - - /* insert an extent item */ - if (insert_extent) { - struct btrfs_disk_key copy_key; - - generation = btrfs_header_generation(node); - - if (level < root_level && nrefs->full_backref[level + 1] && - owner != root->objectid) { - flags |= BTRFS_BLOCK_FLAG_FULL_BACKREF; - } - - key.objectid = bytenr; - if (!skinny_metadata) { - key.type = BTRFS_EXTENT_ITEM_KEY; - key.offset = node_size; - size += sizeof(*bi); - } else { - key.type = BTRFS_METADATA_ITEM_KEY; - key.offset = level; - } - - btrfs_release_path(&path); - ret = btrfs_insert_empty_item(trans, extent_root, &path, &key, - size); - if (ret) - goto out; - - eb = path.nodes[0]; - ei = btrfs_item_ptr(eb, path.slots[0], struct btrfs_extent_item); - - btrfs_set_extent_refs(eb, ei, 0); - btrfs_set_extent_generation(eb, ei, generation); - btrfs_set_extent_flags(eb, ei, flags); - - if (!skinny_metadata) { - bi = (struct btrfs_tree_block_info *)(ei + 1); - memset_extent_buffer(eb, 0, (unsigned long)bi, - sizeof(*bi)); - btrfs_set_disk_key_objectid(©_key, root->objectid); - btrfs_set_disk_key_type(©_key, 0); - btrfs_set_disk_key_offset(©_key, 0); - - btrfs_set_tree_block_level(eb, bi, level); - btrfs_set_tree_block_key(eb, bi, ©_key); - } - btrfs_mark_buffer_dirty(eb); - printf("Added an extent item [%llu %u]\n", bytenr, node_size); - btrfs_update_block_group(extent_root, bytenr, node_size, 1, 0); - - nrefs->refs[level] = 0; - nrefs->full_backref[level] = - flags & BTRFS_BLOCK_FLAG_FULL_BACKREF; - btrfs_release_path(&path); - } - - if (level < root_level && nrefs->full_backref[level + 1] && - owner != root->objectid) - parent = nrefs->bytenr[level + 1]; - - /* increase the ref */ - ret = btrfs_inc_extent_ref(trans, extent_root, bytenr, node_size, - parent, root->objectid, level, 0); - - nrefs->refs[level]++; -out: - btrfs_release_path(&path); - if (ret) { - error( - "failed to repair tree block ref start %llu root %llu due to %s", - bytenr, root->objectid, strerror(-ret)); - } else { - printf("Added one tree block ref start %llu %s %llu\n", - bytenr, parent ? "parent" : "root", - parent ? parent : root->objectid); - err &= ~BACKREF_MISSING; - } - - return err; -} - -static int check_inode_item(struct btrfs_root *root, struct btrfs_path *path, - unsigned int ext_ref); -static int check_tree_block_ref(struct btrfs_root *root, - struct extent_buffer *eb, u64 bytenr, - int level, u64 owner, struct node_refs *nrefs); -static int check_leaf_items(struct btrfs_trans_handle *trans, - struct btrfs_root *root, struct btrfs_path *path, - struct node_refs *nrefs, int account_bytes); - -/* - * @trans just for lowmem repair mode - * @check all if not 0 then check all tree block backrefs and items - * 0 then just check relationship of items in fs tree(s) - * - * Returns >0 Found error, should continue - * Returns <0 Fatal error, must exit the whole check - * Returns 0 No errors found - */ -static int walk_down_tree_v2(struct btrfs_trans_handle *trans, - struct btrfs_root *root, struct btrfs_path *path, - int *level, struct node_refs *nrefs, int ext_ref, - int check_all) - -{ - enum btrfs_tree_block_status status; - u64 bytenr; - u64 ptr_gen; - struct btrfs_fs_info *fs_info = root->fs_info; - struct extent_buffer *next; - struct extent_buffer *cur; - int ret; - int err = 0; - int check; - int account_file_data = 0; - - WARN_ON(*level < 0); - WARN_ON(*level >= BTRFS_MAX_LEVEL); - - ret = update_nodes_refs(root, btrfs_header_bytenr(path->nodes[*level]), - path->nodes[*level], nrefs, *level, check_all); - if (ret < 0) - return ret; - - while (*level >= 0) { - WARN_ON(*level < 0); - WARN_ON(*level >= BTRFS_MAX_LEVEL); - cur = path->nodes[*level]; - bytenr = btrfs_header_bytenr(cur); - check = nrefs->need_check[*level]; - - if (btrfs_header_level(cur) != *level) - WARN_ON(1); - /* - * Update bytes accounting and check tree block ref - * NOTE: Doing accounting and check before checking nritems - * is necessary because of empty node/leaf. - */ - if ((check_all && !nrefs->checked[*level]) || - (!check_all && nrefs->need_check[*level])) { - ret = check_tree_block_ref(root, cur, - btrfs_header_bytenr(cur), btrfs_header_level(cur), - btrfs_header_owner(cur), nrefs); - - if (repair && ret) - ret = repair_tree_block_ref(trans, root, - path->nodes[*level], nrefs, *level, ret); - err |= ret; - - if (check_all && nrefs->need_check[*level] && - nrefs->refs[*level]) { - account_bytes(root, path, *level); - account_file_data = 1; - } - nrefs->checked[*level] = 1; - } - - if (path->slots[*level] >= btrfs_header_nritems(cur)) - break; - - /* Don't forgot to check leaf/node validation */ - if (*level == 0) { - /* skip duplicate check */ - if (check || !check_all) { - ret = btrfs_check_leaf(root, NULL, cur); - if (ret != BTRFS_TREE_BLOCK_CLEAN) { - err |= -EIO; - break; - } - } - - ret = 0; - if (!check_all) - ret = process_one_leaf_v2(root, path, nrefs, - level, ext_ref); - else - ret = check_leaf_items(trans, root, path, - nrefs, account_file_data); - err |= ret; - break; - } else { - if (check || !check_all) { - ret = btrfs_check_node(root, NULL, cur); - if (ret != BTRFS_TREE_BLOCK_CLEAN) { - err |= -EIO; - break; - } - } - } - - bytenr = btrfs_node_blockptr(cur, path->slots[*level]); - ptr_gen = btrfs_node_ptr_generation(cur, path->slots[*level]); - - ret = update_nodes_refs(root, bytenr, NULL, nrefs, *level - 1, - check_all); - if (ret < 0) - break; - /* - * check all trees in check_chunks_and_extent_v2 - * check shared node once in check_fs_roots - */ - if (!check_all && !nrefs->need_check[*level - 1]) { - path->slots[*level]++; - continue; - } - - next = btrfs_find_tree_block(fs_info, bytenr, fs_info->nodesize); - if (!next || !btrfs_buffer_uptodate(next, ptr_gen)) { - free_extent_buffer(next); - reada_walk_down(root, cur, path->slots[*level]); - next = read_tree_block(fs_info, bytenr, ptr_gen); - if (!extent_buffer_uptodate(next)) { - struct btrfs_key node_key; - - btrfs_node_key_to_cpu(path->nodes[*level], - &node_key, - path->slots[*level]); - btrfs_add_corrupt_extent_record(fs_info, - &node_key, path->nodes[*level]->start, - fs_info->nodesize, *level); - err |= -EIO; - break; - } - } - - ret = check_child_node(cur, path->slots[*level], next); - err |= ret; - if (ret < 0) - break; - - 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; - break; - } - - *level = *level - 1; - free_extent_buffer(path->nodes[*level]); - path->nodes[*level] = next; - path->slots[*level] = 0; - account_file_data = 0; - - update_nodes_refs(root, (u64)-1, next, nrefs, *level, check_all); - } - return err; -} - static int walk_up_tree(struct btrfs_root *root, struct btrfs_path *path, struct walk_control *wc, int *level) { @@ -2383,27 +1732,6 @@ static int walk_up_tree(struct btrfs_root *root, struct btrfs_path *path, return 1; } -static int walk_up_tree_v2(struct btrfs_root *root, struct btrfs_path *path, - int *level) -{ - int i; - struct extent_buffer *leaf; - - for (i = *level; i < BTRFS_MAX_LEVEL - 1 && path->nodes[i]; i++) { - leaf = path->nodes[i]; - if (path->slots[i] + 1 < btrfs_header_nritems(leaf)) { - path->slots[i]++; - *level = i; - return 0; - } else { - free_extent_buffer(path->nodes[*level]); - path->nodes[*level] = NULL; - *level = i + 1; - } - } - return 1; -} - static int check_root_dir(struct inode_record *rec) { struct inode_backref *backref; @@ -2618,15 +1946,6 @@ static int delete_dir_index(struct btrfs_root *root, return ret; } -static int create_inode_item_lowmem(struct btrfs_trans_handle *trans, - struct btrfs_root *root, u64 ino, - u8 filetype) -{ - u32 mode = (filetype == BTRFS_FT_DIR ? S_IFDIR : S_IFREG) | 0755; - - return insert_inode_item(trans, root, ino, 0, 0, 0, mode); -} - static int create_inode_item(struct btrfs_root *root, struct inode_record *rec, int root_dir) { @@ -4078,1807 +3397,6 @@ out: return err; } -/* - * Find the @index according by @ino and name. - * Notice:time efficiency is O(N) - * - * @root: the root of the fs/file tree - * @index_ret: the index as return value - * @namebuf: the name to match - * @name_len: the length of name to match - * @file_type: the file_type of INODE_ITEM to match - * - * Returns 0 if found and *@index_ret will be modified with right value - * Returns< 0 not found and *@index_ret will be (u64)-1 - */ -static int find_dir_index(struct btrfs_root *root, u64 dirid, u64 location_id, - u64 *index_ret, char *namebuf, u32 name_len, - u8 file_type) -{ - struct btrfs_path path; - struct extent_buffer *node; - struct btrfs_dir_item *di; - struct btrfs_key key; - struct btrfs_key location; - char name[BTRFS_NAME_LEN] = {0}; - - u32 total; - u32 cur = 0; - u32 len; - u32 data_len; - u8 filetype; - int slot; - int ret; - - ASSERT(index_ret); - - /* search from the last index */ - key.objectid = dirid; - key.offset = (u64)-1; - key.type = BTRFS_DIR_INDEX_KEY; - - btrfs_init_path(&path); - ret = btrfs_search_slot(NULL, root, &key, &path, 0, 0); - if (ret < 0) - return ret; - -loop: - ret = btrfs_previous_item(root, &path, dirid, BTRFS_DIR_INDEX_KEY); - if (ret) { - ret = -ENOENT; - *index_ret = (64)-1; - goto out; - } - /* Check whether inode_id/filetype/name match */ - node = path.nodes[0]; - slot = path.slots[0]; - di = btrfs_item_ptr(node, slot, struct btrfs_dir_item); - total = btrfs_item_size_nr(node, slot); - while (cur < total) { - ret = -ENOENT; - len = btrfs_dir_name_len(node, di); - data_len = btrfs_dir_data_len(node, di); - - btrfs_dir_item_key_to_cpu(node, di, &location); - if (location.objectid != location_id || - location.type != BTRFS_INODE_ITEM_KEY || - location.offset != 0) - goto next; - - filetype = btrfs_dir_type(node, di); - if (file_type != filetype) - goto next; - - if (len > BTRFS_NAME_LEN) - len = BTRFS_NAME_LEN; - - read_extent_buffer(node, name, (unsigned long)(di + 1), len); - if (len != name_len || strncmp(namebuf, name, len)) - goto next; - - btrfs_item_key_to_cpu(path.nodes[0], &key, path.slots[0]); - *index_ret = key.offset; - ret = 0; - goto out; -next: - len += sizeof(*di) + data_len; - di = (struct btrfs_dir_item *)((char *)di + len); - cur += len; - } - goto loop; - -out: - btrfs_release_path(&path); - return ret; -} - -/* - * Find DIR_ITEM/DIR_INDEX for the given key and check it with the specified - * INODE_REF/INODE_EXTREF match. - * - * @root: the root of the fs/file tree - * @key: the key of the DIR_ITEM/DIR_INDEX, key->offset will be right - * value while find index - * @location_key: location key of the struct btrfs_dir_item to match - * @name: the name to match - * @namelen: the length of name - * @file_type: the type of file to math - * - * Return 0 if no error occurred. - * Return DIR_ITEM_MISSING/DIR_INDEX_MISSING if couldn't find - * DIR_ITEM/DIR_INDEX - * Return DIR_ITEM_MISMATCH/DIR_INDEX_MISMATCH if INODE_REF/INODE_EXTREF - * and DIR_ITEM/DIR_INDEX mismatch - */ -static int find_dir_item(struct btrfs_root *root, struct btrfs_key *key, - struct btrfs_key *location_key, char *name, - u32 namelen, u8 file_type) -{ - struct btrfs_path path; - struct extent_buffer *node; - struct btrfs_dir_item *di; - struct btrfs_key location; - char namebuf[BTRFS_NAME_LEN] = {0}; - u32 total; - u32 cur = 0; - u32 len; - u32 data_len; - u8 filetype; - int slot; - int ret; - - /* get the index by traversing all index */ - if (key->type == BTRFS_DIR_INDEX_KEY && key->offset == (u64)-1) { - ret = find_dir_index(root, key->objectid, - location_key->objectid, &key->offset, - name, namelen, file_type); - if (ret) - ret = DIR_INDEX_MISSING; - return ret; - } - - btrfs_init_path(&path); - ret = btrfs_search_slot(NULL, root, key, &path, 0, 0); - if (ret) { - ret = key->type == BTRFS_DIR_ITEM_KEY ? DIR_ITEM_MISSING : - DIR_INDEX_MISSING; - goto out; - } - - /* Check whether inode_id/filetype/name match */ - node = path.nodes[0]; - slot = path.slots[0]; - di = btrfs_item_ptr(node, slot, struct btrfs_dir_item); - total = btrfs_item_size_nr(node, slot); - while (cur < total) { - ret = key->type == BTRFS_DIR_ITEM_KEY ? - DIR_ITEM_MISMATCH : DIR_INDEX_MISMATCH; - - len = btrfs_dir_name_len(node, di); - data_len = btrfs_dir_data_len(node, di); - - btrfs_dir_item_key_to_cpu(node, di, &location); - if (location.objectid != location_key->objectid || - location.type != location_key->type || - location.offset != location_key->offset) - goto next; - - filetype = btrfs_dir_type(node, di); - if (file_type != filetype) - goto next; - - if (len > BTRFS_NAME_LEN) { - len = BTRFS_NAME_LEN; - warning("root %llu %s[%llu %llu] name too long %u, trimmed", - root->objectid, - key->type == BTRFS_DIR_ITEM_KEY ? - "DIR_ITEM" : "DIR_INDEX", - key->objectid, key->offset, len); - } - read_extent_buffer(node, namebuf, (unsigned long)(di + 1), - len); - if (len != namelen || strncmp(namebuf, name, len)) - goto next; - - ret = 0; - goto out; -next: - len += sizeof(*di) + data_len; - di = (struct btrfs_dir_item *)((char *)di + len); - cur += len; - } - -out: - btrfs_release_path(&path); - return ret; -} - -/* - * Prints inode ref error message - */ -static void print_inode_ref_err(struct btrfs_root *root, struct btrfs_key *key, - u64 index, const char *namebuf, int name_len, - u8 filetype, int err) -{ - if (!err) - return; - - /* root dir error */ - if (key->objectid == BTRFS_FIRST_FREE_OBJECTID) { - error( - "root %llu root dir shouldn't have INODE REF[%llu %llu] name %s", - root->objectid, key->objectid, key->offset, namebuf); - return; - } - - /* normal error */ - if (err & (DIR_ITEM_MISMATCH | DIR_ITEM_MISSING)) - error("root %llu DIR ITEM[%llu %llu] %s name %s filetype %u", - root->objectid, key->offset, - btrfs_name_hash(namebuf, name_len), - err & DIR_ITEM_MISMATCH ? "mismatch" : "missing", - namebuf, filetype); - if (err & (DIR_INDEX_MISMATCH | DIR_INDEX_MISSING)) - error("root %llu DIR INDEX[%llu %llu] %s name %s filetype %u", - root->objectid, key->offset, index, - err & DIR_ITEM_MISMATCH ? "mismatch" : "missing", - namebuf, filetype); -} - -/* - * Insert the missing inode item. - * - * Returns 0 means success. - * Returns <0 means error. - */ -static int repair_inode_item_missing(struct btrfs_root *root, u64 ino, - u8 filetype) -{ - struct btrfs_key key; - struct btrfs_trans_handle *trans; - struct btrfs_path path; - int ret; - - key.objectid = ino; - key.type = BTRFS_INODE_ITEM_KEY; - key.offset = 0; - - btrfs_init_path(&path); - trans = btrfs_start_transaction(root, 1); - if (IS_ERR(trans)) { - ret = -EIO; - goto out; - } - - ret = btrfs_search_slot(trans, root, &key, &path, 1, 1); - if (ret < 0 || !ret) - goto fail; - - /* insert inode item */ - create_inode_item_lowmem(trans, root, ino, filetype); - ret = 0; -fail: - btrfs_commit_transaction(trans, root); -out: - if (ret) - error("failed to repair root %llu INODE ITEM[%llu] missing", - root->objectid, ino); - btrfs_release_path(&path); - return ret; -} - -/* - * The ternary means dir item, dir index and relative inode ref. - * The function handles errs: INODE_MISSING, DIR_INDEX_MISSING - * DIR_INDEX_MISMATCH, DIR_ITEM_MISSING, DIR_ITEM_MISMATCH by the follow - * strategy: - * If two of three is missing or mismatched, delete the existing one. - * If one of three is missing or mismatched, add the missing one. - * - * returns 0 means success. - * returns not 0 means on error; - */ -int repair_ternary_lowmem(struct btrfs_root *root, u64 dir_ino, u64 ino, - u64 index, char *name, int name_len, u8 filetype, - int err) -{ - struct btrfs_trans_handle *trans; - int stage = 0; - int ret = 0; - - /* - * stage shall be one of following valild values: - * 0: Fine, nothing to do. - * 1: One of three is wrong, so add missing one. - * 2: Two of three is wrong, so delete existed one. - */ - if (err & (DIR_INDEX_MISMATCH | DIR_INDEX_MISSING)) - stage++; - if (err & (DIR_ITEM_MISMATCH | DIR_ITEM_MISSING)) - stage++; - if (err & (INODE_REF_MISSING)) - stage++; - - /* stage must be smllarer than 3 */ - ASSERT(stage < 3); - - trans = btrfs_start_transaction(root, 1); - if (stage == 2) { - ret = btrfs_unlink(trans, root, ino, dir_ino, index, name, - name_len, 0); - goto out; - } - if (stage == 1) { - ret = btrfs_add_link(trans, root, ino, dir_ino, name, name_len, - filetype, &index, 1, 1); - goto out; - } -out: - btrfs_commit_transaction(trans, root); - - if (ret) - error("fail to repair inode %llu name %s filetype %u", - ino, name, filetype); - else - printf("%s ref/dir_item of inode %llu name %s filetype %u\n", - stage == 2 ? "Delete" : "Add", - ino, name, filetype); - - return ret; -} - -/* - * Traverse the given INODE_REF and call find_dir_item() to find related - * DIR_ITEM/DIR_INDEX. - * - * @root: the root of the fs/file tree - * @ref_key: the key of the INODE_REF - * @path the path provides node and slot - * @refs: the count of INODE_REF - * @mode: the st_mode of INODE_ITEM - * @name_ret: returns with the first ref's name - * @name_len_ret: len of the name_ret - * - * Return 0 if no error occurred. - */ -static int check_inode_ref(struct btrfs_root *root, struct btrfs_key *ref_key, - struct btrfs_path *path, char *name_ret, - u32 *namelen_ret, u64 *refs_ret, int mode) -{ - struct btrfs_key key; - struct btrfs_key location; - struct btrfs_inode_ref *ref; - struct extent_buffer *node; - char namebuf[BTRFS_NAME_LEN] = {0}; - u32 total; - u32 cur = 0; - u32 len; - u32 name_len; - u64 index; - int ret; - int err = 0; - int tmp_err; - int slot; - int need_research = 0; - u64 refs; - -begin: - err = 0; - cur = 0; - refs = *refs_ret; - - /* since after repair, path and the dir item may be changed */ - if (need_research) { - need_research = 0; - btrfs_release_path(path); - ret = btrfs_search_slot(NULL, root, ref_key, path, 0, 0); - /* the item was deleted, let path point to the last checked item */ - if (ret > 0) { - if (path->slots[0] == 0) - btrfs_prev_leaf(root, path); - else - path->slots[0]--; - } - if (ret) - goto out; - } - - location.objectid = ref_key->objectid; - location.type = BTRFS_INODE_ITEM_KEY; - location.offset = 0; - node = path->nodes[0]; - slot = path->slots[0]; - - memset(namebuf, 0, sizeof(namebuf) / sizeof(*namebuf)); - ref = btrfs_item_ptr(node, slot, struct btrfs_inode_ref); - total = btrfs_item_size_nr(node, slot); - -next: - /* Update inode ref count */ - refs++; - tmp_err = 0; - index = btrfs_inode_ref_index(node, ref); - name_len = btrfs_inode_ref_name_len(node, ref); - - if (name_len <= BTRFS_NAME_LEN) { - len = name_len; - } else { - len = BTRFS_NAME_LEN; - warning("root %llu INODE_REF[%llu %llu] name too long", - root->objectid, ref_key->objectid, ref_key->offset); - } - - read_extent_buffer(node, namebuf, (unsigned long)(ref + 1), len); - - /* copy the first name found to name_ret */ - if (refs == 1 && name_ret) { - memcpy(name_ret, namebuf, len); - *namelen_ret = len; - } - - /* Check root dir ref */ - if (ref_key->objectid == BTRFS_FIRST_FREE_OBJECTID) { - if (index != 0 || len != strlen("..") || - strncmp("..", namebuf, len) || - ref_key->offset != BTRFS_FIRST_FREE_OBJECTID) { - /* set err bits then repair will delete the ref */ - err |= DIR_INDEX_MISSING; - err |= DIR_ITEM_MISSING; - } - goto end; - } - - /* Find related DIR_INDEX */ - key.objectid = ref_key->offset; - key.type = BTRFS_DIR_INDEX_KEY; - key.offset = index; - tmp_err |= find_dir_item(root, &key, &location, namebuf, len, - imode_to_type(mode)); - - /* Find related dir_item */ - key.objectid = ref_key->offset; - key.type = BTRFS_DIR_ITEM_KEY; - key.offset = btrfs_name_hash(namebuf, len); - tmp_err |= find_dir_item(root, &key, &location, namebuf, len, - imode_to_type(mode)); -end: - if (tmp_err && repair) { - ret = repair_ternary_lowmem(root, ref_key->offset, - ref_key->objectid, index, namebuf, - name_len, imode_to_type(mode), - tmp_err); - if (!ret) { - need_research = 1; - goto begin; - } - } - print_inode_ref_err(root, ref_key, index, namebuf, name_len, - imode_to_type(mode), tmp_err); - err |= tmp_err; - len = sizeof(*ref) + name_len; - ref = (struct btrfs_inode_ref *)((char *)ref + len); - cur += len; - if (cur < total) - goto next; - -out: - *refs_ret = refs; - return err; -} - -/* - * Traverse the given INODE_EXTREF and call find_dir_item() to find related - * DIR_ITEM/DIR_INDEX. - * - * @root: the root of the fs/file tree - * @ref_key: the key of the INODE_EXTREF - * @refs: the count of INODE_EXTREF - * @mode: the st_mode of INODE_ITEM - * - * Return 0 if no error occurred. - */ -static int check_inode_extref(struct btrfs_root *root, - struct btrfs_key *ref_key, - struct extent_buffer *node, int slot, u64 *refs, - int mode) -{ - struct btrfs_key key; - struct btrfs_key location; - struct btrfs_inode_extref *extref; - char namebuf[BTRFS_NAME_LEN] = {0}; - u32 total; - u32 cur = 0; - u32 len; - u32 name_len; - u64 index; - u64 parent; - int ret; - int err = 0; - - location.objectid = ref_key->objectid; - location.type = BTRFS_INODE_ITEM_KEY; - location.offset = 0; - - extref = btrfs_item_ptr(node, slot, struct btrfs_inode_extref); - total = btrfs_item_size_nr(node, slot); - -next: - /* update inode ref count */ - (*refs)++; - name_len = btrfs_inode_extref_name_len(node, extref); - index = btrfs_inode_extref_index(node, extref); - parent = btrfs_inode_extref_parent(node, extref); - if (name_len <= BTRFS_NAME_LEN) { - len = name_len; - } else { - len = BTRFS_NAME_LEN; - warning("root %llu INODE_EXTREF[%llu %llu] name too long", - root->objectid, ref_key->objectid, ref_key->offset); - } - read_extent_buffer(node, namebuf, (unsigned long)(extref + 1), len); - - /* Check root dir ref name */ - if (index == 0 && strncmp(namebuf, "..", name_len)) { - error("root %llu INODE_EXTREF[%llu %llu] ROOT_DIR name shouldn't be %s", - root->objectid, ref_key->objectid, ref_key->offset, - namebuf); - err |= ROOT_DIR_ERROR; - } - - /* find related dir_index */ - key.objectid = parent; - key.type = BTRFS_DIR_INDEX_KEY; - key.offset = index; - ret = find_dir_item(root, &key, &location, namebuf, len, mode); - err |= ret; - - /* find related dir_item */ - key.objectid = parent; - key.type = BTRFS_DIR_ITEM_KEY; - key.offset = btrfs_name_hash(namebuf, len); - ret = find_dir_item(root, &key, &location, namebuf, len, mode); - err |= ret; - - len = sizeof(*extref) + name_len; - extref = (struct btrfs_inode_extref *)((char *)extref + len); - cur += len; - - if (cur < total) - goto next; - - return err; -} - -/* - * Find INODE_REF/INODE_EXTREF for the given key and check it with the specified - * DIR_ITEM/DIR_INDEX match. - * Return with @index_ret. - * - * @root: the root of the fs/file tree - * @key: the key of the INODE_REF/INODE_EXTREF - * @name: the name in the INODE_REF/INODE_EXTREF - * @namelen: the length of name in the INODE_REF/INODE_EXTREF - * @index_ret: the index in the INODE_REF/INODE_EXTREF, - * value (64)-1 means do not check index - * @ext_ref: the EXTENDED_IREF feature - * - * Return 0 if no error occurred. - * Return >0 for error bitmap - */ -static int find_inode_ref(struct btrfs_root *root, struct btrfs_key *key, - char *name, int namelen, u64 *index_ret, - unsigned int ext_ref) -{ - struct btrfs_path path; - struct btrfs_inode_ref *ref; - struct btrfs_inode_extref *extref; - struct extent_buffer *node; - char ref_namebuf[BTRFS_NAME_LEN] = {0}; - u32 total; - u32 cur = 0; - u32 len; - u32 ref_namelen; - u64 ref_index; - u64 parent; - u64 dir_id; - int slot; - int ret; - - ASSERT(index_ret); - - btrfs_init_path(&path); - ret = btrfs_search_slot(NULL, root, key, &path, 0, 0); - if (ret) { - ret = INODE_REF_MISSING; - goto extref; - } - - node = path.nodes[0]; - slot = path.slots[0]; - - ref = btrfs_item_ptr(node, slot, struct btrfs_inode_ref); - total = btrfs_item_size_nr(node, slot); - - /* Iterate all entry of INODE_REF */ - while (cur < total) { - ret = INODE_REF_MISSING; - - ref_namelen = btrfs_inode_ref_name_len(node, ref); - ref_index = btrfs_inode_ref_index(node, ref); - if (*index_ret != (u64)-1 && *index_ret != ref_index) - goto next_ref; - - if (cur + sizeof(*ref) + ref_namelen > total || - ref_namelen > BTRFS_NAME_LEN) { - warning("root %llu INODE %s[%llu %llu] name too long", - root->objectid, - key->type == BTRFS_INODE_REF_KEY ? - "REF" : "EXTREF", - key->objectid, key->offset); - - if (cur + sizeof(*ref) > total) - break; - len = min_t(u32, total - cur - sizeof(*ref), - BTRFS_NAME_LEN); - } else { - len = ref_namelen; - } - - read_extent_buffer(node, ref_namebuf, (unsigned long)(ref + 1), - len); - - if (len != namelen || strncmp(ref_namebuf, name, len)) - goto next_ref; - - *index_ret = ref_index; - ret = 0; - goto out; -next_ref: - len = sizeof(*ref) + ref_namelen; - ref = (struct btrfs_inode_ref *)((char *)ref + len); - cur += len; - } - -extref: - /* Skip if not support EXTENDED_IREF feature */ - if (!ext_ref) - goto out; - - btrfs_release_path(&path); - btrfs_init_path(&path); - - dir_id = key->offset; - key->type = BTRFS_INODE_EXTREF_KEY; - key->offset = btrfs_extref_hash(dir_id, name, namelen); - - ret = btrfs_search_slot(NULL, root, key, &path, 0, 0); - if (ret) { - ret = INODE_REF_MISSING; - goto out; - } - - node = path.nodes[0]; - slot = path.slots[0]; - - extref = btrfs_item_ptr(node, slot, struct btrfs_inode_extref); - cur = 0; - total = btrfs_item_size_nr(node, slot); - - /* Iterate all entry of INODE_EXTREF */ - while (cur < total) { - ret = INODE_REF_MISSING; - - ref_namelen = btrfs_inode_extref_name_len(node, extref); - ref_index = btrfs_inode_extref_index(node, extref); - parent = btrfs_inode_extref_parent(node, extref); - if (*index_ret != (u64)-1 && *index_ret != ref_index) - goto next_extref; - - if (parent != dir_id) - goto next_extref; - - if (ref_namelen <= BTRFS_NAME_LEN) { - len = ref_namelen; - } else { - len = BTRFS_NAME_LEN; - warning("root %llu INODE %s[%llu %llu] name too long", - root->objectid, - key->type == BTRFS_INODE_REF_KEY ? - "REF" : "EXTREF", - key->objectid, key->offset); - } - read_extent_buffer(node, ref_namebuf, - (unsigned long)(extref + 1), len); - - if (len != namelen || strncmp(ref_namebuf, name, len)) - goto next_extref; - - *index_ret = ref_index; - ret = 0; - goto out; - -next_extref: - len = sizeof(*extref) + ref_namelen; - extref = (struct btrfs_inode_extref *)((char *)extref + len); - cur += len; - - } -out: - btrfs_release_path(&path); - return ret; -} - -static void print_dir_item_err(struct btrfs_root *root, struct btrfs_key *key, - u64 ino, u64 index, const char *namebuf, - int name_len, u8 filetype, int err) -{ - if (err & (DIR_ITEM_MISMATCH | DIR_ITEM_MISSING)) { - error("root %llu DIR ITEM[%llu %llu] name %s filetype %d %s", - root->objectid, key->objectid, key->offset, namebuf, - filetype, - err & DIR_ITEM_MISMATCH ? "mismath" : "missing"); - } - - if (err & (DIR_INDEX_MISMATCH | DIR_INDEX_MISSING)) { - error("root %llu DIR INDEX[%llu %llu] name %s filetype %d %s", - root->objectid, key->objectid, index, namebuf, filetype, - err & DIR_ITEM_MISMATCH ? "mismath" : "missing"); - } - - if (err & (INODE_ITEM_MISSING | INODE_ITEM_MISMATCH)) { - error( - "root %llu INODE_ITEM[%llu] index %llu name %s filetype %d %s", - root->objectid, ino, index, namebuf, filetype, - err & INODE_ITEM_MISMATCH ? "mismath" : "missing"); - } - - if (err & INODE_REF_MISSING) - error( - "root %llu INODE REF[%llu, %llu] name %s filetype %u missing", - root->objectid, ino, key->objectid, namebuf, filetype); - -} - -/* - * Call repair_inode_item_missing and repair_ternary_lowmem to repair - * - * Returns error after repair - */ -static int repair_dir_item(struct btrfs_root *root, u64 dirid, u64 ino, - u64 index, u8 filetype, char *namebuf, u32 name_len, - int err) -{ - int ret; - - if (err & INODE_ITEM_MISSING) { - ret = repair_inode_item_missing(root, ino, filetype); - if (!ret) - err &= ~(INODE_ITEM_MISMATCH | INODE_ITEM_MISSING); - } - - if (err & ~(INODE_ITEM_MISMATCH | INODE_ITEM_MISSING)) { - ret = repair_ternary_lowmem(root, dirid, ino, index, namebuf, - name_len, filetype, err); - if (!ret) { - err &= ~(DIR_INDEX_MISMATCH | DIR_INDEX_MISSING); - err &= ~(DIR_ITEM_MISMATCH | DIR_ITEM_MISSING); - err &= ~(INODE_REF_MISSING); - } - } - return err; -} - -static int __count_dir_isize(struct btrfs_root *root, u64 ino, int type, - u64 *size_ret) -{ - struct btrfs_key key; - struct btrfs_path path; - u32 len; - struct btrfs_dir_item *di; - int ret; - int cur = 0; - int total = 0; - - ASSERT(size_ret); - *size_ret = 0; - - key.objectid = ino; - key.type = type; - key.offset = (u64)-1; - - btrfs_init_path(&path); - ret = btrfs_search_slot(NULL, root, &key, &path, 0, 0); - if (ret < 0) { - ret = -EIO; - goto out; - } - /* if found, go to spacial case */ - if (ret == 0) - goto special_case; - -loop: - ret = btrfs_previous_item(root, &path, ino, type); - - if (ret) { - ret = 0; - goto out; - } - -special_case: - di = btrfs_item_ptr(path.nodes[0], path.slots[0], struct btrfs_dir_item); - cur = 0; - total = btrfs_item_size_nr(path.nodes[0], path.slots[0]); - - while (cur < total) { - len = btrfs_dir_name_len(path.nodes[0], di); - if (len > BTRFS_NAME_LEN) - len = BTRFS_NAME_LEN; - *size_ret += len; - - len += btrfs_dir_data_len(path.nodes[0], di); - len += sizeof(*di); - di = (struct btrfs_dir_item *)((char *)di + len); - cur += len; - } - goto loop; - -out: - btrfs_release_path(&path); - return ret; -} - -static int count_dir_isize(struct btrfs_root *root, u64 ino, u64 *size) -{ - u64 item_size; - u64 index_size; - int ret; - - ASSERT(size); - ret = __count_dir_isize(root, ino, BTRFS_DIR_ITEM_KEY, &item_size); - if (ret) - goto out; - - ret = __count_dir_isize(root, ino, BTRFS_DIR_INDEX_KEY, &index_size); - if (ret) - goto out; - - *size = item_size + index_size; - -out: - if (ret) - error("failed to count root %llu INODE[%llu] root size", - root->objectid, ino); - return ret; -} - -/* - * Traverse the given DIR_ITEM/DIR_INDEX and check related INODE_ITEM and - * call find_inode_ref() to check related INODE_REF/INODE_EXTREF. - * - * @root: the root of the fs/file tree - * @key: the key of the INODE_REF/INODE_EXTREF - * @path: the path - * @size: the st_size of the INODE_ITEM - * @ext_ref: the EXTENDED_IREF feature - * - * Return 0 if no error occurred. - * Return DIR_COUNT_AGAIN if the isize of the inode should be recalculated. - */ -static int check_dir_item(struct btrfs_root *root, struct btrfs_key *di_key, - struct btrfs_path *path, u64 *size, - unsigned int ext_ref) -{ - struct btrfs_dir_item *di; - struct btrfs_inode_item *ii; - struct btrfs_key key; - struct btrfs_key location; - struct extent_buffer *node; - int slot; - char namebuf[BTRFS_NAME_LEN] = {0}; - u32 total; - u32 cur = 0; - u32 len; - u32 name_len; - u32 data_len; - u8 filetype; - u32 mode = 0; - u64 index; - int ret; - int err; - int tmp_err; - int need_research = 0; - - /* - * For DIR_ITEM set index to (u64)-1, so that find_inode_ref - * ignore index check. - */ - if (di_key->type == BTRFS_DIR_INDEX_KEY) - index = di_key->offset; - else - index = (u64)-1; -begin: - err = 0; - cur = 0; - - /* since after repair, path and the dir item may be changed */ - if (need_research) { - need_research = 0; - err |= DIR_COUNT_AGAIN; - btrfs_release_path(path); - ret = btrfs_search_slot(NULL, root, di_key, path, 0, 0); - /* the item was deleted, let path point the last checked item */ - if (ret > 0) { - if (path->slots[0] == 0) - btrfs_prev_leaf(root, path); - else - path->slots[0]--; - } - if (ret) - goto out; - } - - node = path->nodes[0]; - slot = path->slots[0]; - - di = btrfs_item_ptr(node, slot, struct btrfs_dir_item); - total = btrfs_item_size_nr(node, slot); - memset(namebuf, 0, sizeof(namebuf) / sizeof(*namebuf)); - - while (cur < total) { - data_len = btrfs_dir_data_len(node, di); - tmp_err = 0; - if (data_len) - error("root %llu %s[%llu %llu] data_len shouldn't be %u", - root->objectid, - di_key->type == BTRFS_DIR_ITEM_KEY ? "DIR_ITEM" : "DIR_INDEX", - di_key->objectid, di_key->offset, data_len); - - name_len = btrfs_dir_name_len(node, di); - if (name_len <= BTRFS_NAME_LEN) { - len = name_len; - } else { - len = BTRFS_NAME_LEN; - warning("root %llu %s[%llu %llu] name too long", - root->objectid, - di_key->type == BTRFS_DIR_ITEM_KEY ? "DIR_ITEM" : "DIR_INDEX", - di_key->objectid, di_key->offset); - } - (*size) += name_len; - read_extent_buffer(node, namebuf, (unsigned long)(di + 1), - len); - filetype = btrfs_dir_type(node, di); - - if (di_key->type == BTRFS_DIR_ITEM_KEY && - di_key->offset != btrfs_name_hash(namebuf, len)) { - err |= -EIO; - error("root %llu DIR_ITEM[%llu %llu] name %s namelen %u filetype %u mismatch with its hash, wanted %llu have %llu", - root->objectid, di_key->objectid, di_key->offset, - namebuf, len, filetype, di_key->offset, - btrfs_name_hash(namebuf, len)); - } - - btrfs_dir_item_key_to_cpu(node, di, &location); - /* Ignore related ROOT_ITEM check */ - if (location.type == BTRFS_ROOT_ITEM_KEY) - goto next; - - btrfs_release_path(path); - /* Check relative INODE_ITEM(existence/filetype) */ - ret = btrfs_search_slot(NULL, root, &location, path, 0, 0); - if (ret) { - tmp_err |= INODE_ITEM_MISSING; - goto next; - } - - ii = btrfs_item_ptr(path->nodes[0], path->slots[0], - struct btrfs_inode_item); - mode = btrfs_inode_mode(path->nodes[0], ii); - if (imode_to_type(mode) != filetype) { - tmp_err |= INODE_ITEM_MISMATCH; - goto next; - } - - /* Check relative INODE_REF/INODE_EXTREF */ - key.objectid = location.objectid; - key.type = BTRFS_INODE_REF_KEY; - key.offset = di_key->objectid; - tmp_err |= find_inode_ref(root, &key, namebuf, len, - &index, ext_ref); - - /* check relative INDEX/ITEM */ - key.objectid = di_key->objectid; - if (key.type == BTRFS_DIR_ITEM_KEY) { - key.type = BTRFS_DIR_INDEX_KEY; - key.offset = index; - } else { - key.type = BTRFS_DIR_ITEM_KEY; - key.offset = btrfs_name_hash(namebuf, name_len); - } - - tmp_err |= find_dir_item(root, &key, &location, namebuf, - name_len, filetype); - /* find_dir_item may find index */ - if (key.type == BTRFS_DIR_INDEX_KEY) - index = key.offset; -next: - - if (tmp_err && repair) { - ret = repair_dir_item(root, di_key->objectid, - location.objectid, index, - imode_to_type(mode), namebuf, - name_len, tmp_err); - if (ret != tmp_err) { - need_research = 1; - goto begin; - } - } - btrfs_release_path(path); - print_dir_item_err(root, di_key, location.objectid, index, - namebuf, name_len, filetype, tmp_err); - err |= tmp_err; - len = sizeof(*di) + name_len + data_len; - di = (struct btrfs_dir_item *)((char *)di + len); - cur += len; - - if (di_key->type == BTRFS_DIR_INDEX_KEY && cur < total) { - error("root %llu DIR_INDEX[%llu %llu] should contain only one entry", - root->objectid, di_key->objectid, - di_key->offset); - break; - } - } -out: - /* research path */ - btrfs_release_path(path); - ret = btrfs_search_slot(NULL, root, di_key, path, 0, 0); - if (ret) - err |= ret > 0 ? -ENOENT : ret; - return err; -} - -/* - * Wrapper function of btrfs_punch_hole. - * - * Returns 0 means success. - * Returns not 0 means error. - */ -static int punch_extent_hole(struct btrfs_root *root, u64 ino, u64 start, - u64 len) -{ - struct btrfs_trans_handle *trans; - int ret = 0; - - trans = btrfs_start_transaction(root, 1); - if (IS_ERR(trans)) - return PTR_ERR(trans); - - ret = btrfs_punch_hole(trans, root, ino, start, len); - if (ret) - error("failed to add hole [%llu, %llu] in inode [%llu]", - start, len, ino); - else - printf("Add a hole [%llu, %llu] in inode [%llu]\n", start, len, - ino); - - btrfs_commit_transaction(trans, root); - return ret; -} - -/* - * Check file extent datasum/hole, update the size of the file extents, - * check and update the last offset of the file extent. - * - * @root: the root of fs/file tree. - * @fkey: the key of the file extent. - * @nodatasum: INODE_NODATASUM feature. - * @size: the sum of all EXTENT_DATA items size for this inode. - * @end: the offset of the last extent. - * - * Return 0 if no error occurred. - */ -static int check_file_extent(struct btrfs_root *root, struct btrfs_key *fkey, - struct extent_buffer *node, int slot, - unsigned int nodatasum, u64 *size, u64 *end) -{ - struct btrfs_file_extent_item *fi; - u64 disk_bytenr; - u64 disk_num_bytes; - u64 extent_num_bytes; - u64 extent_offset; - u64 csum_found; /* In byte size, sectorsize aligned */ - u64 search_start; /* Logical range start we search for csum */ - u64 search_len; /* Logical range len we search for csum */ - unsigned int extent_type; - unsigned int is_hole; - int compressed = 0; - int ret; - int err = 0; - - fi = btrfs_item_ptr(node, slot, struct btrfs_file_extent_item); - - /* Check inline extent */ - extent_type = btrfs_file_extent_type(node, fi); - if (extent_type == BTRFS_FILE_EXTENT_INLINE) { - struct btrfs_item *e = btrfs_item_nr(slot); - u32 item_inline_len; - - item_inline_len = btrfs_file_extent_inline_item_len(node, e); - extent_num_bytes = btrfs_file_extent_inline_len(node, slot, fi); - compressed = btrfs_file_extent_compression(node, fi); - if (extent_num_bytes == 0) { - error( - "root %llu EXTENT_DATA[%llu %llu] has empty inline extent", - root->objectid, fkey->objectid, fkey->offset); - err |= FILE_EXTENT_ERROR; - } - if (!compressed && extent_num_bytes != item_inline_len) { - error( - "root %llu EXTENT_DATA[%llu %llu] wrong inline size, have: %llu, expected: %u", - root->objectid, fkey->objectid, fkey->offset, - extent_num_bytes, item_inline_len); - err |= FILE_EXTENT_ERROR; - } - *end += extent_num_bytes; - *size += extent_num_bytes; - return err; - } - - /* Check extent type */ - if (extent_type != BTRFS_FILE_EXTENT_REG && - extent_type != BTRFS_FILE_EXTENT_PREALLOC) { - err |= FILE_EXTENT_ERROR; - error("root %llu EXTENT_DATA[%llu %llu] type bad", - root->objectid, fkey->objectid, fkey->offset); - return err; - } - - /* Check REG_EXTENT/PREALLOC_EXTENT */ - disk_bytenr = btrfs_file_extent_disk_bytenr(node, fi); - disk_num_bytes = btrfs_file_extent_disk_num_bytes(node, fi); - extent_num_bytes = btrfs_file_extent_num_bytes(node, fi); - extent_offset = btrfs_file_extent_offset(node, fi); - compressed = btrfs_file_extent_compression(node, fi); - is_hole = (disk_bytenr == 0) && (disk_num_bytes == 0); - - /* - * Check EXTENT_DATA csum - * - * For plain (uncompressed) extent, we should only check the range - * we're referring to, as it's possible that part of prealloc extent - * has been written, and has csum: - * - * |<--- Original large preallocated extent A ---->| - * |<- Prealloc File Extent ->|<- Regular Extent ->| - * No csum Has csum - * - * For compressed extent, we should check the whole range. - */ - if (!compressed) { - search_start = disk_bytenr + extent_offset; - search_len = extent_num_bytes; - } else { - search_start = disk_bytenr; - search_len = disk_num_bytes; - } - ret = count_csum_range(root->fs_info, search_start, search_len, &csum_found); - if (csum_found > 0 && nodatasum) { - err |= ODD_CSUM_ITEM; - error("root %llu EXTENT_DATA[%llu %llu] nodatasum shouldn't have datasum", - root->objectid, fkey->objectid, fkey->offset); - } else if (extent_type == BTRFS_FILE_EXTENT_REG && !nodatasum && - !is_hole && (ret < 0 || csum_found < search_len)) { - err |= CSUM_ITEM_MISSING; - error("root %llu EXTENT_DATA[%llu %llu] csum missing, have: %llu, expected: %llu", - root->objectid, fkey->objectid, fkey->offset, - csum_found, search_len); - } else if (extent_type == BTRFS_FILE_EXTENT_PREALLOC && csum_found > 0) { - err |= ODD_CSUM_ITEM; - error("root %llu EXTENT_DATA[%llu %llu] prealloc shouldn't have csum, but has: %llu", - root->objectid, fkey->objectid, fkey->offset, csum_found); - } - - /* Check EXTENT_DATA hole */ - if (!no_holes && *end != fkey->offset) { - if (repair) - ret = punch_extent_hole(root, fkey->objectid, - *end, fkey->offset - *end); - if (!repair || ret) { - err |= FILE_EXTENT_ERROR; - error( -"root %llu EXTENT_DATA[%llu %llu] gap exists, expected: EXTENT_DATA[%llu %llu]", - root->objectid, fkey->objectid, fkey->offset, - fkey->objectid, *end); - } - } - - *end += extent_num_bytes; - if (!is_hole) - *size += extent_num_bytes; - - return err; -} - -/* - * Set inode item nbytes to @nbytes - * - * Returns 0 on success - * Returns != 0 on error - */ -static int repair_inode_nbytes_lowmem(struct btrfs_root *root, - struct btrfs_path *path, - u64 ino, u64 nbytes) -{ - struct btrfs_trans_handle *trans; - struct btrfs_inode_item *ii; - struct btrfs_key key; - struct btrfs_key research_key; - int err = 0; - int ret; - - btrfs_item_key_to_cpu(path->nodes[0], &research_key, path->slots[0]); - - key.objectid = ino; - key.type = BTRFS_INODE_ITEM_KEY; - key.offset = 0; - - trans = btrfs_start_transaction(root, 1); - if (IS_ERR(trans)) { - ret = PTR_ERR(trans); - err |= ret; - goto out; - } - - btrfs_release_path(path); - ret = btrfs_search_slot(trans, root, &key, path, 0, 1); - if (ret > 0) - ret = -ENOENT; - if (ret) { - err |= ret; - goto fail; - } - - ii = btrfs_item_ptr(path->nodes[0], path->slots[0], - struct btrfs_inode_item); - btrfs_set_inode_nbytes(path->nodes[0], ii, nbytes); - btrfs_mark_buffer_dirty(path->nodes[0]); -fail: - btrfs_commit_transaction(trans, root); -out: - if (ret) - error("failed to set nbytes in inode %llu root %llu", - ino, root->root_key.objectid); - else - printf("Set nbytes in inode item %llu root %llu\n to %llu", ino, - root->root_key.objectid, nbytes); - - /* research path */ - btrfs_release_path(path); - ret = btrfs_search_slot(NULL, root, &research_key, path, 0, 0); - err |= ret; - - return err; -} - -/* - * Set directory inode isize to @isize. - * - * Returns 0 on success. - * Returns != 0 on error. - */ -static int repair_dir_isize_lowmem(struct btrfs_root *root, - struct btrfs_path *path, - u64 ino, u64 isize) -{ - struct btrfs_trans_handle *trans; - struct btrfs_inode_item *ii; - struct btrfs_key key; - struct btrfs_key research_key; - int ret; - int err = 0; - - btrfs_item_key_to_cpu(path->nodes[0], &research_key, path->slots[0]); - - key.objectid = ino; - key.type = BTRFS_INODE_ITEM_KEY; - key.offset = 0; - - trans = btrfs_start_transaction(root, 1); - if (IS_ERR(trans)) { - ret = PTR_ERR(trans); - err |= ret; - goto out; - } - - btrfs_release_path(path); - ret = btrfs_search_slot(trans, root, &key, path, 0, 1); - if (ret > 0) - ret = -ENOENT; - if (ret) { - err |= ret; - goto fail; - } - - ii = btrfs_item_ptr(path->nodes[0], path->slots[0], - struct btrfs_inode_item); - btrfs_set_inode_size(path->nodes[0], ii, isize); - btrfs_mark_buffer_dirty(path->nodes[0]); -fail: - btrfs_commit_transaction(trans, root); -out: - if (ret) - error("failed to set isize in inode %llu root %llu", - ino, root->root_key.objectid); - else - printf("Set isize in inode %llu root %llu to %llu\n", - ino, root->root_key.objectid, isize); - - btrfs_release_path(path); - ret = btrfs_search_slot(NULL, root, &research_key, path, 0, 0); - err |= ret; - - return err; -} - -/* - * Wrapper function for btrfs_add_orphan_item(). - * - * Returns 0 on success. - * Returns != 0 on error. - */ -static int repair_inode_orphan_item_lowmem(struct btrfs_root *root, - struct btrfs_path *path, u64 ino) -{ - struct btrfs_trans_handle *trans; - struct btrfs_key research_key; - int ret; - int err = 0; - - btrfs_item_key_to_cpu(path->nodes[0], &research_key, path->slots[0]); - - trans = btrfs_start_transaction(root, 1); - if (IS_ERR(trans)) { - ret = PTR_ERR(trans); - err |= ret; - goto out; - } - - btrfs_release_path(path); - ret = btrfs_add_orphan_item(trans, root, path, ino); - err |= ret; - btrfs_commit_transaction(trans, root); -out: - if (ret) - error("failed to add inode %llu as orphan item root %llu", - ino, root->root_key.objectid); - else - printf("Added inode %llu as orphan item root %llu\n", - ino, root->root_key.objectid); - - btrfs_release_path(path); - ret = btrfs_search_slot(NULL, root, &research_key, path, 0, 0); - err |= ret; - - return err; -} - -/* Set inode_item nlink to @ref_count. - * If @ref_count == 0, move it to "lost+found" and increase @ref_count. - * - * Returns 0 on success - */ -static int repair_inode_nlinks_lowmem(struct btrfs_root *root, - struct btrfs_path *path, u64 ino, - const char *name, u32 namelen, - u64 ref_count, u8 filetype, u64 *nlink) -{ - struct btrfs_trans_handle *trans; - struct btrfs_inode_item *ii; - struct btrfs_key key; - struct btrfs_key old_key; - char namebuf[BTRFS_NAME_LEN] = {0}; - int name_len; - int ret; - int ret2; - - /* save the key */ - btrfs_item_key_to_cpu(path->nodes[0], &old_key, path->slots[0]); - - if (name && namelen) { - ASSERT(namelen <= BTRFS_NAME_LEN); - memcpy(namebuf, name, namelen); - name_len = namelen; - } else { - sprintf(namebuf, "%llu", ino); - name_len = count_digits(ino); - printf("Can't find file name for inode %llu, use %s instead\n", - ino, namebuf); - } - - trans = btrfs_start_transaction(root, 1); - if (IS_ERR(trans)) { - ret = PTR_ERR(trans); - goto out; - } - - btrfs_release_path(path); - /* if refs is 0, put it into lostfound */ - if (ref_count == 0) { - ret = link_inode_to_lostfound(trans, root, path, ino, namebuf, - name_len, filetype, &ref_count); - if (ret) - goto fail; - } - - /* reset inode_item's nlink to ref_count */ - key.objectid = ino; - key.type = BTRFS_INODE_ITEM_KEY; - key.offset = 0; - - btrfs_release_path(path); - ret = btrfs_search_slot(trans, root, &key, path, 0, 1); - if (ret > 0) - ret = -ENOENT; - if (ret) - goto fail; - - ii = btrfs_item_ptr(path->nodes[0], path->slots[0], - struct btrfs_inode_item); - btrfs_set_inode_nlink(path->nodes[0], ii, ref_count); - btrfs_mark_buffer_dirty(path->nodes[0]); - - if (nlink) - *nlink = ref_count; -fail: - btrfs_commit_transaction(trans, root); -out: - if (ret) - error( - "fail to repair nlink of inode %llu root %llu name %s filetype %u", - root->objectid, ino, namebuf, filetype); - else - printf("Fixed nlink of inode %llu root %llu name %s filetype %u\n", - root->objectid, ino, namebuf, filetype); - - /* research */ - btrfs_release_path(path); - ret2 = btrfs_search_slot(NULL, root, &old_key, path, 0, 0); - if (ret2 < 0) - return ret |= ret2; - return ret; -} - -/* - * Check INODE_ITEM and related ITEMs (the same inode number) - * 1. check link count - * 2. check inode ref/extref - * 3. check dir item/index - * - * @ext_ref: the EXTENDED_IREF feature - * - * Return 0 if no error occurred. - * Return >0 for error or hit the traversal is done(by error bitmap) - */ -static int check_inode_item(struct btrfs_root *root, struct btrfs_path *path, - unsigned int ext_ref) -{ - struct extent_buffer *node; - struct btrfs_inode_item *ii; - struct btrfs_key key; - struct btrfs_key last_key; - u64 inode_id; - u32 mode; - u64 nlink; - u64 nbytes; - u64 isize; - u64 size = 0; - u64 refs = 0; - u64 extent_end = 0; - u64 extent_size = 0; - unsigned int dir; - unsigned int nodatasum; - int slot; - int ret; - int err = 0; - char namebuf[BTRFS_NAME_LEN] = {0}; - u32 name_len = 0; - - node = path->nodes[0]; - slot = path->slots[0]; - - btrfs_item_key_to_cpu(node, &key, slot); - inode_id = key.objectid; - - if (inode_id == BTRFS_ORPHAN_OBJECTID) { - ret = btrfs_next_item(root, path); - if (ret > 0) - err |= LAST_ITEM; - return err; - } - - ii = btrfs_item_ptr(node, slot, struct btrfs_inode_item); - isize = btrfs_inode_size(node, ii); - nbytes = btrfs_inode_nbytes(node, ii); - mode = btrfs_inode_mode(node, ii); - dir = imode_to_type(mode) == BTRFS_FT_DIR; - nlink = btrfs_inode_nlink(node, ii); - nodatasum = btrfs_inode_flags(node, ii) & BTRFS_INODE_NODATASUM; - - while (1) { - btrfs_item_key_to_cpu(path->nodes[0], &last_key, path->slots[0]); - ret = btrfs_next_item(root, path); - if (ret < 0) { - /* out will fill 'err' rusing current statistics */ - goto out; - } else if (ret > 0) { - err |= LAST_ITEM; - goto out; - } - - node = path->nodes[0]; - slot = path->slots[0]; - btrfs_item_key_to_cpu(node, &key, slot); - if (key.objectid != inode_id) - goto out; - - switch (key.type) { - case BTRFS_INODE_REF_KEY: - ret = check_inode_ref(root, &key, path, namebuf, - &name_len, &refs, mode); - err |= ret; - break; - case BTRFS_INODE_EXTREF_KEY: - if (key.type == BTRFS_INODE_EXTREF_KEY && !ext_ref) - warning("root %llu EXTREF[%llu %llu] isn't supported", - root->objectid, key.objectid, - key.offset); - ret = check_inode_extref(root, &key, node, slot, &refs, - mode); - err |= ret; - break; - case BTRFS_DIR_ITEM_KEY: - case BTRFS_DIR_INDEX_KEY: - if (!dir) { - warning("root %llu INODE[%llu] mode %u shouldn't have DIR_INDEX[%llu %llu]", - root->objectid, inode_id, - imode_to_type(mode), key.objectid, - key.offset); - } - ret = check_dir_item(root, &key, path, &size, ext_ref); - err |= ret; - break; - case BTRFS_EXTENT_DATA_KEY: - if (dir) { - warning("root %llu DIR INODE[%llu] shouldn't EXTENT_DATA[%llu %llu]", - root->objectid, inode_id, key.objectid, - key.offset); - } - ret = check_file_extent(root, &key, node, slot, - nodatasum, &extent_size, - &extent_end); - err |= ret; - break; - case BTRFS_XATTR_ITEM_KEY: - break; - default: - error("ITEM[%llu %u %llu] UNKNOWN TYPE", - key.objectid, key.type, key.offset); - } - } - -out: - if (err & LAST_ITEM) { - btrfs_release_path(path); - ret = btrfs_search_slot(NULL, root, &last_key, path, 0, 0); - if (ret) - return err; - } - - /* verify INODE_ITEM nlink/isize/nbytes */ - if (dir) { - if (repair && (err & DIR_COUNT_AGAIN)) { - err &= ~DIR_COUNT_AGAIN; - count_dir_isize(root, inode_id, &size); - } - - if ((nlink != 1 || refs != 1) && repair) { - ret = repair_inode_nlinks_lowmem(root, path, inode_id, - namebuf, name_len, refs, imode_to_type(mode), - &nlink); - } - - if (nlink != 1) { - err |= LINK_COUNT_ERROR; - error("root %llu DIR INODE[%llu] shouldn't have more than one link(%llu)", - root->objectid, inode_id, nlink); - } - - /* - * Just a warning, as dir inode nbytes is just an - * instructive value. - */ - if (!IS_ALIGNED(nbytes, root->fs_info->nodesize)) { - warning("root %llu DIR INODE[%llu] nbytes should be aligned to %u", - root->objectid, inode_id, - root->fs_info->nodesize); - } - - if (isize != size) { - if (repair) - ret = repair_dir_isize_lowmem(root, path, - inode_id, size); - if (!repair || ret) { - err |= ISIZE_ERROR; - error( - "root %llu DIR INODE [%llu] size %llu not equal to %llu", - root->objectid, inode_id, isize, size); - } - } - } else { - if (nlink != refs) { - if (repair) - ret = repair_inode_nlinks_lowmem(root, path, - inode_id, namebuf, name_len, refs, - imode_to_type(mode), &nlink); - if (!repair || ret) { - err |= LINK_COUNT_ERROR; - error( - "root %llu INODE[%llu] nlink(%llu) not equal to inode_refs(%llu)", - root->objectid, inode_id, nlink, refs); - } - } else if (!nlink) { - if (repair) - ret = repair_inode_orphan_item_lowmem(root, - path, inode_id); - if (!repair || ret) { - err |= ORPHAN_ITEM; - error("root %llu INODE[%llu] is orphan item", - root->objectid, inode_id); - } - } - - if (!nbytes && !no_holes && extent_end < isize) { - if (repair) - ret = punch_extent_hole(root, inode_id, - extent_end, isize - extent_end); - if (!repair || ret) { - err |= NBYTES_ERROR; - error( - "root %llu INODE[%llu] size %llu should have a file extent hole", - root->objectid, inode_id, isize); - } - } - - if (nbytes != extent_size) { - if (repair) - ret = repair_inode_nbytes_lowmem(root, path, - inode_id, extent_size); - if (!repair || ret) { - err |= NBYTES_ERROR; - error( - "root %llu INODE[%llu] nbytes %llu not equal to extent_size %llu", - root->objectid, inode_id, nbytes, - extent_size); - } - } - } - - if (err & LAST_ITEM) - btrfs_next_item(root, path); - return err; -} - -/* - * Insert the missing inode item and inode ref. - * - * Normal INODE_ITEM_MISSING and INODE_REF_MISSING are handled in backref * dir. - * Root dir should be handled specially because root dir is the root of fs. - * - * returns err (>0 or 0) after repair - */ -static int repair_fs_first_inode(struct btrfs_root *root, int err) -{ - struct btrfs_trans_handle *trans; - struct btrfs_key key; - struct btrfs_path path; - int filetype = BTRFS_FT_DIR; - int ret = 0; - - btrfs_init_path(&path); - - if (err & INODE_REF_MISSING) { - key.objectid = BTRFS_FIRST_FREE_OBJECTID; - key.type = BTRFS_INODE_REF_KEY; - key.offset = BTRFS_FIRST_FREE_OBJECTID; - - trans = btrfs_start_transaction(root, 1); - if (IS_ERR(trans)) { - ret = PTR_ERR(trans); - goto out; - } - - btrfs_release_path(&path); - ret = btrfs_search_slot(trans, root, &key, &path, 1, 1); - if (ret) - goto trans_fail; - - ret = btrfs_insert_inode_ref(trans, root, "..", 2, - BTRFS_FIRST_FREE_OBJECTID, - BTRFS_FIRST_FREE_OBJECTID, 0); - if (ret) - goto trans_fail; - - printf("Add INODE_REF[%llu %llu] name %s\n", - BTRFS_FIRST_FREE_OBJECTID, BTRFS_FIRST_FREE_OBJECTID, - ".."); - err &= ~INODE_REF_MISSING; -trans_fail: - if (ret) - error("fail to insert first inode's ref"); - btrfs_commit_transaction(trans, root); - } - - if (err & INODE_ITEM_MISSING) { - ret = repair_inode_item_missing(root, - BTRFS_FIRST_FREE_OBJECTID, filetype); - if (ret) - goto out; - err &= ~INODE_ITEM_MISSING; - } -out: - if (ret) - error("fail to repair first inode"); - btrfs_release_path(&path); - return err; -} - -/* - * check first root dir's inode_item and inode_ref - * - * returns 0 means no error - * returns >0 means error - * returns <0 means fatal error - */ -static int check_fs_first_inode(struct btrfs_root *root, unsigned int ext_ref) -{ - struct btrfs_path path; - struct btrfs_key key; - struct btrfs_inode_item *ii; - u64 index; - u32 mode; - int err = 0; - int ret; - - key.objectid = BTRFS_FIRST_FREE_OBJECTID; - key.type = BTRFS_INODE_ITEM_KEY; - key.offset = 0; - - /* For root being dropped, we don't need to check first inode */ - if (btrfs_root_refs(&root->root_item) == 0 && - btrfs_disk_key_objectid(&root->root_item.drop_progress) >= - BTRFS_FIRST_FREE_OBJECTID) - return 0; - - btrfs_init_path(&path); - ret = btrfs_search_slot(NULL, root, &key, &path, 0, 0); - if (ret < 0) - goto out; - if (ret > 0) { - ret = 0; - err |= INODE_ITEM_MISSING; - } else { - ii = btrfs_item_ptr(path.nodes[0], path.slots[0], - struct btrfs_inode_item); - mode = btrfs_inode_mode(path.nodes[0], ii); - if (imode_to_type(mode) != BTRFS_FT_DIR) - err |= INODE_ITEM_MISMATCH; - } - - /* lookup first inode ref */ - key.offset = BTRFS_FIRST_FREE_OBJECTID; - key.type = BTRFS_INODE_REF_KEY; - /* special index value */ - index = 0; - - ret = find_inode_ref(root, &key, "..", strlen(".."), &index, ext_ref); - if (ret < 0) - goto out; - err |= ret; - -out: - btrfs_release_path(&path); - - if (err && repair) - err = repair_fs_first_inode(root, err); - - if (err & (INODE_ITEM_MISSING | INODE_ITEM_MISMATCH)) - error("root dir INODE_ITEM is %s", - err & INODE_ITEM_MISMATCH ? "mismatch" : "missing"); - if (err & INODE_REF_MISSING) - error("root dir INODE_REF is missing"); - - return ret < 0 ? ret : err; -} - static struct tree_backref *find_tree_backref(struct extent_record *rec, u64 parent, u64 root) { @@ -5938,278 +3456,6 @@ static struct data_backref *find_data_backref(struct extent_record *rec, return back; } -/* - * This function calls walk_down_tree_v2 and walk_up_tree_v2 to check tree - * blocks and integrity of fs tree items. - * - * @root: the root of the tree to be checked. - * @ext_ref feature EXTENDED_IREF is enable or not. - * @account if NOT 0 means check the tree (including tree)'s treeblocks. - * otherwise means check fs tree(s) items relationship and - * @root MUST be a fs tree root. - * Returns 0 represents OK. - * Returns not 0 represents error. - */ -static int check_btrfs_root(struct btrfs_trans_handle *trans, - struct btrfs_root *root, unsigned int ext_ref, - int check_all) - -{ - struct btrfs_path path; - struct node_refs nrefs; - struct btrfs_root_item *root_item = &root->root_item; - int ret; - int level; - int err = 0; - - memset(&nrefs, 0, sizeof(nrefs)); - if (!check_all) { - /* - * We need to manually check the first inode item (256) - * As the following traversal function will only start from - * the first inode item in the leaf, if inode item (256) is - * missing we will skip it forever. - */ - ret = check_fs_first_inode(root, ext_ref); - if (ret < 0) - return ret; - } - - - level = btrfs_header_level(root->node); - btrfs_init_path(&path); - - if (btrfs_root_refs(root_item) > 0 || - btrfs_disk_key_objectid(&root_item->drop_progress) == 0) { - path.nodes[level] = root->node; - path.slots[level] = 0; - extent_buffer_get(root->node); - } else { - struct btrfs_key key; - - btrfs_disk_key_to_cpu(&key, &root_item->drop_progress); - level = root_item->drop_level; - path.lowest_level = level; - ret = btrfs_search_slot(NULL, root, &key, &path, 0, 0); - if (ret < 0) - goto out; - ret = 0; - } - - while (1) { - ret = walk_down_tree_v2(trans, root, &path, &level, &nrefs, - ext_ref, check_all); - - err |= !!ret; - - /* if ret is negative, walk shall stop */ - if (ret < 0) { - ret = err; - break; - } - - ret = walk_up_tree_v2(root, &path, &level); - if (ret != 0) { - /* Normal exit, reset ret to err */ - ret = err; - break; - } - } - -out: - btrfs_release_path(&path); - return ret; -} - -/* - * Iterate all items in the tree and call check_inode_item() to check. - * - * @root: the root of the tree to be checked. - * @ext_ref: the EXTENDED_IREF feature - * - * Return 0 if no error found. - * Return <0 for error. - */ -static int check_fs_root_v2(struct btrfs_root *root, unsigned int ext_ref) -{ - reset_cached_block_groups(root->fs_info); - return check_btrfs_root(NULL, root, ext_ref, 0); -} - -/* - * Find the relative ref for root_ref and root_backref. - * - * @root: the root of the root tree. - * @ref_key: the key of the root ref. - * - * Return 0 if no error occurred. - */ -static int check_root_ref(struct btrfs_root *root, struct btrfs_key *ref_key, - struct extent_buffer *node, int slot) -{ - struct btrfs_path path; - struct btrfs_key key; - struct btrfs_root_ref *ref; - struct btrfs_root_ref *backref; - char ref_name[BTRFS_NAME_LEN] = {0}; - char backref_name[BTRFS_NAME_LEN] = {0}; - u64 ref_dirid; - u64 ref_seq; - u32 ref_namelen; - u64 backref_dirid; - u64 backref_seq; - u32 backref_namelen; - u32 len; - int ret; - int err = 0; - - ref = btrfs_item_ptr(node, slot, struct btrfs_root_ref); - ref_dirid = btrfs_root_ref_dirid(node, ref); - ref_seq = btrfs_root_ref_sequence(node, ref); - ref_namelen = btrfs_root_ref_name_len(node, ref); - - if (ref_namelen <= BTRFS_NAME_LEN) { - len = ref_namelen; - } else { - len = BTRFS_NAME_LEN; - warning("%s[%llu %llu] ref_name too long", - ref_key->type == BTRFS_ROOT_REF_KEY ? - "ROOT_REF" : "ROOT_BACKREF", ref_key->objectid, - ref_key->offset); - } - read_extent_buffer(node, ref_name, (unsigned long)(ref + 1), len); - - /* Find relative root_ref */ - key.objectid = ref_key->offset; - key.type = BTRFS_ROOT_BACKREF_KEY + BTRFS_ROOT_REF_KEY - ref_key->type; - key.offset = ref_key->objectid; - - btrfs_init_path(&path); - ret = btrfs_search_slot(NULL, root, &key, &path, 0, 0); - if (ret) { - err |= ROOT_REF_MISSING; - error("%s[%llu %llu] couldn't find relative ref", - ref_key->type == BTRFS_ROOT_REF_KEY ? - "ROOT_REF" : "ROOT_BACKREF", - ref_key->objectid, ref_key->offset); - goto out; - } - - backref = btrfs_item_ptr(path.nodes[0], path.slots[0], - struct btrfs_root_ref); - backref_dirid = btrfs_root_ref_dirid(path.nodes[0], backref); - backref_seq = btrfs_root_ref_sequence(path.nodes[0], backref); - backref_namelen = btrfs_root_ref_name_len(path.nodes[0], backref); - - if (backref_namelen <= BTRFS_NAME_LEN) { - len = backref_namelen; - } else { - len = BTRFS_NAME_LEN; - warning("%s[%llu %llu] ref_name too long", - key.type == BTRFS_ROOT_REF_KEY ? - "ROOT_REF" : "ROOT_BACKREF", - key.objectid, key.offset); - } - read_extent_buffer(path.nodes[0], backref_name, - (unsigned long)(backref + 1), len); - - if (ref_dirid != backref_dirid || ref_seq != backref_seq || - ref_namelen != backref_namelen || - strncmp(ref_name, backref_name, len)) { - err |= ROOT_REF_MISMATCH; - error("%s[%llu %llu] mismatch relative ref", - ref_key->type == BTRFS_ROOT_REF_KEY ? - "ROOT_REF" : "ROOT_BACKREF", - ref_key->objectid, ref_key->offset); - } -out: - btrfs_release_path(&path); - return err; -} - -/* - * Check all fs/file tree in low_memory mode. - * - * 1. for fs tree root item, call check_fs_root_v2() - * 2. for fs tree root ref/backref, call check_root_ref() - * - * Return 0 if no error occurred. - */ -static int check_fs_roots_v2(struct btrfs_fs_info *fs_info) -{ - struct btrfs_root *tree_root = fs_info->tree_root; - struct btrfs_root *cur_root = NULL; - struct btrfs_path path; - struct btrfs_key key; - struct extent_buffer *node; - unsigned int ext_ref; - int slot; - int ret; - int err = 0; - - ext_ref = btrfs_fs_incompat(fs_info, EXTENDED_IREF); - - btrfs_init_path(&path); - key.objectid = BTRFS_FS_TREE_OBJECTID; - key.offset = 0; - key.type = BTRFS_ROOT_ITEM_KEY; - - ret = btrfs_search_slot(NULL, tree_root, &key, &path, 0, 0); - if (ret < 0) { - err = ret; - goto out; - } else if (ret > 0) { - err = -ENOENT; - goto out; - } - - while (1) { - node = path.nodes[0]; - slot = path.slots[0]; - btrfs_item_key_to_cpu(node, &key, slot); - if (key.objectid > BTRFS_LAST_FREE_OBJECTID) - goto out; - if (key.type == BTRFS_ROOT_ITEM_KEY && - fs_root_objectid(key.objectid)) { - if (key.objectid == BTRFS_TREE_RELOC_OBJECTID) { - cur_root = btrfs_read_fs_root_no_cache(fs_info, - &key); - } else { - key.offset = (u64)-1; - cur_root = btrfs_read_fs_root(fs_info, &key); - } - - if (IS_ERR(cur_root)) { - error("Fail to read fs/subvol tree: %lld", - key.objectid); - err = -EIO; - goto next; - } - - ret = check_fs_root_v2(cur_root, ext_ref); - err |= ret; - - if (key.objectid == BTRFS_TREE_RELOC_OBJECTID) - btrfs_free_fs_root(cur_root); - } else if (key.type == BTRFS_ROOT_REF_KEY || - key.type == BTRFS_ROOT_BACKREF_KEY) { - ret = check_root_ref(tree_root, &key, node, slot); - err |= ret; - } -next: - ret = btrfs_next_item(tree_root, &path); - if (ret > 0) - goto out; - if (ret < 0) { - err = ret; - goto out; - } - } - -out: - btrfs_release_path(&path); - return err; -} static int do_check_fs_roots(struct btrfs_fs_info *fs_info, struct cache_tree *root_cache) @@ -11004,1807 +8250,6 @@ loop: goto again; } -static int check_extent_inline_ref(struct extent_buffer *eb, - struct btrfs_key *key, struct btrfs_extent_inline_ref *iref) -{ - int ret; - u8 type = btrfs_extent_inline_ref_type(eb, iref); - - switch (type) { - case BTRFS_TREE_BLOCK_REF_KEY: - case BTRFS_EXTENT_DATA_REF_KEY: - case BTRFS_SHARED_BLOCK_REF_KEY: - case BTRFS_SHARED_DATA_REF_KEY: - ret = 0; - break; - default: - error("extent[%llu %u %llu] has unknown ref type: %d", - key->objectid, key->type, key->offset, type); - ret = UNKNOWN_TYPE; - break; - } - - return ret; -} - -/* - * Check backrefs of a tree block given by @bytenr or @eb. - * - * @root: the root containing the @bytenr or @eb - * @eb: tree block extent buffer, can be NULL - * @bytenr: bytenr of the tree block to search - * @level: tree level of the tree block - * @owner: owner of the tree block - * - * Return >0 for any error found and output error message - * Return 0 for no error found - */ -static int check_tree_block_ref(struct btrfs_root *root, - struct extent_buffer *eb, u64 bytenr, - int level, u64 owner, struct node_refs *nrefs) -{ - struct btrfs_key key; - struct btrfs_root *extent_root = root->fs_info->extent_root; - struct btrfs_path path; - struct btrfs_extent_item *ei; - struct btrfs_extent_inline_ref *iref; - struct extent_buffer *leaf; - unsigned long end; - unsigned long ptr; - int slot; - int skinny_level; - int root_level = btrfs_header_level(root->node); - int type; - u32 nodesize = root->fs_info->nodesize; - u32 item_size; - u64 offset; - int found_ref = 0; - int err = 0; - int ret; - int strict = 1; - int parent = 0; - - btrfs_init_path(&path); - key.objectid = bytenr; - if (btrfs_fs_incompat(root->fs_info, SKINNY_METADATA)) - key.type = BTRFS_METADATA_ITEM_KEY; - else - key.type = BTRFS_EXTENT_ITEM_KEY; - key.offset = (u64)-1; - - /* Search for the backref in extent tree */ - ret = btrfs_search_slot(NULL, extent_root, &key, &path, 0, 0); - if (ret < 0) { - err |= BACKREF_MISSING; - goto out; - } - ret = btrfs_previous_extent_item(extent_root, &path, bytenr); - if (ret) { - err |= BACKREF_MISSING; - goto out; - } - - leaf = path.nodes[0]; - slot = path.slots[0]; - btrfs_item_key_to_cpu(leaf, &key, slot); - - ei = btrfs_item_ptr(leaf, slot, struct btrfs_extent_item); - - if (key.type == BTRFS_METADATA_ITEM_KEY) { - skinny_level = (int)key.offset; - iref = (struct btrfs_extent_inline_ref *)(ei + 1); - } else { - struct btrfs_tree_block_info *info; - - info = (struct btrfs_tree_block_info *)(ei + 1); - skinny_level = btrfs_tree_block_level(leaf, info); - iref = (struct btrfs_extent_inline_ref *)(info + 1); - } - - - if (eb) { - u64 header_gen; - u64 extent_gen; - - /* - * Due to the feature of shared tree blocks, if the upper node - * is a fs root or shared node, the extent of checked node may - * not be updated until the next CoW. - */ - if (nrefs) - strict = should_check_extent_strictly(root, nrefs, - level); - if (!(btrfs_extent_flags(leaf, ei) & - BTRFS_EXTENT_FLAG_TREE_BLOCK)) { - error( - "extent[%llu %u] backref type mismatch, missing bit: %llx", - key.objectid, nodesize, - BTRFS_EXTENT_FLAG_TREE_BLOCK); - err = BACKREF_MISMATCH; - } - header_gen = btrfs_header_generation(eb); - extent_gen = btrfs_extent_generation(leaf, ei); - if (header_gen != extent_gen) { - error( - "extent[%llu %u] backref generation mismatch, wanted: %llu, have: %llu", - key.objectid, nodesize, header_gen, - extent_gen); - err = BACKREF_MISMATCH; - } - if (level != skinny_level) { - error( - "extent[%llu %u] level mismatch, wanted: %u, have: %u", - key.objectid, nodesize, level, skinny_level); - err = BACKREF_MISMATCH; - } - if (!is_fstree(owner) && btrfs_extent_refs(leaf, ei) != 1) { - error( - "extent[%llu %u] is referred by other roots than %llu", - key.objectid, nodesize, root->objectid); - err = BACKREF_MISMATCH; - } - } - - /* - * Iterate the extent/metadata item to find the exact backref - */ - item_size = btrfs_item_size_nr(leaf, slot); - ptr = (unsigned long)iref; - end = (unsigned long)ei + item_size; - - while (ptr < end) { - iref = (struct btrfs_extent_inline_ref *)ptr; - type = btrfs_extent_inline_ref_type(leaf, iref); - offset = btrfs_extent_inline_ref_offset(leaf, iref); - - ret = check_extent_inline_ref(leaf, &key, iref); - if (ret) { - err |= ret; - break; - } - if (type == BTRFS_TREE_BLOCK_REF_KEY) { - if (offset == root->objectid) - found_ref = 1; - if (!strict && owner == offset) - found_ref = 1; - } else if (type == BTRFS_SHARED_BLOCK_REF_KEY) { - /* - * Backref of tree reloc root points to itself, no need - * to check backref any more. - * - * This may be an error of loop backref, but extent tree - * checker should have already handled it. - * Here we only need to avoid infinite iteration. - */ - if (offset == bytenr) { - found_ref = 1; - } else { - /* - * Check if the backref points to valid - * referencer - */ - found_ref = !check_tree_block_ref( root, NULL, - offset, level + 1, owner, - NULL); - } - } - - if (found_ref) - break; - ptr += btrfs_extent_inline_ref_size(type); - } - - /* - * Inlined extent item doesn't have what we need, check - * TREE_BLOCK_REF_KEY - */ - if (!found_ref) { - btrfs_release_path(&path); - key.objectid = bytenr; - key.type = BTRFS_TREE_BLOCK_REF_KEY; - key.offset = root->objectid; - - ret = btrfs_search_slot(NULL, extent_root, &key, &path, 0, 0); - if (!ret) - found_ref = 1; - } - /* - * Finally check SHARED BLOCK REF, any found will be good - * Here we're not doing comprehensive extent backref checking, - * only need to ensure there is some extent referring to this - * tree block. - */ - if (!found_ref) { - btrfs_release_path(&path); - key.objectid = bytenr; - key.type = BTRFS_SHARED_BLOCK_REF_KEY; - key.offset = (u64)-1; - - ret = btrfs_search_slot(NULL, extent_root, &key, &path, 0, 0); - if (ret < 0) { - err |= BACKREF_MISSING; - goto out; - } - ret = btrfs_previous_extent_item(extent_root, &path, bytenr); - if (ret) { - err |= BACKREF_MISSING; - goto out; - } - found_ref = 1; - } - if (!found_ref) - err |= BACKREF_MISSING; -out: - btrfs_release_path(&path); - if (nrefs && strict && - level < root_level && nrefs->full_backref[level + 1]) - parent = nrefs->bytenr[level + 1]; - if (eb && (err & BACKREF_MISSING)) - error( - "extent[%llu %u] backref lost (owner: %llu, level: %u) %s %llu", - bytenr, nodesize, owner, level, - parent ? "parent" : "root", - parent ? parent : root->objectid); - return err; -} - -/* - * If @err contains BACKREF_MISSING then add extent of the - * file_extent_data_item. - * - * Returns error bits after reapir. - */ -static int repair_extent_data_item(struct btrfs_trans_handle *trans, - struct btrfs_root *root, - struct btrfs_path *pathp, - struct node_refs *nrefs, - int err) -{ - struct btrfs_file_extent_item *fi; - struct btrfs_key fi_key; - struct btrfs_key key; - struct btrfs_extent_item *ei; - struct btrfs_path path; - struct btrfs_root *extent_root = root->fs_info->extent_root; - struct extent_buffer *eb; - u64 size; - u64 disk_bytenr; - u64 num_bytes; - u64 parent; - u64 offset; - u64 extent_offset; - u64 file_offset; - int generation; - int slot; - int ret = 0; - - eb = pathp->nodes[0]; - slot = pathp->slots[0]; - btrfs_item_key_to_cpu(eb, &fi_key, slot); - fi = btrfs_item_ptr(eb, slot, struct btrfs_file_extent_item); - - if (btrfs_file_extent_type(eb, fi) == BTRFS_FILE_EXTENT_INLINE || - btrfs_file_extent_disk_bytenr(eb, fi) == 0) - return err; - - file_offset = fi_key.offset; - generation = btrfs_file_extent_generation(eb, fi); - disk_bytenr = btrfs_file_extent_disk_bytenr(eb, fi); - num_bytes = btrfs_file_extent_disk_num_bytes(eb, fi); - extent_offset = btrfs_file_extent_offset(eb, fi); - offset = file_offset - extent_offset; - - /* now repair only adds backref */ - if ((err & BACKREF_MISSING) == 0) - return err; - - /* search extent item */ - key.objectid = disk_bytenr; - key.type = BTRFS_EXTENT_ITEM_KEY; - key.offset = num_bytes; - - btrfs_init_path(&path); - ret = btrfs_search_slot(NULL, extent_root, &key, &path, 0, 0); - if (ret < 0) { - ret = -EIO; - goto out; - } - - /* insert an extent item */ - if (ret > 0) { - key.objectid = disk_bytenr; - key.type = BTRFS_EXTENT_ITEM_KEY; - key.offset = num_bytes; - size = sizeof(*ei); - - btrfs_release_path(&path); - ret = btrfs_insert_empty_item(trans, extent_root, &path, &key, - size); - if (ret) - goto out; - eb = path.nodes[0]; - ei = btrfs_item_ptr(eb, path.slots[0], struct btrfs_extent_item); - - btrfs_set_extent_refs(eb, ei, 0); - btrfs_set_extent_generation(eb, ei, generation); - btrfs_set_extent_flags(eb, ei, BTRFS_EXTENT_FLAG_DATA); - - btrfs_mark_buffer_dirty(eb); - ret = btrfs_update_block_group(extent_root, disk_bytenr, - num_bytes, 1, 0); - btrfs_release_path(&path); - } - - if (nrefs->full_backref[0]) - parent = btrfs_header_bytenr(eb); - else - parent = 0; - - ret = btrfs_inc_extent_ref(trans, root, disk_bytenr, num_bytes, parent, - root->objectid, - parent ? BTRFS_FIRST_FREE_OBJECTID : fi_key.objectid, - offset); - if (ret) { - error( - "failed to increase extent data backref[%llu %llu] root %llu", - disk_bytenr, num_bytes, root->objectid); - goto out; - } else { - printf("Add one extent data backref [%llu %llu]\n", - disk_bytenr, num_bytes); - } - - err &= ~BACKREF_MISSING; -out: - if (ret) - error("can't repair root %llu extent data item[%llu %llu]", - root->objectid, disk_bytenr, num_bytes); - return err; -} - -/* - * Check EXTENT_DATA item, mainly for its dbackref in extent tree - * - * Return >0 any error found and output error message - * Return 0 for no error found - */ -static int check_extent_data_item(struct btrfs_root *root, - struct btrfs_path *pathp, - struct node_refs *nrefs, int account_bytes) -{ - struct btrfs_file_extent_item *fi; - struct extent_buffer *eb = pathp->nodes[0]; - struct btrfs_path path; - struct btrfs_root *extent_root = root->fs_info->extent_root; - struct btrfs_key fi_key; - struct btrfs_key dbref_key; - struct extent_buffer *leaf; - struct btrfs_extent_item *ei; - struct btrfs_extent_inline_ref *iref; - struct btrfs_extent_data_ref *dref; - u64 owner; - u64 disk_bytenr; - u64 disk_num_bytes; - u64 extent_num_bytes; - u64 extent_flags; - u64 offset; - u32 item_size; - unsigned long end; - unsigned long ptr; - int type; - int found_dbackref = 0; - int slot = pathp->slots[0]; - int err = 0; - int ret; - int strict; - - btrfs_item_key_to_cpu(eb, &fi_key, slot); - fi = btrfs_item_ptr(eb, slot, struct btrfs_file_extent_item); - - /* Nothing to check for hole and inline data extents */ - if (btrfs_file_extent_type(eb, fi) == BTRFS_FILE_EXTENT_INLINE || - btrfs_file_extent_disk_bytenr(eb, fi) == 0) - return 0; - - disk_bytenr = btrfs_file_extent_disk_bytenr(eb, fi); - disk_num_bytes = btrfs_file_extent_disk_num_bytes(eb, fi); - extent_num_bytes = btrfs_file_extent_num_bytes(eb, fi); - offset = btrfs_file_extent_offset(eb, fi); - - /* Check unaligned disk_num_bytes and num_bytes */ - if (!IS_ALIGNED(disk_num_bytes, root->fs_info->sectorsize)) { - error( -"file extent [%llu, %llu] has unaligned disk num bytes: %llu, should be aligned to %u", - fi_key.objectid, fi_key.offset, disk_num_bytes, - root->fs_info->sectorsize); - err |= BYTES_UNALIGNED; - } else if (account_bytes) { - data_bytes_allocated += disk_num_bytes; - } - if (!IS_ALIGNED(extent_num_bytes, root->fs_info->sectorsize)) { - error( -"file extent [%llu, %llu] has unaligned num bytes: %llu, should be aligned to %u", - fi_key.objectid, fi_key.offset, extent_num_bytes, - root->fs_info->sectorsize); - err |= BYTES_UNALIGNED; - } else if (account_bytes) { - data_bytes_referenced += extent_num_bytes; - } - owner = btrfs_header_owner(eb); - - /* Check the extent item of the file extent in extent tree */ - btrfs_init_path(&path); - dbref_key.objectid = btrfs_file_extent_disk_bytenr(eb, fi); - dbref_key.type = BTRFS_EXTENT_ITEM_KEY; - dbref_key.offset = btrfs_file_extent_disk_num_bytes(eb, fi); - - ret = btrfs_search_slot(NULL, extent_root, &dbref_key, &path, 0, 0); - if (ret) - goto out; - - leaf = path.nodes[0]; - slot = path.slots[0]; - ei = btrfs_item_ptr(leaf, slot, struct btrfs_extent_item); - - extent_flags = btrfs_extent_flags(leaf, ei); - - if (!(extent_flags & BTRFS_EXTENT_FLAG_DATA)) { - error( - "extent[%llu %llu] backref type mismatch, wanted bit: %llx", - disk_bytenr, disk_num_bytes, - BTRFS_EXTENT_FLAG_DATA); - err |= BACKREF_MISMATCH; - } - - /* Check data backref inside that extent item */ - item_size = btrfs_item_size_nr(leaf, path.slots[0]); - iref = (struct btrfs_extent_inline_ref *)(ei + 1); - ptr = (unsigned long)iref; - end = (unsigned long)ei + item_size; - strict = should_check_extent_strictly(root, nrefs, -1); - - while (ptr < end) { - u64 ref_root; - u64 ref_objectid; - u64 ref_offset; - bool match = false; - - iref = (struct btrfs_extent_inline_ref *)ptr; - type = btrfs_extent_inline_ref_type(leaf, iref); - dref = (struct btrfs_extent_data_ref *)(&iref->offset); - - ret = check_extent_inline_ref(leaf, &dbref_key, iref); - if (ret) { - err |= ret; - break; - } - if (type == BTRFS_EXTENT_DATA_REF_KEY) { - ref_root = btrfs_extent_data_ref_root(leaf, dref); - ref_objectid = btrfs_extent_data_ref_objectid(leaf, dref); - ref_offset = btrfs_extent_data_ref_offset(leaf, dref); - - if (ref_objectid == fi_key.objectid && - ref_offset == fi_key.offset - offset) - match = true; - if (ref_root == root->objectid && match) - found_dbackref = 1; - else if (!strict && owner == ref_root && match) - found_dbackref = 1; - } else if (type == BTRFS_SHARED_DATA_REF_KEY) { - found_dbackref = !check_tree_block_ref(root, NULL, - btrfs_extent_inline_ref_offset(leaf, iref), - 0, owner, NULL); - } - - if (found_dbackref) - break; - ptr += btrfs_extent_inline_ref_size(type); - } - - if (!found_dbackref) { - btrfs_release_path(&path); - - /* Didn't find inlined data backref, try EXTENT_DATA_REF_KEY */ - dbref_key.objectid = btrfs_file_extent_disk_bytenr(eb, fi); - dbref_key.type = BTRFS_EXTENT_DATA_REF_KEY; - dbref_key.offset = hash_extent_data_ref(root->objectid, - fi_key.objectid, fi_key.offset - offset); - - ret = btrfs_search_slot(NULL, root->fs_info->extent_root, - &dbref_key, &path, 0, 0); - if (!ret) { - found_dbackref = 1; - goto out; - } - - btrfs_release_path(&path); - - /* - * Neither inlined nor EXTENT_DATA_REF found, try - * SHARED_DATA_REF as last chance. - */ - dbref_key.objectid = disk_bytenr; - dbref_key.type = BTRFS_SHARED_DATA_REF_KEY; - dbref_key.offset = eb->start; - - ret = btrfs_search_slot(NULL, root->fs_info->extent_root, - &dbref_key, &path, 0, 0); - if (!ret) { - found_dbackref = 1; - goto out; - } - } - -out: - if (!found_dbackref) - err |= BACKREF_MISSING; - btrfs_release_path(&path); - if (err & BACKREF_MISSING) { - error("data extent[%llu %llu] backref lost", - disk_bytenr, disk_num_bytes); - } - return err; -} - -/* - * Get real tree block level for the case like shared block - * Return >= 0 as tree level - * Return <0 for error - */ -static int query_tree_block_level(struct btrfs_fs_info *fs_info, u64 bytenr) -{ - struct extent_buffer *eb; - struct btrfs_path path; - struct btrfs_key key; - struct btrfs_extent_item *ei; - u64 flags; - u64 transid; - u8 backref_level; - u8 header_level; - int ret; - - /* Search extent tree for extent generation and level */ - key.objectid = bytenr; - key.type = BTRFS_METADATA_ITEM_KEY; - key.offset = (u64)-1; - - btrfs_init_path(&path); - ret = btrfs_search_slot(NULL, fs_info->extent_root, &key, &path, 0, 0); - if (ret < 0) - goto release_out; - ret = btrfs_previous_extent_item(fs_info->extent_root, &path, bytenr); - if (ret < 0) - goto release_out; - if (ret > 0) { - ret = -ENOENT; - goto release_out; - } - - btrfs_item_key_to_cpu(path.nodes[0], &key, path.slots[0]); - ei = btrfs_item_ptr(path.nodes[0], path.slots[0], - struct btrfs_extent_item); - flags = btrfs_extent_flags(path.nodes[0], ei); - if (!(flags & BTRFS_EXTENT_FLAG_TREE_BLOCK)) { - ret = -ENOENT; - goto release_out; - } - - /* Get transid for later read_tree_block() check */ - transid = btrfs_extent_generation(path.nodes[0], ei); - - /* Get backref level as one source */ - if (key.type == BTRFS_METADATA_ITEM_KEY) { - backref_level = key.offset; - } else { - struct btrfs_tree_block_info *info; - - info = (struct btrfs_tree_block_info *)(ei + 1); - backref_level = btrfs_tree_block_level(path.nodes[0], info); - } - btrfs_release_path(&path); - - /* Get level from tree block as an alternative source */ - eb = read_tree_block(fs_info, bytenr, transid); - if (!extent_buffer_uptodate(eb)) { - free_extent_buffer(eb); - return -EIO; - } - header_level = btrfs_header_level(eb); - free_extent_buffer(eb); - - if (header_level != backref_level) - return -EIO; - return header_level; - -release_out: - btrfs_release_path(&path); - return ret; -} - -/* - * Check if a tree block backref is valid (points to a valid tree block) - * if level == -1, level will be resolved - * Return >0 for any error found and print error message - */ -static int check_tree_block_backref(struct btrfs_fs_info *fs_info, u64 root_id, - u64 bytenr, int level) -{ - struct btrfs_root *root; - struct btrfs_key key; - struct btrfs_path path; - struct extent_buffer *eb; - struct extent_buffer *node; - u32 nodesize = btrfs_super_nodesize(fs_info->super_copy); - int err = 0; - int ret; - - /* Query level for level == -1 special case */ - if (level == -1) - level = query_tree_block_level(fs_info, bytenr); - if (level < 0) { - err |= REFERENCER_MISSING; - goto out; - } - - key.objectid = root_id; - key.type = BTRFS_ROOT_ITEM_KEY; - key.offset = (u64)-1; - - root = btrfs_read_fs_root(fs_info, &key); - if (IS_ERR(root)) { - err |= REFERENCER_MISSING; - goto out; - } - - /* Read out the tree block to get item/node key */ - eb = read_tree_block(fs_info, bytenr, 0); - if (!extent_buffer_uptodate(eb)) { - err |= REFERENCER_MISSING; - free_extent_buffer(eb); - goto out; - } - - /* Empty tree, no need to check key */ - if (!btrfs_header_nritems(eb) && !level) { - free_extent_buffer(eb); - goto out; - } - - if (level) - btrfs_node_key_to_cpu(eb, &key, 0); - else - btrfs_item_key_to_cpu(eb, &key, 0); - - free_extent_buffer(eb); - - btrfs_init_path(&path); - path.lowest_level = level; - /* Search with the first key, to ensure we can reach it */ - ret = btrfs_search_slot(NULL, root, &key, &path, 0, 0); - if (ret < 0) { - err |= REFERENCER_MISSING; - goto release_out; - } - - node = path.nodes[level]; - if (btrfs_header_bytenr(node) != bytenr) { - error( - "extent [%llu %d] referencer bytenr mismatch, wanted: %llu, have: %llu", - bytenr, nodesize, bytenr, - btrfs_header_bytenr(node)); - err |= REFERENCER_MISMATCH; - } - if (btrfs_header_level(node) != level) { - error( - "extent [%llu %d] referencer level mismatch, wanted: %d, have: %d", - bytenr, nodesize, level, - btrfs_header_level(node)); - err |= REFERENCER_MISMATCH; - } - -release_out: - btrfs_release_path(&path); -out: - if (err & REFERENCER_MISSING) { - if (level < 0) - error("extent [%llu %d] lost referencer (owner: %llu)", - bytenr, nodesize, root_id); - else - error( - "extent [%llu %d] lost referencer (owner: %llu, level: %u)", - bytenr, nodesize, root_id, level); - } - - return err; -} - -/* - * Check if tree block @eb is tree reloc root. - * Return 0 if it's not or any problem happens - * Return 1 if it's a tree reloc root - */ -static int is_tree_reloc_root(struct btrfs_fs_info *fs_info, - struct extent_buffer *eb) -{ - struct btrfs_root *tree_reloc_root; - struct btrfs_key key; - u64 bytenr = btrfs_header_bytenr(eb); - u64 owner = btrfs_header_owner(eb); - int ret = 0; - - key.objectid = BTRFS_TREE_RELOC_OBJECTID; - key.offset = owner; - key.type = BTRFS_ROOT_ITEM_KEY; - - tree_reloc_root = btrfs_read_fs_root_no_cache(fs_info, &key); - if (IS_ERR(tree_reloc_root)) - return 0; - - if (bytenr == btrfs_header_bytenr(tree_reloc_root->node)) - ret = 1; - btrfs_free_fs_root(tree_reloc_root); - return ret; -} - -/* - * Check referencer for shared block backref - * If level == -1, this function will resolve the level. - */ -static int check_shared_block_backref(struct btrfs_fs_info *fs_info, - u64 parent, u64 bytenr, int level) -{ - struct extent_buffer *eb; - u32 nr; - int found_parent = 0; - int i; - - eb = read_tree_block(fs_info, parent, 0); - if (!extent_buffer_uptodate(eb)) - goto out; - - if (level == -1) - level = query_tree_block_level(fs_info, bytenr); - if (level < 0) - goto out; - - /* It's possible it's a tree reloc root */ - if (parent == bytenr) { - if (is_tree_reloc_root(fs_info, eb)) - found_parent = 1; - goto out; - } - - if (level + 1 != btrfs_header_level(eb)) - goto out; - - nr = btrfs_header_nritems(eb); - for (i = 0; i < nr; i++) { - if (bytenr == btrfs_node_blockptr(eb, i)) { - found_parent = 1; - break; - } - } -out: - free_extent_buffer(eb); - if (!found_parent) { - error( - "shared extent[%llu %u] lost its parent (parent: %llu, level: %u)", - bytenr, fs_info->nodesize, parent, level); - return REFERENCER_MISSING; - } - return 0; -} - -/* - * Check referencer for normal (inlined) data ref - * If len == 0, it will be resolved by searching in extent tree - */ -static int check_extent_data_backref(struct btrfs_fs_info *fs_info, - u64 root_id, u64 objectid, u64 offset, - u64 bytenr, u64 len, u32 count) -{ - struct btrfs_root *root; - struct btrfs_root *extent_root = fs_info->extent_root; - struct btrfs_key key; - struct btrfs_path path; - struct extent_buffer *leaf; - struct btrfs_file_extent_item *fi; - u32 found_count = 0; - int slot; - int ret = 0; - - if (!len) { - key.objectid = bytenr; - key.type = BTRFS_EXTENT_ITEM_KEY; - key.offset = (u64)-1; - - btrfs_init_path(&path); - ret = btrfs_search_slot(NULL, extent_root, &key, &path, 0, 0); - if (ret < 0) - goto out; - ret = btrfs_previous_extent_item(extent_root, &path, bytenr); - if (ret) - goto out; - btrfs_item_key_to_cpu(path.nodes[0], &key, path.slots[0]); - if (key.objectid != bytenr || - key.type != BTRFS_EXTENT_ITEM_KEY) - goto out; - len = key.offset; - btrfs_release_path(&path); - } - key.objectid = root_id; - key.type = BTRFS_ROOT_ITEM_KEY; - key.offset = (u64)-1; - btrfs_init_path(&path); - - root = btrfs_read_fs_root(fs_info, &key); - if (IS_ERR(root)) - goto out; - - key.objectid = objectid; - key.type = BTRFS_EXTENT_DATA_KEY; - /* - * It can be nasty as data backref offset is - * file offset - file extent offset, which is smaller or - * equal to original backref offset. The only special case is - * overflow. So we need to special check and do further search. - */ - key.offset = offset & (1ULL << 63) ? 0 : offset; - - ret = btrfs_search_slot(NULL, root, &key, &path, 0, 0); - if (ret < 0) - goto out; - - /* - * Search afterwards to get correct one - * NOTE: As we must do a comprehensive check on the data backref to - * make sure the dref count also matches, we must iterate all file - * extents for that inode. - */ - while (1) { - leaf = path.nodes[0]; - slot = path.slots[0]; - - if (slot >= btrfs_header_nritems(leaf) || - btrfs_header_owner(leaf) != root_id) - goto next; - btrfs_item_key_to_cpu(leaf, &key, slot); - if (key.objectid != objectid || key.type != BTRFS_EXTENT_DATA_KEY) - break; - fi = btrfs_item_ptr(leaf, slot, struct btrfs_file_extent_item); - /* - * Except normal disk bytenr and disk num bytes, we still - * need to do extra check on dbackref offset as - * dbackref offset = file_offset - file_extent_offset - * - * Also, we must check the leaf owner. - * In case of shared tree blocks (snapshots) we can inherit - * leaves from source snapshot. - * In that case, reference from source snapshot should not - * count. - */ - if (btrfs_file_extent_disk_bytenr(leaf, fi) == bytenr && - btrfs_file_extent_disk_num_bytes(leaf, fi) == len && - (u64)(key.offset - btrfs_file_extent_offset(leaf, fi)) == - offset && btrfs_header_owner(leaf) == root_id) - found_count++; - -next: - ret = btrfs_next_item(root, &path); - if (ret) - break; - } -out: - btrfs_release_path(&path); - if (found_count != count) { - error( -"extent[%llu, %llu] referencer count mismatch (root: %llu, owner: %llu, offset: %llu) wanted: %u, have: %u", - bytenr, len, root_id, objectid, offset, count, found_count); - return REFERENCER_MISSING; - } - return 0; -} - -/* - * Check if the referencer of a shared data backref exists - */ -static int check_shared_data_backref(struct btrfs_fs_info *fs_info, - u64 parent, u64 bytenr) -{ - struct extent_buffer *eb; - struct btrfs_key key; - struct btrfs_file_extent_item *fi; - u32 nr; - int found_parent = 0; - int i; - - eb = read_tree_block(fs_info, parent, 0); - if (!extent_buffer_uptodate(eb)) - goto out; - - nr = btrfs_header_nritems(eb); - for (i = 0; i < nr; i++) { - btrfs_item_key_to_cpu(eb, &key, i); - if (key.type != BTRFS_EXTENT_DATA_KEY) - continue; - - fi = btrfs_item_ptr(eb, i, struct btrfs_file_extent_item); - if (btrfs_file_extent_type(eb, fi) == BTRFS_FILE_EXTENT_INLINE) - continue; - - if (btrfs_file_extent_disk_bytenr(eb, fi) == bytenr) { - found_parent = 1; - break; - } - } - -out: - free_extent_buffer(eb); - if (!found_parent) { - error("shared extent %llu referencer lost (parent: %llu)", - bytenr, parent); - return REFERENCER_MISSING; - } - return 0; -} - -/* - * Only delete backref if REFERENCER_MISSING now - * - * Returns <0 the extent was deleted - * Returns >0 the backref was deleted but extent still exists, returned value - * means error after repair - * Returns 0 nothing happened - */ -static int repair_extent_item(struct btrfs_trans_handle *trans, - struct btrfs_root *root, struct btrfs_path *path, - u64 bytenr, u64 num_bytes, u64 parent, u64 root_objectid, - u64 owner, u64 offset, int err) -{ - struct btrfs_key old_key; - int freed = 0; - int ret; - - btrfs_item_key_to_cpu(path->nodes[0], &old_key, path->slots[0]); - - if (err & (REFERENCER_MISSING | REFERENCER_MISMATCH)) { - /* delete the backref */ - ret = btrfs_free_extent(trans, root->fs_info->fs_root, bytenr, - num_bytes, parent, root_objectid, owner, offset); - if (!ret) { - freed = 1; - err &= ~REFERENCER_MISSING; - printf("Delete backref in extent [%llu %llu]\n", - bytenr, num_bytes); - } else { - error("fail to delete backref in extent [%llu %llu]", - bytenr, num_bytes); - } - } - - /* btrfs_free_extent may delete the extent */ - btrfs_release_path(path); - ret = btrfs_search_slot(NULL, root, &old_key, path, 0, 0); - - if (ret) - ret = -ENOENT; - else if (freed) - ret = err; - return ret; -} - -/* - * This function will check a given extent item, including its backref and - * itself (like crossing stripe boundary and type) - * - * Since we don't use extent_record anymore, introduce new error bit - */ -static int check_extent_item(struct btrfs_trans_handle *trans, - struct btrfs_fs_info *fs_info, - struct btrfs_path *path) -{ - struct btrfs_extent_item *ei; - struct btrfs_extent_inline_ref *iref; - struct btrfs_extent_data_ref *dref; - struct extent_buffer *eb = path->nodes[0]; - unsigned long end; - unsigned long ptr; - int slot = path->slots[0]; - int type; - u32 nodesize = btrfs_super_nodesize(fs_info->super_copy); - u32 item_size = btrfs_item_size_nr(eb, slot); - u64 flags; - u64 offset; - u64 parent; - u64 num_bytes; - u64 root_objectid; - u64 owner; - u64 owner_offset; - int metadata = 0; - int level; - struct btrfs_key key; - int ret; - int err = 0; - - btrfs_item_key_to_cpu(eb, &key, slot); - if (key.type == BTRFS_EXTENT_ITEM_KEY) { - bytes_used += key.offset; - num_bytes = key.offset; - } else { - bytes_used += nodesize; - num_bytes = nodesize; - } - - if (item_size < sizeof(*ei)) { - /* - * COMPAT_EXTENT_TREE_V0 case, but it's already a super - * old thing when on disk format is still un-determined. - * No need to care about it anymore - */ - error("unsupported COMPAT_EXTENT_TREE_V0 detected"); - return -ENOTTY; - } - - ei = btrfs_item_ptr(eb, slot, struct btrfs_extent_item); - flags = btrfs_extent_flags(eb, ei); - - if (flags & BTRFS_EXTENT_FLAG_TREE_BLOCK) - metadata = 1; - if (metadata && check_crossing_stripes(global_info, key.objectid, - eb->len)) { - error("bad metadata [%llu, %llu) crossing stripe boundary", - key.objectid, key.objectid + nodesize); - err |= CROSSING_STRIPE_BOUNDARY; - } - - ptr = (unsigned long)(ei + 1); - - if (metadata && key.type == BTRFS_EXTENT_ITEM_KEY) { - /* Old EXTENT_ITEM metadata */ - struct btrfs_tree_block_info *info; - - info = (struct btrfs_tree_block_info *)ptr; - level = btrfs_tree_block_level(eb, info); - ptr += sizeof(struct btrfs_tree_block_info); - } else { - /* New METADATA_ITEM */ - level = key.offset; - } - end = (unsigned long)ei + item_size; - -next: - /* Reached extent item end normally */ - if (ptr == end) - goto out; - - /* Beyond extent item end, wrong item size */ - if (ptr > end) { - err |= ITEM_SIZE_MISMATCH; - error("extent item at bytenr %llu slot %d has wrong size", - eb->start, slot); - goto out; - } - - parent = 0; - root_objectid = 0; - owner = 0; - owner_offset = 0; - /* Now check every backref in this extent item */ - iref = (struct btrfs_extent_inline_ref *)ptr; - type = btrfs_extent_inline_ref_type(eb, iref); - offset = btrfs_extent_inline_ref_offset(eb, iref); - switch (type) { - case BTRFS_TREE_BLOCK_REF_KEY: - root_objectid = offset; - owner = level; - ret = check_tree_block_backref(fs_info, offset, key.objectid, - level); - err |= ret; - break; - case BTRFS_SHARED_BLOCK_REF_KEY: - parent = offset; - ret = check_shared_block_backref(fs_info, offset, key.objectid, - level); - err |= ret; - break; - case BTRFS_EXTENT_DATA_REF_KEY: - dref = (struct btrfs_extent_data_ref *)(&iref->offset); - root_objectid = btrfs_extent_data_ref_root(eb, dref); - owner = btrfs_extent_data_ref_objectid(eb, dref); - owner_offset = btrfs_extent_data_ref_offset(eb, dref); - ret = check_extent_data_backref(fs_info, root_objectid, owner, - owner_offset, key.objectid, key.offset, - btrfs_extent_data_ref_count(eb, dref)); - err |= ret; - break; - case BTRFS_SHARED_DATA_REF_KEY: - parent = offset; - ret = check_shared_data_backref(fs_info, offset, key.objectid); - err |= ret; - break; - default: - error("extent[%llu %d %llu] has unknown ref type: %d", - key.objectid, key.type, key.offset, type); - ret = UNKNOWN_TYPE; - err |= ret; - goto out; - } - - if (err && repair) { - ret = repair_extent_item(trans, fs_info->extent_root, path, - key.objectid, num_bytes, parent, root_objectid, - owner, owner_offset, ret); - if (ret < 0) - goto out; - if (ret) { - goto next; - err = ret; - } - } - - ptr += btrfs_extent_inline_ref_size(type); - goto next; - -out: - return err; -} - -/* - * Check if a dev extent item is referred correctly by its chunk - */ -static int check_dev_extent_item(struct btrfs_fs_info *fs_info, - struct extent_buffer *eb, int slot) -{ - struct btrfs_root *chunk_root = fs_info->chunk_root; - struct btrfs_dev_extent *ptr; - struct btrfs_path path; - struct btrfs_key chunk_key; - struct btrfs_key devext_key; - struct btrfs_chunk *chunk; - struct extent_buffer *l; - int num_stripes; - u64 length; - int i; - int found_chunk = 0; - int ret; - - btrfs_item_key_to_cpu(eb, &devext_key, slot); - ptr = btrfs_item_ptr(eb, slot, struct btrfs_dev_extent); - length = btrfs_dev_extent_length(eb, ptr); - - chunk_key.objectid = btrfs_dev_extent_chunk_objectid(eb, ptr); - chunk_key.type = BTRFS_CHUNK_ITEM_KEY; - chunk_key.offset = btrfs_dev_extent_chunk_offset(eb, ptr); - - btrfs_init_path(&path); - ret = btrfs_search_slot(NULL, chunk_root, &chunk_key, &path, 0, 0); - if (ret) - goto out; - - l = path.nodes[0]; - chunk = btrfs_item_ptr(l, path.slots[0], struct btrfs_chunk); - ret = btrfs_check_chunk_valid(fs_info, l, chunk, path.slots[0], - chunk_key.offset); - if (ret < 0) - goto out; - - if (btrfs_stripe_length(fs_info, l, chunk) != length) - goto out; - - num_stripes = btrfs_chunk_num_stripes(l, chunk); - for (i = 0; i < num_stripes; i++) { - u64 devid = btrfs_stripe_devid_nr(l, chunk, i); - u64 offset = btrfs_stripe_offset_nr(l, chunk, i); - - if (devid == devext_key.objectid && - offset == devext_key.offset) { - found_chunk = 1; - break; - } - } -out: - btrfs_release_path(&path); - if (!found_chunk) { - error( - "device extent[%llu, %llu, %llu] did not find the related chunk", - devext_key.objectid, devext_key.offset, length); - return REFERENCER_MISSING; - } - return 0; -} - -/* - * Check if the used space is correct with the dev item - */ -static int check_dev_item(struct btrfs_fs_info *fs_info, - struct extent_buffer *eb, int slot) -{ - struct btrfs_root *dev_root = fs_info->dev_root; - struct btrfs_dev_item *dev_item; - struct btrfs_path path; - struct btrfs_key key; - struct btrfs_dev_extent *ptr; - u64 total_bytes; - u64 dev_id; - u64 used; - u64 total = 0; - int ret; - - dev_item = btrfs_item_ptr(eb, slot, struct btrfs_dev_item); - dev_id = btrfs_device_id(eb, dev_item); - used = btrfs_device_bytes_used(eb, dev_item); - total_bytes = btrfs_device_total_bytes(eb, dev_item); - - key.objectid = dev_id; - key.type = BTRFS_DEV_EXTENT_KEY; - key.offset = 0; - - btrfs_init_path(&path); - ret = btrfs_search_slot(NULL, dev_root, &key, &path, 0, 0); - if (ret < 0) { - btrfs_item_key_to_cpu(eb, &key, slot); - error("cannot find any related dev extent for dev[%llu, %u, %llu]", - key.objectid, key.type, key.offset); - btrfs_release_path(&path); - return REFERENCER_MISSING; - } - - /* Iterate dev_extents to calculate the used space of a device */ - while (1) { - if (path.slots[0] >= btrfs_header_nritems(path.nodes[0])) - goto next; - - btrfs_item_key_to_cpu(path.nodes[0], &key, path.slots[0]); - if (key.objectid > dev_id) - break; - if (key.type != BTRFS_DEV_EXTENT_KEY || key.objectid != dev_id) - goto next; - - ptr = btrfs_item_ptr(path.nodes[0], path.slots[0], - struct btrfs_dev_extent); - total += btrfs_dev_extent_length(path.nodes[0], ptr); -next: - ret = btrfs_next_item(dev_root, &path); - if (ret) - break; - } - btrfs_release_path(&path); - - if (used != total) { - btrfs_item_key_to_cpu(eb, &key, slot); - error( -"Dev extent's total-byte %llu is not equal to bytes-used %llu in dev[%llu, %u, %llu]", - total, used, BTRFS_ROOT_TREE_OBJECTID, - BTRFS_DEV_EXTENT_KEY, dev_id); - return ACCOUNTING_MISMATCH; - } - check_dev_size_alignment(dev_id, total_bytes, fs_info->sectorsize); - - return 0; -} - -/* - * Check a block group item with its referener (chunk) and its used space - * with extent/metadata item - */ -static int check_block_group_item(struct btrfs_fs_info *fs_info, - struct extent_buffer *eb, int slot) -{ - struct btrfs_root *extent_root = fs_info->extent_root; - struct btrfs_root *chunk_root = fs_info->chunk_root; - struct btrfs_block_group_item *bi; - struct btrfs_block_group_item bg_item; - struct btrfs_path path; - struct btrfs_key bg_key; - struct btrfs_key chunk_key; - struct btrfs_key extent_key; - struct btrfs_chunk *chunk; - struct extent_buffer *leaf; - struct btrfs_extent_item *ei; - u32 nodesize = btrfs_super_nodesize(fs_info->super_copy); - u64 flags; - u64 bg_flags; - u64 used; - u64 total = 0; - int ret; - int err = 0; - - btrfs_item_key_to_cpu(eb, &bg_key, slot); - bi = btrfs_item_ptr(eb, slot, struct btrfs_block_group_item); - read_extent_buffer(eb, &bg_item, (unsigned long)bi, sizeof(bg_item)); - used = btrfs_block_group_used(&bg_item); - bg_flags = btrfs_block_group_flags(&bg_item); - - chunk_key.objectid = BTRFS_FIRST_CHUNK_TREE_OBJECTID; - chunk_key.type = BTRFS_CHUNK_ITEM_KEY; - chunk_key.offset = bg_key.objectid; - - btrfs_init_path(&path); - /* Search for the referencer chunk */ - ret = btrfs_search_slot(NULL, chunk_root, &chunk_key, &path, 0, 0); - if (ret) { - error( - "block group[%llu %llu] did not find the related chunk item", - bg_key.objectid, bg_key.offset); - err |= REFERENCER_MISSING; - } else { - chunk = btrfs_item_ptr(path.nodes[0], path.slots[0], - struct btrfs_chunk); - if (btrfs_chunk_length(path.nodes[0], chunk) != - bg_key.offset) { - error( - "block group[%llu %llu] related chunk item length does not match", - bg_key.objectid, bg_key.offset); - err |= REFERENCER_MISMATCH; - } - } - btrfs_release_path(&path); - - /* Search from the block group bytenr */ - extent_key.objectid = bg_key.objectid; - extent_key.type = 0; - extent_key.offset = 0; - - btrfs_init_path(&path); - ret = btrfs_search_slot(NULL, extent_root, &extent_key, &path, 0, 0); - if (ret < 0) - goto out; - - /* Iterate extent tree to account used space */ - while (1) { - leaf = path.nodes[0]; - - /* Search slot can point to the last item beyond leaf nritems */ - if (path.slots[0] >= btrfs_header_nritems(leaf)) - goto next; - - btrfs_item_key_to_cpu(leaf, &extent_key, path.slots[0]); - if (extent_key.objectid >= bg_key.objectid + bg_key.offset) - break; - - if (extent_key.type != BTRFS_METADATA_ITEM_KEY && - extent_key.type != BTRFS_EXTENT_ITEM_KEY) - goto next; - if (extent_key.objectid < bg_key.objectid) - goto next; - - if (extent_key.type == BTRFS_METADATA_ITEM_KEY) - total += nodesize; - else - total += extent_key.offset; - - ei = btrfs_item_ptr(leaf, path.slots[0], - struct btrfs_extent_item); - flags = btrfs_extent_flags(leaf, ei); - if (flags & BTRFS_EXTENT_FLAG_DATA) { - if (!(bg_flags & BTRFS_BLOCK_GROUP_DATA)) { - error( - "bad extent[%llu, %llu) type mismatch with chunk", - extent_key.objectid, - extent_key.objectid + extent_key.offset); - err |= CHUNK_TYPE_MISMATCH; - } - } else if (flags & BTRFS_EXTENT_FLAG_TREE_BLOCK) { - if (!(bg_flags & (BTRFS_BLOCK_GROUP_SYSTEM | - BTRFS_BLOCK_GROUP_METADATA))) { - error( - "bad extent[%llu, %llu) type mismatch with chunk", - extent_key.objectid, - extent_key.objectid + nodesize); - err |= CHUNK_TYPE_MISMATCH; - } - } -next: - ret = btrfs_next_item(extent_root, &path); - if (ret) - break; - } - -out: - btrfs_release_path(&path); - - if (total != used) { - error( - "block group[%llu %llu] used %llu but extent items used %llu", - bg_key.objectid, bg_key.offset, used, total); - err |= BG_ACCOUNTING_ERROR; - } - return err; -} - -/* - * Add block group item to the extent tree if @err contains REFERENCER_MISSING. - * FIXME: We still need to repair error of dev_item. - * - * Returns error after repair. - */ -static int repair_chunk_item(struct btrfs_trans_handle *trans, - struct btrfs_root *chunk_root, - struct btrfs_path *path, int err) -{ - struct btrfs_chunk *chunk; - struct btrfs_key chunk_key; - struct extent_buffer *eb = path->nodes[0]; - u64 length; - int slot = path->slots[0]; - u64 type; - int ret = 0; - - btrfs_item_key_to_cpu(eb, &chunk_key, slot); - if (chunk_key.type != BTRFS_CHUNK_ITEM_KEY) - return err; - chunk = btrfs_item_ptr(eb, slot, struct btrfs_chunk); - type = btrfs_chunk_type(path->nodes[0], chunk); - length = btrfs_chunk_length(eb, chunk); - - if (err & REFERENCER_MISSING) { - ret = btrfs_make_block_group(trans, chunk_root->fs_info, 0, - type, chunk_key.offset, length); - if (ret) { - error("fail to add block group item[%llu %llu]", - chunk_key.offset, length); - goto out; - } else { - err &= ~REFERENCER_MISSING; - printf("Added block group item[%llu %llu]\n", - chunk_key.offset, length); - } - } - -out: - return err; -} - -/* - * Check a chunk item. - * Including checking all referred dev_extents and block group - */ -static int check_chunk_item(struct btrfs_fs_info *fs_info, - struct extent_buffer *eb, int slot) -{ - struct btrfs_root *extent_root = fs_info->extent_root; - struct btrfs_root *dev_root = fs_info->dev_root; - struct btrfs_path path; - struct btrfs_key chunk_key; - struct btrfs_key bg_key; - struct btrfs_key devext_key; - struct btrfs_chunk *chunk; - struct extent_buffer *leaf; - struct btrfs_block_group_item *bi; - struct btrfs_block_group_item bg_item; - struct btrfs_dev_extent *ptr; - u64 length; - u64 chunk_end; - u64 stripe_len; - u64 type; - int num_stripes; - u64 offset; - u64 objectid; - int i; - int ret; - int err = 0; - - btrfs_item_key_to_cpu(eb, &chunk_key, slot); - chunk = btrfs_item_ptr(eb, slot, struct btrfs_chunk); - length = btrfs_chunk_length(eb, chunk); - chunk_end = chunk_key.offset + length; - ret = btrfs_check_chunk_valid(fs_info, eb, chunk, slot, - chunk_key.offset); - if (ret < 0) { - error("chunk[%llu %llu) is invalid", chunk_key.offset, - chunk_end); - err |= BYTES_UNALIGNED | UNKNOWN_TYPE; - goto out; - } - type = btrfs_chunk_type(eb, chunk); - - bg_key.objectid = chunk_key.offset; - bg_key.type = BTRFS_BLOCK_GROUP_ITEM_KEY; - bg_key.offset = length; - - btrfs_init_path(&path); - ret = btrfs_search_slot(NULL, extent_root, &bg_key, &path, 0, 0); - if (ret) { - error( - "chunk[%llu %llu) did not find the related block group item", - chunk_key.offset, chunk_end); - err |= REFERENCER_MISSING; - } else{ - leaf = path.nodes[0]; - bi = btrfs_item_ptr(leaf, path.slots[0], - struct btrfs_block_group_item); - read_extent_buffer(leaf, &bg_item, (unsigned long)bi, - sizeof(bg_item)); - if (btrfs_block_group_flags(&bg_item) != type) { - error( -"chunk[%llu %llu) related block group item flags mismatch, wanted: %llu, have: %llu", - chunk_key.offset, chunk_end, type, - btrfs_block_group_flags(&bg_item)); - err |= REFERENCER_MISSING; - } - } - - num_stripes = btrfs_chunk_num_stripes(eb, chunk); - stripe_len = btrfs_stripe_length(fs_info, eb, chunk); - for (i = 0; i < num_stripes; i++) { - btrfs_release_path(&path); - btrfs_init_path(&path); - devext_key.objectid = btrfs_stripe_devid_nr(eb, chunk, i); - devext_key.type = BTRFS_DEV_EXTENT_KEY; - devext_key.offset = btrfs_stripe_offset_nr(eb, chunk, i); - - ret = btrfs_search_slot(NULL, dev_root, &devext_key, &path, - 0, 0); - if (ret) - goto not_match_dev; - - leaf = path.nodes[0]; - ptr = btrfs_item_ptr(leaf, path.slots[0], - struct btrfs_dev_extent); - objectid = btrfs_dev_extent_chunk_objectid(leaf, ptr); - offset = btrfs_dev_extent_chunk_offset(leaf, ptr); - if (objectid != chunk_key.objectid || - offset != chunk_key.offset || - btrfs_dev_extent_length(leaf, ptr) != stripe_len) - goto not_match_dev; - continue; -not_match_dev: - err |= BACKREF_MISSING; - error( - "chunk[%llu %llu) stripe %d did not find the related dev extent", - chunk_key.objectid, chunk_end, i); - continue; - } - btrfs_release_path(&path); -out: - return err; -} - -static int delete_extent_tree_item(struct btrfs_trans_handle *trans, - struct btrfs_root *root, - struct btrfs_path *path) -{ - struct btrfs_key key; - int ret = 0; - - btrfs_item_key_to_cpu(path->nodes[0], &key, path->slots[0]); - btrfs_release_path(path); - ret = btrfs_search_slot(trans, root, &key, path, -1, 1); - if (ret) { - ret = -ENOENT; - goto out; - } - - ret = btrfs_del_item(trans, root, path); - if (ret) - goto out; - - if (path->slots[0] == 0) - btrfs_prev_leaf(root, path); - else - path->slots[0]--; -out: - if (ret) - error("failed to delete root %llu item[%llu, %u, %llu]", - root->objectid, key.objectid, key.type, key.offset); - else - printf("Deleted root %llu item[%llu, %u, %llu]\n", - root->objectid, key.objectid, key.type, key.offset); - return ret; -} - -/* - * Main entry function to check known items and update related accounting info - */ -static int check_leaf_items(struct btrfs_trans_handle *trans, - struct btrfs_root *root, struct btrfs_path *path, - struct node_refs *nrefs, int account_bytes) -{ - struct btrfs_fs_info *fs_info = root->fs_info; - struct btrfs_key key; - struct extent_buffer *eb; - int slot; - int type; - struct btrfs_extent_data_ref *dref; - int ret = 0; - int err = 0; - -again: - eb = path->nodes[0]; - slot = path->slots[0]; - if (slot >= btrfs_header_nritems(eb)) { - if (slot == 0) { - error("empty leaf [%llu %u] root %llu", eb->start, - root->fs_info->nodesize, root->objectid); - err |= EIO; - } - goto out; - } - - btrfs_item_key_to_cpu(eb, &key, slot); - type = key.type; - - switch (type) { - case BTRFS_EXTENT_DATA_KEY: - ret = check_extent_data_item(root, path, nrefs, account_bytes); - if (repair && ret) - ret = repair_extent_data_item(trans, root, path, nrefs, - ret); - err |= ret; - break; - case BTRFS_BLOCK_GROUP_ITEM_KEY: - ret = check_block_group_item(fs_info, eb, slot); - if (repair && - ret & REFERENCER_MISSING) - ret = delete_extent_tree_item(trans, root, path); - err |= ret; - break; - case BTRFS_DEV_ITEM_KEY: - ret = check_dev_item(fs_info, eb, slot); - err |= ret; - break; - case BTRFS_CHUNK_ITEM_KEY: - ret = check_chunk_item(fs_info, eb, slot); - if (repair && ret) - ret = repair_chunk_item(trans, root, path, ret); - err |= ret; - break; - case BTRFS_DEV_EXTENT_KEY: - ret = check_dev_extent_item(fs_info, eb, slot); - err |= ret; - break; - case BTRFS_EXTENT_ITEM_KEY: - case BTRFS_METADATA_ITEM_KEY: - ret = check_extent_item(trans, fs_info, path); - err |= ret; - break; - case BTRFS_EXTENT_CSUM_KEY: - total_csum_bytes += btrfs_item_size_nr(eb, slot); - err |= ret; - break; - case BTRFS_TREE_BLOCK_REF_KEY: - ret = check_tree_block_backref(fs_info, key.offset, - key.objectid, -1); - if (repair && - ret & (REFERENCER_MISMATCH | REFERENCER_MISSING)) - ret = delete_extent_tree_item(trans, root, path); - err |= ret; - break; - case BTRFS_EXTENT_DATA_REF_KEY: - dref = btrfs_item_ptr(eb, slot, struct btrfs_extent_data_ref); - ret = check_extent_data_backref(fs_info, - btrfs_extent_data_ref_root(eb, dref), - btrfs_extent_data_ref_objectid(eb, dref), - btrfs_extent_data_ref_offset(eb, dref), - key.objectid, 0, - btrfs_extent_data_ref_count(eb, dref)); - if (repair && - ret & (REFERENCER_MISMATCH | REFERENCER_MISSING)) - ret = delete_extent_tree_item(trans, root, path); - err |= ret; - break; - case BTRFS_SHARED_BLOCK_REF_KEY: - ret = check_shared_block_backref(fs_info, key.offset, - key.objectid, -1); - if (repair && - ret & (REFERENCER_MISMATCH | REFERENCER_MISSING)) - ret = delete_extent_tree_item(trans, root, path); - err |= ret; - break; - case BTRFS_SHARED_DATA_REF_KEY: - ret = check_shared_data_backref(fs_info, key.offset, - key.objectid); - if (repair && - ret & (REFERENCER_MISMATCH | REFERENCER_MISSING)) - ret = delete_extent_tree_item(trans, root, path); - err |= ret; - break; - default: - break; - } - - ++path->slots[0]; - goto again; -out: - return err; -} - -/* - * Low memory usage version check_chunks_and_extents. - */ -static int check_chunks_and_extents_v2(struct btrfs_fs_info *fs_info) -{ - struct btrfs_trans_handle *trans = NULL; - struct btrfs_path path; - struct btrfs_key old_key; - struct btrfs_key key; - struct btrfs_root *root1; - struct btrfs_root *root; - struct btrfs_root *cur_root; - int err = 0; - int ret; - - root = fs_info->fs_root; - - if (repair) { - trans = btrfs_start_transaction(fs_info->extent_root, 1); - if (IS_ERR(trans)) { - error("failed to start transaction before check"); - return PTR_ERR(trans); - } - } - - root1 = root->fs_info->chunk_root; - ret = check_btrfs_root(trans, root1, 0, 1); - err |= ret; - - root1 = root->fs_info->tree_root; - ret = check_btrfs_root(trans, root1, 0, 1); - err |= ret; - - btrfs_init_path(&path); - key.objectid = BTRFS_EXTENT_TREE_OBJECTID; - key.offset = 0; - key.type = BTRFS_ROOT_ITEM_KEY; - - ret = btrfs_search_slot(NULL, root1, &key, &path, 0, 0); - if (ret) { - error("cannot find extent tree in tree_root"); - goto out; - } - - while (1) { - btrfs_item_key_to_cpu(path.nodes[0], &key, path.slots[0]); - if (key.type != BTRFS_ROOT_ITEM_KEY) - goto next; - old_key = key; - key.offset = (u64)-1; - - if (key.objectid == BTRFS_TREE_RELOC_OBJECTID) - cur_root = btrfs_read_fs_root_no_cache(root->fs_info, - &key); - else - cur_root = btrfs_read_fs_root(root->fs_info, &key); - if (IS_ERR(cur_root) || !cur_root) { - error("failed to read tree: %lld", key.objectid); - goto next; - } - - ret = check_btrfs_root(trans, cur_root, 0, 1); - err |= ret; - - if (key.objectid == BTRFS_TREE_RELOC_OBJECTID) - btrfs_free_fs_root(cur_root); - - btrfs_release_path(&path); - ret = btrfs_search_slot(NULL, root->fs_info->tree_root, - &old_key, &path, 0, 0); - if (ret) - goto out; -next: - ret = btrfs_next_item(root1, &path); - if (ret) - goto out; - } -out: - - /* if repair, update block accounting */ - if (repair) { - ret = btrfs_fix_block_accounting(trans, root); - if (ret) - err |= ret; - else - err &= ~BG_ACCOUNTING_ERROR; - } - - if (trans) - btrfs_commit_transaction(trans, root->fs_info->extent_root); - - btrfs_release_path(&path); - - return err; -} - static int do_check_chunks_and_extents(struct btrfs_fs_info *fs_info) { int ret; |