[GitHub/mt8127/android_kernel_alcatel_ttab.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 (contains &&
			    (entry->offset + entry->bytes - 1) >= offset) {
				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;
}

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
	 */
	spin_lock(&block_group->lock);

	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 "adding space in the middle of an existing "
		       "free space area. existing: offset=%Lu, bytes=%Lu. "
		       "new: offset=%Lu, bytes=%Lu\n", right_info->offset,
		       right_info->bytes, offset, bytes);
		BUG();
	}

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

		if (unlikely((left_info->offset + left_info->bytes) !=
			     offset)) {
			printk(KERN_ERR "free space to the left of new free "
			       "space isn't quite right. existing: offset=%Lu,"
			       " bytes=%Lu. new: offset=%Lu, bytes=%Lu\n",
			       left_info->offset, left_info->bytes, offset,
			       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:
	spin_unlock(&block_group->lock);
	if (ret) {
		printk(KERN_ERR "btrfs: unable to add free space :%d\n", ret);
		if (ret == -EEXIST)
			BUG();
	}

	if (alloc_info)
		kfree(alloc_info);

	return ret;
}

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

	spin_lock(&block_group->lock);
	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 %Lu, size %Lu,"
			       "trying to use %Lu\n",
			       info->offset, info->bytes, 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 {
		WARN_ON(1);
	}
out:
	spin_unlock(&block_group->lock);
	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 "offset=%Lu, bytes=%Lu\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;

	spin_lock(&block_group->lock);
	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()) {
			spin_unlock(&block_group->lock);
			cond_resched();
			spin_lock(&block_group->lock);
		}
	}
	spin_unlock(&block_group->lock);
}

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;

	spin_lock(&block_group->lock);
	ret = tree_search_offset(&block_group->free_space_offset, offset,
				 bytes, 0);
	spin_unlock(&block_group->lock);

	return ret;
}

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;

	spin_lock(&block_group->lock);

	ret = tree_search_bytes(&block_group->free_space_bytes, offset, bytes);
	spin_unlock(&block_group->lock);

	return ret;
}

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

	spin_lock(&block_group->lock);
	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);

	spin_unlock(&block_group->lock);

	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) {
93	if (contains &&
94	(entry->offset + entry->bytes - 1) >= offset) {
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
187	int btrfs_add_free_space(struct btrfs_block_group_cache *block_group,
188	u64 offset, u64 bytes)
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	*/
205	spin_lock(&block_group->lock);
206
207	right_info = tree_search_offset(&block_group->free_space_offset,
208	offset+bytes, 0, 1);
209	left_info = tree_search_offset(&block_group->free_space_offset,
210	offset-1, 0, 1);
211
212	if (right_info && right_info->offset == offset+bytes) {
213	unlink_free_space(block_group, right_info);
214	info = right_info;
215	info->offset = offset;
216	info->bytes += bytes;
217	} else if (right_info && right_info->offset != offset+bytes) {
218	printk(KERN_ERR "adding space in the middle of an existing "
219	"free space area. existing: offset=%Lu, bytes=%Lu. "
220	"new: offset=%Lu, bytes=%Lu\n", right_info->offset,
221	right_info->bytes, offset, bytes);
222	BUG();
223	}
224
225	if (left_info) {
226	unlink_free_space(block_group, left_info);
227
228	if (unlikely((left_info->offset + left_info->bytes) !=
229	offset)) {
230	printk(KERN_ERR "free space to the left of new free "
231	"space isn't quite right. existing: offset=%Lu,"
232	" bytes=%Lu. new: offset=%Lu, bytes=%Lu\n",
233	left_info->offset, left_info->bytes, offset,
234	bytes);
235	BUG();
236	}
237
238	if (info) {
239	info->offset = left_info->offset;
240	info->bytes += left_info->bytes;
241	kfree(left_info);
242	} else {
243	info = left_info;
244	info->bytes += bytes;
245	}
246	}
247
248	if (info) {
249	ret = link_free_space(block_group, info);
250	if (!ret)
251	info = NULL;
252	goto out;
253	}
254
255	info = alloc_info;
256	alloc_info = NULL;
257	info->offset = offset;
258	info->bytes = bytes;
259
260	ret = link_free_space(block_group, info);
261	if (ret)
262	kfree(info);
263	out:
264	spin_unlock(&block_group->lock);
265	if (ret) {
266	printk(KERN_ERR "btrfs: unable to add free space :%d\n", ret);
267	if (ret == -EEXIST)
268	BUG();
269	}
270
271	if (alloc_info)
272	kfree(alloc_info);
273
274	return ret;
275	}
276
277	int btrfs_remove_free_space(struct btrfs_block_group_cache *block_group,
278	u64 offset, u64 bytes)
279	{
280	struct btrfs_free_space *info;
281	int ret = 0;
282
283	spin_lock(&block_group->lock);
284	info = tree_search_offset(&block_group->free_space_offset, offset, 0,
285	1);
286
287	if (info && info->offset == offset) {
288	if (info->bytes < bytes) {
289	printk(KERN_ERR "Found free space at %Lu, size %Lu,"
290	"trying to use %Lu\n",
291	info->offset, info->bytes, bytes);
292	WARN_ON(1);
293	ret = -EINVAL;
294	goto out;
295	}
296
297	unlink_free_space(block_group, info);
298
299	if (info->bytes == bytes) {
300	kfree(info);
301	goto out;
302	}
303
304	info->offset += bytes;
305	info->bytes -= bytes;
306
307	ret = link_free_space(block_group, info);
308	BUG_ON(ret);
309	} else {
310	WARN_ON(1);
311	}
312	out:
313	spin_unlock(&block_group->lock);
314	return ret;
315	}
316
317	void btrfs_dump_free_space(struct btrfs_block_group_cache *block_group,
318	u64 bytes)
319	{
320	struct btrfs_free_space *info;
321	struct rb_node *n;
322	int count = 0;
323
324	for (n = rb_first(&block_group->free_space_offset); n; n = rb_next(n)) {
325	info = rb_entry(n, struct btrfs_free_space, offset_index);
326	if (info->bytes >= bytes)
327	count++;
328	//printk(KERN_INFO "offset=%Lu, bytes=%Lu\n", info->offset,
329	// info->bytes);
330	}
331	printk(KERN_INFO "%d blocks of free space at or bigger than bytes is"
332	"\n", count);
333	}
334
335	u64 btrfs_block_group_free_space(struct btrfs_block_group_cache *block_group)
336	{
337	struct btrfs_free_space *info;
338	struct rb_node *n;
339	u64 ret = 0;
340
341	for (n = rb_first(&block_group->free_space_offset); n;
342	n = rb_next(n)) {
343	info = rb_entry(n, struct btrfs_free_space, offset_index);
344	ret += info->bytes;
345	}
346
347	return ret;
348	}
349
350	void btrfs_remove_free_space_cache(struct btrfs_block_group_cache *block_group)
351	{
352	struct btrfs_free_space *info;
353	struct rb_node *node;
354
355	spin_lock(&block_group->lock);
356	while ((node = rb_last(&block_group->free_space_bytes)) != NULL) {
357	info = rb_entry(node, struct btrfs_free_space, bytes_index);
358	unlink_free_space(block_group, info);
359	kfree(info);
360	if (need_resched()) {
361	spin_unlock(&block_group->lock);
362	cond_resched();
363	spin_lock(&block_group->lock);
364	}
365	}
366	spin_unlock(&block_group->lock);
367	}
368
369	struct btrfs_free_space *btrfs_find_free_space_offset(struct
370	btrfs_block_group_cache
371	*block_group, u64 offset,
372	u64 bytes)
373	{
374	struct btrfs_free_space *ret;
375
376	spin_lock(&block_group->lock);
377	ret = tree_search_offset(&block_group->free_space_offset, offset,
378	bytes, 0);
379	spin_unlock(&block_group->lock);
380
381	return ret;
382	}
383
384	struct btrfs_free_space *btrfs_find_free_space_bytes(struct
385	btrfs_block_group_cache
386	*block_group, u64 offset,
387	u64 bytes)
388	{
389	struct btrfs_free_space *ret;
390
391	spin_lock(&block_group->lock);
392
393	ret = tree_search_bytes(&block_group->free_space_bytes, offset, bytes);
394	spin_unlock(&block_group->lock);
395
396	return ret;
397	}
398
399	struct btrfs_free_space *btrfs_find_free_space(struct btrfs_block_group_cache
400	*block_group, u64 offset,
401	u64 bytes)
402	{
403	struct btrfs_free_space *ret;
404
405	spin_lock(&block_group->lock);
406	ret = tree_search_offset(&block_group->free_space_offset, offset,
407	bytes, 0);
408	if (!ret)
409	ret = tree_search_bytes(&block_group->free_space_bytes,
410	offset, bytes);
411
412	spin_unlock(&block_group->lock);
413
414	return ret;
415	}