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

#include <linux/module.h>
#include "ctree.h"
#include "disk-io.h"
#include "print-tree.h"
#include "transaction.h"

static int find_free_extent(struct btrfs_trans_handle *trans, struct btrfs_root
			    *orig_root, u64 num_blocks, u64 search_start, u64
			    search_end, struct btrfs_key *ins);
static int finish_current_insert(struct btrfs_trans_handle *trans, struct
				 btrfs_root *extent_root);
static int del_pending_extents(struct btrfs_trans_handle *trans, struct
			       btrfs_root *extent_root);

static int inc_block_ref(struct btrfs_trans_handle *trans, struct btrfs_root
			 *root, u64 blocknr, u64 num_blocks)
{
	struct btrfs_path *path;
	int ret;
	struct btrfs_key key;
	struct btrfs_leaf *l;
	struct btrfs_extent_item *item;
	struct btrfs_key ins;
	u32 refs;

	find_free_extent(trans, root->fs_info->extent_root, 0, 0, (u64)-1,
			 &ins);
	path = btrfs_alloc_path();
	BUG_ON(!path);
	btrfs_init_path(path);
	key.objectid = blocknr;
	key.flags = 0;
	btrfs_set_key_type(&key, BTRFS_EXTENT_ITEM_KEY);
	key.offset = num_blocks;
	ret = btrfs_search_slot(trans, root->fs_info->extent_root, &key, path,
				0, 1);
	if (ret != 0)
		BUG();
	BUG_ON(ret != 0);
	l = btrfs_buffer_leaf(path->nodes[0]);
	item = btrfs_item_ptr(l, path->slots[0], struct btrfs_extent_item);
	refs = btrfs_extent_refs(item);
	btrfs_set_extent_refs(item, refs + 1);
	btrfs_mark_buffer_dirty(path->nodes[0]);

	btrfs_release_path(root->fs_info->extent_root, path);
	btrfs_free_path(path);
	finish_current_insert(trans, root->fs_info->extent_root);
	del_pending_extents(trans, root->fs_info->extent_root);
	return 0;
}

static int lookup_block_ref(struct btrfs_trans_handle *trans, struct btrfs_root
			    *root, u64 blocknr, u64 num_blocks, u32 *refs)
{
	struct btrfs_path *path;
	int ret;
	struct btrfs_key key;
	struct btrfs_leaf *l;
	struct btrfs_extent_item *item;

	path = btrfs_alloc_path();
	btrfs_init_path(path);
	key.objectid = blocknr;
	key.offset = num_blocks;
	key.flags = 0;
	btrfs_set_key_type(&key, BTRFS_EXTENT_ITEM_KEY);
	ret = btrfs_search_slot(trans, root->fs_info->extent_root, &key, path,
				0, 0);
	if (ret != 0)
		BUG();
	l = btrfs_buffer_leaf(path->nodes[0]);
	item = btrfs_item_ptr(l, path->slots[0], struct btrfs_extent_item);
	*refs = btrfs_extent_refs(item);
	btrfs_release_path(root->fs_info->extent_root, path);
	btrfs_free_path(path);
	return 0;
}

int btrfs_inc_ref(struct btrfs_trans_handle *trans, struct btrfs_root *root,
		  struct buffer_head *buf)
{
	u64 blocknr;
	struct btrfs_node *buf_node;
	struct btrfs_leaf *buf_leaf;
	struct btrfs_disk_key *key;
	struct btrfs_file_extent_item *fi;
	int i;
	int leaf;
	int ret;

	if (!root->ref_cows)
		return 0;
	buf_node = btrfs_buffer_node(buf);
	leaf = btrfs_is_leaf(buf_node);
	buf_leaf = btrfs_buffer_leaf(buf);
	for (i = 0; i < btrfs_header_nritems(&buf_node->header); i++) {
		if (leaf) {
			key = &buf_leaf->items[i].key;
			if (btrfs_disk_key_type(key) != BTRFS_EXTENT_DATA_KEY)
				continue;
			fi = btrfs_item_ptr(buf_leaf, i,
					    struct btrfs_file_extent_item);
			ret = inc_block_ref(trans, root,
				    btrfs_file_extent_disk_blocknr(fi),
				    btrfs_file_extent_disk_num_blocks(fi));
			BUG_ON(ret);
		} else {
			blocknr = btrfs_node_blockptr(buf_node, i);
			ret = inc_block_ref(trans, root, blocknr, 1);
			BUG_ON(ret);
		}
	}
	return 0;
}

int btrfs_finish_extent_commit(struct btrfs_trans_handle *trans, struct
			       btrfs_root *root)
{
	unsigned long gang[8];
	u64 first = 0;
	int ret;
	int i;
	struct radix_tree_root *pinned_radix = &root->fs_info->pinned_radix;

	while(1) {
		ret = find_first_radix_bit(pinned_radix, gang,
					   ARRAY_SIZE(gang));
		if (!ret)
			break;
		if (!first)
			first = gang[0];
		for (i = 0; i < ret; i++) {
			clear_radix_bit(pinned_radix, gang[i]);
		}
	}
	if (root->fs_info->last_insert.objectid > first)
		root->fs_info->last_insert.objectid = first;
	root->fs_info->last_insert.offset = 0;
	return 0;
}

static int finish_current_insert(struct btrfs_trans_handle *trans, struct
				 btrfs_root *extent_root)
{
	struct btrfs_key ins;
	struct btrfs_extent_item extent_item;
	int i;
	int ret;
	u64 super_blocks_used;
	struct btrfs_fs_info *info = extent_root->fs_info;

	btrfs_set_extent_refs(&extent_item, 1);
	btrfs_set_extent_owner(&extent_item,
		btrfs_header_parentid(btrfs_buffer_header(extent_root->node)));
	ins.offset = 1;
	ins.flags = 0;
	btrfs_set_key_type(&ins, BTRFS_EXTENT_ITEM_KEY);

	for (i = 0; i < extent_root->fs_info->current_insert.flags; i++) {
		ins.objectid = extent_root->fs_info->current_insert.objectid +
				i;
		super_blocks_used = btrfs_super_blocks_used(info->disk_super);
		btrfs_set_super_blocks_used(info->disk_super,
					    super_blocks_used + 1);
		ret = btrfs_insert_item(trans, extent_root, &ins, &extent_item,
					sizeof(extent_item));
		BUG_ON(ret);
	}
	extent_root->fs_info->current_insert.offset = 0;
	return 0;
}

static int pin_down_block(struct btrfs_root *root, u64 blocknr, int pending)
{
	int err;
	struct btrfs_header *header;
	struct buffer_head *bh;

	if (!pending) {
		bh = btrfs_find_tree_block(root, blocknr);
		if (bh) {
			if (buffer_uptodate(bh)) {
				u64 transid =
				    root->fs_info->running_transaction->transid;
				header = btrfs_buffer_header(bh);
				if (btrfs_header_generation(header) ==
				    transid) {
					btrfs_block_release(root, bh);
					return 0;
				}
			}
			btrfs_block_release(root, bh);
		}
		err = set_radix_bit(&root->fs_info->pinned_radix, blocknr);
	} else {
		err = set_radix_bit(&root->fs_info->pending_del_radix, blocknr);
	}
	BUG_ON(err);
	return 0;
}

/*
 * remove an extent from the root, returns 0 on success
 */
static int __free_extent(struct btrfs_trans_handle *trans, struct btrfs_root
			 *root, u64 blocknr, u64 num_blocks, int pin)
{
	struct btrfs_path *path;
	struct btrfs_key key;
	struct btrfs_fs_info *info = root->fs_info;
	struct btrfs_root *extent_root = info->extent_root;
	int ret;
	struct btrfs_extent_item *ei;
	struct btrfs_key ins;
	u32 refs;

	key.objectid = blocknr;
	key.flags = 0;
	btrfs_set_key_type(&key, BTRFS_EXTENT_ITEM_KEY);
	key.offset = num_blocks;

	find_free_extent(trans, root, 0, 0, (u64)-1, &ins);
	path = btrfs_alloc_path();
	BUG_ON(!path);
	btrfs_init_path(path);
	ret = btrfs_search_slot(trans, extent_root, &key, path, -1, 1);
	if (ret) {
		printk("failed to find %Lu\n", key.objectid);
		btrfs_print_tree(extent_root, extent_root->node);
		printk("failed to find %Lu\n", key.objectid);
		BUG();
	}
	ei = btrfs_item_ptr(btrfs_buffer_leaf(path->nodes[0]), path->slots[0],
			    struct btrfs_extent_item);
	BUG_ON(ei->refs == 0);
	refs = btrfs_extent_refs(ei) - 1;
	btrfs_set_extent_refs(ei, refs);
	btrfs_mark_buffer_dirty(path->nodes[0]);
	if (refs == 0) {
		u64 super_blocks_used;

		if (pin) {
			ret = pin_down_block(root, blocknr, 0);
			BUG_ON(ret);
		}

		super_blocks_used = btrfs_super_blocks_used(info->disk_super);
		btrfs_set_super_blocks_used(info->disk_super,
					    super_blocks_used - num_blocks);
		ret = btrfs_del_item(trans, extent_root, path);
		if (ret)
			BUG();
	}
	btrfs_release_path(extent_root, path);
	btrfs_free_path(path);
	finish_current_insert(trans, extent_root);
	return ret;
}

/*
 * find all the blocks marked as pending in the radix tree and remove
 * them from the extent map
 */
static int del_pending_extents(struct btrfs_trans_handle *trans, struct
			       btrfs_root *extent_root)
{
	int ret;
	int wret;
	int err = 0;
	unsigned long gang[4];
	int i;
	struct radix_tree_root *pending_radix;
	struct radix_tree_root *pinned_radix;

	pending_radix = &extent_root->fs_info->pending_del_radix;
	pinned_radix = &extent_root->fs_info->pinned_radix;

	while(1) {
		ret = find_first_radix_bit(pending_radix, gang,
					   ARRAY_SIZE(gang));
		if (!ret)
			break;
		for (i = 0; i < ret; i++) {
			wret = set_radix_bit(pinned_radix, gang[i]);
			BUG_ON(wret);
			wret = clear_radix_bit(pending_radix, gang[i]);
			BUG_ON(wret);
			wret = __free_extent(trans, extent_root,
					     gang[i], 1, 0);
			if (wret)
				err = wret;
		}
	}
	return err;
}

/*
 * remove an extent from the root, returns 0 on success
 */
int btrfs_free_extent(struct btrfs_trans_handle *trans, struct btrfs_root
		      *root, u64 blocknr, u64 num_blocks, int pin)
{
	struct btrfs_root *extent_root = root->fs_info->extent_root;
	int pending_ret;
	int ret;

	if (root == extent_root) {
		pin_down_block(root, blocknr, 1);
		return 0;
	}
	ret = __free_extent(trans, root, blocknr, num_blocks, pin);
	pending_ret = del_pending_extents(trans, root->fs_info->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 = BTRFS_EXTENT_ITEM_KEY
 * ins->offset == number of blocks
 * Any available blocks before search_start are skipped.
 */
static int find_free_extent(struct btrfs_trans_handle *trans, struct btrfs_root
			    *orig_root, u64 num_blocks, u64 search_start, u64
			    search_end, struct btrfs_key *ins)
{
	struct btrfs_path *path;
	struct btrfs_key key;
	int ret;
	u64 hole_size = 0;
	int slot = 0;
	u64 last_block = 0;
	u64 test_block;
	int start_found;
	struct btrfs_leaf *l;
	struct btrfs_root * root = orig_root->fs_info->extent_root;
	int total_needed = num_blocks;
	int level;

	level = btrfs_header_level(btrfs_buffer_header(root->node));
	total_needed += (level + 1) * 3;
	if (root->fs_info->last_insert.objectid > search_start)
		search_start = root->fs_info->last_insert.objectid;

	ins->flags = 0;
	btrfs_set_key_type(ins, BTRFS_EXTENT_ITEM_KEY);
	path = btrfs_alloc_path();

check_failed:
	btrfs_init_path(path);
	ins->objectid = search_start;
	ins->offset = 0;
	start_found = 0;
	ret = btrfs_search_slot(trans, root, ins, path, 0, 0);
	if (ret < 0)
		goto error;

	if (path->slots[0] > 0)
		path->slots[0]--;

	while (1) {
		l = btrfs_buffer_leaf(path->nodes[0]);
		slot = path->slots[0];
		if (slot >= btrfs_header_nritems(&l->header)) {
			ret = btrfs_next_leaf(root, path);
			if (ret == 0)
				continue;
			if (ret < 0)
				goto error;
			if (!start_found) {
				ins->objectid = search_start;
				ins->offset = (u64)-1;
				start_found = 1;
				goto check_pending;
			}
			ins->objectid = last_block > search_start ?
					last_block : search_start;
			ins->offset = (u64)-1;
			goto check_pending;
		}
		btrfs_disk_key_to_cpu(&key, &l->items[slot].key);
		if (key.objectid >= search_start) {
			if (start_found) {
				if (last_block < search_start)
					last_block = search_start;
				hole_size = key.objectid - last_block;
				if (hole_size > total_needed) {
					ins->objectid = last_block;
					ins->offset = hole_size;
					goto check_pending;
				}
			}
		}
		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
	 */
	btrfs_release_path(root, path);
	BUG_ON(ins->objectid < search_start);
	for (test_block = ins->objectid;
	     test_block < ins->objectid + total_needed; test_block++) {
		if (test_radix_bit(&root->fs_info->pinned_radix,
				      test_block)) {
			search_start = test_block + 1;
			goto check_failed;
		}
	}
	BUG_ON(root->fs_info->current_insert.offset);
	root->fs_info->current_insert.offset = total_needed - num_blocks;
	root->fs_info->current_insert.objectid = ins->objectid + num_blocks;
	root->fs_info->current_insert.flags = 0;
	root->fs_info->last_insert.objectid = ins->objectid;
	ins->offset = num_blocks;
	btrfs_free_path(path);
	return 0;
error:
	btrfs_release_path(root, path);
	btrfs_free_path(path);
	return ret;
}

/*
 * 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 btrfs_alloc_extent(struct btrfs_trans_handle *trans, struct btrfs_root
			*root, u64 num_blocks, u64 search_start, u64
			search_end, u64 owner, struct btrfs_key *ins)
{
	int ret;
	int pending_ret;
	u64 super_blocks_used;
	struct btrfs_fs_info *info = root->fs_info;
	struct btrfs_root *extent_root = info->extent_root;
	struct btrfs_extent_item extent_item;

	btrfs_set_extent_refs(&extent_item, 1);
	btrfs_set_extent_owner(&extent_item, owner);

	if (root == extent_root) {
		BUG_ON(extent_root->fs_info->current_insert.offset == 0);
		BUG_ON(num_blocks != 1);
		BUG_ON(extent_root->fs_info->current_insert.flags ==
		       extent_root->fs_info->current_insert.offset);
		ins->offset = 1;
		ins->objectid = extent_root->fs_info->current_insert.objectid +
				extent_root->fs_info->current_insert.flags++;
		return 0;
	}
	ret = find_free_extent(trans, root, num_blocks, search_start,
			       search_end, ins);
	if (ret)
		return ret;

	super_blocks_used = btrfs_super_blocks_used(info->disk_super);
	btrfs_set_super_blocks_used(info->disk_super, super_blocks_used +
				    num_blocks);
	ret = btrfs_insert_item(trans, extent_root, ins, &extent_item,
				sizeof(extent_item));

	finish_current_insert(trans, extent_root);
	pending_ret = del_pending_extents(trans, extent_root);
	if (ret)
		return ret;
	if (pending_ret)
		return pending_ret;
	return 0;
}

/*
 * helper function to allocate a block for a given tree
 * returns the tree buffer or NULL.
 */
struct buffer_head *btrfs_alloc_free_block(struct btrfs_trans_handle *trans,
					    struct btrfs_root *root)
{
	struct btrfs_key ins;
	int ret;
	struct buffer_head *buf;

	ret = btrfs_alloc_extent(trans, root, 1, 0, (unsigned long)-1,
		btrfs_header_parentid(btrfs_buffer_header(root->node)), &ins);
	if (ret) {
		BUG();
		return NULL;
	}
	buf = btrfs_find_create_tree_block(root, ins.objectid);
	set_buffer_uptodate(buf);
	return buf;
}

static int drop_leaf_ref(struct btrfs_trans_handle *trans,
			 struct btrfs_root *root, struct buffer_head *cur)
{
	struct btrfs_disk_key *key;
	struct btrfs_leaf *leaf;
	struct btrfs_file_extent_item *fi;
	int i;
	int nritems;
	int ret;

	BUG_ON(!btrfs_is_leaf(btrfs_buffer_node(cur)));
	leaf = btrfs_buffer_leaf(cur);
	nritems = btrfs_header_nritems(&leaf->header);
	for (i = 0; i < nritems; i++) {
		key = &leaf->items[i].key;
		if (btrfs_disk_key_type(key) != BTRFS_EXTENT_DATA_KEY)
			continue;
		fi = btrfs_item_ptr(leaf, i, struct btrfs_file_extent_item);
		/*
		 * FIXME make sure to insert a trans record that
		 * repeats the snapshot del on crash
		 */
		ret = btrfs_free_extent(trans, root,
					btrfs_file_extent_disk_blocknr(fi),
					btrfs_file_extent_disk_num_blocks(fi),
					0);
		BUG_ON(ret);
	}
	return 0;
}

/*
 * helper function for drop_snapshot, this walks down the tree dropping ref
 * counts as it goes.
 */
static int walk_down_tree(struct btrfs_trans_handle *trans, struct btrfs_root
			  *root, struct btrfs_path *path, int *level)
{
	struct buffer_head *next;
	struct buffer_head *cur;
	u64 blocknr;
	int ret;
	u32 refs;

	WARN_ON(*level < 0);
	WARN_ON(*level >= BTRFS_MAX_LEVEL);
	ret = lookup_block_ref(trans, root, path->nodes[*level]->b_blocknr,
			       1, &refs);
	BUG_ON(ret);
	if (refs > 1)
		goto out;
	/*
	 * walk down to the last node level and free all the leaves
	 */
	while(*level >= 0) {
		WARN_ON(*level < 0);
		WARN_ON(*level >= BTRFS_MAX_LEVEL);
		cur = path->nodes[*level];
		if (btrfs_header_level(btrfs_buffer_header(cur)) != *level)
			WARN_ON(1);
		if (path->slots[*level] >=
		    btrfs_header_nritems(btrfs_buffer_header(cur)))
			break;
		if (*level == 0) {
			ret = drop_leaf_ref(trans, root, cur);
			BUG_ON(ret);
			break;
		}
		blocknr = btrfs_node_blockptr(btrfs_buffer_node(cur),
					      path->slots[*level]);
		ret = lookup_block_ref(trans, root, blocknr, 1, &refs);
		BUG_ON(ret);
		if (refs != 1) {
			path->slots[*level]++;
			ret = btrfs_free_extent(trans, root, blocknr, 1, 1);
			BUG_ON(ret);
			continue;
		}
		next = read_tree_block(root, blocknr);
		WARN_ON(*level <= 0);
		if (path->nodes[*level-1])
			btrfs_block_release(root, path->nodes[*level-1]);
		path->nodes[*level-1] = next;
		*level = btrfs_header_level(btrfs_buffer_header(next));
		path->slots[*level] = 0;
	}
out:
	WARN_ON(*level < 0);
	WARN_ON(*level >= BTRFS_MAX_LEVEL);
	ret = btrfs_free_extent(trans, root,
				path->nodes[*level]->b_blocknr, 1, 1);
	btrfs_block_release(root, path->nodes[*level]);
	path->nodes[*level] = NULL;
	*level += 1;
	BUG_ON(ret);
	return 0;
}

/*
 * helper for dropping snapshots.  This walks back up the tree in the path
 * to find the first node higher up where we haven't yet gone through
 * all the slots
 */
static int walk_up_tree(struct btrfs_trans_handle *trans, struct btrfs_root
			*root, struct btrfs_path *path, int *level)
{
	int i;
	int slot;
	int ret;
	for(i = *level; i < BTRFS_MAX_LEVEL - 1 && path->nodes[i]; i++) {
		slot = path->slots[i];
		if (slot < btrfs_header_nritems(
		    btrfs_buffer_header(path->nodes[i])) - 1) {
			path->slots[i]++;
			*level = i;
			return 0;
		} else {
			ret = btrfs_free_extent(trans, root,
						path->nodes[*level]->b_blocknr,
						1, 1);
			BUG_ON(ret);
			btrfs_block_release(root, path->nodes[*level]);
			path->nodes[*level] = NULL;
			*level = i + 1;
		}
	}
	return 1;
}

/*
 * drop the reference count on the tree rooted at 'snap'.  This traverses
 * the tree freeing any blocks that have a ref count of zero after being
 * decremented.
 */
int btrfs_drop_snapshot(struct btrfs_trans_handle *trans, struct btrfs_root
			*root, struct buffer_head *snap)
{
	int ret = 0;
	int wret;
	int level;
	struct btrfs_path *path;
	int i;
	int orig_level;

	path = btrfs_alloc_path();
	BUG_ON(!path);
	btrfs_init_path(path);

	level = btrfs_header_level(btrfs_buffer_header(snap));
	orig_level = level;
	path->nodes[level] = snap;
	path->slots[level] = 0;
	while(1) {
		wret = walk_down_tree(trans, root, path, &level);
		if (wret > 0)
			break;
		if (wret < 0)
			ret = wret;

		wret = walk_up_tree(trans, root, path, &level);
		if (wret > 0)
			break;
		if (wret < 0)
			ret = wret;
	}
	for (i = 0; i <= orig_level; i++) {
		if (path->nodes[i]) {
			btrfs_block_release(root, path->nodes[i]);
		}
	}
	btrfs_free_path(path);
	return ret;
}
Commit	Line	Data
	1	#include <linux/module.h>
	2	#include "ctree.h"
	3	#include "disk-io.h"
	4	#include "print-tree.h"
	5	#include "transaction.h"
	6
	7	static int find_free_extent(struct btrfs_trans_handle *trans, struct btrfs_root
	8	*orig_root, u64 num_blocks, u64 search_start, u64
	9	search_end, struct btrfs_key *ins);
	10	static int finish_current_insert(struct btrfs_trans_handle *trans, struct
	11	btrfs_root *extent_root);
	12	static int del_pending_extents(struct btrfs_trans_handle *trans, struct
	13	btrfs_root *extent_root);
	14
	15	static int inc_block_ref(struct btrfs_trans_handle *trans, struct btrfs_root
	16	*root, u64 blocknr, u64 num_blocks)
	17	{
	18	struct btrfs_path *path;
	19	int ret;
	20	struct btrfs_key key;
	21	struct btrfs_leaf *l;
	22	struct btrfs_extent_item *item;
	23	struct btrfs_key ins;
	24	u32 refs;
	25
	26	find_free_extent(trans, root->fs_info->extent_root, 0, 0, (u64)-1,
	27	&ins);
	28	path = btrfs_alloc_path();
	29	BUG_ON(!path);
	30	btrfs_init_path(path);
	31	key.objectid = blocknr;
	32	key.flags = 0;
	33	btrfs_set_key_type(&key, BTRFS_EXTENT_ITEM_KEY);
	34	key.offset = num_blocks;
	35	ret = btrfs_search_slot(trans, root->fs_info->extent_root, &key, path,
	36	0, 1);
	37	if (ret != 0)
	38	BUG();
	39	BUG_ON(ret != 0);
	40	l = btrfs_buffer_leaf(path->nodes[0]);
	41	item = btrfs_item_ptr(l, path->slots[0], struct btrfs_extent_item);
	42	refs = btrfs_extent_refs(item);
	43	btrfs_set_extent_refs(item, refs + 1);
	44	btrfs_mark_buffer_dirty(path->nodes[0]);
	45
	46	btrfs_release_path(root->fs_info->extent_root, path);
	47	btrfs_free_path(path);
	48	finish_current_insert(trans, root->fs_info->extent_root);
	49	del_pending_extents(trans, root->fs_info->extent_root);
	50	return 0;
	51	}
	52
	53	static int lookup_block_ref(struct btrfs_trans_handle *trans, struct btrfs_root
	54	root, u64 blocknr, u64 num_blocks, u32 refs)
	55	{
	56	struct btrfs_path *path;
	57	int ret;
	58	struct btrfs_key key;
	59	struct btrfs_leaf *l;
	60	struct btrfs_extent_item *item;
	61
	62	path = btrfs_alloc_path();
	63	btrfs_init_path(path);
	64	key.objectid = blocknr;
	65	key.offset = num_blocks;
	66	key.flags = 0;
	67	btrfs_set_key_type(&key, BTRFS_EXTENT_ITEM_KEY);
	68	ret = btrfs_search_slot(trans, root->fs_info->extent_root, &key, path,
	69	0, 0);
	70	if (ret != 0)
	71	BUG();
	72	l = btrfs_buffer_leaf(path->nodes[0]);
	73	item = btrfs_item_ptr(l, path->slots[0], struct btrfs_extent_item);
	74	*refs = btrfs_extent_refs(item);
	75	btrfs_release_path(root->fs_info->extent_root, path);
	76	btrfs_free_path(path);
	77	return 0;
	78	}
	79
	80	int btrfs_inc_ref(struct btrfs_trans_handle trans, struct btrfs_root root,
	81	struct buffer_head *buf)
	82	{
	83	u64 blocknr;
	84	struct btrfs_node *buf_node;
	85	struct btrfs_leaf *buf_leaf;
	86	struct btrfs_disk_key *key;
	87	struct btrfs_file_extent_item *fi;
	88	int i;
	89	int leaf;
	90	int ret;
	91
	92	if (!root->ref_cows)
	93	return 0;
	94	buf_node = btrfs_buffer_node(buf);
	95	leaf = btrfs_is_leaf(buf_node);
	96	buf_leaf = btrfs_buffer_leaf(buf);
	97	for (i = 0; i < btrfs_header_nritems(&buf_node->header); i++) {
	98	if (leaf) {
	99	key = &buf_leaf->items[i].key;
	100	if (btrfs_disk_key_type(key) != BTRFS_EXTENT_DATA_KEY)
	101	continue;
	102	fi = btrfs_item_ptr(buf_leaf, i,
	103	struct btrfs_file_extent_item);
	104	ret = inc_block_ref(trans, root,
	105	btrfs_file_extent_disk_blocknr(fi),
	106	btrfs_file_extent_disk_num_blocks(fi));
	107	BUG_ON(ret);
	108	} else {
	109	blocknr = btrfs_node_blockptr(buf_node, i);
	110	ret = inc_block_ref(trans, root, blocknr, 1);
	111	BUG_ON(ret);
	112	}
	113	}
	114	return 0;
	115	}
	116
	117	int btrfs_finish_extent_commit(struct btrfs_trans_handle *trans, struct
	118	btrfs_root *root)
	119	{
	120	unsigned long gang[8];
	121	u64 first = 0;
	122	int ret;
	123	int i;
	124	struct radix_tree_root *pinned_radix = &root->fs_info->pinned_radix;
	125
	126	while(1) {
	127	ret = find_first_radix_bit(pinned_radix, gang,
	128	ARRAY_SIZE(gang));
	129	if (!ret)
	130	break;
	131	if (!first)
	132	first = gang[0];
	133	for (i = 0; i < ret; i++) {
	134	clear_radix_bit(pinned_radix, gang[i]);
	135	}
	136	}
	137	if (root->fs_info->last_insert.objectid > first)
	138	root->fs_info->last_insert.objectid = first;
	139	root->fs_info->last_insert.offset = 0;
	140	return 0;
	141	}
	142
	143	static int finish_current_insert(struct btrfs_trans_handle *trans, struct
	144	btrfs_root *extent_root)
	145	{
	146	struct btrfs_key ins;
	147	struct btrfs_extent_item extent_item;
	148	int i;
	149	int ret;
	150	u64 super_blocks_used;
	151	struct btrfs_fs_info *info = extent_root->fs_info;
	152
	153	btrfs_set_extent_refs(&extent_item, 1);
	154	btrfs_set_extent_owner(&extent_item,
	155	btrfs_header_parentid(btrfs_buffer_header(extent_root->node)));
	156	ins.offset = 1;
	157	ins.flags = 0;
	158	btrfs_set_key_type(&ins, BTRFS_EXTENT_ITEM_KEY);
	159
	160	for (i = 0; i < extent_root->fs_info->current_insert.flags; i++) {
	161	ins.objectid = extent_root->fs_info->current_insert.objectid +
	162	i;
	163	super_blocks_used = btrfs_super_blocks_used(info->disk_super);
	164	btrfs_set_super_blocks_used(info->disk_super,
	165	super_blocks_used + 1);
	166	ret = btrfs_insert_item(trans, extent_root, &ins, &extent_item,
	167	sizeof(extent_item));
	168	BUG_ON(ret);
	169	}
	170	extent_root->fs_info->current_insert.offset = 0;
	171	return 0;
	172	}
	173
	174	static int pin_down_block(struct btrfs_root *root, u64 blocknr, int pending)
	175	{
	176	int err;
	177	struct btrfs_header *header;
	178	struct buffer_head *bh;
	179
	180	if (!pending) {
	181	bh = btrfs_find_tree_block(root, blocknr);
	182	if (bh) {
	183	if (buffer_uptodate(bh)) {
	184	u64 transid =
	185	root->fs_info->running_transaction->transid;
	186	header = btrfs_buffer_header(bh);
	187	if (btrfs_header_generation(header) ==
	188	transid) {
	189	btrfs_block_release(root, bh);
	190	return 0;
	191	}
	192	}
	193	btrfs_block_release(root, bh);
	194	}
	195	err = set_radix_bit(&root->fs_info->pinned_radix, blocknr);
	196	} else {
	197	err = set_radix_bit(&root->fs_info->pending_del_radix, blocknr);
	198	}
	199	BUG_ON(err);
	200	return 0;
	201	}
	202
	203	/*
	204	* remove an extent from the root, returns 0 on success
	205	*/
	206	static int __free_extent(struct btrfs_trans_handle *trans, struct btrfs_root
	207	*root, u64 blocknr, u64 num_blocks, int pin)
	208	{
	209	struct btrfs_path *path;
	210	struct btrfs_key key;
	211	struct btrfs_fs_info *info = root->fs_info;
	212	struct btrfs_root *extent_root = info->extent_root;
	213	int ret;
	214	struct btrfs_extent_item *ei;
	215	struct btrfs_key ins;
	216	u32 refs;
	217
	218	key.objectid = blocknr;
	219	key.flags = 0;
	220	btrfs_set_key_type(&key, BTRFS_EXTENT_ITEM_KEY);
	221	key.offset = num_blocks;
	222
	223	find_free_extent(trans, root, 0, 0, (u64)-1, &ins);
	224	path = btrfs_alloc_path();
	225	BUG_ON(!path);
	226	btrfs_init_path(path);
	227	ret = btrfs_search_slot(trans, extent_root, &key, path, -1, 1);
	228	if (ret) {
	229	printk("failed to find %Lu\n", key.objectid);
	230	btrfs_print_tree(extent_root, extent_root->node);
	231	printk("failed to find %Lu\n", key.objectid);
	232	BUG();
	233	}
	234	ei = btrfs_item_ptr(btrfs_buffer_leaf(path->nodes[0]), path->slots[0],
	235	struct btrfs_extent_item);
	236	BUG_ON(ei->refs == 0);
	237	refs = btrfs_extent_refs(ei) - 1;
	238	btrfs_set_extent_refs(ei, refs);
	239	btrfs_mark_buffer_dirty(path->nodes[0]);
	240	if (refs == 0) {
	241	u64 super_blocks_used;
	242
	243	if (pin) {
	244	ret = pin_down_block(root, blocknr, 0);
	245	BUG_ON(ret);
	246	}
	247
	248	super_blocks_used = btrfs_super_blocks_used(info->disk_super);
	249	btrfs_set_super_blocks_used(info->disk_super,
	250	super_blocks_used - num_blocks);
	251	ret = btrfs_del_item(trans, extent_root, path);
	252	if (ret)
	253	BUG();
	254	}
	255	btrfs_release_path(extent_root, path);
	256	btrfs_free_path(path);
	257	finish_current_insert(trans, extent_root);
	258	return ret;
	259	}
	260
	261	/*
	262	* find all the blocks marked as pending in the radix tree and remove
	263	* them from the extent map
	264	*/
	265	static int del_pending_extents(struct btrfs_trans_handle *trans, struct
	266	btrfs_root *extent_root)
	267	{
	268	int ret;
	269	int wret;
	270	int err = 0;
	271	unsigned long gang[4];
	272	int i;
	273	struct radix_tree_root *pending_radix;
	274	struct radix_tree_root *pinned_radix;
	275
	276	pending_radix = &extent_root->fs_info->pending_del_radix;
	277	pinned_radix = &extent_root->fs_info->pinned_radix;
	278
	279	while(1) {
	280	ret = find_first_radix_bit(pending_radix, gang,
	281	ARRAY_SIZE(gang));
	282	if (!ret)
	283	break;
	284	for (i = 0; i < ret; i++) {
	285	wret = set_radix_bit(pinned_radix, gang[i]);
	286	BUG_ON(wret);
	287	wret = clear_radix_bit(pending_radix, gang[i]);
	288	BUG_ON(wret);
	289	wret = __free_extent(trans, extent_root,
	290	gang[i], 1, 0);
	291	if (wret)
	292	err = wret;
	293	}
	294	}
	295	return err;
	296	}
	297
	298	/*
	299	* remove an extent from the root, returns 0 on success
	300	*/
	301	int btrfs_free_extent(struct btrfs_trans_handle *trans, struct btrfs_root
	302	*root, u64 blocknr, u64 num_blocks, int pin)
	303	{
	304	struct btrfs_root *extent_root = root->fs_info->extent_root;
	305	int pending_ret;
	306	int ret;
	307
	308	if (root == extent_root) {
	309	pin_down_block(root, blocknr, 1);
	310	return 0;
	311	}
	312	ret = __free_extent(trans, root, blocknr, num_blocks, pin);
	313	pending_ret = del_pending_extents(trans, root->fs_info->extent_root);
	314	return ret ? ret : pending_ret;
	315	}
	316
	317	/*
	318	* walks the btree of allocated extents and find a hole of a given size.
	319	* The key ins is changed to record the hole:
	320	* ins->objectid == block start
	321	* ins->flags = BTRFS_EXTENT_ITEM_KEY
	322	* ins->offset == number of blocks
	323	* Any available blocks before search_start are skipped.
	324	*/
	325	static int find_free_extent(struct btrfs_trans_handle *trans, struct btrfs_root
	326	*orig_root, u64 num_blocks, u64 search_start, u64
	327	search_end, struct btrfs_key *ins)
	328	{
	329	struct btrfs_path *path;
	330	struct btrfs_key key;
	331	int ret;
	332	u64 hole_size = 0;
	333	int slot = 0;
	334	u64 last_block = 0;
	335	u64 test_block;
	336	int start_found;
	337	struct btrfs_leaf *l;
	338	struct btrfs_root * root = orig_root->fs_info->extent_root;
	339	int total_needed = num_blocks;
	340	int level;
	341
	342	level = btrfs_header_level(btrfs_buffer_header(root->node));
	343	total_needed += (level + 1) * 3;
	344	if (root->fs_info->last_insert.objectid > search_start)
	345	search_start = root->fs_info->last_insert.objectid;
	346
	347	ins->flags = 0;
	348	btrfs_set_key_type(ins, BTRFS_EXTENT_ITEM_KEY);
	349	path = btrfs_alloc_path();
	350
	351	check_failed:
	352	btrfs_init_path(path);
	353	ins->objectid = search_start;
	354	ins->offset = 0;
	355	start_found = 0;
	356	ret = btrfs_search_slot(trans, root, ins, path, 0, 0);
	357	if (ret < 0)
	358	goto error;
	359
	360	if (path->slots[0] > 0)
	361	path->slots[0]--;
	362
	363	while (1) {
	364	l = btrfs_buffer_leaf(path->nodes[0]);
	365	slot = path->slots[0];
	366	if (slot >= btrfs_header_nritems(&l->header)) {
	367	ret = btrfs_next_leaf(root, path);
	368	if (ret == 0)
	369	continue;
	370	if (ret < 0)
	371	goto error;
	372	if (!start_found) {
	373	ins->objectid = search_start;
	374	ins->offset = (u64)-1;
	375	start_found = 1;
	376	goto check_pending;
	377	}
	378	ins->objectid = last_block > search_start ?
	379	last_block : search_start;
	380	ins->offset = (u64)-1;
	381	goto check_pending;
	382	}
	383	btrfs_disk_key_to_cpu(&key, &l->items[slot].key);
	384	if (key.objectid >= search_start) {
	385	if (start_found) {
	386	if (last_block < search_start)
	387	last_block = search_start;
	388	hole_size = key.objectid - last_block;
	389	if (hole_size > total_needed) {
	390	ins->objectid = last_block;
	391	ins->offset = hole_size;
	392	goto check_pending;
	393	}
	394	}
	395	}
	396	start_found = 1;
	397	last_block = key.objectid + key.offset;
	398	path->slots[0]++;
	399	}
	400	// FIXME -ENOSPC
	401	check_pending:
	402	/* we have to make sure we didn't find an extent that has already
	403	* been allocated by the map tree or the original allocation
	404	*/
	405	btrfs_release_path(root, path);
	406	BUG_ON(ins->objectid < search_start);
	407	for (test_block = ins->objectid;
	408	test_block < ins->objectid + total_needed; test_block++) {
	409	if (test_radix_bit(&root->fs_info->pinned_radix,
	410	test_block)) {
	411	search_start = test_block + 1;
	412	goto check_failed;
	413	}
	414	}
	415	BUG_ON(root->fs_info->current_insert.offset);
	416	root->fs_info->current_insert.offset = total_needed - num_blocks;
	417	root->fs_info->current_insert.objectid = ins->objectid + num_blocks;
	418	root->fs_info->current_insert.flags = 0;
	419	root->fs_info->last_insert.objectid = ins->objectid;
	420	ins->offset = num_blocks;
	421	btrfs_free_path(path);
	422	return 0;
	423	error:
	424	btrfs_release_path(root, path);
	425	btrfs_free_path(path);
	426	return ret;
	427	}
	428
	429	/*
	430	* finds a free extent and does all the dirty work required for allocation
	431	* returns the key for the extent through ins, and a tree buffer for
	432	* the first block of the extent through buf.
	433	*
	434	* returns 0 if everything worked, non-zero otherwise.
	435	*/
	436	int btrfs_alloc_extent(struct btrfs_trans_handle *trans, struct btrfs_root
	437	*root, u64 num_blocks, u64 search_start, u64
	438	search_end, u64 owner, struct btrfs_key *ins)
	439	{
	440	int ret;
	441	int pending_ret;
	442	u64 super_blocks_used;
	443	struct btrfs_fs_info *info = root->fs_info;
	444	struct btrfs_root *extent_root = info->extent_root;
	445	struct btrfs_extent_item extent_item;
	446
	447	btrfs_set_extent_refs(&extent_item, 1);
	448	btrfs_set_extent_owner(&extent_item, owner);
	449
	450	if (root == extent_root) {
	451	BUG_ON(extent_root->fs_info->current_insert.offset == 0);
	452	BUG_ON(num_blocks != 1);
	453	BUG_ON(extent_root->fs_info->current_insert.flags ==
	454	extent_root->fs_info->current_insert.offset);
	455	ins->offset = 1;
	456	ins->objectid = extent_root->fs_info->current_insert.objectid +
	457	extent_root->fs_info->current_insert.flags++;
	458	return 0;
	459	}
	460	ret = find_free_extent(trans, root, num_blocks, search_start,
	461	search_end, ins);
	462	if (ret)
	463	return ret;
	464
	465	super_blocks_used = btrfs_super_blocks_used(info->disk_super);
	466	btrfs_set_super_blocks_used(info->disk_super, super_blocks_used +
	467	num_blocks);
	468	ret = btrfs_insert_item(trans, extent_root, ins, &extent_item,
	469	sizeof(extent_item));
	470
	471	finish_current_insert(trans, extent_root);
	472	pending_ret = del_pending_extents(trans, extent_root);
	473	if (ret)
	474	return ret;
	475	if (pending_ret)
	476	return pending_ret;
	477	return 0;
	478	}
	479
	480	/*
	481	* helper function to allocate a block for a given tree
	482	* returns the tree buffer or NULL.
	483	*/
	484	struct buffer_head btrfs_alloc_free_block(struct btrfs_trans_handle trans,
	485	struct btrfs_root *root)
	486	{
	487	struct btrfs_key ins;
	488	int ret;
	489	struct buffer_head *buf;
	490
	491	ret = btrfs_alloc_extent(trans, root, 1, 0, (unsigned long)-1,
	492	btrfs_header_parentid(btrfs_buffer_header(root->node)), &ins);
	493	if (ret) {
	494	BUG();
	495	return NULL;
	496	}
	497	buf = btrfs_find_create_tree_block(root, ins.objectid);
	498	set_buffer_uptodate(buf);
	499	return buf;
	500	}
	501
	502	static int drop_leaf_ref(struct btrfs_trans_handle *trans,
	503	struct btrfs_root root, struct buffer_head cur)
	504	{
	505	struct btrfs_disk_key *key;
	506	struct btrfs_leaf *leaf;
	507	struct btrfs_file_extent_item *fi;
	508	int i;
	509	int nritems;
	510	int ret;
	511
	512	BUG_ON(!btrfs_is_leaf(btrfs_buffer_node(cur)));
	513	leaf = btrfs_buffer_leaf(cur);
	514	nritems = btrfs_header_nritems(&leaf->header);
	515	for (i = 0; i < nritems; i++) {
	516	key = &leaf->items[i].key;
	517	if (btrfs_disk_key_type(key) != BTRFS_EXTENT_DATA_KEY)
	518	continue;
	519	fi = btrfs_item_ptr(leaf, i, struct btrfs_file_extent_item);
	520	/*
	521	* FIXME make sure to insert a trans record that
	522	* repeats the snapshot del on crash
	523	*/
	524	ret = btrfs_free_extent(trans, root,
	525	btrfs_file_extent_disk_blocknr(fi),
	526	btrfs_file_extent_disk_num_blocks(fi),
	527	0);
	528	BUG_ON(ret);
	529	}
	530	return 0;
	531	}
	532
	533	/*
	534	* helper function for drop_snapshot, this walks down the tree dropping ref
	535	* counts as it goes.
	536	*/
	537	static int walk_down_tree(struct btrfs_trans_handle *trans, struct btrfs_root
	538	root, struct btrfs_path path, int *level)
	539	{
	540	struct buffer_head *next;
	541	struct buffer_head *cur;
	542	u64 blocknr;
	543	int ret;
	544	u32 refs;
	545
	546	WARN_ON(*level < 0);
	547	WARN_ON(*level >= BTRFS_MAX_LEVEL);
	548	ret = lookup_block_ref(trans, root, path->nodes[*level]->b_blocknr,
	549	1, &refs);
	550	BUG_ON(ret);
	551	if (refs > 1)
	552	goto out;
	553	/*
	554	* walk down to the last node level and free all the leaves
	555	*/
	556	while(*level >= 0) {
	557	WARN_ON(*level < 0);
	558	WARN_ON(*level >= BTRFS_MAX_LEVEL);
	559	cur = path->nodes[*level];
	560	if (btrfs_header_level(btrfs_buffer_header(cur)) != *level)
	561	WARN_ON(1);
	562	if (path->slots[*level] >=
	563	btrfs_header_nritems(btrfs_buffer_header(cur)))
	564	break;
	565	if (*level == 0) {
	566	ret = drop_leaf_ref(trans, root, cur);
	567	BUG_ON(ret);
	568	break;
	569	}
	570	blocknr = btrfs_node_blockptr(btrfs_buffer_node(cur),
	571	path->slots[*level]);
	572	ret = lookup_block_ref(trans, root, blocknr, 1, &refs);
	573	BUG_ON(ret);
	574	if (refs != 1) {
	575	path->slots[*level]++;
	576	ret = btrfs_free_extent(trans, root, blocknr, 1, 1);
	577	BUG_ON(ret);
	578	continue;
	579	}
	580	next = read_tree_block(root, blocknr);
	581	WARN_ON(*level <= 0);
	582	if (path->nodes[*level-1])
	583	btrfs_block_release(root, path->nodes[*level-1]);
	584	path->nodes[*level-1] = next;
	585	*level = btrfs_header_level(btrfs_buffer_header(next));
	586	path->slots[*level] = 0;
	587	}
	588	out:
	589	WARN_ON(*level < 0);
	590	WARN_ON(*level >= BTRFS_MAX_LEVEL);
	591	ret = btrfs_free_extent(trans, root,
	592	path->nodes[*level]->b_blocknr, 1, 1);
	593	btrfs_block_release(root, path->nodes[*level]);
	594	path->nodes[*level] = NULL;
	595	*level += 1;
	596	BUG_ON(ret);
	597	return 0;
	598	}
	599
	600	/*
	601	* helper for dropping snapshots. This walks back up the tree in the path
	602	* to find the first node higher up where we haven't yet gone through
	603	* all the slots
	604	*/
	605	static int walk_up_tree(struct btrfs_trans_handle *trans, struct btrfs_root
	606	root, struct btrfs_path path, int *level)
	607	{
	608	int i;
	609	int slot;
	610	int ret;
	611	for(i = *level; i < BTRFS_MAX_LEVEL - 1 && path->nodes[i]; i++) {
	612	slot = path->slots[i];
	613	if (slot < btrfs_header_nritems(
	614	btrfs_buffer_header(path->nodes[i])) - 1) {
	615	path->slots[i]++;
	616	*level = i;
	617	return 0;
	618	} else {
	619	ret = btrfs_free_extent(trans, root,
	620	path->nodes[*level]->b_blocknr,
	621	1, 1);
	622	BUG_ON(ret);
	623	btrfs_block_release(root, path->nodes[*level]);
	624	path->nodes[*level] = NULL;
	625	*level = i + 1;
	626	}
	627	}
	628	return 1;
	629	}
	630
	631	/*
	632	* drop the reference count on the tree rooted at 'snap'. This traverses
	633	* the tree freeing any blocks that have a ref count of zero after being
	634	* decremented.
	635	*/
	636	int btrfs_drop_snapshot(struct btrfs_trans_handle *trans, struct btrfs_root
	637	root, struct buffer_head snap)
	638	{
	639	int ret = 0;
	640	int wret;
	641	int level;
	642	struct btrfs_path *path;
	643	int i;
	644	int orig_level;
	645
	646	path = btrfs_alloc_path();
	647	BUG_ON(!path);
	648	btrfs_init_path(path);
	649
	650	level = btrfs_header_level(btrfs_buffer_header(snap));
	651	orig_level = level;
	652	path->nodes[level] = snap;
	653	path->slots[level] = 0;
	654	while(1) {
	655	wret = walk_down_tree(trans, root, path, &level);
	656	if (wret > 0)
	657	break;
	658	if (wret < 0)
	659	ret = wret;
	660
	661	wret = walk_up_tree(trans, root, path, &level);
	662	if (wret > 0)
	663	break;
	664	if (wret < 0)
	665	ret = wret;
	666	}
	667	for (i = 0; i <= orig_level; i++) {
	668	if (path->nodes[i]) {
	669	btrfs_block_release(root, path->nodes[i]);
	670	}
	671	}
	672	btrfs_free_path(path);
	673	return ret;
	674	}