+ 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;
+}
+
+/*
+ * 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_fs_info *fs_info,
+ struct extent_buffer *eb, int slot)
+{
+ struct btrfs_extent_item *ei;
+ struct btrfs_extent_inline_ref *iref;
+ struct btrfs_extent_data_ref *dref;
+ unsigned long end;
+ unsigned long ptr;
+ int type;
+ u32 nodesize = btrfs_super_nodesize(fs_info->super_copy);
+ u32 item_size = btrfs_item_size_nr(eb, slot);
+ u64 flags;
+ u64 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;
+ else
+ bytes_used += 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;
+
+ if (ptr >= end) {
+ err |= ITEM_SIZE_MISMATCH;
+ goto out;
+ }
+
+ /* Now check every backref in this extent item */
+next:
+ 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:
+ ret = check_tree_block_backref(fs_info, offset, key.objectid,
+ level);
+ err |= ret;
+ break;
+ case BTRFS_SHARED_BLOCK_REF_KEY:
+ 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);
+ 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, key.offset,
+ btrfs_extent_data_ref_count(eb, dref));
+ err |= ret;
+ break;
+ case BTRFS_SHARED_DATA_REF_KEY:
+ 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);
+ err |= UNKNOWN_TYPE;
+ goto out;
+ }
+
+ ptr += btrfs_extent_inline_ref_size(type);
+ if (ptr < end)
+ 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);
+ if (btrfs_chunk_length(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 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);
+
+ 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) {
+ 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;
+ }
+ 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];
+ 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 |= ACCOUNTING_MISMATCH;
+ }
+ 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;
+ u32 sectorsize = btrfs_super_sectorsize(fs_info->super_copy);
+ u64 length;
+ u64 chunk_end;
+ u64 type;
+ u64 profile;
+ 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;
+ if (!IS_ALIGNED(length, sectorsize)) {
+ error("chunk[%llu %llu) not aligned to %u",
+ chunk_key.offset, chunk_end, sectorsize);
+ err |= BYTES_UNALIGNED;
+ goto out;
+ }
+
+ type = btrfs_chunk_type(eb, chunk);
+ profile = type & BTRFS_BLOCK_GROUP_PROFILE_MASK;
+ if (!(type & BTRFS_BLOCK_GROUP_TYPE_MASK)) {
+ error("chunk[%llu %llu) has no chunk type",
+ chunk_key.offset, chunk_end);
+ err |= UNKNOWN_TYPE;
+ }
+ if (profile && (profile & (profile - 1))) {
+ error("chunk[%llu %llu) multiple profiles detected: %llx",
+ chunk_key.offset, chunk_end, profile);
+ err |= UNKNOWN_TYPE;
+ }
+
+ 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);
+ 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) != length)
+ 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;
+}
+
+/*
+ * Main entry function to check known items and update related accounting info
+ */
+static int check_leaf_items(struct btrfs_root *root, struct extent_buffer *eb)
+{
+ struct btrfs_fs_info *fs_info = root->fs_info;
+ struct btrfs_key key;
+ int slot = 0;
+ int type;
+ struct btrfs_extent_data_ref *dref;
+ int ret;
+ int err = 0;
+
+next:
+ btrfs_item_key_to_cpu(eb, &key, slot);
+ type = key.type;
+
+ switch (type) {
+ case BTRFS_EXTENT_DATA_KEY:
+ ret = check_extent_data_item(root, eb, slot);
+ err |= ret;
+ break;
+ case BTRFS_BLOCK_GROUP_ITEM_KEY:
+ ret = check_block_group_item(fs_info, eb, slot);
+ 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);
+ 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(fs_info, eb, slot);
+ err |= ret;
+ break;
+ case BTRFS_EXTENT_CSUM_KEY:
+ total_csum_bytes += btrfs_item_size_nr(eb, slot);
+ break;
+ case BTRFS_TREE_BLOCK_REF_KEY:
+ ret = check_tree_block_backref(fs_info, key.offset,
+ key.objectid, -1);
+ 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));
+ err |= ret;
+ break;
+ case BTRFS_SHARED_BLOCK_REF_KEY:
+ ret = check_shared_block_backref(fs_info, key.offset,
+ key.objectid, -1);
+ err |= ret;
+ break;
+ case BTRFS_SHARED_DATA_REF_KEY:
+ ret = check_shared_data_backref(fs_info, key.offset,
+ key.objectid);
+ err |= ret;
+ break;
+ default:
+ break;
+ }
+
+ if (++slot < btrfs_header_nritems(eb))
+ goto next;
+
+ return err;
+}
+
+/*
+ * Helper function for later fs/subvol tree check. To determine if a tree
+ * block should be checked.
+ * This function will ensure only the direct referencer with lowest rootid to
+ * check a fs/subvolume tree block.
+ *
+ * Backref check at extent tree would detect errors like missing subvolume
+ * tree, so we can do aggressive check to reduce duplicated checks.
+ */
+static int should_check(struct btrfs_root *root, struct extent_buffer *eb)
+{
+ struct btrfs_root *extent_root = root->fs_info->extent_root;
+ struct btrfs_key key;
+ struct btrfs_path path;
+ struct extent_buffer *leaf;
+ int slot;
+ struct btrfs_extent_item *ei;
+ unsigned long ptr;
+ unsigned long end;
+ int type;
+ u32 item_size;
+ u64 offset;
+ struct btrfs_extent_inline_ref *iref;
+ int ret;
+
+ btrfs_init_path(&path);
+ key.objectid = btrfs_header_bytenr(eb);
+ key.type = BTRFS_METADATA_ITEM_KEY;
+ key.offset = (u64)-1;
+
+ /*
+ * Any failure in backref resolving means we can't determine
+ * whom the tree block belongs to.
+ * So in that case, we need to check that tree block
+ */
+ ret = btrfs_search_slot(NULL, extent_root, &key, &path, 0, 0);
+ if (ret < 0)
+ goto need_check;
+
+ ret = btrfs_previous_extent_item(extent_root, &path,
+ btrfs_header_bytenr(eb));
+ if (ret)
+ goto need_check;
+
+ 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) {
+ iref = (struct btrfs_extent_inline_ref *)(ei + 1);
+ } else {
+ struct btrfs_tree_block_info *info;
+
+ info = (struct btrfs_tree_block_info *)(ei + 1);
+ iref = (struct btrfs_extent_inline_ref *)(info + 1);
+ }
+
+ 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);
+
+ /*
+ * We only check the tree block if current root is
+ * the lowest referencer of it.
+ */
+ if (type == BTRFS_TREE_BLOCK_REF_KEY &&
+ offset < root->objectid) {
+ btrfs_release_path(&path);
+ return 0;
+ }
+
+ ptr += btrfs_extent_inline_ref_size(type);
+ }
+ /*
+ * Normally we should also check keyed tree block ref, but that may be
+ * very time consuming. Inlined ref should already make us skip a lot
+ * of refs now. So skip search keyed tree block ref.
+ */
+
+need_check:
+ btrfs_release_path(&path);
+ return 1;
+}
+
+/*
+ * Traversal function for tree block. We will do:
+ * 1) Skip shared fs/subvolume tree blocks
+ * 2) Update related bytes accounting
+ * 3) Pre-order traversal
+ */
+static int traverse_tree_block(struct btrfs_root *root,
+ struct extent_buffer *node)
+{
+ struct extent_buffer *eb;
+ struct btrfs_key key;
+ struct btrfs_key drop_key;
+ int level;
+ u64 nr;
+ int i;
+ int err = 0;
+ int ret;
+
+ /*
+ * Skip shared fs/subvolume tree block, in that case they will
+ * be checked by referencer with lowest rootid
+ */
+ if (is_fstree(root->objectid) && !should_check(root, node))
+ return 0;
+
+ /* Update bytes accounting */
+ total_btree_bytes += node->len;
+ if (fs_root_objectid(btrfs_header_owner(node)))
+ total_fs_tree_bytes += node->len;
+ if (btrfs_header_owner(node) == BTRFS_EXTENT_TREE_OBJECTID)
+ total_extent_tree_bytes += node->len;
+ if (!found_old_backref &&
+ btrfs_header_owner(node) == BTRFS_TREE_RELOC_OBJECTID &&
+ btrfs_header_backref_rev(node) == BTRFS_MIXED_BACKREF_REV &&
+ !btrfs_header_flag(node, BTRFS_HEADER_FLAG_RELOC))
+ found_old_backref = 1;
+
+ /* pre-order tranversal, check itself first */
+ level = btrfs_header_level(node);
+ ret = check_tree_block_ref(root, node, btrfs_header_bytenr(node),
+ btrfs_header_level(node),
+ btrfs_header_owner(node));
+ err |= ret;
+ if (err)
+ error(
+ "check %s failed root %llu bytenr %llu level %d, force continue check",
+ level ? "node":"leaf", root->objectid,
+ btrfs_header_bytenr(node), btrfs_header_level(node));
+
+ if (!level) {
+ btree_space_waste += btrfs_leaf_free_space(root, node);
+ ret = check_leaf_items(root, node);
+ err |= ret;
+ return err;
+ }
+
+ nr = btrfs_header_nritems(node);
+ btrfs_disk_key_to_cpu(&drop_key, &root->root_item.drop_progress);
+ btree_space_waste += (BTRFS_NODEPTRS_PER_BLOCK(root) - nr) *
+ sizeof(struct btrfs_key_ptr);
+
+ /* Then check all its children */
+ for (i = 0; i < nr; i++) {
+ u64 blocknr = btrfs_node_blockptr(node, i);
+
+ btrfs_node_key_to_cpu(node, &key, i);
+ if (level == root->root_item.drop_level &&
+ is_dropped_key(&key, &drop_key))
+ continue;
+
+ /*
+ * As a btrfs tree has most 8 levels (0..7), so it's quite safe
+ * to call the function itself.
+ */
+ eb = read_tree_block(root, blocknr, root->nodesize, 0);
+ if (extent_buffer_uptodate(eb)) {
+ ret = traverse_tree_block(root, eb);
+ err |= ret;
+ }
+ free_extent_buffer(eb);
+ }
+
+ return err;
+}
+
+/*
+ * Low memory usage version check_chunks_and_extents.
+ */
+static int check_chunks_and_extents_v2(struct btrfs_root *root)
+{
+ struct btrfs_path path;
+ struct btrfs_key key;
+ struct btrfs_root *root1;
+ struct btrfs_root *cur_root;
+ int err = 0;
+ int ret;
+
+ root1 = root->fs_info->chunk_root;
+ ret = traverse_tree_block(root1, root1->node);
+ err |= ret;
+
+ root1 = root->fs_info->tree_root;
+ ret = traverse_tree_block(root1, root1->node);
+ 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 treet 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;
+ key.offset = (u64)-1;
+
+ 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 = traverse_tree_block(cur_root, cur_root->node);
+ err |= ret;
+
+next:
+ ret = btrfs_next_item(root1, &path);
+ if (ret)
+ goto out;
+ }
+
+out:
+ btrfs_release_path(&path);
+ return err;
+}
+
+static int btrfs_fsck_reinit_root(struct btrfs_trans_handle *trans,
+ struct btrfs_root *root, int overwrite)
+{
+ struct extent_buffer *c;
+ struct extent_buffer *old = root->node;
+ int level;
+ int ret;
+ struct btrfs_disk_key disk_key = {0,0,0};
+
+ level = 0;
+
+ if (overwrite) {
+ c = old;
+ extent_buffer_get(c);
+ goto init;
+ }
+ c = btrfs_alloc_free_block(trans, root,
+ root->nodesize,
+ root->root_key.objectid,
+ &disk_key, level, 0, 0);
+ if (IS_ERR(c)) {
+ c = old;
+ extent_buffer_get(c);
+ overwrite = 1;
+ }
+init:
+ memset_extent_buffer(c, 0, 0, sizeof(struct btrfs_header));
+ btrfs_set_header_level(c, level);
+ btrfs_set_header_bytenr(c, c->start);
+ btrfs_set_header_generation(c, trans->transid);
+ btrfs_set_header_backref_rev(c, BTRFS_MIXED_BACKREF_REV);
+ btrfs_set_header_owner(c, root->root_key.objectid);
+
+ write_extent_buffer(c, root->fs_info->fsid,
+ btrfs_header_fsid(), BTRFS_FSID_SIZE);
+
+ write_extent_buffer(c, root->fs_info->chunk_tree_uuid,
+ btrfs_header_chunk_tree_uuid(c),
+ BTRFS_UUID_SIZE);
+
+ btrfs_mark_buffer_dirty(c);
+ /*
+ * this case can happen in the following case:
+ *
+ * 1.overwrite previous root.
+ *
+ * 2.reinit reloc data root, this is because we skip pin
+ * down reloc data tree before which means we can allocate
+ * same block bytenr here.
+ */
+ if (old->start == c->start) {
+ btrfs_set_root_generation(&root->root_item,
+ trans->transid);
+ root->root_item.level = btrfs_header_level(root->node);
+ ret = btrfs_update_root(trans, root->fs_info->tree_root,
+ &root->root_key, &root->root_item);
+ if (ret) {
+ free_extent_buffer(c);
+ return ret;
+ }
+ }
+ free_extent_buffer(old);
+ root->node = c;
+ add_root_to_dirty_list(root);
+ return 0;
+}
+
+static int pin_down_tree_blocks(struct btrfs_fs_info *fs_info,
+ struct extent_buffer *eb, int tree_root)
+{
+ struct extent_buffer *tmp;
+ struct btrfs_root_item *ri;
+ struct btrfs_key key;
+ u64 bytenr;
+ u32 nodesize;
+ int level = btrfs_header_level(eb);
+ int nritems;
+ int ret;
+ int i;
+
+ /*
+ * If we have pinned this block before, don't pin it again.
+ * This can not only avoid forever loop with broken filesystem
+ * but also give us some speedups.
+ */
+ if (test_range_bit(&fs_info->pinned_extents, eb->start,
+ eb->start + eb->len - 1, EXTENT_DIRTY, 0))
+ return 0;
+
+ btrfs_pin_extent(fs_info, eb->start, eb->len);
+
+ nodesize = btrfs_super_nodesize(fs_info->super_copy);
+ nritems = btrfs_header_nritems(eb);
+ for (i = 0; i < nritems; i++) {
+ if (level == 0) {
+ btrfs_item_key_to_cpu(eb, &key, i);
+ if (key.type != BTRFS_ROOT_ITEM_KEY)
+ continue;
+ /* Skip the extent root and reloc roots */
+ if (key.objectid == BTRFS_EXTENT_TREE_OBJECTID ||