Lines Matching +full:existing +full:- +full:parts
1 // SPDX-License-Identifier: GPL-2.0
21 return -ENOMEM; in extent_map_init()
31 * extent_map_tree_init - initialize extent map tree
39 tree->map = RB_ROOT_CACHED; in extent_map_tree_init()
40 INIT_LIST_HEAD(&tree->modified_extents); in extent_map_tree_init()
41 rwlock_init(&tree->lock); in extent_map_tree_init()
45 * alloc_extent_map - allocate new extent map structure
57 RB_CLEAR_NODE(&em->rb_node); in alloc_extent_map()
58 em->compress_type = BTRFS_COMPRESS_NONE; in alloc_extent_map()
59 refcount_set(&em->refs, 1); in alloc_extent_map()
60 INIT_LIST_HEAD(&em->list); in alloc_extent_map()
65 * free_extent_map - drop reference count of an extent_map
75 if (refcount_dec_and_test(&em->refs)) { in free_extent_map()
77 WARN_ON(!list_empty(&em->list)); in free_extent_map()
78 if (test_bit(EXTENT_FLAG_FS_MAPPING, &em->flags)) in free_extent_map()
79 kfree(em->map_lookup); in free_extent_map()
88 return (u64)-1; in range_end()
94 struct rb_node **p = &root->rb_root.rb_node; in tree_insert()
98 u64 end = range_end(em->start, em->len); in tree_insert()
105 if (em->start < entry->start) { in tree_insert()
106 p = &(*p)->rb_left; in tree_insert()
107 } else if (em->start >= extent_map_end(entry)) { in tree_insert()
108 p = &(*p)->rb_right; in tree_insert()
111 return -EEXIST; in tree_insert()
116 while (parent && em->start >= extent_map_end(entry)) { in tree_insert()
121 if (end > entry->start && em->start < extent_map_end(entry)) in tree_insert()
122 return -EEXIST; in tree_insert()
126 while (parent && em->start < entry->start) { in tree_insert()
131 if (end > entry->start && em->start < extent_map_end(entry)) in tree_insert()
132 return -EEXIST; in tree_insert()
134 rb_link_node(&em->rb_node, orig_parent, p); in tree_insert()
135 rb_insert_color_cached(&em->rb_node, root, leftmost); in tree_insert()
146 struct rb_node *n = root->rb_node; in __tree_search()
159 if (offset < entry->start) in __tree_search()
160 n = n->rb_left; in __tree_search()
162 n = n->rb_right; in __tree_search()
184 while (prev && offset < prev_entry->start) { in __tree_search()
196 if (test_bit(EXTENT_FLAG_PINNED, &prev->flags)) in mergable_maps()
203 if (test_bit(EXTENT_FLAG_COMPRESSED, &prev->flags)) in mergable_maps()
206 if (test_bit(EXTENT_FLAG_LOGGING, &prev->flags) || in mergable_maps()
207 test_bit(EXTENT_FLAG_LOGGING, &next->flags)) in mergable_maps()
215 if (!list_empty(&prev->list) || !list_empty(&next->list)) in mergable_maps()
218 ASSERT(next->block_start != EXTENT_MAP_DELALLOC && in mergable_maps()
219 prev->block_start != EXTENT_MAP_DELALLOC); in mergable_maps()
221 if (prev->map_lookup || next->map_lookup) in mergable_maps()
222 ASSERT(test_bit(EXTENT_FLAG_FS_MAPPING, &prev->flags) && in mergable_maps()
223 test_bit(EXTENT_FLAG_FS_MAPPING, &next->flags)); in mergable_maps()
225 if (extent_map_end(prev) == next->start && in mergable_maps()
226 prev->flags == next->flags && in mergable_maps()
227 prev->map_lookup == next->map_lookup && in mergable_maps()
228 ((next->block_start == EXTENT_MAP_HOLE && in mergable_maps()
229 prev->block_start == EXTENT_MAP_HOLE) || in mergable_maps()
230 (next->block_start == EXTENT_MAP_INLINE && in mergable_maps()
231 prev->block_start == EXTENT_MAP_INLINE) || in mergable_maps()
232 (next->block_start < EXTENT_MAP_LAST_BYTE - 1 && in mergable_maps()
233 next->block_start == extent_map_block_end(prev)))) { in mergable_maps()
252 if (refcount_read(&em->refs) > 2) in try_merge_map()
255 if (em->start != 0) { in try_merge_map()
256 rb = rb_prev(&em->rb_node); in try_merge_map()
260 em->start = merge->start; in try_merge_map()
261 em->orig_start = merge->orig_start; in try_merge_map()
262 em->len += merge->len; in try_merge_map()
263 em->block_len += merge->block_len; in try_merge_map()
264 em->block_start = merge->block_start; in try_merge_map()
265 em->mod_len = (em->mod_len + em->mod_start) - merge->mod_start; in try_merge_map()
266 em->mod_start = merge->mod_start; in try_merge_map()
267 em->generation = max(em->generation, merge->generation); in try_merge_map()
268 set_bit(EXTENT_FLAG_MERGED, &em->flags); in try_merge_map()
270 rb_erase_cached(&merge->rb_node, &tree->map); in try_merge_map()
271 RB_CLEAR_NODE(&merge->rb_node); in try_merge_map()
276 rb = rb_next(&em->rb_node); in try_merge_map()
280 em->len += merge->len; in try_merge_map()
281 em->block_len += merge->block_len; in try_merge_map()
282 rb_erase_cached(&merge->rb_node, &tree->map); in try_merge_map()
283 RB_CLEAR_NODE(&merge->rb_node); in try_merge_map()
284 em->mod_len = (merge->mod_start + merge->mod_len) - em->mod_start; in try_merge_map()
285 em->generation = max(em->generation, merge->generation); in try_merge_map()
286 set_bit(EXTENT_FLAG_MERGED, &em->flags); in try_merge_map()
292 * unpin_extent_cache - unpin an extent from the cache
309 write_lock(&tree->lock); in unpin_extent_cache()
312 WARN_ON(!em || em->start != start); in unpin_extent_cache()
317 em->generation = gen; in unpin_extent_cache()
318 clear_bit(EXTENT_FLAG_PINNED, &em->flags); in unpin_extent_cache()
319 em->mod_start = em->start; in unpin_extent_cache()
320 em->mod_len = em->len; in unpin_extent_cache()
322 if (test_bit(EXTENT_FLAG_FILLING, &em->flags)) { in unpin_extent_cache()
324 clear_bit(EXTENT_FLAG_FILLING, &em->flags); in unpin_extent_cache()
330 em->mod_start = em->start; in unpin_extent_cache()
331 em->mod_len = em->len; in unpin_extent_cache()
336 write_unlock(&tree->lock); in unpin_extent_cache()
343 lockdep_assert_held_write(&tree->lock); in clear_em_logging()
345 clear_bit(EXTENT_FLAG_LOGGING, &em->flags); in clear_em_logging()
354 refcount_inc(&em->refs); in setup_extent_mapping()
355 em->mod_start = em->start; in setup_extent_mapping()
356 em->mod_len = em->len; in setup_extent_mapping()
359 list_move(&em->list, &tree->modified_extents); in setup_extent_mapping()
366 struct map_lookup *map = em->map_lookup; in extent_map_device_set_bits()
367 u64 stripe_size = em->orig_block_len; in extent_map_device_set_bits()
370 for (i = 0; i < map->num_stripes; i++) { in extent_map_device_set_bits()
371 struct btrfs_io_stripe *stripe = &map->stripes[i]; in extent_map_device_set_bits()
372 struct btrfs_device *device = stripe->dev; in extent_map_device_set_bits()
374 set_extent_bits_nowait(&device->alloc_state, stripe->physical, in extent_map_device_set_bits()
375 stripe->physical + stripe_size - 1, bits); in extent_map_device_set_bits()
381 struct map_lookup *map = em->map_lookup; in extent_map_device_clear_bits()
382 u64 stripe_size = em->orig_block_len; in extent_map_device_clear_bits()
385 for (i = 0; i < map->num_stripes; i++) { in extent_map_device_clear_bits()
386 struct btrfs_io_stripe *stripe = &map->stripes[i]; in extent_map_device_clear_bits()
387 struct btrfs_device *device = stripe->dev; in extent_map_device_clear_bits()
389 __clear_extent_bit(&device->alloc_state, stripe->physical, in extent_map_device_clear_bits()
390 stripe->physical + stripe_size - 1, bits, in extent_map_device_clear_bits()
404 * existing mappings. The extent_map struct passed in will be inserted
413 lockdep_assert_held_write(&tree->lock); in add_extent_mapping()
415 ret = tree_insert(&tree->map, em); in add_extent_mapping()
420 if (test_bit(EXTENT_FLAG_FS_MAPPING, &em->flags)) { in add_extent_mapping()
437 rb_node = __tree_search(&tree->map.rb_root, start, &prev_or_next); in __lookup_extent_mapping()
447 if (strict && !(end > em->start && start < extent_map_end(em))) in __lookup_extent_mapping()
450 refcount_inc(&em->refs); in __lookup_extent_mapping()
455 * lookup_extent_mapping - lookup extent_map
472 * search_extent_mapping - find a nearby extent map
489 * remove_extent_mapping - removes an extent_map from the extent tree
498 lockdep_assert_held_write(&tree->lock); in remove_extent_mapping()
500 WARN_ON(test_bit(EXTENT_FLAG_PINNED, &em->flags)); in remove_extent_mapping()
501 rb_erase_cached(&em->rb_node, &tree->map); in remove_extent_mapping()
502 if (!test_bit(EXTENT_FLAG_LOGGING, &em->flags)) in remove_extent_mapping()
503 list_del_init(&em->list); in remove_extent_mapping()
504 if (test_bit(EXTENT_FLAG_FS_MAPPING, &em->flags)) in remove_extent_mapping()
506 RB_CLEAR_NODE(&em->rb_node); in remove_extent_mapping()
514 lockdep_assert_held_write(&tree->lock); in replace_extent_mapping()
516 WARN_ON(test_bit(EXTENT_FLAG_PINNED, &cur->flags)); in replace_extent_mapping()
518 if (!test_bit(EXTENT_FLAG_LOGGING, &cur->flags)) in replace_extent_mapping()
519 list_del_init(&cur->list); in replace_extent_mapping()
520 rb_replace_node_cached(&cur->rb_node, &new->rb_node, &tree->map); in replace_extent_mapping()
521 RB_CLEAR_NODE(&cur->rb_node); in replace_extent_mapping()
530 next = rb_next(&em->rb_node); in next_extent_map()
540 prev = rb_prev(&em->rb_node); in prev_extent_map()
547 * Helper for btrfs_get_extent. Given an existing extent in the tree,
548 * the existing extent is the nearest extent to map_start,
553 struct extent_map *existing, in merge_extent_mapping() argument
563 BUG_ON(map_start < em->start || map_start >= extent_map_end(em)); in merge_extent_mapping()
565 if (existing->start > map_start) { in merge_extent_mapping()
566 next = existing; in merge_extent_mapping()
569 prev = existing; in merge_extent_mapping()
573 start = prev ? extent_map_end(prev) : em->start; in merge_extent_mapping()
574 start = max_t(u64, start, em->start); in merge_extent_mapping()
575 end = next ? next->start : extent_map_end(em); in merge_extent_mapping()
577 start_diff = start - em->start; in merge_extent_mapping()
578 em->start = start; in merge_extent_mapping()
579 em->len = end - start; in merge_extent_mapping()
580 if (em->block_start < EXTENT_MAP_LAST_BYTE && in merge_extent_mapping()
581 !test_bit(EXTENT_FLAG_COMPRESSED, &em->flags)) { in merge_extent_mapping()
582 em->block_start += start_diff; in merge_extent_mapping()
583 em->block_len = em->len; in merge_extent_mapping()
601 * the -EEXIST by either:
602 * a) Returning the existing extent in @em_in if @start is within the
603 * existing em.
604 * b) Merge the existing extent with @em_in passed in.
606 * Return 0 on success, otherwise -EEXIST.
621 if (ret == -EEXIST) { in btrfs_add_extent_mapping()
622 struct extent_map *existing; in btrfs_add_extent_mapping() local
626 existing = search_extent_mapping(em_tree, start, len); in btrfs_add_extent_mapping()
628 trace_btrfs_handle_em_exist(fs_info, existing, em, start, len); in btrfs_add_extent_mapping()
631 * existing will always be non-NULL, since there must be in btrfs_add_extent_mapping()
632 * extent causing the -EEXIST. in btrfs_add_extent_mapping()
634 if (start >= existing->start && in btrfs_add_extent_mapping()
635 start < extent_map_end(existing)) { in btrfs_add_extent_mapping()
637 *em_in = existing; in btrfs_add_extent_mapping()
640 u64 orig_start = em->start; in btrfs_add_extent_mapping()
641 u64 orig_len = em->len; in btrfs_add_extent_mapping()
644 * The existing extent map is the one nearest to in btrfs_add_extent_mapping()
647 ret = merge_extent_mapping(em_tree, existing, in btrfs_add_extent_mapping()
653 "unexpected error %d: merge existing(start %llu len %llu) with em(start %llu len %llu)\n", in btrfs_add_extent_mapping()
654 ret, existing->start, existing->len, in btrfs_add_extent_mapping()
657 free_extent_map(existing); in btrfs_add_extent_mapping()
661 ASSERT(ret == 0 || ret == -EEXIST); in btrfs_add_extent_mapping()
672 write_lock(&tree->lock); in drop_all_extent_maps_fast()
673 while (!RB_EMPTY_ROOT(&tree->map.rb_root)) { in drop_all_extent_maps_fast()
677 node = rb_first_cached(&tree->map); in drop_all_extent_maps_fast()
679 clear_bit(EXTENT_FLAG_PINNED, &em->flags); in drop_all_extent_maps_fast()
680 clear_bit(EXTENT_FLAG_LOGGING, &em->flags); in drop_all_extent_maps_fast()
683 cond_resched_rwlock_write(&tree->lock); in drop_all_extent_maps_fast()
685 write_unlock(&tree->lock); in drop_all_extent_maps_fast()
708 struct extent_map_tree *em_tree = &inode->extent_tree; in btrfs_drop_extent_map_range()
709 u64 len = end - start + 1; in btrfs_drop_extent_map_range()
712 if (end == (u64)-1) { in btrfs_drop_extent_map_range()
717 len = (u64)-1; in btrfs_drop_extent_map_range()
734 write_lock(&em_tree->lock); in btrfs_drop_extent_map_range()
749 if (next_em->start < end) in btrfs_drop_extent_map_range()
750 refcount_inc(&next_em->refs); in btrfs_drop_extent_map_range()
756 if (skip_pinned && test_bit(EXTENT_FLAG_PINNED, &em->flags)) { in btrfs_drop_extent_map_range()
758 if (end != (u64)-1) in btrfs_drop_extent_map_range()
759 len = start + len - em_end; in btrfs_drop_extent_map_range()
763 clear_bit(EXTENT_FLAG_PINNED, &em->flags); in btrfs_drop_extent_map_range()
765 modified = !list_empty(&em->list); in btrfs_drop_extent_map_range()
771 if (em->start >= start && em_end <= end) in btrfs_drop_extent_map_range()
774 flags = em->flags; in btrfs_drop_extent_map_range()
775 gen = em->generation; in btrfs_drop_extent_map_range()
776 compressed = test_bit(EXTENT_FLAG_COMPRESSED, &em->flags); in btrfs_drop_extent_map_range()
778 if (em->start < start) { in btrfs_drop_extent_map_range()
785 split->start = em->start; in btrfs_drop_extent_map_range()
786 split->len = start - em->start; in btrfs_drop_extent_map_range()
788 if (em->block_start < EXTENT_MAP_LAST_BYTE) { in btrfs_drop_extent_map_range()
789 split->orig_start = em->orig_start; in btrfs_drop_extent_map_range()
790 split->block_start = em->block_start; in btrfs_drop_extent_map_range()
793 split->block_len = em->block_len; in btrfs_drop_extent_map_range()
795 split->block_len = split->len; in btrfs_drop_extent_map_range()
796 split->orig_block_len = max(split->block_len, in btrfs_drop_extent_map_range()
797 em->orig_block_len); in btrfs_drop_extent_map_range()
798 split->ram_bytes = em->ram_bytes; in btrfs_drop_extent_map_range()
800 split->orig_start = split->start; in btrfs_drop_extent_map_range()
801 split->block_len = 0; in btrfs_drop_extent_map_range()
802 split->block_start = em->block_start; in btrfs_drop_extent_map_range()
803 split->orig_block_len = 0; in btrfs_drop_extent_map_range()
804 split->ram_bytes = split->len; in btrfs_drop_extent_map_range()
807 split->generation = gen; in btrfs_drop_extent_map_range()
808 split->flags = flags; in btrfs_drop_extent_map_range()
809 split->compress_type = em->compress_type; in btrfs_drop_extent_map_range()
822 split->start = start + len; in btrfs_drop_extent_map_range()
823 split->len = em_end - (start + len); in btrfs_drop_extent_map_range()
824 split->block_start = em->block_start; in btrfs_drop_extent_map_range()
825 split->flags = flags; in btrfs_drop_extent_map_range()
826 split->compress_type = em->compress_type; in btrfs_drop_extent_map_range()
827 split->generation = gen; in btrfs_drop_extent_map_range()
829 if (em->block_start < EXTENT_MAP_LAST_BYTE) { in btrfs_drop_extent_map_range()
830 split->orig_block_len = max(em->block_len, in btrfs_drop_extent_map_range()
831 em->orig_block_len); in btrfs_drop_extent_map_range()
833 split->ram_bytes = em->ram_bytes; in btrfs_drop_extent_map_range()
835 split->block_len = em->block_len; in btrfs_drop_extent_map_range()
836 split->orig_start = em->orig_start; in btrfs_drop_extent_map_range()
838 const u64 diff = start + len - em->start; in btrfs_drop_extent_map_range()
840 split->block_len = split->len; in btrfs_drop_extent_map_range()
841 split->block_start += diff; in btrfs_drop_extent_map_range()
842 split->orig_start = em->orig_start; in btrfs_drop_extent_map_range()
845 split->ram_bytes = split->len; in btrfs_drop_extent_map_range()
846 split->orig_start = split->start; in btrfs_drop_extent_map_range()
847 split->block_len = 0; in btrfs_drop_extent_map_range()
848 split->orig_block_len = 0; in btrfs_drop_extent_map_range()
881 * extent map - this is fine since if anyone needs it to in btrfs_drop_extent_map_range()
889 if ((em->start < start || em_end > end) && modified) { in btrfs_drop_extent_map_range()
908 write_unlock(&em_tree->lock); in btrfs_drop_extent_map_range()
931 const u64 end = new_em->start + new_em->len - 1; in btrfs_replace_extent_map_range()
932 struct extent_map_tree *tree = &inode->extent_tree; in btrfs_replace_extent_map_range()
939 * tree, but getting -EEXIST when adding the new extent map can still in btrfs_replace_extent_map_range()
941 * this is due to two tasks operating on different parts of the extent. in btrfs_replace_extent_map_range()
946 btrfs_drop_extent_map_range(inode, new_em->start, end, false); in btrfs_replace_extent_map_range()
947 write_lock(&tree->lock); in btrfs_replace_extent_map_range()
949 write_unlock(&tree->lock); in btrfs_replace_extent_map_range()
950 } while (ret == -EEXIST); in btrfs_replace_extent_map_range()