[GitHub/mt8127/android_kernel_alcatel_ttab.git] / fs / btrfs / extent_map.c

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


static struct kmem_cache *extent_map_cache;

int __init extent_map_init(void)
{
	extent_map_cache = kmem_cache_create("btrfs_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
 *
 * 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)
{
	tree->map = RB_ROOT;
	INIT_LIST_HEAD(&tree->modified_extents);
	rwlock_init(&tree->lock);
}

/**
 * alloc_extent_map - allocate new extent map structure
 *
 * 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(void)
{
	struct extent_map *em;
	em = kmem_cache_zalloc(extent_map_cache, GFP_NOFS);
	if (!em)
		return NULL;
	em->in_tree = 0;
	em->flags = 0;
	em->compress_type = BTRFS_COMPRESS_NONE;
	em->generation = 0;
	atomic_set(&em->refs, 1);
	INIT_LIST_HEAD(&em->list);
	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);
		WARN_ON(!list_empty(&em->list));
		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 (test_bit(EXTENT_FLAG_LOGGING, &prev->flags) ||
	    test_bit(EXTENT_FLAG_LOGGING, &next->flags))
		return 0;

	/*
	 * We don't want to merge stuff that hasn't been written to the log yet
	 * since it may not reflect exactly what is on disk, and that would be
	 * bad.
	 */
	if (!list_empty(&prev->list) || !list_empty(&next->list))
		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;
}

static void try_merge_map(struct extent_map_tree *tree, struct extent_map *em)
{
	struct extent_map *merge = NULL;
	struct rb_node *rb;

	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->orig_start = merge->orig_start;
			em->len += merge->len;
			em->block_len += merge->block_len;
			em->block_start = merge->block_start;
			merge->in_tree = 0;
			em->mod_len = (em->mod_len + em->mod_start) - merge->mod_start;
			em->mod_start = merge->mod_start;
			em->generation = max(em->generation, merge->generation);

			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;
		em->mod_len = (merge->mod_start + merge->mod_len) - em->mod_start;
		em->generation = max(em->generation, merge->generation);
		free_extent_map(merge);
	}
}

/**
 * unpin_extent_cache - unpin an extent from the cache
 * @tree:	tree to unpin the extent in
 * @start:	logical offset in the file
 * @len:	length of the extent
 * @gen:	generation that this extent has been modified in
 *
 * Called after an extent has been written to disk properly.  Set the generation
 * to the generation that actually added the file item to the inode so we know
 * we need to sync this extent when we call fsync().
 */
int unpin_extent_cache(struct extent_map_tree *tree, u64 start, u64 len,
		       u64 gen)
{
	int ret = 0;
	struct extent_map *em;
	bool prealloc = false;

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

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

	if (!em)
		goto out;

	em->generation = gen;
	clear_bit(EXTENT_FLAG_PINNED, &em->flags);
	em->mod_start = em->start;
	em->mod_len = em->len;

	if (test_bit(EXTENT_FLAG_FILLING, &em->flags)) {
		prealloc = true;
		clear_bit(EXTENT_FLAG_FILLING, &em->flags);
	}

	try_merge_map(tree, em);

	if (prealloc) {
		em->mod_start = em->start;
		em->mod_len = em->len;
	}

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

}

void clear_em_logging(struct extent_map_tree *tree, struct extent_map *em)
{
	clear_bit(EXTENT_FLAG_LOGGING, &em->flags);
	if (em->in_tree)
		try_merge_map(tree, em);
}

/**
 * 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 successful.
 */
int add_extent_mapping(struct extent_map_tree *tree,
		       struct extent_map *em, int modified)
{
	int ret = 0;
	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);

	em->mod_start = em->start;
	em->mod_len = em->len;

	if (modified)
		list_move(&em->list, &tree->modified_extents);
	else
		try_merge_map(tree, em);
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;
}

static struct extent_map *
__lookup_extent_mapping(struct extent_map_tree *tree,
			u64 start, u64 len, int strict)
{
	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) {
		if (prev)
			rb_node = prev;
		else if (next)
			rb_node = next;
		else
			return NULL;
	}

	em = rb_entry(rb_node, struct extent_map, rb_node);

	if (strict && !(end > em->start && start < extent_map_end(em)))
		return NULL;

	atomic_inc(&em->refs);
	return em;
}

/**
 * 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)
{
	return __lookup_extent_mapping(tree, start, len, 1);
}

/**
 * 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)
{
	return __lookup_extent_mapping(tree, start, len, 0);
}

/**
 * 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);
	if (!test_bit(EXTENT_FLAG_LOGGING, &em->flags))
		list_del_init(&em->list);
	em->in_tree = 0;
	return ret;
}
Commit	Line	Data
d1310b2e	1	#include <linux/err.h>
d1310b2e	2	#include <linux/slab.h>
a52d9a80	3	#include <linux/spinlock.h>
d1310b2e	4	#include <linux/hardirq.h>
261507a0	5	#include "ctree.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	{
837e1972	13	extent_map_cache = kmem_cache_create("btrfs_extent_map",
9601e3f6 CH	14	sizeof(struct extent_map), 0,
9601e3f6 CH	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
9d2423c5 CH	30	*
	31	* Initialize the extent tree @tree. Should be called for each new inode
	32	* or other user of the extent_map interface.
	33	*/
a8067e02	34	void extent_map_tree_init(struct extent_map_tree *tree)
a52d9a80	35	{
6bef4d31	36	tree->map = RB_ROOT;
5dc562c5	37	INIT_LIST_HEAD(&tree->modified_extents);
890871be	38	rwlock_init(&tree->lock);
a52d9a80	39	}
a52d9a80	40
9d2423c5 CH	41	/**
9d2423c5 CH	42	* alloc_extent_map - allocate new extent map structure
9d2423c5 CH	43	*
	44	* Allocate a new extent_map structure. The new structure is
	45	* returned with a reference count of one and needs to be
	46	* freed using free_extent_map()
	47	*/
172ddd60	48	struct extent_map *alloc_extent_map(void)
a52d9a80 CM	49	{
a52d9a80 CM	50	struct extent_map *em;
70c8a91c	51	em = kmem_cache_zalloc(extent_map_cache, GFP_NOFS);
c26a9203 TI	52	if (!em)
c26a9203 TI	53	return NULL;
a52d9a80	54	em->in_tree = 0;
d1310b2e	55	em->flags = 0;
261507a0	56	em->compress_type = BTRFS_COMPRESS_NONE;
5dc562c5	57	em->generation = 0;
a52d9a80	58	atomic_set(&em->refs, 1);
5dc562c5	59	INIT_LIST_HEAD(&em->list);
a52d9a80 CM	60	return em;
a52d9a80 CM	61	}
a52d9a80	62
9d2423c5 CH	63	/**
	64	* free_extent_map - drop reference count of an extent_map
	65	* @em: extent map beeing releasead
	66	*
	67	* Drops the reference out on @em by one and free the structure
	68	* if the reference count hits zero.
	69	*/
a52d9a80 CM	70	void free_extent_map(struct extent_map *em)
a52d9a80 CM	71	{
2bf5a725 CM	72	if (!em)
2bf5a725 CM	73	return;
d1310b2e	74	WARN_ON(atomic_read(&em->refs) == 0);
a52d9a80 CM	75	if (atomic_dec_and_test(&em->refs)) {
a52d9a80 CM	76	WARN_ON(em->in_tree);
5dc562c5	77	WARN_ON(!list_empty(&em->list));
a52d9a80 CM	78	kmem_cache_free(extent_map_cache, em);
	79	}
	80	}
a52d9a80	81
a52d9a80 CM	82	static struct rb_node tree_insert(struct rb_root root, u64 offset,
	83	struct rb_node *node)
	84	{
d397712b CM	85	struct rb_node **p = &root->rb_node;
d397712b CM	86	struct rb_node *parent = NULL;
d1310b2e	87	struct extent_map *entry;
a52d9a80	88
d397712b	89	while (*p) {
a52d9a80	90	parent = *p;
d1310b2e CM	91	entry = rb_entry(parent, struct extent_map, rb_node);
	92
	93	WARN_ON(!entry->in_tree);
a52d9a80 CM	94
	95	if (offset < entry->start)
	96	p = &(*p)->rb_left;
d1310b2e	97	else if (offset >= extent_map_end(entry))
a52d9a80 CM	98	p = &(*p)->rb_right;
	99	else
	100	return parent;
	101	}
	102
d1310b2e	103	entry = rb_entry(node, struct extent_map, rb_node);
a52d9a80 CM	104	entry->in_tree = 1;
	105	rb_link_node(node, parent, p);
	106	rb_insert_color(node, root);
	107	return NULL;
	108	}
	109
d352ac68 CM	110	/*
	111	* search through the tree for an extent_map with a given offset. If
	112	* it can't be found, try to find some neighboring extents
	113	*/
a52d9a80	114	static struct rb_node __tree_search(struct rb_root root, u64 offset,
5f56406a CM	115	struct rb_node **prev_ret,
5f56406a CM	116	struct rb_node **next_ret)
a52d9a80	117	{
d397712b	118	struct rb_node *n = root->rb_node;
a52d9a80	119	struct rb_node *prev = NULL;
5f56406a	120	struct rb_node *orig_prev = NULL;
d1310b2e CM	121	struct extent_map *entry;
d1310b2e CM	122	struct extent_map *prev_entry = NULL;
a52d9a80	123
d397712b	124	while (n) {
d1310b2e	125	entry = rb_entry(n, struct extent_map, rb_node);
a52d9a80 CM	126	prev = n;
	127	prev_entry = entry;
	128
d1310b2e CM	129	WARN_ON(!entry->in_tree);
d1310b2e CM	130
a52d9a80 CM	131	if (offset < entry->start)
a52d9a80 CM	132	n = n->rb_left;
d1310b2e	133	else if (offset >= extent_map_end(entry))
a52d9a80 CM	134	n = n->rb_right;
	135	else
	136	return n;
	137	}
5f56406a CM	138
	139	if (prev_ret) {
	140	orig_prev = prev;
d397712b	141	while (prev && offset >= extent_map_end(prev_entry)) {
5f56406a	142	prev = rb_next(prev);
d1310b2e	143	prev_entry = rb_entry(prev, struct extent_map, rb_node);
5f56406a CM	144	}
	145	*prev_ret = prev;
	146	prev = orig_prev;
	147	}
	148
	149	if (next_ret) {
d1310b2e	150	prev_entry = rb_entry(prev, struct extent_map, rb_node);
d397712b	151	while (prev && offset < prev_entry->start) {
5f56406a	152	prev = rb_prev(prev);
d1310b2e	153	prev_entry = rb_entry(prev, struct extent_map, rb_node);
5f56406a CM	154	}
5f56406a CM	155	*next_ret = prev;
a52d9a80	156	}
a52d9a80 CM	157	return NULL;
	158	}
	159
d352ac68	160	/* check to see if two extent_map structs are adjacent and safe to merge */
d1310b2e	161	static int mergable_maps(struct extent_map prev, struct extent_map next)
a52d9a80	162	{
7f3c74fb CM	163	if (test_bit(EXTENT_FLAG_PINNED, &prev->flags))
	164	return 0;
	165
c8b97818 CM	166	/*
	167	* don't merge compressed extents, we need to know their
	168	* actual size
	169	*/
	170	if (test_bit(EXTENT_FLAG_COMPRESSED, &prev->flags))
	171	return 0;
	172
201a9038 JB	173	if (test_bit(EXTENT_FLAG_LOGGING, &prev->flags) \|\|
	174	test_bit(EXTENT_FLAG_LOGGING, &next->flags))
	175	return 0;
	176
09a2a8f9 JB	177	/*
	178	* We don't want to merge stuff that hasn't been written to the log yet
	179	* since it may not reflect exactly what is on disk, and that would be
	180	* bad.
	181	*/
	182	if (!list_empty(&prev->list) \|\| !list_empty(&next->list))
	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
4d2c8f62	201	static void try_merge_map(struct extent_map_tree tree, struct extent_map em)
a1ed835e	202	{
a1ed835e CM	203	struct extent_map *merge = NULL;
a1ed835e CM	204	struct rb_node *rb;
a1ed835e CM	205
	206	if (em->start != 0) {
	207	rb = rb_prev(&em->rb_node);
	208	if (rb)
	209	merge = rb_entry(rb, struct extent_map, rb_node);
	210	if (rb && mergable_maps(merge, em)) {
	211	em->start = merge->start;
70c8a91c	212	em->orig_start = merge->orig_start;
a1ed835e CM	213	em->len += merge->len;
	214	em->block_len += merge->block_len;
	215	em->block_start = merge->block_start;
	216	merge->in_tree = 0;
70c8a91c JB	217	em->mod_len = (em->mod_len + em->mod_start) - merge->mod_start;
	218	em->mod_start = merge->mod_start;
	219	em->generation = max(em->generation, merge->generation);
5dc562c5	220
a1ed835e CM	221	rb_erase(&merge->rb_node, &tree->map);
	222	free_extent_map(merge);
	223	}
	224	}
	225
	226	rb = rb_next(&em->rb_node);
	227	if (rb)
	228	merge = rb_entry(rb, struct extent_map, rb_node);
	229	if (rb && mergable_maps(em, merge)) {
	230	em->len += merge->len;
	231	em->block_len += merge->len;
	232	rb_erase(&merge->rb_node, &tree->map);
	233	merge->in_tree = 0;
70c8a91c JB	234	em->mod_len = (merge->mod_start + merge->mod_len) - em->mod_start;
70c8a91c JB	235	em->generation = max(em->generation, merge->generation);
a1ed835e CM	236	free_extent_map(merge);
a1ed835e CM	237	}
4d2c8f62 LZ	238	}
4d2c8f62 LZ	239
5dc562c5	240	/**
52b1de91	241	* unpin_extent_cache - unpin an extent from the cache
5dc562c5 JB	242	* @tree: tree to unpin the extent in
	243	* @start: logical offset in the file
	244	* @len: length of the extent
	245	* @gen: generation that this extent has been modified in
5dc562c5 JB	246	*
	247	* Called after an extent has been written to disk properly. Set the generation
	248	* to the generation that actually added the file item to the inode so we know
	249	* we need to sync this extent when we call fsync().
	250	*/
	251	int unpin_extent_cache(struct extent_map_tree *tree, u64 start, u64 len,
	252	u64 gen)
4d2c8f62 LZ	253	{
	254	int ret = 0;
	255	struct extent_map *em;
4e2f84e6	256	bool prealloc = false;
4d2c8f62 LZ	257
	258	write_lock(&tree->lock);
	259	em = lookup_extent_mapping(tree, start, len);
	260
	261	WARN_ON(!em \|\| em->start != start);
	262
	263	if (!em)
	264	goto out;
	265
5dc562c5	266	em->generation = gen;
4d2c8f62	267	clear_bit(EXTENT_FLAG_PINNED, &em->flags);
4e2f84e6 LB	268	em->mod_start = em->start;
	269	em->mod_len = em->len;
	270
b11e234d	271	if (test_bit(EXTENT_FLAG_FILLING, &em->flags)) {
4e2f84e6	272	prealloc = true;
b11e234d	273	clear_bit(EXTENT_FLAG_FILLING, &em->flags);
4e2f84e6	274	}
4d2c8f62 LZ	275
4d2c8f62 LZ	276	try_merge_map(tree, em);
4e2f84e6 LB	277
	278	if (prealloc) {
	279	em->mod_start = em->start;
	280	em->mod_len = em->len;
	281	}
	282
a1ed835e CM	283	free_extent_map(em);
	284	out:
	285	write_unlock(&tree->lock);
	286	return ret;
	287
	288	}
	289
201a9038 JB	290	void clear_em_logging(struct extent_map_tree tree, struct extent_map em)
	291	{
	292	clear_bit(EXTENT_FLAG_LOGGING, &em->flags);
222c81dc JB	293	if (em->in_tree)
222c81dc JB	294	try_merge_map(tree, em);
201a9038 JB	295	}
201a9038 JB	296
9d2423c5 CH	297	/**
	298	* add_extent_mapping - add new extent map to the extent tree
	299	* @tree: tree to insert new map in
	300	* @em: map to insert
	301	*
	302	* Insert @em into @tree or perform a simple forward/backward merge with
	303	* existing mappings. The extent_map struct passed in will be inserted
	304	* into the tree directly, with an additional reference taken, or a
25985edc	305	* reference dropped if the merge attempt was successful.
a52d9a80 CM	306	*/
a52d9a80 CM	307	int add_extent_mapping(struct extent_map_tree *tree,
09a2a8f9	308	struct extent_map *em, int modified)
a52d9a80 CM	309	{
a52d9a80 CM	310	int ret = 0;
a52d9a80	311	struct rb_node *rb;
7c2fe32a	312	struct extent_map *exist;
a52d9a80	313
7c2fe32a CM	314	exist = lookup_extent_mapping(tree, em->start, em->len);
	315	if (exist) {
	316	free_extent_map(exist);
	317	ret = -EEXIST;
	318	goto out;
	319	}
d1310b2e	320	rb = tree_insert(&tree->map, em->start, &em->rb_node);
a52d9a80	321	if (rb) {
a52d9a80 CM	322	ret = -EEXIST;
	323	goto out;
	324	}
	325	atomic_inc(&em->refs);
4d2c8f62	326
4e2f84e6 LB	327	em->mod_start = em->start;
	328	em->mod_len = em->len;
	329
09a2a8f9 JB	330	if (modified)
	331	list_move(&em->list, &tree->modified_extents);
	332	else
	333	try_merge_map(tree, em);
a52d9a80	334	out:
a52d9a80 CM	335	return ret;
a52d9a80 CM	336	}
a52d9a80	337
d352ac68	338	/* simple helper to do math around the end of an extent, handling wrap */
d1310b2e CM	339	static u64 range_end(u64 start, u64 len)
	340	{
	341	if (start + len < start)
	342	return (u64)-1;
	343	return start + len;
	344	}
	345
48a3b636 ES	346	static struct extent_map *
	347	__lookup_extent_mapping(struct extent_map_tree *tree,
	348	u64 start, u64 len, int strict)
a52d9a80 CM	349	{
	350	struct extent_map *em;
	351	struct rb_node *rb_node;
306929f3 CH	352	struct rb_node *prev = NULL;
	353	struct rb_node *next = NULL;
	354	u64 end = range_end(start, len);
	355
5f56406a	356	rb_node = __tree_search(&tree->map, start, &prev, &next);
a52d9a80	357	if (!rb_node) {
ed64f066 LZ	358	if (prev)
	359	rb_node = prev;
	360	else if (next)
	361	rb_node = next;
	362	else
	363	return NULL;
a52d9a80	364	}
ed64f066	365
a52d9a80	366	em = rb_entry(rb_node, struct extent_map, rb_node);
d1310b2e	367
ed64f066 LZ	368	if (strict && !(end > em->start && start < extent_map_end(em)))
ed64f066 LZ	369	return NULL;
d1310b2e	370
a52d9a80	371	atomic_inc(&em->refs);
a52d9a80 CM	372	return em;
a52d9a80 CM	373	}
a52d9a80	374
ed64f066 LZ	375	/**
	376	* lookup_extent_mapping - lookup extent_map
	377	* @tree: tree to lookup in
	378	* @start: byte offset to start the search
	379	* @len: length of the lookup range
	380	*
	381	* Find and return the first extent_map struct in @tree that intersects the
	382	* [start, len] range. There may be additional objects in the tree that
	383	* intersect, so check the object returned carefully to make sure that no
	384	* additional lookups are needed.
	385	*/
	386	struct extent_map lookup_extent_mapping(struct extent_map_tree tree,
	387	u64 start, u64 len)
	388	{
	389	return __lookup_extent_mapping(tree, start, len, 1);
	390	}
	391
b917b7c3 CM	392	/**
	393	* search_extent_mapping - find a nearby extent map
	394	* @tree: tree to lookup in
	395	* @start: byte offset to start the search
	396	* @len: length of the lookup range
	397	*
	398	* Find and return the first extent_map struct in @tree that intersects the
	399	* [start, len] range.
	400	*
	401	* If one can't be found, any nearby extent may be returned
	402	*/
	403	struct extent_map search_extent_mapping(struct extent_map_tree tree,
	404	u64 start, u64 len)
	405	{
ed64f066	406	return __lookup_extent_mapping(tree, start, len, 0);
b917b7c3 CM	407	}
b917b7c3 CM	408
9d2423c5 CH	409	/**
	410	* remove_extent_mapping - removes an extent_map from the extent tree
	411	* @tree: extent tree to remove from
	412	* @em: extent map beeing removed
	413	*
	414	* Removes @em from @tree. No reference counts are dropped, and no checks
	415	* are done to see if the range is in use
a52d9a80 CM	416	*/
	417	int remove_extent_mapping(struct extent_map_tree tree, struct extent_map em)
	418	{
d1310b2e	419	int ret = 0;
a52d9a80	420
7f3c74fb	421	WARN_ON(test_bit(EXTENT_FLAG_PINNED, &em->flags));
d1310b2e	422	rb_erase(&em->rb_node, &tree->map);
ff44c6e3 JB	423	if (!test_bit(EXTENT_FLAG_LOGGING, &em->flags))
ff44c6e3 JB	424	list_del_init(&em->list);
d1310b2e	425	em->in_tree = 0;
a52d9a80 CM	426	return ret;
a52d9a80 CM	427	}