static enum btrfs_check_mode check_mode = CHECK_MODE_DEFAULT;
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->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->bytes > back2->bytes)
+ return 1;
+ if (back1->bytes < back2->bytes)
+ 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;
return ret;
}
+static struct tree_backref *find_tree_backref(struct extent_record *rec,
+ u64 parent, u64 root)
+{
+ struct rb_node *node;
+ struct tree_backref *back = NULL;
+ struct tree_backref match = {
+ .node = {
+ .is_data = 0,
+ },
+ };
+
+ if (parent) {
+ match.parent = parent;
+ match.node.full_backref = 1;
+ } else {
+ match.root = root;
+ }
+
+ 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 data_backref *find_data_backref(struct extent_record *rec,
+ u64 parent, u64 root,
+ u64 owner, u64 offset,
+ int found_ref,
+ u64 disk_bytenr, u64 bytes)
+{
+ 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,
+ };
+
+ if (parent) {
+ match.parent = parent;
+ match.node.full_backref = 1;
+ } else {
+ match.root = root;
+ }
+
+ 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;
+}
/*
* Iterate all item on the tree and call check_inode_item() to check.
*
static int all_backpointers_checked(struct extent_record *rec, int print_errs)
{
- struct list_head *cur = rec->backrefs.next;
- struct extent_backref *back;
+ struct extent_backref *back, *tmp;
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;
+ rbtree_postorder_for_each_entry_safe(back, tmp,
+ &rec->backref_tree, node) {
if (!back->found_extent_tree) {
err = 1;
if (!print_errs)
goto out;
if (back->is_data) {
dback = to_data_backref(back);
- fprintf(stderr, "Backref %llu %s %llu"
+ fprintf(stderr, "Data backref %llu %s %llu"
" owner %llu offset %llu num_refs %lu"
" not found in extent tree\n",
(unsigned long long)rec->start,
(unsigned long)dback->num_refs);
} else {
tback = to_tree_backref(back);
- fprintf(stderr, "Backref %llu parent %llu"
+ fprintf(stderr, "Tree backref %llu parent %llu"
" root %llu not found in extent tree\n",
(unsigned long long)rec->start,
(unsigned long long)tback->parent,
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 cache_tree *extent_cache)
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 *node, *tmp;
struct tree_backref *back;
int is_extent = 0;
- while(cur != &rec->backrefs) {
- node = to_extent_backref(cur);
- cur = cur->next;
+ rbtree_postorder_for_each_entry_safe(node, tmp,
+ &rec->backref_tree, node) {
if (node->is_data)
return 0;
back = to_tree_backref(node);
return ret;
}
+#if 0
static struct tree_backref *find_tree_backref(struct extent_record *rec,
u64 parent, u64 root)
{
}
return NULL;
}
+#endif
static struct tree_backref *alloc_tree_backref(struct extent_record *rec,
u64 parent, u64 root)
ref->root = root;
ref->node.full_backref = 0;
}
- list_add_tail(&ref->node.list, &rec->backrefs);
return ref;
}
+#if 0
static struct data_backref *find_data_backref(struct extent_record *rec,
u64 parent, u64 root,
u64 owner, u64 offset,
}
return NULL;
}
+#endif
static struct data_backref *alloc_data_backref(struct extent_record *rec,
u64 parent, u64 root,
ref->bytes = max_size;
ref->found_ref = 0;
ref->num_refs = 0;
- list_add_tail(&ref->node.list, &rec->backrefs);
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;
struct tree_backref *back;
struct cache_extent *cache;
int ret;
+ bool insert = false;
cache = lookup_cache_extent(extent_cache, bytenr, 1);
if (!cache) {
back = alloc_tree_backref(rec, parent, root);
if (!back)
return -ENOMEM;
+ insert = true;
}
if (found_ref) {
}
back->node.found_extent_tree = 1;
}
+ if (insert)
+ WARN_ON(rb_insert(&rec->backref_tree, &back->node.node,
+ compare_extent_backref));
check_extent_type(rec);
maybe_free_extent_rec(extent_cache, rec);
return 0;
struct data_backref *back;
struct cache_extent *cache;
int ret;
+ bool insert = false;
cache = lookup_cache_extent(extent_cache, bytenr, 1);
if (!cache) {
back = alloc_data_backref(rec, parent, root, owner, offset,
max_size);
BUG_ON(!back);
+ insert = true;
}
if (found_ref) {
BUG_ON(back->bytes != max_size);
back->node.found_ref = 1;
back->found_ref += 1;
- back->bytes = max_size;
- back->disk_bytenr = bytenr;
+ if (back->bytes != max_size || back->disk_bytenr != bytenr) {
+ back->bytes = max_size;
+ back->disk_bytenr = bytenr;
+
+ /* Need to reinsert if not already in the tree */
+ if (!insert) {
+ rb_erase(&back->node.node, &rec->backref_tree);
+ insert = true;
+ }
+ }
rec->refs += 1;
rec->content_checked = 1;
rec->owner_ref_checked = 1;
back->num_refs = num_refs;
back->node.found_extent_tree = 1;
}
+ if (insert)
+ WARN_ON(rb_insert(&rec->backref_tree, &back->node.node,
+ compare_extent_backref));
+
maybe_free_extent_rec(extent_cache, rec);
return 0;
}
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;
if (rec->metadata)
return 1;
btrfs_init_path(&path);
- 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
}
/*
- * Not supported yet
+ * experimental and dangerous
*/
- if (repair && check_mode == CHECK_MODE_LOWMEM) {
- error("low memory mode doesn't support repair yet");
- exit(1);
- }
+ if (repair && check_mode == CHECK_MODE_LOWMEM)
+ warning("low-memory mode repair support is only partial");
radix_tree_init();
cache_tree_init(&root_cache);
warning(
"filesystem mounted, continuing because of --force");
}
+ /* A block device is mounted in exclusive mode by kernel */
+ ctree_flags &= ~OPEN_CTREE_EXCLUSIVE;
}
/* only allow partial opening under repair mode */
projects / platform / upstream / btrfs-progs.git / blobdiff