1890 lines · c
1// SPDX-License-Identifier: GPL-2.02 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_DEBUG19static 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#else77#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#endif82 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 the127 * tree. This should be called once we are sure no other task can access the128 * tree anymore, so no tree updates happen after we empty the tree and there129 * aren't any waiters on any extent state record (EXTENT_LOCK_BITS are never130 * 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 tree147 * lock and we only change the waitqueue while holding that lock148 * (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 should156 * 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 bits169 */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 else228 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 else238 return NULL;239}240 241/*242 * Search @tree for an entry that contains @offset. Such entry would have243 * entry->start <= offset && entry->end >= offset.244 *245 * @tree: the tree to search246 * @offset: offset that should fall within an entry in @tree247 * @node_ret: pointer where new node should be anchored (used when inserting an248 * entry in the tree)249 * @parent_ret: points to entry which would have been the parent of the entry,250 * containing @offset251 *252 * Return a pointer to the entry that contains @offset byte address and don't change253 * @node_ret and @parent_ret.254 *255 * If no such entry exists, return pointer to entry that ends before @offset256 * 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 else277 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 search296 * @offset: offset that should fall within an entry in @tree297 * @next_ret: pointer to the first entry whose range ends after @offset298 * @prev_ret: pointer to the first entry whose range begins before @offset299 *300 * Return a pointer to the entry that contains @offset byte address. If no301 * 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 else325 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 found343 */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. Any393 * extents with matching state are merged together into a single extent in the394 * tree. Extents with EXTENT_IO in their state field are not merged because395 * the end_io handlers need to be able to do operations on them without396 * 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 the426 * struct before it is inserted.427 *428 * Returns a pointer to the struct extent_state record containing the range429 * requested for insertion, which may be the same as the given struct or it430 * may be an existing record in the tree that was expanded to accommodate the431 * requested range. In case of an extent_state different from the one that was432 * 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 and437 * 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 preallocated512 * struct 'prealloc' as the newly created second half. 'split' indicates an513 * offset inside 'orig' where it should be split.514 *515 * Before calling,516 * the tree has 'orig' at [orig->start, orig->end]. After calling, there517 * 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 held522 * 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 will565 * optionally wake up anyone waiting on this state (wake == 1).566 *567 * If no bits are set on the state struct after clearing things, the568 * struct is freed and removed from the tree569 */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 or616 * inserting elements in the tree, so the gfp mask is used to indicate which617 * 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 end654 * up not needing the pre-allocated extent state at all, which655 * is the case if we only have in the tree extent states that656 * 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 | or701 * | ------------- state -------------- |702 *703 * We need to split the extent we found, and may flip bits on second704 * half.705 *706 * If the extent we found extends past our range, we just split and707 * 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 bit710 * 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 function781 */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 there793 * 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 our804 * 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 after867 * '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 range876 * 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_state912 * so that we can cache the next extent state below and913 * avoid future calls going over the same extent state914 * again. If we haven't found any, clear as well since915 * 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 bits942 *943 * @tree: io tree to check944 * @start: offset to start the search from945 * @start_ret: the first offset we found with the bits set946 * @end_ret: the final contiguous range of the bits that were set947 * @bits: bits to look for948 *949 * set_extent_bit and clear_extent_bit can temporarily split contiguous ranges950 * to set bits appropriately, and then merge them again. During this time it951 * will drop the tree->lock, so use this helper if you want to find the actual952 * contiguous area for given bits. We will search to the first bit we find, and953 * then walk down the tree until we find a non-contiguous area. The area954 * 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 more982 * 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 range999 * 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 or1037 * sleeping. By default all allocations use GFP_NOFS, use EXTENT_NOWAIT for1038 * GFP_NOWAIT.1039 *1040 * If any of the exclusive bits are set, this will fail with -EEXIST if some1041 * part of the range already has the desired bits set. The extent_state of the1042 * existing range is returned in failed_state in this case, and the start of the1043 * existing range is returned in failed_start. failed_state is used as an1044 * optimization for wait_extent_bit, failed_start must be used as the source of1045 * 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 else1072 ASSERT(failed_start == NULL && failed_state == NULL);1073again:1074 if (!prealloc) {1075 /*1076 * Don't care for allocation failure here because we might end1077 * up not needing the pre-allocated extent state at all, which1078 * is the case if we only have in the tree extent states that1079 * 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 range1097 * 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 going1120 */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 * or1146 * | ------------- state -------------- |1147 *1148 * We need to split the extent we found, and may flip bits on second1149 * half.1150 *1151 * If the extent we found extends past our range, we just split and1152 * 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 bit1155 * 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, then1167 * 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 the1204 * 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 else1213 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 later1221 * 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 half1242 */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 another1291 *1292 * @tree: the io tree to search1293 * @start: the start offset in bytes1294 * @end: the end offset in bytes (inclusive)1295 * @bits: the bits to set in this range1296 * @clear_bits: the bits to clear in this range1297 * @cached_state: state that we're going to cache1298 *1299 * This will go through and set bits for the given range. If any states exist1300 * already in this range they are set with the given bit and cleared of the1301 * 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 with1303 * 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 fails1328 * here for the first iteration. We might have a cached state1329 * that matches exactly the target range, in which case no1330 * extent state allocations are needed. We'll only know this1331 * 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 range1348 * 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 * or1391 * | ------------- state -------------- |1392 *1393 * We need to split the extent we found, and may flip bits on second1394 * half.1395 *1396 * If the extent we found extends past our range, we just split and1397 * 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 bit1400 * 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 the1432 * 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 else1441 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 later1451 * 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 before1508 * @start.1509 *1510 * @tree: the tree to search1511 * @start: offset at/after which the found extent should start1512 * @start_ret: records the beginning of the range1513 * @end_ret: records the end of the range (inclusive)1514 * @bits: the set of bits which must be unset1515 *1516 * Since unallocated range is also considered one which doesn't have the bits1517 * set it's possible that @end_ret contains -1, this happens in case the range1518 * spans (last_range_end, end of device]. In this case it's up to the caller to1519 * 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 let1535 * caller deal with it1536 */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 at1543 * 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 is1554 * 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 * start1562 */1563 start = state->end + 1;1564 } else {1565 /*1566 * 'start' falls within a range that doesn't1567 * have the bits set, so take its start as the1568 * beginning of the desired range1569 *1570 * |--range with bits cleared----|1571 * |1572 * start1573 */1574 *start_ret = state->start;1575 break;1576 }1577 } else {1578 /*1579 * |---prev range---|---hole/unset---|---node range---|1580 * |1581 * start1582 *1583 * or1584 *1585 * |---hole/unset--||--first node--|1586 * 0 |1587 * start1588 */1589 if (prev)1590 *start_ret = prev->end + 1;1591 else1592 *start_ret = 0;1593 break;1594 }1595 }1596 1597 /*1598 * Find the longest stretch from start until an entry which has the1599 * bits set1600 */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 a1616 * given range.1617 *1618 * @tree: The io tree to search.1619 * @start: The start offset of the range. This value is updated to the1620 * offset of the first byte found with the given bit(s), so it1621 * 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 stops1624 * 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 all1627 * the bits set are accounted for.1628 * @contig: Indicate if we should ignore holes in the range or not. If1629 * this is true, then stop once we find a hole.1630 * @cached_state: A cached state to be used across multiple calls to this1631 * function in order to speedup searches. Use NULL if this is1632 * called only once or if each call does not start where the1633 * previous one ended.1634 *1635 * Returns the total number of bytes found within the given range that have1636 * all given bits set. If the returned number of bytes is greater than zero1637 * 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. Check1671 * if the previous state record starts at or before the range we1672 * are looking for, and if so, use it - this is a common case1673 * when there are holes between records in the tree. If there is1674 * 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 range1685 * 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 else1771 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 will1812 * record any bits changed, so for EXTENT_LOCK_BITS case, it will either1813 * 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 as1825 * 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 tell1850 * 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}1890