1// SPDX-License-Identifier: GPL-2.0
   2/*
   3 * Copyright (C) 2007 Oracle.  All rights reserved.
   4 */
   5
   6#include <linux/sched.h>
   7#include <linux/sched/signal.h>
   8#include <linux/pagemap.h>
   9#include <linux/writeback.h>
  10#include <linux/blkdev.h>
  11#include <linux/sort.h>
  12#include <linux/rcupdate.h>
  13#include <linux/kthread.h>
  14#include <linux/slab.h>
  15#include <linux/ratelimit.h>
  16#include <linux/percpu_counter.h>
  17#include <linux/lockdep.h>
  18#include <linux/crc32c.h>
  19#include "ctree.h"
  20#include "extent-tree.h"
  21#include "tree-log.h"
  22#include "disk-io.h"
  23#include "print-tree.h"
  24#include "volumes.h"
  25#include "raid56.h"
  26#include "locking.h"
  27#include "free-space-cache.h"
  28#include "free-space-tree.h"
  29#include "sysfs.h"
  30#include "qgroup.h"
  31#include "ref-verify.h"
  32#include "space-info.h"
  33#include "block-rsv.h"
  34#include "delalloc-space.h"
  35#include "discard.h"
  36#include "rcu-string.h"
  37#include "zoned.h"
  38#include "dev-replace.h"
  39#include "fs.h"
  40#include "accessors.h"
  41#include "root-tree.h"
  42#include "file-item.h"
  43#include "orphan.h"
  44#include "tree-checker.h"
  45#include "raid-stripe-tree.h"
  46
  47#undef SCRAMBLE_DELAYED_REFS
  48
  49
  50static int __btrfs_free_extent(struct btrfs_trans_handle *trans,
  51			       struct btrfs_delayed_ref_head *href,
  52			       struct btrfs_delayed_ref_node *node, u64 parent,
  53			       u64 root_objectid, u64 owner_objectid,
  54			       u64 owner_offset,
  55			       struct btrfs_delayed_extent_op *extra_op);
  56static void __run_delayed_extent_op(struct btrfs_delayed_extent_op *extent_op,
  57				    struct extent_buffer *leaf,
  58				    struct btrfs_extent_item *ei);
  59static int alloc_reserved_file_extent(struct btrfs_trans_handle *trans,
  60				      u64 parent, u64 root_objectid,
  61				      u64 flags, u64 owner, u64 offset,
  62				      struct btrfs_key *ins, int ref_mod, u64 oref_root);
  63static int alloc_reserved_tree_block(struct btrfs_trans_handle *trans,
  64				     struct btrfs_delayed_ref_node *node,
  65				     struct btrfs_delayed_extent_op *extent_op);
  66static int find_next_key(struct btrfs_path *path, int level,
  67			 struct btrfs_key *key);
  68
  69static int block_group_bits(struct btrfs_block_group *cache, u64 bits)
  70{
  71	return (cache->flags & bits) == bits;
  72}
  73
  74/* simple helper to search for an existing data extent at a given offset */
  75int btrfs_lookup_data_extent(struct btrfs_fs_info *fs_info, u64 start, u64 len)
  76{
  77	struct btrfs_root *root = btrfs_extent_root(fs_info, start);
  78	int ret;
  79	struct btrfs_key key;
  80	struct btrfs_path *path;
  81
  82	path = btrfs_alloc_path();
  83	if (!path)
  84		return -ENOMEM;
  85
  86	key.objectid = start;
  87	key.offset = len;
  88	key.type = BTRFS_EXTENT_ITEM_KEY;
  89	ret = btrfs_search_slot(NULL, root, &key, path, 0, 0);
  90	btrfs_free_path(path);
  91	return ret;
  92}
  93
  94/*
  95 * helper function to lookup reference count and flags of a tree block.
  96 *
  97 * the head node for delayed ref is used to store the sum of all the
  98 * reference count modifications queued up in the rbtree. the head
  99 * node may also store the extent flags to set. This way you can check
 100 * to see what the reference count and extent flags would be if all of
 101 * the delayed refs are not processed.
 102 */
 103int btrfs_lookup_extent_info(struct btrfs_trans_handle *trans,
 104			     struct btrfs_fs_info *fs_info, u64 bytenr,
 105			     u64 offset, int metadata, u64 *refs, u64 *flags,
 106			     u64 *owning_root)
 107{
 108	struct btrfs_root *extent_root;
 109	struct btrfs_delayed_ref_head *head;
 110	struct btrfs_delayed_ref_root *delayed_refs;
 111	struct btrfs_path *path;
 112	struct btrfs_extent_item *ei;
 113	struct extent_buffer *leaf;
 114	struct btrfs_key key;
 115	u32 item_size;
 116	u64 num_refs;
 117	u64 extent_flags;
 118	u64 owner = 0;
 119	int ret;
 120
 121	/*
 122	 * If we don't have skinny metadata, don't bother doing anything
 123	 * different
 124	 */
 125	if (metadata && !btrfs_fs_incompat(fs_info, SKINNY_METADATA)) {
 126		offset = fs_info->nodesize;
 127		metadata = 0;
 128	}
 129
 130	path = btrfs_alloc_path();
 131	if (!path)
 132		return -ENOMEM;
 133
 134	if (!trans) {
 135		path->skip_locking = 1;
 136		path->search_commit_root = 1;
 137	}
 138
 139search_again:
 140	key.objectid = bytenr;
 141	key.offset = offset;
 142	if (metadata)
 143		key.type = BTRFS_METADATA_ITEM_KEY;
 144	else
 145		key.type = BTRFS_EXTENT_ITEM_KEY;
 146
 147	extent_root = btrfs_extent_root(fs_info, bytenr);
 148	ret = btrfs_search_slot(NULL, extent_root, &key, path, 0, 0);
 149	if (ret < 0)
 150		goto out_free;
 151
 152	if (ret > 0 && metadata && key.type == BTRFS_METADATA_ITEM_KEY) {
 153		if (path->slots[0]) {
 154			path->slots[0]--;
 155			btrfs_item_key_to_cpu(path->nodes[0], &key,
 156					      path->slots[0]);
 157			if (key.objectid == bytenr &&
 158			    key.type == BTRFS_EXTENT_ITEM_KEY &&
 159			    key.offset == fs_info->nodesize)
 160				ret = 0;
 161		}
 162	}
 163
 164	if (ret == 0) {
 165		leaf = path->nodes[0];
 166		item_size = btrfs_item_size(leaf, path->slots[0]);
 167		if (item_size >= sizeof(*ei)) {
 168			ei = btrfs_item_ptr(leaf, path->slots[0],
 169					    struct btrfs_extent_item);
 170			num_refs = btrfs_extent_refs(leaf, ei);
 171			extent_flags = btrfs_extent_flags(leaf, ei);
 172			owner = btrfs_get_extent_owner_root(fs_info, leaf,
 173							    path->slots[0]);
 174		} else {
 175			ret = -EUCLEAN;
 176			btrfs_err(fs_info,
 177			"unexpected extent item size, has %u expect >= %zu",
 178				  item_size, sizeof(*ei));
 179			if (trans)
 180				btrfs_abort_transaction(trans, ret);
 181			else
 182				btrfs_handle_fs_error(fs_info, ret, NULL);
 183
 184			goto out_free;
 185		}
 186
 187		BUG_ON(num_refs == 0);
 188	} else {
 189		num_refs = 0;
 190		extent_flags = 0;
 191		ret = 0;
 192	}
 193
 194	if (!trans)
 195		goto out;
 196
 197	delayed_refs = &trans->transaction->delayed_refs;
 198	spin_lock(&delayed_refs->lock);
 199	head = btrfs_find_delayed_ref_head(delayed_refs, bytenr);
 200	if (head) {
 201		if (!mutex_trylock(&head->mutex)) {
 202			refcount_inc(&head->refs);
 203			spin_unlock(&delayed_refs->lock);
 204
 205			btrfs_release_path(path);
 206
 207			/*
 208			 * Mutex was contended, block until it's released and try
 209			 * again
 210			 */
 211			mutex_lock(&head->mutex);
 212			mutex_unlock(&head->mutex);
 213			btrfs_put_delayed_ref_head(head);
 214			goto search_again;
 215		}
 216		spin_lock(&head->lock);
 217		if (head->extent_op && head->extent_op->update_flags)
 218			extent_flags |= head->extent_op->flags_to_set;
 219		else
 220			BUG_ON(num_refs == 0);
 221
 222		num_refs += head->ref_mod;
 223		spin_unlock(&head->lock);
 224		mutex_unlock(&head->mutex);
 225	}
 226	spin_unlock(&delayed_refs->lock);
 227out:
 228	WARN_ON(num_refs == 0);
 229	if (refs)
 230		*refs = num_refs;
 231	if (flags)
 232		*flags = extent_flags;
 233	if (owning_root)
 234		*owning_root = owner;
 235out_free:
 236	btrfs_free_path(path);
 237	return ret;
 238}
 239
 240/*
 241 * Back reference rules.  Back refs have three main goals:
 242 *
 243 * 1) differentiate between all holders of references to an extent so that
 244 *    when a reference is dropped we can make sure it was a valid reference
 245 *    before freeing the extent.
 246 *
 247 * 2) Provide enough information to quickly find the holders of an extent
 248 *    if we notice a given block is corrupted or bad.
 249 *
 250 * 3) Make it easy to migrate blocks for FS shrinking or storage pool
 251 *    maintenance.  This is actually the same as #2, but with a slightly
 252 *    different use case.
 253 *
 254 * There are two kinds of back refs. The implicit back refs is optimized
 255 * for pointers in non-shared tree blocks. For a given pointer in a block,
 256 * back refs of this kind provide information about the block's owner tree
 257 * and the pointer's key. These information allow us to find the block by
 258 * b-tree searching. The full back refs is for pointers in tree blocks not
 259 * referenced by their owner trees. The location of tree block is recorded
 260 * in the back refs. Actually the full back refs is generic, and can be
 261 * used in all cases the implicit back refs is used. The major shortcoming
 262 * of the full back refs is its overhead. Every time a tree block gets
 263 * COWed, we have to update back refs entry for all pointers in it.
 264 *
 265 * For a newly allocated tree block, we use implicit back refs for
 266 * pointers in it. This means most tree related operations only involve
 267 * implicit back refs. For a tree block created in old transaction, the
 268 * only way to drop a reference to it is COW it. So we can detect the
 269 * event that tree block loses its owner tree's reference and do the
 270 * back refs conversion.
 271 *
 272 * When a tree block is COWed through a tree, there are four cases:
 273 *
 274 * The reference count of the block is one and the tree is the block's
 275 * owner tree. Nothing to do in this case.
 276 *
 277 * The reference count of the block is one and the tree is not the
 278 * block's owner tree. In this case, full back refs is used for pointers
 279 * in the block. Remove these full back refs, add implicit back refs for
 280 * every pointers in the new block.
 281 *
 282 * The reference count of the block is greater than one and the tree is
 283 * the block's owner tree. In this case, implicit back refs is used for
 284 * pointers in the block. Add full back refs for every pointers in the
 285 * block, increase lower level extents' reference counts. The original
 286 * implicit back refs are entailed to the new block.
 287 *
 288 * The reference count of the block is greater than one and the tree is
 289 * not the block's owner tree. Add implicit back refs for every pointer in
 290 * the new block, increase lower level extents' reference count.
 291 *
 292 * Back Reference Key composing:
 293 *
 294 * The key objectid corresponds to the first byte in the extent,
 295 * The key type is used to differentiate between types of back refs.
 296 * There are different meanings of the key offset for different types
 297 * of back refs.
 298 *
 299 * File extents can be referenced by:
 300 *
 301 * - multiple snapshots, subvolumes, or different generations in one subvol
 302 * - different files inside a single subvolume
 303 * - different offsets inside a file (bookend extents in file.c)
 304 *
 305 * The extent ref structure for the implicit back refs has fields for:
 306 *
 307 * - Objectid of the subvolume root
 308 * - objectid of the file holding the reference
 309 * - original offset in the file
 310 * - how many bookend extents
 311 *
 312 * The key offset for the implicit back refs is hash of the first
 313 * three fields.
 314 *
 315 * The extent ref structure for the full back refs has field for:
 316 *
 317 * - number of pointers in the tree leaf
 318 *
 319 * The key offset for the implicit back refs is the first byte of
 320 * the tree leaf
 321 *
 322 * When a file extent is allocated, The implicit back refs is used.
 323 * the fields are filled in:
 324 *
 325 *     (root_key.objectid, inode objectid, offset in file, 1)
 326 *
 327 * When a file extent is removed file truncation, we find the
 328 * corresponding implicit back refs and check the following fields:
 329 *
 330 *     (btrfs_header_owner(leaf), inode objectid, offset in file)
 331 *
 332 * Btree extents can be referenced by:
 333 *
 334 * - Different subvolumes
 335 *
 336 * Both the implicit back refs and the full back refs for tree blocks
 337 * only consist of key. The key offset for the implicit back refs is
 338 * objectid of block's owner tree. The key offset for the full back refs
 339 * is the first byte of parent block.
 340 *
 341 * When implicit back refs is used, information about the lowest key and
 342 * level of the tree block are required. These information are stored in
 343 * tree block info structure.
 344 */
 345
 346/*
 347 * is_data == BTRFS_REF_TYPE_BLOCK, tree block type is required,
 348 * is_data == BTRFS_REF_TYPE_DATA, data type is requiried,
 349 * is_data == BTRFS_REF_TYPE_ANY, either type is OK.
 350 */
 351int btrfs_get_extent_inline_ref_type(const struct extent_buffer *eb,
 352				     struct btrfs_extent_inline_ref *iref,
 353				     enum btrfs_inline_ref_type is_data)
 354{
 355	struct btrfs_fs_info *fs_info = eb->fs_info;
 356	int type = btrfs_extent_inline_ref_type(eb, iref);
 357	u64 offset = btrfs_extent_inline_ref_offset(eb, iref);
 358
 359	if (type == BTRFS_EXTENT_OWNER_REF_KEY) {
 360		ASSERT(btrfs_fs_incompat(fs_info, SIMPLE_QUOTA));
 361		return type;
 362	}
 363
 364	if (type == BTRFS_TREE_BLOCK_REF_KEY ||
 365	    type == BTRFS_SHARED_BLOCK_REF_KEY ||
 366	    type == BTRFS_SHARED_DATA_REF_KEY ||
 367	    type == BTRFS_EXTENT_DATA_REF_KEY) {
 368		if (is_data == BTRFS_REF_TYPE_BLOCK) {
 369			if (type == BTRFS_TREE_BLOCK_REF_KEY)
 370				return type;
 371			if (type == BTRFS_SHARED_BLOCK_REF_KEY) {
 372				ASSERT(fs_info);
 373				/*
 374				 * Every shared one has parent tree block,
 375				 * which must be aligned to sector size.
 376				 */
 377				if (offset && IS_ALIGNED(offset, fs_info->sectorsize))
 378					return type;
 379			}
 380		} else if (is_data == BTRFS_REF_TYPE_DATA) {
 381			if (type == BTRFS_EXTENT_DATA_REF_KEY)
 382				return type;
 383			if (type == BTRFS_SHARED_DATA_REF_KEY) {
 384				ASSERT(fs_info);
 385				/*
 386				 * Every shared one has parent tree block,
 387				 * which must be aligned to sector size.
 388				 */
 389				if (offset &&
 390				    IS_ALIGNED(offset, fs_info->sectorsize))
 391					return type;
 392			}
 393		} else {
 394			ASSERT(is_data == BTRFS_REF_TYPE_ANY);
 395			return type;
 396		}
 397	}
 398
 399	WARN_ON(1);
 400	btrfs_print_leaf(eb);
 401	btrfs_err(fs_info,
 402		  "eb %llu iref 0x%lx invalid extent inline ref type %d",
 403		  eb->start, (unsigned long)iref, type);
 404
 405	return BTRFS_REF_TYPE_INVALID;
 406}
 407
 408u64 hash_extent_data_ref(u64 root_objectid, u64 owner, u64 offset)
 409{
 410	u32 high_crc = ~(u32)0;
 411	u32 low_crc = ~(u32)0;
 412	__le64 lenum;
 413
 414	lenum = cpu_to_le64(root_objectid);
 415	high_crc = crc32c(high_crc, &lenum, sizeof(lenum));
 416	lenum = cpu_to_le64(owner);
 417	low_crc = crc32c(low_crc, &lenum, sizeof(lenum));
 418	lenum = cpu_to_le64(offset);
 419	low_crc = crc32c(low_crc, &lenum, sizeof(lenum));
 420
 421	return ((u64)high_crc << 31) ^ (u64)low_crc;
 422}
 423
 424static u64 hash_extent_data_ref_item(struct extent_buffer *leaf,
 425				     struct btrfs_extent_data_ref *ref)
 426{
 427	return hash_extent_data_ref(btrfs_extent_data_ref_root(leaf, ref),
 428				    btrfs_extent_data_ref_objectid(leaf, ref),
 429				    btrfs_extent_data_ref_offset(leaf, ref));
 430}
 431
 432static int match_extent_data_ref(struct extent_buffer *leaf,
 433				 struct btrfs_extent_data_ref *ref,
 434				 u64 root_objectid, u64 owner, u64 offset)
 435{
 436	if (btrfs_extent_data_ref_root(leaf, ref) != root_objectid ||
 437	    btrfs_extent_data_ref_objectid(leaf, ref) != owner ||
 438	    btrfs_extent_data_ref_offset(leaf, ref) != offset)
 439		return 0;
 440	return 1;
 441}
 442
 443static noinline int lookup_extent_data_ref(struct btrfs_trans_handle *trans,
 444					   struct btrfs_path *path,
 445					   u64 bytenr, u64 parent,
 446					   u64 root_objectid,
 447					   u64 owner, u64 offset)
 448{
 449	struct btrfs_root *root = btrfs_extent_root(trans->fs_info, bytenr);
 450	struct btrfs_key key;
 451	struct btrfs_extent_data_ref *ref;
 452	struct extent_buffer *leaf;
 453	u32 nritems;
 454	int ret;
 455	int recow;
 456	int err = -ENOENT;
 457
 458	key.objectid = bytenr;
 459	if (parent) {
 460		key.type = BTRFS_SHARED_DATA_REF_KEY;
 461		key.offset = parent;
 462	} else {
 463		key.type = BTRFS_EXTENT_DATA_REF_KEY;
 464		key.offset = hash_extent_data_ref(root_objectid,
 465						  owner, offset);
 466	}
 467again:
 468	recow = 0;
 469	ret = btrfs_search_slot(trans, root, &key, path, -1, 1);
 470	if (ret < 0) {
 471		err = ret;
 472		goto fail;
 473	}
 474
 475	if (parent) {
 476		if (!ret)
 477			return 0;
 478		goto fail;
 479	}
 480
 481	leaf = path->nodes[0];
 482	nritems = btrfs_header_nritems(leaf);
 483	while (1) {
 484		if (path->slots[0] >= nritems) {
 485			ret = btrfs_next_leaf(root, path);
 486			if (ret < 0)
 487				err = ret;
 488			if (ret)
 489				goto fail;
 490
 491			leaf = path->nodes[0];
 492			nritems = btrfs_header_nritems(leaf);
 493			recow = 1;
 494		}
 495
 496		btrfs_item_key_to_cpu(leaf, &key, path->slots[0]);
 497		if (key.objectid != bytenr ||
 498		    key.type != BTRFS_EXTENT_DATA_REF_KEY)
 499			goto fail;
 500
 501		ref = btrfs_item_ptr(leaf, path->slots[0],
 502				     struct btrfs_extent_data_ref);
 503
 504		if (match_extent_data_ref(leaf, ref, root_objectid,
 505					  owner, offset)) {
 506			if (recow) {
 507				btrfs_release_path(path);
 508				goto again;
 509			}
 510			err = 0;
 511			break;
 512		}
 513		path->slots[0]++;
 514	}
 515fail:
 516	return err;
 517}
 518
 519static noinline int insert_extent_data_ref(struct btrfs_trans_handle *trans,
 520					   struct btrfs_path *path,
 521					   u64 bytenr, u64 parent,
 522					   u64 root_objectid, u64 owner,
 523					   u64 offset, int refs_to_add)
 524{
 525	struct btrfs_root *root = btrfs_extent_root(trans->fs_info, bytenr);
 526	struct btrfs_key key;
 527	struct extent_buffer *leaf;
 528	u32 size;
 529	u32 num_refs;
 530	int ret;
 531
 532	key.objectid = bytenr;
 533	if (parent) {
 534		key.type = BTRFS_SHARED_DATA_REF_KEY;
 535		key.offset = parent;
 536		size = sizeof(struct btrfs_shared_data_ref);
 537	} else {
 538		key.type = BTRFS_EXTENT_DATA_REF_KEY;
 539		key.offset = hash_extent_data_ref(root_objectid,
 540						  owner, offset);
 541		size = sizeof(struct btrfs_extent_data_ref);
 542	}
 543
 544	ret = btrfs_insert_empty_item(trans, root, path, &key, size);
 545	if (ret && ret != -EEXIST)
 546		goto fail;
 547
 548	leaf = path->nodes[0];
 549	if (parent) {
 550		struct btrfs_shared_data_ref *ref;
 551		ref = btrfs_item_ptr(leaf, path->slots[0],
 552				     struct btrfs_shared_data_ref);
 553		if (ret == 0) {
 554			btrfs_set_shared_data_ref_count(leaf, ref, refs_to_add);
 555		} else {
 556			num_refs = btrfs_shared_data_ref_count(leaf, ref);
 557			num_refs += refs_to_add;
 558			btrfs_set_shared_data_ref_count(leaf, ref, num_refs);
 559		}
 560	} else {
 561		struct btrfs_extent_data_ref *ref;
 562		while (ret == -EEXIST) {
 563			ref = btrfs_item_ptr(leaf, path->slots[0],
 564					     struct btrfs_extent_data_ref);
 565			if (match_extent_data_ref(leaf, ref, root_objectid,
 566						  owner, offset))
 567				break;
 568			btrfs_release_path(path);
 569			key.offset++;
 570			ret = btrfs_insert_empty_item(trans, root, path, &key,
 571						      size);
 572			if (ret && ret != -EEXIST)
 573				goto fail;
 574
 575			leaf = path->nodes[0];
 576		}
 577		ref = btrfs_item_ptr(leaf, path->slots[0],
 578				     struct btrfs_extent_data_ref);
 579		if (ret == 0) {
 580			btrfs_set_extent_data_ref_root(leaf, ref,
 581						       root_objectid);
 582			btrfs_set_extent_data_ref_objectid(leaf, ref, owner);
 583			btrfs_set_extent_data_ref_offset(leaf, ref, offset);
 584			btrfs_set_extent_data_ref_count(leaf, ref, refs_to_add);
 585		} else {
 586			num_refs = btrfs_extent_data_ref_count(leaf, ref);
 587			num_refs += refs_to_add;
 588			btrfs_set_extent_data_ref_count(leaf, ref, num_refs);
 589		}
 590	}
 591	btrfs_mark_buffer_dirty(trans, leaf);
 592	ret = 0;
 593fail:
 594	btrfs_release_path(path);
 595	return ret;
 596}
 597
 598static noinline int remove_extent_data_ref(struct btrfs_trans_handle *trans,
 599					   struct btrfs_root *root,
 600					   struct btrfs_path *path,
 601					   int refs_to_drop)
 602{
 603	struct btrfs_key key;
 604	struct btrfs_extent_data_ref *ref1 = NULL;
 605	struct btrfs_shared_data_ref *ref2 = NULL;
 606	struct extent_buffer *leaf;
 607	u32 num_refs = 0;
 608	int ret = 0;
 609
 610	leaf = path->nodes[0];
 611	btrfs_item_key_to_cpu(leaf, &key, path->slots[0]);
 612
 613	if (key.type == BTRFS_EXTENT_DATA_REF_KEY) {
 614		ref1 = btrfs_item_ptr(leaf, path->slots[0],
 615				      struct btrfs_extent_data_ref);
 616		num_refs = btrfs_extent_data_ref_count(leaf, ref1);
 617	} else if (key.type == BTRFS_SHARED_DATA_REF_KEY) {
 618		ref2 = btrfs_item_ptr(leaf, path->slots[0],
 619				      struct btrfs_shared_data_ref);
 620		num_refs = btrfs_shared_data_ref_count(leaf, ref2);
 621	} else {
 622		btrfs_err(trans->fs_info,
 623			  "unrecognized backref key (%llu %u %llu)",
 624			  key.objectid, key.type, key.offset);
 625		btrfs_abort_transaction(trans, -EUCLEAN);
 626		return -EUCLEAN;
 627	}
 628
 629	BUG_ON(num_refs < refs_to_drop);
 630	num_refs -= refs_to_drop;
 631
 632	if (num_refs == 0) {
 633		ret = btrfs_del_item(trans, root, path);
 634	} else {
 635		if (key.type == BTRFS_EXTENT_DATA_REF_KEY)
 636			btrfs_set_extent_data_ref_count(leaf, ref1, num_refs);
 637		else if (key.type == BTRFS_SHARED_DATA_REF_KEY)
 638			btrfs_set_shared_data_ref_count(leaf, ref2, num_refs);
 639		btrfs_mark_buffer_dirty(trans, leaf);
 640	}
 641	return ret;
 642}
 643
 644static noinline u32 extent_data_ref_count(struct btrfs_path *path,
 645					  struct btrfs_extent_inline_ref *iref)
 646{
 647	struct btrfs_key key;
 648	struct extent_buffer *leaf;
 649	struct btrfs_extent_data_ref *ref1;
 650	struct btrfs_shared_data_ref *ref2;
 651	u32 num_refs = 0;
 652	int type;
 653
 654	leaf = path->nodes[0];
 655	btrfs_item_key_to_cpu(leaf, &key, path->slots[0]);
 656
 657	if (iref) {
 658		/*
 659		 * If type is invalid, we should have bailed out earlier than
 660		 * this call.
 661		 */
 662		type = btrfs_get_extent_inline_ref_type(leaf, iref, BTRFS_REF_TYPE_DATA);
 663		ASSERT(type != BTRFS_REF_TYPE_INVALID);
 664		if (type == BTRFS_EXTENT_DATA_REF_KEY) {
 665			ref1 = (struct btrfs_extent_data_ref *)(&iref->offset);
 666			num_refs = btrfs_extent_data_ref_count(leaf, ref1);
 667		} else {
 668			ref2 = (struct btrfs_shared_data_ref *)(iref + 1);
 669			num_refs = btrfs_shared_data_ref_count(leaf, ref2);
 670		}
 671	} else if (key.type == BTRFS_EXTENT_DATA_REF_KEY) {
 672		ref1 = btrfs_item_ptr(leaf, path->slots[0],
 673				      struct btrfs_extent_data_ref);
 674		num_refs = btrfs_extent_data_ref_count(leaf, ref1);
 675	} else if (key.type == BTRFS_SHARED_DATA_REF_KEY) {
 676		ref2 = btrfs_item_ptr(leaf, path->slots[0],
 677				      struct btrfs_shared_data_ref);
 678		num_refs = btrfs_shared_data_ref_count(leaf, ref2);
 679	} else {
 680		WARN_ON(1);
 681	}
 682	return num_refs;
 683}
 684
 685static noinline int lookup_tree_block_ref(struct btrfs_trans_handle *trans,
 686					  struct btrfs_path *path,
 687					  u64 bytenr, u64 parent,
 688					  u64 root_objectid)
 689{
 690	struct btrfs_root *root = btrfs_extent_root(trans->fs_info, bytenr);
 691	struct btrfs_key key;
 692	int ret;
 693
 694	key.objectid = bytenr;
 695	if (parent) {
 696		key.type = BTRFS_SHARED_BLOCK_REF_KEY;
 697		key.offset = parent;
 698	} else {
 699		key.type = BTRFS_TREE_BLOCK_REF_KEY;
 700		key.offset = root_objectid;
 701	}
 702
 703	ret = btrfs_search_slot(trans, root, &key, path, -1, 1);
 704	if (ret > 0)
 705		ret = -ENOENT;
 706	return ret;
 707}
 708
 709static noinline int insert_tree_block_ref(struct btrfs_trans_handle *trans,
 710					  struct btrfs_path *path,
 711					  u64 bytenr, u64 parent,
 712					  u64 root_objectid)
 713{
 714	struct btrfs_root *root = btrfs_extent_root(trans->fs_info, bytenr);
 715	struct btrfs_key key;
 716	int ret;
 717
 718	key.objectid = bytenr;
 719	if (parent) {
 720		key.type = BTRFS_SHARED_BLOCK_REF_KEY;
 721		key.offset = parent;
 722	} else {
 723		key.type = BTRFS_TREE_BLOCK_REF_KEY;
 724		key.offset = root_objectid;
 725	}
 726
 727	ret = btrfs_insert_empty_item(trans, root, path, &key, 0);
 728	btrfs_release_path(path);
 729	return ret;
 730}
 731
 732static inline int extent_ref_type(u64 parent, u64 owner)
 733{
 734	int type;
 735	if (owner < BTRFS_FIRST_FREE_OBJECTID) {
 736		if (parent > 0)
 737			type = BTRFS_SHARED_BLOCK_REF_KEY;
 738		else
 739			type = BTRFS_TREE_BLOCK_REF_KEY;
 740	} else {
 741		if (parent > 0)
 742			type = BTRFS_SHARED_DATA_REF_KEY;
 743		else
 744			type = BTRFS_EXTENT_DATA_REF_KEY;
 745	}
 746	return type;
 747}
 748
 749static int find_next_key(struct btrfs_path *path, int level,
 750			 struct btrfs_key *key)
 751
 752{
 753	for (; level < BTRFS_MAX_LEVEL; level++) {
 754		if (!path->nodes[level])
 755			break;
 756		if (path->slots[level] + 1 >=
 757		    btrfs_header_nritems(path->nodes[level]))
 758			continue;
 759		if (level == 0)
 760			btrfs_item_key_to_cpu(path->nodes[level], key,
 761					      path->slots[level] + 1);
 762		else
 763			btrfs_node_key_to_cpu(path->nodes[level], key,
 764					      path->slots[level] + 1);
 765		return 0;
 766	}
 767	return 1;
 768}
 769
 770/*
 771 * look for inline back ref. if back ref is found, *ref_ret is set
 772 * to the address of inline back ref, and 0 is returned.
 773 *
 774 * if back ref isn't found, *ref_ret is set to the address where it
 775 * should be inserted, and -ENOENT is returned.
 776 *
 777 * if insert is true and there are too many inline back refs, the path
 778 * points to the extent item, and -EAGAIN is returned.
 779 *
 780 * NOTE: inline back refs are ordered in the same way that back ref
 781 *	 items in the tree are ordered.
 782 */
 783static noinline_for_stack
 784int lookup_inline_extent_backref(struct btrfs_trans_handle *trans,
 785				 struct btrfs_path *path,
 786				 struct btrfs_extent_inline_ref **ref_ret,
 787				 u64 bytenr, u64 num_bytes,
 788				 u64 parent, u64 root_objectid,
 789				 u64 owner, u64 offset, int insert)
 790{
 791	struct btrfs_fs_info *fs_info = trans->fs_info;
 792	struct btrfs_root *root = btrfs_extent_root(fs_info, bytenr);
 793	struct btrfs_key key;
 794	struct extent_buffer *leaf;
 795	struct btrfs_extent_item *ei;
 796	struct btrfs_extent_inline_ref *iref;
 797	u64 flags;
 798	u64 item_size;
 799	unsigned long ptr;
 800	unsigned long end;
 801	int extra_size;
 802	int type;
 803	int want;
 804	int ret;
 805	bool skinny_metadata = btrfs_fs_incompat(fs_info, SKINNY_METADATA);
 806	int needed;
 807
 808	key.objectid = bytenr;
 809	key.type = BTRFS_EXTENT_ITEM_KEY;
 810	key.offset = num_bytes;
 811
 812	want = extent_ref_type(parent, owner);
 813	if (insert) {
 814		extra_size = btrfs_extent_inline_ref_size(want);
 815		path->search_for_extension = 1;
 816		path->keep_locks = 1;
 817	} else
 818		extra_size = -1;
 819
 820	/*
 821	 * Owner is our level, so we can just add one to get the level for the
 822	 * block we are interested in.
 823	 */
 824	if (skinny_metadata && owner < BTRFS_FIRST_FREE_OBJECTID) {
 825		key.type = BTRFS_METADATA_ITEM_KEY;
 826		key.offset = owner;
 827	}
 828
 829again:
 830	ret = btrfs_search_slot(trans, root, &key, path, extra_size, 1);
 831	if (ret < 0)
 832		goto out;
 833
 834	/*
 835	 * We may be a newly converted file system which still has the old fat
 836	 * extent entries for metadata, so try and see if we have one of those.
 837	 */
 838	if (ret > 0 && skinny_metadata) {
 839		skinny_metadata = false;
 840		if (path->slots[0]) {
 841			path->slots[0]--;
 842			btrfs_item_key_to_cpu(path->nodes[0], &key,
 843					      path->slots[0]);
 844			if (key.objectid == bytenr &&
 845			    key.type == BTRFS_EXTENT_ITEM_KEY &&
 846			    key.offset == num_bytes)
 847				ret = 0;
 848		}
 849		if (ret) {
 850			key.objectid = bytenr;
 851			key.type = BTRFS_EXTENT_ITEM_KEY;
 852			key.offset = num_bytes;
 853			btrfs_release_path(path);
 854			goto again;
 855		}
 856	}
 857
 858	if (ret && !insert) {
 859		ret = -ENOENT;
 860		goto out;
 861	} else if (WARN_ON(ret)) {
 862		btrfs_print_leaf(path->nodes[0]);
 863		btrfs_err(fs_info,
 864"extent item not found for insert, bytenr %llu num_bytes %llu parent %llu root_objectid %llu owner %llu offset %llu",
 865			  bytenr, num_bytes, parent, root_objectid, owner,
 866			  offset);
 867		ret = -EUCLEAN;
 868		goto out;
 869	}
 870
 871	leaf = path->nodes[0];
 872	item_size = btrfs_item_size(leaf, path->slots[0]);
 873	if (unlikely(item_size < sizeof(*ei))) {
 874		ret = -EUCLEAN;
 875		btrfs_err(fs_info,
 876			  "unexpected extent item size, has %llu expect >= %zu",
 877			  item_size, sizeof(*ei));
 878		btrfs_abort_transaction(trans, ret);
 879		goto out;
 880	}
 881
 882	ei = btrfs_item_ptr(leaf, path->slots[0], struct btrfs_extent_item);
 883	flags = btrfs_extent_flags(leaf, ei);
 884
 885	ptr = (unsigned long)(ei + 1);
 886	end = (unsigned long)ei + item_size;
 887
 888	if (flags & BTRFS_EXTENT_FLAG_TREE_BLOCK && !skinny_metadata) {
 889		ptr += sizeof(struct btrfs_tree_block_info);
 890		BUG_ON(ptr > end);
 891	}
 892
 893	if (owner >= BTRFS_FIRST_FREE_OBJECTID)
 894		needed = BTRFS_REF_TYPE_DATA;
 895	else
 896		needed = BTRFS_REF_TYPE_BLOCK;
 897
 898	ret = -ENOENT;
 899	while (ptr < end) {
 900		iref = (struct btrfs_extent_inline_ref *)ptr;
 901		type = btrfs_get_extent_inline_ref_type(leaf, iref, needed);
 902		if (type == BTRFS_EXTENT_OWNER_REF_KEY) {
 903			ASSERT(btrfs_fs_incompat(fs_info, SIMPLE_QUOTA));
 904			ptr += btrfs_extent_inline_ref_size(type);
 905			continue;
 906		}
 907		if (type == BTRFS_REF_TYPE_INVALID) {
 908			ret = -EUCLEAN;
 909			goto out;
 910		}
 911
 912		if (want < type)
 913			break;
 914		if (want > type) {
 915			ptr += btrfs_extent_inline_ref_size(type);
 916			continue;
 917		}
 918
 919		if (type == BTRFS_EXTENT_DATA_REF_KEY) {
 920			struct btrfs_extent_data_ref *dref;
 921			dref = (struct btrfs_extent_data_ref *)(&iref->offset);
 922			if (match_extent_data_ref(leaf, dref, root_objectid,
 923						  owner, offset)) {
 924				ret = 0;
 925				break;
 926			}
 927			if (hash_extent_data_ref_item(leaf, dref) <
 928			    hash_extent_data_ref(root_objectid, owner, offset))
 929				break;
 930		} else {
 931			u64 ref_offset;
 932			ref_offset = btrfs_extent_inline_ref_offset(leaf, iref);
 933			if (parent > 0) {
 934				if (parent == ref_offset) {
 935					ret = 0;
 936					break;
 937				}
 938				if (ref_offset < parent)
 939					break;
 940			} else {
 941				if (root_objectid == ref_offset) {
 942					ret = 0;
 943					break;
 944				}
 945				if (ref_offset < root_objectid)
 946					break;
 947			}
 948		}
 949		ptr += btrfs_extent_inline_ref_size(type);
 950	}
 951
 952	if (unlikely(ptr > end)) {
 953		ret = -EUCLEAN;
 954		btrfs_print_leaf(path->nodes[0]);
 955		btrfs_crit(fs_info,
 956"overrun extent record at slot %d while looking for inline extent for root %llu owner %llu offset %llu parent %llu",
 957			   path->slots[0], root_objectid, owner, offset, parent);
 958		goto out;
 959	}
 960
 961	if (ret == -ENOENT && insert) {
 962		if (item_size + extra_size >=
 963		    BTRFS_MAX_EXTENT_ITEM_SIZE(root)) {
 964			ret = -EAGAIN;
 965			goto out;
 966		}
 967		/*
 968		 * To add new inline back ref, we have to make sure
 969		 * there is no corresponding back ref item.
 970		 * For simplicity, we just do not add new inline back
 971		 * ref if there is any kind of item for this block
 972		 */
 973		if (find_next_key(path, 0, &key) == 0 &&
 974		    key.objectid == bytenr &&
 975		    key.type < BTRFS_BLOCK_GROUP_ITEM_KEY) {
 976			ret = -EAGAIN;
 977			goto out;
 978		}
 979	}
 980	*ref_ret = (struct btrfs_extent_inline_ref *)ptr;
 981out:
 982	if (insert) {
 983		path->keep_locks = 0;
 984		path->search_for_extension = 0;
 985		btrfs_unlock_up_safe(path, 1);
 986	}
 987	return ret;
 988}
 989
 990/*
 991 * helper to add new inline back ref
 992 */
 993static noinline_for_stack
 994void setup_inline_extent_backref(struct btrfs_trans_handle *trans,
 995				 struct btrfs_path *path,
 996				 struct btrfs_extent_inline_ref *iref,
 997				 u64 parent, u64 root_objectid,
 998				 u64 owner, u64 offset, int refs_to_add,
 999				 struct btrfs_delayed_extent_op *extent_op)
1000{
1001	struct extent_buffer *leaf;
1002	struct btrfs_extent_item *ei;
1003	unsigned long ptr;
1004	unsigned long end;
1005	unsigned long item_offset;
1006	u64 refs;
1007	int size;
1008	int type;
1009
1010	leaf = path->nodes[0];
1011	ei = btrfs_item_ptr(leaf, path->slots[0], struct btrfs_extent_item);
1012	item_offset = (unsigned long)iref - (unsigned long)ei;
1013
1014	type = extent_ref_type(parent, owner);
1015	size = btrfs_extent_inline_ref_size(type);
1016
1017	btrfs_extend_item(trans, path, size);
1018
1019	ei = btrfs_item_ptr(leaf, path->slots[0], struct btrfs_extent_item);
1020	refs = btrfs_extent_refs(leaf, ei);
1021	refs += refs_to_add;
1022	btrfs_set_extent_refs(leaf, ei, refs);
1023	if (extent_op)
1024		__run_delayed_extent_op(extent_op, leaf, ei);
1025
1026	ptr = (unsigned long)ei + item_offset;
1027	end = (unsigned long)ei + btrfs_item_size(leaf, path->slots[0]);
1028	if (ptr < end - size)
1029		memmove_extent_buffer(leaf, ptr + size, ptr,
1030				      end - size - ptr);
1031
1032	iref = (struct btrfs_extent_inline_ref *)ptr;
1033	btrfs_set_extent_inline_ref_type(leaf, iref, type);
1034	if (type == BTRFS_EXTENT_DATA_REF_KEY) {
1035		struct btrfs_extent_data_ref *dref;
1036		dref = (struct btrfs_extent_data_ref *)(&iref->offset);
1037		btrfs_set_extent_data_ref_root(leaf, dref, root_objectid);
1038		btrfs_set_extent_data_ref_objectid(leaf, dref, owner);
1039		btrfs_set_extent_data_ref_offset(leaf, dref, offset);
1040		btrfs_set_extent_data_ref_count(leaf, dref, refs_to_add);
1041	} else if (type == BTRFS_SHARED_DATA_REF_KEY) {
1042		struct btrfs_shared_data_ref *sref;
1043		sref = (struct btrfs_shared_data_ref *)(iref + 1);
1044		btrfs_set_shared_data_ref_count(leaf, sref, refs_to_add);
1045		btrfs_set_extent_inline_ref_offset(leaf, iref, parent);
1046	} else if (type == BTRFS_SHARED_BLOCK_REF_KEY) {
1047		btrfs_set_extent_inline_ref_offset(leaf, iref, parent);
1048	} else {
1049		btrfs_set_extent_inline_ref_offset(leaf, iref, root_objectid);
1050	}
1051	btrfs_mark_buffer_dirty(trans, leaf);
1052}
1053
1054static int lookup_extent_backref(struct btrfs_trans_handle *trans,
1055				 struct btrfs_path *path,
1056				 struct btrfs_extent_inline_ref **ref_ret,
1057				 u64 bytenr, u64 num_bytes, u64 parent,
1058				 u64 root_objectid, u64 owner, u64 offset)
1059{
1060	int ret;
1061
1062	ret = lookup_inline_extent_backref(trans, path, ref_ret, bytenr,
1063					   num_bytes, parent, root_objectid,
1064					   owner, offset, 0);
1065	if (ret != -ENOENT)
1066		return ret;
1067
1068	btrfs_release_path(path);
1069	*ref_ret = NULL;
1070
1071	if (owner < BTRFS_FIRST_FREE_OBJECTID) {
1072		ret = lookup_tree_block_ref(trans, path, bytenr, parent,
1073					    root_objectid);
1074	} else {
1075		ret = lookup_extent_data_ref(trans, path, bytenr, parent,
1076					     root_objectid, owner, offset);
1077	}
1078	return ret;
1079}
1080
1081/*
1082 * helper to update/remove inline back ref
1083 */
1084static noinline_for_stack int update_inline_extent_backref(
1085				  struct btrfs_trans_handle *trans,
1086				  struct btrfs_path *path,
1087				  struct btrfs_extent_inline_ref *iref,
1088				  int refs_to_mod,
1089				  struct btrfs_delayed_extent_op *extent_op)
1090{
1091	struct extent_buffer *leaf = path->nodes[0];
1092	struct btrfs_fs_info *fs_info = leaf->fs_info;
1093	struct btrfs_extent_item *ei;
1094	struct btrfs_extent_data_ref *dref = NULL;
1095	struct btrfs_shared_data_ref *sref = NULL;
1096	unsigned long ptr;
1097	unsigned long end;
1098	u32 item_size;
1099	int size;
1100	int type;
1101	u64 refs;
1102
1103	ei = btrfs_item_ptr(leaf, path->slots[0], struct btrfs_extent_item);
1104	refs = btrfs_extent_refs(leaf, ei);
1105	if (unlikely(refs_to_mod < 0 && refs + refs_to_mod <= 0)) {
1106		struct btrfs_key key;
1107		u32 extent_size;
1108
1109		btrfs_item_key_to_cpu(leaf, &key, path->slots[0]);
1110		if (key.type == BTRFS_METADATA_ITEM_KEY)
1111			extent_size = fs_info->nodesize;
1112		else
1113			extent_size = key.offset;
1114		btrfs_print_leaf(leaf);
1115		btrfs_err(fs_info,
1116	"invalid refs_to_mod for extent %llu num_bytes %u, has %d expect >= -%llu",
1117			  key.objectid, extent_size, refs_to_mod, refs);
1118		return -EUCLEAN;
1119	}
1120	refs += refs_to_mod;
1121	btrfs_set_extent_refs(leaf, ei, refs);
1122	if (extent_op)
1123		__run_delayed_extent_op(extent_op, leaf, ei);
1124
1125	type = btrfs_get_extent_inline_ref_type(leaf, iref, BTRFS_REF_TYPE_ANY);
1126	/*
1127	 * Function btrfs_get_extent_inline_ref_type() has already printed
1128	 * error messages.
1129	 */
1130	if (unlikely(type == BTRFS_REF_TYPE_INVALID))
1131		return -EUCLEAN;
1132
1133	if (type == BTRFS_EXTENT_DATA_REF_KEY) {
1134		dref = (struct btrfs_extent_data_ref *)(&iref->offset);
1135		refs = btrfs_extent_data_ref_count(leaf, dref);
1136	} else if (type == BTRFS_SHARED_DATA_REF_KEY) {
1137		sref = (struct btrfs_shared_data_ref *)(iref + 1);
1138		refs = btrfs_shared_data_ref_count(leaf, sref);
1139	} else {
1140		refs = 1;
1141		/*
1142		 * For tree blocks we can only drop one ref for it, and tree
1143		 * blocks should not have refs > 1.
1144		 *
1145		 * Furthermore if we're inserting a new inline backref, we
1146		 * won't reach this path either. That would be
1147		 * setup_inline_extent_backref().
1148		 */
1149		if (unlikely(refs_to_mod != -1)) {
1150			struct btrfs_key key;
1151
1152			btrfs_item_key_to_cpu(leaf, &key, path->slots[0]);
1153
1154			btrfs_print_leaf(leaf);
1155			btrfs_err(fs_info,
1156			"invalid refs_to_mod for tree block %llu, has %d expect -1",
1157				  key.objectid, refs_to_mod);
1158			return -EUCLEAN;
1159		}
1160	}
1161
1162	if (unlikely(refs_to_mod < 0 && refs < -refs_to_mod)) {
1163		struct btrfs_key key;
1164		u32 extent_size;
1165
1166		btrfs_item_key_to_cpu(leaf, &key, path->slots[0]);
1167		if (key.type == BTRFS_METADATA_ITEM_KEY)
1168			extent_size = fs_info->nodesize;
1169		else
1170			extent_size = key.offset;
1171		btrfs_print_leaf(leaf);
1172		btrfs_err(fs_info,
1173"invalid refs_to_mod for backref entry, iref %lu extent %llu num_bytes %u, has %d expect >= -%llu",
1174			  (unsigned long)iref, key.objectid, extent_size,
1175			  refs_to_mod, refs);
1176		return -EUCLEAN;
1177	}
1178	refs += refs_to_mod;
1179
1180	if (refs > 0) {
1181		if (type == BTRFS_EXTENT_DATA_REF_KEY)
1182			btrfs_set_extent_data_ref_count(leaf, dref, refs);
1183		else
1184			btrfs_set_shared_data_ref_count(leaf, sref, refs);
1185	} else {
1186		size =  btrfs_extent_inline_ref_size(type);
1187		item_size = btrfs_item_size(leaf, path->slots[0]);
1188		ptr = (unsigned long)iref;
1189		end = (unsigned long)ei + item_size;
1190		if (ptr + size < end)
1191			memmove_extent_buffer(leaf, ptr, ptr + size,
1192					      end - ptr - size);
1193		item_size -= size;
1194		btrfs_truncate_item(trans, path, item_size, 1);
1195	}
1196	btrfs_mark_buffer_dirty(trans, leaf);
1197	return 0;
1198}
1199
1200static noinline_for_stack
1201int insert_inline_extent_backref(struct btrfs_trans_handle *trans,
1202				 struct btrfs_path *path,
1203				 u64 bytenr, u64 num_bytes, u64 parent,
1204				 u64 root_objectid, u64 owner,
1205				 u64 offset, int refs_to_add,
1206				 struct btrfs_delayed_extent_op *extent_op)
1207{
1208	struct btrfs_extent_inline_ref *iref;
1209	int ret;
1210
1211	ret = lookup_inline_extent_backref(trans, path, &iref, bytenr,
1212					   num_bytes, parent, root_objectid,
1213					   owner, offset, 1);
1214	if (ret == 0) {
1215		/*
1216		 * We're adding refs to a tree block we already own, this
1217		 * should not happen at all.
1218		 */
1219		if (owner < BTRFS_FIRST_FREE_OBJECTID) {
1220			btrfs_print_leaf(path->nodes[0]);
1221			btrfs_crit(trans->fs_info,
1222"adding refs to an existing tree ref, bytenr %llu num_bytes %llu root_objectid %llu slot %u",
1223				   bytenr, num_bytes, root_objectid, path->slots[0]);
1224			return -EUCLEAN;
1225		}
1226		ret = update_inline_extent_backref(trans, path, iref,
1227						   refs_to_add, extent_op);
1228	} else if (ret == -ENOENT) {
1229		setup_inline_extent_backref(trans, path, iref, parent,
1230					    root_objectid, owner, offset,
1231					    refs_to_add, extent_op);
1232		ret = 0;
1233	}
1234	return ret;
1235}
1236
1237static int remove_extent_backref(struct btrfs_trans_handle *trans,
1238				 struct btrfs_root *root,
1239				 struct btrfs_path *path,
1240				 struct btrfs_extent_inline_ref *iref,
1241				 int refs_to_drop, int is_data)
1242{
1243	int ret = 0;
1244
1245	BUG_ON(!is_data && refs_to_drop != 1);
1246	if (iref)
1247		ret = update_inline_extent_backref(trans, path, iref,
1248						   -refs_to_drop, NULL);
1249	else if (is_data)
1250		ret = remove_extent_data_ref(trans, root, path, refs_to_drop);
1251	else
1252		ret = btrfs_del_item(trans, root, path);
1253	return ret;
1254}
1255
1256static int btrfs_issue_discard(struct block_device *bdev, u64 start, u64 len,
1257			       u64 *discarded_bytes)
1258{
1259	int j, ret = 0;
1260	u64 bytes_left, end;
1261	u64 aligned_start = ALIGN(start, 1 << SECTOR_SHIFT);
1262
1263	/* Adjust the range to be aligned to 512B sectors if necessary. */
1264	if (start != aligned_start) {
1265		len -= aligned_start - start;
1266		len = round_down(len, 1 << SECTOR_SHIFT);
1267		start = aligned_start;
1268	}
1269
1270	*discarded_bytes = 0;
1271
1272	if (!len)
1273		return 0;
1274
1275	end = start + len;
1276	bytes_left = len;
1277
1278	/* Skip any superblocks on this device. */
1279	for (j = 0; j < BTRFS_SUPER_MIRROR_MAX; j++) {
1280		u64 sb_start = btrfs_sb_offset(j);
1281		u64 sb_end = sb_start + BTRFS_SUPER_INFO_SIZE;
1282		u64 size = sb_start - start;
1283
1284		if (!in_range(sb_start, start, bytes_left) &&
1285		    !in_range(sb_end, start, bytes_left) &&
1286		    !in_range(start, sb_start, BTRFS_SUPER_INFO_SIZE))
1287			continue;
1288
1289		/*
1290		 * Superblock spans beginning of range.  Adjust start and
1291		 * try again.
1292		 */
1293		if (sb_start <= start) {
1294			start += sb_end - start;
1295			if (start > end) {
1296				bytes_left = 0;
1297				break;
1298			}
1299			bytes_left = end - start;
1300			continue;
1301		}
1302
1303		if (size) {
1304			ret = blkdev_issue_discard(bdev, start >> SECTOR_SHIFT,
1305						   size >> SECTOR_SHIFT,
1306						   GFP_NOFS);
1307			if (!ret)
1308				*discarded_bytes += size;
1309			else if (ret != -EOPNOTSUPP)
1310				return ret;
1311		}
1312
1313		start = sb_end;
1314		if (start > end) {
1315			bytes_left = 0;
1316			break;
1317		}
1318		bytes_left = end - start;
1319	}
1320
1321	if (bytes_left) {
1322		ret = blkdev_issue_discard(bdev, start >> SECTOR_SHIFT,
1323					   bytes_left >> SECTOR_SHIFT,
1324					   GFP_NOFS);
1325		if (!ret)
1326			*discarded_bytes += bytes_left;
1327	}
1328	return ret;
1329}
1330
1331static int do_discard_extent(struct btrfs_discard_stripe *stripe, u64 *bytes)
1332{
1333	struct btrfs_device *dev = stripe->dev;
1334	struct btrfs_fs_info *fs_info = dev->fs_info;
1335	struct btrfs_dev_replace *dev_replace = &fs_info->dev_replace;
1336	u64 phys = stripe->physical;
1337	u64 len = stripe->length;
1338	u64 discarded = 0;
1339	int ret = 0;
1340
1341	/* Zone reset on a zoned filesystem */
1342	if (btrfs_can_zone_reset(dev, phys, len)) {
1343		u64 src_disc;
1344
1345		ret = btrfs_reset_device_zone(dev, phys, len, &discarded);
1346		if (ret)
1347			goto out;
1348
1349		if (!btrfs_dev_replace_is_ongoing(dev_replace) ||
1350		    dev != dev_replace->srcdev)
1351			goto out;
1352
1353		src_disc = discarded;
1354
1355		/* Send to replace target as well */
1356		ret = btrfs_reset_device_zone(dev_replace->tgtdev, phys, len,
1357					      &discarded);
1358		discarded += src_disc;
1359	} else if (bdev_max_discard_sectors(stripe->dev->bdev)) {
1360		ret = btrfs_issue_discard(dev->bdev, phys, len, &discarded);
1361	} else {
1362		ret = 0;
1363		*bytes = 0;
1364	}
1365
1366out:
1367	*bytes = discarded;
1368	return ret;
1369}
1370
1371int btrfs_discard_extent(struct btrfs_fs_info *fs_info, u64 bytenr,
1372			 u64 num_bytes, u64 *actual_bytes)
1373{
1374	int ret = 0;
1375	u64 discarded_bytes = 0;
1376	u64 end = bytenr + num_bytes;
1377	u64 cur = bytenr;
1378
1379	/*
1380	 * Avoid races with device replace and make sure the devices in the
1381	 * stripes don't go away while we are discarding.
1382	 */
1383	btrfs_bio_counter_inc_blocked(fs_info);
1384	while (cur < end) {
1385		struct btrfs_discard_stripe *stripes;
1386		unsigned int num_stripes;
1387		int i;
1388
1389		num_bytes = end - cur;
1390		stripes = btrfs_map_discard(fs_info, cur, &num_bytes, &num_stripes);
1391		if (IS_ERR(stripes)) {
1392			ret = PTR_ERR(stripes);
1393			if (ret == -EOPNOTSUPP)
1394				ret = 0;
1395			break;
1396		}
1397
1398		for (i = 0; i < num_stripes; i++) {
1399			struct btrfs_discard_stripe *stripe = stripes + i;
1400			u64 bytes;
1401
1402			if (!stripe->dev->bdev) {
1403				ASSERT(btrfs_test_opt(fs_info, DEGRADED));
1404				continue;
1405			}
1406
1407			if (!test_bit(BTRFS_DEV_STATE_WRITEABLE,
1408					&stripe->dev->dev_state))
1409				continue;
1410
1411			ret = do_discard_extent(stripe, &bytes);
1412			if (ret) {
1413				/*
1414				 * Keep going if discard is not supported by the
1415				 * device.
1416				 */
1417				if (ret != -EOPNOTSUPP)
1418					break;
1419				ret = 0;
1420			} else {
1421				discarded_bytes += bytes;
1422			}
1423		}
1424		kfree(stripes);
1425		if (ret)
1426			break;
1427		cur += num_bytes;
1428	}
1429	btrfs_bio_counter_dec(fs_info);
1430	if (actual_bytes)
1431		*actual_bytes = discarded_bytes;
1432	return ret;
1433}
1434
1435/* Can return -ENOMEM */
1436int btrfs_inc_extent_ref(struct btrfs_trans_handle *trans,
1437			 struct btrfs_ref *generic_ref)
1438{
1439	struct btrfs_fs_info *fs_info = trans->fs_info;
1440	int ret;
1441
1442	ASSERT(generic_ref->type != BTRFS_REF_NOT_SET &&
1443	       generic_ref->action);
1444	BUG_ON(generic_ref->type == BTRFS_REF_METADATA &&
1445	       generic_ref->tree_ref.ref_root == BTRFS_TREE_LOG_OBJECTID);
1446
1447	if (generic_ref->type == BTRFS_REF_METADATA)
1448		ret = btrfs_add_delayed_tree_ref(trans, generic_ref, NULL);
1449	else
1450		ret = btrfs_add_delayed_data_ref(trans, generic_ref, 0);
1451
1452	btrfs_ref_tree_mod(fs_info, generic_ref);
1453
1454	return ret;
1455}
1456
1457/*
1458 * Insert backreference for a given extent.
1459 *
1460 * The counterpart is in __btrfs_free_extent(), with examples and more details
1461 * how it works.
1462 *
1463 * @trans:	    Handle of transaction
1464 *
1465 * @node:	    The delayed ref node used to get the bytenr/length for
1466 *		    extent whose references are incremented.
1467 *
1468 * @parent:	    If this is a shared extent (BTRFS_SHARED_DATA_REF_KEY/
1469 *		    BTRFS_SHARED_BLOCK_REF_KEY) then it holds the logical
1470 *		    bytenr of the parent block. Since new extents are always
1471 *		    created with indirect references, this will only be the case
1472 *		    when relocating a shared extent. In that case, root_objectid
1473 *		    will be BTRFS_TREE_RELOC_OBJECTID. Otherwise, parent must
1474 *		    be 0
1475 *
1476 * @root_objectid:  The id of the root where this modification has originated,
1477 *		    this can be either one of the well-known metadata trees or
1478 *		    the subvolume id which references this extent.
1479 *
1480 * @owner:	    For data extents it is the inode number of the owning file.
1481 *		    For metadata extents this parameter holds the level in the
1482 *		    tree of the extent.
1483 *
1484 * @offset:	    For metadata extents the offset is ignored and is currently
1485 *		    always passed as 0. For data extents it is the fileoffset
1486 *		    this extent belongs to.
1487 *
1488 * @extent_op       Pointer to a structure, holding information necessary when
1489 *                  updating a tree block's flags
1490 *
1491 */
1492static int __btrfs_inc_extent_ref(struct btrfs_trans_handle *trans,
1493				  struct btrfs_delayed_ref_node *node,
1494				  u64 parent, u64 root_objectid,
1495				  u64 owner, u64 offset,
1496				  struct btrfs_delayed_extent_op *extent_op)
1497{
1498	struct btrfs_path *path;
1499	struct extent_buffer *leaf;
1500	struct btrfs_extent_item *item;
1501	struct btrfs_key key;
1502	u64 bytenr = node->bytenr;
1503	u64 num_bytes = node->num_bytes;
1504	u64 refs;
1505	int refs_to_add = node->ref_mod;
1506	int ret;
1507
1508	path = btrfs_alloc_path();
1509	if (!path)
1510		return -ENOMEM;
1511
1512	/* this will setup the path even if it fails to insert the back ref */
1513	ret = insert_inline_extent_backref(trans, path, bytenr, num_bytes,
1514					   parent, root_objectid, owner,
1515					   offset, refs_to_add, extent_op);
1516	if ((ret < 0 && ret != -EAGAIN) || !ret)
1517		goto out;
1518
1519	/*
1520	 * Ok we had -EAGAIN which means we didn't have space to insert and
1521	 * inline extent ref, so just update the reference count and add a
1522	 * normal backref.
1523	 */
1524	leaf = path->nodes[0];
1525	btrfs_item_key_to_cpu(leaf, &key, path->slots[0]);
1526	item = btrfs_item_ptr(leaf, path->slots[0], struct btrfs_extent_item);
1527	refs = btrfs_extent_refs(leaf, item);
1528	btrfs_set_extent_refs(leaf, item, refs + refs_to_add);
1529	if (extent_op)
1530		__run_delayed_extent_op(extent_op, leaf, item);
1531
1532	btrfs_mark_buffer_dirty(trans, leaf);
1533	btrfs_release_path(path);
1534
1535	/* now insert the actual backref */
1536	if (owner < BTRFS_FIRST_FREE_OBJECTID)
1537		ret = insert_tree_block_ref(trans, path, bytenr, parent,
1538					    root_objectid);
1539	else
1540		ret = insert_extent_data_ref(trans, path, bytenr, parent,
1541					     root_objectid, owner, offset,
1542					     refs_to_add);
1543
1544	if (ret)
1545		btrfs_abort_transaction(trans, ret);
1546out:
1547	btrfs_free_path(path);
1548	return ret;
1549}
1550
1551static void free_head_ref_squota_rsv(struct btrfs_fs_info *fs_info,
1552				     struct btrfs_delayed_ref_head *href)
1553{
1554	u64 root = href->owning_root;
1555
1556	/*
1557	 * Don't check must_insert_reserved, as this is called from contexts
1558	 * where it has already been unset.
1559	 */
1560	if (btrfs_qgroup_mode(fs_info) != BTRFS_QGROUP_MODE_SIMPLE ||
1561	    !href->is_data || !is_fstree(root))
1562		return;
1563
1564	btrfs_qgroup_free_refroot(fs_info, root, href->reserved_bytes,
1565				  BTRFS_QGROUP_RSV_DATA);
1566}
1567
1568static int run_delayed_data_ref(struct btrfs_trans_handle *trans,
1569				struct btrfs_delayed_ref_head *href,
1570				struct btrfs_delayed_ref_node *node,
1571				struct btrfs_delayed_extent_op *extent_op,
1572				bool insert_reserved)
1573{
1574	int ret = 0;
1575	struct btrfs_delayed_data_ref *ref;
1576	u64 parent = 0;
1577	u64 flags = 0;
1578
1579	ref = btrfs_delayed_node_to_data_ref(node);
1580	trace_run_delayed_data_ref(trans->fs_info, node, ref, node->action);
1581
1582	if (node->type == BTRFS_SHARED_DATA_REF_KEY)
1583		parent = ref->parent;
1584
1585	if (node->action == BTRFS_ADD_DELAYED_REF && insert_reserved) {
1586		struct btrfs_key key;
1587		struct btrfs_squota_delta delta = {
1588			.root = href->owning_root,
1589			.num_bytes = node->num_bytes,
1590			.is_data = true,
1591			.is_inc	= true,
1592			.generation = trans->transid,
1593		};
1594
1595		if (extent_op)
1596			flags |= extent_op->flags_to_set;
1597
1598		key.objectid = node->bytenr;
1599		key.type = BTRFS_EXTENT_ITEM_KEY;
1600		key.offset = node->num_bytes;
1601
1602		ret = alloc_reserved_file_extent(trans, parent, ref->root,
1603						 flags, ref->objectid,
1604						 ref->offset, &key,
1605						 node->ref_mod, href->owning_root);
1606		free_head_ref_squota_rsv(trans->fs_info, href);
1607		if (!ret)
1608			ret = btrfs_record_squota_delta(trans->fs_info, &delta);
1609	} else if (node->action == BTRFS_ADD_DELAYED_REF) {
1610		ret = __btrfs_inc_extent_ref(trans, node, parent, ref->root,
1611					     ref->objectid, ref->offset,
1612					     extent_op);
1613	} else if (node->action == BTRFS_DROP_DELAYED_REF) {
1614		ret = __btrfs_free_extent(trans, href, node, parent,
1615					  ref->root, ref->objectid,
1616					  ref->offset, extent_op);
1617	} else {
1618		BUG();
1619	}
1620	return ret;
1621}
1622
1623static void __run_delayed_extent_op(struct btrfs_delayed_extent_op *extent_op,
1624				    struct extent_buffer *leaf,
1625				    struct btrfs_extent_item *ei)
1626{
1627	u64 flags = btrfs_extent_flags(leaf, ei);
1628	if (extent_op->update_flags) {
1629		flags |= extent_op->flags_to_set;
1630		btrfs_set_extent_flags(leaf, ei, flags);
1631	}
1632
1633	if (extent_op->update_key) {
1634		struct btrfs_tree_block_info *bi;
1635		BUG_ON(!(flags & BTRFS_EXTENT_FLAG_TREE_BLOCK));
1636		bi = (struct btrfs_tree_block_info *)(ei + 1);
1637		btrfs_set_tree_block_key(leaf, bi, &extent_op->key);
1638	}
1639}
1640
1641static int run_delayed_extent_op(struct btrfs_trans_handle *trans,
1642				 struct btrfs_delayed_ref_head *head,
1643				 struct btrfs_delayed_extent_op *extent_op)
1644{
1645	struct btrfs_fs_info *fs_info = trans->fs_info;
1646	struct btrfs_root *root;
1647	struct btrfs_key key;
1648	struct btrfs_path *path;
1649	struct btrfs_extent_item *ei;
1650	struct extent_buffer *leaf;
1651	u32 item_size;
1652	int ret;
1653	int metadata = 1;
1654
1655	if (TRANS_ABORTED(trans))
1656		return 0;
1657
1658	if (!btrfs_fs_incompat(fs_info, SKINNY_METADATA))
1659		metadata = 0;
1660
1661	path = btrfs_alloc_path();
1662	if (!path)
1663		return -ENOMEM;
1664
1665	key.objectid = head->bytenr;
1666
1667	if (metadata) {
1668		key.type = BTRFS_METADATA_ITEM_KEY;
1669		key.offset = extent_op->level;
1670	} else {
1671		key.type = BTRFS_EXTENT_ITEM_KEY;
1672		key.offset = head->num_bytes;
1673	}
1674
1675	root = btrfs_extent_root(fs_info, key.objectid);
1676again:
1677	ret = btrfs_search_slot(trans, root, &key, path, 0, 1);
1678	if (ret < 0) {
1679		goto out;
1680	} else if (ret > 0) {
1681		if (metadata) {
1682			if (path->slots[0] > 0) {
1683				path->slots[0]--;
1684				btrfs_item_key_to_cpu(path->nodes[0], &key,
1685						      path->slots[0]);
1686				if (key.objectid == head->bytenr &&
1687				    key.type == BTRFS_EXTENT_ITEM_KEY &&
1688				    key.offset == head->num_bytes)
1689					ret = 0;
1690			}
1691			if (ret > 0) {
1692				btrfs_release_path(path);
1693				metadata = 0;
1694
1695				key.objectid = head->bytenr;
1696				key.offset = head->num_bytes;
1697				key.type = BTRFS_EXTENT_ITEM_KEY;
1698				goto again;
1699			}
1700		} else {
1701			ret = -EUCLEAN;
1702			btrfs_err(fs_info,
1703		  "missing extent item for extent %llu num_bytes %llu level %d",
1704				  head->bytenr, head->num_bytes, extent_op->level);
1705			goto out;
1706		}
1707	}
1708
1709	leaf = path->nodes[0];
1710	item_size = btrfs_item_size(leaf, path->slots[0]);
1711
1712	if (unlikely(item_size < sizeof(*ei))) {
1713		ret = -EUCLEAN;
1714		btrfs_err(fs_info,
1715			  "unexpected extent item size, has %u expect >= %zu",
1716			  item_size, sizeof(*ei));
1717		btrfs_abort_transaction(trans, ret);
1718		goto out;
1719	}
1720
1721	ei = btrfs_item_ptr(leaf, path->slots[0], struct btrfs_extent_item);
1722	__run_delayed_extent_op(extent_op, leaf, ei);
1723
1724	btrfs_mark_buffer_dirty(trans, leaf);
1725out:
1726	btrfs_free_path(path);
1727	return ret;
1728}
1729
1730static int run_delayed_tree_ref(struct btrfs_trans_handle *trans,
1731				struct btrfs_delayed_ref_head *href,
1732				struct btrfs_delayed_ref_node *node,
1733				struct btrfs_delayed_extent_op *extent_op,
1734				bool insert_reserved)
1735{
1736	int ret = 0;
1737	struct btrfs_fs_info *fs_info = trans->fs_info;
1738	struct btrfs_delayed_tree_ref *ref;
1739	u64 parent = 0;
1740	u64 ref_root = 0;
1741
1742	ref = btrfs_delayed_node_to_tree_ref(node);
1743	trace_run_delayed_tree_ref(trans->fs_info, node, ref, node->action);
1744
1745	if (node->type == BTRFS_SHARED_BLOCK_REF_KEY)
1746		parent = ref->parent;
1747	ref_root = ref->root;
1748
1749	if (unlikely(node->ref_mod != 1)) {
1750		btrfs_err(trans->fs_info,
1751	"btree block %llu has %d references rather than 1: action %d ref_root %llu parent %llu",
1752			  node->bytenr, node->ref_mod, node->action, ref_root,
1753			  parent);
1754		return -EUCLEAN;
1755	}
1756	if (node->action == BTRFS_ADD_DELAYED_REF && insert_reserved) {
1757		struct btrfs_squota_delta delta = {
1758			.root = href->owning_root,
1759			.num_bytes = fs_info->nodesize,
1760			.is_data = false,
1761			.is_inc = true,
1762			.generation = trans->transid,
1763		};
1764
1765		BUG_ON(!extent_op || !extent_op->update_flags);
1766		ret = alloc_reserved_tree_block(trans, node, extent_op);
1767		if (!ret)
1768			btrfs_record_squota_delta(fs_info, &delta);
1769	} else if (node->action == BTRFS_ADD_DELAYED_REF) {
1770		ret = __btrfs_inc_extent_ref(trans, node, parent, ref_root,
1771					     ref->level, 0, extent_op);
1772	} else if (node->action == BTRFS_DROP_DELAYED_REF) {
1773		ret = __btrfs_free_extent(trans, href, node, parent, ref_root,
1774					  ref->level, 0, extent_op);
1775	} else {
1776		BUG();
1777	}
1778	return ret;
1779}
1780
1781/* helper function to actually process a single delayed ref entry */
1782static int run_one_delayed_ref(struct btrfs_trans_handle *trans,
1783			       struct btrfs_delayed_ref_head *href,
1784			       struct btrfs_delayed_ref_node *node,
1785			       struct btrfs_delayed_extent_op *extent_op,
1786			       bool insert_reserved)
1787{
1788	int ret = 0;
1789
1790	if (TRANS_ABORTED(trans)) {
1791		if (insert_reserved) {
1792			btrfs_pin_extent(trans, node->bytenr, node->num_bytes, 1);
1793			free_head_ref_squota_rsv(trans->fs_info, href);
1794		}
1795		return 0;
1796	}
1797
1798	if (node->type == BTRFS_TREE_BLOCK_REF_KEY ||
1799	    node->type == BTRFS_SHARED_BLOCK_REF_KEY)
1800		ret = run_delayed_tree_ref(trans, href, node, extent_op,
1801					   insert_reserved);
1802	else if (node->type == BTRFS_EXTENT_DATA_REF_KEY ||
1803		 node->type == BTRFS_SHARED_DATA_REF_KEY)
1804		ret = run_delayed_data_ref(trans, href, node, extent_op,
1805					   insert_reserved);
1806	else if (node->type == BTRFS_EXTENT_OWNER_REF_KEY)
1807		ret = 0;
1808	else
1809		BUG();
1810	if (ret && insert_reserved)
1811		btrfs_pin_extent(trans, node->bytenr, node->num_bytes, 1);
1812	if (ret < 0)
1813		btrfs_err(trans->fs_info,
1814"failed to run delayed ref for logical %llu num_bytes %llu type %u action %u ref_mod %d: %d",
1815			  node->bytenr, node->num_bytes, node->type,
1816			  node->action, node->ref_mod, ret);
1817	return ret;
1818}
1819
1820static inline struct btrfs_delayed_ref_node *
1821select_delayed_ref(struct btrfs_delayed_ref_head *head)
1822{
1823	struct btrfs_delayed_ref_node *ref;
1824
1825	if (RB_EMPTY_ROOT(&head->ref_tree.rb_root))
1826		return NULL;
1827
1828	/*
1829	 * Select a delayed ref of type BTRFS_ADD_DELAYED_REF first.
1830	 * This is to prevent a ref count from going down to zero, which deletes
1831	 * the extent item from the extent tree, when there still are references
1832	 * to add, which would fail because they would not find the extent item.
1833	 */
1834	if (!list_empty(&head->ref_add_list))
1835		return list_first_entry(&head->ref_add_list,
1836				struct btrfs_delayed_ref_node, add_list);
1837
1838	ref = rb_entry(rb_first_cached(&head->ref_tree),
1839		       struct btrfs_delayed_ref_node, ref_node);
1840	ASSERT(list_empty(&ref->add_list));
1841	return ref;
1842}
1843
1844static void unselect_delayed_ref_head(struct btrfs_delayed_ref_root *delayed_refs,
1845				      struct btrfs_delayed_ref_head *head)
1846{
1847	spin_lock(&delayed_refs->lock);
1848	head->processing = false;
1849	delayed_refs->num_heads_ready++;
1850	spin_unlock(&delayed_refs->lock);
1851	btrfs_delayed_ref_unlock(head);
1852}
1853
1854static struct btrfs_delayed_extent_op *cleanup_extent_op(
1855				struct btrfs_delayed_ref_head *head)
1856{
1857	struct btrfs_delayed_extent_op *extent_op = head->extent_op;
1858
1859	if (!extent_op)
1860		return NULL;
1861
1862	if (head->must_insert_reserved) {
1863		head->extent_op = NULL;
1864		btrfs_free_delayed_extent_op(extent_op);
1865		return NULL;
1866	}
1867	return extent_op;
1868}
1869
1870static int run_and_cleanup_extent_op(struct btrfs_trans_handle *trans,
1871				     struct btrfs_delayed_ref_head *head)
1872{
1873	struct btrfs_delayed_extent_op *extent_op;
1874	int ret;
1875
1876	extent_op = cleanup_extent_op(head);
1877	if (!extent_op)
1878		return 0;
1879	head->extent_op = NULL;
1880	spin_unlock(&head->lock);
1881	ret = run_delayed_extent_op(trans, head, extent_op);
1882	btrfs_free_delayed_extent_op(extent_op);
1883	return ret ? ret : 1;
1884}
1885
1886u64 btrfs_cleanup_ref_head_accounting(struct btrfs_fs_info *fs_info,
1887				  struct btrfs_delayed_ref_root *delayed_refs,
1888				  struct btrfs_delayed_ref_head *head)
1889{
1890	u64 ret = 0;
1891
1892	/*
1893	 * We had csum deletions accounted for in our delayed refs rsv, we need
1894	 * to drop the csum leaves for this update from our delayed_refs_rsv.
1895	 */
1896	if (head->total_ref_mod < 0 && head->is_data) {
1897		int nr_csums;
1898
1899		spin_lock(&delayed_refs->lock);
1900		delayed_refs->pending_csums -= head->num_bytes;
1901		spin_unlock(&delayed_refs->lock);
1902		nr_csums = btrfs_csum_bytes_to_leaves(fs_info, head->num_bytes);
1903
1904		btrfs_delayed_refs_rsv_release(fs_info, 0, nr_csums);
1905
1906		ret = btrfs_calc_delayed_ref_csum_bytes(fs_info, nr_csums);
1907	}
1908	/* must_insert_reserved can be set only if we didn't run the head ref. */
1909	if (head->must_insert_reserved)
1910		free_head_ref_squota_rsv(fs_info, head);
1911
1912	return ret;
1913}
1914
1915static int cleanup_ref_head(struct btrfs_trans_handle *trans,
1916			    struct btrfs_delayed_ref_head *head,
1917			    u64 *bytes_released)
1918{
1919
1920	struct btrfs_fs_info *fs_info = trans->fs_info;
1921	struct btrfs_delayed_ref_root *delayed_refs;
1922	int ret;
1923
1924	delayed_refs = &trans->transaction->delayed_refs;
1925
1926	ret = run_and_cleanup_extent_op(trans, head);
1927	if (ret < 0) {
1928		unselect_delayed_ref_head(delayed_refs, head);
1929		btrfs_debug(fs_info, "run_delayed_extent_op returned %d", ret);
1930		return ret;
1931	} else if (ret) {
1932		return ret;
1933	}
1934
1935	/*
1936	 * Need to drop our head ref lock and re-acquire the delayed ref lock
1937	 * and then re-check to make sure nobody got added.
1938	 */
1939	spin_unlock(&head->lock);
1940	spin_lock(&delayed_refs->lock);
1941	spin_lock(&head->lock);
1942	if (!RB_EMPTY_ROOT(&head->ref_tree.rb_root) || head->extent_op) {
1943		spin_unlock(&head->lock);
1944		spin_unlock(&delayed_refs->lock);
1945		return 1;
1946	}
1947	btrfs_delete_ref_head(delayed_refs, head);
1948	spin_unlock(&head->lock);
1949	spin_unlock(&delayed_refs->lock);
1950
1951	if (head->must_insert_reserved) {
1952		btrfs_pin_extent(trans, head->bytenr, head->num_bytes, 1);
1953		if (head->is_data) {
1954			struct btrfs_root *csum_root;
1955
1956			csum_root = btrfs_csum_root(fs_info, head->bytenr);
1957			ret = btrfs_del_csums(trans, csum_root, head->bytenr,
1958					      head->num_bytes);
1959		}
1960	}
1961
1962	*bytes_released += btrfs_cleanup_ref_head_accounting(fs_info, delayed_refs, head);
1963
1964	trace_run_delayed_ref_head(fs_info, head, 0);
1965	btrfs_delayed_ref_unlock(head);
1966	btrfs_put_delayed_ref_head(head);
1967	return ret;
1968}
1969
1970static struct btrfs_delayed_ref_head *btrfs_obtain_ref_head(
1971					struct btrfs_trans_handle *trans)
1972{
1973	struct btrfs_delayed_ref_root *delayed_refs =
1974		&trans->transaction->delayed_refs;
1975	struct btrfs_delayed_ref_head *head = NULL;
1976	int ret;
1977
1978	spin_lock(&delayed_refs->lock);
1979	head = btrfs_select_ref_head(delayed_refs);
1980	if (!head) {
1981		spin_unlock(&delayed_refs->lock);
1982		return head;
1983	}
1984
1985	/*
1986	 * Grab the lock that says we are going to process all the refs for
1987	 * this head
1988	 */
1989	ret = btrfs_delayed_ref_lock(delayed_refs, head);
1990	spin_unlock(&delayed_refs->lock);
1991
1992	/*
1993	 * We may have dropped the spin lock to get the head mutex lock, and
1994	 * that might have given someone else time to free the head.  If that's
1995	 * true, it has been removed from our list and we can move on.
1996	 */
1997	if (ret == -EAGAIN)
1998		head = ERR_PTR(-EAGAIN);
1999
2000	return head;
2001}
2002
2003static int btrfs_run_delayed_refs_for_head(struct btrfs_trans_handle *trans,
2004					   struct btrfs_delayed_ref_head *locked_ref,
2005					   u64 *bytes_released)
2006{
2007	struct btrfs_fs_info *fs_info = trans->fs_info;
2008	struct btrfs_delayed_ref_root *delayed_refs;
2009	struct btrfs_delayed_extent_op *extent_op;
2010	struct btrfs_delayed_ref_node *ref;
2011	bool must_insert_reserved;
2012	int ret;
2013
2014	delayed_refs = &trans->transaction->delayed_refs;
2015
2016	lockdep_assert_held(&locked_ref->mutex);
2017	lockdep_assert_held(&locked_ref->lock);
2018
2019	while ((ref = select_delayed_ref(locked_ref))) {
2020		if (ref->seq &&
2021		    btrfs_check_delayed_seq(fs_info, ref->seq)) {
2022			spin_unlock(&locked_ref->lock);
2023			unselect_delayed_ref_head(delayed_refs, locked_ref);
2024			return -EAGAIN;
2025		}
2026
2027		rb_erase_cached(&ref->ref_node, &locked_ref->ref_tree);
2028		RB_CLEAR_NODE(&ref->ref_node);
2029		if (!list_empty(&ref->add_list))
2030			list_del(&ref->add_list);
2031		/*
2032		 * When we play the delayed ref, also correct the ref_mod on
2033		 * head
2034		 */
2035		switch (ref->action) {
2036		case BTRFS_ADD_DELAYED_REF:
2037		case BTRFS_ADD_DELAYED_EXTENT:
2038			locked_ref->ref_mod -= ref->ref_mod;
2039			break;
2040		case BTRFS_DROP_DELAYED_REF:
2041			locked_ref->ref_mod += ref->ref_mod;
2042			break;
2043		default:
2044			WARN_ON(1);
2045		}
2046		atomic_dec(&delayed_refs->num_entries);
2047
2048		/*
2049		 * Record the must_insert_reserved flag before we drop the
2050		 * spin lock.
2051		 */
2052		must_insert_reserved = locked_ref->must_insert_reserved;
2053		/*
2054		 * Unsetting this on the head ref relinquishes ownership of
2055		 * the rsv_bytes, so it is critical that every possible code
2056		 * path from here forward frees all reserves including qgroup
2057		 * reserve.
2058		 */
2059		locked_ref->must_insert_reserved = false;
2060
2061		extent_op = locked_ref->extent_op;
2062		locked_ref->extent_op = NULL;
2063		spin_unlock(&locked_ref->lock);
2064
2065		ret = run_one_delayed_ref(trans, locked_ref, ref, extent_op,
2066					  must_insert_reserved);
2067		btrfs_delayed_refs_rsv_release(fs_info, 1, 0);
2068		*bytes_released += btrfs_calc_delayed_ref_bytes(fs_info, 1);
2069
2070		btrfs_free_delayed_extent_op(extent_op);
2071		if (ret) {
2072			unselect_delayed_ref_head(delayed_refs, locked_ref);
2073			btrfs_put_delayed_ref(ref);
2074			return ret;
2075		}
2076
2077		btrfs_put_delayed_ref(ref);
2078		cond_resched();
2079
2080		spin_lock(&locked_ref->lock);
2081		btrfs_merge_delayed_refs(fs_info, delayed_refs, locked_ref);
2082	}
2083
2084	return 0;
2085}
2086
2087/*
2088 * Returns 0 on success or if called with an already aborted transaction.
2089 * Returns -ENOMEM or -EIO on failure and will abort the transaction.
2090 */
2091static noinline int __btrfs_run_delayed_refs(struct btrfs_trans_handle *trans,
2092					     u64 min_bytes)
2093{
2094	struct btrfs_fs_info *fs_info = trans->fs_info;
2095	struct btrfs_delayed_ref_root *delayed_refs;
2096	struct btrfs_delayed_ref_head *locked_ref = NULL;
2097	int ret;
2098	unsigned long count = 0;
2099	unsigned long max_count = 0;
2100	u64 bytes_processed = 0;
2101
2102	delayed_refs = &trans->transaction->delayed_refs;
2103	if (min_bytes == 0) {
2104		max_count = delayed_refs->num_heads_ready;
2105		min_bytes = U64_MAX;
2106	}
2107
2108	do {
2109		if (!locked_ref) {
2110			locked_ref = btrfs_obtain_ref_head(trans);
2111			if (IS_ERR_OR_NULL(locked_ref)) {
2112				if (PTR_ERR(locked_ref) == -EAGAIN) {
2113					continue;
2114				} else {
2115					break;
2116				}
2117			}
2118			count++;
2119		}
2120		/*
2121		 * We need to try and merge add/drops of the same ref since we
2122		 * can run into issues with relocate dropping the implicit ref
2123		 * and then it being added back again before the drop can
2124		 * finish.  If we merged anything we need to re-loop so we can
2125		 * get a good ref.
2126		 * Or we can get node references of the same type that weren't
2127		 * merged when created due to bumps in the tree mod seq, and
2128		 * we need to merge them to prevent adding an inline extent
2129		 * backref before dropping it (triggering a BUG_ON at
2130		 * insert_inline_extent_backref()).
2131		 */
2132		spin_lock(&locked_ref->lock);
2133		btrfs_merge_delayed_refs(fs_info, delayed_refs, locked_ref);
2134
2135		ret = btrfs_run_delayed_refs_for_head(trans, locked_ref, &bytes_processed);
2136		if (ret < 0 && ret != -EAGAIN) {
2137			/*
2138			 * Error, btrfs_run_delayed_refs_for_head already
2139			 * unlocked everything so just bail out
2140			 */
2141			return ret;
2142		} else if (!ret) {
2143			/*
2144			 * Success, perform the usual cleanup of a processed
2145			 * head
2146			 */
2147			ret = cleanup_ref_head(trans, locked_ref, &bytes_processed);
2148			if (ret > 0 ) {
2149				/* We dropped our lock, we need to loop. */
2150				ret = 0;
2151				continue;
2152			} else if (ret) {
2153				return ret;
2154			}
2155		}
2156
2157		/*
2158		 * Either success case or btrfs_run_delayed_refs_for_head
2159		 * returned -EAGAIN, meaning we need to select another head
2160		 */
2161
2162		locked_ref = NULL;
2163		cond_resched();
2164	} while ((min_bytes != U64_MAX && bytes_processed < min_bytes) ||
2165		 (max_count > 0 && count < max_count) ||
2166		 locked_ref);
2167
2168	return 0;
2169}
2170
2171#ifdef SCRAMBLE_DELAYED_REFS
2172/*
2173 * Normally delayed refs get processed in ascending bytenr order. This
2174 * correlates in most cases to the order added. To expose dependencies on this
2175 * order, we start to process the tree in the middle instead of the beginning
2176 */
2177static u64 find_middle(struct rb_root *root)
2178{
2179	struct rb_node *n = root->rb_node;
2180	struct btrfs_delayed_ref_node *entry;
2181	int alt = 1;
2182	u64 middle;
2183	u64 first = 0, last = 0;
2184
2185	n = rb_first(root);
2186	if (n) {
2187		entry = rb_entry(n, struct btrfs_delayed_ref_node, rb_node);
2188		first = entry->bytenr;
2189	}
2190	n = rb_last(root);
2191	if (n) {
2192		entry = rb_entry(n, struct btrfs_delayed_ref_node, rb_node);
2193		last = entry->bytenr;
2194	}
2195	n = root->rb_node;
2196
2197	while (n) {
2198		entry = rb_entry(n, struct btrfs_delayed_ref_node, rb_node);
2199		WARN_ON(!entry->in_tree);
2200
2201		middle = entry->bytenr;
2202
2203		if (alt)
2204			n = n->rb_left;
2205		else
2206			n = n->rb_right;
2207
2208		alt = 1 - alt;
2209	}
2210	return middle;
2211}
2212#endif
2213
2214/*
2215 * Start processing the delayed reference count updates and extent insertions
2216 * we have queued up so far.
2217 *
2218 * @trans:	Transaction handle.
2219 * @min_bytes:	How many bytes of delayed references to process. After this
2220 *		many bytes we stop processing delayed references if there are
2221 *		any more. If 0 it means to run all existing delayed references,
2222 *		but not new ones added after running all existing ones.
2223 *		Use (u64)-1 (U64_MAX) to run all existing delayed references
2224 *		plus any new ones that are added.
2225 *
2226 * Returns 0 on success or if called with an aborted transaction
2227 * Returns <0 on error and aborts the transaction
2228 */
2229int btrfs_run_delayed_refs(struct btrfs_trans_handle *trans, u64 min_bytes)
2230{
2231	struct btrfs_fs_info *fs_info = trans->fs_info;
2232	struct btrfs_delayed_ref_root *delayed_refs;
2233	int ret;
2234
2235	/* We'll clean this up in btrfs_cleanup_transaction */
2236	if (TRANS_ABORTED(trans))
2237		return 0;
2238
2239	if (test_bit(BTRFS_FS_CREATING_FREE_SPACE_TREE, &fs_info->flags))
2240		return 0;
2241
2242	delayed_refs = &trans->transaction->delayed_refs;
2243again:
2244#ifdef SCRAMBLE_DELAYED_REFS
2245	delayed_refs->run_delayed_start = find_middle(&delayed_refs->root);
2246#endif
2247	ret = __btrfs_run_delayed_refs(trans, min_bytes);
2248	if (ret < 0) {
2249		btrfs_abort_transaction(trans, ret);
2250		return ret;
2251	}
2252
2253	if (min_bytes == U64_MAX) {
2254		btrfs_create_pending_block_groups(trans);
2255
2256		spin_lock(&delayed_refs->lock);
2257		if (RB_EMPTY_ROOT(&delayed_refs->href_root.rb_root)) {
2258			spin_unlock(&delayed_refs->lock);
2259			return 0;
2260		}
2261		spin_unlock(&delayed_refs->lock);
2262
2263		cond_resched();
2264		goto again;
2265	}
2266
2267	return 0;
2268}
2269
2270int btrfs_set_disk_extent_flags(struct btrfs_trans_handle *trans,
2271				struct extent_buffer *eb, u64 flags)
2272{
2273	struct btrfs_delayed_extent_op *extent_op;
2274	int level = btrfs_header_level(eb);
2275	int ret;
2276
2277	extent_op = btrfs_alloc_delayed_extent_op();
2278	if (!extent_op)
2279		return -ENOMEM;
2280
2281	extent_op->flags_to_set = flags;
2282	extent_op->update_flags = true;
2283	extent_op->update_key = false;
2284	extent_op->level = level;
2285
2286	ret = btrfs_add_delayed_extent_op(trans, eb->start, eb->len, extent_op);
2287	if (ret)
2288		btrfs_free_delayed_extent_op(extent_op);
2289	return ret;
2290}
2291
2292static noinline int check_delayed_ref(struct btrfs_root *root,
2293				      struct btrfs_path *path,
2294				      u64 objectid, u64 offset, u64 bytenr)
2295{
2296	struct btrfs_delayed_ref_head *head;
2297	struct btrfs_delayed_ref_node *ref;
2298	struct btrfs_delayed_data_ref *data_ref;
2299	struct btrfs_delayed_ref_root *delayed_refs;
2300	struct btrfs_transaction *cur_trans;
2301	struct rb_node *node;
2302	int ret = 0;
2303
2304	spin_lock(&root->fs_info->trans_lock);
2305	cur_trans = root->fs_info->running_transaction;
2306	if (cur_trans)
2307		refcount_inc(&cur_trans->use_count);
2308	spin_unlock(&root->fs_info->trans_lock);
2309	if (!cur_trans)
2310		return 0;
2311
2312	delayed_refs = &cur_trans->delayed_refs;
2313	spin_lock(&delayed_refs->lock);
2314	head = btrfs_find_delayed_ref_head(delayed_refs, bytenr);
2315	if (!head) {
2316		spin_unlock(&delayed_refs->lock);
2317		btrfs_put_transaction(cur_trans);
2318		return 0;
2319	}
2320
2321	if (!mutex_trylock(&head->mutex)) {
2322		if (path->nowait) {
2323			spin_unlock(&delayed_refs->lock);
2324			btrfs_put_transaction(cur_trans);
2325			return -EAGAIN;
2326		}
2327
2328		refcount_inc(&head->refs);
2329		spin_unlock(&delayed_refs->lock);
2330
2331		btrfs_release_path(path);
2332
2333		/*
2334		 * Mutex was contended, block until it's released and let
2335		 * caller try again
2336		 */
2337		mutex_lock(&head->mutex);
2338		mutex_unlock(&head->mutex);
2339		btrfs_put_delayed_ref_head(head);
2340		btrfs_put_transaction(cur_trans);
2341		return -EAGAIN;
2342	}
2343	spin_unlock(&delayed_refs->lock);
2344
2345	spin_lock(&head->lock);
2346	/*
2347	 * XXX: We should replace this with a proper search function in the
2348	 * future.
2349	 */
2350	for (node = rb_first_cached(&head->ref_tree); node;
2351	     node = rb_next(node)) {
2352		ref = rb_entry(node, struct btrfs_delayed_ref_node, ref_node);
2353		/* If it's a shared ref we know a cross reference exists */
2354		if (ref->type != BTRFS_EXTENT_DATA_REF_KEY) {
2355			ret = 1;
2356			break;
2357		}
2358
2359		data_ref = btrfs_delayed_node_to_data_ref(ref);
2360
2361		/*
2362		 * If our ref doesn't match the one we're currently looking at
2363		 * then we have a cross reference.
2364		 */
2365		if (data_ref->root != root->root_key.objectid ||
2366		    data_ref->objectid != objectid ||
2367		    data_ref->offset != offset) {
2368			ret = 1;
2369			break;
2370		}
2371	}
2372	spin_unlock(&head->lock);
2373	mutex_unlock(&head->mutex);
2374	btrfs_put_transaction(cur_trans);
2375	return ret;
2376}
2377
2378static noinline int check_committed_ref(struct btrfs_root *root,
2379					struct btrfs_path *path,
2380					u64 objectid, u64 offset, u64 bytenr,
2381					bool strict)
2382{
2383	struct btrfs_fs_info *fs_info = root->fs_info;
2384	struct btrfs_root *extent_root = btrfs_extent_root(fs_info, bytenr);
2385	struct extent_buffer *leaf;
2386	struct btrfs_extent_data_ref *ref;
2387	struct btrfs_extent_inline_ref *iref;
2388	struct btrfs_extent_item *ei;
2389	struct btrfs_key key;
2390	u32 item_size;
2391	u32 expected_size;
2392	int type;
2393	int ret;
2394
2395	key.objectid = bytenr;
2396	key.offset = (u64)-1;
2397	key.type = BTRFS_EXTENT_ITEM_KEY;
2398
2399	ret = btrfs_search_slot(NULL, extent_root, &key, path, 0, 0);
2400	if (ret < 0)
2401		goto out;
2402	BUG_ON(ret == 0); /* Corruption */
 
 
 
 
 
 
 
2403
2404	ret = -ENOENT;
2405	if (path->slots[0] == 0)
2406		goto out;
2407
2408	path->slots[0]--;
2409	leaf = path->nodes[0];
2410	btrfs_item_key_to_cpu(leaf, &key, path->slots[0]);
2411
2412	if (key.objectid != bytenr || key.type != BTRFS_EXTENT_ITEM_KEY)
2413		goto out;
2414
2415	ret = 1;
2416	item_size = btrfs_item_size(leaf, path->slots[0]);
2417	ei = btrfs_item_ptr(leaf, path->slots[0], struct btrfs_extent_item);
2418	expected_size = sizeof(*ei) + btrfs_extent_inline_ref_size(BTRFS_EXTENT_DATA_REF_KEY);
2419
2420	/* No inline refs; we need to bail before checking for owner ref. */
2421	if (item_size == sizeof(*ei))
2422		goto out;
2423
2424	/* Check for an owner ref; skip over it to the real inline refs. */
2425	iref = (struct btrfs_extent_inline_ref *)(ei + 1);
2426	type = btrfs_get_extent_inline_ref_type(leaf, iref, BTRFS_REF_TYPE_DATA);
2427	if (btrfs_fs_incompat(fs_info, SIMPLE_QUOTA) && type == BTRFS_EXTENT_OWNER_REF_KEY) {
2428		expected_size += btrfs_extent_inline_ref_size(BTRFS_EXTENT_OWNER_REF_KEY);
2429		iref = (struct btrfs_extent_inline_ref *)(iref + 1);
2430	}
2431
2432	/* If extent item has more than 1 inline ref then it's shared */
2433	if (item_size != expected_size)
2434		goto out;
2435
2436	/*
2437	 * If extent created before last snapshot => it's shared unless the
2438	 * snapshot has been deleted. Use the heuristic if strict is false.
2439	 */
2440	if (!strict &&
2441	    (btrfs_extent_generation(leaf, ei) <=
2442	     btrfs_root_last_snapshot(&root->root_item)))
2443		goto out;
2444
2445	/* If this extent has SHARED_DATA_REF then it's shared */
2446	type = btrfs_get_extent_inline_ref_type(leaf, iref, BTRFS_REF_TYPE_DATA);
2447	if (type != BTRFS_EXTENT_DATA_REF_KEY)
2448		goto out;
2449
2450	ref = (struct btrfs_extent_data_ref *)(&iref->offset);
2451	if (btrfs_extent_refs(leaf, ei) !=
2452	    btrfs_extent_data_ref_count(leaf, ref) ||
2453	    btrfs_extent_data_ref_root(leaf, ref) !=
2454	    root->root_key.objectid ||
2455	    btrfs_extent_data_ref_objectid(leaf, ref) != objectid ||
2456	    btrfs_extent_data_ref_offset(leaf, ref) != offset)
2457		goto out;
2458
2459	ret = 0;
2460out:
2461	return ret;
2462}
2463
2464int btrfs_cross_ref_exist(struct btrfs_root *root, u64 objectid, u64 offset,
2465			  u64 bytenr, bool strict, struct btrfs_path *path)
2466{
2467	int ret;
2468
2469	do {
2470		ret = check_committed_ref(root, path, objectid,
2471					  offset, bytenr, strict);
2472		if (ret && ret != -ENOENT)
2473			goto out;
2474
2475		ret = check_delayed_ref(root, path, objectid, offset, bytenr);
2476	} while (ret == -EAGAIN);
2477
2478out:
2479	btrfs_release_path(path);
2480	if (btrfs_is_data_reloc_root(root))
2481		WARN_ON(ret > 0);
2482	return ret;
2483}
2484
2485static int __btrfs_mod_ref(struct btrfs_trans_handle *trans,
2486			   struct btrfs_root *root,
2487			   struct extent_buffer *buf,
2488			   int full_backref, int inc)
2489{
2490	struct btrfs_fs_info *fs_info = root->fs_info;
2491	u64 bytenr;
2492	u64 num_bytes;
2493	u64 parent;
2494	u64 ref_root;
2495	u32 nritems;
2496	struct btrfs_key key;
2497	struct btrfs_file_extent_item *fi;
2498	struct btrfs_ref generic_ref = { 0 };
2499	bool for_reloc = btrfs_header_flag(buf, BTRFS_HEADER_FLAG_RELOC);
2500	int i;
2501	int action;
2502	int level;
2503	int ret = 0;
2504
2505	if (btrfs_is_testing(fs_info))
2506		return 0;
2507
2508	ref_root = btrfs_header_owner(buf);
2509	nritems = btrfs_header_nritems(buf);
2510	level = btrfs_header_level(buf);
2511
2512	if (!test_bit(BTRFS_ROOT_SHAREABLE, &root->state) && level == 0)
2513		return 0;
2514
2515	if (full_backref)
2516		parent = buf->start;
2517	else
2518		parent = 0;
2519	if (inc)
2520		action = BTRFS_ADD_DELAYED_REF;
2521	else
2522		action = BTRFS_DROP_DELAYED_REF;
2523
2524	for (i = 0; i < nritems; i++) {
2525		if (level == 0) {
2526			btrfs_item_key_to_cpu(buf, &key, i);
2527			if (key.type != BTRFS_EXTENT_DATA_KEY)
2528				continue;
2529			fi = btrfs_item_ptr(buf, i,
2530					    struct btrfs_file_extent_item);
2531			if (btrfs_file_extent_type(buf, fi) ==
2532			    BTRFS_FILE_EXTENT_INLINE)
2533				continue;
2534			bytenr = btrfs_file_extent_disk_bytenr(buf, fi);
2535			if (bytenr == 0)
2536				continue;
2537
2538			num_bytes = btrfs_file_extent_disk_num_bytes(buf, fi);
2539			key.offset -= btrfs_file_extent_offset(buf, fi);
2540			btrfs_init_generic_ref(&generic_ref, action, bytenr,
2541					       num_bytes, parent, ref_root);
2542			btrfs_init_data_ref(&generic_ref, ref_root, key.objectid,
2543					    key.offset, root->root_key.objectid,
2544					    for_reloc);
2545			if (inc)
2546				ret = btrfs_inc_extent_ref(trans, &generic_ref);
2547			else
2548				ret = btrfs_free_extent(trans, &generic_ref);
2549			if (ret)
2550				goto fail;
2551		} else {
2552			bytenr = btrfs_node_blockptr(buf, i);
2553			num_bytes = fs_info->nodesize;
2554			/* We don't know the owning_root, use 0. */
2555			btrfs_init_generic_ref(&generic_ref, action, bytenr,
2556					       num_bytes, parent, 0);
2557			btrfs_init_tree_ref(&generic_ref, level - 1, ref_root,
2558					    root->root_key.objectid, for_reloc);
2559			if (inc)
2560				ret = btrfs_inc_extent_ref(trans, &generic_ref);
2561			else
2562				ret = btrfs_free_extent(trans, &generic_ref);
2563			if (ret)
2564				goto fail;
2565		}
2566	}
2567	return 0;
2568fail:
2569	return ret;
2570}
2571
2572int btrfs_inc_ref(struct btrfs_trans_handle *trans, struct btrfs_root *root,
2573		  struct extent_buffer *buf, int full_backref)
2574{
2575	return __btrfs_mod_ref(trans, root, buf, full_backref, 1);
2576}
2577
2578int btrfs_dec_ref(struct btrfs_trans_handle *trans, struct btrfs_root *root,
2579		  struct extent_buffer *buf, int full_backref)
2580{
2581	return __btrfs_mod_ref(trans, root, buf, full_backref, 0);
2582}
2583
2584static u64 get_alloc_profile_by_root(struct btrfs_root *root, int data)
2585{
2586	struct btrfs_fs_info *fs_info = root->fs_info;
2587	u64 flags;
2588	u64 ret;
2589
2590	if (data)
2591		flags = BTRFS_BLOCK_GROUP_DATA;
2592	else if (root == fs_info->chunk_root)
2593		flags = BTRFS_BLOCK_GROUP_SYSTEM;
2594	else
2595		flags = BTRFS_BLOCK_GROUP_METADATA;
2596
2597	ret = btrfs_get_alloc_profile(fs_info, flags);
2598	return ret;
2599}
2600
2601static u64 first_logical_byte(struct btrfs_fs_info *fs_info)
2602{
2603	struct rb_node *leftmost;
2604	u64 bytenr = 0;
2605
2606	read_lock(&fs_info->block_group_cache_lock);
2607	/* Get the block group with the lowest logical start address. */
2608	leftmost = rb_first_cached(&fs_info->block_group_cache_tree);
2609	if (leftmost) {
2610		struct btrfs_block_group *bg;
2611
2612		bg = rb_entry(leftmost, struct btrfs_block_group, cache_node);
2613		bytenr = bg->start;
2614	}
2615	read_unlock(&fs_info->block_group_cache_lock);
2616
2617	return bytenr;
2618}
2619
2620static int pin_down_extent(struct btrfs_trans_handle *trans,
2621			   struct btrfs_block_group *cache,
2622			   u64 bytenr, u64 num_bytes, int reserved)
2623{
2624	struct btrfs_fs_info *fs_info = cache->fs_info;
2625
2626	spin_lock(&cache->space_info->lock);
2627	spin_lock(&cache->lock);
2628	cache->pinned += num_bytes;
2629	btrfs_space_info_update_bytes_pinned(fs_info, cache->space_info,
2630					     num_bytes);
2631	if (reserved) {
2632		cache->reserved -= num_bytes;
2633		cache->space_info->bytes_reserved -= num_bytes;
2634	}
2635	spin_unlock(&cache->lock);
2636	spin_unlock(&cache->space_info->lock);
2637
2638	set_extent_bit(&trans->transaction->pinned_extents, bytenr,
2639		       bytenr + num_bytes - 1, EXTENT_DIRTY, NULL);
2640	return 0;
2641}
2642
2643int btrfs_pin_extent(struct btrfs_trans_handle *trans,
2644		     u64 bytenr, u64 num_bytes, int reserved)
2645{
2646	struct btrfs_block_group *cache;
2647
2648	cache = btrfs_lookup_block_group(trans->fs_info, bytenr);
2649	BUG_ON(!cache); /* Logic error */
2650
2651	pin_down_extent(trans, cache, bytenr, num_bytes, reserved);
2652
2653	btrfs_put_block_group(cache);
2654	return 0;
2655}
2656
2657int btrfs_pin_extent_for_log_replay(struct btrfs_trans_handle *trans,
2658				    const struct extent_buffer *eb)
2659{
2660	struct btrfs_block_group *cache;
2661	int ret;
2662
2663	cache = btrfs_lookup_block_group(trans->fs_info, eb->start);
2664	if (!cache)
2665		return -EINVAL;
2666
2667	/*
2668	 * Fully cache the free space first so that our pin removes the free space
2669	 * from the cache.
2670	 */
2671	ret = btrfs_cache_block_group(cache, true);
2672	if (ret)
2673		goto out;
2674
2675	pin_down_extent(trans, cache, eb->start, eb->len, 0);
2676
2677	/* remove us from the free space cache (if we're there at all) */
2678	ret = btrfs_remove_free_space(cache, eb->start, eb->len);
2679out:
2680	btrfs_put_block_group(cache);
2681	return ret;
2682}
2683
2684static int __exclude_logged_extent(struct btrfs_fs_info *fs_info,
2685				   u64 start, u64 num_bytes)
2686{
2687	int ret;
2688	struct btrfs_block_group *block_group;
2689
2690	block_group = btrfs_lookup_block_group(fs_info, start);
2691	if (!block_group)
2692		return -EINVAL;
2693
2694	ret = btrfs_cache_block_group(block_group, true);
2695	if (ret)
2696		goto out;
2697
2698	ret = btrfs_remove_free_space(block_group, start, num_bytes);
2699out:
2700	btrfs_put_block_group(block_group);
2701	return ret;
2702}
2703
2704int btrfs_exclude_logged_extents(struct extent_buffer *eb)
2705{
2706	struct btrfs_fs_info *fs_info = eb->fs_info;
2707	struct btrfs_file_extent_item *item;
2708	struct btrfs_key key;
2709	int found_type;
2710	int i;
2711	int ret = 0;
2712
2713	if (!btrfs_fs_incompat(fs_info, MIXED_GROUPS))
2714		return 0;
2715
2716	for (i = 0; i < btrfs_header_nritems(eb); i++) {
2717		btrfs_item_key_to_cpu(eb, &key, i);
2718		if (key.type != BTRFS_EXTENT_DATA_KEY)
2719			continue;
2720		item = btrfs_item_ptr(eb, i, struct btrfs_file_extent_item);
2721		found_type = btrfs_file_extent_type(eb, item);
2722		if (found_type == BTRFS_FILE_EXTENT_INLINE)
2723			continue;
2724		if (btrfs_file_extent_disk_bytenr(eb, item) == 0)
2725			continue;
2726		key.objectid = btrfs_file_extent_disk_bytenr(eb, item);
2727		key.offset = btrfs_file_extent_disk_num_bytes(eb, item);
2728		ret = __exclude_logged_extent(fs_info, key.objectid, key.offset);
2729		if (ret)
2730			break;
2731	}
2732
2733	return ret;
2734}
2735
2736static void
2737btrfs_inc_block_group_reservations(struct btrfs_block_group *bg)
2738{
2739	atomic_inc(&bg->reservations);
2740}
2741
2742/*
2743 * Returns the free cluster for the given space info and sets empty_cluster to
2744 * what it should be based on the mount options.
2745 */
2746static struct btrfs_free_cluster *
2747fetch_cluster_info(struct btrfs_fs_info *fs_info,
2748		   struct btrfs_space_info *space_info, u64 *empty_cluster)
2749{
2750	struct btrfs_free_cluster *ret = NULL;
2751
2752	*empty_cluster = 0;
2753	if (btrfs_mixed_space_info(space_info))
2754		return ret;
2755
2756	if (space_info->flags & BTRFS_BLOCK_GROUP_METADATA) {
2757		ret = &fs_info->meta_alloc_cluster;
2758		if (btrfs_test_opt(fs_info, SSD))
2759			*empty_cluster = SZ_2M;
2760		else
2761			*empty_cluster = SZ_64K;
2762	} else if ((space_info->flags & BTRFS_BLOCK_GROUP_DATA) &&
2763		   btrfs_test_opt(fs_info, SSD_SPREAD)) {
2764		*empty_cluster = SZ_2M;
2765		ret = &fs_info->data_alloc_cluster;
2766	}
2767
2768	return ret;
2769}
2770
2771static int unpin_extent_range(struct btrfs_fs_info *fs_info,
2772			      u64 start, u64 end,
2773			      const bool return_free_space)
2774{
2775	struct btrfs_block_group *cache = NULL;
2776	struct btrfs_space_info *space_info;
2777	struct btrfs_block_rsv *global_rsv = &fs_info->global_block_rsv;
2778	struct btrfs_free_cluster *cluster = NULL;
2779	u64 len;
2780	u64 total_unpinned = 0;
2781	u64 empty_cluster = 0;
2782	bool readonly;
 
2783
2784	while (start <= end) {
2785		readonly = false;
2786		if (!cache ||
2787		    start >= cache->start + cache->length) {
2788			if (cache)
2789				btrfs_put_block_group(cache);
2790			total_unpinned = 0;
2791			cache = btrfs_lookup_block_group(fs_info, start);
2792			BUG_ON(!cache); /* Logic error */
 
 
 
 
2793
2794			cluster = fetch_cluster_info(fs_info,
2795						     cache->space_info,
2796						     &empty_cluster);
2797			empty_cluster <<= 1;
2798		}
2799
2800		len = cache->start + cache->length - start;
2801		len = min(len, end + 1 - start);
2802
2803		if (return_free_space)
2804			btrfs_add_free_space(cache, start, len);
2805
2806		start += len;
2807		total_unpinned += len;
2808		space_info = cache->space_info;
2809
2810		/*
2811		 * If this space cluster has been marked as fragmented and we've
2812		 * unpinned enough in this block group to potentially allow a
2813		 * cluster to be created inside of it go ahead and clear the
2814		 * fragmented check.
2815		 */
2816		if (cluster && cluster->fragmented &&
2817		    total_unpinned > empty_cluster) {
2818			spin_lock(&cluster->lock);
2819			cluster->fragmented = 0;
2820			spin_unlock(&cluster->lock);
2821		}
2822
2823		spin_lock(&space_info->lock);
2824		spin_lock(&cache->lock);
2825		cache->pinned -= len;
2826		btrfs_space_info_update_bytes_pinned(fs_info, space_info, -len);
2827		space_info->max_extent_size = 0;
2828		if (cache->ro) {
2829			space_info->bytes_readonly += len;
2830			readonly = true;
2831		} else if (btrfs_is_zoned(fs_info)) {
2832			/* Need reset before reusing in a zoned block group */
2833			space_info->bytes_zone_unusable += len;
2834			readonly = true;
2835		}
2836		spin_unlock(&cache->lock);
2837		if (!readonly && return_free_space &&
2838		    global_rsv->space_info == space_info) {
2839			spin_lock(&global_rsv->lock);
2840			if (!global_rsv->full) {
2841				u64 to_add = min(len, global_rsv->size -
2842						      global_rsv->reserved);
2843
2844				global_rsv->reserved += to_add;
2845				btrfs_space_info_update_bytes_may_use(fs_info,
2846						space_info, to_add);
2847				if (global_rsv->reserved >= global_rsv->size)
2848					global_rsv->full = 1;
2849				len -= to_add;
2850			}
2851			spin_unlock(&global_rsv->lock);
2852		}
2853		/* Add to any tickets we may have */
2854		if (!readonly && return_free_space && len)
2855			btrfs_try_granting_tickets(fs_info, space_info);
2856		spin_unlock(&space_info->lock);
2857	}
2858
2859	if (cache)
2860		btrfs_put_block_group(cache);
2861	return 0;
 
2862}
2863
2864int btrfs_finish_extent_commit(struct btrfs_trans_handle *trans)
2865{
2866	struct btrfs_fs_info *fs_info = trans->fs_info;
2867	struct btrfs_block_group *block_group, *tmp;
2868	struct list_head *deleted_bgs;
2869	struct extent_io_tree *unpin;
2870	u64 start;
2871	u64 end;
2872	int ret;
2873
2874	unpin = &trans->transaction->pinned_extents;
2875
2876	while (!TRANS_ABORTED(trans)) {
2877		struct extent_state *cached_state = NULL;
2878
2879		mutex_lock(&fs_info->unused_bg_unpin_mutex);
2880		if (!find_first_extent_bit(unpin, 0, &start, &end,
2881					   EXTENT_DIRTY, &cached_state)) {
2882			mutex_unlock(&fs_info->unused_bg_unpin_mutex);
2883			break;
2884		}
2885
2886		if (btrfs_test_opt(fs_info, DISCARD_SYNC))
2887			ret = btrfs_discard_extent(fs_info, start,
2888						   end + 1 - start, NULL);
2889
2890		clear_extent_dirty(unpin, start, end, &cached_state);
2891		unpin_extent_range(fs_info, start, end, true);
 
2892		mutex_unlock(&fs_info->unused_bg_unpin_mutex);
2893		free_extent_state(cached_state);
2894		cond_resched();
2895	}
2896
2897	if (btrfs_test_opt(fs_info, DISCARD_ASYNC)) {
2898		btrfs_discard_calc_delay(&fs_info->discard_ctl);
2899		btrfs_discard_schedule_work(&fs_info->discard_ctl, true);
2900	}
2901
2902	/*
2903	 * Transaction is finished.  We don't need the lock anymore.  We
2904	 * do need to clean up the block groups in case of a transaction
2905	 * abort.
2906	 */
2907	deleted_bgs = &trans->transaction->deleted_bgs;
2908	list_for_each_entry_safe(block_group, tmp, deleted_bgs, bg_list) {
2909		u64 trimmed = 0;
2910
2911		ret = -EROFS;
2912		if (!TRANS_ABORTED(trans))
2913			ret = btrfs_discard_extent(fs_info,
2914						   block_group->start,
2915						   block_group->length,
2916						   &trimmed);
2917
2918		list_del_init(&block_group->bg_list);
2919		btrfs_unfreeze_block_group(block_group);
2920		btrfs_put_block_group(block_group);
2921
2922		if (ret) {
2923			const char *errstr = btrfs_decode_error(ret);
2924			btrfs_warn(fs_info,
2925			   "discard failed while removing blockgroup: errno=%d %s",
2926				   ret, errstr);
2927		}
2928	}
2929
2930	return 0;
2931}
2932
2933/*
2934 * Parse an extent item's inline extents looking for a simple quotas owner ref.
2935 *
2936 * @fs_info:	the btrfs_fs_info for this mount
2937 * @leaf:	a leaf in the extent tree containing the extent item
2938 * @slot:	the slot in the leaf where the extent item is found
2939 *
2940 * Returns the objectid of the root that originally allocated the extent item
2941 * if the inline owner ref is expected and present, otherwise 0.
2942 *
2943 * If an extent item has an owner ref item, it will be the first inline ref
2944 * item. Therefore the logic is to check whether there are any inline ref
2945 * items, then check the type of the first one.
2946 */
2947u64 btrfs_get_extent_owner_root(struct btrfs_fs_info *fs_info,
2948				struct extent_buffer *leaf, int slot)
2949{
2950	struct btrfs_extent_item *ei;
2951	struct btrfs_extent_inline_ref *iref;
2952	struct btrfs_extent_owner_ref *oref;
2953	unsigned long ptr;
2954	unsigned long end;
2955	int type;
2956
2957	if (!btrfs_fs_incompat(fs_info, SIMPLE_QUOTA))
2958		return 0;
2959
2960	ei = btrfs_item_ptr(leaf, slot, struct btrfs_extent_item);
2961	ptr = (unsigned long)(ei + 1);
2962	end = (unsigned long)ei + btrfs_item_size(leaf, slot);
2963
2964	/* No inline ref items of any kind, can't check type. */
2965	if (ptr == end)
2966		return 0;
2967
2968	iref = (struct btrfs_extent_inline_ref *)ptr;
2969	type = btrfs_get_extent_inline_ref_type(leaf, iref, BTRFS_REF_TYPE_ANY);
2970
2971	/* We found an owner ref, get the root out of it. */
2972	if (type == BTRFS_EXTENT_OWNER_REF_KEY) {
2973		oref = (struct btrfs_extent_owner_ref *)(&iref->offset);
2974		return btrfs_extent_owner_ref_root_id(leaf, oref);
2975	}
2976
2977	/* We have inline refs, but not an owner ref. */
2978	return 0;
2979}
2980
2981static int do_free_extent_accounting(struct btrfs_trans_handle *trans,
2982				     u64 bytenr, struct btrfs_squota_delta *delta)
2983{
2984	int ret;
2985	u64 num_bytes = delta->num_bytes;
2986
2987	if (delta->is_data) {
2988		struct btrfs_root *csum_root;
2989
2990		csum_root = btrfs_csum_root(trans->fs_info, bytenr);
2991		ret = btrfs_del_csums(trans, csum_root, bytenr, num_bytes);
2992		if (ret) {
2993			btrfs_abort_transaction(trans, ret);
2994			return ret;
2995		}
2996
2997		ret = btrfs_delete_raid_extent(trans, bytenr, num_bytes);
2998		if (ret) {
2999			btrfs_abort_transaction(trans, ret);
3000			return ret;
3001		}
3002	}
3003
3004	ret = btrfs_record_squota_delta(trans->fs_info, delta);
3005	if (ret) {
3006		btrfs_abort_transaction(trans, ret);
3007		return ret;
3008	}
3009
3010	ret = add_to_free_space_tree(trans, bytenr, num_bytes);
3011	if (ret) {
3012		btrfs_abort_transaction(trans, ret);
3013		return ret;
3014	}
3015
3016	ret = btrfs_update_block_group(trans, bytenr, num_bytes, false);
3017	if (ret)
3018		btrfs_abort_transaction(trans, ret);
3019
3020	return ret;
3021}
3022
3023#define abort_and_dump(trans, path, fmt, args...)	\
3024({							\
3025	btrfs_abort_transaction(trans, -EUCLEAN);	\
3026	btrfs_print_leaf(path->nodes[0]);		\
3027	btrfs_crit(trans->fs_info, fmt, ##args);	\
3028})
3029
3030/*
3031 * Drop one or more refs of @node.
3032 *
3033 * 1. Locate the extent refs.
3034 *    It's either inline in EXTENT/METADATA_ITEM or in keyed SHARED_* item.
3035 *    Locate it, then reduce the refs number or remove the ref line completely.
3036 *
3037 * 2. Update the refs count in EXTENT/METADATA_ITEM
3038 *
3039 * Inline backref case:
3040 *
3041 * in extent tree we have:
3042 *
3043 * 	item 0 key (13631488 EXTENT_ITEM 1048576) itemoff 16201 itemsize 82
3044 *		refs 2 gen 6 flags DATA
3045 *		extent data backref root FS_TREE objectid 258 offset 0 count 1
3046 *		extent data backref root FS_TREE objectid 257 offset 0 count 1
3047 *
3048 * This function gets called with:
3049 *
3050 *    node->bytenr = 13631488
3051 *    node->num_bytes = 1048576
3052 *    root_objectid = FS_TREE
3053 *    owner_objectid = 257
3054 *    owner_offset = 0
3055 *    refs_to_drop = 1
3056 *
3057 * Then we should get some like:
3058 *
3059 * 	item 0 key (13631488 EXTENT_ITEM 1048576) itemoff 16201 itemsize 82
3060 *		refs 1 gen 6 flags DATA
3061 *		extent data backref root FS_TREE objectid 258 offset 0 count 1
3062 *
3063 * Keyed backref case:
3064 *
3065 * in extent tree we have:
3066 *
3067 *	item 0 key (13631488 EXTENT_ITEM 1048576) itemoff 3971 itemsize 24
3068 *		refs 754 gen 6 flags DATA
3069 *	[...]
3070 *	item 2 key (13631488 EXTENT_DATA_REF <HASH>) itemoff 3915 itemsize 28
3071 *		extent data backref root FS_TREE objectid 866 offset 0 count 1
3072 *
3073 * This function get called with:
3074 *
3075 *    node->bytenr = 13631488
3076 *    node->num_bytes = 1048576
3077 *    root_objectid = FS_TREE
3078 *    owner_objectid = 866
3079 *    owner_offset = 0
3080 *    refs_to_drop = 1
3081 *
3082 * Then we should get some like:
3083 *
3084 *	item 0 key (13631488 EXTENT_ITEM 1048576) itemoff 3971 itemsize 24
3085 *		refs 753 gen 6 flags DATA
3086 *
3087 * And that (13631488 EXTENT_DATA_REF <HASH>) gets removed.
3088 */
3089static int __btrfs_free_extent(struct btrfs_trans_handle *trans,
3090			       struct btrfs_delayed_ref_head *href,
3091			       struct btrfs_delayed_ref_node *node, u64 parent,
3092			       u64 root_objectid, u64 owner_objectid,
3093			       u64 owner_offset,
3094			       struct btrfs_delayed_extent_op *extent_op)
3095{
3096	struct btrfs_fs_info *info = trans->fs_info;
3097	struct btrfs_key key;
3098	struct btrfs_path *path;
3099	struct btrfs_root *extent_root;
3100	struct extent_buffer *leaf;
3101	struct btrfs_extent_item *ei;
3102	struct btrfs_extent_inline_ref *iref;
3103	int ret;
3104	int is_data;
3105	int extent_slot = 0;
3106	int found_extent = 0;
3107	int num_to_del = 1;
3108	int refs_to_drop = node->ref_mod;
3109	u32 item_size;
3110	u64 refs;
3111	u64 bytenr = node->bytenr;
3112	u64 num_bytes = node->num_bytes;
3113	bool skinny_metadata = btrfs_fs_incompat(info, SKINNY_METADATA);
3114	u64 delayed_ref_root = href->owning_root;
3115
3116	extent_root = btrfs_extent_root(info, bytenr);
3117	ASSERT(extent_root);
3118
3119	path = btrfs_alloc_path();
3120	if (!path)
3121		return -ENOMEM;
3122
3123	is_data = owner_objectid >= BTRFS_FIRST_FREE_OBJECTID;
3124
3125	if (!is_data && refs_to_drop != 1) {
3126		btrfs_crit(info,
3127"invalid refs_to_drop, dropping more than 1 refs for tree block %llu refs_to_drop %u",
3128			   node->bytenr, refs_to_drop);
3129		ret = -EINVAL;
3130		btrfs_abort_transaction(trans, ret);
3131		goto out;
3132	}
3133
3134	if (is_data)
3135		skinny_metadata = false;
3136
3137	ret = lookup_extent_backref(trans, path, &iref, bytenr, num_bytes,
3138				    parent, root_objectid, owner_objectid,
3139				    owner_offset);
3140	if (ret == 0) {
3141		/*
3142		 * Either the inline backref or the SHARED_DATA_REF/
3143		 * SHARED_BLOCK_REF is found
3144		 *
3145		 * Here is a quick path to locate EXTENT/METADATA_ITEM.
3146		 * It's possible the EXTENT/METADATA_ITEM is near current slot.
3147		 */
3148		extent_slot = path->slots[0];
3149		while (extent_slot >= 0) {
3150			btrfs_item_key_to_cpu(path->nodes[0], &key,
3151					      extent_slot);
3152			if (key.objectid != bytenr)
3153				break;
3154			if (key.type == BTRFS_EXTENT_ITEM_KEY &&
3155			    key.offset == num_bytes) {
3156				found_extent = 1;
3157				break;
3158			}
3159			if (key.type == BTRFS_METADATA_ITEM_KEY &&
3160			    key.offset == owner_objectid) {
3161				found_extent = 1;
3162				break;
3163			}
3164
3165			/* Quick path didn't find the EXTEMT/METADATA_ITEM */
3166			if (path->slots[0] - extent_slot > 5)
3167				break;
3168			extent_slot--;
3169		}
3170
3171		if (!found_extent) {
3172			if (iref) {
3173				abort_and_dump(trans, path,
3174"invalid iref slot %u, no EXTENT/METADATA_ITEM found but has inline extent ref",
3175					   path->slots[0]);
3176				ret = -EUCLEAN;
3177				goto out;
3178			}
3179			/* Must be SHARED_* item, remove the backref first */
3180			ret = remove_extent_backref(trans, extent_root, path,
3181						    NULL, refs_to_drop, is_data);
3182			if (ret) {
3183				btrfs_abort_transaction(trans, ret);
3184				goto out;
3185			}
3186			btrfs_release_path(path);
3187
3188			/* Slow path to locate EXTENT/METADATA_ITEM */
3189			key.objectid = bytenr;
3190			key.type = BTRFS_EXTENT_ITEM_KEY;
3191			key.offset = num_bytes;
3192
3193			if (!is_data && skinny_metadata) {
3194				key.type = BTRFS_METADATA_ITEM_KEY;
3195				key.offset = owner_objectid;
3196			}
3197
3198			ret = btrfs_search_slot(trans, extent_root,
3199						&key, path, -1, 1);
3200			if (ret > 0 && skinny_metadata && path->slots[0]) {
3201				/*
3202				 * Couldn't find our skinny metadata item,
3203				 * see if we have ye olde extent item.
3204				 */
3205				path->slots[0]--;
3206				btrfs_item_key_to_cpu(path->nodes[0], &key,
3207						      path->slots[0]);
3208				if (key.objectid == bytenr &&
3209				    key.type == BTRFS_EXTENT_ITEM_KEY &&
3210				    key.offset == num_bytes)
3211					ret = 0;
3212			}
3213
3214			if (ret > 0 && skinny_metadata) {
3215				skinny_metadata = false;
3216				key.objectid = bytenr;
3217				key.type = BTRFS_EXTENT_ITEM_KEY;
3218				key.offset = num_bytes;
3219				btrfs_release_path(path);
3220				ret = btrfs_search_slot(trans, extent_root,
3221							&key, path, -1, 1);
3222			}
3223
3224			if (ret) {
3225				if (ret > 0)
3226					btrfs_print_leaf(path->nodes[0]);
3227				btrfs_err(info,
3228			"umm, got %d back from search, was looking for %llu, slot %d",
3229					  ret, bytenr, path->slots[0]);
3230			}
3231			if (ret < 0) {
3232				btrfs_abort_transaction(trans, ret);
3233				goto out;
3234			}
3235			extent_slot = path->slots[0];
3236		}
3237	} else if (WARN_ON(ret == -ENOENT)) {
3238		abort_and_dump(trans, path,
3239"unable to find ref byte nr %llu parent %llu root %llu owner %llu offset %llu slot %d",
3240			       bytenr, parent, root_objectid, owner_objectid,
3241			       owner_offset, path->slots[0]);
3242		goto out;
3243	} else {
3244		btrfs_abort_transaction(trans, ret);
3245		goto out;
3246	}
3247
3248	leaf = path->nodes[0];
3249	item_size = btrfs_item_size(leaf, extent_slot);
3250	if (unlikely(item_size < sizeof(*ei))) {
3251		ret = -EUCLEAN;
3252		btrfs_err(trans->fs_info,
3253			  "unexpected extent item size, has %u expect >= %zu",
3254			  item_size, sizeof(*ei));
3255		btrfs_abort_transaction(trans, ret);
3256		goto out;
3257	}
3258	ei = btrfs_item_ptr(leaf, extent_slot,
3259			    struct btrfs_extent_item);
3260	if (owner_objectid < BTRFS_FIRST_FREE_OBJECTID &&
3261	    key.type == BTRFS_EXTENT_ITEM_KEY) {
3262		struct btrfs_tree_block_info *bi;
3263
3264		if (item_size < sizeof(*ei) + sizeof(*bi)) {
3265			abort_and_dump(trans, path,
3266"invalid extent item size for key (%llu, %u, %llu) slot %u owner %llu, has %u expect >= %zu",
3267				       key.objectid, key.type, key.offset,
3268				       path->slots[0], owner_objectid, item_size,
3269				       sizeof(*ei) + sizeof(*bi));
3270			ret = -EUCLEAN;
3271			goto out;
3272		}
3273		bi = (struct btrfs_tree_block_info *)(ei + 1);
3274		WARN_ON(owner_objectid != btrfs_tree_block_level(leaf, bi));
3275	}
3276
3277	refs = btrfs_extent_refs(leaf, ei);
3278	if (refs < refs_to_drop) {
3279		abort_and_dump(trans, path,
3280		"trying to drop %d refs but we only have %llu for bytenr %llu slot %u",
3281			       refs_to_drop, refs, bytenr, path->slots[0]);
3282		ret = -EUCLEAN;
3283		goto out;
3284	}
3285	refs -= refs_to_drop;
3286
3287	if (refs > 0) {
3288		if (extent_op)
3289			__run_delayed_extent_op(extent_op, leaf, ei);
3290		/*
3291		 * In the case of inline back ref, reference count will
3292		 * be updated by remove_extent_backref
3293		 */
3294		if (iref) {
3295			if (!found_extent) {
3296				abort_and_dump(trans, path,
3297"invalid iref, got inlined extent ref but no EXTENT/METADATA_ITEM found, slot %u",
3298					       path->slots[0]);
3299				ret = -EUCLEAN;
3300				goto out;
3301			}
3302		} else {
3303			btrfs_set_extent_refs(leaf, ei, refs);
3304			btrfs_mark_buffer_dirty(trans, leaf);
3305		}
3306		if (found_extent) {
3307			ret = remove_extent_backref(trans, extent_root, path,
3308						    iref, refs_to_drop, is_data);
3309			if (ret) {
3310				btrfs_abort_transaction(trans, ret);
3311				goto out;
3312			}
3313		}
3314	} else {
3315		struct btrfs_squota_delta delta = {
3316			.root = delayed_ref_root,
3317			.num_bytes = num_bytes,
3318			.is_data = is_data,
3319			.is_inc = false,
3320			.generation = btrfs_extent_generation(leaf, ei),
3321		};
3322
3323		/* In this branch refs == 1 */
3324		if (found_extent) {
3325			if (is_data && refs_to_drop !=
3326			    extent_data_ref_count(path, iref)) {
3327				abort_and_dump(trans, path,
3328		"invalid refs_to_drop, current refs %u refs_to_drop %u slot %u",
3329					       extent_data_ref_count(path, iref),
3330					       refs_to_drop, path->slots[0]);
3331				ret = -EUCLEAN;
3332				goto out;
3333			}
3334			if (iref) {
3335				if (path->slots[0] != extent_slot) {
3336					abort_and_dump(trans, path,
3337"invalid iref, extent item key (%llu %u %llu) slot %u doesn't have wanted iref",
3338						       key.objectid, key.type,
3339						       key.offset, path->slots[0]);
3340					ret = -EUCLEAN;
3341					goto out;
3342				}
3343			} else {
3344				/*
3345				 * No inline ref, we must be at SHARED_* item,
3346				 * And it's single ref, it must be:
3347				 * |	extent_slot	  ||extent_slot + 1|
3348				 * [ EXTENT/METADATA_ITEM ][ SHARED_* ITEM ]
3349				 */
3350				if (path->slots[0] != extent_slot + 1) {
3351					abort_and_dump(trans, path,
3352	"invalid SHARED_* item slot %u, previous item is not EXTENT/METADATA_ITEM",
3353						       path->slots[0]);
3354					ret = -EUCLEAN;
3355					goto out;
3356				}
3357				path->slots[0] = extent_slot;
3358				num_to_del = 2;
3359			}
3360		}
3361		/*
3362		 * We can't infer the data owner from the delayed ref, so we need
3363		 * to try to get it from the owning ref item.
3364		 *
3365		 * If it is not present, then that extent was not written under
3366		 * simple quotas mode, so we don't need to account for its deletion.
3367		 */
3368		if (is_data)
3369			delta.root = btrfs_get_extent_owner_root(trans->fs_info,
3370								 leaf, extent_slot);
3371
3372		ret = btrfs_del_items(trans, extent_root, path, path->slots[0],
3373				      num_to_del);
3374		if (ret) {
3375			btrfs_abort_transaction(trans, ret);
3376			goto out;
3377		}
3378		btrfs_release_path(path);
3379
3380		ret = do_free_extent_accounting(trans, bytenr, &delta);
3381	}
3382	btrfs_release_path(path);
3383
3384out:
3385	btrfs_free_path(path);
3386	return ret;
3387}
3388
3389/*
3390 * when we free an block, it is possible (and likely) that we free the last
3391 * delayed ref for that extent as well.  This searches the delayed ref tree for
3392 * a given extent, and if there are no other delayed refs to be processed, it
3393 * removes it from the tree.
3394 */
3395static noinline int check_ref_cleanup(struct btrfs_trans_handle *trans,
3396				      u64 bytenr)
3397{
3398	struct btrfs_delayed_ref_head *head;
3399	struct btrfs_delayed_ref_root *delayed_refs;
3400	int ret = 0;
3401
3402	delayed_refs = &trans->transaction->delayed_refs;
3403	spin_lock(&delayed_refs->lock);
3404	head = btrfs_find_delayed_ref_head(delayed_refs, bytenr);
3405	if (!head)
3406		goto out_delayed_unlock;
3407
3408	spin_lock(&head->lock);
3409	if (!RB_EMPTY_ROOT(&head->ref_tree.rb_root))
3410		goto out;
3411
3412	if (cleanup_extent_op(head) != NULL)
3413		goto out;
3414
3415	/*
3416	 * waiting for the lock here would deadlock.  If someone else has it
3417	 * locked they are already in the process of dropping it anyway
3418	 */
3419	if (!mutex_trylock(&head->mutex))
3420		goto out;
3421
3422	btrfs_delete_ref_head(delayed_refs, head);
3423	head->processing = false;
3424
3425	spin_unlock(&head->lock);
3426	spin_unlock(&delayed_refs->lock);
3427
3428	BUG_ON(head->extent_op);
3429	if (head->must_insert_reserved)
3430		ret = 1;
3431
3432	btrfs_cleanup_ref_head_accounting(trans->fs_info, delayed_refs, head);
3433	mutex_unlock(&head->mutex);
3434	btrfs_put_delayed_ref_head(head);
3435	return ret;
3436out:
3437	spin_unlock(&head->lock);
3438
3439out_delayed_unlock:
3440	spin_unlock(&delayed_refs->lock);
3441	return 0;
3442}
3443
3444void btrfs_free_tree_block(struct btrfs_trans_handle *trans,
3445			   u64 root_id,
3446			   struct extent_buffer *buf,
3447			   u64 parent, int last_ref)
3448{
3449	struct btrfs_fs_info *fs_info = trans->fs_info;
3450	struct btrfs_ref generic_ref = { 0 };
3451	struct btrfs_block_group *bg;
3452	int ret;
3453
3454	btrfs_init_generic_ref(&generic_ref, BTRFS_DROP_DELAYED_REF,
3455			       buf->start, buf->len, parent, btrfs_header_owner(buf));
3456	btrfs_init_tree_ref(&generic_ref, btrfs_header_level(buf),
3457			    root_id, 0, false);
3458
3459	if (root_id != BTRFS_TREE_LOG_OBJECTID) {
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
3460		btrfs_ref_tree_mod(fs_info, &generic_ref);
3461		ret = btrfs_add_delayed_tree_ref(trans, &generic_ref, NULL);
3462		BUG_ON(ret); /* -ENOMEM */
3463	}
3464
3465	if (!last_ref)
3466		return;
3467
3468	if (btrfs_header_generation(buf) != trans->transid)
3469		goto out;
3470
3471	if (root_id != BTRFS_TREE_LOG_OBJECTID) {
3472		ret = check_ref_cleanup(trans, buf->start);
3473		if (!ret)
3474			goto out;
3475	}
3476
3477	bg = btrfs_lookup_block_group(fs_info, buf->start);
3478
3479	if (btrfs_header_flag(buf, BTRFS_HEADER_FLAG_WRITTEN)) {
3480		pin_down_extent(trans, bg, buf->start, buf->len, 1);
3481		btrfs_put_block_group(bg);
3482		goto out;
3483	}
3484
3485	/*
3486	 * If there are tree mod log users we may have recorded mod log
3487	 * operations for this node.  If we re-allocate this node we
3488	 * could replay operations on this node that happened when it
3489	 * existed in a completely different root.  For example if it
3490	 * was part of root A, then was reallocated to root B, and we
3491	 * are doing a btrfs_old_search_slot(root b), we could replay
3492	 * operations that happened when the block was part of root A,
3493	 * giving us an inconsistent view of the btree.
3494	 *
3495	 * We are safe from races here because at this point no other
3496	 * node or root points to this extent buffer, so if after this
3497	 * check a new tree mod log user joins we will not have an
3498	 * existing log of operations on this node that we have to
3499	 * contend with.
3500	 */
3501
3502	if (test_bit(BTRFS_FS_TREE_MOD_LOG_USERS, &fs_info->flags)
3503		     || btrfs_is_zoned(fs_info)) {
3504		pin_down_extent(trans, bg, buf->start, buf->len, 1);
3505		btrfs_put_block_group(bg);
3506		goto out;
3507	}
3508
3509	WARN_ON(test_bit(EXTENT_BUFFER_DIRTY, &buf->bflags));
3510
3511	btrfs_add_free_space(bg, buf->start, buf->len);
3512	btrfs_free_reserved_bytes(bg, buf->len, 0);
3513	btrfs_put_block_group(bg);
3514	trace_btrfs_reserved_extent_free(fs_info, buf->start, buf->len);
3515
3516out:
3517
3518	/*
3519	 * Deleting the buffer, clear the corrupt flag since it doesn't
3520	 * matter anymore.
3521	 */
3522	clear_bit(EXTENT_BUFFER_CORRUPT, &buf->bflags);
3523}
3524
3525/* Can return -ENOMEM */
3526int btrfs_free_extent(struct btrfs_trans_handle *trans, struct btrfs_ref *ref)
3527{
3528	struct btrfs_fs_info *fs_info = trans->fs_info;
3529	int ret;
3530
3531	if (btrfs_is_testing(fs_info))
3532		return 0;
3533
3534	/*
3535	 * tree log blocks never actually go into the extent allocation
3536	 * tree, just update pinning info and exit early.
3537	 */
3538	if ((ref->type == BTRFS_REF_METADATA &&
3539	     ref->tree_ref.ref_root == BTRFS_TREE_LOG_OBJECTID) ||
3540	    (ref->type == BTRFS_REF_DATA &&
3541	     ref->data_ref.ref_root == BTRFS_TREE_LOG_OBJECTID)) {
3542		btrfs_pin_extent(trans, ref->bytenr, ref->len, 1);
3543		ret = 0;
3544	} else if (ref->type == BTRFS_REF_METADATA) {
3545		ret = btrfs_add_delayed_tree_ref(trans, ref, NULL);
3546	} else {
3547		ret = btrfs_add_delayed_data_ref(trans, ref, 0);
3548	}
3549
3550	if (!((ref->type == BTRFS_REF_METADATA &&
3551	       ref->tree_ref.ref_root == BTRFS_TREE_LOG_OBJECTID) ||
3552	      (ref->type == BTRFS_REF_DATA &&
3553	       ref->data_ref.ref_root == BTRFS_TREE_LOG_OBJECTID)))
3554		btrfs_ref_tree_mod(fs_info, ref);
3555
3556	return ret;
3557}
3558
3559enum btrfs_loop_type {
3560	/*
3561	 * Start caching block groups but do not wait for progress or for them
3562	 * to be done.
3563	 */
3564	LOOP_CACHING_NOWAIT,
3565
3566	/*
3567	 * Wait for the block group free_space >= the space we're waiting for if
3568	 * the block group isn't cached.
3569	 */
3570	LOOP_CACHING_WAIT,
3571
3572	/*
3573	 * Allow allocations to happen from block groups that do not yet have a
3574	 * size classification.
3575	 */
3576	LOOP_UNSET_SIZE_CLASS,
3577
3578	/*
3579	 * Allocate a chunk and then retry the allocation.
3580	 */
3581	LOOP_ALLOC_CHUNK,
3582
3583	/*
3584	 * Ignore the size class restrictions for this allocation.
3585	 */
3586	LOOP_WRONG_SIZE_CLASS,
3587
3588	/*
3589	 * Ignore the empty size, only try to allocate the number of bytes
3590	 * needed for this allocation.
3591	 */
3592	LOOP_NO_EMPTY_SIZE,
3593};
3594
3595static inline void
3596btrfs_lock_block_group(struct btrfs_block_group *cache,
3597		       int delalloc)
3598{
3599	if (delalloc)
3600		down_read(&cache->data_rwsem);
3601}
3602
3603static inline void btrfs_grab_block_group(struct btrfs_block_group *cache,
3604		       int delalloc)
3605{
3606	btrfs_get_block_group(cache);
3607	if (delalloc)
3608		down_read(&cache->data_rwsem);
3609}
3610
3611static struct btrfs_block_group *btrfs_lock_cluster(
3612		   struct btrfs_block_group *block_group,
3613		   struct btrfs_free_cluster *cluster,
3614		   int delalloc)
3615	__acquires(&cluster->refill_lock)
3616{
3617	struct btrfs_block_group *used_bg = NULL;
3618
3619	spin_lock(&cluster->refill_lock);
3620	while (1) {
3621		used_bg = cluster->block_group;
3622		if (!used_bg)
3623			return NULL;
3624
3625		if (used_bg == block_group)
3626			return used_bg;
3627
3628		btrfs_get_block_group(used_bg);
3629
3630		if (!delalloc)
3631			return used_bg;
3632
3633		if (down_read_trylock(&used_bg->data_rwsem))
3634			return used_bg;
3635
3636		spin_unlock(&cluster->refill_lock);
3637
3638		/* We should only have one-level nested. */
3639		down_read_nested(&used_bg->data_rwsem, SINGLE_DEPTH_NESTING);
3640
3641		spin_lock(&cluster->refill_lock);
3642		if (used_bg == cluster->block_group)
3643			return used_bg;
3644
3645		up_read(&used_bg->data_rwsem);
3646		btrfs_put_block_group(used_bg);
3647	}
3648}
3649
3650static inline void
3651btrfs_release_block_group(struct btrfs_block_group *cache,
3652			 int delalloc)
3653{
3654	if (delalloc)
3655		up_read(&cache->data_rwsem);
3656	btrfs_put_block_group(cache);
3657}
3658
3659/*
3660 * Helper function for find_free_extent().
3661 *
3662 * Return -ENOENT to inform caller that we need fallback to unclustered mode.
3663 * Return >0 to inform caller that we find nothing
3664 * Return 0 means we have found a location and set ffe_ctl->found_offset.
3665 */
3666static int find_free_extent_clustered(struct btrfs_block_group *bg,
3667				      struct find_free_extent_ctl *ffe_ctl,
3668				      struct btrfs_block_group **cluster_bg_ret)
3669{
3670	struct btrfs_block_group *cluster_bg;
3671	struct btrfs_free_cluster *last_ptr = ffe_ctl->last_ptr;
3672	u64 aligned_cluster;
3673	u64 offset;
3674	int ret;
3675
3676	cluster_bg = btrfs_lock_cluster(bg, last_ptr, ffe_ctl->delalloc);
3677	if (!cluster_bg)
3678		goto refill_cluster;
3679	if (cluster_bg != bg && (cluster_bg->ro ||
3680	    !block_group_bits(cluster_bg, ffe_ctl->flags)))
3681		goto release_cluster;
3682
3683	offset = btrfs_alloc_from_cluster(cluster_bg, last_ptr,
3684			ffe_ctl->num_bytes, cluster_bg->start,
3685			&ffe_ctl->max_extent_size);
3686	if (offset) {
3687		/* We have a block, we're done */
3688		spin_unlock(&last_ptr->refill_lock);
3689		trace_btrfs_reserve_extent_cluster(cluster_bg, ffe_ctl);
3690		*cluster_bg_ret = cluster_bg;
3691		ffe_ctl->found_offset = offset;
3692		return 0;
3693	}
3694	WARN_ON(last_ptr->block_group != cluster_bg);
3695
3696release_cluster:
3697	/*
3698	 * If we are on LOOP_NO_EMPTY_SIZE, we can't set up a new clusters, so
3699	 * lets just skip it and let the allocator find whatever block it can
3700	 * find. If we reach this point, we will have tried the cluster
3701	 * allocator plenty of times and not have found anything, so we are
3702	 * likely way too fragmented for the clustering stuff to find anything.
3703	 *
3704	 * However, if the cluster is taken from the current block group,
3705	 * release the cluster first, so that we stand a better chance of
3706	 * succeeding in the unclustered allocation.
3707	 */
3708	if (ffe_ctl->loop >= LOOP_NO_EMPTY_SIZE && cluster_bg != bg) {
3709		spin_unlock(&last_ptr->refill_lock);
3710		btrfs_release_block_group(cluster_bg, ffe_ctl->delalloc);
3711		return -ENOENT;
3712	}
3713
3714	/* This cluster didn't work out, free it and start over */
3715	btrfs_return_cluster_to_free_space(NULL, last_ptr);
3716
3717	if (cluster_bg != bg)
3718		btrfs_release_block_group(cluster_bg, ffe_ctl->delalloc);
3719
3720refill_cluster:
3721	if (ffe_ctl->loop >= LOOP_NO_EMPTY_SIZE) {
3722		spin_unlock(&last_ptr->refill_lock);
3723		return -ENOENT;
3724	}
3725
3726	aligned_cluster = max_t(u64,
3727			ffe_ctl->empty_cluster + ffe_ctl->empty_size,
3728			bg->full_stripe_len);
3729	ret = btrfs_find_space_cluster(bg, last_ptr, ffe_ctl->search_start,
3730			ffe_ctl->num_bytes, aligned_cluster);
3731	if (ret == 0) {
3732		/* Now pull our allocation out of this cluster */
3733		offset = btrfs_alloc_from_cluster(bg, last_ptr,
3734				ffe_ctl->num_bytes, ffe_ctl->search_start,
3735				&ffe_ctl->max_extent_size);
3736		if (offset) {
3737			/* We found one, proceed */
3738			spin_unlock(&last_ptr->refill_lock);
3739			ffe_ctl->found_offset = offset;
3740			trace_btrfs_reserve_extent_cluster(bg, ffe_ctl);
3741			return 0;
3742		}
3743	}
3744	/*
3745	 * At this point we either didn't find a cluster or we weren't able to
3746	 * allocate a block from our cluster.  Free the cluster we've been
3747	 * trying to use, and go to the next block group.
3748	 */
3749	btrfs_return_cluster_to_free_space(NULL, last_ptr);
3750	spin_unlock(&last_ptr->refill_lock);
3751	return 1;
3752}
3753
3754/*
3755 * Return >0 to inform caller that we find nothing
3756 * Return 0 when we found an free extent and set ffe_ctrl->found_offset
3757 */
3758static int find_free_extent_unclustered(struct btrfs_block_group *bg,
3759					struct find_free_extent_ctl *ffe_ctl)
3760{
3761	struct btrfs_free_cluster *last_ptr = ffe_ctl->last_ptr;
3762	u64 offset;
3763
3764	/*
3765	 * We are doing an unclustered allocation, set the fragmented flag so
3766	 * we don't bother trying to setup a cluster again until we get more
3767	 * space.
3768	 */
3769	if (unlikely(last_ptr)) {
3770		spin_lock(&last_ptr->lock);
3771		last_ptr->fragmented = 1;
3772		spin_unlock(&last_ptr->lock);
3773	}
3774	if (ffe_ctl->cached) {
3775		struct btrfs_free_space_ctl *free_space_ctl;
3776
3777		free_space_ctl = bg->free_space_ctl;
3778		spin_lock(&free_space_ctl->tree_lock);
3779		if (free_space_ctl->free_space <
3780		    ffe_ctl->num_bytes + ffe_ctl->empty_cluster +
3781		    ffe_ctl->empty_size) {
3782			ffe_ctl->total_free_space = max_t(u64,
3783					ffe_ctl->total_free_space,
3784					free_space_ctl->free_space);
3785			spin_unlock(&free_space_ctl->tree_lock);
3786			return 1;
3787		}
3788		spin_unlock(&free_space_ctl->tree_lock);
3789	}
3790
3791	offset = btrfs_find_space_for_alloc(bg, ffe_ctl->search_start,
3792			ffe_ctl->num_bytes, ffe_ctl->empty_size,
3793			&ffe_ctl->max_extent_size);
3794	if (!offset)
3795		return 1;
3796	ffe_ctl->found_offset = offset;
3797	return 0;
3798}
3799
3800static int do_allocation_clustered(struct btrfs_block_group *block_group,
3801				   struct find_free_extent_ctl *ffe_ctl,
3802				   struct btrfs_block_group **bg_ret)
3803{
3804	int ret;
3805
3806	/* We want to try and use the cluster allocator, so lets look there */
3807	if (ffe_ctl->last_ptr && ffe_ctl->use_cluster) {
3808		ret = find_free_extent_clustered(block_group, ffe_ctl, bg_ret);
3809		if (ret >= 0)
3810			return ret;
3811		/* ret == -ENOENT case falls through */
3812	}
3813
3814	return find_free_extent_unclustered(block_group, ffe_ctl);
3815}
3816
3817/*
3818 * Tree-log block group locking
3819 * ============================
3820 *
3821 * fs_info::treelog_bg_lock protects the fs_info::treelog_bg which
3822 * indicates the starting address of a block group, which is reserved only
3823 * for tree-log metadata.
3824 *
3825 * Lock nesting
3826 * ============
3827 *
3828 * space_info::lock
3829 *   block_group::lock
3830 *     fs_info::treelog_bg_lock
3831 */
3832
3833/*
3834 * Simple allocator for sequential-only block group. It only allows sequential
3835 * allocation. No need to play with trees. This function also reserves the
3836 * bytes as in btrfs_add_reserved_bytes.
3837 */
3838static int do_allocation_zoned(struct btrfs_block_group *block_group,
3839			       struct find_free_extent_ctl *ffe_ctl,
3840			       struct btrfs_block_group **bg_ret)
3841{
3842	struct btrfs_fs_info *fs_info = block_group->fs_info;
3843	struct btrfs_space_info *space_info = block_group->space_info;
3844	struct btrfs_free_space_ctl *ctl = block_group->free_space_ctl;
3845	u64 start = block_group->start;
3846	u64 num_bytes = ffe_ctl->num_bytes;
3847	u64 avail;
3848	u64 bytenr = block_group->start;
3849	u64 log_bytenr;
3850	u64 data_reloc_bytenr;
3851	int ret = 0;
3852	bool skip = false;
3853
3854	ASSERT(btrfs_is_zoned(block_group->fs_info));
3855
3856	/*
3857	 * Do not allow non-tree-log blocks in the dedicated tree-log block
3858	 * group, and vice versa.
3859	 */
3860	spin_lock(&fs_info->treelog_bg_lock);
3861	log_bytenr = fs_info->treelog_bg;
3862	if (log_bytenr && ((ffe_ctl->for_treelog && bytenr != log_bytenr) ||
3863			   (!ffe_ctl->for_treelog && bytenr == log_bytenr)))
3864		skip = true;
3865	spin_unlock(&fs_info->treelog_bg_lock);
3866	if (skip)
3867		return 1;
3868
3869	/*
3870	 * Do not allow non-relocation blocks in the dedicated relocation block
3871	 * group, and vice versa.
3872	 */
3873	spin_lock(&fs_info->relocation_bg_lock);
3874	data_reloc_bytenr = fs_info->data_reloc_bg;
3875	if (data_reloc_bytenr &&
3876	    ((ffe_ctl->for_data_reloc && bytenr != data_reloc_bytenr) ||
3877	     (!ffe_ctl->for_data_reloc && bytenr == data_reloc_bytenr)))
3878		skip = true;
3879	spin_unlock(&fs_info->relocation_bg_lock);
3880	if (skip)
3881		return 1;
3882
3883	/* Check RO and no space case before trying to activate it */
3884	spin_lock(&block_group->lock);
3885	if (block_group->ro || btrfs_zoned_bg_is_full(block_group)) {
3886		ret = 1;
3887		/*
3888		 * May need to clear fs_info->{treelog,data_reloc}_bg.
3889		 * Return the error after taking the locks.
3890		 */
3891	}
3892	spin_unlock(&block_group->lock);
3893
3894	/* Metadata block group is activated at write time. */
3895	if (!ret && (block_group->flags & BTRFS_BLOCK_GROUP_DATA) &&
3896	    !btrfs_zone_activate(block_group)) {
3897		ret = 1;
3898		/*
3899		 * May need to clear fs_info->{treelog,data_reloc}_bg.
3900		 * Return the error after taking the locks.
3901		 */
3902	}
3903
3904	spin_lock(&space_info->lock);
3905	spin_lock(&block_group->lock);
3906	spin_lock(&fs_info->treelog_bg_lock);
3907	spin_lock(&fs_info->relocation_bg_lock);
3908
3909	if (ret)
3910		goto out;
3911
3912	ASSERT(!ffe_ctl->for_treelog ||
3913	       block_group->start == fs_info->treelog_bg ||
3914	       fs_info->treelog_bg == 0);
3915	ASSERT(!ffe_ctl->for_data_reloc ||
3916	       block_group->start == fs_info->data_reloc_bg ||
3917	       fs_info->data_reloc_bg == 0);
3918
3919	if (block_group->ro ||
3920	    (!ffe_ctl->for_data_reloc &&
3921	     test_bit(BLOCK_GROUP_FLAG_ZONED_DATA_RELOC, &block_group->runtime_flags))) {
3922		ret = 1;
3923		goto out;
3924	}
3925
3926	/*
3927	 * Do not allow currently using block group to be tree-log dedicated
3928	 * block group.
3929	 */
3930	if (ffe_ctl->for_treelog && !fs_info->treelog_bg &&
3931	    (block_group->used || block_group->reserved)) {
3932		ret = 1;
3933		goto out;
3934	}
3935
3936	/*
3937	 * Do not allow currently used block group to be the data relocation
3938	 * dedicated block group.
3939	 */
3940	if (ffe_ctl->for_data_reloc && !fs_info->data_reloc_bg &&
3941	    (block_group->used || block_group->reserved)) {
3942		ret = 1;
3943		goto out;
3944	}
3945
3946	WARN_ON_ONCE(block_group->alloc_offset > block_group->zone_capacity);
3947	avail = block_group->zone_capacity - block_group->alloc_offset;
3948	if (avail < num_bytes) {
3949		if (ffe_ctl->max_extent_size < avail) {
3950			/*
3951			 * With sequential allocator, free space is always
3952			 * contiguous
3953			 */
3954			ffe_ctl->max_extent_size = avail;
3955			ffe_ctl->total_free_space = avail;
3956		}
3957		ret = 1;
3958		goto out;
3959	}
3960
3961	if (ffe_ctl->for_treelog && !fs_info->treelog_bg)
3962		fs_info->treelog_bg = block_group->start;
3963
3964	if (ffe_ctl->for_data_reloc) {
3965		if (!fs_info->data_reloc_bg)
3966			fs_info->data_reloc_bg = block_group->start;
3967		/*
3968		 * Do not allow allocations from this block group, unless it is
3969		 * for data relocation. Compared to increasing the ->ro, setting
3970		 * the ->zoned_data_reloc_ongoing flag still allows nocow
3971		 * writers to come in. See btrfs_inc_nocow_writers().
3972		 *
3973		 * We need to disable an allocation to avoid an allocation of
3974		 * regular (non-relocation data) extent. With mix of relocation
3975		 * extents and regular extents, we can dispatch WRITE commands
3976		 * (for relocation extents) and ZONE APPEND commands (for
3977		 * regular extents) at the same time to the same zone, which
3978		 * easily break the write pointer.
3979		 *
3980		 * Also, this flag avoids this block group to be zone finished.
3981		 */
3982		set_bit(BLOCK_GROUP_FLAG_ZONED_DATA_RELOC, &block_group->runtime_flags);
3983	}
3984
3985	ffe_ctl->found_offset = start + block_group->alloc_offset;
3986	block_group->alloc_offset += num_bytes;
3987	spin_lock(&ctl->tree_lock);
3988	ctl->free_space -= num_bytes;
3989	spin_unlock(&ctl->tree_lock);
3990
3991	/*
3992	 * We do not check if found_offset is aligned to stripesize. The
3993	 * address is anyway rewritten when using zone append writing.
3994	 */
3995
3996	ffe_ctl->search_start = ffe_ctl->found_offset;
3997
3998out:
3999	if (ret && ffe_ctl->for_treelog)
4000		fs_info->treelog_bg = 0;
4001	if (ret && ffe_ctl->for_data_reloc)
4002		fs_info->data_reloc_bg = 0;
4003	spin_unlock(&fs_info->relocation_bg_lock);
4004	spin_unlock(&fs_info->treelog_bg_lock);
4005	spin_unlock(&block_group->lock);
4006	spin_unlock(&space_info->lock);
4007	return ret;
4008}
4009
4010static int do_allocation(struct btrfs_block_group *block_group,
4011			 struct find_free_extent_ctl *ffe_ctl,
4012			 struct btrfs_block_group **bg_ret)
4013{
4014	switch (ffe_ctl->policy) {
4015	case BTRFS_EXTENT_ALLOC_CLUSTERED:
4016		return do_allocation_clustered(block_group, ffe_ctl, bg_ret);
4017	case BTRFS_EXTENT_ALLOC_ZONED:
4018		return do_allocation_zoned(block_group, ffe_ctl, bg_ret);
4019	default:
4020		BUG();
4021	}
4022}
4023
4024static void release_block_group(struct btrfs_block_group *block_group,
4025				struct find_free_extent_ctl *ffe_ctl,
4026				int delalloc)
4027{
4028	switch (ffe_ctl->policy) {
4029	case BTRFS_EXTENT_ALLOC_CLUSTERED:
4030		ffe_ctl->retry_uncached = false;
4031		break;
4032	case BTRFS_EXTENT_ALLOC_ZONED:
4033		/* Nothing to do */
4034		break;
4035	default:
4036		BUG();
4037	}
4038
4039	BUG_ON(btrfs_bg_flags_to_raid_index(block_group->flags) !=
4040	       ffe_ctl->index);
4041	btrfs_release_block_group(block_group, delalloc);
4042}
4043
4044static void found_extent_clustered(struct find_free_extent_ctl *ffe_ctl,
4045				   struct btrfs_key *ins)
4046{
4047	struct btrfs_free_cluster *last_ptr = ffe_ctl->last_ptr;
4048
4049	if (!ffe_ctl->use_cluster && last_ptr) {
4050		spin_lock(&last_ptr->lock);
4051		last_ptr->window_start = ins->objectid;
4052		spin_unlock(&last_ptr->lock);
4053	}
4054}
4055
4056static void found_extent(struct find_free_extent_ctl *ffe_ctl,
4057			 struct btrfs_key *ins)
4058{
4059	switch (ffe_ctl->policy) {
4060	case BTRFS_EXTENT_ALLOC_CLUSTERED:
4061		found_extent_clustered(ffe_ctl, ins);
4062		break;
4063	case BTRFS_EXTENT_ALLOC_ZONED:
4064		/* Nothing to do */
4065		break;
4066	default:
4067		BUG();
4068	}
4069}
4070
4071static int can_allocate_chunk_zoned(struct btrfs_fs_info *fs_info,
4072				    struct find_free_extent_ctl *ffe_ctl)
4073{
4074	/* Block group's activeness is not a requirement for METADATA block groups. */
4075	if (!(ffe_ctl->flags & BTRFS_BLOCK_GROUP_DATA))
4076		return 0;
4077
4078	/* If we can activate new zone, just allocate a chunk and use it */
4079	if (btrfs_can_activate_zone(fs_info->fs_devices, ffe_ctl->flags))
4080		return 0;
4081
4082	/*
4083	 * We already reached the max active zones. Try to finish one block
4084	 * group to make a room for a new block group. This is only possible
4085	 * for a data block group because btrfs_zone_finish() may need to wait
4086	 * for a running transaction which can cause a deadlock for metadata
4087	 * allocation.
4088	 */
4089	if (ffe_ctl->flags & BTRFS_BLOCK_GROUP_DATA) {
4090		int ret = btrfs_zone_finish_one_bg(fs_info);
4091
4092		if (ret == 1)
4093			return 0;
4094		else if (ret < 0)
4095			return ret;
4096	}
4097
4098	/*
4099	 * If we have enough free space left in an already active block group
4100	 * and we can't activate any other zone now, do not allow allocating a
4101	 * new chunk and let find_free_extent() retry with a smaller size.
4102	 */
4103	if (ffe_ctl->max_extent_size >= ffe_ctl->min_alloc_size)
4104		return -ENOSPC;
4105
4106	/*
4107	 * Even min_alloc_size is not left in any block groups. Since we cannot
4108	 * activate a new block group, allocating it may not help. Let's tell a
4109	 * caller to try again and hope it progress something by writing some
4110	 * parts of the region. That is only possible for data block groups,
4111	 * where a part of the region can be written.
4112	 */
4113	if (ffe_ctl->flags & BTRFS_BLOCK_GROUP_DATA)
4114		return -EAGAIN;
4115
4116	/*
4117	 * We cannot activate a new block group and no enough space left in any
4118	 * block groups. So, allocating a new block group may not help. But,
4119	 * there is nothing to do anyway, so let's go with it.
4120	 */
4121	return 0;
4122}
4123
4124static int can_allocate_chunk(struct btrfs_fs_info *fs_info,
4125			      struct find_free_extent_ctl *ffe_ctl)
4126{
4127	switch (ffe_ctl->policy) {
4128	case BTRFS_EXTENT_ALLOC_CLUSTERED:
4129		return 0;
4130	case BTRFS_EXTENT_ALLOC_ZONED:
4131		return can_allocate_chunk_zoned(fs_info, ffe_ctl);
4132	default:
4133		BUG();
4134	}
4135}
4136
4137/*
4138 * Return >0 means caller needs to re-search for free extent
4139 * Return 0 means we have the needed free extent.
4140 * Return <0 means we failed to locate any free extent.
4141 */
4142static int find_free_extent_update_loop(struct btrfs_fs_info *fs_info,
4143					struct btrfs_key *ins,
4144					struct find_free_extent_ctl *ffe_ctl,
4145					bool full_search)
4146{
4147	struct btrfs_root *root = fs_info->chunk_root;
4148	int ret;
4149
4150	if ((ffe_ctl->loop == LOOP_CACHING_NOWAIT) &&
4151	    ffe_ctl->have_caching_bg && !ffe_ctl->orig_have_caching_bg)
4152		ffe_ctl->orig_have_caching_bg = true;
4153
4154	if (ins->objectid) {
4155		found_extent(ffe_ctl, ins);
4156		return 0;
4157	}
4158
4159	if (ffe_ctl->loop >= LOOP_CACHING_WAIT && ffe_ctl->have_caching_bg)
4160		return 1;
4161
4162	ffe_ctl->index++;
4163	if (ffe_ctl->index < BTRFS_NR_RAID_TYPES)
4164		return 1;
4165
4166	/* See the comments for btrfs_loop_type for an explanation of the phases. */
4167	if (ffe_ctl->loop < LOOP_NO_EMPTY_SIZE) {
4168		ffe_ctl->index = 0;
4169		/*
4170		 * We want to skip the LOOP_CACHING_WAIT step if we don't have
4171		 * any uncached bgs and we've already done a full search
4172		 * through.
4173		 */
4174		if (ffe_ctl->loop == LOOP_CACHING_NOWAIT &&
4175		    (!ffe_ctl->orig_have_caching_bg && full_search))
4176			ffe_ctl->loop++;
4177		ffe_ctl->loop++;
4178
4179		if (ffe_ctl->loop == LOOP_ALLOC_CHUNK) {
4180			struct btrfs_trans_handle *trans;
4181			int exist = 0;
4182
4183			/* Check if allocation policy allows to create a new chunk */
4184			ret = can_allocate_chunk(fs_info, ffe_ctl);
4185			if (ret)
4186				return ret;
4187
4188			trans = current->journal_info;
4189			if (trans)
4190				exist = 1;
4191			else
4192				trans = btrfs_join_transaction(root);
4193
4194			if (IS_ERR(trans)) {
4195				ret = PTR_ERR(trans);
4196				return ret;
4197			}
4198
4199			ret = btrfs_chunk_alloc(trans, ffe_ctl->flags,
4200						CHUNK_ALLOC_FORCE_FOR_EXTENT);
4201
4202			/* Do not bail out on ENOSPC since we can do more. */
4203			if (ret == -ENOSPC) {
4204				ret = 0;
4205				ffe_ctl->loop++;
4206			}
4207			else if (ret < 0)
4208				btrfs_abort_transaction(trans, ret);
4209			else
4210				ret = 0;
4211			if (!exist)
4212				btrfs_end_transaction(trans);
4213			if (ret)
4214				return ret;
4215		}
4216
4217		if (ffe_ctl->loop == LOOP_NO_EMPTY_SIZE) {
4218			if (ffe_ctl->policy != BTRFS_EXTENT_ALLOC_CLUSTERED)
4219				return -ENOSPC;
4220
4221			/*
4222			 * Don't loop again if we already have no empty_size and
4223			 * no empty_cluster.
4224			 */
4225			if (ffe_ctl->empty_size == 0 &&
4226			    ffe_ctl->empty_cluster == 0)
4227				return -ENOSPC;
4228			ffe_ctl->empty_size = 0;
4229			ffe_ctl->empty_cluster = 0;
4230		}
4231		return 1;
4232	}
4233	return -ENOSPC;
4234}
4235
4236static bool find_free_extent_check_size_class(struct find_free_extent_ctl *ffe_ctl,
4237					      struct btrfs_block_group *bg)
4238{
4239	if (ffe_ctl->policy == BTRFS_EXTENT_ALLOC_ZONED)
4240		return true;
4241	if (!btrfs_block_group_should_use_size_class(bg))
4242		return true;
4243	if (ffe_ctl->loop >= LOOP_WRONG_SIZE_CLASS)
4244		return true;
4245	if (ffe_ctl->loop >= LOOP_UNSET_SIZE_CLASS &&
4246	    bg->size_class == BTRFS_BG_SZ_NONE)
4247		return true;
4248	return ffe_ctl->size_class == bg->size_class;
4249}
4250
4251static int prepare_allocation_clustered(struct btrfs_fs_info *fs_info,
4252					struct find_free_extent_ctl *ffe_ctl,
4253					struct btrfs_space_info *space_info,
4254					struct btrfs_key *ins)
4255{
4256	/*
4257	 * If our free space is heavily fragmented we may not be able to make
4258	 * big contiguous allocations, so instead of doing the expensive search
4259	 * for free space, simply return ENOSPC with our max_extent_size so we
4260	 * can go ahead and search for a more manageable chunk.
4261	 *
4262	 * If our max_extent_size is large enough for our allocation simply
4263	 * disable clustering since we will likely not be able to find enough
4264	 * space to create a cluster and induce latency trying.
4265	 */
4266	if (space_info->max_extent_size) {
4267		spin_lock(&space_info->lock);
4268		if (space_info->max_extent_size &&
4269		    ffe_ctl->num_bytes > space_info->max_extent_size) {
4270			ins->offset = space_info->max_extent_size;
4271			spin_unlock(&space_info->lock);
4272			return -ENOSPC;
4273		} else if (space_info->max_extent_size) {
4274			ffe_ctl->use_cluster = false;
4275		}
4276		spin_unlock(&space_info->lock);
4277	}
4278
4279	ffe_ctl->last_ptr = fetch_cluster_info(fs_info, space_info,
4280					       &ffe_ctl->empty_cluster);
4281	if (ffe_ctl->last_ptr) {
4282		struct btrfs_free_cluster *last_ptr = ffe_ctl->last_ptr;
4283
4284		spin_lock(&last_ptr->lock);
4285		if (last_ptr->block_group)
4286			ffe_ctl->hint_byte = last_ptr->window_start;
4287		if (last_ptr->fragmented) {
4288			/*
4289			 * We still set window_start so we can keep track of the
4290			 * last place we found an allocation to try and save
4291			 * some time.
4292			 */
4293			ffe_ctl->hint_byte = last_ptr->window_start;
4294			ffe_ctl->use_cluster = false;
4295		}
4296		spin_unlock(&last_ptr->lock);
4297	}
4298
4299	return 0;
4300}
4301
4302static int prepare_allocation_zoned(struct btrfs_fs_info *fs_info,
4303				    struct find_free_extent_ctl *ffe_ctl)
4304{
4305	if (ffe_ctl->for_treelog) {
4306		spin_lock(&fs_info->treelog_bg_lock);
4307		if (fs_info->treelog_bg)
4308			ffe_ctl->hint_byte = fs_info->treelog_bg;
4309		spin_unlock(&fs_info->treelog_bg_lock);
4310	} else if (ffe_ctl->for_data_reloc) {
4311		spin_lock(&fs_info->relocation_bg_lock);
4312		if (fs_info->data_reloc_bg)
4313			ffe_ctl->hint_byte = fs_info->data_reloc_bg;
4314		spin_unlock(&fs_info->relocation_bg_lock);
4315	} else if (ffe_ctl->flags & BTRFS_BLOCK_GROUP_DATA) {
4316		struct btrfs_block_group *block_group;
4317
4318		spin_lock(&fs_info->zone_active_bgs_lock);
4319		list_for_each_entry(block_group, &fs_info->zone_active_bgs, active_bg_list) {
4320			/*
4321			 * No lock is OK here because avail is monotinically
4322			 * decreasing, and this is just a hint.
4323			 */
4324			u64 avail = block_group->zone_capacity - block_group->alloc_offset;
4325
4326			if (block_group_bits(block_group, ffe_ctl->flags) &&
4327			    avail >= ffe_ctl->num_bytes) {
4328				ffe_ctl->hint_byte = block_group->start;
4329				break;
4330			}
4331		}
4332		spin_unlock(&fs_info->zone_active_bgs_lock);
4333	}
4334
4335	return 0;
4336}
4337
4338static int prepare_allocation(struct btrfs_fs_info *fs_info,
4339			      struct find_free_extent_ctl *ffe_ctl,
4340			      struct btrfs_space_info *space_info,
4341			      struct btrfs_key *ins)
4342{
4343	switch (ffe_ctl->policy) {
4344	case BTRFS_EXTENT_ALLOC_CLUSTERED:
4345		return prepare_allocation_clustered(fs_info, ffe_ctl,
4346						    space_info, ins);
4347	case BTRFS_EXTENT_ALLOC_ZONED:
4348		return prepare_allocation_zoned(fs_info, ffe_ctl);
4349	default:
4350		BUG();
4351	}
4352}
4353
4354/*
4355 * walks the btree of allocated extents and find a hole of a given size.
4356 * The key ins is changed to record the hole:
4357 * ins->objectid == start position
4358 * ins->flags = BTRFS_EXTENT_ITEM_KEY
4359 * ins->offset == the size of the hole.
4360 * Any available blocks before search_start are skipped.
4361 *
4362 * If there is no suitable free space, we will record the max size of
4363 * the free space extent currently.
4364 *
4365 * The overall logic and call chain:
4366 *
4367 * find_free_extent()
4368 * |- Iterate through all block groups
4369 * |  |- Get a valid block group
4370 * |  |- Try to do clustered allocation in that block group
4371 * |  |- Try to do unclustered allocation in that block group
4372 * |  |- Check if the result is valid
4373 * |  |  |- If valid, then exit
4374 * |  |- Jump to next block group
4375 * |
4376 * |- Push harder to find free extents
4377 *    |- If not found, re-iterate all block groups
4378 */
4379static noinline int find_free_extent(struct btrfs_root *root,
4380				     struct btrfs_key *ins,
4381				     struct find_free_extent_ctl *ffe_ctl)
4382{
4383	struct btrfs_fs_info *fs_info = root->fs_info;
4384	int ret = 0;
4385	int cache_block_group_error = 0;
4386	struct btrfs_block_group *block_group = NULL;
4387	struct btrfs_space_info *space_info;
4388	bool full_search = false;
4389
4390	WARN_ON(ffe_ctl->num_bytes < fs_info->sectorsize);
4391
4392	ffe_ctl->search_start = 0;
4393	/* For clustered allocation */
4394	ffe_ctl->empty_cluster = 0;
4395	ffe_ctl->last_ptr = NULL;
4396	ffe_ctl->use_cluster = true;
4397	ffe_ctl->have_caching_bg = false;
4398	ffe_ctl->orig_have_caching_bg = false;
4399	ffe_ctl->index = btrfs_bg_flags_to_raid_index(ffe_ctl->flags);
4400	ffe_ctl->loop = 0;
4401	ffe_ctl->retry_uncached = false;
4402	ffe_ctl->cached = 0;
4403	ffe_ctl->max_extent_size = 0;
4404	ffe_ctl->total_free_space = 0;
4405	ffe_ctl->found_offset = 0;
4406	ffe_ctl->policy = BTRFS_EXTENT_ALLOC_CLUSTERED;
4407	ffe_ctl->size_class = btrfs_calc_block_group_size_class(ffe_ctl->num_bytes);
4408
4409	if (btrfs_is_zoned(fs_info))
4410		ffe_ctl->policy = BTRFS_EXTENT_ALLOC_ZONED;
4411
4412	ins->type = BTRFS_EXTENT_ITEM_KEY;
4413	ins->objectid = 0;
4414	ins->offset = 0;
4415
4416	trace_find_free_extent(root, ffe_ctl);
4417
4418	space_info = btrfs_find_space_info(fs_info, ffe_ctl->flags);
4419	if (!space_info) {
4420		btrfs_err(fs_info, "No space info for %llu", ffe_ctl->flags);
4421		return -ENOSPC;
4422	}
4423
4424	ret = prepare_allocation(fs_info, ffe_ctl, space_info, ins);
4425	if (ret < 0)
4426		return ret;
4427
4428	ffe_ctl->search_start = max(ffe_ctl->search_start,
4429				    first_logical_byte(fs_info));
4430	ffe_ctl->search_start = max(ffe_ctl->search_start, ffe_ctl->hint_byte);
4431	if (ffe_ctl->search_start == ffe_ctl->hint_byte) {
4432		block_group = btrfs_lookup_block_group(fs_info,
4433						       ffe_ctl->search_start);
4434		/*
4435		 * we don't want to use the block group if it doesn't match our
4436		 * allocation bits, or if its not cached.
4437		 *
4438		 * However if we are re-searching with an ideal block group
4439		 * picked out then we don't care that the block group is cached.
4440		 */
4441		if (block_group && block_group_bits(block_group, ffe_ctl->flags) &&
4442		    block_group->cached != BTRFS_CACHE_NO) {
4443			down_read(&space_info->groups_sem);
4444			if (list_empty(&block_group->list) ||
4445			    block_group->ro) {
4446				/*
4447				 * someone is removing this block group,
4448				 * we can't jump into the have_block_group
4449				 * target because our list pointers are not
4450				 * valid
4451				 */
4452				btrfs_put_block_group(block_group);
4453				up_read(&space_info->groups_sem);
4454			} else {
4455				ffe_ctl->index = btrfs_bg_flags_to_raid_index(
4456							block_group->flags);
4457				btrfs_lock_block_group(block_group,
4458						       ffe_ctl->delalloc);
4459				ffe_ctl->hinted = true;
4460				goto have_block_group;
4461			}
4462		} else if (block_group) {
4463			btrfs_put_block_group(block_group);
4464		}
4465	}
4466search:
4467	trace_find_free_extent_search_loop(root, ffe_ctl);
4468	ffe_ctl->have_caching_bg = false;
4469	if (ffe_ctl->index == btrfs_bg_flags_to_raid_index(ffe_ctl->flags) ||
4470	    ffe_ctl->index == 0)
4471		full_search = true;
4472	down_read(&space_info->groups_sem);
4473	list_for_each_entry(block_group,
4474			    &space_info->block_groups[ffe_ctl->index], list) {
4475		struct btrfs_block_group *bg_ret;
4476
4477		ffe_ctl->hinted = false;
4478		/* If the block group is read-only, we can skip it entirely. */
4479		if (unlikely(block_group->ro)) {
4480			if (ffe_ctl->for_treelog)
4481				btrfs_clear_treelog_bg(block_group);
4482			if (ffe_ctl->for_data_reloc)
4483				btrfs_clear_data_reloc_bg(block_group);
4484			continue;
4485		}
4486
4487		btrfs_grab_block_group(block_group, ffe_ctl->delalloc);
4488		ffe_ctl->search_start = block_group->start;
4489
4490		/*
4491		 * this can happen if we end up cycling through all the
4492		 * raid types, but we want to make sure we only allocate
4493		 * for the proper type.
4494		 */
4495		if (!block_group_bits(block_group, ffe_ctl->flags)) {
4496			u64 extra = BTRFS_BLOCK_GROUP_DUP |
4497				BTRFS_BLOCK_GROUP_RAID1_MASK |
4498				BTRFS_BLOCK_GROUP_RAID56_MASK |
4499				BTRFS_BLOCK_GROUP_RAID10;
4500
4501			/*
4502			 * if they asked for extra copies and this block group
4503			 * doesn't provide them, bail.  This does allow us to
4504			 * fill raid0 from raid1.
4505			 */
4506			if ((ffe_ctl->flags & extra) && !(block_group->flags & extra))
4507				goto loop;
4508
4509			/*
4510			 * This block group has different flags than we want.
4511			 * It's possible that we have MIXED_GROUP flag but no
4512			 * block group is mixed.  Just skip such block group.
4513			 */
4514			btrfs_release_block_group(block_group, ffe_ctl->delalloc);
4515			continue;
4516		}
4517
4518have_block_group:
4519		trace_find_free_extent_have_block_group(root, ffe_ctl, block_group);
4520		ffe_ctl->cached = btrfs_block_group_done(block_group);
4521		if (unlikely(!ffe_ctl->cached)) {
4522			ffe_ctl->have_caching_bg = true;
4523			ret = btrfs_cache_block_group(block_group, false);
4524
4525			/*
4526			 * If we get ENOMEM here or something else we want to
4527			 * try other block groups, because it may not be fatal.
4528			 * However if we can't find anything else we need to
4529			 * save our return here so that we return the actual
4530			 * error that caused problems, not ENOSPC.
4531			 */
4532			if (ret < 0) {
4533				if (!cache_block_group_error)
4534					cache_block_group_error = ret;
4535				ret = 0;
4536				goto loop;
4537			}
4538			ret = 0;
4539		}
4540
4541		if (unlikely(block_group->cached == BTRFS_CACHE_ERROR)) {
4542			if (!cache_block_group_error)
4543				cache_block_group_error = -EIO;
4544			goto loop;
4545		}
4546
4547		if (!find_free_extent_check_size_class(ffe_ctl, block_group))
4548			goto loop;
4549
4550		bg_ret = NULL;
4551		ret = do_allocation(block_group, ffe_ctl, &bg_ret);
4552		if (ret > 0)
4553			goto loop;
4554
4555		if (bg_ret && bg_ret != block_group) {
4556			btrfs_release_block_group(block_group, ffe_ctl->delalloc);
4557			block_group = bg_ret;
4558		}
4559
4560		/* Checks */
4561		ffe_ctl->search_start = round_up(ffe_ctl->found_offset,
4562						 fs_info->stripesize);
4563
4564		/* move on to the next group */
4565		if (ffe_ctl->search_start + ffe_ctl->num_bytes >
4566		    block_group->start + block_group->length) {
4567			btrfs_add_free_space_unused(block_group,
4568					    ffe_ctl->found_offset,
4569					    ffe_ctl->num_bytes);
4570			goto loop;
4571		}
4572
4573		if (ffe_ctl->found_offset < ffe_ctl->search_start)
4574			btrfs_add_free_space_unused(block_group,
4575					ffe_ctl->found_offset,
4576					ffe_ctl->search_start - ffe_ctl->found_offset);
4577
4578		ret = btrfs_add_reserved_bytes(block_group, ffe_ctl->ram_bytes,
4579					       ffe_ctl->num_bytes,
4580					       ffe_ctl->delalloc,
4581					       ffe_ctl->loop >= LOOP_WRONG_SIZE_CLASS);
4582		if (ret == -EAGAIN) {
4583			btrfs_add_free_space_unused(block_group,
4584					ffe_ctl->found_offset,
4585					ffe_ctl->num_bytes);
4586			goto loop;
4587		}
4588		btrfs_inc_block_group_reservations(block_group);
4589
4590		/* we are all good, lets return */
4591		ins->objectid = ffe_ctl->search_start;
4592		ins->offset = ffe_ctl->num_bytes;
4593
4594		trace_btrfs_reserve_extent(block_group, ffe_ctl);
4595		btrfs_release_block_group(block_group, ffe_ctl->delalloc);
4596		break;
4597loop:
4598		if (!ffe_ctl->cached && ffe_ctl->loop > LOOP_CACHING_NOWAIT &&
4599		    !ffe_ctl->retry_uncached) {
4600			ffe_ctl->retry_uncached = true;
4601			btrfs_wait_block_group_cache_progress(block_group,
4602						ffe_ctl->num_bytes +
4603						ffe_ctl->empty_cluster +
4604						ffe_ctl->empty_size);
4605			goto have_block_group;
4606		}
4607		release_block_group(block_group, ffe_ctl, ffe_ctl->delalloc);
4608		cond_resched();
4609	}
4610	up_read(&space_info->groups_sem);
4611
4612	ret = find_free_extent_update_loop(fs_info, ins, ffe_ctl, full_search);
4613	if (ret > 0)
4614		goto search;
4615
4616	if (ret == -ENOSPC && !cache_block_group_error) {
4617		/*
4618		 * Use ffe_ctl->total_free_space as fallback if we can't find
4619		 * any contiguous hole.
4620		 */
4621		if (!ffe_ctl->max_extent_size)
4622			ffe_ctl->max_extent_size = ffe_ctl->total_free_space;
4623		spin_lock(&space_info->lock);
4624		space_info->max_extent_size = ffe_ctl->max_extent_size;
4625		spin_unlock(&space_info->lock);
4626		ins->offset = ffe_ctl->max_extent_size;
4627	} else if (ret == -ENOSPC) {
4628		ret = cache_block_group_error;
4629	}
4630	return ret;
4631}
4632
4633/*
4634 * Entry point to the extent allocator. Tries to find a hole that is at least
4635 * as big as @num_bytes.
4636 *
4637 * @root           -	The root that will contain this extent
4638 *
4639 * @ram_bytes      -	The amount of space in ram that @num_bytes take. This
4640 *			is used for accounting purposes. This value differs
4641 *			from @num_bytes only in the case of compressed extents.
4642 *
4643 * @num_bytes      -	Number of bytes to allocate on-disk.
4644 *
4645 * @min_alloc_size -	Indicates the minimum amount of space that the
4646 *			allocator should try to satisfy. In some cases
4647 *			@num_bytes may be larger than what is required and if
4648 *			the filesystem is fragmented then allocation fails.
4649 *			However, the presence of @min_alloc_size gives a
4650 *			chance to try and satisfy the smaller allocation.
4651 *
4652 * @empty_size     -	A hint that you plan on doing more COW. This is the
4653 *			size in bytes the allocator should try to find free
4654 *			next to the block it returns.  This is just a hint and
4655 *			may be ignored by the allocator.
4656 *
4657 * @hint_byte      -	Hint to the allocator to start searching above the byte
4658 *			address passed. It might be ignored.
4659 *
4660 * @ins            -	This key is modified to record the found hole. It will
4661 *			have the following values:
4662 *			ins->objectid == start position
4663 *			ins->flags = BTRFS_EXTENT_ITEM_KEY
4664 *			ins->offset == the size of the hole.
4665 *
4666 * @is_data        -	Boolean flag indicating whether an extent is
4667 *			allocated for data (true) or metadata (false)
4668 *
4669 * @delalloc       -	Boolean flag indicating whether this allocation is for
4670 *			delalloc or not. If 'true' data_rwsem of block groups
4671 *			is going to be acquired.
4672 *
4673 *
4674 * Returns 0 when an allocation succeeded or < 0 when an error occurred. In
4675 * case -ENOSPC is returned then @ins->offset will contain the size of the
4676 * largest available hole the allocator managed to find.
4677 */
4678int btrfs_reserve_extent(struct btrfs_root *root, u64 ram_bytes,
4679			 u64 num_bytes, u64 min_alloc_size,
4680			 u64 empty_size, u64 hint_byte,
4681			 struct btrfs_key *ins, int is_data, int delalloc)
4682{
4683	struct btrfs_fs_info *fs_info = root->fs_info;
4684	struct find_free_extent_ctl ffe_ctl = {};
4685	bool final_tried = num_bytes == min_alloc_size;
4686	u64 flags;
4687	int ret;
4688	bool for_treelog = (root->root_key.objectid == BTRFS_TREE_LOG_OBJECTID);
4689	bool for_data_reloc = (btrfs_is_data_reloc_root(root) && is_data);
4690
4691	flags = get_alloc_profile_by_root(root, is_data);
4692again:
4693	WARN_ON(num_bytes < fs_info->sectorsize);
4694
4695	ffe_ctl.ram_bytes = ram_bytes;
4696	ffe_ctl.num_bytes = num_bytes;
4697	ffe_ctl.min_alloc_size = min_alloc_size;
4698	ffe_ctl.empty_size = empty_size;
4699	ffe_ctl.flags = flags;
4700	ffe_ctl.delalloc = delalloc;
4701	ffe_ctl.hint_byte = hint_byte;
4702	ffe_ctl.for_treelog = for_treelog;
4703	ffe_ctl.for_data_reloc = for_data_reloc;
4704
4705	ret = find_free_extent(root, ins, &ffe_ctl);
4706	if (!ret && !is_data) {
4707		btrfs_dec_block_group_reservations(fs_info, ins->objectid);
4708	} else if (ret == -ENOSPC) {
4709		if (!final_tried && ins->offset) {
4710			num_bytes = min(num_bytes >> 1, ins->offset);
4711			num_bytes = round_down(num_bytes,
4712					       fs_info->sectorsize);
4713			num_bytes = max(num_bytes, min_alloc_size);
4714			ram_bytes = num_bytes;
4715			if (num_bytes == min_alloc_size)
4716				final_tried = true;
4717			goto again;
4718		} else if (btrfs_test_opt(fs_info, ENOSPC_DEBUG)) {
4719			struct btrfs_space_info *sinfo;
4720
4721			sinfo = btrfs_find_space_info(fs_info, flags);
4722			btrfs_err(fs_info,
4723	"allocation failed flags %llu, wanted %llu tree-log %d, relocation: %d",
4724				  flags, num_bytes, for_treelog, for_data_reloc);
4725			if (sinfo)
4726				btrfs_dump_space_info(fs_info, sinfo,
4727						      num_bytes, 1);
4728		}
4729	}
4730
4731	return ret;
4732}
4733
4734int btrfs_free_reserved_extent(struct btrfs_fs_info *fs_info,
4735			       u64 start, u64 len, int delalloc)
4736{
4737	struct btrfs_block_group *cache;
4738
4739	cache = btrfs_lookup_block_group(fs_info, start);
4740	if (!cache) {
4741		btrfs_err(fs_info, "Unable to find block group for %llu",
4742			  start);
4743		return -ENOSPC;
4744	}
4745
4746	btrfs_add_free_space(cache, start, len);
4747	btrfs_free_reserved_bytes(cache, len, delalloc);
4748	trace_btrfs_reserved_extent_free(fs_info, start, len);
4749
4750	btrfs_put_block_group(cache);
4751	return 0;
4752}
4753
4754int btrfs_pin_reserved_extent(struct btrfs_trans_handle *trans,
4755			      const struct extent_buffer *eb)
4756{
4757	struct btrfs_block_group *cache;
4758	int ret = 0;
4759
4760	cache = btrfs_lookup_block_group(trans->fs_info, eb->start);
4761	if (!cache) {
4762		btrfs_err(trans->fs_info, "unable to find block group for %llu",
4763			  eb->start);
4764		return -ENOSPC;
4765	}
4766
4767	ret = pin_down_extent(trans, cache, eb->start, eb->len, 1);
4768	btrfs_put_block_group(cache);
4769	return ret;
4770}
4771
4772static int alloc_reserved_extent(struct btrfs_trans_handle *trans, u64 bytenr,
4773				 u64 num_bytes)
4774{
4775	struct btrfs_fs_info *fs_info = trans->fs_info;
4776	int ret;
4777
4778	ret = remove_from_free_space_tree(trans, bytenr, num_bytes);
4779	if (ret)
4780		return ret;
4781
4782	ret = btrfs_update_block_group(trans, bytenr, num_bytes, true);
4783	if (ret) {
4784		ASSERT(!ret);
4785		btrfs_err(fs_info, "update block group failed for %llu %llu",
4786			  bytenr, num_bytes);
4787		return ret;
4788	}
4789
4790	trace_btrfs_reserved_extent_alloc(fs_info, bytenr, num_bytes);
4791	return 0;
4792}
4793
4794static int alloc_reserved_file_extent(struct btrfs_trans_handle *trans,
4795				      u64 parent, u64 root_objectid,
4796				      u64 flags, u64 owner, u64 offset,
4797				      struct btrfs_key *ins, int ref_mod, u64 oref_root)
4798{
4799	struct btrfs_fs_info *fs_info = trans->fs_info;
4800	struct btrfs_root *extent_root;
4801	int ret;
4802	struct btrfs_extent_item *extent_item;
4803	struct btrfs_extent_owner_ref *oref;
4804	struct btrfs_extent_inline_ref *iref;
4805	struct btrfs_path *path;
4806	struct extent_buffer *leaf;
4807	int type;
4808	u32 size;
4809	const bool simple_quota = (btrfs_qgroup_mode(fs_info) == BTRFS_QGROUP_MODE_SIMPLE);
4810
4811	if (parent > 0)
4812		type = BTRFS_SHARED_DATA_REF_KEY;
4813	else
4814		type = BTRFS_EXTENT_DATA_REF_KEY;
4815
4816	size = sizeof(*extent_item);
4817	if (simple_quota)
4818		size += btrfs_extent_inline_ref_size(BTRFS_EXTENT_OWNER_REF_KEY);
4819	size += btrfs_extent_inline_ref_size(type);
4820
4821	path = btrfs_alloc_path();
4822	if (!path)
4823		return -ENOMEM;
4824
4825	extent_root = btrfs_extent_root(fs_info, ins->objectid);
4826	ret = btrfs_insert_empty_item(trans, extent_root, path, ins, size);
4827	if (ret) {
4828		btrfs_free_path(path);
4829		return ret;
4830	}
4831
4832	leaf = path->nodes[0];
4833	extent_item = btrfs_item_ptr(leaf, path->slots[0],
4834				     struct btrfs_extent_item);
4835	btrfs_set_extent_refs(leaf, extent_item, ref_mod);
4836	btrfs_set_extent_generation(leaf, extent_item, trans->transid);
4837	btrfs_set_extent_flags(leaf, extent_item,
4838			       flags | BTRFS_EXTENT_FLAG_DATA);
4839
4840	iref = (struct btrfs_extent_inline_ref *)(extent_item + 1);
4841	if (simple_quota) {
4842		btrfs_set_extent_inline_ref_type(leaf, iref, BTRFS_EXTENT_OWNER_REF_KEY);
4843		oref = (struct btrfs_extent_owner_ref *)(&iref->offset);
4844		btrfs_set_extent_owner_ref_root_id(leaf, oref, oref_root);
4845		iref = (struct btrfs_extent_inline_ref *)(oref + 1);
4846	}
4847	btrfs_set_extent_inline_ref_type(leaf, iref, type);
4848
4849	if (parent > 0) {
4850		struct btrfs_shared_data_ref *ref;
4851		ref = (struct btrfs_shared_data_ref *)(iref + 1);
4852		btrfs_set_extent_inline_ref_offset(leaf, iref, parent);
4853		btrfs_set_shared_data_ref_count(leaf, ref, ref_mod);
4854	} else {
4855		struct btrfs_extent_data_ref *ref;
4856		ref = (struct btrfs_extent_data_ref *)(&iref->offset);
4857		btrfs_set_extent_data_ref_root(leaf, ref, root_objectid);
4858		btrfs_set_extent_data_ref_objectid(leaf, ref, owner);
4859		btrfs_set_extent_data_ref_offset(leaf, ref, offset);
4860		btrfs_set_extent_data_ref_count(leaf, ref, ref_mod);
4861	}
4862
4863	btrfs_mark_buffer_dirty(trans, path->nodes[0]);
4864	btrfs_free_path(path);
4865
4866	return alloc_reserved_extent(trans, ins->objectid, ins->offset);
4867}
4868
4869static int alloc_reserved_tree_block(struct btrfs_trans_handle *trans,
4870				     struct btrfs_delayed_ref_node *node,
4871				     struct btrfs_delayed_extent_op *extent_op)
4872{
4873	struct btrfs_fs_info *fs_info = trans->fs_info;
4874	struct btrfs_root *extent_root;
4875	int ret;
4876	struct btrfs_extent_item *extent_item;
4877	struct btrfs_key extent_key;
4878	struct btrfs_tree_block_info *block_info;
4879	struct btrfs_extent_inline_ref *iref;
4880	struct btrfs_path *path;
4881	struct extent_buffer *leaf;
4882	struct btrfs_delayed_tree_ref *ref;
4883	u32 size = sizeof(*extent_item) + sizeof(*iref);
4884	u64 flags = extent_op->flags_to_set;
4885	bool skinny_metadata = btrfs_fs_incompat(fs_info, SKINNY_METADATA);
4886
4887	ref = btrfs_delayed_node_to_tree_ref(node);
4888
4889	extent_key.objectid = node->bytenr;
4890	if (skinny_metadata) {
4891		extent_key.offset = ref->level;
4892		extent_key.type = BTRFS_METADATA_ITEM_KEY;
4893	} else {
4894		extent_key.offset = node->num_bytes;
4895		extent_key.type = BTRFS_EXTENT_ITEM_KEY;
4896		size += sizeof(*block_info);
4897	}
4898
4899	path = btrfs_alloc_path();
4900	if (!path)
4901		return -ENOMEM;
4902
4903	extent_root = btrfs_extent_root(fs_info, extent_key.objectid);
4904	ret = btrfs_insert_empty_item(trans, extent_root, path, &extent_key,
4905				      size);
4906	if (ret) {
4907		btrfs_free_path(path);
4908		return ret;
4909	}
4910
4911	leaf = path->nodes[0];
4912	extent_item = btrfs_item_ptr(leaf, path->slots[0],
4913				     struct btrfs_extent_item);
4914	btrfs_set_extent_refs(leaf, extent_item, 1);
4915	btrfs_set_extent_generation(leaf, extent_item, trans->transid);
4916	btrfs_set_extent_flags(leaf, extent_item,
4917			       flags | BTRFS_EXTENT_FLAG_TREE_BLOCK);
4918
4919	if (skinny_metadata) {
4920		iref = (struct btrfs_extent_inline_ref *)(extent_item + 1);
4921	} else {
4922		block_info = (struct btrfs_tree_block_info *)(extent_item + 1);
4923		btrfs_set_tree_block_key(leaf, block_info, &extent_op->key);
4924		btrfs_set_tree_block_level(leaf, block_info, ref->level);
4925		iref = (struct btrfs_extent_inline_ref *)(block_info + 1);
4926	}
4927
4928	if (node->type == BTRFS_SHARED_BLOCK_REF_KEY) {
4929		btrfs_set_extent_inline_ref_type(leaf, iref,
4930						 BTRFS_SHARED_BLOCK_REF_KEY);
4931		btrfs_set_extent_inline_ref_offset(leaf, iref, ref->parent);
4932	} else {
4933		btrfs_set_extent_inline_ref_type(leaf, iref,
4934						 BTRFS_TREE_BLOCK_REF_KEY);
4935		btrfs_set_extent_inline_ref_offset(leaf, iref, ref->root);
4936	}
4937
4938	btrfs_mark_buffer_dirty(trans, leaf);
4939	btrfs_free_path(path);
4940
4941	return alloc_reserved_extent(trans, node->bytenr, fs_info->nodesize);
4942}
4943
4944int btrfs_alloc_reserved_file_extent(struct btrfs_trans_handle *trans,
4945				     struct btrfs_root *root, u64 owner,
4946				     u64 offset, u64 ram_bytes,
4947				     struct btrfs_key *ins)
4948{
4949	struct btrfs_ref generic_ref = { 0 };
4950	u64 root_objectid = root->root_key.objectid;
4951	u64 owning_root = root_objectid;
4952
4953	BUG_ON(root_objectid == BTRFS_TREE_LOG_OBJECTID);
4954
4955	if (btrfs_is_data_reloc_root(root) && is_fstree(root->relocation_src_root))
4956		owning_root = root->relocation_src_root;
4957
4958	btrfs_init_generic_ref(&generic_ref, BTRFS_ADD_DELAYED_EXTENT,
4959			       ins->objectid, ins->offset, 0, owning_root);
4960	btrfs_init_data_ref(&generic_ref, root_objectid, owner,
4961			    offset, 0, false);
4962	btrfs_ref_tree_mod(root->fs_info, &generic_ref);
4963
4964	return btrfs_add_delayed_data_ref(trans, &generic_ref, ram_bytes);
4965}
4966
4967/*
4968 * this is used by the tree logging recovery code.  It records that
4969 * an extent has been allocated and makes sure to clear the free
4970 * space cache bits as well
4971 */
4972int btrfs_alloc_logged_file_extent(struct btrfs_trans_handle *trans,
4973				   u64 root_objectid, u64 owner, u64 offset,
4974				   struct btrfs_key *ins)
4975{
4976	struct btrfs_fs_info *fs_info = trans->fs_info;
4977	int ret;
4978	struct btrfs_block_group *block_group;
4979	struct btrfs_space_info *space_info;
4980	struct btrfs_squota_delta delta = {
4981		.root = root_objectid,
4982		.num_bytes = ins->offset,
4983		.generation = trans->transid,
4984		.is_data = true,
4985		.is_inc = true,
4986	};
4987
4988	/*
4989	 * Mixed block groups will exclude before processing the log so we only
4990	 * need to do the exclude dance if this fs isn't mixed.
4991	 */
4992	if (!btrfs_fs_incompat(fs_info, MIXED_GROUPS)) {
4993		ret = __exclude_logged_extent(fs_info, ins->objectid,
4994					      ins->offset);
4995		if (ret)
4996			return ret;
4997	}
4998
4999	block_group = btrfs_lookup_block_group(fs_info, ins->objectid);
5000	if (!block_group)
5001		return -EINVAL;
5002
5003	space_info = block_group->space_info;
5004	spin_lock(&space_info->lock);
5005	spin_lock(&block_group->lock);
5006	space_info->bytes_reserved += ins->offset;
5007	block_group->reserved += ins->offset;
5008	spin_unlock(&block_group->lock);
5009	spin_unlock(&space_info->lock);
5010
5011	ret = alloc_reserved_file_extent(trans, 0, root_objectid, 0, owner,
5012					 offset, ins, 1, root_objectid);
5013	if (ret)
5014		btrfs_pin_extent(trans, ins->objectid, ins->offset, 1);
5015	ret = btrfs_record_squota_delta(fs_info, &delta);
5016	btrfs_put_block_group(block_group);
5017	return ret;
5018}
5019
5020#ifdef CONFIG_BTRFS_DEBUG
5021/*
5022 * Extra safety check in case the extent tree is corrupted and extent allocator
5023 * chooses to use a tree block which is already used and locked.
5024 */
5025static bool check_eb_lock_owner(const struct extent_buffer *eb)
5026{
5027	if (eb->lock_owner == current->pid) {
5028		btrfs_err_rl(eb->fs_info,
5029"tree block %llu owner %llu already locked by pid=%d, extent tree corruption detected",
5030			     eb->start, btrfs_header_owner(eb), current->pid);
5031		return true;
5032	}
5033	return false;
5034}
5035#else
5036static bool check_eb_lock_owner(struct extent_buffer *eb)
5037{
5038	return false;
5039}
5040#endif
5041
5042static struct extent_buffer *
5043btrfs_init_new_buffer(struct btrfs_trans_handle *trans, struct btrfs_root *root,
5044		      u64 bytenr, int level, u64 owner,
5045		      enum btrfs_lock_nesting nest)
5046{
5047	struct btrfs_fs_info *fs_info = root->fs_info;
5048	struct extent_buffer *buf;
5049	u64 lockdep_owner = owner;
5050
5051	buf = btrfs_find_create_tree_block(fs_info, bytenr, owner, level);
5052	if (IS_ERR(buf))
5053		return buf;
5054
5055	if (check_eb_lock_owner(buf)) {
5056		free_extent_buffer(buf);
5057		return ERR_PTR(-EUCLEAN);
5058	}
5059
5060	/*
5061	 * The reloc trees are just snapshots, so we need them to appear to be
5062	 * just like any other fs tree WRT lockdep.
5063	 *
5064	 * The exception however is in replace_path() in relocation, where we
5065	 * hold the lock on the original fs root and then search for the reloc
5066	 * root.  At that point we need to make sure any reloc root buffers are
5067	 * set to the BTRFS_TREE_RELOC_OBJECTID lockdep class in order to make
5068	 * lockdep happy.
5069	 */
5070	if (lockdep_owner == BTRFS_TREE_RELOC_OBJECTID &&
5071	    !test_bit(BTRFS_ROOT_RESET_LOCKDEP_CLASS, &root->state))
5072		lockdep_owner = BTRFS_FS_TREE_OBJECTID;
5073
5074	/* btrfs_clear_buffer_dirty() accesses generation field. */
5075	btrfs_set_header_generation(buf, trans->transid);
5076
5077	/*
5078	 * This needs to stay, because we could allocate a freed block from an
5079	 * old tree into a new tree, so we need to make sure this new block is
5080	 * set to the appropriate level and owner.
5081	 */
5082	btrfs_set_buffer_lockdep_class(lockdep_owner, buf, level);
5083
5084	__btrfs_tree_lock(buf, nest);
5085	btrfs_clear_buffer_dirty(trans, buf);
5086	clear_bit(EXTENT_BUFFER_STALE, &buf->bflags);
5087	clear_bit(EXTENT_BUFFER_ZONED_ZEROOUT, &buf->bflags);
5088
5089	set_extent_buffer_uptodate(buf);
5090
5091	memzero_extent_buffer(buf, 0, sizeof(struct btrfs_header));
5092	btrfs_set_header_level(buf, level);
5093	btrfs_set_header_bytenr(buf, buf->start);
5094	btrfs_set_header_generation(buf, trans->transid);
5095	btrfs_set_header_backref_rev(buf, BTRFS_MIXED_BACKREF_REV);
5096	btrfs_set_header_owner(buf, owner);
5097	write_extent_buffer_fsid(buf, fs_info->fs_devices->metadata_uuid);
5098	write_extent_buffer_chunk_tree_uuid(buf, fs_info->chunk_tree_uuid);
5099	if (root->root_key.objectid == BTRFS_TREE_LOG_OBJECTID) {
5100		buf->log_index = root->log_transid % 2;
5101		/*
5102		 * we allow two log transactions at a time, use different
5103		 * EXTENT bit to differentiate dirty pages.
5104		 */
5105		if (buf->log_index == 0)
5106			set_extent_bit(&root->dirty_log_pages, buf->start,
5107				       buf->start + buf->len - 1,
5108				       EXTENT_DIRTY, NULL);
5109		else
5110			set_extent_bit(&root->dirty_log_pages, buf->start,
5111				       buf->start + buf->len - 1,
5112				       EXTENT_NEW, NULL);
5113	} else {
5114		buf->log_index = -1;
5115		set_extent_bit(&trans->transaction->dirty_pages, buf->start,
5116			       buf->start + buf->len - 1, EXTENT_DIRTY, NULL);
5117	}
5118	/* this returns a buffer locked for blocking */
5119	return buf;
5120}
5121
5122/*
5123 * finds a free extent and does all the dirty work required for allocation
5124 * returns the tree buffer or an ERR_PTR on error.
5125 */
5126struct extent_buffer *btrfs_alloc_tree_block(struct btrfs_trans_handle *trans,
5127					     struct btrfs_root *root,
5128					     u64 parent, u64 root_objectid,
5129					     const struct btrfs_disk_key *key,
5130					     int level, u64 hint,
5131					     u64 empty_size,
5132					     u64 reloc_src_root,
5133					     enum btrfs_lock_nesting nest)
5134{
5135	struct btrfs_fs_info *fs_info = root->fs_info;
5136	struct btrfs_key ins;
5137	struct btrfs_block_rsv *block_rsv;
5138	struct extent_buffer *buf;
5139	struct btrfs_delayed_extent_op *extent_op;
5140	struct btrfs_ref generic_ref = { 0 };
5141	u64 flags = 0;
5142	int ret;
5143	u32 blocksize = fs_info->nodesize;
5144	bool skinny_metadata = btrfs_fs_incompat(fs_info, SKINNY_METADATA);
5145	u64 owning_root;
5146
5147#ifdef CONFIG_BTRFS_FS_RUN_SANITY_TESTS
5148	if (btrfs_is_testing(fs_info)) {
5149		buf = btrfs_init_new_buffer(trans, root, root->alloc_bytenr,
5150					    level, root_objectid, nest);
5151		if (!IS_ERR(buf))
5152			root->alloc_bytenr += blocksize;
5153		return buf;
5154	}
5155#endif
5156
5157	block_rsv = btrfs_use_block_rsv(trans, root, blocksize);
5158	if (IS_ERR(block_rsv))
5159		return ERR_CAST(block_rsv);
5160
5161	ret = btrfs_reserve_extent(root, blocksize, blocksize, blocksize,
5162				   empty_size, hint, &ins, 0, 0);
5163	if (ret)
5164		goto out_unuse;
5165
5166	buf = btrfs_init_new_buffer(trans, root, ins.objectid, level,
5167				    root_objectid, nest);
5168	if (IS_ERR(buf)) {
5169		ret = PTR_ERR(buf);
5170		goto out_free_reserved;
5171	}
5172	owning_root = btrfs_header_owner(buf);
5173
5174	if (root_objectid == BTRFS_TREE_RELOC_OBJECTID) {
5175		if (parent == 0)
5176			parent = ins.objectid;
5177		flags |= BTRFS_BLOCK_FLAG_FULL_BACKREF;
5178		owning_root = reloc_src_root;
5179	} else
5180		BUG_ON(parent > 0);
5181
5182	if (root_objectid != BTRFS_TREE_LOG_OBJECTID) {
5183		extent_op = btrfs_alloc_delayed_extent_op();
5184		if (!extent_op) {
5185			ret = -ENOMEM;
5186			goto out_free_buf;
5187		}
5188		if (key)
5189			memcpy(&extent_op->key, key, sizeof(extent_op->key));
5190		else
5191			memset(&extent_op->key, 0, sizeof(extent_op->key));
5192		extent_op->flags_to_set = flags;
5193		extent_op->update_key = skinny_metadata ? false : true;
5194		extent_op->update_flags = true;
5195		extent_op->level = level;
5196
5197		btrfs_init_generic_ref(&generic_ref, BTRFS_ADD_DELAYED_EXTENT,
5198				       ins.objectid, ins.offset, parent, owning_root);
5199		btrfs_init_tree_ref(&generic_ref, level, root_objectid,
5200				    root->root_key.objectid, false);
5201		btrfs_ref_tree_mod(fs_info, &generic_ref);
5202		ret = btrfs_add_delayed_tree_ref(trans, &generic_ref, extent_op);
5203		if (ret)
5204			goto out_free_delayed;
5205	}
5206	return buf;
5207
5208out_free_delayed:
5209	btrfs_free_delayed_extent_op(extent_op);
5210out_free_buf:
5211	btrfs_tree_unlock(buf);
5212	free_extent_buffer(buf);
5213out_free_reserved:
5214	btrfs_free_reserved_extent(fs_info, ins.objectid, ins.offset, 0);
5215out_unuse:
5216	btrfs_unuse_block_rsv(fs_info, block_rsv, blocksize);
5217	return ERR_PTR(ret);
5218}
5219
5220struct walk_control {
5221	u64 refs[BTRFS_MAX_LEVEL];
5222	u64 flags[BTRFS_MAX_LEVEL];
5223	struct btrfs_key update_progress;
5224	struct btrfs_key drop_progress;
5225	int drop_level;
5226	int stage;
5227	int level;
5228	int shared_level;
5229	int update_ref;
5230	int keep_locks;
5231	int reada_slot;
5232	int reada_count;
5233	int restarted;
5234};
5235
5236#define DROP_REFERENCE	1
5237#define UPDATE_BACKREF	2
5238
5239static noinline void reada_walk_down(struct btrfs_trans_handle *trans,
5240				     struct btrfs_root *root,
5241				     struct walk_control *wc,
5242				     struct btrfs_path *path)
5243{
5244	struct btrfs_fs_info *fs_info = root->fs_info;
5245	u64 bytenr;
5246	u64 generation;
5247	u64 refs;
5248	u64 flags;
5249	u32 nritems;
5250	struct btrfs_key key;
5251	struct extent_buffer *eb;
5252	int ret;
5253	int slot;
5254	int nread = 0;
5255
5256	if (path->slots[wc->level] < wc->reada_slot) {
5257		wc->reada_count = wc->reada_count * 2 / 3;
5258		wc->reada_count = max(wc->reada_count, 2);
5259	} else {
5260		wc->reada_count = wc->reada_count * 3 / 2;
5261		wc->reada_count = min_t(int, wc->reada_count,
5262					BTRFS_NODEPTRS_PER_BLOCK(fs_info));
5263	}
5264
5265	eb = path->nodes[wc->level];
5266	nritems = btrfs_header_nritems(eb);
5267
5268	for (slot = path->slots[wc->level]; slot < nritems; slot++) {
5269		if (nread >= wc->reada_count)
5270			break;
5271
5272		cond_resched();
5273		bytenr = btrfs_node_blockptr(eb, slot);
5274		generation = btrfs_node_ptr_generation(eb, slot);
5275
5276		if (slot == path->slots[wc->level])
5277			goto reada;
5278
5279		if (wc->stage == UPDATE_BACKREF &&
5280		    generation <= root->root_key.offset)
5281			continue;
5282
5283		/* We don't lock the tree block, it's OK to be racy here */
5284		ret = btrfs_lookup_extent_info(trans, fs_info, bytenr,
5285					       wc->level - 1, 1, &refs,
5286					       &flags, NULL);
5287		/* We don't care about errors in readahead. */
5288		if (ret < 0)
5289			continue;
5290		BUG_ON(refs == 0);
5291
5292		if (wc->stage == DROP_REFERENCE) {
5293			if (refs == 1)
5294				goto reada;
5295
5296			if (wc->level == 1 &&
5297			    (flags & BTRFS_BLOCK_FLAG_FULL_BACKREF))
5298				continue;
5299			if (!wc->update_ref ||
5300			    generation <= root->root_key.offset)
5301				continue;
5302			btrfs_node_key_to_cpu(eb, &key, slot);
5303			ret = btrfs_comp_cpu_keys(&key,
5304						  &wc->update_progress);
5305			if (ret < 0)
5306				continue;
5307		} else {
5308			if (wc->level == 1 &&
5309			    (flags & BTRFS_BLOCK_FLAG_FULL_BACKREF))
5310				continue;
5311		}
5312reada:
5313		btrfs_readahead_node_child(eb, slot);
5314		nread++;
5315	}
5316	wc->reada_slot = slot;
5317}
5318
5319/*
5320 * helper to process tree block while walking down the tree.
5321 *
5322 * when wc->stage == UPDATE_BACKREF, this function updates
5323 * back refs for pointers in the block.
5324 *
5325 * NOTE: return value 1 means we should stop walking down.
5326 */
5327static noinline int walk_down_proc(struct btrfs_trans_handle *trans,
5328				   struct btrfs_root *root,
5329				   struct btrfs_path *path,
5330				   struct walk_control *wc, int lookup_info)
5331{
5332	struct btrfs_fs_info *fs_info = root->fs_info;
5333	int level = wc->level;
5334	struct extent_buffer *eb = path->nodes[level];
5335	u64 flag = BTRFS_BLOCK_FLAG_FULL_BACKREF;
5336	int ret;
5337
5338	if (wc->stage == UPDATE_BACKREF &&
5339	    btrfs_header_owner(eb) != root->root_key.objectid)
5340		return 1;
5341
5342	/*
5343	 * when reference count of tree block is 1, it won't increase
5344	 * again. once full backref flag is set, we never clear it.
5345	 */
5346	if (lookup_info &&
5347	    ((wc->stage == DROP_REFERENCE && wc->refs[level] != 1) ||
5348	     (wc->stage == UPDATE_BACKREF && !(wc->flags[level] & flag)))) {
5349		BUG_ON(!path->locks[level]);
5350		ret = btrfs_lookup_extent_info(trans, fs_info,
5351					       eb->start, level, 1,
5352					       &wc->refs[level],
5353					       &wc->flags[level],
5354					       NULL);
5355		BUG_ON(ret == -ENOMEM);
5356		if (ret)
5357			return ret;
5358		BUG_ON(wc->refs[level] == 0);
5359	}
5360
5361	if (wc->stage == DROP_REFERENCE) {
5362		if (wc->refs[level] > 1)
5363			return 1;
5364
5365		if (path->locks[level] && !wc->keep_locks) {
5366			btrfs_tree_unlock_rw(eb, path->locks[level]);
5367			path->locks[level] = 0;
5368		}
5369		return 0;
5370	}
5371
5372	/* wc->stage == UPDATE_BACKREF */
5373	if (!(wc->flags[level] & flag)) {
5374		BUG_ON(!path->locks[level]);
5375		ret = btrfs_inc_ref(trans, root, eb, 1);
5376		BUG_ON(ret); /* -ENOMEM */
5377		ret = btrfs_dec_ref(trans, root, eb, 0);
5378		BUG_ON(ret); /* -ENOMEM */
5379		ret = btrfs_set_disk_extent_flags(trans, eb, flag);
5380		BUG_ON(ret); /* -ENOMEM */
5381		wc->flags[level] |= flag;
5382	}
5383
5384	/*
5385	 * the block is shared by multiple trees, so it's not good to
5386	 * keep the tree lock
5387	 */
5388	if (path->locks[level] && level > 0) {
5389		btrfs_tree_unlock_rw(eb, path->locks[level]);
5390		path->locks[level] = 0;
5391	}
5392	return 0;
5393}
5394
5395/*
5396 * This is used to verify a ref exists for this root to deal with a bug where we
5397 * would have a drop_progress key that hadn't been updated properly.
5398 */
5399static int check_ref_exists(struct btrfs_trans_handle *trans,
5400			    struct btrfs_root *root, u64 bytenr, u64 parent,
5401			    int level)
5402{
5403	struct btrfs_path *path;
5404	struct btrfs_extent_inline_ref *iref;
5405	int ret;
5406
5407	path = btrfs_alloc_path();
5408	if (!path)
5409		return -ENOMEM;
5410
5411	ret = lookup_extent_backref(trans, path, &iref, bytenr,
5412				    root->fs_info->nodesize, parent,
5413				    root->root_key.objectid, level, 0);
5414	btrfs_free_path(path);
5415	if (ret == -ENOENT)
5416		return 0;
5417	if (ret < 0)
5418		return ret;
5419	return 1;
5420}
5421
5422/*
5423 * helper to process tree block pointer.
5424 *
5425 * when wc->stage == DROP_REFERENCE, this function checks
5426 * reference count of the block pointed to. if the block
5427 * is shared and we need update back refs for the subtree
5428 * rooted at the block, this function changes wc->stage to
5429 * UPDATE_BACKREF. if the block is shared and there is no
5430 * need to update back, this function drops the reference
5431 * to the block.
5432 *
5433 * NOTE: return value 1 means we should stop walking down.
5434 */
5435static noinline int do_walk_down(struct btrfs_trans_handle *trans,
5436				 struct btrfs_root *root,
5437				 struct btrfs_path *path,
5438				 struct walk_control *wc, int *lookup_info)
5439{
5440	struct btrfs_fs_info *fs_info = root->fs_info;
5441	u64 bytenr;
5442	u64 generation;
5443	u64 parent;
5444	u64 owner_root = 0;
5445	struct btrfs_tree_parent_check check = { 0 };
5446	struct btrfs_key key;
5447	struct btrfs_ref ref = { 0 };
5448	struct extent_buffer *next;
5449	int level = wc->level;
5450	int reada = 0;
5451	int ret = 0;
5452	bool need_account = false;
5453
5454	generation = btrfs_node_ptr_generation(path->nodes[level],
5455					       path->slots[level]);
5456	/*
5457	 * if the lower level block was created before the snapshot
5458	 * was created, we know there is no need to update back refs
5459	 * for the subtree
5460	 */
5461	if (wc->stage == UPDATE_BACKREF &&
5462	    generation <= root->root_key.offset) {
5463		*lookup_info = 1;
5464		return 1;
5465	}
5466
5467	bytenr = btrfs_node_blockptr(path->nodes[level], path->slots[level]);
5468
5469	check.level = level - 1;
5470	check.transid = generation;
5471	check.owner_root = root->root_key.objectid;
5472	check.has_first_key = true;
5473	btrfs_node_key_to_cpu(path->nodes[level], &check.first_key,
5474			      path->slots[level]);
5475
5476	next = find_extent_buffer(fs_info, bytenr);
5477	if (!next) {
5478		next = btrfs_find_create_tree_block(fs_info, bytenr,
5479				root->root_key.objectid, level - 1);
5480		if (IS_ERR(next))
5481			return PTR_ERR(next);
5482		reada = 1;
5483	}
5484	btrfs_tree_lock(next);
5485
5486	ret = btrfs_lookup_extent_info(trans, fs_info, bytenr, level - 1, 1,
5487				       &wc->refs[level - 1],
5488				       &wc->flags[level - 1],
5489				       &owner_root);
5490	if (ret < 0)
5491		goto out_unlock;
5492
5493	if (unlikely(wc->refs[level - 1] == 0)) {
5494		btrfs_err(fs_info, "Missing references.");
5495		ret = -EIO;
5496		goto out_unlock;
5497	}
5498	*lookup_info = 0;
5499
5500	if (wc->stage == DROP_REFERENCE) {
5501		if (wc->refs[level - 1] > 1) {
5502			need_account = true;
5503			if (level == 1 &&
5504			    (wc->flags[0] & BTRFS_BLOCK_FLAG_FULL_BACKREF))
5505				goto skip;
5506
5507			if (!wc->update_ref ||
5508			    generation <= root->root_key.offset)
5509				goto skip;
5510
5511			btrfs_node_key_to_cpu(path->nodes[level], &key,
5512					      path->slots[level]);
5513			ret = btrfs_comp_cpu_keys(&key, &wc->update_progress);
5514			if (ret < 0)
5515				goto skip;
5516
5517			wc->stage = UPDATE_BACKREF;
5518			wc->shared_level = level - 1;
5519		}
5520	} else {
5521		if (level == 1 &&
5522		    (wc->flags[0] & BTRFS_BLOCK_FLAG_FULL_BACKREF))
5523			goto skip;
5524	}
5525
5526	if (!btrfs_buffer_uptodate(next, generation, 0)) {
5527		btrfs_tree_unlock(next);
5528		free_extent_buffer(next);
5529		next = NULL;
5530		*lookup_info = 1;
5531	}
5532
5533	if (!next) {
5534		if (reada && level == 1)
5535			reada_walk_down(trans, root, wc, path);
5536		next = read_tree_block(fs_info, bytenr, &check);
5537		if (IS_ERR(next)) {
5538			return PTR_ERR(next);
5539		} else if (!extent_buffer_uptodate(next)) {
5540			free_extent_buffer(next);
5541			return -EIO;
5542		}
5543		btrfs_tree_lock(next);
5544	}
5545
5546	level--;
5547	ASSERT(level == btrfs_header_level(next));
5548	if (level != btrfs_header_level(next)) {
5549		btrfs_err(root->fs_info, "mismatched level");
5550		ret = -EIO;
5551		goto out_unlock;
5552	}
5553	path->nodes[level] = next;
5554	path->slots[level] = 0;
5555	path->locks[level] = BTRFS_WRITE_LOCK;
5556	wc->level = level;
5557	if (wc->level == 1)
5558		wc->reada_slot = 0;
5559	return 0;
5560skip:
5561	wc->refs[level - 1] = 0;
5562	wc->flags[level - 1] = 0;
5563	if (wc->stage == DROP_REFERENCE) {
5564		if (wc->flags[level] & BTRFS_BLOCK_FLAG_FULL_BACKREF) {
5565			parent = path->nodes[level]->start;
5566		} else {
5567			ASSERT(root->root_key.objectid ==
5568			       btrfs_header_owner(path->nodes[level]));
5569			if (root->root_key.objectid !=
5570			    btrfs_header_owner(path->nodes[level])) {
5571				btrfs_err(root->fs_info,
5572						"mismatched block owner");
5573				ret = -EIO;
5574				goto out_unlock;
5575			}
5576			parent = 0;
5577		}
5578
5579		/*
5580		 * If we had a drop_progress we need to verify the refs are set
5581		 * as expected.  If we find our ref then we know that from here
5582		 * on out everything should be correct, and we can clear the
5583		 * ->restarted flag.
5584		 */
5585		if (wc->restarted) {
5586			ret = check_ref_exists(trans, root, bytenr, parent,
5587					       level - 1);
5588			if (ret < 0)
5589				goto out_unlock;
5590			if (ret == 0)
5591				goto no_delete;
5592			ret = 0;
5593			wc->restarted = 0;
5594		}
5595
5596		/*
5597		 * Reloc tree doesn't contribute to qgroup numbers, and we have
5598		 * already accounted them at merge time (replace_path),
5599		 * thus we could skip expensive subtree trace here.
5600		 */
5601		if (root->root_key.objectid != BTRFS_TREE_RELOC_OBJECTID &&
5602		    need_account) {
5603			ret = btrfs_qgroup_trace_subtree(trans, next,
5604							 generation, level - 1);
5605			if (ret) {
5606				btrfs_err_rl(fs_info,
5607					     "Error %d accounting shared subtree. Quota is out of sync, rescan required.",
5608					     ret);
5609			}
5610		}
5611
5612		/*
5613		 * We need to update the next key in our walk control so we can
5614		 * update the drop_progress key accordingly.  We don't care if
5615		 * find_next_key doesn't find a key because that means we're at
5616		 * the end and are going to clean up now.
5617		 */
5618		wc->drop_level = level;
5619		find_next_key(path, level, &wc->drop_progress);
5620
5621		btrfs_init_generic_ref(&ref, BTRFS_DROP_DELAYED_REF, bytenr,
5622				       fs_info->nodesize, parent, owner_root);
5623		btrfs_init_tree_ref(&ref, level - 1, root->root_key.objectid,
5624				    0, false);
5625		ret = btrfs_free_extent(trans, &ref);
5626		if (ret)
5627			goto out_unlock;
5628	}
5629no_delete:
5630	*lookup_info = 1;
5631	ret = 1;
5632
5633out_unlock:
5634	btrfs_tree_unlock(next);
5635	free_extent_buffer(next);
5636
5637	return ret;
5638}
5639
5640/*
5641 * helper to process tree block while walking up the tree.
5642 *
5643 * when wc->stage == DROP_REFERENCE, this function drops
5644 * reference count on the block.
5645 *
5646 * when wc->stage == UPDATE_BACKREF, this function changes
5647 * wc->stage back to DROP_REFERENCE if we changed wc->stage
5648 * to UPDATE_BACKREF previously while processing the block.
5649 *
5650 * NOTE: return value 1 means we should stop walking up.
5651 */
5652static noinline int walk_up_proc(struct btrfs_trans_handle *trans,
5653				 struct btrfs_root *root,
5654				 struct btrfs_path *path,
5655				 struct walk_control *wc)
5656{
5657	struct btrfs_fs_info *fs_info = root->fs_info;
5658	int ret;
5659	int level = wc->level;
5660	struct extent_buffer *eb = path->nodes[level];
5661	u64 parent = 0;
5662
5663	if (wc->stage == UPDATE_BACKREF) {
5664		BUG_ON(wc->shared_level < level);
5665		if (level < wc->shared_level)
5666			goto out;
5667
5668		ret = find_next_key(path, level + 1, &wc->update_progress);
5669		if (ret > 0)
5670			wc->update_ref = 0;
5671
5672		wc->stage = DROP_REFERENCE;
5673		wc->shared_level = -1;
5674		path->slots[level] = 0;
5675
5676		/*
5677		 * check reference count again if the block isn't locked.
5678		 * we should start walking down the tree again if reference
5679		 * count is one.
5680		 */
5681		if (!path->locks[level]) {
5682			BUG_ON(level == 0);
5683			btrfs_tree_lock(eb);
5684			path->locks[level] = BTRFS_WRITE_LOCK;
5685
5686			ret = btrfs_lookup_extent_info(trans, fs_info,
5687						       eb->start, level, 1,
5688						       &wc->refs[level],
5689						       &wc->flags[level],
5690						       NULL);
5691			if (ret < 0) {
5692				btrfs_tree_unlock_rw(eb, path->locks[level]);
5693				path->locks[level] = 0;
5694				return ret;
5695			}
5696			BUG_ON(wc->refs[level] == 0);
5697			if (wc->refs[level] == 1) {
5698				btrfs_tree_unlock_rw(eb, path->locks[level]);
5699				path->locks[level] = 0;
5700				return 1;
5701			}
5702		}
5703	}
5704
5705	/* wc->stage == DROP_REFERENCE */
5706	BUG_ON(wc->refs[level] > 1 && !path->locks[level]);
5707
5708	if (wc->refs[level] == 1) {
5709		if (level == 0) {
5710			if (wc->flags[level] & BTRFS_BLOCK_FLAG_FULL_BACKREF)
5711				ret = btrfs_dec_ref(trans, root, eb, 1);
5712			else
5713				ret = btrfs_dec_ref(trans, root, eb, 0);
5714			BUG_ON(ret); /* -ENOMEM */
5715			if (is_fstree(root->root_key.objectid)) {
5716				ret = btrfs_qgroup_trace_leaf_items(trans, eb);
5717				if (ret) {
5718					btrfs_err_rl(fs_info,
5719	"error %d accounting leaf items, quota is out of sync, rescan required",
5720					     ret);
5721				}
5722			}
5723		}
5724		/* Make block locked assertion in btrfs_clear_buffer_dirty happy. */
5725		if (!path->locks[level]) {
5726			btrfs_tree_lock(eb);
5727			path->locks[level] = BTRFS_WRITE_LOCK;
5728		}
5729		btrfs_clear_buffer_dirty(trans, eb);
5730	}
5731
5732	if (eb == root->node) {
5733		if (wc->flags[level] & BTRFS_BLOCK_FLAG_FULL_BACKREF)
5734			parent = eb->start;
5735		else if (root->root_key.objectid != btrfs_header_owner(eb))
5736			goto owner_mismatch;
5737	} else {
5738		if (wc->flags[level + 1] & BTRFS_BLOCK_FLAG_FULL_BACKREF)
5739			parent = path->nodes[level + 1]->start;
5740		else if (root->root_key.objectid !=
5741			 btrfs_header_owner(path->nodes[level + 1]))
5742			goto owner_mismatch;
5743	}
5744
5745	btrfs_free_tree_block(trans, btrfs_root_id(root), eb, parent,
5746			      wc->refs[level] == 1);
5747out:
5748	wc->refs[level] = 0;
5749	wc->flags[level] = 0;
5750	return 0;
5751
5752owner_mismatch:
5753	btrfs_err_rl(fs_info, "unexpected tree owner, have %llu expect %llu",
5754		     btrfs_header_owner(eb), root->root_key.objectid);
5755	return -EUCLEAN;
5756}
5757
5758static noinline int walk_down_tree(struct btrfs_trans_handle *trans,
5759				   struct btrfs_root *root,
5760				   struct btrfs_path *path,
5761				   struct walk_control *wc)
5762{
5763	int level = wc->level;
5764	int lookup_info = 1;
5765	int ret = 0;
5766
5767	while (level >= 0) {
5768		ret = walk_down_proc(trans, root, path, wc, lookup_info);
5769		if (ret)
5770			break;
5771
5772		if (level == 0)
5773			break;
5774
5775		if (path->slots[level] >=
5776		    btrfs_header_nritems(path->nodes[level]))
5777			break;
5778
5779		ret = do_walk_down(trans, root, path, wc, &lookup_info);
5780		if (ret > 0) {
5781			path->slots[level]++;
5782			continue;
5783		} else if (ret < 0)
5784			break;
5785		level = wc->level;
5786	}
5787	return (ret == 1) ? 0 : ret;
5788}
5789
5790static noinline int walk_up_tree(struct btrfs_trans_handle *trans,
5791				 struct btrfs_root *root,
5792				 struct btrfs_path *path,
5793				 struct walk_control *wc, int max_level)
5794{
5795	int level = wc->level;
5796	int ret;
5797
5798	path->slots[level] = btrfs_header_nritems(path->nodes[level]);
5799	while (level < max_level && path->nodes[level]) {
5800		wc->level = level;
5801		if (path->slots[level] + 1 <
5802		    btrfs_header_nritems(path->nodes[level])) {
5803			path->slots[level]++;
5804			return 0;
5805		} else {
5806			ret = walk_up_proc(trans, root, path, wc);
5807			if (ret > 0)
5808				return 0;
5809			if (ret < 0)
5810				return ret;
5811
5812			if (path->locks[level]) {
5813				btrfs_tree_unlock_rw(path->nodes[level],
5814						     path->locks[level]);
5815				path->locks[level] = 0;
5816			}
5817			free_extent_buffer(path->nodes[level]);
5818			path->nodes[level] = NULL;
5819			level++;
5820		}
5821	}
5822	return 1;
5823}
5824
5825/*
5826 * drop a subvolume tree.
5827 *
5828 * this function traverses the tree freeing any blocks that only
5829 * referenced by the tree.
5830 *
5831 * when a shared tree block is found. this function decreases its
5832 * reference count by one. if update_ref is true, this function
5833 * also make sure backrefs for the shared block and all lower level
5834 * blocks are properly updated.
5835 *
5836 * If called with for_reloc == 0, may exit early with -EAGAIN
5837 */
5838int btrfs_drop_snapshot(struct btrfs_root *root, int update_ref, int for_reloc)
5839{
5840	const bool is_reloc_root = (root->root_key.objectid ==
5841				    BTRFS_TREE_RELOC_OBJECTID);
5842	struct btrfs_fs_info *fs_info = root->fs_info;
5843	struct btrfs_path *path;
5844	struct btrfs_trans_handle *trans;
5845	struct btrfs_root *tree_root = fs_info->tree_root;
5846	struct btrfs_root_item *root_item = &root->root_item;
5847	struct walk_control *wc;
5848	struct btrfs_key key;
5849	int err = 0;
5850	int ret;
5851	int level;
5852	bool root_dropped = false;
5853	bool unfinished_drop = false;
5854
5855	btrfs_debug(fs_info, "Drop subvolume %llu", root->root_key.objectid);
5856
5857	path = btrfs_alloc_path();
5858	if (!path) {
5859		err = -ENOMEM;
5860		goto out;
5861	}
5862
5863	wc = kzalloc(sizeof(*wc), GFP_NOFS);
5864	if (!wc) {
5865		btrfs_free_path(path);
5866		err = -ENOMEM;
5867		goto out;
5868	}
5869
5870	/*
5871	 * Use join to avoid potential EINTR from transaction start. See
5872	 * wait_reserve_ticket and the whole reservation callchain.
5873	 */
5874	if (for_reloc)
5875		trans = btrfs_join_transaction(tree_root);
5876	else
5877		trans = btrfs_start_transaction(tree_root, 0);
5878	if (IS_ERR(trans)) {
5879		err = PTR_ERR(trans);
5880		goto out_free;
5881	}
5882
5883	err = btrfs_run_delayed_items(trans);
5884	if (err)
5885		goto out_end_trans;
5886
5887	/*
5888	 * This will help us catch people modifying the fs tree while we're
5889	 * dropping it.  It is unsafe to mess with the fs tree while it's being
5890	 * dropped as we unlock the root node and parent nodes as we walk down
5891	 * the tree, assuming nothing will change.  If something does change
5892	 * then we'll have stale information and drop references to blocks we've
5893	 * already dropped.
5894	 */
5895	set_bit(BTRFS_ROOT_DELETING, &root->state);
5896	unfinished_drop = test_bit(BTRFS_ROOT_UNFINISHED_DROP, &root->state);
5897
5898	if (btrfs_disk_key_objectid(&root_item->drop_progress) == 0) {
5899		level = btrfs_header_level(root->node);
5900		path->nodes[level] = btrfs_lock_root_node(root);
5901		path->slots[level] = 0;
5902		path->locks[level] = BTRFS_WRITE_LOCK;
5903		memset(&wc->update_progress, 0,
5904		       sizeof(wc->update_progress));
5905	} else {
5906		btrfs_disk_key_to_cpu(&key, &root_item->drop_progress);
5907		memcpy(&wc->update_progress, &key,
5908		       sizeof(wc->update_progress));
5909
5910		level = btrfs_root_drop_level(root_item);
5911		BUG_ON(level == 0);
5912		path->lowest_level = level;
5913		ret = btrfs_search_slot(NULL, root, &key, path, 0, 0);
5914		path->lowest_level = 0;
5915		if (ret < 0) {
5916			err = ret;
5917			goto out_end_trans;
5918		}
5919		WARN_ON(ret > 0);
5920
5921		/*
5922		 * unlock our path, this is safe because only this
5923		 * function is allowed to delete this snapshot
5924		 */
5925		btrfs_unlock_up_safe(path, 0);
5926
5927		level = btrfs_header_level(root->node);
5928		while (1) {
5929			btrfs_tree_lock(path->nodes[level]);
5930			path->locks[level] = BTRFS_WRITE_LOCK;
5931
5932			ret = btrfs_lookup_extent_info(trans, fs_info,
5933						path->nodes[level]->start,
5934						level, 1, &wc->refs[level],
5935						&wc->flags[level], NULL);
5936			if (ret < 0) {
5937				err = ret;
5938				goto out_end_trans;
5939			}
5940			BUG_ON(wc->refs[level] == 0);
5941
5942			if (level == btrfs_root_drop_level(root_item))
5943				break;
5944
5945			btrfs_tree_unlock(path->nodes[level]);
5946			path->locks[level] = 0;
5947			WARN_ON(wc->refs[level] != 1);
5948			level--;
5949		}
5950	}
5951
5952	wc->restarted = test_bit(BTRFS_ROOT_DEAD_TREE, &root->state);
5953	wc->level = level;
5954	wc->shared_level = -1;
5955	wc->stage = DROP_REFERENCE;
5956	wc->update_ref = update_ref;
5957	wc->keep_locks = 0;
5958	wc->reada_count = BTRFS_NODEPTRS_PER_BLOCK(fs_info);
5959
5960	while (1) {
5961
5962		ret = walk_down_tree(trans, root, path, wc);
5963		if (ret < 0) {
5964			btrfs_abort_transaction(trans, ret);
5965			err = ret;
5966			break;
5967		}
5968
5969		ret = walk_up_tree(trans, root, path, wc, BTRFS_MAX_LEVEL);
5970		if (ret < 0) {
5971			btrfs_abort_transaction(trans, ret);
5972			err = ret;
5973			break;
5974		}
5975
5976		if (ret > 0) {
5977			BUG_ON(wc->stage != DROP_REFERENCE);
5978			break;
5979		}
5980
5981		if (wc->stage == DROP_REFERENCE) {
5982			wc->drop_level = wc->level;
5983			btrfs_node_key_to_cpu(path->nodes[wc->drop_level],
5984					      &wc->drop_progress,
5985					      path->slots[wc->drop_level]);
5986		}
5987		btrfs_cpu_key_to_disk(&root_item->drop_progress,
5988				      &wc->drop_progress);
5989		btrfs_set_root_drop_level(root_item, wc->drop_level);
5990
5991		BUG_ON(wc->level == 0);
5992		if (btrfs_should_end_transaction(trans) ||
5993		    (!for_reloc && btrfs_need_cleaner_sleep(fs_info))) {
5994			ret = btrfs_update_root(trans, tree_root,
5995						&root->root_key,
5996						root_item);
5997			if (ret) {
5998				btrfs_abort_transaction(trans, ret);
5999				err = ret;
6000				goto out_end_trans;
6001			}
6002
6003			if (!is_reloc_root)
6004				btrfs_set_last_root_drop_gen(fs_info, trans->transid);
6005
6006			btrfs_end_transaction_throttle(trans);
6007			if (!for_reloc && btrfs_need_cleaner_sleep(fs_info)) {
6008				btrfs_debug(fs_info,
6009					    "drop snapshot early exit");
6010				err = -EAGAIN;
6011				goto out_free;
6012			}
6013
6014		       /*
6015			* Use join to avoid potential EINTR from transaction
6016			* start. See wait_reserve_ticket and the whole
6017			* reservation callchain.
6018			*/
6019			if (for_reloc)
6020				trans = btrfs_join_transaction(tree_root);
6021			else
6022				trans = btrfs_start_transaction(tree_root, 0);
6023			if (IS_ERR(trans)) {
6024				err = PTR_ERR(trans);
6025				goto out_free;
6026			}
6027		}
6028	}
6029	btrfs_release_path(path);
6030	if (err)
6031		goto out_end_trans;
6032
6033	ret = btrfs_del_root(trans, &root->root_key);
6034	if (ret) {
6035		btrfs_abort_transaction(trans, ret);
6036		err = ret;
6037		goto out_end_trans;
6038	}
6039
6040	if (!is_reloc_root) {
6041		ret = btrfs_find_root(tree_root, &root->root_key, path,
6042				      NULL, NULL);
6043		if (ret < 0) {
6044			btrfs_abort_transaction(trans, ret);
6045			err = ret;
6046			goto out_end_trans;
6047		} else if (ret > 0) {
6048			/* if we fail to delete the orphan item this time
6049			 * around, it'll get picked up the next time.
6050			 *
6051			 * The most common failure here is just -ENOENT.
6052			 */
6053			btrfs_del_orphan_item(trans, tree_root,
6054					      root->root_key.objectid);
6055		}
6056	}
6057
6058	/*
6059	 * This subvolume is going to be completely dropped, and won't be
6060	 * recorded as dirty roots, thus pertrans meta rsv will not be freed at
6061	 * commit transaction time.  So free it here manually.
6062	 */
6063	btrfs_qgroup_convert_reserved_meta(root, INT_MAX);
6064	btrfs_qgroup_free_meta_all_pertrans(root);
6065
6066	if (test_bit(BTRFS_ROOT_IN_RADIX, &root->state))
6067		btrfs_add_dropped_root(trans, root);
6068	else
6069		btrfs_put_root(root);
6070	root_dropped = true;
6071out_end_trans:
6072	if (!is_reloc_root)
6073		btrfs_set_last_root_drop_gen(fs_info, trans->transid);
6074
6075	btrfs_end_transaction_throttle(trans);
6076out_free:
6077	kfree(wc);
6078	btrfs_free_path(path);
6079out:
6080	/*
6081	 * We were an unfinished drop root, check to see if there are any
6082	 * pending, and if not clear and wake up any waiters.
6083	 */
6084	if (!err && unfinished_drop)
6085		btrfs_maybe_wake_unfinished_drop(fs_info);
6086
6087	/*
6088	 * So if we need to stop dropping the snapshot for whatever reason we
6089	 * need to make sure to add it back to the dead root list so that we
6090	 * keep trying to do the work later.  This also cleans up roots if we
6091	 * don't have it in the radix (like when we recover after a power fail
6092	 * or unmount) so we don't leak memory.
6093	 */
6094	if (!for_reloc && !root_dropped)
6095		btrfs_add_dead_root(root);
6096	return err;
6097}
6098
6099/*
6100 * drop subtree rooted at tree block 'node'.
6101 *
6102 * NOTE: this function will unlock and release tree block 'node'
6103 * only used by relocation code
6104 */
6105int btrfs_drop_subtree(struct btrfs_trans_handle *trans,
6106			struct btrfs_root *root,
6107			struct extent_buffer *node,
6108			struct extent_buffer *parent)
6109{
6110	struct btrfs_fs_info *fs_info = root->fs_info;
6111	struct btrfs_path *path;
6112	struct walk_control *wc;
6113	int level;
6114	int parent_level;
6115	int ret = 0;
6116	int wret;
6117
6118	BUG_ON(root->root_key.objectid != BTRFS_TREE_RELOC_OBJECTID);
6119
6120	path = btrfs_alloc_path();
6121	if (!path)
6122		return -ENOMEM;
6123
6124	wc = kzalloc(sizeof(*wc), GFP_NOFS);
6125	if (!wc) {
6126		btrfs_free_path(path);
6127		return -ENOMEM;
6128	}
6129
6130	btrfs_assert_tree_write_locked(parent);
6131	parent_level = btrfs_header_level(parent);
6132	atomic_inc(&parent->refs);
6133	path->nodes[parent_level] = parent;
6134	path->slots[parent_level] = btrfs_header_nritems(parent);
6135
6136	btrfs_assert_tree_write_locked(node);
6137	level = btrfs_header_level(node);
6138	path->nodes[level] = node;
6139	path->slots[level] = 0;
6140	path->locks[level] = BTRFS_WRITE_LOCK;
6141
6142	wc->refs[parent_level] = 1;
6143	wc->flags[parent_level] = BTRFS_BLOCK_FLAG_FULL_BACKREF;
6144	wc->level = level;
6145	wc->shared_level = -1;
6146	wc->stage = DROP_REFERENCE;
6147	wc->update_ref = 0;
6148	wc->keep_locks = 1;
6149	wc->reada_count = BTRFS_NODEPTRS_PER_BLOCK(fs_info);
6150
6151	while (1) {
6152		wret = walk_down_tree(trans, root, path, wc);
6153		if (wret < 0) {
6154			ret = wret;
6155			break;
6156		}
6157
6158		wret = walk_up_tree(trans, root, path, wc, parent_level);
6159		if (wret < 0)
6160			ret = wret;
6161		if (wret != 0)
6162			break;
6163	}
6164
6165	kfree(wc);
6166	btrfs_free_path(path);
6167	return ret;
6168}
6169
6170int btrfs_error_unpin_extent_range(struct btrfs_fs_info *fs_info,
6171				   u64 start, u64 end)
 
 
 
6172{
6173	return unpin_extent_range(fs_info, start, end, false);
6174}
6175
6176/*
6177 * It used to be that old block groups would be left around forever.
6178 * Iterating over them would be enough to trim unused space.  Since we
6179 * now automatically remove them, we also need to iterate over unallocated
6180 * space.
6181 *
6182 * We don't want a transaction for this since the discard may take a
6183 * substantial amount of time.  We don't require that a transaction be
6184 * running, but we do need to take a running transaction into account
6185 * to ensure that we're not discarding chunks that were released or
6186 * allocated in the current transaction.
6187 *
6188 * Holding the chunks lock will prevent other threads from allocating
6189 * or releasing chunks, but it won't prevent a running transaction
6190 * from committing and releasing the memory that the pending chunks
6191 * list head uses.  For that, we need to take a reference to the
6192 * transaction and hold the commit root sem.  We only need to hold
6193 * it while performing the free space search since we have already
6194 * held back allocations.
6195 */
6196static int btrfs_trim_free_extents(struct btrfs_device *device, u64 *trimmed)
6197{
6198	u64 start = BTRFS_DEVICE_RANGE_RESERVED, len = 0, end = 0;
6199	int ret;
6200
6201	*trimmed = 0;
6202
6203	/* Discard not supported = nothing to do. */
6204	if (!bdev_max_discard_sectors(device->bdev))
6205		return 0;
6206
6207	/* Not writable = nothing to do. */
6208	if (!test_bit(BTRFS_DEV_STATE_WRITEABLE, &device->dev_state))
6209		return 0;
6210
6211	/* No free space = nothing to do. */
6212	if (device->total_bytes <= device->bytes_used)
6213		return 0;
6214
6215	ret = 0;
6216
6217	while (1) {
6218		struct btrfs_fs_info *fs_info = device->fs_info;
6219		u64 bytes;
6220
6221		ret = mutex_lock_interruptible(&fs_info->chunk_mutex);
6222		if (ret)
6223			break;
6224
6225		find_first_clear_extent_bit(&device->alloc_state, start,
6226					    &start, &end,
6227					    CHUNK_TRIMMED | CHUNK_ALLOCATED);
6228
6229		/* Check if there are any CHUNK_* bits left */
6230		if (start > device->total_bytes) {
6231			WARN_ON(IS_ENABLED(CONFIG_BTRFS_DEBUG));
6232			btrfs_warn_in_rcu(fs_info,
6233"ignoring attempt to trim beyond device size: offset %llu length %llu device %s device size %llu",
6234					  start, end - start + 1,
6235					  btrfs_dev_name(device),
6236					  device->total_bytes);
6237			mutex_unlock(&fs_info->chunk_mutex);
6238			ret = 0;
6239			break;
6240		}
6241
6242		/* Ensure we skip the reserved space on each device. */
6243		start = max_t(u64, start, BTRFS_DEVICE_RANGE_RESERVED);
6244
6245		/*
6246		 * If find_first_clear_extent_bit find a range that spans the
6247		 * end of the device it will set end to -1, in this case it's up
6248		 * to the caller to trim the value to the size of the device.
6249		 */
6250		end = min(end, device->total_bytes - 1);
6251
6252		len = end - start + 1;
6253
6254		/* We didn't find any extents */
6255		if (!len) {
6256			mutex_unlock(&fs_info->chunk_mutex);
6257			ret = 0;
6258			break;
6259		}
6260
6261		ret = btrfs_issue_discard(device->bdev, start, len,
6262					  &bytes);
6263		if (!ret)
6264			set_extent_bit(&device->alloc_state, start,
6265				       start + bytes - 1, CHUNK_TRIMMED, NULL);
6266		mutex_unlock(&fs_info->chunk_mutex);
6267
6268		if (ret)
6269			break;
6270
6271		start += len;
6272		*trimmed += bytes;
6273
6274		if (fatal_signal_pending(current)) {
6275			ret = -ERESTARTSYS;
6276			break;
6277		}
6278
6279		cond_resched();
6280	}
6281
6282	return ret;
6283}
6284
6285/*
6286 * Trim the whole filesystem by:
6287 * 1) trimming the free space in each block group
6288 * 2) trimming the unallocated space on each device
6289 *
6290 * This will also continue trimming even if a block group or device encounters
6291 * an error.  The return value will be the last error, or 0 if nothing bad
6292 * happens.
6293 */
6294int btrfs_trim_fs(struct btrfs_fs_info *fs_info, struct fstrim_range *range)
6295{
6296	struct btrfs_fs_devices *fs_devices = fs_info->fs_devices;
6297	struct btrfs_block_group *cache = NULL;
6298	struct btrfs_device *device;
6299	u64 group_trimmed;
6300	u64 range_end = U64_MAX;
6301	u64 start;
6302	u64 end;
6303	u64 trimmed = 0;
6304	u64 bg_failed = 0;
6305	u64 dev_failed = 0;
6306	int bg_ret = 0;
6307	int dev_ret = 0;
6308	int ret = 0;
6309
6310	if (range->start == U64_MAX)
6311		return -EINVAL;
6312
6313	/*
6314	 * Check range overflow if range->len is set.
6315	 * The default range->len is U64_MAX.
6316	 */
6317	if (range->len != U64_MAX &&
6318	    check_add_overflow(range->start, range->len, &range_end))
6319		return -EINVAL;
6320
6321	cache = btrfs_lookup_first_block_group(fs_info, range->start);
6322	for (; cache; cache = btrfs_next_block_group(cache)) {
6323		if (cache->start >= range_end) {
6324			btrfs_put_block_group(cache);
6325			break;
6326		}
6327
6328		start = max(range->start, cache->start);
6329		end = min(range_end, cache->start + cache->length);
6330
6331		if (end - start >= range->minlen) {
6332			if (!btrfs_block_group_done(cache)) {
6333				ret = btrfs_cache_block_group(cache, true);
6334				if (ret) {
6335					bg_failed++;
6336					bg_ret = ret;
6337					continue;
6338				}
6339			}
6340			ret = btrfs_trim_block_group(cache,
6341						     &group_trimmed,
6342						     start,
6343						     end,
6344						     range->minlen);
6345
6346			trimmed += group_trimmed;
6347			if (ret) {
6348				bg_failed++;
6349				bg_ret = ret;
6350				continue;
6351			}
6352		}
6353	}
6354
6355	if (bg_failed)
6356		btrfs_warn(fs_info,
6357			"failed to trim %llu block group(s), last error %d",
6358			bg_failed, bg_ret);
6359
6360	mutex_lock(&fs_devices->device_list_mutex);
6361	list_for_each_entry(device, &fs_devices->devices, dev_list) {
6362		if (test_bit(BTRFS_DEV_STATE_MISSING, &device->dev_state))
6363			continue;
6364
6365		ret = btrfs_trim_free_extents(device, &group_trimmed);
6366		if (ret) {
6367			dev_failed++;
6368			dev_ret = ret;
6369			break;
6370		}
6371
6372		trimmed += group_trimmed;
6373	}
6374	mutex_unlock(&fs_devices->device_list_mutex);
6375
6376	if (dev_failed)
6377		btrfs_warn(fs_info,
6378			"failed to trim %llu device(s), last error %d",
6379			dev_failed, dev_ret);
6380	range->len = trimmed;
6381	if (bg_ret)
6382		return bg_ret;
6383	return dev_ret;
6384}