From b1c0235e11c7bae27e7cf86f256c3cb650e63041 Mon Sep 17 00:00:00 2001 From: David Sterba Date: Mon, 5 Sep 2016 12:01:07 +0200 Subject: Revert "btrfs-progs: check: switch to iterating over the backref_tree" This reverts commit bbebe814c0e335745cfa773df966418e754b50e3. --- cmds-check.c | 88 +++++++++++++++++++++++++++++++++--------------------------- 1 file changed, 49 insertions(+), 39 deletions(-) diff --git a/cmds-check.c b/cmds-check.c index ef3e3a10..5a3efef9 100644 --- a/cmds-check.c +++ b/cmds-check.c @@ -84,6 +84,7 @@ enum btrfs_check_mode { 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; @@ -92,6 +93,11 @@ struct extent_backref { unsigned int broken:1; }; +static inline struct extent_backref* to_extent_backref(struct list_head *entry) +{ + return list_entry(entry, struct extent_backref, list); +} + static inline struct extent_backref* rb_node_to_extent_backref(struct rb_node *node) { return rb_entry(node, struct extent_backref, node); @@ -3930,15 +3936,16 @@ out: static int all_backpointers_checked(struct extent_record *rec, int print_errs) { - struct rb_node *n; + struct list_head *cur = rec->backrefs.next; struct extent_backref *back; struct tree_backref *tback; struct data_backref *dback; u64 found = 0; int err = 0; - for (n = rb_first(&rec->backref_tree); n; n = rb_next(n)) { - back = rb_node_to_extent_backref(n); + while(cur != &rec->backrefs) { + back = to_extent_backref(cur); + cur = cur->next; if (!back->found_extent_tree) { err = 1; if (!print_errs) @@ -4041,16 +4048,17 @@ out: return err; } -static void __free_one_backref(struct rb_node *node) -{ - struct extent_backref *back = rb_node_to_extent_backref(node); - - free(back); -} - -static void free_all_extent_backrefs(struct extent_record *rec) +static int free_all_extent_backrefs(struct extent_record *rec) { - rb_free_nodes(&rec->backref_tree, __free_one_backref); + 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; } static void free_extent_record_cache(struct btrfs_fs_info *fs_info, @@ -4090,7 +4098,7 @@ static int check_owner_ref(struct btrfs_root *root, struct extent_record *rec, struct extent_buffer *buf) { - struct extent_backref *node, *tmp; + struct extent_backref *node; struct tree_backref *back; struct btrfs_root *ref_root; struct btrfs_key key; @@ -4100,8 +4108,7 @@ static int check_owner_ref(struct btrfs_root *root, int found = 0; int ret; - rbtree_postorder_for_each_entry_safe(node, tmp, - &rec->backref_tree, node) { + list_for_each_entry(node, &rec->backrefs, list) { if (node->is_data) continue; if (!node->found_ref) @@ -4146,16 +4153,18 @@ static int check_owner_ref(struct btrfs_root *root, static int is_extent_tree_record(struct extent_record *rec) { - struct extent_backref *ref, *tmp; + struct list_head *cur = rec->backrefs.next; + struct extent_backref *node; struct tree_backref *back; int is_extent = 0; - rbtree_postorder_for_each_entry_safe(ref, tmp, - &rec->backref_tree, node) { - if (ref->is_data) + while(cur != &rec->backrefs) { + node = to_extent_backref(cur); + cur = cur->next; + if (node->is_data) return 0; - back = to_tree_backref(ref); - if (ref->full_backref) + back = to_tree_backref(node); + if (node->full_backref) return 0; if (back->root == BTRFS_EXTENT_TREE_OBJECTID) is_extent = 1; @@ -4571,6 +4580,7 @@ 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; @@ -4636,6 +4646,7 @@ 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; @@ -4669,12 +4680,12 @@ static void check_extent_type(struct extent_record *rec) * Check SYSTEM extent, as it's also marked as metadata, we can only * make sure it's a SYSTEM extent by its backref */ - if (!RB_EMPTY_ROOT(&rec->backref_tree)) { + if (!list_empty(&rec->backrefs)) { struct extent_backref *node; struct tree_backref *tback; u64 bg_type; - node = rb_node_to_extent_backref(rb_first(&rec->backref_tree)); + node = to_extent_backref(rec->backrefs.next); if (node->is_data) { /* tree block shouldn't have data backref */ rec->wrong_chunk_type = 1; @@ -6649,7 +6660,7 @@ static int free_extent_hook(struct btrfs_trans_handle *trans, back->node.found_extent_tree = 0; if (!back->node.found_extent_tree && back->node.found_ref) { - rb_erase(&back->node.node, &rec->backref_tree); + list_del(&back->node.list); free(back); } } else { @@ -6668,7 +6679,7 @@ static int free_extent_hook(struct btrfs_trans_handle *trans, back->node.found_extent_tree = 0; } if (!back->node.found_extent_tree && back->node.found_ref) { - rb_erase(&back->node.node, &rec->backref_tree); + list_del(&back->node.list); free(back); } } @@ -7105,7 +7116,7 @@ out: static int verify_backrefs(struct btrfs_fs_info *info, struct btrfs_path *path, struct extent_record *rec) { - struct extent_backref *back, *tmp; + struct extent_backref *back; struct data_backref *dback; struct extent_entry *entry, *best = NULL; LIST_HEAD(entries); @@ -7121,8 +7132,7 @@ static int verify_backrefs(struct btrfs_fs_info *info, struct btrfs_path *path, if (rec->metadata) return 0; - rbtree_postorder_for_each_entry_safe(back, tmp, - &rec->backref_tree, node) { + list_for_each_entry(back, &rec->backrefs, list) { if (back->full_backref || !back->is_data) continue; @@ -7248,8 +7258,7 @@ static int verify_backrefs(struct btrfs_fs_info *info, struct btrfs_path *path, * 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. */ - rbtree_postorder_for_each_entry_safe(back, tmp, - &rec->backref_tree, node) { + list_for_each_entry(back, &rec->backrefs, list) { if (back->full_backref || !back->is_data) continue; @@ -7478,7 +7487,7 @@ static int find_possible_backrefs(struct btrfs_fs_info *info, struct extent_record *rec) { struct btrfs_root *root; - struct extent_backref *back, *tmp; + struct extent_backref *back; struct data_backref *dback; struct cache_extent *cache; struct btrfs_file_extent_item *fi; @@ -7486,8 +7495,7 @@ static int find_possible_backrefs(struct btrfs_fs_info *info, u64 bytenr, bytes; int ret; - rbtree_postorder_for_each_entry_safe(back, tmp, - &rec->backref_tree, node) { + list_for_each_entry(back, &rec->backrefs, list) { /* Don't care about full backrefs (poor unloved backrefs) */ if (back->full_backref || !back->is_data) continue; @@ -7575,7 +7583,7 @@ static int record_orphan_data_extents(struct btrfs_fs_info *fs_info, { struct btrfs_key key; struct btrfs_root *dest_root; - struct extent_backref *back, *tmp; + struct extent_backref *back; struct data_backref *dback; struct orphan_data_extent *orphan; struct btrfs_path *path; @@ -7587,8 +7595,7 @@ static int record_orphan_data_extents(struct btrfs_fs_info *fs_info, path = btrfs_alloc_path(); if (!path) return -ENOMEM; - rbtree_postorder_for_each_entry_safe(back, tmp, - &rec->backref_tree, node) { + list_for_each_entry(back, &rec->backrefs, list) { if (back->full_backref || !back->is_data || !back->found_extent_tree) continue; @@ -7655,8 +7662,9 @@ static int fixup_extent_refs(struct btrfs_fs_info *info, 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, *tmp; + struct extent_backref *back; int allocated = 0; u64 flags = 0; @@ -7707,8 +7715,10 @@ static int fixup_extent_refs(struct btrfs_fs_info *info, } /* step three, recreate all the refs we did find */ - rbtree_postorder_for_each_entry_safe(back, tmp, - &rec->backref_tree, node) { + while(cur != &rec->backrefs) { + back = to_extent_backref(cur); + cur = cur->next; + /* * if we didn't find any references, don't create a * new extent record -- cgit v1.2.3