1 // SPDX-License-Identifier: GPL-2.0
3 #include <linux/slab.h>
4 #include <trace/events/btrfs.h>
7 #include "extent-io-tree.h"
8 #include "btrfs_inode.h"
11 static struct kmem_cache *extent_state_cache;
13 static inline bool extent_state_in_tree(const struct extent_state *state)
15 return !RB_EMPTY_NODE(&state->rb_node);
18 #ifdef CONFIG_BTRFS_DEBUG
19 static LIST_HEAD(states);
20 static DEFINE_SPINLOCK(leak_lock);
22 static inline void btrfs_leak_debug_add_state(struct extent_state *state)
26 spin_lock_irqsave(&leak_lock, flags);
27 list_add(&state->leak_list, &states);
28 spin_unlock_irqrestore(&leak_lock, flags);
31 static inline void btrfs_leak_debug_del_state(struct extent_state *state)
35 spin_lock_irqsave(&leak_lock, flags);
36 list_del(&state->leak_list);
37 spin_unlock_irqrestore(&leak_lock, flags);
40 static inline void btrfs_extent_state_leak_debug_check(void)
42 struct extent_state *state;
44 while (!list_empty(&states)) {
45 state = list_entry(states.next, struct extent_state, leak_list);
46 pr_err("BTRFS: state leak: start %llu end %llu state %u in tree %d refs %d\n",
47 state->start, state->end, state->state,
48 extent_state_in_tree(state),
49 refcount_read(&state->refs));
50 list_del(&state->leak_list);
51 kmem_cache_free(extent_state_cache, state);
55 #define btrfs_debug_check_extent_io_range(tree, start, end) \
56 __btrfs_debug_check_extent_io_range(__func__, (tree), (start), (end))
57 static inline void __btrfs_debug_check_extent_io_range(const char *caller,
58 struct extent_io_tree *tree,
61 const struct btrfs_inode *inode;
64 if (tree->owner != IO_TREE_INODE_IO)
67 inode = extent_io_tree_to_inode_const(tree);
68 isize = i_size_read(&inode->vfs_inode);
69 if (end >= PAGE_SIZE && (end % 2) == 0 && end != isize - 1) {
70 btrfs_debug_rl(inode->root->fs_info,
71 "%s: ino %llu isize %llu odd range [%llu,%llu]",
72 caller, btrfs_ino(inode), isize, start, end);
76 #define btrfs_leak_debug_add_state(state) do {} while (0)
77 #define btrfs_leak_debug_del_state(state) do {} while (0)
78 #define btrfs_extent_state_leak_debug_check() do {} while (0)
79 #define btrfs_debug_check_extent_io_range(c, s, e) do {} while (0)
84 * The only tree allowed to set the inode is IO_TREE_INODE_IO.
86 static bool is_inode_io_tree(const struct extent_io_tree *tree)
88 return tree->owner == IO_TREE_INODE_IO;
91 /* Return the inode if it's valid for the given tree, otherwise NULL. */
92 struct btrfs_inode *extent_io_tree_to_inode(struct extent_io_tree *tree)
94 if (tree->owner == IO_TREE_INODE_IO)
99 /* Read-only access to the inode. */
100 const struct btrfs_inode *extent_io_tree_to_inode_const(const struct extent_io_tree *tree)
102 if (tree->owner == IO_TREE_INODE_IO)
107 /* For read-only access to fs_info. */
108 const struct btrfs_fs_info *extent_io_tree_to_fs_info(const struct extent_io_tree *tree)
110 if (tree->owner == IO_TREE_INODE_IO)
111 return tree->inode->root->fs_info;
112 return tree->fs_info;
115 void extent_io_tree_init(struct btrfs_fs_info *fs_info,
116 struct extent_io_tree *tree, unsigned int owner)
118 tree->state = RB_ROOT;
119 spin_lock_init(&tree->lock);
120 tree->fs_info = fs_info;
125 * Empty an io tree, removing and freeing every extent state record from the
126 * tree. This should be called once we are sure no other task can access the
127 * tree anymore, so no tree updates happen after we empty the tree and there
128 * aren't any waiters on any extent state record (EXTENT_LOCKED bit is never
129 * set on any extent state when calling this function).
131 void extent_io_tree_release(struct extent_io_tree *tree)
134 struct extent_state *state;
135 struct extent_state *tmp;
137 spin_lock(&tree->lock);
139 tree->state = RB_ROOT;
140 rbtree_postorder_for_each_entry_safe(state, tmp, &root, rb_node) {
141 /* Clear node to keep free_extent_state() happy. */
142 RB_CLEAR_NODE(&state->rb_node);
143 ASSERT(!(state->state & EXTENT_LOCKED));
145 * No need for a memory barrier here, as we are holding the tree
146 * lock and we only change the waitqueue while holding that lock
147 * (see wait_extent_bit()).
149 ASSERT(!waitqueue_active(&state->wq));
150 free_extent_state(state);
151 cond_resched_lock(&tree->lock);
154 * Should still be empty even after a reschedule, no other task should
155 * be accessing the tree anymore.
157 ASSERT(RB_EMPTY_ROOT(&tree->state));
158 spin_unlock(&tree->lock);
161 static struct extent_state *alloc_extent_state(gfp_t mask)
163 struct extent_state *state;
166 * The given mask might be not appropriate for the slab allocator,
167 * drop the unsupported bits
169 mask &= ~(__GFP_DMA32|__GFP_HIGHMEM);
170 state = kmem_cache_alloc(extent_state_cache, mask);
174 RB_CLEAR_NODE(&state->rb_node);
175 btrfs_leak_debug_add_state(state);
176 refcount_set(&state->refs, 1);
177 init_waitqueue_head(&state->wq);
178 trace_alloc_extent_state(state, mask, _RET_IP_);
182 static struct extent_state *alloc_extent_state_atomic(struct extent_state *prealloc)
185 prealloc = alloc_extent_state(GFP_ATOMIC);
190 void free_extent_state(struct extent_state *state)
194 if (refcount_dec_and_test(&state->refs)) {
195 WARN_ON(extent_state_in_tree(state));
196 btrfs_leak_debug_del_state(state);
197 trace_free_extent_state(state, _RET_IP_);
198 kmem_cache_free(extent_state_cache, state);
202 static int add_extent_changeset(struct extent_state *state, u32 bits,
203 struct extent_changeset *changeset,
210 if (set && (state->state & bits) == bits)
212 if (!set && (state->state & bits) == 0)
214 changeset->bytes_changed += state->end - state->start + 1;
215 ret = ulist_add(&changeset->range_changed, state->start, state->end,
220 static inline struct extent_state *next_state(struct extent_state *state)
222 struct rb_node *next = rb_next(&state->rb_node);
225 return rb_entry(next, struct extent_state, rb_node);
230 static inline struct extent_state *prev_state(struct extent_state *state)
232 struct rb_node *next = rb_prev(&state->rb_node);
235 return rb_entry(next, struct extent_state, rb_node);
241 * Search @tree for an entry that contains @offset. Such entry would have
242 * entry->start <= offset && entry->end >= offset.
244 * @tree: the tree to search
245 * @offset: offset that should fall within an entry in @tree
246 * @node_ret: pointer where new node should be anchored (used when inserting an
248 * @parent_ret: points to entry which would have been the parent of the entry,
251 * Return a pointer to the entry that contains @offset byte address and don't change
252 * @node_ret and @parent_ret.
254 * If no such entry exists, return pointer to entry that ends before @offset
255 * and fill parameters @node_ret and @parent_ret, ie. does not return NULL.
257 static inline struct extent_state *tree_search_for_insert(struct extent_io_tree *tree,
259 struct rb_node ***node_ret,
260 struct rb_node **parent_ret)
262 struct rb_root *root = &tree->state;
263 struct rb_node **node = &root->rb_node;
264 struct rb_node *prev = NULL;
265 struct extent_state *entry = NULL;
269 entry = rb_entry(prev, struct extent_state, rb_node);
271 if (offset < entry->start)
272 node = &(*node)->rb_left;
273 else if (offset > entry->end)
274 node = &(*node)->rb_right;
284 /* Search neighbors until we find the first one past the end */
285 while (entry && offset > entry->end)
286 entry = next_state(entry);
292 * Search offset in the tree or fill neighbor rbtree node pointers.
294 * @tree: the tree to search
295 * @offset: offset that should fall within an entry in @tree
296 * @next_ret: pointer to the first entry whose range ends after @offset
297 * @prev_ret: pointer to the first entry whose range begins before @offset
299 * Return a pointer to the entry that contains @offset byte address. If no
300 * such entry exists, then return NULL and fill @prev_ret and @next_ret.
301 * Otherwise return the found entry and other pointers are left untouched.
303 static struct extent_state *tree_search_prev_next(struct extent_io_tree *tree,
305 struct extent_state **prev_ret,
306 struct extent_state **next_ret)
308 struct rb_root *root = &tree->state;
309 struct rb_node **node = &root->rb_node;
310 struct extent_state *orig_prev;
311 struct extent_state *entry = NULL;
317 entry = rb_entry(*node, struct extent_state, rb_node);
319 if (offset < entry->start)
320 node = &(*node)->rb_left;
321 else if (offset > entry->end)
322 node = &(*node)->rb_right;
328 while (entry && offset > entry->end)
329 entry = next_state(entry);
333 while (entry && offset < entry->start)
334 entry = prev_state(entry);
341 * Inexact rb-tree search, return the next entry if @offset is not found
343 static inline struct extent_state *tree_search(struct extent_io_tree *tree, u64 offset)
345 return tree_search_for_insert(tree, offset, NULL, NULL);
348 static void extent_io_tree_panic(const struct extent_io_tree *tree,
349 const struct extent_state *state,
353 btrfs_panic(extent_io_tree_to_fs_info(tree), err,
354 "extent io tree error on %s state start %llu end %llu",
355 opname, state->start, state->end);
358 static void merge_prev_state(struct extent_io_tree *tree, struct extent_state *state)
360 struct extent_state *prev;
362 prev = prev_state(state);
363 if (prev && prev->end == state->start - 1 && prev->state == state->state) {
364 if (is_inode_io_tree(tree))
365 btrfs_merge_delalloc_extent(extent_io_tree_to_inode(tree),
367 state->start = prev->start;
368 rb_erase(&prev->rb_node, &tree->state);
369 RB_CLEAR_NODE(&prev->rb_node);
370 free_extent_state(prev);
374 static void merge_next_state(struct extent_io_tree *tree, struct extent_state *state)
376 struct extent_state *next;
378 next = next_state(state);
379 if (next && next->start == state->end + 1 && next->state == state->state) {
380 if (is_inode_io_tree(tree))
381 btrfs_merge_delalloc_extent(extent_io_tree_to_inode(tree),
383 state->end = next->end;
384 rb_erase(&next->rb_node, &tree->state);
385 RB_CLEAR_NODE(&next->rb_node);
386 free_extent_state(next);
391 * Utility function to look for merge candidates inside a given range. Any
392 * extents with matching state are merged together into a single extent in the
393 * tree. Extents with EXTENT_IO in their state field are not merged because
394 * the end_io handlers need to be able to do operations on them without
395 * sleeping (or doing allocations/splits).
397 * This should be called with the tree lock held.
399 static void merge_state(struct extent_io_tree *tree, struct extent_state *state)
401 if (state->state & (EXTENT_LOCKED | EXTENT_BOUNDARY))
404 merge_prev_state(tree, state);
405 merge_next_state(tree, state);
408 static void set_state_bits(struct extent_io_tree *tree,
409 struct extent_state *state,
410 u32 bits, struct extent_changeset *changeset)
412 u32 bits_to_set = bits & ~EXTENT_CTLBITS;
415 if (is_inode_io_tree(tree))
416 btrfs_set_delalloc_extent(extent_io_tree_to_inode(tree), state, bits);
418 ret = add_extent_changeset(state, bits_to_set, changeset, 1);
420 state->state |= bits_to_set;
424 * Insert an extent_state struct into the tree. 'bits' are set on the
425 * struct before it is inserted.
427 * Returns a pointer to the struct extent_state record containing the range
428 * requested for insertion, which may be the same as the given struct or it
429 * may be an existing record in the tree that was expanded to accommodate the
430 * requested range. In case of an extent_state different from the one that was
431 * given, the later can be freed or reused by the caller.
433 * On error it returns an error pointer.
435 * The tree lock is not taken internally. This is a utility function and
436 * probably isn't what you want to call (see set/clear_extent_bit).
438 static struct extent_state *insert_state(struct extent_io_tree *tree,
439 struct extent_state *state,
441 struct extent_changeset *changeset)
443 struct rb_node **node;
444 struct rb_node *parent = NULL;
445 const u64 start = state->start - 1;
446 const u64 end = state->end + 1;
447 const bool try_merge = !(bits & (EXTENT_LOCKED | EXTENT_BOUNDARY));
449 set_state_bits(tree, state, bits, changeset);
451 node = &tree->state.rb_node;
453 struct extent_state *entry;
456 entry = rb_entry(parent, struct extent_state, rb_node);
458 if (state->end < entry->start) {
459 if (try_merge && end == entry->start &&
460 state->state == entry->state) {
461 if (is_inode_io_tree(tree))
462 btrfs_merge_delalloc_extent(
463 extent_io_tree_to_inode(tree),
465 entry->start = state->start;
466 merge_prev_state(tree, entry);
470 node = &(*node)->rb_left;
471 } else if (state->end > entry->end) {
472 if (try_merge && entry->end == start &&
473 state->state == entry->state) {
474 if (is_inode_io_tree(tree))
475 btrfs_merge_delalloc_extent(
476 extent_io_tree_to_inode(tree),
478 entry->end = state->end;
479 merge_next_state(tree, entry);
483 node = &(*node)->rb_right;
485 return ERR_PTR(-EEXIST);
489 rb_link_node(&state->rb_node, parent, node);
490 rb_insert_color(&state->rb_node, &tree->state);
496 * Insert state to @tree to the location given by @node and @parent.
498 static void insert_state_fast(struct extent_io_tree *tree,
499 struct extent_state *state, struct rb_node **node,
500 struct rb_node *parent, unsigned bits,
501 struct extent_changeset *changeset)
503 set_state_bits(tree, state, bits, changeset);
504 rb_link_node(&state->rb_node, parent, node);
505 rb_insert_color(&state->rb_node, &tree->state);
506 merge_state(tree, state);
510 * Split a given extent state struct in two, inserting the preallocated
511 * struct 'prealloc' as the newly created second half. 'split' indicates an
512 * offset inside 'orig' where it should be split.
515 * the tree has 'orig' at [orig->start, orig->end]. After calling, there
516 * are two extent state structs in the tree:
517 * prealloc: [orig->start, split - 1]
518 * orig: [ split, orig->end ]
520 * The tree locks are not taken by this function. They need to be held
523 static int split_state(struct extent_io_tree *tree, struct extent_state *orig,
524 struct extent_state *prealloc, u64 split)
526 struct rb_node *parent = NULL;
527 struct rb_node **node;
529 if (is_inode_io_tree(tree))
530 btrfs_split_delalloc_extent(extent_io_tree_to_inode(tree), orig,
533 prealloc->start = orig->start;
534 prealloc->end = split - 1;
535 prealloc->state = orig->state;
538 parent = &orig->rb_node;
541 struct extent_state *entry;
544 entry = rb_entry(parent, struct extent_state, rb_node);
546 if (prealloc->end < entry->start) {
547 node = &(*node)->rb_left;
548 } else if (prealloc->end > entry->end) {
549 node = &(*node)->rb_right;
551 free_extent_state(prealloc);
556 rb_link_node(&prealloc->rb_node, parent, node);
557 rb_insert_color(&prealloc->rb_node, &tree->state);
563 * Utility function to clear some bits in an extent state struct. It will
564 * optionally wake up anyone waiting on this state (wake == 1).
566 * If no bits are set on the state struct after clearing things, the
567 * struct is freed and removed from the tree
569 static struct extent_state *clear_state_bit(struct extent_io_tree *tree,
570 struct extent_state *state,
572 struct extent_changeset *changeset)
574 struct extent_state *next;
575 u32 bits_to_clear = bits & ~EXTENT_CTLBITS;
578 if (is_inode_io_tree(tree))
579 btrfs_clear_delalloc_extent(extent_io_tree_to_inode(tree), state,
582 ret = add_extent_changeset(state, bits_to_clear, changeset, 0);
584 state->state &= ~bits_to_clear;
587 if (state->state == 0) {
588 next = next_state(state);
589 if (extent_state_in_tree(state)) {
590 rb_erase(&state->rb_node, &tree->state);
591 RB_CLEAR_NODE(&state->rb_node);
592 free_extent_state(state);
597 merge_state(tree, state);
598 next = next_state(state);
604 * Detect if extent bits request NOWAIT semantics and set the gfp mask accordingly,
605 * unset the EXTENT_NOWAIT bit.
607 static void set_gfp_mask_from_bits(u32 *bits, gfp_t *mask)
609 *mask = (*bits & EXTENT_NOWAIT ? GFP_NOWAIT : GFP_NOFS);
610 *bits &= EXTENT_NOWAIT - 1;
614 * Clear some bits on a range in the tree. This may require splitting or
615 * inserting elements in the tree, so the gfp mask is used to indicate which
616 * allocations or sleeping are allowed.
618 * Pass 'wake' == 1 to kick any sleepers, and 'delete' == 1 to remove the given
619 * range from the tree regardless of state (ie for truncate).
621 * The range [start, end] is inclusive.
623 * This takes the tree lock, and returns 0 on success and < 0 on error.
625 int __clear_extent_bit(struct extent_io_tree *tree, u64 start, u64 end,
626 u32 bits, struct extent_state **cached_state,
627 struct extent_changeset *changeset)
629 struct extent_state *state;
630 struct extent_state *cached;
631 struct extent_state *prealloc = NULL;
636 int delete = (bits & EXTENT_CLEAR_ALL_BITS);
639 set_gfp_mask_from_bits(&bits, &mask);
640 btrfs_debug_check_extent_io_range(tree, start, end);
641 trace_btrfs_clear_extent_bit(tree, start, end - start + 1, bits);
644 bits |= ~EXTENT_CTLBITS;
646 if (bits & EXTENT_DELALLOC)
647 bits |= EXTENT_NORESERVE;
649 wake = (bits & EXTENT_LOCKED) ? 1 : 0;
650 if (bits & (EXTENT_LOCKED | EXTENT_BOUNDARY))
655 * Don't care for allocation failure here because we might end
656 * up not needing the pre-allocated extent state at all, which
657 * is the case if we only have in the tree extent states that
658 * cover our input range and don't cover too any other range.
659 * If we end up needing a new extent state we allocate it later.
661 prealloc = alloc_extent_state(mask);
664 spin_lock(&tree->lock);
666 cached = *cached_state;
669 *cached_state = NULL;
673 if (cached && extent_state_in_tree(cached) &&
674 cached->start <= start && cached->end > start) {
676 refcount_dec(&cached->refs);
681 free_extent_state(cached);
684 /* This search will find the extents that end after our range starts. */
685 state = tree_search(tree, start);
689 if (state->start > end)
691 WARN_ON(state->end < start);
692 last_end = state->end;
694 /* The state doesn't have the wanted bits, go ahead. */
695 if (!(state->state & bits)) {
696 state = next_state(state);
701 * | ---- desired range ---- |
703 * | ------------- state -------------- |
705 * We need to split the extent we found, and may flip bits on second
708 * If the extent we found extends past our range, we just split and
709 * search again. It'll get split again the next time though.
711 * If the extent we found is inside our range, we clear the desired bit
715 if (state->start < start) {
716 prealloc = alloc_extent_state_atomic(prealloc);
719 err = split_state(tree, state, prealloc, start);
721 extent_io_tree_panic(tree, state, "split", err);
726 if (state->end <= end) {
727 state = clear_state_bit(tree, state, bits, wake, changeset);
733 * | ---- desired range ---- |
735 * We need to split the extent, and clear the bit on the first half.
737 if (state->start <= end && state->end > end) {
738 prealloc = alloc_extent_state_atomic(prealloc);
741 err = split_state(tree, state, prealloc, end + 1);
743 extent_io_tree_panic(tree, state, "split", err);
748 clear_state_bit(tree, prealloc, bits, wake, changeset);
754 state = clear_state_bit(tree, state, bits, wake, changeset);
756 if (last_end == (u64)-1)
758 start = last_end + 1;
759 if (start <= end && state && !need_resched())
765 spin_unlock(&tree->lock);
766 if (gfpflags_allow_blocking(mask))
771 spin_unlock(&tree->lock);
773 free_extent_state(prealloc);
780 * Wait for one or more bits to clear on a range in the state tree.
781 * The range [start, end] is inclusive.
782 * The tree lock is taken by this function
784 static void wait_extent_bit(struct extent_io_tree *tree, u64 start, u64 end,
785 u32 bits, struct extent_state **cached_state)
787 struct extent_state *state;
789 btrfs_debug_check_extent_io_range(tree, start, end);
791 spin_lock(&tree->lock);
794 * Maintain cached_state, as we may not remove it from the tree if there
795 * are more bits than the bits we're waiting on set on this state.
797 if (cached_state && *cached_state) {
798 state = *cached_state;
799 if (extent_state_in_tree(state) &&
800 state->start <= start && start < state->end)
805 * This search will find all the extents that end after our
808 state = tree_search(tree, start);
812 if (state->start > end)
815 if (state->state & bits) {
818 start = state->start;
819 refcount_inc(&state->refs);
820 prepare_to_wait(&state->wq, &wait, TASK_UNINTERRUPTIBLE);
821 spin_unlock(&tree->lock);
823 spin_lock(&tree->lock);
824 finish_wait(&state->wq, &wait);
825 free_extent_state(state);
828 start = state->end + 1;
833 if (!cond_resched_lock(&tree->lock)) {
834 state = next_state(state);
839 /* This state is no longer useful, clear it and free it up. */
840 if (cached_state && *cached_state) {
841 state = *cached_state;
842 *cached_state = NULL;
843 free_extent_state(state);
845 spin_unlock(&tree->lock);
848 static void cache_state_if_flags(struct extent_state *state,
849 struct extent_state **cached_ptr,
852 if (cached_ptr && !(*cached_ptr)) {
853 if (!flags || (state->state & flags)) {
855 refcount_inc(&state->refs);
860 static void cache_state(struct extent_state *state,
861 struct extent_state **cached_ptr)
863 return cache_state_if_flags(state, cached_ptr,
864 EXTENT_LOCKED | EXTENT_BOUNDARY);
868 * Find the first state struct with 'bits' set after 'start', and return it.
869 * tree->lock must be held. NULL will returned if nothing was found after
872 static struct extent_state *find_first_extent_bit_state(struct extent_io_tree *tree,
875 struct extent_state *state;
878 * This search will find all the extents that end after our range
881 state = tree_search(tree, start);
883 if (state->end >= start && (state->state & bits))
885 state = next_state(state);
891 * Find the first offset in the io tree with one or more @bits set.
893 * Note: If there are multiple bits set in @bits, any of them will match.
895 * Return true if we find something, and update @start_ret and @end_ret.
896 * Return false if we found nothing.
898 bool find_first_extent_bit(struct extent_io_tree *tree, u64 start,
899 u64 *start_ret, u64 *end_ret, u32 bits,
900 struct extent_state **cached_state)
902 struct extent_state *state;
905 spin_lock(&tree->lock);
906 if (cached_state && *cached_state) {
907 state = *cached_state;
908 if (state->end == start - 1 && extent_state_in_tree(state)) {
909 while ((state = next_state(state)) != NULL) {
910 if (state->state & bits)
914 * If we found the next extent state, clear cached_state
915 * so that we can cache the next extent state below and
916 * avoid future calls going over the same extent state
917 * again. If we haven't found any, clear as well since
920 free_extent_state(*cached_state);
921 *cached_state = NULL;
926 free_extent_state(*cached_state);
927 *cached_state = NULL;
930 state = find_first_extent_bit_state(tree, start, bits);
933 cache_state_if_flags(state, cached_state, 0);
934 *start_ret = state->start;
935 *end_ret = state->end;
939 spin_unlock(&tree->lock);
944 * Find a contiguous area of bits
946 * @tree: io tree to check
947 * @start: offset to start the search from
948 * @start_ret: the first offset we found with the bits set
949 * @end_ret: the final contiguous range of the bits that were set
950 * @bits: bits to look for
952 * set_extent_bit and clear_extent_bit can temporarily split contiguous ranges
953 * to set bits appropriately, and then merge them again. During this time it
954 * will drop the tree->lock, so use this helper if you want to find the actual
955 * contiguous area for given bits. We will search to the first bit we find, and
956 * then walk down the tree until we find a non-contiguous area. The area
957 * returned will be the full contiguous area with the bits set.
959 int find_contiguous_extent_bit(struct extent_io_tree *tree, u64 start,
960 u64 *start_ret, u64 *end_ret, u32 bits)
962 struct extent_state *state;
965 ASSERT(!btrfs_fs_incompat(extent_io_tree_to_fs_info(tree), NO_HOLES));
967 spin_lock(&tree->lock);
968 state = find_first_extent_bit_state(tree, start, bits);
970 *start_ret = state->start;
971 *end_ret = state->end;
972 while ((state = next_state(state)) != NULL) {
973 if (state->start > (*end_ret + 1))
975 *end_ret = state->end;
979 spin_unlock(&tree->lock);
984 * Find a contiguous range of bytes in the file marked as delalloc, not more
985 * than 'max_bytes'. start and end are used to return the range,
987 * True is returned if we find something, false if nothing was in the tree.
989 bool btrfs_find_delalloc_range(struct extent_io_tree *tree, u64 *start,
990 u64 *end, u64 max_bytes,
991 struct extent_state **cached_state)
993 struct extent_state *state;
994 u64 cur_start = *start;
998 spin_lock(&tree->lock);
1001 * This search will find all the extents that end after our range
1004 state = tree_search(tree, cur_start);
1011 if (found && (state->start != cur_start ||
1012 (state->state & EXTENT_BOUNDARY))) {
1015 if (!(state->state & EXTENT_DELALLOC)) {
1021 *start = state->start;
1022 *cached_state = state;
1023 refcount_inc(&state->refs);
1027 cur_start = state->end + 1;
1028 total_bytes += state->end - state->start + 1;
1029 if (total_bytes >= max_bytes)
1031 state = next_state(state);
1034 spin_unlock(&tree->lock);
1039 * Set some bits on a range in the tree. This may require allocations or
1040 * sleeping. By default all allocations use GFP_NOFS, use EXTENT_NOWAIT for
1043 * If any of the exclusive bits are set, this will fail with -EEXIST if some
1044 * part of the range already has the desired bits set. The extent_state of the
1045 * existing range is returned in failed_state in this case, and the start of the
1046 * existing range is returned in failed_start. failed_state is used as an
1047 * optimization for wait_extent_bit, failed_start must be used as the source of
1048 * truth as failed_state may have changed since we returned.
1050 * [start, end] is inclusive This takes the tree lock.
1052 static int __set_extent_bit(struct extent_io_tree *tree, u64 start, u64 end,
1053 u32 bits, u64 *failed_start,
1054 struct extent_state **failed_state,
1055 struct extent_state **cached_state,
1056 struct extent_changeset *changeset)
1058 struct extent_state *state;
1059 struct extent_state *prealloc = NULL;
1060 struct rb_node **p = NULL;
1061 struct rb_node *parent = NULL;
1065 u32 exclusive_bits = (bits & EXTENT_LOCKED);
1068 set_gfp_mask_from_bits(&bits, &mask);
1069 btrfs_debug_check_extent_io_range(tree, start, end);
1070 trace_btrfs_set_extent_bit(tree, start, end - start + 1, bits);
1073 ASSERT(failed_start);
1075 ASSERT(failed_start == NULL && failed_state == NULL);
1079 * Don't care for allocation failure here because we might end
1080 * up not needing the pre-allocated extent state at all, which
1081 * is the case if we only have in the tree extent states that
1082 * cover our input range and don't cover too any other range.
1083 * If we end up needing a new extent state we allocate it later.
1085 prealloc = alloc_extent_state(mask);
1088 spin_lock(&tree->lock);
1089 if (cached_state && *cached_state) {
1090 state = *cached_state;
1091 if (state->start <= start && state->end > start &&
1092 extent_state_in_tree(state))
1096 * This search will find all the extents that end after our range
1099 state = tree_search_for_insert(tree, start, &p, &parent);
1101 prealloc = alloc_extent_state_atomic(prealloc);
1104 prealloc->start = start;
1105 prealloc->end = end;
1106 insert_state_fast(tree, prealloc, p, parent, bits, changeset);
1107 cache_state(prealloc, cached_state);
1112 last_start = state->start;
1113 last_end = state->end;
1116 * | ---- desired range ---- |
1119 * Just lock what we found and keep going
1121 if (state->start == start && state->end <= end) {
1122 if (state->state & exclusive_bits) {
1123 *failed_start = state->start;
1124 cache_state(state, failed_state);
1129 set_state_bits(tree, state, bits, changeset);
1130 cache_state(state, cached_state);
1131 merge_state(tree, state);
1132 if (last_end == (u64)-1)
1134 start = last_end + 1;
1135 state = next_state(state);
1136 if (start < end && state && state->start == start &&
1143 * | ---- desired range ---- |
1146 * | ------------- state -------------- |
1148 * We need to split the extent we found, and may flip bits on second
1151 * If the extent we found extends past our range, we just split and
1152 * search again. It'll get split again the next time though.
1154 * If the extent we found is inside our range, we set the desired bit
1157 if (state->start < start) {
1158 if (state->state & exclusive_bits) {
1159 *failed_start = start;
1160 cache_state(state, failed_state);
1166 * If this extent already has all the bits we want set, then
1167 * skip it, not necessary to split it or do anything with it.
1169 if ((state->state & bits) == bits) {
1170 start = state->end + 1;
1171 cache_state(state, cached_state);
1175 prealloc = alloc_extent_state_atomic(prealloc);
1178 err = split_state(tree, state, prealloc, start);
1180 extent_io_tree_panic(tree, state, "split", err);
1185 if (state->end <= end) {
1186 set_state_bits(tree, state, bits, changeset);
1187 cache_state(state, cached_state);
1188 merge_state(tree, state);
1189 if (last_end == (u64)-1)
1191 start = last_end + 1;
1192 state = next_state(state);
1193 if (start < end && state && state->start == start &&
1200 * | ---- desired range ---- |
1201 * | state | or | state |
1203 * There's a hole, we need to insert something in it and ignore the
1206 if (state->start > start) {
1208 struct extent_state *inserted_state;
1210 if (end < last_start)
1213 this_end = last_start - 1;
1215 prealloc = alloc_extent_state_atomic(prealloc);
1220 * Avoid to free 'prealloc' if it can be merged with the later
1223 prealloc->start = start;
1224 prealloc->end = this_end;
1225 inserted_state = insert_state(tree, prealloc, bits, changeset);
1226 if (IS_ERR(inserted_state)) {
1227 err = PTR_ERR(inserted_state);
1228 extent_io_tree_panic(tree, prealloc, "insert", err);
1231 cache_state(inserted_state, cached_state);
1232 if (inserted_state == prealloc)
1234 start = this_end + 1;
1238 * | ---- desired range ---- |
1241 * We need to split the extent, and set the bit on the first half
1243 if (state->start <= end && state->end > end) {
1244 if (state->state & exclusive_bits) {
1245 *failed_start = start;
1246 cache_state(state, failed_state);
1251 prealloc = alloc_extent_state_atomic(prealloc);
1254 err = split_state(tree, state, prealloc, end + 1);
1256 extent_io_tree_panic(tree, state, "split", err);
1258 set_state_bits(tree, prealloc, bits, changeset);
1259 cache_state(prealloc, cached_state);
1260 merge_state(tree, prealloc);
1268 spin_unlock(&tree->lock);
1269 if (gfpflags_allow_blocking(mask))
1274 spin_unlock(&tree->lock);
1276 free_extent_state(prealloc);
1282 int set_extent_bit(struct extent_io_tree *tree, u64 start, u64 end,
1283 u32 bits, struct extent_state **cached_state)
1285 return __set_extent_bit(tree, start, end, bits, NULL, NULL,
1286 cached_state, NULL);
1290 * Convert all bits in a given range from one bit to another
1292 * @tree: the io tree to search
1293 * @start: the start offset in bytes
1294 * @end: the end offset in bytes (inclusive)
1295 * @bits: the bits to set in this range
1296 * @clear_bits: the bits to clear in this range
1297 * @cached_state: state that we're going to cache
1299 * This will go through and set bits for the given range. If any states exist
1300 * already in this range they are set with the given bit and cleared of the
1301 * clear_bits. This is only meant to be used by things that are mergeable, ie.
1302 * converting from say DELALLOC to DIRTY. This is not meant to be used with
1303 * boundary bits like LOCK.
1305 * All allocations are done with GFP_NOFS.
1307 int convert_extent_bit(struct extent_io_tree *tree, u64 start, u64 end,
1308 u32 bits, u32 clear_bits,
1309 struct extent_state **cached_state)
1311 struct extent_state *state;
1312 struct extent_state *prealloc = NULL;
1313 struct rb_node **p = NULL;
1314 struct rb_node *parent = NULL;
1318 bool first_iteration = true;
1320 btrfs_debug_check_extent_io_range(tree, start, end);
1321 trace_btrfs_convert_extent_bit(tree, start, end - start + 1, bits,
1327 * Best effort, don't worry if extent state allocation fails
1328 * here for the first iteration. We might have a cached state
1329 * that matches exactly the target range, in which case no
1330 * extent state allocations are needed. We'll only know this
1331 * after locking the tree.
1333 prealloc = alloc_extent_state(GFP_NOFS);
1334 if (!prealloc && !first_iteration)
1338 spin_lock(&tree->lock);
1339 if (cached_state && *cached_state) {
1340 state = *cached_state;
1341 if (state->start <= start && state->end > start &&
1342 extent_state_in_tree(state))
1347 * This search will find all the extents that end after our range
1350 state = tree_search_for_insert(tree, start, &p, &parent);
1352 prealloc = alloc_extent_state_atomic(prealloc);
1357 prealloc->start = start;
1358 prealloc->end = end;
1359 insert_state_fast(tree, prealloc, p, parent, bits, NULL);
1360 cache_state(prealloc, cached_state);
1365 last_start = state->start;
1366 last_end = state->end;
1369 * | ---- desired range ---- |
1372 * Just lock what we found and keep going.
1374 if (state->start == start && state->end <= end) {
1375 set_state_bits(tree, state, bits, NULL);
1376 cache_state(state, cached_state);
1377 state = clear_state_bit(tree, state, clear_bits, 0, NULL);
1378 if (last_end == (u64)-1)
1380 start = last_end + 1;
1381 if (start < end && state && state->start == start &&
1388 * | ---- desired range ---- |
1391 * | ------------- state -------------- |
1393 * We need to split the extent we found, and may flip bits on second
1396 * If the extent we found extends past our range, we just split and
1397 * search again. It'll get split again the next time though.
1399 * If the extent we found is inside our range, we set the desired bit
1402 if (state->start < start) {
1403 prealloc = alloc_extent_state_atomic(prealloc);
1408 err = split_state(tree, state, prealloc, start);
1410 extent_io_tree_panic(tree, state, "split", err);
1414 if (state->end <= end) {
1415 set_state_bits(tree, state, bits, NULL);
1416 cache_state(state, cached_state);
1417 state = clear_state_bit(tree, state, clear_bits, 0, NULL);
1418 if (last_end == (u64)-1)
1420 start = last_end + 1;
1421 if (start < end && state && state->start == start &&
1428 * | ---- desired range ---- |
1429 * | state | or | state |
1431 * There's a hole, we need to insert something in it and ignore the
1434 if (state->start > start) {
1436 struct extent_state *inserted_state;
1438 if (end < last_start)
1441 this_end = last_start - 1;
1443 prealloc = alloc_extent_state_atomic(prealloc);
1450 * Avoid to free 'prealloc' if it can be merged with the later
1453 prealloc->start = start;
1454 prealloc->end = this_end;
1455 inserted_state = insert_state(tree, prealloc, bits, NULL);
1456 if (IS_ERR(inserted_state)) {
1457 err = PTR_ERR(inserted_state);
1458 extent_io_tree_panic(tree, prealloc, "insert", err);
1460 cache_state(inserted_state, cached_state);
1461 if (inserted_state == prealloc)
1463 start = this_end + 1;
1467 * | ---- desired range ---- |
1470 * We need to split the extent, and set the bit on the first half.
1472 if (state->start <= end && state->end > end) {
1473 prealloc = alloc_extent_state_atomic(prealloc);
1479 err = split_state(tree, state, prealloc, end + 1);
1481 extent_io_tree_panic(tree, state, "split", err);
1483 set_state_bits(tree, prealloc, bits, NULL);
1484 cache_state(prealloc, cached_state);
1485 clear_state_bit(tree, prealloc, clear_bits, 0, NULL);
1493 spin_unlock(&tree->lock);
1495 first_iteration = false;
1499 spin_unlock(&tree->lock);
1501 free_extent_state(prealloc);
1507 * Find the first range that has @bits not set. This range could start before
1510 * @tree: the tree to search
1511 * @start: offset at/after which the found extent should start
1512 * @start_ret: records the beginning of the range
1513 * @end_ret: records the end of the range (inclusive)
1514 * @bits: the set of bits which must be unset
1516 * Since unallocated range is also considered one which doesn't have the bits
1517 * set it's possible that @end_ret contains -1, this happens in case the range
1518 * spans (last_range_end, end of device]. In this case it's up to the caller to
1519 * trim @end_ret to the appropriate size.
1521 void find_first_clear_extent_bit(struct extent_io_tree *tree, u64 start,
1522 u64 *start_ret, u64 *end_ret, u32 bits)
1524 struct extent_state *state;
1525 struct extent_state *prev = NULL, *next = NULL;
1527 spin_lock(&tree->lock);
1529 /* Find first extent with bits cleared */
1531 state = tree_search_prev_next(tree, start, &prev, &next);
1532 if (!state && !next && !prev) {
1534 * Tree is completely empty, send full range and let
1535 * caller deal with it
1540 } else if (!state && !next) {
1542 * We are past the last allocated chunk, set start at
1543 * the end of the last extent.
1545 *start_ret = prev->end + 1;
1548 } else if (!state) {
1553 * At this point 'state' either contains 'start' or start is
1556 if (in_range(start, state->start, state->end - state->start + 1)) {
1557 if (state->state & bits) {
1559 * |--range with bits sets--|
1563 start = state->end + 1;
1566 * 'start' falls within a range that doesn't
1567 * have the bits set, so take its start as the
1568 * beginning of the desired range
1570 * |--range with bits cleared----|
1574 *start_ret = state->start;
1579 * |---prev range---|---hole/unset---|---node range---|
1585 * |---hole/unset--||--first node--|
1590 *start_ret = prev->end + 1;
1598 * Find the longest stretch from start until an entry which has the
1602 if (state->end >= start && !(state->state & bits)) {
1603 *end_ret = state->end;
1605 *end_ret = state->start - 1;
1608 state = next_state(state);
1611 spin_unlock(&tree->lock);
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.
1619 * @start: The start offset of the range. This value is updated to the
1620 * offset of the first byte found with the given bit(s), so it
1621 * can end up being bigger than the initial value.
1622 * @search_end: The end offset (inclusive value) of the search range.
1623 * @max_bytes: The maximum byte count we are interested. The search stops
1624 * once it reaches this count.
1625 * @bits: The bits the range must have in order to be accounted for.
1626 * If multiple bits are set, then only subranges that have all
1627 * the bits set are accounted for.
1628 * @contig: Indicate if we should ignore holes in the range or not. If
1629 * this is true, then stop once we find a hole.
1630 * @cached_state: A cached state to be used across multiple calls to this
1631 * function in order to speedup searches. Use NULL if this is
1632 * called only once or if each call does not start where the
1633 * previous one ended.
1635 * Returns the total number of bytes found within the given range that have
1636 * all given bits set. If the returned number of bytes is greater than zero
1637 * then @start is updated with the offset of the first byte with the bits set.
1639 u64 count_range_bits(struct extent_io_tree *tree,
1640 u64 *start, u64 search_end, u64 max_bytes,
1641 u32 bits, int contig,
1642 struct extent_state **cached_state)
1644 struct extent_state *state = NULL;
1645 struct extent_state *cached;
1646 u64 cur_start = *start;
1647 u64 total_bytes = 0;
1651 if (WARN_ON(search_end < cur_start))
1654 spin_lock(&tree->lock);
1656 if (!cached_state || !*cached_state)
1659 cached = *cached_state;
1661 if (!extent_state_in_tree(cached))
1664 if (cached->start <= cur_start && cur_start <= cached->end) {
1666 } else if (cached->start > cur_start) {
1667 struct extent_state *prev;
1670 * The cached state starts after our search range's start. Check
1671 * if the previous state record starts at or before the range we
1672 * are looking for, and if so, use it - this is a common case
1673 * when there are holes between records in the tree. If there is
1674 * no previous state record, we can start from our cached state.
1676 prev = prev_state(cached);
1679 else if (prev->start <= cur_start && cur_start <= prev->end)
1684 * This search will find all the extents that end after our range
1689 state = tree_search(tree, cur_start);
1692 if (state->start > search_end)
1694 if (contig && found && state->start > last + 1)
1696 if (state->end >= cur_start && (state->state & bits) == bits) {
1697 total_bytes += min(search_end, state->end) + 1 -
1698 max(cur_start, state->start);
1699 if (total_bytes >= max_bytes)
1702 *start = max(cur_start, state->start);
1706 } else if (contig && found) {
1709 state = next_state(state);
1713 free_extent_state(*cached_state);
1714 *cached_state = state;
1716 refcount_inc(&state->refs);
1719 spin_unlock(&tree->lock);
1725 * Check if the single @bit exists in the given range.
1727 bool test_range_bit_exists(struct extent_io_tree *tree, u64 start, u64 end, u32 bit)
1729 struct extent_state *state = NULL;
1730 bool bitset = false;
1732 ASSERT(is_power_of_2(bit));
1734 spin_lock(&tree->lock);
1735 state = tree_search(tree, start);
1736 while (state && start <= end) {
1737 if (state->start > end)
1740 if (state->state & bit) {
1745 /* If state->end is (u64)-1, start will overflow to 0 */
1746 start = state->end + 1;
1747 if (start > end || start == 0)
1749 state = next_state(state);
1751 spin_unlock(&tree->lock);
1756 * Check if the whole range [@start,@end) contains the single @bit set.
1758 bool test_range_bit(struct extent_io_tree *tree, u64 start, u64 end, u32 bit,
1759 struct extent_state *cached)
1761 struct extent_state *state = NULL;
1764 ASSERT(is_power_of_2(bit));
1766 spin_lock(&tree->lock);
1767 if (cached && extent_state_in_tree(cached) && cached->start <= start &&
1768 cached->end > start)
1771 state = tree_search(tree, start);
1772 while (state && start <= end) {
1773 if (state->start > start) {
1778 if (state->start > end)
1781 if ((state->state & bit) == 0) {
1786 if (state->end == (u64)-1)
1790 * Last entry (if state->end is (u64)-1 and overflow happens),
1791 * or next entry starts after the range.
1793 start = state->end + 1;
1794 if (start > end || start == 0)
1796 state = next_state(state);
1799 /* We ran out of states and were still inside of our range. */
1802 spin_unlock(&tree->lock);
1806 /* Wrappers around set/clear extent bit */
1807 int set_record_extent_bits(struct extent_io_tree *tree, u64 start, u64 end,
1808 u32 bits, struct extent_changeset *changeset)
1811 * We don't support EXTENT_LOCKED yet, as current changeset will
1812 * record any bits changed, so for EXTENT_LOCKED case, it will
1813 * either fail with -EEXIST or changeset will record the whole
1816 ASSERT(!(bits & EXTENT_LOCKED));
1818 return __set_extent_bit(tree, start, end, bits, NULL, NULL, NULL, changeset);
1821 int clear_record_extent_bits(struct extent_io_tree *tree, u64 start, u64 end,
1822 u32 bits, struct extent_changeset *changeset)
1825 * Don't support EXTENT_LOCKED case, same reason as
1826 * set_record_extent_bits().
1828 ASSERT(!(bits & EXTENT_LOCKED));
1830 return __clear_extent_bit(tree, start, end, bits, NULL, changeset);
1833 int try_lock_extent(struct extent_io_tree *tree, u64 start, u64 end,
1834 struct extent_state **cached)
1839 err = __set_extent_bit(tree, start, end, EXTENT_LOCKED, &failed_start,
1840 NULL, cached, NULL);
1841 if (err == -EEXIST) {
1842 if (failed_start > start)
1843 clear_extent_bit(tree, start, failed_start - 1,
1844 EXTENT_LOCKED, cached);
1851 * Either insert or lock state struct between start and end use mask to tell
1852 * us if waiting is desired.
1854 int lock_extent(struct extent_io_tree *tree, u64 start, u64 end,
1855 struct extent_state **cached_state)
1857 struct extent_state *failed_state = NULL;
1861 err = __set_extent_bit(tree, start, end, EXTENT_LOCKED, &failed_start,
1862 &failed_state, cached_state, NULL);
1863 while (err == -EEXIST) {
1864 if (failed_start != start)
1865 clear_extent_bit(tree, start, failed_start - 1,
1866 EXTENT_LOCKED, cached_state);
1868 wait_extent_bit(tree, failed_start, end, EXTENT_LOCKED,
1870 err = __set_extent_bit(tree, start, end, EXTENT_LOCKED,
1871 &failed_start, &failed_state,
1872 cached_state, NULL);
1877 void __cold extent_state_free_cachep(void)
1879 btrfs_extent_state_leak_debug_check();
1880 kmem_cache_destroy(extent_state_cache);
1883 int __init extent_state_init_cachep(void)
1885 extent_state_cache = kmem_cache_create("btrfs_extent_state",
1886 sizeof(struct extent_state), 0,
1887 SLAB_MEM_SPREAD, NULL);
1888 if (!extent_state_cache)