static int found_old_backref = 0;
static LIST_HEAD(duplicate_extents);
static LIST_HEAD(delete_items);
-static int repair = 0;
static int no_holes = 0;
static int init_extent_tree = 0;
static int check_data_csum = 0;
static struct cache_tree *roots_info_cache = NULL;
struct extent_backref {
- struct list_head list;
+ struct rb_node node;
unsigned int is_data:1;
unsigned int found_extent_tree:1;
unsigned int full_backref:1;
unsigned int broken:1;
};
-static inline struct extent_backref* to_extent_backref(struct list_head *entry)
+static inline struct extent_backref* rb_node_to_extent_backref(struct rb_node *node)
{
- return list_entry(entry, struct extent_backref, list);
+ return rb_entry(node, struct extent_backref, node);
}
struct data_backref {
return container_of(back, struct data_backref, node);
}
+static int compare_data_backref(struct rb_node *node1, struct rb_node *node2)
+{
+ struct extent_backref *ext1 = rb_node_to_extent_backref(node1);
+ struct extent_backref *ext2 = rb_node_to_extent_backref(node2);
+ struct data_backref *back1 = to_data_backref(ext1);
+ struct data_backref *back2 = to_data_backref(ext2);
+
+ WARN_ON(!ext1->is_data);
+ WARN_ON(!ext2->is_data);
+
+ /* parent and root are a union, so this covers both */
+ if (back1->parent > back2->parent)
+ return 1;
+ if (back1->parent < back2->parent)
+ return -1;
+
+ /* This is a full backref and the parents match. */
+ if (back1->node.full_backref)
+ return 0;
+
+ if (back1->owner > back2->owner)
+ return 1;
+ if (back1->owner < back2->owner)
+ return -1;
+
+ if (back1->offset > back2->offset)
+ return 1;
+ if (back1->offset < back2->offset)
+ return -1;
+
+ if (back1->bytes > back2->bytes)
+ return 1;
+ if (back1->bytes < back2->bytes)
+ return -1;
+
+ if (back1->found_ref && back2->found_ref) {
+ if (back1->disk_bytenr > back2->disk_bytenr)
+ return 1;
+ if (back1->disk_bytenr < back2->disk_bytenr)
+ return -1;
+
+ if (back1->found_ref > back2->found_ref)
+ return 1;
+ if (back1->found_ref < back2->found_ref)
+ return -1;
+ }
+
+ return 0;
+}
+
/*
* Much like data_backref, just removed the undetermined members
* and change it to use list_head.
return container_of(back, struct tree_backref, node);
}
+static int compare_tree_backref(struct rb_node *node1, struct rb_node *node2)
+{
+ struct extent_backref *ext1 = rb_node_to_extent_backref(node1);
+ struct extent_backref *ext2 = rb_node_to_extent_backref(node2);
+ struct tree_backref *back1 = to_tree_backref(ext1);
+ struct tree_backref *back2 = to_tree_backref(ext2);
+
+ WARN_ON(ext1->is_data);
+ WARN_ON(ext2->is_data);
+
+ /* parent and root are a union, so this covers both */
+ if (back1->parent > back2->parent)
+ return 1;
+ if (back1->parent < back2->parent)
+ return -1;
+
+ return 0;
+}
+
+static int compare_extent_backref(struct rb_node *node1, struct rb_node *node2)
+{
+ struct extent_backref *ext1 = rb_node_to_extent_backref(node1);
+ struct extent_backref *ext2 = rb_node_to_extent_backref(node2);
+
+ if (ext1->is_data > ext2->is_data)
+ return 1;
+
+ if (ext1->is_data < ext2->is_data)
+ return -1;
+
+ if (ext1->full_backref > ext2->full_backref)
+ return 1;
+ if (ext1->full_backref < ext2->full_backref)
+ return -1;
+
+ if (ext1->is_data)
+ return compare_data_backref(node1, node2);
+ else
+ return compare_tree_backref(node1, node2);
+}
+
/* Explicit initialization for extent_record::flag_block_full_backref */
enum { FLAG_UNSET = 2 };
struct extent_record {
struct list_head backrefs;
struct list_head dups;
+ struct rb_root backref_tree;
struct list_head list;
struct cache_extent cache;
struct btrfs_disk_key parent_key;
struct cache_extent cache_extent;
};
+/*
+ * Error bit for low memory mode check.
+ *
+ * Currently no caller cares about it yet. Just internal use for error
+ * classification.
+ */
+#define BACKREF_MISSING (1 << 0) /* Backref missing in extent tree */
+#define BACKREF_MISMATCH (1 << 1) /* Backref exists but does not match */
+#define BYTES_UNALIGNED (1 << 2) /* Some bytes are not aligned */
+
static void *print_status_check(void *p)
{
struct task_ctx *priv = p;
return ret;
}
+struct node_refs {
+ u64 bytenr[BTRFS_MAX_LEVEL];
+ u64 refs[BTRFS_MAX_LEVEL];
+};
+
static int walk_down_tree(struct btrfs_root *root, struct btrfs_path *path,
- struct walk_control *wc, int *level)
+ struct walk_control *wc, int *level,
+ struct node_refs *nrefs)
{
enum btrfs_tree_block_status status;
u64 bytenr;
WARN_ON(*level < 0);
WARN_ON(*level >= BTRFS_MAX_LEVEL);
- ret = btrfs_lookup_extent_info(NULL, root,
+
+ if (path->nodes[*level]->start == nrefs->bytenr[*level]) {
+ refs = nrefs->refs[*level];
+ ret = 0;
+ } else {
+ ret = btrfs_lookup_extent_info(NULL, root,
path->nodes[*level]->start,
*level, 1, &refs, NULL);
- if (ret < 0) {
- err = ret;
- goto out;
+ if (ret < 0) {
+ err = ret;
+ goto out;
+ }
+ nrefs->bytenr[*level] = path->nodes[*level]->start;
+ nrefs->refs[*level] = refs;
}
if (refs > 1) {
bytenr = btrfs_node_blockptr(cur, path->slots[*level]);
ptr_gen = btrfs_node_ptr_generation(cur, path->slots[*level]);
blocksize = root->nodesize;
- ret = btrfs_lookup_extent_info(NULL, root, bytenr, *level - 1,
- 1, &refs, NULL);
- if (ret < 0)
- refs = 0;
+
+ if (bytenr == nrefs->bytenr[*level - 1]) {
+ refs = nrefs->refs[*level - 1];
+ } else {
+ ret = btrfs_lookup_extent_info(NULL, root, bytenr,
+ *level - 1, 1, &refs, NULL);
+ if (ret < 0) {
+ refs = 0;
+ } else {
+ nrefs->bytenr[*level - 1] = bytenr;
+ nrefs->refs[*level - 1] = refs;
+ }
+ }
if (refs > 1) {
ret = enter_shared_node(root, bytenr, refs,
struct orphan_data_extent *orphan;
struct orphan_data_extent *tmp;
enum btrfs_tree_block_status status;
+ struct node_refs nrefs;
/*
* Reuse the corrupt_block cache tree to record corrupted tree block
memset(&root_node, 0, sizeof(root_node));
cache_tree_init(&root_node.root_cache);
cache_tree_init(&root_node.inode_cache);
+ memset(&nrefs, 0, sizeof(nrefs));
/* Move the orphan extent record to corresponding inode_record */
list_for_each_entry_safe(orphan, tmp,
}
while (1) {
- wret = walk_down_tree(root, &path, wc, &level);
+ wret = walk_down_tree(root, &path, wc, &level, &nrefs);
if (wret < 0)
ret = wret;
if (wret != 0)
static int all_backpointers_checked(struct extent_record *rec, int print_errs)
{
- struct list_head *cur = rec->backrefs.next;
+ struct rb_node *n;
struct extent_backref *back;
struct tree_backref *tback;
struct data_backref *dback;
u64 found = 0;
int err = 0;
- while(cur != &rec->backrefs) {
- back = to_extent_backref(cur);
- cur = cur->next;
+ for (n = rb_first(&rec->backref_tree); n; n = rb_next(n)) {
+ back = rb_node_to_extent_backref(n);
if (!back->found_extent_tree) {
err = 1;
if (!print_errs)
return err;
}
-static int free_all_extent_backrefs(struct extent_record *rec)
+static void __free_one_backref(struct rb_node *node)
{
- struct extent_backref *back;
- struct list_head *cur;
- while (!list_empty(&rec->backrefs)) {
- cur = rec->backrefs.next;
- back = to_extent_backref(cur);
- list_del(cur);
- free(back);
- }
- return 0;
+ struct extent_backref *back = rb_node_to_extent_backref(node);
+
+ free(back);
+}
+
+static void free_all_extent_backrefs(struct extent_record *rec)
+{
+ rb_free_nodes(&rec->backref_tree, __free_one_backref);
}
static void free_extent_record_cache(struct btrfs_fs_info *fs_info,
struct extent_record *rec,
struct extent_buffer *buf)
{
- struct extent_backref *node;
+ struct extent_backref *node, *tmp;
struct tree_backref *back;
struct btrfs_root *ref_root;
struct btrfs_key key;
int found = 0;
int ret;
- list_for_each_entry(node, &rec->backrefs, list) {
+ rbtree_postorder_for_each_entry_safe(node, tmp,
+ &rec->backref_tree, node) {
if (node->is_data)
continue;
if (!node->found_ref)
static int is_extent_tree_record(struct extent_record *rec)
{
- struct list_head *cur = rec->backrefs.next;
- struct extent_backref *node;
+ struct extent_backref *ref, *tmp;
struct tree_backref *back;
int is_extent = 0;
- while(cur != &rec->backrefs) {
- node = to_extent_backref(cur);
- cur = cur->next;
- if (node->is_data)
+ rbtree_postorder_for_each_entry_safe(ref, tmp,
+ &rec->backref_tree, node) {
+ if (ref->is_data)
return 0;
- back = to_tree_backref(node);
- if (node->full_backref)
+ back = to_tree_backref(ref);
+ if (ref->full_backref)
return 0;
if (back->root == BTRFS_EXTENT_TREE_OBJECTID)
is_extent = 1;
return ret;
}
+
static struct tree_backref *find_tree_backref(struct extent_record *rec,
u64 parent, u64 root)
{
- struct list_head *cur = rec->backrefs.next;
- struct extent_backref *node;
- struct tree_backref *back;
+ struct rb_node *node;
+ struct tree_backref *back = NULL;
+ struct tree_backref match = {
+ .node = {
+ .is_data = 0,
+ },
+ };
- while(cur != &rec->backrefs) {
- node = to_extent_backref(cur);
- cur = cur->next;
- if (node->is_data)
- continue;
- back = to_tree_backref(node);
- if (parent > 0) {
- if (!node->full_backref)
- continue;
- if (parent == back->parent)
- return back;
- } else {
- if (node->full_backref)
- continue;
- if (back->root == root)
- return back;
- }
+ if (parent) {
+ match.parent = parent;
+ match.node.full_backref = 1;
+ } else {
+ match.root = root;
}
- return NULL;
+
+ node = rb_search(&rec->backref_tree, &match.node.node,
+ (rb_compare_keys)compare_extent_backref, NULL);
+ if (node)
+ back = to_tree_backref(rb_node_to_extent_backref(node));
+
+ return back;
}
static struct tree_backref *alloc_tree_backref(struct extent_record *rec,
ref->root = root;
ref->node.full_backref = 0;
}
- list_add_tail(&ref->node.list, &rec->backrefs);
+ rb_insert(&rec->backref_tree, &ref->node.node, compare_extent_backref);
return ref;
}
int found_ref,
u64 disk_bytenr, u64 bytes)
{
- struct list_head *cur = rec->backrefs.next;
- struct extent_backref *node;
- struct data_backref *back;
+ struct rb_node *node;
+ struct data_backref *back = NULL;
+ struct data_backref match = {
+ .node = {
+ .is_data = 1,
+ },
+ .owner = owner,
+ .offset = offset,
+ .bytes = bytes,
+ .found_ref = found_ref,
+ .disk_bytenr = disk_bytenr,
+ };
- while(cur != &rec->backrefs) {
- node = to_extent_backref(cur);
- cur = cur->next;
- if (!node->is_data)
- continue;
- back = to_data_backref(node);
- if (parent > 0) {
- if (!node->full_backref)
- continue;
- if (parent == back->parent)
- return back;
- } else {
- if (node->full_backref)
- continue;
- if (back->root == root && back->owner == owner &&
- back->offset == offset) {
- if (found_ref && node->found_ref &&
- (back->bytes != bytes ||
- back->disk_bytenr != disk_bytenr))
- continue;
- return back;
- }
- }
+ if (parent) {
+ match.parent = parent;
+ match.node.full_backref = 1;
+ } else {
+ match.root = root;
}
- return NULL;
+
+ node = rb_search(&rec->backref_tree, &match.node.node,
+ (rb_compare_keys)compare_extent_backref, NULL);
+ if (node)
+ back = to_data_backref(rb_node_to_extent_backref(node));
+
+ return back;
}
static struct data_backref *alloc_data_backref(struct extent_record *rec,
ref->bytes = max_size;
ref->found_ref = 0;
ref->num_refs = 0;
- list_add_tail(&ref->node.list, &rec->backrefs);
+ rb_insert(&rec->backref_tree, &ref->node.node, compare_extent_backref);
if (max_size > rec->max_size)
rec->max_size = max_size;
return ref;
* Check SYSTEM extent, as it's also marked as metadata, we can only
* make sure it's a SYSTEM extent by its backref
*/
- if (!list_empty(&rec->backrefs)) {
+ if (!RB_EMPTY_ROOT(&rec->backref_tree)) {
struct extent_backref *node;
struct tree_backref *tback;
u64 bg_type;
- node = to_extent_backref(rec->backrefs.next);
+ node = rb_node_to_extent_backref(rb_first(&rec->backref_tree));
if (node->is_data) {
/* tree block shouldn't have data backref */
rec->wrong_chunk_type = 1;
INIT_LIST_HEAD(&rec->backrefs);
INIT_LIST_HEAD(&rec->dups);
INIT_LIST_HEAD(&rec->list);
+ rec->backref_tree = RB_ROOT;
memcpy(&rec->parent_key, &tmpl->parent_key, sizeof(tmpl->parent_key));
rec->cache.start = tmpl->start;
rec->cache.size = tmpl->nr;
back->node.found_extent_tree = 0;
if (!back->node.found_extent_tree && back->node.found_ref) {
- list_del(&back->node.list);
+ rb_erase(&back->node.node, &rec->backref_tree);
free(back);
}
} else {
back->node.found_extent_tree = 0;
}
if (!back->node.found_extent_tree && back->node.found_ref) {
- list_del(&back->node.list);
+ rb_erase(&back->node.node, &rec->backref_tree);
free(back);
}
}
static int verify_backrefs(struct btrfs_fs_info *info, struct btrfs_path *path,
struct extent_record *rec)
{
- struct extent_backref *back;
+ struct extent_backref *back, *tmp;
struct data_backref *dback;
struct extent_entry *entry, *best = NULL;
LIST_HEAD(entries);
if (rec->metadata)
return 0;
- list_for_each_entry(back, &rec->backrefs, list) {
+ rbtree_postorder_for_each_entry_safe(back, tmp,
+ &rec->backref_tree, node) {
if (back->full_backref || !back->is_data)
continue;
* Ok great we all agreed on an extent record, let's go find the real
* references and fix up the ones that don't match.
*/
- list_for_each_entry(back, &rec->backrefs, list) {
+ rbtree_postorder_for_each_entry_safe(back, tmp,
+ &rec->backref_tree, node) {
if (back->full_backref || !back->is_data)
continue;
struct extent_record *rec)
{
struct btrfs_root *root;
- struct extent_backref *back;
+ struct extent_backref *back, *tmp;
struct data_backref *dback;
struct cache_extent *cache;
struct btrfs_file_extent_item *fi;
u64 bytenr, bytes;
int ret;
- list_for_each_entry(back, &rec->backrefs, list) {
+ rbtree_postorder_for_each_entry_safe(back, tmp,
+ &rec->backref_tree, node) {
/* Don't care about full backrefs (poor unloved backrefs) */
if (back->full_backref || !back->is_data)
continue;
{
struct btrfs_key key;
struct btrfs_root *dest_root;
- struct extent_backref *back;
+ struct extent_backref *back, *tmp;
struct data_backref *dback;
struct orphan_data_extent *orphan;
struct btrfs_path *path;
path = btrfs_alloc_path();
if (!path)
return -ENOMEM;
- list_for_each_entry(back, &rec->backrefs, list) {
+ rbtree_postorder_for_each_entry_safe(back, tmp,
+ &rec->backref_tree, node) {
if (back->full_backref || !back->is_data ||
!back->found_extent_tree)
continue;
struct btrfs_trans_handle *trans = NULL;
int ret;
struct btrfs_path *path;
- struct list_head *cur = rec->backrefs.next;
struct cache_extent *cache;
- struct extent_backref *back;
+ struct extent_backref *back, *tmp;
int allocated = 0;
u64 flags = 0;
}
/* step three, recreate all the refs we did find */
- while(cur != &rec->backrefs) {
- back = to_extent_backref(cur);
- cur = cur->next;
-
+ rbtree_postorder_for_each_entry_safe(back, tmp,
+ &rec->backref_tree, node) {
/*
* if we didn't find any references, don't create a
* new extent record
goto again;
}
+/*
+ * 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 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 type;
+ u32 nodesize = root->nodesize;
+ u32 item_size;
+ u64 offset;
+ int found_ref = 0;
+ int err = 0;
+ int ret;
+
+ btrfs_init_path(&path);
+ key.objectid = bytenr;
+ if (btrfs_fs_incompat(root->fs_info,
+ BTRFS_FEATURE_INCOMPAT_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;
+
+ 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);
+
+ if (type == BTRFS_TREE_BLOCK_REF_KEY &&
+ (offset == root->objectid || offset == owner)) {
+ found_ref = 1;
+ } else if (type == BTRFS_SHARED_BLOCK_REF_KEY) {
+ /* Check if the backref points to valid referencer */
+ found_ref = !check_tree_block_ref(root, NULL, offset,
+ level + 1, owner);
+ }
+
+ 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;
+ }
+ if (!found_ref)
+ err |= BACKREF_MISSING;
+out:
+ btrfs_release_path(&path);
+ if (eb && (err & BACKREF_MISSING))
+ error("extent[%llu %u] backref lost (owner: %llu, level: %u)",
+ bytenr, nodesize, owner, level);
+ 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 extent_buffer *eb, int slot)
+{
+ struct btrfs_file_extent_item *fi;
+ 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 file_extent_gen;
+ u64 disk_bytenr;
+ u64 disk_num_bytes;
+ u64 extent_num_bytes;
+ u64 extent_flags;
+ u64 extent_gen;
+ u32 item_size;
+ unsigned long end;
+ unsigned long ptr;
+ int type;
+ u64 ref_root;
+ int found_dbackref = 0;
+ int err = 0;
+ int ret;
+
+ btrfs_item_key_to_cpu(eb, &fi_key, slot);
+ fi = btrfs_item_ptr(eb, slot, struct btrfs_file_extent_item);
+ file_extent_gen = btrfs_file_extent_generation(eb, fi);
+
+ /* 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);
+
+ /* Check unaligned disk_num_bytes and num_bytes */
+ if (!IS_ALIGNED(disk_num_bytes, root->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->sectorsize);
+ err |= BYTES_UNALIGNED;
+ } else {
+ data_bytes_allocated += disk_num_bytes;
+ }
+ if (!IS_ALIGNED(extent_num_bytes, root->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->sectorsize);
+ err |= BYTES_UNALIGNED;
+ } else {
+ 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) {
+ err |= BACKREF_MISSING;
+ goto error;
+ }
+
+ 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);
+ extent_gen = btrfs_extent_generation(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;
+ }
+
+ if (file_extent_gen < extent_gen) {
+ error(
+"extent[%llu %llu] backref generation mismatch, wanted: <=%llu, have: %llu",
+ disk_bytenr, disk_num_bytes, file_extent_gen,
+ extent_gen);
+ 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;
+ while (ptr < end) {
+ iref = (struct btrfs_extent_inline_ref *)ptr;
+ type = btrfs_extent_inline_ref_type(leaf, iref);
+ dref = (struct btrfs_extent_data_ref *)(&iref->offset);
+
+ if (type == BTRFS_EXTENT_DATA_REF_KEY) {
+ ref_root = btrfs_extent_data_ref_root(leaf, dref);
+ if (ref_root == owner || ref_root == root->objectid)
+ 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);
+ }
+
+ if (found_dbackref)
+ break;
+ ptr += btrfs_extent_inline_ref_size(type);
+ }
+
+ /* Didn't found inlined data backref, try EXTENT_DATA_REF_KEY */
+ if (!found_dbackref) {
+ btrfs_release_path(&path);
+
+ btrfs_init_path(&path);
+ 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);
+
+ ret = btrfs_search_slot(NULL, root->fs_info->extent_root,
+ &dbref_key, &path, 0, 0);
+ if (!ret)
+ found_dbackref = 1;
+ }
+
+ if (!found_dbackref)
+ err |= BACKREF_MISSING;
+error:
+ 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;
+ u32 nodesize = btrfs_super_nodesize(fs_info->super_copy);
+ 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(fs_info, bytenr, nodesize, 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;
+}
+
static int btrfs_fsck_reinit_root(struct btrfs_trans_handle *trans,
struct btrfs_root *root, int overwrite)
{
int init_csum_tree = 0;
int readonly = 0;
int qgroup_report = 0;
+ int qgroups_repaired = 0;
enum btrfs_open_ctree_flags ctree_flags = OPEN_CTREE_EXCLUSIVE;
while(1) {
uuidbuf);
ret = qgroup_verify_all(info);
if (ret == 0)
- ret = report_qgroups(1);
+ report_qgroups(1);
goto close_out;
}
if (subvolid) {
err = qgroup_verify_all(info);
if (err)
goto out;
+ report_qgroups(0);
+ err = repair_qgroups(info, &qgroups_repaired);
+ if (err)
+ goto out;
}
if (!list_empty(&root->fs_info->recow_ebs)) {
}
out:
/* Don't override original ret */
- if (ret)
- report_qgroups(0);
- else
- ret = report_qgroups(0);
+ if (!ret && qgroups_repaired)
+ ret = qgroups_repaired;
+
if (found_old_backref) { /*
* there was a disk format change when mixed
* backref was in testing tree. The old format