extent-tree.c

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