[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.
 *
 * fuzzy == 1: this is used for allocations where we are given a hint of where
 * to look for free space.  Because the hint may not be completely on an offset
 * mark, or the hint may no longer point to free space we need to fudge our
 * results a bit.  So we look for free space starting at or after offset with at
 * least bytes size.  We prefer to find as close to the given offset as we can.
 * Also if the offset is within a free space range, then we will return the free
 * space that contains the given offset, which means we can return a free space
 * chunk with an offset before the provided offset.
 *
 * fuzzy == 0: this is just a normal tree search.  Give us the free space that
 * starts at the given offset which is at least bytes size, and if its not there
 * return NULL.
 */
static struct btrfs_free_space *tree_search_offset(struct rb_root *root,
						   u64 offset, u64 bytes,
						   int fuzzy)
{
	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 (fuzzy &&
			    (!ret || entry->offset < ret->offset) &&
			    (bytes <= entry->bytes))
				ret = entry;
			n = n->rb_left;
		} else if (offset > entry->offset) {
			if (fuzzy &&
			    (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;
	int ret = 0;

	/*
	 * 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, 0);
	left_info = tree_search_offset(&block_group->free_space_offset,
				       offset-1, 0, 1);

	if (right_info) {
		unlink_free_space(block_group, right_info);
		info = right_info;
		info->offset = offset;
		info->bytes += bytes;
	}

	if (left_info && left_info->offset + left_info->bytes == offset) {
		unlink_free_space(block_group, left_info);

		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)
			kfree(info);
		goto out;
	}

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

	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();
	}

	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;

	BUG_ON(!block_group->cached);
	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 {
		if (!info) {
			printk(KERN_ERR "couldn't find space %llu to free\n",
			       (unsigned long long)offset);
			printk(KERN_ERR "cached is %d, offset %llu bytes %llu\n",
			       block_group->cached, block_group->key.objectid,
			       block_group->key.offset);
			btrfs_dump_free_space(block_group, bytes);
		} else if (info) {
			printk(KERN_ERR "hmm, found offset=%llu bytes=%llu, "
			       "but wanted offset=%llu bytes=%llu\n",
			       info->offset, info->bytes, offset, bytes);
		}
		WARN_ON(1);
	}
out:
	return ret;
}

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

	mutex_lock(&block_group->alloc_mutex);
	ret = __btrfs_add_free_space(block_group, offset, bytes);
	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;

	ret = __btrfs_add_free_space(block_group, offset, bytes);

	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_ERR "entry offset %llu, bytes %llu\n", info->offset,
		       info->bytes);
	}
	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, 1);
	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	/*
70cb0743 JB	71	* searches the tree for the given offset.
	72	*
	73	* fuzzy == 1: this is used for allocations where we are given a hint of where
	74	* to look for free space. Because the hint may not be completely on an offset
	75	* mark, or the hint may no longer point to free space we need to fudge our
	76	* results a bit. So we look for free space starting at or after offset with at
	77	* least bytes size. We prefer to find as close to the given offset as we can.
	78	* Also if the offset is within a free space range, then we will return the free
	79	* space that contains the given offset, which means we can return a free space
	80	* chunk with an offset before the provided offset.
	81	*
	82	* fuzzy == 0: this is just a normal tree search. Give us the free space that
	83	* starts at the given offset which is at least bytes size, and if its not there
	84	* return NULL.
0f9dd46c JB	85	*/
	86	static struct btrfs_free_space tree_search_offset(struct rb_root root,
	87	u64 offset, u64 bytes,
70cb0743	88	int fuzzy)
0f9dd46c JB	89	{
	90	struct rb_node *n = root->rb_node;
	91	struct btrfs_free_space entry, ret = NULL;
	92
	93	while (n) {
	94	entry = rb_entry(n, struct btrfs_free_space, offset_index);
	95
	96	if (offset < entry->offset) {
70cb0743	97	if (fuzzy &&
0f9dd46c JB	98	(!ret \|\| entry->offset < ret->offset) &&
	99	(bytes <= entry->bytes))
	100	ret = entry;
	101	n = n->rb_left;
	102	} else if (offset > entry->offset) {
70cb0743 JB	103	if (fuzzy &&
70cb0743 JB	104	(entry->offset + entry->bytes - 1) >= offset &&
37d3cddd	105	bytes <= entry->bytes) {
0f9dd46c JB	106	ret = entry;
	107	break;
	108	}
	109	n = n->rb_right;
	110	} else {
	111	if (bytes > entry->bytes) {
	112	n = n->rb_right;
	113	continue;
	114	}
	115	ret = entry;
	116	break;
	117	}
	118	}
	119
	120	return ret;
	121	}
	122
	123	/*
	124	* return a chunk at least bytes size, as close to offset that we can get.
	125	*/
	126	static struct btrfs_free_space tree_search_bytes(struct rb_root root,
	127	u64 offset, u64 bytes)
	128	{
	129	struct rb_node *n = root->rb_node;
	130	struct btrfs_free_space entry, ret = NULL;
	131
	132	while (n) {
	133	entry = rb_entry(n, struct btrfs_free_space, bytes_index);
	134
	135	if (bytes < entry->bytes) {
	136	/*
	137	* We prefer to get a hole size as close to the size we
	138	* are asking for so we don't take small slivers out of
	139	* huge holes, but we also want to get as close to the
	140	* offset as possible so we don't have a whole lot of
	141	* fragmentation.
	142	*/
	143	if (offset <= entry->offset) {
	144	if (!ret)
	145	ret = entry;
	146	else if (entry->bytes < ret->bytes)
	147	ret = entry;
	148	else if (entry->offset < ret->offset)
	149	ret = entry;
	150	}
	151	n = n->rb_left;
	152	} else if (bytes > entry->bytes) {
	153	n = n->rb_right;
	154	} else {
	155	/*
	156	* Ok we may have multiple chunks of the wanted size,
	157	* so we don't want to take the first one we find, we
	158	* want to take the one closest to our given offset, so
	159	* keep searching just in case theres a better match.
	160	*/
	161	n = n->rb_right;
	162	if (offset > entry->offset)
	163	continue;
	164	else if (!ret \|\| entry->offset < ret->offset)
	165	ret = entry;
	166	}
	167	}
	168
	169	return ret;
170	}
171
172	static void unlink_free_space(struct btrfs_block_group_cache *block_group,
173	struct btrfs_free_space *info)
174	{
175	rb_erase(&info->offset_index, &block_group->free_space_offset);
176	rb_erase(&info->bytes_index, &block_group->free_space_bytes);
177	}
178
179	static int link_free_space(struct btrfs_block_group_cache *block_group,
180	struct btrfs_free_space *info)
181	{
182	int ret = 0;
183
184
185	ret = tree_insert_offset(&block_group->free_space_offset, info->offset,
186	&info->offset_index);
187	if (ret)
188	return ret;
189
190	ret = tree_insert_bytes(&block_group->free_space_bytes, info->bytes,
191	&info->bytes_index);
192	if (ret)
193	return ret;
194
195	return ret;
196	}
197
25179201 JB	198	static int __btrfs_add_free_space(struct btrfs_block_group_cache *block_group,
25179201 JB	199	u64 offset, u64 bytes)
0f9dd46c JB	200	{
	201	struct btrfs_free_space *right_info;
	202	struct btrfs_free_space *left_info;
	203	struct btrfs_free_space *info = NULL;
0f9dd46c JB	204	int ret = 0;
0f9dd46c JB	205
0f9dd46c JB	206	/*
	207	* first we want to see if there is free space adjacent to the range we
	208	* are adding, if there is remove that struct and add a new one to
	209	* cover the entire range
	210	*/
0f9dd46c	211	right_info = tree_search_offset(&block_group->free_space_offset,
70cb0743	212	offset+bytes, 0, 0);
0f9dd46c JB	213	left_info = tree_search_offset(&block_group->free_space_offset,
	214	offset-1, 0, 1);
	215
70cb0743	216	if (right_info) {
0f9dd46c JB	217	unlink_free_space(block_group, right_info);
	218	info = right_info;
	219	info->offset = offset;
	220	info->bytes += bytes;
0f9dd46c JB	221	}
0f9dd46c JB	222
70cb0743	223	if (left_info && left_info->offset + left_info->bytes == offset) {
0f9dd46c JB	224	unlink_free_space(block_group, left_info);
0f9dd46c JB	225
0f9dd46c JB	226	if (info) {
	227	info->offset = left_info->offset;
	228	info->bytes += left_info->bytes;
	229	kfree(left_info);
	230	} else {
	231	info = left_info;
	232	info->bytes += bytes;
	233	}
	234	}
	235
	236	if (info) {
	237	ret = link_free_space(block_group, info);
70cb0743 JB	238	if (ret)
70cb0743 JB	239	kfree(info);
0f9dd46c JB	240	goto out;
	241	}
	242
70cb0743 JB	243	info = kzalloc(sizeof(struct btrfs_free_space), GFP_NOFS);
	244	if (!info)
	245	return -ENOMEM;
	246
0f9dd46c JB	247	info->offset = offset;
	248	info->bytes = bytes;
	249
	250	ret = link_free_space(block_group, info);
	251	if (ret)
	252	kfree(info);
	253	out:
0f9dd46c JB	254	if (ret) {
	255	printk(KERN_ERR "btrfs: unable to add free space :%d\n", ret);
	256	if (ret == -EEXIST)
	257	BUG();
	258	}
	259
0f9dd46c JB	260	return ret;
	261	}
	262
25179201 JB	263	static int
	264	__btrfs_remove_free_space(struct btrfs_block_group_cache *block_group,
	265	u64 offset, u64 bytes)
0f9dd46c JB	266	{
	267	struct btrfs_free_space *info;
	268	int ret = 0;
	269
70cb0743	270	BUG_ON(!block_group->cached);
0f9dd46c JB	271	info = tree_search_offset(&block_group->free_space_offset, offset, 0,
	272	1);
	273
	274	if (info && info->offset == offset) {
	275	if (info->bytes < bytes) {
d397712b CM	276	printk(KERN_ERR "Found free space at %llu, size %llu,"
	277	"trying to use %llu\n",
	278	(unsigned long long)info->offset,
	279	(unsigned long long)info->bytes,
	280	(unsigned long long)bytes);
0f9dd46c JB	281	WARN_ON(1);
	282	ret = -EINVAL;
	283	goto out;
	284	}
0f9dd46c JB	285	unlink_free_space(block_group, info);
	286
	287	if (info->bytes == bytes) {
	288	kfree(info);
	289	goto out;
	290	}
	291
	292	info->offset += bytes;
	293	info->bytes -= bytes;
	294
	295	ret = link_free_space(block_group, info);
	296	BUG_ON(ret);
9b49c9b9 CM	297	} else if (info && info->offset < offset &&
	298	info->offset + info->bytes >= offset + bytes) {
	299	u64 old_start = info->offset;
	300	/*
	301	* we're freeing space in the middle of the info,
	302	* this can happen during tree log replay
	303	*
	304	* first unlink the old info and then
	305	* insert it again after the hole we're creating
	306	*/
	307	unlink_free_space(block_group, info);
	308	if (offset + bytes < info->offset + info->bytes) {
	309	u64 old_end = info->offset + info->bytes;
	310
	311	info->offset = offset + bytes;
	312	info->bytes = old_end - info->offset;
	313	ret = link_free_space(block_group, info);
	314	BUG_ON(ret);
	315	} else {
	316	/* the hole we're creating ends at the end
	317	* of the info struct, just free the info
	318	*/
	319	kfree(info);
	320	}
	321
	322	/* step two, insert a new info struct to cover anything
	323	* before the hole
	324	*/
25179201 JB	325	ret = __btrfs_add_free_space(block_group, old_start,
25179201 JB	326	offset - old_start);
9b49c9b9	327	BUG_ON(ret);
0f9dd46c	328	} else {
70cb0743 JB	329	if (!info) {
	330	printk(KERN_ERR "couldn't find space %llu to free\n",
	331	(unsigned long long)offset);
	332	printk(KERN_ERR "cached is %d, offset %llu bytes %llu\n",
	333	block_group->cached, block_group->key.objectid,
	334	block_group->key.offset);
	335	btrfs_dump_free_space(block_group, bytes);
	336	} else if (info) {
	337	printk(KERN_ERR "hmm, found offset=%llu bytes=%llu, "
	338	"but wanted offset=%llu bytes=%llu\n",
	339	info->offset, info->bytes, offset, bytes);
	340	}
0f9dd46c JB	341	WARN_ON(1);
	342	}
	343	out:
25179201 JB	344	return ret;
	345	}
	346
	347	int btrfs_add_free_space(struct btrfs_block_group_cache *block_group,
	348	u64 offset, u64 bytes)
	349	{
	350	int ret;
25179201 JB	351
	352	mutex_lock(&block_group->alloc_mutex);
	353	ret = __btrfs_add_free_space(block_group, offset, bytes);
25179201 JB	354	mutex_unlock(&block_group->alloc_mutex);
	355
	356	return ret;
	357	}
	358
	359	int btrfs_add_free_space_lock(struct btrfs_block_group_cache *block_group,
	360	u64 offset, u64 bytes)
	361	{
	362	int ret;
25179201 JB	363
25179201 JB	364	ret = __btrfs_add_free_space(block_group, offset, bytes);
25179201 JB	365
	366	return ret;
	367	}
	368
	369	int btrfs_remove_free_space(struct btrfs_block_group_cache *block_group,
	370	u64 offset, u64 bytes)
	371	{
	372	int ret = 0;
	373
	374	mutex_lock(&block_group->alloc_mutex);
	375	ret = __btrfs_remove_free_space(block_group, offset, bytes);
	376	mutex_unlock(&block_group->alloc_mutex);
	377
	378	return ret;
	379	}
	380
	381	int btrfs_remove_free_space_lock(struct btrfs_block_group_cache *block_group,
	382	u64 offset, u64 bytes)
	383	{
	384	int ret;
	385
	386	ret = __btrfs_remove_free_space(block_group, offset, bytes);
	387
0f9dd46c JB	388	return ret;
	389	}
	390
	391	void btrfs_dump_free_space(struct btrfs_block_group_cache *block_group,
	392	u64 bytes)
	393	{
	394	struct btrfs_free_space *info;
	395	struct rb_node *n;
	396	int count = 0;
	397
	398	for (n = rb_first(&block_group->free_space_offset); n; n = rb_next(n)) {
	399	info = rb_entry(n, struct btrfs_free_space, offset_index);
	400	if (info->bytes >= bytes)
	401	count++;
70cb0743 JB	402	printk(KERN_ERR "entry offset %llu, bytes %llu\n", info->offset,
70cb0743 JB	403	info->bytes);
0f9dd46c JB	404	}
	405	printk(KERN_INFO "%d blocks of free space at or bigger than bytes is"
	406	"\n", count);
	407	}
	408
	409	u64 btrfs_block_group_free_space(struct btrfs_block_group_cache *block_group)
	410	{
	411	struct btrfs_free_space *info;
	412	struct rb_node *n;
	413	u64 ret = 0;
	414
	415	for (n = rb_first(&block_group->free_space_offset); n;
	416	n = rb_next(n)) {
	417	info = rb_entry(n, struct btrfs_free_space, offset_index);
	418	ret += info->bytes;
	419	}
	420
	421	return ret;
	422	}
	423
	424	void btrfs_remove_free_space_cache(struct btrfs_block_group_cache *block_group)
	425	{
	426	struct btrfs_free_space *info;
	427	struct rb_node *node;
	428
25179201	429	mutex_lock(&block_group->alloc_mutex);
0f9dd46c JB	430	while ((node = rb_last(&block_group->free_space_bytes)) != NULL) {
	431	info = rb_entry(node, struct btrfs_free_space, bytes_index);
	432	unlink_free_space(block_group, info);
	433	kfree(info);
	434	if (need_resched()) {
25179201	435	mutex_unlock(&block_group->alloc_mutex);
0f9dd46c	436	cond_resched();
25179201	437	mutex_lock(&block_group->alloc_mutex);
0f9dd46c JB	438	}
0f9dd46c JB	439	}
25179201	440	mutex_unlock(&block_group->alloc_mutex);
0f9dd46c JB	441	}
0f9dd46c JB	442
b2950863 CH	443	#if 0
b2950863 CH	444	static struct btrfs_free_space *btrfs_find_free_space_offset(struct
0f9dd46c JB	445	btrfs_block_group_cache
	446	*block_group, u64 offset,
	447	u64 bytes)
	448	{
	449	struct btrfs_free_space *ret;
	450
25179201	451	mutex_lock(&block_group->alloc_mutex);
0f9dd46c JB	452	ret = tree_search_offset(&block_group->free_space_offset, offset,
0f9dd46c JB	453	bytes, 0);
25179201	454	mutex_unlock(&block_group->alloc_mutex);
0f9dd46c JB	455
	456	return ret;
	457	}
	458
b2950863	459	static struct btrfs_free_space *btrfs_find_free_space_bytes(struct
0f9dd46c JB	460	btrfs_block_group_cache
	461	*block_group, u64 offset,
	462	u64 bytes)
	463	{
	464	struct btrfs_free_space *ret;
	465
25179201	466	mutex_lock(&block_group->alloc_mutex);
0f9dd46c JB	467
0f9dd46c JB	468	ret = tree_search_bytes(&block_group->free_space_bytes, offset, bytes);
25179201	469	mutex_unlock(&block_group->alloc_mutex);
0f9dd46c JB	470
	471	return ret;
	472	}
b2950863	473	#endif
0f9dd46c JB	474
	475	struct btrfs_free_space *btrfs_find_free_space(struct btrfs_block_group_cache
	476	*block_group, u64 offset,
	477	u64 bytes)
	478	{
25179201	479	struct btrfs_free_space *ret = NULL;
0f9dd46c	480
0f9dd46c	481	ret = tree_search_offset(&block_group->free_space_offset, offset,
70cb0743	482	bytes, 1);
0f9dd46c JB	483	if (!ret)
	484	ret = tree_search_bytes(&block_group->free_space_bytes,
	485	offset, bytes);
	486
0f9dd46c JB	487	return ret;
0f9dd46c JB	488	}