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

#include <linux/err.h>
#include <linux/gfp.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_node = NULL;
	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;
}

/*
 * look for an offset in the tree, and if it can't be found, return
 * the first offset we can find smaller than 'offset'.
 */
static inline struct rb_node *tree_search(struct rb_root *root, u64 offset)
{
	struct rb_node *prev;
	struct rb_node *ret;
	ret = __tree_search(root, offset, &prev, NULL);
	if (!ret)
		return prev;
	return ret;
}

/* 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->start != start || !em);

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