Lines Matching +full:existing +full:- +full:parts
1 // SPDX-License-Identifier: GPL-2.0
22 return -ENOMEM; in extent_map_init()
37 tree->map = RB_ROOT_CACHED; in extent_map_tree_init()
38 INIT_LIST_HEAD(&tree->modified_extents); in extent_map_tree_init()
39 rwlock_init(&tree->lock); in extent_map_tree_init()
52 RB_CLEAR_NODE(&em->rb_node); in alloc_extent_map()
53 refcount_set(&em->refs, 1); in alloc_extent_map()
54 INIT_LIST_HEAD(&em->list); in alloc_extent_map()
66 if (refcount_dec_and_test(&em->refs)) { in free_extent_map()
68 WARN_ON(!list_empty(&em->list)); in free_extent_map()
77 return (u64)-1; in range_end()
83 struct rb_node **p = &root->rb_root.rb_node; in tree_insert()
87 u64 end = range_end(em->start, em->len); in tree_insert()
94 if (em->start < entry->start) { in tree_insert()
95 p = &(*p)->rb_left; in tree_insert()
96 } else if (em->start >= extent_map_end(entry)) { in tree_insert()
97 p = &(*p)->rb_right; in tree_insert()
100 return -EEXIST; in tree_insert()
105 while (parent && em->start >= extent_map_end(entry)) { in tree_insert()
110 if (end > entry->start && em->start < extent_map_end(entry)) in tree_insert()
111 return -EEXIST; in tree_insert()
115 while (parent && em->start < entry->start) { in tree_insert()
120 if (end > entry->start && em->start < extent_map_end(entry)) in tree_insert()
121 return -EEXIST; in tree_insert()
123 rb_link_node(&em->rb_node, orig_parent, p); in tree_insert()
124 rb_insert_color_cached(&em->rb_node, root, leftmost); in tree_insert()
135 struct rb_node *n = root->rb_node; in __tree_search()
148 if (offset < entry->start) in __tree_search()
149 n = n->rb_left; in __tree_search()
151 n = n->rb_right; in __tree_search()
173 while (prev && offset < prev_entry->start) { in __tree_search()
184 if (em->block_start + em->block_len < em->block_start) in extent_map_block_end()
185 return (u64)-1; in extent_map_block_end()
186 return em->block_start + em->block_len; in extent_map_block_end()
191 if (em->flags & EXTENT_FLAG_PINNED) in can_merge_extent_map()
198 if (em->flags & EXTENT_FLAG_LOGGING) in can_merge_extent_map()
206 if (!list_empty(&em->list)) in can_merge_extent_map()
215 if (extent_map_end(prev) != next->start) in mergeable_maps()
218 if (prev->flags != next->flags) in mergeable_maps()
221 if (next->block_start < EXTENT_MAP_LAST_BYTE - 1) in mergeable_maps()
222 return next->block_start == extent_map_block_end(prev); in mergeable_maps()
225 return next->block_start == prev->block_start; in mergeable_maps()
241 if (refcount_read(&em->refs) > 2) in try_merge_map()
247 if (em->start != 0) { in try_merge_map()
248 rb = rb_prev(&em->rb_node); in try_merge_map()
252 em->start = merge->start; in try_merge_map()
253 em->orig_start = merge->orig_start; in try_merge_map()
254 em->len += merge->len; in try_merge_map()
255 em->block_len += merge->block_len; in try_merge_map()
256 em->block_start = merge->block_start; in try_merge_map()
257 em->mod_len = (em->mod_len + em->mod_start) - merge->mod_start; in try_merge_map()
258 em->mod_start = merge->mod_start; in try_merge_map()
259 em->generation = max(em->generation, merge->generation); in try_merge_map()
260 em->flags |= EXTENT_FLAG_MERGED; in try_merge_map()
262 rb_erase_cached(&merge->rb_node, &tree->map); in try_merge_map()
263 RB_CLEAR_NODE(&merge->rb_node); in try_merge_map()
268 rb = rb_next(&em->rb_node); in try_merge_map()
272 em->len += merge->len; in try_merge_map()
273 em->block_len += merge->block_len; in try_merge_map()
274 rb_erase_cached(&merge->rb_node, &tree->map); in try_merge_map()
275 RB_CLEAR_NODE(&merge->rb_node); in try_merge_map()
276 em->mod_len = (merge->mod_start + merge->mod_len) - em->mod_start; in try_merge_map()
277 em->generation = max(em->generation, merge->generation); in try_merge_map()
278 em->flags |= EXTENT_FLAG_MERGED; in try_merge_map()
297 struct btrfs_fs_info *fs_info = inode->root->fs_info; in unpin_extent_cache()
298 struct extent_map_tree *tree = &inode->extent_tree; in unpin_extent_cache()
303 write_lock(&tree->lock); in unpin_extent_cache()
309 btrfs_ino(inode), btrfs_root_id(inode->root), in unpin_extent_cache()
314 if (WARN_ON(em->start != start)) in unpin_extent_cache()
317 btrfs_ino(inode), btrfs_root_id(inode->root), in unpin_extent_cache()
318 em->start, start, len, gen); in unpin_extent_cache()
320 em->generation = gen; in unpin_extent_cache()
321 em->flags &= ~EXTENT_FLAG_PINNED; in unpin_extent_cache()
322 em->mod_start = em->start; in unpin_extent_cache()
323 em->mod_len = em->len; in unpin_extent_cache()
325 if (em->flags & EXTENT_FLAG_FILLING) { in unpin_extent_cache()
327 em->flags &= ~EXTENT_FLAG_FILLING; in unpin_extent_cache()
333 em->mod_start = em->start; in unpin_extent_cache()
334 em->mod_len = em->len; in unpin_extent_cache()
339 write_unlock(&tree->lock); in unpin_extent_cache()
346 lockdep_assert_held_write(&tree->lock); in clear_em_logging()
348 em->flags &= ~EXTENT_FLAG_LOGGING; in clear_em_logging()
357 refcount_inc(&em->refs); in setup_extent_mapping()
358 em->mod_start = em->start; in setup_extent_mapping()
359 em->mod_len = em->len; in setup_extent_mapping()
361 ASSERT(list_empty(&em->list)); in setup_extent_mapping()
364 list_add(&em->list, &tree->modified_extents); in setup_extent_mapping()
378 * existing mappings. The extent_map struct passed in will be inserted
387 lockdep_assert_held_write(&tree->lock); in add_extent_mapping()
389 ret = tree_insert(&tree->map, em); in add_extent_mapping()
407 rb_node = __tree_search(&tree->map.rb_root, start, &prev_or_next); in __lookup_extent_mapping()
417 if (strict && !(end > em->start && start < extent_map_end(em))) in __lookup_extent_mapping()
420 refcount_inc(&em->refs); in __lookup_extent_mapping()
471 lockdep_assert_held_write(&tree->lock); in remove_extent_mapping()
473 WARN_ON(em->flags & EXTENT_FLAG_PINNED); in remove_extent_mapping()
474 rb_erase_cached(&em->rb_node, &tree->map); in remove_extent_mapping()
475 if (!(em->flags & EXTENT_FLAG_LOGGING)) in remove_extent_mapping()
476 list_del_init(&em->list); in remove_extent_mapping()
477 RB_CLEAR_NODE(&em->rb_node); in remove_extent_mapping()
485 lockdep_assert_held_write(&tree->lock); in replace_extent_mapping()
487 WARN_ON(cur->flags & EXTENT_FLAG_PINNED); in replace_extent_mapping()
489 if (!(cur->flags & EXTENT_FLAG_LOGGING)) in replace_extent_mapping()
490 list_del_init(&cur->list); in replace_extent_mapping()
491 rb_replace_node_cached(&cur->rb_node, &new->rb_node, &tree->map); in replace_extent_mapping()
492 RB_CLEAR_NODE(&cur->rb_node); in replace_extent_mapping()
501 next = rb_next(&em->rb_node); in next_extent_map()
511 prev = rb_prev(&em->rb_node); in prev_extent_map()
518 * Helper for btrfs_get_extent. Given an existing extent in the tree,
519 * the existing extent is the nearest extent to map_start,
524 struct extent_map *existing, in merge_extent_mapping() argument
534 BUG_ON(map_start < em->start || map_start >= extent_map_end(em)); in merge_extent_mapping()
536 if (existing->start > map_start) { in merge_extent_mapping()
537 next = existing; in merge_extent_mapping()
540 prev = existing; in merge_extent_mapping()
544 start = prev ? extent_map_end(prev) : em->start; in merge_extent_mapping()
545 start = max_t(u64, start, em->start); in merge_extent_mapping()
546 end = next ? next->start : extent_map_end(em); in merge_extent_mapping()
548 start_diff = start - em->start; in merge_extent_mapping()
549 em->start = start; in merge_extent_mapping()
550 em->len = end - start; in merge_extent_mapping()
551 if (em->block_start < EXTENT_MAP_LAST_BYTE && in merge_extent_mapping()
553 em->block_start += start_diff; in merge_extent_mapping()
554 em->block_len = em->len; in merge_extent_mapping()
572 * the -EEXIST by either:
573 * a) Returning the existing extent in @em_in if @start is within the
574 * existing em.
575 * b) Merge the existing extent with @em_in passed in.
577 * Return 0 on success, otherwise -EEXIST.
588 * Tree-checker should have rejected any inline extent with non-zero in btrfs_add_extent_mapping()
591 if (em->block_start == EXTENT_MAP_INLINE) in btrfs_add_extent_mapping()
592 ASSERT(em->start == 0); in btrfs_add_extent_mapping()
599 if (ret == -EEXIST) { in btrfs_add_extent_mapping()
600 struct extent_map *existing; in btrfs_add_extent_mapping() local
602 existing = search_extent_mapping(em_tree, start, len); in btrfs_add_extent_mapping()
604 trace_btrfs_handle_em_exist(fs_info, existing, em, start, len); in btrfs_add_extent_mapping()
607 * existing will always be non-NULL, since there must be in btrfs_add_extent_mapping()
608 * extent causing the -EEXIST. in btrfs_add_extent_mapping()
610 if (start >= existing->start && in btrfs_add_extent_mapping()
611 start < extent_map_end(existing)) { in btrfs_add_extent_mapping()
613 *em_in = existing; in btrfs_add_extent_mapping()
616 u64 orig_start = em->start; in btrfs_add_extent_mapping()
617 u64 orig_len = em->len; in btrfs_add_extent_mapping()
620 * The existing extent map is the one nearest to in btrfs_add_extent_mapping()
623 ret = merge_extent_mapping(em_tree, existing, in btrfs_add_extent_mapping()
629 "unexpected error %d: merge existing(start %llu len %llu) with em(start %llu len %llu)\n", in btrfs_add_extent_mapping()
630 ret, existing->start, existing->len, in btrfs_add_extent_mapping()
633 free_extent_map(existing); in btrfs_add_extent_mapping()
637 ASSERT(ret == 0 || ret == -EEXIST); in btrfs_add_extent_mapping()
648 write_lock(&tree->lock); in drop_all_extent_maps_fast()
649 while (!RB_EMPTY_ROOT(&tree->map.rb_root)) { in drop_all_extent_maps_fast()
653 node = rb_first_cached(&tree->map); in drop_all_extent_maps_fast()
655 em->flags &= ~(EXTENT_FLAG_PINNED | EXTENT_FLAG_LOGGING); in drop_all_extent_maps_fast()
658 cond_resched_rwlock_write(&tree->lock); in drop_all_extent_maps_fast()
660 write_unlock(&tree->lock); in drop_all_extent_maps_fast()
683 struct extent_map_tree *em_tree = &inode->extent_tree; in btrfs_drop_extent_map_range()
684 u64 len = end - start + 1; in btrfs_drop_extent_map_range()
687 if (end == (u64)-1) { in btrfs_drop_extent_map_range()
692 len = (u64)-1; in btrfs_drop_extent_map_range()
709 write_lock(&em_tree->lock); in btrfs_drop_extent_map_range()
724 if (next_em->start < end) in btrfs_drop_extent_map_range()
725 refcount_inc(&next_em->refs); in btrfs_drop_extent_map_range()
731 if (skip_pinned && (em->flags & EXTENT_FLAG_PINNED)) { in btrfs_drop_extent_map_range()
736 flags = em->flags; in btrfs_drop_extent_map_range()
742 em->flags &= ~(EXTENT_FLAG_PINNED | EXTENT_FLAG_LOGGING); in btrfs_drop_extent_map_range()
743 modified = !list_empty(&em->list); in btrfs_drop_extent_map_range()
749 if (em->start >= start && em_end <= end) in btrfs_drop_extent_map_range()
752 gen = em->generation; in btrfs_drop_extent_map_range()
755 if (em->start < start) { in btrfs_drop_extent_map_range()
762 split->start = em->start; in btrfs_drop_extent_map_range()
763 split->len = start - em->start; in btrfs_drop_extent_map_range()
765 if (em->block_start < EXTENT_MAP_LAST_BYTE) { in btrfs_drop_extent_map_range()
766 split->orig_start = em->orig_start; in btrfs_drop_extent_map_range()
767 split->block_start = em->block_start; in btrfs_drop_extent_map_range()
770 split->block_len = em->block_len; in btrfs_drop_extent_map_range()
772 split->block_len = split->len; in btrfs_drop_extent_map_range()
773 split->orig_block_len = max(split->block_len, in btrfs_drop_extent_map_range()
774 em->orig_block_len); in btrfs_drop_extent_map_range()
775 split->ram_bytes = em->ram_bytes; in btrfs_drop_extent_map_range()
777 split->orig_start = split->start; in btrfs_drop_extent_map_range()
778 split->block_len = 0; in btrfs_drop_extent_map_range()
779 split->block_start = em->block_start; in btrfs_drop_extent_map_range()
780 split->orig_block_len = 0; in btrfs_drop_extent_map_range()
781 split->ram_bytes = split->len; in btrfs_drop_extent_map_range()
784 split->generation = gen; in btrfs_drop_extent_map_range()
785 split->flags = flags; in btrfs_drop_extent_map_range()
798 split->start = end; in btrfs_drop_extent_map_range()
799 split->len = em_end - end; in btrfs_drop_extent_map_range()
800 split->block_start = em->block_start; in btrfs_drop_extent_map_range()
801 split->flags = flags; in btrfs_drop_extent_map_range()
802 split->generation = gen; in btrfs_drop_extent_map_range()
804 if (em->block_start < EXTENT_MAP_LAST_BYTE) { in btrfs_drop_extent_map_range()
805 split->orig_block_len = max(em->block_len, in btrfs_drop_extent_map_range()
806 em->orig_block_len); in btrfs_drop_extent_map_range()
808 split->ram_bytes = em->ram_bytes; in btrfs_drop_extent_map_range()
810 split->block_len = em->block_len; in btrfs_drop_extent_map_range()
811 split->orig_start = em->orig_start; in btrfs_drop_extent_map_range()
813 const u64 diff = start + len - em->start; in btrfs_drop_extent_map_range()
815 split->block_len = split->len; in btrfs_drop_extent_map_range()
816 split->block_start += diff; in btrfs_drop_extent_map_range()
817 split->orig_start = em->orig_start; in btrfs_drop_extent_map_range()
820 split->ram_bytes = split->len; in btrfs_drop_extent_map_range()
821 split->orig_start = split->start; in btrfs_drop_extent_map_range()
822 split->block_len = 0; in btrfs_drop_extent_map_range()
823 split->orig_block_len = 0; in btrfs_drop_extent_map_range()
856 * extent map - this is fine since if anyone needs it to in btrfs_drop_extent_map_range()
864 if ((em->start < start || em_end > end) && modified) { in btrfs_drop_extent_map_range()
883 write_unlock(&em_tree->lock); in btrfs_drop_extent_map_range()
906 const u64 end = new_em->start + new_em->len - 1; in btrfs_replace_extent_map_range()
907 struct extent_map_tree *tree = &inode->extent_tree; in btrfs_replace_extent_map_range()
914 * tree, but getting -EEXIST when adding the new extent map can still in btrfs_replace_extent_map_range()
916 * this is due to two tasks operating on different parts of the extent. in btrfs_replace_extent_map_range()
921 btrfs_drop_extent_map_range(inode, new_em->start, end, false); in btrfs_replace_extent_map_range()
922 write_lock(&tree->lock); in btrfs_replace_extent_map_range()
924 write_unlock(&tree->lock); in btrfs_replace_extent_map_range()
925 } while (ret == -EEXIST); in btrfs_replace_extent_map_range()
939 struct extent_map_tree *em_tree = &inode->extent_tree; in split_extent_map()
951 return -ENOMEM; in split_extent_map()
954 ret = -ENOMEM; in split_extent_map()
958 lock_extent(&inode->io_tree, start, start + len - 1, NULL); in split_extent_map()
959 write_lock(&em_tree->lock); in split_extent_map()
962 ret = -EIO; in split_extent_map()
966 ASSERT(em->len == len); in split_extent_map()
968 ASSERT(em->block_start < EXTENT_MAP_LAST_BYTE); in split_extent_map()
969 ASSERT(em->flags & EXTENT_FLAG_PINNED); in split_extent_map()
970 ASSERT(!(em->flags & EXTENT_FLAG_LOGGING)); in split_extent_map()
971 ASSERT(!list_empty(&em->list)); in split_extent_map()
973 flags = em->flags; in split_extent_map()
974 em->flags &= ~EXTENT_FLAG_PINNED; in split_extent_map()
976 /* First, replace the em with a new extent_map starting from * em->start */ in split_extent_map()
977 split_pre->start = em->start; in split_extent_map()
978 split_pre->len = pre; in split_extent_map()
979 split_pre->orig_start = split_pre->start; in split_extent_map()
980 split_pre->block_start = new_logical; in split_extent_map()
981 split_pre->block_len = split_pre->len; in split_extent_map()
982 split_pre->orig_block_len = split_pre->block_len; in split_extent_map()
983 split_pre->ram_bytes = split_pre->len; in split_extent_map()
984 split_pre->flags = flags; in split_extent_map()
985 split_pre->generation = em->generation; in split_extent_map()
991 * [em->start, em->start + pre] in split_extent_map()
995 split_mid->start = em->start + pre; in split_extent_map()
996 split_mid->len = em->len - pre; in split_extent_map()
997 split_mid->orig_start = split_mid->start; in split_extent_map()
998 split_mid->block_start = em->block_start + pre; in split_extent_map()
999 split_mid->block_len = split_mid->len; in split_extent_map()
1000 split_mid->orig_block_len = split_mid->block_len; in split_extent_map()
1001 split_mid->ram_bytes = split_mid->len; in split_extent_map()
1002 split_mid->flags = flags; in split_extent_map()
1003 split_mid->generation = em->generation; in split_extent_map()
1012 write_unlock(&em_tree->lock); in split_extent_map()
1013 unlock_extent(&inode->io_tree, start, start + len - 1, NULL); in split_extent_map()