]>
Commit | Line | Data |
---|---|---|
b2441318 | 1 | // SPDX-License-Identifier: GPL-2.0 |
c1d7c514 | 2 | |
d1310b2e | 3 | #include <linux/err.h> |
d1310b2e | 4 | #include <linux/slab.h> |
a52d9a80 | 5 | #include <linux/spinlock.h> |
261507a0 | 6 | #include "ctree.h" |
1c11b63e | 7 | #include "volumes.h" |
a52d9a80 | 8 | #include "extent_map.h" |
ebb8765b | 9 | #include "compression.h" |
a52d9a80 | 10 | |
86479a04 | 11 | |
a52d9a80 | 12 | static struct kmem_cache *extent_map_cache; |
ca664626 | 13 | |
2f4cbe64 | 14 | int __init extent_map_init(void) |
a52d9a80 | 15 | { |
837e1972 | 16 | extent_map_cache = kmem_cache_create("btrfs_extent_map", |
9601e3f6 | 17 | sizeof(struct extent_map), 0, |
fba4b697 | 18 | SLAB_MEM_SPREAD, NULL); |
2f4cbe64 WB |
19 | if (!extent_map_cache) |
20 | return -ENOMEM; | |
2f4cbe64 | 21 | return 0; |
a52d9a80 CM |
22 | } |
23 | ||
e67c718b | 24 | void __cold extent_map_exit(void) |
a52d9a80 | 25 | { |
5598e900 | 26 | kmem_cache_destroy(extent_map_cache); |
a52d9a80 CM |
27 | } |
28 | ||
9d2423c5 CH |
29 | /** |
30 | * extent_map_tree_init - initialize extent map tree | |
31 | * @tree: tree to initialize | |
9d2423c5 CH |
32 | * |
33 | * Initialize the extent tree @tree. Should be called for each new inode | |
34 | * or other user of the extent_map interface. | |
35 | */ | |
a8067e02 | 36 | void extent_map_tree_init(struct extent_map_tree *tree) |
a52d9a80 | 37 | { |
07e1ce09 | 38 | tree->map = RB_ROOT_CACHED; |
5dc562c5 | 39 | INIT_LIST_HEAD(&tree->modified_extents); |
890871be | 40 | rwlock_init(&tree->lock); |
a52d9a80 | 41 | } |
a52d9a80 | 42 | |
9d2423c5 CH |
43 | /** |
44 | * alloc_extent_map - allocate new extent map structure | |
9d2423c5 CH |
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 | */ | |
172ddd60 | 50 | struct extent_map *alloc_extent_map(void) |
a52d9a80 CM |
51 | { |
52 | struct extent_map *em; | |
70c8a91c | 53 | em = kmem_cache_zalloc(extent_map_cache, GFP_NOFS); |
c26a9203 TI |
54 | if (!em) |
55 | return NULL; | |
cbc0e928 | 56 | RB_CLEAR_NODE(&em->rb_node); |
d1310b2e | 57 | em->flags = 0; |
261507a0 | 58 | em->compress_type = BTRFS_COMPRESS_NONE; |
5dc562c5 | 59 | em->generation = 0; |
490b54d6 | 60 | refcount_set(&em->refs, 1); |
5dc562c5 | 61 | INIT_LIST_HEAD(&em->list); |
a52d9a80 CM |
62 | return em; |
63 | } | |
a52d9a80 | 64 | |
9d2423c5 CH |
65 | /** |
66 | * free_extent_map - drop reference count of an extent_map | |
01327610 | 67 | * @em: extent map being released |
9d2423c5 CH |
68 | * |
69 | * Drops the reference out on @em by one and free the structure | |
70 | * if the reference count hits zero. | |
71 | */ | |
a52d9a80 CM |
72 | void free_extent_map(struct extent_map *em) |
73 | { | |
2bf5a725 CM |
74 | if (!em) |
75 | return; | |
490b54d6 ER |
76 | WARN_ON(refcount_read(&em->refs) == 0); |
77 | if (refcount_dec_and_test(&em->refs)) { | |
cbc0e928 | 78 | WARN_ON(extent_map_in_tree(em)); |
5dc562c5 | 79 | WARN_ON(!list_empty(&em->list)); |
298a8f9c | 80 | if (test_bit(EXTENT_FLAG_FS_MAPPING, &em->flags)) |
95617d69 | 81 | kfree(em->map_lookup); |
a52d9a80 CM |
82 | kmem_cache_free(extent_map_cache, em); |
83 | } | |
84 | } | |
a52d9a80 | 85 | |
32193c14 FDBM |
86 | /* simple helper to do math around the end of an extent, handling wrap */ |
87 | static u64 range_end(u64 start, u64 len) | |
88 | { | |
89 | if (start + len < start) | |
90 | return (u64)-1; | |
91 | return start + len; | |
92 | } | |
93 | ||
07e1ce09 | 94 | static int tree_insert(struct rb_root_cached *root, struct extent_map *em) |
a52d9a80 | 95 | { |
07e1ce09 | 96 | struct rb_node **p = &root->rb_root.rb_node; |
d397712b | 97 | struct rb_node *parent = NULL; |
32193c14 FDBM |
98 | struct extent_map *entry = NULL; |
99 | struct rb_node *orig_parent = NULL; | |
100 | u64 end = range_end(em->start, em->len); | |
07e1ce09 | 101 | bool leftmost = true; |
a52d9a80 | 102 | |
d397712b | 103 | while (*p) { |
a52d9a80 | 104 | parent = *p; |
d1310b2e CM |
105 | entry = rb_entry(parent, struct extent_map, rb_node); |
106 | ||
07e1ce09 | 107 | if (em->start < entry->start) { |
a52d9a80 | 108 | p = &(*p)->rb_left; |
07e1ce09 | 109 | } else if (em->start >= extent_map_end(entry)) { |
a52d9a80 | 110 | p = &(*p)->rb_right; |
07e1ce09 LB |
111 | leftmost = false; |
112 | } else { | |
32193c14 | 113 | return -EEXIST; |
07e1ce09 | 114 | } |
a52d9a80 CM |
115 | } |
116 | ||
32193c14 FDBM |
117 | orig_parent = parent; |
118 | while (parent && em->start >= extent_map_end(entry)) { | |
119 | parent = rb_next(parent); | |
120 | entry = rb_entry(parent, struct extent_map, rb_node); | |
121 | } | |
122 | if (parent) | |
123 | if (end > entry->start && em->start < extent_map_end(entry)) | |
124 | return -EEXIST; | |
125 | ||
126 | parent = orig_parent; | |
127 | entry = rb_entry(parent, struct extent_map, rb_node); | |
128 | while (parent && em->start < entry->start) { | |
129 | parent = rb_prev(parent); | |
130 | entry = rb_entry(parent, struct extent_map, rb_node); | |
131 | } | |
132 | if (parent) | |
133 | if (end > entry->start && em->start < extent_map_end(entry)) | |
134 | return -EEXIST; | |
135 | ||
32193c14 | 136 | rb_link_node(&em->rb_node, orig_parent, p); |
07e1ce09 | 137 | rb_insert_color_cached(&em->rb_node, root, leftmost); |
32193c14 | 138 | return 0; |
a52d9a80 CM |
139 | } |
140 | ||
d352ac68 CM |
141 | /* |
142 | * search through the tree for an extent_map with a given offset. If | |
143 | * it can't be found, try to find some neighboring extents | |
144 | */ | |
a52d9a80 | 145 | static struct rb_node *__tree_search(struct rb_root *root, u64 offset, |
5f56406a CM |
146 | struct rb_node **prev_ret, |
147 | struct rb_node **next_ret) | |
a52d9a80 | 148 | { |
d397712b | 149 | struct rb_node *n = root->rb_node; |
a52d9a80 | 150 | struct rb_node *prev = NULL; |
5f56406a | 151 | struct rb_node *orig_prev = NULL; |
d1310b2e CM |
152 | struct extent_map *entry; |
153 | struct extent_map *prev_entry = NULL; | |
a52d9a80 | 154 | |
d397712b | 155 | while (n) { |
d1310b2e | 156 | entry = rb_entry(n, struct extent_map, rb_node); |
a52d9a80 CM |
157 | prev = n; |
158 | prev_entry = entry; | |
159 | ||
160 | if (offset < entry->start) | |
161 | n = n->rb_left; | |
d1310b2e | 162 | else if (offset >= extent_map_end(entry)) |
a52d9a80 CM |
163 | n = n->rb_right; |
164 | else | |
165 | return n; | |
166 | } | |
5f56406a CM |
167 | |
168 | if (prev_ret) { | |
169 | orig_prev = prev; | |
d397712b | 170 | while (prev && offset >= extent_map_end(prev_entry)) { |
5f56406a | 171 | prev = rb_next(prev); |
d1310b2e | 172 | prev_entry = rb_entry(prev, struct extent_map, rb_node); |
5f56406a CM |
173 | } |
174 | *prev_ret = prev; | |
175 | prev = orig_prev; | |
176 | } | |
177 | ||
178 | if (next_ret) { | |
d1310b2e | 179 | prev_entry = rb_entry(prev, struct extent_map, rb_node); |
d397712b | 180 | while (prev && offset < prev_entry->start) { |
5f56406a | 181 | prev = rb_prev(prev); |
d1310b2e | 182 | prev_entry = rb_entry(prev, struct extent_map, rb_node); |
5f56406a CM |
183 | } |
184 | *next_ret = prev; | |
a52d9a80 | 185 | } |
a52d9a80 CM |
186 | return NULL; |
187 | } | |
188 | ||
d352ac68 | 189 | /* check to see if two extent_map structs are adjacent and safe to merge */ |
d1310b2e | 190 | static int mergable_maps(struct extent_map *prev, struct extent_map *next) |
a52d9a80 | 191 | { |
7f3c74fb CM |
192 | if (test_bit(EXTENT_FLAG_PINNED, &prev->flags)) |
193 | return 0; | |
194 | ||
c8b97818 CM |
195 | /* |
196 | * don't merge compressed extents, we need to know their | |
197 | * actual size | |
198 | */ | |
199 | if (test_bit(EXTENT_FLAG_COMPRESSED, &prev->flags)) | |
200 | return 0; | |
201 | ||
201a9038 JB |
202 | if (test_bit(EXTENT_FLAG_LOGGING, &prev->flags) || |
203 | test_bit(EXTENT_FLAG_LOGGING, &next->flags)) | |
204 | return 0; | |
205 | ||
09a2a8f9 JB |
206 | /* |
207 | * We don't want to merge stuff that hasn't been written to the log yet | |
208 | * since it may not reflect exactly what is on disk, and that would be | |
209 | * bad. | |
210 | */ | |
211 | if (!list_empty(&prev->list) || !list_empty(&next->list)) | |
212 | return 0; | |
213 | ||
951e05a9 NB |
214 | ASSERT(next->block_start != EXTENT_MAP_DELALLOC && |
215 | prev->block_start != EXTENT_MAP_DELALLOC); | |
216 | ||
c3e14909 DS |
217 | if (prev->map_lookup || next->map_lookup) |
218 | ASSERT(test_bit(EXTENT_FLAG_FS_MAPPING, &prev->flags) && | |
219 | test_bit(EXTENT_FLAG_FS_MAPPING, &next->flags)); | |
220 | ||
d1310b2e CM |
221 | if (extent_map_end(prev) == next->start && |
222 | prev->flags == next->flags && | |
c3e14909 | 223 | prev->map_lookup == next->map_lookup && |
d1310b2e CM |
224 | ((next->block_start == EXTENT_MAP_HOLE && |
225 | prev->block_start == EXTENT_MAP_HOLE) || | |
226 | (next->block_start == EXTENT_MAP_INLINE && | |
227 | prev->block_start == EXTENT_MAP_INLINE) || | |
d1310b2e CM |
228 | (next->block_start < EXTENT_MAP_LAST_BYTE - 1 && |
229 | next->block_start == extent_map_block_end(prev)))) { | |
230 | return 1; | |
231 | } | |
a52d9a80 CM |
232 | return 0; |
233 | } | |
234 | ||
4d2c8f62 | 235 | static void try_merge_map(struct extent_map_tree *tree, struct extent_map *em) |
a1ed835e | 236 | { |
a1ed835e CM |
237 | struct extent_map *merge = NULL; |
238 | struct rb_node *rb; | |
a1ed835e | 239 | |
ac05ca91 FM |
240 | /* |
241 | * We can't modify an extent map that is in the tree and that is being | |
242 | * used by another task, as it can cause that other task to see it in | |
243 | * inconsistent state during the merging. We always have 1 reference for | |
244 | * the tree and 1 for this task (which is unpinning the extent map or | |
245 | * clearing the logging flag), so anything > 2 means it's being used by | |
246 | * other tasks too. | |
247 | */ | |
248 | if (refcount_read(&em->refs) > 2) | |
249 | return; | |
250 | ||
a1ed835e CM |
251 | if (em->start != 0) { |
252 | rb = rb_prev(&em->rb_node); | |
253 | if (rb) | |
254 | merge = rb_entry(rb, struct extent_map, rb_node); | |
255 | if (rb && mergable_maps(merge, em)) { | |
256 | em->start = merge->start; | |
70c8a91c | 257 | em->orig_start = merge->orig_start; |
a1ed835e CM |
258 | em->len += merge->len; |
259 | em->block_len += merge->block_len; | |
260 | em->block_start = merge->block_start; | |
70c8a91c JB |
261 | em->mod_len = (em->mod_len + em->mod_start) - merge->mod_start; |
262 | em->mod_start = merge->mod_start; | |
263 | em->generation = max(em->generation, merge->generation); | |
5dc562c5 | 264 | |
07e1ce09 | 265 | rb_erase_cached(&merge->rb_node, &tree->map); |
cbc0e928 | 266 | RB_CLEAR_NODE(&merge->rb_node); |
a1ed835e CM |
267 | free_extent_map(merge); |
268 | } | |
269 | } | |
270 | ||
271 | rb = rb_next(&em->rb_node); | |
272 | if (rb) | |
273 | merge = rb_entry(rb, struct extent_map, rb_node); | |
274 | if (rb && mergable_maps(em, merge)) { | |
275 | em->len += merge->len; | |
d527afe1 | 276 | em->block_len += merge->block_len; |
07e1ce09 | 277 | rb_erase_cached(&merge->rb_node, &tree->map); |
cbc0e928 | 278 | RB_CLEAR_NODE(&merge->rb_node); |
70c8a91c JB |
279 | em->mod_len = (merge->mod_start + merge->mod_len) - em->mod_start; |
280 | em->generation = max(em->generation, merge->generation); | |
a1ed835e CM |
281 | free_extent_map(merge); |
282 | } | |
4d2c8f62 LZ |
283 | } |
284 | ||
5dc562c5 | 285 | /** |
52b1de91 | 286 | * unpin_extent_cache - unpin an extent from the cache |
5dc562c5 JB |
287 | * @tree: tree to unpin the extent in |
288 | * @start: logical offset in the file | |
289 | * @len: length of the extent | |
290 | * @gen: generation that this extent has been modified in | |
5dc562c5 JB |
291 | * |
292 | * Called after an extent has been written to disk properly. Set the generation | |
293 | * to the generation that actually added the file item to the inode so we know | |
294 | * we need to sync this extent when we call fsync(). | |
295 | */ | |
296 | int unpin_extent_cache(struct extent_map_tree *tree, u64 start, u64 len, | |
297 | u64 gen) | |
4d2c8f62 LZ |
298 | { |
299 | int ret = 0; | |
300 | struct extent_map *em; | |
4e2f84e6 | 301 | bool prealloc = false; |
4d2c8f62 LZ |
302 | |
303 | write_lock(&tree->lock); | |
304 | em = lookup_extent_mapping(tree, start, len); | |
305 | ||
306 | WARN_ON(!em || em->start != start); | |
307 | ||
308 | if (!em) | |
309 | goto out; | |
310 | ||
5dc562c5 | 311 | em->generation = gen; |
4d2c8f62 | 312 | clear_bit(EXTENT_FLAG_PINNED, &em->flags); |
4e2f84e6 LB |
313 | em->mod_start = em->start; |
314 | em->mod_len = em->len; | |
315 | ||
b11e234d | 316 | if (test_bit(EXTENT_FLAG_FILLING, &em->flags)) { |
4e2f84e6 | 317 | prealloc = true; |
b11e234d | 318 | clear_bit(EXTENT_FLAG_FILLING, &em->flags); |
4e2f84e6 | 319 | } |
4d2c8f62 LZ |
320 | |
321 | try_merge_map(tree, em); | |
4e2f84e6 LB |
322 | |
323 | if (prealloc) { | |
324 | em->mod_start = em->start; | |
325 | em->mod_len = em->len; | |
326 | } | |
327 | ||
a1ed835e CM |
328 | free_extent_map(em); |
329 | out: | |
330 | write_unlock(&tree->lock); | |
331 | return ret; | |
332 | ||
333 | } | |
334 | ||
201a9038 JB |
335 | void clear_em_logging(struct extent_map_tree *tree, struct extent_map *em) |
336 | { | |
337 | clear_bit(EXTENT_FLAG_LOGGING, &em->flags); | |
cbc0e928 | 338 | if (extent_map_in_tree(em)) |
222c81dc | 339 | try_merge_map(tree, em); |
201a9038 JB |
340 | } |
341 | ||
176840b3 FM |
342 | static inline void setup_extent_mapping(struct extent_map_tree *tree, |
343 | struct extent_map *em, | |
344 | int modified) | |
345 | { | |
490b54d6 | 346 | refcount_inc(&em->refs); |
176840b3 FM |
347 | em->mod_start = em->start; |
348 | em->mod_len = em->len; | |
349 | ||
350 | if (modified) | |
351 | list_move(&em->list, &tree->modified_extents); | |
352 | else | |
353 | try_merge_map(tree, em); | |
354 | } | |
355 | ||
1c11b63e JM |
356 | static void extent_map_device_set_bits(struct extent_map *em, unsigned bits) |
357 | { | |
358 | struct map_lookup *map = em->map_lookup; | |
359 | u64 stripe_size = em->orig_block_len; | |
360 | int i; | |
361 | ||
362 | for (i = 0; i < map->num_stripes; i++) { | |
363 | struct btrfs_bio_stripe *stripe = &map->stripes[i]; | |
364 | struct btrfs_device *device = stripe->dev; | |
365 | ||
366 | set_extent_bits_nowait(&device->alloc_state, stripe->physical, | |
367 | stripe->physical + stripe_size - 1, bits); | |
368 | } | |
369 | } | |
370 | ||
371 | static void extent_map_device_clear_bits(struct extent_map *em, unsigned bits) | |
372 | { | |
373 | struct map_lookup *map = em->map_lookup; | |
374 | u64 stripe_size = em->orig_block_len; | |
375 | int i; | |
376 | ||
377 | for (i = 0; i < map->num_stripes; i++) { | |
378 | struct btrfs_bio_stripe *stripe = &map->stripes[i]; | |
379 | struct btrfs_device *device = stripe->dev; | |
380 | ||
381 | __clear_extent_bit(&device->alloc_state, stripe->physical, | |
382 | stripe->physical + stripe_size - 1, bits, | |
383 | 0, 0, NULL, GFP_NOWAIT, NULL); | |
384 | } | |
385 | } | |
386 | ||
9d2423c5 | 387 | /** |
401bd2dd NB |
388 | * Add new extent map to the extent tree |
389 | * | |
9d2423c5 CH |
390 | * @tree: tree to insert new map in |
391 | * @em: map to insert | |
401bd2dd NB |
392 | * @modified: indicate whether the given @em should be added to the |
393 | * modified list, which indicates the extent needs to be logged | |
9d2423c5 CH |
394 | * |
395 | * Insert @em into @tree or perform a simple forward/backward merge with | |
396 | * existing mappings. The extent_map struct passed in will be inserted | |
397 | * into the tree directly, with an additional reference taken, or a | |
25985edc | 398 | * reference dropped if the merge attempt was successful. |
a52d9a80 CM |
399 | */ |
400 | int add_extent_mapping(struct extent_map_tree *tree, | |
09a2a8f9 | 401 | struct extent_map *em, int modified) |
a52d9a80 CM |
402 | { |
403 | int ret = 0; | |
a52d9a80 | 404 | |
d23ea3fa DS |
405 | lockdep_assert_held_write(&tree->lock); |
406 | ||
32193c14 FDBM |
407 | ret = tree_insert(&tree->map, em); |
408 | if (ret) | |
a52d9a80 | 409 | goto out; |
32193c14 | 410 | |
176840b3 | 411 | setup_extent_mapping(tree, em, modified); |
8811133d | 412 | if (test_bit(EXTENT_FLAG_FS_MAPPING, &em->flags)) { |
1c11b63e | 413 | extent_map_device_set_bits(em, CHUNK_ALLOCATED); |
8811133d NB |
414 | extent_map_device_clear_bits(em, CHUNK_TRIMMED); |
415 | } | |
a52d9a80 | 416 | out: |
a52d9a80 CM |
417 | return ret; |
418 | } | |
a52d9a80 | 419 | |
48a3b636 ES |
420 | static struct extent_map * |
421 | __lookup_extent_mapping(struct extent_map_tree *tree, | |
422 | u64 start, u64 len, int strict) | |
a52d9a80 CM |
423 | { |
424 | struct extent_map *em; | |
425 | struct rb_node *rb_node; | |
306929f3 CH |
426 | struct rb_node *prev = NULL; |
427 | struct rb_node *next = NULL; | |
428 | u64 end = range_end(start, len); | |
429 | ||
07e1ce09 | 430 | rb_node = __tree_search(&tree->map.rb_root, start, &prev, &next); |
a52d9a80 | 431 | if (!rb_node) { |
ed64f066 LZ |
432 | if (prev) |
433 | rb_node = prev; | |
434 | else if (next) | |
435 | rb_node = next; | |
436 | else | |
437 | return NULL; | |
a52d9a80 | 438 | } |
ed64f066 | 439 | |
a52d9a80 | 440 | em = rb_entry(rb_node, struct extent_map, rb_node); |
d1310b2e | 441 | |
ed64f066 LZ |
442 | if (strict && !(end > em->start && start < extent_map_end(em))) |
443 | return NULL; | |
d1310b2e | 444 | |
490b54d6 | 445 | refcount_inc(&em->refs); |
a52d9a80 CM |
446 | return em; |
447 | } | |
a52d9a80 | 448 | |
ed64f066 LZ |
449 | /** |
450 | * lookup_extent_mapping - lookup extent_map | |
451 | * @tree: tree to lookup in | |
452 | * @start: byte offset to start the search | |
453 | * @len: length of the lookup range | |
454 | * | |
455 | * Find and return the first extent_map struct in @tree that intersects the | |
456 | * [start, len] range. There may be additional objects in the tree that | |
457 | * intersect, so check the object returned carefully to make sure that no | |
458 | * additional lookups are needed. | |
459 | */ | |
460 | struct extent_map *lookup_extent_mapping(struct extent_map_tree *tree, | |
461 | u64 start, u64 len) | |
462 | { | |
463 | return __lookup_extent_mapping(tree, start, len, 1); | |
464 | } | |
465 | ||
b917b7c3 CM |
466 | /** |
467 | * search_extent_mapping - find a nearby extent map | |
468 | * @tree: tree to lookup in | |
469 | * @start: byte offset to start the search | |
470 | * @len: length of the lookup range | |
471 | * | |
472 | * Find and return the first extent_map struct in @tree that intersects the | |
473 | * [start, len] range. | |
474 | * | |
475 | * If one can't be found, any nearby extent may be returned | |
476 | */ | |
477 | struct extent_map *search_extent_mapping(struct extent_map_tree *tree, | |
478 | u64 start, u64 len) | |
479 | { | |
ed64f066 | 480 | return __lookup_extent_mapping(tree, start, len, 0); |
b917b7c3 CM |
481 | } |
482 | ||
9d2423c5 CH |
483 | /** |
484 | * remove_extent_mapping - removes an extent_map from the extent tree | |
485 | * @tree: extent tree to remove from | |
bb7ab3b9 | 486 | * @em: extent map being removed |
9d2423c5 CH |
487 | * |
488 | * Removes @em from @tree. No reference counts are dropped, and no checks | |
489 | * are done to see if the range is in use | |
a52d9a80 | 490 | */ |
c1766dd7 | 491 | void remove_extent_mapping(struct extent_map_tree *tree, struct extent_map *em) |
a52d9a80 | 492 | { |
7f3c74fb | 493 | WARN_ON(test_bit(EXTENT_FLAG_PINNED, &em->flags)); |
07e1ce09 | 494 | rb_erase_cached(&em->rb_node, &tree->map); |
ff44c6e3 JB |
495 | if (!test_bit(EXTENT_FLAG_LOGGING, &em->flags)) |
496 | list_del_init(&em->list); | |
1c11b63e JM |
497 | if (test_bit(EXTENT_FLAG_FS_MAPPING, &em->flags)) |
498 | extent_map_device_clear_bits(em, CHUNK_ALLOCATED); | |
cbc0e928 | 499 | RB_CLEAR_NODE(&em->rb_node); |
a52d9a80 | 500 | } |
176840b3 FM |
501 | |
502 | void replace_extent_mapping(struct extent_map_tree *tree, | |
503 | struct extent_map *cur, | |
504 | struct extent_map *new, | |
505 | int modified) | |
506 | { | |
507 | WARN_ON(test_bit(EXTENT_FLAG_PINNED, &cur->flags)); | |
508 | ASSERT(extent_map_in_tree(cur)); | |
509 | if (!test_bit(EXTENT_FLAG_LOGGING, &cur->flags)) | |
510 | list_del_init(&cur->list); | |
07e1ce09 | 511 | rb_replace_node_cached(&cur->rb_node, &new->rb_node, &tree->map); |
176840b3 FM |
512 | RB_CLEAR_NODE(&cur->rb_node); |
513 | ||
514 | setup_extent_mapping(tree, new, modified); | |
515 | } | |
c04e61b5 LB |
516 | |
517 | static struct extent_map *next_extent_map(struct extent_map *em) | |
518 | { | |
519 | struct rb_node *next; | |
520 | ||
521 | next = rb_next(&em->rb_node); | |
522 | if (!next) | |
523 | return NULL; | |
524 | return container_of(next, struct extent_map, rb_node); | |
525 | } | |
526 | ||
527 | static struct extent_map *prev_extent_map(struct extent_map *em) | |
528 | { | |
529 | struct rb_node *prev; | |
530 | ||
531 | prev = rb_prev(&em->rb_node); | |
532 | if (!prev) | |
533 | return NULL; | |
534 | return container_of(prev, struct extent_map, rb_node); | |
535 | } | |
536 | ||
52042d8e AG |
537 | /* |
538 | * Helper for btrfs_get_extent. Given an existing extent in the tree, | |
c04e61b5 LB |
539 | * the existing extent is the nearest extent to map_start, |
540 | * and an extent that you want to insert, deal with overlap and insert | |
541 | * the best fitted new extent into the tree. | |
542 | */ | |
5f4791f4 LB |
543 | static noinline int merge_extent_mapping(struct extent_map_tree *em_tree, |
544 | struct extent_map *existing, | |
545 | struct extent_map *em, | |
546 | u64 map_start) | |
c04e61b5 LB |
547 | { |
548 | struct extent_map *prev; | |
549 | struct extent_map *next; | |
550 | u64 start; | |
551 | u64 end; | |
552 | u64 start_diff; | |
553 | ||
554 | BUG_ON(map_start < em->start || map_start >= extent_map_end(em)); | |
555 | ||
556 | if (existing->start > map_start) { | |
557 | next = existing; | |
558 | prev = prev_extent_map(next); | |
559 | } else { | |
560 | prev = existing; | |
561 | next = next_extent_map(prev); | |
562 | } | |
563 | ||
564 | start = prev ? extent_map_end(prev) : em->start; | |
565 | start = max_t(u64, start, em->start); | |
566 | end = next ? next->start : extent_map_end(em); | |
567 | end = min_t(u64, end, extent_map_end(em)); | |
568 | start_diff = start - em->start; | |
569 | em->start = start; | |
570 | em->len = end - start; | |
571 | if (em->block_start < EXTENT_MAP_LAST_BYTE && | |
572 | !test_bit(EXTENT_FLAG_COMPRESSED, &em->flags)) { | |
573 | em->block_start += start_diff; | |
574 | em->block_len = em->len; | |
575 | } | |
576 | return add_extent_mapping(em_tree, em, 0); | |
577 | } | |
578 | ||
579 | /** | |
9ad37bb3 NB |
580 | * Add extent mapping into em_tree |
581 | * | |
582 | * @fs_info: the filesystem | |
583 | * @em_tree: extent tree into which we want to insert the extent mapping | |
584 | * @em_in: extent we are inserting | |
585 | * @start: start of the logical range btrfs_get_extent() is requesting | |
586 | * @len: length of the logical range btrfs_get_extent() is requesting | |
c04e61b5 LB |
587 | * |
588 | * Note that @em_in's range may be different from [start, start+len), | |
589 | * but they must be overlapped. | |
590 | * | |
591 | * Insert @em_in into @em_tree. In case there is an overlapping range, handle | |
592 | * the -EEXIST by either: | |
593 | * a) Returning the existing extent in @em_in if @start is within the | |
594 | * existing em. | |
595 | * b) Merge the existing extent with @em_in passed in. | |
596 | * | |
597 | * Return 0 on success, otherwise -EEXIST. | |
598 | * | |
599 | */ | |
f46b24c9 DS |
600 | int btrfs_add_extent_mapping(struct btrfs_fs_info *fs_info, |
601 | struct extent_map_tree *em_tree, | |
c04e61b5 LB |
602 | struct extent_map **em_in, u64 start, u64 len) |
603 | { | |
604 | int ret; | |
605 | struct extent_map *em = *em_in; | |
606 | ||
607 | ret = add_extent_mapping(em_tree, em, 0); | |
608 | /* it is possible that someone inserted the extent into the tree | |
609 | * while we had the lock dropped. It is also possible that | |
610 | * an overlapping map exists in the tree | |
611 | */ | |
612 | if (ret == -EEXIST) { | |
613 | struct extent_map *existing; | |
614 | ||
615 | ret = 0; | |
616 | ||
617 | existing = search_extent_mapping(em_tree, start, len); | |
393da918 | 618 | |
f46b24c9 | 619 | trace_btrfs_handle_em_exist(fs_info, existing, em, start, len); |
393da918 | 620 | |
c04e61b5 LB |
621 | /* |
622 | * existing will always be non-NULL, since there must be | |
623 | * extent causing the -EEXIST. | |
624 | */ | |
625 | if (start >= existing->start && | |
626 | start < extent_map_end(existing)) { | |
627 | free_extent_map(em); | |
628 | *em_in = existing; | |
629 | ret = 0; | |
630 | } else { | |
9a7e10e7 LB |
631 | u64 orig_start = em->start; |
632 | u64 orig_len = em->len; | |
633 | ||
c04e61b5 LB |
634 | /* |
635 | * The existing extent map is the one nearest to | |
636 | * the [start, start + len) range which overlaps | |
637 | */ | |
638 | ret = merge_extent_mapping(em_tree, existing, | |
639 | em, start); | |
c04e61b5 LB |
640 | if (ret) { |
641 | free_extent_map(em); | |
642 | *em_in = NULL; | |
9a7e10e7 LB |
643 | WARN_ONCE(ret, |
644 | "unexpected error %d: merge existing(start %llu len %llu) with em(start %llu len %llu)\n", | |
645 | ret, existing->start, existing->len, | |
646 | orig_start, orig_len); | |
c04e61b5 | 647 | } |
9a7e10e7 | 648 | free_extent_map(existing); |
c04e61b5 LB |
649 | } |
650 | } | |
651 | ||
652 | ASSERT(ret == 0 || ret == -EEXIST); | |
653 | return ret; | |
654 | } |