Line data Source code
1 : #include <linux/err.h>
2 : #include <linux/slab.h>
3 : #include <linux/spinlock.h>
4 : #include <linux/hardirq.h>
5 : #include "ctree.h"
6 : #include "extent_map.h"
7 :
8 :
9 : static struct kmem_cache *extent_map_cache;
10 :
11 0 : int __init extent_map_init(void)
12 : {
13 0 : extent_map_cache = kmem_cache_create("btrfs_extent_map",
14 : sizeof(struct extent_map), 0,
15 : SLAB_RECLAIM_ACCOUNT | SLAB_MEM_SPREAD, NULL);
16 0 : if (!extent_map_cache)
17 : return -ENOMEM;
18 0 : return 0;
19 : }
20 :
21 0 : void extent_map_exit(void)
22 : {
23 0 : if (extent_map_cache)
24 0 : kmem_cache_destroy(extent_map_cache);
25 0 : }
26 :
27 : /**
28 : * extent_map_tree_init - initialize extent map tree
29 : * @tree: tree to initialize
30 : *
31 : * Initialize the extent tree @tree. Should be called for each new inode
32 : * or other user of the extent_map interface.
33 : */
34 26150 : void extent_map_tree_init(struct extent_map_tree *tree)
35 : {
36 26150 : tree->map = RB_ROOT;
37 26150 : INIT_LIST_HEAD(&tree->modified_extents);
38 26150 : rwlock_init(&tree->lock);
39 26150 : }
40 :
41 : /**
42 : * alloc_extent_map - allocate new extent map structure
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 : */
48 372729 : struct extent_map *alloc_extent_map(void)
49 : {
50 : struct extent_map *em;
51 372729 : em = kmem_cache_zalloc(extent_map_cache, GFP_NOFS);
52 372731 : if (!em)
53 : return NULL;
54 372733 : RB_CLEAR_NODE(&em->rb_node);
55 372733 : em->flags = 0;
56 372733 : em->compress_type = BTRFS_COMPRESS_NONE;
57 372733 : em->generation = 0;
58 : atomic_set(&em->refs, 1);
59 372733 : INIT_LIST_HEAD(&em->list);
60 372733 : return em;
61 : }
62 :
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 : */
70 4505039 : void free_extent_map(struct extent_map *em)
71 : {
72 4505039 : if (!em)
73 4509428 : return;
74 4499280 : WARN_ON(atomic_read(&em->refs) == 0);
75 9002953 : if (atomic_dec_and_test(&em->refs)) {
76 372537 : WARN_ON(extent_map_in_tree(em));
77 745066 : WARN_ON(!list_empty(&em->list));
78 372533 : if (test_bit(EXTENT_FLAG_FS_MAPPING, &em->flags))
79 1228 : kfree(em->bdev);
80 372533 : kmem_cache_free(extent_map_cache, em);
81 : }
82 : }
83 :
84 : /* simple helper to do math around the end of an extent, handling wrap */
85 : static u64 range_end(u64 start, u64 len)
86 : {
87 3814487 : if (start + len < start)
88 : return (u64)-1;
89 : return start + len;
90 : }
91 :
92 113026 : static int tree_insert(struct rb_root *root, struct extent_map *em)
93 : {
94 113026 : struct rb_node **p = &root->rb_node;
95 : struct rb_node *parent = NULL;
96 980128 : struct extent_map *entry = NULL;
97 : struct rb_node *orig_parent = NULL;
98 113026 : u64 end = range_end(em->start, em->len);
99 :
100 1492313 : while (*p) {
101 : parent = *p;
102 : entry = rb_entry(parent, struct extent_map, rb_node);
103 :
104 1271746 : if (em->start < entry->start)
105 481905 : p = &(*p)->rb_left;
106 789841 : else if (em->start >= extent_map_end(entry))
107 784356 : p = &(*p)->rb_right;
108 : else
109 : return -EEXIST;
110 : }
111 :
112 : orig_parent = parent;
113 279230 : while (parent && em->start >= extent_map_end(entry)) {
114 66251 : parent = rb_next(parent);
115 : entry = rb_entry(parent, struct extent_map, rb_node);
116 : }
117 107542 : if (parent)
118 39311 : if (end > entry->start && em->start < extent_map_end(entry))
119 : return -EEXIST;
120 :
121 : parent = orig_parent;
122 : entry = rb_entry(parent, struct extent_map, rb_node);
123 126495 : while (parent && em->start < entry->start) {
124 19081 : parent = rb_prev(parent);
125 : entry = rb_entry(parent, struct extent_map, rb_node);
126 : }
127 107414 : if (parent)
128 169451 : if (end > entry->start && em->start < extent_map_end(entry))
129 : return -EEXIST;
130 :
131 107411 : rb_link_node(&em->rb_node, orig_parent, p);
132 107411 : rb_insert_color(&em->rb_node, root);
133 107409 : return 0;
134 : }
135 :
136 : /*
137 : * search through the tree for an extent_map with a given offset. If
138 : * it can't be found, try to find some neighboring extents
139 : */
140 3692179 : static struct rb_node *__tree_search(struct rb_root *root, u64 offset,
141 : struct rb_node **prev_ret,
142 : struct rb_node **next_ret)
143 : {
144 3692179 : struct rb_node *n = root->rb_node;
145 : struct rb_node *prev = NULL;
146 : struct rb_node *orig_prev = NULL;
147 10401324 : struct extent_map *entry;
148 122114 : struct extent_map *prev_entry = NULL;
149 :
150 17961885 : while (n) {
151 : entry = rb_entry(n, struct extent_map, rb_node);
152 : prev = n;
153 : prev_entry = entry;
154 :
155 14095633 : if (offset < entry->start)
156 3694309 : n = n->rb_left;
157 10401324 : else if (offset >= extent_map_end(entry))
158 6883218 : n = n->rb_right;
159 : else
160 : return n;
161 : }
162 :
163 174073 : if (prev_ret) {
164 : orig_prev = prev;
165 372100 : while (prev && offset >= extent_map_end(prev_entry)) {
166 75914 : prev = rb_next(prev);
167 : prev_entry = rb_entry(prev, struct extent_map, rb_node);
168 : }
169 174072 : *prev_ret = prev;
170 : prev = orig_prev;
171 : }
172 :
173 174072 : if (next_ret) {
174 : prev_entry = rb_entry(prev, struct extent_map, rb_node);
175 196148 : while (prev && offset < prev_entry->start) {
176 22078 : prev = rb_prev(prev);
177 : prev_entry = rb_entry(prev, struct extent_map, rb_node);
178 : }
179 174070 : *next_ret = prev;
180 : }
181 : return NULL;
182 : }
183 :
184 : /* check to see if two extent_map structs are adjacent and safe to merge */
185 181610 : static int mergable_maps(struct extent_map *prev, struct extent_map *next)
186 : {
187 122791 : if (test_bit(EXTENT_FLAG_PINNED, &prev->flags))
188 : return 0;
189 :
190 : /*
191 : * don't merge compressed extents, we need to know their
192 : * actual size
193 : */
194 116899 : if (test_bit(EXTENT_FLAG_COMPRESSED, &prev->flags))
195 : return 0;
196 :
197 233312 : if (test_bit(EXTENT_FLAG_LOGGING, &prev->flags) ||
198 : test_bit(EXTENT_FLAG_LOGGING, &next->flags))
199 : return 0;
200 :
201 : /*
202 : * We don't want to merge stuff that hasn't been written to the log yet
203 : * since it may not reflect exactly what is on disk, and that would be
204 : * bad.
205 : */
206 273710 : if (!list_empty(&prev->list) || !list_empty(&next->list))
207 : return 0;
208 :
209 65650 : if (extent_map_end(prev) == next->start &&
210 58794 : prev->flags == next->flags &&
211 52897 : prev->bdev == next->bdev &&
212 26880 : ((next->block_start == EXTENT_MAP_HOLE &&
213 26744 : prev->block_start == EXTENT_MAP_HOLE) ||
214 0 : (next->block_start == EXTENT_MAP_INLINE &&
215 25810 : prev->block_start == EXTENT_MAP_INLINE) ||
216 0 : (next->block_start == EXTENT_MAP_DELALLOC &&
217 25810 : prev->block_start == EXTENT_MAP_DELALLOC) ||
218 25012 : (next->block_start < EXTENT_MAP_LAST_BYTE - 1 &&
219 : next->block_start == extent_map_block_end(prev)))) {
220 : return 1;
221 : }
222 33167 : return 0;
223 : }
224 :
225 98626 : static void try_merge_map(struct extent_map_tree *tree, struct extent_map *em)
226 : {
227 : struct extent_map *merge = NULL;
228 : struct rb_node *rb;
229 :
230 98626 : if (em->start != 0) {
231 80909 : rb = rb_prev(&em->rb_node);
232 80912 : if (rb)
233 : merge = rb_entry(rb, struct extent_map, rb_node);
234 80912 : if (rb && mergable_maps(merge, em)) {
235 513 : em->start = merge->start;
236 513 : em->orig_start = merge->orig_start;
237 513 : em->len += merge->len;
238 513 : em->block_len += merge->block_len;
239 513 : em->block_start = merge->block_start;
240 513 : em->mod_len = (em->mod_len + em->mod_start) - merge->mod_start;
241 513 : em->mod_start = merge->mod_start;
242 513 : em->generation = max(em->generation, merge->generation);
243 :
244 513 : rb_erase(&merge->rb_node, &tree->map);
245 513 : RB_CLEAR_NODE(&merge->rb_node);
246 513 : free_extent_map(merge);
247 : }
248 : }
249 :
250 98626 : rb = rb_next(&em->rb_node);
251 98627 : if (rb)
252 : merge = rb_entry(rb, struct extent_map, rb_node);
253 98627 : if (rb && mergable_maps(em, merge)) {
254 127 : em->len += merge->len;
255 127 : em->block_len += merge->block_len;
256 127 : rb_erase(&merge->rb_node, &tree->map);
257 127 : RB_CLEAR_NODE(&merge->rb_node);
258 127 : em->mod_len = (merge->mod_start + merge->mod_len) - em->mod_start;
259 127 : em->generation = max(em->generation, merge->generation);
260 127 : free_extent_map(merge);
261 : }
262 98627 : }
263 :
264 : /**
265 : * unpin_extent_cache - unpin an extent from the cache
266 : * @tree: tree to unpin the extent in
267 : * @start: logical offset in the file
268 : * @len: length of the extent
269 : * @gen: generation that this extent has been modified in
270 : *
271 : * Called after an extent has been written to disk properly. Set the generation
272 : * to the generation that actually added the file item to the inode so we know
273 : * we need to sync this extent when we call fsync().
274 : */
275 51422 : int unpin_extent_cache(struct extent_map_tree *tree, u64 start, u64 len,
276 : u64 gen)
277 : {
278 : int ret = 0;
279 : struct extent_map *em;
280 : bool prealloc = false;
281 :
282 51422 : write_lock(&tree->lock);
283 : em = lookup_extent_mapping(tree, start, len);
284 :
285 51423 : WARN_ON(!em || em->start != start);
286 :
287 51423 : if (!em)
288 : goto out;
289 :
290 51423 : if (!test_bit(EXTENT_FLAG_LOGGING, &em->flags))
291 51412 : list_move(&em->list, &tree->modified_extents);
292 51423 : em->generation = gen;
293 : clear_bit(EXTENT_FLAG_PINNED, &em->flags);
294 51423 : em->mod_start = em->start;
295 51423 : em->mod_len = em->len;
296 :
297 51423 : if (test_bit(EXTENT_FLAG_FILLING, &em->flags)) {
298 : prealloc = true;
299 : clear_bit(EXTENT_FLAG_FILLING, &em->flags);
300 : }
301 :
302 51423 : try_merge_map(tree, em);
303 :
304 51421 : if (prealloc) {
305 5625 : em->mod_start = em->start;
306 5625 : em->mod_len = em->len;
307 : }
308 :
309 51421 : free_extent_map(em);
310 : out:
311 : write_unlock(&tree->lock);
312 51421 : return ret;
313 :
314 : }
315 :
316 2403 : void clear_em_logging(struct extent_map_tree *tree, struct extent_map *em)
317 : {
318 : clear_bit(EXTENT_FLAG_LOGGING, &em->flags);
319 2403 : if (extent_map_in_tree(em))
320 2403 : try_merge_map(tree, em);
321 2403 : }
322 :
323 140109 : static inline void setup_extent_mapping(struct extent_map_tree *tree,
324 : struct extent_map *em,
325 : int modified)
326 : {
327 140109 : atomic_inc(&em->refs);
328 140134 : em->mod_start = em->start;
329 140134 : em->mod_len = em->len;
330 :
331 140134 : if (modified)
332 95324 : list_move(&em->list, &tree->modified_extents);
333 : else
334 44810 : try_merge_map(tree, em);
335 140125 : }
336 :
337 : /**
338 : * add_extent_mapping - add new extent map to the extent tree
339 : * @tree: tree to insert new map in
340 : * @em: map to insert
341 : *
342 : * Insert @em into @tree or perform a simple forward/backward merge with
343 : * existing mappings. The extent_map struct passed in will be inserted
344 : * into the tree directly, with an additional reference taken, or a
345 : * reference dropped if the merge attempt was successful.
346 : */
347 113186 : int add_extent_mapping(struct extent_map_tree *tree,
348 : struct extent_map *em, int modified)
349 : {
350 : int ret = 0;
351 :
352 113186 : ret = tree_insert(&tree->map, em);
353 113166 : if (ret)
354 : goto out;
355 :
356 107407 : setup_extent_mapping(tree, em, modified);
357 : out:
358 113177 : return ret;
359 : }
360 :
361 : static struct extent_map *
362 3701461 : __lookup_extent_mapping(struct extent_map_tree *tree,
363 : u64 start, u64 len, int strict)
364 : {
365 3517941 : struct extent_map *em;
366 : struct rb_node *rb_node;
367 3701461 : struct rb_node *prev = NULL;
368 3701461 : struct rb_node *next = NULL;
369 : u64 end = range_end(start, len);
370 :
371 3701461 : rb_node = __tree_search(&tree->map, start, &prev, &next);
372 3700911 : if (!rb_node) {
373 174070 : if (prev)
374 : rb_node = prev;
375 127875 : else if (next)
376 : rb_node = next;
377 : else
378 : return NULL;
379 : }
380 :
381 : em = rb_entry(rb_node, struct extent_map, rb_node);
382 :
383 7143055 : if (strict && !(end > em->start && start < extent_map_end(em)))
384 : return NULL;
385 :
386 3535056 : atomic_inc(&em->refs);
387 3536722 : return em;
388 : }
389 :
390 : /**
391 : * lookup_extent_mapping - lookup extent_map
392 : * @tree: tree to lookup in
393 : * @start: byte offset to start the search
394 : * @len: length of the lookup range
395 : *
396 : * Find and return the first extent_map struct in @tree that intersects the
397 : * [start, len] range. There may be additional objects in the tree that
398 : * intersect, so check the object returned carefully to make sure that no
399 : * additional lookups are needed.
400 : */
401 3574591 : struct extent_map *lookup_extent_mapping(struct extent_map_tree *tree,
402 : u64 start, u64 len)
403 : {
404 3626013 : return __lookup_extent_mapping(tree, start, len, 1);
405 : }
406 :
407 : /**
408 : * search_extent_mapping - find a nearby extent map
409 : * @tree: tree to lookup in
410 : * @start: byte offset to start the search
411 : * @len: length of the lookup range
412 : *
413 : * Find and return the first extent_map struct in @tree that intersects the
414 : * [start, len] range.
415 : *
416 : * If one can't be found, any nearby extent may be returned
417 : */
418 75910 : struct extent_map *search_extent_mapping(struct extent_map_tree *tree,
419 : u64 start, u64 len)
420 : {
421 75910 : return __lookup_extent_mapping(tree, start, len, 0);
422 : }
423 :
424 : /**
425 : * remove_extent_mapping - removes an extent_map from the extent tree
426 : * @tree: extent tree to remove from
427 : * @em: extent map beeing removed
428 : *
429 : * Removes @em from @tree. No reference counts are dropped, and no checks
430 : * are done to see if the range is in use
431 : */
432 106547 : int remove_extent_mapping(struct extent_map_tree *tree, struct extent_map *em)
433 : {
434 : int ret = 0;
435 :
436 106547 : WARN_ON(test_bit(EXTENT_FLAG_PINNED, &em->flags));
437 106547 : rb_erase(&em->rb_node, &tree->map);
438 106547 : if (!test_bit(EXTENT_FLAG_LOGGING, &em->flags))
439 106546 : list_del_init(&em->list);
440 106547 : RB_CLEAR_NODE(&em->rb_node);
441 106547 : return ret;
442 : }
443 :
444 32703 : void replace_extent_mapping(struct extent_map_tree *tree,
445 : struct extent_map *cur,
446 : struct extent_map *new,
447 : int modified)
448 : {
449 32703 : WARN_ON(test_bit(EXTENT_FLAG_PINNED, &cur->flags));
450 : ASSERT(extent_map_in_tree(cur));
451 32703 : if (!test_bit(EXTENT_FLAG_LOGGING, &cur->flags))
452 32703 : list_del_init(&cur->list);
453 32703 : rb_replace_node(&cur->rb_node, &new->rb_node, &tree->map);
454 32703 : RB_CLEAR_NODE(&cur->rb_node);
455 :
456 32703 : setup_extent_mapping(tree, new, modified);
457 32703 : }
|
