[RFC PATCH 05/17] btrfs: priority alloc: introduce functions to add block group to priority tree

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

Introduce compute_priority_level() to compute priority level according
priority, now just divides PRIORITY_USAGE_FACOTR.

Introduce add_block_group_priority() to add block groups to
priority tree.

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

diff --git a/fs/btrfs/extent-tree.c b/fs/btrfs/extent-tree.c
index 787a68b5bdcb..d63078930a1e 100644
--- a/fs/btrfs/extent-tree.c
+++ b/fs/btrfs/extent-tree.c
@@ -11344,3 +11344,79 @@ static int create_priority_trees(struct btrfs_fs_info *fs_info,
 		remove_priority_trees(fs_info, space_info);
 	return ret;
 }
+
+static int link_block_group_priority(struct btrfs_priority_tree *tree,
+				     struct btrfs_block_group_cache *cache)
+{
+	struct rb_node **p = &tree->block_groups.rb_node;
+	struct rb_node *parent = NULL;
+	struct btrfs_block_group_cache *tmp;
+
+	while (*p) {
+		parent = *p;
+		tmp = rb_entry(parent, struct btrfs_block_group_cache, node);
+		if (cache->key.objectid < tmp->key.objectid)
+			p = &(*p)->rb_left;
+		else if (cache->key.objectid > tmp->key.objectid)
+			p = &(*p)->rb_right;
+		else
+			return -EEXIST;
+	}
+
+	rb_link_node(&cache->node, parent, p);
+	rb_insert_color(&cache->node, &tree->block_groups);
+	return 0;
+}
+
+static struct btrfs_priority_tree *
+search_priority_tree(struct rb_root *root, int level)
+{
+	struct rb_node *node = root->rb_node;
+	struct btrfs_priority_tree *pt;
+
+	while (node) {
+		pt = rb_entry(node, struct btrfs_priority_tree, node);
+
+		if (level > pt->level)
+			node = node->rb_left;
+		else if (level < pt->level)
+			node = node->rb_right;
+		else
+			return pt;
+	}
+
+	return NULL;
+}
+
+static void add_block_group_priority(struct btrfs_block_group_cache *cache)
+{
+	struct btrfs_priority_tree *pt;
+	int index = btrfs_bg_flags_to_raid_index(cache->flags);
+	int level, max_level, min_level;
+	int ret;
+
+	if (!is_priority_alloc_enabled(cache->fs_info))
+		return;
+
+	if (btrfs_test_opt(cache->fs_info, PRIORITY_USAGE)) {
+		max_level = compute_priority_level(cache->fs_info,
+					   (u8)100 << PRIORITY_USAGE_SHIFT);
+		min_level = 0;
+	}
+
+	level = compute_priority_level(cache->fs_info, cache->priority);
+	if (level > max_level || level < min_level) {
+		WARN_ON(level);
+		return;
+	}
+
+	pt = search_priority_tree(&cache->space_info->priority_trees[index],
+				  level);
+	BUG_ON(pt == NULL);
+
+	down_write(&pt->groups_sem);
+	cache->priority_tree = pt;
+	ret = link_block_group_priority(pt, cache);
+	up_write(&pt->groups_sem);
+	BUG_ON(ret);
+}
-- 
2.19.1