[net-next-2.6.git] / fs / btrfs / extent_map.c

#include <linux/err.h>
#include <linux/slab.h>
#include <linux/module.h>
#include <linux/spinlock.h>
#include <linux/hardirq.h>
#include "extent_map.h"


static struct kmem_cache *extent_map_cache;

int __init extent_map_init(void)
{
	extent_map_cache = kmem_cache_create("extent_map",
			sizeof(struct extent_map), 0,
			SLAB_RECLAIM_ACCOUNT | SLAB_MEM_SPREAD, NULL);
	if (!extent_map_cache)
		return -ENOMEM;
	return 0;
}

void extent_map_exit(void)
{
	if (extent_map_cache)
		kmem_cache_destroy(extent_map_cache);
}

/**
 * extent_map_tree_init - initialize extent map tree
 * @tree:		tree to initialize
 * @mask:		flags for memory allocations during tree operations
 *
 * Initialize the extent tree @tree.  Should be called for each new inode
 * or other user of the extent_map interface.
 */
void extent_map_tree_init(struct extent_map_tree *tree, gfp_t mask)
{
	tree->map = RB_ROOT;
	rwlock_init(&tree->lock);
}

/**
 * alloc_extent_map - allocate new extent map structure
 * @mask:	memory allocation flags
 *
 * Allocate a new extent_map structure.  The new structure is
 * returned with a reference count of one and needs to be
 * freed using free_extent_map()
 */
struct extent_map *alloc_extent_map(gfp_t mask)
{
	struct extent_map *em;
	em = kmem_cache_alloc(extent_map_cache, mask);
	if (!em || IS_ERR(em))
		return em;
	em->in_tree = 0;
	em->flags = 0;
	atomic_set(&em->refs, 1);
	return em;
}

/**
 * free_extent_map - drop reference count of an extent_map
 * @em:		extent map beeing releasead
 *
 * Drops the reference out on @em by one and free the structure
 * if the reference count hits zero.
 */
void free_extent_map(struct extent_map *em)
{
	if (!em)
		return;
	WARN_ON(atomic_read(&em->refs) == 0);
	if (atomic_dec_and_test(&em->refs)) {
		WARN_ON(em->in_tree);
		kmem_cache_free(extent_map_cache, em);
	}
}

static struct rb_node *tree_insert(struct rb_root *root, u64 offset,
				   struct rb_node *node)
{
	struct rb_node **p = &root->rb_node;
	struct rb_node *parent = NULL;
	struct extent_map *entry;

	while (*p) {
		parent = *p;
		entry = rb_entry(parent, struct extent_map, rb_node);

		WARN_ON(!entry->in_tree);

		if (offset < entry->start)
			p = &(*p)->rb_left;
		else if (offset >= extent_map_end(entry))
			p = &(*p)->rb_right;
		else
			return parent;
	}

	entry = rb_entry(node, struct extent_map, rb_node);
	entry->in_tree = 1;
	rb_link_node(node, parent, p);
	rb_insert_color(node, root);
	return NULL;
}

/*
 * search through the tree for an extent_map with a given offset.  If
 * it can't be found, try to find some neighboring extents
 */
static struct rb_node *__tree_search(struct rb_root *root, u64 offset,
				     struct rb_node **prev_ret,
				     struct rb_node **next_ret)
{
	struct rb_node *n = root->rb_node;
	struct rb_node *prev = NULL;
	struct rb_node *orig_prev = NULL;
	struct extent_map *entry;
	struct extent_map *prev_entry = NULL;

	while (n) {
		entry = rb_entry(n, struct extent_map, rb_node);
		prev = n;
		prev_entry = entry;

		WARN_ON(!entry->in_tree);

		if (offset < entry->start)
			n = n->rb_left;
		else if (offset >= extent_map_end(entry))
			n = n->rb_right;
		else
			return n;
	}

	if (prev_ret) {
		orig_prev = prev;
		while (prev && offset >= extent_map_end(prev_entry)) {
			prev = rb_next(prev);
			prev_entry = rb_entry(prev, struct extent_map, rb_node);
		}
		*prev_ret = prev;
		prev = orig_prev;
	}

	if (next_ret) {
		prev_entry = rb_entry(prev, struct extent_map, rb_node);
		while (prev && offset < prev_entry->start) {
			prev = rb_prev(prev);
			prev_entry = rb_entry(prev, struct extent_map, rb_node);
		}
		*next_ret = prev;
	}
	return NULL;
}

/* check to see if two extent_map structs are adjacent and safe to merge */
static int mergable_maps(struct extent_map *prev, struct extent_map *next)
{
	if (test_bit(EXTENT_FLAG_PINNED, &prev->flags))
		return 0;

	/*
	 * don't merge compressed extents, we need to know their
	 * actual size
	 */
	if (test_bit(EXTENT_FLAG_COMPRESSED, &prev->flags))
		return 0;

	if (extent_map_end(prev) == next->start &&
	    prev->flags == next->flags &&
	    prev->bdev == next->bdev &&
	    ((next->block_start == EXTENT_MAP_HOLE &&
	      prev->block_start == EXTENT_MAP_HOLE) ||
	     (next->block_start == EXTENT_MAP_INLINE &&
	      prev->block_start == EXTENT_MAP_INLINE) ||
	     (next->block_start == EXTENT_MAP_DELALLOC &&
	      prev->block_start == EXTENT_MAP_DELALLOC) ||
	     (next->block_start < EXTENT_MAP_LAST_BYTE - 1 &&
	      next->block_start == extent_map_block_end(prev)))) {
		return 1;
	}
	return 0;
}

int unpin_extent_cache(struct extent_map_tree *tree, u64 start, u64 len)
{
	int ret = 0;
	struct extent_map *merge = NULL;
	struct rb_node *rb;
	struct extent_map *em;

	write_lock(&tree->lock);
	em = lookup_extent_mapping(tree, start, len);

	WARN_ON(!em || em->start != start);

	if (!em)
		goto out;

	clear_bit(EXTENT_FLAG_PINNED, &em->flags);

	if (em->start != 0) {
		rb = rb_prev(&em->rb_node);
		if (rb)
			merge = rb_entry(rb, struct extent_map, rb_node);
		if (rb && mergable_maps(merge, em)) {
			em->start = merge->start;
			em->len += merge->len;
			em->block_len += merge->block_len;
			em->block_start = merge->block_start;
			merge->in_tree = 0;
			rb_erase(&merge->rb_node, &tree->map);
			free_extent_map(merge);
		}
	}

	rb = rb_next(&em->rb_node);
	if (rb)
		merge = rb_entry(rb, struct extent_map, rb_node);
	if (rb && mergable_maps(em, merge)) {
		em->len += merge->len;
		em->block_len += merge->len;
		rb_erase(&merge->rb_node, &tree->map);
		merge->in_tree = 0;
		free_extent_map(merge);
	}

	free_extent_map(em);
out:
	write_unlock(&tree->lock);
	return ret;

}

/**
 * add_extent_mapping - add new extent map to the extent tree
 * @tree:	tree to insert new map in
 * @em:		map to insert
 *
 * Insert @em into @tree or perform a simple forward/backward merge with
 * existing mappings.  The extent_map struct passed in will be inserted
 * into the tree directly, with an additional reference taken, or a
 * reference dropped if the merge attempt was successfull.
 */
int add_extent_mapping(struct extent_map_tree *tree,
		       struct extent_map *em)
{
	int ret = 0;
	struct extent_map *merge = NULL;
	struct rb_node *rb;
	struct extent_map *exist;

	exist = lookup_extent_mapping(tree, em->start, em->len);
	if (exist) {
		free_extent_map(exist);
		ret = -EEXIST;
		goto out;
	}
	rb = tree_insert(&tree->map, em->start, &em->rb_node);
	if (rb) {
		ret = -EEXIST;
		goto out;
	}
	atomic_inc(&em->refs);
	if (em->start != 0) {
		rb = rb_prev(&em->rb_node);
		if (rb)
			merge = rb_entry(rb, struct extent_map, rb_node);
		if (rb && mergable_maps(merge, em)) {
			em->start = merge->start;
			em->len += merge->len;
			em->block_len += merge->block_len;
			em->block_start = merge->block_start;
			merge->in_tree = 0;
			rb_erase(&merge->rb_node, &tree->map);
			free_extent_map(merge);
		}
	 }
	rb = rb_next(&em->rb_node);
	if (rb)
		merge = rb_entry(rb, struct extent_map, rb_node);
	if (rb && mergable_maps(em, merge)) {
		em->len += merge->len;
		em->block_len += merge->len;
		rb_erase(&merge->rb_node, &tree->map);
		merge->in_tree = 0;
		free_extent_map(merge);
	}
out:
	return ret;
}

/* simple helper to do math around the end of an extent, handling wrap */
static u64 range_end(u64 start, u64 len)
{
	if (start + len < start)
		return (u64)-1;
	return start + len;
}

/**
 * lookup_extent_mapping - lookup extent_map
 * @tree:	tree to lookup in
 * @start:	byte offset to start the search
 * @len:	length of the lookup range
 *
 * Find and return the first extent_map struct in @tree that intersects the
 * [start, len] range.  There may be additional objects in the tree that
 * intersect, so check the object returned carefully to make sure that no
 * additional lookups are needed.
 */
struct extent_map *lookup_extent_mapping(struct extent_map_tree *tree,
					 u64 start, u64 len)
{
	struct extent_map *em;
	struct rb_node *rb_node;
	struct rb_node *prev = NULL;
	struct rb_node *next = NULL;
	u64 end = range_end(start, len);

	rb_node = __tree_search(&tree->map, start, &prev, &next);
	if (!rb_node && prev) {
		em = rb_entry(prev, struct extent_map, rb_node);
		if (end > em->start && start < extent_map_end(em))
			goto found;
	}
	if (!rb_node && next) {
		em = rb_entry(next, struct extent_map, rb_node);
		if (end > em->start && start < extent_map_end(em))
			goto found;
	}
	if (!rb_node) {
		em = NULL;
		goto out;
	}
	if (IS_ERR(rb_node)) {
		em = ERR_PTR(PTR_ERR(rb_node));
		goto out;
	}
	em = rb_entry(rb_node, struct extent_map, rb_node);
	if (end > em->start && start < extent_map_end(em))
		goto found;

	em = NULL;
	goto out;

found:
	atomic_inc(&em->refs);
out:
	return em;
}

/**
 * search_extent_mapping - find a nearby extent map
 * @tree:	tree to lookup in
 * @start:	byte offset to start the search
 * @len:	length of the lookup range
 *
 * Find and return the first extent_map struct in @tree that intersects the
 * [start, len] range.
 *
 * If one can't be found, any nearby extent may be returned
 */
struct extent_map *search_extent_mapping(struct extent_map_tree *tree,
					 u64 start, u64 len)
{
	struct extent_map *em;
	struct rb_node *rb_node;
	struct rb_node *prev = NULL;
	struct rb_node *next = NULL;

	rb_node = __tree_search(&tree->map, start, &prev, &next);
	if (!rb_node && prev) {
		em = rb_entry(prev, struct extent_map, rb_node);
		goto found;
	}
	if (!rb_node && next) {
		em = rb_entry(next, struct extent_map, rb_node);
		goto found;
	}
	if (!rb_node) {
		em = NULL;
		goto out;
	}
	if (IS_ERR(rb_node)) {
		em = ERR_PTR(PTR_ERR(rb_node));
		goto out;
	}
	em = rb_entry(rb_node, struct extent_map, rb_node);
	goto found;

	em = NULL;
	goto out;

found:
	atomic_inc(&em->refs);
out:
	return em;
}

/**
 * remove_extent_mapping - removes an extent_map from the extent tree
 * @tree:	extent tree to remove from
 * @em:		extent map beeing removed
 *
 * Removes @em from @tree.  No reference counts are dropped, and no checks
 * are done to see if the range is in use
 */
int remove_extent_mapping(struct extent_map_tree *tree, struct extent_map *em)
{
	int ret = 0;

	WARN_ON(test_bit(EXTENT_FLAG_PINNED, &em->flags));
	rb_erase(&em->rb_node, &tree->map);
	em->in_tree = 0;
	return ret;
}
Commit	Line	Data
d1310b2e	1	#include <linux/err.h>
d1310b2e	2	#include <linux/slab.h>
a52d9a80 CM	3	#include <linux/module.h>
a52d9a80 CM	4	#include <linux/spinlock.h>
d1310b2e	5	#include <linux/hardirq.h>
a52d9a80 CM	6	#include "extent_map.h"
a52d9a80 CM	7
86479a04	8
a52d9a80	9	static struct kmem_cache *extent_map_cache;
ca664626	10
2f4cbe64	11	int __init extent_map_init(void)
a52d9a80	12	{
9601e3f6 CH	13	extent_map_cache = kmem_cache_create("extent_map",
	14	sizeof(struct extent_map), 0,
	15	SLAB_RECLAIM_ACCOUNT \| SLAB_MEM_SPREAD, NULL);
2f4cbe64 WB	16	if (!extent_map_cache)
2f4cbe64 WB	17	return -ENOMEM;
2f4cbe64	18	return 0;
a52d9a80 CM	19	}
a52d9a80 CM	20
17636e03	21	void extent_map_exit(void)
a52d9a80	22	{
a52d9a80 CM	23	if (extent_map_cache)
a52d9a80 CM	24	kmem_cache_destroy(extent_map_cache);
a52d9a80 CM	25	}
a52d9a80 CM	26
9d2423c5 CH	27	/**
	28	* extent_map_tree_init - initialize extent map tree
	29	* @tree: tree to initialize
	30	* @mask: flags for memory allocations during tree operations
	31	*
	32	* Initialize the extent tree @tree. Should be called for each new inode
	33	* or other user of the extent_map interface.
	34	*/
d1310b2e	35	void extent_map_tree_init(struct extent_map_tree *tree, gfp_t mask)
a52d9a80	36	{
6bef4d31	37	tree->map = RB_ROOT;
890871be	38	rwlock_init(&tree->lock);
a52d9a80	39	}
a52d9a80	40
9d2423c5 CH	41	/**
	42	* alloc_extent_map - allocate new extent map structure
	43	* @mask: memory allocation flags
	44	*
	45	* Allocate a new extent_map structure. The new structure is
	46	* returned with a reference count of one and needs to be
	47	* freed using free_extent_map()
	48	*/
a52d9a80 CM	49	struct extent_map *alloc_extent_map(gfp_t mask)
	50	{
	51	struct extent_map *em;
	52	em = kmem_cache_alloc(extent_map_cache, mask);
	53	if (!em \|\| IS_ERR(em))
	54	return em;
	55	em->in_tree = 0;
d1310b2e	56	em->flags = 0;
a52d9a80 CM	57	atomic_set(&em->refs, 1);
	58	return em;
	59	}
a52d9a80	60
9d2423c5 CH	61	/**
	62	* free_extent_map - drop reference count of an extent_map
	63	* @em: extent map beeing releasead
	64	*
	65	* Drops the reference out on @em by one and free the structure
	66	* if the reference count hits zero.
	67	*/
a52d9a80 CM	68	void free_extent_map(struct extent_map *em)
a52d9a80 CM	69	{
2bf5a725 CM	70	if (!em)
2bf5a725 CM	71	return;
d1310b2e	72	WARN_ON(atomic_read(&em->refs) == 0);
a52d9a80 CM	73	if (atomic_dec_and_test(&em->refs)) {
	74	WARN_ON(em->in_tree);
	75	kmem_cache_free(extent_map_cache, em);
	76	}
	77	}
a52d9a80	78
a52d9a80 CM	79	static struct rb_node tree_insert(struct rb_root root, u64 offset,
	80	struct rb_node *node)
	81	{
d397712b CM	82	struct rb_node **p = &root->rb_node;
d397712b CM	83	struct rb_node *parent = NULL;
d1310b2e	84	struct extent_map *entry;
a52d9a80	85
d397712b	86	while (*p) {
a52d9a80	87	parent = *p;
d1310b2e CM	88	entry = rb_entry(parent, struct extent_map, rb_node);
	89
	90	WARN_ON(!entry->in_tree);
a52d9a80 CM	91
	92	if (offset < entry->start)
	93	p = &(*p)->rb_left;
d1310b2e	94	else if (offset >= extent_map_end(entry))
a52d9a80 CM	95	p = &(*p)->rb_right;
	96	else
	97	return parent;
	98	}
	99
d1310b2e	100	entry = rb_entry(node, struct extent_map, rb_node);
a52d9a80 CM	101	entry->in_tree = 1;
	102	rb_link_node(node, parent, p);
	103	rb_insert_color(node, root);
	104	return NULL;
	105	}
	106
d352ac68 CM	107	/*
	108	* search through the tree for an extent_map with a given offset. If
	109	* it can't be found, try to find some neighboring extents
	110	*/
a52d9a80	111	static struct rb_node __tree_search(struct rb_root root, u64 offset,
5f56406a CM	112	struct rb_node **prev_ret,
5f56406a CM	113	struct rb_node **next_ret)
a52d9a80	114	{
d397712b	115	struct rb_node *n = root->rb_node;
a52d9a80	116	struct rb_node *prev = NULL;
5f56406a	117	struct rb_node *orig_prev = NULL;
d1310b2e CM	118	struct extent_map *entry;
d1310b2e CM	119	struct extent_map *prev_entry = NULL;
a52d9a80	120
d397712b	121	while (n) {
d1310b2e	122	entry = rb_entry(n, struct extent_map, rb_node);
a52d9a80 CM	123	prev = n;
	124	prev_entry = entry;
	125
d1310b2e CM	126	WARN_ON(!entry->in_tree);
d1310b2e CM	127
a52d9a80 CM	128	if (offset < entry->start)
a52d9a80 CM	129	n = n->rb_left;
d1310b2e	130	else if (offset >= extent_map_end(entry))
a52d9a80 CM	131	n = n->rb_right;
	132	else
	133	return n;
	134	}
5f56406a CM	135
	136	if (prev_ret) {
	137	orig_prev = prev;
d397712b	138	while (prev && offset >= extent_map_end(prev_entry)) {
5f56406a	139	prev = rb_next(prev);
d1310b2e	140	prev_entry = rb_entry(prev, struct extent_map, rb_node);
5f56406a CM	141	}
	142	*prev_ret = prev;
	143	prev = orig_prev;
	144	}
	145
	146	if (next_ret) {
d1310b2e	147	prev_entry = rb_entry(prev, struct extent_map, rb_node);
d397712b	148	while (prev && offset < prev_entry->start) {
5f56406a	149	prev = rb_prev(prev);
d1310b2e	150	prev_entry = rb_entry(prev, struct extent_map, rb_node);
5f56406a CM	151	}
5f56406a CM	152	*next_ret = prev;
a52d9a80	153	}
a52d9a80 CM	154	return NULL;
	155	}
	156
d352ac68	157	/* check to see if two extent_map structs are adjacent and safe to merge */
d1310b2e	158	static int mergable_maps(struct extent_map prev, struct extent_map next)
a52d9a80	159	{
7f3c74fb CM	160	if (test_bit(EXTENT_FLAG_PINNED, &prev->flags))
	161	return 0;
	162
c8b97818 CM	163	/*
	164	* don't merge compressed extents, we need to know their
	165	* actual size
	166	*/
	167	if (test_bit(EXTENT_FLAG_COMPRESSED, &prev->flags))
	168	return 0;
	169
d1310b2e CM	170	if (extent_map_end(prev) == next->start &&
	171	prev->flags == next->flags &&
	172	prev->bdev == next->bdev &&
	173	((next->block_start == EXTENT_MAP_HOLE &&
	174	prev->block_start == EXTENT_MAP_HOLE) \|\|
	175	(next->block_start == EXTENT_MAP_INLINE &&
	176	prev->block_start == EXTENT_MAP_INLINE) \|\|
	177	(next->block_start == EXTENT_MAP_DELALLOC &&
	178	prev->block_start == EXTENT_MAP_DELALLOC) \|\|
	179	(next->block_start < EXTENT_MAP_LAST_BYTE - 1 &&
	180	next->block_start == extent_map_block_end(prev)))) {
	181	return 1;
	182	}
a52d9a80 CM	183	return 0;
	184	}
	185
a1ed835e CM	186	int unpin_extent_cache(struct extent_map_tree *tree, u64 start, u64 len)
	187	{
	188	int ret = 0;
	189	struct extent_map *merge = NULL;
	190	struct rb_node *rb;
	191	struct extent_map *em;
	192
	193	write_lock(&tree->lock);
	194	em = lookup_extent_mapping(tree, start, len);
	195
4eb3991c	196	WARN_ON(!em \|\| em->start != start);
a1ed835e CM	197
	198	if (!em)
	199	goto out;
	200
	201	clear_bit(EXTENT_FLAG_PINNED, &em->flags);
	202
	203	if (em->start != 0) {
	204	rb = rb_prev(&em->rb_node);
	205	if (rb)
	206	merge = rb_entry(rb, struct extent_map, rb_node);
	207	if (rb && mergable_maps(merge, em)) {
	208	em->start = merge->start;
	209	em->len += merge->len;
	210	em->block_len += merge->block_len;
	211	em->block_start = merge->block_start;
	212	merge->in_tree = 0;
	213	rb_erase(&merge->rb_node, &tree->map);
	214	free_extent_map(merge);
	215	}
	216	}
	217
	218	rb = rb_next(&em->rb_node);
	219	if (rb)
	220	merge = rb_entry(rb, struct extent_map, rb_node);
	221	if (rb && mergable_maps(em, merge)) {
	222	em->len += merge->len;
	223	em->block_len += merge->len;
	224	rb_erase(&merge->rb_node, &tree->map);
	225	merge->in_tree = 0;
	226	free_extent_map(merge);
	227	}
	228
	229	free_extent_map(em);
	230	out:
	231	write_unlock(&tree->lock);
	232	return ret;
	233
	234	}
	235
9d2423c5 CH	236	/**
	237	* add_extent_mapping - add new extent map to the extent tree
	238	* @tree: tree to insert new map in
	239	* @em: map to insert
	240	*
	241	* Insert @em into @tree or perform a simple forward/backward merge with
	242	* existing mappings. The extent_map struct passed in will be inserted
	243	* into the tree directly, with an additional reference taken, or a
af901ca1	244	* reference dropped if the merge attempt was successfull.
a52d9a80 CM	245	*/
	246	int add_extent_mapping(struct extent_map_tree *tree,
	247	struct extent_map *em)
	248	{
	249	int ret = 0;
d1310b2e	250	struct extent_map *merge = NULL;
a52d9a80	251	struct rb_node *rb;
7c2fe32a	252	struct extent_map *exist;
a52d9a80	253
7c2fe32a CM	254	exist = lookup_extent_mapping(tree, em->start, em->len);
	255	if (exist) {
	256	free_extent_map(exist);
	257	ret = -EEXIST;
	258	goto out;
	259	}
d1310b2e	260	rb = tree_insert(&tree->map, em->start, &em->rb_node);
a52d9a80	261	if (rb) {
a52d9a80 CM	262	ret = -EEXIST;
	263	goto out;
	264	}
	265	atomic_inc(&em->refs);
	266	if (em->start != 0) {
	267	rb = rb_prev(&em->rb_node);
	268	if (rb)
d1310b2e CM	269	merge = rb_entry(rb, struct extent_map, rb_node);
	270	if (rb && mergable_maps(merge, em)) {
	271	em->start = merge->start;
	272	em->len += merge->len;
c8b97818	273	em->block_len += merge->block_len;
d1310b2e CM	274	em->block_start = merge->block_start;
	275	merge->in_tree = 0;
	276	rb_erase(&merge->rb_node, &tree->map);
	277	free_extent_map(merge);
a52d9a80 CM	278	}
a52d9a80 CM	279	}
d1310b2e CM	280	rb = rb_next(&em->rb_node);
	281	if (rb)
	282	merge = rb_entry(rb, struct extent_map, rb_node);
	283	if (rb && mergable_maps(em, merge)) {
	284	em->len += merge->len;
c8b97818	285	em->block_len += merge->len;
d1310b2e CM	286	rb_erase(&merge->rb_node, &tree->map);
	287	merge->in_tree = 0;
	288	free_extent_map(merge);
	289	}
a52d9a80	290	out:
a52d9a80 CM	291	return ret;
a52d9a80 CM	292	}
a52d9a80	293
d352ac68	294	/* simple helper to do math around the end of an extent, handling wrap */
d1310b2e CM	295	static u64 range_end(u64 start, u64 len)
	296	{
	297	if (start + len < start)
	298	return (u64)-1;
	299	return start + len;
	300	}
	301
9d2423c5 CH	302	/**
	303	* lookup_extent_mapping - lookup extent_map
	304	* @tree: tree to lookup in
	305	* @start: byte offset to start the search
	306	* @len: length of the lookup range
	307	*
	308	* Find and return the first extent_map struct in @tree that intersects the
	309	* [start, len] range. There may be additional objects in the tree that
	310	* intersect, so check the object returned carefully to make sure that no
	311	* additional lookups are needed.
a52d9a80 CM	312	*/
a52d9a80 CM	313	struct extent_map lookup_extent_mapping(struct extent_map_tree tree,
d1310b2e	314	u64 start, u64 len)
a52d9a80 CM	315	{
	316	struct extent_map *em;
	317	struct rb_node *rb_node;
306929f3 CH	318	struct rb_node *prev = NULL;
	319	struct rb_node *next = NULL;
	320	u64 end = range_end(start, len);
	321
5f56406a CM	322	rb_node = __tree_search(&tree->map, start, &prev, &next);
	323	if (!rb_node && prev) {
	324	em = rb_entry(prev, struct extent_map, rb_node);
d1310b2e	325	if (end > em->start && start < extent_map_end(em))
5f56406a CM	326	goto found;
	327	}
	328	if (!rb_node && next) {
	329	em = rb_entry(next, struct extent_map, rb_node);
d1310b2e	330	if (end > em->start && start < extent_map_end(em))
5f56406a CM	331	goto found;
5f56406a CM	332	}
a52d9a80 CM	333	if (!rb_node) {
	334	em = NULL;
	335	goto out;
	336	}
	337	if (IS_ERR(rb_node)) {
	338	em = ERR_PTR(PTR_ERR(rb_node));
	339	goto out;
	340	}
	341	em = rb_entry(rb_node, struct extent_map, rb_node);
d1310b2e CM	342	if (end > em->start && start < extent_map_end(em))
	343	goto found;
	344
	345	em = NULL;
	346	goto out;
	347
5f56406a	348	found:
a52d9a80 CM	349	atomic_inc(&em->refs);
a52d9a80 CM	350	out:
a52d9a80 CM	351	return em;
a52d9a80 CM	352	}
a52d9a80	353
b917b7c3 CM	354	/**
	355	* search_extent_mapping - find a nearby extent map
	356	* @tree: tree to lookup in
	357	* @start: byte offset to start the search
	358	* @len: length of the lookup range
	359	*
	360	* Find and return the first extent_map struct in @tree that intersects the
	361	* [start, len] range.
	362	*
	363	* If one can't be found, any nearby extent may be returned
	364	*/
	365	struct extent_map search_extent_mapping(struct extent_map_tree tree,
	366	u64 start, u64 len)
	367	{
	368	struct extent_map *em;
	369	struct rb_node *rb_node;
	370	struct rb_node *prev = NULL;
	371	struct rb_node *next = NULL;
	372
	373	rb_node = __tree_search(&tree->map, start, &prev, &next);
	374	if (!rb_node && prev) {
	375	em = rb_entry(prev, struct extent_map, rb_node);
	376	goto found;
	377	}
	378	if (!rb_node && next) {
	379	em = rb_entry(next, struct extent_map, rb_node);
	380	goto found;
	381	}
	382	if (!rb_node) {
	383	em = NULL;
	384	goto out;
	385	}
	386	if (IS_ERR(rb_node)) {
	387	em = ERR_PTR(PTR_ERR(rb_node));
	388	goto out;
	389	}
	390	em = rb_entry(rb_node, struct extent_map, rb_node);
	391	goto found;
	392
	393	em = NULL;
	394	goto out;
	395
	396	found:
	397	atomic_inc(&em->refs);
	398	out:
	399	return em;
	400	}
	401
9d2423c5 CH	402	/**
	403	* remove_extent_mapping - removes an extent_map from the extent tree
	404	* @tree: extent tree to remove from
	405	* @em: extent map beeing removed
	406	*
	407	* Removes @em from @tree. No reference counts are dropped, and no checks
	408	* are done to see if the range is in use
a52d9a80 CM	409	*/
	410	int remove_extent_mapping(struct extent_map_tree tree, struct extent_map em)
	411	{
d1310b2e	412	int ret = 0;
a52d9a80	413
7f3c74fb	414	WARN_ON(test_bit(EXTENT_FLAG_PINNED, &em->flags));
d1310b2e CM	415	rb_erase(&em->rb_node, &tree->map);
d1310b2e CM	416	em->in_tree = 0;
a52d9a80 CM	417	return ret;
a52d9a80 CM	418	}