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-tree.h"
   8#include "btrfs_inode.h"
   9#include "misc.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		kmem_cache_free(extent_state_cache, state);
  52	}
  53}
  54
  55#define btrfs_debug_check_extent_io_range(tree, start, end)		\
  56	__btrfs_debug_check_extent_io_range(__func__, (tree), (start), (end))
  57static inline void __btrfs_debug_check_extent_io_range(const char *caller,
  58						       struct extent_io_tree *tree,
  59						       u64 start, u64 end)
  60{
  61	const struct btrfs_inode *inode;
  62	u64 isize;
  63
  64	if (tree->owner != IO_TREE_INODE_IO)
  65		return;
  66
  67	inode = extent_io_tree_to_inode_const(tree);
  68	isize = i_size_read(&inode->vfs_inode);
  69	if (end >= PAGE_SIZE && (end % 2) == 0 && end != isize - 1) {
  70		btrfs_debug_rl(inode->root->fs_info,
  71		    "%s: ino %llu isize %llu odd range [%llu,%llu]",
  72			caller, btrfs_ino(inode), isize, start, end);
  73	}
  74}
  75#else
  76#define btrfs_leak_debug_add_state(state)		do {} while (0)
  77#define btrfs_leak_debug_del_state(state)		do {} while (0)
  78#define btrfs_extent_state_leak_debug_check()		do {} while (0)
  79#define btrfs_debug_check_extent_io_range(c, s, e)	do {} while (0)
  80#endif
  81
  82
  83/*
  84 * The only tree allowed to set the inode is IO_TREE_INODE_IO.
  85 */
  86static bool is_inode_io_tree(const struct extent_io_tree *tree)
  87{
  88	return tree->owner == IO_TREE_INODE_IO;
  89}
  90
  91/* Return the inode if it's valid for the given tree, otherwise NULL. */
  92struct btrfs_inode *extent_io_tree_to_inode(struct extent_io_tree *tree)
  93{
  94	if (tree->owner == IO_TREE_INODE_IO)
  95		return tree->inode;
  96	return NULL;
  97}
  98
  99/* Read-only access to the inode. */
 100const struct btrfs_inode *extent_io_tree_to_inode_const(const struct extent_io_tree *tree)
 101{
 102	if (tree->owner == IO_TREE_INODE_IO)
 103		return tree->inode;
 104	return NULL;
 105}
 106
 107/* For read-only access to fs_info. */
 108const struct btrfs_fs_info *extent_io_tree_to_fs_info(const struct extent_io_tree *tree)
 109{
 110	if (tree->owner == IO_TREE_INODE_IO)
 111		return tree->inode->root->fs_info;
 112	return tree->fs_info;
 113}
 114
 115void extent_io_tree_init(struct btrfs_fs_info *fs_info,
 116			 struct extent_io_tree *tree, unsigned int owner)
 117{
 
 118	tree->state = RB_ROOT;
 119	spin_lock_init(&tree->lock);
 120	tree->fs_info = fs_info;
 121	tree->owner = owner;
 
 
 122}
 123
 124/*
 125 * Empty an io tree, removing and freeing every extent state record from the
 126 * tree. This should be called once we are sure no other task can access the
 127 * tree anymore, so no tree updates happen after we empty the tree and there
 128 * aren't any waiters on any extent state record (EXTENT_LOCKED bit is never
 129 * set on any extent state when calling this function).
 130 */
 131void extent_io_tree_release(struct extent_io_tree *tree)
 132{
 133	struct rb_root root;
 134	struct extent_state *state;
 135	struct extent_state *tmp;
 136
 137	spin_lock(&tree->lock);
 138	root = tree->state;
 139	tree->state = RB_ROOT;
 140	rbtree_postorder_for_each_entry_safe(state, tmp, &root, rb_node) {
 141		/* Clear node to keep free_extent_state() happy. */
 
 
 
 
 
 
 
 
 
 142		RB_CLEAR_NODE(&state->rb_node);
 143		ASSERT(!(state->state & EXTENT_LOCKED));
 144		/*
 145		 * No need for a memory barrier here, as we are holding the tree
 146		 * lock and we only change the waitqueue while holding that lock
 147		 * (see wait_extent_bit()).
 148		 */
 149		ASSERT(!waitqueue_active(&state->wq));
 150		free_extent_state(state);
 
 151		cond_resched_lock(&tree->lock);
 152	}
 153	/*
 154	 * Should still be empty even after a reschedule, no other task should
 155	 * be accessing the tree anymore.
 156	 */
 157	ASSERT(RB_EMPTY_ROOT(&tree->state));
 158	spin_unlock(&tree->lock);
 159}
 160
 161static struct extent_state *alloc_extent_state(gfp_t mask)
 162{
 163	struct extent_state *state;
 164
 165	/*
 166	 * The given mask might be not appropriate for the slab allocator,
 167	 * drop the unsupported bits
 168	 */
 169	mask &= ~(__GFP_DMA32|__GFP_HIGHMEM);
 170	state = kmem_cache_alloc(extent_state_cache, mask);
 171	if (!state)
 172		return state;
 173	state->state = 0;
 174	RB_CLEAR_NODE(&state->rb_node);
 175	btrfs_leak_debug_add_state(state);
 176	refcount_set(&state->refs, 1);
 177	init_waitqueue_head(&state->wq);
 178	trace_alloc_extent_state(state, mask, _RET_IP_);
 179	return state;
 180}
 181
 182static struct extent_state *alloc_extent_state_atomic(struct extent_state *prealloc)
 183{
 184	if (!prealloc)
 185		prealloc = alloc_extent_state(GFP_ATOMIC);
 186
 187	return prealloc;
 188}
 189
 190void free_extent_state(struct extent_state *state)
 191{
 192	if (!state)
 193		return;
 194	if (refcount_dec_and_test(&state->refs)) {
 195		WARN_ON(extent_state_in_tree(state));
 196		btrfs_leak_debug_del_state(state);
 197		trace_free_extent_state(state, _RET_IP_);
 198		kmem_cache_free(extent_state_cache, state);
 199	}
 200}
 201
 202static int add_extent_changeset(struct extent_state *state, u32 bits,
 203				 struct extent_changeset *changeset,
 204				 int set)
 205{
 206	int ret;
 207
 208	if (!changeset)
 209		return 0;
 210	if (set && (state->state & bits) == bits)
 211		return 0;
 212	if (!set && (state->state & bits) == 0)
 213		return 0;
 214	changeset->bytes_changed += state->end - state->start + 1;
 215	ret = ulist_add(&changeset->range_changed, state->start, state->end,
 216			GFP_ATOMIC);
 217	return ret;
 218}
 219
 220static inline struct extent_state *next_state(struct extent_state *state)
 221{
 222	struct rb_node *next = rb_next(&state->rb_node);
 223
 224	if (next)
 225		return rb_entry(next, struct extent_state, rb_node);
 226	else
 227		return NULL;
 228}
 229
 230static inline struct extent_state *prev_state(struct extent_state *state)
 231{
 232	struct rb_node *next = rb_prev(&state->rb_node);
 233
 234	if (next)
 235		return rb_entry(next, struct extent_state, rb_node);
 236	else
 237		return NULL;
 238}
 239
 240/*
 241 * Search @tree for an entry that contains @offset. Such entry would have
 242 * entry->start <= offset && entry->end >= offset.
 243 *
 244 * @tree:       the tree to search
 245 * @offset:     offset that should fall within an entry in @tree
 246 * @node_ret:   pointer where new node should be anchored (used when inserting an
 247 *	        entry in the tree)
 248 * @parent_ret: points to entry which would have been the parent of the entry,
 249 *               containing @offset
 250 *
 251 * Return a pointer to the entry that contains @offset byte address and don't change
 252 * @node_ret and @parent_ret.
 253 *
 254 * If no such entry exists, return pointer to entry that ends before @offset
 255 * and fill parameters @node_ret and @parent_ret, ie. does not return NULL.
 256 */
 257static inline struct extent_state *tree_search_for_insert(struct extent_io_tree *tree,
 258							  u64 offset,
 259							  struct rb_node ***node_ret,
 260							  struct rb_node **parent_ret)
 261{
 262	struct rb_root *root = &tree->state;
 263	struct rb_node **node = &root->rb_node;
 264	struct rb_node *prev = NULL;
 265	struct extent_state *entry = NULL;
 266
 267	while (*node) {
 268		prev = *node;
 269		entry = rb_entry(prev, struct extent_state, rb_node);
 270
 271		if (offset < entry->start)
 272			node = &(*node)->rb_left;
 273		else if (offset > entry->end)
 274			node = &(*node)->rb_right;
 275		else
 276			return entry;
 277	}
 278
 279	if (node_ret)
 280		*node_ret = node;
 281	if (parent_ret)
 282		*parent_ret = prev;
 283
 284	/* Search neighbors until we find the first one past the end */
 285	while (entry && offset > entry->end)
 286		entry = next_state(entry);
 287
 288	return entry;
 289}
 290
 291/*
 292 * Search offset in the tree or fill neighbor rbtree node pointers.
 293 *
 294 * @tree:      the tree to search
 295 * @offset:    offset that should fall within an entry in @tree
 296 * @next_ret:  pointer to the first entry whose range ends after @offset
 297 * @prev_ret:  pointer to the first entry whose range begins before @offset
 298 *
 299 * Return a pointer to the entry that contains @offset byte address. If no
 300 * such entry exists, then return NULL and fill @prev_ret and @next_ret.
 301 * Otherwise return the found entry and other pointers are left untouched.
 302 */
 303static struct extent_state *tree_search_prev_next(struct extent_io_tree *tree,
 304						  u64 offset,
 305						  struct extent_state **prev_ret,
 306						  struct extent_state **next_ret)
 307{
 308	struct rb_root *root = &tree->state;
 309	struct rb_node **node = &root->rb_node;
 310	struct extent_state *orig_prev;
 311	struct extent_state *entry = NULL;
 312
 313	ASSERT(prev_ret);
 314	ASSERT(next_ret);
 315
 316	while (*node) {
 317		entry = rb_entry(*node, struct extent_state, rb_node);
 318
 319		if (offset < entry->start)
 320			node = &(*node)->rb_left;
 321		else if (offset > entry->end)
 322			node = &(*node)->rb_right;
 323		else
 324			return entry;
 325	}
 326
 327	orig_prev = entry;
 328	while (entry && offset > entry->end)
 329		entry = next_state(entry);
 330	*next_ret = entry;
 331	entry = orig_prev;
 332
 333	while (entry && offset < entry->start)
 334		entry = prev_state(entry);
 335	*prev_ret = entry;
 336
 337	return NULL;
 338}
 339
 340/*
 341 * Inexact rb-tree search, return the next entry if @offset is not found
 342 */
 343static inline struct extent_state *tree_search(struct extent_io_tree *tree, u64 offset)
 344{
 345	return tree_search_for_insert(tree, offset, NULL, NULL);
 346}
 347
 348static void extent_io_tree_panic(const struct extent_io_tree *tree,
 349				 const struct extent_state *state,
 350				 const char *opname,
 351				 int err)
 352{
 353	btrfs_panic(extent_io_tree_to_fs_info(tree), err,
 354		    "extent io tree error on %s state start %llu end %llu",
 355		    opname, state->start, state->end);
 356}
 357
 358static void merge_prev_state(struct extent_io_tree *tree, struct extent_state *state)
 359{
 360	struct extent_state *prev;
 361
 362	prev = prev_state(state);
 363	if (prev && prev->end == state->start - 1 && prev->state == state->state) {
 364		if (is_inode_io_tree(tree))
 365			btrfs_merge_delalloc_extent(extent_io_tree_to_inode(tree),
 366						    state, prev);
 367		state->start = prev->start;
 368		rb_erase(&prev->rb_node, &tree->state);
 369		RB_CLEAR_NODE(&prev->rb_node);
 370		free_extent_state(prev);
 371	}
 372}
 373
 374static void merge_next_state(struct extent_io_tree *tree, struct extent_state *state)
 375{
 376	struct extent_state *next;
 377
 378	next = next_state(state);
 379	if (next && next->start == state->end + 1 && next->state == state->state) {
 380		if (is_inode_io_tree(tree))
 381			btrfs_merge_delalloc_extent(extent_io_tree_to_inode(tree),
 382						    state, next);
 383		state->end = next->end;
 384		rb_erase(&next->rb_node, &tree->state);
 385		RB_CLEAR_NODE(&next->rb_node);
 386		free_extent_state(next);
 387	}
 388}
 389
 390/*
 391 * Utility function to look for merge candidates inside a given range.  Any
 392 * extents with matching state are merged together into a single extent in the
 393 * tree.  Extents with EXTENT_IO in their state field are not merged because
 394 * the end_io handlers need to be able to do operations on them without
 395 * sleeping (or doing allocations/splits).
 396 *
 397 * This should be called with the tree lock held.
 398 */
 399static void merge_state(struct extent_io_tree *tree, struct extent_state *state)
 400{
 
 
 401	if (state->state & (EXTENT_LOCKED | EXTENT_BOUNDARY))
 402		return;
 403
 404	merge_prev_state(tree, state);
 405	merge_next_state(tree, state);
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 406}
 407
 408static void set_state_bits(struct extent_io_tree *tree,
 409			   struct extent_state *state,
 410			   u32 bits, struct extent_changeset *changeset)
 411{
 412	u32 bits_to_set = bits & ~EXTENT_CTLBITS;
 413	int ret;
 414
 415	if (is_inode_io_tree(tree))
 416		btrfs_set_delalloc_extent(extent_io_tree_to_inode(tree), state, bits);
 417
 418	ret = add_extent_changeset(state, bits_to_set, changeset, 1);
 419	BUG_ON(ret < 0);
 420	state->state |= bits_to_set;
 421}
 422
 423/*
 424 * Insert an extent_state struct into the tree.  'bits' are set on the
 425 * struct before it is inserted.
 426 *
 427 * Returns a pointer to the struct extent_state record containing the range
 428 * requested for insertion, which may be the same as the given struct or it
 429 * may be an existing record in the tree that was expanded to accommodate the
 430 * requested range. In case of an extent_state different from the one that was
 431 * given, the later can be freed or reused by the caller.
 432 *
 433 * On error it returns an error pointer.
 434 *
 435 * The tree lock is not taken internally.  This is a utility function and
 436 * probably isn't what you want to call (see set/clear_extent_bit).
 437 */
 438static struct extent_state *insert_state(struct extent_io_tree *tree,
 439					 struct extent_state *state,
 440					 u32 bits,
 441					 struct extent_changeset *changeset)
 442{
 443	struct rb_node **node;
 444	struct rb_node *parent = NULL;
 445	const u64 start = state->start - 1;
 446	const u64 end = state->end + 1;
 447	const bool try_merge = !(bits & (EXTENT_LOCKED | EXTENT_BOUNDARY));
 448
 449	set_state_bits(tree, state, bits, changeset);
 450
 451	node = &tree->state.rb_node;
 452	while (*node) {
 453		struct extent_state *entry;
 454
 455		parent = *node;
 456		entry = rb_entry(parent, struct extent_state, rb_node);
 457
 458		if (state->end < entry->start) {
 459			if (try_merge && end == entry->start &&
 460			    state->state == entry->state) {
 461				if (is_inode_io_tree(tree))
 462					btrfs_merge_delalloc_extent(
 463							extent_io_tree_to_inode(tree),
 464							state, entry);
 465				entry->start = state->start;
 466				merge_prev_state(tree, entry);
 467				state->state = 0;
 468				return entry;
 469			}
 470			node = &(*node)->rb_left;
 471		} else if (state->end > entry->end) {
 472			if (try_merge && entry->end == start &&
 473			    state->state == entry->state) {
 474				if (is_inode_io_tree(tree))
 475					btrfs_merge_delalloc_extent(
 476							extent_io_tree_to_inode(tree),
 477							state, entry);
 478				entry->end = state->end;
 479				merge_next_state(tree, entry);
 480				state->state = 0;
 481				return entry;
 482			}
 483			node = &(*node)->rb_right;
 484		} else {
 485			return ERR_PTR(-EEXIST);
 
 
 
 486		}
 487	}
 488
 489	rb_link_node(&state->rb_node, parent, node);
 490	rb_insert_color(&state->rb_node, &tree->state);
 491
 492	return state;
 
 493}
 494
 495/*
 496 * Insert state to @tree to the location given by @node and @parent.
 497 */
 498static void insert_state_fast(struct extent_io_tree *tree,
 499			      struct extent_state *state, struct rb_node **node,
 500			      struct rb_node *parent, unsigned bits,
 501			      struct extent_changeset *changeset)
 502{
 503	set_state_bits(tree, state, bits, changeset);
 504	rb_link_node(&state->rb_node, parent, node);
 505	rb_insert_color(&state->rb_node, &tree->state);
 506	merge_state(tree, state);
 507}
 508
 509/*
 510 * Split a given extent state struct in two, inserting the preallocated
 511 * struct 'prealloc' as the newly created second half.  'split' indicates an
 512 * offset inside 'orig' where it should be split.
 513 *
 514 * Before calling,
 515 * the tree has 'orig' at [orig->start, orig->end].  After calling, there
 516 * are two extent state structs in the tree:
 517 * prealloc: [orig->start, split - 1]
 518 * orig: [ split, orig->end ]
 519 *
 520 * The tree locks are not taken by this function. They need to be held
 521 * by the caller.
 522 */
 523static int split_state(struct extent_io_tree *tree, struct extent_state *orig,
 524		       struct extent_state *prealloc, u64 split)
 525{
 526	struct rb_node *parent = NULL;
 527	struct rb_node **node;
 528
 529	if (is_inode_io_tree(tree))
 530		btrfs_split_delalloc_extent(extent_io_tree_to_inode(tree), orig,
 531					    split);
 532
 533	prealloc->start = orig->start;
 534	prealloc->end = split - 1;
 535	prealloc->state = orig->state;
 536	orig->start = split;
 537
 538	parent = &orig->rb_node;
 539	node = &parent;
 540	while (*node) {
 541		struct extent_state *entry;
 542
 543		parent = *node;
 544		entry = rb_entry(parent, struct extent_state, rb_node);
 545
 546		if (prealloc->end < entry->start) {
 547			node = &(*node)->rb_left;
 548		} else if (prealloc->end > entry->end) {
 549			node = &(*node)->rb_right;
 550		} else {
 551			free_extent_state(prealloc);
 552			return -EEXIST;
 553		}
 554	}
 555
 556	rb_link_node(&prealloc->rb_node, parent, node);
 557	rb_insert_color(&prealloc->rb_node, &tree->state);
 558
 559	return 0;
 560}
 561
 562/*
 563 * Utility function to clear some bits in an extent state struct.  It will
 564 * optionally wake up anyone waiting on this state (wake == 1).
 565 *
 566 * If no bits are set on the state struct after clearing things, the
 567 * struct is freed and removed from the tree
 568 */
 569static struct extent_state *clear_state_bit(struct extent_io_tree *tree,
 570					    struct extent_state *state,
 571					    u32 bits, int wake,
 572					    struct extent_changeset *changeset)
 573{
 574	struct extent_state *next;
 575	u32 bits_to_clear = bits & ~EXTENT_CTLBITS;
 576	int ret;
 577
 578	if (is_inode_io_tree(tree))
 579		btrfs_clear_delalloc_extent(extent_io_tree_to_inode(tree), state,
 580					    bits);
 581
 582	ret = add_extent_changeset(state, bits_to_clear, changeset, 0);
 583	BUG_ON(ret < 0);
 584	state->state &= ~bits_to_clear;
 585	if (wake)
 586		wake_up(&state->wq);
 587	if (state->state == 0) {
 588		next = next_state(state);
 589		if (extent_state_in_tree(state)) {
 590			rb_erase(&state->rb_node, &tree->state);
 591			RB_CLEAR_NODE(&state->rb_node);
 592			free_extent_state(state);
 593		} else {
 594			WARN_ON(1);
 595		}
 596	} else {
 597		merge_state(tree, state);
 598		next = next_state(state);
 599	}
 600	return next;
 601}
 602
 603/*
 604 * Detect if extent bits request NOWAIT semantics and set the gfp mask accordingly,
 605 * unset the EXTENT_NOWAIT bit.
 606 */
 607static void set_gfp_mask_from_bits(u32 *bits, gfp_t *mask)
 608{
 609	*mask = (*bits & EXTENT_NOWAIT ? GFP_NOWAIT : GFP_NOFS);
 610	*bits &= EXTENT_NOWAIT - 1;
 611}
 612
 613/*
 614 * Clear some bits on a range in the tree.  This may require splitting or
 615 * inserting elements in the tree, so the gfp mask is used to indicate which
 616 * allocations or sleeping are allowed.
 617 *
 618 * Pass 'wake' == 1 to kick any sleepers, and 'delete' == 1 to remove the given
 619 * range from the tree regardless of state (ie for truncate).
 620 *
 621 * The range [start, end] is inclusive.
 622 *
 623 * This takes the tree lock, and returns 0 on success and < 0 on error.
 624 */
 625int __clear_extent_bit(struct extent_io_tree *tree, u64 start, u64 end,
 626		       u32 bits, struct extent_state **cached_state,
 627		       struct extent_changeset *changeset)
 628{
 629	struct extent_state *state;
 630	struct extent_state *cached;
 631	struct extent_state *prealloc = NULL;
 632	u64 last_end;
 633	int err;
 634	int clear = 0;
 635	int wake;
 636	int delete = (bits & EXTENT_CLEAR_ALL_BITS);
 637	gfp_t mask;
 638
 639	set_gfp_mask_from_bits(&bits, &mask);
 640	btrfs_debug_check_extent_io_range(tree, start, end);
 641	trace_btrfs_clear_extent_bit(tree, start, end - start + 1, bits);
 642
 643	if (delete)
 644		bits |= ~EXTENT_CTLBITS;
 645
 646	if (bits & EXTENT_DELALLOC)
 647		bits |= EXTENT_NORESERVE;
 648
 649	wake = (bits & EXTENT_LOCKED) ? 1 : 0;
 650	if (bits & (EXTENT_LOCKED | EXTENT_BOUNDARY))
 651		clear = 1;
 652again:
 653	if (!prealloc) {
 654		/*
 655		 * Don't care for allocation failure here because we might end
 656		 * up not needing the pre-allocated extent state at all, which
 657		 * is the case if we only have in the tree extent states that
 658		 * cover our input range and don't cover too any other range.
 659		 * If we end up needing a new extent state we allocate it later.
 660		 */
 661		prealloc = alloc_extent_state(mask);
 662	}
 663
 664	spin_lock(&tree->lock);
 665	if (cached_state) {
 666		cached = *cached_state;
 667
 668		if (clear) {
 669			*cached_state = NULL;
 670			cached_state = NULL;
 671		}
 672
 673		if (cached && extent_state_in_tree(cached) &&
 674		    cached->start <= start && cached->end > start) {
 675			if (clear)
 676				refcount_dec(&cached->refs);
 677			state = cached;
 678			goto hit_next;
 679		}
 680		if (clear)
 681			free_extent_state(cached);
 682	}
 683
 684	/* This search will find the extents that end after our range starts. */
 685	state = tree_search(tree, start);
 686	if (!state)
 687		goto out;
 688hit_next:
 689	if (state->start > end)
 690		goto out;
 691	WARN_ON(state->end < start);
 692	last_end = state->end;
 693
 694	/* The state doesn't have the wanted bits, go ahead. */
 695	if (!(state->state & bits)) {
 696		state = next_state(state);
 697		goto next;
 698	}
 699
 700	/*
 701	 *     | ---- desired range ---- |
 702	 *  | state | or
 703	 *  | ------------- state -------------- |
 704	 *
 705	 * We need to split the extent we found, and may flip bits on second
 706	 * half.
 707	 *
 708	 * If the extent we found extends past our range, we just split and
 709	 * search again.  It'll get split again the next time though.
 710	 *
 711	 * If the extent we found is inside our range, we clear the desired bit
 712	 * on it.
 713	 */
 714
 715	if (state->start < start) {
 716		prealloc = alloc_extent_state_atomic(prealloc);
 717		if (!prealloc)
 718			goto search_again;
 719		err = split_state(tree, state, prealloc, start);
 720		if (err)
 721			extent_io_tree_panic(tree, state, "split", err);
 722
 723		prealloc = NULL;
 724		if (err)
 725			goto out;
 726		if (state->end <= end) {
 727			state = clear_state_bit(tree, state, bits, wake, changeset);
 728			goto next;
 729		}
 730		goto search_again;
 731	}
 732	/*
 733	 * | ---- desired range ---- |
 734	 *                        | state |
 735	 * We need to split the extent, and clear the bit on the first half.
 736	 */
 737	if (state->start <= end && state->end > end) {
 738		prealloc = alloc_extent_state_atomic(prealloc);
 739		if (!prealloc)
 740			goto search_again;
 741		err = split_state(tree, state, prealloc, end + 1);
 742		if (err)
 743			extent_io_tree_panic(tree, state, "split", err);
 744
 745		if (wake)
 746			wake_up(&state->wq);
 747
 748		clear_state_bit(tree, prealloc, bits, wake, changeset);
 749
 750		prealloc = NULL;
 751		goto out;
 752	}
 753
 754	state = clear_state_bit(tree, state, bits, wake, changeset);
 755next:
 756	if (last_end == (u64)-1)
 757		goto out;
 758	start = last_end + 1;
 759	if (start <= end && state && !need_resched())
 760		goto hit_next;
 761
 762search_again:
 763	if (start > end)
 764		goto out;
 765	spin_unlock(&tree->lock);
 766	if (gfpflags_allow_blocking(mask))
 767		cond_resched();
 768	goto again;
 769
 770out:
 771	spin_unlock(&tree->lock);
 772	if (prealloc)
 773		free_extent_state(prealloc);
 774
 775	return 0;
 776
 777}
 778
 
 
 
 
 
 
 
 
 
 
 
 
 
 779/*
 780 * Wait for one or more bits to clear on a range in the state tree.
 781 * The range [start, end] is inclusive.
 782 * The tree lock is taken by this function
 783 */
 784static void wait_extent_bit(struct extent_io_tree *tree, u64 start, u64 end,
 785			    u32 bits, struct extent_state **cached_state)
 786{
 787	struct extent_state *state;
 788
 789	btrfs_debug_check_extent_io_range(tree, start, end);
 790
 791	spin_lock(&tree->lock);
 792again:
 793	/*
 794	 * Maintain cached_state, as we may not remove it from the tree if there
 795	 * are more bits than the bits we're waiting on set on this state.
 796	 */
 797	if (cached_state && *cached_state) {
 798		state = *cached_state;
 799		if (extent_state_in_tree(state) &&
 800		    state->start <= start && start < state->end)
 801			goto process_node;
 802	}
 803	while (1) {
 804		/*
 805		 * This search will find all the extents that end after our
 806		 * range starts.
 807		 */
 808		state = tree_search(tree, start);
 809process_node:
 810		if (!state)
 811			break;
 812		if (state->start > end)
 813			goto out;
 814
 815		if (state->state & bits) {
 816			DEFINE_WAIT(wait);
 817
 818			start = state->start;
 819			refcount_inc(&state->refs);
 820			prepare_to_wait(&state->wq, &wait, TASK_UNINTERRUPTIBLE);
 821			spin_unlock(&tree->lock);
 822			schedule();
 823			spin_lock(&tree->lock);
 824			finish_wait(&state->wq, &wait);
 825			free_extent_state(state);
 826			goto again;
 827		}
 828		start = state->end + 1;
 829
 830		if (start > end)
 831			break;
 832
 833		if (!cond_resched_lock(&tree->lock)) {
 834			state = next_state(state);
 835			goto process_node;
 836		}
 837	}
 838out:
 839	/* This state is no longer useful, clear it and free it up. */
 840	if (cached_state && *cached_state) {
 841		state = *cached_state;
 842		*cached_state = NULL;
 843		free_extent_state(state);
 844	}
 845	spin_unlock(&tree->lock);
 846}
 847
 848static void cache_state_if_flags(struct extent_state *state,
 849				 struct extent_state **cached_ptr,
 850				 unsigned flags)
 851{
 852	if (cached_ptr && !(*cached_ptr)) {
 853		if (!flags || (state->state & flags)) {
 854			*cached_ptr = state;
 855			refcount_inc(&state->refs);
 856		}
 857	}
 858}
 859
 860static void cache_state(struct extent_state *state,
 861			struct extent_state **cached_ptr)
 862{
 863	return cache_state_if_flags(state, cached_ptr,
 864				    EXTENT_LOCKED | EXTENT_BOUNDARY);
 865}
 866
 867/*
 868 * Find the first state struct with 'bits' set after 'start', and return it.
 869 * tree->lock must be held.  NULL will returned if nothing was found after
 870 * 'start'.
 871 */
 872static struct extent_state *find_first_extent_bit_state(struct extent_io_tree *tree,
 873							u64 start, u32 bits)
 874{
 875	struct extent_state *state;
 876
 877	/*
 878	 * This search will find all the extents that end after our range
 879	 * starts.
 880	 */
 881	state = tree_search(tree, start);
 882	while (state) {
 883		if (state->end >= start && (state->state & bits))
 884			return state;
 885		state = next_state(state);
 886	}
 887	return NULL;
 888}
 889
 890/*
 891 * Find the first offset in the io tree with one or more @bits set.
 892 *
 893 * Note: If there are multiple bits set in @bits, any of them will match.
 894 *
 895 * Return true if we find something, and update @start_ret and @end_ret.
 896 * Return false if we found nothing.
 897 */
 898bool find_first_extent_bit(struct extent_io_tree *tree, u64 start,
 899			   u64 *start_ret, u64 *end_ret, u32 bits,
 900			   struct extent_state **cached_state)
 901{
 902	struct extent_state *state;
 903	bool ret = false;
 904
 905	spin_lock(&tree->lock);
 906	if (cached_state && *cached_state) {
 907		state = *cached_state;
 908		if (state->end == start - 1 && extent_state_in_tree(state)) {
 909			while ((state = next_state(state)) != NULL) {
 910				if (state->state & bits)
 911					break;
 912			}
 913			/*
 914			 * If we found the next extent state, clear cached_state
 915			 * so that we can cache the next extent state below and
 916			 * avoid future calls going over the same extent state
 917			 * again. If we haven't found any, clear as well since
 918			 * it's now useless.
 919			 */
 920			free_extent_state(*cached_state);
 921			*cached_state = NULL;
 922			if (state)
 923				goto got_it;
 924			goto out;
 925		}
 926		free_extent_state(*cached_state);
 927		*cached_state = NULL;
 928	}
 929
 930	state = find_first_extent_bit_state(tree, start, bits);
 931got_it:
 932	if (state) {
 933		cache_state_if_flags(state, cached_state, 0);
 934		*start_ret = state->start;
 935		*end_ret = state->end;
 936		ret = true;
 937	}
 938out:
 939	spin_unlock(&tree->lock);
 940	return ret;
 941}
 942
 943/*
 944 * Find a contiguous area of bits
 945 *
 946 * @tree:      io tree to check
 947 * @start:     offset to start the search from
 948 * @start_ret: the first offset we found with the bits set
 949 * @end_ret:   the final contiguous range of the bits that were set
 950 * @bits:      bits to look for
 951 *
 952 * set_extent_bit and clear_extent_bit can temporarily split contiguous ranges
 953 * to set bits appropriately, and then merge them again.  During this time it
 954 * will drop the tree->lock, so use this helper if you want to find the actual
 955 * contiguous area for given bits.  We will search to the first bit we find, and
 956 * then walk down the tree until we find a non-contiguous area.  The area
 957 * returned will be the full contiguous area with the bits set.
 958 */
 959int find_contiguous_extent_bit(struct extent_io_tree *tree, u64 start,
 960			       u64 *start_ret, u64 *end_ret, u32 bits)
 961{
 962	struct extent_state *state;
 963	int ret = 1;
 964
 965	ASSERT(!btrfs_fs_incompat(extent_io_tree_to_fs_info(tree), NO_HOLES));
 966
 967	spin_lock(&tree->lock);
 968	state = find_first_extent_bit_state(tree, start, bits);
 969	if (state) {
 970		*start_ret = state->start;
 971		*end_ret = state->end;
 972		while ((state = next_state(state)) != NULL) {
 973			if (state->start > (*end_ret + 1))
 974				break;
 975			*end_ret = state->end;
 976		}
 977		ret = 0;
 978	}
 979	spin_unlock(&tree->lock);
 980	return ret;
 981}
 982
 983/*
 984 * Find a contiguous range of bytes in the file marked as delalloc, not more
 985 * than 'max_bytes'.  start and end are used to return the range,
 986 *
 987 * True is returned if we find something, false if nothing was in the tree.
 988 */
 989bool btrfs_find_delalloc_range(struct extent_io_tree *tree, u64 *start,
 990			       u64 *end, u64 max_bytes,
 991			       struct extent_state **cached_state)
 992{
 993	struct extent_state *state;
 994	u64 cur_start = *start;
 995	bool found = false;
 996	u64 total_bytes = 0;
 997
 998	spin_lock(&tree->lock);
 999
1000	/*
1001	 * This search will find all the extents that end after our range
1002	 * starts.
1003	 */
1004	state = tree_search(tree, cur_start);
1005	if (!state) {
1006		*end = (u64)-1;
1007		goto out;
1008	}
1009
1010	while (state) {
1011		if (found && (state->start != cur_start ||
1012			      (state->state & EXTENT_BOUNDARY))) {
1013			goto out;
1014		}
1015		if (!(state->state & EXTENT_DELALLOC)) {
1016			if (!found)
1017				*end = state->end;
1018			goto out;
1019		}
1020		if (!found) {
1021			*start = state->start;
1022			*cached_state = state;
1023			refcount_inc(&state->refs);
1024		}
1025		found = true;
1026		*end = state->end;
1027		cur_start = state->end + 1;
1028		total_bytes += state->end - state->start + 1;
1029		if (total_bytes >= max_bytes)
1030			break;
1031		state = next_state(state);
1032	}
1033out:
1034	spin_unlock(&tree->lock);
1035	return found;
1036}
1037
1038/*
1039 * Set some bits on a range in the tree.  This may require allocations or
1040 * sleeping. By default all allocations use GFP_NOFS, use EXTENT_NOWAIT for
1041 * GFP_NOWAIT.
1042 *
1043 * If any of the exclusive bits are set, this will fail with -EEXIST if some
1044 * part of the range already has the desired bits set.  The extent_state of the
1045 * existing range is returned in failed_state in this case, and the start of the
1046 * existing range is returned in failed_start.  failed_state is used as an
1047 * optimization for wait_extent_bit, failed_start must be used as the source of
1048 * truth as failed_state may have changed since we returned.
1049 *
1050 * [start, end] is inclusive This takes the tree lock.
1051 */
1052static int __set_extent_bit(struct extent_io_tree *tree, u64 start, u64 end,
1053			    u32 bits, u64 *failed_start,
1054			    struct extent_state **failed_state,
1055			    struct extent_state **cached_state,
1056			    struct extent_changeset *changeset)
1057{
1058	struct extent_state *state;
1059	struct extent_state *prealloc = NULL;
1060	struct rb_node **p = NULL;
1061	struct rb_node *parent = NULL;
1062	int err = 0;
1063	u64 last_start;
1064	u64 last_end;
1065	u32 exclusive_bits = (bits & EXTENT_LOCKED);
1066	gfp_t mask;
1067
1068	set_gfp_mask_from_bits(&bits, &mask);
1069	btrfs_debug_check_extent_io_range(tree, start, end);
1070	trace_btrfs_set_extent_bit(tree, start, end - start + 1, bits);
1071
1072	if (exclusive_bits)
1073		ASSERT(failed_start);
1074	else
1075		ASSERT(failed_start == NULL && failed_state == NULL);
1076again:
1077	if (!prealloc) {
1078		/*
1079		 * Don't care for allocation failure here because we might end
1080		 * up not needing the pre-allocated extent state at all, which
1081		 * is the case if we only have in the tree extent states that
1082		 * cover our input range and don't cover too any other range.
1083		 * If we end up needing a new extent state we allocate it later.
1084		 */
1085		prealloc = alloc_extent_state(mask);
1086	}
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			err = -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			err = -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		err = split_state(tree, state, prealloc, start);
1179		if (err)
1180			extent_io_tree_panic(tree, state, "split", err);
1181
1182		prealloc = NULL;
1183		if (err)
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			err = PTR_ERR(inserted_state);
1228			extent_io_tree_panic(tree, prealloc, "insert", err);
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			err = -EEXIST;
1248			goto out;
1249		}
1250
1251		prealloc = alloc_extent_state_atomic(prealloc);
1252		if (!prealloc)
1253			goto search_again;
1254		err = split_state(tree, state, prealloc, end + 1);
1255		if (err)
1256			extent_io_tree_panic(tree, state, "split", err);
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 err;
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 err = 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			err = -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			err = -ENOMEM;
1406			goto out;
1407		}
1408		err = split_state(tree, state, prealloc, start);
1409		if (err)
1410			extent_io_tree_panic(tree, state, "split", err);
1411		prealloc = NULL;
1412		if (err)
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			err = -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			err = PTR_ERR(inserted_state);
1458			extent_io_tree_panic(tree, prealloc, "insert", err);
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			err = -ENOMEM;
1476			goto out;
1477		}
1478
1479		err = split_state(tree, state, prealloc, end + 1);
1480		if (err)
1481			extent_io_tree_panic(tree, state, "split", err);
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 err;
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_LOCKED yet, as current changeset will
1812	 * record any bits changed, so for EXTENT_LOCKED case, it will
1813	 * either fail with -EEXIST or changeset will record the whole
1814	 * range.
1815	 */
1816	ASSERT(!(bits & EXTENT_LOCKED));
1817
1818	return __set_extent_bit(tree, start, end, bits, NULL, NULL, NULL, changeset);
 
1819}
1820
1821int clear_record_extent_bits(struct extent_io_tree *tree, u64 start, u64 end,
1822			     u32 bits, struct extent_changeset *changeset)
1823{
1824	/*
1825	 * Don't support EXTENT_LOCKED case, same reason as
1826	 * set_record_extent_bits().
1827	 */
1828	ASSERT(!(bits & EXTENT_LOCKED));
1829
1830	return __clear_extent_bit(tree, start, end, bits, NULL, changeset);
 
1831}
1832
1833int try_lock_extent(struct extent_io_tree *tree, u64 start, u64 end,
1834		    struct extent_state **cached)
1835{
1836	int err;
1837	u64 failed_start;
1838
1839	err = __set_extent_bit(tree, start, end, EXTENT_LOCKED, &failed_start,
1840			       NULL, cached, NULL);
1841	if (err == -EEXIST) {
1842		if (failed_start > start)
1843			clear_extent_bit(tree, start, failed_start - 1,
1844					 EXTENT_LOCKED, cached);
1845		return 0;
1846	}
1847	return 1;
1848}
1849
1850/*
1851 * Either insert or lock state struct between start and end use mask to tell
1852 * us if waiting is desired.
1853 */
1854int lock_extent(struct extent_io_tree *tree, u64 start, u64 end,
1855		struct extent_state **cached_state)
1856{
1857	struct extent_state *failed_state = NULL;
1858	int err;
1859	u64 failed_start;
1860
1861	err = __set_extent_bit(tree, start, end, EXTENT_LOCKED, &failed_start,
1862			       &failed_state, cached_state, NULL);
1863	while (err == -EEXIST) {
1864		if (failed_start != start)
1865			clear_extent_bit(tree, start, failed_start - 1,
1866					 EXTENT_LOCKED, cached_state);
1867
1868		wait_extent_bit(tree, failed_start, end, EXTENT_LOCKED,
1869				&failed_state);
1870		err = __set_extent_bit(tree, start, end, EXTENT_LOCKED,
1871				       &failed_start, &failed_state,
1872				       cached_state, NULL);
1873	}
1874	return err;
1875}
1876
1877void __cold extent_state_free_cachep(void)
1878{
1879	btrfs_extent_state_leak_debug_check();
1880	kmem_cache_destroy(extent_state_cache);
1881}
1882
1883int __init extent_state_init_cachep(void)
1884{
1885	extent_state_cache = kmem_cache_create("btrfs_extent_state",
1886			sizeof(struct extent_state), 0,
1887			SLAB_MEM_SPREAD, NULL);
1888	if (!extent_state_cache)
1889		return -ENOMEM;
1890
1891	return 0;
1892}