Revert "btrfs-progs: check: switch to iterating over the backref_tree"

This reverts commit bbebe814c0e335745cfa773df966418e754b50e3.

1 files 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