Lines Matching full:tree
8 #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()
56 #define btrfs_debug_check_extent_io_range(tree, start, end) \ argument
57 __btrfs_debug_check_extent_io_range(__func__, (tree), (start), (end))
59 struct extent_io_tree *tree, in __btrfs_debug_check_extent_io_range() argument
65 if (tree->owner != IO_TREE_INODE_IO) in __btrfs_debug_check_extent_io_range()
68 inode = extent_io_tree_to_inode_const(tree); in __btrfs_debug_check_extent_io_range()
85 * The only tree allowed to set the inode is IO_TREE_INODE_IO.
87 static bool is_inode_io_tree(const struct extent_io_tree *tree) in is_inode_io_tree() argument
89 return tree->owner == IO_TREE_INODE_IO; in is_inode_io_tree()
92 /* Return the inode if it's valid for the given tree, otherwise NULL. */
93 struct btrfs_inode *extent_io_tree_to_inode(struct extent_io_tree *tree) in extent_io_tree_to_inode() argument
95 if (tree->owner == IO_TREE_INODE_IO) in extent_io_tree_to_inode()
96 return tree->inode; in extent_io_tree_to_inode()
101 const struct btrfs_inode *extent_io_tree_to_inode_const(const struct extent_io_tree *tree) in extent_io_tree_to_inode_const() argument
103 if (tree->owner == IO_TREE_INODE_IO) in extent_io_tree_to_inode_const()
104 return tree->inode; in extent_io_tree_to_inode_const()
109 const struct btrfs_fs_info *extent_io_tree_to_fs_info(const struct extent_io_tree *tree) in extent_io_tree_to_fs_info() argument
111 if (tree->owner == IO_TREE_INODE_IO) in extent_io_tree_to_fs_info()
112 return tree->inode->root->fs_info; in extent_io_tree_to_fs_info()
113 return tree->fs_info; in extent_io_tree_to_fs_info()
117 struct extent_io_tree *tree, unsigned int owner) in extent_io_tree_init() argument
119 tree->state = RB_ROOT; in extent_io_tree_init()
120 spin_lock_init(&tree->lock); in extent_io_tree_init()
121 tree->fs_info = fs_info; in extent_io_tree_init()
122 tree->owner = owner; in extent_io_tree_init()
126 * Empty an io tree, removing and freeing every extent state record from the
127 * tree. This should be called once we are sure no other task can access the
128 * tree anymore, so no tree updates happen after we empty the tree and there
132 void extent_io_tree_release(struct extent_io_tree *tree) in extent_io_tree_release() argument
138 spin_lock(&tree->lock); in extent_io_tree_release()
139 root = tree->state; in extent_io_tree_release()
140 tree->state = RB_ROOT; in extent_io_tree_release()
146 * No need for a memory barrier here, as we are holding the tree in extent_io_tree_release()
152 cond_resched_lock(&tree->lock); in extent_io_tree_release()
156 * be accessing the tree anymore. in extent_io_tree_release()
158 ASSERT(RB_EMPTY_ROOT(&tree->state)); in extent_io_tree_release()
159 spin_unlock(&tree->lock); in extent_io_tree_release()
242 * Search @tree for an entry that contains @offset. Such entry would have
245 * @tree: the tree to search
246 * @offset: offset that should fall within an entry in @tree
248 * entry in the tree)
258 static inline struct extent_state *tree_search_for_insert(struct extent_io_tree *tree, in tree_search_for_insert() argument
263 struct rb_root *root = &tree->state; in tree_search_for_insert()
293 * Search offset in the tree or fill neighbor rbtree node pointers.
295 * @tree: the tree to search
296 * @offset: offset that should fall within an entry in @tree
304 static struct extent_state *tree_search_prev_next(struct extent_io_tree *tree, in tree_search_prev_next() argument
309 struct rb_root *root = &tree->state; in tree_search_prev_next()
342 * Inexact rb-tree search, return the next entry if @offset is not found
344 static inline struct extent_state *tree_search(struct extent_io_tree *tree, u64 offset) in tree_search() argument
346 return tree_search_for_insert(tree, offset, NULL, NULL); in tree_search()
349 static void extent_io_tree_panic(const struct extent_io_tree *tree, in extent_io_tree_panic() argument
354 btrfs_panic(extent_io_tree_to_fs_info(tree), err, in extent_io_tree_panic()
355 "extent io tree error on %s state start %llu end %llu", in extent_io_tree_panic()
359 static void merge_prev_state(struct extent_io_tree *tree, struct extent_state *state) in merge_prev_state() argument
365 if (is_inode_io_tree(tree)) in merge_prev_state()
366 btrfs_merge_delalloc_extent(extent_io_tree_to_inode(tree), in merge_prev_state()
369 rb_erase(&prev->rb_node, &tree->state); in merge_prev_state()
375 static void merge_next_state(struct extent_io_tree *tree, struct extent_state *state) in merge_next_state() argument
381 if (is_inode_io_tree(tree)) in merge_next_state()
382 btrfs_merge_delalloc_extent(extent_io_tree_to_inode(tree), in merge_next_state()
385 rb_erase(&next->rb_node, &tree->state); in merge_next_state()
394 * tree. Extents with EXTENT_IO in their state field are not merged because
398 * This should be called with the tree lock held.
400 static void merge_state(struct extent_io_tree *tree, struct extent_state *state) in merge_state() argument
405 merge_prev_state(tree, state); in merge_state()
406 merge_next_state(tree, state); in merge_state()
409 static void set_state_bits(struct extent_io_tree *tree, in set_state_bits() argument
416 if (is_inode_io_tree(tree)) in set_state_bits()
417 btrfs_set_delalloc_extent(extent_io_tree_to_inode(tree), state, bits); in set_state_bits()
425 * Insert an extent_state struct into the tree. 'bits' are set on the
430 * may be an existing record in the tree that was expanded to accommodate the
436 * The tree lock is not taken internally. This is a utility function and
439 static struct extent_state *insert_state(struct extent_io_tree *tree, in insert_state() argument
450 set_state_bits(tree, state, bits, changeset); in insert_state()
452 node = &tree->state.rb_node; in insert_state()
462 if (is_inode_io_tree(tree)) in insert_state()
464 extent_io_tree_to_inode(tree), in insert_state()
467 merge_prev_state(tree, entry); in insert_state()
475 if (is_inode_io_tree(tree)) in insert_state()
477 extent_io_tree_to_inode(tree), in insert_state()
480 merge_next_state(tree, entry); in insert_state()
491 rb_insert_color(&state->rb_node, &tree->state); in insert_state()
497 * Insert state to @tree to the location given by @node and @parent.
499 static void insert_state_fast(struct extent_io_tree *tree, in insert_state_fast() argument
504 set_state_bits(tree, state, bits, changeset); in insert_state_fast()
506 rb_insert_color(&state->rb_node, &tree->state); in insert_state_fast()
507 merge_state(tree, state); in insert_state_fast()
516 * the tree has 'orig' at [orig->start, orig->end]. After calling, there
517 * are two extent state structs in the tree:
521 * The tree locks are not taken by this function. They need to be held
524 static int split_state(struct extent_io_tree *tree, struct extent_state *orig, in split_state() argument
530 if (is_inode_io_tree(tree)) in split_state()
531 btrfs_split_delalloc_extent(extent_io_tree_to_inode(tree), orig, in split_state()
558 rb_insert_color(&prealloc->rb_node, &tree->state); in split_state()
568 * struct is freed and removed from the tree
570 static struct extent_state *clear_state_bit(struct extent_io_tree *tree, in clear_state_bit() argument
579 if (is_inode_io_tree(tree)) in clear_state_bit()
580 btrfs_clear_delalloc_extent(extent_io_tree_to_inode(tree), state, in clear_state_bit()
591 rb_erase(&state->rb_node, &tree->state); in clear_state_bit()
598 merge_state(tree, state); in clear_state_bit()
615 * Clear some bits on a range in the tree. This may require splitting or
616 * inserting elements in the tree, so the gfp mask is used to indicate which
621 * This takes the tree lock, and returns 0 on success and < 0 on error.
623 int __clear_extent_bit(struct extent_io_tree *tree, u64 start, u64 end, in __clear_extent_bit() argument
638 btrfs_debug_check_extent_io_range(tree, start, end); in __clear_extent_bit()
639 trace_btrfs_clear_extent_bit(tree, start, end - start + 1, bits); in __clear_extent_bit()
655 * is the case if we only have in the tree extent states that in __clear_extent_bit()
662 spin_lock(&tree->lock); in __clear_extent_bit()
683 state = tree_search(tree, start); in __clear_extent_bit()
717 err = split_state(tree, state, prealloc, start); in __clear_extent_bit()
719 extent_io_tree_panic(tree, state, "split", err); in __clear_extent_bit()
725 state = clear_state_bit(tree, state, bits, wake, changeset); in __clear_extent_bit()
739 err = split_state(tree, state, prealloc, end + 1); in __clear_extent_bit()
741 extent_io_tree_panic(tree, state, "split", err); in __clear_extent_bit()
746 clear_state_bit(tree, prealloc, bits, wake, changeset); in __clear_extent_bit()
752 state = clear_state_bit(tree, state, bits, wake, changeset); in __clear_extent_bit()
763 spin_unlock(&tree->lock); in __clear_extent_bit()
769 spin_unlock(&tree->lock); in __clear_extent_bit()
778 * Wait for one or more bits to clear on a range in the state tree.
780 * The tree lock is taken by this function
782 static void wait_extent_bit(struct extent_io_tree *tree, u64 start, u64 end, in wait_extent_bit() argument
787 btrfs_debug_check_extent_io_range(tree, start, end); in wait_extent_bit()
789 spin_lock(&tree->lock); in wait_extent_bit()
792 * Maintain cached_state, as we may not remove it from the tree if there in wait_extent_bit()
806 state = tree_search(tree, start); in wait_extent_bit()
819 spin_unlock(&tree->lock); in wait_extent_bit()
821 spin_lock(&tree->lock); in wait_extent_bit()
831 if (!cond_resched_lock(&tree->lock)) { in wait_extent_bit()
843 spin_unlock(&tree->lock); in wait_extent_bit()
866 * tree->lock must be held. NULL will returned if nothing was found after
869 static struct extent_state *find_first_extent_bit_state(struct extent_io_tree *tree, in find_first_extent_bit_state() argument
878 state = tree_search(tree, start); in find_first_extent_bit_state()
888 * Find the first offset in the io tree with one or more @bits set.
895 bool find_first_extent_bit(struct extent_io_tree *tree, u64 start, in find_first_extent_bit() argument
902 spin_lock(&tree->lock); in find_first_extent_bit()
927 state = find_first_extent_bit_state(tree, start, bits); in find_first_extent_bit()
936 spin_unlock(&tree->lock); in find_first_extent_bit()
943 * @tree: io tree to check
951 * will drop the tree->lock, so use this helper if you want to find the actual
953 * then walk down the tree until we find a non-contiguous area. The area
956 int find_contiguous_extent_bit(struct extent_io_tree *tree, u64 start, in find_contiguous_extent_bit() argument
962 ASSERT(!btrfs_fs_incompat(extent_io_tree_to_fs_info(tree), NO_HOLES)); in find_contiguous_extent_bit()
964 spin_lock(&tree->lock); in find_contiguous_extent_bit()
965 state = find_first_extent_bit_state(tree, start, bits); in find_contiguous_extent_bit()
976 spin_unlock(&tree->lock); in find_contiguous_extent_bit()
984 * True is returned if we find something, false if nothing was in the tree.
986 bool btrfs_find_delalloc_range(struct extent_io_tree *tree, u64 *start, in btrfs_find_delalloc_range() argument
995 spin_lock(&tree->lock); in btrfs_find_delalloc_range()
1001 state = tree_search(tree, cur_start); in btrfs_find_delalloc_range()
1031 spin_unlock(&tree->lock); in btrfs_find_delalloc_range()
1036 * Set some bits on a range in the tree. This may require allocations or
1047 * [start, end] is inclusive This takes the tree lock.
1049 static int __set_extent_bit(struct extent_io_tree *tree, u64 start, u64 end, in __set_extent_bit() argument
1066 btrfs_debug_check_extent_io_range(tree, start, end); in __set_extent_bit()
1067 trace_btrfs_set_extent_bit(tree, start, end - start + 1, bits); in __set_extent_bit()
1078 * is the case if we only have in the tree extent states that in __set_extent_bit()
1088 spin_lock(&tree->lock); in __set_extent_bit()
1099 state = tree_search_for_insert(tree, start, &p, &parent); in __set_extent_bit()
1106 insert_state_fast(tree, prealloc, p, parent, bits, changeset); in __set_extent_bit()
1129 set_state_bits(tree, state, bits, changeset); in __set_extent_bit()
1131 merge_state(tree, state); in __set_extent_bit()
1178 ret = split_state(tree, state, prealloc, start); in __set_extent_bit()
1180 extent_io_tree_panic(tree, state, "split", ret); in __set_extent_bit()
1186 set_state_bits(tree, state, bits, changeset); in __set_extent_bit()
1188 merge_state(tree, state); in __set_extent_bit()
1225 inserted_state = insert_state(tree, prealloc, bits, changeset); in __set_extent_bit()
1228 extent_io_tree_panic(tree, prealloc, "insert", ret); in __set_extent_bit()
1254 ret = split_state(tree, state, prealloc, end + 1); in __set_extent_bit()
1256 extent_io_tree_panic(tree, state, "split", ret); in __set_extent_bit()
1258 set_state_bits(tree, prealloc, bits, changeset); in __set_extent_bit()
1260 merge_state(tree, prealloc); in __set_extent_bit()
1268 spin_unlock(&tree->lock); in __set_extent_bit()
1274 spin_unlock(&tree->lock); in __set_extent_bit()
1282 int set_extent_bit(struct extent_io_tree *tree, u64 start, u64 end, in set_extent_bit() argument
1285 return __set_extent_bit(tree, start, end, bits, NULL, NULL, in set_extent_bit()
1292 * @tree: the io tree to search
1307 int convert_extent_bit(struct extent_io_tree *tree, u64 start, u64 end, in convert_extent_bit() argument
1320 btrfs_debug_check_extent_io_range(tree, start, end); in convert_extent_bit()
1321 trace_btrfs_convert_extent_bit(tree, start, end - start + 1, bits, in convert_extent_bit()
1331 * after locking the tree. in convert_extent_bit()
1338 spin_lock(&tree->lock); in convert_extent_bit()
1350 state = tree_search_for_insert(tree, start, &p, &parent); in convert_extent_bit()
1359 insert_state_fast(tree, prealloc, p, parent, bits, NULL); in convert_extent_bit()
1375 set_state_bits(tree, state, bits, NULL); in convert_extent_bit()
1377 state = clear_state_bit(tree, state, clear_bits, 0, NULL); in convert_extent_bit()
1408 ret = split_state(tree, state, prealloc, start); in convert_extent_bit()
1410 extent_io_tree_panic(tree, state, "split", ret); in convert_extent_bit()
1415 set_state_bits(tree, state, bits, NULL); in convert_extent_bit()
1417 state = clear_state_bit(tree, state, clear_bits, 0, NULL); in convert_extent_bit()
1455 inserted_state = insert_state(tree, prealloc, bits, NULL); in convert_extent_bit()
1458 extent_io_tree_panic(tree, prealloc, "insert", ret); in convert_extent_bit()
1479 ret = split_state(tree, state, prealloc, end + 1); in convert_extent_bit()
1481 extent_io_tree_panic(tree, state, "split", ret); in convert_extent_bit()
1483 set_state_bits(tree, prealloc, bits, NULL); in convert_extent_bit()
1485 clear_state_bit(tree, prealloc, clear_bits, 0, NULL); in convert_extent_bit()
1493 spin_unlock(&tree->lock); in convert_extent_bit()
1499 spin_unlock(&tree->lock); in convert_extent_bit()
1510 * @tree: the tree to search
1521 void find_first_clear_extent_bit(struct extent_io_tree *tree, u64 start, in find_first_clear_extent_bit() argument
1527 spin_lock(&tree->lock); in find_first_clear_extent_bit()
1531 state = tree_search_prev_next(tree, start, &prev, &next); in find_first_clear_extent_bit()
1534 * Tree is completely empty, send full range and let in find_first_clear_extent_bit()
1611 spin_unlock(&tree->lock); in find_first_clear_extent_bit()
1615 * Count the number of bytes in the tree that have a given bit(s) set for a
1618 * @tree: The io tree to search.
1639 u64 count_range_bits(struct extent_io_tree *tree, in count_range_bits() argument
1654 spin_lock(&tree->lock); in count_range_bits()
1673 * when there are holes between records in the tree. If there is in count_range_bits()
1689 state = tree_search(tree, cur_start); in count_range_bits()
1719 spin_unlock(&tree->lock); in count_range_bits()
1727 bool test_range_bit_exists(struct extent_io_tree *tree, u64 start, u64 end, u32 bit) in test_range_bit_exists() argument
1734 spin_lock(&tree->lock); in test_range_bit_exists()
1735 state = tree_search(tree, start); in test_range_bit_exists()
1751 spin_unlock(&tree->lock); in test_range_bit_exists()
1758 bool test_range_bit(struct extent_io_tree *tree, u64 start, u64 end, u32 bit, in test_range_bit() argument
1766 spin_lock(&tree->lock); in test_range_bit()
1771 state = tree_search(tree, start); in test_range_bit()
1802 spin_unlock(&tree->lock); in test_range_bit()
1807 int set_record_extent_bits(struct extent_io_tree *tree, u64 start, u64 end, in set_record_extent_bits() argument
1817 return __set_extent_bit(tree, start, end, bits, NULL, NULL, NULL, changeset); in set_record_extent_bits()
1820 int clear_record_extent_bits(struct extent_io_tree *tree, u64 start, u64 end, in clear_record_extent_bits() argument
1829 return __clear_extent_bit(tree, start, end, bits, NULL, changeset); in clear_record_extent_bits()
1832 bool __try_lock_extent(struct extent_io_tree *tree, u64 start, u64 end, u32 bits, in __try_lock_extent() argument
1838 err = __set_extent_bit(tree, start, end, bits, &failed_start, in __try_lock_extent()
1842 clear_extent_bit(tree, start, failed_start - 1, bits, cached); in __try_lock_extent()
1852 int __lock_extent(struct extent_io_tree *tree, u64 start, u64 end, u32 bits, in __lock_extent() argument
1859 err = __set_extent_bit(tree, start, end, bits, &failed_start, in __lock_extent()
1863 clear_extent_bit(tree, start, failed_start - 1, in __lock_extent()
1866 wait_extent_bit(tree, failed_start, end, bits, &failed_state); in __lock_extent()
1867 err = __set_extent_bit(tree, start, end, bits, in __lock_extent()