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