Lines Matching +full:first +full:- +full:generation
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 em->compress_type = BTRFS_COMPRESS_NONE; in alloc_extent_map()
54 refcount_set(&em->refs, 1); in alloc_extent_map()
55 INIT_LIST_HEAD(&em->list); in alloc_extent_map()
67 if (refcount_dec_and_test(&em->refs)) { in free_extent_map()
69 WARN_ON(!list_empty(&em->list)); in free_extent_map()
70 if (test_bit(EXTENT_FLAG_FS_MAPPING, &em->flags)) in free_extent_map()
71 kfree(em->map_lookup); in free_extent_map()
80 return (u64)-1; in range_end()
86 struct rb_node **p = &root->rb_root.rb_node; in tree_insert()
90 u64 end = range_end(em->start, em->len); in tree_insert()
97 if (em->start < entry->start) { in tree_insert()
98 p = &(*p)->rb_left; in tree_insert()
99 } else if (em->start >= extent_map_end(entry)) { in tree_insert()
100 p = &(*p)->rb_right; in tree_insert()
103 return -EEXIST; in tree_insert()
108 while (parent && em->start >= extent_map_end(entry)) { in tree_insert()
113 if (end > entry->start && em->start < extent_map_end(entry)) in tree_insert()
114 return -EEXIST; in tree_insert()
118 while (parent && em->start < entry->start) { in tree_insert()
123 if (end > entry->start && em->start < extent_map_end(entry)) in tree_insert()
124 return -EEXIST; in tree_insert()
126 rb_link_node(&em->rb_node, orig_parent, p); in tree_insert()
127 rb_insert_color_cached(&em->rb_node, root, leftmost); in tree_insert()
138 struct rb_node *n = root->rb_node; in __tree_search()
151 if (offset < entry->start) in __tree_search()
152 n = n->rb_left; in __tree_search()
154 n = n->rb_right; in __tree_search()
176 while (prev && offset < prev_entry->start) { in __tree_search()
188 if (test_bit(EXTENT_FLAG_PINNED, &prev->flags)) in mergable_maps()
195 if (test_bit(EXTENT_FLAG_COMPRESSED, &prev->flags)) in mergable_maps()
198 if (test_bit(EXTENT_FLAG_LOGGING, &prev->flags) || in mergable_maps()
199 test_bit(EXTENT_FLAG_LOGGING, &next->flags)) in mergable_maps()
207 if (!list_empty(&prev->list) || !list_empty(&next->list)) in mergable_maps()
210 ASSERT(next->block_start != EXTENT_MAP_DELALLOC && in mergable_maps()
211 prev->block_start != EXTENT_MAP_DELALLOC); in mergable_maps()
213 if (prev->map_lookup || next->map_lookup) in mergable_maps()
214 ASSERT(test_bit(EXTENT_FLAG_FS_MAPPING, &prev->flags) && in mergable_maps()
215 test_bit(EXTENT_FLAG_FS_MAPPING, &next->flags)); in mergable_maps()
217 if (extent_map_end(prev) == next->start && in mergable_maps()
218 prev->flags == next->flags && in mergable_maps()
219 prev->map_lookup == next->map_lookup && in mergable_maps()
220 ((next->block_start == EXTENT_MAP_HOLE && in mergable_maps()
221 prev->block_start == EXTENT_MAP_HOLE) || in mergable_maps()
222 (next->block_start == EXTENT_MAP_INLINE && in mergable_maps()
223 prev->block_start == EXTENT_MAP_INLINE) || in mergable_maps()
224 (next->block_start < EXTENT_MAP_LAST_BYTE - 1 && in mergable_maps()
225 next->block_start == extent_map_block_end(prev)))) { in mergable_maps()
244 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 set_bit(EXTENT_FLAG_MERGED, &em->flags); 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 set_bit(EXTENT_FLAG_MERGED, &em->flags); in try_merge_map()
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
302 write_lock(&tree->lock); in unpin_extent_cache()
305 WARN_ON(!em || em->start != start); in unpin_extent_cache()
310 em->generation = gen; in unpin_extent_cache()
311 clear_bit(EXTENT_FLAG_PINNED, &em->flags); in unpin_extent_cache()
312 em->mod_start = em->start; in unpin_extent_cache()
313 em->mod_len = em->len; in unpin_extent_cache()
315 if (test_bit(EXTENT_FLAG_FILLING, &em->flags)) { in unpin_extent_cache()
317 clear_bit(EXTENT_FLAG_FILLING, &em->flags); in unpin_extent_cache()
323 em->mod_start = em->start; in unpin_extent_cache()
324 em->mod_len = em->len; in unpin_extent_cache()
329 write_unlock(&tree->lock); in unpin_extent_cache()
336 lockdep_assert_held_write(&tree->lock); in clear_em_logging()
338 clear_bit(EXTENT_FLAG_LOGGING, &em->flags); in clear_em_logging()
347 refcount_inc(&em->refs); in setup_extent_mapping()
348 em->mod_start = em->start; in setup_extent_mapping()
349 em->mod_len = em->len; in setup_extent_mapping()
352 list_move(&em->list, &tree->modified_extents); in setup_extent_mapping()
359 struct map_lookup *map = em->map_lookup; in extent_map_device_set_bits()
360 u64 stripe_size = em->orig_block_len; in extent_map_device_set_bits()
363 for (i = 0; i < map->num_stripes; i++) { in extent_map_device_set_bits()
364 struct btrfs_io_stripe *stripe = &map->stripes[i]; in extent_map_device_set_bits()
365 struct btrfs_device *device = stripe->dev; in extent_map_device_set_bits()
367 set_extent_bit(&device->alloc_state, stripe->physical, in extent_map_device_set_bits()
368 stripe->physical + stripe_size - 1, in extent_map_device_set_bits()
375 struct map_lookup *map = em->map_lookup; in extent_map_device_clear_bits()
376 u64 stripe_size = em->orig_block_len; in extent_map_device_clear_bits()
379 for (i = 0; i < map->num_stripes; i++) { in extent_map_device_clear_bits()
380 struct btrfs_io_stripe *stripe = &map->stripes[i]; in extent_map_device_clear_bits()
381 struct btrfs_device *device = stripe->dev; in extent_map_device_clear_bits()
383 __clear_extent_bit(&device->alloc_state, stripe->physical, in extent_map_device_clear_bits()
384 stripe->physical + stripe_size - 1, in extent_map_device_clear_bits()
408 lockdep_assert_held_write(&tree->lock); in add_extent_mapping()
410 ret = tree_insert(&tree->map, em); in add_extent_mapping()
415 if (test_bit(EXTENT_FLAG_FS_MAPPING, &em->flags)) { in add_extent_mapping()
432 rb_node = __tree_search(&tree->map.rb_root, start, &prev_or_next); in __lookup_extent_mapping()
442 if (strict && !(end > em->start && start < extent_map_end(em))) in __lookup_extent_mapping()
445 refcount_inc(&em->refs); in __lookup_extent_mapping()
456 * Find and return the first extent_map struct in @tree that intersects the
474 * Find and return the first extent_map struct in @tree that intersects the
496 lockdep_assert_held_write(&tree->lock); in remove_extent_mapping()
498 WARN_ON(test_bit(EXTENT_FLAG_PINNED, &em->flags)); in remove_extent_mapping()
499 rb_erase_cached(&em->rb_node, &tree->map); in remove_extent_mapping()
500 if (!test_bit(EXTENT_FLAG_LOGGING, &em->flags)) in remove_extent_mapping()
501 list_del_init(&em->list); in remove_extent_mapping()
502 if (test_bit(EXTENT_FLAG_FS_MAPPING, &em->flags)) in remove_extent_mapping()
504 RB_CLEAR_NODE(&em->rb_node); in remove_extent_mapping()
512 lockdep_assert_held_write(&tree->lock); in replace_extent_mapping()
514 WARN_ON(test_bit(EXTENT_FLAG_PINNED, &cur->flags)); in replace_extent_mapping()
516 if (!test_bit(EXTENT_FLAG_LOGGING, &cur->flags)) in replace_extent_mapping()
517 list_del_init(&cur->list); in replace_extent_mapping()
518 rb_replace_node_cached(&cur->rb_node, &new->rb_node, &tree->map); in replace_extent_mapping()
519 RB_CLEAR_NODE(&cur->rb_node); in replace_extent_mapping()
528 next = rb_next(&em->rb_node); in next_extent_map()
538 prev = rb_prev(&em->rb_node); in prev_extent_map()
561 BUG_ON(map_start < em->start || map_start >= extent_map_end(em)); in merge_extent_mapping()
563 if (existing->start > map_start) { in merge_extent_mapping()
571 start = prev ? extent_map_end(prev) : em->start; in merge_extent_mapping()
572 start = max_t(u64, start, em->start); in merge_extent_mapping()
573 end = next ? next->start : extent_map_end(em); in merge_extent_mapping()
575 start_diff = start - em->start; in merge_extent_mapping()
576 em->start = start; in merge_extent_mapping()
577 em->len = end - start; in merge_extent_mapping()
578 if (em->block_start < EXTENT_MAP_LAST_BYTE && in merge_extent_mapping()
579 !test_bit(EXTENT_FLAG_COMPRESSED, &em->flags)) { in merge_extent_mapping()
580 em->block_start += start_diff; in merge_extent_mapping()
581 em->block_len = em->len; in merge_extent_mapping()
599 * the -EEXIST by either:
604 * Return 0 on success, otherwise -EEXIST.
615 * Tree-checker should have rejected any inline extent with non-zero in btrfs_add_extent_mapping()
618 if (em->block_start == EXTENT_MAP_INLINE) in btrfs_add_extent_mapping()
619 ASSERT(em->start == 0); in btrfs_add_extent_mapping()
626 if (ret == -EEXIST) { in btrfs_add_extent_mapping()
636 * existing will always be non-NULL, since there must be in btrfs_add_extent_mapping()
637 * extent causing the -EEXIST. in btrfs_add_extent_mapping()
639 if (start >= existing->start && in btrfs_add_extent_mapping()
645 u64 orig_start = em->start; in btrfs_add_extent_mapping()
646 u64 orig_len = em->len; in btrfs_add_extent_mapping()
659 ret, existing->start, existing->len, in btrfs_add_extent_mapping()
666 ASSERT(ret == 0 || ret == -EEXIST); in btrfs_add_extent_mapping()
672 * if needed. This avoids searching the tree, from the root down to the first
677 write_lock(&tree->lock); in drop_all_extent_maps_fast()
678 while (!RB_EMPTY_ROOT(&tree->map.rb_root)) { in drop_all_extent_maps_fast()
682 node = rb_first_cached(&tree->map); in drop_all_extent_maps_fast()
684 clear_bit(EXTENT_FLAG_PINNED, &em->flags); in drop_all_extent_maps_fast()
685 clear_bit(EXTENT_FLAG_LOGGING, &em->flags); in drop_all_extent_maps_fast()
688 cond_resched_rwlock_write(&tree->lock); in drop_all_extent_maps_fast()
690 write_unlock(&tree->lock); in drop_all_extent_maps_fast()
713 struct extent_map_tree *em_tree = &inode->extent_tree; in btrfs_drop_extent_map_range()
714 u64 len = end - start + 1; in btrfs_drop_extent_map_range()
717 if (end == (u64)-1) { in btrfs_drop_extent_map_range()
722 len = (u64)-1; in btrfs_drop_extent_map_range()
731 * the worst case, where the first extent map that intersects our range in btrfs_drop_extent_map_range()
739 write_lock(&em_tree->lock); in btrfs_drop_extent_map_range()
754 if (next_em->start < end) in btrfs_drop_extent_map_range()
755 refcount_inc(&next_em->refs); in btrfs_drop_extent_map_range()
761 if (skip_pinned && test_bit(EXTENT_FLAG_PINNED, &em->flags)) { in btrfs_drop_extent_map_range()
766 flags = em->flags; in btrfs_drop_extent_map_range()
767 clear_bit(EXTENT_FLAG_PINNED, &em->flags); in btrfs_drop_extent_map_range()
774 modified = !list_empty(&em->list); in btrfs_drop_extent_map_range()
780 if (em->start >= start && em_end <= end) in btrfs_drop_extent_map_range()
783 gen = em->generation; in btrfs_drop_extent_map_range()
784 compressed = test_bit(EXTENT_FLAG_COMPRESSED, &em->flags); in btrfs_drop_extent_map_range()
786 if (em->start < start) { in btrfs_drop_extent_map_range()
793 split->start = em->start; in btrfs_drop_extent_map_range()
794 split->len = start - em->start; in btrfs_drop_extent_map_range()
796 if (em->block_start < EXTENT_MAP_LAST_BYTE) { in btrfs_drop_extent_map_range()
797 split->orig_start = em->orig_start; in btrfs_drop_extent_map_range()
798 split->block_start = em->block_start; in btrfs_drop_extent_map_range()
801 split->block_len = em->block_len; in btrfs_drop_extent_map_range()
803 split->block_len = split->len; in btrfs_drop_extent_map_range()
804 split->orig_block_len = max(split->block_len, in btrfs_drop_extent_map_range()
805 em->orig_block_len); in btrfs_drop_extent_map_range()
806 split->ram_bytes = em->ram_bytes; in btrfs_drop_extent_map_range()
808 split->orig_start = split->start; in btrfs_drop_extent_map_range()
809 split->block_len = 0; in btrfs_drop_extent_map_range()
810 split->block_start = em->block_start; in btrfs_drop_extent_map_range()
811 split->orig_block_len = 0; in btrfs_drop_extent_map_range()
812 split->ram_bytes = split->len; in btrfs_drop_extent_map_range()
815 split->generation = gen; in btrfs_drop_extent_map_range()
816 split->flags = flags; in btrfs_drop_extent_map_range()
817 split->compress_type = em->compress_type; in btrfs_drop_extent_map_range()
830 split->start = end; in btrfs_drop_extent_map_range()
831 split->len = em_end - end; in btrfs_drop_extent_map_range()
832 split->block_start = em->block_start; in btrfs_drop_extent_map_range()
833 split->flags = flags; in btrfs_drop_extent_map_range()
834 split->compress_type = em->compress_type; in btrfs_drop_extent_map_range()
835 split->generation = gen; in btrfs_drop_extent_map_range()
837 if (em->block_start < EXTENT_MAP_LAST_BYTE) { in btrfs_drop_extent_map_range()
838 split->orig_block_len = max(em->block_len, in btrfs_drop_extent_map_range()
839 em->orig_block_len); in btrfs_drop_extent_map_range()
841 split->ram_bytes = em->ram_bytes; in btrfs_drop_extent_map_range()
843 split->block_len = em->block_len; in btrfs_drop_extent_map_range()
844 split->orig_start = em->orig_start; in btrfs_drop_extent_map_range()
846 const u64 diff = end - em->start; in btrfs_drop_extent_map_range()
848 split->block_len = split->len; in btrfs_drop_extent_map_range()
849 split->block_start += diff; in btrfs_drop_extent_map_range()
850 split->orig_start = em->orig_start; in btrfs_drop_extent_map_range()
853 split->ram_bytes = split->len; in btrfs_drop_extent_map_range()
854 split->orig_start = split->start; in btrfs_drop_extent_map_range()
855 split->block_len = 0; in btrfs_drop_extent_map_range()
856 split->orig_block_len = 0; in btrfs_drop_extent_map_range()
889 * extent map - this is fine since if anyone needs it to in btrfs_drop_extent_map_range()
897 if ((em->start < start || em_end > end) && modified) { in btrfs_drop_extent_map_range()
916 write_unlock(&em_tree->lock); in btrfs_drop_extent_map_range()
939 const u64 end = new_em->start + new_em->len - 1; in btrfs_replace_extent_map_range()
940 struct extent_map_tree *tree = &inode->extent_tree; in btrfs_replace_extent_map_range()
947 * tree, but getting -EEXIST when adding the new extent map can still in btrfs_replace_extent_map_range()
954 btrfs_drop_extent_map_range(inode, new_em->start, end, false); in btrfs_replace_extent_map_range()
955 write_lock(&tree->lock); in btrfs_replace_extent_map_range()
957 write_unlock(&tree->lock); in btrfs_replace_extent_map_range()
958 } while (ret == -EEXIST); in btrfs_replace_extent_map_range()
964 * Split off the first pre bytes from the extent_map at [start, start + len],
972 struct extent_map_tree *em_tree = &inode->extent_tree; in split_extent_map()
984 return -ENOMEM; in split_extent_map()
987 ret = -ENOMEM; in split_extent_map()
991 lock_extent(&inode->io_tree, start, start + len - 1, NULL); in split_extent_map()
992 write_lock(&em_tree->lock); in split_extent_map()
995 ret = -EIO; in split_extent_map()
999 ASSERT(em->len == len); in split_extent_map()
1000 ASSERT(!test_bit(EXTENT_FLAG_COMPRESSED, &em->flags)); in split_extent_map()
1001 ASSERT(em->block_start < EXTENT_MAP_LAST_BYTE); in split_extent_map()
1002 ASSERT(test_bit(EXTENT_FLAG_PINNED, &em->flags)); in split_extent_map()
1003 ASSERT(!test_bit(EXTENT_FLAG_LOGGING, &em->flags)); in split_extent_map()
1004 ASSERT(!list_empty(&em->list)); in split_extent_map()
1006 flags = em->flags; in split_extent_map()
1007 clear_bit(EXTENT_FLAG_PINNED, &em->flags); in split_extent_map()
1009 /* First, replace the em with a new extent_map starting from * em->start */ in split_extent_map()
1010 split_pre->start = em->start; in split_extent_map()
1011 split_pre->len = pre; in split_extent_map()
1012 split_pre->orig_start = split_pre->start; in split_extent_map()
1013 split_pre->block_start = new_logical; in split_extent_map()
1014 split_pre->block_len = split_pre->len; in split_extent_map()
1015 split_pre->orig_block_len = split_pre->block_len; in split_extent_map()
1016 split_pre->ram_bytes = split_pre->len; in split_extent_map()
1017 split_pre->flags = flags; in split_extent_map()
1018 split_pre->compress_type = em->compress_type; in split_extent_map()
1019 split_pre->generation = em->generation; in split_extent_map()
1025 * [em->start, em->start + pre] in split_extent_map()
1029 split_mid->start = em->start + pre; in split_extent_map()
1030 split_mid->len = em->len - pre; in split_extent_map()
1031 split_mid->orig_start = split_mid->start; in split_extent_map()
1032 split_mid->block_start = em->block_start + pre; in split_extent_map()
1033 split_mid->block_len = split_mid->len; in split_extent_map()
1034 split_mid->orig_block_len = split_mid->block_len; in split_extent_map()
1035 split_mid->ram_bytes = split_mid->len; in split_extent_map()
1036 split_mid->flags = flags; in split_extent_map()
1037 split_mid->compress_type = em->compress_type; in split_extent_map()
1038 split_mid->generation = em->generation; in split_extent_map()
1047 write_unlock(&em_tree->lock); in split_extent_map()
1048 unlock_extent(&inode->io_tree, start, start + len - 1, NULL); in split_extent_map()