Lines Matching full:tree
7 #include "extent-io-tree.h"
46 pr_err("BTRFS: state leak: start %llu end %llu state %u in tree %d refs %d\n", in btrfs_extent_state_leak_debug_check()
55 #define btrfs_debug_check_extent_io_range(tree, start, end) \ argument
56 __btrfs_debug_check_extent_io_range(__func__, (tree), (start), (end))
58 struct extent_io_tree *tree, in __btrfs_debug_check_extent_io_range() argument
61 struct btrfs_inode *inode = tree->inode; in __btrfs_debug_check_extent_io_range()
84 * the tree lock and get the inode lock when setting delalloc. These two things
97 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->inode = NULL; 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->inode) in merge_state()
350 btrfs_merge_delalloc_extent(tree->inode, state, other); in merge_state()
352 rb_erase(&other->rb_node, &tree->state); in merge_state()
359 if (tree->inode) in merge_state()
360 btrfs_merge_delalloc_extent(tree->inode, state, other); in merge_state()
362 rb_erase(&other->rb_node, &tree->state); in merge_state()
368 static void set_state_bits(struct extent_io_tree *tree, in set_state_bits() argument
375 if (tree->inode) in set_state_bits()
376 btrfs_set_delalloc_extent(tree->inode, state, bits); in set_state_bits()
384 * Insert an extent_state struct into the tree. 'bits' are set on the
390 * The tree lock is not taken internally. This is a utility function and
393 static int insert_state(struct extent_io_tree *tree, in insert_state() argument
401 set_state_bits(tree, state, bits, changeset); in insert_state()
403 node = &tree->state.rb_node; in insert_state()
415 btrfs_err(tree->fs_info, in insert_state()
423 rb_insert_color(&state->rb_node, &tree->state); in insert_state()
425 merge_state(tree, state); in insert_state()
430 * Insert state to @tree to the location given by @node and @parent.
432 static void insert_state_fast(struct extent_io_tree *tree, in insert_state_fast() argument
437 set_state_bits(tree, state, bits, changeset); in insert_state_fast()
439 rb_insert_color(&state->rb_node, &tree->state); in insert_state_fast()
440 merge_state(tree, state); in insert_state_fast()
449 * the tree has 'orig' at [orig->start, orig->end]. After calling, there
450 * are two extent state structs in the tree:
454 * The tree locks are not taken by this function. They need to be held
457 static int split_state(struct extent_io_tree *tree, struct extent_state *orig, in split_state() argument
463 if (tree->inode) in split_state()
464 btrfs_split_delalloc_extent(tree->inode, orig, split); in split_state()
490 rb_insert_color(&prealloc->rb_node, &tree->state); in split_state()
500 * struct is freed and removed from the tree
502 static struct extent_state *clear_state_bit(struct extent_io_tree *tree, in clear_state_bit() argument
511 if (tree->inode) in clear_state_bit()
512 btrfs_clear_delalloc_extent(tree->inode, state, bits); in clear_state_bit()
522 rb_erase(&state->rb_node, &tree->state); in clear_state_bit()
529 merge_state(tree, state); in clear_state_bit()
546 * Clear some bits on a range in the tree. This may require splitting or
547 * inserting elements in the tree, so the gfp mask is used to indicate which
551 * range from the tree regardless of state (ie for truncate).
555 * This takes the tree lock, and returns 0 on success and < 0 on error.
557 int __clear_extent_bit(struct extent_io_tree *tree, u64 start, u64 end, in __clear_extent_bit() argument
572 btrfs_debug_check_extent_io_range(tree, start, end); in __clear_extent_bit()
573 trace_btrfs_clear_extent_bit(tree, start, end - start + 1, bits); in __clear_extent_bit()
589 * is the case if we only have in the tree extent states that in __clear_extent_bit()
596 spin_lock(&tree->lock); in __clear_extent_bit()
617 state = tree_search(tree, start); in __clear_extent_bit()
651 err = split_state(tree, state, prealloc, start); in __clear_extent_bit()
653 extent_io_tree_panic(tree, err); in __clear_extent_bit()
659 state = clear_state_bit(tree, state, bits, wake, changeset); in __clear_extent_bit()
673 err = split_state(tree, state, prealloc, end + 1); in __clear_extent_bit()
675 extent_io_tree_panic(tree, err); in __clear_extent_bit()
680 clear_state_bit(tree, prealloc, bits, wake, changeset); in __clear_extent_bit()
686 state = clear_state_bit(tree, state, bits, wake, changeset); in __clear_extent_bit()
697 spin_unlock(&tree->lock); in __clear_extent_bit()
703 spin_unlock(&tree->lock); in __clear_extent_bit()
711 static void wait_on_state(struct extent_io_tree *tree, in wait_on_state() argument
713 __releases(tree->lock) in wait_on_state()
714 __acquires(tree->lock) in wait_on_state()
718 spin_unlock(&tree->lock); in wait_on_state()
720 spin_lock(&tree->lock); in wait_on_state()
725 * Wait for one or more bits to clear on a range in the state tree.
727 * The tree lock is taken by this function
729 void wait_extent_bit(struct extent_io_tree *tree, u64 start, u64 end, u32 bits, in wait_extent_bit() argument
734 btrfs_debug_check_extent_io_range(tree, start, end); in wait_extent_bit()
736 spin_lock(&tree->lock); in wait_extent_bit()
739 * Maintain cached_state, as we may not remove it from the tree if there in wait_extent_bit()
753 state = tree_search(tree, start); in wait_extent_bit()
763 wait_on_state(tree, state); in wait_extent_bit()
772 if (!cond_resched_lock(&tree->lock)) { in wait_extent_bit()
784 spin_unlock(&tree->lock); in wait_extent_bit()
808 * tree->lock must be held. NULL will returned if nothing was found after
811 static struct extent_state *find_first_extent_bit_state(struct extent_io_tree *tree, in find_first_extent_bit_state() argument
820 state = tree_search(tree, start); in find_first_extent_bit_state()
830 * Find the first offset in the io tree with one or more @bits set.
837 bool find_first_extent_bit(struct extent_io_tree *tree, u64 start, in find_first_extent_bit() argument
844 spin_lock(&tree->lock); in find_first_extent_bit()
860 state = find_first_extent_bit_state(tree, start, bits); in find_first_extent_bit()
869 spin_unlock(&tree->lock); in find_first_extent_bit()
876 * @tree: io tree to check
884 * will drop the tree->lock, so use this helper if you want to find the actual
886 * then walk down the tree until we find a non-contiguous area. The area
889 int find_contiguous_extent_bit(struct extent_io_tree *tree, u64 start, in find_contiguous_extent_bit() argument
895 spin_lock(&tree->lock); in find_contiguous_extent_bit()
896 state = find_first_extent_bit_state(tree, start, bits); in find_contiguous_extent_bit()
907 spin_unlock(&tree->lock); in find_contiguous_extent_bit()
915 * True is returned if we find something, false if nothing was in the tree.
917 bool btrfs_find_delalloc_range(struct extent_io_tree *tree, u64 *start, in btrfs_find_delalloc_range() argument
926 spin_lock(&tree->lock); in btrfs_find_delalloc_range()
932 state = tree_search(tree, cur_start); in btrfs_find_delalloc_range()
962 spin_unlock(&tree->lock); in btrfs_find_delalloc_range()
967 * Set some bits on a range in the tree. This may require allocations or
978 * [start, end] is inclusive This takes the tree lock.
980 static int __set_extent_bit(struct extent_io_tree *tree, u64 start, u64 end, in __set_extent_bit() argument
997 btrfs_debug_check_extent_io_range(tree, start, end); in __set_extent_bit()
998 trace_btrfs_set_extent_bit(tree, start, end - start + 1, bits); in __set_extent_bit()
1009 * is the case if we only have in the tree extent states that in __set_extent_bit()
1016 spin_lock(&tree->lock); in __set_extent_bit()
1027 state = tree_search_for_insert(tree, start, &p, &parent); in __set_extent_bit()
1034 insert_state_fast(tree, prealloc, p, parent, bits, changeset); in __set_extent_bit()
1057 set_state_bits(tree, state, bits, changeset); in __set_extent_bit()
1059 merge_state(tree, state); in __set_extent_bit()
1106 err = split_state(tree, state, prealloc, start); in __set_extent_bit()
1108 extent_io_tree_panic(tree, err); in __set_extent_bit()
1114 set_state_bits(tree, state, bits, changeset); in __set_extent_bit()
1116 merge_state(tree, state); in __set_extent_bit()
1151 err = insert_state(tree, prealloc, bits, changeset); in __set_extent_bit()
1153 extent_io_tree_panic(tree, err); in __set_extent_bit()
1177 err = split_state(tree, state, prealloc, end + 1); in __set_extent_bit()
1179 extent_io_tree_panic(tree, err); in __set_extent_bit()
1181 set_state_bits(tree, prealloc, bits, changeset); in __set_extent_bit()
1183 merge_state(tree, prealloc); in __set_extent_bit()
1191 spin_unlock(&tree->lock); in __set_extent_bit()
1197 spin_unlock(&tree->lock); in __set_extent_bit()
1205 int set_extent_bit(struct extent_io_tree *tree, u64 start, u64 end, in set_extent_bit() argument
1208 return __set_extent_bit(tree, start, end, bits, NULL, NULL, in set_extent_bit()
1215 * @tree: the io tree to search
1230 int convert_extent_bit(struct extent_io_tree *tree, u64 start, u64 end, in convert_extent_bit() argument
1243 btrfs_debug_check_extent_io_range(tree, start, end); in convert_extent_bit()
1244 trace_btrfs_convert_extent_bit(tree, start, end - start + 1, bits, in convert_extent_bit()
1254 * after locking the tree. in convert_extent_bit()
1261 spin_lock(&tree->lock); in convert_extent_bit()
1273 state = tree_search_for_insert(tree, start, &p, &parent); in convert_extent_bit()
1282 insert_state_fast(tree, prealloc, p, parent, bits, NULL); in convert_extent_bit()
1298 set_state_bits(tree, state, bits, NULL); in convert_extent_bit()
1300 state = clear_state_bit(tree, state, clear_bits, 0, NULL); in convert_extent_bit()
1331 err = split_state(tree, state, prealloc, start); in convert_extent_bit()
1333 extent_io_tree_panic(tree, err); in convert_extent_bit()
1338 set_state_bits(tree, state, bits, NULL); in convert_extent_bit()
1340 state = clear_state_bit(tree, state, clear_bits, 0, NULL); in convert_extent_bit()
1376 err = insert_state(tree, prealloc, bits, NULL); in convert_extent_bit()
1378 extent_io_tree_panic(tree, err); in convert_extent_bit()
1397 err = split_state(tree, state, prealloc, end + 1); in convert_extent_bit()
1399 extent_io_tree_panic(tree, err); in convert_extent_bit()
1401 set_state_bits(tree, prealloc, bits, NULL); in convert_extent_bit()
1403 clear_state_bit(tree, prealloc, clear_bits, 0, NULL); in convert_extent_bit()
1411 spin_unlock(&tree->lock); in convert_extent_bit()
1417 spin_unlock(&tree->lock); in convert_extent_bit()
1428 * @tree: the tree to search
1439 void find_first_clear_extent_bit(struct extent_io_tree *tree, u64 start, in find_first_clear_extent_bit() argument
1445 spin_lock(&tree->lock); in find_first_clear_extent_bit()
1449 state = tree_search_prev_next(tree, start, &prev, &next); in find_first_clear_extent_bit()
1452 * Tree is completely empty, send full range and let in find_first_clear_extent_bit()
1529 spin_unlock(&tree->lock); in find_first_clear_extent_bit()
1533 * Count the number of bytes in the tree that have a given bit(s) set for a
1536 * @tree: The io tree to search.
1557 u64 count_range_bits(struct extent_io_tree *tree, in count_range_bits() argument
1572 spin_lock(&tree->lock); in count_range_bits()
1591 * when there are holes between records in the tree. If there is in count_range_bits()
1607 state = tree_search(tree, cur_start); in count_range_bits()
1637 spin_unlock(&tree->lock); in count_range_bits()
1643 * Search a range in the state tree for a given mask. If 'filled' == 1, this
1644 * returns 1 only if every extent in the tree has the bits set. Otherwise, 1
1647 int test_range_bit(struct extent_io_tree *tree, u64 start, u64 end, in test_range_bit() argument
1653 spin_lock(&tree->lock); in test_range_bit()
1658 state = tree_search(tree, start); in test_range_bit()
1689 spin_unlock(&tree->lock); in test_range_bit()
1694 int set_record_extent_bits(struct extent_io_tree *tree, u64 start, u64 end, in set_record_extent_bits() argument
1705 return __set_extent_bit(tree, start, end, bits, NULL, NULL, NULL, changeset); in set_record_extent_bits()
1708 int clear_record_extent_bits(struct extent_io_tree *tree, u64 start, u64 end, in clear_record_extent_bits() argument
1717 return __clear_extent_bit(tree, start, end, bits, NULL, changeset); in clear_record_extent_bits()
1720 int try_lock_extent(struct extent_io_tree *tree, u64 start, u64 end, in try_lock_extent() argument
1726 err = __set_extent_bit(tree, start, end, EXTENT_LOCKED, &failed_start, in try_lock_extent()
1730 clear_extent_bit(tree, start, failed_start - 1, in try_lock_extent()
1741 int lock_extent(struct extent_io_tree *tree, u64 start, u64 end, in lock_extent() argument
1748 err = __set_extent_bit(tree, start, end, EXTENT_LOCKED, &failed_start, in lock_extent()
1752 clear_extent_bit(tree, start, failed_start - 1, in lock_extent()
1755 wait_extent_bit(tree, failed_start, end, EXTENT_LOCKED, in lock_extent()
1757 err = __set_extent_bit(tree, start, end, EXTENT_LOCKED, in lock_extent()