183cf709aSJosef Bacik // SPDX-License-Identifier: GPL-2.0
283cf709aSJosef Bacik
383cf709aSJosef Bacik #include <linux/slab.h>
483cf709aSJosef Bacik #include <trace/events/btrfs.h>
59b569ea0SJosef Bacik #include "messages.h"
683cf709aSJosef Bacik #include "ctree.h"
783cf709aSJosef Bacik #include "extent-io-tree.h"
86962541eSJosef Bacik #include "btrfs_inode.h"
938830018SJosef Bacik #include "misc.h"
1083cf709aSJosef Bacik
1183cf709aSJosef Bacik static struct kmem_cache *extent_state_cache;
1283cf709aSJosef Bacik
extent_state_in_tree(const struct extent_state * state)13a4055213SJosef Bacik static inline bool extent_state_in_tree(const struct extent_state *state)
14a4055213SJosef Bacik {
15a4055213SJosef Bacik return !RB_EMPTY_NODE(&state->rb_node);
16a4055213SJosef Bacik }
17a4055213SJosef Bacik
1883cf709aSJosef Bacik #ifdef CONFIG_BTRFS_DEBUG
1983cf709aSJosef Bacik static LIST_HEAD(states);
2083cf709aSJosef Bacik static DEFINE_SPINLOCK(leak_lock);
2183cf709aSJosef Bacik
btrfs_leak_debug_add_state(struct extent_state * state)2283cf709aSJosef Bacik static inline void btrfs_leak_debug_add_state(struct extent_state *state)
2383cf709aSJosef Bacik {
2483cf709aSJosef Bacik unsigned long flags;
2583cf709aSJosef Bacik
2683cf709aSJosef Bacik spin_lock_irqsave(&leak_lock, flags);
2783cf709aSJosef Bacik list_add(&state->leak_list, &states);
2883cf709aSJosef Bacik spin_unlock_irqrestore(&leak_lock, flags);
2983cf709aSJosef Bacik }
3083cf709aSJosef Bacik
btrfs_leak_debug_del_state(struct extent_state * state)3183cf709aSJosef Bacik static inline void btrfs_leak_debug_del_state(struct extent_state *state)
3283cf709aSJosef Bacik {
3383cf709aSJosef Bacik unsigned long flags;
3483cf709aSJosef Bacik
3583cf709aSJosef Bacik spin_lock_irqsave(&leak_lock, flags);
3683cf709aSJosef Bacik list_del(&state->leak_list);
3783cf709aSJosef Bacik spin_unlock_irqrestore(&leak_lock, flags);
3883cf709aSJosef Bacik }
3983cf709aSJosef Bacik
btrfs_extent_state_leak_debug_check(void)4083cf709aSJosef Bacik static inline void btrfs_extent_state_leak_debug_check(void)
4183cf709aSJosef Bacik {
4283cf709aSJosef Bacik struct extent_state *state;
4383cf709aSJosef Bacik
4483cf709aSJosef Bacik while (!list_empty(&states)) {
4583cf709aSJosef Bacik state = list_entry(states.next, struct extent_state, leak_list);
4683cf709aSJosef Bacik pr_err("BTRFS: state leak: start %llu end %llu state %u in tree %d refs %d\n",
4783cf709aSJosef Bacik state->start, state->end, state->state,
4883cf709aSJosef Bacik extent_state_in_tree(state),
4983cf709aSJosef Bacik refcount_read(&state->refs));
5083cf709aSJosef Bacik list_del(&state->leak_list);
5183cf709aSJosef Bacik kmem_cache_free(extent_state_cache, state);
5283cf709aSJosef Bacik }
5383cf709aSJosef Bacik }
546962541eSJosef Bacik
55d8038a1fSJosef Bacik #define btrfs_debug_check_extent_io_range(tree, start, end) \
56d8038a1fSJosef Bacik __btrfs_debug_check_extent_io_range(__func__, (tree), (start), (end))
__btrfs_debug_check_extent_io_range(const char * caller,struct extent_io_tree * tree,u64 start,u64 end)57d8038a1fSJosef Bacik static inline void __btrfs_debug_check_extent_io_range(const char *caller,
58d8038a1fSJosef Bacik struct extent_io_tree *tree,
59d8038a1fSJosef Bacik u64 start, u64 end)
606962541eSJosef Bacik {
610988fc7bSDavid Sterba struct btrfs_inode *inode = tree->inode;
626962541eSJosef Bacik u64 isize;
636962541eSJosef Bacik
6423408d81SJosef Bacik if (!inode)
656962541eSJosef Bacik return;
666962541eSJosef Bacik
670988fc7bSDavid Sterba isize = i_size_read(&inode->vfs_inode);
686962541eSJosef Bacik if (end >= PAGE_SIZE && (end % 2) == 0 && end != isize - 1) {
690988fc7bSDavid Sterba btrfs_debug_rl(inode->root->fs_info,
706962541eSJosef Bacik "%s: ino %llu isize %llu odd range [%llu,%llu]",
710988fc7bSDavid Sterba caller, btrfs_ino(inode), isize, start, end);
726962541eSJosef Bacik }
736962541eSJosef Bacik }
7483cf709aSJosef Bacik #else
7583cf709aSJosef Bacik #define btrfs_leak_debug_add_state(state) do {} while (0)
7683cf709aSJosef Bacik #define btrfs_leak_debug_del_state(state) do {} while (0)
7783cf709aSJosef Bacik #define btrfs_extent_state_leak_debug_check() do {} while (0)
78d8038a1fSJosef Bacik #define btrfs_debug_check_extent_io_range(c, s, e) do {} while (0)
7983cf709aSJosef Bacik #endif
8083cf709aSJosef Bacik
8183cf709aSJosef Bacik /*
8283cf709aSJosef Bacik * For the file_extent_tree, we want to hold the inode lock when we lookup and
8383cf709aSJosef Bacik * update the disk_i_size, but lockdep will complain because our io_tree we hold
8483cf709aSJosef Bacik * the tree lock and get the inode lock when setting delalloc. These two things
8583cf709aSJosef Bacik * are unrelated, so make a class for the file_extent_tree so we don't get the
8683cf709aSJosef Bacik * two locking patterns mixed up.
8783cf709aSJosef Bacik */
8883cf709aSJosef Bacik static struct lock_class_key file_extent_tree_class;
8983cf709aSJosef Bacik
90a4055213SJosef Bacik struct tree_entry {
91a4055213SJosef Bacik u64 start;
92a4055213SJosef Bacik u64 end;
93a4055213SJosef Bacik struct rb_node rb_node;
94a4055213SJosef Bacik };
95a4055213SJosef Bacik
extent_io_tree_init(struct btrfs_fs_info * fs_info,struct extent_io_tree * tree,unsigned int owner)9683cf709aSJosef Bacik void extent_io_tree_init(struct btrfs_fs_info *fs_info,
9735da5a7eSDavid Sterba struct extent_io_tree *tree, unsigned int owner)
9883cf709aSJosef Bacik {
9983cf709aSJosef Bacik tree->fs_info = fs_info;
10083cf709aSJosef Bacik tree->state = RB_ROOT;
10183cf709aSJosef Bacik spin_lock_init(&tree->lock);
1020988fc7bSDavid Sterba tree->inode = NULL;
10383cf709aSJosef Bacik tree->owner = owner;
10483cf709aSJosef Bacik if (owner == IO_TREE_INODE_FILE_EXTENT)
10583cf709aSJosef Bacik lockdep_set_class(&tree->lock, &file_extent_tree_class);
10683cf709aSJosef Bacik }
10783cf709aSJosef Bacik
extent_io_tree_release(struct extent_io_tree * tree)10883cf709aSJosef Bacik void extent_io_tree_release(struct extent_io_tree *tree)
10983cf709aSJosef Bacik {
11083cf709aSJosef Bacik spin_lock(&tree->lock);
11183cf709aSJosef Bacik /*
11283cf709aSJosef Bacik * Do a single barrier for the waitqueue_active check here, the state
11383cf709aSJosef Bacik * of the waitqueue should not change once extent_io_tree_release is
11483cf709aSJosef Bacik * called.
11583cf709aSJosef Bacik */
11683cf709aSJosef Bacik smp_mb();
11783cf709aSJosef Bacik while (!RB_EMPTY_ROOT(&tree->state)) {
11883cf709aSJosef Bacik struct rb_node *node;
11983cf709aSJosef Bacik struct extent_state *state;
12083cf709aSJosef Bacik
12183cf709aSJosef Bacik node = rb_first(&tree->state);
12283cf709aSJosef Bacik state = rb_entry(node, struct extent_state, rb_node);
12383cf709aSJosef Bacik rb_erase(&state->rb_node, &tree->state);
12483cf709aSJosef Bacik RB_CLEAR_NODE(&state->rb_node);
12583cf709aSJosef Bacik /*
12683cf709aSJosef Bacik * btree io trees aren't supposed to have tasks waiting for
12783cf709aSJosef Bacik * changes in the flags of extent states ever.
12883cf709aSJosef Bacik */
12983cf709aSJosef Bacik ASSERT(!waitqueue_active(&state->wq));
13083cf709aSJosef Bacik free_extent_state(state);
13183cf709aSJosef Bacik
13283cf709aSJosef Bacik cond_resched_lock(&tree->lock);
13383cf709aSJosef Bacik }
13483cf709aSJosef Bacik spin_unlock(&tree->lock);
13583cf709aSJosef Bacik }
13683cf709aSJosef Bacik
alloc_extent_state(gfp_t mask)137a4055213SJosef Bacik static struct extent_state *alloc_extent_state(gfp_t mask)
13883cf709aSJosef Bacik {
13983cf709aSJosef Bacik struct extent_state *state;
14083cf709aSJosef Bacik
14183cf709aSJosef Bacik /*
14283cf709aSJosef Bacik * The given mask might be not appropriate for the slab allocator,
14383cf709aSJosef Bacik * drop the unsupported bits
14483cf709aSJosef Bacik */
14583cf709aSJosef Bacik mask &= ~(__GFP_DMA32|__GFP_HIGHMEM);
14683cf709aSJosef Bacik state = kmem_cache_alloc(extent_state_cache, mask);
14783cf709aSJosef Bacik if (!state)
14883cf709aSJosef Bacik return state;
14983cf709aSJosef Bacik state->state = 0;
15083cf709aSJosef Bacik RB_CLEAR_NODE(&state->rb_node);
15183cf709aSJosef Bacik btrfs_leak_debug_add_state(state);
15283cf709aSJosef Bacik refcount_set(&state->refs, 1);
15383cf709aSJosef Bacik init_waitqueue_head(&state->wq);
15483cf709aSJosef Bacik trace_alloc_extent_state(state, mask, _RET_IP_);
15583cf709aSJosef Bacik return state;
15683cf709aSJosef Bacik }
15783cf709aSJosef Bacik
alloc_extent_state_atomic(struct extent_state * prealloc)158a4055213SJosef Bacik static struct extent_state *alloc_extent_state_atomic(struct extent_state *prealloc)
15983cf709aSJosef Bacik {
16083cf709aSJosef Bacik if (!prealloc)
16183cf709aSJosef Bacik prealloc = alloc_extent_state(GFP_ATOMIC);
16283cf709aSJosef Bacik
16383cf709aSJosef Bacik return prealloc;
16483cf709aSJosef Bacik }
16583cf709aSJosef Bacik
free_extent_state(struct extent_state * state)16683cf709aSJosef Bacik void free_extent_state(struct extent_state *state)
16783cf709aSJosef Bacik {
16883cf709aSJosef Bacik if (!state)
16983cf709aSJosef Bacik return;
17083cf709aSJosef Bacik if (refcount_dec_and_test(&state->refs)) {
17183cf709aSJosef Bacik WARN_ON(extent_state_in_tree(state));
17283cf709aSJosef Bacik btrfs_leak_debug_del_state(state);
17383cf709aSJosef Bacik trace_free_extent_state(state, _RET_IP_);
17483cf709aSJosef Bacik kmem_cache_free(extent_state_cache, state);
17583cf709aSJosef Bacik }
17683cf709aSJosef Bacik }
17783cf709aSJosef Bacik
add_extent_changeset(struct extent_state * state,u32 bits,struct extent_changeset * changeset,int set)17804eba893SJosef Bacik static int add_extent_changeset(struct extent_state *state, u32 bits,
17904eba893SJosef Bacik struct extent_changeset *changeset,
18004eba893SJosef Bacik int set)
18104eba893SJosef Bacik {
18204eba893SJosef Bacik int ret;
18304eba893SJosef Bacik
18404eba893SJosef Bacik if (!changeset)
18504eba893SJosef Bacik return 0;
18604eba893SJosef Bacik if (set && (state->state & bits) == bits)
18704eba893SJosef Bacik return 0;
18804eba893SJosef Bacik if (!set && (state->state & bits) == 0)
18904eba893SJosef Bacik return 0;
19004eba893SJosef Bacik changeset->bytes_changed += state->end - state->start + 1;
19104eba893SJosef Bacik ret = ulist_add(&changeset->range_changed, state->start, state->end,
19204eba893SJosef Bacik GFP_ATOMIC);
19304eba893SJosef Bacik return ret;
19404eba893SJosef Bacik }
19504eba893SJosef Bacik
next_state(struct extent_state * state)196a4055213SJosef Bacik static inline struct extent_state *next_state(struct extent_state *state)
197a4055213SJosef Bacik {
198a4055213SJosef Bacik struct rb_node *next = rb_next(&state->rb_node);
199a4055213SJosef Bacik
200a4055213SJosef Bacik if (next)
201a4055213SJosef Bacik return rb_entry(next, struct extent_state, rb_node);
202a4055213SJosef Bacik else
203a4055213SJosef Bacik return NULL;
204a4055213SJosef Bacik }
205a4055213SJosef Bacik
prev_state(struct extent_state * state)20643b068caSJosef Bacik static inline struct extent_state *prev_state(struct extent_state *state)
20743b068caSJosef Bacik {
20843b068caSJosef Bacik struct rb_node *next = rb_prev(&state->rb_node);
20943b068caSJosef Bacik
21043b068caSJosef Bacik if (next)
21143b068caSJosef Bacik return rb_entry(next, struct extent_state, rb_node);
21243b068caSJosef Bacik else
21343b068caSJosef Bacik return NULL;
21443b068caSJosef Bacik }
21543b068caSJosef Bacik
21691af24e4SJosef Bacik /*
21791af24e4SJosef Bacik * Search @tree for an entry that contains @offset. Such entry would have
21891af24e4SJosef Bacik * entry->start <= offset && entry->end >= offset.
21991af24e4SJosef Bacik *
22091af24e4SJosef Bacik * @tree: the tree to search
22191af24e4SJosef Bacik * @offset: offset that should fall within an entry in @tree
22291af24e4SJosef Bacik * @node_ret: pointer where new node should be anchored (used when inserting an
22391af24e4SJosef Bacik * entry in the tree)
22491af24e4SJosef Bacik * @parent_ret: points to entry which would have been the parent of the entry,
22591af24e4SJosef Bacik * containing @offset
22691af24e4SJosef Bacik *
22791af24e4SJosef Bacik * Return a pointer to the entry that contains @offset byte address and don't change
22891af24e4SJosef Bacik * @node_ret and @parent_ret.
22991af24e4SJosef Bacik *
23091af24e4SJosef Bacik * If no such entry exists, return pointer to entry that ends before @offset
23191af24e4SJosef Bacik * and fill parameters @node_ret and @parent_ret, ie. does not return NULL.
23291af24e4SJosef Bacik */
tree_search_for_insert(struct extent_io_tree * tree,u64 offset,struct rb_node *** node_ret,struct rb_node ** parent_ret)233e349fd3bSJosef Bacik static inline struct extent_state *tree_search_for_insert(struct extent_io_tree *tree,
234a4055213SJosef Bacik u64 offset,
23591af24e4SJosef Bacik struct rb_node ***node_ret,
23691af24e4SJosef Bacik struct rb_node **parent_ret)
23791af24e4SJosef Bacik {
23891af24e4SJosef Bacik struct rb_root *root = &tree->state;
23991af24e4SJosef Bacik struct rb_node **node = &root->rb_node;
24091af24e4SJosef Bacik struct rb_node *prev = NULL;
241e349fd3bSJosef Bacik struct extent_state *entry = NULL;
24291af24e4SJosef Bacik
24391af24e4SJosef Bacik while (*node) {
24491af24e4SJosef Bacik prev = *node;
245071d19f5SJosef Bacik entry = rb_entry(prev, struct extent_state, rb_node);
24691af24e4SJosef Bacik
24791af24e4SJosef Bacik if (offset < entry->start)
24891af24e4SJosef Bacik node = &(*node)->rb_left;
24991af24e4SJosef Bacik else if (offset > entry->end)
25091af24e4SJosef Bacik node = &(*node)->rb_right;
25191af24e4SJosef Bacik else
252e349fd3bSJosef Bacik return entry;
25391af24e4SJosef Bacik }
25491af24e4SJosef Bacik
25591af24e4SJosef Bacik if (node_ret)
25691af24e4SJosef Bacik *node_ret = node;
25791af24e4SJosef Bacik if (parent_ret)
25891af24e4SJosef Bacik *parent_ret = prev;
25991af24e4SJosef Bacik
26091af24e4SJosef Bacik /* Search neighbors until we find the first one past the end */
261e349fd3bSJosef Bacik while (entry && offset > entry->end)
262e349fd3bSJosef Bacik entry = next_state(entry);
26391af24e4SJosef Bacik
264e349fd3bSJosef Bacik return entry;
26591af24e4SJosef Bacik }
26691af24e4SJosef Bacik
26791af24e4SJosef Bacik /*
26891af24e4SJosef Bacik * Search offset in the tree or fill neighbor rbtree node pointers.
26991af24e4SJosef Bacik *
27091af24e4SJosef Bacik * @tree: the tree to search
27191af24e4SJosef Bacik * @offset: offset that should fall within an entry in @tree
27291af24e4SJosef Bacik * @next_ret: pointer to the first entry whose range ends after @offset
27391af24e4SJosef Bacik * @prev_ret: pointer to the first entry whose range begins before @offset
27491af24e4SJosef Bacik *
27591af24e4SJosef Bacik * Return a pointer to the entry that contains @offset byte address. If no
27691af24e4SJosef Bacik * such entry exists, then return NULL and fill @prev_ret and @next_ret.
27791af24e4SJosef Bacik * Otherwise return the found entry and other pointers are left untouched.
27891af24e4SJosef Bacik */
tree_search_prev_next(struct extent_io_tree * tree,u64 offset,struct extent_state ** prev_ret,struct extent_state ** next_ret)27943b068caSJosef Bacik static struct extent_state *tree_search_prev_next(struct extent_io_tree *tree,
280a4055213SJosef Bacik u64 offset,
28143b068caSJosef Bacik struct extent_state **prev_ret,
28243b068caSJosef Bacik struct extent_state **next_ret)
28391af24e4SJosef Bacik {
28491af24e4SJosef Bacik struct rb_root *root = &tree->state;
28591af24e4SJosef Bacik struct rb_node **node = &root->rb_node;
28643b068caSJosef Bacik struct extent_state *orig_prev;
28743b068caSJosef Bacik struct extent_state *entry = NULL;
28891af24e4SJosef Bacik
28991af24e4SJosef Bacik ASSERT(prev_ret);
29091af24e4SJosef Bacik ASSERT(next_ret);
29191af24e4SJosef Bacik
29291af24e4SJosef Bacik while (*node) {
29343b068caSJosef Bacik entry = rb_entry(*node, struct extent_state, rb_node);
29491af24e4SJosef Bacik
29591af24e4SJosef Bacik if (offset < entry->start)
29691af24e4SJosef Bacik node = &(*node)->rb_left;
29791af24e4SJosef Bacik else if (offset > entry->end)
29891af24e4SJosef Bacik node = &(*node)->rb_right;
29991af24e4SJosef Bacik else
30043b068caSJosef Bacik return entry;
30191af24e4SJosef Bacik }
30291af24e4SJosef Bacik
30343b068caSJosef Bacik orig_prev = entry;
30443b068caSJosef Bacik while (entry && offset > entry->end)
30543b068caSJosef Bacik entry = next_state(entry);
30643b068caSJosef Bacik *next_ret = entry;
30743b068caSJosef Bacik entry = orig_prev;
30891af24e4SJosef Bacik
30943b068caSJosef Bacik while (entry && offset < entry->start)
31043b068caSJosef Bacik entry = prev_state(entry);
31143b068caSJosef Bacik *prev_ret = entry;
31291af24e4SJosef Bacik
31391af24e4SJosef Bacik return NULL;
31491af24e4SJosef Bacik }
31591af24e4SJosef Bacik
31604eba893SJosef Bacik /*
317e3974c66SJosef Bacik * Inexact rb-tree search, return the next entry if @offset is not found
318e3974c66SJosef Bacik */
tree_search(struct extent_io_tree * tree,u64 offset)319aa852dabSJosef Bacik static inline struct extent_state *tree_search(struct extent_io_tree *tree, u64 offset)
320e3974c66SJosef Bacik {
321e349fd3bSJosef Bacik return tree_search_for_insert(tree, offset, NULL, NULL);
322e3974c66SJosef Bacik }
323e3974c66SJosef Bacik
extent_io_tree_panic(struct extent_io_tree * tree,int err)324e3974c66SJosef Bacik static void extent_io_tree_panic(struct extent_io_tree *tree, int err)
325e3974c66SJosef Bacik {
326e3974c66SJosef Bacik btrfs_panic(tree->fs_info, err,
327e3974c66SJosef Bacik "locking error: extent tree was modified by another thread while locked");
328e3974c66SJosef Bacik }
329e3974c66SJosef Bacik
330e3974c66SJosef Bacik /*
33104eba893SJosef Bacik * Utility function to look for merge candidates inside a given range. Any
33204eba893SJosef Bacik * extents with matching state are merged together into a single extent in the
33304eba893SJosef Bacik * tree. Extents with EXTENT_IO in their state field are not merged because
33404eba893SJosef Bacik * the end_io handlers need to be able to do operations on them without
33504eba893SJosef Bacik * sleeping (or doing allocations/splits).
33604eba893SJosef Bacik *
33704eba893SJosef Bacik * This should be called with the tree lock held.
33804eba893SJosef Bacik */
merge_state(struct extent_io_tree * tree,struct extent_state * state)339a4055213SJosef Bacik static void merge_state(struct extent_io_tree *tree, struct extent_state *state)
34004eba893SJosef Bacik {
34104eba893SJosef Bacik struct extent_state *other;
34204eba893SJosef Bacik
34304eba893SJosef Bacik if (state->state & (EXTENT_LOCKED | EXTENT_BOUNDARY))
34404eba893SJosef Bacik return;
34504eba893SJosef Bacik
346e63b81aeSJosef Bacik other = prev_state(state);
347e63b81aeSJosef Bacik if (other && other->end == state->start - 1 &&
34804eba893SJosef Bacik other->state == state->state) {
3490988fc7bSDavid Sterba if (tree->inode)
3502454151cSDavid Sterba btrfs_merge_delalloc_extent(tree->inode, state, other);
35104eba893SJosef Bacik state->start = other->start;
35204eba893SJosef Bacik rb_erase(&other->rb_node, &tree->state);
35304eba893SJosef Bacik RB_CLEAR_NODE(&other->rb_node);
35404eba893SJosef Bacik free_extent_state(other);
35504eba893SJosef Bacik }
356e63b81aeSJosef Bacik other = next_state(state);
357e63b81aeSJosef Bacik if (other && other->start == state->end + 1 &&
35804eba893SJosef Bacik other->state == state->state) {
3590988fc7bSDavid Sterba if (tree->inode)
3602454151cSDavid Sterba btrfs_merge_delalloc_extent(tree->inode, state, other);
36104eba893SJosef Bacik state->end = other->end;
36204eba893SJosef Bacik rb_erase(&other->rb_node, &tree->state);
36304eba893SJosef Bacik RB_CLEAR_NODE(&other->rb_node);
36404eba893SJosef Bacik free_extent_state(other);
36504eba893SJosef Bacik }
36604eba893SJosef Bacik }
36704eba893SJosef Bacik
set_state_bits(struct extent_io_tree * tree,struct extent_state * state,u32 bits,struct extent_changeset * changeset)368a4055213SJosef Bacik static void set_state_bits(struct extent_io_tree *tree,
369a4055213SJosef Bacik struct extent_state *state,
37004eba893SJosef Bacik u32 bits, struct extent_changeset *changeset)
37104eba893SJosef Bacik {
37204eba893SJosef Bacik u32 bits_to_set = bits & ~EXTENT_CTLBITS;
37304eba893SJosef Bacik int ret;
37404eba893SJosef Bacik
3750988fc7bSDavid Sterba if (tree->inode)
3764c5d166fSDavid Sterba btrfs_set_delalloc_extent(tree->inode, state, bits);
37704eba893SJosef Bacik
37804eba893SJosef Bacik ret = add_extent_changeset(state, bits_to_set, changeset, 1);
37904eba893SJosef Bacik BUG_ON(ret < 0);
38004eba893SJosef Bacik state->state |= bits_to_set;
38104eba893SJosef Bacik }
38204eba893SJosef Bacik
38304eba893SJosef Bacik /*
38404eba893SJosef Bacik * Insert an extent_state struct into the tree. 'bits' are set on the
38504eba893SJosef Bacik * struct before it is inserted.
38604eba893SJosef Bacik *
38704eba893SJosef Bacik * This may return -EEXIST if the extent is already there, in which case the
38804eba893SJosef Bacik * state struct is freed.
38904eba893SJosef Bacik *
39004eba893SJosef Bacik * The tree lock is not taken internally. This is a utility function and
39104eba893SJosef Bacik * probably isn't what you want to call (see set/clear_extent_bit).
39204eba893SJosef Bacik */
insert_state(struct extent_io_tree * tree,struct extent_state * state,u32 bits,struct extent_changeset * changeset)393a4055213SJosef Bacik static int insert_state(struct extent_io_tree *tree,
394a4055213SJosef Bacik struct extent_state *state,
39504eba893SJosef Bacik u32 bits, struct extent_changeset *changeset)
39604eba893SJosef Bacik {
39704eba893SJosef Bacik struct rb_node **node;
398d7c9e1beSJosef Bacik struct rb_node *parent = NULL;
39904eba893SJosef Bacik const u64 end = state->end;
40004eba893SJosef Bacik
40104eba893SJosef Bacik set_state_bits(tree, state, bits, changeset);
40204eba893SJosef Bacik
40304eba893SJosef Bacik node = &tree->state.rb_node;
40404eba893SJosef Bacik while (*node) {
405071d19f5SJosef Bacik struct extent_state *entry;
40604eba893SJosef Bacik
40704eba893SJosef Bacik parent = *node;
408071d19f5SJosef Bacik entry = rb_entry(parent, struct extent_state, rb_node);
40904eba893SJosef Bacik
41004eba893SJosef Bacik if (end < entry->start) {
41104eba893SJosef Bacik node = &(*node)->rb_left;
41204eba893SJosef Bacik } else if (end > entry->end) {
41304eba893SJosef Bacik node = &(*node)->rb_right;
41404eba893SJosef Bacik } else {
41504eba893SJosef Bacik btrfs_err(tree->fs_info,
41604eba893SJosef Bacik "found node %llu %llu on insert of %llu %llu",
41704eba893SJosef Bacik entry->start, entry->end, state->start, end);
41804eba893SJosef Bacik return -EEXIST;
41904eba893SJosef Bacik }
42004eba893SJosef Bacik }
42104eba893SJosef Bacik
42204eba893SJosef Bacik rb_link_node(&state->rb_node, parent, node);
42304eba893SJosef Bacik rb_insert_color(&state->rb_node, &tree->state);
42404eba893SJosef Bacik
42504eba893SJosef Bacik merge_state(tree, state);
42604eba893SJosef Bacik return 0;
42704eba893SJosef Bacik }
42804eba893SJosef Bacik
42904eba893SJosef Bacik /*
43004eba893SJosef Bacik * Insert state to @tree to the location given by @node and @parent.
43104eba893SJosef Bacik */
insert_state_fast(struct extent_io_tree * tree,struct extent_state * state,struct rb_node ** node,struct rb_node * parent,unsigned bits,struct extent_changeset * changeset)432a4055213SJosef Bacik static void insert_state_fast(struct extent_io_tree *tree,
433a4055213SJosef Bacik struct extent_state *state, struct rb_node **node,
434a4055213SJosef Bacik struct rb_node *parent, unsigned bits,
435a4055213SJosef Bacik struct extent_changeset *changeset)
43604eba893SJosef Bacik {
43704eba893SJosef Bacik set_state_bits(tree, state, bits, changeset);
43804eba893SJosef Bacik rb_link_node(&state->rb_node, parent, node);
43904eba893SJosef Bacik rb_insert_color(&state->rb_node, &tree->state);
44004eba893SJosef Bacik merge_state(tree, state);
44104eba893SJosef Bacik }
44204eba893SJosef Bacik
44304eba893SJosef Bacik /*
44404eba893SJosef Bacik * Split a given extent state struct in two, inserting the preallocated
44504eba893SJosef Bacik * struct 'prealloc' as the newly created second half. 'split' indicates an
44604eba893SJosef Bacik * offset inside 'orig' where it should be split.
44704eba893SJosef Bacik *
44804eba893SJosef Bacik * Before calling,
44904eba893SJosef Bacik * the tree has 'orig' at [orig->start, orig->end]. After calling, there
45004eba893SJosef Bacik * are two extent state structs in the tree:
45104eba893SJosef Bacik * prealloc: [orig->start, split - 1]
45204eba893SJosef Bacik * orig: [ split, orig->end ]
45304eba893SJosef Bacik *
45404eba893SJosef Bacik * The tree locks are not taken by this function. They need to be held
45504eba893SJosef Bacik * by the caller.
45604eba893SJosef Bacik */
split_state(struct extent_io_tree * tree,struct extent_state * orig,struct extent_state * prealloc,u64 split)457a4055213SJosef Bacik static int split_state(struct extent_io_tree *tree, struct extent_state *orig,
45804eba893SJosef Bacik struct extent_state *prealloc, u64 split)
45904eba893SJosef Bacik {
46004eba893SJosef Bacik struct rb_node *parent = NULL;
46104eba893SJosef Bacik struct rb_node **node;
46204eba893SJosef Bacik
4630988fc7bSDavid Sterba if (tree->inode)
46462798a49SDavid Sterba btrfs_split_delalloc_extent(tree->inode, orig, split);
46504eba893SJosef Bacik
46604eba893SJosef Bacik prealloc->start = orig->start;
46704eba893SJosef Bacik prealloc->end = split - 1;
46804eba893SJosef Bacik prealloc->state = orig->state;
46904eba893SJosef Bacik orig->start = split;
47004eba893SJosef Bacik
47104eba893SJosef Bacik parent = &orig->rb_node;
47204eba893SJosef Bacik node = &parent;
47304eba893SJosef Bacik while (*node) {
474071d19f5SJosef Bacik struct extent_state *entry;
47504eba893SJosef Bacik
47604eba893SJosef Bacik parent = *node;
477071d19f5SJosef Bacik entry = rb_entry(parent, struct extent_state, rb_node);
47804eba893SJosef Bacik
47904eba893SJosef Bacik if (prealloc->end < entry->start) {
48004eba893SJosef Bacik node = &(*node)->rb_left;
48104eba893SJosef Bacik } else if (prealloc->end > entry->end) {
48204eba893SJosef Bacik node = &(*node)->rb_right;
48304eba893SJosef Bacik } else {
48404eba893SJosef Bacik free_extent_state(prealloc);
48504eba893SJosef Bacik return -EEXIST;
48604eba893SJosef Bacik }
48704eba893SJosef Bacik }
48804eba893SJosef Bacik
48904eba893SJosef Bacik rb_link_node(&prealloc->rb_node, parent, node);
49004eba893SJosef Bacik rb_insert_color(&prealloc->rb_node, &tree->state);
49104eba893SJosef Bacik
49204eba893SJosef Bacik return 0;
49304eba893SJosef Bacik }
49404eba893SJosef Bacik
49504eba893SJosef Bacik /*
49604eba893SJosef Bacik * Utility function to clear some bits in an extent state struct. It will
49704eba893SJosef Bacik * optionally wake up anyone waiting on this state (wake == 1).
49804eba893SJosef Bacik *
49904eba893SJosef Bacik * If no bits are set on the state struct after clearing things, the
50004eba893SJosef Bacik * struct is freed and removed from the tree
50104eba893SJosef Bacik */
clear_state_bit(struct extent_io_tree * tree,struct extent_state * state,u32 bits,int wake,struct extent_changeset * changeset)502a4055213SJosef Bacik static struct extent_state *clear_state_bit(struct extent_io_tree *tree,
503a4055213SJosef Bacik struct extent_state *state,
504a4055213SJosef Bacik u32 bits, int wake,
50504eba893SJosef Bacik struct extent_changeset *changeset)
50604eba893SJosef Bacik {
50704eba893SJosef Bacik struct extent_state *next;
50804eba893SJosef Bacik u32 bits_to_clear = bits & ~EXTENT_CTLBITS;
50904eba893SJosef Bacik int ret;
51004eba893SJosef Bacik
5110988fc7bSDavid Sterba if (tree->inode)
512bd54766eSDavid Sterba btrfs_clear_delalloc_extent(tree->inode, state, bits);
51304eba893SJosef Bacik
51404eba893SJosef Bacik ret = add_extent_changeset(state, bits_to_clear, changeset, 0);
51504eba893SJosef Bacik BUG_ON(ret < 0);
51604eba893SJosef Bacik state->state &= ~bits_to_clear;
51704eba893SJosef Bacik if (wake)
51804eba893SJosef Bacik wake_up(&state->wq);
51904eba893SJosef Bacik if (state->state == 0) {
52004eba893SJosef Bacik next = next_state(state);
52104eba893SJosef Bacik if (extent_state_in_tree(state)) {
52204eba893SJosef Bacik rb_erase(&state->rb_node, &tree->state);
52304eba893SJosef Bacik RB_CLEAR_NODE(&state->rb_node);
52404eba893SJosef Bacik free_extent_state(state);
52504eba893SJosef Bacik } else {
52604eba893SJosef Bacik WARN_ON(1);
52704eba893SJosef Bacik }
52804eba893SJosef Bacik } else {
52904eba893SJosef Bacik merge_state(tree, state);
53004eba893SJosef Bacik next = next_state(state);
53104eba893SJosef Bacik }
53204eba893SJosef Bacik return next;
53304eba893SJosef Bacik }
53404eba893SJosef Bacik
53538830018SJosef Bacik /*
53662bc6047SDavid Sterba * Detect if extent bits request NOWAIT semantics and set the gfp mask accordingly,
53762bc6047SDavid Sterba * unset the EXTENT_NOWAIT bit.
53862bc6047SDavid Sterba */
set_gfp_mask_from_bits(u32 * bits,gfp_t * mask)53962bc6047SDavid Sterba static void set_gfp_mask_from_bits(u32 *bits, gfp_t *mask)
54062bc6047SDavid Sterba {
54162bc6047SDavid Sterba *mask = (*bits & EXTENT_NOWAIT ? GFP_NOWAIT : GFP_NOFS);
54262bc6047SDavid Sterba *bits &= EXTENT_NOWAIT - 1;
54362bc6047SDavid Sterba }
54462bc6047SDavid Sterba
54562bc6047SDavid Sterba /*
546e3974c66SJosef Bacik * Clear some bits on a range in the tree. This may require splitting or
547e3974c66SJosef Bacik * inserting elements in the tree, so the gfp mask is used to indicate which
548e3974c66SJosef Bacik * allocations or sleeping are allowed.
549e3974c66SJosef Bacik *
550e3974c66SJosef Bacik * Pass 'wake' == 1 to kick any sleepers, and 'delete' == 1 to remove the given
551e3974c66SJosef Bacik * range from the tree regardless of state (ie for truncate).
552e3974c66SJosef Bacik *
553e3974c66SJosef Bacik * The range [start, end] is inclusive.
554e3974c66SJosef Bacik *
555e3974c66SJosef Bacik * This takes the tree lock, and returns 0 on success and < 0 on error.
556e3974c66SJosef Bacik */
__clear_extent_bit(struct extent_io_tree * tree,u64 start,u64 end,u32 bits,struct extent_state ** cached_state,struct extent_changeset * changeset)557e3974c66SJosef Bacik int __clear_extent_bit(struct extent_io_tree *tree, u64 start, u64 end,
558bd015294SJosef Bacik u32 bits, struct extent_state **cached_state,
5591d126800SDavid Sterba struct extent_changeset *changeset)
560e3974c66SJosef Bacik {
561e3974c66SJosef Bacik struct extent_state *state;
562e3974c66SJosef Bacik struct extent_state *cached;
563e3974c66SJosef Bacik struct extent_state *prealloc = NULL;
564e3974c66SJosef Bacik u64 last_end;
565e3974c66SJosef Bacik int err;
566e3974c66SJosef Bacik int clear = 0;
567bd015294SJosef Bacik int wake;
568bd015294SJosef Bacik int delete = (bits & EXTENT_CLEAR_ALL_BITS);
5691d126800SDavid Sterba gfp_t mask;
570e3974c66SJosef Bacik
57162bc6047SDavid Sterba set_gfp_mask_from_bits(&bits, &mask);
572e3974c66SJosef Bacik btrfs_debug_check_extent_io_range(tree, start, end);
573e3974c66SJosef Bacik trace_btrfs_clear_extent_bit(tree, start, end - start + 1, bits);
574e3974c66SJosef Bacik
575e3974c66SJosef Bacik if (delete)
576e3974c66SJosef Bacik bits |= ~EXTENT_CTLBITS;
577e3974c66SJosef Bacik
578bd015294SJosef Bacik if (bits & EXTENT_DELALLOC)
579bd015294SJosef Bacik bits |= EXTENT_NORESERVE;
580bd015294SJosef Bacik
581bd015294SJosef Bacik wake = (bits & EXTENT_LOCKED) ? 1 : 0;
582e3974c66SJosef Bacik if (bits & (EXTENT_LOCKED | EXTENT_BOUNDARY))
583e3974c66SJosef Bacik clear = 1;
584e3974c66SJosef Bacik again:
5855a75034eSJosef Bacik if (!prealloc) {
586e3974c66SJosef Bacik /*
587e3974c66SJosef Bacik * Don't care for allocation failure here because we might end
588e3974c66SJosef Bacik * up not needing the pre-allocated extent state at all, which
589e3974c66SJosef Bacik * is the case if we only have in the tree extent states that
590e3974c66SJosef Bacik * cover our input range and don't cover too any other range.
591e3974c66SJosef Bacik * If we end up needing a new extent state we allocate it later.
592e3974c66SJosef Bacik */
593e3974c66SJosef Bacik prealloc = alloc_extent_state(mask);
594e3974c66SJosef Bacik }
595e3974c66SJosef Bacik
596e3974c66SJosef Bacik spin_lock(&tree->lock);
597e3974c66SJosef Bacik if (cached_state) {
598e3974c66SJosef Bacik cached = *cached_state;
599e3974c66SJosef Bacik
600e3974c66SJosef Bacik if (clear) {
601e3974c66SJosef Bacik *cached_state = NULL;
602e3974c66SJosef Bacik cached_state = NULL;
603e3974c66SJosef Bacik }
604e3974c66SJosef Bacik
605e3974c66SJosef Bacik if (cached && extent_state_in_tree(cached) &&
606e3974c66SJosef Bacik cached->start <= start && cached->end > start) {
607e3974c66SJosef Bacik if (clear)
608e3974c66SJosef Bacik refcount_dec(&cached->refs);
609e3974c66SJosef Bacik state = cached;
610e3974c66SJosef Bacik goto hit_next;
611e3974c66SJosef Bacik }
612e3974c66SJosef Bacik if (clear)
613e3974c66SJosef Bacik free_extent_state(cached);
614e3974c66SJosef Bacik }
615e3974c66SJosef Bacik
616e3974c66SJosef Bacik /* This search will find the extents that end after our range starts. */
617aa852dabSJosef Bacik state = tree_search(tree, start);
618aa852dabSJosef Bacik if (!state)
619e3974c66SJosef Bacik goto out;
620e3974c66SJosef Bacik hit_next:
621e3974c66SJosef Bacik if (state->start > end)
622e3974c66SJosef Bacik goto out;
623e3974c66SJosef Bacik WARN_ON(state->end < start);
624e3974c66SJosef Bacik last_end = state->end;
625e3974c66SJosef Bacik
626e3974c66SJosef Bacik /* The state doesn't have the wanted bits, go ahead. */
627e3974c66SJosef Bacik if (!(state->state & bits)) {
628e3974c66SJosef Bacik state = next_state(state);
629e3974c66SJosef Bacik goto next;
630e3974c66SJosef Bacik }
631e3974c66SJosef Bacik
632e3974c66SJosef Bacik /*
633e3974c66SJosef Bacik * | ---- desired range ---- |
634e3974c66SJosef Bacik * | state | or
635e3974c66SJosef Bacik * | ------------- state -------------- |
636e3974c66SJosef Bacik *
637e3974c66SJosef Bacik * We need to split the extent we found, and may flip bits on second
638e3974c66SJosef Bacik * half.
639e3974c66SJosef Bacik *
640e3974c66SJosef Bacik * If the extent we found extends past our range, we just split and
641e3974c66SJosef Bacik * search again. It'll get split again the next time though.
642e3974c66SJosef Bacik *
643e3974c66SJosef Bacik * If the extent we found is inside our range, we clear the desired bit
644e3974c66SJosef Bacik * on it.
645e3974c66SJosef Bacik */
646e3974c66SJosef Bacik
647e3974c66SJosef Bacik if (state->start < start) {
648e3974c66SJosef Bacik prealloc = alloc_extent_state_atomic(prealloc);
6495a75034eSJosef Bacik if (!prealloc)
6505a75034eSJosef Bacik goto search_again;
651e3974c66SJosef Bacik err = split_state(tree, state, prealloc, start);
652e3974c66SJosef Bacik if (err)
653e3974c66SJosef Bacik extent_io_tree_panic(tree, err);
654e3974c66SJosef Bacik
655e3974c66SJosef Bacik prealloc = NULL;
656e3974c66SJosef Bacik if (err)
657e3974c66SJosef Bacik goto out;
658e3974c66SJosef Bacik if (state->end <= end) {
659e3974c66SJosef Bacik state = clear_state_bit(tree, state, bits, wake, changeset);
660e3974c66SJosef Bacik goto next;
661e3974c66SJosef Bacik }
662e3974c66SJosef Bacik goto search_again;
663e3974c66SJosef Bacik }
664e3974c66SJosef Bacik /*
665e3974c66SJosef Bacik * | ---- desired range ---- |
666e3974c66SJosef Bacik * | state |
667e3974c66SJosef Bacik * We need to split the extent, and clear the bit on the first half.
668e3974c66SJosef Bacik */
669e3974c66SJosef Bacik if (state->start <= end && state->end > end) {
670e3974c66SJosef Bacik prealloc = alloc_extent_state_atomic(prealloc);
6715a75034eSJosef Bacik if (!prealloc)
6725a75034eSJosef Bacik goto search_again;
673e3974c66SJosef Bacik err = split_state(tree, state, prealloc, end + 1);
674e3974c66SJosef Bacik if (err)
675e3974c66SJosef Bacik extent_io_tree_panic(tree, err);
676e3974c66SJosef Bacik
677e3974c66SJosef Bacik if (wake)
678e3974c66SJosef Bacik wake_up(&state->wq);
679e3974c66SJosef Bacik
680e3974c66SJosef Bacik clear_state_bit(tree, prealloc, bits, wake, changeset);
681e3974c66SJosef Bacik
682e3974c66SJosef Bacik prealloc = NULL;
683e3974c66SJosef Bacik goto out;
684e3974c66SJosef Bacik }
685e3974c66SJosef Bacik
686e3974c66SJosef Bacik state = clear_state_bit(tree, state, bits, wake, changeset);
687e3974c66SJosef Bacik next:
688e3974c66SJosef Bacik if (last_end == (u64)-1)
689e3974c66SJosef Bacik goto out;
690e3974c66SJosef Bacik start = last_end + 1;
691e3974c66SJosef Bacik if (start <= end && state && !need_resched())
692e3974c66SJosef Bacik goto hit_next;
693e3974c66SJosef Bacik
694e3974c66SJosef Bacik search_again:
695e3974c66SJosef Bacik if (start > end)
696e3974c66SJosef Bacik goto out;
697e3974c66SJosef Bacik spin_unlock(&tree->lock);
698e3974c66SJosef Bacik if (gfpflags_allow_blocking(mask))
699e3974c66SJosef Bacik cond_resched();
700e3974c66SJosef Bacik goto again;
701e3974c66SJosef Bacik
702e3974c66SJosef Bacik out:
703e3974c66SJosef Bacik spin_unlock(&tree->lock);
704e3974c66SJosef Bacik if (prealloc)
705e3974c66SJosef Bacik free_extent_state(prealloc);
706e3974c66SJosef Bacik
707e3974c66SJosef Bacik return 0;
708e3974c66SJosef Bacik
709e3974c66SJosef Bacik }
710e3974c66SJosef Bacik
wait_on_state(struct extent_io_tree * tree,struct extent_state * state)711e3974c66SJosef Bacik static void wait_on_state(struct extent_io_tree *tree,
712e3974c66SJosef Bacik struct extent_state *state)
713e3974c66SJosef Bacik __releases(tree->lock)
714e3974c66SJosef Bacik __acquires(tree->lock)
715e3974c66SJosef Bacik {
716e3974c66SJosef Bacik DEFINE_WAIT(wait);
717e3974c66SJosef Bacik prepare_to_wait(&state->wq, &wait, TASK_UNINTERRUPTIBLE);
718e3974c66SJosef Bacik spin_unlock(&tree->lock);
719e3974c66SJosef Bacik schedule();
720e3974c66SJosef Bacik spin_lock(&tree->lock);
721e3974c66SJosef Bacik finish_wait(&state->wq, &wait);
722e3974c66SJosef Bacik }
723e3974c66SJosef Bacik
724e3974c66SJosef Bacik /*
725e3974c66SJosef Bacik * Wait for one or more bits to clear on a range in the state tree.
726e3974c66SJosef Bacik * The range [start, end] is inclusive.
727e3974c66SJosef Bacik * The tree lock is taken by this function
728e3974c66SJosef Bacik */
wait_extent_bit(struct extent_io_tree * tree,u64 start,u64 end,u32 bits,struct extent_state ** cached_state)729123a7f00SJosef Bacik void wait_extent_bit(struct extent_io_tree *tree, u64 start, u64 end, u32 bits,
730123a7f00SJosef Bacik struct extent_state **cached_state)
731e3974c66SJosef Bacik {
732e3974c66SJosef Bacik struct extent_state *state;
733e3974c66SJosef Bacik
734e3974c66SJosef Bacik btrfs_debug_check_extent_io_range(tree, start, end);
735e3974c66SJosef Bacik
736e3974c66SJosef Bacik spin_lock(&tree->lock);
737e3974c66SJosef Bacik again:
738123a7f00SJosef Bacik /*
739123a7f00SJosef Bacik * Maintain cached_state, as we may not remove it from the tree if there
740123a7f00SJosef Bacik * are more bits than the bits we're waiting on set on this state.
741123a7f00SJosef Bacik */
742123a7f00SJosef Bacik if (cached_state && *cached_state) {
743123a7f00SJosef Bacik state = *cached_state;
744123a7f00SJosef Bacik if (extent_state_in_tree(state) &&
745123a7f00SJosef Bacik state->start <= start && start < state->end)
746123a7f00SJosef Bacik goto process_node;
747123a7f00SJosef Bacik }
748e3974c66SJosef Bacik while (1) {
749e3974c66SJosef Bacik /*
750e3974c66SJosef Bacik * This search will find all the extents that end after our
751e3974c66SJosef Bacik * range starts.
752e3974c66SJosef Bacik */
753aa852dabSJosef Bacik state = tree_search(tree, start);
754ccaeff92SJosef Bacik process_node:
755aa852dabSJosef Bacik if (!state)
756aa852dabSJosef Bacik break;
757e3974c66SJosef Bacik if (state->start > end)
758e3974c66SJosef Bacik goto out;
759e3974c66SJosef Bacik
760e3974c66SJosef Bacik if (state->state & bits) {
761e3974c66SJosef Bacik start = state->start;
762e3974c66SJosef Bacik refcount_inc(&state->refs);
763e3974c66SJosef Bacik wait_on_state(tree, state);
764e3974c66SJosef Bacik free_extent_state(state);
765e3974c66SJosef Bacik goto again;
766e3974c66SJosef Bacik }
767e3974c66SJosef Bacik start = state->end + 1;
768e3974c66SJosef Bacik
769e3974c66SJosef Bacik if (start > end)
770e3974c66SJosef Bacik break;
771e3974c66SJosef Bacik
772e3974c66SJosef Bacik if (!cond_resched_lock(&tree->lock)) {
773ccaeff92SJosef Bacik state = next_state(state);
774e3974c66SJosef Bacik goto process_node;
775e3974c66SJosef Bacik }
776e3974c66SJosef Bacik }
777e3974c66SJosef Bacik out:
778123a7f00SJosef Bacik /* This state is no longer useful, clear it and free it up. */
779123a7f00SJosef Bacik if (cached_state && *cached_state) {
780123a7f00SJosef Bacik state = *cached_state;
781123a7f00SJosef Bacik *cached_state = NULL;
782123a7f00SJosef Bacik free_extent_state(state);
783123a7f00SJosef Bacik }
784e3974c66SJosef Bacik spin_unlock(&tree->lock);
785e3974c66SJosef Bacik }
786e3974c66SJosef Bacik
cache_state_if_flags(struct extent_state * state,struct extent_state ** cached_ptr,unsigned flags)787e3974c66SJosef Bacik static void cache_state_if_flags(struct extent_state *state,
788e3974c66SJosef Bacik struct extent_state **cached_ptr,
789e3974c66SJosef Bacik unsigned flags)
790e3974c66SJosef Bacik {
791e3974c66SJosef Bacik if (cached_ptr && !(*cached_ptr)) {
792e3974c66SJosef Bacik if (!flags || (state->state & flags)) {
793e3974c66SJosef Bacik *cached_ptr = state;
794e3974c66SJosef Bacik refcount_inc(&state->refs);
795e3974c66SJosef Bacik }
796e3974c66SJosef Bacik }
797e3974c66SJosef Bacik }
798e3974c66SJosef Bacik
cache_state(struct extent_state * state,struct extent_state ** cached_ptr)799e3974c66SJosef Bacik static void cache_state(struct extent_state *state,
800e3974c66SJosef Bacik struct extent_state **cached_ptr)
801e3974c66SJosef Bacik {
802e3974c66SJosef Bacik return cache_state_if_flags(state, cached_ptr,
803e3974c66SJosef Bacik EXTENT_LOCKED | EXTENT_BOUNDARY);
804e3974c66SJosef Bacik }
805e3974c66SJosef Bacik
806e3974c66SJosef Bacik /*
807e3974c66SJosef Bacik * Find the first state struct with 'bits' set after 'start', and return it.
808e3974c66SJosef Bacik * tree->lock must be held. NULL will returned if nothing was found after
809e3974c66SJosef Bacik * 'start'.
810e3974c66SJosef Bacik */
find_first_extent_bit_state(struct extent_io_tree * tree,u64 start,u32 bits)811e3974c66SJosef Bacik static struct extent_state *find_first_extent_bit_state(struct extent_io_tree *tree,
812e3974c66SJosef Bacik u64 start, u32 bits)
813e3974c66SJosef Bacik {
814e3974c66SJosef Bacik struct extent_state *state;
815e3974c66SJosef Bacik
816e3974c66SJosef Bacik /*
817e3974c66SJosef Bacik * This search will find all the extents that end after our range
818e3974c66SJosef Bacik * starts.
819e3974c66SJosef Bacik */
820aa852dabSJosef Bacik state = tree_search(tree, start);
821ccaeff92SJosef Bacik while (state) {
822e3974c66SJosef Bacik if (state->end >= start && (state->state & bits))
823e3974c66SJosef Bacik return state;
824ccaeff92SJosef Bacik state = next_state(state);
825e3974c66SJosef Bacik }
826e3974c66SJosef Bacik return NULL;
827e3974c66SJosef Bacik }
828e3974c66SJosef Bacik
829e3974c66SJosef Bacik /*
830e3974c66SJosef Bacik * Find the first offset in the io tree with one or more @bits set.
831e3974c66SJosef Bacik *
832e3974c66SJosef Bacik * Note: If there are multiple bits set in @bits, any of them will match.
833e3974c66SJosef Bacik *
834*e5860f82SFilipe Manana * Return true if we find something, and update @start_ret and @end_ret.
835*e5860f82SFilipe Manana * Return false if we found nothing.
836e3974c66SJosef Bacik */
find_first_extent_bit(struct extent_io_tree * tree,u64 start,u64 * start_ret,u64 * end_ret,u32 bits,struct extent_state ** cached_state)837*e5860f82SFilipe Manana bool find_first_extent_bit(struct extent_io_tree *tree, u64 start,
838e3974c66SJosef Bacik u64 *start_ret, u64 *end_ret, u32 bits,
839e3974c66SJosef Bacik struct extent_state **cached_state)
840e3974c66SJosef Bacik {
841e3974c66SJosef Bacik struct extent_state *state;
842*e5860f82SFilipe Manana bool ret = false;
843e3974c66SJosef Bacik
844e3974c66SJosef Bacik spin_lock(&tree->lock);
845e3974c66SJosef Bacik if (cached_state && *cached_state) {
846e3974c66SJosef Bacik state = *cached_state;
847e3974c66SJosef Bacik if (state->end == start - 1 && extent_state_in_tree(state)) {
848e3974c66SJosef Bacik while ((state = next_state(state)) != NULL) {
849e3974c66SJosef Bacik if (state->state & bits)
850e3974c66SJosef Bacik goto got_it;
851e3974c66SJosef Bacik }
852e3974c66SJosef Bacik free_extent_state(*cached_state);
853e3974c66SJosef Bacik *cached_state = NULL;
854e3974c66SJosef Bacik goto out;
855e3974c66SJosef Bacik }
856e3974c66SJosef Bacik free_extent_state(*cached_state);
857e3974c66SJosef Bacik *cached_state = NULL;
858e3974c66SJosef Bacik }
859e3974c66SJosef Bacik
860e3974c66SJosef Bacik state = find_first_extent_bit_state(tree, start, bits);
861e3974c66SJosef Bacik got_it:
862e3974c66SJosef Bacik if (state) {
863e3974c66SJosef Bacik cache_state_if_flags(state, cached_state, 0);
864e3974c66SJosef Bacik *start_ret = state->start;
865e3974c66SJosef Bacik *end_ret = state->end;
866*e5860f82SFilipe Manana ret = true;
867e3974c66SJosef Bacik }
868e3974c66SJosef Bacik out:
869e3974c66SJosef Bacik spin_unlock(&tree->lock);
870e3974c66SJosef Bacik return ret;
871e3974c66SJosef Bacik }
872e3974c66SJosef Bacik
873e3974c66SJosef Bacik /*
874e3974c66SJosef Bacik * Find a contiguous area of bits
875e3974c66SJosef Bacik *
876e3974c66SJosef Bacik * @tree: io tree to check
877e3974c66SJosef Bacik * @start: offset to start the search from
878e3974c66SJosef Bacik * @start_ret: the first offset we found with the bits set
879e3974c66SJosef Bacik * @end_ret: the final contiguous range of the bits that were set
880e3974c66SJosef Bacik * @bits: bits to look for
881e3974c66SJosef Bacik *
882e3974c66SJosef Bacik * set_extent_bit and clear_extent_bit can temporarily split contiguous ranges
883e3974c66SJosef Bacik * to set bits appropriately, and then merge them again. During this time it
884e3974c66SJosef Bacik * will drop the tree->lock, so use this helper if you want to find the actual
885e3974c66SJosef Bacik * contiguous area for given bits. We will search to the first bit we find, and
886e3974c66SJosef Bacik * then walk down the tree until we find a non-contiguous area. The area
887e3974c66SJosef Bacik * returned will be the full contiguous area with the bits set.
888e3974c66SJosef Bacik */
find_contiguous_extent_bit(struct extent_io_tree * tree,u64 start,u64 * start_ret,u64 * end_ret,u32 bits)889e3974c66SJosef Bacik int find_contiguous_extent_bit(struct extent_io_tree *tree, u64 start,
890e3974c66SJosef Bacik u64 *start_ret, u64 *end_ret, u32 bits)
891e3974c66SJosef Bacik {
892e3974c66SJosef Bacik struct extent_state *state;
893e3974c66SJosef Bacik int ret = 1;
894e3974c66SJosef Bacik
895e3974c66SJosef Bacik spin_lock(&tree->lock);
896e3974c66SJosef Bacik state = find_first_extent_bit_state(tree, start, bits);
897e3974c66SJosef Bacik if (state) {
898e3974c66SJosef Bacik *start_ret = state->start;
899e3974c66SJosef Bacik *end_ret = state->end;
900e3974c66SJosef Bacik while ((state = next_state(state)) != NULL) {
901e3974c66SJosef Bacik if (state->start > (*end_ret + 1))
902e3974c66SJosef Bacik break;
903e3974c66SJosef Bacik *end_ret = state->end;
904e3974c66SJosef Bacik }
905e3974c66SJosef Bacik ret = 0;
906e3974c66SJosef Bacik }
907e3974c66SJosef Bacik spin_unlock(&tree->lock);
908e3974c66SJosef Bacik return ret;
909e3974c66SJosef Bacik }
910e3974c66SJosef Bacik
911e3974c66SJosef Bacik /*
912e3974c66SJosef Bacik * Find a contiguous range of bytes in the file marked as delalloc, not more
913e3974c66SJosef Bacik * than 'max_bytes'. start and end are used to return the range,
914e3974c66SJosef Bacik *
915e3974c66SJosef Bacik * True is returned if we find something, false if nothing was in the tree.
916e3974c66SJosef Bacik */
btrfs_find_delalloc_range(struct extent_io_tree * tree,u64 * start,u64 * end,u64 max_bytes,struct extent_state ** cached_state)917e3974c66SJosef Bacik bool btrfs_find_delalloc_range(struct extent_io_tree *tree, u64 *start,
918e3974c66SJosef Bacik u64 *end, u64 max_bytes,
919e3974c66SJosef Bacik struct extent_state **cached_state)
920e3974c66SJosef Bacik {
921e3974c66SJosef Bacik struct extent_state *state;
922e3974c66SJosef Bacik u64 cur_start = *start;
923e3974c66SJosef Bacik bool found = false;
924e3974c66SJosef Bacik u64 total_bytes = 0;
925e3974c66SJosef Bacik
926e3974c66SJosef Bacik spin_lock(&tree->lock);
927e3974c66SJosef Bacik
928e3974c66SJosef Bacik /*
929e3974c66SJosef Bacik * This search will find all the extents that end after our range
930e3974c66SJosef Bacik * starts.
931e3974c66SJosef Bacik */
932aa852dabSJosef Bacik state = tree_search(tree, cur_start);
933aa852dabSJosef Bacik if (!state) {
934e3974c66SJosef Bacik *end = (u64)-1;
935e3974c66SJosef Bacik goto out;
936e3974c66SJosef Bacik }
937e3974c66SJosef Bacik
938ccaeff92SJosef Bacik while (state) {
939e3974c66SJosef Bacik if (found && (state->start != cur_start ||
940e3974c66SJosef Bacik (state->state & EXTENT_BOUNDARY))) {
941e3974c66SJosef Bacik goto out;
942e3974c66SJosef Bacik }
943e3974c66SJosef Bacik if (!(state->state & EXTENT_DELALLOC)) {
944e3974c66SJosef Bacik if (!found)
945e3974c66SJosef Bacik *end = state->end;
946e3974c66SJosef Bacik goto out;
947e3974c66SJosef Bacik }
948e3974c66SJosef Bacik if (!found) {
949e3974c66SJosef Bacik *start = state->start;
950e3974c66SJosef Bacik *cached_state = state;
951e3974c66SJosef Bacik refcount_inc(&state->refs);
952e3974c66SJosef Bacik }
953e3974c66SJosef Bacik found = true;
954e3974c66SJosef Bacik *end = state->end;
955e3974c66SJosef Bacik cur_start = state->end + 1;
956e3974c66SJosef Bacik total_bytes += state->end - state->start + 1;
957e3974c66SJosef Bacik if (total_bytes >= max_bytes)
958e3974c66SJosef Bacik break;
959ccaeff92SJosef Bacik state = next_state(state);
960e3974c66SJosef Bacik }
961e3974c66SJosef Bacik out:
962e3974c66SJosef Bacik spin_unlock(&tree->lock);
963e3974c66SJosef Bacik return found;
964e3974c66SJosef Bacik }
965e3974c66SJosef Bacik
966e3974c66SJosef Bacik /*
967e3974c66SJosef Bacik * Set some bits on a range in the tree. This may require allocations or
9681d126800SDavid Sterba * sleeping. By default all allocations use GFP_NOFS, use EXTENT_NOWAIT for
9691d126800SDavid Sterba * GFP_NOWAIT.
970e3974c66SJosef Bacik *
971e3974c66SJosef Bacik * If any of the exclusive bits are set, this will fail with -EEXIST if some
972123a7f00SJosef Bacik * part of the range already has the desired bits set. The extent_state of the
973123a7f00SJosef Bacik * existing range is returned in failed_state in this case, and the start of the
974123a7f00SJosef Bacik * existing range is returned in failed_start. failed_state is used as an
975123a7f00SJosef Bacik * optimization for wait_extent_bit, failed_start must be used as the source of
976123a7f00SJosef Bacik * truth as failed_state may have changed since we returned.
977e3974c66SJosef Bacik *
978e3974c66SJosef Bacik * [start, end] is inclusive This takes the tree lock.
979e3974c66SJosef Bacik */
__set_extent_bit(struct extent_io_tree * tree,u64 start,u64 end,u32 bits,u64 * failed_start,struct extent_state ** failed_state,struct extent_state ** cached_state,struct extent_changeset * changeset)980994bcd1eSJosef Bacik static int __set_extent_bit(struct extent_io_tree *tree, u64 start, u64 end,
981c07d1004SJosef Bacik u32 bits, u64 *failed_start,
982123a7f00SJosef Bacik struct extent_state **failed_state,
983994bcd1eSJosef Bacik struct extent_state **cached_state,
9841d126800SDavid Sterba struct extent_changeset *changeset)
985e3974c66SJosef Bacik {
986e3974c66SJosef Bacik struct extent_state *state;
987e3974c66SJosef Bacik struct extent_state *prealloc = NULL;
98859864325SJosef Bacik struct rb_node **p = NULL;
98959864325SJosef Bacik struct rb_node *parent = NULL;
990e3974c66SJosef Bacik int err = 0;
991e3974c66SJosef Bacik u64 last_start;
992e3974c66SJosef Bacik u64 last_end;
993c07d1004SJosef Bacik u32 exclusive_bits = (bits & EXTENT_LOCKED);
9941d126800SDavid Sterba gfp_t mask;
995e3974c66SJosef Bacik
99662bc6047SDavid Sterba set_gfp_mask_from_bits(&bits, &mask);
997e3974c66SJosef Bacik btrfs_debug_check_extent_io_range(tree, start, end);
998e3974c66SJosef Bacik trace_btrfs_set_extent_bit(tree, start, end - start + 1, bits);
999e3974c66SJosef Bacik
1000e3974c66SJosef Bacik if (exclusive_bits)
1001e3974c66SJosef Bacik ASSERT(failed_start);
1002e3974c66SJosef Bacik else
1003123a7f00SJosef Bacik ASSERT(failed_start == NULL && failed_state == NULL);
1004e3974c66SJosef Bacik again:
10055a75034eSJosef Bacik if (!prealloc) {
1006e3974c66SJosef Bacik /*
1007e3974c66SJosef Bacik * Don't care for allocation failure here because we might end
1008e3974c66SJosef Bacik * up not needing the pre-allocated extent state at all, which
1009e3974c66SJosef Bacik * is the case if we only have in the tree extent states that
1010e3974c66SJosef Bacik * cover our input range and don't cover too any other range.
1011e3974c66SJosef Bacik * If we end up needing a new extent state we allocate it later.
1012e3974c66SJosef Bacik */
1013e3974c66SJosef Bacik prealloc = alloc_extent_state(mask);
1014e3974c66SJosef Bacik }
1015e3974c66SJosef Bacik
1016e3974c66SJosef Bacik spin_lock(&tree->lock);
1017e3974c66SJosef Bacik if (cached_state && *cached_state) {
1018e3974c66SJosef Bacik state = *cached_state;
1019e3974c66SJosef Bacik if (state->start <= start && state->end > start &&
1020e349fd3bSJosef Bacik extent_state_in_tree(state))
1021e3974c66SJosef Bacik goto hit_next;
1022e3974c66SJosef Bacik }
1023e3974c66SJosef Bacik /*
1024e3974c66SJosef Bacik * This search will find all the extents that end after our range
1025e3974c66SJosef Bacik * starts.
1026e3974c66SJosef Bacik */
1027e349fd3bSJosef Bacik state = tree_search_for_insert(tree, start, &p, &parent);
1028e349fd3bSJosef Bacik if (!state) {
1029e3974c66SJosef Bacik prealloc = alloc_extent_state_atomic(prealloc);
10305a75034eSJosef Bacik if (!prealloc)
10315a75034eSJosef Bacik goto search_again;
1032e3974c66SJosef Bacik prealloc->start = start;
1033e3974c66SJosef Bacik prealloc->end = end;
1034e3974c66SJosef Bacik insert_state_fast(tree, prealloc, p, parent, bits, changeset);
1035e3974c66SJosef Bacik cache_state(prealloc, cached_state);
1036e3974c66SJosef Bacik prealloc = NULL;
1037e3974c66SJosef Bacik goto out;
1038e3974c66SJosef Bacik }
1039e3974c66SJosef Bacik hit_next:
1040e3974c66SJosef Bacik last_start = state->start;
1041e3974c66SJosef Bacik last_end = state->end;
1042e3974c66SJosef Bacik
1043e3974c66SJosef Bacik /*
1044e3974c66SJosef Bacik * | ---- desired range ---- |
1045e3974c66SJosef Bacik * | state |
1046e3974c66SJosef Bacik *
1047e3974c66SJosef Bacik * Just lock what we found and keep going
1048e3974c66SJosef Bacik */
1049e3974c66SJosef Bacik if (state->start == start && state->end <= end) {
1050e3974c66SJosef Bacik if (state->state & exclusive_bits) {
1051e3974c66SJosef Bacik *failed_start = state->start;
1052123a7f00SJosef Bacik cache_state(state, failed_state);
1053e3974c66SJosef Bacik err = -EEXIST;
1054e3974c66SJosef Bacik goto out;
1055e3974c66SJosef Bacik }
1056e3974c66SJosef Bacik
1057e3974c66SJosef Bacik set_state_bits(tree, state, bits, changeset);
1058e3974c66SJosef Bacik cache_state(state, cached_state);
1059e3974c66SJosef Bacik merge_state(tree, state);
1060e3974c66SJosef Bacik if (last_end == (u64)-1)
1061e3974c66SJosef Bacik goto out;
1062e3974c66SJosef Bacik start = last_end + 1;
1063e3974c66SJosef Bacik state = next_state(state);
1064e3974c66SJosef Bacik if (start < end && state && state->start == start &&
1065e3974c66SJosef Bacik !need_resched())
1066e3974c66SJosef Bacik goto hit_next;
1067e3974c66SJosef Bacik goto search_again;
1068e3974c66SJosef Bacik }
1069e3974c66SJosef Bacik
1070e3974c66SJosef Bacik /*
1071e3974c66SJosef Bacik * | ---- desired range ---- |
1072e3974c66SJosef Bacik * | state |
1073e3974c66SJosef Bacik * or
1074e3974c66SJosef Bacik * | ------------- state -------------- |
1075e3974c66SJosef Bacik *
1076e3974c66SJosef Bacik * We need to split the extent we found, and may flip bits on second
1077e3974c66SJosef Bacik * half.
1078e3974c66SJosef Bacik *
1079e3974c66SJosef Bacik * If the extent we found extends past our range, we just split and
1080e3974c66SJosef Bacik * search again. It'll get split again the next time though.
1081e3974c66SJosef Bacik *
1082e3974c66SJosef Bacik * If the extent we found is inside our range, we set the desired bit
1083e3974c66SJosef Bacik * on it.
1084e3974c66SJosef Bacik */
1085e3974c66SJosef Bacik if (state->start < start) {
1086e3974c66SJosef Bacik if (state->state & exclusive_bits) {
1087e3974c66SJosef Bacik *failed_start = start;
1088123a7f00SJosef Bacik cache_state(state, failed_state);
1089e3974c66SJosef Bacik err = -EEXIST;
1090e3974c66SJosef Bacik goto out;
1091e3974c66SJosef Bacik }
1092e3974c66SJosef Bacik
1093e3974c66SJosef Bacik /*
1094e3974c66SJosef Bacik * If this extent already has all the bits we want set, then
1095e3974c66SJosef Bacik * skip it, not necessary to split it or do anything with it.
1096e3974c66SJosef Bacik */
1097e3974c66SJosef Bacik if ((state->state & bits) == bits) {
1098e3974c66SJosef Bacik start = state->end + 1;
1099e3974c66SJosef Bacik cache_state(state, cached_state);
1100e3974c66SJosef Bacik goto search_again;
1101e3974c66SJosef Bacik }
1102e3974c66SJosef Bacik
1103e3974c66SJosef Bacik prealloc = alloc_extent_state_atomic(prealloc);
11045a75034eSJosef Bacik if (!prealloc)
11055a75034eSJosef Bacik goto search_again;
1106e3974c66SJosef Bacik err = split_state(tree, state, prealloc, start);
1107e3974c66SJosef Bacik if (err)
1108e3974c66SJosef Bacik extent_io_tree_panic(tree, err);
1109e3974c66SJosef Bacik
1110e3974c66SJosef Bacik prealloc = NULL;
1111e3974c66SJosef Bacik if (err)
1112e3974c66SJosef Bacik goto out;
1113e3974c66SJosef Bacik if (state->end <= end) {
1114e3974c66SJosef Bacik set_state_bits(tree, state, bits, changeset);
1115e3974c66SJosef Bacik cache_state(state, cached_state);
1116e3974c66SJosef Bacik merge_state(tree, state);
1117e3974c66SJosef Bacik if (last_end == (u64)-1)
1118e3974c66SJosef Bacik goto out;
1119e3974c66SJosef Bacik start = last_end + 1;
1120e3974c66SJosef Bacik state = next_state(state);
1121e3974c66SJosef Bacik if (start < end && state && state->start == start &&
1122e3974c66SJosef Bacik !need_resched())
1123e3974c66SJosef Bacik goto hit_next;
1124e3974c66SJosef Bacik }
1125e3974c66SJosef Bacik goto search_again;
1126e3974c66SJosef Bacik }
1127e3974c66SJosef Bacik /*
1128e3974c66SJosef Bacik * | ---- desired range ---- |
1129e3974c66SJosef Bacik * | state | or | state |
1130e3974c66SJosef Bacik *
1131e3974c66SJosef Bacik * There's a hole, we need to insert something in it and ignore the
1132e3974c66SJosef Bacik * extent we found.
1133e3974c66SJosef Bacik */
1134e3974c66SJosef Bacik if (state->start > start) {
1135e3974c66SJosef Bacik u64 this_end;
1136e3974c66SJosef Bacik if (end < last_start)
1137e3974c66SJosef Bacik this_end = end;
1138e3974c66SJosef Bacik else
1139e3974c66SJosef Bacik this_end = last_start - 1;
1140e3974c66SJosef Bacik
1141e3974c66SJosef Bacik prealloc = alloc_extent_state_atomic(prealloc);
11425a75034eSJosef Bacik if (!prealloc)
11435a75034eSJosef Bacik goto search_again;
1144e3974c66SJosef Bacik
1145e3974c66SJosef Bacik /*
1146e3974c66SJosef Bacik * Avoid to free 'prealloc' if it can be merged with the later
1147e3974c66SJosef Bacik * extent.
1148e3974c66SJosef Bacik */
1149e3974c66SJosef Bacik prealloc->start = start;
1150e3974c66SJosef Bacik prealloc->end = this_end;
1151e3974c66SJosef Bacik err = insert_state(tree, prealloc, bits, changeset);
1152e3974c66SJosef Bacik if (err)
1153e3974c66SJosef Bacik extent_io_tree_panic(tree, err);
1154e3974c66SJosef Bacik
1155e3974c66SJosef Bacik cache_state(prealloc, cached_state);
1156e3974c66SJosef Bacik prealloc = NULL;
1157e3974c66SJosef Bacik start = this_end + 1;
1158e3974c66SJosef Bacik goto search_again;
1159e3974c66SJosef Bacik }
1160e3974c66SJosef Bacik /*
1161e3974c66SJosef Bacik * | ---- desired range ---- |
1162e3974c66SJosef Bacik * | state |
1163e3974c66SJosef Bacik *
1164e3974c66SJosef Bacik * We need to split the extent, and set the bit on the first half
1165e3974c66SJosef Bacik */
1166e3974c66SJosef Bacik if (state->start <= end && state->end > end) {
1167e3974c66SJosef Bacik if (state->state & exclusive_bits) {
1168e3974c66SJosef Bacik *failed_start = start;
1169123a7f00SJosef Bacik cache_state(state, failed_state);
1170e3974c66SJosef Bacik err = -EEXIST;
1171e3974c66SJosef Bacik goto out;
1172e3974c66SJosef Bacik }
1173e3974c66SJosef Bacik
1174e3974c66SJosef Bacik prealloc = alloc_extent_state_atomic(prealloc);
11755a75034eSJosef Bacik if (!prealloc)
11765a75034eSJosef Bacik goto search_again;
1177e3974c66SJosef Bacik err = split_state(tree, state, prealloc, end + 1);
1178e3974c66SJosef Bacik if (err)
1179e3974c66SJosef Bacik extent_io_tree_panic(tree, err);
1180e3974c66SJosef Bacik
1181e3974c66SJosef Bacik set_state_bits(tree, prealloc, bits, changeset);
1182e3974c66SJosef Bacik cache_state(prealloc, cached_state);
1183e3974c66SJosef Bacik merge_state(tree, prealloc);
1184e3974c66SJosef Bacik prealloc = NULL;
1185e3974c66SJosef Bacik goto out;
1186e3974c66SJosef Bacik }
1187e3974c66SJosef Bacik
1188e3974c66SJosef Bacik search_again:
1189e3974c66SJosef Bacik if (start > end)
1190e3974c66SJosef Bacik goto out;
1191e3974c66SJosef Bacik spin_unlock(&tree->lock);
1192e3974c66SJosef Bacik if (gfpflags_allow_blocking(mask))
1193e3974c66SJosef Bacik cond_resched();
1194e3974c66SJosef Bacik goto again;
1195e3974c66SJosef Bacik
1196e3974c66SJosef Bacik out:
1197e3974c66SJosef Bacik spin_unlock(&tree->lock);
1198e3974c66SJosef Bacik if (prealloc)
1199e3974c66SJosef Bacik free_extent_state(prealloc);
1200e3974c66SJosef Bacik
1201e3974c66SJosef Bacik return err;
1202e3974c66SJosef Bacik
1203e3974c66SJosef Bacik }
1204e3974c66SJosef Bacik
set_extent_bit(struct extent_io_tree * tree,u64 start,u64 end,u32 bits,struct extent_state ** cached_state)1205994bcd1eSJosef Bacik int set_extent_bit(struct extent_io_tree *tree, u64 start, u64 end,
12061d126800SDavid Sterba u32 bits, struct extent_state **cached_state)
1207994bcd1eSJosef Bacik {
1208123a7f00SJosef Bacik return __set_extent_bit(tree, start, end, bits, NULL, NULL,
12091d126800SDavid Sterba cached_state, NULL);
1210994bcd1eSJosef Bacik }
1211994bcd1eSJosef Bacik
1212e3974c66SJosef Bacik /*
1213e3974c66SJosef Bacik * Convert all bits in a given range from one bit to another
1214e3974c66SJosef Bacik *
1215e3974c66SJosef Bacik * @tree: the io tree to search
1216e3974c66SJosef Bacik * @start: the start offset in bytes
1217e3974c66SJosef Bacik * @end: the end offset in bytes (inclusive)
1218e3974c66SJosef Bacik * @bits: the bits to set in this range
1219e3974c66SJosef Bacik * @clear_bits: the bits to clear in this range
1220e3974c66SJosef Bacik * @cached_state: state that we're going to cache
1221e3974c66SJosef Bacik *
1222e3974c66SJosef Bacik * This will go through and set bits for the given range. If any states exist
1223e3974c66SJosef Bacik * already in this range they are set with the given bit and cleared of the
1224e3974c66SJosef Bacik * clear_bits. This is only meant to be used by things that are mergeable, ie.
1225e3974c66SJosef Bacik * converting from say DELALLOC to DIRTY. This is not meant to be used with
1226e3974c66SJosef Bacik * boundary bits like LOCK.
1227e3974c66SJosef Bacik *
1228e3974c66SJosef Bacik * All allocations are done with GFP_NOFS.
1229e3974c66SJosef Bacik */
convert_extent_bit(struct extent_io_tree * tree,u64 start,u64 end,u32 bits,u32 clear_bits,struct extent_state ** cached_state)1230e3974c66SJosef Bacik int convert_extent_bit(struct extent_io_tree *tree, u64 start, u64 end,
1231e3974c66SJosef Bacik u32 bits, u32 clear_bits,
1232e3974c66SJosef Bacik struct extent_state **cached_state)
1233e3974c66SJosef Bacik {
1234e3974c66SJosef Bacik struct extent_state *state;
1235e3974c66SJosef Bacik struct extent_state *prealloc = NULL;
123659864325SJosef Bacik struct rb_node **p = NULL;
123759864325SJosef Bacik struct rb_node *parent = NULL;
1238e3974c66SJosef Bacik int err = 0;
1239e3974c66SJosef Bacik u64 last_start;
1240e3974c66SJosef Bacik u64 last_end;
1241e3974c66SJosef Bacik bool first_iteration = true;
1242e3974c66SJosef Bacik
1243e3974c66SJosef Bacik btrfs_debug_check_extent_io_range(tree, start, end);
1244e3974c66SJosef Bacik trace_btrfs_convert_extent_bit(tree, start, end - start + 1, bits,
1245e3974c66SJosef Bacik clear_bits);
1246e3974c66SJosef Bacik
1247e3974c66SJosef Bacik again:
1248e3974c66SJosef Bacik if (!prealloc) {
1249e3974c66SJosef Bacik /*
1250e3974c66SJosef Bacik * Best effort, don't worry if extent state allocation fails
1251e3974c66SJosef Bacik * here for the first iteration. We might have a cached state
1252e3974c66SJosef Bacik * that matches exactly the target range, in which case no
1253e3974c66SJosef Bacik * extent state allocations are needed. We'll only know this
1254e3974c66SJosef Bacik * after locking the tree.
1255e3974c66SJosef Bacik */
1256e3974c66SJosef Bacik prealloc = alloc_extent_state(GFP_NOFS);
1257e3974c66SJosef Bacik if (!prealloc && !first_iteration)
1258e3974c66SJosef Bacik return -ENOMEM;
1259e3974c66SJosef Bacik }
1260e3974c66SJosef Bacik
1261e3974c66SJosef Bacik spin_lock(&tree->lock);
1262e3974c66SJosef Bacik if (cached_state && *cached_state) {
1263e3974c66SJosef Bacik state = *cached_state;
1264e3974c66SJosef Bacik if (state->start <= start && state->end > start &&
1265e349fd3bSJosef Bacik extent_state_in_tree(state))
1266e3974c66SJosef Bacik goto hit_next;
1267e3974c66SJosef Bacik }
1268e3974c66SJosef Bacik
1269e3974c66SJosef Bacik /*
1270e3974c66SJosef Bacik * This search will find all the extents that end after our range
1271e3974c66SJosef Bacik * starts.
1272e3974c66SJosef Bacik */
1273e349fd3bSJosef Bacik state = tree_search_for_insert(tree, start, &p, &parent);
1274e349fd3bSJosef Bacik if (!state) {
1275e3974c66SJosef Bacik prealloc = alloc_extent_state_atomic(prealloc);
1276e3974c66SJosef Bacik if (!prealloc) {
1277e3974c66SJosef Bacik err = -ENOMEM;
1278e3974c66SJosef Bacik goto out;
1279e3974c66SJosef Bacik }
1280e3974c66SJosef Bacik prealloc->start = start;
1281e3974c66SJosef Bacik prealloc->end = end;
1282e3974c66SJosef Bacik insert_state_fast(tree, prealloc, p, parent, bits, NULL);
1283e3974c66SJosef Bacik cache_state(prealloc, cached_state);
1284e3974c66SJosef Bacik prealloc = NULL;
1285e3974c66SJosef Bacik goto out;
1286e3974c66SJosef Bacik }
1287e3974c66SJosef Bacik hit_next:
1288e3974c66SJosef Bacik last_start = state->start;
1289e3974c66SJosef Bacik last_end = state->end;
1290e3974c66SJosef Bacik
1291e3974c66SJosef Bacik /*
1292e3974c66SJosef Bacik * | ---- desired range ---- |
1293e3974c66SJosef Bacik * | state |
1294e3974c66SJosef Bacik *
1295e3974c66SJosef Bacik * Just lock what we found and keep going.
1296e3974c66SJosef Bacik */
1297e3974c66SJosef Bacik if (state->start == start && state->end <= end) {
1298e3974c66SJosef Bacik set_state_bits(tree, state, bits, NULL);
1299e3974c66SJosef Bacik cache_state(state, cached_state);
1300e3974c66SJosef Bacik state = clear_state_bit(tree, state, clear_bits, 0, NULL);
1301e3974c66SJosef Bacik if (last_end == (u64)-1)
1302e3974c66SJosef Bacik goto out;
1303e3974c66SJosef Bacik start = last_end + 1;
1304e3974c66SJosef Bacik if (start < end && state && state->start == start &&
1305e3974c66SJosef Bacik !need_resched())
1306e3974c66SJosef Bacik goto hit_next;
1307e3974c66SJosef Bacik goto search_again;
1308e3974c66SJosef Bacik }
1309e3974c66SJosef Bacik
1310e3974c66SJosef Bacik /*
1311e3974c66SJosef Bacik * | ---- desired range ---- |
1312e3974c66SJosef Bacik * | state |
1313e3974c66SJosef Bacik * or
1314e3974c66SJosef Bacik * | ------------- state -------------- |
1315e3974c66SJosef Bacik *
1316e3974c66SJosef Bacik * We need to split the extent we found, and may flip bits on second
1317e3974c66SJosef Bacik * half.
1318e3974c66SJosef Bacik *
1319e3974c66SJosef Bacik * If the extent we found extends past our range, we just split and
1320e3974c66SJosef Bacik * search again. It'll get split again the next time though.
1321e3974c66SJosef Bacik *
1322e3974c66SJosef Bacik * If the extent we found is inside our range, we set the desired bit
1323e3974c66SJosef Bacik * on it.
1324e3974c66SJosef Bacik */
1325e3974c66SJosef Bacik if (state->start < start) {
1326e3974c66SJosef Bacik prealloc = alloc_extent_state_atomic(prealloc);
1327e3974c66SJosef Bacik if (!prealloc) {
1328e3974c66SJosef Bacik err = -ENOMEM;
1329e3974c66SJosef Bacik goto out;
1330e3974c66SJosef Bacik }
1331e3974c66SJosef Bacik err = split_state(tree, state, prealloc, start);
1332e3974c66SJosef Bacik if (err)
1333e3974c66SJosef Bacik extent_io_tree_panic(tree, err);
1334e3974c66SJosef Bacik prealloc = NULL;
1335e3974c66SJosef Bacik if (err)
1336e3974c66SJosef Bacik goto out;
1337e3974c66SJosef Bacik if (state->end <= end) {
1338e3974c66SJosef Bacik set_state_bits(tree, state, bits, NULL);
1339e3974c66SJosef Bacik cache_state(state, cached_state);
1340e3974c66SJosef Bacik state = clear_state_bit(tree, state, clear_bits, 0, NULL);
1341e3974c66SJosef Bacik if (last_end == (u64)-1)
1342e3974c66SJosef Bacik goto out;
1343e3974c66SJosef Bacik start = last_end + 1;
1344e3974c66SJosef Bacik if (start < end && state && state->start == start &&
1345e3974c66SJosef Bacik !need_resched())
1346e3974c66SJosef Bacik goto hit_next;
1347e3974c66SJosef Bacik }
1348e3974c66SJosef Bacik goto search_again;
1349e3974c66SJosef Bacik }
1350e3974c66SJosef Bacik /*
1351e3974c66SJosef Bacik * | ---- desired range ---- |
1352e3974c66SJosef Bacik * | state | or | state |
1353e3974c66SJosef Bacik *
1354e3974c66SJosef Bacik * There's a hole, we need to insert something in it and ignore the
1355e3974c66SJosef Bacik * extent we found.
1356e3974c66SJosef Bacik */
1357e3974c66SJosef Bacik if (state->start > start) {
1358e3974c66SJosef Bacik u64 this_end;
1359e3974c66SJosef Bacik if (end < last_start)
1360e3974c66SJosef Bacik this_end = end;
1361e3974c66SJosef Bacik else
1362e3974c66SJosef Bacik this_end = last_start - 1;
1363e3974c66SJosef Bacik
1364e3974c66SJosef Bacik prealloc = alloc_extent_state_atomic(prealloc);
1365e3974c66SJosef Bacik if (!prealloc) {
1366e3974c66SJosef Bacik err = -ENOMEM;
1367e3974c66SJosef Bacik goto out;
1368e3974c66SJosef Bacik }
1369e3974c66SJosef Bacik
1370e3974c66SJosef Bacik /*
1371e3974c66SJosef Bacik * Avoid to free 'prealloc' if it can be merged with the later
1372e3974c66SJosef Bacik * extent.
1373e3974c66SJosef Bacik */
1374e3974c66SJosef Bacik prealloc->start = start;
1375e3974c66SJosef Bacik prealloc->end = this_end;
1376e3974c66SJosef Bacik err = insert_state(tree, prealloc, bits, NULL);
1377e3974c66SJosef Bacik if (err)
1378e3974c66SJosef Bacik extent_io_tree_panic(tree, err);
1379e3974c66SJosef Bacik cache_state(prealloc, cached_state);
1380e3974c66SJosef Bacik prealloc = NULL;
1381e3974c66SJosef Bacik start = this_end + 1;
1382e3974c66SJosef Bacik goto search_again;
1383e3974c66SJosef Bacik }
1384e3974c66SJosef Bacik /*
1385e3974c66SJosef Bacik * | ---- desired range ---- |
1386e3974c66SJosef Bacik * | state |
1387e3974c66SJosef Bacik *
1388e3974c66SJosef Bacik * We need to split the extent, and set the bit on the first half.
1389e3974c66SJosef Bacik */
1390e3974c66SJosef Bacik if (state->start <= end && state->end > end) {
1391e3974c66SJosef Bacik prealloc = alloc_extent_state_atomic(prealloc);
1392e3974c66SJosef Bacik if (!prealloc) {
1393e3974c66SJosef Bacik err = -ENOMEM;
1394e3974c66SJosef Bacik goto out;
1395e3974c66SJosef Bacik }
1396e3974c66SJosef Bacik
1397e3974c66SJosef Bacik err = split_state(tree, state, prealloc, end + 1);
1398e3974c66SJosef Bacik if (err)
1399e3974c66SJosef Bacik extent_io_tree_panic(tree, err);
1400e3974c66SJosef Bacik
1401e3974c66SJosef Bacik set_state_bits(tree, prealloc, bits, NULL);
1402e3974c66SJosef Bacik cache_state(prealloc, cached_state);
1403e3974c66SJosef Bacik clear_state_bit(tree, prealloc, clear_bits, 0, NULL);
1404e3974c66SJosef Bacik prealloc = NULL;
1405e3974c66SJosef Bacik goto out;
1406e3974c66SJosef Bacik }
1407e3974c66SJosef Bacik
1408e3974c66SJosef Bacik search_again:
1409e3974c66SJosef Bacik if (start > end)
1410e3974c66SJosef Bacik goto out;
1411e3974c66SJosef Bacik spin_unlock(&tree->lock);
1412e3974c66SJosef Bacik cond_resched();
1413e3974c66SJosef Bacik first_iteration = false;
1414e3974c66SJosef Bacik goto again;
1415e3974c66SJosef Bacik
1416e3974c66SJosef Bacik out:
1417e3974c66SJosef Bacik spin_unlock(&tree->lock);
1418e3974c66SJosef Bacik if (prealloc)
1419e3974c66SJosef Bacik free_extent_state(prealloc);
1420e3974c66SJosef Bacik
1421e3974c66SJosef Bacik return err;
1422e3974c66SJosef Bacik }
1423e3974c66SJosef Bacik
1424e3974c66SJosef Bacik /*
142538830018SJosef Bacik * Find the first range that has @bits not set. This range could start before
142638830018SJosef Bacik * @start.
142738830018SJosef Bacik *
142838830018SJosef Bacik * @tree: the tree to search
142938830018SJosef Bacik * @start: offset at/after which the found extent should start
143038830018SJosef Bacik * @start_ret: records the beginning of the range
143138830018SJosef Bacik * @end_ret: records the end of the range (inclusive)
143238830018SJosef Bacik * @bits: the set of bits which must be unset
143338830018SJosef Bacik *
143438830018SJosef Bacik * Since unallocated range is also considered one which doesn't have the bits
143538830018SJosef Bacik * set it's possible that @end_ret contains -1, this happens in case the range
143638830018SJosef Bacik * spans (last_range_end, end of device]. In this case it's up to the caller to
143738830018SJosef Bacik * trim @end_ret to the appropriate size.
143838830018SJosef Bacik */
find_first_clear_extent_bit(struct extent_io_tree * tree,u64 start,u64 * start_ret,u64 * end_ret,u32 bits)143938830018SJosef Bacik void find_first_clear_extent_bit(struct extent_io_tree *tree, u64 start,
144038830018SJosef Bacik u64 *start_ret, u64 *end_ret, u32 bits)
144138830018SJosef Bacik {
144238830018SJosef Bacik struct extent_state *state;
144326df39a9SJosef Bacik struct extent_state *prev = NULL, *next = NULL;
144438830018SJosef Bacik
144538830018SJosef Bacik spin_lock(&tree->lock);
144638830018SJosef Bacik
144738830018SJosef Bacik /* Find first extent with bits cleared */
144838830018SJosef Bacik while (1) {
144943b068caSJosef Bacik state = tree_search_prev_next(tree, start, &prev, &next);
145043b068caSJosef Bacik if (!state && !next && !prev) {
145138830018SJosef Bacik /*
145238830018SJosef Bacik * Tree is completely empty, send full range and let
145338830018SJosef Bacik * caller deal with it
145438830018SJosef Bacik */
145538830018SJosef Bacik *start_ret = 0;
145638830018SJosef Bacik *end_ret = -1;
145738830018SJosef Bacik goto out;
145843b068caSJosef Bacik } else if (!state && !next) {
145938830018SJosef Bacik /*
146038830018SJosef Bacik * We are past the last allocated chunk, set start at
146138830018SJosef Bacik * the end of the last extent.
146238830018SJosef Bacik */
146343b068caSJosef Bacik *start_ret = prev->end + 1;
146438830018SJosef Bacik *end_ret = -1;
146538830018SJosef Bacik goto out;
146643b068caSJosef Bacik } else if (!state) {
146743b068caSJosef Bacik state = next;
146838830018SJosef Bacik }
146938830018SJosef Bacik
147043b068caSJosef Bacik /*
147143b068caSJosef Bacik * At this point 'state' either contains 'start' or start is
147243b068caSJosef Bacik * before 'state'
147343b068caSJosef Bacik */
147438830018SJosef Bacik if (in_range(start, state->start, state->end - state->start + 1)) {
147538830018SJosef Bacik if (state->state & bits) {
147638830018SJosef Bacik /*
147738830018SJosef Bacik * |--range with bits sets--|
147838830018SJosef Bacik * |
147938830018SJosef Bacik * start
148038830018SJosef Bacik */
148138830018SJosef Bacik start = state->end + 1;
148238830018SJosef Bacik } else {
148338830018SJosef Bacik /*
148438830018SJosef Bacik * 'start' falls within a range that doesn't
148538830018SJosef Bacik * have the bits set, so take its start as the
148638830018SJosef Bacik * beginning of the desired range
148738830018SJosef Bacik *
148838830018SJosef Bacik * |--range with bits cleared----|
148938830018SJosef Bacik * |
149038830018SJosef Bacik * start
149138830018SJosef Bacik */
149238830018SJosef Bacik *start_ret = state->start;
149338830018SJosef Bacik break;
149438830018SJosef Bacik }
149538830018SJosef Bacik } else {
149638830018SJosef Bacik /*
149738830018SJosef Bacik * |---prev range---|---hole/unset---|---node range---|
149838830018SJosef Bacik * |
149938830018SJosef Bacik * start
150038830018SJosef Bacik *
150138830018SJosef Bacik * or
150238830018SJosef Bacik *
150338830018SJosef Bacik * |---hole/unset--||--first node--|
150438830018SJosef Bacik * 0 |
150538830018SJosef Bacik * start
150638830018SJosef Bacik */
150743b068caSJosef Bacik if (prev)
150843b068caSJosef Bacik *start_ret = prev->end + 1;
150943b068caSJosef Bacik else
151038830018SJosef Bacik *start_ret = 0;
151138830018SJosef Bacik break;
151238830018SJosef Bacik }
151338830018SJosef Bacik }
151438830018SJosef Bacik
151538830018SJosef Bacik /*
151638830018SJosef Bacik * Find the longest stretch from start until an entry which has the
151738830018SJosef Bacik * bits set
151838830018SJosef Bacik */
1519ccaeff92SJosef Bacik while (state) {
152038830018SJosef Bacik if (state->end >= start && !(state->state & bits)) {
152138830018SJosef Bacik *end_ret = state->end;
152238830018SJosef Bacik } else {
152338830018SJosef Bacik *end_ret = state->start - 1;
152438830018SJosef Bacik break;
152538830018SJosef Bacik }
1526ccaeff92SJosef Bacik state = next_state(state);
152738830018SJosef Bacik }
152838830018SJosef Bacik out:
152938830018SJosef Bacik spin_unlock(&tree->lock);
153038830018SJosef Bacik }
153138830018SJosef Bacik
1532e3974c66SJosef Bacik /*
15331ee51a06SFilipe Manana * Count the number of bytes in the tree that have a given bit(s) set for a
15341ee51a06SFilipe Manana * given range.
15351ee51a06SFilipe Manana *
15361ee51a06SFilipe Manana * @tree: The io tree to search.
15371ee51a06SFilipe Manana * @start: The start offset of the range. This value is updated to the
15381ee51a06SFilipe Manana * offset of the first byte found with the given bit(s), so it
15391ee51a06SFilipe Manana * can end up being bigger than the initial value.
15401ee51a06SFilipe Manana * @search_end: The end offset (inclusive value) of the search range.
15411ee51a06SFilipe Manana * @max_bytes: The maximum byte count we are interested. The search stops
15421ee51a06SFilipe Manana * once it reaches this count.
15431ee51a06SFilipe Manana * @bits: The bits the range must have in order to be accounted for.
15441ee51a06SFilipe Manana * If multiple bits are set, then only subranges that have all
15451ee51a06SFilipe Manana * the bits set are accounted for.
15461ee51a06SFilipe Manana * @contig: Indicate if we should ignore holes in the range or not. If
15471ee51a06SFilipe Manana * this is true, then stop once we find a hole.
15481ee51a06SFilipe Manana * @cached_state: A cached state to be used across multiple calls to this
15491ee51a06SFilipe Manana * function in order to speedup searches. Use NULL if this is
15501ee51a06SFilipe Manana * called only once or if each call does not start where the
15511ee51a06SFilipe Manana * previous one ended.
15521ee51a06SFilipe Manana *
15531ee51a06SFilipe Manana * Returns the total number of bytes found within the given range that have
15541ee51a06SFilipe Manana * all given bits set. If the returned number of bytes is greater than zero
15551ee51a06SFilipe Manana * then @start is updated with the offset of the first byte with the bits set.
1556e3974c66SJosef Bacik */
count_range_bits(struct extent_io_tree * tree,u64 * start,u64 search_end,u64 max_bytes,u32 bits,int contig,struct extent_state ** cached_state)1557e3974c66SJosef Bacik u64 count_range_bits(struct extent_io_tree *tree,
1558e3974c66SJosef Bacik u64 *start, u64 search_end, u64 max_bytes,
15598c6e53a7SFilipe Manana u32 bits, int contig,
15608c6e53a7SFilipe Manana struct extent_state **cached_state)
1561e3974c66SJosef Bacik {
15628c6e53a7SFilipe Manana struct extent_state *state = NULL;
15638c6e53a7SFilipe Manana struct extent_state *cached;
1564e3974c66SJosef Bacik u64 cur_start = *start;
1565e3974c66SJosef Bacik u64 total_bytes = 0;
1566e3974c66SJosef Bacik u64 last = 0;
1567e3974c66SJosef Bacik int found = 0;
1568e3974c66SJosef Bacik
15692f2e84caSFilipe Manana if (WARN_ON(search_end < cur_start))
1570e3974c66SJosef Bacik return 0;
1571e3974c66SJosef Bacik
1572e3974c66SJosef Bacik spin_lock(&tree->lock);
157371528e9eSJosef Bacik
15748c6e53a7SFilipe Manana if (!cached_state || !*cached_state)
15758c6e53a7SFilipe Manana goto search;
15768c6e53a7SFilipe Manana
15778c6e53a7SFilipe Manana cached = *cached_state;
15788c6e53a7SFilipe Manana
15798c6e53a7SFilipe Manana if (!extent_state_in_tree(cached))
15808c6e53a7SFilipe Manana goto search;
15818c6e53a7SFilipe Manana
15828c6e53a7SFilipe Manana if (cached->start <= cur_start && cur_start <= cached->end) {
15838c6e53a7SFilipe Manana state = cached;
15848c6e53a7SFilipe Manana } else if (cached->start > cur_start) {
15858c6e53a7SFilipe Manana struct extent_state *prev;
15868c6e53a7SFilipe Manana
15878c6e53a7SFilipe Manana /*
15888c6e53a7SFilipe Manana * The cached state starts after our search range's start. Check
15898c6e53a7SFilipe Manana * if the previous state record starts at or before the range we
15908c6e53a7SFilipe Manana * are looking for, and if so, use it - this is a common case
15918c6e53a7SFilipe Manana * when there are holes between records in the tree. If there is
15928c6e53a7SFilipe Manana * no previous state record, we can start from our cached state.
15938c6e53a7SFilipe Manana */
15948c6e53a7SFilipe Manana prev = prev_state(cached);
15958c6e53a7SFilipe Manana if (!prev)
15968c6e53a7SFilipe Manana state = cached;
15978c6e53a7SFilipe Manana else if (prev->start <= cur_start && cur_start <= prev->end)
15988c6e53a7SFilipe Manana state = prev;
15998c6e53a7SFilipe Manana }
16008c6e53a7SFilipe Manana
1601e3974c66SJosef Bacik /*
1602e3974c66SJosef Bacik * This search will find all the extents that end after our range
1603e3974c66SJosef Bacik * starts.
1604e3974c66SJosef Bacik */
16058c6e53a7SFilipe Manana search:
16068c6e53a7SFilipe Manana if (!state)
1607aa852dabSJosef Bacik state = tree_search(tree, cur_start);
16088c6e53a7SFilipe Manana
1609ccaeff92SJosef Bacik while (state) {
1610e3974c66SJosef Bacik if (state->start > search_end)
1611e3974c66SJosef Bacik break;
1612e3974c66SJosef Bacik if (contig && found && state->start > last + 1)
1613e3974c66SJosef Bacik break;
1614e3974c66SJosef Bacik if (state->end >= cur_start && (state->state & bits) == bits) {
1615e3974c66SJosef Bacik total_bytes += min(search_end, state->end) + 1 -
1616e3974c66SJosef Bacik max(cur_start, state->start);
1617e3974c66SJosef Bacik if (total_bytes >= max_bytes)
1618e3974c66SJosef Bacik break;
1619e3974c66SJosef Bacik if (!found) {
1620e3974c66SJosef Bacik *start = max(cur_start, state->start);
1621e3974c66SJosef Bacik found = 1;
1622e3974c66SJosef Bacik }
1623e3974c66SJosef Bacik last = state->end;
1624e3974c66SJosef Bacik } else if (contig && found) {
1625e3974c66SJosef Bacik break;
1626e3974c66SJosef Bacik }
1627ccaeff92SJosef Bacik state = next_state(state);
1628e3974c66SJosef Bacik }
16298c6e53a7SFilipe Manana
16308c6e53a7SFilipe Manana if (cached_state) {
16318c6e53a7SFilipe Manana free_extent_state(*cached_state);
16328c6e53a7SFilipe Manana *cached_state = state;
16338c6e53a7SFilipe Manana if (state)
16348c6e53a7SFilipe Manana refcount_inc(&state->refs);
16358c6e53a7SFilipe Manana }
16368c6e53a7SFilipe Manana
1637e3974c66SJosef Bacik spin_unlock(&tree->lock);
16388c6e53a7SFilipe Manana
1639e3974c66SJosef Bacik return total_bytes;
1640e3974c66SJosef Bacik }
1641e3974c66SJosef Bacik
1642e3974c66SJosef Bacik /*
164367da05b3SColin Ian King * Search a range in the state tree for a given mask. If 'filled' == 1, this
1644e3974c66SJosef Bacik * returns 1 only if every extent in the tree has the bits set. Otherwise, 1
1645e3974c66SJosef Bacik * is returned if any bit in the range is found set.
1646e3974c66SJosef Bacik */
test_range_bit(struct extent_io_tree * tree,u64 start,u64 end,u32 bits,int filled,struct extent_state * cached)1647e3974c66SJosef Bacik int test_range_bit(struct extent_io_tree *tree, u64 start, u64 end,
1648e3974c66SJosef Bacik u32 bits, int filled, struct extent_state *cached)
1649e3974c66SJosef Bacik {
1650e3974c66SJosef Bacik struct extent_state *state = NULL;
1651e3974c66SJosef Bacik int bitset = 0;
1652e3974c66SJosef Bacik
1653e3974c66SJosef Bacik spin_lock(&tree->lock);
1654e3974c66SJosef Bacik if (cached && extent_state_in_tree(cached) && cached->start <= start &&
1655e3974c66SJosef Bacik cached->end > start)
1656aa852dabSJosef Bacik state = cached;
1657e3974c66SJosef Bacik else
1658aa852dabSJosef Bacik state = tree_search(tree, start);
1659ccaeff92SJosef Bacik while (state && start <= end) {
1660e3974c66SJosef Bacik if (filled && state->start > start) {
1661e3974c66SJosef Bacik bitset = 0;
1662e3974c66SJosef Bacik break;
1663e3974c66SJosef Bacik }
1664e3974c66SJosef Bacik
1665e3974c66SJosef Bacik if (state->start > end)
1666e3974c66SJosef Bacik break;
1667e3974c66SJosef Bacik
1668e3974c66SJosef Bacik if (state->state & bits) {
1669e3974c66SJosef Bacik bitset = 1;
1670e3974c66SJosef Bacik if (!filled)
1671e3974c66SJosef Bacik break;
1672e3974c66SJosef Bacik } else if (filled) {
1673e3974c66SJosef Bacik bitset = 0;
1674e3974c66SJosef Bacik break;
1675e3974c66SJosef Bacik }
1676e3974c66SJosef Bacik
1677e3974c66SJosef Bacik if (state->end == (u64)-1)
1678e3974c66SJosef Bacik break;
1679e3974c66SJosef Bacik
1680e3974c66SJosef Bacik start = state->end + 1;
1681e3974c66SJosef Bacik if (start > end)
1682e3974c66SJosef Bacik break;
1683ccaeff92SJosef Bacik state = next_state(state);
1684ccaeff92SJosef Bacik }
1685ccaeff92SJosef Bacik
1686ccaeff92SJosef Bacik /* We ran out of states and were still inside of our range. */
1687ccaeff92SJosef Bacik if (filled && !state)
1688e3974c66SJosef Bacik bitset = 0;
1689e3974c66SJosef Bacik spin_unlock(&tree->lock);
1690e3974c66SJosef Bacik return bitset;
1691e3974c66SJosef Bacik }
1692e3974c66SJosef Bacik
1693a6631887SJosef Bacik /* Wrappers around set/clear extent bit */
set_record_extent_bits(struct extent_io_tree * tree,u64 start,u64 end,u32 bits,struct extent_changeset * changeset)1694a6631887SJosef Bacik int set_record_extent_bits(struct extent_io_tree *tree, u64 start, u64 end,
1695a6631887SJosef Bacik u32 bits, struct extent_changeset *changeset)
1696a6631887SJosef Bacik {
1697a6631887SJosef Bacik /*
1698a6631887SJosef Bacik * We don't support EXTENT_LOCKED yet, as current changeset will
1699a6631887SJosef Bacik * record any bits changed, so for EXTENT_LOCKED case, it will
1700a6631887SJosef Bacik * either fail with -EEXIST or changeset will record the whole
1701a6631887SJosef Bacik * range.
1702a6631887SJosef Bacik */
1703a6631887SJosef Bacik ASSERT(!(bits & EXTENT_LOCKED));
1704a6631887SJosef Bacik
17051d126800SDavid Sterba return __set_extent_bit(tree, start, end, bits, NULL, NULL, NULL, changeset);
1706a6631887SJosef Bacik }
1707a6631887SJosef Bacik
clear_record_extent_bits(struct extent_io_tree * tree,u64 start,u64 end,u32 bits,struct extent_changeset * changeset)1708a6631887SJosef Bacik int clear_record_extent_bits(struct extent_io_tree *tree, u64 start, u64 end,
1709a6631887SJosef Bacik u32 bits, struct extent_changeset *changeset)
1710a6631887SJosef Bacik {
1711a6631887SJosef Bacik /*
1712a6631887SJosef Bacik * Don't support EXTENT_LOCKED case, same reason as
1713a6631887SJosef Bacik * set_record_extent_bits().
1714a6631887SJosef Bacik */
1715a6631887SJosef Bacik ASSERT(!(bits & EXTENT_LOCKED));
1716a6631887SJosef Bacik
17171d126800SDavid Sterba return __clear_extent_bit(tree, start, end, bits, NULL, changeset);
1718a6631887SJosef Bacik }
1719a6631887SJosef Bacik
try_lock_extent(struct extent_io_tree * tree,u64 start,u64 end,struct extent_state ** cached)172083ae4133SJosef Bacik int try_lock_extent(struct extent_io_tree *tree, u64 start, u64 end,
172183ae4133SJosef Bacik struct extent_state **cached)
1722a6631887SJosef Bacik {
1723a6631887SJosef Bacik int err;
1724a6631887SJosef Bacik u64 failed_start;
1725a6631887SJosef Bacik
1726994bcd1eSJosef Bacik err = __set_extent_bit(tree, start, end, EXTENT_LOCKED, &failed_start,
17271d126800SDavid Sterba NULL, cached, NULL);
1728a6631887SJosef Bacik if (err == -EEXIST) {
1729a6631887SJosef Bacik if (failed_start > start)
1730a6631887SJosef Bacik clear_extent_bit(tree, start, failed_start - 1,
173183ae4133SJosef Bacik EXTENT_LOCKED, cached);
1732a6631887SJosef Bacik return 0;
1733a6631887SJosef Bacik }
1734a6631887SJosef Bacik return 1;
1735a6631887SJosef Bacik }
1736a6631887SJosef Bacik
173738830018SJosef Bacik /*
173838830018SJosef Bacik * Either insert or lock state struct between start and end use mask to tell
173938830018SJosef Bacik * us if waiting is desired.
174038830018SJosef Bacik */
lock_extent(struct extent_io_tree * tree,u64 start,u64 end,struct extent_state ** cached_state)1741570eb97bSJosef Bacik int lock_extent(struct extent_io_tree *tree, u64 start, u64 end,
174238830018SJosef Bacik struct extent_state **cached_state)
174338830018SJosef Bacik {
1744123a7f00SJosef Bacik struct extent_state *failed_state = NULL;
174538830018SJosef Bacik int err;
174638830018SJosef Bacik u64 failed_start;
174738830018SJosef Bacik
17489e769bd7SJosef Bacik err = __set_extent_bit(tree, start, end, EXTENT_LOCKED, &failed_start,
17491d126800SDavid Sterba &failed_state, cached_state, NULL);
17509e769bd7SJosef Bacik while (err == -EEXIST) {
17519e769bd7SJosef Bacik if (failed_start != start)
17529e769bd7SJosef Bacik clear_extent_bit(tree, start, failed_start - 1,
17539e769bd7SJosef Bacik EXTENT_LOCKED, cached_state);
17549e769bd7SJosef Bacik
1755123a7f00SJosef Bacik wait_extent_bit(tree, failed_start, end, EXTENT_LOCKED,
1756123a7f00SJosef Bacik &failed_state);
1757994bcd1eSJosef Bacik err = __set_extent_bit(tree, start, end, EXTENT_LOCKED,
1758123a7f00SJosef Bacik &failed_start, &failed_state,
17591d126800SDavid Sterba cached_state, NULL);
176038830018SJosef Bacik }
176138830018SJosef Bacik return err;
176238830018SJosef Bacik }
176338830018SJosef Bacik
extent_state_free_cachep(void)176483cf709aSJosef Bacik void __cold extent_state_free_cachep(void)
176583cf709aSJosef Bacik {
176683cf709aSJosef Bacik btrfs_extent_state_leak_debug_check();
176783cf709aSJosef Bacik kmem_cache_destroy(extent_state_cache);
176883cf709aSJosef Bacik }
176983cf709aSJosef Bacik
extent_state_init_cachep(void)177083cf709aSJosef Bacik int __init extent_state_init_cachep(void)
177183cf709aSJosef Bacik {
177283cf709aSJosef Bacik extent_state_cache = kmem_cache_create("btrfs_extent_state",
177383cf709aSJosef Bacik sizeof(struct extent_state), 0,
177483cf709aSJosef Bacik SLAB_MEM_SPREAD, NULL);
177583cf709aSJosef Bacik if (!extent_state_cache)
177683cf709aSJosef Bacik return -ENOMEM;
177783cf709aSJosef Bacik
177883cf709aSJosef Bacik return 0;
177983cf709aSJosef Bacik }
1780