[RFC PATCH 12/17] btrfs: priority alloc: introduce find_free_extent_search()

[Su Yue <suy.fnst@cn.fujitsu.com>]

In origin, find_free_extent() just searches block groups in space_info
one by one.

In priority aware allocator, we first search block groups in
higher priority tree than in lower priority tree.

This helper unify above two ways for further use.

Signed-off-by: Su Yue <suy.fnst@cn.fujitsu.com>
---
 fs/btrfs/extent-tree.c | 77 ++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 77 insertions(+)

diff --git a/fs/btrfs/extent-tree.c b/fs/btrfs/extent-tree.c
index 74955f79fcce..5484256169dd 100644
--- a/fs/btrfs/extent-tree.c
+++ b/fs/btrfs/extent-tree.c
@@ -7331,6 +7331,83 @@ struct find_free_extent_ctl {
 };
 
 
+/*
+ * Helper function for find_free_extent().
+ *
+ * Return next block_group_cache to use.
+ * Return NULL mean no more block group to use.
+ *
+ * If use_priority is false: return the next of @block_group in
+ * space_info->block_groups[index] or if @blockgroup is NULL, return first
+ * block group in the list.
+ *
+ * If use_priority is true: if *pt_ret is NULL, return first block group in
+ * highest priority level. If *pt_ret is NOT NULL, return the next of
+ * @block_group or if @block_group is NULL, return first available block group
+ * which located in priority level <= *pt_ret->level.
+ * The tree will be down_read if return value is not NULL.
+ *
+ */
+static struct btrfs_block_group_cache *
+find_free_extent_search(struct btrfs_space_info *space_info, int index,
+		struct btrfs_block_group_cache *block_group, bool use_priority,
+		struct btrfs_priority_tree **pt_ret)
+{
+
+	struct list_head *lentry, *head;
+	struct rb_root *root;
+	struct rb_node *node, *bg_node;
+	struct btrfs_priority_tree *pt;
+	bool read;
+
+	if (!use_priority) {
+		head = &space_info->block_groups[index];
+		if (!block_group)
+			lentry = head->next;
+		else
+			lentry = block_group->list.next;
+		if (lentry == head)
+			return NULL;
+		return list_entry(lentry, struct btrfs_block_group_cache,
+				  list);
+	}
+
+	root = &space_info->priority_trees[index];
+	pt = pt_ret ? *pt_ret : NULL;
+
+	if (!pt) {
+		node = rb_first(root);
+		read = true;
+	} else {
+		node = &pt->node;
+		read = false;
+
+		if (block_group)
+			bg_node = rb_next(&block_group->node);
+		else
+			bg_node = rb_first(&pt->block_groups);
+	}
+
+	for (; node; node = rb_next(node)) {
+		pt = rb_entry(node, struct btrfs_priority_tree, node);
+		if (read) {
+			down_read(&pt->groups_sem);
+			bg_node = rb_first(&pt->block_groups);
+		}
+		for (; bg_node; bg_node = rb_next(bg_node)) {
+			if (bg_node) {
+				*pt_ret = pt;
+				return rb_entry(bg_node,
+					struct btrfs_block_group_cache, node);
+			}
+		}
+
+		up_read(&pt->groups_sem);
+		read = true;
+	}
+
+	return NULL;
+}
 /*
  * Helper function for find_free_extent().
  *
-- 
2.19.1