[04/19] btrfs: qgroup: Introduce function to insert non-overlap reserve range
diff mbox

Message ID 1441702920-21278-1-git-send-email-quwenruo@cn.fujitsu.com
State New
Headers show

Commit Message

Qu Wenruo Sept. 8, 2015, 9:01 a.m. UTC
New function insert_data_ranges() will insert non-overlap reserve ranges
into reserve map.

It provides the basis for later qgroup reserve map implement.

Signed-off-by: Qu Wenruo <quwenruo@cn.fujitsu.com>
---
 fs/btrfs/qgroup.c | 124 ++++++++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 124 insertions(+)

Comments

Tsutomu Itoh Sept. 9, 2015, 12:32 a.m. UTC | #1
Hi, Qu,

On 2015/09/08 18:01, Qu Wenruo wrote:
> New function insert_data_ranges() will insert non-overlap reserve ranges
> into reserve map.
> 
> It provides the basis for later qgroup reserve map implement.
> 
> Signed-off-by: Qu Wenruo <quwenruo@cn.fujitsu.com>
> ---
>   fs/btrfs/qgroup.c | 124 ++++++++++++++++++++++++++++++++++++++++++++++++++++++
>   1 file changed, 124 insertions(+)
> 
> diff --git a/fs/btrfs/qgroup.c b/fs/btrfs/qgroup.c
> index fc24fc3..a4e3af4 100644
> --- a/fs/btrfs/qgroup.c
> +++ b/fs/btrfs/qgroup.c
> @@ -2577,6 +2577,130 @@ find_reserve_range(struct btrfs_qgroup_data_rsv_map *map, u64 start)
>   }
>   
>   /*
> + * Insert one data range

> + * [start,len) here won't overflap with each other.

                             overlap

Thanks,
Tsutomu

> + *
> + * Return 0 if range is inserted and tmp is not used.
> + * Return > 0 if range is inserted and tmp is used.
> + * No catchable error case. Only possible error will cause BUG_ON() as
> + * that's logical error.
> + */
> +static int insert_data_range(struct btrfs_qgroup_data_rsv_map *map,
> +			     struct data_rsv_range *tmp,
> +			     u64 start, u64 len)
> +{
> +	struct rb_node **p = &map->root.rb_node;
> +	struct rb_node *parent = NULL;
> +	struct rb_node *tmp_node = NULL;
> +	struct data_rsv_range *range = NULL;
> +	struct data_rsv_range *prev_range = NULL;
> +	struct data_rsv_range *next_range = NULL;
> +	int prev_merged = 0;
> +	int next_merged = 0;
> +	int ret = 0;
> +
> +	while (*p) {
> +		parent = *p;
> +		range = rb_entry(parent, struct data_rsv_range, node);
> +		if (range->start < start)
> +			p = &(*p)->rb_right;
> +		else if (range->start > start)
> +			p = &(*p)->rb_left;
> +		else
> +			BUG_ON(1);
> +	}
> +
> +	/* Empty tree, goto isolated case */
> +	if (!range)
> +		goto insert_isolated;
> +
> +	/* get adjusted ranges */
> +	if (range->start < start) {
> +		prev_range = range;
> +		tmp_node = rb_next(parent);
> +		if (tmp)
> +			next_range = rb_entry(tmp_node, struct data_rsv_range,
> +					      node);
> +	} else {
> +		next_range = range;
> +		tmp_node = rb_prev(parent);
> +		if (tmp)
> +			prev_range = rb_entry(tmp_node, struct data_rsv_range,
> +					      node);
> +	}
> +
> +	/* try to merge with previous and next ranges */
> +	if (prev_range && prev_range->start + prev_range->len == start) {
> +		prev_merged = 1;
> +		prev_range->len += len;
> +	}
> +	if (next_range && start + len == next_range->start) {
> +		next_merged = 1;
> +
> +		/*
> +		 * the range can be merged with adjusted two ranges into one,
> +		 * remove the tailing range.
> +		 */
> +		if (prev_merged) {
> +			prev_range->len += next_range->len;
> +			rb_erase(&next_range->node, &map->root);
> +			kfree(next_range);
> +		} else {
> +			next_range->start = start;
> +			next_range->len += len;
> +		}
> +	}
> +
> +insert_isolated:
> +	/* isolated case, need to insert range now */
> +	if (!next_merged && !prev_merged) {
> +		BUG_ON(!tmp);
> +
> +		tmp->start = start;
> +		tmp->len = len;
> +		rb_link_node(&tmp->node, parent, p);
> +		rb_insert_color(&tmp->node, &map->root);
> +		ret = 1;
> +	}
> +	return ret;
> +}
> +
> +/*
> + * insert reserve range and merge them if possible
> + *
> + * Return 0 if all inserted and tmp not used
> + * Return > 0 if all inserted and tmp used
> + * No catchable error return value.
> + */
> +static int insert_data_ranges(struct btrfs_qgroup_data_rsv_map *map,
> +			      struct data_rsv_range *tmp,
> +			      struct ulist *insert_list)
> +{
> +	struct ulist_node *unode;
> +	struct ulist_iterator uiter;
> +	int tmp_used = 0;
> +	int ret = 0;
> +
> +	ULIST_ITER_INIT(&uiter);
> +	while ((unode = ulist_next(insert_list, &uiter))) {
> +		ret = insert_data_range(map, tmp, unode->val, unode->aux);
> +
> +		/*
> +		 * insert_data_range() won't return error return value,
> +		 * no need to hanle <0 case.
> +		 *
> +		 * Also tmp should be used at most one time, so clear it to
> +		 * NULL to cooperate with sanity check in insert_data_range().
> +		 */
> +		if (ret > 0) {
> +			tmp_used = 1;
> +			tmp = NULL;
> +		}
> +	}
> +	return tmp_used;
> +}
> +
> +/*
>    * Init data_rsv_map for a given inode.
>    *
>    * This is needed at write time as quota can be disabled and then enabled
> 


--
To unsubscribe from this list: send the line "unsubscribe linux-btrfs" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html

Patch
diff mbox

diff --git a/fs/btrfs/qgroup.c b/fs/btrfs/qgroup.c
index fc24fc3..a4e3af4 100644
--- a/fs/btrfs/qgroup.c
+++ b/fs/btrfs/qgroup.c
@@ -2577,6 +2577,130 @@  find_reserve_range(struct btrfs_qgroup_data_rsv_map *map, u64 start)
 }
 
 /*
+ * Insert one data range
+ * [start,len) here won't overflap with each other.
+ *
+ * Return 0 if range is inserted and tmp is not used.
+ * Return > 0 if range is inserted and tmp is used.
+ * No catchable error case. Only possible error will cause BUG_ON() as
+ * that's logical error.
+ */
+static int insert_data_range(struct btrfs_qgroup_data_rsv_map *map,
+			     struct data_rsv_range *tmp,
+			     u64 start, u64 len)
+{
+	struct rb_node **p = &map->root.rb_node;
+	struct rb_node *parent = NULL;
+	struct rb_node *tmp_node = NULL;
+	struct data_rsv_range *range = NULL;
+	struct data_rsv_range *prev_range = NULL;
+	struct data_rsv_range *next_range = NULL;
+	int prev_merged = 0;
+	int next_merged = 0;
+	int ret = 0;
+
+	while (*p) {
+		parent = *p;
+		range = rb_entry(parent, struct data_rsv_range, node);
+		if (range->start < start)
+			p = &(*p)->rb_right;
+		else if (range->start > start)
+			p = &(*p)->rb_left;
+		else
+			BUG_ON(1);
+	}
+
+	/* Empty tree, goto isolated case */
+	if (!range)
+		goto insert_isolated;
+
+	/* get adjusted ranges */
+	if (range->start < start) {
+		prev_range = range;
+		tmp_node = rb_next(parent);
+		if (tmp)
+			next_range = rb_entry(tmp_node, struct data_rsv_range,
+					      node);
+	} else {
+		next_range = range;
+		tmp_node = rb_prev(parent);
+		if (tmp)
+			prev_range = rb_entry(tmp_node, struct data_rsv_range,
+					      node);
+	}
+
+	/* try to merge with previous and next ranges */
+	if (prev_range && prev_range->start + prev_range->len == start) {
+		prev_merged = 1;
+		prev_range->len += len;
+	}
+	if (next_range && start + len == next_range->start) {
+		next_merged = 1;
+
+		/*
+		 * the range can be merged with adjusted two ranges into one,
+		 * remove the tailing range.
+		 */
+		if (prev_merged) {
+			prev_range->len += next_range->len;
+			rb_erase(&next_range->node, &map->root);
+			kfree(next_range);
+		} else {
+			next_range->start = start;
+			next_range->len += len;
+		}
+	}
+
+insert_isolated:
+	/* isolated case, need to insert range now */
+	if (!next_merged && !prev_merged) {
+		BUG_ON(!tmp);
+
+		tmp->start = start;
+		tmp->len = len;
+		rb_link_node(&tmp->node, parent, p);
+		rb_insert_color(&tmp->node, &map->root);
+		ret = 1;
+	}
+	return ret;
+}
+
+/*
+ * insert reserve range and merge them if possible
+ *
+ * Return 0 if all inserted and tmp not used
+ * Return > 0 if all inserted and tmp used
+ * No catchable error return value.
+ */
+static int insert_data_ranges(struct btrfs_qgroup_data_rsv_map *map,
+			      struct data_rsv_range *tmp,
+			      struct ulist *insert_list)
+{
+	struct ulist_node *unode;
+	struct ulist_iterator uiter;
+	int tmp_used = 0;
+	int ret = 0;
+
+	ULIST_ITER_INIT(&uiter);
+	while ((unode = ulist_next(insert_list, &uiter))) {
+		ret = insert_data_range(map, tmp, unode->val, unode->aux);
+
+		/*
+		 * insert_data_range() won't return error return value,
+		 * no need to hanle <0 case.
+		 *
+		 * Also tmp should be used at most one time, so clear it to
+		 * NULL to cooperate with sanity check in insert_data_range().
+		 */
+		if (ret > 0) {
+			tmp_used = 1;
+			tmp = NULL;
+		}
+	}
+	return tmp_used;
+}
+
+/*
  * Init data_rsv_map for a given inode.
  *
  * This is needed at write time as quota can be disabled and then enabled