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