void btrfs_print_tree(struct btrfs_root *root, struct extent_buffer *eb, int follow)
{
	int i;
	u32 nr;
	u32 size;
	struct btrfs_disk_key disk_key;
	struct btrfs_key key;

	if (!eb)
		return;
	nr = btrfs_header_nritems(eb);
	if (btrfs_is_leaf(eb)) {
		btrfs_print_leaf(root, eb);
		return;
	}
	printf("node %llu level %d items %d free %u generation %llu owner %llu\n",
	       (unsigned long long)eb->start,
	        btrfs_header_level(eb), nr,
		(u32)BTRFS_NODEPTRS_PER_BLOCK(root) - nr,
		(unsigned long long)btrfs_header_generation(eb),
		(unsigned long long)btrfs_header_owner(eb));
	print_uuids(eb);
	fflush(stdout);
	size = btrfs_level_size(root, btrfs_header_level(eb) - 1);
	for (i = 0; i < nr; i++) {
		u64 blocknr = btrfs_node_blockptr(eb, i);
		btrfs_node_key(eb, &disk_key, i);
		btrfs_disk_key_to_cpu(&key, &disk_key);
		printf("\t");
		btrfs_print_key(&disk_key);
		printf(" block %llu (%llu) gen %llu\n",
		       (unsigned long long)blocknr,
		       (unsigned long long)blocknr / size,
		       (unsigned long long)btrfs_node_ptr_generation(eb, i));
		fflush(stdout);
	}
	if (!follow)
		return;

	for (i = 0; i < nr; i++) {
		struct extent_buffer *next = read_tree_block(root,
					     btrfs_node_blockptr(eb, i),
					     size,
					     btrfs_node_ptr_generation(eb, i));
		if (!next) {
			fprintf(stderr, "failed to read %llu in tree %llu\n",
				(unsigned long long)btrfs_node_blockptr(eb, i),
				(unsigned long long)btrfs_header_owner(eb));
			continue;
		}
		if (btrfs_is_leaf(next) &&
		    btrfs_header_level(eb) != 1)
			BUG();
		if (btrfs_header_level(next) !=
			btrfs_header_level(eb) - 1)
			BUG();
		btrfs_print_tree(root, next, 1);
		free_extent_buffer(next);
	}
}

static int __inode_info(u64 inum, u64 ioff, u8 key_type,
			struct btrfs_root *fs_root, struct btrfs_path *path,
			struct btrfs_key *found_key)
{
	int ret;
	struct btrfs_key key;
	struct extent_buffer *eb;

	key.type = key_type;
	key.objectid = inum;
	key.offset = ioff;

	ret = btrfs_search_slot(NULL, fs_root, &key, path, 0, 0);
	if (ret < 0)
		return ret;

	eb = path->nodes[0];
	if (ret && path->slots[0] >= btrfs_header_nritems(eb)) {
		ret = btrfs_next_leaf(fs_root, path);
		if (ret)
			return ret;
		eb = path->nodes[0];
	}

	btrfs_item_key_to_cpu(eb, found_key, path->slots[0]);
	if (found_key->type != key.type || found_key->objectid != key.objectid)
		return 1;

	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(&path->nodes[i]->node.header)- 1) {
			path->slots[i]++;
			*level = i;
			return 0;
		} else {
			ret = btrfs_free_extent(trans, root,
						path->nodes[*level]->blocknr,
						1, 1);
			btrfs_block_release(root, path->nodes[*level]);
			path->nodes[*level] = NULL;
			*level = i + 1;
			BUG_ON(ret);
		}
	}
	return 1;
}

static void print_extents(struct btrfs_root *root, struct extent_buffer *eb)
{
    int i;
    u32 nr;
    u32 size;

    if (!eb)
        return;

    if (btrfs_is_leaf(eb)) {
        btrfs_print_leaf(root, eb);
        return;
    }

    size = btrfs_level_size(root, btrfs_header_level(eb) - 1);
    nr = btrfs_header_nritems(eb);
    for (i = 0; i < nr; i++) {
        struct extent_buffer *next = read_tree_block(root,
                                     btrfs_node_blockptr(eb, i),
                                     size,
                                     btrfs_node_ptr_generation(eb, i));
        if (!extent_buffer_uptodate(next))
            continue;
        if (btrfs_is_leaf(next) &&
                btrfs_header_level(eb) != 1)
            BUG();
        if (btrfs_header_level(next) !=
                btrfs_header_level(eb) - 1)
            BUG();
        print_extents(root, next);
        free_extent_buffer(next);
    }
}

struct btrfs_dir_item *
btrfs_search_dir_index_item(struct btrfs_root *root,
			    struct btrfs_path *path, u64 dirid,
			    const char *name, int name_len)
{
	struct extent_buffer *leaf;
	struct btrfs_dir_item *di;
	struct btrfs_key key;
	u32 nritems;
	int ret;

	key.objectid = dirid;
	key.type = BTRFS_DIR_INDEX_KEY;
	key.offset = 0;

	ret = btrfs_search_slot(NULL, root, &key, path, 0, 0);
	if (ret < 0)
		return ERR_PTR(ret);

	leaf = path->nodes[0];
	nritems = btrfs_header_nritems(leaf);

	while (1) {
		if (path->slots[0] >= nritems) {
			ret = btrfs_next_leaf(root, path);
			if (ret < 0)
				return ERR_PTR(ret);
			if (ret > 0)
				break;
			leaf = path->nodes[0];
			nritems = btrfs_header_nritems(leaf);
			continue;
		}

		btrfs_item_key_to_cpu(leaf, &key, path->slots[0]);
		if (key.objectid != dirid || key.type != BTRFS_DIR_INDEX_KEY)
			break;

		di = btrfs_match_dir_item_name(root->fs_info, path,
					       name, name_len);
		if (di)
			return di;

		path->slots[0]++;
	}
	return NULL;
}

static int next_leaf(struct btrfs_root *root, struct btrfs_path *path)
{
	int slot;
	int level = 1;
	int offset = 1;
	struct extent_buffer *c;
	struct extent_buffer *next = NULL;
	struct btrfs_fs_info *fs_info = root->fs_info;

again:
	for (; level < BTRFS_MAX_LEVEL; level++) {
		if (path->nodes[level])
			break;
	}

	if (level >= BTRFS_MAX_LEVEL)
		return 1;

	slot = path->slots[level] + 1;

	while(level < BTRFS_MAX_LEVEL) {
		if (!path->nodes[level])
			return 1;

		slot = path->slots[level] + offset;
		c = path->nodes[level];
		if (slot >= btrfs_header_nritems(c)) {
			level++;
			if (level == BTRFS_MAX_LEVEL)
				return 1;
			offset = 1;
			continue;
		}

		if (path->reada)
			reada_for_search(fs_info, path, level, slot, 0);

		next = read_node_slot(fs_info, c, slot);
		if (extent_buffer_uptodate(next))
			break;
		offset++;
	}
	path->slots[level] = slot;
	while(1) {
		level--;
		c = path->nodes[level];
		free_extent_buffer(c);
		path->nodes[level] = next;
		path->slots[level] = 0;
		if (!level)
			break;
		if (path->reada)
			reada_for_search(fs_info, path, level, 0, 0);
		next = read_node_slot(fs_info, next, 0);
		if (!extent_buffer_uptodate(next))
			goto again;
	}
	return 0;
}

int next_leaf(struct btrfs_root *root, struct btrfs_path *path)
{
	int slot;
	int level = 1;
	struct extent_buffer *c;
	struct extent_buffer *next = NULL;

	for (; level < BTRFS_MAX_LEVEL; level++) {
		if (path->nodes[level])
			break;
	}

	if (level == BTRFS_MAX_LEVEL)
		return 1;

	slot = path->slots[level] + 1;

	while(level < BTRFS_MAX_LEVEL) {
		if (!path->nodes[level])
			return 1;

		slot = path->slots[level] + 1;
		c = path->nodes[level];
		if (slot >= btrfs_header_nritems(c)) {
			level++;
			if (level == BTRFS_MAX_LEVEL)
				return 1;
			continue;
		}

		if (next)
			free_extent_buffer(next);

		if (path->reada)
			reada_for_search(root, path, level, slot, 0);

		next = read_node_slot(root, c, slot);
		break;
	}
	path->slots[level] = slot;
	while(1) {
		level--;
		c = path->nodes[level];
		free_extent_buffer(c);
		path->nodes[level] = next;
		path->slots[level] = 0;
		if (!level)
			break;
		if (path->reada)
			reada_for_search(root, path, level, 0, 0);
		next = read_node_slot(root, next, 0);
	}
	return 0;
}

int btrfs_find_orphan_roots(struct btrfs_root *tree_root)
{
	struct extent_buffer *leaf;
	struct btrfs_path *path;
	struct btrfs_key key;
	int err = 0;
	int ret;

	path = btrfs_alloc_path();
	if (!path)
		return -ENOMEM;

	key.objectid = BTRFS_ORPHAN_OBJECTID;
	key.type = BTRFS_ORPHAN_ITEM_KEY;
	key.offset = 0;

	while (1) {
		ret = btrfs_search_slot(NULL, tree_root, &key, path, 0, 0);
		if (ret < 0) {
			err = ret;
			break;
		}

		leaf = path->nodes[0];
		if (path->slots[0] >= btrfs_header_nritems(leaf)) {
			ret = btrfs_next_leaf(tree_root, path);
			if (ret < 0)
				err = ret;
			if (ret != 0)
				break;
			leaf = path->nodes[0];
		}

		btrfs_item_key_to_cpu(leaf, &key, path->slots[0]);
		btrfs_release_path(tree_root, path);

		if (key.objectid != BTRFS_ORPHAN_OBJECTID ||
		    key.type != BTRFS_ORPHAN_ITEM_KEY)
			break;

		ret = btrfs_find_dead_roots(tree_root, key.offset);
		if (ret) {
			err = ret;
			break;
		}

		key.offset++;
	}

	btrfs_free_path(path);
	return err;
}

/*
 * 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 btrfs_buffer *next;
	struct btrfs_buffer *cur;
	u64 blocknr;
	int ret;
	u32 refs;

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

int btrfs_inc_ref(struct btrfs_trans_handle *trans, struct btrfs_root *root,
		  struct btrfs_buffer *buf)
{
	u64 blocknr;
	int i;

	if (!root->ref_cows)
		return 0;
	if (btrfs_is_leaf(&buf->node))
		return 0;

	for (i = 0; i < btrfs_header_nritems(&buf->node.header); i++) {
		blocknr = btrfs_node_blockptr(&buf->node, i);
		inc_block_ref(trans, root, blocknr);
	}
	return 0;
}

void btrfs_print_tree(struct btrfs_fs_info *fs_info, struct extent_buffer *c)
{
	int i; u32 nr;
	struct btrfs_key key;
	int level;

	if (!c)
		return;
	nr = btrfs_header_nritems(c);
	level = btrfs_header_level(c);
	if (level == 0) {
		btrfs_print_leaf(fs_info, c);
		return;
	}
	btrfs_info(fs_info,
		   "node %llu level %d total ptrs %d free spc %u",
		   btrfs_header_bytenr(c), level, nr,
		   (u32)BTRFS_NODEPTRS_PER_BLOCK(fs_info) - nr);
	for (i = 0; i < nr; i++) {
		btrfs_node_key_to_cpu(c, &key, i);
		pr_info("\tkey %d (%llu %u %llu) block %llu\n",
		       i, key.objectid, key.type, key.offset,
		       btrfs_node_blockptr(c, i));
	}
	for (i = 0; i < nr; i++) {
		struct extent_buffer *next = read_tree_block(fs_info,
					btrfs_node_blockptr(c, i),
					btrfs_node_ptr_generation(c, i));
		if (IS_ERR(next)) {
			continue;
		} else if (!extent_buffer_uptodate(next)) {
			free_extent_buffer(next);
			continue;
		}

		if (btrfs_is_leaf(next) &&
		   level != 1)
			BUG();
		if (btrfs_header_level(next) !=
		       level - 1)
			BUG();
		btrfs_print_tree(fs_info, next);
		free_extent_buffer(next);
	}
}

void btrfs_print_tree(struct btrfs_root *root, struct btrfs_buffer *t)
{
	unsigned int i;
	u32 nr;
	struct btrfs_node *c;

	if (!t)
		return;
	c = &t->node;
	nr = btrfs_header_nritems(&c->header);
	if (btrfs_is_leaf(c)) {
		btrfs_print_leaf(root, (struct btrfs_leaf *)c);
		return;
	}
	printf("node %llu level %d ptrs %d free %u generation %llu owner %llu\n",
	       (u64)t->blocknr,
	        btrfs_header_level(&c->header), nr,
		(u32)BTRFS_NODEPTRS_PER_BLOCK(root) - nr,
		(u64)btrfs_header_generation(&c->header),
		(u64)btrfs_header_owner(&c->header));
	fflush(stdout);
	for (i = 0; i < nr; i++) {
		printf("\tkey %d (%llu %x %llu) block %llu\n",
		       i,
		       (u64)c->ptrs[i].key.objectid,
		       c->ptrs[i].key.flags,
		       (u64)c->ptrs[i].key.offset,
		       (u64)btrfs_node_blockptr(c, i));
		fflush(stdout);
	}
	for (i = 0; i < nr; i++) {
		struct btrfs_buffer *next_buf = read_tree_block(root,
						btrfs_node_blockptr(c, i));
		struct btrfs_node *next = &next_buf->node;
		if (btrfs_is_leaf(next) &&
		    btrfs_header_level(&c->header) != 1)
			BUG();
		if (btrfs_header_level(&next->header) !=
			btrfs_header_level(&c->header) - 1)
			BUG();
		btrfs_print_tree(root, next_buf);
		btrfs_block_release(root, next_buf);
	}
}

/*
 * We can't use btrfs_next_item() in modify_free_space_bitmap() because
 * btrfs_next_leaf() doesn't get the path for writing. We can forgo the fancy
 * tree walking in btrfs_next_leaf() anyways because we know exactly what we're
 * looking for.
 */
static int free_space_next_bitmap(struct btrfs_trans_handle *trans,
                                  struct btrfs_root *root, struct btrfs_path *p)
{
    struct btrfs_key key;

    if (p->slots[0] + 1 < btrfs_header_nritems(p->nodes[0])) {
        p->slots[0]++;
        return 0;
    }

    btrfs_item_key_to_cpu(p->nodes[0], &key, p->slots[0]);
    btrfs_release_path(p);

    key.objectid += key.offset;
    key.type = (u8)-1;
    key.offset = (u64)-1;

    return btrfs_search_prev_slot(trans, root, &key, p, 0, 1);
}

void btrfs_print_tree(struct btrfs_root *root, struct extent_buffer *c)
{
	int i; u32 nr;
	struct btrfs_key key;
	int level;

	if (!c)
		return;
	nr = btrfs_header_nritems(c);
	level = btrfs_header_level(c);
	if (level == 0) {
		btrfs_print_leaf(root, c);
		return;
	}
	printk(KERN_INFO "node %llu level %d total ptrs %d free spc %u\n",
	       (unsigned long long)btrfs_header_bytenr(c),
	      level, nr,
	       (u32)BTRFS_NODEPTRS_PER_BLOCK(root) - nr);
	for (i = 0; i < nr; i++) {
		btrfs_node_key_to_cpu(c, &key, i);
		printk(KERN_INFO "\tkey %d (%llu %u %llu) block %llu\n",
		       i,
		       (unsigned long long)key.objectid,
		       key.type,
		       (unsigned long long)key.offset,
		       (unsigned long long)btrfs_node_blockptr(c, i));
	}
	for (i = 0; i < nr; i++) {
		struct extent_buffer *next = read_tree_block(root,
					btrfs_node_blockptr(c, i),
					btrfs_level_size(root, level - 1),
					btrfs_node_ptr_generation(c, i));
		if (btrfs_is_leaf(next) &&
		   level != 1)
			BUG();
		if (btrfs_header_level(next) !=
		       level - 1)
			BUG();
		btrfs_print_tree(root, next);
		free_extent_buffer(next);
	}
}

static int clear_free_space_tree(struct btrfs_trans_handle *trans,
                                 struct btrfs_root *root)
{
    struct btrfs_path *path;
    struct btrfs_key key;
    int nr;
    int ret;

    path = btrfs_alloc_path();
    if (!path)
        return -ENOMEM;

    path->leave_spinning = 1;

    key.objectid = 0;
    key.type = 0;
    key.offset = 0;

    while (1) {
        ret = btrfs_search_slot(trans, root, &key, path, -1, 1);
        if (ret < 0)
            goto out;

        nr = btrfs_header_nritems(path->nodes[0]);
        if (!nr)
            break;

        path->slots[0] = 0;
        ret = btrfs_del_items(trans, root, path, 0, nr);
        if (ret)
            goto out;

        btrfs_release_path(path);
    }

    ret = 0;
out:
    btrfs_free_path(path);
    return ret;
}

/*
 *  search forward for a root, starting with objectid 'search_start'
 *  if a root key is found, the objectid we find is filled into 'found_objectid'
 *  and 0 is returned.  < 0 is returned on error, 1 if there is nothing
 *  left in the tree.
 */
int btrfs_search_root(struct btrfs_root *root, u64 search_start,
		      u64 *found_objectid)
{
	struct btrfs_path *path;
	struct btrfs_key search_key;
	int ret;

	root = root->fs_info->tree_root;
	search_key.objectid = search_start;
	search_key.type = (u8)-1;
	search_key.offset = (u64)-1;

	path = btrfs_alloc_path();
	BUG_ON(!path);
again:
	ret = btrfs_search_slot(NULL, root, &search_key, path, 0, 0);
	if (ret < 0)
		goto out;
	if (ret == 0) {
		ret = 1;
		goto out;
	}
	if (path->slots[0] >= btrfs_header_nritems(path->nodes[0])) {
		ret = btrfs_next_leaf(root, path);
		if (ret)
			goto out;
	}
	btrfs_item_key_to_cpu(path->nodes[0], &search_key, path->slots[0]);
	if (search_key.type != BTRFS_ROOT_ITEM_KEY) {
		search_key.offset++;
		btrfs_release_path(root, path);
		goto again;
	}
	ret = 0;
	*found_objectid = search_key.objectid;

out:
	btrfs_free_path(path);
	return ret;
}

static int find_extent_in_eb(struct extent_buffer *eb, u64 wanted_disk_byte,
				u64 extent_item_pos,
				struct extent_inode_elem **eie)
{
	u64 disk_byte;
	struct btrfs_key key;
	struct btrfs_file_extent_item *fi;
	int slot;
	int nritems;
	int extent_type;
	int ret;

	/*
	 * from the shared data ref, we only have the leaf but we need
	 * the key. thus, we must look into all items and see that we
	 * find one (some) with a reference to our extent item.
	 */
	nritems = btrfs_header_nritems(eb);
	for (slot = 0; slot < nritems; ++slot) {
		btrfs_item_key_to_cpu(eb, &key, slot);
		if (key.type != BTRFS_EXTENT_DATA_KEY)
			continue;
		fi = btrfs_item_ptr(eb, slot, struct btrfs_file_extent_item);
		extent_type = btrfs_file_extent_type(eb, fi);
		if (extent_type == BTRFS_FILE_EXTENT_INLINE)
			continue;
		/* don't skip BTRFS_FILE_EXTENT_PREALLOC, we can handle that */
		disk_byte = btrfs_file_extent_disk_bytenr(eb, fi);
		if (disk_byte != wanted_disk_byte)
			continue;

		ret = check_extent_in_eb(&key, eb, fi, extent_item_pos, eie);
		if (ret < 0)
			return ret;
	}

	return 0;
}

int btrfs_csum_file_block(struct btrfs_trans_handle *trans,
			  struct btrfs_root *root, u64 alloc_end,
			  u64 bytenr, char *data, size_t len)
{
	int ret;
	struct btrfs_key file_key;
	struct btrfs_key found_key;
	u64 next_offset = (u64)-1;
	int found_next = 0;
	struct btrfs_path *path;
	struct btrfs_csum_item *item;
	struct extent_buffer *leaf = NULL;
	u64 csum_offset;
	u32 csum_result = ~(u32)0;
	u32 nritems;
	u32 ins_size;
	u16 csum_size =
		btrfs_super_csum_size(&root->fs_info->super_copy);

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

	file_key.objectid = BTRFS_EXTENT_CSUM_OBJECTID;
	file_key.offset = bytenr;
	file_key.type = BTRFS_EXTENT_CSUM_KEY;

	item = btrfs_lookup_csum(trans, root, path, bytenr, 1);
	if (!IS_ERR(item)) {
		leaf = path->nodes[0];
		goto found;
	}
	ret = PTR_ERR(item);
	if (ret == -EFBIG) {
		u32 item_size;
		/* we found one, but it isn't big enough yet */
		leaf = path->nodes[0];
		item_size = btrfs_item_size_nr(leaf, path->slots[0]);
		if ((item_size / csum_size) >= MAX_CSUM_ITEMS(root, csum_size)) {
			/* already at max size, make a new one */
			goto insert;
		}
	} else {
		int slot = path->slots[0] + 1;
		/* we didn't find a csum item, insert one */
		nritems = btrfs_header_nritems(path->nodes[0]);
		if (path->slots[0] >= nritems - 1) {
			ret = btrfs_next_leaf(root, path);
			if (ret == 1)
				found_next = 1;
			if (ret != 0)
				goto insert;
			slot = 0;
		}
		btrfs_item_key_to_cpu(path->nodes[0], &found_key, slot);
		if (found_key.objectid != BTRFS_EXTENT_CSUM_OBJECTID ||
		    found_key.type != BTRFS_EXTENT_CSUM_KEY) {
			found_next = 1;
			goto insert;
		}
		next_offset = found_key.offset;
		found_next = 1;
		goto insert;
	}

	/*
	 * at this point, we know the tree has an item, but it isn't big
	 * enough yet to put our csum in.  Grow it
	 */
	btrfs_release_path(root, path);
	ret = btrfs_search_slot(trans, root, &file_key, path,
				csum_size, 1);
	if (ret < 0)
		goto fail;
	if (ret == 0) {
		BUG();
	}
	if (path->slots[0] == 0) {
		goto insert;
	}
	path->slots[0]--;
	leaf = path->nodes[0];
	btrfs_item_key_to_cpu(leaf, &found_key, path->slots[0]);
	csum_offset = (file_key.offset - found_key.offset) / root->sectorsize;
	if (found_key.objectid != BTRFS_EXTENT_CSUM_OBJECTID ||
	    found_key.type != BTRFS_EXTENT_CSUM_KEY ||
	    csum_offset >= MAX_CSUM_ITEMS(root, csum_size)) {
		goto insert;
	}
	if (csum_offset >= btrfs_item_size_nr(leaf, path->slots[0]) /
	    csum_size) {
		u32 diff = (csum_offset + 1) * csum_size;
		diff = diff - btrfs_item_size_nr(leaf, path->slots[0]);
		if (diff != csum_size)
			goto insert;
		ret = btrfs_extend_item(trans, root, path, diff);
		BUG_ON(ret);
		goto csum;
	}

insert:
//.........这里部分代码省略.........

/*
 * this is very complex, but the basic idea is to drop all extents
 * in the range start - end.  hint_block is filled in with a block number
 * that would be a good hint to the block allocator for this file.
 *
 * If an extent intersects the range but is not entirely inside the range
 * it is either truncated or split.  Anything entirely inside the range
 * is deleted from the tree.
 */
int btrfs_drop_extents(struct btrfs_trans_handle *trans, struct inode *inode,
		       u64 start, u64 end, u64 *hint_byte, int drop_cache)
{
	struct btrfs_root *root = BTRFS_I(inode)->root;
	struct extent_buffer *leaf;
	struct btrfs_file_extent_item *fi;
	struct btrfs_path *path;
	struct btrfs_key key;
	struct btrfs_key new_key;
	u64 search_start = start;
	u64 disk_bytenr = 0;
	u64 num_bytes = 0;
	u64 extent_offset = 0;
	u64 extent_end = 0;
	int del_nr = 0;
	int del_slot = 0;
	int extent_type;
	int recow;
	int ret;

	if (drop_cache)
		btrfs_drop_extent_cache(inode, start, end - 1, 0);

	path = btrfs_alloc_path();
	if (!path)
		return -ENOMEM;

	while (1) {
		recow = 0;
		ret = btrfs_lookup_file_extent(trans, root, path, inode->i_ino,
					       search_start, -1);
		if (ret < 0)
			break;
		if (ret > 0 && path->slots[0] > 0 && search_start == start) {
			leaf = path->nodes[0];
			btrfs_item_key_to_cpu(leaf, &key, path->slots[0] - 1);
			if (key.objectid == inode->i_ino &&
			    key.type == BTRFS_EXTENT_DATA_KEY)
				path->slots[0]--;
		}
		ret = 0;
next_slot:
		leaf = path->nodes[0];
		if (path->slots[0] >= btrfs_header_nritems(leaf)) {
			BUG_ON(del_nr > 0);
			ret = btrfs_next_leaf(root, path);
			if (ret < 0)
				break;
			if (ret > 0) {
				ret = 0;
				break;
			}
			leaf = path->nodes[0];
			recow = 1;
		}

		btrfs_item_key_to_cpu(leaf, &key, path->slots[0]);
		if (key.objectid > inode->i_ino ||
		    key.type > BTRFS_EXTENT_DATA_KEY || key.offset >= end)
			break;

		fi = btrfs_item_ptr(leaf, path->slots[0],
				    struct btrfs_file_extent_item);
		extent_type = btrfs_file_extent_type(leaf, fi);

		if (extent_type == BTRFS_FILE_EXTENT_REG ||
		    extent_type == BTRFS_FILE_EXTENT_PREALLOC) {
			disk_bytenr = btrfs_file_extent_disk_bytenr(leaf, fi);
			num_bytes = btrfs_file_extent_disk_num_bytes(leaf, fi);
			extent_offset = btrfs_file_extent_offset(leaf, fi);
			extent_end = key.offset +
				btrfs_file_extent_num_bytes(leaf, fi);
		} else if (extent_type == BTRFS_FILE_EXTENT_INLINE) {
			extent_end = key.offset +
				btrfs_file_extent_inline_len(leaf, fi);
		} else {
			WARN_ON(1);
			extent_end = search_start;
		}

		if (extent_end <= search_start) {
			path->slots[0]++;
			goto next_slot;
		}

		search_start = max(key.offset, start);
		if (recow) {
			btrfs_release_path(root, path);
			continue;
		}

//.........这里部分代码省略.........

void btrfs_print_leaf(struct btrfs_root *root, struct extent_buffer *l)
{
	int i;
	char *str;
	struct btrfs_item *item;
	struct btrfs_dir_item *di;
	struct btrfs_inode_item *ii;
	struct btrfs_file_extent_item *fi;
	struct btrfs_block_group_item *bi;
	struct btrfs_extent_data_ref *dref;
	struct btrfs_shared_data_ref *sref;
	struct btrfs_inode_ref *iref;
	struct btrfs_inode_extref *iref2;
	struct btrfs_dev_extent *dev_extent;
	struct btrfs_disk_key disk_key;
	struct btrfs_block_group_item bg_item;
	struct btrfs_dir_log_item *dlog;
	struct btrfs_qgroup_info_item *qg_info;
	struct btrfs_qgroup_limit_item *qg_limit;
	struct btrfs_qgroup_status_item *qg_status;
	u32 nr = btrfs_header_nritems(l);
	u64 objectid;
	u32 type;

	printf("leaf %llu items %d free space %d generation %llu owner %llu\n",
		(unsigned long long)btrfs_header_bytenr(l), nr,
		btrfs_leaf_free_space(root, l),
		(unsigned long long)btrfs_header_generation(l),
		(unsigned long long)btrfs_header_owner(l));
	print_uuids(l);
	fflush(stdout);
	for (i = 0 ; i < nr ; i++) {
		item = btrfs_item_nr(l, i);
		btrfs_item_key(l, &disk_key, i);
		objectid = btrfs_disk_key_objectid(&disk_key);
		type = btrfs_disk_key_type(&disk_key);
		printf("\titem %d ", i);
		btrfs_print_key(&disk_key);
		printf(" itemoff %d itemsize %d\n",
			btrfs_item_offset(l, item),
			btrfs_item_size(l, item));

		if (type == 0 && objectid == BTRFS_FREE_SPACE_OBJECTID)
			print_free_space_header(l, i);

		switch (type) {
		case BTRFS_INODE_ITEM_KEY:
			ii = btrfs_item_ptr(l, i, struct btrfs_inode_item);
			printf("\t\tinode generation %llu transid %llu size %llu block group %llu mode %o links %u\n",
			       (unsigned long long)btrfs_inode_generation(l, ii),
			       (unsigned long long)btrfs_inode_transid(l, ii),
			       (unsigned long long)btrfs_inode_size(l, ii),
			       (unsigned long long)btrfs_inode_block_group(l,ii),
			       btrfs_inode_mode(l, ii),
			       btrfs_inode_nlink(l, ii));
			break;
		case BTRFS_INODE_REF_KEY:
			iref = btrfs_item_ptr(l, i, struct btrfs_inode_ref);
			print_inode_ref_item(l, item, iref);
			break;
		case BTRFS_INODE_EXTREF_KEY:
			iref2 = btrfs_item_ptr(l, i, struct btrfs_inode_extref);
			print_inode_extref_item(l, item, iref2);
			break;
		case BTRFS_DIR_ITEM_KEY:
		case BTRFS_DIR_INDEX_KEY:
		case BTRFS_XATTR_ITEM_KEY:
			di = btrfs_item_ptr(l, i, struct btrfs_dir_item);
			print_dir_item(l, item, di);
			break;
		case BTRFS_DIR_LOG_INDEX_KEY:
		case BTRFS_DIR_LOG_ITEM_KEY:
			dlog = btrfs_item_ptr(l, i, struct btrfs_dir_log_item);
			printf("\t\tdir log end %Lu\n",
			       (unsigned long long)btrfs_dir_log_end(l, dlog));
		       break;
		case BTRFS_ORPHAN_ITEM_KEY:
			printf("\t\torphan item\n");
			break;
		case BTRFS_ROOT_ITEM_KEY:
			print_root(l, i);
			break;
		case BTRFS_ROOT_REF_KEY:
			print_root_ref(l, i, "ref");
			break;
		case BTRFS_ROOT_BACKREF_KEY:
			print_root_ref(l, i, "backref");
			break;
		case BTRFS_EXTENT_ITEM_KEY:
			print_extent_item(l, i, 0);
			break;
		case BTRFS_METADATA_ITEM_KEY:
			print_extent_item(l, i, 1);
			break;
		case BTRFS_TREE_BLOCK_REF_KEY:
			printf("\t\ttree block backref\n");
			break;
		case BTRFS_SHARED_BLOCK_REF_KEY:
			printf("\t\tshared block backref\n");
			break;
//.........这里部分代码省略.........