1 // SPDX-License-Identifier: GPL-2.0
4 #include <linux/slab.h>
5 #include <linux/spinlock.h>
9 #include "extent_map.h"
10 #include "compression.h"
11 #include "btrfs_inode.h"
14 static struct kmem_cache *extent_map_cache;
16 int __init extent_map_init(void)
18 extent_map_cache = kmem_cache_create("btrfs_extent_map",
19 sizeof(struct extent_map), 0,
20 SLAB_MEM_SPREAD, NULL);
21 if (!extent_map_cache)
26 void __cold extent_map_exit(void)
28 kmem_cache_destroy(extent_map_cache);
32 * Initialize the extent tree @tree. Should be called for each new inode or
33 * other user of the extent_map interface.
35 void extent_map_tree_init(struct extent_map_tree *tree)
37 tree->map = RB_ROOT_CACHED;
38 INIT_LIST_HEAD(&tree->modified_extents);
39 rwlock_init(&tree->lock);
43 * Allocate a new extent_map structure. The new structure is returned with a
44 * reference count of one and needs to be freed using free_extent_map()
46 struct extent_map *alloc_extent_map(void)
48 struct extent_map *em;
49 em = kmem_cache_zalloc(extent_map_cache, GFP_NOFS);
52 RB_CLEAR_NODE(&em->rb_node);
53 em->compress_type = BTRFS_COMPRESS_NONE;
54 refcount_set(&em->refs, 1);
55 INIT_LIST_HEAD(&em->list);
60 * Drop the reference out on @em by one and free the structure if the reference
63 void free_extent_map(struct extent_map *em)
67 if (refcount_dec_and_test(&em->refs)) {
68 WARN_ON(extent_map_in_tree(em));
69 WARN_ON(!list_empty(&em->list));
70 if (test_bit(EXTENT_FLAG_FS_MAPPING, &em->flags))
71 kfree(em->map_lookup);
72 kmem_cache_free(extent_map_cache, em);
76 /* Do the math around the end of an extent, handling wrapping. */
77 static u64 range_end(u64 start, u64 len)
79 if (start + len < start)
84 static int tree_insert(struct rb_root_cached *root, struct extent_map *em)
86 struct rb_node **p = &root->rb_root.rb_node;
87 struct rb_node *parent = NULL;
88 struct extent_map *entry = NULL;
89 struct rb_node *orig_parent = NULL;
90 u64 end = range_end(em->start, em->len);
95 entry = rb_entry(parent, struct extent_map, rb_node);
97 if (em->start < entry->start) {
99 } else if (em->start >= extent_map_end(entry)) {
107 orig_parent = parent;
108 while (parent && em->start >= extent_map_end(entry)) {
109 parent = rb_next(parent);
110 entry = rb_entry(parent, struct extent_map, rb_node);
113 if (end > entry->start && em->start < extent_map_end(entry))
116 parent = orig_parent;
117 entry = rb_entry(parent, struct extent_map, rb_node);
118 while (parent && em->start < entry->start) {
119 parent = rb_prev(parent);
120 entry = rb_entry(parent, struct extent_map, rb_node);
123 if (end > entry->start && em->start < extent_map_end(entry))
126 rb_link_node(&em->rb_node, orig_parent, p);
127 rb_insert_color_cached(&em->rb_node, root, leftmost);
132 * Search through the tree for an extent_map with a given offset. If it can't
133 * be found, try to find some neighboring extents
135 static struct rb_node *__tree_search(struct rb_root *root, u64 offset,
136 struct rb_node **prev_or_next_ret)
138 struct rb_node *n = root->rb_node;
139 struct rb_node *prev = NULL;
140 struct rb_node *orig_prev = NULL;
141 struct extent_map *entry;
142 struct extent_map *prev_entry = NULL;
144 ASSERT(prev_or_next_ret);
147 entry = rb_entry(n, struct extent_map, rb_node);
151 if (offset < entry->start)
153 else if (offset >= extent_map_end(entry))
160 while (prev && offset >= extent_map_end(prev_entry)) {
161 prev = rb_next(prev);
162 prev_entry = rb_entry(prev, struct extent_map, rb_node);
166 * Previous extent map found, return as in this case the caller does not
167 * care about the next one.
170 *prev_or_next_ret = prev;
175 prev_entry = rb_entry(prev, struct extent_map, rb_node);
176 while (prev && offset < prev_entry->start) {
177 prev = rb_prev(prev);
178 prev_entry = rb_entry(prev, struct extent_map, rb_node);
180 *prev_or_next_ret = prev;
185 /* Check to see if two extent_map structs are adjacent and safe to merge. */
186 static int mergable_maps(struct extent_map *prev, struct extent_map *next)
188 if (test_bit(EXTENT_FLAG_PINNED, &prev->flags))
192 * don't merge compressed extents, we need to know their
195 if (test_bit(EXTENT_FLAG_COMPRESSED, &prev->flags))
198 if (test_bit(EXTENT_FLAG_LOGGING, &prev->flags) ||
199 test_bit(EXTENT_FLAG_LOGGING, &next->flags))
203 * We don't want to merge stuff that hasn't been written to the log yet
204 * since it may not reflect exactly what is on disk, and that would be
207 if (!list_empty(&prev->list) || !list_empty(&next->list))
210 ASSERT(next->block_start != EXTENT_MAP_DELALLOC &&
211 prev->block_start != EXTENT_MAP_DELALLOC);
213 if (prev->map_lookup || next->map_lookup)
214 ASSERT(test_bit(EXTENT_FLAG_FS_MAPPING, &prev->flags) &&
215 test_bit(EXTENT_FLAG_FS_MAPPING, &next->flags));
217 if (extent_map_end(prev) == next->start &&
218 prev->flags == next->flags &&
219 prev->map_lookup == next->map_lookup &&
220 ((next->block_start == EXTENT_MAP_HOLE &&
221 prev->block_start == EXTENT_MAP_HOLE) ||
222 (next->block_start == EXTENT_MAP_INLINE &&
223 prev->block_start == EXTENT_MAP_INLINE) ||
224 (next->block_start < EXTENT_MAP_LAST_BYTE - 1 &&
225 next->block_start == extent_map_block_end(prev)))) {
231 static void try_merge_map(struct extent_map_tree *tree, struct extent_map *em)
233 struct extent_map *merge = NULL;
237 * We can't modify an extent map that is in the tree and that is being
238 * used by another task, as it can cause that other task to see it in
239 * inconsistent state during the merging. We always have 1 reference for
240 * the tree and 1 for this task (which is unpinning the extent map or
241 * clearing the logging flag), so anything > 2 means it's being used by
244 if (refcount_read(&em->refs) > 2)
247 if (em->start != 0) {
248 rb = rb_prev(&em->rb_node);
250 merge = rb_entry(rb, struct extent_map, rb_node);
251 if (rb && mergable_maps(merge, em)) {
252 em->start = merge->start;
253 em->orig_start = merge->orig_start;
254 em->len += merge->len;
255 em->block_len += merge->block_len;
256 em->block_start = merge->block_start;
257 em->mod_len = (em->mod_len + em->mod_start) - merge->mod_start;
258 em->mod_start = merge->mod_start;
259 em->generation = max(em->generation, merge->generation);
260 set_bit(EXTENT_FLAG_MERGED, &em->flags);
262 rb_erase_cached(&merge->rb_node, &tree->map);
263 RB_CLEAR_NODE(&merge->rb_node);
264 free_extent_map(merge);
268 rb = rb_next(&em->rb_node);
270 merge = rb_entry(rb, struct extent_map, rb_node);
271 if (rb && mergable_maps(em, merge)) {
272 em->len += merge->len;
273 em->block_len += merge->block_len;
274 rb_erase_cached(&merge->rb_node, &tree->map);
275 RB_CLEAR_NODE(&merge->rb_node);
276 em->mod_len = (merge->mod_start + merge->mod_len) - em->mod_start;
277 em->generation = max(em->generation, merge->generation);
278 set_bit(EXTENT_FLAG_MERGED, &em->flags);
279 free_extent_map(merge);
284 * Unpin an extent from the cache.
286 * @tree: tree to unpin the extent in
287 * @start: logical offset in the file
288 * @len: length of the extent
289 * @gen: generation that this extent has been modified in
291 * Called after an extent has been written to disk properly. Set the generation
292 * to the generation that actually added the file item to the inode so we know
293 * we need to sync this extent when we call fsync().
295 int unpin_extent_cache(struct extent_map_tree *tree, u64 start, u64 len,
299 struct extent_map *em;
300 bool prealloc = false;
302 write_lock(&tree->lock);
303 em = lookup_extent_mapping(tree, start, len);
305 WARN_ON(!em || em->start != start);
310 em->generation = gen;
311 clear_bit(EXTENT_FLAG_PINNED, &em->flags);
312 em->mod_start = em->start;
313 em->mod_len = em->len;
315 if (test_bit(EXTENT_FLAG_FILLING, &em->flags)) {
317 clear_bit(EXTENT_FLAG_FILLING, &em->flags);
320 try_merge_map(tree, em);
323 em->mod_start = em->start;
324 em->mod_len = em->len;
329 write_unlock(&tree->lock);
334 void clear_em_logging(struct extent_map_tree *tree, struct extent_map *em)
336 lockdep_assert_held_write(&tree->lock);
338 clear_bit(EXTENT_FLAG_LOGGING, &em->flags);
339 if (extent_map_in_tree(em))
340 try_merge_map(tree, em);
343 static inline void setup_extent_mapping(struct extent_map_tree *tree,
344 struct extent_map *em,
347 refcount_inc(&em->refs);
348 em->mod_start = em->start;
349 em->mod_len = em->len;
352 list_move(&em->list, &tree->modified_extents);
354 try_merge_map(tree, em);
357 static void extent_map_device_set_bits(struct extent_map *em, unsigned bits)
359 struct map_lookup *map = em->map_lookup;
360 u64 stripe_size = em->orig_block_len;
363 for (i = 0; i < map->num_stripes; i++) {
364 struct btrfs_io_stripe *stripe = &map->stripes[i];
365 struct btrfs_device *device = stripe->dev;
367 set_extent_bit(&device->alloc_state, stripe->physical,
368 stripe->physical + stripe_size - 1,
369 bits | EXTENT_NOWAIT, NULL);
373 static void extent_map_device_clear_bits(struct extent_map *em, unsigned bits)
375 struct map_lookup *map = em->map_lookup;
376 u64 stripe_size = em->orig_block_len;
379 for (i = 0; i < map->num_stripes; i++) {
380 struct btrfs_io_stripe *stripe = &map->stripes[i];
381 struct btrfs_device *device = stripe->dev;
383 __clear_extent_bit(&device->alloc_state, stripe->physical,
384 stripe->physical + stripe_size - 1,
385 bits | EXTENT_NOWAIT,
391 * Add new extent map to the extent tree
393 * @tree: tree to insert new map in
395 * @modified: indicate whether the given @em should be added to the
396 * modified list, which indicates the extent needs to be logged
398 * Insert @em into @tree or perform a simple forward/backward merge with
399 * existing mappings. The extent_map struct passed in will be inserted
400 * into the tree directly, with an additional reference taken, or a
401 * reference dropped if the merge attempt was successful.
403 int add_extent_mapping(struct extent_map_tree *tree,
404 struct extent_map *em, int modified)
408 lockdep_assert_held_write(&tree->lock);
410 ret = tree_insert(&tree->map, em);
414 setup_extent_mapping(tree, em, modified);
415 if (test_bit(EXTENT_FLAG_FS_MAPPING, &em->flags)) {
416 extent_map_device_set_bits(em, CHUNK_ALLOCATED);
417 extent_map_device_clear_bits(em, CHUNK_TRIMMED);
423 static struct extent_map *
424 __lookup_extent_mapping(struct extent_map_tree *tree,
425 u64 start, u64 len, int strict)
427 struct extent_map *em;
428 struct rb_node *rb_node;
429 struct rb_node *prev_or_next = NULL;
430 u64 end = range_end(start, len);
432 rb_node = __tree_search(&tree->map.rb_root, start, &prev_or_next);
435 rb_node = prev_or_next;
440 em = rb_entry(rb_node, struct extent_map, rb_node);
442 if (strict && !(end > em->start && start < extent_map_end(em)))
445 refcount_inc(&em->refs);
450 * Lookup extent_map that intersects @start + @len range.
452 * @tree: tree to lookup in
453 * @start: byte offset to start the search
454 * @len: length of the lookup range
456 * Find and return the first extent_map struct in @tree that intersects the
457 * [start, len] range. There may be additional objects in the tree that
458 * intersect, so check the object returned carefully to make sure that no
459 * additional lookups are needed.
461 struct extent_map *lookup_extent_mapping(struct extent_map_tree *tree,
464 return __lookup_extent_mapping(tree, start, len, 1);
468 * Find a nearby extent map intersecting @start + @len (not an exact search).
470 * @tree: tree to lookup in
471 * @start: byte offset to start the search
472 * @len: length of the lookup range
474 * Find and return the first extent_map struct in @tree that intersects the
475 * [start, len] range.
477 * If one can't be found, any nearby extent may be returned
479 struct extent_map *search_extent_mapping(struct extent_map_tree *tree,
482 return __lookup_extent_mapping(tree, start, len, 0);
486 * Remove an extent_map from the extent tree.
488 * @tree: extent tree to remove from
489 * @em: extent map being removed
491 * Remove @em from @tree. No reference counts are dropped, and no checks
492 * are done to see if the range is in use.
494 void remove_extent_mapping(struct extent_map_tree *tree, struct extent_map *em)
496 lockdep_assert_held_write(&tree->lock);
498 WARN_ON(test_bit(EXTENT_FLAG_PINNED, &em->flags));
499 rb_erase_cached(&em->rb_node, &tree->map);
500 if (!test_bit(EXTENT_FLAG_LOGGING, &em->flags))
501 list_del_init(&em->list);
502 if (test_bit(EXTENT_FLAG_FS_MAPPING, &em->flags))
503 extent_map_device_clear_bits(em, CHUNK_ALLOCATED);
504 RB_CLEAR_NODE(&em->rb_node);
507 static void replace_extent_mapping(struct extent_map_tree *tree,
508 struct extent_map *cur,
509 struct extent_map *new,
512 lockdep_assert_held_write(&tree->lock);
514 WARN_ON(test_bit(EXTENT_FLAG_PINNED, &cur->flags));
515 ASSERT(extent_map_in_tree(cur));
516 if (!test_bit(EXTENT_FLAG_LOGGING, &cur->flags))
517 list_del_init(&cur->list);
518 rb_replace_node_cached(&cur->rb_node, &new->rb_node, &tree->map);
519 RB_CLEAR_NODE(&cur->rb_node);
521 setup_extent_mapping(tree, new, modified);
524 static struct extent_map *next_extent_map(const struct extent_map *em)
526 struct rb_node *next;
528 next = rb_next(&em->rb_node);
531 return container_of(next, struct extent_map, rb_node);
534 static struct extent_map *prev_extent_map(struct extent_map *em)
536 struct rb_node *prev;
538 prev = rb_prev(&em->rb_node);
541 return container_of(prev, struct extent_map, rb_node);
545 * Helper for btrfs_get_extent. Given an existing extent in the tree,
546 * the existing extent is the nearest extent to map_start,
547 * and an extent that you want to insert, deal with overlap and insert
548 * the best fitted new extent into the tree.
550 static noinline int merge_extent_mapping(struct extent_map_tree *em_tree,
551 struct extent_map *existing,
552 struct extent_map *em,
555 struct extent_map *prev;
556 struct extent_map *next;
561 BUG_ON(map_start < em->start || map_start >= extent_map_end(em));
563 if (existing->start > map_start) {
565 prev = prev_extent_map(next);
568 next = next_extent_map(prev);
571 start = prev ? extent_map_end(prev) : em->start;
572 start = max_t(u64, start, em->start);
573 end = next ? next->start : extent_map_end(em);
574 end = min_t(u64, end, extent_map_end(em));
575 start_diff = start - em->start;
577 em->len = end - start;
578 if (em->block_start < EXTENT_MAP_LAST_BYTE &&
579 !test_bit(EXTENT_FLAG_COMPRESSED, &em->flags)) {
580 em->block_start += start_diff;
581 em->block_len = em->len;
583 return add_extent_mapping(em_tree, em, 0);
587 * Add extent mapping into em_tree.
589 * @fs_info: the filesystem
590 * @em_tree: extent tree into which we want to insert the extent mapping
591 * @em_in: extent we are inserting
592 * @start: start of the logical range btrfs_get_extent() is requesting
593 * @len: length of the logical range btrfs_get_extent() is requesting
595 * Note that @em_in's range may be different from [start, start+len),
596 * but they must be overlapped.
598 * Insert @em_in into @em_tree. In case there is an overlapping range, handle
599 * the -EEXIST by either:
600 * a) Returning the existing extent in @em_in if @start is within the
602 * b) Merge the existing extent with @em_in passed in.
604 * Return 0 on success, otherwise -EEXIST.
607 int btrfs_add_extent_mapping(struct btrfs_fs_info *fs_info,
608 struct extent_map_tree *em_tree,
609 struct extent_map **em_in, u64 start, u64 len)
612 struct extent_map *em = *em_in;
615 * Tree-checker should have rejected any inline extent with non-zero
616 * file offset. Here just do a sanity check.
618 if (em->block_start == EXTENT_MAP_INLINE)
619 ASSERT(em->start == 0);
621 ret = add_extent_mapping(em_tree, em, 0);
622 /* it is possible that someone inserted the extent into the tree
623 * while we had the lock dropped. It is also possible that
624 * an overlapping map exists in the tree
626 if (ret == -EEXIST) {
627 struct extent_map *existing;
631 existing = search_extent_mapping(em_tree, start, len);
633 trace_btrfs_handle_em_exist(fs_info, existing, em, start, len);
636 * existing will always be non-NULL, since there must be
637 * extent causing the -EEXIST.
639 if (start >= existing->start &&
640 start < extent_map_end(existing)) {
645 u64 orig_start = em->start;
646 u64 orig_len = em->len;
649 * The existing extent map is the one nearest to
650 * the [start, start + len) range which overlaps
652 ret = merge_extent_mapping(em_tree, existing,
658 "unexpected error %d: merge existing(start %llu len %llu) with em(start %llu len %llu)\n",
659 ret, existing->start, existing->len,
660 orig_start, orig_len);
662 free_extent_map(existing);
666 ASSERT(ret == 0 || ret == -EEXIST);
671 * Drop all extent maps from a tree in the fastest possible way, rescheduling
672 * if needed. This avoids searching the tree, from the root down to the first
673 * extent map, before each deletion.
675 static void drop_all_extent_maps_fast(struct extent_map_tree *tree)
677 write_lock(&tree->lock);
678 while (!RB_EMPTY_ROOT(&tree->map.rb_root)) {
679 struct extent_map *em;
680 struct rb_node *node;
682 node = rb_first_cached(&tree->map);
683 em = rb_entry(node, struct extent_map, rb_node);
684 clear_bit(EXTENT_FLAG_PINNED, &em->flags);
685 clear_bit(EXTENT_FLAG_LOGGING, &em->flags);
686 remove_extent_mapping(tree, em);
688 cond_resched_rwlock_write(&tree->lock);
690 write_unlock(&tree->lock);
694 * Drop all extent maps in a given range.
696 * @inode: The target inode.
697 * @start: Start offset of the range.
698 * @end: End offset of the range (inclusive value).
699 * @skip_pinned: Indicate if pinned extent maps should be ignored or not.
701 * This drops all the extent maps that intersect the given range [@start, @end].
702 * Extent maps that partially overlap the range and extend behind or beyond it,
704 * The caller should have locked an appropriate file range in the inode's io
705 * tree before calling this function.
707 void btrfs_drop_extent_map_range(struct btrfs_inode *inode, u64 start, u64 end,
710 struct extent_map *split;
711 struct extent_map *split2;
712 struct extent_map *em;
713 struct extent_map_tree *em_tree = &inode->extent_tree;
714 u64 len = end - start + 1;
716 WARN_ON(end < start);
717 if (end == (u64)-1) {
718 if (start == 0 && !skip_pinned) {
719 drop_all_extent_maps_fast(em_tree);
724 /* Make end offset exclusive for use in the loop below. */
729 * It's ok if we fail to allocate the extent maps, see the comment near
730 * the bottom of the loop below. We only need two spare extent maps in
731 * the worst case, where the first extent map that intersects our range
732 * starts before the range and the last extent map that intersects our
733 * range ends after our range (and they might be the same extent map),
734 * because we need to split those two extent maps at the boundaries.
736 split = alloc_extent_map();
737 split2 = alloc_extent_map();
739 write_lock(&em_tree->lock);
740 em = lookup_extent_mapping(em_tree, start, len);
743 /* extent_map_end() returns exclusive value (last byte + 1). */
744 const u64 em_end = extent_map_end(em);
745 struct extent_map *next_em = NULL;
752 next_em = next_extent_map(em);
754 if (next_em->start < end)
755 refcount_inc(&next_em->refs);
761 if (skip_pinned && test_bit(EXTENT_FLAG_PINNED, &em->flags)) {
764 len = start + len - em_end;
769 clear_bit(EXTENT_FLAG_PINNED, &em->flags);
771 * In case we split the extent map, we want to preserve the
772 * EXTENT_FLAG_LOGGING flag on our extent map, but we don't want
773 * it on the new extent maps.
775 clear_bit(EXTENT_FLAG_LOGGING, &flags);
776 modified = !list_empty(&em->list);
779 * The extent map does not cross our target range, so no need to
780 * split it, we can remove it directly.
782 if (em->start >= start && em_end <= end)
785 gen = em->generation;
786 compressed = test_bit(EXTENT_FLAG_COMPRESSED, &em->flags);
788 if (em->start < start) {
795 split->start = em->start;
796 split->len = start - em->start;
798 if (em->block_start < EXTENT_MAP_LAST_BYTE) {
799 split->orig_start = em->orig_start;
800 split->block_start = em->block_start;
803 split->block_len = em->block_len;
805 split->block_len = split->len;
806 split->orig_block_len = max(split->block_len,
808 split->ram_bytes = em->ram_bytes;
810 split->orig_start = split->start;
811 split->block_len = 0;
812 split->block_start = em->block_start;
813 split->orig_block_len = 0;
814 split->ram_bytes = split->len;
817 split->generation = gen;
818 split->flags = flags;
819 split->compress_type = em->compress_type;
820 replace_extent_mapping(em_tree, em, split, modified);
821 free_extent_map(split);
832 split->start = start + len;
833 split->len = em_end - (start + len);
834 split->block_start = em->block_start;
835 split->flags = flags;
836 split->compress_type = em->compress_type;
837 split->generation = gen;
839 if (em->block_start < EXTENT_MAP_LAST_BYTE) {
840 split->orig_block_len = max(em->block_len,
843 split->ram_bytes = em->ram_bytes;
845 split->block_len = em->block_len;
846 split->orig_start = em->orig_start;
848 const u64 diff = start + len - em->start;
850 split->block_len = split->len;
851 split->block_start += diff;
852 split->orig_start = em->orig_start;
855 split->ram_bytes = split->len;
856 split->orig_start = split->start;
857 split->block_len = 0;
858 split->orig_block_len = 0;
861 if (extent_map_in_tree(em)) {
862 replace_extent_mapping(em_tree, em, split,
867 ret = add_extent_mapping(em_tree, split,
869 /* Logic error, shouldn't happen. */
871 if (WARN_ON(ret != 0) && modified)
872 btrfs_set_inode_full_sync(inode);
874 free_extent_map(split);
878 if (extent_map_in_tree(em)) {
880 * If the extent map is still in the tree it means that
881 * either of the following is true:
883 * 1) It fits entirely in our range (doesn't end beyond
884 * it or starts before it);
886 * 2) It starts before our range and/or ends after our
887 * range, and we were not able to allocate the extent
888 * maps for split operations, @split and @split2.
890 * If we are at case 2) then we just remove the entire
891 * extent map - this is fine since if anyone needs it to
892 * access the subranges outside our range, will just
893 * load it again from the subvolume tree's file extent
894 * item. However if the extent map was in the list of
895 * modified extents, then we must mark the inode for a
896 * full fsync, otherwise a fast fsync will miss this
897 * extent if it's new and needs to be logged.
899 if ((em->start < start || em_end > end) && modified) {
901 btrfs_set_inode_full_sync(inode);
903 remove_extent_mapping(em_tree, em);
907 * Once for the tree reference (we replaced or removed the
908 * extent map from the tree).
912 /* Once for us (for our lookup reference). */
918 write_unlock(&em_tree->lock);
920 free_extent_map(split);
921 free_extent_map(split2);
925 * Replace a range in the inode's extent map tree with a new extent map.
927 * @inode: The target inode.
928 * @new_em: The new extent map to add to the inode's extent map tree.
929 * @modified: Indicate if the new extent map should be added to the list of
930 * modified extents (for fast fsync tracking).
932 * Drops all the extent maps in the inode's extent map tree that intersect the
933 * range of the new extent map and adds the new extent map to the tree.
934 * The caller should have locked an appropriate file range in the inode's io
935 * tree before calling this function.
937 int btrfs_replace_extent_map_range(struct btrfs_inode *inode,
938 struct extent_map *new_em,
941 const u64 end = new_em->start + new_em->len - 1;
942 struct extent_map_tree *tree = &inode->extent_tree;
945 ASSERT(!extent_map_in_tree(new_em));
948 * The caller has locked an appropriate file range in the inode's io
949 * tree, but getting -EEXIST when adding the new extent map can still
950 * happen in case there are extents that partially cover the range, and
951 * this is due to two tasks operating on different parts of the extent.
952 * See commit 18e83ac75bfe67 ("Btrfs: fix unexpected EEXIST from
953 * btrfs_get_extent") for an example and details.
956 btrfs_drop_extent_map_range(inode, new_em->start, end, false);
957 write_lock(&tree->lock);
958 ret = add_extent_mapping(tree, new_em, modified);
959 write_unlock(&tree->lock);
960 } while (ret == -EEXIST);
966 * Split off the first pre bytes from the extent_map at [start, start + len],
967 * and set the block_start for it to new_logical.
969 * This function is used when an ordered_extent needs to be split.
971 int split_extent_map(struct btrfs_inode *inode, u64 start, u64 len, u64 pre,
974 struct extent_map_tree *em_tree = &inode->extent_tree;
975 struct extent_map *em;
976 struct extent_map *split_pre = NULL;
977 struct extent_map *split_mid = NULL;
984 split_pre = alloc_extent_map();
987 split_mid = alloc_extent_map();
993 lock_extent(&inode->io_tree, start, start + len - 1, NULL);
994 write_lock(&em_tree->lock);
995 em = lookup_extent_mapping(em_tree, start, len);
1001 ASSERT(em->len == len);
1002 ASSERT(!test_bit(EXTENT_FLAG_COMPRESSED, &em->flags));
1003 ASSERT(em->block_start < EXTENT_MAP_LAST_BYTE);
1004 ASSERT(test_bit(EXTENT_FLAG_PINNED, &em->flags));
1005 ASSERT(!test_bit(EXTENT_FLAG_LOGGING, &em->flags));
1006 ASSERT(!list_empty(&em->list));
1009 clear_bit(EXTENT_FLAG_PINNED, &em->flags);
1011 /* First, replace the em with a new extent_map starting from * em->start */
1012 split_pre->start = em->start;
1013 split_pre->len = pre;
1014 split_pre->orig_start = split_pre->start;
1015 split_pre->block_start = new_logical;
1016 split_pre->block_len = split_pre->len;
1017 split_pre->orig_block_len = split_pre->block_len;
1018 split_pre->ram_bytes = split_pre->len;
1019 split_pre->flags = flags;
1020 split_pre->compress_type = em->compress_type;
1021 split_pre->generation = em->generation;
1023 replace_extent_mapping(em_tree, em, split_pre, 1);
1026 * Now we only have an extent_map at:
1027 * [em->start, em->start + pre]
1030 /* Insert the middle extent_map. */
1031 split_mid->start = em->start + pre;
1032 split_mid->len = em->len - pre;
1033 split_mid->orig_start = split_mid->start;
1034 split_mid->block_start = em->block_start + pre;
1035 split_mid->block_len = split_mid->len;
1036 split_mid->orig_block_len = split_mid->block_len;
1037 split_mid->ram_bytes = split_mid->len;
1038 split_mid->flags = flags;
1039 split_mid->compress_type = em->compress_type;
1040 split_mid->generation = em->generation;
1041 add_extent_mapping(em_tree, split_mid, 1);
1044 free_extent_map(em);
1045 /* Once for the tree */
1046 free_extent_map(em);
1049 write_unlock(&em_tree->lock);
1050 unlock_extent(&inode->io_tree, start, start + len - 1, NULL);
1051 free_extent_map(split_mid);
1053 free_extent_map(split_pre);