[linux-2.6-block.git] / fs / btrfs / extent-tree.c

#include <stdio.h>
#include <stdlib.h>
#include "kerncompat.h"
#include "radix-tree.h"
#include "ctree.h"
#include "disk-io.h"
#include "print-tree.h"

/*
 * pending extents are blocks that we're trying to allocate in the extent
 * map while trying to grow the map because of other allocations.  To avoid
 * recursing, they are tagged in the radix tree and cleaned up after
 * other allocations are done.  The pending tag is also used in the same
 * manner for deletes.
 */
#define CTREE_EXTENT_PENDING 0

static int inc_block_ref(struct ctree_root *root, u64 blocknr)
{
	struct ctree_path path;
	int ret;
	struct key key;
	struct leaf *l;
	struct extent_item *item;
	init_path(&path);
	key.objectid = blocknr;
	key.flags = 0;
	key.offset = 1;
	ret = search_slot(root->extent_root, &key, &path, 0, 1);
	BUG_ON(ret != 0);
	l = &path.nodes[0]->leaf;
	item = (struct extent_item *)(l->data +
				      l->items[path.slots[0]].offset);
	item->refs++;
	BUG_ON(list_empty(&path.nodes[0]->dirty));
	release_path(root->extent_root, &path);
	return 0;
}

int btrfs_inc_ref(struct ctree_root *root, struct tree_buffer *buf)
{
	u64 blocknr;
	int i;
	for (i = 0; i < buf->node.header.nritems; i++) {
		blocknr = buf->node.blockptrs[i];
		inc_block_ref(root, blocknr);
	}
	return 0;
}

/*
 * find all the blocks marked as pending in the radix tree and remove
 * them from the extent map
 */
static int del_pending_extents(struct ctree_root *extent_root)
{
	int ret;
	struct key key;
	struct tree_buffer *gang[4];
	int i;
	struct ctree_path path;

	while(1) {
		ret = radix_tree_gang_lookup_tag(&extent_root->cache_radix,
						 (void **)gang, 0,
						 ARRAY_SIZE(gang),
						 CTREE_EXTENT_PENDING);
		if (!ret)
			break;
		for (i = 0; i < ret; i++) {
			key.objectid = gang[i]->blocknr;
			key.flags = 0;
			key.offset = 1;
			init_path(&path);
			ret = search_slot(extent_root, &key, &path, -1, 1);
			if (ret) {
				print_tree(extent_root, extent_root->node);
				printf("unable to find %Lu\n", key.objectid);
				BUG();
				// FIXME undo it and return sane
				return ret;
			}
			ret = del_item(extent_root, &path);
			if (ret) {
				BUG();
				return ret;
			}
			release_path(extent_root, &path);
			radix_tree_tag_clear(&extent_root->cache_radix,
						gang[i]->blocknr,
						CTREE_EXTENT_PENDING);
			tree_block_release(extent_root, gang[i]);
		}
	}
	return 0;
}

/*
 * remove an extent from the root, returns 0 on success
 */
int free_extent(struct ctree_root *root, u64 blocknr, u64 num_blocks)
{
	struct ctree_path path;
	struct key key;
	struct ctree_root *extent_root = root->extent_root;
	struct tree_buffer *t;
	int pending_ret;
	int ret;
	key.objectid = blocknr;
	key.flags = 0;
	key.offset = num_blocks;
	if (root == extent_root) {
		t = read_tree_block(root, key.objectid);
		radix_tree_tag_set(&root->cache_radix, key.objectid,
				   CTREE_EXTENT_PENDING);
		return 0;
	}
	init_path(&path);
	ret = search_slot(extent_root, &key, &path, -1, 1);
	if (ret) {
		print_tree(extent_root, extent_root->node);
		printf("failed to find %Lu\n", key.objectid);
		BUG();
	}
	ret = del_item(extent_root, &path);
	if (ret)
		BUG();
	release_path(extent_root, &path);
	pending_ret = del_pending_extents(root->extent_root);
	return ret ? ret : pending_ret;
}

/*
 * walks the btree of allocated extents and find a hole of a given size.
 * The key ins is changed to record the hole:
 * ins->objectid == block start
 * ins->flags = 0
 * ins->offset == number of blocks
 * Any available blocks before search_start are skipped.
 */
static int find_free_extent(struct ctree_root *orig_root, u64 num_blocks,
			    u64 search_start, u64 search_end, struct key *ins)
{
	struct ctree_path path;
	struct key *key;
	int ret;
	u64 hole_size = 0;
	int slot = 0;
	u64 last_block;
	int start_found;
	struct leaf *l;
	struct ctree_root * root = orig_root->extent_root;

check_failed:
	init_path(&path);
	ins->objectid = search_start;
	ins->offset = 0;
	ins->flags = 0;
	start_found = 0;
	ret = search_slot(root, ins, &path, 0, 0);
	if (ret < 0)
		goto error;

	while (1) {
		l = &path.nodes[0]->leaf;
		slot = path.slots[0];
		if (slot >= l->header.nritems) {
			ret = next_leaf(root, &path);
			if (ret == 0)
				continue;
			if (ret < 0)
				goto error;
			if (!start_found) {
				ins->objectid = search_start;
				ins->offset = num_blocks;
				start_found = 1;
				goto check_pending;
			}
			ins->objectid = last_block > search_start ?
					last_block : search_start;
			ins->offset = num_blocks;
			goto check_pending;
		}
		key = &l->items[slot].key;
		if (key->objectid >= search_start) {
			if (start_found) {
				hole_size = key->objectid - last_block;
				if (hole_size > num_blocks) {
					ins->objectid = last_block;
					ins->offset = num_blocks;
					goto check_pending;
				}
			} else
				start_found = 1;
			last_block = key->objectid + key->offset;
		}
		path.slots[0]++;
	}
	// FIXME -ENOSPC
check_pending:
	/* we have to make sure we didn't find an extent that has already
	 * been allocated by the map tree or the original allocation
	 */
	release_path(root, &path);
	BUG_ON(ins->objectid < search_start);
	if (orig_root->extent_root == orig_root) {
		BUG_ON(num_blocks != 1);
		if ((root->current_insert.objectid <= ins->objectid &&
		    root->current_insert.objectid +
		    root->current_insert.offset > ins->objectid) ||
		   (root->current_insert.objectid > ins->objectid &&
		    root->current_insert.objectid <= ins->objectid +
		    ins->offset) ||
		   radix_tree_tag_get(&root->cache_radix, ins->objectid,
				      CTREE_EXTENT_PENDING)) {
			search_start = ins->objectid + 1;
			goto check_failed;
		}
	}
	if (ins->offset != 1)
		BUG();
	return 0;
error:
	release_path(root, &path);
	return ret;
}

/*
 * insert all of the pending extents reserved during the original
 * allocation.  (CTREE_EXTENT_PENDING).  Returns zero if it all worked out
 */
static int insert_pending_extents(struct ctree_root *extent_root)
{
	int ret;
	struct key key;
	struct extent_item item;
	struct tree_buffer *gang[4];
	int i;

	// FIXME -ENOSPC
	item.refs = 1;
	item.owner = extent_root->node->node.header.parentid;
	while(1) {
		ret = radix_tree_gang_lookup_tag(&extent_root->cache_radix,
						 (void **)gang, 0,
						 ARRAY_SIZE(gang),
						 CTREE_EXTENT_PENDING);
		if (!ret)
			break;
		for (i = 0; i < ret; i++) {
			key.objectid = gang[i]->blocknr;
			key.flags = 0;
			key.offset = 1;
			ret = insert_item(extent_root, &key, &item,
					  sizeof(item));
			if (ret) {
				printf("%Lu already in tree\n", key.objectid);
				print_tree(extent_root, extent_root->node);
				BUG();
				// FIXME undo it and return sane
				return ret;
			}
			radix_tree_tag_clear(&extent_root->cache_radix,
					     gang[i]->blocknr,
					     CTREE_EXTENT_PENDING);
			printf("%Lu is not pending\n", gang[i]->blocknr);
			tree_block_release(extent_root, gang[i]);
		}
	}
	return 0;
}

/*
 * finds a free extent and does all the dirty work required for allocation
 * returns the key for the extent through ins, and a tree buffer for
 * the first block of the extent through buf.
 *
 * returns 0 if everything worked, non-zero otherwise.
 */
int alloc_extent(struct ctree_root *root, u64 num_blocks, u64 search_start,
			 u64 search_end, u64 owner, struct key *ins,
			 struct tree_buffer **buf)
{
	int ret;
	int pending_ret;
	struct extent_item extent_item;
	extent_item.refs = 1;
	extent_item.owner = owner;

	ret = find_free_extent(root, num_blocks, search_start, search_end, ins);
	if (ret)
		return ret;
	if (root != root->extent_root) {
		memcpy(&root->extent_root->current_insert, ins, sizeof(*ins));
		ret = insert_item(root->extent_root, ins, &extent_item,
				  sizeof(extent_item));
		memset(&root->extent_root->current_insert, 0,
		       sizeof(struct key));
		pending_ret = insert_pending_extents(root->extent_root);
		if (ret)
			return ret;
		if (pending_ret)
			return pending_ret;
		*buf = find_tree_block(root, ins->objectid);
		dirty_tree_block(root, *buf);
		return 0;
	}
	/* we're allocating an extent for the extent tree, don't recurse */
	BUG_ON(ins->offset != 1);
	*buf = find_tree_block(root, ins->objectid);
	BUG_ON(!*buf);
	printf("%Lu is pending\n", ins->objectid);
	radix_tree_tag_set(&root->cache_radix, ins->objectid,
			   CTREE_EXTENT_PENDING);
	(*buf)->count++;
	dirty_tree_block(root, *buf);
	return 0;

}

/*
 * helper function to allocate a block for a given tree
 * returns the tree buffer or NULL.
 */
struct tree_buffer *alloc_free_block(struct ctree_root *root)
{
	struct key ins;
	int ret;
	struct tree_buffer *buf = NULL;

	ret = alloc_extent(root, 1, 0, (unsigned long)-1,
			   root->node->node.header.parentid,
			   &ins, &buf);

	if (ret) {
		BUG();
		return NULL;
	}
	if (root != root->extent_root)
		BUG_ON(radix_tree_tag_get(&root->extent_root->cache_radix,
					  buf->blocknr, CTREE_EXTENT_PENDING));
	return buf;
}
Commit	Line	Data
fec577fb CM	1	#include <stdio.h>
	2	#include <stdlib.h>
	3	#include "kerncompat.h"
	4	#include "radix-tree.h"
	5	#include "ctree.h"
	6	#include "disk-io.h"
	7	#include "print-tree.h"
	8
	9	/*
	10	* pending extents are blocks that we're trying to allocate in the extent
	11	* map while trying to grow the map because of other allocations. To avoid
	12	* recursing, they are tagged in the radix tree and cleaned up after
	13	* other allocations are done. The pending tag is also used in the same
	14	* manner for deletes.
	15	*/
	16	#define CTREE_EXTENT_PENDING 0
	17
02217ed2 CM	18	static int inc_block_ref(struct ctree_root *root, u64 blocknr)
	19	{
	20	struct ctree_path path;
	21	int ret;
	22	struct key key;
	23	struct leaf *l;
	24	struct extent_item *item;
	25	init_path(&path);
	26	key.objectid = blocknr;
	27	key.flags = 0;
	28	key.offset = 1;
	29	ret = search_slot(root->extent_root, &key, &path, 0, 1);
	30	BUG_ON(ret != 0);
	31	l = &path.nodes[0]->leaf;
	32	item = (struct extent_item *)(l->data +
	33	l->items[path.slots[0]].offset);
	34	item->refs++;
	35	BUG_ON(list_empty(&path.nodes[0]->dirty));
	36	release_path(root->extent_root, &path);
	37	return 0;
	38	}
	39
	40	int btrfs_inc_ref(struct ctree_root root, struct tree_buffer buf)
	41	{
	42	u64 blocknr;
	43	int i;
	44	for (i = 0; i < buf->node.header.nritems; i++) {
	45	blocknr = buf->node.blockptrs[i];
	46	inc_block_ref(root, blocknr);
	47	}
	48	return 0;
	49	}
	50
fec577fb CM	51	/*
	52	* find all the blocks marked as pending in the radix tree and remove
	53	* them from the extent map
	54	*/
	55	static int del_pending_extents(struct ctree_root *extent_root)
	56	{
	57	int ret;
	58	struct key key;
	59	struct tree_buffer *gang[4];
	60	int i;
	61	struct ctree_path path;
	62
	63	while(1) {
	64	ret = radix_tree_gang_lookup_tag(&extent_root->cache_radix,
	65	(void **)gang, 0,
	66	ARRAY_SIZE(gang),
	67	CTREE_EXTENT_PENDING);
	68	if (!ret)
	69	break;
	70	for (i = 0; i < ret; i++) {
	71	key.objectid = gang[i]->blocknr;
	72	key.flags = 0;
	73	key.offset = 1;
	74	init_path(&path);
02217ed2	75	ret = search_slot(extent_root, &key, &path, -1, 1);
fec577fb CM	76	if (ret) {
fec577fb CM	77	print_tree(extent_root, extent_root->node);
7cf75962	78	printf("unable to find %Lu\n", key.objectid);
fec577fb CM	79	BUG();
	80	// FIXME undo it and return sane
	81	return ret;
	82	}
	83	ret = del_item(extent_root, &path);
	84	if (ret) {
	85	BUG();
	86	return ret;
	87	}
	88	release_path(extent_root, &path);
	89	radix_tree_tag_clear(&extent_root->cache_radix,
	90	gang[i]->blocknr,
	91	CTREE_EXTENT_PENDING);
	92	tree_block_release(extent_root, gang[i]);
	93	}
	94	}
	95	return 0;
	96	}
	97
	98	/*
	99	* remove an extent from the root, returns 0 on success
	100	*/
	101	int free_extent(struct ctree_root *root, u64 blocknr, u64 num_blocks)
	102	{
	103	struct ctree_path path;
	104	struct key key;
	105	struct ctree_root *extent_root = root->extent_root;
	106	struct tree_buffer *t;
	107	int pending_ret;
	108	int ret;
	109	key.objectid = blocknr;
	110	key.flags = 0;
	111	key.offset = num_blocks;
	112	if (root == extent_root) {
	113	t = read_tree_block(root, key.objectid);
	114	radix_tree_tag_set(&root->cache_radix, key.objectid,
	115	CTREE_EXTENT_PENDING);
	116	return 0;
	117	}
	118	init_path(&path);
02217ed2	119	ret = search_slot(extent_root, &key, &path, -1, 1);
fec577fb CM	120	if (ret) {
fec577fb CM	121	print_tree(extent_root, extent_root->node);
7cf75962	122	printf("failed to find %Lu\n", key.objectid);
fec577fb CM	123	BUG();
	124	}
	125	ret = del_item(extent_root, &path);
	126	if (ret)
	127	BUG();
	128	release_path(extent_root, &path);
	129	pending_ret = del_pending_extents(root->extent_root);
	130	return ret ? ret : pending_ret;
	131	}
	132
	133	/*
	134	* walks the btree of allocated extents and find a hole of a given size.
	135	* The key ins is changed to record the hole:
	136	* ins->objectid == block start
	137	* ins->flags = 0
	138	* ins->offset == number of blocks
	139	* Any available blocks before search_start are skipped.
	140	*/
0f70abe2 CM	141	static int find_free_extent(struct ctree_root *orig_root, u64 num_blocks,
0f70abe2 CM	142	u64 search_start, u64 search_end, struct key *ins)
fec577fb CM	143	{
	144	struct ctree_path path;
	145	struct key *key;
	146	int ret;
	147	u64 hole_size = 0;
	148	int slot = 0;
	149	u64 last_block;
	150	int start_found;
	151	struct leaf *l;
	152	struct ctree_root * root = orig_root->extent_root;
	153
	154	check_failed:
	155	init_path(&path);
	156	ins->objectid = search_start;
	157	ins->offset = 0;
	158	ins->flags = 0;
	159	start_found = 0;
02217ed2	160	ret = search_slot(root, ins, &path, 0, 0);
0f70abe2 CM	161	if (ret < 0)
0f70abe2 CM	162	goto error;
aa5d6bed	163
fec577fb CM	164	while (1) {
	165	l = &path.nodes[0]->leaf;
	166	slot = path.slots[0];
	167	if (slot >= l->header.nritems) {
	168	ret = next_leaf(root, &path);
	169	if (ret == 0)
	170	continue;
0f70abe2 CM	171	if (ret < 0)
0f70abe2 CM	172	goto error;
fec577fb CM	173	if (!start_found) {
	174	ins->objectid = search_start;
	175	ins->offset = num_blocks;
	176	start_found = 1;
	177	goto check_pending;
	178	}
	179	ins->objectid = last_block > search_start ?
	180	last_block : search_start;
	181	ins->offset = num_blocks;
	182	goto check_pending;
	183	}
	184	key = &l->items[slot].key;
	185	if (key->objectid >= search_start) {
	186	if (start_found) {
	187	hole_size = key->objectid - last_block;
	188	if (hole_size > num_blocks) {
	189	ins->objectid = last_block;
	190	ins->offset = num_blocks;
	191	goto check_pending;
	192	}
	193	} else
	194	start_found = 1;
	195	last_block = key->objectid + key->offset;
	196	}
	197	path.slots[0]++;
	198	}
	199	// FIXME -ENOSPC
	200	check_pending:
	201	/* we have to make sure we didn't find an extent that has already
	202	* been allocated by the map tree or the original allocation
	203	*/
	204	release_path(root, &path);
	205	BUG_ON(ins->objectid < search_start);
	206	if (orig_root->extent_root == orig_root) {
	207	BUG_ON(num_blocks != 1);
	208	if ((root->current_insert.objectid <= ins->objectid &&
	209	root->current_insert.objectid +
	210	root->current_insert.offset > ins->objectid) \|\|
	211	(root->current_insert.objectid > ins->objectid &&
	212	root->current_insert.objectid <= ins->objectid +
	213	ins->offset) \|\|
	214	radix_tree_tag_get(&root->cache_radix, ins->objectid,
	215	CTREE_EXTENT_PENDING)) {
	216	search_start = ins->objectid + 1;
	217	goto check_failed;
	218	}
	219	}
	220	if (ins->offset != 1)
	221	BUG();
	222	return 0;
0f70abe2 CM	223	error:
	224	release_path(root, &path);
	225	return ret;
fec577fb CM	226	}
	227
	228	/*
	229	* insert all of the pending extents reserved during the original
	230	* allocation. (CTREE_EXTENT_PENDING). Returns zero if it all worked out
	231	*/
	232	static int insert_pending_extents(struct ctree_root *extent_root)
	233	{
	234	int ret;
	235	struct key key;
	236	struct extent_item item;
	237	struct tree_buffer *gang[4];
	238	int i;
	239
	240	// FIXME -ENOSPC
	241	item.refs = 1;
	242	item.owner = extent_root->node->node.header.parentid;
	243	while(1) {
	244	ret = radix_tree_gang_lookup_tag(&extent_root->cache_radix,
	245	(void **)gang, 0,
	246	ARRAY_SIZE(gang),
	247	CTREE_EXTENT_PENDING);
	248	if (!ret)
	249	break;
	250	for (i = 0; i < ret; i++) {
	251	key.objectid = gang[i]->blocknr;
	252	key.flags = 0;
	253	key.offset = 1;
	254	ret = insert_item(extent_root, &key, &item,
	255	sizeof(item));
	256	if (ret) {
02217ed2 CM	257	printf("%Lu already in tree\n", key.objectid);
02217ed2 CM	258	print_tree(extent_root, extent_root->node);
fec577fb CM	259	BUG();
	260	// FIXME undo it and return sane
	261	return ret;
	262	}
	263	radix_tree_tag_clear(&extent_root->cache_radix,
	264	gang[i]->blocknr,
	265	CTREE_EXTENT_PENDING);
02217ed2	266	printf("%Lu is not pending\n", gang[i]->blocknr);
fec577fb CM	267	tree_block_release(extent_root, gang[i]);
	268	}
	269	}
	270	return 0;
	271	}
	272
	273	/*
	274	* finds a free extent and does all the dirty work required for allocation
	275	* returns the key for the extent through ins, and a tree buffer for
	276	* the first block of the extent through buf.
	277	*
	278	* returns 0 if everything worked, non-zero otherwise.
	279	*/
	280	int alloc_extent(struct ctree_root *root, u64 num_blocks, u64 search_start,
	281	u64 search_end, u64 owner, struct key *ins,
	282	struct tree_buffer **buf)
	283	{
	284	int ret;
	285	int pending_ret;
	286	struct extent_item extent_item;
	287	extent_item.refs = 1;
	288	extent_item.owner = owner;
	289
	290	ret = find_free_extent(root, num_blocks, search_start, search_end, ins);
	291	if (ret)
	292	return ret;
	293	if (root != root->extent_root) {
	294	memcpy(&root->extent_root->current_insert, ins, sizeof(*ins));
	295	ret = insert_item(root->extent_root, ins, &extent_item,
	296	sizeof(extent_item));
	297	memset(&root->extent_root->current_insert, 0,
	298	sizeof(struct key));
	299	pending_ret = insert_pending_extents(root->extent_root);
	300	if (ret)
	301	return ret;
	302	if (pending_ret)
	303	return pending_ret;
	304	*buf = find_tree_block(root, ins->objectid);
02217ed2	305	dirty_tree_block(root, *buf);
fec577fb CM	306	return 0;
	307	}
	308	/* we're allocating an extent for the extent tree, don't recurse */
	309	BUG_ON(ins->offset != 1);
	310	*buf = find_tree_block(root, ins->objectid);
	311	BUG_ON(!*buf);
02217ed2	312	printf("%Lu is pending\n", ins->objectid);
fec577fb CM	313	radix_tree_tag_set(&root->cache_radix, ins->objectid,
	314	CTREE_EXTENT_PENDING);
	315	(*buf)->count++;
02217ed2	316	dirty_tree_block(root, *buf);
fec577fb CM	317	return 0;
	318
	319	}
	320
	321	/*
	322	* helper function to allocate a block for a given tree
	323	* returns the tree buffer or NULL.
	324	*/
	325	struct tree_buffer alloc_free_block(struct ctree_root root)
	326	{
	327	struct key ins;
	328	int ret;
	329	struct tree_buffer *buf = NULL;
	330
	331	ret = alloc_extent(root, 1, 0, (unsigned long)-1,
	332	root->node->node.header.parentid,
	333	&ins, &buf);
	334
	335	if (ret) {
	336	BUG();
	337	return NULL;
	338	}
	339	if (root != root->extent_root)
	340	BUG_ON(radix_tree_tag_get(&root->extent_root->cache_radix,
	341	buf->blocknr, CTREE_EXTENT_PENDING));
	342	return buf;
	343	}