[RFC,12/17] btrfs: priority alloc: introduce find_free_extent_search()
diff mbox series

Message ID 20181128031148.357-13-suy.fnst@cn.fujitsu.com
State New
Headers show
Series
  • btrfs: implementation of priority aware allocator
Related show

Commit Message

Su Yue Nov. 28, 2018, 3:11 a.m. UTC
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(+)

Patch
diff mbox series

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().
  *