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* rb_node_to_extent_backref(struct rb_node *node)
+{
+ return rb_entry(node, struct extent_backref, node);
+}
+
struct data_backref {
struct extent_backref node;
union {
u32 found_ref;
};
+static inline struct data_backref* to_data_backref(struct extent_backref *back)
+{
+ 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.
};
};
+static inline struct tree_backref* to_tree_backref(struct extent_backref *back)
+{
+ 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;
u64 info_objectid;
u32 num_duplicates;
u8 info_level;
- int flag_block_full_backref;
+ unsigned int flag_block_full_backref:2;
unsigned int found_rec:1;
unsigned int content_checked:1;
unsigned int owner_ref_checked:1;
unsigned int wrong_chunk_type:1;
};
+static inline struct extent_record* to_extent_record(struct list_head *entry)
+{
+ return container_of(entry, struct extent_record, list);
+}
+
struct inode_backref {
struct list_head list;
unsigned int found_dir_item:1;
char name[0];
};
+static inline struct inode_backref* to_inode_backref(struct list_head *entry)
+{
+ return list_entry(entry, struct inode_backref, list);
+}
+
struct root_item_record {
struct list_head list;
u64 objectid;
char name[0];
};
+static inline struct root_backref* to_root_backref(struct list_head *entry)
+{
+ return list_entry(entry, struct root_backref, list);
+}
+
struct root_record {
struct list_head backrefs;
struct cache_extent cache;
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 */
+
static void *print_status_check(void *p)
{
struct task_ctx *priv = p;
return -EEXIST;
/*
- * Now there will be no overflap, delete the hole and re-add the
+ * Now there will be no overlap, delete the hole and re-add the
* split(s) if they exists.
*/
if (start > hole->start) {
if (errors & REF_ERR_DUP_INODE_REF)
fprintf(stderr, ", dup inode ref");
if (errors & REF_ERR_INDEX_UNMATCH)
- fprintf(stderr, ", index unmatch");
+ fprintf(stderr, ", index mismatch");
if (errors & REF_ERR_FILETYPE_UNMATCH)
- fprintf(stderr, ", filetype unmatch");
+ fprintf(stderr, ", filetype mismatch");
if (errors & REF_ERR_NAME_TOO_LONG)
fprintf(stderr, ", name too long");
if (errors & REF_ERR_NO_ROOT_REF)
return;
while (!list_empty(&rec->backrefs)) {
- backref = list_entry(rec->backrefs.next,
- struct inode_backref, list);
+ backref = to_inode_backref(rec->backrefs.next);
list_del(&backref->list);
free(backref);
}
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,
goto out;
if (list_empty(&rec->backrefs))
goto out;
- backref = list_entry(rec->backrefs.next, struct inode_backref, list);
+ backref = to_inode_backref(rec->backrefs.next);
if (!backref->found_inode_ref)
goto out;
if (backref->index != 0 || backref->namelen != 2 ||
type_recovered = 1;
filetype = BTRFS_FT_REG_FILE;
} else{
- printf("Can't determint the filetype for inode %llu, assume it is a normal file\n",
+ printf("Can't determine the filetype for inode %llu, assume it is a normal file\n",
rec->ino);
type_recovered = 1;
filetype = BTRFS_FT_REG_FILE;
/*
* We need to record the highest inode number for later 'lost+found'
* dir creation.
- * We must select a ino not used/refered by any existing inode, or
+ * We must select an ino not used/referred by any existing inode, or
* 'lost+found' ino may be a missing ino in a corrupted leaf,
* this may cause 'lost+found' dir has wrong nlinks.
*/
rec = container_of(cache, struct root_record, cache);
while (!list_empty(&rec->backrefs)) {
- backref = list_entry(rec->backrefs.next,
- struct root_backref, list);
+ backref = to_root_backref(rec->backrefs.next);
list_del(&backref->list);
free(backref);
}
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 = list_entry(cur, struct extent_backref, list);
- 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)
goto out;
if (back->is_data) {
- dback = (struct data_backref *)back;
+ dback = to_data_backref(back);
fprintf(stderr, "Backref %llu %s %llu"
" owner %llu offset %llu num_refs %lu"
" not found in extent tree\n",
(unsigned long long)dback->offset,
(unsigned long)dback->num_refs);
} else {
- tback = (struct tree_backref *)back;
+ tback = to_tree_backref(back);
fprintf(stderr, "Backref %llu parent %llu"
" root %llu not found in extent tree\n",
(unsigned long long)rec->start,
err = 1;
if (!print_errs)
goto out;
- tback = (struct tree_backref *)back;
+ tback = to_tree_backref(back);
fprintf(stderr, "Backref %llu %s %llu not referenced back %p\n",
(unsigned long long)rec->start,
back->full_backref ? "parent" : "root",
(unsigned long long)tback->root, back);
}
if (back->is_data) {
- dback = (struct data_backref *)back;
+ dback = to_data_backref(back);
if (dback->found_ref != dback->num_refs) {
err = 1;
if (!print_errs)
if (!back->is_data) {
found += 1;
} else {
- dback = (struct data_backref *)back;
+ dback = to_data_backref(back);
found += dback->found_ref;
}
}
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 = list_entry(cur, struct extent_backref, list);
- 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)
continue;
if (node->full_backref)
continue;
- back = (struct tree_backref *)node;
+ back = to_tree_backref(node);
if (btrfs_header_owner(buf) == back->root)
return 0;
}
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 = list_entry(cur, struct extent_backref, list);
- 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 = (struct 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;
} else {
/*
* Signal to callers we need to start the scan over
- * again since we'll have cow'ed blocks.
+ * again since we'll have cowed blocks.
*/
ret = -EAGAIN;
}
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 = list_entry(cur, struct extent_backref, list);
- cur = cur->next;
- if (node->is_data)
- continue;
- back = (struct 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 = list_entry(cur, struct extent_backref, list);
- cur = cur->next;
- if (!node->is_data)
- continue;
- back = (struct 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 = list_entry(rec->backrefs.next, struct extent_backref,
- list);
+ 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;
}
}
+/*
+ * Allocate a new extent record, fill default values from @tmpl and insert int
+ * @extent_cache. Caller is supposed to make sure the [start,nr) is not in
+ * the cache, otherwise it fails.
+ */
+static int add_extent_rec_nolookup(struct cache_tree *extent_cache,
+ struct extent_record *tmpl)
+{
+ struct extent_record *rec;
+ int ret = 0;
+
+ rec = malloc(sizeof(*rec));
+ if (!rec)
+ return -ENOMEM;
+ rec->start = tmpl->start;
+ rec->max_size = tmpl->max_size;
+ rec->nr = max(tmpl->nr, tmpl->max_size);
+ rec->found_rec = tmpl->found_rec;
+ rec->content_checked = tmpl->content_checked;
+ rec->owner_ref_checked = tmpl->owner_ref_checked;
+ rec->num_duplicates = 0;
+ rec->metadata = tmpl->metadata;
+ rec->flag_block_full_backref = FLAG_UNSET;
+ rec->bad_full_backref = 0;
+ rec->crossing_stripes = 0;
+ rec->wrong_chunk_type = 0;
+ rec->is_root = tmpl->is_root;
+ rec->refs = tmpl->refs;
+ rec->extent_item_refs = tmpl->extent_item_refs;
+ rec->parent_generation = tmpl->parent_generation;
+ 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;
+ ret = insert_cache_extent(extent_cache, &rec->cache);
+ BUG_ON(ret);
+ bytes_used += rec->nr;
+
+ if (tmpl->metadata)
+ rec->crossing_stripes = check_crossing_stripes(rec->start,
+ global_info->tree_root->nodesize);
+ check_extent_type(rec);
+ return ret;
+}
+
+/*
+ * Lookup and modify an extent, some values of @tmpl are interpreted verbatim,
+ * some are hints:
+ * - refs - if found, increase refs
+ * - is_root - if found, set
+ * - content_checked - if found, set
+ * - owner_ref_checked - if found, set
+ *
+ * If not found, create a new one, initialize and insert.
+ */
static int add_extent_rec(struct cache_tree *extent_cache,
- struct btrfs_key *parent_key, u64 parent_gen,
- u64 start, u64 nr, u64 extent_item_refs,
- int is_root, int inc_ref, int set_checked,
- int metadata, int extent_rec, u64 max_size)
+ struct extent_record *tmpl)
{
struct extent_record *rec;
struct cache_extent *cache;
int ret = 0;
int dup = 0;
- cache = lookup_cache_extent(extent_cache, start, nr);
+ cache = lookup_cache_extent(extent_cache, tmpl->start, tmpl->nr);
if (cache) {
rec = container_of(cache, struct extent_record, cache);
- if (inc_ref)
+ if (tmpl->refs)
rec->refs++;
if (rec->nr == 1)
- rec->nr = max(nr, max_size);
+ rec->nr = max(tmpl->nr, tmpl->max_size);
/*
* We need to make sure to reset nr to whatever the extent
* record says was the real size, this way we can compare it to
* the backrefs.
*/
- if (extent_rec) {
- if (start != rec->start || rec->found_rec) {
+ if (tmpl->found_rec) {
+ if (tmpl->start != rec->start || rec->found_rec) {
struct extent_record *tmp;
dup = 1;
tmp = malloc(sizeof(*tmp));
if (!tmp)
return -ENOMEM;
- tmp->start = start;
- tmp->max_size = max_size;
- tmp->nr = nr;
+ tmp->start = tmpl->start;
+ tmp->max_size = tmpl->max_size;
+ tmp->nr = tmpl->nr;
tmp->found_rec = 1;
- tmp->metadata = metadata;
- tmp->extent_item_refs = extent_item_refs;
+ tmp->metadata = tmpl->metadata;
+ tmp->extent_item_refs = tmpl->extent_item_refs;
INIT_LIST_HEAD(&tmp->list);
list_add_tail(&tmp->list, &rec->dups);
rec->num_duplicates++;
} else {
- rec->nr = nr;
+ rec->nr = tmpl->nr;
rec->found_rec = 1;
}
}
- if (extent_item_refs && !dup) {
+ if (tmpl->extent_item_refs && !dup) {
if (rec->extent_item_refs) {
fprintf(stderr, "block %llu rec "
"extent_item_refs %llu, passed %llu\n",
- (unsigned long long)start,
+ (unsigned long long)tmpl->start,
(unsigned long long)
rec->extent_item_refs,
- (unsigned long long)extent_item_refs);
+ (unsigned long long)tmpl->extent_item_refs);
}
- rec->extent_item_refs = extent_item_refs;
+ rec->extent_item_refs = tmpl->extent_item_refs;
}
- if (is_root)
+ if (tmpl->is_root)
rec->is_root = 1;
- if (set_checked) {
+ if (tmpl->content_checked)
rec->content_checked = 1;
+ if (tmpl->owner_ref_checked)
rec->owner_ref_checked = 1;
- }
-
- if (parent_key)
- btrfs_cpu_key_to_disk(&rec->parent_key, parent_key);
- if (parent_gen)
- rec->parent_generation = parent_gen;
-
- if (rec->max_size < max_size)
- rec->max_size = max_size;
+ memcpy(&rec->parent_key, &tmpl->parent_key,
+ sizeof(tmpl->parent_key));
+ if (tmpl->parent_generation)
+ rec->parent_generation = tmpl->parent_generation;
+ if (rec->max_size < tmpl->max_size)
+ rec->max_size = tmpl->max_size;
/*
* A metadata extent can't cross stripe_len boundary, otherwise
* As now stripe_len is fixed to BTRFS_STRIPE_LEN, just check
* it.
*/
- if (metadata)
+ if (tmpl->metadata)
rec->crossing_stripes = check_crossing_stripes(
- rec->start, rec->max_size);
+ rec->start, global_info->tree_root->nodesize);
check_extent_type(rec);
maybe_free_extent_rec(extent_cache, rec);
return ret;
}
- rec = malloc(sizeof(*rec));
- if (!rec)
- return -ENOMEM;
- rec->start = start;
- rec->max_size = max_size;
- rec->nr = max(nr, max_size);
- rec->found_rec = !!extent_rec;
- rec->content_checked = 0;
- rec->owner_ref_checked = 0;
- rec->num_duplicates = 0;
- rec->metadata = metadata;
- rec->flag_block_full_backref = -1;
- rec->bad_full_backref = 0;
- rec->crossing_stripes = 0;
- rec->wrong_chunk_type = 0;
- INIT_LIST_HEAD(&rec->backrefs);
- INIT_LIST_HEAD(&rec->dups);
- INIT_LIST_HEAD(&rec->list);
- if (is_root)
- rec->is_root = 1;
- else
- rec->is_root = 0;
-
- if (inc_ref)
- rec->refs = 1;
- else
- rec->refs = 0;
+ ret = add_extent_rec_nolookup(extent_cache, tmpl);
- if (extent_item_refs)
- rec->extent_item_refs = extent_item_refs;
- else
- rec->extent_item_refs = 0;
-
- if (parent_key)
- btrfs_cpu_key_to_disk(&rec->parent_key, parent_key);
- else
- memset(&rec->parent_key, 0, sizeof(*parent_key));
-
- if (parent_gen)
- rec->parent_generation = parent_gen;
- else
- rec->parent_generation = 0;
-
- rec->cache.start = start;
- rec->cache.size = nr;
- ret = insert_cache_extent(extent_cache, &rec->cache);
- BUG_ON(ret);
- bytes_used += nr;
- if (set_checked) {
- rec->content_checked = 1;
- rec->owner_ref_checked = 1;
- }
-
- if (metadata)
- rec->crossing_stripes = check_crossing_stripes(rec->start,
- rec->max_size);
- check_extent_type(rec);
return ret;
}
cache = lookup_cache_extent(extent_cache, bytenr, 1);
if (!cache) {
- add_extent_rec(extent_cache, NULL, 0, bytenr,
- 1, 0, 0, 0, 0, 1, 0, 0);
+ struct extent_record tmpl;
+
+ memset(&tmpl, 0, sizeof(tmpl));
+ tmpl.start = bytenr;
+ tmpl.nr = 1;
+ tmpl.metadata = 1;
+
+ add_extent_rec_nolookup(extent_cache, &tmpl);
+
cache = lookup_cache_extent(extent_cache, bytenr, 1);
if (!cache)
abort();
cache = lookup_cache_extent(extent_cache, bytenr, 1);
if (!cache) {
- add_extent_rec(extent_cache, NULL, 0, bytenr, 1, 0, 0, 0, 0,
- 0, 0, max_size);
+ struct extent_record tmpl;
+
+ memset(&tmpl, 0, sizeof(tmpl));
+ tmpl.start = bytenr;
+ tmpl.nr = 1;
+ tmpl.max_size = max_size;
+
+ add_extent_rec_nolookup(extent_cache, &tmpl);
+
cache = lookup_cache_extent(extent_cache, bytenr, 1);
if (!cache)
abort();
struct btrfs_extent_data_ref *dref;
struct btrfs_shared_data_ref *sref;
struct btrfs_key key;
+ struct extent_record tmpl;
unsigned long end;
unsigned long ptr;
int type;
#else
BUG();
#endif
- return add_extent_rec(extent_cache, NULL, 0, key.objectid,
- num_bytes, refs, 0, 0, 0, metadata, 1,
- num_bytes);
+ memset(&tmpl, 0, sizeof(tmpl));
+ tmpl.start = key.objectid;
+ tmpl.nr = num_bytes;
+ tmpl.extent_item_refs = refs;
+ tmpl.metadata = metadata;
+ tmpl.found_rec = 1;
+ tmpl.max_size = num_bytes;
+
+ return add_extent_rec(extent_cache, &tmpl);
}
ei = btrfs_item_ptr(eb, slot, struct btrfs_extent_item);
else
metadata = 0;
- add_extent_rec(extent_cache, NULL, 0, key.objectid, num_bytes,
- refs, 0, 0, 0, metadata, 1, num_bytes);
+ memset(&tmpl, 0, sizeof(tmpl));
+ tmpl.start = key.objectid;
+ tmpl.nr = num_bytes;
+ tmpl.extent_item_refs = refs;
+ tmpl.metadata = metadata;
+ tmpl.found_rec = 1;
+ tmpl.max_size = num_bytes;
+ add_extent_rec(extent_cache, &tmpl);
ptr = (unsigned long)(ei + 1);
if (btrfs_extent_flags(eb, ei) & BTRFS_EXTENT_FLAG_TREE_BLOCK &&
ret = verify_space_cache(root, cache);
if (ret) {
- fprintf(stderr, "cache appears valid but isnt %Lu\n",
+ fprintf(stderr, "cache appears valid but isn't %Lu\n",
cache->key.objectid);
error++;
}
path = btrfs_alloc_path();
if (!path) {
- fprintf(stderr, "Error allocing path\n");
+ fprintf(stderr, "Error allocating path\n");
return -ENOMEM;
}
/*
* Block group items come before extent items if they have the same
- * bytenr, so walk back one more just in case. Dear future traveler,
+ * bytenr, so walk back one more just in case. Dear future traveller,
* first congrats on mastering time travel. Now if it's not too much
* trouble could you go back to 2006 and tell Chris to make the
* BLOCK_GROUP_ITEM_KEY (and BTRFS_*_REF_KEY) lower than the
* 1) If BTRFS_HEADER_FLAG_RELOC is set then we have FULL_BACKREF set.
* 2) If btrfs_header_owner(buf) no longer points to buf then we have
* FULL_BACKREF set.
- * 3) We cow'ed the block walking down a reloc tree. This is impossible to tell
+ * 3) We cowed the block walking down a reloc tree. This is impossible to tell
* if it happened after the relocation occurred since we'll have dropped the
* reloc root, so it's entirely possible to have FULL_BACKREF set on buf and
* have no real way to know for sure.
goto full_backref;
normal:
*flags = 0;
- if (rec->flag_block_full_backref != -1 &&
+ if (rec->flag_block_full_backref != FLAG_UNSET &&
rec->flag_block_full_backref != 0)
rec->bad_full_backref = 1;
return 0;
full_backref:
*flags |= BTRFS_BLOCK_FLAG_FULL_BACKREF;
- if (rec->flag_block_full_backref != -1 &&
+ if (rec->flag_block_full_backref != FLAG_UNSET &&
rec->flag_block_full_backref != 1)
rec->bad_full_backref = 1;
return 0;
btrfs_item_key_to_cpu(buf, &first_key, 0);
level = btrfs_header_level(buf);
for (i = 0; i < nritems; i++) {
+ struct extent_record tmpl;
+
ptr = btrfs_node_blockptr(buf, i);
size = root->nodesize;
btrfs_node_key_to_cpu(buf, &key, i);
continue;
}
}
- ret = add_extent_rec(extent_cache, &key,
- btrfs_node_ptr_generation(buf, i),
- ptr, size, 0, 0, 1, 0, 1, 0,
- size);
+
+ memset(&tmpl, 0, sizeof(tmpl));
+ btrfs_cpu_key_to_disk(&tmpl.parent_key, &key);
+ tmpl.parent_generation = btrfs_node_ptr_generation(buf, i);
+ tmpl.start = ptr;
+ tmpl.nr = size;
+ tmpl.refs = 1;
+ tmpl.metadata = 1;
+ tmpl.max_size = size;
+ ret = add_extent_rec(extent_cache, &tmpl);
BUG_ON(ret);
add_tree_backref(extent_cache, ptr, parent, owner, 1);
struct cache_tree *nodes,
u64 objectid)
{
+ struct extent_record tmpl;
+
if (btrfs_header_level(buf) > 0)
add_pending(nodes, seen, buf->start, buf->len);
else
add_pending(pending, seen, buf->start, buf->len);
- add_extent_rec(extent_cache, NULL, 0, buf->start, buf->len,
- 0, 1, 1, 0, 1, 0, buf->len);
+
+ memset(&tmpl, 0, sizeof(tmpl));
+ tmpl.start = buf->start;
+ tmpl.nr = buf->len;
+ tmpl.is_root = 1;
+ tmpl.refs = 1;
+ tmpl.metadata = 1;
+ tmpl.max_size = buf->len;
+ add_extent_rec(extent_cache, &tmpl);
if (objectid == BTRFS_TREE_RELOC_OBJECTID ||
btrfs_header_backref_rev(buf) < BTRFS_MIXED_BACKREF_REV)
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);
}
}
} else {
struct btrfs_disk_key copy_key;;
- tback = (struct tree_backref *)back;
+ tback = to_tree_backref(back);
bi = (struct btrfs_tree_block_info *)(ei + 1);
memset_extent_buffer(leaf, 0, (unsigned long)bi,
sizeof(*bi));
u64 parent;
int i;
- dback = (struct data_backref *)back;
+ dback = to_data_backref(back);
if (back->full_backref)
parent = dback->parent;
else
} else {
u64 parent;
- tback = (struct tree_backref *)back;
+ tback = to_tree_backref(back);
if (back->full_backref)
parent = tback->parent;
else
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;
- dback = (struct data_backref *)back;
+ dback = to_data_backref(back);
/*
* We only pay attention to backrefs that we found a real
* 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;
- dback = (struct data_backref *)back;
+ dback = to_data_backref(back);
/*
* Still ignoring backrefs that don't have a real ref attached
*/
remove_cache_extent(extent_cache, &rec->cache);
- good = list_entry(rec->dups.next, struct extent_record, list);
+ good = to_extent_record(rec->dups.next);
list_del_init(&good->list);
INIT_LIST_HEAD(&good->backrefs);
INIT_LIST_HEAD(&good->dups);
if (tmp->start + tmp->nr < good->start + good->nr) {
fprintf(stderr, "Ok we have overlapping extents that "
- "aren't completely covered by eachother, this "
+ "aren't completely covered by each other, this "
"is going to require more careful thought. "
"The extents are [%Lu-%Lu] and [%Lu-%Lu]\n",
tmp->start, tmp->nr, good->start, good->nr);
ret = err;
out:
while (!list_empty(&delete_list)) {
- tmp = list_entry(delete_list.next, struct extent_record, list);
+ tmp = to_extent_record(delete_list.next);
list_del_init(&tmp->list);
if (tmp == rec)
continue;
}
while (!list_empty(&rec->dups)) {
- tmp = list_entry(rec->dups.next, struct extent_record, list);
+ tmp = to_extent_record(rec->dups.next);
list_del_init(&tmp->list);
free(tmp);
}
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;
- dback = (struct data_backref *)back;
+ dback = to_data_backref(back);
/* We found this one, we don't need to do a lookup */
if (dback->found_ref)
{
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;
- dback = (struct data_backref *)back;
+ dback = to_data_backref(back);
if (dback->found_ref)
continue;
key.objectid = dback->root;
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 = list_entry(cur, struct extent_backref, list);
- 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
* belong to a different extent item and not the weird duplicate one.
*/
while (repair && !list_empty(&duplicate_extents)) {
- rec = list_entry(duplicate_extents.next, struct extent_record,
- list);
+ rec = to_extent_record(duplicate_extents.next);
list_del_init(&rec->list);
/* Sometimes we can find a backref before we find an actual
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;
+}
+
static int btrfs_fsck_reinit_root(struct btrfs_trans_handle *trans,
struct btrfs_root *root, int overwrite)
{
ret = reset_balance(trans, fs_info);
if (ret)
- fprintf(stderr, "error reseting the pending balance\n");
+ fprintf(stderr, "error resetting the pending balance\n");
return ret;
}
const char * const cmd_check_usage[] = {
"btrfs check [options] <device>",
- "Check structural inegrity of a filesystem (unmounted).",
- "Check structural inegrity of an unmounted filesystem. Verify internal",
+ "Check structural integrity of a filesystem (unmounted).",
+ "Check structural integrity of an unmounted filesystem. Verify internal",
"trees' consistency and item connectivity. In the repair mode try to",
"fix the problems found.",
"WARNING: the repair mode is considered dangerous",
"--readonly run in read-only mode (default)",
"--init-csum-tree create a new CRC tree",
"--init-extent-tree create a new extent tree",
- "--check-data-csum verify checkums of data blocks",
+ "--check-data-csum verify checksums of data blocks",
"-Q|--qgroup-report print a report on qgroup consistency",
"-E|--subvol-extents <subvolid>",
" print subvolume extents and sharing state",
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)
- print_qgroup_report(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)) {
ret = 1;
}
out:
- print_qgroup_report(0);
+ /* Don't override original ret */
+ 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
(unsigned long long)data_bytes_allocated,
(unsigned long long)data_bytes_referenced);
+ free_qgroup_counts();
free_root_recs_tree(&root_cache);
close_out:
close_ctree(root);