1#include <linux/err.h>
2#include <linux/slab.h>
3#include <linux/module.h>
4#include <linux/spinlock.h>
5#include <linux/hardirq.h>
6#include "extent_map.h"
7
8
9static struct kmem_cache *extent_map_cache;
10
11int __init extent_map_init(void)
12{
13	extent_map_cache = kmem_cache_create("extent_map",
14			sizeof(struct extent_map), 0,
15			SLAB_RECLAIM_ACCOUNT | SLAB_MEM_SPREAD, NULL);
16	if (!extent_map_cache)
17		return -ENOMEM;
18	return 0;
19}
20
21void extent_map_exit(void)
22{
23	if (extent_map_cache)
24		kmem_cache_destroy(extent_map_cache);
25}
26
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 */
35void extent_map_tree_init(struct extent_map_tree *tree, gfp_t mask)
36{
37	tree->map = RB_ROOT;
38	rwlock_init(&tree->lock);
39}
40
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 */
49struct 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;
56	em->flags = 0;
57	atomic_set(&em->refs, 1);
58	return em;
59}
60
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 */
68void free_extent_map(struct extent_map *em)
69{
70	if (!em)
71		return;
72	WARN_ON(atomic_read(&em->refs) == 0);
73	if (atomic_dec_and_test(&em->refs)) {
74		WARN_ON(em->in_tree);
75		kmem_cache_free(extent_map_cache, em);
76	}
77}
78
79static struct rb_node *tree_insert(struct rb_root *root, u64 offset,
80				   struct rb_node *node)
81{
82	struct rb_node **p = &root->rb_node;
83	struct rb_node *parent = NULL;
84	struct extent_map *entry;
85
86	while (*p) {
87		parent = *p;
88		entry = rb_entry(parent, struct extent_map, rb_node);
89
90		WARN_ON(!entry->in_tree);
91
92		if (offset < entry->start)
93			p = &(*p)->rb_left;
94		else if (offset >= extent_map_end(entry))
95			p = &(*p)->rb_right;
96		else
97			return parent;
98	}
99
100	entry = rb_entry(node, struct extent_map, rb_node);
101	entry->in_tree = 1;
102	rb_link_node(node, parent, p);
103	rb_insert_color(node, root);
104	return NULL;
105}
106
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 */
111static struct rb_node *__tree_search(struct rb_root *root, u64 offset,
112				     struct rb_node **prev_ret,
113				     struct rb_node **next_ret)
114{
115	struct rb_node *n = root->rb_node;
116	struct rb_node *prev = NULL;
117	struct rb_node *orig_prev = NULL;
118	struct extent_map *entry;
119	struct extent_map *prev_entry = NULL;
120
121	while (n) {
122		entry = rb_entry(n, struct extent_map, rb_node);
123		prev = n;
124		prev_entry = entry;
125
126		WARN_ON(!entry->in_tree);
127
128		if (offset < entry->start)
129			n = n->rb_left;
130		else if (offset >= extent_map_end(entry))
131			n = n->rb_right;
132		else
133			return n;
134	}
135
136	if (prev_ret) {
137		orig_prev = prev;
138		while (prev && offset >= extent_map_end(prev_entry)) {
139			prev = rb_next(prev);
140			prev_entry = rb_entry(prev, struct extent_map, rb_node);
141		}
142		*prev_ret = prev;
143		prev = orig_prev;
144	}
145
146	if (next_ret) {
147		prev_entry = rb_entry(prev, struct extent_map, rb_node);
148		while (prev && offset < prev_entry->start) {
149			prev = rb_prev(prev);
150			prev_entry = rb_entry(prev, struct extent_map, rb_node);
151		}
152		*next_ret = prev;
153	}
154	return NULL;
155}
156
157/* check to see if two extent_map structs are adjacent and safe to merge */
158static int mergable_maps(struct extent_map *prev, struct extent_map *next)
159{
160	if (test_bit(EXTENT_FLAG_PINNED, &prev->flags))
161		return 0;
162
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
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	}
183	return 0;
184}
185
186int 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
196	WARN_ON(!em || em->start != start);
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);
230out:
231	write_unlock(&tree->lock);
232	return ret;
233
234}
235
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
244 * reference dropped if the merge attempt was successfull.
245 */
246int add_extent_mapping(struct extent_map_tree *tree,
247		       struct extent_map *em)
248{
249	int ret = 0;
250	struct extent_map *merge = NULL;
251	struct rb_node *rb;
252	struct extent_map *exist;
253
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	}
260	rb = tree_insert(&tree->map, em->start, &em->rb_node);
261	if (rb) {
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)
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;
273			em->block_len += merge->block_len;
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);
278		}
279	 }
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;
285		em->block_len += merge->len;
286		rb_erase(&merge->rb_node, &tree->map);
287		merge->in_tree = 0;
288		free_extent_map(merge);
289	}
290out:
291	return ret;
292}
293
294/* simple helper to do math around the end of an extent, handling wrap */
295static u64 range_end(u64 start, u64 len)
296{
297	if (start + len < start)
298		return (u64)-1;
299	return start + len;
300}
301
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.
312 */
313struct extent_map *lookup_extent_mapping(struct extent_map_tree *tree,
314					 u64 start, u64 len)
315{
316	struct extent_map *em;
317	struct rb_node *rb_node;
318	struct rb_node *prev = NULL;
319	struct rb_node *next = NULL;
320	u64 end = range_end(start, len);
321
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);
325		if (end > em->start && start < extent_map_end(em))
326			goto found;
327	}
328	if (!rb_node && next) {
329		em = rb_entry(next, struct extent_map, rb_node);
330		if (end > em->start && start < extent_map_end(em))
331			goto found;
332	}
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);
342	if (end > em->start && start < extent_map_end(em))
343		goto found;
344
345	em = NULL;
346	goto out;
347
348found:
349	atomic_inc(&em->refs);
350out:
351	return em;
352}
353
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 */
365struct 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
396found:
397	atomic_inc(&em->refs);
398out:
399	return em;
400}
401
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
409 */
410int remove_extent_mapping(struct extent_map_tree *tree, struct extent_map *em)
411{
412	int ret = 0;
413
414	WARN_ON(test_bit(EXTENT_FLAG_PINNED, &em->flags));
415	rb_erase(&em->rb_node, &tree->map);
416	em->in_tree = 0;
417	return ret;
418}
419