[linux-2.6-block.git] / fs / btrfs / free-space-cache.c

/*
 * Copyright (C) 2008 Red Hat.  All rights reserved.
 *
 * This program is free software; you can redistribute it and/or
 * modify it under the terms of the GNU General Public
 * License v2 as published by the Free Software Foundation.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
 * General Public License for more details.
 *
 * You should have received a copy of the GNU General Public
 * License along with this program; if not, write to the
 * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
 * Boston, MA 021110-1307, USA.
 */

#include <linux/sched.h>
#include "ctree.h"

static int tree_insert_offset(struct rb_root *root, u64 offset,
			      struct rb_node *node)
{
	struct rb_node **p = &root->rb_node;
	struct rb_node *parent = NULL;
	struct btrfs_free_space *info;

	while (*p) {
		parent = *p;
		info = rb_entry(parent, struct btrfs_free_space, offset_index);

		if (offset < info->offset)
			p = &(*p)->rb_left;
		else if (offset > info->offset)
			p = &(*p)->rb_right;
		else
			return -EEXIST;
	}

	rb_link_node(node, parent, p);
	rb_insert_color(node, root);

	return 0;
}

static int tree_insert_bytes(struct rb_root *root, u64 bytes,
			     struct rb_node *node)
{
	struct rb_node **p = &root->rb_node;
	struct rb_node *parent = NULL;
	struct btrfs_free_space *info;

	while (*p) {
		parent = *p;
		info = rb_entry(parent, struct btrfs_free_space, bytes_index);

		if (bytes < info->bytes)
			p = &(*p)->rb_left;
		else
			p = &(*p)->rb_right;
	}

	rb_link_node(node, parent, p);
	rb_insert_color(node, root);

	return 0;
}

/*
 * searches the tree for the given offset.  If contains is set we will return
 * the free space that contains the given offset.  If contains is not set we
 * will return the free space that starts at or after the given offset and is
 * at least bytes long.
 */
static struct btrfs_free_space *tree_search_offset(struct rb_root *root,
						   u64 offset, u64 bytes,
						   int contains)
{
	struct rb_node *n = root->rb_node;
	struct btrfs_free_space *entry, *ret = NULL;

	while (n) {
		entry = rb_entry(n, struct btrfs_free_space, offset_index);

		if (offset < entry->offset) {
			if (!contains &&
			    (!ret || entry->offset < ret->offset) &&
			    (bytes <= entry->bytes))
				ret = entry;
			n = n->rb_left;
		} else if (offset > entry->offset) {
			if ((entry->offset + entry->bytes - 1) >= offset &&
			    bytes <= entry->bytes) {
				ret = entry;
				break;
			}
			n = n->rb_right;
		} else {
			if (bytes > entry->bytes) {
				n = n->rb_right;
				continue;
			}
			ret = entry;
			break;
		}
	}

	return ret;
}

/*
 * return a chunk at least bytes size, as close to offset that we can get.
 */
static struct btrfs_free_space *tree_search_bytes(struct rb_root *root,
						  u64 offset, u64 bytes)
{
	struct rb_node *n = root->rb_node;
	struct btrfs_free_space *entry, *ret = NULL;

	while (n) {
		entry = rb_entry(n, struct btrfs_free_space, bytes_index);

		if (bytes < entry->bytes) {
			/*
			 * We prefer to get a hole size as close to the size we
			 * are asking for so we don't take small slivers out of
			 * huge holes, but we also want to get as close to the
			 * offset as possible so we don't have a whole lot of
			 * fragmentation.
			 */
			if (offset <= entry->offset) {
				if (!ret)
					ret = entry;
				else if (entry->bytes < ret->bytes)
					ret = entry;
				else if (entry->offset < ret->offset)
					ret = entry;
			}
			n = n->rb_left;
		} else if (bytes > entry->bytes) {
			n = n->rb_right;
		} else {
			/*
			 * Ok we may have multiple chunks of the wanted size,
			 * so we don't want to take the first one we find, we
			 * want to take the one closest to our given offset, so
			 * keep searching just in case theres a better match.
			 */
			n = n->rb_right;
			if (offset > entry->offset)
				continue;
			else if (!ret || entry->offset < ret->offset)
				ret = entry;
		}
	}

	return ret;
}

static void unlink_free_space(struct btrfs_block_group_cache *block_group,
			      struct btrfs_free_space *info)
{
	rb_erase(&info->offset_index, &block_group->free_space_offset);
	rb_erase(&info->bytes_index, &block_group->free_space_bytes);
}

static int link_free_space(struct btrfs_block_group_cache *block_group,
			   struct btrfs_free_space *info)
{
	int ret = 0;


	ret = tree_insert_offset(&block_group->free_space_offset, info->offset,
				 &info->offset_index);
	if (ret)
		return ret;

	ret = tree_insert_bytes(&block_group->free_space_bytes, info->bytes,
				&info->bytes_index);
	if (ret)
		return ret;

	return ret;
}

static int __btrfs_add_free_space(struct btrfs_block_group_cache *block_group,
				  u64 offset, u64 bytes)
{
	struct btrfs_free_space *right_info;
	struct btrfs_free_space *left_info;
	struct btrfs_free_space *info = NULL;
	struct btrfs_free_space *alloc_info;
	int ret = 0;

	alloc_info = kzalloc(sizeof(struct btrfs_free_space), GFP_NOFS);
	if (!alloc_info)
		return -ENOMEM;

	/*
	 * first we want to see if there is free space adjacent to the range we
	 * are adding, if there is remove that struct and add a new one to
	 * cover the entire range
	 */
	right_info = tree_search_offset(&block_group->free_space_offset,
					offset+bytes, 0, 1);
	left_info = tree_search_offset(&block_group->free_space_offset,
				       offset-1, 0, 1);

	if (right_info && right_info->offset == offset+bytes) {
		unlink_free_space(block_group, right_info);
		info = right_info;
		info->offset = offset;
		info->bytes += bytes;
	} else if (right_info && right_info->offset != offset+bytes) {
		printk(KERN_ERR "btrfs adding space in the middle of an "
		       "existing free space area. existing: "
		       "offset=%llu, bytes=%llu. new: offset=%llu, "
		       "bytes=%llu\n", (unsigned long long)right_info->offset,
		       (unsigned long long)right_info->bytes,
		       (unsigned long long)offset,
		       (unsigned long long)bytes);
		BUG();
	}

	if (left_info) {
		unlink_free_space(block_group, left_info);

		if (unlikely((left_info->offset + left_info->bytes) !=
			     offset)) {
			printk(KERN_ERR "btrfs free space to the left "
			       "of new free space isn't "
			       "quite right. existing: offset=%llu, "
			       "bytes=%llu. new: offset=%llu, bytes=%llu\n",
			       (unsigned long long)left_info->offset,
			       (unsigned long long)left_info->bytes,
			       (unsigned long long)offset,
			       (unsigned long long)bytes);
			BUG();
		}

		if (info) {
			info->offset = left_info->offset;
			info->bytes += left_info->bytes;
			kfree(left_info);
		} else {
			info = left_info;
			info->bytes += bytes;
		}
	}

	if (info) {
		ret = link_free_space(block_group, info);
		if (!ret)
			info = NULL;
		goto out;
	}

	info = alloc_info;
	alloc_info = NULL;
	info->offset = offset;
	info->bytes = bytes;

	ret = link_free_space(block_group, info);
	if (ret)
		kfree(info);
out:
	if (ret) {
		printk(KERN_ERR "btrfs: unable to add free space :%d\n", ret);
		if (ret == -EEXIST)
			BUG();
	}

	kfree(alloc_info);

	return ret;
}

static int
__btrfs_remove_free_space(struct btrfs_block_group_cache *block_group,
			  u64 offset, u64 bytes)
{
	struct btrfs_free_space *info;
	int ret = 0;

	info = tree_search_offset(&block_group->free_space_offset, offset, 0,
				  1);

	if (info && info->offset == offset) {
		if (info->bytes < bytes) {
			printk(KERN_ERR "Found free space at %llu, size %llu,"
			       "trying to use %llu\n",
			       (unsigned long long)info->offset,
			       (unsigned long long)info->bytes,
			       (unsigned long long)bytes);
			WARN_ON(1);
			ret = -EINVAL;
			goto out;
		}
		unlink_free_space(block_group, info);

		if (info->bytes == bytes) {
			kfree(info);
			goto out;
		}

		info->offset += bytes;
		info->bytes -= bytes;

		ret = link_free_space(block_group, info);
		BUG_ON(ret);
	} else if (info && info->offset < offset &&
		   info->offset + info->bytes >= offset + bytes) {
		u64 old_start = info->offset;
		/*
		 * we're freeing space in the middle of the info,
		 * this can happen during tree log replay
		 *
		 * first unlink the old info and then
		 * insert it again after the hole we're creating
		 */
		unlink_free_space(block_group, info);
		if (offset + bytes < info->offset + info->bytes) {
			u64 old_end = info->offset + info->bytes;

			info->offset = offset + bytes;
			info->bytes = old_end - info->offset;
			ret = link_free_space(block_group, info);
			BUG_ON(ret);
		} else {
			/* the hole we're creating ends at the end
			 * of the info struct, just free the info
			 */
			kfree(info);
		}

		/* step two, insert a new info struct to cover anything
		 * before the hole
		 */
		ret = __btrfs_add_free_space(block_group, old_start,
					     offset - old_start);
		BUG_ON(ret);
	} else {
		WARN_ON(1);
	}
out:
	return ret;
}

int btrfs_add_free_space(struct btrfs_block_group_cache *block_group,
			 u64 offset, u64 bytes)
{
	int ret;
	struct btrfs_free_space *sp;

	mutex_lock(&block_group->alloc_mutex);
	ret = __btrfs_add_free_space(block_group, offset, bytes);
	sp = tree_search_offset(&block_group->free_space_offset, offset, 0, 1);
	BUG_ON(!sp);
	mutex_unlock(&block_group->alloc_mutex);

	return ret;
}

int btrfs_add_free_space_lock(struct btrfs_block_group_cache *block_group,
			      u64 offset, u64 bytes)
{
	int ret;
	struct btrfs_free_space *sp;

	ret = __btrfs_add_free_space(block_group, offset, bytes);
	sp = tree_search_offset(&block_group->free_space_offset, offset, 0, 1);
	BUG_ON(!sp);

	return ret;
}

int btrfs_remove_free_space(struct btrfs_block_group_cache *block_group,
			    u64 offset, u64 bytes)
{
	int ret = 0;

	mutex_lock(&block_group->alloc_mutex);
	ret = __btrfs_remove_free_space(block_group, offset, bytes);
	mutex_unlock(&block_group->alloc_mutex);

	return ret;
}

int btrfs_remove_free_space_lock(struct btrfs_block_group_cache *block_group,
				 u64 offset, u64 bytes)
{
	int ret;

	ret = __btrfs_remove_free_space(block_group, offset, bytes);

	return ret;
}

void btrfs_dump_free_space(struct btrfs_block_group_cache *block_group,
			   u64 bytes)
{
	struct btrfs_free_space *info;
	struct rb_node *n;
	int count = 0;

	for (n = rb_first(&block_group->free_space_offset); n; n = rb_next(n)) {
		info = rb_entry(n, struct btrfs_free_space, offset_index);
		if (info->bytes >= bytes)
			count++;
	}
	printk(KERN_INFO "%d blocks of free space at or bigger than bytes is"
	       "\n", count);
}

u64 btrfs_block_group_free_space(struct btrfs_block_group_cache *block_group)
{
	struct btrfs_free_space *info;
	struct rb_node *n;
	u64 ret = 0;

	for (n = rb_first(&block_group->free_space_offset); n;
	     n = rb_next(n)) {
		info = rb_entry(n, struct btrfs_free_space, offset_index);
		ret += info->bytes;
	}

	return ret;
}

void btrfs_remove_free_space_cache(struct btrfs_block_group_cache *block_group)
{
	struct btrfs_free_space *info;
	struct rb_node *node;

	mutex_lock(&block_group->alloc_mutex);
	while ((node = rb_last(&block_group->free_space_bytes)) != NULL) {
		info = rb_entry(node, struct btrfs_free_space, bytes_index);
		unlink_free_space(block_group, info);
		kfree(info);
		if (need_resched()) {
			mutex_unlock(&block_group->alloc_mutex);
			cond_resched();
			mutex_lock(&block_group->alloc_mutex);
		}
	}
	mutex_unlock(&block_group->alloc_mutex);
}

#if 0
static struct btrfs_free_space *btrfs_find_free_space_offset(struct
						      btrfs_block_group_cache
						      *block_group, u64 offset,
						      u64 bytes)
{
	struct btrfs_free_space *ret;

	mutex_lock(&block_group->alloc_mutex);
	ret = tree_search_offset(&block_group->free_space_offset, offset,
				 bytes, 0);
	mutex_unlock(&block_group->alloc_mutex);

	return ret;
}

static struct btrfs_free_space *btrfs_find_free_space_bytes(struct
						     btrfs_block_group_cache
						     *block_group, u64 offset,
						     u64 bytes)
{
	struct btrfs_free_space *ret;

	mutex_lock(&block_group->alloc_mutex);

	ret = tree_search_bytes(&block_group->free_space_bytes, offset, bytes);
	mutex_unlock(&block_group->alloc_mutex);

	return ret;
}
#endif

struct btrfs_free_space *btrfs_find_free_space(struct btrfs_block_group_cache
					       *block_group, u64 offset,
					       u64 bytes)
{
	struct btrfs_free_space *ret = NULL;

	ret = tree_search_offset(&block_group->free_space_offset, offset,
				 bytes, 0);
	if (!ret)
		ret = tree_search_bytes(&block_group->free_space_bytes,
					offset, bytes);

	return ret;
}
Commit	Line	Data
0f9dd46c JB	1	/*
	2	* Copyright (C) 2008 Red Hat. All rights reserved.
	3	*
	4	* This program is free software; you can redistribute it and/or
	5	* modify it under the terms of the GNU General Public
	6	* License v2 as published by the Free Software Foundation.
	7	*
	8	* This program is distributed in the hope that it will be useful,
	9	* but WITHOUT ANY WARRANTY; without even the implied warranty of
	10	* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
	11	* General Public License for more details.
	12	*
	13	* You should have received a copy of the GNU General Public
	14	* License along with this program; if not, write to the
	15	* Free Software Foundation, Inc., 59 Temple Place - Suite 330,
	16	* Boston, MA 021110-1307, USA.
	17	*/
	18
	19	#include <linux/sched.h>
	20	#include "ctree.h"
	21
	22	static int tree_insert_offset(struct rb_root *root, u64 offset,
	23	struct rb_node *node)
	24	{
	25	struct rb_node **p = &root->rb_node;
	26	struct rb_node *parent = NULL;
	27	struct btrfs_free_space *info;
	28
	29	while (*p) {
	30	parent = *p;
	31	info = rb_entry(parent, struct btrfs_free_space, offset_index);
	32
	33	if (offset < info->offset)
	34	p = &(*p)->rb_left;
	35	else if (offset > info->offset)
	36	p = &(*p)->rb_right;
	37	else
	38	return -EEXIST;
	39	}
	40
	41	rb_link_node(node, parent, p);
	42	rb_insert_color(node, root);
	43
	44	return 0;
	45	}
	46
	47	static int tree_insert_bytes(struct rb_root *root, u64 bytes,
	48	struct rb_node *node)
	49	{
	50	struct rb_node **p = &root->rb_node;
	51	struct rb_node *parent = NULL;
	52	struct btrfs_free_space *info;
	53
	54	while (*p) {
	55	parent = *p;
	56	info = rb_entry(parent, struct btrfs_free_space, bytes_index);
	57
	58	if (bytes < info->bytes)
	59	p = &(*p)->rb_left;
	60	else
	61	p = &(*p)->rb_right;
	62	}
	63
	64	rb_link_node(node, parent, p);
65	rb_insert_color(node, root);
66
67	return 0;
68	}
69
70	/*
71	* searches the tree for the given offset. If contains is set we will return
72	* the free space that contains the given offset. If contains is not set we
73	* will return the free space that starts at or after the given offset and is
74	* at least bytes long.
75	*/
76	static struct btrfs_free_space tree_search_offset(struct rb_root root,
77	u64 offset, u64 bytes,
78	int contains)
79	{
80	struct rb_node *n = root->rb_node;
81	struct btrfs_free_space entry, ret = NULL;
82
83	while (n) {
84	entry = rb_entry(n, struct btrfs_free_space, offset_index);
85
86	if (offset < entry->offset) {
87	if (!contains &&
88	(!ret \|\| entry->offset < ret->offset) &&
89	(bytes <= entry->bytes))
90	ret = entry;
91	n = n->rb_left;
92	} else if (offset > entry->offset) {
37d3cddd JB	93	if ((entry->offset + entry->bytes - 1) >= offset &&
37d3cddd JB	94	bytes <= entry->bytes) {
0f9dd46c JB	95	ret = entry;
	96	break;
	97	}
	98	n = n->rb_right;
	99	} else {
	100	if (bytes > entry->bytes) {
	101	n = n->rb_right;
	102	continue;
	103	}
	104	ret = entry;
	105	break;
	106	}
	107	}
	108
	109	return ret;
	110	}
	111
	112	/*
	113	* return a chunk at least bytes size, as close to offset that we can get.
	114	*/
	115	static struct btrfs_free_space tree_search_bytes(struct rb_root root,
	116	u64 offset, u64 bytes)
	117	{
	118	struct rb_node *n = root->rb_node;
	119	struct btrfs_free_space entry, ret = NULL;
	120
	121	while (n) {
	122	entry = rb_entry(n, struct btrfs_free_space, bytes_index);
	123
	124	if (bytes < entry->bytes) {
	125	/*
	126	* We prefer to get a hole size as close to the size we
	127	* are asking for so we don't take small slivers out of
	128	* huge holes, but we also want to get as close to the
	129	* offset as possible so we don't have a whole lot of
	130	* fragmentation.
	131	*/
	132	if (offset <= entry->offset) {
	133	if (!ret)
	134	ret = entry;
	135	else if (entry->bytes < ret->bytes)
	136	ret = entry;
	137	else if (entry->offset < ret->offset)
	138	ret = entry;
	139	}
	140	n = n->rb_left;
	141	} else if (bytes > entry->bytes) {
	142	n = n->rb_right;
	143	} else {
	144	/*
	145	* Ok we may have multiple chunks of the wanted size,
	146	* so we don't want to take the first one we find, we
	147	* want to take the one closest to our given offset, so
	148	* keep searching just in case theres a better match.
	149	*/
	150	n = n->rb_right;
	151	if (offset > entry->offset)
	152	continue;
	153	else if (!ret \|\| entry->offset < ret->offset)
	154	ret = entry;
	155	}
	156	}
	157
	158	return ret;
159	}
160
161	static void unlink_free_space(struct btrfs_block_group_cache *block_group,
162	struct btrfs_free_space *info)
163	{
164	rb_erase(&info->offset_index, &block_group->free_space_offset);
165	rb_erase(&info->bytes_index, &block_group->free_space_bytes);
166	}
167
168	static int link_free_space(struct btrfs_block_group_cache *block_group,
169	struct btrfs_free_space *info)
170	{
171	int ret = 0;
172
173
174	ret = tree_insert_offset(&block_group->free_space_offset, info->offset,
175	&info->offset_index);
176	if (ret)
177	return ret;
178
179	ret = tree_insert_bytes(&block_group->free_space_bytes, info->bytes,
180	&info->bytes_index);
181	if (ret)
182	return ret;
183
184	return ret;
185	}
186
25179201 JB	187	static int __btrfs_add_free_space(struct btrfs_block_group_cache *block_group,
25179201 JB	188	u64 offset, u64 bytes)
0f9dd46c JB	189	{
	190	struct btrfs_free_space *right_info;
	191	struct btrfs_free_space *left_info;
	192	struct btrfs_free_space *info = NULL;
	193	struct btrfs_free_space *alloc_info;
	194	int ret = 0;
	195
	196	alloc_info = kzalloc(sizeof(struct btrfs_free_space), GFP_NOFS);
	197	if (!alloc_info)
	198	return -ENOMEM;
	199
	200	/*
	201	* first we want to see if there is free space adjacent to the range we
	202	* are adding, if there is remove that struct and add a new one to
	203	* cover the entire range
	204	*/
0f9dd46c JB	205	right_info = tree_search_offset(&block_group->free_space_offset,
	206	offset+bytes, 0, 1);
	207	left_info = tree_search_offset(&block_group->free_space_offset,
	208	offset-1, 0, 1);
	209
	210	if (right_info && right_info->offset == offset+bytes) {
	211	unlink_free_space(block_group, right_info);
	212	info = right_info;
	213	info->offset = offset;
	214	info->bytes += bytes;
	215	} else if (right_info && right_info->offset != offset+bytes) {
d397712b CM	216	printk(KERN_ERR "btrfs adding space in the middle of an "
	217	"existing free space area. existing: "
	218	"offset=%llu, bytes=%llu. new: offset=%llu, "
	219	"bytes=%llu\n", (unsigned long long)right_info->offset,
	220	(unsigned long long)right_info->bytes,
	221	(unsigned long long)offset,
	222	(unsigned long long)bytes);
0f9dd46c JB	223	BUG();
	224	}
	225
	226	if (left_info) {
	227	unlink_free_space(block_group, left_info);
	228
	229	if (unlikely((left_info->offset + left_info->bytes) !=
	230	offset)) {
d397712b CM	231	printk(KERN_ERR "btrfs free space to the left "
	232	"of new free space isn't "
	233	"quite right. existing: offset=%llu, "
	234	"bytes=%llu. new: offset=%llu, bytes=%llu\n",
	235	(unsigned long long)left_info->offset,
	236	(unsigned long long)left_info->bytes,
	237	(unsigned long long)offset,
	238	(unsigned long long)bytes);
0f9dd46c JB	239	BUG();
	240	}
	241
	242	if (info) {
	243	info->offset = left_info->offset;
	244	info->bytes += left_info->bytes;
	245	kfree(left_info);
	246	} else {
	247	info = left_info;
	248	info->bytes += bytes;
	249	}
	250	}
	251
	252	if (info) {
	253	ret = link_free_space(block_group, info);
	254	if (!ret)
	255	info = NULL;
	256	goto out;
	257	}
	258
	259	info = alloc_info;
	260	alloc_info = NULL;
	261	info->offset = offset;
	262	info->bytes = bytes;
	263
	264	ret = link_free_space(block_group, info);
	265	if (ret)
	266	kfree(info);
	267	out:
0f9dd46c JB	268	if (ret) {
	269	printk(KERN_ERR "btrfs: unable to add free space :%d\n", ret);
	270	if (ret == -EEXIST)
	271	BUG();
	272	}
	273
d397712b	274	kfree(alloc_info);
0f9dd46c JB	275
	276	return ret;
	277	}
	278
25179201 JB	279	static int
	280	__btrfs_remove_free_space(struct btrfs_block_group_cache *block_group,
	281	u64 offset, u64 bytes)
0f9dd46c JB	282	{
	283	struct btrfs_free_space *info;
	284	int ret = 0;
	285
0f9dd46c JB	286	info = tree_search_offset(&block_group->free_space_offset, offset, 0,
	287	1);
	288
	289	if (info && info->offset == offset) {
	290	if (info->bytes < bytes) {
d397712b CM	291	printk(KERN_ERR "Found free space at %llu, size %llu,"
	292	"trying to use %llu\n",
	293	(unsigned long long)info->offset,
	294	(unsigned long long)info->bytes,
	295	(unsigned long long)bytes);
0f9dd46c JB	296	WARN_ON(1);
	297	ret = -EINVAL;
	298	goto out;
	299	}
0f9dd46c JB	300	unlink_free_space(block_group, info);
	301
	302	if (info->bytes == bytes) {
	303	kfree(info);
	304	goto out;
	305	}
	306
	307	info->offset += bytes;
	308	info->bytes -= bytes;
	309
	310	ret = link_free_space(block_group, info);
	311	BUG_ON(ret);
9b49c9b9 CM	312	} else if (info && info->offset < offset &&
	313	info->offset + info->bytes >= offset + bytes) {
	314	u64 old_start = info->offset;
	315	/*
	316	* we're freeing space in the middle of the info,
	317	* this can happen during tree log replay
	318	*
	319	* first unlink the old info and then
	320	* insert it again after the hole we're creating
	321	*/
	322	unlink_free_space(block_group, info);
	323	if (offset + bytes < info->offset + info->bytes) {
	324	u64 old_end = info->offset + info->bytes;
	325
	326	info->offset = offset + bytes;
	327	info->bytes = old_end - info->offset;
	328	ret = link_free_space(block_group, info);
	329	BUG_ON(ret);
	330	} else {
	331	/* the hole we're creating ends at the end
	332	* of the info struct, just free the info
	333	*/
	334	kfree(info);
	335	}
	336
	337	/* step two, insert a new info struct to cover anything
	338	* before the hole
	339	*/
25179201 JB	340	ret = __btrfs_add_free_space(block_group, old_start,
25179201 JB	341	offset - old_start);
9b49c9b9	342	BUG_ON(ret);
0f9dd46c JB	343	} else {
	344	WARN_ON(1);
	345	}
	346	out:
25179201 JB	347	return ret;
	348	}
	349
	350	int btrfs_add_free_space(struct btrfs_block_group_cache *block_group,
	351	u64 offset, u64 bytes)
	352	{
	353	int ret;
	354	struct btrfs_free_space *sp;
	355
	356	mutex_lock(&block_group->alloc_mutex);
	357	ret = __btrfs_add_free_space(block_group, offset, bytes);
	358	sp = tree_search_offset(&block_group->free_space_offset, offset, 0, 1);
	359	BUG_ON(!sp);
	360	mutex_unlock(&block_group->alloc_mutex);
	361
	362	return ret;
	363	}
	364
	365	int btrfs_add_free_space_lock(struct btrfs_block_group_cache *block_group,
	366	u64 offset, u64 bytes)
	367	{
	368	int ret;
	369	struct btrfs_free_space *sp;
	370
	371	ret = __btrfs_add_free_space(block_group, offset, bytes);
	372	sp = tree_search_offset(&block_group->free_space_offset, offset, 0, 1);
	373	BUG_ON(!sp);
	374
	375	return ret;
	376	}
	377
	378	int btrfs_remove_free_space(struct btrfs_block_group_cache *block_group,
	379	u64 offset, u64 bytes)
	380	{
	381	int ret = 0;
	382
	383	mutex_lock(&block_group->alloc_mutex);
	384	ret = __btrfs_remove_free_space(block_group, offset, bytes);
	385	mutex_unlock(&block_group->alloc_mutex);
	386
	387	return ret;
	388	}
	389
	390	int btrfs_remove_free_space_lock(struct btrfs_block_group_cache *block_group,
	391	u64 offset, u64 bytes)
	392	{
	393	int ret;
	394
	395	ret = __btrfs_remove_free_space(block_group, offset, bytes);
	396
0f9dd46c JB	397	return ret;
	398	}
	399
	400	void btrfs_dump_free_space(struct btrfs_block_group_cache *block_group,
	401	u64 bytes)
	402	{
	403	struct btrfs_free_space *info;
	404	struct rb_node *n;
	405	int count = 0;
	406
	407	for (n = rb_first(&block_group->free_space_offset); n; n = rb_next(n)) {
	408	info = rb_entry(n, struct btrfs_free_space, offset_index);
	409	if (info->bytes >= bytes)
	410	count++;
0f9dd46c JB	411	}
	412	printk(KERN_INFO "%d blocks of free space at or bigger than bytes is"
	413	"\n", count);
	414	}
	415
	416	u64 btrfs_block_group_free_space(struct btrfs_block_group_cache *block_group)
	417	{
	418	struct btrfs_free_space *info;
	419	struct rb_node *n;
	420	u64 ret = 0;
	421
	422	for (n = rb_first(&block_group->free_space_offset); n;
	423	n = rb_next(n)) {
	424	info = rb_entry(n, struct btrfs_free_space, offset_index);
	425	ret += info->bytes;
	426	}
	427
	428	return ret;
	429	}
	430
	431	void btrfs_remove_free_space_cache(struct btrfs_block_group_cache *block_group)
	432	{
	433	struct btrfs_free_space *info;
	434	struct rb_node *node;
	435
25179201	436	mutex_lock(&block_group->alloc_mutex);
0f9dd46c JB	437	while ((node = rb_last(&block_group->free_space_bytes)) != NULL) {
	438	info = rb_entry(node, struct btrfs_free_space, bytes_index);
	439	unlink_free_space(block_group, info);
	440	kfree(info);
	441	if (need_resched()) {
25179201	442	mutex_unlock(&block_group->alloc_mutex);
0f9dd46c	443	cond_resched();
25179201	444	mutex_lock(&block_group->alloc_mutex);
0f9dd46c JB	445	}
0f9dd46c JB	446	}
25179201	447	mutex_unlock(&block_group->alloc_mutex);
0f9dd46c JB	448	}
0f9dd46c JB	449
b2950863 CH	450	#if 0
b2950863 CH	451	static struct btrfs_free_space *btrfs_find_free_space_offset(struct
0f9dd46c JB	452	btrfs_block_group_cache
	453	*block_group, u64 offset,
	454	u64 bytes)
	455	{
	456	struct btrfs_free_space *ret;
	457
25179201	458	mutex_lock(&block_group->alloc_mutex);
0f9dd46c JB	459	ret = tree_search_offset(&block_group->free_space_offset, offset,
0f9dd46c JB	460	bytes, 0);
25179201	461	mutex_unlock(&block_group->alloc_mutex);
0f9dd46c JB	462
	463	return ret;
	464	}
	465
b2950863	466	static struct btrfs_free_space *btrfs_find_free_space_bytes(struct
0f9dd46c JB	467	btrfs_block_group_cache
	468	*block_group, u64 offset,
	469	u64 bytes)
	470	{
	471	struct btrfs_free_space *ret;
	472
25179201	473	mutex_lock(&block_group->alloc_mutex);
0f9dd46c JB	474
0f9dd46c JB	475	ret = tree_search_bytes(&block_group->free_space_bytes, offset, bytes);
25179201	476	mutex_unlock(&block_group->alloc_mutex);
0f9dd46c JB	477
	478	return ret;
	479	}
b2950863	480	#endif
0f9dd46c JB	481
	482	struct btrfs_free_space *btrfs_find_free_space(struct btrfs_block_group_cache
	483	*block_group, u64 offset,
	484	u64 bytes)
	485	{
25179201	486	struct btrfs_free_space *ret = NULL;
0f9dd46c	487
0f9dd46c JB	488	ret = tree_search_offset(&block_group->free_space_offset, offset,
	489	bytes, 0);
	490	if (!ret)
	491	ret = tree_search_bytes(&block_group->free_space_bytes,
	492	offset, bytes);
	493
0f9dd46c JB	494	return ret;
0f9dd46c JB	495	}