Lines Matching full:tree
6 #include "extent-io-tree.h"
45 pr_err("BTRFS: state leak: start %llu end %llu state %u in tree %d refs %d\n", in btrfs_extent_state_leak_debug_check()
54 #define btrfs_debug_check_extent_io_range(tree, start, end) \ argument
55 __btrfs_debug_check_extent_io_range(__func__, (tree), (start), (end))
57 struct extent_io_tree *tree, in __btrfs_debug_check_extent_io_range() argument
60 struct inode *inode = tree->private_data; in __btrfs_debug_check_extent_io_range()
83 * the tree lock and get the inode lock when setting delalloc. These two things
96 struct extent_io_tree *tree, unsigned int owner, in extent_io_tree_init() argument
99 tree->fs_info = fs_info; in extent_io_tree_init()
100 tree->state = RB_ROOT; in extent_io_tree_init()
101 spin_lock_init(&tree->lock); in extent_io_tree_init()
102 tree->private_data = private_data; in extent_io_tree_init()
103 tree->owner = owner; in extent_io_tree_init()
105 lockdep_set_class(&tree->lock, &file_extent_tree_class); in extent_io_tree_init()
108 void extent_io_tree_release(struct extent_io_tree *tree) in extent_io_tree_release() argument
110 spin_lock(&tree->lock); in extent_io_tree_release()
117 while (!RB_EMPTY_ROOT(&tree->state)) { in extent_io_tree_release()
121 node = rb_first(&tree->state); in extent_io_tree_release()
123 rb_erase(&state->rb_node, &tree->state); in extent_io_tree_release()
132 cond_resched_lock(&tree->lock); in extent_io_tree_release()
134 spin_unlock(&tree->lock); in extent_io_tree_release()
217 * Search @tree for an entry that contains @offset. Such entry would have
220 * @tree: the tree to search
221 * @offset: offset that should fall within an entry in @tree
223 * entry in the tree)
233 static inline struct extent_state *tree_search_for_insert(struct extent_io_tree *tree, in tree_search_for_insert() argument
238 struct rb_root *root = &tree->state; in tree_search_for_insert()
268 * Search offset in the tree or fill neighbor rbtree node pointers.
270 * @tree: the tree to search
271 * @offset: offset that should fall within an entry in @tree
279 static struct extent_state *tree_search_prev_next(struct extent_io_tree *tree, in tree_search_prev_next() argument
284 struct rb_root *root = &tree->state; in tree_search_prev_next()
317 * Inexact rb-tree search, return the next entry if @offset is not found
319 static inline struct extent_state *tree_search(struct extent_io_tree *tree, u64 offset) in tree_search() argument
321 return tree_search_for_insert(tree, offset, NULL, NULL); in tree_search()
324 static void extent_io_tree_panic(struct extent_io_tree *tree, int err) in extent_io_tree_panic() argument
326 btrfs_panic(tree->fs_info, err, in extent_io_tree_panic()
327 "locking error: extent tree was modified by another thread while locked"); in extent_io_tree_panic()
333 * tree. Extents with EXTENT_IO in their state field are not merged because
337 * This should be called with the tree lock held.
339 static void merge_state(struct extent_io_tree *tree, struct extent_state *state) in merge_state() argument
349 if (tree->private_data) in merge_state()
350 btrfs_merge_delalloc_extent(tree->private_data, in merge_state()
353 rb_erase(&other->rb_node, &tree->state); in merge_state()
360 if (tree->private_data) in merge_state()
361 btrfs_merge_delalloc_extent(tree->private_data, state, in merge_state()
364 rb_erase(&other->rb_node, &tree->state); in merge_state()
370 static void set_state_bits(struct extent_io_tree *tree, in set_state_bits() argument
377 if (tree->private_data) in set_state_bits()
378 btrfs_set_delalloc_extent(tree->private_data, state, bits); in set_state_bits()
386 * Insert an extent_state struct into the tree. 'bits' are set on the
392 * The tree lock is not taken internally. This is a utility function and
395 static int insert_state(struct extent_io_tree *tree, in insert_state() argument
403 set_state_bits(tree, state, bits, changeset); in insert_state()
405 node = &tree->state.rb_node; in insert_state()
417 btrfs_err(tree->fs_info, in insert_state()
425 rb_insert_color(&state->rb_node, &tree->state); in insert_state()
427 merge_state(tree, state); in insert_state()
432 * Insert state to @tree to the location given by @node and @parent.
434 static void insert_state_fast(struct extent_io_tree *tree, in insert_state_fast() argument
439 set_state_bits(tree, state, bits, changeset); in insert_state_fast()
441 rb_insert_color(&state->rb_node, &tree->state); in insert_state_fast()
442 merge_state(tree, state); in insert_state_fast()
451 * the tree has 'orig' at [orig->start, orig->end]. After calling, there
452 * are two extent state structs in the tree:
456 * The tree locks are not taken by this function. They need to be held
459 static int split_state(struct extent_io_tree *tree, struct extent_state *orig, in split_state() argument
465 if (tree->private_data) in split_state()
466 btrfs_split_delalloc_extent(tree->private_data, orig, split); in split_state()
492 rb_insert_color(&prealloc->rb_node, &tree->state); in split_state()
502 * struct is freed and removed from the tree
504 static struct extent_state *clear_state_bit(struct extent_io_tree *tree, in clear_state_bit() argument
513 if (tree->private_data) in clear_state_bit()
514 btrfs_clear_delalloc_extent(tree->private_data, state, bits); in clear_state_bit()
524 rb_erase(&state->rb_node, &tree->state); in clear_state_bit()
531 merge_state(tree, state); in clear_state_bit()
538 * Clear some bits on a range in the tree. This may require splitting or
539 * inserting elements in the tree, so the gfp mask is used to indicate which
543 * range from the tree regardless of state (ie for truncate).
547 * This takes the tree lock, and returns 0 on success and < 0 on error.
549 int __clear_extent_bit(struct extent_io_tree *tree, u64 start, u64 end, in __clear_extent_bit() argument
562 btrfs_debug_check_extent_io_range(tree, start, end); in __clear_extent_bit()
563 trace_btrfs_clear_extent_bit(tree, start, end - start + 1, bits); in __clear_extent_bit()
579 * is the case if we only have in the tree extent states that in __clear_extent_bit()
586 spin_lock(&tree->lock); in __clear_extent_bit()
607 state = tree_search(tree, start); in __clear_extent_bit()
640 err = split_state(tree, state, prealloc, start); in __clear_extent_bit()
642 extent_io_tree_panic(tree, err); in __clear_extent_bit()
648 state = clear_state_bit(tree, state, bits, wake, changeset); in __clear_extent_bit()
661 err = split_state(tree, state, prealloc, end + 1); in __clear_extent_bit()
663 extent_io_tree_panic(tree, err); in __clear_extent_bit()
668 clear_state_bit(tree, prealloc, bits, wake, changeset); in __clear_extent_bit()
674 state = clear_state_bit(tree, state, bits, wake, changeset); in __clear_extent_bit()
685 spin_unlock(&tree->lock); in __clear_extent_bit()
691 spin_unlock(&tree->lock); in __clear_extent_bit()
699 static void wait_on_state(struct extent_io_tree *tree, in wait_on_state() argument
701 __releases(tree->lock) in wait_on_state()
702 __acquires(tree->lock) in wait_on_state()
706 spin_unlock(&tree->lock); in wait_on_state()
708 spin_lock(&tree->lock); in wait_on_state()
713 * Wait for one or more bits to clear on a range in the state tree.
715 * The tree lock is taken by this function
717 void wait_extent_bit(struct extent_io_tree *tree, u64 start, u64 end, u32 bits) in wait_extent_bit() argument
721 btrfs_debug_check_extent_io_range(tree, start, end); in wait_extent_bit()
723 spin_lock(&tree->lock); in wait_extent_bit()
730 state = tree_search(tree, start); in wait_extent_bit()
740 wait_on_state(tree, state); in wait_extent_bit()
749 if (!cond_resched_lock(&tree->lock)) { in wait_extent_bit()
755 spin_unlock(&tree->lock); in wait_extent_bit()
779 * tree->lock must be held. NULL will returned if nothing was found after
782 static struct extent_state *find_first_extent_bit_state(struct extent_io_tree *tree, in find_first_extent_bit_state() argument
791 state = tree_search(tree, start); in find_first_extent_bit_state()
801 * Find the first offset in the io tree with one or more @bits set.
808 int find_first_extent_bit(struct extent_io_tree *tree, u64 start, in find_first_extent_bit() argument
815 spin_lock(&tree->lock); in find_first_extent_bit()
831 state = find_first_extent_bit_state(tree, start, bits); in find_first_extent_bit()
840 spin_unlock(&tree->lock); in find_first_extent_bit()
847 * @tree: io tree to check
855 * will drop the tree->lock, so use this helper if you want to find the actual
857 * then walk down the tree until we find a non-contiguous area. The area
860 int find_contiguous_extent_bit(struct extent_io_tree *tree, u64 start, in find_contiguous_extent_bit() argument
866 spin_lock(&tree->lock); in find_contiguous_extent_bit()
867 state = find_first_extent_bit_state(tree, start, bits); in find_contiguous_extent_bit()
878 spin_unlock(&tree->lock); in find_contiguous_extent_bit()
886 * True is returned if we find something, false if nothing was in the tree.
888 bool btrfs_find_delalloc_range(struct extent_io_tree *tree, u64 *start, in btrfs_find_delalloc_range() argument
897 spin_lock(&tree->lock); in btrfs_find_delalloc_range()
903 state = tree_search(tree, cur_start); in btrfs_find_delalloc_range()
933 spin_unlock(&tree->lock); in btrfs_find_delalloc_range()
938 * Set some bits on a range in the tree. This may require allocations or
945 * [start, end] is inclusive This takes the tree lock.
947 static int __set_extent_bit(struct extent_io_tree *tree, u64 start, u64 end, in __set_extent_bit() argument
961 btrfs_debug_check_extent_io_range(tree, start, end); in __set_extent_bit()
962 trace_btrfs_set_extent_bit(tree, start, end - start + 1, bits); in __set_extent_bit()
973 * is the case if we only have in the tree extent states that in __set_extent_bit()
980 spin_lock(&tree->lock); in __set_extent_bit()
991 state = tree_search_for_insert(tree, start, &p, &parent); in __set_extent_bit()
997 insert_state_fast(tree, prealloc, p, parent, bits, changeset); in __set_extent_bit()
1019 set_state_bits(tree, state, bits, changeset); in __set_extent_bit()
1021 merge_state(tree, state); in __set_extent_bit()
1066 err = split_state(tree, state, prealloc, start); in __set_extent_bit()
1068 extent_io_tree_panic(tree, err); in __set_extent_bit()
1074 set_state_bits(tree, state, bits, changeset); in __set_extent_bit()
1076 merge_state(tree, state); in __set_extent_bit()
1110 err = insert_state(tree, prealloc, bits, changeset); in __set_extent_bit()
1112 extent_io_tree_panic(tree, err); in __set_extent_bit()
1134 err = split_state(tree, state, prealloc, end + 1); in __set_extent_bit()
1136 extent_io_tree_panic(tree, err); in __set_extent_bit()
1138 set_state_bits(tree, prealloc, bits, changeset); in __set_extent_bit()
1140 merge_state(tree, prealloc); in __set_extent_bit()
1148 spin_unlock(&tree->lock); in __set_extent_bit()
1154 spin_unlock(&tree->lock); in __set_extent_bit()
1162 int set_extent_bit(struct extent_io_tree *tree, u64 start, u64 end, in set_extent_bit() argument
1165 return __set_extent_bit(tree, start, end, bits, NULL, cached_state, in set_extent_bit()
1172 * @tree: the io tree to search
1187 int convert_extent_bit(struct extent_io_tree *tree, u64 start, u64 end, in convert_extent_bit() argument
1200 btrfs_debug_check_extent_io_range(tree, start, end); in convert_extent_bit()
1201 trace_btrfs_convert_extent_bit(tree, start, end - start + 1, bits, in convert_extent_bit()
1211 * after locking the tree. in convert_extent_bit()
1218 spin_lock(&tree->lock); in convert_extent_bit()
1230 state = tree_search_for_insert(tree, start, &p, &parent); in convert_extent_bit()
1239 insert_state_fast(tree, prealloc, p, parent, bits, NULL); in convert_extent_bit()
1255 set_state_bits(tree, state, bits, NULL); in convert_extent_bit()
1257 state = clear_state_bit(tree, state, clear_bits, 0, NULL); in convert_extent_bit()
1288 err = split_state(tree, state, prealloc, start); in convert_extent_bit()
1290 extent_io_tree_panic(tree, err); in convert_extent_bit()
1295 set_state_bits(tree, state, bits, NULL); in convert_extent_bit()
1297 state = clear_state_bit(tree, state, clear_bits, 0, NULL); in convert_extent_bit()
1333 err = insert_state(tree, prealloc, bits, NULL); in convert_extent_bit()
1335 extent_io_tree_panic(tree, err); in convert_extent_bit()
1354 err = split_state(tree, state, prealloc, end + 1); in convert_extent_bit()
1356 extent_io_tree_panic(tree, err); in convert_extent_bit()
1358 set_state_bits(tree, prealloc, bits, NULL); in convert_extent_bit()
1360 clear_state_bit(tree, prealloc, clear_bits, 0, NULL); in convert_extent_bit()
1368 spin_unlock(&tree->lock); in convert_extent_bit()
1374 spin_unlock(&tree->lock); in convert_extent_bit()
1385 * @tree: the tree to search
1396 void find_first_clear_extent_bit(struct extent_io_tree *tree, u64 start, in find_first_clear_extent_bit() argument
1402 spin_lock(&tree->lock); in find_first_clear_extent_bit()
1406 state = tree_search_prev_next(tree, start, &prev, &next); in find_first_clear_extent_bit()
1409 * Tree is completely empty, send full range and let in find_first_clear_extent_bit()
1486 spin_unlock(&tree->lock); in find_first_clear_extent_bit()
1490 * Count the number of bytes in the tree that have a given bit(s) set. This
1494 u64 count_range_bits(struct extent_io_tree *tree, in count_range_bits() argument
1507 spin_lock(&tree->lock); in count_range_bits()
1513 state = tree_search(tree, cur_start); in count_range_bits()
1534 spin_unlock(&tree->lock); in count_range_bits()
1539 * Searche a range in the state tree for a given mask. If 'filled' == 1, this
1540 * returns 1 only if every extent in the tree has the bits set. Otherwise, 1
1543 int test_range_bit(struct extent_io_tree *tree, u64 start, u64 end, in test_range_bit() argument
1549 spin_lock(&tree->lock); in test_range_bit()
1554 state = tree_search(tree, start); in test_range_bit()
1585 spin_unlock(&tree->lock); in test_range_bit()
1590 int set_record_extent_bits(struct extent_io_tree *tree, u64 start, u64 end, in set_record_extent_bits() argument
1601 return __set_extent_bit(tree, start, end, bits, NULL, NULL, changeset, in set_record_extent_bits()
1605 int clear_record_extent_bits(struct extent_io_tree *tree, u64 start, u64 end, in clear_record_extent_bits() argument
1614 return __clear_extent_bit(tree, start, end, bits, NULL, GFP_NOFS, in clear_record_extent_bits()
1618 int try_lock_extent(struct extent_io_tree *tree, u64 start, u64 end) in try_lock_extent() argument
1623 err = __set_extent_bit(tree, start, end, EXTENT_LOCKED, &failed_start, in try_lock_extent()
1627 clear_extent_bit(tree, start, failed_start - 1, in try_lock_extent()
1638 int lock_extent(struct extent_io_tree *tree, u64 start, u64 end, in lock_extent() argument
1644 err = __set_extent_bit(tree, start, end, EXTENT_LOCKED, &failed_start, in lock_extent()
1648 clear_extent_bit(tree, start, failed_start - 1, in lock_extent()
1651 wait_extent_bit(tree, failed_start, end, EXTENT_LOCKED); in lock_extent()
1652 err = __set_extent_bit(tree, start, end, EXTENT_LOCKED, in lock_extent()