Loading...
Note: File does not exist in v3.1.
1// SPDX-License-Identifier: GPL-2.0
2
3#include <linux/slab.h>
4#include <trace/events/btrfs.h>
5#include "messages.h"
6#include "ctree.h"
7#include "extent_io.h"
8#include "extent-io-tree.h"
9#include "btrfs_inode.h"
10
11static struct kmem_cache *extent_state_cache;
12
13static inline bool extent_state_in_tree(const struct extent_state *state)
14{
15 return !RB_EMPTY_NODE(&state->rb_node);
16}
17
18#ifdef CONFIG_BTRFS_DEBUG
19static LIST_HEAD(states);
20static DEFINE_SPINLOCK(leak_lock);
21
22static inline void btrfs_leak_debug_add_state(struct extent_state *state)
23{
24 unsigned long flags;
25
26 spin_lock_irqsave(&leak_lock, flags);
27 list_add(&state->leak_list, &states);
28 spin_unlock_irqrestore(&leak_lock, flags);
29}
30
31static inline void btrfs_leak_debug_del_state(struct extent_state *state)
32{
33 unsigned long flags;
34
35 spin_lock_irqsave(&leak_lock, flags);
36 list_del(&state->leak_list);
37 spin_unlock_irqrestore(&leak_lock, flags);
38}
39
40static inline void btrfs_extent_state_leak_debug_check(void)
41{
42 struct extent_state *state;
43
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 WARN_ON_ONCE(1);
52 kmem_cache_free(extent_state_cache, state);
53 }
54}
55
56#define btrfs_debug_check_extent_io_range(tree, start, end) \
57 __btrfs_debug_check_extent_io_range(__func__, (tree), (start), (end))
58static inline void __btrfs_debug_check_extent_io_range(const char *caller,
59 struct extent_io_tree *tree,
60 u64 start, u64 end)
61{
62 const struct btrfs_inode *inode;
63 u64 isize;
64
65 if (tree->owner != IO_TREE_INODE_IO)
66 return;
67
68 inode = extent_io_tree_to_inode_const(tree);
69 isize = i_size_read(&inode->vfs_inode);
70 if (end >= PAGE_SIZE && (end % 2) == 0 && end != isize - 1) {
71 btrfs_debug_rl(inode->root->fs_info,
72 "%s: ino %llu isize %llu odd range [%llu,%llu]",
73 caller, btrfs_ino(inode), isize, start, end);
74 }
75}
76#else
77#define btrfs_leak_debug_add_state(state) do {} while (0)
78#define btrfs_leak_debug_del_state(state) do {} while (0)
79#define btrfs_extent_state_leak_debug_check() do {} while (0)
80#define btrfs_debug_check_extent_io_range(c, s, e) do {} while (0)
81#endif
82
83
84/*
85 * The only tree allowed to set the inode is IO_TREE_INODE_IO.
86 */
87static bool is_inode_io_tree(const struct extent_io_tree *tree)
88{
89 return tree->owner == IO_TREE_INODE_IO;
90}
91
92/* Return the inode if it's valid for the given tree, otherwise NULL. */
93struct btrfs_inode *extent_io_tree_to_inode(struct extent_io_tree *tree)
94{
95 if (tree->owner == IO_TREE_INODE_IO)
96 return tree->inode;
97 return NULL;
98}
99
100/* Read-only access to the inode. */
101const struct btrfs_inode *extent_io_tree_to_inode_const(const struct extent_io_tree *tree)
102{
103 if (tree->owner == IO_TREE_INODE_IO)
104 return tree->inode;
105 return NULL;
106}
107
108/* For read-only access to fs_info. */
109const struct btrfs_fs_info *extent_io_tree_to_fs_info(const struct extent_io_tree *tree)
110{
111 if (tree->owner == IO_TREE_INODE_IO)
112 return tree->inode->root->fs_info;
113 return tree->fs_info;
114}
115
116void extent_io_tree_init(struct btrfs_fs_info *fs_info,
117 struct extent_io_tree *tree, unsigned int owner)
118{
119 tree->state = RB_ROOT;
120 spin_lock_init(&tree->lock);
121 tree->fs_info = fs_info;
122 tree->owner = owner;
123}
124
125/*
126 * Empty an io tree, removing and freeing every extent state record from the
127 * tree. This should be called once we are sure no other task can access the
128 * tree anymore, so no tree updates happen after we empty the tree and there
129 * aren't any waiters on any extent state record (EXTENT_LOCK_BITS are never
130 * set on any extent state when calling this function).
131 */
132void extent_io_tree_release(struct extent_io_tree *tree)
133{
134 struct rb_root root;
135 struct extent_state *state;
136 struct extent_state *tmp;
137
138 spin_lock(&tree->lock);
139 root = tree->state;
140 tree->state = RB_ROOT;
141 rbtree_postorder_for_each_entry_safe(state, tmp, &root, rb_node) {
142 /* Clear node to keep free_extent_state() happy. */
143 RB_CLEAR_NODE(&state->rb_node);
144 ASSERT(!(state->state & EXTENT_LOCK_BITS));
145 /*
146 * No need for a memory barrier here, as we are holding the tree
147 * lock and we only change the waitqueue while holding that lock
148 * (see wait_extent_bit()).
149 */
150 ASSERT(!waitqueue_active(&state->wq));
151 free_extent_state(state);
152 cond_resched_lock(&tree->lock);
153 }
154 /*
155 * Should still be empty even after a reschedule, no other task should
156 * be accessing the tree anymore.
157 */
158 ASSERT(RB_EMPTY_ROOT(&tree->state));
159 spin_unlock(&tree->lock);
160}
161
162static struct extent_state *alloc_extent_state(gfp_t mask)
163{
164 struct extent_state *state;
165
166 /*
167 * The given mask might be not appropriate for the slab allocator,
168 * drop the unsupported bits
169 */
170 mask &= ~(__GFP_DMA32|__GFP_HIGHMEM);
171 state = kmem_cache_alloc(extent_state_cache, mask);
172 if (!state)
173 return state;
174 state->state = 0;
175 RB_CLEAR_NODE(&state->rb_node);
176 btrfs_leak_debug_add_state(state);
177 refcount_set(&state->refs, 1);
178 init_waitqueue_head(&state->wq);
179 trace_alloc_extent_state(state, mask, _RET_IP_);
180 return state;
181}
182
183static struct extent_state *alloc_extent_state_atomic(struct extent_state *prealloc)
184{
185 if (!prealloc)
186 prealloc = alloc_extent_state(GFP_ATOMIC);
187
188 return prealloc;
189}
190
191void free_extent_state(struct extent_state *state)
192{
193 if (!state)
194 return;
195 if (refcount_dec_and_test(&state->refs)) {
196 WARN_ON(extent_state_in_tree(state));
197 btrfs_leak_debug_del_state(state);
198 trace_free_extent_state(state, _RET_IP_);
199 kmem_cache_free(extent_state_cache, state);
200 }
201}
202
203static int add_extent_changeset(struct extent_state *state, u32 bits,
204 struct extent_changeset *changeset,
205 int set)
206{
207 int ret;
208
209 if (!changeset)
210 return 0;
211 if (set && (state->state & bits) == bits)
212 return 0;
213 if (!set && (state->state & bits) == 0)
214 return 0;
215 changeset->bytes_changed += state->end - state->start + 1;
216 ret = ulist_add(&changeset->range_changed, state->start, state->end,
217 GFP_ATOMIC);
218 return ret;
219}
220
221static inline struct extent_state *next_state(struct extent_state *state)
222{
223 struct rb_node *next = rb_next(&state->rb_node);
224
225 if (next)
226 return rb_entry(next, struct extent_state, rb_node);
227 else
228 return NULL;
229}
230
231static inline struct extent_state *prev_state(struct extent_state *state)
232{
233 struct rb_node *next = rb_prev(&state->rb_node);
234
235 if (next)
236 return rb_entry(next, struct extent_state, rb_node);
237 else
238 return NULL;
239}
240
241/*
242 * Search @tree for an entry that contains @offset. Such entry would have
243 * entry->start <= offset && entry->end >= offset.
244 *
245 * @tree: the tree to search
246 * @offset: offset that should fall within an entry in @tree
247 * @node_ret: pointer where new node should be anchored (used when inserting an
248 * entry in the tree)
249 * @parent_ret: points to entry which would have been the parent of the entry,
250 * containing @offset
251 *
252 * Return a pointer to the entry that contains @offset byte address and don't change
253 * @node_ret and @parent_ret.
254 *
255 * If no such entry exists, return pointer to entry that ends before @offset
256 * and fill parameters @node_ret and @parent_ret, ie. does not return NULL.
257 */
258static inline struct extent_state *tree_search_for_insert(struct extent_io_tree *tree,
259 u64 offset,
260 struct rb_node ***node_ret,
261 struct rb_node **parent_ret)
262{
263 struct rb_root *root = &tree->state;
264 struct rb_node **node = &root->rb_node;
265 struct rb_node *prev = NULL;
266 struct extent_state *entry = NULL;
267
268 while (*node) {
269 prev = *node;
270 entry = rb_entry(prev, struct extent_state, rb_node);
271
272 if (offset < entry->start)
273 node = &(*node)->rb_left;
274 else if (offset > entry->end)
275 node = &(*node)->rb_right;
276 else
277 return entry;
278 }
279
280 if (node_ret)
281 *node_ret = node;
282 if (parent_ret)
283 *parent_ret = prev;
284
285 /* Search neighbors until we find the first one past the end */
286 while (entry && offset > entry->end)
287 entry = next_state(entry);
288
289 return entry;
290}
291
292/*
293 * Search offset in the tree or fill neighbor rbtree node pointers.
294 *
295 * @tree: the tree to search
296 * @offset: offset that should fall within an entry in @tree
297 * @next_ret: pointer to the first entry whose range ends after @offset
298 * @prev_ret: pointer to the first entry whose range begins before @offset
299 *
300 * Return a pointer to the entry that contains @offset byte address. If no
301 * such entry exists, then return NULL and fill @prev_ret and @next_ret.
302 * Otherwise return the found entry and other pointers are left untouched.
303 */
304static struct extent_state *tree_search_prev_next(struct extent_io_tree *tree,
305 u64 offset,
306 struct extent_state **prev_ret,
307 struct extent_state **next_ret)
308{
309 struct rb_root *root = &tree->state;
310 struct rb_node **node = &root->rb_node;
311 struct extent_state *orig_prev;
312 struct extent_state *entry = NULL;
313
314 ASSERT(prev_ret);
315 ASSERT(next_ret);
316
317 while (*node) {
318 entry = rb_entry(*node, struct extent_state, rb_node);
319
320 if (offset < entry->start)
321 node = &(*node)->rb_left;
322 else if (offset > entry->end)
323 node = &(*node)->rb_right;
324 else
325 return entry;
326 }
327
328 orig_prev = entry;
329 while (entry && offset > entry->end)
330 entry = next_state(entry);
331 *next_ret = entry;
332 entry = orig_prev;
333
334 while (entry && offset < entry->start)
335 entry = prev_state(entry);
336 *prev_ret = entry;
337
338 return NULL;
339}
340
341/*
342 * Inexact rb-tree search, return the next entry if @offset is not found
343 */
344static inline struct extent_state *tree_search(struct extent_io_tree *tree, u64 offset)
345{
346 return tree_search_for_insert(tree, offset, NULL, NULL);
347}
348
349static void extent_io_tree_panic(const struct extent_io_tree *tree,
350 const struct extent_state *state,
351 const char *opname,
352 int err)
353{
354 btrfs_panic(extent_io_tree_to_fs_info(tree), err,
355 "extent io tree error on %s state start %llu end %llu",
356 opname, state->start, state->end);
357}
358
359static void merge_prev_state(struct extent_io_tree *tree, struct extent_state *state)
360{
361 struct extent_state *prev;
362
363 prev = prev_state(state);
364 if (prev && prev->end == state->start - 1 && prev->state == state->state) {
365 if (is_inode_io_tree(tree))
366 btrfs_merge_delalloc_extent(extent_io_tree_to_inode(tree),
367 state, prev);
368 state->start = prev->start;
369 rb_erase(&prev->rb_node, &tree->state);
370 RB_CLEAR_NODE(&prev->rb_node);
371 free_extent_state(prev);
372 }
373}
374
375static void merge_next_state(struct extent_io_tree *tree, struct extent_state *state)
376{
377 struct extent_state *next;
378
379 next = next_state(state);
380 if (next && next->start == state->end + 1 && next->state == state->state) {
381 if (is_inode_io_tree(tree))
382 btrfs_merge_delalloc_extent(extent_io_tree_to_inode(tree),
383 state, next);
384 state->end = next->end;
385 rb_erase(&next->rb_node, &tree->state);
386 RB_CLEAR_NODE(&next->rb_node);
387 free_extent_state(next);
388 }
389}
390
391/*
392 * Utility function to look for merge candidates inside a given range. Any
393 * extents with matching state are merged together into a single extent in the
394 * tree. Extents with EXTENT_IO in their state field are not merged because
395 * the end_io handlers need to be able to do operations on them without
396 * sleeping (or doing allocations/splits).
397 *
398 * This should be called with the tree lock held.
399 */
400static void merge_state(struct extent_io_tree *tree, struct extent_state *state)
401{
402 if (state->state & (EXTENT_LOCK_BITS | EXTENT_BOUNDARY))
403 return;
404
405 merge_prev_state(tree, state);
406 merge_next_state(tree, state);
407}
408
409static void set_state_bits(struct extent_io_tree *tree,
410 struct extent_state *state,
411 u32 bits, struct extent_changeset *changeset)
412{
413 u32 bits_to_set = bits & ~EXTENT_CTLBITS;
414 int ret;
415
416 if (is_inode_io_tree(tree))
417 btrfs_set_delalloc_extent(extent_io_tree_to_inode(tree), state, bits);
418
419 ret = add_extent_changeset(state, bits_to_set, changeset, 1);
420 BUG_ON(ret < 0);
421 state->state |= bits_to_set;
422}
423
424/*
425 * Insert an extent_state struct into the tree. 'bits' are set on the
426 * struct before it is inserted.
427 *
428 * Returns a pointer to the struct extent_state record containing the range
429 * requested for insertion, which may be the same as the given struct or it
430 * may be an existing record in the tree that was expanded to accommodate the
431 * requested range. In case of an extent_state different from the one that was
432 * given, the later can be freed or reused by the caller.
433 *
434 * On error it returns an error pointer.
435 *
436 * The tree lock is not taken internally. This is a utility function and
437 * probably isn't what you want to call (see set/clear_extent_bit).
438 */
439static struct extent_state *insert_state(struct extent_io_tree *tree,
440 struct extent_state *state,
441 u32 bits,
442 struct extent_changeset *changeset)
443{
444 struct rb_node **node;
445 struct rb_node *parent = NULL;
446 const u64 start = state->start - 1;
447 const u64 end = state->end + 1;
448 const bool try_merge = !(bits & (EXTENT_LOCK_BITS | EXTENT_BOUNDARY));
449
450 set_state_bits(tree, state, bits, changeset);
451
452 node = &tree->state.rb_node;
453 while (*node) {
454 struct extent_state *entry;
455
456 parent = *node;
457 entry = rb_entry(parent, struct extent_state, rb_node);
458
459 if (state->end < entry->start) {
460 if (try_merge && end == entry->start &&
461 state->state == entry->state) {
462 if (is_inode_io_tree(tree))
463 btrfs_merge_delalloc_extent(
464 extent_io_tree_to_inode(tree),
465 state, entry);
466 entry->start = state->start;
467 merge_prev_state(tree, entry);
468 state->state = 0;
469 return entry;
470 }
471 node = &(*node)->rb_left;
472 } else if (state->end > entry->end) {
473 if (try_merge && entry->end == start &&
474 state->state == entry->state) {
475 if (is_inode_io_tree(tree))
476 btrfs_merge_delalloc_extent(
477 extent_io_tree_to_inode(tree),
478 state, entry);
479 entry->end = state->end;
480 merge_next_state(tree, entry);
481 state->state = 0;
482 return entry;
483 }
484 node = &(*node)->rb_right;
485 } else {
486 return ERR_PTR(-EEXIST);
487 }
488 }
489
490 rb_link_node(&state->rb_node, parent, node);
491 rb_insert_color(&state->rb_node, &tree->state);
492
493 return state;
494}
495
496/*
497 * Insert state to @tree to the location given by @node and @parent.
498 */
499static void insert_state_fast(struct extent_io_tree *tree,
500 struct extent_state *state, struct rb_node **node,
501 struct rb_node *parent, unsigned bits,
502 struct extent_changeset *changeset)
503{
504 set_state_bits(tree, state, bits, changeset);
505 rb_link_node(&state->rb_node, parent, node);
506 rb_insert_color(&state->rb_node, &tree->state);
507 merge_state(tree, state);
508}
509
510/*
511 * Split a given extent state struct in two, inserting the preallocated
512 * struct 'prealloc' as the newly created second half. 'split' indicates an
513 * offset inside 'orig' where it should be split.
514 *
515 * Before calling,
516 * the tree has 'orig' at [orig->start, orig->end]. After calling, there
517 * are two extent state structs in the tree:
518 * prealloc: [orig->start, split - 1]
519 * orig: [ split, orig->end ]
520 *
521 * The tree locks are not taken by this function. They need to be held
522 * by the caller.
523 */
524static int split_state(struct extent_io_tree *tree, struct extent_state *orig,
525 struct extent_state *prealloc, u64 split)
526{
527 struct rb_node *parent = NULL;
528 struct rb_node **node;
529
530 if (is_inode_io_tree(tree))
531 btrfs_split_delalloc_extent(extent_io_tree_to_inode(tree), orig,
532 split);
533
534 prealloc->start = orig->start;
535 prealloc->end = split - 1;
536 prealloc->state = orig->state;
537 orig->start = split;
538
539 parent = &orig->rb_node;
540 node = &parent;
541 while (*node) {
542 struct extent_state *entry;
543
544 parent = *node;
545 entry = rb_entry(parent, struct extent_state, rb_node);
546
547 if (prealloc->end < entry->start) {
548 node = &(*node)->rb_left;
549 } else if (prealloc->end > entry->end) {
550 node = &(*node)->rb_right;
551 } else {
552 free_extent_state(prealloc);
553 return -EEXIST;
554 }
555 }
556
557 rb_link_node(&prealloc->rb_node, parent, node);
558 rb_insert_color(&prealloc->rb_node, &tree->state);
559
560 return 0;
561}
562
563/*
564 * Utility function to clear some bits in an extent state struct. It will
565 * optionally wake up anyone waiting on this state (wake == 1).
566 *
567 * If no bits are set on the state struct after clearing things, the
568 * struct is freed and removed from the tree
569 */
570static struct extent_state *clear_state_bit(struct extent_io_tree *tree,
571 struct extent_state *state,
572 u32 bits, int wake,
573 struct extent_changeset *changeset)
574{
575 struct extent_state *next;
576 u32 bits_to_clear = bits & ~EXTENT_CTLBITS;
577 int ret;
578
579 if (is_inode_io_tree(tree))
580 btrfs_clear_delalloc_extent(extent_io_tree_to_inode(tree), state,
581 bits);
582
583 ret = add_extent_changeset(state, bits_to_clear, changeset, 0);
584 BUG_ON(ret < 0);
585 state->state &= ~bits_to_clear;
586 if (wake)
587 wake_up(&state->wq);
588 if (state->state == 0) {
589 next = next_state(state);
590 if (extent_state_in_tree(state)) {
591 rb_erase(&state->rb_node, &tree->state);
592 RB_CLEAR_NODE(&state->rb_node);
593 free_extent_state(state);
594 } else {
595 WARN_ON(1);
596 }
597 } else {
598 merge_state(tree, state);
599 next = next_state(state);
600 }
601 return next;
602}
603
604/*
605 * Detect if extent bits request NOWAIT semantics and set the gfp mask accordingly,
606 * unset the EXTENT_NOWAIT bit.
607 */
608static void set_gfp_mask_from_bits(u32 *bits, gfp_t *mask)
609{
610 *mask = (*bits & EXTENT_NOWAIT ? GFP_NOWAIT : GFP_NOFS);
611 *bits &= EXTENT_NOWAIT - 1;
612}
613
614/*
615 * Clear some bits on a range in the tree. This may require splitting or
616 * inserting elements in the tree, so the gfp mask is used to indicate which
617 * allocations or sleeping are allowed.
618 *
619 * The range [start, end] is inclusive.
620 *
621 * This takes the tree lock, and returns 0 on success and < 0 on error.
622 */
623int __clear_extent_bit(struct extent_io_tree *tree, u64 start, u64 end,
624 u32 bits, struct extent_state **cached_state,
625 struct extent_changeset *changeset)
626{
627 struct extent_state *state;
628 struct extent_state *cached;
629 struct extent_state *prealloc = NULL;
630 u64 last_end;
631 int err;
632 int clear = 0;
633 int wake;
634 int delete = (bits & EXTENT_CLEAR_ALL_BITS);
635 gfp_t mask;
636
637 set_gfp_mask_from_bits(&bits, &mask);
638 btrfs_debug_check_extent_io_range(tree, start, end);
639 trace_btrfs_clear_extent_bit(tree, start, end - start + 1, bits);
640
641 if (delete)
642 bits |= ~EXTENT_CTLBITS;
643
644 if (bits & EXTENT_DELALLOC)
645 bits |= EXTENT_NORESERVE;
646
647 wake = ((bits & EXTENT_LOCK_BITS) ? 1 : 0);
648 if (bits & (EXTENT_LOCK_BITS | EXTENT_BOUNDARY))
649 clear = 1;
650again:
651 if (!prealloc) {
652 /*
653 * Don't care for allocation failure here because we might end
654 * up not needing the pre-allocated extent state at all, which
655 * is the case if we only have in the tree extent states that
656 * cover our input range and don't cover too any other range.
657 * If we end up needing a new extent state we allocate it later.
658 */
659 prealloc = alloc_extent_state(mask);
660 }
661
662 spin_lock(&tree->lock);
663 if (cached_state) {
664 cached = *cached_state;
665
666 if (clear) {
667 *cached_state = NULL;
668 cached_state = NULL;
669 }
670
671 if (cached && extent_state_in_tree(cached) &&
672 cached->start <= start && cached->end > start) {
673 if (clear)
674 refcount_dec(&cached->refs);
675 state = cached;
676 goto hit_next;
677 }
678 if (clear)
679 free_extent_state(cached);
680 }
681
682 /* This search will find the extents that end after our range starts. */
683 state = tree_search(tree, start);
684 if (!state)
685 goto out;
686hit_next:
687 if (state->start > end)
688 goto out;
689 WARN_ON(state->end < start);
690 last_end = state->end;
691
692 /* The state doesn't have the wanted bits, go ahead. */
693 if (!(state->state & bits)) {
694 state = next_state(state);
695 goto next;
696 }
697
698 /*
699 * | ---- desired range ---- |
700 * | state | or
701 * | ------------- state -------------- |
702 *
703 * We need to split the extent we found, and may flip bits on second
704 * half.
705 *
706 * If the extent we found extends past our range, we just split and
707 * search again. It'll get split again the next time though.
708 *
709 * If the extent we found is inside our range, we clear the desired bit
710 * on it.
711 */
712
713 if (state->start < start) {
714 prealloc = alloc_extent_state_atomic(prealloc);
715 if (!prealloc)
716 goto search_again;
717 err = split_state(tree, state, prealloc, start);
718 if (err)
719 extent_io_tree_panic(tree, state, "split", err);
720
721 prealloc = NULL;
722 if (err)
723 goto out;
724 if (state->end <= end) {
725 state = clear_state_bit(tree, state, bits, wake, changeset);
726 goto next;
727 }
728 goto search_again;
729 }
730 /*
731 * | ---- desired range ---- |
732 * | state |
733 * We need to split the extent, and clear the bit on the first half.
734 */
735 if (state->start <= end && state->end > end) {
736 prealloc = alloc_extent_state_atomic(prealloc);
737 if (!prealloc)
738 goto search_again;
739 err = split_state(tree, state, prealloc, end + 1);
740 if (err)
741 extent_io_tree_panic(tree, state, "split", err);
742
743 if (wake)
744 wake_up(&state->wq);
745
746 clear_state_bit(tree, prealloc, bits, wake, changeset);
747
748 prealloc = NULL;
749 goto out;
750 }
751
752 state = clear_state_bit(tree, state, bits, wake, changeset);
753next:
754 if (last_end == (u64)-1)
755 goto out;
756 start = last_end + 1;
757 if (start <= end && state && !need_resched())
758 goto hit_next;
759
760search_again:
761 if (start > end)
762 goto out;
763 spin_unlock(&tree->lock);
764 if (gfpflags_allow_blocking(mask))
765 cond_resched();
766 goto again;
767
768out:
769 spin_unlock(&tree->lock);
770 if (prealloc)
771 free_extent_state(prealloc);
772
773 return 0;
774
775}
776
777/*
778 * Wait for one or more bits to clear on a range in the state tree.
779 * The range [start, end] is inclusive.
780 * The tree lock is taken by this function
781 */
782static void wait_extent_bit(struct extent_io_tree *tree, u64 start, u64 end,
783 u32 bits, struct extent_state **cached_state)
784{
785 struct extent_state *state;
786
787 btrfs_debug_check_extent_io_range(tree, start, end);
788
789 spin_lock(&tree->lock);
790again:
791 /*
792 * Maintain cached_state, as we may not remove it from the tree if there
793 * are more bits than the bits we're waiting on set on this state.
794 */
795 if (cached_state && *cached_state) {
796 state = *cached_state;
797 if (extent_state_in_tree(state) &&
798 state->start <= start && start < state->end)
799 goto process_node;
800 }
801 while (1) {
802 /*
803 * This search will find all the extents that end after our
804 * range starts.
805 */
806 state = tree_search(tree, start);
807process_node:
808 if (!state)
809 break;
810 if (state->start > end)
811 goto out;
812
813 if (state->state & bits) {
814 DEFINE_WAIT(wait);
815
816 start = state->start;
817 refcount_inc(&state->refs);
818 prepare_to_wait(&state->wq, &wait, TASK_UNINTERRUPTIBLE);
819 spin_unlock(&tree->lock);
820 schedule();
821 spin_lock(&tree->lock);
822 finish_wait(&state->wq, &wait);
823 free_extent_state(state);
824 goto again;
825 }
826 start = state->end + 1;
827
828 if (start > end)
829 break;
830
831 if (!cond_resched_lock(&tree->lock)) {
832 state = next_state(state);
833 goto process_node;
834 }
835 }
836out:
837 /* This state is no longer useful, clear it and free it up. */
838 if (cached_state && *cached_state) {
839 state = *cached_state;
840 *cached_state = NULL;
841 free_extent_state(state);
842 }
843 spin_unlock(&tree->lock);
844}
845
846static void cache_state_if_flags(struct extent_state *state,
847 struct extent_state **cached_ptr,
848 unsigned flags)
849{
850 if (cached_ptr && !(*cached_ptr)) {
851 if (!flags || (state->state & flags)) {
852 *cached_ptr = state;
853 refcount_inc(&state->refs);
854 }
855 }
856}
857
858static void cache_state(struct extent_state *state,
859 struct extent_state **cached_ptr)
860{
861 return cache_state_if_flags(state, cached_ptr, EXTENT_LOCK_BITS | EXTENT_BOUNDARY);
862}
863
864/*
865 * Find the first state struct with 'bits' set after 'start', and return it.
866 * tree->lock must be held. NULL will returned if nothing was found after
867 * 'start'.
868 */
869static struct extent_state *find_first_extent_bit_state(struct extent_io_tree *tree,
870 u64 start, u32 bits)
871{
872 struct extent_state *state;
873
874 /*
875 * This search will find all the extents that end after our range
876 * starts.
877 */
878 state = tree_search(tree, start);
879 while (state) {
880 if (state->end >= start && (state->state & bits))
881 return state;
882 state = next_state(state);
883 }
884 return NULL;
885}
886
887/*
888 * Find the first offset in the io tree with one or more @bits set.
889 *
890 * Note: If there are multiple bits set in @bits, any of them will match.
891 *
892 * Return true if we find something, and update @start_ret and @end_ret.
893 * Return false if we found nothing.
894 */
895bool find_first_extent_bit(struct extent_io_tree *tree, u64 start,
896 u64 *start_ret, u64 *end_ret, u32 bits,
897 struct extent_state **cached_state)
898{
899 struct extent_state *state;
900 bool ret = false;
901
902 spin_lock(&tree->lock);
903 if (cached_state && *cached_state) {
904 state = *cached_state;
905 if (state->end == start - 1 && extent_state_in_tree(state)) {
906 while ((state = next_state(state)) != NULL) {
907 if (state->state & bits)
908 break;
909 }
910 /*
911 * If we found the next extent state, clear cached_state
912 * so that we can cache the next extent state below and
913 * avoid future calls going over the same extent state
914 * again. If we haven't found any, clear as well since
915 * it's now useless.
916 */
917 free_extent_state(*cached_state);
918 *cached_state = NULL;
919 if (state)
920 goto got_it;
921 goto out;
922 }
923 free_extent_state(*cached_state);
924 *cached_state = NULL;
925 }
926
927 state = find_first_extent_bit_state(tree, start, bits);
928got_it:
929 if (state) {
930 cache_state_if_flags(state, cached_state, 0);
931 *start_ret = state->start;
932 *end_ret = state->end;
933 ret = true;
934 }
935out:
936 spin_unlock(&tree->lock);
937 return ret;
938}
939
940/*
941 * Find a contiguous area of bits
942 *
943 * @tree: io tree to check
944 * @start: offset to start the search from
945 * @start_ret: the first offset we found with the bits set
946 * @end_ret: the final contiguous range of the bits that were set
947 * @bits: bits to look for
948 *
949 * set_extent_bit and clear_extent_bit can temporarily split contiguous ranges
950 * to set bits appropriately, and then merge them again. During this time it
951 * will drop the tree->lock, so use this helper if you want to find the actual
952 * contiguous area for given bits. We will search to the first bit we find, and
953 * then walk down the tree until we find a non-contiguous area. The area
954 * returned will be the full contiguous area with the bits set.
955 */
956int find_contiguous_extent_bit(struct extent_io_tree *tree, u64 start,
957 u64 *start_ret, u64 *end_ret, u32 bits)
958{
959 struct extent_state *state;
960 int ret = 1;
961
962 ASSERT(!btrfs_fs_incompat(extent_io_tree_to_fs_info(tree), NO_HOLES));
963
964 spin_lock(&tree->lock);
965 state = find_first_extent_bit_state(tree, start, bits);
966 if (state) {
967 *start_ret = state->start;
968 *end_ret = state->end;
969 while ((state = next_state(state)) != NULL) {
970 if (state->start > (*end_ret + 1))
971 break;
972 *end_ret = state->end;
973 }
974 ret = 0;
975 }
976 spin_unlock(&tree->lock);
977 return ret;
978}
979
980/*
981 * Find a contiguous range of bytes in the file marked as delalloc, not more
982 * than 'max_bytes'. start and end are used to return the range,
983 *
984 * True is returned if we find something, false if nothing was in the tree.
985 */
986bool btrfs_find_delalloc_range(struct extent_io_tree *tree, u64 *start,
987 u64 *end, u64 max_bytes,
988 struct extent_state **cached_state)
989{
990 struct extent_state *state;
991 u64 cur_start = *start;
992 bool found = false;
993 u64 total_bytes = 0;
994
995 spin_lock(&tree->lock);
996
997 /*
998 * This search will find all the extents that end after our range
999 * starts.
1000 */
1001 state = tree_search(tree, cur_start);
1002 if (!state) {
1003 *end = (u64)-1;
1004 goto out;
1005 }
1006
1007 while (state) {
1008 if (found && (state->start != cur_start ||
1009 (state->state & EXTENT_BOUNDARY))) {
1010 goto out;
1011 }
1012 if (!(state->state & EXTENT_DELALLOC)) {
1013 if (!found)
1014 *end = state->end;
1015 goto out;
1016 }
1017 if (!found) {
1018 *start = state->start;
1019 *cached_state = state;
1020 refcount_inc(&state->refs);
1021 }
1022 found = true;
1023 *end = state->end;
1024 cur_start = state->end + 1;
1025 total_bytes += state->end - state->start + 1;
1026 if (total_bytes >= max_bytes)
1027 break;
1028 state = next_state(state);
1029 }
1030out:
1031 spin_unlock(&tree->lock);
1032 return found;
1033}
1034
1035/*
1036 * Set some bits on a range in the tree. This may require allocations or
1037 * sleeping. By default all allocations use GFP_NOFS, use EXTENT_NOWAIT for
1038 * GFP_NOWAIT.
1039 *
1040 * If any of the exclusive bits are set, this will fail with -EEXIST if some
1041 * part of the range already has the desired bits set. The extent_state of the
1042 * existing range is returned in failed_state in this case, and the start of the
1043 * existing range is returned in failed_start. failed_state is used as an
1044 * optimization for wait_extent_bit, failed_start must be used as the source of
1045 * truth as failed_state may have changed since we returned.
1046 *
1047 * [start, end] is inclusive This takes the tree lock.
1048 */
1049static int __set_extent_bit(struct extent_io_tree *tree, u64 start, u64 end,
1050 u32 bits, u64 *failed_start,
1051 struct extent_state **failed_state,
1052 struct extent_state **cached_state,
1053 struct extent_changeset *changeset)
1054{
1055 struct extent_state *state;
1056 struct extent_state *prealloc = NULL;
1057 struct rb_node **p = NULL;
1058 struct rb_node *parent = NULL;
1059 int ret = 0;
1060 u64 last_start;
1061 u64 last_end;
1062 u32 exclusive_bits = (bits & EXTENT_LOCK_BITS);
1063 gfp_t mask;
1064
1065 set_gfp_mask_from_bits(&bits, &mask);
1066 btrfs_debug_check_extent_io_range(tree, start, end);
1067 trace_btrfs_set_extent_bit(tree, start, end - start + 1, bits);
1068
1069 if (exclusive_bits)
1070 ASSERT(failed_start);
1071 else
1072 ASSERT(failed_start == NULL && failed_state == NULL);
1073again:
1074 if (!prealloc) {
1075 /*
1076 * Don't care for allocation failure here because we might end
1077 * up not needing the pre-allocated extent state at all, which
1078 * is the case if we only have in the tree extent states that
1079 * cover our input range and don't cover too any other range.
1080 * If we end up needing a new extent state we allocate it later.
1081 */
1082 prealloc = alloc_extent_state(mask);
1083 }
1084 /* Optimistically preallocate the extent changeset ulist node. */
1085 if (changeset)
1086 extent_changeset_prealloc(changeset, mask);
1087
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))
1093 goto hit_next;
1094 }
1095 /*
1096 * This search will find all the extents that end after our range
1097 * starts.
1098 */
1099 state = tree_search_for_insert(tree, start, &p, &parent);
1100 if (!state) {
1101 prealloc = alloc_extent_state_atomic(prealloc);
1102 if (!prealloc)
1103 goto search_again;
1104 prealloc->start = start;
1105 prealloc->end = end;
1106 insert_state_fast(tree, prealloc, p, parent, bits, changeset);
1107 cache_state(prealloc, cached_state);
1108 prealloc = NULL;
1109 goto out;
1110 }
1111hit_next:
1112 last_start = state->start;
1113 last_end = state->end;
1114
1115 /*
1116 * | ---- desired range ---- |
1117 * | state |
1118 *
1119 * Just lock what we found and keep going
1120 */
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);
1125 ret = -EEXIST;
1126 goto out;
1127 }
1128
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)
1133 goto out;
1134 start = last_end + 1;
1135 state = next_state(state);
1136 if (start < end && state && state->start == start &&
1137 !need_resched())
1138 goto hit_next;
1139 goto search_again;
1140 }
1141
1142 /*
1143 * | ---- desired range ---- |
1144 * | state |
1145 * or
1146 * | ------------- state -------------- |
1147 *
1148 * We need to split the extent we found, and may flip bits on second
1149 * half.
1150 *
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.
1153 *
1154 * If the extent we found is inside our range, we set the desired bit
1155 * on it.
1156 */
1157 if (state->start < start) {
1158 if (state->state & exclusive_bits) {
1159 *failed_start = start;
1160 cache_state(state, failed_state);
1161 ret = -EEXIST;
1162 goto out;
1163 }
1164
1165 /*
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.
1168 */
1169 if ((state->state & bits) == bits) {
1170 start = state->end + 1;
1171 cache_state(state, cached_state);
1172 goto search_again;
1173 }
1174
1175 prealloc = alloc_extent_state_atomic(prealloc);
1176 if (!prealloc)
1177 goto search_again;
1178 ret = split_state(tree, state, prealloc, start);
1179 if (ret)
1180 extent_io_tree_panic(tree, state, "split", ret);
1181
1182 prealloc = NULL;
1183 if (ret)
1184 goto out;
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)
1190 goto out;
1191 start = last_end + 1;
1192 state = next_state(state);
1193 if (start < end && state && state->start == start &&
1194 !need_resched())
1195 goto hit_next;
1196 }
1197 goto search_again;
1198 }
1199 /*
1200 * | ---- desired range ---- |
1201 * | state | or | state |
1202 *
1203 * There's a hole, we need to insert something in it and ignore the
1204 * extent we found.
1205 */
1206 if (state->start > start) {
1207 u64 this_end;
1208 struct extent_state *inserted_state;
1209
1210 if (end < last_start)
1211 this_end = end;
1212 else
1213 this_end = last_start - 1;
1214
1215 prealloc = alloc_extent_state_atomic(prealloc);
1216 if (!prealloc)
1217 goto search_again;
1218
1219 /*
1220 * Avoid to free 'prealloc' if it can be merged with the later
1221 * extent.
1222 */
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 ret = PTR_ERR(inserted_state);
1228 extent_io_tree_panic(tree, prealloc, "insert", ret);
1229 }
1230
1231 cache_state(inserted_state, cached_state);
1232 if (inserted_state == prealloc)
1233 prealloc = NULL;
1234 start = this_end + 1;
1235 goto search_again;
1236 }
1237 /*
1238 * | ---- desired range ---- |
1239 * | state |
1240 *
1241 * We need to split the extent, and set the bit on the first half
1242 */
1243 if (state->start <= end && state->end > end) {
1244 if (state->state & exclusive_bits) {
1245 *failed_start = start;
1246 cache_state(state, failed_state);
1247 ret = -EEXIST;
1248 goto out;
1249 }
1250
1251 prealloc = alloc_extent_state_atomic(prealloc);
1252 if (!prealloc)
1253 goto search_again;
1254 ret = split_state(tree, state, prealloc, end + 1);
1255 if (ret)
1256 extent_io_tree_panic(tree, state, "split", ret);
1257
1258 set_state_bits(tree, prealloc, bits, changeset);
1259 cache_state(prealloc, cached_state);
1260 merge_state(tree, prealloc);
1261 prealloc = NULL;
1262 goto out;
1263 }
1264
1265search_again:
1266 if (start > end)
1267 goto out;
1268 spin_unlock(&tree->lock);
1269 if (gfpflags_allow_blocking(mask))
1270 cond_resched();
1271 goto again;
1272
1273out:
1274 spin_unlock(&tree->lock);
1275 if (prealloc)
1276 free_extent_state(prealloc);
1277
1278 return ret;
1279
1280}
1281
1282int set_extent_bit(struct extent_io_tree *tree, u64 start, u64 end,
1283 u32 bits, struct extent_state **cached_state)
1284{
1285 return __set_extent_bit(tree, start, end, bits, NULL, NULL,
1286 cached_state, NULL);
1287}
1288
1289/*
1290 * Convert all bits in a given range from one bit to another
1291 *
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
1298 *
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.
1304 *
1305 * All allocations are done with GFP_NOFS.
1306 */
1307int convert_extent_bit(struct extent_io_tree *tree, u64 start, u64 end,
1308 u32 bits, u32 clear_bits,
1309 struct extent_state **cached_state)
1310{
1311 struct extent_state *state;
1312 struct extent_state *prealloc = NULL;
1313 struct rb_node **p = NULL;
1314 struct rb_node *parent = NULL;
1315 int ret = 0;
1316 u64 last_start;
1317 u64 last_end;
1318 bool first_iteration = true;
1319
1320 btrfs_debug_check_extent_io_range(tree, start, end);
1321 trace_btrfs_convert_extent_bit(tree, start, end - start + 1, bits,
1322 clear_bits);
1323
1324again:
1325 if (!prealloc) {
1326 /*
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.
1332 */
1333 prealloc = alloc_extent_state(GFP_NOFS);
1334 if (!prealloc && !first_iteration)
1335 return -ENOMEM;
1336 }
1337
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))
1343 goto hit_next;
1344 }
1345
1346 /*
1347 * This search will find all the extents that end after our range
1348 * starts.
1349 */
1350 state = tree_search_for_insert(tree, start, &p, &parent);
1351 if (!state) {
1352 prealloc = alloc_extent_state_atomic(prealloc);
1353 if (!prealloc) {
1354 ret = -ENOMEM;
1355 goto out;
1356 }
1357 prealloc->start = start;
1358 prealloc->end = end;
1359 insert_state_fast(tree, prealloc, p, parent, bits, NULL);
1360 cache_state(prealloc, cached_state);
1361 prealloc = NULL;
1362 goto out;
1363 }
1364hit_next:
1365 last_start = state->start;
1366 last_end = state->end;
1367
1368 /*
1369 * | ---- desired range ---- |
1370 * | state |
1371 *
1372 * Just lock what we found and keep going.
1373 */
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)
1379 goto out;
1380 start = last_end + 1;
1381 if (start < end && state && state->start == start &&
1382 !need_resched())
1383 goto hit_next;
1384 goto search_again;
1385 }
1386
1387 /*
1388 * | ---- desired range ---- |
1389 * | state |
1390 * or
1391 * | ------------- state -------------- |
1392 *
1393 * We need to split the extent we found, and may flip bits on second
1394 * half.
1395 *
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.
1398 *
1399 * If the extent we found is inside our range, we set the desired bit
1400 * on it.
1401 */
1402 if (state->start < start) {
1403 prealloc = alloc_extent_state_atomic(prealloc);
1404 if (!prealloc) {
1405 ret = -ENOMEM;
1406 goto out;
1407 }
1408 ret = split_state(tree, state, prealloc, start);
1409 if (ret)
1410 extent_io_tree_panic(tree, state, "split", ret);
1411 prealloc = NULL;
1412 if (ret)
1413 goto out;
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)
1419 goto out;
1420 start = last_end + 1;
1421 if (start < end && state && state->start == start &&
1422 !need_resched())
1423 goto hit_next;
1424 }
1425 goto search_again;
1426 }
1427 /*
1428 * | ---- desired range ---- |
1429 * | state | or | state |
1430 *
1431 * There's a hole, we need to insert something in it and ignore the
1432 * extent we found.
1433 */
1434 if (state->start > start) {
1435 u64 this_end;
1436 struct extent_state *inserted_state;
1437
1438 if (end < last_start)
1439 this_end = end;
1440 else
1441 this_end = last_start - 1;
1442
1443 prealloc = alloc_extent_state_atomic(prealloc);
1444 if (!prealloc) {
1445 ret = -ENOMEM;
1446 goto out;
1447 }
1448
1449 /*
1450 * Avoid to free 'prealloc' if it can be merged with the later
1451 * extent.
1452 */
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 ret = PTR_ERR(inserted_state);
1458 extent_io_tree_panic(tree, prealloc, "insert", ret);
1459 }
1460 cache_state(inserted_state, cached_state);
1461 if (inserted_state == prealloc)
1462 prealloc = NULL;
1463 start = this_end + 1;
1464 goto search_again;
1465 }
1466 /*
1467 * | ---- desired range ---- |
1468 * | state |
1469 *
1470 * We need to split the extent, and set the bit on the first half.
1471 */
1472 if (state->start <= end && state->end > end) {
1473 prealloc = alloc_extent_state_atomic(prealloc);
1474 if (!prealloc) {
1475 ret = -ENOMEM;
1476 goto out;
1477 }
1478
1479 ret = split_state(tree, state, prealloc, end + 1);
1480 if (ret)
1481 extent_io_tree_panic(tree, state, "split", ret);
1482
1483 set_state_bits(tree, prealloc, bits, NULL);
1484 cache_state(prealloc, cached_state);
1485 clear_state_bit(tree, prealloc, clear_bits, 0, NULL);
1486 prealloc = NULL;
1487 goto out;
1488 }
1489
1490search_again:
1491 if (start > end)
1492 goto out;
1493 spin_unlock(&tree->lock);
1494 cond_resched();
1495 first_iteration = false;
1496 goto again;
1497
1498out:
1499 spin_unlock(&tree->lock);
1500 if (prealloc)
1501 free_extent_state(prealloc);
1502
1503 return ret;
1504}
1505
1506/*
1507 * Find the first range that has @bits not set. This range could start before
1508 * @start.
1509 *
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
1515 *
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.
1520 */
1521void find_first_clear_extent_bit(struct extent_io_tree *tree, u64 start,
1522 u64 *start_ret, u64 *end_ret, u32 bits)
1523{
1524 struct extent_state *state;
1525 struct extent_state *prev = NULL, *next = NULL;
1526
1527 spin_lock(&tree->lock);
1528
1529 /* Find first extent with bits cleared */
1530 while (1) {
1531 state = tree_search_prev_next(tree, start, &prev, &next);
1532 if (!state && !next && !prev) {
1533 /*
1534 * Tree is completely empty, send full range and let
1535 * caller deal with it
1536 */
1537 *start_ret = 0;
1538 *end_ret = -1;
1539 goto out;
1540 } else if (!state && !next) {
1541 /*
1542 * We are past the last allocated chunk, set start at
1543 * the end of the last extent.
1544 */
1545 *start_ret = prev->end + 1;
1546 *end_ret = -1;
1547 goto out;
1548 } else if (!state) {
1549 state = next;
1550 }
1551
1552 /*
1553 * At this point 'state' either contains 'start' or start is
1554 * before 'state'
1555 */
1556 if (in_range(start, state->start, state->end - state->start + 1)) {
1557 if (state->state & bits) {
1558 /*
1559 * |--range with bits sets--|
1560 * |
1561 * start
1562 */
1563 start = state->end + 1;
1564 } else {
1565 /*
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
1569 *
1570 * |--range with bits cleared----|
1571 * |
1572 * start
1573 */
1574 *start_ret = state->start;
1575 break;
1576 }
1577 } else {
1578 /*
1579 * |---prev range---|---hole/unset---|---node range---|
1580 * |
1581 * start
1582 *
1583 * or
1584 *
1585 * |---hole/unset--||--first node--|
1586 * 0 |
1587 * start
1588 */
1589 if (prev)
1590 *start_ret = prev->end + 1;
1591 else
1592 *start_ret = 0;
1593 break;
1594 }
1595 }
1596
1597 /*
1598 * Find the longest stretch from start until an entry which has the
1599 * bits set
1600 */
1601 while (state) {
1602 if (state->end >= start && !(state->state & bits)) {
1603 *end_ret = state->end;
1604 } else {
1605 *end_ret = state->start - 1;
1606 break;
1607 }
1608 state = next_state(state);
1609 }
1610out:
1611 spin_unlock(&tree->lock);
1612}
1613
1614/*
1615 * Count the number of bytes in the tree that have a given bit(s) set for a
1616 * given range.
1617 *
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.
1634 *
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.
1638 */
1639u64 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)
1643{
1644 struct extent_state *state = NULL;
1645 struct extent_state *cached;
1646 u64 cur_start = *start;
1647 u64 total_bytes = 0;
1648 u64 last = 0;
1649 int found = 0;
1650
1651 if (WARN_ON(search_end < cur_start))
1652 return 0;
1653
1654 spin_lock(&tree->lock);
1655
1656 if (!cached_state || !*cached_state)
1657 goto search;
1658
1659 cached = *cached_state;
1660
1661 if (!extent_state_in_tree(cached))
1662 goto search;
1663
1664 if (cached->start <= cur_start && cur_start <= cached->end) {
1665 state = cached;
1666 } else if (cached->start > cur_start) {
1667 struct extent_state *prev;
1668
1669 /*
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.
1675 */
1676 prev = prev_state(cached);
1677 if (!prev)
1678 state = cached;
1679 else if (prev->start <= cur_start && cur_start <= prev->end)
1680 state = prev;
1681 }
1682
1683 /*
1684 * This search will find all the extents that end after our range
1685 * starts.
1686 */
1687search:
1688 if (!state)
1689 state = tree_search(tree, cur_start);
1690
1691 while (state) {
1692 if (state->start > search_end)
1693 break;
1694 if (contig && found && state->start > last + 1)
1695 break;
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)
1700 break;
1701 if (!found) {
1702 *start = max(cur_start, state->start);
1703 found = 1;
1704 }
1705 last = state->end;
1706 } else if (contig && found) {
1707 break;
1708 }
1709 state = next_state(state);
1710 }
1711
1712 if (cached_state) {
1713 free_extent_state(*cached_state);
1714 *cached_state = state;
1715 if (state)
1716 refcount_inc(&state->refs);
1717 }
1718
1719 spin_unlock(&tree->lock);
1720
1721 return total_bytes;
1722}
1723
1724/*
1725 * Check if the single @bit exists in the given range.
1726 */
1727bool test_range_bit_exists(struct extent_io_tree *tree, u64 start, u64 end, u32 bit)
1728{
1729 struct extent_state *state = NULL;
1730 bool bitset = false;
1731
1732 ASSERT(is_power_of_2(bit));
1733
1734 spin_lock(&tree->lock);
1735 state = tree_search(tree, start);
1736 while (state && start <= end) {
1737 if (state->start > end)
1738 break;
1739
1740 if (state->state & bit) {
1741 bitset = true;
1742 break;
1743 }
1744
1745 /* If state->end is (u64)-1, start will overflow to 0 */
1746 start = state->end + 1;
1747 if (start > end || start == 0)
1748 break;
1749 state = next_state(state);
1750 }
1751 spin_unlock(&tree->lock);
1752 return bitset;
1753}
1754
1755/*
1756 * Check if the whole range [@start,@end) contains the single @bit set.
1757 */
1758bool test_range_bit(struct extent_io_tree *tree, u64 start, u64 end, u32 bit,
1759 struct extent_state *cached)
1760{
1761 struct extent_state *state = NULL;
1762 bool bitset = true;
1763
1764 ASSERT(is_power_of_2(bit));
1765
1766 spin_lock(&tree->lock);
1767 if (cached && extent_state_in_tree(cached) && cached->start <= start &&
1768 cached->end > start)
1769 state = cached;
1770 else
1771 state = tree_search(tree, start);
1772 while (state && start <= end) {
1773 if (state->start > start) {
1774 bitset = false;
1775 break;
1776 }
1777
1778 if (state->start > end)
1779 break;
1780
1781 if ((state->state & bit) == 0) {
1782 bitset = false;
1783 break;
1784 }
1785
1786 if (state->end == (u64)-1)
1787 break;
1788
1789 /*
1790 * Last entry (if state->end is (u64)-1 and overflow happens),
1791 * or next entry starts after the range.
1792 */
1793 start = state->end + 1;
1794 if (start > end || start == 0)
1795 break;
1796 state = next_state(state);
1797 }
1798
1799 /* We ran out of states and were still inside of our range. */
1800 if (!state)
1801 bitset = false;
1802 spin_unlock(&tree->lock);
1803 return bitset;
1804}
1805
1806/* Wrappers around set/clear extent bit */
1807int set_record_extent_bits(struct extent_io_tree *tree, u64 start, u64 end,
1808 u32 bits, struct extent_changeset *changeset)
1809{
1810 /*
1811 * We don't support EXTENT_LOCK_BITS yet, as current changeset will
1812 * record any bits changed, so for EXTENT_LOCK_BITS case, it will either
1813 * fail with -EEXIST or changeset will record the whole range.
1814 */
1815 ASSERT(!(bits & EXTENT_LOCK_BITS));
1816
1817 return __set_extent_bit(tree, start, end, bits, NULL, NULL, NULL, changeset);
1818}
1819
1820int clear_record_extent_bits(struct extent_io_tree *tree, u64 start, u64 end,
1821 u32 bits, struct extent_changeset *changeset)
1822{
1823 /*
1824 * Don't support EXTENT_LOCK_BITS case, same reason as
1825 * set_record_extent_bits().
1826 */
1827 ASSERT(!(bits & EXTENT_LOCK_BITS));
1828
1829 return __clear_extent_bit(tree, start, end, bits, NULL, changeset);
1830}
1831
1832bool __try_lock_extent(struct extent_io_tree *tree, u64 start, u64 end, u32 bits,
1833 struct extent_state **cached)
1834{
1835 int err;
1836 u64 failed_start;
1837
1838 err = __set_extent_bit(tree, start, end, bits, &failed_start,
1839 NULL, cached, NULL);
1840 if (err == -EEXIST) {
1841 if (failed_start > start)
1842 clear_extent_bit(tree, start, failed_start - 1, bits, cached);
1843 return 0;
1844 }
1845 return 1;
1846}
1847
1848/*
1849 * Either insert or lock state struct between start and end use mask to tell
1850 * us if waiting is desired.
1851 */
1852int __lock_extent(struct extent_io_tree *tree, u64 start, u64 end, u32 bits,
1853 struct extent_state **cached_state)
1854{
1855 struct extent_state *failed_state = NULL;
1856 int err;
1857 u64 failed_start;
1858
1859 err = __set_extent_bit(tree, start, end, bits, &failed_start,
1860 &failed_state, cached_state, NULL);
1861 while (err == -EEXIST) {
1862 if (failed_start != start)
1863 clear_extent_bit(tree, start, failed_start - 1,
1864 bits, cached_state);
1865
1866 wait_extent_bit(tree, failed_start, end, bits, &failed_state);
1867 err = __set_extent_bit(tree, start, end, bits,
1868 &failed_start, &failed_state,
1869 cached_state, NULL);
1870 }
1871 return err;
1872}
1873
1874void __cold extent_state_free_cachep(void)
1875{
1876 btrfs_extent_state_leak_debug_check();
1877 kmem_cache_destroy(extent_state_cache);
1878}
1879
1880int __init extent_state_init_cachep(void)
1881{
1882 extent_state_cache = kmem_cache_create("btrfs_extent_state",
1883 sizeof(struct extent_state), 0, 0,
1884 NULL);
1885 if (!extent_state_cache)
1886 return -ENOMEM;
1887
1888 return 0;
1889}